Line data Source code
1 : /***************************************************************************//**
2 :
3 : @file hashtabletest.c
4 :
5 : @author Stephen Brennan
6 :
7 : @date Created Tuesday, 5 December 2013
8 :
9 : @brief A test of the hash table.
10 :
11 : @copyright Copyright (c) 2013-2015, Stephen Brennan. Released under the
12 : Revised BSD License. See the LICENSE.txt file for details.
13 :
14 : *******************************************************************************/
15 :
16 : #include <stdio.h>
17 :
18 : #include "tests.h"
19 : #include "libstephen/ut.h"
20 : #include "libstephen/ht.h"
21 :
22 : #define TEST_PAIRS 5
23 :
24 : char *test_keys[] = {
25 : "first key",
26 : "second key",
27 : "third key",
28 : "fourth key",
29 : "fifth key"
30 : };
31 :
32 : char *test_values[] = {
33 : "first value",
34 : "second value",
35 : "third value",
36 : "fourth value",
37 : "fifth value"
38 : };
39 :
40 : int ht_test_deletions = 0;
41 :
42 211 : void ht_test_deleter(DATA dValue)
43 : {
44 211 : ht_test_deletions++;
45 211 : }
46 :
47 40 : unsigned int ht_test_constant_hash(DATA dKey)
48 : {
49 : // return random_die_roll();
50 40 : return 4;
51 : }
52 :
53 542 : unsigned int ht_test_linear_hash(DATA dKey)
54 : {
55 542 : return (unsigned int) dKey.data_llint;
56 : }
57 :
58 : /**
59 : This doesn't really just test insert. It also tests create and get. But I
60 : can't really isolate *just* insert.
61 : */
62 1 : int ht_test_insert()
63 : {
64 1 : smb_status status = SMB_SUCCESS;
65 : DATA key, value;
66 : int i;
67 1 : smb_ht *table = ht_create(&ht_string_hash, &data_compare_string);
68 :
69 6 : for (i = 0; i < TEST_PAIRS; i++) {
70 5 : key.data_ptr = test_keys[i];
71 5 : value.data_ptr = test_values[i];
72 5 : ht_insert(table, key, value);
73 : }
74 :
75 6 : for (i = 0; i < TEST_PAIRS; i++) {
76 5 : key.data_ptr = test_keys[i];
77 5 : TEST_ASSERT(test_values[i] == ht_get(table, key, &status).data_ptr);
78 5 : TEST_ASSERT(status == SMB_SUCCESS);
79 : }
80 :
81 1 : ht_delete(table);
82 1 : return 0;
83 : }
84 :
85 1 : int ht_test_remove()
86 : {
87 1 : smb_status status= SMB_SUCCESS;
88 : DATA key, value;
89 : int i;
90 1 : smb_ht *table = ht_create(&ht_string_hash, &data_compare_string);
91 1 : ht_test_deletions = 0;
92 :
93 6 : for (i = 0; i < TEST_PAIRS; i++) {
94 5 : key.data_ptr = test_keys[i];
95 5 : value.data_ptr = test_values[i];
96 5 : ht_insert(table, key, value);
97 : }
98 :
99 1 : TEST_ASSERT(table->length == TEST_PAIRS);
100 :
101 6 : for (i = 0; i < TEST_PAIRS; i++) {
102 5 : key.data_ptr = test_keys[i];
103 5 : value = ht_get(table, key, &status);
104 5 : TEST_ASSERT(status == SMB_SUCCESS);
105 5 : TEST_ASSERT(test_values[i] == value.data_ptr);
106 5 : ht_remove_act(table, key, ht_test_deleter, &status);
107 5 : TEST_ASSERT(status == SMB_SUCCESS);
108 5 : TEST_ASSERT(table->length == TEST_PAIRS - i - 1);
109 : }
110 :
111 1 : ht_delete_act(table, ht_test_deleter);
112 1 : TEST_ASSERT(ht_test_deletions == TEST_PAIRS);
113 1 : return 0;
114 : }
115 :
116 : /*
117 : This test expecs a NOT_FOUND_ERROR
118 : */
119 1 : int ht_test_remove_invalid()
120 : {
121 1 : smb_status status = SMB_SUCCESS;
122 : DATA key;
123 1 : smb_ht *table = ht_create(&ht_string_hash, &data_compare_string);
124 :
125 1 : key.data_ptr = "invalid key";
126 1 : ht_get(table, key, &status);
127 1 : TEST_ASSERT(status == SMB_NOT_FOUND_ERROR);
128 :
129 1 : ht_delete(table);
130 1 : return 0;
131 : }
132 :
133 : /**
134 : This test intentionally uses a very bad hash function that returns a
135 : constant. This way, I can test whether the insertion and removal for large
136 : buckets is working.
137 : */
138 1 : int ht_test_buckets()
139 : {
140 1 : smb_status status = SMB_SUCCESS;
141 : DATA key, value;
142 : int i;
143 1 : smb_ht *table = ht_create(&ht_test_constant_hash, &data_compare_int);
144 1 : ht_test_deletions = 0;
145 :
146 21 : for (i = 0; i < 20; i++) {
147 20 : key.data_llint = i;
148 20 : value.data_llint = -i;
149 20 : ht_insert(table, key, value);
150 20 : TEST_ASSERT(status == SMB_SUCCESS);
151 20 : TEST_ASSERT(table->length == i+1);
152 : }
153 :
154 : // Remove one from the middle of the bucket list.
155 1 : key.data_llint = 10;
156 1 : ht_remove_act(table, key, ht_test_deleter, &status);
157 1 : TEST_ASSERT(status == SMB_SUCCESS);
158 1 : TEST_ASSERT(table->length == 19);
159 :
160 : // Remove one from the beginning of the bucket list.
161 1 : key.data_llint = 0;
162 1 : ht_remove_act(table, key, ht_test_deleter, &status);
163 1 : TEST_ASSERT(status == SMB_SUCCESS);
164 1 : TEST_ASSERT(table->length == 18);
165 :
166 : //ht_print(table, 0);
167 :
168 : // Remove from the end of the list.
169 1 : key.data_llint = 19;
170 1 : ht_remove_act(table, key, ht_test_deleter, &status);
171 1 : TEST_ASSERT(status == SMB_SUCCESS);
172 1 : TEST_ASSERT(table->length == 17);
173 :
174 : //ht_print(table, 0);
175 :
176 : // Verify that the other items are still there.
177 10 : for (i = 1; i < 10; i++) {
178 9 : key.data_llint = i;
179 9 : value = ht_get(table, key, &status);
180 9 : TEST_ASSERT(status == SMB_SUCCESS);
181 9 : TEST_ASSERT(value.data_llint == -i);
182 : }
183 :
184 9 : for (i = 11; i < 19; i++) {
185 8 : key.data_llint = i;
186 8 : value = ht_get(table, key, &status);
187 8 : TEST_ASSERT(status == SMB_SUCCESS);
188 8 : TEST_ASSERT(value.data_llint == -i);
189 : }
190 :
191 1 : ht_delete_act(table, ht_test_deleter);
192 1 : TEST_ASSERT(ht_test_deletions == 20);
193 1 : return 0;
194 : }
195 :
196 : /**
197 : This test adds to the hash table until it is forced to reallocate. Then it
198 : checks that every value is still accessible.
199 : */
200 1 : int ht_test_resize()
201 : {
202 1 : smb_status status = SMB_SUCCESS;
203 : DATA key, value;
204 : int i;
205 : // Truncating addition will trim this to the number just before expanding.
206 1 : int last_stable = 1 + (int) (HASH_TABLE_INITIAL_SIZE * HASH_TABLE_MAX_LOAD_FACTOR);
207 1 : smb_ht *table = ht_create(ht_test_linear_hash, &data_compare_int);
208 1 : ht_test_deletions = 0;
209 :
210 181 : for (i = 0; i < last_stable; i++) {
211 180 : key.data_llint = i;
212 180 : value.data_llint = -i;
213 180 : ht_insert(table, key, value);
214 180 : TEST_ASSERT(table->allocated == HASH_TABLE_INITIAL_SIZE);
215 180 : TEST_ASSERT(table->length == i + 1);
216 : }
217 :
218 1 : key.data_llint = last_stable;
219 1 : value.data_llint = -last_stable;
220 1 : ht_insert(table, key, value);
221 1 : TEST_ASSERT(table->allocated > HASH_TABLE_INITIAL_SIZE);
222 1 : TEST_ASSERT(table->length == last_stable + 1);
223 :
224 182 : for (i = 0; i <= last_stable; i++) {
225 181 : key.data_llint = i;
226 181 : value = ht_get(table, key, &status);
227 181 : TEST_ASSERT(status == SMB_SUCCESS);
228 181 : TEST_ASSERT(value.data_llint == -i);
229 : }
230 :
231 1 : ht_delete_act(table, ht_test_deleter);
232 1 : TEST_ASSERT(ht_test_deletions == last_stable + 1);
233 1 : return 0;
234 : }
235 :
236 1 : int ht_test_duplicate()
237 : {
238 1 : smb_status status = SMB_SUCCESS;
239 : DATA key, value;
240 : int i;
241 1 : char *newKey = "not the first value";
242 1 : smb_ht *table = ht_create(ht_string_hash, &data_compare_string);
243 1 : ht_test_deletions = 0;
244 :
245 6 : for (i = 0; i < TEST_PAIRS; i++) {
246 5 : key.data_ptr = test_keys[i];
247 5 : value.data_ptr = test_values[i];
248 5 : ht_insert(table, key, value);
249 : }
250 :
251 4 : for (i = 0; i < TEST_PAIRS; i += 2) {
252 3 : TEST_ASSERT(table->length == TEST_PAIRS);
253 :
254 3 : key.data_ptr = test_keys[i];
255 3 : value.data_ptr = newKey;
256 3 : ht_insert(table, key, value);
257 3 : value = ht_get(table, key, &status);
258 3 : TEST_ASSERT(status == SMB_SUCCESS);
259 3 : TEST_ASSERT(value.data_ptr == newKey);
260 : }
261 :
262 6 : for (i = 0; i < TEST_PAIRS; i++) {
263 5 : key.data_ptr = test_keys[i];
264 5 : value = ht_get(table, key, &status);
265 5 : TEST_ASSERT(status == SMB_SUCCESS);
266 5 : if (i % 2 == 1) {
267 2 : TEST_ASSERT(value.data_ptr == test_values[i]);
268 : } else {
269 3 : TEST_ASSERT(value.data_ptr == newKey);
270 : }
271 : }
272 :
273 1 : ht_delete_act(table, ht_test_deleter);
274 1 : TEST_ASSERT(ht_test_deletions == TEST_PAIRS);
275 1 : return 0;
276 : }
277 :
278 1 : void hash_table_test()
279 : {
280 1 : smb_ut_group *group = su_create_test_group("hash table");
281 :
282 1 : smb_ut_test *insert = su_create_test("insert", ht_test_insert);
283 1 : su_add_test(group, insert);
284 :
285 1 : smb_ut_test *remove = su_create_test("remove", ht_test_remove);
286 1 : su_add_test(group, remove);
287 :
288 1 : smb_ut_test *remove_invalid = su_create_test("remove_invalid", ht_test_remove_invalid);
289 1 : su_add_test(group, remove_invalid);
290 :
291 1 : smb_ut_test *buckets = su_create_test("buckets", ht_test_buckets);
292 1 : su_add_test(group, buckets);
293 :
294 1 : smb_ut_test *resize = su_create_test("resize", ht_test_resize);
295 1 : su_add_test(group, resize);
296 :
297 1 : smb_ut_test *duplicate = su_create_test("duplicate", ht_test_duplicate);
298 1 : su_add_test(group, duplicate);
299 :
300 1 : su_run_group(group);
301 1 : su_delete_group(group);
302 1 : }
|
