Reformatted.
[chise/xemacs-chise.git.1] / src / gmalloc.c
1 /* Synched up with: Not synched up with FSF 19.28, even though I
2    thought I did so. */
3
4 /* Get the configuration files if we're being compiled for Emacs.  */
5 #ifdef emacs
6 # include <config.h>
7 # include "getpagesize.h"
8 # ifndef HAVE_CONFIG_H
9 # define HAVE_CONFIG_H
10 # endif
11 #endif
12
13 #if defined (__STDC__) && !defined (STDC_HEADERS)
14   /* The ANSI standard says that defining __STDC__ to a non-zero value means
15      that the compiler conforms to that standard.  The standard requires
16      certain header files and library functions to be present.  Therefore,
17      if your compiler defines __STDC__ to non-0 but does not have ANSI headers
18      and the ANSI library routines, then your compiler is buggy.  Conversely,
19      an ANSI-conforming environment (which has both the ANSI headers and
20      library routines, i.e., stdlib.h and `memmove') does not necessarily
21      define the STDC_HEADERS flag.  Lucid Emacs requires an ANSI compiler.
22      Therefore, there is no need to consult the abominable STDC_HEADERS flag.
23      -- jwz
24    */
25 # define STDC_HEADERS
26 #endif
27
28 \f
29 /* DO NOT EDIT THIS FILE -- it is automagically generated.  -*- C -*- */
30 /* Bwaa-haa-haa!  Not a chance that this is actually true! */
31
32 #define _MALLOC_INTERNAL
33
34 /* The malloc headers and source files from the C library follow here.  */
35
36 /* Declarations for `malloc' and friends.
37    Copyright 1990, 1991, 1992, 1993 Free Software Foundation, Inc.
38                   Written May 1989 by Mike Haertel.
39
40 This library is free software; you can redistribute it and/or
41 modify it under the terms of the GNU Library General Public License as
42 published by the Free Software Foundation; either version 2 of the
43 License, or (at your option) any later version.
44
45 This library is distributed in the hope that it will be useful,
46 but WITHOUT ANY WARRANTY; without even the implied warranty of
47 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
48 Library General Public License for more details.
49
50 You should have received a copy of the GNU General Public License
51 along with this library; see the file COPYING.  If not, write to
52 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
53 Boston, MA 02111-1307, USA.
54
55    The author may be reached (Email) at the address mike@ai.mit.edu,
56    or (US mail) as Mike Haertel c/o Free Software Foundation, Inc.  */
57
58 #ifndef _MALLOC_H
59
60 #define _MALLOC_H       1
61
62 #ifdef _MALLOC_INTERNAL
63
64 #ifdef  HAVE_CONFIG_H
65 #include <config.h>
66 #endif
67
68 #include <string.h>
69 #include <limits.h>
70
71 #ifdef  HAVE_UNISTD_H
72 #include <unistd.h>
73 #endif
74
75 #endif  /* _MALLOC_INTERNAL.  */
76
77
78 #ifdef  __cplusplus
79 extern "C"
80 {
81 #endif
82
83 #undef  __P
84 #define __P(args)       args
85 #undef  __ptr_t
86 #define __ptr_t         void *
87
88 #include <stddef.h>
89 #define __malloc_size_t size_t
90
91 #ifndef NULL
92 #define NULL    0
93 #endif
94
95 /* XEmacs: I thought this should be int under SunOS, but that
96    apparently fails.  Curses on all this shit. */
97 #define __free_ret_t void
98
99 /* XEmacs: I tried commenting these out and including stdlib.h,
100    but that fails badly.  Urk!  This sucks. */
101 /* Allocate SIZE bytes of memory.  */
102 extern __ptr_t malloc __P ((size_t __size));
103 /* Re-allocate the previously allocated block
104    in __ptr_t, making the new block SIZE bytes long.  */
105 extern __ptr_t realloc __P ((__ptr_t __ptr, size_t __size));
106 /* Allocate NMEMB elements of SIZE bytes each, all initialized to 0.  */
107 extern __ptr_t calloc __P ((size_t __nmemb, size_t __size));
108 /* Free a block allocated by `malloc', `realloc' or `calloc'.  */
109 extern __free_ret_t free __P ((__ptr_t __ptr));
110
111 /* Allocate SIZE bytes allocated to ALIGNMENT bytes.  */
112 extern __ptr_t memalign __P ((size_t __alignment, size_t __size));
113
114 /* Allocate SIZE bytes on a page boundary.  */
115 extern __ptr_t valloc __P ((size_t __size));
116
117
118 #ifdef _MALLOC_INTERNAL
119
120 /* The allocator divides the heap into blocks of fixed size; large
121    requests receive one or more whole blocks, and small requests
122    receive a fragment of a block.  Fragment sizes are powers of two,
123    and all fragments of a block are the same size.  When all the
124    fragments in a block have been freed, the block itself is freed.  */
125 #define INT_BIT         (CHAR_BIT * sizeof(int))
126 #define BLOCKLOG        (INT_BIT > 16 ? 12 : 9)
127 #define BLOCKSIZE       (1 << BLOCKLOG)
128 #define BLOCKIFY(SIZE)  (((SIZE) + BLOCKSIZE - 1) / BLOCKSIZE)
129
130 /* Determine the amount of memory spanned by the initial heap table
131    (not an absolute limit).  */
132 #define HEAP            (INT_BIT > 16 ? 4194304 : 65536)
133
134 /* Number of contiguous free blocks allowed to build up at the end of
135    memory before they will be returned to the system.  */
136 #define FINAL_FREE_BLOCKS       8
137
138 /* Data structure giving per-block information.  */
139 typedef union
140   {
141     /* Heap information for a busy block.  */
142     struct
143       {
144         /* Zero for a large block, or positive giving the
145            logarithm to the base two of the fragment size.  */
146         int type;
147         union
148           {
149             struct
150               {
151                 __malloc_size_t nfree; /* Free frags in a fragmented block.  */
152                 __malloc_size_t first; /* First free fragment of the block.  */
153               } frag;
154             /* Size (in blocks) of a large cluster.  */
155             __malloc_size_t size;
156           } info;
157       } busy;
158     /* Heap information for a free block
159        (that may be the first of a free cluster).  */
160     struct
161       {
162         __malloc_size_t size;   /* Size (in blocks) of a free cluster.  */
163         __malloc_size_t next;   /* Index of next free cluster.  */
164         __malloc_size_t prev;   /* Index of previous free cluster.  */
165       } free;
166   } malloc_info;
167
168 /* Pointer to first block of the heap.  */
169 extern char *_heapbase;
170
171 /* Table indexed by block number giving per-block information.  */
172 extern malloc_info *_heapinfo;
173
174 /* Address to block number and vice versa.  */
175 #define BLOCK(A)        (((char *) (A) - _heapbase) / BLOCKSIZE + 1)
176 #define ADDRESS(B)      ((__ptr_t) (((B) - 1) * BLOCKSIZE + _heapbase))
177
178 /* Current search index for the heap table.  */
179 extern __malloc_size_t _heapindex;
180
181 /* Limit of valid info table indices.  */
182 extern __malloc_size_t _heaplimit;
183
184 /* Doubly linked lists of free fragments.  */
185 struct list
186 {
187   struct list *next;
188   struct list *prev;
189 };
190
191 /* Free list headers for each fragment size.  */
192 extern struct list _fraghead[];
193
194 /* List of blocks allocated with `memalign' (or `valloc').  */
195 struct alignlist
196 {
197   struct alignlist *next;
198   __ptr_t aligned;              /* The address that memaligned returned.  */
199   __ptr_t exact;                /* The address that malloc returned.  */
200 };
201 extern struct alignlist *_aligned_blocks;
202
203 /* Instrumentation.  */
204 extern __malloc_size_t _chunks_used;
205 extern __malloc_size_t _bytes_used;
206 extern __malloc_size_t _chunks_free;
207 extern __malloc_size_t _bytes_free;
208
209 /* Internal version of `free' used in `morecore' (malloc.c). */
210 extern void _free_internal __P ((__ptr_t __ptr));
211
212 #endif /* _MALLOC_INTERNAL.  */
213
214 /* Underlying allocation function; successive calls should
215    return contiguous pieces of memory.  */
216 extern __ptr_t (*__morecore) __P ((ptrdiff_t __size));
217
218 /* Default value of `__morecore'.  */
219 extern __ptr_t __default_morecore __P ((ptrdiff_t __size));
220
221 /* If not NULL, this function is called after each time
222    `__morecore' is called to increase the data size.  */
223 extern void (*__after_morecore_hook) __P ((void));
224
225 /* Nonzero if `malloc' has been called and done its initialization.  */
226     /* extern int __malloc_initialized; */
227
228 /* Hooks for debugging versions.  */
229 extern void (*__free_hook) __P ((__ptr_t __ptr));
230 extern __ptr_t (*__malloc_hook) __P ((size_t __size));
231 extern __ptr_t (*__realloc_hook) __P ((__ptr_t __ptr, size_t __size));
232
233 /* Return values for `mprobe': these are the kinds of inconsistencies that
234    `mcheck' enables detection of.  */
235 enum mcheck_status
236 {
237   MCHECK_DISABLED = -1,         /* Consistency checking is not turned on.  */
238   MCHECK_OK,                    /* Block is fine.  */
239   MCHECK_FREE,                  /* Block freed twice.  */
240   MCHECK_HEAD,                  /* Memory before the block was clobbered.  */
241   MCHECK_TAIL                   /* Memory after the block was clobbered.  */
242 };
243
244 /* Activate a standard collection of debugging hooks.  This must be called
245    before `malloc' is ever called.  ABORTFUNC is called with an error code
246    (see enum above) when an inconsistency is detected.  If ABORTFUNC is
247    null, the standard function prints on stderr and then calls `abort'.  */
248 extern int mcheck __P ((void (*__abortfunc) __P ((enum mcheck_status))));
249
250 /* Check for aberrations in a particular malloc'd block.  You must have
251    called `mcheck' already.  These are the same checks that `mcheck' does
252    when you free or reallocate a block.  */
253 extern enum mcheck_status mprobe __P ((__ptr_t __ptr));
254
255 /* Activate a standard collection of tracing hooks.  */
256 extern void mtrace __P ((void));
257 extern void muntrace __P ((void));
258
259 /* Statistics available to the user.  */
260 struct mstats
261 {
262   __malloc_size_t bytes_total;  /* Total size of the heap. */
263   __malloc_size_t chunks_used;  /* Chunks allocated by the user. */
264   __malloc_size_t bytes_used;   /* Byte total of user-allocated chunks. */
265   __malloc_size_t chunks_free;  /* Chunks in the free list. */
266   __malloc_size_t bytes_free;   /* Byte total of chunks in the free list. */
267 };
268
269 /* Pick up the current statistics. */
270 extern struct mstats mstats __P ((void));
271
272 /* Call WARNFUN with a warning message when memory usage is high.  */
273 extern void memory_warnings __P ((__ptr_t __start,
274                                   void (*__warnfun) __P ((const char *))));
275
276
277 #if 0 /* unused in this file, and conflicting prototypes anyway */
278 /* Relocating allocator.  */
279
280 /* Allocate SIZE bytes, and store the address in *HANDLEPTR.  */
281 extern __ptr_t r_alloc __P ((__ptr_t *__handleptr, size_t __size));
282
283 /* Free the storage allocated in HANDLEPTR.  */
284 extern void r_alloc_free __P ((__ptr_t *__handleptr));
285
286 /* Adjust the block at HANDLEPTR to be SIZE bytes long.  */
287 extern __ptr_t r_re_alloc __P ((__ptr_t *__handleptr, size_t __size));
288 #endif /* 0 */
289
290 #ifdef  __cplusplus
291 }
292 #endif
293
294 #endif /* malloc.h  */
295 /* Allocate memory on a page boundary.
296    Copyright (C) 1991, 1992, 1993, 1994 Free Software Foundation, Inc.
297
298 This library is free software; you can redistribute it and/or
299 modify it under the terms of the GNU Library General Public License as
300 published by the Free Software Foundation; either version 2 of the
301 License, or (at your option) any later version.
302
303 This library is distributed in the hope that it will be useful,
304 but WITHOUT ANY WARRANTY; without even the implied warranty of
305 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
306 Library General Public License for more details.
307
308 You should have received a copy of the GNU General Public License
309 along with this library; see the file COPYING.  If not, write to
310 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
311 Boston, MA 02111-1307, USA.
312
313    The author may be reached (Email) at the address mike@ai.mit.edu,
314    or (US mail) as Mike Haertel c/o Free Software Foundation, Inc.  */
315
316 #if defined (__GNU_LIBRARY__) || defined (_LIBC)
317 #include <stddef.h>
318 #include <sys/cdefs.h>
319 #if ! (defined (__GLIBC__) && (__GLIBC__ >= 2))
320 extern size_t __getpagesize __P ((void));
321 #endif
322 #else
323 #include "getpagesize.h"
324 #define  __getpagesize()        getpagesize()
325 #endif
326
327 #ifndef _MALLOC_INTERNAL
328 #define _MALLOC_INTERNAL
329 #include <malloc.h>
330 #endif
331
332 static __malloc_size_t pagesize;
333
334 __ptr_t
335 valloc (__malloc_size_t size)
336 {
337   if (pagesize == 0)
338     pagesize = __getpagesize ();
339
340   return memalign (pagesize, size);
341 }
342 /* Memory allocator `malloc'.
343    Copyright 1990, 1991, 1992, 1993, 1994 Free Software Foundation
344                   Written May 1989 by Mike Haertel.
345
346 This library is free software; you can redistribute it and/or
347 modify it under the terms of the GNU Library General Public License as
348 published by the Free Software Foundation; either version 2 of the
349 License, or (at your option) any later version.
350
351 This library is distributed in the hope that it will be useful,
352 but WITHOUT ANY WARRANTY; without even the implied warranty of
353 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
354 Library General Public License for more details.
355
356 You should have received a copy of the GNU General Public License
357 along with this library; see the file COPYING.  If not, write to
358 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
359 Boston, MA 02111-1307, USA.
360
361    The author may be reached (Email) at the address mike@ai.mit.edu,
362    or (US mail) as Mike Haertel c/o Free Software Foundation, Inc.  */
363
364 #ifndef _MALLOC_INTERNAL
365 #define _MALLOC_INTERNAL
366 #include <malloc.h>
367 #endif
368
369 /* How to really get more memory.  */
370 #if defined (HEAP_IN_DATA) && !defined(PDUMP)
371 /* once dumped, free() & realloc() on static heap space will fail */
372 #define PURE_DATA(x) \
373 ((static_heap_dumped && (char*)x >= static_heap_base \
374   && (char*)x <= (static_heap_base + static_heap_size) ) ? 1 : 0)
375 extern int initialized;
376 extern int purify_flag;
377 extern char* static_heap_base;
378 extern char* static_heap_ptr;
379 extern char* static_heap_dumped;
380 extern unsigned long static_heap_size;
381 extern __ptr_t more_static_core __P ((ptrdiff_t __size));
382 __ptr_t (*__morecore) __P ((ptrdiff_t __size)) = more_static_core;
383 #else
384 __ptr_t (*__morecore) __P ((ptrdiff_t __size)) = __default_morecore;
385 #define PURE_DATA(x) 0
386 #endif
387
388 /* Debugging hook for `malloc'.  */
389 __ptr_t (*__malloc_hook) __P ((__malloc_size_t __size));
390
391 /* Pointer to the base of the first block.  */
392 char *_heapbase;
393
394 /* Block information table.  Allocated with align/__free (not malloc/free).  */
395 malloc_info *_heapinfo;
396
397 /* Number of info entries.  */
398 static __malloc_size_t heapsize;
399
400 /* Search index in the info table.  */
401 __malloc_size_t _heapindex;
402
403 /* Limit of valid info table indices.  */
404 __malloc_size_t _heaplimit;
405
406 /* Free lists for each fragment size.  */
407 struct list _fraghead[BLOCKLOG];
408
409 /* Instrumentation.  */
410 __malloc_size_t _chunks_used;
411 __malloc_size_t _bytes_used;
412 __malloc_size_t _chunks_free;
413 __malloc_size_t _bytes_free;
414
415 /* Are you experienced?  */
416 int __malloc_initialized;
417
418 void (*__after_morecore_hook) __P ((void));
419
420 /* Aligned allocation.  */
421 static __ptr_t align __P ((__malloc_size_t));
422 static __ptr_t
423 align (__malloc_size_t size)
424 {
425   __ptr_t result;
426   unsigned long int adj;
427
428   result = (*__morecore) (size);
429   adj = (unsigned long int) ((unsigned long int) ((char *) result -
430                                                   (char *) NULL)) % BLOCKSIZE;
431   if (adj != 0)
432     {
433       adj = BLOCKSIZE - adj;
434       (void) (*__morecore) (adj);
435       result = (char *) result + adj;
436     }
437
438   if (__after_morecore_hook)
439     (*__after_morecore_hook) ();
440
441   return result;
442 }
443
444 /* Set everything up and remember that we have.  */
445 static int initialize __P ((void));
446 static int
447 initialize ()
448 {
449 #if defined (HEAP_IN_DATA) && !defined(PDUMP)
450   if (static_heap_dumped && __morecore == more_static_core)
451     {
452       __morecore = __default_morecore;
453     }
454 #endif
455   heapsize = HEAP / BLOCKSIZE;
456   _heapinfo = (malloc_info *) align (heapsize * sizeof (malloc_info));
457   if (_heapinfo == NULL)
458     return 0;
459   memset (_heapinfo, 0, heapsize * sizeof (malloc_info));
460   memset (_fraghead, 0, BLOCKLOG * sizeof (struct list));
461   _heapinfo[0].free.size = 0;
462   _heapinfo[0].free.next = _heapinfo[0].free.prev = 0;
463   _heapindex = 0;
464   _heaplimit = 0;
465   _heapbase = (char *) _heapinfo;
466
467   /* Account for the _heapinfo block itself in the statistics.  */
468   _bytes_used = heapsize * sizeof (malloc_info);
469   _chunks_used = 1;
470   _chunks_free=0;
471   _bytes_free=0;
472   _aligned_blocks=0;
473
474   __malloc_initialized = 1;
475   return 1;
476 }
477
478 /* Get neatly aligned memory, initializing or
479    growing the heap info table as necessary. */
480 static __ptr_t morecore __P ((__malloc_size_t));
481 static __ptr_t
482 morecore (__malloc_size_t size)
483 {
484   __ptr_t result;
485   malloc_info *newinfo, *oldinfo;
486   __malloc_size_t newsize;
487
488   result = align (size);
489   if (result == NULL)
490     return NULL;
491
492   /* Check if we need to grow the info table.  */
493   if ((__malloc_size_t) BLOCK ((char *) result + size) > heapsize)
494     {
495       newsize = heapsize;
496       while ((__malloc_size_t) BLOCK ((char *) result + size) > newsize)
497         newsize *= 2;
498       newinfo = (malloc_info *) align (newsize * sizeof (malloc_info));
499       if (newinfo == NULL)
500         {
501           (*__morecore) (-(int)size);
502           return NULL;
503         }
504       memcpy (newinfo, _heapinfo, heapsize * sizeof (malloc_info));
505       memset (&newinfo[heapsize], 0,
506               (newsize - heapsize) * sizeof (malloc_info));
507       oldinfo = _heapinfo;
508       newinfo[BLOCK (oldinfo)].busy.type = 0;
509       newinfo[BLOCK (oldinfo)].busy.info.size
510         = BLOCKIFY (heapsize * sizeof (malloc_info));
511       _heapinfo = newinfo;
512       /* Account for the _heapinfo block itself in the statistics.  */
513       _bytes_used += newsize * sizeof (malloc_info);
514       ++_chunks_used;
515       _free_internal (oldinfo);
516       heapsize = newsize;
517     }
518
519   _heaplimit = BLOCK ((char *) result + size);
520   return result;
521 }
522
523 /* Allocate memory from the heap.  */
524 __ptr_t
525 malloc (__malloc_size_t size)
526 {
527   __ptr_t result;
528   __malloc_size_t block, blocks, lastblocks, start;
529   __malloc_size_t i;
530   struct list *next;
531
532   /* ANSI C allows `malloc (0)' to either return NULL, or to return a
533      valid address you can realloc and free (though not dereference).
534
535      It turns out that some extant code (sunrpc, at least Ultrix's version)
536      expects `malloc (0)' to return non-NULL and breaks otherwise.
537      Be compatible.  */
538
539 #ifdef HAVE_X_WINDOWS
540   /* there is at least one Xt bug where calloc(n,x) is blindly called
541      where n can be 0, and yet if 0 is returned, Xt barfs */
542   if (size == 0)
543     size = sizeof (struct list);
544 #else
545   if (size == 0)
546     return NULL;
547 #endif
548
549   if (__malloc_hook != NULL)
550     return (*__malloc_hook) (size);
551
552   if (!__malloc_initialized)
553     if (!initialize ())
554       return NULL;
555
556 #ifdef SUNOS_LOCALTIME_BUG
557   /* Workaround for localtime() allocating 8 bytes and writing 9 bug... */
558   if (size < 16)
559     size = 16;
560 #endif
561
562   if (size < sizeof (struct list))
563       size = sizeof (struct list);
564
565   /* Determine the allocation policy based on the request size.  */
566   if (size <= BLOCKSIZE / 2)
567     {
568       /* Small allocation to receive a fragment of a block.
569          Determine the logarithm to base two of the fragment size. */
570       __malloc_size_t log = 1;
571       --size;
572       while ((size /= 2) != 0)
573         ++log;
574
575       /* Look in the fragment lists for a
576          free fragment of the desired size. */
577       next = _fraghead[log].next;
578       if (next != NULL)
579         {
580           /* There are free fragments of this size.
581              Pop a fragment out of the fragment list and return it.
582              Update the block's nfree and first counters. */
583           result = (__ptr_t) next;
584           next->prev->next = next->next;
585           if (next->next != NULL)
586             next->next->prev = next->prev;
587           block = BLOCK (result);
588           if (--_heapinfo[block].busy.info.frag.nfree != 0)
589             _heapinfo[block].busy.info.frag.first = (unsigned long int)
590               ((unsigned long int) ((char *) next->next - (char *) NULL)
591                % BLOCKSIZE) >> log;
592
593           /* Update the statistics.  */
594           ++_chunks_used;
595           _bytes_used += 1 << log;
596           --_chunks_free;
597           _bytes_free -= 1 << log;
598         }
599       else
600         {
601           /* No free fragments of the desired size, so get a new block
602              and break it into fragments, returning the first.  */
603           result = malloc (BLOCKSIZE);
604           if (result == NULL)
605             return NULL;
606
607           /* Link all fragments but the first into the free list.  */
608           for (i = 1; i < (__malloc_size_t) (BLOCKSIZE >> log); ++i)
609             {
610               next = (struct list *) ((char *) result + (i << log));
611               next->next = _fraghead[log].next;
612               next->prev = &_fraghead[log];
613               next->prev->next = next;
614               if (next->next != NULL)
615                 next->next->prev = next;
616             }
617
618           /* Initialize the nfree and first counters for this block.  */
619           block = BLOCK (result);
620           _heapinfo[block].busy.type = log;
621           _heapinfo[block].busy.info.frag.nfree = i - 1;
622           _heapinfo[block].busy.info.frag.first = i - 1;
623
624           _chunks_free += (BLOCKSIZE >> log) - 1;
625           _bytes_free += BLOCKSIZE - (1 << log);
626           _bytes_used -= BLOCKSIZE - (1 << log);
627         }
628     }
629   else
630     {
631       /* Large allocation to receive one or more blocks.
632          Search the free list in a circle starting at the last place visited.
633          If we loop completely around without finding a large enough
634          space we will have to get more memory from the system.  */
635       blocks = BLOCKIFY (size);
636       start = block = _heapindex;
637       while (_heapinfo[block].free.size < blocks)
638         {
639           block = _heapinfo[block].free.next;
640           if (block == start)
641             {
642               /* Need to get more from the system.  Check to see if
643                  the new core will be contiguous with the final free
644                  block; if so we don't need to get as much.  */
645               block = _heapinfo[0].free.prev;
646               lastblocks = _heapinfo[block].free.size;
647               if (_heaplimit != 0 && block + lastblocks == _heaplimit &&
648                   (*__morecore) (0) == ADDRESS (block + lastblocks) &&
649                   (morecore ((blocks - lastblocks) * BLOCKSIZE)) != NULL)
650                 {
651                   /* Which block we are extending (the `final free
652                      block' referred to above) might have changed, if
653                      it got combined with a freed info table.  */
654                   block = _heapinfo[0].free.prev;
655                   _heapinfo[block].free.size += (blocks - lastblocks);
656                   _bytes_free += (blocks - lastblocks) * BLOCKSIZE;
657                   continue;
658                 }
659               result = morecore (blocks * BLOCKSIZE);
660               if (result == NULL)
661                 return NULL;
662               block = BLOCK (result);
663               _heapinfo[block].busy.type = 0;
664               _heapinfo[block].busy.info.size = blocks;
665               ++_chunks_used;
666               _bytes_used += blocks * BLOCKSIZE;
667               return result;
668             }
669         }
670
671       /* At this point we have found a suitable free list entry.
672          Figure out how to remove what we need from the list. */
673       result = ADDRESS (block);
674       if (_heapinfo[block].free.size > blocks)
675         {
676           /* The block we found has a bit left over,
677              so relink the tail end back into the free list. */
678           _heapinfo[block + blocks].free.size
679             = _heapinfo[block].free.size - blocks;
680           _heapinfo[block + blocks].free.next
681             = _heapinfo[block].free.next;
682           _heapinfo[block + blocks].free.prev
683             = _heapinfo[block].free.prev;
684           _heapinfo[_heapinfo[block].free.prev].free.next
685             = _heapinfo[_heapinfo[block].free.next].free.prev
686             = _heapindex = block + blocks;
687         }
688       else
689         {
690           /* The block exactly matches our requirements,
691              so just remove it from the list. */
692           _heapinfo[_heapinfo[block].free.next].free.prev
693             = _heapinfo[block].free.prev;
694           _heapinfo[_heapinfo[block].free.prev].free.next
695             = _heapindex = _heapinfo[block].free.next;
696           --_chunks_free;
697         }
698
699       _heapinfo[block].busy.type = 0;
700       _heapinfo[block].busy.info.size = blocks;
701       ++_chunks_used;
702       _bytes_used += blocks * BLOCKSIZE;
703       _bytes_free -= blocks * BLOCKSIZE;
704     }
705
706   return result;
707 }
708 \f
709 #ifndef _LIBC
710
711 /* On some ANSI C systems, some libc functions call _malloc, _free
712    and _realloc.  Make them use the GNU functions.  */
713
714 __ptr_t _malloc (__malloc_size_t size);
715 __ptr_t
716 _malloc (__malloc_size_t size)
717 {
718   return malloc (size);
719 }
720
721 void _free (__ptr_t ptr);
722 void
723 _free (__ptr_t ptr)
724 {
725   free (ptr);
726 }
727
728 __ptr_t _realloc (__ptr_t ptr, __malloc_size_t size);
729 __ptr_t
730 _realloc (__ptr_t ptr, __malloc_size_t size)
731 {
732   return realloc (ptr, size);
733 }
734
735 #endif
736 /* Free a block of memory allocated by `malloc'.
737    Copyright 1990, 1991, 1992, 1994 Free Software Foundation
738                   Written May 1989 by Mike Haertel.
739
740 This library is free software; you can redistribute it and/or
741 modify it under the terms of the GNU Library General Public License as
742 published by the Free Software Foundation; either version 2 of the
743 License, or (at your option) any later version.
744
745 This library is distributed in the hope that it will be useful,
746 but WITHOUT ANY WARRANTY; without even the implied warranty of
747 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
748 Library General Public License for more details.
749
750 You should have received a copy of the GNU General Public License
751 along with this library; see the file COPYING.  If not, write to
752 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
753 Boston, MA 02111-1307, USA.
754
755    The author may be reached (Email) at the address mike@ai.mit.edu,
756    or (US mail) as Mike Haertel c/o Free Software Foundation, Inc.  */
757
758 #ifndef _MALLOC_INTERNAL
759 #define _MALLOC_INTERNAL
760 #include <malloc.h>
761 #endif
762
763 /* Debugging hook for free.  */
764 void (*__free_hook) __P ((__ptr_t __ptr));
765
766 /* List of blocks allocated by memalign.  */
767 struct alignlist *_aligned_blocks = NULL;
768
769 /* Return memory to the heap.
770    Like `free' but don't call a __free_hook if there is one.  */
771 void
772 _free_internal (__ptr_t ptr)
773 {
774   int type;
775   __malloc_size_t block, blocks;
776   __malloc_size_t i;
777   struct list *prev, *next;
778
779   block = BLOCK (ptr);
780
781   type = _heapinfo[block].busy.type;
782   switch (type)
783     {
784     case 0:
785       /* Get as many statistics as early as we can.  */
786       --_chunks_used;
787       _bytes_used -= _heapinfo[block].busy.info.size * BLOCKSIZE;
788       _bytes_free += _heapinfo[block].busy.info.size * BLOCKSIZE;
789
790       /* Find the free cluster previous to this one in the free list.
791          Start searching at the last block referenced; this may benefit
792          programs with locality of allocation.  */
793       i = _heapindex;
794       if (i > block)
795         while (i > block)
796           i = _heapinfo[i].free.prev;
797       else
798         {
799           do
800             i = _heapinfo[i].free.next;
801           while (i > 0 && i < block);
802           i = _heapinfo[i].free.prev;
803         }
804
805       /* Determine how to link this block into the free list.  */
806       if (block == i + _heapinfo[i].free.size)
807         {
808           /* Coalesce this block with its predecessor.  */
809           _heapinfo[i].free.size += _heapinfo[block].busy.info.size;
810           block = i;
811         }
812       else
813         {
814           /* Really link this block back into the free list.  */
815           _heapinfo[block].free.size = _heapinfo[block].busy.info.size;
816           _heapinfo[block].free.next = _heapinfo[i].free.next;
817           _heapinfo[block].free.prev = i;
818           _heapinfo[i].free.next = block;
819           _heapinfo[_heapinfo[block].free.next].free.prev = block;
820           ++_chunks_free;
821         }
822
823       /* Now that the block is linked in, see if we can coalesce it
824          with its successor (by deleting its successor from the list
825          and adding in its size).  */
826       if (block + _heapinfo[block].free.size == _heapinfo[block].free.next)
827         {
828           _heapinfo[block].free.size
829             += _heapinfo[_heapinfo[block].free.next].free.size;
830           _heapinfo[block].free.next
831             = _heapinfo[_heapinfo[block].free.next].free.next;
832           _heapinfo[_heapinfo[block].free.next].free.prev = block;
833           --_chunks_free;
834         }
835
836       /* Now see if we can return stuff to the system.  */
837       blocks = _heapinfo[block].free.size;
838       if (blocks >= FINAL_FREE_BLOCKS && block + blocks == _heaplimit
839           && (*__morecore) (0) == ADDRESS (block + blocks))
840         {
841           __malloc_size_t bytes = blocks * BLOCKSIZE;
842           _heaplimit -= blocks;
843           (*__morecore) (-(int)bytes);
844           _heapinfo[_heapinfo[block].free.prev].free.next
845             = _heapinfo[block].free.next;
846           _heapinfo[_heapinfo[block].free.next].free.prev
847             = _heapinfo[block].free.prev;
848           block = _heapinfo[block].free.prev;
849           --_chunks_free;
850           _bytes_free -= bytes;
851         }
852
853       /* Set the next search to begin at this block.  */
854       _heapindex = block;
855       break;
856
857     default:
858       /* Do some of the statistics.  */
859       --_chunks_used;
860       _bytes_used -= 1 << type;
861       ++_chunks_free;
862       _bytes_free += 1 << type;
863
864       /* Get the address of the first free fragment in this block.  */
865       prev = (struct list *) ((char *) ADDRESS (block) +
866                            (_heapinfo[block].busy.info.frag.first << type));
867
868       if (_heapinfo[block].busy.info.frag.nfree == (BLOCKSIZE >> type) - 1)
869         {
870           /* If all fragments of this block are free, remove them
871              from the fragment list and free the whole block.  */
872           next = prev;
873           for (i = 1; i < (__malloc_size_t) (BLOCKSIZE >> type); ++i)
874             next = next->next;
875           prev->prev->next = next;
876           if (next != NULL)
877             next->prev = prev->prev;
878           _heapinfo[block].busy.type = 0;
879           _heapinfo[block].busy.info.size = 1;
880
881           /* Keep the statistics accurate.  */
882           ++_chunks_used;
883           _bytes_used += BLOCKSIZE;
884           _chunks_free -= BLOCKSIZE >> type;
885           _bytes_free -= BLOCKSIZE;
886
887           free (ADDRESS (block));
888         }
889       else if (_heapinfo[block].busy.info.frag.nfree != 0)
890         {
891           /* If some fragments of this block are free, link this
892              fragment into the fragment list after the first free
893              fragment of this block. */
894           next = (struct list *) ptr;
895           next->next = prev->next;
896           next->prev = prev;
897           prev->next = next;
898           if (next->next != NULL)
899             next->next->prev = next;
900           ++_heapinfo[block].busy.info.frag.nfree;
901         }
902       else
903         {
904           /* No fragments of this block are free, so link this
905              fragment into the fragment list and announce that
906              it is the first free fragment of this block. */
907           prev = (struct list *) ptr;
908           _heapinfo[block].busy.info.frag.nfree = 1;
909           _heapinfo[block].busy.info.frag.first = (unsigned long int)
910             ((unsigned long int) ((char *) ptr - (char *) NULL)
911              % BLOCKSIZE >> type);
912           prev->next = _fraghead[type].next;
913           prev->prev = &_fraghead[type];
914           prev->prev->next = prev;
915           if (prev->next != NULL)
916             prev->next->prev = prev;
917         }
918       break;
919     }
920 }
921
922 /* Return memory to the heap.  */
923 __free_ret_t
924 free (__ptr_t ptr)
925 {
926   struct alignlist *l;
927
928   if (ptr == NULL)
929     return;
930
931   if (PURE_DATA(ptr))
932     {
933       return;
934     }
935
936   for (l = _aligned_blocks; l != NULL; l = l->next)
937     if (l->aligned == ptr)
938       {
939         l->aligned = NULL;      /* Mark the slot in the list as free.  */
940         ptr = l->exact;
941         break;
942       }
943
944   if (__free_hook != NULL)
945     (*__free_hook) (ptr);
946   else
947     _free_internal (ptr);
948 }
949 /* Copyright (C) 1991, 1993, 1994 Free Software Foundation, Inc.
950 This file is part of the GNU C Library.
951
952 The GNU C Library is free software; you can redistribute it and/or
953 modify it under the terms of the GNU Library General Public License as
954 published by the Free Software Foundation; either version 2 of the
955 License, or (at your option) any later version.
956
957 The GNU C Library is distributed in the hope that it will be useful,
958 but WITHOUT ANY WARRANTY; without even the implied warranty of
959 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
960 Library General Public License for more details.
961
962 You should have received a copy of the GNU General Public License
963 along with this library; see the file COPYING.  If not, write to
964 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
965 Boston, MA 02111-1307, USA. */
966
967 #ifndef _MALLOC_INTERNAL
968 #define _MALLOC_INTERNAL
969 #include <malloc.h>
970 #endif
971
972 #ifdef _LIBC
973
974 #include <ansidecl.h>
975 #include <gnu-stabs.h>
976
977 #undef  cfree
978
979 function_alias(cfree, free, void, (ptr),
980                DEFUN(cfree, (ptr), PTR ptr))
981
982 #else
983
984 void cfree (__ptr_t ptr);
985 void
986 cfree (__ptr_t ptr)
987 {
988   free (ptr);
989 }
990
991 #endif
992 /* Change the size of a block allocated by `malloc'.
993    Copyright 1990, 1991, 1992, 1993, 1994 Free Software Foundation, Inc.
994                      Written May 1989 by Mike Haertel.
995
996 This library is free software; you can redistribute it and/or
997 modify it under the terms of the GNU Library General Public License as
998 published by the Free Software Foundation; either version 2 of the
999 License, or (at your option) any later version.
1000
1001 This library is distributed in the hope that it will be useful,
1002 but WITHOUT ANY WARRANTY; without even the implied warranty of
1003 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
1004 Library General Public License for more details.
1005
1006 You should have received a copy of the GNU General Public License
1007 along with this library; see the file COPYING.  If not, write to
1008 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
1009 Boston, MA 02111-1307, USA.
1010
1011    The author may be reached (Email) at the address mike@ai.mit.edu,
1012    or (US mail) as Mike Haertel c/o Free Software Foundation, Inc.  */
1013
1014 #ifndef _MALLOC_INTERNAL
1015 #define _MALLOC_INTERNAL
1016 #include <malloc.h>
1017 #endif
1018
1019 #ifndef min
1020 #define min(A, B) ((A) < (B) ? (A) : (B))
1021 #endif
1022
1023 /* Debugging hook for realloc.  */
1024 __ptr_t (*__realloc_hook) __P ((__ptr_t __ptr, __malloc_size_t __size));
1025
1026 /* Resize the given region to the new size, returning a pointer
1027    to the (possibly moved) region.  This is optimized for speed;
1028    some benchmarks seem to indicate that greater compactness is
1029    achieved by unconditionally allocating and copying to a
1030    new region.  This module has incestuous knowledge of the
1031    internals of both free and malloc. */
1032 __ptr_t
1033 realloc (__ptr_t ptr, __malloc_size_t size)
1034 {
1035   __ptr_t result;
1036   int type;
1037   __malloc_size_t block, blocks, oldlimit;
1038
1039   if (PURE_DATA (ptr))
1040     {
1041       result = malloc (size);
1042       memcpy(result, ptr, size);
1043       return result;
1044     }
1045   
1046   else if (size == 0)
1047     {
1048       free (ptr);
1049       return malloc (0);
1050     }
1051   else if (ptr == NULL)
1052     return malloc (size);
1053
1054   if (__realloc_hook != NULL)
1055     return (*__realloc_hook) (ptr, size);
1056
1057   block = BLOCK (ptr);
1058
1059   type = _heapinfo[block].busy.type;
1060   switch (type)
1061     {
1062     case 0:
1063       /* Maybe reallocate a large block to a small fragment.  */
1064       if (size <= BLOCKSIZE / 2)
1065         {
1066           result = malloc (size);
1067           if (result != NULL)
1068             {
1069               memcpy (result, ptr, size);
1070               _free_internal (ptr);
1071               return result;
1072             }
1073         }
1074
1075       /* The new size is a large allocation as well;
1076          see if we can hold it in place. */
1077       blocks = BLOCKIFY (size);
1078       if (blocks < _heapinfo[block].busy.info.size)
1079         {
1080           /* The new size is smaller; return
1081              excess memory to the free list. */
1082           _heapinfo[block + blocks].busy.type = 0;
1083           _heapinfo[block + blocks].busy.info.size
1084             = _heapinfo[block].busy.info.size - blocks;
1085           _heapinfo[block].busy.info.size = blocks;
1086           /* We have just created a new chunk by splitting a chunk in two.
1087              Now we will free this chunk; increment the statistics counter
1088              so it doesn't become wrong when _free_internal decrements it.  */
1089           ++_chunks_used;
1090           _free_internal (ADDRESS (block + blocks));
1091           result = ptr;
1092         }
1093       else if (blocks == _heapinfo[block].busy.info.size)
1094         /* No size change necessary.  */
1095         result = ptr;
1096       else
1097         {
1098           /* Won't fit, so allocate a new region that will.
1099              Free the old region first in case there is sufficient
1100              adjacent free space to grow without moving. */
1101           blocks = _heapinfo[block].busy.info.size;
1102           /* Prevent free from actually returning memory to the system.  */
1103           oldlimit = _heaplimit;
1104           _heaplimit = 0;
1105           free (ptr);
1106           _heaplimit = oldlimit;
1107           result = malloc (size);
1108           if (result == NULL)
1109             {
1110               /* Now we're really in trouble.  We have to unfree
1111                  the thing we just freed.  Unfortunately it might
1112                  have been coalesced with its neighbors.  */
1113               if (_heapindex == block)
1114                 (void) malloc (blocks * BLOCKSIZE);
1115               else
1116                 {
1117                   __ptr_t previous = malloc ((block - _heapindex) * BLOCKSIZE);
1118                   (void) malloc (blocks * BLOCKSIZE);
1119                   free (previous);
1120                 }
1121               return NULL;
1122             }
1123           if (ptr != result)
1124             memmove (result, ptr, blocks * BLOCKSIZE);
1125         }
1126       break;
1127
1128     default:
1129       /* Old size is a fragment; type is logarithm
1130          to base two of the fragment size.  */
1131       if (size > (__malloc_size_t) (1 << (type - 1)) &&
1132           size <= (__malloc_size_t) (1 << type))
1133         /* The new size is the same kind of fragment.  */
1134         result = ptr;
1135       else
1136         {
1137           /* The new size is different; allocate a new space,
1138              and copy the lesser of the new size and the old. */
1139           result = malloc (size);
1140           if (result == NULL)
1141             return NULL;
1142           memcpy (result, ptr, min (size, (__malloc_size_t) 1 << type));
1143           free (ptr);
1144         }
1145       break;
1146     }
1147
1148   return result;
1149 }
1150 /* Copyright (C) 1991, 1992, 1994 Free Software Foundation, Inc.
1151
1152 This library is free software; you can redistribute it and/or
1153 modify it under the terms of the GNU Library General Public License as
1154 published by the Free Software Foundation; either version 2 of the
1155 License, or (at your option) any later version.
1156
1157 This library is distributed in the hope that it will be useful,
1158 but WITHOUT ANY WARRANTY; without even the implied warranty of
1159 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
1160 Library General Public License for more details.
1161
1162 You should have received a copy of the GNU General Public License
1163 along with this library; see the file COPYING.  If not, write to
1164 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
1165 Boston, MA 02111-1307, USA.
1166
1167    The author may be reached (Email) at the address mike@ai.mit.edu,
1168    or (US mail) as Mike Haertel c/o Free Software Foundation, Inc.  */
1169
1170 #ifndef _MALLOC_INTERNAL
1171 #define _MALLOC_INTERNAL
1172 #include <malloc.h>
1173 #endif
1174
1175 /* Allocate an array of NMEMB elements each SIZE bytes long.
1176    The entire array is initialized to zeros.  */
1177 __ptr_t
1178 calloc (__malloc_size_t nmemb, __malloc_size_t size)
1179 {
1180   __ptr_t result = malloc (nmemb * size);
1181
1182   if (result != NULL)
1183     (void) memset (result, 0, nmemb * size);
1184
1185   return result;
1186 }
1187 /* Copyright (C) 1991, 1992, 1993, 1994 Free Software Foundation, Inc.
1188 This file is part of the GNU C Library.
1189
1190 The GNU C Library is free software; you can redistribute it and/or modify
1191 it under the terms of the GNU General Public License as published by
1192 the Free Software Foundation; either version 2, or (at your option)
1193 any later version.
1194
1195 The GNU C Library is distributed in the hope that it will be useful,
1196 but WITHOUT ANY WARRANTY; without even the implied warranty of
1197 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
1198 GNU General Public License for more details.
1199
1200 You should have received a copy of the GNU General Public License
1201 along with the GNU C Library; see the file COPYING.  If not, write to
1202 the Free the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
1203 Boston, MA 02111-1307, USA.  */
1204
1205 #ifndef _MALLOC_INTERNAL
1206 #define _MALLOC_INTERNAL
1207 #include <malloc.h>
1208 #endif
1209
1210 /* #ifndef      __GNU_LIBRARY__ */
1211 #define __sbrk  sbrk
1212 /* #endif */
1213
1214 #ifdef GMALLOC_NEEDS_SBRK_DECL
1215 /* some versions of OSF1 need this */
1216 extern __ptr_t __sbrk __P ((ssize_t increment));
1217 #else
1218 #ifdef __GNU_LIBRARY__
1219 /* It is best not to declare this and cast its result on foreign operating
1220    systems with potentially hostile include files.  */
1221 #if !(defined(linux) && defined(sparc))
1222 extern __ptr_t __sbrk __P ((int increment));
1223 #endif
1224 #endif
1225 #endif
1226
1227 #ifndef NULL
1228 #define NULL 0
1229 #endif
1230
1231 /* Allocate INCREMENT more bytes of data space,
1232    and return the start of data space, or NULL on errors.
1233    If INCREMENT is negative, shrink data space.  */
1234 __ptr_t
1235 __default_morecore (ptrdiff_t increment)
1236 {
1237   __ptr_t result = (__ptr_t) __sbrk (increment);
1238   if (result == (__ptr_t) -1)
1239     return NULL;
1240   return result;
1241 }
1242 /* Copyright (C) 1991, 1992, 1993, 1994 Free Software Foundation, Inc.
1243
1244 This library is free software; you can redistribute it and/or
1245 modify it under the terms of the GNU Library General Public License as
1246 published by the Free Software Foundation; either version 2 of the
1247 License, or (at your option) any later version.
1248
1249 This library is distributed in the hope that it will be useful,
1250 but WITHOUT ANY WARRANTY; without even the implied warranty of
1251 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
1252 Library General Public License for more details.
1253
1254 You should have received a copy of the GNU General Public License
1255 along with this library; see the file COPYING.  If not, write to
1256 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
1257 Boston, MA 02111-1307, USA. */
1258
1259 #ifndef _MALLOC_INTERNAL
1260 #define _MALLOC_INTERNAL
1261 #include <malloc.h>
1262 #endif
1263
1264 __ptr_t
1265 memalign (__malloc_size_t alignment, __malloc_size_t size)
1266 {
1267   __ptr_t result;
1268   unsigned long int adj;
1269
1270   size = ((size + alignment - 1) / alignment) * alignment;
1271
1272   result = malloc (size);
1273   if (result == NULL)
1274     return NULL;
1275   adj = (unsigned long int) ((unsigned long int) ((char *) result -
1276                                                   (char *) NULL)) % alignment;
1277   if (adj != 0)
1278     {
1279       struct alignlist *l;
1280       for (l = _aligned_blocks; l != NULL; l = l->next)
1281         if (l->aligned == NULL)
1282           /* This slot is free.  Use it.  */
1283           break;
1284       if (l == NULL)
1285         {
1286           l = (struct alignlist *) malloc (sizeof (struct alignlist));
1287           if (l == NULL)
1288             {
1289               free (result);
1290               return NULL;
1291             }
1292           l->next = _aligned_blocks;
1293           _aligned_blocks = l;
1294         }
1295       l->exact = result;
1296       result = l->aligned = (char *) result + alignment - adj;
1297     }
1298
1299   return result;
1300 }