/* xmalloc.c
 * xmalloc and xfree implementation -- somewhat lazy version
 * modified by Douglas Jones to comment on deleting PREV, Apr. 11, 2018
 * modified by Douglas Jones to do somewhat lazy 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 <stdio.h>        /* needed for NULL */
#include <unistd.h>       /* needed for sbrk() */
#include <stdint.h>       /* 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

/* NOTE: this algorithm does not need the PREV field, so if we set
 * TAGSIZE to 1*sizeof(void *), delete the definitions of GETPREV and SETPREV
 * and delete all statements that call GETPREV and SETPREV, then we
 * can reduct HEAPSIZE to 4897 and still pass our test
 */

/* 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) {
			while (GETUSED( next ) == FREE) {
				/* we can merge blocks */
				next = GETNEXT( next );
				/* assert next != NULL */
				SETNEXT( p, next );
				SETPREV( next, p );
			}

			if (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 ) {
	SETUSED( p, FREE );
}