heap_free.c 2.9 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889
  1. /*
  2. * libc/stdlib/malloc/heap_free.c -- return memory to a heap
  3. *
  4. * Copyright (C) 2002 NEC Corporation
  5. * Copyright (C) 2002 Miles Bader <miles@gnu.org>
  6. *
  7. * This file is subject to the terms and conditions of the GNU Lesser
  8. * General Public License. See the file COPYING.LIB in the main
  9. * directory of this archive for more details.
  10. *
  11. * Written by Miles Bader <miles@gnu.org>
  12. */
  13. #include <stdlib.h>
  14. #include "heap.h"
  15. /* Return the block of memory at MEM, of size SIZE, to HEAP. */
  16. struct heap_free_area *
  17. __heap_free (struct heap_free_area **heap, void *mem, size_t size)
  18. {
  19. struct heap_free_area *fa, *prev_fa;
  20. void *end = (char *)mem + size;
  21. HEAP_DEBUG (*heap, "before __heap_free");
  22. /* Find the right position in the free-list entry to place the new block.
  23. This is the most speed critical loop in this malloc implementation:
  24. since we use a simple linked-list for the free-list, and we keep it in
  25. address-sorted order, it can become very expensive to insert something
  26. in the free-list when it becomes fragmented and long. [A better
  27. implemention would use a balanced tree or something for the free-list,
  28. though that bloats the code-size and complexity quite a bit.] */
  29. for (prev_fa = 0, fa = *heap; fa; prev_fa = fa, fa = fa->next)
  30. if (unlikely (HEAP_FREE_AREA_END (fa) >= mem))
  31. break;
  32. if (fa && HEAP_FREE_AREA_START (fa) <= end)
  33. /* The free-area FA is adjacent to the new block, merge them. */
  34. {
  35. size_t fa_size = fa->size + size;
  36. if (HEAP_FREE_AREA_START (fa) == end)
  37. /* FA is just after the new block, grow down to encompass it. */
  38. {
  39. /* See if FA can now be merged with its predecessor. */
  40. if (prev_fa && mem == HEAP_FREE_AREA_END (prev_fa))
  41. /* Yup; merge PREV_FA's info into FA. */
  42. {
  43. fa_size += prev_fa->size;
  44. __heap_link_free_area_after (heap, fa, prev_fa->prev);
  45. }
  46. }
  47. else
  48. /* FA is just before the new block, expand to encompass it. */
  49. {
  50. struct heap_free_area *next_fa = fa->next;
  51. /* See if FA can now be merged with its successor. */
  52. if (next_fa && end == HEAP_FREE_AREA_START (next_fa))
  53. /* Yup; merge FA's info into NEXT_FA. */
  54. {
  55. fa_size += next_fa->size;
  56. __heap_link_free_area_after (heap, next_fa, prev_fa);
  57. fa = next_fa;
  58. }
  59. else
  60. /* FA can't be merged; move the descriptor for it to the tail-end
  61. of the memory block. */
  62. {
  63. /* The new descriptor is at the end of the extended block,
  64. SIZE bytes later than the old descriptor. */
  65. fa = (struct heap_free_area *)((char *)fa + size);
  66. /* Update links with the neighbors in the list. */
  67. __heap_link_free_area (heap, fa, prev_fa, next_fa);
  68. }
  69. }
  70. fa->size = fa_size;
  71. }
  72. else
  73. /* Make the new block into a separate free-list entry. */
  74. fa = __heap_add_free_area (heap, mem, size, prev_fa, fa);
  75. HEAP_DEBUG (*heap, "after __heap_free");
  76. return fa;
  77. }