#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!
*/
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
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.
#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
*/
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
Exercise 8-7. malloc() accepts a size request without checking its plausibility; free() believes that the block it is asked to free contains a valid size field. Improve these routines so they take more pains with error checking.
#include <stdio.h> // for printf(), fprintf(), stderr, NULL
#include <string.h> // for strcpy()
#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 *); // put block in free list
int main()
{
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;
}
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;
}
/*
gcc malloc2.c -o malloc2
./malloc2
Hello!
Hello, world!
*/
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
#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 <limits.h> // for ULONG_MAX
#include <time.h> // for time_t, time()
#include <sys/sysinfo.h> // for sysconf(), get_avphys_pages()
#include <unistd.h> // for sbrk(), _SC_PAGESIZE
//#define _XOPEN_SOURCE_EXTENDED 1 // for sbrk()
#define SIZE 100 // array size
#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
// 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()
{
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;
}
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);
}
// allocate space for an array:
void * CAlloc(long unsigned nunits, long unsigned size)
{
long unsigned nbytes = nunits * size;
if (nbytes == 0) // nbytes >= 0
{return NULL;} // calloc(0,0) is legal
// else
if (nbytes > maxmem())
{
fprintf(stderr, "CAlloc(): not enough memory available\n");
return NULL;
}
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)
{ // 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;
}
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 && 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 calloc2.c -o calloc2
./calloc2
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
*/
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
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.
#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!
*/