1// Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#include "platform/hashmap.h"
6
7#include "platform/utils.h"
8
9namespace dart {
10
11SimpleHashMap::SimpleHashMap(MatchFun match, uint32_t initial_capacity) {
12 match_ = match;
13 Initialize(initial_capacity);
14}
15
16SimpleHashMap::~SimpleHashMap() {
17 delete[] map_;
18}
19
20SimpleHashMap::Entry* SimpleHashMap::Lookup(void* key,
21 uint32_t hash,
22 bool insert) {
23 // Find a matching entry.
24 Entry* p = Probe(key, hash);
25 if (p->key != NULL) {
26 return p;
27 }
28
29 // No entry found; insert one if necessary.
30 if (insert) {
31 p->key = key;
32 p->value = NULL;
33 p->hash = hash;
34 occupancy_++;
35
36 // Grow the map if we reached >= 80% occupancy.
37 if ((occupancy_ + (occupancy_ / 4)) >= capacity_) {
38 Resize();
39 p = Probe(key, hash);
40 }
41
42 return p;
43 }
44
45 // No entry found and none inserted.
46 return NULL;
47}
48
49void SimpleHashMap::Remove(void* key, uint32_t hash) {
50 // Lookup the entry for the key to remove.
51 Entry* candidate = Probe(key, hash);
52 if (candidate->key == NULL) {
53 // Key not found nothing to remove.
54 return;
55 }
56
57 // To remove an entry we need to ensure that it does not create an empty
58 // entry that will cause the search for another entry to stop too soon. If all
59 // the entries between the entry to remove and the next empty slot have their
60 // initial position inside this interval, clearing the entry to remove will
61 // not break the search. If, while searching for the next empty entry, an
62 // entry is encountered which does not have its initial position between the
63 // entry to remove and the position looked at, then this entry can be moved to
64 // the place of the entry to remove without breaking the search for it. The
65 // entry made vacant by this move is now the entry to remove and the process
66 // starts over.
67 // Algorithm from http://en.wikipedia.org/wiki/Open_addressing.
68
69 // This guarantees loop termination as there is at least one empty entry so
70 // eventually the removed entry will have an empty entry after it.
71 ASSERT(occupancy_ < capacity_);
72
73 // "candidate" is the candidate entry to clear. "next" is used to scan
74 // forwards.
75 Entry* next = candidate; // Start at the entry to remove.
76 while (true) {
77 // Move "next" to the next entry. Wrap when at the end of the array.
78 next = next + 1;
79 if (next == map_end()) {
80 next = map_;
81 }
82
83 // All entries between "candidate" and "next" have their initial position
84 // between candidate and entry and the entry candidate can be cleared
85 // without breaking the search for these entries.
86 if (next->key == NULL) {
87 break;
88 }
89
90 // Find the initial position for the entry at position "next". That is
91 // the entry where searching for the entry at position "next" will
92 // actually start.
93 Entry* start = map_ + (next->hash & (capacity_ - 1));
94
95 // If the entry at position "next" has its initial position outside the
96 // range between "candidate" and "next" it can be moved forward to
97 // position "candidate" and will still be found. There is now the new
98 // candidate entry for clearing.
99 if ((next > candidate && (start <= candidate || start > next)) ||
100 (next < candidate && (start <= candidate && start > next))) {
101 *candidate = *next;
102 candidate = next;
103 }
104 }
105
106 // Clear the candidate which will not break searching the hash table.
107 candidate->key = NULL;
108 occupancy_--;
109}
110
111void SimpleHashMap::Clear(ClearFun clear) {
112 // Mark all entries as empty.
113 const Entry* end = map_end();
114 for (Entry* p = map_; p < end; p++) {
115 if ((clear != NULL) && (p->key != NULL)) {
116 clear(p->value);
117 }
118 p->key = NULL;
119 }
120 occupancy_ = 0;
121}
122
123SimpleHashMap::Entry* SimpleHashMap::Start() const {
124 return Next(map_ - 1);
125}
126
127SimpleHashMap::Entry* SimpleHashMap::Next(Entry* p) const {
128 const Entry* end = map_end();
129 ASSERT(map_ - 1 <= p && p < end);
130 for (p++; p < end; p++) {
131 if (p->key != NULL) {
132 return p;
133 }
134 }
135 return NULL;
136}
137
138SimpleHashMap::Entry* SimpleHashMap::Probe(void* key, uint32_t hash) {
139 ASSERT(key != NULL);
140
141 ASSERT(dart::Utils::IsPowerOfTwo(capacity_));
142 Entry* p = map_ + (hash & (capacity_ - 1));
143 const Entry* end = map_end();
144 ASSERT(map_ <= p && p < end);
145
146 ASSERT(occupancy_ < capacity_); // Guarantees loop termination.
147 while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) {
148 p++;
149 if (p >= end) {
150 p = map_;
151 }
152 }
153
154 return p;
155}
156
157void SimpleHashMap::Initialize(uint32_t capacity) {
158 ASSERT(dart::Utils::IsPowerOfTwo(capacity));
159 map_ = new Entry[capacity];
160 if (map_ == NULL) {
161 OUT_OF_MEMORY();
162 }
163 capacity_ = capacity;
164 occupancy_ = 0;
165}
166
167void SimpleHashMap::Resize() {
168 Entry* map = map_;
169 uint32_t n = occupancy_;
170
171 // Allocate larger map.
172 Initialize(capacity_ * 2);
173
174 // Rehash all current entries.
175 for (Entry* p = map; n > 0; p++) {
176 if (p->key != NULL) {
177 Lookup(p->key, p->hash, true)->value = p->value;
178 n--;
179 }
180 }
181
182 // Delete old map.
183 delete[] map;
184}
185
186} // namespace dart
187