1
2
3
4
5
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
#include "clar_libgit2.h"
#include "hashtable.h"
#include "hash.h"
// Helpers
typedef struct _aux_object {
int __bulk;
git_oid id;
int visited;
} table_item;
static uint32_t hash_func(const void *key, int hash_id)
{
uint32_t r;
const git_oid *id = (const git_oid *)key;
memcpy(&r, id->id + (hash_id * sizeof(uint32_t)), sizeof(r));
return r;
}
static int hash_cmpkey(const void *a, const void *b)
{
return git_oid_cmp((const git_oid*)a, (const git_oid*)b);
}
void test_hash_table__new(void)
{
// create a new hashtable
git_hashtable *table = NULL;
table = git_hashtable_alloc(55, hash_func, hash_cmpkey);
cl_assert(table != NULL);
cl_assert(table->size_mask + 1 == 64);
git_hashtable_free(table);
}
void test_hash_table__fill(void)
{
// fill the hashtable with random entries
const int objects_n = 32;
int i;
table_item *objects;
git_hashtable *table = NULL;
table = git_hashtable_alloc(objects_n * 2, hash_func, hash_cmpkey);
cl_assert(table != NULL);
objects = (table_item *)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));
cl_git_pass(git_hashtable_insert(table, &(objects[i].id), &(objects[i])));
}
/* make sure all the inserted objects can be found */
for (i = 0; i < objects_n; ++i) {
git_oid id;
table_item *ob;
git_hash_buf(&id, &i, sizeof(int));
ob = (table_item *)git_hashtable_lookup(table, &id);
cl_assert(ob != NULL);
cl_assert(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));
cl_assert(git_hashtable_lookup(table, &id) == NULL);
}
git_hashtable_free(table);
git__free(objects);
}
void test_hash_table__resize(void)
{
// make sure the table resizes automatically
const int objects_n = 64;
int i;
unsigned int old_size;
table_item *objects;
git_hashtable *table = NULL;
table = git_hashtable_alloc(objects_n, hash_func, hash_cmpkey);
cl_assert(table != NULL);
objects = (table_item*)git__malloc(objects_n * sizeof(table_item));
memset(objects, 0x0, objects_n * sizeof(table_item));
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));
cl_git_pass(git_hashtable_insert(table, &(objects[i].id), &(objects[i])));
}
cl_assert(table->size_mask > old_size);
/* make sure all the inserted objects can be found */
for (i = 0; i < objects_n; ++i) {
git_oid id;
table_item *ob;
git_hash_buf(&id, &i, sizeof(int));
ob = (table_item *)git_hashtable_lookup(table, &id);
cl_assert(ob != NULL);
cl_assert(ob == &(objects[i]));
}
git_hashtable_free(table);
git__free(objects);
}
void test_hash_table__iterate(void)
{
// iterate through all the contents of the table
const int objects_n = 32;
int i;
table_item *objects, *ob;
git_hashtable *table = NULL;
table = git_hashtable_alloc(objects_n * 2, hash_func, hash_cmpkey);
cl_assert(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));
cl_git_pass(git_hashtable_insert(table, &(objects[i].id), &(objects[i])));
}
GIT_HASHTABLE_FOREACH_VALUE(table, ob, ob->visited = 1);
/* make sure all nodes have been visited */
for (i = 0; i < objects_n; ++i)
{
cl_assert(objects[i].visited);
}
git_hashtable_free(table);
git__free(objects);
}
|
