Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: code/trunk/src/external/bullet/BulletCollision/Gimpact/gim_hash_table.h @ 8066

Last change on this file since 8066 was 5781, checked in by rgrieder, 15 years ago

Reverted trunk again. We might want to find a way to delete these revisions again (x3n's changes are still available as diff in the commit mails).

  • Property svn:eol-style set to native
File size: 23.4 KB
Line 
1#ifndef GIM_HASH_TABLE_H_INCLUDED
2#define GIM_HASH_TABLE_H_INCLUDED
3/*! \file gim_trimesh_data.h
4\author Francisco Len Nßjera
5*/
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 //!< 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
45template<typename T>
46struct 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
89class GIM_HASH_NODE_GET_KEY
90{
91public:
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
102class GIM_HASH_NODE_CMP_KEY_MACRO
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
112///Macro for comparing Hash nodes
113class GIM_HASH_NODE_CMP_MACRO
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
127//! Sorting for hash table
128/*!
129switch automatically between quicksort and radixsort
130*/
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
153static 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
163inline 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/*!
177A memory aligned compact hash table that coud be treated as an array.
178It could be a simple sorted array without the overhead of the hash key bucked, or could
179be a formely hash table with an array of keys.
180You 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.
185When 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*/
190template<class T>
191class gim_hash_table
192{
193protected:
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
565public:
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
Note: See TracBrowser for help on using the repository browser.