path: root/dep/g3dlite/include/G3D/Table.h

/**
  @file Table.h

  Templated hash table class.

  @maintainer Morgan McGuire, http://graphics.cs.williams.edu
  @created 2001-04-22
  @edited  2013-01-22
  Copyright 2000-2013, Morgan McGuire.
  All rights reserved.
 */

#ifndef G3D_Table_h
#define G3D_Table_h

#include <cstddef>
#include <string>

#include "G3D/platform.h"
#include "G3D/Array.h"
#include "G3D/debug.h"
#include "G3D/System.h"
#include "G3D/g3dmath.h"
#include "G3D/EqualsTrait.h"
#include "G3D/HashTrait.h"
#include "G3D/MemoryManager.h"

#ifdef _MSC_VER
#   pragma warning (push)
    // Debug name too long warning
#   pragma warning (disable : 4786)
#endif

namespace G3D {

/**
 An unordered data structure mapping keys to values.

 There are two ways of definining custom hash functions (G3D provides built-in ones for most classes):

 <pre>
 class Foo {
 public:
     std::string     name;
     int             index;
     static size_t hashCode(const Foo& key) {
          return HashTrait<std::string>::hashCode(key.name) + key.index;
     }
  };

  template<> struct HashTrait<class Foo> {
       static size_t hashCode(const Foo& key) { return HashTrait<std::string>::hashCode(key.name) + key.index; }
  }; 


  // Use Foo::hashCode
  Table<Foo, std::string, Foo> fooTable1;

  // Use HashTrait<Foo>
  Table<Foo, std::string>      fooTable2;
  </pre>


 Key must be a pointer, an int, a std::string or provide overloads for: 

  <PRE>
    template<> struct HashTrait<class Key> {
        static size_t hashCode(const Key& key) { return reinterpret_cast<size_t>( ... ); }
    }; 
  </PRE>

  and one of 

  <PRE>
    template<> struct EqualsTrait<class Key>{
         static bool equals(const Key& a, const Key& b) { return ... ; }
    };


    bool operator==(const Key&, const Key&);
  </PRE>

 G3D pre-defines HashTrait specializations 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 HashTrait<MyEnum> {
        static size_t hashCode(const 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 = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key> > 
class Table {
public:

    /**
     The pairs returned by iterator.
     */
    class Entry {
    public:
        Key    key;
        Value  value;
        Entry() {}
        Entry(const Key& k) : key(k) {}
        Entry(const Key& k, const Value& v) : key(k), value(v) {}
        bool operator==(const Entry &peer) const { return (key == peer.key && value == peer.value); }
        bool operator!=(const Entry &peer) const { return !operator==(peer); }
    };

private:

    typedef Table<Key, Value, HashFunc, EqualsFunc> ThisType;

    /**
     Linked list nodes used internally by HashTable.
     */
    class Node {
    public:
        Entry       entry;
        size_t      hashCode;
        Node*       next;

    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:

        static Node* create(const Key& k, const Value& v, size_t h, Node* n, MemoryManager::Ref& mm) {
            Node* node = (Node*)mm->alloc(sizeof(Node));
            return new (node) Node(k, v, h, n);
        }

        static Node* create(const Key& k, size_t hashCode, Node* n, MemoryManager::Ref& mm) {
            Node* node = (Node*)mm->alloc(sizeof(Node));
            return new (node) Node(k, hashCode, n);
        }

        static void destroy(Node* n, MemoryManager::Ref& mm) {
            n->~Node();
            mm->free(n);
        }

        /**
        Clones a whole chain;
        */
        Node* clone(MemoryManager::Ref& mm) {
           return create(this->entry.key, this->entry.value, hashCode, (next == NULL) ? NULL : next->clone(mm), mm);
        }
    };

    void checkIntegrity() const {
#       ifdef G3D_DEBUG
           debugAssert(m_bucket == NULL || isValidHeapPointer(m_bucket));
           for (size_t b = 0; b < m_numBuckets; ++b) {
               Node* node = m_bucket[b];
               debugAssert(node == NULL || isValidHeapPointer(node));
               while (node != NULL) {
                   debugAssert(node == NULL || isValidHeapPointer(node));
                   node = node->next;
               }
           }
#       endif
    }

    /** Number of elements in the table.*/
    size_t              m_size;

    /**
     Array of Node*. 

     We don't use Array<Node*> because Table is lower-level than Array.
     Some elements may be NULL.
     */
    Node**              m_bucket;
    
    /**
     Length of the m_bucket array.
     */
    size_t              m_numBuckets;

    MemoryManager::Ref  m_memoryManager;

    void* alloc(size_t s) const {
        return m_memoryManager->alloc(s);
    }

    void free(void* p) const {
        return m_memoryManager->free(p);
    }

    /**
     Re-hashes for a larger m_bucket size.
     */
    void resize(size_t newSize) {

        // Hang onto the old m_bucket array
        Node** oldBucket = m_bucket;

        // 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*));
        // Move each node to its new hash location
        for (size_t b = 0; b < m_numBuckets; ++b) {
            Node* node = oldBucket[b];
         
            // There is a linked list of nodes at this m_bucket
            while (node != NULL) {
                // Hang onto the old next pointer
                Node* nextNode = node->next;
        
                // Insert at the head of the list for m_bucket[i]
                size_t i = node->hashCode % newSize;
                node->next = m_bucket[i];
                m_bucket[i] = node;

                // Move on to the next node
                node = nextNode;
            }

            // Drop the old pointer for cleanliness when debugging
            oldBucket[b] = NULL;
        }

        // Delete the old storage
        free(oldBucket);
        this->m_numBuckets = newSize;

        checkIntegrity();
    }


    void copyFrom(const ThisType& h) {
        if (&h == this) {
            return;
        }

        debugAssert(m_bucket == NULL);
        m_size = h.m_size;
        m_numBuckets = h.m_numBuckets;
        m_bucket = (Node**)alloc(sizeof(Node*) * m_numBuckets);
        // No need to NULL elements since we're about to overwrite them

        for (size_t b = 0; b < m_numBuckets; ++b) {
            if (h.m_bucket[b] != NULL) {
                m_bucket[b] = h.m_bucket[b]->clone(m_memoryManager);
            } else {
                m_bucket[b] = NULL;
            }
        }

        checkIntegrity();
    }

    /**
     Frees the heap structures for the nodes.
     */
    void freeMemory() {
        checkIntegrity();

        for (size_t b = 0; b < m_numBuckets; ++b) {
            Node* node = m_bucket[b];
            while (node != NULL) {
                Node* next = node->next;
                Node::destroy(node, m_memoryManager);
                node = next;
            }
            m_bucket[b] = NULL;
        }
        free(m_bucket);
        m_bucket     = NULL;
        m_numBuckets = 0;
        m_size       = 0;
    }

public:

    /**
     Creates an empty hash table using the default MemoryManager.
     */
    Table() : m_bucket(NULL) {
        m_memoryManager = MemoryManager::create();
        m_numBuckets = 0;
        m_size       = 0;
        m_bucket     = NULL;
        checkIntegrity();
    }

    /** Changes the internal memory manager to m */
    void clearAndSetMemoryManager(const MemoryManager::Ref& m) {
        clear();
        debugAssert(m_bucket == NULL);
        m_memoryManager = m;
    }

    /** 
        Recommends that the table resize to anticipate at least this number of elements.
     */
    void setSizeHint(size_t n) {
        size_t s = n * 3;
        if (s > m_numBuckets) {
            resize(s);
        }
    }
    
    /**
       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();
    }

    /** Uses the default memory manager */
    Table(const ThisType& h) {
        m_memoryManager = MemoryManager::create();
        m_numBuckets = 0;
        m_size = 0;
        m_bucket = NULL;
        this->copyFrom(h);
        checkIntegrity();
    }


    Table& operator=(const ThisType& h) {
        // No need to copy if the argument is this
        if (this != &h) {
            // Free the existing nodes
            freeMemory();
            this->copyFrom(h);
            checkIntegrity();
        }
        return *this;
    }

    /**
     Returns the length of the deepest m_bucket.
     */
    size_t debugGetDeepestBucketSize() const {
        size_t deepest = 0;

        for (size_t b = 0; b < m_numBuckets; ++b) {
            size_t  count = 0;
            Node*   node = m_bucket[b];
            while (node != NULL) {
                node = node->next;
                ++count;
            }

            if (count > deepest) {
                deepest = count;
            }
        }

        return deepest;
    }

    /**
       Returns the average size of non-empty buckets.
    */
    float debugGetAverageBucketSize() const {
        uint64 num = 0;

        for (size_t b = 0; b < m_numBuckets; ++b) {
            Node* node = m_bucket[b];
            if (node != NULL) {
                ++num;
            }
        }

        return (float)((double)size() / num);
    }

    /**
     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 (double)size() / m_numBuckets;
    }

    /**
     Returns the number of buckets.
     */
    size_t debugGetNumBuckets() const {
        return m_numBuckets;
    }

    /**
     C++ STL style iterator variable.  See begin().
     */
    class Iterator {
    private:
        friend class Table<Key, Value, HashFunc, EqualsFunc>;

        /**
         Bucket index.
         */
        size_t              index;

        /**
         Linked list node.
         */
        Node*               node;

        size_t              m_numBuckets;
        Node**              m_bucket;
        bool                isDone;

        /**
         Creates the end iterator.
         */
        Iterator() : index(0), node(NULL), m_bucket(NULL) {
            isDone = true;
        }

        Iterator(size_t numBuckets, Node** m_bucket) :
            index(0), 
            node(NULL),
            m_numBuckets(numBuckets),
            m_bucket(m_bucket) {
            
            if (m_numBuckets == 0) {
                // Empty table
                isDone = true;
                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));
        }

        /**
         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;
                if (index >= m_numBuckets) {
                    m_bucket = NULL;
                    index = 0;
                    isDone = true;
                    return;
                } else {
                    node = m_bucket[index];
                    debugAssert((node == NULL) || isValidHeapPointer(node));
                }
            }
            debugAssert(isValidHeapPointer(node));
        }

    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);
            } else {
                return (node == other.node) && (index == other.index);
            }
        }

        /**
         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;
        }

        /**
         Post increment (slower than preincrement).
         */
        Iterator operator++(int) {
            Iterator old = *this;
            ++(*this);
            return old;
        }

        const Entry& operator*() const {
            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 isValid() const {
            return ! isDone;
        }

        /** @deprecated  Use isValid */
        bool hasMore() const {
            return ! isDone;
        }
    };


    /**
     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(m_numBuckets, m_bucket);
    }

    /**
     C++ STL style iterator method.  Returns one after the last iterator
     element.
     */
    const Iterator end() const {
        return Iterator();
    }

    /**
     Removes all elements. Guaranteed to free all memory associated with
     the table.
     */
    void clear() {
        freeMemory();
        m_numBuckets = 0;
        m_size = 0;
        m_bucket = NULL;
    }

   
    /**
     Returns the number of keys.
     */
    size_t size() const {
        return m_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) {
        getCreateEntry(key).value = value;
    }

private:

    /** Helper for remove() and getRemove() */
    bool remove(const Key& key, Key& removedKey, Value& removedValue, bool updateRemoved) {
        if (m_numBuckets == 0) {
            return false;
        }
       
        const size_t code = HashFunc::hashCode(key);
        const size_t b = code % m_numBuckets;

        // Go to the m_bucket
        Node* n = m_bucket[b];

        if (n == NULL) {
            return false;
        }

        Node* previous = NULL;
      
        // Try to find the node
        do {
          if ((code == n->hashCode) && EqualsFunc::equals(n->entry.key, key)) {
              // This is the node; remove it

              // Replace the previous's next pointer
              if (previous == NULL) {
                  m_bucket[b] = n->next;
              } else {
                  previous->next = n->next;
              }

              if (updateRemoved) {
                  removedKey   = n->entry.key;
                  removedValue = n->entry.value;
              }
              // Delete the node
              Node::destroy(n, m_memoryManager);
              --m_size;

              //checkIntegrity();
              return true;
          }

          previous = n;
          n = n->next;
      } while (n != NULL);

      //checkIntegrity();
      return false;
   }

public:

   /** If @a member is present, sets @a removed to the element
    being removed and returns true.  Otherwise returns false
    and does not write to @a removed. */
    bool getRemove(const Key& key, Key& removedKey, Value& removedValue) {
       return remove(key, removedKey, removedValue, true);
    }

    /**
    Removes an element from the table if it is present.  
    @return true if the element was found and removed, otherwise  false
    */
   bool remove(const Key& key) {
       Key x;
       Value v;
       return remove(key, x, v, false);
   }

private:

   Entry* getEntryPointer(const Key& key) const {
       if (m_numBuckets == 0) {
           return NULL;
       }

       size_t  code = HashFunc::hashCode(key);
       size_t b = code % m_numBuckets;

       Node* node = m_bucket[b];

       while (node != NULL) {
           if ((node->hashCode == code) && EqualsFunc::equals(node->entry.key, key)) {
               return &(node->entry);
           }
           node = node->next;
       }

       return NULL;
   }

public:
   
    /** If a value that is EqualsFunc to @a member is present, returns a pointer to the 
        version stored in the data structure, otherwise returns NULL.
     */
   const Key* getKeyPointer(const Key& key) const {
       const Entry* e = getEntryPointer(key);
       if (e == NULL) {
           return NULL;
       } else {
           return &(e->key);
       }
   }

   /**
    Returns the value associated with key.
    @deprecated Use get(key, val) or getPointer(key) 
    */
   Value& get(const Key& key) const {
       Entry* e = getEntryPointer(key);
       debugAssertM(e != NULL, "Key not found");
       return e->value;
   }


   /** Returns a pointer to the element if it exists, or NULL if it does not.
       Note that if your value type <i>is</i> a pointer, the return value is 
       a pointer to a pointer.  Do not remove the element while holding this 
       pointer.

       It is easy to accidentally mis-use this method.  Consider making 
       a Table<Value*> and using get(key, val) instead, which makes you manage
       the memory for the values yourself and is less likely to result in 
       pointer errors.
     */
   Value* getPointer(const Key& key) const {
       if (m_numBuckets == 0) {
           return NULL;
       }

       size_t code = HashFunc::hashCode(key);
       size_t b = code % m_numBuckets;

       Node* node = m_bucket[b];

       while (node != NULL) {
          if ((node->hashCode == code) && EqualsFunc::equals(node->entry.key, key)) {
             // found key
             return &(node->entry.value);
          }
          node = node->next;
      }

      // Failed to find key
      return NULL;
   }

   /**
    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 {
       Value* v = getPointer(key);
       if (v != NULL) {
           val = *v;
           return true;
       } else {
           return false;
       }
   }


    /** Called by getCreate() and set() 
        
        \param created Set to true if the entry was created by this method.
    */  
    Entry& getCreateEntry(const Key& key, bool& created) {
        created = false;

        if (m_numBuckets == 0) {
            resize(10);
        }

        size_t code = HashFunc::hashCode(key);
        size_t b = code % m_numBuckets;
        
        // Go to the m_bucket
        Node* n = m_bucket[b];

        // No m_bucket, so this must be the first
        if (n == NULL) {
            m_bucket[b] = Node::create(key, code, NULL, m_memoryManager);
            ++m_size;
            created = true;
            //checkIntegrity();
            return m_bucket[b]->entry;
        }

        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) && EqualsFunc::equals(n->entry.key, key)) {
               // This is the a pre-existing node
               //checkIntegrity();
               return n->entry;
            }

            n = n->next;
            ++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 * bucketsPerElement)) {

            // This m_bucket was really large; rehash if all elements
            // don't have the same hashcode the number of buckets is
            // reasonable.

            // Back off the scale factor as the number of buckets gets 
            // large
            float f = 3.0f;
            if (m_numBuckets > 1000000) {
                f = 1.5f;
            } else if (m_numBuckets > 100000) {
                f = 2.0f;
            }
            int newSize = iMax((int)(m_numBuckets * f) + 1, (int)(m_size * f));
            resize(newSize);
        }

        // Not found; insert at the head.
        b = code % m_numBuckets;
        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;
        return getCreateEntry(key, ignore);
    }
    

    /** Returns the current value that key maps to, creating it if necessary.*/
    Value& getCreate(const Key& key) {
        return getCreateEntry(key).value;
    }

    /** \param created True if the element was created. */
    Value& getCreate(const Key& key, bool& created) {
        return getCreateEntry(key, created).value;
    }


   /**
    Returns true if key is in the table.
    */
   bool containsKey(const Key& key) const {
       if (m_numBuckets == 0) {
           return false;
       }

       size_t code = HashFunc::hashCode(key);
       size_t b = code % m_numBuckets;

       Node* node = m_bucket[b];

       while (node != NULL) {
           if ((node->hashCode == code) && EqualsFunc::equals(node->entry.key, key)) {
              return true;
           }
           node = node->next;
       }

       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.
    @deprecated
    */
   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 < m_numBuckets; ++i) {
           Node* node = m_bucket[i];
           while (node != NULL) {
               keyArray.append(node->entry.key);
               node = node->next;
           }
       }
   }

   /** 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) {
           Node* node = m_bucket[i];
           while (node != NULL) {
               delete node->entry.key;
               node->entry.key = NULL;
               node = node->next;
           }
       }
       clear();
   }

   /**
    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 NULL pointers.
    */
   void deleteValues() {
       for (size_t i = 0; i < m_numBuckets; ++i) {
           Node* node = m_bucket[i];
           while (node != NULL) {
               delete node->entry.value;
               node->entry.value = NULL;
               node = node->next;
           }
       }
   }

    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

#ifdef _MSC_VER
#   pragma warning (pop)
#endif

#endif