Mercurial > hg > graal-jvmci-8
comparison src/share/vm/memory/binaryTreeDictionary.cpp @ 6028:f69a5d43dc19
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>; |