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