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

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

Initial check-in of icXML 0.8 source files

File size: 10.1 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 207 2012-12-02 20:38:22Z robc $
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                ~HashTable()
43                {
44                        flush();
45                }
46
47                gid_t find
48                (
49                        const Char *                            key
50                        , const unsigned int            length
51                ) const;
52
53                gid_t add
54                (
55                        const T &                               value
56                );
57
58                gid_t add
59                (
60                        const T &                               value
61                        , const unsigned int            index
62                );
63
64                IDISA_ALWAYS_INLINE
65                gid_t indexOf(const T * entry) const
66                {
67                        return static_cast<gid_t>(entry - &_list[0]);
68                }
69
70                // NOTE: it is NOT safe to store pointers to these entries; they will
71                // be relocated in memory whenever the table expands itself.
72                T * operator[](const gid_t gid)
73                {
74                        return &_list[gid];
75                }
76
77                // NOTE: it is NOT safe to store pointers to these entries; they will
78                // be relocated in memory whenever the table expands itself.
79                const T * operator[](const gid_t gid) const
80                {
81                        return &_list[gid];
82                }
83
84                size_t count() const
85                {
86                        return _count;
87                }
88
89                void flush();
90
91        private:
92
93                IDISA_ALWAYS_INLINE
94                bool rebuild();
95
96                IDISA_ALWAYS_INLINE
97                bool expand();
98
99                IDISA_ALWAYS_INLINE
100                bool repopulate();
101
102                IDISA_ALWAYS_INLINE
103                bool clear_and_repopulate();
104
105                IDISA_ALWAYS_INLINE
106                void regenerate_seeds();
107
108                IDISA_ALWAYS_INLINE
109                void swapEntry(T * & entry, size_t idx)
110                {
111                        // swap<T*>(entry, _table[idx]);
112
113                        T * temp = _table[idx];
114                        _table[idx] = entry;
115                        entry = temp;
116                }
117
118                /**
119                put an entry at the hashed location and return the entry that
120                was evicted from that spot (if one exists).
121                **/
122                IDISA_ALWAYS_INLINE
123                T * place(T * entry)
124                {
125                        const size_t idx1 = hashA(entry->getKey(), entry->getLength());
126
127                        swapEntry(entry, idx1);
128
129                        if (unlikely(entry != NULL))
130                        {
131                                size_t idx2 = hashA(entry->getKey(), entry->getLength());
132                                if (idx1 == idx2)
133                                {
134                                        idx2 = hashB(entry->getKey(), entry->getLength());
135                                }
136
137                                swapEntry(entry, idx2);
138                        }
139                        return entry;
140                }
141
142                IDISA_ALWAYS_INLINE
143                size_t hashA(const Char * key, const hash_t length) const
144                {
145                        const hash_t k = Murmur3<Char>::hash(key, length, _seed0);
146                        return k % _table.capacity();
147                }
148
149
150                IDISA_ALWAYS_INLINE
151                size_t hashB(const Char * key, const hash_t length) const
152                {
153                        const hash_t k = Murmur3<Char>::hash(key, length, _seed1);
154                        return k % _table.capacity();
155                }
156
157                IDISA_ALWAYS_INLINE
158                bool equals(const T * entry, const Char * key, const hash_t length) const
159                {
160                        return likely(entry != 0) ? entry->equals(key, length) : 0;
161                }
162
163
164
165        private:
166
167                DynamicArray<T*, defaultSize>                                                                   _table;
168                DynamicArray<T, defaultSize>                                                                    _list;
169                size_t                                                                                                                  _count;
170                hash_t                                                                                                                  _seed0;
171                hash_t                                                                                                                  _seed1;
172};
173
174
175#define HASH_TABLE(retType) \
176        template <class T, typename Char, unsigned int defaultSize, bool userIndexedList> \
177        IDISA_ALWAYS_INLINE \
178        retType \
179        HashTable<T, Char, defaultSize, userIndexedList>
180
181/// -----------------------------------------------------------------------------------------------------------------
182
183HASH_TABLE(gid_t)::
184find
185(
186        const Char *                            key
187        , const unsigned int            length
188) const
189{
190        // WARNING! if this function causes a segfault, check the hash code function!
191        // what if the length of the key is 0, or it's unaligned? will the function still work?
192
193        hash_t idx = hashA(key, length);
194        if (likely(equals(_table[idx], key, length)))
195        {
196                return indexOf(_table[idx]);
197        }
198
199        idx = hashB(key, length);
200        if (likely(equals(_table[idx], key, length)))
201        {
202                return indexOf(_table[idx]);
203        }
204
205        return -1;
206}
207
208/// -----------------------------------------------------------------------------------------------------------------
209
210HASH_TABLE(gid_t)::
211add
212(
213        const T &                               item
214)
215{
216        if (!userIndexedList)
217        {
218                // WARNING! if this function causes a segfault, check the hash code function!
219                // what if the length of the key is 0, or it's unaligned? will the function still work?
220
221        // DEBUG_MESSAGE(std::hex << (size_t)(this) << std::dec << ".add(" << item.getKey() << ')')
222
223                if (unlikely(_count == _list.capacity()))
224                {
225                        expand();
226                }
227
228                const gid_t gid = _count++;
229
230                _list[gid] = item;
231                T * entry = &_list[gid];
232
233                T * evictedEntry = place(entry);
234
235                if (likely(evictedEntry == NULL))
236                {
237                        return gid;
238                }
239
240                // attempt to place this into one of the tables without expanding them
241                for (size_t attemptsRemaining = _count; attemptsRemaining; --attemptsRemaining)
242                {
243                        evictedEntry = place(evictedEntry);
244                        if (likely(evictedEntry == NULL))
245                        {
246                                return gid;
247                        }
248                }
249
250                // if we've gotten here then we almost assuredly hit an infinite rehashing loop; expand the tables and try again.
251                while (unlikely(!rebuild()));
252
253                return gid;
254        }
255        else
256        {
257                assert (!"INCORRECT ADD METHOD CALLED IN HASH TABLE");
258                throw;
259        }
260}
261
262/// -----------------------------------------------------------------------------------------------------------------
263
264HASH_TABLE(gid_t)::
265add
266(
267        const T &                               item
268        , const unsigned int            index
269)
270{
271        if (userIndexedList)
272        {
273        // DEBUG_MESSAGE(std::hex << (size_t)(this) << std::dec << ".add(" << item.getKey() << ',' << index << ')')
274
275                // WARNING! if this function causes a segfault, check the hash code function!
276                // what if the length of the key is 0, or it's unaligned? will the function still work?
277
278                if (unlikely(index >= _list.capacity()))
279                {
280                        expand();
281                }
282
283                const gid_t gid = index;
284
285                assert (_list[gid].getKey() == NULL);
286
287                _list[gid] = item;
288
289                T * entry = &_list[gid];
290                _count++;
291                T * evictedEntry = place(entry);
292
293                if (likely(evictedEntry == NULL))
294                {
295                        return gid;
296                }
297
298                // attempt to place this into one of the tables without expanding them
299                for (size_t attemptsRemaining = _count; attemptsRemaining; attemptsRemaining--)
300                {
301                        evictedEntry = place(evictedEntry);
302                        if (likely(evictedEntry == NULL))
303                        {
304                                return gid;
305                        }
306                }
307
308                // if we've gotten here then we almost assuredly hit an infinite rehashing loop; expand the tables and try again.
309                while (unlikely(!rebuild()));
310
311                return gid;
312        }
313        else
314        {
315                assert (!"INCORRECT ADD METHOD CALLED IN HASH TABLE");
316                throw;
317        }
318}
319
320/// -----------------------------------------------------------------------------------------------------------------
321
322HASH_TABLE(void)::
323flush()
324{
325        _table.clear();
326        _list.clear();
327        _count = 0;
328}
329
330/// -----------------------------------------------------------------------------------------------------------------
331
332HASH_TABLE(bool)::
333rebuild()
334{
335        DEBUG_MESSAGE(std::hex << (size_t)(this) << std::dec << ".HashTable::rebuild " << _table.capacity())
336//      regenerate_seeds();
337//      if (clear_and_repopulate()) return 1;
338        _table.expand(0);
339        return repopulate();
340}
341
342/// -----------------------------------------------------------------------------------------------------------------
343
344HASH_TABLE(void)::
345regenerate_seeds()
346{
347        static uint64_t w = BIG_CONSTANT(0x649709e015d7f183);
348        static uint64_t x = BIG_CONSTANT(0xfb9c766f7f6c0843);
349        static uint64_t y = BIG_CONSTANT(0x0fc0be0a5dc6b207);
350        static uint64_t z = BIG_CONSTANT(0x4913e92641a74cf6);
351
352        const size_t SEEDS_PER_BITBLOCK = sizeof(BitBlock) / sizeof(hash_t);
353
354        union
355        {
356                BitBlock t;
357                hash_t seed[SEEDS_PER_BITBLOCK];
358        };
359
360        uint64_t seed0 = z;
361        z = y;
362        y = x;
363        x = w;
364        w = _seed0;
365
366        seed[0] = _seed1;
367        seed[SEEDS_PER_BITBLOCK / 2] = seed0;
368
369        t = simd_xor(t, mvmd<8>::slli<1>(t));
370        t = simd_xor(t, simd<64>::srli<5>(mvmd<8>::srli<8>(t)));
371        t = simd_xor(t, mvmd<8>::slli<8>(simd<64>::slli<9>(t)));
372
373        _seed0 = seed[0];
374        _seed1 = seed[1];
375}
376
377/// -----------------------------------------------------------------------------------------------------------------
378
379HASH_TABLE(bool)::
380repopulate()
381{
382        DEBUG_MESSAGE(std::hex << (size_t)(this) << std::dec << ".HashTable::repopulate " << _table.capacity() << " userIndexedList=" << userIndexedList)
383
384        if (!userIndexedList)
385        {
386                for (size_t index = 0; index < _count; )
387                {
388                        T * unplacedEntry = &_list[index++];
389
390                        hash_t tries = index;
391                        for (; tries; tries--)
392                        {
393                                unplacedEntry = place(unplacedEntry);
394                                if (!unplacedEntry)
395                                {
396                                        break;
397                                }
398                        }
399                        if (!tries) return 0;
400                }
401        }
402        else
403        {
404                size_t remaining = _count;
405                for (size_t index = 0; (remaining); index++)
406                {
407                        T * unplacedEntry = &_list[index];
408
409                        if (unplacedEntry->getKey() != NULL)
410                        {
411                                size_t tries = index + 1;
412                                for (; tries; tries--)
413                                {
414                                        unplacedEntry = place(unplacedEntry);
415                                        if (!unplacedEntry)
416                                        {
417                                                break;
418                                        }
419                                }
420                                if (!tries) return 0;
421                                --remaining;
422                        }
423                }
424        }
425        return 1;
426}
427
428/// -----------------------------------------------------------------------------------------------------------------
429
430HASH_TABLE(bool)::
431clear_and_repopulate()
432{
433        _table.clear();
434        return repopulate();
435}
436
437
438/// -----------------------------------------------------------------------------------------------------------------
439
440HASH_TABLE(bool)::
441expand()
442{
443        DEBUG_MESSAGE(std::hex << (size_t)(this) << std::dec << ".HashTable::expand " << _list.capacity())
444
445        const size_t origAddr = reinterpret_cast<size_t>(&_list[0]);
446
447        _list.expand(_list.capacity());
448
449        const size_t addrOffset = (reinterpret_cast<size_t>(&_list[0]) - origAddr);
450
451        for (size_t index = 0; index < _table.capacity(); index++)
452        {
453                if (unlikely(_table[index] != NULL))
454                {
455                        _table[index] = reinterpret_cast<T*>(reinterpret_cast<size_t>(_table[index]) + addrOffset);
456                }
457        }
458}
459
460XERCES_CPP_NAMESPACE_END
461
462#undef HASH_TABLE
463
464#endif // HASHTABLE_HPP
Note: See TracBrowser for help on using the repository browser.