Subversion Repositories or1k

/*

 * ringq.c -- Ring queue buffering module

 *

 * Copyright (c) GoAhead Software Inc., 1995-2000. All Rights Reserved.

 *

 * See the file "license.txt" for usage and redistribution license requirements

 */

/******************************** Description *********************************/

/*

 *      A ring queue allows maximum utilization of memory for data storage and is

 *      ideal for input/output buffering.  This module provides a highly efficient

 *      implementation and a vehicle for dynamic strings.

 *

 *      WARNING:  This is a public implementation and callers have full access to

 *      the queue structure and pointers.  Change this module very carefully.

 *

 *      This module follows the open/close model.

 *

 *      Operation of a ringq where rq is a pointer to a ringq :

 *

 *              rq->buflen contains the size of the buffer.

 *              rq->buf will point to the start of the buffer.

 *              rq->servp will point to the first (un-consumed) data byte.

 *              rq->endp will point to the next free location to which new data is added

 *              rq->endbuf will point to one past the end of the buffer.

 *

 *      Eg. If the ringq contains the data "abcdef", it might look like :

 *

 *      +-------------------------------------------------------------------+

 *  |   |   |   |   |   |   |   | a | b | c | d | e | f |   |   |   |   |

 *      +-------------------------------------------------------------------+

 *    ^                           ^                       ^               ^

 *    |                           |                       |               |

 *  rq->buf                    rq->servp               rq->endp      rq->enduf

 *

 *      The queue is empty when servp == endp.  This means that the queue will hold

 *      at most rq->buflen -1 bytes.  It is the filler's responsibility to ensure

 *      the ringq is never filled such that servp == endp.

 *

 *      It is the filler's responsibility to "wrap" the endp back to point to

 *      rq->buf when the pointer steps past the end.  Correspondingly it is the

 *      consumers responsibility to "wrap" the servp when it steps to rq->endbuf.

 *      The ringqPutc and ringqGetc routines will do this automatically.

 */

/********************************* Includes ***********************************/

#if UEMF

        #include        "uemf.h"

#else

        #include        "basic/basicInternal.h"

#endif

/*********************************** Defines **********************************/

/*

 *      Faster than a function call

 */

#define RINGQ_LEN(rq) \

        ((rq->servp > rq->endp) ? \

                (rq->buflen + (rq->endp - rq->servp)) : \

                (rq->endp - rq->servp))

/***************************** Forward Declarations ***************************/

static int      ringqGrow(ringq_t *rq);

static int      getBinBlockSize(int size);

int                     ringqGrowCalls = 0;

/*********************************** Code *************************************/

/*

 *      Create a new ringq. "increment" is the amount to increase the size of the

 *      ringq should it need to grow to accomodate data being added. "maxsize" is

 *      an upper limit (sanity level) beyond which the q must not grow. Set maxsize

 *      to -1 to imply no upper limit. The buffer for the ringq is always

 *      dynamically allocated. Set maxsize

 */

int ringqOpen(ringq_t *rq, int initSize, int maxsize)

{

        int     increment;

        a_assert(rq);

        a_assert(initSize >= 0);

        increment = getBinBlockSize(initSize);

        if ((rq->buf = balloc(B_L, (increment))) == NULL) {

                return -1;

        }

        rq->maxsize = maxsize;

        rq->buflen = increment;

        rq->increment = increment;

        rq->endbuf = &rq->buf[rq->buflen];

        rq->servp = rq->buf;

        rq->endp = rq->buf;

        *rq->servp = '\0';

        return 0;

}

/******************************************************************************/

/*

 *      Delete a ringq and free the ringq buffer.

 */

void ringqClose(ringq_t *rq)

{

        a_assert(rq);

        a_assert(rq->buflen == (rq->endbuf - rq->buf));

        if (rq == NULL) {

                return;

        }

        ringqFlush(rq);

        bfree(B_L, (char*) rq->buf);

        rq->buf = NULL;

}

/******************************************************************************/

/*

 *      Return the length of the data in the ringq. Users must fill the queue to

 *      a high water mark of at most one less than the queue size.

 */

int ringqLen(ringq_t *rq)

{

        a_assert(rq);

        a_assert(rq->buflen == (rq->endbuf - rq->buf));

        if (rq->servp > rq->endp) {

                return rq->buflen + rq->endp - rq->servp;

        } else {

                return rq->endp - rq->servp;

        }

}

/******************************************************************************/

/*

 *      Get a byte from the queue

 */

int ringqGetc(ringq_t *rq)

{

        char_t  c;

        char_t* cp;

        a_assert(rq);

        a_assert(rq->buflen == (rq->endbuf - rq->buf));

        if (rq->servp == rq->endp) {

                return -1;

        }

        cp = (char_t*) rq->servp;

        c = *cp++;

        rq->servp = (unsigned char *) cp;

        if (rq->servp >= rq->endbuf) {

                rq->servp = rq->buf;

        }

        return c;

}

/******************************************************************************/

/*

 *      Add a char to the queue. Note if being used to store wide strings

 *      this does not add a trailing '\0'. Grow the q as required.

 */

int ringqPutc(ringq_t *rq, char_t c)

{

        char_t *cp;

        a_assert(rq);

        a_assert(rq->buflen == (rq->endbuf - rq->buf));

        if ((ringqPutBlkMax(rq) < (int) sizeof(char_t)) && !ringqGrow(rq)) {

                return -1;

        }

        cp = (char_t*) rq->endp;

        *cp++ = (char_t) c;

        rq->endp = (unsigned char *) cp;

        if (rq->endp >= rq->endbuf) {

                rq->endp = rq->buf;

        }

        return 0;

}

/******************************************************************************/

/*

 *      Insert a wide character at the front of the queue

 */

int ringqInsertc(ringq_t *rq, char_t c)

{

        char_t *cp;

        a_assert(rq);

        a_assert(rq->buflen == (rq->endbuf - rq->buf));

        if (ringqPutBlkMax(rq) < (int) sizeof(char_t) && !ringqGrow(rq)) {

                return -1;

        }

        if (rq->servp <= rq->buf) {

                rq->servp = rq->endbuf;

        }

        cp = (char_t*) rq->servp;

        *--cp = (char_t) c;

        rq->servp = (unsigned char *) cp;

        return 0;

}

/******************************************************************************/

/*

 *      Add a string to the queue. Add a trailing null (maybe two nulls)

 */

int ringqPutStr(ringq_t *rq, char_t *str)

{

        int             rc;

        a_assert(rq);

        a_assert(str);

        a_assert(rq->buflen == (rq->endbuf - rq->buf));

        rc = ringqPutBlk(rq, (unsigned char*) str, gstrlen(str) * sizeof(char_t));

        *((char_t*) rq->endp) = (char_t) '\0';

        return rc;

}

/******************************************************************************/

/*

 *      Add a null terminator. This does NOT increase the size of the queue

 */

void ringqAddNull(ringq_t *rq)

{

        a_assert(rq);

        a_assert(rq->buflen == (rq->endbuf - rq->buf));

        *((char_t*) rq->endp) = (char_t) '\0';

}

/******************************************************************************/

#if UNICODE

/*

 *      Get a byte from the queue

 */

int ringqGetcA(ringq_t *rq)

{

        unsigned char   c;

        a_assert(rq);

        a_assert(rq->buflen == (rq->endbuf - rq->buf));

        if (rq->servp == rq->endp) {

                return -1;

        }

        c = *rq->servp++;

        if (rq->servp >= rq->endbuf) {

                rq->servp = rq->buf;

        }

        return c;

}

/******************************************************************************/

/*

 *      Add a byte to the queue. Note if being used to store strings this does not

 *      add a trailing '\0'. Grow the q as required.

 */

int ringqPutcA(ringq_t *rq, char c)

{

        a_assert(rq);

        a_assert(rq->buflen == (rq->endbuf - rq->buf));

        if (ringqPutBlkMax(rq) == 0 && !ringqGrow(rq)) {

                return -1;

        }

        *rq->endp++ = (unsigned char) c;

        if (rq->endp >= rq->endbuf) {

                rq->endp = rq->buf;

        }

        return 0;

}

/******************************************************************************/

/*

 *      Insert a byte at the front of the queue

 */

int ringqInsertcA(ringq_t *rq, char c)

{

        a_assert(rq);

        a_assert(rq->buflen == (rq->endbuf - rq->buf));

        if (ringqPutBlkMax(rq) == 0 && !ringqGrow(rq)) {

                return -1;

        }

        if (rq->servp <= rq->buf) {

                rq->servp = rq->endbuf;

        }

        *--rq->servp = (unsigned char) c;

        return 0;

}

/******************************************************************************/

/*

 *      Add a string to the queue. Add a trailing null (not really in the q).

 *      ie. beyond the last valid byte.

 */

int ringqPutStrA(ringq_t *rq, char *str)

{

        int             rc;

        a_assert(rq);

        a_assert(str);

        a_assert(rq->buflen == (rq->endbuf - rq->buf));

        rc = ringqPutBlk(rq, (unsigned char*) str, strlen(str));

        rq->endp[0] = '\0';

        return rc;

}

#endif /* UNICODE */

/******************************************************************************/

/*

 *      Add a block of data to the ringq. Return the number of bytes added.

 *      Grow the q as required.

 */

int ringqPutBlk(ringq_t *rq, unsigned char *buf, int size)

{

        int             this, bytes_put;

        a_assert(rq);

        a_assert(rq->buflen == (rq->endbuf - rq->buf));

        a_assert(buf);

        a_assert(0 <= size);

/*

 *      Loop adding the maximum bytes we can add in a single straight line copy

 */

        bytes_put = 0;

        while (size > 0) {

                this = min(ringqPutBlkMax(rq), size);

                if (this <= 0) {

                        if (! ringqGrow(rq)) {

                                break;

                        }

                        this = min(ringqPutBlkMax(rq), size);

                }

                memcpy(rq->endp, buf, this);

                buf += this;

                rq->endp += this;

                size -= this;

                bytes_put += this;

                if (rq->endp >= rq->endbuf) {

                        rq->endp = rq->buf;

                }

        }

        return bytes_put;

}

/******************************************************************************/

/*

 *      Get a block of data from the ringq. Return the number of bytes returned.

 */

int ringqGetBlk(ringq_t *rq, unsigned char *buf, int size)

{

        int             this, bytes_read;

        a_assert(rq);

        a_assert(rq->buflen == (rq->endbuf - rq->buf));

        a_assert(buf);

        a_assert(0 <= size && size < rq->buflen);

/*

 *      Loop getting the maximum bytes we can get in a single straight line copy

 */

        bytes_read = 0;

        while (size > 0) {

                this = ringqGetBlkMax(rq);

                this = min(this, size);

                if (this <= 0) {

                        break;

                }

                memcpy(buf, rq->servp, this);

                buf += this;

                rq->servp += this;

                size -= this;

                bytes_read += this;

                if (rq->servp >= rq->endbuf) {

                        rq->servp = rq->buf;

                }

        }

        return bytes_read;

}

/******************************************************************************/

/*

 *      Return the maximum number of bytes the ring q can accept via a single

 *      block copy. Useful if the user is doing their own data insertion.

 */

int ringqPutBlkMax(ringq_t *rq)

{

        int             space, in_a_line;

        a_assert(rq);

        a_assert(rq->buflen == (rq->endbuf - rq->buf));

        space = rq->buflen - RINGQ_LEN(rq) - 1;

        in_a_line = rq->endbuf - rq->endp;

        return min(in_a_line, space);

}

/******************************************************************************/

/*

 *      Return the maximum number of bytes the ring q can provide via a single

 *      block copy. Useful if the user is doing their own data retrieval.

 */

int ringqGetBlkMax(ringq_t *rq)

{

        int             len, in_a_line;

        a_assert(rq);

        a_assert(rq->buflen == (rq->endbuf - rq->buf));

        len = RINGQ_LEN(rq);

        in_a_line = rq->endbuf - rq->servp;

        return min(in_a_line, len);

}

/******************************************************************************/

/*

 *      Adjust the endp pointer after the user has copied data into the queue.

 */

void ringqPutBlkAdj(ringq_t *rq, int size)

{

        a_assert(rq);

        a_assert(rq->buflen == (rq->endbuf - rq->buf));

        a_assert(0 <= size && size < rq->buflen);

        rq->endp += size;

        if (rq->endp >= rq->endbuf) {

                rq->endp -= rq->buflen;

        }

/*

 *      Flush the queue if the endp pointer is corrupted via a bad size

 */

        if (rq->endp >= rq->endbuf) {

                error(E_L, E_LOG, T("Bad end pointer"));

                ringqFlush(rq);

        }

}

/******************************************************************************/

/*

 *      Adjust the servp pointer after the user has copied data from the queue.

 */

void ringqGetBlkAdj(ringq_t *rq, int size)

{

        a_assert(rq);

        a_assert(rq->buflen == (rq->endbuf - rq->buf));

        a_assert(0 < size && size < rq->buflen);

        rq->servp += size;

        if (rq->servp >= rq->endbuf) {

                rq->servp -= rq->buflen;

        }

/*

 *      Flush the queue if the servp pointer is corrupted via a bad size

 */

        if (rq->servp >= rq->endbuf) {

                error(E_L, E_LOG, T("Bad serv pointer"));

                ringqFlush(rq);

        }

}

/******************************************************************************/

/*

 *      Flush all data in a ring q.  Reset the pointers.

 */

void ringqFlush(ringq_t *rq)

{

        a_assert(rq);

        a_assert(rq->servp);

        rq->servp = rq->buf;

        rq->endp = rq->buf;

        if (rq->servp) {

                *rq->servp = '\0';

        }

}

/******************************************************************************/

/*

 *      Grow the buffer. Return true if the buffer can be grown. Grow using

 *      the increment size specified when opening the ringq. Don't grow beyond

 *      the maximum possible size.

 */

static int ringqGrow(ringq_t *rq)

{

        unsigned char   *newbuf;

        int                     len;

        a_assert(rq);

        if (rq->maxsize >= 0 && rq->buflen >= rq->maxsize) {

                return 0;

        }

        len = ringqLen(rq);

        if ((newbuf = balloc(B_L, rq->buflen + rq->increment)) == NULL) {

                return 0;

        }

        ringqGetBlk(rq, newbuf, ringqLen(rq));

        bfree(B_L, (char*) rq->buf);

#if OLD

        rq->endp = &newbuf[endp];

        rq->servp = &newbuf[servp];

        rq->endbuf = &newbuf[rq->buflen];

        rq->buf = newbuf;

#endif

        rq->buflen += rq->increment;

        rq->endp = newbuf;

        rq->servp = newbuf;

        rq->buf = newbuf;

        rq->endbuf = &rq->buf[rq->buflen];

        ringqPutBlk(rq, newbuf, len);

/*

 *      Double the increment so the next grow will line up with balloc'ed memory

 */

        rq->increment = getBinBlockSize(2 * rq->increment);

        return 1;

}

/******************************************************************************/

/*

 *      Find the smallest binary memory size that "size" will fit into.  This

 *      makes the ringq and ringqGrow routines much more efficient.  The balloc

 *      routine likes powers of 2 minus 1.

 */

static int      getBinBlockSize(int size)

{

        int     q;

        size = size >> B_SHIFT;

        for (q = 0; size; size >>= 1) {

                q++;

        }

        return (1 << (B_SHIFT + q));

}

/******************************************************************************/