File Coverage

deps/libgit2/src/util/array.h
Criterion Covered Total %
statement 9 14 64.2
branch 2 8 25.0
condition n/a
subroutine n/a
pod n/a
total 11 22 50.0


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             #ifndef INCLUDE_array_h__
8             #define INCLUDE_array_h__
9              
10             #include "git2_util.h"
11              
12             /*
13             * Use this to declare a typesafe resizable array of items, a la:
14             *
15             * git_array_t(int) my_ints = GIT_ARRAY_INIT;
16             * ...
17             * int *i = git_array_alloc(my_ints);
18             * GIT_ERROR_CHECK_ALLOC(i);
19             * ...
20             * git_array_clear(my_ints);
21             *
22             * You may also want to do things like:
23             *
24             * typedef git_array_t(my_struct) my_struct_array_t;
25             */
26             #define git_array_t(type) struct { type *ptr; size_t size, asize; }
27              
28             #define GIT_ARRAY_INIT { NULL, 0, 0 }
29              
30             #define git_array_init(a) \
31             do { (a).size = (a).asize = 0; (a).ptr = NULL; } while (0)
32              
33             #define git_array_init_to_size(a, desired) \
34             do { (a).size = 0; (a).asize = desired; (a).ptr = git__calloc(desired, sizeof(*(a).ptr)); } while (0)
35              
36             #define git_array_clear(a) \
37             do { git__free((a).ptr); git_array_init(a); } while (0)
38              
39             #define GIT_ERROR_CHECK_ARRAY(a) GIT_ERROR_CHECK_ALLOC((a).ptr)
40              
41              
42             typedef git_array_t(char) git_array_generic_t;
43              
44             /* use a generic array for growth, return 0 on success */
45 10           GIT_INLINE(int) git_array_grow(void *_a, size_t item_size)
46             {
47 10           volatile git_array_generic_t *a = _a;
48             size_t new_size;
49             char *new_array;
50              
51 10 50         if (a->size < 8) {
52 10           new_size = 8;
53             } else {
54 0 0         if (GIT_MULTIPLY_SIZET_OVERFLOW(&new_size, a->size, 3))
    0          
55 0           goto on_oom;
56 0           new_size /= 2;
57             }
58              
59 10 50         if ((new_array = git__reallocarray(a->ptr, new_size, item_size)) == NULL)
60 0           goto on_oom;
61              
62 10           a->ptr = new_array;
63 10           a->asize = new_size;
64 10           return 0;
65              
66             on_oom:
67 0           git_array_clear(*a);
68 10           return -1;
69             }
70              
71             #define git_array_alloc(a) \
72             (((a).size < (a).asize || git_array_grow(&(a), sizeof(*(a).ptr)) == 0) ? \
73             &(a).ptr[(a).size++] : (void *)NULL)
74              
75             #define git_array_last(a) ((a).size ? &(a).ptr[(a).size - 1] : (void *)NULL)
76              
77             #define git_array_pop(a) ((a).size ? &(a).ptr[--(a).size] : (void *)NULL)
78              
79             #define git_array_get(a, i) (((i) < (a).size) ? &(a).ptr[(i)] : (void *)NULL)
80              
81             #define git_array_size(a) (a).size
82              
83             #define git_array_valid_index(a, i) ((i) < (a).size)
84              
85             #define git_array_foreach(a, i, element) \
86             for ((i) = 0; (i) < (a).size && ((element) = &(a).ptr[(i)]); (i)++)
87              
88             GIT_INLINE(int) git_array__search(
89             size_t *out,
90             void *array_ptr,
91             size_t item_size,
92             size_t array_len,
93             int (*compare)(const void *, const void *),
94             const void *key)
95             {
96             size_t lim;
97             unsigned char *part, *array = array_ptr, *base = array_ptr;
98             int cmp = -1;
99              
100             for (lim = array_len; lim != 0; lim >>= 1) {
101             part = base + (lim >> 1) * item_size;
102             cmp = (*compare)(key, part);
103              
104             if (cmp == 0) {
105             base = part;
106             break;
107             }
108             if (cmp > 0) { /* key > p; take right partition */
109             base = part + 1 * item_size;
110             lim--;
111             } /* else take left partition */
112             }
113              
114             if (out)
115             *out = (base - array) / item_size;
116              
117             return (cmp == 0) ? 0 : GIT_ENOTFOUND;
118             }
119              
120             #define git_array_search(out, a, cmp, key) \
121             git_array__search(out, (a).ptr, sizeof(*(a).ptr), (a).size, \
122             (cmp), (key))
123              
124             #endif