From 77b9c60169ba92ff0941959ebf5ea513d13ccb67 Mon Sep 17 00:00:00 2001 From: "sgjesse@chromium.org" Date: Fri, 15 May 2009 07:09:17 +0000 Subject: [PATCH] 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 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@1956 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/hashmap.cc | 62 ++++++++++++++++++++++++++++++++++++-- src/hashmap.h | 3 ++ test/cctest/test-hashmap.cc | 73 ++++++++++++++++++++++++++++++++++++++------- 3 files changed, 126 insertions(+), 12 deletions(-) diff --git a/src/hashmap.cc b/src/hashmap.cc index 34359e8..bce284b 100644 --- a/src/hashmap.cc +++ b/src/hashmap.cc @@ -59,7 +59,7 @@ HashMap::~HashMap() { 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 @@ HashMap::Entry* HashMap::Lookup(void* key, uint32_t hash, bool insert) { } +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 @@ HashMap::Entry* HashMap::Probe(void* key, uint32_t hash) { 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) { diff --git a/src/hashmap.h b/src/hashmap.h index fabf3dc..c9cadb2 100644 --- a/src/hashmap.h +++ b/src/hashmap.h @@ -75,6 +75,9 @@ class HashMap { // 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(); diff --git a/test/cctest/test-hashmap.cc b/test/cctest/test-hashmap.cc index 954dbe1..7e16927 100644 --- a/test/cctest/test-hashmap.cc +++ b/test/cctest/test-hashmap.cc @@ -38,20 +38,28 @@ static bool DefaultMatchFun(void* a, void* b) { } +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(x), Hash(x), true); + HashMap::Entry* p = map_.Lookup(reinterpret_cast(x), hash_(x), true); CHECK(p != NULL); // insert is set! CHECK_EQ(reinterpret_cast(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(x), hash_(x)); + } + bool Present(int x) { - HashMap::Entry* p = map_.Lookup(reinterpret_cast(x), Hash(x), false); + HashMap::Entry* p = map_.Lookup(reinterpret_cast(x), hash_(x), false); if (p != NULL) { CHECK_EQ(reinterpret_cast(x), p->key); } @@ -73,12 +81,16 @@ class IntSet { 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 @@ TEST(Set) { 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 @@ TEST(Set) { 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(set.occupancy())); set.Insert(x); - x = x*factor + offset; + x = x * factor + offset; } + CHECK_EQ(n, static_cast(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(set.occupancy())); + + // Remove all these values. + x = start; + for (uint32_t i = 0; i < n; i++) { + CHECK_EQ(n - i, static_cast(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); } -- 2.7.4