vector.c 3.04 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 25 26 27 28 29 30
/*
 * 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.
 */

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

static const double resize_factor = 1.75;
Vicent Marti committed
31
static const size_t minimum_size = 8;
32 33 34

static int resize_vector(git_vector *v)
{
35
	v->_alloc_size = ((unsigned int)(v->_alloc_size * resize_factor)) + 1;
36
	if (v->_alloc_size < minimum_size)
37 38
		v->_alloc_size = minimum_size;

39 40
	v->contents = realloc(v->contents, v->_alloc_size * sizeof(void *));
	if (v->contents == NULL)
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
		return GIT_ENOMEM;

	return GIT_SUCCESS;
}


void git_vector_free(git_vector *v)
{
	assert(v);
	free(v->contents);
}

int git_vector_init(git_vector *v, unsigned int initial_size, git_vector_cmp cmp, git_vector_srch srch)
{
	assert(v);

	memset(v, 0x0, sizeof(git_vector));

	if (initial_size == 0)
		initial_size = minimum_size;

	v->_alloc_size = initial_size;
	v->_cmp = cmp;
	v->_srch = srch;
	
	v->length = 0;

	v->contents = git__malloc(v->_alloc_size * sizeof(void *));
	if (v->contents == NULL)
		return GIT_ENOMEM;

	return GIT_SUCCESS;
}

int git_vector_insert(git_vector *v, void *element)
{
	assert(v);

	if (v->length >= v->_alloc_size) {
		if (resize_vector(v) < 0)
			return GIT_ENOMEM;
	}

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

	return GIT_SUCCESS;
}

void git_vector_sort(git_vector *v)
{
	assert(v);

	if (v->_cmp != NULL)
		qsort(v->contents, v->length, sizeof(void *), v->_cmp);
}

int git_vector_search(git_vector *v, const void *key)
{
	void **find;

	if (v->_srch == NULL)
		return GIT_ENOTFOUND;

	find = bsearch(key, v->contents, v->length, sizeof(void *), v->_srch);
	if (find == NULL)
		return GIT_ENOTFOUND;

	return (int)(find - v->contents);
}

int git_vector_remove(git_vector *v, unsigned int idx)
{
	unsigned int i;

	assert(v);

	if (idx >= v->length || v->length == 0)
		return GIT_ENOTFOUND;

120
	for (i = idx; i < v->length - 1; ++i)
121 122 123 124 125 126 127 128 129 130 131 132 133
		v->contents[i] = v->contents[i + 1];

	v->length--;
	return GIT_SUCCESS;
}

void git_vector_clear(git_vector *v)
{
	assert(v);
	v->length = 0;
}