← Back to branch summary

~ubuntu-branches/ubuntu/raring/qtwebkit-source/raring-proposed

« back to all changes in this revision

Viewing changes to Source/WTF/wtf/text/StringHash.h

  • Committer: Package Import Robot
  • Author(s): Jonathan Riddell
  • Date: 2013-02-18 14:24:18 UTC
  • Revision ID: package-import@ubuntu.com-20130218142418-eon0jmjg3nj438uy
Tags: upstream-2.3
Import upstream version 2.3

Show diffs side-by-side

added added

removed removed

Lines of Context:
Source/WTF/wtf/text/StringHash.h
 
1
/*
 
2
 * Copyright (C) 2006, 2007, 2008, 2012 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 <wtf/text/AtomicString.h>
 
26
#include <wtf/HashTraits.h>
 
27
#include <wtf/StringHasher.h>
 
28
 
 
29
namespace WTF {
 
30
 
 
31
    inline bool HashTraits<String>::isEmptyValue(const String& value)
 
32
    {
 
33
        return value.isNull();
 
34
    }
 
35
 
 
36
    // The hash() functions on StringHash and CaseFoldingHash do not support
 
37
    // null strings. get(), contains(), and add() on HashMap<String,..., StringHash>
 
38
    // cause a null-pointer dereference when passed null strings.
 
39
 
 
40
    // FIXME: We should really figure out a way to put the computeHash function that's
 
41
    // currently a member function of StringImpl into this file so we can be a little
 
42
    // closer to having all the nearly-identical hash functions in one place.
 
43
 
 
44
    struct StringHash {
 
45
        static unsigned hash(StringImpl* key) { return key->hash(); }
 
46
        static bool equal(const StringImpl* a, const StringImpl* b)
 
47
        {
 
48
            if (a == b)
 
49
                return true;
 
50
            if (!a || !b)
 
51
                return false;
 
52
 
 
53
            unsigned aLength = a->length();
 
54
            unsigned bLength = b->length();
 
55
            if (aLength != bLength)
 
56
                return false;
 
57
 
 
58
            if (a->is8Bit()) {
 
59
                if (b->is8Bit())
 
60
                    return WTF::equal(a->characters8(), b->characters8(), aLength);
 
61
 
 
62
                return WTF::equal(a->characters8(), b->characters16(), aLength);
 
63
            }
 
64
 
 
65
            if (b->is8Bit())
 
66
                return WTF::equal(a->characters16(), b->characters8(), aLength);
 
67
 
 
68
            return WTF::equal(a->characters16(), b->characters16(), aLength);
 
69
        }
 
70
 
 
71
        static unsigned hash(const RefPtr<StringImpl>& key) { return key->hash(); }
 
72
        static bool equal(const RefPtr<StringImpl>& a, const RefPtr<StringImpl>& b)
 
73
        {
 
74
            return equal(a.get(), b.get());
 
75
        }
 
76
 
 
77
        static unsigned hash(const String& key) { return key.impl()->hash(); }
 
78
        static bool equal(const String& a, const String& b)
 
79
        {
 
80
            return equal(a.impl(), b.impl());
 
81
        }
 
82
 
 
83
        static const bool safeToCompareToEmptyOrDeleted = false;
 
84
    };
 
85
 
 
86
    class CaseFoldingHash {
 
87
    public:
 
88
        template<typename T> static inline UChar foldCase(T ch)
 
89
        {
 
90
            return WTF::Unicode::foldCase(ch);
 
91
        }
 
92
 
 
93
        static unsigned hash(const UChar* data, unsigned length)
 
94
        {
 
95
            return StringHasher::computeHashAndMaskTop8Bits<UChar, foldCase<UChar> >(data, length);
 
96
        }
 
97
 
 
98
        static unsigned hash(StringImpl* str)
 
99
        {
 
100
            if (str->is8Bit())
 
101
                return hash(str->characters8(), str->length());
 
102
            return hash(str->characters16(), str->length());
 
103
        }
 
104
 
 
105
        static unsigned hash(const LChar* data, unsigned length)
 
106
        {
 
107
            return StringHasher::computeHashAndMaskTop8Bits<LChar, foldCase<LChar> >(data, length);
 
108
        }
 
109
 
 
110
        static inline unsigned hash(const char* data, unsigned length)
 
111
        {
 
112
            return CaseFoldingHash::hash(reinterpret_cast<const LChar*>(data), length);
 
113
        }
 
114
        
 
115
        static bool equal(const StringImpl* a, const StringImpl* b)
 
116
        {
 
117
            if (a == b)
 
118
                return true;
 
119
            if (!a || !b)
 
120
                return false;
 
121
            unsigned length = a->length();
 
122
            if (length != b->length())
 
123
                return false;
 
124
 
 
125
            if (a->is8Bit()) {
 
126
                if (b->is8Bit())
 
127
                    return equalIgnoringCase(a->characters8(), b->characters8(), length);
 
128
 
 
129
                return equalIgnoringCase(b->characters16(), a->characters8(), length);
 
130
            }
 
131
 
 
132
            if (b->is8Bit())
 
133
                return equalIgnoringCase(a->characters16(), b->characters8(), length);
 
134
 
 
135
            return equalIgnoringCase(a->characters16(), b->characters16(), length);
 
136
        }
 
137
 
 
138
        static unsigned hash(const RefPtr<StringImpl>& key) 
 
139
        {
 
140
            return hash(key.get());
 
141
        }
 
142
 
 
143
        static bool equal(const RefPtr<StringImpl>& a, const RefPtr<StringImpl>& b)
 
144
        {
 
145
            return equal(a.get(), b.get());
 
146
        }
 
147
 
 
148
        static unsigned hash(const String& key)
 
149
        {
 
150
            return hash(key.impl());
 
151
        }
 
152
        static unsigned hash(const AtomicString& key)
 
153
        {
 
154
            return hash(key.impl());
 
155
        }
 
156
        static bool equal(const String& a, const String& b)
 
157
        {
 
158
            return equal(a.impl(), b.impl());
 
159
        }
 
160
        static bool equal(const AtomicString& a, const AtomicString& b)
 
161
        {
 
162
            return (a == b) || equal(a.impl(), b.impl());
 
163
        }
 
164
 
 
165
        static const bool safeToCompareToEmptyOrDeleted = false;
 
166
    };
 
167
 
 
168
    // This hash can be used in cases where the key is a hash of a string, but we don't
 
169
    // want to store the string. It's not really specific to string hashing, but all our
 
170
    // current uses of it are for strings.
 
171
    struct AlreadyHashed : IntHash<unsigned> {
 
172
        static unsigned hash(unsigned key) { return key; }
 
173
 
 
174
        // To use a hash value as a key for a hash table, we need to eliminate the
 
175
        // "deleted" value, which is negative one. That could be done by changing
 
176
        // the string hash function to never generate negative one, but this works
 
177
        // and is still relatively efficient.
 
178
        static unsigned avoidDeletedValue(unsigned hash)
 
179
        {
 
180
            ASSERT(hash);
 
181
            unsigned newHash = hash | (!(hash + 1) << 31);
 
182
            ASSERT(newHash);
 
183
            ASSERT(newHash != 0xFFFFFFFF);
 
184
            return newHash;
 
185
        }
 
186
    };
 
187
 
 
188
}
 
189
 
 
190
using WTF::AlreadyHashed;
 
191
using WTF::CaseFoldingHash;
 
192
using WTF::StringHash;
 
193
 
 
194
#endif