1 /* 2 * 3 * Thread-safe Dictionary Using String Identifiers 4 * Copyright 1998-2000 Scott Shambarger (scott (at) shambarger.net) 5 * 6 * This software is open source. Permission to use, copy, modify, and 7 * distribute this software for any purpose and without fee is hereby granted, 8 * provided that the above copyright notice appear in all copies. No 9 * warranty of any kind is expressed or implied. Use at your own risk. 10 * 11 */ 12 13 #include "cs_config.h" 14 15 #include <string.h> 16 #include <stdlib.h> 17 #include <stdio.h> 18 #include <assert.h> 19 20 #include "neo_misc.h" 21 #include "neo_err.h" 22 #include "dict.h" 23 #include "skiplist.h" 24 #include "ulocks.h" 25 26 27 typedef struct dictValue { 28 29 void *value; /* value to set/update */ 30 dictNewValueCB new; /* new value callback (value is NULL) */ 31 dictUpdateValueCB update; /* update value callback (value is NULL) */ 32 void *rock; /* rock to pass to callbacks */ 33 34 } *dictValuePtr; 35 36 typedef struct dictItem { 37 38 struct dictItem *next; /* pointer to next value */ 39 char *id; /* string id */ 40 void *value; /* value */ 41 42 } *dictItemPtr; 43 44 typedef struct dictEntry { 45 46 dictItemPtr first; /* first item in entry */ 47 BOOL deleted; /* TRUE if entry has been passed to skipDelete */ 48 49 } *dictEntryPtr; 50 51 typedef UINT32 (*dictHashFunc)(const char *str); 52 typedef int (*dictCompFunc)(const char *s1, const char *s2); 53 54 struct _dictCtx { 55 56 pthread_mutex_t mList; /* list update mutex */ 57 skipList list; /* skip list */ 58 59 dictHashFunc hash; /* hash function */ 60 dictCompFunc comp; /* id compare function */ 61 BOOL useCase; 62 63 BOOL threaded; /* TRUE if threaded */ 64 dictFreeValueFunc freeValue; /* free value callback */ 65 void *freeRock; /* context for freeValue */ 66 }; 67 68 #undef DO_DEBUG 69 70 #ifdef DO_DEBUG 71 #include <sched.h> 72 #define DICT_LOCK(dict) \ 73 do { if((dict)->threaded) { sched_yield(); \ 74 mLock(&(dict)->mList); } } while(0) 75 #define DICT_HASH_BITS 16 76 #else 77 #define DICT_LOCK(dict) \ 78 if((dict)->threaded) mLock(&(dict)->mList) 79 #define DICT_HASH_BITS 65536 80 #endif 81 #define DICT_UNLOCK(dict) \ 82 if((dict)->threaded) mUnlock(&(dict)->mList) 83 84 /* entry is locked, so item may be added */ 85 static NEOERR *dictNewItem(dictCtx dict, dictEntryPtr entry, 86 const char *id, dictValuePtr newval, dictItemPtr *item) 87 { 88 dictItemPtr my_item; 89 90 if (item != NULL) 91 *item = NULL; 92 93 /* check if we can set a new value */ 94 if(! (newval->value || newval->new)) 95 return nerr_raise(NERR_ASSERT, "value or new are NULL"); 96 97 if(! (my_item = calloc(1, sizeof(struct dictItem)))) 98 return nerr_raise(NERR_NOMEM, "Unable to allocate new dictItem"); 99 100 if(! (my_item->id = strdup(id))) { 101 free(my_item); 102 return nerr_raise(NERR_NOMEM, "Unable to allocate new id for dictItem"); 103 } 104 105 /* set new value */ 106 if(newval->value) { 107 my_item->value = newval->value; 108 } 109 else { 110 NEOERR *err = STATUS_OK; 111 112 err = newval->new(id, newval->rock, &(my_item->value)); 113 if (err != STATUS_OK) 114 { 115 /* new item callback failed, cleanup */ 116 free(my_item->id); 117 free(my_item); 118 119 return nerr_pass(err); 120 } 121 } 122 123 my_item->next = entry->first; 124 entry->first = my_item; 125 if (item != NULL) 126 *item = my_item; 127 128 return STATUS_OK; 129 } 130 131 static void dictFreeItem(dictCtx dict, dictItemPtr item) { 132 133 if(dict->freeValue) 134 dict->freeValue(item->value, dict->freeRock); 135 free(item->id); 136 free(item); 137 138 return; 139 } 140 141 /* list locked, so safe to walk entry */ 142 static dictItemPtr dictFindItem(dictCtx dict, dictEntryPtr entry, 143 const char *id, BOOL unlink) { 144 145 dictItemPtr *prev, item; 146 147 prev = &entry->first; 148 149 for(item = entry->first; item; item = item->next) { 150 151 if(! dict->comp(item->id, id)) { 152 153 if(unlink) 154 *prev = item->next; 155 156 return item; 157 } 158 159 prev = &item->next; 160 } 161 162 return NULL; 163 } 164 165 static NEOERR *dictUpdate(dictCtx dict, dictEntryPtr entry, const char *id, 166 dictValuePtr newval, void *lock) { 167 168 NEOERR *err = STATUS_OK; 169 dictItemPtr item = NULL; 170 void *newValue; 171 172 /* check for entry (maybe not found...) */ 173 if(! entry) 174 return nerr_raise(NERR_NOT_FOUND, "Entry is NULL"); 175 176 /* only use entry if not deleted */ 177 if(! entry->deleted) { 178 179 /* find item */ 180 if((item = dictFindItem(dict, entry, id, FALSE))) { 181 182 if(newval->value) { 183 184 if(dict->freeValue) 185 dict->freeValue(item->value, dict->freeRock); 186 187 item->value = newval->value; 188 } 189 else if(newval->update) { 190 191 /* track error (if update fails) */ 192 err = newval->update(id, item->value, newval->rock); 193 } 194 else if((err = newval->new(id, newval->rock, &newValue)) == STATUS_OK) { 195 196 if(dict->freeValue) 197 dict->freeValue(item->value, dict->freeRock); 198 199 item->value = newValue; 200 } 201 else { 202 /* new item failed (don't remove old), indicate that update failed */ 203 item = NULL; 204 } 205 } 206 else { 207 208 /* add new item to entry */ 209 err = dictNewItem(dict, entry, id, newval, &item); 210 } 211 } 212 213 /* release entry lock */ 214 skipRelease(dict->list, lock); 215 216 return nerr_pass(err); 217 } 218 219 static NEOERR *dictInsert(dictCtx dict, UINT32 hash, const char *id, 220 dictValuePtr newval) { 221 222 dictEntryPtr entry; 223 void *lock; 224 NEOERR *err = STATUS_OK; 225 226 /* create new item and insert entry */ 227 entry = calloc(1, sizeof(struct dictEntry)); 228 if (entry == NULL) 229 return nerr_raise(NERR_NOMEM, "Unable to allocate memory for dictEntry"); 230 231 /* create/insert item (or cleanup) */ 232 err = dictNewItem(dict, entry, id, newval, NULL); 233 if (err != STATUS_OK) return nerr_pass(err); 234 235 /* if we insert, we're done */ 236 if((err = skipInsert(dict->list, hash, entry, FALSE)) == STATUS_OK) 237 return STATUS_OK; 238 239 /* failed to insert, cleanup */ 240 if(dict->freeValue && ! newval->value) 241 dict->freeValue(entry->first->value, dict->freeRock); 242 free(entry->first->id); 243 free(entry->first); 244 free(entry); 245 246 /* check err */ 247 if (!nerr_handle(&err, NERR_DUPLICATE)) 248 return nerr_pass(err); 249 250 /* cool, someone already inserted the entry before we got the lock */ 251 entry = skipSearch(dict->list, hash, &lock); 252 253 /* update entry as normal (handles entry not found) */ 254 return nerr_pass(dictUpdate(dict, entry, id, newval, lock)); 255 } 256 257 static UINT32 dictHash(dictCtx dict, const char *id) { 258 259 UINT32 hash; 260 261 hash = dict->hash(id) % DICT_HASH_BITS; 262 263 /* ensure hash is valid for skiplist (modify consistently if not) */ 264 if(! (hash && (hash != (UINT32)-1))) 265 hash = 1; 266 267 return hash; 268 } 269 270 static NEOERR *dictModify(dictCtx dict, const char *id, dictValuePtr newval) 271 { 272 NEOERR *err; 273 UINT32 hash; 274 dictEntryPtr entry; 275 void *lock = NULL; 276 277 hash = dictHash(dict, id); 278 279 /* find entry in list */ 280 entry = skipSearch(dict->list, hash, &lock); 281 282 DICT_LOCK(dict); 283 284 if((err = dictUpdate(dict, entry, id, newval, lock)) != STATUS_OK) 285 { 286 /* insert new entry */ 287 nerr_ignore(&err); 288 err = dictInsert(dict, hash, id, newval); 289 } 290 291 DICT_UNLOCK(dict); 292 293 return nerr_pass(err); 294 } 295 296 NEOERR *dictSetValue(dictCtx dict, const char *id, void *value) { 297 298 struct dictValue newval; 299 300 assert(value); 301 302 newval.value = value; 303 304 return dictModify(dict, id, &newval); 305 } 306 307 NEOERR *dictModifyValue(dictCtx dict, const char *id, dictNewValueCB new, 308 dictUpdateValueCB update, void *rock) { 309 310 struct dictValue newval; 311 312 if(! (new || update)) 313 return FALSE; 314 315 newval.value = NULL; 316 newval.new = new; 317 newval.update = update; 318 newval.rock = rock; 319 320 return dictModify(dict, id, &newval); 321 } 322 323 void dictReleaseLock(dictCtx dict, void *lock) { 324 325 /* release entry */ 326 DICT_UNLOCK(dict); 327 328 /* release skip entry */ 329 skipRelease(dict->list, lock); 330 331 return; 332 } 333 334 void dictCleanup(dictCtx dict, dictCleanupFunc cleanup, void *rock) { 335 336 dictItemPtr *prev, item, next; 337 dictEntryPtr entry; 338 UINT32 key = 0; 339 void *lock; 340 341 while((entry = skipNext(dict->list, &key, &lock))) { 342 343 DICT_LOCK(dict); 344 345 prev = &entry->first; 346 347 for(item = entry->first; item; item = next) { 348 349 next = item->next; 350 351 if(cleanup(item->id, item->value, rock)) { 352 353 /* remove item */ 354 *prev = item->next; 355 dictFreeItem(dict, item); 356 } 357 else { 358 /* update reference pointer */ 359 prev = &item->next; 360 } 361 } 362 363 /* delete entry if last item removed */ 364 if(! entry->first) { 365 366 entry->deleted = TRUE; 367 368 skipDelete(dict->list, key); 369 } 370 371 dictReleaseLock(dict, lock); 372 } 373 374 return; 375 } 376 377 void *dictSearch(dictCtx dict, const char *id, void **plock) { 378 379 dictEntryPtr entry; 380 dictItemPtr item; 381 UINT32 hash; 382 void *lock; 383 void *value; 384 385 hash = dictHash(dict, id); 386 387 /* find entry in list */ 388 if(! (entry = skipSearch(dict->list, hash, &lock))) 389 return NULL; 390 391 /* lock entry */ 392 DICT_LOCK(dict); 393 394 /* find item */ 395 if((item = dictFindItem(dict, entry, id, FALSE))) { 396 397 value = item->value; 398 399 if(plock) 400 *plock = lock; 401 else 402 dictReleaseLock(dict, lock); 403 404 return value; 405 } 406 407 dictReleaseLock(dict, lock); 408 409 return NULL; 410 } 411 412 void *dictNext (dictCtx dict, char **id, void **plock) 413 { 414 dictEntryPtr entry; 415 dictItemPtr item; 416 UINT32 hash; 417 void *lock; 418 void *value; 419 420 /* Handle the first one special case */ 421 if (*id == NULL) 422 { 423 hash = 0; 424 /* find entry in list */ 425 if(! (entry = skipNext (dict->list, &hash, &lock))) 426 return NULL; 427 428 /* lock entry */ 429 DICT_LOCK(dict); 430 431 /* Take first item in list */ 432 item = entry->first; 433 434 if (item != NULL) 435 { 436 value = item->value; 437 *id = item->id; 438 439 if(plock) 440 *plock = lock; 441 else 442 dictReleaseLock(dict, lock); 443 444 return value; 445 } 446 447 dictReleaseLock(dict, lock); 448 449 return NULL; 450 } 451 else 452 { 453 hash = dictHash(dict, *id); 454 455 /* find entry in list */ 456 entry = skipSearch (dict->list, hash, &lock); 457 458 if (entry == NULL) 459 { 460 entry = skipNext (dict->list, &hash, &lock); 461 /* Not found, we're at the end of the dict */ 462 if (entry == NULL) 463 return NULL; 464 } 465 466 /* lock entry */ 467 DICT_LOCK(dict); 468 469 item = dictFindItem(dict, entry, *id, FALSE); 470 if (item != NULL) 471 { 472 if (item->next != NULL) 473 { 474 item = item->next; 475 } 476 else 477 { 478 /* we have to move to the next skip entry */ 479 entry = skipNext (dict->list, &hash, &lock); 480 /* Not found, we're at the end of the dict */ 481 item = entry?entry->first:NULL; 482 483 if(! item) { 484 dictReleaseLock(dict, lock); 485 return NULL; 486 } 487 488 } 489 value = item->value; 490 *id = item->id; 491 492 if(plock) 493 *plock = lock; 494 else 495 dictReleaseLock(dict, lock); 496 497 return value; 498 } 499 500 dictReleaseLock(dict, lock); 501 } 502 503 return NULL; 504 } 505 506 BOOL dictRemove(dictCtx dict, const char *id) { 507 508 dictEntryPtr entry; 509 dictItemPtr item; 510 UINT32 hash; 511 void *lock; 512 513 hash = dictHash(dict, id); 514 515 /* find entry in list */ 516 if(! (entry = skipSearch(dict->list, hash, &lock))) 517 return FALSE; 518 519 /* lock entry */ 520 DICT_LOCK(dict); 521 522 /* find/unlink/free item */ 523 if((item = dictFindItem(dict, entry, id, TRUE))) 524 dictFreeItem(dict, item); 525 526 dictReleaseLock(dict, lock); 527 528 return item ? TRUE : FALSE; 529 } 530 531 /* called by skipList when safe to destroy entry */ 532 static void dictDestroyEntry(void *value, void *ctx) { 533 534 dictItemPtr item, next; 535 dictEntryPtr entry; 536 537 entry = value; 538 539 for(item = entry->first; item; item = next) { 540 541 next = item->next; 542 dictFreeItem(ctx, item); 543 item = next; 544 } 545 546 free(value); 547 548 return; 549 } 550 551 NEOERR *dictCreate(dictCtx *rdict, BOOL threaded, UINT32 root, UINT32 maxLevel, 552 UINT32 flushLimit, BOOL useCase, dictFreeValueFunc freeValue, void *freeRock) 553 { 554 NEOERR *err; 555 dictCtx dict; 556 557 *rdict = NULL; 558 559 do { 560 561 if(! (dict = calloc(1, sizeof(struct _dictCtx)))) 562 return nerr_raise (NERR_NOMEM, "Unable to allocate memory for dictCtx"); 563 564 dict->useCase = useCase; 565 dict->hash = python_string_hash; 566 if(useCase) { 567 dict->comp = strcmp; 568 } 569 else { 570 /* dict->hash = uhashUpper; */ 571 dict->comp = strcasecmp; 572 } 573 574 dict->threaded = threaded; 575 dict->freeValue = freeValue; 576 dict->freeRock = freeRock; 577 578 err = skipNewList(&(dict->list), threaded, root, maxLevel, 579 flushLimit, dictDestroyEntry, dict); 580 if (err != STATUS_OK) break; 581 582 if (threaded) 583 { 584 err = mCreate(&(dict->mList)); 585 if (err != STATUS_OK) break; 586 } 587 588 *rdict = dict; 589 return STATUS_OK; 590 591 } while(FALSE); 592 593 dictDestroy(dict); 594 595 return nerr_pass(err); 596 } 597 598 void dictDestroy(dictCtx dict) { 599 600 if(! dict) 601 return; 602 603 skipFreeList(dict->list); 604 605 mDestroy(&dict->mList); 606 607 free(dict); 608 609 return; 610 } 611
