home *** CD-ROM | disk | FTP | other *** search
/ GameStar 2006 March / Gamestar_82_2006-03_dvd.iso / DVDStar / Editace / quake4_sdkv10.exe / source / idlib / containers / HashTable.h < prev    next >
C/C++ Source or Header  |  2005-11-14  |  8KB  |  420 lines
  1.  
  2. #ifndef __HASHTABLE_H__
  3. #define __HASHTABLE_H__
  4.  
  5. /*
  6. ===============================================================================
  7.  
  8.     General hash table. Slower than idHashIndex but it can also be used for
  9.     linked lists and other data structures than just indexes or arrays.
  10.  
  11. ===============================================================================
  12. */
  13.  
  14. template< class Type >
  15. class idHashTable {
  16. public:
  17.                     idHashTable( int newtablesize = 256 );
  18.                     idHashTable( const idHashTable<Type> &map );
  19.                     ~idHashTable( void );
  20.  
  21.                     // returns total size of allocated memory
  22.     size_t            Allocated( void ) const;
  23.                     // returns total size of allocated memory including size of hash table type
  24.     size_t            Size( void ) const;
  25.  
  26.     void            Set( const char *key, Type &value );
  27.     bool            Get( const char *key, Type **value = NULL ) const;
  28.     bool            Remove( const char *key );
  29.  
  30.     void            Clear( void );
  31.     void            DeleteContents( void );
  32.  
  33.                     // the entire contents can be itterated over, but note that the
  34.                     // exact index for a given element may change when new elements are added
  35.     int                Num( void ) const;
  36.     Type *            GetIndex( int index ) const;
  37.  
  38.     int                GetSpread( void ) const;
  39.  
  40. private:
  41.     struct hashnode_s {
  42.         idStr        key;
  43.         Type        value;
  44.         hashnode_s *next;
  45.  
  46.         hashnode_s( const idStr &k, Type v, hashnode_s *n ) : key( k ), value( v ), next( n ) {};
  47.         hashnode_s( const char *k, Type v, hashnode_s *n ) : key( k ), value( v ), next( n ) {};
  48.     };
  49.  
  50.     hashnode_s **    heads;
  51.  
  52.     int                tablesize;
  53.     int                numentries;
  54.     int                tablesizemask;
  55.  
  56.     int                GetHash( const char *key ) const;
  57. };
  58.  
  59. /*
  60. ================
  61. idHashTable<Type>::idHashTable
  62. ================
  63. */
  64. template< class Type >
  65. ID_INLINE idHashTable<Type>::idHashTable( int newtablesize ) {
  66.  
  67.     assert( idMath::IsPowerOfTwo( newtablesize ) );
  68.  
  69.     tablesize = newtablesize;
  70.     assert( tablesize > 0 );
  71.  
  72. // RAVEN BEGIN
  73. // mwhitlock: Dynamic memory consolidation
  74. #if defined(_RV_MEM_SYS_SUPPORT_CONTAINERS)
  75.     bool ok=rvPushHeapContainingMemory(this);
  76. #endif
  77. // RAVEN END
  78.  
  79.     heads = new hashnode_s *[ tablesize ];
  80.  
  81. // RAVEN BEGIN
  82. // mwhitlock: Dynamic memory consolidation
  83. #if defined(_RV_MEM_SYS_SUPPORT_CONTAINERS)
  84.     if(ok)
  85.     {
  86.         RV_POP_HEAP();
  87.     }
  88. #endif
  89. // RAVEN END
  90.  
  91.     memset( heads, 0, sizeof( *heads ) * tablesize );
  92.  
  93.     numentries        = 0;
  94.  
  95.     tablesizemask = tablesize - 1;
  96. }
  97.  
  98. /*
  99. ================
  100. idHashTable<Type>::idHashTable
  101. ================
  102. */
  103. template< class Type >
  104. ID_INLINE idHashTable<Type>::idHashTable( const idHashTable<Type> &map ) {
  105.     int            i;
  106.     hashnode_s    *node;
  107.     hashnode_s    **prev;
  108.  
  109.     assert( map.tablesize > 0 );
  110.  
  111. // RAVEN BEGIN
  112. // mwhitlock: Dynamic memory consolidation
  113. #if defined(_RV_MEM_SYS_SUPPORT_CONTAINERS)
  114.     bool ok=rvPushHeapContainingMemory(this);
  115. #endif
  116. // RAVEN END
  117.  
  118.     tablesize        = map.tablesize;
  119.     heads            = new hashnode_s *[ tablesize ];
  120.     numentries        = map.numentries;
  121.     tablesizemask    = map.tablesizemask;
  122.  
  123.     for( i = 0; i < tablesize; i++ ) {
  124.         if ( !map.heads[ i ] ) {
  125.             heads[ i ] = NULL;
  126.             continue;
  127.         }
  128.  
  129.         prev = &heads[ i ];
  130.         for( node = map.heads[ i ]; node != NULL; node = node->next ) {
  131.             *prev = new hashnode_s( node->key, node->value, NULL );
  132.             prev = &( *prev )->next;
  133.         }
  134.     }
  135.  
  136. // RAVEN BEGIN
  137. // mwhitlock: Dynamic memory consolidation
  138. #if defined(_RV_MEM_SYS_SUPPORT_CONTAINERS)
  139.     if(ok)
  140.     {
  141.         RV_POP_HEAP();
  142.     }
  143. #endif
  144. // RAVEN END
  145. }
  146.  
  147. /*
  148. ================
  149. idHashTable<Type>::~idHashTable<Type>
  150. ================
  151. */
  152. template< class Type >
  153. ID_INLINE idHashTable<Type>::~idHashTable( void ) {
  154.     Clear();
  155.     delete[] heads;
  156. }
  157.  
  158. /*
  159. ================
  160. idHashTable<Type>::Allocated
  161. ================
  162. */
  163. template< class Type >
  164. ID_INLINE size_t idHashTable<Type>::Allocated( void ) const {
  165.     return sizeof( heads ) * tablesize + sizeof( *heads ) * numentries;
  166. }
  167.  
  168. /*
  169. ================
  170. idHashTable<Type>::Size
  171. ================
  172. */
  173. template< class Type >
  174. ID_INLINE size_t idHashTable<Type>::Size( void ) const {
  175.     return sizeof( idHashTable<Type> ) + sizeof( heads ) * tablesize + sizeof( *heads ) * numentries;
  176. }
  177.  
  178. /*
  179. ================
  180. idHashTable<Type>::GetHash
  181. ================
  182. */
  183. template< class Type >
  184. ID_INLINE int idHashTable<Type>::GetHash( const char *key ) const {
  185.     return ( idStr::Hash( key ) & tablesizemask );
  186. }
  187.  
  188. /*
  189. ================
  190. idHashTable<Type>::Set
  191. ================
  192. */
  193. template< class Type >
  194. ID_INLINE void idHashTable<Type>::Set( const char *key, Type &value ) {
  195.     hashnode_s *node, **nextPtr;
  196.     int hash, s;
  197.  
  198.     hash = GetHash( key );
  199.     for( nextPtr = &(heads[hash]), node = *nextPtr; node != NULL; nextPtr = &(node->next), node = *nextPtr ) {
  200.         s = node->key.Cmp( key );
  201.         if ( s == 0 ) {
  202.             node->value = value;
  203.             return;
  204.         }
  205.         if ( s > 0 ) {
  206.             break;
  207.         }
  208.     }
  209.  
  210.     numentries++;
  211.  
  212. // RAVEN BEGIN
  213. // mwhitlock: Dynamic memory consolidation
  214. #if defined(_RV_MEM_SYS_SUPPORT_CONTAINERS)
  215.     bool ok=rvPushHeapContainingMemory(this);
  216. #endif
  217. // RAVEN END
  218.  
  219.     *nextPtr = new hashnode_s( key, value, heads[ hash ] );
  220.     (*nextPtr)->next = node;
  221.  
  222. // RAVEN BEGIN
  223. // mwhitlock: Dynamic memory consolidation
  224. #if defined(_RV_MEM_SYS_SUPPORT_CONTAINERS)
  225.     if(ok)
  226.     {
  227.         RV_POP_HEAP();
  228.     }
  229. #endif
  230. // RAVEN END
  231. }
  232.  
  233. /*
  234. ================
  235. idHashTable<Type>::Get
  236. ================
  237. */
  238. template< class Type >
  239. ID_INLINE bool idHashTable<Type>::Get( const char *key, Type **value ) const {
  240.     hashnode_s *node;
  241.     int hash, s;
  242.  
  243.     hash = GetHash( key );
  244.     for( node = heads[ hash ]; node != NULL; node = node->next ) {
  245.         s = node->key.Cmp( key );
  246.         if ( s == 0 ) {
  247.             if ( value ) {
  248.                 *value = &node->value;
  249.             }
  250.             return true;
  251.         }
  252.         if ( s > 0 ) {
  253.             break;
  254.         }
  255.     }
  256.  
  257.     if ( value ) {
  258.         *value = NULL;
  259.     }
  260.  
  261.     return false;
  262. }
  263.  
  264. /*
  265. ================
  266. idHashTable<Type>::GetIndex
  267.  
  268. the entire contents can be itterated over, but note that the
  269. exact index for a given element may change when new elements are added
  270. ================
  271. */
  272. template< class Type >
  273. ID_INLINE Type *idHashTable<Type>::GetIndex( int index ) const {
  274.     hashnode_s    *node;
  275.     int            count;
  276.     int            i;
  277.  
  278.     if ( ( index < 0 ) || ( index > numentries ) ) {
  279.         assert( 0 );
  280.         return NULL;
  281.     }
  282.  
  283.     count = 0;
  284.     for( i = 0; i < tablesize; i++ ) {
  285.         for( node = heads[ i ]; node != NULL; node = node->next ) {
  286.             if ( count == index ) {
  287.                 return &node->value;
  288.             }
  289.             count++;
  290.         }
  291.     }
  292.  
  293.     return NULL;
  294. }
  295.  
  296. /*
  297. ================
  298. idHashTable<Type>::Remove
  299. ================
  300. */
  301. template< class Type >
  302. ID_INLINE bool idHashTable<Type>::Remove( const char *key ) {
  303.     hashnode_s    **head;
  304.     hashnode_s    *node;
  305.     hashnode_s    *prev;
  306.     int            hash;
  307.  
  308.     hash = GetHash( key );
  309.     head = &heads[ hash ];
  310.     if ( *head ) {
  311.         for( prev = NULL, node = *head; node != NULL; prev = node, node = node->next ) {
  312.             if ( node->key == key ) {
  313.                 if ( prev ) {
  314.                     prev->next = node->next;
  315.                 } else {
  316.                     *head = node->next;
  317.                 }
  318.  
  319.                 delete node;
  320.                 numentries--;
  321.                 return true;
  322.             }
  323.         }
  324.     }
  325.  
  326.     return false;
  327. }
  328.  
  329. /*
  330. ================
  331. idHashTable<Type>::Clear
  332. ================
  333. */
  334. template< class Type >
  335. ID_INLINE void idHashTable<Type>::Clear( void ) {
  336.     int            i;
  337.     hashnode_s    *node;
  338.     hashnode_s    *next;
  339.  
  340.     for( i = 0; i < tablesize; i++ ) {
  341.         next = heads[ i ];
  342.         while( next != NULL ) {
  343.             node = next;
  344.             next = next->next;
  345.             delete node;
  346.         }
  347.  
  348.         heads[ i ] = NULL;
  349.     }
  350.  
  351.     numentries = 0;
  352. }
  353.  
  354. /*
  355. ================
  356. idHashTable<Type>::DeleteContents
  357. ================
  358. */
  359. template< class Type >
  360. ID_INLINE void idHashTable<Type>::DeleteContents( void ) {
  361.     int            i;
  362.     hashnode_s    *node;
  363.     hashnode_s    *next;
  364.  
  365.     for( i = 0; i < tablesize; i++ ) {
  366.         next = heads[ i ];
  367.         while( next != NULL ) {
  368.             node = next;
  369.             next = next->next;
  370.             delete node->value;
  371.             delete node;
  372.         }
  373.  
  374.         heads[ i ] = NULL;
  375.     }
  376.  
  377.     numentries = 0;
  378. }
  379.  
  380. /*
  381. ================
  382. idHashTable<Type>::Num
  383. ================
  384. */
  385. template< class Type >
  386. ID_INLINE int idHashTable<Type>::Num( void ) const {
  387.     return numentries;
  388. }
  389.  
  390. /*
  391. ================
  392. idHashTable<Type>::GetSpread
  393. ================
  394. */
  395. template< class Type >
  396. int idHashTable<Type>::GetSpread( void ) const {
  397.     int i, average, error, e;
  398.     hashnode_s    *node;
  399.  
  400.     // if no items in hash
  401.     if ( !numentries ) {
  402.         return 100;
  403.     }
  404.     average = numentries / tablesize;
  405.     error = 0;
  406.     for ( i = 0; i < tablesize; i++ ) {
  407.         numItems = 0;
  408.         for( node = heads[ i ]; node != NULL; node = node->next ) {
  409.             numItems++;
  410.         }
  411.         e = abs( numItems - average );
  412.         if ( e > 1 ) {
  413.             error += e - 1;
  414.         }
  415.     }
  416.     return 100 - (error * 100 / numentries);
  417. }
  418.  
  419. #endif /* !__HASHTABLE_H__ */
  420.