libdrm/xf86drmSL.c

   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  * $XFree86: xc/programs/Xserver/hw/xfree86/os-support/linux/drm/xf86drmSL.c,v 1.3 2000/06/17 00:03:34 martin Exp $
  29  *
  30  * DESCRIPTION
  31  *
  32  * This file contains a straightforward skip list implementation.n
  33  *
  34  * FUTURE ENHANCEMENTS
  35  *
  36  * REFERENCES
  37  *
  38  * [Pugh90] William Pugh.  Skip Lists: A Probabilistic Alternative to
  39  * Balanced Trees. CACM 33(6), June 1990, pp. 668-676.
  40  *
  41  */
  42
  43 #ifdef HAVE_XORG_CONFIG_H
  44 #include <xorg-config.h>
  45 #endif
  46
  47 #define SL_MAIN 0
  48
  49 #if SL_MAIN
  50 # include <stdio.h>
  51 # include <stdlib.h>
  52 #  include <sys/time.h>
  53 #else
  54 # include "drm.h"
  55 # include "xf86drm.h"
  56 # ifdef XFree86LOADER
  57 #  include "xf86.h"
  58 #  include "xf86_ansic.h"
  59 # else
  60 #  include <stdio.h>
  61 #  include <stdlib.h>
  62 # endif
  63 #endif
  64
  65 #define SL_LIST_MAGIC  0xfacade00LU
  66 #define SL_ENTRY_MAGIC 0x00fab1edLU
  67 #define SL_FREED_MAGIC 0xdecea5edLU
  68 #define SL_MAX_LEVEL   16
  69 #define SL_DEBUG       0
  70 #define SL_RANDOM_SEED 0xc01055a1LU
  71
  72 #if SL_MAIN
  73 #define SL_ALLOC malloc
  74 #define SL_FREE  free
  75 #define SL_RANDOM_DECL        static int state = 0;
  76 #define SL_RANDOM_INIT(seed)  if (!state) { srandom(seed); ++state; }
  77 #define SL_RANDOM             random()
  78 #else
  79 #define SL_ALLOC drmMalloc
  80 #define SL_FREE  drmFree
  81 #define SL_RANDOM_DECL        static void *state = NULL
  82 #define SL_RANDOM_INIT(seed)  if (!state) state = drmRandomCreate(seed)
  83 #define SL_RANDOM             drmRandom(state)
  84
  85 #endif
  86
  87 typedef struct SLEntry {
  88     unsigned long     magic;       /* SL_ENTRY_MAGIC */
  89     unsigned long     key;
  90     void              *value;
  91     int               levels;
  92     struct SLEntry    *forward[1]; /* variable sized array */
  93 } SLEntry, *SLEntryPtr;
  94
  95 typedef struct SkipList {
  96     unsigned long    magic;     /* SL_LIST_MAGIC */
  97     int              level;
  98     int              count;
  99     SLEntryPtr       head;
 100     SLEntryPtr       p0;        /* Position for iteration */
 101 } SkipList, *SkipListPtr;
 102
 103 #if SL_MAIN
 104 extern void *drmSLCreate(void);
 105 extern int  drmSLDestroy(void *l);
 106 extern int  drmSLLookup(void *l, unsigned long key, void **value);
 107 extern int  drmSLInsert(void *l, unsigned long key, void *value);
 108 extern int  drmSLDelete(void *l, unsigned long key);
 109 extern int  drmSLNext(void *l, unsigned long *key, void **value);
 110 extern int  drmSLFirst(void *l, unsigned long *key, void **value);
 111 extern void drmSLDump(void *l);
 112 extern int  drmSLLookupNeighbors(void *l, unsigned long key,
 113                                  unsigned long *prev_key, void **prev_value,
 114                                  unsigned long *next_key, void **next_value);
 115 #endif
 116
 117 static SLEntryPtr SLCreateEntry(int max_level, unsigned long key, void *value)
 118 {
 119     SLEntryPtr entry;
 120
 121     if (max_level < 0 || max_level > SL_MAX_LEVEL) max_level = SL_MAX_LEVEL;
 122
 123     entry         = SL_ALLOC(sizeof(*entry)
 124                              + (max_level + 1) * sizeof(entry->forward[0]));
 125     if (!entry) return NULL;
 126     entry->magic  = SL_ENTRY_MAGIC;
 127     entry->key    = key;
 128     entry->value  = value;
 129     entry->levels = max_level + 1;
 130
 131     return entry;
 132 }
 133
 134 static int SLRandomLevel(void)
 135 {
 136     int level = 1;
 137     SL_RANDOM_DECL;
 138
 139     SL_RANDOM_INIT(SL_RANDOM_SEED);
 140
 141     while ((SL_RANDOM & 0x01) && level < SL_MAX_LEVEL) ++level;
 142     return level;
 143 }
 144
 145 void *drmSLCreate(void)
 146 {
 147     SkipListPtr  list;
 148     int          i;
 149
 150     list           = SL_ALLOC(sizeof(*list));
 151     if (!list) return NULL;
 152     list->magic    = SL_LIST_MAGIC;
 153     list->level    = 0;
 154     list->head     = SLCreateEntry(SL_MAX_LEVEL, 0, NULL);
 155     list->count    = 0;
 156
 157     for (i = 0; i <= SL_MAX_LEVEL; i++) list->head->forward[i] = NULL;
 158
 159     return list;
 160 }
 161
 162 int drmSLDestroy(void *l)
 163 {
 164     SkipListPtr   list  = (SkipListPtr)l;
 165     SLEntryPtr    entry;
 166     SLEntryPtr    next;
 167
 168     if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
 169
 170     for (entry = list->head; entry; entry = next) {
 171         if (entry->magic != SL_ENTRY_MAGIC) return -1; /* Bad magic */
 172         next         = entry->forward[0];
 173         entry->magic = SL_FREED_MAGIC;
 174         SL_FREE(entry);
 175     }
 176
 177     list->magic = SL_FREED_MAGIC;
 178     SL_FREE(list);
 179     return 0;
 180 }
 181
 182 static SLEntryPtr SLLocate(void *l, unsigned long key, SLEntryPtr *update)
 183 {
 184     SkipListPtr   list  = (SkipListPtr)l;
 185     SLEntryPtr    entry;
 186     int           i;
 187
 188     if (list->magic != SL_LIST_MAGIC) return NULL;
 189
 190     for (i = list->level, entry = list->head; i >= 0; i--) {
 191         while (entry->forward[i] && entry->forward[i]->key < key)
 192             entry = entry->forward[i];
 193         update[i] = entry;
 194     }
 195
 196     return entry->forward[0];
 197 }
 198
 199 int drmSLInsert(void *l, unsigned long key, void *value)
 200 {
 201     SkipListPtr   list  = (SkipListPtr)l;
 202     SLEntryPtr    entry;
 203     SLEntryPtr    update[SL_MAX_LEVEL + 1];
 204     int           level;
 205     int           i;
 206
 207     if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
 208
 209     entry = SLLocate(list, key, update);
 210
 211     if (entry && entry->key == key) return 1; /* Already in list */
 212
 213
 214     level = SLRandomLevel();
 215     if (level > list->level) {
 216         level = ++list->level;
 217         update[level] = list->head;
 218     }
 219
 220     entry = SLCreateEntry(level, key, value);
 221
 222                                 /* Fix up forward pointers */
 223     for (i = 0; i <= level; i++) {
 224         entry->forward[i]     = update[i]->forward[i];
 225         update[i]->forward[i] = entry;
 226     }
 227
 228     ++list->count;
 229     return 0;                   /* Added to table */
 230 }
 231
 232 int drmSLDelete(void *l, unsigned long key)
 233 {
 234     SkipListPtr   list = (SkipListPtr)l;
 235     SLEntryPtr    update[SL_MAX_LEVEL + 1];
 236     SLEntryPtr    entry;
 237     int           i;
 238
 239     if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
 240
 241     entry = SLLocate(list, key, update);
 242
 243     if (!entry || entry->key != key) return 1; /* Not found */
 244
 245                                 /* Fix up forward pointers */
 246     for (i = 0; i <= list->level; i++) {
 247         if (update[i]->forward[i] == entry)
 248             update[i]->forward[i] = entry->forward[i];
 249     }
 250
 251     entry->magic = SL_FREED_MAGIC;
 252     SL_FREE(entry);
 253
 254     while (list->level && !list->head->forward[list->level]) --list->level;
 255     --list->count;
 256     return 0;
 257 }
 258
 259 int drmSLLookup(void *l, unsigned long key, void **value)
 260 {
 261     SkipListPtr   list = (SkipListPtr)l;
 262     SLEntryPtr    update[SL_MAX_LEVEL + 1];
 263     SLEntryPtr    entry;
 264
 265     entry = SLLocate(list, key, update);
 266
 267     if (entry && entry->key == key) {
 268         *value = entry;
 269         return 0;
 270     }
 271     *value = NULL;
 272     return -1;
 273 }
 274
 275 int drmSLLookupNeighbors(void *l, unsigned long key,
 276                          unsigned long *prev_key, void **prev_value,
 277                          unsigned long *next_key, void **next_value)
 278 {
 279     SkipListPtr   list = (SkipListPtr)l;
 280     SLEntryPtr    update[SL_MAX_LEVEL + 1];
 281     SLEntryPtr    entry;
 282     int           retcode = 0;
 283
 284     entry = SLLocate(list, key, update);
 285
 286     *prev_key   = *next_key   = key;
 287     *prev_value = *next_value = NULL;
 288
 289     if (update[0]) {
 290         *prev_key   = update[0]->key;
 291         *prev_value = update[0]->value;
 292         ++retcode;
 293         if (update[0]->forward[0]) {
 294             *next_key   = update[0]->forward[0]->key;
 295             *next_value = update[0]->forward[0]->value;
 296             ++retcode;
 297         }
 298     }
 299     return retcode;
 300 }
 301
 302 int drmSLNext(void *l, unsigned long *key, void **value)
 303 {
 304     SkipListPtr   list = (SkipListPtr)l;
 305     SLEntryPtr    entry;
 306
 307     if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
 308
 309     entry    = list->p0;
 310
 311     if (entry) {
 312         list->p0 = entry->forward[0];
 313         *key     = entry->key;
 314         *value   = entry->value;
 315         return 1;
 316     }
 317     list->p0 = NULL;
 318     return 0;
 319 }
 320
 321 int drmSLFirst(void *l, unsigned long *key, void **value)
 322 {
 323     SkipListPtr   list = (SkipListPtr)l;
 324
 325     if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
 326
 327     list->p0 = list->head->forward[0];
 328     return drmSLNext(list, key, value);
 329 }
 330
 331 /* Dump internal data structures for debugging. */
 332 void drmSLDump(void *l)
 333 {
 334     SkipListPtr   list = (SkipListPtr)l;
 335     SLEntryPtr    entry;
 336     int           i;
 337
 338     if (list->magic != SL_LIST_MAGIC) {
 339         printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
 340                list->magic, SL_LIST_MAGIC);
 341         return;
 342     }
 343
 344     printf("Level = %d, count = %d\n", list->level, list->count);
 345     for (entry = list->head; entry; entry = entry->forward[0]) {
 346         if (entry->magic != SL_ENTRY_MAGIC) {
 347             printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
 348                    list->magic, SL_ENTRY_MAGIC);
 349         }
 350         printf("\nEntry %p <0x%08lx, %p> has %2d levels\n",
 351                entry, entry->key, entry->value, entry->levels);
 352         for (i = 0; i < entry->levels; i++) {
 353             if (entry->forward[i]) {
 354                 printf("   %2d: %p <0x%08lx, %p>\n",
 355                        i,
 356                        entry->forward[i],
 357                        entry->forward[i]->key,
 358                        entry->forward[i]->value);
 359             } else {
 360                 printf("   %2d: %p\n", i, entry->forward[i]);
 361             }
 362         }
 363     }
 364 }
 365
 366 #if SL_MAIN
 367 static void print(SkipListPtr list)
 368 {
 369     unsigned long key;
 370     void          *value;
 371
 372     if (drmSLFirst(list, &key, &value)) {
 373         do {
 374             printf("key = %5lu, value = %p\n", key, value);
 375         } while (drmSLNext(list, &key, &value));
 376     }
 377 }
 378
 379 static double do_time(int size, int iter)
 380 {
 381     SkipListPtr    list;
 382     int            i, j;
 383     unsigned long  keys[1000000];
 384     unsigned long  previous;
 385     unsigned long  key;
 386     void           *value;
 387     struct timeval start, stop;
 388     double         usec;
 389     SL_RANDOM_DECL;
 390
 391     SL_RANDOM_INIT(12345);
 392
 393     list = drmSLCreate();
 394
 395     for (i = 0; i < size; i++) {
 396         keys[i] = SL_RANDOM;
 397         drmSLInsert(list, keys[i], NULL);
 398     }
 399
 400     previous = 0;
 401     if (drmSLFirst(list, &key, &value)) {
 402         do {
 403             if (key <= previous) {
 404                 printf( "%lu !< %lu\n", previous, key);
 405             }
 406             previous = key;
 407         } while (drmSLNext(list, &key, &value));
 408     }
 409
 410     gettimeofday(&start, NULL);
 411     for (j = 0; j < iter; j++) {
 412         for (i = 0; i < size; i++) {
 413             if (drmSLLookup(list, keys[i], &value))
 414                 printf("Error %lu %d\n", keys[i], i);
 415         }
 416     }
 417     gettimeofday(&stop, NULL);
 418
 419     usec = (double)(stop.tv_sec * 1000000 + stop.tv_usec
 420                     - start.tv_sec * 1000000 - start.tv_usec) / (size * iter);
 421
 422     printf("%0.2f microseconds for list length %d\n", usec, size);
 423
 424     drmSLDestroy(list);
 425
 426     return usec;
 427 }
 428
 429 static void print_neighbors(void *list, unsigned long key)
 430 {
 431     unsigned long prev_key = 0;
 432     unsigned long next_key = 0;
 433     void          *prev_value;
 434     void          *next_value;
 435     int           retval;
 436
 437     retval = drmSLLookupNeighbors(list, key,
 438                                   &prev_key, &prev_value,
 439                                   &next_key, &next_value);
 440     printf("Neighbors of %5lu: %d %5lu %5lu\n",
 441            key, retval, prev_key, next_key);
 442 }
 443
 444 int main(void)
 445 {
 446     SkipListPtr    list;
 447     double         usec, usec2, usec3, usec4;
 448
 449     list = drmSLCreate();
 450     printf( "list at %p\n", list);
 451
 452     print(list);
 453     printf("\n==============================\n\n");
 454
 455     drmSLInsert(list, 123, NULL);
 456     drmSLInsert(list, 213, NULL);
 457     drmSLInsert(list, 50, NULL);
 458     print(list);
 459     printf("\n==============================\n\n");
 460
 461     print_neighbors(list, 0);
 462     print_neighbors(list, 50);
 463     print_neighbors(list, 51);
 464     print_neighbors(list, 123);
 465     print_neighbors(list, 200);
 466     print_neighbors(list, 213);
 467     print_neighbors(list, 256);
 468     printf("\n==============================\n\n");
 469
 470     drmSLDelete(list, 50);
 471     print(list);
 472     printf("\n==============================\n\n");
 473
 474     drmSLDump(list);
 475     drmSLDestroy(list);
 476     printf("\n==============================\n\n");
 477
 478     usec  = do_time(100, 10000);
 479     usec2 = do_time(1000, 500);
 480     printf("Table size increased by %0.2f, search time increased by %0.2f\n",
 481            1000.0/100.0, usec2 / usec);
 482
 483     usec3 = do_time(10000, 50);
 484     printf("Table size increased by %0.2f, search time increased by %0.2f\n",
 485            10000.0/100.0, usec3 / usec);
 486
 487     usec4 = do_time(100000, 4);
 488     printf("Table size increased by %0.2f, search time increased by %0.2f\n",
 489            100000.0/100.0, usec4 / usec);
 490
 491     return 0;
 492 }
 493 #endif