1ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org// Copyright 2012 the V8 project authors. All rights reserved. 23484964a86451e86dcf04be9bd8c0d76ee04f081rossberg@chromium.org// Use of this source code is governed by a BSD-style license that can be 33484964a86451e86dcf04be9bd8c0d76ee04f081rossberg@chromium.org// found in the LICENSE file. 443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen#ifndef V8_HASHMAP_H_ 643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen#define V8_HASHMAP_H_ 743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 8196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org#include "src/allocation.h" 921d700eedcdd6570eff22ece724b63a5eefe78cbmachenbach@chromium.org#include "src/base/bits.h" 105de0074a922429f5e0ec2cf140c2d2989bf88140yangguo@chromium.org#include "src/base/logging.h" 11196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org#include "src/utils.h" 12fb144a0716afe7ab8bf245f2391a9e53b3db3c89fschneider@chromium.org 1371affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.orgnamespace v8 { 1471affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.orgnamespace internal { 1543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 16ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.orgtemplate<class AllocationPolicy> 172c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.orgclass TemplateHashMapImpl { 1843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen public: 1943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen typedef bool (*MatchFun) (void* key1, void* key2); 2043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 21400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org // The default capacity. This is used by the call sites which want 22400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org // to pass in a non-default AllocationPolicy but want to use the 23400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org // default value of capacity specified by the implementation. 24400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org static const uint32_t kDefaultHashMapCapacity = 8; 25400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org 2643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // initial_capacity is the size of the initial hash map; 2743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // it must be a power of 2 (and thus must not be 0). 28400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org TemplateHashMapImpl(MatchFun match, 29400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org uint32_t capacity = kDefaultHashMapCapacity, 30400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy allocator = AllocationPolicy()); 3143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 322c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org ~TemplateHashMapImpl(); 3343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 343291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // HashMap entries are (key, value, hash) triplets. 3543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // Some clients may not need to use the value slot 3643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // (e.g. implementers of sets, where the key is the value). 3743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen struct Entry { 3843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen void* key; 3943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen void* value; 4046839fbbdee40a3d2d924e8b5b13c4139b0b24f2yangguo@chromium.org uint32_t hash; // The full hash value for key 4146839fbbdee40a3d2d924e8b5b13c4139b0b24f2yangguo@chromium.org int order; // If you never remove entries this is the insertion order. 4243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen }; 4343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 4443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // If an entry with matching key is found, Lookup() 4543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // returns that entry. If no matching entry is found, 4643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // but insert is set, a new entry is inserted with 4743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // corresponding key, key hash, and NULL value. 4843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // Otherwise, NULL is returned. 49400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org Entry* Lookup(void* key, uint32_t hash, bool insert, 50400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy allocator = AllocationPolicy()); 5143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 52b3284ad36ee358a35b81379ad1c449e4f8021362kasperl@chromium.org // Removes the entry with matching key. 5328faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org // It returns the value of the deleted entry 5428faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org // or null if there is no value for such key. 5528faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org void* Remove(void* key, uint32_t hash); 56b3284ad36ee358a35b81379ad1c449e4f8021362kasperl@chromium.org 5743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // Empties the hash map (occupancy() == 0). 5843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen void Clear(); 5943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 6043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // The number of (non-empty) entries in the table. 614a1fe7d5e92fdb673d5f05d5ddf7b1ed703ba18dwhesse@chromium.org uint32_t occupancy() const { return occupancy_; } 6243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 6343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // The capacity of the table. The implementation 6443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // makes sure that occupancy is at most 80% of 6543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // the table capacity. 664a1fe7d5e92fdb673d5f05d5ddf7b1ed703ba18dwhesse@chromium.org uint32_t capacity() const { return capacity_; } 6743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 6843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // Iteration 6943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // 7043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) { 7143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // ... 7243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // } 7343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // 7443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // If entries are inserted during iteration, the effect of 7543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // calling Next() is undefined. 7643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen Entry* Start() const; 7743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen Entry* Next(Entry* p) const; 7843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 79731474e847a8ccd6e27f74842506c9c807dae658jarin@chromium.org // Some match functions defined for convenience. 80731474e847a8ccd6e27f74842506c9c807dae658jarin@chromium.org static bool PointersMatch(void* key1, void* key2) { 81731474e847a8ccd6e27f74842506c9c807dae658jarin@chromium.org return key1 == key2; 82731474e847a8ccd6e27f74842506c9c807dae658jarin@chromium.org } 83731474e847a8ccd6e27f74842506c9c807dae658jarin@chromium.org 8443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen private: 8543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen MatchFun match_; 8643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen Entry* map_; 8743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen uint32_t capacity_; 8843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen uint32_t occupancy_; 8943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 904a1fe7d5e92fdb673d5f05d5ddf7b1ed703ba18dwhesse@chromium.org Entry* map_end() const { return map_ + capacity_; } 9143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen Entry* Probe(void* key, uint32_t hash); 92400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org void Initialize(uint32_t capacity, AllocationPolicy allocator); 93400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org void Resize(AllocationPolicy allocator); 9443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen}; 9543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 962c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.orgtypedef TemplateHashMapImpl<FreeStoreAllocationPolicy> HashMap; 97ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 98400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtemplate<class AllocationPolicy> 99400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgTemplateHashMapImpl<AllocationPolicy>::TemplateHashMapImpl( 100400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org MatchFun match, uint32_t initial_capacity, AllocationPolicy allocator) { 101ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org match_ = match; 102400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org Initialize(initial_capacity, allocator); 103ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org} 104ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 105ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 106400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtemplate<class AllocationPolicy> 107400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgTemplateHashMapImpl<AllocationPolicy>::~TemplateHashMapImpl() { 108400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy::Delete(map_); 109ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org} 110ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 111ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 112400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtemplate<class AllocationPolicy> 113400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtypename TemplateHashMapImpl<AllocationPolicy>::Entry* 114400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgTemplateHashMapImpl<AllocationPolicy>::Lookup( 115400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org void* key, uint32_t hash, bool insert, AllocationPolicy allocator) { 116ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // Find a matching entry. 117ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org Entry* p = Probe(key, hash); 118ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org if (p->key != NULL) { 119ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org return p; 120ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 121ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 122ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // No entry found; insert one if necessary. 123ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org if (insert) { 124ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org p->key = key; 125ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org p->value = NULL; 126ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org p->hash = hash; 12746839fbbdee40a3d2d924e8b5b13c4139b0b24f2yangguo@chromium.org p->order = occupancy_; 128ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org occupancy_++; 129ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 130ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // Grow the map if we reached >= 80% occupancy. 131ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org if (occupancy_ + occupancy_/4 >= capacity_) { 132400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org Resize(allocator); 133ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org p = Probe(key, hash); 134ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 135ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 136ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org return p; 137ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 138ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 139ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // No entry found and none inserted. 140ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org return NULL; 141ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org} 142ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 143ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 144400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtemplate<class AllocationPolicy> 145400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgvoid* TemplateHashMapImpl<AllocationPolicy>::Remove(void* key, uint32_t hash) { 146ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // Lookup the entry for the key to remove. 147ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org Entry* p = Probe(key, hash); 148ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org if (p->key == NULL) { 149ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // Key not found nothing to remove. 15028faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org return NULL; 151ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 152ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 15328faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org void* value = p->value; 154ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // To remove an entry we need to ensure that it does not create an empty 155ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // entry that will cause the search for another entry to stop too soon. If all 156ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // the entries between the entry to remove and the next empty slot have their 157ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // initial position inside this interval, clearing the entry to remove will 158ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // not break the search. If, while searching for the next empty entry, an 159ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // entry is encountered which does not have its initial position between the 160ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // entry to remove and the position looked at, then this entry can be moved to 161ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // the place of the entry to remove without breaking the search for it. The 162ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // entry made vacant by this move is now the entry to remove and the process 163ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // starts over. 164ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // Algorithm from http://en.wikipedia.org/wiki/Open_addressing. 165ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 166ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // This guarantees loop termination as there is at least one empty entry so 167ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // eventually the removed entry will have an empty entry after it. 168e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(occupancy_ < capacity_); 169ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 170ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // p is the candidate entry to clear. q is used to scan forwards. 171ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org Entry* q = p; // Start at the entry to remove. 172ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org while (true) { 173ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // Move q to the next entry. 174ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org q = q + 1; 175ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org if (q == map_end()) { 176ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org q = map_; 177ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 178ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 179ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // All entries between p and q have their initial position between p and q 180ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // and the entry p can be cleared without breaking the search for these 181ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // entries. 182ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org if (q->key == NULL) { 183ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org break; 184ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 185ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 186ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // Find the initial position for the entry at position q. 187ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org Entry* r = map_ + (q->hash & (capacity_ - 1)); 188ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 189ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // If the entry at position q has its initial position outside the range 190ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // between p and q it can be moved forward to position p and will still be 191ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // found. There is now a new candidate entry for clearing. 192ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org if ((q > p && (r <= p || r > q)) || 193ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org (q < p && (r <= p && r > q))) { 194ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org *p = *q; 195ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org p = q; 196ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 197ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 198ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 199ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // Clear the entry which is allowed to en emptied. 200ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org p->key = NULL; 201ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org occupancy_--; 20228faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org return value; 203ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org} 204ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 205ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 206400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtemplate<class AllocationPolicy> 207400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgvoid TemplateHashMapImpl<AllocationPolicy>::Clear() { 208ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // Mark all entries as empty. 209ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org const Entry* end = map_end(); 210ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org for (Entry* p = map_; p < end; p++) { 211ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org p->key = NULL; 212ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 213ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org occupancy_ = 0; 214ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org} 215ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 216ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 217400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtemplate<class AllocationPolicy> 218400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtypename TemplateHashMapImpl<AllocationPolicy>::Entry* 219400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org TemplateHashMapImpl<AllocationPolicy>::Start() const { 220ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org return Next(map_ - 1); 221ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org} 222ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 223ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 224400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtemplate<class AllocationPolicy> 225400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtypename TemplateHashMapImpl<AllocationPolicy>::Entry* 226400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org TemplateHashMapImpl<AllocationPolicy>::Next(Entry* p) const { 227ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org const Entry* end = map_end(); 228e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(map_ - 1 <= p && p < end); 229ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org for (p++; p < end; p++) { 230ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org if (p->key != NULL) { 231ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org return p; 232ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 233ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 234ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org return NULL; 235ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org} 236ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 237ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 238400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtemplate<class AllocationPolicy> 239400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtypename TemplateHashMapImpl<AllocationPolicy>::Entry* 240400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org TemplateHashMapImpl<AllocationPolicy>::Probe(void* key, uint32_t hash) { 241e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(key != NULL); 242ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 24321d700eedcdd6570eff22ece724b63a5eefe78cbmachenbach@chromium.org DCHECK(base::bits::IsPowerOfTwo32(capacity_)); 244ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org Entry* p = map_ + (hash & (capacity_ - 1)); 245ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org const Entry* end = map_end(); 246e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(map_ <= p && p < end); 247ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 248e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(occupancy_ < capacity_); // Guarantees loop termination. 249ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) { 250ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org p++; 251ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org if (p >= end) { 252ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org p = map_; 253ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 254ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 255ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 256ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org return p; 257ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org} 258ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 259ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 260400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtemplate<class AllocationPolicy> 261400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgvoid TemplateHashMapImpl<AllocationPolicy>::Initialize( 262400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org uint32_t capacity, AllocationPolicy allocator) { 26321d700eedcdd6570eff22ece724b63a5eefe78cbmachenbach@chromium.org DCHECK(base::bits::IsPowerOfTwo32(capacity)); 264400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org map_ = reinterpret_cast<Entry*>(allocator.New(capacity * sizeof(Entry))); 265ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org if (map_ == NULL) { 266ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org v8::internal::FatalProcessOutOfMemory("HashMap::Initialize"); 267ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org return; 268ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 269ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org capacity_ = capacity; 270ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org Clear(); 271ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org} 272ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 273ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 274400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtemplate<class AllocationPolicy> 275400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgvoid TemplateHashMapImpl<AllocationPolicy>::Resize(AllocationPolicy allocator) { 276ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org Entry* map = map_; 277ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org uint32_t n = occupancy_; 278ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 279ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // Allocate larger map. 280400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org Initialize(capacity_ * 2, allocator); 281ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 282ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // Rehash all current entries. 283ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org for (Entry* p = map; n > 0; p++) { 284ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org if (p->key != NULL) { 28546839fbbdee40a3d2d924e8b5b13c4139b0b24f2yangguo@chromium.org Entry* entry = Lookup(p->key, p->hash, true, allocator); 28646839fbbdee40a3d2d924e8b5b13c4139b0b24f2yangguo@chromium.org entry->value = p->value; 28746839fbbdee40a3d2d924e8b5b13c4139b0b24f2yangguo@chromium.org entry->order = p->order; 288ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org n--; 289ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 290ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 291ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 292ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // Delete old map. 293400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy::Delete(map); 294ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org} 29543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 2962c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org 2972c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org// A hash map for pointer keys and values with an STL-like interface. 2982c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.orgtemplate<class Key, class Value, class AllocationPolicy> 2992c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.orgclass TemplateHashMap: private TemplateHashMapImpl<AllocationPolicy> { 3002c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org public: 3012c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org STATIC_ASSERT(sizeof(Key*) == sizeof(void*)); // NOLINT 3022c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org STATIC_ASSERT(sizeof(Value*) == sizeof(void*)); // NOLINT 3032c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org struct value_type { 3042c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org Key* first; 3052c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org Value* second; 3062c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org }; 3072c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org 3082c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org class Iterator { 3092c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org public: 3102c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org Iterator& operator++() { 3112c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org entry_ = map_->Next(entry_); 3122c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org return *this; 3132c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org } 3142c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org 3152c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org value_type* operator->() { return reinterpret_cast<value_type*>(entry_); } 3162c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org bool operator!=(const Iterator& other) { return entry_ != other.entry_; } 3172c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org 3182c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org private: 3192c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org Iterator(const TemplateHashMapImpl<AllocationPolicy>* map, 3202c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry) : 3212c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org map_(map), entry_(entry) { } 3222c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org 3232c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org const TemplateHashMapImpl<AllocationPolicy>* map_; 3242c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry_; 3252c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org 3262c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org friend class TemplateHashMap; 3272c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org }; 3282c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org 3292c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org TemplateHashMap( 330400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org typename TemplateHashMapImpl<AllocationPolicy>::MatchFun match, 331400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy allocator = AllocationPolicy()) 332400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org : TemplateHashMapImpl<AllocationPolicy>( 333400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org match, 334400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org TemplateHashMapImpl<AllocationPolicy>::kDefaultHashMapCapacity, 335400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org allocator) { } 3362c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org 3372c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org Iterator begin() const { return Iterator(this, this->Start()); } 3382c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org Iterator end() const { return Iterator(this, NULL); } 3397028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org Iterator find(Key* key, bool insert = false, 3407028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org AllocationPolicy allocator = AllocationPolicy()) { 3417028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org return Iterator(this, this->Lookup(key, key->Hash(), insert, allocator)); 3422c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org } 3432c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org}; 3442c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org 34543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen} } // namespace v8::internal 34643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 34743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen#endif // V8_HASHMAP_H_ 348