From f40718dfab04e2e1f28f0322d44ca9ef2d7f9378 Mon Sep 17 00:00:00 2001 From: Erik Charlebois Date: Sat, 11 May 2013 22:02:05 -0400 Subject: [PATCH] VM: Refactor free_list_allocator to Factor style --- vm/free_list_allocator.hpp | 348 ++++++++++++++++++------------------- 1 file changed, 165 insertions(+), 183 deletions(-) diff --git a/vm/free_list_allocator.hpp b/vm/free_list_allocator.hpp index 7106f7cf13..a935802508 100644 --- a/vm/free_list_allocator.hpp +++ b/vm/free_list_allocator.hpp @@ -1,229 +1,211 @@ -namespace factor -{ - -template struct free_list_allocator { - cell size; - cell start; - cell end; - free_list free_blocks; - mark_bits state; - - explicit free_list_allocator(cell size, cell start); - void initial_free_list(cell occupied); - bool contains_p(Block *block); - Block *first_block(); - Block *last_block(); - Block *next_block_after(Block *block); - Block *next_allocated_block_after(Block *block); - bool can_allot_p(cell size); - Block *allot(cell size); - void free(Block *block); - cell occupied_space(); - cell free_space(); - cell largest_free_block(); - cell free_block_count(); - void sweep(); - template void sweep(Iterator &iter); - template void compact(Iterator &iter, Fixup fixup, const Block **finger); - template void iterate(Iterator &iter, Fixup fixup); - template void iterate(Iterator &iter); +namespace factor { + +template struct free_list_allocator { + cell size; + cell start; + cell end; + free_list free_blocks; + mark_bits state; + + explicit free_list_allocator(cell size, cell start); + void initial_free_list(cell occupied); + bool contains_p(Block* block); + Block* first_block(); + Block* last_block(); + Block* next_block_after(Block* block); + Block* next_allocated_block_after(Block* block); + bool can_allot_p(cell size); + Block* allot(cell size); + void free(Block* block); + cell occupied_space(); + cell free_space(); + cell largest_free_block(); + cell free_block_count(); + void sweep(); + template void sweep(Iterator& iter); + template + void compact(Iterator& iter, Fixup fixup, const Block** finger); + template + void iterate(Iterator& iter, Fixup fixup); + template void iterate(Iterator& iter); }; -template -free_list_allocator::free_list_allocator(cell size_, cell start_) : - size(size_), - start(start_), - end(start_ + size_), - state(mark_bits(size_,start_)) -{ - initial_free_list(0); +template +free_list_allocator::free_list_allocator(cell size_, cell start_) + : size(size_), + start(start_), + end(start_ + size_), + state(mark_bits(size_, start_)) { + initial_free_list(0); } -template void free_list_allocator::initial_free_list(cell occupied) -{ - free_blocks.initial_free_list(start,end,occupied); +template +void free_list_allocator::initial_free_list(cell occupied) { + free_blocks.initial_free_list(start, end, occupied); } -template bool free_list_allocator::contains_p(Block *block) -{ - return ((cell)block - start) < size; +template +bool free_list_allocator::contains_p(Block* block) { + return ((cell) block - start) < size; } -template Block *free_list_allocator::first_block() -{ - return (Block *)start; +template Block* free_list_allocator::first_block() { + return (Block*)start; } -template Block *free_list_allocator::last_block() -{ - return (Block *)end; +template Block* free_list_allocator::last_block() { + return (Block*)end; } -template Block *free_list_allocator::next_block_after(Block *block) -{ - return (Block *)((cell)block + block->size()); +template +Block* free_list_allocator::next_block_after(Block* block) { + return (Block*)((cell) block + block->size()); } -template Block *free_list_allocator::next_allocated_block_after(Block *block) -{ - while(block != this->last_block() && block->free_p()) - { - free_heap_block *free_block = (free_heap_block *)block; - block = (object *)((cell)free_block + free_block->size()); - } +template +Block* free_list_allocator::next_allocated_block_after(Block* block) { + while (block != this->last_block() && block->free_p()) { + free_heap_block* free_block = (free_heap_block*)block; + block = (object*)((cell) free_block + free_block->size()); + } - if(block == this->last_block()) - return NULL; - else - return block; + if (block == this->last_block()) + return NULL; + else + return block; } -template bool free_list_allocator::can_allot_p(cell size) -{ - return free_blocks.can_allot_p(size); +template +bool free_list_allocator::can_allot_p(cell size) { + return free_blocks.can_allot_p(size); } -template Block *free_list_allocator::allot(cell size) -{ - size = align(size,data_alignment); +template Block* free_list_allocator::allot(cell size) { + size = align(size, data_alignment); - free_heap_block *block = free_blocks.find_free_block(size); - if(block) - { - block = free_blocks.split_free_block(block,size); - return (Block *)block; - } - else - return NULL; + free_heap_block* block = free_blocks.find_free_block(size); + if (block) { + block = free_blocks.split_free_block(block, size); + return (Block*)block; + } else + return NULL; } -template void free_list_allocator::free(Block *block) -{ - free_heap_block *free_block = (free_heap_block *)block; - free_block->make_free(block->size()); - free_blocks.add_to_free_list(free_block); +template void free_list_allocator::free(Block* block) { + free_heap_block* free_block = (free_heap_block*)block; + free_block->make_free(block->size()); + free_blocks.add_to_free_list(free_block); } -template cell free_list_allocator::free_space() -{ - return free_blocks.free_space; +template cell free_list_allocator::free_space() { + return free_blocks.free_space; } -template cell free_list_allocator::occupied_space() -{ - return size - free_blocks.free_space; +template cell free_list_allocator::occupied_space() { + return size - free_blocks.free_space; } -template cell free_list_allocator::largest_free_block() -{ - return free_blocks.largest_free_block(); +template +cell free_list_allocator::largest_free_block() { + return free_blocks.largest_free_block(); } -template cell free_list_allocator::free_block_count() -{ - return free_blocks.free_block_count; +template cell free_list_allocator::free_block_count() { + return free_blocks.free_block_count; } -template -template -void free_list_allocator::sweep(Iterator &iter) -{ - free_blocks.clear_free_list(); +template +template +void free_list_allocator::sweep(Iterator& iter) { + free_blocks.clear_free_list(); - Block *start = this->first_block(); - Block *end = this->last_block(); + Block* start = this->first_block(); + Block* end = this->last_block(); - while(start != end) - { - /* find next unmarked block */ - start = state.next_unmarked_block_after(start); - - if(start != end) - { - /* find size */ - cell size = state.unmarked_block_size(start); - FACTOR_ASSERT(size > 0); + while (start != end) { + /* find next unmarked block */ + start = state.next_unmarked_block_after(start); - free_heap_block *free_block = (free_heap_block *)start; - free_block->make_free(size); - free_blocks.add_to_free_list(free_block); - iter(start, size); + if (start != end) { + /* find size */ + cell size = state.unmarked_block_size(start); + FACTOR_ASSERT(size > 0); - start = (Block *)((char *)start + size); - } - } + free_heap_block* free_block = (free_heap_block*)start; + free_block->make_free(size); + free_blocks.add_to_free_list(free_block); + iter(start, size); + + start = (Block*)((char*)start + size); + } + } } -template -struct null_sweep_iterator -{ - void operator()(Block *free_block, cell size) {} +template struct null_sweep_iterator { + void operator()(Block* free_block, cell size) {} }; -template -void free_list_allocator::sweep() -{ - null_sweep_iterator none; - sweep(none); -} - -template struct heap_compactor { - mark_bits *state; - char *address; - Iterator &iter; - const Block **finger; - - explicit heap_compactor(mark_bits *state_, Block *address_, Iterator &iter_, const Block **finger_) : - state(state_), address((char *)address_), iter(iter_), finger(finger_) {} - - void operator()(Block *block, cell size) - { - if(this->state->marked_p(block)) - { - *finger = (Block *)((char *)block + size); - memmove((Block *)address,block,size); - iter(block,(Block *)address,size); - address += size; - } - } +template void free_list_allocator::sweep() { + null_sweep_iterator none; + sweep(none); +} + +template struct heap_compactor { + mark_bits* state; + char* address; + Iterator& iter; + const Block** finger; + + explicit heap_compactor(mark_bits* state_, Block* address_, + Iterator& iter_, const Block** finger_) + : state(state_), address((char*)address_), iter(iter_), finger(finger_) {} + + void operator()(Block* block, cell size) { + if (this->state->marked_p(block)) { + *finger = (Block*)((char*)block + size); + memmove((Block*)address, block, size); + iter(block, (Block*)address, size); + address += size; + } + } }; /* The forwarding map must be computed first by calling -state.compute_forwarding(). */ -template -template -void free_list_allocator::compact(Iterator &iter, Fixup fixup, const Block **finger) -{ - heap_compactor compactor(&state,first_block(),iter,finger); - iterate(compactor,fixup); - - /* Now update the free list; there will be a single free block at - the end */ - free_blocks.initial_free_list(start,end,(cell)compactor.address - start); -} - -/* During compaction we have to be careful and measure object sizes differently */ -template -template -void free_list_allocator::iterate(Iterator &iter, Fixup fixup) -{ - Block *scan = first_block(); - Block *end = last_block(); - - while(scan != end) - { - cell size = fixup.size(scan); - Block *next = (Block *)((cell)scan + size); - if(!scan->free_p()) iter(scan,size); - scan = next; - } -} - -template -template -void free_list_allocator::iterate(Iterator &iter) -{ - iterate(iter,no_fixup()); + state.compute_forwarding(). */ +template +template +void free_list_allocator::compact(Iterator& iter, Fixup fixup, + const Block** finger) { + heap_compactor compactor(&state, first_block(), iter, + finger); + iterate(compactor, fixup); + + /* Now update the free list; there will be a single free block at + the end */ + free_blocks.initial_free_list(start, end, (cell) compactor.address - start); +} + +/* During compaction we have to be careful and measure object sizes + differently */ +template +template +void free_list_allocator::iterate(Iterator& iter, Fixup fixup) { + Block* scan = first_block(); + Block* end = last_block(); + + while (scan != end) { + cell size = fixup.size(scan); + Block* next = (Block*)((cell) scan + size); + if (!scan->free_p()) + iter(scan, size); + scan = next; + } +} + +template +template +void free_list_allocator::iterate(Iterator& iter) { + iterate(iter, no_fixup()); } } -- 2.34.1