COVISE Core
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros
coHashBase.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_HASH_BASE_H
9 #define __CO_HASH_BASE_H
10 
11 #include "coExport.h"
12 #include "coMultiHashBase.h"
13 
23 namespace covise
24 {
25 
26 template <class KEY, class DATA>
27 class coHashBase : public coMultiHashBase<KEY, DATA>
28 {
29 
30 public:
31  coHashBase(DATA nullelem)
32  : coMultiHashBase<KEY, DATA>(nullelem){};
33 
35  : coMultiHashBase<KEY, DATA>(){};
36 
38  virtual unsigned long nextHash(unsigned long /* hashIndex */) const
39  {
40  return 0;
41  }
42 
44  virtual int insert(const KEY &key, const DATA &inData);
45 
47  virtual unsigned long hash1(const KEY &) const = 0;
48 
50  virtual unsigned long hash2(const KEY &) const = 0;
51 
53  virtual bool equal(const KEY &, const KEY &) const = 0;
54 };
55 
56 // +++++++++++ insert an element a hash table
57 
58 template <class KEY, class DATA>
59 inline int coHashBase<KEY, DATA>::insert(const KEY &key, const DATA &inData)
60 {
61  unsigned int x, u, hash;
62 
63  // find free space in the table
64  x = hash1(key);
65  u = hash2(key);
66 
67  // replace same key
68  while ((this->entryFlags[x] == coMultiHashBase<KEY, DATA>::USED)
69  && (!equal(key, this->keys[x])))
70  x = (x + u) % this->size;
71 
72  // copy key and data to respective fields, save Flag info
73  if (this->entryFlags[x] != coMultiHashBase<KEY, DATA>::USED)
74  this->entries++;
75  this->keys[x] = key;
76  this->data[x] = inData;
77  this->entryFlags[x] = coMultiHashBase<KEY, DATA>::USED;
78  hash = x;
79 
80  // delete possible other entries with same key
81  x = (x + u) % this->size;
82  while ((this->entryFlags[x] != coMultiHashBase<KEY, DATA>::EMPTY)
83  && (x != hash) && (!equal(key, this->keys[x])))
84  {
85  x = (x + u) % this->size;
86  }
87  if (this->entryFlags[x] != coMultiHashBase<KEY, DATA>::EMPTY && this->keys[x] == key)
88  {
89  this->entryFlags[x] = coMultiHashBase<KEY, DATA>::PREVIOUS;
90  }
91 
92  // resize table if needed
93  if (this->entries > this->maxEntries)
94  this->resize();
95 
96  // done
97  return (1);
98 }
99 }
100 #endif
coHashBase(DATA nullelem)
Definition: coHashBase.h:31
virtual unsigned long hash1(const KEY &) const =0
first hash function (pure virtual)
GLsizeiptr size
Definition: khronos-glext.h:6610
Definition: coIntMultiHash.h:25
GLint GLint GLint GLint GLint x
Definition: khronos-glext.h:6346
coHashBase()
Definition: coHashBase.h:34
virtual unsigned long nextHash(unsigned long) const
no identical keys in table
Definition: coHashBase.h:38
virtual bool equal(const KEY &, const KEY &) const =0
KEY1 == KEY2 operation (pure virtual)
virtual int insert(const KEY &key, const DATA &inData)
insert: if existing element, replace it
Definition: coHashBase.h:59
virtual unsigned long hash2(const KEY &) const =0
second hash function (pure virtual)
GLsizei GLsizei GLenum GLenum const GLvoid * data
Definition: khronos-glext.h:6354