Leptonica 1.68
C Image Processing Library

stack.c

Go to the documentation of this file.
00001 /*====================================================================*
00002  -  Copyright (C) 2001 Leptonica.  All rights reserved.
00003  -  This software is distributed in the hope that it will be
00004  -  useful, but with NO WARRANTY OF ANY KIND.
00005  -  No author or distributor accepts responsibility to anyone for the
00006  -  consequences of using this software, or for whether it serves any
00007  -  particular purpose or works at all, unless he or she says so in
00008  -  writing.  Everyone is granted permission to copy, modify and
00009  -  redistribute this source code, for commercial or non-commercial
00010  -  purposes, with the following restrictions: (1) the origin of this
00011  -  source code must not be misrepresented; (2) modified versions must
00012  -  be plainly marked as such; and (3) this notice may not be removed
00013  -  or altered from any source or modified source distribution.
00014  *====================================================================*/
00015 
00016 
00017 /*
00018  *  stack.c
00019  *
00020  *      Generic stack
00021  *
00022  *      The lstack is an array of void * ptrs, onto which
00023  *      objects can be stored.  At any time, the number of
00024  *      stored objects is lstack->n.  The object at the bottom
00025  *      of the lstack is at array[0]; the object at the top of
00026  *      the lstack is at array[n-1].  New objects are added
00027  *      to the top of the lstack; i.e., the first available 
00028  *      location, which is at array[n].  The lstack is expanded
00029  *      by doubling, when needed.  Objects are removed
00030  *      from the top of the lstack.  When an attempt is made
00031  *      to remove an object from an empty lstack, the result is null.
00032  *
00033  *      Create/Destroy
00034  *           L_STACK   *lstackCreate()
00035  *           void       lstackDestroy()
00036  *
00037  *      Accessors
00038  *           l_int32    lstackAdd()
00039  *           void      *lstackRemove()
00040  *           l_int32    lstackExtendArray()
00041  *           l_int32    lstackGetCount()
00042  *
00043  *      Text description
00044  *           l_int32    lstackPrint()
00045  */
00046 
00047 #include <stdio.h>
00048 #include <stdlib.h>
00049 #include "allheaders.h"
00050 
00051 static const l_int32  INITIAL_PTR_ARRAYSIZE = 20;
00052 
00053 
00054 /*---------------------------------------------------------------------*
00055  *                          Create/Destroy                             *
00056  *---------------------------------------------------------------------*/
00057 /*!
00058  *  lstackCreate()
00059  *
00060  *      Input:  nalloc (initial ptr array size; use 0 for default)
00061  *      Return: lstack, or null on error
00062  */
00063 L_STACK *
00064 lstackCreate(l_int32  nalloc)
00065 {
00066 L_STACK  *lstack;
00067 
00068     PROCNAME("lstackCreate");
00069 
00070     if (nalloc <= 0)
00071         nalloc = INITIAL_PTR_ARRAYSIZE;
00072 
00073     if ((lstack = (L_STACK *)CALLOC(1, sizeof(L_STACK))) == NULL)
00074         return (L_STACK *)ERROR_PTR("lstack not made", procName, NULL);
00075 
00076     if ((lstack->array = (void **)CALLOC(nalloc, sizeof(void *))) == NULL)
00077         return (L_STACK *)ERROR_PTR("lstack array not made", procName, NULL);
00078 
00079     lstack->nalloc = nalloc;
00080     lstack->n = 0;
00081     
00082     return lstack;
00083 }
00084 
00085 
00086 /*!
00087  *  lstackDestroy()
00088  *
00089  *      Input:  &lstack (<to be nulled>)
00090  *              freeflag (TRUE to free each remaining struct in the array)
00091  *      Return: void
00092  *
00093  *  Notes:
00094  *      (1) If freeflag is TRUE, frees each struct in the array.
00095  *      (2) If freeflag is FALSE but there are elements on the array,
00096  *          gives a warning and destroys the array.  This will
00097  *          cause a memory leak of all the items that were on the lstack.
00098  *          So if the items require their own destroy function, they
00099  *          must be destroyed before the lstack.
00100  *      (3) To destroy the lstack, we destroy the ptr array, then
00101  *          the lstack, and then null the contents of the input ptr.
00102  */
00103 void
00104 lstackDestroy(L_STACK  **plstack,
00105               l_int32    freeflag)
00106 {
00107 void     *item;
00108 L_STACK  *lstack;
00109 
00110     PROCNAME("lstackDestroy");
00111 
00112     if (plstack == NULL) {
00113         L_WARNING("ptr address is NULL", procName);
00114         return;
00115     }
00116     if ((lstack = *plstack) == NULL)
00117         return;
00118 
00119     if (freeflag) {
00120         while(lstack->n > 0) {
00121             item = lstackRemove(lstack);
00122             FREE(item);
00123         }
00124     }
00125     else if (lstack->n > 0)
00126         L_WARNING_INT("memory leak of %d items in lstack", procName, lstack->n);
00127 
00128     if (lstack->auxstack)
00129         lstackDestroy(&lstack->auxstack, freeflag);
00130 
00131     if (lstack->array)
00132         FREE(lstack->array);
00133     FREE(lstack);
00134     *plstack = NULL;
00135 }
00136 
00137 
00138 
00139 /*---------------------------------------------------------------------*
00140  *                               Accessors                             *
00141  *---------------------------------------------------------------------*/
00142 /*!
00143  *  lstackAdd()
00144  *
00145  *      Input:  lstack
00146  *              item to be added to the lstack
00147  *      Return: 0 if OK; 1 on error.
00148  */
00149 l_int32
00150 lstackAdd(L_STACK  *lstack,
00151           void     *item)
00152 {
00153     PROCNAME("lstackAdd");
00154 
00155     if (!lstack)
00156         return ERROR_INT("lstack not defined", procName, 1);
00157     if (!item)
00158         return ERROR_INT("item not defined", procName, 1);
00159 
00160         /* Do we need to extend the array? */
00161     if (lstack->n >= lstack->nalloc)
00162         lstackExtendArray(lstack);
00163 
00164         /* Store the new pointer */
00165     lstack->array[lstack->n] = (void *)item;
00166     lstack->n++;
00167 
00168     return 0;
00169 }
00170 
00171 
00172 /*!
00173  *  lstackRemove()
00174  *
00175  *      Input:  lstack 
00176  *      Return: ptr to item popped from the top of the lstack,
00177  *              or null if the lstack is empty or on error
00178  */
00179 void *
00180 lstackRemove(L_STACK  *lstack)
00181 {
00182 void  *item;
00183 
00184     PROCNAME("lstackRemove");
00185 
00186     if (!lstack)
00187         return ERROR_PTR("lstack not defined", procName, NULL);
00188 
00189     if (lstack->n == 0)
00190         return NULL;
00191 
00192     lstack->n--;
00193     item = lstack->array[lstack->n];
00194         
00195     return item;
00196 }
00197 
00198 
00199 /*!
00200  *  lstackExtendArray()
00201  *
00202  *      Input:  lstack
00203  *      Return: 0 if OK; 1 on error
00204  */
00205 l_int32
00206 lstackExtendArray(L_STACK  *lstack)
00207 {
00208     PROCNAME("lstackExtendArray");
00209 
00210     if (!lstack)
00211         return ERROR_INT("lstack not defined", procName, 1);
00212 
00213     if ((lstack->array = (void **)reallocNew((void **)&lstack->array,
00214                               sizeof(void *) * lstack->nalloc,
00215                               2 * sizeof(void *) * lstack->nalloc)) == NULL)
00216         return ERROR_INT("new lstack array not defined", procName, 1);
00217 
00218     lstack->nalloc = 2 * lstack->nalloc;
00219     return 0;
00220 }
00221 
00222 
00223 /*!
00224  *  lstackGetCount()
00225  *
00226  *      Input:  lstack
00227  *      Return: count, or 0 on error
00228  */
00229 l_int32
00230 lstackGetCount(L_STACK  *lstack)
00231 {
00232     PROCNAME("lstackGetCount");
00233 
00234     if (!lstack)
00235         return ERROR_INT("lstack not defined", procName, 1);
00236 
00237     return lstack->n;
00238 }
00239 
00240 
00241 
00242 /*---------------------------------------------------------------------*
00243  *                            Debug output                             *
00244  *---------------------------------------------------------------------*/
00245 /*!
00246  *  lstackPrint()
00247  *
00248  *      Input:  stream
00249  *              lstack
00250  *      Return: 0 if OK; 1 on error
00251  */
00252 l_int32
00253 lstackPrint(FILE     *fp,
00254             L_STACK  *lstack)
00255 {
00256 l_int32  i;
00257 
00258     PROCNAME("lstackPrint");
00259 
00260     if (!fp)
00261         return ERROR_INT("stream not defined", procName, 1);
00262     if (!lstack)
00263         return ERROR_INT("lstack not defined", procName, 1);
00264 
00265     fprintf(fp, "\n Stack: nalloc = %d, n = %d, array = %p\n", 
00266             lstack->nalloc, lstack->n, lstack->array);
00267     for (i = 0; i < lstack->n; i++)
00268         fprintf(fp,   "array[%d] = %p\n", i, lstack->array[i]);
00269     
00270     return 0;
00271 }
00272 
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Defines