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