1 // (c) 2016 Jeffrey Crowell, Riccardo Schirone(ret2libc)
2 // BSD 3 Clause License
3 // radare2
4
5 // Skiplists are a probabilistic datastructure than can be used as a k-v store
6 // with average case O(lg n) lookup time, and worst case O(n).
7
8 // https://en.wikipedia.org/wiki/Skip_list
9
10 #include <r_skiplist.h>
11
12 #define SKIPLIST_MAX_DEPTH 31
13
r_skiplist_node_new(void * data,int level)14 static RSkipListNode *r_skiplist_node_new(void *data, int level) {
15 RSkipListNode *res = R_NEW0 (RSkipListNode);
16 if (!res) {
17 return NULL;
18 }
19 res->forward = R_NEWS0 (RSkipListNode *, level + 1);
20 if (!res->forward) {
21 free (res);
22 return NULL;
23 }
24 res->data = data;
25 return res;
26 }
27
r_skiplist_node_free(RSkipList * list,RSkipListNode * node)28 static void r_skiplist_node_free(RSkipList *list, RSkipListNode *node) {
29 if (node) {
30 if (list->freefn && node->data) {
31 list->freefn (node->data);
32 }
33 free (node->forward);
34 free (node);
35 }
36 }
37
init_head(RSkipListNode * head)38 static void init_head(RSkipListNode *head) {
39 int i;
40 for (i = 0; i <= SKIPLIST_MAX_DEPTH; i++) {
41 head->forward[i] = head;
42 }
43 }
44
45 // Find the insertion/deletion point for the element `data` in the list.
46 // The array `updates`, if provided, is filled with the nodes that need to be
47 // updated for each layer.
48 //
49 // NOTE: `updates` should be big enough to contain `list->list_level + 1`
50 // elements, when provided.
find_insertpoint(RSkipList * list,void * data,RSkipListNode ** updates,bool by_data)51 static RSkipListNode *find_insertpoint(RSkipList *list, void *data, RSkipListNode **updates, bool by_data) {
52 RSkipListNode *x = list->head;
53 int i;
54
55 for (i = list->list_level; i >= 0; i--) {
56 if (by_data) {
57 while (x->forward[i] != list->head
58 && list->compare (x->forward[i]->data, data) < 0) {
59 x = x->forward[i];
60 }
61 } else {
62 while (x->forward[i] != list->head && x->forward[i] != data) {
63 x = x->forward[i];
64 }
65 }
66 if (updates) {
67 updates[i] = x;
68 }
69 }
70 x = x->forward[0];
71 return x;
72 }
73
delete_element(RSkipList * list,void * data,bool by_data)74 static bool delete_element(RSkipList* list, void* data, bool by_data) {
75 int i;
76 RSkipListNode *update[SKIPLIST_MAX_DEPTH + 1], *x;
77
78 // locate delete points in the lists of all levels
79 x = find_insertpoint (list, data, update, by_data);
80 // do nothing if the element is not present in the list
81 if (x == list->head || list->compare(x->data, data) != 0) {
82 return false;
83 }
84
85 // update forward links for all `update` points,
86 // by removing the element from the list in each level
87 for (i = 0; i <= list->list_level; i++) {
88 if (update[i]->forward[i] != x) {
89 break;
90 }
91 update[i]->forward[i] = x->forward[i];
92 }
93 r_skiplist_node_free (list, x);
94
95 // update the level of the list
96 while ((list->list_level > 0) &&
97 (list->head->forward[list->list_level] == list->head)) {
98 list->list_level--;
99 }
100 list->size--;
101 return true;
102 }
103
104 // Takes in a pointer to the function to free a list element, and a pointer to
105 // a function that returns 0 on equality between two elements, and -1 or 1
106 // when unequal (for sorting).
107 // Returns a new heap-allocated skiplist.
r_skiplist_new(RListFree freefn,RListComparator comparefn)108 R_API RSkipList* r_skiplist_new(RListFree freefn, RListComparator comparefn) {
109 RSkipList *list = R_NEW0 (RSkipList);
110 if (!list) {
111 return NULL;
112 }
113
114 list->head = r_skiplist_node_new (NULL, SKIPLIST_MAX_DEPTH);
115 if (!list->head) {
116 free (list);
117 return NULL;
118 }
119
120 init_head (list->head);
121 list->list_level = 0;
122 list->size = 0;
123 list->freefn = freefn;
124 list->compare = comparefn;
125 return list;
126 }
127
128 // Remove all elements from the list
r_skiplist_purge(RSkipList * list)129 R_API void r_skiplist_purge(RSkipList *list) {
130 RSkipListNode *n;
131 if (!list) {
132 return;
133 }
134 n = list->head->forward[0];
135 while (n != list->head) {
136 RSkipListNode *x = n;
137 n = n->forward[0];
138 r_skiplist_node_free (list, x);
139 }
140 init_head (list->head);
141 list->size = 0;
142 list->list_level = 0;
143 }
144
145 // Free the entire list and it's element (if freefn is specified)
r_skiplist_free(RSkipList * list)146 R_API void r_skiplist_free(RSkipList *list) {
147 if (!list) {
148 return;
149 }
150 r_skiplist_purge (list);
151 r_skiplist_node_free (list, list->head);
152 free (list);
153 }
154
155 // Inserts an element to the skiplist, and returns a pointer to the element's
156 // node.
r_skiplist_insert(RSkipList * list,void * data)157 R_API RSkipListNode* r_skiplist_insert(RSkipList* list, void* data) {
158 RSkipListNode *update[SKIPLIST_MAX_DEPTH + 1];
159 RSkipListNode *x;
160 int i, x_level, new_level;
161
162 // locate insertion points in the lists of all levels
163 x = find_insertpoint (list, data, update, true);
164 // check whether the element is already in the list
165 if (x != list->head && !list->compare(x->data, data)) {
166 return x;
167 }
168
169 // randomly choose the number of levels the new node will be put in
170 for (x_level = 0; rand () < RAND_MAX / 2 && x_level < SKIPLIST_MAX_DEPTH; x_level++) {
171 ;
172 }
173
174 // update the `update` array with default values when the current node
175 // has a level greater than the current one
176 new_level = list->list_level;
177 if (x_level > list->list_level) {
178 for (i = list->list_level + 1; i <= x_level; i++) {
179 update[i] = list->head;
180 }
181 new_level = x_level;
182 }
183
184 x = r_skiplist_node_new (data, x_level);
185 if (!x) {
186 return NULL;
187 }
188
189 // update forward links for all `update` points,
190 // by inserting the new element in the list in each level
191 for (i = 0; i <= x_level; i++) {
192 x->forward[i] = update[i]->forward[i];
193 update[i]->forward[i] = x;
194 }
195
196 list->list_level = new_level;
197 list->size++;
198 return x;
199 }
200
r_skiplist_insert_autofree(RSkipList * list,void * data)201 R_API bool r_skiplist_insert_autofree(RSkipList* list, void* data) {
202 RSkipListNode* node = r_skiplist_insert (list, data);
203 if (node && data != node->data) { // duplicate
204 if (list->freefn) {
205 list->freefn (data);
206 }
207 return false;
208 }
209 return true;
210 }
211
212 // Delete node with data as it's payload.
r_skiplist_delete(RSkipList * list,void * data)213 R_API bool r_skiplist_delete(RSkipList* list, void* data) {
214 return delete_element (list, data, true);
215 }
216
217 // Delete the given RSkipListNode from the skiplist
r_skiplist_delete_node(RSkipList * list,RSkipListNode * node)218 R_API bool r_skiplist_delete_node(RSkipList *list, RSkipListNode *node) {
219 return delete_element (list, node, false);
220 }
221
r_skiplist_find(RSkipList * list,void * data)222 R_API RSkipListNode* r_skiplist_find(RSkipList* list, void* data) {
223 RSkipListNode* x = find_insertpoint (list, data, NULL, true);
224 if (x != list->head && list->compare (x->data, data) == 0) {
225 return x;
226 }
227 return NULL;
228 }
229
r_skiplist_find_geq(RSkipList * list,void * data)230 R_API RSkipListNode* r_skiplist_find_geq(RSkipList* list, void* data) {
231 RSkipListNode* x = find_insertpoint (list, data, NULL, true);
232 return x != list->head ? x : NULL;
233 }
234
r_skiplist_find_leq(RSkipList * list,void * data)235 R_API RSkipListNode* r_skiplist_find_leq(RSkipList* list, void* data) {
236 RSkipListNode *x = list->head;
237 int i;
238
239 for (i = list->list_level; i >= 0; i--) {
240 while (x->forward[i] != list->head
241 && list->compare (x->forward[i]->data, data) <= 0) {
242 x = x->forward[i];
243 }
244 }
245 return x != list->head ? x : NULL;
246 }
247
248 // Move all the elements of `l2` in `l1`.
r_skiplist_join(RSkipList * l1,RSkipList * l2)249 R_API void r_skiplist_join(RSkipList *l1, RSkipList *l2) {
250 RSkipListNode *it;
251 void *data;
252
253 r_skiplist_foreach (l2, it, data) {
254 r_skiplist_insert (l1, data);
255 }
256
257 r_skiplist_purge (l2);
258 }
259
260 // Returns the first data element in the list, if present, NULL otherwise
r_skiplist_get_first(RSkipList * list)261 R_API void *r_skiplist_get_first(RSkipList *list) {
262 if (!list) {
263 return NULL;
264 }
265 RSkipListNode *res = list->head->forward[0];
266 return res == list->head ? NULL : res->data;
267 }
268
269 // Returns the nth data element in the list, if present, NULL otherwise
r_skiplist_get_n(RSkipList * list,int n)270 R_API void *r_skiplist_get_n(RSkipList *list, int n) {
271 int count = 0;
272 RSkipListNode *node;
273 void *data;
274 if (!list || n < 0) {
275 return NULL;
276 }
277 r_skiplist_foreach (list, node, data) {
278 if (count == n) {
279 return data;
280 }
281 ++count;
282 }
283 return NULL;
284 }
285
286
r_skiplist_get_geq(RSkipList * list,void * data)287 R_API void* r_skiplist_get_geq(RSkipList* list, void* data) {
288 RSkipListNode *x = r_skiplist_find_geq (list, data);
289 return x ? x->data : NULL;
290 }
291
r_skiplist_get_leq(RSkipList * list,void * data)292 R_API void* r_skiplist_get_leq(RSkipList* list, void* data) {
293 RSkipListNode *x = r_skiplist_find_leq (list, data);
294 return x ? x->data : NULL;
295 }
296
297 // Return true if the list is empty
r_skiplist_empty(RSkipList * list)298 R_API bool r_skiplist_empty(RSkipList *list) {
299 return list->size == 0;
300 }
301
302 // Return a new allocated RList representing the given `list`
303 //
304 // NOTE: the data will be shared between the two lists. The user of this
305 // function should choose which list will "own" the data pointers.
r_skiplist_to_list(RSkipList * list)306 R_API RList *r_skiplist_to_list(RSkipList *list) {
307 RList *res = r_list_new ();
308 RSkipListNode *n;
309 void *data;
310
311 r_skiplist_foreach (list, n, data) {
312 r_list_append (res, data);
313 }
314
315 return res;
316 }
317