hashtable.c 5.64 KB
Newer Older
1
/*
Vicent Marti committed
2
 * Copyright (C) 2009-2011 the libgit2 contributors
3
 *
Vicent Marti committed
4 5
 * This file is part of libgit2, distributed under the GNU GPL v2 with
 * a Linking Exception. For full terms see the included COPYING file.
6 7 8
 */

#include "common.h"
9 10
#include "repository.h"
#include "commit.h"
11

12
#define MAX_LOOPS 5
13
static const double max_load_factor = 0.65;
14

15 16 17 18 19 20 21 22
static int resize_to(git_hashtable *self, size_t new_size);
static int set_size(git_hashtable *self, size_t new_size);
static git_hashtable_node *node_with_hash(git_hashtable *self, const void *key, int hash_id);
static void node_swap_with(git_hashtable_node *self, git_hashtable_node *other);
static int node_insert(git_hashtable *self, git_hashtable_node *new_node);
static int insert_nodes(git_hashtable *self, git_hashtable_node *old_nodes, size_t old_size);

static int resize_to(git_hashtable *self, size_t new_size)
23
{
24 25 26 27
	git_hashtable_node *old_nodes = self->nodes;
	size_t old_size = self->size;

	self->is_resizing = 1;
28

29 30 31 32 33
	do {
		self->size = new_size;
		self->size_mask = new_size - 1;
		self->key_count = 0;
		self->nodes = git__calloc(1, sizeof(git_hashtable_node) * self->size);
34

35 36
		if (self->nodes == NULL)
			return GIT_ENOMEM;
37

38 39 40 41 42 43 44 45 46 47 48
		if (insert_nodes(self, old_nodes, old_size) == 0)
			self->is_resizing = 0;
		else {
			new_size *= 2;
			free(self->nodes);
		}
	} while(self->is_resizing);

	free(old_nodes);
	return GIT_SUCCESS;
}
49

50 51 52 53 54
static int set_size(git_hashtable *self, size_t new_size)
{
	self->nodes = realloc(self->nodes, new_size * sizeof(git_hashtable_node));
	if (self->nodes == NULL)
		return GIT_ENOMEM;
55

56 57 58
	if (new_size > self->size) {
		memset(&self->nodes[self->size], 0x0, (new_size - self->size) * sizeof(git_hashtable_node));
	}
59

60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78
	self->size = new_size;
	self->size_mask = new_size - 1;
	return GIT_SUCCESS;
}

static git_hashtable_node *node_with_hash(git_hashtable *self, const void *key, int hash_id)
{
	size_t pos = self->hash(key, hash_id) & self->size_mask;
	return git_hashtable_node_at(self->nodes, pos);
}

static void node_swap_with(git_hashtable_node *self, git_hashtable_node *other)
{
	git_hashtable_node tmp = *self;
	*self = *other;
	*other = tmp;
}

static int node_insert(git_hashtable *self, git_hashtable_node *new_node)
79
{
80 81
	int iteration, hash_id;

82
	for (iteration = 0; iteration < MAX_LOOPS; iteration++) {
83 84 85 86 87 88
		for (hash_id = 0; hash_id < GIT_HASHTABLE_HASHES; ++hash_id) {
			git_hashtable_node *node;
			node = node_with_hash(self, new_node->key, hash_id);
			node_swap_with(new_node, node);
			if(new_node->key == 0x0){
				self->key_count++;
89
				return GIT_SUCCESS;
90
			}
91 92 93
		}
	}

94
	if (self->is_resizing)
95
		return git__throw(GIT_EBUSY, "Failed to insert node. Hashtable is currently resizing");
96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112

	resize_to(self, self->size * 2);
	git_hashtable_insert(self, new_node->key, new_node->value);
	return GIT_SUCCESS;
}

static int insert_nodes(git_hashtable *self, git_hashtable_node *old_nodes, size_t old_size)
{
	size_t i;

	for (i = 0; i < old_size; ++i) {
		git_hashtable_node *node = git_hashtable_node_at(old_nodes, i);
		if (node->key && git_hashtable_insert(self, node->key, node->value) < GIT_SUCCESS)
			return GIT_ENOMEM;
	}

	return GIT_SUCCESS;
113 114
}

115
git_hashtable *git_hashtable_alloc(size_t min_size,
116 117
		git_hash_ptr hash,
		git_hash_keyeq_ptr key_eq)
118
{
119
	git_hashtable *table;
120

121
	assert(hash && key_eq);
122

123
	if ((table = git__malloc(sizeof(git_hashtable))) == NULL)
124
		return NULL;
125

126 127 128 129 130
	memset(table, 0x0, sizeof(git_hashtable));

	if (min_size < 8)
		min_size = 8;

131
	/* round up size to closest power of 2 */
132 133 134 135 136 137
	min_size--;
	min_size |= min_size >> 1;
	min_size |= min_size >> 2;
	min_size |= min_size >> 4;
	min_size |= min_size >> 8;
	min_size |= min_size >> 16;
138

139 140 141
	table->hash = hash;
	table->key_equal = key_eq;

142
	set_size(table, min_size + 1);
143

144
	return table;
145 146
}

147
void git_hashtable_clear(git_hashtable *self)
148
{
149
	assert(self);
150

151 152
	memset(self->nodes, 0x0, sizeof(git_hashtable_node) * self->size);
	self->key_count = 0;
153 154
}

155
void git_hashtable_free(git_hashtable *self)
156
{
157
	assert(self);
158

159 160
	free(self->nodes);
	free(self);
161 162 163
}


164
int git_hashtable_insert2(git_hashtable *self, const void *key, void *value, void **old_value)
165
{
166
	int hash_id;
167
	git_hashtable_node *node;
168

169 170
	assert(self && self->nodes);

171 172
	*old_value = NULL;

173 174
	for (hash_id = 0; hash_id < GIT_HASHTABLE_HASHES; ++hash_id) {
		node = node_with_hash(self, key, hash_id);
175

176 177 178 179 180 181
		if (!node->key) {
			node->key = key;
			node->value = value;
			self->key_count++;
			return GIT_SUCCESS;
		}
182

183
		if (key == node->key || self->key_equal(key, node->key) == 0) {
184 185
			*old_value = node->value;
			node->key = key;
186 187 188 189
			node->value = value;
			return GIT_SUCCESS;
		}
	}
190

191 192 193 194 195 196 197
	/* no space in table; must do cuckoo dance */
	{
		git_hashtable_node x;
		x.key = key;
		x.value = value;
		return node_insert(self, &x);
	}
198 199
}

200
void *git_hashtable_lookup(git_hashtable *self, const void *key)
201
{
202
	int hash_id;
203
	git_hashtable_node *node;
204

205 206
	assert(self && self->nodes);

207 208 209 210
	for (hash_id = 0; hash_id < GIT_HASHTABLE_HASHES; ++hash_id) {
		node = node_with_hash(self, key, hash_id);
		if (node->key && self->key_equal(key, node->key) == 0)
			return node->value;
211
	}
212

213
	return NULL;
214 215
}

216
int git_hashtable_remove(git_hashtable *self, const void *key)
217
{
218 219
	int hash_id;
	git_hashtable_node *node;
220

221 222
	assert(self && self->nodes);

223 224 225 226 227 228
	for (hash_id = 0; hash_id < GIT_HASHTABLE_HASHES; ++hash_id) {
		node = node_with_hash(self, key, hash_id);
		if (node->key && self->key_equal(key, node->key) == 0) {
			node->key = NULL;
			node->value = NULL;
			self->key_count--;
229 230 231 232
			return GIT_SUCCESS;
		}
	}

Vicent Marti committed
233
	return git__throw(GIT_ENOTFOUND, "Entry not found in hash table");
234 235
}

236 237 238 239 240 241 242 243
int git_hashtable_merge(git_hashtable *self, git_hashtable *other)
{
	if (resize_to(self, (self->size + other->size) * 2) < GIT_SUCCESS)
		return GIT_ENOMEM;

	return insert_nodes(self, other->nodes, other->key_count);
}