* @brief hash set to record visited vertices * */
| 32 | * |
| 33 | */ |
| 34 | class HashBasedBooleanSet { |
| 35 | private: |
| 36 | size_t table_size_ = 0; |
| 37 | PID mask_ = 0; |
| 38 | std::vector<PID, memory::AlignedAllocator<PID>> table_; |
| 39 | std::unordered_set<PID> stl_hash_; |
| 40 | |
| 41 | [[nodiscard]] auto hash1(const PID value) const { return value & mask_; } |
| 42 | |
| 43 | public: |
| 44 | HashBasedBooleanSet() = default; |
| 45 | ~HashBasedBooleanSet() = default; |
| 46 | |
| 47 | HashBasedBooleanSet(const HashBasedBooleanSet&) = default; |
| 48 | HashBasedBooleanSet(HashBasedBooleanSet&&) noexcept = default; |
| 49 | HashBasedBooleanSet& operator=(HashBasedBooleanSet&&) noexcept = default; |
| 50 | |
| 51 | explicit HashBasedBooleanSet(size_t size) { |
| 52 | size_t bit_size = 0; |
| 53 | size_t bit = size; |
| 54 | while (bit != 0) { |
| 55 | bit_size++; |
| 56 | bit >>= 1; |
| 57 | } |
| 58 | size_t bucket_size = 0x1 << ((bit_size + 4) / 2 + 3); |
| 59 | initialize(bucket_size); |
| 60 | } |
| 61 | |
| 62 | void initialize(const size_t table_size) { |
| 63 | table_size_ = table_size; |
| 64 | mask_ = static_cast<PID>(table_size_ - 1); |
| 65 | const PID check_val = hash1(static_cast<PID>(table_size)); |
| 66 | if (check_val != 0) { |
| 67 | std::cerr << "[WARN] table size is not 2^N : " << table_size << '\n'; |
| 68 | } |
| 69 | |
| 70 | table_ = std::vector<PID, memory::AlignedAllocator<PID>>(table_size); |
| 71 | std::fill(table_.begin(), table_.end(), kPidMax); |
| 72 | stl_hash_.clear(); |
| 73 | } |
| 74 | |
| 75 | void clear() { |
| 76 | std::fill(table_.begin(), table_.end(), kPidMax); |
| 77 | stl_hash_.clear(); |
| 78 | } |
| 79 | |
| 80 | // get if data_id is in the hashset |
| 81 | [[nodiscard]] bool get(PID data_id) const { |
| 82 | PID val = this->table_[hash1(data_id)]; |
| 83 | if (val == data_id) { |
| 84 | return true; |
| 85 | } |
| 86 | return (val != kPidMax && stl_hash_.find(data_id) != stl_hash_.end()); |
| 87 | } |
| 88 | |
| 89 | void set(PID data_id) { |
| 90 | PID& val = table_[hash1(data_id)]; |
| 91 | if (val == data_id) { |