xref: /third_party/libdrm/xf86drmSL.c (revision d722e3fb) 
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 "libdrm_macros.h"
45#include "xf86drm.h"
46
47#define SL_LIST_MAGIC  0xfacade00LU
48#define SL_ENTRY_MAGIC 0x00fab1edLU
49#define SL_FREED_MAGIC 0xdecea5edLU
50#define SL_MAX_LEVEL   16
51#define SL_RANDOM_SEED 0xc01055a1LU
52
53#define SL_RANDOM_DECL        static void *state = NULL
54#define SL_RANDOM_INIT(seed)  if (!state) state = drmRandomCreate(seed)
55#define SL_RANDOM             drmRandom(state)
56
57typedef struct SLEntry {
58    unsigned long     magic;	   /* SL_ENTRY_MAGIC */
59    unsigned long     key;
60    void              *value;
61    int               levels;
62    struct SLEntry    *forward[1]; /* variable sized array */
63} SLEntry, *SLEntryPtr;
64
65typedef struct SkipList {
66    unsigned long    magic;	/* SL_LIST_MAGIC */
67    int              level;
68    int              count;
69    SLEntryPtr       head;
70    SLEntryPtr       p0;	/* Position for iteration */
71} SkipList, *SkipListPtr;
72
73static SLEntryPtr SLCreateEntry(int max_level, unsigned long key, void *value)
74{
75    SLEntryPtr entry;
76
77    if (max_level < 0 || max_level > SL_MAX_LEVEL) max_level = SL_MAX_LEVEL;
78
79    entry         = drmMalloc(sizeof(*entry)
80			     + (max_level + 1) * sizeof(entry->forward[0]));
81    if (!entry) return NULL;
82    entry->magic  = SL_ENTRY_MAGIC;
83    entry->key    = key;
84    entry->value  = value;
85    entry->levels = max_level + 1;
86
87    return entry;
88}
89
90static int SLRandomLevel(void)
91{
92    int level = 1;
93    SL_RANDOM_DECL;
94
95    SL_RANDOM_INIT(SL_RANDOM_SEED);
96
97    while ((SL_RANDOM & 0x01) && level < SL_MAX_LEVEL) ++level;
98    return level;
99}
100
101drm_public void *drmSLCreate(void)
102{
103    SkipListPtr  list;
104    int          i;
105
106    list           = drmMalloc(sizeof(*list));
107    if (!list) return NULL;
108    list->magic    = SL_LIST_MAGIC;
109    list->level    = 0;
110    list->head     = SLCreateEntry(SL_MAX_LEVEL, 0, NULL);
111    list->count    = 0;
112
113    for (i = 0; i <= SL_MAX_LEVEL; i++) list->head->forward[i] = NULL;
114
115    return list;
116}
117
118drm_public int drmSLDestroy(void *l)
119{
120    SkipListPtr   list  = (SkipListPtr)l;
121    SLEntryPtr    entry;
122    SLEntryPtr    next;
123
124    if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
125
126    for (entry = list->head; entry; entry = next) {
127	if (entry->magic != SL_ENTRY_MAGIC) return -1; /* Bad magic */
128	next         = entry->forward[0];
129	entry->magic = SL_FREED_MAGIC;
130	drmFree(entry);
131    }
132
133    list->magic = SL_FREED_MAGIC;
134    drmFree(list);
135    return 0;
136}
137
138static SLEntryPtr SLLocate(void *l, unsigned long key, SLEntryPtr *update)
139{
140    SkipListPtr   list  = (SkipListPtr)l;
141    SLEntryPtr    entry;
142    int           i;
143
144    if (list->magic != SL_LIST_MAGIC) return NULL;
145
146    for (i = list->level, entry = list->head; i >= 0; i--) {
147	while (entry->forward[i] && entry->forward[i]->key < key)
148	    entry = entry->forward[i];
149	update[i] = entry;
150    }
151
152    return entry->forward[0];
153}
154
155drm_public int drmSLInsert(void *l, unsigned long key, void *value)
156{
157    SkipListPtr   list  = (SkipListPtr)l;
158    SLEntryPtr    entry;
159    SLEntryPtr    update[SL_MAX_LEVEL + 1];
160    int           level;
161    int           i;
162
163    if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
164
165    entry = SLLocate(list, key, update);
166
167    if (entry && entry->key == key) return 1; /* Already in list */
168
169
170    level = SLRandomLevel();
171    if (level > list->level) {
172	level = ++list->level;
173	update[level] = list->head;
174    }
175
176    entry = SLCreateEntry(level, key, value);
177
178				/* Fix up forward pointers */
179    for (i = 0; i <= level; i++) {
180	entry->forward[i]     = update[i]->forward[i];
181	update[i]->forward[i] = entry;
182    }
183
184    ++list->count;
185    return 0;			/* Added to table */
186}
187
188drm_public int drmSLDelete(void *l, unsigned long key)
189{
190    SkipListPtr   list = (SkipListPtr)l;
191    SLEntryPtr    update[SL_MAX_LEVEL + 1];
192    SLEntryPtr    entry;
193    int           i;
194
195    if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
196
197    entry = SLLocate(list, key, update);
198
199    if (!entry || entry->key != key) return 1; /* Not found */
200
201				/* Fix up forward pointers */
202    for (i = 0; i <= list->level; i++) {
203	if (update[i]->forward[i] == entry)
204	    update[i]->forward[i] = entry->forward[i];
205    }
206
207    entry->magic = SL_FREED_MAGIC;
208    drmFree(entry);
209
210    while (list->level && !list->head->forward[list->level]) --list->level;
211    --list->count;
212    return 0;
213}
214
215drm_public int drmSLLookup(void *l, unsigned long key, void **value)
216{
217    SkipListPtr   list = (SkipListPtr)l;
218    SLEntryPtr    update[SL_MAX_LEVEL + 1];
219    SLEntryPtr    entry;
220
221    entry = SLLocate(list, key, update);
222
223    if (entry && entry->key == key) {
224	*value = entry;
225	return 0;
226    }
227    *value = NULL;
228    return -1;
229}
230
231drm_public int drmSLLookupNeighbors(void *l, unsigned long key,
232                                    unsigned long *prev_key, void **prev_value,
233                                    unsigned long *next_key, void **next_value)
234{
235    SkipListPtr   list = (SkipListPtr)l;
236    SLEntryPtr    update[SL_MAX_LEVEL + 1] = {0};
237    int           retcode = 0;
238
239    SLLocate(list, key, update);
240
241    *prev_key   = *next_key   = key;
242    *prev_value = *next_value = NULL;
243
244    if (update[0]) {
245	*prev_key   = update[0]->key;
246	*prev_value = update[0]->value;
247	++retcode;
248	if (update[0]->forward[0]) {
249	    *next_key   = update[0]->forward[0]->key;
250	    *next_value = update[0]->forward[0]->value;
251	    ++retcode;
252	}
253    }
254    return retcode;
255}
256
257drm_public int drmSLNext(void *l, unsigned long *key, void **value)
258{
259    SkipListPtr   list = (SkipListPtr)l;
260    SLEntryPtr    entry;
261
262    if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
263
264    entry    = list->p0;
265
266    if (entry) {
267	list->p0 = entry->forward[0];
268	*key     = entry->key;
269	*value   = entry->value;
270	return 1;
271    }
272    list->p0 = NULL;
273    return 0;
274}
275
276drm_public int drmSLFirst(void *l, unsigned long *key, void **value)
277{
278    SkipListPtr   list = (SkipListPtr)l;
279
280    if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
281
282    list->p0 = list->head->forward[0];
283    return drmSLNext(list, key, value);
284}
285
286/* Dump internal data structures for debugging. */
287drm_public void drmSLDump(void *l)
288{
289    SkipListPtr   list = (SkipListPtr)l;
290    SLEntryPtr    entry;
291    int           i;
292
293    if (list->magic != SL_LIST_MAGIC) {
294	printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
295	       list->magic, SL_LIST_MAGIC);
296	return;
297    }
298
299    printf("Level = %d, count = %d\n", list->level, list->count);
300    for (entry = list->head; entry; entry = entry->forward[0]) {
301	if (entry->magic != SL_ENTRY_MAGIC) {
302	    printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
303		   list->magic, SL_ENTRY_MAGIC);
304	}
305	printf("\nEntry %p <0x%08lx, %p> has %2d levels\n",
306	       entry, entry->key, entry->value, entry->levels);
307	for (i = 0; i < entry->levels; i++) {
308	    if (entry->forward[i]) {
309		printf("   %2d: %p <0x%08lx, %p>\n",
310		       i,
311		       entry->forward[i],
312		       entry->forward[i]->key,
313		       entry->forward[i]->value);
314	    } else {
315		printf("   %2d: %p\n", i, entry->forward[i]);
316	    }
317	}
318    }
319}
320