1 /*
2 *
3 * Copyright 2015 gRPC authors.
4 *
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 *
17 */
18
19 #include "src/core/lib/avl/avl.h"
20
21 #include <stdio.h>
22 #include <string.h>
23
24 #include <grpc/support/alloc.h>
25 #include <grpc/support/log.h>
26
27 #include "src/core/lib/gpr/useful.h"
28 #include "test/core/util/test_config.h"
29
box(int x)30 static int* box(int x) {
31 int* b = static_cast<int*>(gpr_malloc(sizeof(*b)));
32 *b = x;
33 return b;
34 }
35
int_compare(void * int1,void * int2,void * unused)36 static long int_compare(void* int1, void* int2, void* unused) {
37 return (*static_cast<int*>(int1)) - (*static_cast<int*>(int2));
38 }
int_copy(void * p,void * unused)39 static void* int_copy(void* p, void* unused) {
40 return box(*static_cast<int*>(p));
41 }
42
destroy(void * p,void * unused)43 static void destroy(void* p, void* unused) { gpr_free(p); }
44
45 static const grpc_avl_vtable int_int_vtable = {destroy, int_copy, int_compare,
46 destroy, int_copy};
47
check_get(grpc_avl avl,int key,int value)48 static void check_get(grpc_avl avl, int key, int value) {
49 int* k = box(key);
50 GPR_ASSERT(*(int*)grpc_avl_get(avl, k, nullptr) == value);
51 gpr_free(k);
52 }
53
check_negget(grpc_avl avl,int key)54 static void check_negget(grpc_avl avl, int key) {
55 int* k = box(key);
56 GPR_ASSERT(grpc_avl_get(avl, k, nullptr) == nullptr);
57 gpr_free(k);
58 }
59
remove_int(grpc_avl avl,int key)60 static grpc_avl remove_int(grpc_avl avl, int key) {
61 int* k = box(key);
62 avl = grpc_avl_remove(avl, k, nullptr);
63 gpr_free(k);
64 return avl;
65 }
66
test_get(void)67 static void test_get(void) {
68 grpc_avl avl;
69 gpr_log(GPR_DEBUG, "test_get");
70 avl = grpc_avl_create(&int_int_vtable);
71 avl = grpc_avl_add(avl, box(1), box(11), nullptr);
72 avl = grpc_avl_add(avl, box(2), box(22), nullptr);
73 avl = grpc_avl_add(avl, box(3), box(33), nullptr);
74 check_get(avl, 1, 11);
75 check_get(avl, 2, 22);
76 check_get(avl, 3, 33);
77 check_negget(avl, 4);
78 grpc_avl_unref(avl, nullptr);
79 }
80
test_ll(void)81 static void test_ll(void) {
82 grpc_avl avl;
83 gpr_log(GPR_DEBUG, "test_ll");
84 avl = grpc_avl_create(&int_int_vtable);
85 avl = grpc_avl_add(avl, box(5), box(1), nullptr);
86 avl = grpc_avl_add(avl, box(4), box(2), nullptr);
87 avl = grpc_avl_add(avl, box(3), box(3), nullptr);
88 GPR_ASSERT(*(int*)avl.root->key == 4);
89 GPR_ASSERT(*(int*)avl.root->left->key == 3);
90 GPR_ASSERT(*(int*)avl.root->right->key == 5);
91 grpc_avl_unref(avl, nullptr);
92 }
93
test_lr(void)94 static void test_lr(void) {
95 grpc_avl avl;
96 gpr_log(GPR_DEBUG, "test_lr");
97 avl = grpc_avl_create(&int_int_vtable);
98 avl = grpc_avl_add(avl, box(5), box(1), nullptr);
99 avl = grpc_avl_add(avl, box(3), box(2), nullptr);
100 avl = grpc_avl_add(avl, box(4), box(3), nullptr);
101 GPR_ASSERT(*(int*)avl.root->key == 4);
102 GPR_ASSERT(*(int*)avl.root->left->key == 3);
103 GPR_ASSERT(*(int*)avl.root->right->key == 5);
104 grpc_avl_unref(avl, nullptr);
105 }
106
test_rr(void)107 static void test_rr(void) {
108 grpc_avl avl;
109 gpr_log(GPR_DEBUG, "test_rr");
110 avl = grpc_avl_create(&int_int_vtable);
111 avl = grpc_avl_add(avl, box(3), box(1), nullptr);
112 avl = grpc_avl_add(avl, box(4), box(2), nullptr);
113 avl = grpc_avl_add(avl, box(5), box(3), nullptr);
114 GPR_ASSERT(*(int*)avl.root->key == 4);
115 GPR_ASSERT(*(int*)avl.root->left->key == 3);
116 GPR_ASSERT(*(int*)avl.root->right->key == 5);
117 grpc_avl_unref(avl, nullptr);
118 }
119
test_rl(void)120 static void test_rl(void) {
121 grpc_avl avl;
122 gpr_log(GPR_DEBUG, "test_rl");
123 avl = grpc_avl_create(&int_int_vtable);
124 avl = grpc_avl_add(avl, box(3), box(1), nullptr);
125 avl = grpc_avl_add(avl, box(5), box(2), nullptr);
126 avl = grpc_avl_add(avl, box(4), box(3), nullptr);
127 GPR_ASSERT(*(int*)avl.root->key == 4);
128 GPR_ASSERT(*(int*)avl.root->left->key == 3);
129 GPR_ASSERT(*(int*)avl.root->right->key == 5);
130 grpc_avl_unref(avl, nullptr);
131 }
132
test_unbalanced(void)133 static void test_unbalanced(void) {
134 grpc_avl avl;
135 gpr_log(GPR_DEBUG, "test_unbalanced");
136 avl = grpc_avl_create(&int_int_vtable);
137 avl = grpc_avl_add(avl, box(5), box(1), nullptr);
138 avl = grpc_avl_add(avl, box(4), box(2), nullptr);
139 avl = grpc_avl_add(avl, box(3), box(3), nullptr);
140 avl = grpc_avl_add(avl, box(2), box(4), nullptr);
141 avl = grpc_avl_add(avl, box(1), box(5), nullptr);
142 GPR_ASSERT(*(int*)avl.root->key == 4);
143 GPR_ASSERT(*(int*)avl.root->left->key == 2);
144 GPR_ASSERT(*(int*)avl.root->left->left->key == 1);
145 GPR_ASSERT(*(int*)avl.root->left->right->key == 3);
146 GPR_ASSERT(*(int*)avl.root->right->key == 5);
147 grpc_avl_unref(avl, nullptr);
148 }
149
test_replace(void)150 static void test_replace(void) {
151 grpc_avl avl;
152 gpr_log(GPR_DEBUG, "test_replace");
153 avl = grpc_avl_create(&int_int_vtable);
154 avl = grpc_avl_add(avl, box(1), box(1), nullptr);
155 avl = grpc_avl_add(avl, box(1), box(2), nullptr);
156 check_get(avl, 1, 2);
157 check_negget(avl, 2);
158 grpc_avl_unref(avl, nullptr);
159 }
160
test_remove(void)161 static void test_remove(void) {
162 grpc_avl avl;
163 grpc_avl avl3, avl4, avl5, avln;
164 gpr_log(GPR_DEBUG, "test_remove");
165 avl = grpc_avl_create(&int_int_vtable);
166 avl = grpc_avl_add(avl, box(3), box(1), nullptr);
167 avl = grpc_avl_add(avl, box(4), box(2), nullptr);
168 avl = grpc_avl_add(avl, box(5), box(3), nullptr);
169
170 avl3 = remove_int(grpc_avl_ref(avl, nullptr), 3);
171 avl4 = remove_int(grpc_avl_ref(avl, nullptr), 4);
172 avl5 = remove_int(grpc_avl_ref(avl, nullptr), 5);
173 avln = remove_int(grpc_avl_ref(avl, nullptr), 1);
174
175 grpc_avl_unref(avl, nullptr);
176
177 check_negget(avl3, 3);
178 check_get(avl3, 4, 2);
179 check_get(avl3, 5, 3);
180 grpc_avl_unref(avl3, nullptr);
181
182 check_get(avl4, 3, 1);
183 check_negget(avl4, 4);
184 check_get(avl4, 5, 3);
185 grpc_avl_unref(avl4, nullptr);
186
187 check_get(avl5, 3, 1);
188 check_get(avl5, 4, 2);
189 check_negget(avl5, 5);
190 grpc_avl_unref(avl5, nullptr);
191
192 check_get(avln, 3, 1);
193 check_get(avln, 4, 2);
194 check_get(avln, 5, 3);
195 grpc_avl_unref(avln, nullptr);
196 }
197
test_badcase1(void)198 static void test_badcase1(void) {
199 grpc_avl avl;
200
201 gpr_log(GPR_DEBUG, "test_badcase1");
202
203 avl = grpc_avl_create(&int_int_vtable);
204 avl = grpc_avl_add(avl, box(88), box(1), nullptr);
205 avl = remove_int(avl, 643);
206 avl = remove_int(avl, 983);
207 avl = grpc_avl_add(avl, box(985), box(4), nullptr);
208 avl = grpc_avl_add(avl, box(640), box(5), nullptr);
209 avl = grpc_avl_add(avl, box(41), box(6), nullptr);
210 avl = grpc_avl_add(avl, box(112), box(7), nullptr);
211 avl = grpc_avl_add(avl, box(342), box(8), nullptr);
212 avl = remove_int(avl, 1013);
213 avl = grpc_avl_add(avl, box(434), box(10), nullptr);
214 avl = grpc_avl_add(avl, box(520), box(11), nullptr);
215 avl = grpc_avl_add(avl, box(231), box(12), nullptr);
216 avl = grpc_avl_add(avl, box(852), box(13), nullptr);
217 avl = remove_int(avl, 461);
218 avl = grpc_avl_add(avl, box(108), box(15), nullptr);
219 avl = grpc_avl_add(avl, box(806), box(16), nullptr);
220 avl = grpc_avl_add(avl, box(827), box(17), nullptr);
221 avl = remove_int(avl, 796);
222 avl = grpc_avl_add(avl, box(340), box(19), nullptr);
223 avl = grpc_avl_add(avl, box(498), box(20), nullptr);
224 avl = grpc_avl_add(avl, box(203), box(21), nullptr);
225 avl = grpc_avl_add(avl, box(751), box(22), nullptr);
226 avl = grpc_avl_add(avl, box(150), box(23), nullptr);
227 avl = remove_int(avl, 237);
228 avl = grpc_avl_add(avl, box(830), box(25), nullptr);
229 avl = remove_int(avl, 1007);
230 avl = remove_int(avl, 394);
231 avl = grpc_avl_add(avl, box(65), box(28), nullptr);
232 avl = remove_int(avl, 904);
233 avl = remove_int(avl, 123);
234 avl = grpc_avl_add(avl, box(238), box(31), nullptr);
235 avl = grpc_avl_add(avl, box(184), box(32), nullptr);
236 avl = remove_int(avl, 331);
237 avl = grpc_avl_add(avl, box(827), box(34), nullptr);
238
239 check_get(avl, 830, 25);
240
241 grpc_avl_unref(avl, nullptr);
242 }
243
test_stress(int amount_of_stress)244 static void test_stress(int amount_of_stress) {
245 int added[1024];
246 int i, j;
247 int deletions = 0;
248 grpc_avl avl;
249
250 unsigned seed = static_cast<unsigned>(time(nullptr));
251
252 gpr_log(GPR_DEBUG, "test_stress amount=%d seed=%u", amount_of_stress, seed);
253
254 srand(static_cast<unsigned>(time(nullptr)));
255 avl = grpc_avl_create(&int_int_vtable);
256
257 memset(added, 0, sizeof(added));
258
259 for (i = 1; deletions < amount_of_stress; i++) {
260 int idx = rand() % static_cast<int> GPR_ARRAY_SIZE(added);
261 GPR_ASSERT(i);
262 if (rand() < RAND_MAX / 2) {
263 added[idx] = i;
264 printf("avl = grpc_avl_add(avl, box(%d), box(%d), NULL); /* d=%d */\n",
265 idx, i, deletions);
266 avl = grpc_avl_add(avl, box(idx), box(i), nullptr);
267 } else {
268 deletions += (added[idx] != 0);
269 added[idx] = 0;
270 printf("avl = remove_int(avl, %d); /* d=%d */\n", idx, deletions);
271 avl = remove_int(avl, idx);
272 }
273 for (j = 0; j < static_cast<int> GPR_ARRAY_SIZE(added); j++) {
274 if (added[j] != 0) {
275 check_get(avl, j, added[j]);
276 } else {
277 check_negget(avl, j);
278 }
279 }
280 }
281
282 grpc_avl_unref(avl, nullptr);
283 }
284
main(int argc,char * argv[])285 int main(int argc, char* argv[]) {
286 grpc_test_init(argc, argv);
287
288 test_get();
289 test_ll();
290 test_lr();
291 test_rr();
292 test_rl();
293 test_unbalanced();
294 test_replace();
295 test_remove();
296 test_badcase1();
297 test_stress(10);
298
299 return 0;
300 }
301