OLD | NEW |
1 // Copyright 2016 the V8 project authors. All rights reserved. | 1 // Copyright 2016 the V8 project authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef V8_SLOT_SET_H | 5 #ifndef V8_SLOT_SET_H |
6 #define V8_SLOT_SET_H | 6 #define V8_SLOT_SET_H |
7 | 7 |
8 #include "src/allocation.h" | 8 #include "src/allocation.h" |
9 #include "src/base/bits.h" | 9 #include "src/base/bits.h" |
10 | 10 |
(...skipping 93 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
104 SlotToIndices(slot_offset, &bucket_index, &cell_index, &bit_index); | 104 SlotToIndices(slot_offset, &bucket_index, &cell_index, &bit_index); |
105 if (bucket[bucket_index] != nullptr) { | 105 if (bucket[bucket_index] != nullptr) { |
106 uint32_t cell = bucket[bucket_index][cell_index]; | 106 uint32_t cell = bucket[bucket_index][cell_index]; |
107 return (cell & (1u << bit_index)) != 0; | 107 return (cell & (1u << bit_index)) != 0; |
108 } | 108 } |
109 return false; | 109 return false; |
110 } | 110 } |
111 | 111 |
112 // Iterate over all slots in the set and for each slot invoke the callback. | 112 // Iterate over all slots in the set and for each slot invoke the callback. |
113 // If the callback returns REMOVE_SLOT then the slot is removed from the set. | 113 // If the callback returns REMOVE_SLOT then the slot is removed from the set. |
| 114 // Returns the new number of slots. |
114 // | 115 // |
115 // Sample usage: | 116 // Sample usage: |
116 // Iterate([](Address slot_address) { | 117 // Iterate([](Address slot_address) { |
117 // if (good(slot_address)) return KEEP_SLOT; | 118 // if (good(slot_address)) return KEEP_SLOT; |
118 // else return REMOVE_SLOT; | 119 // else return REMOVE_SLOT; |
119 // }); | 120 // }); |
120 template <typename Callback> | 121 template <typename Callback> |
121 void Iterate(Callback callback) { | 122 int Iterate(Callback callback) { |
| 123 int new_count = 0; |
122 for (int bucket_index = 0; bucket_index < kBuckets; bucket_index++) { | 124 for (int bucket_index = 0; bucket_index < kBuckets; bucket_index++) { |
123 if (bucket[bucket_index] != nullptr) { | 125 if (bucket[bucket_index] != nullptr) { |
124 bool bucket_is_empty = true; | 126 int in_bucket_count = 0; |
125 uint32_t* current_bucket = bucket[bucket_index]; | 127 uint32_t* current_bucket = bucket[bucket_index]; |
126 int cell_offset = bucket_index * kBitsPerBucket; | 128 int cell_offset = bucket_index * kBitsPerBucket; |
127 for (int i = 0; i < kCellsPerBucket; i++, cell_offset += kBitsPerCell) { | 129 for (int i = 0; i < kCellsPerBucket; i++, cell_offset += kBitsPerCell) { |
128 if (current_bucket[i]) { | 130 if (current_bucket[i]) { |
129 uint32_t cell = current_bucket[i]; | 131 uint32_t cell = current_bucket[i]; |
130 uint32_t old_cell = cell; | 132 uint32_t old_cell = cell; |
131 uint32_t new_cell = cell; | 133 uint32_t new_cell = cell; |
132 while (cell) { | 134 while (cell) { |
133 int bit_offset = base::bits::CountTrailingZeros32(cell); | 135 int bit_offset = base::bits::CountTrailingZeros32(cell); |
134 uint32_t bit_mask = 1u << bit_offset; | 136 uint32_t bit_mask = 1u << bit_offset; |
135 uint32_t slot = (cell_offset + bit_offset) << kPointerSizeLog2; | 137 uint32_t slot = (cell_offset + bit_offset) << kPointerSizeLog2; |
136 if (callback(page_start_ + slot) == KEEP_SLOT) { | 138 if (callback(page_start_ + slot) == KEEP_SLOT) { |
137 bucket_is_empty = false; | 139 ++in_bucket_count; |
138 } else { | 140 } else { |
139 new_cell ^= bit_mask; | 141 new_cell ^= bit_mask; |
140 } | 142 } |
141 cell ^= bit_mask; | 143 cell ^= bit_mask; |
142 } | 144 } |
143 if (old_cell != new_cell) { | 145 if (old_cell != new_cell) { |
144 current_bucket[i] = new_cell; | 146 current_bucket[i] = new_cell; |
145 } | 147 } |
146 } | 148 } |
147 } | 149 } |
148 if (bucket_is_empty) { | 150 if (in_bucket_count == 0) { |
149 ReleaseBucket(bucket_index); | 151 ReleaseBucket(bucket_index); |
150 } | 152 } |
| 153 new_count += in_bucket_count; |
151 } | 154 } |
152 } | 155 } |
| 156 return new_count; |
153 } | 157 } |
154 | 158 |
155 private: | 159 private: |
156 static const int kMaxSlots = (1 << kPageSizeBits) / kPointerSize; | 160 static const int kMaxSlots = (1 << kPageSizeBits) / kPointerSize; |
157 static const int kCellsPerBucket = 32; | 161 static const int kCellsPerBucket = 32; |
158 static const int kCellsPerBucketLog2 = 5; | 162 static const int kCellsPerBucketLog2 = 5; |
159 static const int kBitsPerCell = 32; | 163 static const int kBitsPerCell = 32; |
160 static const int kBitsPerCellLog2 = 5; | 164 static const int kBitsPerCellLog2 = 5; |
161 static const int kBitsPerBucket = kCellsPerBucket * kBitsPerCell; | 165 static const int kBitsPerBucket = kCellsPerBucket * kBitsPerCell; |
162 static const int kBitsPerBucketLog2 = kCellsPerBucketLog2 + kBitsPerCellLog2; | 166 static const int kBitsPerBucketLog2 = kCellsPerBucketLog2 + kBitsPerCellLog2; |
(...skipping 31 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
194 } | 198 } |
195 | 199 |
196 uint32_t* bucket[kBuckets]; | 200 uint32_t* bucket[kBuckets]; |
197 Address page_start_; | 201 Address page_start_; |
198 }; | 202 }; |
199 | 203 |
200 } // namespace internal | 204 } // namespace internal |
201 } // namespace v8 | 205 } // namespace v8 |
202 | 206 |
203 #endif // V8_SLOT_SET_H | 207 #endif // V8_SLOT_SET_H |
OLD | NEW |