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_splice(v1, v0) \
98   do { \
99     if ((v1).capacity < (v1).size + (v0).size) { \
100       (v1).capacity = (v1).size + (v0).size; \
101       kv_roundup32((v1).capacity); \
102       kv_resize((v1), (v1).capacity); \
103     } \
104     memcpy((v1).items + (v1).size, (v0).items, sizeof((v1).items[0]) * (v0).size); \
105     (v1).size = (v1).size + (v0).size; \
106   } while (0)
107 
108 #define kv_pushp(v) \
109   ((((v).size == (v).capacity) ? (kv_resize_full(v), 0) : 0), \
110    ((v).items + ((v).size++)))
111 
112 #define kv_push(v, x) \
113   (*kv_pushp(v) = (x))
114 
115 
116 #define kv_a(v, i) \
117   (*(((v).capacity <= (size_t)(i) \
118       ? ((v).capacity = (v).size = (i) + 1, \
119          kv_roundup32((v).capacity), \
120          kv_resize((v), (v).capacity), 0UL) \
121       : ((v).size <= (size_t)(i) \
122          ? (v).size = (i) + 1 \
123          : 0UL)), \
124      &(v).items[(i)]))
125 
126 /// Type of a vector with a few first members allocated on stack
127 ///
128 /// Is compatible with #kv_A, #kv_pop, #kv_size, #kv_max, #kv_last.
129 /// Is not compatible with #kv_resize, #kv_resize_full, #kv_copy, #kv_push,
130 /// #kv_pushp, #kv_a, #kv_destroy.
131 ///
132 /// @param[in]  type  Type of vector elements.
133 /// @param[in]  init_size  Number of the elements in the initial array.
134 #define kvec_withinit_t(type, INIT_SIZE) \
135   struct { \
136     size_t size; \
137     size_t capacity; \
138     type *items; \
139     type init_array[INIT_SIZE]; \
140   }
141 
142 /// Initialize vector with preallocated array
143 ///
144 /// @param[out]  v  Vector to initialize.
145 #define kvi_init(v) \
146   ((v).capacity = ARRAY_SIZE((v).init_array), \
147    (v).size = 0, \
148    (v).items = (v).init_array)
149 
150 /// Move data to a new destination and free source
_memcpy_free(void * const restrict dest,void * const restrict src,const size_t size)151 static inline void *_memcpy_free(void *const restrict dest, void *const restrict src,
152                                  const size_t size)
153   FUNC_ATTR_NONNULL_ALL FUNC_ATTR_NONNULL_RET FUNC_ATTR_ALWAYS_INLINE
154 {
155   memcpy(dest, src, size);
156   XFREE_CLEAR(src);
157   return dest;
158 }
159 
160 // -V:kvi_push:512
161 
162 /// Resize vector with preallocated array
163 ///
164 /// @note May not resize to an array smaller then init_array: if requested,
165 ///       init_array will be used.
166 ///
167 /// @param[out]  v  Vector to resize.
168 /// @param[in]  s  New size.
169 #define kvi_resize(v, s) \
170   ((v).capacity = ((s) > ARRAY_SIZE((v).init_array) \
171                      ? (s) \
172                      : ARRAY_SIZE((v).init_array)), \
173    (v).items = ((v).capacity == ARRAY_SIZE((v).init_array) \
174                   ? ((v).items == (v).init_array \
175                      ? (v).items \
176                      : _memcpy_free((v).init_array, (v).items, \
177                                     (v).size * sizeof((v).items[0]))) \
178                      : ((v).items == (v).init_array \
179                      ? memcpy(xmalloc((v).capacity * sizeof((v).items[0])), \
180                               (v).items, \
181                               (v).size * sizeof((v).items[0])) \
182                      : xrealloc((v).items, \
183                                 (v).capacity * sizeof((v).items[0])))))
184 
185 /// Resize vector with preallocated array when it is full
186 ///
187 /// @param[out]  v  Vector to resize.
188 #define kvi_resize_full(v) \
189   /* ARRAY_SIZE((v).init_array) is the minimal capacity of this vector. */ \
190   /* Thus when vector is full capacity may not be zero and it is safe */ \
191   /* not to bother with checking whether (v).capacity is 0. But now */ \
192   /* capacity is not guaranteed to have size that is a power of 2, it is */ \
193   /* hard to fix this here and is not very necessary if users will use */ \
194   /* 2^x initial array size. */ \
195   kvi_resize(v, (v).capacity << 1)
196 
197 /// Get location where to store new element to a vector with preallocated array
198 ///
199 /// @param[in,out]  v  Vector to push to.
200 ///
201 /// @return Pointer to the place where new value should be stored.
202 #define kvi_pushp(v) \
203   ((((v).size == (v).capacity) ? (kvi_resize_full(v), 0) : 0), \
204    ((v).items + ((v).size++)))
205 
206 /// Push value to a vector with preallocated array
207 ///
208 /// @param[out]  v  Vector to push to.
209 /// @param[in]  x  Value to push.
210 #define kvi_push(v, x) \
211   (*kvi_pushp(v) = (x))
212 
213 /// Free array of elements of a vector with preallocated array if needed
214 ///
215 /// @param[out]  v  Vector to free.
216 #define kvi_destroy(v) \
217   do { \
218     if ((v).items != (v).init_array) { \
219       XFREE_CLEAR((v).items); \
220     } \
221   } while (0)
222 
223 #endif  // NVIM_LIB_KVEC_H
224