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 impementation 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 #define SKIPLIST_0TIMER_DEBUG 1
  35
  36 /*
  37  * skiplistnodes must always contain data to be valid. Adding an
  38  * empty node to a list is invalid
  39  */
  40 struct skiplistnode
  41 {
  42   void                  *key;
  43   void                  *value;
  44 #if SKIPLIST_0TIMER_DEBUG
  45   int                   flags;
  46 #define SKIPLIST_NODE_FLAG_INSERTED 0x00000001
  47 #endif
  48
  49   struct skiplistnode   *forward[1];    /* variable sized */
  50 };
  51
  52 struct skiplist
  53 {
  54   int                   flags;
  55
  56 #define SKIPLIST_FLAG_ALLOW_DUPLICATES  0x00000001
  57
  58   int                   level;  /* max lvl (1 + current # of levels in list) */
  59   unsigned int          count;
  60   struct skiplistnode   *header;
  61   struct skiplistnode   *stats;
  62   struct skiplistnode   *last;  /* last real list item (NULL if empty list) */
  63
  64   /*
  65    * Returns -1 if val1 < val2, 0 if equal?, 1 if val1 > val2.
  66    * Used as definition of sorted for listnode_add_sort
  67    */
  68   int (*cmp) (void *val1, void *val2);
  69
  70   /* callback to free user-owned data when listnode is deleted. supplying
  71    * this callback is very much encouraged!
  72    */
  73   void (*del) (void *val);
  74 };
  75
  76
  77 /* Prototypes. */
  78 extern struct skiplist *
  79 skiplist_new( /* encouraged: set list.del callback on new lists */
  80     int flags,
  81     int (*cmp) (void *key1, void *key2),        /* NULL => default cmp */
  82     void (*del) (void *val));                   /* NULL => no auto val free */
  83
  84 extern void
  85 skiplist_free (struct skiplist *);
  86
  87 extern int
  88 skiplist_insert(
  89     register struct skiplist *l,
  90     register void *key,
  91     register void *value);
  92
  93 extern int
  94 skiplist_delete(
  95     register struct skiplist *l,
  96     register void *key,
  97     register void *value);
  98
  99 extern int
 100 skiplist_search(
 101     register struct skiplist     *l,
 102     register void               *key,
 103     void                        **valuePointer);
 104
 105 extern int
 106 skiplist_first_value(
 107     register struct skiplist    *l,                     /* in */
 108     register void               *key,                   /* in */
 109     void                        **valuePointer,         /* in/out */
 110     void                        **cursor);              /* out */
 111
 112 extern int
 113 skiplist_next_value(
 114     register struct skiplist    *l,                     /* in */
 115     register void               *key,                   /* in */
 116     void                        **valuePointer,         /* in/out */
 117     void                        **cursor);              /* in/out */
 118
 119 extern int
 120 skiplist_first(
 121     register struct skiplist     *l,
 122     void                        **keyPointer,
 123     void                        **valuePointer);
 124
 125 extern int
 126 skiplist_last(
 127     register struct skiplist     *l,
 128     void                        **keyPointer,
 129     void                        **valuePointer);
 130
 131 extern int
 132 skiplist_delete_first(
 133     register struct skiplist     *l);
 134
 135 extern int
 136 skiplist_next(
 137     register struct skiplist     *l,                    /* in */
 138     void                        **keyPointer,           /* out */
 139     void                        **valuePointer,         /* out */
 140     void                        **cursor);              /* in/out */
 141
 142 extern int
 143 skiplist_empty(
 144     register struct skiplist     *l);                   /* in */
 145
 146 extern unsigned int
 147 skiplist_count(
 148     register struct skiplist     *l);                   /* in */
 149
 150 extern void
 151 skiplist_debug(
 152     struct vty *vty,
 153     struct skiplist *l);
 154
 155 extern void
 156 skiplist_test(
 157     struct vty *vty);
 158
 159 #endif /* _ZEBRA_SKIPLIST_H */