30 // deletions may be done in single-threaded code. This allows us to allow |
30 // deletions may be done in single-threaded code. This allows us to allow |
31 // unsynchronized reads/iterations, as long as expansions caused by |
31 // unsynchronized reads/iterations, as long as expansions caused by |
32 // insertions only enqueue old versions for deletions, but do not delete |
32 // insertions only enqueue old versions for deletions, but do not delete |
33 // old versions synchronously. |
33 // old versions synchronously. |
34 |
34 |
35 |
|
36 class SparsePRTEntry: public CHeapObj { |
35 class SparsePRTEntry: public CHeapObj { |
37 public: |
36 public: |
38 |
|
39 enum SomePublicConstants { |
37 enum SomePublicConstants { |
40 CardsPerEntry = 4, |
38 NullEntry = -1, |
41 NullEntry = -1 |
39 UnrollFactor = 4 |
42 }; |
40 }; |
43 |
|
44 private: |
41 private: |
45 RegionIdx_t _region_ind; |
42 RegionIdx_t _region_ind; |
46 int _next_index; |
43 int _next_index; |
47 CardIdx_t _cards[CardsPerEntry]; |
44 CardIdx_t _cards[1]; |
48 |
45 // WARNING: Don't put any data members beyond this line. Card array has, in fact, variable length. |
49 public: |
46 // It should always be the last data member. |
|
47 public: |
|
48 // Returns the size of the entry, used for entry allocation. |
|
49 static size_t size() { return sizeof(SparsePRTEntry) + sizeof(CardIdx_t) * (cards_num() - 1); } |
|
50 // Returns the size of the card array. |
|
51 static int cards_num() { |
|
52 // The number of cards should be a multiple of 4, because that's our current |
|
53 // unrolling factor. |
|
54 static const int s = MAX2<int>(G1RSetSparseRegionEntries & ~(UnrollFactor - 1), UnrollFactor); |
|
55 return s; |
|
56 } |
50 |
57 |
51 // Set the region_ind to the given value, and delete all cards. |
58 // Set the region_ind to the given value, and delete all cards. |
52 inline void init(RegionIdx_t region_ind); |
59 inline void init(RegionIdx_t region_ind); |
53 |
60 |
54 RegionIdx_t r_ind() const { return _region_ind; } |
61 RegionIdx_t r_ind() const { return _region_ind; } |
132 // overflow the entry for the region. The caller must transfer these |
139 // overflow the entry for the region. The caller must transfer these |
133 // entries to a larger-capacity representation. |
140 // entries to a larger-capacity representation. |
134 bool add_card(RegionIdx_t region_id, CardIdx_t card_index); |
141 bool add_card(RegionIdx_t region_id, CardIdx_t card_index); |
135 |
142 |
136 bool get_cards(RegionIdx_t region_id, CardIdx_t* cards); |
143 bool get_cards(RegionIdx_t region_id, CardIdx_t* cards); |
|
144 |
137 bool delete_entry(RegionIdx_t region_id); |
145 bool delete_entry(RegionIdx_t region_id); |
138 |
146 |
139 bool contains_card(RegionIdx_t region_id, CardIdx_t card_index) const; |
147 bool contains_card(RegionIdx_t region_id, CardIdx_t card_index) const; |
140 |
148 |
141 void add_entry(SparsePRTEntry* e); |
149 void add_entry(SparsePRTEntry* e); |
|
150 |
|
151 SparsePRTEntry* get_entry(RegionIdx_t region_id); |
142 |
152 |
143 void clear(); |
153 void clear(); |
144 |
154 |
145 size_t capacity() const { return _capacity; } |
155 size_t capacity() const { return _capacity; } |
146 size_t capacity_mask() const { return _capacity_mask; } |
156 size_t capacity_mask() const { return _capacity_mask; } |
147 size_t occupied_entries() const { return _occupied_entries; } |
157 size_t occupied_entries() const { return _occupied_entries; } |
148 size_t occupied_cards() const { return _occupied_cards; } |
158 size_t occupied_cards() const { return _occupied_cards; } |
149 size_t mem_size() const; |
159 size_t mem_size() const; |
150 |
160 |
151 SparsePRTEntry* entry(int i) const { return &_entries[i]; } |
161 SparsePRTEntry* entry(int i) const { return (SparsePRTEntry*)((char*)_entries + SparsePRTEntry::size() * i); } |
152 |
162 |
153 void print(); |
163 void print(); |
154 }; |
164 }; |
155 |
165 |
156 // ValueObj because will be embedded in HRRS iterator. |
166 // ValueObj because will be embedded in HRRS iterator. |
157 class RSHashTableIter VALUE_OBJ_CLASS_SPEC { |
167 class RSHashTableIter VALUE_OBJ_CLASS_SPEC { |
158 int _tbl_ind; // [-1, 0.._rsht->_capacity) |
168 int _tbl_ind; // [-1, 0.._rsht->_capacity) |
159 int _bl_ind; // [-1, 0.._rsht->_capacity) |
169 int _bl_ind; // [-1, 0.._rsht->_capacity) |
160 short _card_ind; // [0..CardsPerEntry) |
170 short _card_ind; // [0..SparsePRTEntry::cards_num()) |
161 RSHashTable* _rsht; |
171 RSHashTable* _rsht; |
162 size_t _heap_bot_card_ind; |
172 size_t _heap_bot_card_ind; |
163 |
173 |
164 // If the bucket list pointed to by _bl_ind contains a card, sets |
174 // If the bucket list pointed to by _bl_ind contains a card, sets |
165 // _bl_ind to the index of that entry, and returns the card. |
175 // _bl_ind to the index of that entry, and returns the card. |
174 |
184 |
175 public: |
185 public: |
176 RSHashTableIter(size_t heap_bot_card_ind) : |
186 RSHashTableIter(size_t heap_bot_card_ind) : |
177 _tbl_ind(RSHashTable::NullEntry), |
187 _tbl_ind(RSHashTable::NullEntry), |
178 _bl_ind(RSHashTable::NullEntry), |
188 _bl_ind(RSHashTable::NullEntry), |
179 _card_ind((SparsePRTEntry::CardsPerEntry-1)), |
189 _card_ind((SparsePRTEntry::cards_num() - 1)), |
180 _rsht(NULL), |
190 _rsht(NULL), |
181 _heap_bot_card_ind(heap_bot_card_ind) |
191 _heap_bot_card_ind(heap_bot_card_ind) |
182 {} |
192 {} |
183 |
193 |
184 void init(RSHashTable* rsht) { |
194 void init(RSHashTable* rsht) { |
185 _rsht = rsht; |
195 _rsht = rsht; |
186 _tbl_ind = -1; // So that first increment gets to 0. |
196 _tbl_ind = -1; // So that first increment gets to 0. |
187 _bl_ind = RSHashTable::NullEntry; |
197 _bl_ind = RSHashTable::NullEntry; |
188 _card_ind = (SparsePRTEntry::CardsPerEntry-1); |
198 _card_ind = (SparsePRTEntry::cards_num() - 1); |
189 } |
199 } |
190 |
200 |
191 bool has_next(size_t& card_index); |
201 bool has_next(size_t& card_index); |
192 }; |
202 }; |
193 |
203 |
239 // entries to a larger-capacity representation. |
249 // entries to a larger-capacity representation. |
240 bool add_card(RegionIdx_t region_id, CardIdx_t card_index); |
250 bool add_card(RegionIdx_t region_id, CardIdx_t card_index); |
241 |
251 |
242 // If the table hold an entry for "region_ind", Copies its |
252 // If the table hold an entry for "region_ind", Copies its |
243 // cards into "cards", which must be an array of length at least |
253 // cards into "cards", which must be an array of length at least |
244 // "CardsPerEntry", and returns "true"; otherwise, returns "false". |
254 // "SparePRTEntry::cards_num()", and returns "true"; otherwise, |
|
255 // returns "false". |
245 bool get_cards(RegionIdx_t region_ind, CardIdx_t* cards); |
256 bool get_cards(RegionIdx_t region_ind, CardIdx_t* cards); |
|
257 |
|
258 // Return the pointer to the entry associated with the given region. |
|
259 SparsePRTEntry* get_entry(RegionIdx_t region_ind); |
246 |
260 |
247 // If there is an entry for "region_ind", removes it and return "true"; |
261 // If there is an entry for "region_ind", removes it and return "true"; |
248 // otherwise returns "false." |
262 // otherwise returns "false." |
249 bool delete_entry(RegionIdx_t region_ind); |
263 bool delete_entry(RegionIdx_t region_ind); |
250 |
264 |