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.
43 #ifdef HAVE_XORG_CONFIG_H
44 #include <xorg-config.h>
52 # include <sys/time.h>
58 # include "xf86_ansic.h"
67 #define SL_LIST_MAGIC 0xfacade00LU
68 #define SL_ENTRY_MAGIC 0x00fab1edLU
69 #define SL_FREED_MAGIC 0xdecea5edLU
70 #define SL_MAX_LEVEL 16
72 #define SL_RANDOM_SEED 0xc01055a1LU
75 #define SL_ALLOC malloc
77 #define SL_RANDOM_DECL static int state = 0;
78 #define SL_RANDOM_INIT(seed) if (!state) { srandom(seed); ++state; }
79 #define SL_RANDOM random()
81 #define SL_ALLOC drmMalloc
82 #define SL_FREE drmFree
83 #define SL_RANDOM_DECL static void *state = NULL
84 #define SL_RANDOM_INIT(seed) if (!state) state = drmRandomCreate(seed)
85 #define SL_RANDOM drmRandom(state)
89 typedef struct SLEntry {
90 unsigned long magic; /* SL_ENTRY_MAGIC */
94 struct SLEntry *forward[1]; /* variable sized array */
95 } SLEntry, *SLEntryPtr;
97 typedef struct SkipList {
98 unsigned long magic; /* SL_LIST_MAGIC */
102 SLEntryPtr p0; /* Position for iteration */
103 } SkipList, *SkipListPtr;
106 extern void *N(SLCreate)(void);
107 extern int N(SLDestroy)(void *l);
108 extern int N(SLLookup)(void *l, unsigned long key, void **value);
109 extern int N(SLInsert)(void *l, unsigned long key, void *value);
110 extern int N(SLDelete)(void *l, unsigned long key);
111 extern int N(SLNext)(void *l, unsigned long *key, void **value);
112 extern int N(SLFirst)(void *l, unsigned long *key, void **value);
113 extern void N(SLDump)(void *l);
114 extern int N(SLLookupNeighbors)(void *l, unsigned long key,
115 unsigned long *prev_key, void **prev_value,
116 unsigned long *next_key, void **next_value);
119 static SLEntryPtr SLCreateEntry(int max_level, unsigned long key, void *value)
123 if (max_level < 0 || max_level > SL_MAX_LEVEL) max_level = SL_MAX_LEVEL;
125 entry = SL_ALLOC(sizeof(*entry)
126 + (max_level + 1) * sizeof(entry->forward[0]));
127 if (!entry) return NULL;
128 entry->magic = SL_ENTRY_MAGIC;
130 entry->value = value;
131 entry->levels = max_level + 1;
136 static int SLRandomLevel(void)
141 SL_RANDOM_INIT(SL_RANDOM_SEED);
143 while ((SL_RANDOM & 0x01) && level < SL_MAX_LEVEL) ++level;
147 void *N(SLCreate)(void)
152 list = SL_ALLOC(sizeof(*list));
153 if (!list) return NULL;
154 list->magic = SL_LIST_MAGIC;
156 list->head = SLCreateEntry(SL_MAX_LEVEL, 0, NULL);
159 for (i = 0; i <= SL_MAX_LEVEL; i++) list->head->forward[i] = NULL;
164 int N(SLDestroy)(void *l)
166 SkipListPtr list = (SkipListPtr)l;
170 if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
172 for (entry = list->head; entry; entry = next) {
173 if (entry->magic != SL_ENTRY_MAGIC) return -1; /* Bad magic */
174 next = entry->forward[0];
175 entry->magic = SL_FREED_MAGIC;
179 list->magic = SL_FREED_MAGIC;
184 static SLEntryPtr SLLocate(void *l, unsigned long key, SLEntryPtr *update)
186 SkipListPtr list = (SkipListPtr)l;
190 if (list->magic != SL_LIST_MAGIC) return NULL;
192 for (i = list->level, entry = list->head; i >= 0; i--) {
193 while (entry->forward[i] && entry->forward[i]->key < key)
194 entry = entry->forward[i];
198 return entry->forward[0];
201 int N(SLInsert)(void *l, unsigned long key, void *value)
203 SkipListPtr list = (SkipListPtr)l;
205 SLEntryPtr update[SL_MAX_LEVEL + 1];
209 if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
211 entry = SLLocate(list, key, update);
213 if (entry && entry->key == key) return 1; /* Already in list */
216 level = SLRandomLevel();
217 if (level > list->level) {
218 level = ++list->level;
219 update[level] = list->head;
222 entry = SLCreateEntry(level, key, value);
224 /* Fix up forward pointers */
225 for (i = 0; i <= level; i++) {
226 entry->forward[i] = update[i]->forward[i];
227 update[i]->forward[i] = entry;
231 return 0; /* Added to table */
234 int N(SLDelete)(void *l, unsigned long key)
236 SkipListPtr list = (SkipListPtr)l;
237 SLEntryPtr update[SL_MAX_LEVEL + 1];
241 if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
243 entry = SLLocate(list, key, update);
245 if (!entry || entry->key != key) return 1; /* Not found */
247 /* Fix up forward pointers */
248 for (i = 0; i <= list->level; i++) {
249 if (update[i]->forward[i] == entry)
250 update[i]->forward[i] = entry->forward[i];
253 entry->magic = SL_FREED_MAGIC;
256 while (list->level && !list->head->forward[list->level]) --list->level;
261 int N(SLLookup)(void *l, unsigned long key, void **value)
263 SkipListPtr list = (SkipListPtr)l;
264 SLEntryPtr update[SL_MAX_LEVEL + 1];
267 entry = SLLocate(list, key, update);
269 if (entry && entry->key == key) {
277 int N(SLLookupNeighbors)(void *l, unsigned long key,
278 unsigned long *prev_key, void **prev_value,
279 unsigned long *next_key, void **next_value)
281 SkipListPtr list = (SkipListPtr)l;
282 SLEntryPtr update[SL_MAX_LEVEL + 1];
286 entry = SLLocate(list, key, update);
288 *prev_key = *next_key = key;
289 *prev_value = *next_value = NULL;
292 *prev_key = update[0]->key;
293 *prev_value = update[0]->value;
295 if (update[0]->forward[0]) {
296 *next_key = update[0]->forward[0]->key;
297 *next_value = update[0]->forward[0]->value;
304 int N(SLNext)(void *l, unsigned long *key, void **value)
306 SkipListPtr list = (SkipListPtr)l;
309 if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
314 list->p0 = entry->forward[0];
316 *value = entry->value;
323 int N(SLFirst)(void *l, unsigned long *key, void **value)
325 SkipListPtr list = (SkipListPtr)l;
327 if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
329 list->p0 = list->head->forward[0];
330 return N(SLNext)(list, key, value);
333 /* Dump internal data structures for debugging. */
334 void N(SLDump)(void *l)
336 SkipListPtr list = (SkipListPtr)l;
340 if (list->magic != SL_LIST_MAGIC) {
341 printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
342 list->magic, SL_LIST_MAGIC);
346 printf("Level = %d, count = %d\n", list->level, list->count);
347 for (entry = list->head; entry; entry = entry->forward[0]) {
348 if (entry->magic != SL_ENTRY_MAGIC) {
349 printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
350 list->magic, SL_ENTRY_MAGIC);
352 printf("\nEntry %p <0x%08lx, %p> has %2d levels\n",
353 entry, entry->key, entry->value, entry->levels);
354 for (i = 0; i < entry->levels; i++) {
355 if (entry->forward[i]) {
356 printf(" %2d: %p <0x%08lx, %p>\n",
359 entry->forward[i]->key,
360 entry->forward[i]->value);
362 printf(" %2d: %p\n", i, entry->forward[i]);
369 static void print(SkipListPtr list)
374 if (N(SLFirst)(list, &key, &value)) {
376 printf("key = %5lu, value = %p\n", key, value);
377 } while (N(SLNext)(list, &key, &value));
381 static double do_time(int size, int iter)
385 unsigned long keys[1000000];
386 unsigned long previous;
389 struct timeval start, stop;
393 SL_RANDOM_INIT(12345);
395 list = N(SLCreate)();
397 for (i = 0; i < size; i++) {
399 N(SLInsert)(list, keys[i], NULL);
403 if (N(SLFirst)(list, &key, &value)) {
405 if (key <= previous) {
406 printf( "%lu !< %lu\n", previous, key);
409 } while (N(SLNext)(list, &key, &value));
412 gettimeofday(&start, NULL);
413 for (j = 0; j < iter; j++) {
414 for (i = 0; i < size; i++) {
415 if (N(SLLookup)(list, keys[i], &value))
416 printf("Error %lu %d\n", keys[i], i);
419 gettimeofday(&stop, NULL);
421 usec = (double)(stop.tv_sec * 1000000 + stop.tv_usec
422 - start.tv_sec * 1000000 - start.tv_usec) / (size * iter);
424 printf("%0.2f microseconds for list length %d\n", usec, size);
431 static void print_neighbors(void *list, unsigned long key)
433 unsigned long prev_key = 0;
434 unsigned long next_key = 0;
439 retval = drmSLLookupNeighbors(list, key,
440 &prev_key, &prev_value,
441 &next_key, &next_value);
442 printf("Neighbors of %5lu: %d %5lu %5lu\n",
443 key, retval, prev_key, next_key);
449 double usec, usec2, usec3, usec4;
451 list = N(SLCreate)();
452 printf( "list at %p\n", list);
455 printf("\n==============================\n\n");
457 N(SLInsert)(list, 123, NULL);
458 N(SLInsert)(list, 213, NULL);
459 N(SLInsert)(list, 50, NULL);
461 printf("\n==============================\n\n");
463 print_neighbors(list, 0);
464 print_neighbors(list, 50);
465 print_neighbors(list, 51);
466 print_neighbors(list, 123);
467 print_neighbors(list, 200);
468 print_neighbors(list, 213);
469 print_neighbors(list, 256);
470 printf("\n==============================\n\n");
472 N(SLDelete)(list, 50);
474 printf("\n==============================\n\n");
478 printf("\n==============================\n\n");
480 usec = do_time(100, 10000);
481 usec2 = do_time(1000, 500);
482 printf("Table size increased by %0.2f, search time increased by %0.2f\n",
483 1000.0/100.0, usec2 / usec);
485 usec3 = do_time(10000, 50);
486 printf("Table size increased by %0.2f, search time increased by %0.2f\n",
487 10000.0/100.0, usec3 / usec);
489 usec4 = do_time(100000, 4);
490 printf("Table size increased by %0.2f, search time increased by %0.2f\n",
491 100000.0/100.0, usec4 / usec);