home *** CD-ROM | disk | FTP | other *** search
/ Frozen Fish 1: Amiga / FrozenFish-Apr94.iso / bbs / gnu / binutils-1.8.x.tar.gz / binutils-1.8.x.tar / binutils / gmalloc.old < prev    next >
Text File  |  1991-11-27  |  33KB  |  1,123 lines
  1.  
  2. /* gmalloc.c - THIS FILE IS AUTOMAGICALLY GENERATED SO DON'T EDIT IT. */
  3.  
  4. /* Single-file skeleton for GNU malloc.
  5.    Copyright 1989 Free Software Foundation
  6.           Written May 1989 by Mike Haertel.
  7.  
  8.    This program is free software; you can redistribute it and/or modify
  9.    it under the terms of the GNU General Public License as published by
  10.    the Free Software Foundation; either version 1, or (at your option)
  11.    any later version.
  12.  
  13.    This program is distributed in the hope that it will be useful,
  14.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16.    GNU General Public License for more details.
  17.  
  18.    You should have received a copy of the GNU General Public License
  19.    along with this program; if not, write to the Free Software
  20.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21.  
  22.    The author may be reached (Email) at the address mike@ai.mit.edu,
  23.    or (US mail) as Mike Haertel c/o Free Software Foundation. */
  24.  
  25. #define __ONEFILE
  26.  
  27. /* DO NOT DELETE THIS LINE -- ansidecl.h INSERTED HERE. */
  28. /* Copyright (C) 1989 Free Software Foundation, Inc.
  29. This file is part of the GNU C Library.
  30.  
  31. The GNU C Library is free software; you can redistribute it and/or modify
  32. it under the terms of the GNU General Public License as published by
  33. the Free Software Foundation; either version 1, or (at your option)
  34. any later version.
  35.  
  36. The GNU C Library is distributed in the hope that it will be useful,
  37. but WITHOUT ANY WARRANTY; without even the implied warranty of
  38. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  39. GNU General Public License for more details.
  40.  
  41. You should have received a copy of the GNU General Public License
  42. along with the GNU C Library; see the file COPYING.  If not, write to
  43. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  44.  
  45. /* ANSI and traditional C compatibility macros
  46.  
  47.    ANSI C is assumed if __STDC__ is #defined.
  48.  
  49.     Macros
  50.         PTR        - Generic pointer type
  51.         LONG_DOUBLE    - `long double' type
  52.         CONST        - `const' keyword
  53.         VOLATILE    - `volatile' keyword
  54.         SIGNED        - `signed' keyword
  55.         PTRCONST    - Generic const pointer (void *const)
  56.  
  57.     EXFUN(name, prototype)        - declare external function NAME
  58.                       with prototype PROTOTYPE
  59.     DEFUN(name, arglist, args)    - define function NAME with
  60.                       args ARGLIST of types in ARGS
  61.     DEFUN_VOID(name)        - define function NAME with no args
  62.     AND                - argument separator for ARGS
  63.     NOARGS                - null arglist
  64.     DOTS                - `...' in args
  65.  
  66.     For example:
  67.     extern int EXFUN(printf, (CONST char *format DOTS));
  68.     int DEFUN(fprintf, (stream, format),
  69.           FILE *stream AND CONST char *format DOTS) { ... }
  70.     void DEFUN_VOID(abort) { ... }
  71. */
  72.  
  73. #ifdef WYSE
  74. #include <sys/types.h>
  75. #endif /* WYSE */
  76.  
  77. #ifndef    _ANSIDECL_H
  78.  
  79. #define    _ANSIDECL_H    1
  80.  
  81.  
  82. /* Every source file includes this file,
  83.    so they will all get the switch for lint.  */
  84. /* LINTLIBRARY */
  85.  
  86.  
  87. #ifdef    __STDC__
  88.  
  89. #define    PTR        void *
  90. #define    PTRCONST    void *CONST
  91. #define    LONG_DOUBLE    long double
  92.  
  93. #define    AND        ,
  94. #define    NOARGS        void
  95. #define    CONST        const
  96. #define    VOLATILE    volatile
  97. #define    SIGNED        signed
  98. #define    DOTS        , ...
  99.  
  100. #define    EXFUN(name, proto)        name proto
  101. #define    DEFUN(name, arglist, args)    name(args)
  102. #define    DEFUN_VOID(name)        name(NOARGS)
  103.  
  104. #else    /* Not ANSI C.  */
  105.  
  106. #define    PTR        char *
  107. #define    PTRCONST    PTR
  108. #define    LONG_DOUBLE    double
  109.  
  110. #define    AND        ;
  111. #define    NOARGS
  112. #define    CONST
  113. #define    VOLATILE
  114. #define    SIGNED
  115. #define    DOTS
  116.  
  117. #define    EXFUN(name, proto)        name()
  118. #define    DEFUN(name, arglist, args)    name arglist args;
  119. #define    DEFUN_VOID(name)        name()
  120.  
  121. #endif    /* ANSI C.  */
  122.  
  123.  
  124. #endif    /* ansidecl.h    */
  125.  
  126. #ifdef __STDC__
  127. #include <limits.h>
  128. #else
  129. /* DO NOT DELETE THIS LINE -- limits.h INSERTED HERE. */
  130. /* Number of bits in a `char'.  */
  131. #define CHAR_BIT 8
  132.  
  133. /* No multibyte characters supported yet.  */
  134. #define MB_LEN_MAX 1
  135.  
  136. /* Minimum and maximum values a `signed char' can hold.  */
  137. #define SCHAR_MIN -128
  138. #define SCHAR_MAX 127
  139.  
  140. /* Maximum value an `unsigned char' can hold.  (Minimum is 0).  */
  141. #define UCHAR_MAX 255U
  142.  
  143. /* Minimum and maximum values a `char' can hold.  */
  144. #ifdef __CHAR_UNSIGNED__
  145. #define CHAR_MIN 0
  146. #define CHAR_MAX 255U
  147. #else
  148. #define CHAR_MIN -128
  149. #define CHAR_MAX 127
  150. #endif
  151.  
  152. /* Minimum and maximum values a `signed short int' can hold.  */
  153. #define SHRT_MIN -32768
  154. #define SHRT_MAX 32767
  155.  
  156. /* Maximum value an `unsigned short int' can hold.  (Minimum is 0).  */
  157. #define USHRT_MAX 65535U
  158.  
  159. /* Minimum and maximum values a `signed int' can hold.  */
  160. #define INT_MIN -2147483648
  161. #define INT_MAX 2147483647
  162.  
  163. /* Maximum value an `unsigned int' can hold.  (Minimum is 0).  */
  164. #define UINT_MAX 4294967295U
  165.  
  166. /* Minimum and maximum values a `signed long int' can hold.
  167.    (Same as `int').  */
  168. #define LONG_MIN (-LONG_MAX-1)
  169. #define LONG_MAX 2147483647
  170.  
  171. /* Maximum value an `unsigned long int' can hold.  (Minimum is 0).  */
  172. #define ULONG_MAX 4294967295U
  173. #endif
  174.  
  175. #ifdef __STDC__
  176. #ifndef WYSE
  177. #include <stddef.h>
  178. #endif /* WYSE */
  179. #else
  180. /* DO NOT DELETE THIS LINE -- stddef.h INSERTED HERE. */
  181. #ifndef _STDDEF_H
  182. #define _STDDEF_H
  183.  
  184. /* Signed type of difference of two pointers.  */
  185.  
  186. typedef long ptrdiff_t;
  187.  
  188. /* Unsigned type of `sizeof' something.  */
  189.  
  190. #ifndef _SIZE_T    /* in case <sys/types.h> has defined it. */
  191. #define _SIZE_T
  192. typedef unsigned long size_t;
  193. #endif /* _SIZE_T */
  194.  
  195. /* A null pointer constant.  */
  196.  
  197. #undef NULL        /* in case <stdio.h> has defined it. */
  198. #define NULL 0
  199.  
  200. /* Offset of member MEMBER in a struct of type TYPE.  */
  201.  
  202. #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
  203.  
  204. #endif /* _STDDEF_H */
  205. #endif
  206.  
  207. /* DO NOT DELETE THIS LINE -- stdlib.h INSERTED HERE. */
  208. /* Fake stdlib.h supplying the stuff needed by malloc. */
  209.  
  210. #ifndef __ONEFILE
  211. #include <stddef.h>
  212. #endif
  213.  
  214. extern void EXFUN(abort, (void));
  215. extern void EXFUN(free, (PTR));
  216. extern PTR EXFUN(malloc, (size_t));
  217. extern PTR EXFUN(realloc, (PTR, size_t));
  218.  
  219. /* DO NOT DELETE THIS LINE -- string.h INSERTED HERE. */
  220. /* Fake string.h supplying stuff used by malloc. */
  221. #ifndef __ONEFILE
  222. #include <stddef.h>
  223. #endif
  224.  
  225. extern PTR EXFUN(memcpy, (PTR, PTR, size_t));
  226. extern PTR EXFUN(memset, (PTR, int, size_t));
  227. #define memmove memcpy
  228.  
  229. #define _MALLOC_INTERNAL
  230. /* DO NOT DELETE THIS LINE -- malloc.h INSERTED HERE. */
  231. /* Declarations for `malloc' and friends.
  232.    Copyright 1990 Free Software Foundation
  233.           Written May 1989 by Mike Haertel.
  234.  
  235.    This program is free software; you can redistribute it and/or modify
  236.    it under the terms of the GNU General Public License as published by
  237.    the Free Software Foundation; either version 1, or (at your option)
  238.    any later version.
  239.  
  240.    This program is distributed in the hope that it will be useful,
  241.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  242.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  243.    GNU General Public License for more details.
  244.  
  245.    You should have received a copy of the GNU General Public License
  246.    along with this program; if not, write to the Free Software
  247.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  248.  
  249.    The author may be reached (Email) at the address mike@@ai.mit.edu,
  250.    or (US mail) as Mike Haertel c/o Free Software Foundation. */
  251.  
  252. #ifndef _MALLOC_H
  253.  
  254. #define _MALLOC_H    1
  255.  
  256. #ifndef __ONEFILE
  257. #define    __need_NULL
  258. #define    __need_size_t
  259. #define __need_ptrdiff_t
  260. #include <stddef.h>
  261. #endif
  262.  
  263. #ifdef _MALLOC_INTERNAL
  264.  
  265. #ifndef __ONEFILE
  266. #include <limits.h>
  267. #endif
  268.  
  269. /* The allocator divides the heap into blocks of fixed size; large
  270.    requests receive one or more whole blocks, and small requests
  271.    receive a fragment of a block.  Fragment sizes are powers of two,
  272.    and all fragments of a block are the same size.  When all the
  273.    fragments in a block have been freed, the block itself is freed.  */
  274. #define INT_BIT        (CHAR_BIT * sizeof(int))
  275. #define BLOCKLOG    (INT_BIT > 16 ? 12 : 9)
  276. #define BLOCKSIZE    (1 << BLOCKLOG)
  277. #define BLOCKIFY(SIZE)    (((SIZE) + BLOCKSIZE - 1) / BLOCKSIZE)
  278.  
  279. /* Determine the amount of memory spanned by the initial heap table
  280.    (not an absolute limit).  */
  281. #define HEAP        (INT_BIT > 16 ? 4194304 : 65536)
  282.  
  283. /* Number of contiguous free blocks allowed to build up at the end of
  284.    memory before they will be returned to the system.  */
  285. #define FINAL_FREE_BLOCKS    8
  286.  
  287. /* Where to start searching the free list when looking for new memory.
  288.    The two possible values are 0 and _heapindex.  Starting at 0 seems
  289.    to reduce total memory usage, while starting at _heapindex seems to
  290.    run faster.  */
  291. #define MALLOC_SEARCH_START    _heapindex
  292.  
  293. /* Data structure giving per-block information.  */
  294. typedef union
  295.   {
  296.     /* Heap information for a busy block.  */
  297.     struct
  298.       {
  299.     /* Zero for a large block, or positive giving the
  300.        logarithm to the base two of the fragment size.  */
  301.     int type;
  302.     union
  303.       {
  304.         struct
  305.           {
  306.         size_t nfree;    /* Free fragments in a fragmented block.  */
  307.         size_t first;    /* First free fragment of the block.  */
  308.           } frag;
  309.         /* Size (in blocks) of a large cluster.  */
  310.         size_t size;
  311.       } info;
  312.       } busy;
  313.     /* Heap information for a free block (that may be the first of
  314.        a free cluster).  */
  315.     struct
  316.       {
  317.     size_t size;        /* Size (in blocks) of a free cluster.  */
  318.     size_t next;        /* Index of next free cluster.  */
  319.     size_t prev;        /* Index of previous free cluster.  */
  320.       } free;
  321.   } malloc_info;
  322.  
  323. /* Pointer to first block of the heap.  */
  324. extern char *_heapbase;
  325.  
  326. /* Table indexed by block number giving per-block information.  */
  327. extern malloc_info *_heapinfo;
  328.  
  329. /* Address to block number and vice versa.  */
  330. #define BLOCK(A) (((char *) (A) - _heapbase) / BLOCKSIZE + 1)
  331. #define ADDRESS(B) ((PTR) (((B) - 1) * BLOCKSIZE + _heapbase))
  332.  
  333. /* Current search index for the heap table.  */
  334. extern size_t _heapindex;
  335.  
  336. /* Limit of valid info table indices.  */
  337. extern size_t _heaplimit;
  338.  
  339. /* Doubly linked lists of free fragments.  */
  340. struct list
  341.   {
  342.     struct list *next;
  343.     struct list *prev;
  344.   };
  345.  
  346. /* Free list headers for each fragment size.  */
  347. extern struct list _fraghead[];
  348.  
  349. /* Instrumentation.  */
  350. extern size_t _chunks_used;
  351. extern size_t _bytes_used;
  352. extern size_t _chunks_free;
  353. extern size_t _bytes_free;
  354.  
  355. /* Internal version of free() used in morecore(). */
  356. extern void EXFUN(__free, (PTR __ptr));
  357.  
  358. #endif  /* _MALLOC_INTERNAL.  */
  359.  
  360. /* Underlying allocation function; successive calls should
  361.    return contiguous pieces of memory.  */
  362. extern PTR EXFUN((*__morecore), (ptrdiff_t __size));
  363.  
  364. /* Default value of previous.  */
  365. extern PTR EXFUN(__default_morecore, (ptrdiff_t __size));
  366.  
  367. /* Flag whether malloc has been called.  */
  368. extern int __malloc_initialized;
  369.  
  370. /* Hooks for debugging versions.  */
  371. extern void EXFUN((*__free_hook), (PTR __ptr));
  372. extern PTR EXFUN((*__malloc_hook), (size_t __size));
  373. extern PTR EXFUN((*__realloc_hook), (PTR __ptr, size_t __size));
  374.  
  375. /* Activate a standard collection of debugging hooks.  */
  376. extern void EXFUN(mcheck, (void EXFUN((*func), (void))));
  377.  
  378. /* Statistics available to the user.  */
  379. struct mstats
  380.   {
  381.     size_t bytes_total;        /* Total size of the heap. */
  382.     size_t chunks_used;        /* Chunks allocated by the user. */
  383.     size_t bytes_used;        /* Byte total of user-allocated chunks. */
  384.     size_t chunks_free;        /* Chunks in the free list. */
  385.     size_t bytes_free;        /* Byte total of chunks in the free list. */
  386.   };
  387.  
  388. /* Pick up the current statistics. */
  389. extern struct mstats EXFUN(mstats, (NOARGS));
  390.  
  391. #endif /* malloc.h  */
  392.  
  393. /* DO NOT DELETE THIS LINE -- free.c INSERTED HERE. */
  394. /* Free a block of memory allocated by `malloc'.
  395.    Copyright 1990 Free Software Foundation
  396.           Written May 1989 by Mike Haertel.
  397.  
  398.    This program is free software; you can redistribute it and/or modify
  399.    it under the terms of the GNU General Public License as published by
  400.    the Free Software Foundation; either version 1, or (at your option)
  401.    any later version.
  402.  
  403.    This program is distributed in the hope that it will be useful,
  404.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  405.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  406.    GNU General Public License for more details.
  407.  
  408.    You should have received a copy of the GNU General Public License
  409.    along with this program; if not, write to the Free Software
  410.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  411.  
  412.    The author may be reached (Email) at the address mike@ai.mit.edu,
  413.    or (US mail) as Mike Haertel c/o Free Software Foundation. */
  414.  
  415. #ifndef __ONEFILE
  416. #include "ansidecl.h"
  417. #include <stddef.h>
  418. #include <stdlib.h>
  419.  
  420. #define _MALLOC_INTERNAL
  421. #include "malloc.h"
  422. #endif /* __ONEFILE */
  423.  
  424. /* Debugging hook for free.  */
  425. void EXFUN((*__free_hook), (PTR __ptr));
  426.  
  427. /* Return memory to the heap.  Like free() but don't call a __free_hook
  428.    if there is one.  */
  429. void
  430. DEFUN(__free, (ptr), PTR ptr)
  431. {
  432.   int type;
  433.   size_t block, blocks;
  434.   register size_t i;
  435.   struct list *prev, *next;
  436.  
  437.   block = BLOCK(ptr);
  438.  
  439.   type = _heapinfo[block].busy.type;
  440.   switch (type)
  441.     {
  442.     case 0:
  443.       /* Get as many statistics as early as we can.  */
  444.       --_chunks_used;
  445.       _bytes_used -= _heapinfo[block].busy.info.size * BLOCKSIZE;
  446.       _bytes_free += _heapinfo[block].busy.info.size * BLOCKSIZE;
  447.  
  448.       /* Find the free cluster previous to this one in the free list.
  449.      Start searching at the last block referenced; this may benefit
  450.      programs with locality of allocation.  */
  451.       i = _heapindex;
  452.       if (i > block)
  453.     while (i > block)
  454.       i = _heapinfo[i].free.prev;
  455.       else
  456.     {
  457.       do
  458.         i = _heapinfo[i].free.next;
  459.       while (i > 0 && i < block);
  460.       i = _heapinfo[i].free.prev;
  461.     }
  462.  
  463.       /* Determine how to link this block into the free list.  */
  464.       if (block == i + _heapinfo[i].free.size)
  465.     {
  466.       /* Coalesce this block with its predecessor.  */
  467.       _heapinfo[i].free.size += _heapinfo[block].busy.info.size;
  468.       block = i;
  469.     }
  470.       else
  471.     {
  472.       /* Really link this block back into the free list.  */
  473.       _heapinfo[block].free.size = _heapinfo[block].busy.info.size;
  474.       _heapinfo[block].free.next = _heapinfo[i].free.next;
  475.       _heapinfo[block].free.prev = i;
  476.       _heapinfo[i].free.next = block;
  477.       _heapinfo[_heapinfo[block].free.next].free.prev = block;
  478.       ++_chunks_free;
  479.     }
  480.  
  481.       /* Now that the block is linked in, see if we can coalesce it
  482.      with its successor (by deleting its successor from the list
  483.      and adding in its size).  */
  484.       if (block + _heapinfo[block].free.size == _heapinfo[block].free.next)
  485.     {
  486.       _heapinfo[block].free.size
  487.         += _heapinfo[_heapinfo[block].free.next].free.size;
  488.       _heapinfo[block].free.next
  489.         = _heapinfo[_heapinfo[block].free.next].free.next;
  490.       _heapinfo[_heapinfo[block].free.next].free.prev = block;
  491.       --_chunks_free;
  492.     }
  493.  
  494.       /* Now see if we can return stuff to the system.  */
  495.       blocks = _heapinfo[block].free.size;
  496.       if (blocks >= FINAL_FREE_BLOCKS && block + blocks == _heaplimit
  497.       && (*__morecore)(0) == ADDRESS(block + blocks))
  498.     {
  499.       register size_t bytes = blocks * BLOCKSIZE;
  500.       _heaplimit -= blocks;
  501.       (*__morecore)(- bytes);
  502.       _heapinfo[_heapinfo[block].free.prev].free.next
  503.         = _heapinfo[block].free.next;
  504.       _heapinfo[_heapinfo[block].free.next].free.prev
  505.         = _heapinfo[block].free.prev;
  506.       block = _heapinfo[block].free.prev;
  507.       --_chunks_free;
  508.       _bytes_free -= bytes;
  509.     }
  510.  
  511.       /* Set the next search to begin at this block.  */
  512.       _heapindex = block;
  513.       break;
  514.  
  515.     default:
  516.       /* Do some of the statistics.  */
  517.       --_chunks_used;
  518.       _bytes_used -= 1 << type;
  519.       ++_chunks_free;
  520.       _bytes_free += 1 << type;
  521.  
  522.       /* Get the address of the first free fragment in this block.  */
  523.       prev = (struct list *) ((char *) ADDRESS(block) +
  524.                   (_heapinfo[block].busy.info.frag.first << type));
  525.  
  526.       if (_heapinfo[block].busy.info.frag.nfree == (BLOCKSIZE >> type) - 1)
  527.     {
  528.       /* If all fragments of this block are free, remove them
  529.          from the fragment list and free the whole block.  */
  530.       next = prev;
  531.       for (i = 1; i < BLOCKSIZE >> type; ++i)
  532.         next = next->next;
  533.       prev->prev->next = next;
  534.       if (next != NULL)
  535.         next->prev = prev->prev;
  536.       _heapinfo[block].busy.type = 0;
  537.       _heapinfo[block].busy.info.size = 1;
  538.  
  539.       /* Keep the statistics accurate.  */
  540.       ++_chunks_used;
  541.       _bytes_used += BLOCKSIZE;
  542.       _chunks_free -= BLOCKSIZE >> type;
  543.       _bytes_free -= BLOCKSIZE;
  544.  
  545.       free(ADDRESS(block));
  546.     }
  547.       else if (_heapinfo[block].busy.info.frag.nfree != 0)
  548.     {
  549.       /* If some fragments of this block are free, link this
  550.          fragment into the fragment list after the first free
  551.          fragment of this block. */
  552.       next = (struct list *) ptr;
  553.       next->next = prev->next;
  554.       next->prev = prev;
  555.       prev->next = next;
  556.       if (next->next != NULL)
  557.         next->next->prev = next;
  558.       ++_heapinfo[block].busy.info.frag.nfree;
  559.     }
  560.       else
  561.     {
  562.       /* No fragments of this block are free, so link this
  563.          fragment into the fragment list and announce that
  564.          it is the first free fragment of this block. */
  565.       prev = (struct list *) ptr;
  566.       _heapinfo[block].busy.info.frag.nfree = 1;
  567.       _heapinfo[block].busy.info.frag.first = (unsigned int)
  568.         (((char *) ptr - (char *) NULL) % BLOCKSIZE >> type);
  569.       prev->next = _fraghead[type].next;
  570.       prev->prev = &_fraghead[type];
  571.       prev->prev->next = prev;
  572.       if (prev->next != NULL)
  573.         prev->next->prev = prev;
  574.     }
  575.       break;
  576.     }
  577. }
  578.  
  579. /* Return memory to the heap.  */
  580. void
  581. DEFUN(free, (ptr), PTR ptr)
  582. {
  583.   if (ptr == NULL)
  584.     return;
  585.  
  586.   if (__free_hook != NULL)
  587.     (*__free_hook)(ptr);
  588.   else
  589.     __free (ptr);
  590. }
  591.  
  592. /* DO NOT DELETE THIS LINE -- malloc.c INSERTED HERE. */
  593. /* Memory allocator `malloc'.
  594.    Copyright 1990 Free Software Foundation
  595.           Written May 1989 by Mike Haertel.
  596.  
  597.    This program is free software; you can redistribute it and/or modify
  598.    it under the terms of the GNU General Public License as published by
  599.    the Free Software Foundation; either version 1, or (at your option)
  600.    any later version.
  601.  
  602.    This program is distributed in the hope that it will be useful,
  603.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  604.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  605.    GNU General Public License for more details.
  606.  
  607.    You should have received a copy of the GNU General Public License
  608.    along with this program; if not, write to the Free Software
  609.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  610.  
  611.    The author may be reached (Email) at the address mike@ai.mit.edu,
  612.    or (US mail) as Mike Haertel c/o Free Software Foundation. */
  613.  
  614. #ifndef __ONEFILE
  615. #include "ansidecl.h"
  616. #include <stddef.h>
  617. #include <stdlib.h>
  618. #include <string.h>
  619.  
  620. #define _MALLOC_INTERNAL
  621. #include "malloc.h"
  622. #endif /* __ONEFILE */
  623.  
  624. /* How to really get more memory.  */
  625. PTR EXFUN((*__morecore), (ptrdiff_t __size)) = __default_morecore;
  626.  
  627. /* Debugging hook for `malloc'.  */
  628. PTR EXFUN((*__malloc_hook), (size_t __size));
  629.  
  630. /* Pointer to the base of the first block.  */
  631. char *_heapbase;
  632.  
  633. /* Block information table.  Allocated with align/__free (not malloc/free).  */
  634. malloc_info *_heapinfo;
  635.  
  636. /* Number of info entries.  */
  637. static size_t heapsize;
  638.  
  639. /* Search index in the info table.  */
  640. size_t _heapindex;
  641.  
  642. /* Limit of valid info table indices.  */
  643. size_t _heaplimit;
  644.  
  645. /* Free lists for each fragment size.  */
  646. struct list _fraghead[BLOCKLOG];
  647.  
  648. /* Instrumentation.  */
  649. size_t _chunks_used;
  650. size_t _bytes_used;
  651. size_t _chunks_free;
  652. size_t _bytes_free;
  653.  
  654. /* Are you experienced?  */
  655. int __malloc_initialized;
  656.  
  657. /* Aligned allocation.  */
  658. static PTR
  659. DEFUN(align, (size), size_t size)
  660. {
  661.   PTR result;
  662.   unsigned int adj;
  663.  
  664.   result = (*__morecore)(size);
  665.   adj = (unsigned int) ((char *) result - (char *) NULL) % BLOCKSIZE;
  666.   if (adj != 0)
  667.     {
  668.       adj = BLOCKSIZE - adj;
  669.       (void) (*__morecore)(adj);
  670.       result = (char *) result + adj;
  671.     }
  672.   return result;
  673. }
  674.  
  675. /* Set everything up and remember that we have.  */
  676. static int
  677. DEFUN_VOID(initialize)
  678. {
  679.   heapsize = HEAP / BLOCKSIZE;
  680.   _heapinfo = (malloc_info *) align(heapsize * sizeof(malloc_info));
  681.   if (_heapinfo == NULL)
  682.     return 0;
  683.   memset(_heapinfo, 0, heapsize * sizeof(malloc_info));
  684.   _heapinfo[0].free.size = 0;
  685.   _heapinfo[0].free.next = _heapinfo[0].free.prev = 0;
  686.   _heapindex = 0;
  687.   _heapbase = (char *) _heapinfo;
  688.   __malloc_initialized = 1;
  689.   return 1;
  690. }
  691.  
  692. /* Get neatly aligned memory, initializing or
  693.    growing the heap info table as necessary. */
  694. static PTR
  695. DEFUN(morecore, (size), size_t size)
  696. {
  697.   PTR result;
  698.   malloc_info *newinfo, *oldinfo;
  699.   size_t newsize;
  700.  
  701.   result = align(size);
  702.   if (result == NULL)
  703.     return NULL;
  704.  
  705.   /* Check if we need to grow the info table.  */
  706.   if (BLOCK((char *) result + size) > heapsize)
  707.     {
  708.       newsize = heapsize;
  709.       while (BLOCK((char *) result + size) > newsize)
  710.     newsize *= 2;
  711.       newinfo = (malloc_info *) align(newsize * sizeof(malloc_info));
  712.       if (newinfo == NULL)
  713.     {
  714.       (*__morecore)(- size);
  715.       return NULL;
  716.     }
  717.       memset(newinfo, 0, newsize * sizeof(malloc_info));
  718.       memcpy(newinfo, _heapinfo, heapsize * sizeof(malloc_info));
  719.       oldinfo = _heapinfo;
  720.       newinfo[BLOCK(oldinfo)].busy.type = 0;
  721.       newinfo[BLOCK(oldinfo)].busy.info.size
  722.     = BLOCKIFY(heapsize * sizeof(malloc_info));
  723.       _heapinfo = newinfo;
  724.       __free(oldinfo);
  725.       heapsize = newsize;
  726.     }
  727.  
  728.   _heaplimit = BLOCK((char *) result + size);
  729.   return result;
  730. }
  731.  
  732. /* Allocate memory from the heap.  */
  733. PTR
  734. DEFUN(malloc, (size), size_t size)
  735. {
  736.   PTR result;
  737.   size_t block, blocks, lastblocks, start;
  738.   register size_t i;
  739.   struct list *next;
  740.  
  741.   if (size == 0)
  742.     return NULL;
  743.  
  744.   if (__malloc_hook != NULL)
  745.     return (*__malloc_hook)(size);
  746.  
  747.   if (!__malloc_initialized)
  748.     if (!initialize())
  749.       return NULL;
  750.  
  751.   if (size < sizeof(struct list))
  752.     size = sizeof(struct list);
  753.  
  754.   /* Determine the allocation policy based on the request size.  */
  755.   if (size <= BLOCKSIZE / 2)
  756.     {
  757.       /* Small allocation to receive a fragment of a block.
  758.      Determine the logarithm to base two of the fragment size. */
  759.       register size_t log = 1;
  760.       --size;
  761.       while ((size /= 2) != 0)
  762.     ++log;
  763.  
  764.       /* Look in the fragment lists for a
  765.      free fragment of the desired size. */
  766.       next = _fraghead[log].next;
  767.       if (next != NULL)
  768.     {
  769.       /* There are free fragments of this size.
  770.          Pop a fragment out of the fragment list and return it.
  771.          Update the block's nfree and first counters. */
  772.       result = (PTR) next;
  773.       next->prev->next = next->next;
  774.       if (next->next != NULL)
  775.         next->next->prev = next->prev;
  776.       block = BLOCK(result);
  777.       if (--_heapinfo[block].busy.info.frag.nfree != 0)
  778.         _heapinfo[block].busy.info.frag.first = (unsigned int)
  779.           (((char *) next->next - (char *) NULL) % BLOCKSIZE) >> log;
  780.  
  781.       /* Update the statistics.  */
  782.       ++_chunks_used;
  783.       _bytes_used += 1 << log;
  784.       --_chunks_free;
  785.       _bytes_free -= 1 << log;
  786.     }
  787.       else
  788.     {
  789.       /* No free fragments of the desired size, so get a new block
  790.          and break it into fragments, returning the first.  */
  791.       result = malloc(BLOCKSIZE);
  792.       if (result == NULL)
  793.         return NULL;
  794.  
  795.       /* Link all fragments but the first into the free list.  */
  796.       for (i = 1; i < BLOCKSIZE >> log; ++i)
  797.         {
  798.           next = (struct list *) ((char *) result + (i << log));
  799.           next->next = _fraghead[log].next;
  800.           next->prev = &_fraghead[log];
  801.           next->prev->next = next;
  802.           if (next->next != NULL)
  803.         next->next->prev = next;
  804.         }
  805.  
  806.       /* Initialize the nfree and first counters for this block.  */
  807.       block = BLOCK(result);
  808.       _heapinfo[block].busy.type = log;
  809.       _heapinfo[block].busy.info.frag.nfree = i - 1;
  810.       _heapinfo[block].busy.info.frag.first = i - 1;
  811.  
  812.       _chunks_free += (BLOCKSIZE >> log) - 1;
  813.       _bytes_free += BLOCKSIZE - (1 << log);
  814.     }
  815.     }
  816.   else
  817.     {
  818.       /* Large allocation to receive one or more blocks.
  819.      Search the free list in a circle starting at the last place visited.
  820.      If we loop completely around without finding a large enough
  821.      space we will have to get more memory from the system.  */
  822.       blocks = BLOCKIFY(size);
  823.       start = block = MALLOC_SEARCH_START;
  824.       while (_heapinfo[block].free.size < blocks)
  825.     {
  826.       block = _heapinfo[block].free.next;
  827.       if (block == start)
  828.         {
  829.           /* Need to get more from the system.  Check to see if
  830.          the new core will be contiguous with the final free
  831.          block; if so we don't need to get as much.  */
  832.           block = _heapinfo[0].free.prev;
  833.           lastblocks = _heapinfo[block].free.size;
  834.           if (_heaplimit != 0 && block + lastblocks == _heaplimit &&
  835.           (*__morecore)(0) == ADDRESS(block + lastblocks) &&
  836.           (morecore((blocks - lastblocks) * BLOCKSIZE)) != NULL)
  837.         {
  838.           _heapinfo[block].free.size = blocks;
  839.           _bytes_free += (blocks - lastblocks) * BLOCKSIZE;
  840.           continue;
  841.         }
  842.           result = morecore(blocks * BLOCKSIZE);
  843.           if (result == NULL)
  844.         return NULL;
  845.           block = BLOCK(result);
  846.           _heapinfo[block].busy.type = 0;
  847.           _heapinfo[block].busy.info.size = blocks;
  848.           ++_chunks_used;
  849.           _bytes_used += blocks * BLOCKSIZE;
  850.           return result;
  851.         }
  852.     }
  853.  
  854.       /* At this point we have found a suitable free list entry.
  855.      Figure out how to remove what we need from the list. */
  856.       result = ADDRESS(block);
  857.       if (_heapinfo[block].free.size > blocks)
  858.     {
  859.       /* The block we found has a bit left over,
  860.          so relink the tail end back into the free list. */
  861.       _heapinfo[block + blocks].free.size
  862.         = _heapinfo[block].free.size - blocks;
  863.       _heapinfo[block + blocks].free.next
  864.         = _heapinfo[block].free.next;
  865.       _heapinfo[block + blocks].free.prev
  866.         = _heapinfo[block].free.prev;
  867.       _heapinfo[_heapinfo[block].free.prev].free.next
  868.         = _heapinfo[_heapinfo[block].free.next].free.prev
  869.           = _heapindex = block + blocks;
  870.     }
  871.       else
  872.     {
  873.       /* The block exactly matches our requirements,
  874.          so just remove it from the list. */
  875.       _heapinfo[_heapinfo[block].free.next].free.prev
  876.         = _heapinfo[block].free.prev;
  877.       _heapinfo[_heapinfo[block].free.prev].free.next
  878.         = _heapindex = _heapinfo[block].free.next;
  879.       --_chunks_free;
  880.     }
  881.  
  882.       _heapinfo[block].busy.type = 0;
  883.       _heapinfo[block].busy.info.size = blocks;
  884.       ++_chunks_used;
  885.       _bytes_used += blocks * BLOCKSIZE;
  886.       _bytes_free -= blocks * BLOCKSIZE;
  887.     }
  888.  
  889.   return result;
  890. }
  891.  
  892. /* DO NOT DELETE THIS LINE -- realloc.c INSERTED HERE. */
  893. /* Change the size of a block allocated by `malloc'.
  894.    Copyright 1990 Free Software Foundation
  895.           Written May 1989 by Mike Haertel.
  896.  
  897.    This program is free software; you can redistribute it and/or modify
  898.    it under the terms of the GNU General Public License as published by
  899.    the Free Software Foundation; either version 1, or (at your option)
  900.    any later version.
  901.  
  902.    This program is distributed in the hope that it will be useful,
  903.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  904.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  905.    GNU General Public License for more details.
  906.  
  907.    You should have received a copy of the GNU General Public License
  908.    along with this program; if not, write to the Free Software
  909.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  910.  
  911.    The author may be reached (Email) at the address mike@ai.mit.edu,
  912.    or (US mail) as Mike Haertel c/o Free Software Foundation. */
  913.  
  914. #ifndef __ONEFILE
  915. #include "ansidecl.h"
  916. #include <stdlib.h>
  917. #include <string.h>
  918.  
  919. #define _MALLOC_INTERNAL
  920. #include "malloc.h"
  921. #endif /* __ONEFILE */
  922.  
  923. #define MIN(A, B) ((A) < (B) ? (A) : (B))
  924.  
  925. /* Debugging hook for realloc.  */
  926. PTR EXFUN((*__realloc_hook), (PTR __ptr, size_t __size));
  927.  
  928. /* Resize the given region to the new size, returning a pointer
  929.    to the (possibly moved) region.  This is optimized for speed;
  930.    some benchmarks seem to indicate that greater compactness is
  931.    achieved by unconditionally allocating and copying to a
  932.    new region.  This module has incestuous knowledge of the
  933.    internals of both free and malloc. */
  934. PTR
  935. DEFUN(realloc, (ptr, size), PTR ptr AND size_t size)
  936. {
  937.   PTR result;
  938.   int type;
  939.   size_t block, blocks, oldlimit;
  940.  
  941.   if (size == 0)
  942.     {
  943.       free(ptr);
  944.       return NULL;
  945.     }
  946.   else if (ptr == NULL)
  947.     return malloc(size);
  948.  
  949.   if (__realloc_hook != NULL)
  950.     return (*__realloc_hook)(ptr, size);
  951.  
  952.   block = BLOCK(ptr);
  953.  
  954.   type = _heapinfo[block].busy.type;
  955.   switch (type)
  956.     {
  957.     case 0:
  958.       /* Maybe reallocate a large block to a small fragment.  */
  959.       if (size <= BLOCKSIZE / 2)
  960.     {
  961.       result = malloc(size);
  962.       if (result != NULL)
  963.         {
  964.           memcpy(result, ptr, size);
  965.           free(ptr);
  966.           return result;
  967.         }
  968.     }
  969.  
  970.       /* The new size is a large allocation as well;
  971.      see if we can hold it in place. */
  972.       blocks = BLOCKIFY(size);
  973.       if (blocks < _heapinfo[block].busy.info.size)
  974.     {
  975.       /* The new size is smaller; return
  976.          excess memory to the free list. */
  977.       _heapinfo[block + blocks].busy.type = 0;
  978.       _heapinfo[block + blocks].busy.info.size
  979.         = _heapinfo[block].busy.info.size - blocks;
  980.       _heapinfo[block].busy.info.size = blocks;
  981.       free(ADDRESS(block + blocks));
  982.       result = ptr;
  983.     }
  984.       else if (blocks == _heapinfo[block].busy.info.size)
  985.     /* No size change necessary.  */
  986.     result = ptr;
  987.       else
  988.     {
  989.       /* Won't fit, so allocate a new region that will.
  990.          Free the old region first in case there is sufficient
  991.          adjacent free space to grow without moving. */
  992.       blocks = _heapinfo[block].busy.info.size;
  993.       /* Prevent free from actually returning memory to the system.  */
  994.       oldlimit = _heaplimit;
  995.       _heaplimit = 0;
  996.       free(ptr);
  997.       _heaplimit = oldlimit;
  998.       result = malloc(size);
  999.       if (result == NULL)
  1000.         {
  1001.           (void) malloc(blocks * BLOCKSIZE);
  1002.           return NULL;
  1003.         }
  1004.       if (ptr != result)
  1005.         memmove(result, ptr, blocks * BLOCKSIZE);
  1006.     }
  1007.       break;
  1008.  
  1009.     default:
  1010.       /* Old size is a fragment; type is logarithm
  1011.      to base two of the fragment size.  */
  1012.       if (size > 1 << (type - 1) && size <= 1 << type)
  1013.     /* The new size is the same kind of fragment.  */
  1014.     result = ptr;
  1015.       else
  1016.     {
  1017.       /* The new size is different; allocate a new space,
  1018.          and copy the lesser of the new size and the old. */
  1019.       result = malloc(size);
  1020.       if (result == NULL)
  1021.         return NULL;
  1022.       memcpy(result, ptr, MIN(size, 1 << type));
  1023.       free(ptr);
  1024.     }
  1025.       break;
  1026.     }
  1027.  
  1028.   return result;
  1029. }
  1030.  
  1031. /* DO NOT DELETE THIS LINE -- unix.c INSERTED HERE. */
  1032. /* unix.c - get more memory with a UNIX system call.
  1033.    Copyright 1990 Free Software Foundation
  1034.           Written May 1989 by Mike Haertel.
  1035.  
  1036.    This program is free software; you can redistribute it and/or modify
  1037.    it under the terms of the GNU General Public License as published by
  1038.    the Free Software Foundation; either version 1, or (at your option)
  1039.    any later version.
  1040.  
  1041.    This program is distributed in the hope that it will be useful,
  1042.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  1043.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  1044.    GNU General Public License for more details.
  1045.  
  1046.    You should have received a copy of the GNU General Public License
  1047.    along with this program; if not, write to the Free Software
  1048.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  1049.  
  1050.    The author may be reached (Email) at the address mike@ai.mit.edu,
  1051.    or (US mail) as Mike Haertel c/o Free Software Foundation. */
  1052.  
  1053. #ifndef __ONEFILE
  1054. #include "ansidecl.h"
  1055. #include <stddef.h>
  1056.  
  1057. #define _MALLOC_INTERNAL
  1058. #include "malloc.h"
  1059. #endif /* __ONEFILE */
  1060.  
  1061. extern PTR EXFUN(sbrk, (ptrdiff_t size));
  1062.  
  1063. PTR
  1064. DEFUN(__default_morecore, (size), ptrdiff_t size)
  1065. {
  1066.   PTR result;
  1067.  
  1068.   result = sbrk(size);
  1069.   if (result == (PTR) -1)
  1070.     return NULL;
  1071.   return result;
  1072. }
  1073.  
  1074. #define __getpagesize getpagesize
  1075. /* DO NOT DELETE THIS LINE -- valloc.c INSERTED HERE. */
  1076. /* Allocate memory on a page boundary.
  1077.    Copyright 1990 Free Software Foundation
  1078.           Written May 1989 by Mike Haertel.
  1079.  
  1080.    This program is free software; you can redistribute it and/or modify
  1081.    it under the terms of the GNU General Public License as published by
  1082.    the Free Software Foundation; either version 1, or (at your option)
  1083.    any later version.
  1084.  
  1085.    This program is distributed in the hope that it will be useful,
  1086.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  1087.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  1088.    GNU General Public License for more details.
  1089.  
  1090.    You should have received a copy of the GNU General Public License
  1091.    along with this program; if not, write to the Free Software
  1092.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  1093.  
  1094.    The author may be reached (Email) at the address mike@ai.mit.edu,
  1095.    or (US mail) as Mike Haertel c/o Free Software Foundation. */
  1096.  
  1097. #ifndef __ONEFILE
  1098. #include "ansidecl.h"
  1099. #include <stdlib.h>
  1100. #endif /* __ONEFILE */
  1101.  
  1102. extern size_t EXFUN(__getpagesize, (NOARGS));
  1103.  
  1104. static size_t pagesize;
  1105.  
  1106. PTR
  1107. DEFUN(valloc, (size), size_t size)
  1108. {
  1109.   PTR result;
  1110.   unsigned int adj;
  1111.  
  1112.   if (pagesize == 0)
  1113.     pagesize = __getpagesize();
  1114.  
  1115.   result = malloc(size + pagesize);
  1116.   if (result == NULL)
  1117.     return NULL;
  1118.   adj = (unsigned int) ((char *) result - (char *) NULL) % pagesize;
  1119.   if (adj != 0)
  1120.     result = (char *) result + pagesize - adj;
  1121.   return result;
  1122. }
  1123.