diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/HashTable.h
--- a/jitcraft/HashTable.h	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/HashTable.h	Sat Jul 07 20:28:29 2012 -0700
@@ -1,23 +1,28 @@
-// vim: set ts=4 sw=4 tw=99 et:
-//
-//  
-// (C) Copyright 2010-2011 AlliedModders LLC
-//
-// Initial Author: David Anderson
-// Contributors:
-//
-//
-
+/*
+ * Copyright (C) 2012 David Anderson
+ *
+ * This file is part of JITCraft.
+ *
+ * JITCraft is free software: you can redistribute it and/or modify it under
+ * the terms of the GNU General Public License as published by the Free
+ * Software Foundation, either version 3 of the License, or (at your option)
+ * any later version.
+ * 
+ * Foobar is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * JITCraft. If not, see http://www.gnu.org/licenses/.
+ */
 #ifndef _INCLUDE_KEIMA_HASHTABLE_H_
 #define _INCLUDE_KEIMA_HASHTABLE_H_
 
 #include <new>
 #include <limits.h>
-#include "Object.h"
-#include "vm/Array.h"
-#include "Environment.h"
+#include "Utility.h"
 
-namespace ke {
+namespace jc {
 
 template <typename T>
 class HashTableEntry
@@ -38,9 +43,10 @@
     }
     void setRemoved() {
         hash_ = kRemovedHash;
-        destruct();
+        t_ = T();
     }
     void construct() {
+        hash_ = kFreeHash;
         new (&t_) T();
     }
     void destruct() {
@@ -66,6 +72,8 @@
 template <typename HashPolicy, typename AllocPolicy>
 class HashTable : public AllocPolicy
 {
+    friend class iterator;
+
     typedef typename HashPolicy::Payload Payload;
     typedef HashTableEntry<Payload> Entry;
 
@@ -73,6 +81,7 @@
     uint32 nelements_;
     uint32 ndeleted_;
     Entry *table_;
+    uint32 minCapacity_;
 
   private:
     static const uint32 kMinCapacity = 16;
@@ -88,7 +97,7 @@
     }
 
     Entry *createTable(uint32 capacity) {
-        KE_ASSERT(capacity <= kMaxCapacity);
+        assert(capacity <= kMaxCapacity);
 
         Entry *table = (Entry *)this->malloc(capacity * sizeof(Entry));
         if (!table)
@@ -154,7 +163,7 @@
           : hash_(hash),
             capacity_(capacity)
         {
-            KE_ASSERT(IsPowerOfTwo(capacity_)); 
+            assert(IsPowerOfTwo(capacity_)); 
         }
 
         uint32 entry() const {
@@ -176,11 +185,13 @@
     }
 
     bool shrink() {
+        if ((capacity_ >> 1) < minCapacity_)
+            return true;
         return changeCapacity(capacity_ >> 1);
     }
     
     bool grow() {
-        KE_ASSERT(IsPowerOfTwo(kMaxCapacity));
+        assert(IsPowerOfTwo(kMaxCapacity));
         if (capacity_ >= kMaxCapacity) {
             this->reportAllocationOverflow();
             return false;
@@ -188,16 +199,8 @@
         return changeCapacity(capacity_ << 1);
     }
 
-    bool checkDensity() {
-        if (underloaded())
-            return shrink(); 
-        if (overloaded())
-            return grow();
-        return true;
-    }
-
     bool changeCapacity(uint32 newCapacity) {
-        KE_ASSERT(newCapacity <= kMaxCapacity);
+        assert(newCapacity <= kMaxCapacity);
 
         Entry *newTable = createTable(newCapacity);
         if (!newTable)
@@ -219,7 +222,7 @@
             }
             oldEntry.destruct();
         }
-        this->free(table_);
+        this->free(oldTable);
 
         return true;
     }
@@ -277,7 +280,7 @@
     }
 
     bool add(Insert &i) {
-        KE_ASSERT(!i.found());
+        assert(!i.found());
 
         // If the entry is deleted, just re-use the slot.
         if (i.entry().removed()) {
@@ -310,13 +313,21 @@
         return true;
     }
 
+    void remove(Entry &e) {
+        assert(!e.isLive());
+        e.setRemoved();
+        ndeleted_++;
+        nelements_--;
+    }
+
   public:
     HashTable(AllocPolicy ap)
       : AllocPolicy(ap),
         capacity_(0),
         nelements_(0),
         ndeleted_(0),
-        table_(NULL)
+        table_(NULL),
+        minCapacity_(kMinCapacity)
     {
     }
 
@@ -333,7 +344,9 @@
         else if (capacity > kMaxCapacity)
             capacity = kMaxCapacity;
 
-        KE_ASSERT(IsPowerOfTwo(capacity));
+        minCapacity_ = capacity;
+
+        assert(IsPowerOfTwo(capacity));
         capacity_ = capacity;
 
         table_ = createTable(capacity_);
@@ -359,9 +372,52 @@
         *i = payload;
         return true;
     }
+
+    bool checkDensity() {
+        if (underloaded())
+            return shrink(); 
+        if (overloaded())
+            return grow();
+        return true;
+    }
+
+  public:
+    class iterator
+    {
+        HashTable *table_;
+        Entry *i_;
+        Entry *end_;
+
+      public:
+        iterator(HashTable *table)
+          : table_(table),
+            i_(table->table_),
+            end_(table->table_ + table->capacity_)
+        {
+            while (i_ < end_ && !i_->isLive())
+                i_++;
+        }
+
+        bool empty() const {
+            return i_ == end_;
+        }
+
+        void erase() {
+            assert(!empty());
+            table_->remove(*i_);
+        }
+
+        const Payload &operator *() const {
+            return i_->payload();
+        }
+
+        void next() {
+            while (i_ < end_ && !i_->isLive())
+                i_++;
+        }
+    };
 };
 
 }
 
 #endif // _INCLUDE_KEIMA_HASHTABLE_H_
-