Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/leptonica/src/heap.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 heap.c
29 * <pre>
30 *
31 * Create/Destroy L_Heap
32 * L_HEAP *lheapCreate()
33 * void lheapDestroy()
34 *
35 * Operations to add/remove to/from the heap
36 * l_int32 lheapAdd()
37 * static l_int32 lheapExtendArray()
38 * void *lheapRemove()
39 *
40 * Other accessors
41 * l_int32 lheapGetCount()
42 * void *lheapGetElement()
43 *
44 * Heap sort
45 * l_int32 lheapSort()
46 * l_int32 lheapSortStrictOrder()
47 *
48 * Low-level heap operations
49 * static l_int32 lheapSwapUp()
50 * static l_int32 lheapSwapDown()
51 *
52 * Debug output
53 * l_int32 lheapPrint()
54 *
55 * The L_Heap is useful to implement a priority queue, that is sorted
56 * on a key in each element of the heap. The heap is an array
57 * of nearly arbitrary structs, with a l_float32 the first field.
58 * This field is the key on which the heap is sorted.
59 *
60 * Internally, we keep track of the heap size, n. The item at the
61 * root of the heap is at the head of the array. Items are removed
62 * from the head of the array and added to the end of the array.
63 * When an item is removed from the head, the item at the end
64 * of the array is moved to the head. When items are either
65 * added or removed, it is usually necessary to swap array items
66 * to restore the heap order. It is guaranteed that the number
67 * of swaps does not exceed log(n).
68 *
69 * -------------------------- N.B. ------------------------------
70 * The items on the heap (or, equivalently, in the array) are cast
71 * to void*. Their key is a l_float32, and it is REQUIRED that the
72 * key be the first field in the struct. That allows us to get the
73 * key by simply dereferencing the struct. Alternatively, we could
74 * choose (but don't) to pass an application-specific comparison
75 * function into the heap operation functions.
76 * -------------------------- N.B. ------------------------------
77 * </pre>
78 */
79
80 #ifdef HAVE_CONFIG_H
81 #include <config_auto.h>
82 #endif /* HAVE_CONFIG_H */
83
84 #include <string.h>
85 #include "allheaders.h"
86
87 /* Bounds on initial array size */
88 static const l_uint32 MaxPtrArraySize = 100000;
89 static const l_int32 InitialPtrArraySize = 20; /*!< n'importe quoi */
90
91 #define SWAP_ITEMS(i, j) { void *tempitem = lh->array[(i)]; \
92 lh->array[(i)] = lh->array[(j)]; \
93 lh->array[(j)] = tempitem; }
94
95 /* Static functions */
96 static l_int32 lheapExtendArray(L_HEAP *lh);
97 static l_ok lheapSwapUp(L_HEAP *lh, l_int32 index);
98 static l_ok lheapSwapDown(L_HEAP *lh);
99
100
101 /*--------------------------------------------------------------------------*
102 * L_Heap create/destroy *
103 *--------------------------------------------------------------------------*/
104 /*!
105 * \brief lheapCreate()
106 *
107 * \param[in] n size of ptr array to be alloc'd; use 0 for default
108 * \param[in] direction L_SORT_INCREASING, L_SORT_DECREASING
109 * \return lheap, or NULL on error
110 */
111 L_HEAP *
112 lheapCreate(l_int32 n,
113 l_int32 direction)
114 {
115 L_HEAP *lh;
116
117 if (n < InitialPtrArraySize || n > MaxPtrArraySize)
118 n = InitialPtrArraySize;
119
120 /* Allocate ptr array and initialize counters. */
121 lh = (L_HEAP *)LEPT_CALLOC(1, sizeof(L_HEAP));
122 if ((lh->array = (void **)LEPT_CALLOC(n, sizeof(void *))) == NULL) {
123 lheapDestroy(&lh, FALSE);
124 return (L_HEAP *)ERROR_PTR("ptr array not made", __func__, NULL);
125 }
126 lh->nalloc = n;
127 lh->n = 0;
128 lh->direction = direction;
129 return lh;
130 }
131
132
133 /*!
134 * \brief lheapDestroy()
135 *
136 * \param[in,out] plh will be set to null before returning
137 * \param[in] freeflag TRUE to free each remaining struct in the array
138 * \return void
139 *
140 * <pre>
141 * Notes:
142 * (1) Use %freeflag == TRUE when the items in the array can be
143 * simply destroyed using free. If those items require their
144 * own destroy function, they must be destroyed before
145 * calling this function, and then this function is called
146 * with %freeflag == FALSE.
147 * (2) To destroy the lheap, we destroy the ptr array, then
148 * the lheap, and then null the contents of the input ptr.
149 * </pre>
150 */
151 void
152 lheapDestroy(L_HEAP **plh,
153 l_int32 freeflag)
154 {
155 l_int32 i;
156 L_HEAP *lh;
157
158 if (plh == NULL) {
159 L_WARNING("ptr address is NULL\n", __func__);
160 return;
161 }
162 if ((lh = *plh) == NULL)
163 return;
164
165 if (freeflag) { /* free each struct in the array */
166 for (i = 0; i < lh->n; i++)
167 LEPT_FREE(lh->array[i]);
168 } else if (lh->n > 0) { /* freeflag == FALSE but elements exist on array */
169 L_WARNING("memory leak of %d items in lheap!\n", __func__, lh->n);
170 }
171
172 if (lh->array)
173 LEPT_FREE(lh->array);
174 LEPT_FREE(lh);
175 *plh = NULL;
176 }
177
178 /*--------------------------------------------------------------------------*
179 * Operations to add/remove to/from the heap *
180 *--------------------------------------------------------------------------*/
181 /*!
182 * \brief lheapAdd()
183 *
184 * \param[in] lh heap
185 * \param[in] item to be added to the tail of the heap
186 * \return 0 if OK, 1 on error
187 */
188 l_ok
189 lheapAdd(L_HEAP *lh,
190 void *item)
191 {
192 if (!lh)
193 return ERROR_INT("lh not defined", __func__, 1);
194 if (!item)
195 return ERROR_INT("item not defined", __func__, 1);
196
197 /* If necessary, expand the allocated array by a factor of 2 */
198 if (lh->n >= lh->nalloc) {
199 if (lheapExtendArray(lh))
200 return ERROR_INT("extension failed", __func__, 1);
201 }
202
203 /* Add the item */
204 lh->array[lh->n] = item;
205 lh->n++;
206
207 /* Restore the heap */
208 lheapSwapUp(lh, lh->n - 1);
209 return 0;
210 }
211
212
213 /*!
214 * \brief lheapExtendArray()
215 *
216 * \param[in] lh heap
217 * \return 0 if OK, 1 on error
218 */
219 static l_int32
220 lheapExtendArray(L_HEAP *lh)
221 {
222 if (!lh)
223 return ERROR_INT("lh not defined", __func__, 1);
224
225 if ((lh->array = (void **)reallocNew((void **)&lh->array,
226 sizeof(void *) * lh->nalloc,
227 2 * sizeof(void *) * lh->nalloc)) == NULL)
228 return ERROR_INT("new ptr array not returned", __func__, 1);
229
230 lh->nalloc = 2 * lh->nalloc;
231 return 0;
232 }
233
234
235 /*!
236 * \brief lheapRemove()
237 *
238 * \param[in] lh heap
239 * \return ptr to item popped from the root of the heap,
240 * or NULL if the heap is empty or on error
241 */
242 void *
243 lheapRemove(L_HEAP *lh)
244 {
245 void *item;
246
247 if (!lh)
248 return (void *)ERROR_PTR("lh not defined", __func__, NULL);
249
250 if (lh->n == 0)
251 return NULL;
252
253 item = lh->array[0];
254 lh->array[0] = lh->array[lh->n - 1]; /* move last to the head */
255 lh->array[lh->n - 1] = NULL; /* set ptr to null */
256 lh->n--;
257
258 lheapSwapDown(lh); /* restore the heap */
259 return item;
260 }
261
262
263 /*--------------------------------------------------------------------------*
264 * Other accessors *
265 *--------------------------------------------------------------------------*/
266 /*!
267 * \brief lheapGetCount()
268 *
269 * \param[in] lh heap
270 * \return count, or 0 on error
271 */
272 l_int32
273 lheapGetCount(L_HEAP *lh)
274 {
275 if (!lh)
276 return ERROR_INT("lh not defined", __func__, 0);
277
278 return lh->n;
279 }
280
281
282 /*!
283 * \brief lheapGetElement()
284 *
285 * \param[in] lh heap
286 * \param[in] index into the internal heap array
287 * \return ptr to the element at array[index], or NULL on error
288 *
289 * <pre>
290 * Notes:
291 * (1) This is useful for retrieving an arbitrary element in the
292 * heap array without disturbing the heap. It allows all the
293 * elements on the heap to be queried in linear time; for
294 * example, to find the min or max of some value.
295 * (2) The retrieved element is owned by the heap. Do not destroy it.
296 * </pre>
297 */
298 void *
299 lheapGetElement(L_HEAP *lh,
300 l_int32 index)
301 {
302 if (!lh)
303 return ERROR_PTR("lh not defined", __func__, NULL);
304 if (index < 0 || index >= lh->n)
305 return ERROR_PTR("invalid index", __func__, NULL);
306
307 return (void *)lh->array[index];
308 }
309
310
311 /*--------------------------------------------------------------------------*
312 * Heap sort *
313 *--------------------------------------------------------------------------*/
314 /*!
315 * \brief lheapSort()
316 *
317 * \param[in] lh heap, with internal array
318 * \return 0 if OK, 1 on error
319 *
320 * <pre>
321 * Notes:
322 * (1) This sorts an array into heap order. If the heap is already
323 * in heap order for the direction given, this has no effect.
324 * </pre>
325 */
326 l_ok
327 lheapSort(L_HEAP *lh)
328 {
329 l_int32 i;
330
331 if (!lh)
332 return ERROR_INT("lh not defined", __func__, 1);
333
334 for (i = 0; i < lh->n; i++)
335 lheapSwapUp(lh, i);
336
337 return 0;
338 }
339
340
341 /*!
342 * \brief lheapSortStrictOrder()
343 *
344 * \param[in] lh heap, with internal array
345 * \return 0 if OK, 1 on error
346 *
347 * <pre>
348 * Notes:
349 * (1) This sorts a heap into strict order.
350 * (2) For each element, starting at the end of the array and
351 * working forward, the element is swapped with the head
352 * element and then allowed to swap down onto a heap of
353 * size reduced by one. The result is that the heap is
354 * reversed but in strict order. The array elements are
355 * then reversed to put it in the original order.
356 * </pre>
357 */
358 l_ok
359 lheapSortStrictOrder(L_HEAP *lh)
360 {
361 l_int32 i, index, size;
362
363 if (!lh)
364 return ERROR_INT("lh not defined", __func__, 1);
365
366 /* Start from a sorted heap */
367 lheapSort(lh);
368
369 size = lh->n; /* save the actual size */
370 for (i = 0; i < size; i++) {
371 index = size - i;
372 SWAP_ITEMS(0, index - 1);
373 lh->n--; /* reduce the apparent heap size by 1 */
374 lheapSwapDown(lh);
375 }
376 lh->n = size; /* restore the size */
377
378 for (i = 0; i < size / 2; i++) /* reverse */
379 SWAP_ITEMS(i, size - i - 1);
380
381 return 0;
382 }
383
384
385 /*--------------------------------------------------------------------------*
386 * Low-level heap operations *
387 *--------------------------------------------------------------------------*/
388 /*!
389 * \brief lheapSwapUp()
390 *
391 * \param[in] lh heap
392 * \param[in] index of array corresponding to node to be swapped up
393 * \return 0 if OK, 1 on error
394 *
395 * <pre>
396 * Notes:
397 * (1) This is called after a new item is put on the heap, at the
398 * bottom of a complete tree.
399 * (2) To regain the heap order, we let it bubble up,
400 * iteratively swapping with its parent, until it either
401 * reaches the root of the heap or it finds a parent that
402 * is in the correct position already vis-a-vis the child.
403 * </pre>
404 */
405 static l_ok
406 lheapSwapUp(L_HEAP *lh,
407 l_int32 index)
408 {
409 l_int32 ip; /* index to heap for parent; 1 larger than array index */
410 l_int32 ic; /* index into heap for child */
411 l_float32 valp, valc;
412
413 if (!lh)
414 return ERROR_INT("lh not defined", __func__, 1);
415 if (index < 0 || index >= lh->n)
416 return ERROR_INT("invalid index", __func__, 1);
417
418 ic = index + 1; /* index into heap: add 1 to array index */
419 if (lh->direction == L_SORT_INCREASING) {
420 while (1) {
421 if (ic == 1) /* root of heap */
422 break;
423 ip = ic / 2;
424 valc = *(l_float32 *)(lh->array[ic - 1]);
425 valp = *(l_float32 *)(lh->array[ip - 1]);
426 if (valp <= valc)
427 break;
428 SWAP_ITEMS(ip - 1, ic - 1);
429 ic = ip;
430 }
431 } else { /* lh->direction == L_SORT_DECREASING */
432 while (1) {
433 if (ic == 1) /* root of heap */
434 break;
435 ip = ic / 2;
436 valc = *(l_float32 *)(lh->array[ic - 1]);
437 valp = *(l_float32 *)(lh->array[ip - 1]);
438 if (valp >= valc)
439 break;
440 SWAP_ITEMS(ip - 1, ic - 1);
441 ic = ip;
442 }
443 }
444 return 0;
445 }
446
447
448 /*!
449 * \brief lheapSwapDown()
450 *
451 * \param[in] lh heap
452 * \return 0 if OK, 1 on error
453 *
454 * <pre>
455 * Notes:
456 * (1) This is called after an item has been popped off the
457 * root of the heap, and the last item in the heap has
458 * been placed at the root.
459 * (2) To regain the heap order, we let it bubble down,
460 * iteratively swapping with one of its children. For a
461 * decreasing sort, it swaps with the largest child; for
462 * an increasing sort, the smallest. This continues until
463 * it either reaches the lowest level in the heap, or the
464 * parent finds that neither child should swap with it
465 * (e.g., for a decreasing heap, the parent is larger
466 * than or equal to both children).
467 * </pre>
468 */
469 static l_ok
470 lheapSwapDown(L_HEAP *lh)
471 {
472 l_int32 ip; /* index to heap for parent; 1 larger than array index */
473 l_int32 icr, icl; /* index into heap for left/right children */
474 l_float32 valp, valcl, valcr;
475
476 if (!lh)
477 return ERROR_INT("lh not defined", __func__, 1);
478 if (lheapGetCount(lh) < 1)
479 return 0;
480
481 ip = 1; /* index into top of heap: corresponds to array[0] */
482 if (lh->direction == L_SORT_INCREASING) {
483 while (1) {
484 icl = 2 * ip;
485 if (icl > lh->n)
486 break;
487 valp = *(l_float32 *)(lh->array[ip - 1]);
488 valcl = *(l_float32 *)(lh->array[icl - 1]);
489 icr = icl + 1;
490 if (icr > lh->n) { /* only a left child; no iters below */
491 if (valp > valcl)
492 SWAP_ITEMS(ip - 1, icl - 1);
493 break;
494 } else { /* both children exist; swap with the smallest if bigger */
495 valcr = *(l_float32 *)(lh->array[icr - 1]);
496 if (valp <= valcl && valp <= valcr) /* smaller than both */
497 break;
498 if (valcl <= valcr) { /* left smaller; swap */
499 SWAP_ITEMS(ip - 1, icl - 1);
500 ip = icl;
501 } else { /* right smaller; swap */
502 SWAP_ITEMS(ip - 1, icr - 1);
503 ip = icr;
504 }
505 }
506 }
507 } else { /* lh->direction == L_SORT_DECREASING */
508 while (1) {
509 icl = 2 * ip;
510 if (icl > lh->n)
511 break;
512 valp = *(l_float32 *)(lh->array[ip - 1]);
513 valcl = *(l_float32 *)(lh->array[icl - 1]);
514 icr = icl + 1;
515 if (icr > lh->n) { /* only a left child; no iters below */
516 if (valp < valcl)
517 SWAP_ITEMS(ip - 1, icl - 1);
518 break;
519 } else { /* both children exist; swap with the biggest if smaller */
520 valcr = *(l_float32 *)(lh->array[icr - 1]);
521 if (valp >= valcl && valp >= valcr) /* bigger than both */
522 break;
523 if (valcl >= valcr) { /* left bigger; swap */
524 SWAP_ITEMS(ip - 1, icl - 1);
525 ip = icl;
526 } else { /* right bigger; swap */
527 SWAP_ITEMS(ip - 1, icr - 1);
528 ip = icr;
529 }
530 }
531 }
532 }
533
534 return 0;
535 }
536
537
538 /*---------------------------------------------------------------------*
539 * Debug output *
540 *---------------------------------------------------------------------*/
541 /*!
542 * \brief lheapPrint()
543 *
544 * \param[in] fp file stream
545 * \param[in] lh heap
546 * \return 0 if OK; 1 on error
547 */
548 l_ok
549 lheapPrint(FILE *fp,
550 L_HEAP *lh)
551 {
552 l_int32 i;
553
554 if (!fp)
555 return ERROR_INT("stream not defined", __func__, 1);
556 if (!lh)
557 return ERROR_INT("lh not defined", __func__, 1);
558
559 fprintf(fp, "\n L_Heap: nalloc = %d, n = %d, array = %p\n",
560 lh->nalloc, lh->n, lh->array);
561 for (i = 0; i < lh->n; i++)
562 fprintf(fp, "keyval[%d] = %f\n", i, *(l_float32 *)lh->array[i]);
563
564 return 0;
565 }