neo/idlib/containers/HashTable.h

   1 /*
   2 ===========================================================================
   3
   4 Doom 3 GPL Source Code
   5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
   6
   7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
   8
   9 Doom 3 Source Code is free software: you can redistribute it and/or modify
  10 it under the terms of the GNU General Public License as published by
  11 the Free Software Foundation, either version 3 of the License, or
  12 (at your option) any later version.
  13
  14 Doom 3 Source Code is distributed in the hope that it will be useful,
  15 but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 GNU General Public License for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with Doom 3 Source Code.  If not, see <http://www.gnu.org/licenses/>.
  21
  22 In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code.  If not, please request a copy in writing from id Software at the address below.
  23
  24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
  25
  26 ===========================================================================
  27 */
  28
  29 #ifndef __HASHTABLE_H__
  30 #define __HASHTABLE_H__
  31
  32 /*
  33 ===============================================================================
  34
  35         General hash table. Slower than idHashIndex but it can also be used for
  36         linked lists and other data structures than just indexes or arrays.
  37
  38 ===============================================================================
  39 */
  40
  41 template< class Type >
  42 class idHashTable {
  43 public:
  44                                         idHashTable( int newtablesize = 256 );
  45                                         idHashTable( const idHashTable<Type> &map );
  46                                         ~idHashTable( void );
  47
  48                                         // returns total size of allocated memory
  49         size_t                  Allocated( void ) const;
  50                                         // returns total size of allocated memory including size of hash table type
  51         size_t                  Size( void ) const;
  52
  53         void                    Set( const char *key, Type &value );
  54         bool                    Get( const char *key, Type **value = NULL ) const;
  55         bool                    Remove( const char *key );
  56
  57         void                    Clear( void );
  58         void                    DeleteContents( void );
  59
  60                                         // the entire contents can be itterated over, but note that the
  61                                         // exact index for a given element may change when new elements are added
  62         int                             Num( void ) const;
  63         Type *                  GetIndex( int index ) const;
  64
  65         int                             GetSpread( void ) const;
  66
  67 private:
  68         struct hashnode_s {
  69                 idStr           key;
  70                 Type            value;
  71                 hashnode_s *next;
  72
  73                 hashnode_s( const idStr &k, Type v, hashnode_s *n ) : key( k ), value( v ), next( n ) {};
  74                 hashnode_s( const char *k, Type v, hashnode_s *n ) : key( k ), value( v ), next( n ) {};
  75         };
  76
  77         hashnode_s **   heads;
  78
  79         int                             tablesize;
  80         int                             numentries;
  81         int                             tablesizemask;
  82
  83         int                             GetHash( const char *key ) const;
  84 };
  85
  86 /*
  87 ================
  88 idHashTable<Type>::idHashTable
  89 ================
  90 */
  91 template< class Type >
  92 ID_INLINE idHashTable<Type>::idHashTable( int newtablesize ) {
  93
  94         assert( idMath::IsPowerOfTwo( newtablesize ) );
  95
  96         tablesize = newtablesize;
  97         assert( tablesize > 0 );
  98
  99         heads = new hashnode_s *[ tablesize ];
 100         memset( heads, 0, sizeof( *heads ) * tablesize );
 101
 102         numentries              = 0;
 103
 104         tablesizemask = tablesize - 1;
 105 }
 106
 107 /*
 108 ================
 109 idHashTable<Type>::idHashTable
 110 ================
 111 */
 112 template< class Type >
 113 ID_INLINE idHashTable<Type>::idHashTable( const idHashTable<Type> &map ) {
 114         int                     i;
 115         hashnode_s      *node;
 116         hashnode_s      **prev;
 117
 118         assert( map.tablesize > 0 );
 119
 120         tablesize               = map.tablesize;
 121         heads                   = new hashnode_s *[ tablesize ];
 122         numentries              = map.numentries;
 123         tablesizemask   = map.tablesizemask;
 124
 125         for( i = 0; i < tablesize; i++ ) {
 126                 if ( !map.heads[ i ] ) {
 127                         heads[ i ] = NULL;
 128                         continue;
 129                 }
 130
 131                 prev = &heads[ i ];
 132                 for( node = map.heads[ i ]; node != NULL; node = node->next ) {
 133                         *prev = new hashnode_s( node->key, node->value, NULL );
 134                         prev = &( *prev )->next;
 135                 }
 136         }
 137 }
 138
 139 /*
 140 ================
 141 idHashTable<Type>::~idHashTable<Type>
 142 ================
 143 */
 144 template< class Type >
 145 ID_INLINE idHashTable<Type>::~idHashTable( void ) {
 146         Clear();
 147         delete[] heads;
 148 }
 149
 150 /*
 151 ================
 152 idHashTable<Type>::Allocated
 153 ================
 154 */
 155 template< class Type >
 156 ID_INLINE size_t idHashTable<Type>::Allocated( void ) const {
 157         return sizeof( heads ) * tablesize + sizeof( *heads ) * numentries;
 158 }
 159
 160 /*
 161 ================
 162 idHashTable<Type>::Size
 163 ================
 164 */
 165 template< class Type >
 166 ID_INLINE size_t idHashTable<Type>::Size( void ) const {
 167         return sizeof( idHashTable<Type> ) + sizeof( heads ) * tablesize + sizeof( *heads ) * numentries;
 168 }
 169
 170 /*
 171 ================
 172 idHashTable<Type>::GetHash
 173 ================
 174 */
 175 template< class Type >
 176 ID_INLINE int idHashTable<Type>::GetHash( const char *key ) const {
 177         return ( idStr::Hash( key ) & tablesizemask );
 178 }
 179
 180 /*
 181 ================
 182 idHashTable<Type>::Set
 183 ================
 184 */
 185 template< class Type >
 186 ID_INLINE void idHashTable<Type>::Set( const char *key, Type &value ) {
 187         hashnode_s *node, **nextPtr;
 188         int hash, s;
 189
 190         hash = GetHash( key );
 191         for( nextPtr = &(heads[hash]), node = *nextPtr; node != NULL; nextPtr = &(node->next), node = *nextPtr ) {
 192                 s = node->key.Cmp( key );
 193                 if ( s == 0 ) {
 194                         node->value = value;
 195                         return;
 196                 }
 197                 if ( s > 0 ) {
 198                         break;
 199                 }
 200         }
 201
 202         numentries++;
 203
 204         *nextPtr = new hashnode_s( key, value, heads[ hash ] );
 205         (*nextPtr)->next = node;
 206 }
 207
 208 /*
 209 ================
 210 idHashTable<Type>::Get
 211 ================
 212 */
 213 template< class Type >
 214 ID_INLINE bool idHashTable<Type>::Get( const char *key, Type **value ) const {
 215         hashnode_s *node;
 216         int hash, s;
 217
 218         hash = GetHash( key );
 219         for( node = heads[ hash ]; node != NULL; node = node->next ) {
 220                 s = node->key.Cmp( key );
 221                 if ( s == 0 ) {
 222                         if ( value ) {
 223                                 *value = &node->value;
 224                         }
 225                         return true;
 226                 }
 227                 if ( s > 0 ) {
 228                         break;
 229                 }
 230         }
 231
 232         if ( value ) {
 233                 *value = NULL;
 234         }
 235
 236         return false;
 237 }
 238
 239 /*
 240 ================
 241 idHashTable<Type>::GetIndex
 242
 243 the entire contents can be itterated over, but note that the
 244 exact index for a given element may change when new elements are added
 245 ================
 246 */
 247 template< class Type >
 248 ID_INLINE Type *idHashTable<Type>::GetIndex( int index ) const {
 249         hashnode_s      *node;
 250         int                     count;
 251         int                     i;
 252
 253         if ( ( index < 0 ) || ( index > numentries ) ) {
 254                 assert( 0 );
 255                 return NULL;
 256         }
 257
 258         count = 0;
 259         for( i = 0; i < tablesize; i++ ) {
 260                 for( node = heads[ i ]; node != NULL; node = node->next ) {
 261                         if ( count == index ) {
 262                                 return &node->value;
 263                         }
 264                         count++;
 265                 }
 266         }
 267
 268         return NULL;
 269 }
 270
 271 /*
 272 ================
 273 idHashTable<Type>::Remove
 274 ================
 275 */
 276 template< class Type >
 277 ID_INLINE bool idHashTable<Type>::Remove( const char *key ) {
 278         hashnode_s      **head;
 279         hashnode_s      *node;
 280         hashnode_s      *prev;
 281         int                     hash;
 282
 283         hash = GetHash( key );
 284         head = &heads[ hash ];
 285         if ( *head ) {
 286                 for( prev = NULL, node = *head; node != NULL; prev = node, node = node->next ) {
 287                         if ( node->key == key ) {
 288                                 if ( prev ) {
 289                                         prev->next = node->next;
 290                                 } else {
 291                                         *head = node->next;
 292                                 }
 293
 294                                 delete node;
 295                                 numentries--;
 296                                 return true;
 297                         }
 298                 }
 299         }
 300
 301         return false;
 302 }
 303
 304 /*
 305 ================
 306 idHashTable<Type>::Clear
 307 ================
 308 */
 309 template< class Type >
 310 ID_INLINE void idHashTable<Type>::Clear( void ) {
 311         int                     i;
 312         hashnode_s      *node;
 313         hashnode_s      *next;
 314
 315         for( i = 0; i < tablesize; i++ ) {
 316                 next = heads[ i ];
 317                 while( next != NULL ) {
 318                         node = next;
 319                         next = next->next;
 320                         delete node;
 321                 }
 322
 323                 heads[ i ] = NULL;
 324         }
 325
 326         numentries = 0;
 327 }
 328
 329 /*
 330 ================
 331 idHashTable<Type>::DeleteContents
 332 ================
 333 */
 334 template< class Type >
 335 ID_INLINE void idHashTable<Type>::DeleteContents( 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->value;
 346                         delete node;
 347                 }
 348
 349                 heads[ i ] = NULL;
 350         }
 351
 352         numentries = 0;
 353 }
 354
 355 /*
 356 ================
 357 idHashTable<Type>::Num
 358 ================
 359 */
 360 template< class Type >
 361 ID_INLINE int idHashTable<Type>::Num( void ) const {
 362         return numentries;
 363 }
 364
 365 #if defined(ID_TYPEINFO)
 366 #define __GNUC__ 99
 367 #endif
 368
 369 #if !defined(__GNUC__) || __GNUC__ < 4
 370 /*
 371 ================
 372 idHashTable<Type>::GetSpread
 373 ================
 374 */
 375 template< class Type >
 376 int idHashTable<Type>::GetSpread( void ) const {
 377         int i, average, error, e;
 378         hashnode_s      *node;
 379
 380         // if no items in hash
 381         if ( !numentries ) {
 382                 return 100;
 383         }
 384         average = numentries / tablesize;
 385         error = 0;
 386         for ( i = 0; i < tablesize; i++ ) {
 387                 numItems = 0;
 388                 for( node = heads[ i ]; node != NULL; node = node->next ) {
 389                         numItems++;
 390                 }
 391                 e = abs( numItems - average );
 392                 if ( e > 1 ) {
 393                         error += e - 1;
 394                 }
 395         }
 396         return 100 - (error * 100 / numentries);
 397 }
 398 #endif
 399
 400 #if defined(ID_TYPEINFO)
 401 #undef __GNUC__
 402 #endif
 403
 404 #endif /* !__HASHTABLE_H__ */