]>
git.proxmox.com Git - mirror_frr.git/blob - lib/skiplist.h
1 // SPDX-License-Identifier: LicenseRef-Skiplist-BSD-0-Clause
3 * Copyright 1990 William Pugh
5 * Permission to include in quagga provide on March 31, 2016
9 * Skip List implementation based on code from William Pugh.
10 * ftp://ftp.cs.umd.edu/pub/skipLists/
16 #ifndef _ZEBRA_SKIPLIST_H
17 #define _ZEBRA_SKIPLIST_H
23 #define SKIPLIST_0TIMER_DEBUG 1
26 * skiplistnodes must always contain data to be valid. Adding an
27 * empty node to a list is invalid
32 #if SKIPLIST_0TIMER_DEBUG
34 #define SKIPLIST_NODE_FLAG_INSERTED 0x00000001
37 struct skiplistnode
*forward
[1]; /* variable sized */
43 #define SKIPLIST_FLAG_ALLOW_DUPLICATES 0x00000001
45 int level
; /* max lvl (1 + current # of levels in list) */
47 struct skiplistnode
*header
;
50 *last
; /* last real list item (NULL if empty list) */
53 * Returns -1 if val1 < val2, 0 if equal?, 1 if val1 > val2.
54 * Used as definition of sorted for listnode_add_sort
56 int (*cmp
)(const void *val1
, const void *val2
);
58 /* callback to free user-owned data when listnode is deleted. supplying
59 * this callback is very much encouraged!
61 void (*del
)(void *val
);
66 extern struct skiplist
*
67 skiplist_new(/* encouraged: set list.del callback on new lists */
69 int (*cmp
)(const void *key1
,
70 const void *key2
), /* NULL => default cmp */
71 void (*del
)(void *val
)); /* NULL => no auto val free */
73 extern void skiplist_free(struct skiplist
*);
75 extern int skiplist_insert(register struct skiplist
*l
, register void *key
,
76 register void *value
);
78 extern int skiplist_delete(register struct skiplist
*l
, register void *key
,
79 register void *value
);
81 extern int skiplist_search(register struct skiplist
*l
, register void *key
,
84 extern int skiplist_first_value(register struct skiplist
*l
, /* in */
85 register const void *key
, /* in */
86 void **valuePointer
, /* in/out */
87 void **cursor
); /* out */
89 extern int skiplist_next_value(register struct skiplist
*l
, /* in */
90 register const void *key
, /* in */
91 void **valuePointer
, /* in/out */
92 void **cursor
); /* in/out */
94 extern int skiplist_first(register struct skiplist
*l
, void **keyPointer
,
97 extern int skiplist_last(register struct skiplist
*l
, void **keyPointer
,
100 extern int skiplist_delete_first(register struct skiplist
*l
);
102 extern int skiplist_next(register struct skiplist
*l
, /* in */
103 void **keyPointer
, /* out */
104 void **valuePointer
, /* out */
105 void **cursor
); /* in/out */
107 extern int skiplist_empty(register struct skiplist
*l
); /* in */
109 extern unsigned int skiplist_count(register struct skiplist
*l
); /* in */
112 extern void skiplist_debug(struct vty
*vty
, struct skiplist
*l
);
114 extern void skiplist_test(struct vty
*vty
);
120 #endif /* _ZEBRA_SKIPLIST_H */