tests/drmsl.c

   1 /* drmsl.c -- Skip list test
   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  * 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 #include <sys/time.h>
  44
  45 #include "xf86drm.h"
  46
  47 static void print(void* list)
  48 {
  49     unsigned long key;
  50     void          *value;
  51
  52     if (drmSLFirst(list, &key, &value)) {
  53         do {
  54             printf("key = %5lu, value = %p\n", key, value);
  55         } while (drmSLNext(list, &key, &value));
  56     }
  57 }
  58
  59 static double do_time(int size, int iter)
  60 {
  61     void           *list;
  62     int            i, j;
  63     unsigned long  keys[1000000];
  64     unsigned long  previous;
  65     unsigned long  key;
  66     void           *value;
  67     struct timeval start, stop;
  68     double         usec;
  69     void           *ranstate;
  70
  71     list = drmSLCreate();
  72     ranstate = drmRandomCreate(12345);
  73
  74     for (i = 0; i < size; i++) {
  75         keys[i] = drmRandom(ranstate);
  76         drmSLInsert(list, keys[i], NULL);
  77     }
  78
  79     previous = 0;
  80     if (drmSLFirst(list, &key, &value)) {
  81         do {
  82             if (key <= previous) {
  83                 printf( "%lu !< %lu\n", previous, key);
  84             }
  85             previous = key;
  86         } while (drmSLNext(list, &key, &value));
  87     }
  88
  89     gettimeofday(&start, NULL);
  90     for (j = 0; j < iter; j++) {
  91         for (i = 0; i < size; i++) {
  92             if (drmSLLookup(list, keys[i], &value))
  93                 printf("Error %lu %d\n", keys[i], i);
  94         }
  95     }
  96     gettimeofday(&stop, NULL);
  97
  98     usec = (double)(stop.tv_sec * 1000000 + stop.tv_usec
  99                     - start.tv_sec * 1000000 - start.tv_usec) / (size * iter);
 100
 101     printf("%0.2f microseconds for list length %d\n", usec, size);
 102
 103     drmRandomDouble(ranstate);
 104     drmSLDestroy(list);
 105
 106     return usec;
 107 }
 108
 109 static void print_neighbors(void *list, unsigned long key,
 110                             unsigned long expected_prev,
 111                             unsigned long expected_next)
 112 {
 113     unsigned long prev_key = 0;
 114     unsigned long next_key = 0;
 115     void          *prev_value;
 116     void          *next_value;
 117     int           retval;
 118
 119     retval = drmSLLookupNeighbors(list, key,
 120                                   &prev_key, &prev_value,
 121                                   &next_key, &next_value);
 122     printf("Neighbors of %5lu: %d %5lu %5lu\n",
 123            key, retval, prev_key, next_key);
 124     if (prev_key != expected_prev) {
 125         fprintf(stderr, "Unexpected neighbor: %5lu. Expected: %5lu\n",
 126                 prev_key, expected_prev);
 127         exit(1);
 128     }
 129     if (next_key != expected_next) {
 130         fprintf(stderr, "Unexpected neighbor: %5lu. Expected: %5lu\n",
 131                 next_key, expected_next);
 132         exit(1);
 133     }
 134 }
 135
 136 int main(void)
 137 {
 138     void*    list;
 139     double   usec, usec2, usec3, usec4;
 140
 141     list = drmSLCreate();
 142     printf( "list at %p\n", list);
 143
 144     print(list);
 145     printf("\n==============================\n\n");
 146
 147     drmSLInsert(list, 123, NULL);
 148     drmSLInsert(list, 213, NULL);
 149     drmSLInsert(list, 50, NULL);
 150     print(list);
 151     printf("\n==============================\n\n");
 152
 153     print_neighbors(list, 0, 0, 50);
 154     print_neighbors(list, 50, 0, 50);
 155     print_neighbors(list, 51, 50, 123);
 156     print_neighbors(list, 123, 50, 123);
 157     print_neighbors(list, 200, 123, 213);
 158     print_neighbors(list, 213, 123, 213);
 159     print_neighbors(list, 256, 213, 256);
 160     printf("\n==============================\n\n");
 161
 162     drmSLDelete(list, 50);
 163     print(list);
 164     printf("\n==============================\n\n");
 165
 166     drmSLDump(list);
 167     drmSLDestroy(list);
 168     printf("\n==============================\n\n");
 169
 170     usec  = do_time(100, 10000);
 171     usec2 = do_time(1000, 500);
 172     printf("Table size increased by %0.2f, search time increased by %0.2f\n",
 173            1000.0/100.0, usec2 / usec);
 174
 175     usec3 = do_time(10000, 50);
 176     printf("Table size increased by %0.2f, search time increased by %0.2f\n",
 177            10000.0/100.0, usec3 / usec);
 178
 179     usec4 = do_time(100000, 4);
 180     printf("Table size increased by %0.2f, search time increased by %0.2f\n",
 181            100000.0/100.0, usec4 / usec);
 182
 183     return 0;
 184 }