kvec.h (9025B)
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 /// fit at least "len" more items 98 #define kv_ensure_space(v, len) \ 99 do { \ 100 if ((v).capacity < (v).size + len) { \ 101 (v).capacity = (v).size + len; \ 102 kv_roundup32((v).capacity); \ 103 kv_resize((v), (v).capacity); \ 104 } \ 105 } while (0) 106 107 #define kv_concat_len(v, data, len) \ 108 if (len > 0) { \ 109 kv_ensure_space(v, len); \ 110 assert((v).items); \ 111 memcpy((v).items + (v).size, data, sizeof((v).items[0]) * len); \ 112 (v).size = (v).size + len; \ 113 } 114 115 #define kv_concat(v, str) kv_concat_len(v, str, strlen(str)) 116 #define kv_splice(v1, v0) kv_concat_len(v1, (v0).items, (v0).size) 117 118 #define kv_pushp(v) \ 119 ((((v).size == (v).capacity) ? (kv_resize_full(v), 0) : 0), \ 120 ((v).items + ((v).size++))) 121 122 #define kv_push(v, x) \ 123 (*kv_pushp(v) = (x)) 124 125 #define kv_pushp_c(v) ((v).items + ((v).size++)) 126 #define kv_push_c(v, x) (*kv_pushp_c(v) = (x)) 127 128 #define kv_a(v, i) \ 129 (*(((v).capacity <= (size_t)(i) \ 130 ? ((v).capacity = (v).size = (i) + 1, \ 131 kv_roundup32((v).capacity), \ 132 kv_resize((v), (v).capacity), 0UL) \ 133 : ((v).size <= (size_t)(i) \ 134 ? (v).size = (i) + 1 \ 135 : 0UL)), \ 136 &(v).items[(i)])) 137 138 #define kv_shift(v, i, n) ((v).size -= (n), (i) < (v).size \ 139 && memmove(&kv_A(v, (i)), &kv_A(v, (i)+(n)), \ 140 ((v).size-(i))*sizeof(kv_A(v, i)))) 141 142 /// Type of a vector with a few first members allocated on stack 143 /// 144 /// Is compatible with #kv_A, #kv_pop, #kv_size, #kv_max, #kv_last. 145 /// Is not compatible with #kv_resize, #kv_resize_full, #kv_copy, #kv_push, 146 /// #kv_pushp, #kv_a, #kv_destroy. 147 /// 148 /// @param[in] type Type of vector elements. 149 /// @param[in] init_size Number of the elements in the initial array. 150 #define kvec_withinit_t(type, INIT_SIZE) \ 151 struct { \ 152 size_t size; \ 153 size_t capacity; \ 154 type *items; \ 155 type init_array[INIT_SIZE]; \ 156 } 157 158 #define KVI_INITIAL_VALUE(v) { \ 159 .size = 0, \ 160 .capacity = ARRAY_SIZE((v).init_array), \ 161 .items = (v).init_array \ 162 } 163 164 /// Initialize vector with preallocated array 165 /// 166 /// @param[out] v Vector to initialize. 167 #define kvi_init(v) \ 168 ((v).capacity = ARRAY_SIZE((v).init_array), \ 169 (v).size = 0, \ 170 (v).items = (v).init_array) 171 172 static inline void *_memcpy_free(void *restrict dest, void *restrict src, size_t size) 173 REAL_FATTR_NONNULL_ALL REAL_FATTR_NONNULL_RET REAL_FATTR_ALWAYS_INLINE; 174 175 /// Move data to a new destination and free source 176 static inline void *_memcpy_free(void *const restrict dest, void *const restrict src, 177 const size_t size) 178 { 179 memcpy(dest, src, size); 180 XFREE_CLEAR(src); 181 return dest; 182 } 183 184 /// Resize vector with preallocated array 185 /// 186 /// @note May not resize to an array smaller then init_array: if requested, 187 /// init_array will be used. 188 /// 189 /// @param[out] v Vector to resize. 190 /// @param[in] s New size. 191 #define kvi_resize(v, s) \ 192 ((v).capacity = ((s) > ARRAY_SIZE((v).init_array) \ 193 ? (s) \ 194 : ARRAY_SIZE((v).init_array)), \ 195 (v).items = ((v).capacity == ARRAY_SIZE((v).init_array) \ 196 ? ((v).items == (v).init_array \ 197 ? (v).items \ 198 : _memcpy_free((v).init_array, (v).items, \ 199 (v).size * sizeof((v).items[0]))) \ 200 : ((v).items == (v).init_array \ 201 ? memcpy(xmalloc((v).capacity * sizeof((v).items[0])), \ 202 (v).items, \ 203 (v).size * sizeof((v).items[0])) \ 204 : xrealloc((v).items, \ 205 (v).capacity * sizeof((v).items[0]))))) 206 207 /// Resize vector with preallocated array when it is full 208 /// 209 /// @param[out] v Vector to resize. 210 #define kvi_resize_full(v) \ 211 /* ARRAY_SIZE((v).init_array) is the minimal capacity of this vector. */ \ 212 /* Thus when vector is full capacity may not be zero and it is safe */ \ 213 /* not to bother with checking whether (v).capacity is 0. But now */ \ 214 /* capacity is not guaranteed to have size that is a power of 2, it is */ \ 215 /* hard to fix this here and is not very necessary if users will use */ \ 216 /* 2^x initial array size. */ \ 217 kvi_resize(v, (v).capacity << 1) 218 219 /// fit at least "len" more items 220 #define kvi_ensure_more_space(v, len) \ 221 do { \ 222 if ((v).capacity < (v).size + len) { \ 223 (v).capacity = (v).size + len; \ 224 kv_roundup32((v).capacity); \ 225 kvi_resize((v), (v).capacity); \ 226 } \ 227 } while (0) 228 229 #define kvi_concat_len(v, data, len) \ 230 if (len > 0) { \ 231 kvi_ensure_more_space(v, len); \ 232 assert((v).items); \ 233 memcpy((v).items + (v).size, data, sizeof((v).items[0]) * len); \ 234 (v).size = (v).size + len; \ 235 } 236 237 #define kvi_concat(v, str) kvi_concat_len(v, str, strlen(str)) 238 #define kvi_splice(v1, v0) kvi_concat_len(v1, (v0).items, (v0).size) 239 240 /// Get location where to store new element to a vector with preallocated array 241 /// 242 /// @param[in,out] v Vector to push to. 243 /// 244 /// @return Pointer to the place where new value should be stored. 245 #define kvi_pushp(v) \ 246 ((((v).size == (v).capacity) ? (kvi_resize_full(v), 0) : 0), \ 247 ((v).items + ((v).size++))) 248 249 /// Push value to a vector with preallocated array 250 /// 251 /// @param[out] v Vector to push to. 252 /// @param[in] x Value to push. 253 #define kvi_push(v, x) \ 254 (*kvi_pushp(v) = (x)) 255 256 /// Copy a vector to a preallocated vector 257 /// 258 /// @param[out] v1 destination 259 /// @param[in] v0 source (can be either vector or preallocated vector) 260 #define kvi_copy(v1, v0) \ 261 do { \ 262 if ((v1).capacity < (v0).size) { \ 263 kvi_resize(v1, (v0).size); \ 264 } \ 265 (v1).size = (v0).size; \ 266 memcpy((v1).items, (v0).items, sizeof((v1).items[0]) * (v0).size); \ 267 } while (0) 268 269 /// Free array of elements of a vector with preallocated array if needed 270 /// 271 /// @param[out] v Vector to free. 272 #define kvi_destroy(v) \ 273 do { \ 274 if ((v).items != (v).init_array) { \ 275 XFREE_CLEAR((v).items); \ 276 } \ 277 } while (0) 278 279 #endif // NVIM_LIB_KVEC_H