Return to alloca.c CVS log

Up to [CSRG BSD Unix] / 43BSD / contrib / emacs / src

Annotation of 43BSD/contrib/emacs/src/alloca.c, revision 1.1

1.1     ! root        1: /*
        !             2:        alloca -- (mostly) portable public-domain implementation
        !             3: 
        !             4:        last edit:      86/01/26        D A Gwyn
        !             5: 
        !             6:        This implementation of the PWB library alloca() function,
        !             7:        which is used to allocate space off the run-time stack so
        !             8:        that it is automatically reclaimed upon procedure exit, 
        !             9:        was inspired by discussions with J. Q. Johnson of Cornell.
        !            10: 
        !            11:        It should work under any C implementation that uses an
        !            12:        actual procedure stack (as opposed to a linked list of
        !            13:        frames).  There are some preprocessor constants that can
        !            14:        be defined when compiling for your specific system, for
        !            15:        improved efficiency; however, the defaults should be okay.
        !            16: 
        !            17:        The general concept of this implementation is to keep
        !            18:        track of all alloca()-allocated blocks, and reclaim any
        !            19:        that are found to be deeper in the stack than the current
        !            20:        invocation.  This heuristic does not reclaim storage as
        !            21:        soon as it becomes invalid, but it will do so eventually.
        !            22: 
        !            23:        As a special case, alloca(0) reclaims storage without
        !            24:        allocating any.  It is a good idea to use alloca(0) in
        !            25:        your main control loop, etc. to force garbage collection.
        !            26: */
        !            27: #ifndef lint
        !            28: static char    SCCSid[] = "@(#)alloca.c        1.1";   /* for the "what" utility */
        !            29: #endif
        !            30: 
        !            31: #ifdef X3J11
        !            32: typedef void   *pointer;               /* generic pointer type */
        !            33: #else
        !            34: typedef char   *pointer;               /* generic pointer type */
        !            35: #endif
        !            36: 
        !            37: #define        NULL    0                       /* null pointer constant */
        !            38: 
        !            39: extern void    free();
        !            40: extern pointer malloc();
        !            41: 
        !            42: /*
        !            43:        Define STACK_DIRECTION if you know the direction of stack
        !            44:        growth for your system; otherwise it will be automatically
        !            45:        deduced at run-time.
        !            46: 
        !            47:        STACK_DIRECTION > 0 => grows toward higher addresses
        !            48:        STACK_DIRECTION < 0 => grows toward lower addresses
        !            49:        STACK_DIRECTION = 0 => direction of growth unknown
        !            50: */
        !            51: 
        !            52: #ifndef STACK_DIRECTION
        !            53: #define        STACK_DIRECTION 0               /* direction unknown */
        !            54: #endif
        !            55: 
        !            56: #if STACK_DIRECTION != 0
        !            57: 
        !            58: #define        STACK_DIR       STACK_DIRECTION /* known at compile-time */
        !            59: 
        !            60: #else  /* STACK_DIRECTION == 0; need run-time code */
        !            61: 
        !            62: static int     stack_dir;              /* 1 or -1 once known */
        !            63: #define        STACK_DIR       stack_dir
        !            64: 
        !            65: static void
        !            66: find_stack_direction (/* void */)
        !            67: {
        !            68:   static char  *addr = NULL;   /* address of first
        !            69:                                   `dummy', once known */
        !            70:   auto char    dummy;          /* to get stack address */
        !            71: 
        !            72:   if (addr == NULL)
        !            73:     {                          /* initial entry */
        !            74:       addr = &dummy;
        !            75: 
        !            76:       find_stack_direction (); /* recurse once */
        !            77:     }
        !            78:   else                         /* second entry */
        !            79:     if (&dummy > addr)
        !            80:       stack_dir = 1;           /* stack grew upward */
        !            81:     else
        !            82:       stack_dir = -1;          /* stack grew downward */
        !            83: }
        !            84: 
        !            85: #endif /* STACK_DIRECTION == 0 */
        !            86: 
        !            87: /*
        !            88:        An "alloca header" is used to:
        !            89:        (a) chain together all alloca()ed blocks;
        !            90:        (b) keep track of stack depth.
        !            91: 
        !            92:        It is very important that sizeof(header) agree with malloc()
        !            93:        alignment chunk size.  The following default should work okay.
        !            94: */
        !            95: 
        !            96: #ifndef        ALIGN_SIZE
        !            97: #define        ALIGN_SIZE      sizeof(double)
        !            98: #endif
        !            99: 
        !           100: typedef union hdr
        !           101: {
        !           102:   char align[ALIGN_SIZE];      /* to force sizeof(header) */
        !           103:   struct
        !           104:     {
        !           105:       union hdr *next;         /* for chaining headers */
        !           106:       char *deep;              /* for stack depth measure */
        !           107:     } h;
        !           108: } header;
        !           109: 
        !           110: /*
        !           111:        alloca( size ) returns a pointer to at least `size' bytes of
        !           112:        storage which will be automatically reclaimed upon exit from
        !           113:        the procedure that called alloca().  Originally, this space
        !           114:        was supposed to be taken from the current stack frame of the
        !           115:        caller, but that method cannot be made to work for some
        !           116:        implementations of C, for example under Gould's UTX/32.
        !           117: */
        !           118: 
        !           119: pointer
        !           120: alloca (size)                          /* returns pointer to storage */
        !           121:      unsigned  size;           /* # bytes to allocate */
        !           122: {
        !           123:   static header        *last = NULL;   /* -> last alloca header */
        !           124:   auto char    probe;          /* probes stack depth: */
        !           125:   register char        *depth = &probe;
        !           126: 
        !           127: #if STACK_DIRECTION == 0
        !           128:   if (STACK_DIR == 0)          /* unknown growth direction */
        !           129:     find_stack_direction ();
        !           130: #endif
        !           131: 
        !           132:                                /* Reclaim garbage, defined as all alloca()ed storage that
        !           133:                                   was allocated from deeper in the stack than currently. */
        !           134: 
        !           135:   {
        !           136:     register header    *hp;    /* traverses linked list */
        !           137: 
        !           138:     for (hp = last; hp != NULL;)
        !           139:       if (STACK_DIR > 0 && hp->h.deep > depth
        !           140:          || STACK_DIR < 0 && hp->h.deep < depth)
        !           141:        {
        !           142:          register header       *np = hp->h.next;
        !           143: 
        !           144:          free ((pointer) hp);  /* collect garbage */
        !           145: 
        !           146:          hp = np;              /* -> next header */
        !           147:        }
        !           148:       else
        !           149:        break;                  /* rest are not deeper */
        !           150: 
        !           151:     last = hp;                 /* -> last valid storage */
        !           152:   }
        !           153: 
        !           154:   if (size == 0)
        !           155:     return NULL;               /* no allocation required */
        !           156: 
        !           157:   /* Allocate combined header + user data storage. */
        !           158: 
        !           159:   {
        !           160:     register pointer   new = xmalloc (sizeof (header) + size);
        !           161:     /* address of header */
        !           162: 
        !           163:     ((header *)new)->h.next = last;
        !           164:     ((header *)new)->h.deep = depth;
        !           165: 
        !           166:     last = (header *)new;
        !           167: 
        !           168:     /* User storage begins just after header. */
        !           169: 
        !           170:     return (pointer)((char *)new + sizeof(header));
        !           171:   }
        !           172: }
        !           173: 

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.