t0701-table.c 2.77 KB
Newer Older
1 2 3 4
#include "test_lib.h"
#include "test_helpers.h"
#include "commit.h"
#include "hash.h"
5
#include "hashtable.h"
6

7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
typedef struct table_item
{
	int __bulk;
	git_oid id;
} table_item;


uint32_t hash_func(const void *key)
{
	uint32_t r;
	git_oid *id;

	id = (git_oid *)key;
	memcpy(&r, id->id, sizeof(r));
	return r;
}

int hash_haskey(void *item, const void *key)
{
	table_item *obj;
	git_oid *oid;

	obj = (table_item *)item;
	oid = (git_oid *)key;

	return (git_oid_cmp(oid, &obj->id) == 0);
}
34 35 36

BEGIN_TEST(table_create)

37
	git_hashtable *table = NULL;
38

39
	table = git_hashtable_alloc(55, hash_func, hash_haskey);
40 41 42
	must_be_true(table != NULL);
	must_be_true(table->size_mask + 1 == 64);

43
	git_hashtable_free(table);
44 45 46 47 48 49 50 51

END_TEST

BEGIN_TEST(table_populate)

	const int objects_n = 32;
	int i;

52 53 54 55
	table_item *objects;
	git_hashtable *table = NULL;

	table = git_hashtable_alloc(objects_n * 2, hash_func, hash_haskey);
56 57
	must_be_true(table != NULL);

58 59
	objects = git__malloc(objects_n * sizeof(table_item));
	memset(objects, 0x0, objects_n * sizeof(table_item));
60 61 62 63

	/* populate the hash table */
	for (i = 0; i < objects_n; ++i) {
		git_hash_buf(&(objects[i].id), &i, sizeof(int));
64
		must_pass(git_hashtable_insert(table, &(objects[i].id), &(objects[i])));
65 66 67 68 69
	}

	/* make sure all the inserted objects can be found */
	for (i = 0; i < objects_n; ++i) {
		git_oid id;
70
		table_item *ob;
71 72

		git_hash_buf(&id, &i, sizeof(int));
73
		ob = (table_item *)git_hashtable_lookup(table, &id);
74 75 76 77 78 79 80 81 82 83 84 85

		must_be_true(ob != NULL);
		must_be_true(ob == &(objects[i]));
	}

	/* make sure we cannot find inexisting objects */
	for (i = 0; i < 50; ++i) {
		int hash_id;
		git_oid id;

		hash_id = (rand() % 50000) + objects_n;
		git_hash_buf(&id, &hash_id, sizeof(int));
86
		must_be_true(git_hashtable_lookup(table, &id) == NULL);
87 88
	}

89
	git_hashtable_free(table);
90 91 92 93 94 95 96 97 98 99
	free(objects);

END_TEST


BEGIN_TEST(table_resize)

	const int objects_n = 64;
	int i;
	unsigned int old_size;
100 101
	table_item *objects;
	git_hashtable *table = NULL;
102

103
	table = git_hashtable_alloc(objects_n, hash_func, hash_haskey);
104 105
	must_be_true(table != NULL);

106 107
	objects = git__malloc(objects_n * sizeof(table_item));
	memset(objects, 0x0, objects_n * sizeof(table_item));
108 109 110 111 112 113

	old_size = table->size_mask + 1;

	/* populate the hash table -- should be automatically resized */
	for (i = 0; i < objects_n; ++i) {
		git_hash_buf(&(objects[i].id), &i, sizeof(int));
114
		must_pass(git_hashtable_insert(table, &(objects[i].id), &(objects[i])));
115 116 117 118 119 120 121
	}

	must_be_true(table->size_mask > old_size);

	/* make sure all the inserted objects can be found */
	for (i = 0; i < objects_n; ++i) {
		git_oid id;
122
		table_item *ob;
123 124

		git_hash_buf(&id, &i, sizeof(int));
125
		ob = (table_item *)git_hashtable_lookup(table, &id);
126 127 128 129 130

		must_be_true(ob != NULL);
		must_be_true(ob == &(objects[i]));
	}

131
	git_hashtable_free(table);
132 133 134
	free(objects);

END_TEST