1 // (c) 2016 Jeffrey Crowell 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 #ifndef R2_SKIP_LIST_H 11 #define R2_SKIP_LIST_H 12 13 #include <r_list.h> 14 15 typedef struct r_skiplist_node_t { 16 void *data; // pointer to the value 17 struct r_skiplist_node_t **forward; // forward pointer 18 } RSkipListNode; 19 20 typedef struct r_skiplist_t { 21 RSkipListNode *head; // list header 22 int list_level; // current level of the list. 23 int size; 24 RListFree freefn; 25 RListComparator compare; 26 } RSkipList; 27 28 R_API RSkipList* r_skiplist_new(RListFree freefn, RListComparator comparefn); 29 R_API void r_skiplist_free(RSkipList *list); 30 R_API void r_skiplist_purge(RSkipList *list); 31 R_API RSkipListNode* r_skiplist_insert(RSkipList* list, void* data); 32 R_API bool r_skiplist_insert_autofree(RSkipList* list, void* data); 33 R_API bool r_skiplist_delete(RSkipList* list, void* data); 34 R_API bool r_skiplist_delete_node(RSkipList *list, RSkipListNode *node); 35 R_API RSkipListNode* r_skiplist_find(RSkipList* list, void* data); 36 R_API RSkipListNode* r_skiplist_find_geq(RSkipList* list, void* data); 37 R_API RSkipListNode* r_skiplist_find_leq(RSkipList* list, void* data); 38 R_API void r_skiplist_join(RSkipList *l1, RSkipList *l2); 39 R_API void *r_skiplist_get_first(RSkipList *list); 40 R_API void *r_skiplist_get_n(RSkipList *list, int n); 41 R_API void* r_skiplist_get_geq(RSkipList* list, void* data); 42 R_API void* r_skiplist_get_leq(RSkipList* list, void* data); 43 R_API bool r_skiplist_empty(RSkipList *list); 44 R_API RList *r_skiplist_to_list(RSkipList *list); 45 46 #define r_skiplist_islast(list, el) (el->forward[0] == list->head) 47 48 #define r_skiplist_length(list) (list->size) 49 50 #define r_skiplist_foreach(list, it, pos)\ 51 if (list)\ 52 for (it = list->head->forward[0]; it != list->head && ((pos = it->data) || 1); it = it->forward[0]) 53 54 #define r_skiplist_foreach_safe(list, it, tmp, pos)\ 55 if (list)\ 56 for (it = list->head->forward[0]; it != list->head && ((pos = it->data) || 1) && ((tmp = it->forward[0]) || 1); it = tmp) 57 58 #endif // R2_SKIP_LIST_H 59