18 return (
unsigned int)value;
30template <
class TKey,
class TValue>
37 vrpn_Hash(
unsigned int (*func)(
const TKey &key),
int init=16);
46 TValue&
Find(
const TKey &key);
48 const TValue&
Find(
const TKey &key)
const;
50 bool IsPresent(
const TValue &value, TKey &key)
const;
59 bool Add(TKey key, TValue value);
71 struct HashItem *next;
76 void MakeNull(HashItem **table,
int size);
78 unsigned int m_NrItems;
79 unsigned int m_SizeHash;
80 unsigned int m_InitialSize;
85 unsigned int (*HashFunction)(
const TKey &key);
87 mutable HashItem *m_CurrentItem;
96template <
class TKey,
class TValue>
99 HashFunction = vrpn_LinearHashFunction<TKey>;
103 m_InitialSize = m_SizeHash = init;
104 m_Items =
new HashItem*[m_SizeHash];
105 MakeNull( m_Items, m_SizeHash );
113template <
class TKey,
class TValue>
120 m_InitialSize = m_SizeHash = init;
121 m_Items =
new HashItem*[m_SizeHash];
122 MakeNull( m_Items, m_SizeHash );
125template <
class TKey,
class TValue>
132 fprintf(stderr,
"vrpn_Hash::~vrpn_Hash(): delete failed\n");
137template <
class TKey,
class TValue>
146 fprintf(stderr,
"vrpn_Hash::Clear(): delete failed\n");
153 m_SizeHash = m_InitialSize;
154 try { m_Items =
new HashItem*[m_SizeHash]; }
159 MakeNull( m_Items, m_SizeHash );
162template <
class TKey,
class TValue>
166 TValue &result = zero ;
168 unsigned int HashValue = HashFunction( key ) % m_SizeHash;
169 if ( m_Items[ HashValue ] != 0 )
170 if ( m_Items[ HashValue ]->key == key )
172 result = m_Items[ HashValue ]->value;
173 m_CurrentItem = m_Items[ HashValue ];
179template <
class TKey,
class TValue>
183 TValue &result = zero ;
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;
193template <
class TKey,
class TValue>
196 bool searching = MoveFirst();
200 if( GetCurrentValue() == value )
202 key = GetCurrentKey();
205 searching = MoveNext();
212template <
class TKey,
class TValue>
218 unsigned int HashValue = HashFunction( key ) % m_SizeHash;
219 HashItem* elementPointer = m_Items[ HashValue ];
220 if (elementPointer != 0)
221 theKey = m_Items[ HashValue ]->key;
224 if ( elementPointer != 0 )
232 result = Add( key, value );
241 try { item =
new HashItem; }
242 catch (...) {
return false; }
245 item->next = m_First;
247 m_Items[ HashValue ] = item;
248 m_CurrentItem = m_Items[ HashValue ];
256template <
class TKey,
class TValue>
261 unsigned int HashValue = HashFunction( key ) % m_SizeHash;
262 if ( m_Items[ HashValue ] != 0 ) {
263 if ( m_Items[ HashValue ]->key == key ) {
268 if ( m_Items[ HashValue ] == m_First ) {
269 m_First = m_First->next;
272 for ( item = m_First ; item->next != m_Items[ HashValue ]; item = item->next );
273 item->next = item->next->next;
278 delete m_Items[HashValue];
280 fprintf(stderr,
"vrpn_Hash::Remove(): delete failed\n");
283 m_Items[ HashValue ] = 0;
290template <
class TKey,
class TValue>
293 m_CurrentItem = m_First;
295 return ( m_First==NULL ) ? false :
true;
298template <
class TKey,
class TValue>
301 if ( m_CurrentItem == NULL )
304 m_CurrentItem = m_CurrentItem->next;
305 return ( m_CurrentItem != NULL ) ;
308template <
class TKey,
class TValue>
312 return m_CurrentItem->value;
317template <
class TKey,
class TValue>
321 m_CurrentItem->value=theValue;
324template <
class TKey,
class TValue>
329 return m_CurrentItem->key;
334template <
class TKey,
class TValue>
337 if ( m_CurrentItem ) {
338 theKey = m_CurrentItem->key;
339 theValue = m_CurrentItem->value;
346template <
class TKey,
class TValue>
349 for (
int i = 0 ; i < size ; i++ )
353template <
class TKey,
class TValue>
357 int OldSizeHash = m_SizeHash;
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 )
365 unsigned int HashValue = HashFunction( item->key )% OldSizeHash;
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;
373 HashValue = HashFunction( item->key ) % m_SizeHash;
374 temp[ HashValue ] = NewItem;
382 fprintf(stderr,
"vrpn_Hash::ReHash(): delete failed\n");
389template <
class TKey,
class TValue>
392 for ( HashItem *item = m_First ; item != 0 ; )
399 fprintf(stderr,
"vrpn_Hash::ClearItems(): delete failed\n");
Hash class (not thread-safe)
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
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
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)
unsigned int vrpn_LinearUnsignedIntHashFunction(const unsigned int &i)