]> git.ipfire.org Git - thirdparty/git.git/blob - t/helper/test-hashmap.c
hashmap: introduce hashmap_free_entries
[thirdparty/git.git] / t / helper / test-hashmap.c
1 #include "test-tool.h"
2 #include "git-compat-util.h"
3 #include "hashmap.h"
4 #include "strbuf.h"
5
6 struct test_entry
7 {
8 struct hashmap_entry ent;
9 /* key and value as two \0-terminated strings */
10 char key[FLEX_ARRAY];
11 };
12
13 static const char *get_value(const struct test_entry *e)
14 {
15 return e->key + strlen(e->key) + 1;
16 }
17
18 static int test_entry_cmp(const void *cmp_data,
19 const struct hashmap_entry *eptr,
20 const struct hashmap_entry *entry_or_key,
21 const void *keydata)
22 {
23 const int ignore_case = cmp_data ? *((int *)cmp_data) : 0;
24 const struct test_entry *e1, *e2;
25 const char *key = keydata;
26
27 e1 = container_of(eptr, const struct test_entry, ent);
28 e2 = container_of(entry_or_key, const struct test_entry, ent);
29
30 if (ignore_case)
31 return strcasecmp(e1->key, key ? key : e2->key);
32 else
33 return strcmp(e1->key, key ? key : e2->key);
34 }
35
36 static struct test_entry *alloc_test_entry(unsigned int hash,
37 char *key, char *value)
38 {
39 size_t klen = strlen(key);
40 size_t vlen = strlen(value);
41 struct test_entry *entry = xmalloc(st_add4(sizeof(*entry), klen, vlen, 2));
42 hashmap_entry_init(&entry->ent, hash);
43 memcpy(entry->key, key, klen + 1);
44 memcpy(entry->key + klen + 1, value, vlen + 1);
45 return entry;
46 }
47
48 #define HASH_METHOD_FNV 0
49 #define HASH_METHOD_I 1
50 #define HASH_METHOD_IDIV10 2
51 #define HASH_METHOD_0 3
52 #define HASH_METHOD_X2 4
53 #define TEST_SPARSE 8
54 #define TEST_ADD 16
55 #define TEST_SIZE 100000
56
57 static unsigned int hash(unsigned int method, unsigned int i, const char *key)
58 {
59 unsigned int hash = 0;
60 switch (method & 3)
61 {
62 case HASH_METHOD_FNV:
63 hash = strhash(key);
64 break;
65 case HASH_METHOD_I:
66 hash = i;
67 break;
68 case HASH_METHOD_IDIV10:
69 hash = i / 10;
70 break;
71 case HASH_METHOD_0:
72 hash = 0;
73 break;
74 }
75
76 if (method & HASH_METHOD_X2)
77 hash = 2 * hash;
78 return hash;
79 }
80
81 /*
82 * Test performance of hashmap.[ch]
83 * Usage: time echo "perfhashmap method rounds" | test-tool hashmap
84 */
85 static void perf_hashmap(unsigned int method, unsigned int rounds)
86 {
87 struct hashmap map;
88 char buf[16];
89 struct test_entry **entries;
90 unsigned int *hashes;
91 unsigned int i, j;
92
93 ALLOC_ARRAY(entries, TEST_SIZE);
94 ALLOC_ARRAY(hashes, TEST_SIZE);
95 for (i = 0; i < TEST_SIZE; i++) {
96 xsnprintf(buf, sizeof(buf), "%i", i);
97 entries[i] = alloc_test_entry(0, buf, "");
98 hashes[i] = hash(method, i, entries[i]->key);
99 }
100
101 if (method & TEST_ADD) {
102 /* test adding to the map */
103 for (j = 0; j < rounds; j++) {
104 hashmap_init(&map, test_entry_cmp, NULL, 0);
105
106 /* add entries */
107 for (i = 0; i < TEST_SIZE; i++) {
108 hashmap_entry_init(&entries[i]->ent, hashes[i]);
109 hashmap_add(&map, &entries[i]->ent);
110 }
111
112 hashmap_free(&map);
113 }
114 } else {
115 /* test map lookups */
116 hashmap_init(&map, test_entry_cmp, NULL, 0);
117
118 /* fill the map (sparsely if specified) */
119 j = (method & TEST_SPARSE) ? TEST_SIZE / 10 : TEST_SIZE;
120 for (i = 0; i < j; i++) {
121 hashmap_entry_init(&entries[i]->ent, hashes[i]);
122 hashmap_add(&map, &entries[i]->ent);
123 }
124
125 for (j = 0; j < rounds; j++) {
126 for (i = 0; i < TEST_SIZE; i++) {
127 hashmap_get_from_hash(&map, hashes[i],
128 entries[i]->key);
129 }
130 }
131
132 hashmap_free(&map);
133 }
134 }
135
136 #define DELIM " \t\r\n"
137
138 /*
139 * Read stdin line by line and print result of commands to stdout:
140 *
141 * hash key -> strhash(key) memhash(key) strihash(key) memihash(key)
142 * put key value -> NULL / old value
143 * get key -> NULL / value
144 * remove key -> NULL / old value
145 * iterate -> key1 value1\nkey2 value2\n...
146 * size -> tablesize numentries
147 *
148 * perfhashmap method rounds -> test hashmap.[ch] performance
149 */
150 int cmd__hashmap(int argc, const char **argv)
151 {
152 struct strbuf line = STRBUF_INIT;
153 struct hashmap map;
154 int icase;
155
156 /* init hash map */
157 icase = argc > 1 && !strcmp("ignorecase", argv[1]);
158 hashmap_init(&map, test_entry_cmp, &icase, 0);
159
160 /* process commands from stdin */
161 while (strbuf_getline(&line, stdin) != EOF) {
162 char *cmd, *p1 = NULL, *p2 = NULL;
163 unsigned int hash = 0;
164 struct test_entry *entry;
165
166 /* break line into command and up to two parameters */
167 cmd = strtok(line.buf, DELIM);
168 /* ignore empty lines */
169 if (!cmd || *cmd == '#')
170 continue;
171
172 p1 = strtok(NULL, DELIM);
173 if (p1) {
174 hash = icase ? strihash(p1) : strhash(p1);
175 p2 = strtok(NULL, DELIM);
176 }
177
178 if (!strcmp("add", cmd) && p1 && p2) {
179
180 /* create entry with key = p1, value = p2 */
181 entry = alloc_test_entry(hash, p1, p2);
182
183 /* add to hashmap */
184 hashmap_add(&map, &entry->ent);
185
186 } else if (!strcmp("put", cmd) && p1 && p2) {
187
188 /* create entry with key = p1, value = p2 */
189 entry = alloc_test_entry(hash, p1, p2);
190
191 /* add / replace entry */
192 entry = hashmap_put_entry(&map, entry,
193 struct test_entry,
194 ent /* member name */);
195
196 /* print and free replaced entry, if any */
197 puts(entry ? get_value(entry) : "NULL");
198 free(entry);
199
200 } else if (!strcmp("get", cmd) && p1) {
201 /* lookup entry in hashmap */
202 entry = hashmap_get_entry_from_hash(&map, hash, p1,
203 struct test_entry, ent);
204
205 /* print result */
206 if (!entry)
207 puts("NULL");
208 hashmap_for_each_entry_from(&map, entry,
209 struct test_entry, ent) {
210 puts(get_value(entry));
211 }
212
213 } else if (!strcmp("remove", cmd) && p1) {
214
215 /* setup static key */
216 struct hashmap_entry key;
217 struct hashmap_entry *rm;
218 hashmap_entry_init(&key, hash);
219
220 /* remove entry from hashmap */
221 rm = hashmap_remove(&map, &key, p1);
222 entry = rm ? container_of(rm, struct test_entry, ent)
223 : NULL;
224
225 /* print result and free entry*/
226 puts(entry ? get_value(entry) : "NULL");
227 free(entry);
228
229 } else if (!strcmp("iterate", cmd)) {
230 struct hashmap_iter iter;
231
232 hashmap_for_each_entry(&map, &iter, entry,
233 struct test_entry,
234 ent /* member name */)
235 printf("%s %s\n", entry->key, get_value(entry));
236
237 } else if (!strcmp("size", cmd)) {
238
239 /* print table sizes */
240 printf("%u %u\n", map.tablesize,
241 hashmap_get_size(&map));
242
243 } else if (!strcmp("intern", cmd) && p1) {
244
245 /* test that strintern works */
246 const char *i1 = strintern(p1);
247 const char *i2 = strintern(p1);
248 if (strcmp(i1, p1))
249 printf("strintern(%s) returns %s\n", p1, i1);
250 else if (i1 == p1)
251 printf("strintern(%s) returns input pointer\n", p1);
252 else if (i1 != i2)
253 printf("strintern(%s) != strintern(%s)", i1, i2);
254 else
255 printf("%s\n", i1);
256
257 } else if (!strcmp("perfhashmap", cmd) && p1 && p2) {
258
259 perf_hashmap(atoi(p1), atoi(p2));
260
261 } else {
262
263 printf("Unknown command %s\n", cmd);
264
265 }
266 }
267
268 strbuf_release(&line);
269 hashmap_free_entries(&map, struct test_entry, ent);
270 return 0;
271 }