OLD | NEW |
1 // Copyright 2011 the V8 project authors. All rights reserved. | 1 // Copyright 2011 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 2044 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2055 | 2055 |
2056 // Find entry for key otherwise return kNotFound. | 2056 // Find entry for key otherwise return kNotFound. |
2057 template<typename Shape, typename Key> | 2057 template<typename Shape, typename Key> |
2058 int HashTable<Shape, Key>::FindEntry(Isolate* isolate, Key key) { | 2058 int HashTable<Shape, Key>::FindEntry(Isolate* isolate, Key key) { |
2059 uint32_t capacity = Capacity(); | 2059 uint32_t capacity = Capacity(); |
2060 uint32_t entry = FirstProbe(Shape::Hash(key), capacity); | 2060 uint32_t entry = FirstProbe(Shape::Hash(key), capacity); |
2061 uint32_t count = 1; | 2061 uint32_t count = 1; |
2062 // EnsureCapacity will guarantee the hash table is never full. | 2062 // EnsureCapacity will guarantee the hash table is never full. |
2063 while (true) { | 2063 while (true) { |
2064 Object* element = KeyAt(entry); | 2064 Object* element = KeyAt(entry); |
2065 if (element == isolate->heap()->undefined_value()) break; // Empty entry. | 2065 // Empty entry. |
2066 if (element != isolate->heap()->the_hole_value() && | 2066 if (element == isolate->heap()->raw_unchecked_undefined_value()) break; |
| 2067 if (element != isolate->heap()->raw_unchecked_the_hole_value() && |
2067 Shape::IsMatch(key, element)) return entry; | 2068 Shape::IsMatch(key, element)) return entry; |
2068 entry = NextProbe(entry, count++, capacity); | 2069 entry = NextProbe(entry, count++, capacity); |
2069 } | 2070 } |
2070 return kNotFound; | 2071 return kNotFound; |
2071 } | 2072 } |
2072 | 2073 |
2073 | 2074 |
2074 bool NumberDictionary::requires_slow_elements() { | 2075 bool NumberDictionary::requires_slow_elements() { |
2075 Object* max_index_object = get(kMaxNumberKeyIndex); | 2076 Object* max_index_object = get(kMaxNumberKeyIndex); |
2076 if (!max_index_object->IsSmi()) return false; | 2077 if (!max_index_object->IsSmi()) return false; |
(...skipping 2236 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
4313 | 4314 |
4314 uint32_t String::Hash() { | 4315 uint32_t String::Hash() { |
4315 // Fast case: has hash code already been computed? | 4316 // Fast case: has hash code already been computed? |
4316 uint32_t field = hash_field(); | 4317 uint32_t field = hash_field(); |
4317 if (IsHashFieldComputed(field)) return field >> kHashShift; | 4318 if (IsHashFieldComputed(field)) return field >> kHashShift; |
4318 // Slow case: compute hash code and set it. | 4319 // Slow case: compute hash code and set it. |
4319 return ComputeAndSetHash(); | 4320 return ComputeAndSetHash(); |
4320 } | 4321 } |
4321 | 4322 |
4322 | 4323 |
4323 StringHasher::StringHasher(int length) | 4324 StringHasher::StringHasher(int length, uint32_t seed) |
4324 : length_(length), | 4325 : length_(length), |
4325 raw_running_hash_(0), | 4326 raw_running_hash_(seed), |
4326 array_index_(0), | 4327 array_index_(0), |
4327 is_array_index_(0 < length_ && length_ <= String::kMaxArrayIndexSize), | 4328 is_array_index_(0 < length_ && length_ <= String::kMaxArrayIndexSize), |
4328 is_first_char_(true), | 4329 is_first_char_(true), |
4329 is_valid_(true) { } | 4330 is_valid_(true) { |
| 4331 ASSERT(FLAG_randomize_string_hashes == (raw_running_hash_ != 0)); |
| 4332 } |
4330 | 4333 |
4331 | 4334 |
4332 bool StringHasher::has_trivial_hash() { | 4335 bool StringHasher::has_trivial_hash() { |
4333 return length_ > String::kMaxHashCalcLength; | 4336 return length_ > String::kMaxHashCalcLength; |
4334 } | 4337 } |
4335 | 4338 |
4336 | 4339 |
4337 void StringHasher::AddCharacter(uc32 c) { | 4340 void StringHasher::AddCharacter(uc32 c) { |
4338 // Use the Jenkins one-at-a-time hash function to update the hash | 4341 // Use the Jenkins one-at-a-time hash function to update the hash |
4339 // for the given character. | 4342 // for the given character. |
(...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
4379 result ^= (result >> 11); | 4382 result ^= (result >> 11); |
4380 result += (result << 15); | 4383 result += (result << 15); |
4381 if (result == 0) { | 4384 if (result == 0) { |
4382 result = 27; | 4385 result = 27; |
4383 } | 4386 } |
4384 return result; | 4387 return result; |
4385 } | 4388 } |
4386 | 4389 |
4387 | 4390 |
4388 template <typename schar> | 4391 template <typename schar> |
4389 uint32_t HashSequentialString(const schar* chars, int length) { | 4392 uint32_t HashSequentialString(const schar* chars, int length, uint32_t seed) { |
4390 StringHasher hasher(length); | 4393 StringHasher hasher(length, seed); |
4391 if (!hasher.has_trivial_hash()) { | 4394 if (!hasher.has_trivial_hash()) { |
4392 int i; | 4395 int i; |
4393 for (i = 0; hasher.is_array_index() && (i < length); i++) { | 4396 for (i = 0; hasher.is_array_index() && (i < length); i++) { |
4394 hasher.AddCharacter(chars[i]); | 4397 hasher.AddCharacter(chars[i]); |
4395 } | 4398 } |
4396 for (; i < length; i++) { | 4399 for (; i < length; i++) { |
4397 hasher.AddCharacterNoIndex(chars[i]); | 4400 hasher.AddCharacterNoIndex(chars[i]); |
4398 } | 4401 } |
4399 } | 4402 } |
4400 return hasher.GetHashField(); | 4403 return hasher.GetHashField(); |
(...skipping 365 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
4766 #undef WRITE_INT_FIELD | 4769 #undef WRITE_INT_FIELD |
4767 #undef READ_SHORT_FIELD | 4770 #undef READ_SHORT_FIELD |
4768 #undef WRITE_SHORT_FIELD | 4771 #undef WRITE_SHORT_FIELD |
4769 #undef READ_BYTE_FIELD | 4772 #undef READ_BYTE_FIELD |
4770 #undef WRITE_BYTE_FIELD | 4773 #undef WRITE_BYTE_FIELD |
4771 | 4774 |
4772 | 4775 |
4773 } } // namespace v8::internal | 4776 } } // namespace v8::internal |
4774 | 4777 |
4775 #endif // V8_OBJECTS_INL_H_ | 4778 #endif // V8_OBJECTS_INL_H_ |
OLD | NEW |