]>
Commit | Line | Data |
---|---|---|
c4034e63 VM |
1 | /* |
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. | |
5 | * | |
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.) | |
14 | * | |
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. | |
19 | * | |
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. | |
24 | */ | |
25 | ||
26 | #include "common.h" | |
27 | #include "repository.h" | |
28 | #include "vector.h" | |
29 | ||
30 | static const double resize_factor = 1.75; | |
da7c3c71 | 31 | static const size_t minimum_size = 8; |
c4034e63 VM |
32 | |
33 | static int resize_vector(git_vector *v) | |
34 | { | |
a17777d1 | 35 | v->_alloc_size = ((unsigned int)(v->_alloc_size * resize_factor)) + 1; |
86194b24 | 36 | if (v->_alloc_size < minimum_size) |
c4034e63 VM |
37 | v->_alloc_size = minimum_size; |
38 | ||
86194b24 VM |
39 | v->contents = realloc(v->contents, v->_alloc_size * sizeof(void *)); |
40 | if (v->contents == NULL) | |
c4034e63 VM |
41 | return GIT_ENOMEM; |
42 | ||
c4034e63 VM |
43 | return GIT_SUCCESS; |
44 | } | |
45 | ||
46 | ||
47 | void git_vector_free(git_vector *v) | |
48 | { | |
49 | assert(v); | |
50 | free(v->contents); | |
51 | } | |
52 | ||
86d7e1ca | 53 | int git_vector_init(git_vector *v, unsigned int initial_size, git_vector_cmp cmp) |
c4034e63 VM |
54 | { |
55 | assert(v); | |
56 | ||
57 | memset(v, 0x0, sizeof(git_vector)); | |
58 | ||
59 | if (initial_size == 0) | |
60 | initial_size = minimum_size; | |
61 | ||
62 | v->_alloc_size = initial_size; | |
63 | v->_cmp = cmp; | |
932d1baf | 64 | |
c4034e63 | 65 | v->length = 0; |
86d7e1ca | 66 | v->sorted = 1; |
c4034e63 VM |
67 | |
68 | v->contents = git__malloc(v->_alloc_size * sizeof(void *)); | |
69 | if (v->contents == NULL) | |
70 | return GIT_ENOMEM; | |
71 | ||
72 | return GIT_SUCCESS; | |
73 | } | |
74 | ||
75 | int git_vector_insert(git_vector *v, void *element) | |
76 | { | |
77 | assert(v); | |
78 | ||
79 | if (v->length >= v->_alloc_size) { | |
80 | if (resize_vector(v) < 0) | |
81 | return GIT_ENOMEM; | |
82 | } | |
83 | ||
84 | v->contents[v->length++] = element; | |
86d7e1ca | 85 | v->sorted = 0; |
c4034e63 VM |
86 | |
87 | return GIT_SUCCESS; | |
88 | } | |
89 | ||
c4034e63 VM |
90 | void git_vector_sort(git_vector *v) |
91 | { | |
92 | assert(v); | |
93 | ||
86d7e1ca VM |
94 | if (v->sorted || v->_cmp == NULL) |
95 | return; | |
96 | ||
de18f276 | 97 | git__tsort(v->contents, v->length, v->_cmp); |
86d7e1ca | 98 | v->sorted = 1; |
c4034e63 VM |
99 | } |
100 | ||
86d7e1ca | 101 | int git_vector_bsearch2(git_vector *v, git_vector_cmp key_lookup, const void *key) |
c4034e63 VM |
102 | { |
103 | void **find; | |
104 | ||
86d7e1ca VM |
105 | assert(v && key && key_lookup); |
106 | ||
48c27f86 VM |
107 | /* need comparison function to sort the vector */ |
108 | if (v->_cmp == NULL) | |
86f5fa78 | 109 | return git__throw(GIT_ENOTFOUND, "Can't sort vector. No comparison function set"); |
48c27f86 | 110 | |
86d7e1ca VM |
111 | git_vector_sort(v); |
112 | ||
de18f276 | 113 | find = git__bsearch(key, v->contents, v->length, key_lookup); |
86d7e1ca VM |
114 | if (find != NULL) |
115 | return (int)(find - v->contents); | |
116 | ||
86f5fa78 | 117 | return git__throw(GIT_ENOTFOUND, "Can't find element"); |
86d7e1ca VM |
118 | } |
119 | ||
120 | int git_vector_search2(git_vector *v, git_vector_cmp key_lookup, const void *key) | |
121 | { | |
122 | unsigned int i; | |
123 | ||
124 | assert(v && key && key_lookup); | |
125 | ||
126 | for (i = 0; i < v->length; ++i) { | |
127 | if (key_lookup(key, v->contents[i]) == 0) | |
128 | return i; | |
129 | } | |
130 | ||
86f5fa78 | 131 | return git__throw(GIT_ENOTFOUND, "Can't find element"); |
86d7e1ca VM |
132 | } |
133 | ||
48c27f86 | 134 | static int strict_comparison(const void *a, const void *b) |
86d7e1ca | 135 | { |
3c41c635 | 136 | return (a == b) ? 0 : -1; |
48c27f86 | 137 | } |
c4034e63 | 138 | |
48c27f86 VM |
139 | int git_vector_search(git_vector *v, const void *entry) |
140 | { | |
141 | return git_vector_search2(v, v->_cmp ? v->_cmp : strict_comparison, entry); | |
86d7e1ca VM |
142 | } |
143 | ||
144 | int git_vector_bsearch(git_vector *v, const void *key) | |
145 | { | |
86d7e1ca | 146 | return git_vector_bsearch2(v, v->_cmp, key); |
c4034e63 VM |
147 | } |
148 | ||
149 | int git_vector_remove(git_vector *v, unsigned int idx) | |
150 | { | |
151 | unsigned int i; | |
152 | ||
153 | assert(v); | |
154 | ||
155 | if (idx >= v->length || v->length == 0) | |
86f5fa78 | 156 | return git__throw(GIT_ENOTFOUND, "Can't remove element. Index out of bounds"); |
c4034e63 | 157 | |
a17777d1 | 158 | for (i = idx; i < v->length - 1; ++i) |
c4034e63 VM |
159 | v->contents[i] = v->contents[i + 1]; |
160 | ||
161 | v->length--; | |
162 | return GIT_SUCCESS; | |
163 | } | |
164 | ||
476c42ac KS |
165 | void git_vector_uniq(git_vector *v) |
166 | { | |
167 | git_vector_cmp cmp; | |
168 | unsigned int i, j; | |
169 | ||
170 | if (v->length <= 1) | |
171 | return; | |
172 | ||
173 | git_vector_sort(v); | |
174 | cmp = v->_cmp ? v->_cmp : strict_comparison; | |
175 | ||
176 | for (i = 0, j = 1 ; j < v->length; ++j) | |
de18f276 | 177 | if (!cmp(v->contents[i], v->contents[j])) |
476c42ac KS |
178 | v->contents[i] = v->contents[j]; |
179 | else | |
180 | v->contents[++i] = v->contents[j]; | |
181 | ||
182 | v->length -= j - i - 1; | |
183 | } | |
184 | ||
c4034e63 VM |
185 | void git_vector_clear(git_vector *v) |
186 | { | |
187 | assert(v); | |
188 | v->length = 0; | |
86d7e1ca | 189 | v->sorted = 1; |
c4034e63 VM |
190 | } |
191 | ||
192 |