Mercurial > hg > truffle
annotate src/share/vm/opto/indexSet.cpp @ 1721:413ad0331a0c
6977924: Changes for 6975078 produce build error with certain gcc versions
Summary: The changes introduced for 6975078 assign badHeapOopVal to the _allocation field in the ResourceObj class. In 32 bit linux builds with certain versions of gcc this assignment will be flagged as an error while compiling allocation.cpp. In 32 bit builds the constant value badHeapOopVal (which is cast to an intptr_t) is negative. The _allocation field is typed as an unsigned intptr_t and gcc catches this as an error.
Reviewed-by: jcoomes, ysr, phh
| author | johnc |
|---|---|
| date | Wed, 18 Aug 2010 10:59:06 -0700 |
| parents | c18cbe5936b8 |
| children | f95d63e2154a |
| rev | line source |
|---|---|
| 0 | 1 /* |
|
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
2 * Copyright (c) 1998, 2004, Oracle and/or its affiliates. All rights reserved. |
| 0 | 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| 4 * | |
| 5 * This code is free software; you can redistribute it and/or modify it | |
| 6 * under the terms of the GNU General Public License version 2 only, as | |
| 7 * published by the Free Software Foundation. | |
| 8 * | |
| 9 * This code is distributed in the hope that it will be useful, but WITHOUT | |
| 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 12 * version 2 for more details (a copy is included in the LICENSE file that | |
| 13 * accompanied this code). | |
| 14 * | |
| 15 * You should have received a copy of the GNU General Public License version | |
| 16 * 2 along with this work; if not, write to the Free Software Foundation, | |
| 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. | |
| 18 * | |
|
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
21 * questions. |
| 0 | 22 * |
| 23 */ | |
| 24 | |
| 25 // This file defines the IndexSet class, a set of sparse integer indices. | |
| 26 // This data structure is used by the compiler in its liveness analysis and | |
| 27 // during register allocation. It also defines an iterator for this class. | |
| 28 | |
| 29 #include "incls/_precompiled.incl" | |
| 30 #include "incls/_indexSet.cpp.incl" | |
| 31 | |
| 32 //-------------------------------- Initializations ------------------------------ | |
| 33 | |
| 34 IndexSet::BitBlock IndexSet::_empty_block = IndexSet::BitBlock(); | |
| 35 | |
| 36 #ifdef ASSERT | |
| 37 // Initialize statistics counters | |
| 38 uint IndexSet::_alloc_new = 0; | |
| 39 uint IndexSet::_alloc_total = 0; | |
| 40 | |
| 41 long IndexSet::_total_bits = 0; | |
| 42 long IndexSet::_total_used_blocks = 0; | |
| 43 long IndexSet::_total_unused_blocks = 0; | |
| 44 | |
| 45 // Per set, or all sets operation tracing | |
| 46 int IndexSet::_serial_count = 1; | |
| 47 #endif | |
| 48 | |
| 49 // What is the first set bit in a 5 bit integer? | |
| 50 const byte IndexSetIterator::_first_bit[32] = { | |
| 51 0, 0, 1, 0, | |
| 52 2, 0, 1, 0, | |
| 53 3, 0, 1, 0, | |
| 54 2, 0, 1, 0, | |
| 55 4, 0, 1, 0, | |
| 56 2, 0, 1, 0, | |
| 57 3, 0, 1, 0, | |
| 58 2, 0, 1, 0 | |
| 59 }; | |
| 60 | |
| 61 // What is the second set bit in a 5 bit integer? | |
| 62 const byte IndexSetIterator::_second_bit[32] = { | |
| 63 5, 5, 5, 1, | |
| 64 5, 2, 2, 1, | |
| 65 5, 3, 3, 1, | |
| 66 3, 2, 2, 1, | |
| 67 5, 4, 4, 1, | |
| 68 4, 2, 2, 1, | |
| 69 4, 3, 3, 1, | |
| 70 3, 2, 2, 1 | |
| 71 }; | |
| 72 | |
| 73 // I tried implementing the IndexSetIterator with a window_size of 8 and | |
| 74 // didn't seem to get a noticeable speedup. I am leaving in the tables | |
| 75 // in case we want to switch back. | |
| 76 | |
| 77 /*const byte IndexSetIterator::_first_bit[256] = { | |
| 78 8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 79 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 80 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 81 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 82 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 83 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 84 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 85 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 86 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 87 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 88 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 89 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 90 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 91 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 92 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, | |
| 93 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 | |
| 94 }; | |
| 95 | |
| 96 const byte IndexSetIterator::_second_bit[256] = { | |
| 97 8, 8, 8, 1, 8, 2, 2, 1, 8, 3, 3, 1, 3, 2, 2, 1, | |
| 98 8, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, | |
| 99 8, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, | |
| 100 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, | |
| 101 8, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1, | |
| 102 6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, | |
| 103 6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, | |
| 104 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, | |
| 105 8, 7, 7, 1, 7, 2, 2, 1, 7, 3, 3, 1, 3, 2, 2, 1, | |
| 106 7, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, | |
| 107 7, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, | |
| 108 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, | |
| 109 7, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1, | |
| 110 6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, | |
| 111 6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, | |
| 112 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1 | |
| 113 };*/ | |
| 114 | |
| 115 //---------------------------- IndexSet::populate_free_list() ----------------------------- | |
| 116 // Populate the free BitBlock list with a batch of BitBlocks. The BitBlocks | |
| 117 // are 32 bit aligned. | |
| 118 | |
| 119 void IndexSet::populate_free_list() { | |
| 120 Compile *compile = Compile::current(); | |
| 121 BitBlock *free = (BitBlock*)compile->indexSet_free_block_list(); | |
| 122 | |
| 123 char *mem = (char*)arena()->Amalloc_4(sizeof(BitBlock) * | |
| 124 bitblock_alloc_chunk_size + 32); | |
| 125 | |
| 126 // Align the pointer to a 32 bit boundary. | |
| 127 BitBlock *new_blocks = (BitBlock*)(((uintptr_t)mem + 32) & ~0x001F); | |
| 128 | |
| 129 // Add the new blocks to the free list. | |
| 130 for (int i = 0; i < bitblock_alloc_chunk_size; i++) { | |
| 131 new_blocks->set_next(free); | |
| 132 free = new_blocks; | |
| 133 new_blocks++; | |
| 134 } | |
| 135 | |
| 136 compile->set_indexSet_free_block_list(free); | |
| 137 | |
| 138 #ifdef ASSERT | |
| 139 if (CollectIndexSetStatistics) { | |
| 140 _alloc_new += bitblock_alloc_chunk_size; | |
| 141 } | |
| 142 #endif | |
| 143 } | |
| 144 | |
| 145 | |
| 146 //---------------------------- IndexSet::alloc_block() ------------------------ | |
| 147 // Allocate a BitBlock from the free list. If the free list is empty, | |
| 148 // prime it. | |
| 149 | |
| 150 IndexSet::BitBlock *IndexSet::alloc_block() { | |
| 151 #ifdef ASSERT | |
| 152 if (CollectIndexSetStatistics) { | |
| 153 _alloc_total++; | |
| 154 } | |
| 155 #endif | |
| 156 Compile *compile = Compile::current(); | |
| 157 BitBlock* free_list = (BitBlock*)compile->indexSet_free_block_list(); | |
| 158 if (free_list == NULL) { | |
| 159 populate_free_list(); | |
| 160 free_list = (BitBlock*)compile->indexSet_free_block_list(); | |
| 161 } | |
| 162 BitBlock *block = free_list; | |
| 163 compile->set_indexSet_free_block_list(block->next()); | |
| 164 | |
| 165 block->clear(); | |
| 166 return block; | |
| 167 } | |
| 168 | |
| 169 //---------------------------- IndexSet::alloc_block_containing() ------------- | |
| 170 // Allocate a new BitBlock and put it into the position in the _blocks array | |
| 171 // corresponding to element. | |
| 172 | |
| 173 IndexSet::BitBlock *IndexSet::alloc_block_containing(uint element) { | |
| 174 BitBlock *block = alloc_block(); | |
| 175 uint bi = get_block_index(element); | |
| 176 _blocks[bi] = block; | |
| 177 return block; | |
| 178 } | |
| 179 | |
| 180 //---------------------------- IndexSet::free_block() ------------------------- | |
| 181 // Add a BitBlock to the free list. | |
| 182 | |
| 183 void IndexSet::free_block(uint i) { | |
| 184 debug_only(check_watch("free block", i)); | |
| 185 assert(i < _max_blocks, "block index too large"); | |
| 186 BitBlock *block = _blocks[i]; | |
| 187 assert(block != &_empty_block, "cannot free the empty block"); | |
| 188 block->set_next((IndexSet::BitBlock*)Compile::current()->indexSet_free_block_list()); | |
| 189 Compile::current()->set_indexSet_free_block_list(block); | |
| 190 set_block(i,&_empty_block); | |
| 191 } | |
| 192 | |
| 193 //------------------------------lrg_union-------------------------------------- | |
| 194 // Compute the union of all elements of one and two which interfere with | |
| 195 // the RegMask mask. If the degree of the union becomes exceeds | |
| 196 // fail_degree, the union bails out. The underlying set is cleared before | |
| 197 // the union is performed. | |
| 198 | |
| 199 uint IndexSet::lrg_union(uint lr1, uint lr2, | |
| 200 const uint fail_degree, | |
| 201 const PhaseIFG *ifg, | |
| 202 const RegMask &mask ) { | |
| 203 IndexSet *one = ifg->neighbors(lr1); | |
| 204 IndexSet *two = ifg->neighbors(lr2); | |
| 205 LRG &lrg1 = ifg->lrgs(lr1); | |
| 206 LRG &lrg2 = ifg->lrgs(lr2); | |
| 207 #ifdef ASSERT | |
| 208 assert(_max_elements == one->_max_elements, "max element mismatch"); | |
| 209 check_watch("union destination"); | |
| 210 one->check_watch("union source"); | |
| 211 two->check_watch("union source"); | |
| 212 #endif | |
| 213 | |
| 214 // Compute the degree of the combined live-range. The combined | |
| 215 // live-range has the union of the original live-ranges' neighbors set as | |
| 216 // well as the neighbors of all intermediate copies, minus those neighbors | |
| 217 // that can not use the intersected allowed-register-set. | |
| 218 | |
| 219 // Copy the larger set. Insert the smaller set into the larger. | |
| 220 if (two->count() > one->count()) { | |
| 221 IndexSet *temp = one; | |
| 222 one = two; | |
| 223 two = temp; | |
| 224 } | |
| 225 | |
| 226 clear(); | |
| 227 | |
| 228 // Used to compute degree of register-only interferences. Infinite-stack | |
| 229 // neighbors do not alter colorability, as they can always color to some | |
| 230 // other color. (A variant of the Briggs assertion) | |
| 231 uint reg_degree = 0; | |
| 232 | |
| 233 uint element; | |
| 234 // Load up the combined interference set with the neighbors of one | |
| 235 IndexSetIterator elements(one); | |
| 236 while ((element = elements.next()) != 0) { | |
| 237 LRG &lrg = ifg->lrgs(element); | |
| 238 if (mask.overlap(lrg.mask())) { | |
| 239 insert(element); | |
| 240 if( !lrg.mask().is_AllStack() ) { | |
| 241 reg_degree += lrg1.compute_degree(lrg); | |
| 242 if( reg_degree >= fail_degree ) return reg_degree; | |
| 243 } else { | |
| 244 // !!!!! Danger! No update to reg_degree despite having a neighbor. | |
| 245 // A variant of the Briggs assertion. | |
| 246 // Not needed if I simplify during coalesce, ala George/Appel. | |
| 247 assert( lrg.lo_degree(), "" ); | |
| 248 } | |
| 249 } | |
| 250 } | |
| 251 // Add neighbors of two as well | |
| 252 IndexSetIterator elements2(two); | |
| 253 while ((element = elements2.next()) != 0) { | |
| 254 LRG &lrg = ifg->lrgs(element); | |
| 255 if (mask.overlap(lrg.mask())) { | |
| 256 if (insert(element)) { | |
| 257 if( !lrg.mask().is_AllStack() ) { | |
| 258 reg_degree += lrg2.compute_degree(lrg); | |
| 259 if( reg_degree >= fail_degree ) return reg_degree; | |
| 260 } else { | |
| 261 // !!!!! Danger! No update to reg_degree despite having a neighbor. | |
| 262 // A variant of the Briggs assertion. | |
| 263 // Not needed if I simplify during coalesce, ala George/Appel. | |
| 264 assert( lrg.lo_degree(), "" ); | |
| 265 } | |
| 266 } | |
| 267 } | |
| 268 } | |
| 269 | |
| 270 return reg_degree; | |
| 271 } | |
| 272 | |
| 273 //---------------------------- IndexSet() ----------------------------- | |
| 274 // A deep copy constructor. This is used when you need a scratch copy of this set. | |
| 275 | |
| 276 IndexSet::IndexSet (IndexSet *set) { | |
| 277 #ifdef ASSERT | |
| 278 _serial_number = _serial_count++; | |
| 279 set->check_watch("copied", _serial_number); | |
| 280 check_watch("initialized by copy", set->_serial_number); | |
| 281 _max_elements = set->_max_elements; | |
| 282 #endif | |
| 283 _count = set->_count; | |
| 284 _max_blocks = set->_max_blocks; | |
| 285 if (_max_blocks <= preallocated_block_list_size) { | |
| 286 _blocks = _preallocated_block_list; | |
| 287 } else { | |
| 288 _blocks = | |
| 289 (IndexSet::BitBlock**) arena()->Amalloc_4(sizeof(IndexSet::BitBlock**) * _max_blocks); | |
| 290 } | |
| 291 for (uint i = 0; i < _max_blocks; i++) { | |
| 292 BitBlock *block = set->_blocks[i]; | |
| 293 if (block == &_empty_block) { | |
| 294 set_block(i, &_empty_block); | |
| 295 } else { | |
| 296 BitBlock *new_block = alloc_block(); | |
| 297 memcpy(new_block->words(), block->words(), sizeof(uint32) * words_per_block); | |
| 298 set_block(i, new_block); | |
| 299 } | |
| 300 } | |
| 301 } | |
| 302 | |
| 303 //---------------------------- IndexSet::initialize() ----------------------------- | |
| 304 // Prepare an IndexSet for use. | |
| 305 | |
| 306 void IndexSet::initialize(uint max_elements) { | |
| 307 #ifdef ASSERT | |
| 308 _serial_number = _serial_count++; | |
| 309 check_watch("initialized", max_elements); | |
| 310 _max_elements = max_elements; | |
| 311 #endif | |
| 312 _count = 0; | |
| 313 _max_blocks = (max_elements + bits_per_block - 1) / bits_per_block; | |
| 314 | |
| 315 if (_max_blocks <= preallocated_block_list_size) { | |
| 316 _blocks = _preallocated_block_list; | |
| 317 } else { | |
| 318 _blocks = (IndexSet::BitBlock**) arena()->Amalloc_4(sizeof(IndexSet::BitBlock**) * _max_blocks); | |
| 319 } | |
| 320 for (uint i = 0; i < _max_blocks; i++) { | |
| 321 set_block(i, &_empty_block); | |
| 322 } | |
| 323 } | |
| 324 | |
| 325 //---------------------------- IndexSet::initialize()------------------------------ | |
| 326 // Prepare an IndexSet for use. If it needs to allocate its _blocks array, it does | |
| 327 // so from the Arena passed as a parameter. BitBlock allocation is still done from | |
| 328 // the static Arena which was set with reset_memory(). | |
| 329 | |
| 330 void IndexSet::initialize(uint max_elements, Arena *arena) { | |
| 331 #ifdef ASSERT | |
| 332 _serial_number = _serial_count++; | |
| 333 check_watch("initialized2", max_elements); | |
| 334 _max_elements = max_elements; | |
| 335 #endif // ASSERT | |
| 336 _count = 0; | |
| 337 _max_blocks = (max_elements + bits_per_block - 1) / bits_per_block; | |
| 338 | |
| 339 if (_max_blocks <= preallocated_block_list_size) { | |
| 340 _blocks = _preallocated_block_list; | |
| 341 } else { | |
| 342 _blocks = (IndexSet::BitBlock**) arena->Amalloc_4(sizeof(IndexSet::BitBlock**) * _max_blocks); | |
| 343 } | |
| 344 for (uint i = 0; i < _max_blocks; i++) { | |
| 345 set_block(i, &_empty_block); | |
| 346 } | |
| 347 } | |
| 348 | |
| 349 //---------------------------- IndexSet::swap() ----------------------------- | |
| 350 // Exchange two IndexSets. | |
| 351 | |
| 352 void IndexSet::swap(IndexSet *set) { | |
| 353 #ifdef ASSERT | |
| 354 assert(_max_elements == set->_max_elements, "must have same universe size to swap"); | |
| 355 check_watch("swap", set->_serial_number); | |
| 356 set->check_watch("swap", _serial_number); | |
| 357 #endif | |
| 358 | |
| 359 for (uint i = 0; i < _max_blocks; i++) { | |
| 360 BitBlock *temp = _blocks[i]; | |
| 361 set_block(i, set->_blocks[i]); | |
| 362 set->set_block(i, temp); | |
| 363 } | |
| 364 uint temp = _count; | |
| 365 _count = set->_count; | |
| 366 set->_count = temp; | |
| 367 } | |
| 368 | |
| 369 //---------------------------- IndexSet::dump() ----------------------------- | |
| 370 // Print this set. Used for debugging. | |
| 371 | |
| 372 #ifndef PRODUCT | |
| 373 void IndexSet::dump() const { | |
| 374 IndexSetIterator elements(this); | |
| 375 | |
| 376 tty->print("{"); | |
| 377 uint i; | |
| 378 while ((i = elements.next()) != 0) { | |
| 379 tty->print("L%d ", i); | |
| 380 } | |
| 381 tty->print_cr("}"); | |
| 382 } | |
| 383 #endif | |
| 384 | |
| 385 #ifdef ASSERT | |
| 386 //---------------------------- IndexSet::tally_iteration_statistics() ----------------------------- | |
| 387 // Update block/bit counts to reflect that this set has been iterated over. | |
| 388 | |
| 389 void IndexSet::tally_iteration_statistics() const { | |
| 390 _total_bits += count(); | |
| 391 | |
| 392 for (uint i = 0; i < _max_blocks; i++) { | |
| 393 if (_blocks[i] != &_empty_block) { | |
| 394 _total_used_blocks++; | |
| 395 } else { | |
| 396 _total_unused_blocks++; | |
| 397 } | |
| 398 } | |
| 399 } | |
| 400 | |
| 401 //---------------------------- IndexSet::print_statistics() ----------------------------- | |
| 402 // Print statistics about IndexSet usage. | |
| 403 | |
| 404 void IndexSet::print_statistics() { | |
| 405 long total_blocks = _total_used_blocks + _total_unused_blocks; | |
| 406 tty->print_cr ("Accumulated IndexSet usage statistics:"); | |
| 407 tty->print_cr ("--------------------------------------"); | |
| 408 tty->print_cr (" Iteration:"); | |
| 409 tty->print_cr (" blocks visited: %d", total_blocks); | |
| 410 tty->print_cr (" blocks empty: %4.2f%%", 100.0*_total_unused_blocks/total_blocks); | |
| 411 tty->print_cr (" bit density (bits/used blocks): %4.2f%%", (double)_total_bits/_total_used_blocks); | |
| 412 tty->print_cr (" bit density (bits/all blocks): %4.2f%%", (double)_total_bits/total_blocks); | |
| 413 tty->print_cr (" Allocation:"); | |
| 414 tty->print_cr (" blocks allocated: %d", _alloc_new); | |
| 415 tty->print_cr (" blocks used/reused: %d", _alloc_total); | |
| 416 } | |
| 417 | |
| 418 //---------------------------- IndexSet::verify() ----------------------------- | |
| 419 // Expensive test of IndexSet sanity. Ensure that the count agrees with the | |
| 420 // number of bits in the blocks. Make sure the iterator is seeing all elements | |
| 421 // of the set. Meant for use during development. | |
| 422 | |
| 423 void IndexSet::verify() const { | |
| 424 assert(!member(0), "zero cannot be a member"); | |
| 425 uint count = 0; | |
| 426 uint i; | |
| 427 for (i = 1; i < _max_elements; i++) { | |
| 428 if (member(i)) { | |
| 429 count++; | |
| 430 assert(count <= _count, "_count is messed up"); | |
| 431 } | |
| 432 } | |
| 433 | |
| 434 IndexSetIterator elements(this); | |
| 435 count = 0; | |
| 436 while ((i = elements.next()) != 0) { | |
| 437 count++; | |
| 438 assert(member(i), "returned a non member"); | |
| 439 assert(count <= _count, "iterator returned wrong number of elements"); | |
| 440 } | |
| 441 } | |
| 442 #endif | |
| 443 | |
| 444 //---------------------------- IndexSetIterator() ----------------------------- | |
| 445 // Create an iterator for a set. If empty blocks are detected when iterating | |
| 446 // over the set, these blocks are replaced. | |
| 447 | |
| 448 IndexSetIterator::IndexSetIterator(IndexSet *set) { | |
| 449 #ifdef ASSERT | |
| 450 if (CollectIndexSetStatistics) { | |
| 451 set->tally_iteration_statistics(); | |
| 452 } | |
| 453 set->check_watch("traversed", set->count()); | |
| 454 #endif | |
| 455 if (set->is_empty()) { | |
| 456 _current = 0; | |
| 457 _next_word = IndexSet::words_per_block; | |
| 458 _next_block = 1; | |
| 459 _max_blocks = 1; | |
| 460 | |
| 461 // We don't need the following values when we iterate over an empty set. | |
| 462 // The commented out code is left here to document that the omission | |
| 463 // is intentional. | |
| 464 // | |
| 465 //_value = 0; | |
| 466 //_words = NULL; | |
| 467 //_blocks = NULL; | |
| 468 //_set = NULL; | |
| 469 } else { | |
| 470 _current = 0; | |
| 471 _value = 0; | |
| 472 _next_block = 0; | |
| 473 _next_word = IndexSet::words_per_block; | |
| 474 | |
| 475 _max_blocks = set->_max_blocks; | |
| 476 _words = NULL; | |
| 477 _blocks = set->_blocks; | |
| 478 _set = set; | |
| 479 } | |
| 480 } | |
| 481 | |
| 482 //---------------------------- IndexSetIterator(const) ----------------------------- | |
| 483 // Iterate over a constant IndexSet. | |
| 484 | |
| 485 IndexSetIterator::IndexSetIterator(const IndexSet *set) { | |
| 486 #ifdef ASSERT | |
| 487 if (CollectIndexSetStatistics) { | |
| 488 set->tally_iteration_statistics(); | |
| 489 } | |
| 490 // We don't call check_watch from here to avoid bad recursion. | |
| 491 // set->check_watch("traversed const", set->count()); | |
| 492 #endif | |
| 493 if (set->is_empty()) { | |
| 494 _current = 0; | |
| 495 _next_word = IndexSet::words_per_block; | |
| 496 _next_block = 1; | |
| 497 _max_blocks = 1; | |
| 498 | |
| 499 // We don't need the following values when we iterate over an empty set. | |
| 500 // The commented out code is left here to document that the omission | |
| 501 // is intentional. | |
| 502 // | |
| 503 //_value = 0; | |
| 504 //_words = NULL; | |
| 505 //_blocks = NULL; | |
| 506 //_set = NULL; | |
| 507 } else { | |
| 508 _current = 0; | |
| 509 _value = 0; | |
| 510 _next_block = 0; | |
| 511 _next_word = IndexSet::words_per_block; | |
| 512 | |
| 513 _max_blocks = set->_max_blocks; | |
| 514 _words = NULL; | |
| 515 _blocks = set->_blocks; | |
| 516 _set = NULL; | |
| 517 } | |
| 518 } | |
| 519 | |
| 520 //---------------------------- List16Iterator::advance_and_next() ----------------------------- | |
| 521 // Advance to the next non-empty word in the set being iterated over. Return the next element | |
| 522 // if there is one. If we are done, return 0. This method is called from the next() method | |
| 523 // when it gets done with a word. | |
| 524 | |
| 525 uint IndexSetIterator::advance_and_next() { | |
| 526 // See if there is another non-empty word in the current block. | |
| 527 for (uint wi = _next_word; wi < (unsigned)IndexSet::words_per_block; wi++) { | |
| 528 if (_words[wi] != 0) { | |
| 529 // Found a non-empty word. | |
| 530 _value = ((_next_block - 1) * IndexSet::bits_per_block) + (wi * IndexSet::bits_per_word); | |
| 531 _current = _words[wi]; | |
| 532 | |
| 533 _next_word = wi+1; | |
| 534 | |
| 535 return next(); | |
| 536 } | |
| 537 } | |
| 538 | |
| 539 // We ran out of words in the current block. Advance to next non-empty block. | |
| 540 for (uint bi = _next_block; bi < _max_blocks; bi++) { | |
| 541 if (_blocks[bi] != &IndexSet::_empty_block) { | |
| 542 // Found a non-empty block. | |
| 543 | |
| 544 _words = _blocks[bi]->words(); | |
| 545 for (uint wi = 0; wi < (unsigned)IndexSet::words_per_block; wi++) { | |
| 546 if (_words[wi] != 0) { | |
| 547 // Found a non-empty word. | |
| 548 _value = (bi * IndexSet::bits_per_block) + (wi * IndexSet::bits_per_word); | |
| 549 _current = _words[wi]; | |
| 550 | |
| 551 _next_block = bi+1; | |
| 552 _next_word = wi+1; | |
| 553 | |
| 554 return next(); | |
| 555 } | |
| 556 } | |
| 557 | |
| 558 // All of the words in the block were empty. Replace | |
| 559 // the block with the empty block. | |
| 560 if (_set) { | |
| 561 _set->free_block(bi); | |
| 562 } | |
| 563 } | |
| 564 } | |
| 565 | |
| 566 // These assignments make redundant calls to next on a finished iterator | |
| 567 // faster. Probably not necessary. | |
| 568 _next_block = _max_blocks; | |
| 569 _next_word = IndexSet::words_per_block; | |
| 570 | |
| 571 // No more words. | |
| 572 return 0; | |
| 573 } |