97 HashTable(
int block_size = 16*1024,
int init_hash_size = 32*1024);
125 T*
Get(
int p1,
int p2,
int p3,
int p4 = -1 );
150 int GetId(
int p1,
int p2,
int p3,
int p4 = -1);
174 T*
Find(
int p1,
int p2,
int p3,
int p4 = -1);
184 const T*
Find(
int p1,
int p2)
const;
197 const T*
Find(
int p1,
int p2,
int p3,
int p4 = -1)
const;
222 int FindId(
int p1,
int p2,
int p3,
int p4 = -1)
const;
288 void Reparent(
int id,
int new_p1,
int new_p2,
int new_p3,
int new_p4 = -1);
370 inline int Hash(
size_t p1,
size_t p2)
const
371 {
return (984120265ul*p1 + 125965121ul*p2) &
mask; }
383 inline int Hash(
size_t p1,
size_t p2,
size_t p3)
const
384 {
return (984120265ul*p1 + 125965121ul*p2 + 495698413ul*p3) &
mask; }
427 inline void Insert(
int idx,
int id, T &item);
471 uint64_t buf_[2] = {0, 0};
476 void init(uint64_t seed = 0);
477 void append(
const uint8_t *vs, uint64_t bytes);
483 void add_block(uint64_t k1, uint64_t k2);
486 void finalize(uint64_t k1,
int num);
490 void finalize(uint64_t k1, uint64_t k2,
int num);
496 template <
class T,
class V>
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));
512 template <
class T,
size_t N>
517 hash.
init(0xfebd1fe69813c14full);
518 for (
size_t i = 0; i < N; ++i)
520 hash.
append(
reinterpret_cast<const uint8_t *
>(&v[i]),
sizeof(T));
535 void HashBuffer(
const void *buffer,
size_t num_bytes);
538 template <
typename int_type_const_iter>
540 int_type_const_iter end);
543 template <
typename double_const_iter>
545 double_const_iter end);
561 template <
typename int_type>
568 template <
typename int_type,
size_t num_
ints>
575 template <
typename int_type_container>
588 template <
size_t num_
doubles>
595 template <
typename double_container>
611 mask = init_hash_size-1;
612 MFEM_VERIFY(!(init_hash_size &
mask),
"init_size must be a power of two.");
614 table =
new int[init_hash_size];
615 for (
int i = 0; i < init_hash_size; i++)
623 :
Base(other), mask(other.mask)
640inline void sort3(
int &
a,
int &
b,
int &c)
642 if (
a >
b) { std::swap(
a,
b); }
643 if (
a > c) { std::swap(
a, c); }
644 if (
b > c) { std::swap(
b, c); }
647inline void sort4(
int &
a,
int &
b,
int &c,
int &d)
649 if (
a >
b) { std::swap(
a,
b); }
650 if (
a > c) { std::swap(
a, c); }
651 if (
a > d) { std::swap(
a, d); }
655inline void sort4_ext(
int &
a,
int &
b,
int &c,
int &d)
672 return &(Base::At(GetId(p1, p2)));
678 return &(Base::At(GetId(p1, p2, p3, p4)));
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; }
694 new_id = unused.Last();
699 new_id = Base::Append();
701 T& item = Base::At(new_id);
706 Insert(idx, new_id, item);
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; }
725 new_id = unused.Last();
730 new_id = Base::Append();
732 T& item = Base::At(new_id);
738 Insert(idx, new_id, item);
747 int id = FindId(p1, p2);
748 return (
id >= 0) ? &(Base::At(
id)) : NULL;
754 int id = FindId(p1, p2, p3, p4);
755 return (
id >= 0) ? &(Base::At(
id)) : NULL;
761 int id = FindId(p1, p2);
762 return (
id >= 0) ? &(Base::At(
id)) : NULL;
768 int id = FindId(p1, p2, p3, p4);
769 return (
id >= 0) ? &(Base::At(
id)) : NULL;
775 if (p1 > p2) { std::swap(p1, p2); }
776 return SearchList(table[Hash(p1, p2)], p1, p2);
782 internal::sort4_ext(p1, p2, p3, p4);
783 return SearchList(table[Hash(p1, p2, p3)], p1, p2, p3);
791 const T& item = Base::At(
id);
792 if (item.p1 == p1 && item.p2 == p2) {
return id; }
803 const T& item = Base::At(
id);
804 if (item.p1 == p1 && item.p2 == p2 && item.p3 == p3) {
return id; }
813 const int fill_factor = 2;
816 if (Base::Size() > (mask+1) * fill_factor)
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;
833#if defined(MFEM_DEBUG) && !defined(MFEM_USE_MPI)
834 mfem::out << _MFEM_FUNC_NAME <<
": rehashing to size " << new_table_size
839 for (
iterator it = begin(); it != end(); ++it)
841 Insert(Hash(*it), it.index(), *it);
849 item.next = table[idx];
857 int* p_id = table + idx;
860 T& item = Base::At(*p_id);
868 MFEM_ABORT(
"HashTable<>::Unlink: item not found!");
874 T& item = Base::At(
id);
875 Unlink(Hash(item),
id);
884 for (
int i = 0; i <= mask; i++) { table[i] = -1; }
892 while (
id >= Base::Size())
894 Base::At(Base::Append()).next = -2;
897 T& item = Base::At(
id);
904 Insert(Hash(p1, p2),
id, item);
913 for (
int i = 0; i < Base::Size(); i++)
915 if (Base::At(i).next == -2) { unused.Append(i); }
922 T& item = Base::At(
id);
923 Unlink(Hash(item),
id);
925 if (new_p1 > new_p2) { std::swap(new_p1, new_p2); }
930 int new_idx = Hash(new_p1, new_p2);
931 Insert(new_idx,
id, item);
936 int new_p1,
int new_p2,
int new_p3,
int new_p4)
938 T& item = Base::At(
id);
939 Unlink(Hash(item),
id);
941 internal::sort4_ext(new_p1, new_p2, new_p3, new_p4);
947 int new_idx = Hash(new_p1, new_p2, new_p3);
948 Insert(new_idx,
id, item);
954 return (mask+1) *
sizeof(int) + Base::MemoryUsage() + unused.MemoryUsage();
960 mfem::out << Base::MemoryUsage() <<
" + " << (mask+1) *
sizeof(
int)
961 <<
" + " << unused.MemoryUsage();
971 const T& item = Base::At(
id);
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";
989 for (
int i = 0; i < H; i++) { hist[i] = 0; }
991 for (
int i = 0; i < table_size; i++)
994 if (bs >= H) { bs = H-1; }
999 for (
int i = 0; i < H; i++)
1002 << hist[i] <<
" bins" << std::endl;
1007template <
typename int_type_const_iter>
1009 int_type_const_iter end)
1021 typename std::remove_reference<
decltype(*begin)>::type
1023 "invalid iterator type");
1026 if (
hash_data ==
nullptr) {
return *
this; }
1028 constexpr int max_buffer_bytes = 64*1024;
1029 unsigned char buffer[max_buffer_bytes];
1030 int buffer_counter = 0;
1031 while (begin != end)
1033 int byte_counter = 0;
1035 buffer[buffer_counter] = (k >= 0) ? 0 : (k = -k, 128);
1039 buffer[buffer_counter + byte_counter] = (
unsigned char)(k % 256);
1042 buffer[buffer_counter] |= byte_counter;
1043 buffer_counter += (byte_counter + 1);
1048 buffer_counter + (1 +
sizeof(*begin)) > max_buffer_bytes)
1057template <
typename double_const_iter>
1059 double_const_iter end)
1064 std::is_same<
decltype(*begin),
const real_t &>::value,
1065 "invalid iterator type");
1068 if (
hash_data ==
nullptr) {
return *
this; }
1070 constexpr int max_buffer_bytes = 64*1024;
1071 unsigned char buffer[max_buffer_bytes];
1072 int buffer_counter = 0;
1073 while (begin != end)
1075 auto k =
reinterpret_cast<const uint64_t &
>(*begin);
1076 for (
int i = 0; i != 7; i++)
1078 buffer[buffer_counter++] = (
unsigned char)(k & 255); k >>= 8;
1080 buffer[buffer_counter++] = (
unsigned char)k;
1084 if (begin == end || buffer_counter + 8 > max_buffer_bytes)
int Size() const
Return the logical size of the array.
void Copy(Array ©) const
Create a copy of the internal array to the provided copy.
T & At(int index)
Access item of the array.
const_iterator cbegin() const
int Size() const
Return the number of items actually stored.
Hash function for data sequences.
HashFunction()
Default constructor: initialize the hash function.
HashFunction & AppendInts(const int_type(&ints)[num_ints])
Add a sequence of integers for hashing, given as a fixed-size c-array.
HashFunction & AppendDoubles(const real_t(&doubles)[num_doubles])
Add a sequence of doubles for hashing, given as a fixed-size c-array.
HashFunction & AppendDoubles(const double_container &doubles)
Add a sequence of doubles for hashing, given as a container.
HashFunction & EncodeAndHashInts(int_type_const_iter begin, int_type_const_iter end)
Integer encoding method; result is independent of endianness and type.
HashFunction & EncodeAndHashDoubles(double_const_iter begin, double_const_iter end)
Double encoding method: encode in little-endian byte-order.
std::string GetHash() const
Return the hash string for the current sequence and reset (clear) the sequence.
~HashFunction()
Destructor.
HashFunction & AppendBytes(const void *seq, size_t num_bytes)
Add a sequence of bytes for hashing.
HashFunction & AppendDoubles(const real_t *doubles, size_t num_doubles)
Add a sequence of doubles for hashing, given as a c-array.
HashFunction & AppendInts(const int_type *ints, size_t num_ints)
Add a sequence of integers for hashing, given as a c-array.
HashFunction & AppendInts(const int_type_container &ints)
Add a sequence of integers for hashing, given as a container.
void HashBuffer(const void *buffer, size_t num_bytes)
Add a sequence of bytes for hashing.
Base::const_iterator base
const_iterator(const base &it)
const_iterator & operator++()
void Reparent(int id, int new_p1, int new_p2, int new_p3, int new_p4=-1)
Change the key associated with an item.
const_iterator end() const
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...
void PrintMemoryDetail() const
Write details of the memory usage to the mfem output stream.
int Hash(const Hashed4 &item) const
Hash function for items of type T that inherit from Hashed4.
void DeleteAll()
Remove all items.
T * Find(int p1, int p2)
Find item whose parents are p1, p2... Return NULL if it doesn't exist.
bool IdExists(int id) const
Return true if item 'id' exists in (is used by) the container.
int Hash(size_t p1, size_t p2, size_t p3) const
hash function for Hashed4 items.
HashTable(int block_size=16 *1024, int init_hash_size=32 *1024)
Main constructor of the HashTable class.
void Reparent(int id, int new_p1, int new_p2)
Change the key associated with an item.
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....
int Hash(size_t p1, size_t p2) const
hash function for Hashed2 items.
const_iterator begin() const
void Insert(int idx, int id, T &item)
Insert the item 'id' into bin 'idx'.
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...
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.
int GetId(int p1, int p2)
Get id of item whose parents are p1, p2... Create it if it doesn't exist.
void CheckRehash()
Check table fill factor and resize if necessary.
int NumIds() const
Return the total number of ids (used and unused) in the HashTable.
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...
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 ...
int Hash(const Hashed2 &item) const
Hash function for items of type T that inherit from Hashed2.
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...
void Delete(int id)
Remove an item from the hash table.
HashTable(const HashTable &other)
Deep copy.
int BinSize(int idx) const
Return the size of the bin "idx".
int FindId(int p1, int p2) const
Find id of item whose parents are p1, p2... Return -1 if it doesn't exist.
void DoRehash()
Double the size of the hash table (i.e., double the number of bins) and reinsert all items into the n...
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....
void Alloc(int id, int p1, int p2)
Allocate an item at 'id'. Enlarge the underlying BlockArray if necessary.
const_iterator cend() const
int Size() const
Return the number of elements currently stored in the HashTable.
void Unlink(int idx, int id)
Unlink an item id from the linked list of bin idx.
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 ...
void UpdateUnused()
Reinitialize the internal list of unallocated items.
const_iterator cbegin() const
int NumFreeIds() const
Return the number of free/unused ids in the HashTable.
void PrintStats() const
Print a histogram of bin sizes for debugging purposes.
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.
OutStream out(std::cout)
Global stream used by the library for standard output. Initially it uses the same std::streambuf as s...
Helper class for hashing std::array. Usable in place of std::hash<std::array<T,N>>
size_t operator()(const std::array< T, N > &v) const noexcept
streaming implementation for murmurhash3 128 (x64). Constructs the hash in 3 stages: init,...
void init(uint64_t seed=0)
resets this hasher back to an initial seed
void append(const uint8_t *vs, uint64_t bytes)
Helper class for hashing std::pair. Usable in place of std::hash<std::pair<T,U>>
size_t operator()(const std::pair< T, V > &v) const noexcept