From c0aa1c7b3ec9ab46d55062819daa8bedce185e43 Mon Sep 17 00:00:00 2001 From: Erik Charlebois Date: Sat, 11 May 2013 22:01:24 -0400 Subject: [PATCH] VM: Refactor free_list to Factor style --- vm/free_list.cpp | 214 ++++++++++++++++++++++------------------------- vm/free_list.hpp | 72 +++++++--------- 2 files changed, 130 insertions(+), 156 deletions(-) diff --git a/vm/free_list.cpp b/vm/free_list.cpp index 9b4b06683d..46de38ddae 100644 --- a/vm/free_list.cpp +++ b/vm/free_list.cpp @@ -1,135 +1,117 @@ #include "master.hpp" -namespace factor -{ - -void free_list::clear_free_list() -{ - for(cell i = 0; i < free_list_count; i++) - small_blocks[i].clear(); - large_blocks.clear(); - free_block_count = 0; - free_space = 0; +namespace factor { + +void free_list::clear_free_list() { + for (cell i = 0; i < free_list_count; i++) + small_blocks[i].clear(); + large_blocks.clear(); + free_block_count = 0; + free_space = 0; } -void free_list::initial_free_list(cell start, cell end, cell occupied) -{ - clear_free_list(); - if(occupied != end - start) - { - free_heap_block *last_block = (free_heap_block *)(start + occupied); - last_block->make_free(end - (cell)last_block); - add_to_free_list(last_block); - } +void free_list::initial_free_list(cell start, cell end, cell occupied) { + clear_free_list(); + if (occupied != end - start) { + free_heap_block* last_block = (free_heap_block*)(start + occupied); + last_block->make_free(end - (cell) last_block); + add_to_free_list(last_block); + } } -void free_list::add_to_free_list(free_heap_block *block) -{ - cell size = block->size(); +void free_list::add_to_free_list(free_heap_block* block) { + cell size = block->size(); - free_block_count++; - free_space += size; + free_block_count++; + free_space += size; - if(size < free_list_count * data_alignment) - small_blocks[size / data_alignment].push_back(block); - else - large_blocks.insert(block); + if (size < free_list_count * data_alignment) + small_blocks[size / data_alignment].push_back(block); + else + large_blocks.insert(block); } -free_heap_block *free_list::find_free_block(cell size) -{ - /* Check small free lists */ - if(size / data_alignment < free_list_count) - { - std::vector &blocks = small_blocks[size / data_alignment]; - if(blocks.size() == 0) - { - /* Round up to a multiple of 'size' */ - cell large_block_size = ((allocation_page_size + size - 1) / size) * size; - - /* Allocate a block this big */ - free_heap_block *large_block = find_free_block(large_block_size); - if(!large_block) return NULL; - - large_block = split_free_block(large_block,large_block_size); - - /* Split it up into pieces and add each piece back to the free list */ - for(cell offset = 0; offset < large_block_size; offset += size) - { - free_heap_block *small_block = large_block; - large_block = (free_heap_block *)((cell)large_block + size); - small_block->make_free(size); - add_to_free_list(small_block); - } - } - - free_heap_block *block = blocks.back(); - blocks.pop_back(); - - free_block_count--; - free_space -= block->size(); - - return block; - } - else - { - /* Check large free list */ - free_heap_block key; - key.make_free(size); - large_block_set::iterator iter = large_blocks.lower_bound(&key); - large_block_set::iterator end = large_blocks.end(); - - if(iter != end) - { - free_heap_block *block = *iter; - large_blocks.erase(iter); - - free_block_count--; - free_space -= block->size(); - - return block; - } - - return NULL; - } +free_heap_block* free_list::find_free_block(cell size) { + /* Check small free lists */ + if (size / data_alignment < free_list_count) { + std::vector& blocks = small_blocks[size / data_alignment]; + if (blocks.size() == 0) { + /* Round up to a multiple of 'size' */ + cell large_block_size = ((allocation_page_size + size - 1) / size) * size; + + /* Allocate a block this big */ + free_heap_block* large_block = find_free_block(large_block_size); + if (!large_block) + return NULL; + + large_block = split_free_block(large_block, large_block_size); + + /* Split it up into pieces and add each piece back to the free list */ + for (cell offset = 0; offset < large_block_size; offset += size) { + free_heap_block* small_block = large_block; + large_block = (free_heap_block*)((cell) large_block + size); + small_block->make_free(size); + add_to_free_list(small_block); + } + } + + free_heap_block* block = blocks.back(); + blocks.pop_back(); + + free_block_count--; + free_space -= block->size(); + + return block; + } else { + /* Check large free list */ + free_heap_block key; + key.make_free(size); + large_block_set::iterator iter = large_blocks.lower_bound(&key); + large_block_set::iterator end = large_blocks.end(); + + if (iter != end) { + free_heap_block* block = *iter; + large_blocks.erase(iter); + + free_block_count--; + free_space -= block->size(); + + return block; + } + + return NULL; + } } -free_heap_block *free_list::split_free_block(free_heap_block *block, cell size) -{ - if(block->size() != size) - { - /* split the block in two */ - free_heap_block *split = (free_heap_block *)((cell)block + size); - split->make_free(block->size() - size); - block->make_free(size); - add_to_free_list(split); - } - - return block; +free_heap_block* free_list::split_free_block(free_heap_block* block, + cell size) { + if (block->size() != size) { + /* split the block in two */ + free_heap_block* split = (free_heap_block*)((cell) block + size); + split->make_free(block->size() - size); + block->make_free(size); + add_to_free_list(split); + } + + return block; } -bool free_list::can_allot_p(cell size) -{ - return largest_free_block() >= std::max(size,allocation_page_size); +bool free_list::can_allot_p(cell size) { + return largest_free_block() >= std::max(size, allocation_page_size); } -cell free_list::largest_free_block() -{ - if(large_blocks.size()) - { - large_block_set::reverse_iterator last = large_blocks.rbegin(); - return (*last)->size(); - } - else - { - for(int i = free_list_count - 1; i >= 0; i--) - { - if(small_blocks[i].size()) - return small_blocks[i].back()->size(); - } - - return 0; - } +cell free_list::largest_free_block() { + if (large_blocks.size()) { + large_block_set::reverse_iterator last = large_blocks.rbegin(); + return (*last)->size(); + } else { + for (int i = free_list_count - 1; i >= 0; i--) { + if (small_blocks[i].size()) + return small_blocks[i].back()->size(); + } + + return 0; + } } } diff --git a/vm/free_list.hpp b/vm/free_list.hpp index e0c5a7063b..d30570c5e5 100644 --- a/vm/free_list.hpp +++ b/vm/free_list.hpp @@ -1,54 +1,46 @@ -namespace factor -{ +namespace factor { static const cell free_list_count = 32; static const cell allocation_page_size = 1024; -struct free_heap_block -{ - cell header; - - bool free_p() const - { - return (header & 1) == 1; - } - - cell size() const - { - cell size = header & ~7; - FACTOR_ASSERT(size > 0); - return size; - } - - void make_free(cell size) - { - FACTOR_ASSERT(size > 0); - header = size | 1; - } +struct free_heap_block { + cell header; + + bool free_p() const { return (header & 1) == 1; } + + cell size() const { + cell size = header & ~7; + FACTOR_ASSERT(size > 0); + return size; + } + + void make_free(cell size) { + FACTOR_ASSERT(size > 0); + header = size | 1; + } }; struct block_size_compare { - bool operator()(free_heap_block *a, free_heap_block *b) const - { - return a->size() < b->size(); - } + bool operator()(free_heap_block* a, free_heap_block* b) const { + return a->size() < b->size(); + } }; -typedef std::multiset large_block_set; +typedef std::multiset large_block_set; struct free_list { - std::vector small_blocks[free_list_count]; - large_block_set large_blocks; - cell free_block_count; - cell free_space; - - void clear_free_list(); - void initial_free_list(cell start, cell end, cell occupied); - void add_to_free_list(free_heap_block *block); - free_heap_block *find_free_block(cell size); - free_heap_block *split_free_block(free_heap_block *block, cell size); - bool can_allot_p(cell size); - cell largest_free_block(); + std::vector small_blocks[free_list_count]; + large_block_set large_blocks; + cell free_block_count; + cell free_space; + + void clear_free_list(); + void initial_free_list(cell start, cell end, cell occupied); + void add_to_free_list(free_heap_block* block); + free_heap_block* find_free_block(cell size); + free_heap_block* split_free_block(free_heap_block* block, cell size); + bool can_allot_p(cell size); + cell largest_free_block(); }; } -- 2.34.1