]>
Commit | Line | Data |
---|---|---|
6c2705cd LR |
1 | /* Copyright (C) 2016 Hewlett Packard Enterprise Development LP |
2 | * All Rights Reserved. | |
3 | * | |
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 | |
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, WITHOUT | |
12 | * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the | |
13 | * License for the specific language governing permissions and limitations | |
14 | * under the License. | |
15 | */ | |
16 | ||
17 | /* A non-exhaustive test for some of the functions and macros declared in | |
18 | * skiplist.h. */ | |
19 | ||
20 | #include <config.h> | |
21 | #undef NDEBUG | |
22 | #include <stdio.h> | |
23 | #include <string.h> | |
24 | #include "ovstest.h" | |
25 | #include "skiplist.h" | |
26 | #include "random.h" | |
27 | #include "util.h" | |
28 | ||
29 | static void | |
30 | test_skiplist_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED); | |
31 | ||
32 | static int test_skiplist_cmp(const void *a, const void *b, const void *conf); | |
33 | ||
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); | |
39 | ||
40 | static int | |
41 | test_skiplist_cmp(const void *a, const void *b, | |
42 | const void *conf OVS_UNUSED) | |
43 | { | |
44 | const int *n = (const int *)a; | |
45 | const int *m = (const int *)b; | |
46 | return (*n > *m) - (*n < *m); | |
47 | } | |
48 | ||
49 | static void | |
50 | test_skiplist_insert(void) | |
51 | { | |
52 | struct skiplist *sl = skiplist_create(test_skiplist_cmp, NULL); | |
53 | int i; | |
54 | int *integer; | |
55 | ||
56 | /* Insert a million rows */ | |
57 | for (i = 0; i < 1000000; i++) { | |
58 | integer = xmalloc(sizeof(int)); | |
59 | *integer = i; | |
60 | skiplist_insert(sl, integer); | |
61 | } | |
62 | ||
63 | /* Check that the skiplist maintains the list sorted */ | |
64 | struct skiplist_node *node = skiplist_first(sl); | |
65 | ||
66 | for (i = 0; i < 1000000; i++) { | |
67 | integer = (int *)skiplist_get_data(node); | |
68 | ovs_assert(i == *integer); | |
69 | node = skiplist_next(node); | |
70 | } | |
71 | ||
72 | skiplist_destroy(sl, free); | |
73 | } | |
74 | ||
75 | static void | |
76 | test_skiplist_delete(void) | |
77 | { | |
78 | struct skiplist *sl = skiplist_create(test_skiplist_cmp, NULL); | |
79 | int a, b, c; | |
80 | a = 1; | |
81 | b = 2; | |
82 | c = 3; | |
83 | /* Insert rows */ | |
84 | skiplist_insert(sl, &a); | |
85 | skiplist_insert(sl, &c); | |
86 | skiplist_insert(sl, &b); | |
87 | ||
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))); | |
92 | ||
93 | /* Delete b*/ | |
94 | skiplist_delete(sl, &b); | |
95 | ||
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))); | |
100 | ||
101 | skiplist_destroy(sl, NULL); | |
102 | } | |
103 | ||
104 | static void | |
105 | test_skiplist_find(void) | |
106 | { | |
107 | struct skiplist *sl = skiplist_create(test_skiplist_cmp, NULL); | |
108 | ||
109 | int i; | |
110 | int *integer; | |
111 | /* Insert a many rows */ | |
112 | for (i = 0; i < 1000000; i++) { | |
113 | integer = xmalloc(sizeof(int)); | |
114 | *integer = i; | |
115 | skiplist_insert(sl, integer); | |
116 | } | |
117 | ||
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); | |
122 | } | |
123 | ||
124 | skiplist_destroy(sl, free); | |
125 | } | |
126 | ||
127 | static void | |
128 | test_skiplist_forward_to(void) | |
129 | { | |
130 | struct skiplist *sl = skiplist_create(test_skiplist_cmp, NULL); | |
131 | int a, b, c, d, x; | |
132 | a = 1; | |
133 | b = 3; | |
134 | c = 7; | |
135 | d = 10; | |
136 | /* Insert rows */ | |
137 | skiplist_insert(sl, &a); | |
138 | skiplist_insert(sl, &c); | |
139 | skiplist_insert(sl, &b); | |
140 | skiplist_insert(sl, &d); | |
141 | ||
142 | /* Check that forward_to returns the expected value */ | |
143 | x = a; | |
144 | ovs_assert(a == *(int *)skiplist_get_data(skiplist_forward_to(sl, &x))); | |
145 | ||
146 | x = 2; | |
147 | ovs_assert(b == *(int *)skiplist_get_data(skiplist_forward_to(sl, &x))); | |
148 | ||
149 | x = 5; | |
150 | ovs_assert(c == *(int *)skiplist_get_data(skiplist_forward_to(sl, &x))); | |
151 | ||
152 | x = 8; | |
153 | ovs_assert(d == *(int *)skiplist_get_data(skiplist_forward_to(sl, &x))); | |
154 | ||
155 | x = 15; | |
156 | ovs_assert(NULL == (int *)skiplist_get_data(skiplist_forward_to(sl, &x))); | |
157 | ||
158 | /* Destroy skiplist */ | |
159 | skiplist_destroy(sl, NULL); | |
160 | } | |
161 | ||
162 | static void | |
163 | test_skiplist_random(void) | |
164 | { | |
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); | |
169 | int i, op, element; | |
170 | for (i = 0; i < total_numbers; i++) { | |
171 | numbers[i] = i; | |
172 | } | |
173 | random_init(); | |
174 | for (i = 0; i < total_numbers * 1000; i++) { | |
175 | op = random_uint32() % 2; | |
176 | element = random_range(total_numbers); | |
177 | if (op == 0) { | |
178 | if (!skiplist_find(sl, &numbers[element])) { | |
179 | expected_count++; | |
180 | } | |
181 | skiplist_insert(sl, &numbers[element]); | |
182 | } else { | |
183 | if (skiplist_find(sl, &numbers[element])) { | |
184 | expected_count--; | |
185 | } | |
186 | skiplist_delete(sl, &numbers[element]); | |
187 | } | |
188 | ovs_assert(expected_count == skiplist_get_size(sl)); | |
189 | } | |
190 | ||
191 | skiplist_destroy(sl, NULL); | |
192 | free(numbers); | |
193 | } | |
194 | ||
195 | static void | |
196 | test_skiplist_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) | |
197 | { | |
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(); | |
208 | printf("\n"); | |
209 | } | |
210 | ||
211 | OVSTEST_REGISTER("test-skiplist", test_skiplist_main); |