aboutsummaryrefslogtreecommitdiff
path: root/ch8
diff options
context:
space:
mode:
authorzlg <zlg@zlg.space>2022-01-23 17:59:56 -0800
committerzlg <zlg@zlg.space>2022-01-23 17:59:56 -0800
commit2bbb384783f667226e117e62992779498bc7e5b8 (patch)
treed13a69cd36de9c22fd54435b4964002f6ba50f53 /ch8
parentSolve Exercise 8-05: fsize extended (diff)
downloadknr-2bbb384783f667226e117e62992779498bc7e5b8.tar.gz
knr-2bbb384783f667226e117e62992779498bc7e5b8.tar.bz2
knr-2bbb384783f667226e117e62992779498bc7e5b8.tar.xz
knr-2bbb384783f667226e117e62992779498bc7e5b8.zip
Solve Exercise 8-6: calloc()
I chose to implement calloc() by calling malloc. This exercise went well, but I found it difficult to verify the contents of the headers and buffers within memory. Valgrind showed the correct number of bytes allocated, and a memory dump pointed to a good result, but research was not conclusive.
Diffstat (limited to 'ch8')
-rw-r--r--ch8/8-06_calloc.c136
1 files changed, 136 insertions, 0 deletions
diff --git a/ch8/8-06_calloc.c b/ch8/8-06_calloc.c
new file mode 100644
index 0000000..34f18ab
--- /dev/null
+++ b/ch8/8-06_calloc.c
@@ -0,0 +1,136 @@
+#include <stdio.h>
+#include <string.h>
+
+/* The C Programming Language: 2nd Edition
+ *
+ * Exercise 8-6: The standard library function calloc(n, size) returns a
+ * pointer to `n` objects of size `size`, with the storage initialized to zero.
+ * Write `calloc`, by calling malloc or by modifying it.
+ *
+ * Notes: Replacing the standard library functions here can be problematic if
+ * you also intend to use the stdlib to output text or use other functions that
+ * interact with *alloc, morecore, and free.
+ *
+ * I prefixed the functions with 'z' so I could hack on them *and* use the
+ * standard library as needed.
+ *
+ * Ideally, one would use a debugger or other tool to show that memory is
+ * assigned in the free list, and verify the size of the block of memory. We'll
+ * revisit this when I'm good at debuggers. :)
+ */
+
+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) {
+ /* TODO: get the size field updated correctly */
+ Header *p, *prevp;
+ unsigned nunits;
+ nunits = (nbytes + sizeof (Header) - 1) / sizeof (Header) + 1;
+
+ 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) {
+ 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 (cp == (char*) -1) {
+ return NULL;
+ }
+ up = (Header *) cp;
+ up->s.size = nu;
+ zfree((void *)(up+1));
+ return freep;
+}
+
+void zfree(void *ap) {
+ Header *bp, *p;
+ bp = (Header *)ap - 1;
+ 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;
+}
+
+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 there!";
+ char *buf = zcalloc(strlen(foo) + 1, sizeof (char));
+ strncpy(buf, foo, 5);
+ printf("%s\n", buf);
+ printf("buf is %d long\n", strlen(buf));
+ printf("foo is %d long\n", strlen(foo));
+ printf("the header says buf's max size is %d\n", freep->s.size);
+ return 0;
+}