4 * Copyright 2004 Develer S.r.l. (http://www.develer.com/)
5 * Copyright 1999,2000,2001 Bernardo Innocenti <bernie@develer.com>
6 * This file is part of DevLib - See README.devlib for information.
9 * \brief Heap subsystem (public interface).
13 * \author Bernardo Innocenti <bernie@develer.com>
18 *#* Revision 1.9 2006/07/19 12:56:27 bernie
19 *#* Convert to new Doxygen style.
21 *#* Revision 1.8 2005/11/04 16:20:02 bernie
22 *#* Fix reference to README.devlib in header.
24 *#* Revision 1.7 2005/04/11 19:10:28 bernie
25 *#* Include top-level headers from cfg/ subdir.
27 *#* Revision 1.6 2004/10/26 09:02:13 bernie
28 *#* heap_free(): Handle NULL pointers like free(), write documentation.
30 *#* Revision 1.5 2004/10/03 20:43:22 bernie
31 *#* Import changes from sc/firmware.
33 *#* Revision 1.1 2004/07/31 16:33:58 rasky
34 *#* Spostato lo heap da kern/ a mware/
36 *#* Revision 1.2 2004/06/03 11:27:09 bernie
37 *#* Add dual-license information.
39 *#* Revision 1.1 2004/05/23 17:27:00 bernie
40 *#* Import kern/ subdirectory.
45 #include <string.h> // memset()
46 #include <cfg/macros.h> // IS_POW2()
47 #include <cfg/debug.h> // ASSERT()
49 /* NOTE: struct size must be a 2's power! */
50 typedef struct _MemChunk
52 struct _MemChunk *next;
56 STATIC_ASSERT(IS_POW2(sizeof(MemChunk)));
58 #define FREE_FILL_CODE 0xDEAD
59 #define ALLOC_FILL_CODE 0xBEEF
61 void heap_init(struct Heap* h, void* memory, size_t size)
64 memset(memory, FREE_FILL_CODE, size);
67 /* Initialize heap with a single big chunk */
68 h->FreeList = (MemChunk *)memory;
69 h->FreeList->next = NULL;
70 h->FreeList->size = size;
74 void *heap_allocmem(struct Heap* h, size_t size)
76 MemChunk *chunk, *prev;
78 /* Round size up to the allocation granularity */
79 size = ROUND2(size, sizeof(MemChunk));
81 /* Handle allocations of 0 bytes */
83 size = sizeof(MemChunk);
85 /* Walk on the free list looking for any chunk big enough to
86 * fit the requested block size.
88 for (prev = (MemChunk *)&h->FreeList, chunk = h->FreeList;
90 prev = chunk, chunk = chunk->next)
92 if (chunk->size >= size)
94 if (chunk->size == size)
96 /* Just remove this chunk from the free list */
97 prev->next = chunk->next;
99 memset(chunk, ALLOC_FILL_CODE, size);
101 return (void *)chunk;
105 /* Allocate from the END of an existing chunk */
108 memset((uint8_t *)chunk + chunk->size, ALLOC_FILL_CODE, size);
110 return (void *)((uint8_t *)chunk + chunk->size);
115 return NULL; /* fail */
119 void heap_freemem(struct Heap* h, void *mem, size_t size)
126 memset(mem, FREE_FILL_CODE, size);
129 /* Round size up to the allocation granularity */
130 size = ROUND2(size, sizeof(MemChunk));
132 /* Handle allocations of 0 bytes */
134 size = sizeof(MemChunk);
136 /* Special case: first chunk in the free list */
137 ASSERT((uint8_t*)mem != (uint8_t*)h->FreeList);
138 if (((uint8_t *)mem) < ((uint8_t *)h->FreeList))
140 /* Insert memory block before the current free list head */
141 prev = (MemChunk *)mem;
142 prev->next = h->FreeList;
146 else /* Normal case: not the first chunk in the free list */
149 * Walk on the free list. Stop at the insertion point (when mem
150 * is between prev and prev->next)
153 while (prev->next < (MemChunk *)mem && prev->next)
156 /* Make sure mem is not *within* prev */
157 ASSERT((uint8_t*)mem >= (uint8_t*)prev + prev->size);
159 /* Should it be merged with previous block? */
160 if (((uint8_t *)prev) + prev->size == ((uint8_t *)mem))
165 else /* not merged with previous chunk */
167 MemChunk *curr = (MemChunk*)mem;
169 /* insert it after the previous node
170 * and move the 'prev' pointer forward
171 * for the following operations
173 curr->next = prev->next;
177 /* Adjust for the following test */
182 /* Also merge with next chunk? */
183 if (((uint8_t *)prev) + prev->size == ((uint8_t *)prev->next))
185 prev->size += prev->next->size;
186 prev->next = prev->next->next;
188 /* There should be only one merge opportunity, becuase we always merge on free */
189 ASSERT((uint8_t*)prev + prev->size != (uint8_t*)prev->next);
193 #if CONFIG_HEAP_MALLOC
195 void *heap_malloc(struct Heap* h, size_t size)
199 size += sizeof(size_t);
200 if ((mem = (size_t*)heap_allocmem(h, size)))
206 void *heap_calloc(struct Heap* h, size_t size)
210 if ((mem = heap_malloc(h, size)))
211 memset(mem, 0, size);
217 * Free a block of memory, determining its size automatically.
219 * \param h Heap from which the block was allocated.
220 * \param mem Pointer to a block of memory previously allocated with
221 * either heap_malloc() or heap_calloc().
223 * \note If \a mem is a NULL pointer, no operation is performed.
225 * \note Freeing the same memory block twice has undefined behavior.
227 * \note This function works like the ANSI C free().
229 void heap_free(struct Heap *h, void *mem)
231 size_t *_mem = (size_t *)mem;
236 heap_freemem(h, _mem, *_mem);
240 #endif /* CONFIG_HEAP_MALLOC */