/src/leptonica/src/stack.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 stack.c
 * <pre>
 *
 *      Generic stack
 *
 *      The lstack is an array of void * ptrs, onto which
 *      objects can be stored.  At any time, the number of
 *      stored objects is lstack->n.  The object at the bottom
 *      of the lstack is at array[0]; the object at the top of
 *      the lstack is at array[n-1].  New objects are added
 *      to the top of the lstack; i.e., the first available
 *      location, which is at array[n].  The lstack is expanded
 *      by doubling, when needed.  Objects are removed
 *      from the top of the lstack.  When an attempt is made
 *      to remove an object from an empty lstack, the result is null.
 *
 *      Create/Destroy
 *           L_STACK        *lstackCreate()
 *           void            lstackDestroy()
 *
 *      Accessors
 *           l_int32         lstackAdd()
 *           void           *lstackRemove()
 *           static l_int32  lstackExtendArray()
 *           l_int32         lstackGetCount()
 *
 *      Text description
 *           l_int32         lstackPrint()
 * </pre>
 */

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

#include "allheaders.h"

    /* Bounds on initial array size */
static const l_uint32  MaxPtrArraySize = 100000;
static const l_int32 InitialPtrArraySize = 20;      /*!< n'importe quoi */

    /* Static function */
static l_int32 lstackExtendArray(L_STACK *lstack);

/*---------------------------------------------------------------------*
 *                          Create/Destroy                             *
 *---------------------------------------------------------------------*/
/*!
 * \brief   lstackCreate()
 *
 * \param[in]    n   initial ptr array size; use 0 for default
 * \return  lstack, or NULL on error
 */
L_STACK *
lstackCreate(l_int32  n)
{
L_STACK  *lstack;

    if (n <= 0 || n > (l_int32)MaxPtrArraySize)
        n = InitialPtrArraySize;

    lstack = (L_STACK *)LEPT_CALLOC(1, sizeof(L_STACK));
    lstack->array = (void **)LEPT_CALLOC(n, sizeof(void *));
    if (!lstack->array) {
        lstackDestroy(&lstack, FALSE);
        return (L_STACK *)ERROR_PTR("lstack array not made", __func__, NULL);
    }

    lstack->nalloc = n;
    lstack->n = 0;
    return lstack;
}


/*!
 * \brief   lstackDestroy()
 *
 * \param[in,out]   plstack    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 lstack.
 *          So if the items require their own destroy function, they
 *          must be destroyed before the lstack.
 *      (3) To destroy the lstack, we destroy the ptr array, then
 *          the lstack, and then null the contents of the input ptr.
 * </pre>
 */
void
lstackDestroy(L_STACK  **plstack,
              l_int32    freeflag)
{
void     *item;
L_STACK  *lstack;

    if (plstack == NULL) {
        L_WARNING("ptr address is NULL\n", __func__);
        return;
    }
    if ((lstack = *plstack) == NULL)
        return;

    if (freeflag) {
        while(lstack->n > 0) {
            item = lstackRemove(lstack);
            LEPT_FREE(item);
        }
    } else if (lstack->n > 0) {
        L_WARNING("memory leak of %d items in lstack\n", __func__, lstack->n);
    }

    if (lstack->auxstack)
        lstackDestroy(&lstack->auxstack, freeflag);

    if (lstack->array)
        LEPT_FREE(lstack->array);
    LEPT_FREE(lstack);
    *plstack = NULL;
}



/*---------------------------------------------------------------------*
 *                               Accessors                             *
 *---------------------------------------------------------------------*/
/*!
 * \brief   lstackAdd()
 *
 * \param[in]    lstack
 * \param[in]    item      to be added to the lstack
 * \return  0 if OK; 1 on error.
 */
l_ok
lstackAdd(L_STACK  *lstack,
          void     *item)
{
    if (!lstack)
        return ERROR_INT("lstack not defined", __func__, 1);
    if (!item)
        return ERROR_INT("item not defined", __func__, 1);

        /* Do we need to extend the array? */
    if (lstack->n >= lstack->nalloc) {
        if (lstackExtendArray(lstack))
            return ERROR_INT("extension failed", __func__, 1);
    }

        /* Store the new pointer */
    lstack->array[lstack->n] = (void *)item;
    lstack->n++;

    return 0;
}


/*!
 * \brief   lstackRemove()
 *
 * \param[in]    lstack
 * \return  ptr to item popped from the top of the lstack,
 *              or NULL if the lstack is empty or on error
 */
void *
lstackRemove(L_STACK  *lstack)
{
void  *item;

    if (!lstack)
        return ERROR_PTR("lstack not defined", __func__, NULL);

    if (lstack->n == 0)
        return NULL;

    lstack->n--;
    item = lstack->array[lstack->n];

    return item;
}


/*!
 * \brief   lstackExtendArray()
 *
 * \param[in]    lstack
 * \return  0 if OK; 1 on error
 */
static l_int32
lstackExtendArray(L_STACK  *lstack)
{
    if (!lstack)
        return ERROR_INT("lstack not defined", __func__, 1);

    if ((lstack->array = (void **)reallocNew((void **)&lstack->array,
                              sizeof(void *) * lstack->nalloc,
                              2 * sizeof(void *) * lstack->nalloc)) == NULL)
        return ERROR_INT("new lstack array not defined", __func__, 1);

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


/*!
 * \brief   lstackGetCount()
 *
 * \param[in]    lstack
 * \return  count, or 0 on error
 */
l_int32
lstackGetCount(L_STACK  *lstack)
{
    if (!lstack)
        return ERROR_INT("lstack not defined", __func__, 1);

    return lstack->n;
}



/*---------------------------------------------------------------------*
 *                            Debug output                             *
 *---------------------------------------------------------------------*/
/*!
 * \brief   lstackPrint()
 *
 * \param[in]    fp       file stream
 * \param[in]    lstack
 * \return  0 if OK; 1 on error
 */
l_ok
lstackPrint(FILE     *fp,
            L_STACK  *lstack)
{
l_int32  i;

    if (!fp)
        return ERROR_INT("stream not defined", __func__, 1);
    if (!lstack)
        return ERROR_INT("lstack not defined", __func__, 1);

    fprintf(fp, "\n Stack: nalloc = %d, n = %d, array = %p\n",
            lstack->nalloc, lstack->n, lstack->array);
    for (i = 0; i < lstack->n; i++)
        fprintf(fp,   "array[%d] = %p\n", i, lstack->array[i]);

    return 0;
}

Coverage Report

Created: 2025-06-13 06:48

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 stack.c
29		* <pre>
30		*
31		* Generic stack
32		*
33		* The lstack is an array of void * ptrs, onto which
34		* objects can be stored. At any time, the number of
35		* stored objects is lstack->n. The object at the bottom
36		* of the lstack is at array[0]; the object at the top of
37		* the lstack is at array[n-1]. New objects are added
38		* to the top of the lstack; i.e., the first available
39		* location, which is at array[n]. The lstack is expanded
40		* by doubling, when needed. Objects are removed
41		* from the top of the lstack. When an attempt is made
42		* to remove an object from an empty lstack, the result is null.
43		*
44		* Create/Destroy
45		* L_STACK *lstackCreate()
46		* void lstackDestroy()
47		*
48		* Accessors
49		* l_int32 lstackAdd()
50		* void *lstackRemove()
51		* static l_int32 lstackExtendArray()
52		* l_int32 lstackGetCount()
53		*
54		* Text description
55		* l_int32 lstackPrint()
56		* </pre>
57		*/
58
59		#ifdef HAVE_CONFIG_H
60		#include <config_auto.h>
61		#endif /* HAVE_CONFIG_H */
62
63		#include "allheaders.h"
64
65		/* Bounds on initial array size */
66		static const l_uint32 MaxPtrArraySize = 100000;
67		static const l_int32 InitialPtrArraySize = 20; /!< n'importe quoi /
68
69		/* Static function */
70		static l_int32 lstackExtendArray(L_STACK *lstack);
71
72		/---------------------------------------------------------------------
73		* Create/Destroy *
74		---------------------------------------------------------------------/
75		/*!
76		* \brief lstackCreate()
77		*
78		* \param[in] n initial ptr array size; use 0 for default
79		* \return lstack, or NULL on error
80		*/
81		L_STACK *
82		lstackCreate(l_int32 n)
83	0	{
84	0	L_STACK *lstack;
85
86	0	if (n <= 0 \|\| n > (l_int32)MaxPtrArraySize)
87	0	n = InitialPtrArraySize;
88
89	0	lstack = (L_STACK *)LEPT_CALLOC(1, sizeof(L_STACK));
90	0	lstack->array = (void *)LEPT_CALLOC(n, sizeof(void ));
91	0	if (!lstack->array) {
92	0	lstackDestroy(&lstack, FALSE);
93	0	return (L_STACK *)ERROR_PTR("lstack array not made", __func__, NULL);
94	0	}
95
96	0	lstack->nalloc = n;
97	0	lstack->n = 0;
98	0	return lstack;
99	0	}
100
101
102		/*!
103		* \brief lstackDestroy()
104		*
105		* \param[in,out] plstack will be set to null before returning
106		* \param[in] freeflag TRUE to free each remaining struct in the array
107		* \return void
108		*
109		* <pre>
110		* Notes:
111		* (1) If %freeflag is TRUE, frees each struct in the array.
112		* (2) If %freeflag is FALSE but there are elements on the array,
113		* gives a warning and destroys the array. This will
114		* cause a memory leak of all the items that were on the lstack.
115		* So if the items require their own destroy function, they
116		* must be destroyed before the lstack.
117		* (3) To destroy the lstack, we destroy the ptr array, then
118		* the lstack, and then null the contents of the input ptr.
119		* </pre>
120		*/
121		void
122		lstackDestroy(L_STACK **plstack,
123		l_int32 freeflag)
124	0	{
125	0	void *item;
126	0	L_STACK *lstack;
127
128	0	if (plstack == NULL) {
129	0	L_WARNING("ptr address is NULL\n", __func__);
130	0	return;
131	0	}
132	0	if ((lstack = *plstack) == NULL)
133	0	return;
134
135	0	if (freeflag) {
136	0	while(lstack->n > 0) {
137	0	item = lstackRemove(lstack);
138	0	LEPT_FREE(item);
139	0	}
140	0	} else if (lstack->n > 0) {
141	0	L_WARNING("memory leak of %d items in lstack\n", __func__, lstack->n);
142	0	}
143
144	0	if (lstack->auxstack)
145	0	lstackDestroy(&lstack->auxstack, freeflag);
146
147	0	if (lstack->array)
148	0	LEPT_FREE(lstack->array);
149	0	LEPT_FREE(lstack);
150	0	*plstack = NULL;
151	0	}
152
153
154
155		/---------------------------------------------------------------------
156		* Accessors *
157		---------------------------------------------------------------------/
158		/*!
159		* \brief lstackAdd()
160		*
161		* \param[in] lstack
162		* \param[in] item to be added to the lstack
163		* \return 0 if OK; 1 on error.
164		*/
165		l_ok
166		lstackAdd(L_STACK *lstack,
167		void *item)
168	0	{
169	0	if (!lstack)
170	0	return ERROR_INT("lstack not defined", __func__, 1);
171	0	if (!item)
172	0	return ERROR_INT("item not defined", __func__, 1);
173
174		/* Do we need to extend the array? */
175	0	if (lstack->n >= lstack->nalloc) {
176	0	if (lstackExtendArray(lstack))
177	0	return ERROR_INT("extension failed", __func__, 1);
178	0	}
179
180		/* Store the new pointer */
181	0	lstack->array[lstack->n] = (void *)item;
182	0	lstack->n++;
183
184	0	return 0;
185	0	}
186
187
188		/*!
189		* \brief lstackRemove()
190		*
191		* \param[in] lstack
192		* \return ptr to item popped from the top of the lstack,
193		* or NULL if the lstack is empty or on error
194		*/
195		void *
196		lstackRemove(L_STACK *lstack)
197	0	{
198	0	void *item;
199
200	0	if (!lstack)
201	0	return ERROR_PTR("lstack not defined", __func__, NULL);
202
203	0	if (lstack->n == 0)
204	0	return NULL;
205
206	0	lstack->n--;
207	0	item = lstack->array[lstack->n];
208
209	0	return item;
210	0	}
211
212
213		/*!
214		* \brief lstackExtendArray()
215		*
216		* \param[in] lstack
217		* \return 0 if OK; 1 on error
218		*/
219		static l_int32
220		lstackExtendArray(L_STACK *lstack)
221	0	{
222	0	if (!lstack)
223	0	return ERROR_INT("lstack not defined", __func__, 1);
224
225	0	if ((lstack->array = (void )reallocNew((void )&lstack->array,
226	0	sizeof(void ) lstack->nalloc,
227	0	2 * sizeof(void ) lstack->nalloc)) == NULL)
228	0	return ERROR_INT("new lstack array not defined", __func__, 1);
229
230	0	lstack->nalloc = 2 * lstack->nalloc;
231	0	return 0;
232	0	}
233
234
235		/*!
236		* \brief lstackGetCount()
237		*
238		* \param[in] lstack
239		* \return count, or 0 on error
240		*/
241		l_int32
242		lstackGetCount(L_STACK *lstack)
243	0	{
244	0	if (!lstack)
245	0	return ERROR_INT("lstack not defined", __func__, 1);
246
247	0	return lstack->n;
248	0	}
249
250
251
252		/---------------------------------------------------------------------
253		* Debug output *
254		---------------------------------------------------------------------/
255		/*!
256		* \brief lstackPrint()
257		*
258		* \param[in] fp file stream
259		* \param[in] lstack
260		* \return 0 if OK; 1 on error
261		*/
262		l_ok
263		lstackPrint(FILE *fp,
264		L_STACK *lstack)
265	0	{
266	0	l_int32 i;
267
268	0	if (!fp)
269	0	return ERROR_INT("stream not defined", __func__, 1);
270	0	if (!lstack)
271	0	return ERROR_INT("lstack not defined", __func__, 1);
272
273	0	fprintf(fp, "\n Stack: nalloc = %d, n = %d, array = %p\n",
274	0	lstack->nalloc, lstack->n, lstack->array);
275	0	for (i = 0; i < lstack->n; i++)
276	0	fprintf(fp, "array[%d] = %p\n", i, lstack->array[i]);
277
278	0	return 0;
279	0	}