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 {
 111     unsigned long prev_key = 0;
 112     unsigned long next_key = 0;
 113     void          *prev_value;
 114     void          *next_value;
 115     int           retval;
 116
 117     retval = drmSLLookupNeighbors(list, key,
 118                                   &prev_key, &prev_value,
 119                                   &next_key, &next_value);
 120     printf("Neighbors of %5lu: %d %5lu %5lu\n",
 121            key, retval, prev_key, next_key);
 122 }
 123
 124 int main(void)
 125 {
 126     void*    list;
 127     double   usec, usec2, usec3, usec4;
 128
 129     list = drmSLCreate();
 130     printf( "list at %p\n", list);
 131
 132     print(list);
 133     printf("\n==============================\n\n");
 134
 135     drmSLInsert(list, 123, NULL);
 136     drmSLInsert(list, 213, NULL);
 137     drmSLInsert(list, 50, NULL);
 138     print(list);
 139     printf("\n==============================\n\n");
 140
 141     print_neighbors(list, 0);
 142     print_neighbors(list, 50);
 143     print_neighbors(list, 51);
 144     print_neighbors(list, 123);
 145     print_neighbors(list, 200);
 146     print_neighbors(list, 213);
 147     print_neighbors(list, 256);
 148     printf("\n==============================\n\n");
 149
 150     drmSLDelete(list, 50);
 151     print(list);
 152     printf("\n==============================\n\n");
 153
 154     drmSLDump(list);
 155     drmSLDestroy(list);
 156     printf("\n==============================\n\n");
 157
 158     usec  = do_time(100, 10000);
 159     usec2 = do_time(1000, 500);
 160     printf("Table size increased by %0.2f, search time increased by %0.2f\n",
 161            1000.0/100.0, usec2 / usec);
 162
 163     usec3 = do_time(10000, 50);
 164     printf("Table size increased by %0.2f, search time increased by %0.2f\n",
 165            10000.0/100.0, usec3 / usec);
 166
 167     usec4 = do_time(100000, 4);
 168     printf("Table size increased by %0.2f, search time increased by %0.2f\n",
 169            100000.0/100.0, usec4 / usec);
 170
 171     return 0;
 172 }