39
40 public:
41 typedef size_t idx_t; // Type used for bit and word indices.
42 typedef uintptr_t bm_word_t; // Element type of array that represents
43 // the bitmap.
44
45 // Hints for range sizes.
46 typedef enum {
47 unknown_range, small_range, large_range
48 } RangeSizeHint;
49
50 private:
51 ArrayAllocator<bm_word_t, mtInternal> _map_allocator;
52 bm_word_t* _map; // First word in bitmap
53 idx_t _size; // Size of bitmap (in bits)
54
55 // Puts the given value at the given offset, using resize() to size
56 // the bitmap appropriately if needed using factor-of-two expansion.
57 void at_put_grow(idx_t index, bool value);
58
59 protected:
60 // Return the position of bit within the word that contains it (e.g., if
61 // bitmap words are 32 bits, return a number 0 <= n <= 31).
62 static idx_t bit_in_word(idx_t bit) { return bit & (BitsPerWord - 1); }
63
64 // Return a mask that will select the specified bit, when applied to the word
65 // containing the bit.
66 static bm_word_t bit_mask(idx_t bit) { return (bm_word_t)1 << bit_in_word(bit); }
67
68 // Return the index of the word containing the specified bit.
69 static idx_t word_index(idx_t bit) { return bit >> LogBitsPerWord; }
70
71 // Return the bit number of the first bit in the specified word.
72 static idx_t bit_index(idx_t word) { return word << LogBitsPerWord; }
73
74 // Return the array of bitmap words, or a specific word from it.
75 bm_word_t* map() const { return _map; }
76 bm_word_t map(idx_t word) const { return _map[word]; }
77
78 // Return a pointer to the word containing the specified bit.
79 bm_word_t* word_addr(idx_t bit) const { return map() + word_index(bit); }
80
81 // Set a word to a specified value or to all ones; clear a word.
82 void set_word (idx_t word, bm_word_t val) { _map[word] = val; }
83 void set_word (idx_t word) { set_word(word, ~(uintptr_t)0); }
84 void clear_word(idx_t word) { _map[word] = 0; }
85
86 // Utilities for ranges of bits. Ranges are half-open [beg, end).
87
88 // Ranges within a single word.
89 bm_word_t inverted_bit_mask_for_range(idx_t beg, idx_t end) const;
90 void set_range_within_word (idx_t beg, idx_t end);
91 void clear_range_within_word (idx_t beg, idx_t end);
92 void par_put_range_within_word (idx_t beg, idx_t end, bool value);
93
94 // Ranges spanning entire words.
95 void set_range_of_words (idx_t beg, idx_t end);
96 void clear_range_of_words (idx_t beg, idx_t end);
97 void set_large_range_of_words (idx_t beg, idx_t end);
98 void clear_large_range_of_words (idx_t beg, idx_t end);
99
100 // The index of the first full word in a range.
101 idx_t word_index_round_up(idx_t bit) const;
102
103 // Verification.
104 inline void verify_index(idx_t index) const NOT_DEBUG_RETURN;
105 inline void verify_range(idx_t beg_index, idx_t end_index) const
106 NOT_DEBUG_RETURN;
107
108 // Statistics.
109 static idx_t* _pop_count_table;
110 static void init_pop_count_table();
111 static idx_t num_set_bits(bm_word_t w);
112 static idx_t num_set_bits_from_table(unsigned char c);
113
114 public:
115
116 // Constructs a bitmap with no map, and size 0.
117 BitMap() : _map(NULL), _size(0), _map_allocator(false) {}
118
|
39
40 public:
41 typedef size_t idx_t; // Type used for bit and word indices.
42 typedef uintptr_t bm_word_t; // Element type of array that represents
43 // the bitmap.
44
45 // Hints for range sizes.
46 typedef enum {
47 unknown_range, small_range, large_range
48 } RangeSizeHint;
49
50 private:
51 ArrayAllocator<bm_word_t, mtInternal> _map_allocator;
52 bm_word_t* _map; // First word in bitmap
53 idx_t _size; // Size of bitmap (in bits)
54
55 // Puts the given value at the given offset, using resize() to size
56 // the bitmap appropriately if needed using factor-of-two expansion.
57 void at_put_grow(idx_t index, bool value);
58
59 // Threshold for performing small range operation, even when large range
60 // operation was requested. Measured in words.
61 static const size_t small_range_words = 32;
62
63 protected:
64 // Return the position of bit within the word that contains it (e.g., if
65 // bitmap words are 32 bits, return a number 0 <= n <= 31).
66 static idx_t bit_in_word(idx_t bit) { return bit & (BitsPerWord - 1); }
67
68 // Return a mask that will select the specified bit, when applied to the word
69 // containing the bit.
70 static bm_word_t bit_mask(idx_t bit) { return (bm_word_t)1 << bit_in_word(bit); }
71
72 // Return the index of the word containing the specified bit.
73 static idx_t word_index(idx_t bit) { return bit >> LogBitsPerWord; }
74
75 // Return the bit number of the first bit in the specified word.
76 static idx_t bit_index(idx_t word) { return word << LogBitsPerWord; }
77
78 // Return the array of bitmap words, or a specific word from it.
79 bm_word_t* map() const { return _map; }
80 bm_word_t map(idx_t word) const { return _map[word]; }
81
82 // Return a pointer to the word containing the specified bit.
83 bm_word_t* word_addr(idx_t bit) const { return map() + word_index(bit); }
84
85 // Set a word to a specified value or to all ones; clear a word.
86 void set_word (idx_t word, bm_word_t val) { _map[word] = val; }
87 void set_word (idx_t word) { set_word(word, ~(uintptr_t)0); }
88 void clear_word(idx_t word) { _map[word] = 0; }
89
90 // Utilities for ranges of bits. Ranges are half-open [beg, end).
91
92 // Ranges within a single word.
93 bm_word_t inverted_bit_mask_for_range(idx_t beg, idx_t end) const;
94 void set_range_within_word (idx_t beg, idx_t end);
95 void clear_range_within_word (idx_t beg, idx_t end);
96 void par_put_range_within_word (idx_t beg, idx_t end, bool value);
97
98 // Ranges spanning entire words.
99 void set_range_of_words (idx_t beg, idx_t end);
100 void clear_range_of_words (idx_t beg, idx_t end);
101 void set_large_range_of_words (idx_t beg, idx_t end);
102 void clear_large_range_of_words (idx_t beg, idx_t end);
103
104 static bool is_small_range_of_words(idx_t beg_full_word, idx_t end_full_word);
105
106 // The index of the first full word in a range.
107 idx_t word_index_round_up(idx_t bit) const;
108
109 // Verification.
110 inline void verify_index(idx_t index) const NOT_DEBUG_RETURN;
111 inline void verify_range(idx_t beg_index, idx_t end_index) const
112 NOT_DEBUG_RETURN;
113
114 // Statistics.
115 static idx_t* _pop_count_table;
116 static void init_pop_count_table();
117 static idx_t num_set_bits(bm_word_t w);
118 static idx_t num_set_bits_from_table(unsigned char c);
119
120 public:
121
122 // Constructs a bitmap with no map, and size 0.
123 BitMap() : _map(NULL), _size(0), _map_allocator(false) {}
124
|