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 "HashFunctions.h" |
25 | #include "TypeTraits.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 HashTraits; |
35 | |
36 | template<bool isInteger, typename T> struct GenericHashTraitsBase; |
37 | |
38 | template<typename T> struct GenericHashTraitsBase<false, T> { |
39 | static const bool emptyValueIsZero = false; |
40 | static const bool needsDestruction = true; |
41 | }; |
42 | |
43 | // Default integer traits disallow both 0 and -1 as keys (max value instead of -1 for unsigned). |
44 | template<typename T> struct GenericHashTraitsBase<true, T> { |
45 | static const bool emptyValueIsZero = true; |
46 | static const bool needsDestruction = false; |
47 | static void constructDeletedValue(T& slot) { slot = static_cast<T>(-1); } |
48 | static bool isDeletedValue(T value) { return value == static_cast<T>(-1); } |
49 | }; |
50 | |
51 | template<typename T> struct GenericHashTraits : GenericHashTraitsBase<IsInteger<T>::value, T> { |
52 | typedef T TraitType; |
53 | static T emptyValue() { return T(); } |
54 | }; |
55 | |
56 | template<typename T> struct HashTraits : GenericHashTraits<T> { }; |
57 | |
58 | template<typename T> struct FloatHashTraits : GenericHashTraits<T> { |
59 | static const bool needsDestruction = false; |
60 | static T emptyValue() { return std::numeric_limits<T>::infinity(); } |
61 | static void constructDeletedValue(T& slot) { slot = -std::numeric_limits<T>::infinity(); } |
62 | static bool isDeletedValue(T value) { return value == -std::numeric_limits<T>::infinity(); } |
63 | }; |
64 | |
65 | template<> struct HashTraits<float> : FloatHashTraits<float> { }; |
66 | template<> struct HashTraits<double> : FloatHashTraits<double> { }; |
67 | |
68 | // Default unsigned traits disallow both 0 and max as keys -- use these traits to allow zero and disallow max - 1. |
69 | template<typename T> struct UnsignedWithZeroKeyHashTraits : GenericHashTraits<T> { |
70 | static const bool emptyValueIsZero = false; |
71 | static const bool needsDestruction = false; |
72 | static T emptyValue() { return std::numeric_limits<T>::max(); } |
73 | static void constructDeletedValue(T& slot) { slot = std::numeric_limits<T>::max() - 1; } |
74 | static bool isDeletedValue(T value) { return value == std::numeric_limits<T>::max() - 1; } |
75 | }; |
76 | |
77 | template<typename P> struct HashTraits<P*> : GenericHashTraits<P*> { |
78 | static const bool emptyValueIsZero = true; |
79 | static const bool needsDestruction = false; |
80 | static void constructDeletedValue(P*& slot) { slot = reinterpret_cast<P*>(-1); } |
81 | static bool isDeletedValue(P* value) { return value == reinterpret_cast<P*>(-1); } |
82 | }; |
83 | |
84 | template<typename P> struct HashTraits<RefPtr<P> > : GenericHashTraits<RefPtr<P> > { |
85 | static const bool emptyValueIsZero = true; |
86 | static void constructDeletedValue(RefPtr<P>& slot) { new (&slot) RefPtr<P>(HashTableDeletedValue); } |
87 | static bool isDeletedValue(const RefPtr<P>& value) { return value.isHashTableDeletedValue(); } |
88 | }; |
89 | |
90 | // special traits for pairs, helpful for their use in HashMap implementation |
91 | |
92 | template<typename FirstTraitsArg, typename SecondTraitsArg> |
93 | struct PairHashTraits : GenericHashTraits<pair<typename FirstTraitsArg::TraitType, typename SecondTraitsArg::TraitType> > { |
94 | typedef FirstTraitsArg FirstTraits; |
95 | typedef SecondTraitsArg SecondTraits; |
96 | typedef pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> TraitType; |
97 | |
98 | static const bool emptyValueIsZero = FirstTraits::emptyValueIsZero && SecondTraits::emptyValueIsZero; |
99 | static TraitType emptyValue() { return make_pair(FirstTraits::emptyValue(), SecondTraits::emptyValue()); } |
100 | |
101 | static const bool needsDestruction = FirstTraits::needsDestruction || SecondTraits::needsDestruction; |
102 | |
103 | static void constructDeletedValue(TraitType& slot) { FirstTraits::constructDeletedValue(slot.first); } |
104 | static bool isDeletedValue(const TraitType& value) { return FirstTraits::isDeletedValue(value.first); } |
105 | }; |
106 | |
107 | template<typename First, typename Second> |
108 | struct HashTraits<pair<First, Second> > : public PairHashTraits<HashTraits<First>, HashTraits<Second> > { }; |
109 | |
110 | } // namespace WTF |
111 | |
112 | using WTF::HashTraits; |
113 | using WTF::PairHashTraits; |
114 | |
115 | #endif // WTF_HashTraits_h |
116 | |