/* mp6.c solution by Douglas Jones */

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

#include "buddy.h"

/* the maximum block size is 2**(MAX-1) */
#define MAX 30

/* all the freelists are initially empty */
static void * freelists[MAX] = { NULL };

void * buddyalloc( int i ) {
	/* buddy system allocate one block of size 2 to the i */
	void * p;
	if (i >= MAX) return NULL;
	if (freelists[i] != NULL) { /* easy case */
		p = freelists[i];
		freelists[i] = *(void **)p;

	} else { /* freelists[i] == NULL, hard case */
		p = buddyalloc( i + 1 );
		if (p != NULL) { /* split oversized block */
			void * b = (void *)(((intptr_t) p) ^ (1 << i));
			*(void **)b = NULL;
			freelists[i] = b;
		}

	}
	return p;
}

void buddyfree( void * p, int i ) {
	/* buddy system free the block p of size 2 to the i */
	void * b; /* candidate for buddy of p */
	void ** pb = &freelists[i]; /* pointer b */

	/* search for buddy in free list */
	for (;;) { /* loop exit by break*/
		b = *pb;
		if (b == NULL) { /* search reached end of list */

			/* put p at end of list */
			*(void **)p = NULL;
			*pb = p;

			/* quit loop */
			break;
		}
		if (((intptr_t)p) == (((intptr_t)b) ^ (1 << i))) {

			/* unlink b from its free list */
			*pb = *(void **)b;

			/* compute address of merged blocks */
			p = (void *)(((intptr_t)p) & ((intptr_t)b));

			/* free result of merger */
			buddyfree( p, i + 1 );
			break;
		}
		/* walk down list */
		pb = (void **)b;
	}
}

void enlargeheap( int i ) {
	/* enlarge the heap to guarantee a free block of size 2**i */
	intptr_t twotothei;
	void * p;     /* start of new block of memory (or remainder of it ) */
	void * q;     /* end of new block of memory */
	void * nextp; /* proposed next value of p */

	/* guarantee an aligned block of size 2**i by getting twice that */
	i = i + 1;
	twotothei = 1 << i;

	/* guarantee minimum size */
	while (twotothei < sizeof( void * )) {
		i = i + 1;
		twotothei = twotothei << 1;
	}

	/* get a block of memory from p to just before q */
	p = sbrk( twotothei );
	q = sbrk( 0 );

	/* it's possible that allocation will fail */
	if ((p == q) || (((intptr_t)p) == -1) || p == NULL ) return;

	/* at this point, the original value of i is irrelevant */

	/* First chop block into successively larger free blocks */
	i = 0;
	twotothei = 1;
	for (;;) { /* exit by break */
		/* find the largest block compatible with the address */
		while ((((intptr_t)p) & (twotothei)) == 0) {
			i = i + 1;
			twotothei = twotothei << 1;
		}
		/* now, p is xxxx10000 and twotothei is 000010000 */

		nextp = (void *)(((intptr_t)p) + twotothei);
		if (nextp >= q) break;
		
		/* chop off a chip and free it if big enough */
		if (twotothei >= sizeof( void * )) buddyfree( p, i );
		p = nextp;
	}

	/* Second chop what's left into successively smaller free blocks */
	do {
		/* the proposed nextp might be too large */
		while (nextp > q) {
			i = i - 1;
			twotothei = twotothei >> 1;
			nextp = (void *)(((intptr_t)p) + twotothei);
		}

		/* chop off a chip and free it if big enough */
		if (twotothei >= sizeof( void * )) buddyfree( p, i );

		/* walk on to the next step */
		p = nextp;
		i = i - 1;
		twotothei = twotothei >> 1;
		nextp = (void *)(((intptr_t)p) + twotothei);

	} while (p < q);
}