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 2895 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
2906 set(kCapacityIndex, Smi::FromInt(capacity)); | 2906 set(kCapacityIndex, Smi::FromInt(capacity)); |
2907 } | 2907 } |
2908 | 2908 |
2909 | 2909 |
2910 // Returns probe entry. | 2910 // Returns probe entry. |
2911 static uint32_t GetProbe(uint32_t hash, uint32_t number, uint32_t size) { | 2911 static uint32_t GetProbe(uint32_t hash, uint32_t number, uint32_t size) { |
2912 ASSERT(IsPowerOf2(size)); | 2912 ASSERT(IsPowerOf2(size)); |
2913 return (hash + GetProbeOffset(number)) & (size - 1); | 2913 return (hash + GetProbeOffset(number)) & (size - 1); |
2914 } | 2914 } |
2915 | 2915 |
2916 static uint32_t FirstProbe(uint32_t hash, uint32_t size) { | 2916 inline static uint32_t FirstProbe(uint32_t hash, uint32_t size) { |
2917 return hash & (size - 1); | 2917 return hash & (size - 1); |
2918 } | 2918 } |
2919 | 2919 |
2920 static uint32_t NextProbe(uint32_t last, uint32_t number, uint32_t size) { | 2920 inline static uint32_t NextProbe( |
Vyacheslav Egorov (Google)
2012/09/26 15:12:14
If you want to _force_ inlining consider using INL
Yang
2012/09/26 15:14:43
I'll do some experiments on whether this makes any
| |
2921 uint32_t last, uint32_t number, uint32_t size) { | |
2921 return (last + number) & (size - 1); | 2922 return (last + number) & (size - 1); |
2922 } | 2923 } |
2923 | 2924 |
2924 // Rehashes this hash-table into the new table. | 2925 // Rehashes this hash-table into the new table. |
2925 MUST_USE_RESULT MaybeObject* Rehash(HashTable* new_table, Key key); | 2926 MUST_USE_RESULT MaybeObject* Rehash(HashTable* new_table, Key key); |
2926 | 2927 |
2927 // Attempt to shrink hash table after removal of key. | 2928 // Attempt to shrink hash table after removal of key. |
2928 MUST_USE_RESULT MaybeObject* Shrink(Key key); | 2929 MUST_USE_RESULT MaybeObject* Shrink(Key key); |
2929 | 2930 |
2930 // Ensure enough space for n additional elements. | 2931 // Ensure enough space for n additional elements. |
(...skipping 66 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
2997 // parameter. | 2998 // parameter. |
2998 bool LookupSymbolIfExists(String* str, String** symbol); | 2999 bool LookupSymbolIfExists(String* str, String** symbol); |
2999 bool LookupTwoCharsSymbolIfExists(uint32_t c1, uint32_t c2, String** symbol); | 3000 bool LookupTwoCharsSymbolIfExists(uint32_t c1, uint32_t c2, String** symbol); |
3000 | 3001 |
3001 // Casting. | 3002 // Casting. |
3002 static inline SymbolTable* cast(Object* obj); | 3003 static inline SymbolTable* cast(Object* obj); |
3003 | 3004 |
3004 private: | 3005 private: |
3005 MUST_USE_RESULT MaybeObject* LookupKey(HashTableKey* key, Object** s); | 3006 MUST_USE_RESULT MaybeObject* LookupKey(HashTableKey* key, Object** s); |
3006 | 3007 |
3008 template <bool seq_ascii> friend class JsonParser; | |
3009 | |
3007 DISALLOW_IMPLICIT_CONSTRUCTORS(SymbolTable); | 3010 DISALLOW_IMPLICIT_CONSTRUCTORS(SymbolTable); |
3008 }; | 3011 }; |
3009 | 3012 |
3010 | 3013 |
3011 class MapCacheShape : public BaseShape<HashTableKey*> { | 3014 class MapCacheShape : public BaseShape<HashTableKey*> { |
3012 public: | 3015 public: |
3013 static inline bool IsMatch(HashTableKey* key, Object* value) { | 3016 static inline bool IsMatch(HashTableKey* key, Object* value) { |
3014 return key->IsMatch(value); | 3017 return key->IsMatch(value); |
3015 } | 3018 } |
3016 static inline uint32_t Hash(HashTableKey* key) { | 3019 static inline uint32_t Hash(HashTableKey* key) { |
(...skipping 4030 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
7047 void AddSurrogatePairNoIndex(uc32 c); | 7050 void AddSurrogatePairNoIndex(uc32 c); |
7048 | 7051 |
7049 // Returns the value to store in the hash field of a string with | 7052 // Returns the value to store in the hash field of a string with |
7050 // the given length and contents. | 7053 // the given length and contents. |
7051 uint32_t GetHashField(); | 7054 uint32_t GetHashField(); |
7052 | 7055 |
7053 // Returns true if the characters seen so far make up a legal array | 7056 // Returns true if the characters seen so far make up a legal array |
7054 // index. | 7057 // index. |
7055 bool is_array_index() { return is_array_index_; } | 7058 bool is_array_index() { return is_array_index_; } |
7056 | 7059 |
7057 bool is_valid() { return is_valid_; } | |
7058 | |
7059 void invalidate() { is_valid_ = false; } | |
7060 | |
7061 // Calculated hash value for a string consisting of 1 to | 7060 // Calculated hash value for a string consisting of 1 to |
7062 // String::kMaxArrayIndexSize digits with no leading zeros (except "0"). | 7061 // String::kMaxArrayIndexSize digits with no leading zeros (except "0"). |
7063 // value is represented decimal value. | 7062 // value is represented decimal value. |
7064 static uint32_t MakeArrayIndexHash(uint32_t value, int length); | 7063 static uint32_t MakeArrayIndexHash(uint32_t value, int length); |
7065 | 7064 |
7066 // No string is allowed to have a hash of zero. That value is reserved | 7065 // No string is allowed to have a hash of zero. That value is reserved |
7067 // for internal properties. If the hash calculation yields zero then we | 7066 // for internal properties. If the hash calculation yields zero then we |
7068 // use 27 instead. | 7067 // use 27 instead. |
7069 static const int kZeroHash = 27; | 7068 static const int kZeroHash = 27; |
7070 | 7069 |
7071 private: | 7070 private: |
7072 uint32_t array_index() { | 7071 uint32_t array_index() { |
7073 ASSERT(is_array_index()); | 7072 ASSERT(is_array_index()); |
7074 return array_index_; | 7073 return array_index_; |
7075 } | 7074 } |
7076 | 7075 |
7077 inline uint32_t GetHash(); | 7076 inline uint32_t GetHash(); |
7078 | 7077 |
7078 // Reusable parts of the hashing algorithm. | |
7079 INLINE(static uint32_t AddCharacterCore(uint32_t running_hash, uint32_t c)); | |
7080 INLINE(static uint32_t GetHashCore(uint32_t running_hash)); | |
7081 | |
7079 int length_; | 7082 int length_; |
7080 uint32_t raw_running_hash_; | 7083 uint32_t raw_running_hash_; |
7081 uint32_t array_index_; | 7084 uint32_t array_index_; |
7082 bool is_array_index_; | 7085 bool is_array_index_; |
7083 bool is_first_char_; | 7086 bool is_first_char_; |
7084 bool is_valid_; | |
7085 friend class TwoCharHashTableKey; | 7087 friend class TwoCharHashTableKey; |
7088 | |
7089 template <bool seq_ascii> friend class JsonParser; | |
7086 }; | 7090 }; |
7087 | 7091 |
7088 | 7092 |
7093 class IncrementalAsciiStringHasher { | |
7094 public: | |
7095 explicit inline IncrementalAsciiStringHasher(uint32_t seed, char first_char); | |
7096 inline void AddCharacter(uc32 c); | |
7097 inline uint32_t GetHash(); | |
7098 | |
7099 private: | |
7100 int length_; | |
7101 uint32_t raw_running_hash_; | |
7102 uint32_t array_index_; | |
7103 bool is_array_index_; | |
7104 char first_char_; | |
7105 }; | |
7106 | |
7107 | |
7089 // Calculates string hash. | 7108 // Calculates string hash. |
7090 template <typename schar> | 7109 template <typename schar> |
7091 inline uint32_t HashSequentialString(const schar* chars, | 7110 inline uint32_t HashSequentialString(const schar* chars, |
7092 int length, | 7111 int length, |
7093 uint32_t seed); | 7112 uint32_t seed); |
7094 | 7113 |
7095 | 7114 |
7096 // The characteristics of a string are stored in its map. Retrieving these | 7115 // The characteristics of a string are stored in its map. Retrieving these |
7097 // few bits of information is moderately expensive, involving two memory | 7116 // few bits of information is moderately expensive, involving two memory |
7098 // loads where the second is dependent on the first. To improve efficiency | 7117 // loads where the second is dependent on the first. To improve efficiency |
(...skipping 1920 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
9019 } else { | 9038 } else { |
9020 value &= ~(1 << bit_position); | 9039 value &= ~(1 << bit_position); |
9021 } | 9040 } |
9022 return value; | 9041 return value; |
9023 } | 9042 } |
9024 }; | 9043 }; |
9025 | 9044 |
9026 } } // namespace v8::internal | 9045 } } // namespace v8::internal |
9027 | 9046 |
9028 #endif // V8_OBJECTS_H_ | 9047 #endif // V8_OBJECTS_H_ |
OLD | NEW |