vrpn 07.35
Virtual Reality Peripheral Network
Loading...
Searching...
No Matches
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
10inline unsigned int vrpn_LinearUnsignedIntHashFunction(const unsigned int &i)
11{
12 return i;
13}
14
15template <class T>
16inline unsigned int vrpn_LinearHashFunction(const T &value)
17{
18 return (unsigned int)value;
19}
20
22
30template <class TKey,class TValue>
32{
33public:
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
62private:
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
96template <class TKey,class TValue>
98{
99 HashFunction = vrpn_LinearHashFunction<TKey>;
100 m_NrItems = 0;
101 m_CurrentItem = 0;
102 m_First = 0L;
103 m_InitialSize = m_SizeHash = init;
104 m_Items = new HashItem*[m_SizeHash];
105 MakeNull( m_Items, m_SizeHash );
106}
107
113template <class TKey,class TValue>
114vrpn_Hash<TKey, TValue>::vrpn_Hash(unsigned int (*func)(const TKey &key), int init)
115{
116 HashFunction = func;
117 m_NrItems = 0;
118 m_CurrentItem = 0;
119 m_First = 0L;
120 m_InitialSize = m_SizeHash = init;
121 m_Items = new HashItem*[m_SizeHash];
122 MakeNull( m_Items, m_SizeHash );
123}
124
125template <class TKey,class TValue>
127{
128 ClearItems();
129 try {
130 delete[] m_Items;
131 } catch (...) {
132 fprintf(stderr, "vrpn_Hash::~vrpn_Hash(): delete failed\n");
133 return;
134 }
135}
136
137template <class TKey,class TValue>
139{
140 ClearItems();
141
142 m_NrItems = 0;
143 try {
144 delete[] m_Items;
145 } catch (...) {
146 fprintf(stderr, "vrpn_Hash::Clear(): delete failed\n");
147 return;
148 }
149 m_Items = NULL;
150 m_First = 0;
151 m_CurrentItem = 0;
152
153 m_SizeHash = m_InitialSize;
154 try { m_Items = new HashItem*[m_SizeHash]; }
155 catch (...) {
156 m_SizeHash = 0;
157 return;
158 }
159 MakeNull( m_Items, m_SizeHash );
160}
161
162template <class TKey,class TValue>
163TValue& vrpn_Hash<TKey, TValue>::Find(const TKey &key)
164{
165 TValue zero = 0;
166 TValue &result = zero ;
167
168 unsigned int HashValue = HashFunction( key ) % m_SizeHash;
169 if ( m_Items[ HashValue ] != 0 )
170 if ( m_Items[ HashValue ]->key == key )
171 {
172 result = m_Items[ HashValue ]->value;
173 m_CurrentItem = m_Items[ HashValue ];
174 }
175
176 return result;
177}
178
179template <class TKey,class TValue>
180const TValue& vrpn_Hash<TKey, TValue>::Find(const TKey &key) const
181{
182 TValue zero = 0;
183 TValue &result = zero ;
184
185 unsigned int HashValue = HashFunction( key ) % m_SizeHash;
186 if ( m_Items[ HashValue ] != 0 )
187 if ( m_Items[ HashValue ]->key == key )
188 result = m_Items[ HashValue ]->value;
189
190 return result;
191}
192
193template <class TKey,class TValue>
194bool vrpn_Hash<TKey, TValue>::IsPresent(const TValue &value, TKey &key) const
195{
196 bool searching = MoveFirst();
197
198 while( searching )
199 {
200 if( GetCurrentValue() == value )
201 {
202 key = GetCurrentKey();
203 return true;
204 }
205 searching = MoveNext();
206 }
207
208 return false;
209
210}
211
212template <class TKey,class TValue>
213bool vrpn_Hash<TKey, TValue>::Add(TKey key, TValue value)
214{
215 bool result;
216 TKey theKey;
217
218 unsigned int HashValue = HashFunction( key ) % m_SizeHash;
219 HashItem* elementPointer = m_Items[ HashValue ];
220 if (elementPointer != 0)
221 theKey = m_Items[ HashValue ]->key;
222
223 //---- if object already exists
224 if ( elementPointer != 0 )
225 {
226 if ( theKey == key )
227 result = false;
228 else
229 {
230 ReHash(); //--- private function does not have mutex in this class...
231
232 result = Add( key, value ); //---- mutex must be released here when calling recursively
233 }
234 }
235
236 //---- if object does not exits in the table
237 else
238 {
239 m_NrItems++;
240 HashItem *item;
241 try { item = new HashItem; }
242 catch (...) { return false; }
243 item->key = key;
244 item->value = value;
245 item->next = m_First;
246 m_First = item;
247 m_Items[ HashValue ] = item;
248 m_CurrentItem = m_Items[ HashValue ];
249
250 result = true;
251 }
252
253 return result;
254}
255
256template <class TKey,class TValue>
258{
259 bool result = false;
260
261 unsigned int HashValue = HashFunction( key ) % m_SizeHash;
262 if ( m_Items[ HashValue ] != 0 ) {
263 if ( m_Items[ HashValue ]->key == key ) {
264 m_NrItems--;
265 result = true;
266
267 //--adjust pointers
268 if ( m_Items[ HashValue ] == m_First ) {
269 m_First = m_First->next;
270 } else {
271 HashItem *item;
272 for ( item = m_First ; item->next != m_Items[ HashValue ]; item = item->next );
273 item->next = item->next->next;
274 }
275
276 //--free memory
277 try {
278 delete m_Items[HashValue]; //free( m_Items[ HashValue ] );
279 } catch (...) {
280 fprintf(stderr, "vrpn_Hash::Remove(): delete failed\n");
281 return false;
282 }
283 m_Items[ HashValue ] = 0;
284 }
285 }
286
287 return result;
288}
289
290template <class TKey,class TValue>
292{
293 m_CurrentItem = m_First;
294
295 return ( m_First==NULL ) ? false : true;
296}
297
298template <class TKey,class TValue>
300{
301 if ( m_CurrentItem == NULL )
302 return false;
303
304 m_CurrentItem = m_CurrentItem->next;
305 return ( m_CurrentItem != NULL ) ;
306}
307
308template <class TKey,class TValue>
310{
311 if ( m_CurrentItem )
312 return m_CurrentItem->value;
313 else
314 return 0;
315}
316
317template <class TKey,class TValue>
319{
320 if ( m_CurrentItem )
321 m_CurrentItem->value=theValue;
322}
323
324template <class TKey,class TValue>
326{
327
328 if ( m_CurrentItem )
329 return m_CurrentItem->key;
330 else
331 return 0;
332}
333
334template <class TKey,class TValue>
335bool vrpn_Hash<TKey, TValue>::GetCurrentKeyAndValue(TKey &theKey, TValue &theValue) const
336{
337 if ( m_CurrentItem ) {
338 theKey = m_CurrentItem->key;
339 theValue = m_CurrentItem->value;
340 return true;
341 } else {
342 return false;
343 }
344}
345
346template <class TKey,class TValue> //--- these functions do not implement the mutex (this is done in the calling function)
347void vrpn_Hash<TKey, TValue>::MakeNull(HashItem **table, int size)
348{
349 for ( int i = 0 ; i < size ; i++ )
350 table[i]=0;
351}
352
353template <class TKey,class TValue>
354void vrpn_Hash<TKey, TValue>::ReHash() //--- these functions do not implement the mutex (this is done in the calling function)
355{
356 HashItem **temp;
357 int OldSizeHash = m_SizeHash;
358 m_SizeHash *= 2;
359 try { temp = new HashItem*[m_SizeHash]; }
360 catch (...) { m_SizeHash = 0; return; }
361 MakeNull( temp, m_SizeHash );
362 HashItem *NewFirst = 0;
363 for ( HashItem *item = m_First ; item != 0 ; item = item->next )
364 {
365 unsigned int HashValue = HashFunction( item->key )% OldSizeHash;
366 HashItem *NewItem;
367 try { NewItem = new HashItem; }
368 catch (...) { m_SizeHash = 0; return; }
369 NewItem->key = item->key;
370 NewItem->value = item->value;
371 NewItem->next = NewFirst;
372 NewFirst = NewItem;
373 HashValue = HashFunction( item->key ) % m_SizeHash;
374 temp[ HashValue ] = NewItem;
375 }
376 ClearItems();
377 m_First = NewFirst;
378
379 try {
380 delete[] m_Items;
381 } catch (...) {
382 fprintf(stderr, "vrpn_Hash::ReHash(): delete failed\n");
383 return;
384 }
385 m_Items = temp;
386}
387
388
389template <class TKey,class TValue>
391{
392 for ( HashItem *item = m_First ; item != 0 ; )
393 {
394 HashItem *it = item;
395 item = item->next;
396 try {
397 delete it;
398 } catch (...) {
399 fprintf(stderr, "vrpn_Hash::ClearItems(): delete failed\n");
400 return;
401 }
402 }
403 m_CurrentItem = 0;
404}
405
406#endif
Hash class (not thread-safe)
Definition vrpn_HashST.h:32
bool MoveNext() const
moves the iterator to the next element and returns false if no more element is present
bool IsPresent(const TValue &value, TKey &key) const
checks if the Hash contains a value and returns its key
vrpn_Hash(int init=16)
constructor
Definition vrpn_HashST.h:97
virtual ~vrpn_Hash()
destructor
TValue & Find(const TKey &key)
returns the value that belongs to this key
bool Remove(TKey key)
removes the value that belongs to this key, returns true if succeeded
void SetCurrentValue(TValue theValue)
sets the Value of the current key
const TValue & Find(const TKey &key) const
returns the value that belongs to this key
bool Add(TKey key, TValue value)
adds a new (key, value) pair, returns true if succeeded
TValue GetCurrentValue() const
returns the value of the current item
bool MoveFirst() const
moves an iterator to the first element and returns false if no element is present
void Clear()
clears the Hash
bool GetCurrentKeyAndValue(TKey &theKey, TValue &theValue) const
returns the key and the value of the current item
unsigned int GetNrItems() const
returns the number of items in the Hash
Definition vrpn_HashST.h:44
TKey GetCurrentKey() const
returns the key of the current item
vrpn_Hash(unsigned int(*func)(const TKey &key), int init=16)
constructor
unsigned int vrpn_LinearHashFunction(const T &value)
Definition vrpn_HashST.h:16
unsigned int vrpn_LinearUnsignedIntHashFunction(const unsigned int &i)
Definition vrpn_HashST.h:10