0fe6b36ea29ede09a799b4dceff17983098de611
[WebKit.git] / JavaScriptCore / kjs / PropertyMap.h
1 /*
2  *  Copyright (C) 2004, 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
3  *
4  *  This library is free software; you can redistribute it and/or
5  *  modify it under the terms of the GNU Library General Public
6  *  License as published by the Free Software Foundation; either
7  *  version 2 of the License, or (at your option) any later version.
8  *
9  *  This library is distributed in the hope that it will be useful,
10  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
11  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12  *  Library General Public License for more details.
13  *
14  *  You should have received a copy of the GNU Library General Public License
15  *  along with this library; see the file COPYING.LIB.  If not, write to
16  *  the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17  *  Boston, MA 02110-1301, USA.
18  *
19  */
20
21 #ifndef PropertyMap_h
22 #define PropertyMap_h
23
24 #include "PropertySlot.h"
25 #include "identifier.h"
26 #include <wtf/OwnArrayPtr.h>
27 #include <wtf/NotFound.h>
28
29 namespace JSC {
30
31     class JSObject;
32     class JSValue;
33     class PropertyNameArray;
34
35     typedef JSValue** PropertyStorage;
36
37     struct PropertyMapEntry {
38         UString::Rep* key;
39         unsigned attributes;
40         unsigned index;
41
42         PropertyMapEntry(UString::Rep* k, int a)
43             : key(k)
44             , attributes(a)
45             , index(0)
46         {
47         }
48     };
49
50     // lastIndexUsed is an ever-increasing index used to identify the order items
51     // were inserted into the property map. It's required that getEnumerablePropertyNames
52     // return the properties in the order they were added for compatibility with other
53     // browsers' JavaScript implementations.
54     struct PropertyMapHashTable {
55         unsigned sizeMask;
56         unsigned size;
57         unsigned keyCount;
58         unsigned deletedSentinelCount;
59         unsigned lastIndexUsed;
60         unsigned entryIndices[1];
61
62         PropertyMapEntry* entries()
63         {
64             // The entries vector comes after the indices vector.
65             // The 0th item in the entries vector is not really used; it has to
66             // have a 0 in its key to allow the hash table lookup to handle deleted
67             // sentinels without any special-case code, but the other fields are unused.
68             return reinterpret_cast<PropertyMapEntry*>(&entryIndices[size]);
69         }
70
71         static size_t allocationSize(unsigned size)
72         {
73             // We never let a hash table get more than half full,
74             // So the number of indices we need is the size of the hash table.
75             // But the number of entries is half that (plus one for the deleted sentinel).
76             return sizeof(PropertyMapHashTable)
77                 + (size - 1) * sizeof(unsigned)
78                 + (1 + size / 2) * sizeof(PropertyMapEntry);
79         }
80     };
81
82     class PropertyMap {
83     public:
84         PropertyMap();
85         ~PropertyMap();
86
87         PropertyMap& operator=(const PropertyMap&);
88
89         bool isEmpty() { return !m_table; }
90
91         void put(const Identifier& propertyName, JSValue*, unsigned attributes, bool checkReadOnly, JSObject* slotBase, PutPropertySlot&, PropertyStorage&);
92         void remove(const Identifier& propertyName, PropertyStorage&);
93
94         size_t getOffset(const Identifier& propertyName);
95         size_t getOffset(const Identifier& propertyName, unsigned& attributes);
96
97         void getEnumerablePropertyNames(PropertyNameArray&) const;
98
99         bool hasGetterSetterProperties() const { return m_getterSetterFlag; }
100         void setHasGetterSetterProperties(bool f) { m_getterSetterFlag = f; }
101
102         unsigned size() const { return m_table ? m_table->size : 0; }
103         unsigned storageSize() const { return m_table ? m_table->keyCount + m_table->deletedSentinelCount : 0; }
104
105     private:
106         typedef PropertyMapEntry Entry;
107         typedef PropertyMapHashTable Table;
108
109         void expand(PropertyStorage&);
110         void rehash(PropertyStorage&);
111         void rehash(unsigned newTableSize, PropertyStorage&);
112         void createTable(PropertyStorage&);
113
114         void insert(const Entry&, JSValue*, PropertyStorage&);
115
116         void checkConsistency(PropertyStorage&);
117
118         Table* m_table;
119         bool m_getterSetterFlag : 1;
120     };
121
122     inline PropertyMap::PropertyMap() 
123         : m_table(0)
124         , m_getterSetterFlag(false)
125     {
126     }
127
128 } // namespace JSC
129
130 #endif // PropertyMap_h