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 1857 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1868 // information by subclasses. | 1868 // information by subclasses. |
1869 | 1869 |
1870 template<typename Shape, typename Key> | 1870 template<typename Shape, typename Key> |
1871 class HashTable: public FixedArray { | 1871 class HashTable: public FixedArray { |
1872 public: | 1872 public: |
1873 // Returns the number of elements in the hash table. | 1873 // Returns the number of elements in the hash table. |
1874 int NumberOfElements() { | 1874 int NumberOfElements() { |
1875 return Smi::cast(get(kNumberOfElementsIndex))->value(); | 1875 return Smi::cast(get(kNumberOfElementsIndex))->value(); |
1876 } | 1876 } |
1877 | 1877 |
| 1878 // Returns the number of deleted elements in the hash table. |
| 1879 int NumberOfDeletedElements() { |
| 1880 return Smi::cast(get(kNumberOfDeletedElementsIndex))->value(); |
| 1881 } |
| 1882 |
1878 // Returns the capacity of the hash table. | 1883 // Returns the capacity of the hash table. |
1879 int Capacity() { | 1884 int Capacity() { |
1880 return Smi::cast(get(kCapacityIndex))->value(); | 1885 return Smi::cast(get(kCapacityIndex))->value(); |
1881 } | 1886 } |
1882 | 1887 |
1883 // ElementAdded should be called whenever an element is added to a | 1888 // ElementAdded should be called whenever an element is added to a |
1884 // hash table. | 1889 // hash table. |
1885 void ElementAdded() { SetNumberOfElements(NumberOfElements() + 1); } | 1890 void ElementAdded() { SetNumberOfElements(NumberOfElements() + 1); } |
1886 | 1891 |
1887 // ElementRemoved should be called whenever an element is removed from | 1892 // ElementRemoved should be called whenever an element is removed from |
1888 // a hash table. | 1893 // a hash table. |
1889 void ElementRemoved() { SetNumberOfElements(NumberOfElements() - 1); } | 1894 void ElementRemoved() { |
1890 void ElementsRemoved(int n) { SetNumberOfElements(NumberOfElements() - n); } | 1895 SetNumberOfElements(NumberOfElements() - 1); |
| 1896 SetNumberOfDeletedElements(NumberOfDeletedElements() + 1); |
| 1897 } |
| 1898 void ElementsRemoved(int n) { |
| 1899 SetNumberOfElements(NumberOfElements() - n); |
| 1900 SetNumberOfDeletedElements(NumberOfDeletedElements() + n); |
| 1901 } |
1891 | 1902 |
1892 // Returns a new HashTable object. Might return Failure. | 1903 // Returns a new HashTable object. Might return Failure. |
1893 static Object* Allocate(int at_least_space_for); | 1904 static Object* Allocate(int at_least_space_for); |
1894 | 1905 |
1895 // Returns the key at entry. | 1906 // Returns the key at entry. |
1896 Object* KeyAt(int entry) { return get(EntryToIndex(entry)); } | 1907 Object* KeyAt(int entry) { return get(EntryToIndex(entry)); } |
1897 | 1908 |
1898 // Tells whether k is a real key. Null and undefined are not allowed | 1909 // Tells whether k is a real key. Null and undefined are not allowed |
1899 // as keys and can be used to indicate missing or deleted elements. | 1910 // as keys and can be used to indicate missing or deleted elements. |
1900 bool IsKey(Object* k) { | 1911 bool IsKey(Object* k) { |
1901 return !k->IsNull() && !k->IsUndefined(); | 1912 return !k->IsNull() && !k->IsUndefined(); |
1902 } | 1913 } |
1903 | 1914 |
1904 // Garbage collection support. | 1915 // Garbage collection support. |
1905 void IteratePrefix(ObjectVisitor* visitor); | 1916 void IteratePrefix(ObjectVisitor* visitor); |
1906 void IterateElements(ObjectVisitor* visitor); | 1917 void IterateElements(ObjectVisitor* visitor); |
1907 | 1918 |
1908 // Casting. | 1919 // Casting. |
1909 static inline HashTable* cast(Object* obj); | 1920 static inline HashTable* cast(Object* obj); |
1910 | 1921 |
1911 // Compute the probe offset (quadratic probing). | 1922 // Compute the probe offset (quadratic probing). |
1912 INLINE(static uint32_t GetProbeOffset(uint32_t n)) { | 1923 INLINE(static uint32_t GetProbeOffset(uint32_t n)) { |
1913 return (n + n * n) >> 1; | 1924 return (n + n * n) >> 1; |
1914 } | 1925 } |
1915 | 1926 |
1916 static const int kNumberOfElementsIndex = 0; | 1927 static const int kNumberOfElementsIndex = 0; |
1917 static const int kCapacityIndex = 1; | 1928 static const int kNumberOfDeletedElementsIndex = 1; |
1918 static const int kPrefixStartIndex = 2; | 1929 static const int kCapacityIndex = 2; |
1919 static const int kElementsStartIndex = | 1930 static const int kPrefixStartIndex = 3; |
| 1931 static const int kElementsStartIndex = |
1920 kPrefixStartIndex + Shape::kPrefixSize; | 1932 kPrefixStartIndex + Shape::kPrefixSize; |
1921 static const int kEntrySize = Shape::kEntrySize; | 1933 static const int kEntrySize = Shape::kEntrySize; |
1922 static const int kElementsStartOffset = | 1934 static const int kElementsStartOffset = |
1923 kHeaderSize + kElementsStartIndex * kPointerSize; | 1935 kHeaderSize + kElementsStartIndex * kPointerSize; |
1924 | 1936 |
1925 // Constant used for denoting a absent entry. | 1937 // Constant used for denoting a absent entry. |
1926 static const int kNotFound = -1; | 1938 static const int kNotFound = -1; |
1927 | 1939 |
1928 // Find entry for key otherwise return -1. | 1940 // Find entry for key otherwise return -1. |
1929 int FindEntry(Key key); | 1941 int FindEntry(Key key); |
1930 | 1942 |
1931 protected: | 1943 protected: |
1932 | 1944 |
1933 // Find the entry at which to insert element with the given key that | 1945 // Find the entry at which to insert element with the given key that |
1934 // has the given hash value. | 1946 // has the given hash value. |
1935 uint32_t FindInsertionEntry(uint32_t hash); | 1947 uint32_t FindInsertionEntry(uint32_t hash); |
1936 | 1948 |
1937 // Returns the index for an entry (of the key) | 1949 // Returns the index for an entry (of the key) |
1938 static inline int EntryToIndex(int entry) { | 1950 static inline int EntryToIndex(int entry) { |
1939 return (entry * kEntrySize) + kElementsStartIndex; | 1951 return (entry * kEntrySize) + kElementsStartIndex; |
1940 } | 1952 } |
1941 | 1953 |
1942 // Update the number of elements in the hash table. | 1954 // Update the number of elements in the hash table. |
1943 void SetNumberOfElements(int nof) { | 1955 void SetNumberOfElements(int nof) { |
1944 fast_set(this, kNumberOfElementsIndex, Smi::FromInt(nof)); | 1956 fast_set(this, kNumberOfElementsIndex, Smi::FromInt(nof)); |
1945 } | 1957 } |
1946 | 1958 |
| 1959 // Update the number of deleted elements in the hash table. |
| 1960 void SetNumberOfDeletedElements(int nod) { |
| 1961 fast_set(this, kNumberOfDeletedElementsIndex, Smi::FromInt(nod)); |
| 1962 } |
| 1963 |
1947 // Sets the capacity of the hash table. | 1964 // Sets the capacity of the hash table. |
1948 void SetCapacity(int capacity) { | 1965 void SetCapacity(int capacity) { |
1949 // To scale a computed hash code to fit within the hash table, we | 1966 // To scale a computed hash code to fit within the hash table, we |
1950 // use bit-wise AND with a mask, so the capacity must be positive | 1967 // use bit-wise AND with a mask, so the capacity must be positive |
1951 // and non-zero. | 1968 // and non-zero. |
1952 ASSERT(capacity > 0); | 1969 ASSERT(capacity > 0); |
1953 fast_set(this, kCapacityIndex, Smi::FromInt(capacity)); | 1970 fast_set(this, kCapacityIndex, Smi::FromInt(capacity)); |
1954 } | 1971 } |
1955 | 1972 |
1956 | 1973 |
(...skipping 2915 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
4872 } else { | 4889 } else { |
4873 value &= ~(1 << bit_position); | 4890 value &= ~(1 << bit_position); |
4874 } | 4891 } |
4875 return value; | 4892 return value; |
4876 } | 4893 } |
4877 }; | 4894 }; |
4878 | 4895 |
4879 } } // namespace v8::internal | 4896 } } // namespace v8::internal |
4880 | 4897 |
4881 #endif // V8_OBJECTS_H_ | 4898 #endif // V8_OBJECTS_H_ |
OLD | NEW |