/* mp6skel.c -- skeleton of mp6 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 */
		/* allocate a larger block */
		p = buddyalloc( i + 1 );

		/* then split it */
		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 */

	--- write this code ---
}