tesseract-5.0.zip

/*====================================================================* - 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. *====================================================================*/ /*! * \file heap.c * <pre> * * Create/Destroy L_Heap * L_HEAP *lheapCreate() * void *lheapDestroy() * * Operations to add/remove to/from the heap * l_int32 lheapAdd() * static l_int32 lheapExtendArray() * void *lheapRemove() * * Heap operations * l_int32 lheapSwapUp() * l_int32 lheapSwapDown() * l_int32 lheapSort() * l_int32 lheapSortStrictOrder() * * Accessors * l_int32 lheapGetCount() * * Debug output * l_int32 lheapPrint() * * The L_Heap is useful to implement a priority queue, that is sorted * on a key in each element of the heap. The heap is an array * of nearly arbitrary structs, with a l_float32 the first field. * This field is the key on which the heap is sorted. * * Internally, we keep track of the heap size, n. The item at the * root of the heap is at the head of the array. Items are removed * from the head of the array and added to the end of the array. * When an item is removed from the head, the item at the end * of the array is moved to the head. When items are either * added or removed, it is usually necessary to swap array items * to restore the heap order. It is guaranteed that the number * of swaps does not exceed log(n). * * -------------------------- N.B. ------------------------------ * The items on the heap (or, equivalently, in the array) are cast * to void*. Their key is a l_float32, and it is REQUIRED that the * key be the first field in the struct. That allows us to get the * key by simply dereferencing the struct. Alternatively, we could * choose (but don't) to pass an application-specific comparison * function into the heap operation functions. * -------------------------- N.B. ------------------------------ * </pre> */ #include <string.h> #include "allheaders.h" static const l_int32 MIN_BUFFER_SIZE = 20; /* n'importe quoi */ static const l_int32 INITIAL_BUFFER_ARRAYSIZE = 128; /* n'importe quoi */ #define SWAP_ITEMS(i, j) { void *tempitem = lh->array[(i)]; \ lh->array[(i)] = lh->array[(j)]; \ lh->array[(j)] = tempitem; } /* Static function */ static l_int32 lheapExtendArray(L_HEAP *lh); /*--------------------------------------------------------------------------* * L_Heap create/destroy * *--------------------------------------------------------------------------*/ /*! * \brief lheapCreate() * * \param[in] nalloc size of ptr array to be alloc'd 0 for default * \param[in] direction L_SORT_INCREASING, L_SORT_DECREASING * \return lheap, or NULL on error */ L_HEAP * lheapCreate(l_int32 nalloc, l_int32 direction) { L_HEAP *lh; PROCNAME("lheapCreate"); if (nalloc < MIN_BUFFER_SIZE) nalloc = MIN_BUFFER_SIZE; /* Allocate ptr array and initialize counters. */ if ((lh = (L_HEAP *)LEPT_CALLOC(1, sizeof(L_HEAP))) == NULL) return (L_HEAP *)ERROR_PTR("lh not made", procName, NULL); if ((lh->array = (void **)LEPT_CALLOC(nalloc, sizeof(void *))) == NULL) { lheapDestroy(&lh, FALSE); return (L_HEAP *)ERROR_PTR("ptr array not made", procName, NULL); } lh->nalloc = nalloc; lh->n = 0; lh->direction = direction; return lh; } /*! * \brief lheapDestroy() * * \param[in,out] plh to be nulled * \param[in] freeflag TRUE to free each remaining struct in the array * \return void * * <pre> * Notes: * (1) Use freeflag == TRUE when the items in the array can be * simply destroyed using free. If those items require their * own destroy function, they must be destroyed before * calling this function, and then this function is called * with freeflag == FALSE. * (2) To destroy the lheap, we destroy the ptr array, then * the lheap, and then null the contents of the input ptr. * </pre> */ void lheapDestroy(L_HEAP **plh, l_int32 freeflag) { l_int32 i; L_HEAP *lh; PROCNAME("lheapDestroy"); if (plh == NULL) { L_WARNING("ptr address is NULL\n", procName); return; } if ((lh = *plh) == NULL) return; if (freeflag) { /* free each struct in the array */ for (i = 0; i < lh->n; i++) LEPT_FREE(lh->array[i]); } else if (lh->n > 0) { /* freeflag == FALSE but elements exist on array */ L_WARNING("memory leak of %d items in lheap!\n", procName, lh->n); } if (lh->array) LEPT_FREE(lh->array); LEPT_FREE(lh); *plh = NULL; return; } /*--------------------------------------------------------------------------* * Accessors * *--------------------------------------------------------------------------*/ /*! * \brief lheapAdd() * * \param[in] lh heap * \param[in] item to be added to the tail of the heap * \return 0 if OK, 1 on error */ l_int32 lheapAdd(L_HEAP *lh, void *item) { PROCNAME("lheapAdd"); if (!lh) return ERROR_INT("lh not defined", procName, 1); if (!item) return ERROR_INT("item not defined", procName, 1); /* If necessary, expand the allocated array by a factor of 2 */ if (lh->n >= lh->nalloc) lheapExtendArray(lh); /* Add the item */ lh->array[lh->n] = item; lh->n++; /* Restore the heap */ lheapSwapUp(lh, lh->n - 1); return 0; } /*! * \brief lheapExtendArray() * * \param[in] lh heap * \return 0 if OK, 1 on error */ static l_int32 lheapExtendArray(L_HEAP *lh) { PROCNAME("lheapExtendArray"); if (!lh) return ERROR_INT("lh not defined", procName, 1); if ((lh->array = (void **)reallocNew((void **)&lh->array, sizeof(void *) * lh->nalloc, 2 * sizeof(void *) * lh->nalloc)) == NULL) return ERROR_INT("new ptr array not returned", procName, 1); lh->nalloc = 2 * lh->nalloc; return 0; } /*! * \brief lheapRemove() * * \param[in] lh heap * \return ptr to item popped from the root of the heap, * or NUL