1 /* xf86drmSL.c -- Skip list support 2 * Created: Mon May 10 09:28:13 1999 by faith (at) 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 (at) 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 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 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 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 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 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 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 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 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 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 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 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. */ 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
