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