1 /**
2 * Copyright (C) 2015 Happy Fish / YuQing
3 *
4 * libfastcommon may be copied only under the terms of the GNU General
5 * Public License V3, which may be found in the FastDFS source kit.
6 * Please visit the FastDFS Home Page http://www.fastken.com/ for more detail.
7 **/
8
9 //flat_skiplist.c
10
11 #include <ctype.h>
12 #include <stdlib.h>
13 #include <stdio.h>
14 #include <string.h>
15 #include <errno.h>
16 #include <assert.h>
17 #include "logger.h"
18 #include "flat_skiplist.h"
19
flat_skiplist_init_ex(FlatSkiplist * sl,const int level_count,skiplist_compare_func compare_func,skiplist_free_func free_func,const int min_alloc_elements_once)20 int flat_skiplist_init_ex(FlatSkiplist *sl, const int level_count,
21 skiplist_compare_func compare_func, skiplist_free_func free_func,
22 const int min_alloc_elements_once)
23 {
24 int bytes;
25 int element_size;
26 int i;
27 int alloc_elements_once;
28 int result;
29 struct fast_mblock_man *top_mblock;
30
31 if (level_count <= 0) {
32 logError("file: "__FILE__", line: %d, "
33 "invalid level count: %d",
34 __LINE__, level_count);
35 return EINVAL;
36 }
37
38 if (level_count > 30) {
39 logError("file: "__FILE__", line: %d, "
40 "level count: %d is too large",
41 __LINE__, level_count);
42 return E2BIG;
43 }
44
45 bytes = sizeof(FlatSkiplistNode *) * level_count;
46 sl->tmp_previous = (FlatSkiplistNode **)malloc(bytes);
47 if (sl->tmp_previous == NULL) {
48 logError("file: "__FILE__", line: %d, "
49 "malloc %d bytes fail, errno: %d, error info: %s",
50 __LINE__, bytes, errno, STRERROR(errno));
51 return errno != 0 ? errno : ENOMEM;
52 }
53
54 bytes = sizeof(struct fast_mblock_man) * level_count;
55 sl->mblocks = (struct fast_mblock_man *)malloc(bytes);
56 if (sl->mblocks == NULL) {
57 logError("file: "__FILE__", line: %d, "
58 "malloc %d bytes fail, errno: %d, error info: %s",
59 __LINE__, bytes, errno, STRERROR(errno));
60 return errno != 0 ? errno : ENOMEM;
61 }
62 memset(sl->mblocks, 0, bytes);
63
64 alloc_elements_once = min_alloc_elements_once;
65 if (alloc_elements_once <= 0) {
66 alloc_elements_once = SKIPLIST_DEFAULT_MIN_ALLOC_ELEMENTS_ONCE;
67 }
68 else if (alloc_elements_once > 1024) {
69 alloc_elements_once = 1024;
70 }
71
72 for (i=level_count-1; i>=0; i--) {
73 element_size = sizeof(FlatSkiplistNode) + sizeof(FlatSkiplistNode *) * (i + 1);
74 if ((result=fast_mblock_init_ex(sl->mblocks + i,
75 element_size, alloc_elements_once, NULL, false)) != 0)
76 {
77 return result;
78 }
79 if (i % 2 == 0 && alloc_elements_once < 64 * 1024) {
80 alloc_elements_once *= 2;
81 }
82 }
83
84 sl->top_level_index = level_count - 1;
85 top_mblock = sl->mblocks + sl->top_level_index;
86 sl->top = (FlatSkiplistNode *)fast_mblock_alloc_object(top_mblock);
87 if (sl->top == NULL) {
88 return ENOMEM;
89 }
90 memset(sl->top, 0, top_mblock->info.element_size);
91
92 sl->tail = (FlatSkiplistNode *)fast_mblock_alloc_object(sl->mblocks + 0);
93 if (sl->tail == NULL) {
94 return ENOMEM;
95 }
96 memset(sl->tail, 0, sl->mblocks[0].info.element_size);
97
98 sl->tail->prev = sl->top;
99 for (i=0; i<level_count; i++) {
100 sl->top->links[i] = sl->tail;
101 }
102
103 sl->level_count = level_count;
104 sl->compare_func = compare_func;
105 sl->free_func = free_func;
106
107 srand(time(NULL));
108 return 0;
109 }
110
flat_skiplist_destroy(FlatSkiplist * sl)111 void flat_skiplist_destroy(FlatSkiplist *sl)
112 {
113 int i;
114 FlatSkiplistNode *node;
115 FlatSkiplistNode *deleted;
116
117 if (sl->mblocks == NULL) {
118 return;
119 }
120
121 if (sl->free_func != NULL) {
122 node = sl->top->links[0];
123 while (node != sl->tail) {
124 deleted = node;
125 node = node->links[0];
126 sl->free_func(deleted->data);
127 }
128 }
129
130 for (i=0; i<sl->level_count; i++) {
131 fast_mblock_destroy(sl->mblocks + i);
132 }
133
134 free(sl->mblocks);
135 sl->mblocks = NULL;
136 }
137
flat_skiplist_get_level_index(FlatSkiplist * sl)138 static inline int flat_skiplist_get_level_index(FlatSkiplist *sl)
139 {
140 int i;
141
142 for (i=0; i<sl->top_level_index; i++) {
143 if (rand() < RAND_MAX / 2) {
144 break;
145 }
146 }
147
148 return i;
149 }
150
flat_skiplist_insert(FlatSkiplist * sl,void * data)151 int flat_skiplist_insert(FlatSkiplist *sl, void *data)
152 {
153 int i;
154 int level_index;
155 FlatSkiplistNode *node;
156 FlatSkiplistNode *previous;
157
158 level_index = flat_skiplist_get_level_index(sl);
159 node = (FlatSkiplistNode *)fast_mblock_alloc_object(sl->mblocks + level_index);
160 if (node == NULL) {
161 return ENOMEM;
162 }
163 node->data = data;
164
165 previous = sl->top;
166 for (i=sl->top_level_index; i>level_index; i--) {
167 while (previous->links[i] != sl->tail && sl->compare_func(data,
168 previous->links[i]->data) < 0)
169 {
170 previous = previous->links[i];
171 }
172 }
173
174 while (i >= 0) {
175 while (previous->links[i] != sl->tail && sl->compare_func(data,
176 previous->links[i]->data) < 0)
177 {
178 previous = previous->links[i];
179 }
180
181 sl->tmp_previous[i] = previous;
182 i--;
183 }
184
185 //set previous links of level 0
186 node->prev = previous;
187 previous->links[0]->prev = node;
188
189 //thread safe for one write with many read model
190 for (i=0; i<=level_index; i++) {
191 node->links[i] = sl->tmp_previous[i]->links[i];
192 sl->tmp_previous[i]->links[i] = node;
193 }
194
195 return 0;
196 }
197
flat_skiplist_get_previous(FlatSkiplist * sl,void * data,int * level_index)198 static FlatSkiplistNode *flat_skiplist_get_previous(FlatSkiplist *sl, void *data,
199 int *level_index)
200 {
201 int i;
202 int cmp;
203 FlatSkiplistNode *previous;
204
205 previous = sl->top;
206 for (i=sl->top_level_index; i>=0; i--) {
207 while (previous->links[i] != sl->tail) {
208 cmp = sl->compare_func(data, previous->links[i]->data);
209 if (cmp > 0) {
210 break;
211 }
212 else if (cmp == 0) {
213 *level_index = i;
214 return previous;
215 }
216
217 previous = previous->links[i];
218 }
219 }
220
221 return NULL;
222 }
223
flat_skiplist_get_first_larger_or_equal(FlatSkiplist * sl,void * data)224 static FlatSkiplistNode *flat_skiplist_get_first_larger_or_equal(
225 FlatSkiplist *sl, void *data)
226 {
227 int i;
228 int cmp;
229 FlatSkiplistNode *previous;
230 FlatSkiplistNode *current;
231
232 previous = sl->top;
233 for (i=sl->top_level_index; i>=0; i--) {
234 while (previous->links[i] != sl->tail) {
235 cmp = sl->compare_func(data, previous->links[i]->data);
236 if (cmp > 0) {
237 break;
238 }
239 else if (cmp == 0) {
240 current = previous->links[i]->links[0];
241 while ((current != sl->tail) && (sl->compare_func(
242 data, current->data) == 0))
243 {
244 current = current->links[0];
245 }
246 return current->prev;
247 }
248
249 previous = previous->links[i];
250 }
251 }
252
253 return previous;
254 }
255
flat_skiplist_get_first_larger(FlatSkiplist * sl,void * data)256 static FlatSkiplistNode *flat_skiplist_get_first_larger(
257 FlatSkiplist *sl, void *data)
258 {
259 int i;
260 int cmp;
261 FlatSkiplistNode *previous;
262
263 previous = sl->top;
264 for (i=sl->top_level_index; i>=0; i--) {
265 while (previous->links[i] != sl->tail) {
266 cmp = sl->compare_func(data, previous->links[i]->data);
267 if (cmp > 0) {
268 break;
269 }
270 else if (cmp == 0) {
271 previous = previous->links[i]->prev;
272 while ((previous != sl->top) && (sl->compare_func(
273 data, previous->data) == 0))
274 {
275 previous = previous->prev;
276 }
277
278 return previous;
279 }
280
281 previous = previous->links[i];
282 }
283 }
284
285 return previous;
286 }
287
flat_skiplist_delete(FlatSkiplist * sl,void * data)288 int flat_skiplist_delete(FlatSkiplist *sl, void *data)
289 {
290 int i;
291 int level_index;
292 FlatSkiplistNode *previous;
293 FlatSkiplistNode *deleted;
294
295 previous = flat_skiplist_get_previous(sl, data, &level_index);
296 if (previous == NULL) {
297 return ENOENT;
298 }
299
300 deleted = previous->links[level_index];
301 for (i=level_index; i>=0; i--) {
302 while (previous->links[i] != sl->tail && previous->links[i] != deleted) {
303 previous = previous->links[i];
304 }
305
306 assert(previous->links[i] == deleted);
307 previous->links[i] = previous->links[i]->links[i];
308 }
309
310 deleted->links[0]->prev = previous;
311
312 if (sl->free_func != NULL) {
313 sl->free_func(deleted->data);
314 }
315 fast_mblock_free_object(sl->mblocks + level_index, deleted);
316 return 0;
317 }
318
flat_skiplist_delete_all(FlatSkiplist * sl,void * data,int * delete_count)319 int flat_skiplist_delete_all(FlatSkiplist *sl, void *data, int *delete_count)
320 {
321 *delete_count = 0;
322 while (flat_skiplist_delete(sl, data) == 0) {
323 (*delete_count)++;
324 }
325
326 return *delete_count > 0 ? 0 : ENOENT;
327 }
328
flat_skiplist_find(FlatSkiplist * sl,void * data)329 void *flat_skiplist_find(FlatSkiplist *sl, void *data)
330 {
331 int level_index;
332 FlatSkiplistNode *previous;
333
334 previous = flat_skiplist_get_previous(sl, data, &level_index);
335 return (previous != NULL) ? previous->links[level_index]->data : NULL;
336 }
337
flat_skiplist_find_all(FlatSkiplist * sl,void * data,FlatSkiplistIterator * iterator)338 int flat_skiplist_find_all(FlatSkiplist *sl, void *data, FlatSkiplistIterator *iterator)
339 {
340 int level_index;
341 FlatSkiplistNode *previous;
342 FlatSkiplistNode *last;
343
344 previous = flat_skiplist_get_previous(sl, data, &level_index);
345 if (previous == NULL) {
346 iterator->top = sl->top;
347 iterator->current = sl->top;
348 return ENOENT;
349 }
350
351 previous = previous->links[level_index];
352 last = previous->links[0];
353 while (last != sl->tail && sl->compare_func(data, last->data) == 0) {
354 last = last->links[0];
355 }
356
357 do {
358 previous = previous->prev;
359 } while (previous != sl->top && sl->compare_func(data, previous->data) == 0);
360
361 iterator->top = previous;
362 iterator->current = last->prev;
363 return 0;
364 }
365
flat_skiplist_find_range(FlatSkiplist * sl,void * start_data,void * end_data,FlatSkiplistIterator * iterator)366 int flat_skiplist_find_range(FlatSkiplist *sl, void *start_data, void *end_data,
367 FlatSkiplistIterator *iterator)
368 {
369 if (sl->compare_func(start_data, end_data) > 0) {
370 iterator->current = sl->top;
371 iterator->top = sl->top;
372 return EINVAL;
373 }
374
375 iterator->current = flat_skiplist_get_first_larger_or_equal(sl, start_data);
376 if (iterator->current == sl->top) {
377 iterator->top = sl->top;
378 return ENOENT;
379 }
380
381 iterator->top = flat_skiplist_get_first_larger(sl, end_data);
382 return iterator->current != iterator->top ? 0 : ENOENT;
383 }
384