Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/leptonica/src/ptra.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 ptra.c
29 * <pre>
30 *
31 * Ptra creation and destruction
32 * L_PTRA *ptraCreate()
33 * void *ptraDestroy()
34 *
35 * Add/insert/remove/replace generic ptr object
36 * l_int32 ptraAdd()
37 * static l_int32 ptraExtendArray()
38 * l_int32 ptraInsert()
39 * void *ptraRemove()
40 * void *ptraRemoveLast()
41 * void *ptraReplace()
42 * l_int32 ptraSwap()
43 * l_int32 ptraCompactArray()
44 *
45 * Other array operations
46 * l_int32 ptraReverse()
47 * l_int32 ptraJoin()
48 *
49 * Simple Ptra accessors
50 * l_int32 ptraGetMaxIndex()
51 * l_int32 ptraGetActualCount()
52 * void *ptraGetPtrToItem()
53 *
54 * Ptraa creation and destruction
55 * L_PTRAA *ptraaCreate()
56 * void *ptraaDestroy()
57 *
58 * Ptraa accessors
59 * l_int32 ptraaGetSize()
60 * l_int32 ptraaInsertPtra()
61 * L_PTRA *ptraaGetPtra()
62 *
63 * Ptraa conversion
64 * L_PTRA *ptraaFlattenToPtra()
65 *
66 * Notes on the Ptra:
67 *
68 * (1) The Ptra is a struct, not an array. Always use the accessors
69 * in this file, never the fields directly.
70 * (2) Items can be placed anywhere in the allocated ptr array,
71 * including one index beyond the last ptr (in which case the
72 * ptr array is realloc'd).
73 * (3) Thus, the items on the ptr array need not be compacted. In
74 * general there will be null pointers in the ptr array.
75 * (4) A compacted array will remain compacted on removal if
76 * arbitrary items are removed with compaction, or if items
77 * are removed from the end of the array.
78 * (5) For addition to and removal from the end of the array, this
79 * functions exactly like a stack, and with the same O(1) cost.
80 * (6) This differs from the generic stack in that we allow
81 * random access for insertion, removal and replacement.
82 * Removal can be done without compacting the array.
83 * Insertion into a null ptr in the array has no effect on
84 * the other pointers, but insertion into a location already
85 * occupied by an item has a cost proportional to the
86 * distance to the next null ptr in the array.
87 * (7) Null ptrs are valid input args for both insertion and
88 * replacement; this allows arbitrary swapping.
89 * (8) The item in the array with the largest index is at pa->imax.
90 * This can be any value from -1 (initialized; all array ptrs
91 * are null) up to pa->nalloc - 1 (the last ptr in the array).
92 * (9) In referring to the array: the first ptr is the "top" or
93 * "beginning"; the last pointer is the "bottom" or "end";
94 * items are shifted "up" towards the top when compaction occurs;
95 * and items are shifted "down" towards the bottom when forced to
96 * move due to an insertion.
97 * (10) It should be emphasized that insertion, removal and replacement
98 * are general:
99 * * You can insert an item into any ptr location in the
100 * allocated ptr array, as well as into the next ptr address
101 * beyond the allocated array (in which case a realloc will occur).
102 * * You can remove or replace an item from any ptr location
103 * in the allocated ptr array.
104 * * When inserting into an occupied location, you have
105 * three options for downshifting.
106 * * When removing, you can either leave the ptr null or
107 * compact the array.
108 *
109 * Notes on the Ptraa:
110 *
111 * (1) The Ptraa is a fixed size ptr array for holding Ptra.
112 * In that respect, it is different from other pointer arrays, which
113 * are extensible and grow using the *Add*() functions.
114 * (2) In general, the Ptra ptrs in the Ptraa can be randomly occupied.
115 * A typical usage is to allow an O(n) horizontal sort of Pix,
116 * where the size of the Ptra array is the width of the image,
117 * and each Ptra is an array of all the Pix at a specific x location.
118 * </pre>
119 */
120
121 #ifdef HAVE_CONFIG_H
122 #include <config_auto.h>
123 #endif /* HAVE_CONFIG_H */
124
125 #include "allheaders.h"
126
127 /* Bounds on initial array size */
128 LEPT_DLL const l_uint32 MaxInitPtraSize = 1000001;
129 static const l_int32 DefaultInitPtraSize = 20; /*!< n'importe quoi */
130
131 /* Static function */
132 static l_int32 ptraExtendArray(L_PTRA *pa);
133
134 /*--------------------------------------------------------------------------*
135 * Ptra creation and destruction *
136 *--------------------------------------------------------------------------*/
137 /*!
138 * \brief ptraCreate()
139 *
140 * \param[in] n size of ptr array to be alloc'd; use 0 for default
141 * \return pa, or NULL on error
142 */
143 L_PTRA *
144 ptraCreate(l_int32 n)
145 {
146 L_PTRA *pa;
147
148 if (n > (l_int32)MaxInitPtraSize) {
149 L_ERROR("n = %d > maxsize = %d\n", __func__, n, MaxInitPtraSize);
150 return NULL;
151 }
152 if (n <= 0) n = DefaultInitPtraSize;
153
154 pa = (L_PTRA *)LEPT_CALLOC(1, sizeof(L_PTRA));
155 if ((pa->array = (void **)LEPT_CALLOC(n, sizeof(void *))) == NULL) {
156 ptraDestroy(&pa, 0, 0);
157 return (L_PTRA *)ERROR_PTR("ptr array not made", __func__, NULL);
158 }
159 pa->nalloc = n;
160 pa->imax = -1;
161 pa->nactual = 0;
162 return pa;
163 }
164
165
166 /*!
167 * \brief ptraDestroy()
168 *
169 * \param[in,out] ppa will be set to null before returning
170 * \param[in] freeflag TRUE to free each remaining item in the array
171 * \param[in] warnflag TRUE to warn if any remaining items
172 * are not destroyed
173 * \return void
174 *
175 * <pre>
176 * Notes:
177 * (1) If %freeflag == TRUE, frees each item in the array.
178 * (2) If %freeflag == FALSE and %warnflag == TRUE, and there are
179 * items on the array, this gives a warning and destroys the array.
180 * If these items are not owned elsewhere, this will cause
181 * a memory leak of all the items that were on the array.
182 * So if the items are not owned elsewhere and require their
183 * own destroy function, they must be destroyed before the ptra.
184 * (3) If %warnflag == FALSE, no warnings will be issued. This is
185 * useful if the items are owned elsewhere, such as a
186 * PixMemoryStore().
187 * (4) To destroy the ptra, we destroy the ptr array, then
188 * the ptra, and then null the contents of the input ptr.
189 * </pre>
190 */
191 void
192 ptraDestroy(L_PTRA **ppa,
193 l_int32 freeflag,
194 l_int32 warnflag)
195 {
196 l_int32 i, nactual;
197 void *item;
198 L_PTRA *pa;
199
200 if (ppa == NULL) {
201 L_WARNING("ptr address is NULL\n", __func__);
202 return;
203 }
204 if ((pa = *ppa) == NULL)
205 return;
206
207 ptraGetActualCount(pa, &nactual);
208 if (nactual > 0) {
209 if (freeflag) {
210 for (i = 0; i <= pa->imax; i++) {
211 if ((item = ptraRemove(pa, i, L_NO_COMPACTION)) != NULL)
212 LEPT_FREE(item);
213 }
214 } else if (warnflag) {
215 L_WARNING("potential memory leak of %d items in ptra\n",
216 __func__, nactual);
217 }
218 }
219
220 LEPT_FREE(pa->array);
221 LEPT_FREE(pa);
222 *ppa = NULL;
223 }
224
225
226 /*--------------------------------------------------------------------------*
227 * Add/insert/remove/replace generic ptr object *
228 *--------------------------------------------------------------------------*/
229 /*!
230 * \brief ptraAdd()
231 *
232 * \param[in] pa ptra
233 * \param[in] item generic ptr to a struct
234 * \return 0 if OK, 1 on error
235 *
236 * <pre>
237 * Notes:
238 * (1) This adds the element to the next location beyond imax,
239 * which is the largest occupied ptr in the array. This is
240 * what you expect from a stack, where all ptrs up to and
241 * including imax are occupied, but here the occuption of
242 * items in the array is entirely arbitrary.
243 * </pre>
244 */
245 l_ok
246 ptraAdd(L_PTRA *pa,
247 void *item)
248 {
249 l_int32 imax;
250
251 if (!pa)
252 return ERROR_INT("pa not defined", __func__, 1);
253 if (!item)
254 return ERROR_INT("item not defined", __func__, 1);
255
256 ptraGetMaxIndex(pa, &imax);
257 if (imax >= pa->nalloc - 1 && ptraExtendArray(pa))
258 return ERROR_INT("extension failure", __func__, 1);
259 pa->array[imax + 1] = (void *)item;
260 pa->imax++;
261 pa->nactual++;
262 return 0;
263 }
264
265
266 /*!
267 * \brief ptraExtendArray()
268 *
269 * \param[in] pa
270 * \return 0 if OK, 1 on error
271 */
272 static l_int32
273 ptraExtendArray(L_PTRA *pa)
274 {
275 if (!pa)
276 return ERROR_INT("pa not defined", __func__, 1);
277
278 if ((pa->array = (void **)reallocNew((void **)&pa->array,
279 sizeof(void *) * pa->nalloc,
280 2 * sizeof(void *) * pa->nalloc)) == NULL)
281 return ERROR_INT("new ptr array not returned", __func__, 1);
282
283 pa->nalloc *= 2;
284 return 0;
285 }
286
287
288 /*!
289 * \brief ptraInsert()
290 *
291 * \param[in] pa ptra
292 * \param[in] index location in ptra to insert new value
293 * \param[in] item generic ptr to a struct; can be null
294 * \param[in] shiftflag L_AUTO_DOWNSHIFT, L_MIN_DOWNSHIFT, L_FULL_DOWNSHIFT
295 * \return 0 if OK, 1 on error
296 *
297 * <pre>
298 * Notes:
299 * (1) This checks first to see if the location is valid, and
300 * then if there is presently an item there. If there is not,
301 * it is simply inserted into that location.
302 * (2) If there is an item at the insert location, items must be
303 * moved down to make room for the insert. In the downward
304 * shift there are three options, given by %shiftflag.
305 * ~ If %shiftflag == L_AUTO_DOWNSHIFT, a decision is made
306 * whether, in a cascade of items, to downshift a minimum
307 * amount or for all items above %index. The decision is
308 * based on the expectation of finding holes (null ptrs)
309 * between %index and the bottom of the array.
310 * Assuming the holes are distributed uniformly, if 2 or more
311 * holes are expected, we do a minimum shift.
312 * ~ If %shiftflag == L_MIN_DOWNSHIFT, the downward shifting
313 * cascade of items progresses a minimum amount, until
314 * the first empty slot is reached. This mode requires
315 * some computation before the actual shifting is done.
316 * ~ If %shiftflag == L_FULL_DOWNSHIFT, a shifting cascade is
317 * performed where pa[i] --> pa[i + 1] for all i >= index.
318 * Then, the item is inserted at pa[index].
319 * (3) If you are not using L_AUTO_DOWNSHIFT, the rule of thumb is
320 * to use L_FULL_DOWNSHIFT if the array is compacted (each
321 * element points to an item), and to use L_MIN_DOWNSHIFT
322 * if there are a significant number of null pointers.
323 * There is no penalty to using L_MIN_DOWNSHIFT for a
324 * compacted array, however, because the full shift is required
325 * and we don't do the O(n) computation to look for holes.
326 * (4) This should not be used repeatedly on large arrays,
327 * because the function is generally O(n).
328 * (5) However, it can be used repeatedly if we start with an empty
329 * ptr array and insert only once at each location. For example,
330 * you can support an array of Numa, where at each ptr location
331 * you store either 0 or 1 Numa, and the Numa can be added
332 * randomly to the ptr array.
333 * </pre>
334 */
335 l_ok
336 ptraInsert(L_PTRA *pa,
337 l_int32 index,
338 void *item,
339 l_int32 shiftflag)
340 {
341 l_int32 i, ihole, imax;
342 l_float32 nexpected;
343
344 if (!pa)
345 return ERROR_INT("pa not defined", __func__, 1);
346 if (index < 0 || index > pa->nalloc)
347 return ERROR_INT("index not in [0 ... nalloc]", __func__, 1);
348 if (shiftflag != L_AUTO_DOWNSHIFT && shiftflag != L_MIN_DOWNSHIFT &&
349 shiftflag != L_FULL_DOWNSHIFT)
350 return ERROR_INT("invalid shiftflag", __func__, 1);
351
352 if (item) pa->nactual++;
353 if (index == pa->nalloc) { /* can happen when index == n */
354 if (ptraExtendArray(pa))
355 return ERROR_INT("extension failure", __func__, 1);
356 }
357
358 /* We are inserting into a hole or adding to the end of the array.
359 * No existing items are moved. */
360 ptraGetMaxIndex(pa, &imax);
361 if (pa->array[index] == NULL) {
362 pa->array[index] = item;
363 if (item && index > imax) /* new item put beyond max so far */
364 pa->imax = index;
365 return 0;
366 }
367
368 /* We are inserting at the location of an existing item,
369 * forcing the existing item and those below to shift down.
370 * First, extend the array automatically if the last element
371 * (nalloc - 1) is occupied (imax). This may not be necessary
372 * in every situation, but only an anomalous sequence of insertions
373 * into the array would cause extra ptr allocation. */
374 if (imax >= pa->nalloc - 1 && ptraExtendArray(pa))
375 return ERROR_INT("extension failure", __func__, 1);
376
377 /* If there are no holes, do a full downshift.
378 * Otherwise, if L_AUTO_DOWNSHIFT, use the expected number
379 * of holes between index and n to determine the shift mode */
380 if (imax + 1 == pa->nactual) {
381 shiftflag = L_FULL_DOWNSHIFT;
382 } else if (shiftflag == L_AUTO_DOWNSHIFT) {
383 if (imax < 10) {
384 shiftflag = L_FULL_DOWNSHIFT; /* no big deal */
385 } else {
386 nexpected = (l_float32)(imax - pa->nactual) *
387 (l_float32)((imax - index) / imax);
388 shiftflag = (nexpected > 2.0) ? L_MIN_DOWNSHIFT : L_FULL_DOWNSHIFT;
389 }
390 }
391
392 if (shiftflag == L_MIN_DOWNSHIFT) { /* run down looking for a hole */
393 for (ihole = index + 1; ihole <= imax; ihole++) {
394 if (pa->array[ihole] == NULL)
395 break;
396 }
397 } else { /* L_FULL_DOWNSHIFT */
398 ihole = imax + 1;
399 }
400
401 for (i = ihole; i > index; i--)
402 pa->array[i] = pa->array[i - 1];
403 pa->array[index] = (void *)item;
404 if (ihole == imax + 1) /* the last item was shifted down */
405 pa->imax++;
406
407 return 0;
408 }
409
410
411 /*!
412 * \brief ptraRemove()
413 *
414 * \param[in] pa ptra
415 * \param[in] index element to be removed
416 * \param[in] flag L_NO_COMPACTION, L_COMPACTION
417 * \return item, or NULL on error
418 *
419 * <pre>
420 * Notes:
421 * (1) If flag == L_NO_COMPACTION, this removes the item and
422 * nulls the ptr on the array. If it takes the last item
423 * in the array, pa->n is reduced to the next item.
424 * (2) If flag == L_COMPACTION, this compacts the array for
425 * for all i >= index. It should not be used repeatedly on
426 * large arrays, because compaction is O(n).
427 * (3) The ability to remove without automatic compaction allows
428 * removal with cost O(1).
429 * </pre>
430 */
431 void *
432 ptraRemove(L_PTRA *pa,
433 l_int32 index,
434 l_int32 flag)
435 {
436 l_int32 i, imax, fromend, icurrent;
437 void *item;
438
439 if (!pa)
440 return (void *)ERROR_PTR("pa not defined", __func__, NULL);
441 ptraGetMaxIndex(pa, &imax);
442 if (index < 0 || index > imax)
443 return (void *)ERROR_PTR("index not in [0 ... imax]", __func__, NULL);
444
445 item = pa->array[index];
446 if (item)
447 pa->nactual--;
448 pa->array[index] = NULL;
449
450 /* If we took the last item, need to reduce pa->n */
451 fromend = (index == imax);
452 if (fromend) {
453 for (i = index - 1; i >= 0; i--) {
454 if (pa->array[i])
455 break;
456 }
457 pa->imax = i;
458 }
459
460 /* Compact from index to the end of the array */
461 if (!fromend && flag == L_COMPACTION) {
462 for (icurrent = index, i = index + 1; i <= imax; i++) {
463 if (pa->array[i])
464 pa->array[icurrent++] = pa->array[i];
465 }
466 pa->imax = icurrent - 1;
467 }
468 return item;
469 }
470
471
472 /*!
473 * \brief ptraRemoveLast()
474 *
475 * \param[in] pa ptra
476 * \return item, or NULL on error or if the array is empty
477 */
478 void *
479 ptraRemoveLast(L_PTRA *pa)
480 {
481 l_int32 imax;
482
483 if (!pa)
484 return (void *)ERROR_PTR("pa not defined", __func__, NULL);
485
486 /* Remove the last item in the array. No compaction is required. */
487 ptraGetMaxIndex(pa, &imax);
488 if (imax >= 0)
489 return ptraRemove(pa, imax, L_NO_COMPACTION);
490 else /* empty */
491 return NULL;
492 }
493
494
495 /*!
496 * \brief ptraReplace()
497 *
498 * \param[in] pa ptra
499 * \param[in] index element to be replaced
500 * \param[in] item new generic ptr to a struct; can be null
501 * \param[in] freeflag TRUE to free old item; FALSE to return it
502 * \return item old item, if it exists and is not freed,
503 * or NULL on error
504 */
505 void *
506 ptraReplace(L_PTRA *pa,
507 l_int32 index,
508 void *item,
509 l_int32 freeflag)
510 {
511 l_int32 imax;
512 void *olditem;
513
514 if (!pa)
515 return (void *)ERROR_PTR("pa not defined", __func__, NULL);
516 ptraGetMaxIndex(pa, &imax);
517 if (index < 0 || index > imax)
518 return (void *)ERROR_PTR("index not in [0 ... imax]", __func__, NULL);
519
520 olditem = pa->array[index];
521 pa->array[index] = item;
522 if (!item && olditem)
523 pa->nactual--;
524 else if (item && !olditem)
525 pa->nactual++;
526
527 if (freeflag == FALSE)
528 return olditem;
529
530 if (olditem)
531 LEPT_FREE(olditem);
532 return NULL;
533 }
534
535
536 /*!
537 * \brief ptraSwap()
538 *
539 * \param[in] pa ptra
540 * \param[in] index1
541 * \param[in] index2
542 * \return 0 if OK, 1 on error
543 */
544 l_ok
545 ptraSwap(L_PTRA *pa,
546 l_int32 index1,
547 l_int32 index2)
548 {
549 l_int32 imax;
550 void *item;
551
552 if (!pa)
553 return ERROR_INT("pa not defined", __func__, 1);
554 if (index1 == index2)
555 return 0;
556 ptraGetMaxIndex(pa, &imax);
557 if (index1 < 0 || index1 > imax || index2 < 0 || index2 > imax)
558 return ERROR_INT("invalid index: not in [0 ... imax]", __func__, 1);
559
560 item = ptraRemove(pa, index1, L_NO_COMPACTION);
561 item = ptraReplace(pa, index2, item, FALSE);
562 ptraInsert(pa, index1, item, L_MIN_DOWNSHIFT);
563 return 0;
564 }
565
566
567 /*!
568 * \brief ptraCompactArray()
569 *
570 * \param[in] pa
571 * \return 0 if OK, 1 on error
572 *
573 * <pre>
574 * Notes:
575 * (1) This compacts the items on the array, filling any empty ptrs.
576 * (2) This does not change the size of the array of ptrs.
577 * </pre>
578 */
579 l_ok
580 ptraCompactArray(L_PTRA *pa)
581 {
582 l_int32 i, imax, nactual, index;
583
584 if (!pa)
585 return ERROR_INT("pa not defined", __func__, 1);
586 ptraGetMaxIndex(pa, &imax);
587 ptraGetActualCount(pa, &nactual);
588 if (imax + 1 == nactual) return 0;
589
590 /* Compact the array */
591 for (i = 0, index = 0; i <= imax; i++) {
592 if (pa->array[i])
593 pa->array[index++] = pa->array[i];
594 }
595 pa->imax = index - 1;
596 if (nactual != index)
597 L_ERROR("index = %d; != nactual\n", __func__, index);
598
599 return 0;
600 }
601
602
603 /*----------------------------------------------------------------------*
604 * Other array operations *
605 *----------------------------------------------------------------------*/
606 /*!
607 * \brief ptraReverse()
608 *
609 * \param[in] pa ptra
610 * \return 0 if OK, 1 on error
611 */
612 l_ok
613 ptraReverse(L_PTRA *pa)
614 {
615 l_int32 i, imax;
616
617 if (!pa)
618 return ERROR_INT("pa not defined", __func__, 1);
619 ptraGetMaxIndex(pa, &imax);
620
621 for (i = 0; i < (imax + 1) / 2; i++)
622 ptraSwap(pa, i, imax - i);
623 return 0;
624 }
625
626
627 /*!
628 * \brief ptraJoin()
629 *
630 * \param[in] pa1 add to this one
631 * \param[in] pa2 appended to pa1, and emptied of items; can be null
632 * \return 0 if OK, 1 on error
633 */
634 l_ok
635 ptraJoin(L_PTRA *pa1,
636 L_PTRA *pa2)
637 {
638 l_int32 i, imax;
639 void *item;
640
641 if (!pa1)
642 return ERROR_INT("pa1 not defined", __func__, 1);
643 if (!pa2)
644 return 0;
645
646 ptraGetMaxIndex(pa2, &imax);
647 for (i = 0; i <= imax; i++) {
648 item = ptraRemove(pa2, i, L_NO_COMPACTION);
649 ptraAdd(pa1, item);
650 }
651
652 return 0;
653 }
654
655
656
657 /*----------------------------------------------------------------------*
658 * Simple ptra accessors *
659 *----------------------------------------------------------------------*/
660 /*!
661 * \brief ptraGetMaxIndex()
662 *
663 * \param[in] pa ptra
664 * \param[out] pmaxindex index of last item in the array;
665 * \return 0 if OK; 1 on error
666 *
667 * <pre>
668 * Notes:
669 * (1) The largest index to an item in the array is %maxindex.
670 * %maxindex is one less than the number of items that would be
671 * in the array if there were no null pointers between 0
672 * and %maxindex - 1. However, because the internal ptr array
673 * need not be compacted, there may be NULL pointers at
674 * indices below %maxindex; for example, if items have
675 * been removed.
676 * (2) When an item is added to the end of the array, it goes
677 * into pa->array[maxindex + 1], and maxindex is then
678 * incremented by 1.
679 * (3) If there are no items in the array, this returns %maxindex = -1.
680 * </pre>
681 */
682 l_ok
683 ptraGetMaxIndex(L_PTRA *pa,
684 l_int32 *pmaxindex)
685 {
686 if (!pa)
687 return ERROR_INT("pa not defined", __func__, 1);
688 if (!pmaxindex)
689 return ERROR_INT("&maxindex not defined", __func__, 1);
690 *pmaxindex = pa->imax;
691 return 0;
692 }
693
694
695 /*!
696 * \brief ptraGetActualCount()
697 *
698 * \param[in] pa ptra
699 * \param[out] pcount actual number of items on the ptr array
700 * \return 0 if OK; 1 on error
701 *
702 * <pre>
703 * Notes:
704 * (1) The actual number of items on the ptr array, pa->nactual,
705 * will be smaller than pa->n if the array is not compacted.
706 * </pre>
707 */
708 l_ok
709 ptraGetActualCount(L_PTRA *pa,
710 l_int32 *pcount)
711 {
712 if (!pa)
713 return ERROR_INT("pa not defined", __func__, 1);
714 if (!pcount)
715 return ERROR_INT("&count not defined", __func__, 1);
716 *pcount = pa->nactual;
717
718 return 0;
719 }
720
721
722 /*!
723 * \brief ptraGetPtrToItem()
724 *
725 * \param[in] pa ptra
726 * \param[in] index of element to be retrieved
727 * \return a ptr to the element, or NULL on error
728 *
729 * <pre>
730 * Notes:
731 * (1) This returns a ptr to the item. You must cast it to
732 * the type of item. Do not destroy it; the item belongs
733 * to the Ptra.
734 * (2) This can access all possible items on the ptr array.
735 * If an item doesn't exist, it returns null.
736 * </pre>
737 */
738 void *
739 ptraGetPtrToItem(L_PTRA *pa,
740 l_int32 index)
741 {
742 if (!pa)
743 return (void *)ERROR_PTR("pa not defined", __func__, NULL);
744 if (index < 0 || index >= pa->nalloc)
745 return (void *)ERROR_PTR("index not in [0 ... nalloc-1]",
746 __func__, NULL);
747
748 return pa->array[index];
749 }
750
751
752 /*--------------------------------------------------------------------------*
753 * Ptraa creation and destruction *
754 *--------------------------------------------------------------------------*/
755 /*!
756 * \brief ptraaCreate()
757 *
758 * \param[in] n size of ptr array to be alloc'd
759 * \return paa, or NULL on error
760 *
761 * <pre>
762 * Notes:
763 * (1) The ptraa is generated with a fixed size, that can not change.
764 * The ptra can be generated and inserted randomly into this array.
765 * </pre>
766 */
767 L_PTRAA *
768 ptraaCreate(l_int32 n)
769 {
770 L_PTRAA *paa;
771
772 if (n <= 0)
773 return (L_PTRAA *)ERROR_PTR("n must be > 0", __func__, NULL);
774
775 paa = (L_PTRAA *)LEPT_CALLOC(1, sizeof(L_PTRAA));
776 if ((paa->ptra = (L_PTRA **)LEPT_CALLOC(n, sizeof(L_PTRA *))) == NULL) {
777 ptraaDestroy(&paa, 0, 0);
778 return (L_PTRAA *)ERROR_PTR("ptr array not made", __func__, NULL);
779 }
780 paa->nalloc = n;
781 return paa;
782 }
783
784
785 /*!
786 * \brief ptraaDestroy()
787 *
788 * \param[in,out] ppaa will be set to null before returning
789 * \param[in] freeflag TRUE to free each remaining item in each ptra
790 * \param[in] warnflag TRUE to warn if any remaining items
791 * are not destroyed
792 * \return void
793 *
794 * <pre>
795 * Notes:
796 * (1) See ptraDestroy() for use of %freeflag and %warnflag.
797 * (2) To destroy the ptraa, we destroy each ptra, then the ptr array,
798 * then the ptraa, and then null the contents of the input ptr.
799 * </pre>
800 */
801 void
802 ptraaDestroy(L_PTRAA **ppaa,
803 l_int32 freeflag,
804 l_int32 warnflag)
805 {
806 l_int32 i, n;
807 L_PTRA *pa;
808 L_PTRAA *paa;
809
810 if (ppaa == NULL) {
811 L_WARNING("ptr address is NULL\n", __func__);
812 return;
813 }
814 if ((paa = *ppaa) == NULL)
815 return;
816
817 ptraaGetSize(paa, &n);
818 for (i = 0; i < n; i++) {
819 pa = ptraaGetPtra(paa, i, L_REMOVE);
820 ptraDestroy(&pa, freeflag, warnflag);
821 }
822
823 LEPT_FREE(paa->ptra);
824 LEPT_FREE(paa);
825 *ppaa = NULL;
826 }
827
828
829 /*--------------------------------------------------------------------------*
830 * Ptraa accessors *
831 *--------------------------------------------------------------------------*/
832 /*!
833 * \brief ptraaGetSize()
834 *
835 * \param[in] paa
836 * \param[out] psize size of ptr array
837 * \return 0 if OK; 1 on error
838 */
839 l_ok
840 ptraaGetSize(L_PTRAA *paa,
841 l_int32 *psize)
842 {
843 if (!paa)
844 return ERROR_INT("paa not defined", __func__, 1);
845 if (!psize)
846 return ERROR_INT("&size not defined", __func__, 1);
847 *psize = paa->nalloc;
848
849 return 0;
850 }
851
852
853 /*!
854 * \brief ptraaInsertPtra()
855 *
856 * \param[in] paa ptraa
857 * \param[in] index location in array for insertion
858 * \param[in] pa to be inserted
859 * \return 0 if OK; 1 on error
860 *
861 * <pre>
862 * Notes:
863 * (1) Caller should check return value. On success, the Ptra
864 * is inserted in the Ptraa and is owned by it. However,
865 * on error, the Ptra remains owned by the caller.
866 * </pre>
867 */
868 l_ok
869 ptraaInsertPtra(L_PTRAA *paa,
870 l_int32 index,
871 L_PTRA *pa)
872 {
873 l_int32 n;
874
875 if (!paa)
876 return ERROR_INT("paa not defined", __func__, 1);
877 if (!pa)
878 return ERROR_INT("pa not defined", __func__, 1);
879 ptraaGetSize(paa, &n);
880 if (index < 0 || index >= n)
881 return ERROR_INT("invalid index", __func__, 1);
882 if (paa->ptra[index] != NULL)
883 return ERROR_INT("ptra already stored at index", __func__, 1);
884
885 paa->ptra[index] = pa;
886 return 0;
887 }
888
889
890 /*!
891 * \brief ptraaGetPtra()
892 *
893 * \param[in] paa ptraa
894 * \param[in] index location in array
895 * \param[in] accessflag L_HANDLE_ONLY, L_REMOVE
896 * \return ptra at index location, or NULL on error or if there
897 * is no ptra there.
898 *
899 * <pre>
900 * Notes:
901 * (1) This returns the ptra ptr. If %accessflag == L_HANDLE_ONLY,
902 * the ptra is left on the ptraa. If %accessflag == L_REMOVE,
903 * the ptr in the ptraa is set to NULL, and the caller
904 * is responsible for disposing of the ptra (either putting it
905 * back on the ptraa, or destroying it).
906 * (2) This returns NULL if there is no Ptra at the index location.
907 * </pre>
908 */
909 L_PTRA *
910 ptraaGetPtra(L_PTRAA *paa,
911 l_int32 index,
912 l_int32 accessflag)
913 {
914 l_int32 n;
915 L_PTRA *pa;
916
917 if (!paa)
918 return (L_PTRA *)ERROR_PTR("paa not defined", __func__, NULL);
919 ptraaGetSize(paa, &n);
920 if (index < 0 || index >= n)
921 return (L_PTRA *)ERROR_PTR("invalid index", __func__, NULL);
922 if (accessflag != L_HANDLE_ONLY && accessflag != L_REMOVE)
923 return (L_PTRA *)ERROR_PTR("invalid accessflag", __func__, NULL);
924
925 pa = paa->ptra[index];
926 if (accessflag == L_REMOVE)
927 paa->ptra[index] = NULL;
928 return pa;
929 }
930
931
932 /*--------------------------------------------------------------------------*
933 * Ptraa conversion *
934 *--------------------------------------------------------------------------*/
935 /*!
936 * \brief ptraaFlattenToPtra()
937 *
938 * \param[in] paa ptraa
939 * \return ptra, or NULL on error
940 *
941 * <pre>
942 * Notes:
943 * (1) This 'flattens' the ptraa to a ptra, taking the items in
944 * each ptra, in order, starting with the first ptra, etc.
945 * (2) As a side-effect, the ptra are all removed from the ptraa
946 * and destroyed, leaving an empty ptraa.
947 * </pre>
948 */
949 L_PTRA *
950 ptraaFlattenToPtra(L_PTRAA *paa)
951 {
952 l_int32 i, n;
953 L_PTRA *pat, *pad;
954
955 if (!paa)
956 return (L_PTRA *)ERROR_PTR("paa not defined", __func__, NULL);
957
958 pad = ptraCreate(0);
959 ptraaGetSize(paa, &n);
960 for (i = 0; i < n; i++) {
961 pat = ptraaGetPtra(paa, i, L_REMOVE);
962 if (!pat) continue;
963 ptraJoin(pad, pat);
964 ptraDestroy(&pat, FALSE, FALSE); /* they're all empty */
965 }
966
967 return pad;
968 }