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.
16 #ifndef _PDCLIB_GLUE_H
17 #define _PDCLIB_GLUE_H _PDLIB_GLUE_H
18 #include <_PDCLIB_glue.h>
21 /* TODO: Primitive placeholder. Much room for improvement. */
23 /* Keeping pointers to the first and the last element of the free list. */
24 struct _PDCLIB_headnode_t _PDCLIB_memlist = { NULL, NULL };
26 void * malloc( size_t size )
32 if ( size < _PDCLIB_MINALLOC )
34 size = _PDCLIB_MINALLOC;
37 struct _PDCLIB_memnode_t * current = _PDCLIB_memlist.first;
38 struct _PDCLIB_memnode_t * previous = NULL;
39 struct _PDCLIB_memnode_t * firstfit = NULL;
40 struct _PDCLIB_memnode_t * firstfit_previous = NULL;
41 /* Trying exact fit */
42 while ( current != NULL )
44 if ( current->size == size )
46 /* Found exact fit, allocate node */
47 if ( previous != NULL )
49 /* Node in the middle of the list */
50 previous->next = current->next;
54 /* Node is first in list */
55 _PDCLIB_memlist.first = current->next;
57 if ( _PDCLIB_memlist.last == current )
59 /* Node is last in list */
60 _PDCLIB_memlist.last = previous;
62 return (char *)current + sizeof( struct _PDCLIB_memnode_t );
64 else if ( current->size > size && ( firstfit == NULL || current->size < firstfit->size ) )
66 /* Remember previous node in case we do not get an exact fit.
67 Note that this is the node *pointing to* the first fit,
68 as we need that for allocating (i.e., changing next pointer).
70 firstfit_previous = previous;
73 /* Skip to next node */
75 current = current->next;
77 /* No exact fit; go for first fit */
78 if ( firstfit != NULL )
80 if ( ( firstfit->size - size ) > _PDCLIB_MINALLOC )
82 /* Oversized - split into two nodes */
83 struct _PDCLIB_memnode_t * newnode = (struct _PDCLIB_memnode_t *)( (char *)firstfit + sizeof( struct _PDCLIB_memnode_t ) + size );
84 newnode->size = firstfit->size - size - sizeof( struct _PDCLIB_memnode_t );
85 newnode->next = firstfit->next;
86 firstfit->next = newnode;
87 firstfit->size = firstfit->size - newnode->size - sizeof( struct _PDCLIB_memnode_t );
89 if ( firstfit_previous != NULL )
91 /* Node in the middle of the list */
92 firstfit_previous->next = firstfit->next;
96 /* Node is first in list */
97 _PDCLIB_memlist.first = firstfit->next;
99 if ( _PDCLIB_memlist.last == firstfit )
101 /* Node is last in list */
102 _PDCLIB_memlist.last = firstfit_previous;
104 return (char *)firstfit + sizeof( struct _PDCLIB_memnode_t );
108 /* No fit possible; how many additional pages do we need? */
109 int pages = ( ( size + sizeof( struct _PDCLIB_memnode_t ) - 1 ) / _PDCLIB_PAGESIZE ) + 1;
110 /* Allocate more pages */
111 struct _PDCLIB_memnode_t * newnode = (struct _PDCLIB_memnode_t *)_PDCLIB_allocpages( pages );
112 if ( newnode != NULL )
114 newnode->next = NULL;
115 newnode->size = pages * _PDCLIB_PAGESIZE - sizeof( struct _PDCLIB_memnode_t );
116 if ( ( newnode->size - size ) > ( _PDCLIB_MINALLOC + sizeof( struct _PDCLIB_memnode_t ) ) )
118 /* Oversized - split into two nodes */
119 struct _PDCLIB_memnode_t * splitnode = (struct _PDCLIB_memnode_t *)( (char *)newnode + sizeof( struct _PDCLIB_memnode_t ) + size );
120 splitnode->size = newnode->size - size - sizeof( struct _PDCLIB_memnode_t );
121 newnode->size = size;
122 /* Add splitted node as last element to free node list */
123 if ( _PDCLIB_memlist.last == NULL )
125 _PDCLIB_memlist.first = splitnode;
126 splitnode->next = NULL;
130 _PDCLIB_memlist.last->next = splitnode;
132 _PDCLIB_memlist.last = splitnode;
134 return (char *)newnode + sizeof( struct _PDCLIB_memnode_t );
137 /* No fit, heap extension not possible - out of memory */
144 #include <_PDCLIB_test.h>
147 #define MEMTEST( ptr, size ) ( ( ptr = malloc( size ) ) != NULL ) && ( memset( ptr, 0, size ) == ptr )
148 #define PAGETEST( x ) ( pages_start + x * _PDCLIB_PAGESIZE ) == sbrk( 0 )
149 #define EFFECTIVE _PDCLIB_PAGESIZE - sizeof( struct _PDCLIB_memnode_t )
151 /* This can be enabled to give a dump of available nodes */
153 #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 )
155 #define NODETRACE( x ) ( (void) 0 )
158 /* Note that this test driver heavily tests *internals* of the implementation
159 above (and of free() and realloc(), too). That means that changes in the
160 implementation must be accompanied with appropriate changes of the test
161 driver. It does *not* make a good regression tester for the implementation,
162 I am afraid, and thus there is no REGTEST equivalent.
165 void * sbrk( intptr_t );
170 printf( "Start of malloc() testing...\n" );
172 void * ptr1, * ptr2, * ptr3, * ptr4, * ptr5, * ptr6, * ptr7, * ptr8, * ptr9;
173 char * pages_start = _PDCLIB_allocpages( 0 );
174 /* allocating 10 byte; expected: 1 page allocation, node split */
175 TESTCASE( MEMTEST( ptr1, 10 ) );
176 TESTCASE( PAGETEST( 1 ) );
178 /* allocating EFFECTIVE - 10 byte; expected: no page allocation, receiving split node */
179 TESTCASE( MEMTEST( ptr2, EFFECTIVE - 10 - sizeof( struct _PDCLIB_memnode_t ) ) );
180 TESTCASE( PAGETEST( 1 ) );
182 /* allocating EFFECTIVE; expected: 1 page allocation, no node split */
183 TESTCASE( MEMTEST( ptr3, EFFECTIVE ) );
184 TESTCASE( PAGETEST( 2 ) );
186 /* allocating EFFECTIVE - 4; expected: 1 page allocation, no node split */
187 TESTCASE( MEMTEST( ptr4, EFFECTIVE - 4 ) );
188 TESTCASE( PAGETEST( 3 ) );
190 /* freeing and re-allocating EFFECTIVE - 4; expected: no page allocation, no node split */
192 TESTCASE( MEMTEST( ptr5, EFFECTIVE - 4 ) );
193 TESTCASE( ptr4 == ptr5 );
194 TESTCASE( PAGETEST( 3 ) );
196 /* releasing EFFECTIVE; expected: no page release */
198 TESTCASE( PAGETEST( 3 ) );
200 /* allocating EFFECTIVE + _PDCLIB_PAGESIZE; expected: 2 page allocation, no node split */
201 TESTCASE( MEMTEST( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE ) );
202 TESTCASE( PAGETEST( 5 ) );
204 /* reallocating to 10 byte; expected: no page allocation, no node split */
205 TESTCASE( realloc( ptr3, 10 ) == ptr3 );
206 TESTCASE( PAGETEST( 5 ) );
208 /* reallocating to EFFECTIVE + _PDCLIB_PAGESIZE; expected: no page allocation, no node split */
209 TESTCASE( realloc( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE ) == ptr3 );
210 TESTCASE( PAGETEST( 5 ) );
212 /* reallocating to EFFECTIVE + _PDCLIB_PAGESIZE * 2; expected: 3 page allocations, no node split */
213 TESTCASE( realloc( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE * 2 ) != ptr3 );
214 TESTCASE( PAGETEST( 8 ) );
216 /* allocating EFFECTIVE + _PDCLIB_PAGESIZE; expected: no page allocation, no node split */
217 TESTCASE( MEMTEST( ptr4, EFFECTIVE + _PDCLIB_PAGESIZE ) );
218 TESTCASE( PAGETEST( 8 ) );
220 /* allocating zero size; expected: no page allocation, no node split */
221 TESTCASE( ! MEMTEST( ptr6, 0 ) );
222 TESTCASE( PAGETEST( 8 ) );
224 /* allocating 4 byte; expected: no page allocation, upsizing of size, node split */
225 TESTCASE( MEMTEST( ptr7, 4 ) );
226 TESTCASE( PAGETEST( 8 ) );
228 /* allocating rest of page; expected: no page allocation, no node split */
229 TESTCASE( MEMTEST( ptr8, EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) );
230 TESTCASE( PAGETEST( 8 ) );
232 /* freeing, and allocating one byte more; expected: 1 page allocation, no node split */
235 TESTCASE( MEMTEST( ptr8, EFFECTIVE + 1 - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) );
236 TESTCASE( PAGETEST( 9 ) );
238 /* realloc with NULL pointer; expected: no page allocation, no node split */
239 ptr9 = realloc( NULL, 4072 );
240 TESTCASE( ptr9 != NULL );
241 TESTCASE( memset( ptr9, 0, 4072 ) == ptr9 );
242 TESTCASE( PAGETEST( 9 ) );
244 printf( "End of malloc() testing.\n" );
247 printf( "No testing of malloc() - test driver does not know internals of system malloc().\n" );