diff options
Diffstat (limited to 'extern/softbody/src/sdfgen/hashtable.h')
| -rw-r--r-- | extern/softbody/src/sdfgen/hashtable.h | 252 |
1 files changed, 0 insertions, 252 deletions
diff --git a/extern/softbody/src/sdfgen/hashtable.h b/extern/softbody/src/sdfgen/hashtable.h deleted file mode 100644 index c81fb59ea91..00000000000 --- a/extern/softbody/src/sdfgen/hashtable.h +++ /dev/null @@ -1,252 +0,0 @@ -#ifndef HASHTABLE_H -#define HASHTABLE_H - -#include <functional> -#include <iostream> -#include <vector> - -namespace sdfgen { - -template<class Key, class Data> -struct HashEntry -{ - Key key; - Data data; - int next; -}; - -// a useful core hash function -inline unsigned int hash(unsigned int k) -{ return k*2654435769u; } - -// default hash function object -struct DefaultHashFunction -{ - template<typename Key> - unsigned int operator() (const Key &k) const { return hash(k); } -}; - -struct equal -{ - template<typename T> - bool operator() (const T &a, const T &b) const { return a==b; } -}; - -template<typename Key, typename Data, class HashFunction=DefaultHashFunction, class KeyEqual=equal> -struct HashTable -{ - unsigned int table_rank; - unsigned int table_bits; - std::vector<int> table; - unsigned int num_entries; - std::vector<HashEntry<Key, Data> > pool; - int free_list; - const HashFunction hash_function; - const KeyEqual key_equal; - - explicit HashTable(unsigned int expected_size=64) - : hash_function(HashFunction()), key_equal(KeyEqual()) - { init(expected_size); } - - explicit HashTable(const HashFunction &hf, unsigned int expected_size=64) - : hash_function(hf), key_equal(KeyEqual()) - { init(expected_size); } - - void init(unsigned int expected_size) - { - unsigned int i; - num_entries=0; - table_rank=4; - while(1u<<table_rank < expected_size) - ++table_rank; - ++table_rank; // give us some extra room - table_bits=(1u<<table_rank)-1; - table.resize(1u<<table_rank); - for(i=0; i<table.size(); ++i) - table[i]=-1; // empty list - pool.resize(1u<<table_rank); - free_list=0; - for(unsigned int i=0; i<pool.size()-1; ++i) - pool[i].next=i+1; - pool[pool.size()-1].next=-1; // end of free list - } - - void add(const Key &k, const Data &d) - { - if(free_list==-1) - reserve(1u<<(table_rank+1)); - int i=free_list; // where we're going to put the new entry - free_list=pool[i].next; - unsigned int t=hash_function(k)&table_bits; // index into table - pool[i].key=k; - pool[i].data=d; - pool[i].next=table[t]; // put the new entry at the start of table[t]'s list - table[t]=i; - ++num_entries; - } - - void delete_entry(const Key &k, const Data &d) // delete first entry that matches both key and data - { - unsigned int t=hash_function(k)&table_bits; - int i=table[t], *p_i=&table[t]; - while(i!=-1){ - if(key_equal(k, pool[i].key) && d==pool[i].data){ - *p_i=pool[i].next; // make list skip over this entry - pool[i].next=free_list; // and put it on the front of the free list - free_list=i; - return; // and we're done - } - p_i=&pool[i].next; - i=*p_i; - } - } - - unsigned int size() const - { return num_entries; } - - void clear() - { - unsigned int i=0; - num_entries=0; - for(i=0; i<table.size(); ++i) - table[i]=-1; // empty list - free_list=0; - for(i=0; i<pool.size()-1; ++i) - pool[i].next=i+1; - pool[pool.size()-1].next=-1; - } - - void reserve(unsigned int expected_size) - { - if(expected_size<=pool.size()) - return; - while(1u<<table_rank < expected_size) - ++table_rank; - table_bits=(1u<<table_rank)-1; - // increase room for new entries - unsigned int old_size=(unsigned int)pool.size(), i; - pool.resize(1u<<table_rank); - for(i=old_size; i<pool.size()-1; ++i) - pool[i].next=i+1; - pool[i].next=free_list; - free_list=old_size; - // And finally need to redo table (rehash entries) - old_size=(unsigned int)table.size(); - table.resize(1u<<table_rank); - unsigned int t; - for(t=old_size; t<table.size(); ++t) - table[t]=-1; // initially make new lists empty - int j, *p_j; - for(t=0; t<old_size; ++t){ - j=table[t]; - p_j=&table[t]; - while(j!=-1){ - unsigned int new_t=hash_function(pool[j].key)&table_bits; - if(new_t!=t){ // j doesn't belong in this list anymore? - // delete from this list - *p_j=pool[j].next; - // add to correct list - pool[j].next=table[new_t]; - table[new_t]=j; - }else - p_j=&(pool[j].next); - j=*p_j; - } - } - } - - bool has_entry(const Key &k) const - { - unsigned int t=hash_function(k)&table_bits; - int i=table[t]; - while(i!=-1){ - if(key_equal(k, pool[i].key)) - return true; - i=pool[i].next; - } - return false; - } - - bool get_entry(const Key &k, Data &data_return) const - { - unsigned int t=hash_function(k)&table_bits; - int i=table[t]; - while(i!=-1){ - if(key_equal(k, pool[i].key)){ - data_return=pool[i].data; - return true; - } - i=pool[i].next; - } - return false; - } - - void append_all_entries(const Key& k, std::vector<Data>& data_return) const - { - unsigned int t=hash_function(k)&table_bits; - int i=table[t]; - while(i!=-1){ - if(key_equal(k, pool[i].key)) data_return.push_back(pool[i].data); - i=pool[i].next; - } - } - - Data &operator() (const Key &k, const Data &missing_data) - { - unsigned int t=hash_function(k)&table_bits; - int i=table[t]; - while(i!=-1){ - if(key_equal(k, pool[i].key)) - return pool[i].data; - i=pool[i].next; - } - add(k, missing_data); // note - this could cause the table to be resized, and t made out-of-date - return pool[table[hash_function(k)&table_bits]].data; // we know that add() puts it here! - } - - const Data &operator() (const Key &k, const Data &missing_data) const - { - unsigned int t=hash_function(k)&table_bits; - int i=table[t]; - while(i!=-1){ - if(key_equal(k, pool[i].key)) - return pool[i].data; - i=pool[i].next; - } - return missing_data; - } - - void output_statistics() const - { - std::vector<int> lengthcount(table.size()); - unsigned int t; - int total=0; - for(t=0; t<table.size(); ++t){ - int i=table[t], length=0; - while(i!=-1){ - ++length; - i=pool[i].next; - } - ++lengthcount[length]; - ++total; - } - int subtotal=0; - int maxlength=0; - for(t=0; t<lengthcount.size() && t<10; ++t){ - subtotal+=lengthcount[t]; - if(lengthcount[t]>0){ - std::cout<<"length "<<t<<": "<<lengthcount[t]<<" ("<<lengthcount[t]/(float)total*100.0<<"%)"<<std::endl; - maxlength=t; - } - } - std::cout<<"rest: "<<total-subtotal<<" ("<<100.0*(1.0-subtotal/(float)total)<<"%)"<<std::endl; - for(; t<lengthcount.size(); ++t) - if(lengthcount[t]>0) - maxlength=t; - std::cout<<"longest list: "<<maxlength<<std::endl; - } -}; - -} - -#endif |