]>
git.ipfire.org Git - thirdparty/git.git/blob - t/helper/test-hashmap.c
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(unsigned int hash
,
34 char *key
, char *value
)
36 size_t klen
= strlen(key
);
37 size_t vlen
= strlen(value
);
38 struct test_entry
*entry
= xmalloc(st_add4(sizeof(*entry
), klen
, vlen
, 2));
39 hashmap_entry_init(entry
, hash
);
40 memcpy(entry
->key
, key
, klen
+ 1);
41 memcpy(entry
->key
+ klen
+ 1, value
, vlen
+ 1);
45 #define HASH_METHOD_FNV 0
46 #define HASH_METHOD_I 1
47 #define HASH_METHOD_IDIV10 2
48 #define HASH_METHOD_0 3
49 #define HASH_METHOD_X2 4
52 #define TEST_SIZE 100000
54 static unsigned int hash(unsigned int method
, unsigned int i
, const char *key
)
56 unsigned int hash
= 0;
65 case HASH_METHOD_IDIV10
:
73 if (method
& HASH_METHOD_X2
)
79 * Test performance of hashmap.[ch]
80 * Usage: time echo "perfhashmap method rounds" | test-hashmap
82 static void perf_hashmap(unsigned int method
, unsigned int rounds
)
86 struct test_entry
**entries
;
90 ALLOC_ARRAY(entries
, TEST_SIZE
);
91 ALLOC_ARRAY(hashes
, TEST_SIZE
);
92 for (i
= 0; i
< TEST_SIZE
; i
++) {
93 xsnprintf(buf
, sizeof(buf
), "%i", i
);
94 entries
[i
] = alloc_test_entry(0, buf
, "");
95 hashes
[i
] = hash(method
, i
, entries
[i
]->key
);
98 if (method
& TEST_ADD
) {
99 /* test adding to the map */
100 for (j
= 0; j
< rounds
; j
++) {
101 hashmap_init(&map
, test_entry_cmp
, NULL
, 0);
104 for (i
= 0; i
< TEST_SIZE
; i
++) {
105 hashmap_entry_init(entries
[i
], hashes
[i
]);
106 hashmap_add(&map
, entries
[i
]);
109 hashmap_free(&map
, 0);
112 /* test map lookups */
113 hashmap_init(&map
, test_entry_cmp
, NULL
, 0);
115 /* fill the map (sparsely if specified) */
116 j
= (method
& TEST_SPARSE
) ? TEST_SIZE
/ 10 : TEST_SIZE
;
117 for (i
= 0; i
< j
; i
++) {
118 hashmap_entry_init(entries
[i
], hashes
[i
]);
119 hashmap_add(&map
, entries
[i
]);
122 for (j
= 0; j
< rounds
; j
++) {
123 for (i
= 0; i
< TEST_SIZE
; i
++) {
124 hashmap_get_from_hash(&map
, hashes
[i
],
129 hashmap_free(&map
, 0);
133 #define DELIM " \t\r\n"
136 * Read stdin line by line and print result of commands to stdout:
138 * hash key -> strhash(key) memhash(key) strihash(key) memihash(key)
139 * put key value -> NULL / old value
140 * get key -> NULL / value
141 * remove key -> NULL / old value
142 * iterate -> key1 value1\nkey2 value2\n...
143 * size -> tablesize numentries
145 * perfhashmap method rounds -> test hashmap.[ch] performance
147 int cmd_main(int argc
, const char **argv
)
149 struct strbuf line
= STRBUF_INIT
;
154 icase
= argc
> 1 && !strcmp("ignorecase", argv
[1]);
155 hashmap_init(&map
, test_entry_cmp
, &icase
, 0);
157 /* process commands from stdin */
158 while (strbuf_getline(&line
, stdin
) != EOF
) {
159 char *cmd
, *p1
= NULL
, *p2
= NULL
;
160 unsigned int hash
= 0;
161 struct test_entry
*entry
;
163 /* break line into command and up to two parameters */
164 cmd
= strtok(line
.buf
, DELIM
);
165 /* ignore empty lines */
166 if (!cmd
|| *cmd
== '#')
169 p1
= strtok(NULL
, DELIM
);
171 hash
= icase
? strihash(p1
) : strhash(p1
);
172 p2
= strtok(NULL
, DELIM
);
175 if (!strcmp("hash", cmd
) && p1
) {
177 /* print results of different hash functions */
178 printf("%u %u %u %u\n",
179 strhash(p1
), memhash(p1
, strlen(p1
)),
180 strihash(p1
), memihash(p1
, strlen(p1
)));
182 } else if (!strcmp("add", cmd
) && p1
&& p2
) {
184 /* create entry with key = p1, value = p2 */
185 entry
= alloc_test_entry(hash
, p1
, p2
);
188 hashmap_add(&map
, entry
);
190 } else if (!strcmp("put", cmd
) && p1
&& p2
) {
192 /* create entry with key = p1, value = p2 */
193 entry
= alloc_test_entry(hash
, p1
, p2
);
195 /* add / replace entry */
196 entry
= hashmap_put(&map
, entry
);
198 /* print and free replaced entry, if any */
199 puts(entry
? get_value(entry
) : "NULL");
202 } else if (!strcmp("get", cmd
) && p1
) {
204 /* lookup entry in hashmap */
205 entry
= hashmap_get_from_hash(&map
, hash
, p1
);
211 puts(get_value(entry
));
212 entry
= hashmap_get_next(&map
, entry
);
215 } else if (!strcmp("remove", cmd
) && p1
) {
217 /* setup static key */
218 struct hashmap_entry key
;
219 hashmap_entry_init(&key
, hash
);
221 /* remove entry from hashmap */
222 entry
= hashmap_remove(&map
, &key
, p1
);
224 /* print result and free entry*/
225 puts(entry
? get_value(entry
) : "NULL");
228 } else if (!strcmp("iterate", cmd
)) {
230 struct hashmap_iter iter
;
231 hashmap_iter_init(&map
, &iter
);
232 while ((entry
= hashmap_iter_next(&iter
)))
233 printf("%s %s\n", entry
->key
, get_value(entry
));
235 } else if (!strcmp("size", cmd
)) {
237 /* print table sizes */
238 printf("%u %u\n", map
.tablesize
,
239 hashmap_get_size(&map
));
241 } else if (!strcmp("intern", cmd
) && p1
) {
243 /* test that strintern works */
244 const char *i1
= strintern(p1
);
245 const char *i2
= strintern(p1
);
247 printf("strintern(%s) returns %s\n", p1
, i1
);
249 printf("strintern(%s) returns input pointer\n", p1
);
251 printf("strintern(%s) != strintern(%s)", i1
, i2
);
255 } else if (!strcmp("perfhashmap", cmd
) && p1
&& p2
) {
257 perf_hashmap(atoi(p1
), atoi(p2
));
261 printf("Unknown command %s\n", cmd
);
266 strbuf_release(&line
);
267 hashmap_free(&map
, 1);