aboutsummaryrefslogtreecommitdiff
path: root/dep/include/g3dlite/G3D/Table.h
diff options
context:
space:
mode:
Diffstat (limited to 'dep/include/g3dlite/G3D/Table.h')
-rw-r--r--dep/include/g3dlite/G3D/Table.h113
1 files changed, 0 insertions, 113 deletions
diff --git a/dep/include/g3dlite/G3D/Table.h b/dep/include/g3dlite/G3D/Table.h
index 1d021daae2b..c1da412f3f3 100644
--- a/dep/include/g3dlite/G3D/Table.h
+++ b/dep/include/g3dlite/G3D/Table.h
@@ -1,18 +1,14 @@
/**
@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"
@@ -21,89 +17,71 @@
#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.
@@ -111,7 +89,6 @@ namespace G3D {
template<class Key, class Value, class HashFunc = GHashCode<Key> >
class Table {
public:
-
/**
The pairs returned by iterator.
*/
@@ -120,7 +97,6 @@ public:
Key key;
Value value;
};
-
private:
/**
Linked list nodes used internally by HashTable.
@@ -131,24 +107,20 @@ 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;
*/
@@ -156,54 +128,42 @@ 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;
@@ -215,7 +175,6 @@ private:
}
}
}
-
/**
Frees the heap structures for the nodes.
*/
@@ -233,9 +192,7 @@ private:
numBuckets = 0;
_size = 0;
}
-
public:
-
/**
Creates an empty hash table. This causes some heap allocation to occur.
*/
@@ -245,7 +202,6 @@ 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
@@ -255,11 +211,9 @@ 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) {
@@ -269,13 +223,11 @@ 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];
@@ -283,15 +235,12 @@ 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
@@ -302,26 +251,22 @@ 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.
*/
@@ -330,31 +275,26 @@ 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.
@@ -370,12 +310,10 @@ 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.
@@ -387,7 +325,6 @@ public:
(index == other.index);
}
}
-
/**
Pre increment.
*/
@@ -396,7 +333,6 @@ public:
findNext();
return *this;
}
-
/**
Post increment (slower than preincrement).
*/
@@ -405,21 +341,17 @@ 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
@@ -428,7 +360,6 @@ public:
Iterator begin() const {
return Iterator(this, numBuckets, bucket);
}
-
/**
C++ STL style iterator method. Returns one after the last iterator
element.
@@ -436,7 +367,6 @@ public:
const Iterator end() const {
return Iterator(this);
}
-
/**
Removes all elements
*/
@@ -448,7 +378,6 @@ public:
System::memset(bucket, 0, sizeof(Node*) * numBuckets);
}
-
/**
Returns the number of keys.
*/
@@ -456,7 +385,6 @@ 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
@@ -465,68 +393,53 @@ 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)) {
@@ -541,39 +454,31 @@ 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.
@@ -581,9 +486,7 @@ 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
@@ -592,31 +495,25 @@ 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.
*/
@@ -624,7 +521,6 @@ 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.
@@ -634,7 +530,6 @@ 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++) {
@@ -645,13 +540,10 @@ 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();
@@ -666,12 +558,10 @@ 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.
*/
@@ -685,12 +575,9 @@ public:
}
}
};
-
} // namespace
-
#ifdef G3D_WIN32
# pragma warning (pop)
#endif
-
#endif