Mercurial > hg > truffle

comparison src/share/vm/utilities/bitMap.cpp @ 342:37f87013dfd8

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
6711316: Open source the Garbage-First garbage collector Summary: First mercurial integration of the code for the Garbage-First garbage collector. Reviewed-by: apetrusenko, iveresov, jmasa, sgoldman, tonyp, ysr
author ysr
date Thu, 05 Jun 2008 15:57:56 -0700
parents a61af66fc99e
children 6e2afda171db
comparison
equal deleted inserted replaced
189:0b27f3512f9e 342:37f87013dfd8
24 24
25 # include "incls/_precompiled.incl" 25 # include "incls/_precompiled.incl"
26 # include "incls/_bitMap.cpp.incl" 26 # include "incls/_bitMap.cpp.incl"
27 27
28 28
29 BitMap::BitMap(idx_t* map, idx_t size_in_bits) { 29 BitMap::BitMap(bm_word_t* map, idx_t size_in_bits) :
30 _map(map), _size(size_in_bits)
31 {
32 assert(sizeof(bm_word_t) == BytesPerWord, "Implementation assumption.");
30 assert(size_in_bits >= 0, "just checking"); 33 assert(size_in_bits >= 0, "just checking");
31 _map = map; 34 }
35
36
37 BitMap::BitMap(idx_t size_in_bits, bool in_resource_area) :
38 _map(NULL), _size(0)
39 {
40 assert(sizeof(bm_word_t) == BytesPerWord, "Implementation assumption.");
41 resize(size_in_bits, in_resource_area);
42 }
43
44
45 void BitMap::verify_index(idx_t index) const {
46 assert(index < _size, "BitMap index out of bounds");
47 }
48
49 void BitMap::verify_range(idx_t beg_index, idx_t end_index) const {
50 #ifdef ASSERT
51 assert(beg_index <= end_index, "BitMap range error");
52 // Note that [0,0) and [size,size) are both valid ranges.
53 if (end_index != _size) verify_index(end_index);
54 #endif
55 }
56
57 void BitMap::resize(idx_t size_in_bits, bool in_resource_area) {
58 assert(size_in_bits >= 0, "just checking");
59 idx_t old_size_in_words = size_in_words();
60 bm_word_t* old_map = map();
61
32 _size = size_in_bits; 62 _size = size_in_bits;
33 } 63 idx_t new_size_in_words = size_in_words();
34 64 if (in_resource_area) {
35 65 _map = NEW_RESOURCE_ARRAY(bm_word_t, new_size_in_words);
36 BitMap::BitMap(idx_t size_in_bits) { 66 } else {
37 assert(size_in_bits >= 0, "just checking"); 67 if (old_map != NULL) FREE_C_HEAP_ARRAY(bm_word_t, _map);
38 _size = size_in_bits; 68 _map = NEW_C_HEAP_ARRAY(bm_word_t, new_size_in_words);
39 _map = NEW_RESOURCE_ARRAY(idx_t, size_in_words()); 69 }
40 } 70 Copy::disjoint_words((HeapWord*)old_map, (HeapWord*) _map,
41 71 MIN2(old_size_in_words, new_size_in_words));
42
43 void BitMap::resize(idx_t size_in_bits) {
44 assert(size_in_bits >= 0, "just checking");
45 size_t old_size_in_words = size_in_words();
46 uintptr_t* old_map = map();
47 _size = size_in_bits;
48 size_t new_size_in_words = size_in_words();
49 _map = NEW_RESOURCE_ARRAY(idx_t, new_size_in_words);
50 Copy::disjoint_words((HeapWord*) old_map, (HeapWord*) _map, MIN2(old_size_in_words, new_size_in_words));
51 if (new_size_in_words > old_size_in_words) { 72 if (new_size_in_words > old_size_in_words) {
52 clear_range_of_words(old_size_in_words, size_in_words()); 73 clear_range_of_words(old_size_in_words, size_in_words());
53 } 74 }
54 }
55
56 // Returns a bit mask for a range of bits [beg, end) within a single word. Each
57 // bit in the mask is 0 if the bit is in the range, 1 if not in the range. The
58 // returned mask can be used directly to clear the range, or inverted to set the
59 // range. Note: end must not be 0.
60 inline BitMap::idx_t
61 BitMap::inverted_bit_mask_for_range(idx_t beg, idx_t end) const {
62 assert(end != 0, "does not work when end == 0");
63 assert(beg == end || word_index(beg) == word_index(end - 1),
64 "must be a single-word range");
65 idx_t mask = bit_mask(beg) - 1; // low (right) bits
66 if (bit_in_word(end) != 0) {
67 mask |= ~(bit_mask(end) - 1); // high (left) bits
68 }
69 return mask;
70 } 75 }
71 76
72 void BitMap::set_range_within_word(idx_t beg, idx_t end) { 77 void BitMap::set_range_within_word(idx_t beg, idx_t end) {
73 // With a valid range (beg <= end), this test ensures that end != 0, as 78 // With a valid range (beg <= end), this test ensures that end != 0, as
74 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write. 79 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write.
75 if (beg != end) { 80 if (beg != end) {
76 idx_t mask = inverted_bit_mask_for_range(beg, end); 81 bm_word_t mask = inverted_bit_mask_for_range(beg, end);
77 *word_addr(beg) |= ~mask; 82 *word_addr(beg) |= ~mask;
78 } 83 }
79 } 84 }
80 85
81 void BitMap::clear_range_within_word(idx_t beg, idx_t end) { 86 void BitMap::clear_range_within_word(idx_t beg, idx_t end) {
82 // With a valid range (beg <= end), this test ensures that end != 0, as 87 // With a valid range (beg <= end), this test ensures that end != 0, as
83 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write. 88 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write.
84 if (beg != end) { 89 if (beg != end) {
85 idx_t mask = inverted_bit_mask_for_range(beg, end); 90 bm_word_t mask = inverted_bit_mask_for_range(beg, end);
86 *word_addr(beg) &= mask; 91 *word_addr(beg) &= mask;
87 } 92 }
88 } 93 }
89 94
90 void BitMap::par_put_range_within_word(idx_t beg, idx_t end, bool value) { 95 void BitMap::par_put_range_within_word(idx_t beg, idx_t end, bool value) {
103 nw = value ? (w | ~mr) : (w & mr); 108 nw = value ? (w | ~mr) : (w & mr);
104 } 109 }
105 } 110 }
106 } 111 }
107 112
108 inline void BitMap::set_large_range_of_words(idx_t beg, idx_t end) {
109 memset(_map + beg, ~(unsigned char)0, (end - beg) * sizeof(uintptr_t));
110 }
111
112 inline void BitMap::clear_large_range_of_words(idx_t beg, idx_t end) {
113 memset(_map + beg, 0, (end - beg) * sizeof(uintptr_t));
114 }
115
116 inline BitMap::idx_t BitMap::word_index_round_up(idx_t bit) const {
117 idx_t bit_rounded_up = bit + (BitsPerWord - 1);
118 // Check for integer arithmetic overflow.
119 return bit_rounded_up > bit ? word_index(bit_rounded_up) : size_in_words();
120 }
121
122 void BitMap::set_range(idx_t beg, idx_t end) { 113 void BitMap::set_range(idx_t beg, idx_t end) {
123 verify_range(beg, end); 114 verify_range(beg, end);
124 115
125 idx_t beg_full_word = word_index_round_up(beg); 116 idx_t beg_full_word = word_index_round_up(beg);
126 idx_t end_full_word = word_index(end); 117 idx_t end_full_word = word_index(end);
183 174
184 // The range includes at least one full word. 175 // The range includes at least one full word.
185 clear_range_within_word(beg, bit_index(beg_full_word)); 176 clear_range_within_word(beg, bit_index(beg_full_word));
186 clear_large_range_of_words(beg_full_word, end_full_word); 177 clear_large_range_of_words(beg_full_word, end_full_word);
187 clear_range_within_word(bit_index(end_full_word), end); 178 clear_range_within_word(bit_index(end_full_word), end);
179 }
180
181 void BitMap::mostly_disjoint_range_union(BitMap* from_bitmap,
182 idx_t from_start_index,
183 idx_t to_start_index,
184 size_t word_num) {
185 // Ensure that the parameters are correct.
186 // These shouldn't be that expensive to check, hence I left them as
187 // guarantees.
188 guarantee(from_bitmap->bit_in_word(from_start_index) == 0,
189 "it should be aligned on a word boundary");
190 guarantee(bit_in_word(to_start_index) == 0,
191 "it should be aligned on a word boundary");
192 guarantee(word_num >= 2, "word_num should be at least 2");
193
194 intptr_t* from = (intptr_t*) from_bitmap->word_addr(from_start_index);
195 intptr_t* to = (intptr_t*) word_addr(to_start_index);
196
197 if (*from != 0) {
198 // if it's 0, then there's no point in doing the CAS
199 while (true) {
200 intptr_t old_value = *to;
201 intptr_t new_value = old_value | *from;
202 intptr_t res = Atomic::cmpxchg_ptr(new_value, to, old_value);
203 if (res == old_value) break;
204 }
205 }
206 ++from;
207 ++to;
208
209 for (size_t i = 0; i < word_num - 2; ++i) {
210 if (*from != 0) {
211 // if it's 0, then there's no point in doing the CAS
212 assert(*to == 0, "nobody else should be writing here");
213 intptr_t new_value = *from;
214 *to = new_value;
215 }
216
217 ++from;
218 ++to;
219 }
220
221 if (*from != 0) {
222 // if it's 0, then there's no point in doing the CAS
223 while (true) {
224 intptr_t old_value = *to;
225 intptr_t new_value = old_value | *from;
226 intptr_t res = Atomic::cmpxchg_ptr(new_value, to, old_value);
227 if (res == old_value) break;
228 }
229 }
230
231 // the -1 is because we didn't advance them after the final CAS
232 assert(from ==
233 (intptr_t*) from_bitmap->word_addr(from_start_index) + word_num - 1,
234 "invariant");
235 assert(to == (intptr_t*) word_addr(to_start_index) + word_num - 1,
236 "invariant");
188 } 237 }
189 238
190 void BitMap::at_put(idx_t offset, bool value) { 239 void BitMap::at_put(idx_t offset, bool value) {
191 if (value) { 240 if (value) {
192 set_bit(offset); 241 set_bit(offset);
280 par_put_range_within_word(bit_index(end_full_word), end, value); 329 par_put_range_within_word(bit_index(end_full_word), end, value);
281 } 330 }
282 331
283 bool BitMap::contains(const BitMap other) const { 332 bool BitMap::contains(const BitMap other) const {
284 assert(size() == other.size(), "must have same size"); 333 assert(size() == other.size(), "must have same size");
285 uintptr_t* dest_map = map(); 334 bm_word_t* dest_map = map();
286 uintptr_t* other_map = other.map(); 335 bm_word_t* other_map = other.map();
287 idx_t size = size_in_words(); 336 idx_t size = size_in_words();
288 for (idx_t index = 0; index < size_in_words(); index++) { 337 for (idx_t index = 0; index < size_in_words(); index++) {
289 uintptr_t word_union = dest_map[index] | other_map[index]; 338 bm_word_t word_union = dest_map[index] | other_map[index];
290 // If this has more bits set than dest_map[index], then other is not a 339 // If this has more bits set than dest_map[index], then other is not a
291 // subset. 340 // subset.
292 if (word_union != dest_map[index]) return false; 341 if (word_union != dest_map[index]) return false;
293 } 342 }
294 return true; 343 return true;
295 } 344 }
296 345
297 bool BitMap::intersects(const BitMap other) const { 346 bool BitMap::intersects(const BitMap other) const {
298 assert(size() == other.size(), "must have same size"); 347 assert(size() == other.size(), "must have same size");
299 uintptr_t* dest_map = map(); 348 bm_word_t* dest_map = map();
300 uintptr_t* other_map = other.map(); 349 bm_word_t* other_map = other.map();
301 idx_t size = size_in_words(); 350 idx_t size = size_in_words();
302 for (idx_t index = 0; index < size_in_words(); index++) { 351 for (idx_t index = 0; index < size_in_words(); index++) {
303 if ((dest_map[index] & other_map[index]) != 0) return true; 352 if ((dest_map[index] & other_map[index]) != 0) return true;
304 } 353 }
305 // Otherwise, no intersection. 354 // Otherwise, no intersection.
306 return false; 355 return false;
307 } 356 }
308 357
309 void BitMap::set_union(BitMap other) { 358 void BitMap::set_union(BitMap other) {
310 assert(size() == other.size(), "must have same size"); 359 assert(size() == other.size(), "must have same size");
311 idx_t* dest_map = map(); 360 bm_word_t* dest_map = map();
312 idx_t* other_map = other.map(); 361 bm_word_t* other_map = other.map();
313 idx_t size = size_in_words(); 362 idx_t size = size_in_words();
314 for (idx_t index = 0; index < size_in_words(); index++) { 363 for (idx_t index = 0; index < size_in_words(); index++) {
315 dest_map[index] = dest_map[index] | other_map[index]; 364 dest_map[index] = dest_map[index] | other_map[index];
316 } 365 }
317 } 366 }
318 367
319 368
320 void BitMap::set_difference(BitMap other) { 369 void BitMap::set_difference(BitMap other) {
321 assert(size() == other.size(), "must have same size"); 370 assert(size() == other.size(), "must have same size");
322 idx_t* dest_map = map(); 371 bm_word_t* dest_map = map();
323 idx_t* other_map = other.map(); 372 bm_word_t* other_map = other.map();
324 idx_t size = size_in_words(); 373 idx_t size = size_in_words();
325 for (idx_t index = 0; index < size_in_words(); index++) { 374 for (idx_t index = 0; index < size_in_words(); index++) {
326 dest_map[index] = dest_map[index] & ~(other_map[index]); 375 dest_map[index] = dest_map[index] & ~(other_map[index]);
327 } 376 }
328 } 377 }
329 378
330 379
331 void BitMap::set_intersection(BitMap other) { 380 void BitMap::set_intersection(BitMap other) {
332 assert(size() == other.size(), "must have same size"); 381 assert(size() == other.size(), "must have same size");
333 idx_t* dest_map = map(); 382 bm_word_t* dest_map = map();
334 idx_t* other_map = other.map(); 383 bm_word_t* other_map = other.map();
335 idx_t size = size_in_words(); 384 idx_t size = size_in_words();
336 for (idx_t index = 0; index < size; index++) { 385 for (idx_t index = 0; index < size; index++) {
337 dest_map[index] = dest_map[index] & other_map[index]; 386 dest_map[index] = dest_map[index] & other_map[index];
338 } 387 }
339 } 388 }
340 389
341 390
391 void BitMap::set_intersection_at_offset(BitMap other, idx_t offset) {
392 assert(other.size() >= offset, "offset not in range");
393 assert(other.size() - offset >= size(), "other not large enough");
394 // XXX Ideally, we would remove this restriction.
395 guarantee((offset % (sizeof(bm_word_t) * BitsPerByte)) == 0,
396 "Only handle aligned cases so far.");
397 bm_word_t* dest_map = map();
398 bm_word_t* other_map = other.map();
399 idx_t offset_word_ind = word_index(offset);
400 idx_t size = size_in_words();
401 for (idx_t index = 0; index < size; index++) {
402 dest_map[index] = dest_map[index] & other_map[offset_word_ind + index];
403 }
404 }
405
342 bool BitMap::set_union_with_result(BitMap other) { 406 bool BitMap::set_union_with_result(BitMap other) {
343 assert(size() == other.size(), "must have same size"); 407 assert(size() == other.size(), "must have same size");
344 bool changed = false; 408 bool changed = false;
345 idx_t* dest_map = map(); 409 bm_word_t* dest_map = map();
346 idx_t* other_map = other.map(); 410 bm_word_t* other_map = other.map();
347 idx_t size = size_in_words(); 411 idx_t size = size_in_words();
348 for (idx_t index = 0; index < size; index++) { 412 for (idx_t index = 0; index < size; index++) {
349 idx_t temp = map(index) | other_map[index]; 413 idx_t temp = map(index) | other_map[index];
350 changed = changed || (temp != map(index)); 414 changed = changed || (temp != map(index));
351 map()[index] = temp; 415 map()[index] = temp;
355 419
356 420
357 bool BitMap::set_difference_with_result(BitMap other) { 421 bool BitMap::set_difference_with_result(BitMap other) {
358 assert(size() == other.size(), "must have same size"); 422 assert(size() == other.size(), "must have same size");
359 bool changed = false; 423 bool changed = false;
360 idx_t* dest_map = map(); 424 bm_word_t* dest_map = map();
361 idx_t* other_map = other.map(); 425 bm_word_t* other_map = other.map();
362 idx_t size = size_in_words(); 426 idx_t size = size_in_words();
363 for (idx_t index = 0; index < size; index++) { 427 for (idx_t index = 0; index < size; index++) {
364 idx_t temp = dest_map[index] & ~(other_map[index]); 428 bm_word_t temp = dest_map[index] & ~(other_map[index]);
365 changed = changed || (temp != dest_map[index]); 429 changed = changed || (temp != dest_map[index]);
366 dest_map[index] = temp; 430 dest_map[index] = temp;
367 } 431 }
368 return changed; 432 return changed;
369 } 433 }
370 434
371 435
372 bool BitMap::set_intersection_with_result(BitMap other) { 436 bool BitMap::set_intersection_with_result(BitMap other) {
373 assert(size() == other.size(), "must have same size"); 437 assert(size() == other.size(), "must have same size");
374 bool changed = false; 438 bool changed = false;
375 idx_t* dest_map = map(); 439 bm_word_t* dest_map = map();
376 idx_t* other_map = other.map(); 440 bm_word_t* other_map = other.map();
377 idx_t size = size_in_words(); 441 idx_t size = size_in_words();
378 for (idx_t index = 0; index < size; index++) { 442 for (idx_t index = 0; index < size; index++) {
379 idx_t orig = dest_map[index]; 443 bm_word_t orig = dest_map[index];
380 idx_t temp = orig & other_map[index]; 444 bm_word_t temp = orig & other_map[index];
381 changed = changed || (temp != orig); 445 changed = changed || (temp != orig);
382 dest_map[index] = temp; 446 dest_map[index] = temp;
383 } 447 }
384 return changed; 448 return changed;
385 } 449 }
386 450
387 451
388 void BitMap::set_from(BitMap other) { 452 void BitMap::set_from(BitMap other) {
389 assert(size() == other.size(), "must have same size"); 453 assert(size() == other.size(), "must have same size");
390 idx_t* dest_map = map(); 454 bm_word_t* dest_map = map();
391 idx_t* other_map = other.map(); 455 bm_word_t* other_map = other.map();
392 idx_t size = size_in_words(); 456 idx_t size = size_in_words();
393 for (idx_t index = 0; index < size; index++) { 457 for (idx_t index = 0; index < size; index++) {
394 dest_map[index] = other_map[index]; 458 dest_map[index] = other_map[index];
395 } 459 }
396 } 460 }
397 461
398 462
399 bool BitMap::is_same(BitMap other) { 463 bool BitMap::is_same(BitMap other) {
400 assert(size() == other.size(), "must have same size"); 464 assert(size() == other.size(), "must have same size");
401 idx_t* dest_map = map(); 465 bm_word_t* dest_map = map();
402 idx_t* other_map = other.map(); 466 bm_word_t* other_map = other.map();
403 idx_t size = size_in_words(); 467 idx_t size = size_in_words();
404 for (idx_t index = 0; index < size; index++) { 468 for (idx_t index = 0; index < size; index++) {
405 if (dest_map[index] != other_map[index]) return false; 469 if (dest_map[index] != other_map[index]) return false;
406 } 470 }
407 return true; 471 return true;
408 } 472 }
409 473
410 bool BitMap::is_full() const { 474 bool BitMap::is_full() const {
411 uintptr_t* word = map(); 475 bm_word_t* word = map();
412 idx_t rest = size(); 476 idx_t rest = size();
413 for (; rest >= (idx_t) BitsPerWord; rest -= BitsPerWord) { 477 for (; rest >= (idx_t) BitsPerWord; rest -= BitsPerWord) {
414 if (*word != (uintptr_t) AllBits) return false; 478 if (*word != (bm_word_t) AllBits) return false;
415 word++; 479 word++;
416 } 480 }
417 return rest == 0 || (*word | ~right_n_bits((int)rest)) == (uintptr_t) AllBits; 481 return rest == 0 || (*word | ~right_n_bits((int)rest)) == (bm_word_t) AllBits;
418 } 482 }
419 483
420 484
421 bool BitMap::is_empty() const { 485 bool BitMap::is_empty() const {
422 uintptr_t* word = map(); 486 bm_word_t* word = map();
423 idx_t rest = size(); 487 idx_t rest = size();
424 for (; rest >= (idx_t) BitsPerWord; rest -= BitsPerWord) { 488 for (; rest >= (idx_t) BitsPerWord; rest -= BitsPerWord) {
425 if (*word != (uintptr_t) NoBits) return false; 489 if (*word != (bm_word_t) NoBits) return false;
426 word++; 490 word++;
427 } 491 }
428 return rest == 0 || (*word & right_n_bits((int)rest)) == (uintptr_t) NoBits; 492 return rest == 0 || (*word & right_n_bits((int)rest)) == (bm_word_t) NoBits;
429 } 493 }
430 494
431 void BitMap::clear_large() { 495 void BitMap::clear_large() {
432 clear_large_range_of_words(0, size_in_words()); 496 clear_large_range_of_words(0, size_in_words());
433 } 497 }
434 498
435 // Note that if the closure itself modifies the bitmap 499 // Note that if the closure itself modifies the bitmap
436 // then modifications in and to the left of the _bit_ being 500 // then modifications in and to the left of the _bit_ being
437 // currently sampled will not be seen. Note also that the 501 // currently sampled will not be seen. Note also that the
438 // interval [leftOffset, rightOffset) is right open. 502 // interval [leftOffset, rightOffset) is right open.
439 void BitMap::iterate(BitMapClosure* blk, idx_t leftOffset, idx_t rightOffset) { 503 bool BitMap::iterate(BitMapClosure* blk, idx_t leftOffset, idx_t rightOffset) {
440 verify_range(leftOffset, rightOffset); 504 verify_range(leftOffset, rightOffset);
441 505
442 idx_t startIndex = word_index(leftOffset); 506 idx_t startIndex = word_index(leftOffset);
443 idx_t endIndex = MIN2(word_index(rightOffset) + 1, size_in_words()); 507 idx_t endIndex = MIN2(word_index(rightOffset) + 1, size_in_words());
444 for (idx_t index = startIndex, offset = leftOffset; 508 for (idx_t index = startIndex, offset = leftOffset;
445 offset < rightOffset && index < endIndex; 509 offset < rightOffset && index < endIndex;
446 offset = (++index) << LogBitsPerWord) { 510 offset = (++index) << LogBitsPerWord) {
447 idx_t rest = map(index) >> (offset & (BitsPerWord - 1)); 511 idx_t rest = map(index) >> (offset & (BitsPerWord - 1));
448 for (; offset < rightOffset && rest != (uintptr_t)NoBits; offset++) { 512 for (; offset < rightOffset && rest != (bm_word_t)NoBits; offset++) {
449 if (rest & 1) { 513 if (rest & 1) {
450 blk->do_bit(offset); 514 if (!blk->do_bit(offset)) return false;
451 // resample at each closure application 515 // resample at each closure application
452 // (see, for instance, CMS bug 4525989) 516 // (see, for instance, CMS bug 4525989)
453 rest = map(index) >> (offset & (BitsPerWord -1)); 517 rest = map(index) >> (offset & (BitsPerWord -1));
454 // XXX debugging: remove
455 // The following assertion assumes that closure application
456 // doesn't clear bits (may not be true in general, e.g. G1).
457 assert(rest & 1,
458 "incorrect shift or closure application can clear bits?");
459 } 518 }
460 rest = rest >> 1; 519 rest = rest >> 1;
461 } 520 }
462 } 521 }
463 } 522 return true;
464 523 }
465 BitMap::idx_t BitMap::get_next_one_offset(idx_t l_offset, 524
466 idx_t r_offset) const { 525 BitMap::idx_t* BitMap::_pop_count_table = NULL;
467 assert(l_offset <= size(), "BitMap index out of bounds"); 526
468 assert(r_offset <= size(), "BitMap index out of bounds"); 527 void BitMap::init_pop_count_table() {
469 assert(l_offset <= r_offset, "l_offset > r_offset ?"); 528 if (_pop_count_table == NULL) {
470 529 BitMap::idx_t *table = NEW_C_HEAP_ARRAY(idx_t, 256);
471 if (l_offset == r_offset) { 530 for (uint i = 0; i < 256; i++) {
472 return l_offset; 531 table[i] = num_set_bits(i);
473 } 532 }
474 idx_t index = word_index(l_offset); 533
475 idx_t r_index = word_index(r_offset-1) + 1; 534 intptr_t res = Atomic::cmpxchg_ptr((intptr_t) table,
476 idx_t res_offset = l_offset; 535 (intptr_t*) &_pop_count_table,
477 536 (intptr_t) NULL_WORD);
478 // check bits including and to the _left_ of offset's position 537 if (res != NULL_WORD) {
479 idx_t pos = bit_in_word(res_offset); 538 guarantee( _pop_count_table == (void*) res, "invariant" );
480 idx_t res = map(index) >> pos; 539 FREE_C_HEAP_ARRAY(bm_word_t, table);
481 if (res != (uintptr_t)NoBits) { 540 }
482 // find the position of the 1-bit 541 }
483 for (; !(res & 1); res_offset++) { 542 }
484 res = res >> 1; 543
485 } 544 BitMap::idx_t BitMap::num_set_bits(bm_word_t w) {
486 assert(res_offset >= l_offset, "just checking"); 545 idx_t bits = 0;
487 return MIN2(res_offset, r_offset); 546
488 } 547 while (w != 0) {
489 // skip over all word length 0-bit runs 548 while ((w & 1) == 0) {
490 for (index++; index < r_index; index++) { 549 w >>= 1;
491 res = map(index); 550 }
492 if (res != (uintptr_t)NoBits) { 551 bits++;
493 // found a 1, return the offset 552 w >>= 1;
494 for (res_offset = index << LogBitsPerWord; !(res & 1); 553 }
495 res_offset++) { 554 return bits;
496 res = res >> 1; 555 }
497 } 556
498 assert(res & 1, "tautology; see loop condition"); 557 BitMap::idx_t BitMap::num_set_bits_from_table(unsigned char c) {
499 assert(res_offset >= l_offset, "just checking"); 558 assert(_pop_count_table != NULL, "precondition");
500 return MIN2(res_offset, r_offset); 559 return _pop_count_table[c];
501 } 560 }
502 } 561
503 return r_offset; 562 BitMap::idx_t BitMap::count_one_bits() const {
504 } 563 init_pop_count_table(); // If necessary.
505 564 idx_t sum = 0;
506 BitMap::idx_t BitMap::get_next_zero_offset(idx_t l_offset, 565 typedef unsigned char uchar;
507 idx_t r_offset) const { 566 for (idx_t i = 0; i < size_in_words(); i++) {
508 assert(l_offset <= size(), "BitMap index out of bounds"); 567 bm_word_t w = map()[i];
509 assert(r_offset <= size(), "BitMap index out of bounds"); 568 for (size_t j = 0; j < sizeof(bm_word_t); j++) {
510 assert(l_offset <= r_offset, "l_offset > r_offset ?"); 569 sum += num_set_bits_from_table(uchar(w & 255));
511 570 w >>= 8;
512 if (l_offset == r_offset) { 571 }
513 return l_offset; 572 }
514 } 573 return sum;
515 idx_t index = word_index(l_offset); 574 }
516 idx_t r_index = word_index(r_offset-1) + 1; 575
517 idx_t res_offset = l_offset;
518
519 // check bits including and to the _left_ of offset's position
520 idx_t pos = res_offset & (BitsPerWord - 1);
521 idx_t res = (map(index) >> pos) | left_n_bits((int)pos);
522
523 if (res != (uintptr_t)AllBits) {
524 // find the position of the 0-bit
525 for (; res & 1; res_offset++) {
526 res = res >> 1;
527 }
528 assert(res_offset >= l_offset, "just checking");
529 return MIN2(res_offset, r_offset);
530 }
531 // skip over all word length 1-bit runs
532 for (index++; index < r_index; index++) {
533 res = map(index);
534 if (res != (uintptr_t)AllBits) {
535 // found a 0, return the offset
536 for (res_offset = index << LogBitsPerWord; res & 1;
537 res_offset++) {
538 res = res >> 1;
539 }
540 assert(!(res & 1), "tautology; see loop condition");
541 assert(res_offset >= l_offset, "just checking");
542 return MIN2(res_offset, r_offset);
543 }
544 }
545 return r_offset;
546 }
547 576
548 #ifndef PRODUCT 577 #ifndef PRODUCT
549 578
550 void BitMap::print_on(outputStream* st) const { 579 void BitMap::print_on(outputStream* st) const {
551 tty->print("Bitmap(%d):", size()); 580 tty->print("Bitmap(%d):", size());
556 } 585 }
557 586
558 #endif 587 #endif
559 588
560 589
561 BitMap2D::BitMap2D(uintptr_t* map, idx_t size_in_slots, idx_t bits_per_slot) 590 BitMap2D::BitMap2D(bm_word_t* map, idx_t size_in_slots, idx_t bits_per_slot)
562 : _bits_per_slot(bits_per_slot) 591 : _bits_per_slot(bits_per_slot)
563 , _map(map, size_in_slots * bits_per_slot) 592 , _map(map, size_in_slots * bits_per_slot)
564 { 593 {
565 } 594 }
566 595