/[pcsx2_0.9.7]/trunk/common/include/Utilities/HashMap.h
ViewVC logotype

Contents of /trunk/common/include/Utilities/HashMap.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 62 - (show annotations) (download)
Tue Sep 7 11:08:22 2010 UTC (9 years, 10 months ago) by william
File MIME type: text/plain
File size: 25418 byte(s)
Auto Commited Import of: pcsx2-0.9.7-r3738-debug in ./trunk
1 /* PCSX2 - PS2 Emulator for PCs
2 * Copyright (C) 2002-2010 PCSX2 Dev Team
3 *
4 * PCSX2 is free software: you can redistribute it and/or modify it under the terms
5 * of the GNU Lesser General Public License as published by the Free Software Found-
6 * ation, either version 3 of the License, or (at your option) any later version.
7 *
8 * PCSX2 is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
9 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
10 * PURPOSE. See the GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License along with PCSX2.
13 * If not, see <http://www.gnu.org/licenses/>.
14 */
15
16 #pragma once
17
18 #include <google/type_traits.h>
19 #include <google/dense_hash_set>
20 #include <google/dense_hash_map>
21 #include <google/sparsehash/densehashtable.h>
22
23 #include <wx/string.h>
24
25 namespace HashTools {
26
27 #define HashFriend(Key,T) friend class HashMap<Key,T>
28
29 /// Defines an equality comparison unary method.
30 /// Generally intended for internal use only.
31 #define _EQUALS_UNARY_OP( Type ) bool operator()(const Type s1, const Type s2) const { return s1.Equals( s2 ); }
32
33 /// Defines a hash code unary method
34 /// Generally intended for internal use only.
35 #define _HASHCODE_UNARY_OP( Type ) hash_key_t operator()( const Type& val ) const { return val.GetHashCode(); }
36
37 /// <summary>
38 /// Defines an equality comparison method within an encapsulating struct, using the 'unary method' approach.
39 /// </summary>
40 /// <remarks>
41 /// <para>
42 /// This macro is a shortcut helper to implementing types usable as keys in <see cref="HashMap"/>s.
43 /// Normally you will want to use <see cref="DEFINE_HASH_API"/> instead as it defines both
44 /// the HashCode predicate and Compare predicate.
45 /// </para>
46 /// The code generated by this macro is equivalent to this:
47 /// <code>
48 /// // where 'Type' is the parameter used in the macro.
49 /// struct UnaryEquals
50 /// {
51 /// bool operator()(const Type s1, const Type s2) const
52 /// {
53 /// return s1.Equals( s2 ); // this operator must be implemented by the user.
54 /// }
55 /// };
56 /// </code>
57 /// Note:
58 /// In C++, the term 'unary method' refers to a method that is implemented as an overload of the
59 /// <c>operator ()</c>, such that the object instance itself acts as a method.
60 /// Note:
61 /// This methodology is similar to C# / .NET's <c>object.Equals()</c> method: The class member method
62 /// implementation of <c>Equals</c> should *not* throw exceptions -- it should instead return <c>false</c>
63 /// if either side of the comparison is not a matching type. See <see cref="IHashable" /> for details.
64 /// Note:
65 /// The reason for this (perhaps seemingly) hogwash red tape is because you can define custom
66 /// equality behavior for individual hashmaps, which are independent of the type used. The only
67 /// obvious scenario where such a feature is useful is in
68 /// </remarks>
69 /// <seealso cref="DEFINE_HASHCODE_UNARY"/>
70 /// <seealso cref="DEFINE_HASH_API"/>
71 /// <seealso cref="IHashable"/>
72 /// <seealso cref="HashMap"/>
73 #define DEFINE_EQUALS_UNARY( Type ) struct UnaryEquals{ _EQUALS_UNARY_OP( Type ) }
74
75 /// <summary>
76 /// Defines a hash code predicate within an encapsulating struct; for use in hashable user datatypes
77 /// </summary>
78 /// <remarks>
79 /// <para>
80 /// This macro is a shortcut helper to implementing types usable as keys in <see cref="HashMap"/>s.
81 /// Normally you will want to use <see cref="DEFINE_HASH_API"/> instead as it defines both
82 /// the HashCode predicate and Compare predicate.
83 /// </para>
84 /// The code generated by this macro is equivalent to this:
85 /// <code>
86 /// // where 'Type' is the parameter used in the macro.
87 /// struct UnaryHashCode
88 /// {
89 /// hash_key_t operator()( const Type& val ) const
90 /// {
91 /// return val.GetHashCode(); // this member function must be implemented by the user.
92 /// }
93 /// };
94 /// </code>
95 /// </remarks>
96 /// <seealso cref="DEFINE_EQUALS_UNARY"/>
97 /// <seealso cref="DEFINE_HASH_API"/>
98 /// <seealso cref="IHashable"/>
99 /// <seealso cref="HashMap"/>
100 #define DEFINE_HASHCODE_UNARY( Type ) struct UnaryHashCode{ _HASHCODE_UNARY_OP( Type ) }
101
102 /// <summary>
103 /// Defines the API for hashcode and comparison unary methods; for use in hashable user datatypes
104 /// </summary>
105 /// <remarks>
106 /// This macro creates APIs that allow the class or struct to be used as a key in a <see cref="HashMap"/>.
107 /// It requires that the data type implement the following items:
108 /// * An equality test via an <c>operator==</c> overload.
109 /// * A public instance member method <c>GetHashCode.</c>
110 /// The code generated by this macro is equivalent to this:
111 /// <code>
112 /// // where 'Type' is the parameter used in the macro.
113 /// struct UnaryHashCode
114 /// {
115 /// hash_key_t operator()( const Type& val ) const
116 /// {
117 /// return val.GetHashCode(); // this member function must be implemented by the user.
118 /// }
119 /// };
120 ///
121 /// struct UnaryEquals
122 /// {
123 /// bool operator()(const Type s1, const Type s2) const
124 /// {
125 /// return s1.Equals( s2 ); // this operator must be implemented by the user.
126 /// }
127 /// };
128 /// </code>
129 /// Note:
130 /// In C++, the term 'unary method' refers to a method that is implemented as an overload of the
131 /// <c>operator ()</c>, such that the object instance itself acts as a method.
132 /// Note:
133 /// For class types you can use the <see cref="IHashable"/> interface, which also allows you to group
134 /// multiple types of objects into a single complex HashMap.
135 /// Note:
136 /// Generally speaking, you do not use the <c>IHashable</c> interface on simple C-style structs, since it
137 /// would incur the overhead of a vtbl and could potentially break code that assumes the structs to have
138 /// 1-to-1 data-to-declaration coorlations.
139 /// Note:
140 /// Internally, using this macro is functionally equivalent to using both <see cref="DEFINE_HASHCODE_CLASS"/>
141 /// and <see cref="DEFINE_EQUALS_CLASS"/>.
142 /// </remarks>
143 /// <seealso cref="IHashable"/>
144 /// <seealso cref="DEFINE_HASHCODE_CLASS"/>
145 /// <seealso cref="DEFINE_COMPARE_CLASS"/>
146 /// <seealso cref="DEFINE_HASH_API"/>
147 /// <seealso cref="HashMap"/>
148 #define DEFINE_HASH_API( Type ) DEFINE_HASHCODE_UNARY( Type ); DEFINE_EQUALS_UNARY( Type );
149
150 /// <summary>
151 /// A helper macro for creating custom types that can be used as <see cref="HashMap" /> keys.
152 /// </summary>
153 /// <remarks>
154 /// Use of this macro is only needed if the hashable type in question is a struct that is a private
155 /// local to the namespace of a containing class.
156 /// </remarks>
157 #define PRIVATE_HASHMAP( Key, T ) \
158 typedef SpecializedHashMap<Key, T> Key##HashMap; \
159 friend Key##HashMap;
160
161 /// <summary>
162 /// Type that represents a hashcode; returned by all hash functions.
163 /// </summary>
164 /// <remarks>
165 /// In theory this could be changed to a 64 bit value in the future, although many of the hash algorithms
166 /// would have to be changed to take advantage of the larger data type.
167 /// </remarks>
168 typedef u32 hash_key_t;
169
170 hash_key_t Hash(const char* data, int len);
171
172 struct CommonHashClass;
173 extern const CommonHashClass GetCommonHash;
174
175 /// <summary>
176 /// A unary-style set of methods for getting the hash code of C++ fundamental types.
177 /// </summary>
178 /// <remarks>
179 /// This class is used to pass hash functions into the <see cref="HashMap"/> class and
180 /// it's siblings. It houses methods for most of the fundamental types of C++ and the STL,
181 /// such as all int and float types, and also <c>std::string</c>. All functions can be
182 /// accessed via the () overload on an instance of the class, such as:
183 /// <code>
184 /// const CommonHashClass GetHash;
185 /// int v = 27;
186 /// std::string s = "Joe's World!";
187 /// hash_key_t hashV = GetHash( v );
188 /// hash_key_t hashS = GetHash( s );
189 /// </code>
190 /// Note:
191 /// In C++, the term 'unary method' refers to a method that is implemented as an overload of the
192 /// <c>operator ()</c>, such that the object instance itself acts as a method.
193 /// </remarks>
194 /// <seealso cref="GetCommonHash"/>
195 struct CommonHashClass
196 {
197 public:
198 // GCC needs empty constructors on const instances, because it likes pointlessness.
199 CommonHashClass() {}
200
201 hash_key_t DoInt( u32 val ) const
202 {
203 u32 key = val;
204 key = ~key + (key << 15);
205 key = key ^ (key >> 12);
206 key = key + (key << 2);
207 key = key ^ (key >> 4);
208 key = key * 2057;
209 key = key ^ (key >> 16);
210
211 return val;
212 }
213
214 hash_key_t operator()(const std::string& src) const
215 {
216 return Hash( src.data(), src.length() );
217 }
218
219 hash_key_t operator()( const std::wstring& src ) const
220 {
221 return Hash( (const char *)src.data(), src.length() * sizeof( wchar_t ) );
222 }
223
224 hash_key_t operator()( const wxString& src ) const
225 {
226 return Hash( (const char *)src.data(), src.length() * sizeof( wxChar ) );
227 }
228
229 // Returns a hashcode for a character.
230 // This has function has been optimized to return an even distribution
231 // across the range of an int value. In theory that should be more rewarding
232 // to hastable performance than a straight up char lookup.
233 hash_key_t operator()( const char c1 ) const
234 {
235 // Most chars contain values between 0 and 128, so let's mix it up a bit:
236 int cs = (int)( c1 + (char)64 );
237 return ( cs + ( cs<<8 ) + ( cs << 16 ) + (cs << 24 ) );
238 }
239
240 hash_key_t operator()( const wchar_t wc1 ) const
241 {
242 // Most unicode values are between 0 and 128, with 0-1024
243 // making up the bulk of the rest. Everything else is spatially used.
244 /*int wcs = (int) ( wc1 + 0x2000 );
245 return wcs ^ ( wcs + 0x19000 );*/
246
247 // or maybe I'll just feed it into the int hash:
248 return GetCommonHash( (u32)wc1 );
249 }
250
251 /// <summary>
252 /// Gets the hash code for a 32 bit integer.
253 /// </summary>
254 /// <remarks>
255 /// This method performs a very fast algorithm optimized for typical integral
256 /// dispersion patterns (which tend to favor a bit heavy on the lower-range of values while
257 /// leaving the extremes un-used).
258 /// Note:
259 /// Implementation is based on an article found here: http://www.concentric.net/~Ttwang/tech/inthash.htm
260 /// </remarks>
261 hash_key_t operator()( const u32 val ) const
262 {
263 return DoInt(val);
264 }
265
266 /// <summary>
267 /// Gets the hash code for a 32 bit integer.
268 /// </summary>
269 /// <remarks>
270 /// This method performs a very fast algorithm optimized for typical integral
271 /// dispersion patterns (which tend to favor a bit heavy on the lower-range of values while
272 /// leaving the extremes un-used).
273 /// Note:
274 /// Implementation is based on an article found here: http://www.concentric.net/~Ttwang/tech/inthash.htm
275 /// </remarks>
276 hash_key_t operator()( const s32 val ) const
277 {
278 return DoInt(val);
279 }
280
281 /// <summary>
282 /// Gets the hash code for a 64 bit integer.
283 /// </summary>
284 /// <remarks>
285 /// This method performs a very fast algorithm optimized for typical integral
286 /// dispersion patterns (which tend to favor a bit heavy on the lower-range of values while
287 /// leaving the extremes un-used).
288 /// Note:
289 /// Implementation is based on an article found here: http://www.concentric.net/~Ttwang/tech/inthash.htm
290 /// </remarks>
291 hash_key_t operator()( const u64 val ) const
292 {
293 u64 key = val;
294 key = (~key) + (key << 18);
295 key = key ^ (key >> 31);
296 key = key * 21; // key = (key + (key << 2)) + (key << 4);
297 key = key ^ (key >> 11);
298 key = key + (key << 6);
299 key = key ^ (key >> 22);
300 return (u32) key;
301 }
302
303 /// <summary>
304 /// Gets the hash code for a 64 bit integer.
305 /// </summary>
306 /// <remarks>
307 /// This method performs a very fast algorithm optimized for typical integral
308 /// dispersion patterns (which tend to favor a bit heavy on the lower-range of values while
309 /// leaving the extremes un-used).
310 /// Note:
311 /// Implementation is based on an article found here: http://www.concentric.net/~Ttwang/tech/inthash.htm
312 /// </remarks>
313 hash_key_t operator()( const s64 val ) const
314 {
315 return GetCommonHash((u64)val);
316 }
317
318 hash_key_t operator()( const float val ) const
319 {
320 // floats do a fine enough job of being scattered about
321 // the universe:
322 return *((hash_key_t *)&val);
323 }
324
325 hash_key_t operator()( const double val ) const
326 {
327 // doubles have to be compressed into a 32 bit value:
328 return GetCommonHash( *((u64*)&val) );
329 }
330
331 /// <summary>
332 /// Calculates the hash of a pointer.
333 /// </summary>
334 /// <remarks>
335 /// This method has been optimized to give typical 32 bit pointers a reasonably
336 /// wide spread across the integer spectrum.
337 /// Note:
338 /// This method is optimized for 32 bit pointers only. 64 bit pointer support
339 /// has not been implemented, and thus on 64 bit platforms performance could be poor or,
340 /// worse yet, results may not have a high degree of uniqueness.
341 /// </remarks>
342 hash_key_t operator()( const void* addr ) const
343 {
344 hash_key_t key = (hash_key_t) addr;
345 return (hash_key_t)((key >> 3) * 2654435761ul);
346 }
347
348
349 };
350
351 /// <summary>
352 /// This class contains comparison methods for most fundamental types; and is used by the CommonHashMap class.
353 /// </summary>
354 /// <remarks>
355 /// The predicates of this class do standard equality comparisons between fundamental C/STL types such as
356 /// <c>int, float</c>, and <c>std::string.</c> Usefulness of this class outside the <see cref="CommonHashMap"/>
357 /// class is limited.
358 /// </remarks>
359 /// <seealso cref="CommonHashMap">
360 struct CommonComparisonClass
361 {
362 bool operator()(const char* s1, const char* s2) const
363 {
364 return (s1 == s2) || (s1 && s2 && strcmp(s1, s2) == 0);
365 }
366 };
367
368 /// <summary>
369 /// An interface for classes that implement hashmap functionality.
370 /// </summary>
371 /// <remarks>
372 /// This class provides interface methods for getting th hashcode of a class and checking for object
373 /// equality. It's general intent is for use in situations where you have to store *non-similar objects*
374 /// in a single unified hash map. As all object instances derive from this type, it allows the equality
375 /// comparison to use typeid or dynamic casting to check for type similarity, and then use more detailed
376 /// equality checks for similar types.
377 /// </remarks>
378 class IHashable
379 {
380 public:
381 /// Obligatory Virtual destructor mess!
382 virtual ~IHashable() {};
383
384 /// <summary>
385 /// Your basic no-thrills equality comparison; using a pointer comparison by default.
386 /// </summary>
387 /// <remarks>
388 /// This method uses a pointer comparison by default, which is the only way to really compare objects
389 /// of unrelated types or of derrived types. When implementing this method, you may want to use typeid comparisons
390 /// if you want derived types to register as being non-equal, or <c>dynamic_cast</c> for a more robust
391 /// base-class comparison (illustrated in the example below).
392 /// Note:
393 /// It's recommended important to always do a pointer comparison as the first step of any object equality check.
394 /// It is fast and easy, and 100% reliable.
395 /// </remarks>
396 /// <example>
397 /// Performing non-pointer comparisons:
398 /// <code>
399 /// class Hasher : IHashable
400 /// {
401 /// int someValue;
402 ///
403 /// virtual bool Equals( const IHashable& right ) const
404 /// {
405 /// // Use pointer comparison first since it's fast and accurate:
406 /// if( &right == this ) return true;
407 ///
408 /// Hasher* them = dynamic_cast&lt;Hasher*&gt;( right );
409 /// if( them == NULL ) return false;
410 /// return someValue == them->SomeValue;
411 /// }
412 /// }
413 /// </code>
414 /// </example>
415 virtual bool Equals( const IHashable& right ) const
416 {
417 return ( &right == this ); // pointer comparison.
418 }
419
420 /// <summary>
421 /// Returns a hash value for this object; by default the hash of its pointer address.
422 /// </summary>
423 /// <remarks>
424 /// </remarks>
425 /// <seealso cref="HashMap"/>
426 virtual hash_key_t GetHashCode() const
427 {
428 return GetCommonHash( this );
429 }
430 };
431
432 template< typename Key >
433 class HashSet : public google::dense_hash_set< Key, CommonHashClass >
434 {
435 public:
436 /// <summary>
437 /// Constructor.
438 /// </summary>
439 /// <remarks>
440 /// Both the <c>emptyKey</c>a nd c>deletedKey</c> parameters must be unique values that
441 /// are *not* used as actual values in the set.
442 /// </remarks>
443 HashSet( Key emptyKey, Key deletedKey, int initialCapacity=33 ) :
444 google::dense_hash_set<Key, CommonHashClass>( initialCapacity )
445 {
446 set_empty_key( emptyKey );
447 set_deleted_key( deletedKey );
448 }
449 };
450
451 /// <summary>
452 /// Defines a hashed collection of objects and provides methods for adding, removing, and reading items.
453 /// </summary>
454 /// <remarks>
455 /// <para>This class is for hashing out a set data using objects as keys. Objects should derive from the
456 /// <see cref="IHashable"/> type, and in either case *must* implement the UnaryHashCode and UnaryEquals
457 /// unary classes.</para>
458 /// <para>*Details On Implementing Key Types*</para>
459 /// <para>
460 /// Custom hash keying uses what I consider a somewhat contrived method of implementing the Key type;
461 /// involving a handful of macros in the best case, and a great deal of syntaxical red tape in
462 /// the worst case. Most cases should fall within the realm of the macros, which make life a lot easier,
463 /// so that's the only implementation I will cover in detail here (see below for example).
464 /// </para>
465 /// Note:
466 /// For most hashs based on common or fundamental types or types that can be adequately compared using
467 /// the default equality operator ==, such as <c>int</c> or structs that have no padding alignment concerns,
468 /// use <see cref="HashMap" /> instead. For string-based hashs, use <see cref="Dictionary" /> or <see cref="UnicodeDictionary" />.
469 /// </remarks>
470 /// <example>
471 /// This is an example of making a hashable type out of a struct. This is useful in situations where
472 /// inheriting the <see cref="IHashable"/> type would cause unnecessary overhead and/or broken C/C++
473 /// compatability.
474 /// <code>
475 /// struct Point
476 /// {
477 /// int x, y;
478 ///
479 /// // Empty constructor is necessary for HashMap.
480 /// // This can either be initialized to zero, or uninitialized as here:
481 /// Point() {}
482 ///
483 /// // Copy Constructor is just always necessary.
484 /// Point( const Point& src ) : first( src.first ), second( src.second ) {}
485 ///
486 /// // Standard content constructor (Not needed by HashMap)
487 /// Point( int xpos, int ypos ) : x( xpos ), y( ypos ) {}
488 ///
489 /// /**** Begin Hashmap Interface Implementation ****/
490 ///
491 /// // HashMap Requires both GetEmptyKey() and GetDeleteKey() instance member
492 /// // methods to be defined. These act as defaults. The actual values used
493 /// // can be overridden on an individual HashMap basis via the HashMap constructor.
494 ///
495 /// static Point GetEmptyKey() { return Point( -0xffffff, 0xffffff ); }
496 /// static Point GetDeletedKey() { return Kerning( -0xffffee, 0xffffee ); }
497 ///
498 /// // HashMap Requires an Equality Overload.
499 /// // The inequality overload is not required but is probably a good idea since
500 /// // orphaned equality (without sibling inequality) operator overloads are ugly code.
501 ///
502 /// bool Equals( const Point& right ) const
503 /// {
504 /// return ( x == right.x ) && ( y == right.y );
505 /// }
506 ///
507 /// hash_key_t GetHashCode() const
508 /// {
509 /// // This is a decent "universal" hash method for when you have multiple int types:
510 /// return GetCommonHash( x ) ^ GetCommonHash( y );
511 /// }
512 ///
513 /// // Use a macro to expose the hash API to the HashMap templates.
514 /// // This macro creates MakeHashCode and Compare structs, which use the ()
515 /// // operator to create "unary methods" for the GetHashCode and == operator above.
516 /// // Feeling dizzy yet? Don't worry. Just follow this template. It works!
517 ///
518 /// DEFINE_HASH_API( Point );
519 ///
520 /// /**** End HashMap Interface Implementation ****/
521 /// };
522 /// </code>
523 /// </example>
524 template< class Key, class T >
525 class SpecializedHashMap : public google::dense_hash_map<Key, T, typename Key::UnaryHashCode, typename Key::UnaryEquals>
526 {
527 public:
528 virtual ~SpecializedHashMap() {}
529 SpecializedHashMap( int initialCapacity=33, Key emptyKey=Key::GetEmptyKey(), Key deletedKey=Key::GetDeletedKey() ) :
530 google::dense_hash_map<Key, T, typename Key::UnaryHashCode, typename Key::UnaryEquals>( initialCapacity )
531 {
532 set_empty_key( emptyKey );
533 set_deleted_key( deletedKey );
534 }
535
536 /// <summary>
537 /// Tries to get a value from this hashmap; or does nothing if the Key does not exist.
538 /// </summary>
539 /// <remarks>
540 /// If found, the value associated with the requested key is copied into the <c>outval</c>
541 /// parameter. This is a more favorable alternative to the indexer operator since the
542 /// indexer implementation can and will create new entries for every request that
543 /// </remarks>
544 /*void TryGetValue( const Key& key, T& outval ) const
545 {
546 // GCC doesn't like this for some reason -- says const_iterator can't be found.
547 // Fortunately nothing uses these functions yet, so I just commented them out. --air
548 const_iterator iter = find( key );
549 if( iter != end() )
550 outval = iter->second;
551 }*/
552
553 const T& GetValue( Key key ) const
554 {
555 return (find( key ))->second;
556 }
557 };
558
559 /// <summary>
560 /// This class implements a hashmap that uses fundamental types such as <c>int</c> or <c>std::string</c>
561 /// as keys.
562 /// </summary>
563 /// <remarks>
564 /// This class is provided so that you don't have to jump through hoops in order to use fundamental types as
565 /// hash keys. The <see cref="HashMap" /> class isn't suited to the task since it requires the key type to
566 /// include a set of unary methods. Obviously predicates cannot be added to fundamentals after the fact. :)
567 /// Note:
568 /// Do not use <c>char *</c> or <c>wchar_t *</c> as key types. Use <c>std::string</c> and <c>std::wstring</c>
569 /// instead, as performance of those types will generally be superior due to string length caching. For that
570 /// matter, don't use this class at all! Use the string-specialized classes <see cref="Dictionary" /> and
571 /// <see cref="UnicodeDictionary" />.
572 /// </remarks>
573 template< class Key, class T, class HashFunctor=CommonHashClass >
574 class HashMap : public google::dense_hash_map<Key, T, HashFunctor>
575 {
576 DeclareNoncopyableObject( HashMap );
577
578 typedef typename google::dense_hash_map<Key, T, HashFunctor> _parent;
579
580 public:
581 using _parent::operator[];
582 using _parent::end;
583 typedef typename _parent::const_iterator const_iterator;
584
585 virtual ~HashMap() {}
586
587 /// <summary>
588 /// Constructor.
589 /// </summary>
590 /// <remarks>
591 /// Both the <c>emptyKey</c>a nd c>deletedKey</c> parameters must be unique values that
592 /// are *not* used as actual values in the set.
593 /// </remarks>
594 HashMap( const Key& emptyKey, const Key& deletedKey, int initialCapacity=33 ) :
595 google::dense_hash_map<Key, T, HashFunctor>( initialCapacity )
596 {
597 set_empty_key( emptyKey );
598 set_deleted_key( deletedKey );
599 }
600
601 /// <summary>
602 /// Tries to get a value from this hashmap; or does nothing if the Key does not exist.
603 /// </summary>
604 /// <remarks>
605 /// If found, the value associated with the requested key is copied into the <c>outval</c>
606 /// parameter. This is a more favorable alternative to the indexer operator since the
607 /// indexer implementation can and will create new entries for every request that
608 /// </remarks>
609 bool TryGetValue( const Key& key, T& outval ) const
610 {
611 const_iterator iter( find(key) );
612 if( iter != end() )
613 {
614 outval = iter->second;
615 return true;
616 }
617 return false;
618 }
619
620 const T& GetValue( Key key ) const
621 {
622 return (find( key ))->second;
623 }
624
625 bool Find( Key key ) const
626 {
627 return find(key) != end();
628 }
629 };
630
631 /// <summary>
632 /// A shortcut class for easy implementation of string-based hash maps.
633 /// </summary>
634 /// <remarks>
635 /// Note:
636 /// This class does not support Unicode character sets natively. To use Unicode strings as keys,
637 /// use <see cref="UnicodeDictionary"/> instead.
638 /// </remarks>
639 template< class T >
640 class Dictionary : public HashMap<std::string, T>
641 {
642 public:
643 virtual ~Dictionary() {}
644
645 Dictionary( int initialCapacity=33, const std::string& emptyKey = "@@-EMPTY-@@", const std::string& deletedKey = "@@-DELETED-@@" )
646 : HashMap<std::string, T>( emptyKey, deletedKey, initialCapacity)
647 {
648 }
649 };
650
651 /// <summary>
652 /// A shortcut class for easy implementation of string-based hash maps.
653 /// </summary>
654 /// <remarks>
655 /// Note:
656 /// This class does incur some amount of additional overhead over <see cref="Dictionary"/>, as it
657 /// requires twice as much memory and much hash twice as much data.
658 /// If you're only using the hash for friendly named array access (via string constants)
659 /// then you should probably just stick to using the regular dictionary.
660 /// </remarks>
661 template< class T >
662 class UnicodeDictionary : public HashMap<std::wstring, T>
663 {
664 public:
665 virtual ~UnicodeDictionary() {}
666
667 UnicodeDictionary( int initialCapacity=33, const std::wstring& emptyKey = L"@@-EMPTY-@@", const std::wstring& deletedKey = L"@@-DELETED-@@" )
668 : HashMap<std::wstring, T>( emptyKey, deletedKey, initialCapacity)
669 {
670 }
671 };
672
673 }
674
675 template< class T, class HashFunctor=HashTools::CommonHashClass >
676 class pxDictionary : public HashTools::HashMap<wxString, T, HashFunctor>
677 {
678 public:
679 virtual ~pxDictionary() {}
680
681 pxDictionary( int initialCapacity=33, const wxString& emptyKey = L"@@-EMPTY-@@", const wxString& deletedKey = L"@@-DELETED-@@" )
682 : HashTools::HashMap<wxString, T, HashFunctor>( emptyKey, deletedKey, initialCapacity)
683 {
684 }
685 };

  ViewVC Help
Powered by ViewVC 1.1.22