Merge remote-tracking branch 'upstream/master' into floattitlefloattitle

1 files changed, 236 insertions, 0 deletions

diff --git a/src/klib/kvec.h b/src/klib/kvec.h
new file mode 100644
index 0000000000..b5b3adf7d2
--- /dev/null
+++ b/src/klib/kvec.h
@@ -0,0 +1,236 @@
+// The MIT License
+//
+// Copyright (c) 2008, by Attractive Chaos <attractor@live.co.uk>
+//
+// Permission is hereby granted, free of charge, to any person obtaining
+// a copy of this software and associated documentation files (the
+// "Software"), to deal in the Software without restriction, including
+// without limitation the rights to use, copy, modify, merge, publish,
+// distribute, sublicense, and/or sell copies of the Software, and to
+// permit persons to whom the Software is furnished to do so, subject to
+// the following conditions:
+//
+// The above copyright notice and this permission notice shall be
+// included in all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
+// BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
+// ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+// CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+// SOFTWARE.
+
+// An example:
+//
+//     #include "kvec.h"
+//     int main() {
+//       kvec_t(int) array = KV_INITIAL_VALUE;
+//       kv_push(array, 10); // append
+//       kv_a(array, 20) = 5; // dynamic
+//       kv_A(array, 20) = 4; // static
+//       kv_destroy(array);
+//       return 0;
+//     }
+
+#ifndef NVIM_LIB_KVEC_H
+#define NVIM_LIB_KVEC_H
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "nvim/memory.h"
+#include "nvim/os/os_defs.h"
+
+#define kv_roundup32(x) \
+  ((--(x)), \
+   ((x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16), \
+   (++(x)))
+
+#define KV_INITIAL_VALUE { .size = 0, .capacity = 0, .items = NULL }
+
+#define kvec_t(type) \
+  struct { \
+    size_t size; \
+    size_t capacity; \
+    type *items; \
+  }
+
+#define kv_init(v) ((v).size = (v).capacity = 0, (v).items = 0)
+#define kv_destroy(v) \
+  do { \
+    xfree((v).items); \
+    kv_init(v); \
+  } while (0)
+#define kv_A(v, i) ((v).items[(i)])
+#define kv_pop(v) ((v).items[--(v).size])
+#define kv_size(v) ((v).size)
+#define kv_max(v) ((v).capacity)
+#define kv_Z(v, i) kv_A(v, kv_size(v) - (i) - 1)
+#define kv_last(v) kv_Z(v, 0)
+
+/// Drop last n items from kvec without resizing
+///
+/// Previously spelled as `(void)kv_pop(v)`, repeated n times.
+///
+/// @param[out]  v  Kvec to drop items from.
+/// @param[in]  n  Number of elements to drop.
+#define kv_drop(v, n) ((v).size -= (n))
+
+#define kv_resize(v, s) \
+  ((v).capacity = (s), \
+   (v).items = xrealloc((v).items, sizeof((v).items[0]) * (v).capacity))
+
+#define kv_resize_full(v) \
+  kv_resize(v, (v).capacity ? (v).capacity << 1 : 8)
+
+#define kv_copy(v1, v0) \
+  do { \
+    if ((v1).capacity < (v0).size) { \
+      kv_resize(v1, (v0).size); \
+    } \
+    (v1).size = (v0).size; \
+    memcpy((v1).items, (v0).items, sizeof((v1).items[0]) * (v0).size); \
+  } while (0)
+
+/// fit at least "len" more items
+#define kv_ensure_space(v, len) \
+  do { \
+    if ((v).capacity < (v).size + len) { \
+      (v).capacity = (v).size + len; \
+      kv_roundup32((v).capacity); \
+      kv_resize((v), (v).capacity); \
+    } \
+  } while (0)
+
+#define kv_concat_len(v, data, len) \
+  do { \
+    kv_ensure_space(v, len); \
+    memcpy((v).items + (v).size, data, sizeof((v).items[0]) * len); \
+    (v).size = (v).size + len; \
+  } while (0)
+
+#define kv_concat(v, str) kv_concat_len(v, str, STRLEN(str))
+#define kv_splice(v1, v0) kv_concat_len(v1, (v0).items, (v0).size)
+
+#define kv_pushp(v) \
+  ((((v).size == (v).capacity) ? (kv_resize_full(v), 0) : 0), \
+   ((v).items + ((v).size++)))
+
+#define kv_push(v, x) \
+  (*kv_pushp(v) = (x))
+
+#define kv_pushp_c(v) ((v).items + ((v).size++))
+#define kv_push_c(v, x) (*kv_pushp_c(v) = (x))
+
+#define kv_a(v, i) \
+  (*(((v).capacity <= (size_t)(i) \
+      ? ((v).capacity = (v).size = (i) + 1, \
+         kv_roundup32((v).capacity), \
+         kv_resize((v), (v).capacity), 0UL) \
+      : ((v).size <= (size_t)(i) \
+         ? (v).size = (i) + 1 \
+         : 0UL)), \
+     &(v).items[(i)]))
+
+#define kv_printf(v, ...) kv_do_printf(&(v), __VA_ARGS__)
+
+/// Type of a vector with a few first members allocated on stack
+///
+/// Is compatible with #kv_A, #kv_pop, #kv_size, #kv_max, #kv_last.
+/// Is not compatible with #kv_resize, #kv_resize_full, #kv_copy, #kv_push,
+/// #kv_pushp, #kv_a, #kv_destroy.
+///
+/// @param[in]  type  Type of vector elements.
+/// @param[in]  init_size  Number of the elements in the initial array.
+#define kvec_withinit_t(type, INIT_SIZE) \
+  struct { \
+    size_t size; \
+    size_t capacity; \
+    type *items; \
+    type init_array[INIT_SIZE]; \
+  }
+
+/// Initialize vector with preallocated array
+///
+/// @param[out]  v  Vector to initialize.
+#define kvi_init(v) \
+  ((v).capacity = ARRAY_SIZE((v).init_array), \
+   (v).size = 0, \
+   (v).items = (v).init_array)
+
+/// Move data to a new destination and free source
+static inline void *_memcpy_free(void *const restrict dest, void *const restrict src,
+                                 const size_t size)
+  FUNC_ATTR_NONNULL_ALL FUNC_ATTR_NONNULL_RET FUNC_ATTR_ALWAYS_INLINE
+{
+  memcpy(dest, src, size);
+  XFREE_CLEAR(src);
+  return dest;
+}
+
+// -V:kvi_push:512
+
+/// Resize vector with preallocated array
+///
+/// @note May not resize to an array smaller then init_array: if requested,
+///       init_array will be used.
+///
+/// @param[out]  v  Vector to resize.
+/// @param[in]  s  New size.
+#define kvi_resize(v, s) \
+  ((v).capacity = ((s) > ARRAY_SIZE((v).init_array) \
+                     ? (s) \
+                     : ARRAY_SIZE((v).init_array)), \
+   (v).items = ((v).capacity == ARRAY_SIZE((v).init_array) \
+                  ? ((v).items == (v).init_array \
+                     ? (v).items \
+                     : _memcpy_free((v).init_array, (v).items, \
+                                    (v).size * sizeof((v).items[0]))) \
+                     : ((v).items == (v).init_array \
+                     ? memcpy(xmalloc((v).capacity * sizeof((v).items[0])), \
+                              (v).items, \
+                              (v).size * sizeof((v).items[0])) \
+                     : xrealloc((v).items, \
+                                (v).capacity * sizeof((v).items[0])))))
+
+/// Resize vector with preallocated array when it is full
+///
+/// @param[out]  v  Vector to resize.
+#define kvi_resize_full(v) \
+  /* ARRAY_SIZE((v).init_array) is the minimal capacity of this vector. */ \
+  /* Thus when vector is full capacity may not be zero and it is safe */ \
+  /* not to bother with checking whether (v).capacity is 0. But now */ \
+  /* capacity is not guaranteed to have size that is a power of 2, it is */ \
+  /* hard to fix this here and is not very necessary if users will use */ \
+  /* 2^x initial array size. */ \
+  kvi_resize(v, (v).capacity << 1)
+
+/// Get location where to store new element to a vector with preallocated array
+///
+/// @param[in,out]  v  Vector to push to.
+///
+/// @return Pointer to the place where new value should be stored.
+#define kvi_pushp(v) \
+  ((((v).size == (v).capacity) ? (kvi_resize_full(v), 0) : 0), \
+   ((v).items + ((v).size++)))
+
+/// Push value to a vector with preallocated array
+///
+/// @param[out]  v  Vector to push to.
+/// @param[in]  x  Value to push.
+#define kvi_push(v, x) \
+  (*kvi_pushp(v) = (x))
+
+/// Free array of elements of a vector with preallocated array if needed
+///
+/// @param[out]  v  Vector to free.
+#define kvi_destroy(v) \
+  do { \
+    if ((v).items != (v).init_array) { \
+      XFREE_CLEAR((v).items); \
+    } \
+  } while (0)
+
+#endif  // NVIM_LIB_KVEC_H