src/BulletCollision/Gimpact/gim_hash_table.h

   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@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