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