Add a remove method to the hash map

src/hashmap.cc

 // Copyright 2008 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 41 matching lines @@
 HashMap::~HashMap() {
   if (allocator_) {
     allocator_->Delete(map_);
   }
 }
 
 
 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;
   }
 
   // No entry found; insert one if necessary.
   if (insert) {
     p->key = key;
     p->value = NULL;
     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 NULL;
 }
 
 
+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();
   for (Entry* p = map_; p < end; p++) {
     p->key = NULL;
   }
   occupancy_ = 0;
 }
 
 
@@ skipping 15 matching lines @@
 
 
 HashMap::Entry* HashMap::Probe(void* key, uint32_t hash) {
   ASSERT(key != NULL);
 
   ASSERT(IsPowerOf2(capacity_));
   Entry* p = map_ + (hash & (capacity_ - 1));
   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) {
       p = map_;
     }
   }
 
   return p;
 }
 
@@ skipping 21 matching lines @@
       n--;
     }
   }
 
   // Delete old map.
   allocator_->Delete(map);
 }
 
 
 } }  // namespace v8::internal