/* mp5.c */
/* a buddy-system heap manager
 * written by Douglas Jones
 */

#include <unistd.h>
#include <stdlib.h>
#include <stdint.h>

#include "myheap.h"

/* static data structures */

#define FREELISTS 32
void * freelist[FREELISTS]; /* freelist[i] lists blocks of size 2 to the i */
int freetop;                /* max value of i during heapinit */

/**********************************************
 * private code, the actual buddy system code * 
 **********************************************/

static void * buddyallocate( int i ) {
	if (i > freetop) { /* failure */
		return NULL;
	} else if (freelist[i] != NULL) { /* easy case */
		void * b = freelist[i];
		freelist[i] = *(void **)b;
		return b;
	} else { /* hard case, must split a block */
		void * b = buddyallocate( i + 1 );
		if (b != NULL) { /* split the block */
			void * q; /* the buddy of b */
			q = (void *)((intptr_t)b + (1 << i));

			/* put the buddy on the free list */
			*(void **)q = freelist[i];
			freelist[i] = q;
		}
		return b;
	}
}

static void buddydeallocate( void * p, int i ) {
	void * b = freelist[i];
	if (b == NULL) { /* trivial case */
		*(void **)p = NULL;
		freelist[i] = p;
		return;
	} else {
		int s = 1<<i; /* the block size */
		void * pbuddy = (void *)(s ^ (intptr_t)p);
		void * pparent = (void *)((~s) & (intptr_t)p);
		if (b == pbuddy) { /* merge blocks */
			void * q = *(void **)b; /* find successor */
			freelist[i] = q; /* snip b out of free list */
			buddydeallocate( pparent, i + 1 );
			return;
		} else { /* walk down free list looking for buddy */
			while (*(void **)b != NULL) {
				void * q = *(void **)b; /* merger candidate */
				if (q == pbuddy) { /* merge */
					void * r = *(void **)q; /* find succ */
					*(void **)b = r; /* snip q from list */
					buddydeallocate( pparent, i + 1 );
					return;
				}
				b = *(void **)b; /* walk onward */
			}
			/* buddy not found */
			*(void **)p = freelist[i];
			freelist[i] = p;
			return;
		}	
	}
}

/*************************************************
 * code to implement the interface specification *
 *************************************************/

void heapinit( int s ) {
	int i;       /* block size is 2 to the i */
	void * heap; /* the start of the heap */
	void * end;  /* the address after the end of the heap */

        /* initializes the heap to have size s */
	heap = sbrk( s );
	if (heap == (void *)(-1)) {
		write( 2, "can't create heap\n", 18 );
		exit( EXIT_FAILURE );
	}
	end = (void *)(s + (intptr_t)heap);

	/* clear all free lists */
	for (i = 0; i < FREELISTS; i++) freelist[i] = NULL;

	/* now chop up the initial heap into free blocks */
	i = 0;
	s = 1; /* in what follows, s always equals 2 to the i */
	for (;;) {
		/* find the largest possible block starting at heap */
		/* note, s - 1 has i consecutive one bits at the left end */
		while ( ((s - 1) & (intptr_t)heap) == 0 ) {
			i = i + 1;
			s = s << 1;
		}
		/* this always overshoots */
		i = i - 1;
		s = s >> 1;
		/* assert that heap has exactly i trailing zeros */

		if ( (s + (intptr_t)heap) > (intptr_t)end ) break;

		/* we can chip a block of size s off of the remaining heap */
		if (s >= sizeof(void *)) {
			*(void **)heap = freelist[i];
			freelist[i] = heap;
			freetop = i;
		}
		heap = (void *)(s + (intptr_t)heap);
	}

	/* Now, size s is too big, so we chip off successively smaller blocks */
	for (;;) {
		i = i - 1;
		s = s >> 1;
		if (s < sizeof(void *)) break;

		if ( (s + (intptr_t)heap) <= (intptr_t)end ) { /* one block */
			*(void **)heap = freelist[i];
			freelist[i] = heap;
			heap = (void *)(s + (intptr_t)heap);
		}
	}

	/* heap is now initialized */
}

void * mymalloc( int s ) {
        void * p;
        int i = 0;
        int twotothei = 1;

	/* find the right size */
        s = s + sizeof( intptr_t );
        while (twotothei < s) { /* compute i = log2 s */
                i = i + 1;
                twotothei = twotothei << 1;
        }

	/* use the buddy system */
        p = buddyallocate( i );
	if (p != NULL) {
		*(intptr_t *) p = i; /* save block size in block */
        	return (void *)((intptr_t)p + sizeof(intptr_t));
	} else {
		return NULL;
	}
}

void myfree( void * p ) {
        int i;

	/* get the recorded size */
        p = (void *)((intptr_t)p - sizeof(intptr_t));
        i = *(intptr_t *) p; /* recover the block size from the block */

	/* use the buddy system */
        buddydeallocate( p, i );
}