diff options
Diffstat (limited to 'deps/v8/src/base/hashmap.h')
-rw-r--r-- | deps/v8/src/base/hashmap.h | 363 |
1 files changed, 363 insertions, 0 deletions
diff --git a/deps/v8/src/base/hashmap.h b/deps/v8/src/base/hashmap.h new file mode 100644 index 0000000000..e3c47de6d7 --- /dev/null +++ b/deps/v8/src/base/hashmap.h @@ -0,0 +1,363 @@ +// Copyright 2012 the V8 project authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +// The reason we write our own hash map instead of using unordered_map in STL, +// is that STL containers use a mutex pool on debug build, which will lead to +// deadlock when we are using async signal handler. + +#ifndef V8_BASE_HASHMAP_H_ +#define V8_BASE_HASHMAP_H_ + +#include <stdlib.h> + +#include "src/base/bits.h" +#include "src/base/logging.h" + +namespace v8 { +namespace base { + +class DefaultAllocationPolicy { + public: + V8_INLINE void* New(size_t size) { return malloc(size); } + V8_INLINE static void Delete(void* p) { free(p); } +}; + +template <class AllocationPolicy> +class TemplateHashMapImpl { + public: + typedef bool (*MatchFun)(void* key1, void* key2); + + // The default capacity. This is used by the call sites which want + // to pass in a non-default AllocationPolicy but want to use the + // default value of capacity specified by the implementation. + static const uint32_t kDefaultHashMapCapacity = 8; + + // initial_capacity is the size of the initial hash map; + // it must be a power of 2 (and thus must not be 0). + TemplateHashMapImpl(MatchFun match, + uint32_t capacity = kDefaultHashMapCapacity, + AllocationPolicy allocator = AllocationPolicy()); + + ~TemplateHashMapImpl(); + + // HashMap entries are (key, value, hash) triplets. + // Some clients may not need to use the value slot + // (e.g. implementers of sets, where the key is the value). + struct Entry { + void* key; + void* value; + uint32_t hash; // The full hash value for key + }; + + // If an entry with matching key is found, returns that entry. + // Otherwise, NULL is returned. + Entry* Lookup(void* key, uint32_t hash) const; + + // If an entry with matching key is found, returns that entry. + // If no matching entry is found, a new entry is inserted with + // corresponding key, key hash, and NULL value. + Entry* LookupOrInsert(void* key, uint32_t hash, + AllocationPolicy allocator = AllocationPolicy()); + + Entry* InsertNew(void* key, uint32_t hash, + AllocationPolicy allocator = AllocationPolicy()); + + // Removes the entry with matching key. + // It returns the value of the deleted entry + // or null if there is no value for such key. + void* Remove(void* key, uint32_t hash); + + // Empties the hash map (occupancy() == 0). + void Clear(); + + // The number of (non-empty) entries in the table. + uint32_t occupancy() const { return occupancy_; } + + // The capacity of the table. The implementation + // makes sure that occupancy is at most 80% of + // the table capacity. + uint32_t capacity() const { return capacity_; } + + // Iteration + // + // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) { + // ... + // } + // + // If entries are inserted during iteration, the effect of + // calling Next() is undefined. + Entry* Start() const; + Entry* Next(Entry* p) const; + + // Some match functions defined for convenience. + static bool PointersMatch(void* key1, void* key2) { return key1 == key2; } + + private: + MatchFun match_; + Entry* map_; + uint32_t capacity_; + uint32_t occupancy_; + + Entry* map_end() const { return map_ + capacity_; } + Entry* Probe(void* key, uint32_t hash) const; + void Initialize(uint32_t capacity, AllocationPolicy allocator); + void Resize(AllocationPolicy allocator); +}; + +typedef TemplateHashMapImpl<DefaultAllocationPolicy> HashMap; + +template <class AllocationPolicy> +TemplateHashMapImpl<AllocationPolicy>::TemplateHashMapImpl( + MatchFun match, uint32_t initial_capacity, AllocationPolicy allocator) { + match_ = match; + Initialize(initial_capacity, allocator); +} + +template <class AllocationPolicy> +TemplateHashMapImpl<AllocationPolicy>::~TemplateHashMapImpl() { + AllocationPolicy::Delete(map_); +} + +template <class AllocationPolicy> +typename TemplateHashMapImpl<AllocationPolicy>::Entry* +TemplateHashMapImpl<AllocationPolicy>::Lookup(void* key, uint32_t hash) const { + Entry* p = Probe(key, hash); + return p->key != NULL ? p : NULL; +} + +template <class AllocationPolicy> +typename TemplateHashMapImpl<AllocationPolicy>::Entry* +TemplateHashMapImpl<AllocationPolicy>::LookupOrInsert( + void* key, uint32_t hash, AllocationPolicy allocator) { + // Find a matching entry. + Entry* p = Probe(key, hash); + if (p->key != NULL) { + return p; + } + + return InsertNew(key, hash, allocator); +} + +template <class AllocationPolicy> +typename TemplateHashMapImpl<AllocationPolicy>::Entry* +TemplateHashMapImpl<AllocationPolicy>::InsertNew(void* key, uint32_t hash, + AllocationPolicy allocator) { + // Find a matching entry. + Entry* p = Probe(key, hash); + DCHECK(p->key == NULL); + + // No entry found; insert one. + p->key = key; + p->value = NULL; + p->hash = hash; + occupancy_++; + + // Grow the map if we reached >= 80% occupancy. + if (occupancy_ + occupancy_ / 4 >= capacity_) { + Resize(allocator); + p = Probe(key, hash); + } + + return p; +} + +template <class AllocationPolicy> +void* TemplateHashMapImpl<AllocationPolicy>::Remove(void* key, uint32_t hash) { + // Lookup the entry for the key to remove. + Entry* p = Probe(key, hash); + if (p->key == NULL) { + // Key not found nothing to remove. + return NULL; + } + + void* value = p->value; + // To remove an entry we need to ensure that it does not create an empty + // entry that will cause the search for another entry to stop too soon. If all + // the entries between the entry to remove and the next empty slot have their + // initial position inside this interval, clearing the entry to remove will + // not break the search. If, while searching for the next empty entry, an + // entry is encountered which does not have its initial position between the + // entry to remove and the position looked at, then this entry can be moved to + // the place of the entry to remove without breaking the search for it. The + // entry made vacant by this move is now the entry to remove and the process + // starts over. + // Algorithm from http://en.wikipedia.org/wiki/Open_addressing. + + // This guarantees loop termination as there is at least one empty entry so + // eventually the removed entry will have an empty entry after it. + DCHECK(occupancy_ < capacity_); + + // p is the candidate entry to clear. q is used to scan forwards. + Entry* q = p; // Start at the entry to remove. + while (true) { + // Move q to the next entry. + q = q + 1; + if (q == map_end()) { + q = map_; + } + + // All entries between p and q have their initial position between p and q + // and the entry p can be cleared without breaking the search for these + // entries. + if (q->key == NULL) { + break; + } + + // Find the initial position for the entry at position q. + Entry* r = map_ + (q->hash & (capacity_ - 1)); + + // If the entry at position q has its initial position outside the range + // between p and q it can be moved forward to position p and will still be + // found. There is now a new candidate entry for clearing. + if ((q > p && (r <= p || r > q)) || (q < p && (r <= p && r > q))) { + *p = *q; + p = q; + } + } + + // Clear the entry which is allowed to en emptied. + p->key = NULL; + occupancy_--; + return value; +} + +template <class AllocationPolicy> +void TemplateHashMapImpl<AllocationPolicy>::Clear() { + // Mark all entries as empty. + const Entry* end = map_end(); + for (Entry* p = map_; p < end; p++) { + p->key = NULL; + } + occupancy_ = 0; +} + +template <class AllocationPolicy> +typename TemplateHashMapImpl<AllocationPolicy>::Entry* +TemplateHashMapImpl<AllocationPolicy>::Start() const { + return Next(map_ - 1); +} + +template <class AllocationPolicy> +typename TemplateHashMapImpl<AllocationPolicy>::Entry* +TemplateHashMapImpl<AllocationPolicy>::Next(Entry* p) const { + const Entry* end = map_end(); + DCHECK(map_ - 1 <= p && p < end); + for (p++; p < end; p++) { + if (p->key != NULL) { + return p; + } + } + return NULL; +} + +template <class AllocationPolicy> +typename TemplateHashMapImpl<AllocationPolicy>::Entry* +TemplateHashMapImpl<AllocationPolicy>::Probe(void* key, uint32_t hash) const { + DCHECK(key != NULL); + + DCHECK(base::bits::IsPowerOfTwo32(capacity_)); + Entry* p = map_ + (hash & (capacity_ - 1)); + const Entry* end = map_end(); + DCHECK(map_ <= p && p < end); + + DCHECK(occupancy_ < capacity_); // Guarantees loop termination. + while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) { + p++; + if (p >= end) { + p = map_; + } + } + + return p; +} + +template <class AllocationPolicy> +void TemplateHashMapImpl<AllocationPolicy>::Initialize( + uint32_t capacity, AllocationPolicy allocator) { + DCHECK(base::bits::IsPowerOfTwo32(capacity)); + map_ = reinterpret_cast<Entry*>(allocator.New(capacity * sizeof(Entry))); + if (map_ == NULL) { + FATAL("Out of memory: HashMap::Initialize"); + return; + } + capacity_ = capacity; + Clear(); +} + +template <class AllocationPolicy> +void TemplateHashMapImpl<AllocationPolicy>::Resize(AllocationPolicy allocator) { + Entry* map = map_; + uint32_t n = occupancy_; + + // Allocate larger map. + Initialize(capacity_ * 2, allocator); + + // Rehash all current entries. + for (Entry* p = map; n > 0; p++) { + if (p->key != NULL) { + Entry* entry = LookupOrInsert(p->key, p->hash, allocator); + entry->value = p->value; + n--; + } + } + + // Delete old map. + AllocationPolicy::Delete(map); +} + +// A hash map for pointer keys and values with an STL-like interface. +template <class Key, class Value, class AllocationPolicy> +class TemplateHashMap : private TemplateHashMapImpl<AllocationPolicy> { + public: + STATIC_ASSERT(sizeof(Key*) == sizeof(void*)); // NOLINT + STATIC_ASSERT(sizeof(Value*) == sizeof(void*)); // NOLINT + struct value_type { + Key* first; + Value* second; + }; + + class Iterator { + public: + Iterator& operator++() { + entry_ = map_->Next(entry_); + return *this; + } + + value_type* operator->() { return reinterpret_cast<value_type*>(entry_); } + bool operator!=(const Iterator& other) { return entry_ != other.entry_; } + + private: + Iterator(const TemplateHashMapImpl<AllocationPolicy>* map, + typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry) + : map_(map), entry_(entry) {} + + const TemplateHashMapImpl<AllocationPolicy>* map_; + typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry_; + + friend class TemplateHashMap; + }; + + TemplateHashMap( + typename TemplateHashMapImpl<AllocationPolicy>::MatchFun match, + AllocationPolicy allocator = AllocationPolicy()) + : TemplateHashMapImpl<AllocationPolicy>( + match, + TemplateHashMapImpl<AllocationPolicy>::kDefaultHashMapCapacity, + allocator) {} + + Iterator begin() const { return Iterator(this, this->Start()); } + Iterator end() const { return Iterator(this, NULL); } + Iterator find(Key* key, bool insert = false, + AllocationPolicy allocator = AllocationPolicy()) { + if (insert) { + return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator)); + } + return Iterator(this, this->Lookup(key, key->Hash())); + } +}; + +} // namespace base +} // namespace v8 + +#endif // V8_BASE_HASHMAP_H_ |