a very simple malloc question
[ ... ]
Quote:
> Does anyone know a link to, or can offer a basic implementation of
> malloc? I'd really like to learn from this experience.
Here's a very simple one I wrote years ago. It is intended strictly
for demonstration, not serious use, and lacks a number of things a
"real" malloc needs.
First of all, to keep things portable, this requires that you
initialize it with the address of a block of memory from which it
will do allocations. A real version of malloc will normally allocate
memory from the OS using some non-standard function (e.g. sbrk,
HeapAlloc).
Second, this makes no attempt at coalescing freed blocks. For real
use, that's a crucial addition. The way things are right now, your
heap is likely to be fragmented beyond usability in a VERY short time
(it makes no real attempt at preventing
Finally (again for portability) this makes no attempt at ensuring
that the blocks it returns are aligned for any possible use -- in
fact, on hardware that has alignment requirements, you can almost
depend upon it to do bad things. Fixing this in a non-portable
fashion borders on trivial, but finding alignment requirements
portably is a whole different story.
#include <stddef.h>
typedef struct node {
size_t size;
struct node *next;
Quote:
} node;
node *free_list;
static void *split_end(node *block, size_t new_size) {
size_t difference = block->size - new_size;
node *temp = (node *)((char *)block + difference);
temp->size = new_size;
block->size = difference;
return (void *)((size_t *)temp+1);
Quote:
}
static void *split_begin(node *block, size_t new_size) {
size_t difference = block->size-new_size;
node *temp = (node *)((char *)block + new_size);
temp->size = difference;
temp->next = free_list;
free_list = temp;
return block;
Quote:
}
void b_init(void *block, size_t block_size) {
((node *)block)->size = block_size - sizeof(node);
((node *)block)->next = NULL;
free_list = block;
Quote:
}
void b_free(void *block) {
node *b = (node *)((size_t *)block -1);
b->next = free_list;
free_list = b;
Quote:
}
void *b_malloc(size_t size) {
node *temp, **ptr;
size_t larger = size+sizeof(node);
size += sizeof(size_t);
for ( ptr = &free_list;
NULL != ptr;
ptr = &((*ptr)->next))
{
if ((*ptr)->size >= size) {
if ( (*ptr)->size <= larger) {
temp = (*ptr);
(*ptr) = (*ptr)->next;
return (void *)((size_t *)temp + 1);
}
else
return split_end(*ptr, size);
}
}
return NULL;
Quote:
}
void *b_realloc(void *block, size_t new_size) {
node *b = (node *)((char *)block - sizeof(size_t));
char *temp;
size_t i, size;
if ( new_size == 0) {
b_free(block);
return NULL;
}
new_size += sizeof(size_t);
size = b->size;
if ( new_size <size)
size = new_size;
size -= sizeof(size_t);
if ( b->size >= new_size+sizeof(node *) )
return split_begin(b, new_size);
if ( b->size >= new_size)
return b;
temp = b_malloc(new_size);
if ( NULL == temp)
return NULL;
for ( i=0; i<size;i++)
temp[i] = ((char *)block)[i];
b_free(block);
return temp;
Quote:
}
#ifdef TEST
#define num 10
int main(void) {
int i;
char block[4096];
char *temp[num];
char *big;
b_init(block, sizeof(block));
big = b_malloc(100);
for (i=0; i<num; i++)
temp[i] = b_malloc(10);
for (i=0; i<num; i++)
b_free(temp[i]);
b_realloc(big, 200);
b_realloc(big, 10);
b_realloc(big, 0);
return 0;
Quote:
}
#endif
--
Later,
Jerry.
The universe is a figment of its own imagination.
--
