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 * A binary tree based search structure for free blocks. 3695N/A * This is currently used in the Concurrent Mark&Sweep implementation, but 3695N/A * will be used for free block management for metadata. 0N/A// A TreeList is a FreeList which can be used to maintain a 0N/A// binary tree of free lists. 3786N/A // Explicitly import these names into our namespace to fix name lookup with templates 0N/A // Accessors for links in tree. 0N/A // For constructing a TreeList from a Tree chunk or 0N/A // address and size. 0N/A // Returns the head of the free list as a pointer to a TreeChunk. 0N/A // Returns the first available chunk in the free list as a pointer 1145N/A // Returns the block with the largest heap address amongst 1145N/A // those in the list for this size; potentially slow and expensive, 3697N/A // remove_chunk_replace_if_needed() removes the given "tc" from the TreeList. 0N/A // If "tc" is the first chunk in the list, it is also the 3697N/A // TreeList that is the node in the tree. remove_chunk_replace_if_needed() 0N/A // returns the possibly replaced TreeList* for the node in 0N/A // the tree. It also updates the parent of the original 0N/A // node to point to the new node. 3695N/A// A TreeChunk is a subclass of a Chunk that additionally 0N/A// maintains a pointer to the free list on which it is currently 0N/A// A TreeChunk is also used as a node in the binary tree. This 0N/A// allows the binary tree to be maintained without any additional 0N/A// storage (the free chunks are used). In a binary tree the first 0N/A// chunk in the free list is also the tree node. Note that the 0N/A// TreeChunk has an embedded TreeList for this purpose. Because 0N/A// the first chunk in the list is distinguished in this fashion 0N/A// (also is the node in the tree), it is the last chunk to be found 0N/A// on the free list for a node in the tree and is only removed if 0N/A// it is the last chunk on the free list. 0N/A // Initialize fields in a TreeChunk that should be 0N/A // initialized when the TreeChunk is being added to 0N/A // a free list in the tree. 0N/A // private accessors 3695N/A // This field is added and can be set to point to the 3695N/A // the Mutex used to synchronize access to the 3695N/A // dictionary so that assertion checking can be done. 3695N/A // For example it is set to point to _parDictionaryAllocLock. 0N/A // Remove a chunk of size "size" or larger from the tree and 0N/A // return it. If the chunk 0N/A // is the last chunk of that size, remove the node for that size 0N/A // Return a list of the specified size or NULL from the tree. 0N/A // The list is not removed from the tree. 0N/A // Remove this chunk from the tree. If the removal results 0N/A // in an empty list in the tree, remove the empty list. 0N/A // Remove the node in the trees starting at tl that has the 0N/A // minimum value and return it. Repair the tree as needed. 0N/A // Add this free chunk to the tree. 0N/A // verify that the given chunk is in the tree. 0N/A // Returns the total number of chunks in the list. 0N/A // Returns the total number of words in the chunks in the tree 0N/A // starting at "tl". 0N/A // Returns the sum of the square of the size of each block 0N/A // in the tree starting at "tl". 0N/A // Returns the total number of free blocks in the tree starting 0N/A // Reset the dictionary to the initial conditions with 0N/A // a single free chunk. 0N/A // Reset the dictionary to be empty. 0N/A // Return a chunk of size "size" or greater from 0N/A // want a better dynamic splay strategy for the future. 0N/A "Should be returning a free chunk");
3697N/A "_total_size inconsistency");
0N/A // Find the list with size "size" in the binary tree and update 0N/A // the statistics in the list according to "split" (chunk was 0N/A // split or coalesce) and "birth" (chunk was added or removed). 0N/A // Return true if the dictionary is overpopulated (more chunks of 0N/A // this size than desired) for size "size". 0N/A // Methods called at the beginning of a sweep to prepare the 0N/A // statistics for the sweep. 0N/A // Methods called after the end of a sweep to modify the 0N/A // statistics for the sweep. 0N/A // Return the largest free chunk in the tree. 0N/A // Accessors for statistics 0N/A // Reset statistics for all the lists in the tree. 0N/A // Print the statistcis for all the lists in the tree. Also may 0N/A // print out summaries. 3697N/A // For debugging. Returns the sum of the _returned_bytes for 0N/A // all lists in the tree. 3697N/A // Sets the _returned_bytes for all the lists in the tree to zero. 0N/A // For debugging. Return the total number of chunks in the dictionary. 3695N/A#
endif // SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP