Bullet Collision Detection & Physics Library
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-----------------------------------------------------------------------------
8This source file is part of GIMPACT Library.
9
10For the latest info, see http://gimpact.sourceforge.net/
11
12Copyright (c) 2006 Francisco Leon Najera. C.C. 80087371.
13email: 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
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
44
45template<typename T>
47{
51 {
52 }
53
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 {
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 {
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 {
83 if(m_key == other.m_key) return true;
84 return false;
85 }
86};
87
90{
91public:
92 template<class T>
93 inline GUINT operator()( const T& a)
94 {
95 return a.m_key;
96 }
97};
98
99
100
103{
104public:
105 template<class T>
106 inline int operator() ( const T& a, GUINT key)
107 {
108 return ((int)(a.m_key - key));
109 }
110};
111
114{
115public:
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
128
131template<typename T>
132void 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
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
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
176
190template<class T>
192{
193protected:
195
197 //array< _node_type, SuperAllocator<_node_type> > m_nodes;
199 //SuperBufferedArray< _node_type > m_nodes;
201
207
208
209
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
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
259
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
288 {
289 if(m_hash_table==NULL) return;
291 m_hash_table = NULL;
292 m_table_size = 0;
293 }
294
296 inline void _rehash()
297 {
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
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
326 inline void _resize_table(GUINT newsize)
327 {
328 //Clear memory
330 //Alloc the data
331 _reserve_table_memory(newsize);
332 //Invalidate keys and rehash
333 _rehash();
334 }
335
337 inline void _destroy()
338 {
339 if(m_hash_table==NULL) return;
341 }
342
345 {
346 GUINT cell_index = _find_avaliable_cell(hashkey);
347
348 if(cell_index==GIM_INVALID_HASH)
349 {
350 //rehashing
352 GUINT cell_index = _find_avaliable_cell(hashkey);
353 btAssert(cell_index!=GIM_INVALID_HASH);
354 }
355 return cell_index;
356 }
357
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
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
394
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
421
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
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
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
486
489 inline void _insert_in_pos(GUINT hashkey, const T & value, GUINT pos)
490 {
491 m_nodes.insert(_node_type(hashkey,value),pos);
493 }
494
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
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
565public:
566
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);
590 }
591 else
592 {
596 }
597 }
598 else if(reserve_size!=0)
599 {
600 m_nodes.reserve(reserve_size);
601 }
602
603 }
604
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();
631 m_sorted=true;
632
633
634
635 if(m_hash_table)
636 {
637 _rehash();
638 }
639 return true;
640 }
641
643 {
644 if(m_hash_table) return false;
647 {
649 }
650 else
651 {
652 _resize_table(m_nodes.size()+1);
653 }
654
655 return true;
656 }
657
659 {
660 if(m_hash_table==NULL) return true;
662 return sort();
663 }
664
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 {
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
689 inline GUINT size() const
690 {
691 return m_nodes.size();
692 }
693
695 inline GUINT get_key(GUINT index) const
696 {
697 return m_nodes[index].m_key;
698 }
699
701
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
719
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
754
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
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
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
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
847
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
865
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
886
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
#define btAssert(x)
Definition: btScalar.h:131
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:44
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
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.
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.
const T & operator[](GUINT index) const
GUINT _insert_sorted(GUINT hashkey, const T &value)
Insert an element in an ordered array.
GUINT _insert_hash_table_replace(GUINT hashkey, const T &value)
insert an element in hash table.
T * get_value(GUINT hashkey)
Retrieves the value associated with the index.
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.
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.
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)
T & operator[](GUINT index)
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
gim_array< _node_type > m_nodes
The nodes.
bool _erase_sorted(GUINT index)
Sorted array data management. The hash table has the indices to the corresponding m_nodes array.
T * get_value_by_index(GUINT index)
Retrieves the value by index.
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:89
#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:42
void * gim_alloc(size_t size)
Standar Memory functions.
Definition: gim_memory.cpp:86
void gim_free(void *ptr)
Definition: gim_memory.cpp:119
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.
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