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