Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(923)

Unified Diff: src/objects.cc

Issue 9124004: Backport hash collision workaround to 3.6. (Closed) Base URL: http://v8.googlecode.com/svn/branches/3.6/
Patch Set: Created 8 years, 11 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« src/objects.h ('K') | « src/objects.h ('k') | src/objects-inl.h » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/objects.cc
===================================================================
--- src/objects.cc (revision 10353)
+++ src/objects.cc (working copy)
@@ -5926,6 +5926,20 @@
// Fast check: if hash code is computed for both strings
// a fast negative check can be performed.
if (HasHashCode() && other->HasHashCode()) {
+#ifdef DEBUG
+ if (FLAG_enable_slow_asserts) {
+ if (Hash() != other->Hash()) {
+ bool found_difference = false;
+ for (int i = 0; i < len; i++) {
+ if (Get(i) != other->Get(i)) {
+ found_difference = true;
+ break;
+ }
+ }
+ ASSERT(found_difference);
+ }
+ }
+#endif
if (Hash() != other->Hash()) return false;
}
@@ -6061,12 +6075,16 @@
// Compute the hash code.
uint32_t field = 0;
if (StringShape(this).IsSequentialAscii()) {
- field = HashSequentialString(SeqAsciiString::cast(this)->GetChars(), len);
+ field = HashSequentialString(SeqAsciiString::cast(this)->GetChars(),
+ len,
+ GetHeap()->StringHashSeed());
} else if (StringShape(this).IsSequentialTwoByte()) {
- field = HashSequentialString(SeqTwoByteString::cast(this)->GetChars(), len);
+ field = HashSequentialString(SeqTwoByteString::cast(this)->GetChars(),
+ len,
+ GetHeap()->StringHashSeed());
} else {
StringInputBuffer buffer(this);
- field = ComputeHashField(&buffer, len);
+ field = ComputeHashField(&buffer, len, GetHeap()->StringHashSeed());
}
// Store the hash code in the object.
@@ -6157,8 +6175,9 @@
uint32_t String::ComputeHashField(unibrow::CharacterStream* buffer,
- int length) {
- StringHasher hasher(length);
+ int length,
+ uint32_t seed) {
+ StringHasher hasher(length, seed);
// Very long strings have a trivial hash that doesn't inspect the
// string contents.
@@ -9542,8 +9561,8 @@
// Utf8SymbolKey carries a vector of chars as key.
class Utf8SymbolKey : public HashTableKey {
public:
- explicit Utf8SymbolKey(Vector<const char> string)
- : string_(string), hash_field_(0) { }
+ explicit Utf8SymbolKey(Vector<const char> string, uint32_t seed)
+ : string_(string), hash_field_(0), seed_(seed) { }
bool IsMatch(Object* string) {
return String::cast(string)->IsEqualTo(string_);
@@ -9554,7 +9573,7 @@
unibrow::Utf8InputBuffer<> buffer(string_.start(),
static_cast<unsigned>(string_.length()));
chars_ = buffer.Length();
- hash_field_ = String::ComputeHashField(&buffer, chars_);
+ hash_field_ = String::ComputeHashField(&buffer, chars_, seed_);
uint32_t result = hash_field_ >> String::kHashShift;
ASSERT(result != 0); // Ensure that the hash value of 0 is never computed.
return result;
@@ -9573,17 +9592,18 @@
Vector<const char> string_;
uint32_t hash_field_;
int chars_; // Caches the number of characters when computing the hash code.
+ uint32_t seed_;
};
template <typename Char>
class SequentialSymbolKey : public HashTableKey {
public:
- explicit SequentialSymbolKey(Vector<const Char> string)
- : string_(string), hash_field_(0) { }
+ explicit SequentialSymbolKey(Vector<const Char> string, uint32_t seed)
+ : string_(string), hash_field_(0), seed_(seed) { }
uint32_t Hash() {
- StringHasher hasher(string_.length());
+ StringHasher hasher(string_.length(), seed_);
// Very long strings have a trivial hash that doesn't inspect the
// string contents.
@@ -9619,14 +9639,15 @@
Vector<const Char> string_;
uint32_t hash_field_;
+ uint32_t seed_;
};
class AsciiSymbolKey : public SequentialSymbolKey<char> {
public:
- explicit AsciiSymbolKey(Vector<const char> str)
- : SequentialSymbolKey<char>(str) { }
+ AsciiSymbolKey(Vector<const char> str, uint32_t seed)
+ : SequentialSymbolKey<char>(str, seed) { }
bool IsMatch(Object* string) {
return String::cast(string)->IsAsciiEqualTo(string_);
@@ -9643,13 +9664,14 @@
public:
explicit SubStringAsciiSymbolKey(Handle<SeqAsciiString> string,
int from,
- int length)
- : string_(string), from_(from), length_(length) { }
+ int length,
+ uint32_t seed)
+ : string_(string), from_(from), length_(length), seed_(seed) { }
uint32_t Hash() {
ASSERT(length_ >= 0);
ASSERT(from_ + length_ <= string_->length());
- StringHasher hasher(length_);
+ StringHasher hasher(length_, string_->GetHeap()->StringHashSeed());
// Very long strings have a trivial hash that doesn't inspect the
// string contents.
@@ -9701,13 +9723,14 @@
int from_;
int length_;
uint32_t hash_field_;
+ uint32_t seed_;
};
class TwoByteSymbolKey : public SequentialSymbolKey<uc16> {
public:
- explicit TwoByteSymbolKey(Vector<const uc16> str)
- : SequentialSymbolKey<uc16>(str) { }
+ explicit TwoByteSymbolKey(Vector<const uc16> str, uint32_t seed)
+ : SequentialSymbolKey<uc16>(str, seed) { }
bool IsMatch(Object* string) {
return String::cast(string)->IsTwoByteEqualTo(string_);
@@ -10479,10 +10502,12 @@
// algorithm.
class TwoCharHashTableKey : public HashTableKey {
public:
- TwoCharHashTableKey(uint32_t c1, uint32_t c2)
+ TwoCharHashTableKey(uint32_t c1, uint32_t c2, uint32_t seed)
: c1_(c1), c2_(c2) {
// Char 1.
- uint32_t hash = c1 + (c1 << 10);
+ uint32_t hash = seed;
+ hash += c1;
+ hash += hash << 10;
hash ^= hash >> 6;
// Char 2.
hash += c2;
@@ -10492,9 +10517,9 @@
hash += hash << 3;
hash ^= hash >> 11;
hash += hash << 15;
- if (hash == 0) hash = 27;
+ if ((hash & String::kHashBitMask) == 0) hash = 27;
#ifdef DEBUG
- StringHasher hasher(2);
+ StringHasher hasher(2, seed);
hasher.AddCharacter(c1);
hasher.AddCharacter(c2);
// If this assert fails then we failed to reproduce the two-character
@@ -10551,7 +10576,7 @@
bool SymbolTable::LookupTwoCharsSymbolIfExists(uint32_t c1,
uint32_t c2,
String** symbol) {
- TwoCharHashTableKey key(c1, c2);
+ TwoCharHashTableKey key(c1, c2, GetHeap()->StringHashSeed());
int entry = FindEntry(&key);
if (entry == kNotFound) {
return false;
@@ -10564,15 +10589,16 @@
}
-MaybeObject* SymbolTable::LookupSymbol(Vector<const char> str, Object** s) {
- Utf8SymbolKey key(str);
+MaybeObject* SymbolTable::LookupSymbol(Vector<const char> str,
+ Object** s) {
+ Utf8SymbolKey key(str, GetHeap()->StringHashSeed());
return LookupKey(&key, s);
}
MaybeObject* SymbolTable::LookupAsciiSymbol(Vector<const char> str,
Object** s) {
- AsciiSymbolKey key(str);
+ AsciiSymbolKey key(str, GetHeap()->StringHashSeed());
return LookupKey(&key, s);
}
@@ -10581,14 +10607,14 @@
int from,
int length,
Object** s) {
- SubStringAsciiSymbolKey key(str, from, length);
+ SubStringAsciiSymbolKey key(str, from, length, GetHeap()->StringHashSeed());
return LookupKey(&key, s);
}
MaybeObject* SymbolTable::LookupTwoByteSymbol(Vector<const uc16> str,
Object** s) {
- TwoByteSymbolKey key(str);
+ TwoByteSymbolKey key(str, GetHeap()->StringHashSeed());
return LookupKey(&key, s);
}
« src/objects.h ('K') | « src/objects.h ('k') | src/objects-inl.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698