OLD | NEW |
---|---|
1 // Copyright 2006-2008 Google Inc. All Rights Reserved. | 1 // Copyright 2006-2008 Google Inc. 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 596 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
607 inline bool IsCode(); | 607 inline bool IsCode(); |
608 inline bool IsOddball(); | 608 inline bool IsOddball(); |
609 inline bool IsSharedFunctionInfo(); | 609 inline bool IsSharedFunctionInfo(); |
610 inline bool IsJSValue(); | 610 inline bool IsJSValue(); |
611 inline bool IsProxy(); | 611 inline bool IsProxy(); |
612 inline bool IsBoolean(); | 612 inline bool IsBoolean(); |
613 inline bool IsJSArray(); | 613 inline bool IsJSArray(); |
614 inline bool IsHashTable(); | 614 inline bool IsHashTable(); |
615 inline bool IsDictionary(); | 615 inline bool IsDictionary(); |
616 inline bool IsSymbolTable(); | 616 inline bool IsSymbolTable(); |
617 inline bool IsEvalCache(); | |
617 inline bool IsPrimitive(); | 618 inline bool IsPrimitive(); |
618 inline bool IsGlobalObject(); | 619 inline bool IsGlobalObject(); |
619 inline bool IsJSGlobalObject(); | 620 inline bool IsJSGlobalObject(); |
620 inline bool IsJSBuiltinsObject(); | 621 inline bool IsJSBuiltinsObject(); |
621 inline bool IsUndetectableObject(); | 622 inline bool IsUndetectableObject(); |
622 inline bool IsAccessCheckNeeded(); | 623 inline bool IsAccessCheckNeeded(); |
623 | 624 |
624 // Returns true if this object is an instance of the specified | 625 // Returns true if this object is an instance of the specified |
625 // function template. | 626 // function template. |
626 bool IsInstanceOf(FunctionTemplateInfo* type); | 627 bool IsInstanceOf(FunctionTemplateInfo* type); |
(...skipping 1047 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
1674 // encountered and stops when unused elements are encountered. | 1675 // encountered and stops when unused elements are encountered. |
1675 // | 1676 // |
1676 // - Elements with key == undefined have not been used yet. | 1677 // - Elements with key == undefined have not been used yet. |
1677 // - Elements with key == null have been deleted. | 1678 // - Elements with key == null have been deleted. |
1678 // | 1679 // |
1679 // The hash table class is parameterized with a prefix size and with | 1680 // The hash table class is parameterized with a prefix size and with |
1680 // the size, including the key size, of the elements held in the hash | 1681 // the size, including the key size, of the elements held in the hash |
1681 // table. The prefix size indicates an amount of memory in the | 1682 // table. The prefix size indicates an amount of memory in the |
1682 // beginning of the backing storage that can be used for non-element | 1683 // beginning of the backing storage that can be used for non-element |
1683 // information by subclasses. | 1684 // information by subclasses. |
1685 | |
1686 // HashTableKey is an abstract superclass keys. | |
1687 class HashTableKey { | |
1688 public: | |
1689 // Returns whether the other object matches this key. | |
1690 virtual bool IsMatch(Object* other) = 0; | |
1691 typedef uint32_t (*HashFunction)(Object* obj); | |
1692 // Returns the hash function used for this key. | |
1693 virtual HashFunction GetHashFunction() = 0; | |
1694 // Returns the hash value for this key. | |
1695 virtual uint32_t Hash() = 0; | |
1696 // Returns the key object for storing into the dictionary. | |
1697 // If allocations fails a failure object is returned. | |
1698 virtual Object* GetObject() = 0; | |
1699 virtual bool IsStringKey() = 0; | |
1700 // Required. | |
1701 virtual ~HashTableKey() {} | |
1702 }; | |
1703 | |
1704 | |
1684 template<int prefix_size, int element_size> | 1705 template<int prefix_size, int element_size> |
1685 class HashTable: public FixedArray { | 1706 class HashTable: public FixedArray { |
1686 public: | 1707 public: |
1687 // Returns the number of elements in the dictionary. | 1708 // Returns the number of elements in the dictionary. |
1688 int NumberOfElements() { | 1709 int NumberOfElements() { |
1689 return Smi::cast(get(kNumberOfElementsIndex))->value(); | 1710 return Smi::cast(get(kNumberOfElementsIndex))->value(); |
1690 } | 1711 } |
1691 | 1712 |
1692 // Returns the capacity of the dictionary. | 1713 // Returns the capacity of the dictionary. |
1693 int Capacity() { | 1714 int Capacity() { |
(...skipping 21 matching lines...) Expand all Loading... | |
1715 return !k->IsNull() && !k->IsUndefined(); | 1736 return !k->IsNull() && !k->IsUndefined(); |
1716 } | 1737 } |
1717 | 1738 |
1718 // Garbage collection support. | 1739 // Garbage collection support. |
1719 void IteratePrefix(ObjectVisitor* visitor); | 1740 void IteratePrefix(ObjectVisitor* visitor); |
1720 void IterateElements(ObjectVisitor* visitor); | 1741 void IterateElements(ObjectVisitor* visitor); |
1721 | 1742 |
1722 // Casting. | 1743 // Casting. |
1723 static inline HashTable* cast(Object* obj); | 1744 static inline HashTable* cast(Object* obj); |
1724 | 1745 |
1725 // Key is an abstract superclass keys. | |
1726 class Key { | |
1727 public: | |
1728 // Returns whether the other object matches this key. | |
1729 virtual bool IsMatch(Object* other) = 0; | |
1730 typedef uint32_t (*HashFunction)(Object* obj); | |
1731 // Returns the hash function used for this key. | |
1732 virtual HashFunction GetHashFunction() = 0; | |
1733 // Returns the hash value for this key. | |
1734 virtual uint32_t Hash() = 0; | |
1735 // Returns the key object for storing into the dictionary. | |
1736 // If allocations fails a failure object is returned. | |
1737 virtual Object* GetObject() = 0; | |
1738 virtual bool IsStringKey() = 0; | |
1739 // Required. | |
1740 virtual ~Key() {} | |
1741 }; | |
1742 | |
1743 // Compute the probe offset (quadratic probing). | 1746 // Compute the probe offset (quadratic probing). |
1744 INLINE(static uint32_t GetProbeOffset(uint32_t n)) { | 1747 INLINE(static uint32_t GetProbeOffset(uint32_t n)) { |
1745 return (n + n * n) >> 1; | 1748 return (n + n * n) >> 1; |
1746 } | 1749 } |
1747 | 1750 |
1748 static const int kNumberOfElementsIndex = 0; | 1751 static const int kNumberOfElementsIndex = 0; |
1749 static const int kCapacityIndex = 1; | 1752 static const int kCapacityIndex = 1; |
1750 static const int kPrefixStartIndex = 2; | 1753 static const int kPrefixStartIndex = 2; |
1751 static const int kElementsStartIndex = kPrefixStartIndex + prefix_size; | 1754 static const int kElementsStartIndex = kPrefixStartIndex + prefix_size; |
1752 static const int kElementSize = element_size; | 1755 static const int kElementSize = element_size; |
1753 static const int kElementsStartOffset = | 1756 static const int kElementsStartOffset = |
1754 kHeaderSize + kElementsStartIndex * kPointerSize; | 1757 kHeaderSize + kElementsStartIndex * kPointerSize; |
1755 | 1758 |
1756 protected: | 1759 protected: |
1757 // Find entry for key otherwise return -1. | 1760 // Find entry for key otherwise return -1. |
1758 int FindEntry(Key* key); | 1761 int FindEntry(HashTableKey* key); |
1759 | 1762 |
1760 // Find the entry at which to insert element with the given key that | 1763 // Find the entry at which to insert element with the given key that |
1761 // has the given hash value. | 1764 // has the given hash value. |
1762 uint32_t FindInsertionEntry(Object* key, uint32_t hash); | 1765 uint32_t FindInsertionEntry(Object* key, uint32_t hash); |
1763 | 1766 |
1764 // Returns the index for an entry (of the key) | 1767 // Returns the index for an entry (of the key) |
1765 static inline int EntryToIndex(int entry) { | 1768 static inline int EntryToIndex(int entry) { |
1766 return (entry * kElementSize) + kElementsStartIndex; | 1769 return (entry * kElementSize) + kElementsStartIndex; |
1767 } | 1770 } |
1768 | 1771 |
(...skipping 12 matching lines...) Expand all Loading... | |
1781 } | 1784 } |
1782 | 1785 |
1783 | 1786 |
1784 // Returns probe entry. | 1787 // Returns probe entry. |
1785 static uint32_t GetProbe(uint32_t hash, uint32_t number, uint32_t size) { | 1788 static uint32_t GetProbe(uint32_t hash, uint32_t number, uint32_t size) { |
1786 ASSERT(IsPowerOf2(size)); | 1789 ASSERT(IsPowerOf2(size)); |
1787 return (hash + GetProbeOffset(number)) & (size - 1); | 1790 return (hash + GetProbeOffset(number)) & (size - 1); |
1788 } | 1791 } |
1789 | 1792 |
1790 // Ensure enough space for n additional elements. | 1793 // Ensure enough space for n additional elements. |
1791 Object* EnsureCapacity(int n, Key* key); | 1794 Object* EnsureCapacity(int n, HashTableKey* key); |
1792 }; | 1795 }; |
1793 | 1796 |
1794 | 1797 |
1795 // SymbolTable. | 1798 // SymbolTable. |
1796 // | 1799 // |
1797 // No special elements in the prefix and the element size is 1 | 1800 // No special elements in the prefix and the element size is 1 |
1798 // because only the symbol itself (the key) needs to be stored. | 1801 // because only the symbol itself (the key) needs to be stored. |
1799 class SymbolTable: public HashTable<0, 1> { | 1802 class SymbolTable: public HashTable<0, 1> { |
1800 public: | 1803 public: |
1801 // Find symbol in the symbol table. If it is not there yet, it is | 1804 // Find symbol in the symbol table. If it is not there yet, it is |
1802 // added. The return value is the symbol table which might have | 1805 // added. The return value is the symbol table which might have |
1803 // been enlarged. If the return value is not a failure, the symbol | 1806 // been enlarged. If the return value is not a failure, the symbol |
1804 // pointer *s is set to the symbol found. | 1807 // pointer *s is set to the symbol found. |
1805 Object* LookupSymbol(Vector<const char> str, Object** s); | 1808 Object* LookupSymbol(Vector<const char> str, Object** s); |
1806 Object* LookupString(String* key, Object** s); | 1809 Object* LookupString(String* key, Object** s); |
1807 | 1810 |
1808 // Casting. | 1811 // Casting. |
1809 static inline SymbolTable* cast(Object* obj); | 1812 static inline SymbolTable* cast(Object* obj); |
1810 | 1813 |
1811 private: | 1814 private: |
1812 Object* LookupKey(Key* key, Object** s); | 1815 Object* LookupKey(HashTableKey* key, Object** s); |
1813 class Utf8Key; // Key based on utf8 string. | |
1814 class StringKey; // Key based on String*. | |
1815 | 1816 |
1816 DISALLOW_IMPLICIT_CONSTRUCTORS(SymbolTable); | 1817 DISALLOW_IMPLICIT_CONSTRUCTORS(SymbolTable); |
1817 }; | 1818 }; |
1818 | 1819 |
1819 | 1820 |
1821 // EvalCache for caching eval'ed string and function. | |
Kasper Lund
2008/09/05 09:16:29
Rename to CompilationCacheTable?
Feng Qian
2008/09/09 03:42:50
Done.
| |
1822 // | |
1823 // The cache is cleaned up during a mark-compact GC. | |
1824 class EvalCache: public HashTable<0, 2> { | |
1825 public: | |
1826 // Find cached value for a string key, otherwise return null. | |
1827 Object* Lookup(String* src); | |
1828 Object* Put(String* src, Object* value); | |
1829 | |
1830 static inline EvalCache* cast(Object* obj); | |
1831 | |
1832 private: | |
1833 DISALLOW_IMPLICIT_CONSTRUCTORS(EvalCache); | |
1834 }; | |
1835 | |
1836 | |
1820 // Dictionary for keeping properties and elements in slow case. | 1837 // Dictionary for keeping properties and elements in slow case. |
1821 // | 1838 // |
1822 // One element in the prefix is used for storing non-element | 1839 // One element in the prefix is used for storing non-element |
1823 // information about the dictionary. | 1840 // information about the dictionary. |
1824 // | 1841 // |
1825 // The rest of the array embeds triples of (key, value, details). | 1842 // The rest of the array embeds triples of (key, value, details). |
1826 // if key == undefined the triple is empty. | 1843 // if key == undefined the triple is empty. |
1827 // if key == null the triple has been deleted. | 1844 // if key == null the triple has been deleted. |
1828 // otherwise key contains the name of a property. | 1845 // otherwise key contains the name of a property. |
1829 class DictionaryBase: public HashTable<2, 3> {}; | 1846 class DictionaryBase: public HashTable<2, 3> {}; |
(...skipping 87 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
1917 } | 1934 } |
1918 | 1935 |
1919 int NextEnumerationIndex() { | 1936 int NextEnumerationIndex() { |
1920 return Smi::cast(get(kNextEnumnerationIndexIndex))->value(); | 1937 return Smi::cast(get(kNextEnumnerationIndexIndex))->value(); |
1921 } | 1938 } |
1922 | 1939 |
1923 // Returns a new array for dictionary usage. Might return Failure. | 1940 // Returns a new array for dictionary usage. Might return Failure. |
1924 static Object* Allocate(int at_least_space_for); | 1941 static Object* Allocate(int at_least_space_for); |
1925 | 1942 |
1926 // Ensure enough space for n additional elements. | 1943 // Ensure enough space for n additional elements. |
1927 Object* EnsureCapacity(int n, Key* key); | 1944 Object* EnsureCapacity(int n, HashTableKey* key); |
1928 | 1945 |
1929 #ifdef DEBUG | 1946 #ifdef DEBUG |
1930 void Print(); | 1947 void Print(); |
1931 #endif | 1948 #endif |
1932 // Returns the key (slow). | 1949 // Returns the key (slow). |
1933 Object* SlowReverseLookup(Object* value); | 1950 Object* SlowReverseLookup(Object* value); |
1934 | 1951 |
1935 // Bit masks. | 1952 // Bit masks. |
1936 static const int kRequiresSlowElementsMask = 1; | 1953 static const int kRequiresSlowElementsMask = 1; |
1937 static const int kRequiresSlowElementsTagSize = 1; | 1954 static const int kRequiresSlowElementsTagSize = 1; |
1938 static const uint32_t kRequiresSlowElementsLimit = (1 << 29) - 1; | 1955 static const uint32_t kRequiresSlowElementsLimit = (1 << 29) - 1; |
1939 | 1956 |
1940 private: | 1957 private: |
1941 // Generic at put operation. | 1958 // Generic at put operation. |
1942 Object* AtPut(Key* key, Object* value); | 1959 Object* AtPut(HashTableKey* key, Object* value); |
1943 | 1960 |
1944 Object* Add(Key* key, Object* value, PropertyDetails details); | 1961 Object* Add(HashTableKey* key, Object* value, PropertyDetails details); |
1945 | 1962 |
1946 // Add entry to dictionary. | 1963 // Add entry to dictionary. |
1947 void AddEntry(Object* key, | 1964 void AddEntry(Object* key, |
1948 Object* value, | 1965 Object* value, |
1949 PropertyDetails details, | 1966 PropertyDetails details, |
1950 uint32_t hash); | 1967 uint32_t hash); |
1951 | 1968 |
1952 // Sets the entry to (key, value) pair. | 1969 // Sets the entry to (key, value) pair. |
1953 inline void SetEntry(int entry, | 1970 inline void SetEntry(int entry, |
1954 Object* key, | 1971 Object* key, |
1955 Object* value, | 1972 Object* value, |
1956 PropertyDetails details); | 1973 PropertyDetails details); |
1957 | 1974 |
1958 void UpdateMaxNumberKey(uint32_t key); | 1975 void UpdateMaxNumberKey(uint32_t key); |
1959 | 1976 |
1960 // Generate new enumneration indices to avoid enumeration insdex overflow. | 1977 // Generate new enumneration indices to avoid enumeration insdex overflow. |
1961 Object* GenerateNewEnumerationIndices(); | 1978 Object* GenerateNewEnumerationIndices(); |
1962 | 1979 |
1963 static const int kMaxNumberKeyIndex = kPrefixStartIndex; | 1980 static const int kMaxNumberKeyIndex = kPrefixStartIndex; |
1964 static const int kNextEnumnerationIndexIndex = kMaxNumberKeyIndex + 1; | 1981 static const int kNextEnumnerationIndexIndex = kMaxNumberKeyIndex + 1; |
1965 | 1982 |
1966 class NumberKey; // Key containing uint32_t. | |
1967 class StringKey; // Key containing String*. | |
1968 | |
1969 DISALLOW_IMPLICIT_CONSTRUCTORS(Dictionary); | 1983 DISALLOW_IMPLICIT_CONSTRUCTORS(Dictionary); |
1970 }; | 1984 }; |
1971 | 1985 |
1972 | 1986 |
1973 // ByteArray represents fixed sized byte arrays. Used by the outside world, | 1987 // ByteArray represents fixed sized byte arrays. Used by the outside world, |
1974 // such as PCRE, and also by the memory allocator and garbage collector to | 1988 // such as PCRE, and also by the memory allocator and garbage collector to |
1975 // fill in free blocks in the heap. | 1989 // fill in free blocks in the heap. |
1976 class ByteArray: public Array { | 1990 class ByteArray: public Array { |
1977 public: | 1991 public: |
1978 // Setter and getter. | 1992 // Setter and getter. |
(...skipping 1855 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
3834 } else { | 3848 } else { |
3835 value &= ~(1 << bit_position); | 3849 value &= ~(1 << bit_position); |
3836 } | 3850 } |
3837 return value; | 3851 return value; |
3838 } | 3852 } |
3839 }; | 3853 }; |
3840 | 3854 |
3841 } } // namespace v8::internal | 3855 } } // namespace v8::internal |
3842 | 3856 |
3843 #endif // V8_OBJECTS_H_ | 3857 #endif // V8_OBJECTS_H_ |
OLD | NEW |