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 2575 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2586 // // The prefix size indicates number of elements in the beginning | 2586 // // The prefix size indicates number of elements in the beginning |
2587 // // of the backing storage. | 2587 // // of the backing storage. |
2588 // static const int kPrefixSize = ..; | 2588 // static const int kPrefixSize = ..; |
2589 // // The Element size indicates number of elements per entry. | 2589 // // The Element size indicates number of elements per entry. |
2590 // static const int kEntrySize = ..; | 2590 // static const int kEntrySize = ..; |
2591 // }; | 2591 // }; |
2592 // The prefix size indicates an amount of memory in the | 2592 // The prefix size indicates an amount of memory in the |
2593 // beginning of the backing storage that can be used for non-element | 2593 // beginning of the backing storage that can be used for non-element |
2594 // information by subclasses. | 2594 // information by subclasses. |
2595 | 2595 |
| 2596 template<typename Key> |
| 2597 class BaseShape { |
| 2598 public: |
| 2599 static const bool UsesSeed = false; |
| 2600 static uint32_t Hash(Key key) { return 0; } |
| 2601 static uint32_t SeededHash(Key key, uint32_t seed) { |
| 2602 // Won't be called if UsesSeed isn't overridden by child class. |
| 2603 return Hash(key); |
| 2604 } |
| 2605 static uint32_t HashForObject(Key key, Object* object) { return 0; } |
| 2606 static uint32_t SeededHashForObject(Key key, uint32_t seed, Object* object) { |
| 2607 // Won't be called if UsesSeed isn't overridden by child class. |
| 2608 return HashForObject(key, object); |
| 2609 } |
| 2610 }; |
| 2611 |
2596 template<typename Shape, typename Key> | 2612 template<typename Shape, typename Key> |
2597 class HashTable: public FixedArray { | 2613 class HashTable: public FixedArray { |
2598 public: | 2614 public: |
| 2615 // Wrapper methods |
| 2616 inline uint32_t Hash(Key key) { |
| 2617 if (Shape::UsesSeed) { |
| 2618 return Shape::SeededHash(key, |
| 2619 GetHeap()->StringHashSeed()); |
| 2620 } else { |
| 2621 return Shape::Hash(key); |
| 2622 } |
| 2623 } |
| 2624 |
| 2625 inline uint32_t HashForObject(Key key, Object* object) { |
| 2626 if (Shape::UsesSeed) { |
| 2627 return Shape::SeededHashForObject(key, |
| 2628 GetHeap()->StringHashSeed(), object); |
| 2629 } else { |
| 2630 return Shape::HashForObject(key, object); |
| 2631 } |
| 2632 } |
| 2633 |
2599 // Returns the number of elements in the hash table. | 2634 // Returns the number of elements in the hash table. |
2600 int NumberOfElements() { | 2635 int NumberOfElements() { |
2601 return Smi::cast(get(kNumberOfElementsIndex))->value(); | 2636 return Smi::cast(get(kNumberOfElementsIndex))->value(); |
2602 } | 2637 } |
2603 | 2638 |
2604 // Returns the number of deleted elements in the hash table. | 2639 // Returns the number of deleted elements in the hash table. |
2605 int NumberOfDeletedElements() { | 2640 int NumberOfDeletedElements() { |
2606 return Smi::cast(get(kNumberOfDeletedElementsIndex))->value(); | 2641 return Smi::cast(get(kNumberOfDeletedElementsIndex))->value(); |
2607 } | 2642 } |
2608 | 2643 |
(...skipping 121 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2730 MUST_USE_RESULT MaybeObject* Rehash(HashTable* new_table, Key key); | 2765 MUST_USE_RESULT MaybeObject* Rehash(HashTable* new_table, Key key); |
2731 | 2766 |
2732 // Attempt to shrink hash table after removal of key. | 2767 // Attempt to shrink hash table after removal of key. |
2733 MUST_USE_RESULT MaybeObject* Shrink(Key key); | 2768 MUST_USE_RESULT MaybeObject* Shrink(Key key); |
2734 | 2769 |
2735 // Ensure enough space for n additional elements. | 2770 // Ensure enough space for n additional elements. |
2736 MUST_USE_RESULT MaybeObject* EnsureCapacity(int n, Key key); | 2771 MUST_USE_RESULT MaybeObject* EnsureCapacity(int n, Key key); |
2737 }; | 2772 }; |
2738 | 2773 |
2739 | 2774 |
2740 | |
2741 // HashTableKey is an abstract superclass for virtual key behavior. | 2775 // HashTableKey is an abstract superclass for virtual key behavior. |
2742 class HashTableKey { | 2776 class HashTableKey { |
2743 public: | 2777 public: |
2744 // Returns whether the other object matches this key. | 2778 // Returns whether the other object matches this key. |
2745 virtual bool IsMatch(Object* other) = 0; | 2779 virtual bool IsMatch(Object* other) = 0; |
2746 // Returns the hash value for this key. | 2780 // Returns the hash value for this key. |
2747 virtual uint32_t Hash() = 0; | 2781 virtual uint32_t Hash() = 0; |
2748 // Returns the hash value for object. | 2782 // Returns the hash value for object. |
2749 virtual uint32_t HashForObject(Object* key) = 0; | 2783 virtual uint32_t HashForObject(Object* key) = 0; |
2750 // Returns the key object for storing into the hash table. | 2784 // Returns the key object for storing into the hash table. |
2751 // If allocations fails a failure object is returned. | 2785 // If allocations fails a failure object is returned. |
2752 MUST_USE_RESULT virtual MaybeObject* AsObject() = 0; | 2786 MUST_USE_RESULT virtual MaybeObject* AsObject() = 0; |
2753 // Required. | 2787 // Required. |
2754 virtual ~HashTableKey() {} | 2788 virtual ~HashTableKey() {} |
2755 }; | 2789 }; |
2756 | 2790 |
2757 class SymbolTableShape { | 2791 |
| 2792 class SymbolTableShape : public BaseShape<HashTableKey*> { |
2758 public: | 2793 public: |
2759 static inline bool IsMatch(HashTableKey* key, Object* value) { | 2794 static inline bool IsMatch(HashTableKey* key, Object* value) { |
2760 return key->IsMatch(value); | 2795 return key->IsMatch(value); |
2761 } | 2796 } |
2762 static inline uint32_t Hash(HashTableKey* key) { | 2797 static inline uint32_t Hash(HashTableKey* key) { |
2763 return key->Hash(); | 2798 return key->Hash(); |
2764 } | 2799 } |
2765 static inline uint32_t HashForObject(HashTableKey* key, Object* object) { | 2800 static inline uint32_t HashForObject(HashTableKey* key, Object* object) { |
2766 return key->HashForObject(object); | 2801 return key->HashForObject(object); |
2767 } | 2802 } |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2806 // Casting. | 2841 // Casting. |
2807 static inline SymbolTable* cast(Object* obj); | 2842 static inline SymbolTable* cast(Object* obj); |
2808 | 2843 |
2809 private: | 2844 private: |
2810 MUST_USE_RESULT MaybeObject* LookupKey(HashTableKey* key, Object** s); | 2845 MUST_USE_RESULT MaybeObject* LookupKey(HashTableKey* key, Object** s); |
2811 | 2846 |
2812 DISALLOW_IMPLICIT_CONSTRUCTORS(SymbolTable); | 2847 DISALLOW_IMPLICIT_CONSTRUCTORS(SymbolTable); |
2813 }; | 2848 }; |
2814 | 2849 |
2815 | 2850 |
2816 class MapCacheShape { | 2851 class MapCacheShape : public BaseShape<HashTableKey*> { |
2817 public: | 2852 public: |
2818 static inline bool IsMatch(HashTableKey* key, Object* value) { | 2853 static inline bool IsMatch(HashTableKey* key, Object* value) { |
2819 return key->IsMatch(value); | 2854 return key->IsMatch(value); |
2820 } | 2855 } |
2821 static inline uint32_t Hash(HashTableKey* key) { | 2856 static inline uint32_t Hash(HashTableKey* key) { |
2822 return key->Hash(); | 2857 return key->Hash(); |
2823 } | 2858 } |
2824 | 2859 |
2825 static inline uint32_t HashForObject(HashTableKey* key, Object* object) { | 2860 static inline uint32_t HashForObject(HashTableKey* key, Object* object) { |
2826 return key->HashForObject(object); | 2861 return key->HashForObject(object); |
(...skipping 135 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2962 uint32_t hash); | 2997 uint32_t hash); |
2963 | 2998 |
2964 // Generate new enumeration indices to avoid enumeration index overflow. | 2999 // Generate new enumeration indices to avoid enumeration index overflow. |
2965 MUST_USE_RESULT MaybeObject* GenerateNewEnumerationIndices(); | 3000 MUST_USE_RESULT MaybeObject* GenerateNewEnumerationIndices(); |
2966 static const int kMaxNumberKeyIndex = | 3001 static const int kMaxNumberKeyIndex = |
2967 HashTable<Shape, Key>::kPrefixStartIndex; | 3002 HashTable<Shape, Key>::kPrefixStartIndex; |
2968 static const int kNextEnumerationIndexIndex = kMaxNumberKeyIndex + 1; | 3003 static const int kNextEnumerationIndexIndex = kMaxNumberKeyIndex + 1; |
2969 }; | 3004 }; |
2970 | 3005 |
2971 | 3006 |
2972 class StringDictionaryShape { | 3007 class StringDictionaryShape : public BaseShape<String*> { |
2973 public: | 3008 public: |
2974 static inline bool IsMatch(String* key, Object* other); | 3009 static inline bool IsMatch(String* key, Object* other); |
2975 static inline uint32_t Hash(String* key); | 3010 static inline uint32_t Hash(String* key); |
2976 static inline uint32_t HashForObject(String* key, Object* object); | 3011 static inline uint32_t HashForObject(String* key, Object* object); |
2977 MUST_USE_RESULT static inline MaybeObject* AsObject(String* key); | 3012 MUST_USE_RESULT static inline MaybeObject* AsObject(String* key); |
2978 static const int kPrefixSize = 2; | 3013 static const int kPrefixSize = 2; |
2979 static const int kEntrySize = 3; | 3014 static const int kEntrySize = 3; |
2980 static const bool kIsEnumerable = true; | 3015 static const bool kIsEnumerable = true; |
2981 }; | 3016 }; |
2982 | 3017 |
(...skipping 12 matching lines...) Expand all Loading... |
2995 MUST_USE_RESULT MaybeObject* TransformPropertiesToFastFor( | 3030 MUST_USE_RESULT MaybeObject* TransformPropertiesToFastFor( |
2996 JSObject* obj, | 3031 JSObject* obj, |
2997 int unused_property_fields); | 3032 int unused_property_fields); |
2998 | 3033 |
2999 // Find entry for key, otherwise return kNotFound. Optimized version of | 3034 // Find entry for key, otherwise return kNotFound. Optimized version of |
3000 // HashTable::FindEntry. | 3035 // HashTable::FindEntry. |
3001 int FindEntry(String* key); | 3036 int FindEntry(String* key); |
3002 }; | 3037 }; |
3003 | 3038 |
3004 | 3039 |
3005 class NumberDictionaryShape { | 3040 class NumberDictionaryShape : public BaseShape<uint32_t> { |
3006 public: | 3041 public: |
| 3042 static const bool UsesSeed = true; |
| 3043 |
3007 static inline bool IsMatch(uint32_t key, Object* other); | 3044 static inline bool IsMatch(uint32_t key, Object* other); |
3008 static inline uint32_t Hash(uint32_t key); | 3045 static inline uint32_t Hash(uint32_t key); |
| 3046 static inline uint32_t SeededHash(uint32_t key, uint32_t seed); |
3009 static inline uint32_t HashForObject(uint32_t key, Object* object); | 3047 static inline uint32_t HashForObject(uint32_t key, Object* object); |
| 3048 static inline uint32_t SeededHashForObject(uint32_t key, |
| 3049 uint32_t seed, |
| 3050 Object* object); |
3010 MUST_USE_RESULT static inline MaybeObject* AsObject(uint32_t key); | 3051 MUST_USE_RESULT static inline MaybeObject* AsObject(uint32_t key); |
3011 static const int kPrefixSize = 2; | 3052 static const int kPrefixSize = 2; |
3012 static const int kEntrySize = 3; | 3053 static const int kEntrySize = 3; |
3013 static const bool kIsEnumerable = false; | 3054 static const bool kIsEnumerable = false; |
3014 }; | 3055 }; |
3015 | 3056 |
3016 | 3057 |
3017 class NumberDictionary: public Dictionary<NumberDictionaryShape, uint32_t> { | 3058 class NumberDictionary: public Dictionary<NumberDictionaryShape, uint32_t> { |
3018 public: | 3059 public: |
3019 static NumberDictionary* cast(Object* obj) { | 3060 static NumberDictionary* cast(Object* obj) { |
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3055 inline uint32_t max_number_key(); | 3096 inline uint32_t max_number_key(); |
3056 | 3097 |
3057 // Bit masks. | 3098 // Bit masks. |
3058 static const int kRequiresSlowElementsMask = 1; | 3099 static const int kRequiresSlowElementsMask = 1; |
3059 static const int kRequiresSlowElementsTagSize = 1; | 3100 static const int kRequiresSlowElementsTagSize = 1; |
3060 static const uint32_t kRequiresSlowElementsLimit = (1 << 29) - 1; | 3101 static const uint32_t kRequiresSlowElementsLimit = (1 << 29) - 1; |
3061 }; | 3102 }; |
3062 | 3103 |
3063 | 3104 |
3064 template <int entrysize> | 3105 template <int entrysize> |
3065 class ObjectHashTableShape { | 3106 class ObjectHashTableShape : public BaseShape<Object*> { |
3066 public: | 3107 public: |
3067 static inline bool IsMatch(Object* key, Object* other); | 3108 static inline bool IsMatch(Object* key, Object* other); |
3068 static inline uint32_t Hash(Object* key); | 3109 static inline uint32_t Hash(Object* key); |
3069 static inline uint32_t HashForObject(Object* key, Object* object); | 3110 static inline uint32_t HashForObject(Object* key, Object* object); |
3070 MUST_USE_RESULT static inline MaybeObject* AsObject(Object* key); | 3111 MUST_USE_RESULT static inline MaybeObject* AsObject(Object* key); |
3071 static const int kPrefixSize = 0; | 3112 static const int kPrefixSize = 0; |
3072 static const int kEntrySize = entrysize; | 3113 static const int kEntrySize = entrysize; |
3073 }; | 3114 }; |
3074 | 3115 |
3075 | 3116 |
(...skipping 2891 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
5967 // object is in the saved code field. | 6008 // object is in the saved code field. |
5968 static const int kCompilationErrorValue = -2; | 6009 static const int kCompilationErrorValue = -2; |
5969 | 6010 |
5970 // When we store the sweep generation at which we moved the code from the | 6011 // When we store the sweep generation at which we moved the code from the |
5971 // code index to the saved code index we mask it of to be in the [0:255] | 6012 // code index to the saved code index we mask it of to be in the [0:255] |
5972 // range. | 6013 // range. |
5973 static const int kCodeAgeMask = 0xff; | 6014 static const int kCodeAgeMask = 0xff; |
5974 }; | 6015 }; |
5975 | 6016 |
5976 | 6017 |
5977 class CompilationCacheShape { | 6018 class CompilationCacheShape : public BaseShape<HashTableKey*> { |
5978 public: | 6019 public: |
5979 static inline bool IsMatch(HashTableKey* key, Object* value) { | 6020 static inline bool IsMatch(HashTableKey* key, Object* value) { |
5980 return key->IsMatch(value); | 6021 return key->IsMatch(value); |
5981 } | 6022 } |
5982 | 6023 |
5983 static inline uint32_t Hash(HashTableKey* key) { | 6024 static inline uint32_t Hash(HashTableKey* key) { |
5984 return key->Hash(); | 6025 return key->Hash(); |
5985 } | 6026 } |
5986 | 6027 |
5987 static inline uint32_t HashForObject(HashTableKey* key, Object* object) { | 6028 static inline uint32_t HashForObject(HashTableKey* key, Object* object) { |
(...skipping 83 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
6071 // Code cache layout of the default cache. Elements are alternating name and | 6112 // Code cache layout of the default cache. Elements are alternating name and |
6072 // code objects for non normal load/store/call IC's. | 6113 // code objects for non normal load/store/call IC's. |
6073 static const int kCodeCacheEntrySize = 2; | 6114 static const int kCodeCacheEntrySize = 2; |
6074 static const int kCodeCacheEntryNameOffset = 0; | 6115 static const int kCodeCacheEntryNameOffset = 0; |
6075 static const int kCodeCacheEntryCodeOffset = 1; | 6116 static const int kCodeCacheEntryCodeOffset = 1; |
6076 | 6117 |
6077 DISALLOW_IMPLICIT_CONSTRUCTORS(CodeCache); | 6118 DISALLOW_IMPLICIT_CONSTRUCTORS(CodeCache); |
6078 }; | 6119 }; |
6079 | 6120 |
6080 | 6121 |
6081 class CodeCacheHashTableShape { | 6122 class CodeCacheHashTableShape : public BaseShape<HashTableKey*> { |
6082 public: | 6123 public: |
6083 static inline bool IsMatch(HashTableKey* key, Object* value) { | 6124 static inline bool IsMatch(HashTableKey* key, Object* value) { |
6084 return key->IsMatch(value); | 6125 return key->IsMatch(value); |
6085 } | 6126 } |
6086 | 6127 |
6087 static inline uint32_t Hash(HashTableKey* key) { | 6128 static inline uint32_t Hash(HashTableKey* key) { |
6088 return key->Hash(); | 6129 return key->Hash(); |
6089 } | 6130 } |
6090 | 6131 |
6091 static inline uint32_t HashForObject(HashTableKey* key, Object* object) { | 6132 static inline uint32_t HashForObject(HashTableKey* key, Object* object) { |
(...skipping 1985 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
8077 } else { | 8118 } else { |
8078 value &= ~(1 << bit_position); | 8119 value &= ~(1 << bit_position); |
8079 } | 8120 } |
8080 return value; | 8121 return value; |
8081 } | 8122 } |
8082 }; | 8123 }; |
8083 | 8124 |
8084 } } // namespace v8::internal | 8125 } } // namespace v8::internal |
8085 | 8126 |
8086 #endif // V8_OBJECTS_H_ | 8127 #endif // V8_OBJECTS_H_ |
OLD | NEW |