Commit | Line | Data |
---|---|---|
897ce52e KB |
1 | /* |
2 | * Copyright (c) 1988 Regents of the University of California. | |
3 | * All rights reserved. | |
4 | * | |
5 | * Redistribution and use in source and binary forms are permitted | |
b36fc510 KB |
6 | * provided that the above copyright notice and this paragraph are |
7 | * duplicated in all such forms and that any documentation, | |
8 | * advertising materials, and other materials related to such | |
9 | * distribution and use acknowledge that the software was developed | |
10 | * by the University of California, Berkeley. The name of the | |
11 | * University may not be used to endorse or promote products derived | |
12 | * from this software without specific prior written permission. | |
13 | * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR | |
14 | * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED | |
15 | * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. | |
897ce52e KB |
16 | */ |
17 | ||
18 | #ifndef lint | |
b36fc510 | 19 | static char sccsid[] = "@(#)ring.c 1.10 (Berkeley) %G%"; |
897ce52e KB |
20 | #endif /* not lint */ |
21 | ||
cde671b6 | 22 | /* |
8b6750f5 | 23 | * This defines a structure for a ring buffer. |
cde671b6 | 24 | * |
8b6750f5 | 25 | * The circular buffer has two parts: |
cde671b6 | 26 | *((( |
8b6750f5 GM |
27 | * full: [consume, supply) |
28 | * empty: [supply, consume) | |
cde671b6 GM |
29 | *]]] |
30 | * | |
cde671b6 GM |
31 | */ |
32 | ||
33 | #include <stdio.h> | |
34 | #include <errno.h> | |
35 | ||
36 | #ifdef size_t | |
37 | #undef size_t | |
38 | #endif | |
39 | ||
40 | #include <sys/types.h> | |
41 | #include <sys/ioctl.h> | |
42 | #include <sys/socket.h> | |
43 | ||
44 | #include "ring.h" | |
45 | #include "general.h" | |
46 | ||
47 | /* Internal macros */ | |
48 | ||
115a5494 GM |
49 | #if !defined(MIN) |
50 | #define MIN(a,b) (((a)<(b))? (a):(b)) | |
51 | #endif /* !defined(MIN) */ | |
cde671b6 | 52 | |
115a5494 GM |
53 | #define ring_subtract(d,a,b) ((((int)(a))-((int)(b)) >= 0)? \ |
54 | (a)-(b): (((a)-(b))+(d)->size)) | |
cde671b6 GM |
55 | |
56 | #define ring_increment(d,a,c) (((a)+(c) < (d)->top)? \ | |
57 | (a)+(c) : (((a)+(c))-(d)->size)) | |
58 | ||
218b1a4c GM |
59 | #define ring_decrement(d,a,c) (((a)-(c) >= (d)->bottom)? \ |
60 | (a)-(c) : (((a)-(c))-(d)->size)) | |
61 | ||
cde671b6 GM |
62 | |
63 | /* | |
64 | * The following is a clock, used to determine full, empty, etc. | |
65 | * | |
66 | * There is some trickiness here. Since the ring buffers are initialized | |
67 | * to ZERO on allocation, we need to make sure, when interpreting the | |
8b6750f5 | 68 | * clock, that when the times are EQUAL, then the buffer is FULL. |
cde671b6 GM |
69 | */ |
70 | static u_long ring_clock = 0; | |
71 | ||
72 | ||
8b6750f5 GM |
73 | #define ring_empty(d) (((d)->consume == (d)->supply) && \ |
74 | ((d)->consumetime >= (d)->supplytime)) | |
75 | #define ring_full(d) (((d)->supply == (d)->consume) && \ | |
76 | ((d)->supplytime > (d)->consumetime)) | |
cde671b6 GM |
77 | |
78 | ||
79 | ||
80 | ||
81 | ||
82 | /* Buffer state transition routines */ | |
83 | ||
115a5494 GM |
84 | ring_init(ring, buffer, count) |
85 | Ring *ring; | |
86 | char *buffer; | |
87 | int count; | |
88 | { | |
89 | memset((char *)ring, 0, sizeof *ring); | |
90 | ||
91 | ring->size = count; | |
92 | ||
8b6750f5 | 93 | ring->supply = ring->consume = ring->bottom = buffer; |
115a5494 GM |
94 | |
95 | ring->top = ring->bottom+ring->size; | |
96 | ||
97 | return 1; | |
98 | } | |
cde671b6 | 99 | |
218b1a4c GM |
100 | /* Mark routines */ |
101 | ||
102 | /* | |
103 | * Mark the most recently supplied byte. | |
104 | */ | |
105 | ||
106 | void | |
107 | ring_mark(ring) | |
108 | Ring *ring; | |
109 | { | |
110 | ring->mark = ring_decrement(ring, ring->supply, 1); | |
111 | } | |
112 | ||
113 | /* | |
114 | * Is the ring pointing to the mark? | |
115 | */ | |
116 | ||
117 | int | |
118 | ring_at_mark(ring) | |
119 | Ring *ring; | |
120 | { | |
121 | if (ring->mark == ring->consume) { | |
122 | return 1; | |
123 | } else { | |
124 | return 0; | |
125 | } | |
126 | } | |
127 | ||
128 | /* | |
129 | * Clear any mark set on the ring. | |
130 | */ | |
131 | ||
132 | void | |
133 | ring_clear_mark(ring) | |
134 | Ring *ring; | |
135 | { | |
136 | ring->mark = 0; | |
137 | } | |
138 | ||
cde671b6 GM |
139 | /* |
140 | * Add characters from current segment to ring buffer. | |
141 | */ | |
142 | void | |
8b6750f5 | 143 | ring_supplied(ring, count) |
cde671b6 GM |
144 | Ring *ring; |
145 | int count; | |
146 | { | |
8b6750f5 GM |
147 | ring->supply = ring_increment(ring, ring->supply, count); |
148 | ring->supplytime = ++ring_clock; | |
cde671b6 GM |
149 | } |
150 | ||
151 | /* | |
8b6750f5 | 152 | * We have just consumed "c" bytes. |
cde671b6 GM |
153 | */ |
154 | void | |
8b6750f5 | 155 | ring_consumed(ring, count) |
cde671b6 GM |
156 | Ring *ring; |
157 | int count; | |
158 | { | |
ad1c581e GM |
159 | if (count == 0) /* don't update anything */ |
160 | return; | |
161 | ||
218b1a4c GM |
162 | if (ring->mark && |
163 | (ring_subtract(ring, ring->mark, ring->consume) < count)) { | |
164 | ring->mark = 0; | |
165 | } | |
8b6750f5 GM |
166 | ring->consume = ring_increment(ring, ring->consume, count); |
167 | ring->consumetime = ++ring_clock; | |
8166d918 GM |
168 | /* |
169 | * Try to encourage "ring_empty_consecutive()" to be large. | |
170 | */ | |
171 | if (ring_empty(ring)) { | |
172 | ring->consume = ring->supply = ring->bottom; | |
173 | } | |
cde671b6 GM |
174 | } |
175 | ||
e8507c1e | 176 | |
cde671b6 GM |
177 | |
178 | /* Buffer state query routines */ | |
179 | ||
180 | ||
8b6750f5 | 181 | /* Number of bytes that may be supplied */ |
cde671b6 GM |
182 | int |
183 | ring_empty_count(ring) | |
184 | Ring *ring; | |
185 | { | |
8b6750f5 | 186 | if (ring_empty(ring)) { /* if empty */ |
cde671b6 GM |
187 | return ring->size; |
188 | } else { | |
8b6750f5 | 189 | return ring_subtract(ring, ring->consume, ring->supply); |
cde671b6 GM |
190 | } |
191 | } | |
192 | ||
8b6750f5 | 193 | /* number of CONSECUTIVE bytes that may be supplied */ |
cde671b6 GM |
194 | int |
195 | ring_empty_consecutive(ring) | |
196 | Ring *ring; | |
197 | { | |
8b6750f5 GM |
198 | if ((ring->consume < ring->supply) || ring_empty(ring)) { |
199 | /* | |
200 | * if consume is "below" supply, or empty, then | |
201 | * return distance to the top | |
202 | */ | |
203 | return ring_subtract(ring, ring->top, ring->supply); | |
cde671b6 GM |
204 | } else { |
205 | /* | |
206 | * else, return what we may. | |
207 | */ | |
8b6750f5 | 208 | return ring_subtract(ring, ring->consume, ring->supply); |
cde671b6 GM |
209 | } |
210 | } | |
211 | ||
218b1a4c GM |
212 | /* Return the number of bytes that are available for consuming |
213 | * (but don't give more than enough to get to cross over set mark) | |
214 | */ | |
215 | ||
cde671b6 | 216 | int |
8b6750f5 | 217 | ring_full_count(ring) |
cde671b6 GM |
218 | Ring *ring; |
219 | { | |
218b1a4c GM |
220 | if ((ring->mark == 0) || (ring->mark == ring->consume)) { |
221 | if (ring_full(ring)) { | |
222 | return ring->size; /* nothing consumed, but full */ | |
223 | } else { | |
224 | return ring_subtract(ring, ring->supply, ring->consume); | |
225 | } | |
cde671b6 | 226 | } else { |
218b1a4c | 227 | return ring_subtract(ring, ring->mark, ring->consume); |
cde671b6 GM |
228 | } |
229 | } | |
230 | ||
218b1a4c GM |
231 | /* |
232 | * Return the number of CONSECUTIVE bytes available for consuming. | |
233 | * However, don't return more than enough to cross over set mark. | |
234 | */ | |
cde671b6 | 235 | int |
8b6750f5 | 236 | ring_full_consecutive(ring) |
cde671b6 GM |
237 | Ring *ring; |
238 | { | |
218b1a4c GM |
239 | if ((ring->mark == 0) || (ring->mark == ring->consume)) { |
240 | if ((ring->supply < ring->consume) || ring_full(ring)) { | |
241 | return ring_subtract(ring, ring->top, ring->consume); | |
242 | } else { | |
243 | return ring_subtract(ring, ring->supply, ring->consume); | |
244 | } | |
cde671b6 | 245 | } else { |
218b1a4c GM |
246 | if (ring->mark < ring->consume) { |
247 | return ring_subtract(ring, ring->top, ring->consume); | |
248 | } else { /* Else, distance to mark */ | |
249 | return ring_subtract(ring, ring->mark, ring->consume); | |
250 | } | |
cde671b6 GM |
251 | } |
252 | } | |
253 | ||
cde671b6 | 254 | /* |
8b6750f5 | 255 | * Move data into the "supply" portion of of the ring buffer. |
cde671b6 GM |
256 | */ |
257 | void | |
8b6750f5 | 258 | ring_supply_data(ring, buffer, count) |
cde671b6 GM |
259 | Ring *ring; |
260 | char *buffer; | |
261 | int count; | |
262 | { | |
263 | int i; | |
264 | ||
265 | while (count) { | |
115a5494 | 266 | i = MIN(count, ring_empty_consecutive(ring)); |
8b6750f5 GM |
267 | memcpy(ring->supply, buffer, i); |
268 | ring_supplied(ring, i); | |
cde671b6 GM |
269 | count -= i; |
270 | buffer += i; | |
271 | } | |
272 | } | |
273 | ||
274 | ||
275 | /* | |
8b6750f5 | 276 | * Move data from the "consume" portion of the ring buffer |
cde671b6 GM |
277 | */ |
278 | void | |
8b6750f5 | 279 | ring_consume_data(ring, buffer, count) |
cde671b6 GM |
280 | Ring *ring; |
281 | char *buffer; | |
282 | int count; | |
283 | { | |
284 | int i; | |
285 | ||
286 | while (count) { | |
8b6750f5 GM |
287 | i = MIN(count, ring_full_consecutive(ring)); |
288 | memcpy(buffer, ring->consume, i); | |
289 | ring_consumed(ring, i); | |
cde671b6 GM |
290 | count -= i; |
291 | buffer += i; | |
292 | } | |
293 | } |