Exercise 8-8 (bfree)

Chapter_8     Exercise_8-7 ch8-Exercises     Advanced_Linux_Prog_blog     C_in_C++





Exercise 8-8     K&R, p. 189


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.




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


#include <stdio.h> // for printf(), fprintf(), stderr, NULL
#include <string.h> // for strcpy(), strlen()
#include <limits.h> // for ULONG_MAX
#include <sys/sysinfo.h> // for sysconf(), get_avphys_pages()
#include <unistd.h> // for sbrk(), _SC_PAGESIZE
// unistd.h includes stdlib.h, which contains malloc(), free()

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

#define MAXLEN 100 // max length

#define min(A,B) (((A) < (B)) ? (A) : (B))

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

long unsigned maxmem(); // max memory that can be allocated

// general-purpose storage allocator
void * MAlloc(long unsigned nbytes);
void Free (void *p); // put block p in free list
// add an arbitrary block p of n characters into the free list:
void bfree (void *p, long unsigned n);

int main()
{
int n;
char *s = "Hello!";
n = strlen(s);
bfree(s, n);
printf("%s\n", s);
s = 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);
n = ((10+sizeof(Header)-1)/sizeof(Header) + 1) * sizeof(Header);
bfree(s, n);
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);
n = ((MAXLEN+sizeof(Header)-1)/sizeof(Header) + 1) * sizeof(Header);
bfree(s, n);

return 0;
}

long unsigned maxmem() // max memory that can be allocated
{ // avm - available memory
long unsigned avm = get_avphys_pages() * sysconf(_SC_PAGESIZE);
long unsigned min = min(avm, ULONG_MAX);
// printf("maxmem: %lu bytes\n", min-sizeof(Header));
return min-sizeof(Header);
}

Header * MoreCore(long unsigned);

// general-purpose storage allocator
void * MAlloc(long unsigned nbytes)
{ // nbytes >= 0
if (nbytes == 0)
{return NULL;} // malloc(0) is legal
// else
if (nbytes > maxmem())
{
fprintf(stderr, "MAlloc(): not enough memory available\n");
return NULL;
}

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
{
if (nu * sizeof(Header) > maxmem())
{
fprintf(stderr, "MoreCore(): not enough memory available\n");
return NULL;
}

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; // freep->s.ptr has the allocated space
}

void Free (void *ap) // put block ap in free list
{ // we assume ap was allocated with MAlloc()
if (ap == NULL) // free(NULL) does nothing
{return;} // like free() from stdlib.h

Header *bp, *p;

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

if (bp->s.size == 0)
{return;} // nothing to free
if (bp->s.size * sizeof(Header) > maxmem())
{
fprintf(stderr, "Free(): too much memory");
return;
}

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

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;
}

void bfree (void *p, long unsigned n)
{ // add an arbitrary block p of n characters into the free list
if (p == NULL) // free(NULL) does nothing
{return;} // like free() from stdlib.h
if (n < sizeof(Header) * 2)
{ // enough space for header and another unit of storage
fprintf(stderr, "Freed memory must be at least %lu bytes, ",
sizeof(Header) * 2);
fprintf(stderr, "n = %lu\n", n);
return;
}
if (n > maxmem())
{
fprintf(stderr, "bfree(): too much memory");
return;
}

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

Header *bp = (Header *)p;
bp->s.size = n / sizeof(Header);
Free((void *)(bp + 1));
}

/*
gcc bfree.c -o bfree
./bfree
Freed memory must be at least 32 bytes, n = 6
Hello!
Hello!
Hello, world!
*/





Note:  See also GitHub-kr_(8.8) and clc-wiki-kr_(8.8) solutions.







Chapter_8     Exercise_8-7 BACK_TO_TOP ch8-Exercises     ALP_blog     C_in_C++



Comments

Post a Comment

Popular posts from this blog

Contents

Programming_Languages_blog     C_Prog_blogs Chapter_1     Advanced_Linux_Prog     C_in_C++ NAVIGATION     CHAPTERS     CONTENTS     EXERCISES     INDEX     ABOUT     CONTACT Chapter_1  (Introduction) Hello     Exercise_1-1     Exercise_1-2     quotes     Temperature_Programs     Truncate     Exercise_1-3     Exercise_1-4     for()_variant     Exercise_1-5     #define_directive     copy     Exercise_1-6     Exercise_1-7     copyEOF     count     Exercise_1-8     Exercise_1-9 ...
Read more

Blogger Page Margins in Contempo

NAVIGATION     CHAPTERS     CONTENTS     EXERCISES     INDEX     ABOUT     CONTACT Navigate Blogger left panel   →   Theme   →   CUSTOMIZE drop-down menu   →   Edit HTML CONTENTS:     Left_Margin     Right_Margin     Page_Content_Fills_the_Screen Left Margin No Left Margin .centered-bottom,.centered-top-container,.centered-top-placeholder{ padding:0 0px } Original CSS .centered-bottom,.centered-top-container,.centered-top-placeholder{ padding:0 16px } Right Margin No Right Margin (No Vertical Ads on blog) .vertical-ad-container { float: right; margin-right: 0px; width: 0px; } .page_body.has-vertical-ads .centered .centered-bottom { display: inline-block; width: calc(100% - 0px); } Original CSS .vertical-ad-contain...
Read more