1 /* xf86drmSL.c -- Skip list support
2 * Created: Mon May 10 09:28:13 1999 by faith@precisioninsight.com
4 * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas.
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:
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
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.
26 * Authors: Rickard E. (Rik) Faith <faith@valinux.com>
28 * $XFree86: xc/programs/Xserver/hw/xfree86/os-support/linux/drm/xf86drmSL.c,v 1.3 2000/06/17 00:03:34 martin Exp $
32 * This file contains a straightforward skip list implementation.n
38 * [Pugh90] William Pugh. Skip Lists: A Probabilistic Alternative to
39 * Balanced Trees. CACM 33(6), June 1990, pp. 668-676.
48 # include <sys/time.h>
54 # include "xf86_ansic.h"
63 #define SL_LIST_MAGIC 0xfacade00LU
64 #define SL_ENTRY_MAGIC 0x00fab1edLU
65 #define SL_FREED_MAGIC 0xdecea5edLU
66 #define SL_MAX_LEVEL 16
68 #define SL_RANDOM_SEED 0xc01055a1LU
71 #define SL_ALLOC malloc
73 #define SL_RANDOM_DECL static int state = 0;
74 #define SL_RANDOM_INIT(seed) if (!state) { srandom(seed); ++state; }
75 #define SL_RANDOM random()
77 #define SL_ALLOC drmMalloc
78 #define SL_FREE drmFree
79 #define SL_RANDOM_DECL static void *state = NULL
80 #define SL_RANDOM_INIT(seed) if (!state) state = drmRandomCreate(seed)
81 #define SL_RANDOM drmRandom(state)
85 typedef struct SLEntry {
86 unsigned long magic; /* SL_ENTRY_MAGIC */
90 struct SLEntry *forward[1]; /* variable sized array */
91 } SLEntry, *SLEntryPtr;
93 typedef struct SkipList {
94 unsigned long magic; /* SL_LIST_MAGIC */
98 SLEntryPtr p0; /* Position for iteration */
99 } SkipList, *SkipListPtr;
102 extern void *N(SLCreate)(void);
103 extern int N(SLDestroy)(void *l);
104 extern int N(SLLookup)(void *l, unsigned long key, void **value);
105 extern int N(SLInsert)(void *l, unsigned long key, void *value);
106 extern int N(SLDelete)(void *l, unsigned long key);
107 extern int N(SLNext)(void *l, unsigned long *key, void **value);
108 extern int N(SLFirst)(void *l, unsigned long *key, void **value);
109 extern void N(SLDump)(void *l);
110 extern int N(SLLookupNeighbors)(void *l, unsigned long key,
111 unsigned long *prev_key, void **prev_value,
112 unsigned long *next_key, void **next_value);
115 static SLEntryPtr SLCreateEntry(int max_level, unsigned long key, void *value)
119 if (max_level < 0 || max_level > SL_MAX_LEVEL) max_level = SL_MAX_LEVEL;
121 entry = SL_ALLOC(sizeof(*entry)
122 + (max_level + 1) * sizeof(entry->forward[0]));
123 if (!entry) return NULL;
124 entry->magic = SL_ENTRY_MAGIC;
126 entry->value = value;
127 entry->levels = max_level + 1;
132 static int SLRandomLevel(void)
137 SL_RANDOM_INIT(SL_RANDOM_SEED);
139 while ((SL_RANDOM & 0x01) && level < SL_MAX_LEVEL) ++level;
143 void *N(SLCreate)(void)
148 list = SL_ALLOC(sizeof(*list));
149 if (!list) return NULL;
150 list->magic = SL_LIST_MAGIC;
152 list->head = SLCreateEntry(SL_MAX_LEVEL, 0, NULL);
155 for (i = 0; i <= SL_MAX_LEVEL; i++) list->head->forward[i] = NULL;
160 int N(SLDestroy)(void *l)
162 SkipListPtr list = (SkipListPtr)l;
166 if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
168 for (entry = list->head; entry; entry = next) {
169 if (entry->magic != SL_ENTRY_MAGIC) return -1; /* Bad magic */
170 next = entry->forward[0];
171 entry->magic = SL_FREED_MAGIC;
175 list->magic = SL_FREED_MAGIC;
180 static SLEntryPtr SLLocate(void *l, unsigned long key, SLEntryPtr *update)
182 SkipListPtr list = (SkipListPtr)l;
186 if (list->magic != SL_LIST_MAGIC) return NULL;
188 for (i = list->level, entry = list->head; i >= 0; i--) {
189 while (entry->forward[i] && entry->forward[i]->key < key)
190 entry = entry->forward[i];
194 return entry->forward[0];
197 int N(SLInsert)(void *l, unsigned long key, void *value)
199 SkipListPtr list = (SkipListPtr)l;
201 SLEntryPtr update[SL_MAX_LEVEL + 1];
205 if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
207 entry = SLLocate(list, key, update);
209 if (entry && entry->key == key) return 1; /* Already in list */
212 level = SLRandomLevel();
213 if (level > list->level) {
214 level = ++list->level;
215 update[level] = list->head;
218 entry = SLCreateEntry(level, key, value);
220 /* Fix up forward pointers */
221 for (i = 0; i <= level; i++) {
222 entry->forward[i] = update[i]->forward[i];
223 update[i]->forward[i] = entry;
227 return 0; /* Added to table */
230 int N(SLDelete)(void *l, unsigned long key)
232 SkipListPtr list = (SkipListPtr)l;
233 SLEntryPtr update[SL_MAX_LEVEL + 1];
237 if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
239 entry = SLLocate(list, key, update);
241 if (!entry || entry->key != key) return 1; /* Not found */
243 /* Fix up forward pointers */
244 for (i = 0; i <= list->level; i++) {
245 if (update[i]->forward[i] == entry)
246 update[i]->forward[i] = entry->forward[i];
249 entry->magic = SL_FREED_MAGIC;
252 while (list->level && !list->head->forward[list->level]) --list->level;
257 int N(SLLookup)(void *l, unsigned long key, void **value)
259 SkipListPtr list = (SkipListPtr)l;
260 SLEntryPtr update[SL_MAX_LEVEL + 1];
263 entry = SLLocate(list, key, update);
265 if (entry && entry->key == key) {
273 int N(SLLookupNeighbors)(void *l, unsigned long key,
274 unsigned long *prev_key, void **prev_value,
275 unsigned long *next_key, void **next_value)
277 SkipListPtr list = (SkipListPtr)l;
278 SLEntryPtr update[SL_MAX_LEVEL + 1];
282 entry = SLLocate(list, key, update);
284 *prev_key = *next_key = key;
285 *prev_value = *next_value = NULL;
288 *prev_key = update[0]->key;
289 *prev_value = update[0]->value;
291 if (update[0]->forward[0]) {
292 *next_key = update[0]->forward[0]->key;
293 *next_value = update[0]->forward[0]->value;
300 int N(SLNext)(void *l, unsigned long *key, void **value)
302 SkipListPtr list = (SkipListPtr)l;
305 if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
310 list->p0 = entry->forward[0];
312 *value = entry->value;
319 int N(SLFirst)(void *l, unsigned long *key, void **value)
321 SkipListPtr list = (SkipListPtr)l;
323 if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
325 list->p0 = list->head->forward[0];
326 return N(SLNext)(list, key, value);
329 /* Dump internal data structures for debugging. */
330 void N(SLDump)(void *l)
332 SkipListPtr list = (SkipListPtr)l;
336 if (list->magic != SL_LIST_MAGIC) {
337 printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
338 list->magic, SL_LIST_MAGIC);
342 printf("Level = %d, count = %d\n", list->level, list->count);
343 for (entry = list->head; entry; entry = entry->forward[0]) {
344 if (entry->magic != SL_ENTRY_MAGIC) {
345 printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
346 list->magic, SL_ENTRY_MAGIC);
348 printf("\nEntry %p <0x%08lx, %p> has %2d levels\n",
349 entry, entry->key, entry->value, entry->levels);
350 for (i = 0; i < entry->levels; i++) {
351 if (entry->forward[i]) {
352 printf(" %2d: %p <0x%08lx, %p>\n",
355 entry->forward[i]->key,
356 entry->forward[i]->value);
358 printf(" %2d: %p\n", i, entry->forward[i]);
365 static void print(SkipListPtr list)
370 if (N(SLFirst)(list, &key, &value)) {
372 printf("key = %5lu, value = %p\n", key, value);
373 } while (N(SLNext)(list, &key, &value));
377 static double do_time(int size, int iter)
381 unsigned long keys[1000000];
382 unsigned long previous;
385 struct timeval start, stop;
389 SL_RANDOM_INIT(12345);
391 list = N(SLCreate)();
393 for (i = 0; i < size; i++) {
395 N(SLInsert)(list, keys[i], NULL);
399 if (N(SLFirst)(list, &key, &value)) {
401 if (key <= previous) {
402 printf( "%lu !< %lu\n", previous, key);
405 } while (N(SLNext)(list, &key, &value));
408 gettimeofday(&start, NULL);
409 for (j = 0; j < iter; j++) {
410 for (i = 0; i < size; i++) {
411 if (N(SLLookup)(list, keys[i], &value))
412 printf("Error %lu %d\n", keys[i], i);
415 gettimeofday(&stop, NULL);
417 usec = (double)(stop.tv_sec * 1000000 + stop.tv_usec
418 - start.tv_sec * 1000000 - start.tv_usec) / (size * iter);
420 printf("%0.2f microseconds for list length %d\n", usec, size);
427 static void print_neighbors(void *list, unsigned long key)
429 unsigned long prev_key = 0;
430 unsigned long next_key = 0;
435 retval = drmSLLookupNeighbors(list, key,
436 &prev_key, &prev_value,
437 &next_key, &next_value);
438 printf("Neighbors of %5lu: %d %5lu %5lu\n",
439 key, retval, prev_key, next_key);
445 double usec, usec2, usec3, usec4;
447 list = N(SLCreate)();
448 printf( "list at %p\n", list);
451 printf("\n==============================\n\n");
453 N(SLInsert)(list, 123, NULL);
454 N(SLInsert)(list, 213, NULL);
455 N(SLInsert)(list, 50, NULL);
457 printf("\n==============================\n\n");
459 print_neighbors(list, 0);
460 print_neighbors(list, 50);
461 print_neighbors(list, 51);
462 print_neighbors(list, 123);
463 print_neighbors(list, 200);
464 print_neighbors(list, 213);
465 print_neighbors(list, 256);
466 printf("\n==============================\n\n");
468 N(SLDelete)(list, 50);
470 printf("\n==============================\n\n");
474 printf("\n==============================\n\n");
476 usec = do_time(100, 10000);
477 usec2 = do_time(1000, 500);
478 printf("Table size increased by %0.2f, search time increased by %0.2f\n",
479 1000.0/100.0, usec2 / usec);
481 usec3 = do_time(10000, 50);
482 printf("Table size increased by %0.2f, search time increased by %0.2f\n",
483 10000.0/100.0, usec3 / usec);
485 usec4 = do_time(100000, 4);
486 printf("Table size increased by %0.2f, search time increased by %0.2f\n",
487 100000.0/100.0, usec4 / usec);