ch8-malloc (Dynamic memory allocator)

Chapter_8     Exercise_8-5

Exercise_8-6

---

---

malloc.c     K&R, p. 186-188         download

#include <stdio.h> // for printf(), fprintf(), stderr, NULL
#include <string.h> // for strcpy()
#include <unistd.h> // for sbrk()
// unistd.h includes stdlib.h, which contains malloc(), free()

//#define _XOPEN_SOURCE_EXTENDED 1 // for sbrk()

#define MAXLEN 100 // max length

typedef long Align; // for alignment to 'long' boundaries

union header // block header:
{
struct
{
union header *ptr; // next block on free list
unsigned size; // size of this block
} s;
Align x; // force alignment pf blocks
};

typedef union header Header;

static Header base; // empty list to get started
static Header *freep = NULL; // start of free list

// general-purpose storage allocator
void * MAlloc(long unsigned nbytes);
void Free (void *); // put block in free list

int main() // dynamic or run-time memory allocation
{
char *s = (char *) MAlloc(10);
if (s == NULL)
{
fprintf(stderr, "Could not allocate space\n");
return 1; // end program, signalling error
}
strcpy(s, "Hello!");
printf("%s\n", s);

Free(s);

s = (char *) MAlloc(MAXLEN);
if (s == NULL)
{
fprintf(stderr, "Could not allocate space\n");
return 1; // end program, signalling error
}
strcpy(s, "Hello, world!");
printf("%s\n", s);

Free(s);

return 0;
}

Header * MoreCore(long unsigned);

// general-purpose storage allocator
void * MAlloc(long unsigned nbytes)
{
Header *p, *prevp;
long unsigned nunits;
// no of Header units to cover nbytes plus header (at least 1)
nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1;

if ((prevp = freep) == NULL) // no free list yet
{ // base is the first node in the circular linked list
base.s.ptr = freep = prevp = &base;
base.s.size = 0; // no space allocated yet
}

for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr)
{
if (p->s.size >= nunits) // big enough
{
if (p->s.size == nunits) // exactly
{prevp->s.ptr = p->s.ptr;} // p removed from free list
else // allocate tail end
{
p->s.size -= nunits;
p += p->s.size;
p->s.size = nunits;
}
freep = prevp; // next search begins with freep
return (void *)(p+1); // after header
}
if (p == freep) // wrapped around free list
{
if ((p = MoreCore(nunits)) == NULL)
{return NULL;} // none left
// else p->s.ptr has the newly allocated space
}
// here prevp = p, p = p->s.ptr
}
}

#define NALLOC 1024 // minimum no of units to request

// ask system for more memory
Header * MoreCore(long unsigned nu) // no of units
{
void *vp;
Header *up;

if (nu < NALLOC) // allocate at least NALLOC units
{nu = NALLOC;}

vp = sbrk(nu * sizeof(Header)); // allocate space

if (vp == (void *) -1) // no space at all
{return NULL;}

up = (Header *) vp;
up->s.size = nu; // size includes header
// add newly allocated space to the free list:
Free((void *)(up+1)); // +1 - after header

return freep;
}

void Free (void *ap) // put block ap in free list
{ // we assume ap was allocated with MAlloc()
Header *bp, *p;

bp = (Header *)ap - 1; // point to block header

for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
{ // p >= p->s.ptr at the end of list
if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
{break;} // freed block at start or end of arena
}
// here bp > p and/or bp < p->s.ptr, p < p->s.ptr or p >= p->s.ptr
if (bp + bp->s.size == p->s.ptr) // join to upper neighbor
{
bp->s.size += p->s.ptr->s.size; // add size of p, including header
bp->s.ptr = p->s.ptr->s.ptr; // add bp, remove p->s.ptr
}
else {bp->s.ptr = p->s.ptr;} // add bp in between p and p->s.ptr
// bp can join both neighbors, one, or none
if (p + p->s.size == bp) // join to lower neighbor
{
p->s.size += bp->s.size;
p->s.ptr = bp->s.ptr; // absorb bp into the list
}
else {p->s.ptr = bp;} // bp is in between p and p->s.ptr

freep = p;
}

/*
gcc malloc.c -o malloc
./malloc
Hello!
Hello, world!
*/

---

---

Chapter_8     Exercise_8-5

BACK_TO_TOP

Exercise_8-6