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