t07-hashtable.c 4.88 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
/*
 * This file is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License, version 2,
 * as published by the Free Software Foundation.
 *
 * In addition to the permissions in the GNU General Public License,
 * the authors give you unlimited permission to link the compiled
 * version of this file into combinations with other programs,
 * and to distribute those combinations without any restriction
 * coming from the use of this file.  (The General Public License
 * restrictions do apply in other respects; for example, they cover
 * modification of the file, and distribution when not linked into
 * a combined executable.)
 *
 * This file is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; see the file COPYING.  If not, write to
 * the Free Software Foundation, 51 Franklin Street, Fifth Floor,
 * Boston, MA 02110-1301, USA.
 */
25 26
#include "test_lib.h"
#include "test_helpers.h"
27

28
#include "hashtable.h"
29
#include "hash.h"
30

31
typedef struct _aux_object {
32 33
	int __bulk;
	git_oid id;
34
	int visited;
35 36
} table_item;

37
uint32_t hash_func(const void *key, int hash_id)
38 39 40 41 42
{
	uint32_t r;
	git_oid *id;

	id = (git_oid *)key;
43
	memcpy(&r, id->id + (hash_id * sizeof(uint32_t)), sizeof(r));
44 45 46
	return r;
}

47
int hash_cmpkey(const void *a, const void *b)
48
{
49
	return git_oid_cmp(a, b);
50
}
51

52
BEGIN_TEST(table0, "create a new hashtable")
53

54
	git_hashtable *table = NULL;
55

56
	table = git_hashtable_alloc(55, hash_func, hash_cmpkey);
57 58 59
	must_be_true(table != NULL);
	must_be_true(table->size_mask + 1 == 64);

60
	git_hashtable_free(table);
61 62 63

END_TEST

64
BEGIN_TEST(table1, "fill the hashtable with random entries")
65 66 67 68

	const int objects_n = 32;
	int i;

69 70 71
	table_item *objects;
	git_hashtable *table = NULL;

72
	table = git_hashtable_alloc(objects_n * 2, hash_func, hash_cmpkey);
73 74
	must_be_true(table != NULL);

75 76
	objects = git__malloc(objects_n * sizeof(table_item));
	memset(objects, 0x0, objects_n * sizeof(table_item));
77 78 79 80

	/* populate the hash table */
	for (i = 0; i < objects_n; ++i) {
		git_hash_buf(&(objects[i].id), &i, sizeof(int));
81
		must_pass(git_hashtable_insert(table, &(objects[i].id), &(objects[i])));
82 83 84 85 86
	}

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

		git_hash_buf(&id, &i, sizeof(int));
90
		ob = (table_item *)git_hashtable_lookup(table, &id);
91 92 93 94 95 96 97 98 99 100 101 102

		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));
103
		must_be_true(git_hashtable_lookup(table, &id) == NULL);
104 105
	}

106
	git_hashtable_free(table);
107 108 109 110 111
	free(objects);

END_TEST


112
BEGIN_TEST(table2, "make sure the table resizes automatically")
113 114 115 116

	const int objects_n = 64;
	int i;
	unsigned int old_size;
117 118
	table_item *objects;
	git_hashtable *table = NULL;
119

120
	table = git_hashtable_alloc(objects_n, hash_func, hash_cmpkey);
121 122
	must_be_true(table != NULL);

123 124
	objects = git__malloc(objects_n * sizeof(table_item));
	memset(objects, 0x0, objects_n * sizeof(table_item));
125 126 127 128 129 130

	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));
131
		must_pass(git_hashtable_insert(table, &(objects[i].id), &(objects[i])));
132 133 134 135 136 137 138
	}

	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;
139
		table_item *ob;
140 141

		git_hash_buf(&id, &i, sizeof(int));
142
		ob = (table_item *)git_hashtable_lookup(table, &id);
143 144 145 146 147

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

148
	git_hashtable_free(table);
149 150 151
	free(objects);

END_TEST
152

153
BEGIN_TEST(tableit0, "iterate through all the contents of the table")
154 155 156 157

	const int objects_n = 32;
	int i;
	table_item *objects, *ob;
158
	const void *GIT_UNUSED(_unused);
159 160 161

	git_hashtable *table = NULL;

162
	table = git_hashtable_alloc(objects_n * 2, hash_func, hash_cmpkey);
163 164 165 166 167 168 169 170 171 172 173
	must_be_true(table != NULL);

	objects = git__malloc(objects_n * sizeof(table_item));
	memset(objects, 0x0, objects_n * sizeof(table_item));

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

174
	GIT_HASHTABLE_FOREACH(table, _unused, ob,
175
		ob->visited = 1;
176
	);
177 178 179 180 181 182 183 184 185 186

	/* make sure all nodes have been visited */
	for (i = 0; i < objects_n; ++i)
		must_be_true(objects[i].visited);

	git_hashtable_free(table);
	free(objects);
END_TEST


187 188 189 190 191 192
BEGIN_SUITE(hashtable)
	ADD_TEST(table0);
	ADD_TEST(table1);
	ADD_TEST(table2);
	ADD_TEST(tableit0);
END_SUITE
193