1 /* drmsl.c -- Skip list test 2 * Created: Mon May 10 09:28:13 1999 by faith (at) 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 (at) 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 } 173
