17#include <initializer_list>
36static constexpr PoolIndex invalidIndex{unsigned(-1)};
45template<
typename Value>
59 template<
typename... Args>
60 explicit constexpr Element(Args&&... args)
75template<
typename Value>
84 , freeIdx_ (source.freeIdx_)
85 , capacity_(source.capacity_)
87 source.buf_ =
nullptr;
88 source.freeIdx_ = invalidIndex;
95 freeIdx_ = source.freeIdx_;
96 capacity_ = source.capacity_;
97 source.buf_ =
nullptr;
98 source.freeIdx_ = invalidIndex;
113 assert(idx.
idx < capacity_);
114 return buf_[idx.
idx];
118 return const_cast<Pool&
>(*this).
get(idx);
130 if (freeIdx_ == invalidIndex) grow();
132 auto& elem =
get(idx);
133 freeIdx_ = elem.nextIdx;
134 new (&elem)
Elem(std::forward<V>(value), hash, nextIdx);
143 auto& elem =
get(idx);
145 elem.nextIdx = freeIdx_;
150 template<
typename... Args>
153 if (freeIdx_ == invalidIndex) grow();
155 auto& elem =
get(idx);
156 freeIdx_ = elem.nextIdx;
157 new (&elem)
Elem(std::forward<Args>(args)...);
169 if (capacity_ >=
count)
return;
170 if (capacity_ != 0) {
180 swap(x.buf_, y.buf_);
181 swap(x.freeIdx_, y.freeIdx_);
182 swap(x.capacity_, y.capacity_);
188 if (capacity_ != 0) {
189 growMore(2 * capacity_);
195 void growMore(
unsigned newCapacity)
199 if constexpr (std::is_trivially_move_constructible_v<Elem> &&
200 std::is_trivially_copyable_v<Elem>) {
201 newBuf =
static_cast<Elem*
>(realloc(oldBuf, newCapacity *
sizeof(Elem)));
202 if (!newBuf)
throw std::bad_alloc();
204 newBuf =
static_cast<Elem*
>(malloc(newCapacity *
sizeof(Elem)));
205 if (!newBuf)
throw std::bad_alloc();
207 for (
size_t i :
xrange(capacity_)) {
208 new (&newBuf[i]) Elem(std::move(oldBuf[i]));
214 for (
auto i :
xrange(capacity_, newCapacity - 1)) {
215 newBuf[i].nextIdx = PoolIndex{i + 1};
217 newBuf[newCapacity - 1].nextIdx = invalidIndex;
220 freeIdx_ = PoolIndex{capacity_};
221 capacity_ = newCapacity;
224 void growInitial(
unsigned newCapacity)
226 auto* newBuf =
static_cast<Elem*
>(malloc(newCapacity *
sizeof(Elem)));
227 if (!newBuf)
throw std::bad_alloc();
229 for (
auto i :
xrange(newCapacity - 1)) {
230 newBuf[i].nextIdx = PoolIndex{i + 1};
232 newBuf[newCapacity - 1].nextIdx = invalidIndex;
235 freeIdx_ = PoolIndex{0};
236 capacity_ = newCapacity;
240 Elem* buf_ =
nullptr;
241 PoolIndex freeIdx_ = invalidIndex;
242 unsigned capacity_ = 0;
246template<
typename Value,
typename Extractor>
248 decltype(std::declval<Extractor>()(std::declval<Value>()))>;
267template<
typename Value,
269 typename Hasher = std::hash<hash_set_impl::ExtractedType<Value, Extractor>>,
270 typename Equal = std::equal_to<>>
280 template<
typename HashSet,
typename IValue>
291 template<
typename HashSet2,
typename IValue2>
293 : hashSet(other.hashSet), elemIdx(other.elemIdx) {}
295 template<
typename HashSet2,
typename IValue2>
297 hashSet = rhs.hashSet;
298 elemIdx = rhs.elemIdx;
303 assert((hashSet == rhs.hashSet) || !hashSet || !rhs.hashSet);
304 return elemIdx == rhs.elemIdx;
308 auto& oldElem = hashSet->pool.get(elemIdx);
309 elemIdx = oldElem.nextIdx;
311 unsigned tableIdx = oldElem.hash & hashSet->allocMask;
313 if (tableIdx == hashSet->allocMask)
break;
314 elemIdx = hashSet->table[++tableIdx];
326 return hashSet->pool.get(elemIdx).value;
329 return &hashSet->pool.get(elemIdx).value;
334 : hashSet(m), elemIdx(idx) {}
341 HashSet* hashSet =
nullptr;
350 Extractor extract_ = Extractor(),
351 Hasher hasher_ = Hasher(),
352 Equal equal_ = Equal())
365 for (
unsigned i = 0; i <= source.
allocMask; ++i) {
367 const auto& elem = source.
pool.get(idx);
375 :
table(source.table)
376 ,
pool(std::move(source.pool))
379 ,
extract(std::move(source.extract))
380 ,
hasher (std::move(source.hasher))
381 ,
equal (std::move(source.equal))
383 source.table =
nullptr;
384 source.allocMask = -1;
385 source.elemCount = 0;
388 explicit hash_set(std::initializer_list<Value> args)
390 reserve(narrow<unsigned>(args.size()));
402 if (&source ==
this)
return *
this;
407 for (
unsigned i = 0; i <= source.
allocMask; ++i) {
409 const auto& elem = source.
pool.get(idx);
422 table = source.table;
423 pool = std::move(source.pool);
426 extract = std::move(source.extract);
427 hasher = std::move(source.hasher);
428 equal = std::move(source.equal);
430 source.table =
nullptr;
431 source.allocMask = -1;
432 source.elemCount = 0;
443 std::pair<iterator, bool>
insert(V&& value)
445 return insert_impl<true, true>(std::forward<V>(value));
450 return insert_impl<false, true>(std::forward<V>(value));
455 return insert_impl<true, false>(std::forward<V>(value)).first;
460 return insert_impl<false, false>(std::forward<V>(value)).first;
463 template<
typename... Args>
464 std::pair<iterator, bool>
emplace(Args&&... args)
466 return emplace_impl<true, true>(std::forward<Args>(args)...);
468 template<
typename... Args>
471 return emplace_impl<false, true>(std::forward<Args>(args)...);
473 template<
typename... Args>
476 return emplace_impl<true, false>(std::forward<Args>(args)...).first;
478 template<
typename... Args>
481 return emplace_impl<false, false>(std::forward<Args>(args)...).first;
489 auto hash = unsigned(
hasher(key));
493 auto elemIdx = *prev;
494 auto& elem =
pool.get(elemIdx);
495 if (elem.hash != hash)
continue;
498 *prev = elem.nextIdx;
499 pool.destroy(elemIdx);
513 auto& elem =
pool.get(elemIdx);
515 auto* prev = &
table[tableIdx];
517 while (*prev != elemIdx) {
518 prev = &(
pool.get(*prev).nextIdx);
521 *prev = elem.nextIdx;
522 pool.destroy(elemIdx);
531 [[nodiscard]]
unsigned size()
const
540 for (
unsigned i = 0; i <=
allocMask; ++i) {
542 auto nextIdx =
pool.get(elemIdx).nextIdx;
543 pool.destroy(elemIdx);
567 for (
unsigned idx = 0; idx <=
allocMask; ++idx) {
580 for (
unsigned idx = 0; idx <=
allocMask; ++idx) {
601 unsigned poolCapacity =
pool.capacity();
602 unsigned tableCapacity = (
allocMask + 1) / 4 * 3;
603 return std::min(poolCapacity, tableCapacity);
614 if (oldCount >= newCount)
return;
625 }
while (oldCount < newCount);
632 swap(x.table, y.table);
633 swap(x.pool, y.pool);
634 swap(x.allocMask, y.allocMask);
635 swap(x.elemCount, y.elemCount);
636 swap(x.extract , y.extract);
637 swap(x.hasher , y.hasher);
638 swap(x.equal , y.equal);
651 static_assert(
sizeof(unsigned) ==
sizeof(uint32_t),
"only works for exactly 32 bit");
661 template<
bool CHECK_CAPACITY,
bool CHECK_DUPLICATE,
typename V>
668 if (!CHECK_CAPACITY || (
elemCount > 0)) {
669 primary =
table[tableIdx];
670 if constexpr (CHECK_DUPLICATE) {
671 for (
auto elemIdx = primary; elemIdx !=
invalidIndex; ) {
672 auto& elem =
pool.get(elemIdx);
673 if ((elem.hash == hash) &&
676 return std::pair(
iterator(
this, elemIdx),
false);
678 elemIdx = elem.nextIdx;
686 primary =
table[tableIdx];
690 auto idx =
pool.create(std::forward<V>(value), hash, primary);
691 table[tableIdx] = idx;
692 return std::pair(
iterator(
this, idx),
true);
695 template<
bool CHECK_CAPACITY,
bool CHECK_DUPLICATE,
typename... Args>
698 auto poolIdx =
pool.emplace(std::forward<Args>(args)...);
699 auto& poolElem =
pool.get(poolIdx);
705 if (!CHECK_CAPACITY || (
elemCount > 0)) {
706 primary =
table[tableIdx];
707 if constexpr (CHECK_DUPLICATE) {
708 for (
auto elemIdx = primary; elemIdx !=
invalidIndex; ) {
709 auto& elem =
pool.get(elemIdx);
710 if ((elem.hash == hash) &&
713 pool.destroy(poolIdx);
714 return std::pair(
iterator(
this, elemIdx),
false);
716 elemIdx = elem.nextIdx;
724 primary =
table[tableIdx];
728 poolElem.hash = hash;
729 poolElem.nextIdx = primary;
730 table[tableIdx] = poolIdx;
731 return std::pair(
iterator(
this, poolIdx),
true);
742 unsigned newCount = 2 * oldCount;
751 assert((oldCount & (oldCount - 1)) == 0);
752 for (
auto i :
xrange(oldCount)) {
753 auto* p0 = &
table[i];
754 auto* p1 = &
table[i + oldCount];
756 auto& elem =
pool.get(p);
757 if ((elem.hash & oldCount) == 0) {
775 auto hash = unsigned(
hasher(key));
778 auto& elem =
pool.get(elemIdx);
779 if ((elem.hash == hash) &&
783 elemIdx = elem.nextIdx;
Iter(HashSet *m, PoolIndex idx)
IValue & operator*() const
Iter & operator=(const Iter< HashSet2, IValue2 > &rhs)
Iter(const Iter< HashSet2, IValue2 > &other)
IValue * operator->() const
bool operator==(const Iter &rhs) const
PoolIndex getElementIdx() const
std::forward_iterator_tag iterator_category
PoolIndex emplace(Args &&... args)
unsigned capacity() const
friend void swap(Pool &x, Pool &y) noexcept
const Elem & get(PoolIndex idx) const
Pool(Pool &&source) noexcept
Elem & get(PoolIndex idx)
PoolIndex create(V &&value, unsigned hash, PoolIndex nextIdx)
void destroy(PoolIndex idx)
Pool & operator=(Pool &&source) noexcept
void reserve(unsigned count)
hash_set(unsigned initialSize=0, Extractor extract_=Extractor(), Hasher hasher_=Hasher(), Equal equal_=Equal())
std::pair< iterator, bool > insert_noCapacityCheck(V &&value)
friend auto end(hash_set &s)
void rehash(unsigned oldCount)
std::pair< iterator, bool > emplace_noCapacityCheck(Args &&... args)
friend void swap(hash_set &x, hash_set &y) noexcept
bool contains(const K &key) const
friend auto begin(hash_set &s)
hash_set(std::initializer_list< Value > args)
friend auto begin(const hash_set &s)
static unsigned nextPowerOf2(unsigned x)
const_iterator end() const
hash_set & operator=(const hash_set &source)
std::pair< iterator, bool > emplace(Args &&... args)
iterator insert_noCapacityCheck_noDuplicateCheck(V &&value)
const_iterator begin() const
hash_set(const hash_set &source)
iterator insert_noDuplicateCheck(V &&value)
PoolIndex locateElement(const K &key) const
Iter< const hash_set, const Value > const_iterator
hash_set(hash_set &&source) noexcept
iterator emplace_noDuplicateCheck(Args &&... args)
hash_set & operator=(hash_set &&source) noexcept
std::pair< iterator, bool > emplace_impl(Args &&... args)
iterator find(const K &key)
const_iterator find(const K &key) const
std::pair< iterator, bool > insert(V &&value)
Iter< hash_set, Value > iterator
void reserve(unsigned count)
friend auto end(const hash_set &s)
static constexpr auto invalidIndex
iterator emplace_noCapacityCheck_noDuplicateCheck(Args &&... args)
unsigned capacity() const
hash_set_impl::Pool< Value > pool
std::pair< iterator, bool > insert_impl(V &&value)
ALWAYS_INLINE unsigned count(const uint8_t *pIn, const uint8_t *pMatch, const uint8_t *pInLimit)
constexpr vecN< N, T > min(const vecN< N, T > &x, const vecN< N, T > &y)
typename std::remove_cvref_t< decltype(std::declval< Extractor >()(std::declval< Value >()))> ExtractedType
constexpr void fill(ForwardRange &&range, const T &value)
void swap(openmsx::MemBuffer< T > &l, openmsx::MemBuffer< T > &r) noexcept
constexpr Element(Args &&... args)
constexpr Element(V &&value_, unsigned hash_, PoolIndex nextIdx_)
T & operator()(T &&t) const
constexpr bool operator==(const PoolIndex &) const =default
constexpr auto xrange(T e)