40 #include <Inventor/SbBasic.h> 41 #include <Inventor/lists/SbList.h> 54 template <
class Type,
class Key>
64 void operator delete(
void * ptr) {
81 template <
class Type,
class Key>
88 SbHash(
unsigned int sizearg = 256,
float loadfactorarg = 0.0f)
90 this->commonConstructor(sizearg, loadfactorarg);
95 this->commonConstructor(from.size, from.loadfactor);
102 from.
apply(SbHash::copy_data,
this);
110 delete [] this->buckets;
116 for ( i = 0; i < this->size; i++ ) {
117 while ( this->buckets[i] ) {
119 this->buckets[i] = entry->
next;
127 SbBool
put(
const Key & key,
const Type & obj)
129 unsigned int i = this->
getIndex(key);
132 if ( entry->
key == key ) {
146 entry->
next = this->buckets[i];
147 this->buckets[i] = entry;
149 if ( this->elements++ >= this->threshold ) { this->
resize(this->size * 2); }
153 SbBool
get(
const Key & key, Type & obj)
const 156 unsigned int i = this->
getIndex(key);
157 entry = this->buckets[i];
159 if ( entry->
key == key ) {
168 SbBool
remove(
const Key & key)
170 unsigned int i = this->
getIndex(key);
174 if ( entry->
key == key ) {
177 this->buckets[i] = next;
195 for ( i = 0; i < this->size; i++ ) {
196 elem = this->buckets[i];
198 func(elem->
key, elem->
obj, closure);
206 this->
apply(SbHash::add_to_list, &l);
215 return (uintptr_t) key;
219 unsigned int idx = this->hashfunc(key);
221 return idx & (this->size - 1);
226 if (this->size >= newsize)
return;
229 unsigned int oldsize = this->size;
232 this->size = newsize;
234 this->threshold = (
unsigned int) (newsize * this->loadfactor);
240 for ( i = 0; i < oldsize; i++ ) {
249 delete [] oldbuckets;
253 void commonConstructor(
unsigned int sizearg,
float loadfactorarg)
255 if ( loadfactorarg <= 0.0f ) { loadfactorarg = 0.75f; }
257 while ( s < sizearg ) { s <<= 1; }
261 this->threshold = (
unsigned int) (s * loadfactorarg);
262 this->loadfactor = loadfactorarg;
268 void getStats(
int & buckets_used,
int & buckets,
int & elements,
float & chain_length_avg,
int & chain_length_max)
271 buckets_used = 0, chain_length_max = 0;
272 for ( i = 0; i < this->size; i++ ) {
273 if ( this->buckets[i] ) {
274 unsigned int chain_l = 0;
281 if ( chain_l > chain_length_max ) { chain_length_max = chain_l; }
284 buckets = this->size;
285 elements = this->elements;
286 chain_length_avg = (float) this->elements / buckets_used;
289 static void copy_data(
const Key & key,
const Type & obj,
void * closure)
292 thisp->
put(key, obj);
295 static void add_to_list(
const Key & key,
const Type & obj,
void * closure)
303 unsigned int elements;
304 unsigned int threshold;
311 #endif // !COIN_SBHASH_H SbHash & operator=(const SbHash &from)
Definition: SbHash.h:99
struct cc_memalloc cc_memalloc
void setHashFunc(SbHashFunc *func)
Definition: SbHash.h:211
unsigned int getIndex(const Key &key) const
Definition: SbHash.h:218
void makeKeyList(SbList< Key > &l) const
Definition: SbHash.h:204
void resize(unsigned int newsize)
Definition: SbHash.h:224
void SbHashApplyFunc(const Key &key, const Type &obj, void *closure)
Definition: SbHash.h:85
SbHashEntry< Type, Key > * next
Definition: SbHash.h:75
void append(const Type item)
Definition: SbList.h:187
cc_memalloc * memhandler
Definition: SbHash.h:76
static uintptr_t default_hash_func(const Key &key)
Definition: SbHash.h:214
cc_memalloc * cc_memalloc_construct(const unsigned int unitsize)
void cc_memalloc_destruct(cc_memalloc *allocator)
void * cc_memalloc_allocate(cc_memalloc *allocator)
unsigned int getNumElements(void) const
Definition: SbHash.h:209
Type obj
Definition: SbHash.h:74
uintptr_t SbHashFunc(const Key &key)
Definition: SbHash.h:84
SbBool put(const Key &key, const Type &obj)
Definition: SbHash.h:127
~SbHash()
Definition: SbHash.h:106
void apply(SbHashApplyFunc *func, void *closure) const
Definition: SbHash.h:191
SbHash(const SbHash &from)
Definition: SbHash.h:93
void cc_memalloc_deallocate(cc_memalloc *allocator, void *ptr)
SbHash(unsigned int sizearg=256, float loadfactorarg=0.0f)
Definition: SbHash.h:88
Key key
Definition: SbHash.h:73
void clear(void)
Definition: SbHash.h:113