home *** CD-ROM | disk | FTP | other *** search
/ Serving the Web / ServingTheWeb1995.disc1of1.iso / linux / slacksrce / d / libc / libc-4.6 / libc-4 / libc-linux / malloc-930716 / free.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-30  |  4.4 KB  |  139 lines
  1. /* free.c - C standard library routine.
  2.    Copyright (c) 1989, 1993  Michael J. Haertel
  3.    You may redistribute this library under the terms of the
  4.    GNU Library General Public License (version 2 or any later
  5.    version) as published by the Free Software Foundation.
  6.    THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT ANY EXPRESS OR IMPLIED
  7.    WARRANTY.  IN PARTICULAR, THE AUTHOR MAKES NO REPRESENTATION OR
  8.    WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY OF THIS
  9.    SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. */
  10.  
  11. #include <limits.h>
  12. #include <stddef.h>
  13. #include <stdlib.h>
  14. #include "malloc.h"
  15.  
  16. /* Return memory to the heap. */
  17. void
  18. free(void *ptr)
  19. {
  20.     int block, blocks, i, type;
  21.     struct list *prev, *next;
  22.  
  23.     if (!ptr)
  24.     return;
  25.  
  26.     block = BLOCK(ptr);
  27.  
  28.     switch (type = _heapinfo[block].busy.type) {
  29.     case 0:
  30.     /* Find the free cluster previous to this one in the free list.
  31.        Start searching at the last block referenced; this may benefit
  32.        programs with locality of allocation. */
  33.     i = _heapindex;
  34.     if (i > block)
  35.         while (i > block)
  36.         i = _heapinfo[i].free.prev;
  37.     else {
  38.         do
  39.         i = _heapinfo[i].free.next;
  40.         while (i > 0 && i < block);
  41.         i = _heapinfo[i].free.prev;
  42.     }
  43.  
  44.     /* Determine how to link this block into the free list. */
  45.     if (block == i + _heapinfo[i].free.size) {
  46.         /* Coalesce this block with its predecessor. */
  47.         _heapinfo[i].free.size += _heapinfo[block].busy.info.size;
  48.         block = i;
  49.     } else {
  50.         /* Really link this block back into the free list. */
  51.         _heapinfo[block].free.size = _heapinfo[block].busy.info.size;
  52.         _heapinfo[block].free.next = _heapinfo[i].free.next;
  53.         _heapinfo[block].free.prev = i;
  54.         _heapinfo[i].free.next = block;
  55.         _heapinfo[_heapinfo[block].free.next].free.prev = block;
  56.     }
  57.  
  58.     /* Now that the block is linked in, see if we can coalesce it
  59.        with its successor (by deleting its successor from the list
  60.        and adding in its size). */
  61.     if (block + _heapinfo[block].free.size == _heapinfo[block].free.next) {
  62.         _heapinfo[block].free.size
  63.         += _heapinfo[_heapinfo[block].free.next].free.size;
  64.         _heapinfo[block].free.next
  65.         = _heapinfo[_heapinfo[block].free.next].free.next;
  66.         _heapinfo[_heapinfo[block].free.next].free.prev = block;
  67.     }
  68.  
  69.     /* Now see if we can return stuff to the system. */
  70.     blocks = _heapinfo[block].free.size;
  71.     if (blocks >= FINAL_FREE_BLOCKS && block + blocks == _heaplimit
  72.         && (*_morecore)(0) == ADDRESS(block + blocks)) {
  73.         _heaplimit -= blocks;
  74.         (*_morecore)(-blocks * BLOCKSIZE);
  75.         _heapinfo[_heapinfo[block].free.prev].free.next
  76.         = _heapinfo[block].free.next;
  77.         _heapinfo[_heapinfo[block].free.next].free.prev
  78.         = _heapinfo[block].free.prev;
  79.         block = _heapinfo[block].free.prev;
  80.     }
  81.  
  82.     /* Set the next search to begin at this block. */
  83.     _heapindex = block;
  84.     break;
  85.  
  86.     default:
  87.     /* Get the address of the first free fragment in this block. */
  88.     prev = (struct list *) ((char *) ADDRESS(block)
  89.                 + (_heapinfo[block].busy.info.frag.first
  90.                    << type));
  91.  
  92.     if (_heapinfo[block].busy.info.frag.nfree == (BLOCKSIZE >> type) - 1
  93.     && _fragblocks[type] > 1) {
  94.         /* If all fragments of this block are free, remove them
  95.            from the fragment list and free the whole block. */
  96.         --_fragblocks[type];
  97.         for (next = prev, i = 1; i < BLOCKSIZE >> type; ++i)
  98.         next = next->next;
  99.         prev->prev->next = next;
  100.         if (next)
  101.         next->prev = prev->prev;
  102.         _heapinfo[block].busy.type = 0;
  103.         _heapinfo[block].busy.info.size = 1;
  104.         free(ADDRESS(block));
  105.     } else if (_heapinfo[block].busy.info.frag.nfree) {
  106.         /* If some fragments of this block are free, link this fragment
  107.            into the fragment list after the first free fragment of
  108.            this block. */
  109.         next = ptr;
  110.         next->next = prev->next;
  111.         next->prev = prev;
  112.         prev->next = next;
  113.         if (next->next)
  114.         next->next->prev = next;
  115.         ++_heapinfo[block].busy.info.frag.nfree;
  116.     } else {
  117.         /* No fragments of this block are free, so link this fragment
  118.            into the fragment list and announce that it is the first
  119.            free fragment of this block. */
  120.         prev = (struct list *) ptr;
  121.         _heapinfo[block].busy.info.frag.nfree = 1;
  122.         _heapinfo[block].busy.info.frag.first
  123.         = (unsigned int) ((char *) ptr - (char *) NULL) % BLOCKSIZE
  124.           >> type;
  125.         prev->next = _fraghead[type].next;
  126.         prev->prev = &_fraghead[type];
  127.         prev->prev->next = prev;
  128.         if (prev->next)
  129.         prev->next->prev = prev;
  130.     }
  131.     break;
  132.     }
  133. }
  134.  
  135. #include <gnu-stabs.h>
  136. #ifdef elf_alias
  137. elf_alias (free, cfree);
  138. #endif
  139.