Source/WTF/wtf/HashTraits.h

   1 /*
   2  * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 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 <wtf/HashFunctions.h>
  25 #include <wtf/StdLibExtras.h>
  26 #include <wtf/TypeTraits.h>
  27 #include <utility>
  28 #include <limits>
  29
  30 namespace WTF {
  31
  32     class String;
  33
  34     template<typename T> class OwnPtr;
  35     template<typename T> class PassOwnPtr;
  36
  37     template<typename T> struct HashTraits;
  38
  39     template<bool isInteger, typename T> struct GenericHashTraitsBase;
  40
  41     template<typename T> struct GenericHashTraitsBase<false, T> {
  42         // The emptyValueIsZero flag is used to optimize allocation of empty hash tables with zeroed memory.
  43         static const bool emptyValueIsZero = false;
  44
  45         // The hasIsEmptyValueFunction flag allows the hash table to automatically generate code to check
  46         // for the empty value when it can be done with the equality operator, but allows custom functions
  47         // for cases like String that need them.
  48         static const bool hasIsEmptyValueFunction = false;
  49
  50         // The needsDestruction flag is used to optimize destruction and rehashing.
  51         static const bool needsDestruction = true;
  52
  53         static const int minimumTableSize = 64;
  54     };
  55
  56     // Default integer traits disallow both 0 and -1 as keys (max value instead of -1 for unsigned).
  57     template<typename T> struct GenericHashTraitsBase<true, T> : GenericHashTraitsBase<false, T> {
  58         static const bool emptyValueIsZero = true;
  59         static const bool needsDestruction = false;
  60         static void constructDeletedValue(T& slot) { slot = static_cast<T>(-1); }
  61         static bool isDeletedValue(T value) { return value == static_cast<T>(-1); }
  62     };
  63
  64     template<typename T> struct GenericHashTraits : GenericHashTraitsBase<IsInteger<T>::value, T> {
  65         typedef T TraitType;
  66         typedef T EmptyValueType;
  67
  68         static T emptyValue() { return T(); }
  69
  70         // Type for functions that take ownership, such as add.
  71         // The store function either not be called or called once to store something passed in.
  72         // The value passed to the store function will be either PassInType or PassInType&.
  73         typedef const T& PassInType;
  74         static void store(const T& value, T& storage) { storage = value; }
  75
  76         // Type for return value of functions that transfer ownership, such as take.
  77         typedef T PassOutType;
  78         static PassOutType passOut(const T& value) { return value; }
  79
  80         // Type for return value of functions that do not transfer ownership, such as get.
  81         // FIXME: We could change this type to const T& for better performance if we figured out
  82         // a way to handle the return value from emptyValue, which is a temporary.
  83         typedef T PeekType;
  84         static PeekType peek(const T& value) { return value; }
  85     };
  86
  87     template<typename T> struct HashTraits : GenericHashTraits<T> { };
  88
  89     template<typename T> struct FloatHashTraits : GenericHashTraits<T> {
  90         static const bool needsDestruction = false;
  91         static T emptyValue() { return std::numeric_limits<T>::infinity(); }
  92         static void constructDeletedValue(T& slot) { slot = -std::numeric_limits<T>::infinity(); }
  93         static bool isDeletedValue(T value) { return value == -std::numeric_limits<T>::infinity(); }
  94     };
  95
  96     template<> struct HashTraits<float> : FloatHashTraits<float> { };
  97     template<> struct HashTraits<double> : FloatHashTraits<double> { };
  98
  99     // Default unsigned traits disallow both 0 and max as keys -- use these traits to allow zero and disallow max - 1.
 100     template<typename T> struct UnsignedWithZeroKeyHashTraits : GenericHashTraits<T> {
 101         static const bool emptyValueIsZero = false;
 102         static const bool needsDestruction = false;
 103         static T emptyValue() { return std::numeric_limits<T>::max(); }
 104         static void constructDeletedValue(T& slot) { slot = std::numeric_limits<T>::max() - 1; }
 105         static bool isDeletedValue(T value) { return value == std::numeric_limits<T>::max() - 1; }
 106     };
 107
 108     template<typename P> struct HashTraits<P*> : GenericHashTraits<P*> {
 109         static const bool emptyValueIsZero = true;
 110         static const bool needsDestruction = false;
 111         static void constructDeletedValue(P*& slot) { slot = reinterpret_cast<P*>(-1); }
 112         static bool isDeletedValue(P* value) { return value == reinterpret_cast<P*>(-1); }
 113     };
 114
 115     template<typename T> struct SimpleClassHashTraits : GenericHashTraits<T> {
 116         static const bool emptyValueIsZero = true;
 117         static void constructDeletedValue(T& slot) { new (NotNull, &slot) T(HashTableDeletedValue); }
 118         static bool isDeletedValue(const T& value) { return value.isHashTableDeletedValue(); }
 119     };
 120
 121     template<typename P> struct HashTraits<OwnPtr<P> > : SimpleClassHashTraits<OwnPtr<P> > {
 122         typedef std::nullptr_t EmptyValueType;
 123
 124         static EmptyValueType emptyValue() { return nullptr; }
 125
 126         typedef PassOwnPtr<P> PassInType;
 127         static void store(PassOwnPtr<P> value, OwnPtr<P>& storage) { storage = value; }
 128
 129         typedef PassOwnPtr<P> PassOutType;
 130         static PassOwnPtr<P> passOut(OwnPtr<P>& value) { return value.release(); }
 131         static PassOwnPtr<P> passOut(std::nullptr_t) { return nullptr; }
 132
 133         typedef typename OwnPtr<P>::PtrType PeekType;
 134         static PeekType peek(const OwnPtr<P>& value) { return value.get(); }
 135         static PeekType peek(std::nullptr_t) { return 0; }
 136     };
 137
 138     template<typename P> struct HashTraits<RefPtr<P> > : SimpleClassHashTraits<RefPtr<P> > {
 139         typedef PassRefPtr<P> PassInType;
 140         static void store(PassRefPtr<P> value, RefPtr<P>& storage) { storage = value; }
 141
 142         // FIXME: We should change PassOutType to PassRefPtr for better performance.
 143         // FIXME: We should consider changing PeekType to a raw pointer for better performance,
 144         // but then callers won't need to call get; doing so will require updating many call sites.
 145     };
 146
 147     template<> struct HashTraits<String> : SimpleClassHashTraits<String> {
 148         static const bool hasIsEmptyValueFunction = true;
 149         static bool isEmptyValue(const String&);
 150     };
 151
 152     // This struct template is an implementation detail of the isHashTraitsEmptyValue function,
 153     // which selects either the emptyValue function or the isEmptyValue function to check for empty values.
 154     template<typename Traits, bool hasEmptyValueFunction> struct HashTraitsEmptyValueChecker;
 155     template<typename Traits> struct HashTraitsEmptyValueChecker<Traits, true> {
 156         template<typename T> static bool isEmptyValue(const T& value) { return Traits::isEmptyValue(value); }
 157     };
 158     template<typename Traits> struct HashTraitsEmptyValueChecker<Traits, false> {
 159         template<typename T> static bool isEmptyValue(const T& value) { return value == Traits::emptyValue(); }
 160     };
 161     template<typename Traits, typename T> inline bool isHashTraitsEmptyValue(const T& value)
 162     {
 163         return HashTraitsEmptyValueChecker<Traits, Traits::hasIsEmptyValueFunction>::isEmptyValue(value);
 164     }
 165
 166     template<typename FirstTraitsArg, typename SecondTraitsArg>
 167     struct PairHashTraits : GenericHashTraits<std::pair<typename FirstTraitsArg::TraitType, typename SecondTraitsArg::TraitType> > {
 168         typedef FirstTraitsArg FirstTraits;
 169         typedef SecondTraitsArg SecondTraits;
 170         typedef std::pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> TraitType;
 171         typedef std::pair<typename FirstTraits::EmptyValueType, typename SecondTraits::EmptyValueType> EmptyValueType;
 172
 173         static const bool emptyValueIsZero = FirstTraits::emptyValueIsZero && SecondTraits::emptyValueIsZero;
 174         static EmptyValueType emptyValue() { return std::make_pair(FirstTraits::emptyValue(), SecondTraits::emptyValue()); }
 175
 176         static const bool needsDestruction = FirstTraits::needsDestruction || SecondTraits::needsDestruction;
 177
 178         static const int minimumTableSize = FirstTraits::minimumTableSize;
 179
 180         static void constructDeletedValue(TraitType& slot) { FirstTraits::constructDeletedValue(slot.first); }
 181         static bool isDeletedValue(const TraitType& value) { return FirstTraits::isDeletedValue(value.first); }
 182     };
 183
 184     template<typename First, typename Second>
 185     struct HashTraits<std::pair<First, Second> > : public PairHashTraits<HashTraits<First>, HashTraits<Second> > { };
 186
 187     template<typename KeyTypeArg, typename ValueTypeArg>
 188     struct KeyValuePair {
 189         typedef KeyTypeArg KeyType;
 190
 191         KeyValuePair()
 192         {
 193         }
 194
 195         KeyValuePair(const KeyTypeArg& key, const ValueTypeArg& value)
 196             : first(key)
 197             , second(value)
 198         {
 199         }
 200
 201         template <typename OtherKeyType, typename OtherValueType>
 202         KeyValuePair(const KeyValuePair<OtherKeyType, OtherValueType>& other)
 203             : first(other.first)
 204             , second(other.second)
 205         {
 206         }
 207
 208         // TODO: Rename these to key and value. See https://bugs.webkit.org/show_bug.cgi?id=82784.
 209         KeyTypeArg first;
 210         ValueTypeArg second;
 211     };
 212
 213     template<typename KeyTraitsArg, typename ValueTraitsArg>
 214     struct KeyValuePairHashTraits : GenericHashTraits<KeyValuePair<typename KeyTraitsArg::TraitType, typename ValueTraitsArg::TraitType> > {
 215         typedef KeyTraitsArg KeyTraits;
 216         typedef ValueTraitsArg ValueTraits;
 217         typedef KeyValuePair<typename KeyTraits::TraitType, typename ValueTraits::TraitType> TraitType;
 218         typedef KeyValuePair<typename KeyTraits::EmptyValueType, typename ValueTraits::EmptyValueType> EmptyValueType;
 219
 220         static const bool emptyValueIsZero = KeyTraits::emptyValueIsZero && ValueTraits::emptyValueIsZero;
 221         static EmptyValueType emptyValue() { return KeyValuePair<typename KeyTraits::EmptyValueType, typename ValueTraits::EmptyValueType>(KeyTraits::emptyValue(), ValueTraits::emptyValue()); }
 222
 223         static const bool needsDestruction = KeyTraits::needsDestruction || ValueTraits::needsDestruction;
 224
 225         static const int minimumTableSize = KeyTraits::minimumTableSize;
 226
 227         static void constructDeletedValue(TraitType& slot) { KeyTraits::constructDeletedValue(slot.first); }
 228         static bool isDeletedValue(const TraitType& value) { return KeyTraits::isDeletedValue(value.first); }
 229     };
 230
 231     template<typename Key, typename Value>
 232     struct HashTraits<KeyValuePair<Key, Value> > : public KeyValuePairHashTraits<HashTraits<Key>, HashTraits<Value> > { };
 233
 234 } // namespace WTF
 235
 236 using WTF::HashTraits;
 237 using WTF::PairHashTraits;
 238
 239 #endif // WTF_HashTraits_h