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: hash.h 53135 2008-04-12 02:31:04Z VZ $ 8// Copyright: (c) Julian Smart 9// Licence: wxWindows licence 10///////////////////////////////////////////////////////////////////////////// 11 12#ifndef _WX_HASH_H__ 13#define _WX_HASH_H__ 14 15#include "wx/defs.h" 16 17#if !wxUSE_STL && WXWIN_COMPATIBILITY_2_4 18 #define wxUSE_OLD_HASH_TABLE 1 19#else 20 #define wxUSE_OLD_HASH_TABLE 0 21#endif 22 23#if !wxUSE_STL 24 #include "wx/object.h" 25#else 26 class WXDLLIMPEXP_BASE wxObject; 27#endif 28#if wxUSE_OLD_HASH_TABLE 29 #include "wx/list.h" 30#endif 31#if WXWIN_COMPATIBILITY_2_4 32 #include "wx/dynarray.h" 33#endif 34 35// the default size of the hash 36#define wxHASH_SIZE_DEFAULT (1000) 37 38/* 39 * A hash table is an array of user-definable size with lists 40 * of data items hanging off the array positions. Usually there'll 41 * be a hit, so no search is required; otherwise we'll have to run down 42 * the list to find the desired item. 43*/ 44 45// ---------------------------------------------------------------------------- 46// this is the base class for object hashes: hash tables which contain 47// pointers to objects 48// ---------------------------------------------------------------------------- 49 50#if wxUSE_OLD_HASH_TABLE 51 52class WXDLLIMPEXP_BASE wxHashTableBase : public wxObject 53{ 54public: 55 wxHashTableBase(); 56 57 void Create(wxKeyType keyType = wxKEY_INTEGER, 58 size_t size = wxHASH_SIZE_DEFAULT); 59 void Destroy(); 60 61 size_t GetSize() const { return m_hashSize; } 62 size_t GetCount() const { return m_count; } 63 64 void DeleteContents(bool flag); 65 66protected: 67 // find the node for (key, value) 68 wxNodeBase *GetNode(long key, long value) const; 69 70 // the array of lists in which we store the values for given key hash 71 wxListBase **m_hashTable; 72 73 // the size of m_lists array 74 size_t m_hashSize; 75 76 // the type of indexing we use 77 wxKeyType m_keyType; 78 79 // the total number of elements in the hash 80 size_t m_count; 81 82 // should we delete our data? 83 bool m_deleteContents; 84 85private: 86 // no copy ctor/assignment operator (yet) 87 DECLARE_NO_COPY_CLASS(wxHashTableBase) 88}; 89 90#else // if !wxUSE_OLD_HASH_TABLE 91 92#if !defined(wxENUM_KEY_TYPE_DEFINED) 93#define wxENUM_KEY_TYPE_DEFINED 94 95enum wxKeyType 96{ 97 wxKEY_NONE, 98 wxKEY_INTEGER, 99 wxKEY_STRING 100}; 101 102#endif 103 104union wxHashKeyValue 105{ 106 long integer; 107 wxChar *string; 108}; 109 110// for some compilers (AIX xlC), defining it as friend inside the class is not 111// enough, so provide a real forward declaration 112class WXDLLIMPEXP_FWD_BASE wxHashTableBase; 113 114class WXDLLIMPEXP_BASE wxHashTableBase_Node 115{ 116 friend class WXDLLIMPEXP_FWD_BASE wxHashTableBase; 117 typedef class WXDLLIMPEXP_FWD_BASE wxHashTableBase_Node _Node; 118public: 119 wxHashTableBase_Node( long key, void* value, 120 wxHashTableBase* table ); 121 wxHashTableBase_Node( const wxChar* key, void* value, 122 wxHashTableBase* table ); 123 ~wxHashTableBase_Node(); 124 125 long GetKeyInteger() const { return m_key.integer; } 126 const wxChar* GetKeyString() const { return m_key.string; } 127 128 void* GetData() const { return m_value; } 129 void SetData( void* data ) { m_value = data; } 130 131protected: 132 _Node* GetNext() const { return m_next; } 133 134protected: 135 // next node in the chain 136 wxHashTableBase_Node* m_next; 137 138 // key 139 wxHashKeyValue m_key; 140 141 // value 142 void* m_value; 143 144 // pointer to the hash containing the node, used to remove the 145 // node from the hash when the user deletes the node iterating 146 // through it 147 // TODO: move it to wxHashTable_Node (only wxHashTable supports 148 // iteration) 149 wxHashTableBase* m_hashPtr; 150}; 151 152class WXDLLIMPEXP_BASE wxHashTableBase 153#if !wxUSE_STL 154 : public wxObject 155#endif 156{ 157 friend class WXDLLIMPEXP_FWD_BASE wxHashTableBase_Node; 158public: 159 typedef wxHashTableBase_Node Node; 160 161 wxHashTableBase(); 162 virtual ~wxHashTableBase() { } 163 164 void Create( wxKeyType keyType = wxKEY_INTEGER, 165 size_t size = wxHASH_SIZE_DEFAULT ); 166 void Clear(); 167 void Destroy(); 168 169 size_t GetSize() const { return m_size; } 170 size_t GetCount() const { return m_count; } 171 172 void DeleteContents( bool flag ) { m_deleteContents = flag; } 173 174 static long MakeKey(const wxChar *string); 175 176protected: 177 void DoPut( long key, long hash, void* data ); 178 void DoPut( const wxChar* key, long hash, void* data ); 179 void* DoGet( long key, long hash ) const; 180 void* DoGet( const wxChar* key, long hash ) const; 181 void* DoDelete( long key, long hash ); 182 void* DoDelete( const wxChar* key, long hash ); 183 184private: 185 // Remove the node from the hash, *only called from 186 // ~wxHashTable*_Node destructor 187 void DoRemoveNode( wxHashTableBase_Node* node ); 188 189 // destroys data contained in the node if appropriate: 190 // deletes the key if it is a string and destrys 191 // the value if m_deleteContents is true 192 void DoDestroyNode( wxHashTableBase_Node* node ); 193 194 // inserts a node in the table (at the end of the chain) 195 void DoInsertNode( size_t bucket, wxHashTableBase_Node* node ); 196 197 // removes a node from the table (fiven a pointer to the previous 198 // but does not delete it (only deletes its contents) 199 void DoUnlinkNode( size_t bucket, wxHashTableBase_Node* node, 200 wxHashTableBase_Node* prev ); 201 202 // unconditionally deletes node value (invoking the 203 // correct destructor) 204 virtual void DoDeleteContents( wxHashTableBase_Node* node ) = 0; 205 206protected: 207 // number of buckets 208 size_t m_size; 209 210 // number of nodes (key/value pairs) 211 size_t m_count; 212 213 // table 214 Node** m_table; 215 216 // key typ (INTEGER/STRING) 217 wxKeyType m_keyType; 218 219 // delete contents when hash is cleared 220 bool m_deleteContents; 221 222private: 223 DECLARE_NO_COPY_CLASS(wxHashTableBase) 224}; 225 226#endif // wxUSE_OLD_HASH_TABLE 227 228#if !wxUSE_STL 229 230#if WXWIN_COMPATIBILITY_2_4 231 232// ---------------------------------------------------------------------------- 233// a hash table which stores longs 234// ---------------------------------------------------------------------------- 235 236class WXDLLIMPEXP_BASE wxHashTableLong : public wxObject 237{ 238public: 239 wxHashTableLong(size_t size = wxHASH_SIZE_DEFAULT) 240 { Init(size); } 241 virtual ~wxHashTableLong(); 242 243 void Create(size_t size = wxHASH_SIZE_DEFAULT); 244 void Destroy(); 245 246 size_t GetSize() const { return m_hashSize; } 247 size_t GetCount() const { return m_count; } 248 249 void Put(long key, long value); 250 long Get(long key) const; 251 long Delete(long key); 252 253protected: 254 void Init(size_t size); 255 256private: 257 wxArrayLong **m_values, 258 **m_keys; 259 260 // the size of array above 261 size_t m_hashSize; 262 263 // the total number of elements in the hash 264 size_t m_count; 265 266 // not implemented yet 267 DECLARE_NO_COPY_CLASS(wxHashTableLong) 268}; 269 270// ---------------------------------------------------------------------------- 271// wxStringHashTable: a hash table which indexes strings with longs 272// ---------------------------------------------------------------------------- 273 274class WXDLLIMPEXP_BASE wxStringHashTable : public wxObject 275{ 276public: 277 wxStringHashTable(size_t sizeTable = wxHASH_SIZE_DEFAULT); 278 virtual ~wxStringHashTable(); 279 280 // add a string associated with this key to the table 281 void Put(long key, const wxString& value); 282 283 // get the string from the key: if not found, an empty string is returned 284 // and the wasFound is set to false if not NULL 285 wxString Get(long key, bool *wasFound = NULL) const; 286 287 // remove the item, returning true if the item was found and deleted 288 bool Delete(long key) const; 289 290 // clean up 291 void Destroy(); 292 293private: 294 wxArrayLong **m_keys; 295 wxArrayString **m_values; 296 297 // the size of array above 298 size_t m_hashSize; 299 300 DECLARE_NO_COPY_CLASS(wxStringHashTable) 301}; 302 303#endif // WXWIN_COMPATIBILITY_2_4 304 305#endif // !wxUSE_STL 306 307// ---------------------------------------------------------------------------- 308// for compatibility only 309// ---------------------------------------------------------------------------- 310 311#if !wxUSE_OLD_HASH_TABLE 312 313class WXDLLIMPEXP_BASE wxHashTable_Node : public wxHashTableBase_Node 314{ 315 friend class WXDLLIMPEXP_FWD_BASE wxHashTable; 316public: 317 wxHashTable_Node( long key, void* value, 318 wxHashTableBase* table ) 319 : wxHashTableBase_Node( key, value, table ) { } 320 wxHashTable_Node( const wxChar* key, void* value, 321 wxHashTableBase* table ) 322 : wxHashTableBase_Node( key, value, table ) { } 323 324 wxObject* GetData() const 325 { return (wxObject*)wxHashTableBase_Node::GetData(); } 326 void SetData( wxObject* data ) 327 { wxHashTableBase_Node::SetData( data ); } 328 329 wxHashTable_Node* GetNext() const 330 { return (wxHashTable_Node*)wxHashTableBase_Node::GetNext(); } 331}; 332 333// should inherit protectedly, but it is public for compatibility in 334// order to publicly inherit from wxObject 335class WXDLLIMPEXP_BASE wxHashTable : public wxHashTableBase 336{ 337 typedef wxHashTableBase hash; 338public: 339 typedef wxHashTable_Node Node; 340 typedef wxHashTable_Node* compatibility_iterator; 341public: 342 wxHashTable( wxKeyType keyType = wxKEY_INTEGER, 343 size_t size = wxHASH_SIZE_DEFAULT ) 344 : wxHashTableBase() { Create( keyType, size ); BeginFind(); } 345 wxHashTable( const wxHashTable& table ); 346 347 virtual ~wxHashTable() { Destroy(); } 348 349 const wxHashTable& operator=( const wxHashTable& ); 350 351 // key and value are the same 352 void Put(long value, wxObject *object) 353 { DoPut( value, value, object ); } 354 void Put(long lhash, long value, wxObject *object) 355 { DoPut( value, lhash, object ); } 356 void Put(const wxChar *value, wxObject *object) 357 { DoPut( value, MakeKey( value ), object ); } 358 void Put(long lhash, const wxChar *value, wxObject *object) 359 { DoPut( value, lhash, object ); } 360 361 // key and value are the same 362 wxObject *Get(long value) const 363 { return (wxObject*)DoGet( value, value ); } 364 wxObject *Get(long lhash, long value) const 365 { return (wxObject*)DoGet( value, lhash ); } 366 wxObject *Get(const wxChar *value) const 367 { return (wxObject*)DoGet( value, MakeKey( value ) ); } 368 wxObject *Get(long lhash, const wxChar *value) const 369 { return (wxObject*)DoGet( value, lhash ); } 370 371 // Deletes entry and returns data if found 372 wxObject *Delete(long key) 373 { return (wxObject*)DoDelete( key, key ); } 374 wxObject *Delete(long lhash, long key) 375 { return (wxObject*)DoDelete( key, lhash ); } 376 wxObject *Delete(const wxChar *key) 377 { return (wxObject*)DoDelete( key, MakeKey( key ) ); } 378 wxObject *Delete(long lhash, const wxChar *key) 379 { return (wxObject*)DoDelete( key, lhash ); } 380 381 // Construct your own integer key from a string, e.g. in case 382 // you need to combine it with something 383 long MakeKey(const wxChar *string) const 384 { return wxHashTableBase::MakeKey(string); } 385 386 // Way of iterating through whole hash table (e.g. to delete everything) 387 // Not necessary, of course, if you're only storing pointers to 388 // objects maintained separately 389 void BeginFind() { m_curr = NULL; m_currBucket = 0; } 390 Node* Next(); 391 392 void Clear() { wxHashTableBase::Clear(); } 393 394 size_t GetCount() const { return wxHashTableBase::GetCount(); } 395protected: 396 // copy helper 397 void DoCopy( const wxHashTable& copy ); 398 399 // searches the next node starting from bucket bucketStart and sets 400 // m_curr to it and m_currBucket to its bucket 401 void GetNextNode( size_t bucketStart ); 402private: 403 virtual void DoDeleteContents( wxHashTableBase_Node* node ); 404 405 // current node 406 Node* m_curr; 407 408 // bucket the current node belongs to 409 size_t m_currBucket; 410}; 411 412#else // if wxUSE_OLD_HASH_TABLE 413 414class WXDLLIMPEXP_BASE wxHashTable : public wxObject 415{ 416public: 417 typedef wxNode Node; 418 typedef wxNode* compatibility_iterator; 419 420 int n; 421 int current_position; 422 wxNode *current_node; 423 424 unsigned int key_type; 425 wxList **hash_table; 426 427 wxHashTable(int the_key_type = wxKEY_INTEGER, 428 int size = wxHASH_SIZE_DEFAULT); 429 virtual ~wxHashTable(); 430 431 // copy ctor and assignment operator 432 wxHashTable(const wxHashTable& table) : wxObject() 433 { DoCopy(table); } 434 wxHashTable& operator=(const wxHashTable& table) 435 { Clear(); DoCopy(table); return *this; } 436 437 void DoCopy(const wxHashTable& table); 438 439 void Destroy(); 440 441 bool Create(int the_key_type = wxKEY_INTEGER, 442 int size = wxHASH_SIZE_DEFAULT); 443 444 // Note that there are 2 forms of Put, Get. 445 // With a key and a value, the *value* will be checked 446 // when a collision is detected. Otherwise, if there are 447 // 2 items with a different value but the same key, 448 // we'll retrieve the WRONG ONE. So where possible, 449 // supply the required value along with the key. 450 // In fact, the value-only versions make a key, and still store 451 // the value. The use of an explicit key might be required 452 // e.g. when combining several values into one key. 453 // When doing that, it's highly likely we'll get a collision, 454 // e.g. 1 + 2 = 3, 2 + 1 = 3. 455 456 // key and value are NOT necessarily the same 457 void Put(long key, long value, wxObject *object); 458 void Put(long key, const wxChar *value, wxObject *object); 459 460 // key and value are the same 461 void Put(long value, wxObject *object); 462 void Put(const wxChar *value, wxObject *object); 463 464 // key and value not the same 465 wxObject *Get(long key, long value) const; 466 wxObject *Get(long key, const wxChar *value) const; 467 468 // key and value are the same 469 wxObject *Get(long value) const; 470 wxObject *Get(const wxChar *value) const; 471 472 // Deletes entry and returns data if found 473 wxObject *Delete(long key); 474 wxObject *Delete(const wxChar *key); 475 476 wxObject *Delete(long key, int value); 477 wxObject *Delete(long key, const wxChar *value); 478 479 // Construct your own integer key from a string, e.g. in case 480 // you need to combine it with something 481 long MakeKey(const wxChar *string) const; 482 483 // Way of iterating through whole hash table (e.g. to delete everything) 484 // Not necessary, of course, if you're only storing pointers to 485 // objects maintained separately 486 487 void BeginFind(); 488 Node* Next(); 489 490 void DeleteContents(bool flag); 491 void Clear(); 492 493 // Returns number of nodes 494 size_t GetCount() const { return m_count; } 495 496private: 497 size_t m_count; // number of elements in the hashtable 498 bool m_deleteContents; 499 500 DECLARE_DYNAMIC_CLASS(wxHashTable) 501}; 502 503#endif // wxUSE_OLD_HASH_TABLE 504 505#if !wxUSE_OLD_HASH_TABLE 506 507// defines a new type safe hash table which stores the elements of type eltype 508// in lists of class listclass 509#define _WX_DECLARE_HASH(eltype, dummy, hashclass, classexp) \ 510 classexp hashclass : public wxHashTableBase \ 511 { \ 512 public: \ 513 hashclass(wxKeyType keyType = wxKEY_INTEGER, \ 514 size_t size = wxHASH_SIZE_DEFAULT) \ 515 : wxHashTableBase() { Create(keyType, size); } \ 516 \ 517 virtual ~hashclass() { Destroy(); } \ 518 \ 519 void Put(long key, eltype *data) { DoPut(key, key, (void*)data); } \ 520 void Put(long lhash, long key, eltype *data) \ 521 { DoPut(key, lhash, (void*)data); } \ 522 eltype *Get(long key) const { return (eltype*)DoGet(key, key); } \ 523 eltype *Get(long lhash, long key) const \ 524 { return (eltype*)DoGet(key, lhash); } \ 525 eltype *Delete(long key) { return (eltype*)DoDelete(key, key); } \ 526 eltype *Delete(long lhash, long key) \ 527 { return (eltype*)DoDelete(key, lhash); } \ 528 private: \ 529 virtual void DoDeleteContents( wxHashTableBase_Node* node ) \ 530 { delete (eltype*)node->GetData(); } \ 531 \ 532 DECLARE_NO_COPY_CLASS(hashclass) \ 533 } 534 535#else // if wxUSE_OLD_HASH_TABLE 536 537#define _WX_DECLARE_HASH(eltype, listclass, hashclass, classexp) \ 538 classexp hashclass : public wxHashTableBase \ 539 { \ 540 public: \ 541 hashclass(wxKeyType keyType = wxKEY_INTEGER, \ 542 size_t size = wxHASH_SIZE_DEFAULT) \ 543 { Create(keyType, size); } \ 544 \ 545 virtual ~hashclass() { Destroy(); } \ 546 \ 547 void Put(long key, long val, eltype *data) { DoPut(key, val, data); } \ 548 void Put(long key, eltype *data) { DoPut(key, key, data); } \ 549 \ 550 eltype *Get(long key, long value) const \ 551 { \ 552 wxNodeBase *node = GetNode(key, value); \ 553 return node ? ((listclass::Node *)node)->GetData() : (eltype *)0; \ 554 } \ 555 eltype *Get(long key) const { return Get(key, key); } \ 556 \ 557 eltype *Delete(long key, long value) \ 558 { \ 559 eltype *data; \ 560 \ 561 wxNodeBase *node = GetNode(key, value); \ 562 if ( node ) \ 563 { \ 564 data = ((listclass::Node *)node)->GetData(); \ 565 \ 566 delete node; \ 567 m_count--; \ 568 } \ 569 else \ 570 { \ 571 data = (eltype *)0; \ 572 } \ 573 \ 574 return data; \ 575 } \ 576 eltype *Delete(long key) { return Delete(key, key); } \ 577 \ 578 protected: \ 579 void DoPut(long key, long value, eltype *data) \ 580 { \ 581 size_t slot = (size_t)abs((int)(key % (long)m_hashSize)); \ 582 \ 583 if ( !m_hashTable[slot] ) \ 584 { \ 585 m_hashTable[slot] = new listclass(m_keyType); \ 586 if ( m_deleteContents ) \ 587 m_hashTable[slot]->DeleteContents(true); \ 588 } \ 589 \ 590 ((listclass *)m_hashTable[slot])->Append(value, data); \ 591 m_count++; \ 592 } \ 593 \ 594 DECLARE_NO_COPY_CLASS(hashclass) \ 595 } 596 597#endif // wxUSE_OLD_HASH_TABLE 598 599// this macro is to be used in the user code 600#define WX_DECLARE_HASH(el, list, hash) \ 601 _WX_DECLARE_HASH(el, list, hash, class) 602 603// and this one does exactly the same thing but should be used inside the 604// library 605#define WX_DECLARE_EXPORTED_HASH(el, list, hash) \ 606 _WX_DECLARE_HASH(el, list, hash, class WXDLLEXPORT) 607 608#define WX_DECLARE_USER_EXPORTED_HASH(el, list, hash, usergoo) \ 609 _WX_DECLARE_HASH(el, list, hash, class usergoo) 610 611// delete all hash elements 612// 613// NB: the class declaration of the hash elements must be visible from the 614// place where you use this macro, otherwise the proper destructor may not 615// be called (a decent compiler should give a warning about it, but don't 616// count on it)! 617#define WX_CLEAR_HASH_TABLE(hash) \ 618 { \ 619 (hash).BeginFind(); \ 620 wxHashTable::compatibility_iterator it = (hash).Next(); \ 621 while( it ) \ 622 { \ 623 delete it->GetData(); \ 624 it = (hash).Next(); \ 625 } \ 626 (hash).Clear(); \ 627 } 628 629#endif 630 // _WX_HASH_H__ 631