#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 *
*--------------------------------------------------------------------------*/
/*!
* \brief lqueueCreate()
*
* \param[in] nalloc size of ptr array to be alloc'd; 0 for default
* \return lqueue, or NULL on error
*
*
* Notes:
* (1) Allocates a ptr array of given size, and initializes counters.
*
*/
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;
}
/*!
* \brief lqueueDestroy()
*
* \param[in,out] plq will be set to null before returning
* \param[in] freeflag TRUE to free each remaining struct in the array
* \return void
*
*
* Notes:
* (1) If freeflag is TRUE, frees each struct in the array.
* (2) If freeflag is FALSE but there are elements on the array,
* gives a warning and destroys the array. This will
* cause a memory leak of all the items that were on the queue.
* So if the items require their own destroy function, they
* must be destroyed before the queue. The same applies to the
* auxiliary stack, if it is used.
* (3) To destroy the L_Queue, we destroy the ptr array, then
* the lqueue, and then null the contents of the input ptr.
*
*/
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;
}
/*--------------------------------------------------------------------------*
* Accessors *
*--------------------------------------------------------------------------*/
/*!
* \brief lqueueAdd()
*
* \param[in] lq lqueue
* \param[in] item to be added to the tail of the queue
* \return 0 if OK, 1 on error
*
*
* Notes:
* (1) The algorithm is as follows. If the queue is populated
* to the end of the allocated array, shift all ptrs toward
* the beginning of the array, so that the head of the queue
* is at the beginning of the array. Then, if the array is
* more than 0.75 full, realloc with double the array size.
* Finally, add the item to the tail of the queue.
*
*/
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) {
if (lqueueExtendArray(lq))
return ERROR_INT("extension failed", procName, 1);
}
/* Now add the item */
lq->array[lq->nhead + lq->nelem] = (void *)item;
lq->nelem++;
return 0;
}
/*!
* \brief lqueueExtendArray()
*
* \param[in] lq lqueue
* \return 0 if OK, 1 on error
*/
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;
}
/*!
* \brief lqueueRemove()
*
* \param[in] lq lqueue
* \return ptr to item popped from the head of the queue,
* or NULL if the queue is empty or on error
*
*
* Notes:
* (1) If this is the last item on the queue, so that the queue
* becomes empty, nhead is reset to the beginning of the array.
*
*/
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;
}
/*!
* \brief lqueueGetCount()
*
* \param[in] lq lqueue
* \return count, or 0 on error
*/
l_int32
lqueueGetCount(L_QUEUE *lq)
{
PROCNAME("lqueueGetCount");
if (!lq)
return ERROR_INT("lq not defined", procName, 0);
return lq->nelem;
}
/*---------------------------------------------------------------------*
* Debug output *
*---------------------------------------------------------------------*/
/*!
* \brief lqueuePrint()
*
* \param[in] fp file stream
* \param[in] lq lqueue
* \return 0 if OK; 1 on error
*/
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;
}