#include <stdio.h>
#include <errno.h>
#include <string.h>
#include <limits.h>

/* The C Programming Language: 2nd Edition
 *
 * Exercise 8-7: `malloc` accepts a size request without checking its
 * plausibility; `free` believes that the block it is asked to free contains a
 * valid size field. Improve these routines so that they take more pains with
 * error checking.
 *
 * Notes: There isn't much to check for, since a lot of boundary checking is
 * already done. The primary things to watch out for in functions that accept
 * pointers is the existence of a NULL pointer, which has undefined behavior
 * when dereferenced or otherwise worked with. We also check for the size value
 * of a header not exceeding the system's integer limits. Fairly simple error
 * checking, but it works.
 */

typedef long Align;

union header {
	struct {
		union header *ptr;
		unsigned size;
	} s;
	/* unused, just for alignment */
	Align x;
} hdr;

typedef union header Header;

static Header base;
static Header *freep = NULL;
static Header *zmorecore(unsigned);
void *zmalloc(unsigned);
void zfree(void *);

void *zmalloc(unsigned nbytes) {
	if (nbytes == 0 || nbytes > (UINT_MAX - sizeof (Header))) {
		/* cannot ask for zero memory */
		errno = EINVAL;
		return NULL;
	}
	printf("Requesting %d bytes.\n", nbytes);
	Header *p, *prevp;
	unsigned nunits;
	/* Set the number to something more sane */
	nunits = (nbytes + sizeof (Header));
	/* is the K&R wrong here...? */
	/* nunits = (nbytes + sizeof (Header) - 1) / sizeof (Header) + 1; */
	printf("%d units need allocated.\n", nunits);

	if ((prevp = freep) == NULL) {
		base.s.ptr = freep = prevp = &base;
		base.s.size = 0;
	}
	for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
		/* larger than requested units */
		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 = zmorecore(nunits)) == NULL) {
				errno = ENOMEM;
				return NULL;
			}
		}
	}
}

#define NALLOC 1024

static Header *zmorecore(unsigned nu) {
	char *cp, *sbrk(int);
	Header *up;
	if (nu < NALLOC) {
		nu = NALLOC;
	}
	cp = sbrk(nu * sizeof (Header));
	if (errno == ENOMEM) {
		return NULL;
	}
	up = (Header *) cp;
	up->s.size = nu;
	zfree((void *)(up+1));
	return freep;
}

void zfree(void *ap) {
	if (ap == NULL) {
		printf("Cannot free null pointer.\n");
		errno = EINVAL;
		return;
	}
	Header *bp, *p;
	bp = (Header *)ap - 1;
	if (bp->s.size == 0) {
		printf("Cannot free block of size 0.\n");
		errno = EINVAL;
		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 < (UINT_MAX - p->s.ptr->s.size)) {
		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 < (UINT_MAX - bp->s.size)) {
		p->s.size += bp->s.size;
		p->s.ptr = bp->s.ptr;
	} else {
		p->s.ptr = bp;
	}
	freep = p;
}

void * zcalloc(int count, unsigned size) {
	char *p;
	int i;
	p = zmalloc(count * size);
	if (p != NULL) {
		for (i = 0; i < (count * size); i++) {
			p[i] = '\0';
		}
		return p;
	} else {
		return (int *)(-1);
	}
}

int main(int argc, char *argv[]) {
	char *foo = "Hello world.";
	char *baz = zcalloc(strlen(foo) + 1, sizeof (char));
	strncpy(baz, foo, strlen(foo)+1);
	printf("%s\n", baz);
	printf("baz is %d long\n", strlen(baz));
	printf("\nHEADER INFO:\n");
	Header *i;
	int c = 1;
	for (i = freep; ; i = i->s.ptr, c++) {
		if (c > 1 && i == &base ||
			i->s.ptr == i) {
			break;
		}
		printf("Header %d:\n", c);
		printf("Address: %p\n", i);
		printf("Size:    %d\n", i->s.size);
		printf("Next:    %p\n", i->s.ptr);
		printf("Data:\n%s\n", i+i->s.size+1);
	}
	printf("baz's address is %p\n", baz);
	zfree(baz);
	printf("\nLet's try allocating zero.\n");
	char *beep = zcalloc(0, sizeof (char));
	if (beep = (char *)(-1)) {
		printf("Nope.\n");
	}
	printf("\nLet's try allocating UINT_MAX + 1.\n");
	char *borp = zcalloc(UINT_MAX + 1, sizeof (char));
	if (borp = (char *)(-1)) {
		printf("Nope.\n");
	}
	return 0;
}