source: rtems/c/src/libnetworking/rtems_webserver/ringq.c @ d0d73ec

4.104.114.84.95
Last change on this file since d0d73ec was a6b4c0df, checked in by Joel Sherrill <joel.sherrill@…>, on 09/01/00 at 10:57:21

2000-08-30 Joel Sherrill <joel@…>

  • Merged version 2.1 of GoAhead? webserver. This update was submitted by Antti P Miettinen <antti.p.miettinen@…>.
  • NOTES, base64.c, ejIntrn.h, emfdb.c, emfdb.h, md5.h, md5c.c, um.c, um.h: New files.
  • wbase64.c: Removed.
  • Makefile.am, asp.c, balloc.c, default.c, ej.h, ejlex.c, ejparse.c, form.c, h.c, handler.c, mime.c, misc.c, ringq.c, rom.c, security.c, socket.c, sym.c, uemf.c, uemf.h, url.c, value.c, webcomp.c, webmain.c, webpage.c, webrom.c, webs.c, webs.h, websuemf.c, wsIntrn.h: Modified.
  • Property mode set to 100644
File size: 13.5 KB
Line 
1/*
2 * ringq.c -- Ring queue buffering module
3 *
4 * Copyright (c) GoAhead Software Inc., 1995-2000. All Rights Reserved.
5 *
6 * See the file "license.txt" for usage and redistribution license requirements
7 */
8
9/******************************** Description *********************************/
10
11/*
12 *      A ring queue allows maximum utilization of memory for data storage and is
13 *      ideal for input/output buffering.  This module provides a highly efficient
14 *      implementation and a vehicle for dynamic strings.
15 *
16 *      WARNING:  This is a public implementation and callers have full access to
17 *      the queue structure and pointers.  Change this module very carefully.
18 *
19 *      This module follows the open/close model.
20 *
21 *      Operation of a ringq where rq is a pointer to a ringq :
22 *
23 *              rq->buflen contains the size of the buffer.
24 *              rq->buf will point to the start of the buffer.
25 *              rq->servp will point to the first (un-consumed) data byte.
26 *              rq->endp will point to the next free location to which new data is added
27 *              rq->endbuf will point to one past the end of the buffer.
28 *
29 *      Eg. If the ringq contains the data "abcdef", it might look like :
30 *
31 *      +-------------------------------------------------------------------+
32 *  |   |   |   |   |   |   |   | a | b | c | d | e | f |   |   |   |   |
33 *      +-------------------------------------------------------------------+
34 *    ^                           ^                       ^               ^
35 *    |                           |                       |               |
36 *  rq->buf                    rq->servp               rq->endp      rq->enduf
37 *     
38 *      The queue is empty when servp == endp.  This means that the queue will hold
39 *      at most rq->buflen -1 bytes.  It is the filler's responsibility to ensure
40 *      the ringq is never filled such that servp == endp.
41 *
42 *      It is the filler's responsibility to "wrap" the endp back to point to
43 *      rq->buf when the pointer steps past the end.  Correspondingly it is the
44 *      consumers responsibility to "wrap" the servp when it steps to rq->endbuf.
45 *      The ringqPutc and ringqGetc routines will do this automatically.
46 */
47
48/********************************* Includes ***********************************/
49
50#if UEMF
51        #include        "uemf.h"
52#else
53        #include        "basic/basicInternal.h"
54#endif
55
56/*********************************** Defines **********************************/
57/*
58 *      Faster than a function call
59 */
60
61#define RINGQ_LEN(rq) \
62        ((rq->servp > rq->endp) ? \
63                (rq->buflen + (rq->endp - rq->servp)) : \
64                (rq->endp - rq->servp))
65
66/***************************** Forward Declarations ***************************/
67
68static int      ringqGrow(ringq_t *rq);
69static int      getBinBlockSize(int size);
70
71int                     ringqGrowCalls = 0;
72
73/*********************************** Code *************************************/
74/*
75 *      Create a new ringq. "increment" is the amount to increase the size of the
76 *      ringq should it need to grow to accomodate data being added. "maxsize" is
77 *      an upper limit (sanity level) beyond which the q must not grow. Set maxsize
78 *      to -1 to imply no upper limit. The buffer for the ringq is always
79 *      dynamically allocated. Set maxsize
80 */
81
82int ringqOpen(ringq_t *rq, int initSize, int maxsize)
83{
84        int     increment;
85
86        a_assert(rq);
87        a_assert(initSize >= 0);
88
89        increment = getBinBlockSize(initSize);
90        if ((rq->buf = balloc(B_L, (increment))) == NULL) {
91                return -1;
92        }
93        rq->maxsize = maxsize;
94        rq->buflen = increment;
95        rq->increment = increment;
96        rq->endbuf = &rq->buf[rq->buflen];
97        rq->servp = rq->buf;
98        rq->endp = rq->buf;
99        *rq->servp = '\0';
100        return 0;
101}
102
103/******************************************************************************/
104/*
105 *      Delete a ringq and free the ringq buffer.
106 */
107
108void ringqClose(ringq_t *rq)
109{
110        a_assert(rq);
111        a_assert(rq->buflen == (rq->endbuf - rq->buf));
112
113        if (rq == NULL) {
114                return;
115        }
116
117        ringqFlush(rq);
118        bfree(B_L, (char*) rq->buf);
119        rq->buf = NULL;
120}
121
122/******************************************************************************/
123/*
124 *      Return the length of the data in the ringq. Users must fill the queue to
125 *      a high water mark of at most one less than the queue size.
126 */
127
128int ringqLen(ringq_t *rq)
129{
130        a_assert(rq);
131        a_assert(rq->buflen == (rq->endbuf - rq->buf));
132
133        if (rq->servp > rq->endp) {
134                return rq->buflen + rq->endp - rq->servp;
135        } else {
136                return rq->endp - rq->servp;
137        }
138}
139
140/******************************************************************************/
141/*
142 *      Get a byte from the queue
143 */
144
145int ringqGetc(ringq_t *rq)
146{
147        char_t  c;
148        char_t* cp;
149
150        a_assert(rq);
151        a_assert(rq->buflen == (rq->endbuf - rq->buf));
152
153        if (rq->servp == rq->endp) {
154                return -1;
155        }
156
157        cp = (char_t*) rq->servp;
158        c = *cp++;
159        rq->servp = (unsigned char *) cp;
160        if (rq->servp >= rq->endbuf) {
161                rq->servp = rq->buf;
162        }
163        return c;
164}
165
166/******************************************************************************/
167/*
168 *      Add a char to the queue. Note if being used to store wide strings
169 *      this does not add a trailing '\0'. Grow the q as required.
170 */
171
172int ringqPutc(ringq_t *rq, char_t c)
173{
174        char_t *cp;
175
176        a_assert(rq);
177        a_assert(rq->buflen == (rq->endbuf - rq->buf));
178
179        if ((ringqPutBlkMax(rq) < (int) sizeof(char_t)) && !ringqGrow(rq)) {
180                return -1;
181        }
182
183        cp = (char_t*) rq->endp;
184        *cp++ = (char_t) c;
185        rq->endp = (unsigned char *) cp;
186        if (rq->endp >= rq->endbuf) {
187                rq->endp = rq->buf;
188        }
189        return 0;
190}
191
192/******************************************************************************/
193/*
194 *      Insert a wide character at the front of the queue
195 */
196
197int ringqInsertc(ringq_t *rq, char_t c)
198{
199        char_t *cp;
200
201        a_assert(rq);
202        a_assert(rq->buflen == (rq->endbuf - rq->buf));
203
204        if (ringqPutBlkMax(rq) < (int) sizeof(char_t) && !ringqGrow(rq)) {
205                return -1;
206        }
207        if (rq->servp <= rq->buf) {
208                rq->servp = rq->endbuf;
209        }
210        cp = (char_t*) rq->servp;
211        *--cp = (char_t) c;
212        rq->servp = (unsigned char *) cp;
213        return 0;
214}
215
216/******************************************************************************/
217/*
218 *      Add a string to the queue. Add a trailing null (maybe two nulls)
219 */
220
221int ringqPutStr(ringq_t *rq, char_t *str)
222{
223        int             rc;
224
225        a_assert(rq);
226        a_assert(str);
227        a_assert(rq->buflen == (rq->endbuf - rq->buf));
228
229        rc = ringqPutBlk(rq, (unsigned char*) str, gstrlen(str) * sizeof(char_t));
230        *((char_t*) rq->endp) = (char_t) '\0';
231        return rc;
232}
233
234/******************************************************************************/
235/*
236 *      Add a null terminator. This does NOT increase the size of the queue
237 */
238
239void ringqAddNull(ringq_t *rq)
240{
241        a_assert(rq);
242        a_assert(rq->buflen == (rq->endbuf - rq->buf));
243
244        *((char_t*) rq->endp) = (char_t) '\0';
245}
246
247/******************************************************************************/
248#if UNICODE
249/*
250 *      Get a byte from the queue
251 */
252
253int ringqGetcA(ringq_t *rq)
254{
255        unsigned char   c;
256
257        a_assert(rq);
258        a_assert(rq->buflen == (rq->endbuf - rq->buf));
259
260        if (rq->servp == rq->endp) {
261                return -1;
262        }
263
264        c = *rq->servp++;
265        if (rq->servp >= rq->endbuf) {
266                rq->servp = rq->buf;
267        }
268        return c;
269}
270
271/******************************************************************************/
272/*
273 *      Add a byte to the queue. Note if being used to store strings this does not
274 *      add a trailing '\0'. Grow the q as required.
275 */
276
277int ringqPutcA(ringq_t *rq, char c)
278{
279        a_assert(rq);
280        a_assert(rq->buflen == (rq->endbuf - rq->buf));
281
282        if (ringqPutBlkMax(rq) == 0 && !ringqGrow(rq)) {
283                return -1;
284        }
285
286        *rq->endp++ = (unsigned char) c;
287        if (rq->endp >= rq->endbuf) {
288                rq->endp = rq->buf;
289        }
290        return 0;
291}
292
293/******************************************************************************/
294/*
295 *      Insert a byte at the front of the queue
296 */
297
298int ringqInsertcA(ringq_t *rq, char c)
299{
300        a_assert(rq);
301        a_assert(rq->buflen == (rq->endbuf - rq->buf));
302
303        if (ringqPutBlkMax(rq) == 0 && !ringqGrow(rq)) {
304                return -1;
305        }
306        if (rq->servp <= rq->buf) {
307                rq->servp = rq->endbuf;
308        }
309        *--rq->servp = (unsigned char) c;
310        return 0;
311}
312
313/******************************************************************************/
314/*
315 *      Add a string to the queue. Add a trailing null (not really in the q).
316 *      ie. beyond the last valid byte.
317 */
318
319int ringqPutStrA(ringq_t *rq, char *str)
320{
321        int             rc;
322
323        a_assert(rq);
324        a_assert(str);
325        a_assert(rq->buflen == (rq->endbuf - rq->buf));
326
327        rc = ringqPutBlk(rq, (unsigned char*) str, strlen(str));
328        rq->endp[0] = '\0';
329        return rc;
330}
331
332#endif /* UNICODE */
333/******************************************************************************/
334/*
335 *      Add a block of data to the ringq. Return the number of bytes added.
336 *      Grow the q as required.
337 */
338
339int ringqPutBlk(ringq_t *rq, unsigned char *buf, int size)
340{
341        int             this, bytes_put;
342
343        a_assert(rq);
344        a_assert(rq->buflen == (rq->endbuf - rq->buf));
345        a_assert(buf);
346        a_assert(0 <= size);
347
348/*
349 *      Loop adding the maximum bytes we can add in a single straight line copy
350 */
351        bytes_put = 0;
352        while (size > 0) {
353                this = min(ringqPutBlkMax(rq), size);
354                if (this <= 0) {
355                        if (! ringqGrow(rq)) {
356                                break;
357                        }
358                        this = min(ringqPutBlkMax(rq), size);
359                }
360
361                memcpy(rq->endp, buf, this);
362                buf += this;
363                rq->endp += this;
364                size -= this;
365                bytes_put += this;
366
367                if (rq->endp >= rq->endbuf) {
368                        rq->endp = rq->buf;
369                }
370        }
371        return bytes_put;
372}
373
374/******************************************************************************/
375/*
376 *      Get a block of data from the ringq. Return the number of bytes returned.
377 */
378
379int ringqGetBlk(ringq_t *rq, unsigned char *buf, int size)
380{
381        int             this, bytes_read;
382
383        a_assert(rq);
384        a_assert(rq->buflen == (rq->endbuf - rq->buf));
385        a_assert(buf);
386        a_assert(0 <= size && size < rq->buflen);
387
388/*
389 *      Loop getting the maximum bytes we can get in a single straight line copy
390 */
391        bytes_read = 0;
392        while (size > 0) {
393                this = ringqGetBlkMax(rq);
394                this = min(this, size);
395                if (this <= 0) {
396                        break;
397                }
398
399                memcpy(buf, rq->servp, this);
400                buf += this;
401                rq->servp += this;
402                size -= this;
403                bytes_read += this;
404
405                if (rq->servp >= rq->endbuf) {
406                        rq->servp = rq->buf;
407                }
408        }
409        return bytes_read;
410}
411
412/******************************************************************************/
413/*
414 *      Return the maximum number of bytes the ring q can accept via a single
415 *      block copy. Useful if the user is doing their own data insertion.
416 */
417
418int ringqPutBlkMax(ringq_t *rq)
419{
420        int             space, in_a_line;
421
422        a_assert(rq);
423        a_assert(rq->buflen == (rq->endbuf - rq->buf));
424       
425        space = rq->buflen - RINGQ_LEN(rq) - 1;
426        in_a_line = rq->endbuf - rq->endp;
427
428        return min(in_a_line, space);
429}
430
431/******************************************************************************/
432/*
433 *      Return the maximum number of bytes the ring q can provide via a single
434 *      block copy. Useful if the user is doing their own data retrieval.
435 */
436
437int ringqGetBlkMax(ringq_t *rq)
438{
439        int             len, in_a_line;
440
441        a_assert(rq);
442        a_assert(rq->buflen == (rq->endbuf - rq->buf));
443
444        len = RINGQ_LEN(rq);
445        in_a_line = rq->endbuf - rq->servp;
446
447        return min(in_a_line, len);
448}
449
450/******************************************************************************/
451/*
452 *      Adjust the endp pointer after the user has copied data into the queue.
453 */
454
455void ringqPutBlkAdj(ringq_t *rq, int size)
456{
457        a_assert(rq);
458        a_assert(rq->buflen == (rq->endbuf - rq->buf));
459        a_assert(0 <= size && size < rq->buflen);
460
461        rq->endp += size;
462        if (rq->endp >= rq->endbuf) {
463                rq->endp -= rq->buflen;
464        }
465/*
466 *      Flush the queue if the endp pointer is corrupted via a bad size
467 */
468        if (rq->endp >= rq->endbuf) {
469                error(E_L, E_LOG, T("Bad end pointer"));
470                ringqFlush(rq);
471        }
472}
473
474/******************************************************************************/
475/*
476 *      Adjust the servp pointer after the user has copied data from the queue.
477 */
478
479void ringqGetBlkAdj(ringq_t *rq, int size)
480{
481        a_assert(rq);
482        a_assert(rq->buflen == (rq->endbuf - rq->buf));
483        a_assert(0 < size && size < rq->buflen);
484
485        rq->servp += size;
486        if (rq->servp >= rq->endbuf) {
487                rq->servp -= rq->buflen;
488        }
489/*
490 *      Flush the queue if the servp pointer is corrupted via a bad size
491 */
492        if (rq->servp >= rq->endbuf) {
493                error(E_L, E_LOG, T("Bad serv pointer"));
494                ringqFlush(rq);
495        }
496}
497
498/******************************************************************************/
499/*
500 *      Flush all data in a ring q.  Reset the pointers.
501 */
502
503void ringqFlush(ringq_t *rq)
504{
505        a_assert(rq);
506        a_assert(rq->servp);
507
508        rq->servp = rq->buf;
509        rq->endp = rq->buf;
510        if (rq->servp) {
511                *rq->servp = '\0';
512        }
513}
514
515/******************************************************************************/
516/*
517 *      Grow the buffer. Return true if the buffer can be grown. Grow using
518 *      the increment size specified when opening the ringq. Don't grow beyond
519 *      the maximum possible size.
520 */
521
522static int ringqGrow(ringq_t *rq)
523{
524        unsigned char   *newbuf;
525        int                     len;
526
527        a_assert(rq);
528
529        if (rq->maxsize >= 0 && rq->buflen >= rq->maxsize) {
530                return 0;
531        }
532
533        len = ringqLen(rq);
534
535        if ((newbuf = balloc(B_L, rq->buflen + rq->increment)) == NULL) {
536                return 0;
537        }
538        ringqGetBlk(rq, newbuf, ringqLen(rq));
539        bfree(B_L, (char*) rq->buf);
540
541#if OLD
542        rq->endp = &newbuf[endp];
543        rq->servp = &newbuf[servp];
544        rq->endbuf = &newbuf[rq->buflen];
545        rq->buf = newbuf;
546#endif
547
548        rq->buflen += rq->increment;
549        rq->endp = newbuf;
550        rq->servp = newbuf;
551        rq->buf = newbuf;
552        rq->endbuf = &rq->buf[rq->buflen];
553
554        ringqPutBlk(rq, newbuf, len);
555
556/*
557 *      Double the increment so the next grow will line up with balloc'ed memory
558 */
559        rq->increment = getBinBlockSize(2 * rq->increment);
560
561        return 1;
562}
563
564/******************************************************************************/
565/*
566 *      Find the smallest binary memory size that "size" will fit into.  This
567 *      makes the ringq and ringqGrow routines much more efficient.  The balloc
568 *      routine likes powers of 2 minus 1.
569 */
570
571static int      getBinBlockSize(int size)
572{
573        int     q;
574
575        size = size >> B_SHIFT;
576        for (q = 0; size; size >>= 1) {
577                q++;
578        }
579        return (1 << (B_SHIFT + q));
580}
581
582/******************************************************************************/
Note: See TracBrowser for help on using the repository browser.