Leptonica  1.82.0
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  PROCNAME("ptraCreate");
149 
150  if (n > MaxInitPtraSize) {
151  L_ERROR("n = %d > maxsize = %d\n", procName, n, MaxInitPtraSize);
152  return NULL;
153  }
154  if (n <= 0) n = DefaultInitPtraSize;
155 
156  pa = (L_PTRA *)LEPT_CALLOC(1, sizeof(L_PTRA));
157  if ((pa->array = (void **)LEPT_CALLOC(n, sizeof(void *))) == NULL) {
158  ptraDestroy(&pa, 0, 0);
159  return (L_PTRA *)ERROR_PTR("ptr array not made", procName, NULL);
160  }
161  pa->nalloc = n;
162  pa->imax = -1;
163  pa->nactual = 0;
164  return pa;
165 }
166 
167 
193 void
195  l_int32 freeflag,
196  l_int32 warnflag)
197 {
198 l_int32 i, nactual;
199 void *item;
200 L_PTRA *pa;
201 
202  PROCNAME("ptraDestroy");
203 
204  if (ppa == NULL) {
205  L_WARNING("ptr address is NULL\n", procName);
206  return;
207  }
208  if ((pa = *ppa) == NULL)
209  return;
210 
211  ptraGetActualCount(pa, &nactual);
212  if (nactual > 0) {
213  if (freeflag) {
214  for (i = 0; i <= pa->imax; i++) {
215  if ((item = ptraRemove(pa, i, L_NO_COMPACTION)) != NULL)
216  LEPT_FREE(item);
217  }
218  } else if (warnflag) {
219  L_WARNING("potential memory leak of %d items in ptra\n",
220  procName, nactual);
221  }
222  }
223 
224  LEPT_FREE(pa->array);
225  LEPT_FREE(pa);
226  *ppa = NULL;
227 }
228 
229 
230 /*--------------------------------------------------------------------------*
231  * Add/insert/remove/replace generic ptr object *
232  *--------------------------------------------------------------------------*/
249 l_ok
251  void *item)
252 {
253 l_int32 imax;
254 
255  PROCNAME("ptraAdd");
256 
257  if (!pa)
258  return ERROR_INT("pa not defined", procName, 1);
259  if (!item)
260  return ERROR_INT("item not defined", procName, 1);
261 
262  ptraGetMaxIndex(pa, &imax);
263  if (imax >= pa->nalloc - 1 && ptraExtendArray(pa))
264  return ERROR_INT("extension failure", procName, 1);
265  pa->array[imax + 1] = (void *)item;
266  pa->imax++;
267  pa->nactual++;
268  return 0;
269 }
270 
271 
278 static l_int32
280 {
281  PROCNAME("ptraExtendArray");
282 
283  if (!pa)
284  return ERROR_INT("pa not defined", procName, 1);
285 
286  if ((pa->array = (void **)reallocNew((void **)&pa->array,
287  sizeof(void *) * pa->nalloc,
288  2 * sizeof(void *) * pa->nalloc)) == NULL)
289  return ERROR_INT("new ptr array not returned", procName, 1);
290 
291  pa->nalloc *= 2;
292  return 0;
293 }
294 
295 
343 l_ok
345  l_int32 index,
346  void *item,
347  l_int32 shiftflag)
348 {
349 l_int32 i, ihole, imax;
350 l_float32 nexpected;
351 
352  PROCNAME("ptraInsert");
353 
354  if (!pa)
355  return ERROR_INT("pa not defined", procName, 1);
356  if (index < 0 || index > pa->nalloc)
357  return ERROR_INT("index not in [0 ... nalloc]", procName, 1);
358  if (shiftflag != L_AUTO_DOWNSHIFT && shiftflag != L_MIN_DOWNSHIFT &&
359  shiftflag != L_FULL_DOWNSHIFT)
360  return ERROR_INT("invalid shiftflag", procName, 1);
361 
362  if (item) pa->nactual++;
363  if (index == pa->nalloc) { /* can happen when index == n */
364  if (ptraExtendArray(pa))
365  return ERROR_INT("extension failure", procName, 1);
366  }
367 
368  /* We are inserting into a hole or adding to the end of the array.
369  * No existing items are moved. */
370  ptraGetMaxIndex(pa, &imax);
371  if (pa->array[index] == NULL) {
372  pa->array[index] = item;
373  if (item && index > imax) /* new item put beyond max so far */
374  pa->imax = index;
375  return 0;
376  }
377 
378  /* We are inserting at the location of an existing item,
379  * forcing the existing item and those below to shift down.
380  * First, extend the array automatically if the last element
381  * (nalloc - 1) is occupied (imax). This may not be necessary
382  * in every situation, but only an anomalous sequence of insertions
383  * into the array would cause extra ptr allocation. */
384  if (imax >= pa->nalloc - 1 && ptraExtendArray(pa))
385  return ERROR_INT("extension failure", procName, 1);
386 
387  /* If there are no holes, do a full downshift.
388  * Otherwise, if L_AUTO_DOWNSHIFT, use the expected number
389  * of holes between index and n to determine the shift mode */
390  if (imax + 1 == pa->nactual) {
391  shiftflag = L_FULL_DOWNSHIFT;
392  } else if (shiftflag == L_AUTO_DOWNSHIFT) {
393  if (imax < 10) {
394  shiftflag = L_FULL_DOWNSHIFT; /* no big deal */
395  } else {
396  nexpected = (l_float32)(imax - pa->nactual) *
397  (l_float32)((imax - index) / imax);
398  shiftflag = (nexpected > 2.0) ? L_MIN_DOWNSHIFT : L_FULL_DOWNSHIFT;
399  }
400  }
401 
402  if (shiftflag == L_MIN_DOWNSHIFT) { /* run down looking for a hole */
403  for (ihole = index + 1; ihole <= imax; ihole++) {
404  if (pa->array[ihole] == NULL)
405  break;
406  }
407  } else { /* L_FULL_DOWNSHIFT */
408  ihole = imax + 1;
409  }
410 
411  for (i = ihole; i > index; i--)
412  pa->array[i] = pa->array[i - 1];
413  pa->array[index] = (void *)item;
414  if (ihole == imax + 1) /* the last item was shifted down */
415  pa->imax++;
416 
417  return 0;
418 }
419 
420 
441 void *
443  l_int32 index,
444  l_int32 flag)
445 {
446 l_int32 i, imax, fromend, icurrent;
447 void *item;
448 
449  PROCNAME("ptraRemove");
450 
451  if (!pa)
452  return (void *)ERROR_PTR("pa not defined", procName, NULL);
453  ptraGetMaxIndex(pa, &imax);
454  if (index < 0 || index > imax)
455  return (void *)ERROR_PTR("index not in [0 ... imax]", procName, NULL);
456 
457  item = pa->array[index];
458  if (item)
459  pa->nactual--;
460  pa->array[index] = NULL;
461 
462  /* If we took the last item, need to reduce pa->n */
463  fromend = (index == imax);
464  if (fromend) {
465  for (i = index - 1; i >= 0; i--) {
466  if (pa->array[i])
467  break;
468  }
469  pa->imax = i;
470  }
471 
472  /* Compact from index to the end of the array */
473  if (!fromend && flag == L_COMPACTION) {
474  for (icurrent = index, i = index + 1; i <= imax; i++) {
475  if (pa->array[i])
476  pa->array[icurrent++] = pa->array[i];
477  }
478  pa->imax = icurrent - 1;
479  }
480  return item;
481 }
482 
483 
490 void *
492 {
493 l_int32 imax;
494 
495  PROCNAME("ptraRemoveLast");
496 
497  if (!pa)
498  return (void *)ERROR_PTR("pa not defined", procName, NULL);
499 
500  /* Remove the last item in the array. No compaction is required. */
501  ptraGetMaxIndex(pa, &imax);
502  if (imax >= 0)
503  return ptraRemove(pa, imax, L_NO_COMPACTION);
504  else /* empty */
505  return NULL;
506 }
507 
508 
519 void *
521  l_int32 index,
522  void *item,
523  l_int32 freeflag)
524 {
525 l_int32 imax;
526 void *olditem;
527 
528  PROCNAME("ptraReplace");
529 
530  if (!pa)
531  return (void *)ERROR_PTR("pa not defined", procName, NULL);
532  ptraGetMaxIndex(pa, &imax);
533  if (index < 0 || index > imax)
534  return (void *)ERROR_PTR("index not in [0 ... imax]", procName, NULL);
535 
536  olditem = pa->array[index];
537  pa->array[index] = item;
538  if (!item && olditem)
539  pa->nactual--;
540  else if (item && !olditem)
541  pa->nactual++;
542 
543  if (freeflag == FALSE)
544  return olditem;
545 
546  if (olditem)
547  LEPT_FREE(olditem);
548  return NULL;
549 }
550 
551 
560 l_ok
562  l_int32 index1,
563  l_int32 index2)
564 {
565 l_int32 imax;
566 void *item;
567 
568  PROCNAME("ptraSwap");
569 
570  if (!pa)
571  return ERROR_INT("pa not defined", procName, 1);
572  if (index1 == index2)
573  return 0;
574  ptraGetMaxIndex(pa, &imax);
575  if (index1 < 0 || index1 > imax || index2 < 0 || index2 > imax)
576  return ERROR_INT("invalid index: not in [0 ... imax]", procName, 1);
577 
578  item = ptraRemove(pa, index1, L_NO_COMPACTION);
579  item = ptraReplace(pa, index2, item, FALSE);
580  ptraInsert(pa, index1, item, L_MIN_DOWNSHIFT);
581  return 0;
582 }
583 
584 
597 l_ok
599 {
600 l_int32 i, imax, nactual, index;
601 
602  PROCNAME("ptraCompactArray");
603 
604  if (!pa)
605  return ERROR_INT("pa not defined", procName, 1);
606  ptraGetMaxIndex(pa, &imax);
607  ptraGetActualCount(pa, &nactual);
608  if (imax + 1 == nactual) return 0;
609 
610  /* Compact the array */
611  for (i = 0, index = 0; i <= imax; i++) {
612  if (pa->array[i])
613  pa->array[index++] = pa->array[i];
614  }
615  pa->imax = index - 1;
616  if (nactual != index)
617  L_ERROR("index = %d; != nactual\n", procName, index);
618 
619  return 0;
620 }
621 
622 
623 /*----------------------------------------------------------------------*
624  * Other array operations *
625  *----------------------------------------------------------------------*/
632 l_ok
634 {
635 l_int32 i, imax;
636 
637  PROCNAME("ptraReverse");
638 
639  if (!pa)
640  return ERROR_INT("pa not defined", procName, 1);
641  ptraGetMaxIndex(pa, &imax);
642 
643  for (i = 0; i < (imax + 1) / 2; i++)
644  ptraSwap(pa, i, imax - i);
645  return 0;
646 }
647 
648 
656 l_ok
658  L_PTRA *pa2)
659 {
660 l_int32 i, imax;
661 void *item;
662 
663  PROCNAME("ptraJoin");
664 
665  if (!pa1)
666  return ERROR_INT("pa1 not defined", procName, 1);
667  if (!pa2)
668  return 0;
669 
670  ptraGetMaxIndex(pa2, &imax);
671  for (i = 0; i <= imax; i++) {
672  item = ptraRemove(pa2, i, L_NO_COMPACTION);
673  ptraAdd(pa1, item);
674  }
675 
676  return 0;
677 }
678 
679 
680 
681 /*----------------------------------------------------------------------*
682  * Simple ptra accessors *
683  *----------------------------------------------------------------------*/
706 l_ok
708  l_int32 *pmaxindex)
709 {
710  PROCNAME("ptraGetMaxIndex");
711 
712  if (!pa)
713  return ERROR_INT("pa not defined", procName, 1);
714  if (!pmaxindex)
715  return ERROR_INT("&maxindex not defined", procName, 1);
716  *pmaxindex = pa->imax;
717  return 0;
718 }
719 
720 
734 l_ok
736  l_int32 *pcount)
737 {
738  PROCNAME("ptraGetActualCount");
739 
740  if (!pa)
741  return ERROR_INT("pa not defined", procName, 1);
742  if (!pcount)
743  return ERROR_INT("&count not defined", procName, 1);
744  *pcount = pa->nactual;
745 
746  return 0;
747 }
748 
749 
766 void *
768  l_int32 index)
769 {
770  PROCNAME("ptraGetPtrToItem");
771 
772  if (!pa)
773  return (void *)ERROR_PTR("pa not defined", procName, NULL);
774  if (index < 0 || index >= pa->nalloc)
775  return (void *)ERROR_PTR("index not in [0 ... nalloc-1]",
776  procName, NULL);
777 
778  return pa->array[index];
779 }
780 
781 
782 /*--------------------------------------------------------------------------*
783  * Ptraa creation and destruction *
784  *--------------------------------------------------------------------------*/
797 L_PTRAA *
798 ptraaCreate(l_int32 n)
799 {
800 L_PTRAA *paa;
801 
802  PROCNAME("ptraaCreate");
803 
804  if (n <= 0)
805  return (L_PTRAA *)ERROR_PTR("n must be > 0", procName, NULL);
806 
807  paa = (L_PTRAA *)LEPT_CALLOC(1, sizeof(L_PTRAA));
808  if ((paa->ptra = (L_PTRA **)LEPT_CALLOC(n, sizeof(L_PTRA *))) == NULL) {
809  ptraaDestroy(&paa, 0, 0);
810  return (L_PTRAA *)ERROR_PTR("ptr array not made", procName, NULL);
811  }
812  paa->nalloc = n;
813  return paa;
814 }
815 
816 
833 void
835  l_int32 freeflag,
836  l_int32 warnflag)
837 {
838 l_int32 i, n;
839 L_PTRA *pa;
840 L_PTRAA *paa;
841 
842  PROCNAME("ptraaDestroy");
843 
844  if (ppaa == NULL) {
845  L_WARNING("ptr address is NULL\n", procName);
846  return;
847  }
848  if ((paa = *ppaa) == NULL)
849  return;
850 
851  ptraaGetSize(paa, &n);
852  for (i = 0; i < n; i++) {
853  pa = ptraaGetPtra(paa, i, L_REMOVE);
854  ptraDestroy(&pa, freeflag, warnflag);
855  }
856 
857  LEPT_FREE(paa->ptra);
858  LEPT_FREE(paa);
859  *ppaa = NULL;
860 }
861 
862 
863 /*--------------------------------------------------------------------------*
864  * Ptraa accessors *
865  *--------------------------------------------------------------------------*/
873 l_ok
875  l_int32 *psize)
876 {
877  PROCNAME("ptraaGetSize");
878 
879  if (!paa)
880  return ERROR_INT("paa not defined", procName, 1);
881  if (!psize)
882  return ERROR_INT("&size not defined", procName, 1);
883  *psize = paa->nalloc;
884 
885  return 0;
886 }
887 
888 
904 l_ok
906  l_int32 index,
907  L_PTRA *pa)
908 {
909 l_int32 n;
910 
911  PROCNAME("ptraaInsertPtra");
912 
913  if (!paa)
914  return ERROR_INT("paa not defined", procName, 1);
915  if (!pa)
916  return ERROR_INT("pa not defined", procName, 1);
917  ptraaGetSize(paa, &n);
918  if (index < 0 || index >= n)
919  return ERROR_INT("invalid index", procName, 1);
920  if (paa->ptra[index] != NULL)
921  return ERROR_INT("ptra already stored at index", procName, 1);
922 
923  paa->ptra[index] = pa;
924  return 0;
925 }
926 
927 
947 L_PTRA *
949  l_int32 index,
950  l_int32 accessflag)
951 {
952 l_int32 n;
953 L_PTRA *pa;
954 
955  PROCNAME("ptraaGetPtra");
956 
957  if (!paa)
958  return (L_PTRA *)ERROR_PTR("paa not defined", procName, NULL);
959  ptraaGetSize(paa, &n);
960  if (index < 0 || index >= n)
961  return (L_PTRA *)ERROR_PTR("invalid index", procName, NULL);
962  if (accessflag != L_HANDLE_ONLY && accessflag != L_REMOVE)
963  return (L_PTRA *)ERROR_PTR("invalid accessflag", procName, NULL);
964 
965  pa = paa->ptra[index];
966  if (accessflag == L_REMOVE)
967  paa->ptra[index] = NULL;
968  return pa;
969 }
970 
971 
972 /*--------------------------------------------------------------------------*
973  * Ptraa conversion *
974  *--------------------------------------------------------------------------*/
989 L_PTRA *
991 {
992 l_int32 i, n;
993 L_PTRA *pat, *pad;
994 
995  PROCNAME("ptraaFlattenToPtra");
996 
997  if (!paa)
998  return (L_PTRA *)ERROR_PTR("paa not defined", procName, NULL);
999 
1000  pad = ptraCreate(0);
1001  ptraaGetSize(paa, &n);
1002  for (i = 0; i < n; i++) {
1003  pat = ptraaGetPtra(paa, i, L_REMOVE);
1004  if (!pat) continue;
1005  ptraJoin(pad, pat);
1006  ptraDestroy(&pat, FALSE, FALSE); /* they're all empty */
1007  }
1008 
1009  return pad;
1010 }
L_PTRAA * ptraaCreate(l_int32 n)
ptraaCreate()
Definition: ptra.c:798
l_ok ptraReverse(L_PTRA *pa)
ptraReverse()
Definition: ptra.c:633
l_ok ptraInsert(L_PTRA *pa, l_int32 index, void *item, l_int32 shiftflag)
ptraInsert()
Definition: ptra.c:344
l_ok ptraaGetSize(L_PTRAA *paa, l_int32 *psize)
ptraaGetSize()
Definition: ptra.c:874
L_PTRA * ptraCreate(l_int32 n)
ptraCreate()
Definition: ptra.c:144
l_ok ptraJoin(L_PTRA *pa1, L_PTRA *pa2)
ptraJoin()
Definition: ptra.c:657
l_ok ptraGetMaxIndex(L_PTRA *pa, l_int32 *pmaxindex)
ptraGetMaxIndex()
Definition: ptra.c:707
l_ok ptraSwap(L_PTRA *pa, l_int32 index1, l_int32 index2)
ptraSwap()
Definition: ptra.c:561
L_PTRA * ptraaFlattenToPtra(L_PTRAA *paa)
ptraaFlattenToPtra()
Definition: ptra.c:990
static const l_int32 DefaultInitPtraSize
Definition: ptra.c:129
l_ok ptraGetActualCount(L_PTRA *pa, l_int32 *pcount)
ptraGetActualCount()
Definition: ptra.c:735
l_ok ptraCompactArray(L_PTRA *pa)
ptraCompactArray()
Definition: ptra.c:598
l_ok ptraAdd(L_PTRA *pa, void *item)
ptraAdd()
Definition: ptra.c:250
void * ptraReplace(L_PTRA *pa, l_int32 index, void *item, l_int32 freeflag)
ptraReplace()
Definition: ptra.c:520
void ptraDestroy(L_PTRA **ppa, l_int32 freeflag, l_int32 warnflag)
ptraDestroy()
Definition: ptra.c:194
void * ptraRemove(L_PTRA *pa, l_int32 index, l_int32 flag)
ptraRemove()
Definition: ptra.c:442
void ptraaDestroy(L_PTRAA **ppaa, l_int32 freeflag, l_int32 warnflag)
ptraaDestroy()
Definition: ptra.c:834
void * ptraGetPtrToItem(L_PTRA *pa, l_int32 index)
ptraGetPtrToItem()
Definition: ptra.c:767
L_PTRA * ptraaGetPtra(L_PTRAA *paa, l_int32 index, l_int32 accessflag)
ptraaGetPtra()
Definition: ptra.c:948
l_ok ptraaInsertPtra(L_PTRAA *paa, l_int32 index, L_PTRA *pa)
ptraaInsertPtra()
Definition: ptra.c:905
static l_int32 ptraExtendArray(L_PTRA *pa)
ptraExtendArray()
Definition: ptra.c:279
void * ptraRemoveLast(L_PTRA *pa)
ptraRemoveLast()
Definition: ptra.c:491
@ 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:1302