104 // A BitBlock is composed of some number of 32 bit words. When a BitBlock |
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 |
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. |
106 // is used by IndexSet to mainting this free list. |
107 |
107 |
108 union { |
108 union { |
109 uint32 _words[words_per_block]; |
109 uint32_t _words[words_per_block]; |
110 BitBlock *_next; |
110 BitBlock *_next; |
111 } _data; |
111 } _data; |
112 |
112 |
113 // accessors |
113 // accessors |
114 uint32 *words() { return _data._words; } |
114 uint32_t* words() { return _data._words; } |
115 void set_next(BitBlock *next) { _data._next = next; } |
115 void set_next(BitBlock *next) { _data._next = next; } |
116 BitBlock *next() { return _data._next; } |
116 BitBlock *next() { return _data._next; } |
117 |
117 |
118 // Operations. A BitBlock supports four simple operations, |
118 // Operations. A BitBlock supports four simple operations, |
119 // clear(), member(), insert(), and remove(). These methods do |
119 // clear(), member(), insert(), and remove(). These methods do |
120 // not assume that the block index has been masked out. |
120 // not assume that the block index has been masked out. |
121 |
121 |
122 void clear() { |
122 void clear() { |
123 memset(words(), 0, sizeof(uint32) * words_per_block); |
123 memset(words(), 0, sizeof(uint32_t) * words_per_block); |
124 } |
124 } |
125 |
125 |
126 bool member(uint element) { |
126 bool member(uint element) { |
127 uint word_index = IndexSet::get_word_index(element); |
127 uint word_index = IndexSet::get_word_index(element); |
128 uint bit_index = IndexSet::get_bit_index(element); |
128 uint bit_index = IndexSet::get_bit_index(element); |
129 |
129 |
130 return ((words()[word_index] & (uint32)(0x1 << bit_index)) != 0); |
130 return ((words()[word_index] & (uint32_t)(0x1 << bit_index)) != 0); |
131 } |
131 } |
132 |
132 |
133 bool insert(uint element) { |
133 bool insert(uint element) { |
134 uint word_index = IndexSet::get_word_index(element); |
134 uint word_index = IndexSet::get_word_index(element); |
135 uint bit_index = IndexSet::get_bit_index(element); |
135 uint bit_index = IndexSet::get_bit_index(element); |
136 |
136 |
137 uint32 bit = (0x1 << bit_index); |
137 uint32_t bit = (0x1 << bit_index); |
138 uint32 before = words()[word_index]; |
138 uint32_t before = words()[word_index]; |
139 words()[word_index] = before | bit; |
139 words()[word_index] = before | bit; |
140 return ((before & bit) != 0); |
140 return ((before & bit) != 0); |
141 } |
141 } |
142 |
142 |
143 bool remove(uint element) { |
143 bool remove(uint element) { |
144 uint word_index = IndexSet::get_word_index(element); |
144 uint word_index = IndexSet::get_word_index(element); |
145 uint bit_index = IndexSet::get_bit_index(element); |
145 uint bit_index = IndexSet::get_bit_index(element); |
146 |
146 |
147 uint32 bit = (0x1 << bit_index); |
147 uint32_t bit = (0x1 << bit_index); |
148 uint32 before = words()[word_index]; |
148 uint32_t before = words()[word_index]; |
149 words()[word_index] = before & ~bit; |
149 words()[word_index] = before & ~bit; |
150 return ((before & bit) != 0); |
150 return ((before & bit) != 0); |
151 } |
151 } |
152 }; |
152 }; |
153 |
153 |
402 enum { window_size = 5, |
402 enum { window_size = 5, |
403 window_mask = right_n_bits(window_size), |
403 window_mask = right_n_bits(window_size), |
404 table_size = (1 << window_size) }; |
404 table_size = (1 << window_size) }; |
405 |
405 |
406 // For an integer of length window_size, what is the first set bit? |
406 // For an integer of length window_size, what is the first set bit? |
407 static const byte _first_bit[table_size]; |
407 static const uint8_t _first_bit[table_size]; |
408 |
408 |
409 // For an integer of length window_size, what is the second set bit? |
409 // For an integer of length window_size, what is the second set bit? |
410 static const byte _second_bit[table_size]; |
410 static const uint8_t _second_bit[table_size]; |
411 |
411 |
412 private: |
412 private: |
413 // The current word we are inspecting |
413 // The current word we are inspecting |
414 uint32 _current; |
414 uint32_t _current; |
415 |
415 |
416 // What element number are we currently on? |
416 // What element number are we currently on? |
417 uint _value; |
417 uint _value; |
418 |
418 |
419 // The index of the next word we will inspect |
419 // The index of the next word we will inspect |
420 uint _next_word; |
420 uint _next_word; |
421 |
421 |
422 // A pointer to the contents of the current block |
422 // A pointer to the contents of the current block |
423 uint32 *_words; |
423 uint32_t *_words; |
424 |
424 |
425 // The index of the next block we will inspect |
425 // The index of the next block we will inspect |
426 uint _next_block; |
426 uint _next_block; |
427 |
427 |
428 // A pointer to the blocks in our set |
428 // A pointer to the blocks in our set |