Add a remove method to the hash map

src/hashmap.cc

Index: src/hashmap.cc
===================================================================
--- src/hashmap.cc	(revision 1955)
+++ src/hashmap.cc	(working copy)
@@ -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

[Dean McNamee, 2009/05/15 07:24:00]

too soon

+  // 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

[Dean McNamee, 2009/05/15 07:24:00]

interval, 

+  // 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

[Dean McNamee, 2009/05/15 07:24:00]

looked at,

+  // the entry to remove without breaking the search for it and the new entry to
+  // remove will be its previous position.

[Dean McNamee, 2009/05/15 07:24:00]

runon :)

+  // 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.

[Dean McNamee, 2009/05/15 07:24:00]

entry

+  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) {