OLD | NEW |
1 // Copyright 2011 the V8 project authors. All rights reserved. | 1 // Copyright 2011 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 2496 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2507 // // The prefix size indicates number of elements in the beginning | 2507 // // The prefix size indicates number of elements in the beginning |
2508 // // of the backing storage. | 2508 // // of the backing storage. |
2509 // static const int kPrefixSize = ..; | 2509 // static const int kPrefixSize = ..; |
2510 // // The Element size indicates number of elements per entry. | 2510 // // The Element size indicates number of elements per entry. |
2511 // static const int kEntrySize = ..; | 2511 // static const int kEntrySize = ..; |
2512 // }; | 2512 // }; |
2513 // The prefix size indicates an amount of memory in the | 2513 // The prefix size indicates an amount of memory in the |
2514 // beginning of the backing storage that can be used for non-element | 2514 // beginning of the backing storage that can be used for non-element |
2515 // information by subclasses. | 2515 // information by subclasses. |
2516 | 2516 |
| 2517 template<typename Key> |
| 2518 class BaseShape { |
| 2519 public: |
| 2520 static const bool UsesSeed = false; |
| 2521 static uint32_t Hash(Key key) { return 0; } |
| 2522 static uint32_t SeededHash(Key key, uint32_t seed) { |
| 2523 ASSERT(UsesSeed); |
| 2524 return Hash(key); |
| 2525 } |
| 2526 static uint32_t HashForObject(Key key, Object* object) { return 0; } |
| 2527 static uint32_t SeededHashForObject(Key key, uint32_t seed, Object* object) { |
| 2528 // Won't be called if UsesSeed isn't overridden by child class. |
| 2529 return HashForObject(key, object); |
| 2530 } |
| 2531 }; |
| 2532 |
2517 template<typename Shape, typename Key> | 2533 template<typename Shape, typename Key> |
2518 class HashTable: public FixedArray { | 2534 class HashTable: public FixedArray { |
2519 public: | 2535 public: |
| 2536 // Wrapper methods |
| 2537 inline uint32_t Hash(Key key) { |
| 2538 if (Shape::UsesSeed) { |
| 2539 return Shape::SeededHash(key, |
| 2540 GetHeap()->HashSeed()); |
| 2541 } else { |
| 2542 return Shape::Hash(key); |
| 2543 } |
| 2544 } |
| 2545 |
| 2546 inline uint32_t HashForObject(Key key, Object* object) { |
| 2547 if (Shape::UsesSeed) { |
| 2548 return Shape::SeededHashForObject(key, |
| 2549 GetHeap()->HashSeed(), object); |
| 2550 } else { |
| 2551 return Shape::HashForObject(key, object); |
| 2552 } |
| 2553 } |
| 2554 |
2520 // Returns the number of elements in the hash table. | 2555 // Returns the number of elements in the hash table. |
2521 int NumberOfElements() { | 2556 int NumberOfElements() { |
2522 return Smi::cast(get(kNumberOfElementsIndex))->value(); | 2557 return Smi::cast(get(kNumberOfElementsIndex))->value(); |
2523 } | 2558 } |
2524 | 2559 |
2525 // Returns the number of deleted elements in the hash table. | 2560 // Returns the number of deleted elements in the hash table. |
2526 int NumberOfDeletedElements() { | 2561 int NumberOfDeletedElements() { |
2527 return Smi::cast(get(kNumberOfDeletedElementsIndex))->value(); | 2562 return Smi::cast(get(kNumberOfDeletedElementsIndex))->value(); |
2528 } | 2563 } |
2529 | 2564 |
(...skipping 121 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2651 MUST_USE_RESULT MaybeObject* Rehash(HashTable* new_table, Key key); | 2686 MUST_USE_RESULT MaybeObject* Rehash(HashTable* new_table, Key key); |
2652 | 2687 |
2653 // Attempt to shrink hash table after removal of key. | 2688 // Attempt to shrink hash table after removal of key. |
2654 MUST_USE_RESULT MaybeObject* Shrink(Key key); | 2689 MUST_USE_RESULT MaybeObject* Shrink(Key key); |
2655 | 2690 |
2656 // Ensure enough space for n additional elements. | 2691 // Ensure enough space for n additional elements. |
2657 MUST_USE_RESULT MaybeObject* EnsureCapacity(int n, Key key); | 2692 MUST_USE_RESULT MaybeObject* EnsureCapacity(int n, Key key); |
2658 }; | 2693 }; |
2659 | 2694 |
2660 | 2695 |
2661 | |
2662 // HashTableKey is an abstract superclass for virtual key behavior. | 2696 // HashTableKey is an abstract superclass for virtual key behavior. |
2663 class HashTableKey { | 2697 class HashTableKey { |
2664 public: | 2698 public: |
2665 // Returns whether the other object matches this key. | 2699 // Returns whether the other object matches this key. |
2666 virtual bool IsMatch(Object* other) = 0; | 2700 virtual bool IsMatch(Object* other) = 0; |
2667 // Returns the hash value for this key. | 2701 // Returns the hash value for this key. |
2668 virtual uint32_t Hash() = 0; | 2702 virtual uint32_t Hash() = 0; |
2669 // Returns the hash value for object. | 2703 // Returns the hash value for object. |
2670 virtual uint32_t HashForObject(Object* key) = 0; | 2704 virtual uint32_t HashForObject(Object* key) = 0; |
2671 // Returns the key object for storing into the hash table. | 2705 // Returns the key object for storing into the hash table. |
2672 // If allocations fails a failure object is returned. | 2706 // If allocations fails a failure object is returned. |
2673 MUST_USE_RESULT virtual MaybeObject* AsObject() = 0; | 2707 MUST_USE_RESULT virtual MaybeObject* AsObject() = 0; |
2674 // Required. | 2708 // Required. |
2675 virtual ~HashTableKey() {} | 2709 virtual ~HashTableKey() {} |
2676 }; | 2710 }; |
2677 | 2711 |
2678 class SymbolTableShape { | 2712 |
| 2713 class SymbolTableShape : public BaseShape<HashTableKey*> { |
2679 public: | 2714 public: |
2680 static inline bool IsMatch(HashTableKey* key, Object* value) { | 2715 static inline bool IsMatch(HashTableKey* key, Object* value) { |
2681 return key->IsMatch(value); | 2716 return key->IsMatch(value); |
2682 } | 2717 } |
2683 static inline uint32_t Hash(HashTableKey* key) { | 2718 static inline uint32_t Hash(HashTableKey* key) { |
2684 return key->Hash(); | 2719 return key->Hash(); |
2685 } | 2720 } |
2686 static inline uint32_t HashForObject(HashTableKey* key, Object* object) { | 2721 static inline uint32_t HashForObject(HashTableKey* key, Object* object) { |
2687 return key->HashForObject(object); | 2722 return key->HashForObject(object); |
2688 } | 2723 } |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2727 // Casting. | 2762 // Casting. |
2728 static inline SymbolTable* cast(Object* obj); | 2763 static inline SymbolTable* cast(Object* obj); |
2729 | 2764 |
2730 private: | 2765 private: |
2731 MUST_USE_RESULT MaybeObject* LookupKey(HashTableKey* key, Object** s); | 2766 MUST_USE_RESULT MaybeObject* LookupKey(HashTableKey* key, Object** s); |
2732 | 2767 |
2733 DISALLOW_IMPLICIT_CONSTRUCTORS(SymbolTable); | 2768 DISALLOW_IMPLICIT_CONSTRUCTORS(SymbolTable); |
2734 }; | 2769 }; |
2735 | 2770 |
2736 | 2771 |
2737 class MapCacheShape { | 2772 class MapCacheShape : public BaseShape<HashTableKey*> { |
2738 public: | 2773 public: |
2739 static inline bool IsMatch(HashTableKey* key, Object* value) { | 2774 static inline bool IsMatch(HashTableKey* key, Object* value) { |
2740 return key->IsMatch(value); | 2775 return key->IsMatch(value); |
2741 } | 2776 } |
2742 static inline uint32_t Hash(HashTableKey* key) { | 2777 static inline uint32_t Hash(HashTableKey* key) { |
2743 return key->Hash(); | 2778 return key->Hash(); |
2744 } | 2779 } |
2745 | 2780 |
2746 static inline uint32_t HashForObject(HashTableKey* key, Object* object) { | 2781 static inline uint32_t HashForObject(HashTableKey* key, Object* object) { |
2747 return key->HashForObject(object); | 2782 return key->HashForObject(object); |
(...skipping 135 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2883 uint32_t hash); | 2918 uint32_t hash); |
2884 | 2919 |
2885 // Generate new enumeration indices to avoid enumeration index overflow. | 2920 // Generate new enumeration indices to avoid enumeration index overflow. |
2886 MUST_USE_RESULT MaybeObject* GenerateNewEnumerationIndices(); | 2921 MUST_USE_RESULT MaybeObject* GenerateNewEnumerationIndices(); |
2887 static const int kMaxNumberKeyIndex = | 2922 static const int kMaxNumberKeyIndex = |
2888 HashTable<Shape, Key>::kPrefixStartIndex; | 2923 HashTable<Shape, Key>::kPrefixStartIndex; |
2889 static const int kNextEnumerationIndexIndex = kMaxNumberKeyIndex + 1; | 2924 static const int kNextEnumerationIndexIndex = kMaxNumberKeyIndex + 1; |
2890 }; | 2925 }; |
2891 | 2926 |
2892 | 2927 |
2893 class StringDictionaryShape { | 2928 class StringDictionaryShape : public BaseShape<String*> { |
2894 public: | 2929 public: |
2895 static inline bool IsMatch(String* key, Object* other); | 2930 static inline bool IsMatch(String* key, Object* other); |
2896 static inline uint32_t Hash(String* key); | 2931 static inline uint32_t Hash(String* key); |
2897 static inline uint32_t HashForObject(String* key, Object* object); | 2932 static inline uint32_t HashForObject(String* key, Object* object); |
2898 MUST_USE_RESULT static inline MaybeObject* AsObject(String* key); | 2933 MUST_USE_RESULT static inline MaybeObject* AsObject(String* key); |
2899 static const int kPrefixSize = 2; | 2934 static const int kPrefixSize = 2; |
2900 static const int kEntrySize = 3; | 2935 static const int kEntrySize = 3; |
2901 static const bool kIsEnumerable = true; | 2936 static const bool kIsEnumerable = true; |
2902 }; | 2937 }; |
2903 | 2938 |
(...skipping 12 matching lines...) Expand all Loading... |
2916 MUST_USE_RESULT MaybeObject* TransformPropertiesToFastFor( | 2951 MUST_USE_RESULT MaybeObject* TransformPropertiesToFastFor( |
2917 JSObject* obj, | 2952 JSObject* obj, |
2918 int unused_property_fields); | 2953 int unused_property_fields); |
2919 | 2954 |
2920 // Find entry for key otherwise return kNotFound. Optimzed version of | 2955 // Find entry for key otherwise return kNotFound. Optimzed version of |
2921 // HashTable::FindEntry. | 2956 // HashTable::FindEntry. |
2922 int FindEntry(String* key); | 2957 int FindEntry(String* key); |
2923 }; | 2958 }; |
2924 | 2959 |
2925 | 2960 |
2926 class NumberDictionaryShape { | 2961 class NumberDictionaryShape : public BaseShape<uint32_t> { |
2927 public: | 2962 public: |
| 2963 static const bool UsesSeed = true; |
| 2964 |
2928 static inline bool IsMatch(uint32_t key, Object* other); | 2965 static inline bool IsMatch(uint32_t key, Object* other); |
2929 static inline uint32_t Hash(uint32_t key); | 2966 static inline uint32_t Hash(uint32_t key); |
| 2967 static inline uint32_t SeededHash(uint32_t key, uint32_t seed); |
2930 static inline uint32_t HashForObject(uint32_t key, Object* object); | 2968 static inline uint32_t HashForObject(uint32_t key, Object* object); |
| 2969 static inline uint32_t SeededHashForObject(uint32_t key, |
| 2970 uint32_t seed, |
| 2971 Object* object); |
2931 MUST_USE_RESULT static inline MaybeObject* AsObject(uint32_t key); | 2972 MUST_USE_RESULT static inline MaybeObject* AsObject(uint32_t key); |
2932 static const int kPrefixSize = 2; | 2973 static const int kPrefixSize = 2; |
2933 static const int kEntrySize = 3; | 2974 static const int kEntrySize = 3; |
2934 static const bool kIsEnumerable = false; | 2975 static const bool kIsEnumerable = false; |
2935 }; | 2976 }; |
2936 | 2977 |
2937 | 2978 |
2938 class NumberDictionary: public Dictionary<NumberDictionaryShape, uint32_t> { | 2979 class NumberDictionary: public Dictionary<NumberDictionaryShape, uint32_t> { |
2939 public: | 2980 public: |
2940 static NumberDictionary* cast(Object* obj) { | 2981 static NumberDictionary* cast(Object* obj) { |
(...skipping 30 matching lines...) Expand all Loading... |
2971 // Remove all entries were key is a number and (from <= key && key < to). | 3012 // Remove all entries were key is a number and (from <= key && key < to). |
2972 void RemoveNumberEntries(uint32_t from, uint32_t to); | 3013 void RemoveNumberEntries(uint32_t from, uint32_t to); |
2973 | 3014 |
2974 // Bit masks. | 3015 // Bit masks. |
2975 static const int kRequiresSlowElementsMask = 1; | 3016 static const int kRequiresSlowElementsMask = 1; |
2976 static const int kRequiresSlowElementsTagSize = 1; | 3017 static const int kRequiresSlowElementsTagSize = 1; |
2977 static const uint32_t kRequiresSlowElementsLimit = (1 << 29) - 1; | 3018 static const uint32_t kRequiresSlowElementsLimit = (1 << 29) - 1; |
2978 }; | 3019 }; |
2979 | 3020 |
2980 | 3021 |
2981 class ObjectHashTableShape { | 3022 class ObjectHashTableShape : public BaseShape<Object*> { |
2982 public: | 3023 public: |
2983 static inline bool IsMatch(JSObject* key, Object* other); | 3024 static inline bool IsMatch(JSObject* key, Object* other); |
2984 static inline uint32_t Hash(JSObject* key); | 3025 static inline uint32_t Hash(JSObject* key); |
2985 static inline uint32_t HashForObject(JSObject* key, Object* object); | 3026 static inline uint32_t HashForObject(JSObject* key, Object* object); |
2986 MUST_USE_RESULT static inline MaybeObject* AsObject(JSObject* key); | 3027 MUST_USE_RESULT static inline MaybeObject* AsObject(JSObject* key); |
2987 static const int kPrefixSize = 0; | 3028 static const int kPrefixSize = 0; |
2988 static const int kEntrySize = 2; | 3029 static const int kEntrySize = 2; |
2989 }; | 3030 }; |
2990 | 3031 |
2991 | 3032 |
(...skipping 2544 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
5536 // object is in the saved code field. | 5577 // object is in the saved code field. |
5537 static const int kCompilationErrorValue = -2; | 5578 static const int kCompilationErrorValue = -2; |
5538 | 5579 |
5539 // When we store the sweep generation at which we moved the code from the | 5580 // When we store the sweep generation at which we moved the code from the |
5540 // code index to the saved code index we mask it of to be in the [0:255] | 5581 // code index to the saved code index we mask it of to be in the [0:255] |
5541 // range. | 5582 // range. |
5542 static const int kCodeAgeMask = 0xff; | 5583 static const int kCodeAgeMask = 0xff; |
5543 }; | 5584 }; |
5544 | 5585 |
5545 | 5586 |
5546 class CompilationCacheShape { | 5587 class CompilationCacheShape : public BaseShape<HashTableKey*> { |
5547 public: | 5588 public: |
5548 static inline bool IsMatch(HashTableKey* key, Object* value) { | 5589 static inline bool IsMatch(HashTableKey* key, Object* value) { |
5549 return key->IsMatch(value); | 5590 return key->IsMatch(value); |
5550 } | 5591 } |
5551 | 5592 |
5552 static inline uint32_t Hash(HashTableKey* key) { | 5593 static inline uint32_t Hash(HashTableKey* key) { |
5553 return key->Hash(); | 5594 return key->Hash(); |
5554 } | 5595 } |
5555 | 5596 |
5556 static inline uint32_t HashForObject(HashTableKey* key, Object* object) { | 5597 static inline uint32_t HashForObject(HashTableKey* key, Object* object) { |
(...skipping 79 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
5636 // Code cache layout of the default cache. Elements are alternating name and | 5677 // Code cache layout of the default cache. Elements are alternating name and |
5637 // code objects for non normal load/store/call IC's. | 5678 // code objects for non normal load/store/call IC's. |
5638 static const int kCodeCacheEntrySize = 2; | 5679 static const int kCodeCacheEntrySize = 2; |
5639 static const int kCodeCacheEntryNameOffset = 0; | 5680 static const int kCodeCacheEntryNameOffset = 0; |
5640 static const int kCodeCacheEntryCodeOffset = 1; | 5681 static const int kCodeCacheEntryCodeOffset = 1; |
5641 | 5682 |
5642 DISALLOW_IMPLICIT_CONSTRUCTORS(CodeCache); | 5683 DISALLOW_IMPLICIT_CONSTRUCTORS(CodeCache); |
5643 }; | 5684 }; |
5644 | 5685 |
5645 | 5686 |
5646 class CodeCacheHashTableShape { | 5687 class CodeCacheHashTableShape : public BaseShape<HashTableKey*> { |
5647 public: | 5688 public: |
5648 static inline bool IsMatch(HashTableKey* key, Object* value) { | 5689 static inline bool IsMatch(HashTableKey* key, Object* value) { |
5649 return key->IsMatch(value); | 5690 return key->IsMatch(value); |
5650 } | 5691 } |
5651 | 5692 |
5652 static inline uint32_t Hash(HashTableKey* key) { | 5693 static inline uint32_t Hash(HashTableKey* key) { |
5653 return key->Hash(); | 5694 return key->Hash(); |
5654 } | 5695 } |
5655 | 5696 |
5656 static inline uint32_t HashForObject(HashTableKey* key, Object* object) { | 5697 static inline uint32_t HashForObject(HashTableKey* key, Object* object) { |
(...skipping 1841 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
7498 } else { | 7539 } else { |
7499 value &= ~(1 << bit_position); | 7540 value &= ~(1 << bit_position); |
7500 } | 7541 } |
7501 return value; | 7542 return value; |
7502 } | 7543 } |
7503 }; | 7544 }; |
7504 | 7545 |
7505 } } // namespace v8::internal | 7546 } } // namespace v8::internal |
7506 | 7547 |
7507 #endif // V8_OBJECTS_H_ | 7548 #endif // V8_OBJECTS_H_ |
OLD | NEW |