blob: 1be4d9194d81176f79bd43cd5c121f4d060d6acc [file] [log] [blame]
// Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
#include "platform/hashmap.h"
#include "platform/utils.h"
namespace dart {
SimpleHashMap::SimpleHashMap(MatchFun match, uint32_t initial_capacity) {
match_ = match;
Initialize(initial_capacity);
}
SimpleHashMap::~SimpleHashMap() {
delete[] map_;
}
SimpleHashMap::Entry* SimpleHashMap::Lookup(void* key,
uint32_t hash,
bool insert) {
// Find a matching entry.
Entry* p = Probe(key, hash);
if (p->key != nullptr) {
return p;
}
// No entry found; insert one if necessary.
if (insert) {
p->key = key;
p->value = nullptr;
p->hash = hash;
occupancy_++;
// Grow the map if we reached >= 80% occupancy.
if ((occupancy_ + (occupancy_ / 4)) >= capacity_) {
Resize();
p = Probe(key, hash);
}
return p;
}
// No entry found and none inserted.
return nullptr;
}
void SimpleHashMap::Remove(void* key, uint32_t hash) {
// Lookup the entry for the key to remove.
Entry* candidate = Probe(key, hash);
if (candidate->key == nullptr) {
// Key not found nothing to remove.
return;
}
// To remove an entry we need to ensure that it does not create an empty
// entry that will cause the search for another entry to stop too soon. If all
// the entries between the entry to remove and the next empty slot have their
// initial position inside this interval, clearing the entry to remove will
// not break the search. If, while searching for the next empty entry, an
// entry is encountered which does not have its initial position between the
// entry to remove and the position looked at, then this entry can be moved to
// the place of the entry to remove without breaking the search for it. The
// entry made vacant by this move is now the entry to remove and the process
// starts over.
// Algorithm from http://en.wikipedia.org/wiki/Open_addressing.
// This guarantees loop termination as there is at least one empty entry so
// eventually the removed entry will have an empty entry after it.
ASSERT(occupancy_ < capacity_);
// "candidate" is the candidate entry to clear. "next" is used to scan
// forwards.
Entry* next = candidate; // Start at the entry to remove.
while (true) {
// Move "next" to the next entry. Wrap when at the end of the array.
next = next + 1;
if (next == map_end()) {
next = map_;
}
// All entries between "candidate" and "next" have their initial position
// between candidate and entry and the entry candidate can be cleared
// without breaking the search for these entries.
if (next->key == nullptr) {
break;
}
// Find the initial position for the entry at position "next". That is
// the entry where searching for the entry at position "next" will
// actually start.
Entry* start = map_ + (next->hash & (capacity_ - 1));
// If the entry at position "next" has its initial position outside the
// range between "candidate" and "next" it can be moved forward to
// position "candidate" and will still be found. There is now the new
// candidate entry for clearing.
if ((next > candidate && (start <= candidate || start > next)) ||
(next < candidate && (start <= candidate && start > next))) {
*candidate = *next;
candidate = next;
}
}
// Clear the candidate which will not break searching the hash table.
candidate->key = nullptr;
occupancy_--;
}
void SimpleHashMap::Clear(ClearFun clear) {
// Mark all entries as empty.
const Entry* end = map_end();
for (Entry* p = map_; p < end; p++) {
if ((clear != nullptr) && (p->key != nullptr)) {
clear(p->value);
}
p->key = nullptr;
}
occupancy_ = 0;
}
SimpleHashMap::Entry* SimpleHashMap::Start() const {
return Next(map_ - 1);
}
SimpleHashMap::Entry* SimpleHashMap::Next(Entry* p) const {
const Entry* end = map_end();
ASSERT(map_ - 1 <= p && p < end);
for (p++; p < end; p++) {
if (p->key != nullptr) {
return p;
}
}
return nullptr;
}
SimpleHashMap::Entry* SimpleHashMap::Probe(void* key, uint32_t hash) {
ASSERT(key != nullptr);
ASSERT(dart::Utils::IsPowerOfTwo(capacity_));
Entry* p = map_ + (hash & (capacity_ - 1));
const Entry* end = map_end();
ASSERT(map_ <= p && p < end);
ASSERT(occupancy_ < capacity_); // Guarantees loop termination.
while (p->key != nullptr && (hash != p->hash || !match_(key, p->key))) {
p++;
if (p >= end) {
p = map_;
}
}
return p;
}
void SimpleHashMap::Initialize(uint32_t capacity) {
ASSERT(dart::Utils::IsPowerOfTwo(capacity));
map_ = new Entry[capacity];
capacity_ = capacity;
occupancy_ = 0;
}
void SimpleHashMap::Resize() {
Entry* map = map_;
uint32_t n = occupancy_;
// Allocate larger map.
Initialize(capacity_ * 2);
// Rehash all current entries.
for (Entry* p = map; n > 0; p++) {
if (p->key != nullptr) {
Lookup(p->key, p->hash, true)->value = p->value;
n--;
}
}
// Delete old map.
delete[] map;
}
} // namespace dart