home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / snip9707.zip / STACK.C < prev    next >
C/C++ Source or Header  |  1997-07-05  |  13KB  |  423 lines
  1. /* +++Date last modified: 05-Jul-1997 */
  2.  
  3. /* =======================================================================
  4.     STACK.c     Stack manager.
  5.                 A.Reitsma, Delft, Nederland.
  6.  
  7.                 v0.25  94-07-03  Public Domain.
  8.  
  9.     Many times I wanted to have one or more stacks for the program I was
  10.     working on. Sometimes I did without -- especially on Quick and Dirty
  11.     utilities. At other times I cobbled up something that more or less
  12.     seemed to work. Crashes were common ...
  13.     So I decided to take the time to do something about it.
  14.     This is the result.
  15.  
  16.  -  The Stack system is based on dynamic arrays: automatically growing
  17.     the stacks when needed. The growing is done in steps of 16 items.
  18.     This reduces the number of required memory reallocations (and
  19.     therefore the number of allocation failures).
  20.  -  Stack shrinking is intentionally not implemented.
  21.  -  ItemSizes larger than 2kB are not supported: the minimum of initial
  22.     StackItems per stack is currently 32.
  23.     An assert (debug version) limits ItemSizes: <= 1kB and >= 2 Bytes.
  24.     For large data items a separate 'user' module is probably sensible.
  25.     StackUnpop is added to take a look at info, especially size info so
  26.     an appropriate amount of memory can be allocated by the user.
  27.  -  A certain amount of redundancy is provided to enable integrity checks
  28.     for use in programs with 'wild pointer' problems.
  29.  -  Compile with NDEBUG defined for a 'production' version.
  30.     Compile with NDEBUG _not_ defined for a debug version.
  31.  -  Some functions benefit by using the compilers optimizer.
  32.     Especially 'Common Sub-expression Optimizations'.
  33.  -  Some items should be unsigned in stead of int. Not a real problem.
  34.     Detected by checking the appropriateness and ranges of types.
  35.  -  In some places an int is cast to unsigned, then tested for a 'large'
  36.     value including 'negative' values. This may be non-portable.
  37.  -  Not checked for potential alignment problems. I don't think there are.
  38. ___-------------------------------------------------------------------- */
  39.  
  40. #include <stdlib.h>
  41. #include <string.h>           /* memcpy() */
  42. #include <assert.h>           /* debugging */
  43. #include "stack.h"
  44. #include "stk_defs.h"         /* MALLOC, CALLOC, FREE (re-)definitions  */
  45.                               /* and other debugging re-def's with a    */
  46.                               /* special debugging version.             */
  47.  
  48. #define MEMORY          -1    /* Preparations/replacements for GP Error */
  49. #define Error(x)        (x)   /* manager. Error may terminate program.  */
  50.  
  51. #define STACK_GROWTH    16
  52.  
  53. struct StackHead
  54. {
  55.     char * base ;        /* base address for the stack (char * because  */
  56.                          /*     adding offset to void * doesn't work.)  */
  57.     unsigned offset ;    /* offset of data from base in bytes           */
  58.     int top ;            /* offset of data from base in items           */
  59.     int itemsize ;       /* itemsize * top should equal to offset       */
  60.     int max ;            /* max < top is an error                       */
  61.     int underflow ;      /* flag. Incremented when Pops exceed Pushes.  */
  62. };
  63.  
  64. /*  --- local data and prototypes ------------------------------------- */
  65.  
  66. static struct StackHead * StackArray ; /* initialised: StackSystemInit  */
  67.                                        /* modified by: StackCreate      */
  68. static int StackCount ;                /* same. Used by management only */
  69. static int StackInit( int Stack, int Itemsize );
  70.  
  71. /* ---- Management operations ----------------------------------------- */
  72.  
  73. int StackSystemInit( int StackCountAdditional )
  74. {
  75.     assert( (unsigned) StackCountAdditional <= 20 );
  76.                  /* negative is logic error (cast => neg. is large int) */
  77.                  /* higher than 20 is ridiculous for an initial setup   */
  78.  
  79.     StackCountAdditional += STACK_COUNT_DEFAULT ;
  80.  
  81.     /* Create and initialize stack 'descriptor' array. A zero value
  82.        for all bytes of a pointer is assumed to be a NULL pointer.
  83.     */
  84.     StackArray = CALLOC( StackCountAdditional, struct StackHead );
  85.     if( NULL == StackArray )
  86.     {
  87.         return Error( MEMORY );
  88.     }
  89.  
  90.     /* Initialize each default stack.
  91.     */
  92.     if( StackInit( STACK_INT, sizeof( int )))
  93.     {
  94.         return Error( MEMORY );
  95.     }
  96.  
  97.     if( StackInit( STACK_LONG, sizeof( long )))
  98.     {
  99.         return Error( MEMORY );
  100.     }
  101.  
  102.     if( StackInit( STACK_PTRS, sizeof( char * )))
  103.     {
  104.         return Error( MEMORY );
  105.     }
  106.  
  107.     if( StackInit( STACK_FAR_PTRS, sizeof( char FAR * )))
  108.     {
  109.         return Error( MEMORY );
  110.     }
  111.  
  112.     StackCount = StackCountAdditional ;
  113.     return StackCount ;
  114. }
  115.  
  116. static int StackInit( int Stack, int Itemsize )
  117. {
  118.     StackArray[ Stack ].itemsize  = Itemsize ;
  119.     StackArray[ Stack ].max       = STACK_GROWTH * 2 ;
  120.     StackArray[ Stack ].top       = 0 ;
  121.     StackArray[ Stack ].offset    = 0 ;
  122.     StackArray[ Stack ].underflow = 0 ;
  123.  
  124.     StackArray[ Stack ].base = MALLOC( STACK_GROWTH *2 * Itemsize, char );
  125.  
  126.     if( NULL == StackArray[ Stack ].base )
  127.     {
  128.         return MEMORY ;
  129.     }
  130.  
  131.     return NO_PROBLEMS ;
  132. }
  133.  
  134. int StackCreate( int ItemSize )
  135. {
  136.     int Stack ;
  137.  
  138.     assert( (unsigned) ItemSize-2 <= 1022 );
  139.                      /* Not too small, too large or negative please !!! */
  140.  
  141.     /* Look for empty slot
  142.     */
  143.     for( Stack = 0; Stack < StackCount; Stack++ )
  144.     {
  145.         if( NULL == StackArray[ Stack ].base )
  146.             break;
  147.     }
  148.  
  149.     /*  What if NO EMPTY slot ???
  150.     */
  151.     if( Stack == StackCount )
  152.     {
  153.         struct StackHead * tmp ;         /* StackArray expansion needed */
  154.  
  155.         tmp = realloc( StackArray,
  156.                        (StackCount + 1) * sizeof( struct StackHead ));
  157.         if( NULL == tmp )
  158.         {
  159.             return Error( MEMORY );
  160.         }
  161.  
  162.         StackArray = tmp ;
  163.         StackCount ++ ;
  164.     }
  165.  
  166.     if( StackInit( Stack, ItemSize ))
  167.     {
  168.         return Error( MEMORY );
  169.     }
  170.  
  171.     return Stack ;
  172. }
  173.  
  174. void StackDelete( int Stack )
  175. {
  176.     if( StackCheck( Stack ) < STACK_ERRORS )  /* OK if only warning */
  177.     {
  178.         FREE( StackArray[ Stack ].base );
  179.         StackArray[ Stack ].base = NULL ;
  180.     }
  181.     return ;
  182. }
  183.  
  184. int StackAdapt( int Stack, int Free )
  185. {
  186.    assert( (unsigned) Stack < StackCount );    /* validate stack number */
  187.  
  188.    assert( (unsigned) Free <= 4 * STACK_GROWTH );
  189.                        /* Negative and large numbers are ridiculous ... */
  190.                        /* assuming casted negative int = large unsigned */
  191.  
  192.    while( StackArray[ Stack ].top + Free >= StackArray[ Stack ].max )
  193.    {
  194.         char * tmp ;    /* resize Stack in steps */
  195.  
  196.         tmp = realloc( StackArray[ Stack ].base,
  197.                        StackArray[ Stack ].itemsize
  198.                         * (StackArray[ Stack ].max + STACK_GROWTH ));
  199.         if( NULL == tmp )
  200.         {
  201.             return MEMORY ;
  202.         }
  203.  
  204.         StackArray[ Stack ].max += STACK_GROWTH ;
  205.         StackArray[ Stack ].base = tmp;
  206.    }
  207.  
  208.    return NO_PROBLEMS ;
  209. }
  210.  
  211. int StackCheck( int Stack )      /* Check for possible problems in more */
  212. {                                /* or less decreasing severity         */
  213.     if( (unsigned) Stack >= StackCount )
  214.     {
  215.         return STACK_INV_NUMBER ;
  216.     }
  217.  
  218.     if( NULL == StackArray[ Stack ].base )
  219.     {
  220.         return STACK_NULL ;
  221.     }
  222.  
  223.     if( StackArray[ Stack ].top > StackArray[ Stack ].max )
  224.     {
  225.         return STACK_CORRUPT2 ;
  226.     }
  227.  
  228.     if( StackArray[ Stack ].top * StackArray[ Stack ].itemsize
  229.          != StackArray[ Stack ].offset )
  230.     {
  231.         return STACK_CORRUPT1 ;
  232.     }
  233.  
  234.     if( 0 != StackArray[ Stack ].underflow )
  235.     {
  236.         StackArray[ Stack ].underflow = 0; /* reset underflow flag */
  237.         return STACK_UNDERFLOW ;
  238.     }
  239.  
  240.     if( StackArray[ Stack ].top == StackArray[ Stack ].max )
  241.     {
  242.         return STACK_LIMIT_REACHED ;
  243.     }
  244.  
  245.     if( 0 == StackArray[ Stack ].top )
  246.     {
  247.         return STACK_EMPTY ;
  248.     }
  249.  
  250.     return NO_PROBLEMS ;
  251. }
  252.  
  253. void StackUnpop( int Stack ) /* Reverse a pop. Data is still present!   */
  254. {                            /* very useful for implementing stacks     */
  255.                              /* with variable sized items ...           */
  256.  
  257.     if( StackArray[ Stack ].top < StackArray[ Stack ].max )
  258.     {
  259.         StackArray[ Stack ].offset += StackArray[ Stack ].itemsize ;
  260.         StackArray[ Stack ].top ++ ;
  261.     }
  262.     return ;
  263. }
  264.  
  265. /* ---- Generic push/pop operations ----------------------------------- */
  266.  
  267. int Push( int Stack, void * Source )
  268. {
  269.     if( NO_PROBLEMS != StackAdapt( Stack, 1 ))
  270.     {
  271.         return MEMORY;
  272.     }
  273.  
  274.     memcpy( StackArray[ Stack ].base + StackArray[ Stack ].offset,
  275.             Source,
  276.             StackArray[ Stack ].itemsize );
  277.  
  278.     StackArray[ Stack ].offset += StackArray[ Stack ].itemsize ;
  279.     StackArray[ Stack ].top ++ ;
  280.  
  281.     return NO_PROBLEMS ;
  282. }
  283.  
  284. void Pop( int Stack, void * Destination )
  285. {
  286.     if( 0 != StackArray[ Stack ].top )  /* don't ACTUALLY underflow ... */
  287.     {
  288.         StackArray[ Stack ].offset -= StackArray[ Stack ].itemsize ;
  289.         StackArray[ Stack ].top -- ;
  290.     }
  291.     else
  292.         StackArray[ Stack ].underflow ++ ;
  293.  
  294.     memcpy( Destination,
  295.             StackArray[ Stack ].base + StackArray[ Stack ].offset,
  296.             StackArray[ Stack ].itemsize );
  297.     return ;
  298. }
  299.  
  300. /* ---- Push/pop operations to/from default stacks -------------------- */
  301.  
  302. int PushInt( int Value )
  303. {
  304.     if( NO_PROBLEMS != StackAdapt( STACK_INT, 1 ))
  305.     {
  306.         return MEMORY;
  307.     }
  308.  
  309.     * ((int *) ( StackArray[ STACK_INT ].base
  310.                   + StackArray[ STACK_INT ].offset )) = Value ;
  311.  
  312.     StackArray[ STACK_INT ].offset += sizeof( int );
  313.     StackArray[ STACK_INT ].top ++ ;
  314.  
  315.     return NO_PROBLEMS;
  316. }
  317.  
  318. int PopInt( void )
  319. {
  320.     if( 0 != StackArray[ STACK_INT ].top )
  321.     {
  322.         StackArray[ STACK_INT ].offset -= sizeof( int );
  323.         StackArray[ STACK_INT ].top -- ;
  324.     }
  325.     else
  326.         StackArray[ STACK_INT ].underflow ++ ;
  327.  
  328.     return * ((int *) ( StackArray[ STACK_INT ].base
  329.                          + StackArray[ STACK_INT ].offset ));
  330. }
  331.  
  332. int PushLong( long Value )
  333. {
  334.     if( NO_PROBLEMS != StackAdapt( STACK_LONG, 1 ))
  335.     {
  336.         return MEMORY;
  337.     }
  338.  
  339.     * ((long *) ( StackArray[ STACK_LONG ].base
  340.                    + StackArray[ STACK_LONG ].offset )) = Value ;
  341.  
  342.     StackArray[ STACK_LONG ].offset += sizeof( long );
  343.     StackArray[ STACK_LONG ].top ++ ;
  344.  
  345.     return NO_PROBLEMS;
  346. }
  347.  
  348. long PopLong( void )
  349. {
  350.     if( 0 != StackArray[ STACK_LONG ].top )
  351.     {
  352.         StackArray[ STACK_LONG ].offset -= sizeof( long );
  353.         StackArray[ STACK_LONG ].top -- ;
  354.     }
  355.     else
  356.         StackArray[ STACK_LONG ].underflow ++ ;
  357.  
  358.     return * ((long *) ( StackArray[ STACK_LONG ].base
  359.                           + StackArray[ STACK_LONG ].offset ));
  360. }
  361.  
  362. int PushPtr( void * Value )
  363. {
  364.     if( NO_PROBLEMS != StackAdapt( STACK_PTRS, 1 ))
  365.     {
  366.         return MEMORY;
  367.     }
  368.  
  369.     * ((char **) ( StackArray[ STACK_PTRS ].base
  370.                    + StackArray[ STACK_PTRS ].offset )) = Value ;
  371.  
  372.     StackArray[ STACK_PTRS ].offset += sizeof( char * );
  373.     StackArray[ STACK_PTRS ].top ++ ;
  374.  
  375.     return NO_PROBLEMS;
  376. }
  377.  
  378. void * PopPtr( void )
  379. {
  380.     if( 0 != StackArray[ STACK_PTRS ].top )
  381.     {
  382.         StackArray[ STACK_PTRS ].offset -= sizeof( char * );
  383.         StackArray[ STACK_PTRS ].top -- ;
  384.     }
  385.     else
  386.         StackArray[ STACK_PTRS ].underflow ++ ;
  387.  
  388.     return * ((char **) ( StackArray[ STACK_PTRS ].base
  389.                            + StackArray[ STACK_PTRS ].offset ));
  390. }
  391.  
  392. int PushFptr( void FAR * Value )
  393. {
  394.     if( NO_PROBLEMS != StackAdapt( STACK_FAR_PTRS, 1 ))
  395.     {
  396.         return MEMORY;
  397.     }
  398.  
  399.     * ((char FAR **) ( StackArray[ STACK_FAR_PTRS ].base
  400.                         + StackArray[ STACK_FAR_PTRS ].offset )) = Value ;
  401.  
  402.     StackArray[ STACK_FAR_PTRS ].offset += sizeof( char FAR * );
  403.     StackArray[ STACK_FAR_PTRS ].top ++ ;
  404.  
  405.     return NO_PROBLEMS;
  406. }
  407.  
  408. void FAR * PopFptr( void )
  409. {
  410.     if( 0 != StackArray[ STACK_FAR_PTRS ].top )
  411.     {
  412.         StackArray[ STACK_FAR_PTRS ].offset -= sizeof( char FAR * );
  413.         StackArray[ STACK_FAR_PTRS ].top -- ;
  414.     }
  415.     else
  416.         StackArray[ STACK_FAR_PTRS ].underflow ++ ;
  417.  
  418.     return * ((char FAR **) ( StackArray[ STACK_FAR_PTRS ].base
  419.                                + StackArray[ STACK_FAR_PTRS ].offset ));
  420. }
  421.  
  422. /* === STACK.c end ==================================================== */
  423.