15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* 25c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserved. 35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Copyright (C) 2008 David Levin <levin@chromium.org> 45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * This library is free software; you can redistribute it and/or 65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * modify it under the terms of the GNU Library General Public 75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * License as published by the Free Software Foundation; either 85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * version 2 of the License, or (at your option) any later version. 95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * This library is distributed in the hope that it will be useful, 115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * but WITHOUT ANY WARRANTY; without even the implied warranty of 125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Library General Public License for more details. 145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * You should have received a copy of the GNU Library General Public License 165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * along with this library; see the file COPYING.LIB. If not, write to 175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Boston, MA 02110-1301, USA. 195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef WTF_HashTable_h 235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define WTF_HashTable_h 245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 25591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "wtf/Alignment.h" 26591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "wtf/Assertions.h" 27591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "wtf/FastMalloc.h" 28591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "wtf/HashTraits.h" 2953e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)#include <string.h> 305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define DUMP_HASHTABLE_STATS 0 325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define DUMP_HASHTABLE_STATS_PER_TABLE 0 335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3453e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)#if DUMP_HASHTABLE_STATS_PER_TABLE 35591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "wtf/DataLog.h" 3653e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)#endif 3753e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) 3853e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)namespace WTF { 3953e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) 405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS 415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct HashTableStats { 435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The following variables are all atomically incremented when modified. 4453e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) static int numAccesses; 4553e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) static int numRehashes; 4653e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) static int numRemoves; 4753e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) static int numReinserts; 485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The following variables are only modified in the recordCollisionAtCount method within a mutex. 5053e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) static int maxCollisions; 5153e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) static int numCollisions; 5253e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) static int collisionGraph[4096]; 535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5453e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) static void recordCollisionAtCount(int count); 5553e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) static void dumpStats(); 565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) class HashTable; 625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) class HashTableIterator; 645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) class HashTableConstIterator; 665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef enum { HashItemKnownGood } HashItemKnownGoodTag; 685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) class HashTableConstIterator { 715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType; 735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator; 745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator; 755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef Value ValueType; 765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef const ValueType& ReferenceType; 775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef const ValueType* PointerType; 785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>; 805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) friend class HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>; 815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void skipEmptyBuckets() 835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (m_position != m_endPosition && HashTableType::isEmptyOrDeletedBucket(*m_position)) 855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++m_position; 865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashTableConstIterator(const HashTableType* table, PointerType position, PointerType endPosition) 895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : m_position(position), m_endPosition(endPosition) 905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) skipEmptyBuckets(); 925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashTableConstIterator(const HashTableType* table, PointerType position, PointerType endPosition, HashItemKnownGoodTag) 955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : m_position(position), m_endPosition(endPosition) 965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) public: 1005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashTableConstIterator() 1015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PointerType get() const 1055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_position; 1075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ReferenceType operator*() const { return *get(); } 1095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PointerType operator->() const { return get(); } 1105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_iterator& operator++() 1125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(m_position != m_endPosition); 1145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++m_position; 1155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) skipEmptyBuckets(); 1165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return *this; 1175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // postfix ++ intentionally omitted 1205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Comparison. 1225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool operator==(const const_iterator& other) const 1235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_position == other.m_position; 1255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool operator!=(const const_iterator& other) const 1275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_position != other.m_position; 1295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool operator==(const iterator& other) const 1315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return *this == static_cast<const_iterator>(other); 1335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool operator!=(const iterator& other) const 1355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return *this != static_cast<const_iterator>(other); 1375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 1405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PointerType m_position; 1415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PointerType m_endPosition; 1425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 1435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 1455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) class HashTableIterator { 1465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 1475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType; 1485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator; 1495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator; 1505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef Value ValueType; 1515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ValueType& ReferenceType; 1525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ValueType* PointerType; 1535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>; 1555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashTableIterator(HashTableType* table, PointerType pos, PointerType end) : m_iterator(table, pos, end) { } 1575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashTableIterator(HashTableType* table, PointerType pos, PointerType end, HashItemKnownGoodTag tag) : m_iterator(table, pos, end, tag) { } 1585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) public: 1605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashTableIterator() { } 1615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // default copy, assignment and destructor are OK 1635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PointerType get() const { return const_cast<PointerType>(m_iterator.get()); } 1655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ReferenceType operator*() const { return *get(); } 1665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PointerType operator->() const { return get(); } 1675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator& operator++() { ++m_iterator; return *this; } 1695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // postfix ++ intentionally omitted 1715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Comparison. 1735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; } 1745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; } 1755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool operator==(const const_iterator& other) const { return m_iterator == other; } 1765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool operator!=(const const_iterator& other) const { return m_iterator != other; } 1775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) operator const_iterator() const { return m_iterator; } 1795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 1815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_iterator m_iterator; 1825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 1835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) using std::swap; 1855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Work around MSVC's standard library, whose swap for pairs does not swap by component. 1875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T> inline void hashTableSwap(T& a, T& b) 1885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) swap(a, b); 1905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, typename U> inline void hashTableSwap(KeyValuePair<T, U>& a, KeyValuePair<T, U>& b) 1935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) swap(a.key, b.key); 1955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) swap(a.value, b.value); 1965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, bool useSwap> struct Mover; 1995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T> struct Mover<T, true> { static void move(T& from, T& to) { hashTableSwap(from, to); } }; 2005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T> struct Mover<T, false> { static void move(T& from, T& to) { to = from; } }; 2015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename HashFunctions> class IdentityHashTranslator { 2035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) public: 2045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); } 20593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a, b); } 2065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, typename U> static void translate(T& location, const U&, const T& value) { location = value; } 2075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 2085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename IteratorType> struct HashTableAddResult { 2105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashTableAddResult(IteratorType iter, bool isNewEntry) : iterator(iter), isNewEntry(isNewEntry) { } 2115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) IteratorType iterator; 2125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool isNewEntry; 2135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 2145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 2165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) class HashTable { 2175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) public: 2185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator; 2195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator; 2205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef Traits ValueTraits; 2215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef Key KeyType; 2225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef Value ValueType; 2235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef IdentityHashTranslator<HashFunctions> IdentityTranslatorType; 2245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef HashTableAddResult<iterator> AddResult; 2255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS_PER_TABLE 2275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct Stats { 2285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Stats() 2295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : numAccesses(0) 2305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , numRehashes(0) 2315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , numRemoves(0) 2325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , numReinserts(0) 2335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , maxCollisions(0) 2345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , numCollisions(0) 2355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , collisionGraph() 2365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int numAccesses; 2405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int numRehashes; 2415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int numRemoves; 2425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int numReinserts; 2435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int maxCollisions; 2455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int numCollisions; 2465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int collisionGraph[4096]; 2475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void recordCollisionAtCount(int count) 2495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (count > maxCollisions) 2515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) maxCollisions = count; 2525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) numCollisions++; 2535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) collisionGraph[count]++; 2545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void dumpStats() 2575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 258926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) dataLogF("\nWTF::HashTable::Stats dump\n\n"); 259926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) dataLogF("%d accesses\n", numAccesses); 260926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) dataLogF("%d total collisions, average %.2f probes per access\n", numCollisions, 1.0 * (numAccesses + numCollisions) / numAccesses); 261926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) dataLogF("longest collision chain: %d\n", maxCollisions); 2625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 1; i <= maxCollisions; i++) { 263926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) dataLogF(" %d lookups with exactly %d collisions (%.2f%% , %.2f%% with this many or more)\n", collisionGraph[i], i, 100.0 * (collisionGraph[i] - collisionGraph[i+1]) / numAccesses, 100.0 * collisionGraph[i] / numAccesses); 2645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 265926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) dataLogF("%d rehashes\n", numRehashes); 266926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) dataLogF("%d reinserts\n", numReinserts); 2675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 2695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 2705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashTable(); 27202772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch ~HashTable() 2735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (m_table) 2755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) deallocateTable(m_table, m_tableSize); 2765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashTable(const HashTable&); 2795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void swap(HashTable&); 2805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashTable& operator=(const HashTable&); 2815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // When the hash table is empty, just return the same iterator for end as for begin. 2835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // This is more efficient because we don't have to skip all the empty and deleted 2845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // buckets, and iterating an empty table is a common case that's worth optimizing. 2855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator begin() { return isEmpty() ? end() : makeIterator(m_table); } 2865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator end() { return makeKnownGoodIterator(m_table + m_tableSize); } 2875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_iterator begin() const { return isEmpty() ? end() : makeConstIterator(m_table); } 2885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_iterator end() const { return makeKnownGoodConstIterator(m_table + m_tableSize); } 2895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int size() const { return m_keyCount; } 2915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int capacity() const { return m_tableSize; } 2925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool isEmpty() const { return !m_keyCount; } 2935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) AddResult add(const ValueType& value) { return add<IdentityTranslatorType>(Extractor::extract(value), value); } 2955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // A special version of add() that finds the object by hashing and comparing 2975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // with some other type, to avoid the cost of type conversion if the object is already 2985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // in the table. 2995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename HashTranslator, typename T, typename Extra> AddResult add(const T& key, const Extra&); 3005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename HashTranslator, typename T, typename Extra> AddResult addPassingHashCode(const T& key, const Extra&); 3015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator find(const KeyType& key) { return find<IdentityTranslatorType>(key); } 3035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_iterator find(const KeyType& key) const { return find<IdentityTranslatorType>(key); } 3045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool contains(const KeyType& key) const { return contains<IdentityTranslatorType>(key); } 3055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename HashTranslator, typename T> iterator find(const T&); 3075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename HashTranslator, typename T> const_iterator find(const T&) const; 3085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename HashTranslator, typename T> bool contains(const T&) const; 3095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void remove(const KeyType&); 3115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void remove(iterator); 312e6d4491e48613634a83c1957c72759da80987961Ben Murdoch void remove(const_iterator); 3135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void clear(); 3145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static bool isEmptyBucket(const ValueType& value) { return isHashTraitsEmptyValue<KeyTraits>(Extractor::extract(value)); } 3165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static bool isDeletedBucket(const ValueType& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); } 3175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value) || isDeletedBucket(value); } 3185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueType* lookup(const Key& key) { return lookup<IdentityTranslatorType>(key); } 3205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename HashTranslator, typename T> ValueType* lookup(const T&); 3215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 3235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static ValueType* allocateTable(int size); 3245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static void deallocateTable(ValueType* table, int size); 3255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef std::pair<ValueType*, bool> LookupType; 3275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef std::pair<LookupType, unsigned> FullLookupType; 3285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) LookupType lookupForWriting(const Key& key) { return lookupForWriting<IdentityTranslatorType>(key); }; 3305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename HashTranslator, typename T> FullLookupType fullLookupForWriting(const T&); 3315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename HashTranslator, typename T> LookupType lookupForWriting(const T&); 3325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void remove(ValueType*); 3345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool shouldExpand() const { return (m_keyCount + m_deletedCount) * m_maxLoad >= m_tableSize; } 3365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool mustRehashInPlace() const { return m_keyCount * m_minLoad < m_tableSize * 2; } 3375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool shouldShrink() const { return m_keyCount * m_minLoad < m_tableSize && m_tableSize > KeyTraits::minimumTableSize; } 3385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void expand(); 3395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void shrink() { rehash(m_tableSize / 2); } 3405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void rehash(int newTableSize); 3425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void reinsert(ValueType&); 3435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static void initializeBucket(ValueType& bucket); 3455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static void deleteBucket(ValueType& bucket) { bucket.~ValueType(); Traits::constructDeletedValue(bucket); } 3465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) FullLookupType makeLookupResult(ValueType* position, bool found, unsigned hash) 3485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { return FullLookupType(LookupType(position, found), hash); } 3495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator makeIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize); } 3515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_iterator makeConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize); } 3525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator makeKnownGoodIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); } 3535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_iterator makeKnownGoodConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); } 3545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const int m_maxLoad = 2; 3565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const int m_minLoad = 6; 3575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueType* m_table; 3595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int m_tableSize; 3605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int m_tableSizeMask; 3615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int m_keyCount; 3625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int m_deletedCount; 3635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS_PER_TABLE 3655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) public: 3665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) mutable OwnPtr<Stats> m_stats; 3675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 3685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 3695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Set all the bits to one after the most significant bit: 00110101010 -> 00111111111. 3715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<unsigned size> struct OneifyLowBits; 3725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<> 3735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct OneifyLowBits<0> { 3745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const unsigned value = 0; 3755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 3765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<unsigned number> 3775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct OneifyLowBits { 3785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const unsigned value = number | OneifyLowBits<(number >> 1)>::value; 3795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 3805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Compute the first power of two integer that is an upper bound of the parameter 'number'. 3815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<unsigned number> 3825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct UpperPowerOfTwoBound { 3835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const unsigned value = (OneifyLowBits<number - 1>::value + 1) * 2; 3845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 3855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Because power of two numbers are the limit of maxLoad, their capacity is twice the 3875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // UpperPowerOfTwoBound, or 4 times their values. 3885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<unsigned size, bool isPowerOfTwo> struct HashTableCapacityForSizeSplitter; 3895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<unsigned size> 3905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct HashTableCapacityForSizeSplitter<size, true> { 3915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const unsigned value = size * 4; 3925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 3935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<unsigned size> 3945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct HashTableCapacityForSizeSplitter<size, false> { 3955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const unsigned value = UpperPowerOfTwoBound<size>::value; 3965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 3975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // HashTableCapacityForSize computes the upper power of two capacity to hold the size parameter. 3995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // This is done at compile time to initialize the HashTraits. 4005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<unsigned size> 4015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct HashTableCapacityForSize { 4025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const unsigned value = HashTableCapacityForSizeSplitter<size, !(size & (size - 1))>::value; 4035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) COMPILE_ASSERT(size > 0, HashTableNonZeroMinimumCapacity); 4045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) COMPILE_ASSERT(!static_cast<int>(value >> 31), HashTableNoCapacityOverflow); 4055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) COMPILE_ASSERT(value > (2 * size), HashTableCapacityHoldsContentSize); 4065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 4075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 4095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable() 4105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : m_table(0) 4115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_tableSize(0) 4125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_tableSizeMask(0) 4135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_keyCount(0) 4145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_deletedCount(0) 4155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS_PER_TABLE 4165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_stats(adoptPtr(new Stats)) 4175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 4185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline unsigned doubleHash(unsigned key) 4225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) key = ~key + (key >> 23); 4245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) key ^= (key << 12); 4255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) key ^= (key >> 7); 4265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) key ^= (key << 2); 4275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) key ^= (key >> 20); 4285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return key; 4295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 4325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename HashTranslator, typename T> 4335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookup(const T& key) 4345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int k = 0; 4365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int sizeMask = m_tableSizeMask; 4375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueType* table = m_table; 4385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unsigned h = HashTranslator::hash(key); 4395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int i = h & sizeMask; 4405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!table) 4425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 0; 4435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS 4455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) atomicIncrement(&HashTableStats::numAccesses); 4465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int probeCount = 0; 4475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 4485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS_PER_TABLE 4505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++m_stats->numAccesses; 4515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int perTableProbeCount = 0; 4525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 4535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (1) { 4555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueType* entry = table + i; 45602772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 4575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // we count on the compiler to optimize out this branch 4585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (HashFunctions::safeToCompareToEmptyOrDeleted) { 4595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (HashTranslator::equal(Extractor::extract(*entry), key)) 4605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return entry; 46102772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 4625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (isEmptyBucket(*entry)) 4635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 0; 4645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 4655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (isEmptyBucket(*entry)) 4665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 0; 46702772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 4685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!isDeletedBucket(*entry) && HashTranslator::equal(Extractor::extract(*entry), key)) 4695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return entry; 4705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS 4725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++probeCount; 4735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashTableStats::recordCollisionAtCount(probeCount); 4745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 4755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS_PER_TABLE 4775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++perTableProbeCount; 4785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_stats->recordCollisionAtCount(perTableProbeCount); 4795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 4805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 481591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch if (!k) 4825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k = 1 | doubleHash(h); 4835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) i = (i + k) & sizeMask; 4845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 4885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename HashTranslator, typename T> 4895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::LookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookupForWriting(const T& key) 4905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(m_table); 4925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int k = 0; 4945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueType* table = m_table; 4955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int sizeMask = m_tableSizeMask; 4965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unsigned h = HashTranslator::hash(key); 4975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int i = h & sizeMask; 4985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS 5005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) atomicIncrement(&HashTableStats::numAccesses); 5015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int probeCount = 0; 5025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 5035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS_PER_TABLE 5055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++m_stats->numAccesses; 5065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int perTableProbeCount = 0; 5075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 5085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueType* deletedEntry = 0; 5105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (1) { 5125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueType* entry = table + i; 51302772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 5145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // we count on the compiler to optimize out this branch 5155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (HashFunctions::safeToCompareToEmptyOrDeleted) { 5165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (isEmptyBucket(*entry)) 5175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return LookupType(deletedEntry ? deletedEntry : entry, false); 51802772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 5195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (HashTranslator::equal(Extractor::extract(*entry), key)) 5205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return LookupType(entry, true); 52102772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 5225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (isDeletedBucket(*entry)) 5235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) deletedEntry = entry; 5245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 5255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (isEmptyBucket(*entry)) 5265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return LookupType(deletedEntry ? deletedEntry : entry, false); 52702772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 5285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (isDeletedBucket(*entry)) 5295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) deletedEntry = entry; 5305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else if (HashTranslator::equal(Extractor::extract(*entry), key)) 5315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return LookupType(entry, true); 5325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS 5345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++probeCount; 5355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashTableStats::recordCollisionAtCount(probeCount); 5365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 5375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS_PER_TABLE 5395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++perTableProbeCount; 5405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_stats->recordCollisionAtCount(perTableProbeCount); 5415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 5425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 543591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch if (!k) 5445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k = 1 | doubleHash(h); 5455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) i = (i + k) & sizeMask; 5465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 5505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename HashTranslator, typename T> 5515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::fullLookupForWriting(const T& key) 5525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 5535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(m_table); 5545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int k = 0; 5565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueType* table = m_table; 5575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int sizeMask = m_tableSizeMask; 5585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unsigned h = HashTranslator::hash(key); 5595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int i = h & sizeMask; 5605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS 5625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) atomicIncrement(&HashTableStats::numAccesses); 5635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int probeCount = 0; 5645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 5655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS_PER_TABLE 5675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++m_stats->numAccesses; 5685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int perTableProbeCount = 0; 5695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 5705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueType* deletedEntry = 0; 5725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (1) { 5745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueType* entry = table + i; 57502772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 5765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // we count on the compiler to optimize out this branch 5775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (HashFunctions::safeToCompareToEmptyOrDeleted) { 5785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (isEmptyBucket(*entry)) 5795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h); 58002772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 5815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (HashTranslator::equal(Extractor::extract(*entry), key)) 5825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return makeLookupResult(entry, true, h); 58302772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 5845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (isDeletedBucket(*entry)) 5855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) deletedEntry = entry; 5865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 5875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (isEmptyBucket(*entry)) 5885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h); 58902772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 5905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (isDeletedBucket(*entry)) 5915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) deletedEntry = entry; 5925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else if (HashTranslator::equal(Extractor::extract(*entry), key)) 5935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return makeLookupResult(entry, true, h); 5945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS 5965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++probeCount; 5975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashTableStats::recordCollisionAtCount(probeCount); 5985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 5995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS_PER_TABLE 6015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++perTableProbeCount; 6025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_stats->recordCollisionAtCount(perTableProbeCount); 6035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 6045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 605591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch if (!k) 6065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k = 1 | doubleHash(h); 6075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) i = (i + k) & sizeMask; 6085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<bool emptyValueIsZero> struct HashTableBucketInitializer; 6125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<> struct HashTableBucketInitializer<false> { 6145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Traits, typename Value> static void initialize(Value& bucket) 6155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 6165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) new (NotNull, &bucket) Value(Traits::emptyValue()); 6175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 6195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<> struct HashTableBucketInitializer<true> { 6215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Traits, typename Value> static void initialize(Value& bucket) 6225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 6235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // This initializes the bucket without copying the empty value. 6245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // That makes it possible to use this with types that don't support copying. 6255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The memset to 0 looks like a slow operation but is optimized by the compilers. 6265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) memset(&bucket, 0, sizeof(bucket)); 6275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 62902772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 6305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 6315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::initializeBucket(ValueType& bucket) 6325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 6335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashTableBucketInitializer<Traits::emptyValueIsZero>::template initialize<Traits>(bucket); 6345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 6375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename HashTranslator, typename T, typename Extra> 63893ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::AddResult HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::add(const T& key, const Extra& extra) 6395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 6405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!m_table) 6415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) expand(); 6425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(m_table); 6445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int k = 0; 6465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueType* table = m_table; 6475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int sizeMask = m_tableSizeMask; 6485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unsigned h = HashTranslator::hash(key); 6495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int i = h & sizeMask; 6505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS 6525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) atomicIncrement(&HashTableStats::numAccesses); 6535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int probeCount = 0; 6545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 6555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS_PER_TABLE 6575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++m_stats->numAccesses; 6585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int perTableProbeCount = 0; 6595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 6605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueType* deletedEntry = 0; 6625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueType* entry; 6635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (1) { 6645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) entry = table + i; 66502772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 6665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // we count on the compiler to optimize out this branch 6675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (HashFunctions::safeToCompareToEmptyOrDeleted) { 6685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (isEmptyBucket(*entry)) 6695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 67002772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 6715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (HashTranslator::equal(Extractor::extract(*entry), key)) 6725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return AddResult(makeKnownGoodIterator(entry), false); 67302772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 6745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (isDeletedBucket(*entry)) 6755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) deletedEntry = entry; 6765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 6775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (isEmptyBucket(*entry)) 6785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 67902772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 6805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (isDeletedBucket(*entry)) 6815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) deletedEntry = entry; 6825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else if (HashTranslator::equal(Extractor::extract(*entry), key)) 6835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return AddResult(makeKnownGoodIterator(entry), false); 6845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS 6865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++probeCount; 6875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashTableStats::recordCollisionAtCount(probeCount); 6885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 6895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS_PER_TABLE 6915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++perTableProbeCount; 6925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_stats->recordCollisionAtCount(perTableProbeCount); 6935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 6945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 695591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch if (!k) 6965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k = 1 | doubleHash(h); 6975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) i = (i + k) & sizeMask; 6985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (deletedEntry) { 7015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) initializeBucket(*deletedEntry); 7025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) entry = deletedEntry; 70302772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch --m_deletedCount; 7045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashTranslator::translate(*entry, key, extra); 7075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++m_keyCount; 70902772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 7105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (shouldExpand()) { 7115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // FIXME: This makes an extra copy on expand. Probably not that bad since 7125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // expand is rare, but would be better to have a version of expand that can 7135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // follow a pivot entry and return the new position. 7145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) KeyType enteredKey = Extractor::extract(*entry); 7155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) expand(); 7165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) AddResult result(find(enteredKey), true); 7175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(result.iterator != end()); 7185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 7195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 72002772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 7215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return AddResult(makeKnownGoodIterator(entry), true); 7225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 7255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename HashTranslator, typename T, typename Extra> 72693ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::AddResult HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::addPassingHashCode(const T& key, const Extra& extra) 7275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 7285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!m_table) 7295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) expand(); 7305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) FullLookupType lookupResult = fullLookupForWriting<HashTranslator>(key); 7325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueType* entry = lookupResult.first.first; 7345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool found = lookupResult.first.second; 7355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unsigned h = lookupResult.second; 73602772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 7375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (found) 7385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return AddResult(makeKnownGoodIterator(entry), false); 73902772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 7405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (isDeletedBucket(*entry)) { 7415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) initializeBucket(*entry); 7425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) --m_deletedCount; 7435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 74402772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 7455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashTranslator::translate(*entry, key, extra, h); 7465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++m_keyCount; 7475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (shouldExpand()) { 7485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // FIXME: This makes an extra copy on expand. Probably not that bad since 7495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // expand is rare, but would be better to have a version of expand that can 7505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // follow a pivot entry and return the new position. 7515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) KeyType enteredKey = Extractor::extract(*entry); 7525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) expand(); 7535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) AddResult result(find(enteredKey), true); 7545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(result.iterator != end()); 7555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 7565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return AddResult(makeKnownGoodIterator(entry), true); 7595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 7625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::reinsert(ValueType& entry) 7635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 7645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(m_table); 7655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(!lookupForWriting(Extractor::extract(entry)).second); 7665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(!isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first))); 7675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS 7685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) atomicIncrement(&HashTableStats::numReinserts); 7695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 7705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS_PER_TABLE 7715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++m_stats->numReinserts; 7725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 7735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Mover<ValueType, Traits::needsDestruction>::move(entry, *lookupForWriting(Extractor::extract(entry)).first); 7755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 77802772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch template <typename HashTranslator, typename T> 7795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key) 7805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 7815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!m_table) 7825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return end(); 7835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueType* entry = lookup<HashTranslator>(key); 7855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!entry) 7865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return end(); 7875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return makeKnownGoodIterator(entry); 7895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 79202772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch template <typename HashTranslator, typename T> 7935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::const_iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key) const 7945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 7955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!m_table) 7965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return end(); 7975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueType* entry = const_cast<HashTable*>(this)->lookup<HashTranslator>(key); 7995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!entry) 8005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return end(); 8015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return makeKnownGoodConstIterator(entry); 8035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 80602772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch template <typename HashTranslator, typename T> 8075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::contains(const T& key) const 8085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 8095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!m_table) 8105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 8115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return const_cast<HashTable*>(this)->lookup<HashTranslator>(key); 8135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 8165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(ValueType* pos) 8175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 8185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS 8195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) atomicIncrement(&HashTableStats::numRemoves); 8205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 8215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS_PER_TABLE 8225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++m_stats->numRemoves; 8235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 8245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) deleteBucket(*pos); 8265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++m_deletedCount; 8275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) --m_keyCount; 8285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (shouldShrink()) 8305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) shrink(); 8315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 8345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(iterator it) 8355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 8365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (it == end()) 8375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 8385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 839e6d4491e48613634a83c1957c72759da80987961Ben Murdoch remove(const_cast<ValueType*>(it.m_iterator.m_position)); 8405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 843e6d4491e48613634a83c1957c72759da80987961Ben Murdoch inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(const_iterator it) 8445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 8455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (it == end()) 8465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 8475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 848e6d4491e48613634a83c1957c72759da80987961Ben Murdoch remove(const_cast<ValueType*>(it.m_position)); 8495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 8525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(const KeyType& key) 8535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 8545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) remove(find(key)); 8555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 8585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::allocateTable(int size) 8595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 8605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // would use a template member function with explicit specializations here, but 8615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // gcc doesn't appear to support that 8625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (Traits::emptyValueIsZero) 8635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return static_cast<ValueType*>(fastZeroedMalloc(size * sizeof(ValueType))); 8645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueType* result = static_cast<ValueType*>(fastMalloc(size * sizeof(ValueType))); 8655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i < size; i++) 8665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) initializeBucket(result[i]); 8675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 8685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 8715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType* table, int size) 8725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 8735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (Traits::needsDestruction) { 8745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i < size; ++i) { 8755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!isDeletedBucket(table[i])) 8765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) table[i].~ValueType(); 8775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) fastFree(table); 8805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 8835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::expand() 8845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 8855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int newSize; 8865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (m_tableSize == 0) 8875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) newSize = KeyTraits::minimumTableSize; 8885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else if (mustRehashInPlace()) 8895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) newSize = m_tableSize; 8905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else 8915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) newSize = m_tableSize * 2; 8925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) rehash(newSize); 8945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 8975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::rehash(int newTableSize) 8985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 8995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int oldTableSize = m_tableSize; 9005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueType* oldTable = m_table; 9015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS 9035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (oldTableSize != 0) 9045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) atomicIncrement(&HashTableStats::numRehashes); 9055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 9065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS_PER_TABLE 9085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (oldTableSize != 0) 9095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++m_stats->numRehashes; 9105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 9115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_tableSize = newTableSize; 9135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_tableSizeMask = newTableSize - 1; 9145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_table = allocateTable(newTableSize); 9155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i != oldTableSize; ++i) 9175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!isEmptyOrDeletedBucket(oldTable[i])) 9185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) reinsert(oldTable[i]); 9195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_deletedCount = 0; 9215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) deallocateTable(oldTable, oldTableSize); 9235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 9265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::clear() 9275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 9285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!m_table) 9295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 9305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) deallocateTable(m_table, m_tableSize); 9325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_table = 0; 9335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_tableSize = 0; 9345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_tableSizeMask = 0; 9355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_keyCount = 0; 9365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 9395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable(const HashTable& other) 9405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : m_table(0) 9415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_tableSize(0) 9425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_tableSizeMask(0) 9435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_keyCount(0) 9445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_deletedCount(0) 9455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS_PER_TABLE 9465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_stats(adoptPtr(new Stats(*other.m_stats))) 9475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 9485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 9495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Copy the hash table the dumb way, by adding each element to the new table. 9505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // It might be more efficient to copy the table slots, but it's not clear that efficiency is needed. 9515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_iterator end = other.end(); 9525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (const_iterator it = other.begin(); it != end; ++it) 9535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) add(*it); 9545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 9575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::swap(HashTable& other) 9585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 9595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueType* tmp_table = m_table; 9605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_table = other.m_table; 9615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) other.m_table = tmp_table; 9625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int tmp_tableSize = m_tableSize; 9645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_tableSize = other.m_tableSize; 9655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) other.m_tableSize = tmp_tableSize; 9665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int tmp_tableSizeMask = m_tableSizeMask; 9685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_tableSizeMask = other.m_tableSizeMask; 9695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) other.m_tableSizeMask = tmp_tableSizeMask; 9705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int tmp_keyCount = m_keyCount; 9725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_keyCount = other.m_keyCount; 9735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) other.m_keyCount = tmp_keyCount; 9745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int tmp_deletedCount = m_deletedCount; 9765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_deletedCount = other.m_deletedCount; 9775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) other.m_deletedCount = tmp_deletedCount; 9785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if DUMP_HASHTABLE_STATS_PER_TABLE 9805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_stats.swap(other.m_stats); 9815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 9825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 9855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>& HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::operator=(const HashTable& other) 9865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 9875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashTable tmp(other); 9885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) swap(tmp); 9895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return *this; 9905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // iterator adapters 9935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename HashTableType, typename ValueType> struct HashTableConstIteratorAdapter { 9955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashTableConstIteratorAdapter() {} 9965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashTableConstIteratorAdapter(const typename HashTableType::const_iterator& impl) : m_impl(impl) {} 9975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const ValueType* get() const { return (const ValueType*)m_impl.get(); } 9995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const ValueType& operator*() const { return *get(); } 10005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const ValueType* operator->() const { return get(); } 10015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashTableConstIteratorAdapter& operator++() { ++m_impl; return *this; } 10035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // postfix ++ intentionally omitted 10045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typename HashTableType::const_iterator m_impl; 10065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 10075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename HashTableType, typename ValueType> struct HashTableIteratorAdapter { 10095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashTableIteratorAdapter() {} 10105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashTableIteratorAdapter(const typename HashTableType::iterator& impl) : m_impl(impl) {} 10115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueType* get() const { return (ValueType*)m_impl.get(); } 10135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueType& operator*() const { return *get(); } 10145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueType* operator->() const { return get(); } 10155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashTableIteratorAdapter& operator++() { ++m_impl; return *this; } 10175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // postfix ++ intentionally omitted 10185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) operator HashTableConstIteratorAdapter<HashTableType, ValueType>() { 10205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typename HashTableType::const_iterator i = m_impl; 10215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return i; 10225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typename HashTableType::iterator m_impl; 10255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 10265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, typename U> 10285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b) 10295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 10305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return a.m_impl == b.m_impl; 10315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, typename U> 10345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b) 10355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 10365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return a.m_impl != b.m_impl; 10375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, typename U> 10405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b) 10415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 10425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return a.m_impl == b.m_impl; 10435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, typename U> 10465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b) 10475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 10485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return a.m_impl != b.m_impl; 10495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // All 4 combinations of ==, != and Const,non const. 10525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, typename U> 10535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b) 10545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 10555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return a.m_impl == b.m_impl; 10565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, typename U> 10595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b) 10605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 10615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return a.m_impl != b.m_impl; 10625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, typename U> 10655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b) 10665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 10675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return a.m_impl == b.m_impl; 10685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, typename U> 10715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b) 10725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 10735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return a.m_impl != b.m_impl; 10745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} // namespace WTF 10775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1078591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "wtf/HashIterators.h" 10795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif // WTF_HashTable_h 1081