MFEM v4.8.0
Finite element discretization library
Loading...
Searching...
No Matches
hash.hpp
Go to the documentation of this file.
1// Copyright (c) 2010-2025, Lawrence Livermore National Security, LLC. Produced
2// at the Lawrence Livermore National Laboratory. All Rights reserved. See files
3// LICENSE and NOTICE for details. LLNL-CODE-806117.
4//
5// This file is part of the MFEM library. For more information and source code
6// availability visit https://mfem.org.
7//
8// MFEM is free software; you can redistribute it and/or modify it under the
9// terms of the BSD-3 license. We welcome feedback and contributions, see file
10// CONTRIBUTING.md for details.
11
12#ifndef MFEM_HASH
13#define MFEM_HASH
14
15#include "../config/config.hpp"
16#include "array.hpp"
17#include "globals.hpp"
18
19#include <array>
20#include <cstdint>
21#include <type_traits>
22#include <utility>
23
24namespace mfem
25{
26
27/** A concept for items that should be used in HashTable and be accessible by
28 * hashing two IDs.
29 */
30struct Hashed2
31{
32 int p1, p2;
33 int next;
34};
35
36/** A concept for items that should be used in HashTable and be accessible by
37 * hashing four IDs.
38 */
39struct Hashed4
40{
41 int p1, p2, p3; // NOTE: p4 is neither hashed nor stored
42 int next;
43};
44
45
46/** HashTable is a container for items that require associative access through
47 * pairs (or quadruples) of indices:
48 *
49 * (p1, p2) -> item
50 * (p1, p2, p3, p4) -> item
51 *
52 * An example of this are edges and faces in a mesh. Each edge is uniquely
53 * identified by two parent vertices and so can be easily accessed from
54 * different elements using this class. Similarly for faces.
55 *
56 * The order of the p1, p2, ... indices is not relevant as they are sorted
57 * each time this class is invoked.
58 *
59 * There are two main methods this class provides. The Get(...) methods always
60 * return an item given the two or four indices. If the item didn't previously
61 * exist, the methods creates a new one. The Find(...) methods, on the other
62 * hand, just return NULL or -1 if the item doesn't exist.
63 *
64 * Each new item is automatically assigned a unique ID - the index of the item
65 * inside the BlockArray. The IDs may (but need not) be used as p1, p2, ... of
66 * other items.
67 *
68 * The item type (T) needs to follow either the Hashed2 or the Hashed4
69 * concept. It is easiest to just inherit from these structs.
70 *
71 * All items in the container can also be accessed sequentially using the
72 * provided iterator.
73 *
74 * Notes:
75 * The data structure and implementation is based on a BlockArray<T> which
76 * provides an efficient item storage that avoids heap fragmentation, and
77 * index-based item access. The hash table implemented on top of the
78 * BlockArray provides fast associative (key -> value) access by grouping
79 * items into bins (buckets) of O(1) size.
80 * - "id" denotes the index of an item in the underlying BlockArray<T>,
81 * - "idx" denotes the index of a bin, determined by hashing a key with
82 * the function `Hash`.
83 */
84template<typename T>
85class HashTable : public BlockArray<T>
86{
87protected:
89
90public:
91 /** @brief Main constructor of the HashTable class.
92
93 @param[in] block_size The size of the storage blocks of the underlying
94 BlockArray<T>.
95 @param[in] init_hash_size The initial size of the hash table. Must be
96 a power of 2. */
97 HashTable(int block_size = 16*1024, int init_hash_size = 32*1024);
98 /// @brief Deep copy
99 HashTable(const HashTable& other);
100 /// @brief Copy assignment not supported
101 HashTable& operator=(const HashTable&) = delete;
103
104 /** @brief Item accessor with key (or parents) the pair 'p1', 'p2'. Default
105 construct an item of type T if no value correspond to the requested key.
106
107 @param[in] p1 First part of the key.
108 @param[in] p2 Second part of the key.
109 @return The index "id" of the key in the BlockArray<T>.
110
111 @warning This method should only be called if T inherits from Hashed2. */
112 T* Get(int p1, int p2);
113
114 /** @brief Item accessor with key (or parents) the quadruplet 'p1', 'p2',
115 'p3', 'p4'. The key 'p4' is optional. Default construct an item of type T
116 if no value corresponds to the requested key.
117
118 @param[in] p1 First part of the key.
119 @param[in] p2 Second part of the key.
120 @param[in] p3 Third part of the key.
121 @param[in] p4 Fourth part of the key (optional).
122 @return The index "id" of the key in the BlockArray<T>.
123
124 @warning This method should only be called if T inherits from Hashed4. */
125 T* Get(int p1, int p2, int p3, int p4 = -1 /* p4 optional */);
126
127 /// Get id of item whose parents are p1, p2... Create it if it doesn't exist.
128 /** @brief Get the "id" of an item, this "id" corresponding to the index of the
129 item in the underlying BlockArray<T> object. Default construct an item
130 and id if no value corresponds to the requested key.
131
132 @param[in] p1 First part of the key.
133 @param[in] p2 Second part of the key.
134 @return The index "id" of the key in the BlockArray<T>.
135
136 @warning This method should only be called if T inherits from Hashed2. */
137 int GetId(int p1, int p2);
138
139 /** @brief Get the "id" of an item, this "id" corresponding to the index of the
140 item in the underlying BlockArray<T> object. Default construct an item
141 and id if no value correspond to the requested key.
142
143 @param[in] p1 First part of the key.
144 @param[in] p2 Second part of the key.
145 @param[in] p3 Third part of the key.
146 @param[in] p4 Fourth part of the key (optional).
147 @return The index "id" of the key in the BlockArray<T>.
148
149 @warning This method should only be called if T inherits from Hashed4. */
150 int GetId(int p1, int p2, int p3, int p4 = -1);
151
152 /// Find item whose parents are p1, p2... Return NULL if it doesn't exist.
153 /** @brief Item accessor with key (or parents) the pair 'p1', 'p2'. Return
154 nullptr if no value correspond to the requested key.
155
156 @param[in] p1 First part of the key.
157 @param[in] p2 Second part of the key.
158 @return The item associated to the key (p1,p2).
159
160 @warning This method should only be called if T inherits from Hashed2. */
161 T* Find(int p1, int p2);
162
163 /** @brief Item accessor with key (or parents) the quadruplet 'p1', 'p2',
164 'p3', 'p4'. The key 'p4' is optional. Return nullptr if no value
165 correspond to the requested key.
166
167 @param[in] p1 First part of the key.
168 @param[in] p2 Second part of the key.
169 @param[in] p3 Third part of the key.
170 @param[in] p4 Fourth part of the key (optional).
171 @return The item associated to the key (p1,p2,p3,p4).
172
173 @warning This method should only be called if T inherits from Hashed4. */
174 T* Find(int p1, int p2, int p3, int p4 = -1);
175
176 /** @brief Item const accessor with key (or parents) the pair 'p1', 'p2'.
177 Return nullptr if no value correspond to the requested key.
178
179 @param[in] p1 First part of the key.
180 @param[in] p2 Second part of the key.
181 @return The item associated to the key (p1,p2).
182
183 @warning This method should only be called if T inherits from Hashed2. */
184 const T* Find(int p1, int p2) const;
185
186 /** @brief Item const accessor with key (or parents) the quadruplet 'p1',
187 'p2', 'p3', 'p4'. The key 'p4' is optional. Return nullptr if no value
188 correspond to the requested key.
189
190 @param[in] p1 First part of the key.
191 @param[in] p2 Second part of the key.
192 @param[in] p3 Third part of the key.
193 @param[in] p4 Fourth part of the key (optional).
194 @return The item associated to the key (p1,p2,p3,p4).
195
196 @warning This method should only be called if T inherits from Hashed4. */
197 const T* Find(int p1, int p2, int p3, int p4 = -1) const;
198
199 /// Find id of item whose parents are p1, p2... Return -1 if it doesn't exist.
200 /** @brief Find the "id" of an item, this "id" corresponding to the index of
201 the item in the underlying BlockArray<T> object. Default construct an
202 item and id if no value correspond to the requested key.
203
204 @param[in] p1 First part of the key.
205 @param[in] p2 Second part of the key.
206 @return The index "id" of the key in the BlockArray<T>.
207
208 @warning This method should only be called if T inherits from Hashed2. */
209 int FindId(int p1, int p2) const;
210
211 /** @brief Find the "id" of an item, this "id" corresponding to the index of
212 the item in the underlying BlockArray<T> object. Default construct an
213 item and id if no value correspond to the requested key.
214
215 @param[in] p1 First part of the key.
216 @param[in] p2 Second part of the key.
217 @param[in] p3 Third part of the key.
218 @param[in] p4 Fourth part of the key (optional).
219 @return The index "id" of the key in the BlockArray<T>.
220
221 @warning This method should only be called if T inherits from Hashed4. */
222 int FindId(int p1, int p2, int p3, int p4 = -1) const;
223
224 /// @brief Return the number of elements currently stored in the HashTable.
225 int Size() const { return Base::Size() - unused.Size(); }
226
227 /// @brief Return the total number of ids (used and unused) in the HashTable.
228 int NumIds() const { return Base::Size(); }
229
230 /// @brief Return the number of free/unused ids in the HashTable.
231 int NumFreeIds() const { return unused.Size(); }
232
233 /** @brief Return true if item 'id' exists in (is used by) the container.
234
235 @param[in] id Index of the item in the underlying BlockArray<T>.
236
237 @warning It is assumed that 0 <= id < NumIds(). */
238 bool IdExists(int id) const { return (Base::At(id).next != -2); }
239
240 /** @brief Remove an item from the hash table.
241
242 @param[in] id Index of the item in the underlying BlockArray<T>.
243
244 @warning Its id will be reused by newly added items. */
245 void Delete(int id);
246
247 /// @brief Remove all items.
248 void DeleteAll();
249
250 /** @brief Allocate an item at 'id'. Enlarge the underlying BlockArray if
251 necessary.
252
253 @param[in] id Index of the item in the underlying BlockArray<T>.
254 @param[in] p1 First part of the key.
255 @param[in] p2 Second part of the key.
256
257 @warning This is a special purpose method used when loading data from a
258 file. Does nothing if the slot 'id' has already been allocated. */
259 void Alloc(int id, int p1, int p2);
260
261 /** @brief Reinitialize the internal list of unallocated items.
262
263 @warning This is a special purpose method used when loading data from a file. */
265
266 /** @brief Change the key associated with an item.
267
268 In other words, makes an item hashed under different parent IDs.
269
270 @param[in] id Index of the item in the underlying BlockArray<T>.
271 @param[in] new_p1 First part of the new key.
272 @param[in] new_p2 Second part of the new key.
273
274 @warning This method should only be called if T inherits from Hashed2. */
275 void Reparent(int id, int new_p1, int new_p2);
276
277 /** @brief Change the key associated with an item.
278
279 In other words, makes an item hashed under different parent IDs.
280
281 @param[in] id Index of the item in the underlying BlockArray<T>.
282 @param[in] new_p1 First part of the new key.
283 @param[in] new_p2 Second part of the new key.
284 @param[in] new_p3 Third part of the new key.
285 @param[in] new_p4 Fourth part of the new key (optional).
286
287 @warning This method should only be called if T inherits from Hashed4. */
288 void Reparent(int id, int new_p1, int new_p2, int new_p3, int new_p4 = -1);
289
290 /// @brief Return total size of allocated memory (tables plus items), in bytes.
291 std::size_t MemoryUsage() const;
292
293 /// @brief Write details of the memory usage to the mfem output stream.
294 void PrintMemoryDetail() const;
295
296 /// @brief Print a histogram of bin sizes for debugging purposes.
297 void PrintStats() const;
298
300 {
301 protected:
302 friend class HashTable;
303 typedef typename Base::iterator base;
304
306 iterator(const base &it) : base(it)
307 {
308 while (base::good() && (*this)->next == -2) { base::next(); }
309 }
310
311 public:
313 {
314 while (base::next(), base::good() && (*this)->next == -2) { }
315 return *this;
316 }
317 };
318
320 {
321 protected:
322 friend class HashTable;
323 typedef typename Base::const_iterator base;
324
326 const_iterator(const base &it) : base(it)
327 {
328 while (base::good() && (*this)->next == -2) { base::next(); }
329 }
330
331 public:
333 {
334 while (base::next(), base::good() && (*this)->next == -2) { }
335 return *this;
336 }
337 };
338
340 iterator end() { return iterator(); }
342 const_iterator end() const { return const_iterator(); }
343
345 const_iterator cend() const { return const_iterator(); }
346
347protected:
348 /** The hash table: each bin is a linked list of items. For each non-empty
349 bin, this arrays stores the 'id' of the first item in the list, or -1
350 if the bin is empty. */
351 int* table;
352
353 /** mask = table_size-1. Used for fast modulo operation in Hash(), to wrap
354 the raw hashed index around the current table size (which must be a power
355 of two). */
356 int mask;
357
358 /** List of deleted items in the BlockArray<T>. New items are created with
359 these ids first, before they are appended to the block array. */
361
362 /** @brief hash function for Hashed2 items.
363
364 @param[in] p1 First part of the key.
365 @param[in] p2 Second part of the key.
366 @return The hash key "idx" identifying a bin/bucket.
367
368 NOTE: the constants are arbitrary
369 @warning This method should only be called if T inherits from Hashed2. */
370 inline int Hash(size_t p1, size_t p2) const
371 { return (984120265ul*p1 + 125965121ul*p2) & mask; }
372
373 /** @brief hash function for Hashed4 items.
374
375 @param[in] p1 First part of the key.
376 @param[in] p2 Second part of the key.
377 @param[in] p3 Third part of the key.
378 @return The hash key "idx" identifying a bin/bucket.
379
380 NOTE: The constants are arbitrary.
381 NOTE: p4 is not hashed nor stored as p1, p2, p3 identify a face uniquely.
382 @warning This method should only be called if T inherits from Hashed4. */
383 inline int Hash(size_t p1, size_t p2, size_t p3) const
384 { return (984120265ul*p1 + 125965121ul*p2 + 495698413ul*p3) & mask; }
385
386 // Delete() and Reparent() use one of these:
387 /// @brief Hash function for items of type T that inherit from Hashed2.
388 inline int Hash(const Hashed2& item) const
389 { return Hash(item.p1, item.p2); }
390
391 /// @brief Hash function for items of type T that inherit from Hashed4.
392 inline int Hash(const Hashed4& item) const
393 { return Hash(item.p1, item.p2, item.p3); }
394
395 /** @brief Search the index of the item associated to the key (p1,p2)
396 starting from the item with index @a id.
397
398 @param[in] id Index of the item in the underlying BlockArray<T>.
399 @param[in] p1 First part of the key.
400 @param[in] p2 Second part of the key.
401 @return The index "id" of the key in the BlockArray<T>.
402
403 @warning This method should only be called if T inherits from Hashed2. */
404 int SearchList(int id, int p1, int p2) const;
405
406 /** @brief Search the index of the item associated to the key (p1,p2,p3,(p4))
407 starting from the item with index @a id.
408
409 @param[in] id Index of the item in the underlying BlockArray<T>.
410 @param[in] p1 First part of the key.
411 @param[in] p2 Second part of the key.
412 @param[in] p3 Third part of the key.
413 @return The index "id" of the key in the BlockArray<T>.
414
415 @warning This method should only be called if T inherits from Hashed4. */
416 int SearchList(int id, int p1, int p2, int p3) const;
417
418 /** @brief Insert the item 'id' into bin 'idx'.
419
420 @param[in] idx The bin/bucket index.
421 @param[in] id The index of the item in the BlockArray<T>.
422 @param[in] item The item to insert at the beginning of the linked list.
423
424 @warning The method only works with bin 'idx' and does not check the
425 overall fill factor of the hash table. If appropriate,
426 use CheckRehash() for that. */
427 inline void Insert(int idx, int id, T &item);
428
429 /** @brief Unlink an item @a id from the linked list of bin @a idx.
430
431 @param[in] idx The bin/bucket index.
432 @param[in] id The index of the item in the BlockArray<T>.
433
434 @warning The method aborts if the item is not found. */
435 void Unlink(int idx, int id);
436
437 /** @brief Check table fill factor and resize if necessary.
438
439 The method checks the average size of the bins (i.e., the fill factor).
440 If the fill factor is > 2, the table is enlarged (see DoRehash()). */
441 inline void CheckRehash();
442
443 /** @brief Double the size of the hash table (i.e., double the number of bins)
444 and reinsert all items into the new bins.
445
446 NOTE: Rehashing is computationally expensive (O(N) in the number of items),
447 but since it is only done rarely (when the number of items doubles),
448 the amortized complexity of inserting an item is still O(1). */
449 void DoRehash();
450
451 /** @brief Return the size of the bin "idx".
452
453 @param[in] idx The index of the bin.
454 @return The size of the bin. */
455 int BinSize(int idx) const;
456};
457
458///
459/// @brief streaming implementation for murmurhash3 128 (x64).
460/// Constructs the hash in 3 stages: init, append, finalize.
461///
462struct Hasher
463{
464 /// where the final hash result is stored after finalize. Use data[1] when
465 /// only 64 bits are required.
466 uint64_t data[2] = {0, 0};
467
468private:
469 uint64_t nbytes = 0;
470
471 uint64_t buf_[2] = {0, 0};
472
473public:
474
475 /// resets this hasher back to an initial seed
476 void init(uint64_t seed = 0);
477 void append(const uint8_t *vs, uint64_t bytes);
478
479 void finalize();
480
481private:
482 // add 16 bytes
483 void add_block(uint64_t k1, uint64_t k2);
484
485 // add [1-8] more bytes, then finalize
486 void finalize(uint64_t k1, int num);
487
488 // add [1-15] more bytes, then finalize
489 // 0 < num < 16
490 void finalize(uint64_t k1, uint64_t k2, int num);
491};
492
493/// Helper class for hashing std::pair. Usable in place of std::hash<std::pair<T,U>>
495{
496 template <class T, class V>
497 size_t operator()(const std::pair<T, V> &v) const noexcept
498 {
499 Hasher hash;
500 // chosen randomly with a 2^64-sided dice
501 hash.init(0xfebd1fe69813c14full);
502 hash.append(reinterpret_cast<const uint8_t *>(&v.first), sizeof(T));
503 hash.append(reinterpret_cast<const uint8_t *>(&v.second), sizeof(V));
504 hash.finalize();
505 return hash.data[1];
506 }
507};
508
509/// Helper class for hashing std::array. Usable in place of std::hash<std::array<T,N>>
511{
512 template <class T, size_t N>
513 size_t operator()(const std::array<T, N> &v) const noexcept
514 {
515 Hasher hash;
516 // chosen randomly with a 2^64-sided dice
517 hash.init(0xfebd1fe69813c14full);
518 for (size_t i = 0; i < N; ++i)
519 {
520 hash.append(reinterpret_cast<const uint8_t *>(&v[i]), sizeof(T));
521 }
522 hash.finalize();
523 return hash.data[1];
524 }
525};
526
527/// Hash function for data sequences.
528/** Depends on GnuTLS for SHA-256 hashing. */
530{
531protected:
533
534 /// Add a sequence of bytes for hashing
535 void HashBuffer(const void *buffer, size_t num_bytes);
536
537 /// Integer encoding method; result is independent of endianness and type
538 template <typename int_type_const_iter>
539 HashFunction &EncodeAndHashInts(int_type_const_iter begin,
540 int_type_const_iter end);
541
542 /// Double encoding method: encode in little-endian byte-order
543 template <typename double_const_iter>
544 HashFunction &EncodeAndHashDoubles(double_const_iter begin,
545 double_const_iter end);
546
547public:
548 /// Default constructor: initialize the hash function
549 HashFunction();
550
551 /// Destructor
553
554 /// Add a sequence of bytes for hashing
555 HashFunction &AppendBytes(const void *seq, size_t num_bytes)
556 { HashBuffer(seq, num_bytes); return *this; }
557
558 /// Add a sequence of integers for hashing, given as a c-array.
559 /** Before hashing the sequence is encoded so that the result is independent
560 of endianness and type: int, long, unsigned, etc. */
561 template <typename int_type>
562 HashFunction &AppendInts(const int_type *ints, size_t num_ints)
563 { return EncodeAndHashInts(ints, ints + num_ints); }
564
565 /// Add a sequence of integers for hashing, given as a fixed-size c-array.
566 /** Before hashing the sequence is encoded so that the result is independent
567 of endianness and type: int, long, unsigned, etc. */
568 template <typename int_type, size_t num_ints>
569 HashFunction &AppendInts(const int_type (&ints)[num_ints])
570 { return EncodeAndHashInts(ints, ints + num_ints); }
571
572 /// Add a sequence of integers for hashing, given as a container.
573 /** Before hashing the sequence is encoded so that the result is independent
574 of endianness and type: int, long, unsigned, etc. */
575 template <typename int_type_container>
576 HashFunction &AppendInts(const int_type_container &ints)
577 { return EncodeAndHashInts(ints.begin(), ints.end()); }
578
579 /// Add a sequence of doubles for hashing, given as a c-array.
580 /** Before hashing the sequence is encoded so that the result is independent
581 of endianness. */
582 HashFunction &AppendDoubles(const real_t *doubles, size_t num_doubles)
583 { return EncodeAndHashDoubles(doubles, doubles + num_doubles); }
584
585 /// Add a sequence of doubles for hashing, given as a fixed-size c-array.
586 /** Before hashing the sequence is encoded so that the result is independent
587 of endianness. */
588 template <size_t num_doubles>
589 HashFunction &AppendDoubles(const real_t (&doubles)[num_doubles])
590 { return EncodeAndHashDoubles(doubles, doubles + num_doubles); }
591
592 /// Add a sequence of doubles for hashing, given as a container.
593 /** Before hashing the sequence is encoded so that the result is independent
594 of endianness. */
595 template <typename double_container>
596 HashFunction &AppendDoubles(const double_container &doubles)
597 { return EncodeAndHashDoubles(doubles.begin(), doubles.end()); }
598
599 /** @brief Return the hash string for the current sequence and reset (clear)
600 the sequence. */
601 std::string GetHash() const;
602};
603
604
605// implementation
606
607template<typename T>
608HashTable<T>::HashTable(int block_size, int init_hash_size)
609 : Base(block_size)
610{
611 mask = init_hash_size-1;
612 MFEM_VERIFY(!(init_hash_size & mask), "init_size must be a power of two.");
613
614 table = new int[init_hash_size];
615 for (int i = 0; i < init_hash_size; i++)
616 {
617 table[i] = -1;
618 }
619}
620
621template<typename T>
623 : Base(other), mask(other.mask)
624{
625 int size = mask+1;
626 table = new int[size];
627 memcpy(table, other.table, size*sizeof(int));
628 other.unused.Copy(unused);
629}
630
631template<typename T>
633{
634 delete [] table;
635}
636
637namespace internal
638{
639
640inline void sort3(int &a, int &b, int &c)
641{
642 if (a > b) { std::swap(a, b); }
643 if (a > c) { std::swap(a, c); }
644 if (b > c) { std::swap(b, c); }
645}
646
647inline void sort4(int &a, int &b, int &c, int &d)
648{
649 if (a > b) { std::swap(a, b); }
650 if (a > c) { std::swap(a, c); }
651 if (a > d) { std::swap(a, d); }
652 sort3(b, c, d);
653}
654
655inline void sort4_ext(int &a, int &b, int &c, int &d)
656{
657 if (d < 0) // support optional last index
658 {
659 sort3(a, b, c);
660 }
661 else
662 {
663 sort4(a, b, c, d);
664 }
665}
666
667} // internal
668
669template<typename T>
670inline T* HashTable<T>::Get(int p1, int p2)
671{
672 return &(Base::At(GetId(p1, p2)));
673}
674
675template<typename T>
676inline T* HashTable<T>::Get(int p1, int p2, int p3, int p4)
677{
678 return &(Base::At(GetId(p1, p2, p3, p4)));
679}
680
681template<typename T>
682int HashTable<T>::GetId(int p1, int p2)
683{
684 // search for the item in the hashtable
685 if (p1 > p2) { std::swap(p1, p2); }
686 int idx = Hash(p1, p2);
687 int id = SearchList(table[idx], p1, p2);
688 if (id >= 0) { return id; }
689
690 // not found - use an unused item or create a new one
691 int new_id;
692 if (unused.Size())
693 {
694 new_id = unused.Last();
695 unused.DeleteLast();
696 }
697 else
698 {
699 new_id = Base::Append();
700 }
701 T& item = Base::At(new_id);
702 item.p1 = p1;
703 item.p2 = p2;
704
705 // insert into hashtable
706 Insert(idx, new_id, item);
707 CheckRehash();
708
709 return new_id;
710}
711
712template<typename T>
713int HashTable<T>::GetId(int p1, int p2, int p3, int p4)
714{
715 // search for the item in the hashtable
716 internal::sort4_ext(p1, p2, p3, p4);
717 int idx = Hash(p1, p2, p3);
718 int id = SearchList(table[idx], p1, p2, p3);
719 if (id >= 0) { return id; }
720
721 // not found - use an unused item or create a new one
722 int new_id;
723 if (unused.Size())
724 {
725 new_id = unused.Last();
726 unused.DeleteLast();
727 }
728 else
729 {
730 new_id = Base::Append();
731 }
732 T& item = Base::At(new_id);
733 item.p1 = p1;
734 item.p2 = p2;
735 item.p3 = p3;
736
737 // insert into hashtable
738 Insert(idx, new_id, item);
739 CheckRehash();
740
741 return new_id;
742}
743
744template<typename T>
745inline T* HashTable<T>::Find(int p1, int p2)
746{
747 int id = FindId(p1, p2);
748 return (id >= 0) ? &(Base::At(id)) : NULL;
749}
750
751template<typename T>
752inline T* HashTable<T>::Find(int p1, int p2, int p3, int p4)
753{
754 int id = FindId(p1, p2, p3, p4);
755 return (id >= 0) ? &(Base::At(id)) : NULL;
756}
757
758template<typename T>
759inline const T* HashTable<T>::Find(int p1, int p2) const
760{
761 int id = FindId(p1, p2);
762 return (id >= 0) ? &(Base::At(id)) : NULL;
763}
764
765template<typename T>
766inline const T* HashTable<T>::Find(int p1, int p2, int p3, int p4) const
767{
768 int id = FindId(p1, p2, p3, p4);
769 return (id >= 0) ? &(Base::At(id)) : NULL;
770}
771
772template<typename T>
773int HashTable<T>::FindId(int p1, int p2) const
774{
775 if (p1 > p2) { std::swap(p1, p2); }
776 return SearchList(table[Hash(p1, p2)], p1, p2);
777}
778
779template<typename T>
780int HashTable<T>::FindId(int p1, int p2, int p3, int p4) const
781{
782 internal::sort4_ext(p1, p2, p3, p4);
783 return SearchList(table[Hash(p1, p2, p3)], p1, p2, p3);
784}
785
786template<typename T>
787int HashTable<T>::SearchList(int id, int p1, int p2) const
788{
789 while (id >= 0)
790 {
791 const T& item = Base::At(id);
792 if (item.p1 == p1 && item.p2 == p2) { return id; }
793 id = item.next;
794 }
795 return -1;
796}
797
798template<typename T>
799int HashTable<T>::SearchList(int id, int p1, int p2, int p3) const
800{
801 while (id >= 0)
802 {
803 const T& item = Base::At(id);
804 if (item.p1 == p1 && item.p2 == p2 && item.p3 == p3) { return id; }
805 id = item.next;
806 }
807 return -1;
808}
809
810template<typename T>
812{
813 const int fill_factor = 2;
814
815 // is the table overfull?
816 if (Base::Size() > (mask+1) * fill_factor)
817 {
818 DoRehash();
819 }
820}
821
822template<typename T>
824{
825 delete [] table;
826
827 // double the table size
828 int new_table_size = 2*(mask+1);
829 table = new int[new_table_size];
830 for (int i = 0; i < new_table_size; i++) { table[i] = -1; }
831 mask = new_table_size-1;
832
833#if defined(MFEM_DEBUG) && !defined(MFEM_USE_MPI)
834 mfem::out << _MFEM_FUNC_NAME << ": rehashing to size " << new_table_size
835 << std::endl;
836#endif
837
838 // reinsert all items
839 for (iterator it = begin(); it != end(); ++it)
840 {
841 Insert(Hash(*it), it.index(), *it);
842 }
843}
844
845template<typename T>
846inline void HashTable<T>::Insert(int idx, int id, T &item)
847{
848 // add item at the beginning of the linked list
849 item.next = table[idx];
850 table[idx] = id;
851}
852
853template<typename T>
854void HashTable<T>::Unlink(int idx, int id)
855{
856 // remove item from the linked list
857 int* p_id = table + idx;
858 while (*p_id >= 0)
859 {
860 T& item = Base::At(*p_id);
861 if (*p_id == id)
862 {
863 *p_id = item.next;
864 return;
865 }
866 p_id = &(item.next);
867 }
868 MFEM_ABORT("HashTable<>::Unlink: item not found!");
869}
870
871template<typename T>
873{
874 T& item = Base::At(id);
875 Unlink(Hash(item), id);
876 item.next = -2; // mark item as unused
877 unused.Append(id); // add its id to the unused ids
878}
879
880template<typename T>
882{
883 Base::DeleteAll();
884 for (int i = 0; i <= mask; i++) { table[i] = -1; }
885 unused.DeleteAll();
886}
887
888template<typename T>
889void HashTable<T>::Alloc(int id, int p1, int p2)
890{
891 // enlarge the BlockArray to hold 'id'
892 while (id >= Base::Size())
893 {
894 Base::At(Base::Append()).next = -2; // append "unused" items
895 }
896
897 T& item = Base::At(id);
898 if (item.next == -2)
899 {
900 item.next = -1;
901 item.p1 = p1;
902 item.p2 = p2;
903
904 Insert(Hash(p1, p2), id, item);
905 CheckRehash();
906 }
907}
908
909template<typename T>
911{
912 unused.DeleteAll();
913 for (int i = 0; i < Base::Size(); i++)
914 {
915 if (Base::At(i).next == -2) { unused.Append(i); }
916 }
917}
918
919template<typename T>
920void HashTable<T>::Reparent(int id, int new_p1, int new_p2)
921{
922 T& item = Base::At(id);
923 Unlink(Hash(item), id);
924
925 if (new_p1 > new_p2) { std::swap(new_p1, new_p2); }
926 item.p1 = new_p1;
927 item.p2 = new_p2;
928
929 // reinsert under new parent IDs
930 int new_idx = Hash(new_p1, new_p2);
931 Insert(new_idx, id, item);
932}
933
934template<typename T>
936 int new_p1, int new_p2, int new_p3, int new_p4)
937{
938 T& item = Base::At(id);
939 Unlink(Hash(item), id);
940
941 internal::sort4_ext(new_p1, new_p2, new_p3, new_p4);
942 item.p1 = new_p1;
943 item.p2 = new_p2;
944 item.p3 = new_p3;
945
946 // reinsert under new parent IDs
947 int new_idx = Hash(new_p1, new_p2, new_p3);
948 Insert(new_idx, id, item);
949}
950
951template<typename T>
952std::size_t HashTable<T>::MemoryUsage() const
953{
954 return (mask+1) * sizeof(int) + Base::MemoryUsage() + unused.MemoryUsage();
955}
956
957template<typename T>
959{
960 mfem::out << Base::MemoryUsage() << " + " << (mask+1) * sizeof(int)
961 << " + " << unused.MemoryUsage();
962}
963
964template<typename T>
965int HashTable<T>::BinSize(int idx) const
966{
967 int count = 0;
968 int id = table[idx];
969 while (id >= 0)
970 {
971 const T& item = Base::At(id);
972 id = item.next;
973 count++;
974 }
975 return count;
976}
977
978template<typename T>
980{
981 int table_size = mask+1;
982 mfem::out << "Hash table size: " << table_size << "\n";
983 mfem::out << "Item count: " << Size() << "\n";
984 mfem::out << "BlockArray size: " << Base::Size() << "\n";
985
986 const int H = 16;
987 int hist[H];
988
989 for (int i = 0; i < H; i++) { hist[i] = 0; }
990
991 for (int i = 0; i < table_size; i++)
992 {
993 int bs = BinSize(i);
994 if (bs >= H) { bs = H-1; }
995 hist[bs]++;
996 }
997
998 mfem::out << "Bin size histogram:\n";
999 for (int i = 0; i < H; i++)
1000 {
1001 mfem::out << " size " << i << ": "
1002 << hist[i] << " bins" << std::endl;
1003 }
1004}
1005
1006
1007template <typename int_type_const_iter>
1009 int_type_const_iter end)
1010{
1011 // For hashing, an integer k is encoded as follows:
1012 // * 1 byte = sign_bit(k) + num_bytes(k), where
1013 // - sign_bit(k) = (k >= 0) ? 0 : 128
1014 // - num_bytes(k) = minimum number of bytes needed to represent abs(k)
1015 // with the convention that num_bytes(0) = 0.
1016 // * num_bytes(k) bytes = the bytes of abs(k), starting with the least
1017 // significant byte.
1018
1019 static_assert(
1020 std::is_integral<
1021 /**/ typename std::remove_reference<decltype(*begin)>::type
1022 /**/ >::value,
1023 "invalid iterator type");
1024
1025 // Skip encoding if hashing is not available:
1026 if (hash_data == nullptr) { return *this; }
1027
1028 constexpr int max_buffer_bytes = 64*1024;
1029 unsigned char buffer[max_buffer_bytes];
1030 int buffer_counter = 0;
1031 while (begin != end)
1032 {
1033 int byte_counter = 0;
1034 auto k = *begin;
1035 buffer[buffer_counter] = (k >= 0) ? 0 : (k = -k, 128);
1036 while (k != 0)
1037 {
1038 byte_counter++;
1039 buffer[buffer_counter + byte_counter] = (unsigned char)(k % 256);
1040 k /= 256; // (k >>= 8) results in error, e.g. for 'char'
1041 }
1042 buffer[buffer_counter] |= byte_counter;
1043 buffer_counter += (byte_counter + 1);
1044
1045 ++begin;
1046
1047 if (begin == end ||
1048 buffer_counter + (1 + sizeof(*begin)) > max_buffer_bytes)
1049 {
1050 HashBuffer(buffer, buffer_counter);
1051 buffer_counter = 0;
1052 }
1053 }
1054 return *this;
1055}
1056
1057template <typename double_const_iter>
1059 double_const_iter end)
1060{
1061 // For hashing, a double is encoded in little endian byte-order.
1062
1063 static_assert(
1064 std::is_same<decltype(*begin), const real_t &>::value,
1065 "invalid iterator type");
1066
1067 // Skip encoding if hashing is not available:
1068 if (hash_data == nullptr) { return *this; }
1069
1070 constexpr int max_buffer_bytes = 64*1024;
1071 unsigned char buffer[max_buffer_bytes];
1072 int buffer_counter = 0;
1073 while (begin != end)
1074 {
1075 auto k = reinterpret_cast<const uint64_t &>(*begin);
1076 for (int i = 0; i != 7; i++)
1077 {
1078 buffer[buffer_counter++] = (unsigned char)(k & 255); k >>= 8;
1079 }
1080 buffer[buffer_counter++] = (unsigned char)k;
1081
1082 ++begin;
1083
1084 if (begin == end || buffer_counter + 8 > max_buffer_bytes)
1085 {
1086 HashBuffer(buffer, buffer_counter);
1087 buffer_counter = 0;
1088 }
1089 }
1090 return *this;
1091}
1092
1093} // namespace mfem
1094
1095#endif
int Size() const
Return the logical size of the array.
Definition array.hpp:147
void Copy(Array &copy) const
Create a copy of the internal array to the provided copy.
Definition array.hpp:935
iterator begin()
Definition array.hpp:636
T & At(int index)
Access item of the array.
Definition array.hpp:526
const_iterator cbegin() const
Definition array.hpp:641
int Size() const
Return the number of items actually stored.
Definition array.hpp:542
Hash function for data sequences.
Definition hash.hpp:530
HashFunction()
Default constructor: initialize the hash function.
Definition hash.cpp:29
HashFunction & AppendInts(const int_type(&ints)[num_ints])
Add a sequence of integers for hashing, given as a fixed-size c-array.
Definition hash.hpp:569
HashFunction & AppendDoubles(const real_t(&doubles)[num_doubles])
Add a sequence of doubles for hashing, given as a fixed-size c-array.
Definition hash.hpp:589
HashFunction & AppendDoubles(const double_container &doubles)
Add a sequence of doubles for hashing, given as a container.
Definition hash.hpp:596
HashFunction & EncodeAndHashInts(int_type_const_iter begin, int_type_const_iter end)
Integer encoding method; result is independent of endianness and type.
Definition hash.hpp:1008
HashFunction & EncodeAndHashDoubles(double_const_iter begin, double_const_iter end)
Double encoding method: encode in little-endian byte-order.
Definition hash.hpp:1058
std::string GetHash() const
Return the hash string for the current sequence and reset (clear) the sequence.
Definition hash.cpp:60
~HashFunction()
Destructor.
Definition hash.cpp:38
HashFunction & AppendBytes(const void *seq, size_t num_bytes)
Add a sequence of bytes for hashing.
Definition hash.hpp:555
HashFunction & AppendDoubles(const real_t *doubles, size_t num_doubles)
Add a sequence of doubles for hashing, given as a c-array.
Definition hash.hpp:582
HashFunction & AppendInts(const int_type *ints, size_t num_ints)
Add a sequence of integers for hashing, given as a c-array.
Definition hash.hpp:562
HashFunction & AppendInts(const int_type_container &ints)
Add a sequence of integers for hashing, given as a container.
Definition hash.hpp:576
void HashBuffer(const void *buffer, size_t num_bytes)
Add a sequence of bytes for hashing.
Definition hash.cpp:45
Base::const_iterator base
Definition hash.hpp:323
const_iterator(const base &it)
Definition hash.hpp:326
const_iterator & operator++()
Definition hash.hpp:332
iterator(const base &it)
Definition hash.hpp:306
Base::iterator base
Definition hash.hpp:303
iterator & operator++()
Definition hash.hpp:312
void Reparent(int id, int new_p1, int new_p2, int new_p3, int new_p4=-1)
Change the key associated with an item.
Definition hash.hpp:935
const_iterator end() const
Definition hash.hpp:342
T * Get(int p1, int p2)
Item accessor with key (or parents) the pair 'p1', 'p2'. Default construct an item of type T if no va...
Definition hash.hpp:670
void PrintMemoryDetail() const
Write details of the memory usage to the mfem output stream.
Definition hash.hpp:958
int Hash(const Hashed4 &item) const
Hash function for items of type T that inherit from Hashed4.
Definition hash.hpp:392
void DeleteAll()
Remove all items.
Definition hash.hpp:881
T * Find(int p1, int p2)
Find item whose parents are p1, p2... Return NULL if it doesn't exist.
Definition hash.hpp:745
bool IdExists(int id) const
Return true if item 'id' exists in (is used by) the container.
Definition hash.hpp:238
int Hash(size_t p1, size_t p2, size_t p3) const
hash function for Hashed4 items.
Definition hash.hpp:383
iterator begin()
Definition hash.hpp:339
HashTable(int block_size=16 *1024, int init_hash_size=32 *1024)
Main constructor of the HashTable class.
Definition hash.hpp:608
void Reparent(int id, int new_p1, int new_p2)
Change the key associated with an item.
Definition hash.hpp:920
BlockArray< T > Base
Definition hash.hpp:88
T * Get(int p1, int p2, int p3, int p4=-1)
Item accessor with key (or parents) the quadruplet 'p1', 'p2', 'p3', 'p4'. The key 'p4' is optional....
Definition hash.hpp:676
int Hash(size_t p1, size_t p2) const
hash function for Hashed2 items.
Definition hash.hpp:370
const_iterator begin() const
Definition hash.hpp:341
void Insert(int idx, int id, T &item)
Insert the item 'id' into bin 'idx'.
Definition hash.hpp:846
int FindId(int p1, int p2, int p3, int p4=-1) const
Find the "id" of an item, this "id" corresponding to the index of the item in the underlying BlockArr...
Definition hash.hpp:780
int SearchList(int id, int p1, int p2) const
Search the index of the item associated to the key (p1,p2) starting from the item with index id.
Definition hash.hpp:787
int GetId(int p1, int p2)
Get id of item whose parents are p1, p2... Create it if it doesn't exist.
Definition hash.hpp:682
void CheckRehash()
Check table fill factor and resize if necessary.
Definition hash.hpp:811
int NumIds() const
Return the total number of ids (used and unused) in the HashTable.
Definition hash.hpp:228
const T * Find(int p1, int p2, int p3, int p4=-1) const
Item const accessor with key (or parents) the quadruplet 'p1', 'p2', 'p3', 'p4'. The key 'p4' is opti...
Definition hash.hpp:766
int SearchList(int id, int p1, int p2, int p3) const
Search the index of the item associated to the key (p1,p2,p3,(p4)) starting from the item with index ...
Definition hash.hpp:799
iterator end()
Definition hash.hpp:340
int Hash(const Hashed2 &item) const
Hash function for items of type T that inherit from Hashed2.
Definition hash.hpp:388
int GetId(int p1, int p2, int p3, int p4=-1)
Get the "id" of an item, this "id" corresponding to the index of the item in the underlying BlockArra...
Definition hash.hpp:713
void Delete(int id)
Remove an item from the hash table.
Definition hash.hpp:872
HashTable(const HashTable &other)
Deep copy.
Definition hash.hpp:622
int BinSize(int idx) const
Return the size of the bin "idx".
Definition hash.hpp:965
int FindId(int p1, int p2) const
Find id of item whose parents are p1, p2... Return -1 if it doesn't exist.
Definition hash.hpp:773
Array< int > unused
Definition hash.hpp:360
void DoRehash()
Double the size of the hash table (i.e., double the number of bins) and reinsert all items into the n...
Definition hash.hpp:823
T * Find(int p1, int p2, int p3, int p4=-1)
Item accessor with key (or parents) the quadruplet 'p1', 'p2', 'p3', 'p4'. The key 'p4' is optional....
Definition hash.hpp:752
void Alloc(int id, int p1, int p2)
Allocate an item at 'id'. Enlarge the underlying BlockArray if necessary.
Definition hash.hpp:889
const_iterator cend() const
Definition hash.hpp:345
int Size() const
Return the number of elements currently stored in the HashTable.
Definition hash.hpp:225
void Unlink(int idx, int id)
Unlink an item id from the linked list of bin idx.
Definition hash.hpp:854
const T * Find(int p1, int p2) const
Item const accessor with key (or parents) the pair 'p1', 'p2'. Return nullptr if no value correspond ...
Definition hash.hpp:759
void UpdateUnused()
Reinitialize the internal list of unallocated items.
Definition hash.hpp:910
const_iterator cbegin() const
Definition hash.hpp:344
int NumFreeIds() const
Return the number of free/unused ids in the HashTable.
Definition hash.hpp:231
void PrintStats() const
Print a histogram of bin sizes for debugging purposes.
Definition hash.hpp:979
HashTable & operator=(const HashTable &)=delete
Copy assignment not supported.
std::size_t MemoryUsage() const
Return total size of allocated memory (tables plus items), in bytes.
Definition hash.hpp:952
real_t b
Definition lissajous.cpp:42
real_t a
Definition lissajous.cpp:41
OutStream out(std::cout)
Global stream used by the library for standard output. Initially it uses the same std::streambuf as s...
Definition globals.hpp:66
float real_t
Definition config.hpp:43
Helper class for hashing std::array. Usable in place of std::hash<std::array<T,N>>
Definition hash.hpp:511
size_t operator()(const std::array< T, N > &v) const noexcept
Definition hash.hpp:513
streaming implementation for murmurhash3 128 (x64). Constructs the hash in 3 stages: init,...
Definition hash.hpp:463
void init(uint64_t seed=0)
resets this hasher back to an initial seed
Definition hash.cpp:88
uint64_t data[2]
Definition hash.hpp:466
void finalize()
Definition hash.cpp:158
void append(const uint8_t *vs, uint64_t bytes)
Definition hash.cpp:131
Helper class for hashing std::pair. Usable in place of std::hash<std::pair<T,U>>
Definition hash.hpp:495
size_t operator()(const std::pair< T, V > &v) const noexcept
Definition hash.hpp:497