1 /* 2 * 3 * Thread-safe Skiplist Using Integer 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 * 1/14/2001 blong 12 * Made it use neo errs... probably need to check locking functions 13 * for error returns... 14 * 15 */ 16 17 #ifndef __SKIPLIST_H_ 18 #define __SKIPLIST_H_ 19 20 #include "util/neo_err.h" 21 22 __BEGIN_DECLS 23 24 /* 25 * Larger values of <root> means fewer levels and faster lookups, 26 * but more variability in those lookup times (range limited from 2 to 4). 27 * 28 * <maxLevel> should be calculated from expected list size using (^ = power): 29 * 30 * <root> ^ <maxLevel> == expected # of items 31 * 32 * I've capped <maxLevel> at 20, which would be good for a minimum of 33 * 1 million items on lists with <root> == 2. 34 * 35 * 36 * Example 37 * skipNewList(&(my_wdb->ondisk), 0, 4, 2, 0, NULL, NULL); 38 */ 39 #define SKIP_MAXLEVEL 20 40 41 /* SKIP LIST TYPEDEFS */ 42 typedef struct skipList_struct *skipList; 43 typedef void (*skipFreeValue)(void *value, void *ctx); 44 45 NEOERR *skipNewList(skipList *skip, int threaded, int root, int maxLevel, 46 int flushLimit, skipFreeValue freeValue, void *ctx); 47 /* 48 * Function: skipNewList - create a skip list. 49 * Description: Returns a new skip list. If <threaded> is true, list is 50 * multi-thread safe. <root> and <maxLevel> determine 51 * performance and expected size (see discussion above). 52 * <flushLimit> is for threaded lists and determines the 53 * maximum number of deleted items to keep cached during 54 * concurrent searches. Once the limit is reached, new 55 * concurrent reads are blocked until all deleted items are 56 * flushed. 57 * Input: threaded - true if list should be thread-safe. 58 * root - performance parameter (see above). 59 * maxLevel - performance parameter (see above). 60 * flushLimit - max deleted items to keep cached before 61 * forcing a flush. 62 * freeValue - callback made whenever a value is flushed. 63 * ctx - context to pass to <freeValue>. 64 * Output: None. 65 * Return: New skip list, NULL on error. 66 * MT-Level: Safe. 67 */ 68 69 void skipFreeList(skipList list); 70 /* 71 * Function: skipFreeList - free a skip list. 72 * Description: Release all resources used by <list> including all key/value 73 * pairs. 74 * Input: list - list to free. 75 * Output: None. 76 * Return: None. 77 * MT-Level: Safe for unique <list>. 78 */ 79 80 void *skipNext(skipList list, UINT32 *pkey, void **plock); 81 /* 82 * Function: skipNext - find next item. 83 * Description: Searches in list <list> for item with key next larger 84 * that the one in <pkey>, and returns its value if 85 * found, or NULL if not. If <plock> is non-NULL, then 86 * the lock returned in <plock> will be associated with 87 * the returned value. Until this lock is passed to 88 * skipRelease(), the value will not be freed with the 89 * freeValue callback (see skipNewList()). 90 * Input: list - list to search in. 91 * pkey - pointer to previous key (0 to start). 92 * plock - place for value lock (or NULL). 93 * Output: pkey - set to new key. 94 * plock - set to value lock. 95 * Return: Value associated with new <pkey>, or NULL last item. 96 * MT-Level: Safe if <list> thread-safe. 97 */ 98 99 void *skipSearch(skipList list, UINT32 key, void **plock); 100 /* 101 * Function: skipSearch - search a skip list. 102 * Description: Searches for <key> in <list>, and returns value if 103 * found, or NULL if not. If <plock> is non-NULL, then 104 * the lock returned in <plock> will be associated with 105 * the returned value. Until this lock is passed to 106 * skipRelease(), the value will not be freed with the 107 * freeValue callback (see skipNewList()). 108 * Input: list - list to search in. 109 * key - key to look for. 110 * plock - place for value lock (or NULL). 111 * Output: plock - set to value lock. 112 * Return: Value associated with <key>, or NULL if <key> not found. 113 * MT-Level: Safe if <list> thread-safe. 114 */ 115 116 void skipRelease(skipList list, void *lock); 117 /* 118 * Function: skipRelease - release lock on value. 119 * Description: Releases the lock on the value associated with <lock>. Once 120 * the lock is released, the freeValue callback can be called 121 * and the item freed (see skipNewList()). 122 * Input: list - list containing value to release. 123 * lock - lock to release. 124 * Output: None. 125 * Return: None. 126 * MT-Level: Safe if <list> thread-safe. 127 */ 128 129 NEOERR *skipInsert(skipList list, UINT32 key, void *value, int allowUpdate); 130 /* 131 * Function: skipInsert - insert an item. 132 * Description: Inserts the <key>/<value> pair into the <list>. 133 * Key values 0 and -1 are reserved (and illegal). 134 * If key is already in list, and <allowUpdate> is true, 135 * value is updated, otherwise SKIPERR_EXISTS is returned. 136 * Input: list - list to add pair to. 137 * key - key identifying <value>. 138 * value - value to store (may NOT be NULL) 139 * Output: None. 140 * Return: NERR_ASSERT on invalid key or value 141 * NERR_DUPLICATE if allowUpdate is 0 and key exists 142 * NERR_NOMEM 143 * MT-Level: Safe if <list> thread-safe. 144 */ 145 146 void skipDelete(skipList list, UINT32 key); 147 /* 148 * Function: skipDelete - delete an item. 149 * Description: Delete the item associated with <key> from <list>. 150 * Input: list - list to delete item from. 151 * key - key identifying value to delete. 152 * Output: None. 153 * Return: None. 154 * MT-Level: Safe if <list> thread-safe. 155 */ 156 157 __END_DECLS 158 159 #endif /* __SKIPLIST_H_ */ 160 161 162 163 164 165 166