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 SLEntryPtr entry; 269 int retcode = 0; 270 271 entry = SLLocate(list, key, update); 272 273 *prev_key = *next_key = key; 274 *prev_value = *next_value = NULL; 275 276 if (update[0]) { 277 *prev_key = update[0]->key; 278 *prev_value = update[0]->value; 279 ++retcode; 280 if (update[0]->forward[0]) { 281 *next_key = update[0]->forward[0]->key; 282 *next_value = update[0]->forward[0]->value; 283 ++retcode; 284 } 285 } 286 return retcode; 287 } 288 289 int drmSLNext(void *l, unsigned long *key, void **value) 290 { 291 SkipListPtr list = (SkipListPtr)l; 292 SLEntryPtr entry; 293 294 if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */ 295 296 entry = list->p0; 297 298 if (entry) { 299 list->p0 = entry->forward[0]; 300 *key = entry->key; 301 *value = entry->value; 302 return 1; 303 } 304 list->p0 = NULL; 305 return 0; 306 } 307 308 int drmSLFirst(void *l, unsigned long *key, void **value) 309 { 310 SkipListPtr list = (SkipListPtr)l; 311 312 if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */ 313 314 list->p0 = list->head->forward[0]; 315 return drmSLNext(list, key, value); 316 } 317 318 /* Dump internal data structures for debugging. */ 319 void drmSLDump(void *l) 320 { 321 SkipListPtr list = (SkipListPtr)l; 322 SLEntryPtr entry; 323 int i; 324 325 if (list->magic != SL_LIST_MAGIC) { 326 printf("Bad magic: 0x%08lx (expected 0x%08lx)\n", 327 list->magic, SL_LIST_MAGIC); 328 return; 329 } 330 331 printf("Level = %d, count = %d\n", list->level, list->count); 332 for (entry = list->head; entry; entry = entry->forward[0]) { 333 if (entry->magic != SL_ENTRY_MAGIC) { 334 printf("Bad magic: 0x%08lx (expected 0x%08lx)\n", 335 list->magic, SL_ENTRY_MAGIC); 336 } 337 printf("\nEntry %p <0x%08lx, %p> has %2d levels\n", 338 entry, entry->key, entry->value, entry->levels); 339 for (i = 0; i < entry->levels; i++) { 340 if (entry->forward[i]) { 341 printf(" %2d: %p <0x%08lx, %p>\n", 342 i, 343 entry->forward[i], 344 entry->forward[i]->key, 345 entry->forward[i]->value); 346 } else { 347 printf(" %2d: %p\n", i, entry->forward[i]); 348 } 349 } 350 } 351 } 352 353 #if SL_MAIN 354 static void print(SkipListPtr list) 355 { 356 unsigned long key; 357 void *value; 358 359 if (drmSLFirst(list, &key, &value)) { 360 do { 361 printf("key = %5lu, value = %p\n", key, value); 362 } while (drmSLNext(list, &key, &value)); 363 } 364 } 365 366 static double do_time(int size, int iter) 367 { 368 SkipListPtr list; 369 int i, j; 370 unsigned long keys[1000000]; 371 unsigned long previous; 372 unsigned long key; 373 void *value; 374 struct timeval start, stop; 375 double usec; 376 SL_RANDOM_DECL; 377 378 SL_RANDOM_INIT(12345); 379 380 list = drmSLCreate(); 381 382 for (i = 0; i < size; i++) { 383 keys[i] = SL_RANDOM; 384 drmSLInsert(list, keys[i], NULL); 385 } 386 387 previous = 0; 388 if (drmSLFirst(list, &key, &value)) { 389 do { 390 if (key <= previous) { 391 printf( "%lu !< %lu\n", previous, key); 392 } 393 previous = key; 394 } while (drmSLNext(list, &key, &value)); 395 } 396 397 gettimeofday(&start, NULL); 398 for (j = 0; j < iter; j++) { 399 for (i = 0; i < size; i++) { 400 if (drmSLLookup(list, keys[i], &value)) 401 printf("Error %lu %d\n", keys[i], i); 402 } 403 } 404 gettimeofday(&stop, NULL); 405 406 usec = (double)(stop.tv_sec * 1000000 + stop.tv_usec 407 - start.tv_sec * 1000000 - start.tv_usec) / (size * iter); 408 409 printf("%0.2f microseconds for list length %d\n", usec, size); 410 411 drmSLDestroy(list); 412 413 return usec; 414 } 415 416 static void print_neighbors(void *list, unsigned long key) 417 { 418 unsigned long prev_key = 0; 419 unsigned long next_key = 0; 420 void *prev_value; 421 void *next_value; 422 int retval; 423 424 retval = drmSLLookupNeighbors(list, key, 425 &prev_key, &prev_value, 426 &next_key, &next_value); 427 printf("Neighbors of %5lu: %d %5lu %5lu\n", 428 key, retval, prev_key, next_key); 429 } 430 431 int main(void) 432 { 433 SkipListPtr list; 434 double usec, usec2, usec3, usec4; 435 436 list = drmSLCreate(); 437 printf( "list at %p\n", list); 438 439 print(list); 440 printf("\n==============================\n\n"); 441 442 drmSLInsert(list, 123, NULL); 443 drmSLInsert(list, 213, NULL); 444 drmSLInsert(list, 50, NULL); 445 print(list); 446 printf("\n==============================\n\n"); 447 448 print_neighbors(list, 0); 449 print_neighbors(list, 50); 450 print_neighbors(list, 51); 451 print_neighbors(list, 123); 452 print_neighbors(list, 200); 453 print_neighbors(list, 213); 454 print_neighbors(list, 256); 455 printf("\n==============================\n\n"); 456 457 drmSLDelete(list, 50); 458 print(list); 459 printf("\n==============================\n\n"); 460 461 drmSLDump(list); 462 drmSLDestroy(list); 463 printf("\n==============================\n\n"); 464 465 usec = do_time(100, 10000); 466 usec2 = do_time(1000, 500); 467 printf("Table size increased by %0.2f, search time increased by %0.2f\n", 468 1000.0/100.0, usec2 / usec); 469 470 usec3 = do_time(10000, 50); 471 printf("Table size increased by %0.2f, search time increased by %0.2f\n", 472 10000.0/100.0, usec3 / usec); 473 474 usec4 = do_time(100000, 4); 475 printf("Table size increased by %0.2f, search time increased by %0.2f\n", 476 100000.0/100.0, usec4 / usec); 477 478 return 0; 479 } 480 #endif 481
