BadVPN – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 /**
2 * @file cavl_test.c
3 * @author Ambroz Bizjak <ambrop7@gmail.com>
4 *
5 * @section LICENSE
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * 3. Neither the name of the author nor the
15 * names of its contributors may be used to endorse or promote products
16 * derived from this software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
20 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
22 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
24 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
25 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
27 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29  
30 #include <stdio.h>
31 #include <stdlib.h>
32 #include <time.h>
33 #include <stdint.h>
34 #include <limits.h>
35  
36 #include <misc/balloc.h>
37 #include <misc/compare.h>
38 #include <misc/debug.h>
39 #include <misc/print_macros.h>
40 #include <structure/CAvl.h>
41  
42 #define USE_COUNTS 0
43 #define USE_ASSOC 1
44  
45 typedef size_t entry_index;
46 #define MAX_INDICES SIZE_MAX
47  
48 typedef uint32_t entry_key;
49  
50 typedef uint8_t assoc_value;
51 typedef uint64_t assoc_sum;
52  
53 struct entry {
54 entry_index tree_child[2];
55 entry_index tree_parent;
56 int8_t tree_balance;
57 #if USE_COUNTS
58 size_t tree_count;
59 #endif
60 #if USE_ASSOC
61 assoc_value assoc_value;
62 assoc_sum assoc_sum;
63 #endif
64 entry_key key;
65 };
66  
67 typedef struct entry *entry_ptr;
68  
69 #include "cavl_test_tree.h"
70 #include <structure/CAvl_decl.h>
71  
72 #include "cavl_test_tree.h"
73 #include <structure/CAvl_impl.h>
74  
75 static void random_bytes (char *buf, size_t len)
76 {
77 while (len > 0) {
78 *((unsigned char *)buf) = rand();
79 buf++;
80 len--;
81 }
82 }
83  
84 static int uint64_less (void *user, uint64_t a, uint64_t b)
85 {
86 return (a < b);
87 }
88  
89 #if USE_ASSOC
90 static MyTreeRef assoc_continue_last_lesser_equal (MyTree *tree, struct entry *arg, MyTreeRef ref, assoc_sum target_sum)
91 {
92 assoc_sum cur_sum = MyTree_ExclusiveAssocPrefixSum(tree, arg, ref);
93 ASSERT(target_sum >= cur_sum)
94 while (cur_sum + ref.ptr->assoc_value <= target_sum) {
95 MyTreeRef next_ref = MyTree_GetNext(tree, arg, ref);
96 if (next_ref.link == -1) {
97 break;
98 }
99 cur_sum += ref.ptr->assoc_value;
100 ref = next_ref;
101 }
102 return ref;
103 }
104 #endif
105  
106 static void test_assoc (MyTree *tree, struct entry *arg)
107 {
108 #if USE_ASSOC
109 assoc_sum sum = 0;
110 for (MyTreeRef ref = MyTree_GetFirst(tree, arg); ref.link != -1; ref = MyTree_GetNext(tree, arg, ref)) {
111 assoc_sum tree_sum = MyTree_ExclusiveAssocPrefixSum(tree, arg, ref);
112 ASSERT_FORCE(tree_sum == sum);
113 ASSERT_FORCE(MyTree_FindLastExclusiveAssocPrefixSumLesserEqual(tree, arg, sum, uint64_less, NULL).link == assoc_continue_last_lesser_equal(tree, arg, ref, sum).link);
114 ASSERT_FORCE(MyTree_FindLastExclusiveAssocPrefixSumLesserEqual(tree, arg, sum + 1, uint64_less, NULL).link == assoc_continue_last_lesser_equal(tree, arg, ref, sum + 1).link);
115 sum += ref.ptr->assoc_value;
116 }
117 ASSERT_FORCE(sum == MyTree_AssocSum(tree, arg));
118 #endif
119 }
120  
121 int main (int argc, char *argv[])
122 {
123 //srand(time(NULL));
124  
125 printf("sizeof(struct entry)=%" PRIsz "\n", sizeof(struct entry));
126  
127 if (argc != 6) {
128 fprintf(stderr, "Usage: %s <num_keys> <num_lookups> <num_remove> <do_remove=1/0> <do_verify=1/0>\n", (argc > 0 ? argv[0] : ""));
129 return 1;
130 }
131  
132 size_t num_keys = atoi(argv[1]);
133 size_t num_lookups = atoi(argv[2]);
134 size_t num_remove = atoi(argv[3]);
135 size_t do_remove = atoi(argv[4]);
136 size_t do_verify = atoi(argv[5]);
137  
138 printf("Allocating keys...\n");
139 entry_key *keys = (entry_key *)BAllocArray(num_keys, sizeof(keys[0]));
140 ASSERT_FORCE(keys);
141  
142 printf("Generating random keys...\n");
143 random_bytes((char *)keys, num_keys * sizeof(keys[0]));
144  
145 printf("Allocating lookup indices...\n");
146 uint64_t *lookup_indices = (uint64_t *)BAllocArray(num_lookups, sizeof(lookup_indices[0]));
147 ASSERT_FORCE(lookup_indices);
148  
149 printf("Generating random lookup indices...\n");
150 random_bytes((char *)lookup_indices, num_lookups * sizeof(lookup_indices[0]));
151  
152 printf("Allocating remove indices...\n");
153 uint64_t *remove_indices = (uint64_t *)BAllocArray(num_remove, sizeof(remove_indices[0]));
154 ASSERT_FORCE(remove_indices);
155  
156 printf("Generating random remove indices...\n");
157 random_bytes((char *)remove_indices, num_remove * sizeof(remove_indices[0]));
158  
159 #if USE_ASSOC
160 printf("Allocating assoc values...\n");
161 assoc_value *assoc_values = (assoc_value *)BAllocArray(num_keys, sizeof(assoc_values[0]));
162 ASSERT_FORCE(assoc_values);
163  
164 printf("Generating random assoc values...\n");
165 random_bytes((char *)assoc_values, num_keys * sizeof(assoc_values[0]));
166 #endif
167  
168 printf("Allocating entries...\n");
169 ASSERT_FORCE(num_keys <= MAX_INDICES);
170 struct entry *entries = (struct entry *)BAllocArray(num_keys, sizeof(*entries));
171 ASSERT_FORCE(entries);
172 entry_index num_used_entries = 0;
173  
174 MyTree tree;
175 MyTree_Init(&tree);
176  
177 struct entry *arg = entries;
178  
179 ASSERT_FORCE(MyTree_IsEmpty(&tree));
180 #if USE_COUNTS
181 ASSERT_FORCE(MyTree_Count(&tree, arg) == 0);
182 #endif
183 test_assoc(&tree, arg);
184  
185 size_t num;
186 #if USE_COUNTS
187 size_t prevNum;
188 #endif
189  
190 printf("Inserting random numbers...\n");
191 num = 0;
192 for (size_t i = 0; i < num_keys; i++) {
193 entries[num_used_entries].key = keys[i];
194 #if USE_ASSOC
195 entries[num_used_entries].assoc_value = assoc_values[i];
196 #endif
197 MyTreeRef ref = {&entries[num_used_entries], num_used_entries};
198 if (!MyTree_Insert(&tree, arg, ref, NULL)) {
199 //printf("Insert collision!\n");
200 continue;
201 }
202 num_used_entries++;
203 num++;
204 }
205 printf("Inserted %" PRIsz ".\n", num);
206 #if USE_COUNTS
207 ASSERT_FORCE(MyTree_Count(&tree, arg) == num);
208 #endif
209 if (do_verify) {
210 printf("Verifying...\n");
211 MyTree_Verify(&tree, arg);
212 test_assoc(&tree, arg);
213 }
214  
215 printf("Looking up random inserted keys...\n");
216 for (size_t i = 0; i < num_lookups; i++) {
217 entry_index idx = lookup_indices[i] % num_keys;
218 MyTreeRef entry = MyTree_LookupExact(&tree, arg, keys[idx]);
219 ASSERT_FORCE(!MyTreeIsNullRef(entry));
220 }
221  
222 #if USE_COUNTS
223 prevNum = MyTree_Count(&tree, arg);
224 #endif
225 num = 0;
226 printf("Looking up and removing random inserted keys...\n");
227 for (size_t i = 0; i < num_remove; i++) {
228 entry_index idx = remove_indices[i] % num_keys;
229 MyTreeRef entry = MyTree_LookupExact(&tree, arg, keys[idx]);
230 if (MyTreeIsNullRef(entry)) {
231 //printf("Remove collision!\n");
232 continue;
233 }
234 ASSERT_FORCE(entry.ptr->key == keys[idx]);
235 MyTree_Remove(&tree, arg, entry);
236 num++;
237 }
238 printf("Removed %" PRIsz ".\n", num);
239 #if USE_COUNTS
240 ASSERT_FORCE(MyTree_Count(&tree, arg) == prevNum - num);
241 #endif
242 if (do_verify) {
243 printf("Verifying...\n");
244 MyTree_Verify(&tree, arg);
245 test_assoc(&tree, arg);
246 }
247  
248 if (do_remove) {
249 #if USE_COUNTS
250 prevNum = MyTree_Count(&tree, arg);
251 #endif
252 num = 0;
253 printf("Removing remaining...\n");
254  
255 MyTreeRef cur = MyTree_GetFirst(&tree, arg);
256 while (!MyTreeIsNullRef(cur)) {
257 MyTreeRef prev = cur;
258 cur = MyTree_GetNext(&tree, arg, cur);
259 MyTree_Remove(&tree, arg, prev);
260 num++;
261 }
262  
263 printf("Removed %" PRIsz ".\n", num);
264 ASSERT_FORCE(MyTree_IsEmpty(&tree));
265 #if USE_COUNTS
266 ASSERT_FORCE(MyTree_Count(&tree, arg) == 0);
267 ASSERT_FORCE(num == prevNum);
268 #endif
269 if (do_verify) {
270 printf("Verifying...\n");
271 MyTree_Verify(&tree, arg);
272 }
273 }
274  
275 printf("Freeing...\n");
276 BFree(keys);
277 BFree(lookup_indices);
278 BFree(remove_indices);
279 #if USE_ASSOC
280 BFree(assoc_values);
281 #endif
282 BFree(entries);
283  
284 return 0;
285 }