18e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project/* 28e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved. 3635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project * Copyright (C) 2008 David Levin <levin@chromium.org> 48e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 58e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * This library is free software; you can redistribute it and/or 68e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * modify it under the terms of the GNU Library General Public 78e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * License as published by the Free Software Foundation; either 88e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * version 2 of the License, or (at your option) any later version. 98e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * This library is distributed in the hope that it will be useful, 118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * but WITHOUT ANY WARRANTY; without even the implied warranty of 128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Library General Public License for more details. 148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * You should have received a copy of the GNU Library General Public License 168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * along with this library; see the file COPYING.LIB. If not, write to 178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Boston, MA 02110-1301, USA. 198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project */ 218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifndef WTF_HashTable_h 238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define WTF_HashTable_h 248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#include "FastMalloc.h" 268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#include "HashTraits.h" 278a0914b749bbe7da7768e07a7db5c6d4bb09472bSteve Block#include "ValueCheck.h" 288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#include <wtf/Assertions.h> 29635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project#include <wtf/Threading.h> 308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectnamespace WTF { 328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define DUMP_HASHTABLE_STATS 0 34d0825bca7fe65beaee391d30da42e937db621564Steve Block// Enables internal WTF consistency checks that are invoked automatically. Non-WTF callers can call checkTableConsistency() even if internal checks are disabled. 358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define CHECK_HASHTABLE_CONSISTENCY 0 368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifdef NDEBUG 388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define CHECK_HASHTABLE_ITERATORS 0 398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define CHECK_HASHTABLE_USE_AFTER_DESTRUCTION 0 408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#else 418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define CHECK_HASHTABLE_ITERATORS 1 428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define CHECK_HASHTABLE_USE_AFTER_DESTRUCTION 1 438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#if DUMP_HASHTABLE_STATS 468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project struct HashTableStats { 488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ~HashTableStats(); 49635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project // All of the variables are accessed in ~HashTableStats when the static struct is destroyed. 50635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project 51635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project // The following variables are all atomically incremented when modified. 528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static int numAccesses; 538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static int numRehashes; 548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static int numRemoves; 558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static int numReinserts; 56635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project 57635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project // The following variables are only modified in the recordCollisionAtCount method within a mutex. 58635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project static int maxCollisions; 59635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project static int numCollisions; 60635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project static int collisionGraph[4096]; 61635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project 628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static void recordCollisionAtCount(int count); 638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project class HashTable; 698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project class HashTableIterator; 718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project class HashTableConstIterator; 738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*, 768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*); 778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*); 808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#if !CHECK_HASHTABLE_ITERATORS 828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*, 858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*) { } 868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*) { } 898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef enum { HashItemKnownGood } HashItemKnownGoodTag; 938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project class HashTableConstIterator { 968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType; 988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator; 998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator; 1008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef Value ValueType; 1018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef const ValueType& ReferenceType; 1028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef const ValueType* PointerType; 1038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>; 1058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project friend class HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>; 1068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void skipEmptyBuckets() 1088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project while (m_position != m_endPosition && HashTableType::isEmptyOrDeletedBucket(*m_position)) 1108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ++m_position; 1118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashTableConstIterator(const HashTableType* table, PointerType position, PointerType endPosition) 1148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project : m_position(position), m_endPosition(endPosition) 1158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project addIterator(table, this); 1178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project skipEmptyBuckets(); 1188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashTableConstIterator(const HashTableType* table, PointerType position, PointerType endPosition, HashItemKnownGoodTag) 1218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project : m_position(position), m_endPosition(endPosition) 1228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project addIterator(table, this); 1248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project public: 1278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashTableConstIterator() 1288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project addIterator(0, this); 1308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // default copy, assignment and destructor are OK if CHECK_HASHTABLE_ITERATORS is 0 1338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#if CHECK_HASHTABLE_ITERATORS 1358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ~HashTableConstIterator() 1368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project removeIterator(this); 1388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashTableConstIterator(const const_iterator& other) 1418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project : m_position(other.m_position), m_endPosition(other.m_endPosition) 1428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project addIterator(other.m_table, this); 1448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const_iterator& operator=(const const_iterator& other) 1478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_position = other.m_position; 1498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_endPosition = other.m_endPosition; 1508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project removeIterator(this); 1528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project addIterator(other.m_table, this); 1538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return *this; 1558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 1578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project PointerType get() const 1598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(); 1618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return m_position; 1628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ReferenceType operator*() const { return *get(); } 1648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project PointerType operator->() const { return get(); } 1658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const_iterator& operator++() 1678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(); 1698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(m_position != m_endPosition); 1708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ++m_position; 1718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project skipEmptyBuckets(); 1728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return *this; 1738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // postfix ++ intentionally omitted 1768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Comparison. 1788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool operator==(const const_iterator& other) const 1798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(other); 1818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return m_position == other.m_position; 1828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool operator!=(const const_iterator& other) const 1848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkValidity(other); 1868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return m_position != other.m_position; 1878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 1908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void checkValidity() const 1918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#if CHECK_HASHTABLE_ITERATORS 1938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(m_table); 1948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 1958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#if CHECK_HASHTABLE_ITERATORS 1998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void checkValidity(const const_iterator& other) const 2008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 2018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(m_table); 202d0825bca7fe65beaee391d30da42e937db621564Steve Block ASSERT_UNUSED(other, other.m_table); 2038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(m_table == other.m_table); 2048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#else 2068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void checkValidity(const const_iterator&) const { } 2078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 2088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project PointerType m_position; 2108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project PointerType m_endPosition; 2118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#if CHECK_HASHTABLE_ITERATORS 2138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project public: 214635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project // Any modifications of the m_next or m_previous of an iterator that is in a linked list of a HashTable::m_iterator, 215635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project // should be guarded with m_table->m_mutex. 2168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project mutable const HashTableType* m_table; 2178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project mutable const_iterator* m_next; 2188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project mutable const_iterator* m_previous; 2198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 2208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 2218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 2238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project class HashTableIterator { 2248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 2258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType; 2268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator; 2278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator; 2288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef Value ValueType; 2298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef ValueType& ReferenceType; 2308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef ValueType* PointerType; 2318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>; 2338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashTableIterator(HashTableType* table, PointerType pos, PointerType end) : m_iterator(table, pos, end) { } 2358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashTableIterator(HashTableType* table, PointerType pos, PointerType end, HashItemKnownGoodTag tag) : m_iterator(table, pos, end, tag) { } 2368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project public: 2388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashTableIterator() { } 2398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // default copy, assignment and destructor are OK 2418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project PointerType get() const { return const_cast<PointerType>(m_iterator.get()); } 2438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ReferenceType operator*() const { return *get(); } 2448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project PointerType operator->() const { return get(); } 2458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project iterator& operator++() { ++m_iterator; return *this; } 2478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // postfix ++ intentionally omitted 2498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Comparison. 2518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; } 2528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; } 2538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project operator const_iterator() const { return m_iterator; } 2558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 2578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const_iterator m_iterator; 2588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 2598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project using std::swap; 2618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2622daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch // Work around MSVC's standard library, whose swap for pairs does not swap by component. 2632daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch template<typename T> inline void hashTableSwap(T& a, T& b) 2642daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch { 2652daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch swap(a, b); 2662daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch } 2678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2682daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch // Swap pairs by component, in case of pair members that specialize swap. 2692daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch template<typename T, typename U> inline void hashTableSwap(pair<T, U>& a, pair<T, U>& b) 2708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 2718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project swap(a.first, b.first); 2728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project swap(a.second, b.second); 2738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, bool useSwap> struct Mover; 2762daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch template<typename T> struct Mover<T, true> { static void move(T& from, T& to) { hashTableSwap(from, to); } }; 2778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T> struct Mover<T, false> { static void move(T& from, T& to) { to = from; } }; 2788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename HashFunctions> class IdentityHashTranslator { 2808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project public: 2818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static unsigned hash(const Key& key) { return HashFunctions::hash(key); } 2828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static bool equal(const Key& a, const Key& b) { return HashFunctions::equal(a, b); } 2838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static void translate(Value& location, const Key&, const Value& value) { location = value; } 2848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 2858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 2878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project class HashTable { 2888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project public: 2898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator; 2908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator; 2918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef Traits ValueTraits; 2928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef Key KeyType; 2938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef Value ValueType; 2948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef IdentityHashTranslator<Key, Value, HashFunctions> IdentityTranslatorType; 2958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashTable(); 2978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ~HashTable() 2988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 2998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project invalidateIterators(); 3008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project deallocateTable(m_table, m_tableSize); 3018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#if CHECK_HASHTABLE_USE_AFTER_DESTRUCTION 3028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_table = (ValueType*)(uintptr_t)0xbbadbeef; 3038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 3048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashTable(const HashTable&); 3078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void swap(HashTable&); 3088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashTable& operator=(const HashTable&); 3098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project iterator begin() { return makeIterator(m_table); } 3118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project iterator end() { return makeKnownGoodIterator(m_table + m_tableSize); } 3128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const_iterator begin() const { return makeConstIterator(m_table); } 3138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const_iterator end() const { return makeKnownGoodConstIterator(m_table + m_tableSize); } 3148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int size() const { return m_keyCount; } 3168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int capacity() const { return m_tableSize; } 3178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool isEmpty() const { return !m_keyCount; } 3188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project pair<iterator, bool> add(const ValueType& value) { return add<KeyType, ValueType, IdentityTranslatorType>(Extractor::extract(value), value); } 3208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // A special version of add() that finds the object by hashing and comparing 3228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // with some other type, to avoid the cost of type conversion if the object is already 3238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // in the table. 3248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename Extra, typename HashTranslator> pair<iterator, bool> add(const T& key, const Extra&); 3258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename Extra, typename HashTranslator> pair<iterator, bool> addPassingHashCode(const T& key, const Extra&); 3268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project iterator find(const KeyType& key) { return find<KeyType, IdentityTranslatorType>(key); } 3288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const_iterator find(const KeyType& key) const { return find<KeyType, IdentityTranslatorType>(key); } 3298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool contains(const KeyType& key) const { return contains<KeyType, IdentityTranslatorType>(key); } 3308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template <typename T, typename HashTranslator> iterator find(const T&); 3328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template <typename T, typename HashTranslator> const_iterator find(const T&) const; 3338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template <typename T, typename HashTranslator> bool contains(const T&) const; 3348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void remove(const KeyType&); 3368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void remove(iterator); 3378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void removeWithoutEntryConsistencyCheck(iterator); 338ca9cb53ed1119a3fd98fafa0972ffeb56dee1c24Steve Block void removeWithoutEntryConsistencyCheck(const_iterator); 3398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void clear(); 3408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static bool isEmptyBucket(const ValueType& value) { return Extractor::extract(value) == KeyTraits::emptyValue(); } 3428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static bool isDeletedBucket(const ValueType& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); } 3438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value) || isDeletedBucket(value); } 3448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ValueType* lookup(const Key& key) { return lookup<Key, IdentityTranslatorType>(key); } 3468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename HashTranslator> ValueType* lookup(const T&); 3478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 348d0825bca7fe65beaee391d30da42e937db621564Steve Block#if !ASSERT_DISABLED 3498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void checkTableConsistency() const; 3508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#else 3518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static void checkTableConsistency() { } 3528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 353d0825bca7fe65beaee391d30da42e937db621564Steve Block#if CHECK_HASHTABLE_CONSISTENCY 354d0825bca7fe65beaee391d30da42e937db621564Steve Block void internalCheckTableConsistency() const { checkTableConsistency(); } 355d0825bca7fe65beaee391d30da42e937db621564Steve Block void internalCheckTableConsistencyExceptSize() const { checkTableConsistencyExceptSize(); } 356d0825bca7fe65beaee391d30da42e937db621564Steve Block#else 357d0825bca7fe65beaee391d30da42e937db621564Steve Block static void internalCheckTableConsistencyExceptSize() { } 358d0825bca7fe65beaee391d30da42e937db621564Steve Block static void internalCheckTableConsistency() { } 359d0825bca7fe65beaee391d30da42e937db621564Steve Block#endif 3608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 3628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static ValueType* allocateTable(int size); 3638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static void deallocateTable(ValueType* table, int size); 3648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef pair<ValueType*, bool> LookupType; 3668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef pair<LookupType, unsigned> FullLookupType; 3678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project LookupType lookupForWriting(const Key& key) { return lookupForWriting<Key, IdentityTranslatorType>(key); }; 3698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename HashTranslator> FullLookupType fullLookupForWriting(const T&); 3708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename HashTranslator> LookupType lookupForWriting(const T&); 3718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename HashTranslator> void checkKey(const T&); 3738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void removeAndInvalidateWithoutEntryConsistencyCheck(ValueType*); 3758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void removeAndInvalidate(ValueType*); 3768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void remove(ValueType*); 3778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool shouldExpand() const { return (m_keyCount + m_deletedCount) * m_maxLoad >= m_tableSize; } 3798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool mustRehashInPlace() const { return m_keyCount * m_minLoad < m_tableSize * 2; } 3808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool shouldShrink() const { return m_keyCount * m_minLoad < m_tableSize && m_tableSize > m_minTableSize; } 3818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void expand(); 3828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void shrink() { rehash(m_tableSize / 2); } 3838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void rehash(int newTableSize); 3858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void reinsert(ValueType&); 3868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static void initializeBucket(ValueType& bucket) { new (&bucket) ValueType(Traits::emptyValue()); } 3888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static void deleteBucket(ValueType& bucket) { bucket.~ValueType(); Traits::constructDeletedValue(bucket); } 3898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project FullLookupType makeLookupResult(ValueType* position, bool found, unsigned hash) 3918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { return FullLookupType(LookupType(position, found), hash); } 3928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project iterator makeIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize); } 3948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const_iterator makeConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize); } 3958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project iterator makeKnownGoodIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); } 3968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const_iterator makeKnownGoodConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); } 3978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 398d0825bca7fe65beaee391d30da42e937db621564Steve Block#if !ASSERT_DISABLED 3998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void checkTableConsistencyExceptSize() const; 4008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#else 4018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static void checkTableConsistencyExceptSize() { } 4028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 4038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#if CHECK_HASHTABLE_ITERATORS 4058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void invalidateIterators(); 4068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#else 4078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static void invalidateIterators() { } 4088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 4098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static const int m_minTableSize = 64; 4118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static const int m_maxLoad = 2; 4128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static const int m_minLoad = 6; 4138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ValueType* m_table; 4158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int m_tableSize; 4168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int m_tableSizeMask; 4178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int m_keyCount; 4188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int m_deletedCount; 4198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#if CHECK_HASHTABLE_ITERATORS 4218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project public: 422635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project // All access to m_iterators should be guarded with m_mutex. 4238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project mutable const_iterator* m_iterators; 424635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project mutable Mutex m_mutex; 4258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 4268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 4278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 4298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable() 4308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project : m_table(0) 4318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project , m_tableSize(0) 4328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project , m_tableSizeMask(0) 4338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project , m_keyCount(0) 4348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project , m_deletedCount(0) 4358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#if CHECK_HASHTABLE_ITERATORS 4368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project , m_iterators(0) 4378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 4388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 4398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 4408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static inline unsigned doubleHash(unsigned key) 4428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 4438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project key = ~key + (key >> 23); 4448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project key ^= (key << 12); 4458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project key ^= (key >> 7); 4468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project key ^= (key << 2); 4478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project key ^= (key >> 20); 4488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return key; 4498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 4508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#if ASSERT_DISABLED 4528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 4548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename HashTranslator> 4558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T&) 4568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 4578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 4588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#else 4608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 4628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename HashTranslator> 4638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T& key) 4648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 4658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!HashFunctions::safeToCompareToEmptyOrDeleted) 4668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return; 4678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(!HashTranslator::equal(KeyTraits::emptyValue(), key)); 4688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ValueType deletedValue = Traits::emptyValue(); 4698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project deletedValue.~ValueType(); 4708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Traits::constructDeletedValue(deletedValue); 4718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(!HashTranslator::equal(Extractor::extract(deletedValue), key)); 4728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project new (&deletedValue) ValueType(Traits::emptyValue()); 4738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 4748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 4768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 4788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename HashTranslator> 4798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookup(const T& key) 4808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 4818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkKey<T, HashTranslator>(key); 4828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int k = 0; 4848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int sizeMask = m_tableSizeMask; 4858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ValueType* table = m_table; 4868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project unsigned h = HashTranslator::hash(key); 4878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int i = h & sizeMask; 4888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!table) 4908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return 0; 4918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#if DUMP_HASHTABLE_STATS 493635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project atomicIncrement(&HashTableStats::numAccesses); 4948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int probeCount = 0; 4958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 4968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project while (1) { 4988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ValueType* entry = table + i; 4998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // we count on the compiler to optimize out this branch 5018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (HashFunctions::safeToCompareToEmptyOrDeleted) { 5028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (HashTranslator::equal(Extractor::extract(*entry), key)) 5038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return entry; 5048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (isEmptyBucket(*entry)) 5068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return 0; 5078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { 5088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (isEmptyBucket(*entry)) 5098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return 0; 5108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!isDeletedBucket(*entry) && HashTranslator::equal(Extractor::extract(*entry), key)) 5128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return entry; 5138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#if DUMP_HASHTABLE_STATS 5158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ++probeCount; 5168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashTableStats::recordCollisionAtCount(probeCount); 5178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 5188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (k == 0) 5198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project k = 1 | doubleHash(h); 5208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project i = (i + k) & sizeMask; 5218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 5258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename HashTranslator> 5268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::LookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookupForWriting(const T& key) 5278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 5288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(m_table); 5298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkKey<T, HashTranslator>(key); 5308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int k = 0; 5328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ValueType* table = m_table; 5338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int sizeMask = m_tableSizeMask; 5348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project unsigned h = HashTranslator::hash(key); 5358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int i = h & sizeMask; 5368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#if DUMP_HASHTABLE_STATS 538635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project atomicIncrement(&HashTableStats::numAccesses); 5398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int probeCount = 0; 5408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 5418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ValueType* deletedEntry = 0; 5438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project while (1) { 5458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ValueType* entry = table + i; 5468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // we count on the compiler to optimize out this branch 5488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (HashFunctions::safeToCompareToEmptyOrDeleted) { 5498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (isEmptyBucket(*entry)) 5508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return LookupType(deletedEntry ? deletedEntry : entry, false); 5518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (HashTranslator::equal(Extractor::extract(*entry), key)) 5538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return LookupType(entry, true); 5548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (isDeletedBucket(*entry)) 5568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project deletedEntry = entry; 5578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { 5588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (isEmptyBucket(*entry)) 5598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return LookupType(deletedEntry ? deletedEntry : entry, false); 5608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (isDeletedBucket(*entry)) 5628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project deletedEntry = entry; 5638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else if (HashTranslator::equal(Extractor::extract(*entry), key)) 5648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return LookupType(entry, true); 5658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#if DUMP_HASHTABLE_STATS 5678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ++probeCount; 5688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashTableStats::recordCollisionAtCount(probeCount); 5698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 5708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (k == 0) 5718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project k = 1 | doubleHash(h); 5728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project i = (i + k) & sizeMask; 5738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 5778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename HashTranslator> 5788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::fullLookupForWriting(const T& key) 5798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 5808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(m_table); 5818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkKey<T, HashTranslator>(key); 5828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int k = 0; 5848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ValueType* table = m_table; 5858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int sizeMask = m_tableSizeMask; 5868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project unsigned h = HashTranslator::hash(key); 5878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int i = h & sizeMask; 5888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#if DUMP_HASHTABLE_STATS 590635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project atomicIncrement(&HashTableStats::numAccesses); 5918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int probeCount = 0; 5928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 5938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ValueType* deletedEntry = 0; 5958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project while (1) { 5978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ValueType* entry = table + i; 5988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // we count on the compiler to optimize out this branch 6008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (HashFunctions::safeToCompareToEmptyOrDeleted) { 6018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (isEmptyBucket(*entry)) 6028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h); 6038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (HashTranslator::equal(Extractor::extract(*entry), key)) 6058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return makeLookupResult(entry, true, h); 6068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (isDeletedBucket(*entry)) 6088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project deletedEntry = entry; 6098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { 6108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (isEmptyBucket(*entry)) 6118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h); 6128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (isDeletedBucket(*entry)) 6148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project deletedEntry = entry; 6158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else if (HashTranslator::equal(Extractor::extract(*entry), key)) 6168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return makeLookupResult(entry, true, h); 6178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#if DUMP_HASHTABLE_STATS 6198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ++probeCount; 6208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashTableStats::recordCollisionAtCount(probeCount); 6218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 6228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (k == 0) 6238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project k = 1 | doubleHash(h); 6248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project i = (i + k) & sizeMask; 6258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 6298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename Extra, typename HashTranslator> 6308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline pair<typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator, bool> HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::add(const T& key, const Extra& extra) 6318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 6328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkKey<T, HashTranslator>(key); 6338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project invalidateIterators(); 6358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!m_table) 6378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project expand(); 6388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 639d0825bca7fe65beaee391d30da42e937db621564Steve Block internalCheckTableConsistency(); 6408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(m_table); 6428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int k = 0; 6448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ValueType* table = m_table; 6458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int sizeMask = m_tableSizeMask; 6468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project unsigned h = HashTranslator::hash(key); 6478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int i = h & sizeMask; 6488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#if DUMP_HASHTABLE_STATS 650635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project atomicIncrement(&HashTableStats::numAccesses); 6518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int probeCount = 0; 6528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 6538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ValueType* deletedEntry = 0; 6558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ValueType* entry; 6568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project while (1) { 6578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project entry = table + i; 6588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // we count on the compiler to optimize out this branch 6608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (HashFunctions::safeToCompareToEmptyOrDeleted) { 6618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (isEmptyBucket(*entry)) 6628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project break; 6638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (HashTranslator::equal(Extractor::extract(*entry), key)) 6658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return std::make_pair(makeKnownGoodIterator(entry), false); 6668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (isDeletedBucket(*entry)) 6688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project deletedEntry = entry; 6698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { 6708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (isEmptyBucket(*entry)) 6718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project break; 6728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (isDeletedBucket(*entry)) 6748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project deletedEntry = entry; 6758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else if (HashTranslator::equal(Extractor::extract(*entry), key)) 6768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return std::make_pair(makeKnownGoodIterator(entry), false); 6778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#if DUMP_HASHTABLE_STATS 6798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ++probeCount; 6808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashTableStats::recordCollisionAtCount(probeCount); 6818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 6828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (k == 0) 6838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project k = 1 | doubleHash(h); 6848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project i = (i + k) & sizeMask; 6858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (deletedEntry) { 6888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project initializeBucket(*deletedEntry); 6898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project entry = deletedEntry; 6908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project --m_deletedCount; 6918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashTranslator::translate(*entry, key, extra); 6948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ++m_keyCount; 6968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (shouldExpand()) { 6988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // FIXME: This makes an extra copy on expand. Probably not that bad since 6998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // expand is rare, but would be better to have a version of expand that can 7008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // follow a pivot entry and return the new position. 7018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project KeyType enteredKey = Extractor::extract(*entry); 7028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project expand(); 7038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project pair<iterator, bool> p = std::make_pair(find(enteredKey), true); 7048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(p.first != end()); 7058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return p; 7068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 7078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 708d0825bca7fe65beaee391d30da42e937db621564Steve Block internalCheckTableConsistency(); 7098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return std::make_pair(makeKnownGoodIterator(entry), true); 7118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 7128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 7148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename Extra, typename HashTranslator> 7158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline pair<typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator, bool> HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::addPassingHashCode(const T& key, const Extra& extra) 7168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 7178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkKey<T, HashTranslator>(key); 7188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project invalidateIterators(); 7208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!m_table) 7228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project expand(); 7238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 724d0825bca7fe65beaee391d30da42e937db621564Steve Block internalCheckTableConsistency(); 7258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project FullLookupType lookupResult = fullLookupForWriting<T, HashTranslator>(key); 7278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ValueType* entry = lookupResult.first.first; 7298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool found = lookupResult.first.second; 7308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project unsigned h = lookupResult.second; 7318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (found) 7338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return std::make_pair(makeKnownGoodIterator(entry), false); 7348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (isDeletedBucket(*entry)) { 7368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project initializeBucket(*entry); 7378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project --m_deletedCount; 7388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 7398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashTranslator::translate(*entry, key, extra, h); 7418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ++m_keyCount; 7428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (shouldExpand()) { 7438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // FIXME: This makes an extra copy on expand. Probably not that bad since 7448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // expand is rare, but would be better to have a version of expand that can 7458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // follow a pivot entry and return the new position. 7468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project KeyType enteredKey = Extractor::extract(*entry); 7478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project expand(); 7488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project pair<iterator, bool> p = std::make_pair(find(enteredKey), true); 7498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(p.first != end()); 7508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return p; 7518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 7528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 753d0825bca7fe65beaee391d30da42e937db621564Steve Block internalCheckTableConsistency(); 7548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return std::make_pair(makeKnownGoodIterator(entry), true); 7568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 7578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 7598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::reinsert(ValueType& entry) 7608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 7618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(m_table); 7628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(!lookupForWriting(Extractor::extract(entry)).second); 7638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(!isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first))); 7648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#if DUMP_HASHTABLE_STATS 765635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project atomicIncrement(&HashTableStats::numReinserts); 7668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 7678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Mover<ValueType, Traits::needsDestruction>::move(entry, *lookupForWriting(Extractor::extract(entry)).first); 7698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 7708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 7728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template <typename T, typename HashTranslator> 7738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key) 7748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 7758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!m_table) 7768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return end(); 7778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ValueType* entry = lookup<T, HashTranslator>(key); 7798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!entry) 7808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return end(); 7818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return makeKnownGoodIterator(entry); 7838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 7848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 7868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template <typename T, typename HashTranslator> 7878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::const_iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key) const 7888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 7898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!m_table) 7908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return end(); 7918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ValueType* entry = const_cast<HashTable*>(this)->lookup<T, HashTranslator>(key); 7938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!entry) 7948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return end(); 7958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return makeKnownGoodConstIterator(entry); 7978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 7988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 8008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template <typename T, typename HashTranslator> 8018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::contains(const T& key) const 8028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 8038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!m_table) 8048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return false; 8058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 8068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return const_cast<HashTable*>(this)->lookup<T, HashTranslator>(key); 8078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 8088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 8098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 8108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeAndInvalidateWithoutEntryConsistencyCheck(ValueType* pos) 8118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 8128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project invalidateIterators(); 8138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project remove(pos); 8148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 8158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 8168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 8178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeAndInvalidate(ValueType* pos) 8188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 8198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project invalidateIterators(); 820d0825bca7fe65beaee391d30da42e937db621564Steve Block internalCheckTableConsistency(); 8218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project remove(pos); 8228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 8238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 8248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 8258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(ValueType* pos) 8268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 8278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#if DUMP_HASHTABLE_STATS 828635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project atomicIncrement(&HashTableStats::numRemoves); 8298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 8308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 8318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project deleteBucket(*pos); 8328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ++m_deletedCount; 8338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project --m_keyCount; 8348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 8358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (shouldShrink()) 8368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project shrink(); 8378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 838d0825bca7fe65beaee391d30da42e937db621564Steve Block internalCheckTableConsistency(); 8398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 8408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 8418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 8428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(iterator it) 8438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 8448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (it == end()) 8458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return; 8468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 8478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project removeAndInvalidate(const_cast<ValueType*>(it.m_iterator.m_position)); 8488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 8498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 8508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 8518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeWithoutEntryConsistencyCheck(iterator it) 8528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 8538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (it == end()) 8548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return; 8558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 8568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project removeAndInvalidateWithoutEntryConsistencyCheck(const_cast<ValueType*>(it.m_iterator.m_position)); 8578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 8588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 8598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 860ca9cb53ed1119a3fd98fafa0972ffeb56dee1c24Steve Block inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeWithoutEntryConsistencyCheck(const_iterator it) 861ca9cb53ed1119a3fd98fafa0972ffeb56dee1c24Steve Block { 862ca9cb53ed1119a3fd98fafa0972ffeb56dee1c24Steve Block if (it == end()) 863ca9cb53ed1119a3fd98fafa0972ffeb56dee1c24Steve Block return; 864ca9cb53ed1119a3fd98fafa0972ffeb56dee1c24Steve Block 865ca9cb53ed1119a3fd98fafa0972ffeb56dee1c24Steve Block removeAndInvalidateWithoutEntryConsistencyCheck(const_cast<ValueType*>(it.m_position)); 866ca9cb53ed1119a3fd98fafa0972ffeb56dee1c24Steve Block } 867ca9cb53ed1119a3fd98fafa0972ffeb56dee1c24Steve Block 868ca9cb53ed1119a3fd98fafa0972ffeb56dee1c24Steve Block template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 8698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(const KeyType& key) 8708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 8718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project remove(find(key)); 8728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 8738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 8748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 8758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::allocateTable(int size) 8768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 8778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // would use a template member function with explicit specializations here, but 8788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // gcc doesn't appear to support that 8798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (Traits::emptyValueIsZero) 8808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return static_cast<ValueType*>(fastZeroedMalloc(size * sizeof(ValueType))); 8818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ValueType* result = static_cast<ValueType*>(fastMalloc(size * sizeof(ValueType))); 8828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (int i = 0; i < size; i++) 8838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project initializeBucket(result[i]); 8848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return result; 8858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 8868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 8878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 8888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType* table, int size) 8898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 8908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (Traits::needsDestruction) { 8918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (int i = 0; i < size; ++i) { 8928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!isDeletedBucket(table[i])) 8938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project table[i].~ValueType(); 8948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 8958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 8968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project fastFree(table); 8978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 8988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 8998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 9008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::expand() 9018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 9028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int newSize; 9038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (m_tableSize == 0) 9048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project newSize = m_minTableSize; 9058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else if (mustRehashInPlace()) 9068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project newSize = m_tableSize; 9078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else 9088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project newSize = m_tableSize * 2; 9098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 9108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project rehash(newSize); 9118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 9128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 9138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 9148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::rehash(int newTableSize) 9158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 916d0825bca7fe65beaee391d30da42e937db621564Steve Block internalCheckTableConsistencyExceptSize(); 9178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 9188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int oldTableSize = m_tableSize; 9198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ValueType* oldTable = m_table; 9208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 9218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#if DUMP_HASHTABLE_STATS 9228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (oldTableSize != 0) 923635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project atomicIncrement(&HashTableStats::numRehashes); 9248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 9258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 9268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_tableSize = newTableSize; 9278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_tableSizeMask = newTableSize - 1; 9288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_table = allocateTable(newTableSize); 9298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 9308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (int i = 0; i != oldTableSize; ++i) 9318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!isEmptyOrDeletedBucket(oldTable[i])) 9328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project reinsert(oldTable[i]); 9338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 9348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_deletedCount = 0; 9358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 9368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project deallocateTable(oldTable, oldTableSize); 9378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 938d0825bca7fe65beaee391d30da42e937db621564Steve Block internalCheckTableConsistency(); 9398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 9408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 9418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 9428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::clear() 9438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 9448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project invalidateIterators(); 9458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project deallocateTable(m_table, m_tableSize); 9468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_table = 0; 9478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_tableSize = 0; 9488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_tableSizeMask = 0; 9498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_keyCount = 0; 9508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 9518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 9528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 9538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable(const HashTable& other) 9548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project : m_table(0) 9558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project , m_tableSize(0) 9568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project , m_tableSizeMask(0) 9578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project , m_keyCount(0) 9588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project , m_deletedCount(0) 9598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#if CHECK_HASHTABLE_ITERATORS 9608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project , m_iterators(0) 9618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 9628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 9638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Copy the hash table the dumb way, by adding each element to the new table. 9648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // It might be more efficient to copy the table slots, but it's not clear that efficiency is needed. 9658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const_iterator end = other.end(); 9668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (const_iterator it = other.begin(); it != end; ++it) 9678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project add(*it); 9688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 9698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 9708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 9718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::swap(HashTable& other) 9728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 9738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project invalidateIterators(); 9748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project other.invalidateIterators(); 9758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 9768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ValueType* tmp_table = m_table; 9778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_table = other.m_table; 9788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project other.m_table = tmp_table; 9798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 9808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int tmp_tableSize = m_tableSize; 9818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_tableSize = other.m_tableSize; 9828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project other.m_tableSize = tmp_tableSize; 9838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 9848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int tmp_tableSizeMask = m_tableSizeMask; 9858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_tableSizeMask = other.m_tableSizeMask; 9868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project other.m_tableSizeMask = tmp_tableSizeMask; 9878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 9888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int tmp_keyCount = m_keyCount; 9898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_keyCount = other.m_keyCount; 9908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project other.m_keyCount = tmp_keyCount; 9918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 9928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int tmp_deletedCount = m_deletedCount; 9938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_deletedCount = other.m_deletedCount; 9948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project other.m_deletedCount = tmp_deletedCount; 9958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 9968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 9978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 9988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>& HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::operator=(const HashTable& other) 9998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 10008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashTable tmp(other); 10018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project swap(tmp); 10028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return *this; 10038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 10048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1005d0825bca7fe65beaee391d30da42e937db621564Steve Block#if !ASSERT_DISABLED 10068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 10078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 10088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistency() const 10098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 10108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project checkTableConsistencyExceptSize(); 1011d0825bca7fe65beaee391d30da42e937db621564Steve Block ASSERT(!m_table || !shouldExpand()); 10128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(!shouldShrink()); 10138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 10148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 10158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 10168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistencyExceptSize() const 10178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 10188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!m_table) 10198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return; 10208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 10218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int count = 0; 10228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int deletedCount = 0; 10238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (int j = 0; j < m_tableSize; ++j) { 10248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ValueType* entry = m_table + j; 10258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (isEmptyBucket(*entry)) 10268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project continue; 10278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 10288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (isDeletedBucket(*entry)) { 10298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ++deletedCount; 10308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project continue; 10318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 10328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 10338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const_iterator it = find(Extractor::extract(*entry)); 10348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(entry == it.m_position); 10358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ++count; 1036d0825bca7fe65beaee391d30da42e937db621564Steve Block 10378a0914b749bbe7da7768e07a7db5c6d4bb09472bSteve Block ValueCheck<Key>::checkConsistency(it->first); 10388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 10398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 10408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(count == m_keyCount); 10418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(deletedCount == m_deletedCount); 10428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(m_tableSize >= m_minTableSize); 10438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(m_tableSizeMask); 10448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(m_tableSize == m_tableSizeMask + 1); 10458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 10468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1047d0825bca7fe65beaee391d30da42e937db621564Steve Block#endif // ASSERT_DISABLED 10488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 10498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#if CHECK_HASHTABLE_ITERATORS 10508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 10518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 10528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::invalidateIterators() 10538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1054635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project MutexLocker lock(m_mutex); 10558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const_iterator* next; 10568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (const_iterator* p = m_iterators; p; p = next) { 10578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project next = p->m_next; 10588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project p->m_table = 0; 10598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project p->m_next = 0; 10608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project p->m_previous = 0; 10618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 10628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_iterators = 0; 10638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 10648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 10658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 10668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* table, 10678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it) 10688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 10698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project it->m_table = table; 10708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project it->m_previous = 0; 10718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 10728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Insert iterator at head of doubly-linked list of iterators. 10738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!table) { 10748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project it->m_next = 0; 10758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { 1076635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project MutexLocker lock(table->m_mutex); 10778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(table->m_iterators != it); 10788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project it->m_next = table->m_iterators; 10798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project table->m_iterators = it; 10808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (it->m_next) { 10818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(!it->m_next->m_previous); 10828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project it->m_next->m_previous = it; 10838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 10848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 10858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 10868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 10878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 10888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it) 10898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 10908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType; 10918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator; 10928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 10938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Delete iterator from doubly-linked list of iterators. 10948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!it->m_table) { 10958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(!it->m_next); 10968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(!it->m_previous); 10978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { 1098635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project MutexLocker lock(it->m_table->m_mutex); 10998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (it->m_next) { 11008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(it->m_next->m_previous == it); 11018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project it->m_next->m_previous = it->m_previous; 11028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 11038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (it->m_previous) { 11048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(it->m_table->m_iterators != it); 11058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(it->m_previous->m_next == it); 11068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project it->m_previous->m_next = it->m_next; 11078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { 11088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(it->m_table->m_iterators == it); 11098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project it->m_table->m_iterators = it->m_next; 11108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 11118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 11128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 11138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project it->m_table = 0; 11148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project it->m_next = 0; 11158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project it->m_previous = 0; 11168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 11178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 11188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif // CHECK_HASHTABLE_ITERATORS 11198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 11208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // iterator adapters 11218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 11228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename HashTableType, typename ValueType> struct HashTableConstIteratorAdapter { 11238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashTableConstIteratorAdapter(const typename HashTableType::const_iterator& impl) : m_impl(impl) {} 11248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 11258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const ValueType* get() const { return (const ValueType*)m_impl.get(); } 11268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const ValueType& operator*() const { return *get(); } 11278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const ValueType* operator->() const { return get(); } 11288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 11298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashTableConstIteratorAdapter& operator++() { ++m_impl; return *this; } 11308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // postfix ++ intentionally omitted 11318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 11328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typename HashTableType::const_iterator m_impl; 11338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 11348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 11358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename HashTableType, typename ValueType> struct HashTableIteratorAdapter { 11368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashTableIteratorAdapter(const typename HashTableType::iterator& impl) : m_impl(impl) {} 11378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 11388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ValueType* get() const { return (ValueType*)m_impl.get(); } 11398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ValueType& operator*() const { return *get(); } 11408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ValueType* operator->() const { return get(); } 11418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 11428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashTableIteratorAdapter& operator++() { ++m_impl; return *this; } 11438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // postfix ++ intentionally omitted 11448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 11458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project operator HashTableConstIteratorAdapter<HashTableType, ValueType>() { 11468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typename HashTableType::const_iterator i = m_impl; 11478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return i; 11488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 11498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 11508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typename HashTableType::iterator m_impl; 11518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 11528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 11538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename U> 11548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b) 11558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 11568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return a.m_impl == b.m_impl; 11578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 11588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 11598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename U> 11608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b) 11618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 11628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return a.m_impl != b.m_impl; 11638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 11648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 11658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename U> 11668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b) 11678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 11688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return a.m_impl == b.m_impl; 11698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 11708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 11718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename U> 11728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b) 11738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 11748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return a.m_impl != b.m_impl; 11758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 11768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 11778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project} // namespace WTF 11788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 11798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#include "HashIterators.h" 11808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 11818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif // WTF_HashTable_h 1182