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 #include "allheaders.h"
122
123 static const l_int32 INITIAL_PTR_ARRAYSIZE = 20; /* n'importe quoi */
124
125 /* Static function */
126 static l_int32 ptraExtendArray(L_PTRA *pa);
127
128
129 /*--------------------------------------------------------------------------*
130 * Ptra creation and destruction *
131 *--------------------------------------------------------------------------*/
132 /*!
133 * \brief ptraCreate()
134 *
135 * \param[in] n size of ptr array to be alloc'd 0 for default
136 * \return pa, or NULL on error
137 */
138 L_PTRA *
ptraCreate(l_int32 n)139 ptraCreate(l_int32 n)
140 {
141 L_PTRA *pa;
142
143 PROCNAME("ptraCreate");
144
145 if (n <= 0)
146 n = INITIAL_PTR_ARRAYSIZE;
147
148 pa = (L_PTRA *)LEPT_CALLOC(1, sizeof(L_PTRA));
149 if ((pa->array = (void **)LEPT_CALLOC(n, sizeof(void *))) == NULL) {
150 ptraDestroy(&pa, 0, 0);
151 return (L_PTRA *)ERROR_PTR("ptr array not made", procName, NULL);
152 }
153 pa->nalloc = n;
154 pa->imax = -1;
155 pa->nactual = 0;
156 return pa;
157 }
158
159
160 /*!
161 * \brief ptraDestroy()
162 *
163 * \param[in,out] ppa ptra to be nulled
164 * \param[in] freeflag TRUE to free each remaining item in the array
165 * \param[in] warnflag TRUE to warn if any remaining items are not destroyed
166 * \return void
167 *
168 * <pre>
169 * Notes:
170 * (1) If %freeflag == TRUE, frees each item in the array.
171 * (2) If %freeflag == FALSE and %warnflag == TRUE, and there are
172 * items on the array, this gives a warning and destroys the array.
173 * If these items are not owned elsewhere, this will cause
174 * a memory leak of all the items that were on the array.
175 * So if the items are not owned elsewhere and require their
176 * own destroy function, they must be destroyed before the ptra.
177 * (3) If %warnflag == FALSE, no warnings will be issued. This is
178 * useful if the items are owned elsewhere, such as a
179 * PixMemoryStore().
180 * (4) To destroy the ptra, we destroy the ptr array, then
181 * the ptra, and then null the contents of the input ptr.
182 * </pre>
183 */
184 void
ptraDestroy(L_PTRA ** ppa,l_int32 freeflag,l_int32 warnflag)185 ptraDestroy(L_PTRA **ppa,
186 l_int32 freeflag,
187 l_int32 warnflag)
188 {
189 l_int32 i, nactual;
190 void *item;
191 L_PTRA *pa;
192
193 PROCNAME("ptraDestroy");
194
195 if (ppa == NULL) {
196 L_WARNING("ptr address is NULL\n", procName);
197 return;
198 }
199 if ((pa = *ppa) == NULL)
200 return;
201
202 ptraGetActualCount(pa, &nactual);
203 if (nactual > 0) {
204 if (freeflag) {
205 for (i = 0; i <= pa->imax; i++) {
206 if ((item = ptraRemove(pa, i, L_NO_COMPACTION)) != NULL)
207 LEPT_FREE(item);
208 }
209 } else if (warnflag) {
210 L_WARNING("potential memory leak of %d items in ptra\n",
211 procName, nactual);
212 }
213 }
214
215 LEPT_FREE(pa->array);
216 LEPT_FREE(pa);
217 *ppa = NULL;
218 return;
219 }
220
221
222 /*--------------------------------------------------------------------------*
223 * Add/insert/remove/replace generic ptr object *
224 *--------------------------------------------------------------------------*/
225 /*!
226 * \brief ptraAdd()
227 *
228 * \param[in] pa ptra
229 * \param[in] item generic ptr to a struct
230 * \return 0 if OK, 1 on error
231 *
232 * <pre>
233 * Notes:
234 * (1) This adds the element to the next location beyond imax,
235 * which is the largest occupied ptr in the array. This is
236 * what you expect from a stack, where all ptrs up to and
237 * including imax are occupied, but here the occuption of
238 * items in the array is entirely arbitrary.
239 * </pre>
240 */
241 l_int32
ptraAdd(L_PTRA * pa,void * item)242 ptraAdd(L_PTRA *pa,
243 void *item)
244 {
245 l_int32 imax;
246
247 PROCNAME("ptraAdd");
248
249 if (!pa)
250 return ERROR_INT("pa not defined", procName, 1);
251 if (!item)
252 return ERROR_INT("item not defined", procName, 1);
253
254 ptraGetMaxIndex(pa, &imax);
255 if (imax >= pa->nalloc - 1 && ptraExtendArray(pa))
256 return ERROR_INT("extension failure", procName, 1);
257 pa->array[imax + 1] = (void *)item;
258 pa->imax++;
259 pa->nactual++;
260 return 0;
261 }
262
263
264 /*!
265 * \brief ptraExtendArray()
266 *
267 * \param[in] pa
268 * \return 0 if OK, 1 on error
269 */
270 static l_int32
ptraExtendArray(L_PTRA * pa)271 ptraExtendArray(L_PTRA *pa)
272 {
273 PROCNAME("ptraExtendArray");
274
275 if (!pa)
276 return ERROR_INT("pa not defined", procName, 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", procName, 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_int32
ptraInsert(L_PTRA * pa,l_int32 index,void * item,l_int32 shiftflag)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 PROCNAME("ptraInsert");
345
346 if (!pa)
347 return ERROR_INT("pa not defined", procName, 1);
348 if (index < 0 || index > pa->nalloc)
349 return ERROR_INT("index not in [0 ... nalloc]", procName, 1);
350 if (shiftflag != L_AUTO_DOWNSHIFT && shiftflag != L_MIN_DOWNSHIFT &&
351 shiftflag != L_FULL_DOWNSHIFT)
352 return ERROR_INT("invalid shiftflag", procName, 1);
353
354 if (item) pa->nactual++;
355 if (index == pa->nalloc) { /* can happen when index == n */
356 if (ptraExtendArray(pa))
357 return ERROR_INT("extension failure", procName, 1);
358 }
359
360 /* We are inserting into a hole or adding to the end of the array.
361 * No existing items are moved. */
362 ptraGetMaxIndex(pa, &imax);
363 if (pa->array[index] == NULL) {
364 pa->array[index] = item;
365 if (item && index > imax) /* new item put beyond max so far */
366 pa->imax = index;
367 return 0;
368 }
369
370 /* We are inserting at the location of an existing item,
371 * forcing the existing item and those below to shift down.
372 * First, extend the array automatically if the last element
373 * (nalloc - 1) is occupied (imax). This may not be necessary
374 * in every situation, but only an anomalous sequence of insertions
375 * into the array would cause extra ptr allocation. */
376 if (imax >= pa->nalloc - 1 && ptraExtendArray(pa))
377 return ERROR_INT("extension failure", procName, 1);
378
379 /* If there are no holes, do a full downshift.
380 * Otherwise, if L_AUTO_DOWNSHIFT, use the expected number
381 * of holes between index and n to determine the shift mode */
382 if (imax + 1 == pa->nactual) {
383 shiftflag = L_FULL_DOWNSHIFT;
384 } else if (shiftflag == L_AUTO_DOWNSHIFT) {
385 if (imax < 10) {
386 shiftflag = L_FULL_DOWNSHIFT; /* no big deal */
387 } else {
388 nexpected = (l_float32)(imax - pa->nactual) *
389 (l_float32)((imax - index) / imax);
390 shiftflag = (nexpected > 2.0) ? L_MIN_DOWNSHIFT : L_FULL_DOWNSHIFT;
391 }
392 }
393
394 if (shiftflag == L_MIN_DOWNSHIFT) { /* run down looking for a hole */
395 for (ihole = index + 1; ihole <= imax; ihole++) {
396 if (pa->array[ihole] == NULL)
397 break;
398 }
399 } else { /* L_FULL_DOWNSHIFT */
400 ihole = imax + 1;
401 }
402
403 for (i = ihole; i > index; i--)
404 pa->array[i] = pa->array[i - 1];
405 pa->array[index] = (void *)item;
406 if (ihole == imax + 1) /* the last item was shifted down */
407 pa->imax++;
408
409 return 0;
410 }
411
412
413 /*!
414 * \brief ptraRemove()
415 *
416 * \param[in] pa ptra
417 * \param[in] index element to be removed
418 * \param[in] flag L_NO_COMPACTION, L_COMPACTION
419 * \return item, or NULL on error
420 *
421 * <pre>
422 * Notes:
423 * (1) If flag == L_NO_COMPACTION, this removes the item and
424 * nulls the ptr on the array. If it takes the last item
425 * in the array, pa->n is reduced to the next item.
426 * (2) If flag == L_COMPACTION, this compacts the array for
427 * for all i >= index. It should not be used repeatedly on
428 * large arrays, because compaction is O(n).
429 * (3) The ability to remove without automatic compaction allows
430 * removal with cost O(1).
431 * </pre>
432 */
433 void *
ptraRemove(L_PTRA * pa,l_int32 index,l_int32 flag)434 ptraRemove(L_PTRA *pa,
435 l_int32 index,
436 l_int32 flag)
437 {
438 l_int32 i, imax, fromend, icurrent;
439 void *item;
440
441 PROCNAME("ptraRemove");
442
443 if (!pa)
444 return (void *)ERROR_PTR("pa not defined", procName, NULL);
445 ptraGetMaxIndex(pa, &imax);
446 if (index < 0 || index > imax)
447 return (void *)ERROR_PTR("index not in [0 ... imax]", procName, NULL);
448
449 item = pa->array[index];
450 if (item)
451 pa->nactual--;
452 pa->array[index] = NULL;
453
454 /* If we took the last item, need to reduce pa->n */
455 fromend = (index == imax);
456 if (fromend) {
457 for (i = index - 1; i >= 0; i--) {
458 if (pa->array[i])
459 break;
460 }
461 pa->imax = i;
462 }
463
464 /* Compact from index to the end of the array */
465 if (!fromend && flag == L_COMPACTION) {
466 for (icurrent = index, i = index + 1; i <= imax; i++) {
467 if (pa->array[i])
468 pa->array[icurrent++] = pa->array[i];
469 }
470 pa->imax = icurrent - 1;
471 }
472 return item;
473 }
474
475
476 /*!
477 * \brief ptraRemoveLast()
478 *
479 * \param[in] pa ptra
480 * \return item, or NULL on error or if the array is empty
481 */
482 void *
ptraRemoveLast(L_PTRA * pa)483 ptraRemoveLast(L_PTRA *pa)
484 {
485 l_int32 imax;
486
487 PROCNAME("ptraRemoveLast");
488
489 if (!pa)
490 return (void *)ERROR_PTR("pa not defined", procName, NULL);
491
492 /* Remove the last item in the array. No compaction is required. */
493 ptraGetMaxIndex(pa, &imax);
494 if (imax >= 0)
495 return ptraRemove(pa, imax, L_NO_COMPACTION);
496 else /* empty */
497 return NULL;
498 }
499
500
501 /*!
502 * \brief ptraReplace()
503 *
504 * \param[in] pa ptra
505 * \param[in] index element to be replaced
506 * \param[in] item new generic ptr to a struct; can be null
507 * \param[in] freeflag TRUE to free old item; FALSE to return it
508 * \return item old item, if it exists and is not freed,
509 * or NULL on error
510 */
511 void *
ptraReplace(L_PTRA * pa,l_int32 index,void * item,l_int32 freeflag)512 ptraReplace(L_PTRA *pa,
513 l_int32 index,
514 void *item,
515 l_int32 freeflag)
516 {
517 l_int32 imax;
518 void *olditem;
519
520 PROCNAME("ptraReplace");
521
522 if (!pa)
523 return (void *)ERROR_PTR("pa not defined", procName, NULL);
524 ptraGetMaxIndex(pa, &imax);
525 if (index < 0 || index > imax)
526 return (void *)ERROR_PTR("index not in [0 ... imax]", procName, NULL);
527
528 olditem = pa->array[index];
529 pa->array[index] = item;
530 if (!item && olditem)
531 pa->nactual--;
532 else if (item && !olditem)
533 pa->nactual++;
534
535 if (freeflag == FALSE)
536 return olditem;
537
538 if (olditem)
539 LEPT_FREE(olditem);
540 return NULL;
541 }
542
543
544 /*!
545 * \brief ptraSwap()
546 *
547 * \param[in] pa ptra
548 * \param[in] index1
549 * \param[in] index2
550 * \return 0 if OK, 1 on error
551 */
552 l_int32
ptraSwap(L_PTRA * pa,l_int32 index1,l_int32 index2)553 ptraSwap(L_PTRA *pa,
554 l_int32 index1,
555 l_int32 index2)
556 {
557 l_int32 imax;
558 void *item;
559
560 PROCNAME("ptraSwap");
561
562 if (!pa)
563 return ERROR_INT("pa not defined", procName, 1);
564 if (index1 == index2)
565 return 0;
566 ptraGetMaxIndex(pa, &imax);
567 if (index1 < 0 || index1 > imax || index2 < 0 || index2 > imax)
568 return ERROR_INT("invalid index: not in [0 ... imax]", procName, 1);
569
570 item = ptraRemove(pa, index1, L_NO_COMPACTION);
571 item = ptraReplace(pa, index2, item, FALSE);
572 ptraInsert(pa, index1, item, L_MIN_DOWNSHIFT);
573 return 0;
574 }
575
576
577 /*!
578 * \brief ptraCompactArray()
579 *
580 * \param[in] pa
581 * \return 0 if OK, 1 on error
582 *
583 * <pre>
584 * Notes:
585 * (1) This compacts the items on the array, filling any empty ptrs.
586 * (2) This does not change the size of the array of ptrs.
587 * </pre>
588 */
589 l_int32
ptraCompactArray(L_PTRA * pa)590 ptraCompactArray(L_PTRA *pa)
591 {
592 l_int32 i, imax, nactual, index;
593
594 PROCNAME("ptraCompactArray");
595
596 if (!pa)
597 return ERROR_INT("pa not defined", procName, 1);
598 ptraGetMaxIndex(pa, &imax);
599 ptraGetActualCount(pa, &nactual);
600 if (imax + 1 == nactual) return 0;
601
602 /* Compact the array */
603 for (i = 0, index = 0; i <= imax; i++) {
604 if (pa->array[i])
605 pa->array[index++] = pa->array[i];
606 }
607 pa->imax = index - 1;
608 if (nactual != index)
609 L_ERROR("index = %d; != nactual\n", procName, index);
610
611 return 0;
612 }
613
614
615 /*----------------------------------------------------------------------*
616 * Other array operations *
617 *----------------------------------------------------------------------*/
618 /*!
619 * \brief ptraReverse()
620 *
621 * \param[in] pa ptra
622 * \return 0 if OK, 1 on error
623 */
624 l_int32
ptraReverse(L_PTRA * pa)625 ptraReverse(L_PTRA *pa)
626 {
627 l_int32 i, imax;
628
629 PROCNAME("ptraReverse");
630
631 if (!pa)
632 return ERROR_INT("pa not defined", procName, 1);
633 ptraGetMaxIndex(pa, &imax);
634
635 for (i = 0; i < (imax + 1) / 2; i++)
636 ptraSwap(pa, i, imax - i);
637 return 0;
638 }
639
640
641 /*!
642 * \brief ptraJoin()
643 *
644 * \param[in] pa1 add to this one
645 * \param[in] pa2 appended to pa1, and emptied of items; can be null
646 * \return 0 if OK, 1 on error
647 */
648 l_int32
ptraJoin(L_PTRA * pa1,L_PTRA * pa2)649 ptraJoin(L_PTRA *pa1,
650 L_PTRA *pa2)
651 {
652 l_int32 i, imax;
653 void *item;
654
655 PROCNAME("ptraJoin");
656
657 if (!pa1)
658 return ERROR_INT("pa1 not defined", procName, 1);
659 if (!pa2)
660 return 0;
661
662 ptraGetMaxIndex(pa2, &imax);
663 for (i = 0; i <= imax; i++) {
664 item = ptraRemove(pa2, i, L_NO_COMPACTION);
665 ptraAdd(pa1, item);
666 }
667
668 return 0;
669 }
670
671
672
673 /*----------------------------------------------------------------------*
674 * Simple ptra accessors *
675 *----------------------------------------------------------------------*/
676 /*!
677 * \brief ptraGetMaxIndex()
678 *
679 * \param[in] pa ptra
680 * \param[out] pmaxindex index of last item in the array;
681 * \return 0 if OK; 1 on error
682 *
683 * <pre>
684 * Notes:
685 * (1) The largest index to an item in the array is %maxindex.
686 * %maxindex is one less than the number of items that would be
687 * in the array if there were no null pointers between 0
688 * and %maxindex - 1. However, because the internal ptr array
689 * need not be compacted, there may be NULL pointers at
690 * indices below %maxindex; for example, if items have
691 * been removed.
692 * (2) When an item is added to the end of the array, it goes
693 * into pa->array[maxindex + 1], and maxindex is then
694 * incremented by 1.
695 * (3) If there are no items in the array, this returns %maxindex = -1.
696 * </pre>
697 */
698 l_int32
ptraGetMaxIndex(L_PTRA * pa,l_int32 * pmaxindex)699 ptraGetMaxIndex(L_PTRA *pa,
700 l_int32 *pmaxindex)
701 {
702 PROCNAME("ptraGetMaxIndex");
703
704 if (!pa)
705 return ERROR_INT("pa not defined", procName, 1);
706 if (!pmaxindex)
707 return ERROR_INT("&maxindex not defined", procName, 1);
708 *pmaxindex = pa->imax;
709 return 0;
710 }
711
712
713 /*!
714 * \brief ptraGetActualCount()
715 *
716 * \param[in] pa ptra
717 * \param[out] pcount actual number of items on the ptr array
718 * \return 0 if OK; 1 on error
719 *
720 * <pre>
721 * Notes:
722 * (1) The actual number of items on the ptr array, pa->nactual,
723 * will be smaller than pa->n if the array is not compacted.
724 * </pre>
725 */
726 l_int32
ptraGetActualCount(L_PTRA * pa,l_int32 * pcount)727 ptraGetActualCount(L_PTRA *pa,
728 l_int32 *pcount)
729 {
730 PROCNAME("ptraGetActualCount");
731
732 if (!pa)
733 return ERROR_INT("pa not defined", procName, 1);
734 if (!pcount)
735 return ERROR_INT("&count not defined", procName, 1);
736 *pcount = pa->nactual;
737
738 return 0;
739 }
740
741
742 /*!
743 * \brief ptraGetPtrToItem()
744 *
745 * \param[in] pa ptra
746 * \param[in] index of element to be retrieved
747 * \return a ptr to the element, or NULL on error
748 *
749 * <pre>
750 * Notes:
751 * (1) This returns a ptr to the item. You must cast it to
752 * the type of item. Do not destroy it; the item belongs
753 * to the Ptra.
754 * (2) This can access all possible items on the ptr array.
755 * If an item doesn't exist, it returns null.
756 * </pre>
757 */
758 void *
ptraGetPtrToItem(L_PTRA * pa,l_int32 index)759 ptraGetPtrToItem(L_PTRA *pa,
760 l_int32 index)
761 {
762 PROCNAME("ptraGetPtrToItem");
763
764 if (!pa)
765 return (void *)ERROR_PTR("pa not defined", procName, NULL);
766 if (index < 0 || index >= pa->nalloc)
767 return (void *)ERROR_PTR("index not in [0 ... nalloc-1]",
768 procName, NULL);
769
770 return pa->array[index];
771 }
772
773
774 /*--------------------------------------------------------------------------*
775 * Ptraa creation and destruction *
776 *--------------------------------------------------------------------------*/
777 /*!
778 * \brief ptraaCreate()
779 *
780 * \param[in] n size of ptr array to be alloc'd
781 * \return paa, or NULL on error
782 *
783 * <pre>
784 * Notes:
785 * (1) The ptraa is generated with a fixed size, that can not change.
786 * The ptra can be generated and inserted randomly into this array.
787 * </pre>
788 */
789 L_PTRAA *
ptraaCreate(l_int32 n)790 ptraaCreate(l_int32 n)
791 {
792 L_PTRAA *paa;
793
794 PROCNAME("ptraaCreate");
795
796 if (n <= 0)
797 return (L_PTRAA *)ERROR_PTR("n must be > 0", procName, NULL);
798
799 if ((paa = (L_PTRAA *)LEPT_CALLOC(1, sizeof(L_PTRAA))) == NULL)
800 return (L_PTRAA *)ERROR_PTR("paa not made", procName, NULL);
801 if ((paa->ptra = (L_PTRA **)LEPT_CALLOC(n, sizeof(L_PTRA *))) == NULL) {
802 ptraaDestroy(&paa, 0, 0);
803 return (L_PTRAA *)ERROR_PTR("ptr array not made", procName, NULL);
804 }
805 paa->nalloc = n;
806 return paa;
807 }
808
809
810 /*!
811 * \brief ptraaDestroy()
812 *
813 * \param[in,out] ppaa to be nulled
814 * \param[in] freeflag TRUE to free each remaining item in each ptra
815 * \param[in] warnflag TRUE to warn if any remaining items are not destroyed
816 * \return void
817 *
818 * <pre>
819 * Notes:
820 * (1) See ptraDestroy() for use of %freeflag and %warnflag.
821 * (2) To destroy the ptraa, we destroy each ptra, then the ptr array,
822 * then the ptraa, and then null the contents of the input ptr.
823 * </pre>
824 */
825 void
ptraaDestroy(L_PTRAA ** ppaa,l_int32 freeflag,l_int32 warnflag)826 ptraaDestroy(L_PTRAA **ppaa,
827 l_int32 freeflag,
828 l_int32 warnflag)
829 {
830 l_int32 i, n;
831 L_PTRA *pa;
832 L_PTRAA *paa;
833
834 PROCNAME("ptraaDestroy");
835
836 if (ppaa == NULL) {
837 L_WARNING("ptr address is NULL\n", procName);
838 return;
839 }
840 if ((paa = *ppaa) == NULL)
841 return;
842
843 ptraaGetSize(paa, &n);
844 for (i = 0; i < n; i++) {
845 pa = ptraaGetPtra(paa, i, L_REMOVE);
846 ptraDestroy(&pa, freeflag, warnflag);
847 }
848
849 LEPT_FREE(paa->ptra);
850 LEPT_FREE(paa);
851 *ppaa = NULL;
852 return;
853 }
854
855
856 /*--------------------------------------------------------------------------*
857 * Ptraa accessors *
858 *--------------------------------------------------------------------------*/
859 /*!
860 * \brief ptraaGetSize()
861 *
862 * \param[in] paa
863 * \param[out] psize size of ptr array
864 * \return 0 if OK; 1 on error
865 */
866 l_int32
ptraaGetSize(L_PTRAA * paa,l_int32 * psize)867 ptraaGetSize(L_PTRAA *paa,
868 l_int32 *psize)
869 {
870 PROCNAME("ptraaGetSize");
871
872 if (!paa)
873 return ERROR_INT("paa not defined", procName, 1);
874 if (!psize)
875 return ERROR_INT("&size not defined", procName, 1);
876 *psize = paa->nalloc;
877
878 return 0;
879 }
880
881
882 /*!
883 * \brief ptraaInsertPtra()
884 *
885 * \param[in] paa ptraa
886 * \param[in] index location in array for insertion
887 * \param[in] pa to be inserted
888 * \return 0 if OK; 1 on error
889 *
890 * <pre>
891 * Notes:
892 * (1) Caller should check return value. On success, the Ptra
893 * is inserted in the Ptraa and is owned by it. However,
894 * on error, the Ptra remains owned by the caller.
895 * </pre>
896 */
897 l_int32
ptraaInsertPtra(L_PTRAA * paa,l_int32 index,L_PTRA * pa)898 ptraaInsertPtra(L_PTRAA *paa,
899 l_int32 index,
900 L_PTRA *pa)
901 {
902 l_int32 n;
903
904 PROCNAME("ptraaInsertPtra");
905
906 if (!paa)
907 return ERROR_INT("paa not defined", procName, 1);
908 if (!pa)
909 return ERROR_INT("pa not defined", procName, 1);
910 ptraaGetSize(paa, &n);
911 if (index < 0 || index >= n)
912 return ERROR_INT("invalid index", procName, 1);
913 if (paa->ptra[index] != NULL)
914 return ERROR_INT("ptra alread stored at index", procName, 1);
915
916 paa->ptra[index] = pa;
917 return 0;
918 }
919
920
921 /*!
922 * \brief ptraaGetPtra()
923 *
924 * \param[in] paa ptraa
925 * \param[in] index location in array
926 * \param[in] accessflag L_HANDLE_ONLY, L_REMOVE
927 * \return ptra at index location, or NULL on error or if there
928 * is no ptra there.
929 *
930 * <pre>
931 * Notes:
932 * (1) This returns the ptra ptr. If %accessflag == L_HANDLE_ONLY,
933 * the ptra is left on the ptraa. If %accessflag == L_REMOVE,
934 * the ptr in the ptraa is set to NULL, and the caller
935 * is responsible for disposing of the ptra (either putting it
936 * back on the ptraa, or destroying it).
937 * (2) This returns NULL if there is no Ptra at the index location.
938 * </pre>
939 */
940 L_PTRA *
ptraaGetPtra(L_PTRAA * paa,l_int32 index,l_int32 accessflag)941 ptraaGetPtra(L_PTRAA *paa,
942 l_int32 index,
943 l_int32 accessflag)
944 {
945 l_int32 n;
946 L_PTRA *pa;
947
948 PROCNAME("ptraaGetPtra");
949
950 if (!paa)
951 return (L_PTRA *)ERROR_PTR("paa not defined", procName, NULL);
952 ptraaGetSize(paa, &n);
953 if (index < 0 || index >= n)
954 return (L_PTRA *)ERROR_PTR("invalid index", procName, NULL);
955 if (accessflag != L_HANDLE_ONLY && accessflag != L_REMOVE)
956 return (L_PTRA *)ERROR_PTR("invalid accessflag", procName, NULL);
957
958 pa = paa->ptra[index];
959 if (accessflag == L_REMOVE)
960 paa->ptra[index] = NULL;
961 return pa;
962 }
963
964
965 /*--------------------------------------------------------------------------*
966 * Ptraa conversion *
967 *--------------------------------------------------------------------------*/
968 /*!
969 * \brief ptraaFlattenToPtra()
970 *
971 * \param[in] paa ptraa
972 * \return ptra, or NULL on error
973 *
974 * <pre>
975 * Notes:
976 * (1) This 'flattens' the ptraa to a ptra, taking the items in
977 * each ptra, in order, starting with the first ptra, etc.
978 * (2) As a side-effect, the ptra are all removed from the ptraa
979 * and destroyed, leaving an empty ptraa.
980 * </pre>
981 */
982 L_PTRA *
ptraaFlattenToPtra(L_PTRAA * paa)983 ptraaFlattenToPtra(L_PTRAA *paa)
984 {
985 l_int32 i, n;
986 L_PTRA *pat, *pad;
987
988 PROCNAME("ptraaFlattenToPtra");
989
990 if (!paa)
991 return (L_PTRA *)ERROR_PTR("paa not defined", procName, NULL);
992
993 pad = ptraCreate(0);
994 ptraaGetSize(paa, &n);
995 for (i = 0; i < n; i++) {
996 pat = ptraaGetPtra(paa, i, L_REMOVE);
997 if (!pat) continue;
998 ptraJoin(pad, pat);
999 ptraDestroy(&pat, FALSE, FALSE); /* they're all empty */
1000 }
1001
1002 return pad;
1003 }
1004