HashTable.h 24 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854
  1. // Jolt Physics Library (https://github.com/jrouwe/JoltPhysics)
  2. // SPDX-FileCopyrightText: 2024 Jorrit Rouwe
  3. // SPDX-License-Identifier: MIT
  4. #pragma once
  5. #include <Jolt/Math/BVec16.h>
  6. JPH_NAMESPACE_BEGIN
  7. /// Helper class for implementing an UnorderedSet or UnorderedMap
  8. /// Based on CppCon 2017: Matt Kulukundis "Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step"
  9. /// See: https://www.youtube.com/watch?v=ncHmEUmJZf4
  10. template <class Key, class KeyValue, class HashTableDetail, class Hash, class KeyEqual>
  11. class HashTable
  12. {
  13. public:
  14. /// Properties
  15. using value_type = KeyValue;
  16. using size_type = uint32;
  17. using difference_type = ptrdiff_t;
  18. private:
  19. /// Base class for iterators
  20. template <class Table, class Iterator>
  21. class IteratorBase
  22. {
  23. public:
  24. /// Properties
  25. using difference_type = typename Table::difference_type;
  26. using value_type = typename Table::value_type;
  27. using iterator_category = std::forward_iterator_tag;
  28. /// Copy constructor
  29. IteratorBase(const IteratorBase &inRHS) = default;
  30. /// Assignment operator
  31. IteratorBase & operator = (const IteratorBase &inRHS) = default;
  32. /// Iterator at start of table
  33. explicit IteratorBase(Table *inTable) :
  34. mTable(inTable),
  35. mIndex(0)
  36. {
  37. while (mIndex < mTable->mMaxSize && (mTable->mControl[mIndex] & cBucketUsed) == 0)
  38. ++mIndex;
  39. }
  40. /// Iterator at specific index
  41. IteratorBase(Table *inTable, size_type inIndex) :
  42. mTable(inTable),
  43. mIndex(inIndex)
  44. {
  45. }
  46. /// Prefix increment
  47. Iterator & operator ++ ()
  48. {
  49. JPH_ASSERT(IsValid());
  50. do
  51. {
  52. ++mIndex;
  53. }
  54. while (mIndex < mTable->mMaxSize && (mTable->mControl[mIndex] & cBucketUsed) == 0);
  55. return static_cast<Iterator &>(*this);
  56. }
  57. /// Postfix increment
  58. Iterator operator ++ (int)
  59. {
  60. Iterator result(mTable, mIndex);
  61. ++(*this);
  62. return result;
  63. }
  64. /// Access to key value pair
  65. const KeyValue & operator * () const
  66. {
  67. JPH_ASSERT(IsValid());
  68. return mTable->mData[mIndex];
  69. }
  70. /// Access to key value pair
  71. const KeyValue * operator -> () const
  72. {
  73. JPH_ASSERT(IsValid());
  74. return mTable->mData + mIndex;
  75. }
  76. /// Equality operator
  77. bool operator == (const Iterator &inRHS) const
  78. {
  79. return mIndex == inRHS.mIndex && mTable == inRHS.mTable;
  80. }
  81. /// Inequality operator
  82. bool operator != (const Iterator &inRHS) const
  83. {
  84. return !(*this == inRHS);
  85. }
  86. /// Check that the iterator is valid
  87. bool IsValid() const
  88. {
  89. return mIndex < mTable->mMaxSize
  90. && (mTable->mControl[mIndex] & cBucketUsed) != 0;
  91. }
  92. Table * mTable;
  93. size_type mIndex;
  94. };
  95. /// Get the maximum number of elements that we can support given a number of buckets
  96. static constexpr size_type sGetMaxLoad(size_type inBucketCount)
  97. {
  98. return uint32((cMaxLoadFactorNumerator * inBucketCount) / cMaxLoadFactorDenominator);
  99. }
  100. /// Update the control value for a bucket
  101. JPH_INLINE void SetControlValue(size_type inIndex, uint8 inValue)
  102. {
  103. JPH_ASSERT(inIndex < mMaxSize);
  104. mControl[inIndex] = inValue;
  105. // Mirror the first 15 bytes to the 15 bytes beyond mMaxSize
  106. // Note that this is equivalent to:
  107. // if (inIndex < 15)
  108. // mControl[inIndex + mMaxSize] = inValue
  109. // else
  110. // mControl[inIndex] = inValue
  111. // Which performs a needless write if inIndex >= 15 but at least it is branch-less
  112. mControl[((inIndex - 15) & (mMaxSize - 1)) + 15] = inValue;
  113. }
  114. /// Get the index and control value for a particular key
  115. JPH_INLINE void GetIndexAndControlValue(const Key &inKey, size_type &outIndex, uint8 &outControl) const
  116. {
  117. // Calculate hash
  118. uint64 hash_value = Hash { } (inKey);
  119. // Split hash into index and control value
  120. outIndex = size_type(hash_value >> 7) & (mMaxSize - 1);
  121. outControl = cBucketUsed | uint8(hash_value);
  122. }
  123. /// Allocate space for the hash table
  124. void AllocateTable(size_type inMaxSize)
  125. {
  126. JPH_ASSERT(mData == nullptr);
  127. mMaxSize = inMaxSize;
  128. mLoadLeft = sGetMaxLoad(inMaxSize);
  129. size_t required_size = size_t(mMaxSize) * (sizeof(KeyValue) + 1) + 15; // Add 15 bytes to mirror the first 15 bytes of the control values
  130. if constexpr (cNeedsAlignedAllocate)
  131. mData = reinterpret_cast<KeyValue *>(AlignedAllocate(required_size, alignof(KeyValue)));
  132. else
  133. mData = reinterpret_cast<KeyValue *>(Allocate(required_size));
  134. mControl = reinterpret_cast<uint8 *>(mData + mMaxSize);
  135. }
  136. /// Copy the contents of another hash table
  137. void CopyTable(const HashTable &inRHS)
  138. {
  139. if (inRHS.empty())
  140. return;
  141. AllocateTable(inRHS.mMaxSize);
  142. // Copy control bytes
  143. memcpy(mControl, inRHS.mControl, mMaxSize + 15);
  144. // Copy elements
  145. uint index = 0;
  146. for (const uint8 *control = mControl, *control_end = mControl + mMaxSize; control != control_end; ++control, ++index)
  147. if (*control & cBucketUsed)
  148. new (mData + index) KeyValue(inRHS.mData[index]);
  149. mSize = inRHS.mSize;
  150. }
  151. /// Grow the table to the next power of 2
  152. void GrowTable()
  153. {
  154. // Calculate new size
  155. size_type new_max_size = max<size_type>(mMaxSize << 1, 16);
  156. if (new_max_size < mMaxSize)
  157. {
  158. JPH_ASSERT(false, "Overflow in hash table size, can't grow!");
  159. return;
  160. }
  161. // Move the old table to a temporary structure
  162. size_type old_max_size = mMaxSize;
  163. KeyValue *old_data = mData;
  164. const uint8 *old_control = mControl;
  165. mData = nullptr;
  166. mControl = nullptr;
  167. mSize = 0;
  168. mMaxSize = 0;
  169. mLoadLeft = 0;
  170. // Allocate new table
  171. AllocateTable(new_max_size);
  172. // Reset all control bytes
  173. memset(mControl, cBucketEmpty, mMaxSize + 15);
  174. if (old_data != nullptr)
  175. {
  176. // Copy all elements from the old table
  177. for (size_type i = 0; i < old_max_size; ++i)
  178. if (old_control[i] & cBucketUsed)
  179. {
  180. size_type index;
  181. KeyValue *element = old_data + i;
  182. JPH_IF_ENABLE_ASSERTS(bool inserted =) InsertKey</* InsertAfterGrow= */ true>(HashTableDetail::sGetKey(*element), index);
  183. JPH_ASSERT(inserted);
  184. new (mData + index) KeyValue(std::move(*element));
  185. element->~KeyValue();
  186. }
  187. // Free memory
  188. if constexpr (cNeedsAlignedAllocate)
  189. AlignedFree(old_data);
  190. else
  191. Free(old_data);
  192. }
  193. }
  194. protected:
  195. /// Get an element by index
  196. KeyValue & GetElement(size_type inIndex) const
  197. {
  198. return mData[inIndex];
  199. }
  200. /// Insert a key into the map, returns true if the element was inserted, false if it already existed.
  201. /// outIndex is the index at which the element should be constructed / where it is located.
  202. template <bool InsertAfterGrow = false>
  203. bool InsertKey(const Key &inKey, size_type &outIndex)
  204. {
  205. // Ensure we have enough space
  206. if (mLoadLeft == 0)
  207. {
  208. // Should not be growing if we're already growing!
  209. if constexpr (InsertAfterGrow)
  210. JPH_ASSERT(false);
  211. // Decide if we need to clean up all tombstones or if we need to grow the map
  212. size_type num_deleted = sGetMaxLoad(mMaxSize) - mSize;
  213. if (num_deleted * cMaxDeletedElementsDenominator > mMaxSize * cMaxDeletedElementsNumerator)
  214. rehash(0);
  215. else
  216. GrowTable();
  217. }
  218. // Split hash into index and control value
  219. size_type index;
  220. uint8 control;
  221. GetIndexAndControlValue(inKey, index, control);
  222. // Keeps track of the index of the first deleted bucket we found
  223. constexpr size_type cNoDeleted = ~size_type(0);
  224. size_type first_deleted_index = cNoDeleted;
  225. // Linear probing
  226. KeyEqual equal;
  227. size_type bucket_mask = mMaxSize - 1;
  228. BVec16 control16 = BVec16::sReplicate(control);
  229. BVec16 bucket_empty = BVec16::sZero();
  230. BVec16 bucket_deleted = BVec16::sReplicate(cBucketDeleted);
  231. for (;;)
  232. {
  233. // Read 16 control values (note that we added 15 bytes at the end of the control values that mirror the first 15 bytes)
  234. BVec16 control_bytes = BVec16::sLoadByte16(mControl + index);
  235. // Check if we must find the element before we can insert
  236. if constexpr (!InsertAfterGrow)
  237. {
  238. // Check for the control value we're looking for
  239. // Note that when deleting we can create empty buckets instead of deleted buckets.
  240. // This means we must unconditionally check all buckets in this batch for equality
  241. // (also beyond the first empty bucket).
  242. uint32 control_equal = uint32(BVec16::sEquals(control_bytes, control16).GetTrues());
  243. // Index within the 16 buckets
  244. size_type local_index = index;
  245. // Loop while there's still buckets to process
  246. while (control_equal != 0)
  247. {
  248. // Get the first equal bucket
  249. uint first_equal = CountTrailingZeros(control_equal);
  250. // Skip to the bucket
  251. local_index += first_equal;
  252. // Make sure that our index is not beyond the end of the table
  253. local_index &= bucket_mask;
  254. // We found a bucket with same control value
  255. if (equal(HashTableDetail::sGetKey(mData[local_index]), inKey))
  256. {
  257. // Element already exists
  258. outIndex = local_index;
  259. return false;
  260. }
  261. // Skip past this bucket
  262. control_equal >>= first_equal + 1;
  263. local_index++;
  264. }
  265. // Check if we're still scanning for deleted buckets
  266. if (first_deleted_index == cNoDeleted)
  267. {
  268. // Check if any buckets have been deleted, if so store the first one
  269. uint32 control_deleted = uint32(BVec16::sEquals(control_bytes, bucket_deleted).GetTrues());
  270. if (control_deleted != 0)
  271. first_deleted_index = index + CountTrailingZeros(control_deleted);
  272. }
  273. }
  274. // Check for empty buckets
  275. uint32 control_empty = uint32(BVec16::sEquals(control_bytes, bucket_empty).GetTrues());
  276. if (control_empty != 0)
  277. {
  278. // If we found a deleted bucket, use it.
  279. // It doesn't matter if it is before or after the first empty bucket we found
  280. // since we will always be scanning in batches of 16 buckets.
  281. if (first_deleted_index == cNoDeleted || InsertAfterGrow)
  282. {
  283. index += CountTrailingZeros(control_empty);
  284. --mLoadLeft; // Using an empty bucket decreases the load left
  285. }
  286. else
  287. {
  288. index = first_deleted_index;
  289. }
  290. // Make sure that our index is not beyond the end of the table
  291. index &= bucket_mask;
  292. // Update control byte
  293. SetControlValue(index, control);
  294. ++mSize;
  295. // Return index to newly allocated bucket
  296. outIndex = index;
  297. return true;
  298. }
  299. // Move to next batch of 16 buckets
  300. index = (index + 16) & bucket_mask;
  301. }
  302. }
  303. public:
  304. /// Non-const iterator
  305. class iterator : public IteratorBase<HashTable, iterator>
  306. {
  307. using Base = IteratorBase<HashTable, iterator>;
  308. public:
  309. /// Properties
  310. using reference = typename Base::value_type &;
  311. using pointer = typename Base::value_type *;
  312. /// Constructors
  313. explicit iterator(HashTable *inTable) : Base(inTable) { }
  314. iterator(HashTable *inTable, size_type inIndex) : Base(inTable, inIndex) { }
  315. iterator(const iterator &inIterator) : Base(inIterator) { }
  316. /// Assignment
  317. iterator & operator = (const iterator &inRHS) { Base::operator = (inRHS); return *this; }
  318. using Base::operator *;
  319. /// Non-const access to key value pair
  320. KeyValue & operator * ()
  321. {
  322. JPH_ASSERT(this->IsValid());
  323. return this->mTable->mData[this->mIndex];
  324. }
  325. using Base::operator ->;
  326. /// Non-const access to key value pair
  327. KeyValue * operator -> ()
  328. {
  329. JPH_ASSERT(this->IsValid());
  330. return this->mTable->mData + this->mIndex;
  331. }
  332. };
  333. /// Const iterator
  334. class const_iterator : public IteratorBase<const HashTable, const_iterator>
  335. {
  336. using Base = IteratorBase<const HashTable, const_iterator>;
  337. public:
  338. /// Properties
  339. using reference = const typename Base::value_type &;
  340. using pointer = const typename Base::value_type *;
  341. /// Constructors
  342. explicit const_iterator(const HashTable *inTable) : Base(inTable) { }
  343. const_iterator(const HashTable *inTable, size_type inIndex) : Base(inTable, inIndex) { }
  344. const_iterator(const const_iterator &inRHS) : Base(inRHS) { }
  345. const_iterator(const iterator &inIterator) : Base(inIterator.mTable, inIterator.mIndex) { }
  346. /// Assignment
  347. const_iterator & operator = (const iterator &inRHS) { this->mTable = inRHS.mTable; this->mIndex = inRHS.mIndex; return *this; }
  348. const_iterator & operator = (const const_iterator &inRHS) { Base::operator = (inRHS); return *this; }
  349. };
  350. /// Default constructor
  351. HashTable() = default;
  352. /// Copy constructor
  353. HashTable(const HashTable &inRHS)
  354. {
  355. CopyTable(inRHS);
  356. }
  357. /// Move constructor
  358. HashTable(HashTable &&ioRHS) noexcept :
  359. mData(ioRHS.mData),
  360. mControl(ioRHS.mControl),
  361. mSize(ioRHS.mSize),
  362. mMaxSize(ioRHS.mMaxSize),
  363. mLoadLeft(ioRHS.mLoadLeft)
  364. {
  365. ioRHS.mData = nullptr;
  366. ioRHS.mControl = nullptr;
  367. ioRHS.mSize = 0;
  368. ioRHS.mMaxSize = 0;
  369. ioRHS.mLoadLeft = 0;
  370. }
  371. /// Assignment operator
  372. HashTable & operator = (const HashTable &inRHS)
  373. {
  374. if (this != &inRHS)
  375. {
  376. clear();
  377. CopyTable(inRHS);
  378. }
  379. return *this;
  380. }
  381. /// Move assignment operator
  382. HashTable & operator = (HashTable &&ioRHS) noexcept
  383. {
  384. if (this != &ioRHS)
  385. {
  386. clear();
  387. mData = ioRHS.mData;
  388. mControl = ioRHS.mControl;
  389. mSize = ioRHS.mSize;
  390. mMaxSize = ioRHS.mMaxSize;
  391. mLoadLeft = ioRHS.mLoadLeft;
  392. ioRHS.mData = nullptr;
  393. ioRHS.mControl = nullptr;
  394. ioRHS.mSize = 0;
  395. ioRHS.mMaxSize = 0;
  396. ioRHS.mLoadLeft = 0;
  397. }
  398. return *this;
  399. }
  400. /// Destructor
  401. ~HashTable()
  402. {
  403. clear();
  404. }
  405. /// Reserve memory for a certain number of elements
  406. void reserve(size_type inMaxSize)
  407. {
  408. // Calculate max size based on load factor
  409. size_type max_size = GetNextPowerOf2(max<uint32>((cMaxLoadFactorDenominator * inMaxSize) / cMaxLoadFactorNumerator, 16));
  410. if (max_size <= mMaxSize)
  411. return;
  412. // Allocate buffers
  413. AllocateTable(max_size);
  414. // Reset all control bytes
  415. memset(mControl, cBucketEmpty, mMaxSize + 15);
  416. }
  417. /// Destroy the entire hash table
  418. void clear()
  419. {
  420. // Delete all elements
  421. if constexpr (!std::is_trivially_destructible<KeyValue>())
  422. if (!empty())
  423. for (size_type i = 0; i < mMaxSize; ++i)
  424. if (mControl[i] & cBucketUsed)
  425. mData[i].~KeyValue();
  426. if (mData != nullptr)
  427. {
  428. // Free memory
  429. if constexpr (cNeedsAlignedAllocate)
  430. AlignedFree(mData);
  431. else
  432. Free(mData);
  433. // Reset members
  434. mData = nullptr;
  435. mControl = nullptr;
  436. mSize = 0;
  437. mMaxSize = 0;
  438. mLoadLeft = 0;
  439. }
  440. }
  441. /// Iterator to first element
  442. iterator begin()
  443. {
  444. return iterator(this);
  445. }
  446. /// Iterator to one beyond last element
  447. iterator end()
  448. {
  449. return iterator(this, mMaxSize);
  450. }
  451. /// Iterator to first element
  452. const_iterator begin() const
  453. {
  454. return const_iterator(this);
  455. }
  456. /// Iterator to one beyond last element
  457. const_iterator end() const
  458. {
  459. return const_iterator(this, mMaxSize);
  460. }
  461. /// Iterator to first element
  462. const_iterator cbegin() const
  463. {
  464. return const_iterator(this);
  465. }
  466. /// Iterator to one beyond last element
  467. const_iterator cend() const
  468. {
  469. return const_iterator(this, mMaxSize);
  470. }
  471. /// Number of buckets in the table
  472. size_type bucket_count() const
  473. {
  474. return mMaxSize;
  475. }
  476. /// Max number of buckets that the table can have
  477. constexpr size_type max_bucket_count() const
  478. {
  479. return size_type(1) << (sizeof(size_type) * 8 - 1);
  480. }
  481. /// Check if there are no elements in the table
  482. bool empty() const
  483. {
  484. return mSize == 0;
  485. }
  486. /// Number of elements in the table
  487. size_type size() const
  488. {
  489. return mSize;
  490. }
  491. /// Max number of elements that the table can hold
  492. constexpr size_type max_size() const
  493. {
  494. return size_type((uint64(max_bucket_count()) * cMaxLoadFactorNumerator) / cMaxLoadFactorDenominator);
  495. }
  496. /// Get the max load factor for this table (max number of elements / number of buckets)
  497. constexpr float max_load_factor() const
  498. {
  499. return float(cMaxLoadFactorNumerator) / float(cMaxLoadFactorDenominator);
  500. }
  501. /// Insert a new element, returns iterator and if the element was inserted
  502. std::pair<iterator, bool> insert(const value_type &inValue)
  503. {
  504. size_type index;
  505. bool inserted = InsertKey(HashTableDetail::sGetKey(inValue), index);
  506. if (inserted)
  507. new (mData + index) KeyValue(inValue);
  508. return std::make_pair(iterator(this, index), inserted);
  509. }
  510. /// Find an element, returns iterator to element or end() if not found
  511. const_iterator find(const Key &inKey) const
  512. {
  513. // Check if we have any data
  514. if (empty())
  515. return cend();
  516. // Split hash into index and control value
  517. size_type index;
  518. uint8 control;
  519. GetIndexAndControlValue(inKey, index, control);
  520. // Linear probing
  521. KeyEqual equal;
  522. size_type bucket_mask = mMaxSize - 1;
  523. BVec16 control16 = BVec16::sReplicate(control);
  524. BVec16 bucket_empty = BVec16::sZero();
  525. for (;;)
  526. {
  527. // Read 16 control values
  528. // (note that we added 15 bytes at the end of the control values that mirror the first 15 bytes)
  529. BVec16 control_bytes = BVec16::sLoadByte16(mControl + index);
  530. // Check for the control value we're looking for
  531. // Note that when deleting we can create empty buckets instead of deleted buckets.
  532. // This means we must unconditionally check all buckets in this batch for equality
  533. // (also beyond the first empty bucket).
  534. uint32 control_equal = uint32(BVec16::sEquals(control_bytes, control16).GetTrues());
  535. // Index within the 16 buckets
  536. size_type local_index = index;
  537. // Loop while there's still buckets to process
  538. while (control_equal != 0)
  539. {
  540. // Get the first equal bucket
  541. uint first_equal = CountTrailingZeros(control_equal);
  542. // Skip to the bucket
  543. local_index += first_equal;
  544. // Make sure that our index is not beyond the end of the table
  545. local_index &= bucket_mask;
  546. // We found a bucket with same control value
  547. if (equal(HashTableDetail::sGetKey(mData[local_index]), inKey))
  548. {
  549. // Element found
  550. return const_iterator(this, local_index);
  551. }
  552. // Skip past this bucket
  553. control_equal >>= first_equal + 1;
  554. local_index++;
  555. }
  556. // Check for empty buckets
  557. uint32 control_empty = uint32(BVec16::sEquals(control_bytes, bucket_empty).GetTrues());
  558. if (control_empty != 0)
  559. {
  560. // An empty bucket was found, we didn't find the element
  561. return cend();
  562. }
  563. // Move to next batch of 16 buckets
  564. index = (index + 16) & bucket_mask;
  565. }
  566. }
  567. /// @brief Erase an element by iterator
  568. void erase(const const_iterator &inIterator)
  569. {
  570. JPH_ASSERT(inIterator.IsValid());
  571. // Read 16 control values before and after the current index
  572. // (note that we added 15 bytes at the end of the control values that mirror the first 15 bytes)
  573. BVec16 control_bytes_before = BVec16::sLoadByte16(mControl + ((inIterator.mIndex - 16) & (mMaxSize - 1)));
  574. BVec16 control_bytes_after = BVec16::sLoadByte16(mControl + inIterator.mIndex);
  575. BVec16 bucket_empty = BVec16::sZero();
  576. uint32 control_empty_before = uint32(BVec16::sEquals(control_bytes_before, bucket_empty).GetTrues());
  577. uint32 control_empty_after = uint32(BVec16::sEquals(control_bytes_after, bucket_empty).GetTrues());
  578. // If (this index including) there exist 16 consecutive non-empty slots (represented by a bit being 0) then
  579. // a probe looking for some element needs to continue probing so we cannot mark the bucket as empty
  580. // but must mark it as deleted instead.
  581. // Note that we use: CountLeadingZeros(uint16) = CountLeadingZeros(uint32) - 16.
  582. uint8 control_value = CountLeadingZeros(control_empty_before) - 16 + CountTrailingZeros(control_empty_after) < 16? cBucketEmpty : cBucketDeleted;
  583. // Mark the bucket as empty/deleted
  584. SetControlValue(inIterator.mIndex, control_value);
  585. // Destruct the element
  586. mData[inIterator.mIndex].~KeyValue();
  587. // If we marked the bucket as empty we can increase the load left
  588. if (control_value == cBucketEmpty)
  589. ++mLoadLeft;
  590. // Decrease size
  591. --mSize;
  592. }
  593. /// @brief Erase an element by key
  594. size_type erase(const Key &inKey)
  595. {
  596. const_iterator it = find(inKey);
  597. if (it == cend())
  598. return 0;
  599. erase(it);
  600. return 1;
  601. }
  602. /// Swap the contents of two hash tables
  603. void swap(HashTable &ioRHS) noexcept
  604. {
  605. std::swap(mData, ioRHS.mData);
  606. std::swap(mControl, ioRHS.mControl);
  607. std::swap(mSize, ioRHS.mSize);
  608. std::swap(mMaxSize, ioRHS.mMaxSize);
  609. std::swap(mLoadLeft, ioRHS.mLoadLeft);
  610. }
  611. /// In place re-hashing of all elements in the table. Removes all cBucketDeleted elements
  612. /// The std version takes a bucket count, but we just re-hash to the same size.
  613. void rehash(size_type)
  614. {
  615. // Update the control value for all buckets
  616. for (size_type i = 0; i < mMaxSize; ++i)
  617. {
  618. uint8 &control = mControl[i];
  619. switch (control)
  620. {
  621. case cBucketDeleted:
  622. // Deleted buckets become empty
  623. control = cBucketEmpty;
  624. break;
  625. case cBucketEmpty:
  626. // Remains empty
  627. break;
  628. default:
  629. // Mark all occupied as deleted, to indicate it needs to move to the correct place
  630. control = cBucketDeleted;
  631. break;
  632. }
  633. }
  634. // Replicate control values to the last 15 entries
  635. for (size_type i = 0; i < 15; ++i)
  636. mControl[mMaxSize + i] = mControl[i];
  637. // Loop over all elements that have been 'deleted' and move them to their new spot
  638. BVec16 bucket_used = BVec16::sReplicate(cBucketUsed);
  639. size_type bucket_mask = mMaxSize - 1;
  640. uint32 probe_mask = bucket_mask & ~uint32(0b1111); // Mask out lower 4 bits because we test 16 buckets at a time
  641. for (size_type src = 0; src < mMaxSize; ++src)
  642. if (mControl[src] == cBucketDeleted)
  643. for (;;)
  644. {
  645. // Split hash into index and control value
  646. size_type src_index;
  647. uint8 src_control;
  648. GetIndexAndControlValue(HashTableDetail::sGetKey(mData[src]), src_index, src_control);
  649. // Linear probing
  650. size_type dst = src_index;
  651. for (;;)
  652. {
  653. // Check if any buckets are free
  654. BVec16 control_bytes = BVec16::sLoadByte16(mControl + dst);
  655. uint32 control_free = uint32(BVec16::sAnd(control_bytes, bucket_used).GetTrues()) ^ 0xffff;
  656. if (control_free != 0)
  657. {
  658. // Select this bucket as destination
  659. dst += CountTrailingZeros(control_free);
  660. dst &= bucket_mask;
  661. break;
  662. }
  663. // Move to next batch of 16 buckets
  664. dst = (dst + 16) & bucket_mask;
  665. }
  666. // Check if we stay in the same probe group
  667. if (((dst - src_index) & probe_mask) == ((src - src_index) & probe_mask))
  668. {
  669. // We stay in the same group, we can stay where we are
  670. SetControlValue(src, src_control);
  671. break;
  672. }
  673. else if (mControl[dst] == cBucketEmpty)
  674. {
  675. // There's an empty bucket, move us there
  676. SetControlValue(dst, src_control);
  677. SetControlValue(src, cBucketEmpty);
  678. new (mData + dst) KeyValue(std::move(mData[src]));
  679. mData[src].~KeyValue();
  680. break;
  681. }
  682. else
  683. {
  684. // There's an element in the bucket we want to move to, swap them
  685. JPH_ASSERT(mControl[dst] == cBucketDeleted);
  686. SetControlValue(dst, src_control);
  687. std::swap(mData[src], mData[dst]);
  688. // Iterate again with the same source bucket
  689. }
  690. }
  691. // Reinitialize load left
  692. mLoadLeft = sGetMaxLoad(mMaxSize) - mSize;
  693. }
  694. private:
  695. /// If this allocator needs to fall back to aligned allocations because the type requires it
  696. static constexpr bool cNeedsAlignedAllocate = alignof(KeyValue) > (JPH_CPU_ADDRESS_BITS == 32? 8 : 16);
  697. /// Max load factor is cMaxLoadFactorNumerator / cMaxLoadFactorDenominator
  698. static constexpr uint64 cMaxLoadFactorNumerator = 7;
  699. static constexpr uint64 cMaxLoadFactorDenominator = 8;
  700. /// If we can recover this fraction of deleted elements, we'll reshuffle the buckets in place rather than growing the table
  701. static constexpr uint64 cMaxDeletedElementsNumerator = 1;
  702. static constexpr uint64 cMaxDeletedElementsDenominator = 8;
  703. /// Values that the control bytes can have
  704. static constexpr uint8 cBucketEmpty = 0;
  705. static constexpr uint8 cBucketDeleted = 0x7f;
  706. static constexpr uint8 cBucketUsed = 0x80; // Lowest 7 bits are lowest 7 bits of the hash value
  707. /// The buckets, an array of size mMaxSize
  708. KeyValue * mData = nullptr;
  709. /// Control bytes, an array of size mMaxSize + 15
  710. uint8 * mControl = nullptr;
  711. /// Number of elements in the table
  712. size_type mSize = 0;
  713. /// Max number of elements that can be stored in the table
  714. size_type mMaxSize = 0;
  715. /// Number of elements we can add to the table before we need to grow
  716. size_type mLoadLeft = 0;
  717. };
  718. JPH_NAMESPACE_END