home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / gnu / djgppzip / pubquick.c < prev    next >
C/C++ Source or Header  |  1994-03-01  |  42KB  |  1,599 lines
  1. #define _INTERNAL_MALLOC_
  2. #define _IN_OUTPUT_
  3. /* -*-c-*- */
  4. #ifndef _UserMalloc_pre_h_
  5. #define _UserMalloc_pre_h_
  6.  
  7. /*****************************************************************************/
  8. /**  Using Gnu G++ Malloc                                                    */
  9. /*****************************************************************************/
  10.  
  11. #ifndef MallocArgType
  12. #  ifdef __cplusplus
  13. #     define MallocArgType int
  14. #     define MallocPtrType void *
  15. #     define FreePtrType void *
  16. #     define FreeRetType void
  17. #  else
  18. #    ifdef sun
  19. #     ifdef __malloc_h_
  20. #       define MallocArgType int
  21. #       define MallocPtrType malloc_t
  22. #       define FreePtrType malloc_t
  23. #       define FreeRetType int
  24. #     else
  25. #       define MallocArgType int
  26. #       define MallocPtrType char *
  27. #       define FreePtrType void *
  28. #       define FreeRetType int
  29. #     endif
  30. #    else
  31. #     define MallocArgType unsigned int
  32. #     define MallocPtrType void *
  33. #     define FreePtrType void *
  34. #     define FreeRetType void
  35. #    endif
  36. #  endif
  37. #endif
  38.  
  39. extern MallocPtrType __internal_malloc(MallocArgType);
  40.  
  41. typedef unsigned int SizeType;
  42.  
  43. #define MallocChunk struct __CustomAllocMallocChunkStruct
  44. struct __CustomAllocMallocChunkStruct
  45. {
  46.   SizeType       size;
  47.   MallocChunk *fd;
  48. };
  49.  
  50. #endif
  51. /* 
  52. Copyright (C) 1989 Free Software Foundation
  53.     written by Doug Lea (dl@oswego.edu)
  54.  
  55. This file is part of the GNU C++ Library.  This library is free
  56. software; you can redistribute it and/or modify it under the terms of
  57. the GNU Library General Public License as published by the Free
  58. Software Foundation; either version 2 of the License, or (at your
  59. option) any later version.  This library is distributed in the hope
  60. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  61. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  62. PURPOSE.  See the GNU Library General Public License for more details.
  63. You should have received a copy of the GNU Library General Public
  64. License along with this library; if not, write to the Free Software
  65. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  66. */
  67.  
  68.  
  69. /* compile with -DMALLOC_STATS to collect statistics */
  70. /* collecting statistics slows down malloc by at least 15% */
  71.  
  72. #ifndef MallocArgType
  73. #  ifdef __cplusplus
  74. #     define MallocArgType int
  75. #     define MallocPtrType void *
  76. #     define FreePtrType void *
  77. #     define FreeRetType void
  78. #  else
  79. #    ifdef sun
  80. #     ifdef __malloc_h_
  81. #       define MallocArgType int
  82. #       define MallocPtrType malloc_t
  83. #       define FreePtrType malloc_t
  84. #       define FreeRetType int
  85. #     else
  86. #       define MallocArgType int
  87. #       define MallocPtrType char *
  88. #       define FreePtrType void *
  89. #       define FreeRetType int
  90. #     endif
  91. #    else
  92. #     define MallocArgType unsigned int
  93. #     define MallocPtrType void *
  94. #     define FreePtrType void *
  95. #     define FreeRetType void
  96. #    endif
  97. #  endif
  98. #endif
  99.  
  100.  
  101. #ifdef MALLOC_STATS
  102. #define UPDATE_STATS(ARGS) {ARGS;}
  103. #else
  104. #define UPDATE_STATS(ARGS)
  105. #endif
  106.  
  107. /* History
  108.  
  109.  
  110.    Tue Jan 16 04:54:27 1990  Doug Lea  (dl at g.oswego.edu)
  111.  
  112.      version 1 released in libg++
  113.  
  114.    Sun Jan 21 05:52:47 1990  Doug Lea  (dl at g.oswego.edu)
  115.  
  116.      bins are now own struct for, sanity.
  117.  
  118.      new victim search strategy: scan up and consolidate.
  119.      Both faster and less fragmentation.
  120.  
  121.      refined when to scan bins for consolidation, via consollink, etc.
  122.  
  123.      realloc: always try to expand chunk, avoiding some fragmentation.
  124.  
  125.      changed a few inlines into macros
  126.  
  127.      hardwired SBRK_UNIT to 4096 for uniformity across systems
  128.  
  129.    Tue Mar 20 14:18:23 1990  Doug Lea  (dl at g.oswego.edu)
  130.  
  131.      calloc and cfree now correctly parameterized.
  132.  
  133.    Sun Apr  1 10:00:48 1990  Doug Lea  (dl at g.oswego.edu)
  134.  
  135.      added memalign and valloc.
  136.  
  137.    Sun Jun 24 05:46:48 1990  Doug Lea  (dl at g.oswego.edu)
  138.  
  139.      #include gepagesize.h only ifndef sun
  140.      cache pagesize after first call
  141.  
  142.    Wed Jul 25 08:35:19 1990  Doug Lea  (dl at g.oswego.edu)
  143.  
  144.      No longer rely on a `designated victim':
  145.  
  146.        1. It sometimes caused splits of large chunks
  147.           when smaller ones would do, leading to
  148.           bad worst-case fragmentation.
  149.  
  150.        2. Scanning through the av array fast anyway,
  151.           so the overhead isn't worth it.
  152.  
  153.      To compensate, several other minor changes:
  154.  
  155.        1. Unusable chunks are checked for consolidation during
  156.           searches inside bins, better distributing chunks
  157.           across bins.
  158.  
  159.        2. Chunks are returned when found in malloc_find_space,
  160.            rather than finishing cleaning everything up, to
  161.            avoid wasted iterations due to (1).
  162.  
  163.    Sun Dec 15 08:50:37 1991  Doug Lea  (dl at g.oswego.edu)
  164.  
  165.        unsigned int => size_t
  166.  
  167. */
  168.  
  169. /* 
  170.   A version of malloc/free/realloc tuned for C++ applications.
  171.  
  172.   Here's what you probably want to know first:
  173.  
  174.   In various tests, this appears to be about as fast as,
  175.   and usually substantially less memory-wasteful than BSD/GNUemacs malloc.
  176.  
  177.   Generally, it is slower (by perhaps 20%) than bsd-style malloc
  178.   only when bsd malloc would waste a great deal of space in 
  179.   fragmented blocks, which this malloc recovers; or when, by
  180.   chance or design, nearly all requests are near the bsd malloc
  181.   power-of-2 allocation bin boundaries, and as many chunks are
  182.   used as are allocated. 
  183.  
  184.   It uses more space than bsd malloc only when, again by chance
  185.   or design, only bsdmalloc bin-sized requests are malloced, or when
  186.   little dynamic space is malloced, since this malloc may grab larger
  187.   chunks from the system at a time than bsd.
  188.  
  189.   In other words, this malloc seems generally superior to bsd
  190.   except perhaps for programs that are specially tuned to
  191.   deal with bsdmalloc's characteristics. But even here, the
  192.   performance differences are slight.
  193.  
  194.  
  195.   This malloc, like any other, is a compromised design. 
  196.  
  197.  
  198.   Chunks of memory are maintained using a `boundary tag' method as
  199.   described in e.g., Knuth or Standish.  This means that the size of
  200.   the chunk is stored both in the front of the chunk and at the end.
  201.   This makes consolidating fragmented chunks into bigger chunks very fast.
  202.   The size field is also used to hold bits representing whether a
  203.   chunk is free or in use.
  204.  
  205.   Malloced chunks have space overhead of 8 bytes: The preceding
  206.   and trailing size fields. When they are freed, the list pointer
  207.   fields are also needed.
  208.  
  209.   Available chunks are kept in doubly linked lists. The lists are
  210.   maintained in an array of bins using a power-of-two method, except
  211.   that instead of 32 bins (one for each 1 << i), there are 128: each
  212.   power of two is split in quarters. The use of very fine bin sizes 
  213.   closely approximates the use of one bin per actually used size,
  214.   without necessitating the overhead of locating such bins. It is
  215.   especially desirable in common C++ applications where large numbers
  216.   of identically-sized blocks are malloced/freed in some dynamic
  217.   manner, and then later are all freed. The finer bin sizes make
  218.   finding blocks fast, with little wasted overallocation. The
  219.   consolidation methods ensure that once the collection of blocks is
  220.   no longer useful, fragments are gathered into bigger chunks awaiting new
  221.   roles.
  222.  
  223.   The bins av[i] serve as heads of the lists. Bins contain a dummy
  224.   header for the chunk lists, and a `dirty' field used to indicate
  225.   whether the list may need to be scanned for consolidation.
  226.  
  227.   On allocation, the bin corresponding to the request size is
  228.   scanned, and if there is a chunk with size >= requested, it
  229.   is split, if too big, and used. Chunks on the list which are
  230.   too small are examined for consolidation during this traversal.
  231.  
  232.   If no chunk exists in the list bigger bins are scanned in search of
  233.   a victim.
  234.  
  235.   If no victim can be found, then smaller bins are examined for
  236.   consolidation in order to construct a victim.
  237.  
  238.   Finally, if consolidation fails to come up with a usable chunk,
  239.   more space is obtained from the system.
  240.  
  241.   After a split, the remainder is placed on
  242.   the back of the appropriate bin list. (All freed chunks are placed
  243.   on fronts of lists. All remaindered or consolidated chunks are
  244.   placed on the rear. Correspondingly, searching within a bin
  245.   starts at the front, but finding victims is from the back. All
  246.   of this approximates  the  effect of having 2 kinds of lists per 
  247.   bin: returned chunks vs unallocated chunks, but without the overhead 
  248.   of maintaining 2 lists.)
  249.  
  250.   Deallocation (free) consists only of placing the chunk on
  251.   a list.
  252.  
  253.   Reallocation proceeds in the usual way. If a chunk can be extended,
  254.   it is, else a malloc-copy-free sequence is taken.
  255.  
  256.   memalign requests more than enough space from malloc, finds a
  257.   spot within that chunk that meets the alignment request, and
  258.   then possibly frees the leading and trailing space. Overreliance
  259.   on memalign is a sure way to fragment space.
  260.  
  261.  
  262.   Some other implementation matters:
  263.  
  264.   8 byte alignment is currently hardwired into the design. Calling
  265.   memalign will return a chunk that is both 8-byte aligned, and
  266.   meets the requested alignment.
  267.  
  268.   The basic overhead of a used chunk is 8 bytes: 4 at the front and
  269.   4 at the end.
  270.  
  271.   When a chunk is free, 8 additional bytes are needed for free list
  272.   pointers. Thus, the minimum allocatable size is 16 bytes.
  273.  
  274.   The existence of front and back overhead permits some reasonably
  275.   effective fence-bashing checks: The front and back fields must
  276.   be identical. This is checked only within free() and realloc().
  277.   The checks are fast enough to be made non-optional.
  278.  
  279.   The overwriting of parts of freed memory with the freelist pointers
  280.   can also be very effective (albeit in an annoying way) in helping 
  281.   users track down dangling pointers.
  282.  
  283.   User overwriting of freed space will often result in crashes
  284.   within malloc or free.
  285.   
  286.   These routines are also tuned to C++ in that free(0) is a noop and
  287.   a failed malloc automatically calls (*new_handler)(). 
  288.  
  289.   malloc(0) returns a pointer to something of the minimum allocatable size.
  290.  
  291.   Additional memory is gathered from the system (via sbrk) in a
  292.   way that allows chunks obtained across different sbrk calls to
  293.   be consolidated, but does not require contiguous memory: Thus,
  294.   it should be safe to intersperse mallocs with other sbrk calls.
  295.  
  296.   This malloc is NOT designed to work in multiprocessing applications.
  297.   No semaphores or other concurrency control are provided to ensure
  298.   that multiple malloc or free calls don't run at the same time,
  299.   which could be disasterous.
  300.  
  301.   VERY heavy use of inlines is made, for clarity. If this malloc
  302.   is ported via a compiler without inlining capabilities, all
  303.   inlines should be transformed into macros -- making them non-inline
  304.   makes malloc at least twice as slow.
  305.  
  306.  
  307. */
  308.  
  309.  
  310. /* preliminaries */
  311.  
  312. #include <stddef.h>   /* for size_t */
  313.  
  314. #ifdef __cplusplus
  315. #include <stdio.h>
  316. #else
  317. #include "//usr/include/stdio.h"  /* needed for error reporting */
  318. #endif
  319.  
  320. #ifdef __cplusplus
  321. extern "C" {
  322. #endif
  323.  
  324. #ifdef USG
  325. extern void*     memset(void*, int, int);
  326. extern void*     memcpy(void*,  const void*, int);
  327. inline void      bzero(void* s, int l) { memset(s, 0, l); }
  328. #else
  329. extern void      bzero(void*, size_t      );
  330. #endif
  331.  
  332. extern void      bcopy(void*, void*, size_t      );
  333.  
  334. extern void*     sbrk(size_t      );
  335.  
  336.  
  337. #ifdef __GNUC__
  338. extern volatile void abort();
  339. #else
  340. extern void abort();
  341. #endif
  342.  
  343. #ifdef __cplusplus
  344. };  /* end of extern "C" */
  345. #endif
  346.  
  347.  
  348. /* A good multiple to call sbrk with */
  349.  
  350. #define SBRK_UNIT (2 * 4096)
  351.  
  352. extern MallocPtrType malloc(MallocArgType);
  353. extern FreeRetType free(FreePtrType);
  354.  
  355.  
  356.  
  357. /* how to die on detected error */
  358.  
  359. #ifdef __GNUC__
  360. static volatile void malloc_user_error()
  361. #else
  362. static void malloc_user_error()
  363. #endif
  364. {
  365.   fputs("malloc/free/realloc: clobbered space detected\n", stderr); abort();
  366. }
  367.  
  368.  
  369.  
  370. /*  Basic overhead for each malloc'ed chunk */
  371.  
  372.  
  373. struct malloc_chunk
  374. {
  375.   size_t               size;     /* Size in bytes, including overhead. */
  376.                                  /* Or'ed with INUSE if in use. */
  377.  
  378.   struct malloc_chunk* fd;       /* double links -- used only if free. */
  379.   struct malloc_chunk* bk;
  380.  
  381. };
  382.  
  383. typedef struct malloc_chunk* mchunkptr;
  384.  
  385. struct malloc_bin
  386. {
  387.   struct malloc_chunk hd;        /* dummy list header */
  388.   size_t              dirty;     /* True if maybe consolidatable */
  389.                                  /* Wasting a word here makes */
  390.                                  /* sizeof(bin) a power of 2, */
  391.                                  /* which makes size2bin() faster */
  392. };
  393.  
  394. typedef struct malloc_bin* mbinptr;
  395.  
  396.  
  397. /*  sizes, alignments */
  398.  
  399.  
  400. #define SIZE_SZ                   (sizeof(size_t      ))
  401. #define MALLOC_MIN_OVERHEAD       (SIZE_SZ + SIZE_SZ)
  402. #define MALLOC_ALIGN_MASK         (MALLOC_MIN_OVERHEAD - 1)
  403.  
  404. #define MINSIZE (sizeof(struct malloc_chunk) + SIZE_SZ) /* MUST == 16! */
  405.  
  406.  
  407. /* pad request bytes into a usable size */
  408.  
  409. static inline size_t       request2size(size_t       request)
  410. {
  411.   return  (request == 0) ?  MINSIZE : 
  412.     ((request + MALLOC_MIN_OVERHEAD + MALLOC_ALIGN_MASK) 
  413.       & ~(MALLOC_ALIGN_MASK));
  414. }
  415.  
  416.  
  417. static inline int aligned_OK(void* m)  
  418. {
  419.   return ((size_t      )(m) & (MALLOC_ALIGN_MASK)) == 0;
  420. }
  421.  
  422.  
  423. /* size field or'd with INUSE when in use */
  424. #define INUSE  0x1
  425.  
  426.  
  427.  
  428. /* the bins, initialized to have null double linked lists */
  429.  
  430. #define MAXBIN 120   /* 1 more than needed for 32 bit addresses */
  431.  
  432. #define FIRSTBIN (&(av[0])) 
  433.  
  434. static struct malloc_bin  av[MAXBIN] = 
  435. {
  436.   { { 0, &(av[0].hd),  &(av[0].hd) }, 0 },
  437.   { { 0, &(av[1].hd),  &(av[1].hd) }, 0 },
  438.   { { 0, &(av[2].hd),  &(av[2].hd) }, 0 },
  439.   { { 0, &(av[3].hd),  &(av[3].hd) }, 0 },
  440.   { { 0, &(av[4].hd),  &(av[4].hd) }, 0 },
  441.   { { 0, &(av[5].hd),  &(av[5].hd) }, 0 },
  442.   { { 0, &(av[6].hd),  &(av[6].hd) }, 0 },
  443.   { { 0, &(av[7].hd),  &(av[7].hd) }, 0 },
  444.   { { 0, &(av[8].hd),  &(av[8].hd) }, 0 },
  445.   { { 0, &(av[9].hd),  &(av[9].hd) }, 0 },
  446.  
  447.   { { 0, &(av[10].hd), &(av[10].hd) }, 0 },
  448.   { { 0, &(av[11].hd), &(av[11].hd) }, 0 },
  449.   { { 0, &(av[12].hd), &(av[12].hd) }, 0 },
  450.   { { 0, &(av[13].hd), &(av[13].hd) }, 0 },
  451.   { { 0, &(av[14].hd), &(av[14].hd) }, 0 },
  452.   { { 0, &(av[15].hd), &(av[15].hd) }, 0 },
  453.   { { 0, &(av[16].hd), &(av[16].hd) }, 0 },
  454.   { { 0, &(av[17].hd), &(av[17].hd) }, 0 },
  455.   { { 0, &(av[18].hd), &(av[18].hd) }, 0 },
  456.   { { 0, &(av[19].hd), &(av[19].hd) }, 0 },
  457.  
  458.   { { 0, &(av[20].hd), &(av[20].hd) }, 0 },
  459.   { { 0, &(av[21].hd), &(av[21].hd) }, 0 },
  460.   { { 0, &(av[22].hd), &(av[22].hd) }, 0 },
  461.   { { 0, &(av[23].hd), &(av[23].hd) }, 0 },
  462.   { { 0, &(av[24].hd), &(av[24].hd) }, 0 },
  463.   { { 0, &(av[25].hd), &(av[25].hd) }, 0 },
  464.   { { 0, &(av[26].hd), &(av[26].hd) }, 0 },
  465.   { { 0, &(av[27].hd), &(av[27].hd) }, 0 },
  466.   { { 0, &(av[28].hd), &(av[28].hd) }, 0 },
  467.   { { 0, &(av[29].hd), &(av[29].hd) }, 0 },
  468.  
  469.   { { 0, &(av[30].hd), &(av[30].hd) }, 0 },
  470.   { { 0, &(av[31].hd), &(av[31].hd) }, 0 },
  471.   { { 0, &(av[32].hd), &(av[32].hd) }, 0 },
  472.   { { 0, &(av[33].hd), &(av[33].hd) }, 0 },
  473.   { { 0, &(av[34].hd), &(av[34].hd) }, 0 },
  474.   { { 0, &(av[35].hd), &(av[35].hd) }, 0 },
  475.   { { 0, &(av[36].hd), &(av[36].hd) }, 0 },
  476.   { { 0, &(av[37].hd), &(av[37].hd) }, 0 },
  477.   { { 0, &(av[38].hd), &(av[38].hd) }, 0 },
  478.   { { 0, &(av[39].hd), &(av[39].hd) }, 0 },
  479.  
  480.   { { 0, &(av[40].hd), &(av[40].hd) }, 0 },
  481.   { { 0, &(av[41].hd), &(av[41].hd) }, 0 },
  482.   { { 0, &(av[42].hd), &(av[42].hd) }, 0 },
  483.   { { 0, &(av[43].hd), &(av[43].hd) }, 0 },
  484.   { { 0, &(av[44].hd), &(av[44].hd) }, 0 },
  485.   { { 0, &(av[45].hd), &(av[45].hd) }, 0 },
  486.   { { 0, &(av[46].hd), &(av[46].hd) }, 0 },
  487.   { { 0, &(av[47].hd), &(av[47].hd) }, 0 },
  488.   { { 0, &(av[48].hd), &(av[48].hd) }, 0 },
  489.   { { 0, &(av[49].hd), &(av[49].hd) }, 0 },
  490.  
  491.   { { 0, &(av[50].hd), &(av[50].hd) }, 0 },
  492.   { { 0, &(av[51].hd), &(av[51].hd) }, 0 },
  493.   { { 0, &(av[52].hd), &(av[52].hd) }, 0 },
  494.   { { 0, &(av[53].hd), &(av[53].hd) }, 0 },
  495.   { { 0, &(av[54].hd), &(av[54].hd) }, 0 },
  496.   { { 0, &(av[55].hd), &(av[55].hd) }, 0 },
  497.   { { 0, &(av[56].hd), &(av[56].hd) }, 0 },
  498.   { { 0, &(av[57].hd), &(av[57].hd) }, 0 },
  499.   { { 0, &(av[58].hd), &(av[58].hd) }, 0 },
  500.   { { 0, &(av[59].hd), &(av[59].hd) }, 0 },
  501.  
  502.   { { 0, &(av[60].hd), &(av[60].hd) }, 0 },
  503.   { { 0, &(av[61].hd), &(av[61].hd) }, 0 },
  504.   { { 0, &(av[62].hd), &(av[62].hd) }, 0 },
  505.   { { 0, &(av[63].hd), &(av[63].hd) }, 0 },
  506.   { { 0, &(av[64].hd), &(av[64].hd) }, 0 },
  507.   { { 0, &(av[65].hd), &(av[65].hd) }, 0 },
  508.   { { 0, &(av[66].hd), &(av[66].hd) }, 0 },
  509.   { { 0, &(av[67].hd), &(av[67].hd) }, 0 },
  510.   { { 0, &(av[68].hd), &(av[68].hd) }, 0 },
  511.   { { 0, &(av[69].hd), &(av[69].hd) }, 0 },
  512.  
  513.   { { 0, &(av[70].hd), &(av[70].hd) }, 0 },
  514.   { { 0, &(av[71].hd), &(av[71].hd) }, 0 },
  515.   { { 0, &(av[72].hd), &(av[72].hd) }, 0 },
  516.   { { 0, &(av[73].hd), &(av[73].hd) }, 0 },
  517.   { { 0, &(av[74].hd), &(av[74].hd) }, 0 },
  518.   { { 0, &(av[75].hd), &(av[75].hd) }, 0 },
  519.   { { 0, &(av[76].hd), &(av[76].hd) }, 0 },
  520.   { { 0, &(av[77].hd), &(av[77].hd) }, 0 },
  521.   { { 0, &(av[78].hd), &(av[78].hd) }, 0 },
  522.   { { 0, &(av[79].hd), &(av[79].hd) }, 0 },
  523.  
  524.   { { 0, &(av[80].hd), &(av[80].hd) }, 0 },
  525.   { { 0, &(av[81].hd), &(av[81].hd) }, 0 },
  526.   { { 0, &(av[82].hd), &(av[82].hd) }, 0 },
  527.   { { 0, &(av[83].hd), &(av[83].hd) }, 0 },
  528.   { { 0, &(av[84].hd), &(av[84].hd) }, 0 },
  529.   { { 0, &(av[85].hd), &(av[85].hd) }, 0 },
  530.   { { 0, &(av[86].hd), &(av[86].hd) }, 0 },
  531.   { { 0, &(av[87].hd), &(av[87].hd) }, 0 },
  532.   { { 0, &(av[88].hd), &(av[88].hd) }, 0 },
  533.   { { 0, &(av[89].hd), &(av[89].hd) }, 0 },
  534.  
  535.   { { 0, &(av[90].hd), &(av[90].hd) }, 0 },
  536.   { { 0, &(av[91].hd), &(av[91].hd) }, 0 },
  537.   { { 0, &(av[92].hd), &(av[92].hd) }, 0 },
  538.   { { 0, &(av[93].hd), &(av[93].hd) }, 0 },
  539.   { { 0, &(av[94].hd), &(av[94].hd) }, 0 },
  540.   { { 0, &(av[95].hd), &(av[95].hd) }, 0 },
  541.   { { 0, &(av[96].hd), &(av[96].hd) }, 0 },
  542.   { { 0, &(av[97].hd), &(av[97].hd) }, 0 },
  543.   { { 0, &(av[98].hd), &(av[98].hd) }, 0 },
  544.   { { 0, &(av[99].hd), &(av[99].hd) }, 0 },
  545.  
  546.   { { 0, &(av[100].hd), &(av[100].hd) }, 0 },
  547.   { { 0, &(av[101].hd), &(av[101].hd) }, 0 },
  548.   { { 0, &(av[102].hd), &(av[102].hd) }, 0 },
  549.   { { 0, &(av[103].hd), &(av[103].hd) }, 0 },
  550.   { { 0, &(av[104].hd), &(av[104].hd) }, 0 },
  551.   { { 0, &(av[105].hd), &(av[105].hd) }, 0 },
  552.   { { 0, &(av[106].hd), &(av[106].hd) }, 0 },
  553.   { { 0, &(av[107].hd), &(av[107].hd) }, 0 },
  554.   { { 0, &(av[108].hd), &(av[108].hd) }, 0 },
  555.   { { 0, &(av[109].hd), &(av[109].hd) }, 0 },
  556.  
  557.   { { 0, &(av[110].hd), &(av[110].hd) }, 0 },
  558.   { { 0, &(av[111].hd), &(av[111].hd) }, 0 },
  559.   { { 0, &(av[112].hd), &(av[112].hd) }, 0 },
  560.   { { 0, &(av[113].hd), &(av[113].hd) }, 0 },
  561.   { { 0, &(av[114].hd), &(av[114].hd) }, 0 },
  562.   { { 0, &(av[115].hd), &(av[115].hd) }, 0 },
  563.   { { 0, &(av[116].hd), &(av[116].hd) }, 0 },
  564.   { { 0, &(av[117].hd), &(av[117].hd) }, 0 },
  565.   { { 0, &(av[118].hd), &(av[118].hd) }, 0 },
  566.   { { 0, &(av[119].hd), &(av[119].hd) }, 0 }
  567. };
  568.  
  569. /*
  570.   indexing into bins
  571. */
  572.  
  573. static inline mbinptr size2bin(size_t       sz)
  574. {
  575.   mbinptr b = av;
  576.   while (sz >= (MINSIZE * 2)) { b += 4; sz >>= 1; } /* find power of 2 */
  577.   b += (sz - MINSIZE) >> 2;                         /* find quadrant */
  578.   return b;
  579. }
  580.  
  581.  
  582.  
  583. /* counts maintained if MALLOC_STATS defined */
  584.  
  585. #ifdef MALLOC_STATS
  586.  
  587. static size_t       sbrked_mem;
  588. static size_t       requested_mem;
  589. static size_t       malloced_mem;
  590. static size_t       freed_mem;
  591. static size_t       max_used_mem;
  592.  
  593. static size_t       n_sbrks;
  594. static size_t       n_mallocs;
  595. static size_t       n_frees;
  596. static size_t       n_reallocs;
  597. static size_t       n_reallocs_with_copy;
  598. static size_t       n_avail;
  599. static size_t       max_inuse;
  600.  
  601. static size_t       n_malloc_chunks;
  602. static size_t       n_malloc_bins;
  603.  
  604. static size_t       n_split;
  605. static size_t       n_consol;
  606.  
  607.  
  608. static void do_malloc_stats(const mchunkptr p)
  609. {
  610.   ++n_mallocs;
  611.   if ((n_mallocs-n_frees) > max_inuse)
  612.     max_inuse = n_mallocs - n_frees;
  613.   malloced_mem += (p->size & ~(INUSE));
  614.   if (malloced_mem - freed_mem > max_used_mem)
  615.     max_used_mem = malloced_mem - freed_mem;
  616. }
  617.  
  618. static void do_free_stats(const mchunkptr p)
  619. {
  620.   ++n_frees;
  621.   freed_mem += (p->size & ~(INUSE));
  622. }        
  623.  
  624. #endif
  625.  
  626.  
  627.  
  628. /* Utilities needed below for memalign */
  629. /* This is redundant with libg++ support, but not if used stand-alone */
  630.  
  631. static size_t       gcd(size_t       a, size_t       b)
  632. {
  633.   size_t       tmp;
  634.   
  635.   if (b > a)
  636.   {
  637.     tmp = a; a = b; b = tmp;
  638.   }
  639.   for(;;)
  640.   {
  641.     if (b == 0)
  642.       return a;
  643.     else if (b == 1)
  644.       return b;
  645.     else
  646.     {
  647.       tmp = b;
  648.       b = a % b;
  649.       a = tmp;
  650.     }
  651.   }
  652. }
  653.  
  654. static inline size_t       lcm(size_t       x, size_t       y)
  655. {
  656.   return x / gcd(x, y) * y;
  657. }
  658.  
  659.  
  660.  
  661. /* maintaining INUSE via size field */
  662.  
  663.  
  664. #define inuse(p)       ((p)->size & INUSE)
  665. #define set_inuse(p)   ((p)->size |= INUSE)
  666. #define clear_inuse(b) ((p)->size &= ~INUSE)
  667.  
  668.   
  669. /* operations on  malloc_chunk addresses */
  670.  
  671.  
  672. /* return ptr to next physical malloc_chunk */
  673.  
  674. #define next_chunk(p) ((mchunkptr)((char*)(p) + (p)->size))
  675.  
  676. /* return ptr to previous physical malloc_chunk */
  677.  
  678. #define prev_chunk(p) ((mchunkptr)((char*)(p)-((((int*)(p))[-1]) & ~(INUSE))))
  679.  
  680. /* place size at front and back of chunk */
  681.  
  682.  
  683. static inline void set_size(mchunkptr p, size_t       sz)
  684. {
  685.   p->size = *((int*)((char*)(p) + sz - SIZE_SZ)) = sz;
  686. }
  687.  
  688.  
  689.  
  690.  
  691. /* conversion from malloc headers to user pointers, and back */
  692.  
  693. static inline void* chunk2mem(mchunkptr p) 
  694. { 
  695.   set_inuse(p);
  696.   return (void*)((char*)(p) + SIZE_SZ); 
  697. }
  698.  
  699. static inline mchunkptr mem2chunk(void* mem) 
  700. { 
  701.   mchunkptr p = (mchunkptr)((char*)(mem) - SIZE_SZ); 
  702.  
  703.   /* a quick sanity check */
  704.   size_t       sz = p->size & ~(INUSE);
  705.   if (p->size == sz || sz != *((int*)((char*)(p) + sz - SIZE_SZ)))
  706.     malloc_user_error();
  707.  
  708.   p->size = sz;   /* clears INUSE */
  709.   return p;
  710. }
  711.  
  712.  
  713.  
  714. /* maintaining bins & pointers */
  715.  
  716.  
  717. /* maximum bin actually used */
  718.  
  719. static mbinptr malloc_maxbin = FIRSTBIN;
  720.  
  721.  
  722. /* operations on lists inside bins */
  723.  
  724.  
  725. /* take a chunk off a list */
  726.  
  727. static inline void unlink_chunk(mchunkptr p)
  728. {
  729.   mchunkptr b = p->bk;
  730.   mchunkptr f = p->fd;
  731.  
  732.   f->bk = b;  b->fd = f;
  733.  
  734.   UPDATE_STATS (--n_avail);
  735. }
  736.  
  737.  
  738.  
  739. /* split a chunk and place on the back of a list */
  740.  
  741. static inline void split(mchunkptr p, size_t       offset)
  742. {
  743.   size_t       room = p->size - offset;
  744.   if (room >= MINSIZE)
  745.   {
  746.     mbinptr   bn = size2bin(room);                  /* new bin */
  747.     mchunkptr h  = &(bn->hd);                       /* its head */
  748.     mchunkptr b  = h->bk;                           /* old back element */
  749.     mchunkptr t = (mchunkptr)((char*)(p) + offset); /* remaindered chunk */
  750.     
  751.     /* set size */
  752.     t->size = *((int*)((char*)(t) + room    - SIZE_SZ)) = room;
  753.  
  754.     /* link up */
  755.     t->bk = b;  t->fd = h;  h->bk = b->fd = t;
  756.     
  757.     /* adjust maxbin (h == b means was empty) */
  758.     if (h == b && bn > malloc_maxbin) malloc_maxbin = bn; 
  759.  
  760.     /* adjust size of chunk to be returned */
  761.     p->size = *((int*)((char*)(p) + offset  - SIZE_SZ)) = offset;
  762.  
  763.     UPDATE_STATS ((++n_split, ++n_avail));
  764.   }
  765. }
  766.  
  767.  
  768.  
  769. /* place a consolidated chunk on the back of a list */
  770. /* like above, except no split */
  771.  
  772. static inline void consollink(mchunkptr p)
  773. {
  774.   mbinptr   bn = size2bin(p->size);
  775.   mchunkptr h  = &(bn->hd);
  776.   mchunkptr b  = h->bk;
  777.  
  778.   p->bk = b;  p->fd = h;  h->bk = b->fd = p;
  779.  
  780.   if (h == b && bn > malloc_maxbin) malloc_maxbin = bn; 
  781.  
  782.   UPDATE_STATS(++n_avail);
  783. }
  784.  
  785.  
  786. /* place a freed chunk on the front of a list */
  787.  
  788. static inline void frontlink(mchunkptr p)
  789. {
  790.   mbinptr   bn = size2bin(p->size);
  791.   mchunkptr h  = &(bn->hd);
  792.   mchunkptr f  = h->fd;
  793.  
  794.   p->bk = h;  p->fd = f;  f->bk = h->fd = p;
  795.  
  796.   if (h == f && bn > malloc_maxbin) malloc_maxbin = bn;  
  797.  
  798.   bn->dirty = 1;
  799.  
  800.   UPDATE_STATS(++n_avail);
  801. }
  802.  
  803.  
  804.  
  805. /* Dealing with sbrk */
  806.  
  807.  
  808. /* To link consecutive sbrk regions when possible */
  809.  
  810. static int* last_sbrk_end;
  811.  
  812. /*  who to call when sbrk returns failure */
  813.  
  814. static mchunkptr malloc_from_sys(unsigned nb)
  815. {
  816.   mchunkptr p;
  817.   size_t       sbrk_size;
  818.   int* ip;
  819.   
  820.   /* Minimally, we need to pad with enough space */
  821.   /* to place dummy size/use fields to ends if needed */
  822.  
  823.   sbrk_size = ((nb + SBRK_UNIT - 1 + SIZE_SZ + SIZE_SZ) 
  824.                / SBRK_UNIT) * SBRK_UNIT;
  825.  
  826.   ip = (int*)(sbrk(sbrk_size));
  827.   if ((char*)ip == (char*)(-1)) /* sbrk returns -1 on failure */
  828.   {
  829.     return 0;
  830.   }
  831.  
  832.   UPDATE_STATS ((++n_sbrks, sbrked_mem += sbrk_size));
  833.  
  834.  
  835.   if (last_sbrk_end != &ip[-1]) 
  836.   {                             
  837.     /* It's either first time through or someone else called sbrk. */
  838.     /* Arrange end-markers at front & back */
  839.  
  840.     /* Shouldn't be necessary, but better to be safe */
  841.     while (!aligned_OK(ip)) { ++ip; sbrk_size -= SIZE_SZ; }
  842.  
  843.  
  844.     /* Mark the front as in use to prevent merging. */
  845.     /* Note we can get away with only 1 word, not MINSIZE overhead here */
  846.  
  847.     *ip++ = SIZE_SZ | INUSE;
  848.     
  849.     p = (mchunkptr)ip;
  850.     set_size(p,sbrk_size - (SIZE_SZ + SIZE_SZ)); 
  851.     
  852.   }
  853.   else 
  854.   {
  855.     mchunkptr l;  
  856.  
  857.     /* We can safely make the header start at end of prev sbrked chunk. */
  858.     /* We will still have space left at the end from a previous call */
  859.     /* to place the end marker, below */
  860.  
  861.     p = (mchunkptr)(last_sbrk_end);
  862.     set_size(p, sbrk_size);
  863.  
  864.  
  865.     /* Even better, maybe we can merge with last fragment: */
  866.  
  867.     l = prev_chunk(p);
  868.     if (!inuse(l))  
  869.     {
  870.       unlink_chunk(l);
  871.       set_size(l, p->size + l->size);
  872.       p = l;
  873.     }
  874.  
  875.   }
  876.  
  877.   /* mark the end of sbrked space as in use to prevent merging */
  878.  
  879.   last_sbrk_end = (int*)((char*)p + p->size);
  880.   *last_sbrk_end = SIZE_SZ | INUSE;
  881.  
  882.   UPDATE_STATS((++n_avail, ++n_malloc_chunks));
  883.  
  884.   /* make it safe to unlink in malloc */
  885.   UPDATE_STATS(++n_avail);
  886.   p->fd = p->bk = p;
  887.  
  888.   return p;
  889. }
  890.  
  891.  
  892.  
  893. /* Consolidate dirty bins. */
  894. /* Stop if found a chunk big enough to satisfy current malloc request */
  895.  
  896. /* (It requires much less bookkeeping to consolidate entire bins */
  897. /* at once than to keep records of which chunks might be */
  898. /* consolidatable. So long as the lists are short, which we */
  899. /* try to ensure via small bin ranges, there is little wasted effort.) */
  900.  
  901. static mchunkptr malloc_find_space(size_t       nb)
  902. {
  903.   mbinptr b;
  904.  
  905.   /* first, re-adjust max used bin */
  906.  
  907. #ifdef _USE_RECOVERY_
  908.   static unsigned int recover(int);
  909.   int did_recovery = 0;
  910. #endif
  911.  
  912.   TOTALLY_BOGUS_HACK:
  913.  
  914.   while (malloc_maxbin >= FIRSTBIN && 
  915.          malloc_maxbin->hd.bk == &(malloc_maxbin->hd))
  916.   {
  917.     malloc_maxbin->dirty = 0;
  918.     --malloc_maxbin;
  919.   }
  920.  
  921.   for (b = malloc_maxbin; b >= FIRSTBIN; --b)
  922.   {
  923.     UPDATE_STATS(++n_malloc_bins);
  924.  
  925.     if (b->dirty)
  926.     {
  927.       mchunkptr h = &(b->hd);         /* head of list */
  928.       mchunkptr p = h->fd;            /* chunk traverser */
  929.  
  930.       while (p != h)
  931.       {
  932.         mchunkptr nextp = p->fd;       /* save, in case of relinks */
  933.         int consolidated = 0;          /* only unlink/relink if consolidated */
  934.  
  935.         mchunkptr t;
  936.  
  937.         UPDATE_STATS(++n_malloc_chunks);
  938.  
  939.         while (!inuse(t = prev_chunk(p))) /* consolidate backward */
  940.         {
  941.           if (!consolidated) { consolidated = 1; unlink_chunk(p); }
  942.           if (t == nextp) nextp = t->fd;
  943.           unlink_chunk(t);
  944.           set_size(t, t->size + p->size);
  945.           p = t;
  946.           UPDATE_STATS (++n_consol);
  947.         }
  948.         
  949.         while (!inuse(t = next_chunk(p))) /* consolidate forward */
  950.         {
  951.           if (!consolidated) { consolidated = 1; unlink_chunk(p); }
  952.           if (t == nextp) nextp = t->fd;
  953.           unlink_chunk(t);
  954.           set_size(p, p->size + t->size);
  955.           UPDATE_STATS (++n_consol);
  956.         }
  957.  
  958.        if (consolidated)
  959.        {
  960.           if (p->size >= nb)
  961.           {
  962.             /* make it safe to unlink in malloc */
  963.             UPDATE_STATS(++n_avail);
  964.             p->fd = p->bk = p;
  965.             return p;
  966.           }
  967.           else
  968.             consollink(p);
  969.         }
  970.  
  971.         p = nextp;
  972.  
  973.       }
  974.  
  975.       b->dirty = 0;
  976.  
  977.     }
  978.   }
  979.  
  980. #ifdef _USE_RECOVERY_
  981.   if ( !did_recovery ) {
  982.     did_recovery = 1;
  983.     if ( recover(nb) > nb ) goto TOTALLY_BOGUS_HACK;
  984.   }
  985. #endif
  986.  
  987.   /* nothing available - sbrk some more */
  988.  
  989.   return malloc_from_sys(nb);
  990. }
  991.  
  992.  
  993.  
  994. /*   Finally, the user-level functions  */
  995.  
  996. #ifdef _INTERNAL_MALLOC_
  997. MallocPtrType __internal_malloc(MallocArgType bytes)
  998. #else
  999. MallocPtrType malloc(MallocArgType bytes)
  1000. #endif
  1001. {
  1002.   size_t       nb  = request2size(bytes);  /* padded request size */
  1003.   mbinptr      b   = size2bin(nb);         /* corresponding bin */
  1004.   mchunkptr    hd  = &(b->hd);             /* head of its list */
  1005.   mchunkptr    p   = hd->fd;               /* chunk traverser */
  1006.  
  1007.   UPDATE_STATS((requested_mem+=bytes, ++n_malloc_bins));
  1008.  
  1009.   /* Try a (near) exact match in own bin */
  1010.   /* clean out unusable but consolidatable chunks in bin while traversing */
  1011.  
  1012.   while (p != hd)
  1013.   {
  1014.     UPDATE_STATS(++n_malloc_chunks);
  1015.     if (p->size >= nb)
  1016.       goto found;
  1017.     else    /* try to consolidate; same code as malloc_find_space */
  1018.     {
  1019.       mchunkptr nextp = p->fd;       /* save, in case of relinks */
  1020.       int consolidated = 0;          /* only unlink/relink if consolidated */
  1021.       
  1022.       mchunkptr t;
  1023.  
  1024.       while (!inuse(t = prev_chunk(p))) /* consolidate backward */
  1025.       {
  1026.         if (!consolidated) { consolidated = 1; unlink_chunk(p); }
  1027.         if (t == nextp) nextp = t->fd;
  1028.         unlink_chunk(t);
  1029.         set_size(t, t->size + p->size);
  1030.         p = t;
  1031.         UPDATE_STATS (++n_consol);
  1032.       }
  1033.       
  1034.       while (!inuse(t = next_chunk(p))) /* consolidate forward */
  1035.       {
  1036.         if (!consolidated) { consolidated = 1; unlink_chunk(p); }
  1037.         if (t == nextp) nextp = t->fd;
  1038.         unlink_chunk(t);
  1039.         set_size(p, p->size + t->size);
  1040.         UPDATE_STATS (++n_consol);
  1041.       }
  1042.       
  1043.       if (consolidated)
  1044.       {
  1045.         if (p->size >= nb)
  1046.         {
  1047.           /* make it safe to unlink again below */
  1048.           UPDATE_STATS(++n_avail);
  1049.           p->fd = p->bk = p;
  1050.           goto found;
  1051.         }
  1052.         else
  1053.           consollink(p);
  1054.       }
  1055.  
  1056.       p = nextp;
  1057.  
  1058.     }
  1059.   }
  1060.  
  1061.   b->dirty = 0; /* true if got here */
  1062.  
  1063.   /*  Scan bigger bins for a victim */
  1064.  
  1065.   while (++b <= malloc_maxbin)
  1066.   {
  1067.     UPDATE_STATS(++n_malloc_bins);
  1068.     if ((p = b->hd.bk) != &(b->hd))    /* no need to check size */
  1069.       goto found;
  1070.   }
  1071.  
  1072.   /* Consolidate or sbrk */
  1073.  
  1074.   p = malloc_find_space(nb);
  1075.  
  1076.   if (p == 0) return 0; /* allocation failure */
  1077.  
  1078.  found:   /* Use what we found */
  1079.  
  1080.   unlink_chunk(p);
  1081.   split(p, nb); 
  1082.   UPDATE_STATS(do_malloc_stats(p));
  1083.   return chunk2mem(p);
  1084. }
  1085.  
  1086.  
  1087.  
  1088.  
  1089. #ifdef _INTERNAL_MALLOC_
  1090. static inline void __internal_free(void* mem)
  1091. #else
  1092. FreeRetType free(FreePtrType mem)
  1093. #endif
  1094. {
  1095.   if (mem != 0)
  1096.   {
  1097.     mchunkptr p = mem2chunk(mem);
  1098.     UPDATE_STATS(do_free_stats(p));
  1099.     frontlink(p);
  1100.   }
  1101. }
  1102.  
  1103.  
  1104. void* calloc(size_t       n, size_t       elem_size)
  1105. {
  1106.   size_t       sz = n * elem_size;
  1107.   void* p = (void *) malloc(sz);
  1108.   bzero(p, sz);
  1109.   return p;
  1110. };
  1111.  
  1112. /* This is here for compatibility with older systems */
  1113. void cfree(void *mem)
  1114. {
  1115.   free(mem);
  1116. }
  1117.  
  1118.  
  1119. size_t       malloc_usable_size(void* mem)
  1120. {
  1121.   if (mem == 0)
  1122.     return 0;
  1123.   else
  1124.   {
  1125.     mchunkptr p = (mchunkptr)((char*)(mem) - SIZE_SZ); 
  1126.     size_t       sz = p->size & ~(INUSE);
  1127.     if (p->size == sz || sz != *((int*)((char*)(p) + sz - SIZE_SZ)))
  1128.       return 0;
  1129.     else
  1130.       return sz - MALLOC_MIN_OVERHEAD;
  1131.   }
  1132. }
  1133.  
  1134.  
  1135.  
  1136. #ifdef _INTERNAL_MALLOC_
  1137. static inline void* __internal_realloc(void* mem, unsigned int bytes)
  1138. #else
  1139. void* realloc(void* mem, unsigned int bytes)
  1140. #endif
  1141. {
  1142.   if (mem == 0) 
  1143.     return (void *) malloc(bytes);
  1144.   else
  1145.   {
  1146.     size_t       nb      = request2size(bytes);
  1147.     mchunkptr    p       = mem2chunk(mem);
  1148.     size_t       oldsize = p->size;
  1149.     int          room;
  1150.     mchunkptr    nxt;
  1151.  
  1152.     UPDATE_STATS((++n_reallocs, requested_mem += bytes-oldsize));
  1153.     
  1154.     /* try to expand (even if already big enough), to clean up chunk */
  1155.  
  1156.     while (!inuse(nxt = next_chunk(p)))
  1157.     {
  1158.       UPDATE_STATS ((malloced_mem += nxt->size, ++n_consol));
  1159.       unlink_chunk(nxt);
  1160.       set_size(p, p->size + nxt->size);
  1161.     }
  1162.  
  1163.     room = p->size - nb;
  1164.     if (room >= 0)
  1165.     {
  1166.       split(p, nb);
  1167.       UPDATE_STATS(malloced_mem -= room);
  1168.       return chunk2mem(p);
  1169.     }
  1170.     else /* do the obvious */
  1171.     {
  1172.       void* newmem;
  1173.       set_inuse(p);    /* don't let malloc consolidate us yet! */
  1174.       newmem = malloc(nb);
  1175.       bcopy(mem, newmem, oldsize - SIZE_SZ);
  1176.       free(mem);
  1177.       UPDATE_STATS(++n_reallocs_with_copy);
  1178.       return newmem;
  1179.     }
  1180.   }
  1181. }
  1182.  
  1183.  
  1184.  
  1185. /* return a pointer to space with at least the alignment requested */
  1186.  
  1187. void* memalign(size_t       alignment, size_t       bytes)
  1188. {
  1189.   mchunkptr p;
  1190.   size_t       nb = request2size(bytes);
  1191.  
  1192.   /* find an alignment that both we and the user can live with: */
  1193.   /* least common multiple guarantees mutual happiness */
  1194.   size_t       align = lcm(alignment, MALLOC_MIN_OVERHEAD);
  1195.   size_t       mask = align - 1;
  1196.  
  1197.   /* call malloc with worst case padding to hit alignment; */
  1198.   /* we will give back extra */
  1199.  
  1200.   size_t       req = nb + align + MINSIZE;
  1201.   void* m = malloc(req);
  1202.  
  1203.   if (m == 0) return m;
  1204.  
  1205.   p = mem2chunk(m);
  1206.  
  1207.   /* keep statistics on track */
  1208.  
  1209.   UPDATE_STATS(--n_mallocs);
  1210.   UPDATE_STATS(malloced_mem -= p->size);
  1211.   UPDATE_STATS(requested_mem -= req);
  1212.   UPDATE_STATS(requested_mem += bytes);
  1213.  
  1214.   if (((int)(m) & (mask)) != 0) /* misaligned */
  1215.   {
  1216.  
  1217.     /* find an aligned spot inside chunk */
  1218.  
  1219.     mchunkptr ap = (mchunkptr)(( ((int)(m) + mask) & -align) - SIZE_SZ);
  1220.  
  1221.     size_t       gap = (size_t      )(ap) - (size_t      )(p);
  1222.     size_t       room;
  1223.  
  1224.     /* we need to give back leading space in a chunk of at least MINSIZE */
  1225.  
  1226.     if (gap < MINSIZE)
  1227.     {
  1228.       /* This works since align >= MINSIZE */
  1229.       /* and we've malloc'd enough total room */
  1230.  
  1231.       ap = (mchunkptr)( (int)(ap) + align );
  1232.       gap += align;    
  1233.     }
  1234.  
  1235.     if (gap + nb > p->size) /* can't happen unless chunk sizes corrupted */
  1236.       malloc_user_error();
  1237.  
  1238.     room = p->size - gap;
  1239.  
  1240.     /* give back leader */
  1241.     set_size(p, gap);
  1242.     consollink(p);
  1243.  
  1244.     /* use the rest */
  1245.     p = ap;
  1246.     set_size(p, room);
  1247.   }
  1248.  
  1249.   /* also give back spare room at the end */
  1250.  
  1251.   split(p, nb); 
  1252.   UPDATE_STATS(do_malloc_stats(p));
  1253.   return chunk2mem(p);
  1254.  
  1255. }
  1256.  
  1257. #ifndef sun
  1258. #include <getpagesize.h>
  1259. #endif
  1260.  
  1261. static size_t       malloc_pagesize = 0;
  1262.  
  1263. void* valloc(size_t       bytes)
  1264. {
  1265.   if (malloc_pagesize == 0) malloc_pagesize = getpagesize();
  1266.   return memalign (malloc_pagesize, bytes);
  1267. }
  1268.     
  1269.  
  1270. void malloc_stats()
  1271. {
  1272. #ifndef MALLOC_STATS
  1273. }
  1274. #else
  1275.   int i;
  1276.   mchunkptr p;
  1277.   double nm = (double)(n_mallocs + n_reallocs);
  1278.  
  1279.   fprintf(stderr, "\nmalloc statistics\n\n");
  1280.  
  1281.   if (n_mallocs != 0)
  1282.   fprintf(stderr, "requests  = %10u total size = %10u\tave = %10u\n",
  1283.           n_mallocs, requested_mem, requested_mem/n_mallocs);
  1284.  
  1285.   if (n_mallocs != 0)
  1286.   fprintf(stderr, "mallocs   = %10u total size = %10u\tave = %10u\n",
  1287.           n_mallocs, malloced_mem, malloced_mem/n_mallocs);
  1288.   
  1289.   if (n_frees != 0)
  1290.   fprintf(stderr, "frees     = %10u total size = %10u\tave = %10u\n",
  1291.           n_frees, freed_mem, freed_mem/n_frees);
  1292.   
  1293.   if (n_mallocs-n_frees != 0)
  1294.   fprintf(stderr, "in use    = %10u total size = %10u\tave = %10u\n",
  1295.           n_mallocs-n_frees, malloced_mem-freed_mem, 
  1296.           (malloced_mem-freed_mem) / (n_mallocs-n_frees));
  1297.  
  1298.   if (max_inuse != 0)
  1299.   fprintf(stderr, "max in use= %10u total size = %10u\tave = %10u\n",
  1300.           max_inuse, max_used_mem, max_used_mem / max_inuse);
  1301.   
  1302.   if (n_avail != 0)
  1303.   fprintf(stderr, "available = %10u total size = %10u\tave = %10u\n",
  1304.           n_avail, sbrked_mem - (malloced_mem-freed_mem), 
  1305.           (sbrked_mem - (malloced_mem-freed_mem)) / n_avail);
  1306.  
  1307.   if (n_sbrks != 0)
  1308.   fprintf(stderr, "sbrks     = %10u total size = %10u\tave = %10u\n\n",
  1309.           n_sbrks, sbrked_mem, sbrked_mem/ n_sbrks);
  1310.  
  1311.   if (n_reallocs != 0)
  1312.   fprintf(stderr, "reallocs  = %10u with copy  = %10u\n\n",
  1313.           n_reallocs, n_reallocs_with_copy);
  1314.  
  1315.  
  1316.   if (nm != 0)
  1317.   {
  1318.     fprintf(stderr, "chunks scanned per malloc = %6.3f\n", 
  1319.             n_malloc_chunks / nm);
  1320.     fprintf(stderr, "bins scanned per malloc   = %6.3f\n", 
  1321.             n_malloc_bins / nm);
  1322.     fprintf(stderr, "splits per malloc         = %6.3f\n", 
  1323.             n_split / nm);
  1324.     fprintf(stderr, "consolidations per malloc = %6.3f\n", 
  1325.             n_consol / nm);
  1326.   }
  1327.  
  1328.   fprintf(stderr, "\nfree chunks:\n");
  1329.   for (i = 0; i < MAXBIN; ++i)
  1330.   {
  1331.     p = av[i].hd.fd;
  1332.     if (p != &(av[i].hd))
  1333.     {
  1334.       size_t       count = 1;
  1335.       size_t       sz = p->size;
  1336.       for (p = p->fd; p != &(av[i].hd); p = p->fd)
  1337.       {
  1338.         if (p->size == sz)
  1339.           ++count;
  1340.         else
  1341.         {
  1342.           fprintf(stderr, "\tsize = %10u count = %5u\n", sz, count);
  1343.           count = 1;
  1344.           sz = p->size;
  1345.         }
  1346.       }
  1347.  
  1348.       fprintf(stderr, "\tsize = %10u count = %5u\n", sz, count);
  1349.  
  1350.     }
  1351.   }
  1352. }
  1353. #endif /* MALLOC_STATS */
  1354. /* -*-c-*- */
  1355. #ifndef _UserMalloc_h_
  1356. #define _UserMalloc_h_
  1357.  
  1358. #ifndef _UserMalloc_pre_h_
  1359. #  include "UserMalloc-pre.h"
  1360. #endif
  1361.  
  1362. #ifndef SIZE_SZ
  1363. #  define SIZE_SZ                   (sizeof(SizeType))
  1364. #endif
  1365.  
  1366. #ifndef MINSIZE
  1367. #  define MINSIZE              16 /* from malloc.c */
  1368. #endif
  1369.  
  1370. /*
  1371.  * Return the malloc_chunk structure from a value returned by malloc
  1372.  */
  1373.  
  1374. static inline MallocChunk *external_to_malloc(SizeType *v)
  1375. {
  1376.   return( (MallocChunk*) &v[-1]) ;
  1377. }
  1378.  
  1379. /*
  1380.  * The other way around
  1381.  */
  1382. static inline SizeType *malloc_to_external(MallocChunk *p)
  1383. {
  1384.   SizeType *v = (SizeType*) p;
  1385.   return( &v[1]);
  1386. }
  1387.  
  1388. static inline int malloc_size(MallocChunk *p)
  1389. {
  1390.   return ( (p -> size) & ~0x1 );
  1391. }
  1392.  
  1393. /*****************************************************************************/
  1394.  
  1395.  
  1396. #ifndef CUSTOMALLOC_CACHE_BITS
  1397. #  define CUSTOMALLOC_CACHE_BITS    (5)
  1398. #endif
  1399.  
  1400. #define CUSTOMALLOC_CACHE_VALUE    (1 << CUSTOMALLOC_CACHE_BITS)
  1401. #define CUSTOMALLOC_CACHE_MASK    (~(CUSTOMALLOC_CACHE_VALUE - 1 ))
  1402.  
  1403. #ifdef _IN_OUTPUT_
  1404. static inline void *__customalloc_unlink(char **list)
  1405. {
  1406.   char **p = (char **) *list;
  1407.   *list = p[0];
  1408.   return( &p[0] );
  1409. }
  1410.  
  1411. static inline void __customalloc_link(char **list, void *ptr)
  1412. {
  1413.   char **p = (char **) ptr;
  1414.   p[0] = *list;
  1415.   *list = (char *) ptr;
  1416. }
  1417. #endif
  1418.  
  1419. static inline int size_external_to_internal (int size)
  1420. {
  1421.   return( (size + CUSTOMALLOC_CACHE_VALUE - 1) & CUSTOMALLOC_CACHE_MASK );
  1422. }
  1423.  
  1424. static inline int size_malloc_to_internal (int size)
  1425. {
  1426.   return( size & CUSTOMALLOC_CACHE_MASK );
  1427. }
  1428.  
  1429. #endif
  1430. static char *sbrk_base = 0;
  1431. static char *sbrk_ptr = 0;
  1432. static char *sbrk_end = 0;
  1433.  
  1434. static inline int is_sbrk(void *mem)
  1435. {
  1436.   SizeType* foo = (SizeType *) mem;
  1437.   return( foo[-1] & 0x2 );
  1438. }
  1439.  
  1440. /*
  1441.  * The sbrk malloc allocates 2 * SIZE_SZ overhead, just like the other
  1442.  * malloc, because we want to consistency check routines to be happy.
  1443.  */
  1444. static inline MallocPtrType __sbrk_malloc(MallocArgType size)
  1445. {
  1446.   int rounded_size = ((size + 0x3) & (~0x3)) + 2 * SIZE_SZ;
  1447.   SizeType *next = (unsigned int *) (sbrk_ptr + rounded_size);
  1448.   SizeType *base; 
  1449.  
  1450.   if ( (SizeType) next >= (SizeType) sbrk_end ) {
  1451.  
  1452. #ifndef __customalloc_HowMuchToSbrk_
  1453. #  define __customalloc_HowMuchToSbrk_ ((8 * 1024) - (4 * SIZE_SZ))
  1454. #endif
  1455.  
  1456.     int alloc = __customalloc_HowMuchToSbrk_;
  1457.     int over = sbrk_end - sbrk_ptr;
  1458.  
  1459.     /*
  1460.      * Return unused portion of this extent
  1461.      */
  1462.     if ( sbrk_base && over > MINSIZE ) {
  1463.       /*
  1464.        * We know this will never copy.
  1465.        */
  1466.       int required = sbrk_ptr - sbrk_base + 4;
  1467.       char *new = __internal_realloc(sbrk_base, required + 4);
  1468.       if ( (unsigned int) new != (unsigned int) sbrk_base ) abort();
  1469.  
  1470.       sbrk_base = 0;
  1471.       sbrk_ptr = 0;
  1472.       sbrk_end = 0;
  1473.     }
  1474.  
  1475.     if ( alloc < rounded_size ) {
  1476.       return( __internal_malloc(size) );
  1477.     } 
  1478.     sbrk_base = (char *) __internal_malloc( alloc );
  1479.     sbrk_ptr = sbrk_base;
  1480.     sbrk_end = sbrk_ptr + alloc;
  1481.     next = (SizeType *) (sbrk_ptr + rounded_size);
  1482.   }
  1483.  
  1484.   base = (SizeType *) sbrk_ptr;
  1485.   base[0] = rounded_size | 0x3; /* Mark front end of the chunk */
  1486.   sbrk_ptr = (char *) next;
  1487.   return( (MallocPtrType) &base[1] );
  1488. }
  1489.  
  1490. char *__customalloc_FreeList[9] = {0};
  1491.  
  1492. static int __customalloc_SizeClasses = 9;
  1493.  
  1494. static int __customalloc_ObjectSize[8] = {0, 4, 8, 12, 16, 20, 24, 32};
  1495. static inline MallocPtrType __sbrk_realloc(MallocPtrType mem,
  1496.                          MallocArgType bytes)
  1497. {
  1498.   if ( mem == 0 ) {
  1499.     /*
  1500.      * Some people do the weirdest things.
  1501.      */
  1502.     return( (MallocPtrType) malloc(bytes) );
  1503.   } else {
  1504.     /*
  1505.      * We know p is a pointer to an sbrk'd region at this point
  1506.      */
  1507.     int new_user_size = ((bytes + 0x3) & (~0x3));
  1508.     int new_rounded_size = new_user_size + (2 * SIZE_SZ);
  1509.     
  1510.     SizeType *ptr = (SizeType *) mem;
  1511.     char *base = (char *) &ptr[-1];
  1512.     int old_rounded_size = ptr[-1] & ~0x3;
  1513.     int old_user_size = old_rounded_size - (2 * SIZE_SZ);
  1514.     
  1515.     /*
  1516.      *  OK to simply extend?
  1517.      */
  1518.     if ( (base + old_rounded_size) == sbrk_ptr
  1519.     && ((base + new_rounded_size) < sbrk_end ) ) {
  1520.       sbrk_ptr = base + new_rounded_size;
  1521.       ptr[-1] = ((SizeType) new_rounded_size) | 0x3;
  1522.       return( (MallocPtrType) ptr );
  1523.     } else {
  1524.       int copy_size = (old_user_size < new_user_size )
  1525.     ? old_user_size  : new_user_size;
  1526.       
  1527.       MallocPtrType newmem = (MallocPtrType) malloc(new_user_size);
  1528.       bcopy(mem, newmem, copy_size);
  1529.       free( mem );
  1530.       return( (MallocPtrType) newmem );
  1531.     }
  1532.   }
  1533. }
  1534. /*
  1535.  * Quick fit
  1536.  */
  1537.  
  1538. MallocPtrType realloc(MallocPtrType mem, MallocArgType bytes)
  1539. {
  1540.    if ( mem == 0 ) {
  1541.      return( malloc(bytes) );
  1542.    } else {
  1543.      if ( is_sbrk(mem) ) {
  1544.         return( __sbrk_realloc(mem,bytes));
  1545.      } else {
  1546.         return( __internal_realloc(mem,bytes));
  1547.      }
  1548.    }
  1549. }
  1550.  
  1551. MallocPtrType malloc(MallocArgType bytes)
  1552. {
  1553.   if ( bytes <= 32 ) {
  1554.     /*
  1555.      * Round size up by 4
  1556.      */
  1557.     int index = (bytes+3) >> 2;
  1558.     int size = index << 2;
  1559.     if (__customalloc_FreeList[index]) 
  1560.       return(__customalloc_unlink(&(__customalloc_FreeList[index])));
  1561.     else
  1562.       /*
  1563.        * create it of appropriate size to fit in this bin..
  1564.        */
  1565.       return( __sbrk_malloc(size) ); 
  1566.   } else {
  1567.     return __internal_malloc(bytes);
  1568.   }
  1569. }
  1570.  
  1571. FreeRetType free(FreePtrType p)
  1572. {
  1573.   if ( p ) {
  1574.      MallocChunk *chunk = external_to_malloc(p);
  1575.      int bytes = malloc_size(chunk) - (2 * SIZE_SZ);
  1576.  
  1577.      if ( bytes <= 32 ) {
  1578.        /*
  1579.     * Truncate size
  1580.     */
  1581.        int index = bytes >> 2;
  1582.        __customalloc_link(&(__customalloc_FreeList[index]), p);
  1583.      } else {
  1584.        /*
  1585.     * If it's an sbrk, it must be returned to a freelist
  1586.     */
  1587.        if (is_sbrk(p)) {
  1588.      int index = bytes >> 2;
  1589.      if ( index >= __customalloc_SizeClasses ) {
  1590.        index = __customalloc_SizeClasses - 1;
  1591.      }
  1592.      __customalloc_link(&(__customalloc_FreeList[index]), p);
  1593.        } else {
  1594.      __internal_free(p);
  1595.        }
  1596.      }
  1597.    }
  1598. }
  1599.