pd.if.org Git - pdclib.old/blob - functions/stdlib/malloc.c

   1 /* $Id$ */
   2
   3 /* Release $Name$ */
   4
   5 /* void * malloc( size_t )
   6
   7    This file is part of the Public Domain C Library (PDCLib).
   8    Permission is granted to use, modify, and / or redistribute at will.
   9 */
  10
  11 #include <stdlib.h>
  12
  13 #ifndef REGTEST
  14
  15 #include <stdint.h>
  16
  17 #ifndef _PDCLIB_INT_H
  18 #define _PDCLIB_INT_H _PDLIB_INT_H
  19 #include <_PDCLIB_int.h>
  20 #endif
  21
  22 /* TODO: Primitive placeholder. Much room for improvement. */
  23 /* TODO: Leaves nodes with size < _PDCLIB_MINALLOC, which are never assigned */
  24
  25 /* Keeping pointers to the first and the last element of the free list. */
  26 struct _PDCLIB_headnode_t _PDCLIB_memlist = { NULL, NULL };
  27
  28 void * malloc( size_t size )
  29 {
  30     if ( size == 0 )
  31     {
  32         return NULL;
  33     }
  34     if ( size < _PDCLIB_MINALLOC )
  35     {
  36         size = _PDCLIB_MINALLOC;
  37     }
  38     {
  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 )
  45     {
  46         if ( current->size == size )
  47         {
  48             /* Found exact fit, allocate node */
  49             if ( previous != NULL )
  50             {
  51                 /* Node in the middle of the list */
  52                 previous->next = current->next;
  53             }
  54             else
  55             {
  56                 /* Node is first in list */
  57                 _PDCLIB_memlist.first = current->next;
  58             }
  59             if ( _PDCLIB_memlist.last == current )
  60             {
  61                 /* Node is last in list */
  62                 _PDCLIB_memlist.last = previous;
  63             }
  64             return (char *)current + sizeof( struct _PDCLIB_memnode_t );
  65         }
  66         else if ( current->size > size && ( firstfit == NULL || current->size < firstfit->size ) )
  67         {
  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).
  71             */
  72             firstfit_previous = previous;
  73             firstfit = current;
  74         }
  75         /* Skip to next node */
  76         previous = current;
  77         current = current->next;
  78     }
  79     /* No exact fit; go for first fit */
  80     if ( firstfit != NULL )
  81     {
  82         if ( ( firstfit->size - size ) > _PDCLIB_MINALLOC )
  83         {
  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 );
  90         }
  91         if ( firstfit_previous != NULL )
  92         {
  93             /* Node in the middle of the list */
  94             firstfit_previous->next = firstfit->next;
  95         }
  96         else
  97         {
  98             /* Node is first in list */
  99             _PDCLIB_memlist.first = firstfit->next;
 100         }
 101         if ( _PDCLIB_memlist.last == firstfit )
 102         {
 103             /* Node is last in list */
 104             _PDCLIB_memlist.last = firstfit_previous;
 105         }
 106         return (char *)firstfit + sizeof( struct _PDCLIB_memnode_t );
 107     }
 108     }
 109     {
 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 )
 115     {
 116         newnode->next = NULL;
 117         newnode->size = pages * _PDCLIB_PAGESIZE - sizeof( struct _PDCLIB_memnode_t );
 118         if ( ( newnode->size - size ) > _PDCLIB_MINALLOC )
 119         {
 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 )
 126             {
 127                 _PDCLIB_memlist.first = splitnode;
 128                 splitnode->next = NULL;
 129             }
 130             else
 131             {
 132                 _PDCLIB_memlist.last->next = splitnode;
 133             }
 134             _PDCLIB_memlist.last = splitnode;
 135         }
 136         return (char *)newnode + sizeof( struct _PDCLIB_memnode_t );
 137     }
 138     }
 139     /* No fit, heap extension not possible - out of memory */
 140     return NULL;
 141 }
 142
 143 #endif
 144
 145 #ifdef TEST
 146 #include <_PDCLIB_test.h>
 147 #include <string.h>
 148
 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 )
 152
 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.
 158 */
 159
 160 #include <unistd.h>
 161
 162 int main( int argc, char * argv[] )
 163 {
 164     BEGIN_TESTS;
 165 #ifndef REGTEST
 166     {
 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 */
 182     free( ptr4 );
 183     TESTCASE( MEMTEST( ptr5, EFFECTIVE - 4 ) );
 184     TESTCASE( ptr4 == ptr5 );
 185     TESTCASE( PAGETEST( 3 ) );
 186     /* releasing EFFECTIVE; expected: no page release */
 187     free( ptr3 );
 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 */
 214     free( ptr8 );
 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 ) );
 222     }
 223 #endif
 224     return TEST_RESULTS;
 225 }
 226
 227 #endif