/* xmalloc.c * xmalloc and xfree implementation -- eager version * modified by Douglas Jones to do eager merger, Apr. 3, 2018 * originally by Douglas Jones, Mar. 28, 2018 * * This verion always searches through all blocks from the bottom of the heap. */ #include /* needed for NULL */ #include /* needed for sbrk() */ #include /* needed for intptr_t */ #include "xmalloc.h" /* force compatability with header file */ /* the heap size */ /* under our test 10000 is always safe. For this, 5273 works, 5272 doesn't.) */ #define HEAPSIZE 5273 /* description of boundary tag structure based on homework 9 problem 3 */ #define TAGSIZE ( 2*sizeof(void *) ) #define USED 1 #define FREE 0 /* private memory addressing functions used only in tag manipulation */ #define _PNEXT(p) ((intptr_t)(p) - sizeof(void *)) #define _PPREV(p) ((intptr_t)(p) - 2*sizeof(void *)) /* public functions to access fields of boundary tags */ /* get field values */ #define GETNEXT(p) ( (void *)( *(intptr_t *)_PNEXT( p ) & ~1 ) ) #define GETPREV(p) ( *(void **)_PPREV( p ) ) #define GETUSED(p) ( *(intptr_t *)_PNEXT( p ) & 1 ) #define GETSIZE(p) ( ((intptr_t)GETNEXT( p ) - (intptr_t)(p)) - TAGSIZE ) /* set field values */ #define SETNEXT(p, next) ( \ *(intptr_t *)_PNEXT( p ) = \ (*(intptr_t *)_PNEXT( p ) & 1) | (intptr_t)(next) \ ) #define SETPREV(p, prev) ( *(void **)_PPREV( p ) = (prev) ) #define SETUSED(p, used) ( \ *(intptr_t *)_PNEXT( p ) = \ (*(intptr_t *)_PNEXT( p ) & ~1) | (used) \ ) /* public function to round integer byte counts up to a word boundary */ #define ROUNDUP(i) ( ((i) + (sizeof(void *) - 1)) & ~(sizeof(void *) - 1) ) /* the first byte of the heap */ void * heap = NULL; void * xmalloc( int size ) { /* make sure we have a heap with a tag at each end */ if (heap == NULL) { /* the initial heap has a boundary tag at each end */ int heapsize = ROUNDUP( HEAPSIZE ); heap = (void *)( (intptr_t)sbrk( heapsize + 2*TAGSIZE ) + TAGSIZE ); /* heap points to the first block on the heap */ void * end = (void *)((intptr_t)heap + heapsize + TAGSIZE); SETPREV( heap, NULL ); SETNEXT( heap, end ); SETUSED( heap, FREE ); SETPREV( end, heap ); SETNEXT( end, NULL ); SETUSED( end, USED ); /* used so nobody ever tries to use it */ } /* round size up to the next multiple of a pointer size */ size = ROUNDUP( size ); /* search for a big enough free block */ void * p = heap; while (p != NULL) { void * next = GETNEXT( p ); if ((GETUSED( p ) == FREE) && (GETSIZE( p ) >= size)) { /* we found a big enough block */ if (GETSIZE( p ) > (size + TAGSIZE)) { /* the block is big enough to split */ void * new = (void *)( (intptr_t)p + size + TAGSIZE ); SETNEXT( new, next ); SETPREV( new, p ); SETUSED( new, FREE ); SETNEXT( p, new ); SETPREV( next, new ); } SETUSED( p, USED ); return p; } p = GETNEXT( p ); } /* control only reaches here if there is no big enough free block */ return NULL; } void xfree( void * p ) { void * prev; /* the previous block, needed for block mergers */ void * next; /* the next block, needed for block mergers */ /* mark this block as free */ SETUSED( p, FREE ); /* merge this block with its successor if that is free */ next = GETNEXT( p ); /* assert next != NULL since last heap block marked USED at startup */ if (GETUSED( next ) == FREE) { next = GETNEXT( next ); /* assert next != NULL */ SETPREV( next, p ); SETNEXT( p, next ); } /* merge this block with its predecessor if that is free */ prev = GETPREV( p ); next = GETNEXT( p ); /* assert prev could be NULL if p is the first block in the heap */ if ((prev != NULL) && (GETUSED( prev ) == FREE)) { SETNEXT( prev, next ); SETPREV( next, prev ); } }