1 /* Licensed to the Apache Software Foundation (ASF) under one or more
2 * contributor license agreements. See the NOTICE file distributed with
3 * this work for additional information regarding copyright ownership.
4 * The ASF licenses this file to You under the Apache License, Version 2.0
5 * (the "License"); you may not use this file except in compliance with
6 * the License. You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "testutil.h"
18 #include "apr.h"
19 #include "apr_strings.h"
20 #include "apr_general.h"
21 #include "apr_pools.h"
22 #include "apr_skiplist.h"
23 #if APR_HAVE_STDIO_H
24 #include <stdio.h>
25 #endif
26 #if APR_HAVE_STDLIB_H
27 #include <stdlib.h>
28 #endif
29 #if APR_HAVE_STRING_H
30 #include <string.h>
31 #endif
32
33 static apr_pool_t *ptmp = NULL;
34 static apr_skiplist *skiplist = NULL;
35
36 /* apr_skiplist_add[_compare]() are missing in 1.5.x,
37 * so emulate them (not thread-safe!)...
38 */
39 static apr_skiplist_compare current_comp;
add_comp(void * a,void * b)40 static int add_comp(void *a, void *b)
41 {
42 return current_comp(a, b) < 0 ? -1 : +1;
43 }
apr_skiplist_add_compare(apr_skiplist * sl,void * data,apr_skiplist_compare comp)44 static apr_skiplistnode *apr_skiplist_add_compare(apr_skiplist *sl, void *data,
45 apr_skiplist_compare comp)
46 {
47 current_comp = comp;
48 return apr_skiplist_insert_compare(sl, data, add_comp);
49 }
apr_skiplist_add(apr_skiplist * sl,void * data)50 static apr_skiplistnode *apr_skiplist_add(apr_skiplist *sl, void *data)
51 {
52 /* Ugly, really, but should work *as long as* the compare function is the
53 * first field of the (opaque) skiplist struct, this is the case for now :p
54 */
55 return apr_skiplist_add_compare(sl, data, *(apr_skiplist_compare*)sl);
56 }
57
skiplist_get_size(abts_case * tc,apr_skiplist * sl)58 static int skiplist_get_size(abts_case *tc, apr_skiplist *sl)
59 {
60 size_t size = 0;
61 apr_skiplistnode *n;
62 for (n = apr_skiplist_getlist(sl); n; apr_skiplist_next(sl, &n)) {
63 ++size;
64 }
65 return size;
66 }
67
skiplist_init(abts_case * tc,void * data)68 static void skiplist_init(abts_case *tc, void *data)
69 {
70 apr_time_t now = apr_time_now();
71 srand((unsigned int)(((now >> 32) ^ now) & 0xffffffff));
72
73 ABTS_INT_EQUAL(tc, APR_SUCCESS, apr_skiplist_init(&skiplist, p));
74 ABTS_PTR_NOTNULL(tc, skiplist);
75 apr_skiplist_set_compare(skiplist, (apr_skiplist_compare)strcmp,
76 (apr_skiplist_compare)strcmp);
77 }
78
skiplist_find(abts_case * tc,void * data)79 static void skiplist_find(abts_case *tc, void *data)
80 {
81 const char *val;
82
83 ABTS_PTR_NOTNULL(tc, apr_skiplist_insert(skiplist, "baton"));
84 val = apr_skiplist_find(skiplist, "baton", NULL);
85 ABTS_PTR_NOTNULL(tc, val);
86 ABTS_STR_EQUAL(tc, "baton", val);
87 }
88
skiplist_dontfind(abts_case * tc,void * data)89 static void skiplist_dontfind(abts_case *tc, void *data)
90 {
91 const char *val;
92
93 val = apr_skiplist_find(skiplist, "keynotthere", NULL);
94 ABTS_PTR_EQUAL(tc, NULL, (void *)val);
95 }
96
skiplist_insert(abts_case * tc,void * data)97 static void skiplist_insert(abts_case *tc, void *data)
98 {
99 const char *val;
100 int i;
101
102 for (i = 0; i < 10; ++i) {
103 ABTS_PTR_EQUAL(tc, NULL, apr_skiplist_insert(skiplist, "baton"));
104 ABTS_TRUE(tc, 1 == skiplist_get_size(tc, skiplist));
105 val = apr_skiplist_find(skiplist, "baton", NULL);
106 ABTS_PTR_NOTNULL(tc, val);
107 ABTS_STR_EQUAL(tc, "baton", val);
108 }
109
110 ABTS_PTR_NOTNULL(tc, apr_skiplist_insert(skiplist, "foo"));
111 ABTS_TRUE(tc, 2 == skiplist_get_size(tc, skiplist));
112 val = apr_skiplist_find(skiplist, "foo", NULL);
113 ABTS_PTR_NOTNULL(tc, val);
114 ABTS_STR_EQUAL(tc, "foo", val);
115
116 ABTS_PTR_NOTNULL(tc, apr_skiplist_insert(skiplist, "atfirst"));
117 ABTS_TRUE(tc, 3 == skiplist_get_size(tc, skiplist));
118 val = apr_skiplist_find(skiplist, "atfirst", NULL);
119 ABTS_PTR_NOTNULL(tc, val);
120 ABTS_STR_EQUAL(tc, "atfirst", val);
121 }
122
skiplist_add(abts_case * tc,void * data)123 static void skiplist_add(abts_case *tc, void *data)
124 {
125 const char *val;
126 size_t i, n = skiplist_get_size(tc, skiplist);
127
128 for (i = 0; i < 100; ++i) {
129 n++;
130 ABTS_PTR_NOTNULL(tc, apr_skiplist_add(skiplist, "daton"));
131 ABTS_TRUE(tc, n == skiplist_get_size(tc, skiplist));
132 val = apr_skiplist_find(skiplist, "daton", NULL);
133 ABTS_PTR_NOTNULL(tc, val);
134 ABTS_STR_EQUAL(tc, "daton", val);
135
136 n++;
137 ABTS_PTR_NOTNULL(tc, apr_skiplist_add(skiplist, "baton"));
138 ABTS_TRUE(tc, n == skiplist_get_size(tc, skiplist));
139 val = apr_skiplist_find(skiplist, "baton", NULL);
140 ABTS_PTR_NOTNULL(tc, val);
141 ABTS_STR_EQUAL(tc, "baton", val);
142
143 n++;
144 ABTS_PTR_NOTNULL(tc, apr_skiplist_add(skiplist, "caton"));
145 ABTS_TRUE(tc, n == skiplist_get_size(tc, skiplist));
146 val = apr_skiplist_find(skiplist, "caton", NULL);
147 ABTS_PTR_NOTNULL(tc, val);
148 ABTS_STR_EQUAL(tc, "caton", val);
149
150 n++;
151 ABTS_PTR_NOTNULL(tc, apr_skiplist_add(skiplist, "aaton"));
152 ABTS_TRUE(tc, n == skiplist_get_size(tc, skiplist));
153 val = apr_skiplist_find(skiplist, "aaton", NULL);
154 ABTS_PTR_NOTNULL(tc, val);
155 ABTS_STR_EQUAL(tc, "aaton", val);
156 }
157 }
158
skiplist_destroy(abts_case * tc,void * data)159 static void skiplist_destroy(abts_case *tc, void *data)
160 {
161 apr_skiplist_destroy(skiplist, NULL);
162 ABTS_TRUE(tc, 0 == skiplist_get_size(tc, skiplist));
163 }
164
skiplist_size(abts_case * tc,void * data)165 static void skiplist_size(abts_case *tc, void *data)
166 {
167 const char *val;
168
169 ABTS_TRUE(tc, 0 == skiplist_get_size(tc, skiplist));
170
171 ABTS_PTR_NOTNULL(tc, apr_skiplist_insert(skiplist, "abc"));
172 ABTS_PTR_NOTNULL(tc, apr_skiplist_insert(skiplist, "ghi"));
173 ABTS_PTR_NOTNULL(tc, apr_skiplist_insert(skiplist, "def"));
174 val = apr_skiplist_find(skiplist, "abc", NULL);
175 ABTS_PTR_NOTNULL(tc, val);
176 ABTS_STR_EQUAL(tc, "abc", val);
177 val = apr_skiplist_find(skiplist, "ghi", NULL);
178 ABTS_PTR_NOTNULL(tc, val);
179 ABTS_STR_EQUAL(tc, "ghi", val);
180 val = apr_skiplist_find(skiplist, "def", NULL);
181 ABTS_PTR_NOTNULL(tc, val);
182 ABTS_STR_EQUAL(tc, "def", val);
183
184 ABTS_TRUE(tc, 3 == skiplist_get_size(tc, skiplist));
185 apr_skiplist_destroy(skiplist, NULL);
186 }
187
skiplist_remove(abts_case * tc,void * data)188 static void skiplist_remove(abts_case *tc, void *data)
189 {
190 const char *val;
191
192 ABTS_TRUE(tc, 0 == skiplist_get_size(tc, skiplist));
193
194 ABTS_PTR_NOTNULL(tc, apr_skiplist_add(skiplist, "baton"));
195 ABTS_TRUE(tc, 1 == skiplist_get_size(tc, skiplist));
196 val = apr_skiplist_find(skiplist, "baton", NULL);
197 ABTS_PTR_NOTNULL(tc, val);
198 ABTS_STR_EQUAL(tc, "baton", val);
199
200 ABTS_PTR_NOTNULL(tc, apr_skiplist_add(skiplist, "baton"));
201 ABTS_TRUE(tc, 2 == skiplist_get_size(tc, skiplist));
202 val = apr_skiplist_find(skiplist, "baton", NULL);
203 ABTS_PTR_NOTNULL(tc, val);
204 ABTS_STR_EQUAL(tc, "baton", val);
205
206 ABTS_TRUE(tc, apr_skiplist_remove(skiplist, "baton", NULL) != 0);
207 ABTS_TRUE(tc, 1 == skiplist_get_size(tc, skiplist));
208 val = apr_skiplist_find(skiplist, "baton", NULL);
209 ABTS_PTR_NOTNULL(tc, val);
210 ABTS_STR_EQUAL(tc, "baton", val);
211
212 ABTS_PTR_NOTNULL(tc, apr_skiplist_add(skiplist, "baton"));
213 ABTS_TRUE(tc, 2 == skiplist_get_size(tc, skiplist));
214 val = apr_skiplist_find(skiplist, "baton", NULL);
215 ABTS_PTR_NOTNULL(tc, val);
216 ABTS_STR_EQUAL(tc, "baton", val);
217
218 /* remove all "baton"s */
219 while (apr_skiplist_remove(skiplist, "baton", NULL))
220 ;
221 ABTS_TRUE(tc, 0 == skiplist_get_size(tc, skiplist));
222 val = apr_skiplist_find(skiplist, "baton", NULL);
223 ABTS_PTR_EQUAL(tc, NULL, val);
224 }
225
226 #define NUM_RAND (100)
227 #define NUM_FIND (3 * NUM_RAND)
skiplist_random_loop(abts_case * tc,void * data)228 static void skiplist_random_loop(abts_case *tc, void *data)
229 {
230 char **batons;
231 apr_skiplist *sl;
232 const char *val;
233 int i;
234
235 ABTS_INT_EQUAL(tc, APR_SUCCESS, apr_skiplist_init(&sl, ptmp));
236 apr_skiplist_set_compare(sl, (apr_skiplist_compare)strcmp,
237 (apr_skiplist_compare)strcmp);
238
239 batons = apr_palloc(ptmp, NUM_FIND * sizeof(char*));
240
241 for (i = 0; i < NUM_FIND; ++i) {
242 if (i < NUM_RAND) {
243 batons[i] = apr_psprintf(ptmp, "%.6u", rand() % 1000000);
244 }
245 else {
246 batons[i] = apr_pstrdup(ptmp, batons[i % NUM_RAND]);
247 }
248 ABTS_PTR_NOTNULL(tc, apr_skiplist_add(sl, batons[i]));
249 val = apr_skiplist_find(sl, batons[i], NULL);
250 ABTS_PTR_NOTNULL(tc, val);
251 ABTS_STR_EQUAL(tc, batons[i], val);
252 }
253
254 apr_pool_clear(ptmp);
255 }
256
257 typedef struct elem {
258 int b;
259 int a;
260 } elem;
261
262
add_int_to_skiplist(abts_case * tc,apr_skiplist * list,int n)263 static void add_int_to_skiplist(abts_case *tc, apr_skiplist *list, int n){
264 int* a = apr_skiplist_alloc(list, sizeof(int));
265 *a = n;
266 ABTS_PTR_NOTNULL(tc, apr_skiplist_insert(list, a));
267 }
268
add_elem_to_skiplist(abts_case * tc,apr_skiplist * list,elem n)269 static void add_elem_to_skiplist(abts_case *tc, apr_skiplist *list, elem n){
270 elem* a = apr_skiplist_alloc(list, sizeof(elem));
271 *a = n;
272 ABTS_PTR_NOTNULL(tc, apr_skiplist_insert(list, a));
273 }
274
comp(void * a,void * b)275 static int comp(void *a, void *b){
276 return (*((int*) a) < *((int*) b)) ? -1 : 1;
277 }
278
scomp(void * a,void * b)279 static int scomp(void *a, void *b){
280 return (((elem*) a)->a < ((elem*) b)->a) ? -1 : 1;
281 }
282
ecomp(void * a,void * b)283 static int ecomp(void *a, void *b)
284 {
285 elem const * const e1 = a;
286 elem const * const e2 = b;
287 if (e1->a < e2->a) {
288 return -1;
289 }
290 else if (e1->a > e2->a) {
291 return +1;
292 }
293 else if (e1->b < e2->b) {
294 return -1;
295 }
296 else if (e1->b > e2->b) {
297 return +1;
298 }
299 else {
300 return 0;
301 }
302 }
303
skiplist_test(abts_case * tc,void * data)304 static void skiplist_test(abts_case *tc, void *data) {
305 int test_elems = 10;
306 int i = 0, j = 0;
307 int *val = NULL;
308 elem *val2 = NULL;
309 apr_skiplist * list = NULL;
310 apr_skiplist * list2 = NULL;
311 apr_skiplist * list3 = NULL;
312 int first_forty_two = 42,
313 second_forty_two = 42;
314 apr_array_header_t *array;
315 elem t1, t2, t3, t4, t5;
316 t1.a = 1; t1.b = 1;
317 t2.a = 42; t2.b = 1;
318 t3.a = 42; t3.b = 2;
319 t4.a = 42; t4.b = 3;
320 t5.a = 142; t5.b = 1;
321
322 ABTS_INT_EQUAL(tc, APR_SUCCESS, apr_skiplist_init(&list, ptmp));
323 apr_skiplist_set_compare(list, comp, comp);
324
325 /* insert 10 objects */
326 for (i = 0; i < test_elems; ++i){
327 add_int_to_skiplist(tc, list, i);
328 }
329
330 /* remove all objects */
331 while ((val = apr_skiplist_pop(list, NULL))){
332 ABTS_INT_EQUAL(tc, *val, j++);
333 }
334
335 /* insert 10 objects again */
336 for (i = test_elems; i < test_elems+test_elems; ++i){
337 add_int_to_skiplist(tc, list, i);
338 }
339
340 j = test_elems;
341 while ((val = apr_skiplist_pop(list, NULL))){
342 ABTS_INT_EQUAL(tc, *val, j++);
343 }
344
345 /* empty */
346 val = apr_skiplist_pop(list, NULL);
347 ABTS_PTR_EQUAL(tc, val, NULL);
348
349 add_int_to_skiplist(tc, list, 42);
350 val = apr_skiplist_pop(list, NULL);
351 ABTS_INT_EQUAL(tc, *val, 42);
352
353 /* empty */
354 val = apr_skiplist_pop(list, NULL);
355 ABTS_PTR_EQUAL(tc, val, NULL);
356
357 ABTS_PTR_NOTNULL(tc, apr_skiplist_add(list, &first_forty_two));
358 add_int_to_skiplist(tc, list, 1);
359 add_int_to_skiplist(tc, list, 142);
360 ABTS_PTR_NOTNULL(tc, apr_skiplist_add(list, &second_forty_two));
361 val = apr_skiplist_peek(list);
362 ABTS_INT_EQUAL(tc, *val, 1);
363 val = apr_skiplist_pop(list, NULL);
364 ABTS_INT_EQUAL(tc, *val, 1);
365 val = apr_skiplist_peek(list);
366 ABTS_PTR_EQUAL(tc, val, &first_forty_two);
367 ABTS_INT_EQUAL(tc, *val, 42);
368 val = apr_skiplist_pop(list, NULL);
369 ABTS_PTR_EQUAL(tc, val, &first_forty_two);
370 ABTS_INT_EQUAL(tc, *val, 42);
371 val = apr_skiplist_pop(list, NULL);
372 ABTS_PTR_EQUAL(tc, val, &second_forty_two);
373 ABTS_INT_EQUAL(tc, *val, 42);
374 val = apr_skiplist_peek(list);
375 ABTS_INT_EQUAL(tc, *val, 142);
376
377 ABTS_INT_EQUAL(tc, APR_SUCCESS, apr_skiplist_init(&list2, ptmp));
378 apr_skiplist_set_compare(list2, scomp, scomp);
379 add_elem_to_skiplist(tc, list2, t2);
380 add_elem_to_skiplist(tc, list2, t1);
381 add_elem_to_skiplist(tc, list2, t3);
382 add_elem_to_skiplist(tc, list2, t5);
383 add_elem_to_skiplist(tc, list2, t4);
384 val2 = apr_skiplist_pop(list2, NULL);
385 ABTS_INT_EQUAL(tc, val2->a, 1);
386 val2 = apr_skiplist_pop(list2, NULL);
387 ABTS_INT_EQUAL(tc, val2->a, 42);
388 ABTS_INT_EQUAL(tc, val2->b, 1);
389 val2 = apr_skiplist_pop(list2, NULL);
390 ABTS_INT_EQUAL(tc, val2->a, 42);
391 ABTS_INT_EQUAL(tc, val2->b, 2);
392 val2 = apr_skiplist_pop(list2, NULL);
393 ABTS_INT_EQUAL(tc, val2->a, 42);
394 ABTS_INT_EQUAL(tc, val2->b, 3);
395 val2 = apr_skiplist_pop(list2, NULL);
396 ABTS_INT_EQUAL(tc, val2->a, 142);
397 ABTS_INT_EQUAL(tc, val2->b, 1);
398
399 ABTS_INT_EQUAL(tc, APR_SUCCESS, apr_skiplist_init(&list3, ptmp));
400 apr_skiplist_set_compare(list3, ecomp, ecomp);
401 array = apr_array_make(ptmp, 10, sizeof(elem *));
402 for (i = 0; i < 10; ++i) {
403 elem *e = apr_palloc(ptmp, sizeof *e);
404 e->a = 4224;
405 e->b = i;
406 APR_ARRAY_PUSH(array, elem *) = e;
407 ABTS_PTR_NOTNULL(tc, apr_skiplist_insert(list3, e));
408 }
409 for (i = 0; i < 5; ++i) {
410 elem *e = APR_ARRAY_IDX(array, i, elem *);
411 val2 = apr_skiplist_find(list3, e, NULL);
412 ABTS_PTR_EQUAL(tc, e, val2);
413 ABTS_TRUE(tc, apr_skiplist_remove(list3, e, NULL) != 0);
414 }
415 for (i = 0; i < 5; ++i) {
416 elem *e = APR_ARRAY_IDX(array, 9 - i, elem *);
417 val2 = apr_skiplist_find(list3, e, NULL);
418 ABTS_PTR_EQUAL(tc, e, val2);
419 ABTS_TRUE(tc, apr_skiplist_remove(list3, e, NULL) != 0);
420 }
421
422 apr_pool_clear(ptmp);
423 }
424
425
testskiplist(abts_suite * suite)426 abts_suite *testskiplist(abts_suite *suite)
427 {
428 suite = ADD_SUITE(suite)
429
430 apr_pool_create(&ptmp, p);
431
432 abts_run_test(suite, skiplist_init, NULL);
433 abts_run_test(suite, skiplist_find, NULL);
434 abts_run_test(suite, skiplist_dontfind, NULL);
435 abts_run_test(suite, skiplist_insert, NULL);
436 abts_run_test(suite, skiplist_add, NULL);
437 abts_run_test(suite, skiplist_destroy, NULL);
438 abts_run_test(suite, skiplist_size, NULL);
439 abts_run_test(suite, skiplist_remove, NULL);
440 abts_run_test(suite, skiplist_random_loop, NULL);
441
442 abts_run_test(suite, skiplist_test, NULL);
443
444 apr_pool_destroy(ptmp);
445
446 return suite;
447 }
448
449