Back to index

libdrm  2.4.37
xf86drmSL.c
Go to the documentation of this file.
00001 /* xf86drmSL.c -- Skip list support
00002  * Created: Mon May 10 09:28:13 1999 by faith@precisioninsight.com
00003  *
00004  * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas.
00005  * All Rights Reserved.
00006  *
00007  * Permission is hereby granted, free of charge, to any person obtaining a
00008  * copy of this software and associated documentation files (the "Software"),
00009  * to deal in the Software without restriction, including without limitation
00010  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
00011  * and/or sell copies of the Software, and to permit persons to whom the
00012  * Software is furnished to do so, subject to the following conditions:
00013  * 
00014  * The above copyright notice and this permission notice (including the next
00015  * paragraph) shall be included in all copies or substantial portions of the
00016  * Software.
00017  * 
00018  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
00019  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
00020  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
00021  * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
00022  * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
00023  * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
00024  * DEALINGS IN THE SOFTWARE.
00025  * 
00026  * Authors: Rickard E. (Rik) Faith <faith@valinux.com>
00027  *
00028  * DESCRIPTION
00029  *
00030  * This file contains a straightforward skip list implementation.n
00031  *
00032  * FUTURE ENHANCEMENTS
00033  *
00034  * REFERENCES
00035  *
00036  * [Pugh90] William Pugh.  Skip Lists: A Probabilistic Alternative to
00037  * Balanced Trees. CACM 33(6), June 1990, pp. 668-676.
00038  *
00039  */
00040 
00041 #include <stdio.h>
00042 #include <stdlib.h>
00043 
00044 #define SL_MAIN 0
00045 
00046 #if !SL_MAIN
00047 # include "xf86drm.h"
00048 #else
00049 # include <sys/time.h>
00050 #endif
00051 
00052 #define SL_LIST_MAGIC  0xfacade00LU
00053 #define SL_ENTRY_MAGIC 0x00fab1edLU
00054 #define SL_FREED_MAGIC 0xdecea5edLU
00055 #define SL_MAX_LEVEL   16
00056 #define SL_DEBUG       0
00057 #define SL_RANDOM_SEED 0xc01055a1LU
00058 
00059 #if SL_MAIN
00060 #define SL_ALLOC malloc
00061 #define SL_FREE  free
00062 #define SL_RANDOM_DECL        static int state = 0;
00063 #define SL_RANDOM_INIT(seed)  if (!state) { srandom(seed); ++state; }
00064 #define SL_RANDOM             random()
00065 #else
00066 #define SL_ALLOC drmMalloc
00067 #define SL_FREE  drmFree
00068 #define SL_RANDOM_DECL        static void *state = NULL
00069 #define SL_RANDOM_INIT(seed)  if (!state) state = drmRandomCreate(seed)
00070 #define SL_RANDOM             drmRandom(state)
00071 
00072 #endif
00073 
00074 typedef struct SLEntry {
00075     unsigned long     magic;          /* SL_ENTRY_MAGIC */
00076     unsigned long     key;
00077     void              *value;
00078     int               levels;
00079     struct SLEntry    *forward[1]; /* variable sized array */
00080 } SLEntry, *SLEntryPtr;
00081 
00082 typedef struct SkipList {
00083     unsigned long    magic; /* SL_LIST_MAGIC */
00084     int              level;
00085     int              count;
00086     SLEntryPtr       head;
00087     SLEntryPtr       p0;    /* Position for iteration */
00088 } SkipList, *SkipListPtr;
00089 
00090 #if SL_MAIN
00091 extern void *drmSLCreate(void);
00092 extern int  drmSLDestroy(void *l);
00093 extern int  drmSLLookup(void *l, unsigned long key, void **value);
00094 extern int  drmSLInsert(void *l, unsigned long key, void *value);
00095 extern int  drmSLDelete(void *l, unsigned long key);
00096 extern int  drmSLNext(void *l, unsigned long *key, void **value);
00097 extern int  drmSLFirst(void *l, unsigned long *key, void **value);
00098 extern void drmSLDump(void *l);
00099 extern int  drmSLLookupNeighbors(void *l, unsigned long key,
00100                              unsigned long *prev_key, void **prev_value,
00101                              unsigned long *next_key, void **next_value);
00102 #endif
00103 
00104 static SLEntryPtr SLCreateEntry(int max_level, unsigned long key, void *value)
00105 {
00106     SLEntryPtr entry;
00107     
00108     if (max_level < 0 || max_level > SL_MAX_LEVEL) max_level = SL_MAX_LEVEL;
00109 
00110     entry         = SL_ALLOC(sizeof(*entry)
00111                           + (max_level + 1) * sizeof(entry->forward[0]));
00112     if (!entry) return NULL;
00113     entry->magic  = SL_ENTRY_MAGIC;
00114     entry->key    = key;
00115     entry->value  = value;
00116     entry->levels = max_level + 1;
00117 
00118     return entry;
00119 }
00120 
00121 static int SLRandomLevel(void)
00122 {
00123     int level = 1;
00124     SL_RANDOM_DECL;
00125 
00126     SL_RANDOM_INIT(SL_RANDOM_SEED);
00127     
00128     while ((SL_RANDOM & 0x01) && level < SL_MAX_LEVEL) ++level;
00129     return level;
00130 }
00131 
00132 void *drmSLCreate(void)
00133 {
00134     SkipListPtr  list;
00135     int          i;
00136 
00137     list           = SL_ALLOC(sizeof(*list));
00138     if (!list) return NULL;
00139     list->magic    = SL_LIST_MAGIC;
00140     list->level    = 0;
00141     list->head     = SLCreateEntry(SL_MAX_LEVEL, 0, NULL);
00142     list->count    = 0;
00143 
00144     for (i = 0; i <= SL_MAX_LEVEL; i++) list->head->forward[i] = NULL;
00145     
00146     return list;
00147 }
00148 
00149 int drmSLDestroy(void *l)
00150 {
00151     SkipListPtr   list  = (SkipListPtr)l;
00152     SLEntryPtr    entry;
00153     SLEntryPtr    next;
00154 
00155     if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
00156 
00157     for (entry = list->head; entry; entry = next) {
00158        if (entry->magic != SL_ENTRY_MAGIC) return -1; /* Bad magic */
00159        next         = entry->forward[0];
00160        entry->magic = SL_FREED_MAGIC;
00161        SL_FREE(entry);
00162     }
00163 
00164     list->magic = SL_FREED_MAGIC;
00165     SL_FREE(list);
00166     return 0;
00167 }
00168 
00169 static SLEntryPtr SLLocate(void *l, unsigned long key, SLEntryPtr *update)
00170 {
00171     SkipListPtr   list  = (SkipListPtr)l;
00172     SLEntryPtr    entry;
00173     int           i;
00174 
00175     if (list->magic != SL_LIST_MAGIC) return NULL;
00176 
00177     for (i = list->level, entry = list->head; i >= 0; i--) {
00178        while (entry->forward[i] && entry->forward[i]->key < key)
00179            entry = entry->forward[i];
00180        update[i] = entry;
00181     }
00182 
00183     return entry->forward[0];
00184 }
00185 
00186 int drmSLInsert(void *l, unsigned long key, void *value)
00187 {
00188     SkipListPtr   list  = (SkipListPtr)l;
00189     SLEntryPtr    entry;
00190     SLEntryPtr    update[SL_MAX_LEVEL + 1];
00191     int           level;
00192     int           i;
00193 
00194     if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
00195 
00196     entry = SLLocate(list, key, update);
00197 
00198     if (entry && entry->key == key) return 1; /* Already in list */
00199 
00200 
00201     level = SLRandomLevel();
00202     if (level > list->level) {
00203        level = ++list->level;
00204        update[level] = list->head;
00205     }
00206 
00207     entry = SLCreateEntry(level, key, value);
00208 
00209                             /* Fix up forward pointers */
00210     for (i = 0; i <= level; i++) {
00211        entry->forward[i]     = update[i]->forward[i];
00212        update[i]->forward[i] = entry;
00213     }
00214 
00215     ++list->count;
00216     return 0;               /* Added to table */
00217 }
00218 
00219 int drmSLDelete(void *l, unsigned long key)
00220 {
00221     SkipListPtr   list = (SkipListPtr)l;
00222     SLEntryPtr    update[SL_MAX_LEVEL + 1];
00223     SLEntryPtr    entry;
00224     int           i;
00225 
00226     if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
00227 
00228     entry = SLLocate(list, key, update);
00229 
00230     if (!entry || entry->key != key) return 1; /* Not found */
00231 
00232                             /* Fix up forward pointers */
00233     for (i = 0; i <= list->level; i++) {
00234        if (update[i]->forward[i] == entry)
00235            update[i]->forward[i] = entry->forward[i];
00236     }
00237 
00238     entry->magic = SL_FREED_MAGIC;
00239     SL_FREE(entry);
00240 
00241     while (list->level && !list->head->forward[list->level]) --list->level;
00242     --list->count;
00243     return 0;
00244 }
00245 
00246 int drmSLLookup(void *l, unsigned long key, void **value)
00247 {
00248     SkipListPtr   list = (SkipListPtr)l;
00249     SLEntryPtr    update[SL_MAX_LEVEL + 1];
00250     SLEntryPtr    entry;
00251 
00252     entry = SLLocate(list, key, update);
00253 
00254     if (entry && entry->key == key) {
00255        *value = entry;
00256        return 0;
00257     }
00258     *value = NULL;
00259     return -1;
00260 }
00261 
00262 int drmSLLookupNeighbors(void *l, unsigned long key,
00263                       unsigned long *prev_key, void **prev_value,
00264                       unsigned long *next_key, void **next_value)
00265 {
00266     SkipListPtr   list = (SkipListPtr)l;
00267     SLEntryPtr    update[SL_MAX_LEVEL + 1];
00268     int           retcode = 0;
00269 
00270     *prev_key   = *next_key   = key;
00271     *prev_value = *next_value = NULL;
00272        
00273     if (update[0]) {
00274        *prev_key   = update[0]->key;
00275        *prev_value = update[0]->value;
00276        ++retcode;
00277        if (update[0]->forward[0]) {
00278            *next_key   = update[0]->forward[0]->key;
00279            *next_value = update[0]->forward[0]->value;
00280            ++retcode;
00281        }
00282     }
00283     return retcode;
00284 }
00285 
00286 int drmSLNext(void *l, unsigned long *key, void **value)
00287 {
00288     SkipListPtr   list = (SkipListPtr)l;
00289     SLEntryPtr    entry;
00290     
00291     if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
00292 
00293     entry    = list->p0;
00294 
00295     if (entry) {
00296        list->p0 = entry->forward[0];
00297        *key     = entry->key;
00298        *value   = entry->value;
00299        return 1;
00300     }
00301     list->p0 = NULL;
00302     return 0;
00303 }
00304 
00305 int drmSLFirst(void *l, unsigned long *key, void **value)
00306 {
00307     SkipListPtr   list = (SkipListPtr)l;
00308     
00309     if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
00310     
00311     list->p0 = list->head->forward[0];
00312     return drmSLNext(list, key, value);
00313 }
00314 
00315 /* Dump internal data structures for debugging. */
00316 void drmSLDump(void *l)
00317 {
00318     SkipListPtr   list = (SkipListPtr)l;
00319     SLEntryPtr    entry;
00320     int           i;
00321     
00322     if (list->magic != SL_LIST_MAGIC) {
00323        printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
00324               list->magic, SL_LIST_MAGIC);
00325        return;
00326     }
00327 
00328     printf("Level = %d, count = %d\n", list->level, list->count);
00329     for (entry = list->head; entry; entry = entry->forward[0]) {
00330        if (entry->magic != SL_ENTRY_MAGIC) {
00331            printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
00332                  list->magic, SL_ENTRY_MAGIC);
00333        }
00334        printf("\nEntry %p <0x%08lx, %p> has %2d levels\n",
00335               entry, entry->key, entry->value, entry->levels);
00336        for (i = 0; i < entry->levels; i++) {
00337            if (entry->forward[i]) {
00338               printf("   %2d: %p <0x%08lx, %p>\n",
00339                      i,
00340                      entry->forward[i],
00341                      entry->forward[i]->key,
00342                      entry->forward[i]->value);
00343            } else {
00344               printf("   %2d: %p\n", i, entry->forward[i]);
00345            }
00346        }
00347     }
00348 }
00349 
00350 #if SL_MAIN
00351 static void print(SkipListPtr list)
00352 {
00353     unsigned long key;
00354     void          *value;
00355     
00356     if (drmSLFirst(list, &key, &value)) {
00357        do {
00358            printf("key = %5lu, value = %p\n", key, value);
00359        } while (drmSLNext(list, &key, &value));
00360     }
00361 }
00362 
00363 static double do_time(int size, int iter)
00364 {
00365     SkipListPtr    list;
00366     int            i, j;
00367     unsigned long  keys[1000000];
00368     unsigned long  previous;
00369     unsigned long  key;
00370     void           *value;
00371     struct timeval start, stop;
00372     double         usec;
00373     SL_RANDOM_DECL;
00374 
00375     SL_RANDOM_INIT(12345);
00376     
00377     list = drmSLCreate();
00378 
00379     for (i = 0; i < size; i++) {
00380        keys[i] = SL_RANDOM;
00381        drmSLInsert(list, keys[i], NULL);
00382     }
00383 
00384     previous = 0;
00385     if (drmSLFirst(list, &key, &value)) {
00386        do {
00387            if (key <= previous) {
00388               printf( "%lu !< %lu\n", previous, key);
00389            }
00390            previous = key;
00391        } while (drmSLNext(list, &key, &value));
00392     }
00393     
00394     gettimeofday(&start, NULL);
00395     for (j = 0; j < iter; j++) {
00396        for (i = 0; i < size; i++) {
00397            if (drmSLLookup(list, keys[i], &value))
00398               printf("Error %lu %d\n", keys[i], i);
00399        }
00400     }
00401     gettimeofday(&stop, NULL);
00402     
00403     usec = (double)(stop.tv_sec * 1000000 + stop.tv_usec
00404                   - start.tv_sec * 1000000 - start.tv_usec) / (size * iter);
00405     
00406     printf("%0.2f microseconds for list length %d\n", usec, size);
00407 
00408     drmSLDestroy(list);
00409     
00410     return usec;
00411 }
00412 
00413 static void print_neighbors(void *list, unsigned long key)
00414 {
00415     unsigned long prev_key = 0;
00416     unsigned long next_key = 0;
00417     void          *prev_value;
00418     void          *next_value;
00419     int           retval;
00420 
00421     retval = drmSLLookupNeighbors(list, key,
00422                               &prev_key, &prev_value,
00423                               &next_key, &next_value);
00424     printf("Neighbors of %5lu: %d %5lu %5lu\n",
00425           key, retval, prev_key, next_key);
00426 }
00427 
00428 int main(void)
00429 {
00430     SkipListPtr    list;
00431     double         usec, usec2, usec3, usec4;
00432 
00433     list = drmSLCreate();
00434     printf( "list at %p\n", list);
00435 
00436     print(list);
00437     printf("\n==============================\n\n");
00438 
00439     drmSLInsert(list, 123, NULL);
00440     drmSLInsert(list, 213, NULL);
00441     drmSLInsert(list, 50, NULL);
00442     print(list);
00443     printf("\n==============================\n\n");
00444     
00445     print_neighbors(list, 0);
00446     print_neighbors(list, 50);
00447     print_neighbors(list, 51);
00448     print_neighbors(list, 123);
00449     print_neighbors(list, 200);
00450     print_neighbors(list, 213);
00451     print_neighbors(list, 256);
00452     printf("\n==============================\n\n");    
00453     
00454     drmSLDelete(list, 50);
00455     print(list);
00456     printf("\n==============================\n\n");
00457 
00458     drmSLDump(list);
00459     drmSLDestroy(list);
00460     printf("\n==============================\n\n");
00461 
00462     usec  = do_time(100, 10000);
00463     usec2 = do_time(1000, 500);
00464     printf("Table size increased by %0.2f, search time increased by %0.2f\n",
00465           1000.0/100.0, usec2 / usec);
00466     
00467     usec3 = do_time(10000, 50);
00468     printf("Table size increased by %0.2f, search time increased by %0.2f\n",
00469           10000.0/100.0, usec3 / usec);
00470     
00471     usec4 = do_time(100000, 4);
00472     printf("Table size increased by %0.2f, search time increased by %0.2f\n",
00473           100000.0/100.0, usec4 / usec);
00474 
00475     return 0;
00476 }
00477 #endif