1 /*
2 Copyright 2011-2014 David Robillard <http://drobilla.net>
3
4 Permission to use, copy, modify, and/or distribute this software for any
5 purpose with or without fee is hereby granted, provided that the above
6 copyright notice and this permission notice appear in all copies.
7
8 THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15 */
16
17 #include <stdarg.h>
18 #include <stdio.h>
19 #include <string.h>
20
21 #include "test_malloc.h"
22 #include "zix/hash.h"
23
24 static bool expect_failure = false;
25
26 static const char* strings[] = {
27 "one", "two", "three", "four", "five", "six", "seven", "eight",
28 "2one", "2two", "2three", "2four", "2five", "2six", "2seven", "2eight",
29 "3one", "3two", "3three", "3four", "3five", "3six", "3seven", "3eight",
30 "4one", "4two", "4three", "4four", "4five", "4six", "4seven", "4eight",
31 "5one", "5two", "5three", "5four", "5five", "5six", "5seven", "5eight",
32 "6one", "6two", "6three", "6four", "6five", "6six", "6seven", "6eight",
33 "7one", "7two", "7three", "7four", "7five", "7six", "7seven", "7eight",
34 "8one", "8two", "8three", "8four", "8five", "8six", "8seven", "8eight",
35 "9one", "9two", "9three", "9four", "9five", "9six", "9seven", "9eight",
36 "Aone", "Atwo", "Athree", "Afour", "Afive", "Asix", "Aseven", "Aeight",
37 "Bone", "Btwo", "Bthree", "Bfour", "Bfive", "Bsix", "Bseven", "Beight",
38 "Cone", "Ctwo", "Cthree", "Cfour", "Cfive", "Csix", "Cseven", "Ceight",
39 "Done", "Dtwo", "Dthree", "Dfour", "Dfive", "Dsix", "Dseven", "Deight",
40 };
41
42 static int
test_fail(const char * fmt,...)43 test_fail(const char* fmt, ...)
44 {
45 if (expect_failure) {
46 return 0;
47 }
48 va_list args;
49 va_start(args, fmt);
50 fprintf(stderr, "error: ");
51 vfprintf(stderr, fmt, args);
52 va_end(args);
53 return 1;
54 }
55
56 static unsigned n_checked = 0;
57
58 static void
check(void * value,void * user_data)59 check(void* value, void* user_data)
60 {
61 if (strlen(*(const char*const*)value) >= 3) {
62 ++n_checked;
63 } else {
64 fprintf(stderr, "ERROR: %s\n", (const char*)value);
65 }
66 }
67
68 static uint32_t
string_ptr_hash(const void * value)69 string_ptr_hash(const void* value)
70 {
71 // Trusty old DJB hash
72 const char* str = *(const char*const*)value;
73 unsigned h = 5381;
74 for (const char* s = str; *s != '\0'; ++s) {
75 h = (h << 5) + h + *s; // h = h * 33 + c
76 }
77 return h;
78 }
79
80 static bool
string_ptr_equal(const void * a,const void * b)81 string_ptr_equal(const void* a, const void* b)
82 {
83 return !strcmp(*(const char*const*)a, *(const char*const*)b);
84 }
85
86 static int
stress(void)87 stress(void)
88 {
89 ZixHash* hash = zix_hash_new(
90 string_ptr_hash, string_ptr_equal, sizeof(const char*));
91 if (!hash) {
92 return test_fail("Failed to allocate hash\n");
93 }
94
95 const size_t n_strings = sizeof(strings) / sizeof(const char*);
96
97 // Insert each string
98 for (size_t i = 0; i < n_strings; ++i) {
99 const void* inserted = NULL;
100 ZixStatus st = zix_hash_insert(hash, &strings[i], &inserted);
101 if (st) {
102 return test_fail("Failed to insert `%s'\n", strings[i]);
103 } else if (*(const void*const*)inserted != strings[i]) {
104 return test_fail("Corrupt insertion %s != %s\n",
105 strings[i], *(const char*const*)inserted);
106 }
107 }
108
109 // Ensure hash size is correct
110 if (zix_hash_size(hash) != n_strings) {
111 return test_fail("Hash size %zu != %zu\n",
112 zix_hash_size(hash), n_strings);
113 }
114
115 //zix_hash_print_dot(hash, stdout);
116
117 // Attempt to insert each string again
118 for (size_t i = 0; i < n_strings; ++i) {
119 const void* inserted = NULL;
120 ZixStatus st = zix_hash_insert(hash, &strings[i], &inserted);
121 if (st != ZIX_STATUS_EXISTS) {
122 return test_fail("Double inserted `%s'\n", strings[i]);
123 }
124 }
125
126 // Search for each string
127 for (size_t i = 0; i < n_strings; ++i) {
128 const char*const* match = (const char*const*)zix_hash_find(
129 hash, &strings[i]);
130 if (!match) {
131 return test_fail("Failed to find `%s'\n", strings[i]);
132 }
133 if (*match != strings[i]) {
134 return test_fail("Bad match for `%s': `%s'\n", strings[i], match);
135 }
136 }
137
138 // Try some false matches
139 const char* not_indexed[] = {
140 "ftp://example.org/not-there-at-all",
141 "http://example.org/foobar",
142 "http://",
143 "http://otherdomain.com"
144 };
145 const size_t n_not_indexed = sizeof(not_indexed) / sizeof(char*);
146 for (size_t i = 0; i < n_not_indexed; ++i) {
147 const char*const* match = (const char*const*)zix_hash_find(
148 hash, ¬_indexed[i]);
149 if (match) {
150 return test_fail("Unexpectedly found `%s'\n", not_indexed[i]);
151 }
152 }
153
154 // Remove strings
155 for (size_t i = 0; i < n_strings; ++i) {
156 // Remove string
157 ZixStatus st = zix_hash_remove(hash, &strings[i]);
158 if (st) {
159 return test_fail("Failed to remove `%s'\n", strings[i]);
160 }
161
162 // Ensure second removal fails
163 st = zix_hash_remove(hash, &strings[i]);
164 if (st != ZIX_STATUS_NOT_FOUND) {
165 return test_fail("Unexpectedly removed `%s' twice\n", strings[i]);
166 }
167
168 // Check to ensure remaining strings are still present
169 for (size_t j = i + 1; j < n_strings; ++j) {
170 const char*const* match = (const char*const*)zix_hash_find(
171 hash, &strings[j]);
172 if (!match) {
173 return test_fail("Failed to find `%s' after remove\n", strings[j]);
174 }
175 if (*match != strings[j]) {
176 return test_fail("Bad match for `%s' after remove\n", strings[j]);
177 }
178 }
179 }
180
181 // Insert each string again (to check non-empty desruction)
182 for (size_t i = 0; i < n_strings; ++i) {
183 ZixStatus st = zix_hash_insert(hash, &strings[i], NULL);
184 if (st) {
185 return test_fail("Failed to insert `%s'\n", strings[i]);
186 }
187 }
188
189 // Check key == value (and test zix_hash_foreach)
190 zix_hash_foreach(hash, check, NULL);
191 if (n_checked != n_strings) {
192 return test_fail("Check failed\n");
193 }
194
195 zix_hash_free(hash);
196
197 return 0;
198 }
199
200 int
main(int argc,char ** argv)201 main(int argc, char** argv)
202 {
203 if (stress()) {
204 return 1;
205 }
206
207 const size_t total_n_allocs = test_malloc_get_n_allocs();
208 printf("Testing 0 ... %zu failed allocations\n", total_n_allocs);
209 expect_failure = true;
210 for (size_t i = 0; i < total_n_allocs; ++i) {
211 test_malloc_reset(i);
212 stress();
213 }
214
215 test_malloc_reset((size_t)-1);
216
217 return 0;
218 }
219