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