]>
git.proxmox.com Git - mirror_ovs.git/blob - tests/test-skiplist.c
1 /* Copyright (C) 2016 Hewlett Packard Enterprise Development LP
4 * Licensed under the Apache License, Version 2.0 (the "License"); you may
5 * not use this file except in compliance with the License. You may obtain
6 * a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13 * License for the specific language governing permissions and limitations
17 /* A non-exhaustive test for some of the functions and macros declared in
30 test_skiplist_main(int argc OVS_UNUSED
, char *argv
[] OVS_UNUSED
);
32 static int test_skiplist_cmp(const void *a
, const void *b
, const void *conf
);
34 static void test_skiplist_insert(void);
35 static void test_skiplist_delete(void);
36 static void test_skiplist_find(void);
37 static void test_skiplist_forward_to(void);
38 static void test_skiplist_random(void);
41 test_skiplist_cmp(const void *a
, const void *b
,
42 const void *conf OVS_UNUSED
)
44 const int *n
= (const int *)a
;
45 const int *m
= (const int *)b
;
46 return (*n
> *m
) - (*n
< *m
);
50 test_skiplist_insert(void)
52 struct skiplist
*sl
= skiplist_create(test_skiplist_cmp
, NULL
);
56 /* Insert a million rows */
57 for (i
= 0; i
< 1000000; i
++) {
58 integer
= xmalloc(sizeof(int));
60 skiplist_insert(sl
, integer
);
63 /* Check that the skiplist maintains the list sorted */
64 struct skiplist_node
*node
= skiplist_first(sl
);
66 for (i
= 0; i
< 1000000; i
++) {
67 integer
= (int *)skiplist_get_data(node
);
68 ovs_assert(i
== *integer
);
69 node
= skiplist_next(node
);
72 skiplist_destroy(sl
, free
);
76 test_skiplist_delete(void)
78 struct skiplist
*sl
= skiplist_create(test_skiplist_cmp
, NULL
);
84 skiplist_insert(sl
, &a
);
85 skiplist_insert(sl
, &c
);
86 skiplist_insert(sl
, &b
);
88 /* Check that the items exists */
89 ovs_assert(a
== *(int *)skiplist_get_data(skiplist_find(sl
, &a
)));
90 ovs_assert(b
== *(int *)skiplist_get_data(skiplist_find(sl
, &b
)));
91 ovs_assert(c
== *(int *)skiplist_get_data(skiplist_find(sl
, &c
)));
94 skiplist_delete(sl
, &b
);
96 /* Check that the items doesn't exists */
97 ovs_assert(a
== *(int *)skiplist_get_data(skiplist_find(sl
, &a
)));
98 ovs_assert(NULL
== skiplist_get_data(skiplist_find(sl
, &b
)));
99 ovs_assert(c
== *(int *)skiplist_get_data(skiplist_find(sl
, &c
)));
101 skiplist_destroy(sl
, NULL
);
105 test_skiplist_find(void)
107 struct skiplist
*sl
= skiplist_create(test_skiplist_cmp
, NULL
);
111 /* Insert a many rows */
112 for (i
= 0; i
< 1000000; i
++) {
113 integer
= xmalloc(sizeof(int));
115 skiplist_insert(sl
, integer
);
118 /* Seek all the items */
119 for (i
= 0; i
< 1000000; i
++) {
120 integer
= (int *)skiplist_get_data(skiplist_find(sl
, &i
));
121 ovs_assert(i
== *integer
);
124 skiplist_destroy(sl
, free
);
128 test_skiplist_forward_to(void)
130 struct skiplist
*sl
= skiplist_create(test_skiplist_cmp
, NULL
);
137 skiplist_insert(sl
, &a
);
138 skiplist_insert(sl
, &c
);
139 skiplist_insert(sl
, &b
);
140 skiplist_insert(sl
, &d
);
142 /* Check that forward_to returns the expected value */
144 ovs_assert(a
== *(int *)skiplist_get_data(skiplist_forward_to(sl
, &x
)));
147 ovs_assert(b
== *(int *)skiplist_get_data(skiplist_forward_to(sl
, &x
)));
150 ovs_assert(c
== *(int *)skiplist_get_data(skiplist_forward_to(sl
, &x
)));
153 ovs_assert(d
== *(int *)skiplist_get_data(skiplist_forward_to(sl
, &x
)));
156 ovs_assert(NULL
== (int *)skiplist_get_data(skiplist_forward_to(sl
, &x
)));
158 /* Destroy skiplist */
159 skiplist_destroy(sl
, NULL
);
163 test_skiplist_random(void)
165 struct skiplist
*sl
= skiplist_create(test_skiplist_cmp
, NULL
);
166 int total_numbers
= 50;
167 int expected_count
= 0;
168 int *numbers
= xmalloc(sizeof(int) * total_numbers
);
170 for (i
= 0; i
< total_numbers
; i
++) {
174 for (i
= 0; i
< total_numbers
* 1000; i
++) {
175 op
= random_uint32() % 2;
176 element
= random_range(total_numbers
);
178 if (!skiplist_find(sl
, &numbers
[element
])) {
181 skiplist_insert(sl
, &numbers
[element
]);
183 if (skiplist_find(sl
, &numbers
[element
])) {
186 skiplist_delete(sl
, &numbers
[element
]);
188 ovs_assert(expected_count
== skiplist_get_size(sl
));
191 skiplist_destroy(sl
, NULL
);
196 test_skiplist_main(int argc OVS_UNUSED
, char *argv
[] OVS_UNUSED
)
198 printf("skiplist insert\n");
199 test_skiplist_insert();
200 printf("skiplist delete\n");
201 test_skiplist_delete();
202 printf("skiplist find\n");
203 test_skiplist_find();
204 printf("skiplist forward_to\n");
205 test_skiplist_forward_to();
206 printf("skiplist random\n");
207 test_skiplist_random();
211 OVSTEST_REGISTER("test-skiplist", test_skiplist_main
);