1 /*
2 * Copyright (C) 2009-2021 Free Software Foundation, Inc.
3 * Written by Jim Meyering
4 *
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 3 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program. If not, see <https://www.gnu.org/licenses/>. */
17
18 #include <config.h>
19
20 #include "hash.h"
21 #include "hash-pjw.h"
22 #include "inttostr.h"
23
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include <stdbool.h>
27 #include <string.h>
28 #include <unistd.h>
29
30 #include "macros.h"
31
32 #define STREQ(a, b) (strcmp (a, b) == 0)
33 #define ARRAY_CARDINALITY(Array) (sizeof (Array) / sizeof *(Array))
34
35 static bool
36 hash_compare_strings (void const *x, void const *y)
37 {
38 ASSERT (x != y);
39 return STREQ (x, y) ? true : false;
40 }
41
42 static void
43 hash_freer (void *x)
44 {
45 free (x);
46 }
47
48 static void
49 insert_new (Hash_table *ht, const void *ent)
50 {
51 void *e = hash_insert (ht, ent);
52 ASSERT (e == ent);
53 }
54
55 static bool
56 walk (void *ent, void *data)
57 {
58 char *str = ent;
59 unsigned int *map = data;
60 switch (*str)
61 {
62 case 'a': *map |= 1; return true;
63 case 'b': *map |= 2; return true;
64 case 'c': *map |= 4; return true;
65 }
66 *map |= 8;
67 return false;
68 }
69
70 static int
71 get_seed (char const *str, unsigned int *seed)
72 {
73 size_t len = strlen (str);
74 if (len == 0 || strspn (str, "0123456789") != len || 10 < len)
75 return 1;
76
77 *seed = atoi (str);
78 return 0;
79 }
80
81 int
82 main (int argc, char **argv)
83 {
84 unsigned int i;
85 unsigned int k;
86 unsigned int table_size[] = {1, 2, 3, 4, 5, 23, 53};
87 Hash_table *ht;
88 Hash_tuning tuning;
89
90 hash_reset_tuning (&tuning);
91 tuning.shrink_threshold = 0.3;
92 tuning.shrink_factor = 0.707;
93 tuning.growth_threshold = 1.5;
94 tuning.growth_factor = 2.0;
95 tuning.is_n_buckets = true;
96
97 if (1 < argc)
98 {
99 unsigned int seed;
100 if (get_seed (argv[1], &seed) != 0)
101 {
102 fprintf (stderr, "invalid seed: %s\n", argv[1]);
103 exit (EXIT_FAILURE);
104 }
105
106 srand (seed);
107 }
108
109 for (i = 0; i < ARRAY_CARDINALITY (table_size); i++)
110 {
111 size_t sz = table_size[i];
112 ht = hash_initialize (sz, NULL, hash_pjw, hash_compare_strings, NULL);
113 ASSERT (ht);
114 insert_new (ht, "a");
115 {
116 char *str1 = strdup ("a");
117 char *str2;
118 ASSERT (str1);
119 str2 = hash_insert (ht, str1);
120 ASSERT (str1 != str2);
121 ASSERT (STREQ (str1, str2));
122 free (str1);
123 }
124 insert_new (ht, "b");
125 insert_new (ht, "c");
126 i = 0;
127 ASSERT (hash_do_for_each (ht, walk, &i) == 3);
128 ASSERT (i == 7);
129 {
130 void *buf[5] = { NULL };
131 ASSERT (hash_get_entries (ht, NULL, 0) == 0);
132 ASSERT (hash_get_entries (ht, buf, 5) == 3);
133 ASSERT (STREQ (buf[0], "a") || STREQ (buf[0], "b") || STREQ (buf[0], "c"));
134 }
135 ASSERT (hash_remove (ht, "a"));
136 ASSERT (hash_remove (ht, "a") == NULL);
137 ASSERT (hash_remove (ht, "b"));
138 ASSERT (hash_remove (ht, "c"));
139
140 ASSERT (hash_rehash (ht, 47));
141 ASSERT (hash_rehash (ht, 467));
142
143 /* Free an empty table. */
144 hash_clear (ht);
145 hash_free (ht);
146
147 ht = hash_initialize (sz, NULL, hash_pjw, hash_compare_strings, NULL);
148 ASSERT (ht);
149
150 insert_new (ht, "z");
151 insert_new (ht, "y");
152 insert_new (ht, "x");
153 insert_new (ht, "w");
154 insert_new (ht, "v");
155 insert_new (ht, "u");
156
157 hash_clear (ht);
158 ASSERT (hash_get_n_entries (ht) == 0);
159 hash_free (ht);
160
161 /* Test pointer hashing. */
162 ht = hash_initialize (sz, NULL, NULL, NULL, NULL);
163 ASSERT (ht);
164 {
165 char *str = strdup ("a");
166 ASSERT (str);
167 insert_new (ht, "a");
168 insert_new (ht, str);
169 ASSERT (hash_lookup (ht, str) == str);
170 free (str);
171 }
172 hash_free (ht);
173 }
174
175 hash_reset_tuning (&tuning);
176 tuning.shrink_threshold = 0.3;
177 tuning.shrink_factor = 0.707;
178 tuning.growth_threshold = 1.5;
179 tuning.growth_factor = 2.0;
180 tuning.is_n_buckets = true;
181 /* Invalid tuning. */
182 ht = hash_initialize (4651, &tuning, hash_pjw, hash_compare_strings,
183 hash_freer);
184 ASSERT (!ht);
185
186 /* Alternate tuning. */
187 tuning.growth_threshold = 0.89;
188
189 /* Run with default tuning, then with custom tuning settings. */
190 for (k = 0; k < 2; k++)
191 {
192 Hash_tuning const *tune = (k == 0 ? NULL : &tuning);
193 /* Now, each entry is malloc'd. */
194 ht = hash_initialize (4651, tune, hash_pjw,
195 hash_compare_strings, hash_freer);
196 ASSERT (ht);
197 for (i = 0; i < 10000; i++)
198 {
199 unsigned int op = rand () % 10;
200 switch (op)
201 {
202 case 0:
203 case 1:
204 case 2:
205 case 3:
206 case 4:
207 case 5:
208 {
209 char buf[50];
210 char const *p = uinttostr (i, buf);
211 char *p_dup = strdup (p);
212 ASSERT (p_dup);
213 insert_new (ht, p_dup);
214 }
215 break;
216
217 case 6:
218 {
219 size_t n = hash_get_n_entries (ht);
220 ASSERT (hash_rehash (ht, n + rand () % 20));
221 }
222 break;
223
224 case 7:
225 {
226 size_t n = hash_get_n_entries (ht);
227 size_t delta = rand () % 20;
228 if (delta < n)
229 ASSERT (hash_rehash (ht, n - delta));
230 }
231 break;
232
233 case 8:
234 case 9:
235 {
236 /* Delete a random entry. */
237 size_t n = hash_get_n_entries (ht);
238 if (n)
239 {
240 size_t kk = rand () % n;
241 void const *p;
242 void *v;
243 for (p = hash_get_first (ht); kk;
244 --kk, p = hash_get_next (ht, p))
245 {
246 /* empty */
247 }
248 ASSERT (p);
249 v = hash_remove (ht, p);
250 ASSERT (v);
251 free (v);
252 }
253 break;
254 }
255 }
256 ASSERT (hash_table_ok (ht));
257 }
258
259 hash_free (ht);
260 }
261
262 return 0;
263 }