Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/leptonica/src/queue.c @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
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 queue.c
29 * <pre>
30 *
31 * Create/Destroy L_Queue
32 * L_QUEUE *lqueueCreate()
33 * void *lqueueDestroy()
34 *
35 * Operations to add/remove to/from a L_Queue
36 * l_int32 lqueueAdd()
37 * static l_int32 lqueueExtendArray()
38 * void *lqueueRemove()
39 *
40 * Accessors
41 * l_int32 lqueueGetCount()
42 *
43 * Debug output
44 * l_int32 lqueuePrint()
45 *
46 * The lqueue is a fifo that implements a queue of void* pointers.
47 * It can be used to hold a queue of any type of struct.
48 * Internally, it maintains two counters:
49 * nhead: location of head (in ptrs) from the beginning
50 * of the buffer
51 * nelem: number of ptr elements stored in the queue
52 * As items are added to the queue, nelem increases.
53 * As items are removed, nhead increases and nelem decreases.
54 * Any time the tail reaches the end of the allocated buffer,
55 * all the pointers are shifted to the left, so that the head
56 * is at the beginning of the array.
57 * If the buffer becomes more than 3/4 full, it doubles in size.
58 *
59 * [A circular queue would allow us to skip the shifting and
60 * to resize only when the buffer is full. For most applications,
61 * the extra work we do for a linear queue is not significant.]
62 * </pre>
63 */
64
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 *--------------------------------------------------------------------------*/
81 /*!
82 * \brief lqueueCreate()
83 *
84 * \param[in] nalloc size of ptr array to be alloc'd; 0 for default
85 * \return lqueue, or NULL on error
86 *
87 * <pre>
88 * Notes:
89 * (1) Allocates a ptr array of given size, and initializes counters.
90 * </pre>
91 */
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
111 /*!
112 * \brief lqueueDestroy()
113 *
114 * \param[in,out] plq will be set to null before returning
115 * \param[in] freeflag TRUE to free each remaining struct in the array
116 * \return void
117 *
118 * <pre>
119 * Notes:
120 * (1) If freeflag is TRUE, frees each struct in the array.
121 * (2) If freeflag is FALSE but there are elements on the array,
122 * gives a warning and destroys the array. This will
123 * cause a memory leak of all the items that were on the queue.
124 * So if the items require their own destroy function, they
125 * must be destroyed before the queue. The same applies to the
126 * auxiliary stack, if it is used.
127 * (3) To destroy the L_Queue, we destroy the ptr array, then
128 * the lqueue, and then null the contents of the input ptr.
129 * </pre>
130 */
131 void
132 lqueueDestroy(L_QUEUE **plq,
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 *--------------------------------------------------------------------------*/
166 /*!
167 * \brief lqueueAdd()
168 *
169 * \param[in] lq lqueue
170 * \param[in] item to be added to the tail of the queue
171 * \return 0 if OK, 1 on error
172 *
173 * <pre>
174 * Notes:
175 * (1) The algorithm is as follows. If the queue is populated
176 * to the end of the allocated array, shift all ptrs toward
177 * the beginning of the array, so that the head of the queue
178 * is at the beginning of the array. Then, if the array is
179 * more than 0.75 full, realloc with double the array size.
180 * Finally, add the item to the tail of the queue.
181 * </pre>
182 */
183 l_ok
184 lqueueAdd(L_QUEUE *lq,
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
213 /*!
214 * \brief lqueueExtendArray()
215 *
216 * \param[in] lq lqueue
217 * \return 0 if OK, 1 on error
218 */
219 static l_int32
220 lqueueExtendArray(L_QUEUE *lq)
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
235 /*!
236 * \brief lqueueRemove()
237 *
238 * \param[in] lq lqueue
239 * \return ptr to item popped from the head of the queue,
240 * or NULL if the queue is empty or on error
241 *
242 * <pre>
243 * Notes:
244 * (1) If this is the last item on the queue, so that the queue
245 * becomes empty, nhead is reset to the beginning of the array.
246 * </pre>
247 */
248 void *
249 lqueueRemove(L_QUEUE *lq)
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
269 /*!
270 * \brief lqueueGetCount()
271 *
272 * \param[in] lq lqueue
273 * \return count, or 0 on error
274 */
275 l_int32
276 lqueueGetCount(L_QUEUE *lq)
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 *---------------------------------------------------------------------*/
288 /*!
289 * \brief lqueuePrint()
290 *
291 * \param[in] fp file stream
292 * \param[in] lq lqueue
293 * \return 0 if OK; 1 on error
294 */
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 }