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 2566 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2577 case kSlicedStringTag | kTwoByteStringTag: { | 2577 case kSlicedStringTag | kTwoByteStringTag: { |
2578 SlicedString* slicedString = SlicedString::cast(string); | 2578 SlicedString* slicedString = SlicedString::cast(string); |
2579 slice_offset += slicedString->offset(); | 2579 slice_offset += slicedString->offset(); |
2580 string = slicedString->parent(); | 2580 string = slicedString->parent(); |
2581 type = string->map()->instance_type(); | 2581 type = string->map()->instance_type(); |
2582 continue; | 2582 continue; |
2583 } | 2583 } |
2584 | 2584 |
2585 case kConsStringTag | kOneByteStringTag: | 2585 case kConsStringTag | kOneByteStringTag: |
2586 case kConsStringTag | kTwoByteStringTag: | 2586 case kConsStringTag | kTwoByteStringTag: |
2587 string = cons_op.Operate(ConsString::cast(string), &offset, &type, | 2587 string = cons_op.Operate(string, &offset, &type, &length); |
2588 &length); | |
2589 if (string == NULL) return; | 2588 if (string == NULL) return; |
2590 slice_offset = offset; | 2589 slice_offset = offset; |
2591 ASSERT(length == static_cast<unsigned>(string->length())); | 2590 ASSERT(length == static_cast<unsigned>(string->length())); |
2592 continue; | 2591 continue; |
2593 | 2592 |
2594 default: | 2593 default: |
2595 UNREACHABLE(); | 2594 UNREACHABLE(); |
2596 return; | 2595 return; |
2597 } | 2596 } |
2598 } | 2597 } |
(...skipping 171 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2770 return GetChars()[index]; | 2769 return GetChars()[index]; |
2771 } | 2770 } |
2772 | 2771 |
2773 | 2772 |
2774 const uint16_t* ExternalTwoByteString::ExternalTwoByteStringGetData( | 2773 const uint16_t* ExternalTwoByteString::ExternalTwoByteStringGetData( |
2775 unsigned start) { | 2774 unsigned start) { |
2776 return GetChars() + start; | 2775 return GetChars() + start; |
2777 } | 2776 } |
2778 | 2777 |
2779 | 2778 |
| 2779 String* ConsStringNullOp::Operate(String*, unsigned*, int32_t*, unsigned*) { |
| 2780 return NULL; |
| 2781 } |
| 2782 |
| 2783 |
2780 unsigned ConsStringIteratorOp::OffsetForDepth(unsigned depth) { | 2784 unsigned ConsStringIteratorOp::OffsetForDepth(unsigned depth) { |
2781 return depth & kDepthMask; | 2785 return depth & kDepthMask; |
2782 } | 2786 } |
2783 | 2787 |
2784 | 2788 |
2785 void ConsStringIteratorOp::PushLeft(ConsString* string) { | 2789 void ConsStringIteratorOp::PushLeft(ConsString* string) { |
2786 frames_[depth_++ & kDepthMask] = string; | 2790 frames_[depth_++ & kDepthMask] = string; |
2787 } | 2791 } |
2788 | 2792 |
2789 | 2793 |
2790 void ConsStringIteratorOp::PushRight(ConsString* string) { | 2794 void ConsStringIteratorOp::PushRight(ConsString* string) { |
2791 // Inplace update. | 2795 // Inplace update. |
2792 frames_[(depth_-1) & kDepthMask] = string; | 2796 frames_[(depth_-1) & kDepthMask] = string; |
2793 } | 2797 } |
2794 | 2798 |
2795 | 2799 |
2796 void ConsStringIteratorOp::AdjustMaximumDepth() { | 2800 void ConsStringIteratorOp::AdjustMaximumDepth() { |
2797 if (depth_ > maximum_depth_) maximum_depth_ = depth_; | 2801 if (depth_ > maximum_depth_) maximum_depth_ = depth_; |
2798 } | 2802 } |
2799 | 2803 |
2800 | 2804 |
2801 void ConsStringIteratorOp::Pop() { | 2805 void ConsStringIteratorOp::Pop() { |
2802 ASSERT(depth_ > 0); | 2806 ASSERT(depth_ > 0); |
2803 ASSERT(depth_ <= maximum_depth_); | 2807 ASSERT(depth_ <= maximum_depth_); |
2804 depth_--; | 2808 depth_--; |
2805 } | 2809 } |
2806 | 2810 |
2807 | 2811 |
2808 void ConsStringIteratorOp::Reset() { | |
2809 depth_ = 0; | |
2810 maximum_depth_ = 0; | |
2811 } | |
2812 | |
2813 | |
2814 bool ConsStringIteratorOp::HasMore() { | 2812 bool ConsStringIteratorOp::HasMore() { |
2815 return depth_ != 0; | 2813 return depth_ != 0; |
2816 } | 2814 } |
2817 | 2815 |
2818 | 2816 |
2819 bool ConsStringIteratorOp::ContinueOperation(ContinueResponse* response) { | 2817 void ConsStringIteratorOp::Reset() { |
2820 bool blew_stack; | 2818 depth_ = 0; |
2821 int32_t type; | |
2822 unsigned length; | |
2823 String* string = NextLeaf(&blew_stack, &type, &length); | |
2824 // String found. | |
2825 if (string != NULL) { | |
2826 consumed_ += length; | |
2827 response->string_ = string; | |
2828 response->offset_ = 0; | |
2829 response->length_ = length; | |
2830 response->type_ = type; | |
2831 return true; | |
2832 } | |
2833 // Traversal complete. | |
2834 if (!blew_stack) return false; | |
2835 // Restart search. | |
2836 Reset(); | |
2837 // TODO(dcarney) This is unnecessary. | |
2838 // After a reset, we don't need a String::Visit | |
2839 response->string_ = root_; | |
2840 response->offset_ = consumed_; | |
2841 response->length_ = root_length_; | |
2842 response->type_ = root_type_; | |
2843 return true; | |
2844 } | 2819 } |
2845 | 2820 |
2846 | 2821 |
| 2822 String* ConsStringIteratorOp::ContinueOperation(int32_t* type_out, |
| 2823 unsigned* length_out) { |
| 2824 bool blew_stack; |
| 2825 String* string = NextLeaf(&blew_stack, type_out, length_out); |
| 2826 // String found. |
| 2827 if (string != NULL) { |
| 2828 // Verify output. |
| 2829 ASSERT(*length_out == static_cast<unsigned>(string->length())); |
| 2830 ASSERT(*type_out == string->map()->instance_type()); |
| 2831 return string; |
| 2832 } |
| 2833 // Traversal complete. |
| 2834 if (!blew_stack) return NULL; |
| 2835 // Restart search from root. |
| 2836 unsigned offset_out; |
| 2837 string = Search(&offset_out, type_out, length_out); |
| 2838 // Verify output. |
| 2839 ASSERT(string == NULL || offset_out == 0); |
| 2840 ASSERT(string == NULL || |
| 2841 *length_out == static_cast<unsigned>(string->length())); |
| 2842 ASSERT(string == NULL || *type_out == string->map()->instance_type()); |
| 2843 return string; |
| 2844 } |
| 2845 |
| 2846 |
2847 uint16_t StringCharacterStream::GetNext() { | 2847 uint16_t StringCharacterStream::GetNext() { |
2848 ASSERT((buffer8_ == NULL && end_ == NULL) || buffer8_ < end_); | 2848 ASSERT((buffer8_ == NULL && end_ == NULL) || buffer8_ < end_); |
2849 return is_one_byte_ ? *buffer8_++ : *buffer16_++; | 2849 return is_one_byte_ ? *buffer8_++ : *buffer16_++; |
2850 } | 2850 } |
2851 | 2851 |
2852 | 2852 |
2853 StringCharacterStream::StringCharacterStream( | 2853 StringCharacterStream::StringCharacterStream( |
2854 String* string, unsigned offset, ConsStringIteratorOp* op) | 2854 String* string, unsigned offset, ConsStringIteratorOp* op) |
2855 : is_one_byte_(false), | 2855 : is_one_byte_(false), |
2856 buffer8_(NULL), | 2856 buffer8_(NULL), |
2857 end_(NULL), | 2857 end_(NULL), |
2858 op_(op) { | 2858 op_(op) { |
2859 op->Reset(); | 2859 op->Reset(); |
2860 String::Visit(string, | 2860 int32_t type = string->map()->instance_type(); |
2861 offset, *this, *op, string->map()->instance_type(), string->length()); | 2861 unsigned length = string->length(); |
| 2862 String::Visit(string, offset, *this, *op, type, length); |
2862 } | 2863 } |
2863 | 2864 |
2864 | 2865 |
2865 bool StringCharacterStream::HasMore() { | 2866 bool StringCharacterStream::HasMore() { |
2866 if (buffer8_ != end_) return true; | 2867 if (buffer8_ != end_) return true; |
2867 if (!op_->HasMore()) return false; | 2868 if (!op_->HasMore()) return false; |
2868 ConsStringIteratorOp::ContinueResponse response; | 2869 unsigned length; |
2869 if (!op_->ContinueOperation(&response)) return false; | 2870 int32_t type; |
2870 String::Visit(response.string_, | 2871 String* string = op_->ContinueOperation(&type, &length); |
2871 response.offset_, *this, *op_, response.type_, response.length_); | 2872 if (string == NULL) return false; |
| 2873 ASSERT(!string->IsConsString()); |
| 2874 ASSERT(string->length() != 0); |
| 2875 ConsStringNullOp null_op; |
| 2876 String::Visit(string, 0, *this, null_op, type, length); |
| 2877 ASSERT(buffer8_ != end_); |
2872 return true; | 2878 return true; |
2873 } | 2879 } |
2874 | 2880 |
2875 | 2881 |
2876 void StringCharacterStream::VisitOneByteString( | 2882 void StringCharacterStream::VisitOneByteString( |
2877 const uint8_t* chars, unsigned length) { | 2883 const uint8_t* chars, unsigned length) { |
2878 is_one_byte_ = true; | 2884 is_one_byte_ = true; |
2879 buffer8_ = chars; | 2885 buffer8_ = chars; |
2880 end_ = chars + length; | 2886 end_ = chars + length; |
2881 } | 2887 } |
(...skipping 2234 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
5116 is_first_char_(true) { | 5122 is_first_char_(true) { |
5117 ASSERT(FLAG_randomize_hashes || raw_running_hash_ == 0); | 5123 ASSERT(FLAG_randomize_hashes || raw_running_hash_ == 0); |
5118 } | 5124 } |
5119 | 5125 |
5120 | 5126 |
5121 bool StringHasher::has_trivial_hash() { | 5127 bool StringHasher::has_trivial_hash() { |
5122 return length_ > String::kMaxHashCalcLength; | 5128 return length_ > String::kMaxHashCalcLength; |
5123 } | 5129 } |
5124 | 5130 |
5125 | 5131 |
5126 uint32_t StringHasher::AddCharacterCore(uint32_t running_hash, uint32_t c) { | 5132 uint32_t StringHasher::AddCharacterCore(uint32_t running_hash, uint16_t c) { |
5127 running_hash += c; | 5133 running_hash += c; |
5128 running_hash += (running_hash << 10); | 5134 running_hash += (running_hash << 10); |
5129 running_hash ^= (running_hash >> 6); | 5135 running_hash ^= (running_hash >> 6); |
5130 return running_hash; | 5136 return running_hash; |
5131 } | 5137 } |
5132 | 5138 |
5133 | 5139 |
5134 uint32_t StringHasher::GetHashCore(uint32_t running_hash) { | 5140 uint32_t StringHasher::GetHashCore(uint32_t running_hash) { |
5135 running_hash += (running_hash << 3); | 5141 running_hash += (running_hash << 3); |
5136 running_hash ^= (running_hash >> 11); | 5142 running_hash ^= (running_hash >> 11); |
5137 running_hash += (running_hash << 15); | 5143 running_hash += (running_hash << 15); |
5138 if ((running_hash & String::kHashBitMask) == 0) { | 5144 if ((running_hash & String::kHashBitMask) == 0) { |
5139 return kZeroHash; | 5145 return kZeroHash; |
5140 } | 5146 } |
5141 return running_hash; | 5147 return running_hash; |
5142 } | 5148 } |
5143 | 5149 |
5144 | 5150 |
5145 void StringHasher::AddCharacter(uint32_t c) { | 5151 void StringHasher::AddCharacter(uint16_t c) { |
5146 if (c > unibrow::Utf16::kMaxNonSurrogateCharCode) { | |
5147 AddSurrogatePair(c); // Not inlined. | |
5148 return; | |
5149 } | |
5150 // Use the Jenkins one-at-a-time hash function to update the hash | 5152 // Use the Jenkins one-at-a-time hash function to update the hash |
5151 // for the given character. | 5153 // for the given character. |
5152 raw_running_hash_ = AddCharacterCore(raw_running_hash_, c); | 5154 raw_running_hash_ = AddCharacterCore(raw_running_hash_, c); |
5153 // Incremental array index computation. | 5155 } |
| 5156 |
| 5157 |
| 5158 bool StringHasher::UpdateIndex(uint16_t c) { |
| 5159 ASSERT(is_array_index_); |
| 5160 if (c < '0' || c > '9') { |
| 5161 is_array_index_ = false; |
| 5162 return false; |
| 5163 } |
| 5164 int d = c - '0'; |
| 5165 if (is_first_char_) { |
| 5166 is_first_char_ = false; |
| 5167 if (c == '0' && length_ > 1) { |
| 5168 is_array_index_ = false; |
| 5169 return false; |
| 5170 } |
| 5171 } |
| 5172 if (array_index_ > 429496729U - ((d + 2) >> 3)) { |
| 5173 is_array_index_ = false; |
| 5174 return false; |
| 5175 } |
| 5176 array_index_ = array_index_ * 10 + d; |
| 5177 return true; |
| 5178 } |
| 5179 |
| 5180 |
| 5181 template<typename Char> |
| 5182 inline void StringHasher::AddCharacters(const Char* chars, int length) { |
| 5183 ASSERT(sizeof(Char) == 1 || sizeof(Char) == 2); |
| 5184 int i = 0; |
5154 if (is_array_index_) { | 5185 if (is_array_index_) { |
5155 if (c < '0' || c > '9') { | 5186 for (; i < length; i++) { |
5156 is_array_index_ = false; | 5187 AddCharacter(chars[i]); |
5157 } else { | 5188 if (!UpdateIndex(chars[i])) { |
5158 int d = c - '0'; | 5189 i++; |
5159 if (is_first_char_) { | 5190 break; |
5160 is_first_char_ = false; | |
5161 if (c == '0' && length_ > 1) { | |
5162 is_array_index_ = false; | |
5163 return; | |
5164 } | |
5165 } | |
5166 if (array_index_ > 429496729U - ((d + 2) >> 3)) { | |
5167 is_array_index_ = false; | |
5168 } else { | |
5169 array_index_ = array_index_ * 10 + d; | |
5170 } | 5191 } |
5171 } | 5192 } |
5172 } | 5193 } |
| 5194 for (; i < length; i++) { |
| 5195 ASSERT(!is_array_index_); |
| 5196 AddCharacter(chars[i]); |
| 5197 } |
5173 } | 5198 } |
5174 | 5199 |
5175 | 5200 |
5176 void StringHasher::AddCharacterNoIndex(uint32_t c) { | |
5177 ASSERT(!is_array_index()); | |
5178 if (c > unibrow::Utf16::kMaxNonSurrogateCharCode) { | |
5179 AddSurrogatePairNoIndex(c); // Not inlined. | |
5180 return; | |
5181 } | |
5182 raw_running_hash_ = AddCharacterCore(raw_running_hash_, c); | |
5183 } | |
5184 | |
5185 | |
5186 uint32_t StringHasher::GetHash() { | |
5187 // Get the calculated raw hash value and do some more bit ops to distribute | |
5188 // the hash further. Ensure that we never return zero as the hash value. | |
5189 return GetHashCore(raw_running_hash_); | |
5190 } | |
5191 | |
5192 | |
5193 template <typename schar> | 5201 template <typename schar> |
5194 uint32_t HashSequentialString(const schar* chars, int length, uint32_t seed) { | 5202 uint32_t StringHasher::HashSequentialString(const schar* chars, |
| 5203 int length, |
| 5204 uint32_t seed) { |
5195 StringHasher hasher(length, seed); | 5205 StringHasher hasher(length, seed); |
5196 if (!hasher.has_trivial_hash()) { | 5206 if (!hasher.has_trivial_hash()) hasher.AddCharacters(chars, length); |
5197 int i; | |
5198 for (i = 0; hasher.is_array_index() && (i < length); i++) { | |
5199 hasher.AddCharacter(chars[i]); | |
5200 } | |
5201 for (; i < length; i++) { | |
5202 hasher.AddCharacterNoIndex(chars[i]); | |
5203 } | |
5204 } | |
5205 return hasher.GetHashField(); | 5207 return hasher.GetHashField(); |
5206 } | 5208 } |
5207 | 5209 |
5208 | 5210 |
5209 bool String::AsArrayIndex(uint32_t* index) { | 5211 bool String::AsArrayIndex(uint32_t* index) { |
5210 uint32_t field = hash_field(); | 5212 uint32_t field = hash_field(); |
5211 if (IsHashFieldComputed(field) && (field & kIsNotArrayIndexMask)) { | 5213 if (IsHashFieldComputed(field) && (field & kIsNotArrayIndexMask)) { |
5212 return false; | 5214 return false; |
5213 } | 5215 } |
5214 return SlowAsArrayIndex(index); | 5216 return SlowAsArrayIndex(index); |
(...skipping 539 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
5754 #undef WRITE_UINT32_FIELD | 5756 #undef WRITE_UINT32_FIELD |
5755 #undef READ_SHORT_FIELD | 5757 #undef READ_SHORT_FIELD |
5756 #undef WRITE_SHORT_FIELD | 5758 #undef WRITE_SHORT_FIELD |
5757 #undef READ_BYTE_FIELD | 5759 #undef READ_BYTE_FIELD |
5758 #undef WRITE_BYTE_FIELD | 5760 #undef WRITE_BYTE_FIELD |
5759 | 5761 |
5760 | 5762 |
5761 } } // namespace v8::internal | 5763 } } // namespace v8::internal |
5762 | 5764 |
5763 #endif // V8_OBJECTS_INL_H_ | 5765 #endif // V8_OBJECTS_INL_H_ |
OLD | NEW |