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