From 48f71ac559ec2207379579af4d1f516d2535cb65 Mon Sep 17 00:00:00 2001
From: "Michael D. Lowis" <mike@mdlowis.com>
Date: Mon, 6 Apr 2015 22:22:09 -0400
Subject: [PATCH] move segments to a full list when they have been fully
 allocated

---
 source/runtime/heap.c | 27 ++++++++++++++++++---------
 source/runtime/heap.h |  5 ++++-
 tests/test_heap.c     | 15 +++++++--------
 3 files changed, 29 insertions(+), 18 deletions(-)

diff --git a/source/runtime/heap.c b/source/runtime/heap.c
index 58fac98..66ab2cd 100644
--- a/source/runtime/heap.c
+++ b/source/runtime/heap.c
@@ -26,7 +26,7 @@ void heap_destroy(heap_t* heap)
     destroy_large_blocks(heap->greylist);
     /* Free all of the small block segments */
     for (i = 0; i < NUM_HEAP_STACKS; i++) {
-        segment_destroy(heap->heaps[i]);
+        segment_destroy(heap->heaps[i].available);
     }
     /* Free the heap itself */
     free(heap);
@@ -34,12 +34,21 @@ void heap_destroy(heap_t* heap)
 
 static void* allocate_small_block(heap_t* heap, uintptr_t num_slots)
 {
+    void* object;
     uintptr_t index = (num_slots >= MIN_NUM_SLOTS) ? (num_slots - HEAP_INDEX_OFFSET) : 0;
-    segment_t* current = heap->heaps[index];
-    if ((NULL == current) || segment_full(current)) {
-        heap->heaps[index] = segment_create(num_slots, current);
+    /* If we dont have any available segments, allocate a new one */
+    if (NULL == heap->heaps[index].available)
+        heap->heaps[index].available = segment_create(num_slots, heap->heaps[index].available);
+    /* Allocate the object */
+    object = segment_alloc(heap->heaps[index].available);
+    /* If we filled it up then move it to the full list */
+    if (segment_full(heap->heaps[index].available)) {
+        segment_t* current = heap->heaps[index].available;
+        heap->heaps[index].available = heap->heaps[index].available->next;
+        current->next = heap->heaps[index].full;
+        heap->heaps[index].full = current;
     }
-    return segment_alloc(heap->heaps[index]);
+    return object;
 }
 
 static void* allocate_large_block(heap_t* heap, uintptr_t num_slots)
@@ -68,8 +77,8 @@ void heap_start_collection(heap_t* heap)
     heap->greylist = heap->blocks;
     heap->blocks = NULL;
     for (uintptr_t i = 0; i < NUM_HEAP_STACKS; i++) {
-        for(segment_t* curr = heap->heaps[i]; curr != NULL; curr = curr->next) {
-            segment_clear_map(heap->heaps[i]);
+        for(segment_t* curr = heap->heaps[i].available; curr != NULL; curr = curr->next) {
+            segment_clear_map(heap->heaps[i].available);
         }
     }
 }
@@ -83,8 +92,8 @@ void heap_finish_collection(heap_t* heap)
 static void* subheap_find_and_mark(heap_t* heap, uintptr_t addr) {
     void* obj = NULL;
     for (uintptr_t i = 0; i < NUM_HEAP_STACKS; i++) {
-        for(segment_t* curr = heap->heaps[i]; curr != NULL; curr = curr->next) {
-            obj = segment_find_and_mark(heap->heaps[i], addr);
+        for(segment_t* curr = heap->heaps[i].available; curr != NULL; curr = curr->next) {
+            obj = segment_find_and_mark(heap->heaps[i].available, addr);
             if (NULL != obj) {
                 i = NUM_HEAP_STACKS;
                 break;
diff --git a/source/runtime/heap.h b/source/runtime/heap.h
index 39b2a92..9544b8e 100644
--- a/source/runtime/heap.h
+++ b/source/runtime/heap.h
@@ -22,7 +22,10 @@ typedef struct block_t {
 } block_t;
 
 typedef struct {
-    segment_t* heaps[NUM_HEAP_STACKS];
+    struct {
+        segment_t* available;
+        segment_t* full;
+    } heaps[NUM_HEAP_STACKS];
     block_t* blocks;
     block_t* greylist;
 } heap_t;
diff --git a/tests/test_heap.c b/tests/test_heap.c
index 13acbdc..5e46ad5 100644
--- a/tests/test_heap.c
+++ b/tests/test_heap.c
@@ -18,27 +18,26 @@ TEST_SUITE(Heap) {
     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);
+        CHECK(heap->heaps[0].available != NULL);
         heap_destroy(heap);
     }
 
     TEST(Verify_Allocate_should_allocate_a_new_segment_if_the_current_segment_is_full) {
         heap_t* heap = heap_create();
-        segment_t* prev;
         CHECK(NULL != heap_allocate(heap, 1));
-        CHECK(heap->heaps[0] != NULL);
-        prev = heap->heaps[0];
-        prev->blockmap[0] = 0;
+        heap->heaps[0].available->blockmap[0] = 1 << ((sizeof(uint16_t) * 8) - 1);
+        heap->heaps[0].available->blockmap[16] = 1 << ((sizeof(uint16_t) * 8) - 1);
         CHECK(NULL != heap_allocate(heap, 1));
-        CHECK(heap->heaps[0] != prev);
-        CHECK(heap->heaps[0]->next == prev);
+        CHECK(heap->heaps[0].available == NULL);
+        CHECK(heap->heaps[0].full != NULL);
+        CHECK(heap->heaps[0].full->next == NULL);
         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);
+        CHECK(heap->heaps[0].available != NULL);
         heap_destroy(heap);
     }
 
-- 
2.52.0