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