• Skip to content
  • Skip to link menu
KDE 4.1 API Reference
  • KDE API Reference
  • kdelibs
  • Sitemap
  • Contact Us
 

WTF

HashTable.h

Go to the documentation of this file.
00001 // -*- mode: c++; c-basic-offset: 4 -*-
00002 /*
00003  * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
00004  *
00005  * This library is free software; you can redistribute it and/or
00006  * modify it under the terms of the GNU Library General Public
00007  * License as published by the Free Software Foundation; either
00008  * version 2 of the License, or (at your option) any later version.
00009  *
00010  * This library is distributed in the hope that it will be useful,
00011  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00012  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013  * Library General Public License for more details.
00014  *
00015  * You should have received a copy of the GNU Library General Public License
00016  * along with this library; see the file COPYING.LIB.  If not, write to
00017  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
00018  * Boston, MA 02110-1301, USA.
00019  *
00020  */
00021 
00022 #ifndef WTF_HashTable_h
00023 #define WTF_HashTable_h
00024 
00025 #include "FastMalloc.h"
00026 #include "HashTraits.h"
00027 #include <wtf/Assertions.h>
00028 
00029 namespace WTF {
00030 
00031 #define DUMP_HASHTABLE_STATS 0
00032 #define CHECK_HASHTABLE_CONSISTENCY 0
00033 
00034 // The Apple tree triggers this based on debug or not
00035 // We can't do this, since it would make the two builds BIC!
00036 #define CHECK_HASHTABLE_ITERATORS 0
00037 #define CHECK_HASHTABLE_USE_AFTER_DESTRUCTION 0
00038 
00039 #if DUMP_HASHTABLE_STATS
00040 
00041     struct HashTableStats {
00042         ~HashTableStats();
00043         static int numAccesses;
00044         static int numCollisions;
00045         static int collisionGraph[4096];
00046         static int maxCollisions;
00047         static int numRehashes;
00048         static int numRemoves;
00049         static int numReinserts;
00050         static void recordCollisionAtCount(int count);
00051     };
00052 
00053 #endif
00054 
00055     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00056     class HashTable;
00057     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00058     class HashTableIterator;
00059     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00060     class HashTableConstIterator;
00061 
00062     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00063     void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*,
00064         HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*);
00065 
00066     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00067     void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*);
00068 
00069 #if !CHECK_HASHTABLE_ITERATORS
00070 
00071     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00072     inline void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*,
00073         HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*) { }
00074 
00075     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00076     inline void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*) { }
00077 
00078 #endif
00079 
00080     typedef enum { HashItemKnownGood } HashItemKnownGoodTag;
00081 
00082     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00083     class HashTableConstIterator {
00084     private:
00085         typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType;
00086         typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator;
00087         typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
00088         typedef Value ValueType;
00089         typedef const ValueType& ReferenceType;
00090         typedef const ValueType* PointerType;
00091 
00092         friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>;
00093         friend class HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>;
00094 
00095         void skipEmptyBuckets()
00096         {
00097             while (m_position != m_endPosition && HashTableType::isEmptyOrDeletedBucket(*m_position))
00098                 ++m_position;
00099         }
00100 
00101         HashTableConstIterator(const HashTableType* table, PointerType position, PointerType endPosition)
00102             : m_position(position), m_endPosition(endPosition)
00103         {
00104             addIterator(table, this);
00105             skipEmptyBuckets();
00106         }
00107 
00108         HashTableConstIterator(const HashTableType* table, PointerType position, PointerType endPosition, HashItemKnownGoodTag)
00109             : m_position(position), m_endPosition(endPosition)
00110         {
00111             addIterator(table, this);
00112         }
00113 
00114     public:
00115         HashTableConstIterator()
00116         {
00117             addIterator(0, this);
00118         }
00119 
00120         // default copy, assignment and destructor are OK if CHECK_HASHTABLE_ITERATORS is 0
00121 
00122 #if CHECK_HASHTABLE_ITERATORS
00123         ~HashTableConstIterator()
00124         {
00125             removeIterator(this);
00126         }
00127 
00128         HashTableConstIterator(const const_iterator& other)
00129             : m_position(other.m_position), m_endPosition(other.m_endPosition)
00130         {
00131             addIterator(other.m_table, this);
00132         }
00133 
00134         const_iterator& operator=(const const_iterator& other)
00135         {
00136             m_position = other.m_position;
00137             m_endPosition = other.m_endPosition;
00138 
00139             removeIterator(this);
00140             addIterator(other.m_table, this);
00141 
00142             return *this;
00143         }
00144 #endif
00145 
00146         PointerType get() const
00147         {
00148             checkValidity();
00149             return m_position;
00150         }
00151         ReferenceType operator*() const { return *get(); }
00152         PointerType operator->() const { return get(); }
00153 
00154         const_iterator& operator++()
00155         {
00156             checkValidity();
00157             ASSERT(m_position != m_endPosition);
00158             ++m_position;
00159             skipEmptyBuckets();
00160             return *this;
00161         }
00162 
00163         // postfix ++ intentionally omitted
00164 
00165         // Comparison.
00166         bool operator==(const const_iterator& other) const
00167         {
00168             checkValidity(other);
00169             return m_position == other.m_position;
00170         }
00171         bool operator!=(const const_iterator& other) const
00172         {
00173             checkValidity(other);
00174             return m_position != other.m_position;
00175         }
00176 
00177     private:
00178         void checkValidity() const
00179         {
00180 #if CHECK_HASHTABLE_ITERATORS
00181             ASSERT(m_table);
00182 #endif
00183         }
00184 
00185 
00186 #if CHECK_HASHTABLE_ITERATORS
00187         void checkValidity(const const_iterator& other) const
00188         {
00189             ASSERT(m_table);
00190             ASSERT(other.m_table);
00191             ASSERT(m_table == other.m_table);
00192         }
00193 #else
00194         void checkValidity(const const_iterator&) const { }
00195 #endif
00196 
00197         PointerType m_position;
00198         PointerType m_endPosition;
00199 
00200 #if CHECK_HASHTABLE_ITERATORS
00201     public:
00202         mutable const HashTableType* m_table;
00203         mutable const_iterator* m_next;
00204         mutable const_iterator* m_previous;
00205 #endif
00206     };
00207 
00208     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00209     class HashTableIterator {
00210     private:
00211         typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType;
00212         typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator;
00213         typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
00214         typedef Value ValueType;
00215         typedef ValueType& ReferenceType;
00216         typedef ValueType* PointerType;
00217 
00218         friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>;
00219 
00220         HashTableIterator(HashTableType* table, PointerType pos, PointerType end) : m_iterator(table, pos, end) { }
00221         HashTableIterator(HashTableType* table, PointerType pos, PointerType end, HashItemKnownGoodTag tag) : m_iterator(table, pos, end, tag) { }
00222 
00223     public:
00224         HashTableIterator() { }
00225 
00226         // default copy, assignment and destructor are OK
00227 
00228         PointerType get() const { return const_cast<PointerType>(m_iterator.get()); }
00229         ReferenceType operator*() const { return *get(); }
00230         PointerType operator->() const { return get(); }
00231 
00232         iterator& operator++() { ++m_iterator; return *this; }
00233 
00234         // postfix ++ intentionally omitted
00235 
00236         // Comparison.
00237         bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; }
00238         bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; }
00239 
00240         operator const_iterator() const { return m_iterator; }
00241 
00242     private:
00243         const_iterator m_iterator;
00244     };
00245 
00246     using std::swap;
00247 
00248 #if !COMPILER(MSVC)
00249     // Visual C++ has a swap for pairs defined.
00250 
00251     // swap pairs by component, in case of pair members that specialize swap
00252     template<typename T, typename U> inline void swap(pair<T, U>& a, pair<T, U>& b)
00253     {
00254         swap(a.first, b.first);
00255         swap(a.second, b.second);
00256     }
00257 #endif
00258 
00259     template<typename T, bool useSwap> struct Mover;
00260     template<typename T> struct Mover<T, true> { static void move(T& from, T& to) { swap(from, to); } };
00261     template<typename T> struct Mover<T, false> { static void move(T& from, T& to) { to = from; } };
00262 
00263     template<typename Key, typename Value, typename HashFunctions> class IdentityHashTranslator {
00264     public:
00265         static unsigned hash(const Key& key) { return HashFunctions::hash(key); }
00266         static bool equal(const Key& a, const Key& b) { return HashFunctions::equal(a, b); }
00267         static void translate(Value& location, const Key&, const Value& value) { location = value; }
00268     };
00269 
00270     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00271     class HashTable {
00272     public:
00273         typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator;
00274         typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
00275         typedef Traits ValueTraits;
00276         typedef Key KeyType;
00277         typedef Value ValueType;
00278         typedef IdentityHashTranslator<Key, Value, HashFunctions> IdentityTranslatorType;
00279 
00280         HashTable();
00281         ~HashTable() 
00282         {
00283             invalidateIterators(); 
00284             deallocateTable(m_table, m_tableSize); 
00285 #if CHECK_HASHTABLE_USE_AFTER_DESTRUCTION
00286             m_table = (ValueType*)(uintptr_t)0xbbadbeef;
00287 #endif
00288         }
00289 
00290         HashTable(const HashTable&);
00291         void swap(HashTable&);
00292         HashTable& operator=(const HashTable&);
00293 
00294         iterator begin() { return makeIterator(m_table); }
00295         iterator end() { return makeKnownGoodIterator(m_table + m_tableSize); }
00296         const_iterator begin() const { return makeConstIterator(m_table); }
00297         const_iterator end() const { return makeKnownGoodConstIterator(m_table + m_tableSize); }
00298 
00299         int size() const { return m_keyCount; }
00300         int capacity() const { return m_tableSize; }
00301         bool isEmpty() const { return !m_keyCount; }
00302 
00303         pair<iterator, bool> add(const ValueType& value) { return add<KeyType, ValueType, IdentityTranslatorType>(Extractor::extract(value), value); }
00304 
00305         // A special version of add() that finds the object by hashing and comparing
00306         // with some other type, to avoid the cost of type conversion if the object is already
00307         // in the table.
00308         template<typename T, typename Extra, typename HashTranslator> pair<iterator, bool> add(const T& key, const Extra&);
00309         template<typename T, typename Extra, typename HashTranslator> pair<iterator, bool> addPassingHashCode(const T& key, const Extra&);
00310 
00311         iterator find(const KeyType& key) { return find<KeyType, IdentityTranslatorType>(key); }
00312         const_iterator find(const KeyType& key) const { return find<KeyType, IdentityTranslatorType>(key); }
00313         bool contains(const KeyType& key) const { return contains<KeyType, IdentityTranslatorType>(key); }
00314 
00315         template <typename T, typename HashTranslator> iterator find(const T&);
00316         template <typename T, typename HashTranslator> const_iterator find(const T&) const;
00317         template <typename T, typename HashTranslator> bool contains(const T&) const;
00318 
00319         void remove(const KeyType&);
00320         void remove(iterator);
00321         void removeWithoutEntryConsistencyCheck(iterator);
00322         void clear();
00323 
00324         static bool isEmptyBucket(const ValueType& value) { return Extractor::extract(value) == KeyTraits::emptyValue(); }
00325         static bool isDeletedBucket(const ValueType& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); }
00326         static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value) || isDeletedBucket(value); }
00327 
00328         ValueType* lookup(const Key& key) { return lookup<Key, IdentityTranslatorType>(key); }
00329         template<typename T, typename HashTranslator> ValueType* lookup(const T&);
00330 
00331 #if CHECK_HASHTABLE_CONSISTENCY
00332         void checkTableConsistency() const;
00333 #else
00334         static void checkTableConsistency() { }
00335 #endif
00336 
00337     private:
00338         static ValueType* allocateTable(int size);
00339         static void deallocateTable(ValueType* table, int size);
00340 
00341         typedef pair<ValueType*, bool> LookupType;
00342         typedef pair<LookupType, unsigned> FullLookupType;
00343 
00344         LookupType lookupForWriting(const Key& key) { return lookupForWriting<Key, IdentityTranslatorType>(key); };
00345         template<typename T, typename HashTranslator> FullLookupType fullLookupForWriting(const T&);
00346         template<typename T, typename HashTranslator> LookupType lookupForWriting(const T&);
00347 
00348         template<typename T, typename HashTranslator> void checkKey(const T&);
00349 
00350         void removeAndInvalidateWithoutEntryConsistencyCheck(ValueType*);
00351         void removeAndInvalidate(ValueType*);
00352         void remove(ValueType*);
00353 
00354         bool shouldExpand() const { return (m_keyCount + m_deletedCount) * m_maxLoad >= m_tableSize; }
00355         bool mustRehashInPlace() const { return m_keyCount * m_minLoad < m_tableSize * 2; }
00356         bool shouldShrink() const { return m_keyCount * m_minLoad < m_tableSize && m_tableSize > m_minTableSize; }
00357         void expand();
00358         void shrink() { rehash(m_tableSize / 2); }
00359 
00360         void rehash(int newTableSize);
00361         void reinsert(ValueType&);
00362 
00363         static void initializeBucket(ValueType& bucket) { new (&bucket) ValueType(Traits::emptyValue()); }
00364         static void deleteBucket(ValueType& bucket) { bucket.~ValueType(); Traits::constructDeletedValue(&bucket); }
00365 
00366         FullLookupType makeLookupResult(ValueType* position, bool found, unsigned hash)
00367             { return FullLookupType(LookupType(position, found), hash); }
00368 
00369         iterator makeIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize); }
00370         const_iterator makeConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize); }
00371         iterator makeKnownGoodIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); }
00372         const_iterator makeKnownGoodConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); }
00373 
00374 #if CHECK_HASHTABLE_CONSISTENCY
00375         void checkTableConsistencyExceptSize() const;
00376 #else
00377         static void checkTableConsistencyExceptSize() { }
00378 #endif
00379 
00380 #if CHECK_HASHTABLE_ITERATORS
00381         void invalidateIterators();
00382 #else
00383         static void invalidateIterators() { }
00384 #endif
00385 
00386         static const int m_minTableSize = 64;
00387         static const int m_maxLoad = 2;
00388         static const int m_minLoad = 6;
00389 
00390         ValueType* m_table;
00391         int m_tableSize;
00392         int m_tableSizeMask;
00393         int m_keyCount;
00394         int m_deletedCount;
00395 
00396 #if CHECK_HASHTABLE_ITERATORS
00397     public:
00398         mutable const_iterator* m_iterators;
00399 #endif
00400     };
00401 
00402     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00403     inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable()
00404         : m_table(0)
00405         , m_tableSize(0)
00406         , m_tableSizeMask(0)
00407         , m_keyCount(0)
00408         , m_deletedCount(0)
00409 #if CHECK_HASHTABLE_ITERATORS
00410         , m_iterators(0)
00411 #endif
00412     {
00413     }
00414 
00415     static inline unsigned doubleHash(unsigned key)
00416     {
00417         key = ~key + (key >> 23);
00418         key ^= (key << 12);
00419         key ^= (key >> 7);
00420         key ^= (key << 2);
00421         key ^= (key >> 20);
00422         return key;
00423     }
00424 
00425 #if ASSERT_DISABLED
00426 
00427     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00428     template<typename T, typename HashTranslator>
00429     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T&)
00430     {
00431     }
00432 
00433 #else
00434 
00435     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00436     template<typename T, typename HashTranslator>
00437     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T& key)
00438     {
00439         if (!HashFunctions::safeToCompareToEmptyOrDeleted)
00440             return;
00441         ASSERT(!HashTranslator::equal(KeyTraits::emptyValue(), key));
00442         ValueType deletedValue = Traits::emptyValue();
00443         deletedValue.~ValueType();
00444         Traits::constructDeletedValue(&deletedValue);
00445         ASSERT(!HashTranslator::equal(Extractor::extract(deletedValue), key));
00446         new (&deletedValue) ValueType(Traits::emptyValue());
00447     }
00448 
00449 #endif
00450 
00451     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00452     template<typename T, typename HashTranslator>
00453     inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookup(const T& key)
00454     {
00455         checkKey<T, HashTranslator>(key);
00456 
00457         int k = 0;
00458         int sizeMask = m_tableSizeMask;
00459         ValueType* table = m_table;
00460         unsigned h = HashTranslator::hash(key);
00461         int i = h & sizeMask;
00462 
00463         if (!table)
00464             return 0;
00465 
00466 #if DUMP_HASHTABLE_STATS
00467         ++HashTableStats::numAccesses;
00468         int probeCount = 0;
00469 #endif
00470 
00471         while (1) {
00472             ValueType* entry = table + i;
00473                 
00474             // we count on the compiler to optimize out this branch
00475             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
00476                 if (HashTranslator::equal(Extractor::extract(*entry), key))
00477                     return entry;
00478                 
00479                 if (isEmptyBucket(*entry))
00480                     return 0;
00481             } else {
00482                 if (isEmptyBucket(*entry))
00483                     return 0;
00484                 
00485                 if (!isDeletedBucket(*entry) && HashTranslator::equal(Extractor::extract(*entry), key))
00486                     return entry;
00487             }
00488 #if DUMP_HASHTABLE_STATS
00489             ++probeCount;
00490             HashTableStats::recordCollisionAtCount(probeCount);
00491 #endif
00492             if (k == 0)
00493                 k = 1 | doubleHash(h);
00494             i = (i + k) & sizeMask;
00495         }
00496     }
00497 
00498     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00499     template<typename T, typename HashTranslator>
00500     inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::LookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookupForWriting(const T& key)
00501     {
00502         ASSERT(m_table);
00503         checkKey<T, HashTranslator>(key);
00504 
00505         int k = 0;
00506         ValueType* table = m_table;
00507         int sizeMask = m_tableSizeMask;
00508         unsigned h = HashTranslator::hash(key);
00509         int i = h & sizeMask;
00510 
00511 #if DUMP_HASHTABLE_STATS
00512         ++HashTableStats::numAccesses;
00513         int probeCount = 0;
00514 #endif
00515 
00516         ValueType* deletedEntry = 0;
00517 
00518         while (1) {
00519             ValueType* entry = table + i;
00520             
00521             // we count on the compiler to optimize out this branch
00522             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
00523                 if (isEmptyBucket(*entry))
00524                     return LookupType(deletedEntry ? deletedEntry : entry, false);
00525                 
00526                 if (HashTranslator::equal(Extractor::extract(*entry), key))
00527                     return LookupType(entry, true);
00528                 
00529                 if (isDeletedBucket(*entry))
00530                     deletedEntry = entry;
00531             } else {
00532                 if (isEmptyBucket(*entry))
00533                     return LookupType(deletedEntry ? deletedEntry : entry, false);
00534             
00535                 if (isDeletedBucket(*entry))
00536                     deletedEntry = entry;
00537                 else if (HashTranslator::equal(Extractor::extract(*entry), key))
00538                     return LookupType(entry, true);
00539             }
00540 #if DUMP_HASHTABLE_STATS
00541             ++probeCount;
00542             HashTableStats::recordCollisionAtCount(probeCount);
00543 #endif
00544             if (k == 0)
00545                 k = 1 | doubleHash(h);
00546             i = (i + k) & sizeMask;
00547         }
00548     }
00549 
00550     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00551     template<typename T, typename HashTranslator>
00552     inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::fullLookupForWriting(const T& key)
00553     {
00554         ASSERT(m_table);
00555         checkKey<T, HashTranslator>(key);
00556 
00557         int k = 0;
00558         ValueType* table = m_table;
00559         int sizeMask = m_tableSizeMask;
00560         unsigned h = HashTranslator::hash(key);
00561         int i = h & sizeMask;
00562 
00563 #if DUMP_HASHTABLE_STATS
00564         ++HashTableStats::numAccesses;
00565         int probeCount = 0;
00566 #endif
00567 
00568         ValueType* deletedEntry = 0;
00569 
00570         while (1) {
00571             ValueType* entry = table + i;
00572             
00573             // we count on the compiler to optimize out this branch
00574             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
00575                 if (isEmptyBucket(*entry))
00576                     return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
00577                 
00578                 if (HashTranslator::equal(Extractor::extract(*entry), key))
00579                     return makeLookupResult(entry, true, h);
00580                 
00581                 if (isDeletedBucket(*entry))
00582                     deletedEntry = entry;
00583             } else {
00584                 if (isEmptyBucket(*entry))
00585                     return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
00586             
00587                 if (isDeletedBucket(*entry))
00588                     deletedEntry = entry;
00589                 else if (HashTranslator::equal(Extractor::extract(*entry), key))
00590                     return makeLookupResult(entry, true, h);
00591             }
00592 #if DUMP_HASHTABLE_STATS
00593             ++probeCount;
00594             HashTableStats::recordCollisionAtCount(probeCount);
00595 #endif
00596             if (k == 0)
00597                 k = 1 | doubleHash(h);
00598             i = (i + k) & sizeMask;
00599         }
00600     }
00601 
00602     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00603     template<typename T, typename Extra, typename HashTranslator>
00604     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)
00605     {
00606         checkKey<T, HashTranslator>(key);
00607 
00608         invalidateIterators();
00609 
00610         if (!m_table)
00611             expand();
00612 
00613         checkTableConsistency();
00614 
00615         ASSERT(m_table);
00616 
00617         int k = 0;
00618         ValueType* table = m_table;
00619         int sizeMask = m_tableSizeMask;
00620         unsigned h = HashTranslator::hash(key);
00621         int i = h & sizeMask;
00622 
00623 #if DUMP_HASHTABLE_STATS
00624         ++HashTableStats::numAccesses;
00625         int probeCount = 0;
00626 #endif
00627 
00628         ValueType* deletedEntry = 0;
00629         ValueType* entry;
00630         while (1) {
00631             entry = table + i;
00632             
00633             // we count on the compiler to optimize out this branch
00634             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
00635                 if (isEmptyBucket(*entry))
00636                     break;
00637                 
00638                 if (HashTranslator::equal(Extractor::extract(*entry), key))
00639                     return std::make_pair(makeKnownGoodIterator(entry), false);
00640                 
00641                 if (isDeletedBucket(*entry))
00642                     deletedEntry = entry;
00643             } else {
00644                 if (isEmptyBucket(*entry))
00645                     break;
00646             
00647                 if (isDeletedBucket(*entry))
00648                     deletedEntry = entry;
00649                 else if (HashTranslator::equal(Extractor::extract(*entry), key))
00650                     return std::make_pair(makeKnownGoodIterator(entry), false);
00651             }
00652 #if DUMP_HASHTABLE_STATS
00653             ++probeCount;
00654             HashTableStats::recordCollisionAtCount(probeCount);
00655 #endif
00656             if (k == 0)
00657                 k = 1 | doubleHash(h);
00658             i = (i + k) & sizeMask;
00659         }
00660 
00661         if (deletedEntry) {
00662             initializeBucket(*deletedEntry);
00663             entry = deletedEntry;
00664             --m_deletedCount; 
00665         }
00666 
00667         HashTranslator::translate(*entry, key, extra);
00668 
00669         ++m_keyCount;
00670         
00671         if (shouldExpand()) {
00672             // FIXME: This makes an extra copy on expand. Probably not that bad since
00673             // expand is rare, but would be better to have a version of expand that can
00674             // follow a pivot entry and return the new position.
00675             KeyType enteredKey = Extractor::extract(*entry);
00676             expand();
00677             return std::make_pair(find(enteredKey), true);
00678         }
00679         
00680         checkTableConsistency();
00681         
00682         return std::make_pair(makeKnownGoodIterator(entry), true);
00683     }
00684 
00685     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00686     template<typename T, typename Extra, typename HashTranslator>
00687     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)
00688     {
00689         checkKey<T, HashTranslator>(key);
00690 
00691         invalidateIterators();
00692 
00693         if (!m_table)
00694             expand();
00695 
00696         checkTableConsistency();
00697 
00698         FullLookupType lookupResult = fullLookupForWriting<T, HashTranslator>(key);
00699 
00700         ValueType* entry = lookupResult.first.first;
00701         bool found = lookupResult.first.second;
00702         unsigned h = lookupResult.second;
00703         
00704         if (found)
00705             return std::make_pair(makeKnownGoodIterator(entry), false);
00706         
00707         if (isDeletedBucket(*entry)) {
00708             initializeBucket(*entry);
00709             --m_deletedCount;
00710         }
00711         
00712         HashTranslator::translate(*entry, key, extra, h);
00713         ++m_keyCount;
00714         if (shouldExpand()) {
00715             // FIXME: This makes an extra copy on expand. Probably not that bad since
00716             // expand is rare, but would be better to have a version of expand that can
00717             // follow a pivot entry and return the new position.
00718             KeyType enteredKey = Extractor::extract(*entry);
00719             expand();
00720             return std::make_pair(find(enteredKey), true);
00721         }
00722 
00723         checkTableConsistency();
00724 
00725         return std::make_pair(makeKnownGoodIterator(entry), true);
00726     }
00727 
00728     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00729     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::reinsert(ValueType& entry)
00730     {
00731         ASSERT(m_table);
00732         ASSERT(!lookupForWriting(Extractor::extract(entry)).second);
00733         ASSERT(!isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first)));
00734 #if DUMP_HASHTABLE_STATS
00735         ++HashTableStats::numReinserts;
00736 #endif
00737 
00738         Mover<ValueType, Traits::needsDestruction>::move(entry, *lookupForWriting(Extractor::extract(entry)).first);
00739     }
00740 
00741     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00742     template <typename T, typename HashTranslator> 
00743     typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key)
00744     {
00745         if (!m_table)
00746             return end();
00747 
00748         ValueType* entry = lookup<T, HashTranslator>(key);
00749         if (!entry)
00750             return end();
00751 
00752         return makeKnownGoodIterator(entry);
00753     }
00754 
00755     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00756     template <typename T, typename HashTranslator> 
00757     typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::const_iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key) const
00758     {
00759         if (!m_table)
00760             return end();
00761 
00762         ValueType* entry = const_cast<HashTable*>(this)->lookup<T, HashTranslator>(key);
00763         if (!entry)
00764             return end();
00765 
00766         return makeKnownGoodConstIterator(entry);
00767     }
00768 
00769     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00770     template <typename T, typename HashTranslator> 
00771     bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::contains(const T& key) const
00772     {
00773         if (!m_table)
00774             return false;
00775 
00776         return const_cast<HashTable*>(this)->lookup<T, HashTranslator>(key);
00777     }
00778 
00779     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00780     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeAndInvalidateWithoutEntryConsistencyCheck(ValueType* pos)
00781     {
00782         invalidateIterators();
00783         remove(pos);
00784     }
00785 
00786     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00787     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeAndInvalidate(ValueType* pos)
00788     {
00789         invalidateIterators();
00790         checkTableConsistency();
00791         remove(pos);
00792     }
00793 
00794     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00795     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(ValueType* pos)
00796     {
00797 #if DUMP_HASHTABLE_STATS
00798         ++HashTableStats::numRemoves;
00799 #endif
00800 
00801         deleteBucket(*pos);
00802         ++m_deletedCount;
00803         --m_keyCount;
00804 
00805         if (shouldShrink())
00806             shrink();
00807 
00808         checkTableConsistency();
00809     }
00810 
00811     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00812     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(iterator it)
00813     {
00814         if (it == end())
00815             return;
00816 
00817         removeAndInvalidate(const_cast<ValueType*>(it.m_iterator.m_position));
00818     }
00819 
00820     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00821     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeWithoutEntryConsistencyCheck(iterator it)
00822     {
00823         if (it == end())
00824             return;
00825 
00826         removeAndInvalidateWithoutEntryConsistencyCheck(const_cast<ValueType*>(it.m_iterator.m_position));
00827     }
00828 
00829     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00830     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(const KeyType& key)
00831     {
00832         remove(find(key));
00833     }
00834 
00835     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00836     Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::allocateTable(int size)
00837     {
00838         // would use a template member function with explicit specializations here, but
00839         // gcc doesn't appear to support that
00840         if (Traits::emptyValueIsZero)
00841             return static_cast<ValueType*>(fastZeroedMalloc(size * sizeof(ValueType)));
00842         ValueType* result = static_cast<ValueType*>(fastMalloc(size * sizeof(ValueType)));
00843         for (int i = 0; i < size; i++)
00844             initializeBucket(result[i]);
00845         return result;
00846     }
00847 
00848     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00849     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType* table, int size)
00850     {
00851         if (Traits::needsDestruction) {
00852             for (int i = 0; i < size; ++i) {
00853                 if (!isDeletedBucket(table[i]))
00854                     table[i].~ValueType();
00855             }
00856         }
00857         fastFree(table);
00858     }
00859 
00860     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00861     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::expand()
00862     {
00863         int newSize;
00864         if (m_tableSize == 0)
00865             newSize = m_minTableSize;
00866         else if (mustRehashInPlace())
00867             newSize = m_tableSize;
00868         else
00869             newSize = m_tableSize * 2;
00870 
00871         rehash(newSize);
00872     }
00873 
00874     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00875     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::rehash(int newTableSize)
00876     {
00877         checkTableConsistencyExceptSize();
00878 
00879         int oldTableSize = m_tableSize;
00880         ValueType* oldTable = m_table;
00881 
00882 #if DUMP_HASHTABLE_STATS
00883         if (oldTableSize != 0)
00884             ++HashTableStats::numRehashes;
00885 #endif
00886 
00887         m_tableSize = newTableSize;
00888         m_tableSizeMask = newTableSize - 1;
00889         m_table = allocateTable(newTableSize);
00890 
00891         for (int i = 0; i != oldTableSize; ++i)
00892             if (!isEmptyOrDeletedBucket(oldTable[i]))
00893                 reinsert(oldTable[i]);
00894 
00895         m_deletedCount = 0;
00896 
00897         deallocateTable(oldTable, oldTableSize);
00898 
00899         checkTableConsistency();
00900     }
00901 
00902     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00903     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::clear()
00904     {
00905         invalidateIterators();
00906         deallocateTable(m_table, m_tableSize);
00907         m_table = 0;
00908         m_tableSize = 0;
00909         m_tableSizeMask = 0;
00910         m_keyCount = 0;
00911     }
00912 
00913     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00914     HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable(const HashTable& other)
00915         : m_table(0)
00916         , m_tableSize(0)
00917         , m_tableSizeMask(0)
00918         , m_keyCount(0)
00919         , m_deletedCount(0)
00920 #if CHECK_HASHTABLE_ITERATORS
00921         , m_iterators(0)
00922 #endif
00923     {
00924         // Copy the hash table the dumb way, by adding each element to the new table.
00925         // It might be more efficient to copy the table slots, but it's not clear that efficiency is needed.
00926         const_iterator end = other.end();
00927         for (const_iterator it = other.begin(); it != end; ++it)
00928             add(*it);
00929     }
00930 
00931     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00932     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::swap(HashTable& other)
00933     {
00934         invalidateIterators();
00935         other.invalidateIterators();
00936 
00937         ValueType* tmp_table = m_table;
00938         m_table = other.m_table;
00939         other.m_table = tmp_table;
00940 
00941         int tmp_tableSize = m_tableSize;
00942         m_tableSize = other.m_tableSize;
00943         other.m_tableSize = tmp_tableSize;
00944 
00945         int tmp_tableSizeMask = m_tableSizeMask;
00946         m_tableSizeMask = other.m_tableSizeMask;
00947         other.m_tableSizeMask = tmp_tableSizeMask;
00948 
00949         int tmp_keyCount = m_keyCount;
00950         m_keyCount = other.m_keyCount;
00951         other.m_keyCount = tmp_keyCount;
00952 
00953         int tmp_deletedCount = m_deletedCount;
00954         m_deletedCount = other.m_deletedCount;
00955         other.m_deletedCount = tmp_deletedCount;
00956     }
00957 
00958     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00959     HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>& HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::operator=(const HashTable& other)
00960     {
00961         HashTable tmp(other);
00962         swap(tmp);
00963         return *this;
00964     }
00965 
00966 #if CHECK_HASHTABLE_CONSISTENCY
00967 
00968     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00969     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistency() const
00970     {
00971         checkTableConsistencyExceptSize();
00972         ASSERT(!shouldExpand());
00973         ASSERT(!shouldShrink());
00974     }
00975 
00976     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00977     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistencyExceptSize() const
00978     {
00979         if (!m_table)
00980             return;
00981 
00982         int count = 0;
00983         int deletedCount = 0;
00984         for (int j = 0; j < m_tableSize; ++j) {
00985             ValueType* entry = m_table + j;
00986             if (isEmptyBucket(*entry))
00987                 continue;
00988 
00989             if (isDeletedBucket(*entry)) {
00990                 ++deletedCount;
00991                 continue;
00992             }
00993 
00994             const_iterator it = find(Extractor::extract(*entry));
00995             ASSERT(entry == it.m_position);
00996             ++count;
00997         }
00998 
00999         ASSERT(count == m_keyCount);
01000         ASSERT(deletedCount == m_deletedCount);
01001         ASSERT(m_tableSize >= m_minTableSize);
01002         ASSERT(m_tableSizeMask);
01003         ASSERT(m_tableSize == m_tableSizeMask + 1);
01004     }
01005 
01006 #endif // CHECK_HASHTABLE_CONSISTENCY
01007 
01008 #if CHECK_HASHTABLE_ITERATORS
01009 
01010     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
01011     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::invalidateIterators()
01012     {
01013         const_iterator* next;
01014         for (const_iterator* p = m_iterators; p; p = next) {
01015             next = p->m_next;
01016             p->m_table = 0;
01017             p->m_next = 0;
01018             p->m_previous = 0;
01019         }
01020         m_iterators = 0;
01021     }
01022 
01023     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
01024     void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* table,
01025         HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it)
01026     {
01027         it->m_table = table;
01028         it->m_previous = 0;
01029 
01030         // Insert iterator at head of doubly-linked list of iterators.
01031         if (!table) {
01032             it->m_next = 0;
01033         } else {
01034             ASSERT(table->m_iterators != it);
01035             it->m_next = table->m_iterators;
01036             table->m_iterators = it;
01037             if (it->m_next) {
01038                 ASSERT(!it->m_next->m_previous);
01039                 it->m_next->m_previous = it;
01040             }
01041         }
01042     }
01043 
01044     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
01045     void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it)
01046     {
01047         typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType;
01048         typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
01049 
01050         // Delete iterator from doubly-linked list of iterators.
01051         if (!it->m_table) {
01052             ASSERT(!it->m_next);
01053             ASSERT(!it->m_previous);
01054         } else {
01055             if (it->m_next) {
01056                 ASSERT(it->m_next->m_previous == it);
01057                 it->m_next->m_previous = it->m_previous;
01058             }
01059             if (it->m_previous) {
01060                 ASSERT(it->m_table->m_iterators != it);
01061                 ASSERT(it->m_previous->m_next == it);
01062                 it->m_previous->m_next = it->m_next;
01063             } else {
01064                 ASSERT(it->m_table->m_iterators == it);
01065                 it->m_table->m_iterators = it->m_next;
01066             }
01067         }
01068 
01069         it->m_table = 0;
01070         it->m_next = 0;
01071         it->m_previous = 0;
01072     }
01073 
01074 #endif // CHECK_HASHTABLE_ITERATORS
01075 
01076     // iterator adapters
01077 
01078     template<typename HashTableType, typename ValueType> struct HashTableConstIteratorAdapter {
01079         HashTableConstIteratorAdapter(const typename HashTableType::const_iterator& impl) : m_impl(impl) {}
01080 
01081         const ValueType* get() const { return (const ValueType*)m_impl.get(); }
01082         const ValueType& operator*() const { return *get(); }
01083         const ValueType* operator->() const { return get(); }
01084 
01085         HashTableConstIteratorAdapter& operator++() { ++m_impl; return *this; }
01086         // postfix ++ intentionally omitted
01087 
01088         typename HashTableType::const_iterator m_impl;
01089     };
01090 
01091     template<typename HashTableType, typename ValueType> struct HashTableIteratorAdapter {
01092         HashTableIteratorAdapter(const typename HashTableType::iterator& impl) : m_impl(impl) {}
01093 
01094         ValueType* get() const { return (ValueType*)m_impl.get(); }
01095         ValueType& operator*() const { return *get(); }
01096         ValueType* operator->() const { return get(); }
01097 
01098         HashTableIteratorAdapter& operator++() { ++m_impl; return *this; }
01099         // postfix ++ intentionally omitted
01100 
01101         operator HashTableConstIteratorAdapter<HashTableType, ValueType>() {
01102             typename HashTableType::const_iterator i = m_impl;
01103             return i;
01104         }
01105 
01106         typename HashTableType::iterator m_impl;
01107     };
01108 
01109     template<typename T, typename U>
01110     inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
01111     {
01112         return a.m_impl == b.m_impl;
01113     }
01114 
01115     template<typename T, typename U>
01116     inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
01117     {
01118         return a.m_impl != b.m_impl;
01119     }
01120 
01121     template<typename T, typename U>
01122     inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
01123     {
01124         return a.m_impl == b.m_impl;
01125     }
01126 
01127     template<typename T, typename U>
01128     inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
01129     {
01130         return a.m_impl != b.m_impl;
01131     }
01132 
01133 } // namespace WTF
01134 
01135 #include "HashIterators.h"
01136 
01137 #endif // WTF_HashTable_h

WTF

Skip menu "WTF"
  • Main Page
  • Namespace List
  • Class Hierarchy
  • Alphabetical List
  • Class List
  • File List
  • Namespace Members
  • Class Members
  • Related Pages

kdelibs

Skip menu "kdelibs"
  • DNSSD
  • Interfaces
  •   KHexEdit
  •   KMediaPlayer
  •   KSpeech
  •   KTextEditor
  • Kate
  • kconf_update
  • KDE3Support
  •   KUnitTest
  • KDECore
  • KDED
  • KDEsu
  • KDEUI
  • KDocTools
  • KFile
  • KHTML
  • KImgIO
  • KInit
  • KIO
  • KIOSlave
  • KJS
  •   KJS-API
  •   WTF
  • kjsembed
  • KNewStuff
  • KParts
  • Kross
  • KUtils
  • Nepomuk
  • Solid
  • Sonnet
  • ThreadWeaver
Generated for kdelibs by doxygen 1.5.4
This website is maintained by Adriaan de Groot and Allen Winter.
KDE® and the K Desktop Environment® logo are registered trademarks of KDE e.V. | Legal