Reviewed by mjs
[WebKit-https.git] / JavaScriptCore / kxmlcore / HashTable.h
1 // -*- mode: c++; c-basic-offset: 4 -*-
2 /*
3  * This file is part of the KDE libraries
4  * Copyright (C) 2005, 2006 Apple Computer, Inc.
5  *
6  * This library is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU Library General Public
8  * License as published by the Free Software Foundation; either
9  * version 2 of the License, or (at your option) any later version.
10  *
11  * This library is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14  * Library General Public License for more details.
15  *
16  * You should have received a copy of the GNU Library General Public License
17  * along with this library; see the file COPYING.LIB.  If not, write to
18  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
19  * Boston, MA 02110-1301, USA.
20  *
21  */
22
23 #ifndef KXMLCORE_HASH_TABLE_H
24 #define KXMLCORE_HASH_TABLE_H
25
26 #include "FastMalloc.h"
27 #include "HashTraits.h"
28 #include <assert.h>
29 #include <algorithm>
30
31 namespace KXMLCore {
32
33 #define DUMP_HASHTABLE_STATS 0
34 #define CHECK_HASHTABLE_CONSISTENCY 0
35
36 #ifdef NDEBUG
37 #define CHECK_HASHTABLE_ITERATORS 0
38 #else
39 #define CHECK_HASHTABLE_ITERATORS 1
40 #endif
41
42 #if DUMP_HASHTABLE_STATS
43
44     struct HashTableStats {
45         ~HashTableStats();
46         static int numAccesses;
47         static int numCollisions;
48         static int collisionGraph[4096];
49         static int maxCollisions;
50         static int numRehashes;
51         static int numRemoves;
52         static int numReinserts;
53         static void recordCollisionAtCount(int count);
54     };
55
56 #endif
57
58     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
59     class HashTable;
60     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
61     class HashTableIterator;
62     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
63     class HashTableConstIterator;
64
65 #if CHECK_HASHTABLE_ITERATORS
66     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
67     void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*,
68         HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*);
69
70     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
71     void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*);
72 #else
73     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
74     inline void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*,
75         HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*) { }
76
77     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
78     inline void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*) { }
79 #endif
80
81     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
82     class HashTableConstIterator {
83     private:
84         typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType;
85         typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator;
86         typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
87         typedef Value ValueType;
88         typedef const ValueType& ReferenceType;
89         typedef const ValueType* PointerType;
90
91         friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>;
92         friend class HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>;
93
94         void skipEmptyBuckets()
95         {
96             while (m_position != m_endPosition && HashTableType::isEmptyOrDeletedBucket(*m_position))
97                 ++m_position;
98         }
99
100         HashTableConstIterator(const HashTableType* table, PointerType position, PointerType endPosition)
101             : m_position(position), m_endPosition(endPosition)
102         {
103             addIterator(table, this);
104             skipEmptyBuckets();
105         }
106
107     public:
108         HashTableConstIterator()
109         {
110             addIterator(0, this);
111         }
112
113         // default copy, assignment and destructor are OK if CHECK_HASHTABLE_ITERATORS is 0
114
115 #if CHECK_HASHTABLE_ITERATORS
116         ~HashTableConstIterator()
117         {
118             removeIterator(this);
119         }
120
121         HashTableConstIterator(const const_iterator& other)
122             : m_position(other.m_position), m_endPosition(other.m_endPosition)
123         {
124             addIterator(other.m_table, this);
125         }
126
127         const_iterator& operator=(const const_iterator& other)
128         {
129             m_position = other.m_position;
130             m_endPosition = other.m_endPosition;
131
132             removeIterator(this);
133             addIterator(other.m_table, this);
134
135             return *this;
136         }
137 #endif
138
139         PointerType get() const
140         {
141             checkValidity();
142             return m_position;
143         }
144         ReferenceType operator*() const { return *get(); }
145         PointerType operator->() const { return get(); }
146
147         const_iterator& operator++()
148         {
149             checkValidity();
150             assert(m_position != m_endPosition);
151             ++m_position;
152             skipEmptyBuckets();
153             return *this;
154         }
155
156         // postfix ++ intentionally omitted
157
158         // Comparison.
159         bool operator==(const const_iterator& other) const
160         {
161             checkValidity(other);
162             return m_position == other.m_position;
163         }
164         bool operator!=(const const_iterator& other) const
165         {
166             checkValidity(other);
167             return m_position != other.m_position;
168         }
169
170     private:
171         void checkValidity() const
172         {
173 #if CHECK_HASHTABLE_ITERATORS
174             assert(m_table);
175 #endif
176         }
177
178
179 #if CHECK_HASHTABLE_ITERATORS
180         void checkValidity(const const_iterator& other) const
181         {
182             assert(m_table);
183             assert(other.m_table);
184             assert(m_table == other.m_table);
185         }
186 #else
187         void checkValidity(const const_iterator&) const { }
188 #endif
189
190         PointerType m_position;
191         PointerType m_endPosition;
192
193 #if CHECK_HASHTABLE_ITERATORS
194     public:
195         mutable const HashTableType* m_table;
196         mutable const_iterator* m_next;
197         mutable const_iterator* m_previous;
198 #endif
199     };
200
201     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
202     class HashTableIterator {
203     private:
204         typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType;
205         typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator;
206         typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
207         typedef Value ValueType;
208         typedef ValueType& ReferenceType;
209         typedef ValueType* PointerType;
210
211         friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>;
212
213         HashTableIterator(HashTableType* table, PointerType pos, PointerType end) : m_iterator(table, pos, end) { }
214
215     public:
216         HashTableIterator() { }
217
218         // default copy, assignment and destructor are OK
219
220         PointerType get() const { return const_cast<PointerType>(m_iterator.get()); }
221         ReferenceType operator*() const { return *get(); }
222         PointerType operator->() const { return get(); }
223
224         iterator& operator++() { ++m_iterator; return *this; }
225
226         // postfix ++ intentionally omitted
227
228         // Comparison.
229         bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; }
230         bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; }
231
232         operator const_iterator() const { return m_iterator; }
233
234     private:
235         const_iterator m_iterator;
236     };
237
238     using std::swap;
239
240 #if !COMPILER(MSVC)
241     // Visual C++ has a swap for pairs defined.
242
243     // swap pairs by component, in case of pair members that specialize swap
244     template<typename T, typename U> inline void swap(pair<T, U>& a, pair<T, U>& b)
245     {
246         swap(a.first, b.first);
247         swap(a.second, b.second);
248     }
249 #endif
250
251     template<typename T, bool useSwap> struct Mover;
252     template<typename T> struct Mover<T, true> { static void move(T& from, T& to) { swap(from, to); } };
253     template<typename T> struct Mover<T, false> { static void move(T& from, T& to) { to = from; } };
254
255     template<typename Key, typename Value, typename HashFunctions> class IdentityHashTranslator {
256     public:
257         static unsigned hash(const Key& key) { return HashFunctions::hash(key); }
258         static bool equal(const Key& a, const Key& b) { return HashFunctions::equal(a, b); }
259         static void translate(Value& location, const Key&, const Value& value, unsigned) { location = value; }
260     };
261
262     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
263     class HashTable {
264     public:
265         typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator;
266         typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
267         typedef Traits ValueTraits;
268         typedef Key KeyType;
269         typedef Value ValueType;
270         typedef IdentityHashTranslator<Key, Value, HashFunctions> IdentityTranslatorType;
271
272         HashTable();
273         ~HashTable() { invalidateIterators(); deallocateTable(m_table, m_tableSize); }
274
275         HashTable(const HashTable&);
276         void swap(HashTable&);
277         HashTable& operator=(const HashTable&);
278
279         iterator begin() { return makeIterator(m_table); }
280         iterator end() { return makeIterator(m_table + m_tableSize); }
281         const_iterator begin() const { return makeConstIterator(m_table); }
282         const_iterator end() const { return makeConstIterator(m_table + m_tableSize); }
283
284         int size() const { return m_keyCount; }
285         int capacity() const { return m_tableSize; }
286         bool isEmpty() const { return !m_keyCount; }
287
288         pair<iterator, bool> add(const ValueType& value) { return add<KeyType, ValueType, IdentityTranslatorType>(Extractor::extract(value), value); }
289
290         // A special version of add() that finds the object by hashing and comparing
291         // with some other type, to avoid the cost of type conversion if the object is already
292         // in the table.
293         template<typename T, typename Extra, typename HashTranslator> pair<iterator, bool> add(const T& key, const Extra&);
294
295         iterator find(const KeyType&);
296         const_iterator find(const KeyType&) const;
297         bool contains(const KeyType&) const;
298
299         void remove(const KeyType&);
300         void remove(iterator);
301         void clear();
302
303         static bool isEmptyBucket(const ValueType& value) { return Extractor::extract(value) == KeyTraits::emptyValue(); }
304         static bool isDeletedBucket(const ValueType& value) { return Extractor::extract(value) == KeyTraits::deletedValue(); }
305         static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value) || isDeletedBucket(value); }
306
307     private:
308         static ValueType* allocateTable(int size);
309         static void deallocateTable(ValueType* table, int size);
310
311         typedef pair<ValueType*, bool> LookupType;
312         typedef pair<LookupType, unsigned> FullLookupType;
313
314         LookupType lookup(const Key& key) { return lookup<Key, IdentityTranslatorType>(key).first; }
315         template<typename T, typename HashTranslator> FullLookupType lookup(const T&);
316
317         void remove(ValueType*);
318
319         bool shouldExpand() const { return (m_keyCount + m_deletedCount) * m_maxLoad >= m_tableSize; }
320         bool mustRehashInPlace() const { return m_keyCount * m_minLoad < m_tableSize * 2; }
321         bool shouldShrink() const { return m_keyCount * m_minLoad < m_tableSize && m_tableSize > m_minTableSize; }
322         void expand();
323         void shrink() { rehash(m_tableSize / 2); }
324
325         void rehash(int newTableSize);
326         void reinsert(ValueType&);
327
328         static void initializeBucket(ValueType& bucket) { new (&bucket) ValueType(Traits::emptyValue()); }
329         static void deleteBucket(ValueType& bucket) { assignDeleted<ValueType, Traits>(bucket); }
330
331         FullLookupType makeLookupResult(ValueType* position, bool found, unsigned hash)
332             { return FullLookupType(LookupType(position, found), hash); }
333
334         iterator makeIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize); }
335         const_iterator makeConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize); }
336
337 #if CHECK_HASHTABLE_CONSISTENCY
338         void checkTableConsistency() const;
339         void checkTableConsistencyExceptSize() const;
340 #else
341         static void checkTableConsistency() { }
342         static void checkTableConsistencyExceptSize() { }
343 #endif
344
345 #if CHECK_HASHTABLE_ITERATORS
346         void invalidateIterators();
347 #else
348         static void invalidateIterators() { }
349 #endif
350
351         static const int m_minTableSize = 64;
352         static const int m_maxLoad = 2;
353         static const int m_minLoad = 6;
354
355         ValueType* m_table;
356         int m_tableSize;
357         int m_tableSizeMask;
358         int m_keyCount;
359         int m_deletedCount;
360
361 #if CHECK_HASHTABLE_ITERATORS
362     public:
363         mutable const_iterator* m_iterators;
364 #endif
365     };
366
367     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
368     inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable()
369         : m_table(0)
370         , m_tableSize(0)
371         , m_tableSizeMask(0)
372         , m_keyCount(0)
373         , m_deletedCount(0)
374 #if CHECK_HASHTABLE_ITERATORS
375         , m_iterators(0)
376 #endif
377     {
378     }
379
380     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
381     template<typename T, typename HashTranslator>
382     inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookup(const T& key)
383     {
384         assert(m_table);
385
386         unsigned h = HashTranslator::hash(key);
387         int sizeMask = m_tableSizeMask;
388         int i = h & sizeMask;
389         int k = 0;
390
391 #if DUMP_HASHTABLE_STATS
392         ++HashTableStats::numAccesses;
393         int probeCount = 0;
394 #endif
395
396         ValueType *table = m_table;
397         ValueType *entry;
398         ValueType *deletedEntry = 0;
399         while (!isEmptyBucket(*(entry = table + i))) {
400             if (isDeletedBucket(*entry))
401                 deletedEntry = entry;
402             else if (HashTranslator::equal(Extractor::extract(*entry), key))
403                 return makeLookupResult(entry, true, h);
404 #if DUMP_HASHTABLE_STATS
405             ++probeCount;
406             HashTableStats::recordCollisionAtCount(probeCount);
407 #endif
408             if (k == 0)
409                 k = 1 | (h % sizeMask);
410             i = (i + k) & sizeMask;
411         }
412
413         return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
414     }
415
416
417     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
418     template<typename T, typename Extra, typename HashTranslator>
419     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)
420     {
421         invalidateIterators();
422
423         if (!m_table)
424             expand();
425
426         checkTableConsistency();
427
428         FullLookupType lookupResult = lookup<T, HashTranslator>(key);
429
430         ValueType *entry = lookupResult.first.first;
431         bool found = lookupResult.first.second;
432         unsigned h = lookupResult.second;
433
434         if (found)
435             return std::make_pair(makeIterator(entry), false);
436
437         if (isDeletedBucket(*entry))
438             --m_deletedCount;
439
440         HashTranslator::translate(*entry, key, extra, h);
441         ++m_keyCount;
442
443         if (shouldExpand()) {
444             // FIXME: this makes an extra copy on expand. Probably not that bad since
445             // expand is rare, but would be better to have a version of expand that can
446             // follow a pivot entry and return the new position
447             KeyType enteredKey = Extractor::extract(*entry);
448             expand();
449             return std::make_pair(find(enteredKey), true);
450         }
451
452         checkTableConsistency();
453
454         return std::make_pair(makeIterator(entry), true);
455     }
456
457     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
458     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::reinsert(ValueType& entry)
459     {
460         assert(m_table);
461         assert(!lookup(Extractor::extract(entry)).second);
462         assert(!isDeletedBucket(*(lookup(Extractor::extract(entry)).first)));
463 #if DUMP_HASHTABLE_STATS
464         ++HashTableStats::numReinserts;
465 #endif
466
467         Mover<ValueType, Traits::needsDestruction>::move(entry, *(lookup(Extractor::extract(entry)).first));
468     }
469
470     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
471     typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const Key& key)
472     {
473         if (!m_table)
474             return end();
475
476         LookupType result = lookup(key);
477         if (!result.second)
478             return end();
479         return makeIterator(result.first);
480     }
481
482     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
483     typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::const_iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const Key& key) const
484     {
485         if (!m_table)
486             return end();
487
488         LookupType result = const_cast<HashTable *>(this)->lookup(key);
489         if (!result.second)
490             return end();
491         return makeConstIterator(result.first);
492     }
493
494     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
495     bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::contains(const KeyType& key) const
496     {
497         if (!m_table)
498             return false;
499
500         return const_cast<HashTable *>(this)->lookup(key).second;
501     }
502
503     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
504     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(ValueType* pos)
505     {
506         invalidateIterators();
507         checkTableConsistency();
508
509 #if DUMP_HASHTABLE_STATS
510         ++HashTableStats::numRemoves;
511 #endif
512
513         deleteBucket(*pos);
514         ++m_deletedCount;
515         --m_keyCount;
516
517         if (shouldShrink())
518             shrink();
519
520         checkTableConsistency();
521     }
522
523     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
524     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(iterator it)
525     {
526         if (it == end())
527             return;
528
529         remove(const_cast<ValueType*>(it.m_iterator.m_position));
530     }
531
532     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
533     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(const KeyType& key)
534     {
535         remove(find(key));
536     }
537
538     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
539     Value *HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::allocateTable(int size)
540     {
541         // would use a template member function with explicit specializations here, but
542         // gcc doesn't appear to support that
543         if (Traits::emptyValueIsZero)
544             return static_cast<ValueType *>(fastCalloc(size, sizeof(ValueType)));
545         ValueType* result = static_cast<ValueType*>(fastMalloc(size * sizeof(ValueType)));
546         for (int i = 0; i < size; i++)
547             initializeBucket(result[i]);
548         return result;
549     }
550
551     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
552     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType *table, int size)
553     {
554         if (Traits::needsDestruction)
555             for (int i = 0; i < size; ++i)
556                 table[i].~ValueType();
557         fastFree(table);
558     }
559
560     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
561     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::expand()
562     {
563         int newSize;
564         if (m_tableSize == 0)
565             newSize = m_minTableSize;
566         else if (mustRehashInPlace())
567             newSize = m_tableSize;
568         else
569             newSize = m_tableSize * 2;
570
571         rehash(newSize);
572     }
573
574     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
575     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::rehash(int newTableSize)
576     {
577         checkTableConsistencyExceptSize();
578
579         int oldTableSize = m_tableSize;
580         ValueType *oldTable = m_table;
581
582 #if DUMP_HASHTABLE_STATS
583         if (oldTableSize != 0)
584             ++HashTableStats::numRehashes;
585 #endif
586
587         m_tableSize = newTableSize;
588         m_tableSizeMask = newTableSize - 1;
589         m_table = allocateTable(newTableSize);
590
591         for (int i = 0; i != oldTableSize; ++i)
592             if (!isEmptyOrDeletedBucket(oldTable[i]))
593                 reinsert(oldTable[i]);
594
595         m_deletedCount = 0;
596
597         deallocateTable(oldTable, oldTableSize);
598
599         checkTableConsistency();
600     }
601
602     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
603     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::clear()
604     {
605         invalidateIterators();
606         deallocateTable(m_table, m_tableSize);
607         m_table = 0;
608         m_tableSize = 0;
609         m_tableSizeMask = 0;
610         m_keyCount = 0;
611     }
612
613     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
614     HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable(const HashTable& other)
615         : m_table(0)
616         , m_tableSize(0)
617         , m_tableSizeMask(0)
618         , m_keyCount(0)
619         , m_deletedCount(0)
620 #if CHECK_HASHTABLE_ITERATORS
621         , m_iterators(0)
622 #endif
623     {
624         // Copy the hash table the dumb way, by adding each element to the new table.
625         // It might be more efficient to copy the table slots, but it's not clear that efficiency is needed.
626         const_iterator end = other.end();
627         for (const_iterator it = other.begin(); it != end; ++it)
628             add(*it);
629     }
630
631     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
632     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::swap(HashTable& other)
633     {
634         invalidateIterators();
635         other.invalidateIterators();
636
637         ValueType *tmp_table = m_table;
638         m_table = other.m_table;
639         other.m_table = tmp_table;
640
641         int tmp_tableSize = m_tableSize;
642         m_tableSize = other.m_tableSize;
643         other.m_tableSize = tmp_tableSize;
644
645         int tmp_tableSizeMask = m_tableSizeMask;
646         m_tableSizeMask = other.m_tableSizeMask;
647         other.m_tableSizeMask = tmp_tableSizeMask;
648
649         int tmp_keyCount = m_keyCount;
650         m_keyCount = other.m_keyCount;
651         other.m_keyCount = tmp_keyCount;
652
653         int tmp_deletedCount = m_deletedCount;
654         m_deletedCount = other.m_deletedCount;
655         other.m_deletedCount = tmp_deletedCount;
656     }
657
658     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
659     HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>& HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::operator=(const HashTable& other)
660     {
661         HashTable tmp(other);
662         swap(tmp);
663         return *this;
664     }
665
666 #if CHECK_HASHTABLE_CONSISTENCY
667
668     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
669     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistency() const
670     {
671         checkTableConsistencyExceptSize();
672         assert(!shouldExpand());
673         assert(!shouldShrink());
674     }
675
676     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
677     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistencyExceptSize() const
678     {
679         if (!m_table)
680             return;
681
682         int count = 0;
683         int deletedCount = 0;
684         for (int j = 0; j < m_tableSize; ++j) {
685             ValueType *entry = m_table + j;
686             if (isEmptyBucket(*entry))
687                 continue;
688
689             if (isDeletedBucket(*entry)) {
690                 ++deletedCount;
691                 continue;
692             }
693
694             const_iterator it = find(Extractor::extract(*entry));
695             assert(entry == it.m_position);
696             ++count;
697         }
698
699         assert(count == m_keyCount);
700         assert(deletedCount == m_deletedCount);
701         assert(m_tableSize >= m_minTableSize);
702         assert(m_tableSizeMask);
703         assert(m_tableSize == m_tableSizeMask + 1);
704     }
705
706 #endif // CHECK_HASHTABLE_CONSISTENCY
707
708 #if CHECK_HASHTABLE_ITERATORS
709
710     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
711     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::invalidateIterators()
712     {
713         const_iterator* next;
714         for (const_iterator* p = m_iterators; p; p = next) {
715             next = p->m_next;
716             p->m_table = 0;
717             p->m_next = 0;
718             p->m_previous = 0;
719         }
720         m_iterators = 0;
721     }
722
723     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
724     void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* table,
725         HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it)
726     {
727         it->m_table = table;
728         it->m_previous = 0;
729
730         // Insert iterator at head of doubly-linked list of iterators.
731         if (!table) {
732             it->m_next = 0;
733         } else {
734             assert(table->m_iterators != it);
735             it->m_next = table->m_iterators;
736             table->m_iterators = it;
737             if (it->m_next) {
738                 assert(!it->m_next->m_previous);
739                 it->m_next->m_previous = it;
740             }
741         }
742     }
743
744     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
745     void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it)
746     {
747         typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType;
748         typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
749
750         // Delete iterator from doubly-linked list of iterators.
751         if (!it->m_table) {
752             assert(!it->m_next);
753             assert(!it->m_previous);
754         } else {
755             if (it->m_next) {
756                 assert(it->m_next->m_previous == it);
757                 it->m_next->m_previous = it->m_previous;
758             }
759             if (it->m_previous) {
760                 assert(it->m_table->m_iterators != it);
761                 assert(it->m_previous->m_next == it);
762                 it->m_previous->m_next = it->m_next;
763             } else {
764                 assert(it->m_table->m_iterators == it);
765                 it->m_table->m_iterators = it->m_next;
766             }
767         }
768
769         it->m_table = 0;
770         it->m_next = 0;
771         it->m_previous = 0;
772     }
773
774 #endif // CHECK_HASHTABLE_ITERATORS
775
776     // iterator adapters
777
778     template<typename HashTableType, typename ValueType> struct HashTableConstIteratorAdapter {
779         HashTableConstIteratorAdapter(const typename HashTableType::const_iterator& impl) : m_impl(impl) {}
780
781         const ValueType* get() const { return (const ValueType*)m_impl.get(); }
782         const ValueType& operator*() const { return *get(); }
783         const ValueType* operator->() const { return get(); }
784
785         HashTableConstIteratorAdapter& operator++() { ++m_impl; return *this; }
786         // postfix ++ intentionally omitted
787
788         typename HashTableType::const_iterator m_impl;
789     };
790
791     template<typename HashTableType, typename ValueType> struct HashTableIteratorAdapter {
792         HashTableIteratorAdapter(const typename HashTableType::iterator& impl) : m_impl(impl) {}
793
794         ValueType* get() const { return (ValueType*)m_impl.get(); }
795         ValueType& operator*() const { return *get(); }
796         ValueType* operator->() const { return get(); }
797
798         HashTableIteratorAdapter& operator++() { ++m_impl; return *this; }
799         // postfix ++ intentionally omitted
800
801         operator HashTableConstIteratorAdapter<HashTableType, ValueType>() {
802             typename HashTableType::const_iterator i = m_impl;
803             return i;
804         }
805
806         typename HashTableType::iterator m_impl;
807     };
808
809     template<typename T, typename U>
810     inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
811     {
812         return a.m_impl == b.m_impl;
813     }
814
815     template<typename T, typename U>
816     inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
817     {
818         return a.m_impl != b.m_impl;
819     }
820
821     template<typename T, typename U>
822     inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
823     {
824         return a.m_impl == b.m_impl;
825     }
826
827     template<typename T, typename U>
828     inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
829     {
830         return a.m_impl != b.m_impl;
831     }
832
833     // reference count manager
834     
835     template<typename ValueTraits, typename ValueStorageTraits> struct NeedsRef {
836         static const bool value = ValueTraits::needsRef && !ValueStorageTraits::needsRef;
837     };
838
839     template<bool needsRef, typename ValueTraits> struct RefCounterBase;
840
841     template<typename ValueTraits>
842     struct RefCounterBase<false, ValueTraits> {
843         typedef typename ValueTraits::TraitType ValueType;
844         static void ref(const ValueType&) { }
845         static void deref(const ValueType&) { }
846     };
847
848     template<typename ValueTraits>
849     struct RefCounterBase<true, ValueTraits> {
850         typedef typename ValueTraits::TraitType ValueType;
851         static void ref(const ValueType& v) { ValueTraits::ref(*(const ValueType*)&v); }
852         static void deref(const ValueType& v) { ValueTraits::deref(*(const ValueType*)&v); }
853     };
854
855     template<typename ValueTraits, typename ValueStorageTraits> struct RefCounter {
856         typedef typename ValueTraits::TraitType ValueType;
857         typedef typename ValueStorageTraits::TraitType ValueStorageType;
858         static const bool needsRef = NeedsRef<ValueTraits, ValueStorageTraits>::value;
859         typedef RefCounterBase<needsRef, ValueTraits> Base;
860         static void ref(const ValueStorageType& v) { Base::ref(*(const ValueType*)&v); }
861         static void deref(const ValueStorageType& v) { Base::deref(*(const ValueType*)&v); }
862     };
863
864     template<typename FirstTraits, typename SecondTraits, typename ValueStorageTraits>
865     struct RefCounter<PairBaseHashTraits<FirstTraits, SecondTraits>, ValueStorageTraits> {
866         typedef typename FirstTraits::TraitType FirstType;
867         typedef typename SecondTraits::TraitType SecondType;
868         typedef typename ValueStorageTraits::FirstTraits FirstStorageTraits;
869         typedef typename ValueStorageTraits::SecondTraits SecondStorageTraits;
870         typedef typename ValueStorageTraits::TraitType ValueStorageType;
871         static const bool firstNeedsRef = NeedsRef<FirstTraits, FirstStorageTraits>::value;
872         static const bool secondNeedsRef = NeedsRef<SecondTraits, SecondStorageTraits>::value;
873         typedef RefCounterBase<firstNeedsRef, FirstTraits> FirstBase;
874         typedef RefCounterBase<secondNeedsRef, SecondTraits> SecondBase;
875         static void ref(const ValueStorageType& v) {
876             FirstBase::ref(*(const FirstType*)&v.first);
877             SecondBase::ref(*(const SecondType*)&v.second);
878         }
879         static void deref(const ValueStorageType& v) {
880             FirstBase::deref(*(const FirstType*)&v.first);
881             SecondBase::deref(*(const SecondType*)&v.second);
882         }
883     };
884
885     template<bool needsRef, typename HashTableType, typename ValueTraits> struct HashTableRefCounterBase;
886
887     template<typename HashTableType, typename ValueTraits>
888     struct HashTableRefCounterBase<false, HashTableType, ValueTraits>
889     {
890         static void refAll(HashTableType&) { }
891         static void derefAll(HashTableType&) { }
892     };
893
894     template<typename HashTableType, typename ValueTraits>
895     struct HashTableRefCounterBase<true, HashTableType, ValueTraits>
896     {
897         typedef typename HashTableType::iterator iterator;
898         typedef RefCounter<ValueTraits, typename HashTableType::ValueTraits> ValueRefCounter;
899         static void refAll(HashTableType&);
900         static void derefAll(HashTableType&);
901     };
902
903     template<typename HashTableType, typename ValueTraits>
904     void HashTableRefCounterBase<true, HashTableType, ValueTraits>::refAll(HashTableType& table)
905     {
906         iterator end = table.end();
907         for (iterator it = table.begin(); it != end; ++it)
908             ValueRefCounter::ref(*it);
909     }
910
911     template<typename HashTableType, typename ValueTraits>
912     void HashTableRefCounterBase<true, HashTableType, ValueTraits>::derefAll(HashTableType& table)
913     {
914         iterator end = table.end();
915         for (iterator it = table.begin(); it != end; ++it)
916             ValueRefCounter::deref(*it);
917     }
918
919     template<typename HashTableType, typename ValueTraits> struct HashTableRefCounter {
920         static const bool needsRef = NeedsRef<ValueTraits, typename HashTableType::ValueTraits>::value;
921         typedef HashTableRefCounterBase<needsRef, HashTableType, ValueTraits> Base;
922         static void refAll(HashTableType& table) { Base::refAll(table); }
923         static void derefAll(HashTableType& table) { Base::derefAll(table); }
924     };
925
926 } // namespace KXMLCore
927
928 #endif // KXMLCORE_HASH_TABLE_H