123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146 |
- /*
- * libc/stdlib/malloc-zarg/heap.h -- heap allocator used for malloc
- *
- * Copyright (C) 2002 NEC Corporation
- * Copyright (C) 2002 Miles Bader <miles@gnu.org>
- *
- * This file is subject to the terms and conditions of the GNU Lesser
- * General Public License. See the file COPYING.LIB in the main
- * directory of this archive for more details.
- *
- * Written by Miles Bader <miles@gnu.org>
- */
- #include <features.h>
- #ifdef __UCLIBC_HAS_THREADS__
- #include <pthread.h>
- typedef pthread_mutex_t mutex_t;
- # define MUTEX_INITIALIZER PTHREAD_MUTEX_INITIALIZER
- # define mutex_lock(x) pthread_mutex_lock(&(x))
- # define mutex_unlock(x) pthread_mutex_unlock(&(x));
- #else
- /* Mutex operations are currently a nop. */
- typedef int mutex_t;
- # define MUTEX_INITIALIZER 0
- # define mutex_lock(x)
- # define mutex_unlock(x)
- #endif
- /* The unit in which allocation is done, due to alignment constraints, etc.
- All allocation requests are rounded up to a multiple of this size.
- Must be a power of 2. */
- #define HEAP_GRANULARITY (sizeof (double))
- struct heap
- {
- struct heap_free_area *free_areas;
- mutex_t lock;
- };
- #define HEAP_INIT { 0, MUTEX_INITIALIZER }
- /* A free-list area `header'. These are actually stored at the _ends_ of
- free areas (to make allocating from the beginning of the area simpler),
- so one might call it a `footer'. */
- struct heap_free_area
- {
- size_t size;
- struct heap_free_area *next, *prev;
- };
- /* Return the address of the end of the frea area FA. */
- #define HEAP_FREE_AREA_END(fa) ((void *)(fa + 1))
- /* Return the address of the beginning of the frea area FA. FA is
- evaulated multiple times. */
- #define HEAP_FREE_AREA_START(fa) ((void *)((char *)(fa + 1) - (fa)->size))
- /* Rounds SZ up to be a multiple of HEAP_GRANULARITY. */
- #define HEAP_ADJUST_SIZE(sz) \
- (((sz) + HEAP_GRANULARITY - 1) & ~(HEAP_GRANULARITY - 1))
- /* The minimum size of a free area. It must include at least enough room
- to hold a struct heap_free_area, plus enough extra to be usefully
- allocated. */
- #define HEAP_MIN_FREE_AREA_SIZE \
- (sizeof (struct heap_free_area) + HEAP_ADJUST_SIZE (1))
- #if 0
- #include <stdio.h>
- static void HEAP_DEBUG (struct heap *heap, const char *str)
- {
- static int recursed = 0;
- if (! recursed)
- {
- struct heap_free_area *fa;
- recursed = 1;
- fprintf (stderr, " %s: heap @0x%lx:\n", str, (long)heap);
- for (fa = heap->free_areas; fa; fa = fa->next)
- fprintf (stderr,
- " 0x%lx: 0x%lx - 0x%lx (%d)\tN=0x%lx, P=0x%lx\n",
- (long)fa,
- (long)HEAP_FREE_AREA_START (fa),
- (long)HEAP_FREE_AREA_END (fa),
- fa->size,
- (long)fa->prev,
- (long)fa->next);
- recursed = 0;
- }
- }
- #else
- #define HEAP_DEBUG(heap, str) (void)0
- #endif
- /* 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
- __heap_free_area_alloc (struct heap *heap,
- struct heap_free_area *fa, size_t size)
- {
- size_t fa_size = fa->size;
- if (fa_size < size + HEAP_MIN_FREE_AREA_SIZE)
- /* There's not enough room left over in FA after allocating the block, so
- just use the whole thing, removing it from the list of free areas. */
- {
- if (fa->next)
- fa->next->prev = fa->prev;
- if (fa->prev)
- fa->prev->next = fa->next;
- else
- heap->free_areas = fa->next;
- /* Remember that we've alloced the whole area. */
- size = fa_size;
- }
- else
- /* Reduce size of FA to account for this allocation. */
- fa->size = fa_size - size;
- return size;
- }
- /* Allocate and return a block at least *SIZE bytes long from HEAP.
- *SIZE is adjusted to reflect the actual amount allocated (which may be
- greater than requested). */
- extern void *__heap_alloc (struct heap *heap, size_t *size);
- /* Allocate SIZE bytes at address MEM in HEAP. Return the actual size
- allocated, or 0 if we failed. */
- extern size_t __heap_alloc_at (struct heap *heap, void *mem, size_t size);
- /* Return the memory area MEM of size SIZE to HEAP. */
- extern void __heap_free (struct heap *heap, void *mem, size_t size);
- /* If the memory area MEM, of size SIZE, immediately follows an existing
- free-area in HEAP, use it to extend that free-area, and return true;
- otherwise return false. */
- extern int __heap_append_free (struct heap *heap, void *mem, size_t size);
|