2 * This file is free software; you can redistribute it and/or modify
3 * it under the terms of the GNU General Public License, version 2,
4 * as published by the Free Software Foundation.
6 * In addition to the permissions in the GNU General Public License,
7 * the authors give you unlimited permission to link the compiled
8 * version of this file into combinations with other programs,
9 * and to distribute those combinations without any restriction
10 * coming from the use of this file. (The General Public License
11 * restrictions do apply in other respects; for example, they cover
12 * modification of the file, and distribution when not linked into
13 * a combined executable.)
15 * This file is distributed in the hope that it will be useful, but
16 * WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 * General Public License for more details.
20 * You should have received a copy of the GNU General Public License
21 * along with this program; see the file COPYING. If not, write to
22 * the Free Software Foundation, 51 Franklin Street, Fifth Floor,
23 * Boston, MA 02110-1301, USA.
27 #include "repository.h"
30 static const double resize_factor
= 1.75;
31 static const size_t minimum_size
= 8;
33 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 v
->_alloc_size
= minimum_size
;
39 v
->contents
= realloc(v
->contents
, v
->_alloc_size
* sizeof(void *));
40 if (v
->contents
== NULL
)
47 void git_vector_free(git_vector
*v
)
53 int git_vector_init(git_vector
*v
, unsigned int initial_size
, git_vector_cmp cmp
)
57 memset(v
, 0x0, sizeof(git_vector
));
59 if (initial_size
== 0)
60 initial_size
= minimum_size
;
62 v
->_alloc_size
= initial_size
;
68 v
->contents
= git__malloc(v
->_alloc_size
* sizeof(void *));
69 if (v
->contents
== NULL
)
75 int git_vector_insert(git_vector
*v
, void *element
)
79 if (v
->length
>= v
->_alloc_size
) {
80 if (resize_vector(v
) < 0)
84 v
->contents
[v
->length
++] = element
;
90 void git_vector_sort(git_vector
*v
)
94 if (v
->sorted
|| v
->_cmp
== NULL
)
97 qsort(v
->contents
, v
->length
, sizeof(void *), v
->_cmp
);
101 int git_vector_bsearch2(git_vector
*v
, git_vector_cmp key_lookup
, const void *key
)
105 assert(v
&& key
&& key_lookup
);
107 /* need comparison function to sort the vector */
109 return git__throw(GIT_ENOTFOUND
, "Can't sort vector. No comparison function set");
113 find
= bsearch(key
, v
->contents
, v
->length
, sizeof(void *), key_lookup
);
115 return (int)(find
- v
->contents
);
117 return git__throw(GIT_ENOTFOUND
, "Can't find element");
120 int git_vector_search2(git_vector
*v
, git_vector_cmp key_lookup
, const void *key
)
124 assert(v
&& key
&& key_lookup
);
126 for (i
= 0; i
< v
->length
; ++i
) {
127 if (key_lookup(key
, v
->contents
[i
]) == 0)
131 return git__throw(GIT_ENOTFOUND
, "Can't find element");
134 static int strict_comparison(const void *a
, const void *b
)
136 return (a
== b
) ? 0 : -1;
139 int git_vector_search(git_vector
*v
, const void *entry
)
141 return git_vector_search2(v
, v
->_cmp
? v
->_cmp
: strict_comparison
, entry
);
144 int git_vector_bsearch(git_vector
*v
, const void *key
)
146 return git_vector_bsearch2(v
, v
->_cmp
, key
);
149 int git_vector_remove(git_vector
*v
, unsigned int idx
)
155 if (idx
>= v
->length
|| v
->length
== 0)
156 return git__throw(GIT_ENOTFOUND
, "Can't remove element. Index out of bounds");
158 for (i
= idx
; i
< v
->length
- 1; ++i
)
159 v
->contents
[i
] = v
->contents
[i
+ 1];
165 void git_vector_clear(git_vector
*v
)