1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/opto/indexSet.cpp Wed Apr 27 01:25:04 2016 +0800
1.3 @@ -0,0 +1,577 @@
1.4 +/*
1.5 + * Copyright (c) 1998, 2011, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation.
1.11 + *
1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.15 + * version 2 for more details (a copy is included in the LICENSE file that
1.16 + * accompanied this code).
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License version
1.19 + * 2 along with this work; if not, write to the Free Software Foundation,
1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 + *
1.22 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.23 + * or visit www.oracle.com if you need additional information or have any
1.24 + * questions.
1.25 + *
1.26 + */
1.27 +
1.28 +#include "precompiled.hpp"
1.29 +#include "memory/allocation.inline.hpp"
1.30 +#include "opto/chaitin.hpp"
1.31 +#include "opto/compile.hpp"
1.32 +#include "opto/indexSet.hpp"
1.33 +#include "opto/regmask.hpp"
1.34 +
1.35 +// This file defines the IndexSet class, a set of sparse integer indices.
1.36 +// This data structure is used by the compiler in its liveness analysis and
1.37 +// during register allocation. It also defines an iterator for this class.
1.38 +
1.39 +//-------------------------------- Initializations ------------------------------
1.40 +
1.41 +IndexSet::BitBlock IndexSet::_empty_block = IndexSet::BitBlock();
1.42 +
1.43 +#ifdef ASSERT
1.44 +// Initialize statistics counters
1.45 +julong IndexSet::_alloc_new = 0;
1.46 +julong IndexSet::_alloc_total = 0;
1.47 +
1.48 +julong IndexSet::_total_bits = 0;
1.49 +julong IndexSet::_total_used_blocks = 0;
1.50 +julong IndexSet::_total_unused_blocks = 0;
1.51 +
1.52 +// Per set, or all sets operation tracing
1.53 +int IndexSet::_serial_count = 1;
1.54 +#endif
1.55 +
1.56 +// What is the first set bit in a 5 bit integer?
1.57 +const byte IndexSetIterator::_first_bit[32] = {
1.58 + 0, 0, 1, 0,
1.59 + 2, 0, 1, 0,
1.60 + 3, 0, 1, 0,
1.61 + 2, 0, 1, 0,
1.62 + 4, 0, 1, 0,
1.63 + 2, 0, 1, 0,
1.64 + 3, 0, 1, 0,
1.65 + 2, 0, 1, 0
1.66 +};
1.67 +
1.68 +// What is the second set bit in a 5 bit integer?
1.69 +const byte IndexSetIterator::_second_bit[32] = {
1.70 + 5, 5, 5, 1,
1.71 + 5, 2, 2, 1,
1.72 + 5, 3, 3, 1,
1.73 + 3, 2, 2, 1,
1.74 + 5, 4, 4, 1,
1.75 + 4, 2, 2, 1,
1.76 + 4, 3, 3, 1,
1.77 + 3, 2, 2, 1
1.78 +};
1.79 +
1.80 +// I tried implementing the IndexSetIterator with a window_size of 8 and
1.81 +// didn't seem to get a noticeable speedup. I am leaving in the tables
1.82 +// in case we want to switch back.
1.83 +
1.84 +/*const byte IndexSetIterator::_first_bit[256] = {
1.85 + 8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1.86 + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1.87 + 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1.88 + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1.89 + 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1.90 + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1.91 + 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1.92 + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1.93 + 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1.94 + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1.95 + 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1.96 + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1.97 + 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1.98 + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1.99 + 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
1.100 + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
1.101 +};
1.102 +
1.103 +const byte IndexSetIterator::_second_bit[256] = {
1.104 + 8, 8, 8, 1, 8, 2, 2, 1, 8, 3, 3, 1, 3, 2, 2, 1,
1.105 + 8, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
1.106 + 8, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
1.107 + 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
1.108 + 8, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1,
1.109 + 6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
1.110 + 6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
1.111 + 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
1.112 + 8, 7, 7, 1, 7, 2, 2, 1, 7, 3, 3, 1, 3, 2, 2, 1,
1.113 + 7, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
1.114 + 7, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
1.115 + 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
1.116 + 7, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1,
1.117 + 6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
1.118 + 6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
1.119 + 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1
1.120 +};*/
1.121 +
1.122 +//---------------------------- IndexSet::populate_free_list() -----------------------------
1.123 +// Populate the free BitBlock list with a batch of BitBlocks. The BitBlocks
1.124 +// are 32 bit aligned.
1.125 +
1.126 +void IndexSet::populate_free_list() {
1.127 + Compile *compile = Compile::current();
1.128 + BitBlock *free = (BitBlock*)compile->indexSet_free_block_list();
1.129 +
1.130 + char *mem = (char*)arena()->Amalloc_4(sizeof(BitBlock) *
1.131 + bitblock_alloc_chunk_size + 32);
1.132 +
1.133 + // Align the pointer to a 32 bit boundary.
1.134 + BitBlock *new_blocks = (BitBlock*)(((uintptr_t)mem + 32) & ~0x001F);
1.135 +
1.136 + // Add the new blocks to the free list.
1.137 + for (int i = 0; i < bitblock_alloc_chunk_size; i++) {
1.138 + new_blocks->set_next(free);
1.139 + free = new_blocks;
1.140 + new_blocks++;
1.141 + }
1.142 +
1.143 + compile->set_indexSet_free_block_list(free);
1.144 +
1.145 +#ifdef ASSERT
1.146 + if (CollectIndexSetStatistics) {
1.147 + inc_stat_counter(&_alloc_new, bitblock_alloc_chunk_size);
1.148 + }
1.149 +#endif
1.150 +}
1.151 +
1.152 +
1.153 +//---------------------------- IndexSet::alloc_block() ------------------------
1.154 +// Allocate a BitBlock from the free list. If the free list is empty,
1.155 +// prime it.
1.156 +
1.157 +IndexSet::BitBlock *IndexSet::alloc_block() {
1.158 +#ifdef ASSERT
1.159 + if (CollectIndexSetStatistics) {
1.160 + inc_stat_counter(&_alloc_total, 1);
1.161 + }
1.162 +#endif
1.163 + Compile *compile = Compile::current();
1.164 + BitBlock* free_list = (BitBlock*)compile->indexSet_free_block_list();
1.165 + if (free_list == NULL) {
1.166 + populate_free_list();
1.167 + free_list = (BitBlock*)compile->indexSet_free_block_list();
1.168 + }
1.169 + BitBlock *block = free_list;
1.170 + compile->set_indexSet_free_block_list(block->next());
1.171 +
1.172 + block->clear();
1.173 + return block;
1.174 +}
1.175 +
1.176 +//---------------------------- IndexSet::alloc_block_containing() -------------
1.177 +// Allocate a new BitBlock and put it into the position in the _blocks array
1.178 +// corresponding to element.
1.179 +
1.180 +IndexSet::BitBlock *IndexSet::alloc_block_containing(uint element) {
1.181 + BitBlock *block = alloc_block();
1.182 + uint bi = get_block_index(element);
1.183 + _blocks[bi] = block;
1.184 + return block;
1.185 +}
1.186 +
1.187 +//---------------------------- IndexSet::free_block() -------------------------
1.188 +// Add a BitBlock to the free list.
1.189 +
1.190 +void IndexSet::free_block(uint i) {
1.191 + debug_only(check_watch("free block", i));
1.192 + assert(i < _max_blocks, "block index too large");
1.193 + BitBlock *block = _blocks[i];
1.194 + assert(block != &_empty_block, "cannot free the empty block");
1.195 + block->set_next((IndexSet::BitBlock*)Compile::current()->indexSet_free_block_list());
1.196 + Compile::current()->set_indexSet_free_block_list(block);
1.197 + set_block(i,&_empty_block);
1.198 +}
1.199 +
1.200 +//------------------------------lrg_union--------------------------------------
1.201 +// Compute the union of all elements of one and two which interfere with
1.202 +// the RegMask mask. If the degree of the union becomes exceeds
1.203 +// fail_degree, the union bails out. The underlying set is cleared before
1.204 +// the union is performed.
1.205 +
1.206 +uint IndexSet::lrg_union(uint lr1, uint lr2,
1.207 + const uint fail_degree,
1.208 + const PhaseIFG *ifg,
1.209 + const RegMask &mask ) {
1.210 + IndexSet *one = ifg->neighbors(lr1);
1.211 + IndexSet *two = ifg->neighbors(lr2);
1.212 + LRG &lrg1 = ifg->lrgs(lr1);
1.213 + LRG &lrg2 = ifg->lrgs(lr2);
1.214 +#ifdef ASSERT
1.215 + assert(_max_elements == one->_max_elements, "max element mismatch");
1.216 + check_watch("union destination");
1.217 + one->check_watch("union source");
1.218 + two->check_watch("union source");
1.219 +#endif
1.220 +
1.221 + // Compute the degree of the combined live-range. The combined
1.222 + // live-range has the union of the original live-ranges' neighbors set as
1.223 + // well as the neighbors of all intermediate copies, minus those neighbors
1.224 + // that can not use the intersected allowed-register-set.
1.225 +
1.226 + // Copy the larger set. Insert the smaller set into the larger.
1.227 + if (two->count() > one->count()) {
1.228 + IndexSet *temp = one;
1.229 + one = two;
1.230 + two = temp;
1.231 + }
1.232 +
1.233 + clear();
1.234 +
1.235 + // Used to compute degree of register-only interferences. Infinite-stack
1.236 + // neighbors do not alter colorability, as they can always color to some
1.237 + // other color. (A variant of the Briggs assertion)
1.238 + uint reg_degree = 0;
1.239 +
1.240 + uint element;
1.241 + // Load up the combined interference set with the neighbors of one
1.242 + IndexSetIterator elements(one);
1.243 + while ((element = elements.next()) != 0) {
1.244 + LRG &lrg = ifg->lrgs(element);
1.245 + if (mask.overlap(lrg.mask())) {
1.246 + insert(element);
1.247 + if( !lrg.mask().is_AllStack() ) {
1.248 + reg_degree += lrg1.compute_degree(lrg);
1.249 + if( reg_degree >= fail_degree ) return reg_degree;
1.250 + } else {
1.251 + // !!!!! Danger! No update to reg_degree despite having a neighbor.
1.252 + // A variant of the Briggs assertion.
1.253 + // Not needed if I simplify during coalesce, ala George/Appel.
1.254 + assert( lrg.lo_degree(), "" );
1.255 + }
1.256 + }
1.257 + }
1.258 + // Add neighbors of two as well
1.259 + IndexSetIterator elements2(two);
1.260 + while ((element = elements2.next()) != 0) {
1.261 + LRG &lrg = ifg->lrgs(element);
1.262 + if (mask.overlap(lrg.mask())) {
1.263 + if (insert(element)) {
1.264 + if( !lrg.mask().is_AllStack() ) {
1.265 + reg_degree += lrg2.compute_degree(lrg);
1.266 + if( reg_degree >= fail_degree ) return reg_degree;
1.267 + } else {
1.268 + // !!!!! Danger! No update to reg_degree despite having a neighbor.
1.269 + // A variant of the Briggs assertion.
1.270 + // Not needed if I simplify during coalesce, ala George/Appel.
1.271 + assert( lrg.lo_degree(), "" );
1.272 + }
1.273 + }
1.274 + }
1.275 + }
1.276 +
1.277 + return reg_degree;
1.278 +}
1.279 +
1.280 +//---------------------------- IndexSet() -----------------------------
1.281 +// A deep copy constructor. This is used when you need a scratch copy of this set.
1.282 +
1.283 +IndexSet::IndexSet (IndexSet *set) {
1.284 +#ifdef ASSERT
1.285 + _serial_number = _serial_count++;
1.286 + set->check_watch("copied", _serial_number);
1.287 + check_watch("initialized by copy", set->_serial_number);
1.288 + _max_elements = set->_max_elements;
1.289 +#endif
1.290 + _count = set->_count;
1.291 + _max_blocks = set->_max_blocks;
1.292 + if (_max_blocks <= preallocated_block_list_size) {
1.293 + _blocks = _preallocated_block_list;
1.294 + } else {
1.295 + _blocks =
1.296 + (IndexSet::BitBlock**) arena()->Amalloc_4(sizeof(IndexSet::BitBlock**) * _max_blocks);
1.297 + }
1.298 + for (uint i = 0; i < _max_blocks; i++) {
1.299 + BitBlock *block = set->_blocks[i];
1.300 + if (block == &_empty_block) {
1.301 + set_block(i, &_empty_block);
1.302 + } else {
1.303 + BitBlock *new_block = alloc_block();
1.304 + memcpy(new_block->words(), block->words(), sizeof(uint32) * words_per_block);
1.305 + set_block(i, new_block);
1.306 + }
1.307 + }
1.308 +}
1.309 +
1.310 +//---------------------------- IndexSet::initialize() -----------------------------
1.311 +// Prepare an IndexSet for use.
1.312 +
1.313 +void IndexSet::initialize(uint max_elements) {
1.314 +#ifdef ASSERT
1.315 + _serial_number = _serial_count++;
1.316 + check_watch("initialized", max_elements);
1.317 + _max_elements = max_elements;
1.318 +#endif
1.319 + _count = 0;
1.320 + _max_blocks = (max_elements + bits_per_block - 1) / bits_per_block;
1.321 +
1.322 + if (_max_blocks <= preallocated_block_list_size) {
1.323 + _blocks = _preallocated_block_list;
1.324 + } else {
1.325 + _blocks = (IndexSet::BitBlock**) arena()->Amalloc_4(sizeof(IndexSet::BitBlock**) * _max_blocks);
1.326 + }
1.327 + for (uint i = 0; i < _max_blocks; i++) {
1.328 + set_block(i, &_empty_block);
1.329 + }
1.330 +}
1.331 +
1.332 +//---------------------------- IndexSet::initialize()------------------------------
1.333 +// Prepare an IndexSet for use. If it needs to allocate its _blocks array, it does
1.334 +// so from the Arena passed as a parameter. BitBlock allocation is still done from
1.335 +// the static Arena which was set with reset_memory().
1.336 +
1.337 +void IndexSet::initialize(uint max_elements, Arena *arena) {
1.338 +#ifdef ASSERT
1.339 + _serial_number = _serial_count++;
1.340 + check_watch("initialized2", max_elements);
1.341 + _max_elements = max_elements;
1.342 +#endif // ASSERT
1.343 + _count = 0;
1.344 + _max_blocks = (max_elements + bits_per_block - 1) / bits_per_block;
1.345 +
1.346 + if (_max_blocks <= preallocated_block_list_size) {
1.347 + _blocks = _preallocated_block_list;
1.348 + } else {
1.349 + _blocks = (IndexSet::BitBlock**) arena->Amalloc_4(sizeof(IndexSet::BitBlock**) * _max_blocks);
1.350 + }
1.351 + for (uint i = 0; i < _max_blocks; i++) {
1.352 + set_block(i, &_empty_block);
1.353 + }
1.354 +}
1.355 +
1.356 +//---------------------------- IndexSet::swap() -----------------------------
1.357 +// Exchange two IndexSets.
1.358 +
1.359 +void IndexSet::swap(IndexSet *set) {
1.360 +#ifdef ASSERT
1.361 + assert(_max_elements == set->_max_elements, "must have same universe size to swap");
1.362 + check_watch("swap", set->_serial_number);
1.363 + set->check_watch("swap", _serial_number);
1.364 +#endif
1.365 +
1.366 + for (uint i = 0; i < _max_blocks; i++) {
1.367 + BitBlock *temp = _blocks[i];
1.368 + set_block(i, set->_blocks[i]);
1.369 + set->set_block(i, temp);
1.370 + }
1.371 + uint temp = _count;
1.372 + _count = set->_count;
1.373 + set->_count = temp;
1.374 +}
1.375 +
1.376 +//---------------------------- IndexSet::dump() -----------------------------
1.377 +// Print this set. Used for debugging.
1.378 +
1.379 +#ifndef PRODUCT
1.380 +void IndexSet::dump() const {
1.381 + IndexSetIterator elements(this);
1.382 +
1.383 + tty->print("{");
1.384 + uint i;
1.385 + while ((i = elements.next()) != 0) {
1.386 + tty->print("L%d ", i);
1.387 + }
1.388 + tty->print_cr("}");
1.389 +}
1.390 +#endif
1.391 +
1.392 +#ifdef ASSERT
1.393 +//---------------------------- IndexSet::tally_iteration_statistics() -----------------------------
1.394 +// Update block/bit counts to reflect that this set has been iterated over.
1.395 +
1.396 +void IndexSet::tally_iteration_statistics() const {
1.397 + inc_stat_counter(&_total_bits, count());
1.398 +
1.399 + for (uint i = 0; i < _max_blocks; i++) {
1.400 + if (_blocks[i] != &_empty_block) {
1.401 + inc_stat_counter(&_total_used_blocks, 1);
1.402 + } else {
1.403 + inc_stat_counter(&_total_unused_blocks, 1);
1.404 + }
1.405 + }
1.406 +}
1.407 +
1.408 +//---------------------------- IndexSet::print_statistics() -----------------------------
1.409 +// Print statistics about IndexSet usage.
1.410 +
1.411 +void IndexSet::print_statistics() {
1.412 + julong total_blocks = _total_used_blocks + _total_unused_blocks;
1.413 + tty->print_cr ("Accumulated IndexSet usage statistics:");
1.414 + tty->print_cr ("--------------------------------------");
1.415 + tty->print_cr (" Iteration:");
1.416 + tty->print_cr (" blocks visited: " UINT64_FORMAT, total_blocks);
1.417 + tty->print_cr (" blocks empty: %4.2f%%", 100.0*(double)_total_unused_blocks/total_blocks);
1.418 + tty->print_cr (" bit density (bits/used blocks): %4.2f", (double)_total_bits/_total_used_blocks);
1.419 + tty->print_cr (" bit density (bits/all blocks): %4.2f", (double)_total_bits/total_blocks);
1.420 + tty->print_cr (" Allocation:");
1.421 + tty->print_cr (" blocks allocated: " UINT64_FORMAT, _alloc_new);
1.422 + tty->print_cr (" blocks used/reused: " UINT64_FORMAT, _alloc_total);
1.423 +}
1.424 +
1.425 +//---------------------------- IndexSet::verify() -----------------------------
1.426 +// Expensive test of IndexSet sanity. Ensure that the count agrees with the
1.427 +// number of bits in the blocks. Make sure the iterator is seeing all elements
1.428 +// of the set. Meant for use during development.
1.429 +
1.430 +void IndexSet::verify() const {
1.431 + assert(!member(0), "zero cannot be a member");
1.432 + uint count = 0;
1.433 + uint i;
1.434 + for (i = 1; i < _max_elements; i++) {
1.435 + if (member(i)) {
1.436 + count++;
1.437 + assert(count <= _count, "_count is messed up");
1.438 + }
1.439 + }
1.440 +
1.441 + IndexSetIterator elements(this);
1.442 + count = 0;
1.443 + while ((i = elements.next()) != 0) {
1.444 + count++;
1.445 + assert(member(i), "returned a non member");
1.446 + assert(count <= _count, "iterator returned wrong number of elements");
1.447 + }
1.448 +}
1.449 +#endif
1.450 +
1.451 +//---------------------------- IndexSetIterator() -----------------------------
1.452 +// Create an iterator for a set. If empty blocks are detected when iterating
1.453 +// over the set, these blocks are replaced.
1.454 +
1.455 +IndexSetIterator::IndexSetIterator(IndexSet *set) {
1.456 +#ifdef ASSERT
1.457 + if (CollectIndexSetStatistics) {
1.458 + set->tally_iteration_statistics();
1.459 + }
1.460 + set->check_watch("traversed", set->count());
1.461 +#endif
1.462 + if (set->is_empty()) {
1.463 + _current = 0;
1.464 + _next_word = IndexSet::words_per_block;
1.465 + _next_block = 1;
1.466 + _max_blocks = 1;
1.467 +
1.468 + // We don't need the following values when we iterate over an empty set.
1.469 + // The commented out code is left here to document that the omission
1.470 + // is intentional.
1.471 + //
1.472 + //_value = 0;
1.473 + //_words = NULL;
1.474 + //_blocks = NULL;
1.475 + //_set = NULL;
1.476 + } else {
1.477 + _current = 0;
1.478 + _value = 0;
1.479 + _next_block = 0;
1.480 + _next_word = IndexSet::words_per_block;
1.481 +
1.482 + _max_blocks = set->_max_blocks;
1.483 + _words = NULL;
1.484 + _blocks = set->_blocks;
1.485 + _set = set;
1.486 + }
1.487 +}
1.488 +
1.489 +//---------------------------- IndexSetIterator(const) -----------------------------
1.490 +// Iterate over a constant IndexSet.
1.491 +
1.492 +IndexSetIterator::IndexSetIterator(const IndexSet *set) {
1.493 +#ifdef ASSERT
1.494 + if (CollectIndexSetStatistics) {
1.495 + set->tally_iteration_statistics();
1.496 + }
1.497 + // We don't call check_watch from here to avoid bad recursion.
1.498 + // set->check_watch("traversed const", set->count());
1.499 +#endif
1.500 + if (set->is_empty()) {
1.501 + _current = 0;
1.502 + _next_word = IndexSet::words_per_block;
1.503 + _next_block = 1;
1.504 + _max_blocks = 1;
1.505 +
1.506 + // We don't need the following values when we iterate over an empty set.
1.507 + // The commented out code is left here to document that the omission
1.508 + // is intentional.
1.509 + //
1.510 + //_value = 0;
1.511 + //_words = NULL;
1.512 + //_blocks = NULL;
1.513 + //_set = NULL;
1.514 + } else {
1.515 + _current = 0;
1.516 + _value = 0;
1.517 + _next_block = 0;
1.518 + _next_word = IndexSet::words_per_block;
1.519 +
1.520 + _max_blocks = set->_max_blocks;
1.521 + _words = NULL;
1.522 + _blocks = set->_blocks;
1.523 + _set = NULL;
1.524 + }
1.525 +}
1.526 +
1.527 +//---------------------------- List16Iterator::advance_and_next() -----------------------------
1.528 +// Advance to the next non-empty word in the set being iterated over. Return the next element
1.529 +// if there is one. If we are done, return 0. This method is called from the next() method
1.530 +// when it gets done with a word.
1.531 +
1.532 +uint IndexSetIterator::advance_and_next() {
1.533 + // See if there is another non-empty word in the current block.
1.534 + for (uint wi = _next_word; wi < (unsigned)IndexSet::words_per_block; wi++) {
1.535 + if (_words[wi] != 0) {
1.536 + // Found a non-empty word.
1.537 + _value = ((_next_block - 1) * IndexSet::bits_per_block) + (wi * IndexSet::bits_per_word);
1.538 + _current = _words[wi];
1.539 +
1.540 + _next_word = wi+1;
1.541 +
1.542 + return next();
1.543 + }
1.544 + }
1.545 +
1.546 + // We ran out of words in the current block. Advance to next non-empty block.
1.547 + for (uint bi = _next_block; bi < _max_blocks; bi++) {
1.548 + if (_blocks[bi] != &IndexSet::_empty_block) {
1.549 + // Found a non-empty block.
1.550 +
1.551 + _words = _blocks[bi]->words();
1.552 + for (uint wi = 0; wi < (unsigned)IndexSet::words_per_block; wi++) {
1.553 + if (_words[wi] != 0) {
1.554 + // Found a non-empty word.
1.555 + _value = (bi * IndexSet::bits_per_block) + (wi * IndexSet::bits_per_word);
1.556 + _current = _words[wi];
1.557 +
1.558 + _next_block = bi+1;
1.559 + _next_word = wi+1;
1.560 +
1.561 + return next();
1.562 + }
1.563 + }
1.564 +
1.565 + // All of the words in the block were empty. Replace
1.566 + // the block with the empty block.
1.567 + if (_set) {
1.568 + _set->free_block(bi);
1.569 + }
1.570 + }
1.571 + }
1.572 +
1.573 + // These assignments make redundant calls to next on a finished iterator
1.574 + // faster. Probably not necessary.
1.575 + _next_block = _max_blocks;
1.576 + _next_word = IndexSet::words_per_block;
1.577 +
1.578 + // No more words.
1.579 + return 0;
1.580 +}
