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
130
|
/*
* 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)
GIT_INLINE(void *) git_array__alloc(void *arr, size_t *size, size_t *asize, size_t item_size)
{
size_t new_size;
void *new_array;
if (*size < *asize)
return arr;
if (*size < 8) {
new_size = 8;
} else {
if (GIT_MULTIPLY_SIZET_OVERFLOW(&new_size, *asize, 3))
goto on_oom;
new_size /= 2;
}
if ((new_array = git__reallocarray(arr, new_size, item_size)) == NULL)
goto on_oom;
*asize = new_size;
return new_array;
on_oom:
git__free(arr);
*size = 0;
*asize = 0;
return NULL;
}
#define git_array_alloc(a) \
(((a).size < (a).asize || \
((a).ptr = git_array__alloc((a).ptr, &(a).size, &(a).asize, sizeof(*(a).ptr))) != NULL) ? &(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
|
