1 /*
2 **
3 **
4 ** Copyright (C) 2014-2021 Cisco and/or its affiliates. All rights reserved.
5 ** Copyright (C) 2013-2013 Sourcefire, Inc.
6 **
7 ** This program is free software; you can redistribute it and/or modify
8 ** it under the terms of the GNU General Public License Version 2 as
9 ** published by the Free Software Foundation. You may not use, modify or
10 ** distribute this program under any other version of the GNU General
11 ** Public License.
12 **
13 ** This program is distributed in the hope that it will be useful,
14 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
15 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 ** GNU General Public License for more details.
17 **
18 ** You should have received a copy of the GNU General Public License
19 ** along with this program; if not, write to the Free Software
20 ** Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
21 **
22 ** Author(s): Hui Cao <hcao@sourcefire.com>
23 **
24 ** NOTES
25 **
26 ** Circular buffer is thread safe for one writer and one reader thread
27 **
28 ** This implementaton is inspired by one slot open approach.
29 ** See http://en.wikipedia.org/wiki/Circular_buffer
30 **
31 ** 5.25.13 - Initial Source Code. Hui Cao
32 */
33
34 #include "sf_types.h"
35 #include "circular_buffer.h"
36
37 #include <stdio.h>
38 #include <stdlib.h>
39
40 /* Circular buffer object */
41 struct _CircularBuffer{
42
43 uint64_t size; /* maximum number of elements */
44 uint64_t start; /* index of oldest element, reader update only */
45 uint64_t end; /* index to write new element, writer update only*/
46 uint64_t under_run;
47 uint64_t over_run;
48 ElemType *elems; /* vector of elements */
49 uint64_t total_write;
50 uint64_t total_read;
51 };
52
53 /* This approach adds one bit to end and start pointers */
54
cbuffer_init(uint64_t size)55 CircularBuffer * cbuffer_init(uint64_t size)
56 {
57 CircularBuffer* cb = calloc(1, sizeof(*cb));
58
59 if ( !cb )
60 return NULL;
61
62 cb->size = size + 1;
63
64 cb->elems = (ElemType *)calloc(cb->size, sizeof(ElemType));
65 if (!cb->elems)
66 {
67 free(cb);
68 return NULL;
69 }
70
71 return cb;
72 }
73
74
cbuffer_free(CircularBuffer * cb)75 void cbuffer_free(CircularBuffer *cb)
76 {
77 if(cb && cb->elems)
78 {
79 free(cb->elems);
80 cb->elems = NULL;
81 }
82
83 free(cb);
84 }
85 /* We use mirror flag to detection full or empty efficiently*/
cbuffer_is_full(CircularBuffer * cb)86 int cbuffer_is_full(CircularBuffer *cb)
87 {
88 uint64_t next = cb->end + 1;
89
90 if ( next == cb->size )
91 next = 0;
92
93 return (next == cb->start);
94 }
95
96 /* We use mirror flag to detection full or empty efficiently*/
cbuffer_is_empty(CircularBuffer * cb)97 int cbuffer_is_empty(CircularBuffer *cb)
98 {
99 return (cb->end == cb->start);
100 }
101
102 /* Returns number of elements in use*/
cbuffer_used(CircularBuffer * cb)103 uint64_t cbuffer_used(CircularBuffer *cb)
104 {
105 /* cb->end < cb->start means passing the end of buffer */
106 if (cb->end < cb->start)
107 {
108 return (cb->size + cb->end - cb->start);
109 }
110 else
111 {
112 return (cb->end - cb->start);
113 }
114 }
115
116 /* Returns number of free elements*/
cbuffer_available(CircularBuffer * cb)117 uint64_t cbuffer_available(CircularBuffer *cb)
118 {
119 return (cbuffer_size(cb) - cbuffer_used(cb));
120 }
121
122 /* Returns total number of elements*/
cbuffer_size(CircularBuffer * cb)123 uint64_t cbuffer_size(CircularBuffer *cb)
124 {
125 return (cb->size - 1);
126 }
127
128 /*
129 * Add one element to the buffer,
130 *
131 * Args:
132 * CircularBuffer *: buffer
133 * ElemType elem: the element to be added
134 * Return:
135 * CB_FAIL
136 * CB_SUCCESS
137 */
cbuffer_write(CircularBuffer * cb,const ElemType elem)138 int cbuffer_write(CircularBuffer *cb, const ElemType elem)
139 {
140 uint64_t w = cb->end;
141
142 if ( cbuffer_is_full (cb)) /* full, return error */
143 {
144 cb->over_run++;
145 return CB_FAIL;
146 }
147
148 cb->elems[w++] = elem;
149 if ( w == cb->size )
150 w = 0;
151
152 cb->end = w;
153 cb->total_write++;
154
155 return CB_SUCCESS;
156 }
157
158 /*
159 * Read one element from the buffer and remove it from buffer,
160 *
161 * Args:
162 * CircularBuffer *: buffer
163 * ElemType *elem: the element pointer to be stored
164 * Return:
165 * CB_FAIL
166 * CB_SUCCESS
167 */
cbuffer_read(CircularBuffer * cb,ElemType * elem)168 int cbuffer_read(CircularBuffer *cb, ElemType *elem)
169 {
170 uint64_t r = cb->start;
171
172 if (cbuffer_is_empty(cb)) /* Empty, return error */
173 {
174 cb->under_run++;
175 return CB_FAIL;
176 }
177
178 *elem = cb->elems[r++];
179 if ( r == cb->size )
180 r = 0;
181
182 cb->start = r;
183 cb->total_read++;
184
185 return CB_SUCCESS;
186 }
187
188 /*
189 * Read one element from the buffer and no change on buffer
190 *
191 * Args:
192 * CircularBuffer *: buffer
193 * ElemType *elem: the element pointer to be stored
194 * Return:
195 * CB_FAIL
196 * CB_SUCCESS
197 */
cbuffer_peek(CircularBuffer * cb,ElemType * elem)198 int cbuffer_peek(CircularBuffer *cb, ElemType *elem) {
199
200 if (cbuffer_is_empty(cb)) /* Empty, return error */
201 return CB_FAIL;
202
203 *elem = cb->elems[cb->start];
204
205 return CB_SUCCESS;
206 }
207
208 /* Returns total number of reads*/
cbuffer_num_reads(CircularBuffer * cb)209 uint64_t cbuffer_num_reads(CircularBuffer *cb)
210 {
211 return (cb->total_read);
212 }
213
214 /* Returns total number of writes*/
cbuffer_num_writes(CircularBuffer * cb)215 uint64_t cbuffer_num_writes(CircularBuffer *cb)
216 {
217 return (cb->total_write);
218 }
219
220 /* Returns total number of writer overruns*/
cbuffer_num_over_runs(CircularBuffer * cb)221 uint64_t cbuffer_num_over_runs(CircularBuffer *cb)
222 {
223 return (cb->over_run);
224 }
225
226 /* Returns total number of reader overruns*/
cbuffer_num_under_runs(CircularBuffer * cb)227 uint64_t cbuffer_num_under_runs(CircularBuffer *cb)
228 {
229 return (cb->under_run);
230 }
231