Mercurial > hg > truffle
comparison src/share/vm/memory/binaryTreeDictionary.cpp @ 17695:ab36007d6358
8034171: Remove use of template template parameters from binaryTreeDictionary.
Reviewed-by: mgerdin, jmasa
Contributed-by: matthias.baesken@sap.com
author | goetz |
---|---|
date | Tue, 11 Feb 2014 09:34:50 +0100 |
parents | bdfbb1fb19ca |
children | 78bbf4d43a14 |
comparison
equal
deleted
inserted
replaced
17694:cc3f124c6eae | 17695:ab36007d6358 |
---|---|
42 //////////////////////////////////////////////////////////////////////////////// | 42 //////////////////////////////////////////////////////////////////////////////// |
43 // A binary tree based search structure for free blocks. | 43 // A binary tree based search structure for free blocks. |
44 // This is currently used in the Concurrent Mark&Sweep implementation. | 44 // This is currently used in the Concurrent Mark&Sweep implementation. |
45 //////////////////////////////////////////////////////////////////////////////// | 45 //////////////////////////////////////////////////////////////////////////////// |
46 | 46 |
47 template <class Chunk_t, template <class> class FreeList_t> | 47 template <class Chunk_t, class FreeList_t> |
48 size_t TreeChunk<Chunk_t, FreeList_t>::_min_tree_chunk_size = sizeof(TreeChunk<Chunk_t, FreeList_t>)/HeapWordSize; | 48 size_t TreeChunk<Chunk_t, FreeList_t>::_min_tree_chunk_size = sizeof(TreeChunk<Chunk_t, FreeList_t>)/HeapWordSize; |
49 | 49 |
50 template <class Chunk_t, template <class> class FreeList_t> | 50 template <class Chunk_t, class FreeList_t> |
51 TreeChunk<Chunk_t, FreeList_t>* TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(Chunk_t* fc) { | 51 TreeChunk<Chunk_t, FreeList_t>* TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(Chunk_t* fc) { |
52 // Do some assertion checking here. | 52 // Do some assertion checking here. |
53 return (TreeChunk<Chunk_t, FreeList_t>*) fc; | 53 return (TreeChunk<Chunk_t, FreeList_t>*) fc; |
54 } | 54 } |
55 | 55 |
56 template <class Chunk_t, template <class> class FreeList_t> | 56 template <class Chunk_t, class FreeList_t> |
57 void TreeChunk<Chunk_t, FreeList_t>::verify_tree_chunk_list() const { | 57 void TreeChunk<Chunk_t, FreeList_t>::verify_tree_chunk_list() const { |
58 TreeChunk<Chunk_t, FreeList_t>* nextTC = (TreeChunk<Chunk_t, FreeList_t>*)next(); | 58 TreeChunk<Chunk_t, FreeList_t>* nextTC = (TreeChunk<Chunk_t, FreeList_t>*)next(); |
59 if (prev() != NULL) { // interior list node shouldn'r have tree fields | 59 if (prev() != NULL) { // interior list node shouldn'r have tree fields |
60 guarantee(embedded_list()->parent() == NULL && embedded_list()->left() == NULL && | 60 guarantee(embedded_list()->parent() == NULL && embedded_list()->left() == NULL && |
61 embedded_list()->right() == NULL, "should be clear"); | 61 embedded_list()->right() == NULL, "should be clear"); |
65 guarantee(nextTC->size() == size(), "wrong size"); | 65 guarantee(nextTC->size() == size(), "wrong size"); |
66 nextTC->verify_tree_chunk_list(); | 66 nextTC->verify_tree_chunk_list(); |
67 } | 67 } |
68 } | 68 } |
69 | 69 |
70 template <class Chunk_t, template <class> class FreeList_t> | 70 template <class Chunk_t, class FreeList_t> |
71 TreeList<Chunk_t, FreeList_t>::TreeList() : _parent(NULL), | 71 TreeList<Chunk_t, FreeList_t>::TreeList() : _parent(NULL), |
72 _left(NULL), _right(NULL) {} | 72 _left(NULL), _right(NULL) {} |
73 | 73 |
74 template <class Chunk_t, template <class> class FreeList_t> | 74 template <class Chunk_t, class FreeList_t> |
75 TreeList<Chunk_t, FreeList_t>* | 75 TreeList<Chunk_t, FreeList_t>* |
76 TreeList<Chunk_t, FreeList_t>::as_TreeList(TreeChunk<Chunk_t,FreeList_t>* tc) { | 76 TreeList<Chunk_t, FreeList_t>::as_TreeList(TreeChunk<Chunk_t,FreeList_t>* tc) { |
77 // This first free chunk in the list will be the tree list. | 77 // This first free chunk in the list will be the tree list. |
78 assert((tc->size() >= (TreeChunk<Chunk_t, FreeList_t>::min_size())), | 78 assert((tc->size() >= (TreeChunk<Chunk_t, FreeList_t>::min_size())), |
79 "Chunk is too small for a TreeChunk"); | 79 "Chunk is too small for a TreeChunk"); |
86 tl->set_count(1); | 86 tl->set_count(1); |
87 assert(tl->parent() == NULL, "Should be clear"); | 87 assert(tl->parent() == NULL, "Should be clear"); |
88 return tl; | 88 return tl; |
89 } | 89 } |
90 | 90 |
91 | 91 template <class Chunk_t, class FreeList_t> |
92 template <class Chunk_t, template <class> class FreeList_t> | |
93 TreeList<Chunk_t, FreeList_t>* | |
94 get_chunk(size_t size, enum FreeBlockDictionary<Chunk_t>::Dither dither) { | |
95 FreeBlockDictionary<Chunk_t>::verify_par_locked(); | |
96 Chunk_t* res = get_chunk_from_tree(size, dither); | |
97 assert(res == NULL || res->is_free(), | |
98 "Should be returning a free chunk"); | |
99 assert(dither != FreeBlockDictionary<Chunk_t>::exactly || | |
100 res->size() == size, "Not correct size"); | |
101 return res; | |
102 } | |
103 | |
104 template <class Chunk_t, template <class> class FreeList_t> | |
105 TreeList<Chunk_t, FreeList_t>* | 92 TreeList<Chunk_t, FreeList_t>* |
106 TreeList<Chunk_t, FreeList_t>::as_TreeList(HeapWord* addr, size_t size) { | 93 TreeList<Chunk_t, FreeList_t>::as_TreeList(HeapWord* addr, size_t size) { |
107 TreeChunk<Chunk_t, FreeList_t>* tc = (TreeChunk<Chunk_t, FreeList_t>*) addr; | 94 TreeChunk<Chunk_t, FreeList_t>* tc = (TreeChunk<Chunk_t, FreeList_t>*) addr; |
108 assert((size >= TreeChunk<Chunk_t, FreeList_t>::min_size()), | 95 assert((size >= TreeChunk<Chunk_t, FreeList_t>::min_size()), |
109 "Chunk is too small for a TreeChunk"); | 96 "Chunk is too small for a TreeChunk"); |
123 // Specialize for AdaptiveFreeList which tries to avoid | 110 // Specialize for AdaptiveFreeList which tries to avoid |
124 // splitting a chunk of a size that is under populated in favor of | 111 // splitting a chunk of a size that is under populated in favor of |
125 // an over populated size. The general get_better_list() just returns | 112 // an over populated size. The general get_better_list() just returns |
126 // the current list. | 113 // the current list. |
127 template <> | 114 template <> |
128 TreeList<FreeChunk, AdaptiveFreeList>* | 115 TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >* |
129 TreeList<FreeChunk, AdaptiveFreeList>::get_better_list( | 116 TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >::get_better_list( |
130 BinaryTreeDictionary<FreeChunk, ::AdaptiveFreeList>* dictionary) { | 117 BinaryTreeDictionary<FreeChunk, ::AdaptiveFreeList<FreeChunk> >* dictionary) { |
131 // A candidate chunk has been found. If it is already under | 118 // A candidate chunk has been found. If it is already under |
132 // populated, get a chunk associated with the hint for this | 119 // populated, get a chunk associated with the hint for this |
133 // chunk. | 120 // chunk. |
134 | 121 |
135 TreeList<FreeChunk, ::AdaptiveFreeList>* curTL = this; | 122 TreeList<FreeChunk, ::AdaptiveFreeList<FreeChunk> >* curTL = this; |
136 if (surplus() <= 0) { | 123 if (surplus() <= 0) { |
137 /* Use the hint to find a size with a surplus, and reset the hint. */ | 124 /* Use the hint to find a size with a surplus, and reset the hint. */ |
138 TreeList<FreeChunk, ::AdaptiveFreeList>* hintTL = this; | 125 TreeList<FreeChunk, ::AdaptiveFreeList<FreeChunk> >* hintTL = this; |
139 while (hintTL->hint() != 0) { | 126 while (hintTL->hint() != 0) { |
140 assert(hintTL->hint() > hintTL->size(), | 127 assert(hintTL->hint() > hintTL->size(), |
141 "hint points in the wrong direction"); | 128 "hint points in the wrong direction"); |
142 hintTL = dictionary->find_list(hintTL->hint()); | 129 hintTL = dictionary->find_list(hintTL->hint()); |
143 assert(curTL != hintTL, "Infinite loop"); | 130 assert(curTL != hintTL, "Infinite loop"); |
161 } | 148 } |
162 return curTL; | 149 return curTL; |
163 } | 150 } |
164 #endif // INCLUDE_ALL_GCS | 151 #endif // INCLUDE_ALL_GCS |
165 | 152 |
166 template <class Chunk_t, template <class> class FreeList_t> | 153 template <class Chunk_t, class FreeList_t> |
167 TreeList<Chunk_t, FreeList_t>* | 154 TreeList<Chunk_t, FreeList_t>* |
168 TreeList<Chunk_t, FreeList_t>::get_better_list( | 155 TreeList<Chunk_t, FreeList_t>::get_better_list( |
169 BinaryTreeDictionary<Chunk_t, FreeList_t>* dictionary) { | 156 BinaryTreeDictionary<Chunk_t, FreeList_t>* dictionary) { |
170 return this; | 157 return this; |
171 } | 158 } |
172 | 159 |
173 template <class Chunk_t, template <class> class FreeList_t> | 160 template <class Chunk_t, class FreeList_t> |
174 TreeList<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::remove_chunk_replace_if_needed(TreeChunk<Chunk_t, FreeList_t>* tc) { | 161 TreeList<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::remove_chunk_replace_if_needed(TreeChunk<Chunk_t, FreeList_t>* tc) { |
175 | 162 |
176 TreeList<Chunk_t, FreeList_t>* retTL = this; | 163 TreeList<Chunk_t, FreeList_t>* retTL = this; |
177 Chunk_t* list = head(); | 164 Chunk_t* list = head(); |
178 assert(!list || list != list->next(), "Chunk on list twice"); | 165 assert(!list || list != list->next(), "Chunk on list twice"); |
284 assert(retTL->tail() == NULL || retTL->tail()->next() == NULL, | 271 assert(retTL->tail() == NULL || retTL->tail()->next() == NULL, |
285 "list invariant"); | 272 "list invariant"); |
286 return retTL; | 273 return retTL; |
287 } | 274 } |
288 | 275 |
289 template <class Chunk_t, template <class> class FreeList_t> | 276 template <class Chunk_t, class FreeList_t> |
290 void TreeList<Chunk_t, FreeList_t>::return_chunk_at_tail(TreeChunk<Chunk_t, FreeList_t>* chunk) { | 277 void TreeList<Chunk_t, FreeList_t>::return_chunk_at_tail(TreeChunk<Chunk_t, FreeList_t>* chunk) { |
291 assert(chunk != NULL, "returning NULL chunk"); | 278 assert(chunk != NULL, "returning NULL chunk"); |
292 assert(chunk->list() == this, "list should be set for chunk"); | 279 assert(chunk->list() == this, "list should be set for chunk"); |
293 assert(tail() != NULL, "The tree list is embedded in the first chunk"); | 280 assert(tail() != NULL, "The tree list is embedded in the first chunk"); |
294 // which means that the list can never be empty. | 281 // which means that the list can never be empty. |
299 Chunk_t* fc = tail(); | 286 Chunk_t* fc = tail(); |
300 fc->link_after(chunk); | 287 fc->link_after(chunk); |
301 this->link_tail(chunk); | 288 this->link_tail(chunk); |
302 | 289 |
303 assert(!tail() || size() == tail()->size(), "Wrong sized chunk in list"); | 290 assert(!tail() || size() == tail()->size(), "Wrong sized chunk in list"); |
304 FreeList_t<Chunk_t>::increment_count(); | 291 FreeList_t::increment_count(); |
305 debug_only(this->increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));) | 292 debug_only(this->increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));) |
306 assert(head() == NULL || head()->prev() == NULL, "list invariant"); | 293 assert(head() == NULL || head()->prev() == NULL, "list invariant"); |
307 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); | 294 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); |
308 } | 295 } |
309 | 296 |
310 // Add this chunk at the head of the list. "At the head of the list" | 297 // Add this chunk at the head of the list. "At the head of the list" |
311 // is defined to be after the chunk pointer to by head(). This is | 298 // is defined to be after the chunk pointer to by head(). This is |
312 // because the TreeList<Chunk_t, FreeList_t> is embedded in the first TreeChunk<Chunk_t, FreeList_t> in the | 299 // because the TreeList<Chunk_t, FreeList_t> is embedded in the first TreeChunk<Chunk_t, FreeList_t> in the |
313 // list. See the definition of TreeChunk<Chunk_t, FreeList_t>. | 300 // list. See the definition of TreeChunk<Chunk_t, FreeList_t>. |
314 template <class Chunk_t, template <class> class FreeList_t> | 301 template <class Chunk_t, class FreeList_t> |
315 void TreeList<Chunk_t, FreeList_t>::return_chunk_at_head(TreeChunk<Chunk_t, FreeList_t>* chunk) { | 302 void TreeList<Chunk_t, FreeList_t>::return_chunk_at_head(TreeChunk<Chunk_t, FreeList_t>* chunk) { |
316 assert(chunk->list() == this, "list should be set for chunk"); | 303 assert(chunk->list() == this, "list should be set for chunk"); |
317 assert(head() != NULL, "The tree list is embedded in the first chunk"); | 304 assert(head() != NULL, "The tree list is embedded in the first chunk"); |
318 assert(chunk != NULL, "returning NULL chunk"); | 305 assert(chunk != NULL, "returning NULL chunk"); |
319 assert(!this->verify_chunk_in_free_list(chunk), "Double entry"); | 306 assert(!this->verify_chunk_in_free_list(chunk), "Double entry"); |
327 assert(tail() == NULL, "List is inconsistent"); | 314 assert(tail() == NULL, "List is inconsistent"); |
328 this->link_tail(chunk); | 315 this->link_tail(chunk); |
329 } | 316 } |
330 head()->link_after(chunk); | 317 head()->link_after(chunk); |
331 assert(!head() || size() == head()->size(), "Wrong sized chunk in list"); | 318 assert(!head() || size() == head()->size(), "Wrong sized chunk in list"); |
332 FreeList_t<Chunk_t>::increment_count(); | 319 FreeList_t::increment_count(); |
333 debug_only(this->increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));) | 320 debug_only(this->increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));) |
334 assert(head() == NULL || head()->prev() == NULL, "list invariant"); | 321 assert(head() == NULL || head()->prev() == NULL, "list invariant"); |
335 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); | 322 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); |
336 } | 323 } |
337 | 324 |
338 template <class Chunk_t, template <class> class FreeList_t> | 325 template <class Chunk_t, class FreeList_t> |
339 void TreeChunk<Chunk_t, FreeList_t>::assert_is_mangled() const { | 326 void TreeChunk<Chunk_t, FreeList_t>::assert_is_mangled() const { |
340 assert((ZapUnusedHeapArea && | 327 assert((ZapUnusedHeapArea && |
341 SpaceMangler::is_mangled((HeapWord*) Chunk_t::size_addr()) && | 328 SpaceMangler::is_mangled((HeapWord*) Chunk_t::size_addr()) && |
342 SpaceMangler::is_mangled((HeapWord*) Chunk_t::prev_addr()) && | 329 SpaceMangler::is_mangled((HeapWord*) Chunk_t::prev_addr()) && |
343 SpaceMangler::is_mangled((HeapWord*) Chunk_t::next_addr())) || | 330 SpaceMangler::is_mangled((HeapWord*) Chunk_t::next_addr())) || |
344 (size() == 0 && prev() == NULL && next() == NULL), | 331 (size() == 0 && prev() == NULL && next() == NULL), |
345 "Space should be clear or mangled"); | 332 "Space should be clear or mangled"); |
346 } | 333 } |
347 | 334 |
348 template <class Chunk_t, template <class> class FreeList_t> | 335 template <class Chunk_t, class FreeList_t> |
349 TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::head_as_TreeChunk() { | 336 TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::head_as_TreeChunk() { |
350 assert(head() == NULL || (TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(head())->list() == this), | 337 assert(head() == NULL || (TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(head())->list() == this), |
351 "Wrong type of chunk?"); | 338 "Wrong type of chunk?"); |
352 return TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(head()); | 339 return TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(head()); |
353 } | 340 } |
354 | 341 |
355 template <class Chunk_t, template <class> class FreeList_t> | 342 template <class Chunk_t, class FreeList_t> |
356 TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::first_available() { | 343 TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::first_available() { |
357 assert(head() != NULL, "The head of the list cannot be NULL"); | 344 assert(head() != NULL, "The head of the list cannot be NULL"); |
358 Chunk_t* fc = head()->next(); | 345 Chunk_t* fc = head()->next(); |
359 TreeChunk<Chunk_t, FreeList_t>* retTC; | 346 TreeChunk<Chunk_t, FreeList_t>* retTC; |
360 if (fc == NULL) { | 347 if (fc == NULL) { |
367 } | 354 } |
368 | 355 |
369 // Returns the block with the largest heap address amongst | 356 // Returns the block with the largest heap address amongst |
370 // those in the list for this size; potentially slow and expensive, | 357 // those in the list for this size; potentially slow and expensive, |
371 // use with caution! | 358 // use with caution! |
372 template <class Chunk_t, template <class> class FreeList_t> | 359 template <class Chunk_t, class FreeList_t> |
373 TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::largest_address() { | 360 TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::largest_address() { |
374 assert(head() != NULL, "The head of the list cannot be NULL"); | 361 assert(head() != NULL, "The head of the list cannot be NULL"); |
375 Chunk_t* fc = head()->next(); | 362 Chunk_t* fc = head()->next(); |
376 TreeChunk<Chunk_t, FreeList_t>* retTC; | 363 TreeChunk<Chunk_t, FreeList_t>* retTC; |
377 if (fc == NULL) { | 364 if (fc == NULL) { |
390 } | 377 } |
391 assert(retTC->list() == this, "Wrong type of chunk."); | 378 assert(retTC->list() == this, "Wrong type of chunk."); |
392 return retTC; | 379 return retTC; |
393 } | 380 } |
394 | 381 |
395 template <class Chunk_t, template <class> class FreeList_t> | 382 template <class Chunk_t, class FreeList_t> |
396 BinaryTreeDictionary<Chunk_t, FreeList_t>::BinaryTreeDictionary(MemRegion mr) { | 383 BinaryTreeDictionary<Chunk_t, FreeList_t>::BinaryTreeDictionary(MemRegion mr) { |
397 assert((mr.byte_size() > min_size()), "minimum chunk size"); | 384 assert((mr.byte_size() > min_size()), "minimum chunk size"); |
398 | 385 |
399 reset(mr); | 386 reset(mr); |
400 assert(root()->left() == NULL, "reset check failed"); | 387 assert(root()->left() == NULL, "reset check failed"); |
403 assert(root()->head()->prev() == NULL, "reset check failed"); | 390 assert(root()->head()->prev() == NULL, "reset check failed"); |
404 assert(total_size() == root()->size(), "reset check failed"); | 391 assert(total_size() == root()->size(), "reset check failed"); |
405 assert(total_free_blocks() == 1, "reset check failed"); | 392 assert(total_free_blocks() == 1, "reset check failed"); |
406 } | 393 } |
407 | 394 |
408 template <class Chunk_t, template <class> class FreeList_t> | 395 template <class Chunk_t, class FreeList_t> |
409 void BinaryTreeDictionary<Chunk_t, FreeList_t>::inc_total_size(size_t inc) { | 396 void BinaryTreeDictionary<Chunk_t, FreeList_t>::inc_total_size(size_t inc) { |
410 _total_size = _total_size + inc; | 397 _total_size = _total_size + inc; |
411 } | 398 } |
412 | 399 |
413 template <class Chunk_t, template <class> class FreeList_t> | 400 template <class Chunk_t, class FreeList_t> |
414 void BinaryTreeDictionary<Chunk_t, FreeList_t>::dec_total_size(size_t dec) { | 401 void BinaryTreeDictionary<Chunk_t, FreeList_t>::dec_total_size(size_t dec) { |
415 _total_size = _total_size - dec; | 402 _total_size = _total_size - dec; |
416 } | 403 } |
417 | 404 |
418 template <class Chunk_t, template <class> class FreeList_t> | 405 template <class Chunk_t, class FreeList_t> |
419 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset(MemRegion mr) { | 406 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset(MemRegion mr) { |
420 assert((mr.byte_size() > min_size()), "minimum chunk size"); | 407 assert((mr.byte_size() > min_size()), "minimum chunk size"); |
421 set_root(TreeList<Chunk_t, FreeList_t>::as_TreeList(mr.start(), mr.word_size())); | 408 set_root(TreeList<Chunk_t, FreeList_t>::as_TreeList(mr.start(), mr.word_size())); |
422 set_total_size(mr.word_size()); | 409 set_total_size(mr.word_size()); |
423 set_total_free_blocks(1); | 410 set_total_free_blocks(1); |
424 } | 411 } |
425 | 412 |
426 template <class Chunk_t, template <class> class FreeList_t> | 413 template <class Chunk_t, class FreeList_t> |
427 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset(HeapWord* addr, size_t byte_size) { | 414 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset(HeapWord* addr, size_t byte_size) { |
428 MemRegion mr(addr, heap_word_size(byte_size)); | 415 MemRegion mr(addr, heap_word_size(byte_size)); |
429 reset(mr); | 416 reset(mr); |
430 } | 417 } |
431 | 418 |
432 template <class Chunk_t, template <class> class FreeList_t> | 419 template <class Chunk_t, class FreeList_t> |
433 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset() { | 420 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset() { |
434 set_root(NULL); | 421 set_root(NULL); |
435 set_total_size(0); | 422 set_total_size(0); |
436 set_total_free_blocks(0); | 423 set_total_free_blocks(0); |
437 } | 424 } |
438 | 425 |
439 // Get a free block of size at least size from tree, or NULL. | 426 // Get a free block of size at least size from tree, or NULL. |
440 template <class Chunk_t, template <class> class FreeList_t> | 427 template <class Chunk_t, class FreeList_t> |
441 TreeChunk<Chunk_t, FreeList_t>* | 428 TreeChunk<Chunk_t, FreeList_t>* |
442 BinaryTreeDictionary<Chunk_t, FreeList_t>::get_chunk_from_tree( | 429 BinaryTreeDictionary<Chunk_t, FreeList_t>::get_chunk_from_tree( |
443 size_t size, | 430 size_t size, |
444 enum FreeBlockDictionary<Chunk_t>::Dither dither) | 431 enum FreeBlockDictionary<Chunk_t>::Dither dither) |
445 { | 432 { |
494 verify(); | 481 verify(); |
495 } | 482 } |
496 return retTC; | 483 return retTC; |
497 } | 484 } |
498 | 485 |
499 template <class Chunk_t, template <class> class FreeList_t> | 486 template <class Chunk_t, class FreeList_t> |
500 TreeList<Chunk_t, FreeList_t>* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_list(size_t size) const { | 487 TreeList<Chunk_t, FreeList_t>* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_list(size_t size) const { |
501 TreeList<Chunk_t, FreeList_t>* curTL; | 488 TreeList<Chunk_t, FreeList_t>* curTL; |
502 for (curTL = root(); curTL != NULL;) { | 489 for (curTL = root(); curTL != NULL;) { |
503 if (curTL->size() == size) { // exact match | 490 if (curTL->size() == size) { // exact match |
504 break; | 491 break; |
513 } | 500 } |
514 return curTL; | 501 return curTL; |
515 } | 502 } |
516 | 503 |
517 | 504 |
518 template <class Chunk_t, template <class> class FreeList_t> | 505 template <class Chunk_t, class FreeList_t> |
519 bool BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_chunk_in_free_list(Chunk_t* tc) const { | 506 bool BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_chunk_in_free_list(Chunk_t* tc) const { |
520 size_t size = tc->size(); | 507 size_t size = tc->size(); |
521 TreeList<Chunk_t, FreeList_t>* tl = find_list(size); | 508 TreeList<Chunk_t, FreeList_t>* tl = find_list(size); |
522 if (tl == NULL) { | 509 if (tl == NULL) { |
523 return false; | 510 return false; |
524 } else { | 511 } else { |
525 return tl->verify_chunk_in_free_list(tc); | 512 return tl->verify_chunk_in_free_list(tc); |
526 } | 513 } |
527 } | 514 } |
528 | 515 |
529 template <class Chunk_t, template <class> class FreeList_t> | 516 template <class Chunk_t, class FreeList_t> |
530 Chunk_t* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_largest_dict() const { | 517 Chunk_t* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_largest_dict() const { |
531 TreeList<Chunk_t, FreeList_t> *curTL = root(); | 518 TreeList<Chunk_t, FreeList_t> *curTL = root(); |
532 if (curTL != NULL) { | 519 if (curTL != NULL) { |
533 while(curTL->right() != NULL) curTL = curTL->right(); | 520 while(curTL->right() != NULL) curTL = curTL->right(); |
534 return curTL->largest_address(); | 521 return curTL->largest_address(); |
539 | 526 |
540 // Remove the current chunk from the tree. If it is not the last | 527 // Remove the current chunk from the tree. If it is not the last |
541 // chunk in a list on a tree node, just unlink it. | 528 // chunk in a list on a tree node, just unlink it. |
542 // If it is the last chunk in the list (the next link is NULL), | 529 // If it is the last chunk in the list (the next link is NULL), |
543 // remove the node and repair the tree. | 530 // remove the node and repair the tree. |
544 template <class Chunk_t, template <class> class FreeList_t> | 531 template <class Chunk_t, class FreeList_t> |
545 TreeChunk<Chunk_t, FreeList_t>* | 532 TreeChunk<Chunk_t, FreeList_t>* |
546 BinaryTreeDictionary<Chunk_t, FreeList_t>::remove_chunk_from_tree(TreeChunk<Chunk_t, FreeList_t>* tc) { | 533 BinaryTreeDictionary<Chunk_t, FreeList_t>::remove_chunk_from_tree(TreeChunk<Chunk_t, FreeList_t>* tc) { |
547 assert(tc != NULL, "Should not call with a NULL chunk"); | 534 assert(tc != NULL, "Should not call with a NULL chunk"); |
548 assert(tc->is_free(), "Header is not marked correctly"); | 535 assert(tc->is_free(), "Header is not marked correctly"); |
549 | 536 |
680 } | 667 } |
681 | 668 |
682 // Remove the leftmost node (lm) in the tree and return it. | 669 // Remove the leftmost node (lm) in the tree and return it. |
683 // If lm has a right child, link it to the left node of | 670 // If lm has a right child, link it to the left node of |
684 // the parent of lm. | 671 // the parent of lm. |
685 template <class Chunk_t, template <class> class FreeList_t> | 672 template <class Chunk_t, class FreeList_t> |
686 TreeList<Chunk_t, FreeList_t>* BinaryTreeDictionary<Chunk_t, FreeList_t>::remove_tree_minimum(TreeList<Chunk_t, FreeList_t>* tl) { | 673 TreeList<Chunk_t, FreeList_t>* BinaryTreeDictionary<Chunk_t, FreeList_t>::remove_tree_minimum(TreeList<Chunk_t, FreeList_t>* tl) { |
687 assert(tl != NULL && tl->parent() != NULL, "really need a proper sub-tree"); | 674 assert(tl != NULL && tl->parent() != NULL, "really need a proper sub-tree"); |
688 // locate the subtree minimum by walking down left branches | 675 // locate the subtree minimum by walking down left branches |
689 TreeList<Chunk_t, FreeList_t>* curTL = tl; | 676 TreeList<Chunk_t, FreeList_t>* curTL = tl; |
690 for (; curTL->left() != NULL; curTL = curTL->left()); | 677 for (; curTL->left() != NULL; curTL = curTL->left()); |
715 verify_tree(); | 702 verify_tree(); |
716 } | 703 } |
717 return curTL; | 704 return curTL; |
718 } | 705 } |
719 | 706 |
720 template <class Chunk_t, template <class> class FreeList_t> | 707 template <class Chunk_t, class FreeList_t> |
721 void BinaryTreeDictionary<Chunk_t, FreeList_t>::insert_chunk_in_tree(Chunk_t* fc) { | 708 void BinaryTreeDictionary<Chunk_t, FreeList_t>::insert_chunk_in_tree(Chunk_t* fc) { |
722 TreeList<Chunk_t, FreeList_t> *curTL, *prevTL; | 709 TreeList<Chunk_t, FreeList_t> *curTL, *prevTL; |
723 size_t size = fc->size(); | 710 size_t size = fc->size(); |
724 | 711 |
725 assert((size >= min_size()), | 712 assert((size >= min_size()), |
781 if (FLSVerifyDictionary) { | 768 if (FLSVerifyDictionary) { |
782 verify_tree(); | 769 verify_tree(); |
783 } | 770 } |
784 } | 771 } |
785 | 772 |
786 template <class Chunk_t, template <class> class FreeList_t> | 773 template <class Chunk_t, class FreeList_t> |
787 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::max_chunk_size() const { | 774 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::max_chunk_size() const { |
788 FreeBlockDictionary<Chunk_t>::verify_par_locked(); | 775 FreeBlockDictionary<Chunk_t>::verify_par_locked(); |
789 TreeList<Chunk_t, FreeList_t>* tc = root(); | 776 TreeList<Chunk_t, FreeList_t>* tc = root(); |
790 if (tc == NULL) return 0; | 777 if (tc == NULL) return 0; |
791 for (; tc->right() != NULL; tc = tc->right()); | 778 for (; tc->right() != NULL; tc = tc->right()); |
792 return tc->size(); | 779 return tc->size(); |
793 } | 780 } |
794 | 781 |
795 template <class Chunk_t, template <class> class FreeList_t> | 782 template <class Chunk_t, class FreeList_t> |
796 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_list_length(TreeList<Chunk_t, FreeList_t>* tl) const { | 783 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_list_length(TreeList<Chunk_t, FreeList_t>* tl) const { |
797 size_t res; | 784 size_t res; |
798 res = tl->count(); | 785 res = tl->count(); |
799 #ifdef ASSERT | 786 #ifdef ASSERT |
800 size_t cnt; | 787 size_t cnt; |
803 assert(res == cnt, "The count is not being maintained correctly"); | 790 assert(res == cnt, "The count is not being maintained correctly"); |
804 #endif | 791 #endif |
805 return res; | 792 return res; |
806 } | 793 } |
807 | 794 |
808 template <class Chunk_t, template <class> class FreeList_t> | 795 template <class Chunk_t, class FreeList_t> |
809 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_size_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const { | 796 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_size_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const { |
810 if (tl == NULL) | 797 if (tl == NULL) |
811 return 0; | 798 return 0; |
812 return (tl->size() * total_list_length(tl)) + | 799 return (tl->size() * total_list_length(tl)) + |
813 total_size_in_tree(tl->left()) + | 800 total_size_in_tree(tl->left()) + |
814 total_size_in_tree(tl->right()); | 801 total_size_in_tree(tl->right()); |
815 } | 802 } |
816 | 803 |
817 template <class Chunk_t, template <class> class FreeList_t> | 804 template <class Chunk_t, class FreeList_t> |
818 double BinaryTreeDictionary<Chunk_t, FreeList_t>::sum_of_squared_block_sizes(TreeList<Chunk_t, FreeList_t>* const tl) const { | 805 double BinaryTreeDictionary<Chunk_t, FreeList_t>::sum_of_squared_block_sizes(TreeList<Chunk_t, FreeList_t>* const tl) const { |
819 if (tl == NULL) { | 806 if (tl == NULL) { |
820 return 0.0; | 807 return 0.0; |
821 } | 808 } |
822 double size = (double)(tl->size()); | 809 double size = (double)(tl->size()); |
824 curr += sum_of_squared_block_sizes(tl->left()); | 811 curr += sum_of_squared_block_sizes(tl->left()); |
825 curr += sum_of_squared_block_sizes(tl->right()); | 812 curr += sum_of_squared_block_sizes(tl->right()); |
826 return curr; | 813 return curr; |
827 } | 814 } |
828 | 815 |
829 template <class Chunk_t, template <class> class FreeList_t> | 816 template <class Chunk_t, class FreeList_t> |
830 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_free_blocks_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const { | 817 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_free_blocks_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const { |
831 if (tl == NULL) | 818 if (tl == NULL) |
832 return 0; | 819 return 0; |
833 return total_list_length(tl) + | 820 return total_list_length(tl) + |
834 total_free_blocks_in_tree(tl->left()) + | 821 total_free_blocks_in_tree(tl->left()) + |
835 total_free_blocks_in_tree(tl->right()); | 822 total_free_blocks_in_tree(tl->right()); |
836 } | 823 } |
837 | 824 |
838 template <class Chunk_t, template <class> class FreeList_t> | 825 template <class Chunk_t, class FreeList_t> |
839 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::num_free_blocks() const { | 826 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::num_free_blocks() const { |
840 assert(total_free_blocks_in_tree(root()) == total_free_blocks(), | 827 assert(total_free_blocks_in_tree(root()) == total_free_blocks(), |
841 "_total_free_blocks inconsistency"); | 828 "_total_free_blocks inconsistency"); |
842 return total_free_blocks(); | 829 return total_free_blocks(); |
843 } | 830 } |
844 | 831 |
845 template <class Chunk_t, template <class> class FreeList_t> | 832 template <class Chunk_t, class FreeList_t> |
846 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::tree_height_helper(TreeList<Chunk_t, FreeList_t>* tl) const { | 833 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::tree_height_helper(TreeList<Chunk_t, FreeList_t>* tl) const { |
847 if (tl == NULL) | 834 if (tl == NULL) |
848 return 0; | 835 return 0; |
849 return 1 + MAX2(tree_height_helper(tl->left()), | 836 return 1 + MAX2(tree_height_helper(tl->left()), |
850 tree_height_helper(tl->right())); | 837 tree_height_helper(tl->right())); |
851 } | 838 } |
852 | 839 |
853 template <class Chunk_t, template <class> class FreeList_t> | 840 template <class Chunk_t, class FreeList_t> |
854 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::tree_height() const { | 841 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::tree_height() const { |
855 return tree_height_helper(root()); | 842 return tree_height_helper(root()); |
856 } | 843 } |
857 | 844 |
858 template <class Chunk_t, template <class> class FreeList_t> | 845 template <class Chunk_t, class FreeList_t> |
859 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_nodes_helper(TreeList<Chunk_t, FreeList_t>* tl) const { | 846 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_nodes_helper(TreeList<Chunk_t, FreeList_t>* tl) const { |
860 if (tl == NULL) { | 847 if (tl == NULL) { |
861 return 0; | 848 return 0; |
862 } | 849 } |
863 return 1 + total_nodes_helper(tl->left()) + | 850 return 1 + total_nodes_helper(tl->left()) + |
864 total_nodes_helper(tl->right()); | 851 total_nodes_helper(tl->right()); |
865 } | 852 } |
866 | 853 |
867 template <class Chunk_t, template <class> class FreeList_t> | 854 template <class Chunk_t, class FreeList_t> |
868 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_nodes_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const { | 855 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_nodes_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const { |
869 return total_nodes_helper(root()); | 856 return total_nodes_helper(root()); |
870 } | 857 } |
871 | 858 |
872 template <class Chunk_t, template <class> class FreeList_t> | 859 template <class Chunk_t, class FreeList_t> |
873 void BinaryTreeDictionary<Chunk_t, FreeList_t>::dict_census_update(size_t size, bool split, bool birth){} | 860 void BinaryTreeDictionary<Chunk_t, FreeList_t>::dict_census_update(size_t size, bool split, bool birth){} |
874 | 861 |
875 #if INCLUDE_ALL_GCS | 862 #if INCLUDE_ALL_GCS |
876 template <> | 863 template <> |
877 void AFLBinaryTreeDictionary::dict_census_update(size_t size, bool split, bool birth){ | 864 void AFLBinaryTreeDictionary::dict_census_update(size_t size, bool split, bool birth) { |
878 TreeList<FreeChunk, AdaptiveFreeList>* nd = find_list(size); | 865 TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >* nd = find_list(size); |
879 if (nd) { | 866 if (nd) { |
880 if (split) { | 867 if (split) { |
881 if (birth) { | 868 if (birth) { |
882 nd->increment_split_births(); | 869 nd->increment_split_births(); |
883 nd->increment_surplus(); | 870 nd->increment_surplus(); |
901 // This is a birth associated with a LinAB. The chunk | 888 // This is a birth associated with a LinAB. The chunk |
902 // for the LinAB is not in the dictionary. | 889 // for the LinAB is not in the dictionary. |
903 } | 890 } |
904 #endif // INCLUDE_ALL_GCS | 891 #endif // INCLUDE_ALL_GCS |
905 | 892 |
906 template <class Chunk_t, template <class> class FreeList_t> | 893 template <class Chunk_t, class FreeList_t> |
907 bool BinaryTreeDictionary<Chunk_t, FreeList_t>::coal_dict_over_populated(size_t size) { | 894 bool BinaryTreeDictionary<Chunk_t, FreeList_t>::coal_dict_over_populated(size_t size) { |
908 // For the general type of freelists, encourage coalescing by | 895 // For the general type of freelists, encourage coalescing by |
909 // returning true. | 896 // returning true. |
910 return true; | 897 return true; |
911 } | 898 } |
913 #if INCLUDE_ALL_GCS | 900 #if INCLUDE_ALL_GCS |
914 template <> | 901 template <> |
915 bool AFLBinaryTreeDictionary::coal_dict_over_populated(size_t size) { | 902 bool AFLBinaryTreeDictionary::coal_dict_over_populated(size_t size) { |
916 if (FLSAlwaysCoalesceLarge) return true; | 903 if (FLSAlwaysCoalesceLarge) return true; |
917 | 904 |
918 TreeList<FreeChunk, AdaptiveFreeList>* list_of_size = find_list(size); | 905 TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >* list_of_size = find_list(size); |
919 // None of requested size implies overpopulated. | 906 // None of requested size implies overpopulated. |
920 return list_of_size == NULL || list_of_size->coal_desired() <= 0 || | 907 return list_of_size == NULL || list_of_size->coal_desired() <= 0 || |
921 list_of_size->count() > list_of_size->coal_desired(); | 908 list_of_size->count() > list_of_size->coal_desired(); |
922 } | 909 } |
923 #endif // INCLUDE_ALL_GCS | 910 #endif // INCLUDE_ALL_GCS |
926 // do_list() walks the free list in a node applying the closure | 913 // do_list() walks the free list in a node applying the closure |
927 // to each free chunk in the list | 914 // to each free chunk in the list |
928 // do_tree() walks the nodes in the binary tree applying do_list() | 915 // do_tree() walks the nodes in the binary tree applying do_list() |
929 // to each list at each node. | 916 // to each list at each node. |
930 | 917 |
931 template <class Chunk_t, template <class> class FreeList_t> | 918 template <class Chunk_t, class FreeList_t> |
932 class TreeCensusClosure : public StackObj { | 919 class TreeCensusClosure : public StackObj { |
933 protected: | 920 protected: |
934 virtual void do_list(FreeList_t<Chunk_t>* fl) = 0; | 921 virtual void do_list(FreeList_t* fl) = 0; |
935 public: | 922 public: |
936 virtual void do_tree(TreeList<Chunk_t, FreeList_t>* tl) = 0; | 923 virtual void do_tree(TreeList<Chunk_t, FreeList_t>* tl) = 0; |
937 }; | 924 }; |
938 | 925 |
939 template <class Chunk_t, template <class> class FreeList_t> | 926 template <class Chunk_t, class FreeList_t> |
940 class AscendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> { | 927 class AscendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> { |
941 public: | 928 public: |
942 void do_tree(TreeList<Chunk_t, FreeList_t>* tl) { | 929 void do_tree(TreeList<Chunk_t, FreeList_t>* tl) { |
943 if (tl != NULL) { | 930 if (tl != NULL) { |
944 do_tree(tl->left()); | 931 do_tree(tl->left()); |
946 do_tree(tl->right()); | 933 do_tree(tl->right()); |
947 } | 934 } |
948 } | 935 } |
949 }; | 936 }; |
950 | 937 |
951 template <class Chunk_t, template <class> class FreeList_t> | 938 template <class Chunk_t, class FreeList_t> |
952 class DescendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> { | 939 class DescendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> { |
953 public: | 940 public: |
954 void do_tree(TreeList<Chunk_t, FreeList_t>* tl) { | 941 void do_tree(TreeList<Chunk_t, FreeList_t>* tl) { |
955 if (tl != NULL) { | 942 if (tl != NULL) { |
956 do_tree(tl->right()); | 943 do_tree(tl->right()); |
960 } | 947 } |
961 }; | 948 }; |
962 | 949 |
963 // For each list in the tree, calculate the desired, desired | 950 // For each list in the tree, calculate the desired, desired |
964 // coalesce, count before sweep, and surplus before sweep. | 951 // coalesce, count before sweep, and surplus before sweep. |
965 template <class Chunk_t, template <class> class FreeList_t> | 952 template <class Chunk_t, class FreeList_t> |
966 class BeginSweepClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { | 953 class BeginSweepClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { |
967 double _percentage; | 954 double _percentage; |
968 float _inter_sweep_current; | 955 float _inter_sweep_current; |
969 float _inter_sweep_estimate; | 956 float _inter_sweep_estimate; |
970 float _intra_sweep_estimate; | 957 float _intra_sweep_estimate; |
993 | 980 |
994 // Used to search the tree until a condition is met. | 981 // Used to search the tree until a condition is met. |
995 // Similar to TreeCensusClosure but searches the | 982 // Similar to TreeCensusClosure but searches the |
996 // tree and returns promptly when found. | 983 // tree and returns promptly when found. |
997 | 984 |
998 template <class Chunk_t, template <class> class FreeList_t> | 985 template <class Chunk_t, class FreeList_t> |
999 class TreeSearchClosure : public StackObj { | 986 class TreeSearchClosure : public StackObj { |
1000 protected: | 987 protected: |
1001 virtual bool do_list(FreeList_t<Chunk_t>* fl) = 0; | 988 virtual bool do_list(FreeList_t* fl) = 0; |
1002 public: | 989 public: |
1003 virtual bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) = 0; | 990 virtual bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) = 0; |
1004 }; | 991 }; |
1005 | 992 |
1006 #if 0 // Don't need this yet but here for symmetry. | 993 #if 0 // Don't need this yet but here for symmetry. |
1007 template <class Chunk_t, template <class> class FreeList_t> | 994 template <class Chunk_t, class FreeList_t> |
1008 class AscendTreeSearchClosure : public TreeSearchClosure<Chunk_t> { | 995 class AscendTreeSearchClosure : public TreeSearchClosure<Chunk_t> { |
1009 public: | 996 public: |
1010 bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) { | 997 bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) { |
1011 if (tl != NULL) { | 998 if (tl != NULL) { |
1012 if (do_tree(tl->left())) return true; | 999 if (do_tree(tl->left())) return true; |
1016 return false; | 1003 return false; |
1017 } | 1004 } |
1018 }; | 1005 }; |
1019 #endif | 1006 #endif |
1020 | 1007 |
1021 template <class Chunk_t, template <class> class FreeList_t> | 1008 template <class Chunk_t, class FreeList_t> |
1022 class DescendTreeSearchClosure : public TreeSearchClosure<Chunk_t, FreeList_t> { | 1009 class DescendTreeSearchClosure : public TreeSearchClosure<Chunk_t, FreeList_t> { |
1023 public: | 1010 public: |
1024 bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) { | 1011 bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) { |
1025 if (tl != NULL) { | 1012 if (tl != NULL) { |
1026 if (do_tree(tl->right())) return true; | 1013 if (do_tree(tl->right())) return true; |
1031 } | 1018 } |
1032 }; | 1019 }; |
1033 | 1020 |
1034 // Searches the tree for a chunk that ends at the | 1021 // Searches the tree for a chunk that ends at the |
1035 // specified address. | 1022 // specified address. |
1036 template <class Chunk_t, template <class> class FreeList_t> | 1023 template <class Chunk_t, class FreeList_t> |
1037 class EndTreeSearchClosure : public DescendTreeSearchClosure<Chunk_t, FreeList_t> { | 1024 class EndTreeSearchClosure : public DescendTreeSearchClosure<Chunk_t, FreeList_t> { |
1038 HeapWord* _target; | 1025 HeapWord* _target; |
1039 Chunk_t* _found; | 1026 Chunk_t* _found; |
1040 | 1027 |
1041 public: | 1028 public: |
1042 EndTreeSearchClosure(HeapWord* target) : _target(target), _found(NULL) {} | 1029 EndTreeSearchClosure(HeapWord* target) : _target(target), _found(NULL) {} |
1043 bool do_list(FreeList_t<Chunk_t>* fl) { | 1030 bool do_list(FreeList_t* fl) { |
1044 Chunk_t* item = fl->head(); | 1031 Chunk_t* item = fl->head(); |
1045 while (item != NULL) { | 1032 while (item != NULL) { |
1046 if (item->end() == (uintptr_t*) _target) { | 1033 if (item->end() == (uintptr_t*) _target) { |
1047 _found = item; | 1034 _found = item; |
1048 return true; | 1035 return true; |
1052 return false; | 1039 return false; |
1053 } | 1040 } |
1054 Chunk_t* found() { return _found; } | 1041 Chunk_t* found() { return _found; } |
1055 }; | 1042 }; |
1056 | 1043 |
1057 template <class Chunk_t, template <class> class FreeList_t> | 1044 template <class Chunk_t, class FreeList_t> |
1058 Chunk_t* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_chunk_ends_at(HeapWord* target) const { | 1045 Chunk_t* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_chunk_ends_at(HeapWord* target) const { |
1059 EndTreeSearchClosure<Chunk_t, FreeList_t> etsc(target); | 1046 EndTreeSearchClosure<Chunk_t, FreeList_t> etsc(target); |
1060 bool found_target = etsc.do_tree(root()); | 1047 bool found_target = etsc.do_tree(root()); |
1061 assert(found_target || etsc.found() == NULL, "Consistency check"); | 1048 assert(found_target || etsc.found() == NULL, "Consistency check"); |
1062 assert(!found_target || etsc.found() != NULL, "Consistency check"); | 1049 assert(!found_target || etsc.found() != NULL, "Consistency check"); |
1063 return etsc.found(); | 1050 return etsc.found(); |
1064 } | 1051 } |
1065 | 1052 |
1066 template <class Chunk_t, template <class> class FreeList_t> | 1053 template <class Chunk_t, class FreeList_t> |
1067 void BinaryTreeDictionary<Chunk_t, FreeList_t>::begin_sweep_dict_census(double coalSurplusPercent, | 1054 void BinaryTreeDictionary<Chunk_t, FreeList_t>::begin_sweep_dict_census(double coalSurplusPercent, |
1068 float inter_sweep_current, float inter_sweep_estimate, float intra_sweep_estimate) { | 1055 float inter_sweep_current, float inter_sweep_estimate, float intra_sweep_estimate) { |
1069 BeginSweepClosure<Chunk_t, FreeList_t> bsc(coalSurplusPercent, inter_sweep_current, | 1056 BeginSweepClosure<Chunk_t, FreeList_t> bsc(coalSurplusPercent, inter_sweep_current, |
1070 inter_sweep_estimate, | 1057 inter_sweep_estimate, |
1071 intra_sweep_estimate); | 1058 intra_sweep_estimate); |
1073 } | 1060 } |
1074 | 1061 |
1075 // Closures and methods for calculating total bytes returned to the | 1062 // Closures and methods for calculating total bytes returned to the |
1076 // free lists in the tree. | 1063 // free lists in the tree. |
1077 #ifndef PRODUCT | 1064 #ifndef PRODUCT |
1078 template <class Chunk_t, template <class> class FreeList_t> | 1065 template <class Chunk_t, class FreeList_t> |
1079 class InitializeDictReturnedBytesClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { | 1066 class InitializeDictReturnedBytesClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { |
1080 public: | 1067 public: |
1081 void do_list(FreeList_t<Chunk_t>* fl) { | 1068 void do_list(FreeList_t* fl) { |
1082 fl->set_returned_bytes(0); | 1069 fl->set_returned_bytes(0); |
1083 } | 1070 } |
1084 }; | 1071 }; |
1085 | 1072 |
1086 template <class Chunk_t, template <class> class FreeList_t> | 1073 template <class Chunk_t, class FreeList_t> |
1087 void BinaryTreeDictionary<Chunk_t, FreeList_t>::initialize_dict_returned_bytes() { | 1074 void BinaryTreeDictionary<Chunk_t, FreeList_t>::initialize_dict_returned_bytes() { |
1088 InitializeDictReturnedBytesClosure<Chunk_t, FreeList_t> idrb; | 1075 InitializeDictReturnedBytesClosure<Chunk_t, FreeList_t> idrb; |
1089 idrb.do_tree(root()); | 1076 idrb.do_tree(root()); |
1090 } | 1077 } |
1091 | 1078 |
1092 template <class Chunk_t, template <class> class FreeList_t> | 1079 template <class Chunk_t, class FreeList_t> |
1093 class ReturnedBytesClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { | 1080 class ReturnedBytesClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { |
1094 size_t _dict_returned_bytes; | 1081 size_t _dict_returned_bytes; |
1095 public: | 1082 public: |
1096 ReturnedBytesClosure() { _dict_returned_bytes = 0; } | 1083 ReturnedBytesClosure() { _dict_returned_bytes = 0; } |
1097 void do_list(FreeList_t<Chunk_t>* fl) { | 1084 void do_list(FreeList_t* fl) { |
1098 _dict_returned_bytes += fl->returned_bytes(); | 1085 _dict_returned_bytes += fl->returned_bytes(); |
1099 } | 1086 } |
1100 size_t dict_returned_bytes() { return _dict_returned_bytes; } | 1087 size_t dict_returned_bytes() { return _dict_returned_bytes; } |
1101 }; | 1088 }; |
1102 | 1089 |
1103 template <class Chunk_t, template <class> class FreeList_t> | 1090 template <class Chunk_t, class FreeList_t> |
1104 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::sum_dict_returned_bytes() { | 1091 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::sum_dict_returned_bytes() { |
1105 ReturnedBytesClosure<Chunk_t, FreeList_t> rbc; | 1092 ReturnedBytesClosure<Chunk_t, FreeList_t> rbc; |
1106 rbc.do_tree(root()); | 1093 rbc.do_tree(root()); |
1107 | 1094 |
1108 return rbc.dict_returned_bytes(); | 1095 return rbc.dict_returned_bytes(); |
1109 } | 1096 } |
1110 | 1097 |
1111 // Count the number of entries in the tree. | 1098 // Count the number of entries in the tree. |
1112 template <class Chunk_t, template <class> class FreeList_t> | 1099 template <class Chunk_t, class FreeList_t> |
1113 class treeCountClosure : public DescendTreeCensusClosure<Chunk_t, FreeList_t> { | 1100 class treeCountClosure : public DescendTreeCensusClosure<Chunk_t, FreeList_t> { |
1114 public: | 1101 public: |
1115 uint count; | 1102 uint count; |
1116 treeCountClosure(uint c) { count = c; } | 1103 treeCountClosure(uint c) { count = c; } |
1117 void do_list(FreeList_t<Chunk_t>* fl) { | 1104 void do_list(FreeList_t* fl) { |
1118 count++; | 1105 count++; |
1119 } | 1106 } |
1120 }; | 1107 }; |
1121 | 1108 |
1122 template <class Chunk_t, template <class> class FreeList_t> | 1109 template <class Chunk_t, class FreeList_t> |
1123 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_count() { | 1110 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_count() { |
1124 treeCountClosure<Chunk_t, FreeList_t> ctc(0); | 1111 treeCountClosure<Chunk_t, FreeList_t> ctc(0); |
1125 ctc.do_tree(root()); | 1112 ctc.do_tree(root()); |
1126 return ctc.count; | 1113 return ctc.count; |
1127 } | 1114 } |
1128 #endif // PRODUCT | 1115 #endif // PRODUCT |
1129 | 1116 |
1130 // Calculate surpluses for the lists in the tree. | 1117 // Calculate surpluses for the lists in the tree. |
1131 template <class Chunk_t, template <class> class FreeList_t> | 1118 template <class Chunk_t, class FreeList_t> |
1132 class setTreeSurplusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { | 1119 class setTreeSurplusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { |
1133 double percentage; | 1120 double percentage; |
1134 public: | 1121 public: |
1135 setTreeSurplusClosure(double v) { percentage = v; } | 1122 setTreeSurplusClosure(double v) { percentage = v; } |
1136 void do_list(FreeList<Chunk_t>* fl) {} | 1123 void do_list(FreeList<Chunk_t>* fl) {} |
1142 (ssize_t)((double)fl->desired() * splitSurplusPercent)); | 1129 (ssize_t)((double)fl->desired() * splitSurplusPercent)); |
1143 } | 1130 } |
1144 #endif // INCLUDE_ALL_GCS | 1131 #endif // INCLUDE_ALL_GCS |
1145 }; | 1132 }; |
1146 | 1133 |
1147 template <class Chunk_t, template <class> class FreeList_t> | 1134 template <class Chunk_t, class FreeList_t> |
1148 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_surplus(double splitSurplusPercent) { | 1135 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_surplus(double splitSurplusPercent) { |
1149 setTreeSurplusClosure<Chunk_t, FreeList_t> sts(splitSurplusPercent); | 1136 setTreeSurplusClosure<Chunk_t, FreeList_t> sts(splitSurplusPercent); |
1150 sts.do_tree(root()); | 1137 sts.do_tree(root()); |
1151 } | 1138 } |
1152 | 1139 |
1153 // Set hints for the lists in the tree. | 1140 // Set hints for the lists in the tree. |
1154 template <class Chunk_t, template <class> class FreeList_t> | 1141 template <class Chunk_t, class FreeList_t> |
1155 class setTreeHintsClosure : public DescendTreeCensusClosure<Chunk_t, FreeList_t> { | 1142 class setTreeHintsClosure : public DescendTreeCensusClosure<Chunk_t, FreeList_t> { |
1156 size_t hint; | 1143 size_t hint; |
1157 public: | 1144 public: |
1158 setTreeHintsClosure(size_t v) { hint = v; } | 1145 setTreeHintsClosure(size_t v) { hint = v; } |
1159 void do_list(FreeList<Chunk_t>* fl) {} | 1146 void do_list(FreeList<Chunk_t>* fl) {} |
1168 } | 1155 } |
1169 } | 1156 } |
1170 #endif // INCLUDE_ALL_GCS | 1157 #endif // INCLUDE_ALL_GCS |
1171 }; | 1158 }; |
1172 | 1159 |
1173 template <class Chunk_t, template <class> class FreeList_t> | 1160 template <class Chunk_t, class FreeList_t> |
1174 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_hints(void) { | 1161 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_hints(void) { |
1175 setTreeHintsClosure<Chunk_t, FreeList_t> sth(0); | 1162 setTreeHintsClosure<Chunk_t, FreeList_t> sth(0); |
1176 sth.do_tree(root()); | 1163 sth.do_tree(root()); |
1177 } | 1164 } |
1178 | 1165 |
1179 // Save count before previous sweep and splits and coalesces. | 1166 // Save count before previous sweep and splits and coalesces. |
1180 template <class Chunk_t, template <class> class FreeList_t> | 1167 template <class Chunk_t, class FreeList_t> |
1181 class clearTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { | 1168 class clearTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { |
1182 void do_list(FreeList<Chunk_t>* fl) {} | 1169 void do_list(FreeList<Chunk_t>* fl) {} |
1183 | 1170 |
1184 #if INCLUDE_ALL_GCS | 1171 #if INCLUDE_ALL_GCS |
1185 void do_list(AdaptiveFreeList<Chunk_t>* fl) { | 1172 void do_list(AdaptiveFreeList<Chunk_t>* fl) { |
1190 fl->set_split_deaths(0); | 1177 fl->set_split_deaths(0); |
1191 } | 1178 } |
1192 #endif // INCLUDE_ALL_GCS | 1179 #endif // INCLUDE_ALL_GCS |
1193 }; | 1180 }; |
1194 | 1181 |
1195 template <class Chunk_t, template <class> class FreeList_t> | 1182 template <class Chunk_t, class FreeList_t> |
1196 void BinaryTreeDictionary<Chunk_t, FreeList_t>::clear_tree_census(void) { | 1183 void BinaryTreeDictionary<Chunk_t, FreeList_t>::clear_tree_census(void) { |
1197 clearTreeCensusClosure<Chunk_t, FreeList_t> ctc; | 1184 clearTreeCensusClosure<Chunk_t, FreeList_t> ctc; |
1198 ctc.do_tree(root()); | 1185 ctc.do_tree(root()); |
1199 } | 1186 } |
1200 | 1187 |
1201 // Do reporting and post sweep clean up. | 1188 // Do reporting and post sweep clean up. |
1202 template <class Chunk_t, template <class> class FreeList_t> | 1189 template <class Chunk_t, class FreeList_t> |
1203 void BinaryTreeDictionary<Chunk_t, FreeList_t>::end_sweep_dict_census(double splitSurplusPercent) { | 1190 void BinaryTreeDictionary<Chunk_t, FreeList_t>::end_sweep_dict_census(double splitSurplusPercent) { |
1204 // Does walking the tree 3 times hurt? | 1191 // Does walking the tree 3 times hurt? |
1205 set_tree_surplus(splitSurplusPercent); | 1192 set_tree_surplus(splitSurplusPercent); |
1206 set_tree_hints(); | 1193 set_tree_hints(); |
1207 if (PrintGC && Verbose) { | 1194 if (PrintGC && Verbose) { |
1209 } | 1196 } |
1210 clear_tree_census(); | 1197 clear_tree_census(); |
1211 } | 1198 } |
1212 | 1199 |
1213 // Print summary statistics | 1200 // Print summary statistics |
1214 template <class Chunk_t, template <class> class FreeList_t> | 1201 template <class Chunk_t, class FreeList_t> |
1215 void BinaryTreeDictionary<Chunk_t, FreeList_t>::report_statistics() const { | 1202 void BinaryTreeDictionary<Chunk_t, FreeList_t>::report_statistics() const { |
1216 FreeBlockDictionary<Chunk_t>::verify_par_locked(); | 1203 FreeBlockDictionary<Chunk_t>::verify_par_locked(); |
1217 gclog_or_tty->print("Statistics for BinaryTreeDictionary:\n" | 1204 gclog_or_tty->print("Statistics for BinaryTreeDictionary:\n" |
1218 "------------------------------------\n"); | 1205 "------------------------------------\n"); |
1219 size_t total_size = total_chunk_size(debug_only(NULL)); | 1206 size_t total_size = total_chunk_size(debug_only(NULL)); |
1228 } | 1215 } |
1229 | 1216 |
1230 // Print census information - counts, births, deaths, etc. | 1217 // Print census information - counts, births, deaths, etc. |
1231 // for each list in the tree. Also print some summary | 1218 // for each list in the tree. Also print some summary |
1232 // information. | 1219 // information. |
1233 template <class Chunk_t, template <class> class FreeList_t> | 1220 template <class Chunk_t, class FreeList_t> |
1234 class PrintTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { | 1221 class PrintTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { |
1235 int _print_line; | 1222 int _print_line; |
1236 size_t _total_free; | 1223 size_t _total_free; |
1237 FreeList_t<Chunk_t> _total; | 1224 FreeList_t _total; |
1238 | 1225 |
1239 public: | 1226 public: |
1240 PrintTreeCensusClosure() { | 1227 PrintTreeCensusClosure() { |
1241 _print_line = 0; | 1228 _print_line = 0; |
1242 _total_free = 0; | 1229 _total_free = 0; |
1243 } | 1230 } |
1244 FreeList_t<Chunk_t>* total() { return &_total; } | 1231 FreeList_t* total() { return &_total; } |
1245 size_t total_free() { return _total_free; } | 1232 size_t total_free() { return _total_free; } |
1246 void do_list(FreeList<Chunk_t>* fl) { | 1233 void do_list(FreeList<Chunk_t>* fl) { |
1247 if (++_print_line >= 40) { | 1234 if (++_print_line >= 40) { |
1248 FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, "size"); | 1235 FreeList_t::print_labels_on(gclog_or_tty, "size"); |
1249 _print_line = 0; | 1236 _print_line = 0; |
1250 } | 1237 } |
1251 fl->print_on(gclog_or_tty); | 1238 fl->print_on(gclog_or_tty); |
1252 _total_free += fl->count() * fl->size() ; | 1239 _total_free += fl->count() * fl->size() ; |
1253 total()->set_count( total()->count() + fl->count() ); | 1240 total()->set_count( total()->count() + fl->count() ); |
1254 } | 1241 } |
1255 | 1242 |
1256 #if INCLUDE_ALL_GCS | 1243 #if INCLUDE_ALL_GCS |
1257 void do_list(AdaptiveFreeList<Chunk_t>* fl) { | 1244 void do_list(AdaptiveFreeList<Chunk_t>* fl) { |
1258 if (++_print_line >= 40) { | 1245 if (++_print_line >= 40) { |
1259 FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, "size"); | 1246 FreeList_t::print_labels_on(gclog_or_tty, "size"); |
1260 _print_line = 0; | 1247 _print_line = 0; |
1261 } | 1248 } |
1262 fl->print_on(gclog_or_tty); | 1249 fl->print_on(gclog_or_tty); |
1263 _total_free += fl->count() * fl->size() ; | 1250 _total_free += fl->count() * fl->size() ; |
1264 total()->set_count( total()->count() + fl->count() ); | 1251 total()->set_count( total()->count() + fl->count() ); |
1273 total()->set_split_deaths(total()->split_deaths() + fl->split_deaths()); | 1260 total()->set_split_deaths(total()->split_deaths() + fl->split_deaths()); |
1274 } | 1261 } |
1275 #endif // INCLUDE_ALL_GCS | 1262 #endif // INCLUDE_ALL_GCS |
1276 }; | 1263 }; |
1277 | 1264 |
1278 template <class Chunk_t, template <class> class FreeList_t> | 1265 template <class Chunk_t, class FreeList_t> |
1279 void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_dict_census(void) const { | 1266 void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_dict_census(void) const { |
1280 | 1267 |
1281 gclog_or_tty->print("\nBinaryTree\n"); | 1268 gclog_or_tty->print("\nBinaryTree\n"); |
1282 FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, "size"); | 1269 FreeList_t::print_labels_on(gclog_or_tty, "size"); |
1283 PrintTreeCensusClosure<Chunk_t, FreeList_t> ptc; | 1270 PrintTreeCensusClosure<Chunk_t, FreeList_t> ptc; |
1284 ptc.do_tree(root()); | 1271 ptc.do_tree(root()); |
1285 | 1272 |
1286 FreeList_t<Chunk_t>* total = ptc.total(); | 1273 FreeList_t* total = ptc.total(); |
1287 FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, " "); | 1274 FreeList_t::print_labels_on(gclog_or_tty, " "); |
1288 } | 1275 } |
1289 | 1276 |
1290 #if INCLUDE_ALL_GCS | 1277 #if INCLUDE_ALL_GCS |
1291 template <> | 1278 template <> |
1292 void AFLBinaryTreeDictionary::print_dict_census(void) const { | 1279 void AFLBinaryTreeDictionary::print_dict_census(void) const { |
1293 | 1280 |
1294 gclog_or_tty->print("\nBinaryTree\n"); | 1281 gclog_or_tty->print("\nBinaryTree\n"); |
1295 AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, "size"); | 1282 AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, "size"); |
1296 PrintTreeCensusClosure<FreeChunk, AdaptiveFreeList> ptc; | 1283 PrintTreeCensusClosure<FreeChunk, AdaptiveFreeList<FreeChunk> > ptc; |
1297 ptc.do_tree(root()); | 1284 ptc.do_tree(root()); |
1298 | 1285 |
1299 AdaptiveFreeList<FreeChunk>* total = ptc.total(); | 1286 AdaptiveFreeList<FreeChunk>* total = ptc.total(); |
1300 AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, " "); | 1287 AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, " "); |
1301 total->print_on(gclog_or_tty, "TOTAL\t"); | 1288 total->print_on(gclog_or_tty, "TOTAL\t"); |
1309 (double)(total->desired() - total->count()) | 1296 (double)(total->desired() - total->count()) |
1310 /(total->desired() != 0 ? (double)total->desired() : 1.0)); | 1297 /(total->desired() != 0 ? (double)total->desired() : 1.0)); |
1311 } | 1298 } |
1312 #endif // INCLUDE_ALL_GCS | 1299 #endif // INCLUDE_ALL_GCS |
1313 | 1300 |
1314 template <class Chunk_t, template <class> class FreeList_t> | 1301 template <class Chunk_t, class FreeList_t> |
1315 class PrintFreeListsClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { | 1302 class PrintFreeListsClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { |
1316 outputStream* _st; | 1303 outputStream* _st; |
1317 int _print_line; | 1304 int _print_line; |
1318 | 1305 |
1319 public: | 1306 public: |
1320 PrintFreeListsClosure(outputStream* st) { | 1307 PrintFreeListsClosure(outputStream* st) { |
1321 _st = st; | 1308 _st = st; |
1322 _print_line = 0; | 1309 _print_line = 0; |
1323 } | 1310 } |
1324 void do_list(FreeList_t<Chunk_t>* fl) { | 1311 void do_list(FreeList_t* fl) { |
1325 if (++_print_line >= 40) { | 1312 if (++_print_line >= 40) { |
1326 FreeList_t<Chunk_t>::print_labels_on(_st, "size"); | 1313 FreeList_t::print_labels_on(_st, "size"); |
1327 _print_line = 0; | 1314 _print_line = 0; |
1328 } | 1315 } |
1329 fl->print_on(gclog_or_tty); | 1316 fl->print_on(gclog_or_tty); |
1330 size_t sz = fl->size(); | 1317 size_t sz = fl->size(); |
1331 for (Chunk_t* fc = fl->head(); fc != NULL; | 1318 for (Chunk_t* fc = fl->head(); fc != NULL; |
1335 fc->cantCoalesce() ? "\t CC" : ""); | 1322 fc->cantCoalesce() ? "\t CC" : ""); |
1336 } | 1323 } |
1337 } | 1324 } |
1338 }; | 1325 }; |
1339 | 1326 |
1340 template <class Chunk_t, template <class> class FreeList_t> | 1327 template <class Chunk_t, class FreeList_t> |
1341 void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_free_lists(outputStream* st) const { | 1328 void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_free_lists(outputStream* st) const { |
1342 | 1329 |
1343 FreeList_t<Chunk_t>::print_labels_on(st, "size"); | 1330 FreeList_t::print_labels_on(st, "size"); |
1344 PrintFreeListsClosure<Chunk_t, FreeList_t> pflc(st); | 1331 PrintFreeListsClosure<Chunk_t, FreeList_t> pflc(st); |
1345 pflc.do_tree(root()); | 1332 pflc.do_tree(root()); |
1346 } | 1333 } |
1347 | 1334 |
1348 // Verify the following tree invariants: | 1335 // Verify the following tree invariants: |
1349 // . _root has no parent | 1336 // . _root has no parent |
1350 // . parent and child point to each other | 1337 // . parent and child point to each other |
1351 // . each node's key correctly related to that of its child(ren) | 1338 // . each node's key correctly related to that of its child(ren) |
1352 template <class Chunk_t, template <class> class FreeList_t> | 1339 template <class Chunk_t, class FreeList_t> |
1353 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_tree() const { | 1340 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_tree() const { |
1354 guarantee(root() == NULL || total_free_blocks() == 0 || | 1341 guarantee(root() == NULL || total_free_blocks() == 0 || |
1355 total_size() != 0, "_total_size should't be 0?"); | 1342 total_size() != 0, "_total_size should't be 0?"); |
1356 guarantee(root() == NULL || root()->parent() == NULL, "_root shouldn't have parent"); | 1343 guarantee(root() == NULL || root()->parent() == NULL, "_root shouldn't have parent"); |
1357 verify_tree_helper(root()); | 1344 verify_tree_helper(root()); |
1358 } | 1345 } |
1359 | 1346 |
1360 template <class Chunk_t, template <class> class FreeList_t> | 1347 template <class Chunk_t, class FreeList_t> |
1361 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_prev_free_ptrs(TreeList<Chunk_t, FreeList_t>* tl) { | 1348 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_prev_free_ptrs(TreeList<Chunk_t, FreeList_t>* tl) { |
1362 size_t ct = 0; | 1349 size_t ct = 0; |
1363 for (Chunk_t* curFC = tl->head(); curFC != NULL; curFC = curFC->next()) { | 1350 for (Chunk_t* curFC = tl->head(); curFC != NULL; curFC = curFC->next()) { |
1364 ct++; | 1351 ct++; |
1365 assert(curFC->prev() == NULL || curFC->prev()->is_free(), | 1352 assert(curFC->prev() == NULL || curFC->prev()->is_free(), |
1369 } | 1356 } |
1370 | 1357 |
1371 // Note: this helper is recursive rather than iterative, so use with | 1358 // Note: this helper is recursive rather than iterative, so use with |
1372 // caution on very deep trees; and watch out for stack overflow errors; | 1359 // caution on very deep trees; and watch out for stack overflow errors; |
1373 // In general, to be used only for debugging. | 1360 // In general, to be used only for debugging. |
1374 template <class Chunk_t, template <class> class FreeList_t> | 1361 template <class Chunk_t, class FreeList_t> |
1375 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_tree_helper(TreeList<Chunk_t, FreeList_t>* tl) const { | 1362 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_tree_helper(TreeList<Chunk_t, FreeList_t>* tl) const { |
1376 if (tl == NULL) | 1363 if (tl == NULL) |
1377 return; | 1364 return; |
1378 guarantee(tl->size() != 0, "A list must has a size"); | 1365 guarantee(tl->size() != 0, "A list must has a size"); |
1379 guarantee(tl->left() == NULL || tl->left()->parent() == tl, | 1366 guarantee(tl->left() == NULL || tl->left()->parent() == tl, |
1398 } | 1385 } |
1399 verify_tree_helper(tl->left()); | 1386 verify_tree_helper(tl->left()); |
1400 verify_tree_helper(tl->right()); | 1387 verify_tree_helper(tl->right()); |
1401 } | 1388 } |
1402 | 1389 |
1403 template <class Chunk_t, template <class> class FreeList_t> | 1390 template <class Chunk_t, class FreeList_t> |
1404 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify() const { | 1391 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify() const { |
1405 verify_tree(); | 1392 verify_tree(); |
1406 guarantee(total_size() == total_size_in_tree(root()), "Total Size inconsistency"); | 1393 guarantee(total_size() == total_size_in_tree(root()), "Total Size inconsistency"); |
1407 } | 1394 } |
1408 | 1395 |
1409 template class TreeList<Metablock, FreeList>; | 1396 template class TreeList<Metablock, FreeList<Metablock> >; |
1410 template class BinaryTreeDictionary<Metablock, FreeList>; | 1397 template class BinaryTreeDictionary<Metablock, FreeList<Metablock> >; |
1411 template class TreeChunk<Metablock, FreeList>; | 1398 template class TreeChunk<Metablock, FreeList<Metablock> >; |
1412 | 1399 |
1413 template class TreeList<Metachunk, FreeList>; | 1400 template class TreeList<Metachunk, FreeList<Metachunk> >; |
1414 template class BinaryTreeDictionary<Metachunk, FreeList>; | 1401 template class BinaryTreeDictionary<Metachunk, FreeList<Metachunk> >; |
1415 template class TreeChunk<Metachunk, FreeList>; | 1402 template class TreeChunk<Metachunk, FreeList<Metachunk> >; |
1416 | 1403 |
1417 | 1404 |
1418 #if INCLUDE_ALL_GCS | 1405 #if INCLUDE_ALL_GCS |
1419 // Explicitly instantiate these types for FreeChunk. | 1406 // Explicitly instantiate these types for FreeChunk. |
1420 template class TreeList<FreeChunk, AdaptiveFreeList>; | 1407 template class TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >; |
1421 template class BinaryTreeDictionary<FreeChunk, AdaptiveFreeList>; | 1408 template class BinaryTreeDictionary<FreeChunk, AdaptiveFreeList<FreeChunk> >; |
1422 template class TreeChunk<FreeChunk, AdaptiveFreeList>; | 1409 template class TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >; |
1423 | 1410 |
1424 #endif // INCLUDE_ALL_GCS | 1411 #endif // INCLUDE_ALL_GCS |