Neovim Home
src
nvim
lib
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