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 "v8.h"
29
30#include "hashmap.h"
31
32namespace v8 {
33namespace internal {
34
35Allocator HashMap::DefaultAllocator;
36
37
38HashMap::HashMap() {
39  allocator_ = NULL;
40  match_ = NULL;
41}
42
43
44HashMap::HashMap(MatchFun match,
45                 Allocator* allocator,
46                 uint32_t initial_capacity) {
47  allocator_ = allocator;
48  match_ = match;
49  Initialize(initial_capacity);
50}
51
52
53HashMap::~HashMap() {
54  if (allocator_) {
55    allocator_->Delete(map_);
56  }
57}
58
59
60HashMap::Entry* HashMap::Lookup(void* key, uint32_t hash, bool insert) {
61  // Find a matching entry.
62  Entry* p = Probe(key, hash);
63  if (p->key != NULL) {
64    return p;
65  }
66
67  // No entry found; insert one if necessary.
68  if (insert) {
69    p->key = key;
70    p->value = NULL;
71    p->hash = hash;
72    occupancy_++;
73
74    // Grow the map if we reached >= 80% occupancy.
75    if (occupancy_ + occupancy_/4 >= capacity_) {
76      Resize();
77      p = Probe(key, hash);
78    }
79
80    return p;
81  }
82
83  // No entry found and none inserted.
84  return NULL;
85}
86
87
88void HashMap::Remove(void* key, uint32_t hash) {
89  // Lookup the entry for the key to remove.
90  Entry* p = Probe(key, hash);
91  if (p->key == NULL) {
92    // Key not found nothing to remove.
93    return;
94  }
95
96  // To remove an entry we need to ensure that it does not create an empty
97  // entry that will cause the search for another entry to stop too soon. If all
98  // the entries between the entry to remove and the next empty slot have their
99  // initial position inside this interval, clearing the entry to remove will
100  // not break the search. If, while searching for the next empty entry, an
101  // entry is encountered which does not have its initial position between the
102  // entry to remove and the position looked at, then this entry can be moved to
103  // the place of the entry to remove without breaking the search for it. The
104  // entry made vacant by this move is now the entry to remove and the process
105  // starts over.
106  // Algorithm from http://en.wikipedia.org/wiki/Open_addressing.
107
108  // This guarantees loop termination as there is at least one empty entry so
109  // eventually the removed entry will have an empty entry after it.
110  ASSERT(occupancy_ < capacity_);
111
112  // p is the candidate entry to clear. q is used to scan forwards.
113  Entry* q = p;  // Start at the entry to remove.
114  while (true) {
115    // Move q to the next entry.
116    q = q + 1;
117    if (q == map_end()) {
118      q = map_;
119    }
120
121    // All entries between p and q have their initial position between p and q
122    // and the entry p can be cleared without breaking the search for these
123    // entries.
124    if (q->key == NULL) {
125      break;
126    }
127
128    // Find the initial position for the entry at position q.
129    Entry* r = map_ + (q->hash & (capacity_ - 1));
130
131    // If the entry at position q has its initial position outside the range
132    // between p and q it can be moved forward to position p and will still be
133    // found. There is now a new candidate entry for clearing.
134    if ((q > p && (r <= p || r > q)) ||
135        (q < p && (r <= p && r > q))) {
136      *p = *q;
137      p = q;
138    }
139  }
140
141  // Clear the entry which is allowed to en emptied.
142  p->key = NULL;
143  occupancy_--;
144}
145
146
147void HashMap::Clear() {
148  // Mark all entries as empty.
149  const Entry* end = map_end();
150  for (Entry* p = map_; p < end; p++) {
151    p->key = NULL;
152  }
153  occupancy_ = 0;
154}
155
156
157HashMap::Entry* HashMap::Start() const {
158  return Next(map_ - 1);
159}
160
161
162HashMap::Entry* HashMap::Next(Entry* p) const {
163  const Entry* end = map_end();
164  ASSERT(map_ - 1 <= p && p < end);
165  for (p++; p < end; p++) {
166    if (p->key != NULL) {
167      return p;
168    }
169  }
170  return NULL;
171}
172
173
174HashMap::Entry* HashMap::Probe(void* key, uint32_t hash) {
175  ASSERT(key != NULL);
176
177  ASSERT(IsPowerOf2(capacity_));
178  Entry* p = map_ + (hash & (capacity_ - 1));
179  const Entry* end = map_end();
180  ASSERT(map_ <= p && p < end);
181
182  ASSERT(occupancy_ < capacity_);  // Guarantees loop termination.
183  while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) {
184    p++;
185    if (p >= end) {
186      p = map_;
187    }
188  }
189
190  return p;
191}
192
193
194void HashMap::Initialize(uint32_t capacity) {
195  ASSERT(IsPowerOf2(capacity));
196  map_ = reinterpret_cast<Entry*>(allocator_->New(capacity * sizeof(Entry)));
197  if (map_ == NULL) {
198    V8::FatalProcessOutOfMemory("HashMap::Initialize");
199    return;
200  }
201  capacity_ = capacity;
202  Clear();
203}
204
205
206void HashMap::Resize() {
207  Entry* map = map_;
208  uint32_t n = occupancy_;
209
210  // Allocate larger map.
211  Initialize(capacity_ * 2);
212
213  // Rehash all current entries.
214  for (Entry* p = map; n > 0; p++) {
215    if (p->key != NULL) {
216      Lookup(p->key, p->hash, true)->value = p->value;
217      n--;
218    }
219  }
220
221  // Delete old map.
222  allocator_->Delete(map);
223}
224
225
226} }  // namespace v8::internal
227