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