[svn] * Proper SVN structureinit

--HG--
branch : trunk

1 files changed, 695 insertions, 0 deletions

diff --git a/dep/include/g3dlite/G3D/Table.h b/dep/include/g3dlite/G3D/Table.h
new file mode 100644
index 00000000000..285d774d24a
--- /dev/null
+++ b/dep/include/g3dlite/G3D/Table.h
@@ -0,0 +1,695 @@
+/**
+  @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"
+#include "G3D/System.h"
+#include "G3D/g3dmath.h"
+#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.
+ */
+template<class Key, class Value, class HashFunc = GHashCode<Key> > 
+class Table {
+public:
+
+    /**
+     The pairs returned by iterator.
+     */
+    class Entry {
+    public:
+        Key    key;
+        Value  value;
+    };
+
+private:
+    /**
+     Linked list nodes used internally by HashTable.
+     */
+    class Node {
+    public:
+        size_t      hashCode;
+        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;
+        */
+        Node* clone() {
+           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;
+        this->bucket = (Node**)System::alignedMalloc(sizeof(Node*) * numBuckets, 16);
+        System::memset(this->bucket, 0, sizeof(Node*) * numBuckets);
+        for (size_t b = 0; b < this->numBuckets; b++) {
+            if (h.bucket[b] != NULL) {
+                bucket[b] = h.bucket[b]->clone();
+            }
+        }
+    }
+
+    /**
+     Frees the heap structures for the nodes.
+     */
+    void freeMemory() {
+        for (size_t b = 0; b < numBuckets; b++) {
+           Node* node = bucket[b];
+           while (node != NULL) {
+                Node* next = node->next;
+                delete node;
+                node = next;
+           }
+        }
+        System::alignedFree(bucket);
+        bucket     = NULL;
+        numBuckets = 0;
+        _size     = 0;
+    }
+
+public:
+
+    /**
+     Creates an empty hash table.  This causes some heap allocation to occur.
+     */
+    Table() {
+        numBuckets = 10;
+        _size      = 0;
+        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
+    deallocate things that the table points at, use getKeys() and Array::deleteAll()
+    to delete them.
+    */
+    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) {
+            // Free the existing nodes
+            freeMemory();
+            this->copyFrom(h);
+        }
+        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];
+            while (node != NULL) {
+                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 
+     the hash table is acting poorly-- all operations will be very slow.
+     A large load will result from a bad hash function that maps too
+     many keys to the same code.
+     */
+    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.
+         */
+        Node*               node;
+        Table<Key, Value>*  table;
+        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.
+         */
+        void findNext() {
+            while (node == NULL) {
+                index++;
+                if (index >= numBuckets) {
+                    isDone = true;
+                    break;
+                } else {
+                    node = bucket[index];
+                }
+            }
+        }
+
+    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.
+                return (isDone == other.isDone) && (other.table == table);
+            } else {
+                return
+                    (table == other.table) &&
+                    (node == other.node) && 
+                    (index == other.index);
+            }
+        }
+
+        /**
+         Pre increment.
+         */
+        Iterator& operator++() {
+            node = node->next;
+            findNext();
+            return *this;
+        }
+
+        /**
+         Post increment (slower than preincrement).
+         */
+        Iterator operator++(int) {
+            Iterator old = *this;
+            ++(*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
+     the next element.  Do not modify the table while iterating.
+     */
+    Iterator begin() const {
+        return Iterator(this, numBuckets, bucket);
+    }
+
+    /**
+     C++ STL style iterator method.  Returns one after the last iterator
+     element.
+     */
+    const Iterator end() const {
+        return Iterator(this);
+    }
+
+    /**
+     Removes all elements
+     */
+    void clear() {
+         freeMemory();
+         numBuckets = 20;
+         _size = 0;
+         bucket = (Node**)System::alignedMalloc(sizeof(Node*) * numBuckets, 16);
+         System::memset(bucket, 0, sizeof(Node*) * numBuckets);
+    }
+
+   
+    /**
+     Returns the number of keys.
+     */
+    size_t size() const {
+        return _size;
+    }
+
+
+    /**
+     If you insert a pointer into the key or value of a table, you are
+     responsible for deallocating the object eventually.  Inserting 
+     key into a table is O(1), but may cause a potentially slow rehashing.
+     */
+    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)) {
+              // This is the node; remove it
+              if (previous == NULL) {
+                  bucket[b] = n->next;
+              } else {
+                  previous->next = n->next;
+              }
+              // Delete the node
+              delete n;
+              --_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.
+    */
+   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
+             val = node->entry.value;
+             return true;
+          }
+          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;
+       } while (node != NULL);
+
+       return false;
+   }
+
+
+   /**
+    Short syntax for get.
+    */
+   inline Value& operator[](const Key &key) const {
+      return get(key);
+   }
+
+
+   /**
+    Returns an array of all of the keys in the table.
+    You can iterate over the keys to get the values.
+    */
+   Array<Key> getKeys() const {
+       Array<Key> keyArray;
+       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++) {
+           Node* node = bucket[i];
+           while (node != NULL) {
+               keyArray.append(node->entry.key);
+               node = node->next;
+           }
+       }
+   }
+
+   /**
+    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();
+        Set<Value> value;
+        for (int k = 0; k < keys.length(); k++) {
+           value.insert(keys[k]);
+        }
+        value.getMembers().deleteAll();
+        keys.deleteAll();
+    </PRE>
+    */
+   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.
+    */
+   void deleteValues() {
+       for (int i = 0; i < numBuckets; i++) {
+           Node* node = bucket[i];
+           while (node != NULL) {
+               delete node->entry.value;
+               node = node->next;
+           }
+       }
+   }
+};
+
+} // namespace
+
+#ifdef G3D_WIN32
+#   pragma warning (pop)
+#endif
+
+#endif