1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
/*
* Copyright 1990 William Pugh
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS''
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
* PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*
* Permission to include in quagga provide on March 31, 2016
*/
/*
* Skip List impementation based on code from William Pugh.
* ftp://ftp.cs.umd.edu/pub/skipLists/
*/
/* skiplist.h */
#ifndef _ZEBRA_SKIPLIST_H
#define _ZEBRA_SKIPLIST_H
#define SKIPLIST_0TIMER_DEBUG 1
/*
* skiplistnodes must always contain data to be valid. Adding an
* empty node to a list is invalid
*/
struct skiplistnode
{
void *key;
void *value;
#if SKIPLIST_0TIMER_DEBUG
int flags;
#define SKIPLIST_NODE_FLAG_INSERTED 0x00000001
#endif
struct skiplistnode *forward[1]; /* variable sized */
};
struct skiplist
{
int flags;
#define SKIPLIST_FLAG_ALLOW_DUPLICATES 0x00000001
int level; /* max lvl (1 + current # of levels in list) */
unsigned int count;
struct skiplistnode *header;
struct skiplistnode *stats;
struct skiplistnode *last; /* last real list item (NULL if empty list) */
/*
* Returns -1 if val1 < val2, 0 if equal?, 1 if val1 > val2.
* Used as definition of sorted for listnode_add_sort
*/
int (*cmp) (void *val1, void *val2);
/* callback to free user-owned data when listnode is deleted. supplying
* this callback is very much encouraged!
*/
void (*del) (void *val);
};
/* Prototypes. */
extern struct skiplist *
skiplist_new( /* encouraged: set list.del callback on new lists */
int flags,
int (*cmp) (void *key1, void *key2), /* NULL => default cmp */
void (*del) (void *val)); /* NULL => no auto val free */
extern void
skiplist_free (struct skiplist *);
extern int
skiplist_insert(
register struct skiplist *l,
register void *key,
register void *value);
extern int
skiplist_delete(
register struct skiplist *l,
register void *key,
register void *value);
extern int
skiplist_search(
register struct skiplist *l,
register void *key,
void **valuePointer);
extern int
skiplist_first_value(
register struct skiplist *l, /* in */
register void *key, /* in */
void **valuePointer, /* in/out */
void **cursor); /* out */
extern int
skiplist_next_value(
register struct skiplist *l, /* in */
register void *key, /* in */
void **valuePointer, /* in/out */
void **cursor); /* in/out */
extern int
skiplist_first(
register struct skiplist *l,
void **keyPointer,
void **valuePointer);
extern int
skiplist_last(
register struct skiplist *l,
void **keyPointer,
void **valuePointer);
extern int
skiplist_delete_first(
register struct skiplist *l);
extern int
skiplist_next(
register struct skiplist *l, /* in */
void **keyPointer, /* out */
void **valuePointer, /* out */
void **cursor); /* in/out */
extern int
skiplist_empty(
register struct skiplist *l); /* in */
extern unsigned int
skiplist_count(
register struct skiplist *l); /* in */
extern void
skiplist_debug(
struct vty *vty,
struct skiplist *l);
extern void
skiplist_test(
struct vty *vty);
#endif /* _ZEBRA_SKIPLIST_H */
|
