src/share/vm/memory/binaryTreeDictionary.cpp
Print this page
*** 42,61 ****
////////////////////////////////////////////////////////////////////////////////
// A binary tree based search structure for free blocks.
// This is currently used in the Concurrent Mark&Sweep implementation.
////////////////////////////////////////////////////////////////////////////////
! template <class Chunk_t, template <class> class FreeList_t>
size_t TreeChunk<Chunk_t, FreeList_t>::_min_tree_chunk_size = sizeof(TreeChunk<Chunk_t, FreeList_t>)/HeapWordSize;
! template <class Chunk_t, template <class> class FreeList_t>
TreeChunk<Chunk_t, FreeList_t>* TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(Chunk_t* fc) {
// Do some assertion checking here.
return (TreeChunk<Chunk_t, FreeList_t>*) fc;
}
! template <class Chunk_t, template <class> class FreeList_t>
void TreeChunk<Chunk_t, FreeList_t>::verify_tree_chunk_list() const {
TreeChunk<Chunk_t, FreeList_t>* nextTC = (TreeChunk<Chunk_t, FreeList_t>*)next();
if (prev() != NULL) { // interior list node shouldn't have tree fields
guarantee(embedded_list()->parent() == NULL && embedded_list()->left() == NULL &&
embedded_list()->right() == NULL, "should be clear");
--- 42,61 ----
////////////////////////////////////////////////////////////////////////////////
// A binary tree based search structure for free blocks.
// This is currently used in the Concurrent Mark&Sweep implementation.
////////////////////////////////////////////////////////////////////////////////
! template <class Chunk_t, class FreeList_t>
size_t TreeChunk<Chunk_t, FreeList_t>::_min_tree_chunk_size = sizeof(TreeChunk<Chunk_t, FreeList_t>)/HeapWordSize;
! template <class Chunk_t, class FreeList_t>
TreeChunk<Chunk_t, FreeList_t>* TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(Chunk_t* fc) {
// Do some assertion checking here.
return (TreeChunk<Chunk_t, FreeList_t>*) fc;
}
! template <class Chunk_t, class FreeList_t>
void TreeChunk<Chunk_t, FreeList_t>::verify_tree_chunk_list() const {
TreeChunk<Chunk_t, FreeList_t>* nextTC = (TreeChunk<Chunk_t, FreeList_t>*)next();
if (prev() != NULL) { // interior list node shouldn't have tree fields
guarantee(embedded_list()->parent() == NULL && embedded_list()->left() == NULL &&
embedded_list()->right() == NULL, "should be clear");
*** 65,79 ****
guarantee(nextTC->size() == size(), "wrong size");
nextTC->verify_tree_chunk_list();
}
}
! template <class Chunk_t, template <class> class FreeList_t>
TreeList<Chunk_t, FreeList_t>::TreeList() : _parent(NULL),
_left(NULL), _right(NULL) {}
! template <class Chunk_t, template <class> class FreeList_t>
TreeList<Chunk_t, FreeList_t>*
TreeList<Chunk_t, FreeList_t>::as_TreeList(TreeChunk<Chunk_t,FreeList_t>* tc) {
// This first free chunk in the list will be the tree list.
assert((tc->size() >= (TreeChunk<Chunk_t, FreeList_t>::min_size())),
"Chunk is too small for a TreeChunk");
--- 65,79 ----
guarantee(nextTC->size() == size(), "wrong size");
nextTC->verify_tree_chunk_list();
}
}
! template <class Chunk_t, class FreeList_t>
TreeList<Chunk_t, FreeList_t>::TreeList() : _parent(NULL),
_left(NULL), _right(NULL) {}
! template <class Chunk_t, class FreeList_t>
TreeList<Chunk_t, FreeList_t>*
TreeList<Chunk_t, FreeList_t>::as_TreeList(TreeChunk<Chunk_t,FreeList_t>* tc) {
// This first free chunk in the list will be the tree list.
assert((tc->size() >= (TreeChunk<Chunk_t, FreeList_t>::min_size())),
"Chunk is too small for a TreeChunk");
*** 86,109 ****
tl->set_count(1);
assert(tl->parent() == NULL, "Should be clear");
return tl;
}
!
! template <class Chunk_t, template <class> class FreeList_t>
! TreeList<Chunk_t, FreeList_t>*
! get_chunk(size_t size, enum FreeBlockDictionary<Chunk_t>::Dither dither) {
! FreeBlockDictionary<Chunk_t>::verify_par_locked();
! Chunk_t* res = get_chunk_from_tree(size, dither);
! assert(res == NULL || res->is_free(),
! "Should be returning a free chunk");
! assert(dither != FreeBlockDictionary<Chunk_t>::exactly ||
! res->size() == size, "Not correct size");
! return res;
! }
!
! template <class Chunk_t, template <class> class FreeList_t>
TreeList<Chunk_t, FreeList_t>*
TreeList<Chunk_t, FreeList_t>::as_TreeList(HeapWord* addr, size_t size) {
TreeChunk<Chunk_t, FreeList_t>* tc = (TreeChunk<Chunk_t, FreeList_t>*) addr;
assert((size >= TreeChunk<Chunk_t, FreeList_t>::min_size()),
"Chunk is too small for a TreeChunk");
--- 86,96 ----
tl->set_count(1);
assert(tl->parent() == NULL, "Should be clear");
return tl;
}
! template <class Chunk_t, class FreeList_t>
TreeList<Chunk_t, FreeList_t>*
TreeList<Chunk_t, FreeList_t>::as_TreeList(HeapWord* addr, size_t size) {
TreeChunk<Chunk_t, FreeList_t>* tc = (TreeChunk<Chunk_t, FreeList_t>*) addr;
assert((size >= TreeChunk<Chunk_t, FreeList_t>::min_size()),
"Chunk is too small for a TreeChunk");
*** 123,143 ****
// Specialize for AdaptiveFreeList which tries to avoid
// splitting a chunk of a size that is under populated in favor of
// an over populated size. The general get_better_list() just returns
// the current list.
template <>
! TreeList<FreeChunk, AdaptiveFreeList>*
! TreeList<FreeChunk, AdaptiveFreeList>::get_better_list(
! BinaryTreeDictionary<FreeChunk, ::AdaptiveFreeList>* dictionary) {
// A candidate chunk has been found. If it is already under
// populated, get a chunk associated with the hint for this
// chunk.
! TreeList<FreeChunk, ::AdaptiveFreeList>* curTL = this;
if (surplus() <= 0) {
/* Use the hint to find a size with a surplus, and reset the hint. */
! TreeList<FreeChunk, ::AdaptiveFreeList>* hintTL = this;
while (hintTL->hint() != 0) {
assert(hintTL->hint() > hintTL->size(),
"hint points in the wrong direction");
hintTL = dictionary->find_list(hintTL->hint());
assert(curTL != hintTL, "Infinite loop");
--- 110,130 ----
// Specialize for AdaptiveFreeList which tries to avoid
// splitting a chunk of a size that is under populated in favor of
// an over populated size. The general get_better_list() just returns
// the current list.
template <>
! TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >*
! TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >::get_better_list(
! BinaryTreeDictionary<FreeChunk, ::AdaptiveFreeList<FreeChunk> >* dictionary) {
// A candidate chunk has been found. If it is already under
// populated, get a chunk associated with the hint for this
// chunk.
! TreeList<FreeChunk, ::AdaptiveFreeList<FreeChunk> >* curTL = this;
if (surplus() <= 0) {
/* Use the hint to find a size with a surplus, and reset the hint. */
! TreeList<FreeChunk, ::AdaptiveFreeList<FreeChunk> >* hintTL = this;
while (hintTL->hint() != 0) {
assert(hintTL->hint() > hintTL->size(),
"hint points in the wrong direction");
hintTL = dictionary->find_list(hintTL->hint());
assert(curTL != hintTL, "Infinite loop");
*** 161,178 ****
}
return curTL;
}
#endif // INCLUDE_ALL_GCS
! template <class Chunk_t, template <class> class FreeList_t>
TreeList<Chunk_t, FreeList_t>*
TreeList<Chunk_t, FreeList_t>::get_better_list(
BinaryTreeDictionary<Chunk_t, FreeList_t>* dictionary) {
return this;
}
! template <class Chunk_t, template <class> class FreeList_t>
TreeList<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::remove_chunk_replace_if_needed(TreeChunk<Chunk_t, FreeList_t>* tc) {
TreeList<Chunk_t, FreeList_t>* retTL = this;
Chunk_t* list = head();
assert(!list || list != list->next(), "Chunk on list twice");
--- 148,165 ----
}
return curTL;
}
#endif // INCLUDE_ALL_GCS
! template <class Chunk_t, class FreeList_t>
TreeList<Chunk_t, FreeList_t>*
TreeList<Chunk_t, FreeList_t>::get_better_list(
BinaryTreeDictionary<Chunk_t, FreeList_t>* dictionary) {
return this;
}
! template <class Chunk_t, class FreeList_t>
TreeList<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::remove_chunk_replace_if_needed(TreeChunk<Chunk_t, FreeList_t>* tc) {
TreeList<Chunk_t, FreeList_t>* retTL = this;
Chunk_t* list = head();
assert(!list || list != list->next(), "Chunk on list twice");
*** 284,294 ****
assert(retTL->tail() == NULL || retTL->tail()->next() == NULL,
"list invariant");
return retTL;
}
! template <class Chunk_t, template <class> class FreeList_t>
void TreeList<Chunk_t, FreeList_t>::return_chunk_at_tail(TreeChunk<Chunk_t, FreeList_t>* chunk) {
assert(chunk != NULL, "returning NULL chunk");
assert(chunk->list() == this, "list should be set for chunk");
assert(tail() != NULL, "The tree list is embedded in the first chunk");
// which means that the list can never be empty.
--- 271,281 ----
assert(retTL->tail() == NULL || retTL->tail()->next() == NULL,
"list invariant");
return retTL;
}
! template <class Chunk_t, class FreeList_t>
void TreeList<Chunk_t, FreeList_t>::return_chunk_at_tail(TreeChunk<Chunk_t, FreeList_t>* chunk) {
assert(chunk != NULL, "returning NULL chunk");
assert(chunk->list() == this, "list should be set for chunk");
assert(tail() != NULL, "The tree list is embedded in the first chunk");
// which means that the list can never be empty.
*** 299,319 ****
Chunk_t* fc = tail();
fc->link_after(chunk);
this->link_tail(chunk);
assert(!tail() || size() == tail()->size(), "Wrong sized chunk in list");
! FreeList_t<Chunk_t>::increment_count();
debug_only(this->increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));)
assert(head() == NULL || head()->prev() == NULL, "list invariant");
assert(tail() == NULL || tail()->next() == NULL, "list invariant");
}
// Add this chunk at the head of the list. "At the head of the list"
// is defined to be after the chunk pointer to by head(). This is
// because the TreeList<Chunk_t, FreeList_t> is embedded in the first TreeChunk<Chunk_t, FreeList_t> in the
// list. See the definition of TreeChunk<Chunk_t, FreeList_t>.
! template <class Chunk_t, template <class> class FreeList_t>
void TreeList<Chunk_t, FreeList_t>::return_chunk_at_head(TreeChunk<Chunk_t, FreeList_t>* chunk) {
assert(chunk->list() == this, "list should be set for chunk");
assert(head() != NULL, "The tree list is embedded in the first chunk");
assert(chunk != NULL, "returning NULL chunk");
assert(!this->verify_chunk_in_free_list(chunk), "Double entry");
--- 286,306 ----
Chunk_t* fc = tail();
fc->link_after(chunk);
this->link_tail(chunk);
assert(!tail() || size() == tail()->size(), "Wrong sized chunk in list");
! FreeList_t::increment_count();
debug_only(this->increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));)
assert(head() == NULL || head()->prev() == NULL, "list invariant");
assert(tail() == NULL || tail()->next() == NULL, "list invariant");
}
// Add this chunk at the head of the list. "At the head of the list"
// is defined to be after the chunk pointer to by head(). This is
// because the TreeList<Chunk_t, FreeList_t> is embedded in the first TreeChunk<Chunk_t, FreeList_t> in the
// list. See the definition of TreeChunk<Chunk_t, FreeList_t>.
! template <class Chunk_t, class FreeList_t>
void TreeList<Chunk_t, FreeList_t>::return_chunk_at_head(TreeChunk<Chunk_t, FreeList_t>* chunk) {
assert(chunk->list() == this, "list should be set for chunk");
assert(head() != NULL, "The tree list is embedded in the first chunk");
assert(chunk != NULL, "returning NULL chunk");
assert(!this->verify_chunk_in_free_list(chunk), "Double entry");
*** 327,360 ****
assert(tail() == NULL, "List is inconsistent");
this->link_tail(chunk);
}
head()->link_after(chunk);
assert(!head() || size() == head()->size(), "Wrong sized chunk in list");
! FreeList_t<Chunk_t>::increment_count();
debug_only(this->increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));)
assert(head() == NULL || head()->prev() == NULL, "list invariant");
assert(tail() == NULL || tail()->next() == NULL, "list invariant");
}
! template <class Chunk_t, template <class> class FreeList_t>
void TreeChunk<Chunk_t, FreeList_t>::assert_is_mangled() const {
assert((ZapUnusedHeapArea &&
SpaceMangler::is_mangled((HeapWord*) Chunk_t::size_addr()) &&
SpaceMangler::is_mangled((HeapWord*) Chunk_t::prev_addr()) &&
SpaceMangler::is_mangled((HeapWord*) Chunk_t::next_addr())) ||
(size() == 0 && prev() == NULL && next() == NULL),
"Space should be clear or mangled");
}
! template <class Chunk_t, template <class> class FreeList_t>
TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::head_as_TreeChunk() {
assert(head() == NULL || (TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(head())->list() == this),
"Wrong type of chunk?");
return TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(head());
}
! template <class Chunk_t, template <class> class FreeList_t>
TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::first_available() {
assert(head() != NULL, "The head of the list cannot be NULL");
Chunk_t* fc = head()->next();
TreeChunk<Chunk_t, FreeList_t>* retTC;
if (fc == NULL) {
--- 314,347 ----
assert(tail() == NULL, "List is inconsistent");
this->link_tail(chunk);
}
head()->link_after(chunk);
assert(!head() || size() == head()->size(), "Wrong sized chunk in list");
! FreeList_t::increment_count();
debug_only(this->increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));)
assert(head() == NULL || head()->prev() == NULL, "list invariant");
assert(tail() == NULL || tail()->next() == NULL, "list invariant");
}
! template <class Chunk_t, class FreeList_t>
void TreeChunk<Chunk_t, FreeList_t>::assert_is_mangled() const {
assert((ZapUnusedHeapArea &&
SpaceMangler::is_mangled((HeapWord*) Chunk_t::size_addr()) &&
SpaceMangler::is_mangled((HeapWord*) Chunk_t::prev_addr()) &&
SpaceMangler::is_mangled((HeapWord*) Chunk_t::next_addr())) ||
(size() == 0 && prev() == NULL && next() == NULL),
"Space should be clear or mangled");
}
! template <class Chunk_t, class FreeList_t>
TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::head_as_TreeChunk() {
assert(head() == NULL || (TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(head())->list() == this),
"Wrong type of chunk?");
return TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(head());
}
! template <class Chunk_t, class FreeList_t>
TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::first_available() {
assert(head() != NULL, "The head of the list cannot be NULL");
Chunk_t* fc = head()->next();
TreeChunk<Chunk_t, FreeList_t>* retTC;
if (fc == NULL) {
*** 367,377 ****
}
// Returns the block with the largest heap address amongst
// those in the list for this size; potentially slow and expensive,
// use with caution!
! template <class Chunk_t, template <class> class FreeList_t>
TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::largest_address() {
assert(head() != NULL, "The head of the list cannot be NULL");
Chunk_t* fc = head()->next();
TreeChunk<Chunk_t, FreeList_t>* retTC;
if (fc == NULL) {
--- 354,364 ----
}
// Returns the block with the largest heap address amongst
// those in the list for this size; potentially slow and expensive,
// use with caution!
! template <class Chunk_t, class FreeList_t>
TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::largest_address() {
assert(head() != NULL, "The head of the list cannot be NULL");
Chunk_t* fc = head()->next();
TreeChunk<Chunk_t, FreeList_t>* retTC;
if (fc == NULL) {
*** 390,400 ****
}
assert(retTC->list() == this, "Wrong type of chunk.");
return retTC;
}
! template <class Chunk_t, template <class> class FreeList_t>
BinaryTreeDictionary<Chunk_t, FreeList_t>::BinaryTreeDictionary(MemRegion mr) {
assert((mr.byte_size() > min_size()), "minimum chunk size");
reset(mr);
assert(root()->left() == NULL, "reset check failed");
--- 377,387 ----
}
assert(retTC->list() == this, "Wrong type of chunk.");
return retTC;
}
! template <class Chunk_t, class FreeList_t>
BinaryTreeDictionary<Chunk_t, FreeList_t>::BinaryTreeDictionary(MemRegion mr) {
assert((mr.byte_size() > min_size()), "minimum chunk size");
reset(mr);
assert(root()->left() == NULL, "reset check failed");
*** 403,445 ****
assert(root()->head()->prev() == NULL, "reset check failed");
assert(total_size() == root()->size(), "reset check failed");
assert(total_free_blocks() == 1, "reset check failed");
}
! template <class Chunk_t, template <class> class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::inc_total_size(size_t inc) {
_total_size = _total_size + inc;
}
! template <class Chunk_t, template <class> class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::dec_total_size(size_t dec) {
_total_size = _total_size - dec;
}
! template <class Chunk_t, template <class> class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset(MemRegion mr) {
assert((mr.byte_size() > min_size()), "minimum chunk size");
set_root(TreeList<Chunk_t, FreeList_t>::as_TreeList(mr.start(), mr.word_size()));
set_total_size(mr.word_size());
set_total_free_blocks(1);
}
! template <class Chunk_t, template <class> class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset(HeapWord* addr, size_t byte_size) {
MemRegion mr(addr, heap_word_size(byte_size));
reset(mr);
}
! template <class Chunk_t, template <class> class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset() {
set_root(NULL);
set_total_size(0);
set_total_free_blocks(0);
}
// Get a free block of size at least size from tree, or NULL.
! template <class Chunk_t, template <class> class FreeList_t>
TreeChunk<Chunk_t, FreeList_t>*
BinaryTreeDictionary<Chunk_t, FreeList_t>::get_chunk_from_tree(
size_t size,
enum FreeBlockDictionary<Chunk_t>::Dither dither)
{
--- 390,432 ----
assert(root()->head()->prev() == NULL, "reset check failed");
assert(total_size() == root()->size(), "reset check failed");
assert(total_free_blocks() == 1, "reset check failed");
}
! template <class Chunk_t, class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::inc_total_size(size_t inc) {
_total_size = _total_size + inc;
}
! template <class Chunk_t, class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::dec_total_size(size_t dec) {
_total_size = _total_size - dec;
}
! template <class Chunk_t, class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset(MemRegion mr) {
assert((mr.byte_size() > min_size()), "minimum chunk size");
set_root(TreeList<Chunk_t, FreeList_t>::as_TreeList(mr.start(), mr.word_size()));
set_total_size(mr.word_size());
set_total_free_blocks(1);
}
! template <class Chunk_t, class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset(HeapWord* addr, size_t byte_size) {
MemRegion mr(addr, heap_word_size(byte_size));
reset(mr);
}
! template <class Chunk_t, class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset() {
set_root(NULL);
set_total_size(0);
set_total_free_blocks(0);
}
// Get a free block of size at least size from tree, or NULL.
! template <class Chunk_t, class FreeList_t>
TreeChunk<Chunk_t, FreeList_t>*
BinaryTreeDictionary<Chunk_t, FreeList_t>::get_chunk_from_tree(
size_t size,
enum FreeBlockDictionary<Chunk_t>::Dither dither)
{
*** 494,504 ****
verify();
}
return retTC;
}
! template <class Chunk_t, template <class> class FreeList_t>
TreeList<Chunk_t, FreeList_t>* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_list(size_t size) const {
TreeList<Chunk_t, FreeList_t>* curTL;
for (curTL = root(); curTL != NULL;) {
if (curTL->size() == size) { // exact match
break;
--- 481,491 ----
verify();
}
return retTC;
}
! template <class Chunk_t, class FreeList_t>
TreeList<Chunk_t, FreeList_t>* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_list(size_t size) const {
TreeList<Chunk_t, FreeList_t>* curTL;
for (curTL = root(); curTL != NULL;) {
if (curTL->size() == size) { // exact match
break;
*** 513,534 ****
}
return curTL;
}
! template <class Chunk_t, template <class> class FreeList_t>
bool BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_chunk_in_free_list(Chunk_t* tc) const {
size_t size = tc->size();
TreeList<Chunk_t, FreeList_t>* tl = find_list(size);
if (tl == NULL) {
return false;
} else {
return tl->verify_chunk_in_free_list(tc);
}
}
! template <class Chunk_t, template <class> class FreeList_t>
Chunk_t* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_largest_dict() const {
TreeList<Chunk_t, FreeList_t> *curTL = root();
if (curTL != NULL) {
while(curTL->right() != NULL) curTL = curTL->right();
return curTL->largest_address();
--- 500,521 ----
}
return curTL;
}
! template <class Chunk_t, class FreeList_t>
bool BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_chunk_in_free_list(Chunk_t* tc) const {
size_t size = tc->size();
TreeList<Chunk_t, FreeList_t>* tl = find_list(size);
if (tl == NULL) {
return false;
} else {
return tl->verify_chunk_in_free_list(tc);
}
}
! template <class Chunk_t, class FreeList_t>
Chunk_t* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_largest_dict() const {
TreeList<Chunk_t, FreeList_t> *curTL = root();
if (curTL != NULL) {
while(curTL->right() != NULL) curTL = curTL->right();
return curTL->largest_address();
*** 539,549 ****
// Remove the current chunk from the tree. If it is not the last
// chunk in a list on a tree node, just unlink it.
// If it is the last chunk in the list (the next link is NULL),
// remove the node and repair the tree.
! template <class Chunk_t, template <class> class FreeList_t>
TreeChunk<Chunk_t, FreeList_t>*
BinaryTreeDictionary<Chunk_t, FreeList_t>::remove_chunk_from_tree(TreeChunk<Chunk_t, FreeList_t>* tc) {
assert(tc != NULL, "Should not call with a NULL chunk");
assert(tc->is_free(), "Header is not marked correctly");
--- 526,536 ----
// Remove the current chunk from the tree. If it is not the last
// chunk in a list on a tree node, just unlink it.
// If it is the last chunk in the list (the next link is NULL),
// remove the node and repair the tree.
! template <class Chunk_t, class FreeList_t>
TreeChunk<Chunk_t, FreeList_t>*
BinaryTreeDictionary<Chunk_t, FreeList_t>::remove_chunk_from_tree(TreeChunk<Chunk_t, FreeList_t>* tc) {
assert(tc != NULL, "Should not call with a NULL chunk");
assert(tc->is_free(), "Header is not marked correctly");
*** 680,690 ****
}
// Remove the leftmost node (lm) in the tree and return it.
// If lm has a right child, link it to the left node of
// the parent of lm.
! template <class Chunk_t, template <class> class FreeList_t>
TreeList<Chunk_t, FreeList_t>* BinaryTreeDictionary<Chunk_t, FreeList_t>::remove_tree_minimum(TreeList<Chunk_t, FreeList_t>* tl) {
assert(tl != NULL && tl->parent() != NULL, "really need a proper sub-tree");
// locate the subtree minimum by walking down left branches
TreeList<Chunk_t, FreeList_t>* curTL = tl;
for (; curTL->left() != NULL; curTL = curTL->left());
--- 667,677 ----
}
// Remove the leftmost node (lm) in the tree and return it.
// If lm has a right child, link it to the left node of
// the parent of lm.
! template <class Chunk_t, class FreeList_t>
TreeList<Chunk_t, FreeList_t>* BinaryTreeDictionary<Chunk_t, FreeList_t>::remove_tree_minimum(TreeList<Chunk_t, FreeList_t>* tl) {
assert(tl != NULL && tl->parent() != NULL, "really need a proper sub-tree");
// locate the subtree minimum by walking down left branches
TreeList<Chunk_t, FreeList_t>* curTL = tl;
for (; curTL->left() != NULL; curTL = curTL->left());
*** 715,725 ****
verify_tree();
}
return curTL;
}
! template <class Chunk_t, template <class> class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::insert_chunk_in_tree(Chunk_t* fc) {
TreeList<Chunk_t, FreeList_t> *curTL, *prevTL;
size_t size = fc->size();
assert((size >= min_size()),
--- 702,712 ----
verify_tree();
}
return curTL;
}
! template <class Chunk_t, class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::insert_chunk_in_tree(Chunk_t* fc) {
TreeList<Chunk_t, FreeList_t> *curTL, *prevTL;
size_t size = fc->size();
assert((size >= min_size()),
*** 781,800 ****
if (FLSVerifyDictionary) {
verify_tree();
}
}
! template <class Chunk_t, template <class> class FreeList_t>
size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::max_chunk_size() const {
FreeBlockDictionary<Chunk_t>::verify_par_locked();
TreeList<Chunk_t, FreeList_t>* tc = root();
if (tc == NULL) return 0;
for (; tc->right() != NULL; tc = tc->right());
return tc->size();
}
! template <class Chunk_t, template <class> class FreeList_t>
size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_list_length(TreeList<Chunk_t, FreeList_t>* tl) const {
size_t res;
res = tl->count();
#ifdef ASSERT
size_t cnt;
--- 768,787 ----
if (FLSVerifyDictionary) {
verify_tree();
}
}
! template <class Chunk_t, class FreeList_t>
size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::max_chunk_size() const {
FreeBlockDictionary<Chunk_t>::verify_par_locked();
TreeList<Chunk_t, FreeList_t>* tc = root();
if (tc == NULL) return 0;
for (; tc->right() != NULL; tc = tc->right());
return tc->size();
}
! template <class Chunk_t, class FreeList_t>
size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_list_length(TreeList<Chunk_t, FreeList_t>* tl) const {
size_t res;
res = tl->count();
#ifdef ASSERT
size_t cnt;
*** 803,822 ****
assert(res == cnt, "The count is not being maintained correctly");
#endif
return res;
}
! template <class Chunk_t, template <class> class FreeList_t>
size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_size_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const {
if (tl == NULL)
return 0;
return (tl->size() * total_list_length(tl)) +
total_size_in_tree(tl->left()) +
total_size_in_tree(tl->right());
}
! template <class Chunk_t, template <class> class FreeList_t>
double BinaryTreeDictionary<Chunk_t, FreeList_t>::sum_of_squared_block_sizes(TreeList<Chunk_t, FreeList_t>* const tl) const {
if (tl == NULL) {
return 0.0;
}
double size = (double)(tl->size());
--- 790,809 ----
assert(res == cnt, "The count is not being maintained correctly");
#endif
return res;
}
! template <class Chunk_t, class FreeList_t>
size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_size_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const {
if (tl == NULL)
return 0;
return (tl->size() * total_list_length(tl)) +
total_size_in_tree(tl->left()) +
total_size_in_tree(tl->right());
}
! template <class Chunk_t, class FreeList_t>
double BinaryTreeDictionary<Chunk_t, FreeList_t>::sum_of_squared_block_sizes(TreeList<Chunk_t, FreeList_t>* const tl) const {
if (tl == NULL) {
return 0.0;
}
double size = (double)(tl->size());
*** 824,883 ****
curr += sum_of_squared_block_sizes(tl->left());
curr += sum_of_squared_block_sizes(tl->right());
return curr;
}
! template <class Chunk_t, template <class> class FreeList_t>
size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_free_blocks_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const {
if (tl == NULL)
return 0;
return total_list_length(tl) +
total_free_blocks_in_tree(tl->left()) +
total_free_blocks_in_tree(tl->right());
}
! template <class Chunk_t, template <class> class FreeList_t>
size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::num_free_blocks() const {
assert(total_free_blocks_in_tree(root()) == total_free_blocks(),
"_total_free_blocks inconsistency");
return total_free_blocks();
}
! template <class Chunk_t, template <class> class FreeList_t>
size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::tree_height_helper(TreeList<Chunk_t, FreeList_t>* tl) const {
if (tl == NULL)
return 0;
return 1 + MAX2(tree_height_helper(tl->left()),
tree_height_helper(tl->right()));
}
! template <class Chunk_t, template <class> class FreeList_t>
size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::tree_height() const {
return tree_height_helper(root());
}
! template <class Chunk_t, template <class> class FreeList_t>
size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_nodes_helper(TreeList<Chunk_t, FreeList_t>* tl) const {
if (tl == NULL) {
return 0;
}
return 1 + total_nodes_helper(tl->left()) +
total_nodes_helper(tl->right());
}
! template <class Chunk_t, template <class> class FreeList_t>
size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_nodes_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const {
return total_nodes_helper(root());
}
! template <class Chunk_t, template <class> class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::dict_census_update(size_t size, bool split, bool birth){}
#if INCLUDE_ALL_GCS
template <>
! void AFLBinaryTreeDictionary::dict_census_update(size_t size, bool split, bool birth){
! TreeList<FreeChunk, AdaptiveFreeList>* nd = find_list(size);
if (nd) {
if (split) {
if (birth) {
nd->increment_split_births();
nd->increment_surplus();
--- 811,870 ----
curr += sum_of_squared_block_sizes(tl->left());
curr += sum_of_squared_block_sizes(tl->right());
return curr;
}
! template <class Chunk_t, class FreeList_t>
size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_free_blocks_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const {
if (tl == NULL)
return 0;
return total_list_length(tl) +
total_free_blocks_in_tree(tl->left()) +
total_free_blocks_in_tree(tl->right());
}
! template <class Chunk_t, class FreeList_t>
size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::num_free_blocks() const {
assert(total_free_blocks_in_tree(root()) == total_free_blocks(),
"_total_free_blocks inconsistency");
return total_free_blocks();
}
! template <class Chunk_t, class FreeList_t>
size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::tree_height_helper(TreeList<Chunk_t, FreeList_t>* tl) const {
if (tl == NULL)
return 0;
return 1 + MAX2(tree_height_helper(tl->left()),
tree_height_helper(tl->right()));
}
! template <class Chunk_t, class FreeList_t>
size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::tree_height() const {
return tree_height_helper(root());
}
! template <class Chunk_t, class FreeList_t>
size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_nodes_helper(TreeList<Chunk_t, FreeList_t>* tl) const {
if (tl == NULL) {
return 0;
}
return 1 + total_nodes_helper(tl->left()) +
total_nodes_helper(tl->right());
}
! template <class Chunk_t, class FreeList_t>
size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_nodes_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const {
return total_nodes_helper(root());
}
! template <class Chunk_t, class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::dict_census_update(size_t size, bool split, bool birth){}
#if INCLUDE_ALL_GCS
template <>
! void AFLBinaryTreeDictionary::dict_census_update(size_t size, bool split, bool birth) {
! TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >* nd = find_list(size);
if (nd) {
if (split) {
if (birth) {
nd->increment_split_births();
nd->increment_surplus();
*** 901,911 ****
// This is a birth associated with a LinAB. The chunk
// for the LinAB is not in the dictionary.
}
#endif // INCLUDE_ALL_GCS
! template <class Chunk_t, template <class> class FreeList_t>
bool BinaryTreeDictionary<Chunk_t, FreeList_t>::coal_dict_over_populated(size_t size) {
// For the general type of freelists, encourage coalescing by
// returning true.
return true;
}
--- 888,898 ----
// This is a birth associated with a LinAB. The chunk
// for the LinAB is not in the dictionary.
}
#endif // INCLUDE_ALL_GCS
! template <class Chunk_t, class FreeList_t>
bool BinaryTreeDictionary<Chunk_t, FreeList_t>::coal_dict_over_populated(size_t size) {
// For the general type of freelists, encourage coalescing by
// returning true.
return true;
}
*** 913,923 ****
#if INCLUDE_ALL_GCS
template <>
bool AFLBinaryTreeDictionary::coal_dict_over_populated(size_t size) {
if (FLSAlwaysCoalesceLarge) return true;
! TreeList<FreeChunk, AdaptiveFreeList>* list_of_size = find_list(size);
// None of requested size implies overpopulated.
return list_of_size == NULL || list_of_size->coal_desired() <= 0 ||
list_of_size->count() > list_of_size->coal_desired();
}
#endif // INCLUDE_ALL_GCS
--- 900,910 ----
#if INCLUDE_ALL_GCS
template <>
bool AFLBinaryTreeDictionary::coal_dict_over_populated(size_t size) {
if (FLSAlwaysCoalesceLarge) return true;
! TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >* list_of_size = find_list(size);
// None of requested size implies overpopulated.
return list_of_size == NULL || list_of_size->coal_desired() <= 0 ||
list_of_size->count() > list_of_size->coal_desired();
}
#endif // INCLUDE_ALL_GCS
*** 926,944 ****
// do_list() walks the free list in a node applying the closure
// to each free chunk in the list
// do_tree() walks the nodes in the binary tree applying do_list()
// to each list at each node.
! template <class Chunk_t, template <class> class FreeList_t>
class TreeCensusClosure : public StackObj {
protected:
! virtual void do_list(FreeList_t<Chunk_t>* fl) = 0;
public:
virtual void do_tree(TreeList<Chunk_t, FreeList_t>* tl) = 0;
};
! template <class Chunk_t, template <class> class FreeList_t>
class AscendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> {
public:
void do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
if (tl != NULL) {
do_tree(tl->left());
--- 913,931 ----
// do_list() walks the free list in a node applying the closure
// to each free chunk in the list
// do_tree() walks the nodes in the binary tree applying do_list()
// to each list at each node.
! template <class Chunk_t, class FreeList_t>
class TreeCensusClosure : public StackObj {
protected:
! virtual void do_list(FreeList_t* fl) = 0;
public:
virtual void do_tree(TreeList<Chunk_t, FreeList_t>* tl) = 0;
};
! template <class Chunk_t, class FreeList_t>
class AscendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> {
public:
void do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
if (tl != NULL) {
do_tree(tl->left());
*** 946,956 ****
do_tree(tl->right());
}
}
};
! template <class Chunk_t, template <class> class FreeList_t>
class DescendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> {
public:
void do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
if (tl != NULL) {
do_tree(tl->right());
--- 933,943 ----
do_tree(tl->right());
}
}
};
! template <class Chunk_t, class FreeList_t>
class DescendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> {
public:
void do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
if (tl != NULL) {
do_tree(tl->right());
*** 960,970 ****
}
};
// For each list in the tree, calculate the desired, desired
// coalesce, count before sweep, and surplus before sweep.
! template <class Chunk_t, template <class> class FreeList_t>
class BeginSweepClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
double _percentage;
float _inter_sweep_current;
float _inter_sweep_estimate;
float _intra_sweep_estimate;
--- 947,957 ----
}
};
// For each list in the tree, calculate the desired, desired
// coalesce, count before sweep, and surplus before sweep.
! template <class Chunk_t, class FreeList_t>
class BeginSweepClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
double _percentage;
float _inter_sweep_current;
float _inter_sweep_estimate;
float _intra_sweep_estimate;
*** 993,1012 ****
// Used to search the tree until a condition is met.
// Similar to TreeCensusClosure but searches the
// tree and returns promptly when found.
! template <class Chunk_t, template <class> class FreeList_t>
class TreeSearchClosure : public StackObj {
protected:
! virtual bool do_list(FreeList_t<Chunk_t>* fl) = 0;
public:
virtual bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) = 0;
};
#if 0 // Don't need this yet but here for symmetry.
! template <class Chunk_t, template <class> class FreeList_t>
class AscendTreeSearchClosure : public TreeSearchClosure<Chunk_t> {
public:
bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
if (tl != NULL) {
if (do_tree(tl->left())) return true;
--- 980,999 ----
// Used to search the tree until a condition is met.
// Similar to TreeCensusClosure but searches the
// tree and returns promptly when found.
! template <class Chunk_t, class FreeList_t>
class TreeSearchClosure : public StackObj {
protected:
! virtual bool do_list(FreeList_t* fl) = 0;
public:
virtual bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) = 0;
};
#if 0 // Don't need this yet but here for symmetry.
! template <class Chunk_t, class FreeList_t>
class AscendTreeSearchClosure : public TreeSearchClosure<Chunk_t> {
public:
bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
if (tl != NULL) {
if (do_tree(tl->left())) return true;
*** 1016,1026 ****
return false;
}
};
#endif
! template <class Chunk_t, template <class> class FreeList_t>
class DescendTreeSearchClosure : public TreeSearchClosure<Chunk_t, FreeList_t> {
public:
bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
if (tl != NULL) {
if (do_tree(tl->right())) return true;
--- 1003,1013 ----
return false;
}
};
#endif
! template <class Chunk_t, class FreeList_t>
class DescendTreeSearchClosure : public TreeSearchClosure<Chunk_t, FreeList_t> {
public:
bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
if (tl != NULL) {
if (do_tree(tl->right())) return true;
*** 1031,1048 ****
}
};
// Searches the tree for a chunk that ends at the
// specified address.
! template <class Chunk_t, template <class> class FreeList_t>
class EndTreeSearchClosure : public DescendTreeSearchClosure<Chunk_t, FreeList_t> {
HeapWord* _target;
Chunk_t* _found;
public:
EndTreeSearchClosure(HeapWord* target) : _target(target), _found(NULL) {}
! bool do_list(FreeList_t<Chunk_t>* fl) {
Chunk_t* item = fl->head();
while (item != NULL) {
if (item->end() == (uintptr_t*) _target) {
_found = item;
return true;
--- 1018,1035 ----
}
};
// Searches the tree for a chunk that ends at the
// specified address.
! template <class Chunk_t, class FreeList_t>
class EndTreeSearchClosure : public DescendTreeSearchClosure<Chunk_t, FreeList_t> {
HeapWord* _target;
Chunk_t* _found;
public:
EndTreeSearchClosure(HeapWord* target) : _target(target), _found(NULL) {}
! bool do_list(FreeList_t* fl) {
Chunk_t* item = fl->head();
while (item != NULL) {
if (item->end() == (uintptr_t*) _target) {
_found = item;
return true;
*** 1052,1071 ****
return false;
}
Chunk_t* found() { return _found; }
};
! template <class Chunk_t, template <class> class FreeList_t>
Chunk_t* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_chunk_ends_at(HeapWord* target) const {
EndTreeSearchClosure<Chunk_t, FreeList_t> etsc(target);
bool found_target = etsc.do_tree(root());
assert(found_target || etsc.found() == NULL, "Consistency check");
assert(!found_target || etsc.found() != NULL, "Consistency check");
return etsc.found();
}
! template <class Chunk_t, template <class> class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::begin_sweep_dict_census(double coalSurplusPercent,
float inter_sweep_current, float inter_sweep_estimate, float intra_sweep_estimate) {
BeginSweepClosure<Chunk_t, FreeList_t> bsc(coalSurplusPercent, inter_sweep_current,
inter_sweep_estimate,
intra_sweep_estimate);
--- 1039,1058 ----
return false;
}
Chunk_t* found() { return _found; }
};
! template <class Chunk_t, class FreeList_t>
Chunk_t* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_chunk_ends_at(HeapWord* target) const {
EndTreeSearchClosure<Chunk_t, FreeList_t> etsc(target);
bool found_target = etsc.do_tree(root());
assert(found_target || etsc.found() == NULL, "Consistency check");
assert(!found_target || etsc.found() != NULL, "Consistency check");
return etsc.found();
}
! template <class Chunk_t, class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::begin_sweep_dict_census(double coalSurplusPercent,
float inter_sweep_current, float inter_sweep_estimate, float intra_sweep_estimate) {
BeginSweepClosure<Chunk_t, FreeList_t> bsc(coalSurplusPercent, inter_sweep_current,
inter_sweep_estimate,
intra_sweep_estimate);
*** 1073,1136 ****
}
// Closures and methods for calculating total bytes returned to the
// free lists in the tree.
#ifndef PRODUCT
! template <class Chunk_t, template <class> class FreeList_t>
class InitializeDictReturnedBytesClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
public:
! void do_list(FreeList_t<Chunk_t>* fl) {
fl->set_returned_bytes(0);
}
};
! template <class Chunk_t, template <class> class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::initialize_dict_returned_bytes() {
InitializeDictReturnedBytesClosure<Chunk_t, FreeList_t> idrb;
idrb.do_tree(root());
}
! template <class Chunk_t, template <class> class FreeList_t>
class ReturnedBytesClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
size_t _dict_returned_bytes;
public:
ReturnedBytesClosure() { _dict_returned_bytes = 0; }
! void do_list(FreeList_t<Chunk_t>* fl) {
_dict_returned_bytes += fl->returned_bytes();
}
size_t dict_returned_bytes() { return _dict_returned_bytes; }
};
! template <class Chunk_t, template <class> class FreeList_t>
size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::sum_dict_returned_bytes() {
ReturnedBytesClosure<Chunk_t, FreeList_t> rbc;
rbc.do_tree(root());
return rbc.dict_returned_bytes();
}
// Count the number of entries in the tree.
! template <class Chunk_t, template <class> class FreeList_t>
class treeCountClosure : public DescendTreeCensusClosure<Chunk_t, FreeList_t> {
public:
uint count;
treeCountClosure(uint c) { count = c; }
! void do_list(FreeList_t<Chunk_t>* fl) {
count++;
}
};
! template <class Chunk_t, template <class> class FreeList_t>
size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_count() {
treeCountClosure<Chunk_t, FreeList_t> ctc(0);
ctc.do_tree(root());
return ctc.count;
}
#endif // PRODUCT
// Calculate surpluses for the lists in the tree.
! template <class Chunk_t, template <class> class FreeList_t>
class setTreeSurplusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
double percentage;
public:
setTreeSurplusClosure(double v) { percentage = v; }
void do_list(FreeList<Chunk_t>* fl) {}
--- 1060,1123 ----
}
// Closures and methods for calculating total bytes returned to the
// free lists in the tree.
#ifndef PRODUCT
! template <class Chunk_t, class FreeList_t>
class InitializeDictReturnedBytesClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
public:
! void do_list(FreeList_t* fl) {
fl->set_returned_bytes(0);
}
};
! template <class Chunk_t, class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::initialize_dict_returned_bytes() {
InitializeDictReturnedBytesClosure<Chunk_t, FreeList_t> idrb;
idrb.do_tree(root());
}
! template <class Chunk_t, class FreeList_t>
class ReturnedBytesClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
size_t _dict_returned_bytes;
public:
ReturnedBytesClosure() { _dict_returned_bytes = 0; }
! void do_list(FreeList_t* fl) {
_dict_returned_bytes += fl->returned_bytes();
}
size_t dict_returned_bytes() { return _dict_returned_bytes; }
};
! template <class Chunk_t, class FreeList_t>
size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::sum_dict_returned_bytes() {
ReturnedBytesClosure<Chunk_t, FreeList_t> rbc;
rbc.do_tree(root());
return rbc.dict_returned_bytes();
}
// Count the number of entries in the tree.
! template <class Chunk_t, class FreeList_t>
class treeCountClosure : public DescendTreeCensusClosure<Chunk_t, FreeList_t> {
public:
uint count;
treeCountClosure(uint c) { count = c; }
! void do_list(FreeList_t* fl) {
count++;
}
};
! template <class Chunk_t, class FreeList_t>
size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_count() {
treeCountClosure<Chunk_t, FreeList_t> ctc(0);
ctc.do_tree(root());
return ctc.count;
}
#endif // PRODUCT
// Calculate surpluses for the lists in the tree.
! template <class Chunk_t, class FreeList_t>
class setTreeSurplusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
double percentage;
public:
setTreeSurplusClosure(double v) { percentage = v; }
void do_list(FreeList<Chunk_t>* fl) {}
*** 1142,1159 ****
(ssize_t)((double)fl->desired() * splitSurplusPercent));
}
#endif // INCLUDE_ALL_GCS
};
! template <class Chunk_t, template <class> class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_surplus(double splitSurplusPercent) {
setTreeSurplusClosure<Chunk_t, FreeList_t> sts(splitSurplusPercent);
sts.do_tree(root());
}
// Set hints for the lists in the tree.
! template <class Chunk_t, template <class> class FreeList_t>
class setTreeHintsClosure : public DescendTreeCensusClosure<Chunk_t, FreeList_t> {
size_t hint;
public:
setTreeHintsClosure(size_t v) { hint = v; }
void do_list(FreeList<Chunk_t>* fl) {}
--- 1129,1146 ----
(ssize_t)((double)fl->desired() * splitSurplusPercent));
}
#endif // INCLUDE_ALL_GCS
};
! template <class Chunk_t, class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_surplus(double splitSurplusPercent) {
setTreeSurplusClosure<Chunk_t, FreeList_t> sts(splitSurplusPercent);
sts.do_tree(root());
}
// Set hints for the lists in the tree.
! template <class Chunk_t, class FreeList_t>
class setTreeHintsClosure : public DescendTreeCensusClosure<Chunk_t, FreeList_t> {
size_t hint;
public:
setTreeHintsClosure(size_t v) { hint = v; }
void do_list(FreeList<Chunk_t>* fl) {}
*** 1168,1185 ****
}
}
#endif // INCLUDE_ALL_GCS
};
! template <class Chunk_t, template <class> class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_hints(void) {
setTreeHintsClosure<Chunk_t, FreeList_t> sth(0);
sth.do_tree(root());
}
// Save count before previous sweep and splits and coalesces.
! template <class Chunk_t, template <class> class FreeList_t>
class clearTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
void do_list(FreeList<Chunk_t>* fl) {}
#if INCLUDE_ALL_GCS
void do_list(AdaptiveFreeList<Chunk_t>* fl) {
--- 1155,1172 ----
}
}
#endif // INCLUDE_ALL_GCS
};
! template <class Chunk_t, class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_hints(void) {
setTreeHintsClosure<Chunk_t, FreeList_t> sth(0);
sth.do_tree(root());
}
// Save count before previous sweep and splits and coalesces.
! template <class Chunk_t, class FreeList_t>
class clearTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
void do_list(FreeList<Chunk_t>* fl) {}
#if INCLUDE_ALL_GCS
void do_list(AdaptiveFreeList<Chunk_t>* fl) {
*** 1190,1207 ****
fl->set_split_deaths(0);
}
#endif // INCLUDE_ALL_GCS
};
! template <class Chunk_t, template <class> class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::clear_tree_census(void) {
clearTreeCensusClosure<Chunk_t, FreeList_t> ctc;
ctc.do_tree(root());
}
// Do reporting and post sweep clean up.
! template <class Chunk_t, template <class> class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::end_sweep_dict_census(double splitSurplusPercent) {
// Does walking the tree 3 times hurt?
set_tree_surplus(splitSurplusPercent);
set_tree_hints();
if (PrintGC && Verbose) {
--- 1177,1194 ----
fl->set_split_deaths(0);
}
#endif // INCLUDE_ALL_GCS
};
! template <class Chunk_t, class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::clear_tree_census(void) {
clearTreeCensusClosure<Chunk_t, FreeList_t> ctc;
ctc.do_tree(root());
}
// Do reporting and post sweep clean up.
! template <class Chunk_t, class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::end_sweep_dict_census(double splitSurplusPercent) {
// Does walking the tree 3 times hurt?
set_tree_surplus(splitSurplusPercent);
set_tree_hints();
if (PrintGC && Verbose) {
*** 1209,1219 ****
}
clear_tree_census();
}
// Print summary statistics
! template <class Chunk_t, template <class> class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::report_statistics() const {
FreeBlockDictionary<Chunk_t>::verify_par_locked();
gclog_or_tty->print("Statistics for BinaryTreeDictionary:\n"
"------------------------------------\n");
size_t total_size = total_chunk_size(debug_only(NULL));
--- 1196,1206 ----
}
clear_tree_census();
}
// Print summary statistics
! template <class Chunk_t, class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::report_statistics() const {
FreeBlockDictionary<Chunk_t>::verify_par_locked();
gclog_or_tty->print("Statistics for BinaryTreeDictionary:\n"
"------------------------------------\n");
size_t total_size = total_chunk_size(debug_only(NULL));
*** 1228,1264 ****
}
// Print census information - counts, births, deaths, etc.
// for each list in the tree. Also print some summary
// information.
! template <class Chunk_t, template <class> class FreeList_t>
class PrintTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
int _print_line;
size_t _total_free;
! FreeList_t<Chunk_t> _total;
public:
PrintTreeCensusClosure() {
_print_line = 0;
_total_free = 0;
}
! FreeList_t<Chunk_t>* total() { return &_total; }
size_t total_free() { return _total_free; }
void do_list(FreeList<Chunk_t>* fl) {
if (++_print_line >= 40) {
! FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, "size");
_print_line = 0;
}
fl->print_on(gclog_or_tty);
_total_free += fl->count() * fl->size() ;
total()->set_count( total()->count() + fl->count() );
}
#if INCLUDE_ALL_GCS
void do_list(AdaptiveFreeList<Chunk_t>* fl) {
if (++_print_line >= 40) {
! FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, "size");
_print_line = 0;
}
fl->print_on(gclog_or_tty);
_total_free += fl->count() * fl->size() ;
total()->set_count( total()->count() + fl->count() );
--- 1215,1251 ----
}
// Print census information - counts, births, deaths, etc.
// for each list in the tree. Also print some summary
// information.
! template <class Chunk_t, class FreeList_t>
class PrintTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
int _print_line;
size_t _total_free;
! FreeList_t _total;
public:
PrintTreeCensusClosure() {
_print_line = 0;
_total_free = 0;
}
! FreeList_t* total() { return &_total; }
size_t total_free() { return _total_free; }
void do_list(FreeList<Chunk_t>* fl) {
if (++_print_line >= 40) {
! FreeList_t::print_labels_on(gclog_or_tty, "size");
_print_line = 0;
}
fl->print_on(gclog_or_tty);
_total_free += fl->count() * fl->size() ;
total()->set_count( total()->count() + fl->count() );
}
#if INCLUDE_ALL_GCS
void do_list(AdaptiveFreeList<Chunk_t>* fl) {
if (++_print_line >= 40) {
! FreeList_t::print_labels_on(gclog_or_tty, "size");
_print_line = 0;
}
fl->print_on(gclog_or_tty);
_total_free += fl->count() * fl->size() ;
total()->set_count( total()->count() + fl->count() );
*** 1273,1301 ****
total()->set_split_deaths(total()->split_deaths() + fl->split_deaths());
}
#endif // INCLUDE_ALL_GCS
};
! template <class Chunk_t, template <class> class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_dict_census(void) const {
gclog_or_tty->print("\nBinaryTree\n");
! FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, "size");
PrintTreeCensusClosure<Chunk_t, FreeList_t> ptc;
ptc.do_tree(root());
! FreeList_t<Chunk_t>* total = ptc.total();
! FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, " ");
}
#if INCLUDE_ALL_GCS
template <>
void AFLBinaryTreeDictionary::print_dict_census(void) const {
gclog_or_tty->print("\nBinaryTree\n");
AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, "size");
! PrintTreeCensusClosure<FreeChunk, AdaptiveFreeList> ptc;
ptc.do_tree(root());
AdaptiveFreeList<FreeChunk>* total = ptc.total();
AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, " ");
total->print_on(gclog_or_tty, "TOTAL\t");
--- 1260,1288 ----
total()->set_split_deaths(total()->split_deaths() + fl->split_deaths());
}
#endif // INCLUDE_ALL_GCS
};
! template <class Chunk_t, class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_dict_census(void) const {
gclog_or_tty->print("\nBinaryTree\n");
! FreeList_t::print_labels_on(gclog_or_tty, "size");
PrintTreeCensusClosure<Chunk_t, FreeList_t> ptc;
ptc.do_tree(root());
! FreeList_t* total = ptc.total();
! FreeList_t::print_labels_on(gclog_or_tty, " ");
}
#if INCLUDE_ALL_GCS
template <>
void AFLBinaryTreeDictionary::print_dict_census(void) const {
gclog_or_tty->print("\nBinaryTree\n");
AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, "size");
! PrintTreeCensusClosure<FreeChunk, AdaptiveFreeList<FreeChunk> > ptc;
ptc.do_tree(root());
AdaptiveFreeList<FreeChunk>* total = ptc.total();
AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, " ");
total->print_on(gclog_or_tty, "TOTAL\t");
*** 1309,1331 ****
(double)(total->desired() - total->count())
/(total->desired() != 0 ? (double)total->desired() : 1.0));
}
#endif // INCLUDE_ALL_GCS
! template <class Chunk_t, template <class> class FreeList_t>
class PrintFreeListsClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
outputStream* _st;
int _print_line;
public:
PrintFreeListsClosure(outputStream* st) {
_st = st;
_print_line = 0;
}
! void do_list(FreeList_t<Chunk_t>* fl) {
if (++_print_line >= 40) {
! FreeList_t<Chunk_t>::print_labels_on(_st, "size");
_print_line = 0;
}
fl->print_on(gclog_or_tty);
size_t sz = fl->size();
for (Chunk_t* fc = fl->head(); fc != NULL;
--- 1296,1318 ----
(double)(total->desired() - total->count())
/(total->desired() != 0 ? (double)total->desired() : 1.0));
}
#endif // INCLUDE_ALL_GCS
! template <class Chunk_t, class FreeList_t>
class PrintFreeListsClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
outputStream* _st;
int _print_line;
public:
PrintFreeListsClosure(outputStream* st) {
_st = st;
_print_line = 0;
}
! void do_list(FreeList_t* fl) {
if (++_print_line >= 40) {
! FreeList_t::print_labels_on(_st, "size");
_print_line = 0;
}
fl->print_on(gclog_or_tty);
size_t sz = fl->size();
for (Chunk_t* fc = fl->head(); fc != NULL;
*** 1335,1365 ****
fc->cantCoalesce() ? "\t CC" : "");
}
}
};
! template <class Chunk_t, template <class> class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_free_lists(outputStream* st) const {
! FreeList_t<Chunk_t>::print_labels_on(st, "size");
PrintFreeListsClosure<Chunk_t, FreeList_t> pflc(st);
pflc.do_tree(root());
}
// Verify the following tree invariants:
// . _root has no parent
// . parent and child point to each other
// . each node's key correctly related to that of its child(ren)
! template <class Chunk_t, template <class> class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_tree() const {
guarantee(root() == NULL || total_free_blocks() == 0 ||
total_size() != 0, "_total_size should't be 0?");
guarantee(root() == NULL || root()->parent() == NULL, "_root shouldn't have parent");
verify_tree_helper(root());
}
! template <class Chunk_t, template <class> class FreeList_t>
size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_prev_free_ptrs(TreeList<Chunk_t, FreeList_t>* tl) {
size_t ct = 0;
for (Chunk_t* curFC = tl->head(); curFC != NULL; curFC = curFC->next()) {
ct++;
assert(curFC->prev() == NULL || curFC->prev()->is_free(),
--- 1322,1352 ----
fc->cantCoalesce() ? "\t CC" : "");
}
}
};
! template <class Chunk_t, class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_free_lists(outputStream* st) const {
! FreeList_t::print_labels_on(st, "size");
PrintFreeListsClosure<Chunk_t, FreeList_t> pflc(st);
pflc.do_tree(root());
}
// Verify the following tree invariants:
// . _root has no parent
// . parent and child point to each other
// . each node's key correctly related to that of its child(ren)
! template <class Chunk_t, class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_tree() const {
guarantee(root() == NULL || total_free_blocks() == 0 ||
total_size() != 0, "_total_size should't be 0?");
guarantee(root() == NULL || root()->parent() == NULL, "_root shouldn't have parent");
verify_tree_helper(root());
}
! template <class Chunk_t, class FreeList_t>
size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_prev_free_ptrs(TreeList<Chunk_t, FreeList_t>* tl) {
size_t ct = 0;
for (Chunk_t* curFC = tl->head(); curFC != NULL; curFC = curFC->next()) {
ct++;
assert(curFC->prev() == NULL || curFC->prev()->is_free(),
*** 1369,1379 ****
}
// Note: this helper is recursive rather than iterative, so use with
// caution on very deep trees; and watch out for stack overflow errors;
// In general, to be used only for debugging.
! template <class Chunk_t, template <class> class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_tree_helper(TreeList<Chunk_t, FreeList_t>* tl) const {
if (tl == NULL)
return;
guarantee(tl->size() != 0, "A list must has a size");
guarantee(tl->left() == NULL || tl->left()->parent() == tl,
--- 1356,1366 ----
}
// Note: this helper is recursive rather than iterative, so use with
// caution on very deep trees; and watch out for stack overflow errors;
// In general, to be used only for debugging.
! template <class Chunk_t, class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_tree_helper(TreeList<Chunk_t, FreeList_t>* tl) const {
if (tl == NULL)
return;
guarantee(tl->size() != 0, "A list must has a size");
guarantee(tl->left() == NULL || tl->left()->parent() == tl,
*** 1398,1424 ****
}
verify_tree_helper(tl->left());
verify_tree_helper(tl->right());
}
! template <class Chunk_t, template <class> class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify() const {
verify_tree();
guarantee(total_size() == total_size_in_tree(root()), "Total Size inconsistency");
}
! template class TreeList<Metablock, FreeList>;
! template class BinaryTreeDictionary<Metablock, FreeList>;
! template class TreeChunk<Metablock, FreeList>;
!
! template class TreeList<Metachunk, FreeList>;
! template class BinaryTreeDictionary<Metachunk, FreeList>;
! template class TreeChunk<Metachunk, FreeList>;
#if INCLUDE_ALL_GCS
// Explicitly instantiate these types for FreeChunk.
! template class TreeList<FreeChunk, AdaptiveFreeList>;
! template class BinaryTreeDictionary<FreeChunk, AdaptiveFreeList>;
! template class TreeChunk<FreeChunk, AdaptiveFreeList>;
#endif // INCLUDE_ALL_GCS
--- 1385,1411 ----
}
verify_tree_helper(tl->left());
verify_tree_helper(tl->right());
}
! template <class Chunk_t, class FreeList_t>
void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify() const {
verify_tree();
guarantee(total_size() == total_size_in_tree(root()), "Total Size inconsistency");
}
! template class TreeList<Metablock, FreeList<Metablock> >;
! template class BinaryTreeDictionary<Metablock, FreeList<Metablock> >;
! template class TreeChunk<Metablock, FreeList<Metablock> >;
!
! template class TreeList<Metachunk, FreeList<Metachunk> >;
! template class BinaryTreeDictionary<Metachunk, FreeList<Metachunk> >;
! template class TreeChunk<Metachunk, FreeList<Metachunk> >;
#if INCLUDE_ALL_GCS
// Explicitly instantiate these types for FreeChunk.
! template class TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >;
! template class BinaryTreeDictionary<FreeChunk, AdaptiveFreeList<FreeChunk> >;
! template class TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >;
#endif // INCLUDE_ALL_GCS