1 /*====================================================================*
2 - Copyright (C) 2001 Leptonica. All rights reserved.
3 - This software is distributed in the hope that it will be
4 - useful, but with NO WARRANTY OF ANY KIND.
5 - No author or distributor accepts responsibility to anyone for the
6 - consequences of using this software, or for whether it serves any
7 - particular purpose or works at all, unless he or she says so in
8 - writing. Everyone is granted permission to copy, modify and
9 - redistribute this source code, for commercial or non-commercial
10 - purposes, with the following restrictions: (1) the origin of this
11 - source code must not be misrepresented; (2) modified versions must
12 - be plainly marked as such; and (3) this notice may not be removed
13 - or altered from any source or modified source distribution.
14 *====================================================================*/
15
16
17 /*
18 * stack.c
19 *
20 * Generic stack
21 *
22 * The lstack is an array of void * ptrs, onto which
23 * objects can be stored. At any time, the number of
24 * stored objects is lstack->n. The object at the bottom
25 * of the lstack is at array[0]; the object at the top of
26 * the lstack is at array[n-1]. New objects are added
27 * to the top of the lstack; i.e., the first available
28 * location, which is at array[n]. The lstack is expanded
29 * by doubling, when needed. Objects are removed
30 * from the top of the lstack. When an attempt is made
31 * to remove an object from an empty lstack, the result is null.
32 *
33 * Create/Destroy
34 * L_STACK *lstackCreate()
35 * void lstackDestroy()
36 *
37 * Accessors
38 * l_int32 lstackAdd()
39 * void *lstackRemove()
40 * l_int32 lstackExtendArray()
41 * l_int32 lstackGetCount()
42 *
43 * Text description
44 * l_int32 lstackPrint()
45 */
46
47 #include <stdio.h>
48 #include <stdlib.h>
49 #include "allheaders.h"
50
51 static const l_int32 INITIAL_PTR_ARRAYSIZE = 20;
52
53
54 /*---------------------------------------------------------------------*
55 * Create/Destroy *
56 *---------------------------------------------------------------------*/
57 /*!
58 * lstackCreate()
59 *
60 * Input: nalloc (initial ptr array size; use 0 for default)
61 * Return: lstack, or null on error
62 */
63 L_STACK *
lstackCreate(l_int32 nalloc)64 lstackCreate(l_int32 nalloc)
65 {
66 L_STACK *lstack;
67
68 PROCNAME("lstackCreate");
69
70 if (nalloc <= 0)
71 nalloc = INITIAL_PTR_ARRAYSIZE;
72
73 if ((lstack = (L_STACK *)CALLOC(1, sizeof(L_STACK))) == NULL)
74 return (L_STACK *)ERROR_PTR("lstack not made", procName, NULL);
75
76 if ((lstack->array = (void **)CALLOC(nalloc, sizeof(void *))) == NULL)
77 return (L_STACK *)ERROR_PTR("lstack array not made", procName, NULL);
78
79 lstack->nalloc = nalloc;
80 lstack->n = 0;
81
82 return lstack;
83 }
84
85
86 /*!
87 * lstackDestroy()
88 *
89 * Input: &lstack (<to be nulled>)
90 * freeflag (TRUE to free each remaining struct in the array)
91 * Return: void
92 *
93 * Notes:
94 * (1) If freeflag is TRUE, frees each struct in the array.
95 * (2) If freeflag is FALSE but there are elements on the array,
96 * gives a warning and destroys the array. This will
97 * cause a memory leak of all the items that were on the lstack.
98 * So if the items require their own destroy function, they
99 * must be destroyed before the lstack.
100 * (3) To destroy the lstack, we destroy the ptr array, then
101 * the lstack, and then null the contents of the input ptr.
102 */
103 void
lstackDestroy(L_STACK ** plstack,l_int32 freeflag)104 lstackDestroy(L_STACK **plstack,
105 l_int32 freeflag)
106 {
107 void *item;
108 L_STACK *lstack;
109
110 PROCNAME("lstackDestroy");
111
112 if (plstack == NULL) {
113 L_WARNING("ptr address is NULL", procName);
114 return;
115 }
116 if ((lstack = *plstack) == NULL)
117 return;
118
119 if (freeflag) {
120 while(lstack->n > 0) {
121 item = lstackRemove(lstack);
122 FREE(item);
123 }
124 }
125 else if (lstack->n > 0)
126 L_WARNING_INT("memory leak of %d items in lstack", procName, lstack->n);
127
128 if (lstack->auxstack)
129 lstackDestroy(&lstack->auxstack, freeflag);
130
131 if (lstack->array)
132 FREE(lstack->array);
133 FREE(lstack);
134 *plstack = NULL;
135 }
136
137
138
139 /*---------------------------------------------------------------------*
140 * Accessors *
141 *---------------------------------------------------------------------*/
142 /*!
143 * lstackAdd()
144 *
145 * Input: lstack
146 * item to be added to the lstack
147 * Return: 0 if OK; 1 on error.
148 */
149 l_int32
lstackAdd(L_STACK * lstack,void * item)150 lstackAdd(L_STACK *lstack,
151 void *item)
152 {
153 PROCNAME("lstackAdd");
154
155 if (!lstack)
156 return ERROR_INT("lstack not defined", procName, 1);
157 if (!item)
158 return ERROR_INT("item not defined", procName, 1);
159
160 /* Do we need to extend the array? */
161 if (lstack->n >= lstack->nalloc)
162 lstackExtendArray(lstack);
163
164 /* Store the new pointer */
165 lstack->array[lstack->n] = (void *)item;
166 lstack->n++;
167
168 return 0;
169 }
170
171
172 /*!
173 * lstackRemove()
174 *
175 * Input: lstack
176 * Return: ptr to item popped from the top of the lstack,
177 * or null if the lstack is empty or on error
178 */
179 void *
lstackRemove(L_STACK * lstack)180 lstackRemove(L_STACK *lstack)
181 {
182 void *item;
183
184 PROCNAME("lstackRemove");
185
186 if (!lstack)
187 return ERROR_PTR("lstack not defined", procName, NULL);
188
189 if (lstack->n == 0)
190 return NULL;
191
192 lstack->n--;
193 item = lstack->array[lstack->n];
194
195 return item;
196 }
197
198
199 /*!
200 * lstackExtendArray()
201 *
202 * Input: lstack
203 * Return: 0 if OK; 1 on error
204 */
205 l_int32
lstackExtendArray(L_STACK * lstack)206 lstackExtendArray(L_STACK *lstack)
207 {
208 PROCNAME("lstackExtendArray");
209
210 if (!lstack)
211 return ERROR_INT("lstack not defined", procName, 1);
212
213 if ((lstack->array = (void **)reallocNew((void **)&lstack->array,
214 sizeof(void *) * lstack->nalloc,
215 2 * sizeof(void *) * lstack->nalloc)) == NULL)
216 return ERROR_INT("new lstack array not defined", procName, 1);
217
218 lstack->nalloc = 2 * lstack->nalloc;
219 return 0;
220 }
221
222
223 /*!
224 * lstackGetCount()
225 *
226 * Input: lstack
227 * Return: count, or 0 on error
228 */
229 l_int32
lstackGetCount(L_STACK * lstack)230 lstackGetCount(L_STACK *lstack)
231 {
232 PROCNAME("lstackGetCount");
233
234 if (!lstack)
235 return ERROR_INT("lstack not defined", procName, 1);
236
237 return lstack->n;
238 }
239
240
241
242 /*---------------------------------------------------------------------*
243 * Debug output *
244 *---------------------------------------------------------------------*/
245 /*!
246 * lstackPrint()
247 *
248 * Input: stream
249 * lstack
250 * Return: 0 if OK; 1 on error
251 */
252 l_int32
lstackPrint(FILE * fp,L_STACK * lstack)253 lstackPrint(FILE *fp,
254 L_STACK *lstack)
255 {
256 l_int32 i;
257
258 PROCNAME("lstackPrint");
259
260 if (!fp)
261 return ERROR_INT("stream not defined", procName, 1);
262 if (!lstack)
263 return ERROR_INT("lstack not defined", procName, 1);
264
265 fprintf(fp, "\n Stack: nalloc = %d, n = %d, array = %p\n",
266 lstack->nalloc, lstack->n, lstack->array);
267 for (i = 0; i < lstack->n; i++)
268 fprintf(fp, "array[%d] = %p\n", i, lstack->array[i]);
269
270 return 0;
271 }
272
273