vector.c 8.15 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
 */

#include "vector.h"
9

10
#include "integer.h"
11

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

15
GIT_INLINE(size_t) compute_new_size(git_vector *v)
16
{
17 18 19 20 21 22
	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
23 24
	else if (new_size <= (SIZE_MAX / 3) * 2)
		new_size += new_size / 2;
25 26 27 28 29
	else
		new_size = SIZE_MAX;

	return new_size;
}
30

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

35 36 37
	if (new_size == 0)
		return 0;

38
	new_contents = git__reallocarray(v->contents, new_size, sizeof(void *));
39
	GIT_ERROR_CHECK_ALLOC(new_contents);
40 41 42

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

44
	return 0;
45 46
}

47 48 49 50 51 52 53
int git_vector_size_hint(git_vector *v, size_t size_hint)
{
	if (v->_alloc_size >= size_hint)
		return 0;
	return resize_vector(v, size_hint);
}

54
int git_vector_dup(git_vector *v, const git_vector *src, git_vector_cmp cmp)
55
{
56 57
	GIT_ASSERT_ARG(v);
	GIT_ASSERT_ARG(src);
58

59 60
	v->_alloc_size = 0;
	v->contents = NULL;
61
	v->_cmp = cmp ? cmp : src->_cmp;
62
	v->length = src->length;
63 64 65
	v->flags  = src->flags;
	if (cmp != src->_cmp)
		git_vector_set_sorted(v, 0);
66

67 68
	if (src->length) {
		size_t bytes;
69
		GIT_ERROR_CHECK_ALLOC_MULTIPLY(&bytes, src->length, sizeof(void *));
70
		v->contents = git__malloc(bytes);
71
		GIT_ERROR_CHECK_ALLOC(v->contents);
72 73 74
		v->_alloc_size = src->length;
		memcpy(v->contents, src->contents, bytes);
	}
75 76 77 78

	return 0;
}

79 80
void git_vector_free(git_vector *v)
{
81 82
	if (!v)
		return;
83

84
	git__free(v->contents);
85 86 87 88
	v->contents = NULL;

	v->length = 0;
	v->_alloc_size = 0;
89 90
}

91
void git_vector_free_deep(git_vector *v)
Russell Belfer committed
92 93 94
{
	size_t i;

95 96
	if (!v)
		return;
Russell Belfer committed
97 98 99 100 101 102 103 104 105

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

	git_vector_free(v);
}

106
int git_vector_init(git_vector *v, size_t initial_size, git_vector_cmp cmp)
107
{
108
	GIT_ASSERT_ARG(v);
109

110
	v->_alloc_size = 0;
111 112
	v->_cmp = cmp;
	v->length = 0;
113
	v->flags = GIT_VECTOR_SORTED;
114
	v->contents = NULL;
115

116
	return resize_vector(v, max(initial_size, MIN_ALLOCSIZE));
117 118
}

119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134
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;
}

135 136
int git_vector_insert(git_vector *v, void *element)
{
137
	GIT_ASSERT_ARG(v);
138

139
	if (v->length >= v->_alloc_size &&
140
		resize_vector(v, compute_new_size(v)) < 0)
141
		return -1;
142 143

	v->contents[v->length++] = element;
144 145

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

147
	return 0;
148 149
}

150 151
int git_vector_insert_sorted(
	git_vector *v, void *element, int (*on_dup)(void **old, void *new))
152
{
153
	int result;
154 155
	size_t pos;

156 157
	GIT_ASSERT_ARG(v);
	GIT_ASSERT(v->_cmp);
158

159
	if (!git_vector_is_sorted(v))
160 161
		git_vector_sort(v);

162
	if (v->length >= v->_alloc_size &&
163
		resize_vector(v, compute_new_size(v)) < 0)
164
		return -1;
165

166 167
	/* If we find the element and have a duplicate handler callback,
	 * invoke it.  If it returns non-zero, then cancel insert, otherwise
168 169
	 * proceed with normal insert.
	 */
170 171
	if (!git__bsearch(v->contents, v->length, element, v->_cmp, &pos) &&
		on_dup && (result = on_dup(&v->contents[pos], element)) < 0)
172
		return result;
173 174

	/* shift elements to the right */
175
	if (pos < v->length)
176 177 178 179 180
		memmove(v->contents + pos + 1, v->contents + pos,
		        (v->length - pos) * sizeof(void *));

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

182
	return 0;
183 184
}

185 186
void git_vector_sort(git_vector *v)
{
187
	if (git_vector_is_sorted(v) || !v->_cmp)
188 189
		return;

190 191
	if (v->length > 1)
		git__tsort(v->contents, v->length, v->_cmp);
192
	git_vector_set_sorted(v, 1);
193 194
}

195
int git_vector_bsearch2(
196
	size_t *at_pos,
197 198 199
	git_vector *v,
	git_vector_cmp key_lookup,
	const void *key)
200
{
201 202 203
	GIT_ASSERT_ARG(v);
	GIT_ASSERT_ARG(key);
	GIT_ASSERT(key_lookup);
204

205
	/* need comparison function to sort the vector */
206 207
	if (!v->_cmp)
		return -1;
208

209 210
	git_vector_sort(v);

211
	return git__bsearch(v->contents, v->length, key, key_lookup, at_pos);
212 213
}

214
int git_vector_search2(
215
	size_t *at_pos, const git_vector *v, git_vector_cmp key_lookup, const void *key)
216
{
217
	size_t i;
218

219 220 221
	GIT_ASSERT_ARG(v);
	GIT_ASSERT_ARG(key);
	GIT_ASSERT(key_lookup);
222 223

	for (i = 0; i < v->length; ++i) {
224 225 226 227 228 229
		if (key_lookup(key, v->contents[i]) == 0) {
			if (at_pos)
				*at_pos = i;

			return 0;
		}
230 231
	}

232
	return GIT_ENOTFOUND;
233 234
}

235
static int strict_comparison(const void *a, const void *b)
236
{
Vicent Marti committed
237
	return (a == b) ? 0 : -1;
238
}
239

240
int git_vector_search(size_t *at_pos, const git_vector *v, const void *entry)
241
{
242
	return git_vector_search2(at_pos, v, v->_cmp ? v->_cmp : strict_comparison, entry);
243 244
}

245
int git_vector_remove(git_vector *v, size_t idx)
246
{
247
	size_t shift_count;
248

249
	GIT_ASSERT_ARG(v);
250

251
	if (idx >= v->length)
252
		return GIT_ENOTFOUND;
253

254 255 256 257 258
	shift_count = v->length - idx - 1;

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

	v->length--;
261
	return 0;
262 263
}

264
void git_vector_pop(git_vector *v)
265
{
266 267
	if (v->length > 0)
		v->length--;
268 269
}

270
void git_vector_uniq(git_vector *v, void  (*git_free_cb)(void *))
271 272
{
	git_vector_cmp cmp;
273
	size_t i, j;
274 275 276 277 278 279 280 281

	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)
282 283 284 285
		if (!cmp(v->contents[i], v->contents[j])) {
			if (git_free_cb)
				git_free_cb(v->contents[i]);

286
			v->contents[i] = v->contents[j];
287
		} else
288 289 290 291 292
			v->contents[++i] = v->contents[j];

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

293
void git_vector_remove_matching(
294 295 296
	git_vector *v,
	int (*match)(const git_vector *v, size_t idx, void *payload),
	void *payload)
Edward Thomson committed
297
{
298
	size_t i, j;
Edward Thomson committed
299 300 301 302

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

303
		if (!match(v, i, payload))
Edward Thomson committed
304 305 306 307 308 309
			i++;
	}

	v->length = i;
}

310 311 312
void git_vector_clear(git_vector *v)
{
	v->length = 0;
313
	git_vector_set_sorted(v, 1);
314 315
}

316 317 318 319
void git_vector_swap(git_vector *a, git_vector *b)
{
	git_vector t;

320 321 322 323 324
	if (a != b) {
		memcpy(&t, a, sizeof(t));
		memcpy(a, b, sizeof(t));
		memcpy(b, &t, sizeof(t));
	}
325
}
326 327 328

int git_vector_resize_to(git_vector *v, size_t new_length)
{
329 330 331
	if (new_length > v->_alloc_size &&
		resize_vector(v, new_length) < 0)
		return -1;
332

333 334 335
	if (new_length > v->length)
		memset(&v->contents[v->length], 0,
			sizeof(void *) * (new_length - v->length));
336 337 338 339 340 341

	v->length = new_length;

	return 0;
}

342
int git_vector_insert_null(git_vector *v, size_t idx, size_t insert_len)
343
{
344
	size_t new_length;
345

346 347
	GIT_ASSERT_ARG(insert_len > 0);
	GIT_ASSERT_ARG(idx <= v->length);
348

349
	GIT_ERROR_CHECK_ALLOC_ADD(&new_length, v->length, insert_len);
350 351

	if (new_length > v->_alloc_size && resize_vector(v, new_length) < 0)
352 353
		return -1;

354
	memmove(&v->contents[idx + insert_len], &v->contents[idx],
355
		sizeof(void *) * (v->length - idx));
356
	memset(&v->contents[idx], 0, sizeof(void *) * insert_len);
357 358 359 360 361

	v->length = new_length;
	return 0;
}

362
int git_vector_remove_range(git_vector *v, size_t idx, size_t remove_len)
363
{
364
	size_t new_length = v->length - remove_len;
365
	size_t end_idx = 0;
366 367

	GIT_ASSERT_ARG(remove_len > 0);
368

369
	if (git__add_sizet_overflow(&end_idx, idx, remove_len))
370
		GIT_ASSERT(0);
371

372
	GIT_ASSERT(end_idx <= v->length);
373

374
	if (end_idx < v->length)
375
		memmove(&v->contents[idx], &v->contents[end_idx],
376
			sizeof(void *) * (v->length - end_idx));
377

378
	memset(&v->contents[new_length], 0, sizeof(void *) * remove_len);
379 380 381 382 383

	v->length = new_length;
	return 0;
}

384 385
int git_vector_set(void **old, git_vector *v, size_t position, void *value)
{
386 387 388 389
	if (position + 1 > v->length) {
		if (git_vector_resize_to(v, position + 1) < 0)
			return -1;
	}
390 391 392 393 394 395 396 397

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

	v->contents[position] = value;

	return 0;
}
398 399 400 401 402 403 404 405 406 407 408 409 410 411 412

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;
}
413 414 415 416 417

void git_vector_reverse(git_vector *v)
{
	size_t a, b;

418 419 420
	if (v->length == 0)
		return;

421 422 423 424 425 426 427 428 429 430 431
	a = 0;
	b = v->length - 1;

	while (a < b) {
		void *tmp = v->contents[a];
		v->contents[a] = v->contents[b];
		v->contents[b] = tmp;
		a++;
		b--;
	}
}