Lines Matching full:list
61 /* list constants */
62 int threaded; /* TRUE if list needs to be thread safe */
64 INT32 maxLevel; /* max level list can reach */
70 static void readLock(skipList list) {
72 mLock(&list->read);
74 if(list->block)
75 cWait(&list->resume, &list->read);
77 list->readers++;
79 mUnlock(&list->read);
84 static void readUnlock(skipList list, skipItem x, void **plock) {
88 if(list->threaded)
89 mLock(&list->read);
96 if(! list->threaded)
99 list->readers--;
101 if((list->readers == 0) && list->block)
104 mUnlock(&list->read);
107 cSignal(&list->flush);
112 static void readBlock(skipList list) {
114 mLock(&list->read);
116 list->block = TRUE;
118 if(list->readers)
119 cWait(&list->flush, &list->read); /* wait until reader locks released */
124 static void readUnblock(skipList list) {
126 list->block = FALSE;
128 mUnlock(&list->read);
130 cBroadcast(&list->resume);
136 static void writeLock(skipList list) {
138 mLock(&list->write);
143 static void writeUnlock(skipList list) {
145 mUnlock(&list->write);
166 static void skipFreeItem(skipList list, skipItem item) {
168 if(list->freeValue)
169 list->freeValue(item->value, list->freeValueCtx); /* free value */
176 static void skipFlushDeleted(skipList list, int force) {
180 x = list->deleted;
183 while(y != list->tail) {
190 skipFreeItem(list, y); /* free item */
192 list->cached--; /* update cached count */
204 static void skipWriteUnlock(skipList list) {
208 if(! list->threaded)
211 if((list->cached > list->flushLimit) && (! list->flushing)) {
212 list->flushing = TRUE;
219 writeUnlock(list); /* let any pending writes complete */
220 readUnlock(list, NULL, NULL); /* no longer reading */
225 readBlock(list); /* acquire all read locks */
229 skipFlushDeleted(list, FALSE); /* flush deleted items */
231 list->flushing = FALSE; /* done flushing */
233 readUnblock(list); /* let everyone continue */
239 static skipItem skipFind(skipList list, UINT32 key) {
244 if(list->threaded)
245 readLock(list);
247 x = list->header; /* header contains all levels */
249 for(i = list->levelHint; /* loop from levelHint level down to level 0 */
264 void *skipSearch(skipList list, UINT32 key, void **plock) {
269 y = skipFind(list, key); /* find item */
279 readUnlock(list, y, plock);
284 void *skipNext(skipList list, UINT32 *pkey, void **plock) {
289 y = skipFind(list, *pkey); /* find item */
291 if((y->key == *pkey) && (y != list->tail)) /* skip to next if found y */
294 if(y != list->tail) { /* reset key to next, return value */
303 readUnlock(list, y, plock);
308 void skipRelease(skipList list, void *lock) {
312 mLock(&list->read);
317 mUnlock(&list->read);
322 /* list is write locked */
323 static NEOERR *skipNewItem(skipList list, skipItem *item, UINT32 key,
329 while((drand48() < list->randLimit) && (level < list->maxLevel))
332 if(level > list->topLevel) {
334 if(list->topLevel < list->maxLevel)
335 list->topLevel++;
337 level = list->topLevel;
343 /* list is write locked */
344 static void skipDeleteItem(skipList list, skipItem item) {
346 if(list->threaded) {
347 item->next[item->level + 1] = list->deleted->next[1];
348 list->cached++;
349 list->deleted->next[1] = item;
352 skipFreeItem(list, item);
362 skipList list;
366 if(! (list = calloc(1, sizeof(struct skipList_struct))))
380 list->maxLevel = maxLevel; /* init list constants */
381 list->randLimit = 1.0 / (double)root;
382 list->threaded = threaded;
383 list->freeValue = freeValue;
384 list->freeValueCtx = ctx;
389 list->flushLimit = flushLimit;
391 err = mCreate(&list->read);
394 err = mCreate(&list->write);
397 err = cCreate(&list->resume);
400 err = cCreate(&list->flush);
404 err = skipAllocItem(&(list->header), list->maxLevel, 0, NULL);
406 err = skipAllocItem(&(list->tail), list->maxLevel, (UINT32)-1, NULL);
408 err = skipAllocItem(&(list->deleted), 0, 0, NULL);
412 i <= list->maxLevel;
414 list->tail->next[i] = NULL;
415 list->header->next[i] = list->tail;
418 list->deleted->next[1] = list->tail;
420 *skip = list;
421 return STATUS_OK; /* return new list */
425 if(list->header) /* failed to make list, bail */
426 free(list->header);
427 free(list);
432 /* list considered locked */
433 static void skipFreeAllItems(skipList list) {
438 x = list->header->next[0];
440 while(x != list->tail) {
442 skipFreeItem(list, x); /* release item */
447 i <= list->maxLevel;
449 list->header->next[i] = list->tail;
454 void skipFreeList(skipList list) {
456 skipFlushDeleted(list, TRUE); /* flush deleted items */
458 skipFreeAllItems(list); /* free list items */
460 if(list->threaded) {
461 cDestroy(&list->flush);
462 cDestroy(&list->resume);
463 mDestroy(&list->write);
464 mDestroy(&list->read);
467 free(list->tail); /* free list */
468 free(list->header);
469 free(list->deleted);
470 free(list);
475 /* <list> is locked, <x> is at least level <level>, and <x>->key < <key> */
490 static skipItem skipLock(skipList list, UINT32 key, skipItem *save, INT32 top) {
495 if(list->threaded)
496 readLock(list);
498 x = list->header; /* header contains all levels */
514 if(list->threaded)
515 writeLock(list); /* lock list for update */
521 NEOERR *skipInsert(skipList list, UINT32 key, void *value, int allowUpdate)
533 level = list->levelHint;
535 x = skipLock(list, key, save, level); /* quick search for key */
543 skipWriteUnlock(list);
548 skipWriteUnlock(list);
552 err = skipNewItem(list, &y, key, value);
555 skipWriteUnlock(list);
562 save[i] = list->header;
575 while((list->levelHint < list->topLevel) /* update levelHint */
576 && (list->header->next[list->levelHint+1] != list->tail))
577 list->levelHint++;
579 skipWriteUnlock(list);
584 void skipDelete(skipList list, UINT32 key) {
592 level = list->levelHint;
594 x = skipLock(list, key, save, level); /* quick search for key */
600 skipWriteUnlock(list);
607 save[i] = list->header;
620 skipDeleteItem(list, y); /* put on deleted list */
622 while((list->levelHint > 0) /* update levelHint */
623 && (list->header->next[list->levelHint] == list->tail))
624 list->levelHint--;
626 skipWriteUnlock(list);
