ringbuf.h
Go to the documentation of this file.
1 #ifndef NVIM_LIB_RINGBUF_H
16 #define NVIM_LIB_RINGBUF_H
17 
18 #include <assert.h>
19 #include <stddef.h>
20 #include <stdint.h>
21 #include <string.h>
22 
23 #include "nvim/func_attr.h"
24 #include "nvim/memory.h"
25 
26 #define _RINGBUF_LENGTH(rb) \
27  ((rb)->first == NULL ? 0 \
28  : ((rb)->next == (rb)->first) ? (size_t)((rb)->buf_end - (rb)->buf) + 1 \
29  : ((rb)->next > \
30  (rb)->first) ? (size_t)((rb)->next - \
31  (rb)->first) \
32  : (size_t)((rb)-> \
33  next - (rb)->buf + \
34  (rb)->buf_end - \
35  (rb)->first + 1))
36 
37 #define _RINGBUF_NEXT(rb, var) \
38  ((var) == (rb)->buf_end ? (rb)->buf : (var) + 1)
39 #define _RINGBUF_PREV(rb, var) \
40  ((var) == (rb)->buf ? (rb)->buf_end : (var) - 1)
41 
47 #define RINGBUF_FORALL(rb, RBType, varname) \
48  size_t varname##_length_fa_ = _RINGBUF_LENGTH(rb); \
49  for (RBType *varname = ((rb)->first == NULL ? (rb)->next : (rb)->first); \
50  varname##_length_fa_; \
51  (varname = _RINGBUF_NEXT(rb, varname)), \
52  varname##_length_fa_--)
53 
62 #define RINGBUF_ITER_BACK(rb, RBType, varname) \
63  size_t varname##_length_ib_ = _RINGBUF_LENGTH(rb); \
64  for (varname = ((rb)->next == (rb)->buf ? (rb)->buf_end : (rb)->next - 1); \
65  varname##_length_ib_; \
66  (varname = _RINGBUF_PREV(rb, varname)), \
67  varname##_length_ib_--)
68 
74 #define RINGBUF_TYPEDEF(TypeName, RBType) \
75  typedef struct { \
76  RBType *buf; \
77  RBType *next; \
78  RBType *first; \
79  RBType *buf_end; \
80  } TypeName##RingBuffer;
81 
87 #define RINGBUF_DUMMY_FREE(item)
88 
99 #define RINGBUF_STATIC(scope, TypeName, RBType, varname, rbsize) \
100  static RBType _##varname##_buf[rbsize]; \
101  scope TypeName##RingBuffer varname = { \
102  .buf = _##varname##_buf, \
103  .next = _##varname##_buf, \
104  .first = NULL, \
105  .buf_end = _##varname##_buf + rbsize - 1, \
106  };
107 
119 #define RINGBUF_INIT(TypeName, funcprefix, RBType, rbfree) \
120  static inline TypeName##RingBuffer funcprefix##_rb_new(const size_t size) \
121  REAL_FATTR_WARN_UNUSED_RESULT; \
122  static inline TypeName##RingBuffer funcprefix##_rb_new(const size_t size) \
123  { \
124  assert(size != 0); \
125  RBType *buf = xmalloc(size * sizeof(RBType)); \
126  return (TypeName##RingBuffer) { \
127  .buf = buf, \
128  .next = buf, \
129  .first = NULL, \
130  .buf_end = buf + size - 1, \
131  }; \
132  } \
133  static inline void funcprefix##_rb_free(TypeName##RingBuffer *const rb) \
134  REAL_FATTR_UNUSED; \
135  static inline void funcprefix##_rb_free(TypeName##RingBuffer *const rb) \
136  { \
137  if (rb == NULL) { \
138  return; \
139  } \
140  RINGBUF_FORALL(rb, RBType, rbitem) { \
141  rbfree(rbitem); \
142  } \
143  XFREE_CLEAR(rb->buf); \
144  } \
145  static inline void funcprefix##_rb_dealloc(TypeName##RingBuffer *const rb) \
146  REAL_FATTR_UNUSED; \
147  static inline void funcprefix##_rb_dealloc(TypeName##RingBuffer *const rb) \
148  { \
149  XFREE_CLEAR(rb->buf); \
150  } \
151  static inline void funcprefix##_rb_push(TypeName##RingBuffer *const rb, \
152  RBType item) \
153  REAL_FATTR_NONNULL_ARG(1); \
154  static inline void funcprefix##_rb_push(TypeName##RingBuffer *const rb, \
155  RBType item) \
156  { \
157  if (rb->next == rb->first) { \
158  rbfree(rb->first); \
159  rb->first = _RINGBUF_NEXT(rb, rb->first); \
160  } else if (rb->first == NULL) { \
161  rb->first = rb->next; \
162  } \
163  *rb->next = item; \
164  rb->next = _RINGBUF_NEXT(rb, rb->next); \
165  } \
166  static inline ptrdiff_t funcprefix##_rb_find_idx(const TypeName##RingBuffer *const rb, \
167  const RBType *const item_p) \
168  REAL_FATTR_NONNULL_ALL REAL_FATTR_PURE REAL_FATTR_UNUSED; \
169  static inline ptrdiff_t funcprefix##_rb_find_idx(const TypeName##RingBuffer *const rb, \
170  const RBType *const item_p) \
171  { \
172  assert(rb->buf <= item_p); \
173  assert(rb->buf_end >= item_p); \
174  if (rb->first == NULL) { \
175  return -1; \
176  } else if (item_p >= rb->first) { \
177  return item_p - rb->first; \
178  } else { \
179  return item_p - rb->buf + rb->buf_end - rb->first + 1; \
180  } \
181  } \
182  static inline size_t funcprefix##_rb_size(const TypeName##RingBuffer *const rb) \
183  REAL_FATTR_NONNULL_ALL REAL_FATTR_PURE; \
184  static inline size_t funcprefix##_rb_size(const TypeName##RingBuffer *const rb) \
185  { \
186  return (size_t)(rb->buf_end - rb->buf) + 1; \
187  } \
188  static inline size_t funcprefix##_rb_length(const TypeName##RingBuffer *const rb) \
189  REAL_FATTR_NONNULL_ALL REAL_FATTR_PURE; \
190  static inline size_t funcprefix##_rb_length(const TypeName##RingBuffer *const rb) \
191  { \
192  return _RINGBUF_LENGTH(rb); \
193  } \
194  static inline RBType *funcprefix##_rb_idx_p(const TypeName##RingBuffer *const rb, \
195  const size_t idx) \
196  REAL_FATTR_NONNULL_ALL REAL_FATTR_PURE; \
197  static inline RBType *funcprefix##_rb_idx_p(const TypeName##RingBuffer *const rb, \
198  const size_t idx) \
199  { \
200  assert(idx <= funcprefix##_rb_size(rb)); \
201  assert(idx <= funcprefix##_rb_length(rb)); \
202  if (rb->first + idx > rb->buf_end) { \
203  return rb->buf + ((rb->first + idx) - (rb->buf_end + 1)); \
204  } else { \
205  return rb->first + idx; \
206  } \
207  } \
208  static inline RBType funcprefix##_rb_idx(const TypeName##RingBuffer *const rb, \
209  const size_t idx) \
210  REAL_FATTR_NONNULL_ALL REAL_FATTR_PURE REAL_FATTR_UNUSED; \
211  static inline RBType funcprefix##_rb_idx(const TypeName##RingBuffer *const rb, \
212  const size_t idx) \
213  { \
214  return *funcprefix##_rb_idx_p(rb, idx); \
215  } \
216  static inline void funcprefix##_rb_insert(TypeName##RingBuffer *const rb, \
217  const size_t idx, \
218  RBType item) \
219  REAL_FATTR_NONNULL_ARG(1) REAL_FATTR_UNUSED; \
220  static inline void funcprefix##_rb_insert(TypeName##RingBuffer *const rb, \
221  const size_t idx, \
222  RBType item) \
223  { \
224  assert(idx <= funcprefix##_rb_size(rb)); \
225  assert(idx <= funcprefix##_rb_length(rb)); \
226  const size_t length = funcprefix##_rb_length(rb); \
227  if (idx == length) { \
228  funcprefix##_rb_push(rb, item); \
229  return; \
230  } \
231  RBType *const insertpos = funcprefix##_rb_idx_p(rb, idx); \
232  if (insertpos == rb->next) { \
233  funcprefix##_rb_push(rb, item); \
234  return; \
235  } \
236  if (length == funcprefix##_rb_size(rb)) { \
237  rbfree(rb->first); \
238  } \
239  if (insertpos < rb->next) { \
240  memmove(insertpos + 1, insertpos, \
241  (size_t)((uintptr_t)rb->next - (uintptr_t)insertpos)); \
242  } else { \
243  assert(insertpos > rb->first); \
244  assert(rb->next <= rb->first); \
245  memmove(rb->buf + 1, rb->buf, \
246  (size_t)((uintptr_t)rb->next - (uintptr_t)rb->buf)); \
247  *rb->buf = *rb->buf_end; \
248  memmove(insertpos + 1, insertpos, \
249  (size_t)((uintptr_t)(rb->buf_end + 1) - (uintptr_t)insertpos)); \
250  } \
251  *insertpos = item; \
252  if (length == funcprefix##_rb_size(rb)) { \
253  rb->first = _RINGBUF_NEXT(rb, rb->first); \
254  } \
255  rb->next = _RINGBUF_NEXT(rb, rb->next); \
256  } \
257  static inline void funcprefix##_rb_remove(TypeName##RingBuffer *const rb, \
258  const size_t idx) \
259  REAL_FATTR_NONNULL_ARG(1) REAL_FATTR_UNUSED; \
260  static inline void funcprefix##_rb_remove(TypeName##RingBuffer *const rb, \
261  const size_t idx) \
262  { \
263  assert(idx < funcprefix##_rb_size(rb)); \
264  assert(idx < funcprefix##_rb_length(rb)); \
265  RBType *const rmpos = funcprefix##_rb_idx_p(rb, idx); \
266  rbfree(rmpos); \
267  if (rmpos == rb->next - 1) { \
268  rb->next--; \
269  if (rb->first == rb->next) { \
270  rb->first = NULL; \
271  rb->next = rb->buf; \
272  } \
273  } else if (rmpos == rb->first) { \
274  rb->first = _RINGBUF_NEXT(rb, rb->first); \
275  if (rb->first == rb->next) { \
276  rb->first = NULL; \
277  rb->next = rb->buf; \
278  } \
279  } else if (rb->first < rb->next || rb->next == rb->buf) { \
280  assert(rmpos > rb->first); \
281  assert(rmpos <= _RINGBUF_PREV(rb, rb->next)); \
282  memmove(rb->first + 1, rb->first, \
283  (size_t)((uintptr_t)rmpos - (uintptr_t)rb->first)); \
284  rb->first = _RINGBUF_NEXT(rb, rb->first); \
285  } else if (rmpos < rb->next) { \
286  memmove(rmpos, rmpos + 1, \
287  (size_t)((uintptr_t)rb->next - (uintptr_t)rmpos)); \
288  rb->next = _RINGBUF_PREV(rb, rb->next); \
289  } else { \
290  assert(rb->first < rb->buf_end); \
291  memmove(rb->first + 1, rb->first, \
292  (size_t)((uintptr_t)rmpos - (uintptr_t)rb->first)); \
293  rb->first = _RINGBUF_NEXT(rb, rb->first); \
294  } \
295  }
296 
297 #endif // NVIM_LIB_RINGBUF_H
assert.h
func_attr.h
memory.h