Implements 1d and 2d arrays of generic pointers (Ptra, Ptraa) More...

#include <stdio.h>
#include <stdlib.h>
#include "allheaders.h"

Functions
L_PTRA *	ptraCreate (l_int32 n)
void	ptraDestroy (L_PTRA **ppa, l_int32 freeflag, l_int32 warnflag)
l_int32	ptraAdd (L_PTRA pa, void item)
l_int32	ptraExtendArray (L_PTRA *pa)
l_int32	ptraInsert (L_PTRA pa, l_int32 index, void item, l_int32 shiftflag)
void *	ptraGetHandle (L_PTRA *pa, l_int32 index)
void *	ptraRemove (L_PTRA *pa, l_int32 index, l_int32 flag)
void *	ptraRemoveLast (L_PTRA *pa)
void *	ptraReplace (L_PTRA pa, l_int32 index, void item, l_int32 freeflag)
l_int32	ptraSwap (L_PTRA *pa, l_int32 index1, l_int32 index2)
l_int32	ptraCompactArray (L_PTRA *pa)
l_int32	ptraReverse (L_PTRA *pa)
l_int32	ptraJoin (L_PTRA pa1, L_PTRA pa2)
l_int32	ptraGetMaxIndex (L_PTRA pa, l_int32 pmaxindex)
l_int32	ptraGetActualCount (L_PTRA pa, l_int32 pcount)
void *	ptraGetPtrToItem (L_PTRA *pa, l_int32 index)
L_PTRAA *	ptraaCreate (l_int32 n)
void	ptraaDestroy (L_PTRAA **ppaa, l_int32 freeflag, l_int32 warnflag)
l_int32	ptraaGetSize (L_PTRAA paa, l_int32 psize)
l_int32	ptraaInsertPtra (L_PTRAA paa, l_int32 index, L_PTRA pa)
L_PTRA *	ptraaGetPtra (L_PTRAA *paa, l_int32 index, l_int32 accessflag)
L_PTRA *	ptraaFlattenToPtra (L_PTRAA *paa)
NUMA *	numaGetBinSortIndex (NUMA *nas, l_int32 sortorder)
Variables
static const l_int32	INITIAL_PTR_ARRAYSIZE = 20

Detailed Description

Implements 1d and 2d arrays of generic pointers (Ptra, Ptraa)

    Ptra creation and destruction
        L_PTRA      *ptraCreate()
        void        *ptraDestroy()

    Add/insert/remove/replace generic ptr object
        l_int32      ptraAdd()
        l_int32      ptraExtendArray()
        l_int32      ptraInsert()
        void        *ptraGetHandle()
        void        *ptraRemove()
        void        *ptraRemoveLast()
        void        *ptraReplace()
        l_int32      ptraSwap()
        l_int32      ptraCompactArray()

    Other array operations
        l_int32      ptraReverse()
        l_int32      ptraJoin()

    Simple Ptra accessors
        l_int32      ptraGetMaxIndex()
        l_int32      ptraGetActualCount()
        void        *ptraGetPtrToItem()

    Ptraa creation and destruction
        L_PTRAA     *ptraaCreate()
        void        *ptraaDestroy()

    Ptraa accessors
        l_int32      ptraaGetSize()
        l_int32      ptraaInsertPtra()
        L_PTRA      *ptraaGetPtra()

    Ptraa conversion
        L_PTRA      *ptraaFlattenToPtra()

    Functions using L_PTRA
        NUMA        *numaGetBinSortIndex()

  Notes on the Ptra:

  (1) The Ptra is a struct, not an array.  Always use the accessors
      in this file, never the fields directly.
  (2) Items can be placed anywhere in the allocated ptr array,
      including one index beyond the last ptr (in which case the
      ptr array is realloc'd).
  (3) Thus, the items on the ptr array need not be compacted.  In
      general there will be null pointers in the ptr array.
  (4) A compacted array will remain compacted on removal if
      arbitrary items are removed with compaction, or if items
      are removed from the end of the array.
  (5) For addition to and removal from the end of the array, this
      functions exactly like a stack, and with the same O(1) cost.
  (6) This differs from the generic stack in that we allow
      random access for insertion, removal and replacement.
      Removal can be done without compacting the array.
      Insertion into a null ptr in the array has no effect on
      the other pointers, but insertion into a location already
      occupied by an item has a cost proportional to the
      distance to the next null ptr in the array.
  (7) Null ptrs are valid input args for both insertion and
      replacement; this allows arbitrary swapping.
  (8) The item in the array with the largest index is at pa->imax.
      This can be any value from -1 (initialized; all array ptrs
      are null) up to pa->nalloc - 1 (the last ptr in the array).
  (9) In referring to the array: the first ptr is the "top" or
      "beginning"; the last pointer is the "bottom" or "end";
      items are shifted "up" towards the top when compaction occurs;
      and items are shifted "down" towards the bottom when forced to
      move due to an insertion.
 (10) It should be emphasized that insertion, removal and replacement
      are general:
 You can insert an item into any ptr location in the
         allocated ptr array, as well as into the next ptr address
         beyond the allocated array (in which case a realloc will occur).   
 You can remove or replace an item from any ptr location
         in the allocated ptr array.
 When inserting into an occupied location, you have
         three options for downshifting.
 When removing, you can either leave the ptr null or
         compact the array.

  Notes on the Ptraa:

  (1) The Ptraa is a fixed size ptr array for holding Ptra.
      In that respect, it is different from other pointer arrays, which
      are extensible and grow using the *Add*() functions.
  (2) In general, the Ptra ptrs in the Ptraa can be randomly occupied.
      A typical usage is to allow an O(n) horizontal sort of Pix,
      where the size of the Ptra array is the width of the image,
      and each Ptra is an array of all the Pix at a specific x location.

Definition in file ptra.c.

Function Documentation

L_PTRA* ptraCreate ( l_int32 n )

ptraCreate()

Input: size of ptr array to be alloc'd (0 for default) Return: pa, or null on error

Definition at line 129 of file ptra.c.

References L_Ptra::array, CALLOC, ERROR_PTR, L_Ptra::imax, INITIAL_PTR_ARRAYSIZE, L_Ptra::nactual, L_Ptra::nalloc, NULL, and PROCNAME.

Referenced by BoxaSortTest(), convertSegmentedFilesToPdf(), CopyPtras(), main(), MakePtrasFromPixa(), numaGetBinSortIndex(), pdfdataCreate(), pmsCreate(), ptraaFlattenToPtra(), saConcatenatePdfToData(), and saConvertFilesToPdfData().

void ptraDestroy	(	L_PTRA **	ppa,
		l_int32	freeflag,
		l_int32	warnflag
	)

ptraDestroy()

Input: &ptra (<to be="" nulled>="">) freeflag (TRUE to free each remaining item in the array) warnflag (TRUE to warn if any remaining items are not destroyed) Return: void

Notes: (1) If == TRUE, frees each item in the array. (2) If == FALSE and warnflag == TRUE, and there are items on the array, this gives a warning and destroys the array. If these items are not owned elsewhere, this will cause a memory leak of all the items that were on the array. So if the items are not owned elsewhere and require their own destroy function, they must be destroyed before the ptra. (3) If warnflag == FALSE, no warnings will be issued. This is useful if the items are owned elsewhere, such as a PixMemoryStore(). (4) To destroy the ptra, we destroy the ptr array, then the ptra, and then null the contents of the input ptr.

Definition at line 174 of file ptra.c.

References L_Ptra::array, FREE, L_Ptra::imax, L_NO_COMPACTION, L_WARNING, L_WARNING_INT, NULL, PROCNAME, ptraGetActualCount(), and ptraRemove().

Referenced by BoxaSortTest(), convertSegmentedFilesToPdf(), main(), numaGetBinSortIndex(), pdfdataDestroy(), ptraaDestroy(), ptraaFlattenToPtra(), saConcatenatePdfToData(), and saConvertFilesToPdfData().

l_int32 ptraAdd	(	L_PTRA *	pa,
		void *	item
	)

ptraAdd()

Input: ptra item (generic ptr to a struct) Return: 0 if OK, 1 on error

Notes: (1) This adds the element to the next location beyond imax, which is the largest occupied ptr in the array. This is what you expect from a stack, where all ptrs up to and including imax are occupied, but here the occuption of items in the array is entirely arbitrary.

Definition at line 229 of file ptra.c.

References L_Ptra::array, ERROR_INT, L_Ptra::imax, L_Ptra::nactual, L_Ptra::nalloc, PROCNAME, ptraExtendArray(), and ptraGetMaxIndex().

Referenced by BoxaSortTest(), convertSegmentedFilesToPdf(), CopyPtras(), main(), MakePtrasFromPixa(), pixConvertToPdfData(), pmsCreate(), pmsCustomDealloc(), ptraJoin(), saConcatenatePdfToData(), and saConvertFilesToPdfData().

l_int32 ptraExtendArray ( L_PTRA * pa )

ptraExtendArray()

Input: ptra Return: 0 if OK, 1 on error

Definition at line 258 of file ptra.c.

References L_Ptra::array, ERROR_INT, L_Ptra::nalloc, NULL, PROCNAME, and reallocNew().

Referenced by ptraAdd(), and ptraInsert().

l_int32 ptraInsert	(	L_PTRA *	pa,
		l_int32	index,
		void *	item,
		l_int32	shiftflag
	)

ptraInsert()

Input: ptra index (location in ptra to insert new value) item (generic ptr to a struct; can be null) shiftflag (L_AUTO_DOWNSHIFT, L_MIN_DOWNSHIFT, L_FULL_DOWNSHIFT) Return: 0 if OK, 1 on error

Notes: (1) This checks first to see if the location is valid, and then if there is presently an item there. If there is not, it is simply inserted into that location. (2) If there is an item at the insert location, items must be moved down to make room for the insert. In the downward shift there are three options, given by .

If == L_AUTO_DOWNSHIFT, a decision is made whether, in a cascade of items, to downshift a minimum amount or for all items above . The decision is based on the expectation of finding holes (null ptrs) between and the bottom of the array. Assuming the holes are distributed uniformly, if 2 or more holes are expected, we do a minimum shift.
If == L_MIN_DOWNSHIFT, the downward shifting cascade of items progresses a minimum amount, until the first empty slot is reached. This mode requires some computation before the actual shifting is done.
If == L_FULL_DOWNSHIFT, a shifting cascade is performed where pa[i] --> pa[i + 1] for all i >= index. Then, the item is inserted at pa[index]. (3) If you are not using L_AUTO_DOWNSHIFT, the rule of thumb is to use L_FULL_DOWNSHIFT if the array is compacted (each element points to an item), and to use L_MIN_DOWNSHIFT if there are a significant number of null pointers. There is no penalty to using L_MIN_DOWNSHIFT for a compacted array, however, because the full shift is required and we don't do the O(n) computation to look for holes. (4) This should not be used repeatedly on large arrays, because the function is generally O(n). (5) However, it can be used repeatedly if we start with an empty ptr array and insert only once at each location. For example, you can support an array of Numa, where at each ptr location you store either 0 or 1 Numa, and the Numa can be added randomly to the ptr array.

Definition at line 321 of file ptra.c.

References L_Ptra::array, ERROR_INT, L_Ptra::imax, L_AUTO_DOWNSHIFT, L_FULL_DOWNSHIFT, L_MIN_DOWNSHIFT, L_Ptra::nactual, L_Ptra::nalloc, NULL, PROCNAME, ptraExtendArray(), and ptraGetMaxIndex().

Referenced by BoxaSortTest(), main(), numaGetBinSortIndex(), and ptraSwap().

void* ptraGetHandle	(	L_PTRA *	pa,
		l_int32	index
	)

ptraGetHandle()

Input: ptra index (element to be retrieved) Return: item, or null on error

Notes: (1) This returns a ptr to the item. You must cast it to the type of item. Do not destroy it; the item belongs to the Ptra. (2) This can access all possible items on the ptr array. If an item doesn't exist, it returns null.

Definition at line 413 of file ptra.c.

References L_Ptra::array, ERROR_PTR, L_Ptra::nalloc, NULL, and PROCNAME.

Referenced by BoxaSortTest(), numaGetBinSortIndex(), pdfdataGetCid(), and ptraConcatenatePdfToData().

void* ptraRemove	(	L_PTRA *	pa,
		l_int32	index,
		l_int32	flag
	)

ptraRemove()

Input: ptra index (element to be removed) flag (L_NO_COMPACTION, L_COMPACTION) Return: item, or null on error

Notes: (1) If flag == L_NO_COMPACTION, this removes the item and nulls the ptr on the array. If it takes the last item in the array, pa->n is reduced to the next item. (2) If flag == L_COMPACTION, this compacts the array for for all i >= index. It should not be used repeatedly on large arrays, because compaction is O(n). (3) The ability to remove without automatic compaction allows removal with cost O(1).

Definition at line 447 of file ptra.c.

References L_Ptra::array, ERROR_PTR, L_Ptra::imax, L_COMPACTION, L_Ptra::nactual, NULL, PROCNAME, and ptraGetMaxIndex().

Referenced by BoxaSortTest(), convertSegmentedFilesToPdf(), main(), numaGetBinSortIndex(), pdfdataDestroy(), ptraConcatenatePdfToData(), ptraDestroy(), ptraJoin(), ptraRemoveLast(), ptraSwap(), ReconstructPixa1(), ReconstructPixa2(), saConcatenatePdfToData(), and saConvertFilesToPdfData().

void* ptraRemoveLast ( L_PTRA * pa )

ptraRemoveLast()

Input: ptra Return: item, or null on error or if the array is empty

Definition at line 497 of file ptra.c.

References ERROR_PTR, L_NO_COMPACTION, NULL, PROCNAME, ptraGetMaxIndex(), and ptraRemove().

Referenced by pmsCustomAlloc().

void* ptraReplace	(	L_PTRA *	pa,
		l_int32	index,
		void *	item,
		l_int32	freeflag
	)

ptraReplace()

Input: ptra index (element to be replaced) item (new generic ptr to a struct; can be null) freeflag (TRUE to free old item; FALSE to return it) Return: item (old item, if it exists and is not freed), or null on error

Definition at line 526 of file ptra.c.

References L_Ptra::array, ERROR_PTR, FALSE, FREE, L_Ptra::nactual, NULL, PROCNAME, and ptraGetMaxIndex().

Referenced by ptraSwap().

l_int32 ptraSwap	(	L_PTRA *	pa,
		l_int32	index1,
		l_int32	index2
	)

ptraSwap()

Input: ptra index1 index2 Return: 0 if OK, 1 on error

Definition at line 567 of file ptra.c.

References ERROR_INT, FALSE, L_MIN_DOWNSHIFT, L_NO_COMPACTION, PROCNAME, ptraGetMaxIndex(), ptraInsert(), ptraRemove(), and ptraReplace().

Referenced by main(), and ptraReverse().

l_int32 ptraCompactArray ( L_PTRA * pa )

ptraCompactArray()

Input: ptra Return: 0 if OK, 1 on error

Notes: (1) This compacts the items on the array, filling any empty ptrs. (2) This does not change the size of the array of ptrs.

Definition at line 602 of file ptra.c.

References L_Ptra::array, ERROR_INT, L_Ptra::imax, L_ERROR_INT, PROCNAME, ptraGetActualCount(), and ptraGetMaxIndex().

Referenced by main(), ptraConcatenatePdfToData(), and ReconstructPixa2().

l_int32 ptraReverse ( L_PTRA * pa )

ptraReverse()

Input: ptra Return: 0 if OK, 1 on error

Definition at line 637 of file ptra.c.

References ERROR_INT, PROCNAME, ptraGetMaxIndex(), and ptraSwap().

l_int32 ptraJoin	(	L_PTRA *	pa1,
		L_PTRA *	pa2
	)

ptraJoin()

Input: ptra1 (add to this one) ptra2 (appended to ptra1, and emptied of items; can be null) Return: 0 if OK, 1 on error

Definition at line 661 of file ptra.c.

References ERROR_INT, L_NO_COMPACTION, PROCNAME, ptraAdd(), ptraGetMaxIndex(), and ptraRemove().

Referenced by ptraaFlattenToPtra().

l_int32 ptraGetMaxIndex	(	L_PTRA *	pa,
		l_int32 *	pmaxindex
	)

ptraGetMaxIndex()

Input: ptra &maxindex (<return> index of last item in the array); Return: 0 if OK; 1 on error

Notes: (1) The largest index to an item in the array is . is one less than the number of items that would be in the array if there were no null pointers between 0 and - 1. However, because the internal ptr array need not be compacted, there may be null pointers at indices below ; for example, if items have been removed. (2) When an item is added to the end of the array, it goes into pa->array[maxindex + 1], and maxindex is then incremented by 1. (3) If there are no items in the array, this returns = -1.

Definition at line 709 of file ptra.c.

References ERROR_INT, L_Ptra::imax, and PROCNAME.

Referenced by BoxaSortTest(), CopyPtras(), main(), numaGetBinSortIndex(), ptraAdd(), ptraCompactArray(), ptraInsert(), ptraJoin(), ptraRemove(), ptraRemoveLast(), ptraReplace(), ptraReverse(), ptraSwap(), ReconstructPixa1(), and ReconstructPixa2().

l_int32 ptraGetActualCount	(	L_PTRA *	pa,
		l_int32 *	pcount
	)

ptraGetActualCount()

Input: ptra &count (<return> actual number of items on the ptr array) Return: 0 if OK; 1 on error

Notes: (1) The actual number of items on the ptr array, pa->nactual, will be smaller than pa->n if the array is not compacted.

Definition at line 735 of file ptra.c.

References ERROR_INT, L_Ptra::nactual, and PROCNAME.

Referenced by BoxaSortTest(), convertSegmentedFilesToPdf(), main(), ptraCompactArray(), ptraConcatenatePdfToData(), ptraDestroy(), ReconstructPixa1(), ReconstructPixa2(), saConcatenatePdfToData(), and saConvertFilesToPdfData().

void* ptraGetPtrToItem	(	L_PTRA *	pa,
		l_int32	index
	)

ptraGetPtrToItem()

Input: ptra index (element to fetch pointer to) Return: item (just a pointer to it)

Notes: (1) The item remains on the Ptra and is 'owned' by it, so the item must not be destroyed.

Definition at line 762 of file ptra.c.

References L_Ptra::array, ERROR_PTR, L_Ptra::imax, NULL, and PROCNAME.

Referenced by CopyPtras().

L_PTRAA* ptraaCreate ( l_int32 n )

ptraaCreate()

Input: size of ptr array to be alloc'd Return: paa, or null on error

Notes: (1) The ptraa is generated with a fixed size, that can not change. The ptra can be generated and inserted randomly into this array.

Definition at line 790 of file ptra.c.

References CALLOC, ERROR_PTR, L_Ptraa::nalloc, NULL, PixMemoryStore::paa, PROCNAME, and L_Ptraa::ptra.

Referenced by BoxaSortTest(), and pmsCreate().

void ptraaDestroy	(	L_PTRAA **	ppaa,
		l_int32	freeflag,
		l_int32	warnflag
	)

ptraaDestroy()

Input: &paa (<to be="" nulled>="">) freeflag (TRUE to free each remaining item in each ptra) warnflag (TRUE to warn if any remaining items are not destroyed) Return: void

Notes: (1) See ptraDestroy() for use of and . (2) To destroy the ptraa, we destroy each ptra, then the ptr array, then the ptraa, and then null the contents of the input ptr.

Definition at line 823 of file ptra.c.

References FREE, L_REMOVE, L_WARNING, NULL, PixMemoryStore::paa, PROCNAME, L_Ptraa::ptra, ptraaGetPtra(), ptraaGetSize(), and ptraDestroy().

Referenced by BoxaSortTest(), and pmsDestroy().

l_int32 ptraaGetSize	(	L_PTRAA *	paa,
		l_int32 *	psize
	)

ptraaGetSize()

Input: ptraa &size (<return> size of ptr array) Return: 0 if OK; 1 on error

Definition at line 864 of file ptra.c.

References ERROR_INT, L_Ptraa::nalloc, and PROCNAME.

Referenced by ptraaDestroy(), ptraaFlattenToPtra(), ptraaGetPtra(), and ptraaInsertPtra().

l_int32 ptraaInsertPtra	(	L_PTRAA *	paa,
		l_int32	index,
		L_PTRA *	pa
	)

ptraaInsertPtra()

Input: ptraa index (location in array for insertion) ptra (to be inserted) Return: 0 if OK; 1 on error

Notes: (1) Caller should check return value. On success, the Ptra is inserted in the Ptraa and is owned by it. However, on error, the Ptra remains owned by the caller.

Definition at line 893 of file ptra.c.

References ERROR_INT, NULL, PROCNAME, L_Ptraa::ptra, and ptraaGetSize().

Referenced by BoxaSortTest(), and pmsCreate().

L_PTRA* ptraaGetPtra	(	L_PTRAA *	paa,
		l_int32	index,
		l_int32	accessflag
	)

ptraaGetPtra()

Input: ptraa index (location in array) accessflag (L_HANDLE_ONLY, L_REMOVE) Return: ptra (at index location), or NULL on error or if there is no ptra there.

Notes: (1) This returns the ptra ptr. If == L_HANDLE_ONLY, the ptra is left on the ptraa. If == L_REMOVE, the ptr in the ptraa is set to NULL, and the caller is responsible for disposing of the ptra (either putting it back on the ptraa, or destroying it). (2) This returns NULL if there is no Ptra at the index location.

Definition at line 934 of file ptra.c.

References ERROR_PTR, L_HANDLE_ONLY, L_REMOVE, NULL, PROCNAME, L_Ptraa::ptra, and ptraaGetSize().

Referenced by BoxaSortTest(), pmsCustomAlloc(), pmsCustomDealloc(), ptraaDestroy(), and ptraaFlattenToPtra().

L_PTRA* ptraaFlattenToPtra ( L_PTRAA * paa )

ptraaFlattenToPtra()

Input: ptraa Return: ptra, or null on error

Notes: (1) This 'flattens' the ptraa to a ptra, taking the items in each ptra, in order, starting with the first ptra, etc. (2) As a side-effect, the ptra are all removed from the ptraa and destroyed, leaving an empty ptraa.

Definition at line 974 of file ptra.c.

References ERROR_PTR, FALSE, L_REMOVE, NULL, PROCNAME, ptraaGetPtra(), ptraaGetSize(), ptraCreate(), ptraDestroy(), and ptraJoin().

Referenced by BoxaSortTest().

NUMA* numaGetBinSortIndex	(	NUMA *	nas,
		l_int32	sortorder
	)

numaGetBinSortIndex()

Input: na (of non-negative integers with a max that is typically less than 50,000) sortorder (L_SORT_INCREASING or L_SORT_DECREASING) Return: na (sorted), or null on error

Notes: (1) This creates an array (or lookup table) that gives the sorted position of the elements in the input Numa. (2) Because it uses a bin sort with buckets of size 1, it is not appropriate for sorting either small arrays or arrays containing very large integer values. For such arrays, use a standard general sort function like numaGetSortIndex().

Definition at line 1018 of file ptra.c.

References ERROR_PTR, FALSE, L_MIN_DOWNSHIFT, L_NO_COMPACTION, L_SORT_DECREASING, L_SORT_INCREASING, L_WARNING_INT, NULL, numaAddNumber(), numaCreate(), numaDestroy(), numaGetCount(), numaGetIValue(), numaGetMax(), numaJoin(), PROCNAME, ptraCreate(), ptraDestroy(), ptraGetHandle(), ptraGetMaxIndex(), ptraInsert(), ptraRemove(), and size.

Referenced by boxaBinSort(), and pixaBinSort().

Variable Documentation

const l_int32 INITIAL_PTR_ARRAYSIZE = 20 [static]

Definition at line 116 of file ptra.c.

Referenced by ptraCreate().

ptra.c File Reference

Functions

Variables

Detailed Description

Function Documentation

Variable Documentation