COVISE Core
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros
coMultiHashBase.h
Go to the documentation of this file.
1 /* This file is part of COVISE.
2 
3  You can use it under the terms of the GNU Lesser General Public License
4  version 2.1 or later, see lgpl-2.1.txt.
5 
6  * License: LGPL 2+ */
7 
8 #ifndef __CO_MULTI_HASH_BASE_H
9 #define __CO_MULTI_HASH_BASE_H
10 
11 #include "coExport.h"
12 
13 #include <assert.h>
14 
15 namespace covise
16 {
17 
18 template <class KEY, class DATA>
19 class coHashIter;
20 template <class KEY, class DATA>
21 class coHashBase;
22 
40 template <class KEY, class DATA>
41 class coMultiHashBase
42 {
43 
44  friend class coHashIter<KEY, DATA>;
45  friend class coHashBase<KEY, DATA>;
46 
47 private:
48  // Null element
49  DATA d_nullElem;
50 
51  // the data associated to the keys
52  DATA *data;
53 
54  // number of entries in the list
55  unsigned int entries;
56 
57  // if entries>maxEntries then resize the list
58  unsigned int maxEntries;
59 
60  // index of prime in the primeList
62 
63  // resize the table if necessary
64  void resize(void);
65 
66  // percentage of filling when to resize the table
67  //static const float fillFactor;
68 
69  // +++++++++++ number of primes available
70  enum
71  {
72  NUMPRIMES = 28
73  };
74 
75  // +++++++++++ the primes themselves
76  //static const unsigned long primeList[NUMPRIMES];
77 
78 protected:
79  // flag values for entry field
80  enum
81  {
82  EMPTY = 0,
85  };
86 
87  // keys
88  KEY *keys;
89 
90  // list with flags if the associated entry is used or not
91  // values: EMPTY, PREVIOUS(ly used), USED
92  unsigned char *entryFlags;
93 
95  unsigned int size;
96 
98  unsigned int prime;
99 
100 public:
102  coMultiHashBase();
103 
105  coMultiHashBase(DATA nullelem);
106 
108  const DATA &getNullElem() const
109  {
110  return d_nullElem;
111  };
112 
114  virtual ~coMultiHashBase();
115 
117  virtual int insert(const KEY &key, const DATA &inData);
118 
120  int remove(unsigned long hashIndex);
121 
123  void removeAll();
124 
126  unsigned long getHash(const KEY &key) const;
127 
129  DATA &operator[](unsigned long hashIndex);
130 
132  const DATA &operator[](unsigned long hashIndex) const;
133 
135  virtual unsigned long nextHash(unsigned long hashIndex) const;
136 
138  int getNumEntries() const;
139 
141  virtual unsigned long hash1(const KEY &) const = 0;
142 
144  virtual unsigned long hash2(const KEY &) const = 0;
145 
147  virtual bool equal(const KEY &, const KEY &) const = 0;
148 };
149 
150 // +++++++++++ Create a hash table
151 
152 template <class KEY, class DATA>
154 {
155  static unsigned long primeList[NUMPRIMES] = {
156  53ul, 97ul, 193ul, 389ul, 769ul,
157  1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
158  49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
159  1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
160  50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
161  1610612741ul, 3221225473ul, 4294967291ul
162  };
163 
164  // create the list
165  primeIndex = 0;
166  prime = primeList[primeIndex];
167  size = prime;
168  entries = 0;
169  //fillFactor
170  maxEntries = (unsigned int)(((float)size) * 0.75);
171 
172  // and allocate the key and data storage
173  this->keys = new KEY[size];
174  this->data = new DATA[size];
175  entryFlags = new unsigned char[size];
176 
177  unsigned long i;
178 
179  for (i = 0; i < size; i++)
180  entryFlags[i] = ((unsigned char)EMPTY);
181 
182  // done
183  return;
184 }
185 
186 // +++++++++++ Create a hash table
187 
188 template <class KEY, class DATA>
190 {
191  static unsigned long primeList[NUMPRIMES] = {
192  53ul, 97ul, 193ul, 389ul, 769ul,
193  1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
194  49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
195  1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
196  50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
197  1610612741ul, 3221225473ul, 4294967291ul
198  };
199  // create the list
200  primeIndex = 0;
201  prime = primeList[primeIndex];
202  size = prime;
203  entries = 0;
204  d_nullElem = nullelem;
205  //fillFactor
206  maxEntries = (unsigned int)(((float)size) * 0.75);
207 
208  // and allocate the key and data storage
209  this->keys = new KEY[size];
210  this->data = new DATA[size];
211  entryFlags = new unsigned char[size];
212 
213  unsigned long i;
214 
215  for (i = 0; i < size; i++)
216  {
217  entryFlags[i] = ((unsigned char)EMPTY);
218  this->data[i] = d_nullElem;
219  }
220 
221  // done
222  return;
223 }
224 
225 // +++++++++++ remove all elements from
226 
227 template <class KEY, class DATA>
229 {
230  unsigned long i;
231 
232  for (i = 0; i < size; i++)
233  {
234  entryFlags[i] = ((unsigned char)EMPTY);
235  this->data[i] = d_nullElem;
236  }
237 
238  // done
239  return;
240 }
241 
242 // +++++++++++ Delete a hash table
243 
244 template <class KEY, class DATA>
246 {
247  // clean up
248  delete[] this->keys;
249  delete[] this->data;
250  delete[] entryFlags;
251  return;
252 }
253 
254 // +++++++++++ resize a hash table
255 // AW: only called if needed
256 
257 template <class KEY, class DATA>
259 {
260  // save old table
261  KEY *oldKeys = this->keys;
262  DATA *oldData = this->data;
263  unsigned int oldSize = size;
264  unsigned char *oldFlags = entryFlags;
265 
266  static unsigned long primeList[NUMPRIMES] = {
267  53ul, 97ul, 193ul, 389ul, 769ul,
268  1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
269  49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
270  1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
271  50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
272  1610612741ul, 3221225473ul, 4294967291ul
273  };
274  // initialize new table
275  primeIndex++;
276  prime = primeList[primeIndex];
277  size = prime;
278  entries = 0L;
279  //fillFactor
280  maxEntries = (unsigned int)(((float)size) * 0.75);
281  this->keys = new KEY[size];
282  this->data = new DATA[size];
283  entryFlags = new unsigned char[size];
284  unsigned int i;
285  for (i = 0; i < size; i++)
286  entryFlags[i] = ((unsigned char)EMPTY);
287 
288  // now convert the old table into the new one
289  for (i = 0L; i < oldSize; i++)
290  if (oldFlags[i] == USED)
291  insert(oldKeys[i], oldData[i]);
292 
293  // now clean up
294  delete[] oldKeys;
295  delete[] oldData;
296  delete[] oldFlags;
297 
298  // done
299  return;
300 }
301 
302 // +++++++++++ insert an element a hash table
303 
304 template <class KEY, class DATA>
305 inline int coMultiHashBase<KEY, DATA>::insert(const KEY &key, const DATA &inData)
306 {
307  int secondHash = 0;
308  unsigned int x = 0, u = 0;
309 
310  // find free space in the table
311  x = hash1(key);
312  while (entryFlags[x] == USED)
313  {
314  if (!secondHash)
315  {
316  u = hash2(key);
317  secondHash = 1;
318  }
319  x = (x + u) % size;
320  }
321 
322  // copy key and data to respective fields, save Flag info
323  entries++;
324  this->keys[x] = key;
325  this->data[x] = inData;
326  entryFlags[x] = (unsigned char)USED;
327 
328  // resize table if needed
329  if (entries > maxEntries)
330  resize();
331 
332  // done
333  return (1);
334 }
335 
336 // +++++++++++ remove an element from hash
337 
338 template <class KEY, class DATA>
339 inline int coMultiHashBase<KEY, DATA>::remove(unsigned long idx)
340 {
341  int res = 0;
342  if ((idx) && (idx <= size))
343  {
344  idx--;
345  if (entryFlags[idx] == USED)
346  {
347  entryFlags[idx] = PREVIOUS;
348  entries--;
349  res = 1;
350  }
351  }
352  return res;
353 }
354 
355 // +++++++++++ find an element in the hash table, 0 if not found
356 
357 template <class KEY, class DATA>
358 inline unsigned long coMultiHashBase<KEY, DATA>::getHash(const KEY &key) const
359 {
360  int secondHash = 0;
361  unsigned int idx, u = 0;
362  idx = hash1(key);
363  while (((entryFlags[idx] == USED) && (!equal(this->keys[idx], key)))
364  || (entryFlags[idx] == PREVIOUS))
365  {
366  if (!secondHash)
367  {
368  u = hash2(key);
369  secondHash = 1;
370  }
371  idx = (idx + u) % size;
372  }
373 
374  if (entryFlags[idx] != USED)
375  idx = 0;
376  else
377  idx++; // one more to have 0 as error
378 
379  // done
380  return idx;
381 }
382 
383 // +++++++++++ return value for given hash value
384 template <class KEY, class DATA>
385 inline DATA &coMultiHashBase<KEY, DATA>::operator[](unsigned long idx)
386 {
387  // make sure we got legal index
388  assert((idx) && (idx <= size));
389  return this->data[idx - 1];
390 }
391 
392 // +++++++++++ return value for given hash value: const
393 template <class KEY, class DATA>
394 inline const DATA &coMultiHashBase<KEY, DATA>::operator[](unsigned long idx) const
395 {
396  // make sure we got legal index
397  assert((idx) && (idx <= size));
398  return this->data[idx - 1];
399 }
400 
401 // +++++++++++ get the next jash value
402 template <class KEY, class DATA>
403 inline unsigned long coMultiHashBase<KEY, DATA>::nextHash(unsigned long idx) const
404 {
405  // make sure we got legal index
406  assert((idx) && (idx <= size) && (entryFlags[idx - 1] == USED));
407 
408  // user idx'es are one too high
409  idx--;
410 
411  // look out for next one with my key
412  const KEY &myKey = this->keys[idx];
413  unsigned long u = hash2(myKey);
414  //cerr << "Checking further hashes, start with idx=" << idx
415  // << ", key is " << myKey << endl;
416  idx = (idx + u) % size;
417  //cerr << "+ Check " << idx << endl;
418  while (((entryFlags[idx] == USED) && (!equal(this->keys[idx], myKey)))
419  || (entryFlags[idx] == PREVIOUS))
420  {
421  idx = (idx + u) % size;
422  //cerr << "+ Check " << idx << endl;
423  }
424 
425  if (entryFlags[idx] != USED)
426  idx = 0;
427  else
428  idx++;
429 
430  return idx;
431 }
432 
433 template <class KEY, class DATA>
435 {
436  return entries;
437 }
438 }
439 #endif
DATA & operator[](unsigned long hashIndex)
access element by hash index: assert() correct index !!
Definition: coMultiHashBase.h:385
virtual unsigned long hash1(const KEY &) const =0
first hash function (pure virtual)
void resize(void)
Definition: coMultiHashBase.h:258
unsigned char * entryFlags
Definition: coMultiHashBase.h:92
int primeIndex
Definition: coMultiHashBase.h:61
int getNumEntries() const
get number of entries currently in hash
Definition: coMultiHashBase.h:434
Definition: coMultiHashBase.h:82
Definition: coMultiHashBase.h:72
GLuint res
Definition: khronos-glext.h:10588
unsigned long getHash(const KEY &key) const
get hash index, 0 if no element found
Definition: coMultiHashBase.h:358
virtual unsigned long nextHash(unsigned long hashIndex) const
get next hashIndex to given hashIndex
Definition: coMultiHashBase.h:403
virtual unsigned long hash2(const KEY &) const =0
second hash function (pure virtual)
GLsizeiptr size
Definition: khronos-glext.h:6610
void removeAll()
remove an entry by hashIndex
Definition: coMultiHashBase.h:228
Definition: coMultiHashBase.h:84
GLint GLint GLint GLint GLint x
Definition: khronos-glext.h:6346
KEY * keys
Definition: coMultiHashBase.h:88
unsigned int size
size of the list
Definition: coMultiHashBase.h:95
int remove(unsigned long hashIndex)
remove an entry by hashIndex
Definition: coMultiHashBase.h:339
Definition: coMultiHashBase.h:83
virtual int insert(const KEY &key, const DATA &inData)
insert an entry (virtual for non-multi hash)
Definition: coMultiHashBase.h:305
unsigned int maxEntries
Definition: coMultiHashBase.h:58
Definition: coHashIter.h:34
const DATA & getNullElem() const
get the NULL element
Definition: coMultiHashBase.h:108
DATA * data
Definition: coMultiHashBase.h:52
unsigned int entries
Definition: coMultiHashBase.h:55
unsigned int prime
the prime currently used as the length of the list
Definition: coMultiHashBase.h:98
virtual bool equal(const KEY &, const KEY &) const =0
KEY1 == KEY2 operation (pure virtual)
virtual ~coMultiHashBase()
destructor
Definition: coMultiHashBase.h:245
GLsizei GLsizei GLenum GLenum const GLvoid * data
Definition: khronos-glext.h:6354
Definition: coHash.h:24
DATA d_nullElem
Definition: coMultiHashBase.h:49
coMultiHashBase()
constructor
Definition: coMultiHashBase.h:153