1// The MIT License
2//
3// Copyright (c) 2008, by Attractive Chaos <attractor@live.co.uk>
4//
5// Permission is hereby granted, free of charge, to any person obtaining
6// a copy of this software and associated documentation files (the
7// "Software"), to deal in the Software without restriction, including
8// without limitation the rights to use, copy, modify, merge, publish,
9// distribute, sublicense, and/or sell copies of the Software, and to
10// permit persons to whom the Software is furnished to do so, subject to
11// the following conditions:
12//
13// The above copyright notice and this permission notice shall be
14// included in all copies or substantial portions of the Software.
15//
16// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
19// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
20// BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
21// ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
22// CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
23// SOFTWARE.
24
25// An example:
26//
27// #include "kvec.h"
28// int main() {
29// kvec_t(int) array = KV_INITIAL_VALUE;
30// kv_push(array, 10); // append
31// kv_a(array, 20) = 5; // dynamic
32// kv_A(array, 20) = 4; // static
33// kv_destroy(array);
34// return 0;
35// }
36
37#ifndef NVIM_LIB_KVEC_H
38#define NVIM_LIB_KVEC_H
39
40#include <stdlib.h>
41#include <string.h>
42
43#include "nvim/memory.h"
44#include "nvim/os/os_defs.h"
45
46#define kv_roundup32(x) \
47 ((--(x)), \
48 ((x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16), \
49 (++(x)))
50
51#define KV_INITIAL_VALUE { .size = 0, .capacity = 0, .items = NULL }
52
53#define kvec_t(type) \
54 struct { \
55 size_t size; \
56 size_t capacity; \
57 type *items; \
58 }
59
60#define kv_init(v) ((v).size = (v).capacity = 0, (v).items = 0)
61#define kv_destroy(v) \
62 do { \
63 xfree((v).items); \
64 kv_init(v); \
65 } while (0)
66#define kv_A(v, i) ((v).items[(i)])
67#define kv_pop(v) ((v).items[--(v).size])
68#define kv_size(v) ((v).size)
69#define kv_max(v) ((v).capacity)
70#define kv_Z(v, i) kv_A(v, kv_size(v) - (i) - 1)
71#define kv_last(v) kv_Z(v, 0)
72
73/// Drop last n items from kvec without resizing
74///
75/// Previously spelled as `(void)kv_pop(v)`, repeated n times.
76///
77/// @param[out] v Kvec to drop items from.
78/// @param[in] n Number of elements to drop.
79#define kv_drop(v, n) ((v).size -= (n))
80
81#define kv_resize(v, s) \
82 ((v).capacity = (s), \
83 (v).items = xrealloc((v).items, sizeof((v).items[0]) * (v).capacity))
84
85#define kv_resize_full(v) \
86 kv_resize(v, (v).capacity ? (v).capacity << 1 : 8)
87
88#define kv_copy(v1, v0) \
89 do { \
90 if ((v1).capacity < (v0).size) { \
91 kv_resize(v1, (v0).size); \
92 } \
93 (v1).size = (v0).size; \
94 memcpy((v1).items, (v0).items, sizeof((v1).items[0]) * (v0).size); \
95 } while (0)
96
97#define kv_pushp(v) \
98 ((((v).size == (v).capacity) ? (kv_resize_full(v), 0) : 0), \
99 ((v).items + ((v).size++)))
100
101#define kv_push(v, x) \
102 (*kv_pushp(v) = (x))
103
104#define kv_a(v, i) \
105 (*(((v).capacity <= (size_t) (i) \
106 ? ((v).capacity = (v).size = (i) + 1, \
107 kv_roundup32((v).capacity), \
108 kv_resize((v), (v).capacity), 0UL) \
109 : ((v).size <= (size_t) (i) \
110 ? (v).size = (i) + 1 \
111 : 0UL)), \
112 &(v).items[(i)]))
113
114/// Type of a vector with a few first members allocated on stack
115///
116/// Is compatible with #kv_A, #kv_pop, #kv_size, #kv_max, #kv_last.
117/// Is not compatible with #kv_resize, #kv_resize_full, #kv_copy, #kv_push,
118/// #kv_pushp, #kv_a, #kv_destroy.
119///
120/// @param[in] type Type of vector elements.
121/// @param[in] init_size Number of the elements in the initial array.
122#define kvec_withinit_t(type, INIT_SIZE) \
123 struct { \
124 size_t size; \
125 size_t capacity; \
126 type *items; \
127 type init_array[INIT_SIZE]; \
128 }
129
130/// Initialize vector with preallocated array
131///
132/// @param[out] v Vector to initialize.
133#define kvi_init(v) \
134 ((v).capacity = ARRAY_SIZE((v).init_array), \
135 (v).size = 0, \
136 (v).items = (v).init_array)
137
138/// Move data to a new destination and free source
139static inline void *_memcpy_free(void *const restrict dest,
140 void *const restrict src,
141 const size_t size)
142 FUNC_ATTR_NONNULL_ALL FUNC_ATTR_NONNULL_RET FUNC_ATTR_ALWAYS_INLINE
143{
144 memcpy(dest, src, size);
145 XFREE_CLEAR(src);
146 return dest;
147}
148
149// -V:kvi_push:512
150
151/// Resize vector with preallocated array
152///
153/// @note May not resize to an array smaller then init_array: if requested,
154/// init_array will be used.
155///
156/// @param[out] v Vector to resize.
157/// @param[in] s New size.
158#define kvi_resize(v, s) \
159 ((v).capacity = ((s) > ARRAY_SIZE((v).init_array) \
160 ? (s) \
161 : ARRAY_SIZE((v).init_array)), \
162 (v).items = ((v).capacity == ARRAY_SIZE((v).init_array) \
163 ? ((v).items == (v).init_array \
164 ? (v).items \
165 : _memcpy_free((v).init_array, (v).items, \
166 (v).size * sizeof((v).items[0]))) \
167 : ((v).items == (v).init_array \
168 ? memcpy(xmalloc((v).capacity * sizeof((v).items[0])), \
169 (v).items, \
170 (v).size * sizeof((v).items[0])) \
171 : xrealloc((v).items, \
172 (v).capacity * sizeof((v).items[0])))))
173
174/// Resize vector with preallocated array when it is full
175///
176/// @param[out] v Vector to resize.
177#define kvi_resize_full(v) \
178 /* ARRAY_SIZE((v).init_array) is the minimal capacity of this vector. */ \
179 /* Thus when vector is full capacity may not be zero and it is safe */ \
180 /* not to bother with checking whether (v).capacity is 0. But now */ \
181 /* capacity is not guaranteed to have size that is a power of 2, it is */ \
182 /* hard to fix this here and is not very necessary if users will use */ \
183 /* 2^x initial array size. */ \
184 kvi_resize(v, (v).capacity << 1)
185
186/// Get location where to store new element to a vector with preallocated array
187///
188/// @param[in,out] v Vector to push to.
189///
190/// @return Pointer to the place where new value should be stored.
191#define kvi_pushp(v) \
192 ((((v).size == (v).capacity) ? (kvi_resize_full(v), 0) : 0), \
193 ((v).items + ((v).size++)))
194
195/// Push value to a vector with preallocated array
196///
197/// @param[out] v Vector to push to.
198/// @param[in] x Value to push.
199#define kvi_push(v, x) \
200 (*kvi_pushp(v) = (x))
201
202/// Free array of elements of a vector with preallocated array if needed
203///
204/// @param[out] v Vector to free.
205#define kvi_destroy(v) \
206 do { \
207 if ((v).items != (v).init_array) { \
208 XFREE_CLEAR((v).items); \
209 } \
210 } while (0)
211
212#endif // NVIM_LIB_KVEC_H
213