OLD | NEW |
1 // Copyright 2012 the V8 project authors. All rights reserved. | 1 // Copyright 2012 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 4931 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
4942 // Slow case: compute hash code and set it. | 4942 // Slow case: compute hash code and set it. |
4943 return ComputeAndSetHash(); | 4943 return ComputeAndSetHash(); |
4944 } | 4944 } |
4945 | 4945 |
4946 | 4946 |
4947 StringHasher::StringHasher(int length, uint32_t seed) | 4947 StringHasher::StringHasher(int length, uint32_t seed) |
4948 : length_(length), | 4948 : length_(length), |
4949 raw_running_hash_(seed), | 4949 raw_running_hash_(seed), |
4950 array_index_(0), | 4950 array_index_(0), |
4951 is_array_index_(0 < length_ && length_ <= String::kMaxArrayIndexSize), | 4951 is_array_index_(0 < length_ && length_ <= String::kMaxArrayIndexSize), |
4952 is_first_char_(true), | 4952 is_first_char_(true) { |
4953 is_valid_(true) { | |
4954 ASSERT(FLAG_randomize_hashes || raw_running_hash_ == 0); | 4953 ASSERT(FLAG_randomize_hashes || raw_running_hash_ == 0); |
4955 } | 4954 } |
4956 | 4955 |
4957 | 4956 |
4958 bool StringHasher::has_trivial_hash() { | 4957 bool StringHasher::has_trivial_hash() { |
4959 return length_ > String::kMaxHashCalcLength; | 4958 return length_ > String::kMaxHashCalcLength; |
4960 } | 4959 } |
4961 | 4960 |
4962 | 4961 |
| 4962 uint32_t StringHasher::AddCharacterCore(uint32_t running_hash, uint32_t c) { |
| 4963 running_hash += c; |
| 4964 running_hash += (running_hash << 10); |
| 4965 running_hash ^= (running_hash >> 6); |
| 4966 return running_hash; |
| 4967 } |
| 4968 |
| 4969 |
| 4970 uint32_t StringHasher::GetHashCore(uint32_t running_hash) { |
| 4971 running_hash += (running_hash << 3); |
| 4972 running_hash ^= (running_hash >> 11); |
| 4973 running_hash += (running_hash << 15); |
| 4974 if ((running_hash & String::kHashBitMask) == 0) { |
| 4975 return 27; |
| 4976 } |
| 4977 return running_hash; |
| 4978 } |
| 4979 |
| 4980 |
4963 void StringHasher::AddCharacter(uint32_t c) { | 4981 void StringHasher::AddCharacter(uint32_t c) { |
4964 if (c > unibrow::Utf16::kMaxNonSurrogateCharCode) { | 4982 if (c > unibrow::Utf16::kMaxNonSurrogateCharCode) { |
4965 AddSurrogatePair(c); // Not inlined. | 4983 AddSurrogatePair(c); // Not inlined. |
4966 return; | 4984 return; |
4967 } | 4985 } |
4968 // Use the Jenkins one-at-a-time hash function to update the hash | 4986 // Use the Jenkins one-at-a-time hash function to update the hash |
4969 // for the given character. | 4987 // for the given character. |
4970 raw_running_hash_ += c; | 4988 raw_running_hash_ = AddCharacterCore(raw_running_hash_, c); |
4971 raw_running_hash_ += (raw_running_hash_ << 10); | |
4972 raw_running_hash_ ^= (raw_running_hash_ >> 6); | |
4973 // Incremental array index computation. | 4989 // Incremental array index computation. |
4974 if (is_array_index_) { | 4990 if (is_array_index_) { |
4975 if (c < '0' || c > '9') { | 4991 if (c < '0' || c > '9') { |
4976 is_array_index_ = false; | 4992 is_array_index_ = false; |
4977 } else { | 4993 } else { |
4978 int d = c - '0'; | 4994 int d = c - '0'; |
4979 if (is_first_char_) { | 4995 if (is_first_char_) { |
4980 is_first_char_ = false; | 4996 is_first_char_ = false; |
4981 if (c == '0' && length_ > 1) { | 4997 if (c == '0' && length_ > 1) { |
4982 is_array_index_ = false; | 4998 is_array_index_ = false; |
4983 return; | 4999 return; |
4984 } | 5000 } |
4985 } | 5001 } |
4986 if (array_index_ > 429496729U - ((d + 2) >> 3)) { | 5002 if (array_index_ > 429496729U - ((d + 2) >> 3)) { |
4987 is_array_index_ = false; | 5003 is_array_index_ = false; |
4988 } else { | 5004 } else { |
4989 array_index_ = array_index_ * 10 + d; | 5005 array_index_ = array_index_ * 10 + d; |
4990 } | 5006 } |
4991 } | 5007 } |
4992 } | 5008 } |
4993 } | 5009 } |
4994 | 5010 |
4995 | 5011 |
4996 void StringHasher::AddCharacterNoIndex(uint32_t c) { | 5012 void StringHasher::AddCharacterNoIndex(uint32_t c) { |
4997 ASSERT(!is_array_index()); | 5013 ASSERT(!is_array_index()); |
4998 if (c > unibrow::Utf16::kMaxNonSurrogateCharCode) { | 5014 if (c > unibrow::Utf16::kMaxNonSurrogateCharCode) { |
4999 AddSurrogatePairNoIndex(c); // Not inlined. | 5015 AddSurrogatePairNoIndex(c); // Not inlined. |
5000 return; | 5016 return; |
5001 } | 5017 } |
5002 raw_running_hash_ += c; | 5018 raw_running_hash_ = AddCharacterCore(raw_running_hash_, c); |
5003 raw_running_hash_ += (raw_running_hash_ << 10); | |
5004 raw_running_hash_ ^= (raw_running_hash_ >> 6); | |
5005 } | 5019 } |
5006 | 5020 |
5007 | 5021 |
5008 uint32_t StringHasher::GetHash() { | 5022 uint32_t StringHasher::GetHash() { |
5009 // Get the calculated raw hash value and do some more bit ops to distribute | 5023 // Get the calculated raw hash value and do some more bit ops to distribute |
5010 // the hash further. Ensure that we never return zero as the hash value. | 5024 // the hash further. Ensure that we never return zero as the hash value. |
5011 uint32_t result = raw_running_hash_; | 5025 return GetHashCore(raw_running_hash_); |
5012 result += (result << 3); | |
5013 result ^= (result >> 11); | |
5014 result += (result << 15); | |
5015 if ((result & String::kHashBitMask) == 0) { | |
5016 result = 27; | |
5017 } | |
5018 return result; | |
5019 } | 5026 } |
5020 | 5027 |
5021 | 5028 |
5022 template <typename schar> | 5029 template <typename schar> |
5023 uint32_t HashSequentialString(const schar* chars, int length, uint32_t seed) { | 5030 uint32_t HashSequentialString(const schar* chars, int length, uint32_t seed) { |
5024 StringHasher hasher(length, seed); | 5031 StringHasher hasher(length, seed); |
5025 if (!hasher.has_trivial_hash()) { | 5032 if (!hasher.has_trivial_hash()) { |
5026 int i; | 5033 int i; |
5027 for (i = 0; hasher.is_array_index() && (i < length); i++) { | 5034 for (i = 0; hasher.is_array_index() && (i < length); i++) { |
5028 hasher.AddCharacter(chars[i]); | 5035 hasher.AddCharacter(chars[i]); |
(...skipping 521 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
5550 #undef WRITE_UINT32_FIELD | 5557 #undef WRITE_UINT32_FIELD |
5551 #undef READ_SHORT_FIELD | 5558 #undef READ_SHORT_FIELD |
5552 #undef WRITE_SHORT_FIELD | 5559 #undef WRITE_SHORT_FIELD |
5553 #undef READ_BYTE_FIELD | 5560 #undef READ_BYTE_FIELD |
5554 #undef WRITE_BYTE_FIELD | 5561 #undef WRITE_BYTE_FIELD |
5555 | 5562 |
5556 | 5563 |
5557 } } // namespace v8::internal | 5564 } } // namespace v8::internal |
5558 | 5565 |
5559 #endif // V8_OBJECTS_INL_H_ | 5566 #endif // V8_OBJECTS_INL_H_ |
OLD | NEW |