15 #include <initializer_list>
18 #include <type_traits>
33 static constexpr
PoolIndex invalidIndex{unsigned(-1)};
44 template<
typename Value>
52 :
value(std::forward<V>(value_))
58 template<
typename... Args>
59 explicit constexpr
Element(Args&&... args)
60 :
value(std::forward<Args>(args)...)
74 template<
typename Value>
83 , freeIdx_ (source.freeIdx_)
84 , capacity_(source.capacity_)
86 source.buf_ =
nullptr;
87 source.freeIdx_ = invalidIndex;
94 freeIdx_ = source.freeIdx_;
95 capacity_ = source.capacity_;
96 source.buf_ =
nullptr;
97 source.freeIdx_ = invalidIndex;
112 assert(idx.
idx < capacity_);
113 return buf_[idx.
idx];
117 return const_cast<Pool&
>(*this).
get(idx);
129 if (freeIdx_ == invalidIndex) grow();
131 auto& elem =
get(idx);
132 freeIdx_ = elem.nextIdx;
133 new (&elem)
Elem(std::forward<V>(value), hash, nextIdx);
142 auto& elem =
get(idx);
144 elem.nextIdx = freeIdx_;
149 template<
typename... Args>
152 if (freeIdx_ == invalidIndex) grow();
154 auto& elem =
get(idx);
155 freeIdx_ = elem.nextIdx;
156 new (&elem)
Elem(std::forward<Args>(args)...);
168 if (capacity_ >=
count)
return;
169 if (capacity_ != 0) {
179 swap(
x.buf_, y.buf_);
180 swap(
x.freeIdx_, y.freeIdx_);
181 swap(
x.capacity_, y.capacity_);
187 if (capacity_ != 0) {
188 growMore(2 * capacity_);
194 void growMore(
unsigned newCapacity)
198 if constexpr (std::is_trivially_move_constructible_v<Elem> &&
199 std::is_trivially_copyable_v<Elem>) {
200 newBuf =
static_cast<Elem*
>(realloc(oldBuf, newCapacity *
sizeof(Elem)));
201 if (!newBuf)
throw std::bad_alloc();
203 newBuf =
static_cast<Elem*
>(malloc(newCapacity *
sizeof(Elem)));
204 if (!newBuf)
throw std::bad_alloc();
206 for (
size_t i :
xrange(capacity_)) {
207 new (&newBuf[i]) Elem(std::move(oldBuf[i]));
213 for (
auto i :
xrange(capacity_, newCapacity - 1)) {
214 newBuf[i].nextIdx = PoolIndex{i + 1};
216 newBuf[newCapacity - 1].nextIdx = invalidIndex;
219 freeIdx_ = PoolIndex{capacity_};
220 capacity_ = newCapacity;
223 void growInitial(
unsigned newCapacity)
225 auto* newBuf =
static_cast<Elem*
>(malloc(newCapacity *
sizeof(Elem)));
226 if (!newBuf)
throw std::bad_alloc();
228 for (
auto i :
xrange(newCapacity - 1)) {
229 newBuf[i].nextIdx = PoolIndex{i + 1};
231 newBuf[newCapacity - 1].nextIdx = invalidIndex;
234 freeIdx_ = PoolIndex{0};
235 capacity_ = newCapacity;
239 Elem* buf_ =
nullptr;
240 PoolIndex freeIdx_ = invalidIndex;
241 unsigned capacity_ = 0;
245 template<
typename Value,
typename Extractor>
247 typename std::remove_cv<
248 typename std::remove_reference<
249 decltype(std::declval<Extractor>()(std::declval<Value>()))>
270 template<
typename Value,
272 typename Hasher = std::hash<hash_set_impl::ExtractedType<Value, Extractor>>,
273 typename Equal = std::equal_to<>>
277 static constexpr
auto invalidIndex = hash_set_impl::invalidIndex;
282 template<
typename HashSet,
typename IValue>
293 template<
typename HashSet2,
typename IValue2>
295 : hashSet(other.hashSet), elemIdx(other.elemIdx) {}
297 template<
typename HashSet2,
typename IValue2>
299 hashSet = rhs.hashSet;
300 elemIdx = rhs.elemIdx;
305 assert((hashSet == rhs.hashSet) || !hashSet || !rhs.hashSet);
306 return elemIdx == rhs.elemIdx;
309 return !(*
this == rhs);
313 auto& oldElem = hashSet->pool.get(elemIdx);
314 elemIdx = oldElem.nextIdx;
315 if (elemIdx == invalidIndex) {
316 unsigned tableIdx = oldElem.hash & hashSet->allocMask;
318 if (tableIdx == hashSet->allocMask)
break;
319 elemIdx = hashSet->table[++tableIdx];
320 }
while (elemIdx == invalidIndex);
331 return hashSet->pool.get(elemIdx).value;
334 return &hashSet->pool.get(elemIdx).value;
341 : hashSet(m), elemIdx(idx) {}
343 [[nodiscard]]
PoolIndex getElementIdx()
const {
348 HashSet* hashSet =
nullptr;
349 PoolIndex elemIdx = invalidIndex;
357 Extractor extract_ = Extractor(),
358 Hasher hasher_ = Hasher(),
359 Equal equal_ = Equal())
360 : extract(extract_), hasher(hasher_), equal(equal_)
366 : extract(source.extract), hasher(source.hasher)
367 , equal(source.equal)
369 if (source.elemCount == 0)
return;
372 for (
unsigned i = 0; i <= source.allocMask; ++i) {
373 for (
auto idx = source.table[i]; idx != invalidIndex; ) {
374 const auto& elem = source.pool.get(idx);
382 : table(source.table)
383 , pool(std::move(source.pool))
384 , allocMask(source.allocMask)
385 , elemCount(source.elemCount)
386 , extract(std::move(source.extract))
387 , hasher (std::move(source.hasher))
388 , equal (std::move(source.equal))
390 source.table =
nullptr;
391 source.allocMask = -1;
392 source.elemCount = 0;
395 explicit hash_set(std::initializer_list<Value> args)
409 if (&source ==
this)
return *
this;
411 if (source.elemCount == 0)
return *
this;
414 for (
unsigned i = 0; i <= source.allocMask; ++i) {
415 for (
auto idx = source.table[i]; idx != invalidIndex; ) {
416 const auto& elem = source.pool.get(idx);
421 extract = source.extract;
422 hasher = source.hasher;
423 equal = source.equal;
429 table = source.table;
430 pool = std::move(source.pool);
431 allocMask = source.allocMask;
432 elemCount = source.elemCount;
433 extract = std::move(source.extract);
434 hasher = std::move(source.hasher);
435 equal = std::move(source.equal);
437 source.table =
nullptr;
438 source.allocMask = -1;
439 source.elemCount = 0;
446 return locateElement(key) != invalidIndex;
450 std::pair<iterator, bool>
insert(V&& value)
452 return insert_impl<true, true>(std::forward<V>(value));
457 return insert_impl<false, true>(std::forward<V>(value));
462 return insert_impl<true, false>(std::forward<V>(value)).first;
467 return insert_impl<false, false>(std::forward<V>(value)).first;
470 template<
typename... Args>
471 std::pair<iterator, bool>
emplace(Args&&... args)
473 return emplace_impl<true, true>(std::forward<Args>(args)...);
475 template<
typename... Args>
478 return emplace_impl<false, true>(std::forward<Args>(args)...);
480 template<
typename... Args>
483 return emplace_impl<true, false>(std::forward<Args>(args)...).first;
485 template<
typename... Args>
488 return emplace_impl<false, false>(std::forward<Args>(args)...).first;
494 if (elemCount == 0)
return false;
496 auto hash = unsigned(hasher(key));
497 auto tableIdx = hash & allocMask;
499 for (
auto* prev = &table[tableIdx]; *prev != invalidIndex; prev = &(pool.get(*prev).nextIdx)) {
500 auto elemIdx = *prev;
501 auto& elem = pool.get(elemIdx);
502 if (elem.hash != hash)
continue;
503 if (!equal(extract(elem.value), key))
continue;
505 *prev = elem.nextIdx;
506 pool.destroy(elemIdx);
515 auto elemIdx = it.getElementIdx();
516 if (elemIdx == invalidIndex) {
520 auto& elem = pool.get(elemIdx);
521 auto tableIdx = pool.get(elemIdx).hash & allocMask;
522 auto* prev = &table[tableIdx];
523 assert(*prev != invalidIndex);
524 while (*prev != elemIdx) {
525 prev = &(pool.get(*prev).nextIdx);
526 assert(*prev != invalidIndex);
528 *prev = elem.nextIdx;
529 pool.destroy(elemIdx);
535 return elemCount == 0;
538 [[nodiscard]]
unsigned size()
const
545 if (elemCount == 0)
return;
547 for (
unsigned i = 0; i <= allocMask; ++i) {
548 for (
auto elemIdx = table[i]; elemIdx != invalidIndex; ) {
549 auto nextIdx = pool.get(elemIdx).nextIdx;
550 pool.destroy(elemIdx);
553 table[i] = invalidIndex;
561 return iterator(
this, locateElement(key));
572 if (elemCount == 0)
return end();
574 for (
unsigned idx = 0; idx <= allocMask; ++idx) {
575 if (table[idx] != invalidIndex) {
585 if (elemCount == 0)
return end();
587 for (
unsigned idx = 0; idx <= allocMask; ++idx) {
588 if (table[idx] != invalidIndex) {
608 unsigned poolCapacity = pool.capacity();
609 unsigned tableCapacity = (allocMask + 1) / 4 * 3;
610 return std::min(poolCapacity, tableCapacity);
619 unsigned oldCount = allocMask + 1;
620 unsigned newCount = nextPowerOf2((
count + 2) / 3 * 4);
621 if (oldCount >= newCount)
return;
623 allocMask = newCount - 1;
626 std::fill(table, table + newCount, invalidIndex);
632 }
while (oldCount < newCount);
639 swap(
x.table, y.table);
640 swap(
x.pool, y.pool);
641 swap(
x.allocMask, y.allocMask);
642 swap(
x.elemCount, y.elemCount);
643 swap(
x.extract , y.extract);
644 swap(
x.hasher , y.hasher);
645 swap(
x.equal , y.equal);
656 [[nodiscard]]
static inline unsigned nextPowerOf2(
unsigned x)
658 static_assert(
sizeof(
unsigned) ==
sizeof(uint32_t),
"only works for exactly 32 bit");
668 template<
bool CHECK_CAPACITY,
bool CHECK_DUPLICATE,
typename V>
669 [[nodiscard]] std::pair<iterator, bool> insert_impl(V&& value)
671 auto hash = unsigned(hasher(extract(value)));
672 auto tableIdx = hash & allocMask;
673 PoolIndex primary = invalidIndex;
675 if (!CHECK_CAPACITY || (elemCount > 0)) {
676 primary = table[tableIdx];
677 if (CHECK_DUPLICATE) {
678 for (
auto elemIdx = primary; elemIdx != invalidIndex; ) {
679 auto& elem = pool.get(elemIdx);
680 if ((elem.hash == hash) &&
681 equal(extract(elem.value), extract(value))) {
683 return std::pair(
iterator(
this, elemIdx),
false);
685 elemIdx = elem.nextIdx;
690 if (CHECK_CAPACITY && (elemCount >= ((allocMask + 1) / 4 * 3))) {
692 tableIdx = hash & allocMask;
693 primary = table[tableIdx];
697 auto idx = pool.create(std::forward<V>(value), hash, primary);
698 table[tableIdx] = idx;
699 return std::pair(
iterator(
this, idx),
true);
702 template<
bool CHECK_CAPACITY,
bool CHECK_DUPLICATE,
typename... Args>
703 [[nodiscard]] std::pair<iterator, bool> emplace_impl(Args&&... args)
705 auto poolIdx = pool.emplace(std::forward<Args>(args)...);
706 auto& poolElem = pool.get(poolIdx);
708 auto hash = unsigned(hasher(extract(poolElem.value)));
709 auto tableIdx = hash & allocMask;
710 PoolIndex primary = invalidIndex;
712 if (!CHECK_CAPACITY || (elemCount > 0)) {
713 primary = table[tableIdx];
714 if (CHECK_DUPLICATE) {
715 for (
auto elemIdx = primary; elemIdx != invalidIndex; ) {
716 auto& elem = pool.get(elemIdx);
717 if ((elem.hash == hash) &&
718 equal(extract(elem.value), extract(poolElem.value))) {
720 pool.destroy(poolIdx);
721 return std::pair(
iterator(
this, elemIdx),
false);
723 elemIdx = elem.nextIdx;
728 if (CHECK_CAPACITY && (elemCount >= ((allocMask + 1) / 4 * 3))) {
730 tableIdx = hash & allocMask;
731 primary = table[tableIdx];
735 poolElem.hash = hash;
736 poolElem.nextIdx = primary;
737 table[tableIdx] = poolIdx;
738 return std::pair(
iterator(
this, poolIdx),
true);
743 unsigned oldCount = allocMask + 1;
746 table =
static_cast<PoolIndex*
>(malloc(4 *
sizeof(PoolIndex)));
747 std::fill(table, table + 4, invalidIndex);
749 unsigned newCount = 2 * oldCount;
750 allocMask = newCount - 1;
751 table =
static_cast<PoolIndex*
>(realloc(table, newCount *
sizeof(
unsigned)));
756 void rehash(
unsigned oldCount)
758 assert((oldCount & (oldCount - 1)) == 0);
759 for (
auto i :
xrange(oldCount)) {
760 auto* p0 = &table[i];
761 auto* p1 = &table[i + oldCount];
762 for (
auto p = *p0; p != invalidIndex; p = pool.get(p).nextIdx) {
763 auto& elem = pool.get(p);
764 if ((elem.hash & oldCount) == 0) {
778 [[nodiscard]] PoolIndex locateElement(
const K& key)
const
780 if (elemCount == 0)
return invalidIndex;
782 auto hash = unsigned(hasher(key));
783 auto tableIdx = hash & allocMask;
784 for (
auto elemIdx = table[tableIdx]; elemIdx != invalidIndex; ) {
785 auto& elem = pool.get(elemIdx);
786 if ((elem.hash == hash) &&
787 equal(extract(elem.value), key)) {
790 elemIdx = elem.nextIdx;
796 PoolIndex* table =
nullptr;
798 unsigned allocMask = unsigned(-1);
799 unsigned elemCount = 0;
IValue * operator->() const
Iter & operator=(const Iter< HashSet2, IValue2 > &rhs)
Iter(const Iter< HashSet2, IValue2 > &other)
bool operator==(const Iter &rhs) const
IValue & operator*() const
std::forward_iterator_tag iterator_category
bool operator!=(const Iter &rhs) const
PoolIndex emplace(Args &&... args)
const Elem & get(PoolIndex idx) const
unsigned capacity() const
friend void swap(Pool &x, Pool &y) noexcept
Pool(Pool &&source) noexcept
PoolIndex create(V &&value, unsigned hash, PoolIndex nextIdx)
Pool & operator=(Pool &&source) noexcept
void destroy(PoolIndex idx)
Elem & get(PoolIndex idx)
void reserve(unsigned count)
hash_set(unsigned initialSize=0, Extractor extract_=Extractor(), Hasher hasher_=Hasher(), Equal equal_=Equal())
friend auto end(hash_set &s)
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)
std::pair< iterator, bool > insert(V &&value)
const_iterator end() const
std::pair< iterator, bool > emplace_noCapacityCheck(Args &&... args)
iterator insert_noCapacityCheck_noDuplicateCheck(V &&value)
const_iterator begin() const
hash_set(const hash_set &source)
iterator insert_noDuplicateCheck(V &&value)
Iter< const hash_set, const Value > const_iterator
hash_set(hash_set &&source) noexcept
iterator emplace_noDuplicateCheck(Args &&... args)
iterator find(const K &key)
const_iterator find(const K &key) const
Iter< hash_set, Value > iterator
void reserve(unsigned count)
hash_set & operator=(hash_set &&source) noexcept
friend auto end(const hash_set &s)
std::pair< iterator, bool > insert_noCapacityCheck(V &&value)
hash_set & operator=(const hash_set &source)
iterator emplace_noCapacityCheck_noDuplicateCheck(Args &&... args)
unsigned capacity() const
std::pair< iterator, bool > emplace(Args &&... args)
ALWAYS_INLINE unsigned count(const uint8_t *pIn, const uint8_t *pMatch, const uint8_t *pInLimit)
constexpr void fill(ForwardIt first, ForwardIt last, const T &value)
constexpr vecN< N, T > min(const vecN< N, T > &x, const vecN< N, T > &y)
constexpr bool operator==(PoolIndex i, PoolIndex j)
constexpr bool operator!=(PoolIndex i, PoolIndex j)
typename std::remove_cv< typename std::remove_reference< decltype(std::declval< Extractor >()(std::declval< Value >()))> ::type > ::type ExtractedType
constexpr KeyMatrixPosition x
Keyboard bindings.
constexpr Element(Args &&... args)
constexpr Element(V &&value_, unsigned hash_, PoolIndex nextIdx_)
T & operator()(T &&t) const
constexpr auto xrange(T e)