]>
Commit | Line | Data |
---|---|---|
c4034e63 | 1 | /* |
5e0de328 | 2 | * Copyright (C) 2009-2012 the libgit2 contributors |
c4034e63 | 3 | * |
bb742ede VM |
4 | * This file is part of libgit2, distributed under the GNU GPL v2 with |
5 | * a Linking Exception. For full terms see the included COPYING file. | |
c4034e63 VM |
6 | */ |
7 | ||
8 | #include "common.h" | |
9 | #include "repository.h" | |
10 | #include "vector.h" | |
11 | ||
12 | static const double resize_factor = 1.75; | |
44ef8b1b | 13 | static const unsigned int minimum_size = 8; |
c4034e63 VM |
14 | |
15 | static int resize_vector(git_vector *v) | |
16 | { | |
a17777d1 | 17 | v->_alloc_size = ((unsigned int)(v->_alloc_size * resize_factor)) + 1; |
86194b24 | 18 | if (v->_alloc_size < minimum_size) |
c4034e63 VM |
19 | v->_alloc_size = minimum_size; |
20 | ||
3286c408 | 21 | v->contents = git__realloc(v->contents, v->_alloc_size * sizeof(void *)); |
ae9e29fd | 22 | GITERR_CHECK_ALLOC(v->contents); |
c4034e63 | 23 | |
ae9e29fd | 24 | return 0; |
c4034e63 VM |
25 | } |
26 | ||
c4034e63 VM |
27 | void git_vector_free(git_vector *v) |
28 | { | |
29 | assert(v); | |
ee1f0b1a | 30 | |
3286c408 | 31 | git__free(v->contents); |
ee1f0b1a RB |
32 | v->contents = NULL; |
33 | ||
34 | v->length = 0; | |
35 | v->_alloc_size = 0; | |
c4034e63 VM |
36 | } |
37 | ||
86d7e1ca | 38 | int git_vector_init(git_vector *v, unsigned int initial_size, git_vector_cmp cmp) |
c4034e63 VM |
39 | { |
40 | assert(v); | |
41 | ||
42 | memset(v, 0x0, sizeof(git_vector)); | |
43 | ||
44 | if (initial_size == 0) | |
45 | initial_size = minimum_size; | |
46 | ||
47 | v->_alloc_size = initial_size; | |
48 | v->_cmp = cmp; | |
932d1baf | 49 | |
c4034e63 | 50 | v->length = 0; |
86d7e1ca | 51 | v->sorted = 1; |
c4034e63 VM |
52 | |
53 | v->contents = git__malloc(v->_alloc_size * sizeof(void *)); | |
ae9e29fd | 54 | GITERR_CHECK_ALLOC(v->contents); |
c4034e63 | 55 | |
ae9e29fd | 56 | return 0; |
c4034e63 VM |
57 | } |
58 | ||
59 | int git_vector_insert(git_vector *v, void *element) | |
60 | { | |
61 | assert(v); | |
62 | ||
ae9e29fd RB |
63 | if (v->length >= v->_alloc_size && |
64 | resize_vector(v) < 0) | |
65 | return -1; | |
c4034e63 VM |
66 | |
67 | v->contents[v->length++] = element; | |
86d7e1ca | 68 | v->sorted = 0; |
c4034e63 | 69 | |
ae9e29fd | 70 | return 0; |
c4034e63 VM |
71 | } |
72 | ||
ae9e29fd RB |
73 | int git_vector_insert_sorted( |
74 | git_vector *v, void *element, int (*on_dup)(void **old, void *new)) | |
bd370b14 | 75 | { |
ae9e29fd | 76 | int result; |
bd370b14 RB |
77 | size_t pos; |
78 | ||
79 | assert(v && v->_cmp); | |
80 | ||
81 | if (!v->sorted) | |
82 | git_vector_sort(v); | |
83 | ||
ae9e29fd RB |
84 | if (v->length >= v->_alloc_size && |
85 | resize_vector(v) < 0) | |
86 | return -1; | |
bd370b14 | 87 | |
ae9e29fd RB |
88 | /* If we find the element and have a duplicate handler callback, |
89 | * invoke it. If it returns non-zero, then cancel insert, otherwise | |
bd370b14 RB |
90 | * proceed with normal insert. |
91 | */ | |
ae9e29fd RB |
92 | if (git__bsearch(v->contents, v->length, element, v->_cmp, &pos) >= 0 && |
93 | on_dup != NULL && | |
94 | (result = on_dup(&v->contents[pos], element)) < 0) | |
95 | return result; | |
bd370b14 RB |
96 | |
97 | /* shift elements to the right */ | |
98 | if (pos < v->length) { | |
99 | memmove(v->contents + pos + 1, v->contents + pos, | |
100 | (v->length - pos) * sizeof(void *)); | |
101 | } | |
102 | ||
103 | v->contents[pos] = element; | |
104 | v->length++; | |
ae9e29fd | 105 | return 0; |
bd370b14 RB |
106 | } |
107 | ||
c4034e63 VM |
108 | void git_vector_sort(git_vector *v) |
109 | { | |
110 | assert(v); | |
111 | ||
86d7e1ca VM |
112 | if (v->sorted || v->_cmp == NULL) |
113 | return; | |
114 | ||
de18f276 | 115 | git__tsort(v->contents, v->length, v->_cmp); |
86d7e1ca | 116 | v->sorted = 1; |
c4034e63 VM |
117 | } |
118 | ||
86d7e1ca | 119 | int git_vector_bsearch2(git_vector *v, git_vector_cmp key_lookup, const void *key) |
c4034e63 | 120 | { |
bd370b14 | 121 | size_t pos; |
c4034e63 | 122 | |
86d7e1ca VM |
123 | assert(v && key && key_lookup); |
124 | ||
48c27f86 | 125 | /* need comparison function to sort the vector */ |
ae9e29fd | 126 | assert(v->_cmp != NULL); |
48c27f86 | 127 | |
86d7e1ca VM |
128 | git_vector_sort(v); |
129 | ||
ae9e29fd | 130 | if (git__bsearch(v->contents, v->length, key, key_lookup, &pos) >= 0) |
bd370b14 | 131 | return (int)pos; |
86d7e1ca | 132 | |
ae9e29fd | 133 | return GIT_ENOTFOUND; |
86d7e1ca VM |
134 | } |
135 | ||
136 | int git_vector_search2(git_vector *v, git_vector_cmp key_lookup, const void *key) | |
137 | { | |
138 | unsigned int i; | |
139 | ||
140 | assert(v && key && key_lookup); | |
141 | ||
142 | for (i = 0; i < v->length; ++i) { | |
143 | if (key_lookup(key, v->contents[i]) == 0) | |
144 | return i; | |
145 | } | |
146 | ||
ae9e29fd | 147 | return GIT_ENOTFOUND; |
86d7e1ca VM |
148 | } |
149 | ||
48c27f86 | 150 | static int strict_comparison(const void *a, const void *b) |
86d7e1ca | 151 | { |
3c41c635 | 152 | return (a == b) ? 0 : -1; |
48c27f86 | 153 | } |
c4034e63 | 154 | |
48c27f86 VM |
155 | int git_vector_search(git_vector *v, const void *entry) |
156 | { | |
157 | return git_vector_search2(v, v->_cmp ? v->_cmp : strict_comparison, entry); | |
86d7e1ca VM |
158 | } |
159 | ||
160 | int git_vector_bsearch(git_vector *v, const void *key) | |
161 | { | |
86d7e1ca | 162 | return git_vector_bsearch2(v, v->_cmp, key); |
c4034e63 VM |
163 | } |
164 | ||
165 | int git_vector_remove(git_vector *v, unsigned int idx) | |
166 | { | |
167 | unsigned int i; | |
168 | ||
169 | assert(v); | |
170 | ||
171 | if (idx >= v->length || v->length == 0) | |
ae9e29fd | 172 | return GIT_ENOTFOUND; |
c4034e63 | 173 | |
a17777d1 | 174 | for (i = idx; i < v->length - 1; ++i) |
c4034e63 VM |
175 | v->contents[i] = v->contents[i + 1]; |
176 | ||
177 | v->length--; | |
ae9e29fd | 178 | return 0; |
c4034e63 VM |
179 | } |
180 | ||
0534641d | 181 | void git_vector_pop(git_vector *v) |
b6c93aef | 182 | { |
0534641d RB |
183 | if (v->length > 0) |
184 | v->length--; | |
b6c93aef RB |
185 | } |
186 | ||
476c42ac KS |
187 | void git_vector_uniq(git_vector *v) |
188 | { | |
189 | git_vector_cmp cmp; | |
190 | unsigned int i, j; | |
191 | ||
192 | if (v->length <= 1) | |
193 | return; | |
194 | ||
195 | git_vector_sort(v); | |
196 | cmp = v->_cmp ? v->_cmp : strict_comparison; | |
197 | ||
198 | for (i = 0, j = 1 ; j < v->length; ++j) | |
de18f276 | 199 | if (!cmp(v->contents[i], v->contents[j])) |
476c42ac KS |
200 | v->contents[i] = v->contents[j]; |
201 | else | |
202 | v->contents[++i] = v->contents[j]; | |
203 | ||
204 | v->length -= j - i - 1; | |
205 | } | |
206 | ||
c4034e63 VM |
207 | void git_vector_clear(git_vector *v) |
208 | { | |
209 | assert(v); | |
210 | v->length = 0; | |
86d7e1ca | 211 | v->sorted = 1; |
c4034e63 VM |
212 | } |
213 | ||
74fa4bfa RB |
214 | void git_vector_swap(git_vector *a, git_vector *b) |
215 | { | |
216 | git_vector t; | |
217 | ||
218 | if (!a || !b || a == b) | |
219 | return; | |
c4034e63 | 220 | |
74fa4bfa RB |
221 | memcpy(&t, a, sizeof(t)); |
222 | memcpy(a, b, sizeof(t)); | |
223 | memcpy(b, &t, sizeof(t)); | |
224 | } |