17#include <initializer_list>
29static constexpr PoolIndex invalidIndex{unsigned(-1)};
38template<
typename Value>
52 template<
typename... Args>
53 explicit constexpr Element(Args&&... args)
68template<
typename Value>
77 , freeIdx_ (source.freeIdx_)
78 , capacity_(source.capacity_)
80 source.buf_ =
nullptr;
81 source.freeIdx_ = invalidIndex;
88 freeIdx_ = source.freeIdx_;
89 capacity_ = source.capacity_;
90 source.buf_ =
nullptr;
91 source.freeIdx_ = invalidIndex;
106 assert(idx.
idx < capacity_);
107 return buf_[idx.
idx];
111 return const_cast<Pool&
>(*this).
get(idx);
123 if (freeIdx_ == invalidIndex) grow();
125 auto& elem =
get(idx);
126 freeIdx_ = elem.nextIdx;
127 new (&elem)
Elem(std::forward<V>(value), hash, nextIdx);
136 auto& elem =
get(idx);
138 elem.nextIdx = freeIdx_;
143 template<
typename... Args>
146 if (freeIdx_ == invalidIndex) grow();
148 auto& elem =
get(idx);
149 freeIdx_ = elem.nextIdx;
150 new (&elem)
Elem(std::forward<Args>(args)...);
162 if (capacity_ >= count)
return;
163 if (capacity_ != 0) {
173 swap(x.buf_, y.buf_);
174 swap(x.freeIdx_, y.freeIdx_);
175 swap(x.capacity_, y.capacity_);
181 if (capacity_ != 0) {
182 growMore(2 * capacity_);
188 void growMore(
unsigned newCapacity)
192 if constexpr (std::is_trivially_move_constructible_v<Elem> &&
193 std::is_trivially_copyable_v<Elem>) {
194 newBuf =
static_cast<Elem*
>(realloc(oldBuf, newCapacity *
sizeof(Elem)));
195 if (!newBuf)
throw std::bad_alloc();
197 newBuf =
static_cast<Elem*
>(malloc(newCapacity *
sizeof(Elem)));
198 if (!newBuf)
throw std::bad_alloc();
200 for (
size_t i :
xrange(capacity_)) {
201 new (&newBuf[i]) Elem(std::move(oldBuf[i]));
207 for (
auto i :
xrange(capacity_, newCapacity - 1)) {
208 newBuf[i].nextIdx = PoolIndex{i + 1};
210 newBuf[newCapacity - 1].nextIdx = invalidIndex;
213 freeIdx_ = PoolIndex{capacity_};
214 capacity_ = newCapacity;
217 void growInitial(
unsigned newCapacity)
219 auto* newBuf =
static_cast<Elem*
>(malloc(newCapacity *
sizeof(Elem)));
220 if (!newBuf)
throw std::bad_alloc();
222 for (
auto i :
xrange(newCapacity - 1)) {
223 newBuf[i].nextIdx = PoolIndex{i + 1};
225 newBuf[newCapacity - 1].nextIdx = invalidIndex;
228 freeIdx_ = PoolIndex{0};
229 capacity_ = newCapacity;
233 Elem* buf_ =
nullptr;
234 PoolIndex freeIdx_ = invalidIndex;
235 unsigned capacity_ = 0;
239template<
typename Value,
typename Extractor>
241 decltype(std::declval<Extractor>()(std::declval<Value>()))>;
260template<
typename Value,
261 typename Extractor = std::identity,
262 typename Hasher = std::hash<hash_set_impl::ExtractedType<Value, Extractor>>,
263 typename Equal = std::equal_to<>>
273 template<
typename HashSet,
typename IValue>
284 template<
typename HashSet2,
typename IValue2>
286 : hashSet(other.hashSet), elemIdx(other.elemIdx) {}
288 template<
typename HashSet2,
typename IValue2>
290 hashSet = rhs.hashSet;
291 elemIdx = rhs.elemIdx;
296 assert((hashSet == rhs.hashSet) || !hashSet || !rhs.hashSet);
297 return elemIdx == rhs.elemIdx;
301 auto& oldElem = hashSet->pool.get(elemIdx);
302 elemIdx = oldElem.nextIdx;
304 unsigned tableIdx = oldElem.hash & hashSet->allocMask;
306 if (tableIdx == hashSet->allocMask)
break;
307 elemIdx = hashSet->table[++tableIdx];
319 return hashSet->pool.get(elemIdx).value;
322 return &hashSet->pool.get(elemIdx).value;
327 : hashSet(m), elemIdx(idx) {}
334 HashSet* hashSet =
nullptr;
343 Extractor extract_ = Extractor(),
344 Hasher hasher_ = Hasher(),
345 Equal equal_ = Equal())
358 for (
unsigned i = 0; i <= source.
allocMask; ++i) {
360 const auto& elem = source.
pool.get(idx);
368 :
table(source.table)
369 ,
pool(std::move(source.pool))
372 ,
extract(std::move(source.extract))
373 ,
hasher (std::move(source.hasher))
374 ,
equal (std::move(source.equal))
376 source.table =
nullptr;
377 source.allocMask = -1;
378 source.elemCount = 0;
381 explicit hash_set(std::initializer_list<Value> args)
383 reserve(narrow<unsigned>(args.size()));
395 if (&source ==
this)
return *
this;
400 for (
unsigned i = 0; i <= source.
allocMask; ++i) {
402 const auto& elem = source.
pool.get(idx);
415 table = source.table;
416 pool = std::move(source.pool);
419 extract = std::move(source.extract);
420 hasher = std::move(source.hasher);
421 equal = std::move(source.equal);
423 source.table =
nullptr;
424 source.allocMask = -1;
425 source.elemCount = 0;
436 std::pair<iterator, bool>
insert(V&& value)
438 return insert_impl<true, true>(std::forward<V>(value));
443 return insert_impl<false, true>(std::forward<V>(value));
448 return insert_impl<true, false>(std::forward<V>(value)).first;
453 return insert_impl<false, false>(std::forward<V>(value)).first;
456 template<
typename... Args>
457 std::pair<iterator, bool>
emplace(Args&&... args)
459 return emplace_impl<true, true>(std::forward<Args>(args)...);
461 template<
typename... Args>
464 return emplace_impl<false, true>(std::forward<Args>(args)...);
466 template<
typename... Args>
469 return emplace_impl<true, false>(std::forward<Args>(args)...).first;
471 template<
typename... Args>
474 return emplace_impl<false, false>(std::forward<Args>(args)...).first;
482 auto hash = unsigned(
hasher(key));
486 auto elemIdx = *prev;
487 auto& elem =
pool.get(elemIdx);
488 if (elem.hash != hash)
continue;
491 *prev = elem.nextIdx;
492 pool.destroy(elemIdx);
506 auto& elem =
pool.get(elemIdx);
508 auto* prev = &
table[tableIdx];
510 while (*prev != elemIdx) {
511 prev = &(
pool.get(*prev).nextIdx);
514 *prev = elem.nextIdx;
515 pool.destroy(elemIdx);
524 [[nodiscard]]
unsigned size()
const
533 for (
unsigned i = 0; i <=
allocMask; ++i) {
535 auto nextIdx =
pool.get(elemIdx).nextIdx;
536 pool.destroy(elemIdx);
560 for (
unsigned idx = 0; idx <=
allocMask; ++idx) {
573 for (
unsigned idx = 0; idx <=
allocMask; ++idx) {
594 unsigned poolCapacity =
pool.capacity();
595 unsigned tableCapacity = (
allocMask + 1) / 4 * 3;
596 return std::min(poolCapacity, tableCapacity);
607 if (oldCount >= newCount)
return;
618 }
while (oldCount < newCount);
625 swap(x.table, y.table);
626 swap(x.pool, y.pool);
627 swap(x.allocMask, y.allocMask);
628 swap(x.elemCount, y.elemCount);
629 swap(x.extract , y.extract);
630 swap(x.hasher , y.hasher);
631 swap(x.equal , y.equal);
644 static_assert(
sizeof(unsigned) ==
sizeof(uint32_t),
"only works for exactly 32 bit");
654 template<
bool CHECK_CAPACITY,
bool CHECK_DUPLICATE,
typename V>
661 if (!CHECK_CAPACITY || (
elemCount > 0)) {
662 primary =
table[tableIdx];
663 if constexpr (CHECK_DUPLICATE) {
664 for (
auto elemIdx = primary; elemIdx !=
invalidIndex; ) {
665 auto& elem =
pool.get(elemIdx);
666 if ((elem.hash == hash) &&
669 return std::pair(
iterator(
this, elemIdx),
false);
671 elemIdx = elem.nextIdx;
679 primary =
table[tableIdx];
683 auto idx =
pool.create(std::forward<V>(value), hash, primary);
684 table[tableIdx] = idx;
685 return std::pair(
iterator(
this, idx),
true);
688 template<
bool CHECK_CAPACITY,
bool CHECK_DUPLICATE,
typename... Args>
691 auto poolIdx =
pool.emplace(std::forward<Args>(args)...);
692 auto& poolElem =
pool.get(poolIdx);
698 if (!CHECK_CAPACITY || (
elemCount > 0)) {
699 primary =
table[tableIdx];
700 if constexpr (CHECK_DUPLICATE) {
701 for (
auto elemIdx = primary; elemIdx !=
invalidIndex; ) {
702 auto& elem =
pool.get(elemIdx);
703 if ((elem.hash == hash) &&
706 pool.destroy(poolIdx);
707 return std::pair(
iterator(
this, elemIdx),
false);
709 elemIdx = elem.nextIdx;
717 primary =
table[tableIdx];
721 poolElem.hash = hash;
722 poolElem.nextIdx = primary;
723 table[tableIdx] = poolIdx;
724 return std::pair(
iterator(
this, poolIdx),
true);
735 unsigned newCount = 2 * oldCount;
744 assert((oldCount & (oldCount - 1)) == 0);
745 for (
auto i :
xrange(oldCount)) {
746 auto* p0 = &
table[i];
747 auto* p1 = &
table[i + oldCount];
749 auto& elem =
pool.get(p);
750 if ((elem.hash & oldCount) == 0) {
768 auto hash = unsigned(
hasher(key));
771 auto& elem =
pool.get(elemIdx);
772 if ((elem.hash == hash) &&
776 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)
typename std::remove_cvref_t< decltype(std::declval< Extractor >()(std::declval< Value >()))> ExtractedType
constexpr Element(Args &&... args)
constexpr Element(V &&value_, unsigned hash_, PoolIndex nextIdx_)
constexpr bool operator==(const PoolIndex &) const =default
constexpr auto xrange(T e)