Blender  V3.3
gim_hash_table.h
Go to the documentation of this file.
1 #ifndef GIM_HASH_TABLE_H_INCLUDED
2 #define GIM_HASH_TABLE_H_INCLUDED
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
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
43 
44 template <typename T>
46 {
50  {
51  }
52 
54  {
55  m_key = value.m_key;
56  m_data = value.m_data;
57  }
58 
60  {
61  m_key = key;
62  m_data = data;
63  }
64 
65  bool operator<(const GIM_HASH_TABLE_NODE<T>& other) const
66  {
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  {
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  {
82  if (m_key == other.m_key) return true;
83  return false;
84  }
85 };
86 
89 {
90 public:
91  template <class T>
92  inline GUINT operator()(const T& a)
93  {
94  return a.m_key;
95  }
96 };
97 
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 
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 
121 
124 template <typename T>
126 {
127  if (array_count < GIM_MIN_RADIX_SORT_SIZE)
128  {
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 
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 
161 
175 template <class T>
177 {
178 protected:
180 
182  //array< _node_type, SuperAllocator<_node_type> > m_nodes;
184  //SuperBufferedArray< _node_type > m_nodes;
185  bool m_sorted;
186 
192 
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 
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 
240 
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 
268  inline void _clear_table_memory()
269  {
270  if (m_hash_table == NULL) return;
272  m_hash_table = NULL;
273  m_table_size = 0;
274  }
275 
277  inline void _rehash()
278  {
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 
306  inline void _resize_table(GUINT newsize)
307  {
308  //Clear memory
310  //Alloc the data
311  _reserve_table_memory(newsize);
312  //Invalidate keys and rehash
313  _rehash();
314  }
315 
317  inline void _destroy()
318  {
319  if (m_hash_table == NULL) return;
321  }
322 
325  {
326  GUINT cell_index = _find_avaliable_cell(hashkey);
327 
328  if (cell_index == GIM_INVALID_HASH)
329  {
330  //rehashing
332  GUINT cell_index = _find_avaliable_cell(hashkey);
333  btAssert(cell_index != GIM_INVALID_HASH);
334  }
335  return cell_index;
336  }
337 
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 
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 
372 
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 
399 
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 
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 
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 
462 
465  inline void _insert_in_pos(GUINT hashkey, const T& value, GUINT pos)
466  {
467  m_nodes.insert(_node_type(hashkey, value), pos);
469  }
470 
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 
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:
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);
561  }
562  else
563  {
567  }
568  }
569  else if (reserve_size != 0)
570  {
571  m_nodes.reserve(reserve_size);
572  }
573  }
574 
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();
600  m_sorted = true;
601 
602  if (m_hash_table)
603  {
604  _rehash();
605  }
606  return true;
607  }
608 
610  {
611  if (m_hash_table) return false;
614  {
616  }
617  else
618  {
619  _resize_table(m_nodes.size() + 1);
620  }
621 
622  return true;
623  }
624 
626  {
627  if (m_hash_table == NULL) return true;
629  return sort();
630  }
631 
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  {
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 
656  inline GUINT size() const
657  {
658  return m_nodes.size();
659  }
660 
662  inline GUINT get_key(GUINT index) const
663  {
664  return m_nodes[index].m_key;
665  }
666 
668 
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 
686 
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 
720 
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 
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 
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 
808 
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 
826 
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 
845 
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
ATTR_WARN_UNUSED_RESULT const void * element
#define btAssert(x)
Definition: btScalar.h:295
Macro for comparing the key and the element.
int operator()(const T &a, GUINT key)
Macro for comparing Hash nodes.
int operator()(const T &a, const T &b)
Macro for getting the key.
GUINT operator()(const T &a)
Very simple array container with fast access and simd memory.
Definition: gim_array.h:43
A compact hash table implementation.
bool switch_to_hashtable()
void _clear_table_memory()
Clear all memory for the hash table.
bool _erase_unsorted(GUINT index)
faster, but unsorted
T & operator[](GUINT index)
GUINT find(GUINT hashkey)
Finds the index of the element with the key.
bool erase_by_key(GUINT hashkey)
bool erase_by_index_unsorted(GUINT index)
void _destroy()
Destroy hash table memory.
GUINT * m_hash_table
Hash table data management. The hash table has the indices to the corresponding m_nodes array.
void _insert_in_pos(GUINT hashkey, const T &value, GUINT pos)
Insert in position ordered.
T * get_value(GUINT hashkey)
Retrieves the value associated with the index.
GUINT _insert_hash_table(GUINT hashkey, const T &value)
insert an element in hash table
void _reserve_table_memory(GUINT newtablesize)
reserves the memory for the hash table.
void _resize_table(GUINT newsize)
Resize hash table indices.
GUINT _insert_sorted(GUINT hashkey, const T &value)
Insert an element in an ordered array.
gim_array< _node_type > m_nodes
The nodes.
GUINT _insert_hash_table_replace(GUINT hashkey, const T &value)
insert an element in hash table.
GUINT size() const
Retrieves the amount of keys.
GUINT insert_override(GUINT hashkey, const T &element)
Insert an element into the hash, and could overrite an existing object with the same hash.
const T & operator[](GUINT index) const
GUINT _assign_hash_table_cell(GUINT hashkey)
Finds an avaliable hash table cell, and resizes the table if there isn't space.
GIM_HASH_TABLE_NODE< T > _node_type
GUINT _insert_unsorted(GUINT hashkey, const T &value)
Fast insertion in m_nodes array.
void _rehash()
Invalidates the keys (Assigning GIM_INVALID_HASH to all) Reorders the hash keys.
GUINT get_key(GUINT index) const
Retrieves the hash key.
GUINT _find_cell(GUINT hashkey)
Returns the cell index.
T * get_value_by_index(GUINT index)
Retrieves the value by index.
void _invalidate_keys()
bool check_for_switching_to_hashtable()
If the container reaches the.
bool erase_by_index(GUINT index)
void set_sorted(bool value)
GUINT insert_unsorted(GUINT hashkey, const T &element)
Insert an element into the hash,But if this container is a sorted array, this inserts it unsorted.
GUINT _insert_sorted_replace(GUINT hashkey, const T &value)
GUINT _find_avaliable_cell(GUINT hashkey)
Find the avaliable cell for the hashkey, and return an existing cell if it has the same hash key.
bool switch_to_sorted_array()
GUINT m_min_hash_table_size
bool _erase_sorted(GUINT index)
Sorted array data management. The hash table has the indices to the corresponding m_nodes array.
gim_hash_table(GUINT reserve_size=GIM_DEFAULT_HASH_TABLE_SIZE, GUINT node_size=GIM_DEFAULT_HASH_TABLE_NODE_SIZE, GUINT min_hash_table_size=GIM_INVALID_HASH)
bool _erase_hash_table(GUINT hashkey)
erase by key in hash table
bool _erase_by_index_hash_table(GUINT index)
erase by index in hash table
GUINT insert(GUINT hashkey, const T &element)
Insert an element into the hash.
Prototype for copying elements.
Definition: gim_radixsort.h:86
#define GIM_DEFAULT_HASH_TABLE_SIZE
#define GIM_NUM_PRIME
static const GUINT gim_prime_list[GIM_NUM_PRIME]
GUINT gim_next_prime(GUINT number)
void gim_sort_hash_node_array(T *array, GUINT array_count)
Sorting for hash table.
#define GIM_MIN_RADIX_SORT_SIZE
calibrated on a PIII
#define GIM_INVALID_HASH
A very very high value.
#define GIM_DEFAULT_HASH_TABLE_NODE_SIZE
#define GUINT
Definition: gim_math.h:40
void gim_free(void *ptr)
Definition: gim_memory.cpp:117
void * gim_alloc(size_t size)
Standar Memory functions.
Definition: gim_memory.cpp:82
bool gim_binary_search(const T *_array, GUINT _start_i, GUINT _end_i, const T &_search_key, GUINT &_result_index)
Failsafe Iterative binary search,Template version.
void gim_heap_sort(T *pArr, GUINT element_count, COMP_CLASS CompareFunc)
bool gim_binary_search_ex(const T *_array, GUINT _start_i, GUINT _end_i, GUINT &_result_index, const KEYCLASS &_search_key, COMP_CLASS _comp_macro)
Failsafe Iterative binary search,.
void gim_radix_sort(T *array, GUINT element_count, GETKEY_CLASS get_uintkey_macro, COPY_CLASS copy_elements_macro)
Sorts array in place. For generic use.
uint pos
#define T
static unsigned a[3]
Definition: RandGen.cpp:78
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
GIM_HASH_TABLE_NODE(GUINT key, const T &data)
bool operator<(const GIM_HASH_TABLE_NODE< T > &other) const
bool operator==(const GIM_HASH_TABLE_NODE< T > &other) const
GIM_HASH_TABLE_NODE(const GIM_HASH_TABLE_NODE &value)
bool operator>(const GIM_HASH_TABLE_NODE< T > &other) const
PointerRNA * ptr
Definition: wm_files.c:3480