Open Broadcaster Software
Free, open source software for live streaming and recording
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
circlebuf.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2013 Hugh Bailey <obs.jim@gmail.com>
3  *
4  * Permission to use, copy, modify, and distribute this software for any
5  * purpose with or without fee is hereby granted, provided that the above
6  * copyright notice and this permission notice appear in all copies.
7  *
8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15  */
16 
17 #pragma once
18 
19 #include "c99defs.h"
20 #include <string.h>
21 #include <stdlib.h>
22 #include <assert.h>
23 
24 #include "bmem.h"
25 
26 #ifdef __cplusplus
27 extern "C" {
28 #endif
29 
30 /* Dynamic circular buffer */
31 
32 struct circlebuf {
33  void *data;
34  size_t size;
35 
36  size_t start_pos;
37  size_t end_pos;
38  size_t capacity;
39 };
40 
41 static inline void circlebuf_init(struct circlebuf *cb)
42 {
43  memset(cb, 0, sizeof(struct circlebuf));
44 }
45 
46 static inline void circlebuf_free(struct circlebuf *cb)
47 {
48  bfree(cb->data);
49  memset(cb, 0, sizeof(struct circlebuf));
50 }
51 
52 static inline void circlebuf_reorder_data(struct circlebuf *cb,
53  size_t new_capacity)
54 {
55  size_t difference;
56  uint8_t *data;
57 
58  if (!cb->size || !cb->start_pos || cb->end_pos > cb->start_pos)
59  return;
60 
61  difference = new_capacity - cb->capacity;
62  data = (uint8_t*)cb->data + cb->start_pos;
63  memmove(data+difference, data, cb->capacity - cb->start_pos);
64  cb->start_pos += difference;
65 }
66 
67 static inline void circlebuf_ensure_capacity(struct circlebuf *cb)
68 {
69  size_t new_capacity;
70  if (cb->size <= cb->capacity)
71  return;
72 
73  new_capacity = cb->capacity*2;
74  if (cb->size > new_capacity)
75  new_capacity = cb->size;
76 
77  cb->data = brealloc(cb->data, new_capacity);
78  circlebuf_reorder_data(cb, new_capacity);
79  cb->capacity = new_capacity;
80 }
81 
82 static inline void circlebuf_reserve(struct circlebuf *cb, size_t capacity)
83 {
84  if (capacity <= cb->capacity)
85  return;
86 
87  cb->data = brealloc(cb->data, capacity);
88  circlebuf_reorder_data(cb, capacity);
89  cb->capacity = capacity;
90 }
91 
92 static inline void circlebuf_upsize(struct circlebuf *cb, size_t size)
93 {
94  size_t add_size = size - cb->size;
95  size_t new_end_pos = cb->end_pos + add_size;
96 
97  if (size <= cb->size)
98  return;
99 
100  cb->size = size;
101  circlebuf_ensure_capacity(cb);
102 
103  if (new_end_pos > cb->capacity) {
104  size_t back_size = cb->capacity - cb->end_pos;
105  size_t loop_size = add_size - back_size;
106 
107  if (back_size)
108  memset((uint8_t*)cb->data + cb->end_pos, 0, back_size);
109 
110  memset(cb->data, 0, loop_size);
111  new_end_pos -= cb->capacity;
112  } else {
113  memset((uint8_t*)cb->data + cb->end_pos, 0, add_size);
114  }
115 
116  cb->end_pos = new_end_pos;
117 }
118 
120 static inline void circlebuf_place(struct circlebuf *cb, size_t position,
121  const void *data, size_t size)
122 {
123  size_t end_point = position + size;
124  size_t data_end_pos;
125 
126  if (end_point > cb->size)
127  circlebuf_upsize(cb, end_point);
128 
129  position += cb->start_pos;
130  if (position >= cb->capacity)
131  position -= cb->capacity;
132 
133  data_end_pos = position + size;
134  if (data_end_pos > cb->capacity) {
135  size_t back_size = data_end_pos - cb->capacity;
136  size_t loop_size = size - back_size;
137 
138  if (back_size)
139  memcpy((uint8_t*)cb->data + position, data, loop_size);
140  memcpy(cb->data, (uint8_t*)data + loop_size, back_size);
141  } else {
142  memcpy((uint8_t*)cb->data + position, data, size);
143  }
144 }
145 
146 static inline void circlebuf_push_back(struct circlebuf *cb, const void *data,
147  size_t size)
148 {
149  size_t new_end_pos = cb->end_pos + size;
150 
151  cb->size += size;
152  circlebuf_ensure_capacity(cb);
153 
154  if (new_end_pos > cb->capacity) {
155  size_t back_size = cb->capacity - cb->end_pos;
156  size_t loop_size = size - back_size;
157 
158  if (back_size)
159  memcpy((uint8_t*)cb->data + cb->end_pos, data,
160  back_size);
161  memcpy(cb->data, (uint8_t*)data + back_size, loop_size);
162 
163  new_end_pos -= cb->capacity;
164  } else {
165  memcpy((uint8_t*)cb->data + cb->end_pos, data, size);
166  }
167 
168  cb->end_pos = new_end_pos;
169 }
170 
171 static inline void circlebuf_push_front(struct circlebuf *cb, const void *data,
172  size_t size)
173 {
174  cb->size += size;
175  circlebuf_ensure_capacity(cb);
176 
177  if (cb->start_pos < size) {
178  size_t back_size = size - cb->start_pos;
179 
180  if (cb->start_pos)
181  memcpy(cb->data, (uint8_t*)data + back_size,
182  cb->start_pos);
183 
184  cb->start_pos = cb->capacity - back_size;
185  memcpy((uint8_t*)cb->data + cb->start_pos, data, back_size);
186  } else {
187  cb->start_pos -= size;
188  memcpy((uint8_t*)cb->data + cb->start_pos, data, size);
189  }
190 }
191 
192 static inline void circlebuf_push_back_zero(struct circlebuf *cb, size_t size)
193 {
194  size_t new_end_pos = cb->end_pos + size;
195 
196  cb->size += size;
197  circlebuf_ensure_capacity(cb);
198 
199  if (new_end_pos > cb->capacity) {
200  size_t back_size = cb->capacity - cb->end_pos;
201  size_t loop_size = size - back_size;
202 
203  if (back_size)
204  memset((uint8_t*)cb->data + cb->end_pos, 0, back_size);
205  memset(cb->data, 0, loop_size);
206 
207  new_end_pos -= cb->capacity;
208  } else {
209  memset((uint8_t*)cb->data + cb->end_pos, 0, size);
210  }
211 
212  cb->end_pos = new_end_pos;
213 }
214 
215 static inline void circlebuf_push_front_zero(struct circlebuf *cb, size_t size)
216 {
217  cb->size += size;
218  circlebuf_ensure_capacity(cb);
219 
220  if (cb->start_pos < size) {
221  size_t back_size = size - cb->start_pos;
222 
223  if (cb->start_pos)
224  memset(cb->data, 0, cb->start_pos);
225 
226  cb->start_pos = cb->capacity - back_size;
227  memset((uint8_t*)cb->data + cb->start_pos, 0, back_size);
228  } else {
229  cb->start_pos -= size;
230  memset((uint8_t*)cb->data + cb->start_pos, 0, size);
231  }
232 }
233 
234 static inline void circlebuf_peek_front(struct circlebuf *cb, void *data,
235  size_t size)
236 {
237  assert(size <= cb->size);
238 
239  if (data) {
240  size_t start_size = cb->capacity - cb->start_pos;
241 
242  if (start_size < size) {
243  memcpy(data, (uint8_t*)cb->data + cb->start_pos,
244  start_size);
245  memcpy((uint8_t*)data + start_size, cb->data,
246  size - start_size);
247  } else {
248  memcpy(data, (uint8_t*)cb->data + cb->start_pos, size);
249  }
250  }
251 }
252 
253 static inline void circlebuf_peek_back(struct circlebuf *cb, void *data,
254  size_t size)
255 {
256  assert(size <= cb->size);
257 
258  if (data) {
259  size_t back_size = (cb->end_pos ? cb->end_pos : cb->capacity);
260 
261  if (back_size < size) {
262  size_t front_size = size - back_size;
263  size_t new_end_pos = cb->capacity - front_size;
264 
265  memcpy((uint8_t*)data + (size - back_size), cb->data,
266  back_size);
267  memcpy(data, (uint8_t*)cb->data + new_end_pos,
268  front_size);
269  } else {
270  memcpy(data, (uint8_t*)cb->data + cb->end_pos - size,
271  size);
272  }
273  }
274 }
275 
276 static inline void circlebuf_pop_front(struct circlebuf *cb, void *data,
277  size_t size)
278 {
279  circlebuf_peek_front(cb, data, size);
280 
281  cb->size -= size;
282  if (!cb->size) {
283  cb->start_pos = cb->end_pos = 0;
284  return;
285  }
286 
287  cb->start_pos += size;
288  if (cb->start_pos >= cb->capacity)
289  cb->start_pos -= cb->capacity;
290 }
291 
292 static inline void circlebuf_pop_back(struct circlebuf *cb, void *data,
293  size_t size)
294 {
295  circlebuf_peek_front(cb, data, size);
296 
297  cb->size -= size;
298  if (!cb->size) {
299  cb->start_pos = cb->end_pos = 0;
300  return;
301  }
302 
303  if (cb->end_pos <= size)
304  cb->end_pos = cb->capacity - (size - cb->end_pos);
305  else
306  cb->end_pos -= size;
307 }
308 
309 static inline void *circlebuf_data(struct circlebuf *cb, size_t idx)
310 {
311  uint8_t *ptr = (uint8_t*)cb->data;
312  size_t offset = cb->start_pos + idx;
313 
314  if (idx > cb->size)
315  return NULL;
316 
317  if (offset >= cb->capacity)
318  offset -= cb->capacity;
319 
320  return ptr + offset;
321 }
322 
323 #ifdef __cplusplus
324 }
325 #endif
Definition: circlebuf.h:32
EXPORT void * brealloc(void *ptr, size_t size)
size_t end_pos
Definition: circlebuf.h:37
unsigned char uint8_t
Definition: vc_stdint.h:27
size_t size
Definition: circlebuf.h:34
size_t capacity
Definition: circlebuf.h:38
size_t start_pos
Definition: circlebuf.h:36
void * data
Definition: circlebuf.h:33
EXPORT void bfree(void *ptr)