#include <unistd.h>
#include <stdio.h>
#include "malloc.h"

#define NALLOC		128
#define MAX_BYTES	(size_t) 8192

typedef long long Align;

typedef union header {
	struct {
		union header *ptr;
		size_t size;
	} s;

	Align x;
} Header;

/* see my_free
 * static size_t maxalloc; */
static Header base;
static Header *freep = NULL;

/* static Header *my_morecore(size_t nunits); */

void *my_calloc(size_t n ,size_t size)
{
	char *p, *temp;
	size_t nb;

	nb = n * size;
	if ((p = temp = my_malloc(nb)) == NULL)
		while (nb-- > 0)
			*temp++ = '\0';

	return p;
}

void *my_malloc(size_t nbytes)
{
	Header *prevp, *p;
	size_t nunits;

	if (nbytes > MAX_BYTES) {
		fprintf(stderr, "alloc:can't allocate more than %lu bytes\n",
		      MAX_BYTES);
		return NULL;
	}

	if ((prevp = freep) == NULL) {
		base.s.ptr = prevp = freep = &base;
		base.s.size = 0;
	}

	nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;
	for (p = freep->s.ptr; ; prevp = p, p = p->s.ptr) {
		if (p->s.size >= nunits) {
			if (p->s.size == nunits) {
				prevp->s.ptr = p->s.ptr;
			} else {
				p->s.size -= nunits;
				p += p->s.size;
				p->s.size = nunits;
			}

			freep = prevp;
			return (void *)(p + 1);
		}

		if (p == freep)
			/* if ((p = my_morecore(nunits)) == NULL) \
			* we fully rely on mem from stdlib malloc */
			return NULL;
	}

	return NULL;
}

/* see my_free
 * static Header *my_morecore(size_t nunits)
 *{
 *	Header *p;
 *
 *	if (nunits < NALLOC)
 *		nunits = NALLOC;
 *
 *	if ((p = sbrk(nunits * sizeof(Header))) == (Header *) -1)
 *		return NULL;
 *
 *	p->s.size = nunits;
 *	if ((p->s.size = nunits) > maxalloc)
 *	 	maxalloc = nunits;
 *
 *	my_free (p + 1);
 *	return freep;
 * } */

void my_free(void *ap)
{
	Header *bp, *p;

	bp = (Header *)ap - 1;

	if (freep == NULL) {
		base.s.ptr = freep = &base;
		base.s.size = 0;
	}

	/* we accept random values from bfree 
	 * if (bp->s.size == 0 || bp->s.size > maxalloc) {
	 *	fprintf(stderr, "alloc: can't free %lu units\n", bp->s.size);
	 *	return;
	 * } */

	for (p = freep; !(bp > p && bp < p->s.ptr) ; p = p->s.ptr)
		if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
			break;

	if (bp + bp->s.size == p->s.ptr) {
		bp->s.size += p->s.ptr->s.size;
		bp->s.ptr = p->s.ptr->s.ptr;
	} else {
		bp->s.ptr = p->s.ptr;
	}

	if (p + p->s.size == bp) {
		p->s.size += bp->s.size;
		p->s.ptr = bp->s.ptr;
	} else {
		p->s.ptr = bp;
	}

	freep = p;
}

size_t bfree(void *ap, size_t n)
{
	Header *p;

	if (n < sizeof(Header) * 2) {
		fprintf(stderr, "bfree: can't free %lu bytes\n", n);
		return 0;
	}

	p = (Header *) ap;
	p->s.size = (n / sizeof(Header));
	my_free(p + 1);

	return p->s.size;
}