diff options
Diffstat (limited to 'src/nvim/lib')
| -rw-r--r-- | src/nvim/lib/klist.h | 154 | ||||
| -rw-r--r-- | src/nvim/lib/kvec.h | 260 | ||||
| -rw-r--r-- | src/nvim/lib/queue.h | 154 | ||||
| -rw-r--r-- | src/nvim/lib/ringbuf.h | 388 |
4 files changed, 530 insertions, 426 deletions
diff --git a/src/nvim/lib/klist.h b/src/nvim/lib/klist.h index 1280a927e8..7ee100ab8c 100644 --- a/src/nvim/lib/klist.h +++ b/src/nvim/lib/klist.h @@ -33,35 +33,37 @@ #include "nvim/func_attr.h" -#define KMEMPOOL_INIT(name, kmptype_t, kmpfree_f) \ - typedef struct { \ - size_t cnt, n, max; \ - kmptype_t **buf; \ - } kmp_##name##_t; \ - static inline kmp_##name##_t *kmp_init_##name(void) { \ - return xcalloc(1, sizeof(kmp_##name##_t)); \ - } \ - static inline void kmp_destroy_##name(kmp_##name##_t *mp) \ - REAL_FATTR_UNUSED; \ - static inline void kmp_destroy_##name(kmp_##name##_t *mp) { \ - size_t k; \ - for (k = 0; k < mp->n; ++k) { \ - kmpfree_f(mp->buf[k]); xfree(mp->buf[k]); \ - } \ - xfree(mp->buf); xfree(mp); \ - } \ - static inline kmptype_t *kmp_alloc_##name(kmp_##name##_t *mp) { \ - ++mp->cnt; \ - if (mp->n == 0) return xcalloc(1, sizeof(kmptype_t)); \ - return mp->buf[--mp->n]; \ - } \ +#define KMEMPOOL_INIT(name, kmptype_t, kmpfree_f) \ + typedef struct { \ + size_t cnt, n, max; \ + kmptype_t **buf; \ + } kmp_##name##_t; \ + static inline kmp_##name##_t *kmp_init_##name(void) { \ + return xcalloc(1, sizeof(kmp_##name##_t)); \ + } \ + static inline void kmp_destroy_##name(kmp_##name##_t *mp) \ + REAL_FATTR_UNUSED; \ + static inline void kmp_destroy_##name(kmp_##name##_t *mp) { \ + size_t k; \ + for (k = 0; k < mp->n; k++) { \ + kmpfree_f(mp->buf[k]); xfree(mp->buf[k]); \ + } \ + xfree(mp->buf); xfree(mp); \ + } \ + static inline kmptype_t *kmp_alloc_##name(kmp_##name##_t *mp) { \ + mp->cnt++; \ + if (mp->n == 0) { \ + return xcalloc(1, sizeof(kmptype_t)); \ + } \ + return mp->buf[--mp->n]; \ + } \ static inline void kmp_free_##name(kmp_##name##_t *mp, kmptype_t *p) { \ - --mp->cnt; \ - if (mp->n == mp->max) { \ - mp->max = mp->max? mp->max<<1 : 16; \ + mp->cnt--; \ + if (mp->n == mp->max) { \ + mp->max = mp->max ? (mp->max << 1) : 16; \ mp->buf = xrealloc(mp->buf, sizeof(kmptype_t *) * mp->max); \ - } \ - mp->buf[mp->n++] = p; \ + } \ + mp->buf[mp->n++] = p; \ } #define kmempool_t(name) kmp_##name##_t @@ -70,54 +72,56 @@ #define kmp_alloc(name, mp) kmp_alloc_##name(mp) #define kmp_free(name, mp, p) kmp_free_##name(mp, p) -#define KLIST_INIT(name, kltype_t, kmpfree_t) \ - struct __kl1_##name { \ - kltype_t data; \ - struct __kl1_##name *next; \ - }; \ - typedef struct __kl1_##name kl1_##name; \ - KMEMPOOL_INIT(name, kl1_##name, kmpfree_t) \ - typedef struct { \ - kl1_##name *head, *tail; \ - kmp_##name##_t *mp; \ - size_t size; \ - } kl_##name##_t; \ - static inline kl_##name##_t *kl_init_##name(void) { \ - kl_##name##_t *kl = xcalloc(1, sizeof(kl_##name##_t)); \ - kl->mp = kmp_init(name); \ - kl->head = kl->tail = kmp_alloc(name, kl->mp); \ - kl->head->next = 0; \ - return kl; \ - } \ - static inline void kl_destroy_##name(kl_##name##_t *kl) \ - REAL_FATTR_UNUSED; \ - static inline void kl_destroy_##name(kl_##name##_t *kl) { \ - kl1_##name *p; \ - for (p = kl->head; p != kl->tail; p = p->next) \ - kmp_free(name, kl->mp, p); \ - kmp_free(name, kl->mp, p); \ - kmp_destroy(name, kl->mp); \ - xfree(kl); \ - } \ - static inline void kl_push_##name(kl_##name##_t *kl, kltype_t d) { \ - kl1_##name *q, *p = kmp_alloc(name, kl->mp); \ - q = kl->tail; p->next = 0; kl->tail->next = p; kl->tail = p; \ - ++kl->size; \ - q->data = d; \ - } \ - static inline kltype_t kl_shift_at_##name(kl_##name##_t *kl, \ - kl1_##name **n) { \ - assert((*n)->next); \ - kl1_##name *p; \ - --kl->size; \ - p = *n; \ - *n = (*n)->next; \ - if (p == kl->head) kl->head = *n; \ - kltype_t d = p->data; \ - kmp_free(name, kl->mp, p); \ - return d; \ - } \ - +#define KLIST_INIT(name, kltype_t, kmpfree_t) \ + struct __kl1_##name { \ + kltype_t data; \ + struct __kl1_##name *next; \ + }; \ + typedef struct __kl1_##name kl1_##name; \ + KMEMPOOL_INIT(name, kl1_##name, kmpfree_t) \ + typedef struct { \ + kl1_##name *head, *tail; \ + kmp_##name##_t *mp; \ + size_t size; \ + } kl_##name##_t; \ + static inline kl_##name##_t *kl_init_##name(void) { \ + kl_##name##_t *kl = xcalloc(1, sizeof(kl_##name##_t)); \ + kl->mp = kmp_init(name); \ + kl->head = kl->tail = kmp_alloc(name, kl->mp); \ + kl->head->next = 0; \ + return kl; \ + } \ + static inline void kl_destroy_##name(kl_##name##_t *kl) \ + REAL_FATTR_UNUSED; \ + static inline void kl_destroy_##name(kl_##name##_t *kl) { \ + kl1_##name *p; \ + for (p = kl->head; p != kl->tail; p = p->next) { \ + kmp_free(name, kl->mp, p); \ + } \ + kmp_free(name, kl->mp, p); \ + kmp_destroy(name, kl->mp); \ + xfree(kl); \ + } \ + static inline void kl_push_##name(kl_##name##_t *kl, kltype_t d) { \ + kl1_##name *q, *p = kmp_alloc(name, kl->mp); \ + q = kl->tail; p->next = 0; kl->tail->next = p; kl->tail = p; \ + kl->size++; \ + q->data = d; \ + } \ + static inline kltype_t kl_shift_at_##name(kl_##name##_t *kl, \ + kl1_##name **n) { \ + assert((*n)->next); \ + kl1_##name *p; \ + kl->size--; \ + p = *n; \ + *n = (*n)->next; \ + if (p == kl->head) { \ + kl->head = *n; \ + } \ + kltype_t d = p->data; \ + kmp_free(name, kl->mp, p); \ + return d; \ + } #define kliter_t(name) kl1_##name #define klist_t(name) kl_##name##_t diff --git a/src/nvim/lib/kvec.h b/src/nvim/lib/kvec.h index b41ef0cc9f..584282d773 100644 --- a/src/nvim/lib/kvec.h +++ b/src/nvim/lib/kvec.h @@ -1,59 +1,61 @@ -/* 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_init(array); - kv_push(int, array, 10); // append - kv_a(int, array, 20) = 5; // dynamic - kv_A(array, 20) = 4; // static - kv_destroy(array); - return 0; -} -*/ - -/* - 2008-09-22 (0.1.0): +// 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 - * The initial version. +#include <stdlib.h> +#include <string.h> -*/ +#include "nvim/memory.h" -#ifndef AC_KVEC_H -#define AC_KVEC_H +#define kv_roundup32(x) \ + ((--(x)), \ + ((x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16), \ + (++(x))) -#include <stdlib.h> -#include "nvim/memory.h" +#define KV_INITIAL_VALUE { .size = 0, .capacity = 0, .items = NULL } -#define kv_roundup32(x) (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x)) +#define kvec_t(type) \ + struct { \ + size_t size; \ + size_t capacity; \ + type *items; \ + } -#define kvec_t(type) struct { size_t size, capacity; type *items; } #define kv_init(v) ((v).size = (v).capacity = 0, (v).items = 0) #define kv_destroy(v) xfree((v).items) #define kv_A(v, i) ((v).items[(i)]) @@ -62,31 +64,133 @@ int main() { #define kv_max(v) ((v).capacity) #define kv_last(v) kv_A(v, kv_size(v) - 1) -#define kv_resize(type, v, s) ((v).capacity = (s), (v).items = (type*)xrealloc((v).items, sizeof(type) * (v).capacity)) - -#define kv_copy(type, v1, v0) do { \ - if ((v1).capacity < (v0).size) kv_resize(type, v1, (v0).size); \ - (v1).size = (v0).size; \ - memcpy((v1).items, (v0).items, sizeof(type) * (v0).size); \ - } while (0) \ - -#define kv_push(type, v, x) do { \ - if ((v).size == (v).capacity) { \ - (v).capacity = (v).capacity? (v).capacity<<1 : 8; \ - (v).items = (type*)xrealloc((v).items, sizeof(type) * (v).capacity); \ - } \ - (v).items[(v).size++] = (x); \ - } while (0) - -#define kv_pushp(type, v) ((((v).size == (v).capacity)? \ - ((v).capacity = ((v).capacity? (v).capacity<<1 : 8), \ - (v).items = (type*)xrealloc((v).items, sizeof(type) * (v).capacity), 0) \ - : 0), ((v).items + ((v).size++))) - -#define kv_a(type, v, i) (((v).capacity <= (size_t)(i)? \ - ((v).capacity = (v).size = (i) + 1, kv_roundup32((v).capacity), \ - (v).items = (type*)xrealloc((v).items, sizeof(type) * (v).capacity), 0) \ - : (v).size <= (size_t)(i)? (v).size = (i) + 1 \ - : 0), (v).items[(i)]) - -#endif +#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) \ + +#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_a(v, i) \ + (((v).capacity <= (size_t) (i) \ + ? ((v).capacity = (v).size = (i) + 1, \ + kv_roundup32((v).capacity), \ + kv_resize((v), (v).capacity), 0) \ + : ((v).size <= (size_t) (i) \ + ? (v).size = (i) + 1 \ + : 0)), \ + (v).items[(i)]) + +/// 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(src); + return dest; +} + +/// 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((v).items); \ + } \ + } while (0) + +#endif // NVIM_LIB_KVEC_H diff --git a/src/nvim/lib/queue.h b/src/nvim/lib/queue.h index fe02b454ea..ab9270081e 100644 --- a/src/nvim/lib/queue.h +++ b/src/nvim/lib/queue.h @@ -1,92 +1,90 @@ -/* Copyright (c) 2013, Ben Noordhuis <info@bnoordhuis.nl> - * - * Permission to use, copy, modify, and/or distribute this software for any - * purpose with or without fee is hereby granted, provided that the above - * copyright notice and this permission notice appear in all copies. - * - * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. - */ +// Queue implemented by circularly-linked list. +// +// Adapted from libuv. Simpler and more efficient than klist.h for implementing +// queues that support arbitrary insertion/removal. +// +// Copyright (c) 2013, Ben Noordhuis <info@bnoordhuis.nl> +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES +// WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF +// MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR +// ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES +// WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN +// ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF +// OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -#ifndef QUEUE_H_ -#define QUEUE_H_ +#ifndef NVIM_LIB_QUEUE_H +#define NVIM_LIB_QUEUE_H -typedef void *QUEUE[2]; +#include <stddef.h> -/* Private macros. */ -#define QUEUE_NEXT(q) (*(QUEUE **) &((*(q))[0])) -#define QUEUE_PREV(q) (*(QUEUE **) &((*(q))[1])) -#define QUEUE_PREV_NEXT(q) (QUEUE_NEXT(QUEUE_PREV(q))) -#define QUEUE_NEXT_PREV(q) (QUEUE_PREV(QUEUE_NEXT(q))) +#include "nvim/func_attr.h" -/* Public macros. */ -#define QUEUE_DATA(ptr, type, field) \ - ((type *) ((char *) (ptr) - ((char *) &((type *) 0)->field))) +typedef struct _queue { + struct _queue *next; + struct _queue *prev; +} QUEUE; -#define QUEUE_FOREACH(q, h) \ - for ((q) = QUEUE_NEXT(h); (q) != (h); (q) = QUEUE_NEXT(q)) +// Public macros. +#define QUEUE_DATA(ptr, type, field) \ + ((type *)((char *)(ptr) - offsetof(type, field))) -#define QUEUE_EMPTY(q) \ - ((const QUEUE *) (q) == (const QUEUE *) QUEUE_NEXT(q)) +// Important note: mutating the list while QUEUE_FOREACH is +// iterating over its elements results in undefined behavior. +#define QUEUE_FOREACH(q, h) \ + for ( /* NOLINT(readability/braces) */ \ + (q) = (h)->next; (q) != (h); (q) = (q)->next) -#define QUEUE_HEAD(q) \ - (QUEUE_NEXT(q)) +// ffi.cdef is unable to swallow `bool` in place of `int` here. +static inline int QUEUE_EMPTY(const QUEUE *const q) + FUNC_ATTR_ALWAYS_INLINE FUNC_ATTR_PURE FUNC_ATTR_WARN_UNUSED_RESULT +{ + return q == q->next; +} -#define QUEUE_INIT(q) \ - do { \ - QUEUE_NEXT(q) = (q); \ - QUEUE_PREV(q) = (q); \ - } \ - while (0) +#define QUEUE_HEAD(q) (q)->next -#define QUEUE_ADD(h, n) \ - do { \ - QUEUE_PREV_NEXT(h) = QUEUE_NEXT(n); \ - QUEUE_NEXT_PREV(n) = QUEUE_PREV(h); \ - QUEUE_PREV(h) = QUEUE_PREV(n); \ - QUEUE_PREV_NEXT(h) = (h); \ - } \ - while (0) +static inline void QUEUE_INIT(QUEUE *const q) FUNC_ATTR_ALWAYS_INLINE +{ + q->next = q; + q->prev = q; +} -#define QUEUE_SPLIT(h, q, n) \ - do { \ - QUEUE_PREV(n) = QUEUE_PREV(h); \ - QUEUE_PREV_NEXT(n) = (n); \ - QUEUE_NEXT(n) = (q); \ - QUEUE_PREV(h) = QUEUE_PREV(q); \ - QUEUE_PREV_NEXT(h) = (h); \ - QUEUE_PREV(q) = (n); \ - } \ - while (0) +static inline void QUEUE_ADD(QUEUE *const h, QUEUE *const n) + FUNC_ATTR_ALWAYS_INLINE +{ + h->prev->next = n->next; + n->next->prev = h->prev; + h->prev = n->prev; + h->prev->next = h; +} -#define QUEUE_INSERT_HEAD(h, q) \ - do { \ - QUEUE_NEXT(q) = QUEUE_NEXT(h); \ - QUEUE_PREV(q) = (h); \ - QUEUE_NEXT_PREV(q) = (q); \ - QUEUE_NEXT(h) = (q); \ - } \ - while (0) +static inline void QUEUE_INSERT_HEAD(QUEUE *const h, QUEUE *const q) + FUNC_ATTR_ALWAYS_INLINE +{ + q->next = h->next; + q->prev = h; + q->next->prev = q; + h->next = q; +} -#define QUEUE_INSERT_TAIL(h, q) \ - do { \ - QUEUE_NEXT(q) = (h); \ - QUEUE_PREV(q) = QUEUE_PREV(h); \ - QUEUE_PREV_NEXT(q) = (q); \ - QUEUE_PREV(h) = (q); \ - } \ - while (0) +static inline void QUEUE_INSERT_TAIL(QUEUE *const h, QUEUE *const q) + FUNC_ATTR_ALWAYS_INLINE +{ + q->next = h; + q->prev = h->prev; + q->prev->next = q; + h->prev = q; +} -#define QUEUE_REMOVE(q) \ - do { \ - QUEUE_PREV_NEXT(q) = QUEUE_NEXT(q); \ - QUEUE_NEXT_PREV(q) = QUEUE_PREV(q); \ - } \ - while (0) +static inline void QUEUE_REMOVE(QUEUE *const q) FUNC_ATTR_ALWAYS_INLINE +{ + q->prev->next = q->next; + q->next->prev = q->prev; +} -#endif /* QUEUE_H_ */ +#endif // NVIM_LIB_QUEUE_H diff --git a/src/nvim/lib/ringbuf.h b/src/nvim/lib/ringbuf.h index cb71500bb7..12b75ec65a 100644 --- a/src/nvim/lib/ringbuf.h +++ b/src/nvim/lib/ringbuf.h @@ -65,12 +65,12 @@ /// @param TypeName Ring buffer type name. Actual type name will be /// `{TypeName}RingBuffer`. /// @param RBType Type of the single ring buffer element. -#define RINGBUF_TYPEDEF(TypeName, RBType) \ -typedef struct { \ - RBType *buf; \ - RBType *next; \ - RBType *first; \ - RBType *buf_end; \ +#define RINGBUF_TYPEDEF(TypeName, RBType) \ +typedef struct { \ + RBType *buf; \ + RBType *next; \ + RBType *first; \ + RBType *buf_end; \ } TypeName##RingBuffer; /// Initialize a new ring buffer @@ -84,198 +84,196 @@ typedef struct { \ /// a macros like `#define RBFREE(item)` (to skip freeing). /// /// Intended function signature: `void *rbfree(RBType *)`; -#define RINGBUF_INIT(TypeName, funcprefix, RBType, rbfree) \ - \ - \ -static inline TypeName##RingBuffer funcprefix##_rb_new(const size_t size) \ - REAL_FATTR_WARN_UNUSED_RESULT; \ -static inline TypeName##RingBuffer funcprefix##_rb_new(const size_t size) \ -{ \ - assert(size != 0); \ - RBType *buf = xmalloc(size * sizeof(RBType)); \ - return (TypeName##RingBuffer) { \ - .buf = buf, \ - .next = buf, \ - .first = NULL, \ - .buf_end = buf + size - 1, \ - }; \ -} \ - \ -static inline void funcprefix##_rb_free(TypeName##RingBuffer *const rb) \ - REAL_FATTR_UNUSED; \ -static inline void funcprefix##_rb_free(TypeName##RingBuffer *const rb) \ -{ \ - if (rb == NULL) { \ - return; \ - } \ - RINGBUF_FORALL(rb, RBType, rbitem) { \ - rbfree(rbitem); \ - } \ - xfree(rb->buf); \ -} \ - \ -static inline void funcprefix##_rb_dealloc(TypeName##RingBuffer *const rb) \ - REAL_FATTR_UNUSED; \ -static inline void funcprefix##_rb_dealloc(TypeName##RingBuffer *const rb) \ -{ \ - xfree(rb->buf); \ -} \ - \ -static inline void funcprefix##_rb_push(TypeName##RingBuffer *const rb, \ - RBType item) \ - REAL_FATTR_NONNULL_ARG(1); \ -static inline void funcprefix##_rb_push(TypeName##RingBuffer *const rb, \ - RBType item) \ -{ \ - if (rb->next == rb->first) { \ - rbfree(rb->first); \ - rb->first = _RINGBUF_NEXT(rb, rb->first); \ - } else if (rb->first == NULL) { \ - rb->first = rb->next; \ - } \ - *rb->next = item; \ - rb->next = _RINGBUF_NEXT(rb, rb->next); \ -} \ - \ -static inline ptrdiff_t funcprefix##_rb_find_idx( \ - const TypeName##RingBuffer *const rb, const RBType *const item_p) \ - REAL_FATTR_NONNULL_ALL REAL_FATTR_PURE REAL_FATTR_UNUSED; \ -static inline ptrdiff_t funcprefix##_rb_find_idx( \ - const TypeName##RingBuffer *const rb, const RBType *const item_p) \ -{ \ - assert(rb->buf <= item_p); \ - assert(rb->buf_end >= item_p); \ - if (rb->first == NULL) { \ - return -1; \ - } else if (item_p >= rb->first) { \ - return item_p - rb->first; \ - } else { \ - return item_p - rb->buf + rb->buf_end - rb->first + 1; \ - } \ -} \ - \ -static inline size_t funcprefix##_rb_size( \ - const TypeName##RingBuffer *const rb) \ - REAL_FATTR_NONNULL_ALL REAL_FATTR_PURE; \ -static inline size_t funcprefix##_rb_size( \ - const TypeName##RingBuffer *const rb) \ -{ \ - return (size_t) (rb->buf_end - rb->buf) + 1; \ -} \ - \ -static inline size_t funcprefix##_rb_length( \ - const TypeName##RingBuffer *const rb) \ - REAL_FATTR_NONNULL_ALL REAL_FATTR_PURE; \ -static inline size_t funcprefix##_rb_length( \ - const TypeName##RingBuffer *const rb) \ -{ \ - return _RINGBUF_LENGTH(rb); \ -} \ - \ -static inline RBType *funcprefix##_rb_idx_p( \ - const TypeName##RingBuffer *const rb, const size_t idx) \ - REAL_FATTR_NONNULL_ALL REAL_FATTR_PURE; \ -static inline RBType *funcprefix##_rb_idx_p( \ - const TypeName##RingBuffer *const rb, const size_t idx) \ -{ \ - assert(idx <= funcprefix##_rb_size(rb)); \ - assert(idx <= funcprefix##_rb_length(rb)); \ - if (rb->first + idx > rb->buf_end) { \ - return rb->buf + ((rb->first + idx) - (rb->buf_end + 1)); \ - } else { \ - return rb->first + idx; \ - } \ -} \ - \ +#define RINGBUF_INIT(TypeName, funcprefix, RBType, rbfree) \ +static inline TypeName##RingBuffer funcprefix##_rb_new(const size_t size) \ + REAL_FATTR_WARN_UNUSED_RESULT; \ +static inline TypeName##RingBuffer funcprefix##_rb_new(const size_t size) \ +{ \ + assert(size != 0); \ + RBType *buf = xmalloc(size * sizeof(RBType)); \ + return (TypeName##RingBuffer) { \ + .buf = buf, \ + .next = buf, \ + .first = NULL, \ + .buf_end = buf + size - 1, \ + }; \ +} \ +\ +static inline void funcprefix##_rb_free(TypeName##RingBuffer *const rb) \ + REAL_FATTR_UNUSED; \ +static inline void funcprefix##_rb_free(TypeName##RingBuffer *const rb) \ +{ \ + if (rb == NULL) { \ + return; \ + } \ + RINGBUF_FORALL(rb, RBType, rbitem) { \ + rbfree(rbitem); \ + } \ + xfree(rb->buf); \ +} \ +\ +static inline void funcprefix##_rb_dealloc(TypeName##RingBuffer *const rb) \ + REAL_FATTR_UNUSED; \ +static inline void funcprefix##_rb_dealloc(TypeName##RingBuffer *const rb) \ +{ \ + xfree(rb->buf); \ +} \ +\ +static inline void funcprefix##_rb_push(TypeName##RingBuffer *const rb, \ + RBType item) \ + REAL_FATTR_NONNULL_ARG(1); \ +static inline void funcprefix##_rb_push(TypeName##RingBuffer *const rb, \ + RBType item) \ +{ \ + if (rb->next == rb->first) { \ + rbfree(rb->first); \ + rb->first = _RINGBUF_NEXT(rb, rb->first); \ + } else if (rb->first == NULL) { \ + rb->first = rb->next; \ + } \ + *rb->next = item; \ + rb->next = _RINGBUF_NEXT(rb, rb->next); \ +} \ +\ +static inline ptrdiff_t funcprefix##_rb_find_idx( \ + const TypeName##RingBuffer *const rb, const RBType *const item_p) \ + REAL_FATTR_NONNULL_ALL REAL_FATTR_PURE REAL_FATTR_UNUSED; \ +static inline ptrdiff_t funcprefix##_rb_find_idx( \ + const TypeName##RingBuffer *const rb, const RBType *const item_p) \ +{ \ + assert(rb->buf <= item_p); \ + assert(rb->buf_end >= item_p); \ + if (rb->first == NULL) { \ + return -1; \ + } else if (item_p >= rb->first) { \ + return item_p - rb->first; \ + } else { \ + return item_p - rb->buf + rb->buf_end - rb->first + 1; \ + } \ +} \ +\ +static inline size_t funcprefix##_rb_size( \ + const TypeName##RingBuffer *const rb) \ + REAL_FATTR_NONNULL_ALL REAL_FATTR_PURE; \ +static inline size_t funcprefix##_rb_size( \ + const TypeName##RingBuffer *const rb) \ +{ \ + return (size_t) (rb->buf_end - rb->buf) + 1; \ +} \ +\ +static inline size_t funcprefix##_rb_length( \ + const TypeName##RingBuffer *const rb) \ + REAL_FATTR_NONNULL_ALL REAL_FATTR_PURE; \ +static inline size_t funcprefix##_rb_length( \ + const TypeName##RingBuffer *const rb) \ +{ \ + return _RINGBUF_LENGTH(rb); \ +} \ +\ +static inline RBType *funcprefix##_rb_idx_p( \ + const TypeName##RingBuffer *const rb, const size_t idx) \ + REAL_FATTR_NONNULL_ALL REAL_FATTR_PURE; \ +static inline RBType *funcprefix##_rb_idx_p( \ + const TypeName##RingBuffer *const rb, const size_t idx) \ +{ \ + assert(idx <= funcprefix##_rb_size(rb)); \ + assert(idx <= funcprefix##_rb_length(rb)); \ + if (rb->first + idx > rb->buf_end) { \ + return rb->buf + ((rb->first + idx) - (rb->buf_end + 1)); \ + } else { \ + return rb->first + idx; \ + } \ +} \ +\ static inline RBType funcprefix##_rb_idx(const TypeName##RingBuffer *const rb, \ - const size_t idx) \ - REAL_FATTR_NONNULL_ALL REAL_FATTR_PURE REAL_FATTR_UNUSED; \ + const size_t idx) \ + REAL_FATTR_NONNULL_ALL REAL_FATTR_PURE REAL_FATTR_UNUSED; \ static inline RBType funcprefix##_rb_idx(const TypeName##RingBuffer *const rb, \ - const size_t idx) \ -{ \ - return *funcprefix##_rb_idx_p(rb, idx); \ -} \ - \ -static inline void funcprefix##_rb_insert(TypeName##RingBuffer *const rb, \ - const size_t idx, \ - RBType item) \ - REAL_FATTR_NONNULL_ARG(1) REAL_FATTR_UNUSED; \ -static inline void funcprefix##_rb_insert(TypeName##RingBuffer *const rb, \ - const size_t idx, \ - RBType item) \ -{ \ - assert(idx <= funcprefix##_rb_size(rb)); \ - assert(idx <= funcprefix##_rb_length(rb)); \ - const size_t length = funcprefix##_rb_length(rb); \ - if (idx == length) { \ - funcprefix##_rb_push(rb, item); \ - return; \ - } \ - RBType *const insertpos = funcprefix##_rb_idx_p(rb, idx); \ - if (insertpos == rb->next) { \ - funcprefix##_rb_push(rb, item); \ - return; \ - } \ - if (length == funcprefix##_rb_size(rb)) { \ - rbfree(rb->first); \ - } \ - if (insertpos < rb->next) { \ - memmove(insertpos + 1, insertpos, \ - (size_t) ((uintptr_t) rb->next - (uintptr_t) insertpos)); \ - } else { \ - assert(insertpos > rb->first); \ - assert(rb->next <= rb->first); \ - memmove(rb->buf + 1, rb->buf, \ - (size_t) ((uintptr_t) rb->next - (uintptr_t) rb->buf)); \ - *rb->buf = *rb->buf_end; \ - memmove(insertpos + 1, insertpos, \ + const size_t idx) \ +{ \ + return *funcprefix##_rb_idx_p(rb, idx); \ +} \ +\ +static inline void funcprefix##_rb_insert(TypeName##RingBuffer *const rb, \ + const size_t idx, \ + RBType item) \ + REAL_FATTR_NONNULL_ARG(1) REAL_FATTR_UNUSED; \ +static inline void funcprefix##_rb_insert(TypeName##RingBuffer *const rb, \ + const size_t idx, \ + RBType item) \ +{ \ + assert(idx <= funcprefix##_rb_size(rb)); \ + assert(idx <= funcprefix##_rb_length(rb)); \ + const size_t length = funcprefix##_rb_length(rb); \ + if (idx == length) { \ + funcprefix##_rb_push(rb, item); \ + return; \ + } \ + RBType *const insertpos = funcprefix##_rb_idx_p(rb, idx); \ + if (insertpos == rb->next) { \ + funcprefix##_rb_push(rb, item); \ + return; \ + } \ + if (length == funcprefix##_rb_size(rb)) { \ + rbfree(rb->first); \ + } \ + if (insertpos < rb->next) { \ + memmove(insertpos + 1, insertpos, \ + (size_t) ((uintptr_t) rb->next - (uintptr_t) insertpos)); \ + } else { \ + assert(insertpos > rb->first); \ + assert(rb->next <= rb->first); \ + memmove(rb->buf + 1, rb->buf, \ + (size_t) ((uintptr_t) rb->next - (uintptr_t) rb->buf)); \ + *rb->buf = *rb->buf_end; \ + memmove(insertpos + 1, insertpos, \ (size_t) ((uintptr_t) (rb->buf_end + 1) - (uintptr_t) insertpos)); \ - } \ - *insertpos = item; \ - if (length == funcprefix##_rb_size(rb)) { \ - rb->first = _RINGBUF_NEXT(rb, rb->first); \ - } \ - rb->next = _RINGBUF_NEXT(rb, rb->next); \ -} \ - \ -static inline void funcprefix##_rb_remove(TypeName##RingBuffer *const rb, \ - const size_t idx) \ - REAL_FATTR_NONNULL_ARG(1) REAL_FATTR_UNUSED; \ -static inline void funcprefix##_rb_remove(TypeName##RingBuffer *const rb, \ - const size_t idx) \ -{ \ - assert(idx < funcprefix##_rb_size(rb)); \ - assert(idx < funcprefix##_rb_length(rb)); \ - RBType *const rmpos = funcprefix##_rb_idx_p(rb, idx); \ - rbfree(rmpos); \ - if (rmpos == rb->next - 1) { \ - rb->next--; \ - if (rb->first == rb->next) { \ - rb->first = NULL; \ - rb->next = rb->buf; \ - } \ - } else if (rmpos == rb->first) { \ - rb->first = _RINGBUF_NEXT(rb, rb->first); \ - if (rb->first == rb->next) { \ - rb->first = NULL; \ - rb->next = rb->buf; \ - } \ - } else if (rb->first < rb->next || rb->next == rb->buf) { \ - assert(rmpos > rb->first); \ - assert(rmpos <= _RINGBUF_PREV(rb, rb->next)); \ - memmove(rb->first + 1, rb->first, \ - (size_t) ((uintptr_t) rmpos - (uintptr_t) rb->first)); \ - rb->first = _RINGBUF_NEXT(rb, rb->first); \ - } else if (rmpos < rb->next) { \ - memmove(rmpos, rmpos + 1, \ - (size_t) ((uintptr_t) rb->next - (uintptr_t) rmpos)); \ - rb->next = _RINGBUF_PREV(rb, rb->next); \ - } else { \ - assert(rb->first < rb->buf_end); \ - memmove(rb->first + 1, rb->first, \ - (size_t) ((uintptr_t) rmpos - (uintptr_t) rb->first)); \ - rb->first = _RINGBUF_NEXT(rb, rb->first); \ - } \ + } \ + *insertpos = item; \ + if (length == funcprefix##_rb_size(rb)) { \ + rb->first = _RINGBUF_NEXT(rb, rb->first); \ + } \ + rb->next = _RINGBUF_NEXT(rb, rb->next); \ +} \ +\ +static inline void funcprefix##_rb_remove(TypeName##RingBuffer *const rb, \ + const size_t idx) \ + REAL_FATTR_NONNULL_ARG(1) REAL_FATTR_UNUSED; \ +static inline void funcprefix##_rb_remove(TypeName##RingBuffer *const rb, \ + const size_t idx) \ +{ \ + assert(idx < funcprefix##_rb_size(rb)); \ + assert(idx < funcprefix##_rb_length(rb)); \ + RBType *const rmpos = funcprefix##_rb_idx_p(rb, idx); \ + rbfree(rmpos); \ + if (rmpos == rb->next - 1) { \ + rb->next--; \ + if (rb->first == rb->next) { \ + rb->first = NULL; \ + rb->next = rb->buf; \ + } \ + } else if (rmpos == rb->first) { \ + rb->first = _RINGBUF_NEXT(rb, rb->first); \ + if (rb->first == rb->next) { \ + rb->first = NULL; \ + rb->next = rb->buf; \ + } \ + } else if (rb->first < rb->next || rb->next == rb->buf) { \ + assert(rmpos > rb->first); \ + assert(rmpos <= _RINGBUF_PREV(rb, rb->next)); \ + memmove(rb->first + 1, rb->first, \ + (size_t) ((uintptr_t) rmpos - (uintptr_t) rb->first)); \ + rb->first = _RINGBUF_NEXT(rb, rb->first); \ + } else if (rmpos < rb->next) { \ + memmove(rmpos, rmpos + 1, \ + (size_t) ((uintptr_t) rb->next - (uintptr_t) rmpos)); \ + rb->next = _RINGBUF_PREV(rb, rb->next); \ + } else { \ + assert(rb->first < rb->buf_end); \ + memmove(rb->first + 1, rb->first, \ + (size_t) ((uintptr_t) rmpos - (uintptr_t) rb->first)); \ + rb->first = _RINGBUF_NEXT(rb, rb->first); \ + } \ } #endif // NVIM_LIB_RINGBUF_H |