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" 9196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org#include "src/checks.h" 10196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org#include "src/utils.h" 11fb144a0716afe7ab8bf245f2391a9e53b3db3c89fschneider@chromium.org 1271affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.orgnamespace v8 { 1371affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.orgnamespace internal { 1443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 15ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.orgtemplate<class AllocationPolicy> 162c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.orgclass TemplateHashMapImpl { 1743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen public: 1843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen typedef bool (*MatchFun) (void* key1, void* key2); 1943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 20400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org // The default capacity. This is used by the call sites which want 21400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org // to pass in a non-default AllocationPolicy but want to use the 22400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org // default value of capacity specified by the implementation. 23400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org static const uint32_t kDefaultHashMapCapacity = 8; 24400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org 2543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // initial_capacity is the size of the initial hash map; 2643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // it must be a power of 2 (and thus must not be 0). 27400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org TemplateHashMapImpl(MatchFun match, 28400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org uint32_t capacity = kDefaultHashMapCapacity, 29400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy allocator = AllocationPolicy()); 3043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 312c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org ~TemplateHashMapImpl(); 3243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 333291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // HashMap entries are (key, value, hash) triplets. 3443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // Some clients may not need to use the value slot 3543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // (e.g. implementers of sets, where the key is the value). 3643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen struct Entry { 3743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen void* key; 3843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen void* value; 3946839fbbdee40a3d2d924e8b5b13c4139b0b24f2yangguo@chromium.org uint32_t hash; // The full hash value for key 4046839fbbdee40a3d2d924e8b5b13c4139b0b24f2yangguo@chromium.org int order; // If you never remove entries this is the insertion order. 4143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen }; 4243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 4343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // If an entry with matching key is found, Lookup() 4443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // returns that entry. If no matching entry is found, 4543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // but insert is set, a new entry is inserted with 4643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // corresponding key, key hash, and NULL value. 4743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // Otherwise, NULL is returned. 48400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org Entry* Lookup(void* key, uint32_t hash, bool insert, 49400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy allocator = AllocationPolicy()); 5043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 51b3284ad36ee358a35b81379ad1c449e4f8021362kasperl@chromium.org // Removes the entry with matching key. 5228faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org // It returns the value of the deleted entry 5328faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org // or null if there is no value for such key. 5428faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org void* Remove(void* key, uint32_t hash); 55b3284ad36ee358a35b81379ad1c449e4f8021362kasperl@chromium.org 5643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // Empties the hash map (occupancy() == 0). 5743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen void Clear(); 5843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 5943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // The number of (non-empty) entries in the table. 604a1fe7d5e92fdb673d5f05d5ddf7b1ed703ba18dwhesse@chromium.org uint32_t occupancy() const { return occupancy_; } 6143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 6243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // The capacity of the table. The implementation 6343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // makes sure that occupancy is at most 80% of 6443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // the table capacity. 654a1fe7d5e92fdb673d5f05d5ddf7b1ed703ba18dwhesse@chromium.org uint32_t capacity() const { return capacity_; } 6643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 6743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // Iteration 6843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // 6943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) { 7043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // ... 7143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // } 7243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // 7343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // If entries are inserted during iteration, the effect of 7443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // calling Next() is undefined. 7543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen Entry* Start() const; 7643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen Entry* Next(Entry* p) const; 7743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 78731474e847a8ccd6e27f74842506c9c807dae658jarin@chromium.org // Some match functions defined for convenience. 79731474e847a8ccd6e27f74842506c9c807dae658jarin@chromium.org static bool PointersMatch(void* key1, void* key2) { 80731474e847a8ccd6e27f74842506c9c807dae658jarin@chromium.org return key1 == key2; 81731474e847a8ccd6e27f74842506c9c807dae658jarin@chromium.org } 82731474e847a8ccd6e27f74842506c9c807dae658jarin@chromium.org 8343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen private: 8443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen MatchFun match_; 8543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen Entry* map_; 8643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen uint32_t capacity_; 8743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen uint32_t occupancy_; 8843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 894a1fe7d5e92fdb673d5f05d5ddf7b1ed703ba18dwhesse@chromium.org Entry* map_end() const { return map_ + capacity_; } 9043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen Entry* Probe(void* key, uint32_t hash); 91400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org void Initialize(uint32_t capacity, AllocationPolicy allocator); 92400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org void Resize(AllocationPolicy allocator); 9343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen}; 9443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 952c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.orgtypedef TemplateHashMapImpl<FreeStoreAllocationPolicy> HashMap; 96ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 97400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtemplate<class AllocationPolicy> 98400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgTemplateHashMapImpl<AllocationPolicy>::TemplateHashMapImpl( 99400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org MatchFun match, uint32_t initial_capacity, AllocationPolicy allocator) { 100ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org match_ = match; 101400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org Initialize(initial_capacity, allocator); 102ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org} 103ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 104ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 105400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtemplate<class AllocationPolicy> 106400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgTemplateHashMapImpl<AllocationPolicy>::~TemplateHashMapImpl() { 107400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy::Delete(map_); 108ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org} 109ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 110ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 111400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtemplate<class AllocationPolicy> 112400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtypename TemplateHashMapImpl<AllocationPolicy>::Entry* 113400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgTemplateHashMapImpl<AllocationPolicy>::Lookup( 114400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org void* key, uint32_t hash, bool insert, AllocationPolicy allocator) { 115ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // Find a matching entry. 116ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org Entry* p = Probe(key, hash); 117ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org if (p->key != NULL) { 118ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org return p; 119ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 120ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 121ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // No entry found; insert one if necessary. 122ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org if (insert) { 123ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org p->key = key; 124ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org p->value = NULL; 125ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org p->hash = hash; 12646839fbbdee40a3d2d924e8b5b13c4139b0b24f2yangguo@chromium.org p->order = occupancy_; 127ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org occupancy_++; 128ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 129ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // Grow the map if we reached >= 80% occupancy. 130ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org if (occupancy_ + occupancy_/4 >= capacity_) { 131400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org Resize(allocator); 132ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org p = Probe(key, hash); 133ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 134ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 135ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org return p; 136ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 137ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 138ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // No entry found and none inserted. 139ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org return NULL; 140ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org} 141ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 142ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 143400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtemplate<class AllocationPolicy> 144400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgvoid* TemplateHashMapImpl<AllocationPolicy>::Remove(void* key, uint32_t hash) { 145ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // Lookup the entry for the key to remove. 146ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org Entry* p = Probe(key, hash); 147ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org if (p->key == NULL) { 148ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // Key not found nothing to remove. 14928faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org return NULL; 150ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 151ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 15228faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org void* value = p->value; 153ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // To remove an entry we need to ensure that it does not create an empty 154ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // entry that will cause the search for another entry to stop too soon. If all 155ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // the entries between the entry to remove and the next empty slot have their 156ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // initial position inside this interval, clearing the entry to remove will 157ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // not break the search. If, while searching for the next empty entry, an 158ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // entry is encountered which does not have its initial position between the 159ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // entry to remove and the position looked at, then this entry can be moved to 160ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // the place of the entry to remove without breaking the search for it. The 161ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // entry made vacant by this move is now the entry to remove and the process 162ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // starts over. 163ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // Algorithm from http://en.wikipedia.org/wiki/Open_addressing. 164ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 165ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // This guarantees loop termination as there is at least one empty entry so 166ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // eventually the removed entry will have an empty entry after it. 167ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org ASSERT(occupancy_ < capacity_); 168ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 169ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // p is the candidate entry to clear. q is used to scan forwards. 170ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org Entry* q = p; // Start at the entry to remove. 171ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org while (true) { 172ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // Move q to the next entry. 173ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org q = q + 1; 174ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org if (q == map_end()) { 175ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org q = map_; 176ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 177ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 178ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // All entries between p and q have their initial position between p and q 179ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // and the entry p can be cleared without breaking the search for these 180ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // entries. 181ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org if (q->key == NULL) { 182ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org break; 183ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 184ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 185ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // Find the initial position for the entry at position q. 186ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org Entry* r = map_ + (q->hash & (capacity_ - 1)); 187ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 188ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // If the entry at position q has its initial position outside the range 189ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // between p and q it can be moved forward to position p and will still be 190ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // found. There is now a new candidate entry for clearing. 191ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org if ((q > p && (r <= p || r > q)) || 192ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org (q < p && (r <= p && r > q))) { 193ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org *p = *q; 194ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org p = q; 195ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 196ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 197ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 198ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // Clear the entry which is allowed to en emptied. 199ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org p->key = NULL; 200ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org occupancy_--; 20128faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org return value; 202ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org} 203ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 204ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 205400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtemplate<class AllocationPolicy> 206400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgvoid TemplateHashMapImpl<AllocationPolicy>::Clear() { 207ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // Mark all entries as empty. 208ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org const Entry* end = map_end(); 209ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org for (Entry* p = map_; p < end; p++) { 210ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org p->key = NULL; 211ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 212ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org occupancy_ = 0; 213ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org} 214ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 215ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 216400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtemplate<class AllocationPolicy> 217400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtypename TemplateHashMapImpl<AllocationPolicy>::Entry* 218400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org TemplateHashMapImpl<AllocationPolicy>::Start() const { 219ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org return Next(map_ - 1); 220ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org} 221ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 222ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 223400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtemplate<class AllocationPolicy> 224400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtypename TemplateHashMapImpl<AllocationPolicy>::Entry* 225400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org TemplateHashMapImpl<AllocationPolicy>::Next(Entry* p) const { 226ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org const Entry* end = map_end(); 227ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org ASSERT(map_ - 1 <= p && p < end); 228ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org for (p++; p < end; p++) { 229ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org if (p->key != NULL) { 230ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org return p; 231ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 232ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 233ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org return NULL; 234ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org} 235ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 236ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 237400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtemplate<class AllocationPolicy> 238400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtypename TemplateHashMapImpl<AllocationPolicy>::Entry* 239400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org TemplateHashMapImpl<AllocationPolicy>::Probe(void* key, uint32_t hash) { 240ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org ASSERT(key != NULL); 241ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 242ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org ASSERT(IsPowerOf2(capacity_)); 243ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org Entry* p = map_ + (hash & (capacity_ - 1)); 244ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org const Entry* end = map_end(); 245ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org ASSERT(map_ <= p && p < end); 246ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 247ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org ASSERT(occupancy_ < capacity_); // Guarantees loop termination. 248ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) { 249ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org p++; 250ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org if (p >= end) { 251ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org p = map_; 252ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 253ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 254ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 255ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org return p; 256ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org} 257ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 258ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 259400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtemplate<class AllocationPolicy> 260400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgvoid TemplateHashMapImpl<AllocationPolicy>::Initialize( 261400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org uint32_t capacity, AllocationPolicy allocator) { 262ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org ASSERT(IsPowerOf2(capacity)); 263400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org map_ = reinterpret_cast<Entry*>(allocator.New(capacity * sizeof(Entry))); 264ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org if (map_ == NULL) { 265ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org v8::internal::FatalProcessOutOfMemory("HashMap::Initialize"); 266ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org return; 267ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 268ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org capacity_ = capacity; 269ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org Clear(); 270ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org} 271ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 272ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 273400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtemplate<class AllocationPolicy> 274400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgvoid TemplateHashMapImpl<AllocationPolicy>::Resize(AllocationPolicy allocator) { 275ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org Entry* map = map_; 276ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org uint32_t n = occupancy_; 277ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 278ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // Allocate larger map. 279400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org Initialize(capacity_ * 2, allocator); 280ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 281ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // Rehash all current entries. 282ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org for (Entry* p = map; n > 0; p++) { 283ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org if (p->key != NULL) { 28446839fbbdee40a3d2d924e8b5b13c4139b0b24f2yangguo@chromium.org Entry* entry = Lookup(p->key, p->hash, true, allocator); 28546839fbbdee40a3d2d924e8b5b13c4139b0b24f2yangguo@chromium.org entry->value = p->value; 28646839fbbdee40a3d2d924e8b5b13c4139b0b24f2yangguo@chromium.org entry->order = p->order; 287ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org n--; 288ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 289ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org } 290ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org 291ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org // Delete old map. 292400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy::Delete(map); 293ab30bb83bf3dae0053739c57b1db9ad13c1f9e3ayangguo@chromium.org} 29443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 2952c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org 2962c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org// A hash map for pointer keys and values with an STL-like interface. 2972c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.orgtemplate<class Key, class Value, class AllocationPolicy> 2982c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.orgclass TemplateHashMap: private TemplateHashMapImpl<AllocationPolicy> { 2992c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org public: 3002c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org STATIC_ASSERT(sizeof(Key*) == sizeof(void*)); // NOLINT 3012c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org STATIC_ASSERT(sizeof(Value*) == sizeof(void*)); // NOLINT 3022c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org struct value_type { 3032c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org Key* first; 3042c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org Value* second; 3052c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org }; 3062c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org 3072c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org class Iterator { 3082c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org public: 3092c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org Iterator& operator++() { 3102c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org entry_ = map_->Next(entry_); 3112c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org return *this; 3122c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org } 3132c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org 3142c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org value_type* operator->() { return reinterpret_cast<value_type*>(entry_); } 3152c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org bool operator!=(const Iterator& other) { return entry_ != other.entry_; } 3162c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org 3172c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org private: 3182c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org Iterator(const TemplateHashMapImpl<AllocationPolicy>* map, 3192c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry) : 3202c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org map_(map), entry_(entry) { } 3212c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org 3222c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org const TemplateHashMapImpl<AllocationPolicy>* map_; 3232c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry_; 3242c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org 3252c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org friend class TemplateHashMap; 3262c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org }; 3272c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org 3282c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org TemplateHashMap( 329400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org typename TemplateHashMapImpl<AllocationPolicy>::MatchFun match, 330400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy allocator = AllocationPolicy()) 331400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org : TemplateHashMapImpl<AllocationPolicy>( 332400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org match, 333400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org TemplateHashMapImpl<AllocationPolicy>::kDefaultHashMapCapacity, 334400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org allocator) { } 3352c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org 3362c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org Iterator begin() const { return Iterator(this, this->Start()); } 3372c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org Iterator end() const { return Iterator(this, NULL); } 3387028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org Iterator find(Key* key, bool insert = false, 3397028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org AllocationPolicy allocator = AllocationPolicy()) { 3407028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org return Iterator(this, this->Lookup(key, key->Hash(), insert, allocator)); 3412c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org } 3422c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org}; 3432c067b150f65db3e076b6b5a813e7f6f2492f770rossberg@chromium.org 34443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen} } // namespace v8::internal 34543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 34643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen#endif // V8_HASHMAP_H_ 347