/*====================================================================* - Copyright (C) 2001 Leptonica. All rights reserved. - This software is distributed in the hope that it will be - useful, but with NO WARRANTY OF ANY KIND. - No author or distributor accepts responsibility to anyone for the - consequences of using this software, or for whether it serves any - particular purpose or works at all, unless he or she says so in - writing. Everyone is granted permission to copy, modify and - redistribute this source code, for commercial or non-commercial - purposes, with the following restrictions: (1) the origin of this - source code must not be misrepresented; (2) modified versions must - be plainly marked as such; and (3) this notice may not be removed - or altered from any source or modified source distribution. *====================================================================*/ /* * queue.c * * Create/Destroy L_Queue * L_QUEUE *lqueueCreate() * void *lqueueDestroy() * * Operations to add/remove to/from a L_Queue * l_int32 lqueueAdd() * l_int32 lqueueExtendArray() * void *lqueueRemove() * * Accessors * l_int32 lqueueGetCount() * * Debug output * l_int32 lqueuePrint() * * The lqueue is a fifo that implements a queue of void* pointers. * It can be used to hold a queue of any type of struct. * Internally, it maintains two counters: * nhead: location of head (in ptrs) from the beginning * of the buffer * nelem: number of ptr elements stored in the queue * As items are added to the queue, nelem increases. * As items are removed, nhead increases and nelem decreases. * Any time the tail reaches the end of the allocated buffer, * all the pointers are shifted to the left, so that the head * is at the beginning of the array. * If the buffer becomes more than 3/4 full, it doubles in size. * * [A circular queue would allow us to skip the shifting and * to resize only when the buffer is full. For most applications, * the extra work we do for a linear queue is not significant.] */ #include <stdio.h> #include <string.h> #include <stdlib.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 */ /*--------------------------------------------------------------------------* * L_Queue create/destroy * *--------------------------------------------------------------------------*/ /*! * lqueueCreate() * * Input: 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; if ((lq = (L_QUEUE *)CALLOC(1, sizeof(L_QUEUE))) == NULL) return (L_QUEUE *)ERROR_PTR("lq not made", procName, NULL); if ((lq->array = (void **)CALLOC(nalloc, sizeof(void *))) == NULL) return (L_QUEUE *)ERROR_PTR("ptr array not made", procName, NULL); lq->nalloc = nalloc; lq->nhead = lq->nelem = 0; return lq; } /*! * lqueueDestroy() * * Input: &lqueue (<to be nulled>) * 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", procName); return; } if ((lq = *plq) == NULL) return; if (freeflag) { while(lq->nelem > 0) { item = lqueueRemove(lq); FREE(item); } } else if (lq->nelem > 0) L_WARNING_INT("memory leak of %d items in lqueue!", procName, lq->nelem); if (lq->array) FREE(lq->array); if (lq->stack) lstackDestroy(&lq->stack, freeflag); FREE(lq); *plq = NULL; return; } /*--------------------------------------------------------------------------* * Accessors * *--------------------------------------------------------------------------*/ /*! * lqueueAdd() * * Input: lqueue * 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_int32 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; } /*! * lqueueExtendArray() * * Input: lqueue * Return: 0 if OK, 1 on error */ 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; } /*! * lqueueRemove() * * Input: 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; } /*! * lqueueGetCount() * * Input: 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 * *---------------------------------------------------------------------*/ /*! * lqueuePrint() * * Input: stream * lqueue * Return: 0 if OK; 1 on error */ l_int32 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; }