1 #ifndef GIM_HASH_TABLE_H_INCLUDED 2 #define GIM_HASH_TABLE_H_INCLUDED 3 /*! \file gim_trimesh_data.h 4 \author Francisco Leon Najera 5 */ 6 /* 7 ----------------------------------------------------------------------------- 8 This source file is part of GIMPACT Library. 9 10 For the latest info, see http://gimpact.sourceforge.net/ 11 12 Copyright (c) 2006 Francisco Leon Najera. C.C. 80087371. 13 email: projectileman (at) yahoo.com 14 15 This library is free software; you can redistribute it and/or 16 modify it under the terms of EITHER: 17 (1) The GNU Lesser General Public License as published by the Free 18 Software Foundation; either version 2.1 of the License, or (at 19 your option) any later version. The text of the GNU Lesser 20 General Public License is included with this library in the 21 file GIMPACT-LICENSE-LGPL.TXT. 22 (2) The BSD-style license that is included with this library in 23 the file GIMPACT-LICENSE-BSD.TXT. 24 (3) The zlib/libpng license that is included with this library in 25 the file GIMPACT-LICENSE-ZLIB.TXT. 26 27 This library is distributed in the hope that it will be useful, 28 but WITHOUT ANY WARRANTY; without even the implied warranty of 29 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the files 30 GIMPACT-LICENSE-LGPL.TXT, GIMPACT-LICENSE-ZLIB.TXT and GIMPACT-LICENSE-BSD.TXT for more details. 31 32 ----------------------------------------------------------------------------- 33 */ 34 35 #include "gim_radixsort.h" 36 37 38 #define GIM_INVALID_HASH 0xffffffff //!< A very very high value 39 #define GIM_DEFAULT_HASH_TABLE_SIZE 380 40 #define GIM_DEFAULT_HASH_TABLE_NODE_SIZE 4 41 #define GIM_HASH_TABLE_GROW_FACTOR 2 42 43 #define GIM_MIN_RADIX_SORT_SIZE 860 //!< calibrated on a PIII 44 45 template<typename T> 46 struct GIM_HASH_TABLE_NODE 47 { 48 GUINT m_key; 49 T m_data; 50 GIM_HASH_TABLE_NODE() 51 { 52 } 53 54 GIM_HASH_TABLE_NODE(const GIM_HASH_TABLE_NODE & value) 55 { 56 m_key = value.m_key; 57 m_data = value.m_data; 58 } 59 60 GIM_HASH_TABLE_NODE(GUINT key, const T & data) 61 { 62 m_key = key; 63 m_data = data; 64 } 65 66 bool operator <(const GIM_HASH_TABLE_NODE<T> & other) const 67 { 68 ///inverse order, further objects are first 69 if(m_key < other.m_key) return true; 70 return false; 71 } 72 73 bool operator >(const GIM_HASH_TABLE_NODE<T> & other) const 74 { 75 ///inverse order, further objects are first 76 if(m_key > other.m_key) return true; 77 return false; 78 } 79 80 bool operator ==(const GIM_HASH_TABLE_NODE<T> & other) const 81 { 82 ///inverse order, further objects are first 83 if(m_key == other.m_key) return true; 84 return false; 85 } 86 }; 87 88 ///Macro for getting the key 89 class GIM_HASH_NODE_GET_KEY 90 { 91 public: 92 template<class T> 93 inline GUINT operator()( const T& a) 94 { 95 return a.m_key; 96 } 97 }; 98 99 100 101 ///Macro for comparing the key and the element 102 class GIM_HASH_NODE_CMP_KEY_MACRO 103 { 104 public: 105 template<class T> 106 inline int operator() ( const T& a, GUINT key) 107 { 108 return ((int)(a.m_key - key)); 109 } 110 }; 111 112 ///Macro for comparing Hash nodes 113 class GIM_HASH_NODE_CMP_MACRO 114 { 115 public: 116 template<class T> 117 inline int operator() ( const T& a, const T& b ) 118 { 119 return ((int)(a.m_key - b.m_key)); 120 } 121 }; 122 123 124 125 126 127 //! Sorting for hash table 128 /*! 129 switch automatically between quicksort and radixsort 130 */ 131 template<typename T> 132 void gim_sort_hash_node_array(T * array, GUINT array_count) 133 { 134 if(array_count<GIM_MIN_RADIX_SORT_SIZE) 135 { 136 gim_heap_sort(array,array_count,GIM_HASH_NODE_CMP_MACRO()); 137 } 138 else 139 { 140 memcopy_elements_func cmpfunc; 141 gim_radix_sort(array,array_count,GIM_HASH_NODE_GET_KEY(),cmpfunc); 142 } 143 } 144 145 146 147 148 149 150 // Note: assumes long is at least 32 bits. 151 #define GIM_NUM_PRIME 28 152 153 static const GUINT gim_prime_list[GIM_NUM_PRIME] = 154 { 155 53ul, 97ul, 193ul, 389ul, 769ul, 156 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, 157 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, 158 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, 159 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, 160 1610612741ul, 3221225473ul, 4294967291ul 161 }; 162 163 inline GUINT gim_next_prime(GUINT number) 164 { 165 //Find nearest upper prime 166 GUINT result_ind = 0; 167 gim_binary_search(gim_prime_list,0,(GIM_NUM_PRIME-2),number,result_ind); 168 169 // inv: result_ind < 28 170 return gim_prime_list[result_ind]; 171 } 172 173 174 175 //! A compact hash table implementation 176 /*! 177 A memory aligned compact hash table that coud be treated as an array. 178 It could be a simple sorted array without the overhead of the hash key bucked, or could 179 be a formely hash table with an array of keys. 180 You can use switch_to_hashtable() and switch_to_sorted_array for saving space or increase speed. 181 </br> 182 183 <ul> 184 <li> if node_size = 0, then this container becomes a simple sorted array allocator. reserve_size is used for reserve memory in m_nodes. 185 When the array size reaches the size equivalent to 'min_hash_table_size', then it becomes a hash table by calling check_for_switching_to_hashtable. 186 <li> If node_size != 0, then this container becomes a hash table for ever 187 </ul> 188 189 */ 190 template<class T> 191 class gim_hash_table 192 { 193 protected: 194 typedef GIM_HASH_TABLE_NODE<T> _node_type; 195 196 //!The nodes 197 //array< _node_type, SuperAllocator<_node_type> > m_nodes; 198 gim_array< _node_type > m_nodes; 199 //SuperBufferedArray< _node_type > m_nodes; 200 bool m_sorted; 201 202 ///Hash table data management. The hash table has the indices to the corresponding m_nodes array 203 GUINT * m_hash_table;//!< 204 GUINT m_table_size;//!< 205 GUINT m_node_size;//!< 206 GUINT m_min_hash_table_size; 207 208 209 210 //! Returns the cell index 211 inline GUINT _find_cell(GUINT hashkey) 212 { 213 _node_type * nodesptr = m_nodes.pointer(); 214 GUINT start_index = (hashkey%m_table_size)*m_node_size; 215 GUINT end_index = start_index + m_node_size; 216 217 while(start_index<end_index) 218 { 219 GUINT value = m_hash_table[start_index]; 220 if(value != GIM_INVALID_HASH) 221 { 222 if(nodesptr[value].m_key == hashkey) return start_index; 223 } 224 start_index++; 225 } 226 return GIM_INVALID_HASH; 227 } 228 229 //! Find the avaliable cell for the hashkey, and return an existing cell if it has the same hash key 230 inline GUINT _find_avaliable_cell(GUINT hashkey) 231 { 232 _node_type * nodesptr = m_nodes.pointer(); 233 GUINT avaliable_index = GIM_INVALID_HASH; 234 GUINT start_index = (hashkey%m_table_size)*m_node_size; 235 GUINT end_index = start_index + m_node_size; 236 237 while(start_index<end_index) 238 { 239 GUINT value = m_hash_table[start_index]; 240 if(value == GIM_INVALID_HASH) 241 { 242 if(avaliable_index==GIM_INVALID_HASH) 243 { 244 avaliable_index = start_index; 245 } 246 } 247 else if(nodesptr[value].m_key == hashkey) 248 { 249 return start_index; 250 } 251 start_index++; 252 } 253 return avaliable_index; 254 } 255 256 257 258 //! reserves the memory for the hash table. 259 /*! 260 \pre hash table must be empty 261 \post reserves the memory for the hash table, an initializes all elements to GIM_INVALID_HASH. 262 */ 263 inline void _reserve_table_memory(GUINT newtablesize) 264 { 265 if(newtablesize==0) return; 266 if(m_node_size==0) return; 267 268 //Get a Prime size 269 270 m_table_size = gim_next_prime(newtablesize); 271 272 GUINT datasize = m_table_size*m_node_size; 273 //Alloc the data buffer 274 m_hash_table = (GUINT *)gim_alloc(datasize*sizeof(GUINT)); 275 } 276 277 inline void _invalidate_keys() 278 { 279 GUINT datasize = m_table_size*m_node_size; 280 for(GUINT i=0;i<datasize;i++) 281 { 282 m_hash_table[i] = GIM_INVALID_HASH;// invalidate keys 283 } 284 } 285 286 //! Clear all memory for the hash table 287 inline void _clear_table_memory() 288 { 289 if(m_hash_table==NULL) return; 290 gim_free(m_hash_table); 291 m_hash_table = NULL; 292 m_table_size = 0; 293 } 294 295 //! Invalidates the keys (Assigning GIM_INVALID_HASH to all) Reorders the hash keys 296 inline void _rehash() 297 { 298 _invalidate_keys(); 299 300 _node_type * nodesptr = m_nodes.pointer(); 301 for(GUINT i=0;i<(GUINT)m_nodes.size();i++) 302 { 303 GUINT nodekey = nodesptr[i].m_key; 304 if(nodekey != GIM_INVALID_HASH) 305 { 306 //Search for the avaliable cell in buffer 307 GUINT index = _find_avaliable_cell(nodekey); 308 309 310 if(m_hash_table[index]!=GIM_INVALID_HASH) 311 {//The new index is alreade used... discard this new incomming object, repeated key 312 btAssert(m_hash_table[index]==nodekey); 313 nodesptr[i].m_key = GIM_INVALID_HASH; 314 } 315 else 316 { 317 //; 318 //Assign the value for alloc 319 m_hash_table[index] = i; 320 } 321 } 322 } 323 } 324 325 //! Resize hash table indices 326 inline void _resize_table(GUINT newsize) 327 { 328 //Clear memory 329 _clear_table_memory(); 330 //Alloc the data 331 _reserve_table_memory(newsize); 332 //Invalidate keys and rehash 333 _rehash(); 334 } 335 336 //! Destroy hash table memory 337 inline void _destroy() 338 { 339 if(m_hash_table==NULL) return; 340 _clear_table_memory(); 341 } 342 343 //! Finds an avaliable hash table cell, and resizes the table if there isn't space 344 inline GUINT _assign_hash_table_cell(GUINT hashkey) 345 { 346 GUINT cell_index = _find_avaliable_cell(hashkey); 347 348 if(cell_index==GIM_INVALID_HASH) 349 { 350 //rehashing 351 _resize_table(m_table_size+1); 352 GUINT cell_index = _find_avaliable_cell(hashkey); 353 btAssert(cell_index!=GIM_INVALID_HASH); 354 } 355 return cell_index; 356 } 357 358 //! erase by index in hash table 359 inline bool _erase_by_index_hash_table(GUINT index) 360 { 361 if(index >= m_nodes.size()) return false; 362 if(m_nodes[index].m_key != GIM_INVALID_HASH) 363 { 364 //Search for the avaliable cell in buffer 365 GUINT cell_index = _find_cell(m_nodes[index].m_key); 366 367 btAssert(cell_index!=GIM_INVALID_HASH); 368 btAssert(m_hash_table[cell_index]==index); 369 370 m_hash_table[cell_index] = GIM_INVALID_HASH; 371 } 372 373 return this->_erase_unsorted(index); 374 } 375 376 //! erase by key in hash table 377 inline bool _erase_hash_table(GUINT hashkey) 378 { 379 if(hashkey == GIM_INVALID_HASH) return false; 380 381 //Search for the avaliable cell in buffer 382 GUINT cell_index = _find_cell(hashkey); 383 if(cell_index ==GIM_INVALID_HASH) return false; 384 385 GUINT index = m_hash_table[cell_index]; 386 m_hash_table[cell_index] = GIM_INVALID_HASH; 387 388 return this->_erase_unsorted(index); 389 } 390 391 392 393 //! insert an element in hash table 394 /*! 395 If the element exists, this won't insert the element 396 \return the index in the array of the existing element,or GIM_INVALID_HASH if the element has been inserted 397 If so, the element has been inserted at the last position of the array. 398 */ 399 inline GUINT _insert_hash_table(GUINT hashkey, const T & value) 400 { 401 if(hashkey==GIM_INVALID_HASH) 402 { 403 //Insert anyway 404 _insert_unsorted(hashkey,value); 405 return GIM_INVALID_HASH; 406 } 407 408 GUINT cell_index = _assign_hash_table_cell(hashkey); 409 410 GUINT value_key = m_hash_table[cell_index]; 411 412 if(value_key!= GIM_INVALID_HASH) return value_key;// Not overrited 413 414 m_hash_table[cell_index] = m_nodes.size(); 415 416 _insert_unsorted(hashkey,value); 417 return GIM_INVALID_HASH; 418 } 419 420 //! insert an element in hash table. 421 /*! 422 If the element exists, this replaces the element. 423 \return the index in the array of the existing element,or GIM_INVALID_HASH if the element has been inserted 424 If so, the element has been inserted at the last position of the array. 425 */ 426 inline GUINT _insert_hash_table_replace(GUINT hashkey, const T & value) 427 { 428 if(hashkey==GIM_INVALID_HASH) 429 { 430 //Insert anyway 431 _insert_unsorted(hashkey,value); 432 return GIM_INVALID_HASH; 433 } 434 435 GUINT cell_index = _assign_hash_table_cell(hashkey); 436 437 GUINT value_key = m_hash_table[cell_index]; 438 439 if(value_key!= GIM_INVALID_HASH) 440 {//replaces the existing 441 m_nodes[value_key] = _node_type(hashkey,value); 442 return value_key;// index of the replaced element 443 } 444 445 m_hash_table[cell_index] = m_nodes.size(); 446 447 _insert_unsorted(hashkey,value); 448 return GIM_INVALID_HASH; 449 450 } 451 452 453 ///Sorted array data management. The hash table has the indices to the corresponding m_nodes array 454 inline bool _erase_sorted(GUINT index) 455 { 456 if(index>=(GUINT)m_nodes.size()) return false; 457 m_nodes.erase_sorted(index); 458 if(m_nodes.size()<2) m_sorted = false; 459 return true; 460 } 461 462 //! faster, but unsorted 463 inline bool _erase_unsorted(GUINT index) 464 { 465 if(index>=m_nodes.size()) return false; 466 467 GUINT lastindex = m_nodes.size()-1; 468 if(index<lastindex && m_hash_table!=0) 469 { 470 GUINT hashkey = m_nodes[lastindex].m_key; 471 if(hashkey!=GIM_INVALID_HASH) 472 { 473 //update the new position of the last element 474 GUINT cell_index = _find_cell(hashkey); 475 btAssert(cell_index!=GIM_INVALID_HASH); 476 //new position of the last element which will be swaped 477 m_hash_table[cell_index] = index; 478 } 479 } 480 m_nodes.erase(index); 481 m_sorted = false; 482 return true; 483 } 484 485 //! Insert in position ordered 486 /*! 487 Also checks if it is needed to transform this container to a hash table, by calling check_for_switching_to_hashtable 488 */ 489 inline void _insert_in_pos(GUINT hashkey, const T & value, GUINT pos) 490 { 491 m_nodes.insert(_node_type(hashkey,value),pos); 492 this->check_for_switching_to_hashtable(); 493 } 494 495 //! Insert an element in an ordered array 496 inline GUINT _insert_sorted(GUINT hashkey, const T & value) 497 { 498 if(hashkey==GIM_INVALID_HASH || size()==0) 499 { 500 m_nodes.push_back(_node_type(hashkey,value)); 501 return GIM_INVALID_HASH; 502 } 503 //Insert at last position 504 //Sort element 505 506 507 GUINT result_ind=0; 508 GUINT last_index = m_nodes.size()-1; 509 _node_type * ptr = m_nodes.pointer(); 510 511 bool found = gim_binary_search_ex( 512 ptr,0,last_index,result_ind,hashkey,GIM_HASH_NODE_CMP_KEY_MACRO()); 513 514 515 //Insert before found index 516 if(found) 517 { 518 return result_ind; 519 } 520 else 521 { 522 _insert_in_pos(hashkey, value, result_ind); 523 } 524 return GIM_INVALID_HASH; 525 } 526 527 inline GUINT _insert_sorted_replace(GUINT hashkey, const T & value) 528 { 529 if(hashkey==GIM_INVALID_HASH || size()==0) 530 { 531 m_nodes.push_back(_node_type(hashkey,value)); 532 return GIM_INVALID_HASH; 533 } 534 //Insert at last position 535 //Sort element 536 GUINT result_ind; 537 GUINT last_index = m_nodes.size()-1; 538 _node_type * ptr = m_nodes.pointer(); 539 540 bool found = gim_binary_search_ex( 541 ptr,0,last_index,result_ind,hashkey,GIM_HASH_NODE_CMP_KEY_MACRO()); 542 543 //Insert before found index 544 if(found) 545 { 546 m_nodes[result_ind] = _node_type(hashkey,value); 547 } 548 else 549 { 550 _insert_in_pos(hashkey, value, result_ind); 551 } 552 return result_ind; 553 } 554 555 //! Fast insertion in m_nodes array 556 inline GUINT _insert_unsorted(GUINT hashkey, const T & value) 557 { 558 m_nodes.push_back(_node_type(hashkey,value)); 559 m_sorted = false; 560 return GIM_INVALID_HASH; 561 } 562 563 564 565 public: 566 567 /*! 568 <li> if node_size = 0, then this container becomes a simple sorted array allocator. reserve_size is used for reserve memory in m_nodes. 569 When the array size reaches the size equivalent to 'min_hash_table_size', then it becomes a hash table by calling check_for_switching_to_hashtable. 570 <li> If node_size != 0, then this container becomes a hash table for ever 571 </ul> 572 */ 573 gim_hash_table(GUINT reserve_size = GIM_DEFAULT_HASH_TABLE_SIZE, 574 GUINT node_size = GIM_DEFAULT_HASH_TABLE_NODE_SIZE, 575 GUINT min_hash_table_size = GIM_INVALID_HASH) 576 { 577 m_hash_table = NULL; 578 m_table_size = 0; 579 m_sorted = false; 580 m_node_size = node_size; 581 m_min_hash_table_size = min_hash_table_size; 582 583 if(m_node_size!=0) 584 { 585 if(reserve_size!=0) 586 { 587 m_nodes.reserve(reserve_size); 588 _reserve_table_memory(reserve_size); 589 _invalidate_keys(); 590 } 591 else 592 { 593 m_nodes.reserve(GIM_DEFAULT_HASH_TABLE_SIZE); 594 _reserve_table_memory(GIM_DEFAULT_HASH_TABLE_SIZE); 595 _invalidate_keys(); 596 } 597 } 598 else if(reserve_size!=0) 599 { 600 m_nodes.reserve(reserve_size); 601 } 602 603 } 604 605 ~gim_hash_table() 606 { 607 _destroy(); 608 } 609 610 inline bool is_hash_table() 611 { 612 if(m_hash_table) return true; 613 return false; 614 } 615 616 inline bool is_sorted() 617 { 618 if(size()<2) return true; 619 return m_sorted; 620 } 621 622 bool sort() 623 { 624 if(is_sorted()) return true; 625 if(m_nodes.size()<2) return false; 626 627 628 _node_type * ptr = m_nodes.pointer(); 629 GUINT siz = m_nodes.size(); 630 gim_sort_hash_node_array(ptr,siz); 631 m_sorted=true; 632 633 634 635 if(m_hash_table) 636 { 637 _rehash(); 638 } 639 return true; 640 } 641 642 bool switch_to_hashtable() 643 { 644 if(m_hash_table) return false; 645 if(m_node_size==0) m_node_size = GIM_DEFAULT_HASH_TABLE_NODE_SIZE; 646 if(m_nodes.size()<GIM_DEFAULT_HASH_TABLE_SIZE) 647 { 648 _resize_table(GIM_DEFAULT_HASH_TABLE_SIZE); 649 } 650 else 651 { 652 _resize_table(m_nodes.size()+1); 653 } 654 655 return true; 656 } 657 658 bool switch_to_sorted_array() 659 { 660 if(m_hash_table==NULL) return true; 661 _clear_table_memory(); 662 return sort(); 663 } 664 665 //!If the container reaches the 666 bool check_for_switching_to_hashtable() 667 { 668 if(this->m_hash_table) return true; 669 670 if(!(m_nodes.size()< m_min_hash_table_size)) 671 { 672 if(m_node_size == 0) 673 { 674 m_node_size = GIM_DEFAULT_HASH_TABLE_NODE_SIZE; 675 } 676 677 _resize_table(m_nodes.size()+1); 678 return true; 679 } 680 return false; 681 } 682 683 inline void set_sorted(bool value) 684 { 685 m_sorted = value; 686 } 687 688 //! Retrieves the amount of keys. 689 inline GUINT size() const 690 { 691 return m_nodes.size(); 692 } 693 694 //! Retrieves the hash key. 695 inline GUINT get_key(GUINT index) const 696 { 697 return m_nodes[index].m_key; 698 } 699 700 //! Retrieves the value by index 701 /*! 702 */ 703 inline T * get_value_by_index(GUINT index) 704 { 705 return &m_nodes[index].m_data; 706 } 707 708 inline const T& operator[](GUINT index) const 709 { 710 return m_nodes[index].m_data; 711 } 712 713 inline T& operator[](GUINT index) 714 { 715 return m_nodes[index].m_data; 716 } 717 718 //! Finds the index of the element with the key 719 /*! 720 \return the index in the array of the existing element,or GIM_INVALID_HASH if the element has been inserted 721 If so, the element has been inserted at the last position of the array. 722 */ 723 inline GUINT find(GUINT hashkey) 724 { 725 if(m_hash_table) 726 { 727 GUINT cell_index = _find_cell(hashkey); 728 if(cell_index==GIM_INVALID_HASH) return GIM_INVALID_HASH; 729 return m_hash_table[cell_index]; 730 } 731 GUINT last_index = m_nodes.size(); 732 if(last_index<2) 733 { 734 if(last_index==0) return GIM_INVALID_HASH; 735 if(m_nodes[0].m_key == hashkey) return 0; 736 return GIM_INVALID_HASH; 737 } 738 else if(m_sorted) 739 { 740 //Binary search 741 GUINT result_ind = 0; 742 last_index--; 743 _node_type * ptr = m_nodes.pointer(); 744 745 bool found = gim_binary_search_ex(ptr,0,last_index,result_ind,hashkey,GIM_HASH_NODE_CMP_KEY_MACRO()); 746 747 748 if(found) return result_ind; 749 } 750 return GIM_INVALID_HASH; 751 } 752 753 //! Retrieves the value associated with the index 754 /*! 755 \return the found element, or null 756 */ 757 inline T * get_value(GUINT hashkey) 758 { 759 GUINT index = find(hashkey); 760 if(index == GIM_INVALID_HASH) return NULL; 761 return &m_nodes[index].m_data; 762 } 763 764 765 /*! 766 */ 767 inline bool erase_by_index(GUINT index) 768 { 769 if(index > m_nodes.size()) return false; 770 771 if(m_hash_table == NULL) 772 { 773 if(is_sorted()) 774 { 775 return this->_erase_sorted(index); 776 } 777 else 778 { 779 return this->_erase_unsorted(index); 780 } 781 } 782 else 783 { 784 return this->_erase_by_index_hash_table(index); 785 } 786 return false; 787 } 788 789 790 791 inline bool erase_by_index_unsorted(GUINT index) 792 { 793 if(index > m_nodes.size()) return false; 794 795 if(m_hash_table == NULL) 796 { 797 return this->_erase_unsorted(index); 798 } 799 else 800 { 801 return this->_erase_by_index_hash_table(index); 802 } 803 return false; 804 } 805 806 807 808 /*! 809 810 */ 811 inline bool erase_by_key(GUINT hashkey) 812 { 813 if(size()==0) return false; 814 815 if(m_hash_table) 816 { 817 return this->_erase_hash_table(hashkey); 818 } 819 //Binary search 820 821 if(is_sorted()==false) return false; 822 823 GUINT result_ind = find(hashkey); 824 if(result_ind!= GIM_INVALID_HASH) 825 { 826 return this->_erase_sorted(result_ind); 827 } 828 return false; 829 } 830 831 void clear() 832 { 833 m_nodes.clear(); 834 835 if(m_hash_table==NULL) return; 836 GUINT datasize = m_table_size*m_node_size; 837 //Initialize the hashkeys. 838 GUINT i; 839 for(i=0;i<datasize;i++) 840 { 841 m_hash_table[i] = GIM_INVALID_HASH;// invalidate keys 842 } 843 m_sorted = false; 844 } 845 846 //! Insert an element into the hash 847 /*! 848 \return If GIM_INVALID_HASH, the object has been inserted succesfully. Else it returns the position 849 of the existing element. 850 */ 851 inline GUINT insert(GUINT hashkey, const T & element) 852 { 853 if(m_hash_table) 854 { 855 return this->_insert_hash_table(hashkey,element); 856 } 857 if(this->is_sorted()) 858 { 859 return this->_insert_sorted(hashkey,element); 860 } 861 return this->_insert_unsorted(hashkey,element); 862 } 863 864 //! Insert an element into the hash, and could overrite an existing object with the same hash. 865 /*! 866 \return If GIM_INVALID_HASH, the object has been inserted succesfully. Else it returns the position 867 of the replaced element. 868 */ 869 inline GUINT insert_override(GUINT hashkey, const T & element) 870 { 871 if(m_hash_table) 872 { 873 return this->_insert_hash_table_replace(hashkey,element); 874 } 875 if(this->is_sorted()) 876 { 877 return this->_insert_sorted_replace(hashkey,element); 878 } 879 this->_insert_unsorted(hashkey,element); 880 return m_nodes.size(); 881 } 882 883 884 885 //! Insert an element into the hash,But if this container is a sorted array, this inserts it unsorted 886 /*! 887 */ 888 inline GUINT insert_unsorted(GUINT hashkey,const T & element) 889 { 890 if(m_hash_table) 891 { 892 return this->_insert_hash_table(hashkey,element); 893 } 894 return this->_insert_unsorted(hashkey,element); 895 } 896 897 898 }; 899 900 901 902 #endif // GIM_CONTAINERS_H_INCLUDED 903
