1 #include "git-compat-util.h"
7 struct hashmap_entry ent
;
8 /* key and value as two \0-terminated strings */
12 static const char *get_value(const struct test_entry
*e
)
14 return e
->key
+ strlen(e
->key
) + 1;
17 static int test_entry_cmp(const void *cmp_data
,
19 const void *entry_or_key
,
22 const int ignore_case
= cmp_data
? *((int *)cmp_data
) : 0;
23 const struct test_entry
*e1
= entry
;
24 const struct test_entry
*e2
= entry_or_key
;
25 const char *key
= keydata
;
28 return strcasecmp(e1
->key
, key
? key
: e2
->key
);
30 return strcmp(e1
->key
, key
? key
: e2
->key
);
33 static struct test_entry
*alloc_test_entry(int hash
, char *key
, char *value
)
35 size_t klen
= strlen(key
);
36 size_t vlen
= strlen(value
);
37 struct test_entry
*entry
= xmalloc(st_add4(sizeof(*entry
), klen
, vlen
, 2));
38 hashmap_entry_init(entry
, hash
);
39 memcpy(entry
->key
, key
, klen
+ 1);
40 memcpy(entry
->key
+ klen
+ 1, value
, vlen
+ 1);
44 #define HASH_METHOD_FNV 0
45 #define HASH_METHOD_I 1
46 #define HASH_METHOD_IDIV10 2
47 #define HASH_METHOD_0 3
48 #define HASH_METHOD_X2 4
51 #define TEST_SIZE 100000
53 static unsigned int hash(unsigned int method
, unsigned int i
, const char *key
)
55 unsigned int hash
= 0;
64 case HASH_METHOD_IDIV10
:
72 if (method
& HASH_METHOD_X2
)
78 * Test performance of hashmap.[ch]
79 * Usage: time echo "perfhashmap method rounds" | test-hashmap
81 static void perf_hashmap(unsigned int method
, unsigned int rounds
)
85 struct test_entry
**entries
;
89 ALLOC_ARRAY(entries
, TEST_SIZE
);
90 ALLOC_ARRAY(hashes
, TEST_SIZE
);
91 for (i
= 0; i
< TEST_SIZE
; i
++) {
92 xsnprintf(buf
, sizeof(buf
), "%i", i
);
93 entries
[i
] = alloc_test_entry(0, buf
, "");
94 hashes
[i
] = hash(method
, i
, entries
[i
]->key
);
97 if (method
& TEST_ADD
) {
98 /* test adding to the map */
99 for (j
= 0; j
< rounds
; j
++) {
100 hashmap_init(&map
, test_entry_cmp
, NULL
, 0);
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
, 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
)
148 struct strbuf line
= STRBUF_INIT
;
153 icase
= argc
> 1 && !strcmp("ignorecase", argv
[1]);
154 hashmap_init(&map
, test_entry_cmp
, &icase
, 0);
156 /* process commands from stdin */
157 while (strbuf_getline(&line
, stdin
) != EOF
) {
158 char *cmd
, *p1
= NULL
, *p2
= NULL
;
160 struct test_entry
*entry
;
162 /* break line into command and up to two parameters */
163 cmd
= strtok(line
.buf
, DELIM
);
164 /* ignore empty lines */
165 if (!cmd
|| *cmd
== '#')
168 p1
= strtok(NULL
, DELIM
);
170 hash
= icase
? strihash(p1
) : strhash(p1
);
171 p2
= strtok(NULL
, DELIM
);
174 if (!strcmp("hash", cmd
) && p1
) {
176 /* print results of different hash functions */
177 printf("%u %u %u %u\n",
178 strhash(p1
), memhash(p1
, strlen(p1
)),
179 strihash(p1
), memihash(p1
, strlen(p1
)));
181 } else if (!strcmp("add", cmd
) && p1
&& p2
) {
183 /* create entry with key = p1, value = p2 */
184 entry
= alloc_test_entry(hash
, p1
, p2
);
187 hashmap_add(&map
, entry
);
189 } else if (!strcmp("put", cmd
) && p1
&& p2
) {
191 /* create entry with key = p1, value = p2 */
192 entry
= alloc_test_entry(hash
, p1
, p2
);
194 /* add / replace entry */
195 entry
= hashmap_put(&map
, entry
);
197 /* print and free replaced entry, if any */
198 puts(entry
? get_value(entry
) : "NULL");
201 } else if (!strcmp("get", cmd
) && p1
) {
203 /* lookup entry in hashmap */
204 entry
= hashmap_get_from_hash(&map
, hash
, p1
);
210 puts(get_value(entry
));
211 entry
= hashmap_get_next(&map
, entry
);
214 } else if (!strcmp("remove", cmd
) && p1
) {
216 /* setup static key */
217 struct hashmap_entry key
;
218 hashmap_entry_init(&key
, hash
);
220 /* remove entry from hashmap */
221 entry
= hashmap_remove(&map
, &key
, p1
);
223 /* print result and free entry*/
224 puts(entry
? get_value(entry
) : "NULL");
227 } else if (!strcmp("iterate", cmd
)) {
229 struct hashmap_iter iter
;
230 hashmap_iter_init(&map
, &iter
);
231 while ((entry
= hashmap_iter_next(&iter
)))
232 printf("%s %s\n", entry
->key
, get_value(entry
));
234 } else if (!strcmp("size", cmd
)) {
236 /* print table sizes */
237 printf("%u %u\n", map
.tablesize
,
238 hashmap_get_size(&map
));
240 } else if (!strcmp("intern", cmd
) && p1
) {
242 /* test that strintern works */
243 const char *i1
= strintern(p1
);
244 const char *i2
= strintern(p1
);
246 printf("strintern(%s) returns %s\n", p1
, i1
);
248 printf("strintern(%s) returns input pointer\n", p1
);
250 printf("strintern(%s) != strintern(%s)", i1
, i2
);
254 } else if (!strcmp("perfhashmap", cmd
) && p1
&& p2
) {
256 perf_hashmap(atoi(p1
), atoi(p2
));
260 printf("Unknown command %s\n", cmd
);
265 strbuf_release(&line
);
266 hashmap_free(&map
, 1);