[thirdparty/git.git] / t / helper / test-hashmap.c

#include "git-compat-util.h"
#include "hashmap.h"

struct test_entry
{
	struct hashmap_entry ent;
	/* key and value as two \0-terminated strings */
	char key[FLEX_ARRAY];
};

static const char *get_value(const struct test_entry *e)
{
	return e->key + strlen(e->key) + 1;
}

static int test_entry_cmp(const void *unused_cmp_data,
			  const struct test_entry *e1,
			  const struct test_entry *e2,
			  const char* key)
{
	return strcmp(e1->key, key ? key : e2->key);
}

static int test_entry_cmp_icase(const void *unused_cmp_data,
				const struct test_entry *e1,
				const struct test_entry *e2,
				const char* key)
{
	return strcasecmp(e1->key, key ? key : e2->key);
}

static struct test_entry *alloc_test_entry(int hash, char *key, int klen,
		char *value, int vlen)
{
	struct test_entry *entry = malloc(sizeof(struct test_entry) + klen
			+ vlen + 2);
	hashmap_entry_init(entry, hash);
	memcpy(entry->key, key, klen + 1);
	memcpy(entry->key + klen + 1, value, vlen + 1);
	return entry;
}

#define HASH_METHOD_FNV 0
#define HASH_METHOD_I 1
#define HASH_METHOD_IDIV10 2
#define HASH_METHOD_0 3
#define HASH_METHOD_X2 4
#define TEST_SPARSE 8
#define TEST_ADD 16
#define TEST_SIZE 100000

static unsigned int hash(unsigned int method, unsigned int i, const char *key)
{
	unsigned int hash = 0;
	switch (method & 3)
	{
	case HASH_METHOD_FNV:
		hash = strhash(key);
		break;
	case HASH_METHOD_I:
		hash = i;
		break;
	case HASH_METHOD_IDIV10:
		hash = i / 10;
		break;
	case HASH_METHOD_0:
		hash = 0;
		break;
	}

	if (method & HASH_METHOD_X2)
		hash = 2 * hash;
	return hash;
}

/*
 * Test performance of hashmap.[ch]
 * Usage: time echo "perfhashmap method rounds" | test-hashmap
 */
static void perf_hashmap(unsigned int method, unsigned int rounds)
{
	struct hashmap map;
	char buf[16];
	struct test_entry **entries;
	unsigned int *hashes;
	unsigned int i, j;

	entries = malloc(TEST_SIZE * sizeof(struct test_entry *));
	hashes = malloc(TEST_SIZE * sizeof(int));
	for (i = 0; i < TEST_SIZE; i++) {
		snprintf(buf, sizeof(buf), "%i", i);
		entries[i] = alloc_test_entry(0, buf, strlen(buf), "", 0);
		hashes[i] = hash(method, i, entries[i]->key);
	}

	if (method & TEST_ADD) {
		/* test adding to the map */
		for (j = 0; j < rounds; j++) {
			hashmap_init(&map, (hashmap_cmp_fn) test_entry_cmp,
				     NULL, 0);

			/* add entries */
			for (i = 0; i < TEST_SIZE; i++) {
				hashmap_entry_init(entries[i], hashes[i]);
				hashmap_add(&map, entries[i]);
			}

			hashmap_free(&map, 0);
		}
	} else {
		/* test map lookups */
		hashmap_init(&map, (hashmap_cmp_fn) test_entry_cmp, NULL, 0);

		/* fill the map (sparsely if specified) */
		j = (method & TEST_SPARSE) ? TEST_SIZE / 10 : TEST_SIZE;
		for (i = 0; i < j; i++) {
			hashmap_entry_init(entries[i], hashes[i]);
			hashmap_add(&map, entries[i]);
		}

		for (j = 0; j < rounds; j++) {
			for (i = 0; i < TEST_SIZE; i++) {
				hashmap_get_from_hash(&map, hashes[i],
						      entries[i]->key);
			}
		}

		hashmap_free(&map, 0);
	}
}

#define DELIM " \t\r\n"

/*
 * Read stdin line by line and print result of commands to stdout:
 *
 * hash key -> strhash(key) memhash(key) strihash(key) memihash(key)
 * put key value -> NULL / old value
 * get key -> NULL / value
 * remove key -> NULL / old value
 * iterate -> key1 value1\nkey2 value2\n...
 * size -> tablesize numentries
 *
 * perfhashmap method rounds -> test hashmap.[ch] performance
 */
int cmd_main(int argc, const char **argv)
{
	char line[1024];
	struct hashmap map;
	int icase;

	/* init hash map */
	icase = argc > 1 && !strcmp("ignorecase", argv[1]);
	hashmap_init(&map, (hashmap_cmp_fn) (icase ? test_entry_cmp_icase
			: test_entry_cmp), NULL, 0);

	/* process commands from stdin */
	while (fgets(line, sizeof(line), stdin)) {
		char *cmd, *p1 = NULL, *p2 = NULL;
		int l1 = 0, l2 = 0, hash = 0;
		struct test_entry *entry;

		/* break line into command and up to two parameters */
		cmd = strtok(line, DELIM);
		/* ignore empty lines */
		if (!cmd || *cmd == '#')
			continue;

		p1 = strtok(NULL, DELIM);
		if (p1) {
			l1 = strlen(p1);
			hash = icase ? strihash(p1) : strhash(p1);
			p2 = strtok(NULL, DELIM);
			if (p2)
				l2 = strlen(p2);
		}

		if (!strcmp("hash", cmd) && l1) {

			/* print results of different hash functions */
			printf("%u %u %u %u\n", strhash(p1), memhash(p1, l1),
					strihash(p1), memihash(p1, l1));

		} else if (!strcmp("add", cmd) && l1 && l2) {

			/* create entry with key = p1, value = p2 */
			entry = alloc_test_entry(hash, p1, l1, p2, l2);

			/* add to hashmap */
			hashmap_add(&map, entry);

		} else if (!strcmp("put", cmd) && l1 && l2) {

			/* create entry with key = p1, value = p2 */
			entry = alloc_test_entry(hash, p1, l1, p2, l2);

			/* add / replace entry */
			entry = hashmap_put(&map, entry);

			/* print and free replaced entry, if any */
			puts(entry ? get_value(entry) : "NULL");
			free(entry);

		} else if (!strcmp("get", cmd) && l1) {

			/* lookup entry in hashmap */
			entry = hashmap_get_from_hash(&map, hash, p1);

			/* print result */
			if (!entry)
				puts("NULL");
			while (entry) {
				puts(get_value(entry));
				entry = hashmap_get_next(&map, entry);
			}

		} else if (!strcmp("remove", cmd) && l1) {

			/* setup static key */
			struct hashmap_entry key;
			hashmap_entry_init(&key, hash);

			/* remove entry from hashmap */
			entry = hashmap_remove(&map, &key, p1);

			/* print result and free entry*/
			puts(entry ? get_value(entry) : "NULL");
			free(entry);

		} else if (!strcmp("iterate", cmd)) {

			struct hashmap_iter iter;
			hashmap_iter_init(&map, &iter);
			while ((entry = hashmap_iter_next(&iter)))
				printf("%s %s\n", entry->key, get_value(entry));

		} else if (!strcmp("size", cmd)) {

			/* print table sizes */
			printf("%u %u\n", map.tablesize, map.size);

		} else if (!strcmp("intern", cmd) && l1) {

			/* test that strintern works */
			const char *i1 = strintern(p1);
			const char *i2 = strintern(p1);
			if (strcmp(i1, p1))
				printf("strintern(%s) returns %s\n", p1, i1);
			else if (i1 == p1)
				printf("strintern(%s) returns input pointer\n", p1);
			else if (i1 != i2)
				printf("strintern(%s) != strintern(%s)", i1, i2);
			else
				printf("%s\n", i1);

		} else if (!strcmp("perfhashmap", cmd) && l1 && l2) {

			perf_hashmap(atoi(p1), atoi(p2));

		} else {

			printf("Unknown command %s\n", cmd);

		}
	}

	hashmap_free(&map, 1);
	return 0;
}
Commit	Line	Data
e8fa59b9	1	#include "git-compat-util.h"
6a364ced	2	#include "hashmap.h"
6a364ced KB	3
	4	struct test_entry
	5	{
	6	struct hashmap_entry ent;
	7	/* key and value as two \0-terminated strings */
	8	char key[FLEX_ARRAY];
	9	};
	10
	11	static const char get_value(const struct test_entry e)
	12	{
	13	return e->key + strlen(e->key) + 1;
	14	}
	15
7663cdc8 SB	16	static int test_entry_cmp(const void *unused_cmp_data,
	17	const struct test_entry *e1,
	18	const struct test_entry *e2,
	19	const char* key)
6a364ced KB	20	{
	21	return strcmp(e1->key, key ? key : e2->key);
	22	}
	23
7663cdc8 SB	24	static int test_entry_cmp_icase(const void *unused_cmp_data,
	25	const struct test_entry *e1,
	26	const struct test_entry *e2,
	27	const char* key)
6a364ced KB	28	{
	29	return strcasecmp(e1->key, key ? key : e2->key);
	30	}
	31
	32	static struct test_entry alloc_test_entry(int hash, char key, int klen,
	33	char *value, int vlen)
	34	{
	35	struct test_entry *entry = malloc(sizeof(struct test_entry) + klen
	36	+ vlen + 2);
	37	hashmap_entry_init(entry, hash);
	38	memcpy(entry->key, key, klen + 1);
	39	memcpy(entry->key + klen + 1, value, vlen + 1);
	40	return entry;
	41	}
	42
	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
	48	#define TEST_SPARSE 8
	49	#define TEST_ADD 16
	50	#define TEST_SIZE 100000
	51
	52	static unsigned int hash(unsigned int method, unsigned int i, const char *key)
	53	{
3b9a2b07	54	unsigned int hash = 0;
6a364ced KB	55	switch (method & 3)
	56	{
	57	case HASH_METHOD_FNV:
	58	hash = strhash(key);
	59	break;
	60	case HASH_METHOD_I:
	61	hash = i;
	62	break;
	63	case HASH_METHOD_IDIV10:
	64	hash = i / 10;
	65	break;
	66	case HASH_METHOD_0:
	67	hash = 0;
	68	break;
	69	}
	70
	71	if (method & HASH_METHOD_X2)
	72	hash = 2 * hash;
	73	return hash;
	74	}
	75
	76	/*
	77	* Test performance of hashmap.[ch]
	78	* Usage: time echo "perfhashmap method rounds" \| test-hashmap
	79	*/
	80	static void perf_hashmap(unsigned int method, unsigned int rounds)
	81	{
	82	struct hashmap map;
	83	char buf[16];
	84	struct test_entry **entries;
	85	unsigned int *hashes;
	86	unsigned int i, j;
	87
	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);
	94	}
	95
	96	if (method & TEST_ADD) {
	97	/* test adding to the map */
	98	for (j = 0; j < rounds; j++) {
7663cdc8 SB	99	hashmap_init(&map, (hashmap_cmp_fn) test_entry_cmp,
7663cdc8 SB	100	NULL, 0);
6a364ced KB	101
	102	/* add entries */
	103	for (i = 0; i < TEST_SIZE; i++) {
	104	hashmap_entry_init(entries[i], hashes[i]);
	105	hashmap_add(&map, entries[i]);
	106	}
	107
	108	hashmap_free(&map, 0);
	109	}
	110	} else {
	111	/* test map lookups */
7663cdc8	112	hashmap_init(&map, (hashmap_cmp_fn) test_entry_cmp, NULL, 0);
6a364ced KB	113
	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]);
	119	}
	120
	121	for (j = 0; j < rounds; j++) {
	122	for (i = 0; i < TEST_SIZE; i++) {
ab73a9d1 KB	123	hashmap_get_from_hash(&map, hashes[i],
ab73a9d1 KB	124	entries[i]->key);
6a364ced KB	125	}
	126	}
	127
	128	hashmap_free(&map, 0);
	129	}
	130	}
	131
6a364ced KB	132	#define DELIM " \t\r\n"
	133
	134	/*
	135	* Read stdin line by line and print result of commands to stdout:
	136	*
	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
	143	*
	144	* perfhashmap method rounds -> test hashmap.[ch] performance
6a364ced	145	*/
3f2e2297	146	int cmd_main(int argc, const char **argv)
6a364ced KB	147	{
	148	char line[1024];
	149	struct hashmap map;
	150	int icase;
	151
	152	/* init hash map */
	153	icase = argc > 1 && !strcmp("ignorecase", argv[1]);
	154	hashmap_init(&map, (hashmap_cmp_fn) (icase ? test_entry_cmp_icase
7663cdc8	155	: test_entry_cmp), NULL, 0);
6a364ced KB	156
	157	/* process commands from stdin */
	158	while (fgets(line, sizeof(line), stdin)) {
	159	char cmd, p1 = NULL, *p2 = NULL;
	160	int l1 = 0, l2 = 0, hash = 0;
	161	struct test_entry *entry;
	162
	163	/* break line into command and up to two parameters */
	164	cmd = strtok(line, DELIM);
	165	/* ignore empty lines */
	166	if (!cmd \|\| *cmd == '#')
	167	continue;
	168
	169	p1 = strtok(NULL, DELIM);
	170	if (p1) {
	171	l1 = strlen(p1);
	172	hash = icase ? strihash(p1) : strhash(p1);
	173	p2 = strtok(NULL, DELIM);
	174	if (p2)
	175	l2 = strlen(p2);
	176	}
	177
	178	if (!strcmp("hash", cmd) && l1) {
	179
	180	/* print results of different hash functions */
	181	printf("%u %u %u %u\n", strhash(p1), memhash(p1, l1),
	182	strihash(p1), memihash(p1, l1));
	183
	184	} else if (!strcmp("add", cmd) && l1 && l2) {
	185
	186	/* create entry with key = p1, value = p2 */
	187	entry = alloc_test_entry(hash, p1, l1, p2, l2);
	188
	189	/* add to hashmap */
	190	hashmap_add(&map, entry);
	191
	192	} else if (!strcmp("put", cmd) && l1 && l2) {
	193
	194	/* create entry with key = p1, value = p2 */
	195	entry = alloc_test_entry(hash, p1, l1, p2, l2);
	196
	197	/* add / replace entry */
	198	entry = hashmap_put(&map, entry);
	199
	200	/* print and free replaced entry, if any */
	201	puts(entry ? get_value(entry) : "NULL");
	202	free(entry);
	203
	204	} else if (!strcmp("get", cmd) && l1) {
	205
6a364ced	206	/* lookup entry in hashmap */
ab73a9d1	207	entry = hashmap_get_from_hash(&map, hash, p1);
6a364ced KB	208
	209	/* print result */
	210	if (!entry)
	211	puts("NULL");
	212	while (entry) {
	213	puts(get_value(entry));
	214	entry = hashmap_get_next(&map, entry);
	215	}
	216
	217	} else if (!strcmp("remove", cmd) && l1) {
	218
	219	/* setup static key */
	220	struct hashmap_entry key;
	221	hashmap_entry_init(&key, hash);
	222
	223	/* remove entry from hashmap */
	224	entry = hashmap_remove(&map, &key, p1);
	225
	226	/* print result and free entry*/
	227	puts(entry ? get_value(entry) : "NULL");
	228	free(entry);
	229
	230	} else if (!strcmp("iterate", cmd)) {
	231
	232	struct hashmap_iter iter;
	233	hashmap_iter_init(&map, &iter);
	234	while ((entry = hashmap_iter_next(&iter)))
	235	printf("%s %s\n", entry->key, get_value(entry));
	236
	237	} else if (!strcmp("size", cmd)) {
	238
	239	/* print table sizes */
	240	printf("%u %u\n", map.tablesize, map.size);
	241
7b64d42d KB	242	} else if (!strcmp("intern", cmd) && l1) {
	243
	244	/* test that strintern works */
	245	const char *i1 = strintern(p1);
	246	const char *i2 = strintern(p1);
	247	if (strcmp(i1, p1))
	248	printf("strintern(%s) returns %s\n", p1, i1);
	249	else if (i1 == p1)
	250	printf("strintern(%s) returns input pointer\n", p1);
	251	else if (i1 != i2)
	252	printf("strintern(%s) != strintern(%s)", i1, i2);
	253	else
	254	printf("%s\n", i1);
	255
6a364ced KB	256	} else if (!strcmp("perfhashmap", cmd) && l1 && l2) {
	257
	258	perf_hashmap(atoi(p1), atoi(p2));
	259
6a364ced KB	260	} else {
	261
	262	printf("Unknown command %s\n", cmd);
	263
	264	}
	265	}
	266
	267	hashmap_free(&map, 1);
	268	return 0;
	269	}