/src/leptonica/src/queue.c

Source (jump to first uncovered line)
/*====================================================================*
 -  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.
 *====================================================================*/

/*!
 * \file  queue.c
 * <pre>
 *
 *      Create/Destroy L_Queue
 *          L_QUEUE        *lqueueCreate()
 *          void           *lqueueDestroy()
 *
 *      Operations to add/remove to/from a L_Queue
 *          l_int32         lqueueAdd()
 *          static 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.]
 * </pre>
 */

#ifdef HAVE_CONFIG_H
#include <config_auto.h>
#endif  /* HAVE_CONFIG_H */

#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                           *
 *--------------------------------------------------------------------------*/
/*!
 * \brief   lqueueCreate()
 *
 * \param[in]    nalloc     size of ptr array to be alloc'd; 0 for default
 * \return  lqueue, or NULL on error
 *
 * <pre>
 * Notes:
 *      (1) Allocates a ptr array of given size, and initializes counters.
 * </pre>
 */
L_QUEUE *
lqueueCreate(l_int32  nalloc)
{
L_QUEUE  *lq;

    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", __func__, 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
 *
 * <pre>
 * 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.
 * </pre>
 */
void
lqueueDestroy(L_QUEUE  **plq,
              l_int32    freeflag)
{
void     *item;
L_QUEUE  *lq;

    if (plq == NULL) {
        L_WARNING("ptr address is NULL\n", __func__);
        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", __func__, 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
 *
 * <pre>
 * 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.
 * </pre>
 */
l_ok
lqueueAdd(L_QUEUE  *lq,
          void     *item)
{
    if (!lq)
        return ERROR_INT("lq not defined", __func__, 1);
    if (!item)
        return ERROR_INT("item not defined", __func__, 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", __func__, 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)
{
    if (!lq)
        return ERROR_INT("lq not defined", __func__, 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", __func__, 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
 *
 * <pre>
 * 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.
 * </pre>
 */
void *
lqueueRemove(L_QUEUE  *lq)
{
void  *item;

    if (!lq)
        return (void *)ERROR_PTR("lq not defined", __func__, 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)
{
    if (!lq)
        return ERROR_INT("lq not defined", __func__, 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;

    if (!fp)
        return ERROR_INT("stream not defined", __func__, 1);
    if (!lq)
        return ERROR_INT("lq not defined", __func__, 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;
}

Coverage Report

Created: 2024-07-27 06:27

Line	Count	Source (jump to first uncovered line)
1		/====================================================================
2		- Copyright (C) 2001 Leptonica. All rights reserved.
3		-
4		- Redistribution and use in source and binary forms, with or without
5		- modification, are permitted provided that the following conditions
6		- are met:
7		- 1. Redistributions of source code must retain the above copyright
8		- notice, this list of conditions and the following disclaimer.
9		- 2. Redistributions in binary form must reproduce the above
10		- copyright notice, this list of conditions and the following
11		- disclaimer in the documentation and/or other materials
12		- provided with the distribution.
13		-
14		- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15		- ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16		- LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17		- A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ANY
18		- CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19		- EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20		- PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21		- PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22		- OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
23		- NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24		- SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25		====================================================================/
26
27		/*!
28		* \file queue.c
29		* <pre>
30		*
31		* Create/Destroy L_Queue
32		* L_QUEUE *lqueueCreate()
33		* void *lqueueDestroy()
34		*
35		* Operations to add/remove to/from a L_Queue
36		* l_int32 lqueueAdd()
37		* static l_int32 lqueueExtendArray()
38		* void *lqueueRemove()
39		*
40		* Accessors
41		* l_int32 lqueueGetCount()
42		*
43		* Debug output
44		* l_int32 lqueuePrint()
45		*
46		* The lqueue is a fifo that implements a queue of void* pointers.
47		* It can be used to hold a queue of any type of struct.
48		* Internally, it maintains two counters:
49		* nhead: location of head (in ptrs) from the beginning
50		* of the buffer
51		* nelem: number of ptr elements stored in the queue
52		* As items are added to the queue, nelem increases.
53		* As items are removed, nhead increases and nelem decreases.
54		* Any time the tail reaches the end of the allocated buffer,
55		* all the pointers are shifted to the left, so that the head
56		* is at the beginning of the array.
57		* If the buffer becomes more than 3/4 full, it doubles in size.
58		*
59		* [A circular queue would allow us to skip the shifting and
60		* to resize only when the buffer is full. For most applications,
61		* the extra work we do for a linear queue is not significant.]
62		* </pre>
63		*/
64
65		#ifdef HAVE_CONFIG_H
66		#include <config_auto.h>
67		#endif /* HAVE_CONFIG_H */
68
69		#include <string.h>
70		#include "allheaders.h"
71
72		static const l_int32 MIN_BUFFER_SIZE = 20; /* n'importe quoi */
73		static const l_int32 INITIAL_BUFFER_ARRAYSIZE = 1024; /* n'importe quoi */
74
75		/* Static function */
76		static l_int32 lqueueExtendArray(L_QUEUE *lq);
77
78		/--------------------------------------------------------------------------
79		* L_Queue create/destroy *
80		--------------------------------------------------------------------------/
81		/*!
82		* \brief lqueueCreate()
83		*
84		* \param[in] nalloc size of ptr array to be alloc'd; 0 for default
85		* \return lqueue, or NULL on error
86		*
87		* <pre>
88		* Notes:
89		* (1) Allocates a ptr array of given size, and initializes counters.
90		* </pre>
91		*/
92		L_QUEUE *
93		lqueueCreate(l_int32 nalloc)
94	0	{
95	0	L_QUEUE *lq;
96
97	0	if (nalloc < MIN_BUFFER_SIZE)
98	0	nalloc = INITIAL_BUFFER_ARRAYSIZE;
99
100	0	lq = (L_QUEUE *)LEPT_CALLOC(1, sizeof(L_QUEUE));
101	0	if ((lq->array = (void *)LEPT_CALLOC(nalloc, sizeof(void ))) == NULL) {
102	0	lqueueDestroy(&lq, 0);
103	0	return (L_QUEUE *)ERROR_PTR("ptr array not made", __func__, NULL);
104	0	}
105	0	lq->nalloc = nalloc;
106	0	lq->nhead = lq->nelem = 0;
107	0	return lq;
108	0	}
109
110
111		/*!
112		* \brief lqueueDestroy()
113		*
114		* \param[in,out] plq will be set to null before returning
115		* \param[in] freeflag TRUE to free each remaining struct in the array
116		* \return void
117		*
118		* <pre>
119		* Notes:
120		* (1) If freeflag is TRUE, frees each struct in the array.
121		* (2) If freeflag is FALSE but there are elements on the array,
122		* gives a warning and destroys the array. This will
123		* cause a memory leak of all the items that were on the queue.
124		* So if the items require their own destroy function, they
125		* must be destroyed before the queue. The same applies to the
126		* auxiliary stack, if it is used.
127		* (3) To destroy the L_Queue, we destroy the ptr array, then
128		* the lqueue, and then null the contents of the input ptr.
129		* </pre>
130		*/
131		void
132		lqueueDestroy(L_QUEUE **plq,
133		l_int32 freeflag)
134	0	{
135	0	void *item;
136	0	L_QUEUE *lq;
137
138	0	if (plq == NULL) {
139	0	L_WARNING("ptr address is NULL\n", __func__);
140	0	return;
141	0	}
142	0	if ((lq = *plq) == NULL)
143	0	return;
144
145	0	if (freeflag) {
146	0	while(lq->nelem > 0) {
147	0	item = lqueueRemove(lq);
148	0	LEPT_FREE(item);
149	0	}
150	0	} else if (lq->nelem > 0) {
151	0	L_WARNING("memory leak of %d items in lqueue!\n", __func__, lq->nelem);
152	0	}
153
154	0	if (lq->array)
155	0	LEPT_FREE(lq->array);
156	0	if (lq->stack)
157	0	lstackDestroy(&lq->stack, freeflag);
158	0	LEPT_FREE(lq);
159	0	*plq = NULL;
160	0	}
161
162
163		/--------------------------------------------------------------------------
164		* Accessors *
165		--------------------------------------------------------------------------/
166		/*!
167		* \brief lqueueAdd()
168		*
169		* \param[in] lq lqueue
170		* \param[in] item to be added to the tail of the queue
171		* \return 0 if OK, 1 on error
172		*
173		* <pre>
174		* Notes:
175		* (1) The algorithm is as follows. If the queue is populated
176		* to the end of the allocated array, shift all ptrs toward
177		* the beginning of the array, so that the head of the queue
178		* is at the beginning of the array. Then, if the array is
179		* more than 0.75 full, realloc with double the array size.
180		* Finally, add the item to the tail of the queue.
181		* </pre>
182		*/
183		l_ok
184		lqueueAdd(L_QUEUE *lq,
185		void *item)
186	0	{
187	0	if (!lq)
188	0	return ERROR_INT("lq not defined", __func__, 1);
189	0	if (!item)
190	0	return ERROR_INT("item not defined", __func__, 1);
191
192		/* If filled to the end and the ptrs can be shifted to the left,
193		* shift them. */
194	0	if ((lq->nhead + lq->nelem >= lq->nalloc) && (lq->nhead != 0)) {
195	0	memmove(lq->array, lq->array + lq->nhead, sizeof(void ) lq->nelem);
196	0	lq->nhead = 0;
197	0	}
198
199		/* If necessary, expand the allocated array by a factor of 2 */
200	0	if (lq->nelem > 0.75 * lq->nalloc) {
201	0	if (lqueueExtendArray(lq))
202	0	return ERROR_INT("extension failed", __func__, 1);
203	0	}
204
205		/* Now add the item */
206	0	lq->array[lq->nhead + lq->nelem] = (void *)item;
207	0	lq->nelem++;
208
209	0	return 0;
210	0	}
211
212
213		/*!
214		* \brief lqueueExtendArray()
215		*
216		* \param[in] lq lqueue
217		* \return 0 if OK, 1 on error
218		*/
219		static l_int32
220		lqueueExtendArray(L_QUEUE *lq)
221	0	{
222	0	if (!lq)
223	0	return ERROR_INT("lq not defined", __func__, 1);
224
225	0	if ((lq->array = (void )reallocNew((void )&lq->array,
226	0	sizeof(void ) lq->nalloc,
227	0	2 * sizeof(void ) lq->nalloc)) == NULL)
228	0	return ERROR_INT("new ptr array not returned", __func__, 1);
229
230	0	lq->nalloc = 2 * lq->nalloc;
231	0	return 0;
232	0	}
233
234
235		/*!
236		* \brief lqueueRemove()
237		*
238		* \param[in] lq lqueue
239		* \return ptr to item popped from the head of the queue,
240		* or NULL if the queue is empty or on error
241		*
242		* <pre>
243		* Notes:
244		* (1) If this is the last item on the queue, so that the queue
245		* becomes empty, nhead is reset to the beginning of the array.
246		* </pre>
247		*/
248		void *
249		lqueueRemove(L_QUEUE *lq)
250	0	{
251	0	void *item;
252
253	0	if (!lq)
254	0	return (void *)ERROR_PTR("lq not defined", __func__, NULL);
255
256	0	if (lq->nelem == 0)
257	0	return NULL;
258	0	item = lq->array[lq->nhead];
259	0	lq->array[lq->nhead] = NULL;
260	0	if (lq->nelem == 1)
261	0	lq->nhead = 0; /* reset head ptr */
262	0	else
263	0	(lq->nhead)++; /* can't go off end of array because nelem > 1 */
264	0	lq->nelem--;
265	0	return item;
266	0	}
267
268
269		/*!
270		* \brief lqueueGetCount()
271		*
272		* \param[in] lq lqueue
273		* \return count, or 0 on error
274		*/
275		l_int32
276		lqueueGetCount(L_QUEUE *lq)
277	0	{
278	0	if (!lq)
279	0	return ERROR_INT("lq not defined", __func__, 0);
280
281	0	return lq->nelem;
282	0	}
283
284
285		/---------------------------------------------------------------------
286		* Debug output *
287		---------------------------------------------------------------------/
288		/*!
289		* \brief lqueuePrint()
290		*
291		* \param[in] fp file stream
292		* \param[in] lq lqueue
293		* \return 0 if OK; 1 on error
294		*/
295		l_ok
296		lqueuePrint(FILE *fp,
297		L_QUEUE *lq)
298	0	{
299	0	l_int32 i;
300
301	0	if (!fp)
302	0	return ERROR_INT("stream not defined", __func__, 1);
303	0	if (!lq)
304	0	return ERROR_INT("lq not defined", __func__, 1);
305
306	0	fprintf(fp, "\n L_Queue: nalloc = %d, nhead = %d, nelem = %d, array = %p\n",
307	0	lq->nalloc, lq->nhead, lq->nelem, lq->array);
308	0	for (i = lq->nhead; i < lq->nhead + lq->nelem; i++)
309	0	fprintf(fp, "array[%d] = %p\n", i, lq->array[i]);
310
311	0	return 0;
312	0	}