hashlist.h (18790B)
1 #pragma once
2
3 #include "libsheepyObject.h"
4 #include "shpPackages/hashtable/hashtable.h"
5
6 /**
7 * \file
8 *
9 * hashlist - random access double linked lists
10 *
11 * this data structure is a double linked list in a hashtable
12 * each node in the list has a key, any node in the list is accessed using a key
13 * multiple lists can be created in the hashtable
14 *
15 * the macros in this define and implement the hashlist types and functions
16 * the hash function has to be provided by another package (hashfunctions)
17 *
18 * - hashlistDef defines the types and function prototype for the hashlist and hashtable
19 * - hashlistFunctions implements the hashlist and hashtable functions
20 *
21 * the hashlist function names have the following pattern:
22 * hashlistFUNCTION_NAME##hashlistFuncSuffix
23 *
24 * the hashtable function names have the following pattern:
25 * FUNCTION_NAME##hashlistFuncSuffix
26 *
27 * the hashlist type is: hashlistTypeName##t
28 * the hashlist node type is: valueTypeName##t
29 *
30 * node.key is the key
31 * node.prev is a pointer to previous node, NULL when node is head
32 * node.next is a pointer to next node, NULL when node is last
33 *
34 * Use the regular hashtable functions to access the nodes using the keys: get####hashlistFuncSuffix, find##hashlistFuncSuffix...
35 *
36 * Push, Prepend, AppendAfter, AppendBefore add new nodes and return a pointer to it
37 * AddAfter, AddAfterKey, AddBefore, AddBeforeKey add new nodes and store the value in parameter in it
38 *
39 * Use Unlink to crop a node from the list and then use the FreeNode or Insert functions
40 *
41 * function descriptions:
42 *
43 * - Create: create a new list and store value in first node.
44 * Returns: node pointer or NULL when key already exists
45 * - New: create a new list and a new node with given key.
46 * Returns: node pointer or NULL when key already exists
47 * - Free: free all nodes in list (nodes before and after given node are freed, node doesn't need to be head or last)
48 * - Release: free all nodes in list starting with node with given key
49 * (nodes before and after given key are freed, node doesn't need to be head or last)
50 * - Push: add a new node with newKey after given node.
51 * Returns: new node pointer or NULL when node is NULL or when key already exists
52 * - Prepend: add a new node with newKey before given node.
53 * Returns: new node pointer or NULL when node is NULL or when key already exists
54 * - AppendAfter: add a new node with newKey after node given key.
55 * Returns: new node pointer or NULL when key doesn't exists or when key already exists
56 * - AppendBefore: add a new node with newKey before node given key.
57 * Returns: new node pointer or NULL when key doesn't exists or when key already exists
58 * - Unlink: crop node from the list.
59 * Returns node pointer or NULL when node is NULL
60 * - UnlinkKey: crop node with given key from the list.
61 * Returns node pointer or NULL when key doesn't exists
62 * - FreeNode (del##hashlistFuncSuffix): free an unlinked node.
63 * Returns: true or false when node is NULL
64 * - DelNode: unlink and free node
65 * - Del: unlink and free node with given key
66 * - InsertAfter: insert unlinked node after given node. Returns node pointer or NULL when node or value are NULL
67 * - InsertAfterKey: insert unlinked node after node with key. Returns node pointer or NULL when key doesn't exists or value is NULL
68 * - InsertBefore: insert unlinked node before given node. Returns node pointer or NULL when node or value are NULL
69 * - InsertBeforeKey: insert unlinked node before node with key. Returns node pointer or NULL when key doesn't exists or value is NULL
70 * - AddAfter: add new node and store value in it after node.
71 * Returns: new node pointer or NULL when node is NULL or value.key already exists
72 * - AddAfterKey: add new node and store value in it after node with given key.
73 * Returns: new node pointer or NULL when key doesn't exists or value.key already exists
74 * - AddBefore: add new node and store value in it before node.
75 * Returns: new node pointer or NULL when node is NULL or value.key already exists
76 * - AddBeforeKey: add new node and store value in it before node with given key.
77 * Returns: new node pointer or NULL when key doesn't exists or value.key already exists
78 *
79 * Example:
80 * See main.c for more details
81 *
82 * // define node members:
83 * #define listMembers char *v;
84 *
85 * // define hashlist
86 * hashlistDef(, lists, Lists, u64, list, u64, listMembers);
87 *
88 * // select hashtable functions
89 * #define HASHFUNC u64Hash
90 * #define CMPFUNC cmpU64
91 * #define FREEFUNC freeList
92 *
93 * // implement hashlist functions
94 * hashlistFunctions(, lists, Lists, u64, list, u64, listMembers,
95 * int cmpU64(u64 k1, u64 k2) {
96 * return k1 == k2;
97 * }
98 * void freeList(u64 *k, listt *v) {
99 * });
100 *
101 * // undef functions
102 * #undef HASHFUNC
103 * #undef CMPFUNC
104 * #undef FREEFUNC
105 *
106 * // declare hashlist
107 * listst hlists;
108 *
109 * // initlialize hashlist
110 * initLists(&hlists);
111 *
112 * // declare hashlist node
113 * listt g;
114 *
115 * // create new list
116 * g.key = 0;
117 * g.v = "sdf";
118 * listt *head = hashlistCreateLists(&hlists, g);
119 *
120 * // access node
121 * listt *G = findLists(&hlists, 0);
122 * logVarG(G->v);
123 *
124 * // push new node
125 * G = hashlistPushLists(&hlists, head, 1);
126 * G->v = "22";
127 *
128 * // free list
129 * hashlistFreeLists(&hlists, head);
130 *
131 * // free hashlist
132 * freeLists(&hlists);
133 *
134 */
135
136 #define hashlistDef(scope, hashlistTypeName, hashlistFuncSuffix, keyType, valueTypeName, hashType, valueMembers)\
137 typ struct valueTypeName##t valueTypeName##t;\
138 struct valueTypeName##t {\
139 /* linked list */\
140 keyType key;\
141 valueTypeName##t *prev; /* prev list node */\
142 valueTypeName##t *next; /* next list node */\
143 valueMembers\
144 };\
145 \
146 hashTbDef(scope, hashlistTypeName /* hashlistTypeNamet hashtable */, hashlistFuncSuffix /* functions: inithashlistFuncSuffix,... */, keyType /* key */, valueTypeName##t /* value */, hashType /* hash */);\
147 scope valueTypeName##t* hashlistCreate##hashlistFuncSuffix(hashlistTypeName##t *hashlist, valueTypeName##t value);\
148 scope valueTypeName##t* hashlistNew##hashlistFuncSuffix(hashlistTypeName##t *hashlist, keyType key);\
149 scope void hashlistFree##hashlistFuncSuffix(hashlistTypeName##t *hashlist, valueTypeName##t *node);\
150 scope void hashlistRelease##hashlistFuncSuffix(hashlistTypeName##t *hashlist, keyType key);\
151 scope valueTypeName##t* hashlistPush##hashlistFuncSuffix(hashlistTypeName##t *hashlist, valueTypeName##t *node, keyType newKey);\
152 scope valueTypeName##t* hashlistPrepend##hashlistFuncSuffix(hashlistTypeName##t *hashlist, valueTypeName##t *node, keyType newKey);\
153 scope valueTypeName##t* hashlistAppendAfter##hashlistFuncSuffix(hashlistTypeName##t *hashlist, keyType key, keyType newKey);\
154 scope valueTypeName##t* hashlistAppendBefore##hashlistFuncSuffix(hashlistTypeName##t *hashlist, keyType key, keyType newKey);\
155 scope valueTypeName##t* hashlistUnlink##hashlistFuncSuffix(valueTypeName##t *node);\
156 scope valueTypeName##t* hashlistUnlinkKey##hashlistFuncSuffix(hashlistTypeName##t *hashlist, keyType key);\
157 scope bool hashlistFreeNode##hashlistFuncSuffix(hashlistTypeName##t *hashlist, valueTypeName##t *node);\
158 scope bool hashlistDelNode##hashlistFuncSuffix(hashlistTypeName##t *hashlist, valueTypeName##t *node);\
159 scope void hashlistDel##hashlistFuncSuffix(hashlistTypeName##t *hashlist, keyType key);\
160 scope valueTypeName##t* hashlistInsertAfter##hashlistFuncSuffix(valueTypeName##t *node, valueTypeName##t *value);\
161 scope valueTypeName##t* hashlistInsertAfterKey##hashlistFuncSuffix(hashlistTypeName##t *hashlist, keyType key, valueTypeName##t *value);\
162 scope valueTypeName##t* hashlistInsertBefore##hashlistFuncSuffix(valueTypeName##t *node, valueTypeName##t *value);\
163 scope valueTypeName##t* hashlistInsertBeforeKey##hashlistFuncSuffix(hashlistTypeName##t *hashlist, keyType key, valueTypeName##t *value);\
164 scope valueTypeName##t* hashlistAddAfter##hashlistFuncSuffix(hashlistTypeName##t *hashlist, valueTypeName##t *node, valueTypeName##t value);\
165 scope valueTypeName##t* hashlistAddAfterKey##hashlistFuncSuffix(hashlistTypeName##t *hashlist, keyType key, valueTypeName##t value);\
166 scope valueTypeName##t* hashlistAddBefore##hashlistFuncSuffix(hashlistTypeName##t *hashlist, valueTypeName##t *node, valueTypeName##t value);\
167 scope valueTypeName##t* hashlistAddBeforeKey##hashlistFuncSuffix(hashlistTypeName##t *hashlist, keyType key, valueTypeName##t value);
168
169 #define hashlistFunctions(scope, hashlistTypeName, hashlistFuncSuffix, keyType, valueTypeName, hashType, valueMembers, functions /* declare the functions here */)\
170 functions;\
171 \
172 hashTbFunctions(scope, hashlistTypeName, hashlistFuncSuffix, keyType /* key */, valueTypeName##t /* value */)\
173 /* create head - first node in list */\
174 scope valueTypeName##t* hashlistCreate##hashlistFuncSuffix(hashlistTypeName##t *hashlist, valueTypeName##t value) {\
175 value.prev = value.next = NULL;\
176 bool r;\
177 valueTypeName##t* res = addOrFind##hashlistFuncSuffix(hashlist, value.key, &r);\
178 if (!r) ret NULL;\
179 *res = value;\
180 ret res;\
181 }\
182 /* create new head with given key - first node in list */\
183 scope valueTypeName##t* hashlistNew##hashlistFuncSuffix(hashlistTypeName##t *hashlist, keyType key) {\
184 bool r;\
185 valueTypeName##t* res = addOrFind##hashlistFuncSuffix(hashlist, key, &r);\
186 if (!r) ret NULL;\
187 res->prev = res->next = NULL;\
188 res->key = key;\
189 ret res;\
190 }\
191 /* free list */\
192 scope void hashlistFree##hashlistFuncSuffix(hashlistTypeName##t *hashlist, valueTypeName##t *node) {\
193 if (!node) ret;\
194 if (node->next) {\
195 if (node->prev) {\
196 /* there are nodes before and after */\
197 var prev = node->prev;\
198 /* delete node and next nodes */\
199 var n = node;\
200 var tmp = n;\
201 while (n) {\
202 tmp = n->next;\
203 del##hashlistFuncSuffix(hashlist, n->key);\
204 n = tmp;\
205 }\
206 /* delete previous nodes */\
207 n = prev;\
208 while (n) {\
209 tmp = n->prev;\
210 del##hashlistFuncSuffix(hashlist, n->key);\
211 n = tmp;\
212 }\
213 }\
214 else {\
215 /* node is head, there are only next nodes*/\
216 var n = node;\
217 var tmp = n;\
218 while (n) {\
219 tmp = n->next;\
220 del##hashlistFuncSuffix(hashlist, n->key);\
221 n = tmp;\
222 }\
223 }\
224 }\
225 else {\
226 /* node is last, there are only previous nodes */\
227 var n = node;\
228 var tmp = n;\
229 while (n) {\
230 tmp = n->prev;\
231 del##hashlistFuncSuffix(hashlist, n->key);\
232 n = tmp;\
233 }\
234 }\
235 }\
236 /* free list using key */\
237 scope void hashlistRelease##hashlistFuncSuffix(hashlistTypeName##t *hashlist, keyType key) {\
238 valueTypeName##t *node = find##hashlistFuncSuffix(hashlist, key);\
239 hashlistFree##hashlistFuncSuffix(hashlist, node);\
240 }\
241 /* push */\
242 scope valueTypeName##t* hashlistPush##hashlistFuncSuffix(hashlistTypeName##t *hashlist, valueTypeName##t *node, keyType newKey) {\
243 if (!node) ret NULL;\
244 bool r;\
245 valueTypeName##t *val = addOrFind##hashlistFuncSuffix(hashlist, newKey, &r);\
246 if (!r) /* key already exists, failed to create new node */ ret NULL;\
247 val->key = newKey;\
248 /* connect new node to list */\
249 val->next = node->next;\
250 if (val->next) {\
251 val->next->prev = val;\
252 }\
253 node->next = val;\
254 val->prev = node;\
255 ret val;\
256 }\
257 /* prepend */\
258 scope valueTypeName##t* hashlistPrepend##hashlistFuncSuffix(hashlistTypeName##t *hashlist, valueTypeName##t *node, keyType newKey) {\
259 if (!node) ret NULL;\
260 bool r;\
261 valueTypeName##t *val = addOrFind##hashlistFuncSuffix(hashlist, newKey, &r);\
262 if (!r) /* key already exists, failed to create new node */ ret NULL;\
263 val->key = newKey;\
264 /* connect new node to list */\
265 val->prev = node->prev;\
266 if (val->prev) {\
267 val->prev->next = val;\
268 }\
269 node->prev = val;\
270 val->next = node;\
271 ret val;\
272 }\
273 /* append new node after node with key */\
274 scope valueTypeName##t* hashlistAppendAfter##hashlistFuncSuffix(hashlistTypeName##t *hashlist, keyType key, keyType newKey) {\
275 valueTypeName##t *node = find##hashlistFuncSuffix(hashlist, key);\
276 ret hashlistPush##hashlistFuncSuffix(hashlist, node, newKey);\
277 }\
278 /* append new node before node with key */\
279 scope valueTypeName##t* hashlistAppendBefore##hashlistFuncSuffix(hashlistTypeName##t *hashlist, keyType key, keyType newKey) {\
280 valueTypeName##t *node = find##hashlistFuncSuffix(hashlist, key);\
281 ret hashlistPrepend##hashlistFuncSuffix(hashlist, node, newKey);\
282 }\
283 /* unlink */\
284 scope valueTypeName##t* hashlistUnlink##hashlistFuncSuffix(valueTypeName##t *node) {\
285 if (!node) ret NULL;\
286 if (node->prev) {\
287 node->prev->next = node->next;\
288 }\
289 if (node->next) {\
290 node->next->prev = node->prev;\
291 }\
292 return node;\
293 }\
294 /* unlink with key */\
295 scope valueTypeName##t* hashlistUnlinkKey##hashlistFuncSuffix(hashlistTypeName##t *hashlist, keyType key) {\
296 valueTypeName##t *node = find##hashlistFuncSuffix(hashlist, key);\
297 ret hashlistUnlink##hashlistFuncSuffix(node);\
298 }\
299 /* free unlinked node */\
300 scope bool hashlistFreeNode##hashlistFuncSuffix(hashlistTypeName##t *hashlist, valueTypeName##t *node) {\
301 if (!node) ret false;\
302 del##hashlistFuncSuffix(hashlist, node->key);\
303 ret true;\
304 }\
305 /* del node */\
306 scope bool hashlistDelNode##hashlistFuncSuffix(hashlistTypeName##t *hashlist, valueTypeName##t *node) {\
307 if (!node) ret false;\
308 hashlistUnlink##hashlistFuncSuffix(node);\
309 del##hashlistFuncSuffix(hashlist, node->key);\
310 ret true;\
311 }\
312 /* del using key */\
313 scope void hashlistDel##hashlistFuncSuffix(hashlistTypeName##t *hashlist, keyType key) {\
314 hashlistTypeName##Nodet *node = unlink##hashlistFuncSuffix(hashlist, key);\
315 if (!node) /* node not found */ ret;\
316 hashlistUnlink##hashlistFuncSuffix(&node->value);\
317 freeUnlinked##hashlistFuncSuffix(hashlist, node);\
318 }\
319 /* TODO swap 2 nodes */\
320 /* insert an unlinked value after node */\
321 scope valueTypeName##t* hashlistInsertAfter##hashlistFuncSuffix(valueTypeName##t *node, valueTypeName##t *value) {\
322 if (!node or !value) ret NULL;\
323 /* connect value node to list */\
324 value->next = node->next;\
325 if (value->next) {\
326 value->next->prev = value;\
327 }\
328 node->next = value;\
329 value->prev = node;\
330 ret value;\
331 }\
332 /* insert an unlinked value after node with key */\
333 scope valueTypeName##t* hashlistInsertAfterKey##hashlistFuncSuffix(hashlistTypeName##t *hashlist, keyType key, valueTypeName##t *value) {\
334 valueTypeName##t *node = find##hashlistFuncSuffix(hashlist, key);\
335 ret hashlistInsertAfter##hashlistFuncSuffix(node, value);\
336 }\
337 /* insert an unlinked value before node */\
338 scope valueTypeName##t* hashlistInsertBefore##hashlistFuncSuffix(valueTypeName##t *node, valueTypeName##t *value) {\
339 if (!node or !value) ret NULL;\
340 /* connect value node to list */\
341 value->prev = node->prev;\
342 if (value->prev) {\
343 value->prev->next = value;\
344 }\
345 node->prev = value;\
346 value->next = node;\
347 ret value;\
348 }\
349 /* insert an unlinked value before node with key */\
350 scope valueTypeName##t* hashlistInsertBeforeKey##hashlistFuncSuffix(hashlistTypeName##t *hashlist, keyType key, valueTypeName##t *value) {\
351 valueTypeName##t *node = find##hashlistFuncSuffix(hashlist, key);\
352 ret hashlistInsertBefore##hashlistFuncSuffix(node, value);\
353 }\
354 /* Add new node after node */\
355 scope valueTypeName##t* hashlistAddAfter##hashlistFuncSuffix(hashlistTypeName##t *hashlist, valueTypeName##t *node, valueTypeName##t value) {\
356 if (!node) ret NULL;\
357 bool r;\
358 valueTypeName##t *val = addOrFind##hashlistFuncSuffix(hashlist, value.key, &r);\
359 if (!r) /* key already exists, failed to create new node */ ret NULL;\
360 /* copy data to new node */\
361 *val = value;\
362 /* connect new node to list */\
363 val->next = node->next;\
364 if (val->next) {\
365 val->next->prev = val;\
366 }\
367 node->next = val;\
368 val->prev = node;\
369 ret val;\
370 }\
371 /* Add new node after node for given key */\
372 scope valueTypeName##t* hashlistAddAfterKey##hashlistFuncSuffix(hashlistTypeName##t *hashlist, keyType key, valueTypeName##t value) {\
373 valueTypeName##t *node = find##hashlistFuncSuffix(hashlist, key);\
374 ret hashlistAddAfter##hashlistFuncSuffix(hashlist, node, value);\
375 }\
376 /* Add new node before node */\
377 scope valueTypeName##t* hashlistAddBefore##hashlistFuncSuffix(hashlistTypeName##t *hashlist, valueTypeName##t *node, valueTypeName##t value) {\
378 if (!node) ret NULL;\
379 bool r;\
380 valueTypeName##t *val = addOrFind##hashlistFuncSuffix(hashlist, value.key, &r);\
381 if (!r) /* key already exists, failed to create new node */ ret NULL;\
382 /* copy data to new node */\
383 *val = value;\
384 /* connect new node to list */\
385 val->prev = node->prev;\
386 if (val->prev) {\
387 val->prev->next = val;\
388 }\
389 node->prev = val;\
390 val->next = node;\
391 ret val;\
392 }\
393 /* Add new node before node for given key */\
394 scope valueTypeName##t* hashlistAddBeforeKey##hashlistFuncSuffix(hashlistTypeName##t *hashlist, keyType key, valueTypeName##t value) {\
395 valueTypeName##t *node = find##hashlistFuncSuffix(hashlist, key);\
396 ret hashlistAddBefore##hashlistFuncSuffix(hashlist, node, value);\
397 }\
398 /* write/read */
399
400
401 // forEach: lForEach(node, startNode) regular linked list forEach from libsheepy.h
402 #define hashlistForEach lForEach
403 #define hashlistForEachDown lForEachDown
404 #define hashlistForEachPrev lForEachPrev
405
406
407 // vim: set expandtab ts=2 sw=2: