1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/gc_implementation/concurrentMarkSweep/binaryTreeDictionary.cpp Sat Dec 01 00:00:00 2007 +0000
1.3 @@ -0,0 +1,1210 @@
1.4 +/*
1.5 + * Copyright 2001-2006 Sun Microsystems, Inc. All Rights Reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation.
1.11 + *
1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.15 + * version 2 for more details (a copy is included in the LICENSE file that
1.16 + * accompanied this code).
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License version
1.19 + * 2 along with this work; if not, write to the Free Software Foundation,
1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 + *
1.22 + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
1.23 + * CA 95054 USA or visit www.sun.com if you need additional information or
1.24 + * have any questions.
1.25 + *
1.26 + */
1.27 +
1.28 +# include "incls/_precompiled.incl"
1.29 +# include "incls/_binaryTreeDictionary.cpp.incl"
1.30 +
1.31 +////////////////////////////////////////////////////////////////////////////////
1.32 +// A binary tree based search structure for free blocks.
1.33 +// This is currently used in the Concurrent Mark&Sweep implementation.
1.34 +////////////////////////////////////////////////////////////////////////////////
1.35 +
1.36 +TreeChunk* TreeChunk::as_TreeChunk(FreeChunk* fc) {
1.37 + // Do some assertion checking here.
1.38 + return (TreeChunk*) fc;
1.39 +}
1.40 +
1.41 +void TreeChunk::verifyTreeChunkList() const {
1.42 + TreeChunk* nextTC = (TreeChunk*)next();
1.43 + if (prev() != NULL) { // interior list node shouldn'r have tree fields
1.44 + guarantee(embedded_list()->parent() == NULL && embedded_list()->left() == NULL &&
1.45 + embedded_list()->right() == NULL, "should be clear");
1.46 + }
1.47 + if (nextTC != NULL) {
1.48 + guarantee(as_TreeChunk(nextTC->prev()) == this, "broken chain");
1.49 + guarantee(nextTC->size() == size(), "wrong size");
1.50 + nextTC->verifyTreeChunkList();
1.51 + }
1.52 +}
1.53 +
1.54 +
1.55 +TreeList* TreeList::as_TreeList(TreeChunk* tc) {
1.56 + // This first free chunk in the list will be the tree list.
1.57 + assert(tc->size() >= sizeof(TreeChunk), "Chunk is too small for a TreeChunk");
1.58 + TreeList* tl = tc->embedded_list();
1.59 + tc->set_list(tl);
1.60 +#ifdef ASSERT
1.61 + tl->set_protecting_lock(NULL);
1.62 +#endif
1.63 + tl->set_hint(0);
1.64 + tl->set_size(tc->size());
1.65 + tl->link_head(tc);
1.66 + tl->link_tail(tc);
1.67 + tl->set_count(1);
1.68 + tl->init_statistics();
1.69 + tl->setParent(NULL);
1.70 + tl->setLeft(NULL);
1.71 + tl->setRight(NULL);
1.72 + return tl;
1.73 +}
1.74 +TreeList* TreeList::as_TreeList(HeapWord* addr, size_t size) {
1.75 + TreeChunk* tc = (TreeChunk*) addr;
1.76 + assert(size >= sizeof(TreeChunk), "Chunk is too small for a TreeChunk");
1.77 + assert(tc->size() == 0 && tc->prev() == NULL && tc->next() == NULL,
1.78 + "Space should be clear");
1.79 + tc->setSize(size);
1.80 + tc->linkPrev(NULL);
1.81 + tc->linkNext(NULL);
1.82 + TreeList* tl = TreeList::as_TreeList(tc);
1.83 + return tl;
1.84 +}
1.85 +
1.86 +TreeList* TreeList::removeChunkReplaceIfNeeded(TreeChunk* tc) {
1.87 +
1.88 + TreeList* retTL = this;
1.89 + FreeChunk* list = head();
1.90 + assert(!list || list != list->next(), "Chunk on list twice");
1.91 + assert(tc != NULL, "Chunk being removed is NULL");
1.92 + assert(parent() == NULL || this == parent()->left() ||
1.93 + this == parent()->right(), "list is inconsistent");
1.94 + assert(tc->isFree(), "Header is not marked correctly");
1.95 + assert(head() == NULL || head()->prev() == NULL, "list invariant");
1.96 + assert(tail() == NULL || tail()->next() == NULL, "list invariant");
1.97 +
1.98 + FreeChunk* prevFC = tc->prev();
1.99 + TreeChunk* nextTC = TreeChunk::as_TreeChunk(tc->next());
1.100 + assert(list != NULL, "should have at least the target chunk");
1.101 +
1.102 + // Is this the first item on the list?
1.103 + if (tc == list) {
1.104 + // The "getChunk..." functions for a TreeList will not return the
1.105 + // first chunk in the list unless it is the last chunk in the list
1.106 + // because the first chunk is also acting as the tree node.
1.107 + // When coalescing happens, however, the first chunk in the a tree
1.108 + // list can be the start of a free range. Free ranges are removed
1.109 + // from the free lists so that they are not available to be
1.110 + // allocated when the sweeper yields (giving up the free list lock)
1.111 + // to allow mutator activity. If this chunk is the first in the
1.112 + // list and is not the last in the list, do the work to copy the
1.113 + // TreeList from the first chunk to the next chunk and update all
1.114 + // the TreeList pointers in the chunks in the list.
1.115 + if (nextTC == NULL) {
1.116 + assert(prevFC == NULL, "Not last chunk in the list")
1.117 + set_tail(NULL);
1.118 + set_head(NULL);
1.119 + } else {
1.120 + // copy embedded list.
1.121 + nextTC->set_embedded_list(tc->embedded_list());
1.122 + retTL = nextTC->embedded_list();
1.123 + // Fix the pointer to the list in each chunk in the list.
1.124 + // This can be slow for a long list. Consider having
1.125 + // an option that does not allow the first chunk on the
1.126 + // list to be coalesced.
1.127 + for (TreeChunk* curTC = nextTC; curTC != NULL;
1.128 + curTC = TreeChunk::as_TreeChunk(curTC->next())) {
1.129 + curTC->set_list(retTL);
1.130 + }
1.131 + // Fix the parent to point to the new TreeList.
1.132 + if (retTL->parent() != NULL) {
1.133 + if (this == retTL->parent()->left()) {
1.134 + retTL->parent()->setLeft(retTL);
1.135 + } else {
1.136 + assert(this == retTL->parent()->right(), "Parent is incorrect");
1.137 + retTL->parent()->setRight(retTL);
1.138 + }
1.139 + }
1.140 + // Fix the children's parent pointers to point to the
1.141 + // new list.
1.142 + assert(right() == retTL->right(), "Should have been copied");
1.143 + if (retTL->right() != NULL) {
1.144 + retTL->right()->setParent(retTL);
1.145 + }
1.146 + assert(left() == retTL->left(), "Should have been copied");
1.147 + if (retTL->left() != NULL) {
1.148 + retTL->left()->setParent(retTL);
1.149 + }
1.150 + retTL->link_head(nextTC);
1.151 + assert(nextTC->isFree(), "Should be a free chunk");
1.152 + }
1.153 + } else {
1.154 + if (nextTC == NULL) {
1.155 + // Removing chunk at tail of list
1.156 + link_tail(prevFC);
1.157 + }
1.158 + // Chunk is interior to the list
1.159 + prevFC->linkAfter(nextTC);
1.160 + }
1.161 +
1.162 + // Below this point the embeded TreeList being used for the
1.163 + // tree node may have changed. Don't use "this"
1.164 + // TreeList*.
1.165 + // chunk should still be a free chunk (bit set in _prev)
1.166 + assert(!retTL->head() || retTL->size() == retTL->head()->size(),
1.167 + "Wrong sized chunk in list");
1.168 + debug_only(
1.169 + tc->linkPrev(NULL);
1.170 + tc->linkNext(NULL);
1.171 + tc->set_list(NULL);
1.172 + bool prev_found = false;
1.173 + bool next_found = false;
1.174 + for (FreeChunk* curFC = retTL->head();
1.175 + curFC != NULL; curFC = curFC->next()) {
1.176 + assert(curFC != tc, "Chunk is still in list");
1.177 + if (curFC == prevFC) {
1.178 + prev_found = true;
1.179 + }
1.180 + if (curFC == nextTC) {
1.181 + next_found = true;
1.182 + }
1.183 + }
1.184 + assert(prevFC == NULL || prev_found, "Chunk was lost from list");
1.185 + assert(nextTC == NULL || next_found, "Chunk was lost from list");
1.186 + assert(retTL->parent() == NULL ||
1.187 + retTL == retTL->parent()->left() ||
1.188 + retTL == retTL->parent()->right(),
1.189 + "list is inconsistent");
1.190 + )
1.191 + retTL->decrement_count();
1.192 +
1.193 + assert(tc->isFree(), "Should still be a free chunk");
1.194 + assert(retTL->head() == NULL || retTL->head()->prev() == NULL,
1.195 + "list invariant");
1.196 + assert(retTL->tail() == NULL || retTL->tail()->next() == NULL,
1.197 + "list invariant");
1.198 + return retTL;
1.199 +}
1.200 +void TreeList::returnChunkAtTail(TreeChunk* chunk) {
1.201 + assert(chunk != NULL, "returning NULL chunk");
1.202 + assert(chunk->list() == this, "list should be set for chunk");
1.203 + assert(tail() != NULL, "The tree list is embedded in the first chunk");
1.204 + // which means that the list can never be empty.
1.205 + assert(!verifyChunkInFreeLists(chunk), "Double entry");
1.206 + assert(head() == NULL || head()->prev() == NULL, "list invariant");
1.207 + assert(tail() == NULL || tail()->next() == NULL, "list invariant");
1.208 +
1.209 + FreeChunk* fc = tail();
1.210 + fc->linkAfter(chunk);
1.211 + link_tail(chunk);
1.212 +
1.213 + assert(!tail() || size() == tail()->size(), "Wrong sized chunk in list");
1.214 + increment_count();
1.215 + debug_only(increment_returnedBytes_by(chunk->size()*sizeof(HeapWord));)
1.216 + assert(head() == NULL || head()->prev() == NULL, "list invariant");
1.217 + assert(tail() == NULL || tail()->next() == NULL, "list invariant");
1.218 +}
1.219 +
1.220 +// Add this chunk at the head of the list. "At the head of the list"
1.221 +// is defined to be after the chunk pointer to by head(). This is
1.222 +// because the TreeList is embedded in the first TreeChunk in the
1.223 +// list. See the definition of TreeChunk.
1.224 +void TreeList::returnChunkAtHead(TreeChunk* chunk) {
1.225 + assert(chunk->list() == this, "list should be set for chunk");
1.226 + assert(head() != NULL, "The tree list is embedded in the first chunk");
1.227 + assert(chunk != NULL, "returning NULL chunk");
1.228 + assert(!verifyChunkInFreeLists(chunk), "Double entry");
1.229 + assert(head() == NULL || head()->prev() == NULL, "list invariant");
1.230 + assert(tail() == NULL || tail()->next() == NULL, "list invariant");
1.231 +
1.232 + FreeChunk* fc = head()->next();
1.233 + if (fc != NULL) {
1.234 + chunk->linkAfter(fc);
1.235 + } else {
1.236 + assert(tail() == NULL, "List is inconsistent");
1.237 + link_tail(chunk);
1.238 + }
1.239 + head()->linkAfter(chunk);
1.240 + assert(!head() || size() == head()->size(), "Wrong sized chunk in list");
1.241 + increment_count();
1.242 + debug_only(increment_returnedBytes_by(chunk->size()*sizeof(HeapWord));)
1.243 + assert(head() == NULL || head()->prev() == NULL, "list invariant");
1.244 + assert(tail() == NULL || tail()->next() == NULL, "list invariant");
1.245 +}
1.246 +
1.247 +TreeChunk* TreeList::head_as_TreeChunk() {
1.248 + assert(head() == NULL || TreeChunk::as_TreeChunk(head())->list() == this,
1.249 + "Wrong type of chunk?");
1.250 + return TreeChunk::as_TreeChunk(head());
1.251 +}
1.252 +
1.253 +TreeChunk* TreeList::first_available() {
1.254 + guarantee(head() != NULL, "The head of the list cannot be NULL");
1.255 + FreeChunk* fc = head()->next();
1.256 + TreeChunk* retTC;
1.257 + if (fc == NULL) {
1.258 + retTC = head_as_TreeChunk();
1.259 + } else {
1.260 + retTC = TreeChunk::as_TreeChunk(fc);
1.261 + }
1.262 + assert(retTC->list() == this, "Wrong type of chunk.");
1.263 + return retTC;
1.264 +}
1.265 +
1.266 +BinaryTreeDictionary::BinaryTreeDictionary(MemRegion mr, bool splay):
1.267 + _splay(splay)
1.268 +{
1.269 + assert(mr.byte_size() > MIN_TREE_CHUNK_SIZE, "minimum chunk size");
1.270 +
1.271 + reset(mr);
1.272 + assert(root()->left() == NULL, "reset check failed");
1.273 + assert(root()->right() == NULL, "reset check failed");
1.274 + assert(root()->head()->next() == NULL, "reset check failed");
1.275 + assert(root()->head()->prev() == NULL, "reset check failed");
1.276 + assert(totalSize() == root()->size(), "reset check failed");
1.277 + assert(totalFreeBlocks() == 1, "reset check failed");
1.278 +}
1.279 +
1.280 +void BinaryTreeDictionary::inc_totalSize(size_t inc) {
1.281 + _totalSize = _totalSize + inc;
1.282 +}
1.283 +
1.284 +void BinaryTreeDictionary::dec_totalSize(size_t dec) {
1.285 + _totalSize = _totalSize - dec;
1.286 +}
1.287 +
1.288 +void BinaryTreeDictionary::reset(MemRegion mr) {
1.289 + assert(mr.byte_size() > MIN_TREE_CHUNK_SIZE, "minimum chunk size");
1.290 + set_root(TreeList::as_TreeList(mr.start(), mr.word_size()));
1.291 + set_totalSize(mr.word_size());
1.292 + set_totalFreeBlocks(1);
1.293 +}
1.294 +
1.295 +void BinaryTreeDictionary::reset(HeapWord* addr, size_t byte_size) {
1.296 + MemRegion mr(addr, heap_word_size(byte_size));
1.297 + reset(mr);
1.298 +}
1.299 +
1.300 +void BinaryTreeDictionary::reset() {
1.301 + set_root(NULL);
1.302 + set_totalSize(0);
1.303 + set_totalFreeBlocks(0);
1.304 +}
1.305 +
1.306 +// Get a free block of size at least size from tree, or NULL.
1.307 +// If a splay step is requested, the removal algorithm (only) incorporates
1.308 +// a splay step as follows:
1.309 +// . the search proceeds down the tree looking for a possible
1.310 +// match. At the (closest) matching location, an appropriate splay step is applied
1.311 +// (zig, zig-zig or zig-zag). A chunk of the appropriate size is then returned
1.312 +// if available, and if it's the last chunk, the node is deleted. A deteleted
1.313 +// node is replaced in place by its tree successor.
1.314 +TreeChunk*
1.315 +BinaryTreeDictionary::getChunkFromTree(size_t size, Dither dither, bool splay)
1.316 +{
1.317 + TreeList *curTL, *prevTL;
1.318 + TreeChunk* retTC = NULL;
1.319 + assert(size >= MIN_TREE_CHUNK_SIZE, "minimum chunk size");
1.320 + if (FLSVerifyDictionary) {
1.321 + verifyTree();
1.322 + }
1.323 + // starting at the root, work downwards trying to find match.
1.324 + // Remember the last node of size too great or too small.
1.325 + for (prevTL = curTL = root(); curTL != NULL;) {
1.326 + if (curTL->size() == size) { // exact match
1.327 + break;
1.328 + }
1.329 + prevTL = curTL;
1.330 + if (curTL->size() < size) { // proceed to right sub-tree
1.331 + curTL = curTL->right();
1.332 + } else { // proceed to left sub-tree
1.333 + assert(curTL->size() > size, "size inconsistency");
1.334 + curTL = curTL->left();
1.335 + }
1.336 + }
1.337 + if (curTL == NULL) { // couldn't find exact match
1.338 + // try and find the next larger size by walking back up the search path
1.339 + for (curTL = prevTL; curTL != NULL;) {
1.340 + if (curTL->size() >= size) break;
1.341 + else curTL = curTL->parent();
1.342 + }
1.343 + assert(curTL == NULL || curTL->count() > 0,
1.344 + "An empty list should not be in the tree");
1.345 + }
1.346 + if (curTL != NULL) {
1.347 + assert(curTL->size() >= size, "size inconsistency");
1.348 + if (UseCMSAdaptiveFreeLists) {
1.349 +
1.350 + // A candidate chunk has been found. If it is already under
1.351 + // populated, get a chunk associated with the hint for this
1.352 + // chunk.
1.353 + if (curTL->surplus() <= 0) {
1.354 + /* Use the hint to find a size with a surplus, and reset the hint. */
1.355 + TreeList* hintTL = curTL;
1.356 + while (hintTL->hint() != 0) {
1.357 + assert(hintTL->hint() == 0 || hintTL->hint() > hintTL->size(),
1.358 + "hint points in the wrong direction");
1.359 + hintTL = findList(hintTL->hint());
1.360 + assert(curTL != hintTL, "Infinite loop");
1.361 + if (hintTL == NULL ||
1.362 + hintTL == curTL /* Should not happen but protect against it */ ) {
1.363 + // No useful hint. Set the hint to NULL and go on.
1.364 + curTL->set_hint(0);
1.365 + break;
1.366 + }
1.367 + assert(hintTL->size() > size, "hint is inconsistent");
1.368 + if (hintTL->surplus() > 0) {
1.369 + // The hint led to a list that has a surplus. Use it.
1.370 + // Set the hint for the candidate to an overpopulated
1.371 + // size.
1.372 + curTL->set_hint(hintTL->size());
1.373 + // Change the candidate.
1.374 + curTL = hintTL;
1.375 + break;
1.376 + }
1.377 + // The evm code reset the hint of the candidate as
1.378 + // at an interrim point. Why? Seems like this leaves
1.379 + // the hint pointing to a list that didn't work.
1.380 + // curTL->set_hint(hintTL->size());
1.381 + }
1.382 + }
1.383 + }
1.384 + // don't waste time splaying if chunk's singleton
1.385 + if (splay && curTL->head()->next() != NULL) {
1.386 + semiSplayStep(curTL);
1.387 + }
1.388 + retTC = curTL->first_available();
1.389 + assert((retTC != NULL) && (curTL->count() > 0),
1.390 + "A list in the binary tree should not be NULL");
1.391 + assert(retTC->size() >= size,
1.392 + "A chunk of the wrong size was found");
1.393 + removeChunkFromTree(retTC);
1.394 + assert(retTC->isFree(), "Header is not marked correctly");
1.395 + }
1.396 +
1.397 + if (FLSVerifyDictionary) {
1.398 + verify();
1.399 + }
1.400 + return retTC;
1.401 +}
1.402 +
1.403 +TreeList* BinaryTreeDictionary::findList(size_t size) const {
1.404 + TreeList* curTL;
1.405 + for (curTL = root(); curTL != NULL;) {
1.406 + if (curTL->size() == size) { // exact match
1.407 + break;
1.408 + }
1.409 +
1.410 + if (curTL->size() < size) { // proceed to right sub-tree
1.411 + curTL = curTL->right();
1.412 + } else { // proceed to left sub-tree
1.413 + assert(curTL->size() > size, "size inconsistency");
1.414 + curTL = curTL->left();
1.415 + }
1.416 + }
1.417 + return curTL;
1.418 +}
1.419 +
1.420 +
1.421 +bool BinaryTreeDictionary::verifyChunkInFreeLists(FreeChunk* tc) const {
1.422 + size_t size = tc->size();
1.423 + TreeList* tl = findList(size);
1.424 + if (tl == NULL) {
1.425 + return false;
1.426 + } else {
1.427 + return tl->verifyChunkInFreeLists(tc);
1.428 + }
1.429 +}
1.430 +
1.431 +FreeChunk* BinaryTreeDictionary::findLargestDict() const {
1.432 + TreeList *curTL = root();
1.433 + if (curTL != NULL) {
1.434 + while(curTL->right() != NULL) curTL = curTL->right();
1.435 + return curTL->first_available();
1.436 + } else {
1.437 + return NULL;
1.438 + }
1.439 +}
1.440 +
1.441 +// Remove the current chunk from the tree. If it is not the last
1.442 +// chunk in a list on a tree node, just unlink it.
1.443 +// If it is the last chunk in the list (the next link is NULL),
1.444 +// remove the node and repair the tree.
1.445 +TreeChunk*
1.446 +BinaryTreeDictionary::removeChunkFromTree(TreeChunk* tc) {
1.447 + assert(tc != NULL, "Should not call with a NULL chunk");
1.448 + assert(tc->isFree(), "Header is not marked correctly");
1.449 +
1.450 + TreeList *newTL, *parentTL;
1.451 + TreeChunk* retTC;
1.452 + TreeList* tl = tc->list();
1.453 + debug_only(
1.454 + bool removing_only_chunk = false;
1.455 + if (tl == _root) {
1.456 + if ((_root->left() == NULL) && (_root->right() == NULL)) {
1.457 + if (_root->count() == 1) {
1.458 + assert(_root->head() == tc, "Should only be this one chunk");
1.459 + removing_only_chunk = true;
1.460 + }
1.461 + }
1.462 + }
1.463 + )
1.464 + assert(tl != NULL, "List should be set");
1.465 + assert(tl->parent() == NULL || tl == tl->parent()->left() ||
1.466 + tl == tl->parent()->right(), "list is inconsistent");
1.467 +
1.468 + bool complicatedSplice = false;
1.469 +
1.470 + retTC = tc;
1.471 + // Removing this chunk can have the side effect of changing the node
1.472 + // (TreeList*) in the tree. If the node is the root, update it.
1.473 + TreeList* replacementTL = tl->removeChunkReplaceIfNeeded(tc);
1.474 + assert(tc->isFree(), "Chunk should still be free");
1.475 + assert(replacementTL->parent() == NULL ||
1.476 + replacementTL == replacementTL->parent()->left() ||
1.477 + replacementTL == replacementTL->parent()->right(),
1.478 + "list is inconsistent");
1.479 + if (tl == root()) {
1.480 + assert(replacementTL->parent() == NULL, "Incorrectly replacing root");
1.481 + set_root(replacementTL);
1.482 + }
1.483 + debug_only(
1.484 + if (tl != replacementTL) {
1.485 + assert(replacementTL->head() != NULL,
1.486 + "If the tree list was replaced, it should not be a NULL list");
1.487 + TreeList* rhl = replacementTL->head_as_TreeChunk()->list();
1.488 + TreeList* rtl = TreeChunk::as_TreeChunk(replacementTL->tail())->list();
1.489 + assert(rhl == replacementTL, "Broken head");
1.490 + assert(rtl == replacementTL, "Broken tail");
1.491 + assert(replacementTL->size() == tc->size(), "Broken size");
1.492 + }
1.493 + )
1.494 +
1.495 + // Does the tree need to be repaired?
1.496 + if (replacementTL->count() == 0) {
1.497 + assert(replacementTL->head() == NULL &&
1.498 + replacementTL->tail() == NULL, "list count is incorrect");
1.499 + // Find the replacement node for the (soon to be empty) node being removed.
1.500 + // if we have a single (or no) child, splice child in our stead
1.501 + if (replacementTL->left() == NULL) {
1.502 + // left is NULL so pick right. right may also be NULL.
1.503 + newTL = replacementTL->right();
1.504 + debug_only(replacementTL->clearRight();)
1.505 + } else if (replacementTL->right() == NULL) {
1.506 + // right is NULL
1.507 + newTL = replacementTL->left();
1.508 + debug_only(replacementTL->clearLeft();)
1.509 + } else { // we have both children, so, by patriarchal convention,
1.510 + // my replacement is least node in right sub-tree
1.511 + complicatedSplice = true;
1.512 + newTL = removeTreeMinimum(replacementTL->right());
1.513 + assert(newTL != NULL && newTL->left() == NULL &&
1.514 + newTL->right() == NULL, "sub-tree minimum exists");
1.515 + }
1.516 + // newTL is the replacement for the (soon to be empty) node.
1.517 + // newTL may be NULL.
1.518 + // should verify; we just cleanly excised our replacement
1.519 + if (FLSVerifyDictionary) {
1.520 + verifyTree();
1.521 + }
1.522 + // first make newTL my parent's child
1.523 + if ((parentTL = replacementTL->parent()) == NULL) {
1.524 + // newTL should be root
1.525 + assert(tl == root(), "Incorrectly replacing root");
1.526 + set_root(newTL);
1.527 + if (newTL != NULL) {
1.528 + newTL->clearParent();
1.529 + }
1.530 + } else if (parentTL->right() == replacementTL) {
1.531 + // replacementTL is a right child
1.532 + parentTL->setRight(newTL);
1.533 + } else { // replacementTL is a left child
1.534 + assert(parentTL->left() == replacementTL, "should be left child");
1.535 + parentTL->setLeft(newTL);
1.536 + }
1.537 + debug_only(replacementTL->clearParent();)
1.538 + if (complicatedSplice) { // we need newTL to get replacementTL's
1.539 + // two children
1.540 + assert(newTL != NULL &&
1.541 + newTL->left() == NULL && newTL->right() == NULL,
1.542 + "newTL should not have encumbrances from the past");
1.543 + // we'd like to assert as below:
1.544 + // assert(replacementTL->left() != NULL && replacementTL->right() != NULL,
1.545 + // "else !complicatedSplice");
1.546 + // ... however, the above assertion is too strong because we aren't
1.547 + // guaranteed that replacementTL->right() is still NULL.
1.548 + // Recall that we removed
1.549 + // the right sub-tree minimum from replacementTL.
1.550 + // That may well have been its right
1.551 + // child! So we'll just assert half of the above:
1.552 + assert(replacementTL->left() != NULL, "else !complicatedSplice");
1.553 + newTL->setLeft(replacementTL->left());
1.554 + newTL->setRight(replacementTL->right());
1.555 + debug_only(
1.556 + replacementTL->clearRight();
1.557 + replacementTL->clearLeft();
1.558 + )
1.559 + }
1.560 + assert(replacementTL->right() == NULL &&
1.561 + replacementTL->left() == NULL &&
1.562 + replacementTL->parent() == NULL,
1.563 + "delete without encumbrances");
1.564 + }
1.565 +
1.566 + assert(totalSize() >= retTC->size(), "Incorrect total size");
1.567 + dec_totalSize(retTC->size()); // size book-keeping
1.568 + assert(totalFreeBlocks() > 0, "Incorrect total count");
1.569 + set_totalFreeBlocks(totalFreeBlocks() - 1);
1.570 +
1.571 + assert(retTC != NULL, "null chunk?");
1.572 + assert(retTC->prev() == NULL && retTC->next() == NULL,
1.573 + "should return without encumbrances");
1.574 + if (FLSVerifyDictionary) {
1.575 + verifyTree();
1.576 + }
1.577 + assert(!removing_only_chunk || _root == NULL, "root should be NULL");
1.578 + return TreeChunk::as_TreeChunk(retTC);
1.579 +}
1.580 +
1.581 +// Remove the leftmost node (lm) in the tree and return it.
1.582 +// If lm has a right child, link it to the left node of
1.583 +// the parent of lm.
1.584 +TreeList* BinaryTreeDictionary::removeTreeMinimum(TreeList* tl) {
1.585 + assert(tl != NULL && tl->parent() != NULL, "really need a proper sub-tree");
1.586 + // locate the subtree minimum by walking down left branches
1.587 + TreeList* curTL = tl;
1.588 + for (; curTL->left() != NULL; curTL = curTL->left());
1.589 + // obviously curTL now has at most one child, a right child
1.590 + if (curTL != root()) { // Should this test just be removed?
1.591 + TreeList* parentTL = curTL->parent();
1.592 + if (parentTL->left() == curTL) { // curTL is a left child
1.593 + parentTL->setLeft(curTL->right());
1.594 + } else {
1.595 + // If the list tl has no left child, then curTL may be
1.596 + // the right child of parentTL.
1.597 + assert(parentTL->right() == curTL, "should be a right child");
1.598 + parentTL->setRight(curTL->right());
1.599 + }
1.600 + } else {
1.601 + // The only use of this method would not pass the root of the
1.602 + // tree (as indicated by the assertion above that the tree list
1.603 + // has a parent) but the specification does not explicitly exclude the
1.604 + // passing of the root so accomodate it.
1.605 + set_root(NULL);
1.606 + }
1.607 + debug_only(
1.608 + curTL->clearParent(); // Test if this needs to be cleared
1.609 + curTL->clearRight(); // recall, above, left child is already null
1.610 + )
1.611 + // we just excised a (non-root) node, we should still verify all tree invariants
1.612 + if (FLSVerifyDictionary) {
1.613 + verifyTree();
1.614 + }
1.615 + return curTL;
1.616 +}
1.617 +
1.618 +// Based on a simplification of the algorithm by Sleator and Tarjan (JACM 1985).
1.619 +// The simplifications are the following:
1.620 +// . we splay only when we delete (not when we insert)
1.621 +// . we apply a single spay step per deletion/access
1.622 +// By doing such partial splaying, we reduce the amount of restructuring,
1.623 +// while getting a reasonably efficient search tree (we think).
1.624 +// [Measurements will be needed to (in)validate this expectation.]
1.625 +
1.626 +void BinaryTreeDictionary::semiSplayStep(TreeList* tc) {
1.627 + // apply a semi-splay step at the given node:
1.628 + // . if root, norting needs to be done
1.629 + // . if child of root, splay once
1.630 + // . else zig-zig or sig-zag depending on path from grandparent
1.631 + if (root() == tc) return;
1.632 + warning("*** Splaying not yet implemented; "
1.633 + "tree operations may be inefficient ***");
1.634 +}
1.635 +
1.636 +void BinaryTreeDictionary::insertChunkInTree(FreeChunk* fc) {
1.637 + TreeList *curTL, *prevTL;
1.638 + size_t size = fc->size();
1.639 +
1.640 + assert(size >= MIN_TREE_CHUNK_SIZE, "too small to be a TreeList");
1.641 + if (FLSVerifyDictionary) {
1.642 + verifyTree();
1.643 + }
1.644 + // XXX: do i need to clear the FreeChunk fields, let me do it just in case
1.645 + // Revisit this later
1.646 +
1.647 + fc->clearNext();
1.648 + fc->linkPrev(NULL);
1.649 +
1.650 + // work down from the _root, looking for insertion point
1.651 + for (prevTL = curTL = root(); curTL != NULL;) {
1.652 + if (curTL->size() == size) // exact match
1.653 + break;
1.654 + prevTL = curTL;
1.655 + if (curTL->size() > size) { // follow left branch
1.656 + curTL = curTL->left();
1.657 + } else { // follow right branch
1.658 + assert(curTL->size() < size, "size inconsistency");
1.659 + curTL = curTL->right();
1.660 + }
1.661 + }
1.662 + TreeChunk* tc = TreeChunk::as_TreeChunk(fc);
1.663 + // This chunk is being returned to the binary try. It's embedded
1.664 + // TreeList should be unused at this point.
1.665 + tc->initialize();
1.666 + if (curTL != NULL) { // exact match
1.667 + tc->set_list(curTL);
1.668 + curTL->returnChunkAtTail(tc);
1.669 + } else { // need a new node in tree
1.670 + tc->clearNext();
1.671 + tc->linkPrev(NULL);
1.672 + TreeList* newTL = TreeList::as_TreeList(tc);
1.673 + assert(((TreeChunk*)tc)->list() == newTL,
1.674 + "List was not initialized correctly");
1.675 + if (prevTL == NULL) { // we are the only tree node
1.676 + assert(root() == NULL, "control point invariant");
1.677 + set_root(newTL);
1.678 + } else { // insert under prevTL ...
1.679 + if (prevTL->size() < size) { // am right child
1.680 + assert(prevTL->right() == NULL, "control point invariant");
1.681 + prevTL->setRight(newTL);
1.682 + } else { // am left child
1.683 + assert(prevTL->size() > size && prevTL->left() == NULL, "cpt pt inv");
1.684 + prevTL->setLeft(newTL);
1.685 + }
1.686 + }
1.687 + }
1.688 + assert(tc->list() != NULL, "Tree list should be set");
1.689 +
1.690 + inc_totalSize(size);
1.691 + // Method 'totalSizeInTree' walks through the every block in the
1.692 + // tree, so it can cause significant performance loss if there are
1.693 + // many blocks in the tree
1.694 + assert(!FLSVerifyDictionary || totalSizeInTree(root()) == totalSize(), "_totalSize inconsistency");
1.695 + set_totalFreeBlocks(totalFreeBlocks() + 1);
1.696 + if (FLSVerifyDictionary) {
1.697 + verifyTree();
1.698 + }
1.699 +}
1.700 +
1.701 +size_t BinaryTreeDictionary::maxChunkSize() const {
1.702 + verify_par_locked();
1.703 + TreeList* tc = root();
1.704 + if (tc == NULL) return 0;
1.705 + for (; tc->right() != NULL; tc = tc->right());
1.706 + return tc->size();
1.707 +}
1.708 +
1.709 +size_t BinaryTreeDictionary::totalListLength(TreeList* tl) const {
1.710 + size_t res;
1.711 + res = tl->count();
1.712 +#ifdef ASSERT
1.713 + size_t cnt;
1.714 + FreeChunk* tc = tl->head();
1.715 + for (cnt = 0; tc != NULL; tc = tc->next(), cnt++);
1.716 + assert(res == cnt, "The count is not being maintained correctly");
1.717 +#endif
1.718 + return res;
1.719 +}
1.720 +
1.721 +size_t BinaryTreeDictionary::totalSizeInTree(TreeList* tl) const {
1.722 + if (tl == NULL)
1.723 + return 0;
1.724 + return (tl->size() * totalListLength(tl)) +
1.725 + totalSizeInTree(tl->left()) +
1.726 + totalSizeInTree(tl->right());
1.727 +}
1.728 +
1.729 +double BinaryTreeDictionary::sum_of_squared_block_sizes(TreeList* const tl) const {
1.730 + if (tl == NULL) {
1.731 + return 0.0;
1.732 + }
1.733 + double size = (double)(tl->size());
1.734 + double curr = size * size * totalListLength(tl);
1.735 + curr += sum_of_squared_block_sizes(tl->left());
1.736 + curr += sum_of_squared_block_sizes(tl->right());
1.737 + return curr;
1.738 +}
1.739 +
1.740 +size_t BinaryTreeDictionary::totalFreeBlocksInTree(TreeList* tl) const {
1.741 + if (tl == NULL)
1.742 + return 0;
1.743 + return totalListLength(tl) +
1.744 + totalFreeBlocksInTree(tl->left()) +
1.745 + totalFreeBlocksInTree(tl->right());
1.746 +}
1.747 +
1.748 +size_t BinaryTreeDictionary::numFreeBlocks() const {
1.749 + assert(totalFreeBlocksInTree(root()) == totalFreeBlocks(),
1.750 + "_totalFreeBlocks inconsistency");
1.751 + return totalFreeBlocks();
1.752 +}
1.753 +
1.754 +size_t BinaryTreeDictionary::treeHeightHelper(TreeList* tl) const {
1.755 + if (tl == NULL)
1.756 + return 0;
1.757 + return 1 + MAX2(treeHeightHelper(tl->left()),
1.758 + treeHeightHelper(tl->right()));
1.759 +}
1.760 +
1.761 +size_t BinaryTreeDictionary::treeHeight() const {
1.762 + return treeHeightHelper(root());
1.763 +}
1.764 +
1.765 +size_t BinaryTreeDictionary::totalNodesHelper(TreeList* tl) const {
1.766 + if (tl == NULL) {
1.767 + return 0;
1.768 + }
1.769 + return 1 + totalNodesHelper(tl->left()) +
1.770 + totalNodesHelper(tl->right());
1.771 +}
1.772 +
1.773 +size_t BinaryTreeDictionary::totalNodesInTree(TreeList* tl) const {
1.774 + return totalNodesHelper(root());
1.775 +}
1.776 +
1.777 +void BinaryTreeDictionary::dictCensusUpdate(size_t size, bool split, bool birth){
1.778 + TreeList* nd = findList(size);
1.779 + if (nd) {
1.780 + if (split) {
1.781 + if (birth) {
1.782 + nd->increment_splitBirths();
1.783 + nd->increment_surplus();
1.784 + } else {
1.785 + nd->increment_splitDeaths();
1.786 + nd->decrement_surplus();
1.787 + }
1.788 + } else {
1.789 + if (birth) {
1.790 + nd->increment_coalBirths();
1.791 + nd->increment_surplus();
1.792 + } else {
1.793 + nd->increment_coalDeaths();
1.794 + nd->decrement_surplus();
1.795 + }
1.796 + }
1.797 + }
1.798 + // A list for this size may not be found (nd == 0) if
1.799 + // This is a death where the appropriate list is now
1.800 + // empty and has been removed from the list.
1.801 + // This is a birth associated with a LinAB. The chunk
1.802 + // for the LinAB is not in the dictionary.
1.803 +}
1.804 +
1.805 +bool BinaryTreeDictionary::coalDictOverPopulated(size_t size) {
1.806 + TreeList* list_of_size = findList(size);
1.807 + // None of requested size implies overpopulated.
1.808 + return list_of_size == NULL || list_of_size->coalDesired() <= 0 ||
1.809 + list_of_size->count() > list_of_size->coalDesired();
1.810 +}
1.811 +
1.812 +// Closures for walking the binary tree.
1.813 +// do_list() walks the free list in a node applying the closure
1.814 +// to each free chunk in the list
1.815 +// do_tree() walks the nodes in the binary tree applying do_list()
1.816 +// to each list at each node.
1.817 +
1.818 +class TreeCensusClosure : public StackObj {
1.819 + protected:
1.820 + virtual void do_list(FreeList* fl) = 0;
1.821 + public:
1.822 + virtual void do_tree(TreeList* tl) = 0;
1.823 +};
1.824 +
1.825 +class AscendTreeCensusClosure : public TreeCensusClosure {
1.826 + public:
1.827 + void do_tree(TreeList* tl) {
1.828 + if (tl != NULL) {
1.829 + do_tree(tl->left());
1.830 + do_list(tl);
1.831 + do_tree(tl->right());
1.832 + }
1.833 + }
1.834 +};
1.835 +
1.836 +class DescendTreeCensusClosure : public TreeCensusClosure {
1.837 + public:
1.838 + void do_tree(TreeList* tl) {
1.839 + if (tl != NULL) {
1.840 + do_tree(tl->right());
1.841 + do_list(tl);
1.842 + do_tree(tl->left());
1.843 + }
1.844 + }
1.845 +};
1.846 +
1.847 +// For each list in the tree, calculate the desired, desired
1.848 +// coalesce, count before sweep, and surplus before sweep.
1.849 +class BeginSweepClosure : public AscendTreeCensusClosure {
1.850 + double _percentage;
1.851 + float _inter_sweep_current;
1.852 + float _inter_sweep_estimate;
1.853 +
1.854 + public:
1.855 + BeginSweepClosure(double p, float inter_sweep_current,
1.856 + float inter_sweep_estimate) :
1.857 + _percentage(p),
1.858 + _inter_sweep_current(inter_sweep_current),
1.859 + _inter_sweep_estimate(inter_sweep_estimate) { }
1.860 +
1.861 + void do_list(FreeList* fl) {
1.862 + double coalSurplusPercent = _percentage;
1.863 + fl->compute_desired(_inter_sweep_current, _inter_sweep_estimate);
1.864 + fl->set_coalDesired((ssize_t)((double)fl->desired() * coalSurplusPercent));
1.865 + fl->set_beforeSweep(fl->count());
1.866 + fl->set_bfrSurp(fl->surplus());
1.867 + }
1.868 +};
1.869 +
1.870 +// Used to search the tree until a condition is met.
1.871 +// Similar to TreeCensusClosure but searches the
1.872 +// tree and returns promptly when found.
1.873 +
1.874 +class TreeSearchClosure : public StackObj {
1.875 + protected:
1.876 + virtual bool do_list(FreeList* fl) = 0;
1.877 + public:
1.878 + virtual bool do_tree(TreeList* tl) = 0;
1.879 +};
1.880 +
1.881 +#if 0 // Don't need this yet but here for symmetry.
1.882 +class AscendTreeSearchClosure : public TreeSearchClosure {
1.883 + public:
1.884 + bool do_tree(TreeList* tl) {
1.885 + if (tl != NULL) {
1.886 + if (do_tree(tl->left())) return true;
1.887 + if (do_list(tl)) return true;
1.888 + if (do_tree(tl->right())) return true;
1.889 + }
1.890 + return false;
1.891 + }
1.892 +};
1.893 +#endif
1.894 +
1.895 +class DescendTreeSearchClosure : public TreeSearchClosure {
1.896 + public:
1.897 + bool do_tree(TreeList* tl) {
1.898 + if (tl != NULL) {
1.899 + if (do_tree(tl->right())) return true;
1.900 + if (do_list(tl)) return true;
1.901 + if (do_tree(tl->left())) return true;
1.902 + }
1.903 + return false;
1.904 + }
1.905 +};
1.906 +
1.907 +// Searches the tree for a chunk that ends at the
1.908 +// specified address.
1.909 +class EndTreeSearchClosure : public DescendTreeSearchClosure {
1.910 + HeapWord* _target;
1.911 + FreeChunk* _found;
1.912 +
1.913 + public:
1.914 + EndTreeSearchClosure(HeapWord* target) : _target(target), _found(NULL) {}
1.915 + bool do_list(FreeList* fl) {
1.916 + FreeChunk* item = fl->head();
1.917 + while (item != NULL) {
1.918 + if (item->end() == _target) {
1.919 + _found = item;
1.920 + return true;
1.921 + }
1.922 + item = item->next();
1.923 + }
1.924 + return false;
1.925 + }
1.926 + FreeChunk* found() { return _found; }
1.927 +};
1.928 +
1.929 +FreeChunk* BinaryTreeDictionary::find_chunk_ends_at(HeapWord* target) const {
1.930 + EndTreeSearchClosure etsc(target);
1.931 + bool found_target = etsc.do_tree(root());
1.932 + assert(found_target || etsc.found() == NULL, "Consistency check");
1.933 + assert(!found_target || etsc.found() != NULL, "Consistency check");
1.934 + return etsc.found();
1.935 +}
1.936 +
1.937 +void BinaryTreeDictionary::beginSweepDictCensus(double coalSurplusPercent,
1.938 + float inter_sweep_current, float inter_sweep_estimate) {
1.939 + BeginSweepClosure bsc(coalSurplusPercent, inter_sweep_current,
1.940 + inter_sweep_estimate);
1.941 + bsc.do_tree(root());
1.942 +}
1.943 +
1.944 +// Closures and methods for calculating total bytes returned to the
1.945 +// free lists in the tree.
1.946 +NOT_PRODUCT(
1.947 + class InitializeDictReturnedBytesClosure : public AscendTreeCensusClosure {
1.948 + public:
1.949 + void do_list(FreeList* fl) {
1.950 + fl->set_returnedBytes(0);
1.951 + }
1.952 + };
1.953 +
1.954 + void BinaryTreeDictionary::initializeDictReturnedBytes() {
1.955 + InitializeDictReturnedBytesClosure idrb;
1.956 + idrb.do_tree(root());
1.957 + }
1.958 +
1.959 + class ReturnedBytesClosure : public AscendTreeCensusClosure {
1.960 + size_t _dictReturnedBytes;
1.961 + public:
1.962 + ReturnedBytesClosure() { _dictReturnedBytes = 0; }
1.963 + void do_list(FreeList* fl) {
1.964 + _dictReturnedBytes += fl->returnedBytes();
1.965 + }
1.966 + size_t dictReturnedBytes() { return _dictReturnedBytes; }
1.967 + };
1.968 +
1.969 + size_t BinaryTreeDictionary::sumDictReturnedBytes() {
1.970 + ReturnedBytesClosure rbc;
1.971 + rbc.do_tree(root());
1.972 +
1.973 + return rbc.dictReturnedBytes();
1.974 + }
1.975 +
1.976 + // Count the number of entries in the tree.
1.977 + class treeCountClosure : public DescendTreeCensusClosure {
1.978 + public:
1.979 + uint count;
1.980 + treeCountClosure(uint c) { count = c; }
1.981 + void do_list(FreeList* fl) {
1.982 + count++;
1.983 + }
1.984 + };
1.985 +
1.986 + size_t BinaryTreeDictionary::totalCount() {
1.987 + treeCountClosure ctc(0);
1.988 + ctc.do_tree(root());
1.989 + return ctc.count;
1.990 + }
1.991 +)
1.992 +
1.993 +// Calculate surpluses for the lists in the tree.
1.994 +class setTreeSurplusClosure : public AscendTreeCensusClosure {
1.995 + double percentage;
1.996 + public:
1.997 + setTreeSurplusClosure(double v) { percentage = v; }
1.998 + void do_list(FreeList* fl) {
1.999 + double splitSurplusPercent = percentage;
1.1000 + fl->set_surplus(fl->count() -
1.1001 + (ssize_t)((double)fl->desired() * splitSurplusPercent));
1.1002 + }
1.1003 +};
1.1004 +
1.1005 +void BinaryTreeDictionary::setTreeSurplus(double splitSurplusPercent) {
1.1006 + setTreeSurplusClosure sts(splitSurplusPercent);
1.1007 + sts.do_tree(root());
1.1008 +}
1.1009 +
1.1010 +// Set hints for the lists in the tree.
1.1011 +class setTreeHintsClosure : public DescendTreeCensusClosure {
1.1012 + size_t hint;
1.1013 + public:
1.1014 + setTreeHintsClosure(size_t v) { hint = v; }
1.1015 + void do_list(FreeList* fl) {
1.1016 + fl->set_hint(hint);
1.1017 + assert(fl->hint() == 0 || fl->hint() > fl->size(),
1.1018 + "Current hint is inconsistent");
1.1019 + if (fl->surplus() > 0) {
1.1020 + hint = fl->size();
1.1021 + }
1.1022 + }
1.1023 +};
1.1024 +
1.1025 +void BinaryTreeDictionary::setTreeHints(void) {
1.1026 + setTreeHintsClosure sth(0);
1.1027 + sth.do_tree(root());
1.1028 +}
1.1029 +
1.1030 +// Save count before previous sweep and splits and coalesces.
1.1031 +class clearTreeCensusClosure : public AscendTreeCensusClosure {
1.1032 + void do_list(FreeList* fl) {
1.1033 + fl->set_prevSweep(fl->count());
1.1034 + fl->set_coalBirths(0);
1.1035 + fl->set_coalDeaths(0);
1.1036 + fl->set_splitBirths(0);
1.1037 + fl->set_splitDeaths(0);
1.1038 + }
1.1039 +};
1.1040 +
1.1041 +void BinaryTreeDictionary::clearTreeCensus(void) {
1.1042 + clearTreeCensusClosure ctc;
1.1043 + ctc.do_tree(root());
1.1044 +}
1.1045 +
1.1046 +// Do reporting and post sweep clean up.
1.1047 +void BinaryTreeDictionary::endSweepDictCensus(double splitSurplusPercent) {
1.1048 + // Does walking the tree 3 times hurt?
1.1049 + setTreeSurplus(splitSurplusPercent);
1.1050 + setTreeHints();
1.1051 + if (PrintGC && Verbose) {
1.1052 + reportStatistics();
1.1053 + }
1.1054 + clearTreeCensus();
1.1055 +}
1.1056 +
1.1057 +// Print summary statistics
1.1058 +void BinaryTreeDictionary::reportStatistics() const {
1.1059 + verify_par_locked();
1.1060 + gclog_or_tty->print("Statistics for BinaryTreeDictionary:\n"
1.1061 + "------------------------------------\n");
1.1062 + size_t totalSize = totalChunkSize(debug_only(NULL));
1.1063 + size_t freeBlocks = numFreeBlocks();
1.1064 + gclog_or_tty->print("Total Free Space: %d\n", totalSize);
1.1065 + gclog_or_tty->print("Max Chunk Size: %d\n", maxChunkSize());
1.1066 + gclog_or_tty->print("Number of Blocks: %d\n", freeBlocks);
1.1067 + if (freeBlocks > 0) {
1.1068 + gclog_or_tty->print("Av. Block Size: %d\n", totalSize/freeBlocks);
1.1069 + }
1.1070 + gclog_or_tty->print("Tree Height: %d\n", treeHeight());
1.1071 +}
1.1072 +
1.1073 +// Print census information - counts, births, deaths, etc.
1.1074 +// for each list in the tree. Also print some summary
1.1075 +// information.
1.1076 +class printTreeCensusClosure : public AscendTreeCensusClosure {
1.1077 + size_t _totalFree;
1.1078 + AllocationStats _totals;
1.1079 + size_t _count;
1.1080 +
1.1081 + public:
1.1082 + printTreeCensusClosure() {
1.1083 + _totalFree = 0;
1.1084 + _count = 0;
1.1085 + _totals.initialize();
1.1086 + }
1.1087 + AllocationStats* totals() { return &_totals; }
1.1088 + size_t count() { return _count; }
1.1089 + void increment_count_by(size_t v) { _count += v; }
1.1090 + size_t totalFree() { return _totalFree; }
1.1091 + void increment_totalFree_by(size_t v) { _totalFree += v; }
1.1092 + void do_list(FreeList* fl) {
1.1093 + bool nl = false; // "maybe this is not needed" isNearLargestChunk(fl->head());
1.1094 +
1.1095 + gclog_or_tty->print("%c %4d\t\t" "%7d\t" "%7d\t"
1.1096 + "%7d\t" "%7d\t" "%7d\t" "%7d\t"
1.1097 + "%7d\t" "%7d\t" "%7d\t"
1.1098 + "%7d\t" "\n",
1.1099 + " n"[nl], fl->size(), fl->bfrSurp(), fl->surplus(),
1.1100 + fl->desired(), fl->prevSweep(), fl->beforeSweep(), fl->count(),
1.1101 + fl->coalBirths(), fl->coalDeaths(), fl->splitBirths(),
1.1102 + fl->splitDeaths());
1.1103 +
1.1104 + increment_totalFree_by(fl->count() * fl->size());
1.1105 + increment_count_by(fl->count());
1.1106 + totals()->set_bfrSurp(totals()->bfrSurp() + fl->bfrSurp());
1.1107 + totals()->set_surplus(totals()->splitDeaths() + fl->surplus());
1.1108 + totals()->set_prevSweep(totals()->prevSweep() + fl->prevSweep());
1.1109 + totals()->set_beforeSweep(totals()->beforeSweep() + fl->beforeSweep());
1.1110 + totals()->set_coalBirths(totals()->coalBirths() + fl->coalBirths());
1.1111 + totals()->set_coalDeaths(totals()->coalDeaths() + fl->coalDeaths());
1.1112 + totals()->set_splitBirths(totals()->splitBirths() + fl->splitBirths());
1.1113 + totals()->set_splitDeaths(totals()->splitDeaths() + fl->splitDeaths());
1.1114 + }
1.1115 +};
1.1116 +
1.1117 +void BinaryTreeDictionary::printDictCensus(void) const {
1.1118 +
1.1119 + gclog_or_tty->print("\nBinaryTree\n");
1.1120 + gclog_or_tty->print(
1.1121 + "%4s\t\t" "%7s\t" "%7s\t" "%7s\t" "%7s\t" "%7s\t"
1.1122 + "%7s\t" "%7s\t" "%7s\t" "%7s\t" "%7s\t" "\n",
1.1123 + "size", "bfrsurp", "surplus", "desired", "prvSwep", "bfrSwep",
1.1124 + "count", "cBirths", "cDeaths", "sBirths", "sDeaths");
1.1125 +
1.1126 + printTreeCensusClosure ptc;
1.1127 + ptc.do_tree(root());
1.1128 +
1.1129 + gclog_or_tty->print(
1.1130 + "\t\t" "%7s\t" "%7s\t" "%7s\t" "%7s\t"
1.1131 + "%7s\t" "%7s\t" "%7s\t" "%7s\t" "%7s\t" "\n",
1.1132 + "bfrsurp", "surplus", "prvSwep", "bfrSwep",
1.1133 + "count", "cBirths", "cDeaths", "sBirths", "sDeaths");
1.1134 + gclog_or_tty->print(
1.1135 + "%s\t\t" "%7d\t" "%7d\t" "%7d\t" "%7d\t"
1.1136 + "%7d\t" "%7d\t" "%7d\t" "%7d\t" "%7d\t" "\n",
1.1137 + "totl",
1.1138 + ptc.totals()->bfrSurp(),
1.1139 + ptc.totals()->surplus(),
1.1140 + ptc.totals()->prevSweep(),
1.1141 + ptc.totals()->beforeSweep(),
1.1142 + ptc.count(),
1.1143 + ptc.totals()->coalBirths(),
1.1144 + ptc.totals()->coalDeaths(),
1.1145 + ptc.totals()->splitBirths(),
1.1146 + ptc.totals()->splitDeaths());
1.1147 + gclog_or_tty->print("totalFree(words): %7d growth: %8.5f deficit: %8.5f\n",
1.1148 + ptc.totalFree(),
1.1149 + (double)(ptc.totals()->splitBirths()+ptc.totals()->coalBirths()
1.1150 + -ptc.totals()->splitDeaths()-ptc.totals()->coalDeaths())
1.1151 + /(ptc.totals()->prevSweep() != 0 ?
1.1152 + (double)ptc.totals()->prevSweep() : 1.0),
1.1153 + (double)(ptc.totals()->desired() - ptc.count())
1.1154 + /(ptc.totals()->desired() != 0 ?
1.1155 + (double)ptc.totals()->desired() : 1.0));
1.1156 +}
1.1157 +
1.1158 +// Verify the following tree invariants:
1.1159 +// . _root has no parent
1.1160 +// . parent and child point to each other
1.1161 +// . each node's key correctly related to that of its child(ren)
1.1162 +void BinaryTreeDictionary::verifyTree() const {
1.1163 + guarantee(root() == NULL || totalFreeBlocks() == 0 ||
1.1164 + totalSize() != 0, "_totalSize should't be 0?");
1.1165 + guarantee(root() == NULL || root()->parent() == NULL, "_root shouldn't have parent");
1.1166 + verifyTreeHelper(root());
1.1167 +}
1.1168 +
1.1169 +size_t BinaryTreeDictionary::verifyPrevFreePtrs(TreeList* tl) {
1.1170 + size_t ct = 0;
1.1171 + for (FreeChunk* curFC = tl->head(); curFC != NULL; curFC = curFC->next()) {
1.1172 + ct++;
1.1173 + assert(curFC->prev() == NULL || curFC->prev()->isFree(),
1.1174 + "Chunk should be free");
1.1175 + }
1.1176 + return ct;
1.1177 +}
1.1178 +
1.1179 +// Note: this helper is recursive rather than iterative, so use with
1.1180 +// caution on very deep trees; and watch out for stack overflow errors;
1.1181 +// In general, to be used only for debugging.
1.1182 +void BinaryTreeDictionary::verifyTreeHelper(TreeList* tl) const {
1.1183 + if (tl == NULL)
1.1184 + return;
1.1185 + guarantee(tl->size() != 0, "A list must has a size");
1.1186 + guarantee(tl->left() == NULL || tl->left()->parent() == tl,
1.1187 + "parent<-/->left");
1.1188 + guarantee(tl->right() == NULL || tl->right()->parent() == tl,
1.1189 + "parent<-/->right");;
1.1190 + guarantee(tl->left() == NULL || tl->left()->size() < tl->size(),
1.1191 + "parent !> left");
1.1192 + guarantee(tl->right() == NULL || tl->right()->size() > tl->size(),
1.1193 + "parent !< left");
1.1194 + guarantee(tl->head() == NULL || tl->head()->isFree(), "!Free");
1.1195 + guarantee(tl->head() == NULL || tl->head_as_TreeChunk()->list() == tl,
1.1196 + "list inconsistency");
1.1197 + guarantee(tl->count() > 0 || (tl->head() == NULL && tl->tail() == NULL),
1.1198 + "list count is inconsistent");
1.1199 + guarantee(tl->count() > 1 || tl->head() == tl->tail(),
1.1200 + "list is incorrectly constructed");
1.1201 + size_t count = verifyPrevFreePtrs(tl);
1.1202 + guarantee(count == (size_t)tl->count(), "Node count is incorrect");
1.1203 + if (tl->head() != NULL) {
1.1204 + tl->head_as_TreeChunk()->verifyTreeChunkList();
1.1205 + }
1.1206 + verifyTreeHelper(tl->left());
1.1207 + verifyTreeHelper(tl->right());
1.1208 +}
1.1209 +
1.1210 +void BinaryTreeDictionary::verify() const {
1.1211 + verifyTree();
1.1212 + guarantee(totalSize() == totalSizeInTree(root()), "Total Size inconsistency");
1.1213 +}
