wtf/HashTraits.h

   1 /*
   2  * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Library General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Library General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Library General Public License
  15  * along with this library; see the file COPYING.LIB.  If not, write to
  16  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  17  * Boston, MA 02110-1301, USA.
  18  *
  19  */
  20
  21 #ifndef WTF_HashTraits_h
  22 #define WTF_HashTraits_h
  23
  24 #include "Assertions.h"
  25 #include "HashFunctions.h"
  26 #include <utility>
  27 #include <limits>
  28
  29 namespace WTF {
  30
  31     using std::pair;
  32     using std::make_pair;
  33
  34     template<typename T> struct IsInteger           { static const bool value = false; };
  35     template<> struct IsInteger<bool>               { static const bool value = true; };
  36     template<> struct IsInteger<char>               { static const bool value = true; };
  37     template<> struct IsInteger<signed char>        { static const bool value = true; };
  38     template<> struct IsInteger<unsigned char>      { static const bool value = true; };
  39     template<> struct IsInteger<short>              { static const bool value = true; };
  40     template<> struct IsInteger<unsigned short>     { static const bool value = true; };
  41     template<> struct IsInteger<int>                { static const bool value = true; };
  42     template<> struct IsInteger<unsigned int>       { static const bool value = true; };
  43     template<> struct IsInteger<long>               { static const bool value = true; };
  44     template<> struct IsInteger<unsigned long>      { static const bool value = true; };
  45     template<> struct IsInteger<long long>          { static const bool value = true; };
  46     template<> struct IsInteger<unsigned long long> { static const bool value = true; };
  47
  48 #if !COMPILER(MSVC) || defined(_NATIVE_WCHAR_T_DEFINED)
  49     template<> struct IsInteger<wchar_t>            { static const bool value = true; };
  50 #endif
  51
  52     COMPILE_ASSERT(IsInteger<bool>::value, WTF_IsInteger_bool_true);
  53     COMPILE_ASSERT(IsInteger<char>::value, WTF_IsInteger_char_true);
  54     COMPILE_ASSERT(IsInteger<signed char>::value, WTF_IsInteger_signed_char_true);
  55     COMPILE_ASSERT(IsInteger<unsigned char>::value, WTF_IsInteger_unsigned_char_true);
  56     COMPILE_ASSERT(IsInteger<short>::value, WTF_IsInteger_short_true);
  57     COMPILE_ASSERT(IsInteger<unsigned short>::value, WTF_IsInteger_unsigned_short_true);
  58     COMPILE_ASSERT(IsInteger<int>::value, WTF_IsInteger_int_true);
  59     COMPILE_ASSERT(IsInteger<unsigned int>::value, WTF_IsInteger_unsigned_int_true);
  60     COMPILE_ASSERT(IsInteger<long>::value, WTF_IsInteger_long_true);
  61     COMPILE_ASSERT(IsInteger<unsigned long>::value, WTF_IsInteger_unsigned_long_true);
  62     COMPILE_ASSERT(IsInteger<long long>::value, WTF_IsInteger_long_long_true);
  63     COMPILE_ASSERT(IsInteger<unsigned long long>::value, WTF_IsInteger_unsigned_long_long_true);
  64
  65 #if !COMPILER(MSVC) || defined(_NATIVE_WCHAR_T_DEFINED)
  66     COMPILE_ASSERT(IsInteger<wchar_t>::value, WTF_IsInteger_wchar_t_true);
  67 #endif
  68
  69     COMPILE_ASSERT(!IsInteger<char*>::value, WTF_IsInteger_char_pointer_false);
  70     COMPILE_ASSERT(!IsInteger<const char* >::value, WTF_IsInteger_const_char_pointer_false);
  71     COMPILE_ASSERT(!IsInteger<volatile char* >::value, WTF_IsInteger_volatile_char_pointer__false);
  72     COMPILE_ASSERT(!IsInteger<double>::value, WTF_IsInteger_double_false);
  73     COMPILE_ASSERT(!IsInteger<float>::value, WTF_IsInteger_float_false);
  74
  75     template<typename T> struct HashTraits;
  76
  77     template<bool isInteger, typename T> struct GenericHashTraitsBase;
  78
  79     template<typename T> struct GenericHashTraitsBase<false, T> {
  80         static const bool emptyValueIsZero = false;
  81         static const bool needsDestruction = true;
  82     };
  83
  84     // Default integer traits disallow both 0 and -1 as keys (max value instead of -1 for unsigned).
  85     template<typename T> struct GenericHashTraitsBase<true, T> {
  86         static const bool emptyValueIsZero = true;
  87         static const bool needsDestruction = false;
  88         static void constructDeletedValue(T& slot) { slot = static_cast<T>(-1); }
  89         static bool isDeletedValue(T value) { return value == static_cast<T>(-1); }
  90     };
  91
  92     template<typename T> struct GenericHashTraits : GenericHashTraitsBase<IsInteger<T>::value, T> {
  93         typedef T TraitType;
  94         static T emptyValue() { return T(); }
  95     };
  96
  97     template<typename T> struct HashTraits : GenericHashTraits<T> { };
  98
  99     template<typename T> struct FloatHashTraits : GenericHashTraits<T> {
 100         static const bool needsDestruction = false;
 101         static T emptyValue() { return std::numeric_limits<T>::infinity(); }
 102         static void constructDeletedValue(T& slot) { slot = -std::numeric_limits<T>::infinity(); }
 103         static bool isDeletedValue(T value) { return value == -std::numeric_limits<T>::infinity(); }
 104     };
 105
 106     template<> struct HashTraits<float> : FloatHashTraits<float> { };
 107     template<> struct HashTraits<double> : FloatHashTraits<double> { };
 108
 109     // Default unsigned traits disallow both 0 and max as keys -- use these traits to allow zero and disallow max - 1.
 110     template<typename T> struct UnsignedWithZeroKeyHashTraits : GenericHashTraits<T> {
 111         static const bool emptyValueIsZero = false;
 112         static const bool needsDestruction = false;
 113         static T emptyValue() { return std::numeric_limits<T>::max(); }
 114         static void constructDeletedValue(T& slot) { slot = std::numeric_limits<T>::max() - 1; }
 115         static bool isDeletedValue(T value) { return value == std::numeric_limits<T>::max() - 1; }
 116     };
 117
 118     template<typename P> struct HashTraits<P*> : GenericHashTraits<P*> {
 119         static const bool emptyValueIsZero = true;
 120         static const bool needsDestruction = false;
 121         static void constructDeletedValue(P*& slot) { slot = reinterpret_cast<P*>(-1); }
 122         static bool isDeletedValue(P* value) { return value == reinterpret_cast<P*>(-1); }
 123     };
 124
 125     template<typename P> struct HashTraits<RefPtr<P> > : GenericHashTraits<RefPtr<P> > {
 126         static const bool emptyValueIsZero = true;
 127         static void constructDeletedValue(RefPtr<P>& slot) { new (&slot) RefPtr<P>(HashTableDeletedValue); }
 128         static bool isDeletedValue(const RefPtr<P>& value) { return value.isHashTableDeletedValue(); }
 129     };
 130
 131     // special traits for pairs, helpful for their use in HashMap implementation
 132
 133     template<typename FirstTraitsArg, typename SecondTraitsArg>
 134     struct PairHashTraits : GenericHashTraits<pair<typename FirstTraitsArg::TraitType, typename SecondTraitsArg::TraitType> > {
 135         typedef FirstTraitsArg FirstTraits;
 136         typedef SecondTraitsArg SecondTraits;
 137         typedef pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> TraitType;
 138
 139         static const bool emptyValueIsZero = FirstTraits::emptyValueIsZero && SecondTraits::emptyValueIsZero;
 140         static TraitType emptyValue() { return make_pair(FirstTraits::emptyValue(), SecondTraits::emptyValue()); }
 141
 142         static const bool needsDestruction = FirstTraits::needsDestruction || SecondTraits::needsDestruction;
 143
 144         static void constructDeletedValue(TraitType& slot) { FirstTraits::constructDeletedValue(slot.first); }
 145         static bool isDeletedValue(const TraitType& value) { return FirstTraits::isDeletedValue(value.first); }
 146     };
 147
 148     template<typename First, typename Second>
 149     struct HashTraits<pair<First, Second> > : public PairHashTraits<HashTraits<First>, HashTraits<Second> > { };
 150
 151 } // namespace WTF
 152
 153 using WTF::HashTraits;
 154 using WTF::PairHashTraits;
 155
 156 #endif // WTF_HashTraits_h