source: webkit/trunk/JavaScriptCore/wtf/HashTraits.h@ 27885

Last change on this file since 27885 was 27334, checked in by kmccullo, 18 years ago

Reviewed by Sam.

  • Corrected spelling.
  • wtf/HashTraits.h:
  • Property svn:eol-style set to native
File size: 9.7 KB
Line 
1// -*- mode: c++; c-basic-offset: 4 -*-
2/*
3 * This file is part of the KDE libraries
4 * Copyright (C) 2005, 2006 Apple Computer, Inc.
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Library General Public
8 * License as published by the Free Software Foundation; either
9 * version 2 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Library General Public License for more details.
15 *
16 * You should have received a copy of the GNU Library General Public License
17 * along with this library; see the file COPYING.LIB. If not, write to
18 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
19 * Boston, MA 02110-1301, USA.
20 *
21 */
22
23#ifndef WTF_HashTraits_h
24#define WTF_HashTraits_h
25
26#include "HashFunctions.h"
27#include <utility>
28#include <limits>
29
30namespace WTF {
31
32 using std::pair;
33 using std::make_pair;
34
35 template<typename T> struct IsInteger { static const bool value = false; };
36 template<> struct IsInteger<bool> { static const bool value = true; };
37 template<> struct IsInteger<char> { static const bool value = true; };
38 template<> struct IsInteger<signed char> { static const bool value = true; };
39 template<> struct IsInteger<unsigned char> { static const bool value = true; };
40 template<> struct IsInteger<short> { static const bool value = true; };
41 template<> struct IsInteger<unsigned short> { static const bool value = true; };
42 template<> struct IsInteger<int> { static const bool value = true; };
43 template<> struct IsInteger<unsigned int> { static const bool value = true; };
44 template<> struct IsInteger<long> { static const bool value = true; };
45 template<> struct IsInteger<unsigned long> { static const bool value = true; };
46 template<> struct IsInteger<long long> { static const bool value = true; };
47 template<> struct IsInteger<unsigned long long> { static const bool value = true; };
48
49 template<typename T> struct HashTraits;
50
51 template<bool isInteger, typename T> struct GenericHashTraitsBase;
52 template<typename T> struct GenericHashTraitsBase<true, T> {
53 typedef T TraitType;
54 typedef HashTraits<typename IntTypes<sizeof(T)>::SignedType> StorageTraits;
55 static const bool emptyValueIsZero = true;
56 static const bool needsDestruction = false;
57 };
58 template<typename T> struct GenericHashTraitsBase<false, T> {
59 typedef T TraitType;
60 typedef HashTraits<T> StorageTraits;
61 static const bool emptyValueIsZero = false;
62 static const bool needsDestruction = true;
63 };
64
65 template<typename T> struct GenericHashTraits : GenericHashTraitsBase<IsInteger<T>::value, T> {
66 static T emptyValue() { return T(); }
67 static const bool needsRef = false;
68 };
69
70 template<typename T> struct HashTraits : GenericHashTraits<T> { };
71
72 // signed integer traits may not be appropriate for all uses since they disallow 0 and -1 as keys
73 template<> struct HashTraits<signed char> : GenericHashTraits<int> {
74 static signed char deletedValue() { return -1; }
75 };
76 template<> struct HashTraits<short> : GenericHashTraits<int> {
77 static short deletedValue() { return -1; }
78 };
79 template<> struct HashTraits<int> : GenericHashTraits<int> {
80 static int deletedValue() { return -1; }
81 };
82 template<> struct HashTraits<unsigned int> : GenericHashTraits<unsigned int> {
83 static unsigned int deletedValue() { return static_cast<unsigned int>(-1); }
84 };
85 template<> struct HashTraits<long> : GenericHashTraits<long> {
86 static long deletedValue() { return -1; }
87 };
88 template<> struct HashTraits<unsigned long> : GenericHashTraits<unsigned long> {
89 static unsigned long deletedValue() { return static_cast<unsigned long>(-1); }
90 };
91 template<> struct HashTraits<long long> : GenericHashTraits<long long> {
92 static long long deletedValue() { return -1; }
93 };
94 template<> struct HashTraits<unsigned long long> : GenericHashTraits<unsigned long long> {
95 static unsigned long long deletedValue() { return static_cast<unsigned long long>(-1); }
96 };
97
98 template<typename T> struct FloatHashTraits {
99 typedef T TraitType;
100 typedef HashTraits<T> StorageTraits;
101 static T emptyValue() { return std::numeric_limits<T>::infinity(); }
102 static T deletedValue() { return -std::numeric_limits<T>::infinity(); }
103 static const bool emptyValueIsZero = false;
104 static const bool needsDestruction = false;
105 static const bool needsRef = false;
106 };
107 template<> struct HashTraits<float> : FloatHashTraits<float> {
108 };
109 template<> struct HashTraits<double> : FloatHashTraits<double> {
110 };
111
112 template<typename P> struct HashTraits<P*> : GenericHashTraits<P*> {
113 typedef HashTraits<typename IntTypes<sizeof(P*)>::SignedType> StorageTraits;
114 static const bool emptyValueIsZero = true;
115 static const bool needsDestruction = false;
116 static P* deletedValue() { return reinterpret_cast<P*>(-1); }
117 };
118
119 template<typename P> struct HashTraits<RefPtr<P> > : GenericHashTraits<RefPtr<P> > {
120 typedef HashTraits<typename IntTypes<sizeof(P*)>::SignedType> StorageTraits;
121 typedef typename StorageTraits::TraitType StorageType;
122 static const bool emptyValueIsZero = true;
123 static const bool needsRef = true;
124
125 typedef union {
126 P* m_p;
127 StorageType m_s;
128 } UnionType;
129
130 static void ref(const StorageType& s)
131 {
132 if (const P* p = reinterpret_cast<const UnionType*>(&s)->m_p)
133 const_cast<P*>(p)->ref();
134 }
135 static void deref(const StorageType& s)
136 {
137 if (const P* p = reinterpret_cast<const UnionType*>(&s)->m_p)
138 const_cast<P*>(p)->deref();
139 }
140 };
141
142 // template to set deleted values
143
144 template<typename Traits> struct DeletedValueAssigner {
145 static void assignDeletedValue(typename Traits::TraitType& location) { location = Traits::deletedValue(); }
146 };
147
148 template<typename T, typename Traits> inline void assignDeleted(T& location)
149 {
150 DeletedValueAssigner<Traits>::assignDeletedValue(location);
151 }
152
153 // special traits for pairs, helpful for their use in HashMap implementation
154
155 template<typename FirstTraits, typename SecondTraits> struct PairHashTraits;
156
157 template<typename FirstTraitsArg, typename SecondTraitsArg>
158 struct PairBaseHashTraits : GenericHashTraits<pair<typename FirstTraitsArg::TraitType, typename SecondTraitsArg::TraitType> > {
159 typedef FirstTraitsArg FirstTraits;
160 typedef SecondTraitsArg SecondTraits;
161 typedef pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> TraitType;
162
163 typedef PairHashTraits<typename FirstTraits::StorageTraits, typename SecondTraits::StorageTraits> StorageTraits;
164
165 static const bool emptyValueIsZero = FirstTraits::emptyValueIsZero && SecondTraits::emptyValueIsZero;
166
167 static TraitType emptyValue()
168 {
169 return make_pair(FirstTraits::emptyValue(), SecondTraits::emptyValue());
170 }
171 };
172
173 template<typename FirstTraits, typename SecondTraits>
174 struct PairHashTraits : PairBaseHashTraits<FirstTraits, SecondTraits> {
175 typedef pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> TraitType;
176
177 static const bool needsDestruction = FirstTraits::needsDestruction || SecondTraits::needsDestruction;
178
179 static TraitType deletedValue()
180 {
181 return TraitType(FirstTraits::deletedValue(), SecondTraits::emptyValue());
182 }
183
184 static void assignDeletedValue(TraitType& location)
185 {
186 assignDeleted<typename FirstTraits::TraitType, FirstTraits>(location.first);
187 location.second = SecondTraits::emptyValue();
188 }
189 };
190
191 template<typename First, typename Second>
192 struct HashTraits<pair<First, Second> > : public PairHashTraits<HashTraits<First>, HashTraits<Second> > { };
193
194 template<typename FirstTraits, typename SecondTraits>
195 struct DeletedValueAssigner<PairHashTraits<FirstTraits, SecondTraits> >
196 {
197 static void assignDeletedValue(pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType>& location)
198 {
199 PairHashTraits<FirstTraits, SecondTraits>::assignDeletedValue(location);
200 }
201 };
202
203 template<typename First, typename Second>
204 struct DeletedValueAssigner<HashTraits<pair<First, Second> > >
205 {
206 static void assignDeletedValue(pair<First, Second>& location)
207 {
208 HashTraits<pair<First, Second> >::assignDeletedValue(location);
209 }
210 };
211
212 // hash functions and traits that are equivalent (for code sharing)
213
214 template<typename HashArg, typename TraitsArg> struct HashKeyStorageTraits {
215 typedef HashArg Hash;
216 typedef TraitsArg Traits;
217 };
218 template<typename P> struct HashKeyStorageTraits<PtrHash<P*>, HashTraits<P*> > {
219 typedef typename IntTypes<sizeof(P*)>::SignedType IntType;
220 typedef IntHash<IntType> Hash;
221 typedef HashTraits<IntType> Traits;
222 };
223 template<typename P> struct HashKeyStorageTraits<PtrHash<RefPtr<P> >, HashTraits<RefPtr<P> > > {
224 typedef typename IntTypes<sizeof(P*)>::SignedType IntType;
225 typedef IntHash<IntType> Hash;
226 typedef HashTraits<IntType> Traits;
227 };
228
229} // namespace WTF
230
231using WTF::HashTraits;
232using WTF::PairHashTraits;
233
234#endif // WTF_HashTraits_h
Note: See TracBrowser for help on using the repository browser.