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 *cmp_data
,
18 const void *entry_or_key
,
21 const int ignore_case
= cmp_data
? *((int *)cmp_data
) : 0;
22 const struct test_entry
*e1
= entry
;
23 const struct test_entry
*e2
= entry_or_key
;
24 const char *key
= keydata
;
27 return strcasecmp(e1
->key
, key
? key
: e2
->key
);
29 return strcmp(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
, test_entry_cmp
, NULL
, 0);
102 for (i
= 0; i
< TEST_SIZE
; i
++) {
103 hashmap_entry_init(entries
[i
], hashes
[i
]);
104 hashmap_add(&map
, entries
[i
]);
107 hashmap_free(&map
, 0);
110 /* test map lookups */
111 hashmap_init(&map
, test_entry_cmp
, NULL
, 0);
113 /* fill the map (sparsely if specified) */
114 j
= (method
& TEST_SPARSE
) ? TEST_SIZE
/ 10 : TEST_SIZE
;
115 for (i
= 0; i
< j
; i
++) {
116 hashmap_entry_init(entries
[i
], hashes
[i
]);
117 hashmap_add(&map
, entries
[i
]);
120 for (j
= 0; j
< rounds
; j
++) {
121 for (i
= 0; i
< TEST_SIZE
; i
++) {
122 hashmap_get_from_hash(&map
, hashes
[i
],
127 hashmap_free(&map
, 0);
131 #define DELIM " \t\r\n"
134 * Read stdin line by line and print result of commands to stdout:
136 * hash key -> strhash(key) memhash(key) strihash(key) memihash(key)
137 * put key value -> NULL / old value
138 * get key -> NULL / value
139 * remove key -> NULL / old value
140 * iterate -> key1 value1\nkey2 value2\n...
141 * size -> tablesize numentries
143 * perfhashmap method rounds -> test hashmap.[ch] performance
145 int cmd_main(int argc
, const char **argv
)
152 icase
= argc
> 1 && !strcmp("ignorecase", argv
[1]);
153 hashmap_init(&map
, test_entry_cmp
, &icase
, 0);
155 /* process commands from stdin */
156 while (fgets(line
, sizeof(line
), stdin
)) {
157 char *cmd
, *p1
= NULL
, *p2
= NULL
;
158 int l1
= 0, l2
= 0, hash
= 0;
159 struct test_entry
*entry
;
161 /* break line into command and up to two parameters */
162 cmd
= strtok(line
, DELIM
);
163 /* ignore empty lines */
164 if (!cmd
|| *cmd
== '#')
167 p1
= strtok(NULL
, DELIM
);
170 hash
= icase
? strihash(p1
) : strhash(p1
);
171 p2
= strtok(NULL
, DELIM
);
176 if (!strcmp("hash", cmd
) && l1
) {
178 /* print results of different hash functions */
179 printf("%u %u %u %u\n", strhash(p1
), memhash(p1
, l1
),
180 strihash(p1
), memihash(p1
, l1
));
182 } else if (!strcmp("add", cmd
) && l1
&& l2
) {
184 /* create entry with key = p1, value = p2 */
185 entry
= alloc_test_entry(hash
, p1
, l1
, p2
, l2
);
188 hashmap_add(&map
, entry
);
190 } else if (!strcmp("put", cmd
) && l1
&& l2
) {
192 /* create entry with key = p1, value = p2 */
193 entry
= alloc_test_entry(hash
, p1
, l1
, p2
, l2
);
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
) && l1
) {
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
) && l1
) {
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
) && l1
) {
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
) && l1
&& l2
) {
257 perf_hashmap(atoi(p1
), atoi(p2
));
261 printf("Unknown command %s\n", cmd
);
266 hashmap_free(&map
, 1);