1 /*
2 * Copyright (c) 2001, 2010, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #include "precompiled.hpp"
26 #include "gc_implementation/concurrentMarkSweep/binaryTreeDictionary.hpp"
27 #include "gc_implementation/shared/allocationStats.hpp"
28 #include "gc_implementation/shared/spaceDecorator.hpp"
29 #include "memory/space.inline.hpp"
30 #include "runtime/globals.hpp"
31 #include "utilities/ostream.hpp"
32
33 ////////////////////////////////////////////////////////////////////////////////
34 // A binary tree based search structure for free blocks.
35 // This is currently used in the Concurrent Mark&Sweep implementation.
36 ////////////////////////////////////////////////////////////////////////////////
37
38 TreeChunk* TreeChunk::as_TreeChunk(FreeChunk* fc) {
39 // Do some assertion checking here.
40 return (TreeChunk*) fc;
41 }
42
43 void TreeChunk::verifyTreeChunkList() const {
44 TreeChunk* nextTC = (TreeChunk*)next();
45 if (prev() != NULL) { // interior list node shouldn'r have tree fields
46 guarantee(embedded_list()->parent() == NULL && embedded_list()->left() == NULL &&
47 embedded_list()->right() == NULL, "should be clear");
48 }
49 if (nextTC != NULL) {
50 guarantee(as_TreeChunk(nextTC->prev()) == this, "broken chain");
51 guarantee(nextTC->size() == size(), "wrong size");
52 nextTC->verifyTreeChunkList();
53 }
54 }
55
56
57 TreeList* TreeList::as_TreeList(TreeChunk* tc) {
58 // This first free chunk in the list will be the tree list.
59 assert(tc->size() >= sizeof(TreeChunk), "Chunk is too small for a TreeChunk");
60 TreeList* tl = tc->embedded_list();
61 tc->set_list(tl);
62 #ifdef ASSERT
63 tl->set_protecting_lock(NULL);
64 #endif
65 tl->set_hint(0);
66 tl->set_size(tc->size());
67 tl->link_head(tc);
68 tl->link_tail(tc);
69 tl->set_count(1);
70 tl->init_statistics(true /* split_birth */);
71 tl->setParent(NULL);
72 tl->setLeft(NULL);
73 tl->setRight(NULL);
74 return tl;
75 }
76
77 TreeList* TreeList::as_TreeList(HeapWord* addr, size_t size) {
78 TreeChunk* tc = (TreeChunk*) addr;
79 assert(size >= sizeof(TreeChunk), "Chunk is too small for a TreeChunk");
80 // The space in the heap will have been mangled initially but
81 // is not remangled when a free chunk is returned to the free list
82 // (since it is used to maintain the chunk on the free list).
83 assert((ZapUnusedHeapArea &&
84 SpaceMangler::is_mangled((HeapWord*) tc->size_addr()) &&
85 SpaceMangler::is_mangled((HeapWord*) tc->prev_addr()) &&
86 SpaceMangler::is_mangled((HeapWord*) tc->next_addr())) ||
87 (tc->size() == 0 && tc->prev() == NULL && tc->next() == NULL),
88 "Space should be clear or mangled");
89 tc->setSize(size);
90 tc->linkPrev(NULL);
91 tc->linkNext(NULL);
92 TreeList* tl = TreeList::as_TreeList(tc);
93 return tl;
94 }
95
96 TreeList* TreeList::removeChunkReplaceIfNeeded(TreeChunk* tc) {
97
98 TreeList* retTL = this;
99 FreeChunk* list = head();
100 assert(!list || list != list->next(), "Chunk on list twice");
101 assert(tc != NULL, "Chunk being removed is NULL");
102 assert(parent() == NULL || this == parent()->left() ||
103 this == parent()->right(), "list is inconsistent");
104 assert(tc->isFree(), "Header is not marked correctly");
105 assert(head() == NULL || head()->prev() == NULL, "list invariant");
106 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
107
108 FreeChunk* prevFC = tc->prev();
109 TreeChunk* nextTC = TreeChunk::as_TreeChunk(tc->next());
110 assert(list != NULL, "should have at least the target chunk");
111
112 // Is this the first item on the list?
113 if (tc == list) {
114 // The "getChunk..." functions for a TreeList will not return the
115 // first chunk in the list unless it is the last chunk in the list
116 // because the first chunk is also acting as the tree node.
117 // When coalescing happens, however, the first chunk in the a tree
118 // list can be the start of a free range. Free ranges are removed
119 // from the free lists so that they are not available to be
120 // allocated when the sweeper yields (giving up the free list lock)
121 // to allow mutator activity. If this chunk is the first in the
122 // list and is not the last in the list, do the work to copy the
123 // TreeList from the first chunk to the next chunk and update all
124 // the TreeList pointers in the chunks in the list.
125 if (nextTC == NULL) {
126 assert(prevFC == NULL, "Not last chunk in the list");
127 set_tail(NULL);
128 set_head(NULL);
129 } else {
130 // copy embedded list.
131 nextTC->set_embedded_list(tc->embedded_list());
132 retTL = nextTC->embedded_list();
133 // Fix the pointer to the list in each chunk in the list.
134 // This can be slow for a long list. Consider having
135 // an option that does not allow the first chunk on the
136 // list to be coalesced.
137 for (TreeChunk* curTC = nextTC; curTC != NULL;
138 curTC = TreeChunk::as_TreeChunk(curTC->next())) {
139 curTC->set_list(retTL);
140 }
141 // Fix the parent to point to the new TreeList.
142 if (retTL->parent() != NULL) {
143 if (this == retTL->parent()->left()) {
144 retTL->parent()->setLeft(retTL);
145 } else {
146 assert(this == retTL->parent()->right(), "Parent is incorrect");
147 retTL->parent()->setRight(retTL);
148 }
149 }
150 // Fix the children's parent pointers to point to the
151 // new list.
152 assert(right() == retTL->right(), "Should have been copied");
153 if (retTL->right() != NULL) {
154 retTL->right()->setParent(retTL);
155 }
156 assert(left() == retTL->left(), "Should have been copied");
157 if (retTL->left() != NULL) {
158 retTL->left()->setParent(retTL);
159 }
160 retTL->link_head(nextTC);
161 assert(nextTC->isFree(), "Should be a free chunk");
162 }
163 } else {
164 if (nextTC == NULL) {
165 // Removing chunk at tail of list
166 link_tail(prevFC);
167 }
168 // Chunk is interior to the list
169 prevFC->linkAfter(nextTC);
170 }
171
172 // Below this point the embeded TreeList being used for the
173 // tree node may have changed. Don't use "this"
174 // TreeList*.
175 // chunk should still be a free chunk (bit set in _prev)
176 assert(!retTL->head() || retTL->size() == retTL->head()->size(),
177 "Wrong sized chunk in list");
178 debug_only(
179 tc->linkPrev(NULL);
180 tc->linkNext(NULL);
181 tc->set_list(NULL);
182 bool prev_found = false;
183 bool next_found = false;
184 for (FreeChunk* curFC = retTL->head();
185 curFC != NULL; curFC = curFC->next()) {
186 assert(curFC != tc, "Chunk is still in list");
187 if (curFC == prevFC) {
188 prev_found = true;
189 }
190 if (curFC == nextTC) {
191 next_found = true;
192 }
193 }
194 assert(prevFC == NULL || prev_found, "Chunk was lost from list");
195 assert(nextTC == NULL || next_found, "Chunk was lost from list");
196 assert(retTL->parent() == NULL ||
197 retTL == retTL->parent()->left() ||
198 retTL == retTL->parent()->right(),
199 "list is inconsistent");
200 )
201 retTL->decrement_count();
202
203 assert(tc->isFree(), "Should still be a free chunk");
204 assert(retTL->head() == NULL || retTL->head()->prev() == NULL,
205 "list invariant");
206 assert(retTL->tail() == NULL || retTL->tail()->next() == NULL,
207 "list invariant");
208 return retTL;
209 }
210 void TreeList::returnChunkAtTail(TreeChunk* chunk) {
211 assert(chunk != NULL, "returning NULL chunk");
212 assert(chunk->list() == this, "list should be set for chunk");
213 assert(tail() != NULL, "The tree list is embedded in the first chunk");
214 // which means that the list can never be empty.
215 assert(!verifyChunkInFreeLists(chunk), "Double entry");
216 assert(head() == NULL || head()->prev() == NULL, "list invariant");
217 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
218
219 FreeChunk* fc = tail();
220 fc->linkAfter(chunk);
221 link_tail(chunk);
222
223 assert(!tail() || size() == tail()->size(), "Wrong sized chunk in list");
224 increment_count();
225 debug_only(increment_returnedBytes_by(chunk->size()*sizeof(HeapWord));)
226 assert(head() == NULL || head()->prev() == NULL, "list invariant");
227 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
228 }
229
230 // Add this chunk at the head of the list. "At the head of the list"
231 // is defined to be after the chunk pointer to by head(). This is
232 // because the TreeList is embedded in the first TreeChunk in the
233 // list. See the definition of TreeChunk.
234 void TreeList::returnChunkAtHead(TreeChunk* chunk) {
235 assert(chunk->list() == this, "list should be set for chunk");
236 assert(head() != NULL, "The tree list is embedded in the first chunk");
237 assert(chunk != NULL, "returning NULL chunk");
238 assert(!verifyChunkInFreeLists(chunk), "Double entry");
239 assert(head() == NULL || head()->prev() == NULL, "list invariant");
240 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
241
242 FreeChunk* fc = head()->next();
243 if (fc != NULL) {
244 chunk->linkAfter(fc);
245 } else {
246 assert(tail() == NULL, "List is inconsistent");
247 link_tail(chunk);
248 }
249 head()->linkAfter(chunk);
250 assert(!head() || size() == head()->size(), "Wrong sized chunk in list");
251 increment_count();
252 debug_only(increment_returnedBytes_by(chunk->size()*sizeof(HeapWord));)
253 assert(head() == NULL || head()->prev() == NULL, "list invariant");
254 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
255 }
256
257 TreeChunk* TreeList::head_as_TreeChunk() {
258 assert(head() == NULL || TreeChunk::as_TreeChunk(head())->list() == this,
259 "Wrong type of chunk?");
260 return TreeChunk::as_TreeChunk(head());
261 }
262
263 TreeChunk* TreeList::first_available() {
264 assert(head() != NULL, "The head of the list cannot be NULL");
265 FreeChunk* fc = head()->next();
266 TreeChunk* retTC;
267 if (fc == NULL) {
268 retTC = head_as_TreeChunk();
269 } else {
270 retTC = TreeChunk::as_TreeChunk(fc);
271 }
272 assert(retTC->list() == this, "Wrong type of chunk.");
273 return retTC;
274 }
275
276 // Returns the block with the largest heap address amongst
277 // those in the list for this size; potentially slow and expensive,
278 // use with caution!
279 TreeChunk* TreeList::largest_address() {
280 assert(head() != NULL, "The head of the list cannot be NULL");
281 FreeChunk* fc = head()->next();
282 TreeChunk* retTC;
283 if (fc == NULL) {
284 retTC = head_as_TreeChunk();
285 } else {
286 // walk down the list and return the one with the highest
287 // heap address among chunks of this size.
288 FreeChunk* last = fc;
289 while (fc->next() != NULL) {
290 if ((HeapWord*)last < (HeapWord*)fc) {
291 last = fc;
292 }
293 fc = fc->next();
294 }
295 retTC = TreeChunk::as_TreeChunk(last);
296 }
297 assert(retTC->list() == this, "Wrong type of chunk.");
298 return retTC;
299 }
300
301 BinaryTreeDictionary::BinaryTreeDictionary(MemRegion mr, bool splay):
302 _splay(splay)
303 {
304 assert(mr.byte_size() > MIN_TREE_CHUNK_SIZE, "minimum chunk size");
305
306 reset(mr);
307 assert(root()->left() == NULL, "reset check failed");
308 assert(root()->right() == NULL, "reset check failed");
309 assert(root()->head()->next() == NULL, "reset check failed");
310 assert(root()->head()->prev() == NULL, "reset check failed");
311 assert(totalSize() == root()->size(), "reset check failed");
312 assert(totalFreeBlocks() == 1, "reset check failed");
313 }
314
315 void BinaryTreeDictionary::inc_totalSize(size_t inc) {
316 _totalSize = _totalSize + inc;
317 }
318
319 void BinaryTreeDictionary::dec_totalSize(size_t dec) {
320 _totalSize = _totalSize - dec;
321 }
322
323 void BinaryTreeDictionary::reset(MemRegion mr) {
324 assert(mr.byte_size() > MIN_TREE_CHUNK_SIZE, "minimum chunk size");
325 set_root(TreeList::as_TreeList(mr.start(), mr.word_size()));
326 set_totalSize(mr.word_size());
327 set_totalFreeBlocks(1);
328 }
329
330 void BinaryTreeDictionary::reset(HeapWord* addr, size_t byte_size) {
331 MemRegion mr(addr, heap_word_size(byte_size));
332 reset(mr);
333 }
334
335 void BinaryTreeDictionary::reset() {
336 set_root(NULL);
337 set_totalSize(0);
338 set_totalFreeBlocks(0);
339 }
340
341 // Get a free block of size at least size from tree, or NULL.
342 // If a splay step is requested, the removal algorithm (only) incorporates
343 // a splay step as follows:
344 // . the search proceeds down the tree looking for a possible
345 // match. At the (closest) matching location, an appropriate splay step is applied
346 // (zig, zig-zig or zig-zag). A chunk of the appropriate size is then returned
347 // if available, and if it's the last chunk, the node is deleted. A deteleted
348 // node is replaced in place by its tree successor.
349 TreeChunk*
350 BinaryTreeDictionary::getChunkFromTree(size_t size, Dither dither, bool splay)
351 {
352 TreeList *curTL, *prevTL;
353 TreeChunk* retTC = NULL;
354 assert(size >= MIN_TREE_CHUNK_SIZE, "minimum chunk size");
355 if (FLSVerifyDictionary) {
356 verifyTree();
357 }
358 // starting at the root, work downwards trying to find match.
359 // Remember the last node of size too great or too small.
360 for (prevTL = curTL = root(); curTL != NULL;) {
361 if (curTL->size() == size) { // exact match
362 break;
363 }
364 prevTL = curTL;
365 if (curTL->size() < size) { // proceed to right sub-tree
366 curTL = curTL->right();
367 } else { // proceed to left sub-tree
368 assert(curTL->size() > size, "size inconsistency");
369 curTL = curTL->left();
370 }
371 }
372 if (curTL == NULL) { // couldn't find exact match
373 // try and find the next larger size by walking back up the search path
374 for (curTL = prevTL; curTL != NULL;) {
375 if (curTL->size() >= size) break;
376 else curTL = curTL->parent();
377 }
378 assert(curTL == NULL || curTL->count() > 0,
379 "An empty list should not be in the tree");
380 }
381 if (curTL != NULL) {
382 assert(curTL->size() >= size, "size inconsistency");
383 if (UseCMSAdaptiveFreeLists) {
384
385 // A candidate chunk has been found. If it is already under
386 // populated, get a chunk associated with the hint for this
387 // chunk.
388 if (curTL->surplus() <= 0) {
389 /* Use the hint to find a size with a surplus, and reset the hint. */
390 TreeList* hintTL = curTL;
391 while (hintTL->hint() != 0) {
392 assert(hintTL->hint() == 0 || hintTL->hint() > hintTL->size(),
393 "hint points in the wrong direction");
394 hintTL = findList(hintTL->hint());
395 assert(curTL != hintTL, "Infinite loop");
396 if (hintTL == NULL ||
397 hintTL == curTL /* Should not happen but protect against it */ ) {
398 // No useful hint. Set the hint to NULL and go on.
399 curTL->set_hint(0);
400 break;
401 }
402 assert(hintTL->size() > size, "hint is inconsistent");
403 if (hintTL->surplus() > 0) {
404 // The hint led to a list that has a surplus. Use it.
405 // Set the hint for the candidate to an overpopulated
406 // size.
407 curTL->set_hint(hintTL->size());
408 // Change the candidate.
409 curTL = hintTL;
410 break;
411 }
412 // The evm code reset the hint of the candidate as
413 // at an interim point. Why? Seems like this leaves
414 // the hint pointing to a list that didn't work.
415 // curTL->set_hint(hintTL->size());
416 }
417 }
418 }
419 // don't waste time splaying if chunk's singleton
420 if (splay && curTL->head()->next() != NULL) {
421 semiSplayStep(curTL);
422 }
423 retTC = curTL->first_available();
424 assert((retTC != NULL) && (curTL->count() > 0),
425 "A list in the binary tree should not be NULL");
426 assert(retTC->size() >= size,
427 "A chunk of the wrong size was found");
428 removeChunkFromTree(retTC);
429 assert(retTC->isFree(), "Header is not marked correctly");
430 }
431
432 if (FLSVerifyDictionary) {
433 verify();
434 }
435 return retTC;
436 }
437
438 TreeList* BinaryTreeDictionary::findList(size_t size) const {
439 TreeList* curTL;
440 for (curTL = root(); curTL != NULL;) {
441 if (curTL->size() == size) { // exact match
442 break;
443 }
444
445 if (curTL->size() < size) { // proceed to right sub-tree
446 curTL = curTL->right();
447 } else { // proceed to left sub-tree
448 assert(curTL->size() > size, "size inconsistency");
449 curTL = curTL->left();
450 }
451 }
452 return curTL;
453 }
454
455
456 bool BinaryTreeDictionary::verifyChunkInFreeLists(FreeChunk* tc) const {
457 size_t size = tc->size();
458 TreeList* tl = findList(size);
459 if (tl == NULL) {
460 return false;
461 } else {
462 return tl->verifyChunkInFreeLists(tc);
463 }
464 }
465
466 FreeChunk* BinaryTreeDictionary::findLargestDict() const {
467 TreeList *curTL = root();
468 if (curTL != NULL) {
469 while(curTL->right() != NULL) curTL = curTL->right();
470 return curTL->largest_address();
471 } else {
472 return NULL;
473 }
474 }
475
476 // Remove the current chunk from the tree. If it is not the last
477 // chunk in a list on a tree node, just unlink it.
478 // If it is the last chunk in the list (the next link is NULL),
479 // remove the node and repair the tree.
480 TreeChunk*
481 BinaryTreeDictionary::removeChunkFromTree(TreeChunk* tc) {
482 assert(tc != NULL, "Should not call with a NULL chunk");
483 assert(tc->isFree(), "Header is not marked correctly");
484
485 TreeList *newTL, *parentTL;
486 TreeChunk* retTC;
487 TreeList* tl = tc->list();
488 debug_only(
489 bool removing_only_chunk = false;
490 if (tl == _root) {
491 if ((_root->left() == NULL) && (_root->right() == NULL)) {
492 if (_root->count() == 1) {
493 assert(_root->head() == tc, "Should only be this one chunk");
494 removing_only_chunk = true;
495 }
496 }
497 }
498 )
499 assert(tl != NULL, "List should be set");
500 assert(tl->parent() == NULL || tl == tl->parent()->left() ||
501 tl == tl->parent()->right(), "list is inconsistent");
502
503 bool complicatedSplice = false;
504
505 retTC = tc;
506 // Removing this chunk can have the side effect of changing the node
507 // (TreeList*) in the tree. If the node is the root, update it.
508 TreeList* replacementTL = tl->removeChunkReplaceIfNeeded(tc);
509 assert(tc->isFree(), "Chunk should still be free");
510 assert(replacementTL->parent() == NULL ||
511 replacementTL == replacementTL->parent()->left() ||
512 replacementTL == replacementTL->parent()->right(),
513 "list is inconsistent");
514 if (tl == root()) {
515 assert(replacementTL->parent() == NULL, "Incorrectly replacing root");
516 set_root(replacementTL);
517 }
518 debug_only(
519 if (tl != replacementTL) {
520 assert(replacementTL->head() != NULL,
521 "If the tree list was replaced, it should not be a NULL list");
522 TreeList* rhl = replacementTL->head_as_TreeChunk()->list();
523 TreeList* rtl = TreeChunk::as_TreeChunk(replacementTL->tail())->list();
524 assert(rhl == replacementTL, "Broken head");
525 assert(rtl == replacementTL, "Broken tail");
526 assert(replacementTL->size() == tc->size(), "Broken size");
527 }
528 )
529
530 // Does the tree need to be repaired?
531 if (replacementTL->count() == 0) {
532 assert(replacementTL->head() == NULL &&
533 replacementTL->tail() == NULL, "list count is incorrect");
534 // Find the replacement node for the (soon to be empty) node being removed.
535 // if we have a single (or no) child, splice child in our stead
536 if (replacementTL->left() == NULL) {
537 // left is NULL so pick right. right may also be NULL.
538 newTL = replacementTL->right();
539 debug_only(replacementTL->clearRight();)
540 } else if (replacementTL->right() == NULL) {
541 // right is NULL
542 newTL = replacementTL->left();
543 debug_only(replacementTL->clearLeft();)
544 } else { // we have both children, so, by patriarchal convention,
545 // my replacement is least node in right sub-tree
546 complicatedSplice = true;
547 newTL = removeTreeMinimum(replacementTL->right());
548 assert(newTL != NULL && newTL->left() == NULL &&
549 newTL->right() == NULL, "sub-tree minimum exists");
550 }
551 // newTL is the replacement for the (soon to be empty) node.
552 // newTL may be NULL.
553 // should verify; we just cleanly excised our replacement
554 if (FLSVerifyDictionary) {
555 verifyTree();
556 }
557 // first make newTL my parent's child
558 if ((parentTL = replacementTL->parent()) == NULL) {
559 // newTL should be root
560 assert(tl == root(), "Incorrectly replacing root");
561 set_root(newTL);
562 if (newTL != NULL) {
563 newTL->clearParent();
564 }
565 } else if (parentTL->right() == replacementTL) {
566 // replacementTL is a right child
567 parentTL->setRight(newTL);
568 } else { // replacementTL is a left child
569 assert(parentTL->left() == replacementTL, "should be left child");
570 parentTL->setLeft(newTL);
571 }
572 debug_only(replacementTL->clearParent();)
573 if (complicatedSplice) { // we need newTL to get replacementTL's
574 // two children
575 assert(newTL != NULL &&
576 newTL->left() == NULL && newTL->right() == NULL,
577 "newTL should not have encumbrances from the past");
578 // we'd like to assert as below:
579 // assert(replacementTL->left() != NULL && replacementTL->right() != NULL,
580 // "else !complicatedSplice");
581 // ... however, the above assertion is too strong because we aren't
582 // guaranteed that replacementTL->right() is still NULL.
583 // Recall that we removed
584 // the right sub-tree minimum from replacementTL.
585 // That may well have been its right
586 // child! So we'll just assert half of the above:
587 assert(replacementTL->left() != NULL, "else !complicatedSplice");
588 newTL->setLeft(replacementTL->left());
589 newTL->setRight(replacementTL->right());
590 debug_only(
591 replacementTL->clearRight();
592 replacementTL->clearLeft();
593 )
594 }
595 assert(replacementTL->right() == NULL &&
596 replacementTL->left() == NULL &&
597 replacementTL->parent() == NULL,
598 "delete without encumbrances");
599 }
600
601 assert(totalSize() >= retTC->size(), "Incorrect total size");
602 dec_totalSize(retTC->size()); // size book-keeping
603 assert(totalFreeBlocks() > 0, "Incorrect total count");
604 set_totalFreeBlocks(totalFreeBlocks() - 1);
605
606 assert(retTC != NULL, "null chunk?");
607 assert(retTC->prev() == NULL && retTC->next() == NULL,
608 "should return without encumbrances");
609 if (FLSVerifyDictionary) {
610 verifyTree();
611 }
612 assert(!removing_only_chunk || _root == NULL, "root should be NULL");
613 return TreeChunk::as_TreeChunk(retTC);
614 }
615
616 // Remove the leftmost node (lm) in the tree and return it.
617 // If lm has a right child, link it to the left node of
618 // the parent of lm.
619 TreeList* BinaryTreeDictionary::removeTreeMinimum(TreeList* tl) {
620 assert(tl != NULL && tl->parent() != NULL, "really need a proper sub-tree");
621 // locate the subtree minimum by walking down left branches
622 TreeList* curTL = tl;
623 for (; curTL->left() != NULL; curTL = curTL->left());
624 // obviously curTL now has at most one child, a right child
625 if (curTL != root()) { // Should this test just be removed?
626 TreeList* parentTL = curTL->parent();
627 if (parentTL->left() == curTL) { // curTL is a left child
628 parentTL->setLeft(curTL->right());
629 } else {
630 // If the list tl has no left child, then curTL may be
631 // the right child of parentTL.
632 assert(parentTL->right() == curTL, "should be a right child");
633 parentTL->setRight(curTL->right());
634 }
635 } else {
636 // The only use of this method would not pass the root of the
637 // tree (as indicated by the assertion above that the tree list
638 // has a parent) but the specification does not explicitly exclude the
639 // passing of the root so accomodate it.
640 set_root(NULL);
641 }
642 debug_only(
643 curTL->clearParent(); // Test if this needs to be cleared
644 curTL->clearRight(); // recall, above, left child is already null
645 )
646 // we just excised a (non-root) node, we should still verify all tree invariants
647 if (FLSVerifyDictionary) {
648 verifyTree();
649 }
650 return curTL;
651 }
652
653 // Based on a simplification of the algorithm by Sleator and Tarjan (JACM 1985).
654 // The simplifications are the following:
655 // . we splay only when we delete (not when we insert)
656 // . we apply a single spay step per deletion/access
657 // By doing such partial splaying, we reduce the amount of restructuring,
658 // while getting a reasonably efficient search tree (we think).
659 // [Measurements will be needed to (in)validate this expectation.]
660
661 void BinaryTreeDictionary::semiSplayStep(TreeList* tc) {
662 // apply a semi-splay step at the given node:
663 // . if root, norting needs to be done
664 // . if child of root, splay once
665 // . else zig-zig or sig-zag depending on path from grandparent
666 if (root() == tc) return;
667 warning("*** Splaying not yet implemented; "
668 "tree operations may be inefficient ***");
669 }
670
671 void BinaryTreeDictionary::insertChunkInTree(FreeChunk* fc) {
672 TreeList *curTL, *prevTL;
673 size_t size = fc->size();
674
675 assert(size >= MIN_TREE_CHUNK_SIZE, "too small to be a TreeList");
676 if (FLSVerifyDictionary) {
677 verifyTree();
678 }
679 // XXX: do i need to clear the FreeChunk fields, let me do it just in case
680 // Revisit this later
681
682 fc->clearNext();
683 fc->linkPrev(NULL);
684
685 // work down from the _root, looking for insertion point
686 for (prevTL = curTL = root(); curTL != NULL;) {
687 if (curTL->size() == size) // exact match
688 break;
689 prevTL = curTL;
690 if (curTL->size() > size) { // follow left branch
691 curTL = curTL->left();
692 } else { // follow right branch
693 assert(curTL->size() < size, "size inconsistency");
694 curTL = curTL->right();
695 }
696 }
697 TreeChunk* tc = TreeChunk::as_TreeChunk(fc);
698 // This chunk is being returned to the binary tree. Its embedded
699 // TreeList should be unused at this point.
700 tc->initialize();
701 if (curTL != NULL) { // exact match
702 tc->set_list(curTL);
703 curTL->returnChunkAtTail(tc);
704 } else { // need a new node in tree
705 tc->clearNext();
706 tc->linkPrev(NULL);
707 TreeList* newTL = TreeList::as_TreeList(tc);
708 assert(((TreeChunk*)tc)->list() == newTL,
709 "List was not initialized correctly");
710 if (prevTL == NULL) { // we are the only tree node
711 assert(root() == NULL, "control point invariant");
712 set_root(newTL);
713 } else { // insert under prevTL ...
714 if (prevTL->size() < size) { // am right child
715 assert(prevTL->right() == NULL, "control point invariant");
716 prevTL->setRight(newTL);
717 } else { // am left child
718 assert(prevTL->size() > size && prevTL->left() == NULL, "cpt pt inv");
719 prevTL->setLeft(newTL);
720 }
721 }
722 }
723 assert(tc->list() != NULL, "Tree list should be set");
724
725 inc_totalSize(size);
726 // Method 'totalSizeInTree' walks through the every block in the
727 // tree, so it can cause significant performance loss if there are
728 // many blocks in the tree
729 assert(!FLSVerifyDictionary || totalSizeInTree(root()) == totalSize(), "_totalSize inconsistency");
730 set_totalFreeBlocks(totalFreeBlocks() + 1);
731 if (FLSVerifyDictionary) {
732 verifyTree();
733 }
734 }
735
736 size_t BinaryTreeDictionary::maxChunkSize() const {
737 verify_par_locked();
738 TreeList* tc = root();
739 if (tc == NULL) return 0;
740 for (; tc->right() != NULL; tc = tc->right());
741 return tc->size();
742 }
743
744 size_t BinaryTreeDictionary::totalListLength(TreeList* tl) const {
745 size_t res;
746 res = tl->count();
747 #ifdef ASSERT
748 size_t cnt;
749 FreeChunk* tc = tl->head();
750 for (cnt = 0; tc != NULL; tc = tc->next(), cnt++);
751 assert(res == cnt, "The count is not being maintained correctly");
752 #endif
753 return res;
754 }
755
756 size_t BinaryTreeDictionary::totalSizeInTree(TreeList* tl) const {
757 if (tl == NULL)
758 return 0;
759 return (tl->size() * totalListLength(tl)) +
760 totalSizeInTree(tl->left()) +
761 totalSizeInTree(tl->right());
762 }
763
764 double BinaryTreeDictionary::sum_of_squared_block_sizes(TreeList* const tl) const {
765 if (tl == NULL) {
766 return 0.0;
767 }
768 double size = (double)(tl->size());
769 double curr = size * size * totalListLength(tl);
770 curr += sum_of_squared_block_sizes(tl->left());
771 curr += sum_of_squared_block_sizes(tl->right());
772 return curr;
773 }
774
775 size_t BinaryTreeDictionary::totalFreeBlocksInTree(TreeList* tl) const {
776 if (tl == NULL)
777 return 0;
778 return totalListLength(tl) +
779 totalFreeBlocksInTree(tl->left()) +
780 totalFreeBlocksInTree(tl->right());
781 }
782
783 size_t BinaryTreeDictionary::numFreeBlocks() const {
784 assert(totalFreeBlocksInTree(root()) == totalFreeBlocks(),
785 "_totalFreeBlocks inconsistency");
786 return totalFreeBlocks();
787 }
788
789 size_t BinaryTreeDictionary::treeHeightHelper(TreeList* tl) const {
790 if (tl == NULL)
791 return 0;
792 return 1 + MAX2(treeHeightHelper(tl->left()),
793 treeHeightHelper(tl->right()));
794 }
795
796 size_t BinaryTreeDictionary::treeHeight() const {
797 return treeHeightHelper(root());
798 }
799
800 size_t BinaryTreeDictionary::totalNodesHelper(TreeList* tl) const {
801 if (tl == NULL) {
802 return 0;
803 }
804 return 1 + totalNodesHelper(tl->left()) +
805 totalNodesHelper(tl->right());
806 }
807
808 size_t BinaryTreeDictionary::totalNodesInTree(TreeList* tl) const {
809 return totalNodesHelper(root());
810 }
811
812 void BinaryTreeDictionary::dictCensusUpdate(size_t size, bool split, bool birth){
813 TreeList* nd = findList(size);
814 if (nd) {
815 if (split) {
816 if (birth) {
817 nd->increment_splitBirths();
818 nd->increment_surplus();
819 } else {
820 nd->increment_splitDeaths();
821 nd->decrement_surplus();
822 }
823 } else {
824 if (birth) {
825 nd->increment_coalBirths();
826 nd->increment_surplus();
827 } else {
828 nd->increment_coalDeaths();
829 nd->decrement_surplus();
830 }
831 }
832 }
833 // A list for this size may not be found (nd == 0) if
834 // This is a death where the appropriate list is now
835 // empty and has been removed from the list.
836 // This is a birth associated with a LinAB. The chunk
837 // for the LinAB is not in the dictionary.
838 }
839
840 bool BinaryTreeDictionary::coalDictOverPopulated(size_t size) {
841 if (FLSAlwaysCoalesceLarge) return true;
842
843 TreeList* list_of_size = findList(size);
844 // None of requested size implies overpopulated.
845 return list_of_size == NULL || list_of_size->coalDesired() <= 0 ||
846 list_of_size->count() > list_of_size->coalDesired();
847 }
848
849 // Closures for walking the binary tree.
850 // do_list() walks the free list in a node applying the closure
851 // to each free chunk in the list
852 // do_tree() walks the nodes in the binary tree applying do_list()
853 // to each list at each node.
854
855 class TreeCensusClosure : public StackObj {
856 protected:
857 virtual void do_list(FreeList* fl) = 0;
858 public:
859 virtual void do_tree(TreeList* tl) = 0;
860 };
861
862 class AscendTreeCensusClosure : public TreeCensusClosure {
863 public:
864 void do_tree(TreeList* tl) {
865 if (tl != NULL) {
866 do_tree(tl->left());
867 do_list(tl);
868 do_tree(tl->right());
869 }
870 }
871 };
872
873 class DescendTreeCensusClosure : public TreeCensusClosure {
874 public:
875 void do_tree(TreeList* tl) {
876 if (tl != NULL) {
877 do_tree(tl->right());
878 do_list(tl);
879 do_tree(tl->left());
880 }
881 }
882 };
883
884 // For each list in the tree, calculate the desired, desired
885 // coalesce, count before sweep, and surplus before sweep.
886 class BeginSweepClosure : public AscendTreeCensusClosure {
887 double _percentage;
888 float _inter_sweep_current;
889 float _inter_sweep_estimate;
890 float _intra_sweep_estimate;
891
892 public:
893 BeginSweepClosure(double p, float inter_sweep_current,
894 float inter_sweep_estimate,
895 float intra_sweep_estimate) :
896 _percentage(p),
897 _inter_sweep_current(inter_sweep_current),
898 _inter_sweep_estimate(inter_sweep_estimate),
899 _intra_sweep_estimate(intra_sweep_estimate) { }
900
901 void do_list(FreeList* fl) {
902 double coalSurplusPercent = _percentage;
903 fl->compute_desired(_inter_sweep_current, _inter_sweep_estimate, _intra_sweep_estimate);
904 fl->set_coalDesired((ssize_t)((double)fl->desired() * coalSurplusPercent));
905 fl->set_beforeSweep(fl->count());
906 fl->set_bfrSurp(fl->surplus());
907 }
908 };
909
910 // Used to search the tree until a condition is met.
911 // Similar to TreeCensusClosure but searches the
912 // tree and returns promptly when found.
913
914 class TreeSearchClosure : public StackObj {
915 protected:
916 virtual bool do_list(FreeList* fl) = 0;
917 public:
918 virtual bool do_tree(TreeList* tl) = 0;
919 };
920
921 #if 0 // Don't need this yet but here for symmetry.
922 class AscendTreeSearchClosure : public TreeSearchClosure {
923 public:
924 bool do_tree(TreeList* tl) {
925 if (tl != NULL) {
926 if (do_tree(tl->left())) return true;
927 if (do_list(tl)) return true;
928 if (do_tree(tl->right())) return true;
929 }
930 return false;
931 }
932 };
933 #endif
934
935 class DescendTreeSearchClosure : public TreeSearchClosure {
936 public:
937 bool do_tree(TreeList* tl) {
938 if (tl != NULL) {
939 if (do_tree(tl->right())) return true;
940 if (do_list(tl)) return true;
941 if (do_tree(tl->left())) return true;
942 }
943 return false;
944 }
945 };
946
947 // Searches the tree for a chunk that ends at the
948 // specified address.
949 class EndTreeSearchClosure : public DescendTreeSearchClosure {
950 HeapWord* _target;
951 FreeChunk* _found;
952
953 public:
954 EndTreeSearchClosure(HeapWord* target) : _target(target), _found(NULL) {}
955 bool do_list(FreeList* fl) {
956 FreeChunk* item = fl->head();
957 while (item != NULL) {
958 if (item->end() == _target) {
959 _found = item;
960 return true;
961 }
962 item = item->next();
963 }
964 return false;
965 }
966 FreeChunk* found() { return _found; }
967 };
968
969 FreeChunk* BinaryTreeDictionary::find_chunk_ends_at(HeapWord* target) const {
970 EndTreeSearchClosure etsc(target);
971 bool found_target = etsc.do_tree(root());
972 assert(found_target || etsc.found() == NULL, "Consistency check");
973 assert(!found_target || etsc.found() != NULL, "Consistency check");
974 return etsc.found();
975 }
976
977 void BinaryTreeDictionary::beginSweepDictCensus(double coalSurplusPercent,
978 float inter_sweep_current, float inter_sweep_estimate, float intra_sweep_estimate) {
979 BeginSweepClosure bsc(coalSurplusPercent, inter_sweep_current,
980 inter_sweep_estimate,
981 intra_sweep_estimate);
982 bsc.do_tree(root());
983 }
984
985 // Closures and methods for calculating total bytes returned to the
986 // free lists in the tree.
987 NOT_PRODUCT(
988 class InitializeDictReturnedBytesClosure : public AscendTreeCensusClosure {
989 public:
990 void do_list(FreeList* fl) {
991 fl->set_returnedBytes(0);
992 }
993 };
994
995 void BinaryTreeDictionary::initializeDictReturnedBytes() {
996 InitializeDictReturnedBytesClosure idrb;
997 idrb.do_tree(root());
998 }
999
1000 class ReturnedBytesClosure : public AscendTreeCensusClosure {
1001 size_t _dictReturnedBytes;
1002 public:
1003 ReturnedBytesClosure() { _dictReturnedBytes = 0; }
1004 void do_list(FreeList* fl) {
1005 _dictReturnedBytes += fl->returnedBytes();
1006 }
1007 size_t dictReturnedBytes() { return _dictReturnedBytes; }
1008 };
1009
1010 size_t BinaryTreeDictionary::sumDictReturnedBytes() {
1011 ReturnedBytesClosure rbc;
1012 rbc.do_tree(root());
1013
1014 return rbc.dictReturnedBytes();
1015 }
1016
1017 // Count the number of entries in the tree.
1018 class treeCountClosure : public DescendTreeCensusClosure {
1019 public:
1020 uint count;
1021 treeCountClosure(uint c) { count = c; }
1022 void do_list(FreeList* fl) {
1023 count++;
1024 }
1025 };
1026
1027 size_t BinaryTreeDictionary::totalCount() {
1028 treeCountClosure ctc(0);
1029 ctc.do_tree(root());
1030 return ctc.count;
1031 }
1032 )
1033
1034 // Calculate surpluses for the lists in the tree.
1035 class setTreeSurplusClosure : public AscendTreeCensusClosure {
1036 double percentage;
1037 public:
1038 setTreeSurplusClosure(double v) { percentage = v; }
1039 void do_list(FreeList* fl) {
1040 double splitSurplusPercent = percentage;
1041 fl->set_surplus(fl->count() -
1042 (ssize_t)((double)fl->desired() * splitSurplusPercent));
1043 }
1044 };
1045
1046 void BinaryTreeDictionary::setTreeSurplus(double splitSurplusPercent) {
1047 setTreeSurplusClosure sts(splitSurplusPercent);
1048 sts.do_tree(root());
1049 }
1050
1051 // Set hints for the lists in the tree.
1052 class setTreeHintsClosure : public DescendTreeCensusClosure {
1053 size_t hint;
1054 public:
1055 setTreeHintsClosure(size_t v) { hint = v; }
1056 void do_list(FreeList* fl) {
1057 fl->set_hint(hint);
1058 assert(fl->hint() == 0 || fl->hint() > fl->size(),
1059 "Current hint is inconsistent");
1060 if (fl->surplus() > 0) {
1061 hint = fl->size();
1062 }
1063 }
1064 };
1065
1066 void BinaryTreeDictionary::setTreeHints(void) {
1067 setTreeHintsClosure sth(0);
1068 sth.do_tree(root());
1069 }
1070
1071 // Save count before previous sweep and splits and coalesces.
1072 class clearTreeCensusClosure : public AscendTreeCensusClosure {
1073 void do_list(FreeList* fl) {
1074 fl->set_prevSweep(fl->count());
1075 fl->set_coalBirths(0);
1076 fl->set_coalDeaths(0);
1077 fl->set_splitBirths(0);
1078 fl->set_splitDeaths(0);
1079 }
1080 };
1081
1082 void BinaryTreeDictionary::clearTreeCensus(void) {
1083 clearTreeCensusClosure ctc;
1084 ctc.do_tree(root());
1085 }
1086
1087 // Do reporting and post sweep clean up.
1088 void BinaryTreeDictionary::endSweepDictCensus(double splitSurplusPercent) {
1089 // Does walking the tree 3 times hurt?
1090 setTreeSurplus(splitSurplusPercent);
1091 setTreeHints();
1092 if (PrintGC && Verbose) {
1093 reportStatistics();
1094 }
1095 clearTreeCensus();
1096 }
1097
1098 // Print summary statistics
1099 void BinaryTreeDictionary::reportStatistics() const {
1100 verify_par_locked();
1101 gclog_or_tty->print("Statistics for BinaryTreeDictionary:\n"
1102 "------------------------------------\n");
1103 size_t totalSize = totalChunkSize(debug_only(NULL));
1104 size_t freeBlocks = numFreeBlocks();
1105 gclog_or_tty->print("Total Free Space: %d\n", totalSize);
1106 gclog_or_tty->print("Max Chunk Size: %d\n", maxChunkSize());
1107 gclog_or_tty->print("Number of Blocks: %d\n", freeBlocks);
1108 if (freeBlocks > 0) {
1109 gclog_or_tty->print("Av. Block Size: %d\n", totalSize/freeBlocks);
1110 }
1111 gclog_or_tty->print("Tree Height: %d\n", treeHeight());
1112 }
1113
1114 // Print census information - counts, births, deaths, etc.
1115 // for each list in the tree. Also print some summary
1116 // information.
1117 class PrintTreeCensusClosure : public AscendTreeCensusClosure {
1118 int _print_line;
1119 size_t _totalFree;
1120 FreeList _total;
1121
1122 public:
1123 PrintTreeCensusClosure() {
1124 _print_line = 0;
1125 _totalFree = 0;
1126 }
1127 FreeList* total() { return &_total; }
1128 size_t totalFree() { return _totalFree; }
1129 void do_list(FreeList* fl) {
1130 if (++_print_line >= 40) {
1131 FreeList::print_labels_on(gclog_or_tty, "size");
1132 _print_line = 0;
1133 }
1134 fl->print_on(gclog_or_tty);
1135 _totalFree += fl->count() * fl->size() ;
1136 total()->set_count( total()->count() + fl->count() );
1137 total()->set_bfrSurp( total()->bfrSurp() + fl->bfrSurp() );
1138 total()->set_surplus( total()->splitDeaths() + fl->surplus() );
1139 total()->set_desired( total()->desired() + fl->desired() );
1140 total()->set_prevSweep( total()->prevSweep() + fl->prevSweep() );
1141 total()->set_beforeSweep(total()->beforeSweep() + fl->beforeSweep());
1142 total()->set_coalBirths( total()->coalBirths() + fl->coalBirths() );
1143 total()->set_coalDeaths( total()->coalDeaths() + fl->coalDeaths() );
1144 total()->set_splitBirths(total()->splitBirths() + fl->splitBirths());
1145 total()->set_splitDeaths(total()->splitDeaths() + fl->splitDeaths());
1146 }
1147 };
1148
1149 void BinaryTreeDictionary::printDictCensus(void) const {
1150
1151 gclog_or_tty->print("\nBinaryTree\n");
1152 FreeList::print_labels_on(gclog_or_tty, "size");
1153 PrintTreeCensusClosure ptc;
1154 ptc.do_tree(root());
1155
1156 FreeList* total = ptc.total();
1157 FreeList::print_labels_on(gclog_or_tty, " ");
1158 total->print_on(gclog_or_tty, "TOTAL\t");
1159 gclog_or_tty->print(
1160 "totalFree(words): " SIZE_FORMAT_W(16)
1161 " growth: %8.5f deficit: %8.5f\n",
1162 ptc.totalFree(),
1163 (double)(total->splitBirths() + total->coalBirths()
1164 - total->splitDeaths() - total->coalDeaths())
1165 /(total->prevSweep() != 0 ? (double)total->prevSweep() : 1.0),
1166 (double)(total->desired() - total->count())
1167 /(total->desired() != 0 ? (double)total->desired() : 1.0));
1168 }
1169
1170 class PrintFreeListsClosure : public AscendTreeCensusClosure {
1171 outputStream* _st;
1172 int _print_line;
1173
1174 public:
1175 PrintFreeListsClosure(outputStream* st) {
1176 _st = st;
1177 _print_line = 0;
1178 }
1179 void do_list(FreeList* fl) {
1180 if (++_print_line >= 40) {
1181 FreeList::print_labels_on(_st, "size");
1182 _print_line = 0;
1183 }
1184 fl->print_on(gclog_or_tty);
1185 size_t sz = fl->size();
1186 for (FreeChunk* fc = fl->head(); fc != NULL;
1187 fc = fc->next()) {
1188 _st->print_cr("\t[" PTR_FORMAT "," PTR_FORMAT ") %s",
1189 fc, (HeapWord*)fc + sz,
1190 fc->cantCoalesce() ? "\t CC" : "");
1191 }
1192 }
1193 };
1194
1195 void BinaryTreeDictionary::print_free_lists(outputStream* st) const {
1196
1197 FreeList::print_labels_on(st, "size");
1198 PrintFreeListsClosure pflc(st);
1199 pflc.do_tree(root());
1200 }
1201
1202 // Verify the following tree invariants:
1203 // . _root has no parent
1204 // . parent and child point to each other
1205 // . each node's key correctly related to that of its child(ren)
1206 void BinaryTreeDictionary::verifyTree() const {
1207 guarantee(root() == NULL || totalFreeBlocks() == 0 ||
1208 totalSize() != 0, "_totalSize should't be 0?");
1209 guarantee(root() == NULL || root()->parent() == NULL, "_root shouldn't have parent");
1210 verifyTreeHelper(root());
1211 }
1212
1213 size_t BinaryTreeDictionary::verifyPrevFreePtrs(TreeList* tl) {
1214 size_t ct = 0;
1215 for (FreeChunk* curFC = tl->head(); curFC != NULL; curFC = curFC->next()) {
1216 ct++;
1217 assert(curFC->prev() == NULL || curFC->prev()->isFree(),
1218 "Chunk should be free");
1219 }
1220 return ct;
1221 }
1222
1223 // Note: this helper is recursive rather than iterative, so use with
1224 // caution on very deep trees; and watch out for stack overflow errors;
1225 // In general, to be used only for debugging.
1226 void BinaryTreeDictionary::verifyTreeHelper(TreeList* tl) const {
1227 if (tl == NULL)
1228 return;
1229 guarantee(tl->size() != 0, "A list must has a size");
1230 guarantee(tl->left() == NULL || tl->left()->parent() == tl,
1231 "parent<-/->left");
1232 guarantee(tl->right() == NULL || tl->right()->parent() == tl,
1233 "parent<-/->right");;
1234 guarantee(tl->left() == NULL || tl->left()->size() < tl->size(),
1235 "parent !> left");
1236 guarantee(tl->right() == NULL || tl->right()->size() > tl->size(),
1237 "parent !< left");
1238 guarantee(tl->head() == NULL || tl->head()->isFree(), "!Free");
1239 guarantee(tl->head() == NULL || tl->head_as_TreeChunk()->list() == tl,
1240 "list inconsistency");
1241 guarantee(tl->count() > 0 || (tl->head() == NULL && tl->tail() == NULL),
1242 "list count is inconsistent");
1243 guarantee(tl->count() > 1 || tl->head() == tl->tail(),
1244 "list is incorrectly constructed");
1245 size_t count = verifyPrevFreePtrs(tl);
1246 guarantee(count == (size_t)tl->count(), "Node count is incorrect");
1247 if (tl->head() != NULL) {
1248 tl->head_as_TreeChunk()->verifyTreeChunkList();
1249 }
1250 verifyTreeHelper(tl->left());
1251 verifyTreeHelper(tl->right());
1252 }
1253
1254 void BinaryTreeDictionary::verify() const {
1255 verifyTree();
1256 guarantee(totalSize() == totalSizeInTree(root()), "Total Size inconsistency");
1257 }