WTF

HashTraits.h

00001 // -*- mode: c++; c-basic-offset: 4 -*-
00002 /*
00003  * This file is part of the KDE libraries
00004  * Copyright (C) 2005, 2006 Apple Computer, Inc.
00005  *
00006  * This library is free software; you can redistribute it and/or
00007  * modify it under the terms of the GNU Library General Public
00008  * License as published by the Free Software Foundation; either
00009  * version 2 of the License, or (at your option) any later version.
00010  *
00011  * This library is distributed in the hope that it will be useful,
00012  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00013  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014  * Library General Public License for more details.
00015  *
00016  * You should have received a copy of the GNU Library General Public License
00017  * along with this library; see the file COPYING.LIB.  If not, write to
00018  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
00019  * Boston, MA 02110-1301, USA.
00020  *
00021  */
00022 
00023 #ifndef WTF_HashTraits_h
00024 #define WTF_HashTraits_h
00025 
00026 #include "HashFunctions.h"
00027 #include <utility>
00028 
00029 namespace WTF {
00030 
00031     using std::pair;
00032     using std::make_pair;
00033 
00034     template<typename T> struct IsInteger           { static const bool value = false; };
00035     template<> struct IsInteger<bool>               { static const bool value = true; };
00036     template<> struct IsInteger<char>               { static const bool value = true; };
00037     template<> struct IsInteger<signed char>        { static const bool value = true; };
00038     template<> struct IsInteger<unsigned char>      { static const bool value = true; };
00039     template<> struct IsInteger<short>              { static const bool value = true; };
00040     template<> struct IsInteger<unsigned short>     { static const bool value = true; };
00041     template<> struct IsInteger<int>                { static const bool value = true; };
00042     template<> struct IsInteger<unsigned int>       { static const bool value = true; };
00043     template<> struct IsInteger<long>               { static const bool value = true; };
00044     template<> struct IsInteger<unsigned long>      { static const bool value = true; };
00045     template<> struct IsInteger<long long>          { static const bool value = true; };
00046     template<> struct IsInteger<unsigned long long> { static const bool value = true; };
00047 
00048     template<typename T> struct HashTraits;
00049 
00050     template<bool isInteger, typename T> struct GenericHashTraitsBase;
00051     template<typename T> struct GenericHashTraitsBase<true, T> {
00052         typedef T TraitType;
00053         typedef HashTraits<typename IntTypes<sizeof(T)>::SignedType> StorageTraits;
00054         static const bool emptyValueIsZero = true;
00055         static const bool needsDestruction = false;
00056     };
00057     template<typename T> struct GenericHashTraitsBase<false, T> {
00058         typedef T TraitType;
00059         typedef HashTraits<T> StorageTraits;
00060         static const bool emptyValueIsZero = false;
00061         static const bool needsDestruction = true;
00062     };
00063 
00064     template<typename T> struct GenericHashTraits : GenericHashTraitsBase<IsInteger<T>::value, T> {
00065         static T emptyValue() { return T(); }
00066         static const bool needsRef = false;
00067     };
00068 
00069     template<typename T> struct HashTraits : GenericHashTraits<T> { };
00070 
00071     // signed integer traits may not be appropriate for all uses since they disallow 0 and -1 as keys
00072     template<> struct HashTraits<signed char> : GenericHashTraits<int> {
00073         static signed char deletedValue() { return -1; }
00074     };
00075     template<> struct HashTraits<short> : GenericHashTraits<int> {
00076         static short deletedValue() { return -1; }
00077     };
00078     template<> struct HashTraits<int> : GenericHashTraits<int> {
00079         static int deletedValue() { return -1; }
00080     };
00081     template<> struct HashTraits<unsigned int> : GenericHashTraits<unsigned int> {
00082         static unsigned int deletedValue() { return static_cast<unsigned int>(-1); }
00083     };
00084     template<> struct HashTraits<long> : GenericHashTraits<long> {
00085         static long deletedValue() { return -1; }
00086     };
00087     template<> struct HashTraits<unsigned long> : GenericHashTraits<unsigned long> {
00088         static unsigned long deletedValue() { return static_cast<unsigned long>(-1); }
00089     };
00090     template<> struct HashTraits<long long> : GenericHashTraits<long long> {
00091         static long long deletedValue() { return -1; }
00092     };
00093     template<> struct HashTraits<unsigned long long> : GenericHashTraits<unsigned long long> {
00094         static unsigned long long deletedValue() { return static_cast<unsigned long long>(-1); }
00095     };
00096     
00097     template<typename P> struct HashTraits<P*> : GenericHashTraits<P*> {
00098         typedef HashTraits<typename IntTypes<sizeof(P*)>::SignedType> StorageTraits;
00099         static const bool emptyValueIsZero = true;
00100         static const bool needsDestruction = false;
00101         static P* deletedValue() { return reinterpret_cast<P*>(-1); }
00102     };
00103 
00104     template<typename P> struct HashTraits<RefPtr<P> > : GenericHashTraits<RefPtr<P> > {
00105         typedef HashTraits<typename IntTypes<sizeof(P*)>::SignedType> StorageTraits;
00106         typedef typename StorageTraits::TraitType StorageType;
00107         static const bool emptyValueIsZero = true;
00108         static const bool needsRef = true;
00109 
00110         typedef union { 
00111             P* m_p; 
00112             StorageType m_s; 
00113         } UnionType;
00114 
00115         static void ref(const StorageType& s) 
00116         { 
00117             if (const P* p = reinterpret_cast<const UnionType*>(&s)->m_p) 
00118                 const_cast<P*>(p)->ref(); 
00119         }
00120         static void deref(const StorageType& s) 
00121         { 
00122             if (const P* p = reinterpret_cast<const UnionType*>(&s)->m_p) 
00123                 const_cast<P*>(p)->deref(); 
00124         }
00125     };
00126 
00127     // template to set deleted values
00128 
00129     template<typename Traits> struct DeletedValueAssigner {
00130         static void assignDeletedValue(typename Traits::TraitType& location) { location = Traits::deletedValue(); }
00131     };
00132 
00133     template<typename T, typename Traits> inline void assignDeleted(T& location)
00134     {
00135         DeletedValueAssigner<Traits>::assignDeletedValue(location);
00136     }
00137 
00138     // special traits for pairs, helpful for their use in HashMap implementation
00139 
00140     template<typename FirstTraits, typename SecondTraits> struct PairHashTraits;
00141 
00142     template<typename FirstTraitsArg, typename SecondTraitsArg>
00143     struct PairBaseHashTraits : GenericHashTraits<pair<typename FirstTraitsArg::TraitType, typename SecondTraitsArg::TraitType> > {
00144         typedef FirstTraitsArg FirstTraits;
00145         typedef SecondTraitsArg SecondTraits;
00146         typedef pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> TraitType;
00147 
00148         typedef PairHashTraits<typename FirstTraits::StorageTraits, typename SecondTraits::StorageTraits> StorageTraits;
00149 
00150         static const bool emptyValueIsZero = FirstTraits::emptyValueIsZero && SecondTraits::emptyValueIsZero;
00151 
00152         static TraitType emptyValue()
00153         {
00154             return make_pair(FirstTraits::emptyValue(), SecondTraits::emptyValue());
00155         }
00156     };
00157 
00158     template<typename FirstTraits, typename SecondTraits>
00159     struct PairHashTraits : PairBaseHashTraits<FirstTraits, SecondTraits> {
00160         typedef pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> TraitType;
00161 
00162         static const bool needsDestruction = FirstTraits::needsDestruction || SecondTraits::needsDestruction;
00163 
00164         static TraitType deletedValue()
00165         {
00166             return TraitType(FirstTraits::deletedValue(), SecondTraits::emptyValue());
00167         }
00168 
00169         static void assignDeletedValue(TraitType& location)
00170         {
00171             assignDeleted<typename FirstTraits::TraitType, FirstTraits>(location.first);
00172             location.second = SecondTraits::emptyValue();
00173         }
00174     };
00175 
00176     template<typename First, typename Second>
00177     struct HashTraits<pair<First, Second> > : public PairHashTraits<HashTraits<First>, HashTraits<Second> > { };
00178 
00179     template<typename FirstTraits, typename SecondTraits>
00180     struct DeletedValueAssigner<PairHashTraits<FirstTraits, SecondTraits> >
00181     {
00182         static void assignDeletedValue(pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType>& location)
00183         {
00184             PairHashTraits<FirstTraits, SecondTraits>::assignDeletedValue(location);
00185         }
00186     };
00187 
00188     template<typename First, typename Second>
00189     struct DeletedValueAssigner<HashTraits<pair<First, Second> > >
00190     {
00191         static void assignDeletedValue(pair<First, Second>& location)
00192         {
00193             HashTraits<pair<First, Second> >::assignDeletedValue(location);
00194         }
00195     };
00196 
00197     // hassh functions and traits that are equivalent (for code sharing)
00198 
00199     template<typename HashArg, typename TraitsArg> struct HashKeyStorageTraits {
00200         typedef HashArg Hash;
00201         typedef TraitsArg Traits;
00202     };
00203     template<typename P> struct HashKeyStorageTraits<PtrHash<P*>, HashTraits<P*> > {
00204         typedef typename IntTypes<sizeof(P*)>::SignedType IntType;
00205         typedef IntHash<IntType> Hash;
00206         typedef HashTraits<IntType> Traits;
00207     };
00208     template<typename P> struct HashKeyStorageTraits<PtrHash<RefPtr<P> >, HashTraits<RefPtr<P> > > {
00209         typedef typename IntTypes<sizeof(P*)>::SignedType IntType;
00210         typedef IntHash<IntType> Hash;
00211         typedef HashTraits<IntType> Traits;
00212     };
00213 
00214 } // namespace WTF
00215 
00216 using WTF::HashTraits;
00217 using WTF::PairHashTraits;
00218 
00219 #endif // WTF_HashTraits_h
WTF

HashTraits.h

WTF

kdelibs
