#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;

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)
				return NULL;
	}

	return NULL;
}

static Header *my_morecore(size_t nunits)
{
	Header *p;

	if (nunits < NALLOC)
		nunits = NALLOC;

	if ((p = sbrk(nunits * sizeof(Header))) == (Header *) -1)
		return NULL;

	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 (bp->s.size == 0 || bp->s.size > maxalloc) {
		fprintf(stderr, "alloc: can't free %lu units", 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;
}