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 #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         struct skiplistnode *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)(void *val1, 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)(void *key1, void *key2), /* NULL => default cmp */
  85              void (*del)(void *val));            /* NULL => no auto val free */
  86
  87 extern void skiplist_free(struct skiplist *);
  88
  89 extern int skiplist_insert(register struct skiplist *l, register void *key,
  90                            register void *value);
  91
  92 extern int skiplist_delete(register struct skiplist *l, register void *key,
  93                            register void *value);
  94
  95 extern int skiplist_search(register struct skiplist *l, register void *key,
  96                            void **valuePointer);
  97
  98 extern int skiplist_first_value(register struct skiplist *l, /* in */
  99                                 register void *key,       /* in */
 100                                 void **valuePointer,     /* in/out */
 101                                 void **cursor);              /* out */
 102
 103 extern int skiplist_next_value(register struct skiplist *l, /* in */
 104                                register void *key,        /* in */
 105                                void **valuePointer,      /* in/out */
 106                                void **cursor);              /* in/out */
 107
 108 extern int skiplist_first(register struct skiplist *l, void **keyPointer,
 109                           void **valuePointer);
 110
 111 extern int skiplist_last(register struct skiplist *l, void **keyPointer,
 112                          void **valuePointer);
 113
 114 extern int skiplist_delete_first(register struct skiplist *l);
 115
 116 extern int skiplist_next(register struct skiplist *l, /* in */
 117                          void **keyPointer,        /* out */
 118                          void **valuePointer,    /* out */
 119                          void **cursor);              /* in/out */
 120
 121 extern int skiplist_empty(register struct skiplist *l); /* in */
 122
 123 extern unsigned int skiplist_count(register struct skiplist *l); /* in */
 124
 125 extern void skiplist_debug(struct vty *vty, struct skiplist *l);
 126
 127 extern void skiplist_test(struct vty *vty);
 128
 129 #ifdef __cplusplus
 130 }
 131 #endif
 132
 133 #endif /* _ZEBRA_SKIPLIST_H */