89 static uint get_bit_index(uint element) {
90 return mask_bits(element,bit_index_mask);
91 }
92
93 //------------------------------ class BitBlock ----------------------------
94 // The BitBlock class is a segment of a bitvector set.
95
96 class BitBlock : public ResourceObj {
97 friend class IndexSetIterator;
98 friend class IndexSet;
99
100 private:
101 // All of BitBlocks fields and methods are declared private. We limit
102 // access to IndexSet and IndexSetIterator.
103
104 // A BitBlock is composed of some number of 32 bit words. When a BitBlock
105 // is not in use by any IndexSet, it is stored on a free list. The next field
106 // is used by IndexSet to mainting this free list.
107
108 union {
109 uint32 _words[words_per_block];
110 BitBlock *_next;
111 } _data;
112
113 // accessors
114 uint32 *words() { return _data._words; }
115 void set_next(BitBlock *next) { _data._next = next; }
116 BitBlock *next() { return _data._next; }
117
118 // Operations. A BitBlock supports four simple operations,
119 // clear(), member(), insert(), and remove(). These methods do
120 // not assume that the block index has been masked out.
121
122 void clear() {
123 memset(words(), 0, sizeof(uint32) * words_per_block);
124 }
125
126 bool member(uint element) {
127 uint word_index = IndexSet::get_word_index(element);
128 uint bit_index = IndexSet::get_bit_index(element);
129
130 return ((words()[word_index] & (uint32)(0x1 << bit_index)) != 0);
131 }
132
133 bool insert(uint element) {
134 uint word_index = IndexSet::get_word_index(element);
135 uint bit_index = IndexSet::get_bit_index(element);
136
137 uint32 bit = (0x1 << bit_index);
138 uint32 before = words()[word_index];
139 words()[word_index] = before | bit;
140 return ((before & bit) != 0);
141 }
142
143 bool remove(uint element) {
144 uint word_index = IndexSet::get_word_index(element);
145 uint bit_index = IndexSet::get_bit_index(element);
146
147 uint32 bit = (0x1 << bit_index);
148 uint32 before = words()[word_index];
149 words()[word_index] = before & ~bit;
150 return ((before & bit) != 0);
151 }
152 };
153
154 //-------------------------- BitBlock allocation ---------------------------
155 private:
156
157 // All IndexSets share an arena from which they allocate BitBlocks. Unused
158 // BitBlocks are placed on a free list.
159
160 // The number of BitBlocks to allocate at a time
161 enum { bitblock_alloc_chunk_size = 50 };
162
163 static Arena *arena() { return Compile::current()->indexSet_arena(); }
164
165 static void populate_free_list();
166
167 public:
168
387 static void print_statistics();
388
389 #endif
390 };
391
392
393 //-------------------------------- class IndexSetIterator --------------------
394 // An iterator for IndexSets.
395
396 class IndexSetIterator VALUE_OBJ_CLASS_SPEC {
397 friend class IndexSet;
398
399 public:
400
401 // We walk over the bits in a word in chunks of size window_size.
402 enum { window_size = 5,
403 window_mask = right_n_bits(window_size),
404 table_size = (1 << window_size) };
405
406 // For an integer of length window_size, what is the first set bit?
407 static const byte _first_bit[table_size];
408
409 // For an integer of length window_size, what is the second set bit?
410 static const byte _second_bit[table_size];
411
412 private:
413 // The current word we are inspecting
414 uint32 _current;
415
416 // What element number are we currently on?
417 uint _value;
418
419 // The index of the next word we will inspect
420 uint _next_word;
421
422 // A pointer to the contents of the current block
423 uint32 *_words;
424
425 // The index of the next block we will inspect
426 uint _next_block;
427
428 // A pointer to the blocks in our set
429 IndexSet::BitBlock **_blocks;
430
431 // The number of blocks in the set
432 uint _max_blocks;
433
434 // If the iterator was created from a non-const set, we replace
435 // non-canonical empty blocks with the _empty_block pointer. If
436 // _set is NULL, we do no replacement.
437 IndexSet *_set;
438
439 // Advance to the next non-empty word and return the next
440 // element in the set.
441 uint advance_and_next();
442
443
|
89 static uint get_bit_index(uint element) {
90 return mask_bits(element,bit_index_mask);
91 }
92
93 //------------------------------ class BitBlock ----------------------------
94 // The BitBlock class is a segment of a bitvector set.
95
96 class BitBlock : public ResourceObj {
97 friend class IndexSetIterator;
98 friend class IndexSet;
99
100 private:
101 // All of BitBlocks fields and methods are declared private. We limit
102 // access to IndexSet and IndexSetIterator.
103
104 // A BitBlock is composed of some number of 32 bit words. When a BitBlock
105 // is not in use by any IndexSet, it is stored on a free list. The next field
106 // is used by IndexSet to mainting this free list.
107
108 union {
109 uint32_t _words[words_per_block];
110 BitBlock *_next;
111 } _data;
112
113 // accessors
114 uint32_t* words() { return _data._words; }
115 void set_next(BitBlock *next) { _data._next = next; }
116 BitBlock *next() { return _data._next; }
117
118 // Operations. A BitBlock supports four simple operations,
119 // clear(), member(), insert(), and remove(). These methods do
120 // not assume that the block index has been masked out.
121
122 void clear() {
123 memset(words(), 0, sizeof(uint32_t) * words_per_block);
124 }
125
126 bool member(uint element) {
127 uint word_index = IndexSet::get_word_index(element);
128 uint bit_index = IndexSet::get_bit_index(element);
129
130 return ((words()[word_index] & (uint32_t)(0x1 << bit_index)) != 0);
131 }
132
133 bool insert(uint element) {
134 uint word_index = IndexSet::get_word_index(element);
135 uint bit_index = IndexSet::get_bit_index(element);
136
137 uint32_t bit = (0x1 << bit_index);
138 uint32_t before = words()[word_index];
139 words()[word_index] = before | bit;
140 return ((before & bit) != 0);
141 }
142
143 bool remove(uint element) {
144 uint word_index = IndexSet::get_word_index(element);
145 uint bit_index = IndexSet::get_bit_index(element);
146
147 uint32_t bit = (0x1 << bit_index);
148 uint32_t before = words()[word_index];
149 words()[word_index] = before & ~bit;
150 return ((before & bit) != 0);
151 }
152 };
153
154 //-------------------------- BitBlock allocation ---------------------------
155 private:
156
157 // All IndexSets share an arena from which they allocate BitBlocks. Unused
158 // BitBlocks are placed on a free list.
159
160 // The number of BitBlocks to allocate at a time
161 enum { bitblock_alloc_chunk_size = 50 };
162
163 static Arena *arena() { return Compile::current()->indexSet_arena(); }
164
165 static void populate_free_list();
166
167 public:
168
387 static void print_statistics();
388
389 #endif
390 };
391
392
393 //-------------------------------- class IndexSetIterator --------------------
394 // An iterator for IndexSets.
395
396 class IndexSetIterator VALUE_OBJ_CLASS_SPEC {
397 friend class IndexSet;
398
399 public:
400
401 // We walk over the bits in a word in chunks of size window_size.
402 enum { window_size = 5,
403 window_mask = right_n_bits(window_size),
404 table_size = (1 << window_size) };
405
406 // For an integer of length window_size, what is the first set bit?
407 static const uint8_t _first_bit[table_size];
408
409 // For an integer of length window_size, what is the second set bit?
410 static const uint8_t _second_bit[table_size];
411
412 private:
413 // The current word we are inspecting
414 uint32_t _current;
415
416 // What element number are we currently on?
417 uint _value;
418
419 // The index of the next word we will inspect
420 uint _next_word;
421
422 // A pointer to the contents of the current block
423 uint32_t *_words;
424
425 // The index of the next block we will inspect
426 uint _next_block;
427
428 // A pointer to the blocks in our set
429 IndexSet::BitBlock **_blocks;
430
431 // The number of blocks in the set
432 uint _max_blocks;
433
434 // If the iterator was created from a non-const set, we replace
435 // non-canonical empty blocks with the _empty_block pointer. If
436 // _set is NULL, we do no replacement.
437 IndexSet *_set;
438
439 // Advance to the next non-empty word and return the next
440 // element in the set.
441 uint advance_and_next();
442
443
|