forked from smacker/go-tree-sitter
-
Notifications
You must be signed in to change notification settings - Fork 0
/
array.h
249 lines (208 loc) · 8.47 KB
/
array.h
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
#ifndef TREE_SITTER_ARRAY_H_
#define TREE_SITTER_ARRAY_H_
#ifdef __cplusplus
extern "C" {
#endif
#include <string.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>
#include <stdbool.h>
#include "./alloc.h"
#define Array(T) \
struct { \
T *contents; \
uint32_t size; \
uint32_t capacity; \
}
#define array_init(self) \
((self)->size = 0, (self)->capacity = 0, (self)->contents = NULL)
#define array_new() \
{ NULL, 0, 0 }
#define array_get(self, _index) \
(assert((uint32_t)(_index) < (self)->size), &(self)->contents[_index])
#define array_front(self) array_get(self, 0)
#define array_back(self) array_get(self, (self)->size - 1)
#define array_clear(self) ((self)->size = 0)
#define array_reserve(self, new_capacity) \
array__reserve((VoidArray *)(self), array__elem_size(self), new_capacity)
// Free any memory allocated for this array.
#define array_delete(self) array__delete((VoidArray *)(self))
#define array_push(self, element) \
(array__grow((VoidArray *)(self), 1, array__elem_size(self)), \
(self)->contents[(self)->size++] = (element))
// Increase the array's size by a given number of elements, reallocating
// if necessary. New elements are zero-initialized.
#define array_grow_by(self, count) \
(array__grow((VoidArray *)(self), count, array__elem_size(self)), \
memset((self)->contents + (self)->size, 0, (count) * array__elem_size(self)), \
(self)->size += (count))
#define array_push_all(self, other) \
array_extend((self), (other)->size, (other)->contents)
// Append `count` elements to the end of the array, reading their values from the
// `contents` pointer.
#define array_extend(self, count, contents) \
array__splice( \
(VoidArray *)(self), array__elem_size(self), (self)->size, \
0, count, contents \
)
// Remove `old_count` elements from the array starting at the given `index`. At
// the same index, insert `new_count` new elements, reading their values from the
// `new_contents` pointer.
#define array_splice(self, _index, old_count, new_count, new_contents) \
array__splice( \
(VoidArray *)(self), array__elem_size(self), _index, \
old_count, new_count, new_contents \
)
// Insert one `element` into the array at the given `index`.
#define array_insert(self, _index, element) \
array__splice((VoidArray *)(self), array__elem_size(self), _index, 0, 1, &(element))
// Remove one `element` from the array at the given `index`.
#define array_erase(self, _index) \
array__erase((VoidArray *)(self), array__elem_size(self), _index)
#define array_pop(self) ((self)->contents[--(self)->size])
#define array_assign(self, other) \
array__assign((VoidArray *)(self), (const VoidArray *)(other), array__elem_size(self))
#define array_swap(self, other) \
array__swap((VoidArray *)(self), (VoidArray *)(other))
// Search a sorted array for a given `needle` value, using the given `compare`
// callback to determine the order.
//
// If an existing element is found to be equal to `needle`, then the `index`
// out-parameter is set to the existing value's index, and the `exists`
// out-parameter is set to true. Otherwise, `index` is set to an index where
// `needle` should be inserted in order to preserve the sorting, and `exists`
// is set to false.
#define array_search_sorted_with(self, compare, needle, _index, _exists) \
array__search_sorted(self, 0, compare, , needle, _index, _exists)
// Search a sorted array for a given `needle` value, using integer comparisons
// of a given struct field (specified with a leading dot) to determine the order.
//
// See also `array_search_sorted_with`.
#define array_search_sorted_by(self, field, needle, _index, _exists) \
array__search_sorted(self, 0, compare_int, field, needle, _index, _exists)
// Insert a given `value` into a sorted array, using the given `compare`
// callback to determine the order.
#define array_insert_sorted_with(self, compare, value) \
do { \
unsigned _index, _exists; \
array_search_sorted_with(self, compare, &(value), &_index, &_exists); \
if (!_exists) array_insert(self, _index, value); \
} while (0)
// Insert a given `value` into a sorted array, using integer comparisons of
// a given struct field (specified with a leading dot) to determine the order.
//
// See also `array_search_sorted_by`.
#define array_insert_sorted_by(self, field, value) \
do { \
unsigned _index, _exists; \
array_search_sorted_by(self, field, (value) field, &_index, &_exists); \
if (!_exists) array_insert(self, _index, value); \
} while (0)
// Private
typedef Array(void) VoidArray;
#define array__elem_size(self) sizeof(*(self)->contents)
static inline void array__delete(VoidArray *self) {
if (self->contents) {
ts_free(self->contents);
self->contents = NULL;
self->size = 0;
self->capacity = 0;
}
}
static inline void array__erase(VoidArray *self, size_t element_size,
uint32_t index) {
assert(index < self->size);
char *contents = (char *)self->contents;
memmove(contents + index * element_size, contents + (index + 1) * element_size,
(self->size - index - 1) * element_size);
self->size--;
}
static inline void array__reserve(VoidArray *self, size_t element_size, uint32_t new_capacity) {
if (new_capacity > self->capacity) {
if (self->contents) {
self->contents = ts_realloc(self->contents, new_capacity * element_size);
} else {
self->contents = ts_malloc(new_capacity * element_size);
}
self->capacity = new_capacity;
}
}
static inline void array__assign(VoidArray *self, const VoidArray *other, size_t element_size) {
array__reserve(self, element_size, other->size);
self->size = other->size;
memcpy(self->contents, other->contents, self->size * element_size);
}
static inline void array__swap(VoidArray *self, VoidArray *other) {
VoidArray swap = *other;
*other = *self;
*self = swap;
}
static inline void array__grow(VoidArray *self, uint32_t count, size_t element_size) {
uint32_t new_size = self->size + count;
if (new_size > self->capacity) {
uint32_t new_capacity = self->capacity * 2;
if (new_capacity < 8) new_capacity = 8;
if (new_capacity < new_size) new_capacity = new_size;
array__reserve(self, element_size, new_capacity);
}
}
static inline void array__splice(VoidArray *self, size_t element_size,
uint32_t index, uint32_t old_count,
uint32_t new_count, const void *elements) {
uint32_t new_size = self->size + new_count - old_count;
uint32_t old_end = index + old_count;
uint32_t new_end = index + new_count;
assert(old_end <= self->size);
array__reserve(self, element_size, new_size);
char *contents = (char *)self->contents;
if (self->size > old_end) {
memmove(
contents + new_end * element_size,
contents + old_end * element_size,
(self->size - old_end) * element_size
);
}
if (new_count > 0) {
if (elements) {
memcpy(
(contents + index * element_size),
elements,
new_count * element_size
);
} else {
memset(
(contents + index * element_size),
0,
new_count * element_size
);
}
}
self->size += new_count - old_count;
}
// A binary search routine, based on Rust's `std::slice::binary_search_by`.
#define array__search_sorted(self, start, compare, suffix, needle, _index, _exists) \
do { \
*(_index) = start; \
*(_exists) = false; \
uint32_t size = (self)->size - *(_index); \
if (size == 0) break; \
int comparison; \
while (size > 1) { \
uint32_t half_size = size / 2; \
uint32_t mid_index = *(_index) + half_size; \
comparison = compare(&((self)->contents[mid_index] suffix), (needle)); \
if (comparison <= 0) *(_index) = mid_index; \
size -= half_size; \
} \
comparison = compare(&((self)->contents[*(_index)] suffix), (needle)); \
if (comparison == 0) *(_exists) = true; \
else if (comparison < 0) *(_index) += 1; \
} while (0)
// Helper macro for the `_sorted_by` routines below. This takes the left (existing)
// parameter by reference in order to work with the generic sorting function above.
#define compare_int(a, b) ((int)*(a) - (int)(b))
#ifdef __cplusplus
}
#endif
#endif // TREE_SITTER_ARRAY_H_