Exercise 8.08

Page 189

Write a routine bfree(p,n) that will free an arbitrary block p of n characters into the free list maintained by malloc and free. By using bfree, a user can add a static or external array to the free list at any time.

/* I found this SO answer very helpful in understanding some of the routines presented:
 * https://stackoverflow.com/questions/13159564/explain-this-implementation-of-malloc-from-the-kr-book/36512105#36512105 */

#include <unistd.h>

typedef long Align;

union header {
	struct {
		union header *ptr;
		unsigned size;
	} s;
	Align _;
};

typedef union header Header;

static Header base;
static Header *freep = NULL;
static Header *knrmorecore(unsigned nu);

void *knrmalloc(unsigned nbytes)
{
	Header *currp, *prevp;
	Header *morecore(unsigned);
	unsigned nunits;

	if (nbytes == 0) {
		return NULL;
	}

	nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;

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

	for (currp = prevp->s.ptr;; prevp = currp, currp = currp->s.ptr) {
		if (currp->s.size >= nunits) {
			if (currp->s.size == nunits) {
				prevp->s.ptr = currp->s.ptr;
			} else { /* allocate tail end */
				currp->s.size -= nunits;
				currp += currp->s.size;
				currp->s.size = nunits;
			}
			freep = prevp;
			return (void *)(currp + 1);
		}
		if (currp == freep) {
			if ((currp = knrmorecore(nunits)) == NULL) {
				return NULL;
			}
		}
	}
}

#define NALLOC 1024
void knrfree(void *ap);
static Header *knrmorecore(unsigned nu)
{
	char *cp;
	Header *up;

	if (nu < NALLOC) {
		nu = NALLOC;
	}
	cp = sbrk(nu * sizeof(Header));
	if (cp == (char *)-1) {
		return NULL;
	}
	up = (Header *)cp;
	up->s.size = nu;
	knrfree((void *)(up + 1));
	return freep;
}

void knrfree(void *ap)
{
	Header *insertp, *currp;

	if (ap == NULL) {
		return;
	}

	insertp = (Header *)ap - 1;

	if (insertp->s.size == 0) {
		return;
	}

	for (currp = freep; !(insertp > currp && insertp < currp->s.ptr);
	     currp = currp->s.ptr) {
		if (currp >= currp->s.ptr &&
		    (insertp > currp || insertp < currp->s.ptr)) {
			break;
		}
	}

	if (insertp + insertp->s.size == currp->s.ptr) { /* join to upper nbr */
		insertp->s.size += currp->s.ptr->s.size;
		insertp->s.ptr = currp->s.ptr->s.ptr;
	} else {
		insertp->s.ptr = currp->s.ptr;
	}

	if (currp + currp->s.size == insertp) {
		currp->s.size += insertp->s.size;
		currp->s.ptr = insertp->s.ptr;
	} else {
		currp->s.ptr = insertp;
	}
	freep = currp;
}

#include <string.h>
void *mycalloc(int n, size_t size)
{
	void *res = knrmalloc(n * size);
	if (res != NULL) {
		memset(res, 0, n * size);
	}
	return res;
}

void *bfree(void *p, size_t n)
{
	if (n <= sizeof(Header)) {
		return NULL;
	}

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

	knrfree(p + 1);

	return p + 1;
}

#include <stdio.h>
#include <stdlib.h>
int main()
{
	char str[] =
		"sizeof(Header) appears to be 16 bytes on my system (makes sense, as it is the size of a long)"
		"so this string needs to be at least 17 characters long else there isn't enough space for the"
		"block header.";

	void *res = bfree(str, sizeof(str));

	if (res == NULL) {
		puts("error: bfree failed");
		exit(1);
	}

	puts("success");
	exit(0);
}