← Back to branch summary

~ubuntu-branches/ubuntu/vivid/emscripten/vivid

« back to all changes in this revision

Viewing changes to tests/bullet/src/BulletCollision/Gimpact/gim_hash_table.h

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2013-05-02 13:11:51 UTC
  • Revision ID: package-import@ubuntu.com-20130502131151-q8dvteqr1ef2x7xz
Tags: upstream-1.4.1~20130504~adb56cb
Import upstream version 1.4.1~20130504~adb56cb

Show diffs side-by-side

added added

removed removed

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