BadVPN – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 /**
2 * @file savl_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 <stdlib.h>
31 #include <limits.h>
32  
33 #include <misc/debug.h>
34 #include <misc/balloc.h>
35 #include <misc/compare.h>
36 #include <structure/SAvl.h>
37 #include <security/BRandom.h>
38  
39 struct mynode;
40  
41 #include "savl_test_tree.h"
42 #include <structure/SAvl_decl.h>
43  
44 struct mynode {
45 int used;
46 int num;
47 MyTreeNode tree_node;
48 };
49  
50 #include "savl_test_tree.h"
51 #include <structure/SAvl_impl.h>
52  
53 static void verify (MyTree *tree)
54 {
55 printf("Verifying...\n");
56 MyTree_Verify(tree, 0);
57 }
58  
59 int main (int argc, char **argv)
60 {
61 int num_nodes;
62 int num_random_delete;
63  
64 if (argc != 3 || (num_nodes = atoi(argv[1])) <= 0 || (num_random_delete = atoi(argv[2])) < 0) {
65 fprintf(stderr, "Usage: %s <num> <numrandomdelete>\n", (argc > 0 ? argv[0] : NULL));
66 return 1;
67 }
68  
69 struct mynode *nodes = (struct mynode *)BAllocArray(num_nodes, sizeof(*nodes));
70 ASSERT_FORCE(nodes)
71  
72 int *values_ins = (int *)BAllocArray(num_nodes, sizeof(int));
73 ASSERT_FORCE(values_ins)
74  
75 int *values = (int *)BAllocArray(num_random_delete, sizeof(int));
76 ASSERT_FORCE(values)
77  
78 MyTree tree;
79 MyTree_Init(&tree);
80 verify(&tree);
81  
82 printf("Inserting random values...\n");
83 int inserted = 0;
84 BRandom_randomize((uint8_t *)values_ins, num_nodes * sizeof(int));
85 for (int i = 0; i < num_nodes; i++) {
86 nodes[i].num = values_ins[i];
87 if (MyTree_Insert(&tree, 0, &nodes[i], NULL)) {
88 nodes[i].used = 1;
89 inserted++;
90 } else {
91 nodes[i].used = 0;
92 printf("Insert collision!\n");
93 }
94 }
95 printf("Inserted %d entries\n", inserted);
96 ASSERT_FORCE(MyTree_Count(&tree, 0) == inserted)
97 verify(&tree);
98  
99 printf("Removing random entries...\n");
100 int removed1 = 0;
101 BRandom_randomize((uint8_t *)values, num_random_delete * sizeof(int));
102 for (int i = 0; i < num_random_delete; i++) {
103 int index = (((unsigned int *)values)[i] % num_nodes);
104 struct mynode *node = nodes + index;
105 if (node->used) {
106 MyTree_Remove(&tree, 0, node);
107 node->used = 0;
108 removed1++;
109 }
110 }
111 printf("Removed %d entries\n", removed1);
112 ASSERT_FORCE(MyTree_Count(&tree, 0) == inserted - removed1)
113 verify(&tree);
114  
115 printf("Removing remaining...\n");
116 int removed2 = 0;
117 while (!MyTree_IsEmpty(&tree)) {
118 struct mynode *node = MyTree_GetFirst(&tree, 0);
119 ASSERT_FORCE(node->used)
120 MyTree_Remove(&tree, 0, node);
121 node->used = 0;
122 removed2++;
123 }
124 printf("Removed %d entries\n", removed2);
125 ASSERT_FORCE(MyTree_IsEmpty(&tree))
126 ASSERT_FORCE(removed1 + removed2 == inserted)
127 ASSERT_FORCE(MyTree_Count(&tree, 0) == 0)
128 verify(&tree);
129  
130 BFree(nodes);
131 BFree(values_ins);
132 BFree(values);
133  
134 return 0;
135 }