OLD | NEW |
| (Empty) |
1 // Copyright 2008 the V8 project authors. All rights reserved. | |
2 // Redistribution and use in source and binary forms, with or without | |
3 // modification, are permitted provided that the following conditions are | |
4 // met: | |
5 // | |
6 // * Redistributions of source code must retain the above copyright | |
7 // notice, this list of conditions and the following disclaimer. | |
8 // * Redistributions in binary form must reproduce the above | |
9 // copyright notice, this list of conditions and the following | |
10 // disclaimer in the documentation and/or other materials provided | |
11 // with the distribution. | |
12 // * Neither the name of Google Inc. nor the names of its | |
13 // contributors may be used to endorse or promote products derived | |
14 // from this software without specific prior written permission. | |
15 // | |
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
27 | |
28 #include "../include/v8stdint.h" | |
29 #include "globals.h" | |
30 #include "checks.h" | |
31 #include "utils.h" | |
32 #include "allocation.h" | |
33 | |
34 #include "hashmap.h" | |
35 | |
36 namespace v8 { | |
37 namespace internal { | |
38 | |
39 Allocator* HashMap::DefaultAllocator = ::new Allocator(); | |
40 | |
41 | |
42 HashMap::HashMap(MatchFun match, | |
43 Allocator* allocator, | |
44 uint32_t initial_capacity) { | |
45 allocator_ = allocator; | |
46 match_ = match; | |
47 Initialize(initial_capacity); | |
48 } | |
49 | |
50 | |
51 HashMap::~HashMap() { | |
52 if (allocator_) { | |
53 allocator_->Delete(map_); | |
54 } | |
55 } | |
56 | |
57 | |
58 HashMap::Entry* HashMap::Lookup(void* key, uint32_t hash, bool insert) { | |
59 // Find a matching entry. | |
60 Entry* p = Probe(key, hash); | |
61 if (p->key != NULL) { | |
62 return p; | |
63 } | |
64 | |
65 // No entry found; insert one if necessary. | |
66 if (insert) { | |
67 p->key = key; | |
68 p->value = NULL; | |
69 p->hash = hash; | |
70 occupancy_++; | |
71 | |
72 // Grow the map if we reached >= 80% occupancy. | |
73 if (occupancy_ + occupancy_/4 >= capacity_) { | |
74 Resize(); | |
75 p = Probe(key, hash); | |
76 } | |
77 | |
78 return p; | |
79 } | |
80 | |
81 // No entry found and none inserted. | |
82 return NULL; | |
83 } | |
84 | |
85 | |
86 void HashMap::Remove(void* key, uint32_t hash) { | |
87 // Lookup the entry for the key to remove. | |
88 Entry* p = Probe(key, hash); | |
89 if (p->key == NULL) { | |
90 // Key not found nothing to remove. | |
91 return; | |
92 } | |
93 | |
94 // To remove an entry we need to ensure that it does not create an empty | |
95 // entry that will cause the search for another entry to stop too soon. If all | |
96 // the entries between the entry to remove and the next empty slot have their | |
97 // initial position inside this interval, clearing the entry to remove will | |
98 // not break the search. If, while searching for the next empty entry, an | |
99 // entry is encountered which does not have its initial position between the | |
100 // entry to remove and the position looked at, then this entry can be moved to | |
101 // the place of the entry to remove without breaking the search for it. The | |
102 // entry made vacant by this move is now the entry to remove and the process | |
103 // starts over. | |
104 // Algorithm from http://en.wikipedia.org/wiki/Open_addressing. | |
105 | |
106 // This guarantees loop termination as there is at least one empty entry so | |
107 // eventually the removed entry will have an empty entry after it. | |
108 ASSERT(occupancy_ < capacity_); | |
109 | |
110 // p is the candidate entry to clear. q is used to scan forwards. | |
111 Entry* q = p; // Start at the entry to remove. | |
112 while (true) { | |
113 // Move q to the next entry. | |
114 q = q + 1; | |
115 if (q == map_end()) { | |
116 q = map_; | |
117 } | |
118 | |
119 // All entries between p and q have their initial position between p and q | |
120 // and the entry p can be cleared without breaking the search for these | |
121 // entries. | |
122 if (q->key == NULL) { | |
123 break; | |
124 } | |
125 | |
126 // Find the initial position for the entry at position q. | |
127 Entry* r = map_ + (q->hash & (capacity_ - 1)); | |
128 | |
129 // If the entry at position q has its initial position outside the range | |
130 // between p and q it can be moved forward to position p and will still be | |
131 // found. There is now a new candidate entry for clearing. | |
132 if ((q > p && (r <= p || r > q)) || | |
133 (q < p && (r <= p && r > q))) { | |
134 *p = *q; | |
135 p = q; | |
136 } | |
137 } | |
138 | |
139 // Clear the entry which is allowed to en emptied. | |
140 p->key = NULL; | |
141 occupancy_--; | |
142 } | |
143 | |
144 | |
145 void HashMap::Clear() { | |
146 // Mark all entries as empty. | |
147 const Entry* end = map_end(); | |
148 for (Entry* p = map_; p < end; p++) { | |
149 p->key = NULL; | |
150 } | |
151 occupancy_ = 0; | |
152 } | |
153 | |
154 | |
155 HashMap::Entry* HashMap::Start() const { | |
156 return Next(map_ - 1); | |
157 } | |
158 | |
159 | |
160 HashMap::Entry* HashMap::Next(Entry* p) const { | |
161 const Entry* end = map_end(); | |
162 ASSERT(map_ - 1 <= p && p < end); | |
163 for (p++; p < end; p++) { | |
164 if (p->key != NULL) { | |
165 return p; | |
166 } | |
167 } | |
168 return NULL; | |
169 } | |
170 | |
171 | |
172 HashMap::Entry* HashMap::Probe(void* key, uint32_t hash) { | |
173 ASSERT(key != NULL); | |
174 | |
175 ASSERT(IsPowerOf2(capacity_)); | |
176 Entry* p = map_ + (hash & (capacity_ - 1)); | |
177 const Entry* end = map_end(); | |
178 ASSERT(map_ <= p && p < end); | |
179 | |
180 ASSERT(occupancy_ < capacity_); // Guarantees loop termination. | |
181 while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) { | |
182 p++; | |
183 if (p >= end) { | |
184 p = map_; | |
185 } | |
186 } | |
187 | |
188 return p; | |
189 } | |
190 | |
191 | |
192 void HashMap::Initialize(uint32_t capacity) { | |
193 ASSERT(IsPowerOf2(capacity)); | |
194 map_ = reinterpret_cast<Entry*>(allocator_->New(capacity * sizeof(Entry))); | |
195 if (map_ == NULL) { | |
196 v8::internal::FatalProcessOutOfMemory("HashMap::Initialize"); | |
197 return; | |
198 } | |
199 capacity_ = capacity; | |
200 Clear(); | |
201 } | |
202 | |
203 | |
204 void HashMap::Resize() { | |
205 Entry* map = map_; | |
206 uint32_t n = occupancy_; | |
207 | |
208 // Allocate larger map. | |
209 Initialize(capacity_ * 2); | |
210 | |
211 // Rehash all current entries. | |
212 for (Entry* p = map; n > 0; p++) { | |
213 if (p->key != NULL) { | |
214 Lookup(p->key, p->hash, true)->value = p->value; | |
215 n--; | |
216 } | |
217 } | |
218 | |
219 // Delete old map. | |
220 allocator_->Delete(map); | |
221 } | |
222 | |
223 | |
224 } } // namespace v8::internal | |
OLD | NEW |