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
|
/*
* 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 implementation based on code from William Pugh.
* ftp://ftp.cs.umd.edu/pub/skipLists/
*/
/* skiplist.h */
#ifndef _ZEBRA_SKIPLIST_H
#define _ZEBRA_SKIPLIST_H
#ifdef __cplusplus
extern "C" {
#endif
#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;
int *level_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)(const void *val1, const 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)(const void *key1,
const 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 const void *key, /* in */
void **valuePointer, /* in/out */
void **cursor); /* out */
extern int skiplist_next_value(register struct skiplist *l, /* in */
register const 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 */
struct vty;
extern void skiplist_debug(struct vty *vty, struct skiplist *l);
extern void skiplist_test(struct vty *vty);
#ifdef __cplusplus
}
#endif
#endif /* _ZEBRA_SKIPLIST_H */
|
