A89: memory management routines.
[Prev][Next][Index][Thread]
A89: memory management routines.
I just finished writing a memory manager in C, providing support for the
normal malloc(), calloc(), realloc(), and free(). Because it's entirely
in C, it should compile for any of the ti calculators. This doesn't
provide support for things like memory protection, however, because that
gets into protected mode programming, which the z80 doesn't have, and i
have no idea how to do on the m68k.
I'm sure something like this hasn't been written for the ti86, and I
have no idea about the ti89.
Anyways, i just thought these routines would be helpfull for all the
programmers out there who use C compilers
for their TI calculators.
Documentation is in the file header.
The thing is thouroghly commented, so it shouldn't be too hard to
understand.
--robin
/*
Machine Independant Memory Management
by Robin Kirkman
email: misty@drrobin.yi.org
These routines provide trust-based memory management for those of you writing
code out there for bare systems. I wrote them for my ti89, which doesn't have
these calls, to my knowledge. If it does, well, I'm sure these will be usefull
for all those z80 programmers, cause the TI calcs w/ z80's i am -certain- do
not have this stuff. Happy Days!
This is just the standard malloc(), calloc(), realloc(), and free().
The one exception is _initialize_malloc(void *ram_start), which you need to call.
ram_start is assumed to be the bottom of a memory block, which is assumed to be
without an upper bound. If you don't call _initialize_malloc before you use any
of these calls, then your system will crash very quickly.
Feel free to use these routines in anything you like. All I want in return is a
copy of whatever you use them in.
This code is copyrighted Nov 21, 1999, by Robin Kirkman.
Modify it all you want, but you best be leaving my name in here ;)
Funtion Prototypes:
void _initlialize_malloc(void *ramstart);
void _set_start_ram(void *ramstart);
void _free_all();
void *malloc(size_t size);
void *calloc(num_t num, size_t size);
void *realloc(void *ptr, size_t size);
void *free(void *ptr);
_initialize_ram(void *ramstart);
Sets the starting address and clears any allocations.
_set_start_ram(void *ramstart);
Sets the starting ram. If you use this while your program is running, you can
have different areas with different allocations.
_free_all();
Frees all allocated blocks.
malloc(size_t size);
Allocates size bytes, and returns a pointer to them. If size is zero, does nothing.
calloc(num_t num, size_t size);
Allocates num*size bytes, and returns a pointer to them. If size or num is zero, does nothing.
realloc(void *ptr, size_t size);
Reallocates the block at ptr to size bytes, and returns a new pointer. All data is retained.
If ptr is null, then realloc acts like malloc.
If size is null, then realloc acts like free.
free(void *ptr);
Frees an allocated block. If the block is not found, free() returns a -1. If found, returns null.
NOTE: This is different from ANSI! In ansi, free() is typed as void (not void pointer), and it
has 'undefined behavior' (read: crashes) when ptr isn't an allocated block.
*/
typedef struct __malloc_block {
void *data;
size_t size;
struct _malloc_block *next;
} _malloc_block;
/*
_malloc_block is an element in a linked list which the memory manager uses to keep
track of where the allocated blocks are.
*/
static void *_ramstart;
// Where is the bottom of our ram?
static void *_first_malloc_block=0;
// Where is the first _malloc_block structure? This is set by the initialization routine.
void _set_start_ram(void *ramstart) {
_ramstart=ramstart;
}
void _free_all(){
_first_malloc_block=0;
}
void _initialize_malloc(void *ramstart) {
_set_start_ram(ramstart);
_free_all();
}
void *_find_free_ram(size_t size) {
/*
_find_free_ram is used internally to find a block that is big enough for size.
This is used in malloc, first to find space for another malloc_block, then
to find space for the data.
*/
_malloc_block *mblock,*mtmp;
void *f_address=0; // Our address that we are finding
int found_block=0; // Have we found it yet?
int mtmp_search_ok;
mblock=_first_malloc_block; // Get the first block. Assume we have been initialized.
if(!mblock) // If we have no blocks, the first chunk must be the beginning of ram
return _ramstart;
while(!found_block) {
f_address=0;
while(mblock->next) { // Search for a chunk of ram that is big enough
if(mblock->data+mblock->size+size<(mblock->next)->data) {
f_address=mblock->data+mblock->size; // Use this chunk.
// We know that this chunk is acceptable because the linked list of _malloc_block's
// are organized ascending by the data element.
break;
}
mblock=mblock->next; // Check next malloc_block...
}
if(!f_address)
f_address=mblock->data+mblock->size; // Otherwise, use the end of the last chunk
// The above check sees if our chunk address interrupted by a data block.
// Now we need to see if it is interrupted by a malloc_block
mtmp=_first_malloc_block;
mtmp_search_ok=1;
while(mtmp && mtmp_search_ok) {
if(mtmp+sizeof(_malloc_block)-1 >= f_address && mtmp < f_address+size) {
// Bogus block, it's interrupted by a malloc_block.
if(mtmp+sizeof(_malloc_block)+size<(mblock->next)->data) {
// If there's enough space at the end of this malloc_block for data block, shift it
// and restart the search
f_address=mtmp+sizeof(_malloc_block);
mtmp=_first_malloc_block;
// By setting mtmp to _first_malloc_block, we are going to not be able to
// check the first malloc_block in the next cycle. However, this is not a
// problem because either the block didn't interfere with the first
// malloc_block, or it has just been adjusted so that it doesn't. :)
} else {
// If there isn't space, then we have to continue searching between data blocks
mtmp_search_ok=0;
}
}
// If our block isn't interrupted by a malloc_block, then continue checking
mtmp=mtmp->next;
}
if(mtmp_search_okay) {
//Our data block has passed all tests, we can return it
found_block=1;
}
// If our block isn't okay, then go search for another candidate between the data blocks
}
// f_address now points to a block of ram at least size big. Happy days!
return f_address;
}
void *malloc(size_t size) {
_malloc_block *mblock,*mtmp;
void *t;
mblock=_find_free_ram(sizeof(_malloc_block));
// Find a place to put another _malloc_block structure
mtmp=_first_malloc_block;
if(!mtmp) {
// What if there are no _malloc_block's yet? IE- this is the first call to malloc
_first_malloc_block=mblock;
mblock->next=0;
mblock->size=size;
mblock->data=_find_free_ram(size);
return mblock;
}
while(mtmp->next) {
if((mtmp->next)->data > mblock)
break;
// Find the largest value of mtmp->data that is less than mblock.
// since the linked list is -always- organized ascending by mtmp->data,
// we can be assured that this is correct
}
t=mtmp->next;
mtmp->next=mblock;
mblock->next=t;
mblock->size=size;
mblock->data=_find_free_ram(size);
// We have just inserted the element. Or appended, if it was at the end of the list.
return mblock;
}
void *calloc(num_t num, size_t size)
{
// Calloc is silly, it wants two arguments. Stupid ancient ansi stuff. Oh well...
void *t,*i;
// If either one of our arguments is null, do nothing.
if(!(num*size))
return 0;
// Wipe the ram. That's the only good thing about calloc().
t=malloc(size*num);
for(i=t;i<t+size;i++)
*i=0;
return t;
}
void *free(void *ptr) {
// If an unallocated pointer is passed, return a -1. Otherwise return null.
// This is against the ANSI typedef of free() !!!!!!
// ANSI says this: void free(void *ptr)
// Making free() an int shouldn't cause any problems anywhere.
// However, it -does- allow us to not have 'undefined' behavior when
// you attempt to free an unallocated pointer.
_malloc_block *mtmp,*mtp=0;
// If we are passed a NULL, we aren't sposed to do anything...
if(!ptr)
return 0;
// Go search for ptr...
mtmp=_first_malloc_block;
while(mtmp) {
if(mtmp->data = ptr)
break;
mtp=mtmp;
mtmp=mtmp->next;
}
if(!mtmp)
return -1; // Nope, you been passing me some shit...
if(!mtp) {
// There is only one allocated block, which we are removing...
_first_malloc_pointer=0;
return 0;
}
mtp->next=mtmp->next;
// To remove the block, all we have to do is cut the _malloc_block structure out of the list.
return 0;
}
void *realloc(void *ptr, size_t size)
{
// Remember, we must return a null if ptr isn't allocated!
_malloc_block *mtmp;
void *t;
size_t i;
// If ptr is null, then do a malloc...
if(!ptr)
return malloc(size);
// If size is null, then free this junx.
if(!size)
return free(ptr);
mtmp=_first_malloc_block;
while(mtmp) {
if(mtmp->data = ptr)
break;
mtmp=mtmp->next;
}
if(!mtmp)
return 0; // We didn't find it. ANSI says that behavior should be 'undefined' in this case.
// I'm being nice and telling you it didn't work.
t=malloc(size);
for(i=0,i<t+size;i++)
*(t+i)=*(ptr+i);
// Copy over the old ram...
free(ptr);
return t;
}
Follow-Ups: