lib/skiplist.h

   1 /*
   2  * Copyright 1990 William Pugh
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted.
   6  *
   7  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS''
   8  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
   9  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
  10  * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR
  11  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  12  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  13  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  14  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  15  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  16  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  17  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  18  * SUCH DAMAGE.
  19  *
  20  * Permission to include in quagga provide on March 31, 2016
  21  */
  22
  23 /*
  24  * Skip List implementation based on code from William Pugh.
  25  * ftp://ftp.cs.umd.edu/pub/skipLists/
  26  */
  27
  28 /* skiplist.h */
  29
  30
  31 #ifndef _ZEBRA_SKIPLIST_H
  32 #define _ZEBRA_SKIPLIST_H
  33
  34 #ifdef __cplusplus
  35 extern "C" {
  36 #endif
  37
  38 #define SKIPLIST_0TIMER_DEBUG 1
  39
  40 /*
  41  * skiplistnodes must always contain data to be valid. Adding an
  42  * empty node to a list is invalid
  43  */
  44 struct skiplistnode {
  45         void *key;
  46         void *value;
  47 #if SKIPLIST_0TIMER_DEBUG
  48         int flags;
  49 #define SKIPLIST_NODE_FLAG_INSERTED 0x00000001
  50 #endif
  51
  52         struct skiplistnode *forward[1]; /* variable sized */
  53 };
  54
  55 struct skiplist {
  56         int flags;
  57
  58 #define SKIPLIST_FLAG_ALLOW_DUPLICATES  0x00000001
  59
  60         int level; /* max lvl (1 + current # of levels in list) */
  61         unsigned int count;
  62         struct skiplistnode *header;
  63         int *level_stats;
  64         struct skiplistnode
  65                 *last; /* last real list item (NULL if empty list) */
  66
  67         /*
  68          * Returns -1 if val1 < val2, 0 if equal?, 1 if val1 > val2.
  69          * Used as definition of sorted for listnode_add_sort
  70          */
  71         int (*cmp)(const void *val1, const void *val2);
  72
  73         /* callback to free user-owned data when listnode is deleted. supplying
  74          * this callback is very much encouraged!
  75          */
  76         void (*del)(void *val);
  77 };
  78
  79
  80 /* Prototypes. */
  81 extern struct skiplist *
  82 skiplist_new(/* encouraged: set list.del callback on new lists */
  83              int flags,
  84              int (*cmp)(const void *key1,
  85                         const void *key2), /* NULL => default cmp */
  86              void (*del)(void *val));      /* NULL => no auto val free */
  87
  88 extern void skiplist_free(struct skiplist *);
  89
  90 extern int skiplist_insert(register struct skiplist *l, register void *key,
  91                            register void *value);
  92
  93 extern int skiplist_delete(register struct skiplist *l, register void *key,
  94                            register void *value);
  95
  96 extern int skiplist_search(register struct skiplist *l, register void *key,
  97                            void **valuePointer);
  98
  99 extern int skiplist_first_value(register struct skiplist *l, /* in */
 100                                 register const void *key,    /* in */
 101                                 void **valuePointer,         /* in/out */
 102                                 void **cursor);              /* out */
 103
 104 extern int skiplist_next_value(register struct skiplist *l, /* in */
 105                                register const void *key,          /* in */
 106                                void **valuePointer,      /* in/out */
 107                                void **cursor);              /* in/out */
 108
 109 extern int skiplist_first(register struct skiplist *l, void **keyPointer,
 110                           void **valuePointer);
 111
 112 extern int skiplist_last(register struct skiplist *l, void **keyPointer,
 113                          void **valuePointer);
 114
 115 extern int skiplist_delete_first(register struct skiplist *l);
 116
 117 extern int skiplist_next(register struct skiplist *l, /* in */
 118                          void **keyPointer,        /* out */
 119                          void **valuePointer,    /* out */
 120                          void **cursor);              /* in/out */
 121
 122 extern int skiplist_empty(register struct skiplist *l); /* in */
 123
 124 extern unsigned int skiplist_count(register struct skiplist *l); /* in */
 125
 126 struct vty;
 127 extern void skiplist_debug(struct vty *vty, struct skiplist *l);
 128
 129 extern void skiplist_test(struct vty *vty);
 130
 131 #ifdef __cplusplus
 132 }
 133 #endif
 134
 135 #endif /* _ZEBRA_SKIPLIST_H */