Re-import from Subversion.

[pdclib] / functions / stdlib / malloc.c

diff --git a/functions/stdlib/malloc.c b/functions/stdlib/malloc.c
index d1a8d5e3673374222c0af0287aaa76ecfe988856..a563350f929faf48c6949cdf59c1fe2c52031648 100644 (file)
--- a/functions/stdlib/malloc.c
+++ b/functions/stdlib/malloc.c
@@ -1,8 +1,121 @@
-// ----------------------------------------------------------------------------
-// $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;
+}