1 /************************************************************************
2 *
3 * SKIPLIST.C - Skiplist functions for use in Nagios event/object lists
4 *
5 *
6 * Notes:
7 *
8 * These function implement a slightly modified skiplist from that
9 * described by William Pugh (ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf).
10 * The structures and function were modified to allow the list to act
11 * like a priority queue for the Nagios event list/queue(s). Multiple nodes with
12 * the same key value are allowed on the list to accommodate multiple events
13 * occurring at the same (second) point in time. Implemented peek() and pop()
14 * functions to allow for quick event queue processing, and a method to delete
15 * a specific list item, based on its pointer, rather than its data value. Again,
16 * this is useful for the Nagios event queue.
17 *
18 * License:
19 *
20 * This program is free software; you can redistribute it and/or modify
21 * it under the terms of the GNU General Public License version 2 as
22 * published by the Free Software Foundation.
23 *
24 * This program is distributed in the hope that it will be useful,
25 * but WITHOUT ANY WARRANTY; without even the implied warranty of
26 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
27 * GNU General Public License for more details.
28 *
29 * You should have received a copy of the GNU General Public License
30 * along with this program; if not, write to the Free Software
31 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
32 ************************************************************************/
33
34 #include <unistd.h>
35 #include <stdlib.h>
36 #include "skiplist.h"
37
38
39 typedef struct skiplistnode_struct {
40 void *data;
41 struct skiplistnode_struct *forward[1]; /* this must be the last element of the struct, as we allocate # of elements during runtime*/
42 } skiplistnode;
43
44 struct skiplist_struct {
45 int current_level;
46 int max_levels;
47 float level_probability;
48 unsigned long items;
49 int allow_duplicates;
50 int append_duplicates;
51 int (*compare_function)(void *, void *);
52 skiplistnode *head;
53 };
54
skiplist_num_items(skiplist * list)55 unsigned long skiplist_num_items(skiplist *list) {
56 return list ? list->items : 0;
57 }
58
skiplist_new_node(skiplist * list,int node_levels)59 static skiplistnode *skiplist_new_node(skiplist *list, int node_levels) {
60 skiplistnode *newnode = NULL;
61 register int x = 0;
62
63 if(list == NULL)
64 return NULL;
65
66 if(node_levels < 0 || node_levels > list->max_levels)
67 return NULL;
68
69 /* allocate memory for node + variable number of level pointers */
70 if((newnode = (skiplistnode *)malloc(sizeof(skiplistnode) + (node_levels * sizeof(skiplistnode *))))) {
71
72 /* initialize forward pointers */
73 for(x = 0; x < node_levels; x++)
74 newnode->forward[x] = NULL;
75
76 /* initialize data pointer */
77 newnode->data = NULL;
78 }
79
80 return newnode;
81 }
82
83
skiplist_new(int max_levels,float level_probability,int allow_duplicates,int append_duplicates,int (* compare_function)(void *,void *))84 skiplist *skiplist_new(int max_levels, float level_probability, int allow_duplicates, int append_duplicates, int (*compare_function)(void *, void *)) {
85 skiplist *newlist = NULL;
86
87 /* alloc memory for new list structure */
88 if((newlist = (skiplist *)malloc(sizeof(skiplist)))) {
89
90 /* initialize levels, etc. */
91 newlist->current_level = 0;
92 newlist->max_levels = max_levels;
93 newlist->level_probability = level_probability;
94 newlist->allow_duplicates = allow_duplicates;
95 newlist->append_duplicates = append_duplicates;
96 newlist->items = 0;
97 newlist->compare_function = compare_function;
98
99 /* initialize head node */
100 newlist->head = skiplist_new_node(newlist, max_levels);
101 }
102
103 return newlist;
104 }
105
106
skiplist_random_level(skiplist * list)107 static int skiplist_random_level(skiplist *list) {
108 int level = 0;
109 float r = 0.0;
110
111 if(list == NULL)
112 return -1;
113
114 for(level = 0; level < list->max_levels; level++) {
115 r = ((float)rand() / (float)RAND_MAX);
116 if(r > list->level_probability)
117 break;
118 }
119
120 return (level >= list->max_levels) ? list->max_levels - 1 : level;
121 }
122
123
skiplist_insert(skiplist * list,void * data)124 int skiplist_insert(skiplist *list, void *data) {
125 skiplistnode **update = NULL;
126 skiplistnode *thisnode = NULL;
127 skiplistnode *nextnode = NULL;
128 skiplistnode *newnode = NULL;
129 int level = 0;
130 int x = 0;
131
132 if(list == NULL || data == NULL) {
133 return SKIPLIST_ERROR_ARGS;
134 }
135
136 /* check to make sure we don't have duplicates */
137 /* NOTE: this could made be more efficient */
138 if(list->allow_duplicates == FALSE) {
139 if(skiplist_find_first(list, data, NULL))
140 return SKIPLIST_ERROR_DUPLICATE;
141 }
142
143 /* initialize update vector */
144 if((update = (skiplistnode **)malloc(sizeof(skiplistnode *) * list->max_levels)) == NULL) {
145 return SKIPLIST_ERROR_MEMORY;
146 }
147 for(x = 0; x < list->max_levels; x++)
148 update[x] = NULL;
149
150 /* find proper position for insert, remember pointers with an update vector */
151 thisnode = list->head;
152 for(level = list->current_level; level >= 0; level--) {
153
154 while((nextnode = thisnode->forward[level])) {
155 if(list->append_duplicates == TRUE) {
156 if(list->compare_function(nextnode->data, data) > 0)
157 break;
158 }
159 else {
160 if(list->compare_function(nextnode->data, data) >= 0)
161 break;
162 }
163 thisnode = nextnode;
164 }
165
166 update[level] = thisnode;
167 }
168
169 /* get a random level the new node should be inserted at */
170 level = skiplist_random_level(list);
171
172 /* we're adding a new level... */
173 if(level > list->current_level) {
174 /*printf("NEW LEVEL!\n");*/
175 list->current_level++;
176 level = list->current_level;
177 update[level] = list->head;
178 }
179
180 /* create a new node */
181 if((newnode = skiplist_new_node(list, level)) == NULL) {
182 /*printf("NODE ERROR\n");*/
183 free(update);
184 return SKIPLIST_ERROR_MEMORY;
185 }
186 newnode->data = data;
187
188 /* update pointers to insert node at proper location */
189 do {
190 thisnode = update[level];
191 newnode->forward[level] = thisnode->forward[level];
192 thisnode->forward[level] = newnode;
193
194 }
195 while(--level >= 0);
196
197 /* update counters */
198 list->items++;
199
200 /* free memory */
201 free(update);
202
203 return SKIPLIST_OK;
204 }
205
206
207
skiplist_empty(skiplist * list)208 int skiplist_empty(skiplist *list) {
209 skiplistnode *this = NULL;
210 skiplistnode *next = NULL;
211 int level = 0;
212
213 if(list == NULL)
214 return ERROR;
215
216 /* free all list nodes (but not header) */
217 for(this = list->head->forward[0]; this != NULL; this = next) {
218 next = this->forward[0];
219 free(this);
220 }
221
222 /* reset level pointers */
223 for(level = list->current_level; level >= 0; level--)
224 list->head->forward[level] = NULL;
225
226 /* reset list level */
227 list->current_level = 0;
228
229 /* reset items */
230 list->items = 0;
231
232 return OK;
233 }
234
235
236
skiplist_free(skiplist ** list)237 int skiplist_free(skiplist **list) {
238 skiplistnode *this = NULL;
239 skiplistnode *next = NULL;
240
241 if(list == NULL)
242 return ERROR;
243 if(*list == NULL)
244 return OK;
245
246 /* free header and all list nodes */
247 for(this = (*list)->head; this != NULL; this = next) {
248 next = this->forward[0];
249 free(this);
250 }
251
252 /* free list structure */
253 free(*list);
254 *list = NULL;
255
256 return OK;
257 }
258
259
260
261 /* get first item in list */
skiplist_peek(skiplist * list)262 void *skiplist_peek(skiplist *list) {
263
264 if(list == NULL)
265 return NULL;
266
267 /* return first item */
268 return list->head->forward[0]->data;
269 }
270
271
272
273 /* get/remove first item in list */
skiplist_pop(skiplist * list)274 void *skiplist_pop(skiplist *list) {
275 skiplistnode *thisnode = NULL;
276 void *data = NULL;
277 int level = 0;
278
279 if(list == NULL)
280 return NULL;
281
282 /* get first item */
283 thisnode = list->head->forward[0];
284 if(thisnode == NULL)
285 return NULL;
286
287 /* get data for first item */
288 data = thisnode->data;
289
290 /* remove first item from queue - update forward links from head to first node */
291 for(level = 0; level <= list->current_level; level++) {
292 if(list->head->forward[level] == thisnode)
293 list->head->forward[level] = thisnode->forward[level];
294 }
295
296 /* free deleted node */
297 free(thisnode);
298
299 /* adjust items */
300 list->items--;
301
302 return data;
303 }
304
305
306
307 /* get first item in list */
skiplist_get_first(skiplist * list,void ** node_ptr)308 void *skiplist_get_first(skiplist *list, void **node_ptr) {
309 skiplistnode *thisnode = NULL;
310
311 if(list == NULL)
312 return NULL;
313
314 /* get first node */
315 thisnode = list->head->forward[0];
316
317 /* return pointer to node */
318 if(node_ptr)
319 *node_ptr = (void *)thisnode;
320
321 if(thisnode)
322 return thisnode->data;
323 else
324 return NULL;
325 }
326
327
328
329 /* get next item in list */
skiplist_get_next(void ** node_ptr)330 void *skiplist_get_next(void **node_ptr) {
331 skiplistnode *thisnode = NULL;
332 skiplistnode *nextnode = NULL;
333
334 if(node_ptr == NULL || *node_ptr == NULL)
335 return NULL;
336
337 thisnode = (skiplistnode *)(*node_ptr);
338 nextnode = thisnode->forward[0];
339
340 *node_ptr = (void *)nextnode;
341
342 if(nextnode)
343 return nextnode->data;
344 else
345 return NULL;
346 }
347
348
349
350 /* first first item in list */
skiplist_find_first(skiplist * list,void * data,void ** node_ptr)351 void *skiplist_find_first(skiplist *list, void *data, void **node_ptr) {
352 skiplistnode *thisnode = NULL;
353 skiplistnode *nextnode = NULL;
354 int level = 0;
355
356 if(list == NULL || data == NULL)
357 return NULL;
358
359 thisnode = list->head;
360 for(level = list->current_level; level >= 0; level--) {
361 while((nextnode = thisnode->forward[level])) {
362 if(list->compare_function(nextnode->data, data) >= 0)
363 break;
364 thisnode = nextnode;
365 }
366 }
367
368 /* we found it! */
369 if(nextnode && list->compare_function(nextnode->data, data) == 0) {
370 if(node_ptr)
371 *node_ptr = (void *)nextnode;
372 return nextnode->data;
373 }
374 else {
375 if(node_ptr)
376 *node_ptr = NULL;
377 }
378
379 return NULL;
380 }
381
382
383
384 /* find next match */
skiplist_find_next(skiplist * list,void * data,void ** node_ptr)385 void *skiplist_find_next(skiplist *list, void *data, void **node_ptr) {
386 skiplistnode *thisnode = NULL;
387 skiplistnode *nextnode = NULL;
388
389 if(list == NULL || data == NULL || node_ptr == NULL)
390 return NULL;
391 if(*node_ptr == NULL)
392 return NULL;
393
394 thisnode = (skiplistnode *)(*node_ptr);
395 nextnode = thisnode->forward[0];
396
397 if(nextnode) {
398 if(list->compare_function(nextnode->data, data) == 0) {
399 *node_ptr = (void *)nextnode;
400 return nextnode->data;
401 }
402 }
403
404 *node_ptr = NULL;
405 return NULL;
406 }
407
408
409
410 /* delete first matching item from list */
skiplist_delete_first(skiplist * list,void * data)411 int skiplist_delete_first(skiplist *list, void *data) {
412 skiplistnode **update = NULL;
413 skiplistnode *thisnode = NULL;
414 skiplistnode *nextnode = NULL;
415 int level = 0;
416 int top_level = 0;
417 int deleted = FALSE;
418 int x = 0;
419
420 if(list == NULL || data == NULL)
421 return ERROR;
422
423 /* initialize update vector */
424 if((update = (skiplistnode **)malloc(sizeof(skiplistnode *) * list->max_levels)) == NULL)
425 return ERROR;
426 for(x = 0; x < list->max_levels; x++)
427 update[x] = NULL;
428
429 /* find location in list */
430 thisnode = list->head;
431 for(top_level = level = list->current_level; level >= 0; level--) {
432 while((nextnode = thisnode->forward[level])) {
433 if(list->compare_function(nextnode->data, data) >= 0)
434 break;
435 thisnode = nextnode;
436 }
437 update[level] = thisnode;
438 }
439
440 /* we found a match! */
441 if(list->compare_function(nextnode->data, data) == 0) {
442
443 /* adjust level pointers to bypass (soon to be) removed node */
444 for(level = 0; level <= top_level; level++) {
445
446 thisnode = update[level];
447 if(thisnode->forward[level] != nextnode)
448 break;
449
450 thisnode->forward[level] = nextnode->forward[level];
451 }
452
453 /* free node memory */
454 free(nextnode);
455
456 /* adjust top/current level of list is necessary */
457 while(list->head->forward[top_level] == NULL && top_level > 0)
458 top_level--;
459 list->current_level = top_level;
460
461 /* adjust items */
462 list->items--;
463
464 deleted = TRUE;
465 }
466
467 /* free memory */
468 free(update);
469
470 return deleted;
471 }
472
473
474
475 /* delete all matching items from list */
skiplist_delete(skiplist * list,void * data)476 int skiplist_delete(skiplist *list, void *data) {
477 int deleted = 0;
478 int total_deleted = 0;
479
480 /* NOTE: there is a more efficient way to do this... */
481 while((deleted = skiplist_delete_first(list, data)) == 1)
482 total_deleted++;
483
484 return total_deleted;
485 }
486
487
488
489 /* delete specific node from list */
skiplist_delete_node(skiplist * list,void * node_ptr)490 int skiplist_delete_node(skiplist *list, void *node_ptr) {
491 void *data = NULL;
492 skiplistnode **update = NULL;
493 skiplistnode *thenode = NULL;
494 skiplistnode *thisnode = NULL;
495 skiplistnode *nextnode = NULL;
496 int level = 0;
497 int top_level = 0;
498 int deleted = FALSE;
499 int x = 0;
500
501 if(list == NULL || node_ptr == NULL)
502 return ERROR;
503
504 /* we'll need the data from the node to first find the node */
505 thenode = (skiplistnode *)node_ptr;
506 data = thenode->data;
507
508 /* initialize update vector */
509 if((update = (skiplistnode **)malloc(sizeof(skiplistnode *) * list->max_levels)) == NULL)
510 return ERROR;
511 for(x = 0; x < list->max_levels; x++)
512 update[x] = NULL;
513
514 /* find location in list */
515 thisnode = list->head;
516 for(top_level = level = list->current_level; level >= 0; level--) {
517 while((nextnode = thisnode->forward[level])) {
518
519 /* next node would be too far */
520 if(list->compare_function(nextnode->data, data) > 0)
521 break;
522 /* this is the exact node we want */
523 if(list->compare_function(nextnode->data, data) == 0 && nextnode == thenode)
524 break;
525
526 thisnode = nextnode;
527 }
528 update[level] = thisnode;
529 }
530
531 /* we found a match! (value + pointers match) */
532 if(nextnode && list->compare_function(nextnode->data, data) == 0 && nextnode == thenode) {
533
534 /* adjust level pointers to bypass (soon to be) removed node */
535 for(level = 0; level <= top_level; level++) {
536
537 thisnode = update[level];
538 if(thisnode->forward[level] != nextnode)
539 break;
540
541 thisnode->forward[level] = nextnode->forward[level];
542 }
543
544 /* free node memory */
545 free(nextnode);
546
547 /* adjust top/current level of list is necessary */
548 while(list->head->forward[top_level] == NULL && top_level > 0)
549 top_level--;
550 list->current_level = top_level;
551
552 /* adjust items */
553 list->items--;
554
555 deleted = TRUE;
556 }
557
558 /* free memory */
559 free(update);
560
561 return deleted;
562 }
563
564
565
566