binaryTreeDictionary.cpp revision 3697
3695N/A * Copyright (c) 2001, 2012, Oracle and/or its affiliates. All rights reserved. 0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 0N/A * This code is free software; you can redistribute it and/or modify it 0N/A * under the terms of the GNU General Public License version 2 only, as 0N/A * published by the Free Software Foundation. 0N/A * This code is distributed in the hope that it will be useful, but WITHOUT 0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 0N/A * version 2 for more details (a copy is included in the LICENSE file that 0N/A * accompanied this code). 0N/A * You should have received a copy of the GNU General Public License version 0N/A * 2 along with this work; if not, write to the Free Software Foundation, 0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 1472N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 0N/A//////////////////////////////////////////////////////////////////////////////// 0N/A// A binary tree based search structure for free blocks. 0N/A// This is currently used in the Concurrent Mark&Sweep implementation. 0N/A//////////////////////////////////////////////////////////////////////////////// 0N/A // Do some assertion checking here. 0N/A if (
prev() !=
NULL) {
// interior list node shouldn'r have tree fields 0N/A // This first free chunk in the list will be the tree list. 263N/A // The space in the heap will have been mangled initially but 263N/A // is not remangled when a free chunk is returned to the free list 263N/A // (since it is used to maintain the chunk on the free list). 263N/A "Space should be clear or mangled");
0N/A // Is this the first item on the list? 3695N/A // The "getChunk..." functions for a TreeList<Chunk> will not return the 0N/A // first chunk in the list unless it is the last chunk in the list 0N/A // because the first chunk is also acting as the tree node. 0N/A // When coalescing happens, however, the first chunk in the a tree 0N/A // list can be the start of a free range. Free ranges are removed 0N/A // from the free lists so that they are not available to be 0N/A // allocated when the sweeper yields (giving up the free list lock) 0N/A // to allow mutator activity. If this chunk is the first in the 0N/A // list and is not the last in the list, do the work to copy the 3695N/A // TreeList<Chunk> from the first chunk to the next chunk and update all 3695N/A // the TreeList<Chunk> pointers in the chunks in the list. 0N/A // copy embedded list. 0N/A // Fix the pointer to the list in each chunk in the list. 0N/A // This can be slow for a long list. Consider having 0N/A // an option that does not allow the first chunk on the 0N/A // list to be coalesced. 3695N/A // Fix the parent to point to the new TreeList<Chunk>. 0N/A // Fix the children's parent pointers to point to the 0N/A // Removing chunk at tail of list 0N/A // Chunk is interior to the list 3695N/A // Below this point the embeded TreeList<Chunk> being used for the 0N/A // tree node may have changed. Don't use "this" 0N/A // chunk should still be a free chunk (bit set in _prev) 0N/A "Wrong sized chunk in list");
0N/A "list is inconsistent");
0N/A // which means that the list can never be empty. 0N/A// Add this chunk at the head of the list. "At the head of the list" 0N/A// is defined to be after the chunk pointer to by head(). This is 3695N/A// because the TreeList<Chunk> is embedded in the first TreeChunk<Chunk> in the 3695N/A// list. See the definition of TreeChunk<Chunk>. 0N/A "Wrong type of chunk?");
1145N/A// Returns the block with the largest heap address amongst 1145N/A// those in the list for this size; potentially slow and expensive, 1145N/A // walk down the list and return the one with the highest 1145N/A // heap address among chunks of this size. 0N/A// Get a free block of size at least size from tree, or NULL. 0N/A// If a splay step is requested, the removal algorithm (only) incorporates 0N/A// a splay step as follows: 0N/A// . the search proceeds down the tree looking for a possible 0N/A// match. At the (closest) matching location, an appropriate splay step is applied 0N/A// (zig, zig-zig or zig-zag). A chunk of the appropriate size is then returned 0N/A// if available, and if it's the last chunk, the node is deleted. A deteleted 0N/A// node is replaced in place by its tree successor. 0N/A // starting at the root, work downwards trying to find match. 0N/A // Remember the last node of size too great or too small. 0N/A }
else {
// proceed to left sub-tree 0N/A // try and find the next larger size by walking back up the search path 0N/A "An empty list should not be in the tree");
0N/A // A candidate chunk has been found. If it is already under 0N/A // populated, get a chunk associated with the hint for this 0N/A /* Use the hint to find a size with a surplus, and reset the hint. */ 0N/A "hint points in the wrong direction");
0N/A // No useful hint. Set the hint to NULL and go on. 0N/A // The hint led to a list that has a surplus. Use it. 0N/A // Set the hint for the candidate to an overpopulated 0N/A // Change the candidate. 0N/A // The evm code reset the hint of the candidate as 1145N/A // at an interim point. Why? Seems like this leaves 0N/A // the hint pointing to a list that didn't work. 0N/A // curTL->set_hint(hintTL->size()); 0N/A // don't waste time splaying if chunk's singleton 0N/A "A list in the binary tree should not be NULL");
0N/A "A chunk of the wrong size was found");
0N/A }
else {
// proceed to left sub-tree 0N/A// Remove the current chunk from the tree. If it is not the last 0N/A// chunk in a list on a tree node, just unlink it. 0N/A// If it is the last chunk in the list (the next link is NULL), 0N/A// remove the node and repair the tree. 0N/A // Removing this chunk can have the side effect of changing the node 3695N/A // (TreeList<Chunk>*) in the tree. If the node is the root, update it. 0N/A "list is inconsistent");
0N/A "If the tree list was replaced, it should not be a NULL list");
0N/A // Does the tree need to be repaired? 0N/A // Find the replacement node for the (soon to be empty) node being removed. 0N/A // if we have a single (or no) child, splice child in our stead 0N/A // left is NULL so pick right. right may also be NULL. 0N/A }
else {
// we have both children, so, by patriarchal convention, 0N/A // my replacement is least node in right sub-tree 0N/A // newTL is the replacement for the (soon to be empty) node. 0N/A // newTL may be NULL. 0N/A // should verify; we just cleanly excised our replacement 0N/A // first make newTL my parent's child 0N/A // newTL should be root 0N/A // replacementTL is a right child 0N/A }
else {
// replacementTL is a left child 0N/A "newTL should not have encumbrances from the past");
0N/A // we'd like to assert as below: 0N/A // assert(replacementTL->left() != NULL && replacementTL->right() != NULL, 3697N/A // "else !complicated_splice"); 0N/A // ... however, the above assertion is too strong because we aren't 0N/A // guaranteed that replacementTL->right() is still NULL. 0N/A // Recall that we removed 0N/A // the right sub-tree minimum from replacementTL. 0N/A // That may well have been its right 0N/A // child! So we'll just assert half of the above: 0N/A "delete without encumbrances");
0N/A "should return without encumbrances");
0N/A// Remove the leftmost node (lm) in the tree and return it. 0N/A// If lm has a right child, link it to the left node of 0N/A // locate the subtree minimum by walking down left branches 0N/A // obviously curTL now has at most one child, a right child 0N/A // If the list tl has no left child, then curTL may be 0N/A // the right child of parentTL. 0N/A // The only use of this method would not pass the root of the 0N/A // tree (as indicated by the assertion above that the tree list 0N/A // has a parent) but the specification does not explicitly exclude the 0N/A // passing of the root so accomodate it. 0N/A // we just excised a (non-root) node, we should still verify all tree invariants 0N/A// Based on a simplification of the algorithm by Sleator and Tarjan (JACM 1985). 0N/A// The simplifications are the following: 0N/A// . we splay only when we delete (not when we insert) 0N/A// By doing such partial splaying, we reduce the amount of restructuring, 0N/A// while getting a reasonably efficient search tree (we think). 0N/A// [Measurements will be needed to (in)validate this expectation.] 0N/A // apply a semi-splay step at the given node: 0N/A // . if root, norting needs to be done 0N/A // . if child of root, splay once 0N/A // . else zig-zig or sig-zag depending on path from grandparent 0N/A "tree operations may be inefficient ***");
0N/A // work down from the _root, looking for insertion point 0N/A }
else {
// follow right branch 1145N/A // This chunk is being returned to the binary tree. Its embedded 3695N/A // TreeList<Chunk> should be unused at this point. 0N/A }
else {
// need a new node in tree 0N/A "List was not initialized correctly");
0N/A }
else {
// insert under prevTL ... 0N/A }
else {
// am left child 3697N/A // Method 'total_size_in_tree' walks through the every block in the 0N/A // tree, so it can cause significant performance loss if there are 0N/A // many blocks in the tree 3697N/A "_total_free_blocks inconsistency");
0N/A // A list for this size may not be found (nd == 0) if 0N/A // This is a death where the appropriate list is now 0N/A // empty and has been removed from the list. 0N/A // This is a birth associated with a LinAB. The chunk 0N/A // for the LinAB is not in the dictionary. 0N/A // None of requested size implies overpopulated. 0N/A// Closures for walking the binary tree. 0N/A// do_list() walks the free list in a node applying the closure 0N/A// to each free chunk in the list 0N/A// do_tree() walks the nodes in the binary tree applying do_list() 0N/A// to each list at each node. 0N/A// For each list in the tree, calculate the desired, desired 0N/A// coalesce, count before sweep, and surplus before sweep. 0N/A// Used to search the tree until a condition is met. 0N/A// Similar to TreeCensusClosure but searches the 0N/A// tree and returns promptly when found. 0N/A#
if 0
// Don't need this yet but here for symmetry. 0N/A// Searches the tree for a chunk that ends at the 0N/A// specified address. 0N/A// Closures and methods for calculating total bytes returned to the 0N/A// free lists in the tree. 3695N/A// Count the number of entries in the tree. 0N/A// Calculate surpluses for the lists in the tree. 0N/A// Set hints for the lists in the tree. 0N/A "Current hint is inconsistent");
0N/A// Save count before previous sweep and splits and coalesces. 0N/A// Do reporting and post sweep clean up. 0N/A // Does walking the tree 3 times hurt? 0N/A// Print summary statistics 0N/A "------------------------------------\n");
0N/A// Print census information - counts, births, deaths, etc. 0N/A// for each list in the tree. Also print some summary 12N/A " growth: %8.5f deficit: %8.5f\n",
0N/A// Verify the following tree invariants: 0N/A// . _root has no parent 0N/A// . parent and child point to each other 0N/A// . each node's key correctly related to that of its child(ren) 0N/A "Chunk should be free");
0N/A// Note: this helper is recursive rather than iterative, so use with 0N/A// caution on very deep trees; and watch out for stack overflow errors; 0N/A// In general, to be used only for debugging. 0N/A "parent<-/->right");;
0N/A "list inconsistency");
0N/A "list count is inconsistent");
0N/A "list is incorrectly constructed");
3695N/A// Explicitly instantiate these types for FreeChunk.