1 /////////////////////////////////////////////////////////////////////////////
3 // Purpose: wxHashTable class
4 // Author: Julian Smart
5 // Modified by: VZ at 25.02.00: type safe hashes with WX_DECLARE_HASH()
9 // Licence: wxWindows licence
10 /////////////////////////////////////////////////////////////////////////////
15 #if defined(__GNUG__) && !defined(NO_GCC_PRAGMA)
16 #pragma interface "hash.h"
24 #if WXWIN_COMPATIBILITY_2_4
25 #include "wx/dynarray.h"
28 class WXDLLIMPEXP_BASE wxObject
;
30 // the default size of the hash
31 #define wxHASH_SIZE_DEFAULT (1000)
34 * A hash table is an array of user-definable size with lists
35 * of data items hanging off the array positions. Usually there'll
36 * be a hit, so no search is required; otherwise we'll have to run down
37 * the list to find the desired item.
40 // ----------------------------------------------------------------------------
41 // this is the base class for object hashes: hash tables which contain
42 // pointers to objects
43 // ----------------------------------------------------------------------------
47 class WXDLLIMPEXP_BASE wxHashTableBase
: public wxObject
52 void Create(wxKeyType keyType
= wxKEY_INTEGER
,
53 size_t size
= wxHASH_SIZE_DEFAULT
);
56 size_t GetSize() const { return m_hashSize
; }
57 size_t GetCount() const { return m_count
; }
59 void DeleteContents(bool flag
);
62 // find the node for (key, value)
63 wxNodeBase
*GetNode(long key
, long value
) const;
65 // the array of lists in which we store the values for given key hash
66 wxListBase
**m_hashTable
;
68 // the size of m_lists array
71 // the type of indexing we use
74 // the total number of elements in the hash
77 // should we delete our data?
78 bool m_deleteContents
;
81 // no copy ctor/assignment operator (yet)
82 DECLARE_NO_COPY_CLASS(wxHashTableBase
)
87 #include "wx/hashmap.h"
89 #if !defined(wxENUM_KEY_TYPE_DEFINED)
90 #define wxENUM_KEY_TYPE_DEFINED
107 struct WXDLLIMPEXP_BASE wxHashTableHash
109 wxHashTableHash() { }
110 wxHashTableHash( wxKeyType keyType
) : m_keyType( keyType
) { }
114 unsigned long operator ()( const wxHashKeyValue
& k
) const
116 if( m_keyType
== wxKEY_STRING
)
117 return wxStringHash::wxCharStringHash( k
.string
);
119 return (unsigned long)k
.integer
;
123 struct WXDLLIMPEXP_BASE wxHashTableEqual
125 wxHashTableEqual() { }
126 wxHashTableEqual( wxKeyType keyType
) : m_keyType( keyType
) { }
130 bool operator ()( const wxHashKeyValue
& k1
, const wxHashKeyValue
& k2
) const
132 if( m_keyType
== wxKEY_STRING
)
133 return wxStrcmp( k1
.string
, k2
.string
) == 0;
135 return k1
.integer
== k2
.integer
;
139 WX_DECLARE_EXPORTED_HASH_MAP( wxHashKeyValue
,
143 wxHashTableBaseBase
);
145 class WXDLLIMPEXP_BASE wxHashTableBase
148 wxHashTableBase( wxKeyType keyType
= wxKEY_INTEGER
,
149 size_t size
= wxHASH_SIZE_DEFAULT
)
150 : m_map( size
, wxHashTableHash( keyType
),
151 wxHashTableEqual( keyType
) ),
152 m_keyType( keyType
) { }
154 ~wxHashTableBase() { Clear(); }
156 size_t GetCount() const { return m_map
.size(); }
160 if( m_keyType
== wxKEY_STRING
)
162 for( wxHashTableBaseBase::iterator it
= m_map
.begin(),
166 wxChar
* tmp
= it
->first
.string
;
168 delete[] tmp
; // used in operator++
174 void DoPut( long key
, void* data
)
176 wxASSERT( m_keyType
== wxKEY_INTEGER
);
178 wxHashKeyValue k
; k
.integer
= key
;
182 void DoPut( const wxChar
* key
, void* data
)
184 wxASSERT( m_keyType
== wxKEY_STRING
);
187 k
.string
= (wxChar
*)key
;
188 wxHashTableBaseBase::iterator it
= m_map
.find(k
);
190 if( it
== m_map
.end() )
192 k
.string
= new wxChar
[wxStrlen(key
) + 1];
193 wxStrcpy(k
.string
, key
);
200 void* DoGet( long key
) const
202 wxASSERT( m_keyType
== wxKEY_INTEGER
);
204 wxHashKeyValue k
; k
.integer
= key
;
205 wxHashTableBaseBase::const_iterator it
= m_map
.find( k
);
207 return it
!= m_map
.end() ? it
->second
: NULL
;
210 void* DoGet( const wxChar
* key
) const
212 wxASSERT( m_keyType
== wxKEY_STRING
);
214 wxHashKeyValue k
; k
.string
= (wxChar
*)key
;
215 wxHashTableBaseBase::const_iterator it
= m_map
.find( k
);
217 return it
!= m_map
.end() ? it
->second
: NULL
;
220 void* DoDelete( long key
)
222 wxASSERT( m_keyType
== wxKEY_INTEGER
);
224 wxHashKeyValue k
; k
.integer
= key
;
225 wxHashTableBaseBase::iterator it
= m_map
.find( k
);
227 if( it
!= m_map
.end() )
229 void* data
= it
->second
;
238 void* DoDelete( const wxChar
* key
)
240 wxASSERT( m_keyType
== wxKEY_STRING
);
242 wxHashKeyValue k
; k
.string
= (wxChar
*)key
;
243 wxHashTableBaseBase::iterator it
= m_map
.find( k
);
245 if( it
!= m_map
.end() )
247 void* data
= it
->second
;
248 wxChar
* k
= it
->first
.string
;
258 wxHashTableBaseBase m_map
;
266 #if WXWIN_COMPATIBILITY_2_4
268 // ----------------------------------------------------------------------------
269 // a hash table which stores longs
270 // ----------------------------------------------------------------------------
272 class WXDLLIMPEXP_BASE wxHashTableLong
: public wxObject
275 wxHashTableLong(size_t size
= wxHASH_SIZE_DEFAULT
)
277 virtual ~wxHashTableLong();
279 void Create(size_t size
= wxHASH_SIZE_DEFAULT
);
282 size_t GetSize() const { return m_hashSize
; }
283 size_t GetCount() const { return m_count
; }
285 void Put(long key
, long value
);
286 long Get(long key
) const;
287 long Delete(long key
);
290 void Init(size_t size
);
293 wxArrayLong
**m_values
,
296 // the size of array above
299 // the total number of elements in the hash
302 // not implemented yet
303 DECLARE_NO_COPY_CLASS(wxHashTableLong
)
306 // ----------------------------------------------------------------------------
307 // wxStringHashTable: a hash table which indexes strings with longs
308 // ----------------------------------------------------------------------------
310 class WXDLLIMPEXP_BASE wxStringHashTable
: public wxObject
313 wxStringHashTable(size_t sizeTable
= wxHASH_SIZE_DEFAULT
);
314 virtual ~wxStringHashTable();
316 // add a string associated with this key to the table
317 void Put(long key
, const wxString
& value
);
319 // get the string from the key: if not found, an empty string is returned
320 // and the wasFound is set to FALSE if not NULL
321 wxString
Get(long key
, bool *wasFound
= NULL
) const;
323 // remove the item, returning TRUE if the item was found and deleted
324 bool Delete(long key
) const;
330 wxArrayLong
**m_keys
;
331 wxArrayString
**m_values
;
333 // the size of array above
336 DECLARE_NO_COPY_CLASS(wxStringHashTable
)
339 #endif // WXWIN_COMPATIBILITY_2_4
343 // ----------------------------------------------------------------------------
344 // for compatibility only
345 // ----------------------------------------------------------------------------
349 class WXDLLIMPEXP_BASE wxHashTable
: protected wxHashTableBase
351 typedef wxHashTableBaseBase hash
;
355 struct compatibility_iterator
357 hash::iterator m_iter
;
360 operator bool() const { return m_iter
!= m_hash
->end(); }
361 bool operator !() const { return m_iter
== m_hash
->end(); }
362 compatibility_iterator( hash
* li
, hash::iterator it
)
363 : m_iter( it
), m_hash( li
) {}
364 compatibility_iterator() { }
366 dummy
* operator->() { return (dummy
*)this; }
368 typedef compatibility_iterator citer
;
372 typedef hash::iterator it
;
373 typedef compatibility_iterator citer
;
375 wxObject
* GetData() const
377 citer
* i
= (citer
*)this;
378 return (wxObject
*)i
->m_iter
->second
;
380 citer
GetNext() const
382 citer
* i
= (citer
*)this;
384 return citer( i
->m_hash
, ++lit
);
386 void SetData( wxObject
* e
)
388 citer
* i
= (citer
*)this;
389 i
->m_iter
->second
= e
;
395 wxHashTable( wxKeyType keyType
= wxKEY_INTEGER
,
396 size_t size
= wxHASH_SIZE_DEFAULT
)
397 : wxHashTableBase( keyType
, size
) { }
399 void Destroy() { Clear(); }
401 // key and value are the same
402 void Put(long value
, wxObject
*object
) { DoPut( value
, object
); }
403 void Put(const wxChar
*value
, wxObject
*object
) { DoPut( value
, object
); }
405 // key and value are the same
406 wxObject
*Get(long value
) const { return (wxObject
*)DoGet( value
); }
407 wxObject
*Get(const wxChar
*value
) const { return (wxObject
*)DoGet( value
); }
409 // Deletes entry and returns data if found
410 wxObject
*Delete(long key
) { return (wxObject
*)DoGet( key
); }
411 wxObject
*Delete(const wxChar
*key
) { return (wxObject
*)DoGet( key
); }
414 // Construct your own integer key from a string, e.g. in case
415 // you need to combine it with something
416 long MakeKey(const wxChar
*string
) const;
418 // Way of iterating through whole hash table (e.g. to delete everything)
419 // Not necessary, of course, if you're only storing pointers to
420 // objects maintained separately
421 void BeginFind() { m_iter
= citer( &this->m_map
, this->m_map
.begin() ); }
422 compatibility_iterator
Next()
424 compatibility_iterator it
= m_iter
;
426 m_iter
= m_iter
->GetNext();
430 void Clear() { wxHashTableBase::Clear(); }
432 size_t GetCount() const { return wxHashTableBase::GetCount(); }
434 compatibility_iterator m_iter
;
437 #else // if !wxUSE_STL
439 class WXDLLIMPEXP_BASE wxHashTable
: public wxObject
443 int current_position
;
444 wxNode
*current_node
;
446 unsigned int key_type
;
449 wxHashTable(int the_key_type
= wxKEY_INTEGER
,
450 int size
= wxHASH_SIZE_DEFAULT
);
453 // copy ctor and assignment operator
454 wxHashTable(const wxHashTable
& table
) : wxObject()
456 wxHashTable
& operator=(const wxHashTable
& table
)
457 { Clear(); DoCopy(table
); return *this; }
459 void DoCopy(const wxHashTable
& table
);
463 bool Create(int the_key_type
= wxKEY_INTEGER
,
464 int size
= wxHASH_SIZE_DEFAULT
);
466 // Note that there are 2 forms of Put, Get.
467 // With a key and a value, the *value* will be checked
468 // when a collision is detected. Otherwise, if there are
469 // 2 items with a different value but the same key,
470 // we'll retrieve the WRONG ONE. So where possible,
471 // supply the required value along with the key.
472 // In fact, the value-only versions make a key, and still store
473 // the value. The use of an explicit key might be required
474 // e.g. when combining several values into one key.
475 // When doing that, it's highly likely we'll get a collision,
476 // e.g. 1 + 2 = 3, 2 + 1 = 3.
478 // key and value are NOT necessarily the same
479 void Put(long key
, long value
, wxObject
*object
);
480 void Put(long key
, const wxChar
*value
, wxObject
*object
);
482 // key and value are the same
483 void Put(long value
, wxObject
*object
);
484 void Put(const wxChar
*value
, wxObject
*object
);
486 // key and value not the same
487 wxObject
*Get(long key
, long value
) const;
488 wxObject
*Get(long key
, const wxChar
*value
) const;
490 // key and value are the same
491 wxObject
*Get(long value
) const;
492 wxObject
*Get(const wxChar
*value
) const;
494 // Deletes entry and returns data if found
495 wxObject
*Delete(long key
);
496 wxObject
*Delete(const wxChar
*key
);
498 wxObject
*Delete(long key
, int value
);
499 wxObject
*Delete(long key
, const wxChar
*value
);
501 // Construct your own integer key from a string, e.g. in case
502 // you need to combine it with something
503 long MakeKey(const wxChar
*string
) const;
505 // Way of iterating through whole hash table (e.g. to delete everything)
506 // Not necessary, of course, if you're only storing pointers to
507 // objects maintained separately
512 void DeleteContents(bool flag
);
515 // Returns number of nodes
516 size_t GetCount() const { return m_count
; }
518 typedef wxNode
* compatibility_iterator
;
520 size_t m_count
; // number of elements in the hashtable
521 bool m_deleteContents
;
523 DECLARE_DYNAMIC_CLASS(wxHashTable
)
530 // defines a new type safe hash table which stores the elements of type eltype
531 // in lists of class listclass
532 #define _WX_DECLARE_HASH(eltype, dummy, hashclass, classexp) \
533 classexp hashclass : public wxHashTableBase \
536 hashclass(wxKeyType keyType = wxKEY_INTEGER, \
537 size_t size = wxHASH_SIZE_DEFAULT) \
538 : wxHashTableBase(keyType, size) { } \
540 ~hashclass() { Destroy(); } \
542 void Destroy() { m_map.clear(); } \
543 void Put(long key, eltype *data) { DoPut(key, (void*)data); } \
544 eltype *Get(long key) const { return (eltype*)DoGet(key); } \
545 eltype *Delete(long key) { return (eltype*)DoDelete(key); } \
548 #else // if !wxUSE_STL
550 #define _WX_DECLARE_HASH(eltype, listclass, hashclass, classexp) \
551 classexp hashclass : public wxHashTableBase \
554 hashclass(wxKeyType keyType = wxKEY_INTEGER, \
555 size_t size = wxHASH_SIZE_DEFAULT) \
556 { Create(keyType, size); } \
558 ~hashclass() { Destroy(); } \
560 void Put(long key, long val, eltype *data) { DoPut(key, val, data); } \
561 void Put(long key, eltype *data) { DoPut(key, key, data); } \
563 eltype *Get(long key, long value) const \
565 wxNodeBase *node = GetNode(key, value); \
566 return node ? ((listclass::Node *)node)->GetData() : (eltype *)0; \
568 eltype *Get(long key) const { return Get(key, key); } \
570 eltype *Delete(long key, long value) \
574 wxNodeBase *node = GetNode(key, value); \
577 data = ((listclass::Node *)node)->GetData(); \
584 data = (eltype *)0; \
589 eltype *Delete(long key) { return Delete(key, key); } \
592 void DoPut(long key, long value, eltype *data) \
594 size_t slot = (size_t)abs((int)(key % (long)m_hashSize)); \
596 if ( !m_hashTable[slot] ) \
598 m_hashTable[slot] = new listclass(m_keyType); \
599 if ( m_deleteContents ) \
600 m_hashTable[slot]->DeleteContents(TRUE); \
603 ((listclass *)m_hashTable[slot])->Append(value, data); \
607 DECLARE_NO_COPY_CLASS(hashclass) \
612 // this macro is to be used in the user code
613 #define WX_DECLARE_HASH(el, list, hash) \
614 _WX_DECLARE_HASH(el, list, hash, class)
616 // and this one does exactly the same thing but should be used inside the
618 #define WX_DECLARE_EXPORTED_HASH(el, list, hash) \
619 _WX_DECLARE_HASH(el, list, hash, class WXDLLEXPORT)
621 #define WX_DECLARE_USER_EXPORTED_HASH(el, list, hash, usergoo) \
622 _WX_DECLARE_HASH(el, list, hash, class usergoo)
624 // delete all hash elements
626 // NB: the class declaration of the hash elements must be visible from the
627 // place where you use this macro, otherwise the proper destructor may not
628 // be called (a decent compiler should give a warning about it, but don't
630 #define WX_CLEAR_HASH_TABLE(hash) \
632 (hash).BeginFind(); \
633 wxHashTable::compatibility_iterator it = (hash).Next(); \
636 delete it->GetData(); \
637 it = (hash).Next(); \