31 // Forward decl;
32 class BitMapClosure;
33
34 // Operations for bitmaps represented as arrays of unsigned integers.
35 // Bit offsets are numbered from 0 to size-1.
36
37 class BitMap VALUE_OBJ_CLASS_SPEC {
38 friend class BitMap2D;
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.
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
119 // Constructs a bitmap with the given map and size.
120 BitMap(bm_word_t* map, idx_t size_in_bits);
121
122 // Constructs an empty bitmap of the given size (that is, this clears the
123 // new bitmap). Allocates the map array in resource area if
124 // "in_resource_area" is true, else in the C heap.
125 BitMap(idx_t size_in_bits, bool in_resource_area = true);
126
127 // Set the map and size.
128 void set_map(bm_word_t* map) { _map = map; }
129 void set_size(idx_t size_in_bits) { _size = size_in_bits; }
130
131 // Allocates necessary data structure, either in the resource area
132 // or in the C heap, as indicated by "in_resource_area."
133 // Preserves state currently in bit map by copying data.
134 // Zeros any newly-addressable bits.
135 // If "in_resource_area" is false, frees the current map.
136 // (Note that this assumes that all calls to "resize" on the same BitMap
137 // use the same value for "in_resource_area".)
|
31 // Forward decl;
32 class BitMapClosure;
33
34 // Operations for bitmaps represented as arrays of unsigned integers.
35 // Bit offsets are numbered from 0 to size-1.
36
37 class BitMap VALUE_OBJ_CLASS_SPEC {
38 friend class BitMap2D;
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 bm_word_t* _map; // First word in bitmap
52 idx_t _size; // Size of bitmap (in bits)
53
54 // Puts the given value at the given offset, using resize() to size
55 // the bitmap appropriately if needed using factor-of-two expansion.
56 void at_put_grow(idx_t index, bool value);
57
58 protected:
59 // Return the position of bit within the word that contains it (e.g., if
60 // bitmap words are 32 bits, return a number 0 <= n <= 31).
61 static idx_t bit_in_word(idx_t bit) { return bit & (BitsPerWord - 1); }
62
63 // Return a mask that will select the specified bit, when applied to the word
64 // containing the bit.
65 static bm_word_t bit_mask(idx_t bit) { return (bm_word_t)1 << bit_in_word(bit); }
66
67 // Return the index of the word containing the specified bit.
68 static idx_t word_index(idx_t bit) { return bit >> LogBitsPerWord; }
69
70 // Return the bit number of the first bit in the specified word.
96 void set_large_range_of_words (idx_t beg, idx_t end);
97 void clear_large_range_of_words (idx_t beg, idx_t end);
98
99 // The index of the first full word in a range.
100 idx_t word_index_round_up(idx_t bit) const;
101
102 // Verification.
103 inline void verify_index(idx_t index) const NOT_DEBUG_RETURN;
104 inline void verify_range(idx_t beg_index, idx_t end_index) const
105 NOT_DEBUG_RETURN;
106
107 // Statistics.
108 static idx_t* _pop_count_table;
109 static void init_pop_count_table();
110 static idx_t num_set_bits(bm_word_t w);
111 static idx_t num_set_bits_from_table(unsigned char c);
112
113 public:
114
115 // Constructs a bitmap with no map, and size 0.
116 BitMap() : _map(NULL), _size(0) {}
117
118 // Constructs a bitmap with the given map and size.
119 BitMap(bm_word_t* map, idx_t size_in_bits);
120
121 // Constructs an empty bitmap of the given size (that is, this clears the
122 // new bitmap). Allocates the map array in resource area if
123 // "in_resource_area" is true, else in the C heap.
124 BitMap(idx_t size_in_bits, bool in_resource_area = true);
125
126 // Set the map and size.
127 void set_map(bm_word_t* map) { _map = map; }
128 void set_size(idx_t size_in_bits) { _size = size_in_bits; }
129
130 // Allocates necessary data structure, either in the resource area
131 // or in the C heap, as indicated by "in_resource_area."
132 // Preserves state currently in bit map by copying data.
133 // Zeros any newly-addressable bits.
134 // If "in_resource_area" is false, frees the current map.
135 // (Note that this assumes that all calls to "resize" on the same BitMap
136 // use the same value for "in_resource_area".)
|