1 #include "git-compat-util.h"
6 struct hashmap_entry ent
;
7 /* key and value as two \0-terminated strings */
11 static const char *get_value(const struct test_entry
*e
)
13 return e
->key
+ strlen(e
->key
) + 1;
16 static int test_entry_cmp(const void *unused_cmp_data
,
17 const struct test_entry
*e1
,
18 const struct test_entry
*e2
,
21 return strcmp(e1
->key
, key
? key
: e2
->key
);
24 static int test_entry_cmp_icase(const void *unused_cmp_data
,
25 const struct test_entry
*e1
,
26 const struct test_entry
*e2
,
29 return strcasecmp(e1
->key
, key
? key
: e2
->key
);
32 static struct test_entry
*alloc_test_entry(int hash
, char *key
, int klen
,
33 char *value
, int vlen
)
35 struct test_entry
*entry
= malloc(sizeof(struct test_entry
) + klen
37 hashmap_entry_init(entry
, hash
);
38 memcpy(entry
->key
, key
, klen
+ 1);
39 memcpy(entry
->key
+ klen
+ 1, value
, vlen
+ 1);
43 #define HASH_METHOD_FNV 0
44 #define HASH_METHOD_I 1
45 #define HASH_METHOD_IDIV10 2
46 #define HASH_METHOD_0 3
47 #define HASH_METHOD_X2 4
50 #define TEST_SIZE 100000
52 static unsigned int hash(unsigned int method
, unsigned int i
, const char *key
)
54 unsigned int hash
= 0;
63 case HASH_METHOD_IDIV10
:
71 if (method
& HASH_METHOD_X2
)
77 * Test performance of hashmap.[ch]
78 * Usage: time echo "perfhashmap method rounds" | test-hashmap
80 static void perf_hashmap(unsigned int method
, unsigned int rounds
)
84 struct test_entry
**entries
;
88 entries
= malloc(TEST_SIZE
* sizeof(struct test_entry
*));
89 hashes
= malloc(TEST_SIZE
* sizeof(int));
90 for (i
= 0; i
< TEST_SIZE
; i
++) {
91 snprintf(buf
, sizeof(buf
), "%i", i
);
92 entries
[i
] = alloc_test_entry(0, buf
, strlen(buf
), "", 0);
93 hashes
[i
] = hash(method
, i
, entries
[i
]->key
);
96 if (method
& TEST_ADD
) {
97 /* test adding to the map */
98 for (j
= 0; j
< rounds
; j
++) {
99 hashmap_init(&map
, (hashmap_cmp_fn
) test_entry_cmp
,
103 for (i
= 0; i
< TEST_SIZE
; i
++) {
104 hashmap_entry_init(entries
[i
], hashes
[i
]);
105 hashmap_add(&map
, entries
[i
]);
108 hashmap_free(&map
, 0);
111 /* test map lookups */
112 hashmap_init(&map
, (hashmap_cmp_fn
) test_entry_cmp
, NULL
, 0);
114 /* fill the map (sparsely if specified) */
115 j
= (method
& TEST_SPARSE
) ? TEST_SIZE
/ 10 : TEST_SIZE
;
116 for (i
= 0; i
< j
; i
++) {
117 hashmap_entry_init(entries
[i
], hashes
[i
]);
118 hashmap_add(&map
, entries
[i
]);
121 for (j
= 0; j
< rounds
; j
++) {
122 for (i
= 0; i
< TEST_SIZE
; i
++) {
123 hashmap_get_from_hash(&map
, hashes
[i
],
128 hashmap_free(&map
, 0);
132 #define DELIM " \t\r\n"
135 * Read stdin line by line and print result of commands to stdout:
137 * hash key -> strhash(key) memhash(key) strihash(key) memihash(key)
138 * put key value -> NULL / old value
139 * get key -> NULL / value
140 * remove key -> NULL / old value
141 * iterate -> key1 value1\nkey2 value2\n...
142 * size -> tablesize numentries
144 * perfhashmap method rounds -> test hashmap.[ch] performance
146 int cmd_main(int argc
, const char **argv
)
153 icase
= argc
> 1 && !strcmp("ignorecase", argv
[1]);
154 hashmap_init(&map
, (hashmap_cmp_fn
) (icase
? test_entry_cmp_icase
155 : test_entry_cmp
), NULL
, 0);
157 /* process commands from stdin */
158 while (fgets(line
, sizeof(line
), stdin
)) {
159 char *cmd
, *p1
= NULL
, *p2
= NULL
;
160 int l1
= 0, l2
= 0, hash
= 0;
161 struct test_entry
*entry
;
163 /* break line into command and up to two parameters */
164 cmd
= strtok(line
, DELIM
);
165 /* ignore empty lines */
166 if (!cmd
|| *cmd
== '#')
169 p1
= strtok(NULL
, DELIM
);
172 hash
= icase
? strihash(p1
) : strhash(p1
);
173 p2
= strtok(NULL
, DELIM
);
178 if (!strcmp("hash", cmd
) && l1
) {
180 /* print results of different hash functions */
181 printf("%u %u %u %u\n", strhash(p1
), memhash(p1
, l1
),
182 strihash(p1
), memihash(p1
, l1
));
184 } else if (!strcmp("add", cmd
) && l1
&& l2
) {
186 /* create entry with key = p1, value = p2 */
187 entry
= alloc_test_entry(hash
, p1
, l1
, p2
, l2
);
190 hashmap_add(&map
, entry
);
192 } else if (!strcmp("put", cmd
) && l1
&& l2
) {
194 /* create entry with key = p1, value = p2 */
195 entry
= alloc_test_entry(hash
, p1
, l1
, p2
, l2
);
197 /* add / replace entry */
198 entry
= hashmap_put(&map
, entry
);
200 /* print and free replaced entry, if any */
201 puts(entry
? get_value(entry
) : "NULL");
204 } else if (!strcmp("get", cmd
) && l1
) {
206 /* lookup entry in hashmap */
207 entry
= hashmap_get_from_hash(&map
, hash
, p1
);
213 puts(get_value(entry
));
214 entry
= hashmap_get_next(&map
, entry
);
217 } else if (!strcmp("remove", cmd
) && l1
) {
219 /* setup static key */
220 struct hashmap_entry key
;
221 hashmap_entry_init(&key
, hash
);
223 /* remove entry from hashmap */
224 entry
= hashmap_remove(&map
, &key
, p1
);
226 /* print result and free entry*/
227 puts(entry
? get_value(entry
) : "NULL");
230 } else if (!strcmp("iterate", cmd
)) {
232 struct hashmap_iter iter
;
233 hashmap_iter_init(&map
, &iter
);
234 while ((entry
= hashmap_iter_next(&iter
)))
235 printf("%s %s\n", entry
->key
, get_value(entry
));
237 } else if (!strcmp("size", cmd
)) {
239 /* print table sizes */
240 printf("%u %u\n", map
.tablesize
, map
.size
);
242 } else if (!strcmp("intern", cmd
) && l1
) {
244 /* test that strintern works */
245 const char *i1
= strintern(p1
);
246 const char *i2
= strintern(p1
);
248 printf("strintern(%s) returns %s\n", p1
, i1
);
250 printf("strintern(%s) returns input pointer\n", p1
);
252 printf("strintern(%s) != strintern(%s)", i1
, i2
);
256 } else if (!strcmp("perfhashmap", cmd
) && l1
&& l2
) {
258 perf_hashmap(atoi(p1
), atoi(p2
));
262 printf("Unknown command %s\n", cmd
);
267 hashmap_free(&map
, 1);