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 "common.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 so this can return the new item */
git_array_grow(void * _a,size_t item_size)45 GIT_INLINE(void *) git_array_grow(void *_a, size_t item_size)
46 {
47 volatile git_array_generic_t *a = _a;
48 size_t new_size;
49 char *new_array;
50
51 if (a->size < 8) {
52 new_size = 8;
53 } else {
54 if (GIT_MULTIPLY_SIZET_OVERFLOW(&new_size, a->size, 3))
55 goto on_oom;
56 new_size /= 2;
57 }
58
59 if ((new_array = git__reallocarray(a->ptr, new_size, item_size)) == NULL)
60 goto on_oom;
61
62 a->ptr = new_array; a->asize = new_size; a->size++;
63 return a->ptr + (a->size - 1) * item_size;
64
65 on_oom:
66 git_array_clear(*a);
67 return NULL;
68 }
69
70 #define git_array_alloc(a) \
71 (((a).size >= (a).asize) ? \
72 git_array_grow(&(a), sizeof(*(a).ptr)) : \
73 ((a).ptr ? &(a).ptr[(a).size++] : NULL))
74
75 #define git_array_last(a) ((a).size ? &(a).ptr[(a).size - 1] : NULL)
76
77 #define git_array_pop(a) ((a).size ? &(a).ptr[--(a).size] : NULL)
78
79 #define git_array_get(a, i) (((i) < (a).size) ? &(a).ptr[(i)] : 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
git_array__search(size_t * out,void * array_ptr,size_t item_size,size_t array_len,int (* compare)(const void *,const void *),const void * key)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
125