Leptonica  1.83.1
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 *
93 lqueueCreate(l_int32 nalloc)
94 {
95 L_QUEUE *lq;
96 
97  if (nalloc < MIN_BUFFER_SIZE)
98  nalloc = INITIAL_BUFFER_ARRAYSIZE;
99 
100  lq = (L_QUEUE *)LEPT_CALLOC(1, sizeof(L_QUEUE));
101  if ((lq->array = (void **)LEPT_CALLOC(nalloc, sizeof(void *))) == NULL) {
102  lqueueDestroy(&lq, 0);
103  return (L_QUEUE *)ERROR_PTR("ptr array not made", __func__, NULL);
104  }
105  lq->nalloc = nalloc;
106  lq->nhead = lq->nelem = 0;
107  return lq;
108 }
109 
110 
131 void
133  l_int32 freeflag)
134 {
135 void *item;
136 L_QUEUE *lq;
137 
138  if (plq == NULL) {
139  L_WARNING("ptr address is NULL\n", __func__);
140  return;
141  }
142  if ((lq = *plq) == NULL)
143  return;
144 
145  if (freeflag) {
146  while(lq->nelem > 0) {
147  item = lqueueRemove(lq);
148  LEPT_FREE(item);
149  }
150  } else if (lq->nelem > 0) {
151  L_WARNING("memory leak of %d items in lqueue!\n", __func__, lq->nelem);
152  }
153 
154  if (lq->array)
155  LEPT_FREE(lq->array);
156  if (lq->stack)
157  lstackDestroy(&lq->stack, freeflag);
158  LEPT_FREE(lq);
159  *plq = NULL;
160 }
161 
162 
163 /*--------------------------------------------------------------------------*
164  * Accessors *
165  *--------------------------------------------------------------------------*/
183 l_ok
185  void *item)
186 {
187  if (!lq)
188  return ERROR_INT("lq not defined", __func__, 1);
189  if (!item)
190  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  if ((lq->nhead + lq->nelem >= lq->nalloc) && (lq->nhead != 0)) {
195  memmove(lq->array, lq->array + lq->nhead, sizeof(void *) * lq->nelem);
196  lq->nhead = 0;
197  }
198 
199  /* If necessary, expand the allocated array by a factor of 2 */
200  if (lq->nelem > 0.75 * lq->nalloc) {
201  if (lqueueExtendArray(lq))
202  return ERROR_INT("extension failed", __func__, 1);
203  }
204 
205  /* Now add the item */
206  lq->array[lq->nhead + lq->nelem] = (void *)item;
207  lq->nelem++;
208 
209  return 0;
210 }
211 
212 
219 static l_int32
221 {
222  if (!lq)
223  return ERROR_INT("lq not defined", __func__, 1);
224 
225  if ((lq->array = (void **)reallocNew((void **)&lq->array,
226  sizeof(void *) * lq->nalloc,
227  2 * sizeof(void *) * lq->nalloc)) == NULL)
228  return ERROR_INT("new ptr array not returned", __func__, 1);
229 
230  lq->nalloc = 2 * lq->nalloc;
231  return 0;
232 }
233 
234 
248 void *
250 {
251 void *item;
252 
253  if (!lq)
254  return (void *)ERROR_PTR("lq not defined", __func__, NULL);
255 
256  if (lq->nelem == 0)
257  return NULL;
258  item = lq->array[lq->nhead];
259  lq->array[lq->nhead] = NULL;
260  if (lq->nelem == 1)
261  lq->nhead = 0; /* reset head ptr */
262  else
263  (lq->nhead)++; /* can't go off end of array because nelem > 1 */
264  lq->nelem--;
265  return item;
266 }
267 
268 
275 l_int32
277 {
278  if (!lq)
279  return ERROR_INT("lq not defined", __func__, 0);
280 
281  return lq->nelem;
282 }
283 
284 
285 /*---------------------------------------------------------------------*
286  * Debug output *
287  *---------------------------------------------------------------------*/
295 l_ok
296 lqueuePrint(FILE *fp,
297  L_QUEUE *lq)
298 {
299 l_int32 i;
300 
301  if (!fp)
302  return ERROR_INT("stream not defined", __func__, 1);
303  if (!lq)
304  return ERROR_INT("lq not defined", __func__, 1);
305 
306  fprintf(fp, "\n L_Queue: nalloc = %d, nhead = %d, nelem = %d, array = %p\n",
307  lq->nalloc, lq->nhead, lq->nelem, lq->array);
308  for (i = lq->nhead; i < lq->nhead + lq->nelem; i++)
309  fprintf(fp, "array[%d] = %p\n", i, lq->array[i]);
310 
311  return 0;
312 }
l_int32 lqueueGetCount(L_QUEUE *lq)
lqueueGetCount()
Definition: queue.c:276
static l_int32 lqueueExtendArray(L_QUEUE *lq)
lqueueExtendArray()
Definition: queue.c:220
void lqueueDestroy(L_QUEUE **plq, l_int32 freeflag)
lqueueDestroy()
Definition: queue.c:132
l_ok lqueuePrint(FILE *fp, L_QUEUE *lq)
lqueuePrint()
Definition: queue.c:296
void * lqueueRemove(L_QUEUE *lq)
lqueueRemove()
Definition: queue.c:249
l_ok lqueueAdd(L_QUEUE *lq, void *item)
lqueueAdd()
Definition: queue.c:184
L_QUEUE * lqueueCreate(l_int32 nalloc)
lqueueCreate()
Definition: queue.c:93
void lstackDestroy(L_STACK **plstack, l_int32 freeflag)
lstackDestroy()
Definition: stack.c:122
Definition: queue.h:65
l_int32 nhead
Definition: queue.h:67
struct L_Stack * stack
Definition: queue.h:71
l_int32 nalloc
Definition: queue.h:66
void ** array
Definition: queue.h:70
l_int32 nelem
Definition: queue.h:69
void * reallocNew(void **pindata, size_t oldsize, size_t newsize)
reallocNew()
Definition: utils2.c:1262