188 //-------------------------- Members ------------------------------------------ |
188 //-------------------------- Members ------------------------------------------ |
189 |
189 |
190 // The number of elements in the set |
190 // The number of elements in the set |
191 uint _count; |
191 uint _count; |
192 |
192 |
|
193 // The current upper limit of blocks that has been allocated and might be in use |
|
194 uint _current_block_limit; |
|
195 |
193 // Our top level array of bitvector segments |
196 // Our top level array of bitvector segments |
194 BitBlock **_blocks; |
197 BitBlock **_blocks; |
195 |
198 |
196 BitBlock *_preallocated_block_list[preallocated_block_list_size]; |
199 BitBlock *_preallocated_block_list[preallocated_block_list_size]; |
197 |
200 |
244 public: |
247 public: |
245 //-------------------------- Primitive set operations -------------------------- |
248 //-------------------------- Primitive set operations -------------------------- |
246 |
249 |
247 void clear() { |
250 void clear() { |
248 _count = 0; |
251 _count = 0; |
249 for (uint i = 0; i < _max_blocks; i++) { |
252 for (uint i = 0; i < _current_block_limit; i++) { |
250 BitBlock *block = _blocks[i]; |
253 BitBlock *block = _blocks[i]; |
251 if (block != &_empty_block) { |
254 if (block != &_empty_block) { |
252 free_block(i); |
255 free_block(i); |
253 } |
256 } |
254 } |
257 } |
|
258 _current_block_limit = 0; |
255 } |
259 } |
256 |
260 |
257 uint count() const { return _count; } |
261 uint count() const { return _count; } |
258 |
262 |
259 bool is_empty() const { return _count == 0; } |
263 bool is_empty() const { return _count == 0; } |
378 uint _value; |
382 uint _value; |
379 |
383 |
380 // The index of the next word we will inspect |
384 // The index of the next word we will inspect |
381 uint _next_word; |
385 uint _next_word; |
382 |
386 |
|
387 // The index of the next block we will inspect |
|
388 uint _next_block; |
|
389 |
|
390 // The number of blocks in the set |
|
391 uint _max_blocks; |
|
392 |
383 // A pointer to the contents of the current block |
393 // A pointer to the contents of the current block |
384 uint32_t *_words; |
394 uint32_t *_words; |
385 |
395 |
386 // The index of the next block we will inspect |
|
387 uint _next_block; |
|
388 |
|
389 // A pointer to the blocks in our set |
396 // A pointer to the blocks in our set |
390 IndexSet::BitBlock **_blocks; |
397 IndexSet::BitBlock **_blocks; |
391 |
|
392 // The number of blocks in the set |
|
393 uint _max_blocks; |
|
394 |
398 |
395 // If the iterator was created from a non-const set, we replace |
399 // If the iterator was created from a non-const set, we replace |
396 // non-canonical empty blocks with the _empty_block pointer. If |
400 // non-canonical empty blocks with the _empty_block pointer. If |
397 // _set is NULL, we do no replacement. |
401 // _set is NULL, we do no replacement. |
398 IndexSet *_set; |
402 IndexSet *_set; |
403 |
407 |
404 public: |
408 public: |
405 |
409 |
406 // If an iterator is built from a constant set then empty blocks |
410 // If an iterator is built from a constant set then empty blocks |
407 // are not canonicalized. |
411 // are not canonicalized. |
408 IndexSetIterator(IndexSet *set); |
412 IndexSetIterator(IndexSet *set) : |
409 IndexSetIterator(const IndexSet *set); |
413 _current(0), |
|
414 _value(0), |
|
415 _next_word(IndexSet::words_per_block), |
|
416 _next_block(0), |
|
417 _max_blocks(set->is_empty() ? 0 : set->_current_block_limit), |
|
418 _words(NULL), |
|
419 _blocks(set->_blocks), |
|
420 _set(set) { |
|
421 #ifdef ASSERT |
|
422 if (CollectIndexSetStatistics) { |
|
423 set->tally_iteration_statistics(); |
|
424 } |
|
425 set->check_watch("traversed", set->count()); |
|
426 #endif |
|
427 } |
|
428 |
|
429 IndexSetIterator(const IndexSet *set) : |
|
430 _current(0), |
|
431 _value(0), |
|
432 _next_word(IndexSet::words_per_block), |
|
433 _next_block(0), |
|
434 _max_blocks(set->is_empty() ? 0 : set->_current_block_limit), |
|
435 _words(NULL), |
|
436 _blocks(set->_blocks), |
|
437 _set(NULL) |
|
438 { |
|
439 #ifdef ASSERT |
|
440 if (CollectIndexSetStatistics) { |
|
441 set->tally_iteration_statistics(); |
|
442 } |
|
443 // We don't call check_watch from here to avoid bad recursion. |
|
444 // set->check_watch("traversed const", set->count()); |
|
445 #endif |
|
446 } |
|
447 |
|
448 // Return the next element of the set. |
|
449 uint next_value() { |
|
450 uint current = _current; |
|
451 assert(current != 0, "sanity"); |
|
452 uint advance = count_trailing_zeros(current); |
|
453 assert(((current >> advance) & 0x1) == 1, "sanity"); |
|
454 _current = (current >> advance) - 1; |
|
455 _value += advance; |
|
456 return _value; |
|
457 } |
410 |
458 |
411 // Return the next element of the set. Return 0 when done. |
459 // Return the next element of the set. Return 0 when done. |
412 uint next() { |
460 uint next() { |
413 uint current = _current; |
461 if (_current != 0) { |
414 if (current != 0) { |
462 return next_value(); |
415 uint advance = count_trailing_zeros(current); |
463 } else if (_next_word < IndexSet::words_per_block || _next_block < _max_blocks) { |
416 assert(((current >> advance) & 0x1) == 1, "sanity"); |
464 return advance_and_next(); |
417 _current = (current >> advance) - 1; |
|
418 _value += advance; |
|
419 return _value; |
|
420 } else { |
465 } else { |
421 return advance_and_next(); |
466 return 0; |
422 } |
467 } |
423 } |
468 } |
|
469 |
424 }; |
470 }; |
425 |
471 |
426 #endif // SHARE_OPTO_INDEXSET_HPP |
472 #endif // SHARE_OPTO_INDEXSET_HPP |