vrpn  07.33
Virtual Reality Peripheral Network
vrpn_HashST.h
Go to the documentation of this file.
1 /*
2  * vrpn_HashST.H
3  *
4  */
5 
6 
7 #ifndef _VRPN_HASHST_H
8 #define _VRPN_HASHST_H
9 
10 inline unsigned int vrpn_LinearUnsignedIntHashFunction(const unsigned int &i)
11 {
12  return i;
13 }
14 
15 template <class T>
16 inline unsigned int vrpn_LinearHashFunction(const T &value)
17 {
18  return (unsigned int)value;
19 }
20 
22 
30 template <class TKey,class TValue>
31 class vrpn_Hash
32 {
33 public:
35  vrpn_Hash(int init=16);
37  vrpn_Hash(unsigned int (*func)(const TKey &key), int init=16);
39  virtual ~vrpn_Hash();
41  void Clear();
42 
44  unsigned int GetNrItems() const { return m_NrItems; }
46  TValue& Find(const TKey &key);
48  const TValue& Find(const TKey &key) const;
50  bool IsPresent(const TValue &value, TKey &key) const;
51 
52  bool MoveFirst() const;
53  bool MoveNext() const;
54  TValue GetCurrentValue() const;
55  TKey GetCurrentKey() const;
56  void SetCurrentValue(TValue theValue);
57  bool GetCurrentKeyAndValue(TKey &theKey, TValue &theValue) const;
58 
59  bool Add(TKey key, TValue value);
60  bool Remove(TKey key);
61 
62 private:
64 
67  struct HashItem
68  {
69  TKey key;
70  TValue value;
71  struct HashItem *next;
72  };
73 
74  void ClearItems();
75  void ReHash();
76  void MakeNull(HashItem **table,int size);
77 
78  unsigned int m_NrItems;
79  unsigned int m_SizeHash;
80  unsigned int m_InitialSize;
81 
82  HashItem **m_Items;
83  HashItem *m_First;
84 
85  unsigned int (*HashFunction)(const TKey &key);
86 
87  mutable HashItem *m_CurrentItem;
88 
89  unsigned int m_Owner;
90 };
91 
96 template <class TKey,class TValue>
98 {
99  HashFunction = vrpn_LinearHashFunction<TKey>;
100  m_NrItems = 0;
101  m_InitialSize = m_SizeHash = init;
102  m_Items = new HashItem*[m_SizeHash];
103  MakeNull( m_Items, m_SizeHash );
104  m_CurrentItem = 0;
105 
106  m_First=0L;
107 }
108 
114 template <class TKey,class TValue>
115 vrpn_Hash<TKey, TValue>::vrpn_Hash(unsigned int (*func)(const TKey &key), int init)
116 {
117  HashFunction = func;
118  m_NrItems = 0;
119  m_InitialSize = m_SizeHash = init;
120  m_Items = new HashItem*[m_SizeHash];
121  MakeNull( m_Items, m_SizeHash );
122  m_CurrentItem = 0;
123 
124  m_First=0L;
125 }
126 
127 template <class TKey,class TValue>
129 {
130 
131  ClearItems();
132  delete[] m_Items;
133 }
134 
135 template <class TKey,class TValue>
137 {
138  ClearItems();
139 
140  m_NrItems = 0;
141  delete m_Items;
142 
143  m_SizeHash = m_InitialSize;
144  m_Items = new HashItem*[m_SizeHash];
145  MakeNull( m_Items, m_SizeHash );
146  m_First = 0;
147  m_CurrentItem = 0;
148 }
149 
150 template <class TKey,class TValue>
151 TValue& vrpn_Hash<TKey, TValue>::Find(const TKey &key)
152 {
153  TValue zero = 0;
154  TValue &result = zero ;
155 
156  unsigned int HashValue = HashFunction( key ) % m_SizeHash;
157  if ( m_Items[ HashValue ] != 0 )
158  if ( m_Items[ HashValue ]->key == key )
159  {
160  result = m_Items[ HashValue ]->value;
161  m_CurrentItem = m_Items[ HashValue ];
162  }
163 
164  return result;
165 }
166 
167 template <class TKey,class TValue>
168 const TValue& vrpn_Hash<TKey, TValue>::Find(const TKey &key) const
169 {
170  TValue zero = 0;
171  TValue &result = zero ;
172 
173  unsigned int HashValue = HashFunction( key ) % m_SizeHash;
174  if ( m_Items[ HashValue ] != 0 )
175  if ( m_Items[ HashValue ]->key == key )
176  result = m_Items[ HashValue ]->value;
177 
178  return result;
179 }
180 
181 template <class TKey,class TValue>
182 bool vrpn_Hash<TKey, TValue>::IsPresent(const TValue &value, TKey &key) const
183 {
184  bool searching = MoveFirst();
185 
186  while( searching )
187  {
188  if( GetCurrentValue() == value )
189  {
190  key = GetCurrentKey();
191  return true;
192  }
193  searching = MoveNext();
194  }
195 
196  return false;
197 
198 }
199 
200 template <class TKey,class TValue>
201 bool vrpn_Hash<TKey, TValue>::Add(TKey key, TValue value)
202 {
203  bool result;
204  TKey theKey;
205 
206  unsigned int HashValue = HashFunction( key ) % m_SizeHash;
207  HashItem* elementPointer = m_Items[ HashValue ];
208  if (elementPointer != 0)
209  theKey = m_Items[ HashValue ]->key;
210 
211  //---- if object already exists
212  if ( elementPointer != 0 )
213  {
214  if ( theKey == key )
215  result = false;
216  else
217  {
218  ReHash(); //--- private function does not have mutex in this class...
219 
220  result = Add( key, value ); //---- mutex must be released here when calling recursively
221  }
222  }
223 
224  //---- if object does not exits in the table
225  else
226  {
227  m_NrItems++;
228  HashItem *item = new HashItem; //( HashItem * ) malloc( sizeof( HashItem ) );
229  item->key = key;
230  item->value = value;
231  item->next = m_First;
232  m_First = item;
233  m_Items[ HashValue ] = item;
234  m_CurrentItem = m_Items[ HashValue ];
235 
236  result = true;
237  }
238 
239  return result;
240 }
241 
242 template <class TKey,class TValue>
244 {
245  bool result = false;
246 
247  unsigned int HashValue = HashFunction( key ) % m_SizeHash;
248  if ( m_Items[ HashValue ] != 0 ) {
249  if ( m_Items[ HashValue ]->key == key ) {
250  m_NrItems--;
251  result = true;
252 
253  //--adjust pointers
254  if ( m_Items[ HashValue ] == m_First ) {
255  m_First = m_First->next;
256  } else {
257  HashItem *item;
258  for ( item = m_First ; item->next != m_Items[ HashValue ]; item = item->next );
259  item->next = item->next->next;
260  }
261 
262  //--free memory
263  delete m_Items[ HashValue ]; //free( m_Items[ HashValue ] );
264  m_Items[ HashValue ] = 0;
265  }
266  }
267 
268  return result;
269 }
270 
271 template <class TKey,class TValue>
273 {
274  m_CurrentItem = m_First;
275 
276  return ( m_First==NULL ) ? false : true;
277 }
278 
279 template <class TKey,class TValue>
281 {
282  if ( m_CurrentItem == NULL )
283  return false;
284 
285  m_CurrentItem = m_CurrentItem->next;
286  return ( m_CurrentItem != NULL ) ;
287 }
288 
289 template <class TKey,class TValue>
291 {
292  if ( m_CurrentItem )
293  return m_CurrentItem->value;
294  else
295  return 0;
296 }
297 
298 template <class TKey,class TValue>
300 {
301  if ( m_CurrentItem )
302  m_CurrentItem->value=theValue;
303 }
304 
305 template <class TKey,class TValue>
307 {
308 
309  if ( m_CurrentItem )
310  return m_CurrentItem->key;
311  else
312  return 0;
313 }
314 
315 template <class TKey,class TValue>
316 bool vrpn_Hash<TKey, TValue>::GetCurrentKeyAndValue(TKey &theKey, TValue &theValue) const
317 {
318  bool result;
319 
320 
321  if ( m_CurrentItem )
322  {
323  theKey = m_CurrentItem->key;
324  theValue = m_CurrentItem->value;
325  return true;
326  }
327  else
328  return false;
329 }
330 
331 template <class TKey,class TValue> //--- these functions do not implement the mutex (this is done in the calling function)
332 void vrpn_Hash<TKey, TValue>::MakeNull(HashItem **table, int size)
333 {
334  for ( int i = 0 ; i < size ; i++ )
335  table[i]=0;
336 }
337 
338 template <class TKey,class TValue>
339 void vrpn_Hash<TKey, TValue>::ReHash() //--- these functions do not implement the mutex (this is done in the calling function)
340 {
341  HashItem **temp;
342  int OldSizeHash = m_SizeHash;
343  m_SizeHash *= 2;
344  temp = new HashItem*[m_SizeHash];
345  MakeNull( temp, m_SizeHash );
346  HashItem *NewFirst = 0;
347  for ( HashItem *item = m_First ; item != 0 ; item = item->next )
348  {
349  unsigned int HashValue = HashFunction( item->key )% OldSizeHash;
350  HashItem *NewItem = new HashItem;
351  NewItem->key = item->key;
352  NewItem->value = item->value;
353  NewItem->next = NewFirst;
354  NewFirst = NewItem;
355  HashValue = HashFunction( item->key ) % m_SizeHash;
356  temp[ HashValue ] = NewItem;
357  }
358  ClearItems();
359  m_First = NewFirst;
360 
361  delete m_Items; //free( m_Items );
362  m_Items = temp;
363 }
364 
365 
366 template <class TKey,class TValue>
368 {
369  for ( HashItem *item = m_First ; item != 0 ; )
370  {
371  HashItem *it = item;
372  item = item->next;
373  delete it;
374  }
375  m_CurrentItem = 0;
376 }
377 
378 #endif
bool GetCurrentKeyAndValue(TKey &theKey, TValue &theValue) const
returns the key and the value of the current item
Definition: vrpn_HashST.h:316
bool MoveNext() const
moves the iterator to the next element and returns false if no more element is present ...
Definition: vrpn_HashST.h:280
bool MoveFirst() const
moves an iterator to the first element and returns false if no element is present ...
Definition: vrpn_HashST.h:272
TKey GetCurrentKey() const
returns the key of the current item
Definition: vrpn_HashST.h:306
bool IsPresent(const TValue &value, TKey &key) const
checks if the Hash contains a value and returns its key
Definition: vrpn_HashST.h:182
bool Add(TKey key, TValue value)
adds a new (key, value) pair, returns true if succeeded
Definition: vrpn_HashST.h:201
unsigned int GetNrItems() const
returns the number of items in the Hash
Definition: vrpn_HashST.h:44
Hash class (not thread-safe)
Definition: vrpn_HashST.h:31
void Clear()
clears the Hash
Definition: vrpn_HashST.h:136
void SetCurrentValue(TValue theValue)
sets the Value of the current key
Definition: vrpn_HashST.h:299
unsigned int vrpn_LinearUnsignedIntHashFunction(const unsigned int &i)
Definition: vrpn_HashST.h:10
unsigned int vrpn_LinearHashFunction(const T &value)
Definition: vrpn_HashST.h:16
TValue GetCurrentValue() const
returns the value of the current item
Definition: vrpn_HashST.h:290
virtual ~vrpn_Hash()
destructor
Definition: vrpn_HashST.h:128
vrpn_Hash(int init=16)
constructor
Definition: vrpn_HashST.h:97
TValue & Find(const TKey &key)
returns the value that belongs to this key
Definition: vrpn_HashST.h:151
bool Remove(TKey key)
removes the value that belongs to this key, returns true if succeeded
Definition: vrpn_HashST.h:243