Fresh Fish 5/FreshFish_July-August1994.bin/bbs/util/mg-3b.lha/mg-3b/src.LZH/mg/alloca.c

C/C++ Source or Header | 1990-05-23 | 4.7 KB | 165 lines

/*
 * Note to mg porters: this is included on the off chance you don't have an
 * alloca, and want to use the regexp code. I seriously recommend not using
 * it if you can avoid it.
 */

/*
 * alloca -- (mostly) portable public-domain implementation -- D A Gwyn
 *
 * This implementation of the PWB library alloca() function, which is used to
 * allocate space off the run-time stack so that it is automatically
 * reclaimed upon procedure exit, was inspired by discussions with J. Q.
 * Johnson of Cornell.
 *
 * It should work under any C implementation that uses an actual procedure stack
 * (as opposed to a linked list of frames).  There are some preprocessor
 * constants that can be defined when compiling for your specific system, for
 * improved efficiency; however, the defaults should be okay.
 *
 * The general concept of this implementation is to keep track of all
 * alloca()-allocated blocks, and reclaim any that are found to be deeper in
 * the stack than the current invocation.  This heuristic does not reclaim
 * storage as soon as it becomes invalid, but it will do so eventually.
 *
 * As a special case, alloca(0) reclaims storage without allocating any.  It is
 * a good idea to use alloca(0) in your main control loop, etc. to force
 * garbage collection.
 */
#include "regexp.h"
#ifdef    REGEXP

#include "def.h"        /* Get me lotsa defines */

#ifdef ANSI
#include <stdlib.h>
#endif

typedef VOID   *pointer;    /* generic pointer type */

/*
 * Define STACK_DIRECTION if you know the direction of stack growth for your
 * system; otherwise it will be automatically deduced at run-time.
 *
 * STACK_DIRECTION > 0 => grows toward higher addresses STACK_DIRECTION < 0 =>
 * grows toward lower addresses STACK_DIRECTION undefined => direction of
 * growth unknown
 */


#ifdef STACK_DIRECTION

#define    STACK_DIR    STACK_DIRECTION    /* known at compile-time */

#else                /* STACK_DIRECTION undefined -> need to find
                 * it at compile time */

static int      stack_dir;    /* 1 or -1 once known */
#define    STACK_DIR    stack_dir

static          VOID
find_stack_direction PROTO(( VOID ))
{
    static char    *addr = NULL;    /* address of first `dummy', once
                     * known */
    auto char       dummy;    /* to get stack address */

    if (addr == NULL) {    /* initial entry */
        addr = &dummy;

        find_stack_direction();    /* recurse once */
    } else
     /* second entry */ if (&dummy > addr)
        stack_dir = 1;    /* stack grew upward */
    else
        stack_dir = -1;    /* stack grew downward */
}

#endif                /* STACK_DIRECTION */

/*
 * An "alloca header" is used to: (a) chain together all alloca()ed blocks;
 * (b) keep track of stack depth.
 *
 * It is very important that sizeof(header) agree with malloc() alignment chunk
 * size.  The following default should work okay.
 */

#ifndef    ALIGN_SIZE
#define    ALIGN_SIZE    sizeof(double)
#endif

typedef union hdr {
    char            align[ALIGN_SIZE];    /* to force sizeof(header) */
    struct {
        union hdr      *next;    /* for chaining headers */
        char           *deep;    /* for stack depth measure */
    }               h;
}               header;

/*
 * alloca( size ) returns a pointer to at least `size' bytes of storage which
 * will be automatically reclaimed upon exit from the procedure that called
 * alloca().  Originally, this space was supposed to be taken from the
 * current stack frame of the caller, but that method cannot be made to work
 * for some implementations of C, for example under Gould's UTX/32.
 */

static header  *last_alloca_header = NULL;    /* -> last alloca header */

pointer
alloca(size)            /* returns pointer to storage */
    unsigned        size;    /* # bytes to allocate */
{
    auto char       probe;    /* probes stack depth: */
    register char  *depth = &probe;

#ifndef STACK_DIRECTION
    if (STACK_DIR == 0)    /* unknown growth direction */
        find_stack_direction();
#endif
    /*
     * Reclaim garbage, defined as all alloca()ed storage that was
     * allocated from deeper in the stack than currently.
     */

    {
        register header *hp;    /* traverses linked list */

        for (hp = last_alloca_header; hp != NULL;)
            if (STACK_DIR > 0 && hp->h.deep > depth
                || STACK_DIR < 0 && hp->h.deep < depth) {
                register header *np = hp->h.next;

                free((pointer) hp);    /* collect garbage */

                hp = np;    /* -> next header */
            } else
                break;    /* rest are not deeper */

        last_alloca_header = hp;    /* -> last valid storage */
    }

    if (size == 0)
        return NULL;    /* no allocation required */

    /* Allocate combined header + user data storage. */

    {
        register pointer new = malloc(sizeof(header) + size);
        /* address of header */

        ((header *) new)->h.next = last_alloca_header;
        ((header *) new)->h.deep = depth;

        last_alloca_header = (header *) new;

        /* User storage begins just after header. */

        return (pointer) ((char *) new + sizeof(header));
    }
}
#else
#include "nullfile.h"
#endif