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