BadVPN – Blame information for rev 1
?pathlinks?
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 | } |