src/third_party/WebKit/Source/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/HashTableDeletedValueType.h"
  26 #include "wtf/StdLibExtras.h"
  27 #include "wtf/TypeTraits.h"
  28 #include <utility>
  29 #include <limits>
  30
  31 namespace WTF {
  32
  33     class String;
  34
  35     template<typename T> class OwnPtr;
  36     template<typename T> class PassOwnPtr;
  37
  38     template<typename T> struct HashTraits;
  39
  40     template<bool isInteger, typename T> struct GenericHashTraitsBase;
  41
  42     template<typename T> struct GenericHashTraitsBase<false, T> {
  43         // The emptyValueIsZero flag is used to optimize allocation of empty hash tables with zeroed memory.
  44         static const bool emptyValueIsZero = false;
  45
  46         // The hasIsEmptyValueFunction flag allows the hash table to automatically generate code to check
  47         // for the empty value when it can be done with the equality operator, but allows custom functions
  48         // for cases like String that need them.
  49         static const bool hasIsEmptyValueFunction = false;
  50
  51         // The needsDestruction flag is used to optimize destruction and rehashing.
  52         static const bool needsDestruction = true;
  53
  54         // The starting table size. Can be overridden when we know beforehand that
  55         // a hash table will have at least N entries.
  56 #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
  57         static const unsigned minimumTableSize = 1;
  58 #else
  59         static const unsigned minimumTableSize = 8;
  60 #endif
  61
  62         static const bool needsTracing = NeedsTracing<T>::value;
  63         static const bool isWeak = IsWeak<T>::value;
  64     };
  65
  66     // Default integer traits disallow both 0 and -1 as keys (max value instead of -1 for unsigned).
  67     template<typename T> struct GenericHashTraitsBase<true, T> : GenericHashTraitsBase<false, T> {
  68         static const bool emptyValueIsZero = true;
  69         static const bool needsDestruction = false;
  70         static void constructDeletedValue(T& slot) { slot = static_cast<T>(-1); }
  71         static bool isDeletedValue(T value) { return value == static_cast<T>(-1); }
  72     };
  73
  74     template<typename T> struct GenericHashTraits : GenericHashTraitsBase<IsInteger<T>::value, T> {
  75         typedef T TraitType;
  76         typedef T EmptyValueType;
  77
  78         static T emptyValue() { return T(); }
  79
  80         // Type for functions that do not take ownership, such as contains.
  81         typedef const T& PeekInType;
  82         typedef T* IteratorGetType;
  83         typedef const T* IteratorConstGetType;
  84         typedef T& IteratorReferenceType;
  85         typedef const T& IteratorConstReferenceType;
  86         static IteratorConstGetType getToConstGetConversion(const T* x) { return x; }
  87         static IteratorReferenceType getToReferenceConversion(IteratorGetType x) { return *x; }
  88         static IteratorConstReferenceType getToReferenceConstConversion(IteratorConstGetType x) { return *x; }
  89         // Type for functions that take ownership, such as add.
  90         // The store function either not be called or called once to store something passed in.
  91         // The value passed to the store function will be PassInType.
  92         typedef const T& PassInType;
  93         static void store(const T& value, T& storage) { storage = value; }
  94
  95         // Type for return value of functions that transfer ownership, such as take.
  96         typedef T PassOutType;
  97         static PassOutType passOut(const T& value) { return value; }
  98
  99         // Type for return value of functions that do not transfer ownership, such as get.
 100         // FIXME: We could change this type to const T& for better performance if we figured out
 101         // a way to handle the return value from emptyValue, which is a temporary.
 102         typedef T PeekOutType;
 103         static PeekOutType peek(const T& value) { return value; }
 104     };
 105
 106     template<typename T> struct HashTraits : GenericHashTraits<T> { };
 107
 108     template<typename T> struct FloatHashTraits : GenericHashTraits<T> {
 109         static const bool needsDestruction = false;
 110         static T emptyValue() { return std::numeric_limits<T>::infinity(); }
 111         static void constructDeletedValue(T& slot) { slot = -std::numeric_limits<T>::infinity(); }
 112         static bool isDeletedValue(T value) { return value == -std::numeric_limits<T>::infinity(); }
 113     };
 114
 115     template<> struct HashTraits<float> : FloatHashTraits<float> { };
 116     template<> struct HashTraits<double> : FloatHashTraits<double> { };
 117
 118     // Default unsigned traits disallow both 0 and max as keys -- use these traits to allow zero and disallow max - 1.
 119     template<typename T> struct UnsignedWithZeroKeyHashTraits : GenericHashTraits<T> {
 120         static const bool emptyValueIsZero = false;
 121         static const bool needsDestruction = false;
 122         static T emptyValue() { return std::numeric_limits<T>::max(); }
 123         static void constructDeletedValue(T& slot) { slot = std::numeric_limits<T>::max() - 1; }
 124         static bool isDeletedValue(T value) { return value == std::numeric_limits<T>::max() - 1; }
 125     };
 126
 127     template<typename P> struct HashTraits<P*> : GenericHashTraits<P*> {
 128         static const bool emptyValueIsZero = true;
 129         static const bool needsDestruction = false;
 130         static void constructDeletedValue(P*& slot) { slot = reinterpret_cast<P*>(-1); }
 131         static bool isDeletedValue(P* value) { return value == reinterpret_cast<P*>(-1); }
 132     };
 133
 134     template<typename T> struct SimpleClassHashTraits : GenericHashTraits<T> {
 135         static const bool emptyValueIsZero = true;
 136         static void constructDeletedValue(T& slot) { new (NotNull, &slot) T(HashTableDeletedValue); }
 137         static bool isDeletedValue(const T& value) { return value.isHashTableDeletedValue(); }
 138     };
 139
 140     template<typename P> struct HashTraits<OwnPtr<P> > : SimpleClassHashTraits<OwnPtr<P> > {
 141         typedef std::nullptr_t EmptyValueType;
 142
 143         static EmptyValueType emptyValue() { return nullptr; }
 144
 145         typedef const OwnPtr<P>& PeekInType;
 146         typedef typename OwnPtr<P>::PtrType IteratorGetType;
 147         typedef const IteratorGetType IteratorConstGetType;
 148         typedef typename OwnPtr<P>::ValueType& IteratorReferenceType;
 149         typedef const IteratorReferenceType IteratorConstReferenceType;
 150         static IteratorReferenceType getToReferenceConversion(IteratorGetType x) { return *x; }
 151         static IteratorConstReferenceType getToReferenceConstConversion(IteratorConstGetType x) { return *x; }
 152         typedef PassOwnPtr<P> PassInType;
 153         static void store(PassOwnPtr<P> value, OwnPtr<P>& storage) { storage = value; }
 154
 155         typedef PassOwnPtr<P> PassOutType;
 156         static PassOwnPtr<P> passOut(OwnPtr<P>& value) { return value.release(); }
 157         static PassOwnPtr<P> passOut(std::nullptr_t) { return nullptr; }
 158
 159         typedef typename OwnPtr<P>::PtrType PeekOutType;
 160         static PeekOutType peek(const OwnPtr<P>& value) { return value.get(); }
 161         static PeekOutType peek(std::nullptr_t) { return 0; }
 162     };
 163
 164     template<typename P> struct HashTraits<RefPtr<P> > : SimpleClassHashTraits<RefPtr<P> > {
 165         typedef const RefPtr<P>& PeekInType;
 166         typedef RefPtr<P>* IteratorGetType;
 167         typedef const RefPtr<P>* IteratorConstGetType;
 168         typedef RefPtr<P>& IteratorReferenceType;
 169         typedef const RefPtr<P>& IteratorConstReferenceType;
 170         static IteratorReferenceType getToReferenceConversion(IteratorGetType x) { return *x; }
 171         static IteratorConstReferenceType getToReferenceConstConversion(IteratorConstGetType x) { return *x; }
 172
 173         static P* emptyValue() { return 0; }
 174
 175         typedef PassRefPtr<P> PassInType;
 176         static void store(PassRefPtr<P> value, RefPtr<P>& storage) { storage = value; }
 177
 178         typedef PassRefPtr<P> PassOutType;
 179         static PassRefPtr<P> passOut(RefPtr<P>& value) { return value.release(); }
 180         static PassRefPtr<P> passOut(P* value) { return value; }
 181
 182         typedef P* PeekOutType;
 183         static PeekOutType peek(const RefPtr<P>& value) { return value.get(); }
 184         static PeekOutType peek(P* value) { return value; }
 185     };
 186
 187     template<> struct HashTraits<String> : SimpleClassHashTraits<String> {
 188         static const bool hasIsEmptyValueFunction = true;
 189         static bool isEmptyValue(const String&);
 190     };
 191
 192     // This struct template is an implementation detail of the isHashTraitsEmptyValue function,
 193     // which selects either the emptyValue function or the isEmptyValue function to check for empty values.
 194     template<typename Traits, bool hasEmptyValueFunction> struct HashTraitsEmptyValueChecker;
 195     template<typename Traits> struct HashTraitsEmptyValueChecker<Traits, true> {
 196         template<typename T> static bool isEmptyValue(const T& value) { return Traits::isEmptyValue(value); }
 197     };
 198     template<typename Traits> struct HashTraitsEmptyValueChecker<Traits, false> {
 199         template<typename T> static bool isEmptyValue(const T& value) { return value == Traits::emptyValue(); }
 200     };
 201     template<typename Traits, typename T> inline bool isHashTraitsEmptyValue(const T& value)
 202     {
 203         return HashTraitsEmptyValueChecker<Traits, Traits::hasIsEmptyValueFunction>::isEmptyValue(value);
 204     }
 205
 206     template<typename FirstTraitsArg, typename SecondTraitsArg>
 207     struct PairHashTraits : GenericHashTraits<std::pair<typename FirstTraitsArg::TraitType, typename SecondTraitsArg::TraitType> > {
 208         typedef FirstTraitsArg FirstTraits;
 209         typedef SecondTraitsArg SecondTraits;
 210         typedef std::pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> TraitType;
 211         typedef std::pair<typename FirstTraits::EmptyValueType, typename SecondTraits::EmptyValueType> EmptyValueType;
 212
 213         static const bool emptyValueIsZero = FirstTraits::emptyValueIsZero && SecondTraits::emptyValueIsZero;
 214         static EmptyValueType emptyValue() { return std::make_pair(FirstTraits::emptyValue(), SecondTraits::emptyValue()); }
 215
 216         static const bool needsDestruction = FirstTraits::needsDestruction || SecondTraits::needsDestruction;
 217
 218         static const unsigned minimumTableSize = FirstTraits::minimumTableSize;
 219
 220         static void constructDeletedValue(TraitType& slot) { FirstTraits::constructDeletedValue(slot.first); }
 221         static bool isDeletedValue(const TraitType& value) { return FirstTraits::isDeletedValue(value.first); }
 222     };
 223
 224     template<typename First, typename Second>
 225     struct HashTraits<std::pair<First, Second> > : public PairHashTraits<HashTraits<First>, HashTraits<Second> > { };
 226
 227     template<typename KeyTypeArg, typename ValueTypeArg>
 228     struct KeyValuePair {
 229         typedef KeyTypeArg KeyType;
 230
 231         KeyValuePair()
 232         {
 233         }
 234
 235         KeyValuePair(const KeyTypeArg& _key, const ValueTypeArg& _value)
 236             : key(_key)
 237             , value(_value)
 238         {
 239         }
 240
 241         template <typename OtherKeyType, typename OtherValueType>
 242         KeyValuePair(const KeyValuePair<OtherKeyType, OtherValueType>& other)
 243             : key(other.key)
 244             , value(other.value)
 245         {
 246         }
 247
 248         KeyTypeArg key;
 249         ValueTypeArg value;
 250     };
 251
 252     template<typename KeyTraitsArg, typename ValueTraitsArg>
 253     struct KeyValuePairHashTraits : GenericHashTraits<KeyValuePair<typename KeyTraitsArg::TraitType, typename ValueTraitsArg::TraitType> > {
 254         typedef KeyTraitsArg KeyTraits;
 255         typedef ValueTraitsArg ValueTraits;
 256         typedef KeyValuePair<typename KeyTraits::TraitType, typename ValueTraits::TraitType> TraitType;
 257         typedef KeyValuePair<typename KeyTraits::EmptyValueType, typename ValueTraits::EmptyValueType> EmptyValueType;
 258
 259         static const bool emptyValueIsZero = KeyTraits::emptyValueIsZero && ValueTraits::emptyValueIsZero;
 260         static EmptyValueType emptyValue() { return KeyValuePair<typename KeyTraits::EmptyValueType, typename ValueTraits::EmptyValueType>(KeyTraits::emptyValue(), ValueTraits::emptyValue()); }
 261
 262         static const bool needsDestruction = KeyTraits::needsDestruction || ValueTraits::needsDestruction;
 263         static const bool needsTracing = KeyTraits::needsTracing || ValueTraits::needsTracing;
 264         static const bool isWeak = KeyTraits::isWeak || ValueTraits::isWeak;
 265
 266         static const unsigned minimumTableSize = KeyTraits::minimumTableSize;
 267
 268         static void constructDeletedValue(TraitType& slot) { KeyTraits::constructDeletedValue(slot.key); }
 269         static bool isDeletedValue(const TraitType& value) { return KeyTraits::isDeletedValue(value.key); }
 270     };
 271
 272     template<typename Key, typename Value>
 273     struct HashTraits<KeyValuePair<Key, Value> > : public KeyValuePairHashTraits<HashTraits<Key>, HashTraits<Value> > { };
 274
 275     template<typename T>
 276     struct NullableHashTraits : public HashTraits<T> {
 277         static const bool emptyValueIsZero = false;
 278         static T emptyValue() { return reinterpret_cast<T>(1); }
 279     };
 280
 281 } // namespace WTF
 282
 283 using WTF::HashTraits;
 284 using WTF::PairHashTraits;
 285 using WTF::NullableHashTraits;
 286 using WTF::SimpleClassHashTraits;
 287
 288 #endif // WTF_HashTraits_h