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 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. 16 */ 17 18 #ifndef lint 19 static char sccsid[] = "@(#)ring.c 1.10 (Berkeley) 06/29/88"; 20 #endif /* not lint */ 21 22 /* 23 * This defines a structure for a ring buffer. 24 * 25 * The circular buffer has two parts: 26 *((( 27 * full: [consume, supply) 28 * empty: [supply, consume) 29 *]]] 30 * 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 49 #if !defined(MIN) 50 #define MIN(a,b) (((a)<(b))? (a):(b)) 51 #endif /* !defined(MIN) */ 52 53 #define ring_subtract(d,a,b) ((((int)(a))-((int)(b)) >= 0)? \ 54 (a)-(b): (((a)-(b))+(d)->size)) 55 56 #define ring_increment(d,a,c) (((a)+(c) < (d)->top)? \ 57 (a)+(c) : (((a)+(c))-(d)->size)) 58 59 #define ring_decrement(d,a,c) (((a)-(c) >= (d)->bottom)? \ 60 (a)-(c) : (((a)-(c))-(d)->size)) 61 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 68 * clock, that when the times are EQUAL, then the buffer is FULL. 69 */ 70 static u_long ring_clock = 0; 71 72 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)) 77 78 79 80 81 82 /* Buffer state transition routines */ 83 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 93 ring->supply = ring->consume = ring->bottom = buffer; 94 95 ring->top = ring->bottom+ring->size; 96 97 return 1; 98 } 99 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 139 /* 140 * Add characters from current segment to ring buffer. 141 */ 142 void 143 ring_supplied(ring, count) 144 Ring *ring; 145 int count; 146 { 147 ring->supply = ring_increment(ring, ring->supply, count); 148 ring->supplytime = ++ring_clock; 149 } 150 151 /* 152 * We have just consumed "c" bytes. 153 */ 154 void 155 ring_consumed(ring, count) 156 Ring *ring; 157 int count; 158 { 159 if (count == 0) /* don't update anything */ 160 return; 161 162 if (ring->mark && 163 (ring_subtract(ring, ring->mark, ring->consume) < count)) { 164 ring->mark = 0; 165 } 166 ring->consume = ring_increment(ring, ring->consume, count); 167 ring->consumetime = ++ring_clock; 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 } 174 } 175 176 177 178 /* Buffer state query routines */ 179 180 181 /* Number of bytes that may be supplied */ 182 int 183 ring_empty_count(ring) 184 Ring *ring; 185 { 186 if (ring_empty(ring)) { /* if empty */ 187 return ring->size; 188 } else { 189 return ring_subtract(ring, ring->consume, ring->supply); 190 } 191 } 192 193 /* number of CONSECUTIVE bytes that may be supplied */ 194 int 195 ring_empty_consecutive(ring) 196 Ring *ring; 197 { 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); 204 } else { 205 /* 206 * else, return what we may. 207 */ 208 return ring_subtract(ring, ring->consume, ring->supply); 209 } 210 } 211 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 216 int 217 ring_full_count(ring) 218 Ring *ring; 219 { 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 } 226 } else { 227 return ring_subtract(ring, ring->mark, ring->consume); 228 } 229 } 230 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 */ 235 int 236 ring_full_consecutive(ring) 237 Ring *ring; 238 { 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 } 245 } else { 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 } 251 } 252 } 253 254 /* 255 * Move data into the "supply" portion of of the ring buffer. 256 */ 257 void 258 ring_supply_data(ring, buffer, count) 259 Ring *ring; 260 char *buffer; 261 int count; 262 { 263 int i; 264 265 while (count) { 266 i = MIN(count, ring_empty_consecutive(ring)); 267 memcpy(ring->supply, buffer, i); 268 ring_supplied(ring, i); 269 count -= i; 270 buffer += i; 271 } 272 } 273 274 275 /* 276 * Move data from the "consume" portion of the ring buffer 277 */ 278 void 279 ring_consume_data(ring, buffer, count) 280 Ring *ring; 281 char *buffer; 282 int count; 283 { 284 int i; 285 286 while (count) { 287 i = MIN(count, ring_full_consecutive(ring)); 288 memcpy(buffer, ring->consume, i); 289 ring_consumed(ring, i); 290 count -= i; 291 buffer += i; 292 } 293 } 294