Mercurial > hg > graal-jvmci-8

comparison src/share/vm/memory/binaryTreeDictionary.cpp @ 6028:f69a5d43dc19

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary* Summary: Fix naming style to be consistent with the predominant hotspot style. Reviewed-by: ysr, brutisso
author jmasa
date Wed, 25 Apr 2012 09:55:55 -0700
parents 9f059abe8cf2
children a297b0e14605
comparison
equal deleted inserted replaced
6026:9f059abe8cf2 6028:f69a5d43dc19
42 // Do some assertion checking here. 42 // Do some assertion checking here.
43 return (TreeChunk<Chunk>*) fc; 43 return (TreeChunk<Chunk>*) fc;
44 } 44 }
45 45
46 template <class Chunk> 46 template <class Chunk>
47 void TreeChunk<Chunk>::verifyTreeChunkList() const { 47 void TreeChunk<Chunk>::verify_tree_chunk_list() const {
48 TreeChunk<Chunk>* nextTC = (TreeChunk<Chunk>*)next(); 48 TreeChunk<Chunk>* nextTC = (TreeChunk<Chunk>*)next();
49 if (prev() != NULL) { // interior list node shouldn'r have tree fields 49 if (prev() != NULL) { // interior list node shouldn'r have tree fields
50 guarantee(embedded_list()->parent() == NULL && embedded_list()->left() == NULL && 50 guarantee(embedded_list()->parent() == NULL && embedded_list()->left() == NULL &&
51 embedded_list()->right() == NULL, "should be clear"); 51 embedded_list()->right() == NULL, "should be clear");
52 } 52 }
53 if (nextTC != NULL) { 53 if (nextTC != NULL) {
54 guarantee(as_TreeChunk(nextTC->prev()) == this, "broken chain"); 54 guarantee(as_TreeChunk(nextTC->prev()) == this, "broken chain");
55 guarantee(nextTC->size() == size(), "wrong size"); 55 guarantee(nextTC->size() == size(), "wrong size");
56 nextTC->verifyTreeChunkList(); 56 nextTC->verify_tree_chunk_list();
57 } 57 }
58 } 58 }
59 59
60 60
61 template <class Chunk> 61 template <class Chunk>
71 tl->set_size(tc->size()); 71 tl->set_size(tc->size());
72 tl->link_head(tc); 72 tl->link_head(tc);
73 tl->link_tail(tc); 73 tl->link_tail(tc);
74 tl->set_count(1); 74 tl->set_count(1);
75 tl->init_statistics(true /* split_birth */); 75 tl->init_statistics(true /* split_birth */);
76 tl->setParent(NULL); 76 tl->set_parent(NULL);
77 tl->setLeft(NULL); 77 tl->set_left(NULL);
78 tl->setRight(NULL); 78 tl->set_right(NULL);
79 return tl; 79 return tl;
80 } 80 }
81 81
82 template <class Chunk> 82 template <class Chunk>
83 TreeList<Chunk>* TreeList<Chunk>::as_TreeList(HeapWord* addr, size_t size) { 83 TreeList<Chunk>* TreeList<Chunk>::as_TreeList(HeapWord* addr, size_t size) {
90 SpaceMangler::is_mangled((HeapWord*) tc->size_addr()) && 90 SpaceMangler::is_mangled((HeapWord*) tc->size_addr()) &&
91 SpaceMangler::is_mangled((HeapWord*) tc->prev_addr()) && 91 SpaceMangler::is_mangled((HeapWord*) tc->prev_addr()) &&
92 SpaceMangler::is_mangled((HeapWord*) tc->next_addr())) || 92 SpaceMangler::is_mangled((HeapWord*) tc->next_addr())) ||
93 (tc->size() == 0 && tc->prev() == NULL && tc->next() == NULL), 93 (tc->size() == 0 && tc->prev() == NULL && tc->next() == NULL),
94 "Space should be clear or mangled"); 94 "Space should be clear or mangled");
95 tc->setSize(size); 95 tc->set_size(size);
96 tc->linkPrev(NULL); 96 tc->link_prev(NULL);
97 tc->linkNext(NULL); 97 tc->link_next(NULL);
98 TreeList<Chunk>* tl = TreeList<Chunk>::as_TreeList(tc); 98 TreeList<Chunk>* tl = TreeList<Chunk>::as_TreeList(tc);
99 return tl; 99 return tl;
100 } 100 }
101 101
102 template <class Chunk> 102 template <class Chunk>
103 TreeList<Chunk>* TreeList<Chunk>::removeChunkReplaceIfNeeded(TreeChunk<Chunk>* tc) { 103 TreeList<Chunk>* TreeList<Chunk>::remove_chunk_replace_if_needed(TreeChunk<Chunk>* tc) {
104 104
105 TreeList<Chunk>* retTL = this; 105 TreeList<Chunk>* retTL = this;
106 Chunk* list = head(); 106 Chunk* list = head();
107 assert(!list || list != list->next(), "Chunk on list twice"); 107 assert(!list || list != list->next(), "Chunk on list twice");
108 assert(tc != NULL, "Chunk being removed is NULL"); 108 assert(tc != NULL, "Chunk being removed is NULL");
109 assert(parent() == NULL || this == parent()->left() || 109 assert(parent() == NULL || this == parent()->left() ||
110 this == parent()->right(), "list is inconsistent"); 110 this == parent()->right(), "list is inconsistent");
111 assert(tc->isFree(), "Header is not marked correctly"); 111 assert(tc->is_free(), "Header is not marked correctly");
112 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 112 assert(head() == NULL || head()->prev() == NULL, "list invariant");
113 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 113 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
114 114
115 Chunk* prevFC = tc->prev(); 115 Chunk* prevFC = tc->prev();
116 TreeChunk<Chunk>* nextTC = TreeChunk<Chunk>::as_TreeChunk(tc->next()); 116 TreeChunk<Chunk>* nextTC = TreeChunk<Chunk>::as_TreeChunk(tc->next());
146 curTC->set_list(retTL); 146 curTC->set_list(retTL);
147 } 147 }
148 // Fix the parent to point to the new TreeList<Chunk>. 148 // Fix the parent to point to the new TreeList<Chunk>.
149 if (retTL->parent() != NULL) { 149 if (retTL->parent() != NULL) {
150 if (this == retTL->parent()->left()) { 150 if (this == retTL->parent()->left()) {
151 retTL->parent()->setLeft(retTL); 151 retTL->parent()->set_left(retTL);
152 } else { 152 } else {
153 assert(this == retTL->parent()->right(), "Parent is incorrect"); 153 assert(this == retTL->parent()->right(), "Parent is incorrect");
154 retTL->parent()->setRight(retTL); 154 retTL->parent()->set_right(retTL);
155 } 155 }
156 } 156 }
157 // Fix the children's parent pointers to point to the 157 // Fix the children's parent pointers to point to the
158 // new list. 158 // new list.
159 assert(right() == retTL->right(), "Should have been copied"); 159 assert(right() == retTL->right(), "Should have been copied");
160 if (retTL->right() != NULL) { 160 if (retTL->right() != NULL) {
161 retTL->right()->setParent(retTL); 161 retTL->right()->set_parent(retTL);
162 } 162 }
163 assert(left() == retTL->left(), "Should have been copied"); 163 assert(left() == retTL->left(), "Should have been copied");
164 if (retTL->left() != NULL) { 164 if (retTL->left() != NULL) {
165 retTL->left()->setParent(retTL); 165 retTL->left()->set_parent(retTL);
166 } 166 }
167 retTL->link_head(nextTC); 167 retTL->link_head(nextTC);
168 assert(nextTC->isFree(), "Should be a free chunk"); 168 assert(nextTC->is_free(), "Should be a free chunk");
169 } 169 }
170 } else { 170 } else {
171 if (nextTC == NULL) { 171 if (nextTC == NULL) {
172 // Removing chunk at tail of list 172 // Removing chunk at tail of list
173 link_tail(prevFC); 173 link_tail(prevFC);
174 } 174 }
175 // Chunk is interior to the list 175 // Chunk is interior to the list
176 prevFC->linkAfter(nextTC); 176 prevFC->link_after(nextTC);
177 } 177 }
178 178
179 // Below this point the embeded TreeList<Chunk> being used for the 179 // Below this point the embeded TreeList<Chunk> being used for the
180 // tree node may have changed. Don't use "this" 180 // tree node may have changed. Don't use "this"
181 // TreeList<Chunk>*. 181 // TreeList<Chunk>*.
182 // chunk should still be a free chunk (bit set in _prev) 182 // chunk should still be a free chunk (bit set in _prev)
183 assert(!retTL->head() || retTL->size() == retTL->head()->size(), 183 assert(!retTL->head() || retTL->size() == retTL->head()->size(),
184 "Wrong sized chunk in list"); 184 "Wrong sized chunk in list");
185 debug_only( 185 debug_only(
186 tc->linkPrev(NULL); 186 tc->link_prev(NULL);
187 tc->linkNext(NULL); 187 tc->link_next(NULL);
188 tc->set_list(NULL); 188 tc->set_list(NULL);
189 bool prev_found = false; 189 bool prev_found = false;
190 bool next_found = false; 190 bool next_found = false;
191 for (Chunk* curFC = retTL->head(); 191 for (Chunk* curFC = retTL->head();
192 curFC != NULL; curFC = curFC->next()) { 192 curFC != NULL; curFC = curFC->next()) {
205 retTL == retTL->parent()->right(), 205 retTL == retTL->parent()->right(),
206 "list is inconsistent"); 206 "list is inconsistent");
207 ) 207 )
208 retTL->decrement_count(); 208 retTL->decrement_count();
209 209
210 assert(tc->isFree(), "Should still be a free chunk"); 210 assert(tc->is_free(), "Should still be a free chunk");
211 assert(retTL->head() == NULL || retTL->head()->prev() == NULL, 211 assert(retTL->head() == NULL || retTL->head()->prev() == NULL,
212 "list invariant"); 212 "list invariant");
213 assert(retTL->tail() == NULL || retTL->tail()->next() == NULL, 213 assert(retTL->tail() == NULL || retTL->tail()->next() == NULL,
214 "list invariant"); 214 "list invariant");
215 return retTL; 215 return retTL;
216 } 216 }
217 217
218 template <class Chunk> 218 template <class Chunk>
219 void TreeList<Chunk>::returnChunkAtTail(TreeChunk<Chunk>* chunk) { 219 void TreeList<Chunk>::return_chunk_at_tail(TreeChunk<Chunk>* chunk) {
220 assert(chunk != NULL, "returning NULL chunk"); 220 assert(chunk != NULL, "returning NULL chunk");
221 assert(chunk->list() == this, "list should be set for chunk"); 221 assert(chunk->list() == this, "list should be set for chunk");
222 assert(tail() != NULL, "The tree list is embedded in the first chunk"); 222 assert(tail() != NULL, "The tree list is embedded in the first chunk");
223 // which means that the list can never be empty. 223 // which means that the list can never be empty.
224 assert(!verifyChunkInFreeLists(chunk), "Double entry"); 224 assert(!verify_chunk_in_free_list(chunk), "Double entry");
225 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 225 assert(head() == NULL || head()->prev() == NULL, "list invariant");
226 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 226 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
227 227
228 Chunk* fc = tail(); 228 Chunk* fc = tail();
229 fc->linkAfter(chunk); 229 fc->link_after(chunk);
230 link_tail(chunk); 230 link_tail(chunk);
231 231
232 assert(!tail() || size() == tail()->size(), "Wrong sized chunk in list"); 232 assert(!tail() || size() == tail()->size(), "Wrong sized chunk in list");
233 FreeList<Chunk>::increment_count(); 233 FreeList<Chunk>::increment_count();
234 debug_only(increment_returnedBytes_by(chunk->size()*sizeof(HeapWord));) 234 debug_only(increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));)
235 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 235 assert(head() == NULL || head()->prev() == NULL, "list invariant");
236 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 236 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
237 } 237 }
238 238
239 // Add this chunk at the head of the list. "At the head of the list" 239 // Add this chunk at the head of the list. "At the head of the list"
240 // is defined to be after the chunk pointer to by head(). This is 240 // is defined to be after the chunk pointer to by head(). This is
241 // because the TreeList<Chunk> is embedded in the first TreeChunk<Chunk> in the 241 // because the TreeList<Chunk> is embedded in the first TreeChunk<Chunk> in the
242 // list. See the definition of TreeChunk<Chunk>. 242 // list. See the definition of TreeChunk<Chunk>.
243 template <class Chunk> 243 template <class Chunk>
244 void TreeList<Chunk>::returnChunkAtHead(TreeChunk<Chunk>* chunk) { 244 void TreeList<Chunk>::return_chunk_at_head(TreeChunk<Chunk>* chunk) {
245 assert(chunk->list() == this, "list should be set for chunk"); 245 assert(chunk->list() == this, "list should be set for chunk");
246 assert(head() != NULL, "The tree list is embedded in the first chunk"); 246 assert(head() != NULL, "The tree list is embedded in the first chunk");
247 assert(chunk != NULL, "returning NULL chunk"); 247 assert(chunk != NULL, "returning NULL chunk");
248 assert(!verifyChunkInFreeLists(chunk), "Double entry"); 248 assert(!verify_chunk_in_free_list(chunk), "Double entry");
249 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 249 assert(head() == NULL || head()->prev() == NULL, "list invariant");
250 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 250 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
251 251
252 Chunk* fc = head()->next(); 252 Chunk* fc = head()->next();
253 if (fc != NULL) { 253 if (fc != NULL) {
254 chunk->linkAfter(fc); 254 chunk->link_after(fc);
255 } else { 255 } else {
256 assert(tail() == NULL, "List is inconsistent"); 256 assert(tail() == NULL, "List is inconsistent");
257 link_tail(chunk); 257 link_tail(chunk);
258 } 258 }
259 head()->linkAfter(chunk); 259 head()->link_after(chunk);
260 assert(!head() || size() == head()->size(), "Wrong sized chunk in list"); 260 assert(!head() || size() == head()->size(), "Wrong sized chunk in list");
261 FreeList<Chunk>::increment_count(); 261 FreeList<Chunk>::increment_count();
262 debug_only(increment_returnedBytes_by(chunk->size()*sizeof(HeapWord));) 262 debug_only(increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));)
263 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 263 assert(head() == NULL || head()->prev() == NULL, "list invariant");
264 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 264 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
265 } 265 }
266 266
267 template <class Chunk> 267 template <class Chunk>
312 } 312 }
313 313
314 template <class Chunk> 314 template <class Chunk>
315 BinaryTreeDictionary<Chunk>::BinaryTreeDictionary(bool adaptive_freelists, bool splay) : 315 BinaryTreeDictionary<Chunk>::BinaryTreeDictionary(bool adaptive_freelists, bool splay) :
316 _splay(splay), _adaptive_freelists(adaptive_freelists), 316 _splay(splay), _adaptive_freelists(adaptive_freelists),
317 _totalSize(0), _totalFreeBlocks(0), _root(0) {} 317 _total_size(0), _total_free_blocks(0), _root(0) {}
318 318
319 template <class Chunk> 319 template <class Chunk>
320 BinaryTreeDictionary<Chunk>::BinaryTreeDictionary(MemRegion mr, 320 BinaryTreeDictionary<Chunk>::BinaryTreeDictionary(MemRegion mr,
321 bool adaptive_freelists, 321 bool adaptive_freelists,
322 bool splay): 322 bool splay):
327 reset(mr); 327 reset(mr);
328 assert(root()->left() == NULL, "reset check failed"); 328 assert(root()->left() == NULL, "reset check failed");
329 assert(root()->right() == NULL, "reset check failed"); 329 assert(root()->right() == NULL, "reset check failed");
330 assert(root()->head()->next() == NULL, "reset check failed"); 330 assert(root()->head()->next() == NULL, "reset check failed");
331 assert(root()->head()->prev() == NULL, "reset check failed"); 331 assert(root()->head()->prev() == NULL, "reset check failed");
332 assert(totalSize() == root()->size(), "reset check failed"); 332 assert(total_size() == root()->size(), "reset check failed");
333 assert(totalFreeBlocks() == 1, "reset check failed"); 333 assert(total_free_blocks() == 1, "reset check failed");
334 } 334 }
335 335
336 template <class Chunk> 336 template <class Chunk>
337 void BinaryTreeDictionary<Chunk>::inc_totalSize(size_t inc) { 337 void BinaryTreeDictionary<Chunk>::inc_total_size(size_t inc) {
338 _totalSize = _totalSize + inc; 338 _total_size = _total_size + inc;
339 } 339 }
340 340
341 template <class Chunk> 341 template <class Chunk>
342 void BinaryTreeDictionary<Chunk>::dec_totalSize(size_t dec) { 342 void BinaryTreeDictionary<Chunk>::dec_total_size(size_t dec) {
343 _totalSize = _totalSize - dec; 343 _total_size = _total_size - dec;
344 } 344 }
345 345
346 template <class Chunk> 346 template <class Chunk>
347 void BinaryTreeDictionary<Chunk>::reset(MemRegion mr) { 347 void BinaryTreeDictionary<Chunk>::reset(MemRegion mr) {
348 assert(mr.word_size() >= BinaryTreeDictionary<Chunk>::min_tree_chunk_size, "minimum chunk size"); 348 assert(mr.word_size() >= BinaryTreeDictionary<Chunk>::min_tree_chunk_size, "minimum chunk size");
349 set_root(TreeList<Chunk>::as_TreeList(mr.start(), mr.word_size())); 349 set_root(TreeList<Chunk>::as_TreeList(mr.start(), mr.word_size()));
350 set_totalSize(mr.word_size()); 350 set_total_size(mr.word_size());
351 set_totalFreeBlocks(1); 351 set_total_free_blocks(1);
352 } 352 }
353 353
354 template <class Chunk> 354 template <class Chunk>
355 void BinaryTreeDictionary<Chunk>::reset(HeapWord* addr, size_t byte_size) { 355 void BinaryTreeDictionary<Chunk>::reset(HeapWord* addr, size_t byte_size) {
356 MemRegion mr(addr, heap_word_size(byte_size)); 356 MemRegion mr(addr, heap_word_size(byte_size));
358 } 358 }
359 359
360 template <class Chunk> 360 template <class Chunk>
361 void BinaryTreeDictionary<Chunk>::reset() { 361 void BinaryTreeDictionary<Chunk>::reset() {
362 set_root(NULL); 362 set_root(NULL);
363 set_totalSize(0); 363 set_total_size(0);
364 set_totalFreeBlocks(0); 364 set_total_free_blocks(0);
365 } 365 }
366 366
367 // Get a free block of size at least size from tree, or NULL. 367 // Get a free block of size at least size from tree, or NULL.
368 // If a splay step is requested, the removal algorithm (only) incorporates 368 // If a splay step is requested, the removal algorithm (only) incorporates
369 // a splay step as follows: 369 // a splay step as follows:
372 // (zig, zig-zig or zig-zag). A chunk of the appropriate size is then returned 372 // (zig, zig-zig or zig-zag). A chunk of the appropriate size is then returned
373 // if available, and if it's the last chunk, the node is deleted. A deteleted 373 // if available, and if it's the last chunk, the node is deleted. A deteleted
374 // node is replaced in place by its tree successor. 374 // node is replaced in place by its tree successor.
375 template <class Chunk> 375 template <class Chunk>
376 TreeChunk<Chunk>* 376 TreeChunk<Chunk>*
377 BinaryTreeDictionary<Chunk>::getChunkFromTree(size_t size, enum FreeBlockDictionary<Chunk>::Dither dither, bool splay) 377 BinaryTreeDictionary<Chunk>::get_chunk_from_tree(size_t size, enum FreeBlockDictionary<Chunk>::Dither dither, bool splay)
378 { 378 {
379 TreeList<Chunk> *curTL, *prevTL; 379 TreeList<Chunk> *curTL, *prevTL;
380 TreeChunk<Chunk>* retTC = NULL; 380 TreeChunk<Chunk>* retTC = NULL;
381 assert(size >= BinaryTreeDictionary<Chunk>::min_tree_chunk_size, "minimum chunk size"); 381 assert(size >= BinaryTreeDictionary<Chunk>::min_tree_chunk_size, "minimum chunk size");
382 if (FLSVerifyDictionary) { 382 if (FLSVerifyDictionary) {
383 verifyTree(); 383 verify_tree();
384 } 384 }
385 // starting at the root, work downwards trying to find match. 385 // starting at the root, work downwards trying to find match.
386 // Remember the last node of size too great or too small. 386 // Remember the last node of size too great or too small.
387 for (prevTL = curTL = root(); curTL != NULL;) { 387 for (prevTL = curTL = root(); curTL != NULL;) {
388 if (curTL->size() == size) { // exact match 388 if (curTL->size() == size) { // exact match
419 /* Use the hint to find a size with a surplus, and reset the hint. */ 419 /* Use the hint to find a size with a surplus, and reset the hint. */
420 TreeList<Chunk>* hintTL = curTL; 420 TreeList<Chunk>* hintTL = curTL;
421 while (hintTL->hint() != 0) { 421 while (hintTL->hint() != 0) {
422 assert(hintTL->hint() == 0 || hintTL->hint() > hintTL->size(), 422 assert(hintTL->hint() == 0 || hintTL->hint() > hintTL->size(),
423 "hint points in the wrong direction"); 423 "hint points in the wrong direction");
424 hintTL = findList(hintTL->hint()); 424 hintTL = find_list(hintTL->hint());
425 assert(curTL != hintTL, "Infinite loop"); 425 assert(curTL != hintTL, "Infinite loop");
426 if (hintTL == NULL || 426 if (hintTL == NULL ||
427 hintTL == curTL /* Should not happen but protect against it */ ) { 427 hintTL == curTL /* Should not happen but protect against it */ ) {
428 // No useful hint. Set the hint to NULL and go on. 428 // No useful hint. Set the hint to NULL and go on.
429 curTL->set_hint(0); 429 curTL->set_hint(0);
446 } 446 }
447 } 447 }
448 } 448 }
449 // don't waste time splaying if chunk's singleton 449 // don't waste time splaying if chunk's singleton
450 if (splay && curTL->head()->next() != NULL) { 450 if (splay && curTL->head()->next() != NULL) {
451 semiSplayStep(curTL); 451 semi_splay_step(curTL);
452 } 452 }
453 retTC = curTL->first_available(); 453 retTC = curTL->first_available();
454 assert((retTC != NULL) && (curTL->count() > 0), 454 assert((retTC != NULL) && (curTL->count() > 0),
455 "A list in the binary tree should not be NULL"); 455 "A list in the binary tree should not be NULL");
456 assert(retTC->size() >= size, 456 assert(retTC->size() >= size,
457 "A chunk of the wrong size was found"); 457 "A chunk of the wrong size was found");
458 removeChunkFromTree(retTC); 458 remove_chunk_from_tree(retTC);
459 assert(retTC->isFree(), "Header is not marked correctly"); 459 assert(retTC->is_free(), "Header is not marked correctly");
460 } 460 }
461 461
462 if (FLSVerifyDictionary) { 462 if (FLSVerifyDictionary) {
463 verify(); 463 verify();
464 } 464 }
465 return retTC; 465 return retTC;
466 } 466 }
467 467
468 template <class Chunk> 468 template <class Chunk>
469 TreeList<Chunk>* BinaryTreeDictionary<Chunk>::findList(size_t size) const { 469 TreeList<Chunk>* BinaryTreeDictionary<Chunk>::find_list(size_t size) const {
470 TreeList<Chunk>* curTL; 470 TreeList<Chunk>* curTL;
471 for (curTL = root(); curTL != NULL;) { 471 for (curTL = root(); curTL != NULL;) {
472 if (curTL->size() == size) { // exact match 472 if (curTL->size() == size) { // exact match
473 break; 473 break;
474 } 474 }
483 return curTL; 483 return curTL;
484 } 484 }
485 485
486 486
487 template <class Chunk> 487 template <class Chunk>
488 bool BinaryTreeDictionary<Chunk>::verifyChunkInFreeLists(Chunk* tc) const { 488 bool BinaryTreeDictionary<Chunk>::verify_chunk_in_free_list(Chunk* tc) const {
489 size_t size = tc->size(); 489 size_t size = tc->size();
490 TreeList<Chunk>* tl = findList(size); 490 TreeList<Chunk>* tl = find_list(size);
491 if (tl == NULL) { 491 if (tl == NULL) {
492 return false; 492 return false;
493 } else { 493 } else {
494 return tl->verifyChunkInFreeLists(tc); 494 return tl->verify_chunk_in_free_list(tc);
495 } 495 }
496 } 496 }
497 497
498 template <class Chunk> 498 template <class Chunk>
499 Chunk* BinaryTreeDictionary<Chunk>::findLargestDict() const { 499 Chunk* BinaryTreeDictionary<Chunk>::find_largest_dict() const {
500 TreeList<Chunk> *curTL = root(); 500 TreeList<Chunk> *curTL = root();
501 if (curTL != NULL) { 501 if (curTL != NULL) {
502 while(curTL->right() != NULL) curTL = curTL->right(); 502 while(curTL->right() != NULL) curTL = curTL->right();
503 return curTL->largest_address(); 503 return curTL->largest_address();
504 } else { 504 } else {
510 // chunk in a list on a tree node, just unlink it. 510 // chunk in a list on a tree node, just unlink it.
511 // If it is the last chunk in the list (the next link is NULL), 511 // If it is the last chunk in the list (the next link is NULL),
512 // remove the node and repair the tree. 512 // remove the node and repair the tree.
513 template <class Chunk> 513 template <class Chunk>
514 TreeChunk<Chunk>* 514 TreeChunk<Chunk>*
515 BinaryTreeDictionary<Chunk>::removeChunkFromTree(TreeChunk<Chunk>* tc) { 515 BinaryTreeDictionary<Chunk>::remove_chunk_from_tree(TreeChunk<Chunk>* tc) {
516 assert(tc != NULL, "Should not call with a NULL chunk"); 516 assert(tc != NULL, "Should not call with a NULL chunk");
517 assert(tc->isFree(), "Header is not marked correctly"); 517 assert(tc->is_free(), "Header is not marked correctly");
518 518
519 TreeList<Chunk> *newTL, *parentTL; 519 TreeList<Chunk> *newTL, *parentTL;
520 TreeChunk<Chunk>* retTC; 520 TreeChunk<Chunk>* retTC;
521 TreeList<Chunk>* tl = tc->list(); 521 TreeList<Chunk>* tl = tc->list();
522 debug_only( 522 debug_only(
532 ) 532 )
533 assert(tl != NULL, "List should be set"); 533 assert(tl != NULL, "List should be set");
534 assert(tl->parent() == NULL || tl == tl->parent()->left() || 534 assert(tl->parent() == NULL || tl == tl->parent()->left() ||
535 tl == tl->parent()->right(), "list is inconsistent"); 535 tl == tl->parent()->right(), "list is inconsistent");
536 536
537 bool complicatedSplice = false; 537 bool complicated_splice = false;
538 538
539 retTC = tc; 539 retTC = tc;
540 // Removing this chunk can have the side effect of changing the node 540 // Removing this chunk can have the side effect of changing the node
541 // (TreeList<Chunk>*) in the tree. If the node is the root, update it. 541 // (TreeList<Chunk>*) in the tree. If the node is the root, update it.
542 TreeList<Chunk>* replacementTL = tl->removeChunkReplaceIfNeeded(tc); 542 TreeList<Chunk>* replacementTL = tl->remove_chunk_replace_if_needed(tc);
543 assert(tc->isFree(), "Chunk should still be free"); 543 assert(tc->is_free(), "Chunk should still be free");
544 assert(replacementTL->parent() == NULL || 544 assert(replacementTL->parent() == NULL ||
545 replacementTL == replacementTL->parent()->left() || 545 replacementTL == replacementTL->parent()->left() ||
546 replacementTL == replacementTL->parent()->right(), 546 replacementTL == replacementTL->parent()->right(),
547 "list is inconsistent"); 547 "list is inconsistent");
548 if (tl == root()) { 548 if (tl == root()) {
568 // Find the replacement node for the (soon to be empty) node being removed. 568 // Find the replacement node for the (soon to be empty) node being removed.
569 // if we have a single (or no) child, splice child in our stead 569 // if we have a single (or no) child, splice child in our stead
570 if (replacementTL->left() == NULL) { 570 if (replacementTL->left() == NULL) {
571 // left is NULL so pick right. right may also be NULL. 571 // left is NULL so pick right. right may also be NULL.
572 newTL = replacementTL->right(); 572 newTL = replacementTL->right();
573 debug_only(replacementTL->clearRight();) 573 debug_only(replacementTL->clear_right();)
574 } else if (replacementTL->right() == NULL) { 574 } else if (replacementTL->right() == NULL) {
575 // right is NULL 575 // right is NULL
576 newTL = replacementTL->left(); 576 newTL = replacementTL->left();
577 debug_only(replacementTL->clearLeft();) 577 debug_only(replacementTL->clearLeft();)
578 } else { // we have both children, so, by patriarchal convention, 578 } else { // we have both children, so, by patriarchal convention,
579 // my replacement is least node in right sub-tree 579 // my replacement is least node in right sub-tree
580 complicatedSplice = true; 580 complicated_splice = true;
581 newTL = removeTreeMinimum(replacementTL->right()); 581 newTL = remove_tree_minimum(replacementTL->right());
582 assert(newTL != NULL && newTL->left() == NULL && 582 assert(newTL != NULL && newTL->left() == NULL &&
583 newTL->right() == NULL, "sub-tree minimum exists"); 583 newTL->right() == NULL, "sub-tree minimum exists");
584 } 584 }
585 // newTL is the replacement for the (soon to be empty) node. 585 // newTL is the replacement for the (soon to be empty) node.
586 // newTL may be NULL. 586 // newTL may be NULL.
587 // should verify; we just cleanly excised our replacement 587 // should verify; we just cleanly excised our replacement
588 if (FLSVerifyDictionary) { 588 if (FLSVerifyDictionary) {
589 verifyTree(); 589 verify_tree();
590 } 590 }
591 // first make newTL my parent's child 591 // first make newTL my parent's child
592 if ((parentTL = replacementTL->parent()) == NULL) { 592 if ((parentTL = replacementTL->parent()) == NULL) {
593 // newTL should be root 593 // newTL should be root
594 assert(tl == root(), "Incorrectly replacing root"); 594 assert(tl == root(), "Incorrectly replacing root");
595 set_root(newTL); 595 set_root(newTL);
596 if (newTL != NULL) { 596 if (newTL != NULL) {
597 newTL->clearParent(); 597 newTL->clear_parent();
598 } 598 }
599 } else if (parentTL->right() == replacementTL) { 599 } else if (parentTL->right() == replacementTL) {
600 // replacementTL is a right child 600 // replacementTL is a right child
601 parentTL->setRight(newTL); 601 parentTL->set_right(newTL);
602 } else { // replacementTL is a left child 602 } else { // replacementTL is a left child
603 assert(parentTL->left() == replacementTL, "should be left child"); 603 assert(parentTL->left() == replacementTL, "should be left child");
604 parentTL->setLeft(newTL); 604 parentTL->set_left(newTL);
605 } 605 }
606 debug_only(replacementTL->clearParent();) 606 debug_only(replacementTL->clear_parent();)
607 if (complicatedSplice) { // we need newTL to get replacementTL's 607 if (complicated_splice) { // we need newTL to get replacementTL's
608 // two children 608 // two children
609 assert(newTL != NULL && 609 assert(newTL != NULL &&
610 newTL->left() == NULL && newTL->right() == NULL, 610 newTL->left() == NULL && newTL->right() == NULL,
611 "newTL should not have encumbrances from the past"); 611 "newTL should not have encumbrances from the past");
612 // we'd like to assert as below: 612 // we'd like to assert as below:
613 // assert(replacementTL->left() != NULL && replacementTL->right() != NULL, 613 // assert(replacementTL->left() != NULL && replacementTL->right() != NULL,
614 // "else !complicatedSplice"); 614 // "else !complicated_splice");
615 // ... however, the above assertion is too strong because we aren't 615 // ... however, the above assertion is too strong because we aren't
616 // guaranteed that replacementTL->right() is still NULL. 616 // guaranteed that replacementTL->right() is still NULL.
617 // Recall that we removed 617 // Recall that we removed
618 // the right sub-tree minimum from replacementTL. 618 // the right sub-tree minimum from replacementTL.
619 // That may well have been its right 619 // That may well have been its right
620 // child! So we'll just assert half of the above: 620 // child! So we'll just assert half of the above:
621 assert(replacementTL->left() != NULL, "else !complicatedSplice"); 621 assert(replacementTL->left() != NULL, "else !complicated_splice");
622 newTL->setLeft(replacementTL->left()); 622 newTL->set_left(replacementTL->left());
623 newTL->setRight(replacementTL->right()); 623 newTL->set_right(replacementTL->right());
624 debug_only( 624 debug_only(
625 replacementTL->clearRight(); 625 replacementTL->clear_right();
626 replacementTL->clearLeft(); 626 replacementTL->clearLeft();
627 ) 627 )
628 } 628 }
629 assert(replacementTL->right() == NULL && 629 assert(replacementTL->right() == NULL &&
630 replacementTL->left() == NULL && 630 replacementTL->left() == NULL &&
631 replacementTL->parent() == NULL, 631 replacementTL->parent() == NULL,
632 "delete without encumbrances"); 632 "delete without encumbrances");
633 } 633 }
634 634
635 assert(totalSize() >= retTC->size(), "Incorrect total size"); 635 assert(total_size() >= retTC->size(), "Incorrect total size");
636 dec_totalSize(retTC->size()); // size book-keeping 636 dec_total_size(retTC->size()); // size book-keeping
637 assert(totalFreeBlocks() > 0, "Incorrect total count"); 637 assert(total_free_blocks() > 0, "Incorrect total count");
638 set_totalFreeBlocks(totalFreeBlocks() - 1); 638 set_total_free_blocks(total_free_blocks() - 1);
639 639
640 assert(retTC != NULL, "null chunk?"); 640 assert(retTC != NULL, "null chunk?");
641 assert(retTC->prev() == NULL && retTC->next() == NULL, 641 assert(retTC->prev() == NULL && retTC->next() == NULL,
642 "should return without encumbrances"); 642 "should return without encumbrances");
643 if (FLSVerifyDictionary) { 643 if (FLSVerifyDictionary) {
644 verifyTree(); 644 verify_tree();
645 } 645 }
646 assert(!removing_only_chunk || _root == NULL, "root should be NULL"); 646 assert(!removing_only_chunk || _root == NULL, "root should be NULL");
647 return TreeChunk<Chunk>::as_TreeChunk(retTC); 647 return TreeChunk<Chunk>::as_TreeChunk(retTC);
648 } 648 }
649 649
650 // Remove the leftmost node (lm) in the tree and return it. 650 // Remove the leftmost node (lm) in the tree and return it.
651 // If lm has a right child, link it to the left node of 651 // If lm has a right child, link it to the left node of
652 // the parent of lm. 652 // the parent of lm.
653 template <class Chunk> 653 template <class Chunk>
654 TreeList<Chunk>* BinaryTreeDictionary<Chunk>::removeTreeMinimum(TreeList<Chunk>* tl) { 654 TreeList<Chunk>* BinaryTreeDictionary<Chunk>::remove_tree_minimum(TreeList<Chunk>* tl) {
655 assert(tl != NULL && tl->parent() != NULL, "really need a proper sub-tree"); 655 assert(tl != NULL && tl->parent() != NULL, "really need a proper sub-tree");
656 // locate the subtree minimum by walking down left branches 656 // locate the subtree minimum by walking down left branches
657 TreeList<Chunk>* curTL = tl; 657 TreeList<Chunk>* curTL = tl;
658 for (; curTL->left() != NULL; curTL = curTL->left()); 658 for (; curTL->left() != NULL; curTL = curTL->left());
659 // obviously curTL now has at most one child, a right child 659 // obviously curTL now has at most one child, a right child
660 if (curTL != root()) { // Should this test just be removed? 660 if (curTL != root()) { // Should this test just be removed?
661 TreeList<Chunk>* parentTL = curTL->parent(); 661 TreeList<Chunk>* parentTL = curTL->parent();
662 if (parentTL->left() == curTL) { // curTL is a left child 662 if (parentTL->left() == curTL) { // curTL is a left child
663 parentTL->setLeft(curTL->right()); 663 parentTL->set_left(curTL->right());
664 } else { 664 } else {
665 // If the list tl has no left child, then curTL may be 665 // If the list tl has no left child, then curTL may be
666 // the right child of parentTL. 666 // the right child of parentTL.
667 assert(parentTL->right() == curTL, "should be a right child"); 667 assert(parentTL->right() == curTL, "should be a right child");
668 parentTL->setRight(curTL->right()); 668 parentTL->set_right(curTL->right());
669 } 669 }
670 } else { 670 } else {
671 // The only use of this method would not pass the root of the 671 // The only use of this method would not pass the root of the
672 // tree (as indicated by the assertion above that the tree list 672 // tree (as indicated by the assertion above that the tree list
673 // has a parent) but the specification does not explicitly exclude the 673 // has a parent) but the specification does not explicitly exclude the
674 // passing of the root so accomodate it. 674 // passing of the root so accomodate it.
675 set_root(NULL); 675 set_root(NULL);
676 } 676 }
677 debug_only( 677 debug_only(
678 curTL->clearParent(); // Test if this needs to be cleared 678 curTL->clear_parent(); // Test if this needs to be cleared
679 curTL->clearRight(); // recall, above, left child is already null 679 curTL->clear_right(); // recall, above, left child is already null
680 ) 680 )
681 // we just excised a (non-root) node, we should still verify all tree invariants 681 // we just excised a (non-root) node, we should still verify all tree invariants
682 if (FLSVerifyDictionary) { 682 if (FLSVerifyDictionary) {
683 verifyTree(); 683 verify_tree();
684 } 684 }
685 return curTL; 685 return curTL;
686 } 686 }
687 687
688 // Based on a simplification of the algorithm by Sleator and Tarjan (JACM 1985). 688 // Based on a simplification of the algorithm by Sleator and Tarjan (JACM 1985).
692 // By doing such partial splaying, we reduce the amount of restructuring, 692 // By doing such partial splaying, we reduce the amount of restructuring,
693 // while getting a reasonably efficient search tree (we think). 693 // while getting a reasonably efficient search tree (we think).
694 // [Measurements will be needed to (in)validate this expectation.] 694 // [Measurements will be needed to (in)validate this expectation.]
695 695
696 template <class Chunk> 696 template <class Chunk>
697 void BinaryTreeDictionary<Chunk>::semiSplayStep(TreeList<Chunk>* tc) { 697 void BinaryTreeDictionary<Chunk>::semi_splay_step(TreeList<Chunk>* tc) {
698 // apply a semi-splay step at the given node: 698 // apply a semi-splay step at the given node:
699 // . if root, norting needs to be done 699 // . if root, norting needs to be done
700 // . if child of root, splay once 700 // . if child of root, splay once
701 // . else zig-zig or sig-zag depending on path from grandparent 701 // . else zig-zig or sig-zag depending on path from grandparent
702 if (root() == tc) return; 702 if (root() == tc) return;
703 warning("*** Splaying not yet implemented; " 703 warning("*** Splaying not yet implemented; "
704 "tree operations may be inefficient ***"); 704 "tree operations may be inefficient ***");
705 } 705 }
706 706
707 template <class Chunk> 707 template <class Chunk>
708 void BinaryTreeDictionary<Chunk>::insertChunkInTree(Chunk* fc) { 708 void BinaryTreeDictionary<Chunk>::insert_chunk_in_tree(Chunk* fc) {
709 TreeList<Chunk> *curTL, *prevTL; 709 TreeList<Chunk> *curTL, *prevTL;
710 size_t size = fc->size(); 710 size_t size = fc->size();
711 711
712 assert(size >= BinaryTreeDictionary<Chunk>::min_tree_chunk_size, "too small to be a TreeList<Chunk>"); 712 assert(size >= BinaryTreeDictionary<Chunk>::min_tree_chunk_size, "too small to be a TreeList<Chunk>");
713 if (FLSVerifyDictionary) { 713 if (FLSVerifyDictionary) {
714 verifyTree(); 714 verify_tree();
715 } 715 }
716 716
717 fc->clearNext(); 717 fc->clear_next();
718 fc->linkPrev(NULL); 718 fc->link_prev(NULL);
719 719
720 // work down from the _root, looking for insertion point 720 // work down from the _root, looking for insertion point
721 for (prevTL = curTL = root(); curTL != NULL;) { 721 for (prevTL = curTL = root(); curTL != NULL;) {
722 if (curTL->size() == size) // exact match 722 if (curTL->size() == size) // exact match
723 break; 723 break;
733 // This chunk is being returned to the binary tree. Its embedded 733 // This chunk is being returned to the binary tree. Its embedded
734 // TreeList<Chunk> should be unused at this point. 734 // TreeList<Chunk> should be unused at this point.
735 tc->initialize(); 735 tc->initialize();
736 if (curTL != NULL) { // exact match 736 if (curTL != NULL) { // exact match
737 tc->set_list(curTL); 737 tc->set_list(curTL);
738 curTL->returnChunkAtTail(tc); 738 curTL->return_chunk_at_tail(tc);
739 } else { // need a new node in tree 739 } else { // need a new node in tree
740 tc->clearNext(); 740 tc->clear_next();
741 tc->linkPrev(NULL); 741 tc->link_prev(NULL);
742 TreeList<Chunk>* newTL = TreeList<Chunk>::as_TreeList(tc); 742 TreeList<Chunk>* newTL = TreeList<Chunk>::as_TreeList(tc);
743 assert(((TreeChunk<Chunk>*)tc)->list() == newTL, 743 assert(((TreeChunk<Chunk>*)tc)->list() == newTL,
744 "List was not initialized correctly"); 744 "List was not initialized correctly");
745 if (prevTL == NULL) { // we are the only tree node 745 if (prevTL == NULL) { // we are the only tree node
746 assert(root() == NULL, "control point invariant"); 746 assert(root() == NULL, "control point invariant");
747 set_root(newTL); 747 set_root(newTL);
748 } else { // insert under prevTL ... 748 } else { // insert under prevTL ...
749 if (prevTL->size() < size) { // am right child 749 if (prevTL->size() < size) { // am right child
750 assert(prevTL->right() == NULL, "control point invariant"); 750 assert(prevTL->right() == NULL, "control point invariant");
751 prevTL->setRight(newTL); 751 prevTL->set_right(newTL);
752 } else { // am left child 752 } else { // am left child
753 assert(prevTL->size() > size && prevTL->left() == NULL, "cpt pt inv"); 753 assert(prevTL->size() > size && prevTL->left() == NULL, "cpt pt inv");
754 prevTL->setLeft(newTL); 754 prevTL->set_left(newTL);
755 } 755 }
756 } 756 }
757 } 757 }
758 assert(tc->list() != NULL, "Tree list should be set"); 758 assert(tc->list() != NULL, "Tree list should be set");
759 759
760 inc_totalSize(size); 760 inc_total_size(size);
761 // Method 'totalSizeInTree' walks through the every block in the 761 // Method 'total_size_in_tree' walks through the every block in the
762 // tree, so it can cause significant performance loss if there are 762 // tree, so it can cause significant performance loss if there are
763 // many blocks in the tree 763 // many blocks in the tree
764 assert(!FLSVerifyDictionary || totalSizeInTree(root()) == totalSize(), "_totalSize inconsistency"); 764 assert(!FLSVerifyDictionary || total_size_in_tree(root()) == total_size(), "_total_size inconsistency");
765 set_totalFreeBlocks(totalFreeBlocks() + 1); 765 set_total_free_blocks(total_free_blocks() + 1);
766 if (FLSVerifyDictionary) { 766 if (FLSVerifyDictionary) {
767 verifyTree(); 767 verify_tree();
768 } 768 }
769 } 769 }
770 770
771 template <class Chunk> 771 template <class Chunk>
772 size_t BinaryTreeDictionary<Chunk>::maxChunkSize() const { 772 size_t BinaryTreeDictionary<Chunk>::max_chunk_size() const {
773 FreeBlockDictionary<Chunk>::verify_par_locked(); 773 FreeBlockDictionary<Chunk>::verify_par_locked();
774 TreeList<Chunk>* tc = root(); 774 TreeList<Chunk>* tc = root();
775 if (tc == NULL) return 0; 775 if (tc == NULL) return 0;
776 for (; tc->right() != NULL; tc = tc->right()); 776 for (; tc->right() != NULL; tc = tc->right());
777 return tc->size(); 777 return tc->size();
778 } 778 }
779 779
780 template <class Chunk> 780 template <class Chunk>
781 size_t BinaryTreeDictionary<Chunk>::totalListLength(TreeList<Chunk>* tl) const { 781 size_t BinaryTreeDictionary<Chunk>::total_list_length(TreeList<Chunk>* tl) const {
782 size_t res; 782 size_t res;
783 res = tl->count(); 783 res = tl->count();
784 #ifdef ASSERT 784 #ifdef ASSERT
785 size_t cnt; 785 size_t cnt;
786 Chunk* tc = tl->head(); 786 Chunk* tc = tl->head();
789 #endif 789 #endif
790 return res; 790 return res;
791 } 791 }
792 792
793 template <class Chunk> 793 template <class Chunk>
794 size_t BinaryTreeDictionary<Chunk>::totalSizeInTree(TreeList<Chunk>* tl) const { 794 size_t BinaryTreeDictionary<Chunk>::total_size_in_tree(TreeList<Chunk>* tl) const {
795 if (tl == NULL) 795 if (tl == NULL)
796 return 0; 796 return 0;
797 return (tl->size() * totalListLength(tl)) + 797 return (tl->size() * total_list_length(tl)) +
798 totalSizeInTree(tl->left()) + 798 total_size_in_tree(tl->left()) +
799 totalSizeInTree(tl->right()); 799 total_size_in_tree(tl->right());
800 } 800 }
801 801
802 template <class Chunk> 802 template <class Chunk>
803 double BinaryTreeDictionary<Chunk>::sum_of_squared_block_sizes(TreeList<Chunk>* const tl) const { 803 double BinaryTreeDictionary<Chunk>::sum_of_squared_block_sizes(TreeList<Chunk>* const tl) const {
804 if (tl == NULL) { 804 if (tl == NULL) {
805 return 0.0; 805 return 0.0;
806 } 806 }
807 double size = (double)(tl->size()); 807 double size = (double)(tl->size());
808 double curr = size * size * totalListLength(tl); 808 double curr = size * size * total_list_length(tl);
809 curr += sum_of_squared_block_sizes(tl->left()); 809 curr += sum_of_squared_block_sizes(tl->left());
810 curr += sum_of_squared_block_sizes(tl->right()); 810 curr += sum_of_squared_block_sizes(tl->right());
811 return curr; 811 return curr;
812 } 812 }
813 813
814 template <class Chunk> 814 template <class Chunk>
815 size_t BinaryTreeDictionary<Chunk>::totalFreeBlocksInTree(TreeList<Chunk>* tl) const { 815 size_t BinaryTreeDictionary<Chunk>::total_free_blocks_in_tree(TreeList<Chunk>* tl) const {
816 if (tl == NULL) 816 if (tl == NULL)
817 return 0; 817 return 0;
818 return totalListLength(tl) + 818 return total_list_length(tl) +
819 totalFreeBlocksInTree(tl->left()) + 819 total_free_blocks_in_tree(tl->left()) +
820 totalFreeBlocksInTree(tl->right()); 820 total_free_blocks_in_tree(tl->right());
821 } 821 }
822 822
823 template <class Chunk> 823 template <class Chunk>
824 size_t BinaryTreeDictionary<Chunk>::numFreeBlocks() const { 824 size_t BinaryTreeDictionary<Chunk>::num_free_blocks() const {
825 assert(totalFreeBlocksInTree(root()) == totalFreeBlocks(), 825 assert(total_free_blocks_in_tree(root()) == total_free_blocks(),
826 "_totalFreeBlocks inconsistency"); 826 "_total_free_blocks inconsistency");
827 return totalFreeBlocks(); 827 return total_free_blocks();
828 } 828 }
829 829
830 template <class Chunk> 830 template <class Chunk>
831 size_t BinaryTreeDictionary<Chunk>::treeHeightHelper(TreeList<Chunk>* tl) const { 831 size_t BinaryTreeDictionary<Chunk>::tree_height_helper(TreeList<Chunk>* tl) const {
832 if (tl == NULL) 832 if (tl == NULL)
833 return 0; 833 return 0;
834 return 1 + MAX2(treeHeightHelper(tl->left()), 834 return 1 + MAX2(tree_height_helper(tl->left()),
835 treeHeightHelper(tl->right())); 835 tree_height_helper(tl->right()));
836 } 836 }
837 837
838 template <class Chunk> 838 template <class Chunk>
839 size_t BinaryTreeDictionary<Chunk>::treeHeight() const { 839 size_t BinaryTreeDictionary<Chunk>::treeHeight() const {
840 return treeHeightHelper(root()); 840 return tree_height_helper(root());
841 } 841 }
842 842
843 template <class Chunk> 843 template <class Chunk>
844 size_t BinaryTreeDictionary<Chunk>::totalNodesHelper(TreeList<Chunk>* tl) const { 844 size_t BinaryTreeDictionary<Chunk>::total_nodes_helper(TreeList<Chunk>* tl) const {
845 if (tl == NULL) { 845 if (tl == NULL) {
846 return 0; 846 return 0;
847 } 847 }
848 return 1 + totalNodesHelper(tl->left()) + 848 return 1 + total_nodes_helper(tl->left()) +
849 totalNodesHelper(tl->right()); 849 total_nodes_helper(tl->right());
850 } 850 }
851 851
852 template <class Chunk> 852 template <class Chunk>
853 size_t BinaryTreeDictionary<Chunk>::totalNodesInTree(TreeList<Chunk>* tl) const { 853 size_t BinaryTreeDictionary<Chunk>::total_nodes_in_tree(TreeList<Chunk>* tl) const {
854 return totalNodesHelper(root()); 854 return total_nodes_helper(root());
855 } 855 }
856 856
857 template <class Chunk> 857 template <class Chunk>
858 void BinaryTreeDictionary<Chunk>::dictCensusUpdate(size_t size, bool split, bool birth){ 858 void BinaryTreeDictionary<Chunk>::dict_census_udpate(size_t size, bool split, bool birth){
859 TreeList<Chunk>* nd = findList(size); 859 TreeList<Chunk>* nd = find_list(size);
860 if (nd) { 860 if (nd) {
861 if (split) { 861 if (split) {
862 if (birth) { 862 if (birth) {
863 nd->increment_splitBirths(); 863 nd->increment_split_births();
864 nd->increment_surplus(); 864 nd->increment_surplus();
865 } else { 865 } else {
866 nd->increment_splitDeaths(); 866 nd->increment_split_deaths();
867 nd->decrement_surplus(); 867 nd->decrement_surplus();
868 } 868 }
869 } else { 869 } else {
870 if (birth) { 870 if (birth) {
871 nd->increment_coalBirths(); 871 nd->increment_coal_births();
872 nd->increment_surplus(); 872 nd->increment_surplus();
873 } else { 873 } else {
874 nd->increment_coalDeaths(); 874 nd->increment_coal_deaths();
875 nd->decrement_surplus(); 875 nd->decrement_surplus();
876 } 876 }
877 } 877 }
878 } 878 }
879 // A list for this size may not be found (nd == 0) if 879 // A list for this size may not be found (nd == 0) if
882 // This is a birth associated with a LinAB. The chunk 882 // This is a birth associated with a LinAB. The chunk
883 // for the LinAB is not in the dictionary. 883 // for the LinAB is not in the dictionary.
884 } 884 }
885 885
886 template <class Chunk> 886 template <class Chunk>
887 bool BinaryTreeDictionary<Chunk>::coalDictOverPopulated(size_t size) { 887 bool BinaryTreeDictionary<Chunk>::coal_dict_over_populated(size_t size) {
888 if (FLSAlwaysCoalesceLarge) return true; 888 if (FLSAlwaysCoalesceLarge) return true;
889 889
890 TreeList<Chunk>* list_of_size = findList(size); 890 TreeList<Chunk>* list_of_size = find_list(size);
891 // None of requested size implies overpopulated. 891 // None of requested size implies overpopulated.
892 return list_of_size == NULL || list_of_size->coalDesired() <= 0 || 892 return list_of_size == NULL || list_of_size->coal_desired() <= 0 ||
893 list_of_size->count() > list_of_size->coalDesired(); 893 list_of_size->count() > list_of_size->coal_desired();
894 } 894 }
895 895
896 // Closures for walking the binary tree. 896 // Closures for walking the binary tree.
897 // do_list() walks the free list in a node applying the closure 897 // do_list() walks the free list in a node applying the closure
898 // to each free chunk in the list 898 // to each free chunk in the list
950 _intra_sweep_estimate(intra_sweep_estimate) { } 950 _intra_sweep_estimate(intra_sweep_estimate) { }
951 951
952 void do_list(FreeList<Chunk>* fl) { 952 void do_list(FreeList<Chunk>* fl) {
953 double coalSurplusPercent = _percentage; 953 double coalSurplusPercent = _percentage;
954 fl->compute_desired(_inter_sweep_current, _inter_sweep_estimate, _intra_sweep_estimate); 954 fl->compute_desired(_inter_sweep_current, _inter_sweep_estimate, _intra_sweep_estimate);
955 fl->set_coalDesired((ssize_t)((double)fl->desired() * coalSurplusPercent)); 955 fl->set_coal_desired((ssize_t)((double)fl->desired() * coalSurplusPercent));
956 fl->set_beforeSweep(fl->count()); 956 fl->set_before_sweep(fl->count());
957 fl->set_bfrSurp(fl->surplus()); 957 fl->set_bfr_surp(fl->surplus());
958 } 958 }
959 }; 959 };
960 960
961 // Used to search the tree until a condition is met. 961 // Used to search the tree until a condition is met.
962 // Similar to TreeCensusClosure but searches the 962 // Similar to TreeCensusClosure but searches the
1029 assert(!found_target || etsc.found() != NULL, "Consistency check"); 1029 assert(!found_target || etsc.found() != NULL, "Consistency check");
1030 return etsc.found(); 1030 return etsc.found();
1031 } 1031 }
1032 1032
1033 template <class Chunk> 1033 template <class Chunk>
1034 void BinaryTreeDictionary<Chunk>::beginSweepDictCensus(double coalSurplusPercent, 1034 void BinaryTreeDictionary<Chunk>::begin_sweep_dict_census(double coalSurplusPercent,
1035 float inter_sweep_current, float inter_sweep_estimate, float intra_sweep_estimate) { 1035 float inter_sweep_current, float inter_sweep_estimate, float intra_sweep_estimate) {
1036 BeginSweepClosure<Chunk> bsc(coalSurplusPercent, inter_sweep_current, 1036 BeginSweepClosure<Chunk> bsc(coalSurplusPercent, inter_sweep_current,
1037 inter_sweep_estimate, 1037 inter_sweep_estimate,
1038 intra_sweep_estimate); 1038 intra_sweep_estimate);
1039 bsc.do_tree(root()); 1039 bsc.do_tree(root());
1044 #ifndef PRODUCT 1044 #ifndef PRODUCT
1045 template <class Chunk> 1045 template <class Chunk>
1046 class InitializeDictReturnedBytesClosure : public AscendTreeCensusClosure<Chunk> { 1046 class InitializeDictReturnedBytesClosure : public AscendTreeCensusClosure<Chunk> {
1047 public: 1047 public:
1048 void do_list(FreeList<Chunk>* fl) { 1048 void do_list(FreeList<Chunk>* fl) {
1049 fl->set_returnedBytes(0); 1049 fl->set_returned_bytes(0);
1050 } 1050 }
1051 }; 1051 };
1052 1052
1053 template <class Chunk> 1053 template <class Chunk>
1054 void BinaryTreeDictionary<Chunk>::initializeDictReturnedBytes() { 1054 void BinaryTreeDictionary<Chunk>::initialize_dict_returned_bytes() {
1055 InitializeDictReturnedBytesClosure<Chunk> idrb; 1055 InitializeDictReturnedBytesClosure<Chunk> idrb;
1056 idrb.do_tree(root()); 1056 idrb.do_tree(root());
1057 } 1057 }
1058 1058
1059 template <class Chunk> 1059 template <class Chunk>
1060 class ReturnedBytesClosure : public AscendTreeCensusClosure<Chunk> { 1060 class ReturnedBytesClosure : public AscendTreeCensusClosure<Chunk> {
1061 size_t _dictReturnedBytes; 1061 size_t _dict_returned_bytes;
1062 public: 1062 public:
1063 ReturnedBytesClosure() { _dictReturnedBytes = 0; } 1063 ReturnedBytesClosure() { _dict_returned_bytes = 0; }
1064 void do_list(FreeList<Chunk>* fl) { 1064 void do_list(FreeList<Chunk>* fl) {
1065 _dictReturnedBytes += fl->returnedBytes(); 1065 _dict_returned_bytes += fl->returned_bytes();
1066 } 1066 }
1067 size_t dictReturnedBytes() { return _dictReturnedBytes; } 1067 size_t dict_returned_bytes() { return _dict_returned_bytes; }
1068 }; 1068 };
1069 1069
1070 template <class Chunk> 1070 template <class Chunk>
1071 size_t BinaryTreeDictionary<Chunk>::sumDictReturnedBytes() { 1071 size_t BinaryTreeDictionary<Chunk>::sum_dict_returned_bytes() {
1072 ReturnedBytesClosure<Chunk> rbc; 1072 ReturnedBytesClosure<Chunk> rbc;
1073 rbc.do_tree(root()); 1073 rbc.do_tree(root());
1074 1074
1075 return rbc.dictReturnedBytes(); 1075 return rbc.dict_returned_bytes();
1076 } 1076 }
1077 1077
1078 // Count the number of entries in the tree. 1078 // Count the number of entries in the tree.
1079 template <class Chunk> 1079 template <class Chunk>
1080 class treeCountClosure : public DescendTreeCensusClosure<Chunk> { 1080 class treeCountClosure : public DescendTreeCensusClosure<Chunk> {
1085 count++; 1085 count++;
1086 } 1086 }
1087 }; 1087 };
1088 1088
1089 template <class Chunk> 1089 template <class Chunk>
1090 size_t BinaryTreeDictionary<Chunk>::totalCount() { 1090 size_t BinaryTreeDictionary<Chunk>::total_count() {
1091 treeCountClosure<Chunk> ctc(0); 1091 treeCountClosure<Chunk> ctc(0);
1092 ctc.do_tree(root()); 1092 ctc.do_tree(root());
1093 return ctc.count; 1093 return ctc.count;
1094 } 1094 }
1095 #endif // PRODUCT 1095 #endif // PRODUCT
1106 (ssize_t)((double)fl->desired() * splitSurplusPercent)); 1106 (ssize_t)((double)fl->desired() * splitSurplusPercent));
1107 } 1107 }
1108 }; 1108 };
1109 1109
1110 template <class Chunk> 1110 template <class Chunk>
1111 void BinaryTreeDictionary<Chunk>::setTreeSurplus(double splitSurplusPercent) { 1111 void BinaryTreeDictionary<Chunk>::set_tree_surplus(double splitSurplusPercent) {
1112 setTreeSurplusClosure<Chunk> sts(splitSurplusPercent); 1112 setTreeSurplusClosure<Chunk> sts(splitSurplusPercent);
1113 sts.do_tree(root()); 1113 sts.do_tree(root());
1114 } 1114 }
1115 1115
1116 // Set hints for the lists in the tree. 1116 // Set hints for the lists in the tree.
1128 } 1128 }
1129 } 1129 }
1130 }; 1130 };
1131 1131
1132 template <class Chunk> 1132 template <class Chunk>
1133 void BinaryTreeDictionary<Chunk>::setTreeHints(void) { 1133 void BinaryTreeDictionary<Chunk>::set_tree_hints(void) {
1134 setTreeHintsClosure<Chunk> sth(0); 1134 setTreeHintsClosure<Chunk> sth(0);
1135 sth.do_tree(root()); 1135 sth.do_tree(root());
1136 } 1136 }
1137 1137
1138 // Save count before previous sweep and splits and coalesces. 1138 // Save count before previous sweep and splits and coalesces.
1139 template <class Chunk> 1139 template <class Chunk>
1140 class clearTreeCensusClosure : public AscendTreeCensusClosure<Chunk> { 1140 class clearTreeCensusClosure : public AscendTreeCensusClosure<Chunk> {
1141 void do_list(FreeList<Chunk>* fl) { 1141 void do_list(FreeList<Chunk>* fl) {
1142 fl->set_prevSweep(fl->count()); 1142 fl->set_prev_sweep(fl->count());
1143 fl->set_coalBirths(0); 1143 fl->set_coal_births(0);
1144 fl->set_coalDeaths(0); 1144 fl->set_coal_deaths(0);
1145 fl->set_splitBirths(0); 1145 fl->set_split_births(0);
1146 fl->set_splitDeaths(0); 1146 fl->set_split_deaths(0);
1147 } 1147 }
1148 }; 1148 };
1149 1149
1150 template <class Chunk> 1150 template <class Chunk>
1151 void BinaryTreeDictionary<Chunk>::clearTreeCensus(void) { 1151 void BinaryTreeDictionary<Chunk>::clear_tree_census(void) {
1152 clearTreeCensusClosure<Chunk> ctc; 1152 clearTreeCensusClosure<Chunk> ctc;
1153 ctc.do_tree(root()); 1153 ctc.do_tree(root());
1154 } 1154 }
1155 1155
1156 // Do reporting and post sweep clean up. 1156 // Do reporting and post sweep clean up.
1157 template <class Chunk> 1157 template <class Chunk>
1158 void BinaryTreeDictionary<Chunk>::endSweepDictCensus(double splitSurplusPercent) { 1158 void BinaryTreeDictionary<Chunk>::end_sweep_dict_census(double splitSurplusPercent) {
1159 // Does walking the tree 3 times hurt? 1159 // Does walking the tree 3 times hurt?
1160 setTreeSurplus(splitSurplusPercent); 1160 set_tree_surplus(splitSurplusPercent);
1161 setTreeHints(); 1161 set_tree_hints();
1162 if (PrintGC && Verbose) { 1162 if (PrintGC && Verbose) {
1163 reportStatistics(); 1163 report_statistics();
1164 } 1164 }
1165 clearTreeCensus(); 1165 clear_tree_census();
1166 } 1166 }
1167 1167
1168 // Print summary statistics 1168 // Print summary statistics
1169 template <class Chunk> 1169 template <class Chunk>
1170 void BinaryTreeDictionary<Chunk>::reportStatistics() const { 1170 void BinaryTreeDictionary<Chunk>::report_statistics() const {
1171 FreeBlockDictionary<Chunk>::verify_par_locked(); 1171 FreeBlockDictionary<Chunk>::verify_par_locked();
1172 gclog_or_tty->print("Statistics for BinaryTreeDictionary:\n" 1172 gclog_or_tty->print("Statistics for BinaryTreeDictionary:\n"
1173 "------------------------------------\n"); 1173 "------------------------------------\n");
1174 size_t totalSize = totalChunkSize(debug_only(NULL)); 1174 size_t total_size = total_chunk_size(debug_only(NULL));
1175 size_t freeBlocks = numFreeBlocks(); 1175 size_t free_blocks = num_free_blocks();
1176 gclog_or_tty->print("Total Free Space: %d\n", totalSize); 1176 gclog_or_tty->print("Total Free Space: %d\n", total_size);
1177 gclog_or_tty->print("Max Chunk Size: %d\n", maxChunkSize()); 1177 gclog_or_tty->print("Max Chunk Size: %d\n", max_chunk_size());
1178 gclog_or_tty->print("Number of Blocks: %d\n", freeBlocks); 1178 gclog_or_tty->print("Number of Blocks: %d\n", free_blocks);
1179 if (freeBlocks > 0) { 1179 if (free_blocks > 0) {
1180 gclog_or_tty->print("Av. Block Size: %d\n", totalSize/freeBlocks); 1180 gclog_or_tty->print("Av. Block Size: %d\n", total_size/free_blocks);
1181 } 1181 }
1182 gclog_or_tty->print("Tree Height: %d\n", treeHeight()); 1182 gclog_or_tty->print("Tree Height: %d\n", treeHeight());
1183 } 1183 }
1184 1184
1185 // Print census information - counts, births, deaths, etc. 1185 // Print census information - counts, births, deaths, etc.
1186 // for each list in the tree. Also print some summary 1186 // for each list in the tree. Also print some summary
1187 // information. 1187 // information.
1188 template <class Chunk> 1188 template <class Chunk>
1189 class PrintTreeCensusClosure : public AscendTreeCensusClosure<Chunk> { 1189 class PrintTreeCensusClosure : public AscendTreeCensusClosure<Chunk> {
1190 int _print_line; 1190 int _print_line;
1191 size_t _totalFree; 1191 size_t _total_free;
1192 FreeList<Chunk> _total; 1192 FreeList<Chunk> _total;
1193 1193
1194 public: 1194 public:
1195 PrintTreeCensusClosure() { 1195 PrintTreeCensusClosure() {
1196 _print_line = 0; 1196 _print_line = 0;
1197 _totalFree = 0; 1197 _total_free = 0;
1198 } 1198 }
1199 FreeList<Chunk>* total() { return &_total; } 1199 FreeList<Chunk>* total() { return &_total; }
1200 size_t totalFree() { return _totalFree; } 1200 size_t total_free() { return _total_free; }
1201 void do_list(FreeList<Chunk>* fl) { 1201 void do_list(FreeList<Chunk>* fl) {
1202 if (++_print_line >= 40) { 1202 if (++_print_line >= 40) {
1203 FreeList<Chunk>::print_labels_on(gclog_or_tty, "size"); 1203 FreeList<Chunk>::print_labels_on(gclog_or_tty, "size");
1204 _print_line = 0; 1204 _print_line = 0;
1205 } 1205 }
1206 fl->print_on(gclog_or_tty); 1206 fl->print_on(gclog_or_tty);
1207 _totalFree += fl->count() * fl->size() ; 1207 _total_free += fl->count() * fl->size() ;
1208 total()->set_count( total()->count() + fl->count() ); 1208 total()->set_count( total()->count() + fl->count() );
1209 total()->set_bfrSurp( total()->bfrSurp() + fl->bfrSurp() ); 1209 total()->set_bfr_surp( total()->bfr_surp() + fl->bfr_surp() );
1210 total()->set_surplus( total()->splitDeaths() + fl->surplus() ); 1210 total()->set_surplus( total()->split_deaths() + fl->surplus() );
1211 total()->set_desired( total()->desired() + fl->desired() ); 1211 total()->set_desired( total()->desired() + fl->desired() );
1212 total()->set_prevSweep( total()->prevSweep() + fl->prevSweep() ); 1212 total()->set_prev_sweep( total()->prev_sweep() + fl->prev_sweep() );
1213 total()->set_beforeSweep(total()->beforeSweep() + fl->beforeSweep()); 1213 total()->set_before_sweep(total()->before_sweep() + fl->before_sweep());
1214 total()->set_coalBirths( total()->coalBirths() + fl->coalBirths() ); 1214 total()->set_coal_births( total()->coal_births() + fl->coal_births() );
1215 total()->set_coalDeaths( total()->coalDeaths() + fl->coalDeaths() ); 1215 total()->set_coal_deaths( total()->coal_deaths() + fl->coal_deaths() );
1216 total()->set_splitBirths(total()->splitBirths() + fl->splitBirths()); 1216 total()->set_split_births(total()->split_births() + fl->split_births());
1217 total()->set_splitDeaths(total()->splitDeaths() + fl->splitDeaths()); 1217 total()->set_split_deaths(total()->split_deaths() + fl->split_deaths());
1218 } 1218 }
1219 }; 1219 };
1220 1220
1221 template <class Chunk> 1221 template <class Chunk>
1222 void BinaryTreeDictionary<Chunk>::printDictCensus(void) const { 1222 void BinaryTreeDictionary<Chunk>::print_dict_census(void) const {
1223 1223
1224 gclog_or_tty->print("\nBinaryTree\n"); 1224 gclog_or_tty->print("\nBinaryTree\n");
1225 FreeList<Chunk>::print_labels_on(gclog_or_tty, "size"); 1225 FreeList<Chunk>::print_labels_on(gclog_or_tty, "size");
1226 PrintTreeCensusClosure<Chunk> ptc; 1226 PrintTreeCensusClosure<Chunk> ptc;
1227 ptc.do_tree(root()); 1227 ptc.do_tree(root());
1228 1228
1229 FreeList<Chunk>* total = ptc.total(); 1229 FreeList<Chunk>* total = ptc.total();
1230 FreeList<Chunk>::print_labels_on(gclog_or_tty, " "); 1230 FreeList<Chunk>::print_labels_on(gclog_or_tty, " ");
1231 total->print_on(gclog_or_tty, "TOTAL\t"); 1231 total->print_on(gclog_or_tty, "TOTAL\t");
1232 gclog_or_tty->print( 1232 gclog_or_tty->print(
1233 "totalFree(words): " SIZE_FORMAT_W(16) 1233 "total_free(words): " SIZE_FORMAT_W(16)
1234 " growth: %8.5f deficit: %8.5f\n", 1234 " growth: %8.5f deficit: %8.5f\n",
1235 ptc.totalFree(), 1235 ptc.total_free(),
1236 (double)(total->splitBirths() + total->coalBirths() 1236 (double)(total->split_births() + total->coal_births()
1237 - total->splitDeaths() - total->coalDeaths()) 1237 - total->split_deaths() - total->coal_deaths())
1238 /(total->prevSweep() != 0 ? (double)total->prevSweep() : 1.0), 1238 /(total->prev_sweep() != 0 ? (double)total->prev_sweep() : 1.0),
1239 (double)(total->desired() - total->count()) 1239 (double)(total->desired() - total->count())
1240 /(total->desired() != 0 ? (double)total->desired() : 1.0)); 1240 /(total->desired() != 0 ? (double)total->desired() : 1.0));
1241 } 1241 }
1242 1242
1243 template <class Chunk> 1243 template <class Chunk>
1277 // Verify the following tree invariants: 1277 // Verify the following tree invariants:
1278 // . _root has no parent 1278 // . _root has no parent
1279 // . parent and child point to each other 1279 // . parent and child point to each other
1280 // . each node's key correctly related to that of its child(ren) 1280 // . each node's key correctly related to that of its child(ren)
1281 template <class Chunk> 1281 template <class Chunk>
1282 void BinaryTreeDictionary<Chunk>::verifyTree() const { 1282 void BinaryTreeDictionary<Chunk>::verify_tree() const {
1283 guarantee(root() == NULL || totalFreeBlocks() == 0 || 1283 guarantee(root() == NULL || total_free_blocks() == 0 ||
1284 totalSize() != 0, "_totalSize should't be 0?"); 1284 total_size() != 0, "_total_size should't be 0?");
1285 guarantee(root() == NULL || root()->parent() == NULL, "_root shouldn't have parent"); 1285 guarantee(root() == NULL || root()->parent() == NULL, "_root shouldn't have parent");
1286 verifyTreeHelper(root()); 1286 verify_tree_helper(root());
1287 } 1287 }
1288 1288
1289 template <class Chunk> 1289 template <class Chunk>
1290 size_t BinaryTreeDictionary<Chunk>::verifyPrevFreePtrs(TreeList<Chunk>* tl) { 1290 size_t BinaryTreeDictionary<Chunk>::verify_prev_free_ptrs(TreeList<Chunk>* tl) {
1291 size_t ct = 0; 1291 size_t ct = 0;
1292 for (Chunk* curFC = tl->head(); curFC != NULL; curFC = curFC->next()) { 1292 for (Chunk* curFC = tl->head(); curFC != NULL; curFC = curFC->next()) {
1293 ct++; 1293 ct++;
1294 assert(curFC->prev() == NULL || curFC->prev()->isFree(), 1294 assert(curFC->prev() == NULL || curFC->prev()->is_free(),
1295 "Chunk should be free"); 1295 "Chunk should be free");
1296 } 1296 }
1297 return ct; 1297 return ct;
1298 } 1298 }
1299 1299
1300 // Note: this helper is recursive rather than iterative, so use with 1300 // Note: this helper is recursive rather than iterative, so use with
1301 // caution on very deep trees; and watch out for stack overflow errors; 1301 // caution on very deep trees; and watch out for stack overflow errors;
1302 // In general, to be used only for debugging. 1302 // In general, to be used only for debugging.
1303 template <class Chunk> 1303 template <class Chunk>
1304 void BinaryTreeDictionary<Chunk>::verifyTreeHelper(TreeList<Chunk>* tl) const { 1304 void BinaryTreeDictionary<Chunk>::verify_tree_helper(TreeList<Chunk>* tl) const {
1305 if (tl == NULL) 1305 if (tl == NULL)
1306 return; 1306 return;
1307 guarantee(tl->size() != 0, "A list must has a size"); 1307 guarantee(tl->size() != 0, "A list must has a size");
1308 guarantee(tl->left() == NULL || tl->left()->parent() == tl, 1308 guarantee(tl->left() == NULL || tl->left()->parent() == tl,
1309 "parent<-/->left"); 1309 "parent<-/->left");
1311 "parent<-/->right");; 1311 "parent<-/->right");;
1312 guarantee(tl->left() == NULL || tl->left()->size() < tl->size(), 1312 guarantee(tl->left() == NULL || tl->left()->size() < tl->size(),
1313 "parent !> left"); 1313 "parent !> left");
1314 guarantee(tl->right() == NULL || tl->right()->size() > tl->size(), 1314 guarantee(tl->right() == NULL || tl->right()->size() > tl->size(),
1315 "parent !< left"); 1315 "parent !< left");
1316 guarantee(tl->head() == NULL || tl->head()->isFree(), "!Free"); 1316 guarantee(tl->head() == NULL || tl->head()->is_free(), "!Free");
1317 guarantee(tl->head() == NULL || tl->head_as_TreeChunk()->list() == tl, 1317 guarantee(tl->head() == NULL || tl->head_as_TreeChunk()->list() == tl,
1318 "list inconsistency"); 1318 "list inconsistency");
1319 guarantee(tl->count() > 0 || (tl->head() == NULL && tl->tail() == NULL), 1319 guarantee(tl->count() > 0 || (tl->head() == NULL && tl->tail() == NULL),
1320 "list count is inconsistent"); 1320 "list count is inconsistent");
1321 guarantee(tl->count() > 1 || tl->head() == tl->tail(), 1321 guarantee(tl->count() > 1 || tl->head() == tl->tail(),
1322 "list is incorrectly constructed"); 1322 "list is incorrectly constructed");
1323 size_t count = verifyPrevFreePtrs(tl); 1323 size_t count = verify_prev_free_ptrs(tl);
1324 guarantee(count == (size_t)tl->count(), "Node count is incorrect"); 1324 guarantee(count == (size_t)tl->count(), "Node count is incorrect");
1325 if (tl->head() != NULL) { 1325 if (tl->head() != NULL) {
1326 tl->head_as_TreeChunk()->verifyTreeChunkList(); 1326 tl->head_as_TreeChunk()->verify_tree_chunk_list();
1327 } 1327 }
1328 verifyTreeHelper(tl->left()); 1328 verify_tree_helper(tl->left());
1329 verifyTreeHelper(tl->right()); 1329 verify_tree_helper(tl->right());
1330 } 1330 }
1331 1331
1332 template <class Chunk> 1332 template <class Chunk>
1333 void BinaryTreeDictionary<Chunk>::verify() const { 1333 void BinaryTreeDictionary<Chunk>::verify() const {
1334 verifyTree(); 1334 verify_tree();
1335 guarantee(totalSize() == totalSizeInTree(root()), "Total Size inconsistency"); 1335 guarantee(total_size() == total_size_in_tree(root()), "Total Size inconsistency");
1336 } 1336 }
1337 1337
1338 #ifndef SERIALGC 1338 #ifndef SERIALGC
1339 // Explicitly instantiate these types for FreeChunk. 1339 // Explicitly instantiate these types for FreeChunk.
1340 template class BinaryTreeDictionary<FreeChunk>; 1340 template class BinaryTreeDictionary<FreeChunk>;