Line Flow Count Block(s) Source
1 - /*
2 - * Copyright (C) the libgit2 contributors. All rights reserved.
3 - *
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.
6 - */
7 -
8 - #include "vector.h"
9 -
10 - #include "integer.h"
11 -
12 - /* In elements, not bytes */
13 - #define MIN_ALLOCSIZE 8
14 -
15 78445 2 GIT_INLINE(size_t) compute_new_size(git_vector *v)
16 - {
17 78445 2 size_t new_size = v->_alloc_size;
18 -
19 - /* Use a resize factor of 1.5, which is quick to compute using integer
20 - * instructions and less than the golden ratio (1.618...) */
21 78445 2 if (new_size < MIN_ALLOCSIZE)
22 73940 3 new_size = MIN_ALLOCSIZE;
23 4505 4 else if (new_size <= (SIZE_MAX / 3) * 2)
24 4505 5 new_size += new_size / 2;
25 - else
26 ##### 6 new_size = SIZE_MAX;
27 -
28 78445 7 return new_size;
29 - }
30 -
31 365681 2 GIT_INLINE(int) resize_vector(git_vector *v, size_t new_size)
32 - {
33 - void *new_contents;
34 -
35 365681 2 if (new_size == 0)
36 ##### 3 return 0;
37 -
38 365681 4 new_contents = git__reallocarray(v->contents, new_size, sizeof(void *));
39 365734 5,6 GIT_ERROR_CHECK_ALLOC(new_contents);
40 -
41 365734 7 v->_alloc_size = new_size;
42 365734 7 v->contents = new_contents;
43 -
44 365734 7 return 0;
45 - }
46 -
47 496 2 int git_vector_size_hint(git_vector *v, size_t size_hint)
48 - {
49 496 2 if (v->_alloc_size >= size_hint)
50 431 3 return 0;
51 65 4 return resize_vector(v, size_hint);
52 - }
53 -
54 6473 2 int git_vector_dup(git_vector *v, const git_vector *src, git_vector_cmp cmp)
55 - {
56 6473 2-4 assert(v && src);
57 -
58 6473 5 v->_alloc_size = 0;
59 6473 5 v->contents = NULL;
60 6473 5-7 v->_cmp = cmp ? cmp : src->_cmp;
61 6473 8 v->length = src->length;
62 6473 8 v->flags = src->flags;
63 6473 8 if (cmp != src->_cmp)
64 3 9 git_vector_set_sorted(v, 0);
65 -
66 6473 10 if (src->length) {
67 - size_t bytes;
68 6136 11-17,22 GIT_ERROR_CHECK_ALLOC_MULTIPLY(&bytes, src->length, sizeof(void *));
69 6136 18 v->contents = git__malloc(bytes);
70 6136 19,20 GIT_ERROR_CHECK_ALLOC(v->contents);
71 6136 21 v->_alloc_size = src->length;
72 6136 21 memcpy(v->contents, src->contents, bytes);
73 - }
74 -
75 6473 23 return 0;
76 - }
77 -
78 743751 2 void git_vector_free(git_vector *v)
79 - {
80 743751 2,3 assert(v);
81 -
82 743751 4 git__free(v->contents);
83 743720 5 v->contents = NULL;
84 -
85 743720 5 v->length = 0;
86 743720 5 v->_alloc_size = 0;
87 743720 5 }
88 -
89 19182 2 void git_vector_free_deep(git_vector *v)
90 - {
91 - size_t i;
92 -
93 19182 2,3 assert(v);
94 -
95 56047 4,6,7 for (i = 0; i < v->length; ++i) {
96 36865 5 git__free(v->contents[i]);
97 36865 6 v->contents[i] = NULL;
98 - }
99 -
100 19182 8 git_vector_free(v);
101 19182 9 }
102 -
103 287189 2 int git_vector_init(git_vector *v, size_t initial_size, git_vector_cmp cmp)
104 - {
105 287189 2,3 assert(v);
106 -
107 287189 4 v->_alloc_size = 0;
108 287189 4 v->_cmp = cmp;
109 287189 4 v->length = 0;
110 287189 4 v->flags = GIT_VECTOR_SORTED;
111 287189 4 v->contents = NULL;
112 -
113 287189 4 return resize_vector(v, max(initial_size, MIN_ALLOCSIZE));
114 - }
115 -
116 218 2 void **git_vector_detach(size_t *size, size_t *asize, git_vector *v)
117 - {
118 218 2 void **data = v->contents;
119 -
120 218 2 if (size)
121 208 3 *size = v->length;
122 218 4 if (asize)
123 ##### 5 *asize = v->_alloc_size;
124 -
125 218 6 v->_alloc_size = 0;
126 218 6 v->length = 0;
127 218 6 v->contents = NULL;
128 -
129 218 6 return data;
130 - }
131 -
132 1060421 2 int git_vector_insert(git_vector *v, void *element)
133 - {
134 1060421 2,3 assert(v);
135 -
136 1060421 4,7 if (v->length >= v->_alloc_size &&
137 75782 5,6 resize_vector(v, compute_new_size(v)) < 0)
138 ##### 8 return -1;
139 -
140 1060431 9 v->contents[v->length++] = element;
141 -
142 1060431 9-11 git_vector_set_sorted(v, v->length <= 1);
143 -
144 1060431 12 return 0;
145 - }
146 -
147 - 2 suppressed: function cannot be solved git_vector_insert_sorted (automatic due to inconsistent arc counts in .gcda files)int git_vector_insert_sorted(
148 - git_vector *v, void *element, int (*on_dup)(void **old, void *new))
149 - {
150 - int result;
151 - size_t pos;
152 -
153 - 2-4 suppressed: function cannot be solved git_vector_insert_sorted (automatic due to inconsistent arc counts in .gcda files) assert(v && v->_cmp);
154 -
155 - 5 suppressed: function cannot be solved git_vector_insert_sorted (automatic due to inconsistent arc counts in .gcda files) if (!git_vector_is_sorted(v))
156 - 6 suppressed: function cannot be solved git_vector_insert_sorted (automatic due to inconsistent arc counts in .gcda files) git_vector_sort(v);
157 -
158 - 7,10 suppressed: function cannot be solved git_vector_insert_sorted (automatic due to inconsistent arc counts in .gcda files) if (v->length >= v->_alloc_size &&
159 - 8,9 suppressed: function cannot be solved git_vector_insert_sorted (automatic due to inconsistent arc counts in .gcda files) resize_vector(v, compute_new_size(v)) < 0)
160 - 11 suppressed: function cannot be solved git_vector_insert_sorted (automatic due to inconsistent arc counts in .gcda files) return -1;
161 -
162 - /* If we find the element and have a duplicate handler callback,
163 - * invoke it. If it returns non-zero, then cancel insert, otherwise
164 - * proceed with normal insert.
165 - */
166 - 12-14 suppressed: function cannot be solved git_vector_insert_sorted (automatic due to inconsistent arc counts in .gcda files) if (!git__bsearch(v->contents, v->length, element, v->_cmp, &pos) &&
167 - 15,16 suppressed: function cannot be solved git_vector_insert_sorted (automatic due to inconsistent arc counts in .gcda files) on_dup && (result = on_dup(&v->contents[pos], element)) < 0)
168 - 17 suppressed: function cannot be solved git_vector_insert_sorted (automatic due to inconsistent arc counts in .gcda files) return result;
169 -
170 - /* shift elements to the right */
171 - 18 suppressed: function cannot be solved git_vector_insert_sorted (automatic due to inconsistent arc counts in .gcda files) if (pos < v->length)
172 - 19 suppressed: function cannot be solved git_vector_insert_sorted (automatic due to inconsistent arc counts in .gcda files) memmove(v->contents + pos + 1, v->contents + pos,
173 - 19 suppressed: function cannot be solved git_vector_insert_sorted (automatic due to inconsistent arc counts in .gcda files) (v->length - pos) * sizeof(void *));
174 -
175 - 20 suppressed: function cannot be solved git_vector_insert_sorted (automatic due to inconsistent arc counts in .gcda files) v->contents[pos] = element;
176 - 20 suppressed: function cannot be solved git_vector_insert_sorted (automatic due to inconsistent arc counts in .gcda files) v->length++;
177 -
178 - 20 suppressed: function cannot be solved git_vector_insert_sorted (automatic due to inconsistent arc counts in .gcda files) return 0;
179 - }
180 -
181 488505 2 void git_vector_sort(git_vector *v)
182 - {
183 488505 2,3 assert(v);
184 -
185 488505 4,5 if (git_vector_is_sorted(v) || !v->_cmp)
186 488493 6,10 return;
187 -
188 17954 7 if (v->length > 1)
189 12528 8 git__tsort(v->contents, v->length, v->_cmp);
190 17942 9 git_vector_set_sorted(v, 1);
191 - }
192 -
193 - 2 suppressed: function cannot be solved git_vector_bsearch2 (automatic due to inconsistent arc counts in .gcda files)int git_vector_bsearch2(
194 - size_t *at_pos,
195 - git_vector *v,
196 - git_vector_cmp key_lookup,
197 - const void *key)
198 - {
199 - 2-5 suppressed: function cannot be solved git_vector_bsearch2 (automatic due to inconsistent arc counts in .gcda files) assert(v && key && key_lookup);
200 -
201 - /* need comparison function to sort the vector */
202 - 6 suppressed: function cannot be solved git_vector_bsearch2 (automatic due to inconsistent arc counts in .gcda files) if (!v->_cmp)
203 - 7 suppressed: function cannot be solved git_vector_bsearch2 (automatic due to inconsistent arc counts in .gcda files) return -1;
204 -
205 - 8 suppressed: function cannot be solved git_vector_bsearch2 (automatic due to inconsistent arc counts in .gcda files) git_vector_sort(v);
206 -
207 - 9 suppressed: function cannot be solved git_vector_bsearch2 (automatic due to inconsistent arc counts in .gcda files) return git__bsearch(v->contents, v->length, key, key_lookup, at_pos);
208 - }
209 -
210 168 2 int git_vector_search2(
211 - size_t *at_pos, const git_vector *v, git_vector_cmp key_lookup, const void *key)
212 - {
213 - size_t i;
214 -
215 168 2-5 assert(v && key && key_lookup);
216 -
217 1188 6,12,13 for (i = 0; i < v->length; ++i) {
218 1108 7,8 if (key_lookup(key, v->contents[i]) == 0) {
219 88 9 if (at_pos)
220 87 10 *at_pos = i;
221 -
222 88 11 return 0;
223 - }
224 - }
225 -
226 80 14 return GIT_ENOTFOUND;
227 - }
228 -
229 ##### 2 static int strict_comparison(const void *a, const void *b)
230 - {
231 ##### 2 return (a == b) ? 0 : -1;
232 - }
233 -
234 45 2 int git_vector_search(size_t *at_pos, const git_vector *v, const void *entry)
235 - {
236 45 2 return git_vector_search2(at_pos, v, v->_cmp ? v->_cmp : strict_comparison, entry);
237 - }
238 -
239 44546 2 int git_vector_remove(git_vector *v, size_t idx)
240 - {
241 - size_t shift_count;
242 -
243 44546 2,3 assert(v);
244 -
245 44546 4 if (idx >= v->length)
246 1 5 return GIT_ENOTFOUND;
247 -
248 44545 6 shift_count = v->length - idx - 1;
249 -
250 44545 6 if (shift_count)
251 1922 7 memmove(&v->contents[idx], &v->contents[idx + 1],
252 - shift_count * sizeof(void *));
253 -
254 44545 8 v->length--;
255 44545 8 return 0;
256 - }
257 -
258 5770 2 void git_vector_pop(git_vector *v)
259 - {
260 5770 2 if (v->length > 0)
261 5686 3 v->length--;
262 5770 4 }
263 -
264 509 2 void git_vector_uniq(git_vector *v, void (*git_free_cb)(void *))
265 - {
266 - git_vector_cmp cmp;
267 - size_t i, j;
268 -
269 509 2 if (v->length <= 1)
270 509 3,18 return;
271 -
272 74 4 git_vector_sort(v);
273 74 5-7 cmp = v->_cmp ? v->_cmp : strict_comparison;
274 -
275 546 8,15,16 for (i = 0, j = 1 ; j < v->length; ++j)
276 472 9,10 if (!cmp(v->contents[i], v->contents[j])) {
277 15 11 if (git_free_cb)
278 12 12 git_free_cb(v->contents[i]);
279 -
280 15 13 v->contents[i] = v->contents[j];
281 - } else
282 457 14 v->contents[++i] = v->contents[j];
283 -
284 74 17 v->length -= j - i - 1;
285 - }
286 -
287 591 2 void git_vector_remove_matching(
288 - git_vector *v,
289 - int (*match)(const git_vector *v, size_t idx, void *payload),
290 - void *payload)
291 - {
292 - size_t i, j;
293 -
294 4383 2,6,7 for (i = 0, j = 0; j < v->length; ++j) {
295 3792 3 v->contents[i] = v->contents[j];
296 -
297 3792 3,4 if (!match(v, i, payload))
298 2684 5 i++;
299 - }
300 -
301 591 8 v->length = i;
302 591 8 }
303 -
304 32449 2 void git_vector_clear(git_vector *v)
305 - {
306 32449 2,3 assert(v);
307 32449 4 v->length = 0;
308 32449 4 git_vector_set_sorted(v, 1);
309 32449 4 }
310 -
311 439 2 void git_vector_swap(git_vector *a, git_vector *b)
312 - {
313 - git_vector t;
314 -
315 439 2-4 assert(a && b);
316 -
317 439 5 if (a != b) {
318 439 6 memcpy(&t, a, sizeof(t));
319 439 6 memcpy(a, b, sizeof(t));
320 439 6 memcpy(b, &t, sizeof(t));
321 - }
322 439 7 }
323 -
324 ##### 2 int git_vector_resize_to(git_vector *v, size_t new_length)
325 - {
326 ##### 2,4 if (new_length > v->_alloc_size &&
327 ##### 3 resize_vector(v, new_length) < 0)
328 ##### 5 return -1;
329 -
330 ##### 6 if (new_length > v->length)
331 ##### 7 memset(&v->contents[v->length], 0,
332 ##### 7 sizeof(void *) * (new_length - v->length));
333 -
334 ##### 8 v->length = new_length;
335 -
336 ##### 8 return 0;
337 - }
338 -
339 34 2 int git_vector_insert_null(git_vector *v, size_t idx, size_t insert_len)
340 - {
341 - size_t new_length;
342 -
343 34 2-4 assert(insert_len > 0 && idx <= v->length);
344 -
345 34 5-11 GIT_ERROR_CHECK_ALLOC_ADD(&new_length, v->length, insert_len);
346 -
347 34 12-14 if (new_length > v->_alloc_size && resize_vector(v, new_length) < 0)
348 ##### 15 return -1;
349 -
350 34 16 memmove(&v->contents[idx + insert_len], &v->contents[idx],
351 34 16 sizeof(void *) * (v->length - idx));
352 34 16 memset(&v->contents[idx], 0, sizeof(void *) * insert_len);
353 -
354 34 16 v->length = new_length;
355 34 16 return 0;
356 - }
357 -
358 24 2 int git_vector_remove_range(git_vector *v, size_t idx, size_t remove_len)
359 - {
360 24 2 size_t new_length = v->length - remove_len;
361 24 2 size_t end_idx = 0;
362 -
363 24 2,3 assert(remove_len > 0);
364 -
365 24 4,5 if (git__add_sizet_overflow(&end_idx, idx, remove_len))
366 - 6 assert(0);
367 -
368 24 7,8 assert(end_idx <= v->length);
369 -
370 24 9 if (end_idx < v->length)
371 16 10 memmove(&v->contents[idx], &v->contents[end_idx],
372 16 10 sizeof(void *) * (v->length - end_idx));
373 -
374 24 11 memset(&v->contents[new_length], 0, sizeof(void *) * remove_len);
375 -
376 24 11 v->length = new_length;
377 24 11 return 0;
378 - }
379 -
380 784 2 int git_vector_set(void **old, git_vector *v, size_t position, void *value)
381 - {
382 784 2 if (position + 1 > v->length) {
383 ##### 3,4 if (git_vector_resize_to(v, position + 1) < 0)
384 ##### 5 return -1;
385 - }
386 -
387 784 6 if (old != NULL)
388 93 7 *old = v->contents[position];
389 -
390 784 8 v->contents[position] = value;
391 -
392 784 8 return 0;
393 - }
394 -
395 6 2 int git_vector_verify_sorted(const git_vector *v)
396 - {
397 - size_t i;
398 -
399 6 2 if (!git_vector_is_sorted(v))
400 ##### 3 return -1;
401 -
402 654 4,8,9 for (i = 1; i < v->length; ++i) {
403 648 5,6 if (v->_cmp(v->contents[i - 1], v->contents[i]) > 0)
404 ##### 7 return -1;
405 - }
406 -
407 6 10 return 0;
408 - }
409 -
410 8 2 void git_vector_reverse(git_vector *v)
411 - {
412 - size_t a, b;
413 -
414 8 2 if (v->length == 0)
415 8 3,7 return;
416 -
417 7 4 a = 0;
418 7 4 b = v->length - 1;
419 -
420 11 4,6 while (a < b) {
421 4 5 void *tmp = v->contents[a];
422 4 5 v->contents[a] = v->contents[b];
423 4 5 v->contents[b] = tmp;
424 4 5 a++;
425 4 5 b--;
426 - }
427 - }