ptra.c

Go to the documentation of this file.

/*====================================================================*
 -  Copyright (C) 2001 Leptonica.  All rights reserved.
 -
 -  Redistribution and use in source and binary forms, with or without
 -  modification, are permitted provided that the following conditions
 -  are met:
 -  1. Redistributions of source code must retain the above copyright
 -     notice, this list of conditions and the following disclaimer.
 -  2. Redistributions in binary form must reproduce the above
 -     copyright notice, this list of conditions and the following
 -     disclaimer in the documentation and/or other materials
 -     provided with the distribution.
 -
 -  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 -  ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 -  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 -  A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL ANY
 -  CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 -  EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 -  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 -  PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 -  OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 -  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 -  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *====================================================================*/
 
#ifdef HAVE_CONFIG_H
#include <config_auto.h>
#endif  /* HAVE_CONFIG_H */
 
#include "allheaders.h"
 
    /* Bounds on initial array size */
LEPT_DLL const l_uint32  MaxInitPtraSize = 1000001;
static const l_int32 DefaultInitPtraSize = 20;      
    /* Static function */
static l_int32 ptraExtendArray(L_PTRA *pa);
 
/*--------------------------------------------------------------------------*
 *                       Ptra creation and destruction                      *
 *--------------------------------------------------------------------------*/
L_PTRA *
ptraCreate(l_int32  n)
{
L_PTRA  *pa;
 
    if (n > (l_int32)MaxInitPtraSize) {
        L_ERROR("n = %d > maxsize = %d\n", __func__, n, MaxInitPtraSize);
        return NULL;
    }
    if (n <= 0) n = DefaultInitPtraSize;
 
    pa = (L_PTRA *)LEPT_CALLOC(1, sizeof(L_PTRA));
    if ((pa->array = (void **)LEPT_CALLOC(n, sizeof(void *))) == NULL) {
        ptraDestroy(&pa, 0, 0);
        return (L_PTRA *)ERROR_PTR("ptr array not made", __func__, NULL);
    }
    pa->nalloc = n;
    pa->imax = -1;
    pa->nactual = 0;
    return pa;
}
 
 
void
ptraDestroy(L_PTRA  **ppa,
            l_int32   freeflag,
            l_int32   warnflag)
{
l_int32  i, nactual;
void    *item;
L_PTRA  *pa;
 
    if (ppa == NULL) {
        L_WARNING("ptr address is NULL\n", __func__);
        return;
    }
    if ((pa = *ppa) == NULL)
        return;
 
    ptraGetActualCount(pa, &nactual);
    if (nactual > 0) {
        if (freeflag) {
            for (i = 0; i <= pa->imax; i++) {
                if ((item = ptraRemove(pa, i, L_NO_COMPACTION)) != NULL)
                    LEPT_FREE(item);
            }
        } else if (warnflag) {
            L_WARNING("potential memory leak of %d items in ptra\n",
                      __func__, nactual);
        }
    }
 
    LEPT_FREE(pa->array);
    LEPT_FREE(pa);
    *ppa = NULL;
}
 
 
/*--------------------------------------------------------------------------*
 *               Add/insert/remove/replace generic ptr object               *
 *--------------------------------------------------------------------------*/
l_ok
ptraAdd(L_PTRA  *pa,
        void    *item)
{
l_int32  imax;
 
    if (!pa)
        return ERROR_INT("pa not defined", __func__, 1);
    if (!item)
        return ERROR_INT("item not defined", __func__, 1);
 
    ptraGetMaxIndex(pa, &imax);
    if (imax >= pa->nalloc - 1 && ptraExtendArray(pa))
        return ERROR_INT("extension failure", __func__, 1);
    pa->array[imax + 1] = (void *)item;
    pa->imax++;
    pa->nactual++;
    return 0;
}
 
 
static l_int32
ptraExtendArray(L_PTRA  *pa)
{
    if (!pa)
        return ERROR_INT("pa not defined", __func__, 1);
 
    if ((pa->array = (void **)reallocNew((void **)&pa->array,
                                sizeof(void *) * pa->nalloc,
                                2 * sizeof(void *) * pa->nalloc)) == NULL)
            return ERROR_INT("new ptr array not returned", __func__, 1);
 
    pa->nalloc *= 2;
    return 0;
}
 
 
l_ok
ptraInsert(L_PTRA  *pa,
           l_int32  index,
           void    *item,
           l_int32  shiftflag)
{
l_int32    i, ihole, imax;
l_float32  nexpected;
 
    if (!pa)
        return ERROR_INT("pa not defined", __func__, 1);
    if (index < 0 || index > pa->nalloc)
        return ERROR_INT("index not in [0 ... nalloc]", __func__, 1);
    if (shiftflag != L_AUTO_DOWNSHIFT && shiftflag != L_MIN_DOWNSHIFT &&
        shiftflag != L_FULL_DOWNSHIFT)
        return ERROR_INT("invalid shiftflag", __func__, 1);
 
    if (item) pa->nactual++;
    if (index == pa->nalloc) {  /* can happen when index == n */
        if (ptraExtendArray(pa))
            return ERROR_INT("extension failure", __func__, 1);
    }
 
        /* We are inserting into a hole or adding to the end of the array.
         * No existing items are moved. */
    ptraGetMaxIndex(pa, &imax);
    if (pa->array[index] == NULL) {
        pa->array[index] = item;
        if (item && index > imax)  /* new item put beyond max so far */
            pa->imax = index;
        return 0;
    }
 
        /* We are inserting at the location of an existing item,
         * forcing the existing item and those below to shift down.
         * First, extend the array automatically if the last element
         * (nalloc - 1) is occupied (imax).  This may not be necessary
         * in every situation, but only an anomalous sequence of insertions
         * into the array would cause extra ptr allocation.  */
    if (imax >= pa->nalloc - 1 && ptraExtendArray(pa))
        return ERROR_INT("extension failure", __func__, 1);
 
        /* If there are no holes, do a full downshift.
         * Otherwise, if L_AUTO_DOWNSHIFT, use the expected number
         * of holes between index and n to determine the shift mode */
    if (imax + 1 == pa->nactual) {
        shiftflag = L_FULL_DOWNSHIFT;
    } else if (shiftflag == L_AUTO_DOWNSHIFT) {
        if (imax < 10) {
            shiftflag = L_FULL_DOWNSHIFT;  /* no big deal */
        } else {
            nexpected = (l_float32)(imax - pa->nactual) *
                         (l_float32)((imax - index) / imax);
            shiftflag = (nexpected > 2.0) ? L_MIN_DOWNSHIFT : L_FULL_DOWNSHIFT;
        }
    }
 
    if (shiftflag == L_MIN_DOWNSHIFT) {  /* run down looking for a hole */
        for (ihole = index + 1; ihole <= imax; ihole++) {
             if (pa->array[ihole] == NULL)
                 break;
        }
    } else {  /* L_FULL_DOWNSHIFT */
        ihole = imax + 1;
    }
 
    for (i = ihole; i > index; i--)
        pa->array[i] = pa->array[i - 1];
    pa->array[index] = (void *)item;
    if (ihole == imax + 1)  /* the last item was shifted down */
        pa->imax++;
 
    return 0;
}
 
 
void *
ptraRemove(L_PTRA  *pa,
           l_int32  index,
           l_int32  flag)
{
l_int32  i, imax, fromend, icurrent;
void    *item;
 
    if (!pa)
        return (void *)ERROR_PTR("pa not defined", __func__, NULL);
    ptraGetMaxIndex(pa, &imax);
    if (index < 0 || index > imax)
        return (void *)ERROR_PTR("index not in [0 ... imax]", __func__, NULL);
 
    item = pa->array[index];
    if (item)
        pa->nactual--;
    pa->array[index] = NULL;
 
        /* If we took the last item, need to reduce pa->n */
    fromend = (index == imax);
    if (fromend) {
        for (i = index - 1; i >= 0; i--) {
            if (pa->array[i])
                break;
        }
        pa->imax = i;
    }
 
        /* Compact from index to the end of the array */
    if (!fromend && flag == L_COMPACTION) {
        for (icurrent = index, i = index + 1; i <= imax; i++) {
            if (pa->array[i])
                pa->array[icurrent++] = pa->array[i];
        }
        pa->imax = icurrent - 1;
    }
    return item;
}
 
 
void *
ptraRemoveLast(L_PTRA  *pa)
{
l_int32  imax;
 
    if (!pa)
        return (void *)ERROR_PTR("pa not defined", __func__, NULL);
 
        /* Remove the last item in the array.  No compaction is required. */
    ptraGetMaxIndex(pa, &imax);
    if (imax >= 0)
        return ptraRemove(pa, imax, L_NO_COMPACTION);
    else  /* empty */
        return NULL;
}
 
 
void *
ptraReplace(L_PTRA  *pa,
            l_int32  index,
            void    *item,
            l_int32  freeflag)
{
l_int32  imax;
void    *olditem;
 
    if (!pa)
        return (void *)ERROR_PTR("pa not defined", __func__, NULL);
    ptraGetMaxIndex(pa, &imax);
    if (index < 0 || index > imax)
        return (void *)ERROR_PTR("index not in [0 ... imax]", __func__, NULL);
 
    olditem = pa->array[index];
    pa->array[index] = item;
    if (!item && olditem)
        pa->nactual--;
    else if (item && !olditem)
        pa->nactual++;
 
    if (freeflag == FALSE)
        return olditem;
 
    if (olditem)
        LEPT_FREE(olditem);
    return NULL;
}
 
 
l_ok
ptraSwap(L_PTRA  *pa,
         l_int32  index1,
         l_int32  index2)
{
l_int32  imax;
void    *item;
 
    if (!pa)
        return ERROR_INT("pa not defined", __func__, 1);
    if (index1 == index2)
        return 0;
    ptraGetMaxIndex(pa, &imax);
    if (index1 < 0 || index1 > imax || index2 < 0 || index2 > imax)
        return ERROR_INT("invalid index: not in [0 ... imax]", __func__, 1);
 
    item = ptraRemove(pa, index1, L_NO_COMPACTION);
    item = ptraReplace(pa, index2, item, FALSE);
    ptraInsert(pa, index1, item, L_MIN_DOWNSHIFT);
    return 0;
}
 
 
l_ok
ptraCompactArray(L_PTRA  *pa)
{
l_int32  i, imax, nactual, index;
 
    if (!pa)
        return ERROR_INT("pa not defined", __func__, 1);
    ptraGetMaxIndex(pa, &imax);
    ptraGetActualCount(pa, &nactual);
    if (imax + 1 == nactual) return 0;
 
        /* Compact the array */
    for (i = 0, index = 0; i <= imax; i++) {
        if (pa->array[i])
             pa->array[index++] = pa->array[i];
    }
    pa->imax = index - 1;
    if (nactual != index)
        L_ERROR("index = %d; != nactual\n", __func__, index);
 
    return 0;
}
 
 
/*----------------------------------------------------------------------*
 *                        Other array operations                        *
 *----------------------------------------------------------------------*/
l_ok
ptraReverse(L_PTRA  *pa)
{
l_int32  i, imax;
 
    if (!pa)
        return ERROR_INT("pa not defined", __func__, 1);
    ptraGetMaxIndex(pa, &imax);
 
    for (i = 0; i < (imax + 1) / 2; i++)
        ptraSwap(pa, i, imax - i);
    return 0;
}
 
 
l_ok
ptraJoin(L_PTRA  *pa1,
         L_PTRA  *pa2)
{
l_int32  i, imax;
void    *item;
 
    if (!pa1)
        return ERROR_INT("pa1 not defined", __func__, 1);
    if (!pa2)
        return 0;
 
    ptraGetMaxIndex(pa2, &imax);
    for (i = 0; i <= imax; i++) {
        item = ptraRemove(pa2, i, L_NO_COMPACTION);
        ptraAdd(pa1, item);
    }
 
    return 0;
}
 
 
 
/*----------------------------------------------------------------------*
 *                        Simple ptra accessors                         *
 *----------------------------------------------------------------------*/
l_ok
ptraGetMaxIndex(L_PTRA   *pa,
                l_int32  *pmaxindex)
{
    if (!pa)
        return ERROR_INT("pa not defined", __func__, 1);
    if (!pmaxindex)
        return ERROR_INT("&maxindex not defined", __func__, 1);
    *pmaxindex = pa->imax;
    return 0;
}
 
 
l_ok
ptraGetActualCount(L_PTRA   *pa,
                   l_int32  *pcount)
{
    if (!pa)
        return ERROR_INT("pa not defined", __func__, 1);
    if (!pcount)
        return ERROR_INT("&count not defined", __func__, 1);
    *pcount = pa->nactual;
 
    return 0;
}
 
 
void *
ptraGetPtrToItem(L_PTRA  *pa,
                 l_int32  index)
{
    if (!pa)
        return (void *)ERROR_PTR("pa not defined", __func__, NULL);
    if (index < 0 || index >= pa->nalloc)
        return (void *)ERROR_PTR("index not in [0 ... nalloc-1]",
                                 __func__, NULL);
 
    return pa->array[index];
}
 
 
/*--------------------------------------------------------------------------*
 *                      Ptraa creation and destruction                      *
 *--------------------------------------------------------------------------*/
L_PTRAA *
ptraaCreate(l_int32  n)
{
L_PTRAA  *paa;
 
    if (n <= 0)
        return (L_PTRAA *)ERROR_PTR("n must be > 0", __func__, NULL);
 
    paa = (L_PTRAA *)LEPT_CALLOC(1, sizeof(L_PTRAA));
    if ((paa->ptra = (L_PTRA **)LEPT_CALLOC(n, sizeof(L_PTRA *))) == NULL) {
        ptraaDestroy(&paa, 0, 0);
        return (L_PTRAA *)ERROR_PTR("ptr array not made", __func__, NULL);
    }
    paa->nalloc = n;
    return paa;
}
 
 
void
ptraaDestroy(L_PTRAA  **ppaa,
             l_int32    freeflag,
             l_int32    warnflag)
{
l_int32   i, n;
L_PTRA   *pa;
L_PTRAA  *paa;
 
    if (ppaa == NULL) {
        L_WARNING("ptr address is NULL\n", __func__);
        return;
    }
    if ((paa = *ppaa) == NULL)
        return;
 
    ptraaGetSize(paa, &n);
    for (i = 0; i < n; i++) {
        pa = ptraaGetPtra(paa, i, L_REMOVE);
        ptraDestroy(&pa, freeflag, warnflag);
    }
 
    LEPT_FREE(paa->ptra);
    LEPT_FREE(paa);
    *ppaa = NULL;
}
 
 
/*--------------------------------------------------------------------------*
 *                             Ptraa accessors                              *
 *--------------------------------------------------------------------------*/
l_ok
ptraaGetSize(L_PTRAA  *paa,
             l_int32  *psize)
{
    if (!paa)
        return ERROR_INT("paa not defined", __func__, 1);
    if (!psize)
        return ERROR_INT("&size not defined", __func__, 1);
    *psize = paa->nalloc;
 
    return 0;
}
 
 
l_ok
ptraaInsertPtra(L_PTRAA  *paa,
                l_int32   index,
                L_PTRA   *pa)
{
l_int32  n;
 
    if (!paa)
        return ERROR_INT("paa not defined", __func__, 1);
    if (!pa)
        return ERROR_INT("pa not defined", __func__, 1);
    ptraaGetSize(paa, &n);
    if (index < 0 || index >= n)
        return ERROR_INT("invalid index", __func__, 1);
    if (paa->ptra[index] != NULL)
        return ERROR_INT("ptra already stored at index", __func__, 1);
 
    paa->ptra[index] = pa;
    return 0;
}
 
 
L_PTRA *
ptraaGetPtra(L_PTRAA  *paa,
             l_int32   index,
             l_int32   accessflag)
{
l_int32  n;
L_PTRA  *pa;
 
    if (!paa)
        return (L_PTRA *)ERROR_PTR("paa not defined", __func__, NULL);
    ptraaGetSize(paa, &n);
    if (index < 0 || index >= n)
        return (L_PTRA *)ERROR_PTR("invalid index", __func__, NULL);
    if (accessflag != L_HANDLE_ONLY && accessflag != L_REMOVE)
        return (L_PTRA *)ERROR_PTR("invalid accessflag", __func__, NULL);
 
    pa = paa->ptra[index];
    if (accessflag == L_REMOVE)
        paa->ptra[index] = NULL;
    return pa;
}
 
 
/*--------------------------------------------------------------------------*
 *                             Ptraa conversion                             *
 *--------------------------------------------------------------------------*/
L_PTRA *
ptraaFlattenToPtra(L_PTRAA  *paa)
{
l_int32  i, n;
L_PTRA    *pat, *pad;
 
    if (!paa)
        return (L_PTRA *)ERROR_PTR("paa not defined", __func__, NULL);
 
    pad = ptraCreate(0);
    ptraaGetSize(paa, &n);
    for (i = 0; i < n; i++) {
        pat = ptraaGetPtra(paa, i, L_REMOVE);
        if (!pat) continue;
        ptraJoin(pad, pat);
        ptraDestroy(&pat, FALSE, FALSE);  /* they're all empty */
    }
 
    return pad;
}