691 // passing of the root so accommodate it.
692 set_root(NULL);
693 }
694 debug_only(
695 curTL->clear_parent(); // Test if this needs to be cleared
696 curTL->clear_right(); // recall, above, left child is already null
697 )
698 // we just excised a (non-root) node, we should still verify all tree invariants
699 if (FLSVerifyDictionary) {
700 verify_tree();
701 }
702 return curTL;
703 }
704
705 template <class Chunk_t, class FreeList_t>
706 void BinaryTreeDictionary<Chunk_t, FreeList_t>::insert_chunk_in_tree(Chunk_t* fc) {
707 TreeList<Chunk_t, FreeList_t> *curTL, *prevTL;
708 size_t size = fc->size();
709
710 assert((size >= min_size()),
711 err_msg(SIZE_FORMAT " is too small to be a TreeChunk<Chunk_t, FreeList_t> " SIZE_FORMAT,
712 size, min_size()));
713 if (FLSVerifyDictionary) {
714 verify_tree();
715 }
716
717 fc->clear_next();
718 fc->link_prev(NULL);
719
720 // work down from the _root, looking for insertion point
721 for (prevTL = curTL = root(); curTL != NULL;) {
722 if (curTL->size() == size) // exact match
723 break;
724 prevTL = curTL;
725 if (curTL->size() > size) { // follow left branch
726 curTL = curTL->left();
727 } else { // follow right branch
728 assert(curTL->size() < size, "size inconsistency");
729 curTL = curTL->right();
730 }
731 }
732 TreeChunk<Chunk_t, FreeList_t>* tc = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(fc);
|
691 // passing of the root so accommodate it.
692 set_root(NULL);
693 }
694 debug_only(
695 curTL->clear_parent(); // Test if this needs to be cleared
696 curTL->clear_right(); // recall, above, left child is already null
697 )
698 // we just excised a (non-root) node, we should still verify all tree invariants
699 if (FLSVerifyDictionary) {
700 verify_tree();
701 }
702 return curTL;
703 }
704
705 template <class Chunk_t, class FreeList_t>
706 void BinaryTreeDictionary<Chunk_t, FreeList_t>::insert_chunk_in_tree(Chunk_t* fc) {
707 TreeList<Chunk_t, FreeList_t> *curTL, *prevTL;
708 size_t size = fc->size();
709
710 assert((size >= min_size()),
711 SIZE_FORMAT " is too small to be a TreeChunk<Chunk_t, FreeList_t> " SIZE_FORMAT,
712 size, min_size());
713 if (FLSVerifyDictionary) {
714 verify_tree();
715 }
716
717 fc->clear_next();
718 fc->link_prev(NULL);
719
720 // work down from the _root, looking for insertion point
721 for (prevTL = curTL = root(); curTL != NULL;) {
722 if (curTL->size() == size) // exact match
723 break;
724 prevTL = curTL;
725 if (curTL->size() > size) { // follow left branch
726 curTL = curTL->left();
727 } else { // follow right branch
728 assert(curTL->size() < size, "size inconsistency");
729 curTL = curTL->right();
730 }
731 }
732 TreeChunk<Chunk_t, FreeList_t>* tc = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(fc);
|