Ruby  1.9.3p448(2013-06-27revision41675)
alloca.c
Go to the documentation of this file.
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
29 static char SCCSid[] = "@(#)alloca.c 1.1"; /* for the "what" utility */
30 #endif
31 
32 #include "ruby/config.h"
33 #ifdef C_ALLOCA
34 
35 #ifdef emacs
36 #ifdef static
37 /* actually, only want this if static is defined as ""
38  -- this is for usg, in which emacs must undefine static
39  in order to make unexec workable
40  */
41 #ifndef STACK_DIRECTION
42 you
43 lose
44 -- must know STACK_DIRECTION at compile-time
45 #endif /* STACK_DIRECTION undefined */
46 #endif /* static */
47 #endif /* emacs */
48 
49 #ifdef X3J11
50 typedef void *pointer; /* generic pointer type */
51 #else
52 typedef char *pointer; /* generic pointer type */
53 #endif /* X3J11 */
54 
55 #define NULL 0 /* null pointer constant */
56 
57 #ifdef RUBY_LIB_PREFIX
58 #define xmalloc ruby_xmalloc
59 #define xfree ruby_xfree
60 #endif
61 
62 extern void xfree();
63 extern pointer xmalloc();
64 
65 /*
66  Define STACK_DIRECTION if you know the direction of stack
67  growth for your system; otherwise it will be automatically
68  deduced at run-time.
69 
70  STACK_DIRECTION > 0 => grows toward higher addresses
71  STACK_DIRECTION < 0 => grows toward lower addresses
72  STACK_DIRECTION = 0 => direction of growth unknown
73 */
74 
75 #ifndef STACK_DIRECTION
76 #define STACK_DIRECTION 0 /* direction unknown */
77 #endif
78 
79 #if STACK_DIRECTION != 0
80 
81 #define STACK_DIR STACK_DIRECTION /* known at compile-time */
82 
83 #else /* STACK_DIRECTION == 0; need run-time code */
84 
85 static int stack_dir; /* 1 or -1 once known */
86 #define STACK_DIR stack_dir
87 
88 static void
89 find_stack_direction (/* void */)
90 {
91  static char *addr = NULL; /* address of first
92  `dummy', once known */
93  auto char dummy; /* to get stack address */
94 
95  if (addr == NULL)
96  { /* initial entry */
97  addr = &dummy;
98 
99  find_stack_direction (); /* recurse once */
100  }
101  else /* second entry */
102  if (&dummy > addr)
103  stack_dir = 1; /* stack grew upward */
104  else
105  stack_dir = -1; /* stack grew downward */
106 }
107 
108 #endif /* STACK_DIRECTION == 0 */
109 
110 /*
111  An "alloca header" is used to:
112  (a) chain together all alloca()ed blocks;
113  (b) keep track of stack depth.
114 
115  It is very important that sizeof(header) agree with malloc()
116  alignment chunk size. The following default should work okay.
117 */
118 
119 #ifndef ALIGN_SIZE
120 #define ALIGN_SIZE sizeof(double)
121 #endif
122 
123 typedef union hdr
124 {
125  char align[ALIGN_SIZE]; /* to force sizeof(header) */
126  struct
127  {
128  union hdr *next; /* for chaining headers */
129  char *deep; /* for stack depth measure */
130  } h;
131 } header;
132 
133 /*
134  alloca( size ) returns a pointer to at least `size' bytes of
135  storage which will be automatically reclaimed upon exit from
136  the procedure that called alloca(). Originally, this space
137  was supposed to be taken from the current stack frame of the
138  caller, but that method cannot be made to work for some
139  implementations of C, for example under Gould's UTX/32.
140 */
141 
142 static header *last_alloca_header = NULL; /* -> last alloca header */
143 
144 pointer
145 alloca (size) /* returns pointer to storage */
146  unsigned size; /* # bytes to allocate */
147 {
148  auto char probe; /* probes stack depth: */
149  register char *depth = &probe;
150 
151 #if STACK_DIRECTION == 0
152  if (STACK_DIR == 0) /* unknown growth direction */
153  find_stack_direction ();
154 #endif
155 
156  /* Reclaim garbage, defined as all alloca()ed storage that
157  was allocated from deeper in the stack than currently. */
158  {
159  register header *hp; /* traverses linked list */
160 
161  for (hp = last_alloca_header; hp != NULL;)
162  if (STACK_DIR > 0 && hp->h.deep > depth
163  || STACK_DIR < 0 && hp->h.deep < depth)
164  {
165  register header *np = hp->h.next;
166 
167  xfree ((pointer) hp); /* collect garbage */
168 
169  hp = np; /* -> next header */
170  }
171  else
172  break; /* rest are not deeper */
173 
174  last_alloca_header = hp; /* -> last valid storage */
175  }
176 
177  if (size == 0)
178  return NULL; /* no allocation required */
179 
180  /* Allocate combined header + user data storage. */
181 
182  {
183  register pointer new = xmalloc (sizeof (header) + size);
184  /* address of header */
185 
186  ((header *)new)->h.next = last_alloca_header;
187  ((header *)new)->h.deep = depth;
188 
189  last_alloca_header = (header *)new;
190 
191  /* User storage begins just after header. */
192 
193  return (pointer)((char *)new + sizeof(header));
194  }
195 }
196 
197 #endif
void * alloca()
#define NULL
void xfree(void *)
int size
Definition: encoding.c:51
#define xmalloc
Definition: defines.h:64
static char SCCSid[]
Definition: alloca.c:29