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 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 } 185
