]>
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
43 #if SKIPLIST_0TIMER_DEBUG
45 #define SKIPLIST_NODE_FLAG_INSERTED 0x00000001
48 struct skiplistnode
*forward
[1]; /* variable sized */
54 #define SKIPLIST_FLAG_ALLOW_DUPLICATES 0x00000001
56 int level
; /* max lvl (1 + current # of levels in list) */
58 struct skiplistnode
*header
;
59 struct skiplistnode
*stats
;
61 *last
; /* last real list item (NULL if empty list) */
64 * Returns -1 if val1 < val2, 0 if equal?, 1 if val1 > val2.
65 * Used as definition of sorted for listnode_add_sort
67 int (*cmp
)(void *val1
, void *val2
);
69 /* callback to free user-owned data when listnode is deleted. supplying
70 * this callback is very much encouraged!
72 void (*del
)(void *val
);
77 extern struct skiplist
*
78 skiplist_new(/* encouraged: set list.del callback on new lists */
80 int (*cmp
)(void *key1
, void *key2
), /* NULL => default cmp */
81 void (*del
)(void *val
)); /* NULL => no auto val free */
83 extern void skiplist_free(struct skiplist
*);
85 extern int skiplist_insert(register struct skiplist
*l
, register void *key
,
86 register void *value
);
88 extern int skiplist_delete(register struct skiplist
*l
, register void *key
,
89 register void *value
);
91 extern int skiplist_search(register struct skiplist
*l
, register void *key
,
94 extern int skiplist_first_value(register struct skiplist
*l
, /* in */
95 register void *key
, /* in */
96 void **valuePointer
, /* in/out */
97 void **cursor
); /* out */
99 extern int skiplist_next_value(register struct skiplist
*l
, /* in */
100 register void *key
, /* in */
101 void **valuePointer
, /* in/out */
102 void **cursor
); /* in/out */
104 extern int skiplist_first(register struct skiplist
*l
, void **keyPointer
,
105 void **valuePointer
);
107 extern int skiplist_last(register struct skiplist
*l
, void **keyPointer
,
108 void **valuePointer
);
110 extern int skiplist_delete_first(register struct skiplist
*l
);
112 extern int skiplist_next(register struct skiplist
*l
, /* in */
113 void **keyPointer
, /* out */
114 void **valuePointer
, /* out */
115 void **cursor
); /* in/out */
117 extern int skiplist_empty(register struct skiplist
*l
); /* in */
119 extern unsigned int skiplist_count(register struct skiplist
*l
); /* in */
121 extern void skiplist_debug(struct vty
*vty
, struct skiplist
*l
);
123 extern void skiplist_test(struct vty
*vty
);
125 #endif /* _ZEBRA_SKIPLIST_H */