Rev 1142 | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 1142 | Rev 1144 | ||
---|---|---|---|
1 | /* |
1 | /* |
2 | * Copyright (C) 2006 Jakub Jermar |
2 | * Copyright (C) 2006 Jakub Jermar |
3 | * All rights reserved. |
3 | * All rights reserved. |
4 | * |
4 | * |
5 | * Redistribution and use in source and binary forms, with or without |
5 | * Redistribution and use in source and binary forms, with or without |
6 | * modification, are permitted provided that the following conditions |
6 | * modification, are permitted provided that the following conditions |
7 | * are met: |
7 | * are met: |
8 | * |
8 | * |
9 | * - Redistributions of source code must retain the above copyright |
9 | * - Redistributions of source code must retain the above copyright |
10 | * notice, this list of conditions and the following disclaimer. |
10 | * notice, this list of conditions and the following disclaimer. |
11 | * - Redistributions in binary form must reproduce the above copyright |
11 | * - Redistributions in binary form must reproduce the above copyright |
12 | * notice, this list of conditions and the following disclaimer in the |
12 | * notice, this list of conditions and the following disclaimer in the |
13 | * documentation and/or other materials provided with the distribution. |
13 | * documentation and/or other materials provided with the distribution. |
14 | * - The name of the author may not be used to endorse or promote products |
14 | * - The name of the author may not be used to endorse or promote products |
15 | * derived from this software without specific prior written permission. |
15 | * derived from this software without specific prior written permission. |
16 | * |
16 | * |
17 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
17 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
18 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
18 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
19 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
19 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
20 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
20 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
21 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
21 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
22 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
22 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
23 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
23 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
24 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
24 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
25 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
25 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
26 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
26 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
27 | */ |
27 | */ |
28 | 28 | ||
29 | #include <test.h> |
29 | #include <test.h> |
30 | #include <print.h> |
30 | #include <print.h> |
31 | #include <adt/btree.h> |
31 | #include <adt/btree.h> |
32 | #include <debug.h> |
32 | #include <debug.h> |
33 | 33 | ||
34 | void *data = (void *) 0xdeadbeef; |
34 | void *data = (void *) 0xdeadbeef; |
35 | 35 | ||
36 | void test(void) |
36 | void test(void) |
37 | { |
37 | { |
38 | btree_t t; |
38 | btree_t t; |
39 | int i; |
39 | int i; |
40 | 40 | ||
41 | btree_create(&t); |
41 | btree_create(&t); |
42 | 42 | ||
- | 43 | printf("Inserting keys.\n"); |
|
- | 44 | btree_insert(&t, 19, data, NULL); |
|
- | 45 | btree_insert(&t, 20, data, NULL); |
|
- | 46 | btree_insert(&t, 21, data, NULL); |
|
- | 47 | btree_insert(&t, 0, data, NULL); |
|
- | 48 | btree_insert(&t, 25, data, NULL); |
|
- | 49 | btree_insert(&t, 22, data, NULL); |
|
- | 50 | btree_insert(&t, 26, data, NULL); |
|
43 | btree_insert(&t, 23, data, NULL); |
51 | btree_insert(&t, 23, data, NULL); |
44 | btree_insert(&t, 24, data, NULL); |
52 | btree_insert(&t, 24, data, NULL); |
45 | btree_insert(&t, 5, data, NULL); |
53 | btree_insert(&t, 5, data, NULL); |
46 | btree_insert(&t, 1, data, NULL); |
54 | btree_insert(&t, 1, data, NULL); |
47 | btree_insert(&t, 4, data, NULL); |
55 | btree_insert(&t, 4, data, NULL); |
48 | btree_insert(&t, 28, data, NULL); |
56 | btree_insert(&t, 28, data, NULL); |
49 | btree_insert(&t, 29, data, NULL); |
57 | btree_insert(&t, 29, data, NULL); |
50 | btree_insert(&t, 7, data, NULL); |
58 | btree_insert(&t, 7, data, NULL); |
51 | btree_insert(&t, 8, data, NULL); |
59 | btree_insert(&t, 8, data, NULL); |
52 | btree_insert(&t, 9, data, NULL); |
60 | btree_insert(&t, 9, data, NULL); |
53 | btree_insert(&t, 17, data, NULL); |
61 | btree_insert(&t, 17, data, NULL); |
54 | btree_insert(&t, 18, data, NULL); |
62 | btree_insert(&t, 18, data, NULL); |
55 | btree_insert(&t, 2, data, NULL); |
63 | btree_insert(&t, 2, data, NULL); |
56 | btree_insert(&t, 3, data, NULL); |
64 | btree_insert(&t, 3, data, NULL); |
57 | btree_insert(&t, 6, data, NULL); |
65 | btree_insert(&t, 6, data, NULL); |
58 | btree_insert(&t, 19, data, NULL); |
- | |
59 | btree_insert(&t, 20, data, NULL); |
- | |
60 | btree_insert(&t, 21, data, NULL); |
- | |
61 | btree_insert(&t, 0, data, NULL); |
- | |
62 | btree_insert(&t, 25, data, NULL); |
- | |
63 | btree_insert(&t, 22, data, NULL); |
- | |
64 | btree_insert(&t, 26, data, NULL); |
- | |
65 | btree_insert(&t, 10, data, NULL); |
66 | btree_insert(&t, 10, data, NULL); |
66 | btree_insert(&t, 11, data, NULL); |
67 | btree_insert(&t, 11, data, NULL); |
67 | btree_insert(&t, 12, data, NULL); |
68 | btree_insert(&t, 12, data, NULL); |
68 | btree_insert(&t, 13, data, NULL); |
69 | btree_insert(&t, 13, data, NULL); |
69 | btree_insert(&t, 14, data, NULL); |
70 | btree_insert(&t, 14, data, NULL); |
70 | btree_insert(&t, 15, data, NULL); |
71 | btree_insert(&t, 15, data, NULL); |
71 | btree_insert(&t, 16, data, NULL); |
72 | btree_insert(&t, 16, data, NULL); |
72 | btree_insert(&t, 27, data, NULL); |
73 | btree_insert(&t, 27, data, NULL); |
73 | 74 | ||
74 | for (i = 30; i < 50; i++) |
75 | for (i = 30; i < 50; i++) |
75 | btree_insert(&t, i, data, NULL); |
76 | btree_insert(&t, i, data, NULL); |
76 | for (i = 100; i >= 50; i--) |
77 | for (i = 100; i >= 50; i--) |
77 | btree_insert(&t, i, data, NULL); |
78 | btree_insert(&t, i, data, NULL); |
78 | 79 | ||
79 | btree_print(&t); |
80 | btree_print(&t); |
80 | 81 | ||
- | 82 | printf("Removing keys.\n"); |
|
81 | btree_remove(&t, 50, NULL); |
83 | btree_remove(&t, 50, NULL); |
- | 84 | btree_remove(&t, 49, NULL); |
|
- | 85 | btree_remove(&t, 51, NULL); |
|
- | 86 | btree_remove(&t, 46, NULL); |
|
- | 87 | btree_remove(&t, 45, NULL); |
|
- | 88 | btree_remove(&t, 48, NULL); |
|
- | 89 | btree_remove(&t, 53, NULL); |
|
- | 90 | btree_remove(&t, 47, NULL); |
|
- | 91 | btree_remove(&t, 52, NULL); |
|
- | 92 | btree_remove(&t, 54, NULL); |
|
- | 93 | btree_remove(&t, 65, NULL); |
|
- | 94 | btree_remove(&t, 60, NULL); |
|
- | 95 | btree_remove(&t, 99, NULL); |
|
- | 96 | btree_remove(&t, 97, NULL); |
|
- | 97 | btree_remove(&t, 57, NULL); |
|
- | 98 | btree_remove(&t, 58, NULL); |
|
- | 99 | btree_remove(&t, 61, NULL); |
|
- | 100 | btree_remove(&t, 64, NULL); |
|
- | 101 | btree_remove(&t, 56, NULL); |
|
- | 102 | btree_remove(&t, 41, NULL); |
|
- | 103 | ||
- | 104 | for (i = 5; i < 20; i++) |
|
- | 105 | btree_remove(&t, i, NULL); |
|
82 | 106 | ||
- | 107 | btree_remove(&t, 2, NULL); |
|
- | 108 | btree_remove(&t, 43, NULL); |
|
- | 109 | btree_remove(&t, 22, NULL); |
|
- | 110 | btree_remove(&t, 100, NULL); |
|
- | 111 | btree_remove(&t, 98, NULL); |
|
- | 112 | btree_remove(&t, 96, NULL); |
|
- | 113 | btree_remove(&t, 66, NULL); |
|
- | 114 | btree_remove(&t, 1, NULL); |
|
- | 115 | ||
- | 116 | for (i = 70; i < 90; i++) |
|
- | 117 | btree_remove(&t, i, NULL); |
|
- | 118 | ||
- | 119 | btree_remove(&t, 20, NULL); |
|
- | 120 | btree_remove(&t, 0, NULL); |
|
- | 121 | btree_remove(&t, 40, NULL); |
|
- | 122 | btree_remove(&t, 3, NULL); |
|
- | 123 | btree_remove(&t, 4, NULL); |
|
- | 124 | btree_remove(&t, 21, NULL); |
|
- | 125 | btree_remove(&t, 44, NULL); |
|
- | 126 | btree_remove(&t, 55, NULL); |
|
- | 127 | btree_remove(&t, 62, NULL); |
|
- | 128 | btree_remove(&t, 26, NULL); |
|
- | 129 | btree_remove(&t, 27, NULL); |
|
- | 130 | btree_remove(&t, 28, NULL); |
|
- | 131 | btree_remove(&t, 29, NULL); |
|
- | 132 | btree_remove(&t, 30, NULL); |
|
- | 133 | btree_remove(&t, 31, NULL); |
|
- | 134 | btree_remove(&t, 32, NULL); |
|
- | 135 | btree_remove(&t, 33, NULL); |
|
- | 136 | btree_remove(&t, 93, NULL); |
|
- | 137 | btree_remove(&t, 95, NULL); |
|
- | 138 | btree_remove(&t, 94, NULL); |
|
- | 139 | btree_remove(&t, 69, NULL); |
|
- | 140 | btree_remove(&t, 68, NULL); |
|
- | 141 | btree_remove(&t, 92, NULL); |
|
- | 142 | btree_remove(&t, 91, NULL); |
|
- | 143 | btree_remove(&t, 67, NULL); |
|
- | 144 | btree_remove(&t, 63, NULL); |
|
- | 145 | btree_remove(&t, 90, NULL); |
|
- | 146 | btree_remove(&t, 59, NULL); |
|
- | 147 | btree_remove(&t, 23, NULL); |
|
- | 148 | btree_remove(&t, 24, NULL); |
|
- | 149 | btree_remove(&t, 25, NULL); |
|
- | 150 | btree_remove(&t, 37, NULL); |
|
- | 151 | btree_remove(&t, 38, NULL); |
|
- | 152 | btree_remove(&t, 42, NULL); |
|
- | 153 | btree_remove(&t, 39, NULL); |
|
- | 154 | btree_remove(&t, 34, NULL); |
|
- | 155 | btree_remove(&t, 35, NULL); |
|
- | 156 | btree_remove(&t, 36, NULL); |
|
- | 157 | ||
- | 158 | btree_print(&t); |
|
83 | } |
159 | } |
84 | 160 |