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