File Coverage

deps/libgit2/src/vector.c
Criterion Covered Total %
statement 157 219 71.6
branch 77 156 49.3
condition n/a
subroutine n/a
pod n/a
total 234 375 62.4


line stmt bran cond sub pod time code
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 1093           GIT_INLINE(size_t) compute_new_size(git_vector *v)
16             {
17 1093           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 1093 100         if (new_size < MIN_ALLOCSIZE)
22 1083           new_size = MIN_ALLOCSIZE;
23 10 50         else if (new_size <= (SIZE_MAX / 3) * 2)
24 10           new_size += new_size / 2;
25             else
26 0           new_size = SIZE_MAX;
27              
28 1093           return new_size;
29             }
30              
31 4985           GIT_INLINE(int) resize_vector(git_vector *v, size_t new_size)
32             {
33             void *new_contents;
34              
35 4985 50         if (new_size == 0)
36 0           return 0;
37              
38 4985           new_contents = git__reallocarray(v->contents, new_size, sizeof(void *));
39 4985 50         GIT_ERROR_CHECK_ALLOC(new_contents);
40              
41 4985           v->_alloc_size = new_size;
42 4985           v->contents = new_contents;
43              
44 4985           return 0;
45             }
46              
47 25           int git_vector_size_hint(git_vector *v, size_t size_hint)
48             {
49 25 50         if (v->_alloc_size >= size_hint)
50 25           return 0;
51 0           return resize_vector(v, size_hint);
52             }
53              
54 431           int git_vector_dup(git_vector *v, const git_vector *src, git_vector_cmp cmp)
55             {
56 431 50         assert(v && src);
    50          
57              
58 431           v->_alloc_size = 0;
59 431           v->contents = NULL;
60 431 50         v->_cmp = cmp ? cmp : src->_cmp;
61 431           v->length = src->length;
62 431           v->flags = src->flags;
63 431 50         if (cmp != src->_cmp)
64 0           git_vector_set_sorted(v, 0);
65              
66 431 100         if (src->length) {
67             size_t bytes;
68 400 50         GIT_ERROR_CHECK_ALLOC_MULTIPLY(&bytes, src->length, sizeof(void *));
    50          
69 400           v->contents = git__malloc(bytes);
70 400 50         GIT_ERROR_CHECK_ALLOC(v->contents);
71 400           v->_alloc_size = src->length;
72 400           memcpy(v->contents, src->contents, bytes);
73             }
74              
75 431           return 0;
76             }
77              
78 8494           void git_vector_free(git_vector *v)
79             {
80 8494 50         assert(v);
81              
82 8494           git__free(v->contents);
83 8494           v->contents = NULL;
84              
85 8494           v->length = 0;
86 8494           v->_alloc_size = 0;
87 8494           }
88              
89 862           void git_vector_free_deep(git_vector *v)
90             {
91             size_t i;
92              
93 862 50         assert(v);
94              
95 1382 100         for (i = 0; i < v->length; ++i) {
96 520           git__free(v->contents[i]);
97 520           v->contents[i] = NULL;
98             }
99              
100 862           git_vector_free(v);
101 862           }
102              
103 3892           int git_vector_init(git_vector *v, size_t initial_size, git_vector_cmp cmp)
104             {
105 3892 50         assert(v);
106              
107 3892           v->_alloc_size = 0;
108 3892           v->_cmp = cmp;
109 3892           v->length = 0;
110 3892           v->flags = GIT_VECTOR_SORTED;
111 3892           v->contents = NULL;
112              
113 3892           return resize_vector(v, max(initial_size, MIN_ALLOCSIZE));
114             }
115              
116 9           void **git_vector_detach(size_t *size, size_t *asize, git_vector *v)
117             {
118 9           void **data = v->contents;
119              
120 9 50         if (size)
121 9           *size = v->length;
122 9 50         if (asize)
123 0           *asize = v->_alloc_size;
124              
125 9           v->_alloc_size = 0;
126 9           v->length = 0;
127 9           v->contents = NULL;
128              
129 9           return data;
130             }
131              
132 5710           int git_vector_insert(git_vector *v, void *element)
133             {
134 5710 50         assert(v);
135              
136 6787           if (v->length >= v->_alloc_size &&
137 1077           resize_vector(v, compute_new_size(v)) < 0)
138 0           return -1;
139              
140 5710           v->contents[v->length++] = element;
141              
142 5710 100         git_vector_set_sorted(v, v->length <= 1);
143              
144 5710           return 0;
145             }
146              
147 1467           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 1467 50         assert(v && v->_cmp);
    50          
154              
155 1467 100         if (!git_vector_is_sorted(v))
156 16           git_vector_sort(v);
157              
158 1483           if (v->length >= v->_alloc_size &&
159 16           resize_vector(v, compute_new_size(v)) < 0)
160 0           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 1467 100         if (!git__bsearch(v->contents, v->length, element, v->_cmp, &pos) &&
    50          
167 7 50         on_dup && (result = on_dup(&v->contents[pos], element)) < 0)
168 7           return result;
169              
170             /* shift elements to the right */
171 1460 100         if (pos < v->length)
172 144           memmove(v->contents + pos + 1, v->contents + pos,
173 144           (v->length - pos) * sizeof(void *));
174              
175 1460           v->contents[pos] = element;
176 1460           v->length++;
177              
178 1467           return 0;
179             }
180              
181 8262           void git_vector_sort(git_vector *v)
182             {
183 8262 50         assert(v);
184              
185 8262 100         if (git_vector_is_sorted(v) || !v->_cmp)
    50          
186 7684           return;
187              
188 578 100         if (v->length > 1)
189 412           git__tsort(v->contents, v->length, v->_cmp);
190 578           git_vector_set_sorted(v, 1);
191             }
192              
193 1833           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 1833 50         assert(v && key && key_lookup);
    50          
    50          
200              
201             /* need comparison function to sort the vector */
202 1833 50         if (!v->_cmp)
203 0           return -1;
204              
205 1833           git_vector_sort(v);
206              
207 1833           return git__bsearch(v->contents, v->length, key, key_lookup, at_pos);
208             }
209              
210 12           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 12 50         assert(v && key && key_lookup);
    50          
    50          
216              
217 36 100         for (i = 0; i < v->length; ++i) {
218 29 100         if (key_lookup(key, v->contents[i]) == 0) {
219 5 50         if (at_pos)
220 5           *at_pos = i;
221              
222 5           return 0;
223             }
224             }
225              
226 7           return GIT_ENOTFOUND;
227             }
228              
229 0           static int strict_comparison(const void *a, const void *b)
230             {
231 0 0         return (a == b) ? 0 : -1;
232             }
233              
234 0           int git_vector_search(size_t *at_pos, const git_vector *v, const void *entry)
235             {
236 0 0         return git_vector_search2(at_pos, v, v->_cmp ? v->_cmp : strict_comparison, entry);
237             }
238              
239 183           int git_vector_remove(git_vector *v, size_t idx)
240             {
241             size_t shift_count;
242              
243 183 50         assert(v);
244              
245 183 50         if (idx >= v->length)
246 0           return GIT_ENOTFOUND;
247              
248 183           shift_count = v->length - idx - 1;
249              
250 183 100         if (shift_count)
251 17           memmove(&v->contents[idx], &v->contents[idx + 1],
252             shift_count * sizeof(void *));
253              
254 183           v->length--;
255 183           return 0;
256             }
257              
258 435           void git_vector_pop(git_vector *v)
259             {
260 435 100         if (v->length > 0)
261 421           v->length--;
262 435           }
263              
264 3           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 3 50         if (v->length <= 1)
270 0           return;
271              
272 3           git_vector_sort(v);
273 3 50         cmp = v->_cmp ? v->_cmp : strict_comparison;
274              
275 10 100         for (i = 0, j = 1 ; j < v->length; ++j)
276 7 100         if (!cmp(v->contents[i], v->contents[j])) {
277 3 50         if (git_free_cb)
278 3           git_free_cb(v->contents[i]);
279              
280 3           v->contents[i] = v->contents[j];
281             } else
282 4           v->contents[++i] = v->contents[j];
283              
284 3           v->length -= j - i - 1;
285             }
286              
287 39           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 64 100         for (i = 0, j = 0; j < v->length; ++j) {
295 25           v->contents[i] = v->contents[j];
296              
297 25 50         if (!match(v, i, payload))
298 25           i++;
299             }
300              
301 39           v->length = i;
302 39           }
303              
304 843           void git_vector_clear(git_vector *v)
305             {
306 843 50         assert(v);
307 843           v->length = 0;
308 843           git_vector_set_sorted(v, 1);
309 843           }
310              
311 17           void git_vector_swap(git_vector *a, git_vector *b)
312             {
313             git_vector t;
314              
315 17 50         assert(a && b);
    50          
316              
317 17 50         if (a != b) {
318 17           memcpy(&t, a, sizeof(t));
319 17           memcpy(a, b, sizeof(t));
320 17           memcpy(b, &t, sizeof(t));
321             }
322 17           }
323              
324 0           int git_vector_resize_to(git_vector *v, size_t new_length)
325             {
326 0           if (new_length > v->_alloc_size &&
327 0           resize_vector(v, new_length) < 0)
328 0           return -1;
329              
330 0 0         if (new_length > v->length)
331 0           memset(&v->contents[v->length], 0,
332 0           sizeof(void *) * (new_length - v->length));
333              
334 0           v->length = new_length;
335              
336 0           return 0;
337             }
338              
339 0           int git_vector_insert_null(git_vector *v, size_t idx, size_t insert_len)
340             {
341             size_t new_length;
342              
343 0 0         assert(insert_len > 0 && idx <= v->length);
    0          
344              
345 0 0         GIT_ERROR_CHECK_ALLOC_ADD(&new_length, v->length, insert_len);
    0          
346              
347 0 0         if (new_length > v->_alloc_size && resize_vector(v, new_length) < 0)
    0          
348 0           return -1;
349              
350 0           memmove(&v->contents[idx + insert_len], &v->contents[idx],
351 0           sizeof(void *) * (v->length - idx));
352 0           memset(&v->contents[idx], 0, sizeof(void *) * insert_len);
353              
354 0           v->length = new_length;
355 0           return 0;
356             }
357              
358 0           int git_vector_remove_range(git_vector *v, size_t idx, size_t remove_len)
359             {
360 0           size_t new_length = v->length - remove_len;
361 0           size_t end_idx = 0;
362            
363 0 0         assert(remove_len > 0);
364              
365 0 0         if (git__add_sizet_overflow(&end_idx, idx, remove_len))
366 0           assert(0);
367              
368 0 0         assert(end_idx <= v->length);
369              
370 0 0         if (end_idx < v->length)
371 0           memmove(&v->contents[idx], &v->contents[end_idx],
372 0           sizeof(void *) * (v->length - end_idx));
373              
374 0           memset(&v->contents[new_length], 0, sizeof(void *) * remove_len);
375              
376 0           v->length = new_length;
377 0           return 0;
378             }
379              
380 2           int git_vector_set(void **old, git_vector *v, size_t position, void *value)
381             {
382 2 50         if (position + 1 > v->length) {
383 0 0         if (git_vector_resize_to(v, position + 1) < 0)
384 0           return -1;
385             }
386              
387 2 50         if (old != NULL)
388 0           *old = v->contents[position];
389              
390 2           v->contents[position] = value;
391              
392 2           return 0;
393             }
394              
395 0           int git_vector_verify_sorted(const git_vector *v)
396             {
397             size_t i;
398              
399 0 0         if (!git_vector_is_sorted(v))
400 0           return -1;
401              
402 0 0         for (i = 1; i < v->length; ++i) {
403 0 0         if (v->_cmp(v->contents[i - 1], v->contents[i]) > 0)
404 0           return -1;
405             }
406              
407 0           return 0;
408             }
409              
410 5           void git_vector_reverse(git_vector *v)
411             {
412             size_t a, b;
413              
414 5 50         if (v->length == 0)
415 0           return;
416              
417 5           a = 0;
418 5           b = v->length - 1;
419              
420 5 50         while (a < b) {
421 0           void *tmp = v->contents[a];
422 0           v->contents[a] = v->contents[b];
423 0           v->contents[b] = tmp;
424 0           a++;
425 0           b--;
426             }
427             }