pd.if.org Git - pdclib/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
  24 /* Keeping pointers to the first and the last element of the free list. */
  25 struct _PDCLIB_headnode_t _PDCLIB_memlist = { NULL, NULL };
  26
  27 void * malloc( size_t size )
  28 {
  29     if ( size == 0 )
  30     {
  31         return NULL;
  32     }
  33     if ( size < _PDCLIB_MINALLOC )
  34     {
  35         size = _PDCLIB_MINALLOC;
  36     }
  37     {
  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 )
  44     {
  45         if ( current->size == size )
  46         {
  47             /* Found exact fit, allocate node */
  48             if ( previous != NULL )
  49             {
  50                 /* Node in the middle of the list */
  51                 previous->next = current->next;
  52             }
  53             else
  54             {
  55                 /* Node is first in list */
  56                 _PDCLIB_memlist.first = current->next;
  57             }
  58             if ( _PDCLIB_memlist.last == current )
  59             {
  60                 /* Node is last in list */
  61                 _PDCLIB_memlist.last = previous;
  62             }
  63             return (char *)current + sizeof( struct _PDCLIB_memnode_t );
  64         }
  65         else if ( current->size > size && ( firstfit == NULL || current->size < firstfit->size ) )
  66         {
  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).
  70             */
  71             firstfit_previous = previous;
  72             firstfit = current;
  73         }
  74         /* Skip to next node */
  75         previous = current;
  76         current = current->next;
  77     }
  78     /* No exact fit; go for first fit */
  79     if ( firstfit != NULL )
  80     {
  81         if ( ( firstfit->size - size ) > _PDCLIB_MINALLOC )
  82         {
  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 );
  89         }
  90         if ( firstfit_previous != NULL )
  91         {
  92             /* Node in the middle of the list */
  93             firstfit_previous->next = firstfit->next;
  94         }
  95         else
  96         {
  97             /* Node is first in list */
  98             _PDCLIB_memlist.first = firstfit->next;
  99         }
 100         if ( _PDCLIB_memlist.last == firstfit )
 101         {
 102             /* Node is last in list */
 103             _PDCLIB_memlist.last = firstfit_previous;
 104         }
 105         return (char *)firstfit + sizeof( struct _PDCLIB_memnode_t );
 106     }
 107     }
 108     {
 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 )
 114     {
 115         newnode->next = NULL;
 116         newnode->size = pages * _PDCLIB_PAGESIZE - sizeof( struct _PDCLIB_memnode_t );
 117         if ( ( newnode->size - size ) > _PDCLIB_MINALLOC )
 118         {
 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 )
 125             {
 126                 _PDCLIB_memlist.first = splitnode;
 127                 splitnode->next = NULL;
 128             }
 129             else
 130             {
 131                 _PDCLIB_memlist.last->next = splitnode;
 132             }
 133             _PDCLIB_memlist.last = splitnode;
 134         }
 135         return (char *)newnode + sizeof( struct _PDCLIB_memnode_t );
 136     }
 137     }
 138     /* No fit, heap extension not possible - out of memory */
 139     return NULL;
 140 }
 141
 142 #endif
 143
 144 #ifdef TEST
 145 #include <_PDCLIB_test.h>
 146 #include <string.h>
 147
 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 )
 151
 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.
 157 */
 158
 159 #include <unistd.h>
 160
 161 int main( int argc, char * argv[] )
 162 {
 163     BEGIN_TESTS;
 164 #ifndef REGTEST
 165     {
 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 */
 181     free( ptr4 );
 182     TESTCASE( MEMTEST( ptr5, EFFECTIVE - 4 ) );
 183     TESTCASE( ptr4 == ptr5 );
 184     TESTCASE( PAGETEST( 3 ) );
 185     /* releasing EFFECTIVE; expected: no page release */
 186     free( ptr3 );
 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 */
 213     free( ptr8 );
 214     TESTCASE( MEMTEST( ptr8, EFFECTIVE + 1 - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) );
 215     TESTCASE( PAGETEST( 9 ) );
 216     }
 217 #endif
 218     return TEST_RESULTS;
 219 }
 220
 221 #endif