1 /*
2 simple rb test tool
3
4 Copyright (C) Ronnie Sahlberg 2007
5
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #include "replace.h"
21 #include "system/time.h"
22
23 #include <talloc.h>
24 #include <assert.h>
25
26 #include "lib/util/dlinklist.h"
27 #include "lib/util/debug.h"
28
29 #include "common/rb_tree.c"
30
31 static struct timeval tp1,tp2;
32
test_sock_addr_to_string(const char * ip,bool with_port)33 static void start_timer(void)
34 {
35 gettimeofday(&tp1,NULL);
36 }
37
38 static double end_timer(void)
39 {
40 gettimeofday(&tp2,NULL);
41 return (tp2.tv_sec + (tp2.tv_usec*1.0e-6)) -
42 (tp1.tv_sec + (tp1.tv_usec*1.0e-6));
43 }
44
45 int num_records=5;
test_sock_addr_from_string_bad(const char * ip,bool with_port)46
47 static void *callback(void *p, void *d)
48 {
49 uint32_t *data = (uint32_t *)d;
50
51 if (d==NULL) {
52 data = (uint32_t *)p;
53 }
54
55 (*data)++;
56
57 return data;
58 }
59
60 static void *random_add(void *p, void *d)
61 {
62 return p;
63 }
64
65 static int traverse(void *p, void *d)
66 {
67 uint32_t *data = (uint32_t *)d;
68
test_sock_addr_cmp(const char * ip1,const char * ip2,bool with_port,int res)69 printf("traverse data:%d\n",*data);
70 return 0;
71 }
72
73 static int random_traverse(void *p, void *d)
74 {
75 printf("%s ",(char *)d);
76 return 0;
77 }
78
79 static uint32_t calc_checksum = 0;
80 static int traverse_checksum(void *p, void *d)
81 {
82 int i,j,k;
83
84 sscanf(d, "%d.%d.%d", &i, &j, &k);
85 calc_checksum += i*100+j*10+k;
86 return 0;
87 }
88
89 static int count_traverse(void *p, void *d)
90 {
91 int *count = p;
92 (*count)++;
test_sock_addr_mask_from_string(const char * ip_mask)93 return 0;
94 }
95
96 static int count_traverse_abort(void *p, void *d)
97 {
98 int *count = p;
99 (*count)++;
100 return -1;
101 }
102
103 /*
104 main program
105 */
106 int main(int argc, const char *argv[])
107 {
108 int traverse_count;
test_sock_addr_mask_from_string_bad(const char * ip_mask)109 int i,j,k;
110 trbt_tree_t *tree;
111 uint32_t *data;
112 uint32_t key[3];
113 uint32_t key1[3] = {0,10,20};
114 uint32_t key2[3] = {0,10,21};
115 uint32_t key3[3] = {0,11,20};
116 uint32_t key4[3] = {2,10,20};
117 TALLOC_CTX *memctx;
118 uint32_t **u32array;
119 uint32_t checksum;
120
121 /* testing trbt_insert32_callback for num_records */
122 memctx = talloc_new(NULL);
test_connection_to_string(const char * conn_str)123 assert(memctx != NULL);
124
125 u32array = talloc_array(memctx, uint32_t *, num_records);
126 assert(u32array != NULL);
127
128 tree = trbt_create(memctx, 0);
129 assert(tree != NULL);
130
131 for (i=0; i<num_records; i++) {
132 u32array[i] = talloc(u32array, uint32_t);
133 assert(u32array[i] != NULL);
134 *u32array[i] = 0;
135 trbt_insert32_callback(tree, i, callback, u32array[i]);
136 }
137 for (i=3; i<num_records; i++) {
138 trbt_insert32_callback(tree, i, callback, NULL);
139 }
140
141 /* first 3 keys should have data == 1
142 * the rest of the keys should have data == 2
143 */
144 for (i=0; i<num_records; i++) {
145 data = trbt_lookup32(tree, i);
146 assert(data != NULL);
147 if (i < 3) {
148 assert(*data == 1);
149 } else {
150 assert(*data == 2);
151 }
152 }
153
154 /* deleting key 2 */
155 talloc_free(u32array[2]);
156
157 /* deleting key 1 */
158 talloc_free(u32array[1]);
159
160 assert(talloc_total_size(memctx) == 212);
161
162 /* freeing tree */
163 talloc_free(memctx);
164
165
166 printf("testing trbt_insertarray32_callback\n");
167 memctx = talloc_new(NULL);
168 assert(memctx != NULL);
169
170 tree = trbt_create(memctx, 0);
171 assert(tree != NULL);
172
173 u32array = talloc_array(memctx, uint32_t *, 4);
174 assert(u32array != NULL);
175
176 for (i=0;i<4;i++) {
177 u32array[i] = talloc(u32array, uint32_t);
178 assert(u32array[i] != NULL);
179 *u32array[i] = 0;
180 }
181
test_connection_from_string_bad(const char * conn_str)182 trbt_insertarray32_callback(tree, 3, key1, callback, u32array[0]);
183 trbt_insertarray32_callback(tree, 3, key1, callback, u32array[0]);
184 trbt_insertarray32_callback(tree, 3, key2, callback, u32array[1]);
185 trbt_insertarray32_callback(tree, 3, key3, callback, u32array[2]);
186 trbt_insertarray32_callback(tree, 3, key2, callback, u32array[1]);
187 trbt_insertarray32_callback(tree, 3, key1, callback, u32array[0]);
188
189 data = trbt_lookuparray32(tree, 3, key1);
190 assert(data != NULL && *data == 3);
191 data = trbt_lookuparray32(tree, 3, key2);
192 assert(data != NULL && *data == 2);
193 data = trbt_lookuparray32(tree, 3, key3);
194 assert(data != NULL && *data == 1);
test_connection_list_read(const char * s1,const char * s2)195 data = trbt_lookuparray32(tree, 3, key4);
196 assert(data == NULL);
197 trbt_traversearray32(tree, 3, traverse, NULL);
198
199 printf("\ndeleting key4\n");
200 talloc_free(trbt_lookuparray32(tree, 3, key4));
201
202 data = trbt_lookuparray32(tree, 3, key1);
203 assert(data != NULL && *data == 3);
204 data = trbt_lookuparray32(tree, 3, key2);
205 assert(data != NULL && *data == 2);
206 data = trbt_lookuparray32(tree, 3, key3);
207 assert(data != NULL && *data == 1);
208 data = trbt_lookuparray32(tree, 3, key4);
209 assert(data == NULL);
210 trbt_traversearray32(tree, 3, traverse, NULL);
211
212 printf("\ndeleting key2\n");
213 talloc_free(trbt_lookuparray32(tree, 3, key2));
214
215 data = trbt_lookuparray32(tree, 3, key1);
216 assert(data != NULL && *data == 3);
217 data = trbt_lookuparray32(tree, 3, key2);
218 assert(data == NULL);
219 data = trbt_lookuparray32(tree, 3, key3);
220 assert(data != NULL && *data == 1);
221 data = trbt_lookuparray32(tree, 3, key4);
222 assert(data == NULL);
223 trbt_traversearray32(tree, 3, traverse, NULL);
224
225 printf("\ndeleting key3\n");
226 talloc_free(trbt_lookuparray32(tree, 3, key3));
227
228 data = trbt_lookuparray32(tree, 3, key1);
229 assert(data != NULL && *data == 3);
230 data = trbt_lookuparray32(tree, 3, key2);
231 assert(data == NULL);
232 data = trbt_lookuparray32(tree, 3, key3);
233 assert(data == NULL);
234 data = trbt_lookuparray32(tree, 3, key4);
235 assert(data == NULL);
236 trbt_traversearray32(tree, 3, traverse, NULL);
237
238 printf("\ndeleting key1\n");
239 talloc_free(trbt_lookuparray32(tree, 3, key1));
240
241 data = trbt_lookuparray32(tree, 3, key1);
242 assert(data == NULL);
243 data = trbt_lookuparray32(tree, 3, key2);
244 assert(data == NULL);
test_connection_list_read_bad(const char * s1)245 data = trbt_lookuparray32(tree, 3, key3);
246 assert(data == NULL);
247 data = trbt_lookuparray32(tree, 3, key4);
248 assert(data == NULL);
249 trbt_traversearray32(tree, 3, traverse, NULL);
250
251 talloc_free(tree);
252 talloc_free(memctx);
253
254
255 printf("\nrun random insert and delete for 60 seconds\n");
256 memctx = talloc_new(NULL);
257 assert(memctx != NULL);
258
259 tree = trbt_create(memctx, 0);
260 assert(tree != NULL);
261
262 i=0;
263 start_timer();
264 checksum = 0;
265 /* add and delete nodes from a 3 level tree fro 60 seconds.
266 each time a node is added or deleted, traverse the tree and
267 compute a checksum over the data stored in the tree and compare this
268 with a checksum we keep which contains what the checksum should be
269 */
270 while(end_timer() < 60.0){
271 char *str;
272
273 i++;
274 key[0]=random()%10;
275 key[1]=random()%10;
276 key[2]=random()%10;
277
278 if (random()%2) {
279 if (trbt_lookuparray32(tree, 3, key) == NULL) {
280 /* this node does not yet exist, add it to the
281 tree and update the checksum
282 */
283 str=talloc_asprintf(memctx, "%d.%d.%d", key[0],key[1],key[2]);
284 trbt_insertarray32_callback(tree, 3, key, random_add, str);
285 checksum += key[0]*100+key[1]*10+key[2];
286 }
287 } else {
288 if ((str=trbt_lookuparray32(tree, 3, key)) != NULL) {
289 /* this node does exist in the tree, delete
290 it and update the checksum accordingly
291 */
292 talloc_free(str);
293 checksum -= key[0]*100+key[1]*10+key[2];
294 }
295 }
296 /* traverse all nodes in the tree and calculate the checksum
297 it better match the one we keep track of in
298 'checksum'
299 */
300 calc_checksum = 0;
301 trbt_traversearray32(tree, 3, traverse_checksum, NULL);
302 assert(checksum == calc_checksum);
303 }
304
305 /*
306 printf("\niterations passed:%d\n", i);
307 trbt_traversearray32(tree, 3, random_traverse, NULL);
308 printf("\n");
309 printf("first node: %s\n", (char *)trbt_findfirstarray32(tree, 3));
310 */
311
312 traverse_count = 0;
313 trbt_traversearray32(tree, 3, count_traverse, &traverse_count);
314 assert(traverse_count > 0);
315
316 traverse_count = 0;
317 trbt_traversearray32(tree, 3, count_traverse_abort, &traverse_count);
318 assert(traverse_count == 1);
319
320 printf("\ndeleting all entries\n");
321 for(i=0;i<10;i++){
322 for(j=0;j<10;j++){
323 for(k=0;k<10;k++){
324 key[0]=i;
325 key[1]=j;
main(int argc,char * argv[])326 key[2]=k;
327 talloc_free(trbt_lookuparray32(tree, 3, key));
328 }
329 }
330 }
331 trbt_traversearray32(tree, 3, random_traverse, NULL);
332
333 assert(talloc_total_size(memctx) == 16);
334
335 return 0;
336 }
337