xf86drmSL.c revision e4a519635f75bde38aeb5b09f2ff4efbf73453e9 
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#define SL_MAIN 0
45
46#if !SL_MAIN
47# include "xf86drm.h"
48#else
49# include <sys/time.h>
50#endif
51
52#define SL_LIST_MAGIC  0xfacade00LU
53#define SL_ENTRY_MAGIC 0x00fab1edLU
54#define SL_FREED_MAGIC 0xdecea5edLU
55#define SL_MAX_LEVEL   16
56#define SL_DEBUG       0
57#define SL_RANDOM_SEED 0xc01055a1LU
58
59#if SL_MAIN
60#define SL_ALLOC malloc
61#define SL_FREE  free
62#define SL_RANDOM_DECL        static int state = 0;
63#define SL_RANDOM_INIT(seed)  if (!state) { srandom(seed); ++state; }
64#define SL_RANDOM             random()
65#else
66#define SL_ALLOC drmMalloc
67#define SL_FREE  drmFree
68#define SL_RANDOM_DECL        static void *state = NULL
69#define SL_RANDOM_INIT(seed)  if (!state) state = drmRandomCreate(seed)
70#define SL_RANDOM             drmRandom(state)
71
72#endif
73
74typedef struct SLEntry {
75    unsigned long     magic;	   /* SL_ENTRY_MAGIC */
76    unsigned long     key;
77    void              *value;
78    int               levels;
79    struct SLEntry    *forward[1]; /* variable sized array */
80} SLEntry, *SLEntryPtr;
81
82typedef struct SkipList {
83    unsigned long    magic;	/* SL_LIST_MAGIC */
84    int              level;
85    int              count;
86    SLEntryPtr       head;
87    SLEntryPtr       p0;	/* Position for iteration */
88} SkipList, *SkipListPtr;
89
90#if SL_MAIN
91extern void *drmSLCreate(void);
92extern int  drmSLDestroy(void *l);
93extern int  drmSLLookup(void *l, unsigned long key, void **value);
94extern int  drmSLInsert(void *l, unsigned long key, void *value);
95extern int  drmSLDelete(void *l, unsigned long key);
96extern int  drmSLNext(void *l, unsigned long *key, void **value);
97extern int  drmSLFirst(void *l, unsigned long *key, void **value);
98extern void drmSLDump(void *l);
99extern int  drmSLLookupNeighbors(void *l, unsigned long key,
100				 unsigned long *prev_key, void **prev_value,
101				 unsigned long *next_key, void **next_value);
102#endif
103
104static SLEntryPtr SLCreateEntry(int max_level, unsigned long key, void *value)
105{
106    SLEntryPtr entry;
107
108    if (max_level < 0 || max_level > SL_MAX_LEVEL) max_level = SL_MAX_LEVEL;
109
110    entry         = SL_ALLOC(sizeof(*entry)
111			     + (max_level + 1) * sizeof(entry->forward[0]));
112    if (!entry) return NULL;
113    entry->magic  = SL_ENTRY_MAGIC;
114    entry->key    = key;
115    entry->value  = value;
116    entry->levels = max_level + 1;
117
118    return entry;
119}
120
121static int SLRandomLevel(void)
122{
123    int level = 1;
124    SL_RANDOM_DECL;
125
126    SL_RANDOM_INIT(SL_RANDOM_SEED);
127
128    while ((SL_RANDOM & 0x01) && level < SL_MAX_LEVEL) ++level;
129    return level;
130}
131
132void *drmSLCreate(void)
133{
134    SkipListPtr  list;
135    int          i;
136
137    list           = SL_ALLOC(sizeof(*list));
138    if (!list) return NULL;
139    list->magic    = SL_LIST_MAGIC;
140    list->level    = 0;
141    list->head     = SLCreateEntry(SL_MAX_LEVEL, 0, NULL);
142    list->count    = 0;
143
144    for (i = 0; i <= SL_MAX_LEVEL; i++) list->head->forward[i] = NULL;
145
146    return list;
147}
148
149int drmSLDestroy(void *l)
150{
151    SkipListPtr   list  = (SkipListPtr)l;
152    SLEntryPtr    entry;
153    SLEntryPtr    next;
154
155    if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
156
157    for (entry = list->head; entry; entry = next) {
158	if (entry->magic != SL_ENTRY_MAGIC) return -1; /* Bad magic */
159	next         = entry->forward[0];
160	entry->magic = SL_FREED_MAGIC;
161	SL_FREE(entry);
162    }
163
164    list->magic = SL_FREED_MAGIC;
165    SL_FREE(list);
166    return 0;
167}
168
169static SLEntryPtr SLLocate(void *l, unsigned long key, SLEntryPtr *update)
170{
171    SkipListPtr   list  = (SkipListPtr)l;
172    SLEntryPtr    entry;
173    int           i;
174
175    if (list->magic != SL_LIST_MAGIC) return NULL;
176
177    for (i = list->level, entry = list->head; i >= 0; i--) {
178	while (entry->forward[i] && entry->forward[i]->key < key)
179	    entry = entry->forward[i];
180	update[i] = entry;
181    }
182
183    return entry->forward[0];
184}
185
186int drmSLInsert(void *l, unsigned long key, void *value)
187{
188    SkipListPtr   list  = (SkipListPtr)l;
189    SLEntryPtr    entry;
190    SLEntryPtr    update[SL_MAX_LEVEL + 1];
191    int           level;
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; /* Already in list */
199
200
201    level = SLRandomLevel();
202    if (level > list->level) {
203	level = ++list->level;
204	update[level] = list->head;
205    }
206
207    entry = SLCreateEntry(level, key, value);
208
209				/* Fix up forward pointers */
210    for (i = 0; i <= level; i++) {
211	entry->forward[i]     = update[i]->forward[i];
212	update[i]->forward[i] = entry;
213    }
214
215    ++list->count;
216    return 0;			/* Added to table */
217}
218
219int drmSLDelete(void *l, unsigned long key)
220{
221    SkipListPtr   list = (SkipListPtr)l;
222    SLEntryPtr    update[SL_MAX_LEVEL + 1];
223    SLEntryPtr    entry;
224    int           i;
225
226    if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
227
228    entry = SLLocate(list, key, update);
229
230    if (!entry || entry->key != key) return 1; /* Not found */
231
232				/* Fix up forward pointers */
233    for (i = 0; i <= list->level; i++) {
234	if (update[i]->forward[i] == entry)
235	    update[i]->forward[i] = entry->forward[i];
236    }
237
238    entry->magic = SL_FREED_MAGIC;
239    SL_FREE(entry);
240
241    while (list->level && !list->head->forward[list->level]) --list->level;
242    --list->count;
243    return 0;
244}
245
246int drmSLLookup(void *l, unsigned long key, void **value)
247{
248    SkipListPtr   list = (SkipListPtr)l;
249    SLEntryPtr    update[SL_MAX_LEVEL + 1];
250    SLEntryPtr    entry;
251
252    entry = SLLocate(list, key, update);
253
254    if (entry && entry->key == key) {
255	*value = entry;
256	return 0;
257    }
258    *value = NULL;
259    return -1;
260}
261
262int drmSLLookupNeighbors(void *l, unsigned long key,
263			 unsigned long *prev_key, void **prev_value,
264			 unsigned long *next_key, void **next_value)
265{
266    SkipListPtr   list = (SkipListPtr)l;
267    SLEntryPtr    update[SL_MAX_LEVEL + 1];
268    int           retcode = 0;
269
270    *prev_key   = *next_key   = key;
271    *prev_value = *next_value = NULL;
272
273    if (update[0]) {
274	*prev_key   = update[0]->key;
275	*prev_value = update[0]->value;
276	++retcode;
277	if (update[0]->forward[0]) {
278	    *next_key   = update[0]->forward[0]->key;
279	    *next_value = update[0]->forward[0]->value;
280	    ++retcode;
281	}
282    }
283    return retcode;
284}
285
286int drmSLNext(void *l, unsigned long *key, void **value)
287{
288    SkipListPtr   list = (SkipListPtr)l;
289    SLEntryPtr    entry;
290
291    if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
292
293    entry    = list->p0;
294
295    if (entry) {
296	list->p0 = entry->forward[0];
297	*key     = entry->key;
298	*value   = entry->value;
299	return 1;
300    }
301    list->p0 = NULL;
302    return 0;
303}
304
305int drmSLFirst(void *l, unsigned long *key, void **value)
306{
307    SkipListPtr   list = (SkipListPtr)l;
308
309    if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
310
311    list->p0 = list->head->forward[0];
312    return drmSLNext(list, key, value);
313}
314
315/* Dump internal data structures for debugging. */
316void drmSLDump(void *l)
317{
318    SkipListPtr   list = (SkipListPtr)l;
319    SLEntryPtr    entry;
320    int           i;
321
322    if (list->magic != SL_LIST_MAGIC) {
323	printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
324	       list->magic, SL_LIST_MAGIC);
325	return;
326    }
327
328    printf("Level = %d, count = %d\n", list->level, list->count);
329    for (entry = list->head; entry; entry = entry->forward[0]) {
330	if (entry->magic != SL_ENTRY_MAGIC) {
331	    printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
332		   list->magic, SL_ENTRY_MAGIC);
333	}
334	printf("\nEntry %p <0x%08lx, %p> has %2d levels\n",
335	       entry, entry->key, entry->value, entry->levels);
336	for (i = 0; i < entry->levels; i++) {
337	    if (entry->forward[i]) {
338		printf("   %2d: %p <0x%08lx, %p>\n",
339		       i,
340		       entry->forward[i],
341		       entry->forward[i]->key,
342		       entry->forward[i]->value);
343	    } else {
344		printf("   %2d: %p\n", i, entry->forward[i]);
345	    }
346	}
347    }
348}
349
350#if SL_MAIN
351static void print(SkipListPtr list)
352{
353    unsigned long key;
354    void          *value;
355
356    if (drmSLFirst(list, &key, &value)) {
357	do {
358	    printf("key = %5lu, value = %p\n", key, value);
359	} while (drmSLNext(list, &key, &value));
360    }
361}
362
363static double do_time(int size, int iter)
364{
365    SkipListPtr    list;
366    int            i, j;
367    unsigned long  keys[1000000];
368    unsigned long  previous;
369    unsigned long  key;
370    void           *value;
371    struct timeval start, stop;
372    double         usec;
373    SL_RANDOM_DECL;
374
375    SL_RANDOM_INIT(12345);
376
377    list = drmSLCreate();
378
379    for (i = 0; i < size; i++) {
380	keys[i] = SL_RANDOM;
381	drmSLInsert(list, keys[i], NULL);
382    }
383
384    previous = 0;
385    if (drmSLFirst(list, &key, &value)) {
386	do {
387	    if (key <= previous) {
388		printf( "%lu !< %lu\n", previous, key);
389	    }
390	    previous = key;
391	} while (drmSLNext(list, &key, &value));
392    }
393
394    gettimeofday(&start, NULL);
395    for (j = 0; j < iter; j++) {
396	for (i = 0; i < size; i++) {
397	    if (drmSLLookup(list, keys[i], &value))
398		printf("Error %lu %d\n", keys[i], i);
399	}
400    }
401    gettimeofday(&stop, NULL);
402
403    usec = (double)(stop.tv_sec * 1000000 + stop.tv_usec
404		    - start.tv_sec * 1000000 - start.tv_usec) / (size * iter);
405
406    printf("%0.2f microseconds for list length %d\n", usec, size);
407
408    drmSLDestroy(list);
409
410    return usec;
411}
412
413static void print_neighbors(void *list, unsigned long key)
414{
415    unsigned long prev_key = 0;
416    unsigned long next_key = 0;
417    void          *prev_value;
418    void          *next_value;
419    int           retval;
420
421    retval = drmSLLookupNeighbors(list, key,
422				  &prev_key, &prev_value,
423				  &next_key, &next_value);
424    printf("Neighbors of %5lu: %d %5lu %5lu\n",
425	   key, retval, prev_key, next_key);
426}
427
428int main(void)
429{
430    SkipListPtr    list;
431    double         usec, usec2, usec3, usec4;
432
433    list = drmSLCreate();
434    printf( "list at %p\n", list);
435
436    print(list);
437    printf("\n==============================\n\n");
438
439    drmSLInsert(list, 123, NULL);
440    drmSLInsert(list, 213, NULL);
441    drmSLInsert(list, 50, NULL);
442    print(list);
443    printf("\n==============================\n\n");
444
445    print_neighbors(list, 0);
446    print_neighbors(list, 50);
447    print_neighbors(list, 51);
448    print_neighbors(list, 123);
449    print_neighbors(list, 200);
450    print_neighbors(list, 213);
451    print_neighbors(list, 256);
452    printf("\n==============================\n\n");
453
454    drmSLDelete(list, 50);
455    print(list);
456    printf("\n==============================\n\n");
457
458    drmSLDump(list);
459    drmSLDestroy(list);
460    printf("\n==============================\n\n");
461
462    usec  = do_time(100, 10000);
463    usec2 = do_time(1000, 500);
464    printf("Table size increased by %0.2f, search time increased by %0.2f\n",
465	   1000.0/100.0, usec2 / usec);
466
467    usec3 = do_time(10000, 50);
468    printf("Table size increased by %0.2f, search time increased by %0.2f\n",
469	   10000.0/100.0, usec3 / usec);
470
471    usec4 = do_time(100000, 4);
472    printf("Table size increased by %0.2f, search time increased by %0.2f\n",
473	   100000.0/100.0, usec4 / usec);
474
475    return 0;
476}
477#endif
478