diff options
Diffstat (limited to 'src/3rdparty/v8/src/hashmap.h')
-rw-r--r-- | src/3rdparty/v8/src/hashmap.h | 100 |
1 files changed, 60 insertions, 40 deletions
diff --git a/src/3rdparty/v8/src/hashmap.h b/src/3rdparty/v8/src/hashmap.h index 91843b8..11f6ace 100644 --- a/src/3rdparty/v8/src/hashmap.h +++ b/src/3rdparty/v8/src/hashmap.h @@ -40,9 +40,16 @@ 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 initial_capacity = 8); + TemplateHashMapImpl(MatchFun match, + uint32_t capacity = kDefaultHashMapCapacity, + AllocationPolicy allocator = AllocationPolicy()); ~TemplateHashMapImpl(); @@ -52,7 +59,8 @@ class TemplateHashMapImpl { struct Entry { void* key; void* value; - uint32_t hash; // the full hash value for key + uint32_t hash; // The full hash value for key + int order; // If you never remove entries this is the insertion order. }; // If an entry with matching key is found, Lookup() @@ -60,7 +68,8 @@ class TemplateHashMapImpl { // but insert is set, a new entry is inserted with // corresponding key, key hash, and NULL value. // Otherwise, NULL is returned. - Entry* Lookup(void* key, uint32_t hash, bool insert); + Entry* Lookup(void* key, uint32_t hash, bool insert, + AllocationPolicy allocator = AllocationPolicy()); // Removes the entry with matching key. // It returns the value of the deleted entry @@ -97,29 +106,30 @@ class TemplateHashMapImpl { Entry* map_end() const { return map_ + capacity_; } Entry* Probe(void* key, uint32_t hash); - void Initialize(uint32_t capacity); - void Resize(); + void Initialize(uint32_t capacity, AllocationPolicy allocator); + void Resize(AllocationPolicy allocator); }; typedef TemplateHashMapImpl<FreeStoreAllocationPolicy> HashMap; -template<class P> -TemplateHashMapImpl<P>::TemplateHashMapImpl(MatchFun match, - uint32_t initial_capacity) { +template<class AllocationPolicy> +TemplateHashMapImpl<AllocationPolicy>::TemplateHashMapImpl( + MatchFun match, uint32_t initial_capacity, AllocationPolicy allocator) { match_ = match; - Initialize(initial_capacity); + Initialize(initial_capacity, allocator); } -template<class P> -TemplateHashMapImpl<P>::~TemplateHashMapImpl() { - P::Delete(map_); +template<class AllocationPolicy> +TemplateHashMapImpl<AllocationPolicy>::~TemplateHashMapImpl() { + AllocationPolicy::Delete(map_); } -template<class P> -typename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Lookup( - void* key, uint32_t hash, bool insert) { +template<class AllocationPolicy> +typename TemplateHashMapImpl<AllocationPolicy>::Entry* +TemplateHashMapImpl<AllocationPolicy>::Lookup( + void* key, uint32_t hash, bool insert, AllocationPolicy allocator) { // Find a matching entry. Entry* p = Probe(key, hash); if (p->key != NULL) { @@ -131,11 +141,12 @@ typename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Lookup( p->key = key; p->value = NULL; p->hash = hash; + p->order = occupancy_; occupancy_++; // Grow the map if we reached >= 80% occupancy. if (occupancy_ + occupancy_/4 >= capacity_) { - Resize(); + Resize(allocator); p = Probe(key, hash); } @@ -147,8 +158,8 @@ typename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Lookup( } -template<class P> -void* TemplateHashMapImpl<P>::Remove(void* key, uint32_t hash) { +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) { @@ -209,8 +220,8 @@ void* TemplateHashMapImpl<P>::Remove(void* key, uint32_t hash) { } -template<class P> -void TemplateHashMapImpl<P>::Clear() { +template<class AllocationPolicy> +void TemplateHashMapImpl<AllocationPolicy>::Clear() { // Mark all entries as empty. const Entry* end = map_end(); for (Entry* p = map_; p < end; p++) { @@ -220,15 +231,16 @@ void TemplateHashMapImpl<P>::Clear() { } -template<class P> -typename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Start() const { +template<class AllocationPolicy> +typename TemplateHashMapImpl<AllocationPolicy>::Entry* + TemplateHashMapImpl<AllocationPolicy>::Start() const { return Next(map_ - 1); } -template<class P> -typename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Next(Entry* p) - const { +template<class AllocationPolicy> +typename TemplateHashMapImpl<AllocationPolicy>::Entry* + TemplateHashMapImpl<AllocationPolicy>::Next(Entry* p) const { const Entry* end = map_end(); ASSERT(map_ - 1 <= p && p < end); for (p++; p < end; p++) { @@ -240,9 +252,9 @@ typename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Next(Entry* p) } -template<class P> -typename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Probe(void* key, - uint32_t hash) { +template<class AllocationPolicy> +typename TemplateHashMapImpl<AllocationPolicy>::Entry* + TemplateHashMapImpl<AllocationPolicy>::Probe(void* key, uint32_t hash) { ASSERT(key != NULL); ASSERT(IsPowerOf2(capacity_)); @@ -262,10 +274,11 @@ typename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Probe(void* key, } -template<class P> -void TemplateHashMapImpl<P>::Initialize(uint32_t capacity) { +template<class AllocationPolicy> +void TemplateHashMapImpl<AllocationPolicy>::Initialize( + uint32_t capacity, AllocationPolicy allocator) { ASSERT(IsPowerOf2(capacity)); - map_ = reinterpret_cast<Entry*>(P::New(capacity * sizeof(Entry))); + map_ = reinterpret_cast<Entry*>(allocator.New(capacity * sizeof(Entry))); if (map_ == NULL) { v8::internal::FatalProcessOutOfMemory("HashMap::Initialize"); return; @@ -275,24 +288,26 @@ void TemplateHashMapImpl<P>::Initialize(uint32_t capacity) { } -template<class P> -void TemplateHashMapImpl<P>::Resize() { +template<class AllocationPolicy> +void TemplateHashMapImpl<AllocationPolicy>::Resize(AllocationPolicy allocator) { Entry* map = map_; uint32_t n = occupancy_; // Allocate larger map. - Initialize(capacity_ * 2); + Initialize(capacity_ * 2, allocator); // Rehash all current entries. for (Entry* p = map; n > 0; p++) { if (p->key != NULL) { - Lookup(p->key, p->hash, true)->value = p->value; + Entry* entry = Lookup(p->key, p->hash, true, allocator); + entry->value = p->value; + entry->order = p->order; n--; } } // Delete old map. - P::Delete(map); + AllocationPolicy::Delete(map); } @@ -329,13 +344,18 @@ class TemplateHashMap: private TemplateHashMapImpl<AllocationPolicy> { }; TemplateHashMap( - typename TemplateHashMapImpl<AllocationPolicy>::MatchFun match) - : TemplateHashMapImpl<AllocationPolicy>(match) { } + 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) { - return Iterator(this, this->Lookup(key, key->Hash(), insert)); + Iterator find(Key* key, bool insert = false, + AllocationPolicy allocator = AllocationPolicy()) { + return Iterator(this, this->Lookup(key, key->Hash(), insert, allocator)); } }; |