9 #ifndef V8_BASE_HASHMAP_H_ 10 #define V8_BASE_HASHMAP_H_ 14 #include "src/base/bits.h" 15 #include "src/base/hashmap-entry.h" 16 #include "src/base/logging.h" 23 V8_INLINE
void* New(
size_t size) {
return malloc(size); }
24 V8_INLINE
static void Delete(
void* p) { free(p); }
27 template <
typename Key,
typename Value,
class MatchFun,
class AllocationPolicy>
35 static const uint32_t kDefaultHashMapCapacity = 8;
40 MatchFun match = MatchFun(),
41 AllocationPolicy allocator = AllocationPolicy());
45 AllocationPolicy>* original,
46 AllocationPolicy allocator = AllocationPolicy());
58 AllocationPolicy allocator = AllocationPolicy());
63 template <
typename Func>
65 AllocationPolicy allocator = AllocationPolicy());
68 AllocationPolicy allocator = AllocationPolicy());
80 AllocationPolicy::Delete(map_);
87 uint32_t occupancy()
const {
return occupancy_; }
92 uint32_t capacity()
const {
return capacity_; }
102 Entry* Start()
const;
105 void Reset(AllocationPolicy allocator) {
106 Initialize(capacity_, allocator);
111 void Initialize(
uint32_t capacity, AllocationPolicy allocator);
121 Entry* map_end()
const {
return map_ + capacity_; }
123 Entry* FillEmptyEntry(
Entry* entry,
const Key& key,
const Value& value,
125 AllocationPolicy allocator = AllocationPolicy());
126 void Resize(AllocationPolicy allocator);
130 template <
typename Key,
typename Value,
typename MatchFun,
131 class AllocationPolicy>
134 AllocationPolicy allocator)
136 Initialize(initial_capacity, allocator);
139 template <
typename Key,
typename Value,
typename MatchFun,
140 class AllocationPolicy>
141 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::
142 TemplateHashMapImpl(
const TemplateHashMapImpl<Key,
Value, MatchFun,
143 AllocationPolicy>* original,
144 AllocationPolicy allocator)
145 : capacity_(original->capacity_),
146 occupancy_(original->occupancy_),
147 match_(original->match_) {
148 map_ =
reinterpret_cast<Entry*
>(allocator.New(capacity_ *
sizeof(Entry)));
149 memcpy(map_, original->map_, capacity_ *
sizeof(Entry));
152 template <
typename Key,
typename Value,
typename MatchFun,
153 class AllocationPolicy>
154 TemplateHashMapImpl<Key,
Value, MatchFun,
155 AllocationPolicy>::~TemplateHashMapImpl() {
156 AllocationPolicy::Delete(map_);
159 template <
typename Key,
typename Value,
typename MatchFun,
160 class AllocationPolicy>
161 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
162 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Lookup(
163 const Key& key,
uint32_t hash)
const {
164 Entry* entry = Probe(key, hash);
165 return entry->exists() ? entry :
nullptr;
168 template <
typename Key,
typename Value,
typename MatchFun,
169 class AllocationPolicy>
170 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
171 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::LookupOrInsert(
172 const Key& key,
uint32_t hash, AllocationPolicy allocator) {
173 return LookupOrInsert(key, hash, []() {
return Value(); }, allocator);
176 template <
typename Key,
typename Value,
typename MatchFun,
177 class AllocationPolicy>
178 template <
typename Func>
179 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
180 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::LookupOrInsert(
181 const Key& key,
uint32_t hash,
const Func& value_func,
182 AllocationPolicy allocator) {
184 Entry* entry = Probe(key, hash);
185 if (entry->exists()) {
189 return FillEmptyEntry(entry, key, value_func(), hash, allocator);
192 template <
typename Key,
typename Value,
typename MatchFun,
193 class AllocationPolicy>
194 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
195 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::InsertNew(
196 const Key& key,
uint32_t hash, AllocationPolicy allocator) {
197 Entry* entry = Probe(key, hash);
198 return FillEmptyEntry(entry, key,
Value(), hash, allocator);
201 template <
typename Key,
typename Value,
typename MatchFun,
202 class AllocationPolicy>
203 Value TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Remove(
206 Entry* p = Probe(key, hash);
212 Value value = p->value;
227 DCHECK(occupancy_ < capacity_);
234 if (q == map_end()) {
246 Entry* r = map_ + (q->hash & (capacity_ - 1));
251 if ((q > p && (r <= p || r > q)) || (q < p && (r <= p && r > q))) {
263 template <
typename Key,
typename Value,
typename MatchFun,
264 class AllocationPolicy>
265 void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Clear() {
267 for (
size_t i = 0;
i < capacity_; ++
i) {
273 template <
typename Key,
typename Value,
typename MatchFun,
274 class AllocationPolicy>
275 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
276 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Start()
const {
277 return Next(map_ - 1);
280 template <
typename Key,
typename Value,
typename MatchFun,
281 class AllocationPolicy>
282 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
283 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Next(
284 Entry* entry)
const {
285 const Entry* end = map_end();
286 DCHECK(map_ - 1 <= entry && entry < end);
287 for (entry++; entry < end; entry++) {
288 if (entry->exists()) {
295 template <
typename Key,
typename Value,
typename MatchFun,
296 class AllocationPolicy>
297 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
298 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Probe(
299 const Key& key,
uint32_t hash)
const {
300 DCHECK(base::bits::IsPowerOfTwo(capacity_));
301 size_t i = hash & (capacity_ - 1);
302 DCHECK(
i < capacity_);
304 DCHECK(occupancy_ < capacity_);
305 while (map_[
i].exists() && !match_(hash, map_[
i].hash, key, map_[
i].key)) {
306 i = (
i + 1) & (capacity_ - 1);
312 template <
typename Key,
typename Value,
typename MatchFun,
313 class AllocationPolicy>
314 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
315 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::FillEmptyEntry(
316 Entry* entry,
const Key& key,
const Value& value,
uint32_t hash,
317 AllocationPolicy allocator) {
318 DCHECK(!entry->exists());
320 new (entry) Entry(key, value, hash);
324 if (occupancy_ + occupancy_ / 4 >= capacity_) {
326 entry = Probe(key, hash);
332 template <
typename Key,
typename Value,
typename MatchFun,
333 class AllocationPolicy>
334 void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Initialize(
335 uint32_t capacity, AllocationPolicy allocator) {
336 DCHECK(base::bits::IsPowerOfTwo(capacity));
337 map_ =
reinterpret_cast<Entry*
>(allocator.New(capacity *
sizeof(Entry)));
338 if (map_ ==
nullptr) {
339 FATAL(
"Out of memory: HashMap::Initialize");
342 capacity_ = capacity;
346 template <
typename Key,
typename Value,
typename MatchFun,
347 class AllocationPolicy>
348 void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Resize(
349 AllocationPolicy allocator) {
354 Initialize(capacity_ * 2, allocator);
357 for (Entry* entry = map; n > 0; entry++) {
358 if (entry->exists()) {
359 Entry* new_entry = Probe(entry->key, entry->hash);
360 new_entry = FillEmptyEntry(new_entry, entry->key, entry->value,
361 entry->hash, allocator);
367 AllocationPolicy::Delete(map);
372 template <
typename Key,
typename MatchFun>
377 const Key& key2)
const {
378 return hash1 == hash2 && match_(key1, key2);
386 template <
typename AllocationPolicy>
390 HashEqualityThenKeyMatcher<void*, bool (*)(void*, void*)>,
398 typedef bool (*MatchFun)(
void*,
void*);
401 MatchFun match,
uint32_t capacity = Base::kDefaultHashMapCapacity,
402 AllocationPolicy allocator = AllocationPolicy())
408 AllocationPolicy allocator = AllocationPolicy())
409 :
Base(original, allocator) {}
416 CustomMatcherHashMap;
419 template <
typename Key>
422 const Key& key2)
const {
428 template <
typename AllocationPolicy>
438 AllocationPolicy allocator = AllocationPolicy())
445 template <
class Key,
class Value,
class MatchFun,
class AllocationPolicy>
448 HashEqualityThenKeyMatcher<void*, MatchFun>,
456 STATIC_ASSERT(
sizeof(Key*) ==
sizeof(
void*));
457 STATIC_ASSERT(
sizeof(
Value*) ==
sizeof(
void*));
466 entry_ = map_->Next(entry_);
471 bool operator!=(
const Iterator& other) {
return entry_ != other.entry_; }
475 : map_(map), entry_(entry) {}
484 AllocationPolicy allocator = AllocationPolicy())
485 :
Base(
Base::kDefaultHashMapCapacity,
488 Iterator begin()
const {
return Iterator(
this, this->Start()); }
489 Iterator end()
const {
return Iterator(
this,
nullptr); }
490 Iterator find(Key* key,
bool insert =
false,
491 AllocationPolicy allocator = AllocationPolicy()) {
493 return Iterator(
this, this->LookupOrInsert(key, key->Hash(), allocator));
495 return Iterator(
this, this->Lookup(key, key->Hash()));
502 #endif // V8_BASE_HASHMAP_H_