home *** CD-ROM | disk | FTP | other *** search
/ GameStar 2006 March / Gamestar_82_2006-03_dvd.iso / DVDStar / Editace / quake4_sdkv10.exe / source / idlib / containers / HashIndex.h < prev    next >
C/C++ Source or Header  |  2005-11-14  |  10KB  |  417 lines
  1.  
  2. #ifndef __HASHINDEX_H__
  3. #define __HASHINDEX_H__
  4.  
  5. /*
  6. ===============================================================================
  7.  
  8.     Fast hash table for indexes and arrays.
  9.     Does not allocate memory until the first key/index pair is added.
  10.  
  11. ===============================================================================
  12. */
  13.  
  14. #define DEFAULT_HASH_SIZE            1024
  15. #define DEFAULT_HASH_GRANULARITY    1024
  16.  
  17. class idHashIndex {
  18. public:
  19.                     idHashIndex( void );
  20.                     idHashIndex( const int initialHashSize, const int initialIndexSize );
  21.                     ~idHashIndex( void );
  22.  
  23.                     // returns total size of allocated memory
  24.     size_t            Allocated( void ) const;
  25.                     // returns total size of allocated memory including size of hash index type
  26.     size_t            Size( void ) const;
  27.  
  28.     idHashIndex &    operator=( const idHashIndex &other );
  29.                     // add an index to the hash, assumes the index has not yet been added to the hash
  30.     void            Add( const int key, const int index );
  31.                     // remove an index from the hash
  32.     void            Remove( const int key, const int index );
  33.                     // get the first index from the hash, returns -1 if empty hash entry
  34.     int                First( const int key ) const;
  35.                     // get the next index from the hash, returns -1 if at the end of the hash chain
  36.     int                Next( const int index ) const;
  37.                     // insert an entry into the index and add it to the hash, increasing all indexes >= index
  38.     void            InsertIndex( const int key, const int index );
  39.                     // remove an entry from the index and remove it from the hash, decreasing all indexes >= index
  40.     void            RemoveIndex( const int key, const int index );
  41.                     // clear the hash
  42.     void            Clear( void );
  43.                     // clear and resize
  44.     void            Clear( const int newHashSize, const int newIndexSize );
  45.                     // free allocated memory
  46.     void            Free( void );
  47.                     // get size of hash table
  48.     int                GetHashSize( void ) const;
  49.                     // get size of the index
  50.     int                GetIndexSize( void ) const;
  51.                     // set granularity
  52.     void            SetGranularity( const int newGranularity );
  53.                     // force resizing the index, current hash table stays intact
  54.     void            ResizeIndex( const int newIndexSize );
  55.                     // returns number in the range [0-100] representing the spread over the hash table
  56.     int                GetSpread( void ) const;
  57.                     // returns a key for a string
  58.     int                GenerateKey( const char *string, bool caseSensitive = true ) const;
  59.                     // returns a key for a vector
  60.     int                GenerateKey( const idVec3 &v ) const;
  61.                     // returns a key for two integers
  62.     int                GenerateKey( const int n1, const int n2 ) const;
  63. // RAVEN BEGIN
  64. // mwhitlock: Dynamic memory consolidation
  65. #if defined(_RV_MEM_SYS_SUPPORT)
  66.     void            SetAllocatorHeap ( rvHeap* heap );                    // set the heap used for all allocations
  67. #endif
  68. // RAVEN END
  69.  
  70. private:
  71.     int                hashSize;
  72.     int *            hash;
  73.     int                indexSize;
  74.     int *            indexChain;
  75.     int                granularity;
  76.     int                hashMask;
  77.     int                lookupMask;
  78.  
  79. // RAVEN BEGIN
  80. // mwhitlock: Dynamic memory consolidation
  81. #if defined(_RV_MEM_SYS_SUPPORT)
  82.     rvHeap*            allocatorHeap;
  83. #endif
  84. // RAVEN END
  85.  
  86.     static int        INVALID_INDEX[1];
  87.  
  88.     void            Init( const int initialHashSize, const int initialIndexSize );
  89.     void            Allocate( const int newHashSize, const int newIndexSize );
  90. };
  91.  
  92. /*
  93. ================
  94. idHashIndex::idHashIndex
  95. ================
  96. */
  97. ID_INLINE idHashIndex::idHashIndex( void ) {
  98.     Init( DEFAULT_HASH_SIZE, DEFAULT_HASH_SIZE );
  99. }
  100.  
  101. /*
  102. ================
  103. idHashIndex::idHashIndex
  104. ================
  105. */
  106. ID_INLINE idHashIndex::idHashIndex( const int initialHashSize, const int initialIndexSize ) {
  107.     Init( initialHashSize, initialIndexSize );
  108. }
  109.  
  110. /*
  111. ================
  112. idHashIndex::~idHashIndex
  113. ================
  114. */
  115. ID_INLINE idHashIndex::~idHashIndex( void ) {
  116.     Free();
  117. }
  118.  
  119. /*
  120. ================
  121. idHashIndex::Allocated
  122. ================
  123. */
  124. ID_INLINE size_t idHashIndex::Allocated( void ) const {
  125.     return hashSize * sizeof( int ) + indexSize * sizeof( int );
  126. }
  127.  
  128. /*
  129. ================
  130. idHashIndex::Size
  131. ================
  132. */
  133. ID_INLINE size_t idHashIndex::Size( void ) const {
  134.     return sizeof( *this ) + Allocated();
  135. }
  136.  
  137. /*
  138. ================
  139. idHashIndex::operator=
  140. ================
  141. */
  142. ID_INLINE idHashIndex &idHashIndex::operator=( const idHashIndex &other ) {
  143.     granularity = other.granularity;
  144.     hashMask = other.hashMask;
  145.     lookupMask = other.lookupMask;
  146.  
  147.     if ( other.lookupMask == 0 ) {
  148.         hashSize = other.hashSize;
  149.         indexSize = other.indexSize;
  150.         Free();
  151.     }
  152.     else {
  153. // RAVEN BEGIN
  154. // mwhitlock: Dynamic memory consolidation
  155. #if defined(_RV_MEM_SYS_SUPPORT)
  156.         if(allocatorHeap)
  157.         {
  158.             RV_PUSH_HEAP_PTR(allocatorHeap);
  159.         }
  160. #endif
  161. // RAVEN END
  162.  
  163.         if ( other.hashSize != hashSize || hash == INVALID_INDEX ) {
  164.             if ( hash != INVALID_INDEX ) {
  165.                 delete[] hash;
  166.             }
  167.             hashSize = other.hashSize;
  168.             hash = new int[hashSize];
  169.         }
  170.         if ( other.indexSize != indexSize || indexChain == INVALID_INDEX ) {
  171.             if ( indexChain != INVALID_INDEX ) {
  172.                 delete[] indexChain;
  173.             }
  174.             indexSize = other.indexSize;
  175.             indexChain = new int[indexSize];
  176.         }
  177. // RAVEN BEGIN
  178. // mwhitlock: Dynamic memory consolidation
  179. #if defined(_RV_MEM_SYS_SUPPORT)
  180.         if(allocatorHeap)
  181.         {
  182.             RV_POP_HEAP();
  183.         }
  184. #endif
  185. // RAVEN END
  186.  
  187.         memcpy( hash, other.hash, hashSize * sizeof( hash[0] ) );
  188.         memcpy( indexChain, other.indexChain, indexSize * sizeof( indexChain[0] ) );
  189.     }
  190.  
  191.     return *this;
  192. }
  193.  
  194. /*
  195. ================
  196. idHashIndex::Add
  197. ================
  198. */
  199. ID_INLINE void idHashIndex::Add( const int key, const int index ) {
  200.     int h;
  201. // RAVEN BEGIN
  202. // jnewquist: Tag scope and callees to track allocations using "new".
  203.     MEM_SCOPED_TAG(tag,MA_DEFAULT);
  204. // RAVEN END
  205.  
  206.     assert( index >= 0 );
  207.     if ( hash == INVALID_INDEX ) {
  208.         Allocate( hashSize, index >= indexSize ? index + 1 : indexSize );
  209.     }
  210.     else if ( index >= indexSize ) {
  211.         ResizeIndex( index + 1 );
  212.     }
  213.     h = key & hashMask;
  214.     indexChain[index] = hash[h];
  215.     hash[h] = index;
  216. }
  217.  
  218. /*
  219. ================
  220. idHashIndex::Remove
  221. ================
  222. */
  223. ID_INLINE void idHashIndex::Remove( const int key, const int index ) {
  224.     int k = key & hashMask;
  225.  
  226.     if ( hash == INVALID_INDEX ) {
  227.         return;
  228.     }
  229.     if ( hash[k] == index ) {
  230.         hash[k] = indexChain[index];
  231.     }
  232.     else {
  233.         for ( int i = hash[k]; i != -1; i = indexChain[i] ) {
  234.             if ( indexChain[i] == index ) {
  235.                 indexChain[i] = indexChain[index];
  236.                 break;
  237.             }
  238.         }
  239.     }
  240.     indexChain[index] = -1;
  241. }
  242.  
  243. /*
  244. ================
  245. idHashIndex::First
  246. ================
  247. */
  248. ID_INLINE int idHashIndex::First( const int key ) const {
  249.     return hash[key & hashMask & lookupMask];
  250. }
  251.  
  252. /*
  253. ================
  254. idHashIndex::Next
  255. ================
  256. */
  257. ID_INLINE int idHashIndex::Next( const int index ) const {
  258.     assert( index >= 0 && index < indexSize );
  259.     return indexChain[index & lookupMask];
  260. }
  261.  
  262. /*
  263. ================
  264. idHashIndex::InsertIndex
  265. ================
  266. */
  267. ID_INLINE void idHashIndex::InsertIndex( const int key, const int index ) {
  268.     int i, max;
  269.  
  270.     if ( hash != INVALID_INDEX ) {
  271.         max = index;
  272.         for ( i = 0; i < hashSize; i++ ) {
  273.             if ( hash[i] >= index ) {
  274.                 hash[i]++;
  275.                 if ( hash[i] > max ) {
  276.                     max = hash[i];
  277.                 }
  278.             }
  279.         }
  280.         for ( i = 0; i < indexSize; i++ ) {
  281.             if ( indexChain[i] >= index ) {
  282.                 indexChain[i]++;
  283.                 if ( indexChain[i] > max ) {
  284.                     max = indexChain[i];
  285.                 }
  286.             }
  287.         }
  288.         if ( max >= indexSize ) {
  289.             ResizeIndex( max + 1 );
  290.         }
  291.         for ( i = max; i > index; i-- ) {
  292.             indexChain[i] = indexChain[i-1];
  293.         }
  294.         indexChain[index] = -1;
  295.     }
  296.     Add( key, index );
  297. }
  298.  
  299. /*
  300. ================
  301. idHashIndex::RemoveIndex
  302. ================
  303. */
  304. ID_INLINE void idHashIndex::RemoveIndex( const int key, const int index ) {
  305.     int i, max;
  306.  
  307.     Remove( key, index );
  308.     if ( hash != INVALID_INDEX ) {
  309.         max = index;
  310.         for ( i = 0; i < hashSize; i++ ) {
  311.             if ( hash[i] >= index ) {
  312.                 if ( hash[i] > max ) {
  313.                     max = hash[i];
  314.                 }
  315.                 hash[i]--;
  316.             }
  317.         }
  318.         for ( i = 0; i < indexSize; i++ ) {
  319.             if ( indexChain[i] >= index ) {
  320.                 if ( indexChain[i] > max ) {
  321.                     max = indexChain[i];
  322.                 }
  323.                 indexChain[i]--;
  324.             }
  325.         }
  326.         for ( i = index; i < max; i++ ) {
  327.             indexChain[i] = indexChain[i+1];
  328.         }
  329.         indexChain[max] = -1;
  330.     }
  331. }
  332.  
  333. /*
  334. ================
  335. idHashIndex::Clear
  336. ================
  337. */
  338. ID_INLINE void idHashIndex::Clear( void ) {
  339.     // only clear the hash table because clearing the indexChain is not really needed
  340.     if ( hash != INVALID_INDEX ) {
  341.         memset( hash, 0xff, hashSize * sizeof( hash[0] ) );
  342.     }
  343. }
  344.  
  345. /*
  346. ================
  347. idHashIndex::Clear
  348. ================
  349. */
  350. ID_INLINE void idHashIndex::Clear( const int newHashSize, const int newIndexSize ) {
  351.     Free();
  352.     hashSize = newHashSize;
  353.     indexSize = newIndexSize;
  354. }
  355.  
  356. /*
  357. ================
  358. idHashIndex::GetHashSize
  359. ================
  360. */
  361. ID_INLINE int idHashIndex::GetHashSize( void ) const {
  362.     return hashSize;
  363. }
  364.  
  365. /*
  366. ================
  367. idHashIndex::GetIndexSize
  368. ================
  369. */
  370. ID_INLINE int idHashIndex::GetIndexSize( void ) const {
  371.     return indexSize;
  372. }
  373.  
  374. /*
  375. ================
  376. idHashIndex::SetGranularity
  377. ================
  378. */
  379. ID_INLINE void idHashIndex::SetGranularity( const int newGranularity ) {
  380.     assert( newGranularity > 0 );
  381.     granularity = newGranularity;
  382. }
  383.  
  384. /*
  385. ================
  386. idHashIndex::GenerateKey
  387. ================
  388. */
  389. ID_INLINE int idHashIndex::GenerateKey( const char *string, bool caseSensitive ) const {
  390.     if ( caseSensitive ) {
  391.         return ( idStr::Hash( string ) & hashMask );
  392.     } else {
  393.         return ( idStr::IHash( string ) & hashMask );
  394.     }
  395. }
  396.  
  397. /*
  398. ================
  399. idHashIndex::GenerateKey
  400. ================
  401. */
  402. ID_INLINE int idHashIndex::GenerateKey( const idVec3 &v ) const {
  403.     return ( (((int) v[0]) + ((int) v[1]) + ((int) v[2])) & hashMask );
  404. //    return ( ( idMath::FtoiFast( v[0] ) + idMath::FtoiFast( v[1] ) + idMath::FtoiFast( v[2] ) ) & hashMask );
  405. }
  406.  
  407. /*
  408. ================
  409. idHashIndex::GenerateKey
  410. ================
  411. */
  412. ID_INLINE int idHashIndex::GenerateKey( const int n1, const int n2 ) const {
  413.     return ( ( n1 + n2 ) & hashMask );
  414. }
  415.  
  416. #endif /* !__HASHINDEX_H__ */
  417.