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