diff options
Diffstat (limited to 'src/nvim/lib')
| -rw-r--r-- | src/nvim/lib/khash.h | 433 | ||||
| -rw-r--r-- | src/nvim/lib/ringbuf.h | 281 |
2 files changed, 549 insertions, 165 deletions
diff --git a/src/nvim/lib/khash.h b/src/nvim/lib/khash.h index 96e7ea6df0..56be29d14c 100644 --- a/src/nvim/lib/khash.h +++ b/src/nvim/lib/khash.h @@ -114,8 +114,8 @@ int main() { */ -#ifndef __AC_KHASH_H -#define __AC_KHASH_H +#ifndef NVIM_LIB_KHASH_H +#define NVIM_LIB_KHASH_H /*! @header @@ -194,166 +194,229 @@ static const double __ac_HASH_UPPER = 0.77; khval_t *vals; \ } kh_##name##_t; -#define __KHASH_PROTOTYPES(name, khkey_t, khval_t) \ - extern kh_##name##_t *kh_init_##name(void); \ - extern void kh_destroy_##name(kh_##name##_t *h); \ - extern void kh_clear_##name(kh_##name##_t *h); \ - extern khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key); \ - extern void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets); \ - extern khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret); \ - extern void kh_del_##name(kh_##name##_t *h, khint_t x); - -#define __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \ - SCOPE kh_##name##_t *kh_init_##name(void) { \ - return (kh_##name##_t*)kcalloc(1, sizeof(kh_##name##_t)); \ - } \ - SCOPE void kh_destroy_##name(kh_##name##_t *h) \ - REAL_FATTR_UNUSED; \ - SCOPE void kh_destroy_##name(kh_##name##_t *h) \ - { \ - if (h) { \ - kfree((void *)h->keys); kfree(h->flags); \ - kfree((void *)h->vals); \ - kfree(h); \ - } \ - } \ - SCOPE void kh_clear_##name(kh_##name##_t *h) \ - REAL_FATTR_UNUSED; \ - SCOPE void kh_clear_##name(kh_##name##_t *h) \ - { \ - if (h && h->flags) { \ - memset(h->flags, 0xaa, __ac_fsize(h->n_buckets) * sizeof(khint32_t)); \ - h->size = h->n_occupied = 0; \ - } \ - } \ - SCOPE khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key) \ - REAL_FATTR_UNUSED; \ - SCOPE khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key) \ - { \ - if (h->n_buckets) { \ - khint_t k, i, last, mask, step = 0; \ - mask = h->n_buckets - 1; \ - k = __hash_func(key); i = k & mask; \ - last = i; \ - while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \ - i = (i + (++step)) & mask; \ - if (i == last) return h->n_buckets; \ - } \ - return __ac_iseither(h->flags, i)? h->n_buckets : i; \ - } else return 0; \ - } \ - SCOPE void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \ - REAL_FATTR_UNUSED; \ - SCOPE void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \ - { /* This function uses 0.25*n_buckets bytes of working space instead of [sizeof(key_t+val_t)+.25]*n_buckets. */ \ - khint32_t *new_flags = 0; \ - khint_t j = 1; \ - { \ - kroundup32(new_n_buckets); \ - if (new_n_buckets < 4) new_n_buckets = 4; \ - if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0; /* requested size is too small */ \ - else { /* hash table size to be changed (shrink or expand); rehash */ \ - new_flags = (khint32_t*)kmalloc(__ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ - memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ - if (h->n_buckets < new_n_buckets) { /* expand */ \ - khkey_t *new_keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ - h->keys = new_keys; \ - if (kh_is_map) { \ - khval_t *new_vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ - h->vals = new_vals; \ - } \ - } /* otherwise shrink */ \ - } \ - } \ - if (j) { /* rehashing is needed */ \ - for (j = 0; j != h->n_buckets; ++j) { \ - if (__ac_iseither(h->flags, j) == 0) { \ - khkey_t key = h->keys[j]; \ - khval_t val; \ - khint_t new_mask; \ - new_mask = new_n_buckets - 1; \ - if (kh_is_map) val = h->vals[j]; \ - __ac_set_isdel_true(h->flags, j); \ - while (1) { /* kick-out process; sort of like in Cuckoo hashing */ \ - khint_t k, i, step = 0; \ - k = __hash_func(key); \ - i = k & new_mask; \ - while (!__ac_isempty(new_flags, i)) i = (i + (++step)) & new_mask; \ - __ac_set_isempty_false(new_flags, i); \ - if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { /* kick out the existing element */ \ - { khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \ - if (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \ - __ac_set_isdel_true(h->flags, i); /* mark it as deleted in the old hash table */ \ - } else { /* write the element and jump out of the loop */ \ - h->keys[i] = key; \ - if (kh_is_map) h->vals[i] = val; \ - break; \ - } \ - } \ - } \ - } \ - if (h->n_buckets > new_n_buckets) { /* shrink the hash table */ \ - h->keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ - if (kh_is_map) h->vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ - } \ - kfree(h->flags); /* free the working space */ \ - h->flags = new_flags; \ - h->n_buckets = new_n_buckets; \ - h->n_occupied = h->size; \ - h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \ - } \ - } \ - SCOPE khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \ - REAL_FATTR_UNUSED; \ - SCOPE khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \ - { \ - khint_t x; \ - if (h->n_occupied >= h->upper_bound) { /* update the hash table */ \ - if (h->n_buckets > (h->size<<1)) { \ - kh_resize_##name(h, h->n_buckets - 1); /* clear "deleted" elements */ \ - } else { \ - kh_resize_##name(h, h->n_buckets + 1); /* expand the hash table */ \ - } \ - } /* TODO: to implement automatically shrinking; resize() already support shrinking */ \ - { \ - khint_t k, i, site, last, mask = h->n_buckets - 1, step = 0; \ - x = site = h->n_buckets; k = __hash_func(key); i = k & mask; \ - if (__ac_isempty(h->flags, i)) x = i; /* for speed up */ \ - else { \ - last = i; \ - while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \ - if (__ac_isdel(h->flags, i)) site = i; \ - i = (i + (++step)) & mask; \ - if (i == last) { x = site; break; } \ - } \ - if (x == h->n_buckets) { \ - if (__ac_isempty(h->flags, i) && site != h->n_buckets) x = site; \ - else x = i; \ - } \ - } \ - } \ - if (__ac_isempty(h->flags, x)) { /* not present at all */ \ - h->keys[x] = key; \ - __ac_set_isboth_false(h->flags, x); \ - ++h->size; ++h->n_occupied; \ - *ret = 1; \ - } else if (__ac_isdel(h->flags, x)) { /* deleted */ \ - h->keys[x] = key; \ - __ac_set_isboth_false(h->flags, x); \ - ++h->size; \ - *ret = 2; \ - } else *ret = 0; /* Don't touch h->keys[x] if present and not deleted */ \ - return x; \ - } \ - SCOPE void kh_del_##name(kh_##name##_t *h, khint_t x) \ - REAL_FATTR_UNUSED; \ - SCOPE void kh_del_##name(kh_##name##_t *h, khint_t x) \ - { \ - if (x != h->n_buckets && !__ac_iseither(h->flags, x)) { \ - __ac_set_isdel_true(h->flags, x); \ - --h->size; \ - } \ - } +#define __KHASH_PROTOTYPES(name, khkey_t, khval_t) \ + extern kh_##name##_t *kh_init_##name(void); \ + extern void kh_dealloc_##name(kh_##name##_t *h); \ + extern void kh_destroy_##name(kh_##name##_t *h); \ + extern void kh_clear_##name(kh_##name##_t *h); \ + extern khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key); \ + extern void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets); \ + extern khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret); \ + extern void kh_del_##name(kh_##name##_t *h, khint_t x); + +#define __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, \ + __hash_equal) \ + SCOPE kh_##name##_t *kh_init_##name(void) \ + REAL_FATTR_UNUSED; \ + SCOPE kh_##name##_t *kh_init_##name(void) { \ + return (kh_##name##_t*)kcalloc(1, sizeof(kh_##name##_t)); \ + } \ + SCOPE void kh_dealloc_##name(kh_##name##_t *h) \ + REAL_FATTR_UNUSED; \ + SCOPE void kh_dealloc_##name(kh_##name##_t *h) \ + { \ + kfree(h->keys); \ + kfree(h->flags); \ + kfree(h->vals); \ + } \ + SCOPE void kh_destroy_##name(kh_##name##_t *h) \ + REAL_FATTR_UNUSED; \ + SCOPE void kh_destroy_##name(kh_##name##_t *h) \ + { \ + if (h) { \ + kh_dealloc_##name(h); \ + kfree(h); \ + } \ + } \ + SCOPE void kh_clear_##name(kh_##name##_t *h) \ + REAL_FATTR_UNUSED; \ + SCOPE void kh_clear_##name(kh_##name##_t *h) \ + { \ + if (h && h->flags) { \ + memset(h->flags, 0xaa, __ac_fsize(h->n_buckets) * sizeof(khint32_t)); \ + h->size = h->n_occupied = 0; \ + } \ + } \ + SCOPE khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key) \ + REAL_FATTR_UNUSED; \ + SCOPE khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key) \ + { \ + if (h->n_buckets) { \ + khint_t k, i, last, mask, step = 0; \ + mask = h->n_buckets - 1; \ + k = __hash_func(key); i = k & mask; \ + last = i; \ + while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || \ + !__hash_equal(h->keys[i], key))) { \ + i = (i + (++step)) & mask; \ + if (i == last) { \ + return h->n_buckets; \ + } \ + } \ + return __ac_iseither(h->flags, i) ? h->n_buckets : i; \ + } else { \ + return 0; \ + } \ + } \ + SCOPE void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \ + REAL_FATTR_UNUSED; \ + SCOPE void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \ + { /* This function uses 0.25*n_buckets bytes of working space instead of */ \ + /* [sizeof(key_t+val_t)+.25]*n_buckets. */ \ + khint32_t *new_flags = 0; \ + khint_t j = 1; \ + { \ + kroundup32(new_n_buckets); \ + if (new_n_buckets < 4) { \ + new_n_buckets = 4; \ + } \ + /* requested size is too small */ \ + if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) { \ + j = 0; \ + } else { /* hash table size to be changed (shrink or expand); rehash */ \ + new_flags = (khint32_t*)kmalloc(__ac_fsize(new_n_buckets) \ + * sizeof(khint32_t)); \ + memset(new_flags, 0xaa, \ + __ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ + if (h->n_buckets < new_n_buckets) { /* expand */ \ + khkey_t *new_keys = (khkey_t*)krealloc( \ + (void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ + h->keys = new_keys; \ + if (kh_is_map) { \ + khval_t *new_vals = (khval_t*)krealloc( \ + (void *)h->vals, new_n_buckets * sizeof(khval_t)); \ + h->vals = new_vals; \ + } \ + } /* otherwise shrink */ \ + } \ + } \ + if (j) { /* rehashing is needed */ \ + for (j = 0; j != h->n_buckets; ++j) { \ + if (__ac_iseither(h->flags, j) == 0) { \ + khkey_t key = h->keys[j]; \ + khval_t val; \ + khint_t new_mask; \ + new_mask = new_n_buckets - 1; \ + if (kh_is_map) { \ + val = h->vals[j]; \ + } \ + __ac_set_isdel_true(h->flags, j); \ + /* kick-out process; sort of like in Cuckoo hashing */ \ + while (1) { \ + khint_t k, i, step = 0; \ + k = __hash_func(key); \ + i = k & new_mask; \ + while (!__ac_isempty(new_flags, i)) { \ + i = (i + (++step)) & new_mask; \ + } \ + __ac_set_isempty_false(new_flags, i); \ + /* kick out the existing element */ \ + if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { \ + { \ + khkey_t tmp = h->keys[i]; \ + h->keys[i] = key; \ + key = tmp; \ + } \ + if (kh_is_map) { \ + khval_t tmp = h->vals[i]; \ + h->vals[i] = val; \ + val = tmp; \ + } \ + /* mark it as deleted in the old hash table */ \ + __ac_set_isdel_true(h->flags, i); \ + } else { /* write the element and jump out of the loop */ \ + h->keys[i] = key; \ + if (kh_is_map) { \ + h->vals[i] = val; \ + } \ + break; \ + } \ + } \ + } \ + } \ + if (h->n_buckets > new_n_buckets) { /* shrink the hash table */ \ + h->keys = (khkey_t*)krealloc((void *)h->keys, \ + new_n_buckets * sizeof(khkey_t)); \ + if (kh_is_map) { \ + h->vals = (khval_t*)krealloc((void *)h->vals, \ + new_n_buckets * sizeof(khval_t)); \ + } \ + } \ + kfree(h->flags); /* free the working space */ \ + h->flags = new_flags; \ + h->n_buckets = new_n_buckets; \ + h->n_occupied = h->size; \ + h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \ + } \ + } \ + SCOPE khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \ + REAL_FATTR_UNUSED; \ + SCOPE khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \ + { \ + khint_t x; \ + if (h->n_occupied >= h->upper_bound) { /* update the hash table */ \ + if (h->n_buckets > (h->size << 1)) { \ + kh_resize_##name(h, h->n_buckets - 1); /* clear "deleted" elements */ \ + } else { \ + kh_resize_##name(h, h->n_buckets + 1); /* expand the hash table */ \ + } \ + } /* TODO: implement automatically shrinking; */ \ + /* resize() already support shrinking */ \ + { \ + khint_t k, i, site, last, mask = h->n_buckets - 1, step = 0; \ + x = site = h->n_buckets; \ + k = __hash_func(key); \ + i = k & mask; \ + if (__ac_isempty(h->flags, i)) { \ + x = i; /* for speed up */ \ + } else { \ + last = i; \ + while (!__ac_isempty(h->flags, i) \ + && (__ac_isdel(h->flags, i) \ + || !__hash_equal(h->keys[i], key))) { \ + if (__ac_isdel(h->flags, i)) { \ + site = i; \ + } \ + i = (i + (++step)) & mask; \ + if (i == last) { \ + x = site; \ + break; \ + } \ + } \ + if (x == h->n_buckets) { \ + if (__ac_isempty(h->flags, i) && site != h->n_buckets) { \ + x = site; \ + } else { \ + x = i; \ + } \ + } \ + } \ + } \ + if (__ac_isempty(h->flags, x)) { /* not present at all */ \ + h->keys[x] = key; \ + __ac_set_isboth_false(h->flags, x); \ + h->size++; \ + h->n_occupied++; \ + *ret = 1; \ + } else if (__ac_isdel(h->flags, x)) { /* deleted */ \ + h->keys[x] = key; \ + __ac_set_isboth_false(h->flags, x); \ + h->size++; \ + *ret = 2; \ + } else { \ + *ret = 0; /* Don't touch h->keys[x] if present and not deleted */ \ + } \ + return x; \ + } \ + SCOPE void kh_del_##name(kh_##name##_t *h, khint_t x) \ + REAL_FATTR_UNUSED; \ + SCOPE void kh_del_##name(kh_##name##_t *h, khint_t x) \ + { \ + if (x != h->n_buckets && !__ac_iseither(h->flags, x)) { \ + __ac_set_isdel_true(h->flags, x); \ + --h->size; \ + } \ + } #define KHASH_DECLARE(name, khkey_t, khval_t) \ __KHASH_TYPE(name, khkey_t, khval_t) \ @@ -447,6 +510,13 @@ static kh_inline khint_t __ac_Wang_hash(khint_t key) #define kh_destroy(name, h) kh_destroy_##name(h) /*! @function + @abstract Free memory referenced directly inside a hash table. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + */ +#define kh_dealloc(name, h) kh_dealloc_##name(h) + +/*! @function @abstract Reset a hash table without deallocating memory. @param name Name of the hash table [symbol] @param h Pointer to the hash table [khash_t(name)*] @@ -577,6 +647,24 @@ static kh_inline khint_t __ac_Wang_hash(khint_t key) code; \ } } +/*! @function + @abstract Iterate over the keys in the hash table + @param h Pointer to the hash table [khash_t(name)*] + @param kvar Variable to which value will be assigned + @param code Block of code to execute + */ +#define kh_foreach_key(h, kvar, code) \ + { \ + khint_t __i; \ + for (__i = kh_begin(h); __i != kh_end(h); __i++) { \ + if (!kh_exist(h, __i)) { \ + continue; \ + } \ + (kvar) = kh_key(h, __i); \ + code; \ + } \ + } + /* More conenient interfaces */ /*! @function @@ -622,6 +710,21 @@ typedef const char *kh_cstr_t; @param name Name of the hash table [symbol] @param khval_t Type of values [type] */ -#define KHASH_MAP_INIT_STR(name, khval_t) \ - KHASH_INIT(name, kh_cstr_t, khval_t, 1, kh_str_hash_func, kh_str_hash_equal) -#endif /* __AC_KHASH_H */ +#define KHASH_MAP_INIT_STR(name, khval_t) \ + KHASH_INIT(name, kh_cstr_t, khval_t, 1, kh_str_hash_func, kh_str_hash_equal) + +/*! @function + @abstract Return a literal for an empty hash table. + @param name Name of the hash table [symbol] + */ +#define KHASH_EMPTY_TABLE(name) \ + ((kh_##name##_t) { \ + .n_buckets = 0, \ + .size = 0, \ + .n_occupied = 0, \ + .upper_bound = 0, \ + .flags = NULL, \ + .keys = NULL, \ + .vals = NULL, \ + }) +#endif // NVIM_LIB_KHASH_H diff --git a/src/nvim/lib/ringbuf.h b/src/nvim/lib/ringbuf.h new file mode 100644 index 0000000000..cb71500bb7 --- /dev/null +++ b/src/nvim/lib/ringbuf.h @@ -0,0 +1,281 @@ +/// Macros-based ring buffer implementation. +/// +/// Supported functions: +/// +/// - new: allocates new ring buffer. +/// - dealloc: free ring buffer itself. +/// - free: free ring buffer and all its elements. +/// - push: adds element to the end of the buffer. +/// - length: get buffer length. +/// - size: size of the ring buffer. +/// - idx: get element at given index. +/// - idx_p: get pointer to the element at given index. +/// - insert: insert element at given position. +/// - remove: remove element from given position. +#ifndef NVIM_LIB_RINGBUF_H +#define NVIM_LIB_RINGBUF_H + +#include <string.h> +#include <assert.h> +#include <stdint.h> + +#include "nvim/memory.h" +#include "nvim/func_attr.h" + +#define _RINGBUF_LENGTH(rb) \ + ((rb)->first == NULL ? 0 \ + : ((rb)->next == (rb)->first) ? (size_t) ((rb)->buf_end - (rb)->buf) + 1 \ + : ((rb)->next > (rb)->first) ? (size_t) ((rb)->next - (rb)->first) \ + : (size_t) ((rb)->next - (rb)->buf + (rb)->buf_end - (rb)->first + 1)) + +#define _RINGBUF_NEXT(rb, var) \ + ((var) == (rb)->buf_end ? (rb)->buf : (var) + 1) +#define _RINGBUF_PREV(rb, var) \ + ((var) == (rb)->buf ? (rb)->buf_end : (var) - 1) + +/// Iterate over all ringbuf values +/// +/// @param rb Ring buffer to iterate over. +/// @param RBType Type of the ring buffer element. +/// @param varname Variable name. +#define RINGBUF_FORALL(rb, RBType, varname) \ + size_t varname##_length_fa_ = _RINGBUF_LENGTH(rb); \ + for (RBType *varname = ((rb)->first == NULL ? (rb)->next : (rb)->first); \ + varname##_length_fa_; \ + (varname = _RINGBUF_NEXT(rb, varname)), \ + varname##_length_fa_--) + +/// Iterate over all ringbuf values, from end to the beginning +/// +/// Unlike previous RINGBUF_FORALL uses already defined variable, in place of +/// defining variable in the cycle body. +/// +/// @param rb Ring buffer to iterate over. +/// @param RBType Type of the ring buffer element. +/// @param varname Variable name. +#define RINGBUF_ITER_BACK(rb, RBType, varname) \ + size_t varname##_length_ib_ = _RINGBUF_LENGTH(rb); \ + for (varname = ((rb)->next == (rb)->buf ? (rb)->buf_end : (rb)->next - 1); \ + varname##_length_ib_; \ + (varname = _RINGBUF_PREV(rb, varname)), \ + varname##_length_ib_--) + +/// Define a ring buffer structure +/// +/// @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; \ +} TypeName##RingBuffer; + +/// Initialize a new ring buffer +/// +/// @param TypeName Ring buffer type name. Actual type name will be +/// `{TypeName}RingBuffer`. +/// @param funcprefix Prefix for all ring buffer functions. Function name will +/// look like `{funcprefix}_rb_{function_name}`. +/// @param RBType Type of the single ring buffer element. +/// @param rbfree Function used to free ring buffer element. May be +/// 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; \ + } \ +} \ + \ +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; \ +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, \ + (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); \ + } \ +} + +#endif // NVIM_LIB_RINGBUF_H |