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 5This library is free software; you can redistribute it and/or 6modify it under the terms of the GNU Library General Public License as 7published by the Free Software Foundation; either version 2 of the 8License, or (at your option) any later version. 9 10This library is distributed in the hope that it will be useful, 11but WITHOUT ANY WARRANTY; without even the implied warranty of 12MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13Library General Public License for more details. 14 15You should have received a copy of the GNU Library General Public 16License along with this library; see the file COPYING.LIB. If 17not, write to the Free Software Foundation, Inc., 675 Mass Ave, 18Cambridge, 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. */ 29void (*__free_hook) __P ((__ptr_t __ptr)); 30 31/* List of blocks allocated by memalign. */ 32struct 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. */ 36void 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 { 136 /* If all fragments of this block are free, remove them 137 from the fragment list and free the whole block. */ 138 next = prev; 139 for (i = 1; i < (size_t) (BLOCKSIZE >> type); ++i) 140 next = next->next; 141 prev->prev->next = next; 142 if (next != NULL) 143 next->prev = prev->prev; 144 _heapinfo[block].busy.type = 0; 145 _heapinfo[block].busy.info.size = 1; 146 147 /* Keep the statistics accurate. */ 148 ++_chunks_used; 149 _bytes_used += BLOCKSIZE; 150 _chunks_free -= BLOCKSIZE >> type; 151 _bytes_free -= BLOCKSIZE; 152 153 free (ADDRESS (block)); 154 } 155 else if (_heapinfo[block].busy.info.frag.nfree != 0) 156 { 157 /* If some fragments of this block are free, link this 158 fragment into the fragment list after the first free 159 fragment of this block. */ 160 next = (struct list *) ptr; 161 next->next = prev->next; 162 next->prev = prev; 163 prev->next = next; 164 if (next->next != NULL) 165 next->next->prev = next; 166 ++_heapinfo[block].busy.info.frag.nfree; 167 } 168 else 169 { 170 /* No fragments of this block are free, so link this 171 fragment into the fragment list and announce that 172 it is the first free fragment of this block. */ 173 prev = (struct list *) ptr; 174 _heapinfo[block].busy.info.frag.nfree = 1; 175 _heapinfo[block].busy.info.frag.first = (unsigned long int) 176 ((unsigned long int) ((char *) ptr - (char *) NULL) 177 % BLOCKSIZE >> type); 178 prev->next = _fraghead[type].next; 179 prev->prev = &_fraghead[type]; 180 prev->prev->next = prev; 181 if (prev->next != NULL) 182 prev->next->prev = prev; 183 } 184 break; 185 } 186} 187 188/* Return memory to the heap. */ 189void 190free (ptr) 191 __ptr_t ptr; 192{ 193 register struct alignlist *l; 194 195 if (ptr == NULL) 196 return; 197 198 for (l = _aligned_blocks; l != NULL; l = l->next) 199 if (l->aligned == ptr) 200 { 201 l->aligned = NULL; /* Mark the slot in the list as free. */ 202 ptr = l->exact; 203 break; 204 } 205 206 if (__free_hook != NULL) 207 (*__free_hook) (ptr); 208 else 209 _free_internal (ptr); 210} 211