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 #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 74 typedef 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 82 typedef 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 91 extern void *drmSLCreate(void); 92 extern int drmSLDestroy(void *l); 93 extern int drmSLLookup(void *l, unsigned long key, void **value); 94 extern int drmSLInsert(void *l, unsigned long key, void *value); 95 extern int drmSLDelete(void *l, unsigned long key); 96 extern int drmSLNext(void *l, unsigned long *key, void **value); 97 extern int drmSLFirst(void *l, unsigned long *key, void **value); 98 extern void drmSLDump(void *l); 99 extern 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 104 static 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 121 static 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 132 void *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 149 int 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 169 static 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 186 int 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 219 int 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 246 int 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 262 int 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 286 int 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 305 int 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. */ 316 void 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 351 static 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 363 static 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 413 static 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 428 int 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
