| 1 |
/* drmsl.c -- Skip list test |
| 2 |
* Created: Mon May 10 09:28:13 1999 by [email protected] |
| 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 <[email protected]> |
| 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 |
} |