source: icXML/icXML-devel/src/icxmlc/HashTable.hpp @ 2807

Last change on this file since 2807 was 2807, checked in by cameron, 6 years ago

Fixes default attribute+namespace resolution; hashing

File size: 9.6 KB
Line 
1/*
2 *  Copyright © 2012 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icXML is a trademark of International Characters.
5 */
6
7/*
8 * @author Nigel Medforth, nigelm -at- interational-characters.com
9 * @version $Id: HashTable.hpp 243 2013-01-12 00:31:44Z nigelm $
10 *
11 */
12
13#ifndef HASHTABLE_HPP
14#define HASHTABLE_HPP
15
16#include <icxmlc/murmurhash3.h>
17#include <icxmlc/Array.hpp>
18#include <icxmlc/stringpool.h>
19#include <icxmlc/XMLConfig.hpp>
20#include <simd-lib/perflib/i386_timer.h>
21
22XERCES_CPP_NAMESPACE_BEGIN
23
24// QUESTION: is it better to use the gid concept to allow for internal list reorganization or to use a "memory pool"
25// to store everything and return pointers to immutable entries?
26
27/// -----------------------------------------------------------------------------------------------------------------
28
29template <class T, typename Char, unsigned int defaultSize, bool userIndexedList = false>
30class HashTable
31{
32        public:
33
34                HashTable()
35                : _count(0)
36                , _seed0((hash_t)BIG_CONSTANT(0x36c45fd53c6a7bfb))
37                , _seed1((hash_t)BIG_CONSTANT(0xba08eec2ec6fc58d))
38                {
39
40
41
42                }
43
44        ~HashTable() { }
45
46                gid_t find
47                (
48                        const Char *                            key
49                        , const unsigned int            length
50                ) const;
51
52                gid_t add
53                (
54                        const T &                               value
55                );
56
57                gid_t add
58                (
59                        const T &                               value
60                        , const unsigned int            index
61                );
62
63                IDISA_ALWAYS_INLINE
64                gid_t indexOf(const T * entry) const
65                {
66                        return static_cast<gid_t>(entry - &_list[0]);
67                }
68
69                // NOTE: it is NOT safe to store pointers to these entries; they will
70                // be relocated in memory whenever the table expands itself.
71                T * operator[](const gid_t gid)
72                {
73                        return &_list[gid];
74                }
75
76                // NOTE: it is NOT safe to store pointers to these entries; they will
77                // be relocated in memory whenever the table expands itself.
78                const T * operator[](const gid_t gid) const
79                {
80                        return &_list[gid];
81                }
82
83                size_t count() const
84                {
85                        return _count;
86                }
87
88                void flush();
89
90        private:
91
92                IDISA_ALWAYS_INLINE
93                bool rebuild();
94
95                IDISA_ALWAYS_INLINE
96                bool expand();
97
98                bool repopulate();
99
100                IDISA_ALWAYS_INLINE
101                bool clear_and_repopulate();
102
103                IDISA_ALWAYS_INLINE
104                void regenerate_seeds();
105
106                IDISA_ALWAYS_INLINE
107        void swap(T *& a, T *& b)
108                {
109            // check into __atomic_exchange() ?
110            T * const c = b; b = a; a = c;
111                }
112
113                /**
114                put an entry at the hashed location and return the entry that
115                was evicted from that spot (if one exists).
116                **/
117                IDISA_ALWAYS_INLINE
118                T * place(T * entry)
119                {
120            DEBUG_MESSAGE("hashA(" << entry->getKey() << ')')
121                        const size_t idx1 = hashA(entry->getKey(), entry->getLength());
122            swap(entry, _table[idx1]);
123                        if (unlikely(entry != NULL))
124                        {
125                DEBUG_MESSAGE("hashB(" << entry->getKey() << ')')
126                const size_t idx2 = hashB(entry->getKey(), entry->getLength());
127                // don't swap them back; that'll guarantee an infinite loop
128                if (likely(idx1 != idx2))
129                {
130                    swap(entry, _table[idx2]);
131                }
132                        }
133                        return entry;
134                }
135
136                IDISA_ALWAYS_INLINE
137                size_t hashA(const Char * key, const hash_t length) const
138                {
139            return Murmur3<Char>::hash(key, length, _seed0, _table.capacity());
140                }
141
142
143                IDISA_ALWAYS_INLINE
144                size_t hashB(const Char * key, const hash_t length) const
145                {
146            return Murmur3<Char>::hash(key, length, _seed1, _table.capacity());
147                }
148
149                IDISA_ALWAYS_INLINE
150                bool equals(const T * entry, const Char * key, const hash_t length) const
151                {
152                        return likely(entry != 0) ? entry->equals(key, length) : 0;
153                }
154
155        private:
156
157                DynamicArray<T*, defaultSize>                                                                   _table;
158                DynamicArray<T, defaultSize>                                                                    _list;
159                size_t                                                                                                                  _count;
160                hash_t                                                                                                                  _seed0;
161                hash_t                                                                                                                  _seed1;
162};
163
164
165#define HASH_TABLE(retType) \
166        template <class T, typename Char, unsigned int defaultSize, bool userIndexedList> \
167        IDISA_ALWAYS_INLINE \
168        retType \
169        HashTable<T, Char, defaultSize, userIndexedList>
170
171/// -----------------------------------------------------------------------------------------------------------------
172
173HASH_TABLE(gid_t)::
174find
175(
176        const Char *                            key
177        , const unsigned int            length
178) const
179{
180        // WARNING! if this function causes a segfault, check the hash code function!
181        // what if the length of the key is 0, or it's unaligned? will the function still work?
182
183        hash_t idx = hashA(key, length);
184        if (likely(equals(_table[idx], key, length)))
185        {
186                return indexOf(_table[idx]);
187        }
188
189        idx = hashB(key, length);
190        if (likely(equals(_table[idx], key, length)))
191        {
192                return indexOf(_table[idx]);
193        }
194
195        return -1;
196}
197
198/// -----------------------------------------------------------------------------------------------------------------
199
200HASH_TABLE(gid_t)::
201add
202(
203        const T &                               item
204)
205{
206        if (!userIndexedList)
207        {
208                // WARNING! if this function causes a segfault, check the hash code function!
209                // what if the length of the key is 0, or it's unaligned? will the function still work?
210
211        // DEBUG_MESSAGE(std::hex << (size_t)(this) << std::dec << ".add(" << item.getKey() << ')')
212
213                if (unlikely(_count == _list.capacity()))
214                {
215                        expand();
216                }
217
218                const gid_t gid = _count++;
219
220                _list[gid] = item;
221                T * entry = &_list[gid];
222
223                T * evictedEntry = place(entry);
224
225                if (likely(evictedEntry == NULL))
226                {
227                        return gid;
228                }
229
230                // attempt to place this into one of the tables without expanding them
231                for (size_t attemptsRemaining = _count; attemptsRemaining; --attemptsRemaining)
232                {
233                        evictedEntry = place(evictedEntry);
234                        if (likely(evictedEntry == NULL))
235                        {
236                                return gid;
237                        }
238                }
239
240                // if we've gotten here then we almost assuredly hit an infinite rehashing loop; expand the tables and try again.
241                while (unlikely(!rebuild()));
242
243                return gid;
244        }
245        else
246        {
247                assert (!"INCORRECT ADD METHOD CALLED IN HASH TABLE");
248                throw;
249        }
250}
251
252/// -----------------------------------------------------------------------------------------------------------------
253
254HASH_TABLE(gid_t)::
255add
256(
257        const T &                               item
258        , const unsigned int            index
259)
260{
261        if (userIndexedList)
262        {
263        // DEBUG_MESSAGE(std::hex << (size_t)(this) << std::dec << ".add(" << item.getKey() << ',' << index << ')')
264
265                // WARNING! if this function causes a segfault, check the hash code function!
266                // what if the length of the key is 0, or it's unaligned? will the function still work?
267
268                if (unlikely(index >= _list.capacity()))
269                {
270                        expand();
271                }
272
273                const gid_t gid = index;
274
275                _list[gid] = item;
276
277                T * entry = &_list[gid];
278                _count++;
279                T * evictedEntry = place(entry);
280
281                if (likely(evictedEntry == NULL))
282                {
283                        return gid;
284                }
285
286                // attempt to place this into one of the tables without expanding them
287                for (size_t attemptsRemaining = _count; attemptsRemaining; attemptsRemaining--)
288                {
289                        evictedEntry = place(evictedEntry);
290                        if (likely(evictedEntry == NULL))
291                        {
292                                return gid;
293                        }
294                }
295
296                // if we've gotten here then we almost assuredly hit an infinite rehashing loop; expand the tables and try again.
297                while (unlikely(!rebuild()));
298
299                return gid;
300        }
301        else
302        {
303                assert (!"INCORRECT ADD METHOD CALLED IN HASH TABLE");
304                throw;
305        }
306}
307
308/// -----------------------------------------------------------------------------------------------------------------
309
310HASH_TABLE(void)::
311flush()
312{
313        _table.clear();
314        _list.clear();
315        _count = 0;
316}
317
318/// -----------------------------------------------------------------------------------------------------------------
319
320HASH_TABLE(bool)::
321rebuild()
322{
323        DEBUG_MESSAGE(std::hex << (size_t)(this) << std::dec << ".HashTable::rebuild " << _table.capacity())
324
325    regenerate_seeds();
326    if (clear_and_repopulate()) return 1;
327
328//    regenerate_seeds();
329//    if (clear_and_repopulate()) return 1;
330
331        _table.expand(0);
332        return repopulate();
333}
334
335/// -----------------------------------------------------------------------------------------------------------------
336
337HASH_TABLE(void)::
338regenerate_seeds()
339{
340    register hash_t x = _seed1;
341    // recommended by xorshift paper for 32/64 settings
342    if (sizeof(hash_t) == 8)
343    {       
344        x ^= (x << 13);
345        x ^= (x >> 17);
346        x ^= (x << 5);
347    }
348    else
349    {
350        x ^= (x << 13);
351        x ^= (x >> 7);
352        x ^= (x << 17);
353    }
354    _seed1 += _seed0;
355    _seed0 = x;
356}
357
358/// -----------------------------------------------------------------------------------------------------------------
359
360HASH_TABLE(bool)::
361repopulate()
362{
363        DEBUG_MESSAGE(std::hex << (size_t)(this) << std::dec << ".HashTable::repopulate " << _table.capacity() << " userIndexedList=" << userIndexedList)
364
365        if (!userIndexedList)
366        {
367                for (size_t index = 0; index < _count; )
368                {
369                        T * unplacedEntry = &_list[index++];
370
371                        hash_t tries = index;
372                        for (; tries; tries--)
373                        {
374                                unplacedEntry = place(unplacedEntry);
375                                if (!unplacedEntry)
376                                {
377                                        break;
378                                }
379                        }
380                        if (!tries) return 0;
381                }
382        }
383        else
384        {
385                size_t remaining = _count;
386                for (size_t index = 0; (remaining); index++)
387                {
388                        T * unplacedEntry = &_list[index];
389
390                        if (unplacedEntry->getKey() != NULL)
391                        {
392                                size_t tries = index + 1;
393                                for (; tries; tries--)
394                                {
395                                        unplacedEntry = place(unplacedEntry);
396                                        if (!unplacedEntry)
397                                        {
398                                                break;
399                                        }
400                                }
401                                if (!tries) return 0;
402                                --remaining;
403                        }
404                }
405        }
406        return 1;
407}
408
409/// -----------------------------------------------------------------------------------------------------------------
410
411HASH_TABLE(bool)::
412clear_and_repopulate()
413{
414        _table.clear();
415        return repopulate();
416}
417
418
419/// -----------------------------------------------------------------------------------------------------------------
420
421HASH_TABLE(bool)::
422expand()
423{
424    _list.expand(_list.capacity());
425    DEBUG_MESSAGE("HashTable::expand() -> list.capacity=" << _list.capacity())
426    _table.expand(0);
427    return repopulate();
428}
429
430XERCES_CPP_NAMESPACE_END
431
432#undef HASH_TABLE
433
434#endif // HASHTABLE_HPP
Note: See TracBrowser for help on using the repository browser.