1 /*
2 *
3 * Thread-safe Dictionary Using String Identifiers
4 * Copyright 1998-2000 Scott Shambarger (scott@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 */
dictNewItem(dictCtx dict,dictEntryPtr entry,const char * id,dictValuePtr newval,dictItemPtr * item)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
dictFreeItem(dictCtx dict,dictItemPtr item)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 */
dictFindItem(dictCtx dict,dictEntryPtr entry,const char * id,BOOL unlink)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
dictUpdate(dictCtx dict,dictEntryPtr entry,const char * id,dictValuePtr newval,void * lock)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
dictInsert(dictCtx dict,UINT32 hash,const char * id,dictValuePtr newval)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
dictHash(dictCtx dict,const char * id)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
dictModify(dictCtx dict,const char * id,dictValuePtr newval)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
dictSetValue(dictCtx dict,const char * id,void * value)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
dictModifyValue(dictCtx dict,const char * id,dictNewValueCB new,dictUpdateValueCB update,void * rock)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
dictReleaseLock(dictCtx dict,void * lock)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
dictCleanup(dictCtx dict,dictCleanupFunc cleanup,void * rock)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
dictSearch(dictCtx dict,const char * id,void ** plock)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
dictNext(dictCtx dict,char ** id,void ** plock)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
dictRemove(dictCtx dict,const char * id)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 */
dictDestroyEntry(void * value,void * ctx)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
dictCreate(dictCtx * rdict,BOOL threaded,UINT32 root,UINT32 maxLevel,UINT32 flushLimit,BOOL useCase,dictFreeValueFunc freeValue,void * freeRock)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
dictDestroy(dictCtx dict)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