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