Coin Logo Coin3D is Free Software,
published under the BSD 3-clause license.
https://bitbucket.org/Coin3D/
http://www.kongsberg.com/kogt/
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
SbHash.h
Go to the documentation of this file.
1 #ifndef COIN_SBHASH_H
2 #define COIN_SBHASH_H
3 
4 /**************************************************************************\
5  * Copyright (c) Kongsberg Oil & Gas Technologies AS
6  * All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions are
10  * met:
11  *
12  * Redistributions of source code must retain the above copyright notice,
13  * this list of conditions and the following disclaimer.
14  *
15  * Redistributions in binary form must reproduce the above copyright
16  * notice, this list of conditions and the following disclaimer in the
17  * documentation and/or other materials provided with the distribution.
18  *
19  * Neither the name of the copyright holder nor the names of its
20  * contributors may be used to endorse or promote products derived from
21  * this software without specific prior written permission.
22  *
23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
27  * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
29  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
30  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
31  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
32  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
33  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 \**************************************************************************/
35 
36 #include <cassert>
37 #include <cstddef> // NULL
38 #include <cstring> // memset()
39 
40 #include <Inventor/SbBasic.h>
41 #include <Inventor/lists/SbList.h>
43 
44 // *************************************************************************
45 
46 // We usually implement inline functions below the class definition,
47 // since we think that makes the file more readable. However, this is
48 // not done for this class, since Microsoft Visual C++ is not too
49 // happy about having functions declared as inline for a template
50 // class.
51 
52 // *************************************************************************
53 
54 template <class Type, class Key>
55 class SbHashEntry {
56 public:
57 
58  void * operator new(size_t size, cc_memalloc * memhandler) {
61  entry->memhandler = memhandler;
62  return (void*) entry;
63  }
64  void operator delete(void * ptr) {
67  }
68  void operator delete(void * ptr, cc_memalloc * memhandler) {
71  }
72 
73  Key key;
74  Type obj;
77 };
78 
79 // *************************************************************************
80 
81 template <class Type, class Key>
82 class SbHash {
83 public:
84  typedef uintptr_t SbHashFunc(const Key & key);
85  typedef void SbHashApplyFunc(const Key & key, const Type & obj, void * closure);
86 
87 public:
88  SbHash(unsigned int sizearg = 256, float loadfactorarg = 0.0f)
89  {
90  this->commonConstructor(sizearg, loadfactorarg);
91  }
92 
93  SbHash(const SbHash & from)
94  {
95  this->commonConstructor(from.size, from.loadfactor);
96  this->operator=(from);
97  }
98 
99  SbHash & operator=(const SbHash & from)
100  {
101  this->clear();
102  from.apply(SbHash::copy_data, this);
103  return *this;
104  }
105 
107  {
108  this->clear();
109  cc_memalloc_destruct(this->memhandler);
110  delete [] this->buckets;
111  }
112 
113  void clear(void)
114  {
115  unsigned int i;
116  for ( i = 0; i < this->size; i++ ) {
117  while ( this->buckets[i] ) {
118  SbHashEntry<Type, Key> * entry = this->buckets[i];
119  this->buckets[i] = entry->next;
120  delete entry;
121  }
122  }
123  memset(this->buckets, 0, this->size * sizeof(SbHashEntry<Type, Key> *));
124  this->elements = 0;
125  }
126 
127  SbBool put(const Key & key, const Type & obj)
128  {
129  unsigned int i = this->getIndex(key);
130  SbHashEntry<Type, Key> * entry = this->buckets[i];
131  while ( entry ) {
132  if ( entry->key == key ) {
133  /* Replace the old value */
134  entry->obj = obj;
135  return FALSE;
136  }
137  entry = entry->next;
138  }
139 
140  /* Key not already in the hash table; insert a new
141  * entry as the first element in the bucket
142  */
143  entry = new (this->memhandler) SbHashEntry<Type, Key>;
144  entry->key = key;
145  entry->obj = obj;
146  entry->next = this->buckets[i];
147  this->buckets[i] = entry;
148 
149  if ( this->elements++ >= this->threshold ) { this->resize(this->size * 2); }
150  return TRUE;
151  }
152 
153  SbBool get(const Key & key, Type & obj) const
154  {
155  SbHashEntry<Type, Key> * entry;
156  unsigned int i = this->getIndex(key);
157  entry = this->buckets[i];
158  while ( entry ) {
159  if ( entry->key == key ) {
160  obj = entry->obj;
161  return TRUE;
162  }
163  entry = entry->next;
164  }
165  return FALSE;
166  }
167 
168  SbBool remove(const Key & key)
169  {
170  unsigned int i = this->getIndex(key);
171  SbHashEntry<Type, Key> * entry = this->buckets[i], * next, * prev = NULL;
172  while ( entry ) {
173  next = entry->next;
174  if ( entry->key == key ) {
175  this->elements--;
176  if ( prev == NULL) {
177  this->buckets[i] = next;
178  }
179  else {
180  prev->next = next;
181  }
182  delete entry;
183  return TRUE;
184  }
185  prev = entry;
186  entry = next;
187  }
188  return FALSE;
189  }
190 
191  void apply(SbHashApplyFunc * func, void * closure) const
192  {
193  unsigned int i;
194  SbHashEntry<Type, Key> * elem;
195  for ( i = 0; i < this->size; i++ ) {
196  elem = this->buckets[i];
197  while ( elem ) {
198  func(elem->key, elem->obj, closure);
199  elem = elem->next;
200  }
201  }
202  }
203 
204  void makeKeyList(SbList<Key> & l) const
205  {
206  this->apply(SbHash::add_to_list, &l);
207  }
208 
209  unsigned int getNumElements(void) const { return this->elements; }
210 
211  void setHashFunc(SbHashFunc * func) { this->hashfunc = func; }
212 
213 protected:
214  static uintptr_t default_hash_func(const Key & key) {
215  return (uintptr_t) key;
216  }
217 
218  unsigned int getIndex(const Key & key) const {
219  unsigned int idx = this->hashfunc(key);
220  idx -= (idx << 7); /* i.e. key = key * -127; */
221  return idx & (this->size - 1);
222  }
223 
224  void resize(unsigned int newsize) {
225  /* we don't shrink the table */
226  if (this->size >= newsize) return;
227  /* assert(coin_is_power_of_two(newsize)); */
228 
229  unsigned int oldsize = this->size;
230  SbHashEntry<Type, Key> ** oldbuckets = this->buckets;
231 
232  this->size = newsize;
233  this->elements = 0;
234  this->threshold = (unsigned int) (newsize * this->loadfactor);
235  this->buckets = new SbHashEntry<Type, Key> * [newsize];
236  memset(this->buckets, 0, this->size * sizeof(SbHashEntry<Type, Key> *));
237 
238  /* Transfer all mappings */
239  unsigned int i;
240  for ( i = 0; i < oldsize; i++ ) {
241  SbHashEntry<Type, Key> * entry = oldbuckets[i];
242  while ( entry ) {
243  this->put(entry->key, entry->obj);
244  SbHashEntry<Type, Key> * preventry = entry;
245  entry = entry->next;
246  delete preventry;
247  }
248  }
249  delete [] oldbuckets;
250  }
251 
252 private:
253  void commonConstructor(unsigned int sizearg, float loadfactorarg)
254  {
255  if ( loadfactorarg <= 0.0f ) { loadfactorarg = 0.75f; }
256  unsigned int s = 1;
257  while ( s < sizearg ) { s <<= 1; } // power-of-two size
258  this->memhandler = cc_memalloc_construct(sizeof(SbHashEntry<Type, Key>));
259  this->size = s;
260  this->elements = 0;
261  this->threshold = (unsigned int) (s * loadfactorarg);
262  this->loadfactor = loadfactorarg;
263  this->buckets = new SbHashEntry<Type, Key> * [this->size];
264  memset(this->buckets, 0, this->size * sizeof(SbHashEntry<Type, Key> *));
265  this->hashfunc = default_hash_func;
266  }
267 
268  void getStats(int & buckets_used, int & buckets, int & elements, float & chain_length_avg, int & chain_length_max)
269  {
270  unsigned int i;
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;
275  SbHashEntry<Type, Key> * entry = this->buckets[i];
276  buckets_used++;
277  while ( entry ) {
278  chain_l++;
279  entry = entry->next;
280  }
281  if ( chain_l > chain_length_max ) { chain_length_max = chain_l; }
282  }
283  }
284  buckets = this->size;
285  elements = this->elements;
286  chain_length_avg = (float) this->elements / buckets_used;
287  }
288 
289  static void copy_data(const Key & key, const Type & obj, void * closure)
290  {
291  SbHash * thisp = (SbHash *)closure;
292  thisp->put(key, obj);
293  }
294 
295  static void add_to_list(const Key & key, const Type & obj, void * closure)
296  {
297  SbList<Key> * l = (SbList<Key> *)closure;
298  l->append(key);
299  }
300 
301  float loadfactor;
302  unsigned int size;
303  unsigned int elements;
304  unsigned int threshold;
305 
306  SbHashEntry<Type, Key> ** buckets;
307  SbHashFunc * hashfunc;
308  cc_memalloc * memhandler;
309 };
310 
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
Definition: SbList.h:69
static uintptr_t default_hash_func(const Key &key)
Definition: SbHash.h:214
cc_memalloc * cc_memalloc_construct(const unsigned int unitsize)
Definition: SbHash.h:82
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
Definition: SbHash.h:55
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