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
= xmalloc(st_add4(sizeof(*entry
), klen
, vlen
, 2));
36 hashmap_entry_init(entry
, hash
);
37 memcpy(entry
->key
, key
, klen
+ 1);
38 memcpy(entry
->key
+ klen
+ 1, value
, vlen
+ 1);
42 #define HASH_METHOD_FNV 0
43 #define HASH_METHOD_I 1
44 #define HASH_METHOD_IDIV10 2
45 #define HASH_METHOD_0 3
46 #define HASH_METHOD_X2 4
49 #define TEST_SIZE 100000
51 static unsigned int hash(unsigned int method
, unsigned int i
, const char *key
)
53 unsigned int hash
= 0;
62 case HASH_METHOD_IDIV10
:
70 if (method
& HASH_METHOD_X2
)
76 * Test performance of hashmap.[ch]
77 * Usage: time echo "perfhashmap method rounds" | test-hashmap
79 static void perf_hashmap(unsigned int method
, unsigned int rounds
)
83 struct test_entry
**entries
;
87 ALLOC_ARRAY(entries
, TEST_SIZE
);
88 ALLOC_ARRAY(hashes
, TEST_SIZE
);
89 for (i
= 0; i
< TEST_SIZE
; i
++) {
90 snprintf(buf
, sizeof(buf
), "%i", i
);
91 entries
[i
] = alloc_test_entry(0, buf
, strlen(buf
), "", 0);
92 hashes
[i
] = hash(method
, i
, entries
[i
]->key
);
95 if (method
& TEST_ADD
) {
96 /* test adding to the map */
97 for (j
= 0; j
< rounds
; j
++) {
98 hashmap_init(&map
, test_entry_cmp
, NULL
, 0);
101 for (i
= 0; i
< TEST_SIZE
; i
++) {
102 hashmap_entry_init(entries
[i
], hashes
[i
]);
103 hashmap_add(&map
, entries
[i
]);
106 hashmap_free(&map
, 0);
109 /* test map lookups */
110 hashmap_init(&map
, test_entry_cmp
, NULL
, 0);
112 /* fill the map (sparsely if specified) */
113 j
= (method
& TEST_SPARSE
) ? TEST_SIZE
/ 10 : TEST_SIZE
;
114 for (i
= 0; i
< j
; i
++) {
115 hashmap_entry_init(entries
[i
], hashes
[i
]);
116 hashmap_add(&map
, entries
[i
]);
119 for (j
= 0; j
< rounds
; j
++) {
120 for (i
= 0; i
< TEST_SIZE
; i
++) {
121 hashmap_get_from_hash(&map
, hashes
[i
],
126 hashmap_free(&map
, 0);
130 #define DELIM " \t\r\n"
133 * Read stdin line by line and print result of commands to stdout:
135 * hash key -> strhash(key) memhash(key) strihash(key) memihash(key)
136 * put key value -> NULL / old value
137 * get key -> NULL / value
138 * remove key -> NULL / old value
139 * iterate -> key1 value1\nkey2 value2\n...
140 * size -> tablesize numentries
142 * perfhashmap method rounds -> test hashmap.[ch] performance
144 int cmd_main(int argc
, const char **argv
)
151 icase
= argc
> 1 && !strcmp("ignorecase", argv
[1]);
152 hashmap_init(&map
, test_entry_cmp
, &icase
, 0);
154 /* process commands from stdin */
155 while (fgets(line
, sizeof(line
), stdin
)) {
156 char *cmd
, *p1
= NULL
, *p2
= NULL
;
157 int l1
= 0, l2
= 0, hash
= 0;
158 struct test_entry
*entry
;
160 /* break line into command and up to two parameters */
161 cmd
= strtok(line
, DELIM
);
162 /* ignore empty lines */
163 if (!cmd
|| *cmd
== '#')
166 p1
= strtok(NULL
, DELIM
);
169 hash
= icase
? strihash(p1
) : strhash(p1
);
170 p2
= strtok(NULL
, DELIM
);
175 if (!strcmp("hash", cmd
) && l1
) {
177 /* print results of different hash functions */
178 printf("%u %u %u %u\n", strhash(p1
), memhash(p1
, l1
),
179 strihash(p1
), memihash(p1
, l1
));
181 } else if (!strcmp("add", cmd
) && l1
&& l2
) {
183 /* create entry with key = p1, value = p2 */
184 entry
= alloc_test_entry(hash
, p1
, l1
, p2
, l2
);
187 hashmap_add(&map
, entry
);
189 } else if (!strcmp("put", cmd
) && l1
&& l2
) {
191 /* create entry with key = p1, value = p2 */
192 entry
= alloc_test_entry(hash
, p1
, l1
, p2
, l2
);
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
) && l1
) {
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
) && l1
) {
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
) && l1
) {
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
) && l1
&& l2
) {
256 perf_hashmap(atoi(p1
), atoi(p2
));
260 printf("Unknown command %s\n", cmd
);
265 hashmap_free(&map
, 1);