]>
git.proxmox.com Git - mirror_frr.git/blob - lib/skiplist.h
2 * Copyright 1990 William Pugh
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted.
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
20 * Permission to include in quagga provide on March 31, 2016
24 * Skip List impementation based on code from William Pugh.
25 * ftp://ftp.cs.umd.edu/pub/skipLists/
31 #ifndef _ZEBRA_SKIPLIST_H
32 #define _ZEBRA_SKIPLIST_H
34 #define SKIPLIST_0TIMER_DEBUG 1
37 * skiplistnodes must always contain data to be valid. Adding an
38 * empty node to a list is invalid
44 #if SKIPLIST_0TIMER_DEBUG
46 #define SKIPLIST_NODE_FLAG_INSERTED 0x00000001
49 struct skiplistnode
*forward
[1]; /* variable sized */
56 #define SKIPLIST_FLAG_ALLOW_DUPLICATES 0x00000001
58 int level
; /* max lvl (1 + current # of levels in list) */
60 struct skiplistnode
*header
;
61 struct skiplistnode
*stats
;
62 struct skiplistnode
*last
; /* last real list item (NULL if empty list) */
65 * Returns -1 if val1 < val2, 0 if equal?, 1 if val1 > val2.
66 * Used as definition of sorted for listnode_add_sort
68 int (*cmp
) (void *val1
, void *val2
);
70 /* callback to free user-owned data when listnode is deleted. supplying
71 * this callback is very much encouraged!
73 void (*del
) (void *val
);
78 extern struct skiplist
*
79 skiplist_new( /* encouraged: set list.del callback on new lists */
81 int (*cmp
) (void *key1
, void *key2
), /* NULL => default cmp */
82 void (*del
) (void *val
)); /* NULL => no auto val free */
85 skiplist_free (struct skiplist
*);
89 register struct skiplist
*l
,
91 register void *value
);
95 register struct skiplist
*l
,
97 register void *value
);
101 register struct skiplist
*l
,
103 void **valuePointer
);
106 skiplist_first_value(
107 register struct skiplist
*l
, /* in */
108 register void *key
, /* in */
109 void **valuePointer
, /* in/out */
110 void **cursor
); /* out */
114 register struct skiplist
*l
, /* in */
115 register void *key
, /* in */
116 void **valuePointer
, /* in/out */
117 void **cursor
); /* in/out */
121 register struct skiplist
*l
,
123 void **valuePointer
);
127 register struct skiplist
*l
,
129 void **valuePointer
);
132 skiplist_delete_first(
133 register struct skiplist
*l
);
137 register struct skiplist
*l
, /* in */
138 void **keyPointer
, /* out */
139 void **valuePointer
, /* out */
140 void **cursor
); /* in/out */
144 register struct skiplist
*l
); /* in */
148 register struct skiplist
*l
); /* in */
159 #endif /* _ZEBRA_SKIPLIST_H */