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