Leptonica  1.82.0
Image processing and image analysis suite
queue.c
Go to the documentation of this file.
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 
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  *--------------------------------------------------------------------------*/
92 L_QUEUE *
94 {
95 L_QUEUE *lq;
96 
97  PROCNAME("lqueueCreate");
98 
99  if (nalloc < MIN_BUFFER_SIZE)
100  nalloc = INITIAL_BUFFER_ARRAYSIZE;
101 
102  lq = (L_QUEUE *)LEPT_CALLOC(1, sizeof(L_QUEUE));
103  if ((lq->array = (void **)LEPT_CALLOC(nalloc, sizeof(void *))) == NULL) {
104  lqueueDestroy(&lq, 0);
105  return (L_QUEUE *)ERROR_PTR("ptr array not made", procName, NULL);
106  }
107  lq->nalloc = nalloc;
108  lq->nhead = lq->nelem = 0;
109  return lq;
110 }
111 
112 
133 void
135  l_int32 freeflag)
136 {
137 void *item;
138 L_QUEUE *lq;
139 
140  PROCNAME("lqueueDestroy");
141 
142  if (plq == NULL) {
143  L_WARNING("ptr address is NULL\n", procName);
144  return;
145  }
146  if ((lq = *plq) == NULL)
147  return;
148 
149  if (freeflag) {
150  while(lq->nelem > 0) {
151  item = lqueueRemove(lq);
152  LEPT_FREE(item);
153  }
154  } else if (lq->nelem > 0) {
155  L_WARNING("memory leak of %d items in lqueue!\n", procName, lq->nelem);
156  }
157 
158  if (lq->array)
159  LEPT_FREE(lq->array);
160  if (lq->stack)
161  lstackDestroy(&lq->stack, freeflag);
162  LEPT_FREE(lq);
163  *plq = NULL;
164 }
165 
166 
167 /*--------------------------------------------------------------------------*
168  * Accessors *
169  *--------------------------------------------------------------------------*/
187 l_ok
189  void *item)
190 {
191  PROCNAME("lqueueAdd");
192 
193  if (!lq)
194  return ERROR_INT("lq not defined", procName, 1);
195  if (!item)
196  return ERROR_INT("item not defined", procName, 1);
197 
198  /* If filled to the end and the ptrs can be shifted to the left,
199  * shift them. */
200  if ((lq->nhead + lq->nelem >= lq->nalloc) && (lq->nhead != 0)) {
201  memmove(lq->array, lq->array + lq->nhead, sizeof(void *) * lq->nelem);
202  lq->nhead = 0;
203  }
204 
205  /* If necessary, expand the allocated array by a factor of 2 */
206  if (lq->nelem > 0.75 * lq->nalloc) {
207  if (lqueueExtendArray(lq))
208  return ERROR_INT("extension failed", procName, 1);
209  }
210 
211  /* Now add the item */
212  lq->array[lq->nhead + lq->nelem] = (void *)item;
213  lq->nelem++;
214 
215  return 0;
216 }
217 
218 
225 static l_int32
227 {
228  PROCNAME("lqueueExtendArray");
229 
230  if (!lq)
231  return ERROR_INT("lq not defined", procName, 1);
232 
233  if ((lq->array = (void **)reallocNew((void **)&lq->array,
234  sizeof(void *) * lq->nalloc,
235  2 * sizeof(void *) * lq->nalloc)) == NULL)
236  return ERROR_INT("new ptr array not returned", procName, 1);
237 
238  lq->nalloc = 2 * lq->nalloc;
239  return 0;
240 }
241 
242 
256 void *
258 {
259 void *item;
260 
261  PROCNAME("lqueueRemove");
262 
263  if (!lq)
264  return (void *)ERROR_PTR("lq not defined", procName, NULL);
265 
266  if (lq->nelem == 0)
267  return NULL;
268  item = lq->array[lq->nhead];
269  lq->array[lq->nhead] = NULL;
270  if (lq->nelem == 1)
271  lq->nhead = 0; /* reset head ptr */
272  else
273  (lq->nhead)++; /* can't go off end of array because nelem > 1 */
274  lq->nelem--;
275  return item;
276 }
277 
278 
285 l_int32
287 {
288  PROCNAME("lqueueGetCount");
289 
290  if (!lq)
291  return ERROR_INT("lq not defined", procName, 0);
292 
293  return lq->nelem;
294 }
295 
296 
297 /*---------------------------------------------------------------------*
298  * Debug output *
299  *---------------------------------------------------------------------*/
307 l_ok
308 lqueuePrint(FILE *fp,
309  L_QUEUE *lq)
310 {
311 l_int32 i;
312 
313  PROCNAME("lqueuePrint");
314 
315  if (!fp)
316  return ERROR_INT("stream not defined", procName, 1);
317  if (!lq)
318  return ERROR_INT("lq not defined", procName, 1);
319 
320  fprintf(fp, "\n L_Queue: nalloc = %d, nhead = %d, nelem = %d, array = %p\n",
321  lq->nalloc, lq->nhead, lq->nelem, lq->array);
322  for (i = lq->nhead; i < lq->nhead + lq->nelem; i++)
323  fprintf(fp, "array[%d] = %p\n", i, lq->array[i]);
324 
325  return 0;
326 }
l_int32 nalloc
Definition: queue.h:66
l_ok lqueuePrint(FILE *fp, L_QUEUE *lq)
lqueuePrint()
Definition: queue.c:308
void lstackDestroy(L_STACK **plstack, l_int32 freeflag)
lstackDestroy()
Definition: stack.c:124
L_QUEUE * lqueueCreate(l_int32 nalloc)
lqueueCreate()
Definition: queue.c:93
l_int32 nelem
Definition: queue.h:69
struct L_Stack * stack
Definition: queue.h:71
void * lqueueRemove(L_QUEUE *lq)
lqueueRemove()
Definition: queue.c:257
void ** array
Definition: queue.h:70
l_int32 nalloc
Definition: ptra.h:66
l_ok lqueueAdd(L_QUEUE *lq, void *item)
lqueueAdd()
Definition: queue.c:188
Definition: queue.h:64
void * reallocNew(void **pindata, size_t oldsize, size_t newsize)
reallocNew()
Definition: utils2.c:1302
l_int32 lqueueGetCount(L_QUEUE *lq)
lqueueGetCount()
Definition: queue.c:286
void lqueueDestroy(L_QUEUE **plq, l_int32 freeflag)
lqueueDestroy()
Definition: queue.c:134
static l_int32 lqueueExtendArray(L_QUEUE *lq)
lqueueExtendArray()
Definition: queue.c:226
l_int32 nhead
Definition: queue.h:67