*Backed out changeset 3be01fb200a5

--HG--
branch : trunk

1 files changed, 113 insertions, 0 deletions

diff --git a/dep/include/g3dlite/G3D/Table.h b/dep/include/g3dlite/G3D/Table.h
index c1da412f3f3..1d021daae2b 100644
--- a/dep/include/g3dlite/G3D/Table.h
+++ b/dep/include/g3dlite/G3D/Table.h
@@ -1,14 +1,18 @@
 /**
   @file Table.h
+
   Templated hash table class.
+
   @maintainer Morgan McGuire, matrix@graphics3d.com
   @created 2001-04-22
   @edited  2006-10-14
   Copyright 2000-2006, Morgan McGuire.
   All rights reserved.
  */
+
 #ifndef G3D_TABLE_H
 #define G3D_TABLE_H
+
 #include "G3D/platform.h"
 #include "G3D/Array.h"
 #include "G3D/debug.h"
@@ -17,71 +21,89 @@
 #include "G3D/Crypto.h"
 #include <cstddef>
 #include <string>
+
 #ifdef G3D_WIN32
 #   pragma warning (push)
     // Debug name too long warning
 #   pragma warning (disable : 4786)
 #endif
 
+
 template<typename Key>
 struct GHashCode{};
+
 template <>
 struct GHashCode<int>
 {
     size_t operator()(int key) const { return static_cast<size_t>(key); }
 };
+
 template <>
 struct GHashCode<G3D::uint32>
 {
     size_t operator()(G3D::uint32 key) const { return static_cast<size_t>(key); }
 };
+
 template <>
 struct GHashCode<G3D::uint64>
 {
     size_t operator()(G3D::uint64 key) const { return static_cast<size_t>(key); }
 };
+
 template <>
 struct GHashCode<void*>
 {
     size_t operator()(const void* key) const { return reinterpret_cast<size_t>(key); }
 };
+
 template<class T>
 struct GHashCode<T*>
 {
     size_t operator()(const T* key) const { return reinterpret_cast<size_t>(key); }
 };
+
 template <>
 struct GHashCode<const std::string>
 {
     size_t operator()(const std::string& key) const { return static_cast<size_t>(G3D::Crypto::crc32(key.c_str(), key.size())); }
 };
+
 template <>
 struct GHashCode<std::string>
 {
     size_t operator()(const std::string& key) const { return static_cast<size_t>(G3D::Crypto::crc32(key.c_str(), key.size())); }
 };
+
 namespace G3D {
 
+
 /**
  An unordered data structure mapping keys to values.
+
  Key must be a pointer, an int, a std::string, a class with a hashCode() method,
  or provide overloads for:
+
   <PRE>
     template<> struct GHashCode<class Key> {
         size_t operator()(Key key) const { return reinterpret_cast<size_t>( ... ); }
     };
+
    bool operator==(const Key&, const Key&);
   </PRE>
+
  G3D pre-defines GHashCode functions for common types (like <CODE>int</CODE> and <CODE>std::string</CODE>).
  If you use a Table with a different type you must write those functions yourself.  For example,
  an enum would use:
+
   <PRE>
     template<> struct GHashCode<MyEnum> {
         size_t operator()(MyEnum key) const { return reinterpret_cast<size_t>( key ); }
     };
   </PRE>
+
   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
   the same output.
@@ -89,6 +111,7 @@ namespace G3D {
 template<class Key, class Value, class HashFunc = GHashCode<Key> >
 class Table {
 public:
+
     /**
      The pairs returned by iterator.
      */
@@ -97,6 +120,7 @@ public:
         Key    key;
         Value  value;
     };
+
 private:
     /**
      Linked list nodes used internally by HashTable.
@@ -107,20 +131,24 @@ private:
         Entry       entry;
         Node*       next;
 
+
         /** Provide pooled allocation for speed. */
         inline void* operator new (size_t size) {
             return System::malloc(size);
         }
+
         inline void operator delete (void* p) {
             System::free(p);
         }
 
+
         Node(Key key, Value value, size_t hashCode, Node* next) {
             this->entry.key   = key;
             this->entry.value = value;
             this->hashCode    = hashCode;
             this->next        = next;
         }
+
         /**
         Clones a whole chain;
         */
@@ -128,42 +156,54 @@ private:
            return new Node(this->entry.key, this->entry.value, hashCode, (next == NULL) ? NULL : next->clone());
         }
     };
+
     HashFunc m_HashFunc;
+
     /**
      Number of elements in the table.
      */
     size_t  _size;
+
     /**
      Array of Node*.
      We don't use Array<Node*> because Table is lower level.
      Some elements may be NULL.
      */
     Node**  bucket;
+
     /**
      Length of the bucket array.
      */
     size_t  numBuckets;
+
     /**
      Re-hashes for a larger bucket size.
      */
     void resize(size_t numBuckets) {
+
         Node** oldBucket = bucket;
         bucket = (Node**)System::alignedMalloc(sizeof(Node*) * numBuckets, 16);
         System::memset(bucket, 0, sizeof(Node*) * numBuckets);
+
         for (size_t b = 0; b < this->numBuckets; b++) {
             Node* node = oldBucket[b];
+
             while (node != NULL) {
                 Node* nextNode = node->next;
+
                 // insert at the head of the list for bucket[i]
                 size_t i = node->hashCode % numBuckets;
                 node->next = bucket[i];
                 bucket[i] = node;
+
                 node = nextNode;
             }
         }
+
         System::alignedFree(oldBucket);
         this->numBuckets = numBuckets;
     }
+
     void copyFrom(const Table<Key, Value>& h) {
         this->_size = h._size;
         this->numBuckets = h.numBuckets;
@@ -175,6 +215,7 @@ private:
             }
         }
     }
+
     /**
      Frees the heap structures for the nodes.
      */
@@ -192,7 +233,9 @@ private:
         numBuckets = 0;
         _size     = 0;
     }
+
 public:
+
     /**
      Creates an empty hash table.  This causes some heap allocation to occur.
      */
@@ -202,6 +245,7 @@ public:
         bucket     = (Node**)System::alignedMalloc(sizeof(Node*) * numBuckets, 16);
         System::memset(bucket, 0, sizeof(Node*) * numBuckets);
     }
+
     /**
     Destroys all of the memory allocated by the table, but does <B>not</B>
     call delete on keys or values if they are pointers.  If you want to
@@ -211,9 +255,11 @@ public:
     virtual ~Table() {
         freeMemory();
     }
+
     Table(const Table<Key, Value>& h) {
         this->copyFrom(h);
     }
+
     Table& operator=(const Table<Key, Value>& h) {
         // No need to copy if the argument is this
         if (this != &h) {
@@ -223,11 +269,13 @@ public:
         }
         return *this;
     }
+
     /**
      Returns the length of the deepest bucket.
      */
     size_t debugGetDeepestBucketSize() const {
         size_t deepest = 0;
+
         for (size_t b = 0; b < numBuckets; b++) {
             size_t  count = 0;
             Node*   node = bucket[b];
@@ -235,12 +283,15 @@ public:
                 node = node->next;
                 ++count;
             }
+
             if (count > deepest) {
                 deepest = count;
             }
         }
+
         return deepest;
     }
+
     /**
      A small load (close to zero) means the hash table is acting very
      efficiently most of the time.  A large load (close to 1) means
@@ -251,22 +302,26 @@ public:
     double debugGetLoad() const {
         return debugGetDeepestBucketSize() / (double)size();
     }
+
     /**
      Returns the number of buckets.
      */
     size_t debugGetNumBuckets() const {
         return numBuckets;
     }
+
     /**
      C++ STL style iterator variable.  See begin().
      */
     class Iterator {
     private:
         friend class Table<Key, Value>;
+
         /**
          Bucket index.
          */
         size_t              index;
+
         /**
          Linked list node.
          */
@@ -275,26 +330,31 @@ public:
         size_t              numBuckets;
         Node**              bucket;
         bool                isDone;
+
         /**
          Creates the end iterator.
          */
         Iterator(const Table<Key, Value>* table) : table(const_cast<Table<Key, Value>*>(table)) {
             isDone = true;
         }
+
         Iterator(const Table<Key, Value>* table, size_t numBuckets, Node** bucket) :
             table(const_cast<Table<Key, Value>*>(table)),
             numBuckets(numBuckets),
             bucket(bucket) {
+
             if (numBuckets == 0) {
                 // Empty table
                 isDone = true;
                 return;
             }
+
             index = 0;
             node = bucket[index];
             isDone = false;
             findNext();
         }
+
         /**
          Finds the next element, setting isDone if one can't be found.
          Looks at the current element first.
@@ -310,10 +370,12 @@ public:
                 }
             }
         }
+
     public:
         inline bool operator!=(const Iterator& other) const {
             return !(*this == other);
         }
+
         bool operator==(const Iterator& other) const {
             if (other.isDone || isDone) {
                 // Common case; check against isDone.
@@ -325,6 +387,7 @@ public:
                     (index == other.index);
             }
         }
+
         /**
          Pre increment.
          */
@@ -333,6 +396,7 @@ public:
             findNext();
             return *this;
         }
+
         /**
          Post increment (slower than preincrement).
          */
@@ -341,17 +405,21 @@ public:
             ++(*this);
             return old;
         }
+
         const Entry& operator*() const {
             return node->entry;
         }
+
         Entry* operator->() const {
             return &(node->entry);
         }
+
         operator Entry*() const {
             return &(node->entry);
         }
     };
 
+
     /**
      C++ STL style iterator method.  Returns the first Entry, which
      contains a key and value.  Use preincrement (++entry) to get to
@@ -360,6 +428,7 @@ public:
     Iterator begin() const {
         return Iterator(this, numBuckets, bucket);
     }
+
     /**
      C++ STL style iterator method.  Returns one after the last iterator
      element.
@@ -367,6 +436,7 @@ public:
     const Iterator end() const {
         return Iterator(this);
     }
+
     /**
      Removes all elements
      */
@@ -378,6 +448,7 @@ public:
          System::memset(bucket, 0, sizeof(Node*) * numBuckets);
     }
 
+
     /**
      Returns the number of keys.
      */
@@ -385,6 +456,7 @@ public:
         return _size;
     }
 
+
     /**
      If you insert a pointer into the key or value of a table, you are
      responsible for deallocating the object eventually.  Inserting
@@ -393,53 +465,68 @@ public:
     void set(const Key& key, const Value& value) {
         size_t code = m_HashFunc(key);
         size_t b = code % numBuckets;
+
         // Go to the bucket
         Node* n = bucket[b];
+
         // No bucket, so this must be the first
         if (n == NULL) {
             bucket[b] = new Node(key, value, code, NULL);
             ++_size;
             return;
         }
+
         size_t bucketLength = 1;
+
         // Sometimes a bad hash code will cause all elements
         // to collide.  Detect this case and don't rehash when
         // it occurs; nothing good will come from the rehashing.
         bool allSameCode = true;
+
         // Try to find the node
         do {
             allSameCode = allSameCode && (code == n->hashCode);
+
             if ((code == n->hashCode) && (n->entry.key == key)) {
                // Replace the existing node.
                n->entry.value = value;
                return;
             }
+
             n = n->next;
             ++bucketLength;
         } while (n != NULL);
+
         const size_t maxBucketLength = 5;
         if ((bucketLength > maxBucketLength) & ! allSameCode && (numBuckets < _size * 20)) {
             // This bucket was really large; rehash if all elements
             // don't have the same hashcode the number of buckets is reasonable.
             resize(numBuckets * 2 + 1);
         }
+
         // Not found; insert at the head.
         b = code % numBuckets;
         bucket[b] = new Node(key, value, code, bucket[b]);
         ++_size;
    }
+
    /**
     Removes an element from the table if it is present.  It is an error
     to remove an element that isn't present.
     */
    void remove(const Key& key) {
+
       size_t code = m_HashFunc(key);
       size_t b = code % numBuckets;
+
       // Go to the bucket
       Node* n = bucket[b];
+
       // Make sure it was found
       alwaysAssertM(n != NULL, "Tried to remove a key that was not in the table.");
+
       Node* previous = NULL;
+
       // Try to find the node
       do {
           if ((code == n->hashCode) && (n->entry.key == key)) {
@@ -454,31 +541,39 @@ public:
               --_size;
               return;
           }
+
           previous = n;
           n = n->next;
        } while (n != NULL);
 
+
       alwaysAssertM(false, "Tried to remove a key that was not in the table.");
    }
+
    /**
     Returns the value associated with key.
     @deprecated Use get(key, val) or
     */
    Value& get(const Key& key) const {
+
         size_t  code = m_HashFunc(key);
         size_t b = code % numBuckets;
+
         Node* node = bucket[b];
+
         while (node != NULL) {
             if ((node->hashCode == code) && (node->entry.key == key)) {
                 return node->entry.value;
             }
             node = node->next;
         }
+
         debugAssertM(false, "Key not found");
         // The next line is here just to make
         // a compiler warning go away.
         return node->entry.value;
    }
+
    /**
     If the key is present in the table, val is set to the associated value and returns true.
     If the key is not present, returns false.
@@ -486,7 +581,9 @@ public:
    bool get(const Key& key, Value& val) const {
       size_t code = m_HashFunc(key);
       size_t b = code % numBuckets;
+
       Node* node = bucket[b];
+
       while (node != NULL) {
           if ((node->hashCode == code) && (node->entry.key == key)) {
              // found key
@@ -495,25 +592,31 @@ public:
           }
           node = node->next;
       }
+
       // Failed to find key
       return false;
    }
+
    /**
     Returns true if key is in the table.
     */
    bool containsKey(const Key& key) const {
        size_t code = m_HashFunc(key);
        size_t b = code % numBuckets;
+
        Node* node = bucket[b];
+
        while (node != NULL) {
            if ((node->hashCode == code) && (node->entry.key == key)) {
               return true;
            }
            node = node->next;
        }
+
        return false;
    }
 
+
    /**
     Short syntax for get.
     */
@@ -521,6 +624,7 @@ public:
       return get(key);
    }
 
+
    /**
     Returns an array of all of the keys in the table.
     You can iterate over the keys to get the values.
@@ -530,6 +634,7 @@ public:
        getKeys(keyArray);
        return keyArray;
    }
+
    void getKeys(Array<Key>& keyArray) const {
        keyArray.resize(0, DONT_SHRINK_UNDERLYING_ARRAY);
        for (size_t i = 0; i < numBuckets; i++) {
@@ -540,10 +645,13 @@ public:
            }
        }
    }
+
    /**
     Calls delete on all of the keys.  Does not clear the table,
     however, so you are left with a table of dangling pointers.
+
     Same as <CODE>getKeys().deleteAll();</CODE>
+
     To delete all of the values, you may want something like
     <PRE>
         Array<Key> keys = table.getKeys();
@@ -558,10 +666,12 @@ public:
    void deleteKeys() {
        getKeys().deleteAll();
    }
+
    /**
     Calls delete on all of the values.  This is unsafe--
     do not call unless you know that each value appears
     at most once.
+
     Does not clear the table, so you are left with a table
     of dangling pointers.
     */
@@ -575,9 +685,12 @@ public:
        }
    }
 };
+
 } // namespace
+
 #ifdef G3D_WIN32
 #   pragma warning (pop)
 #endif
+
 #endif