src/share/vm/memory/binaryTreeDictionary.cpp

Print this page
rev 5878 : 8034171: Remove use of template template parameters from binaryTreeDictionary.
Contributed-by: Matthias.Baesken@sap.com

*** 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