OLD | NEW |
1 // Copyright 2006-2009 the V8 project authors. All rights reserved. | 1 // Copyright 2006-2009 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 2014 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2025 // // Returns the hash value for object. | 2025 // // Returns the hash value for object. |
2026 // static uint32_t HashForObject(Key key, Object* object); | 2026 // static uint32_t HashForObject(Key key, Object* object); |
2027 // // Convert key to an object. | 2027 // // Convert key to an object. |
2028 // static inline Object* AsObject(Key key); | 2028 // static inline Object* AsObject(Key key); |
2029 // // The prefix size indicates number of elements in the beginning | 2029 // // The prefix size indicates number of elements in the beginning |
2030 // // of the backing storage. | 2030 // // of the backing storage. |
2031 // static const int kPrefixSize = ..; | 2031 // static const int kPrefixSize = ..; |
2032 // // The Element size indicates number of elements per entry. | 2032 // // The Element size indicates number of elements per entry. |
2033 // static const int kEntrySize = ..; | 2033 // static const int kEntrySize = ..; |
2034 // }; | 2034 // }; |
2035 // table. The prefix size indicates an amount of memory in the | 2035 // The prefix size indicates an amount of memory in the |
2036 // beginning of the backing storage that can be used for non-element | 2036 // beginning of the backing storage that can be used for non-element |
2037 // information by subclasses. | 2037 // information by subclasses. |
2038 | 2038 |
2039 template<typename Shape, typename Key> | 2039 template<typename Shape, typename Key> |
2040 class HashTable: public FixedArray { | 2040 class HashTable: public FixedArray { |
2041 public: | 2041 public: |
2042 // Returns the number of elements in the dictionary. | 2042 // Returns the number of elements in the hash table. |
2043 int NumberOfElements() { | 2043 int NumberOfElements() { |
2044 return Smi::cast(get(kNumberOfElementsIndex))->value(); | 2044 return Smi::cast(get(kNumberOfElementsIndex))->value(); |
2045 } | 2045 } |
2046 | 2046 |
2047 // Returns the capacity of the dictionary. | 2047 // Returns the capacity of the hash table. |
2048 int Capacity() { | 2048 int Capacity() { |
2049 return Smi::cast(get(kCapacityIndex))->value(); | 2049 return Smi::cast(get(kCapacityIndex))->value(); |
2050 } | 2050 } |
2051 | 2051 |
2052 // ElementAdded should be called whenever an element is added to a | 2052 // ElementAdded should be called whenever an element is added to a |
2053 // dictionary. | 2053 // hash table. |
2054 void ElementAdded() { SetNumberOfElements(NumberOfElements() + 1); } | 2054 void ElementAdded() { SetNumberOfElements(NumberOfElements() + 1); } |
2055 | 2055 |
2056 // ElementRemoved should be called whenever an element is removed from | 2056 // ElementRemoved should be called whenever an element is removed from |
2057 // a dictionary. | 2057 // a hash table. |
2058 void ElementRemoved() { SetNumberOfElements(NumberOfElements() - 1); } | 2058 void ElementRemoved() { SetNumberOfElements(NumberOfElements() - 1); } |
2059 void ElementsRemoved(int n) { SetNumberOfElements(NumberOfElements() - n); } | 2059 void ElementsRemoved(int n) { SetNumberOfElements(NumberOfElements() - n); } |
2060 | 2060 |
2061 // Returns a new array for dictionary usage. Might return Failure. | 2061 // Returns a new HashTable object. Might return Failure. |
2062 static Object* Allocate(int at_least_space_for); | 2062 static Object* Allocate(int at_least_space_for); |
2063 | 2063 |
2064 // Returns the key at entry. | 2064 // Returns the key at entry. |
2065 Object* KeyAt(int entry) { return get(EntryToIndex(entry)); } | 2065 Object* KeyAt(int entry) { return get(EntryToIndex(entry)); } |
2066 | 2066 |
2067 // Tells whether k is a real key. Null and undefined are not allowed | 2067 // Tells whether k is a real key. Null and undefined are not allowed |
2068 // as keys and can be used to indicate missing or deleted elements. | 2068 // as keys and can be used to indicate missing or deleted elements. |
2069 bool IsKey(Object* k) { | 2069 bool IsKey(Object* k) { |
2070 return !k->IsNull() && !k->IsUndefined(); | 2070 return !k->IsNull() && !k->IsUndefined(); |
2071 } | 2071 } |
(...skipping 29 matching lines...) Expand all Loading... |
2101 | 2101 |
2102 // Find the entry at which to insert element with the given key that | 2102 // Find the entry at which to insert element with the given key that |
2103 // has the given hash value. | 2103 // has the given hash value. |
2104 uint32_t FindInsertionEntry(uint32_t hash); | 2104 uint32_t FindInsertionEntry(uint32_t hash); |
2105 | 2105 |
2106 // Returns the index for an entry (of the key) | 2106 // Returns the index for an entry (of the key) |
2107 static inline int EntryToIndex(int entry) { | 2107 static inline int EntryToIndex(int entry) { |
2108 return (entry * kEntrySize) + kElementsStartIndex; | 2108 return (entry * kEntrySize) + kElementsStartIndex; |
2109 } | 2109 } |
2110 | 2110 |
2111 // Update the number of elements in the dictionary. | 2111 // Update the number of elements in the hash table. |
2112 void SetNumberOfElements(int nof) { | 2112 void SetNumberOfElements(int nof) { |
2113 fast_set(this, kNumberOfElementsIndex, Smi::FromInt(nof)); | 2113 fast_set(this, kNumberOfElementsIndex, Smi::FromInt(nof)); |
2114 } | 2114 } |
2115 | 2115 |
2116 // Sets the capacity of the hash table. | 2116 // Sets the capacity of the hash table. |
2117 void SetCapacity(int capacity) { | 2117 void SetCapacity(int capacity) { |
2118 // To scale a computed hash code to fit within the hash table, we | 2118 // To scale a computed hash code to fit within the hash table, we |
2119 // use bit-wise AND with a mask, so the capacity must be positive | 2119 // use bit-wise AND with a mask, so the capacity must be positive |
2120 // and non-zero. | 2120 // and non-zero. |
2121 ASSERT(capacity > 0); | 2121 ASSERT(capacity > 0); |
(...skipping 15 matching lines...) Expand all Loading... |
2137 | 2137 |
2138 // HashTableKey is an abstract superclass for virtual key behavior. | 2138 // HashTableKey is an abstract superclass for virtual key behavior. |
2139 class HashTableKey { | 2139 class HashTableKey { |
2140 public: | 2140 public: |
2141 // Returns whether the other object matches this key. | 2141 // Returns whether the other object matches this key. |
2142 virtual bool IsMatch(Object* other) = 0; | 2142 virtual bool IsMatch(Object* other) = 0; |
2143 // Returns the hash value for this key. | 2143 // Returns the hash value for this key. |
2144 virtual uint32_t Hash() = 0; | 2144 virtual uint32_t Hash() = 0; |
2145 // Returns the hash value for object. | 2145 // Returns the hash value for object. |
2146 virtual uint32_t HashForObject(Object* key) = 0; | 2146 virtual uint32_t HashForObject(Object* key) = 0; |
2147 // Returns the key object for storing into the dictionary. | 2147 // Returns the key object for storing into the hash table. |
2148 // If allocations fails a failure object is returned. | 2148 // If allocations fails a failure object is returned. |
2149 virtual Object* AsObject() = 0; | 2149 virtual Object* AsObject() = 0; |
2150 // Required. | 2150 // Required. |
2151 virtual ~HashTableKey() {} | 2151 virtual ~HashTableKey() {} |
2152 }; | 2152 }; |
2153 | 2153 |
2154 class SymbolTableShape { | 2154 class SymbolTableShape { |
2155 public: | 2155 public: |
2156 static bool IsMatch(HashTableKey* key, Object* value) { | 2156 static bool IsMatch(HashTableKey* key, Object* value) { |
2157 return key->IsMatch(value); | 2157 return key->IsMatch(value); |
(...skipping 1410 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3568 } | 3568 } |
3569 | 3569 |
3570 static Object* AsObject(HashTableKey* key) { | 3570 static Object* AsObject(HashTableKey* key) { |
3571 return key->AsObject(); | 3571 return key->AsObject(); |
3572 } | 3572 } |
3573 | 3573 |
3574 static const int kPrefixSize = 0; | 3574 static const int kPrefixSize = 0; |
3575 static const int kEntrySize = 2; | 3575 static const int kEntrySize = 2; |
3576 }; | 3576 }; |
3577 | 3577 |
| 3578 |
3578 class CompilationCacheTable: public HashTable<CompilationCacheShape, | 3579 class CompilationCacheTable: public HashTable<CompilationCacheShape, |
3579 HashTableKey*> { | 3580 HashTableKey*> { |
3580 public: | 3581 public: |
3581 // Find cached value for a string key, otherwise return null. | 3582 // Find cached value for a string key, otherwise return null. |
3582 Object* Lookup(String* src); | 3583 Object* Lookup(String* src); |
3583 Object* LookupEval(String* src, Context* context); | 3584 Object* LookupEval(String* src, Context* context); |
3584 Object* LookupRegExp(String* source, JSRegExp::Flags flags); | 3585 Object* LookupRegExp(String* source, JSRegExp::Flags flags); |
3585 Object* Put(String* src, Object* value); | 3586 Object* Put(String* src, Object* value); |
3586 Object* PutEval(String* src, Context* context, Object* value); | 3587 Object* PutEval(String* src, Context* context, Object* value); |
3587 Object* PutRegExp(String* src, JSRegExp::Flags flags, FixedArray* value); | 3588 Object* PutRegExp(String* src, JSRegExp::Flags flags, FixedArray* value); |
(...skipping 1297 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
4885 } else { | 4886 } else { |
4886 value &= ~(1 << bit_position); | 4887 value &= ~(1 << bit_position); |
4887 } | 4888 } |
4888 return value; | 4889 return value; |
4889 } | 4890 } |
4890 }; | 4891 }; |
4891 | 4892 |
4892 } } // namespace v8::internal | 4893 } } // namespace v8::internal |
4893 | 4894 |
4894 #endif // V8_OBJECTS_H_ | 4895 #endif // V8_OBJECTS_H_ |
OLD | NEW |