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