1#ifndef TREE_SITTER_ARRAY_H_
  2#define TREE_SITTER_ARRAY_H_
  3
  4#ifdef __cplusplus
  5extern "C" {
  6#endif
  7
  8#include "./alloc.h"
  9
 10#include <assert.h>
 11#include <stdbool.h>
 12#include <stdint.h>
 13#include <stdlib.h>
 14#include <string.h>
 15
 16#ifdef _MSC_VER
 17#pragma warning(disable : 4101)
 18#elif defined(__GNUC__) || defined(__clang__)
 19#pragma GCC diagnostic push
 20#pragma GCC diagnostic ignored "-Wunused-variable"
 21#endif
 22
 23#define Array(T)       \
 24  struct {             \
 25    T *contents;       \
 26    uint32_t size;     \
 27    uint32_t capacity; \
 28  }
 29
 30/// Initialize an array.
 31#define array_init(self) \
 32  ((self)->size = 0, (self)->capacity = 0, (self)->contents = NULL)
 33
 34/// Create an empty array.
 35#define array_new() \
 36  { NULL, 0, 0 }
 37
 38/// Get a pointer to the element at a given `index` in the array.
 39#define array_get(self, _index) \
 40  (assert((uint32_t)(_index) < (self)->size), &(self)->contents[_index])
 41
 42/// Get a pointer to the first element in the array.
 43#define array_front(self) array_get(self, 0)
 44
 45/// Get a pointer to the last element in the array.
 46#define array_back(self) array_get(self, (self)->size - 1)
 47
 48/// Clear the array, setting its size to zero. Note that this does not free any
 49/// memory allocated for the array's contents.
 50#define array_clear(self) ((self)->size = 0)
 51
 52/// Reserve `new_capacity` elements of space in the array. If `new_capacity` is
 53/// less than the array's current capacity, this function has no effect.
 54#define array_reserve(self, new_capacity) \
 55  _array__reserve((Array *)(self), array_elem_size(self), new_capacity)
 56
 57/// Free any memory allocated for this array. Note that this does not free any
 58/// memory allocated for the array's contents.
 59#define array_delete(self) _array__delete((Array *)(self))
 60
 61/// Push a new `element` onto the end of the array.
 62#define array_push(self, element)                            \
 63  (_array__grow((Array *)(self), 1, array_elem_size(self)), \
 64   (self)->contents[(self)->size++] = (element))
 65
 66/// Increase the array's size by `count` elements.
 67/// New elements are zero-initialized.
 68#define array_grow_by(self, count) \
 69  do { \
 70    if ((count) == 0) break; \
 71    _array__grow((Array *)(self), count, array_elem_size(self)); \
 72    memset((self)->contents + (self)->size, 0, (count) * array_elem_size(self)); \
 73    (self)->size += (count); \
 74  } while (0)
 75
 76/// Append all elements from one array to the end of another.
 77#define array_push_all(self, other)                                       \
 78  array_extend((self), (other)->size, (other)->contents)
 79
 80/// Append `count` elements to the end of the array, reading their values from the
 81/// `contents` pointer.
 82#define array_extend(self, count, contents)                    \
 83  _array__splice(                                               \
 84    (Array *)(self), array_elem_size(self), (self)->size, \
 85    0, count,  contents                                        \
 86  )
 87
 88/// Remove `old_count` elements from the array starting at the given `index`. At
 89/// the same index, insert `new_count` new elements, reading their values from the
 90/// `new_contents` pointer.
 91#define array_splice(self, _index, old_count, new_count, new_contents)  \
 92  _array__splice(                                                       \
 93    (Array *)(self), array_elem_size(self), _index,                \
 94    old_count, new_count, new_contents                                 \
 95  )
 96
 97/// Insert one `element` into the array at the given `index`.
 98#define array_insert(self, _index, element) \
 99  _array__splice((Array *)(self), array_elem_size(self), _index, 0, 1, &(element))
100
101/// Remove one element from the array at the given `index`.
102#define array_erase(self, _index) \
103  _array__erase((Array *)(self), array_elem_size(self), _index)
104
105/// Pop the last element off the array, returning the element by value.
106#define array_pop(self) ((self)->contents[--(self)->size])
107
108/// Assign the contents of one array to another, reallocating if necessary.
109#define array_assign(self, other) \
110  _array__assign((Array *)(self), (const Array *)(other), array_elem_size(self))
111
112/// Swap one array with another
113#define array_swap(self, other) \
114  _array__swap((Array *)(self), (Array *)(other))
115
116/// Get the size of the array contents
117#define array_elem_size(self) (sizeof *(self)->contents)
118
119/// Search a sorted array for a given `needle` value, using the given `compare`
120/// callback to determine the order.
121///
122/// If an existing element is found to be equal to `needle`, then the `index`
123/// out-parameter is set to the existing value's index, and the `exists`
124/// out-parameter is set to true. Otherwise, `index` is set to an index where
125/// `needle` should be inserted in order to preserve the sorting, and `exists`
126/// is set to false.
127#define array_search_sorted_with(self, compare, needle, _index, _exists) \
128  _array__search_sorted(self, 0, compare, , needle, _index, _exists)
129
130/// Search a sorted array for a given `needle` value, using integer comparisons
131/// of a given struct field (specified with a leading dot) to determine the order.
132///
133/// See also `array_search_sorted_with`.
134#define array_search_sorted_by(self, field, needle, _index, _exists) \
135  _array__search_sorted(self, 0, _compare_int, field, needle, _index, _exists)
136
137/// Insert a given `value` into a sorted array, using the given `compare`
138/// callback to determine the order.
139#define array_insert_sorted_with(self, compare, value) \
140  do { \
141    unsigned _index, _exists; \
142    array_search_sorted_with(self, compare, &(value), &_index, &_exists); \
143    if (!_exists) array_insert(self, _index, value); \
144  } while (0)
145
146/// Insert a given `value` into a sorted array, using integer comparisons of
147/// a given struct field (specified with a leading dot) to determine the order.
148///
149/// See also `array_search_sorted_by`.
150#define array_insert_sorted_by(self, field, value) \
151  do { \
152    unsigned _index, _exists; \
153    array_search_sorted_by(self, field, (value) field, &_index, &_exists); \
154    if (!_exists) array_insert(self, _index, value); \
155  } while (0)
156
157// Private
158
159typedef Array(void) Array;
160
161/// This is not what you're looking for, see `array_delete`.
162static inline void _array__delete(Array *self) {
163  if (self->contents) {
164    ts_free(self->contents);
165    self->contents = NULL;
166    self->size = 0;
167    self->capacity = 0;
168  }
169}
170
171/// This is not what you're looking for, see `array_erase`.
172static inline void _array__erase(Array *self, size_t element_size,
173                                uint32_t index) {
174  assert(index < self->size);
175  char *contents = (char *)self->contents;
176  memmove(contents + index * element_size, contents + (index + 1) * element_size,
177          (self->size - index - 1) * element_size);
178  self->size--;
179}
180
181/// This is not what you're looking for, see `array_reserve`.
182static inline void _array__reserve(Array *self, size_t element_size, uint32_t new_capacity) {
183  if (new_capacity > self->capacity) {
184    if (self->contents) {
185      self->contents = ts_realloc(self->contents, new_capacity * element_size);
186    } else {
187      self->contents = ts_malloc(new_capacity * element_size);
188    }
189    self->capacity = new_capacity;
190  }
191}
192
193/// This is not what you're looking for, see `array_assign`.
194static inline void _array__assign(Array *self, const Array *other, size_t element_size) {
195  _array__reserve(self, element_size, other->size);
196  self->size = other->size;
197  memcpy(self->contents, other->contents, self->size * element_size);
198}
199
200/// This is not what you're looking for, see `array_swap`.
201static inline void _array__swap(Array *self, Array *other) {
202  Array swap = *other;
203  *other = *self;
204  *self = swap;
205}
206
207/// This is not what you're looking for, see `array_push` or `array_grow_by`.
208static inline void _array__grow(Array *self, uint32_t count, size_t element_size) {
209  uint32_t new_size = self->size + count;
210  if (new_size > self->capacity) {
211    uint32_t new_capacity = self->capacity * 2;
212    if (new_capacity < 8) new_capacity = 8;
213    if (new_capacity < new_size) new_capacity = new_size;
214    _array__reserve(self, element_size, new_capacity);
215  }
216}
217
218/// This is not what you're looking for, see `array_splice`.
219static inline void _array__splice(Array *self, size_t element_size,
220                                 uint32_t index, uint32_t old_count,
221                                 uint32_t new_count, const void *elements) {
222  uint32_t new_size = self->size + new_count - old_count;
223  uint32_t old_end = index + old_count;
224  uint32_t new_end = index + new_count;
225  assert(old_end <= self->size);
226
227  _array__reserve(self, element_size, new_size);
228
229  char *contents = (char *)self->contents;
230  if (self->size > old_end) {
231    memmove(
232      contents + new_end * element_size,
233      contents + old_end * element_size,
234      (self->size - old_end) * element_size
235    );
236  }
237  if (new_count > 0) {
238    if (elements) {
239      memcpy(
240        (contents + index * element_size),
241        elements,
242        new_count * element_size
243      );
244    } else {
245      memset(
246        (contents + index * element_size),
247        0,
248        new_count * element_size
249      );
250    }
251  }
252  self->size += new_count - old_count;
253}
254
255/// A binary search routine, based on Rust's `std::slice::binary_search_by`.
256/// This is not what you're looking for, see `array_search_sorted_with` or `array_search_sorted_by`.
257#define _array__search_sorted(self, start, compare, suffix, needle, _index, _exists) \
258  do { \
259    *(_index) = start; \
260    *(_exists) = false; \
261    uint32_t size = (self)->size - *(_index); \
262    if (size == 0) break; \
263    int comparison; \
264    while (size > 1) { \
265      uint32_t half_size = size / 2; \
266      uint32_t mid_index = *(_index) + half_size; \
267      comparison = compare(&((self)->contents[mid_index] suffix), (needle)); \
268      if (comparison <= 0) *(_index) = mid_index; \
269      size -= half_size; \
270    } \
271    comparison = compare(&((self)->contents[*(_index)] suffix), (needle)); \
272    if (comparison == 0) *(_exists) = true; \
273    else if (comparison < 0) *(_index) += 1; \
274  } while (0)
275
276/// Helper macro for the `_sorted_by` routines below. This takes the left (existing)
277/// parameter by reference in order to work with the generic sorting function above.
278#define _compare_int(a, b) ((int)*(a) - (int)(b))
279
280#ifdef _MSC_VER
281#pragma warning(default : 4101)
282#elif defined(__GNUC__) || defined(__clang__)
283#pragma GCC diagnostic pop
284#endif
285
286#ifdef __cplusplus
287}
288#endif
289
290#endif  // TREE_SITTER_ARRAY_H_