1 /* xf86drmSL.c -- Skip list support
2 * Created: Mon May 10 09:28:13 1999 by faith@precisioninsight.com
3 *
4 * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas.
5 * All Rights Reserved.
6 *
7 * Permission is hereby granted, free of charge, to any person obtaining a
8 * copy of this software and associated documentation files (the "Software"),
9 * to deal in the Software without restriction, including without limitation
10 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
11 * and/or sell copies of the Software, and to permit persons to whom the
12 * Software is furnished to do so, subject to the following conditions:
13 *
14 * The above copyright notice and this permission notice (including the next
15 * paragraph) shall be included in all copies or substantial portions of the
16 * Software.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
21 * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
22 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
23 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
24 * DEALINGS IN THE SOFTWARE.
25 *
26 * Authors: Rickard E. (Rik) Faith <faith@valinux.com>
27 *
28 * DESCRIPTION
29 *
30 * This file contains a straightforward skip list implementation.n
31 *
32 * FUTURE ENHANCEMENTS
33 *
34 * REFERENCES
35 *
36 * [Pugh90] William Pugh. Skip Lists: A Probabilistic Alternative to
37 * Balanced Trees. CACM 33(6), June 1990, pp. 668-676.
38 *
39 */
40
41 #include <stdio.h>
42 #include <stdlib.h>
43
44 #include "xf86drm.h"
45
46 #define SL_LIST_MAGIC 0xfacade00LU
47 #define SL_ENTRY_MAGIC 0x00fab1edLU
48 #define SL_FREED_MAGIC 0xdecea5edLU
49 #define SL_MAX_LEVEL 16
50 #define SL_RANDOM_SEED 0xc01055a1LU
51
52 #define SL_RANDOM_DECL static void *state = NULL
53 #define SL_RANDOM_INIT(seed) if (!state) state = drmRandomCreate(seed)
54 #define SL_RANDOM drmRandom(state)
55
56 typedef struct SLEntry {
57 unsigned long magic; /* SL_ENTRY_MAGIC */
58 unsigned long key;
59 void *value;
60 int levels;
61 struct SLEntry *forward[1]; /* variable sized array */
62 } SLEntry, *SLEntryPtr;
63
64 typedef struct SkipList {
65 unsigned long magic; /* SL_LIST_MAGIC */
66 int level;
67 int count;
68 SLEntryPtr head;
69 SLEntryPtr p0; /* Position for iteration */
70 } SkipList, *SkipListPtr;
71
SLCreateEntry(int max_level,unsigned long key,void * value)72 static SLEntryPtr SLCreateEntry(int max_level, unsigned long key, void *value)
73 {
74 SLEntryPtr entry;
75
76 if (max_level < 0 || max_level > SL_MAX_LEVEL) max_level = SL_MAX_LEVEL;
77
78 entry = drmMalloc(sizeof(*entry)
79 + (max_level + 1) * sizeof(entry->forward[0]));
80 if (!entry) return NULL;
81 entry->magic = SL_ENTRY_MAGIC;
82 entry->key = key;
83 entry->value = value;
84 entry->levels = max_level + 1;
85
86 return entry;
87 }
88
SLRandomLevel(void)89 static int SLRandomLevel(void)
90 {
91 int level = 1;
92 SL_RANDOM_DECL;
93
94 SL_RANDOM_INIT(SL_RANDOM_SEED);
95
96 while ((SL_RANDOM & 0x01) && level < SL_MAX_LEVEL) ++level;
97 return level;
98 }
99
drmSLCreate(void)100 void *drmSLCreate(void)
101 {
102 SkipListPtr list;
103 int i;
104
105 list = drmMalloc(sizeof(*list));
106 if (!list) return NULL;
107 list->magic = SL_LIST_MAGIC;
108 list->level = 0;
109 list->head = SLCreateEntry(SL_MAX_LEVEL, 0, NULL);
110 list->count = 0;
111
112 for (i = 0; i <= SL_MAX_LEVEL; i++) list->head->forward[i] = NULL;
113
114 return list;
115 }
116
drmSLDestroy(void * l)117 int drmSLDestroy(void *l)
118 {
119 SkipListPtr list = (SkipListPtr)l;
120 SLEntryPtr entry;
121 SLEntryPtr next;
122
123 if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
124
125 for (entry = list->head; entry; entry = next) {
126 if (entry->magic != SL_ENTRY_MAGIC) return -1; /* Bad magic */
127 next = entry->forward[0];
128 entry->magic = SL_FREED_MAGIC;
129 drmFree(entry);
130 }
131
132 list->magic = SL_FREED_MAGIC;
133 drmFree(list);
134 return 0;
135 }
136
SLLocate(void * l,unsigned long key,SLEntryPtr * update)137 static SLEntryPtr SLLocate(void *l, unsigned long key, SLEntryPtr *update)
138 {
139 SkipListPtr list = (SkipListPtr)l;
140 SLEntryPtr entry;
141 int i;
142
143 if (list->magic != SL_LIST_MAGIC) return NULL;
144
145 for (i = list->level, entry = list->head; i >= 0; i--) {
146 while (entry->forward[i] && entry->forward[i]->key < key)
147 entry = entry->forward[i];
148 update[i] = entry;
149 }
150
151 return entry->forward[0];
152 }
153
drmSLInsert(void * l,unsigned long key,void * value)154 int drmSLInsert(void *l, unsigned long key, void *value)
155 {
156 SkipListPtr list = (SkipListPtr)l;
157 SLEntryPtr entry;
158 SLEntryPtr update[SL_MAX_LEVEL + 1];
159 int level;
160 int i;
161
162 if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
163
164 entry = SLLocate(list, key, update);
165
166 if (entry && entry->key == key) return 1; /* Already in list */
167
168
169 level = SLRandomLevel();
170 if (level > list->level) {
171 level = ++list->level;
172 update[level] = list->head;
173 }
174
175 entry = SLCreateEntry(level, key, value);
176
177 /* Fix up forward pointers */
178 for (i = 0; i <= level; i++) {
179 entry->forward[i] = update[i]->forward[i];
180 update[i]->forward[i] = entry;
181 }
182
183 ++list->count;
184 return 0; /* Added to table */
185 }
186
drmSLDelete(void * l,unsigned long key)187 int drmSLDelete(void *l, unsigned long key)
188 {
189 SkipListPtr list = (SkipListPtr)l;
190 SLEntryPtr update[SL_MAX_LEVEL + 1];
191 SLEntryPtr entry;
192 int i;
193
194 if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
195
196 entry = SLLocate(list, key, update);
197
198 if (!entry || entry->key != key) return 1; /* Not found */
199
200 /* Fix up forward pointers */
201 for (i = 0; i <= list->level; i++) {
202 if (update[i]->forward[i] == entry)
203 update[i]->forward[i] = entry->forward[i];
204 }
205
206 entry->magic = SL_FREED_MAGIC;
207 drmFree(entry);
208
209 while (list->level && !list->head->forward[list->level]) --list->level;
210 --list->count;
211 return 0;
212 }
213
drmSLLookup(void * l,unsigned long key,void ** value)214 int drmSLLookup(void *l, unsigned long key, void **value)
215 {
216 SkipListPtr list = (SkipListPtr)l;
217 SLEntryPtr update[SL_MAX_LEVEL + 1];
218 SLEntryPtr entry;
219
220 entry = SLLocate(list, key, update);
221
222 if (entry && entry->key == key) {
223 *value = entry;
224 return 0;
225 }
226 *value = NULL;
227 return -1;
228 }
229
drmSLLookupNeighbors(void * l,unsigned long key,unsigned long * prev_key,void ** prev_value,unsigned long * next_key,void ** next_value)230 int drmSLLookupNeighbors(void *l, unsigned long key,
231 unsigned long *prev_key, void **prev_value,
232 unsigned long *next_key, void **next_value)
233 {
234 SkipListPtr list = (SkipListPtr)l;
235 SLEntryPtr update[SL_MAX_LEVEL + 1] = {0};
236 int retcode = 0;
237
238 SLLocate(list, key, update);
239
240 *prev_key = *next_key = key;
241 *prev_value = *next_value = NULL;
242
243 if (update[0]) {
244 *prev_key = update[0]->key;
245 *prev_value = update[0]->value;
246 ++retcode;
247 if (update[0]->forward[0]) {
248 *next_key = update[0]->forward[0]->key;
249 *next_value = update[0]->forward[0]->value;
250 ++retcode;
251 }
252 }
253 return retcode;
254 }
255
drmSLNext(void * l,unsigned long * key,void ** value)256 int drmSLNext(void *l, unsigned long *key, void **value)
257 {
258 SkipListPtr list = (SkipListPtr)l;
259 SLEntryPtr entry;
260
261 if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
262
263 entry = list->p0;
264
265 if (entry) {
266 list->p0 = entry->forward[0];
267 *key = entry->key;
268 *value = entry->value;
269 return 1;
270 }
271 list->p0 = NULL;
272 return 0;
273 }
274
drmSLFirst(void * l,unsigned long * key,void ** value)275 int drmSLFirst(void *l, unsigned long *key, void **value)
276 {
277 SkipListPtr list = (SkipListPtr)l;
278
279 if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
280
281 list->p0 = list->head->forward[0];
282 return drmSLNext(list, key, value);
283 }
284
285 /* Dump internal data structures for debugging. */
drmSLDump(void * l)286 void drmSLDump(void *l)
287 {
288 SkipListPtr list = (SkipListPtr)l;
289 SLEntryPtr entry;
290 int i;
291
292 if (list->magic != SL_LIST_MAGIC) {
293 printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
294 list->magic, SL_LIST_MAGIC);
295 return;
296 }
297
298 printf("Level = %d, count = %d\n", list->level, list->count);
299 for (entry = list->head; entry; entry = entry->forward[0]) {
300 if (entry->magic != SL_ENTRY_MAGIC) {
301 printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
302 list->magic, SL_ENTRY_MAGIC);
303 }
304 printf("\nEntry %p <0x%08lx, %p> has %2d levels\n",
305 entry, entry->key, entry->value, entry->levels);
306 for (i = 0; i < entry->levels; i++) {
307 if (entry->forward[i]) {
308 printf(" %2d: %p <0x%08lx, %p>\n",
309 i,
310 entry->forward[i],
311 entry->forward[i]->key,
312 entry->forward[i]->value);
313 } else {
314 printf(" %2d: %p\n", i, entry->forward[i]);
315 }
316 }
317 }
318 }
319