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>
53 # include "xf86_ansic.h"
62 #define SL_LIST_MAGIC 0xfacade00LU
63 #define SL_ENTRY_MAGIC 0x00fab1edLU
64 #define SL_FREED_MAGIC 0xdecea5edLU
65 #define SL_MAX_LEVEL 16
67 #define SL_RANDOM_SEED 0xc01055a1LU
70 #define SL_ALLOC malloc
72 #define SL_RANDOM_DECL static int state = 0;
73 #define SL_RANDOM_INIT(seed) if (!state) { srandom(seed); ++state; }
74 #define SL_RANDOM random()
76 #define SL_ALLOC drmMalloc
77 #define SL_FREE drmFree
78 #define SL_RANDOM_DECL static void *state = NULL
79 #define SL_RANDOM_INIT(seed) if (!state) state = drmRandomCreate(seed)
80 #define SL_RANDOM drmRandom(state)
84 typedef struct SLEntry
{
85 unsigned long magic
; /* SL_ENTRY_MAGIC */
89 struct SLEntry
*forward
[1]; /* variable sized array */
90 } SLEntry
, *SLEntryPtr
;
92 typedef struct SkipList
{
93 unsigned long magic
; /* SL_LIST_MAGIC */
97 SLEntryPtr p0
; /* Position for iteration */
98 } SkipList
, *SkipListPtr
;
101 extern void *N(SLCreate
)(void);
102 extern int N(SLDestroy
)(void *l
);
103 extern int N(SLLookup
)(void *l
, unsigned long key
, void **value
);
104 extern int N(SLInsert
)(void *l
, unsigned long key
, void *value
);
105 extern int N(SLDelete
)(void *l
, unsigned long key
);
106 extern int N(SLNext
)(void *l
, unsigned long *key
, void **value
);
107 extern int N(SLFirst
)(void *l
, unsigned long *key
, void **value
);
108 extern void N(SLDump
)(void *l
);
109 extern int N(SLLookupNeighbors
)(void *l
, unsigned long key
,
110 unsigned long *prev_key
, void **prev_value
,
111 unsigned long *next_key
, void **next_value
);
114 static SLEntryPtr
SLCreateEntry(int max_level
, unsigned long key
, void *value
)
118 if (max_level
< 0 || max_level
> SL_MAX_LEVEL
) max_level
= SL_MAX_LEVEL
;
120 entry
= SL_ALLOC(sizeof(*entry
)
121 + (max_level
+ 1) * sizeof(entry
->forward
[0]));
122 if (!entry
) return NULL
;
123 entry
->magic
= SL_ENTRY_MAGIC
;
125 entry
->value
= value
;
126 entry
->levels
= max_level
+ 1;
131 static int SLRandomLevel(void)
136 SL_RANDOM_INIT(SL_RANDOM_SEED
);
138 while ((SL_RANDOM
& 0x01) && level
< SL_MAX_LEVEL
) ++level
;
142 void *N(SLCreate
)(void)
147 list
= SL_ALLOC(sizeof(*list
));
148 if (!list
) return NULL
;
149 list
->magic
= SL_LIST_MAGIC
;
151 list
->head
= SLCreateEntry(SL_MAX_LEVEL
, 0, NULL
);
154 for (i
= 0; i
<= SL_MAX_LEVEL
; i
++) list
->head
->forward
[i
] = NULL
;
159 int N(SLDestroy
)(void *l
)
161 SkipListPtr list
= (SkipListPtr
)l
;
165 if (list
->magic
!= SL_LIST_MAGIC
) return -1; /* Bad magic */
167 for (entry
= list
->head
; entry
; entry
= next
) {
168 if (entry
->magic
!= SL_ENTRY_MAGIC
) return -1; /* Bad magic */
169 next
= entry
->forward
[0];
170 entry
->magic
= SL_FREED_MAGIC
;
174 list
->magic
= SL_FREED_MAGIC
;
179 static SLEntryPtr
SLLocate(void *l
, unsigned long key
, SLEntryPtr
*update
)
181 SkipListPtr list
= (SkipListPtr
)l
;
185 if (list
->magic
!= SL_LIST_MAGIC
) return NULL
;
187 for (i
= list
->level
, entry
= list
->head
; i
>= 0; i
--) {
188 while (entry
->forward
[i
] && entry
->forward
[i
]->key
< key
)
189 entry
= entry
->forward
[i
];
193 return entry
->forward
[0];
196 int N(SLInsert
)(void *l
, unsigned long key
, void *value
)
198 SkipListPtr list
= (SkipListPtr
)l
;
200 SLEntryPtr update
[SL_MAX_LEVEL
+ 1];
204 if (list
->magic
!= SL_LIST_MAGIC
) return -1; /* Bad magic */
206 entry
= SLLocate(list
, key
, update
);
208 if (entry
&& entry
->key
== key
) return 1; /* Already in list */
211 level
= SLRandomLevel();
212 if (level
> list
->level
) {
213 level
= ++list
->level
;
214 update
[level
] = list
->head
;
217 entry
= SLCreateEntry(level
, key
, value
);
219 /* Fix up forward pointers */
220 for (i
= 0; i
<= level
; i
++) {
221 entry
->forward
[i
] = update
[i
]->forward
[i
];
222 update
[i
]->forward
[i
] = entry
;
226 return 0; /* Added to table */
229 int N(SLDelete
)(void *l
, unsigned long key
)
231 SkipListPtr list
= (SkipListPtr
)l
;
232 SLEntryPtr update
[SL_MAX_LEVEL
+ 1];
236 if (list
->magic
!= SL_LIST_MAGIC
) return -1; /* Bad magic */
238 entry
= SLLocate(list
, key
, update
);
240 if (!entry
|| entry
->key
!= key
) return 1; /* Not found */
242 /* Fix up forward pointers */
243 for (i
= 0; i
<= list
->level
; i
++) {
244 if (update
[i
]->forward
[i
] == entry
)
245 update
[i
]->forward
[i
] = entry
->forward
[i
];
248 entry
->magic
= SL_FREED_MAGIC
;
251 while (list
->level
&& !list
->head
->forward
[list
->level
]) --list
->level
;
256 int N(SLLookup
)(void *l
, unsigned long key
, void **value
)
258 SkipListPtr list
= (SkipListPtr
)l
;
259 SLEntryPtr update
[SL_MAX_LEVEL
+ 1];
262 entry
= SLLocate(list
, key
, update
);
264 if (entry
&& entry
->key
== key
) {
272 int N(SLLookupNeighbors
)(void *l
, unsigned long key
,
273 unsigned long *prev_key
, void **prev_value
,
274 unsigned long *next_key
, void **next_value
)
276 SkipListPtr list
= (SkipListPtr
)l
;
277 SLEntryPtr update
[SL_MAX_LEVEL
+ 1];
281 entry
= SLLocate(list
, key
, update
);
283 *prev_key
= *next_key
= key
;
284 *prev_value
= *next_value
= NULL
;
287 *prev_key
= update
[0]->key
;
288 *prev_value
= update
[0]->value
;
290 if (update
[0]->forward
[0]) {
291 *next_key
= update
[0]->forward
[0]->key
;
292 *next_value
= update
[0]->forward
[0]->value
;
299 int N(SLNext
)(void *l
, unsigned long *key
, void **value
)
301 SkipListPtr list
= (SkipListPtr
)l
;
304 if (list
->magic
!= SL_LIST_MAGIC
) return -1; /* Bad magic */
309 list
->p0
= entry
->forward
[0];
311 *value
= entry
->value
;
318 int N(SLFirst
)(void *l
, unsigned long *key
, void **value
)
320 SkipListPtr list
= (SkipListPtr
)l
;
322 if (list
->magic
!= SL_LIST_MAGIC
) return -1; /* Bad magic */
324 list
->p0
= list
->head
->forward
[0];
325 return N(SLNext
)(list
, key
, value
);
328 /* Dump internal data structures for debugging. */
329 void N(SLDump
)(void *l
)
331 SkipListPtr list
= (SkipListPtr
)l
;
335 if (list
->magic
!= SL_LIST_MAGIC
) {
336 printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
337 list
->magic
, SL_LIST_MAGIC
);
341 printf("Level = %d, count = %d\n", list
->level
, list
->count
);
342 for (entry
= list
->head
; entry
; entry
= entry
->forward
[0]) {
343 if (entry
->magic
!= SL_ENTRY_MAGIC
) {
344 printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
345 list
->magic
, SL_ENTRY_MAGIC
);
347 printf("\nEntry %p <0x%08lx, %p> has %2d levels\n",
348 entry
, entry
->key
, entry
->value
, entry
->levels
);
349 for (i
= 0; i
< entry
->levels
; i
++) {
350 if (entry
->forward
[i
]) {
351 printf(" %2d: %p <0x%08lx, %p>\n",
354 entry
->forward
[i
]->key
,
355 entry
->forward
[i
]->value
);
357 printf(" %2d: %p\n", i
, entry
->forward
[i
]);
364 static void print(SkipListPtr list
)
369 if (N(SLFirst
)(list
, &key
, &value
)) {
371 printf("key = %5lu, value = %p\n", key
, value
);
372 } while (N(SLNext
)(list
, &key
, &value
));
376 static double do_time(int size
, int iter
)
380 unsigned long keys
[1000000];
381 unsigned long previous
;
384 struct timeval start
, stop
;
388 SL_RANDOM_INIT(12345);
390 list
= N(SLCreate
)();
392 for (i
= 0; i
< size
; i
++) {
394 N(SLInsert
)(list
, keys
[i
], NULL
);
398 if (N(SLFirst
)(list
, &key
, &value
)) {
400 if (key
<= previous
) {
401 printf( "%lu !< %lu\n", previous
, key
);
404 } while (N(SLNext
)(list
, &key
, &value
));
407 gettimeofday(&start
, NULL
);
408 for (j
= 0; j
< iter
; j
++) {
409 for (i
= 0; i
< size
; i
++) {
410 if (N(SLLookup
)(list
, keys
[i
], &value
))
411 printf("Error %lu %d\n", keys
[i
], i
);
414 gettimeofday(&stop
, NULL
);
416 usec
= (double)(stop
.tv_sec
* 1000000 + stop
.tv_usec
417 - start
.tv_sec
* 1000000 - start
.tv_usec
) / (size
* iter
);
419 printf("%0.2f microseconds for list length %d\n", usec
, size
);
426 static void print_neighbors(void *list
, unsigned long key
)
428 unsigned long prev_key
= 0;
429 unsigned long next_key
= 0;
434 retval
= drmSLLookupNeighbors(list
, key
,
435 &prev_key
, &prev_value
,
436 &next_key
, &next_value
);
437 printf("Neighbors of %5lu: %d %5lu %5lu\n",
438 key
, retval
, prev_key
, next_key
);
444 double usec
, usec2
, usec3
, usec4
;
446 list
= N(SLCreate
)();
447 printf( "list at %p\n", list
);
450 printf("\n==============================\n\n");
452 N(SLInsert
)(list
, 123, NULL
);
453 N(SLInsert
)(list
, 213, NULL
);
454 N(SLInsert
)(list
, 50, NULL
);
456 printf("\n==============================\n\n");
458 print_neighbors(list
, 0);
459 print_neighbors(list
, 50);
460 print_neighbors(list
, 51);
461 print_neighbors(list
, 123);
462 print_neighbors(list
, 200);
463 print_neighbors(list
, 213);
464 print_neighbors(list
, 256);
465 printf("\n==============================\n\n");
467 N(SLDelete
)(list
, 50);
469 printf("\n==============================\n\n");
473 printf("\n==============================\n\n");
475 usec
= do_time(100, 10000);
476 usec2
= do_time(1000, 500);
477 printf("Table size increased by %0.2f, search time increased by %0.2f\n",
478 1000.0/100.0, usec2
/ usec
);
480 usec3
= do_time(10000, 50);
481 printf("Table size increased by %0.2f, search time increased by %0.2f\n",
482 10000.0/100.0, usec3
/ usec
);
484 usec4
= do_time(100000, 4);
485 printf("Table size increased by %0.2f, search time increased by %0.2f\n",
486 100000.0/100.0, usec4
/ usec
);