wtf/HashTraits.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 WTF_HashTraits_h
  24 #define WTF_HashTraits_h
  25
  26 #include "Assertions.h"
  27 #include "HashFunctions.h"
  28 #include <utility>
  29 #include <limits>
  30
  31 namespace WTF {
  32
  33     using std::pair;
  34     using std::make_pair;
  35
  36     template<typename T> struct IsInteger           { static const bool value = false; };
  37     template<> struct IsInteger<bool>               { static const bool value = true; };
  38     template<> struct IsInteger<char>               { static const bool value = true; };
  39     template<> struct IsInteger<signed char>        { static const bool value = true; };
  40     template<> struct IsInteger<unsigned char>      { static const bool value = true; };
  41     template<> struct IsInteger<short>              { static const bool value = true; };
  42     template<> struct IsInteger<unsigned short>     { static const bool value = true; };
  43     template<> struct IsInteger<int>                { static const bool value = true; };
  44     template<> struct IsInteger<unsigned int>       { static const bool value = true; };
  45     template<> struct IsInteger<long>               { static const bool value = true; };
  46     template<> struct IsInteger<unsigned long>      { static const bool value = true; };
  47     template<> struct IsInteger<long long>          { static const bool value = true; };
  48     template<> struct IsInteger<unsigned long long> { static const bool value = true; };
  49
  50     COMPILE_ASSERT(IsInteger<bool>::value, WTF_IsInteger_bool_true);
  51     COMPILE_ASSERT(IsInteger<char>::value, WTF_IsInteger_char_true);
  52     COMPILE_ASSERT(IsInteger<signed char>::value, WTF_IsInteger_signed_char_true);
  53     COMPILE_ASSERT(IsInteger<unsigned char>::value, WTF_IsInteger_unsigned_char_true);
  54     COMPILE_ASSERT(IsInteger<short>::value, WTF_IsInteger_short_true);
  55     COMPILE_ASSERT(IsInteger<unsigned short>::value, WTF_IsInteger_unsigned_short_true);
  56     COMPILE_ASSERT(IsInteger<int>::value, WTF_IsInteger_int_true);
  57     COMPILE_ASSERT(IsInteger<unsigned int>::value, WTF_IsInteger_unsigned_int_true);
  58     COMPILE_ASSERT(IsInteger<long>::value, WTF_IsInteger_long_true);
  59     COMPILE_ASSERT(IsInteger<unsigned long>::value, WTF_IsInteger_unsigned_long_true);
  60     COMPILE_ASSERT(IsInteger<long long>::value, WTF_IsInteger_long_long_true);
  61     COMPILE_ASSERT(IsInteger<unsigned long long>::value, WTF_IsInteger_unsigned_long_long_true);
  62
  63     COMPILE_ASSERT(!IsInteger<char*>::value, WTF_IsInteger_char_pointer_false);
  64     COMPILE_ASSERT(!IsInteger<const char* >::value, WTF_IsInteger_const_char_pointer_false);
  65     COMPILE_ASSERT(!IsInteger<volatile char* >::value, WTF_IsInteger_volatile_char_pointer__false);
  66     COMPILE_ASSERT(!IsInteger<double>::value, WTF_IsInteger_double_false);
  67     COMPILE_ASSERT(!IsInteger<float>::value, WTF_IsInteger_float_false);
  68
  69     template<typename T> struct HashTraits;
  70
  71     template<bool isInteger, typename T> struct GenericHashTraitsBase;
  72     template<typename T> struct GenericHashTraitsBase<true, T> {
  73         typedef T TraitType;
  74         typedef HashTraits<typename IntTypes<sizeof(T)>::SignedType> StorageTraits;
  75         static const bool emptyValueIsZero = true;
  76         static const bool needsDestruction = false;
  77     };
  78     template<typename T> struct GenericHashTraitsBase<false, T> {
  79         typedef T TraitType;
  80         typedef HashTraits<T> StorageTraits;
  81         static const bool emptyValueIsZero = false;
  82         static const bool needsDestruction = true;
  83     };
  84
  85     template<typename T> struct GenericHashTraits : GenericHashTraitsBase<IsInteger<T>::value, T> {
  86         static T emptyValue() { return T(); }
  87         static const bool needsRef = false;
  88     };
  89
  90     template<typename T> struct HashTraits : GenericHashTraits<T> { };
  91
  92     // signed integer traits may not be appropriate for all uses since they disallow 0 and -1 as keys
  93     template<> struct HashTraits<signed char> : GenericHashTraits<int> {
  94         static signed char deletedValue() { return -1; }
  95     };
  96     template<> struct HashTraits<short> : GenericHashTraits<int> {
  97         static short deletedValue() { return -1; }
  98     };
  99     template<> struct HashTraits<int> : GenericHashTraits<int> {
 100         static int deletedValue() { return -1; }
 101     };
 102     template<> struct HashTraits<unsigned int> : GenericHashTraits<unsigned int> {
 103         static unsigned int deletedValue() { return static_cast<unsigned int>(-1); }
 104     };
 105     template<> struct HashTraits<long> : GenericHashTraits<long> {
 106         static long deletedValue() { return -1; }
 107     };
 108     template<> struct HashTraits<unsigned long> : GenericHashTraits<unsigned long> {
 109         static unsigned long deletedValue() { return static_cast<unsigned long>(-1); }
 110     };
 111     template<> struct HashTraits<long long> : GenericHashTraits<long long> {
 112         static long long deletedValue() { return -1; }
 113     };
 114     template<> struct HashTraits<unsigned long long> : GenericHashTraits<unsigned long long> {
 115         static unsigned long long deletedValue() { return static_cast<unsigned long long>(-1); }
 116     };
 117
 118     template<typename T> struct FloatHashTraits {
 119         typedef T TraitType;
 120         typedef HashTraits<T> StorageTraits;
 121         static T emptyValue() { return std::numeric_limits<T>::infinity(); }
 122         static T deletedValue() { return -std::numeric_limits<T>::infinity(); }
 123         static const bool emptyValueIsZero = false;
 124         static const bool needsDestruction = false;
 125         static const bool needsRef = false;
 126     };
 127     template<> struct HashTraits<float> : FloatHashTraits<float> {
 128     };
 129     template<> struct HashTraits<double> : FloatHashTraits<double> {
 130     };
 131
 132     template<typename P> struct HashTraits<P*> : GenericHashTraits<P*> {
 133         typedef HashTraits<typename IntTypes<sizeof(P*)>::SignedType> StorageTraits;
 134         static const bool emptyValueIsZero = true;
 135         static const bool needsDestruction = false;
 136         static P* deletedValue() { return reinterpret_cast<P*>(-1); }
 137     };
 138
 139     template<typename P> struct HashTraits<RefPtr<P> > : GenericHashTraits<RefPtr<P> > {
 140         typedef HashTraits<typename IntTypes<sizeof(P*)>::SignedType> StorageTraits;
 141         typedef typename StorageTraits::TraitType StorageType;
 142         static const bool emptyValueIsZero = true;
 143         static const bool needsRef = true;
 144
 145         typedef union {
 146             P* m_p;
 147             StorageType m_s;
 148         } UnionType;
 149
 150         static void ref(const StorageType& s)
 151         {
 152             if (const P* p = reinterpret_cast<const UnionType*>(&s)->m_p)
 153                 const_cast<P*>(p)->ref();
 154         }
 155         static void deref(const StorageType& s)
 156         {
 157             if (const P* p = reinterpret_cast<const UnionType*>(&s)->m_p)
 158                 const_cast<P*>(p)->deref();
 159         }
 160     };
 161
 162     // template to set deleted values
 163
 164     template<typename Traits> struct DeletedValueAssigner {
 165         static void assignDeletedValue(typename Traits::TraitType& location) { location = Traits::deletedValue(); }
 166     };
 167
 168     template<typename T, typename Traits> inline void assignDeleted(T& location)
 169     {
 170         DeletedValueAssigner<Traits>::assignDeletedValue(location);
 171     }
 172
 173     // special traits for pairs, helpful for their use in HashMap implementation
 174
 175     template<typename FirstTraits, typename SecondTraits> struct PairHashTraits;
 176
 177     template<typename FirstTraitsArg, typename SecondTraitsArg>
 178     struct PairBaseHashTraits : GenericHashTraits<pair<typename FirstTraitsArg::TraitType, typename SecondTraitsArg::TraitType> > {
 179         typedef FirstTraitsArg FirstTraits;
 180         typedef SecondTraitsArg SecondTraits;
 181         typedef pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> TraitType;
 182
 183         typedef PairHashTraits<typename FirstTraits::StorageTraits, typename SecondTraits::StorageTraits> StorageTraits;
 184
 185         static const bool emptyValueIsZero = FirstTraits::emptyValueIsZero && SecondTraits::emptyValueIsZero;
 186
 187         static TraitType emptyValue()
 188         {
 189             return make_pair(FirstTraits::emptyValue(), SecondTraits::emptyValue());
 190         }
 191     };
 192
 193     template<typename FirstTraits, typename SecondTraits>
 194     struct PairHashTraits : PairBaseHashTraits<FirstTraits, SecondTraits> {
 195         typedef pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> TraitType;
 196
 197         static const bool needsDestruction = FirstTraits::needsDestruction || SecondTraits::needsDestruction;
 198
 199         static TraitType deletedValue()
 200         {
 201             return TraitType(FirstTraits::deletedValue(), SecondTraits::emptyValue());
 202         }
 203
 204         static void assignDeletedValue(TraitType& location)
 205         {
 206             assignDeleted<typename FirstTraits::TraitType, FirstTraits>(location.first);
 207             location.second = SecondTraits::emptyValue();
 208         }
 209     };
 210
 211     template<typename First, typename Second>
 212     struct HashTraits<pair<First, Second> > : public PairHashTraits<HashTraits<First>, HashTraits<Second> > { };
 213
 214     template<typename FirstTraits, typename SecondTraits>
 215     struct DeletedValueAssigner<PairHashTraits<FirstTraits, SecondTraits> >
 216     {
 217         static void assignDeletedValue(pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType>& location)
 218         {
 219             PairHashTraits<FirstTraits, SecondTraits>::assignDeletedValue(location);
 220         }
 221     };
 222
 223     template<typename First, typename Second>
 224     struct DeletedValueAssigner<HashTraits<pair<First, Second> > >
 225     {
 226         static void assignDeletedValue(pair<First, Second>& location)
 227         {
 228             HashTraits<pair<First, Second> >::assignDeletedValue(location);
 229         }
 230     };
 231
 232     // hash functions and traits that are equivalent (for code sharing)
 233
 234     template<typename HashArg, typename TraitsArg> struct HashKeyStorageTraits {
 235         typedef HashArg Hash;
 236         typedef TraitsArg Traits;
 237     };
 238     template<typename P> struct HashKeyStorageTraits<PtrHash<P*>, HashTraits<P*> > {
 239         typedef typename IntTypes<sizeof(P*)>::SignedType IntType;
 240         typedef IntHash<IntType> Hash;
 241         typedef HashTraits<IntType> Traits;
 242     };
 243     template<typename P> struct HashKeyStorageTraits<PtrHash<RefPtr<P> >, HashTraits<RefPtr<P> > > {
 244         typedef typename IntTypes<sizeof(P*)>::SignedType IntType;
 245         typedef IntHash<IntType> Hash;
 246         typedef HashTraits<IntType> Traits;
 247     };
 248
 249 } // namespace WTF
 250
 251 using WTF::HashTraits;
 252 using WTF::PairHashTraits;
 253
 254 #endif // WTF_HashTraits_h