3 /* void * malloc( size_t )
5 This file is part of the Public Domain C Library (PDCLib).
6 Permission is granted to use, modify, and / or redistribute at will.
14 #ifndef _PDCLIB_GLUE_H
15 #define _PDCLIB_GLUE_H _PDLIB_GLUE_H
16 #include <_PDCLIB_glue.h>
19 /* TODO: Primitive placeholder. Much room for improvement. */
21 /* Keeping pointers to the first and the last element of the free list. */
22 struct _PDCLIB_headnode_t _PDCLIB_memlist = { NULL, NULL };
24 void * malloc( size_t size )
30 if ( size < _PDCLIB_MINALLOC )
32 size = _PDCLIB_MINALLOC;
35 struct _PDCLIB_memnode_t * current = _PDCLIB_memlist.first;
36 struct _PDCLIB_memnode_t * previous = NULL;
37 struct _PDCLIB_memnode_t * firstfit = NULL;
38 struct _PDCLIB_memnode_t * firstfit_previous = NULL;
39 /* Trying exact fit */
40 while ( current != NULL )
42 if ( current->size == size )
44 /* Found exact fit, allocate node */
45 if ( previous != NULL )
47 /* Node in the middle of the list */
48 previous->next = current->next;
52 /* Node is first in list */
53 _PDCLIB_memlist.first = current->next;
55 if ( _PDCLIB_memlist.last == current )
57 /* Node is last in list */
58 _PDCLIB_memlist.last = previous;
60 return (char *)current + sizeof( struct _PDCLIB_memnode_t );
62 else if ( current->size > size && ( firstfit == NULL || current->size < firstfit->size ) )
64 /* Remember previous node in case we do not get an exact fit.
65 Note that this is the node *pointing to* the first fit,
66 as we need that for allocating (i.e., changing next pointer).
68 firstfit_previous = previous;
71 /* Skip to next node */
73 current = current->next;
75 /* No exact fit; go for first fit */
76 if ( firstfit != NULL )
78 if ( ( firstfit->size - size ) > _PDCLIB_MINALLOC )
80 /* Oversized - split into two nodes */
81 struct _PDCLIB_memnode_t * newnode = (struct _PDCLIB_memnode_t *)( (char *)firstfit + sizeof( struct _PDCLIB_memnode_t ) + size );
82 newnode->size = firstfit->size - size - sizeof( struct _PDCLIB_memnode_t );
83 newnode->next = firstfit->next;
84 firstfit->next = newnode;
85 firstfit->size = firstfit->size - newnode->size - sizeof( struct _PDCLIB_memnode_t );
87 if ( firstfit_previous != NULL )
89 /* Node in the middle of the list */
90 firstfit_previous->next = firstfit->next;
94 /* Node is first in list */
95 _PDCLIB_memlist.first = firstfit->next;
97 if ( _PDCLIB_memlist.last == firstfit )
99 /* Node is last in list */
100 _PDCLIB_memlist.last = firstfit_previous;
102 return (char *)firstfit + sizeof( struct _PDCLIB_memnode_t );
106 /* No fit possible; how many additional pages do we need? */
107 int pages = ( ( size + sizeof( struct _PDCLIB_memnode_t ) - 1 ) / _PDCLIB_PAGESIZE ) + 1;
108 /* Allocate more pages */
109 struct _PDCLIB_memnode_t * newnode = (struct _PDCLIB_memnode_t *)_PDCLIB_allocpages( pages );
110 if ( newnode != NULL )
112 newnode->next = NULL;
113 newnode->size = pages * _PDCLIB_PAGESIZE - sizeof( struct _PDCLIB_memnode_t );
114 if ( ( newnode->size - size ) > ( _PDCLIB_MINALLOC + sizeof( struct _PDCLIB_memnode_t ) ) )
116 /* Oversized - split into two nodes */
117 struct _PDCLIB_memnode_t * splitnode = (struct _PDCLIB_memnode_t *)( (char *)newnode + sizeof( struct _PDCLIB_memnode_t ) + size );
118 splitnode->size = newnode->size - size - sizeof( struct _PDCLIB_memnode_t );
119 newnode->size = size;
120 /* Add splitted node as last element to free node list */
121 if ( _PDCLIB_memlist.last == NULL )
123 _PDCLIB_memlist.first = splitnode;
127 _PDCLIB_memlist.last->next = splitnode;
129 splitnode->next = NULL; /* TODO: This is bug #7, uncovered by testdriver yet. */
130 _PDCLIB_memlist.last = splitnode;
132 return (char *)newnode + sizeof( struct _PDCLIB_memnode_t );
135 /* No fit, heap extension not possible - out of memory */
142 #include <_PDCLIB_test.h>
145 #define MEMTEST( ptr, size ) ( ( ptr = malloc( size ) ) != NULL ) && ( memset( ptr, 0, size ) == ptr )
146 #define PAGETEST( x ) ( pages_start + x * _PDCLIB_PAGESIZE ) == sbrk( 0 )
147 #define EFFECTIVE _PDCLIB_PAGESIZE - sizeof( struct _PDCLIB_memnode_t )
149 /* This can be enabled to give a dump of available nodes */
151 #define NODETRACE( x ) do { struct _PDCLIB_memnode_t * tracer = _PDCLIB_memlist.first; printf( "Node trace #%d, %d allocated pages\n", x, ( (intptr_t)sbrk( 0 ) - (intptr_t)pages_start ) / _PDCLIB_PAGESIZE ); while ( tracer != NULL ) { printf( "- node %p, size %#x\n", (void *)tracer, tracer->size ); tracer = tracer->next; } } while ( 0 )
153 #define NODETRACE( x ) ( (void) 0 )
156 /* Note that this test driver heavily tests *internals* of the implementation
157 above (and of free() and realloc(), too). That means that changes in the
158 implementation must be accompanied with appropriate changes of the test
159 driver. It does *not* make a good regression tester for the implementation,
160 I am afraid, and thus there is no REGTEST equivalent.
163 void * sbrk( intptr_t );
168 void * ptr1, * ptr2, * ptr3, * ptr4, * ptr5, * ptr6, * ptr7, * ptr8, * ptr9;
169 char * pages_start = _PDCLIB_allocpages( 0 );
170 /* allocating 10 byte; expected: 1 page allocation, node split */
171 TESTCASE( MEMTEST( ptr1, 10 ) );
172 TESTCASE( PAGETEST( 1 ) );
174 /* allocating EFFECTIVE - 10 byte; expected: no page allocation, receiving split node */
175 TESTCASE( MEMTEST( ptr2, EFFECTIVE - 10 - sizeof( struct _PDCLIB_memnode_t ) ) );
176 TESTCASE( PAGETEST( 1 ) );
178 /* allocating EFFECTIVE; expected: 1 page allocation, no node split */
179 TESTCASE( MEMTEST( ptr3, EFFECTIVE ) );
180 TESTCASE( PAGETEST( 2 ) );
182 /* allocating EFFECTIVE - 4; expected: 1 page allocation, no node split */
183 TESTCASE( MEMTEST( ptr4, EFFECTIVE - 4 ) );
184 TESTCASE( PAGETEST( 3 ) );
186 /* freeing and re-allocating EFFECTIVE - 4; expected: no page allocation, no node split */
188 TESTCASE( MEMTEST( ptr5, EFFECTIVE - 4 ) );
189 TESTCASE( ptr4 == ptr5 );
190 TESTCASE( PAGETEST( 3 ) );
192 /* releasing EFFECTIVE; expected: no page release */
194 TESTCASE( PAGETEST( 3 ) );
196 /* allocating EFFECTIVE + _PDCLIB_PAGESIZE; expected: 2 page allocation, no node split */
197 TESTCASE( MEMTEST( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE ) );
198 TESTCASE( PAGETEST( 5 ) );
200 /* reallocating to 10 byte; expected: no page allocation, no node split */
201 TESTCASE( realloc( ptr3, 10 ) == ptr3 );
202 TESTCASE( PAGETEST( 5 ) );
204 /* reallocating to EFFECTIVE + _PDCLIB_PAGESIZE; expected: no page allocation, no node split */
205 TESTCASE( realloc( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE ) == ptr3 );
206 TESTCASE( PAGETEST( 5 ) );
208 /* reallocating to EFFECTIVE + _PDCLIB_PAGESIZE * 2; expected: 3 page allocations, no node split */
209 TESTCASE( realloc( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE * 2 ) != ptr3 );
210 TESTCASE( PAGETEST( 8 ) );
212 /* allocating EFFECTIVE + _PDCLIB_PAGESIZE; expected: no page allocation, no node split */
213 TESTCASE( MEMTEST( ptr4, EFFECTIVE + _PDCLIB_PAGESIZE ) );
214 TESTCASE( PAGETEST( 8 ) );
216 /* allocating zero size; expected: no page allocation, no node split */
217 TESTCASE( ! MEMTEST( ptr6, 0 ) );
218 TESTCASE( PAGETEST( 8 ) );
220 /* allocating 4 byte; expected: no page allocation, upsizing of size, node split */
221 TESTCASE( MEMTEST( ptr7, 4 ) );
222 TESTCASE( PAGETEST( 8 ) );
224 /* allocating rest of page; expected: no page allocation, no node split */
225 TESTCASE( MEMTEST( ptr8, EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) );
226 TESTCASE( PAGETEST( 8 ) );
228 /* freeing, and allocating one byte more; expected: 1 page allocation, no node split */
231 TESTCASE( MEMTEST( ptr8, EFFECTIVE + 1 - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) );
232 TESTCASE( PAGETEST( 9 ) );
234 /* realloc with NULL pointer; expected: no page allocation, no node split */
235 ptr9 = realloc( NULL, 4072 );
236 TESTCASE( ptr9 != NULL );
237 TESTCASE( memset( ptr9, 0, 4072 ) == ptr9 );
238 TESTCASE( PAGETEST( 9 ) );
241 puts( " NOTEST malloc() test driver is PDCLib-specific." );