]>
Commit | Line | Data |
---|---|---|
6c2705cd LR |
1 | /* Copyright (C) 2016 Hewlett Packard Enterprise Development LP |
2 | * All Rights Reserved. | |
3 | * | |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); you may | |
5 | * not use this file except in compliance with the License. You may obtain | |
6 | * a copy of the License at | |
7 | * | |
8 | * http://www.apache.org/licenses/LICENSE-2.0 | |
9 | * | |
10 | * Unless required by applicable law or agreed to in writing, software | |
11 | * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT | |
12 | * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the | |
13 | * License for the specific language governing permissions and limitations | |
14 | * under the License. | |
15 | */ | |
16 | ||
17 | /* Skiplist implementation based on: | |
18 | * "Skip List: A Probabilistic Alternative to Balanced Trees", | |
19 | * by William Pugh. */ | |
20 | ||
21 | #include <config.h> | |
22 | #include <stdio.h> | |
23 | #include <stdbool.h> | |
24 | #include <stdint.h> | |
25 | #include <stdlib.h> | |
26 | #include <string.h> | |
27 | ||
28 | #include "skiplist.h" | |
29 | #include "random.h" | |
30 | #include "util.h" | |
31 | ||
32 | /* | |
33 | * A maximum height level of 32 should be more than sufficient for | |
34 | * anticipated use cases, delivering good expected performance with | |
35 | * up to 2**32 list nodes. Changes to this limit will also require | |
36 | * changes in skiplist_determine_level(). | |
37 | */ | |
38 | #define SKIPLIST_MAX_LEVELS 32 | |
39 | ||
40 | /* Skiplist node container */ | |
41 | struct skiplist_node { | |
42 | const void *data; /* Pointer to saved data. */ | |
6c2705cd LR |
43 | struct skiplist_node *forward[]; /* Links to the next nodes. */ |
44 | }; | |
45 | ||
46 | /* Skiplist container */ | |
47 | struct skiplist { | |
48 | struct skiplist_node *header; /* Pointer to head node (not first | |
49 | * data node). */ | |
50 | skiplist_comparator *cmp; /* Pointer to the skiplist's comparison | |
51 | * function. */ | |
52 | void *cfg; /* Pointer to optional comparison | |
53 | * configuration, used by the comparator. */ | |
54 | int level; /* Maximum level currently in use. */ | |
55 | uint32_t size; /* Current number of nodes in skiplist. */ | |
56 | }; | |
57 | ||
58 | /* Create a new skiplist_node with given level and data. */ | |
59 | static struct skiplist_node * | |
60 | skiplist_create_node(int level, const void *object) | |
61 | { | |
62 | struct skiplist_node *new_node; | |
63 | size_t alloc_size = sizeof *new_node + | |
64 | (level + 1) * sizeof new_node->forward[0]; | |
65 | ||
66 | new_node = xmalloc(alloc_size); | |
67 | new_node->data = object; | |
6c2705cd LR |
68 | memset(new_node->forward, 0, |
69 | (level + 1) * sizeof new_node->forward[0]); | |
70 | ||
71 | return new_node; | |
72 | } | |
73 | ||
74 | /* | |
75 | * Create a new skiplist, configured with given data comparison function | |
76 | * and configuration. | |
77 | */ | |
78 | struct skiplist * | |
79 | skiplist_create(skiplist_comparator object_comparator, void *configuration) | |
80 | { | |
81 | random_init(); | |
82 | struct skiplist *sl; | |
83 | ||
84 | sl = xmalloc(sizeof (struct skiplist)); | |
85 | sl->cfg = configuration; | |
86 | sl->size = 0; | |
87 | sl->level = 0; | |
88 | sl->cmp = object_comparator; | |
89 | sl->header = skiplist_create_node(SKIPLIST_MAX_LEVELS, NULL); | |
90 | ||
91 | return sl; | |
92 | } | |
93 | ||
94 | /* | |
95 | * Move the cursor forward to the first node with associated data greater than | |
96 | * or equal to "value". | |
97 | */ | |
98 | static struct skiplist_node * | |
99 | skiplist_forward_to_(struct skiplist *sl, const void *value, | |
100 | struct skiplist_node **update) | |
101 | { | |
102 | struct skiplist_node *x = sl->header; | |
103 | int i; | |
104 | ||
105 | /* Loop invariant: x < value */ | |
106 | for (i = sl->level; i >= 0; i--) { | |
107 | while (x->forward[i] && | |
108 | sl->cmp(x->forward[i]->data, value, sl->cfg) < 0) { | |
109 | x = x->forward[i]; | |
110 | } | |
111 | /* x < value <= x->forward[1] */ | |
112 | if (update) { | |
113 | update[i] = x; | |
114 | } | |
115 | } | |
116 | /* x < value <= x->forward[1] */ | |
117 | x = x->forward[0]; | |
118 | return x; | |
119 | } | |
120 | ||
121 | struct skiplist_node * | |
122 | skiplist_forward_to(struct skiplist *sl, const void *value) | |
123 | { | |
124 | return skiplist_forward_to_(sl, value, NULL); | |
125 | } | |
126 | ||
127 | /* Find the first exact match of value in the skiplist. */ | |
128 | struct skiplist_node * | |
129 | skiplist_find(struct skiplist *sl, const void *value) | |
130 | { | |
131 | struct skiplist_node *x = skiplist_forward_to(sl, value); | |
132 | ||
133 | return x && sl->cmp(x->data, value, sl->cfg) == 0 ? x : NULL; | |
134 | } | |
135 | ||
136 | /* | |
137 | * Determine the level for a skiplist node by choosing a level N with | |
138 | * probability P(N) = 1/(2**(N+1)) in the range 0..32, with the returned | |
139 | * level clamped at the current skiplist height plus 1. | |
140 | */ | |
141 | static int | |
142 | skiplist_determine_level(struct skiplist *sl) | |
143 | { | |
144 | int lvl; | |
145 | ||
146 | lvl = clz32(random_uint32()); | |
147 | ||
148 | return MIN(lvl, sl->level + 1); | |
149 | } | |
150 | ||
151 | /* Insert data into a skiplist. */ | |
152 | void | |
153 | skiplist_insert(struct skiplist *list, const void *value) | |
154 | { | |
155 | struct skiplist_node *update[SKIPLIST_MAX_LEVELS + 1]; | |
156 | struct skiplist_node *x = skiplist_forward_to_(list, value, update); | |
157 | int i, lvl; | |
158 | ||
159 | if (x && list->cmp(x->data, value, list->cfg) == 0) { | |
160 | x->data = value; | |
161 | } else { | |
162 | lvl = skiplist_determine_level(list); | |
163 | if (lvl > list->level) { | |
164 | for (i = list->level + 1; i <= lvl; i++) { | |
165 | update[i] = list->header; | |
166 | } | |
167 | list->level = lvl; | |
168 | } | |
169 | x = skiplist_create_node(lvl, value); | |
170 | for (i = 0; i <= lvl; i++) { | |
171 | x->forward[i] = update[i]->forward[i]; | |
172 | update[i]->forward[i] = x; | |
173 | } | |
174 | list->size++; | |
175 | } | |
176 | } | |
177 | ||
178 | /* Remove first node with associated data equal to "value" from skiplist. */ | |
179 | void * | |
180 | skiplist_delete(struct skiplist *list, const void *value) | |
181 | { | |
182 | struct skiplist_node *update[SKIPLIST_MAX_LEVELS + 1]; | |
183 | struct skiplist_node *x; | |
184 | void *data = NULL; | |
185 | int i; | |
186 | ||
187 | x = skiplist_forward_to_(list, value, update); | |
188 | ||
189 | if (x && list->cmp(x->data, value, list->cfg) == 0) { | |
190 | for (i = 0; i <= list->level; i++) { | |
7f289e02 | 191 | if (update[i]->forward[i] != x) { |
6c2705cd LR |
192 | break; |
193 | } | |
194 | update[i]->forward[i] = x->forward[i]; | |
195 | } | |
196 | data = CONST_CAST(void *, x->data); | |
197 | ||
198 | free(x); | |
199 | ||
200 | while (list->level > 0 && !list->header->forward[list->level]) { | |
201 | list->level--; | |
202 | } | |
203 | list->size--; | |
204 | } | |
205 | return data; | |
206 | } | |
207 | ||
208 | /* Get the associated data value stored in a skiplist node. */ | |
209 | void * | |
210 | skiplist_get_data(struct skiplist_node *node) | |
211 | { | |
212 | return node ? CONST_CAST(void *, node->data) : NULL; | |
213 | } | |
214 | ||
215 | /* Get the number of items in a skiplist. */ | |
216 | uint32_t | |
217 | skiplist_get_size(struct skiplist *sl) | |
218 | { | |
219 | return sl->size; | |
220 | } | |
221 | ||
222 | /* Get the first node in a skiplist. */ | |
223 | struct skiplist_node * | |
224 | skiplist_first(struct skiplist *sl) | |
225 | { | |
226 | return sl->header->forward[0]; | |
227 | } | |
228 | ||
229 | /* Get a node's successor in a skiplist. */ | |
230 | struct skiplist_node * | |
231 | skiplist_next(struct skiplist_node *node) | |
232 | { | |
233 | return node ? node->forward[0] : NULL; | |
234 | } | |
235 | ||
236 | /* | |
237 | * Destroy a skiplist and free all nodes in the list. If the "data_destroy" | |
238 | * function pointer is non-NULL, it will be called for each node as it is | |
239 | * removed to allow any needed cleanups to be performed on the associated | |
240 | * data. | |
241 | */ | |
242 | void | |
243 | skiplist_destroy(struct skiplist *sl, void (*data_destroy)(void *)) | |
244 | { | |
245 | struct skiplist_node *node, *next; | |
246 | ||
247 | next = node = sl->header; | |
248 | while (next != NULL) { | |
249 | next = node->forward[0]; | |
250 | if (data_destroy) { | |
251 | data_destroy(CONST_CAST(void *, node->data)); | |
252 | } | |
253 | free(node); | |
254 | node = next; | |
255 | } | |
256 | free(sl); | |
257 | } |