1/*
2 * Copyright (C) 2006, 2007, 2008 Apple Inc. All rights reserved
3 * Copyright (C) Research In Motion Limited 2009. All rights reserved.
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Library General Public
7 * License as published by the Free Software Foundation; either
8 * version 2 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13 * Library General Public License for more details.
14 *
15 * You should have received a copy of the GNU Library General Public License
16 * along with this library; see the file COPYING.LIB.  If not, write to
17 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18 * Boston, MA 02110-1301, USA.
19 *
20 */
21
22#ifndef StringHash_h
23#define StringHash_h
24
25#include "AtomicString.h"
26#include "WTFString.h"
27#include <wtf/Forward.h>
28#include <wtf/HashTraits.h>
29#include <wtf/StringHasher.h>
30#include <wtf/unicode/Unicode.h>
31
32namespace WTF {
33
34    // The hash() functions on StringHash and CaseFoldingHash do not support
35    // null strings. get(), contains(), and add() on HashMap<String,..., StringHash>
36    // cause a null-pointer dereference when passed null strings.
37
38    // FIXME: We should really figure out a way to put the computeHash function that's
39    // currently a member function of StringImpl into this file so we can be a little
40    // closer to having all the nearly-identical hash functions in one place.
41
42    struct StringHash {
43        static unsigned hash(StringImpl* key) { return key->hash(); }
44        static bool equal(const StringImpl* a, const StringImpl* b)
45        {
46            if (a == b)
47                return true;
48            if (!a || !b)
49                return false;
50
51            unsigned aLength = a->length();
52            unsigned bLength = b->length();
53            if (aLength != bLength)
54                return false;
55
56            // FIXME: perhaps we should have a more abstract macro that indicates when
57            // going 4 bytes at a time is unsafe
58#if CPU(ARM) || CPU(SH4) || CPU(MIPS)
59            const UChar* aChars = a->characters();
60            const UChar* bChars = b->characters();
61            for (unsigned i = 0; i != aLength; ++i) {
62                if (*aChars++ != *bChars++)
63                    return false;
64            }
65            return true;
66#else
67            /* Do it 4-bytes-at-a-time on architectures where it's safe */
68            const uint32_t* aChars = reinterpret_cast<const uint32_t*>(a->characters());
69            const uint32_t* bChars = reinterpret_cast<const uint32_t*>(b->characters());
70
71            unsigned halfLength = aLength >> 1;
72            for (unsigned i = 0; i != halfLength; ++i)
73                if (*aChars++ != *bChars++)
74                    return false;
75
76            if (aLength & 1 && *reinterpret_cast<const uint16_t*>(aChars) != *reinterpret_cast<const uint16_t*>(bChars))
77                return false;
78
79            return true;
80#endif
81        }
82
83        static unsigned hash(const RefPtr<StringImpl>& key) { return key->hash(); }
84        static bool equal(const RefPtr<StringImpl>& a, const RefPtr<StringImpl>& b)
85        {
86            return equal(a.get(), b.get());
87        }
88
89        static unsigned hash(const String& key) { return key.impl()->hash(); }
90        static bool equal(const String& a, const String& b)
91        {
92            return equal(a.impl(), b.impl());
93        }
94
95        static const bool safeToCompareToEmptyOrDeleted = false;
96    };
97
98    class CaseFoldingHash {
99    public:
100        template<typename T> static inline UChar foldCase(T ch)
101        {
102            return WTF::Unicode::foldCase(ch);
103        }
104
105        static unsigned hash(const UChar* data, unsigned length)
106        {
107            return StringHasher::computeHash<UChar, foldCase<UChar> >(data, length);
108        }
109
110        static unsigned hash(StringImpl* str)
111        {
112            return hash(str->characters(), str->length());
113        }
114
115        static unsigned hash(const char* data, unsigned length)
116        {
117            return StringHasher::computeHash<char, foldCase<char> >(data, length);
118        }
119
120        static bool equal(const StringImpl* a, const StringImpl* b)
121        {
122            if (a == b)
123                return true;
124            if (!a || !b)
125                return false;
126            unsigned length = a->length();
127            if (length != b->length())
128                return false;
129            return WTF::Unicode::umemcasecmp(a->characters(), b->characters(), length) == 0;
130        }
131
132        static unsigned hash(const RefPtr<StringImpl>& key)
133        {
134            return hash(key.get());
135        }
136
137        static bool equal(const RefPtr<StringImpl>& a, const RefPtr<StringImpl>& b)
138        {
139            return equal(a.get(), b.get());
140        }
141
142        static unsigned hash(const String& key)
143        {
144            return hash(key.impl());
145        }
146        static unsigned hash(const AtomicString& key)
147        {
148            return hash(key.impl());
149        }
150        static bool equal(const String& a, const String& b)
151        {
152            return equal(a.impl(), b.impl());
153        }
154        static bool equal(const AtomicString& a, const AtomicString& b)
155        {
156            return (a == b) || equal(a.impl(), b.impl());
157        }
158
159        static const bool safeToCompareToEmptyOrDeleted = false;
160    };
161
162    // This hash can be used in cases where the key is a hash of a string, but we don't
163    // want to store the string. It's not really specific to string hashing, but all our
164    // current uses of it are for strings.
165    struct AlreadyHashed : IntHash<unsigned> {
166        static unsigned hash(unsigned key) { return key; }
167
168        // To use a hash value as a key for a hash table, we need to eliminate the
169        // "deleted" value, which is negative one. That could be done by changing
170        // the string hash function to never generate negative one, but this works
171        // and is still relatively efficient.
172        static unsigned avoidDeletedValue(unsigned hash)
173        {
174            ASSERT(hash);
175            unsigned newHash = hash | (!(hash + 1) << 31);
176            ASSERT(newHash);
177            ASSERT(newHash != 0xFFFFFFFF);
178            return newHash;
179        }
180    };
181
182    template<> struct HashTraits<String> : SimpleClassHashTraits<String> { };
183
184}
185
186using WTF::StringHash;
187using WTF::CaseFoldingHash;
188using WTF::AlreadyHashed;
189
190#endif
191