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
|
/*
* 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 */
|
