diff options
| -rw-r--r-- | ch8/8-08_bfree.c | 200 |
1 files changed, 200 insertions, 0 deletions
diff --git a/ch8/8-08_bfree.c b/ch8/8-08_bfree.c new file mode 100644 index 0000000..2414d25 --- /dev/null +++ b/ch8/8-08_bfree.c @@ -0,0 +1,200 @@ +#include <stdio.h> +#include <stdlib.h> +#include <errno.h> +#include <string.h> +#include <limits.h> +#include <unistd.h> + +/* The C Programming Language: 2nd Edition + * + * Exercise 8-8: 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. + * + * Notes: It's unclear exactly what the goal is with bfree. It seems like it's + * a way to add space into the heap for a data structure before copying it to + * memory. I've done what I could to indicate things are being added to the + * free list, but the real world applications of this are not clear to me. + */ + +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; + } + if (nbytes < (sizeof (Header) * 2)) { + nbytes = sizeof (Header) * 2; + } + printf("Requesting %d bytes.\n", nbytes); + Header *p, *prevp; + unsigned nunits; + 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; + 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); + } +} + +void bfree(void *p, unsigned n) { + if (p == NULL) { + errno = EINVAL; + return; + } + if (n > (UINT_MAX - sizeof (Header)) || + n == 0) { + errno = EINVAL; + return; + } + if (n < sizeof (Header) * 2) { + printf("Buffer not large enough to be worth putting in the heap.\n"); + return; + } + if (freep == NULL) { + base.s.ptr = freep = &base; + base.s.size = 0; + } + Header *hp = (Header *) p; + hp->s.size = (n / sizeof(Header)) - 1; + zfree((void *)(hp + 1)); +} + +int main(int argc, char *argv[]) { + char foo[sizeof (Header) * 3] = "Hello world!"; + char *bar = zcalloc(40, sizeof (char)); + strcpy(bar, foo); + printf("%s\n", bar); + bfree(foo, sizeof (Header) * 3); + if (errno == EINVAL) { + printf("Bad juju.\n"); + exit(1); + } + + bfree(bar, 40); + if (errno == EINVAL) { + printf("Bad juju.\n"); + exit(1); + } + + 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); + } + return 0; +} |