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. */
24 /* Keeping pointers to the first and the last element of the free list. */
25 struct _PDCLIB_headnode_t _PDCLIB_memlist = { NULL, NULL };
27 void * malloc( size_t size )
33 if ( size < _PDCLIB_MINALLOC )
35 size = _PDCLIB_MINALLOC;
38 struct _PDCLIB_memnode_t * current = _PDCLIB_memlist.first;
39 struct _PDCLIB_memnode_t * previous = NULL;
40 struct _PDCLIB_memnode_t * firstfit = NULL;
41 struct _PDCLIB_memnode_t * firstfit_previous = NULL;
42 /* Trying exact fit */
43 while ( current != NULL )
45 if ( current->size == size )
47 /* Found exact fit, allocate node */
48 if ( previous != NULL )
50 /* Node in the middle of the list */
51 previous->next = current->next;
55 /* Node is first in list */
56 _PDCLIB_memlist.first = current->next;
58 if ( _PDCLIB_memlist.last == current )
60 /* Node is last in list */
61 _PDCLIB_memlist.last = previous;
63 return (char *)current + sizeof( struct _PDCLIB_memnode_t );
65 else if ( current->size > size && ( firstfit == NULL || current->size < firstfit->size ) )
67 /* Remember previous node in case we do not get an exact fit.
68 Note that this is the node *pointing to* the first fit,
69 as we need that for allocating (i.e., changing next pointer).
71 firstfit_previous = previous;
74 /* Skip to next node */
76 current = current->next;
78 /* No exact fit; go for first fit */
79 if ( firstfit != NULL )
81 if ( ( firstfit->size - size ) > _PDCLIB_MINALLOC )
83 /* Oversized - split into two nodes */
84 struct _PDCLIB_memnode_t * newnode = (struct _PDCLIB_memnode_t *)( (char *)firstfit + sizeof( struct _PDCLIB_memnode_t ) + size );
85 newnode->size = firstfit->size - size - sizeof( struct _PDCLIB_memnode_t );
86 newnode->next = firstfit->next;
87 firstfit->next = newnode;
88 firstfit->size = firstfit->size - newnode->size - sizeof( struct _PDCLIB_memnode_t );
90 if ( firstfit_previous != NULL )
92 /* Node in the middle of the list */
93 firstfit_previous->next = firstfit->next;
97 /* Node is first in list */
98 _PDCLIB_memlist.first = firstfit->next;
100 if ( _PDCLIB_memlist.last == firstfit )
102 /* Node is last in list */
103 _PDCLIB_memlist.last = firstfit_previous;
105 return (char *)firstfit + sizeof( struct _PDCLIB_memnode_t );
109 /* No fit possible; how many additional pages do we need? */
110 uintmax_t pages = ( ( size + sizeof( struct _PDCLIB_memnode_t ) - 1 ) / _PDCLIB_PAGESIZE ) + 1;
111 /* Allocate more pages */
112 struct _PDCLIB_memnode_t * newnode = (struct _PDCLIB_memnode_t *)_PDCLIB_allocpages( pages );
113 if ( newnode != NULL )
115 newnode->next = NULL;
116 newnode->size = pages * _PDCLIB_PAGESIZE - sizeof( struct _PDCLIB_memnode_t );
117 if ( ( newnode->size - size ) > _PDCLIB_MINALLOC )
119 /* Oversized - split into two nodes */
120 struct _PDCLIB_memnode_t * splitnode = (struct _PDCLIB_memnode_t *)( (char *)newnode + sizeof( struct _PDCLIB_memnode_t ) + size );
121 splitnode->size = newnode->size - size - sizeof( struct _PDCLIB_memnode_t );
122 newnode->size = size;
123 /* Add splitted node as last element to free node list */
124 if ( _PDCLIB_memlist.last == NULL )
126 _PDCLIB_memlist.first = splitnode;
127 splitnode->next = NULL;
131 _PDCLIB_memlist.last->next = splitnode;
133 _PDCLIB_memlist.last = splitnode;
135 return (char *)newnode + sizeof( struct _PDCLIB_memnode_t );
138 /* No fit, heap extension not possible - out of memory */
145 #include <_PDCLIB_test.h>
148 #define MEMTEST( ptr, size ) ( ( ptr = malloc( size ) ) != NULL ) && ( memset( ptr, 0, size ) == ptr )
149 #define PAGETEST( x ) ( pages_start + x * _PDCLIB_PAGESIZE ) == sbrk( 0 )
150 #define EFFECTIVE _PDCLIB_PAGESIZE - sizeof( struct _PDCLIB_memnode_t )
152 /* Note that this test driver heavily tests *internals* of the implementation
153 above (and of free() and realloc(), too). That means that changes in the
154 implementation must be accompanied with appropriate changes of the test
155 driver. It does *not* make a good regression tester for the implementation,
156 I am afraid, and thus there is no REGTEST equivalent.
161 int main( int argc, char * argv[] )
166 void * ptr1, * ptr2, * ptr3, * ptr4, * ptr5, * ptr6, * ptr7, * ptr8;
167 char * pages_start = _PDCLIB_allocpages( 0 );
168 /* allocating 10 byte; expected: 1 page allocation, node split */
169 TESTCASE( MEMTEST( ptr1, 10 ) );
170 TESTCASE( PAGETEST( 1 ) );
171 /* allocating EFFECTIVE - 10 byte; expected: no page allocation, receiving split node */
172 TESTCASE( MEMTEST( ptr2, EFFECTIVE - 10 - sizeof( struct _PDCLIB_memnode_t ) ) );
173 TESTCASE( PAGETEST( 1 ) );
174 /* allocating EFFECTIVE; expected: 1 page allocation, no node split */
175 TESTCASE( MEMTEST( ptr3, EFFECTIVE ) );
176 TESTCASE( PAGETEST( 2 ) );
177 /* allocating EFFECTIVE - 4; expected: 1 page allocation, no node split */
178 TESTCASE( MEMTEST( ptr4, EFFECTIVE - 4 ) );
179 TESTCASE( PAGETEST( 3 ) );
180 /* freeing and re-allocating EFFECTIVE - 4; expected: no page allocation, no node split */
182 TESTCASE( MEMTEST( ptr5, EFFECTIVE - 4 ) );
183 TESTCASE( ptr4 == ptr5 );
184 TESTCASE( PAGETEST( 3 ) );
185 /* releasing EFFECTIVE; expected: no page release */
187 TESTCASE( PAGETEST( 3 ) );
188 /* allocating EFFECTIVE + _PDCLIB_PAGESIZE; expected: 2 page allocation, no node split */
189 TESTCASE( MEMTEST( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE ) );
190 TESTCASE( PAGETEST( 5 ) );
191 /* reallocating to 10 byte; expected: no page allocation, no node split */
192 TESTCASE( realloc( ptr3, 10 ) == ptr3 );
193 TESTCASE( PAGETEST( 5 ) );
194 /* reallocating to EFFECTIVE + _PDCLIB_PAGESIZE; expected: no page allocation, no node split */
195 TESTCASE( realloc( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE ) == ptr3 );
196 TESTCASE( PAGETEST( 5 ) );
197 /* reallocating to EFFECTIVE + _PDCLIB_PAGESIZE * 2; expected: 3 page allocations, no node split */
198 TESTCASE( realloc( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE * 2 ) != ptr3 );
199 TESTCASE( PAGETEST( 8 ) );
200 /* allocating EFFECTIVE + _PDCLIB_PAGESIZE; expected: no page allocation, no node split */
201 TESTCASE( MEMTEST( ptr4, EFFECTIVE + _PDCLIB_PAGESIZE ) );
202 TESTCASE( PAGETEST( 8 ) );
203 /* allocating zero size; expected: no page allocation, no node split */
204 TESTCASE( ! MEMTEST( ptr6, 0 ) );
205 TESTCASE( PAGETEST( 8 ) );
206 /* allocating 4 byte; expected: no page allocation, upsizing of size, node split */
207 TESTCASE( MEMTEST( ptr7, 4 ) );
208 TESTCASE( PAGETEST( 8 ) );
209 /* allocating rest of page; expected: no page allocation, no node split */
210 TESTCASE( MEMTEST( ptr8, EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) );
211 TESTCASE( PAGETEST( 8 ) );
212 /* freeing, and allocating one byte more; expected: 1 page allocation, node split */
214 TESTCASE( MEMTEST( ptr8, EFFECTIVE + 1 - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) );
215 TESTCASE( PAGETEST( 9 ) );