13ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch// Copyright 2012 the V8 project authors. All rights reserved. 2a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Redistribution and use in source and binary forms, with or without 3a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// modification, are permitted provided that the following conditions are 4a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// met: 5a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// 6a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// * Redistributions of source code must retain the above copyright 7a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// notice, this list of conditions and the following disclaimer. 8a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// * Redistributions in binary form must reproduce the above 9a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// copyright notice, this list of conditions and the following 10a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// disclaimer in the documentation and/or other materials provided 11a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// with the distribution. 12a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// * Neither the name of Google Inc. nor the names of its 13a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// contributors may be used to endorse or promote products derived 14a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// from this software without specific prior written permission. 15a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// 16a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 28a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#ifndef V8_HASHMAP_H_ 29a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#define V8_HASHMAP_H_ 30a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 31257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch#include "allocation.h" 323ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch#include "checks.h" 333ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch#include "utils.h" 34257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch 35a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocknamespace v8 { 36a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocknamespace internal { 37a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 383ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochtemplate<class AllocationPolicy> 393ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochclass TemplateHashMapImpl { 40a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block public: 41a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block typedef bool (*MatchFun) (void* key1, void* key2); 42a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 43a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // initial_capacity is the size of the initial hash map; 44a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // it must be a power of 2 (and thus must not be 0). 453ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch TemplateHashMapImpl(MatchFun match, uint32_t initial_capacity = 8); 46a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 473ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch ~TemplateHashMapImpl(); 48a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 49a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // HashMap entries are (key, value, hash) triplets. 50a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Some clients may not need to use the value slot 51a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // (e.g. implementers of sets, where the key is the value). 52a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block struct Entry { 53a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block void* key; 54a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block void* value; 55a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block uint32_t hash; // the full hash value for key 56a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block }; 57a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 58a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // If an entry with matching key is found, Lookup() 59a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // returns that entry. If no matching entry is found, 60a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // but insert is set, a new entry is inserted with 61a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // corresponding key, key hash, and NULL value. 62a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Otherwise, NULL is returned. 63a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block Entry* Lookup(void* key, uint32_t hash, bool insert); 64a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 65a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Removes the entry with matching key. 66a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block void Remove(void* key, uint32_t hash); 67a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 68a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Empties the hash map (occupancy() == 0). 69a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block void Clear(); 70a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 71a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // The number of (non-empty) entries in the table. 720d5e116f6aee03185f237311a943491bb079a768Kristian Monsen uint32_t occupancy() const { return occupancy_; } 73a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 74a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // The capacity of the table. The implementation 75a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // makes sure that occupancy is at most 80% of 76a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // the table capacity. 770d5e116f6aee03185f237311a943491bb079a768Kristian Monsen uint32_t capacity() const { return capacity_; } 78a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 79a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Iteration 80a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // 81a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) { 82a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // ... 83a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // } 84a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // 85a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // If entries are inserted during iteration, the effect of 86a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // calling Next() is undefined. 87a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block Entry* Start() const; 88a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block Entry* Next(Entry* p) const; 89a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 90a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block private: 91a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block MatchFun match_; 92a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block Entry* map_; 93a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block uint32_t capacity_; 94a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block uint32_t occupancy_; 95a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 960d5e116f6aee03185f237311a943491bb079a768Kristian Monsen Entry* map_end() const { return map_ + capacity_; } 97a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block Entry* Probe(void* key, uint32_t hash); 98a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block void Initialize(uint32_t capacity); 99a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block void Resize(); 100a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block}; 101a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 1023ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochtypedef TemplateHashMapImpl<FreeStoreAllocationPolicy> HashMap; 1033ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1043ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochtemplate<class P> 1053ef787dbeca8a5fb1086949cda830dccee07bfbdBen MurdochTemplateHashMapImpl<P>::TemplateHashMapImpl(MatchFun match, 1063ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch uint32_t initial_capacity) { 1073ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch match_ = match; 1083ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Initialize(initial_capacity); 1093ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch} 1103ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1113ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1123ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochtemplate<class P> 1133ef787dbeca8a5fb1086949cda830dccee07bfbdBen MurdochTemplateHashMapImpl<P>::~TemplateHashMapImpl() { 1143ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch P::Delete(map_); 1153ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch} 1163ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1173ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1183ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochtemplate<class P> 1193ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochtypename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Lookup( 1203ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch void* key, uint32_t hash, bool insert) { 1213ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Find a matching entry. 1223ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Entry* p = Probe(key, hash); 1233ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (p->key != NULL) { 1243ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return p; 1253ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 1263ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1273ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // No entry found; insert one if necessary. 1283ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (insert) { 1293ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch p->key = key; 1303ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch p->value = NULL; 1313ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch p->hash = hash; 1323ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch occupancy_++; 1333ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1343ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Grow the map if we reached >= 80% occupancy. 1353ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (occupancy_ + occupancy_/4 >= capacity_) { 1363ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Resize(); 1373ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch p = Probe(key, hash); 1383ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 1393ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1403ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return p; 1413ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 1423ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1433ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // No entry found and none inserted. 1443ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return NULL; 1453ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch} 1463ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1473ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1483ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochtemplate<class P> 1493ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid TemplateHashMapImpl<P>::Remove(void* key, uint32_t hash) { 1503ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Lookup the entry for the key to remove. 1513ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Entry* p = Probe(key, hash); 1523ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (p->key == NULL) { 1533ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Key not found nothing to remove. 1543ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return; 1553ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 1563ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1573ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // To remove an entry we need to ensure that it does not create an empty 1583ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // entry that will cause the search for another entry to stop too soon. If all 1593ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // the entries between the entry to remove and the next empty slot have their 1603ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // initial position inside this interval, clearing the entry to remove will 1613ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // not break the search. If, while searching for the next empty entry, an 1623ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // entry is encountered which does not have its initial position between the 1633ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // entry to remove and the position looked at, then this entry can be moved to 1643ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // the place of the entry to remove without breaking the search for it. The 1653ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // entry made vacant by this move is now the entry to remove and the process 1663ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // starts over. 1673ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Algorithm from http://en.wikipedia.org/wiki/Open_addressing. 1683ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1693ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // This guarantees loop termination as there is at least one empty entry so 1703ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // eventually the removed entry will have an empty entry after it. 1713ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch ASSERT(occupancy_ < capacity_); 1723ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1733ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // p is the candidate entry to clear. q is used to scan forwards. 1743ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Entry* q = p; // Start at the entry to remove. 1753ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch while (true) { 1763ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Move q to the next entry. 1773ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch q = q + 1; 1783ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (q == map_end()) { 1793ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch q = map_; 1803ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 1813ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1823ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // All entries between p and q have their initial position between p and q 1833ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // and the entry p can be cleared without breaking the search for these 1843ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // entries. 1853ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (q->key == NULL) { 1863ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch break; 1873ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 1883ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1893ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Find the initial position for the entry at position q. 1903ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Entry* r = map_ + (q->hash & (capacity_ - 1)); 1913ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1923ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // If the entry at position q has its initial position outside the range 1933ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // between p and q it can be moved forward to position p and will still be 1943ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // found. There is now a new candidate entry for clearing. 1953ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if ((q > p && (r <= p || r > q)) || 1963ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch (q < p && (r <= p && r > q))) { 1973ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch *p = *q; 1983ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch p = q; 1993ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 2003ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 2013ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 2023ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Clear the entry which is allowed to en emptied. 2033ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch p->key = NULL; 2043ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch occupancy_--; 2053ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch} 2063ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 2073ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 2083ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochtemplate<class P> 2093ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid TemplateHashMapImpl<P>::Clear() { 2103ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Mark all entries as empty. 2113ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch const Entry* end = map_end(); 2123ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch for (Entry* p = map_; p < end; p++) { 2133ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch p->key = NULL; 2143ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 2153ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch occupancy_ = 0; 2163ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch} 2173ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 2183ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 2193ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochtemplate<class P> 2203ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochtypename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Start() const { 2213ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return Next(map_ - 1); 2223ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch} 2233ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 2243ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 2253ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochtemplate<class P> 2263ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochtypename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Next(Entry* p) 2273ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch const { 2283ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch const Entry* end = map_end(); 2293ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch ASSERT(map_ - 1 <= p && p < end); 2303ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch for (p++; p < end; p++) { 2313ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (p->key != NULL) { 2323ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return p; 2333ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 2343ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 2353ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return NULL; 2363ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch} 2373ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 2383ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 2393ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochtemplate<class P> 2403ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochtypename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Probe(void* key, 2413ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch uint32_t hash) { 2423ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch ASSERT(key != NULL); 2433ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 2443ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch ASSERT(IsPowerOf2(capacity_)); 2453ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Entry* p = map_ + (hash & (capacity_ - 1)); 2463ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch const Entry* end = map_end(); 2473ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch ASSERT(map_ <= p && p < end); 2483ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 2493ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch ASSERT(occupancy_ < capacity_); // Guarantees loop termination. 2503ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) { 2513ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch p++; 2523ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (p >= end) { 2533ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch p = map_; 2543ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 2553ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 2563ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 2573ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return p; 2583ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch} 2593ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 2603ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 2613ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochtemplate<class P> 2623ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid TemplateHashMapImpl<P>::Initialize(uint32_t capacity) { 2633ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch ASSERT(IsPowerOf2(capacity)); 2643ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch map_ = reinterpret_cast<Entry*>(P::New(capacity * sizeof(Entry))); 2653ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (map_ == NULL) { 2663ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch v8::internal::FatalProcessOutOfMemory("HashMap::Initialize"); 2673ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return; 2683ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 2693ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch capacity_ = capacity; 2703ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Clear(); 2713ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch} 2723ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 2733ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 2743ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochtemplate<class P> 2753ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid TemplateHashMapImpl<P>::Resize() { 2763ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Entry* map = map_; 2773ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch uint32_t n = occupancy_; 2783ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 2793ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Allocate larger map. 2803ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Initialize(capacity_ * 2); 2813ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 2823ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Rehash all current entries. 2833ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch for (Entry* p = map; n > 0; p++) { 2843ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (p->key != NULL) { 2853ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Lookup(p->key, p->hash, true)->value = p->value; 2863ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch n--; 2873ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 2883ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 2893ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 2903ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Delete old map. 2913ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch P::Delete(map); 2923ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch} 2933ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 2943ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 2953ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch// A hash map for pointer keys and values with an STL-like interface. 2963ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochtemplate<class Key, class Value, class AllocationPolicy> 2973ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochclass TemplateHashMap: private TemplateHashMapImpl<AllocationPolicy> { 2983ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch public: 2993ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch STATIC_ASSERT(sizeof(Key*) == sizeof(void*)); // NOLINT 3003ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch STATIC_ASSERT(sizeof(Value*) == sizeof(void*)); // NOLINT 3013ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch struct value_type { 3023ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Key* first; 3033ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Value* second; 3043ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch }; 3053ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 3063ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch class Iterator { 3073ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch public: 3083ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Iterator& operator++() { 3093ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch entry_ = map_->Next(entry_); 3103ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return *this; 3113ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 3123ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 3133ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch value_type* operator->() { return reinterpret_cast<value_type*>(entry_); } 3143ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch bool operator!=(const Iterator& other) { return entry_ != other.entry_; } 3153ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 3163ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch private: 3173ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Iterator(const TemplateHashMapImpl<AllocationPolicy>* map, 3183ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry) : 3193ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch map_(map), entry_(entry) { } 3203ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 3213ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch const TemplateHashMapImpl<AllocationPolicy>* map_; 3223ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry_; 3233ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 3243ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch friend class TemplateHashMap; 3253ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch }; 3263ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 3273ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch TemplateHashMap( 3283ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch typename TemplateHashMapImpl<AllocationPolicy>::MatchFun match) 3293ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch : TemplateHashMapImpl<AllocationPolicy>(match) { } 3303ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 3313ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Iterator begin() const { return Iterator(this, this->Start()); } 3323ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Iterator end() const { return Iterator(this, NULL); } 3333ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Iterator find(Key* key, bool insert = false) { 3343ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return Iterator(this, this->Lookup(key, key->Hash(), insert)); 3353ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 3363ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch}; 337a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 338a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} } // namespace v8::internal 339a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 340a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#endif // V8_HASHMAP_H_ 341