free.c 4.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156
  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. #include <limits.h>
  11. #include <stddef.h>
  12. #include <stdlib.h>
  13. #include "malloc.h"
  14. /* Return memory to the heap. */
  15. void
  16. _free_internal (void *ptr)
  17. {
  18. int block, blocks, i, type;
  19. struct list *prev, *next;
  20. if (!ptr)
  21. return;
  22. block = BLOCK(ptr);
  23. switch (type = _heapinfo[block].busy.type) {
  24. case 0:
  25. /* Find the free cluster previous to this one in the free list.
  26. Start searching at the last block referenced; this may benefit
  27. programs with locality of allocation. */
  28. i = _heapindex;
  29. if (i > block)
  30. while (i > block)
  31. i = _heapinfo[i].free.prev;
  32. else {
  33. do
  34. i = _heapinfo[i].free.next;
  35. while (i > 0 && i < block);
  36. i = _heapinfo[i].free.prev;
  37. }
  38. /* Determine how to link this block into the free list. */
  39. if (block == i + _heapinfo[i].free.size) {
  40. /* Coalesce this block with its predecessor. */
  41. _heapinfo[i].free.size += _heapinfo[block].busy.info.size;
  42. block = i;
  43. } else {
  44. /* Really link this block back into the free list. */
  45. _heapinfo[block].free.size = _heapinfo[block].busy.info.size;
  46. _heapinfo[block].free.next = _heapinfo[i].free.next;
  47. _heapinfo[block].free.prev = i;
  48. _heapinfo[i].free.next = block;
  49. _heapinfo[_heapinfo[block].free.next].free.prev = block;
  50. }
  51. /* Now that the block is linked in, see if we can coalesce it
  52. with its successor (by deleting its successor from the list
  53. and adding in its size). */
  54. if (block + _heapinfo[block].free.size == _heapinfo[block].free.next) {
  55. _heapinfo[block].free.size
  56. += _heapinfo[_heapinfo[block].free.next].free.size;
  57. _heapinfo[block].free.next
  58. = _heapinfo[_heapinfo[block].free.next].free.next;
  59. _heapinfo[_heapinfo[block].free.next].free.prev = block;
  60. }
  61. /* Now see if we can return stuff to the system. */
  62. blocks = _heapinfo[block].free.size;
  63. if (blocks >= FINAL_FREE_BLOCKS && block + blocks == _heaplimit
  64. && (*__morecore)(0) == ADDRESS(block + blocks)) {
  65. _heaplimit -= blocks;
  66. (*__morecore)(-blocks * BLOCKSIZE);
  67. _heapinfo[_heapinfo[block].free.prev].free.next
  68. = _heapinfo[block].free.next;
  69. _heapinfo[_heapinfo[block].free.next].free.prev
  70. = _heapinfo[block].free.prev;
  71. block = _heapinfo[block].free.prev;
  72. }
  73. /* Set the next search to begin at this block. */
  74. _heapindex = block;
  75. break;
  76. default:
  77. /* Get the address of the first free fragment in this block. */
  78. prev = (struct list *) ((char *) ADDRESS(block)
  79. + (_heapinfo[block].busy.info.frag.first
  80. << type));
  81. if (_heapinfo[block].busy.info.frag.nfree == (BLOCKSIZE >> type) - 1
  82. && _fragblocks[type] > 1) {
  83. /* If all fragments of this block are free, remove them
  84. from the fragment list and free the whole block. */
  85. --_fragblocks[type];
  86. for (next = prev, i = 1; i < BLOCKSIZE >> type; ++i)
  87. next = next->next;
  88. prev->prev->next = next;
  89. if (next)
  90. next->prev = prev->prev;
  91. _heapinfo[block].busy.type = 0;
  92. _heapinfo[block].busy.info.size = 1;
  93. free(ADDRESS(block));
  94. } else if (_heapinfo[block].busy.info.frag.nfree) {
  95. /* If some fragments of this block are free, link this fragment
  96. into the fragment list after the first free fragment of
  97. this block. */
  98. next = ptr;
  99. next->next = prev->next;
  100. next->prev = prev;
  101. prev->next = next;
  102. if (next->next)
  103. next->next->prev = next;
  104. ++_heapinfo[block].busy.info.frag.nfree;
  105. } else {
  106. /* No fragments of this block are free, so link this fragment
  107. into the fragment list and announce that it is the first
  108. free fragment of this block. */
  109. prev = (struct list *) ptr;
  110. _heapinfo[block].busy.info.frag.nfree = 1;
  111. _heapinfo[block].busy.info.frag.first
  112. = (unsigned int) ((char *) ptr - (char *) NULL) % BLOCKSIZE
  113. >> type;
  114. prev->next = _fraghead[type].next;
  115. prev->prev = &_fraghead[type];
  116. prev->prev->next = prev;
  117. if (prev->next)
  118. prev->next->prev = prev;
  119. }
  120. break;
  121. }
  122. }
  123. struct alignlist *_aligned_blocks = NULL;
  124. void
  125. free (void *ptr)
  126. {
  127. register struct alignlist *l;
  128. if (ptr == NULL)
  129. return;
  130. for (l = _aligned_blocks; l != NULL; l = l->next)
  131. {
  132. if (l->aligned == ptr)
  133. {
  134. l->aligned = NULL; /* Mark the slot in the list as free. */
  135. ptr = l->exact;
  136. break;
  137. }
  138. }
  139. _free_internal (ptr);
  140. }