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 |
139 | static 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 | |