table.h

WOW 服务模拟端 支持2.4.3版本 来自开源的ASCENT 自己REPACK

/**
  @file Table.h

  Templated hash table class.

  @maintainer Morgan McGuire, [e-mail]
  @cite Bug fix by Darius Jazayeri, [e-mail]

  @created 2001-04-22
  @edited  2005-09-12
  Copyright 2000-2005, 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 <assert.h>
#include <string>
#include <locale>

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

namespace G3D {
class Hashable {
public:
    virtual size_t hashCode() const = 0;
    
    /**
     An empty virtual destructor for virtual methods.
    */
    virtual ~Hashable() {}
};
}

/**
 Int hashing function for use with Table.
 */
inline size_t hashCode(const int a) {
	return static_cast<size_t>(a);
}

inline size_t hashCode(const uint32 a) {
	return static_cast<size_t>(a);
}

inline size_t hashCode(const uint64 a) {
	return static_cast<size_t>(a);
}

inline size_t hashCode(const void* a) {
	// Avoid 64-bit pointer cast problems by turning
	// the pointer itself into an array of integers.
	//int* intPtr = (int*)(((unsigned char*)&a) + (sizeof(void*) - sizeof(int)));
	//return *intPtr;

	// sucks - burlex :P
	// use a 64bit hash code instead !
	// void* and size_t should be equal types (4byte on x86, 8byte on x64)
	return reinterpret_cast<size_t>(a);
}

/**
 Default class pointer hash.
 */
inline size_t hashCode(const G3D::Hashable* a) {
    return a->hashCode();
}

/**
 Default class hash.
 */
inline size_t hashCode(const G3D::Hashable& a) {
    return a.hashCode();
}

/**
 String hashing function for use with Table.
 */
inline size_t hashCode(const std::string& a) {
    //static const std::collate<char>& col = std::use_facet< std::collate<char> > (std::locale::empty( ));
    //return col.hash(a.c_str(), a.c_str() + a.size());

	// burlex - this shouldn't be done with only 4 bytes, collisions are possible
	// although i don't think we use std::strings much in this class
    return static_cast<size_t>(G3D::Crypto::crc32(a.c_str(), a.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 the following <B>two</B> functions: 

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

 G3D pre-defines hash 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>
  size_t hashCode(const MyEnum& x) { return (unsigned int)x; };
  </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 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());
        }
    };


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