Menu
▾
▴
[Javaprofiler-commits] CVS: library/src/hash hash.h,1.20,1.21
|
From: Marek P. <ma...@us...> - 2001-11-21 22:32:16
|
Update of /cvsroot/javaprofiler/library/src/hash
In directory usw-pr-cvs1:/tmp/cvs-serv12170/src/hash
Modified Files:
hash.h
Log Message:
some parts completely rewritten;
changes in communication interface to make it faster;
ported to linux
Index: hash.h
===================================================================
RCS file: /cvsroot/javaprofiler/library/src/hash/hash.h,v
retrieving revision 1.20
retrieving revision 1.21
diff -C2 -r1.20 -r1.21
*** hash.h 2001/09/02 20:14:21 1.20
--- hash.h 2001/11/21 22:31:43 1.21
***************
*** 36,39 ****
--- 36,42 ----
#define _HASH_H_
+ #include "../main/includes.h"
+ #include "../list/list.h"
+
/** Hash table template.
**
***************
*** 85,88 ****
--- 88,93 ----
};
+ private:
+
/// an array of lists
List<T,L>* _table;
***************
*** 100,177 ****
unsigned int _index;
- private:
-
- /** Converts argument to an index to the hash table.
- ** Used in conjunction with hash function.
- ** Robert Jenkins' 32-bit mix function is used for hashing.
- **
- ** @param x typically result of a hash function
- **
- ** @return hash table index */
-
- unsigned int makeIndex( int x) {
-
- unsigned int key = (unsigned)x;
-
- key += (key << 12);
- key ^= (key >> 22);
- key += (key << 4);
- key ^= (key >> 9);
- key += (key << 10);
- key ^= (key >> 2);
- key += (key << 7);
- key ^= (key >> 12);
-
- unsigned int index = key & _mask;
- if( index >= _size) index >>= 1;
-
- return index;
- }
-
- /** Rehashing. This method resizes hashtable and
- ** rehashes its items.
- **
- ** @param sz new size of hashtable */
-
- void rehash( int sz) {
-
- int size = _size;
- List<T,L>* table = _table;
-
- _size = sz;
- _table = new List<T,L>[_size];
-
- _mask = _size-1;
-
- List<T,L>* p = table;
- T* t;
- K key;
- int h;
-
- for( int i = 0; i < size; i++, p++) {
- while( t = p->remove( p->first())) {
- h = T::hashKey(t->getKey(key));
- _table[makeIndex(h)].add( t);
- }
- }
-
- delete[] table;
- }
-
public:
/// Default constructor.
! Hash() : _size( 1<<10), _numItems( 0), _index(0) {
_table = new List<T,L>[_size];
-
_mask = _size-1;
}
/// Destructor.
! virtual ~Hash() { delete[] _table;};
/** Gets the first item in the hash table for iterating.
! ** Returns NULL if the hash table is empty;
**
** @return pointer to an item or NULL
--- 105,135 ----
unsigned int _index;
public:
/// Default constructor.
! Hash() :
!
! _size( 1<<10),
! _numItems( 0),
! _index(0) {
_table = new List<T,L>[_size];
_mask = _size-1;
}
/// Destructor.
! ~Hash() { delete[] _table;}
!
! /** Clears the whole hashtable. Its size remains unchanged.
! ** Don't use it - for testing only. */
!
! void clear() {
+ List<T,L>* p = _table;
+ for( unsigned int i = 0; i < _size; i++, p++) p->clear();
+ }
+
/** Gets the first item in the hash table for iterating.
! ** Returns NULL if the hash table is empty.
**
** @return pointer to an item or NULL
***************
*** 180,187 ****
T* first() {
- T* p;
- for (_index = 0; _index < _size; _index++)
- if (p = _table[_index].first()) return p;
return NULL;
}
--- 138,148 ----
T* first() {
+
+ List<T,L>* p = _table;
+ T* q;
+
+ for( _index = 0; _index < _size; _index++, p++)
+ if( q = p->first()) return q;
return NULL;
}
***************
*** 190,204 ****
** Returns NULL if the end of the hash table was reached.
**
! ** @param item pointer to an item
** @return pointer to the next item or NULL
**
** @see first() */
! T* next(T* item) {
- T* p = (T*)(L*)((L*)item)->next();
- if (p) return p;
- for (_index++ ; _index < _size; _index++)
- if (p = _table[_index].first()) return p;
return NULL;
}
--- 151,170 ----
** Returns NULL if the end of the hash table was reached.
**
! ** @param item pointer to an item
! **
** @return pointer to the next item or NULL
**
** @see first() */
+
+ T* next( T* item) {
+
+ T* q = static_cast<T*>( static_cast<L*>( item->L::next()));
+ if( q) return q;
+
+ List<T,L>* p = &_table[++_index];
! for( ; _index < _size; _index++)
! if( q = p->first()) return q;
return NULL;
}
***************
*** 206,222 ****
/** Adds an item to the hash table without rehashing.
**
! ** @param item pointer to an item
** @return pointer to the inserted item
**
** @see add(), remove(), removeNoRehash() */
! T* addNoRehash(T* item) {
! if (!item) return NULL;
K key;
! int h = T::hashKey(item->getKey(key));
! _table[makeIndex(h)].add(item);
_numItems++;
--- 172,189 ----
/** Adds an item to the hash table without rehashing.
**
! ** @param item pointer to an item
! **
** @return pointer to the inserted item
**
** @see add(), remove(), removeNoRehash() */
! T* addNoRehash( T* item) {
! if( !item) return NULL;
K key;
! int h = T::hashKey( item->getKey( key));
! _table[makeIndex( h)].add( item);
_numItems++;
***************
*** 225,253 ****
/** Adds an item to the hash table.
**
- ** @param item pointer to an item
** @return pointer to the inserted item
**
** @see addNoRehash(), remove(), removeNoRehash() */
! T* add(T* item) {
! if (!addNoRehash(item)) return NULL;
if( _numItems > _size*HASH_LIST_LIMIT+5) rehash( _size<<1);
return item;
}
/** Removes an item from the hash table without rehashing.
**
- ** @param item pointer to an item
** @return pointer to the removed item
**
** @see remove(), add(), addNoRehash() */
! T* removeNoRehash(T* item) {
! if (!item) return NULL;
! ((L*)item)->remove();
_numItems--;
--- 192,224 ----
/** Adds an item to the hash table.
+ **
+ ** @param item pointer to an item
**
** @return pointer to the inserted item
**
** @see addNoRehash(), remove(), removeNoRehash() */
! T* add( T* item) {
! if( !addNoRehash( item)) return NULL;
if( _numItems > _size*HASH_LIST_LIMIT+5) rehash( _size<<1);
+
return item;
}
/** Removes an item from the hash table without rehashing.
+ **
+ ** @param item pointer to an item
**
** @return pointer to the removed item
**
** @see remove(), add(), addNoRehash() */
! T* removeNoRehash( T* item) {
! if( !item) return NULL;
!
! item->L::remove();
_numItems--;
***************
*** 256,290 ****
/** Removes an item from the hash table.
**
- ** @param item pointer to an item
** @return pointer to the removed item
**
** @see add(), addNoRehash(), removeNoRehash() */
! T* remove(T* item) {
! if (!removeNoRehash(item)) return NULL;
unsigned int sz = _size>>1;
! if(_numItems < sz*HASH_LIST_LIMIT) rehash( sz);
return item;
}
/** Searches the hash table for an item corresponing
! ** to the specified key. If no item is found NULL is
** returned.
**
! ** @param key key to search for
** @return pointer to the found item */
! T* get(const K& key) {
! int h = T::hashKey(key);
! List<T,L>* list = &_table[makeIndex(h)];
T* p = list->first();
! while (p && (!(*p == key))) p = list->next(p);
! if (p) {
! ((L*)p)->remove();
! list->add(p);
! }
return p;
}
--- 227,265 ----
/** Removes an item from the hash table.
+ **
+ ** @param item pointer to an item
**
** @return pointer to the removed item
**
** @see add(), addNoRehash(), removeNoRehash() */
! T* remove( T* item) {
! if( !removeNoRehash( item)) return NULL;
!
unsigned int sz = _size>>1;
! if( _numItems < sz*HASH_LIST_LIMIT) rehash( sz);
!
return item;
}
/** Searches the hash table for an item corresponing
! ** to the specified key. If no item is found, NULL is
** returned.
**
! ** @param key key to search for
! **
** @return pointer to the found item */
! T* get( const K& key) {
! int h = T::hashKey( key);
! List<T,L>* list = &_table[makeIndex( h)];
T* p = list->first();
!
! while( p && !(*p == key)) p = list->next( p);
!
! if( p) list->add( list->remove( p));
!
return p;
}
***************
*** 299,304 ****
** as 'f', else when it stops it returns 0.
**
! ** @param f pointer to function
! ** @param inout the second argument of 'f' function
**
** @return value
--- 274,279 ----
** as 'f', else when it stops it returns 0.
**
! ** @param f pointer to function
! ** @param inout the second argument of 'f' function
**
** @return value
***************
*** 308,312 ****
int forEach( int (*f)( T*, void**), void** inout) {
! List<T,L>* p = &_table[0];
for( unsigned int i = 0; i < _size; i++, p++) {
--- 283,287 ----
int forEach( int (*f)( T*, void**), void** inout) {
! List<T,L>* p = _table;
for( unsigned int i = 0; i < _size; i++, p++) {
***************
*** 319,323 ****
--- 294,355 ----
}
+ private:
+
+ /** Converts argument to an index to the hash table.
+ ** Used in conjunction with hash function.
+ ** Robert Jenkins' 32-bit mix function is used for hashing.
+ **
+ ** @param x typically result of a hash function
+ **
+ ** @return hash table index */
+
+ unsigned int makeIndex( int x) {
+
+ unsigned int key = (unsigned)x;
+
+ key += (key << 12);
+ key ^= (key >> 22);
+ key += (key << 4);
+ key ^= (key >> 9);
+ key += (key << 10);
+ key ^= (key >> 2);
+ key += (key << 7);
+ key ^= (key >> 12);
+
+ unsigned int index = key & _mask;
+ if( index >= _size) index >>= 1;
+
+ return index;
+ }
+
+ /** Rehashing. This method resizes hashtable and
+ ** rehashes its items.
+ **
+ ** @param sz new size of hashtable */
+
+ void rehash( unsigned int sz) {
+
+ unsigned int size = _size;
+ List<T,L>* table = _table;
+
+ _size = sz;
+ _table = new List<T,L>[_size];
+
+ _mask = _size-1;
+ _numItems = 0;
+
+ _index = 0;
+
+ List<T,L>* p = table;
+
+ for( unsigned int i = 0; i < size; i++, p++)
+ while( addNoRehash( p->remove( p->first())));
+
+ delete[] table;
+ }
+
#ifdef _DEBUG
+ public:
+
/** Print statistics. This method prints statistic about
** the hashtable to standard output. It is used for debugging
***************
*** 362,364 ****
#endif // _HASH_H_
-
--- 394,395 ----
|
