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 3024 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3035 int length, | 3035 int length, |
3036 Object** s); | 3036 Object** s); |
3037 MUST_USE_RESULT MaybeObject* LookupTwoByteSymbol(Vector<const uc16> str, | 3037 MUST_USE_RESULT MaybeObject* LookupTwoByteSymbol(Vector<const uc16> str, |
3038 Object** s); | 3038 Object** s); |
3039 MUST_USE_RESULT MaybeObject* LookupString(String* key, Object** s); | 3039 MUST_USE_RESULT MaybeObject* LookupString(String* key, Object** s); |
3040 | 3040 |
3041 // Looks up a symbol that is equal to the given string and returns | 3041 // Looks up a symbol that is equal to the given string and returns |
3042 // true if it is found, assigning the symbol to the given output | 3042 // true if it is found, assigning the symbol to the given output |
3043 // parameter. | 3043 // parameter. |
3044 bool LookupSymbolIfExists(String* str, String** symbol); | 3044 bool LookupSymbolIfExists(String* str, String** symbol); |
3045 bool LookupTwoCharsSymbolIfExists(uint32_t c1, uint32_t c2, String** symbol); | 3045 bool LookupTwoCharsSymbolIfExists(uint16_t c1, uint16_t c2, String** symbol); |
3046 | 3046 |
3047 // Casting. | 3047 // Casting. |
3048 static inline SymbolTable* cast(Object* obj); | 3048 static inline SymbolTable* cast(Object* obj); |
3049 | 3049 |
3050 private: | 3050 private: |
3051 MUST_USE_RESULT MaybeObject* LookupKey(HashTableKey* key, Object** s); | 3051 MUST_USE_RESULT MaybeObject* LookupKey(HashTableKey* key, Object** s); |
3052 | 3052 |
3053 template <bool seq_ascii> friend class JsonParser; | 3053 template <bool seq_ascii> friend class JsonParser; |
3054 | 3054 |
3055 DISALLOW_IMPLICIT_CONSTRUCTORS(SymbolTable); | 3055 DISALLOW_IMPLICIT_CONSTRUCTORS(SymbolTable); |
(...skipping 3844 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
6900 | 6900 |
6901 | 6901 |
6902 enum AllowNullsFlag {ALLOW_NULLS, DISALLOW_NULLS}; | 6902 enum AllowNullsFlag {ALLOW_NULLS, DISALLOW_NULLS}; |
6903 enum RobustnessFlag {ROBUST_STRING_TRAVERSAL, FAST_STRING_TRAVERSAL}; | 6903 enum RobustnessFlag {ROBUST_STRING_TRAVERSAL, FAST_STRING_TRAVERSAL}; |
6904 | 6904 |
6905 | 6905 |
6906 class StringHasher { | 6906 class StringHasher { |
6907 public: | 6907 public: |
6908 explicit inline StringHasher(int length, uint32_t seed); | 6908 explicit inline StringHasher(int length, uint32_t seed); |
6909 | 6909 |
6910 // Returns true if the hash of this string can be computed without | 6910 template <typename schar> |
6911 // looking at the contents. | 6911 static inline uint32_t HashSequentialString(const schar* chars, |
6912 inline bool has_trivial_hash(); | 6912 int length, |
| 6913 uint32_t seed); |
6913 | 6914 |
6914 // Add a character to the hash and update the array index calculation. | 6915 static uint32_t ComputeHashField(unibrow::CharacterStream* buffer, |
6915 inline void AddCharacter(uint32_t c); | 6916 int length, |
6916 | 6917 uint32_t seed); |
6917 // Adds a character to the hash but does not update the array index | |
6918 // calculation. This can only be called when it has been verified | |
6919 // that the input is not an array index. | |
6920 inline void AddCharacterNoIndex(uint32_t c); | |
6921 | |
6922 // Add a character above 0xffff as a surrogate pair. These can get into | |
6923 // the hasher through the routines that take a UTF-8 string and make a symbol. | |
6924 void AddSurrogatePair(uc32 c); | |
6925 void AddSurrogatePairNoIndex(uc32 c); | |
6926 | |
6927 // Returns the value to store in the hash field of a string with | |
6928 // the given length and contents. | |
6929 uint32_t GetHashField(); | |
6930 | |
6931 // Returns true if the characters seen so far make up a legal array | |
6932 // index. | |
6933 bool is_array_index() { return is_array_index_; } | |
6934 | 6918 |
6935 // Calculated hash value for a string consisting of 1 to | 6919 // Calculated hash value for a string consisting of 1 to |
6936 // String::kMaxArrayIndexSize digits with no leading zeros (except "0"). | 6920 // String::kMaxArrayIndexSize digits with no leading zeros (except "0"). |
6937 // value is represented decimal value. | 6921 // value is represented decimal value. |
6938 static uint32_t MakeArrayIndexHash(uint32_t value, int length); | 6922 static uint32_t MakeArrayIndexHash(uint32_t value, int length); |
6939 | 6923 |
6940 // No string is allowed to have a hash of zero. That value is reserved | 6924 // No string is allowed to have a hash of zero. That value is reserved |
6941 // for internal properties. If the hash calculation yields zero then we | 6925 // for internal properties. If the hash calculation yields zero then we |
6942 // use 27 instead. | 6926 // use 27 instead. |
6943 static const int kZeroHash = 27; | 6927 static const int kZeroHash = 27; |
6944 | 6928 |
| 6929 // Reusable parts of the hashing algorithm. |
| 6930 INLINE(static uint32_t AddCharacterCore(uint32_t running_hash, uint16_t c)); |
| 6931 INLINE(static uint32_t GetHashCore(uint32_t running_hash)); |
| 6932 |
| 6933 protected: |
| 6934 // Returns the value to store in the hash field of a string with |
| 6935 // the given length and contents. |
| 6936 uint32_t GetHashField(); |
| 6937 // Returns true if the hash of this string can be computed without |
| 6938 // looking at the contents. |
| 6939 inline bool has_trivial_hash(); |
| 6940 // Adds a block of characters to the hash. |
| 6941 template<typename Char> |
| 6942 inline void AddCharacters(const Char* chars, int len); |
| 6943 |
6945 private: | 6944 private: |
6946 uint32_t array_index() { | 6945 // Add a character to the hash. |
6947 ASSERT(is_array_index()); | 6946 inline void AddCharacter(uint16_t c); |
6948 return array_index_; | 6947 // Update index. Returns true if string is still an index. |
6949 } | 6948 inline bool UpdateIndex(uint16_t c); |
6950 | |
6951 inline uint32_t GetHash(); | |
6952 | |
6953 // Reusable parts of the hashing algorithm. | |
6954 INLINE(static uint32_t AddCharacterCore(uint32_t running_hash, uint32_t c)); | |
6955 INLINE(static uint32_t GetHashCore(uint32_t running_hash)); | |
6956 | 6949 |
6957 int length_; | 6950 int length_; |
6958 uint32_t raw_running_hash_; | 6951 uint32_t raw_running_hash_; |
6959 uint32_t array_index_; | 6952 uint32_t array_index_; |
6960 bool is_array_index_; | 6953 bool is_array_index_; |
6961 bool is_first_char_; | 6954 bool is_first_char_; |
6962 friend class TwoCharHashTableKey; | 6955 DISALLOW_COPY_AND_ASSIGN(StringHasher); |
6963 | |
6964 template <bool seq_ascii> friend class JsonParser; | |
6965 }; | 6956 }; |
6966 | 6957 |
6967 | 6958 |
6968 class IncrementalAsciiStringHasher { | |
6969 public: | |
6970 explicit inline IncrementalAsciiStringHasher(uint32_t seed, char first_char); | |
6971 inline void AddCharacter(uc32 c); | |
6972 inline uint32_t GetHash(); | |
6973 | |
6974 private: | |
6975 int length_; | |
6976 uint32_t raw_running_hash_; | |
6977 uint32_t array_index_; | |
6978 bool is_array_index_; | |
6979 char first_char_; | |
6980 }; | |
6981 | |
6982 | |
6983 // Calculates string hash. | |
6984 template <typename schar> | |
6985 inline uint32_t HashSequentialString(const schar* chars, | |
6986 int length, | |
6987 uint32_t seed); | |
6988 | |
6989 | |
6990 // The characteristics of a string are stored in its map. Retrieving these | 6959 // The characteristics of a string are stored in its map. Retrieving these |
6991 // few bits of information is moderately expensive, involving two memory | 6960 // few bits of information is moderately expensive, involving two memory |
6992 // loads where the second is dependent on the first. To improve efficiency | 6961 // loads where the second is dependent on the first. To improve efficiency |
6993 // the shape of the string is given its own class so that it can be retrieved | 6962 // the shape of the string is given its own class so that it can be retrieved |
6994 // once and used for several string operations. A StringShape is small enough | 6963 // once and used for several string operations. A StringShape is small enough |
6995 // to be passed by value and is immutable, but be aware that flattening a | 6964 // to be passed by value and is immutable, but be aware that flattening a |
6996 // string can potentially alter its shape. Also be aware that a GC caused by | 6965 // string can potentially alter its shape. Also be aware that a GC caused by |
6997 // something else can alter the shape of a string due to ConsString | 6966 // something else can alter the shape of a string due to ConsString |
6998 // shortcutting. Keeping these restrictions in mind has proven to be error- | 6967 // shortcutting. Keeping these restrictions in mind has proven to be error- |
6999 // prone and so we no longer put StringShapes in variables unless there is a | 6968 // prone and so we no longer put StringShapes in variables unless there is a |
(...skipping 198 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
7198 // do any heap allocations. This is useful when printing stack traces. | 7167 // do any heap allocations. This is useful when printing stack traces. |
7199 SmartArrayPointer<uc16> ToWideCString( | 7168 SmartArrayPointer<uc16> ToWideCString( |
7200 RobustnessFlag robustness_flag = FAST_STRING_TRAVERSAL); | 7169 RobustnessFlag robustness_flag = FAST_STRING_TRAVERSAL); |
7201 | 7170 |
7202 // Tells whether the hash code has been computed. | 7171 // Tells whether the hash code has been computed. |
7203 inline bool HasHashCode(); | 7172 inline bool HasHashCode(); |
7204 | 7173 |
7205 // Returns a hash value used for the property table | 7174 // Returns a hash value used for the property table |
7206 inline uint32_t Hash(); | 7175 inline uint32_t Hash(); |
7207 | 7176 |
7208 static uint32_t ComputeHashField(unibrow::CharacterStream* buffer, | |
7209 int length, | |
7210 uint32_t seed); | |
7211 | |
7212 static bool ComputeArrayIndex(unibrow::CharacterStream* buffer, | 7177 static bool ComputeArrayIndex(unibrow::CharacterStream* buffer, |
7213 uint32_t* index, | 7178 uint32_t* index, |
7214 int length); | 7179 int length); |
7215 | 7180 |
7216 // Externalization. | 7181 // Externalization. |
7217 bool MakeExternal(v8::String::ExternalStringResource* resource); | 7182 bool MakeExternal(v8::String::ExternalStringResource* resource); |
7218 bool MakeExternal(v8::String::ExternalAsciiStringResource* resource); | 7183 bool MakeExternal(v8::String::ExternalAsciiStringResource* resource); |
7219 | 7184 |
7220 // Conversion. | 7185 // Conversion. |
7221 inline bool AsArrayIndex(uint32_t* index); | 7186 inline bool AsArrayIndex(uint32_t* index); |
(...skipping 619 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
7841 // not always desirable, however (esp. in debugging situations). | 7806 // not always desirable, however (esp. in debugging situations). |
7842 class StringInputBuffer: public unibrow::InputBuffer<String, String*, 1024> { | 7807 class StringInputBuffer: public unibrow::InputBuffer<String, String*, 1024> { |
7843 public: | 7808 public: |
7844 virtual void Seek(unsigned pos); | 7809 virtual void Seek(unsigned pos); |
7845 inline StringInputBuffer(): unibrow::InputBuffer<String, String*, 1024>() {} | 7810 inline StringInputBuffer(): unibrow::InputBuffer<String, String*, 1024>() {} |
7846 explicit inline StringInputBuffer(String* backing): | 7811 explicit inline StringInputBuffer(String* backing): |
7847 unibrow::InputBuffer<String, String*, 1024>(backing) {} | 7812 unibrow::InputBuffer<String, String*, 1024>(backing) {} |
7848 }; | 7813 }; |
7849 | 7814 |
7850 | 7815 |
| 7816 // A ConsStringOp that returns null. |
| 7817 // Useful when the operation to apply on a ConsString |
| 7818 // requires an expensive data structure. |
| 7819 struct ConsStringNullOp { |
| 7820 static inline String* Operate(String*, unsigned*, int32_t*, unsigned*); |
| 7821 }; |
| 7822 |
| 7823 |
7851 // This maintains an off-stack representation of the stack frames required | 7824 // This maintains an off-stack representation of the stack frames required |
7852 // to traverse a ConsString, allowing an entirely iterative and restartable | 7825 // to traverse a ConsString, allowing an entirely iterative and restartable |
7853 // traversal of the entire string | 7826 // traversal of the entire string |
7854 // Note: this class is not GC-safe. | 7827 // Note: this class is not GC-safe. |
7855 class ConsStringIteratorOp { | 7828 class ConsStringIteratorOp { |
7856 public: | 7829 public: |
7857 struct ContinueResponse { | |
7858 String* string_; | |
7859 unsigned offset_; | |
7860 unsigned length_; | |
7861 int32_t type_; | |
7862 }; | |
7863 inline ConsStringIteratorOp() {} | 7830 inline ConsStringIteratorOp() {} |
7864 String* Operate(ConsString* cons_string, unsigned* offset_out, | 7831 String* Operate(String* string, |
7865 int32_t* type_out, unsigned* length_out); | 7832 unsigned* offset_out, |
7866 inline bool ContinueOperation(ContinueResponse* response); | 7833 int32_t* type_out, |
| 7834 unsigned* length_out); |
| 7835 inline String* ContinueOperation(int32_t* type_out, unsigned* length_out); |
7867 inline void Reset(); | 7836 inline void Reset(); |
7868 inline bool HasMore(); | 7837 inline bool HasMore(); |
7869 | 7838 |
7870 private: | 7839 private: |
7871 // TODO(dcarney): Templatize this out for different stack sizes. | 7840 // TODO(dcarney): Templatize this out for different stack sizes. |
7872 static const unsigned kStackSize = 32; | 7841 static const unsigned kStackSize = 32; |
7873 // Use a mask instead of doing modulo operations for stack wrapping. | 7842 // Use a mask instead of doing modulo operations for stack wrapping. |
7874 static const unsigned kDepthMask = kStackSize-1; | 7843 static const unsigned kDepthMask = kStackSize-1; |
7875 STATIC_ASSERT(IS_POWER_OF_TWO(kStackSize)); | 7844 STATIC_ASSERT(IS_POWER_OF_TWO(kStackSize)); |
7876 static inline unsigned OffsetForDepth(unsigned depth); | 7845 static inline unsigned OffsetForDepth(unsigned depth); |
7877 | 7846 |
7878 inline void PushLeft(ConsString* string); | 7847 inline void PushLeft(ConsString* string); |
7879 inline void PushRight(ConsString* string); | 7848 inline void PushRight(ConsString* string); |
7880 inline void AdjustMaximumDepth(); | 7849 inline void AdjustMaximumDepth(); |
7881 inline void Pop(); | 7850 inline void Pop(); |
7882 String* NextLeaf(bool* blew_stack, int32_t* type_out, unsigned* length_out); | 7851 String* NextLeaf(bool* blew_stack, int32_t* type_out, unsigned* length_out); |
| 7852 String* Search(unsigned* offset_out, |
| 7853 int32_t* type_out, |
| 7854 unsigned* length_out); |
7883 | 7855 |
7884 unsigned depth_; | 7856 unsigned depth_; |
7885 unsigned maximum_depth_; | 7857 unsigned maximum_depth_; |
7886 // Stack must always contain only frames for which right traversal | 7858 // Stack must always contain only frames for which right traversal |
7887 // has not yet been performed. | 7859 // has not yet been performed. |
7888 ConsString* frames_[kStackSize]; | 7860 ConsString* frames_[kStackSize]; |
7889 unsigned consumed_; | 7861 unsigned consumed_; |
7890 ConsString* root_; | 7862 ConsString* root_; |
7891 int32_t root_type_; | |
7892 unsigned root_length_; | |
7893 DISALLOW_COPY_AND_ASSIGN(ConsStringIteratorOp); | 7863 DISALLOW_COPY_AND_ASSIGN(ConsStringIteratorOp); |
7894 }; | 7864 }; |
7895 | 7865 |
7896 | 7866 |
7897 // Note: this class is not GC-safe. | 7867 // Note: this class is not GC-safe. |
7898 class StringCharacterStream { | 7868 class StringCharacterStream { |
7899 public: | 7869 public: |
7900 inline StringCharacterStream( | 7870 inline StringCharacterStream(String* string, |
7901 String* string, unsigned offset, ConsStringIteratorOp* op); | 7871 unsigned offset, |
| 7872 ConsStringIteratorOp* op); |
7902 inline uint16_t GetNext(); | 7873 inline uint16_t GetNext(); |
7903 inline bool HasMore(); | 7874 inline bool HasMore(); |
7904 inline void Reset(String* string, unsigned offset, ConsStringIteratorOp* op); | 7875 inline void Reset(String* string, unsigned offset, ConsStringIteratorOp* op); |
7905 inline void VisitOneByteString(const uint8_t* chars, unsigned length); | 7876 inline void VisitOneByteString(const uint8_t* chars, unsigned length); |
7906 inline void VisitTwoByteString(const uint16_t* chars, unsigned length); | 7877 inline void VisitTwoByteString(const uint16_t* chars, unsigned length); |
7907 | 7878 |
7908 private: | 7879 private: |
7909 bool is_one_byte_; | 7880 bool is_one_byte_; |
7910 union { | 7881 union { |
7911 const uint8_t* buffer8_; | 7882 const uint8_t* buffer8_; |
(...skipping 970 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
8882 } else { | 8853 } else { |
8883 value &= ~(1 << bit_position); | 8854 value &= ~(1 << bit_position); |
8884 } | 8855 } |
8885 return value; | 8856 return value; |
8886 } | 8857 } |
8887 }; | 8858 }; |
8888 | 8859 |
8889 } } // namespace v8::internal | 8860 } } // namespace v8::internal |
8890 | 8861 |
8891 #endif // V8_OBJECTS_H_ | 8862 #endif // V8_OBJECTS_H_ |
OLD | NEW |