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 * queue.c
18 *
19 * Create/Destroy L_Queue
20 * L_QUEUE *lqueueCreate()
21 * void *lqueueDestroy()
22 *
23 * Operations to add/remove to/from a L_Queue
24 * l_int32 lqueueAdd()
25 * l_int32 lqueueExtendArray()
26 * void *lqueueRemove()
27 *
28 * Accessors
29 * l_int32 lqueueGetCount()
30 *
31 * Debug output
32 * l_int32 lqueuePrint()
33 *
34 * The lqueue is a fifo that implements a queue of void* pointers.
35 * It can be used to hold a queue of any type of struct.
36 * Internally, it maintains two counters:
37 * nhead: location of head (in ptrs) from the beginning
38 * of the buffer
39 * nelem: number of ptr elements stored in the queue
40 * As items are added to the queue, nelem increases.
41 * As items are removed, nhead increases and nelem decreases.
42 * Any time the tail reaches the end of the allocated buffer,
43 * all the pointers are shifted to the left, so that the head
44 * is at the beginning of the array.
45 * If the buffer becomes more than 3/4 full, it doubles in size.
46 *
47 * [A circular queue would allow us to skip the shifting and
48 * to resize only when the buffer is full. For most applications,
49 * the extra work we do for a linear queue is not significant.]
50 */
51
52 #include <stdio.h>
53 #include <string.h>
54 #include <stdlib.h>
55 #include "allheaders.h"
56
57 static const l_int32 MIN_BUFFER_SIZE = 20; /* n'importe quoi */
58 static const l_int32 INITIAL_BUFFER_ARRAYSIZE = 1024; /* n'importe quoi */
59
60
61 /*--------------------------------------------------------------------------*
62 * L_Queue create/destroy *
63 *--------------------------------------------------------------------------*/
64 /*!
65 * lqueueCreate()
66 *
67 * Input: size of ptr array to be alloc'd (0 for default)
68 * Return: lqueue, or null on error
69 *
70 * Notes:
71 * (1) Allocates a ptr array of given size, and initializes counters.
72 */
73 L_QUEUE *
lqueueCreate(l_int32 nalloc)74 lqueueCreate(l_int32 nalloc)
75 {
76 L_QUEUE *lq;
77
78 PROCNAME("lqueueCreate");
79
80 if (nalloc < MIN_BUFFER_SIZE)
81 nalloc = INITIAL_BUFFER_ARRAYSIZE;
82
83 if ((lq = (L_QUEUE *)CALLOC(1, sizeof(L_QUEUE))) == NULL)
84 return (L_QUEUE *)ERROR_PTR("lq not made", procName, NULL);
85 if ((lq->array = (void **)CALLOC(nalloc, sizeof(void *))) == NULL)
86 return (L_QUEUE *)ERROR_PTR("ptr array not made", procName, NULL);
87 lq->nalloc = nalloc;
88 lq->nhead = lq->nelem = 0;
89 return lq;
90 }
91
92
93 /*!
94 * lqueueDestroy()
95 *
96 * Input: &lqueue (<to be nulled>)
97 * freeflag (TRUE to free each remaining struct in the array)
98 * Return: void
99 *
100 * Notes:
101 * (1) If freeflag is TRUE, frees each struct in the array.
102 * (2) If freeflag is FALSE but there are elements on the array,
103 * gives a warning and destroys the array. This will
104 * cause a memory leak of all the items that were on the queue.
105 * So if the items require their own destroy function, they
106 * must be destroyed before the queue. The same applies to the
107 * auxiliary stack, if it is used.
108 * (3) To destroy the L_Queue, we destroy the ptr array, then
109 * the lqueue, and then null the contents of the input ptr.
110 */
111 void
lqueueDestroy(L_QUEUE ** plq,l_int32 freeflag)112 lqueueDestroy(L_QUEUE **plq,
113 l_int32 freeflag)
114 {
115 void *item;
116 L_QUEUE *lq;
117
118 PROCNAME("lqueueDestroy");
119
120 if (plq == NULL) {
121 L_WARNING("ptr address is NULL", procName);
122 return;
123 }
124 if ((lq = *plq) == NULL)
125 return;
126
127 if (freeflag) {
128 while(lq->nelem > 0) {
129 item = lqueueRemove(lq);
130 FREE(item);
131 }
132 }
133 else if (lq->nelem > 0)
134 L_WARNING_INT("memory leak of %d items in lqueue!",
135 procName, lq->nelem);
136
137 if (lq->array)
138 FREE(lq->array);
139 if (lq->stack)
140 lstackDestroy(&lq->stack, freeflag);
141 FREE(lq);
142 *plq = NULL;
143
144 return;
145 }
146
147
148 /*--------------------------------------------------------------------------*
149 * Accessors *
150 *--------------------------------------------------------------------------*/
151 /*!
152 * lqueueAdd()
153 *
154 * Input: lqueue
155 * item to be added to the tail of the queue
156 * Return: 0 if OK, 1 on error
157 *
158 * Notes:
159 * (1) The algorithm is as follows. If the queue is populated
160 * to the end of the allocated array, shift all ptrs toward
161 * the beginning of the array, so that the head of the queue
162 * is at the beginning of the array. Then, if the array is
163 * more than 0.75 full, realloc with double the array size.
164 * Finally, add the item to the tail of the queue.
165 */
166 l_int32
lqueueAdd(L_QUEUE * lq,void * item)167 lqueueAdd(L_QUEUE *lq,
168 void *item)
169 {
170 PROCNAME("lqueueAdd");
171
172 if (!lq)
173 return ERROR_INT("lq not defined", procName, 1);
174 if (!item)
175 return ERROR_INT("item not defined", procName, 1);
176
177 /* If filled to the end and the ptrs can be shifted to the left,
178 * shift them. */
179 if ((lq->nhead + lq->nelem >= lq->nalloc) && (lq->nhead != 0)) {
180 memmove(lq->array, lq->array + lq->nhead, sizeof(void *) * lq->nelem);
181 lq->nhead = 0;
182 }
183
184 /* If necessary, expand the allocated array by a factor of 2 */
185 if (lq->nelem > 0.75 * lq->nalloc)
186 lqueueExtendArray(lq);
187
188 /* Now add the item */
189 lq->array[lq->nhead + lq->nelem] = (void *)item;
190 lq->nelem++;
191
192 return 0;
193 }
194
195
196 /*!
197 * lqueueExtendArray()
198 *
199 * Input: lqueue
200 * Return: 0 if OK, 1 on error
201 */
202 l_int32
lqueueExtendArray(L_QUEUE * lq)203 lqueueExtendArray(L_QUEUE *lq)
204 {
205 PROCNAME("lqueueExtendArray");
206
207 if (!lq)
208 return ERROR_INT("lq not defined", procName, 1);
209
210 if ((lq->array = (void **)reallocNew((void **)&lq->array,
211 sizeof(void *) * lq->nalloc,
212 2 * sizeof(void *) * lq->nalloc)) == NULL)
213 return ERROR_INT("new ptr array not returned", procName, 1);
214
215 lq->nalloc = 2 * lq->nalloc;
216 return 0;
217 }
218
219
220 /*!
221 * lqueueRemove()
222 *
223 * Input: lqueue
224 * Return: ptr to item popped from the head of the queue,
225 * or null if the queue is empty or on error
226 *
227 * Notes:
228 * (1) If this is the last item on the queue, so that the queue
229 * becomes empty, nhead is reset to the beginning of the array.
230 */
231 void *
lqueueRemove(L_QUEUE * lq)232 lqueueRemove(L_QUEUE *lq)
233 {
234 void *item;
235
236 PROCNAME("lqueueRemove");
237
238 if (!lq)
239 return (void *)ERROR_PTR("lq not defined", procName, NULL);
240
241 if (lq->nelem == 0)
242 return NULL;
243 item = lq->array[lq->nhead];
244 lq->array[lq->nhead] = NULL;
245 if (lq->nelem == 1)
246 lq->nhead = 0; /* reset head ptr */
247 else
248 (lq->nhead)++; /* can't go off end of array because nelem > 1 */
249 lq->nelem--;
250 return item;
251 }
252
253
254 /*!
255 * lqueueGetCount()
256 *
257 * Input: lqueue
258 * Return: count, or 0 on error
259 */
260 l_int32
lqueueGetCount(L_QUEUE * lq)261 lqueueGetCount(L_QUEUE *lq)
262 {
263 PROCNAME("lqueueGetCount");
264
265 if (!lq)
266 return ERROR_INT("lq not defined", procName, 0);
267
268 return lq->nelem;
269 }
270
271
272 /*---------------------------------------------------------------------*
273 * Debug output *
274 *---------------------------------------------------------------------*/
275 /*!
276 * lqueuePrint()
277 *
278 * Input: stream
279 * lqueue
280 * Return: 0 if OK; 1 on error
281 */
282 l_int32
lqueuePrint(FILE * fp,L_QUEUE * lq)283 lqueuePrint(FILE *fp,
284 L_QUEUE *lq)
285 {
286 l_int32 i;
287
288 PROCNAME("lqueuePrint");
289
290 if (!fp)
291 return ERROR_INT("stream not defined", procName, 1);
292 if (!lq)
293 return ERROR_INT("lq not defined", procName, 1);
294
295 fprintf(fp, "\n L_Queue: nalloc = %d, nhead = %d, nelem = %d, array = %p\n",
296 lq->nalloc, lq->nhead, lq->nelem, lq->array);
297 for (i = lq->nhead; i < lq->nhead + lq->nelem; i++)
298 fprintf(fp, "array[%d] = %p\n", i, lq->array[i]);
299
300 return 0;
301 }
302
303