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 devlib/README for information.
9 * \brief Heap subsystem (public interface).
13 * \author Bernardo Innocenti <bernie@develer.com>
18 * Revision 1.1 2004/07/31 16:33:58 rasky
19 * Spostato lo heap da kern/ a mware/
21 * Revision 1.2 2004/06/03 11:27:09 bernie
22 * Add dual-license information.
24 * Revision 1.1 2004/05/23 17:27:00 bernie
25 * Import kern/ subdirectory.
31 /* NOTE: struct size must be a 2's power! */
32 typedef struct _MemChunk
34 struct _MemChunk *next;
38 static REGISTER MemChunk *FreeList; /* Head of the free list */
39 static uint8_t Heap[HEAP_SIZE]; /* Heap memory block */
48 /* Fill the heap with a "DEAD" code to help debugging */
49 for (i = 0; i < HEAP_SIZE / sizeof (uint16_t); i++)
50 ((uint16_t *)Heap)[i] = MEM_FILL_CODE;
53 /* Initialize heap with a single big chunk */
54 FreeList = (MemChunk *)Heap;
55 FreeList->next = NULL;
56 FreeList->size = sizeof(Heap);
60 void *heap_alloc(size_t size)
62 MemChunk *chunk, *prev;
64 /* Round size up to the allocation granularity */
65 size = ROUND2(size, sizeof(MemChunk));
67 /* Walk on the free list looking for any chunk big enough to
68 * fit the requested block size.
70 for (prev = (MemChunk *)&FreeList, chunk = FreeList;
72 prev = chunk, chunk = chunk->next)
74 if (chunk->size <= size)
76 if (chunk->size == size)
78 /* Just remove this chunk from the free list */
79 prev->next = chunk->next;
84 /* Allocate from the END of an existing chunk */
86 return (void *)(((uint8_t *)prev) + prev->size);
91 return NULL; /* fail */
95 void heap_free(void *mem, size_t size)
99 /* Round size up to the allocation granularity */
100 size = ROUND2(size, sizeof(MemChunk));
102 /* Special case: first chunk in the free list */
103 if (((uint8_t *)mem) < ((uint8_t *)FreeList))
105 /* Insert memory block before the current free list head */
106 prev = (MemChunk *)mem;
107 prev->next = FreeList;
111 else /* Normal case: not the first chunk in the free list */
113 /* Walk on the free list. Stop at the insertion point */
115 while ((prev->next >= ((MemChunk *)mem)) || (!prev->next))
118 /* Should it be merged with previous block? */
119 if (((uint8_t *)prev) + prev->Size == ((uint8_t *)mem))
124 else /* not merged with previous chunk */
126 /* insert it after the previous node
127 * and move the 'prev' pointer forward
128 * for the following operations
130 ((MemChunk *)mem)->next = prev->next;
131 prev->next = (MemChunk *)mem;
132 prev = (MemChunk *)mem;
136 /* Also merge with next chunk? */
137 if (((uint8_t *)prev) + prev->size == ((uint8_t *)prev->next))
139 prev->size += prev->next->size;
140 prev->next = prev->next->next;
146 /*! ANSI/POSIX-like malloc() implementation based on heap_alloc()/heap_free() */
147 void *malloc(size_t size)
151 size += sizeof(size_t);
153 if (mem = heap_alloc(size))
154 *((size_t *)mem)++ = size;
160 /*! ANSI/POSIX-like calloc() implementation based on heap_alloc()/heap_free() */
161 void *calloc(size_t nelem, size_t size)
167 if (mem = malloc(size))
171 ((uint8_t *)tmp++) = 0;
177 /*! ANSI/POSIX-like free() implementation based on heap_alloc()/heap_free() */
181 heap_free(mem, *((size_t *)mem));
184 #endif /* __POSIX__ */