commit 93c0140bca82ccbc02e6740b42ad557bc804a8fa
parent 9e4500f7dcf19c26dd951bfd08e69b1a77bc303e
Author: Remy Noulin <loader2x@gmail.com>
Date: Sat, 31 Aug 2019 12:07:06 +0200
add iterator
hashtable.h | 148 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
package.yml | 2 +-
2 files changed, 148 insertions(+), 2 deletions(-)
Diffstat:
| M | hashtable.h | | | 148 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++- |
| M | package.yml | | | 2 | +- |
2 files changed, 148 insertions(+), 2 deletions(-)
diff --git a/hashtable.h b/hashtable.h
@@ -46,7 +46,7 @@
* are defined with hashTbT or hashNodeT and hashtableT.
*
* The hashTb* are short and convenient macros for the hashtable* macros.
- * With hashTb* macros there is no need to specify the hash, cmp and free functions.
+ * With the hashTb* macros there is no need to specify the hash, cmp and free functions.
*
* Before using the hashTb* macros, define HASHFUNC CMPFUNC and FREEFUNC.
*
@@ -78,6 +78,16 @@
*
* See the 'node macros' section below for details on usage scenarios of the *Node macros.
*
+ * With the iterator, it is possible to loop on all nodes. Nodes can be deleted and added while the iteration
+ * is ongoing.
+ *
+ * The iterator macros are: hashTbIterStart, hashTbIterNext, hashTbIterKey, hashTbIterValue.
+ *
+ * To start the iteration call hashTbIterStart, check (name).res for status and
+ * to get the next nodes call hashTbIterNext until (name).res is false.
+ *
+ * hashTbIterKey and hashTbIterValue provide key and value for current node in iteration.
+ *
* Example:
* hashTbT(hasht, char*, u32, u32);
*
@@ -98,6 +108,10 @@
* u32 result = 0;
* hashTbGet(h, "a key", result);
*
+ * for(hashTbIterStart(h); (name).res ; hashTbIterNext(h)) {
+ * put(hashTbIterKey(h));
+ * }
+ *
* hashTbDel(h, "a key");
*
* hashTbFree(h);
@@ -341,6 +355,18 @@
/** delete a node */
#define hashTbDelNode(HT, NODECONTEXT) hashtableDelNode(HT, NODECONTEXT, FREEFUNC)
+/** start iteration on all nodes */
+#define hashTbIterStart(name) hashtableIterStart(name)
+
+/** move to next node in iteration */
+#define hashTbIterNext(name) hashtableIterNext(name)
+
+/** key of node in iteration */
+#define hashTbIterKey(name) hashtableIterKey(name)
+
+/** value of node in iteration */
+#define hashTbIterValue(name) hashtableIterValue(name)
+
/**
* node definition for bucket single linked lists
*
@@ -395,6 +421,10 @@
u32 loadfactor_denominator;\
bool res; /* return value for macros */\
bool newNodeInDArray; /* add, addOrFind and addOrFindNode set this flag: true an new node is pushed in aHashnode, false an existing array element is recycled */\
+ u32 iterIdx; /* iterator bucket index */\
+ u8 iterMoreOrLess; /* iterator list index */\
+ nodeType* iterNode; /* iterator node - NULL when iteration is finished or not started */\
+ nodeType* iterNext; /* iterator next node */\
} typeName
/**
@@ -445,6 +475,11 @@ u32 ilog2Hashtable(u32 value);
memset((name).list, 0, (name).size * 2 * sizeof(typeof((name).node)*));\
(name).count = 0;\
(name).res = true;\
+ (name).newNodeInDArray = false;\
+ (name).iterIdx = 0;\
+ (name).iterMoreOrLess = 0;\
+ (name).iterNode = NULL;\
+ (name).iterNext = NULL;\
} while(0)
/** Internal - for testing the hash table
@@ -1308,6 +1343,117 @@ u32 ilog2Hashtable(u32 value);
hashtableInternalDelNode(name, (nodeContext).node, (nodeContext).mhash, (nodeContext).prev, (nodeContext).moreOrLess);\
} while(0)
+/**
+ * start iteration on all nodes
+ *
+ * To get the key and value of current node in iteration use:
+ * hashtableIterKey and hashtableIterValue
+ *
+ * \return
+ * (name).res = true when first node is found
+ * (name).res = false when no node is found
+ */
+#define hashtableIterStart(name) procbegin\
+ if (!(name).count) {\
+ (name).iterNode = NULL;\
+ (name).res = false;\
+ goto UNIQVAR(end);\
+ }\
+ range(UNIQVAR(i), (name).size) {\
+ if ((*(name).list)[UNIQVAR(i)][0]) {\
+ (name).iterNode = (*(name).list)[UNIQVAR(i)][0];\
+ (name).iterIdx = UNIQVAR(i);\
+ (name).iterMoreOrLess = 0;\
+ goto UNIQVAR(foundFirstElement);\
+ }\
+ }\
+ /* no element found - should not happen because count == 0 */\
+ (name).iterNode = NULL;\
+ (name).res = false;\
+ goto UNIQVAR(end);\
+ UNIQVAR(foundFirstElement):\
+ hashtableInternalIterNext(name);\
+ (name).res = true;\
+ UNIQVAR(end):;\
+ procend
+
+/**
+ * move to next node in iteration
+ *
+ * Before call this macro, the iteration has to be started with
+ * hashtableIterStart
+ *
+ * To get the key and value of current node in iteration use:
+ * hashtableIterKey and hashtableIterValue
+ *
+ * \return
+ * (name).res = true when next node is found
+ * (name).res = false when no node is found (iteration is finished or not started, (name).iterNode is set to NULL)
+ */
+#define hashtableIterNext(name) procbegin\
+ if (!(name).iterNode) {\
+ /* iteration is finished or not started */\
+ (name).res = false;\
+ goto UNIQVAR(end);\
+ }\
+ (name).iterNode = (name).iterNext;\
+ if ((name).iterNode) {\
+ hashtableInternalIterNext(name);\
+ (name).res = true;\
+ goto UNIQVAR(end);\
+ }\
+ /* find next linked list or the iteration is finished */\
+ if ((name).iterMoreOrLess == 0) {\
+ /* check second linked list for iterIdx */\
+ (name).iterNode = (*(name).list)[(name).iterIdx][1];\
+ if ((name).iterNode) {\
+ (name).iterMoreOrLess = 1;\
+ goto UNIQVAR(foundElement);\
+ }\
+ }\
+ /* fixIterMoreOrLess == 1 or no node in second list */\
+ (name).iterIdx++;\
+ rangeFrom(UNIQVAR(i), (name).iterIdx, (name).size) {\
+ /* if there is an element at this index it is always in the first list */\
+ if ((*(name).list)[UNIQVAR(i)][0]) {\
+ (name).iterNode = (*(name).list)[UNIQVAR(i)][0];\
+ (name).iterIdx = UNIQVAR(i);\
+ (name).iterMoreOrLess = 0;\
+ goto UNIQVAR(foundElement);\
+ }\
+ }\
+ /* no next node found - iterNode is NULL */\
+ (name).res = false;\
+ goto UNIQVAR(end);\
+ UNIQVAR(foundElement):;\
+ hashtableInternalIterNext(name);\
+ (name).res = true;\
+ UNIQVAR(end):;\
+ procend
+
+/** key of node in iteration */
+#define hashtableIterKey(name) ((name).iterNode->key)
+
+/** value of node in iteration */
+#define hashtableIterValue(name) ((name).iterNode->value)
+
+/** internal macro to find next node in iteration */
+#define hashtableInternalIterNext(name) procbegin\
+ /* save next pointer to allow calls to delete current element */\
+ /* and still iterate through all elements*/\
+ if ((*(name).list)[(name).iterIdx][0] == (name).iterNode\
+ and !(name).iterNode->next\
+ and (*(name).list)[(name).iterIdx][1]) {\
+ /* check if current node is a unique node in first linked list */\
+ /* and there is a least one node in the second linked list. */\
+ (name).iterNext = (*(name).list)[(name).iterIdx][1];\
+ (name).iterMoreOrLess = 1;\
+ }\
+ else {\
+ (name).iterNext = (name).iterNode->next;\
+ }\
+ procend
+
// the function in hashtable doesnt depend on libsheepy, no need to recompile when libsheepy version is changed
#define isHashtableCompiledWithCurrentLisheepyVersion true
diff --git a/package.yml b/package.yml
@@ -1,6 +1,6 @@
---
name: hashtable
- version: 0.0.16
+ version: 0.0.17
description: "hash table macros for creating hash table functions, it supports any type key, value, hash"
bin: ./hashtable.c
cflags: "-O1 -std=gnu11 -fPIC -pipe"
