lib/malloclib/free.c

   1 /* Free a block of memory allocated by `malloc'.
   2    Copyright 1990, 1991, 1992 Free Software Foundation
   3                   Written May 1989 by Mike Haertel.
   4
   5 This library is free software; you can redistribute it and/or
   6 modify it under the terms of the GNU Library General Public License as
   7 published by the Free Software Foundation; either version 2 of the
   8 License, or (at your option) any later version.
   9
  10 This library is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13 Library General Public License for more details.
  14
  15 You should have received a copy of the GNU Library General Public
  16 License along with this library; see the file COPYING.LIB.  If
  17 not, write to the Free Software Foundation, Inc., 675 Mass Ave,
  18 Cambridge, MA 02139, USA.
  19
  20    The author may be reached (Email) at the address mike@ai.mit.edu,
  21    or (US mail) as Mike Haertel c/o Free Software Foundation.  */
  22
  23 #ifndef _MALLOC_INTERNAL
  24 #define _MALLOC_INTERNAL
  25 #include <malloc.h>
  26 #endif
  27
  28 /* Debugging hook for free.  */
  29 void (*__free_hook) __P ((__ptr_t __ptr));
  30
  31 /* List of blocks allocated by memalign.  */
  32 struct alignlist *_aligned_blocks = NULL;
  33
  34 /* Return memory to the heap.
  35    Like `free' but don't call a __free_hook if there is one.  */
  36 void
  37 _free_internal (ptr)
  38      __ptr_t ptr;
  39 {
  40   int type;
  41   size_t block, blocks;
  42   register size_t i;
  43   struct list *prev, *next;
  44
  45   block = BLOCK (ptr);
  46
  47   type = _heapinfo[block].busy.type;
  48   switch (type)
  49     {
  50     case 0:
  51       /* Get as many statistics as early as we can.  */
  52       --_chunks_used;
  53       _bytes_used -= _heapinfo[block].busy.info.size * BLOCKSIZE;
  54       _bytes_free += _heapinfo[block].busy.info.size * BLOCKSIZE;
  55
  56       /* Find the free cluster previous to this one in the free list.
  57          Start searching at the last block referenced; this may benefit
  58          programs with locality of allocation.  */
  59       i = _heapindex;
  60       if (i > block)
  61         while (i > block)
  62           i = _heapinfo[i].free.prev;
  63       else
  64         {
  65           do
  66             i = _heapinfo[i].free.next;
  67           while (i > 0 && i < block);
  68           i = _heapinfo[i].free.prev;
  69         }
  70
  71       /* Determine how to link this block into the free list.  */
  72       if (block == i + _heapinfo[i].free.size)
  73         {
  74           /* Coalesce this block with its predecessor.  */
  75           _heapinfo[i].free.size += _heapinfo[block].busy.info.size;
  76           block = i;
  77         }
  78       else
  79         {
  80           /* Really link this block back into the free list.  */
  81           _heapinfo[block].free.size = _heapinfo[block].busy.info.size;
  82           _heapinfo[block].free.next = _heapinfo[i].free.next;
  83           _heapinfo[block].free.prev = i;
  84           _heapinfo[i].free.next = block;
  85           _heapinfo[_heapinfo[block].free.next].free.prev = block;
  86           ++_chunks_free;
  87         }
  88
  89       /* Now that the block is linked in, see if we can coalesce it
  90          with its successor (by deleting its successor from the list
  91          and adding in its size).  */
  92       if (block + _heapinfo[block].free.size == _heapinfo[block].free.next)
  93         {
  94           _heapinfo[block].free.size
  95             += _heapinfo[_heapinfo[block].free.next].free.size;
  96           _heapinfo[block].free.next
  97             = _heapinfo[_heapinfo[block].free.next].free.next;
  98           _heapinfo[_heapinfo[block].free.next].free.prev = block;
  99           --_chunks_free;
 100         }
 101
 102       /* Now see if we can return stuff to the system.  */
 103       blocks = _heapinfo[block].free.size;
 104       if (blocks >= FINAL_FREE_BLOCKS && block + blocks == _heaplimit
 105           && (*__morecore) (0) == ADDRESS (block + blocks))
 106         {
 107           register size_t bytes = blocks * BLOCKSIZE;
 108           _heaplimit -= blocks;
 109           (*__morecore) (-bytes);
 110           _heapinfo[_heapinfo[block].free.prev].free.next
 111             = _heapinfo[block].free.next;
 112           _heapinfo[_heapinfo[block].free.next].free.prev
 113             = _heapinfo[block].free.prev;
 114           block = _heapinfo[block].free.prev;
 115           --_chunks_free;
 116           _bytes_free -= bytes;
 117         }
 118
 119       /* Set the next search to begin at this block.  */
 120       _heapindex = block;
 121       break;
 122
 123     default:
 124       /* Do some of the statistics.  */
 125       --_chunks_used;
 126       _bytes_used -= 1 << type;
 127       ++_chunks_free;
 128       _bytes_free += 1 << type;
 129
 130       /* Get the address of the first free fragment in this block.  */
 131       prev = (struct list *) ((char *) ADDRESS (block) +
 132                            (_heapinfo[block].busy.info.frag.first << type));
 133
 134       if (_heapinfo[block].busy.info.frag.nfree == (BLOCKSIZE >> type) - 1
 135           && _fragblocks[type] > 1)
 136         {
 137           /* If all fragments of this block are free, remove them
 138              from the fragment list and free the whole block.  */
 139           --_fragblocks[type];
 140           next = prev;
 141           for (i = 1; i < (size_t) (BLOCKSIZE >> type); ++i)
 142             next = next->next;
 143           prev->prev->next = next;
 144           if (next != NULL)
 145             next->prev = prev->prev;
 146           _heapinfo[block].busy.type = 0;
 147           _heapinfo[block].busy.info.size = 1;
 148
 149           /* Keep the statistics accurate.  */
 150           ++_chunks_used;
 151           _bytes_used += BLOCKSIZE;
 152           _chunks_free -= BLOCKSIZE >> type;
 153           _bytes_free -= BLOCKSIZE;
 154
 155           free (ADDRESS (block));
 156         }
 157       else if (_heapinfo[block].busy.info.frag.nfree != 0)
 158         {
 159           /* If some fragments of this block are free, link this
 160              fragment into the fragment list after the first free
 161              fragment of this block. */
 162           next = (struct list *) ptr;
 163           next->next = prev->next;
 164           next->prev = prev;
 165           prev->next = next;
 166           if (next->next != NULL)
 167             next->next->prev = next;
 168           ++_heapinfo[block].busy.info.frag.nfree;
 169         }
 170       else
 171         {
 172           /* No fragments of this block are free, so link this
 173              fragment into the fragment list and announce that
 174              it is the first free fragment of this block. */
 175           prev = (struct list *) ptr;
 176           _heapinfo[block].busy.info.frag.nfree = 1;
 177           _heapinfo[block].busy.info.frag.first = (unsigned long int)
 178             ((unsigned long int) ((char *) ptr - (char *) NULL)
 179              % BLOCKSIZE >> type);
 180           prev->next = _fraghead[type].next;
 181           prev->prev = &_fraghead[type];
 182           prev->prev->next = prev;
 183           if (prev->next != NULL)
 184             prev->next->prev = prev;
 185         }
 186       break;
 187     }
 188 }
 189
 190 /* Return memory to the heap.  */
 191 void
 192 free (ptr)
 193      __ptr_t ptr;
 194 {
 195   register struct alignlist *l;
 196
 197   if (ptr == NULL)
 198     return;
 199
 200   for (l = _aligned_blocks; l != NULL; l = l->next)
 201     if (l->aligned == ptr)
 202       {
 203         l->aligned = NULL;      /* Mark the slot in the list as free.  */
 204         ptr = l->exact;
 205         break;
 206       }
 207
 208   if (__free_hook != NULL)
 209     (*__free_hook) (ptr);
 210   else
 211     _free_internal (ptr);
 212 }