# HG changeset patch
# User Jens Alfke <jens@mooseyard.com>
# Date 1253813330 25200
# Node ID 8e3ae153e2c9709e750d8f2b26561b1255301f3c
# Parent  851de24ecb61468d6479f1361548e6d12e91bce8
Fixed a nasty bug in HashDictionary that could cause heap corruption after removing a value. Added a test case to catch that bug. A few tweaks to Hash.

diff -r 851de24ecb61 -r 8e3ae153e2c9 include/Dictionary.h
--- a/include/Dictionary.h	Sun Sep 20 21:25:47 2009 -0700
+++ b/include/Dictionary.h	Thu Sep 24 10:28:50 2009 -0700
@@ -24,6 +24,7 @@
         explicit Key (const Blob &b)                    :Blob(b), hash(computeHash(b)) { }
         Key (const Blob &b, HashCode h)                 :Blob(b), hash(h) { }
         Key (const char *str)                           :Blob(str), hash(computeHash(*this)) { }
+        Key (const void *bytes, uint32_t len)           :Blob(bytes,len), hash(computeHash(*this)) { }
         Key (const void *b, uint32_t len, HashCode h)   :Blob(b,len), hash(h) { }
 
         static HashCode computeHash (Blob);
diff -r 851de24ecb61 -r 8e3ae153e2c9 src/Dictionary.cpp
--- a/src/Dictionary.cpp	Sun Sep 20 21:25:47 2009 -0700
+++ b/src/Dictionary.cpp	Thu Sep 24 10:28:50 2009 -0700
@@ -186,9 +186,9 @@
     }
     
     bool HashDictionary::remove (Key key) {
-        KeyAndValue *kv = (KeyAndValue*) _hash.get(key);
+        KeyAndValue *kv = (KeyAndValue*) _hash.remove(key);
         if (kv) {
-            free(kv);
+            delete kv;
             return true;
         } else
             return false;
@@ -196,7 +196,7 @@
     
     void HashDictionary::removeAll() {
         for (Hash::Iterator it(&_hash); it; ++it)
-            free(it.value());
+            delete (KeyAndValue*) it.value();
         _hash.removeAll();
     }
         
diff -r 851de24ecb61 -r 8e3ae153e2c9 src/Hash.cpp
--- a/src/Hash.cpp	Sun Sep 20 21:25:47 2009 -0700
+++ b/src/Hash.cpp	Thu Sep 24 10:28:50 2009 -0700
@@ -20,7 +20,7 @@
              _value(value) 
         { }
         
-        Key key() const                             {return _key;}
+        const Key& key() const                      {return _key;}
         HashCode hash() const                       {return _key.hash;}
         Hash::Value value() const                   {return _key.bytes ?_value :NULL;}
         void setValue (Hash::Value value)           {_value = value;}
@@ -50,8 +50,7 @@
     }
     
     Hash::IndexEntry& Hash::_find (Key key) const {
-        Key k = Key(key);
-        IndexEntry newEntry(k);
+        IndexEntry newEntry(key);
         int index = newEntry.hash() % _tableSize;
         IndexEntry *found = &_table[index];
         int probe = 0;
@@ -78,7 +77,7 @@
     }
     
     void Hash::put(Key key, Hash::Value value) {
-        IndexEntry newEntry = IndexEntry(Key(key),value);
+        IndexEntry newEntry = IndexEntry(key,value);
         IndexEntry &found = _findForPut(newEntry);
         if (found.hasValue())
             found.setValue(value);
@@ -90,15 +89,16 @@
         }
     }
     
-    bool Hash::remove(Key key) {
+    Hash::Value Hash::remove(Key key) {
         IndexEntry &entry = _find(key);
-        if (!entry.value())
-            return false;
+        Value formerValue = entry.value();
+        if (!formerValue)
+            return NULL;
         entry.markDeleted();
         _count--;
         if (_count/(float)_tableSize < Dictionary::kMinLoadFactor)
             _resize(_tableSize/2);
-        return true;
+        return formerValue;
     }
         
     void Hash::removeAll() {
@@ -109,7 +109,7 @@
     void Hash::dump() const {
         for (int index=0; index<_tableSize; index++)
             if (_table[index].hasValue()) {
-                Blob key = _table[index].key();
+                const Key &key = _table[index].key();
                 printf("%3i: %*s -> %p\n", 
                        index, (int)key.length,(const char*)key.bytes, _table[index].value());
             }
diff -r 851de24ecb61 -r 8e3ae153e2c9 src/Hash.h
--- a/src/Hash.h	Sun Sep 20 21:25:47 2009 -0700
+++ b/src/Hash.h	Thu Sep 24 10:28:50 2009 -0700
@@ -38,8 +38,8 @@
         /** Sets the given value for the given key, replacing any existing value. */
         void put(Key, Value);
         
-        /** Removes the value with the given key. */
-        bool remove(Key);
+        /** Removes the value with the given key. Returns the former value, or NULL if not found. */
+        Value remove(Key);
         
         /** Removes all values. */
         void removeAll();
diff -r 851de24ecb61 -r 8e3ae153e2c9 test/Dictionary_test.cpp
--- a/test/Dictionary_test.cpp	Sun Sep 20 21:25:47 2009 -0700
+++ b/test/Dictionary_test.cpp	Thu Sep 24 10:28:50 2009 -0700
@@ -32,6 +32,26 @@
     return *sDict;
 }
 
+TEST(Dictionary,AddRemove) {
+    HashDictionary dict;
+    EXPECT_EQ(0, dict.count());
+    dict.put("key 1", "value 1");
+    EXPECT_EQ(1, dict.count());
+    dict.put("key 2", "value 2");
+    EXPECT_EQ(2, dict.count());
+    dict.put("key 3", "value 3");
+    EXPECT_TRUE(dict.get("key 1").equals("value 1"));
+    EXPECT_TRUE(dict.get("key 2").equals("value 2"));
+    EXPECT_TRUE(dict.get("key 3").equals("value 3"));
+    EXPECT_TRUE(!dict.get("key 4"));
+
+    EXPECT_TRUE(dict.remove("key 2"));
+    EXPECT_EQ(2, dict.count());
+    EXPECT_TRUE(dict.get("key 1").equals("value 1"));
+    EXPECT_TRUE(!dict.get("key 2"));
+    EXPECT_TRUE(dict.get("key 3").equals("value 3"));
+}
+
 TEST(Dictionary,GetAll) {
     const Dictionary &dict = getDict();
     EXPECT_EQ( sNWords ,  dict.count() );