-// ----------------------------------------------------------------------------
-// $Id$
-// ----------------------------------------------------------------------------
-// Public Domain C Library - http://pdclib.sourceforge.net
-// This code is Public Domain. Use, modify, and redistribute at will.
-// ----------------------------------------------------------------------------
+/* ----------------------------------------------------------------------------
+ * $Id$
+ * ----------------------------------------------------------------------------
+ * Public Domain C Library - http://pdclib.sourceforge.net
+ * This code is Public Domain. Use, modify, and redistribute at will.
+ * --------------------------------------------------------------------------*/
+
+#include <__size_t.h>
void * malloc( size_t size ) { /* TODO */ };
+
+/* This is a simple best-fit / first-fit implementation heavily based on
+ * Thomas "Beyond Infinity" Kreitner's code
+ */
+
+/* memory list element */
+struct chunk_t
+{
+ void * address;
+ size_t size;
+ chunk_t * next;
+};
+
+struct memlist_t
+{
+ chunk_t * start;
+ chunk_t * last;
+};
+
+size_t heap_start = 0xa0000000;
+size_t heap_used = 0x00000050; /* HEAP in use. Holds the next FREE address (?) */
+size_t heap_max = 0xfffffff; /* max. HEAP */
+
+static struct memlist_t free_mem = { (struct memlist_t *) heap_start,
+ (struct memlist_t *) heap_start };
+/* free_mem.start->next = NULL; */
+
+static struct memlist_t used_mem = { (struct memlist_t *) heap_start + sizeof( chunk_t ),
+ (struct memlist_t *) heap_start + sizeof( chunk_t ) };
+/* used_mem.start->next = NULL; */
+
+void * malloc( size_t size )
+{
+ chunk_t * chunk = 0;
+ chunk_t * prev_chunk;
+ if ( free_mem.start != free_mem.last )
+ {
+ /* first pass: exact fit */
+ chunk = free_mem.start;
+ while ( 1 )
+ {
+ prev_chunk = chunk;
+ chunk = chunk->next;
+ if ( ( chunk == NULL ) || ( chunk->size == size ) )
+ {
+ break;
+ }
+ }
+ }
+ if ( chunk == NULL )
+ {
+ /* second pass - first fit */
+ chunk = free_mem.start;
+ while ( 1 )
+ {
+ prev_chunk = chunk;
+ chunk = chunk-> next;
+ if ( ( chunk == NULL ) || ( chunk->size > size ) )
+ {
+ break;
+ }
+ }
+ }
+ if ( chunk != NULL )
+ {
+ /* remove chunk from free_mem list */
+ if ( free_mem.start->next->next == NULL )
+ {
+ /* free_mem list has only one entry */
+ free_mem.last = free_mem.start;
+ }
+ else if ( chunk == free_mem.last )
+ {
+ /* chunk is last element of free_mem list */
+ prev_chunk->next = NULL;
+ free_mem.last = prev_chunk;
+ }
+ else
+ {
+ /* chunk is neither only nor last in free_mem list */
+ prev_chunk->next = prev_chunk->next->next;
+ }
+ /* append chunk to used_mem list */
+ chunk->next = NULL;
+ used_mem.last->next = chunk;
+ used_mem.last = chunk;
+ }
+ /* append new chunk to end of used_mem list (if there's space) */
+ if ( chunk == NULL )
+ {
+ if ( ( heap_used + size ) <= heap_max )
+ {
+ /* building the header */
+ chunk = (chunk_t *) heap_start + heap_used + 1;
+ chunk->size = size;
+ chunk->next = NULL;
+ chunk->address = chunk + sizeof( chunk_t );
+ /* push heap_used past allocated area */
+ heap_used += sizeof( chunk_t ) + size;
+ used_mem.last->next = chunk;
+ used_mem.last = chunk;
+ }
+ else
+ {
+ /* allocation would exceed max. heap size -
+ /* demand more memory from kernel - not implemented */
+ return 0;
+ }
+ }
+ return (void *) chunk->address;
+}