Leptonica  1.83.1
Image processing and image analysis suite
ptra.c
Go to the documentation of this file.
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 
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;
131  /* Static function */
132 static l_int32 ptraExtendArray(L_PTRA *pa);
133 
134 /*--------------------------------------------------------------------------*
135  * Ptra creation and destruction *
136  *--------------------------------------------------------------------------*/
143 L_PTRA *
144 ptraCreate(l_int32 n)
145 {
146 L_PTRA *pa;
147 
148  if (n > 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 
191 void
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  *--------------------------------------------------------------------------*/
245 l_ok
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 
272 static l_int32
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 
335 l_ok
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 
431 void *
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 
478 void *
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 
505 void *
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 
544 l_ok
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 
579 l_ok
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  *----------------------------------------------------------------------*/
612 l_ok
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 
634 l_ok
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  *----------------------------------------------------------------------*/
682 l_ok
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 
708 l_ok
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 
738 void *
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  *--------------------------------------------------------------------------*/
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 
801 void
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  *--------------------------------------------------------------------------*/
839 l_ok
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 
868 l_ok
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 
909 L_PTRA *
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  *--------------------------------------------------------------------------*/
949 L_PTRA *
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 }
L_PTRAA * ptraaCreate(l_int32 n)
ptraaCreate()
Definition: ptra.c:768
l_ok ptraReverse(L_PTRA *pa)
ptraReverse()
Definition: ptra.c:613
l_ok ptraInsert(L_PTRA *pa, l_int32 index, void *item, l_int32 shiftflag)
ptraInsert()
Definition: ptra.c:336
l_ok ptraaGetSize(L_PTRAA *paa, l_int32 *psize)
ptraaGetSize()
Definition: ptra.c:840
L_PTRA * ptraCreate(l_int32 n)
ptraCreate()
Definition: ptra.c:144
l_ok ptraJoin(L_PTRA *pa1, L_PTRA *pa2)
ptraJoin()
Definition: ptra.c:635
l_ok ptraGetMaxIndex(L_PTRA *pa, l_int32 *pmaxindex)
ptraGetMaxIndex()
Definition: ptra.c:683
l_ok ptraSwap(L_PTRA *pa, l_int32 index1, l_int32 index2)
ptraSwap()
Definition: ptra.c:545
L_PTRA * ptraaFlattenToPtra(L_PTRAA *paa)
ptraaFlattenToPtra()
Definition: ptra.c:950
static const l_int32 DefaultInitPtraSize
Definition: ptra.c:129
l_ok ptraGetActualCount(L_PTRA *pa, l_int32 *pcount)
ptraGetActualCount()
Definition: ptra.c:709
l_ok ptraCompactArray(L_PTRA *pa)
ptraCompactArray()
Definition: ptra.c:580
l_ok ptraAdd(L_PTRA *pa, void *item)
ptraAdd()
Definition: ptra.c:246
void * ptraReplace(L_PTRA *pa, l_int32 index, void *item, l_int32 freeflag)
ptraReplace()
Definition: ptra.c:506
void ptraDestroy(L_PTRA **ppa, l_int32 freeflag, l_int32 warnflag)
ptraDestroy()
Definition: ptra.c:192
void * ptraRemove(L_PTRA *pa, l_int32 index, l_int32 flag)
ptraRemove()
Definition: ptra.c:432
void ptraaDestroy(L_PTRAA **ppaa, l_int32 freeflag, l_int32 warnflag)
ptraaDestroy()
Definition: ptra.c:802
void * ptraGetPtrToItem(L_PTRA *pa, l_int32 index)
ptraGetPtrToItem()
Definition: ptra.c:739
L_PTRA * ptraaGetPtra(L_PTRAA *paa, l_int32 index, l_int32 accessflag)
ptraaGetPtra()
Definition: ptra.c:910
l_ok ptraaInsertPtra(L_PTRAA *paa, l_int32 index, L_PTRA *pa)
ptraaInsertPtra()
Definition: ptra.c:869
static l_int32 ptraExtendArray(L_PTRA *pa)
ptraExtendArray()
Definition: ptra.c:273
void * ptraRemoveLast(L_PTRA *pa)
ptraRemoveLast()
Definition: ptra.c:479
@ L_REMOVE
Definition: ptra.h:93
@ L_HANDLE_ONLY
Definition: ptra.h:92
@ L_COMPACTION
Definition: ptra.h:80
@ L_NO_COMPACTION
Definition: ptra.h:79
@ L_AUTO_DOWNSHIFT
Definition: ptra.h:85
@ L_FULL_DOWNSHIFT
Definition: ptra.h:87
@ L_MIN_DOWNSHIFT
Definition: ptra.h:86
Definition: ptra.h:54
l_int32 nalloc
Definition: ptra.h:55
l_int32 imax
Definition: ptra.h:56
void ** array
Definition: ptra.h:58
l_int32 nactual
Definition: ptra.h:57
Definition: ptra.h:65
l_int32 nalloc
Definition: ptra.h:66
struct L_Ptra ** ptra
Definition: ptra.h:67
void * reallocNew(void **pindata, size_t oldsize, size_t newsize)
reallocNew()
Definition: utils2.c:1262