Author: [email protected]
Date: Fri May 15 00:09:17 2009
New Revision: 1956
Modified:
branches/bleeding_edge/src/hashmap.cc
branches/bleeding_edge/src/hashmap.h
branches/bleeding_edge/test/cctest/test-hashmap.cc
Log:
Add a remove method to the hash map.
Extended the hash map test to also use a heavy collision hash function to
exercise the remove code.
Review URL: http://codereview.chromium.org/113397
Modified: branches/bleeding_edge/src/hashmap.cc
==============================================================================
--- branches/bleeding_edge/src/hashmap.cc (original)
+++ branches/bleeding_edge/src/hashmap.cc Fri May 15 00:09:17 2009
@@ -59,7 +59,7 @@
HashMap::Entry* HashMap::Lookup(void* key, uint32_t hash, bool insert) {
// Find a matching entry.
Entry* p = Probe(key, hash);
- if (p->key != NULL) {
+ if (p->key != NULL) {
return p;
}
@@ -84,6 +84,64 @@
}
+void HashMap::Remove(void* key, uint32_t hash) {
+ // Lookup the entry for the key to remove.
+ Entry *p = Probe(key, hash);
+ if (p->key == NULL) {
+ // Key not found nothing to remove.
+ return;
+ }
+
+ // To remove the entry we need to ensure that it does not create an empty
+ // entry that will cause search for an entry to stop to 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 this entry can be moved to the
place of
+ // the entry to remove without breaking the search for it and the new
entry to
+ // remove will be its previous position.
+ // 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 entyr will have an empty entry after it.
+ ASSERT(occupancy_ < capacity_);
+
+ // p is the candidate entry to clear. q is used to scan forwards.
+ Entry* q = p; // Start at the entry to remove.
+ while (true) {
+ // Move q to the next entry.
+ q = q + 1;
+ if (q == map_end()) {
+ q = map_;
+ }
+
+ // All entries between p and q have their initial position between p
and q
+ // and the entry p can be cleared without breaking the search for these
+ // entries.
+ if (q->key == NULL) {
+ break;
+ }
+
+ // Find the initial position for the entry at position q.
+ Entry* r = map_ + (q->hash & (capacity_ - 1));
+
+ // If the entry at position q has its initial position outside the
range
+ // between p and q it can be moved forward to position p and will
still be
+ // found. There is now a new candidate entry for clearing.
+ if (q > p && (r <= p || r > q) ||
+ q < p && (r <= p && r > q)) {
+ *p = *q;
+ p = q;
+ }
+ }
+
+ // Clear the entry which is allowed to en emptied.
+ p->key = NULL;
+ occupancy_--;
+}
+
+
void HashMap::Clear() {
// Mark all entries as empty.
const Entry* end = map_end();
@@ -119,7 +177,7 @@
const Entry* end = map_end();
ASSERT(map_ <= p && p < end);
- ASSERT(occupancy_ < capacity_); // guarantees loop termination
+ ASSERT(occupancy_ < capacity_); // Guarantees loop termination.
while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) {
p++;
if (p >= end) {
Modified: branches/bleeding_edge/src/hashmap.h
==============================================================================
--- branches/bleeding_edge/src/hashmap.h (original)
+++ branches/bleeding_edge/src/hashmap.h Fri May 15 00:09:17 2009
@@ -75,6 +75,9 @@
// Otherwise, NULL is returned.
Entry* Lookup(void* key, uint32_t hash, bool insert);
+ // Removes the entry with matching key.
+ void Remove(void* key, uint32_t hash);
+
// Empties the hash map (occupancy() == 0).
void Clear();
Modified: branches/bleeding_edge/test/cctest/test-hashmap.cc
==============================================================================
--- branches/bleeding_edge/test/cctest/test-hashmap.cc (original)
+++ branches/bleeding_edge/test/cctest/test-hashmap.cc Fri May 15 00:09:17
2009
@@ -38,20 +38,28 @@
}
+typedef uint32_t (*IntKeyHash)(uint32_t key);
+
+
class IntSet {
public:
- IntSet() : map_(DefaultMatchFun) {}
+ IntSet(IntKeyHash hash) : hash_(hash), map_(DefaultMatchFun) {}
void Insert(int x) {
CHECK_NE(0, x); // 0 corresponds to (void*)NULL - illegal key value
- HashMap::Entry* p = map_.Lookup(reinterpret_cast<void*>(x), Hash(x),
true);
+ HashMap::Entry* p = map_.Lookup(reinterpret_cast<void*>(x), hash_(x),
true);
CHECK(p != NULL); // insert is set!
CHECK_EQ(reinterpret_cast<void*>(x), p->key);
// we don't care about p->value
}
+ void Remove(int x) {
+ CHECK_NE(0, x); // 0 corresponds to (void*)NULL - illegal key value
+ map_.Remove(reinterpret_cast<void*>(x), hash_(x));
+ }
+
bool Present(int x) {
- HashMap::Entry* p = map_.Lookup(reinterpret_cast<void*>(x), Hash(x),
false);
+ HashMap::Entry* p = map_.Lookup(reinterpret_cast<void*>(x), hash_(x),
false);
if (p != NULL) {
CHECK_EQ(reinterpret_cast<void*>(x), p->key);
}
@@ -73,12 +81,16 @@
private:
HashMap map_;
- static uint32_t Hash(uint32_t key) { return key * 23; }
+ IntKeyHash hash_;
};
-TEST(Set) {
- IntSet set;
+static uint32_t Hash(uint32_t key) { return 23; }
+static uint32_t CollisionHash(uint32_t key) { return key & 0x3; }
+
+
+void TestSet(IntKeyHash hash, int size) {
+ IntSet set(hash);
CHECK_EQ(0, set.occupancy());
set.Insert(1);
@@ -96,6 +108,18 @@
CHECK(!set.Present(4));
CHECK_EQ(3, set.occupancy());
+ set.Remove(1);
+ CHECK(!set.Present(1));
+ CHECK(set.Present(2));
+ CHECK(set.Present(3));
+ CHECK_EQ(2, set.occupancy());
+
+ set.Remove(3);
+ CHECK(!set.Present(1));
+ CHECK(set.Present(2));
+ CHECK(!set.Present(3));
+ CHECK_EQ(1, set.occupancy());
+
set.Clear();
CHECK_EQ(0, set.occupancy());
@@ -103,21 +127,50 @@
const int start = 453;
const int factor = 13;
const int offset = 7;
- const uint32_t n = 1000;
+ const uint32_t n = size;
int x = start;
for (uint32_t i = 0; i < n; i++) {
CHECK_EQ(i, static_cast<double>(set.occupancy()));
set.Insert(x);
- x = x*factor + offset;
+ x = x * factor + offset;
}
+ CHECK_EQ(n, static_cast<double>(set.occupancy()));
// Verify the same sequence of values.
x = start;
for (uint32_t i = 0; i < n; i++) {
CHECK(set.Present(x));
- x = x*factor + offset;
+ x = x * factor + offset;
}
-
CHECK_EQ(n, static_cast<double>(set.occupancy()));
+
+ // Remove all these values.
+ x = start;
+ for (uint32_t i = 0; i < n; i++) {
+ CHECK_EQ(n - i, static_cast<double>(set.occupancy()));
+ CHECK(set.Present(x));
+ set.Remove(x);
+ CHECK(!set.Present(x));
+ x = x * factor + offset;
+
+ // Verify the the expected values are still there.
+ int y = start;
+ for (uint32_t j = 0; j < n; j++) {
+ if (j <= i) {
+ CHECK(!set.Present(y));
+ } else {
+ CHECK(set.Present(y));
+ }
+ y = y * factor + offset;
+ }
+
+ }
+ CHECK_EQ(0, set.occupancy());
+}
+
+
+TEST(Set) {
+ TestSet(Hash, 1000);
+ TestSet(CollisionHash, 100);
}
--~--~---------~--~----~------------~-------~--~----~
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
-~----------~----~----~----~------~----~------~--~---
