Exercise 8-6 (calloc - Dynamic array allocator)

Chapter_8     Exercise_8-5     malloc

Exercise_8-7

---

---

Exercise 8-6     K&R, p. 189

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.

calloc.c     K&R, p. 186-189         download

#include <stdio.h> // for printf(), fprintf(), stderr, NULL
#include <string.h> // for memset()
#include <stdlib.h> // for srand(), rand()
// stdlib.h declares malloc(), calloc(), free()
#include <time.h> // for time_t, time()
#include <unistd.h> // for sbrk()

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

#define SIZE 100 // array size

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

// allocate space for an array:
void * CAlloc(long unsigned nunits, long unsigned size);
// general-purpose storage allocator:
void * MAlloc(long unsigned nbytes);
void Free (void *); // put block in free list

int main() // Dynamic or run-time array allocation
{
int i;
int *p = (int *) CAlloc(10, sizeof(int));

if (p == NULL)
{
fprintf(stderr, "Could not allocate space\n");
return 1; // end program, signalling error
}

time_t t;

srand((unsigned) time(&t)); // seed rand()

for (i = 0; i < 10; i++)
{p[i] = rand() % 50;}

for (i = 0; i < 9; i++)
{printf("%d, ", p[i]);}
printf("%d\n\n", p[i]);

Free(p);

p = (int *) CAlloc(SIZE, sizeof(int));

if (p == NULL)
{
fprintf(stderr, "Could not allocate space\n");
return 1; // end program, signalling error
}

for (i = 0; i < SIZE; i++)
{p[i] = rand() % SIZE;}

for (i = 0; i < SIZE; i++)
{printf("%d%s", p[i], (i % 10 == 9) ? "\n" : ", ");}

Free(p);

return 0;
}

// allocate space for an array:
void * CAlloc(long unsigned nunits, long unsigned size)
{
long unsigned nbytes = nunits * size;

void *p = MAlloc(nbytes);

if (p == NULL)
{return NULL;} // return p
// else
memset(p, 0, nbytes); // initialize to 0

return p;
}

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 && 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 calloc.c -o calloc
./calloc
40, 38, 39, 42, 48, 5, 25, 46, 16, 35

24, 97, 92, 69, 14, 91, 5, 22, 21, 35
80, 67, 69, 46, 74, 54, 73, 15, 94, 76
63, 35, 66, 5, 79, 64, 60, 54, 63, 26
39, 39, 76, 32, 9, 90, 75, 14, 64, 48
1, 97, 15, 70, 43, 90, 76, 68, 57, 22
44, 21, 9, 62, 26, 88, 27, 38, 43, 42
17, 34, 81, 45, 66, 90, 87, 93, 56, 51
41, 57, 48, 57, 79, 43, 99, 55, 12, 56
30, 8, 29, 39, 71, 7, 28, 50, 98, 71
92, 15, 5, 25, 60, 24, 16, 47, 17, 24
*/

---

---

Chapter_8     Exercise_8-5     malloc

BACK_TO_TOP

Exercise_8-7