Coverage Report

Created: 2025-06-13 07:02

/src/leptonica/src/ptra.c
Line
Count
Source (jump to first uncovered line)
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
0
{
146
0
L_PTRA  *pa;
147
148
0
    if (n > (l_int32)MaxInitPtraSize) {
149
0
        L_ERROR("n = %d > maxsize = %d\n", __func__, n, MaxInitPtraSize);
150
0
        return NULL;
151
0
    }
152
0
    if (n <= 0) n = DefaultInitPtraSize;
153
154
0
    pa = (L_PTRA *)LEPT_CALLOC(1, sizeof(L_PTRA));
155
0
    if ((pa->array = (void **)LEPT_CALLOC(n, sizeof(void *))) == NULL) {
156
0
        ptraDestroy(&pa, 0, 0);
157
0
        return (L_PTRA *)ERROR_PTR("ptr array not made", __func__, NULL);
158
0
    }
159
0
    pa->nalloc = n;
160
0
    pa->imax = -1;
161
0
    pa->nactual = 0;
162
0
    return pa;
163
0
}
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
0
{
196
0
l_int32  i, nactual;
197
0
void    *item;
198
0
L_PTRA  *pa;
199
200
0
    if (ppa == NULL) {
201
0
        L_WARNING("ptr address is NULL\n", __func__);
202
0
        return;
203
0
    }
204
0
    if ((pa = *ppa) == NULL)
205
0
        return;
206
207
0
    ptraGetActualCount(pa, &nactual);
208
0
    if (nactual > 0) {
209
0
        if (freeflag) {
210
0
            for (i = 0; i <= pa->imax; i++) {
211
0
                if ((item = ptraRemove(pa, i, L_NO_COMPACTION)) != NULL)
212
0
                    LEPT_FREE(item);
213
0
            }
214
0
        } else if (warnflag) {
215
0
            L_WARNING("potential memory leak of %d items in ptra\n",
216
0
                      __func__, nactual);
217
0
        }
218
0
    }
219
220
0
    LEPT_FREE(pa->array);
221
0
    LEPT_FREE(pa);
222
0
    *ppa = NULL;
223
0
}
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
0
{
249
0
l_int32  imax;
250
251
0
    if (!pa)
252
0
        return ERROR_INT("pa not defined", __func__, 1);
253
0
    if (!item)
254
0
        return ERROR_INT("item not defined", __func__, 1);
255
256
0
    ptraGetMaxIndex(pa, &imax);
257
0
    if (imax >= pa->nalloc - 1 && ptraExtendArray(pa))
258
0
        return ERROR_INT("extension failure", __func__, 1);
259
0
    pa->array[imax + 1] = (void *)item;
260
0
    pa->imax++;
261
0
    pa->nactual++;
262
0
    return 0;
263
0
}
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
0
{
275
0
    if (!pa)
276
0
        return ERROR_INT("pa not defined", __func__, 1);
277
278
0
    if ((pa->array = (void **)reallocNew((void **)&pa->array,
279
0
                                sizeof(void *) * pa->nalloc,
280
0
                                2 * sizeof(void *) * pa->nalloc)) == NULL)
281
0
            return ERROR_INT("new ptr array not returned", __func__, 1);
282
283
0
    pa->nalloc *= 2;
284
0
    return 0;
285
0
}
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
0
{
341
0
l_int32    i, ihole, imax;
342
0
l_float32  nexpected;
343
344
0
    if (!pa)
345
0
        return ERROR_INT("pa not defined", __func__, 1);
346
0
    if (index < 0 || index > pa->nalloc)
347
0
        return ERROR_INT("index not in [0 ... nalloc]", __func__, 1);
348
0
    if (shiftflag != L_AUTO_DOWNSHIFT && shiftflag != L_MIN_DOWNSHIFT &&
349
0
        shiftflag != L_FULL_DOWNSHIFT)
350
0
        return ERROR_INT("invalid shiftflag", __func__, 1);
351
352
0
    if (item) pa->nactual++;
353
0
    if (index == pa->nalloc) {  /* can happen when index == n */
354
0
        if (ptraExtendArray(pa))
355
0
            return ERROR_INT("extension failure", __func__, 1);
356
0
    }
357
358
        /* We are inserting into a hole or adding to the end of the array.
359
         * No existing items are moved. */
360
0
    ptraGetMaxIndex(pa, &imax);
361
0
    if (pa->array[index] == NULL) {
362
0
        pa->array[index] = item;
363
0
        if (item && index > imax)  /* new item put beyond max so far */
364
0
            pa->imax = index;
365
0
        return 0;
366
0
    }
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
0
    if (imax >= pa->nalloc - 1 && ptraExtendArray(pa))
375
0
        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
0
    if (imax + 1 == pa->nactual) {
381
0
        shiftflag = L_FULL_DOWNSHIFT;
382
0
    } else if (shiftflag == L_AUTO_DOWNSHIFT) {
383
0
        if (imax < 10) {
384
0
            shiftflag = L_FULL_DOWNSHIFT;  /* no big deal */
385
0
        } else {
386
0
            nexpected = (l_float32)(imax - pa->nactual) *
387
0
                         (l_float32)((imax - index) / imax);
388
0
            shiftflag = (nexpected > 2.0) ? L_MIN_DOWNSHIFT : L_FULL_DOWNSHIFT;
389
0
        }
390
0
    }
391
392
0
    if (shiftflag == L_MIN_DOWNSHIFT) {  /* run down looking for a hole */
393
0
        for (ihole = index + 1; ihole <= imax; ihole++) {
394
0
             if (pa->array[ihole] == NULL)
395
0
                 break;
396
0
        }
397
0
    } else {  /* L_FULL_DOWNSHIFT */
398
0
        ihole = imax + 1;
399
0
    }
400
401
0
    for (i = ihole; i > index; i--)
402
0
        pa->array[i] = pa->array[i - 1];
403
0
    pa->array[index] = (void *)item;
404
0
    if (ihole == imax + 1)  /* the last item was shifted down */
405
0
        pa->imax++;
406
407
0
    return 0;
408
0
}
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
0
{
436
0
l_int32  i, imax, fromend, icurrent;
437
0
void    *item;
438
439
0
    if (!pa)
440
0
        return (void *)ERROR_PTR("pa not defined", __func__, NULL);
441
0
    ptraGetMaxIndex(pa, &imax);
442
0
    if (index < 0 || index > imax)
443
0
        return (void *)ERROR_PTR("index not in [0 ... imax]", __func__, NULL);
444
445
0
    item = pa->array[index];
446
0
    if (item)
447
0
        pa->nactual--;
448
0
    pa->array[index] = NULL;
449
450
        /* If we took the last item, need to reduce pa->n */
451
0
    fromend = (index == imax);
452
0
    if (fromend) {
453
0
        for (i = index - 1; i >= 0; i--) {
454
0
            if (pa->array[i])
455
0
                break;
456
0
        }
457
0
        pa->imax = i;
458
0
    }
459
460
        /* Compact from index to the end of the array */
461
0
    if (!fromend && flag == L_COMPACTION) {
462
0
        for (icurrent = index, i = index + 1; i <= imax; i++) {
463
0
            if (pa->array[i])
464
0
                pa->array[icurrent++] = pa->array[i];
465
0
        }
466
0
        pa->imax = icurrent - 1;
467
0
    }
468
0
    return item;
469
0
}
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
0
{
481
0
l_int32  imax;
482
483
0
    if (!pa)
484
0
        return (void *)ERROR_PTR("pa not defined", __func__, NULL);
485
486
        /* Remove the last item in the array.  No compaction is required. */
487
0
    ptraGetMaxIndex(pa, &imax);
488
0
    if (imax >= 0)
489
0
        return ptraRemove(pa, imax, L_NO_COMPACTION);
490
0
    else  /* empty */
491
0
        return NULL;
492
0
}
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
0
{
511
0
l_int32  imax;
512
0
void    *olditem;
513
514
0
    if (!pa)
515
0
        return (void *)ERROR_PTR("pa not defined", __func__, NULL);
516
0
    ptraGetMaxIndex(pa, &imax);
517
0
    if (index < 0 || index > imax)
518
0
        return (void *)ERROR_PTR("index not in [0 ... imax]", __func__, NULL);
519
520
0
    olditem = pa->array[index];
521
0
    pa->array[index] = item;
522
0
    if (!item && olditem)
523
0
        pa->nactual--;
524
0
    else if (item && !olditem)
525
0
        pa->nactual++;
526
527
0
    if (freeflag == FALSE)
528
0
        return olditem;
529
530
0
    if (olditem)
531
0
        LEPT_FREE(olditem);
532
0
    return NULL;
533
0
}
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
0
{
549
0
l_int32  imax;
550
0
void    *item;
551
552
0
    if (!pa)
553
0
        return ERROR_INT("pa not defined", __func__, 1);
554
0
    if (index1 == index2)
555
0
        return 0;
556
0
    ptraGetMaxIndex(pa, &imax);
557
0
    if (index1 < 0 || index1 > imax || index2 < 0 || index2 > imax)
558
0
        return ERROR_INT("invalid index: not in [0 ... imax]", __func__, 1);
559
560
0
    item = ptraRemove(pa, index1, L_NO_COMPACTION);
561
0
    item = ptraReplace(pa, index2, item, FALSE);
562
0
    ptraInsert(pa, index1, item, L_MIN_DOWNSHIFT);
563
0
    return 0;
564
0
}
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
0
{
582
0
l_int32  i, imax, nactual, index;
583
584
0
    if (!pa)
585
0
        return ERROR_INT("pa not defined", __func__, 1);
586
0
    ptraGetMaxIndex(pa, &imax);
587
0
    ptraGetActualCount(pa, &nactual);
588
0
    if (imax + 1 == nactual) return 0;
589
590
        /* Compact the array */
591
0
    for (i = 0, index = 0; i <= imax; i++) {
592
0
        if (pa->array[i])
593
0
             pa->array[index++] = pa->array[i];
594
0
    }
595
0
    pa->imax = index - 1;
596
0
    if (nactual != index)
597
0
        L_ERROR("index = %d; != nactual\n", __func__, index);
598
599
0
    return 0;
600
0
}
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
0
{
615
0
l_int32  i, imax;
616
617
0
    if (!pa)
618
0
        return ERROR_INT("pa not defined", __func__, 1);
619
0
    ptraGetMaxIndex(pa, &imax);
620
621
0
    for (i = 0; i < (imax + 1) / 2; i++)
622
0
        ptraSwap(pa, i, imax - i);
623
0
    return 0;
624
0
}
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
0
{
638
0
l_int32  i, imax;
639
0
void    *item;
640
641
0
    if (!pa1)
642
0
        return ERROR_INT("pa1 not defined", __func__, 1);
643
0
    if (!pa2)
644
0
        return 0;
645
646
0
    ptraGetMaxIndex(pa2, &imax);
647
0
    for (i = 0; i <= imax; i++) {
648
0
        item = ptraRemove(pa2, i, L_NO_COMPACTION);
649
0
        ptraAdd(pa1, item);
650
0
    }
651
652
0
    return 0;
653
0
}
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
0
{
686
0
    if (!pa)
687
0
        return ERROR_INT("pa not defined", __func__, 1);
688
0
    if (!pmaxindex)
689
0
        return ERROR_INT("&maxindex not defined", __func__, 1);
690
0
    *pmaxindex = pa->imax;
691
0
    return 0;
692
0
}
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
0
{
712
0
    if (!pa)
713
0
        return ERROR_INT("pa not defined", __func__, 1);
714
0
    if (!pcount)
715
0
        return ERROR_INT("&count not defined", __func__, 1);
716
0
    *pcount = pa->nactual;
717
718
0
    return 0;
719
0
}
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
0
{
742
0
    if (!pa)
743
0
        return (void *)ERROR_PTR("pa not defined", __func__, NULL);
744
0
    if (index < 0 || index >= pa->nalloc)
745
0
        return (void *)ERROR_PTR("index not in [0 ... nalloc-1]",
746
0
                                 __func__, NULL);
747
748
0
    return pa->array[index];
749
0
}
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
0
{
770
0
L_PTRAA  *paa;
771
772
0
    if (n <= 0)
773
0
        return (L_PTRAA *)ERROR_PTR("n must be > 0", __func__, NULL);
774
775
0
    paa = (L_PTRAA *)LEPT_CALLOC(1, sizeof(L_PTRAA));
776
0
    if ((paa->ptra = (L_PTRA **)LEPT_CALLOC(n, sizeof(L_PTRA *))) == NULL) {
777
0
        ptraaDestroy(&paa, 0, 0);
778
0
        return (L_PTRAA *)ERROR_PTR("ptr array not made", __func__, NULL);
779
0
    }
780
0
    paa->nalloc = n;
781
0
    return paa;
782
0
}
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
0
{
806
0
l_int32   i, n;
807
0
L_PTRA   *pa;
808
0
L_PTRAA  *paa;
809
810
0
    if (ppaa == NULL) {
811
0
        L_WARNING("ptr address is NULL\n", __func__);
812
0
        return;
813
0
    }
814
0
    if ((paa = *ppaa) == NULL)
815
0
        return;
816
817
0
    ptraaGetSize(paa, &n);
818
0
    for (i = 0; i < n; i++) {
819
0
        pa = ptraaGetPtra(paa, i, L_REMOVE);
820
0
        ptraDestroy(&pa, freeflag, warnflag);
821
0
    }
822
823
0
    LEPT_FREE(paa->ptra);
824
0
    LEPT_FREE(paa);
825
0
    *ppaa = NULL;
826
0
}
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
0
{
843
0
    if (!paa)
844
0
        return ERROR_INT("paa not defined", __func__, 1);
845
0
    if (!psize)
846
0
        return ERROR_INT("&size not defined", __func__, 1);
847
0
    *psize = paa->nalloc;
848
849
0
    return 0;
850
0
}
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
0
{
873
0
l_int32  n;
874
875
0
    if (!paa)
876
0
        return ERROR_INT("paa not defined", __func__, 1);
877
0
    if (!pa)
878
0
        return ERROR_INT("pa not defined", __func__, 1);
879
0
    ptraaGetSize(paa, &n);
880
0
    if (index < 0 || index >= n)
881
0
        return ERROR_INT("invalid index", __func__, 1);
882
0
    if (paa->ptra[index] != NULL)
883
0
        return ERROR_INT("ptra already stored at index", __func__, 1);
884
885
0
    paa->ptra[index] = pa;
886
0
    return 0;
887
0
}
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
0
{
914
0
l_int32  n;
915
0
L_PTRA  *pa;
916
917
0
    if (!paa)
918
0
        return (L_PTRA *)ERROR_PTR("paa not defined", __func__, NULL);
919
0
    ptraaGetSize(paa, &n);
920
0
    if (index < 0 || index >= n)
921
0
        return (L_PTRA *)ERROR_PTR("invalid index", __func__, NULL);
922
0
    if (accessflag != L_HANDLE_ONLY && accessflag != L_REMOVE)
923
0
        return (L_PTRA *)ERROR_PTR("invalid accessflag", __func__, NULL);
924
925
0
    pa = paa->ptra[index];
926
0
    if (accessflag == L_REMOVE)
927
0
        paa->ptra[index] = NULL;
928
0
    return pa;
929
0
}
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
0
{
952
0
l_int32  i, n;
953
0
L_PTRA    *pat, *pad;
954
955
0
    if (!paa)
956
0
        return (L_PTRA *)ERROR_PTR("paa not defined", __func__, NULL);
957
958
0
    pad = ptraCreate(0);
959
0
    ptraaGetSize(paa, &n);
960
0
    for (i = 0; i < n; i++) {
961
0
        pat = ptraaGetPtra(paa, i, L_REMOVE);
962
0
        if (!pat) continue;
963
0
        ptraJoin(pad, pat);
964
0
        ptraDestroy(&pat, FALSE, FALSE);  /* they're all empty */
965
0
    }
966
967
0
    return pad;
968
0
}