libdrm/xf86drmSL.c

   1 /* xf86drmSL.c -- Skip list support
   2  * Created: Mon May 10 09:28:13 1999 by faith@precisioninsight.com
   3  * Revised: Thu Jun  3 16:13:01 1999 by faith@precisioninsight.com
   4  *
   5  * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas.
   6  * All Rights Reserved.
   7  *
   8  * Permission is hereby granted, free of charge, to any person obtaining a
   9  * copy of this software and associated documentation files (the "Software"),
  10  * to deal in the Software without restriction, including without limitation
  11  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
  12  * and/or sell copies of the Software, and to permit persons to whom the
  13  * Software is furnished to do so, subject to the following conditions:
  14  *
  15  * The above copyright notice and this permission notice (including the next
  16  * paragraph) shall be included in all copies or substantial portions of the
  17  * Software.
  18  *
  19  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  20  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  21  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  22  * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
  23  * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
  24  * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  25  * DEALINGS IN THE SOFTWARE.
  26  *
  27  * $XFree86: xc/programs/Xserver/hw/xfree86/os-support/linux/drm/xf86drmSL.c,v 1.2 2000/02/23 04:47:24 martin Exp $
  28  *
  29  * DESCRIPTION
  30  *
  31  * This file contains a straightforward skip list implementation.n
  32  *
  33  * FUTURE ENHANCEMENTS
  34  *
  35  * REFERENCES
  36  *
  37  * [Pugh90] William Pugh.  Skip Lists: A Probabilistic Alternative to
  38  * Balanced Trees. CACM 33(6), June 1990, pp. 668-676.
  39  *
  40  */
  41
  42 #define SL_MAIN 0
  43
  44 #if SL_MAIN
  45 # include <stdio.h>
  46 # include <stdlib.h>
  47 #  include <sys/time.h>
  48 #else
  49 # include "xf86drm.h"
  50 # ifdef XFree86LOADER
  51 #  include "xf86.h"
  52 #  include "xf86_ansic.h"
  53 # else
  54 #  include <stdio.h>
  55 #  include <stdlib.h>
  56 # endif
  57 #endif
  58
  59 #define N(x)  drm##x
  60
  61 #define SL_LIST_MAGIC  0xfacade00LU
  62 #define SL_ENTRY_MAGIC 0x00fab1edLU
  63 #define SL_FREED_MAGIC 0xdecea5edLU
  64 #define SL_MAX_LEVEL   16
  65 #define SL_DEBUG       0
  66 #define SL_RANDOM_SEED 0xc01055a1LU
  67
  68 #if SL_MAIN
  69 #define SL_ALLOC malloc
  70 #define SL_FREE  free
  71 #define SL_RANDOM_DECL        static int state = 0;
  72 #define SL_RANDOM_INIT(seed)  if (!state) { srandom(seed); ++state; }
  73 #define SL_RANDOM             random()
  74 #else
  75 #define SL_ALLOC drmMalloc
  76 #define SL_FREE  drmFree
  77 #define SL_RANDOM_DECL        static void *state = NULL
  78 #define SL_RANDOM_INIT(seed)  if (!state) state = drmRandomCreate(seed)
  79 #define SL_RANDOM             drmRandom(state)
  80
  81 #endif
  82
  83 typedef struct SLEntry {
  84     unsigned long     magic;       /* SL_ENTRY_MAGIC */
  85     unsigned long     key;
  86     void              *value;
  87     int               levels;
  88     struct SLEntry    *forward[1]; /* variable sized array */
  89 } SLEntry, *SLEntryPtr;
  90
  91 typedef struct SkipList {
  92     unsigned long    magic;     /* SL_LIST_MAGIC */
  93     int              level;
  94     int              count;
  95     SLEntryPtr       head;
  96     SLEntryPtr       p0;        /* Position for iteration */
  97 } SkipList, *SkipListPtr;
  98
  99 #if SL_MAIN
 100 extern void *N(SLCreate)(void);
 101 extern int  N(SLDestroy)(void *l);
 102 extern int  N(SLLookup)(void *l, unsigned long key, void **value);
 103 extern int  N(SLInsert)(void *l, unsigned long key, void *value);
 104 extern int  N(SLDelete)(void *l, unsigned long key);
 105 extern int  N(SLNext)(void *l, unsigned long *key, void **value);
 106 extern int  N(SLFirst)(void *l, unsigned long *key, void **value);
 107 extern void N(SLDump)(void *l);
 108 extern int  N(SLLookupNeighbors)(void *l, unsigned long key,
 109                                  unsigned long *prev_key, void **prev_value,
 110                                  unsigned long *next_key, void **next_value);
 111 #endif
 112
 113 static SLEntryPtr SLCreateEntry(int max_level, unsigned long key, void *value)
 114 {
 115     SLEntryPtr entry;
 116
 117     if (max_level < 0 || max_level > SL_MAX_LEVEL) max_level = SL_MAX_LEVEL;
 118
 119     entry         = SL_ALLOC(sizeof(*entry)
 120                              + (max_level + 1) * sizeof(entry->forward[0]));
 121     if (!entry) return NULL;
 122     entry->magic  = SL_ENTRY_MAGIC;
 123     entry->key    = key;
 124     entry->value  = value;
 125     entry->levels = max_level + 1;
 126
 127     return entry;
 128 }
 129
 130 static int SLRandomLevel(void)
 131 {
 132     int level = 1;
 133     SL_RANDOM_DECL;
 134
 135     SL_RANDOM_INIT(SL_RANDOM_SEED);
 136
 137     while ((SL_RANDOM & 0x01) && level < SL_MAX_LEVEL) ++level;
 138     return level;
 139 }
 140
 141 void *N(SLCreate)(void)
 142 {
 143     SkipListPtr  list;
 144     int          i;
 145
 146     list           = SL_ALLOC(sizeof(*list));
 147     if (!list) return NULL;
 148     list->magic    = SL_LIST_MAGIC;
 149     list->level    = 0;
 150     list->head     = SLCreateEntry(SL_MAX_LEVEL, 0, NULL);
 151     list->count    = 0;
 152
 153     for (i = 0; i <= SL_MAX_LEVEL; i++) list->head->forward[i] = NULL;
 154
 155     return list;
 156 }
 157
 158 int N(SLDestroy)(void *l)
 159 {
 160     SkipListPtr   list  = (SkipListPtr)l;
 161     SLEntryPtr    entry;
 162     SLEntryPtr    next;
 163
 164     if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
 165
 166     for (entry = list->head; entry; entry = next) {
 167         if (entry->magic != SL_ENTRY_MAGIC) return -1; /* Bad magic */
 168         next         = entry->forward[0];
 169         entry->magic = SL_FREED_MAGIC;
 170         SL_FREE(entry);
 171     }
 172
 173     list->magic = SL_FREED_MAGIC;
 174     SL_FREE(list);
 175     return 0;
 176 }
 177
 178 static SLEntryPtr SLLocate(void *l, unsigned long key, SLEntryPtr *update)
 179 {
 180     SkipListPtr   list  = (SkipListPtr)l;
 181     SLEntryPtr    entry;
 182     int           i;
 183
 184     if (list->magic != SL_LIST_MAGIC) return NULL;
 185
 186     for (i = list->level, entry = list->head; i >= 0; i--) {
 187         while (entry->forward[i] && entry->forward[i]->key < key)
 188             entry = entry->forward[i];
 189         update[i] = entry;
 190     }
 191
 192     return entry->forward[0];
 193 }
 194
 195 int N(SLInsert)(void *l, unsigned long key, void *value)
 196 {
 197     SkipListPtr   list  = (SkipListPtr)l;
 198     SLEntryPtr    entry;
 199     SLEntryPtr    update[SL_MAX_LEVEL + 1];
 200     int           level;
 201     int           i;
 202
 203     if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
 204
 205     entry = SLLocate(list, key, update);
 206
 207     if (entry && entry->key == key) return 1; /* Already in list */
 208
 209
 210     level = SLRandomLevel();
 211     if (level > list->level) {
 212         level = ++list->level;
 213         update[level] = list->head;
 214     }
 215
 216     entry = SLCreateEntry(level, key, value);
 217
 218                                 /* Fix up forward pointers */
 219     for (i = 0; i <= level; i++) {
 220         entry->forward[i]     = update[i]->forward[i];
 221         update[i]->forward[i] = entry;
 222     }
 223
 224     ++list->count;
 225     return 0;                   /* Added to table */
 226 }
 227
 228 int N(SLDelete)(void *l, unsigned long key)
 229 {
 230     SkipListPtr   list = (SkipListPtr)l;
 231     SLEntryPtr    update[SL_MAX_LEVEL + 1];
 232     SLEntryPtr    entry;
 233     int           i;
 234
 235     if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
 236
 237     entry = SLLocate(list, key, update);
 238
 239     if (!entry || entry->key != key) return 1; /* Not found */
 240
 241                                 /* Fix up forward pointers */
 242     for (i = 0; i <= list->level; i++) {
 243         if (update[i]->forward[i] == entry)
 244             update[i]->forward[i] = entry->forward[i];
 245     }
 246
 247     entry->magic = SL_FREED_MAGIC;
 248     SL_FREE(entry);
 249
 250     while (list->level && !list->head->forward[list->level]) --list->level;
 251     --list->count;
 252     return 0;
 253 }
 254
 255 int N(SLLookup)(void *l, unsigned long key, void **value)
 256 {
 257     SkipListPtr   list = (SkipListPtr)l;
 258     SLEntryPtr    update[SL_MAX_LEVEL + 1];
 259     SLEntryPtr    entry;
 260
 261     entry = SLLocate(list, key, update);
 262
 263     if (entry && entry->key == key) {
 264         *value = entry;
 265         return 0;
 266     }
 267     *value = NULL;
 268     return -1;
 269 }
 270
 271 int N(SLLookupNeighbors)(void *l, unsigned long key,
 272                          unsigned long *prev_key, void **prev_value,
 273                          unsigned long *next_key, void **next_value)
 274 {
 275     SkipListPtr   list = (SkipListPtr)l;
 276     SLEntryPtr    update[SL_MAX_LEVEL + 1];
 277     SLEntryPtr    entry;
 278     int           retcode = 0;
 279
 280     entry = SLLocate(list, key, update);
 281
 282     *prev_key   = *next_key   = key;
 283     *prev_value = *next_value = NULL;
 284
 285     if (update[0]) {
 286         *prev_key   = update[0]->key;
 287         *prev_value = update[0]->value;
 288         ++retcode;
 289         if (update[0]->forward[0]) {
 290             *next_key   = update[0]->forward[0]->key;
 291             *next_value = update[0]->forward[0]->value;
 292             ++retcode;
 293         }
 294     }
 295     return retcode;
 296 }
 297
 298 int N(SLNext)(void *l, unsigned long *key, void **value)
 299 {
 300     SkipListPtr   list = (SkipListPtr)l;
 301     SLEntryPtr    entry;
 302
 303     if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
 304
 305     entry    = list->p0;
 306
 307     if (entry) {
 308         list->p0 = entry->forward[0];
 309         *key     = entry->key;
 310         *value   = entry->value;
 311         return 1;
 312     }
 313     list->p0 = NULL;
 314     return 0;
 315 }
 316
 317 int N(SLFirst)(void *l, unsigned long *key, void **value)
 318 {
 319     SkipListPtr   list = (SkipListPtr)l;
 320
 321     if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
 322
 323     list->p0 = list->head->forward[0];
 324     return N(SLNext)(list, key, value);
 325 }
 326
 327 /* Dump internal data structures for debugging. */
 328 void N(SLDump)(void *l)
 329 {
 330     SkipListPtr   list = (SkipListPtr)l;
 331     SLEntryPtr    entry;
 332     int           i;
 333
 334     if (list->magic != SL_LIST_MAGIC) {
 335         printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
 336                list->magic, SL_LIST_MAGIC);
 337         return;
 338     }
 339
 340     printf("Level = %d, count = %d\n", list->level, list->count);
 341     for (entry = list->head; entry; entry = entry->forward[0]) {
 342         if (entry->magic != SL_ENTRY_MAGIC) {
 343             printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
 344                    list->magic, SL_ENTRY_MAGIC);
 345         }
 346         printf("\nEntry %p <0x%08lx, %p> has %2d levels\n",
 347                entry, entry->key, entry->value, entry->levels);
 348         for (i = 0; i < entry->levels; i++) {
 349             if (entry->forward[i]) {
 350                 printf("   %2d: %p <0x%08lx, %p>\n",
 351                        i,
 352                        entry->forward[i],
 353                        entry->forward[i]->key,
 354                        entry->forward[i]->value);
 355             } else {
 356                 printf("   %2d: %p\n", i, entry->forward[i]);
 357             }
 358         }
 359     }
 360 }
 361
 362 #if SL_MAIN
 363 static void print(SkipListPtr list)
 364 {
 365     unsigned long key;
 366     void          *value;
 367
 368     if (N(SLFirst)(list, &key, &value)) {
 369         do {
 370             printf("key = %5lu, value = %p\n", key, value);
 371         } while (N(SLNext)(list, &key, &value));
 372     }
 373 }
 374
 375 static double do_time(int size, int iter)
 376 {
 377     SkipListPtr    list;
 378     int            i, j;
 379     unsigned long  keys[1000000];
 380     unsigned long  previous;
 381     unsigned long  key;
 382     void           *value;
 383     struct timeval start, stop;
 384     double         usec;
 385     SL_RANDOM_DECL;
 386
 387     SL_RANDOM_INIT(12345);
 388
 389     list = N(SLCreate)();
 390
 391     for (i = 0; i < size; i++) {
 392         keys[i] = SL_RANDOM;
 393         N(SLInsert)(list, keys[i], NULL);
 394     }
 395
 396     previous = 0;
 397     if (N(SLFirst)(list, &key, &value)) {
 398         do {
 399             if (key <= previous) {
 400                 printf( "%lu !< %lu\n", previous, key);
 401             }
 402             previous = key;
 403         } while (N(SLNext)(list, &key, &value));
 404     }
 405
 406     gettimeofday(&start, NULL);
 407     for (j = 0; j < iter; j++) {
 408         for (i = 0; i < size; i++) {
 409             if (N(SLLookup)(list, keys[i], &value))
 410                 printf("Error %lu %d\n", keys[i], i);
 411         }
 412     }
 413     gettimeofday(&stop, NULL);
 414
 415     usec = (double)(stop.tv_sec * 1000000 + stop.tv_usec
 416                     - start.tv_sec * 1000000 - start.tv_usec) / (size * iter);
 417
 418     printf("%0.2f microseconds for list length %d\n", usec, size);
 419
 420     N(SLDestroy)(list);
 421
 422     return usec;
 423 }
 424
 425 static void print_neighbors(void *list, unsigned long key)
 426 {
 427     unsigned long prev_key = 0;
 428     unsigned long next_key = 0;
 429     void          *prev_value;
 430     void          *next_value;
 431     int           retval;
 432
 433     retval = drmSLLookupNeighbors(list, key,
 434                                   &prev_key, &prev_value,
 435                                   &next_key, &next_value);
 436     printf("Neighbors of %5lu: %d %5lu %5lu\n",
 437            key, retval, prev_key, next_key);
 438 }
 439
 440 int main(void)
 441 {
 442     SkipListPtr    list;
 443     double         usec, usec2, usec3, usec4;
 444
 445     list = N(SLCreate)();
 446     printf( "list at %p\n", list);
 447
 448     print(list);
 449     printf("\n==============================\n\n");
 450
 451     N(SLInsert)(list, 123, NULL);
 452     N(SLInsert)(list, 213, NULL);
 453     N(SLInsert)(list, 50, NULL);
 454     print(list);
 455     printf("\n==============================\n\n");
 456
 457     print_neighbors(list, 0);
 458     print_neighbors(list, 50);
 459     print_neighbors(list, 51);
 460     print_neighbors(list, 123);
 461     print_neighbors(list, 200);
 462     print_neighbors(list, 213);
 463     print_neighbors(list, 256);
 464     printf("\n==============================\n\n");
 465
 466     N(SLDelete)(list, 50);
 467     print(list);
 468     printf("\n==============================\n\n");
 469
 470     N(SLDump)(list);
 471     N(SLDestroy)(list);
 472     printf("\n==============================\n\n");
 473
 474     usec  = do_time(100, 10000);
 475     usec2 = do_time(1000, 500);
 476     printf("Table size increased by %0.2f, search time increased by %0.2f\n",
 477            1000.0/100.0, usec2 / usec);
 478
 479     usec3 = do_time(10000, 50);
 480     printf("Table size increased by %0.2f, search time increased by %0.2f\n",
 481            10000.0/100.0, usec3 / usec);
 482
 483     usec4 = do_time(100000, 4);
 484     printf("Table size increased by %0.2f, search time increased by %0.2f\n",
 485            100000.0/100.0, usec4 / usec);
 486
 487     return 0;
 488 }
 489 #endif