1///////////////////////////////////////////////////////////////////////////// 2// Name: src/common/hash.cpp 3// Purpose: wxHashTable implementation 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.cpp 49529 2007-10-30 00:32:18Z VZ $ 8// Copyright: (c) Julian Smart 9// Licence: wxWindows licence 10///////////////////////////////////////////////////////////////////////////// 11 12// ============================================================================ 13// declarations 14// ============================================================================ 15 16// ---------------------------------------------------------------------------- 17// headers 18// ---------------------------------------------------------------------------- 19 20// For compilers that support precompilation, includes "wx.h". 21#include "wx/wxprec.h" 22 23#ifdef __BORLANDC__ 24 #pragma hdrstop 25#endif 26 27#ifndef WX_PRECOMP 28 #include "wx/list.h" 29 #include "wx/hash.h" 30#endif 31 32#if wxUSE_OLD_HASH_TABLE 33 34#include <string.h> 35#include <stdarg.h> 36 37// ---------------------------------------------------------------------------- 38// wxWin macros 39// ---------------------------------------------------------------------------- 40 41IMPLEMENT_DYNAMIC_CLASS(wxHashTable, wxObject) 42 43// ============================================================================ 44// implementation 45// ============================================================================ 46 47// ---------------------------------------------------------------------------- 48// wxHashTablleBase for working with "void *" data 49// ---------------------------------------------------------------------------- 50 51wxHashTableBase::wxHashTableBase() 52{ 53 m_deleteContents = false; 54 m_hashTable = (wxListBase **)NULL; 55 m_hashSize = 0; 56 m_count = 0; 57 m_keyType = wxKEY_NONE; 58} 59 60void wxHashTableBase::Create(wxKeyType keyType, size_t size) 61{ 62 Destroy(); 63 64 m_hashSize = size; 65 m_keyType = keyType; 66 m_hashTable = new wxListBase *[size]; 67 for ( size_t n = 0; n < m_hashSize; n++ ) 68 { 69 m_hashTable[n] = (wxListBase *) NULL; 70 } 71} 72 73void wxHashTableBase::Destroy() 74{ 75 if ( m_hashTable ) 76 { 77 for ( size_t n = 0; n < m_hashSize; n++ ) 78 { 79 delete m_hashTable[n]; 80 } 81 82 delete [] m_hashTable; 83 84 m_hashTable = (wxListBase **)NULL; 85 86 m_count = 0; 87 } 88} 89 90void wxHashTableBase::DeleteContents(bool flag) 91{ 92 m_deleteContents = flag; 93 for ( size_t n = 0; n < m_hashSize; n++ ) 94 { 95 if ( m_hashTable[n] ) 96 { 97 m_hashTable[n]->DeleteContents(flag); 98 } 99 } 100} 101 102wxNodeBase *wxHashTableBase::GetNode(long key, long value) const 103{ 104 size_t slot = (size_t)abs((int)(key % (long)m_hashSize)); 105 106 wxNodeBase *node; 107 if ( m_hashTable[slot] ) 108 { 109 node = m_hashTable[slot]->Find(wxListKey(value)); 110 } 111 else 112 { 113 node = (wxNodeBase *)NULL; 114 } 115 116 return node; 117} 118 119#if WXWIN_COMPATIBILITY_2_4 120 121// ---------------------------------------------------------------------------- 122// wxHashTableLong 123// ---------------------------------------------------------------------------- 124 125wxHashTableLong::~wxHashTableLong() 126{ 127 Destroy(); 128} 129 130void wxHashTableLong::Init(size_t size) 131{ 132 m_hashSize = size; 133 m_values = new wxArrayLong *[size]; 134 m_keys = new wxArrayLong *[size]; 135 136 for ( size_t n = 0; n < m_hashSize; n++ ) 137 { 138 m_values[n] = 139 m_keys[n] = (wxArrayLong *)NULL; 140 } 141 142 m_count = 0; 143} 144 145void wxHashTableLong::Create(size_t size) 146{ 147 Init(size); 148} 149 150void wxHashTableLong::Destroy() 151{ 152 for ( size_t n = 0; n < m_hashSize; n++ ) 153 { 154 delete m_values[n]; 155 delete m_keys[n]; 156 } 157 158 delete [] m_values; 159 delete [] m_keys; 160 m_hashSize = 0; 161 m_count = 0; 162} 163 164void wxHashTableLong::Put(long key, long value) 165{ 166 wxCHECK_RET( m_hashSize, _T("must call Create() first") ); 167 168 size_t slot = (size_t)abs((int)(key % (long)m_hashSize)); 169 170 if ( !m_keys[slot] ) 171 { 172 m_keys[slot] = new wxArrayLong; 173 m_values[slot] = new wxArrayLong; 174 } 175 176 m_keys[slot]->Add(key); 177 m_values[slot]->Add(value); 178 179 m_count++; 180} 181 182long wxHashTableLong::Get(long key) const 183{ 184 wxCHECK_MSG( m_hashSize, wxNOT_FOUND, _T("must call Create() first") ); 185 186 size_t slot = (size_t)abs((int)(key % (long)m_hashSize)); 187 188 wxArrayLong *keys = m_keys[slot]; 189 if ( keys ) 190 { 191 size_t count = keys->GetCount(); 192 for ( size_t n = 0; n < count; n++ ) 193 { 194 if ( keys->Item(n) == key ) 195 { 196 return m_values[slot]->Item(n); 197 } 198 } 199 } 200 201 return wxNOT_FOUND; 202} 203 204long wxHashTableLong::Delete(long key) 205{ 206 wxCHECK_MSG( m_hashSize, wxNOT_FOUND, _T("must call Create() first") ); 207 208 size_t slot = (size_t)abs((int)(key % (long)m_hashSize)); 209 210 wxArrayLong *keys = m_keys[slot]; 211 if ( keys ) 212 { 213 size_t count = keys->GetCount(); 214 for ( size_t n = 0; n < count; n++ ) 215 { 216 if ( keys->Item(n) == key ) 217 { 218 long val = m_values[slot]->Item(n); 219 220 keys->RemoveAt(n); 221 m_values[slot]->RemoveAt(n); 222 223 m_count--; 224 225 return val; 226 } 227 } 228 } 229 230 return wxNOT_FOUND; 231} 232 233// ---------------------------------------------------------------------------- 234// wxStringHashTable: more efficient than storing strings in a list 235// ---------------------------------------------------------------------------- 236 237wxStringHashTable::wxStringHashTable(size_t sizeTable) 238{ 239 m_keys = new wxArrayLong *[sizeTable]; 240 m_values = new wxArrayString *[sizeTable]; 241 242 m_hashSize = sizeTable; 243 for ( size_t n = 0; n < m_hashSize; n++ ) 244 { 245 m_values[n] = (wxArrayString *)NULL; 246 m_keys[n] = (wxArrayLong *)NULL; 247 } 248} 249 250wxStringHashTable::~wxStringHashTable() 251{ 252 Destroy(); 253} 254 255void wxStringHashTable::Destroy() 256{ 257 for ( size_t n = 0; n < m_hashSize; n++ ) 258 { 259 delete m_values[n]; 260 delete m_keys[n]; 261 } 262 263 delete [] m_values; 264 delete [] m_keys; 265 m_hashSize = 0; 266} 267 268void wxStringHashTable::Put(long key, const wxString& value) 269{ 270 wxCHECK_RET( m_hashSize, _T("must call Create() first") ); 271 272 size_t slot = (size_t)abs((int)(key % (long)m_hashSize)); 273 274 if ( !m_keys[slot] ) 275 { 276 m_keys[slot] = new wxArrayLong; 277 m_values[slot] = new wxArrayString; 278 } 279 280 m_keys[slot]->Add(key); 281 m_values[slot]->Add(value); 282} 283 284wxString wxStringHashTable::Get(long key, bool *wasFound) const 285{ 286 wxCHECK_MSG( m_hashSize, wxEmptyString, _T("must call Create() first") ); 287 288 size_t slot = (size_t)abs((int)(key % (long)m_hashSize)); 289 290 wxArrayLong *keys = m_keys[slot]; 291 if ( keys ) 292 { 293 size_t count = keys->GetCount(); 294 for ( size_t n = 0; n < count; n++ ) 295 { 296 if ( keys->Item(n) == key ) 297 { 298 if ( wasFound ) 299 *wasFound = true; 300 301 return m_values[slot]->Item(n); 302 } 303 } 304 } 305 306 if ( wasFound ) 307 *wasFound = false; 308 309 return wxEmptyString; 310} 311 312bool wxStringHashTable::Delete(long key) const 313{ 314 wxCHECK_MSG( m_hashSize, false, _T("must call Create() first") ); 315 316 size_t slot = (size_t)abs((int)(key % (long)m_hashSize)); 317 318 wxArrayLong *keys = m_keys[slot]; 319 if ( keys ) 320 { 321 size_t count = keys->GetCount(); 322 for ( size_t n = 0; n < count; n++ ) 323 { 324 if ( keys->Item(n) == key ) 325 { 326 keys->RemoveAt(n); 327 m_values[slot]->RemoveAt(n); 328 return true; 329 } 330 } 331 } 332 333 return false; 334} 335 336#endif // WXWIN_COMPATIBILITY_2_4 337 338// ---------------------------------------------------------------------------- 339// old not type safe wxHashTable 340// ---------------------------------------------------------------------------- 341 342wxHashTable::wxHashTable (int the_key_type, int size) 343{ 344 n = 0; 345 hash_table = (wxList**) NULL; 346 Create(the_key_type, size); 347 m_count = 0; 348 m_deleteContents = false; 349/* 350 n = size; 351 current_position = -1; 352 current_node = (wxNode *) NULL; 353 354 key_type = the_key_type; 355 hash_table = new wxList *[size]; 356 int i; 357 for (i = 0; i < size; i++) 358 hash_table[i] = (wxList *) NULL; 359*/ 360} 361 362wxHashTable::~wxHashTable () 363{ 364 Destroy(); 365} 366 367void wxHashTable::Destroy() 368{ 369 if (!hash_table) return; 370 int i; 371 for (i = 0; i < n; i++) 372 if (hash_table[i]) 373 delete hash_table[i]; 374 delete[] hash_table; 375 hash_table = NULL; 376} 377 378bool wxHashTable::Create(int the_key_type, int size) 379{ 380 Destroy(); 381 382 n = size; 383 current_position = -1; 384 current_node = (wxNode *) NULL; 385 386 key_type = the_key_type; 387 hash_table = new wxList *[size]; 388 int i; 389 for (i = 0; i < size; i++) 390 hash_table[i] = (wxList *) NULL; 391 return true; 392} 393 394 395void wxHashTable::DoCopy(const wxHashTable& table) 396{ 397 n = table.n; 398 m_count = table.m_count; 399 current_position = table.current_position; 400 current_node = NULL; // doesn't matter - Next() will reconstruct it 401 key_type = table.key_type; 402 403 hash_table = new wxList *[n]; 404 for (int i = 0; i < n; i++) { 405 if (table.hash_table[i] == NULL) 406 hash_table[i] = NULL; 407 else { 408 hash_table[i] = new wxList(key_type); 409 *hash_table[i] = *(table.hash_table[i]); 410 } 411 } 412} 413 414void wxHashTable::Put (long key, long value, wxObject * object) 415{ 416 // Should NEVER be 417 long k = (long) key; 418 419 int position = (int) (k % n); 420 if (position < 0) position = -position; 421 422 if (!hash_table[position]) 423 { 424 hash_table[position] = new wxList (wxKEY_INTEGER); 425 if (m_deleteContents) hash_table[position]->DeleteContents(true); 426 } 427 428 hash_table[position]->Append (value, object); 429 m_count++; 430} 431 432void wxHashTable::Put (long key, const wxChar *value, wxObject * object) 433{ 434 // Should NEVER be 435 long k = (long) key; 436 437 int position = (int) (k % n); 438 if (position < 0) position = -position; 439 440 if (!hash_table[position]) 441 { 442 hash_table[position] = new wxList (wxKEY_STRING); 443 if (m_deleteContents) hash_table[position]->DeleteContents(true); 444 } 445 446 hash_table[position]->Append (value, object); 447 m_count++; 448} 449 450void wxHashTable::Put (long key, wxObject * object) 451{ 452 // Should NEVER be 453 long k = (long) key; 454 455 int position = (int) (k % n); 456 if (position < 0) position = -position; 457 458 if (!hash_table[position]) 459 { 460 hash_table[position] = new wxList (wxKEY_INTEGER); 461 if (m_deleteContents) hash_table[position]->DeleteContents(true); 462 } 463 464 hash_table[position]->Append (k, object); 465 m_count++; 466} 467 468void wxHashTable::Put (const wxChar *key, wxObject * object) 469{ 470 int position = (int) (MakeKey (key) % n); 471 if (position < 0) position = -position; 472 473 if (!hash_table[position]) 474 { 475 hash_table[position] = new wxList (wxKEY_STRING); 476 if (m_deleteContents) hash_table[position]->DeleteContents(true); 477 } 478 479 hash_table[position]->Append (key, object); 480 m_count++; 481} 482 483wxObject *wxHashTable::Get (long key, long value) const 484{ 485 // Should NEVER be 486 long k = (long) key; 487 488 int position = (int) (k % n); 489 if (position < 0) position = -position; 490 491 if (!hash_table[position]) 492 return (wxObject *) NULL; 493 else 494 { 495 wxNode *node = hash_table[position]->Find (value); 496 if (node) 497 return node->GetData (); 498 else 499 return (wxObject *) NULL; 500 } 501} 502 503wxObject *wxHashTable::Get (long key, const wxChar *value) const 504{ 505 // Should NEVER be 506 long k = (long) key; 507 508 int position = (int) (k % n); 509 if (position < 0) position = -position; 510 511 if (!hash_table[position]) 512 return (wxObject *) NULL; 513 else 514 { 515 wxNode *node = hash_table[position]->Find (value); 516 if (node) 517 return node->GetData (); 518 else 519 return (wxObject *) NULL; 520 } 521} 522 523wxObject *wxHashTable::Get (long key) const 524{ 525 // Should NEVER be 526 long k = (long) key; 527 528 int position = (int) (k % n); 529 if (position < 0) position = -position; 530 531 if (!hash_table[position]) 532 return (wxObject *) NULL; 533 else 534 { 535 wxNode *node = hash_table[position]->Find (k); 536 return node ? node->GetData () : (wxObject*)NULL; 537 } 538} 539 540wxObject *wxHashTable::Get (const wxChar *key) const 541{ 542 int position = (int) (MakeKey (key) % n); 543 if (position < 0) position = -position; 544 545 if (!hash_table[position]) 546 return (wxObject *) NULL; 547 else 548 { 549 wxNode *node = hash_table[position]->Find (key); 550 return node ? node->GetData () : (wxObject*)NULL; 551 } 552} 553 554wxObject *wxHashTable::Delete (long key) 555{ 556 // Should NEVER be 557 long k = (long) key; 558 559 int position = (int) (k % n); 560 if (position < 0) position = -position; 561 562 if (!hash_table[position]) 563 return (wxObject *) NULL; 564 else 565 { 566 wxNode *node = hash_table[position]->Find (k); 567 if (node) 568 { 569 wxObject *data = node->GetData (); 570 delete node; 571 m_count--; 572 return data; 573 } 574 else 575 return (wxObject *) NULL; 576 } 577} 578 579wxObject *wxHashTable::Delete (const wxChar *key) 580{ 581 int position = (int) (MakeKey (key) % n); 582 if (position < 0) position = -position; 583 584 if (!hash_table[position]) 585 return (wxObject *) NULL; 586 else 587 { 588 wxNode *node = hash_table[position]->Find (key); 589 if (node) 590 { 591 wxObject *data = node->GetData (); 592 delete node; 593 m_count--; 594 return data; 595 } 596 else 597 return (wxObject *) NULL; 598 } 599} 600 601wxObject *wxHashTable::Delete (long key, int value) 602{ 603 // Should NEVER be 604 long k = (long) key; 605 606 int position = (int) (k % n); 607 if (position < 0) position = -position; 608 609 if (!hash_table[position]) 610 return (wxObject *) NULL; 611 else 612 { 613 wxNode *node = hash_table[position]->Find (value); 614 if (node) 615 { 616 wxObject *data = node->GetData (); 617 delete node; 618 m_count--; 619 return data; 620 } 621 else 622 return (wxObject *) NULL; 623 } 624} 625 626wxObject *wxHashTable::Delete (long key, const wxChar *value) 627{ 628 int position = (int) (key % n); 629 if (position < 0) position = -position; 630 631 if (!hash_table[position]) 632 return (wxObject *) NULL; 633 else 634 { 635 wxNode *node = hash_table[position]->Find (value); 636 if (node) 637 { 638 wxObject *data = node->GetData (); 639 delete node; 640 m_count--; 641 return data; 642 } 643 else 644 return (wxObject *) NULL; 645 } 646} 647 648long wxHashTable::MakeKey (const wxChar *string) const 649{ 650 long int_key = 0; 651 652 while (*string) 653 int_key += (wxUChar) *string++; 654 655 return int_key; 656} 657 658void wxHashTable::BeginFind () 659{ 660 current_position = -1; 661 current_node = (wxNode *) NULL; 662} 663 664wxHashTable::Node* wxHashTable::Next () 665{ 666 wxNode *found = (wxNode *) NULL; 667 bool end = false; 668 while (!end && !found) 669 { 670 if (!current_node) 671 { 672 current_position++; 673 if (current_position >= n) 674 { 675 current_position = -1; 676 current_node = (wxNode *) NULL; 677 end = true; 678 } 679 else 680 { 681 if (hash_table[current_position]) 682 { 683 current_node = hash_table[current_position]->GetFirst (); 684 found = current_node; 685 } 686 } 687 } 688 else 689 { 690 current_node = current_node->GetNext (); 691 found = current_node; 692 } 693 } 694 return found; 695} 696 697void wxHashTable::DeleteContents (bool flag) 698{ 699 int i; 700 m_deleteContents = flag; 701 for (i = 0; i < n; i++) 702 { 703 if (hash_table[i]) 704 hash_table[i]->DeleteContents (flag); 705 } 706} 707 708void wxHashTable::Clear () 709{ 710 int i; 711 if (hash_table) 712 { 713 for (i = 0; i < n; i++) 714 { 715 if (hash_table[i]) 716 hash_table[i]->Clear (); 717 } 718 } 719 m_count = 0; 720} 721 722#else // if !wxUSE_OLD_HASH_TABLE 723 724wxHashTableBase_Node::wxHashTableBase_Node( long key, void* value, 725 wxHashTableBase* table ) 726 : m_value( value ), m_hashPtr( table ) 727{ 728 m_key.integer = key; 729} 730 731wxHashTableBase_Node::wxHashTableBase_Node( const wxChar* key, void* value, 732 wxHashTableBase* table ) 733 : m_value( value ), m_hashPtr( table ) 734{ 735 m_key.string = wxStrcpy( new wxChar[wxStrlen( key ) + 1], key ); 736} 737 738wxHashTableBase_Node::~wxHashTableBase_Node() 739{ 740 if( m_hashPtr ) m_hashPtr->DoRemoveNode( this ); 741} 742 743// 744 745wxHashTableBase::wxHashTableBase() 746 : m_size( 0 ), m_count( 0 ), m_table( NULL ), m_keyType( wxKEY_NONE ), 747 m_deleteContents( false ) 748{ 749} 750 751void wxHashTableBase::Create( wxKeyType keyType, size_t size ) 752{ 753 m_keyType = keyType; 754 m_size = size; 755 m_table = new wxHashTableBase_Node*[ m_size ]; 756 757 for( size_t i = 0; i < m_size; ++i ) 758 m_table[i] = NULL; 759} 760 761void wxHashTableBase::Clear() 762{ 763 for( size_t i = 0; i < m_size; ++i ) 764 { 765 Node* end = m_table[i]; 766 767 if( end == NULL ) 768 continue; 769 770 Node *curr, *next = end->GetNext(); 771 772 do 773 { 774 curr = next; 775 next = curr->GetNext(); 776 777 DoDestroyNode( curr ); 778 779 delete curr; 780 } 781 while( curr != end ); 782 783 m_table[i] = NULL; 784 } 785 786 m_count = 0; 787} 788 789void wxHashTableBase::DoRemoveNode( wxHashTableBase_Node* node ) 790{ 791 size_t bucket = ( m_keyType == wxKEY_INTEGER ? 792 node->m_key.integer : 793 MakeKey( node->m_key.string ) ) % m_size; 794 795 if( node->GetNext() == node ) 796 { 797 // single-node chain (common case) 798 m_table[bucket] = NULL; 799 } 800 else 801 { 802 Node *start = m_table[bucket], *curr; 803 Node* prev = start; 804 805 for( curr = prev->GetNext(); curr != node; 806 prev = curr, curr = curr->GetNext() ) ; 807 808 DoUnlinkNode( bucket, node, prev ); 809 } 810 811 DoDestroyNode( node ); 812} 813 814void wxHashTableBase::DoDestroyNode( wxHashTableBase_Node* node ) 815{ 816 // if it is called from DoRemoveNode, node has already been 817 // removed, from other places it does not matter 818 node->m_hashPtr = NULL; 819 820 if( m_keyType == wxKEY_STRING ) 821 delete[] node->m_key.string; 822 if( m_deleteContents ) 823 DoDeleteContents( node ); 824} 825 826void wxHashTableBase::Destroy() 827{ 828 Clear(); 829 830 delete[] m_table; 831 832 m_table = NULL; 833 m_size = 0; 834} 835 836void wxHashTableBase::DoInsertNode( size_t bucket, wxHashTableBase_Node* node ) 837{ 838 if( m_table[bucket] == NULL ) 839 { 840 m_table[bucket] = node->m_next = node; 841 } 842 else 843 { 844 Node *prev = m_table[bucket]; 845 Node *next = prev->m_next; 846 847 prev->m_next = node; 848 node->m_next = next; 849 m_table[bucket] = node; 850 } 851 852 ++m_count; 853} 854 855void wxHashTableBase::DoPut( long key, long hash, void* data ) 856{ 857 wxASSERT( m_keyType == wxKEY_INTEGER ); 858 859 size_t bucket = size_t(hash) % m_size; 860 Node* node = new wxHashTableBase_Node( key, data, this ); 861 862 DoInsertNode( bucket, node ); 863} 864 865void wxHashTableBase::DoPut( const wxChar* key, long hash, void* data ) 866{ 867 wxASSERT( m_keyType == wxKEY_STRING ); 868 869 size_t bucket = size_t(hash) % m_size; 870 Node* node = new wxHashTableBase_Node( key, data, this ); 871 872 DoInsertNode( bucket, node ); 873} 874 875void* wxHashTableBase::DoGet( long key, long hash ) const 876{ 877 wxASSERT( m_keyType == wxKEY_INTEGER ); 878 879 size_t bucket = size_t(hash) % m_size; 880 881 if( m_table[bucket] == NULL ) 882 return NULL; 883 884 Node *first = m_table[bucket]->GetNext(), 885 *curr = first; 886 887 do 888 { 889 if( curr->m_key.integer == key ) 890 return curr->m_value; 891 892 curr = curr->GetNext(); 893 } 894 while( curr != first ); 895 896 return NULL; 897} 898 899void* wxHashTableBase::DoGet( const wxChar* key, long hash ) const 900{ 901 wxASSERT( m_keyType == wxKEY_STRING ); 902 903 size_t bucket = size_t(hash) % m_size; 904 905 if( m_table[bucket] == NULL ) 906 return NULL; 907 908 Node *first = m_table[bucket]->GetNext(), 909 *curr = first; 910 911 do 912 { 913 if( wxStrcmp( curr->m_key.string, key ) == 0 ) 914 return curr->m_value; 915 916 curr = curr->GetNext(); 917 } 918 while( curr != first ); 919 920 return NULL; 921} 922 923void wxHashTableBase::DoUnlinkNode( size_t bucket, wxHashTableBase_Node* node, 924 wxHashTableBase_Node* prev ) 925{ 926 if( node == m_table[bucket] ) 927 m_table[bucket] = prev; 928 929 if( prev == node && prev == node->GetNext() ) 930 m_table[bucket] = NULL; 931 else 932 prev->m_next = node->m_next; 933 934 DoDestroyNode( node ); 935 --m_count; 936} 937 938void* wxHashTableBase::DoDelete( long key, long hash ) 939{ 940 wxASSERT( m_keyType == wxKEY_INTEGER ); 941 942 size_t bucket = size_t(hash) % m_size; 943 944 if( m_table[bucket] == NULL ) 945 return NULL; 946 947 Node *first = m_table[bucket]->GetNext(), 948 *curr = first, 949 *prev = m_table[bucket]; 950 951 do 952 { 953 if( curr->m_key.integer == key ) 954 { 955 void* retval = curr->m_value; 956 curr->m_value = NULL; 957 958 DoUnlinkNode( bucket, curr, prev ); 959 delete curr; 960 961 return retval; 962 } 963 964 prev = curr; 965 curr = curr->GetNext(); 966 } 967 while( curr != first ); 968 969 return NULL; 970} 971 972void* wxHashTableBase::DoDelete( const wxChar* key, long hash ) 973{ 974 wxASSERT( m_keyType == wxKEY_STRING ); 975 976 size_t bucket = size_t(hash) % m_size; 977 978 if( m_table[bucket] == NULL ) 979 return NULL; 980 981 Node *first = m_table[bucket]->GetNext(), 982 *curr = first, 983 *prev = m_table[bucket]; 984 985 do 986 { 987 if( wxStrcmp( curr->m_key.string, key ) == 0 ) 988 { 989 void* retval = curr->m_value; 990 curr->m_value = NULL; 991 992 DoUnlinkNode( bucket, curr, prev ); 993 delete curr; 994 995 return retval; 996 } 997 998 prev = curr; 999 curr = curr->GetNext(); 1000 } 1001 while( curr != first ); 1002 1003 return NULL; 1004} 1005 1006long wxHashTableBase::MakeKey( const wxChar *str ) 1007{ 1008 long int_key = 0; 1009 1010 while( *str ) 1011 int_key += (wxUChar)*str++; 1012 1013 return int_key; 1014} 1015 1016// ---------------------------------------------------------------------------- 1017// wxHashTable 1018// ---------------------------------------------------------------------------- 1019 1020wxHashTable::wxHashTable( const wxHashTable& table ) 1021 : wxHashTableBase() 1022{ 1023 DoCopy( table ); 1024} 1025 1026const wxHashTable& wxHashTable::operator=( const wxHashTable& table ) 1027{ 1028 Destroy(); 1029 DoCopy( table ); 1030 1031 return *this; 1032} 1033 1034void wxHashTable::DoCopy( const wxHashTable& WXUNUSED(table) ) 1035{ 1036 Create( m_keyType, m_size ); 1037 1038 wxFAIL; 1039} 1040 1041void wxHashTable::DoDeleteContents( wxHashTableBase_Node* node ) 1042{ 1043 delete ((wxHashTable_Node*)node)->GetData(); 1044} 1045 1046void wxHashTable::GetNextNode( size_t bucketStart ) 1047{ 1048 for( size_t i = bucketStart; i < m_size; ++i ) 1049 { 1050 if( m_table[i] != NULL ) 1051 { 1052 m_curr = ((Node*)m_table[i])->GetNext(); 1053 m_currBucket = i; 1054 return; 1055 } 1056 } 1057 1058 m_curr = NULL; 1059 m_currBucket = 0; 1060} 1061 1062wxHashTable::Node* wxHashTable::Next() 1063{ 1064 if( m_curr == NULL ) 1065 GetNextNode( 0 ); 1066 else 1067 { 1068 m_curr = m_curr->GetNext(); 1069 1070 if( m_curr == ( (Node*)m_table[m_currBucket] )->GetNext() ) 1071 GetNextNode( m_currBucket + 1 ); 1072 } 1073 1074 return m_curr; 1075} 1076 1077#endif // !wxUSE_OLD_HASH_TABLE 1078