Fix naming conventions.
[bertos.git] / mware / heap.c
1 /*!
2  * \file
3  * <!--
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.
7  * -->
8  *
9  * \brief Heap subsystem (public interface).
10  *
11  * \version $Id$
12  *
13  * \author Bernardo Innocenti <bernie@develer.com>
14  */
15
16 /*#*
17  *#* $Log$
18  *#* Revision 1.8  2005/11/04 16:20:02  bernie
19  *#* Fix reference to README.devlib in header.
20  *#*
21  *#* Revision 1.7  2005/04/11 19:10:28  bernie
22  *#* Include top-level headers from cfg/ subdir.
23  *#*
24  *#* Revision 1.6  2004/10/26 09:02:13  bernie
25  *#* heap_free(): Handle NULL pointers like free(), write documentation.
26  *#*
27  *#* Revision 1.5  2004/10/03 20:43:22  bernie
28  *#* Import changes from sc/firmware.
29  *#*
30  *#* Revision 1.1  2004/07/31 16:33:58  rasky
31  *#* Spostato lo heap da kern/ a mware/
32  *#*
33  *#* Revision 1.2  2004/06/03 11:27:09  bernie
34  *#* Add dual-license information.
35  *#*
36  *#* Revision 1.1  2004/05/23 17:27:00  bernie
37  *#* Import kern/ subdirectory.
38  *#*
39  *#*/
40
41 #include "heap.h"
42 #include <string.h>           // memset()
43 #include <cfg/macros.h>           // IS_POW2()
44 #include <cfg/debug.h>            // ASSERT()
45
46 /* NOTE: struct size must be a 2's power! */
47 typedef struct _MemChunk
48 {
49         struct _MemChunk *next;
50         size_t size;
51 } MemChunk;
52
53 STATIC_ASSERT(IS_POW2(sizeof(MemChunk)));
54
55 #define FREE_FILL_CODE     0xDEAD
56 #define ALLOC_FILL_CODE    0xBEEF
57
58 void heap_init(struct Heap* h, void* memory, size_t size)
59 {
60 #ifdef _DEBUG
61         memset(memory, FREE_FILL_CODE, size);
62 #endif
63
64         /* Initialize heap with a single big chunk */
65         h->FreeList = (MemChunk *)memory;
66         h->FreeList->next = NULL;
67         h->FreeList->size = size;
68 }
69
70
71 void *heap_allocmem(struct Heap* h, size_t size)
72 {
73         MemChunk *chunk, *prev;
74
75         /* Round size up to the allocation granularity */
76         size = ROUND2(size, sizeof(MemChunk));
77
78         /* Handle allocations of 0 bytes */
79         if (!size)
80                 size = sizeof(MemChunk);
81
82         /* Walk on the free list looking for any chunk big enough to
83          * fit the requested block size.
84          */
85         for (prev = (MemChunk *)&h->FreeList, chunk = h->FreeList;
86                 chunk;
87                 prev = chunk, chunk = chunk->next)
88         {
89                 if (chunk->size >= size)
90                 {
91                         if (chunk->size == size)
92                         {
93                                 /* Just remove this chunk from the free list */
94                                 prev->next = chunk->next;
95                                 #ifdef _DEBUG
96                                         memset(chunk, ALLOC_FILL_CODE, size);
97                                 #endif
98                                 return (void *)chunk;
99                         }
100                         else
101                         {
102                                 /* Allocate from the END of an existing chunk */
103                                 chunk->size -= size;
104                                 #ifdef _DEBUG
105                                         memset((uint8_t *)chunk + chunk->size, ALLOC_FILL_CODE, size);
106                                 #endif
107                                 return (void *)((uint8_t *)chunk + chunk->size);
108                         }
109                 }
110         }
111
112         return NULL; /* fail */
113 }
114
115
116 void heap_freemem(struct Heap* h, void *mem, size_t size)
117 {
118         MemChunk *prev;
119
120         ASSERT(mem);
121
122 #ifdef _DEBUG
123         memset(mem, FREE_FILL_CODE, size);
124 #endif
125
126         /* Round size up to the allocation granularity */
127         size = ROUND2(size, sizeof(MemChunk));
128
129         /* Handle allocations of 0 bytes */
130         if (!size)
131                 size = sizeof(MemChunk);
132
133         /* Special case: first chunk in the free list */
134         ASSERT((uint8_t*)mem != (uint8_t*)h->FreeList);
135         if (((uint8_t *)mem) < ((uint8_t *)h->FreeList))
136         {
137                 /* Insert memory block before the current free list head */
138                 prev = (MemChunk *)mem;
139                 prev->next = h->FreeList;
140                 prev->size = size;
141                 h->FreeList = prev;
142         }
143         else /* Normal case: not the first chunk in the free list */
144         {
145                 /*
146                  * Walk on the free list. Stop at the insertion point (when mem
147                  * is between prev and prev->next)
148                  */
149                 prev = h->FreeList;
150                 while (prev->next < (MemChunk *)mem && prev->next)
151                         prev = prev->next;
152
153                 /* Make sure mem is not *within* prev */
154                 ASSERT((uint8_t*)mem >= (uint8_t*)prev + prev->size);
155
156                 /* Should it be merged with previous block? */
157                 if (((uint8_t *)prev) + prev->size == ((uint8_t *)mem))
158                 {
159                         /* Yes */
160                         prev->size += size;
161                 }
162                 else /* not merged with previous chunk */
163                 {
164                         MemChunk *curr = (MemChunk*)mem;
165
166                         /* insert it after the previous node
167                          * and move the 'prev' pointer forward
168                          * for the following operations
169                          */
170                         curr->next = prev->next;
171                         curr->size = size;
172                         prev->next = curr;
173
174                         /* Adjust for the following test */
175                         prev = curr;
176                 }
177         }
178
179         /* Also merge with next chunk? */
180         if (((uint8_t *)prev) + prev->size == ((uint8_t *)prev->next))
181         {
182                 prev->size += prev->next->size;
183                 prev->next = prev->next->next;
184
185                 /* There should be only one merge opportunity, becuase we always merge on free */
186                 ASSERT((uint8_t*)prev + prev->size != (uint8_t*)prev->next);
187         }
188 }
189
190 #if CONFIG_HEAP_MALLOC
191
192 void *heap_malloc(struct Heap* h, size_t size)
193 {
194         size_t *mem;
195
196         size += sizeof(size_t);
197         if ((mem = (size_t*)heap_allocmem(h, size)))
198                 *mem++ = size;
199
200         return mem;
201 }
202
203 void *heap_calloc(struct Heap* h, size_t size)
204 {
205         void *mem;
206
207         if ((mem = heap_malloc(h, size)))
208                 memset(mem, 0, size);
209
210         return mem;
211 }
212
213 /*!
214  * Free a block of memory, determining its size automatically.
215  *
216  * \param h    Heap from which the block was allocated.
217  * \param mem  Pointer to a block of memory previously allocated with
218  *             either heap_malloc() or heap_calloc().
219  *
220  * \note If \a mem is a NULL pointer, no operation is performed.
221  *
222  * \note Freeing the same memory block twice has undefined behavior.
223  *
224  * \note This function works like the ANSI C free().
225  */
226 void heap_free(struct Heap *h, void *mem)
227 {
228         size_t *_mem = (size_t *)mem;
229
230         if (_mem)
231         {
232                 --_mem;
233                 heap_freemem(h, _mem, *_mem);
234         }
235 }
236
237 #endif /* CONFIG_HEAP_MALLOC */