]> git.saurik.com Git - wxWidgets.git/blob - include/wx/hash.h
added WXK_COMMAND
[wxWidgets.git] / include / wx / hash.h
1 /////////////////////////////////////////////////////////////////////////////
2 // Name: wx/hash.h
3 // Purpose: wxHashTable class
4 // Author: Julian Smart
5 // Modified by: VZ at 25.02.00: type safe hashes with WX_DECLARE_HASH()
6 // Created: 01/02/97
7 // RCS-ID: $Id$
8 // Copyright: (c)
9 // Licence: wxWindows licence
10 /////////////////////////////////////////////////////////////////////////////
11
12 #ifndef _WX_HASH_H__
13 #define _WX_HASH_H__
14
15 #if defined(__GNUG__) && !defined(NO_GCC_PRAGMA)
16 #pragma interface "hash.h"
17 #endif
18
19 #include "wx/defs.h"
20
21 #if !wxUSE_STL
22 #include "wx/list.h"
23 #endif
24 #if WXWIN_COMPATIBILITY_2_4
25 #include "wx/dynarray.h"
26 #endif
27
28 class WXDLLIMPEXP_BASE wxObject;
29
30 // the default size of the hash
31 #define wxHASH_SIZE_DEFAULT (1000)
32
33 /*
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.
38 */
39
40 // ----------------------------------------------------------------------------
41 // this is the base class for object hashes: hash tables which contain
42 // pointers to objects
43 // ----------------------------------------------------------------------------
44
45 #if !wxUSE_STL
46
47 class WXDLLIMPEXP_BASE wxHashTableBase : public wxObject
48 {
49 public:
50 wxHashTableBase();
51
52 void Create(wxKeyType keyType = wxKEY_INTEGER,
53 size_t size = wxHASH_SIZE_DEFAULT);
54 void Destroy();
55
56 size_t GetSize() const { return m_hashSize; }
57 size_t GetCount() const { return m_count; }
58
59 void DeleteContents(bool flag);
60
61 protected:
62 // find the node for (key, value)
63 wxNodeBase *GetNode(long key, long value) const;
64
65 // the array of lists in which we store the values for given key hash
66 wxListBase **m_hashTable;
67
68 // the size of m_lists array
69 size_t m_hashSize;
70
71 // the type of indexing we use
72 wxKeyType m_keyType;
73
74 // the total number of elements in the hash
75 size_t m_count;
76
77 // should we delete our data?
78 bool m_deleteContents;
79
80 private:
81 // no copy ctor/assignment operator (yet)
82 DECLARE_NO_COPY_CLASS(wxHashTableBase)
83 };
84
85 #else
86
87 #include "wx/hashmap.h"
88
89 #if !defined(wxENUM_KEY_TYPE_DEFINED)
90 #define wxENUM_KEY_TYPE_DEFINED
91
92 enum wxKeyType
93 {
94 wxKEY_NONE,
95 wxKEY_INTEGER,
96 wxKEY_STRING
97 };
98
99 #endif
100
101 union wxHashKeyValue
102 {
103 long integer;
104 wxChar *string;
105 };
106
107 struct WXDLLIMPEXP_BASE wxHashTableHash
108 {
109 wxHashTableHash() { }
110 wxHashTableHash( wxKeyType keyType ) : m_keyType( keyType ) { }
111
112 wxKeyType m_keyType;
113
114 unsigned long operator ()( const wxHashKeyValue& k ) const
115 {
116 if( m_keyType == wxKEY_STRING )
117 return wxStringHash::wxCharStringHash( k.string );
118 else
119 return (unsigned long)k.integer;
120 }
121 };
122
123 struct WXDLLIMPEXP_BASE wxHashTableEqual
124 {
125 wxHashTableEqual() { }
126 wxHashTableEqual( wxKeyType keyType ) : m_keyType( keyType ) { }
127
128 wxKeyType m_keyType;
129
130 bool operator ()( const wxHashKeyValue& k1, const wxHashKeyValue& k2 ) const
131 {
132 if( m_keyType == wxKEY_STRING )
133 return wxStrcmp( k1.string, k2.string ) == 0;
134 else
135 return k1.integer == k2.integer;
136 }
137 };
138
139 WX_DECLARE_EXPORTED_HASH_MAP( wxHashKeyValue,
140 void*,
141 wxHashTableHash,
142 wxHashTableEqual,
143 wxHashTableBaseBase );
144
145 class WXDLLIMPEXP_BASE wxHashTableBase
146 {
147 public:
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 ) { }
153
154 ~wxHashTableBase() { Clear(); }
155
156 size_t GetCount() const { return m_map.size(); }
157
158 void Clear()
159 {
160 if( m_keyType == wxKEY_STRING )
161 {
162 for( wxHashTableBaseBase::iterator it = m_map.begin(),
163 en = m_map.end();
164 it != en; )
165 {
166 wxChar* tmp = it->first.string;
167 ++it;
168 delete[] tmp; // used in operator++
169 }
170 }
171 m_map.clear();
172 }
173 protected:
174 void DoPut( long key, void* data )
175 {
176 wxASSERT( m_keyType == wxKEY_INTEGER );
177
178 wxHashKeyValue k; k.integer = key;
179 m_map[k] = data;
180 }
181
182 void DoPut( const wxChar* key, void* data )
183 {
184 wxASSERT( m_keyType == wxKEY_STRING );
185
186 wxHashKeyValue k;
187 k.string = (wxChar*)key;
188 wxHashTableBaseBase::iterator it = m_map.find(k);
189
190 if( it == m_map.end() )
191 {
192 k.string = new wxChar[wxStrlen(key) + 1];
193 wxStrcpy(k.string, key);
194 m_map[k] = data;
195 }
196 else
197 it->second = data;
198 }
199
200 void* DoGet( long key ) const
201 {
202 wxASSERT( m_keyType == wxKEY_INTEGER );
203
204 wxHashKeyValue k; k.integer = key;
205 wxHashTableBaseBase::const_iterator it = m_map.find( k );
206
207 return it != m_map.end() ? it->second : NULL;
208 }
209
210 void* DoGet( const wxChar* key ) const
211 {
212 wxASSERT( m_keyType == wxKEY_STRING );
213
214 wxHashKeyValue k; k.string = (wxChar*)key;
215 wxHashTableBaseBase::const_iterator it = m_map.find( k );
216
217 return it != m_map.end() ? it->second : NULL;
218 }
219
220 void* DoDelete( long key )
221 {
222 wxASSERT( m_keyType == wxKEY_INTEGER );
223
224 wxHashKeyValue k; k.integer = key;
225 wxHashTableBaseBase::iterator it = m_map.find( k );
226
227 if( it != m_map.end() )
228 {
229 void* data = it->second;
230
231 m_map.erase( it );
232 return data;
233 }
234
235 return NULL;
236 }
237
238 void* DoDelete( const wxChar* key )
239 {
240 wxASSERT( m_keyType == wxKEY_STRING );
241
242 wxHashKeyValue k; k.string = (wxChar*)key;
243 wxHashTableBaseBase::iterator it = m_map.find( k );
244
245 if( it != m_map.end() )
246 {
247 void* data = it->second;
248 wxChar* k = it->first.string;
249
250 m_map.erase( it );
251 delete[] k;
252 return data;
253 }
254
255 return NULL;
256 }
257
258 wxHashTableBaseBase m_map;
259 wxKeyType m_keyType;
260 };
261
262 #endif // !wxUSE_STL
263
264 #if !wxUSE_STL
265
266 #if WXWIN_COMPATIBILITY_2_4
267
268 // ----------------------------------------------------------------------------
269 // a hash table which stores longs
270 // ----------------------------------------------------------------------------
271
272 class WXDLLIMPEXP_BASE wxHashTableLong : public wxObject
273 {
274 public:
275 wxHashTableLong(size_t size = wxHASH_SIZE_DEFAULT)
276 { Init(size); }
277 virtual ~wxHashTableLong();
278
279 void Create(size_t size = wxHASH_SIZE_DEFAULT);
280 void Destroy();
281
282 size_t GetSize() const { return m_hashSize; }
283 size_t GetCount() const { return m_count; }
284
285 void Put(long key, long value);
286 long Get(long key) const;
287 long Delete(long key);
288
289 protected:
290 void Init(size_t size);
291
292 private:
293 wxArrayLong **m_values,
294 **m_keys;
295
296 // the size of array above
297 size_t m_hashSize;
298
299 // the total number of elements in the hash
300 size_t m_count;
301
302 // not implemented yet
303 DECLARE_NO_COPY_CLASS(wxHashTableLong)
304 };
305
306 // ----------------------------------------------------------------------------
307 // wxStringHashTable: a hash table which indexes strings with longs
308 // ----------------------------------------------------------------------------
309
310 class WXDLLIMPEXP_BASE wxStringHashTable : public wxObject
311 {
312 public:
313 wxStringHashTable(size_t sizeTable = wxHASH_SIZE_DEFAULT);
314 virtual ~wxStringHashTable();
315
316 // add a string associated with this key to the table
317 void Put(long key, const wxString& value);
318
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;
322
323 // remove the item, returning TRUE if the item was found and deleted
324 bool Delete(long key) const;
325
326 // clean up
327 void Destroy();
328
329 private:
330 wxArrayLong **m_keys;
331 wxArrayString **m_values;
332
333 // the size of array above
334 size_t m_hashSize;
335
336 DECLARE_NO_COPY_CLASS(wxStringHashTable)
337 };
338
339 #endif // WXWIN_COMPATIBILITY_2_4
340
341 #endif // !wxUSE_STL
342
343 // ----------------------------------------------------------------------------
344 // for compatibility only
345 // ----------------------------------------------------------------------------
346
347 #if wxUSE_STL
348
349 class WXDLLIMPEXP_BASE wxHashTable : protected wxHashTableBase
350 {
351 typedef wxHashTableBaseBase hash;
352 public:
353 class dummy;
354
355 struct compatibility_iterator
356 {
357 hash::iterator m_iter;
358 hash* m_hash;
359
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() { }
365
366 dummy* operator->() { return (dummy*)this; }
367 };
368 typedef compatibility_iterator citer;
369
370 class dummy
371 {
372 typedef hash::iterator it;
373 typedef compatibility_iterator citer;
374 public:
375 wxObject* GetData() const
376 {
377 citer* i = (citer*)this;
378 return (wxObject*)i->m_iter->second;
379 }
380 citer GetNext() const
381 {
382 citer* i = (citer*)this;
383 it lit = i->m_iter;
384 return citer( i->m_hash, ++lit );
385 }
386 void SetData( wxObject* e )
387 {
388 citer* i = (citer*)this;
389 i->m_iter->second = e;
390 }
391 private:
392 dummy();
393 };
394 public:
395 wxHashTable( wxKeyType keyType = wxKEY_INTEGER,
396 size_t size = wxHASH_SIZE_DEFAULT )
397 : wxHashTableBase( keyType, size ) { }
398
399 void Destroy() { Clear(); }
400
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 ); }
404
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 ); }
408
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 ); }
412
413 #if 0
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;
417 #endif
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()
423 {
424 compatibility_iterator it = m_iter;
425 if( m_iter )
426 m_iter = m_iter->GetNext();
427 return it;
428 }
429
430 void Clear() { wxHashTableBase::Clear(); }
431
432 size_t GetCount() const { return wxHashTableBase::GetCount(); }
433 private:
434 compatibility_iterator m_iter;
435 };
436
437 #else // if !wxUSE_STL
438
439 class WXDLLIMPEXP_BASE wxHashTable : public wxObject
440 {
441 public:
442 int n;
443 int current_position;
444 wxNode *current_node;
445
446 unsigned int key_type;
447 wxList **hash_table;
448
449 wxHashTable(int the_key_type = wxKEY_INTEGER,
450 int size = wxHASH_SIZE_DEFAULT);
451 ~wxHashTable();
452
453 // copy ctor and assignment operator
454 wxHashTable(const wxHashTable& table) : wxObject()
455 { DoCopy(table); }
456 wxHashTable& operator=(const wxHashTable& table)
457 { Clear(); DoCopy(table); return *this; }
458
459 void DoCopy(const wxHashTable& table);
460
461 void Destroy();
462
463 bool Create(int the_key_type = wxKEY_INTEGER,
464 int size = wxHASH_SIZE_DEFAULT);
465
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.
477
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);
481
482 // key and value are the same
483 void Put(long value, wxObject *object);
484 void Put(const wxChar *value, wxObject *object);
485
486 // key and value not the same
487 wxObject *Get(long key, long value) const;
488 wxObject *Get(long key, const wxChar *value) const;
489
490 // key and value are the same
491 wxObject *Get(long value) const;
492 wxObject *Get(const wxChar *value) const;
493
494 // Deletes entry and returns data if found
495 wxObject *Delete(long key);
496 wxObject *Delete(const wxChar *key);
497
498 wxObject *Delete(long key, int value);
499 wxObject *Delete(long key, const wxChar *value);
500
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;
504
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
508
509 void BeginFind();
510 wxNode *Next();
511
512 void DeleteContents(bool flag);
513 void Clear();
514
515 // Returns number of nodes
516 size_t GetCount() const { return m_count; }
517
518 typedef wxNode* compatibility_iterator;
519 private:
520 size_t m_count; // number of elements in the hashtable
521 bool m_deleteContents;
522
523 DECLARE_DYNAMIC_CLASS(wxHashTable)
524 };
525
526 #endif
527
528 #if wxUSE_STL
529
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 \
534 { \
535 public: \
536 hashclass(wxKeyType keyType = wxKEY_INTEGER, \
537 size_t size = wxHASH_SIZE_DEFAULT) \
538 : wxHashTableBase(keyType, size) { } \
539 \
540 ~hashclass() { Destroy(); } \
541 \
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); } \
546 }
547
548 #else // if !wxUSE_STL
549
550 #define _WX_DECLARE_HASH(eltype, listclass, hashclass, classexp) \
551 classexp hashclass : public wxHashTableBase \
552 { \
553 public: \
554 hashclass(wxKeyType keyType = wxKEY_INTEGER, \
555 size_t size = wxHASH_SIZE_DEFAULT) \
556 { Create(keyType, size); } \
557 \
558 ~hashclass() { Destroy(); } \
559 \
560 void Put(long key, long val, eltype *data) { DoPut(key, val, data); } \
561 void Put(long key, eltype *data) { DoPut(key, key, data); } \
562 \
563 eltype *Get(long key, long value) const \
564 { \
565 wxNodeBase *node = GetNode(key, value); \
566 return node ? ((listclass::Node *)node)->GetData() : (eltype *)0; \
567 } \
568 eltype *Get(long key) const { return Get(key, key); } \
569 \
570 eltype *Delete(long key, long value) \
571 { \
572 eltype *data; \
573 \
574 wxNodeBase *node = GetNode(key, value); \
575 if ( node ) \
576 { \
577 data = ((listclass::Node *)node)->GetData(); \
578 \
579 delete node; \
580 m_count--; \
581 } \
582 else \
583 { \
584 data = (eltype *)0; \
585 } \
586 \
587 return data; \
588 } \
589 eltype *Delete(long key) { return Delete(key, key); } \
590 \
591 protected: \
592 void DoPut(long key, long value, eltype *data) \
593 { \
594 size_t slot = (size_t)abs((int)(key % (long)m_hashSize)); \
595 \
596 if ( !m_hashTable[slot] ) \
597 { \
598 m_hashTable[slot] = new listclass(m_keyType); \
599 if ( m_deleteContents ) \
600 m_hashTable[slot]->DeleteContents(TRUE); \
601 } \
602 \
603 ((listclass *)m_hashTable[slot])->Append(value, data); \
604 m_count++; \
605 } \
606 \
607 DECLARE_NO_COPY_CLASS(hashclass) \
608 }
609
610 #endif
611
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)
615
616 // and this one does exactly the same thing but should be used inside the
617 // library
618 #define WX_DECLARE_EXPORTED_HASH(el, list, hash) \
619 _WX_DECLARE_HASH(el, list, hash, class WXDLLEXPORT)
620
621 #define WX_DECLARE_USER_EXPORTED_HASH(el, list, hash, usergoo) \
622 _WX_DECLARE_HASH(el, list, hash, class usergoo)
623
624 // delete all hash elements
625 //
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
629 // count on it)!
630 #define WX_CLEAR_HASH_TABLE(hash) \
631 { \
632 (hash).BeginFind(); \
633 wxHashTable::compatibility_iterator it = (hash).Next(); \
634 while( it ) \
635 { \
636 delete it->GetData(); \
637 it = (hash).Next(); \
638 } \
639 (hash).Clear(); \
640 }
641
642 #endif
643 // _WX_HASH_H__