Mercurial > hg > truffle
diff src/share/vm/memory/binaryTreeDictionary.cpp @ 14521:29ccc4cbabca
Merge
author | Gilles Duboscq <duboscq@ssw.jku.at> |
---|---|
date | Wed, 12 Mar 2014 13:30:08 +0100 |
parents | aa8fab3bed11 |
children | 4ca6dc0799b6 |
line wrap: on
line diff
--- a/src/share/vm/memory/binaryTreeDictionary.cpp Tue Mar 11 15:34:06 2014 +0100 +++ b/src/share/vm/memory/binaryTreeDictionary.cpp Wed Mar 12 13:30:08 2014 +0100 @@ -44,19 +44,19 @@ // This is currently used in the Concurrent Mark&Sweep implementation. //////////////////////////////////////////////////////////////////////////////// -template <class Chunk_t, template <class> class FreeList_t> +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, template <class> class FreeList_t> +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, template <class> class FreeList_t> +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'r have tree fields + 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"); } @@ -67,11 +67,11 @@ } } -template <class Chunk_t, template <class> class FreeList_t> +template <class Chunk_t, class FreeList_t> TreeList<Chunk_t, FreeList_t>::TreeList() : _parent(NULL), _left(NULL), _right(NULL) {} -template <class Chunk_t, template <class> class FreeList_t> +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. @@ -88,20 +88,7 @@ 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> +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; @@ -125,17 +112,17 @@ // 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) { +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>* curTL = this; + 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>* hintTL = this; + TreeList<FreeChunk, ::AdaptiveFreeList<FreeChunk> >* hintTL = this; while (hintTL->hint() != 0) { assert(hintTL->hint() > hintTL->size(), "hint points in the wrong direction"); @@ -163,14 +150,14 @@ } #endif // INCLUDE_ALL_GCS -template <class Chunk_t, template <class> class FreeList_t> +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, template <class> class FreeList_t> +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; @@ -247,7 +234,7 @@ prevFC->link_after(nextTC); } - // Below this point the embeded TreeList<Chunk_t, FreeList_t> being used for the + // Below this point the embedded TreeList<Chunk_t, FreeList_t> being used for the // tree node may have changed. Don't use "this" // TreeList<Chunk_t, FreeList_t>*. // chunk should still be a free chunk (bit set in _prev) @@ -286,7 +273,7 @@ return retTL; } -template <class Chunk_t, template <class> class FreeList_t> +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"); @@ -301,7 +288,7 @@ this->link_tail(chunk); assert(!tail() || size() == tail()->size(), "Wrong sized chunk in list"); - FreeList_t<Chunk_t>::increment_count(); + 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"); @@ -311,7 +298,7 @@ // 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> +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"); @@ -329,13 +316,13 @@ } head()->link_after(chunk); assert(!head() || size() == head()->size(), "Wrong sized chunk in list"); - FreeList_t<Chunk_t>::increment_count(); + 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, template <class> class FreeList_t> +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()) && @@ -345,14 +332,14 @@ "Space should be clear or mangled"); } -template <class Chunk_t, template <class> class FreeList_t> +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, template <class> class FreeList_t> +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(); @@ -369,7 +356,7 @@ // 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> +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(); @@ -392,7 +379,7 @@ return retTC; } -template <class Chunk_t, template <class> class FreeList_t> +template <class Chunk_t, class FreeList_t> BinaryTreeDictionary<Chunk_t, FreeList_t>::BinaryTreeDictionary(MemRegion mr) { assert((mr.byte_size() > min_size()), "minimum chunk size"); @@ -405,17 +392,17 @@ assert(total_free_blocks() == 1, "reset check failed"); } -template <class Chunk_t, template <class> class FreeList_t> +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, template <class> class FreeList_t> +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, template <class> class FreeList_t> +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())); @@ -423,13 +410,13 @@ set_total_free_blocks(1); } -template <class Chunk_t, template <class> class FreeList_t> +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, template <class> class FreeList_t> +template <class Chunk_t, class FreeList_t> void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset() { set_root(NULL); set_total_size(0); @@ -437,7 +424,7 @@ } // Get a free block of size at least size from tree, or NULL. -template <class Chunk_t, template <class> class FreeList_t> +template <class Chunk_t, class FreeList_t> TreeChunk<Chunk_t, FreeList_t>* BinaryTreeDictionary<Chunk_t, FreeList_t>::get_chunk_from_tree( size_t size, @@ -496,7 +483,7 @@ return retTC; } -template <class Chunk_t, template <class> class FreeList_t> +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;) { @@ -515,7 +502,7 @@ } -template <class Chunk_t, template <class> class FreeList_t> +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); @@ -526,7 +513,7 @@ } } -template <class Chunk_t, template <class> class FreeList_t> +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) { @@ -541,7 +528,7 @@ // 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> +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"); @@ -682,7 +669,7 @@ // 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> +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 @@ -703,7 +690,7 @@ // The only use of this method would not pass the root of the // tree (as indicated by the assertion above that the tree list // has a parent) but the specification does not explicitly exclude the - // passing of the root so accomodate it. + // passing of the root so accommodate it. set_root(NULL); } debug_only( @@ -717,7 +704,7 @@ return curTL; } -template <class Chunk_t, template <class> class FreeList_t> +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(); @@ -783,7 +770,7 @@ } } -template <class Chunk_t, template <class> class FreeList_t> +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(); @@ -792,7 +779,7 @@ return tc->size(); } -template <class Chunk_t, template <class> class FreeList_t> +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(); @@ -805,7 +792,7 @@ return res; } -template <class Chunk_t, template <class> class FreeList_t> +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; @@ -814,7 +801,7 @@ total_size_in_tree(tl->right()); } -template <class Chunk_t, template <class> class FreeList_t> +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; @@ -826,7 +813,7 @@ return curr; } -template <class Chunk_t, template <class> class FreeList_t> +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; @@ -835,14 +822,14 @@ total_free_blocks_in_tree(tl->right()); } -template <class Chunk_t, template <class> class FreeList_t> +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, template <class> class FreeList_t> +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; @@ -850,12 +837,12 @@ tree_height_helper(tl->right())); } -template <class Chunk_t, template <class> class FreeList_t> +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, template <class> class FreeList_t> +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; @@ -864,18 +851,18 @@ total_nodes_helper(tl->right()); } -template <class Chunk_t, template <class> class FreeList_t> +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, template <class> class FreeList_t> +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>* nd = find_list(size); +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) { @@ -903,7 +890,7 @@ } #endif // INCLUDE_ALL_GCS -template <class Chunk_t, template <class> class FreeList_t> +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. @@ -915,7 +902,7 @@ bool AFLBinaryTreeDictionary::coal_dict_over_populated(size_t size) { if (FLSAlwaysCoalesceLarge) return true; - TreeList<FreeChunk, AdaptiveFreeList>* list_of_size = find_list(size); + 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(); @@ -928,15 +915,15 @@ // 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> +template <class Chunk_t, class FreeList_t> class TreeCensusClosure : public StackObj { protected: - virtual void do_list(FreeList_t<Chunk_t>* fl) = 0; + virtual void do_list(FreeList_t* fl) = 0; public: virtual void do_tree(TreeList<Chunk_t, FreeList_t>* tl) = 0; }; -template <class Chunk_t, template <class> class FreeList_t> +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) { @@ -948,7 +935,7 @@ } }; -template <class Chunk_t, template <class> class FreeList_t> +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) { @@ -962,7 +949,7 @@ // 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> +template <class Chunk_t, class FreeList_t> class BeginSweepClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { double _percentage; float _inter_sweep_current; @@ -995,16 +982,16 @@ // Similar to TreeCensusClosure but searches the // tree and returns promptly when found. -template <class Chunk_t, template <class> class FreeList_t> +template <class Chunk_t, class FreeList_t> class TreeSearchClosure : public StackObj { protected: - virtual bool do_list(FreeList_t<Chunk_t>* fl) = 0; + 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, template <class> class FreeList_t> +template <class Chunk_t, class FreeList_t> class AscendTreeSearchClosure : public TreeSearchClosure<Chunk_t> { public: bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) { @@ -1018,7 +1005,7 @@ }; #endif -template <class Chunk_t, template <class> class FreeList_t> +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) { @@ -1033,14 +1020,14 @@ // Searches the tree for a chunk that ends at the // specified address. -template <class Chunk_t, template <class> class FreeList_t> +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<Chunk_t>* fl) { + bool do_list(FreeList_t* fl) { Chunk_t* item = fl->head(); while (item != NULL) { if (item->end() == (uintptr_t*) _target) { @@ -1054,7 +1041,7 @@ Chunk_t* found() { return _found; } }; -template <class Chunk_t, template <class> class FreeList_t> +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()); @@ -1063,7 +1050,7 @@ return etsc.found(); } -template <class Chunk_t, template <class> class FreeList_t> +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, @@ -1075,32 +1062,32 @@ // 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> +template <class Chunk_t, class FreeList_t> class InitializeDictReturnedBytesClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { public: - void do_list(FreeList_t<Chunk_t>* fl) { + void do_list(FreeList_t* fl) { fl->set_returned_bytes(0); } }; -template <class Chunk_t, template <class> class FreeList_t> +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, template <class> class FreeList_t> +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<Chunk_t>* fl) { + 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, template <class> class FreeList_t> +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()); @@ -1109,17 +1096,17 @@ } // Count the number of entries in the tree. -template <class Chunk_t, template <class> class FreeList_t> +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<Chunk_t>* fl) { + void do_list(FreeList_t* fl) { count++; } }; -template <class Chunk_t, template <class> class FreeList_t> +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()); @@ -1128,7 +1115,7 @@ #endif // PRODUCT // Calculate surpluses for the lists in the tree. -template <class Chunk_t, template <class> class FreeList_t> +template <class Chunk_t, class FreeList_t> class setTreeSurplusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { double percentage; public: @@ -1144,14 +1131,14 @@ #endif // INCLUDE_ALL_GCS }; -template <class Chunk_t, template <class> class FreeList_t> +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, template <class> class FreeList_t> +template <class Chunk_t, class FreeList_t> class setTreeHintsClosure : public DescendTreeCensusClosure<Chunk_t, FreeList_t> { size_t hint; public: @@ -1170,14 +1157,14 @@ #endif // INCLUDE_ALL_GCS }; -template <class Chunk_t, template <class> class FreeList_t> +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, template <class> class FreeList_t> +template <class Chunk_t, class FreeList_t> class clearTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { void do_list(FreeList<Chunk_t>* fl) {} @@ -1192,14 +1179,14 @@ #endif // INCLUDE_ALL_GCS }; -template <class Chunk_t, template <class> class FreeList_t> +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, template <class> class FreeList_t> +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); @@ -1211,7 +1198,7 @@ } // Print summary statistics -template <class Chunk_t, template <class> class FreeList_t> +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" @@ -1230,22 +1217,22 @@ // 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> +template <class Chunk_t, class FreeList_t> class PrintTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { int _print_line; size_t _total_free; - FreeList_t<Chunk_t> _total; + FreeList_t _total; public: PrintTreeCensusClosure() { _print_line = 0; _total_free = 0; } - FreeList_t<Chunk_t>* total() { return &_total; } + 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<Chunk_t>::print_labels_on(gclog_or_tty, "size"); + FreeList_t::print_labels_on(gclog_or_tty, "size"); _print_line = 0; } fl->print_on(gclog_or_tty); @@ -1256,7 +1243,7 @@ #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"); + FreeList_t::print_labels_on(gclog_or_tty, "size"); _print_line = 0; } fl->print_on(gclog_or_tty); @@ -1275,16 +1262,16 @@ #endif // INCLUDE_ALL_GCS }; -template <class Chunk_t, template <class> class FreeList_t> +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<Chunk_t>::print_labels_on(gclog_or_tty, "size"); + FreeList_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, " "); + FreeList_t* total = ptc.total(); + FreeList_t::print_labels_on(gclog_or_tty, " "); } #if INCLUDE_ALL_GCS @@ -1293,7 +1280,7 @@ gclog_or_tty->print("\nBinaryTree\n"); AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, "size"); - PrintTreeCensusClosure<FreeChunk, AdaptiveFreeList> ptc; + PrintTreeCensusClosure<FreeChunk, AdaptiveFreeList<FreeChunk> > ptc; ptc.do_tree(root()); AdaptiveFreeList<FreeChunk>* total = ptc.total(); @@ -1311,7 +1298,7 @@ } #endif // INCLUDE_ALL_GCS -template <class Chunk_t, template <class> class FreeList_t> +template <class Chunk_t, class FreeList_t> class PrintFreeListsClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { outputStream* _st; int _print_line; @@ -1321,9 +1308,9 @@ _st = st; _print_line = 0; } - void do_list(FreeList_t<Chunk_t>* fl) { + void do_list(FreeList_t* fl) { if (++_print_line >= 40) { - FreeList_t<Chunk_t>::print_labels_on(_st, "size"); + FreeList_t::print_labels_on(_st, "size"); _print_line = 0; } fl->print_on(gclog_or_tty); @@ -1337,10 +1324,10 @@ } }; -template <class Chunk_t, template <class> class FreeList_t> +template <class Chunk_t, class FreeList_t> void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_free_lists(outputStream* st) const { - FreeList_t<Chunk_t>::print_labels_on(st, "size"); + FreeList_t::print_labels_on(st, "size"); PrintFreeListsClosure<Chunk_t, FreeList_t> pflc(st); pflc.do_tree(root()); } @@ -1349,15 +1336,15 @@ // . _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> +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?"); + total_size() != 0, "_total_size shouldn'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> +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()) { @@ -1371,7 +1358,7 @@ // 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> +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; @@ -1400,25 +1387,25 @@ verify_tree_helper(tl->right()); } -template <class Chunk_t, template <class> class FreeList_t> +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>; -template class BinaryTreeDictionary<Metablock, FreeList>; -template class TreeChunk<Metablock, FreeList>; +template class TreeList<Metablock, FreeList<Metablock> >; +template class BinaryTreeDictionary<Metablock, FreeList<Metablock> >; +template class TreeChunk<Metablock, FreeList<Metablock> >; -template class TreeList<Metachunk, FreeList>; -template class BinaryTreeDictionary<Metachunk, FreeList>; -template class TreeChunk<Metachunk, FreeList>; +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>; -template class BinaryTreeDictionary<FreeChunk, AdaptiveFreeList>; -template class TreeChunk<FreeChunk, AdaptiveFreeList>; +template class TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >; +template class BinaryTreeDictionary<FreeChunk, AdaptiveFreeList<FreeChunk> >; +template class TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >; #endif // INCLUDE_ALL_GCS