Home | History | Annotate | Download | only in wtf
      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 
     63     // Default integer traits disallow both 0 and -1 as keys (max value instead of -1 for unsigned).
     64     template<typename T> struct GenericHashTraitsBase<true, T> : GenericHashTraitsBase<false, T> {
     65         static const bool emptyValueIsZero = true;
     66         static const bool needsDestruction = false;
     67         static void constructDeletedValue(T& slot) { slot = static_cast<T>(-1); }
     68         static bool isDeletedValue(T value) { return value == static_cast<T>(-1); }
     69     };
     70 
     71     template<typename T> struct GenericHashTraits : GenericHashTraitsBase<IsInteger<T>::value, T> {
     72         typedef T TraitType;
     73         typedef T EmptyValueType;
     74 
     75         static T emptyValue() { return T(); }
     76 
     77         // Type for functions that take ownership, such as add.
     78         // The store function either not be called or called once to store something passed in.
     79         // The value passed to the store function will be either PassInType or PassInType&.
     80         typedef const T& PassInType;
     81         static void store(const T& value, T& storage) { storage = value; }
     82 
     83         // Type for return value of functions that transfer ownership, such as take.
     84         typedef T PassOutType;
     85         static PassOutType passOut(const T& value) { return value; }
     86         static T& passOut(T& value) { return value; } // Overloaded to avoid copying of non-temporary values.
     87 
     88         // Type for return value of functions that do not transfer ownership, such as get.
     89         // FIXME: We could change this type to const T& for better performance if we figured out
     90         // a way to handle the return value from emptyValue, which is a temporary.
     91         typedef T PeekType;
     92         static PeekType peek(const T& value) { return value; }
     93         static T& peek(T& value) { return value; } // Overloaded to avoid copying of non-temporary values.
     94     };
     95 
     96     template<typename T> struct HashTraits : GenericHashTraits<T> { };
     97 
     98     template<typename T> struct FloatHashTraits : GenericHashTraits<T> {
     99         static const bool needsDestruction = false;
    100         static T emptyValue() { return std::numeric_limits<T>::infinity(); }
    101         static void constructDeletedValue(T& slot) { slot = -std::numeric_limits<T>::infinity(); }
    102         static bool isDeletedValue(T value) { return value == -std::numeric_limits<T>::infinity(); }
    103     };
    104 
    105     template<> struct HashTraits<float> : FloatHashTraits<float> { };
    106     template<> struct HashTraits<double> : FloatHashTraits<double> { };
    107 
    108     // Default unsigned traits disallow both 0 and max as keys -- use these traits to allow zero and disallow max - 1.
    109     template<typename T> struct UnsignedWithZeroKeyHashTraits : GenericHashTraits<T> {
    110         static const bool emptyValueIsZero = false;
    111         static const bool needsDestruction = false;
    112         static T emptyValue() { return std::numeric_limits<T>::max(); }
    113         static void constructDeletedValue(T& slot) { slot = std::numeric_limits<T>::max() - 1; }
    114         static bool isDeletedValue(T value) { return value == std::numeric_limits<T>::max() - 1; }
    115     };
    116 
    117     template<typename P> struct HashTraits<P*> : GenericHashTraits<P*> {
    118         static const bool emptyValueIsZero = true;
    119         static const bool needsDestruction = false;
    120         static void constructDeletedValue(P*& slot) { slot = reinterpret_cast<P*>(-1); }
    121         static bool isDeletedValue(P* value) { return value == reinterpret_cast<P*>(-1); }
    122     };
    123 
    124     template<typename T> struct SimpleClassHashTraits : GenericHashTraits<T> {
    125         static const bool emptyValueIsZero = true;
    126         static void constructDeletedValue(T& slot) { new (NotNull, &slot) T(HashTableDeletedValue); }
    127         static bool isDeletedValue(const T& value) { return value.isHashTableDeletedValue(); }
    128     };
    129 
    130     template<typename P> struct HashTraits<OwnPtr<P> > : SimpleClassHashTraits<OwnPtr<P> > {
    131         typedef std::nullptr_t EmptyValueType;
    132 
    133         static EmptyValueType emptyValue() { return nullptr; }
    134 
    135         typedef PassOwnPtr<P> PassInType;
    136         static void store(PassOwnPtr<P> value, OwnPtr<P>& storage) { storage = value; }
    137 
    138         typedef PassOwnPtr<P> PassOutType;
    139         static PassOwnPtr<P> passOut(OwnPtr<P>& value) { return value.release(); }
    140         static PassOwnPtr<P> passOut(std::nullptr_t) { return nullptr; }
    141 
    142         typedef typename OwnPtr<P>::PtrType PeekType;
    143         static PeekType peek(const OwnPtr<P>& value) { return value.get(); }
    144         static PeekType peek(std::nullptr_t) { return 0; }
    145     };
    146 
    147     template<typename P> struct HashTraits<RefPtr<P> > : SimpleClassHashTraits<RefPtr<P> > {
    148         static P* emptyValue() { return 0; }
    149 
    150         typedef PassRefPtr<P> PassInType;
    151         static void store(PassRefPtr<P> value, RefPtr<P>& storage) { storage = value; }
    152 
    153         typedef PassRefPtr<P> PassOutType;
    154         static PassRefPtr<P> passOut(RefPtr<P>& value) { return value.release(); }
    155         static PassRefPtr<P> passOut(P* value) { return value; }
    156 
    157         typedef P* PeekType;
    158         static PeekType peek(const RefPtr<P>& value) { return value.get(); }
    159         static PeekType peek(P* value) { return value; }
    160     };
    161 
    162     template<> struct HashTraits<String> : SimpleClassHashTraits<String> {
    163         static const bool hasIsEmptyValueFunction = true;
    164         static bool isEmptyValue(const String&);
    165     };
    166 
    167     // This struct template is an implementation detail of the isHashTraitsEmptyValue function,
    168     // which selects either the emptyValue function or the isEmptyValue function to check for empty values.
    169     template<typename Traits, bool hasEmptyValueFunction> struct HashTraitsEmptyValueChecker;
    170     template<typename Traits> struct HashTraitsEmptyValueChecker<Traits, true> {
    171         template<typename T> static bool isEmptyValue(const T& value) { return Traits::isEmptyValue(value); }
    172     };
    173     template<typename Traits> struct HashTraitsEmptyValueChecker<Traits, false> {
    174         template<typename T> static bool isEmptyValue(const T& value) { return value == Traits::emptyValue(); }
    175     };
    176     template<typename Traits, typename T> inline bool isHashTraitsEmptyValue(const T& value)
    177     {
    178         return HashTraitsEmptyValueChecker<Traits, Traits::hasIsEmptyValueFunction>::isEmptyValue(value);
    179     }
    180 
    181     template<typename FirstTraitsArg, typename SecondTraitsArg>
    182     struct PairHashTraits : GenericHashTraits<std::pair<typename FirstTraitsArg::TraitType, typename SecondTraitsArg::TraitType> > {
    183         typedef FirstTraitsArg FirstTraits;
    184         typedef SecondTraitsArg SecondTraits;
    185         typedef std::pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> TraitType;
    186         typedef std::pair<typename FirstTraits::EmptyValueType, typename SecondTraits::EmptyValueType> EmptyValueType;
    187 
    188         static const bool emptyValueIsZero = FirstTraits::emptyValueIsZero && SecondTraits::emptyValueIsZero;
    189         static EmptyValueType emptyValue() { return std::make_pair(FirstTraits::emptyValue(), SecondTraits::emptyValue()); }
    190 
    191         static const bool needsDestruction = FirstTraits::needsDestruction || SecondTraits::needsDestruction;
    192 
    193         static const unsigned minimumTableSize = FirstTraits::minimumTableSize;
    194 
    195         static void constructDeletedValue(TraitType& slot) { FirstTraits::constructDeletedValue(slot.first); }
    196         static bool isDeletedValue(const TraitType& value) { return FirstTraits::isDeletedValue(value.first); }
    197     };
    198 
    199     template<typename First, typename Second>
    200     struct HashTraits<std::pair<First, Second> > : public PairHashTraits<HashTraits<First>, HashTraits<Second> > { };
    201 
    202     template<typename KeyTypeArg, typename ValueTypeArg>
    203     struct KeyValuePair {
    204         typedef KeyTypeArg KeyType;
    205 
    206         KeyValuePair()
    207         {
    208         }
    209 
    210         KeyValuePair(const KeyTypeArg& _key, const ValueTypeArg& _value)
    211             : key(_key)
    212             , value(_value)
    213         {
    214         }
    215 
    216         template <typename OtherKeyType, typename OtherValueType>
    217         KeyValuePair(const KeyValuePair<OtherKeyType, OtherValueType>& other)
    218             : key(other.key)
    219             , value(other.value)
    220         {
    221         }
    222 
    223         KeyTypeArg key;
    224         ValueTypeArg value;
    225     };
    226 
    227     template<typename KeyTraitsArg, typename ValueTraitsArg>
    228     struct KeyValuePairHashTraits : GenericHashTraits<KeyValuePair<typename KeyTraitsArg::TraitType, typename ValueTraitsArg::TraitType> > {
    229         typedef KeyTraitsArg KeyTraits;
    230         typedef ValueTraitsArg ValueTraits;
    231         typedef KeyValuePair<typename KeyTraits::TraitType, typename ValueTraits::TraitType> TraitType;
    232         typedef KeyValuePair<typename KeyTraits::EmptyValueType, typename ValueTraits::EmptyValueType> EmptyValueType;
    233 
    234         static const bool emptyValueIsZero = KeyTraits::emptyValueIsZero && ValueTraits::emptyValueIsZero;
    235         static EmptyValueType emptyValue() { return KeyValuePair<typename KeyTraits::EmptyValueType, typename ValueTraits::EmptyValueType>(KeyTraits::emptyValue(), ValueTraits::emptyValue()); }
    236 
    237         static const bool needsDestruction = KeyTraits::needsDestruction || ValueTraits::needsDestruction;
    238 
    239         static const unsigned minimumTableSize = KeyTraits::minimumTableSize;
    240 
    241         static void constructDeletedValue(TraitType& slot) { KeyTraits::constructDeletedValue(slot.key); }
    242         static bool isDeletedValue(const TraitType& value) { return KeyTraits::isDeletedValue(value.key); }
    243     };
    244 
    245     template<typename Key, typename Value>
    246     struct HashTraits<KeyValuePair<Key, Value> > : public KeyValuePairHashTraits<HashTraits<Key>, HashTraits<Value> > { };
    247 
    248     template<typename T>
    249     struct NullableHashTraits : public HashTraits<T> {
    250         static const bool emptyValueIsZero = false;
    251         static T emptyValue() { return reinterpret_cast<T>(1); }
    252     };
    253 
    254 } // namespace WTF
    255 
    256 using WTF::HashTraits;
    257 using WTF::PairHashTraits;
    258 using WTF::NullableHashTraits;
    259 using WTF::SimpleClassHashTraits;
    260 
    261 #endif // WTF_HashTraits_h
    262