vector.c 6.55 KB
Newer Older
1
/*
Edward Thomson committed
2
 * Copyright (C) the libgit2 contributors. All rights reserved.
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 9 10
 */

#include "common.h"
#include "vector.h"

11 12
/* In elements, not bytes */
#define MIN_ALLOCSIZE	8
13

14
GIT_INLINE(size_t) compute_new_size(git_vector *v)
15
{
16 17 18 19 20 21
	size_t new_size = v->_alloc_size;

	/* Use a resize factor of 1.5, which is quick to compute using integer
	 * instructions and less than the golden ratio (1.618...) */
	if (new_size < MIN_ALLOCSIZE)
		new_size = MIN_ALLOCSIZE;
Philip Kelley committed
22 23
	else if (new_size <= (SIZE_MAX / 3) * 2)
		new_size += new_size / 2;
24 25 26 27 28
	else
		new_size = SIZE_MAX;

	return new_size;
}
29

30 31 32 33
GIT_INLINE(int) resize_vector(git_vector *v, size_t new_size)
{
	void *new_contents;

34
	new_contents = git__reallocarray(v->contents, new_size, sizeof(void *));
35 36 37 38
	GITERR_CHECK_ALLOC(new_contents);

	v->_alloc_size = new_size;
	v->contents = new_contents;
39

40
	return 0;
41 42
}

43
int git_vector_dup(git_vector *v, const git_vector *src, git_vector_cmp cmp)
44
{
45 46
	size_t bytes;

47 48
	assert(v && src);

49
	GITERR_CHECK_ALLOC_MULTIPLY(&bytes, src->length, sizeof(void *));
50

51
	v->_alloc_size = src->length;
52
	v->_cmp = cmp ? cmp : src->_cmp;
53
	v->length = src->length;
54 55 56
	v->flags  = src->flags;
	if (cmp != src->_cmp)
		git_vector_set_sorted(v, 0);
57
	v->contents = git__malloc(bytes);
58 59
	GITERR_CHECK_ALLOC(v->contents);

60
	memcpy(v->contents, src->contents, bytes);
61 62 63 64

	return 0;
}

65 66 67
void git_vector_free(git_vector *v)
{
	assert(v);
68

69
	git__free(v->contents);
70 71 72 73
	v->contents = NULL;

	v->length = 0;
	v->_alloc_size = 0;
74 75
}

76
void git_vector_free_deep(git_vector *v)
Russell Belfer committed
77 78 79 80 81 82 83 84 85 86 87 88 89
{
	size_t i;

	assert(v);

	for (i = 0; i < v->length; ++i) {
		git__free(v->contents[i]);
		v->contents[i] = NULL;
	}

	git_vector_free(v);
}

90
int git_vector_init(git_vector *v, size_t initial_size, git_vector_cmp cmp)
91 92 93
{
	assert(v);

94
	v->_alloc_size = 0;
95 96
	v->_cmp = cmp;
	v->length = 0;
97
	v->flags = GIT_VECTOR_SORTED;
98
	v->contents = NULL;
99

100
	return resize_vector(v, max(initial_size, MIN_ALLOCSIZE));
101 102
}

103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118
void **git_vector_detach(size_t *size, size_t *asize, git_vector *v)
{
	void **data = v->contents;

	if (size)
		*size = v->length;
	if (asize)
		*asize = v->_alloc_size;

	v->_alloc_size = 0;
	v->length   = 0;
	v->contents = NULL;

	return data;
}

119 120 121 122
int git_vector_insert(git_vector *v, void *element)
{
	assert(v);

123
	if (v->length >= v->_alloc_size &&
124
		resize_vector(v, compute_new_size(v)) < 0)
125
		return -1;
126 127

	v->contents[v->length++] = element;
128 129

	git_vector_set_sorted(v, v->length <= 1);
130

131
	return 0;
132 133
}

134 135
int git_vector_insert_sorted(
	git_vector *v, void *element, int (*on_dup)(void **old, void *new))
136
{
137
	int result;
138 139 140 141
	size_t pos;

	assert(v && v->_cmp);

142
	if (!git_vector_is_sorted(v))
143 144
		git_vector_sort(v);

145
	if (v->length >= v->_alloc_size &&
146
		resize_vector(v, compute_new_size(v)) < 0)
147
		return -1;
148

149 150
	/* If we find the element and have a duplicate handler callback,
	 * invoke it.  If it returns non-zero, then cancel insert, otherwise
151 152
	 * proceed with normal insert.
	 */
153 154
	if (!git__bsearch(v->contents, v->length, element, v->_cmp, &pos) &&
		on_dup && (result = on_dup(&v->contents[pos], element)) < 0)
155
		return result;
156 157

	/* shift elements to the right */
158
	if (pos < v->length)
159 160 161 162 163
		memmove(v->contents + pos + 1, v->contents + pos,
		        (v->length - pos) * sizeof(void *));

	v->contents[pos] = element;
	v->length++;
164

165
	return 0;
166 167
}

168 169 170 171
void git_vector_sort(git_vector *v)
{
	assert(v);

172
	if (git_vector_is_sorted(v) || !v->_cmp)
173 174
		return;

175 176
	if (v->length > 1)
		git__tsort(v->contents, v->length, v->_cmp);
177
	git_vector_set_sorted(v, 1);
178 179
}

180
int git_vector_bsearch2(
181
	size_t *at_pos,
182 183 184
	git_vector *v,
	git_vector_cmp key_lookup,
	const void *key)
185
{
186 187
	assert(v && key && key_lookup);

188
	/* need comparison function to sort the vector */
189 190
	if (!v->_cmp)
		return -1;
191

192 193
	git_vector_sort(v);

194
	return git__bsearch(v->contents, v->length, key, key_lookup, at_pos);
195 196
}

197
int git_vector_search2(
198
	size_t *at_pos, const git_vector *v, git_vector_cmp key_lookup, const void *key)
199
{
200
	size_t i;
201 202 203 204

	assert(v && key && key_lookup);

	for (i = 0; i < v->length; ++i) {
205 206 207 208 209 210
		if (key_lookup(key, v->contents[i]) == 0) {
			if (at_pos)
				*at_pos = i;

			return 0;
		}
211 212
	}

213
	return GIT_ENOTFOUND;
214 215
}

216
static int strict_comparison(const void *a, const void *b)
217
{
Vicent Marti committed
218
	return (a == b) ? 0 : -1;
219
}
220

221
int git_vector_search(size_t *at_pos, const git_vector *v, const void *entry)
222
{
223
	return git_vector_search2(at_pos, v, v->_cmp ? v->_cmp : strict_comparison, entry);
224 225
}

226
int git_vector_remove(git_vector *v, size_t idx)
227
{
228
	size_t shift_count;
229 230 231

	assert(v);

232
	if (idx >= v->length)
233
		return GIT_ENOTFOUND;
234

235 236 237 238 239
	shift_count = v->length - idx - 1;

	if (shift_count)
		memmove(&v->contents[idx], &v->contents[idx + 1],
			shift_count * sizeof(void *));
240 241

	v->length--;
242
	return 0;
243 244
}

245
void git_vector_pop(git_vector *v)
246
{
247 248
	if (v->length > 0)
		v->length--;
249 250
}

251
void git_vector_uniq(git_vector *v, void  (*git_free_cb)(void *))
252 253
{
	git_vector_cmp cmp;
254
	size_t i, j;
255 256 257 258 259 260 261 262

	if (v->length <= 1)
		return;

	git_vector_sort(v);
	cmp = v->_cmp ? v->_cmp : strict_comparison;

	for (i = 0, j = 1 ; j < v->length; ++j)
263 264 265 266
		if (!cmp(v->contents[i], v->contents[j])) {
			if (git_free_cb)
				git_free_cb(v->contents[i]);

267
			v->contents[i] = v->contents[j];
268
		} else
269 270 271 272 273
			v->contents[++i] = v->contents[j];

	v->length -= j - i - 1;
}

274
void git_vector_remove_matching(
275 276 277
	git_vector *v,
	int (*match)(const git_vector *v, size_t idx, void *payload),
	void *payload)
Edward Thomson committed
278
{
279
	size_t i, j;
Edward Thomson committed
280 281 282 283

	for (i = 0, j = 0; j < v->length; ++j) {
		v->contents[i] = v->contents[j];

284
		if (!match(v, i, payload))
Edward Thomson committed
285 286 287 288 289 290
			i++;
	}

	v->length = i;
}

291 292 293 294
void git_vector_clear(git_vector *v)
{
	assert(v);
	v->length = 0;
295
	git_vector_set_sorted(v, 1);
296 297
}

298 299 300 301
void git_vector_swap(git_vector *a, git_vector *b)
{
	git_vector t;

302
	assert(a && b);
303

304 305 306 307 308
	if (a != b) {
		memcpy(&t, a, sizeof(t));
		memcpy(a, b, sizeof(t));
		memcpy(b, &t, sizeof(t));
	}
309
}
310 311 312

int git_vector_resize_to(git_vector *v, size_t new_length)
{
313 314 315
	if (new_length > v->_alloc_size &&
		resize_vector(v, new_length) < 0)
		return -1;
316

317 318 319
	if (new_length > v->length)
		memset(&v->contents[v->length], 0,
			sizeof(void *) * (new_length - v->length));
320 321 322 323 324 325 326 327

	v->length = new_length;

	return 0;
}

int git_vector_set(void **old, git_vector *v, size_t position, void *value)
{
328 329 330 331
	if (position + 1 > v->length) {
		if (git_vector_resize_to(v, position + 1) < 0)
			return -1;
	}
332 333 334 335 336 337 338 339

	if (old != NULL)
		*old = v->contents[position];

	v->contents[position] = value;

	return 0;
}
340 341 342 343 344 345 346 347 348 349 350 351 352 353 354

int git_vector_verify_sorted(const git_vector *v)
{
	size_t i;

	if (!git_vector_is_sorted(v))
		return -1;

	for (i = 1; i < v->length; ++i) {
		if (v->_cmp(v->contents[i - 1], v->contents[i]) > 0)
			return -1;
	}

	return 0;
}