From 2bbb384783f667226e117e62992779498bc7e5b8 Mon Sep 17 00:00:00 2001 From: zlg Date: Sun, 23 Jan 2022 17:59:56 -0800 Subject: 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. --- ch8/8-06_calloc.c | 136 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 136 insertions(+) create mode 100644 ch8/8-06_calloc.c 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 +#include + +/* 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; +} -- cgit v1.2.3-54-g00ecf 143&follow=1'>vgstash: let backlog filter ignore unbeatable gameszlg1-1/+1 2018-10-18Bump to 0.3beta2 for PyPIzlg1-3/+3 2018-10-18vgstash.DB.__init__: fix error output formattingzlg1-1/+1 2018-10-18README: fix inline <code> formattingzlg1-3/+4 2018-10-18cli: show msg if game to be deleted is not in DBzlg2-2/+12 2018-10-18README: expand on usage, cover shell quotingzlg1-7/+99 2018-10-18cli: Tell the user when a game lacks noteszlg2-3/+15 2018-10-18Catch when an invalid list filter is passedzlg4-3/+24 2018-10-12cli: Add zero-game import/export messageszlg2-11/+18 2018-10-10Bump to 0.3beta1 for PyPIzlg1-1/+1 2018-10-10Move tests and data to dedicated directoryzlg7-10/+26 2018-10-10cli: Add "export" commandzlg2-5/+54 2018-10-10cli: Add "import" commandzlg5-1/+76 2018-10-09Bump to 0.3alpha6 for PyPIzlg1-1/+1 2018-10-09cli: Add "notes" commandzlg2-4/+74 2018-10-09update_game: ensure notes are also savedzlg1-2/+2 2018-10-09cli: add 'update' commandzlg3-20/+92 2018-10-06cli: Add "delete" commandzlg2-0/+19 2018-10-06Remove ID field from DBzlg3-38/+46 2018-10-06cli: change "Status" heading to "Progress"zlg2-36/+40 2018-09-29Bump to 0.3alpha5 for PyPIzlg1-1/+1 2018-09-29cli: Add pretty printing to 'list' commandzlg3-17/+107 2018-09-08setup.py: Bump to alpha4 for PyPIzlg1-1/+1 2018-09-08cli: add '--raw' option to list commandzlg2-9/+45 2018-09-08Add remaining filters to vgstash packagezlg1-2/+11 2018-09-04Update LICENSE to match setup.pyzlg1-80/+67 2018-09-03Branch off from master with pytest, tox, clickzlg16-778/+779 2018-03-18Flesh out filter types and ownership statuszlg3-82/+144 2018-03-18README.mdown: break line correctlyzlg1-1/+1 2018-03-18add 'playlog' list filterzlg2-2/+9 2018-03-13Update helpers a bitzlg1-2/+9 2018-03-13Make VGSTASH_DB_LOCATION point to a filezlg2-21/+20 2016-11-18Remove settings from helpers.shZe Libertine Gamer1-5/+0 2016-11-15Correct phrasing in README.Ze Libertine Gamer1-4/+4 2016-11-13DerpZe Libertine Gamer1-0/+1 2016-11-03Improve error handling in shell scriptsZe Libertine Gamer4-3/+23 2016-10-24Correct run_again, add recursionZe Libertine Gamer1-0/+4 2016-10-21Add quotes to correct behavior for arglistZe Libertine Gamer1-1/+1 2016-10-14updater.sh: add recursion, error handlingZe Libertine Gamer1-43/+101 2016-10-14Correct pipe-handling behaviorZe Libertine Gamer1-1/+9 2016-10-12Clarify a method to move between platformsZe Libertine Gamer1-2/+5