39 #include "gc_implementation/concurrentMarkSweep/freeChunk.hpp"
40 #endif // INCLUDE_ALL_GCS
41
42 ////////////////////////////////////////////////////////////////////////////////
43 // A binary tree based search structure for free blocks.
44 // This is currently used in the Concurrent Mark&Sweep implementation.
45 ////////////////////////////////////////////////////////////////////////////////
46
47 template <class Chunk_t, template <class> class FreeList_t>
48 size_t TreeChunk<Chunk_t, FreeList_t>::_min_tree_chunk_size = sizeof(TreeChunk<Chunk_t, FreeList_t>)/HeapWordSize;
49
50 template <class Chunk_t, template <class> class FreeList_t>
51 TreeChunk<Chunk_t, FreeList_t>* TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(Chunk_t* fc) {
52 // Do some assertion checking here.
53 return (TreeChunk<Chunk_t, FreeList_t>*) fc;
54 }
55
56 template <class Chunk_t, template <class> class FreeList_t>
57 void TreeChunk<Chunk_t, FreeList_t>::verify_tree_chunk_list() const {
58 TreeChunk<Chunk_t, FreeList_t>* nextTC = (TreeChunk<Chunk_t, FreeList_t>*)next();
59 if (prev() != NULL) { // interior list node shouldn'r have tree fields
60 guarantee(embedded_list()->parent() == NULL && embedded_list()->left() == NULL &&
61 embedded_list()->right() == NULL, "should be clear");
62 }
63 if (nextTC != NULL) {
64 guarantee(as_TreeChunk(nextTC->prev()) == this, "broken chain");
65 guarantee(nextTC->size() == size(), "wrong size");
66 nextTC->verify_tree_chunk_list();
67 }
68 }
69
70 template <class Chunk_t, template <class> class FreeList_t>
71 TreeList<Chunk_t, FreeList_t>::TreeList() : _parent(NULL),
72 _left(NULL), _right(NULL) {}
73
74 template <class Chunk_t, template <class> class FreeList_t>
75 TreeList<Chunk_t, FreeList_t>*
76 TreeList<Chunk_t, FreeList_t>::as_TreeList(TreeChunk<Chunk_t,FreeList_t>* tc) {
77 // This first free chunk in the list will be the tree list.
78 assert((tc->size() >= (TreeChunk<Chunk_t, FreeList_t>::min_size())),
79 "Chunk is too small for a TreeChunk");
230 assert(right() == retTL->right(), "Should have been copied");
231 if (retTL->right() != NULL) {
232 retTL->right()->set_parent(retTL);
233 }
234 assert(left() == retTL->left(), "Should have been copied");
235 if (retTL->left() != NULL) {
236 retTL->left()->set_parent(retTL);
237 }
238 retTL->link_head(nextTC);
239 assert(nextTC->is_free(), "Should be a free chunk");
240 }
241 } else {
242 if (nextTC == NULL) {
243 // Removing chunk at tail of list
244 this->link_tail(prevFC);
245 }
246 // Chunk is interior to the list
247 prevFC->link_after(nextTC);
248 }
249
250 // Below this point the embeded TreeList<Chunk_t, FreeList_t> being used for the
251 // tree node may have changed. Don't use "this"
252 // TreeList<Chunk_t, FreeList_t>*.
253 // chunk should still be a free chunk (bit set in _prev)
254 assert(!retTL->head() || retTL->size() == retTL->head()->size(),
255 "Wrong sized chunk in list");
256 debug_only(
257 tc->link_prev(NULL);
258 tc->link_next(NULL);
259 tc->set_list(NULL);
260 bool prev_found = false;
261 bool next_found = false;
262 for (Chunk_t* curFC = retTL->head();
263 curFC != NULL; curFC = curFC->next()) {
264 assert(curFC != tc, "Chunk is still in list");
265 if (curFC == prevFC) {
266 prev_found = true;
267 }
268 if (curFC == nextTC) {
269 next_found = true;
270 }
686 TreeList<Chunk_t, FreeList_t>* BinaryTreeDictionary<Chunk_t, FreeList_t>::remove_tree_minimum(TreeList<Chunk_t, FreeList_t>* tl) {
687 assert(tl != NULL && tl->parent() != NULL, "really need a proper sub-tree");
688 // locate the subtree minimum by walking down left branches
689 TreeList<Chunk_t, FreeList_t>* curTL = tl;
690 for (; curTL->left() != NULL; curTL = curTL->left());
691 // obviously curTL now has at most one child, a right child
692 if (curTL != root()) { // Should this test just be removed?
693 TreeList<Chunk_t, FreeList_t>* parentTL = curTL->parent();
694 if (parentTL->left() == curTL) { // curTL is a left child
695 parentTL->set_left(curTL->right());
696 } else {
697 // If the list tl has no left child, then curTL may be
698 // the right child of parentTL.
699 assert(parentTL->right() == curTL, "should be a right child");
700 parentTL->set_right(curTL->right());
701 }
702 } else {
703 // The only use of this method would not pass the root of the
704 // tree (as indicated by the assertion above that the tree list
705 // has a parent) but the specification does not explicitly exclude the
706 // passing of the root so accomodate it.
707 set_root(NULL);
708 }
709 debug_only(
710 curTL->clear_parent(); // Test if this needs to be cleared
711 curTL->clear_right(); // recall, above, left child is already null
712 )
713 // we just excised a (non-root) node, we should still verify all tree invariants
714 if (FLSVerifyDictionary) {
715 verify_tree();
716 }
717 return curTL;
718 }
719
720 template <class Chunk_t, template <class> class FreeList_t>
721 void BinaryTreeDictionary<Chunk_t, FreeList_t>::insert_chunk_in_tree(Chunk_t* fc) {
722 TreeList<Chunk_t, FreeList_t> *curTL, *prevTL;
723 size_t size = fc->size();
724
725 assert((size >= min_size()),
726 err_msg(SIZE_FORMAT " is too small to be a TreeChunk<Chunk_t, FreeList_t> " SIZE_FORMAT,
|
39 #include "gc_implementation/concurrentMarkSweep/freeChunk.hpp"
40 #endif // INCLUDE_ALL_GCS
41
42 ////////////////////////////////////////////////////////////////////////////////
43 // A binary tree based search structure for free blocks.
44 // This is currently used in the Concurrent Mark&Sweep implementation.
45 ////////////////////////////////////////////////////////////////////////////////
46
47 template <class Chunk_t, template <class> class FreeList_t>
48 size_t TreeChunk<Chunk_t, FreeList_t>::_min_tree_chunk_size = sizeof(TreeChunk<Chunk_t, FreeList_t>)/HeapWordSize;
49
50 template <class Chunk_t, template <class> class FreeList_t>
51 TreeChunk<Chunk_t, FreeList_t>* TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(Chunk_t* fc) {
52 // Do some assertion checking here.
53 return (TreeChunk<Chunk_t, FreeList_t>*) fc;
54 }
55
56 template <class Chunk_t, template <class> class FreeList_t>
57 void TreeChunk<Chunk_t, FreeList_t>::verify_tree_chunk_list() const {
58 TreeChunk<Chunk_t, FreeList_t>* nextTC = (TreeChunk<Chunk_t, FreeList_t>*)next();
59 if (prev() != NULL) { // interior list node shouldn't have tree fields
60 guarantee(embedded_list()->parent() == NULL && embedded_list()->left() == NULL &&
61 embedded_list()->right() == NULL, "should be clear");
62 }
63 if (nextTC != NULL) {
64 guarantee(as_TreeChunk(nextTC->prev()) == this, "broken chain");
65 guarantee(nextTC->size() == size(), "wrong size");
66 nextTC->verify_tree_chunk_list();
67 }
68 }
69
70 template <class Chunk_t, template <class> class FreeList_t>
71 TreeList<Chunk_t, FreeList_t>::TreeList() : _parent(NULL),
72 _left(NULL), _right(NULL) {}
73
74 template <class Chunk_t, template <class> class FreeList_t>
75 TreeList<Chunk_t, FreeList_t>*
76 TreeList<Chunk_t, FreeList_t>::as_TreeList(TreeChunk<Chunk_t,FreeList_t>* tc) {
77 // This first free chunk in the list will be the tree list.
78 assert((tc->size() >= (TreeChunk<Chunk_t, FreeList_t>::min_size())),
79 "Chunk is too small for a TreeChunk");
230 assert(right() == retTL->right(), "Should have been copied");
231 if (retTL->right() != NULL) {
232 retTL->right()->set_parent(retTL);
233 }
234 assert(left() == retTL->left(), "Should have been copied");
235 if (retTL->left() != NULL) {
236 retTL->left()->set_parent(retTL);
237 }
238 retTL->link_head(nextTC);
239 assert(nextTC->is_free(), "Should be a free chunk");
240 }
241 } else {
242 if (nextTC == NULL) {
243 // Removing chunk at tail of list
244 this->link_tail(prevFC);
245 }
246 // Chunk is interior to the list
247 prevFC->link_after(nextTC);
248 }
249
250 // Below this point the embedded TreeList<Chunk_t, FreeList_t> being used for the
251 // tree node may have changed. Don't use "this"
252 // TreeList<Chunk_t, FreeList_t>*.
253 // chunk should still be a free chunk (bit set in _prev)
254 assert(!retTL->head() || retTL->size() == retTL->head()->size(),
255 "Wrong sized chunk in list");
256 debug_only(
257 tc->link_prev(NULL);
258 tc->link_next(NULL);
259 tc->set_list(NULL);
260 bool prev_found = false;
261 bool next_found = false;
262 for (Chunk_t* curFC = retTL->head();
263 curFC != NULL; curFC = curFC->next()) {
264 assert(curFC != tc, "Chunk is still in list");
265 if (curFC == prevFC) {
266 prev_found = true;
267 }
268 if (curFC == nextTC) {
269 next_found = true;
270 }
686 TreeList<Chunk_t, FreeList_t>* BinaryTreeDictionary<Chunk_t, FreeList_t>::remove_tree_minimum(TreeList<Chunk_t, FreeList_t>* tl) {
687 assert(tl != NULL && tl->parent() != NULL, "really need a proper sub-tree");
688 // locate the subtree minimum by walking down left branches
689 TreeList<Chunk_t, FreeList_t>* curTL = tl;
690 for (; curTL->left() != NULL; curTL = curTL->left());
691 // obviously curTL now has at most one child, a right child
692 if (curTL != root()) { // Should this test just be removed?
693 TreeList<Chunk_t, FreeList_t>* parentTL = curTL->parent();
694 if (parentTL->left() == curTL) { // curTL is a left child
695 parentTL->set_left(curTL->right());
696 } else {
697 // If the list tl has no left child, then curTL may be
698 // the right child of parentTL.
699 assert(parentTL->right() == curTL, "should be a right child");
700 parentTL->set_right(curTL->right());
701 }
702 } else {
703 // The only use of this method would not pass the root of the
704 // tree (as indicated by the assertion above that the tree list
705 // has a parent) but the specification does not explicitly exclude the
706 // passing of the root so accommodate it.
707 set_root(NULL);
708 }
709 debug_only(
710 curTL->clear_parent(); // Test if this needs to be cleared
711 curTL->clear_right(); // recall, above, left child is already null
712 )
713 // we just excised a (non-root) node, we should still verify all tree invariants
714 if (FLSVerifyDictionary) {
715 verify_tree();
716 }
717 return curTL;
718 }
719
720 template <class Chunk_t, template <class> class FreeList_t>
721 void BinaryTreeDictionary<Chunk_t, FreeList_t>::insert_chunk_in_tree(Chunk_t* fc) {
722 TreeList<Chunk_t, FreeList_t> *curTL, *prevTL;
723 size_t size = fc->size();
724
725 assert((size >= min_size()),
726 err_msg(SIZE_FORMAT " is too small to be a TreeChunk<Chunk_t, FreeList_t> " SIZE_FORMAT,
|