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_peek_front(struct circlebuf *cb, void *data,
193  size_t size)
194 {
195  assert(size <= cb->size);
196 
197  if (data) {
198  size_t start_size = cb->capacity - cb->start_pos;
199 
200  if (start_size < size) {
201  memcpy(data, (uint8_t*)cb->data + cb->start_pos,
202  start_size);
203  memcpy((uint8_t*)data + start_size, cb->data,
204  size - start_size);
205  } else {
206  memcpy(data, (uint8_t*)cb->data + cb->start_pos, size);
207  }
208  }
209 }
210 
211 static inline void circlebuf_peek_back(struct circlebuf *cb, void *data,
212  size_t size)
213 {
214  assert(size <= cb->size);
215 
216  if (data) {
217  size_t back_size = (cb->end_pos ? cb->end_pos : cb->capacity);
218 
219  if (back_size < size) {
220  size_t front_size = size - back_size;
221  size_t new_end_pos = cb->capacity - front_size;
222 
223  memcpy((uint8_t*)data + (size - back_size), cb->data,
224  back_size);
225  memcpy(data, (uint8_t*)cb->data + new_end_pos,
226  front_size);
227  } else {
228  memcpy(data, (uint8_t*)cb->data + cb->end_pos - size,
229  size);
230  }
231  }
232 }
233 
234 static inline void circlebuf_pop_front(struct circlebuf *cb, void *data,
235  size_t size)
236 {
237  circlebuf_peek_front(cb, data, size);
238 
239  cb->size -= size;
240  cb->start_pos += size;
241  if (cb->start_pos >= cb->capacity)
242  cb->start_pos -= cb->capacity;
243 }
244 
245 static inline void circlebuf_pop_back(struct circlebuf *cb, void *data,
246  size_t size)
247 {
248  circlebuf_peek_front(cb, data, size);
249 
250  cb->size -= size;
251  if (cb->end_pos <= size)
252  cb->end_pos = cb->capacity - (size - cb->end_pos);
253  else
254  cb->end_pos -= size;
255 }
256 
257 static inline void *circlebuf_data(struct circlebuf *cb, size_t idx)
258 {
259  uint8_t *ptr = (uint8_t*)cb->data;
260  size_t offset = cb->start_pos + idx;
261 
262  if (idx > cb->size)
263  return NULL;
264 
265  if (offset >= cb->capacity)
266  offset -= cb->capacity;
267 
268  return ptr + offset;
269 }
270 
271 #ifdef __cplusplus
272 }
273 #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)