| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserv
ed. | 2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserv
ed. |
| 3 * Copyright (C) 2008 David Levin <levin@chromium.org> | 3 * Copyright (C) 2008 David Levin <levin@chromium.org> |
| 4 * | 4 * |
| 5 * This library is free software; you can redistribute it and/or | 5 * This library is free software; you can redistribute it and/or |
| 6 * modify it under the terms of the GNU Library General Public | 6 * modify it under the terms of the GNU Library General Public |
| 7 * License as published by the Free Software Foundation; either | 7 * License as published by the Free Software Foundation; either |
| 8 * version 2 of the License, or (at your option) any later version. | 8 * version 2 of the License, or (at your option) any later version. |
| 9 * | 9 * |
| 10 * This library is distributed in the hope that it will be useful, | 10 * This library is distributed in the hope that it will be useful, |
| (...skipping 95 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 106 | 106 |
| 107 typedef enum { HashItemKnownGood } HashItemKnownGoodTag; | 107 typedef enum { HashItemKnownGood } HashItemKnownGoodTag; |
| 108 | 108 |
| 109 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> | 109 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> |
| 110 class HashTableConstIterator { | 110 class HashTableConstIterator { |
| 111 private: | 111 private: |
| 112 typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTrait
s, Allocator> HashTableType; | 112 typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTrait
s, Allocator> HashTableType; |
| 113 typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits,
KeyTraits, Allocator> iterator; | 113 typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits,
KeyTraits, Allocator> iterator; |
| 114 typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Tra
its, KeyTraits, Allocator> const_iterator; | 114 typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Tra
its, KeyTraits, Allocator> const_iterator; |
| 115 typedef Value ValueType; | 115 typedef Value ValueType; |
| 116 typedef const ValueType& ReferenceType; | 116 typedef typename Traits::IteratorConstGetType GetType; |
| 117 typedef const ValueType* PointerType; | 117 typedef const ValueType* PointerType; |
| 118 typedef typename Allocator::template IteratorWitness<HashTableType>::Typ
e IteratorWitnessType; | 118 typedef typename Allocator::template IteratorWitness<HashTableType>::Typ
e IteratorWitnessType; |
| 119 | 119 |
| 120 friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, Key
Traits, Allocator>; | 120 friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, Key
Traits, Allocator>; |
| 121 friend class HashTableIterator<Key, Value, Extractor, HashFunctions, Tra
its, KeyTraits, Allocator>; | 121 friend class HashTableIterator<Key, Value, Extractor, HashFunctions, Tra
its, KeyTraits, Allocator>; |
| 122 | 122 |
| 123 void skipEmptyBuckets() | 123 void skipEmptyBuckets() |
| 124 { | 124 { |
| 125 while (m_position != m_endPosition && HashTableType::isEmptyOrDelete
dBucket(*m_position)) | 125 while (m_position != m_endPosition && HashTableType::isEmptyOrDelete
dBucket(*m_position)) |
| 126 --m_position; | 126 --m_position; |
| (...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 185 | 185 |
| 186 #if CHECK_HASHTABLE_ITERATORS | 186 #if CHECK_HASHTABLE_ITERATORS |
| 187 m_witness = other.m_witness; | 187 m_witness = other.m_witness; |
| 188 #endif | 188 #endif |
| 189 addIterator(other.m_table, this); | 189 addIterator(other.m_table, this); |
| 190 | 190 |
| 191 return *this; | 191 return *this; |
| 192 } | 192 } |
| 193 #endif | 193 #endif |
| 194 | 194 |
| 195 PointerType get() const | 195 GetType get() const |
| 196 { | 196 { |
| 197 checkValidity(); | 197 checkValidity(); |
| 198 return m_position; | 198 return m_position; |
| 199 } | 199 } |
| 200 ReferenceType operator*() const { return *get(); } | 200 typename Traits::IteratorConstReferenceType operator*() const { return T
raits::getToReferenceConstConversion(get()); } |
| 201 PointerType operator->() const { return get(); } | 201 GetType operator->() const { return get(); } |
| 202 | 202 |
| 203 const_iterator& operator++() | 203 const_iterator& operator++() |
| 204 { | 204 { |
| 205 checkValidity(); | 205 checkValidity(); |
| 206 ASSERT(m_position != m_endPosition); | 206 ASSERT(m_position != m_endPosition); |
| 207 --m_position; | 207 --m_position; |
| 208 skipEmptyBuckets(); | 208 skipEmptyBuckets(); |
| 209 return *this; | 209 return *this; |
| 210 } | 210 } |
| 211 | 211 |
| (...skipping 55 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 267 #endif | 267 #endif |
| 268 }; | 268 }; |
| 269 | 269 |
| 270 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> | 270 template<typename Key, typename Value, typename Extractor, typename HashFunc
tions, typename Traits, typename KeyTraits, typename Allocator> |
| 271 class HashTableIterator { | 271 class HashTableIterator { |
| 272 private: | 272 private: |
| 273 typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTrait
s, Allocator> HashTableType; | 273 typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTrait
s, Allocator> HashTableType; |
| 274 typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits,
KeyTraits, Allocator> iterator; | 274 typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits,
KeyTraits, Allocator> iterator; |
| 275 typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Tra
its, KeyTraits, Allocator> const_iterator; | 275 typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Tra
its, KeyTraits, Allocator> const_iterator; |
| 276 typedef Value ValueType; | 276 typedef Value ValueType; |
| 277 typedef ValueType& ReferenceType; | 277 typedef typename Traits::IteratorGetType GetType; |
| 278 typedef ValueType* PointerType; | 278 typedef ValueType* PointerType; |
| 279 typedef typename Allocator::template IteratorWitness<HashTableType>::Typ
e IteratorWitnessType; | 279 typedef typename Allocator::template IteratorWitness<HashTableType>::Typ
e IteratorWitnessType; |
| 280 | 280 |
| 281 friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, Key
Traits, Allocator>; | 281 friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, Key
Traits, Allocator>; |
| 282 | 282 |
| 283 HashTableIterator(HashTableType* table, PointerType pos, PointerType end
, IteratorWitnessType witness) : m_iterator(table, pos, end, witness) { } | 283 HashTableIterator(HashTableType* table, PointerType pos, PointerType end
, IteratorWitnessType witness) : m_iterator(table, pos, end, witness) { } |
| 284 HashTableIterator(HashTableType* table, PointerType pos, PointerType end
, HashItemKnownGoodTag tag, IteratorWitnessType witness) : m_iterator(table, pos
, end, tag, witness) { } | 284 HashTableIterator(HashTableType* table, PointerType pos, PointerType end
, HashItemKnownGoodTag tag, IteratorWitnessType witness) : m_iterator(table, pos
, end, tag, witness) { } |
| 285 | 285 |
| 286 public: | 286 public: |
| 287 HashTableIterator() { } | 287 HashTableIterator() { } |
| 288 | 288 |
| 289 // default copy, assignment and destructor are OK | 289 // default copy, assignment and destructor are OK |
| 290 | 290 |
| 291 PointerType get() const { return const_cast<PointerType>(m_iterator.get(
)); } | 291 GetType get() const { return const_cast<PointerType>(m_iterator.get());
} |
| 292 ReferenceType operator*() const { return *get(); } | 292 typename Traits::IteratorReferenceType operator*() const { return Traits
::getToReferenceConversion(get()); } |
| 293 PointerType operator->() const { return get(); } | 293 GetType operator->() const { return get(); } |
| 294 | 294 |
| 295 iterator& operator++() { ++m_iterator; return *this; } | 295 iterator& operator++() { ++m_iterator; return *this; } |
| 296 | 296 |
| 297 // postfix ++ intentionally omitted | 297 // postfix ++ intentionally omitted |
| 298 | 298 |
| 299 // Comparison. | 299 // Comparison. |
| 300 bool operator==(const iterator& other) const { return m_iterator == othe
r.m_iterator; } | 300 bool operator==(const iterator& other) const { return m_iterator == othe
r.m_iterator; } |
| 301 bool operator!=(const iterator& other) const { return m_iterator != othe
r.m_iterator; } | 301 bool operator!=(const iterator& other) const { return m_iterator != othe
r.m_iterator; } |
| 302 bool operator==(const const_iterator& other) const { return m_iterator =
= other; } | 302 bool operator==(const const_iterator& other) const { return m_iterator =
= other; } |
| 303 bool operator!=(const const_iterator& other) const { return m_iterator !
= other; } | 303 bool operator!=(const const_iterator& other) const { return m_iterator !
= other; } |
| (...skipping 1119 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1423 | 1423 |
| 1424 it->m_table = 0; | 1424 it->m_table = 0; |
| 1425 it->m_next = 0; | 1425 it->m_next = 0; |
| 1426 it->m_previous = 0; | 1426 it->m_previous = 0; |
| 1427 } | 1427 } |
| 1428 | 1428 |
| 1429 #endif // CHECK_HASHTABLE_ITERATORS | 1429 #endif // CHECK_HASHTABLE_ITERATORS |
| 1430 | 1430 |
| 1431 // iterator adapters | 1431 // iterator adapters |
| 1432 | 1432 |
| 1433 template<typename HashTableType, typename ValueType> struct HashTableConstIt
eratorAdapter { | 1433 template<typename HashTableType, typename Traits> struct HashTableConstItera
torAdapter { |
| 1434 HashTableConstIteratorAdapter() {} | 1434 HashTableConstIteratorAdapter() {} |
| 1435 HashTableConstIteratorAdapter(const typename HashTableType::const_iterat
or& impl) : m_impl(impl) {} | 1435 HashTableConstIteratorAdapter(const typename HashTableType::const_iterat
or& impl) : m_impl(impl) {} |
| 1436 typedef typename Traits::IteratorConstGetType GetType; |
| 1437 typedef typename HashTableType::ValueTraits::IteratorConstGetType Source
GetType; |
| 1436 | 1438 |
| 1437 const ValueType* get() const { return (const ValueType*)m_impl.get(); } | 1439 GetType get() const { return (GetType)SourceGetType(m_impl.get()); } |
| 1438 const ValueType& operator*() const { return *get(); } | 1440 typename Traits::IteratorConstReferenceType operator*() const { return T
raits::getToReferenceConstConversion(get()); } |
| 1439 const ValueType* operator->() const { return get(); } | 1441 GetType operator->() const { return get(); } |
| 1440 | 1442 |
| 1441 HashTableConstIteratorAdapter& operator++() { ++m_impl; return *this; } | 1443 HashTableConstIteratorAdapter& operator++() { ++m_impl; return *this; } |
| 1442 // postfix ++ intentionally omitted | 1444 // postfix ++ intentionally omitted |
| 1443 | 1445 |
| 1444 typename HashTableType::const_iterator m_impl; | 1446 typename HashTableType::const_iterator m_impl; |
| 1445 }; | 1447 }; |
| 1446 | 1448 |
| 1447 template<typename HashTableType, typename ValueType> struct HashTableIterato
rAdapter { | 1449 template<typename HashTableType, typename Traits> struct HashTableIteratorAd
apter { |
| 1450 typedef typename Traits::IteratorGetType GetType; |
| 1451 typedef typename HashTableType::ValueTraits::IteratorGetType SourceGetTy
pe; |
| 1452 |
| 1448 HashTableIteratorAdapter() {} | 1453 HashTableIteratorAdapter() {} |
| 1449 HashTableIteratorAdapter(const typename HashTableType::iterator& impl) :
m_impl(impl) {} | 1454 HashTableIteratorAdapter(const typename HashTableType::iterator& impl) :
m_impl(impl) {} |
| 1450 | 1455 |
| 1451 ValueType* get() const { return (ValueType*)m_impl.get(); } | 1456 GetType get() const { return (GetType)SourceGetType(m_impl.get()); } |
| 1452 ValueType& operator*() const { return *get(); } | 1457 typename Traits::IteratorReferenceType operator*() const { return Traits
::getToReferenceConversion(get()); } |
| 1453 ValueType* operator->() const { return get(); } | 1458 GetType operator->() const { return get(); } |
| 1454 | 1459 |
| 1455 HashTableIteratorAdapter& operator++() { ++m_impl; return *this; } | 1460 HashTableIteratorAdapter& operator++() { ++m_impl; return *this; } |
| 1456 // postfix ++ intentionally omitted | 1461 // postfix ++ intentionally omitted |
| 1457 | 1462 |
| 1458 operator HashTableConstIteratorAdapter<HashTableType, ValueType>() { | 1463 operator HashTableConstIteratorAdapter<HashTableType, Traits>() |
| 1464 { |
| 1459 typename HashTableType::const_iterator i = m_impl; | 1465 typename HashTableType::const_iterator i = m_impl; |
| 1460 return i; | 1466 return i; |
| 1461 } | 1467 } |
| 1462 | 1468 |
| 1463 typename HashTableType::iterator m_impl; | 1469 typename HashTableType::iterator m_impl; |
| 1464 }; | 1470 }; |
| 1465 | 1471 |
| 1466 template<typename T, typename U> | 1472 template<typename T, typename U> |
| 1467 inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const H
ashTableConstIteratorAdapter<T, U>& b) | 1473 inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const H
ashTableConstIteratorAdapter<T, U>& b) |
| 1468 { | 1474 { |
| (...skipping 41 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1510 inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTa
bleConstIteratorAdapter<T, U>& b) | 1516 inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTa
bleConstIteratorAdapter<T, U>& b) |
| 1511 { | 1517 { |
| 1512 return a.m_impl != b.m_impl; | 1518 return a.m_impl != b.m_impl; |
| 1513 } | 1519 } |
| 1514 | 1520 |
| 1515 } // namespace WTF | 1521 } // namespace WTF |
| 1516 | 1522 |
| 1517 #include <wtf/HashIterators.h> | 1523 #include <wtf/HashIterators.h> |
| 1518 | 1524 |
| 1519 #endif // WTF_HashTable_h | 1525 #endif // WTF_HashTable_h |
| OLD | NEW |