queue.c

Go to the documentation of this file.

/*====================================================================*
 -  Copyright (C) 2001 Leptonica.  All rights reserved.
 -
 -  Redistribution and use in source and binary forms, with or without
 -  modification, are permitted provided that the following conditions
 -  are met:
 -  1. Redistributions of source code must retain the above copyright
 -     notice, this list of conditions and the following disclaimer.
 -  2. Redistributions in binary form must reproduce the above
 -     copyright notice, this list of conditions and the following
 -     disclaimer in the documentation and/or other materials
 -     provided with the distribution.
 -
 -  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 -  ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 -  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 -  A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL ANY
 -  CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 -  EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 -  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 -  PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 -  OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 -  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 -  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *====================================================================*/

#include <string.h>
#include "allheaders.h"

static const l_int32  MIN_BUFFER_SIZE = 20;             /* n'importe quoi */
static const l_int32  INITIAL_BUFFER_ARRAYSIZE = 1024;  /* n'importe quoi */

    /* Static function */
static l_int32 lqueueExtendArray(L_QUEUE *lq);


/*--------------------------------------------------------------------------*
 *                         L_Queue create/destroy                           *
 *--------------------------------------------------------------------------*/
L_QUEUE *
lqueueCreate(l_int32  nalloc)
{
L_QUEUE  *lq;

    PROCNAME("lqueueCreate");

    if (nalloc < MIN_BUFFER_SIZE)
        nalloc = INITIAL_BUFFER_ARRAYSIZE;

    lq = (L_QUEUE *)LEPT_CALLOC(1, sizeof(L_QUEUE));
    if ((lq->array = (void **)LEPT_CALLOC(nalloc, sizeof(void *))) == NULL) {
        lqueueDestroy(&lq, 0);
        return (L_QUEUE *)ERROR_PTR("ptr array not made", procName, NULL);
    }
    lq->nalloc = nalloc;
    lq->nhead = lq->nelem = 0;
    return lq;
}


void
lqueueDestroy(L_QUEUE  **plq,
              l_int32    freeflag)
{
void     *item;
L_QUEUE  *lq;

    PROCNAME("lqueueDestroy");

    if (plq == NULL) {
        L_WARNING("ptr address is NULL\n", procName);
        return;
    }
    if ((lq = *plq) == NULL)
        return;

    if (freeflag) {
        while(lq->nelem > 0) {
            item = lqueueRemove(lq);
            LEPT_FREE(item);
        }
    } else if (lq->nelem > 0) {
        L_WARNING("memory leak of %d items in lqueue!\n", procName, lq->nelem);
    }

    if (lq->array)
        LEPT_FREE(lq->array);
    if (lq->stack)
        lstackDestroy(&lq->stack, freeflag);
    LEPT_FREE(lq);
    *plq = NULL;

    return;
}


/*--------------------------------------------------------------------------*
 *                                  Accessors                               *
 *--------------------------------------------------------------------------*/
l_ok
lqueueAdd(L_QUEUE  *lq,
          void     *item)
{
    PROCNAME("lqueueAdd");

    if (!lq)
        return ERROR_INT("lq not defined", procName, 1);
    if (!item)
        return ERROR_INT("item not defined", procName, 1);

        /* If filled to the end and the ptrs can be shifted to the left,
         * shift them. */
    if ((lq->nhead + lq->nelem >= lq->nalloc) && (lq->nhead != 0)) {
        memmove(lq->array, lq->array + lq->nhead, sizeof(void *) * lq->nelem);
        lq->nhead = 0;
    }

        /* If necessary, expand the allocated array by a factor of 2 */
    if (lq->nelem > 0.75 * lq->nalloc)
        lqueueExtendArray(lq);

        /* Now add the item */
    lq->array[lq->nhead + lq->nelem] = (void *)item;
    lq->nelem++;

    return 0;
}


static l_int32
lqueueExtendArray(L_QUEUE  *lq)
{
    PROCNAME("lqueueExtendArray");

    if (!lq)
        return ERROR_INT("lq not defined", procName, 1);

    if ((lq->array = (void **)reallocNew((void **)&lq->array,
                                sizeof(void *) * lq->nalloc,
                                2 * sizeof(void *) * lq->nalloc)) == NULL)
        return ERROR_INT("new ptr array not returned", procName, 1);

    lq->nalloc = 2 * lq->nalloc;
    return 0;
}


void *
lqueueRemove(L_QUEUE  *lq)
{
void  *item;

    PROCNAME("lqueueRemove");

    if (!lq)
        return (void *)ERROR_PTR("lq not defined", procName, NULL);

    if (lq->nelem == 0)
        return NULL;
    item = lq->array[lq->nhead];
    lq->array[lq->nhead] = NULL;
    if (lq->nelem == 1)
        lq->nhead = 0;  /* reset head ptr */
    else
        (lq->nhead)++;  /* can't go off end of array because nelem > 1 */
    lq->nelem--;
    return item;
}


l_int32
lqueueGetCount(L_QUEUE  *lq)
{
    PROCNAME("lqueueGetCount");

    if (!lq)
        return ERROR_INT("lq not defined", procName, 0);

    return lq->nelem;
}


/*---------------------------------------------------------------------*
 *                            Debug output                             *
 *---------------------------------------------------------------------*/
l_ok
lqueuePrint(FILE     *fp,
            L_QUEUE  *lq)
{
l_int32  i;

    PROCNAME("lqueuePrint");

    if (!fp)
        return ERROR_INT("stream not defined", procName, 1);
    if (!lq)
        return ERROR_INT("lq not defined", procName, 1);

    fprintf(fp, "\n L_Queue: nalloc = %d, nhead = %d, nelem = %d, array = %p\n",
            lq->nalloc, lq->nhead, lq->nelem, lq->array);
    for (i = lq->nhead; i < lq->nhead + lq->nelem; i++)
    fprintf(fp,   "array[%d] = %p\n", i, lq->array[i]);

    return 0;
}