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: