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