source: trunk/third/enscript/compat/alloca.c @ 17620

Revision 17620, 13.9 KB checked in by ghudson, 22 years ago (diff)
This commit was generated by cvs2svn to compensate for changes in r17619, which included commits to RCS files with non-trunk default branches.
Line 
1/* alloca.c -- allocate automatically reclaimed memory
2   (Mostly) portable public-domain implementation -- D A Gwyn
3
4   This implementation of the PWB library alloca function,
5   which is used to allocate space off the run-time stack so
6   that it is automatically reclaimed upon procedure exit,
7   was inspired by discussions with J. Q. Johnson of Cornell.
8   J.Otto Tennant <jot@cray.com> contributed the Cray support.
9
10   There are some preprocessor constants that can
11   be defined when compiling for your specific system, for
12   improved efficiency; however, the defaults should be okay.
13
14   The general concept of this implementation is to keep
15   track of all alloca-allocated blocks, and reclaim any
16   that are found to be deeper in the stack than the current
17   invocation.  This heuristic does not reclaim storage as
18   soon as it becomes invalid, but it will do so eventually.
19
20   As a special case, alloca(0) reclaims storage without
21   allocating any.  It is a good idea to use alloca(0) in
22   your main control loop, etc. to force garbage collection.  */
23
24#ifdef HAVE_CONFIG_H
25#include <config.h>
26#endif
27
28#ifdef HAVE_STRING_H
29#include <string.h>
30#endif
31#ifdef HAVE_STDLIB_H
32#include <stdlib.h>
33#endif
34
35#ifdef emacs
36#include "blockinput.h"
37#endif
38
39/* If compiling with GCC 2, this file's not needed.  */
40#if !defined (__GNUC__) || __GNUC__ < 2
41
42/* If someone has defined alloca as a macro,
43   there must be some other way alloca is supposed to work.  */
44#ifndef alloca
45
46#ifdef emacs
47#ifdef static
48/* actually, only want this if static is defined as ""
49   -- this is for usg, in which emacs must undefine static
50   in order to make unexec workable
51   */
52#ifndef STACK_DIRECTION
53you
54lose
55-- must know STACK_DIRECTION at compile-time
56#endif /* STACK_DIRECTION undefined */
57#endif /* static */
58#endif /* emacs */
59
60/* If your stack is a linked list of frames, you have to
61   provide an "address metric" ADDRESS_FUNCTION macro.  */
62
63#if defined (CRAY) && defined (CRAY_STACKSEG_END)
64long i00afunc ();
65#define ADDRESS_FUNCTION(arg) (char *) i00afunc (&(arg))
66#else
67#define ADDRESS_FUNCTION(arg) &(arg)
68#endif
69
70#if __STDC__
71typedef void *pointer;
72#else
73typedef char *pointer;
74#endif
75
76#ifndef NULL
77#define NULL    0
78#endif
79
80/* Different portions of Emacs need to call different versions of
81   malloc.  The Emacs executable needs alloca to call xmalloc, because
82   ordinary malloc isn't protected from input signals.  On the other
83   hand, the utilities in lib-src need alloca to call malloc; some of
84   them are very simple, and don't have an xmalloc routine.
85
86   Non-Emacs programs expect this to call xmalloc.
87
88   Callers below should use malloc.  */
89
90#ifndef emacs
91#define malloc xmalloc
92#endif
93extern pointer malloc ();
94
95/* Define STACK_DIRECTION if you know the direction of stack
96   growth for your system; otherwise it will be automatically
97   deduced at run-time.
98
99   STACK_DIRECTION > 0 => grows toward higher addresses
100   STACK_DIRECTION < 0 => grows toward lower addresses
101   STACK_DIRECTION = 0 => direction of growth unknown  */
102
103#ifndef STACK_DIRECTION
104#define STACK_DIRECTION 0       /* Direction unknown.  */
105#endif
106
107#if STACK_DIRECTION != 0
108
109#define STACK_DIR       STACK_DIRECTION /* Known at compile-time.  */
110
111#else /* STACK_DIRECTION == 0; need run-time code.  */
112
113static int stack_dir;           /* 1 or -1 once known.  */
114#define STACK_DIR       stack_dir
115
116static void
117find_stack_direction ()
118{
119  static char *addr = NULL;     /* Address of first `dummy', once known.  */
120  auto char dummy;              /* To get stack address.  */
121
122  if (addr == NULL)
123    {                           /* Initial entry.  */
124      addr = ADDRESS_FUNCTION (dummy);
125
126      find_stack_direction ();  /* Recurse once.  */
127    }
128  else
129    {
130      /* Second entry.  */
131      if (ADDRESS_FUNCTION (dummy) > addr)
132        stack_dir = 1;          /* Stack grew upward.  */
133      else
134        stack_dir = -1;         /* Stack grew downward.  */
135    }
136}
137
138#endif /* STACK_DIRECTION == 0 */
139
140/* An "alloca header" is used to:
141   (a) chain together all alloca'ed blocks;
142   (b) keep track of stack depth.
143
144   It is very important that sizeof(header) agree with malloc
145   alignment chunk size.  The following default should work okay.  */
146
147#ifndef ALIGN_SIZE
148#define ALIGN_SIZE      sizeof(double)
149#endif
150
151typedef union hdr
152{
153  char align[ALIGN_SIZE];       /* To force sizeof(header).  */
154  struct
155    {
156      union hdr *next;          /* For chaining headers.  */
157      char *deep;               /* For stack depth measure.  */
158    } h;
159} header;
160
161static header *last_alloca_header = NULL;       /* -> last alloca header.  */
162
163/* Return a pointer to at least SIZE bytes of storage,
164   which will be automatically reclaimed upon exit from
165   the procedure that called alloca.  Originally, this space
166   was supposed to be taken from the current stack frame of the
167   caller, but that method cannot be made to work for some
168   implementations of C, for example under Gould's UTX/32.  */
169
170pointer
171alloca (size)
172     unsigned size;
173{
174  auto char probe;              /* Probes stack depth: */
175  register char *depth = ADDRESS_FUNCTION (probe);
176
177#if STACK_DIRECTION == 0
178  if (STACK_DIR == 0)           /* Unknown growth direction.  */
179    find_stack_direction ();
180#endif
181
182  /* Reclaim garbage, defined as all alloca'd storage that
183     was allocated from deeper in the stack than currently.  */
184
185  {
186    register header *hp;        /* Traverses linked list.  */
187
188#ifdef emacs
189    BLOCK_INPUT;
190#endif
191
192    for (hp = last_alloca_header; hp != NULL;)
193      if ((STACK_DIR > 0 && hp->h.deep > depth)
194          || (STACK_DIR < 0 && hp->h.deep < depth))
195        {
196          register header *np = hp->h.next;
197
198          free ((pointer) hp);  /* Collect garbage.  */
199
200          hp = np;              /* -> next header.  */
201        }
202      else
203        break;                  /* Rest are not deeper.  */
204
205    last_alloca_header = hp;    /* -> last valid storage.  */
206
207#ifdef emacs
208    UNBLOCK_INPUT;
209#endif
210  }
211
212  if (size == 0)
213    return NULL;                /* No allocation required.  */
214
215  /* Allocate combined header + user data storage.  */
216
217  {
218    register pointer new = malloc (sizeof (header) + size);
219    /* Address of header.  */
220
221    if (new == 0)
222      abort();
223
224    ((header *) new)->h.next = last_alloca_header;
225    ((header *) new)->h.deep = depth;
226
227    last_alloca_header = (header *) new;
228
229    /* User storage begins just after header.  */
230
231    return (pointer) ((char *) new + sizeof (header));
232  }
233}
234
235#if defined (CRAY) && defined (CRAY_STACKSEG_END)
236
237#ifdef DEBUG_I00AFUNC
238#include <stdio.h>
239#endif
240
241#ifndef CRAY_STACK
242#define CRAY_STACK
243#ifndef CRAY2
244/* Stack structures for CRAY-1, CRAY X-MP, and CRAY Y-MP */
245struct stack_control_header
246  {
247    long shgrow:32;             /* Number of times stack has grown.  */
248    long shaseg:32;             /* Size of increments to stack.  */
249    long shhwm:32;              /* High water mark of stack.  */
250    long shsize:32;             /* Current size of stack (all segments).  */
251  };
252
253/* The stack segment linkage control information occurs at
254   the high-address end of a stack segment.  (The stack
255   grows from low addresses to high addresses.)  The initial
256   part of the stack segment linkage control information is
257   0200 (octal) words.  This provides for register storage
258   for the routine which overflows the stack.  */
259
260struct stack_segment_linkage
261  {
262    long ss[0200];              /* 0200 overflow words.  */
263    long sssize:32;             /* Number of words in this segment.  */
264    long ssbase:32;             /* Offset to stack base.  */
265    long:32;
266    long sspseg:32;             /* Offset to linkage control of previous
267                                   segment of stack.  */
268    long:32;
269    long sstcpt:32;             /* Pointer to task common address block.  */
270    long sscsnm;                /* Private control structure number for
271                                   microtasking.  */
272    long ssusr1;                /* Reserved for user.  */
273    long ssusr2;                /* Reserved for user.  */
274    long sstpid;                /* Process ID for pid based multi-tasking.  */
275    long ssgvup;                /* Pointer to multitasking thread giveup.  */
276    long sscray[7];             /* Reserved for Cray Research.  */
277    long ssa0;
278    long ssa1;
279    long ssa2;
280    long ssa3;
281    long ssa4;
282    long ssa5;
283    long ssa6;
284    long ssa7;
285    long sss0;
286    long sss1;
287    long sss2;
288    long sss3;
289    long sss4;
290    long sss5;
291    long sss6;
292    long sss7;
293  };
294
295#else /* CRAY2 */
296/* The following structure defines the vector of words
297   returned by the STKSTAT library routine.  */
298struct stk_stat
299  {
300    long now;                   /* Current total stack size.  */
301    long maxc;                  /* Amount of contiguous space which would
302                                   be required to satisfy the maximum
303                                   stack demand to date.  */
304    long high_water;            /* Stack high-water mark.  */
305    long overflows;             /* Number of stack overflow ($STKOFEN) calls.  */
306    long hits;                  /* Number of internal buffer hits.  */
307    long extends;               /* Number of block extensions.  */
308    long stko_mallocs;          /* Block allocations by $STKOFEN.  */
309    long underflows;            /* Number of stack underflow calls ($STKRETN).  */
310    long stko_free;             /* Number of deallocations by $STKRETN.  */
311    long stkm_free;             /* Number of deallocations by $STKMRET.  */
312    long segments;              /* Current number of stack segments.  */
313    long maxs;                  /* Maximum number of stack segments so far.  */
314    long pad_size;              /* Stack pad size.  */
315    long current_address;       /* Current stack segment address.  */
316    long current_size;          /* Current stack segment size.  This
317                                   number is actually corrupted by STKSTAT to
318                                   include the fifteen word trailer area.  */
319    long initial_address;       /* Address of initial segment.  */
320    long initial_size;          /* Size of initial segment.  */
321  };
322
323/* The following structure describes the data structure which trails
324   any stack segment.  I think that the description in 'asdef' is
325   out of date.  I only describe the parts that I am sure about.  */
326
327struct stk_trailer
328  {
329    long this_address;          /* Address of this block.  */
330    long this_size;             /* Size of this block (does not include
331                                   this trailer).  */
332    long unknown2;
333    long unknown3;
334    long link;                  /* Address of trailer block of previous
335                                   segment.  */
336    long unknown5;
337    long unknown6;
338    long unknown7;
339    long unknown8;
340    long unknown9;
341    long unknown10;
342    long unknown11;
343    long unknown12;
344    long unknown13;
345    long unknown14;
346  };
347
348#endif /* CRAY2 */
349#endif /* not CRAY_STACK */
350
351#ifdef CRAY2
352/* Determine a "stack measure" for an arbitrary ADDRESS.
353   I doubt that "lint" will like this much.  */
354
355static long
356i00afunc (long *address)
357{
358  struct stk_stat status;
359  struct stk_trailer *trailer;
360  long *block, size;
361  long result = 0;
362
363  /* We want to iterate through all of the segments.  The first
364     step is to get the stack status structure.  We could do this
365     more quickly and more directly, perhaps, by referencing the
366     $LM00 common block, but I know that this works.  */
367
368  STKSTAT (&status);
369
370  /* Set up the iteration.  */
371
372  trailer = (struct stk_trailer *) (status.current_address
373                                    + status.current_size
374                                    - 15);
375
376  /* There must be at least one stack segment.  Therefore it is
377     a fatal error if "trailer" is null.  */
378
379  if (trailer == 0)
380    abort ();
381
382  /* Discard segments that do not contain our argument address.  */
383
384  while (trailer != 0)
385    {
386      block = (long *) trailer->this_address;
387      size = trailer->this_size;
388      if (block == 0 || size == 0)
389        abort ();
390      trailer = (struct stk_trailer *) trailer->link;
391      if ((block <= address) && (address < (block + size)))
392        break;
393    }
394
395  /* Set the result to the offset in this segment and add the sizes
396     of all predecessor segments.  */
397
398  result = address - block;
399
400  if (trailer == 0)
401    {
402      return result;
403    }
404
405  do
406    {
407      if (trailer->this_size <= 0)
408        abort ();
409      result += trailer->this_size;
410      trailer = (struct stk_trailer *) trailer->link;
411    }
412  while (trailer != 0);
413
414  /* We are done.  Note that if you present a bogus address (one
415     not in any segment), you will get a different number back, formed
416     from subtracting the address of the first block.  This is probably
417     not what you want.  */
418
419  return (result);
420}
421
422#else /* not CRAY2 */
423/* Stack address function for a CRAY-1, CRAY X-MP, or CRAY Y-MP.
424   Determine the number of the cell within the stack,
425   given the address of the cell.  The purpose of this
426   routine is to linearize, in some sense, stack addresses
427   for alloca.  */
428
429static long
430i00afunc (long address)
431{
432  long stkl = 0;
433
434  long size, pseg, this_segment, stack;
435  long result = 0;
436
437  struct stack_segment_linkage *ssptr;
438
439  /* Register B67 contains the address of the end of the
440     current stack segment.  If you (as a subprogram) store
441     your registers on the stack and find that you are past
442     the contents of B67, you have overflowed the segment.
443
444     B67 also points to the stack segment linkage control
445     area, which is what we are really interested in.  */
446
447  stkl = CRAY_STACKSEG_END ();
448  ssptr = (struct stack_segment_linkage *) stkl;
449
450  /* If one subtracts 'size' from the end of the segment,
451     one has the address of the first word of the segment.
452
453     If this is not the first segment, 'pseg' will be
454     nonzero.  */
455
456  pseg = ssptr->sspseg;
457  size = ssptr->sssize;
458
459  this_segment = stkl - size;
460
461  /* It is possible that calling this routine itself caused
462     a stack overflow.  Discard stack segments which do not
463     contain the target address.  */
464
465  while (!(this_segment <= address && address <= stkl))
466    {
467#ifdef DEBUG_I00AFUNC
468      fprintf (stderr, "%011o %011o %011o\n", this_segment, address, stkl);
469#endif
470      if (pseg == 0)
471        break;
472      stkl = stkl - pseg;
473      ssptr = (struct stack_segment_linkage *) stkl;
474      size = ssptr->sssize;
475      pseg = ssptr->sspseg;
476      this_segment = stkl - size;
477    }
478
479  result = address - this_segment;
480
481  /* If you subtract pseg from the current end of the stack,
482     you get the address of the previous stack segment's end.
483     This seems a little convoluted to me, but I'll bet you save
484     a cycle somewhere.  */
485
486  while (pseg != 0)
487    {
488#ifdef DEBUG_I00AFUNC
489      fprintf (stderr, "%011o %011o\n", pseg, size);
490#endif
491      stkl = stkl - pseg;
492      ssptr = (struct stack_segment_linkage *) stkl;
493      size = ssptr->sssize;
494      pseg = ssptr->sspseg;
495      result += size;
496    }
497  return (result);
498}
499
500#endif /* not CRAY2 */
501#endif /* CRAY */
502
503#endif /* no alloca */
504#endif /* not GCC version 2 */
Note: See TracBrowser for help on using the repository browser.