]>
Commit | Line | Data |
---|---|---|
2a1732b4 VM |
1 | /* |
2 | * This file is free software; you can redistribute it and/or modify | |
3 | * it under the terms of the GNU General Public License, version 2, | |
4 | * as published by the Free Software Foundation. | |
5 | * | |
6 | * In addition to the permissions in the GNU General Public License, | |
7 | * the authors give you unlimited permission to link the compiled | |
8 | * version of this file into combinations with other programs, | |
9 | * and to distribute those combinations without any restriction | |
10 | * coming from the use of this file. (The General Public License | |
11 | * restrictions do apply in other respects; for example, they cover | |
12 | * modification of the file, and distribution when not linked into | |
13 | * a combined executable.) | |
14 | * | |
15 | * This file is distributed in the hope that it will be useful, but | |
16 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
17 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
18 | * General Public License for more details. | |
19 | * | |
20 | * You should have received a copy of the GNU General Public License | |
21 | * along with this program; see the file COPYING. If not, write to | |
22 | * the Free Software Foundation, 51 Franklin Street, Fifth Floor, | |
23 | * Boston, MA 02110-1301, USA. | |
24 | */ | |
b231ef3a VM |
25 | #include "test_lib.h" |
26 | #include "test_helpers.h" | |
2a1732b4 | 27 | |
3315782c | 28 | #include "hashtable.h" |
2a1732b4 | 29 | #include "hash.h" |
b231ef3a | 30 | |
2a1732b4 | 31 | typedef struct _aux_object { |
3315782c VM |
32 | int __bulk; |
33 | git_oid id; | |
2a1732b4 | 34 | int visited; |
3315782c VM |
35 | } table_item; |
36 | ||
fc658755 | 37 | uint32_t hash_func(const void *key, int hash_id) |
3315782c VM |
38 | { |
39 | uint32_t r; | |
84ef7f36 | 40 | const git_oid *id = key; |
3315782c | 41 | |
fc658755 | 42 | memcpy(&r, id->id + (hash_id * sizeof(uint32_t)), sizeof(r)); |
3315782c VM |
43 | return r; |
44 | } | |
45 | ||
fc658755 | 46 | int hash_cmpkey(const void *a, const void *b) |
3315782c | 47 | { |
fc658755 | 48 | return git_oid_cmp(a, b); |
3315782c | 49 | } |
b231ef3a | 50 | |
3dccfed1 | 51 | BEGIN_TEST(table0, "create a new hashtable") |
b231ef3a | 52 | |
3315782c | 53 | git_hashtable *table = NULL; |
b231ef3a | 54 | |
fc658755 | 55 | table = git_hashtable_alloc(55, hash_func, hash_cmpkey); |
b231ef3a VM |
56 | must_be_true(table != NULL); |
57 | must_be_true(table->size_mask + 1 == 64); | |
58 | ||
3315782c | 59 | git_hashtable_free(table); |
b231ef3a VM |
60 | |
61 | END_TEST | |
62 | ||
3dccfed1 | 63 | BEGIN_TEST(table1, "fill the hashtable with random entries") |
b231ef3a VM |
64 | |
65 | const int objects_n = 32; | |
66 | int i; | |
b231ef3a | 67 | |
3315782c VM |
68 | table_item *objects; |
69 | git_hashtable *table = NULL; | |
70 | ||
fc658755 | 71 | table = git_hashtable_alloc(objects_n * 2, hash_func, hash_cmpkey); |
b231ef3a VM |
72 | must_be_true(table != NULL); |
73 | ||
3315782c VM |
74 | objects = git__malloc(objects_n * sizeof(table_item)); |
75 | memset(objects, 0x0, objects_n * sizeof(table_item)); | |
b231ef3a VM |
76 | |
77 | /* populate the hash table */ | |
78 | for (i = 0; i < objects_n; ++i) { | |
79 | git_hash_buf(&(objects[i].id), &i, sizeof(int)); | |
3315782c | 80 | must_pass(git_hashtable_insert(table, &(objects[i].id), &(objects[i]))); |
b231ef3a VM |
81 | } |
82 | ||
83 | /* make sure all the inserted objects can be found */ | |
84 | for (i = 0; i < objects_n; ++i) { | |
85 | git_oid id; | |
3315782c | 86 | table_item *ob; |
b231ef3a VM |
87 | |
88 | git_hash_buf(&id, &i, sizeof(int)); | |
3315782c | 89 | ob = (table_item *)git_hashtable_lookup(table, &id); |
b231ef3a VM |
90 | |
91 | must_be_true(ob != NULL); | |
92 | must_be_true(ob == &(objects[i])); | |
93 | } | |
94 | ||
95 | /* make sure we cannot find inexisting objects */ | |
96 | for (i = 0; i < 50; ++i) { | |
97 | int hash_id; | |
98 | git_oid id; | |
99 | ||
100 | hash_id = (rand() % 50000) + objects_n; | |
101 | git_hash_buf(&id, &hash_id, sizeof(int)); | |
3315782c | 102 | must_be_true(git_hashtable_lookup(table, &id) == NULL); |
b231ef3a VM |
103 | } |
104 | ||
3315782c | 105 | git_hashtable_free(table); |
b231ef3a VM |
106 | free(objects); |
107 | ||
108 | END_TEST | |
109 | ||
110 | ||
3dccfed1 | 111 | BEGIN_TEST(table2, "make sure the table resizes automatically") |
b231ef3a VM |
112 | |
113 | const int objects_n = 64; | |
114 | int i; | |
115 | unsigned int old_size; | |
3315782c VM |
116 | table_item *objects; |
117 | git_hashtable *table = NULL; | |
b231ef3a | 118 | |
fc658755 | 119 | table = git_hashtable_alloc(objects_n, hash_func, hash_cmpkey); |
b231ef3a VM |
120 | must_be_true(table != NULL); |
121 | ||
3315782c VM |
122 | objects = git__malloc(objects_n * sizeof(table_item)); |
123 | memset(objects, 0x0, objects_n * sizeof(table_item)); | |
b231ef3a VM |
124 | |
125 | old_size = table->size_mask + 1; | |
126 | ||
127 | /* populate the hash table -- should be automatically resized */ | |
128 | for (i = 0; i < objects_n; ++i) { | |
129 | git_hash_buf(&(objects[i].id), &i, sizeof(int)); | |
3315782c | 130 | must_pass(git_hashtable_insert(table, &(objects[i].id), &(objects[i]))); |
b231ef3a VM |
131 | } |
132 | ||
b231ef3a VM |
133 | must_be_true(table->size_mask > old_size); |
134 | ||
135 | /* make sure all the inserted objects can be found */ | |
136 | for (i = 0; i < objects_n; ++i) { | |
137 | git_oid id; | |
3315782c | 138 | table_item *ob; |
b231ef3a VM |
139 | |
140 | git_hash_buf(&id, &i, sizeof(int)); | |
3315782c | 141 | ob = (table_item *)git_hashtable_lookup(table, &id); |
b231ef3a VM |
142 | |
143 | must_be_true(ob != NULL); | |
144 | must_be_true(ob == &(objects[i])); | |
145 | } | |
146 | ||
3315782c | 147 | git_hashtable_free(table); |
b231ef3a VM |
148 | free(objects); |
149 | ||
150 | END_TEST | |
2a1732b4 | 151 | |
3dccfed1 | 152 | BEGIN_TEST(tableit0, "iterate through all the contents of the table") |
2a1732b4 VM |
153 | |
154 | const int objects_n = 32; | |
155 | int i; | |
156 | table_item *objects, *ob; | |
402a47a7 | 157 | const void *GIT_UNUSED(_unused); |
2a1732b4 VM |
158 | |
159 | git_hashtable *table = NULL; | |
2a1732b4 | 160 | |
fc658755 | 161 | table = git_hashtable_alloc(objects_n * 2, hash_func, hash_cmpkey); |
2a1732b4 VM |
162 | must_be_true(table != NULL); |
163 | ||
164 | objects = git__malloc(objects_n * sizeof(table_item)); | |
165 | memset(objects, 0x0, objects_n * sizeof(table_item)); | |
166 | ||
167 | /* populate the hash table */ | |
168 | for (i = 0; i < objects_n; ++i) { | |
169 | git_hash_buf(&(objects[i].id), &i, sizeof(int)); | |
170 | must_pass(git_hashtable_insert(table, &(objects[i].id), &(objects[i]))); | |
171 | } | |
172 | ||
fc658755 | 173 | GIT_HASHTABLE_FOREACH(table, _unused, ob, |
2a1732b4 | 174 | ob->visited = 1; |
fc658755 | 175 | ); |
2a1732b4 VM |
176 | |
177 | /* make sure all nodes have been visited */ | |
178 | for (i = 0; i < objects_n; ++i) | |
179 | must_be_true(objects[i].visited); | |
180 | ||
181 | git_hashtable_free(table); | |
182 | free(objects); | |
2a1732b4 VM |
183 | END_TEST |
184 | ||
185 | ||
3dccfed1 VM |
186 | BEGIN_SUITE(hashtable) |
187 | ADD_TEST(table0); | |
188 | ADD_TEST(table1); | |
189 | ADD_TEST(table2); | |
190 | ADD_TEST(tableit0); | |
191 | END_SUITE | |
2a1732b4 | 192 |