1 files changed, 137 insertions, 52 deletions

diff --git a/dep/g3dlite/include/G3D/Table.h b/dep/g3dlite/include/G3D/Table.h
index ab0b114b1c4..b8653fdcc9d 100644
--- a/dep/g3dlite/include/G3D/Table.h
+++ b/dep/g3dlite/include/G3D/Table.h
@@ -5,8 +5,8 @@
 
   @maintainer Morgan McGuire, http://graphics.cs.williams.edu
   @created 2001-04-22
-  @edited  2010-01-28
-  Copyright 2000-2010, Morgan McGuire.
+  @edited  2013-01-22
+  Copyright 2000-2013, Morgan McGuire.
   All rights reserved.
  */
 
@@ -90,7 +90,8 @@ namespace G3D {
     };
   </PRE>
 
-  and rely on the default enum operator==.
+  And rely on the default enum operator==.
+
 
   Periodically check that debugGetLoad() is low (> 0.1).  When it gets near
   1.0 your hash function is badly designed and maps too many inputs to
@@ -132,10 +133,12 @@ private:
         // Private to require use of the allocator
         Node(const Key& k, const Value& v, size_t h, Node* n) 
             : entry(k, v), hashCode(h), next(n) {
+                debugAssert((next == NULL) || isValidHeapPointer(next));
         }
 
         Node(const Key& k, size_t h, Node* n) 
             : entry(k), hashCode(h), next(n) {
+                debugAssert((next == NULL) || isValidHeapPointer(next));
         }
 
     public:
@@ -213,9 +216,9 @@ private:
 
         // Allocate a new m_bucket array with the new size
         m_bucket = (Node**)alloc(sizeof(Node*) * newSize);
+        alwaysAssertM(m_bucket != NULL, "MemoryManager::alloc returned NULL. Out of memory.");
         // Set all pointers to NULL
         System::memset(m_bucket, 0, newSize * sizeof(Node*));
-        debugAssertM(m_bucket != NULL, "MemoryManager::alloc returned NULL. Out of memory.");
         // Move each node to its new hash location
         for (size_t b = 0; b < m_numBuckets; ++b) {
             Node* node = oldBucket[b];
@@ -274,7 +277,7 @@ private:
     void freeMemory() {
         checkIntegrity();
 
-        for (size_t b = 0; b < m_numBuckets; b++) {
+        for (size_t b = 0; b < m_numBuckets; ++b) {
             Node* node = m_bucket[b];
             while (node != NULL) {
                 Node* next = node->next;
@@ -357,7 +360,7 @@ public:
     size_t debugGetDeepestBucketSize() const {
         size_t deepest = 0;
 
-        for (size_t b = 0; b < m_numBuckets; b++) {
+        for (size_t b = 0; b < m_numBuckets; ++b) {
             size_t  count = 0;
             Node*   node = m_bucket[b];
             while (node != NULL) {
@@ -377,21 +380,16 @@ public:
        Returns the average size of non-empty buckets.
     */
     float debugGetAverageBucketSize() const {
-        size_t num = 0;
-        size_t count = 0;
+        uint64 num = 0;
 
-        for (size_t b = 0; b < m_numBuckets; b++) {
+        for (size_t b = 0; b < m_numBuckets; ++b) {
             Node* node = m_bucket[b];
             if (node != NULL) {
                 ++num;
-                while (node != NULL) {
-                    node = node->next;
-                    ++count;
-                }
             }
         }
 
-        return (float)((double)count / num);
+        return (float)((double)size() / num);
     }
 
     /**
@@ -402,7 +400,7 @@ public:
      many keys to the same code.
      */
     double debugGetLoad() const {
-        return debugGetDeepestBucketSize() / (double)size();
+        return (double)size() / m_numBuckets;
     }
 
     /**
@@ -428,7 +426,7 @@ public:
          Linked list node.
          */
         Node*               node;
-        ThisType*           table;
+
         size_t              m_numBuckets;
         Node**              m_bucket;
         bool                isDone;
@@ -436,13 +434,14 @@ public:
         /**
          Creates the end iterator.
          */
-        Iterator(const ThisType* table) : table(const_cast<ThisType*>(table)) {
+        Iterator() : index(0), node(NULL), m_bucket(NULL) {
             isDone = true;
         }
 
-        Iterator(const ThisType* table, size_t m_numBuckets, Node** m_bucket) :
-            table(const_cast<ThisType*>(table)),
-            m_numBuckets(m_numBuckets),
+        Iterator(size_t numBuckets, Node** m_bucket) :
+            index(0), 
+            node(NULL),
+            m_numBuckets(numBuckets),
             m_bucket(m_bucket) {
             
             if (m_numBuckets == 0) {
@@ -451,26 +450,38 @@ public:
                 return;
             }
 
+#           ifdef G3D_DEBUG
+                for (unsigned int i = 0; i < m_numBuckets; ++i) {
+                    debugAssert((m_bucket[i] == NULL) || isValidHeapPointer(m_bucket[i]));
+                }
+#           endif
+
             index = 0;
             node = m_bucket[index];
+            debugAssert((node == NULL) || isValidHeapPointer(node));
             isDone = false;
             findNext();
+            debugAssert((node == NULL) || isValidHeapPointer(node));
         }
 
         /**
-         Finds the next element, setting isDone if one can't be found.
-         Looks at the current element first.
+         If node is NULL, then finds the next element by searching through the bucket array.
+         Sets isDone if no more nodes are available.
          */
         void findNext() {
             while (node == NULL) {
-                index++;
+                ++index;
                 if (index >= m_numBuckets) {
+                    m_bucket = NULL;
+                    index = 0;
                     isDone = true;
-                    break;
+                    return;
                 } else {
                     node = m_bucket[index];
+                    debugAssert((node == NULL) || isValidHeapPointer(node));
                 }
             }
+            debugAssert(isValidHeapPointer(node));
         }
 
     public:
@@ -481,12 +492,9 @@ public:
         bool operator==(const Iterator& other) const {
             if (other.isDone || isDone) {
                 // Common case; check against isDone.
-                return (isDone == other.isDone) && (other.table == table);
+                return (isDone == other.isDone);
             } else {
-                return
-                    (table == other.table) &&
-                    (node == other.node) && 
-                    (index == other.index);
+                return (node == other.node) && (index == other.index);
             }
         }
 
@@ -494,8 +502,13 @@ public:
          Pre increment.
          */
         Iterator& operator++() {
+            debugAssert(! isDone);
+            debugAssert(node != NULL);
+            debugAssert(isValidHeapPointer(node));
+            debugAssert((node->next == NULL) || isValidHeapPointer(node->next));
             node = node->next;
             findNext();
+            debugAssert(isDone || isValidHeapPointer(node));
             return *this;
         }
 
@@ -512,17 +525,32 @@ public:
             return node->entry;
         }
 
+        const Value& value() const {
+            return node->entry.value;
+        }
+
+        const Key& key() const {
+            return node->entry.key;
+        }
+
         Entry* operator->() const {
+            debugAssert(isValidHeapPointer(node));
             return &(node->entry);
         }
 
         operator Entry*() const {
+            debugAssert(isValidHeapPointer(node));
             return &(node->entry);
         }
 
-		bool hasMore() const {
-			return ! isDone;
-		}
+        bool isValid() const {
+            return ! isDone;
+        }
+
+        /** @deprecated  Use isValid */
+        bool hasMore() const {
+            return ! isDone;
+        }
     };
 
 
@@ -532,7 +560,7 @@ public:
      the next element.  Do not modify the table while iterating.
      */
     Iterator begin() const {
-        return Iterator(this, m_numBuckets, m_bucket);
+        return Iterator(m_numBuckets, m_bucket);
     }
 
     /**
@@ -540,11 +568,12 @@ public:
      element.
      */
     const Iterator end() const {
-        return Iterator(this);
+        return Iterator();
     }
 
     /**
-     Removes all elements
+     Removes all elements. Guaranteed to free all memory associated with
+     the table.
      */
     void clear() {
         freeMemory();
@@ -578,20 +607,21 @@ private:
         if (m_numBuckets == 0) {
             return false;
         }
-       size_t code = HashFunc::hashCode(key);
-       size_t b = code % m_numBuckets;
+       
+        const size_t code = HashFunc::hashCode(key);
+        const size_t b = code % m_numBuckets;
 
-       // Go to the m_bucket
-       Node* n = m_bucket[b];
+        // Go to the m_bucket
+        Node* n = m_bucket[b];
 
-       if (n == NULL) {
-           return false;
-       }
+        if (n == NULL) {
+            return false;
+        }
 
-       Node* previous = NULL;
+        Node* previous = NULL;
       
-       // Try to find the node
-       do {
+        // Try to find the node
+        do {
           if ((code == n->hashCode) && EqualsFunc::equals(n->entry.key, key)) {
               // This is the node; remove it
 
@@ -609,6 +639,8 @@ private:
               // Delete the node
               Node::destroy(n, m_memoryManager);
               --m_size;
+
+              //checkIntegrity();
               return true;
           }
 
@@ -616,8 +648,8 @@ private:
           n = n->next;
       } while (n != NULL);
 
+      //checkIntegrity();
       return false;
-      //alwaysAssertM(false, "Tried to remove a key that was not in the table.");
    }
 
 public:
@@ -658,7 +690,7 @@ private:
            node = node->next;
        }
 
-        return NULL;
+       return NULL;
    }
 
 public:
@@ -733,7 +765,6 @@ public:
    }
 
 
-
     /** Called by getCreate() and set() 
         
         \param created Set to true if the entry was created by this method.
@@ -756,6 +787,7 @@ public:
             m_bucket[b] = Node::create(key, code, NULL, m_memoryManager);
             ++m_size;
             created = true;
+            //checkIntegrity();
             return m_bucket[b]->entry;
         }
 
@@ -772,6 +804,7 @@ public:
 
             if ((code == n->hashCode) && EqualsFunc::equals(n->entry.key, key)) {
                // This is the a pre-existing node
+               //checkIntegrity();
                return n->entry;
             }
 
@@ -779,12 +812,18 @@ public:
             ++bucketLength;
         } while (n != NULL);
 
+        // Allow the load factor to rise as the table gets huge
+        const int bucketsPerElement = 
+            (m_size > 50000) ? 3 :
+                ((m_size > 10000) ? 5 :
+                 ((m_size > 5000) ? 10 : 15));
+
         const size_t maxBucketLength = 3;
         // (Don't bother changing the size of the table if all entries
         // have the same hashcode--they'll still collide)
         if ((bucketLength > maxBucketLength) && 
             ! allSameCode && 
-            (m_numBuckets < m_size * 15)) {
+            (m_numBuckets < m_size * bucketsPerElement)) {
 
             // This m_bucket was really large; rehash if all elements
             // don't have the same hashcode the number of buckets is
@@ -807,8 +846,10 @@ public:
         m_bucket[b] = Node::create(key, code, m_bucket[b], m_memoryManager);
         ++m_size;
         created = true;
+
+        //checkIntegrity();
         return m_bucket[b]->entry;
-   }
+    }
 
     Entry& getCreateEntry(const Key& key) {
         bool ignore;
@@ -871,7 +912,7 @@ public:
 
    void getKeys(Array<Key>& keyArray) const {
        keyArray.resize(0, DONT_SHRINK_UNDERLYING_ARRAY);
-       for (size_t i = 0; i < m_numBuckets; i++) {
+       for (size_t i = 0; i < m_numBuckets; ++i) {
            Node* node = m_bucket[i];
            while (node != NULL) {
                keyArray.append(node->entry.key);
@@ -880,14 +921,27 @@ public:
        }
    }
 
+   /** Will contain duplicate values if they exist in the table.  This array is parallel to the one returned by getKeys() if the table has not been modified. */
+   void getValues(Array<Value>& valueArray) const {
+       valueArray.resize(0, DONT_SHRINK_UNDERLYING_ARRAY);
+       for (size_t i = 0; i < m_numBuckets; ++i) {
+           Node* node = m_bucket[i];
+           while (node != NULL) {
+               valueArray.append(node->entry.value);
+               node = node->next;
+           }
+       }
+   }
+
    /**
     Calls delete on all of the keys and then clears the table.
     */
    void deleteKeys() {
-       for (size_t i = 0; i < m_numBuckets; i++) {
+       for (size_t i = 0; i < m_numBuckets; ++i) {
            Node* node = m_bucket[i];
            while (node != NULL) {
                delete node->entry.key;
+               node->entry.key = NULL;
                node = node->next;
            }
        }
@@ -912,6 +966,37 @@ public:
            }
        }
    }
+
+    template<class H, class E>
+    bool operator==(const Table<Key, Value, H, E>& other) const {
+        if (size() != other.size()) {
+            return false;
+        }
+
+        for (Iterator it = begin(); it.hasMore(); ++it) {
+            const Value* v = other.getPointer(it->key);
+            if ((v == NULL) || (*v != it->value)) {
+                // Either the key did not exist or the value was not the same
+                return false;
+            }
+        }
+
+        // this and other have the same number of keys, so we don't
+        // have to check for extra keys in other.
+
+        return true;
+    }
+
+    template<class H, class E>
+    bool operator!=(const Table<Key, Value, H, E>& other) const {
+        return ! (*this == other);
+    }
+
+    void debugPrintStatus() {
+        debugPrintf("Deepest bucket size    = %d\n", (int)debugGetDeepestBucketSize());
+        debugPrintf("Average bucket size    = %g\n", debugGetAverageBucketSize());
+        debugPrintf("Load factor            = %g\n", debugGetLoad());
+    }
 };
 
 } // namespace