5 /* void * malloc( size_t )
7 This file is part of the Public Domain C Library (PDCLib).
8 Permission is granted to use, modify, and / or redistribute at will.
18 #define _PDCLIB_INT_H _PDLIB_INT_H
19 #include <_PDCLIB_int.h>
22 /* TODO: Primitive placeholder. Much room for improvement. */
23 /* TODO: Leaves nodes with size < _PDCLIB_MINALLOC, which are never assigned */
25 /* Keeping pointers to the first and the last element of the free list. */
26 struct _PDCLIB_headnode_t _PDCLIB_memlist = { NULL, NULL };
28 void * malloc( size_t size )
34 if ( size < _PDCLIB_MINALLOC )
36 size = _PDCLIB_MINALLOC;
39 struct _PDCLIB_memnode_t * current = _PDCLIB_memlist.first;
40 struct _PDCLIB_memnode_t * previous = NULL;
41 struct _PDCLIB_memnode_t * firstfit = NULL;
42 struct _PDCLIB_memnode_t * firstfit_previous = NULL;
43 /* Trying exact fit */
44 while ( current != NULL )
46 if ( current->size == size )
48 /* Found exact fit, allocate node */
49 if ( previous != NULL )
51 /* Node in the middle of the list */
52 previous->next = current->next;
56 /* Node is first in list */
57 _PDCLIB_memlist.first = current->next;
59 if ( _PDCLIB_memlist.last == current )
61 /* Node is last in list */
62 _PDCLIB_memlist.last = previous;
64 return (char *)current + sizeof( struct _PDCLIB_memnode_t );
66 else if ( current->size > size && ( firstfit == NULL || current->size < firstfit->size ) )
68 /* Remember previous node in case we do not get an exact fit.
69 Note that this is the node *pointing to* the first fit,
70 as we need that for allocating (i.e., changing next pointer).
72 firstfit_previous = previous;
75 /* Skip to next node */
77 current = current->next;
79 /* No exact fit; go for first fit */
80 if ( firstfit != NULL )
82 if ( ( firstfit->size - size ) > _PDCLIB_MINALLOC )
84 /* Oversized - split into two nodes */
85 struct _PDCLIB_memnode_t * newnode = (struct _PDCLIB_memnode_t *)( (char *)firstfit + sizeof( struct _PDCLIB_memnode_t ) + size );
86 newnode->size = firstfit->size - size - sizeof( struct _PDCLIB_memnode_t );
87 newnode->next = firstfit->next;
88 firstfit->next = newnode;
89 firstfit->size = firstfit->size - newnode->size - sizeof( struct _PDCLIB_memnode_t );
91 if ( firstfit_previous != NULL )
93 /* Node in the middle of the list */
94 firstfit_previous->next = firstfit->next;
98 /* Node is first in list */
99 _PDCLIB_memlist.first = firstfit->next;
101 if ( _PDCLIB_memlist.last == firstfit )
103 /* Node is last in list */
104 _PDCLIB_memlist.last = firstfit_previous;
106 return (char *)firstfit + sizeof( struct _PDCLIB_memnode_t );
110 /* No fit possible; how many additional pages do we need? */
111 uintmax_t pages = ( ( size + sizeof( struct _PDCLIB_memnode_t ) - 1 ) / _PDCLIB_PAGESIZE ) + 1;
112 /* Allocate more pages */
113 struct _PDCLIB_memnode_t * newnode = (struct _PDCLIB_memnode_t *)_PDCLIB_allocpages( pages );
114 if ( newnode != NULL )
116 newnode->next = NULL;
117 newnode->size = pages * _PDCLIB_PAGESIZE - sizeof( struct _PDCLIB_memnode_t );
118 if ( ( newnode->size - size ) > _PDCLIB_MINALLOC )
120 /* Oversized - split into two nodes */
121 struct _PDCLIB_memnode_t * splitnode = (struct _PDCLIB_memnode_t *)( (char *)newnode + sizeof( struct _PDCLIB_memnode_t ) + size );
122 splitnode->size = newnode->size - size - sizeof( struct _PDCLIB_memnode_t );
123 newnode->size = size;
124 /* Add splitted node as last element to free node list */
125 if ( _PDCLIB_memlist.last == NULL )
127 _PDCLIB_memlist.first = splitnode;
128 splitnode->next = NULL;
132 _PDCLIB_memlist.last->next = splitnode;
134 _PDCLIB_memlist.last = splitnode;
136 return (char *)newnode + sizeof( struct _PDCLIB_memnode_t );
139 /* No fit, heap extension not possible - out of memory */
146 #include <_PDCLIB_test.h>
149 #define MEMTEST( ptr, size ) ( ( ptr = malloc( size ) ) != NULL ) && ( memset( ptr, 0, size ) == ptr )
150 #define PAGETEST( x ) ( pages_start + x * _PDCLIB_PAGESIZE ) == sbrk( 0 )
151 #define EFFECTIVE _PDCLIB_PAGESIZE - sizeof( struct _PDCLIB_memnode_t )
153 /* Note that this test driver heavily tests *internals* of the implementation
154 above (and of free() and realloc(), too). That means that changes in the
155 implementation must be accompanied with appropriate changes of the test
156 driver. It does *not* make a good regression tester for the implementation,
157 I am afraid, and thus there is no REGTEST equivalent.
162 int main( int argc, char * argv[] )
167 void * ptr1, * ptr2, * ptr3, * ptr4, * ptr5, * ptr6, * ptr7, * ptr8, * ptr9;
168 char * pages_start = _PDCLIB_allocpages( 0 );
169 /* allocating 10 byte; expected: 1 page allocation, node split */
170 TESTCASE( MEMTEST( ptr1, 10 ) );
171 TESTCASE( PAGETEST( 1 ) );
172 /* allocating EFFECTIVE - 10 byte; expected: no page allocation, receiving split node */
173 TESTCASE( MEMTEST( ptr2, EFFECTIVE - 10 - sizeof( struct _PDCLIB_memnode_t ) ) );
174 TESTCASE( PAGETEST( 1 ) );
175 /* allocating EFFECTIVE; expected: 1 page allocation, no node split */
176 TESTCASE( MEMTEST( ptr3, EFFECTIVE ) );
177 TESTCASE( PAGETEST( 2 ) );
178 /* allocating EFFECTIVE - 4; expected: 1 page allocation, no node split */
179 TESTCASE( MEMTEST( ptr4, EFFECTIVE - 4 ) );
180 TESTCASE( PAGETEST( 3 ) );
181 /* freeing and re-allocating EFFECTIVE - 4; expected: no page allocation, no node split */
183 TESTCASE( MEMTEST( ptr5, EFFECTIVE - 4 ) );
184 TESTCASE( ptr4 == ptr5 );
185 TESTCASE( PAGETEST( 3 ) );
186 /* releasing EFFECTIVE; expected: no page release */
188 TESTCASE( PAGETEST( 3 ) );
189 /* allocating EFFECTIVE + _PDCLIB_PAGESIZE; expected: 2 page allocation, no node split */
190 TESTCASE( MEMTEST( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE ) );
191 TESTCASE( PAGETEST( 5 ) );
192 /* reallocating to 10 byte; expected: no page allocation, no node split */
193 TESTCASE( realloc( ptr3, 10 ) == ptr3 );
194 TESTCASE( PAGETEST( 5 ) );
195 /* reallocating to EFFECTIVE + _PDCLIB_PAGESIZE; expected: no page allocation, no node split */
196 TESTCASE( realloc( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE ) == ptr3 );
197 TESTCASE( PAGETEST( 5 ) );
198 /* reallocating to EFFECTIVE + _PDCLIB_PAGESIZE * 2; expected: 3 page allocations, no node split */
199 TESTCASE( realloc( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE * 2 ) != ptr3 );
200 TESTCASE( PAGETEST( 8 ) );
201 /* allocating EFFECTIVE + _PDCLIB_PAGESIZE; expected: no page allocation, no node split */
202 TESTCASE( MEMTEST( ptr4, EFFECTIVE + _PDCLIB_PAGESIZE ) );
203 TESTCASE( PAGETEST( 8 ) );
204 /* allocating zero size; expected: no page allocation, no node split */
205 TESTCASE( ! MEMTEST( ptr6, 0 ) );
206 TESTCASE( PAGETEST( 8 ) );
207 /* allocating 4 byte; expected: no page allocation, upsizing of size, node split */
208 TESTCASE( MEMTEST( ptr7, 4 ) );
209 TESTCASE( PAGETEST( 8 ) );
210 /* allocating rest of page; expected: no page allocation, no node split */
211 TESTCASE( MEMTEST( ptr8, EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) );
212 TESTCASE( PAGETEST( 8 ) );
213 /* freeing, and allocating one byte more; expected: 1 page allocation, node split */
215 TESTCASE( MEMTEST( ptr8, EFFECTIVE + 1 - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) );
216 TESTCASE( PAGETEST( 9 ) );
217 /* realloc with NULL pointer; expected: no page allocation, no node split */
218 ptr9 = realloc( NULL, 4072 );
219 TESTCASE( ptr9 != NULL );
220 TESTCASE( memset( ptr9, 0, 4072 ) == ptr9 );
221 TESTCASE( PAGETEST( 9 ) );