lib/skiplist.h

   1 // SPDX-License-Identifier: LicenseRef-Skiplist-BSD-0-Clause
   2 /*
   3  * Copyright 1990 William Pugh
   4  *
   5  * Permission to include in quagga provide on March 31, 2016
   6  */
   7
   8 /*
   9  * Skip List implementation based on code from William Pugh.
  10  * ftp://ftp.cs.umd.edu/pub/skipLists/
  11  */
  12
  13 /* skiplist.h */
  14
  15
  16 #ifndef _ZEBRA_SKIPLIST_H
  17 #define _ZEBRA_SKIPLIST_H
  18
  19 #ifdef __cplusplus
  20 extern "C" {
  21 #endif
  22
  23 #define SKIPLIST_0TIMER_DEBUG 1
  24
  25 /*
  26  * skiplistnodes must always contain data to be valid. Adding an
  27  * empty node to a list is invalid
  28  */
  29 struct skiplistnode {
  30         void *key;
  31         void *value;
  32 #if SKIPLIST_0TIMER_DEBUG
  33         int flags;
  34 #define SKIPLIST_NODE_FLAG_INSERTED 0x00000001
  35 #endif
  36
  37         struct skiplistnode *forward[1]; /* variable sized */
  38 };
  39
  40 struct skiplist {
  41         int flags;
  42
  43 #define SKIPLIST_FLAG_ALLOW_DUPLICATES  0x00000001
  44
  45         int level; /* max lvl (1 + current # of levels in list) */
  46         unsigned int count;
  47         struct skiplistnode *header;
  48         int *level_stats;
  49         struct skiplistnode
  50                 *last; /* last real list item (NULL if empty list) */
  51
  52         /*
  53          * Returns -1 if val1 < val2, 0 if equal?, 1 if val1 > val2.
  54          * Used as definition of sorted for listnode_add_sort
  55          */
  56         int (*cmp)(const void *val1, const void *val2);
  57
  58         /* callback to free user-owned data when listnode is deleted. supplying
  59          * this callback is very much encouraged!
  60          */
  61         void (*del)(void *val);
  62 };
  63
  64
  65 /* Prototypes. */
  66 extern struct skiplist *
  67 skiplist_new(/* encouraged: set list.del callback on new lists */
  68              int flags,
  69              int (*cmp)(const void *key1,
  70                         const void *key2), /* NULL => default cmp */
  71              void (*del)(void *val));      /* NULL => no auto val free */
  72
  73 extern void skiplist_free(struct skiplist *);
  74
  75 extern int skiplist_insert(register struct skiplist *l, register void *key,
  76                            register void *value);
  77
  78 extern int skiplist_delete(register struct skiplist *l, register void *key,
  79                            register void *value);
  80
  81 extern int skiplist_search(register struct skiplist *l, register void *key,
  82                            void **valuePointer);
  83
  84 extern int skiplist_first_value(register struct skiplist *l, /* in */
  85                                 register const void *key,    /* in */
  86                                 void **valuePointer,         /* in/out */
  87                                 void **cursor);              /* out */
  88
  89 extern int skiplist_next_value(register struct skiplist *l, /* in */
  90                                register const void *key,          /* in */
  91                                void **valuePointer,      /* in/out */
  92                                void **cursor);              /* in/out */
  93
  94 extern int skiplist_first(register struct skiplist *l, void **keyPointer,
  95                           void **valuePointer);
  96
  97 extern int skiplist_last(register struct skiplist *l, void **keyPointer,
  98                          void **valuePointer);
  99
 100 extern int skiplist_delete_first(register struct skiplist *l);
 101
 102 extern int skiplist_next(register struct skiplist *l, /* in */
 103                          void **keyPointer,        /* out */
 104                          void **valuePointer,    /* out */
 105                          void **cursor);              /* in/out */
 106
 107 extern int skiplist_empty(register struct skiplist *l); /* in */
 108
 109 extern unsigned int skiplist_count(register struct skiplist *l); /* in */
 110
 111 struct vty;
 112 extern void skiplist_debug(struct vty *vty, struct skiplist *l);
 113
 114 extern void skiplist_test(struct vty *vty);
 115
 116 #ifdef __cplusplus
 117 }
 118 #endif
 119
 120 #endif /* _ZEBRA_SKIPLIST_H */