1 /* $OpenBSD: ring.c,v 1.11 2014/07/22 07:30:24 jsg Exp $ */ 2 /* $NetBSD: ring.c,v 1.7 1996/02/28 21:04:07 thorpej Exp $ */ 3 4 /* 5 * Copyright (c) 1988, 1993 6 * The Regents of the University of California. All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 3. Neither the name of the University nor the names of its contributors 17 * may be used to endorse or promote products derived from this software 18 * without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30 * SUCH DAMAGE. 31 */ 32 33 #include <string.h> 34 #include "ring.h" 35 36 /* 37 * This defines a structure for a ring buffer. 38 * 39 * The circular buffer has two parts: 40 *((( 41 * full: [consume, supply) 42 * empty: [supply, consume) 43 *]]] 44 * 45 */ 46 47 /* Internal macros */ 48 #define ring_subtract(d,a,b) (((a)-(b) >= 0)? \ 49 (a)-(b): (((a)-(b))+(d)->size)) 50 51 #define ring_increment(d,a,c) (((a)+(c) < (d)->top)? \ 52 (a)+(c) : (((a)+(c))-(d)->size)) 53 54 #define ring_decrement(d,a,c) (((a)-(c) >= (d)->bottom)? \ 55 (a)-(c) : (((a)-(c))-(d)->size)) 56 57 58 /* 59 * The following is a clock, used to determine full, empty, etc. 60 * 61 * There is some trickiness here. Since the ring buffers are initialized 62 * to ZERO on allocation, we need to make sure, when interpreting the 63 * clock, that when the times are EQUAL, then the buffer is FULL. 64 */ 65 static unsigned long ring_clock = 0; 66 67 68 #define ring_empty(d) (((d)->consume == (d)->supply) && \ 69 ((d)->consumetime >= (d)->supplytime)) 70 #define ring_full(d) (((d)->supply == (d)->consume) && \ 71 ((d)->supplytime > (d)->consumetime)) 72 73 74 /* Buffer state transition routines */ 75 76 void 77 ring_init(Ring *ring, unsigned char *buffer, int count) 78 { 79 memset(ring, 0, sizeof *ring); 80 81 ring->size = count; 82 83 ring->supply = ring->consume = ring->bottom = buffer; 84 85 ring->top = ring->bottom+ring->size; 86 } 87 88 /* Mark routines */ 89 90 /* 91 * Mark the most recently supplied byte. 92 */ 93 94 void 95 ring_mark(Ring *ring) 96 { 97 ring->mark = ring_decrement(ring, ring->supply, 1); 98 } 99 100 /* 101 * Is the ring pointing to the mark? 102 */ 103 104 int 105 ring_at_mark(Ring *ring) 106 { 107 if (ring->mark == ring->consume) { 108 return 1; 109 } else { 110 return 0; 111 } 112 } 113 114 /* 115 * Clear any mark set on the ring. 116 */ 117 118 void 119 ring_clear_mark(Ring *ring) 120 { 121 ring->mark = NULL; 122 } 123 124 /* 125 * Add characters from current segment to ring buffer. 126 */ 127 void 128 ring_supplied(Ring *ring, int count) 129 { 130 ring->supply = ring_increment(ring, ring->supply, count); 131 ring->supplytime = ++ring_clock; 132 } 133 134 /* 135 * We have just consumed "c" bytes. 136 */ 137 void 138 ring_consumed(Ring *ring, int count) 139 { 140 if (count == 0) /* don't update anything */ 141 return; 142 143 if (ring->mark && 144 (ring_subtract(ring, ring->mark, ring->consume) < count)) { 145 ring->mark = NULL; 146 } 147 ring->consume = ring_increment(ring, ring->consume, count); 148 ring->consumetime = ++ring_clock; 149 /* 150 * Try to encourage "ring_empty_consecutive()" to be large. 151 */ 152 if (ring_empty(ring)) { 153 ring->consume = ring->supply = ring->bottom; 154 } 155 } 156 157 158 /* Buffer state query routines */ 159 160 161 /* Number of bytes that may be supplied */ 162 int 163 ring_empty_count(Ring *ring) 164 { 165 if (ring_empty(ring)) { /* if empty */ 166 return ring->size; 167 } else { 168 return ring_subtract(ring, ring->consume, ring->supply); 169 } 170 } 171 172 /* number of CONSECUTIVE bytes that may be supplied */ 173 int 174 ring_empty_consecutive(Ring *ring) 175 { 176 if ((ring->consume < ring->supply) || ring_empty(ring)) { 177 /* 178 * if consume is "below" supply, or empty, then 179 * return distance to the top 180 */ 181 return ring_subtract(ring, ring->top, ring->supply); 182 } else { 183 /* 184 * else, return what we may. 185 */ 186 return ring_subtract(ring, ring->consume, ring->supply); 187 } 188 } 189 190 /* Return the number of bytes that are available for consuming 191 * (but don't give more than enough to get to cross over set mark) 192 */ 193 194 int 195 ring_full_count(Ring *ring) 196 { 197 if ((ring->mark == NULL) || (ring->mark == ring->consume)) { 198 if (ring_full(ring)) { 199 return ring->size; /* nothing consumed, but full */ 200 } else { 201 return ring_subtract(ring, ring->supply, ring->consume); 202 } 203 } else { 204 return ring_subtract(ring, ring->mark, ring->consume); 205 } 206 } 207 208 /* 209 * Return the number of CONSECUTIVE bytes available for consuming. 210 * However, don't return more than enough to cross over set mark. 211 */ 212 int 213 ring_full_consecutive(Ring *ring) 214 { 215 if ((ring->mark == NULL) || (ring->mark == ring->consume)) { 216 if ((ring->supply < ring->consume) || ring_full(ring)) { 217 return ring_subtract(ring, ring->top, ring->consume); 218 } else { 219 return ring_subtract(ring, ring->supply, ring->consume); 220 } 221 } else { 222 if (ring->mark < ring->consume) { 223 return ring_subtract(ring, ring->top, ring->consume); 224 } else { /* Else, distance to mark */ 225 return ring_subtract(ring, ring->mark, ring->consume); 226 } 227 } 228 } 229 230 /* 231 * Move data into the "supply" portion of of the ring buffer. 232 */ 233 void 234 ring_supply_data(Ring *ring, unsigned char *buffer, int count) 235 { 236 int i; 237 238 while (count) { 239 i = ring_empty_consecutive(ring); 240 if (i > count) 241 i = count; 242 memcpy(ring->supply, buffer, i); 243 ring_supplied(ring, i); 244 count -= i; 245 buffer += i; 246 } 247 } 248