diff options
| -rw-r--r-- | libc/stdlib/malloc/heap.h | 66 | ||||
| -rw-r--r-- | libc/stdlib/malloc/heap_free.c | 61 |
2 files changed, 74 insertions, 53 deletions
diff --git a/libc/stdlib/malloc/heap.h b/libc/stdlib/malloc/heap.h index 589bf42b0..5207afe8e 100644 --- a/libc/stdlib/malloc/heap.h +++ b/libc/stdlib/malloc/heap.h @@ -115,14 +115,68 @@ static void HEAP_DEBUG (struct heap *heap, const char *str) extern inline void __heap_unlink_free_area (struct heap *heap, struct heap_free_area *fa) { - if (fa->next) - fa->next->prev = fa->prev; - if (fa->prev) - fa->prev->next = fa->next; - else - heap->free_areas = fa->next; + if (fa->next) + fa->next->prev = fa->prev; + if (fa->prev) + fa->prev->next = fa->next; + else + heap->free_areas = fa->next; +} + +/* Link the free-area FA between the existing free-area's PREV and NEXT in + HEAP. PREV and NEXT may be 0; if PREV is 0, FA is installed as the + first free-area. */ +extern inline void +__heap_link_free_area (struct heap *heap, struct heap_free_area *fa, + struct heap_free_area *prev, + struct heap_free_area *next) +{ + fa->next = next; + fa->prev = prev; + + if (prev) + prev->next = fa; + else + heap->free_areas = fa; + if (next) + next->prev = fa; } +/* Update the mutual links between the free-areas PREV and FA in HEAP. + PREV may be 0, in which case FA is installed as the first free-area (but + FA may not be 0). */ +extern inline void +__heap_link_free_area_after (struct heap *heap, + struct heap_free_area *fa, + struct heap_free_area *prev) +{ + if (prev) + prev->next = fa; + else + heap->free_areas = fa; + fa->prev = prev; +} + +/* Add a new free-area MEM, of length SIZE, in between the existing + free-area's PREV and NEXT in HEAP, and return a pointer to its header. + PREV and NEXT may be 0; if PREV is 0, MEM is installed as the first + free-area. */ +extern inline struct heap_free_area * +__heap_add_free_area (struct heap *heap, void *mem, size_t size, + struct heap_free_area *prev, + struct heap_free_area *next) +{ + struct heap_free_area *fa = (struct heap_free_area *) + ((char *)mem + size - sizeof (struct heap_free_area)); + + fa->size = size; + + __heap_link_free_area (heap, fa, prev, next); + + return fa; +} + + /* Allocate SIZE bytes from the front of the free-area FA in HEAP, and return the amount actually allocated (which may be more than SIZE). */ extern inline size_t diff --git a/libc/stdlib/malloc/heap_free.c b/libc/stdlib/malloc/heap_free.c index ac7e00be3..e958f920d 100644 --- a/libc/stdlib/malloc/heap_free.c +++ b/libc/stdlib/malloc/heap_free.c @@ -20,7 +20,7 @@ struct heap_free_area * __heap_free (struct heap *heap, void *mem, size_t size) { - struct heap_free_area *prev_fa, *fa, *new_fa; + struct heap_free_area *prev_fa, *fa; void *end = (char *)mem + size; __heap_lock (heap); @@ -31,10 +31,9 @@ __heap_free (struct heap *heap, void *mem, size_t size) for (prev_fa = 0, fa = heap->free_areas; fa; prev_fa = fa, fa = fa->next) { size_t fa_size = fa->size; - void *fa_end = HEAP_FREE_AREA_END (fa); void *fa_mem = HEAP_FREE_AREA_START (fa); - if (fa_mem == end) + if (end == fa_mem) /* FA is just after MEM, grow down to encompass it. */ { fa_size += size; @@ -43,20 +42,15 @@ __heap_free (struct heap *heap, void *mem, size_t size) if (prev_fa && fa_mem - size == HEAP_FREE_AREA_END (prev_fa)) /* Yup; merge PREV_FA's info into FA. */ { - struct heap_free_area *pp = prev_fa->prev; fa_size += prev_fa->size; - if (pp) - pp->next = fa; - else - heap->free_areas = fa; - fa->prev = pp; + __heap_link_free_area_after (heap, fa, prev_fa->prev); } fa->size = fa_size; goto done; } - else if (fa_end == mem) + else if (HEAP_FREE_AREA_END (fa) == mem) /* FA is just before MEM, expand to encompass it. */ { struct heap_free_area *next_fa = fa->next; @@ -64,33 +58,22 @@ __heap_free (struct heap *heap, void *mem, size_t size) fa_size += size; /* See if FA can now be merged with its successor. */ - if (next_fa && fa_end + size == HEAP_FREE_AREA_START (next_fa)) + if (next_fa && mem + size == HEAP_FREE_AREA_START (next_fa)) { /* Yup; merge FA's info into NEXT_FA. */ fa_size += next_fa->size; - if (prev_fa) - prev_fa->next = next_fa; - else - heap->free_areas = next_fa; - next_fa->prev = prev_fa; + __heap_link_free_area_after (heap, next_fa, prev_fa); fa = next_fa; } else /* FA can't be merged; move the descriptor for it to the tail-end of the memory block. */ { - new_fa = (struct heap_free_area *)((char *)fa + size); - /* Update surrounding free-areas to point to FA's new address. */ - if (prev_fa) - prev_fa->next = new_fa; - else - heap->free_areas = new_fa; - if (next_fa) - next_fa->prev = new_fa; - /* Fill in the moved descriptor. */ - new_fa->prev = prev_fa; - new_fa->next = next_fa; - fa = new_fa; + /* The new descriptor is at the end of the extended block, + SIZE bytes later than the old descriptor. */ + fa = (struct heap_free_area *)((char *)fa + size); + /* Update links with the neighbors in the list. */ + __heap_link_free_area (heap, fa, prev_fa, next_fa); } fa->size = fa_size; @@ -99,28 +82,12 @@ __heap_free (struct heap *heap, void *mem, size_t size) } else if (fa_mem > mem) /* We've reached the right spot in the free-list without finding an - adjacent free-area, so add a new free area to hold MEM. */ + adjacent free-area, so continue below to add a new free area. */ break; } - /* Make a new free-list entry. */ - - /* NEW_FA initially holds only MEM. */ - new_fa = (struct heap_free_area *) - ((char *)mem + size - sizeof (struct heap_free_area)); - new_fa->size = size; - new_fa->next = fa; - new_fa->prev = prev_fa; - - /* Insert NEW_FA in the free-list between PREV_FA and FA. */ - if (prev_fa) - prev_fa->next = new_fa; - else - heap->free_areas = new_fa; - if (fa) - fa->prev = new_fa; - - fa = new_fa; + /* Make MEM into a new free-list entry. */ + fa = __heap_add_free_area (heap, mem, size, prev_fa, fa); done: HEAP_DEBUG (heap, "after __heap_free"); |