From d376e7c68059ffe25079307168455cc8bfa134ea Mon Sep 17 00:00:00 2001
From: "Mike D. Lowis" <mike.lowis@gentex.com>
Date: Wed, 1 Apr 2015 10:37:56 -0400
Subject: [PATCH] Finished initial implementation of heap module

---
 build.rb              |  2 +-
 source/runtime/heap.c | 24 +++++++++++++++++-------
 source/runtime/heap.h | 13 +++++++++----
 tests/test_heap.c     | 40 +++++++++++++++++++++++++++++++++++++---
 4 files changed, 64 insertions(+), 15 deletions(-)

diff --git a/build.rb b/build.rb
index 5d048de..7508bde 100755
--- a/build.rb
+++ b/build.rb
@@ -1,4 +1,4 @@
-#!/usr/bin/ruby
+#!/usr/bin/env ruby
 
 require_relative 'modules/build-system/setup'
 
diff --git a/source/runtime/heap.c b/source/runtime/heap.c
index 2b4b095..5c64b64 100644
--- a/source/runtime/heap.c
+++ b/source/runtime/heap.c
@@ -7,13 +7,20 @@
 
 heap_t* heap_create(void)
 {
-    heap_t* heap = (heap_t*)calloc(1u, sizeof(heap_t));
-    return heap;
+    return (heap_t*)calloc(1u, sizeof(heap_t));;
 }
 
 void heap_destroy(heap_t* heap)
 {
     int i;
+    block_t* current = heap->blocks;
+    /* Free all the large blocks */
+    while (NULL != current) {
+        block_t* deadite = current;
+        current = deadite->next;
+        free(deadite);
+    }
+    /* Free all of the small block segments */
     for (i = 0; i < NUM_HEAP_STACKS; i++) {
         segnode_t* curr = heap->heaps[i];
         while (NULL != curr) {
@@ -23,13 +30,13 @@ void heap_destroy(heap_t* heap)
             free(deadite);
         }
     }
+    /* Free the heap itself */
     free(heap);
 }
 
-void* allocate_small_block(heap_t* heap, uintptr_t num_slots)
+static void* allocate_small_block(heap_t* heap, uintptr_t num_slots)
 {
-    uintptr_t index = num_slots - HEAP_INDEX_OFFSET;
-    printf("index: %d, %d\n", (unsigned int)index, (unsigned int)num_slots);
+    uintptr_t index = (num_slots >= MIN_NUM_SLOTS) ? (num_slots - HEAP_INDEX_OFFSET) : 0;
     segnode_t* node = heap->heaps[index];
     if ((NULL == node) || segment_full(node->segment)) {
         segnode_t* newnode = (segnode_t*)malloc(sizeof(segnode_t));
@@ -41,9 +48,12 @@ void* allocate_small_block(heap_t* heap, uintptr_t num_slots)
     return segment_alloc(heap->heaps[index]->segment);
 }
 
-void* allocate_large_block(heap_t* heap, uintptr_t num_slots)
+static void* allocate_large_block(heap_t* heap, uintptr_t num_slots)
 {
-    return NULL;
+    block_t* blk = (block_t*)malloc(sizeof(block_t) + (num_slots * sizeof(uintptr_t)));
+    blk->next = heap->blocks;
+    heap->blocks = blk;
+    return (&blk->data[0]);
 }
 
 void* heap_allocate(heap_t* heap, uintptr_t num_slots)
diff --git a/source/runtime/heap.h b/source/runtime/heap.h
index 54ae442..926b6bf 100644
--- a/source/runtime/heap.h
+++ b/source/runtime/heap.h
@@ -7,22 +7,27 @@
 
 #include "segment.h"
 
-#define MIN_NUM_SLOTS (2u)
+#define MIN_NUM_SLOTS (1u)
 
-#define MAX_NUM_SLOTS ((sizeof(uintptr_t)*8u) - 1u)
+#define MAX_NUM_SLOTS (sizeof(uintptr_t) * 8u)
 
 #define HEAP_INDEX_OFFSET (MIN_NUM_SLOTS)
 
-#define NUM_HEAP_STACKS ((sizeof(uintptr_t) * 8u) - 1)
+#define NUM_HEAP_STACKS (MAX_NUM_SLOTS)
 
 typedef struct segnode_t {
     segment_t* segment;
     struct segnode_t* next;
 } segnode_t;
 
+typedef struct block_t {
+    struct block_t* next;
+    uintptr_t data[];
+} block_t;
+
 typedef struct {
-    uintptr_t bytes_allocated;
     segnode_t* heaps[NUM_HEAP_STACKS];
+    block_t* blocks;
 } heap_t;
 
 heap_t* heap_create(void);
diff --git a/tests/test_heap.c b/tests/test_heap.c
index 83316e6..5087d70 100644
--- a/tests/test_heap.c
+++ b/tests/test_heap.c
@@ -7,11 +7,45 @@ TEST_SUITE(Heap) {
     TEST(Verify_Create_allocates_and_initializes_a_heap) {
         heap_t* heap = heap_create();
         CHECK(heap != NULL);
-
-        CHECK(NULL != heap_allocate(heap, 63));
+        CHECK(NULL != heap_allocate(heap, 64));
+        CHECK(NULL != heap_allocate(heap, 65));
         heap_destroy(heap);
     }
 
-    /* Verify: segment_alloc
+    /* Verify: heap_alloc
      *************************************************************************/
+    TEST(Verify_Allocate_should_allocate_a_new_segment_if_the_subheap_is_empty) {
+        heap_t* heap = heap_create();
+        CHECK(NULL != heap_allocate(heap, 1));
+        CHECK(heap->heaps[0] != NULL);
+        heap_destroy(heap);
+    }
+
+    TEST(Verify_Allocate_should_allocate_a_new_segment_if_the_current_segment_is_full) {
+        heap_t* heap = heap_create();
+        segnode_t* prev_seg_node;
+        CHECK(NULL != heap_allocate(heap, 1));
+        CHECK(heap->heaps[0] != NULL);
+        prev_seg_node = heap->heaps[0];
+        prev_seg_node->segment->blockmap[0] = 0;
+        CHECK(NULL != heap_allocate(heap, 1));
+        CHECK(heap->heaps[0] != prev_seg_node);
+        CHECK(heap->heaps[0]->next == prev_seg_node);
+        heap_destroy(heap);
+    }
+
+    TEST(Verify_Allocate_should_allocate_the_minimum_size_if_num_slots_is_less_than_the_minimum) {
+        heap_t* heap = heap_create();
+        CHECK(NULL != heap_allocate(heap, 0));
+        CHECK(heap->heaps[0] != NULL);
+        heap_destroy(heap);
+    }
+
+    TEST(Verify_Allocate_should_allocate_a_large_block_if_the_number_of_slots_is_greater_than_the_max) {
+        heap_t* heap = heap_create();
+        CHECK(NULL != heap_allocate(heap, 65));
+        CHECK(heap->blocks != NULL);
+        CHECK(heap->blocks->next == NULL);
+        heap_destroy(heap);
+    }
 }
-- 
2.52.0