2 #include "git-compat-util.h"
5 #include "string-list.h"
9 int padding
; /* hashmap entry no longer needs to be the first member */
10 struct hashmap_entry ent
;
11 /* key and value as two \0-terminated strings */
15 static const char *get_value(const struct test_entry
*e
)
17 return e
->key
+ strlen(e
->key
) + 1;
20 static int test_entry_cmp(const void *cmp_data
,
21 const struct hashmap_entry
*eptr
,
22 const struct hashmap_entry
*entry_or_key
,
25 const int ignore_case
= cmp_data
? *((int *)cmp_data
) : 0;
26 const struct test_entry
*e1
, *e2
;
27 const char *key
= keydata
;
29 e1
= container_of(eptr
, const struct test_entry
, ent
);
30 e2
= container_of(entry_or_key
, const struct test_entry
, ent
);
33 return strcasecmp(e1
->key
, key
? key
: e2
->key
);
35 return strcmp(e1
->key
, key
? key
: e2
->key
);
38 static struct test_entry
*alloc_test_entry(unsigned int hash
,
39 char *key
, char *value
)
41 size_t klen
= strlen(key
);
42 size_t vlen
= strlen(value
);
43 struct test_entry
*entry
= xmalloc(st_add4(sizeof(*entry
), klen
, vlen
, 2));
44 hashmap_entry_init(&entry
->ent
, hash
);
45 memcpy(entry
->key
, key
, klen
+ 1);
46 memcpy(entry
->key
+ klen
+ 1, value
, vlen
+ 1);
50 #define HASH_METHOD_FNV 0
51 #define HASH_METHOD_I 1
52 #define HASH_METHOD_IDIV10 2
53 #define HASH_METHOD_0 3
54 #define HASH_METHOD_X2 4
57 #define TEST_SIZE 100000
59 static unsigned int hash(unsigned int method
, unsigned int i
, const char *key
)
61 unsigned int hash
= 0;
70 case HASH_METHOD_IDIV10
:
78 if (method
& HASH_METHOD_X2
)
84 * Test performance of hashmap.[ch]
85 * Usage: time echo "perfhashmap method rounds" | test-tool hashmap
87 static void perf_hashmap(unsigned int method
, unsigned int rounds
)
91 struct test_entry
**entries
;
95 ALLOC_ARRAY(entries
, TEST_SIZE
);
96 ALLOC_ARRAY(hashes
, TEST_SIZE
);
97 for (i
= 0; i
< TEST_SIZE
; i
++) {
98 xsnprintf(buf
, sizeof(buf
), "%i", i
);
99 entries
[i
] = alloc_test_entry(0, buf
, "");
100 hashes
[i
] = hash(method
, i
, entries
[i
]->key
);
103 if (method
& TEST_ADD
) {
104 /* test adding to the map */
105 for (j
= 0; j
< rounds
; j
++) {
106 hashmap_init(&map
, test_entry_cmp
, NULL
, 0);
109 for (i
= 0; i
< TEST_SIZE
; i
++) {
110 hashmap_entry_init(&entries
[i
]->ent
, hashes
[i
]);
111 hashmap_add(&map
, &entries
[i
]->ent
);
117 /* test map lookups */
118 hashmap_init(&map
, test_entry_cmp
, NULL
, 0);
120 /* fill the map (sparsely if specified) */
121 j
= (method
& TEST_SPARSE
) ? TEST_SIZE
/ 10 : TEST_SIZE
;
122 for (i
= 0; i
< j
; i
++) {
123 hashmap_entry_init(&entries
[i
]->ent
, hashes
[i
]);
124 hashmap_add(&map
, &entries
[i
]->ent
);
127 for (j
= 0; j
< rounds
; j
++) {
128 for (i
= 0; i
< TEST_SIZE
; i
++) {
129 hashmap_get_from_hash(&map
, hashes
[i
],
138 #define DELIM " \t\r\n"
141 * Read stdin line by line and print result of commands to stdout:
143 * hash key -> strhash(key) memhash(key) strihash(key) memihash(key)
144 * put key value -> NULL / old value
145 * get key -> NULL / value
146 * remove key -> NULL / old value
147 * iterate -> key1 value1\nkey2 value2\n...
148 * size -> tablesize numentries
150 * perfhashmap method rounds -> test hashmap.[ch] performance
152 int cmd__hashmap(int argc
, const char **argv
)
154 struct string_list parts
= STRING_LIST_INIT_NODUP
;
155 struct strbuf line
= STRBUF_INIT
;
157 struct hashmap map
= HASHMAP_INIT(test_entry_cmp
, &icase
);
160 icase
= argc
> 1 && !strcmp("ignorecase", argv
[1]);
162 /* process commands from stdin */
163 while (strbuf_getline(&line
, stdin
) != EOF
) {
165 unsigned int hash
= 0;
166 struct test_entry
*entry
;
168 /* break line into command and up to two parameters */
169 string_list_setlen(&parts
, 0);
170 string_list_split_in_place(&parts
, line
.buf
, DELIM
, 2);
171 string_list_remove_empty_items(&parts
, 0);
173 /* ignore empty lines */
176 if (!*parts
.items
[0].string
|| *parts
.items
[0].string
== '#')
179 cmd
= parts
.items
[0].string
;
180 p1
= parts
.nr
>= 1 ? parts
.items
[1].string
: NULL
;
181 p2
= parts
.nr
>= 2 ? parts
.items
[2].string
: NULL
;
183 hash
= icase
? strihash(p1
) : strhash(p1
);
185 if (!strcmp("add", cmd
) && p1
&& p2
) {
187 /* create entry with key = p1, value = p2 */
188 entry
= alloc_test_entry(hash
, p1
, p2
);
191 hashmap_add(&map
, &entry
->ent
);
193 } else if (!strcmp("put", cmd
) && p1
&& p2
) {
195 /* create entry with key = p1, value = p2 */
196 entry
= alloc_test_entry(hash
, p1
, p2
);
198 /* add / replace entry */
199 entry
= hashmap_put_entry(&map
, entry
, ent
);
201 /* print and free replaced entry, if any */
202 puts(entry
? get_value(entry
) : "NULL");
205 } else if (!strcmp("get", cmd
) && p1
) {
206 /* lookup entry in hashmap */
207 entry
= hashmap_get_entry_from_hash(&map
, hash
, p1
,
208 struct test_entry
, ent
);
213 hashmap_for_each_entry_from(&map
, entry
, ent
)
214 puts(get_value(entry
));
216 } else if (!strcmp("remove", cmd
) && p1
) {
218 /* setup static key */
219 struct hashmap_entry key
;
220 struct hashmap_entry
*rm
;
221 hashmap_entry_init(&key
, hash
);
223 /* remove entry from hashmap */
224 rm
= hashmap_remove(&map
, &key
, p1
);
225 entry
= rm
? container_of(rm
, struct test_entry
, ent
)
228 /* print result and free entry*/
229 puts(entry
? get_value(entry
) : "NULL");
232 } else if (!strcmp("iterate", cmd
)) {
233 struct hashmap_iter iter
;
235 hashmap_for_each_entry(&map
, &iter
, entry
,
236 ent
/* member name */)
237 printf("%s %s\n", entry
->key
, get_value(entry
));
239 } else if (!strcmp("size", cmd
)) {
241 /* print table sizes */
242 printf("%u %u\n", map
.tablesize
,
243 hashmap_get_size(&map
));
245 } else if (!strcmp("intern", cmd
) && p1
) {
247 /* test that strintern works */
248 const char *i1
= strintern(p1
);
249 const char *i2
= strintern(p1
);
251 printf("strintern(%s) returns %s\n", p1
, i1
);
253 printf("strintern(%s) returns input pointer\n", p1
);
255 printf("strintern(%s) != strintern(%s)", i1
, i2
);
259 } else if (!strcmp("perfhashmap", cmd
) && p1
&& p2
) {
261 perf_hashmap(atoi(p1
), atoi(p2
));
265 printf("Unknown command %s\n", cmd
);
270 string_list_clear(&parts
, 0);
271 strbuf_release(&line
);
272 hashmap_clear_and_free(&map
, struct test_entry
, ent
);