14#include <initializer_list>
31template <
typename T,
typename K,
typename Traits = T>
43 fCapacity = that.fCapacity;
44 fSlots.reset(
new Slot[that.fCapacity]);
45 for (
int i = 0; i < fCapacity; i++) {
46 fSlots[i] = that.fSlots[i];
55 fCapacity = that.fCapacity;
56 fSlots = std::move(that.fSlots);
58 that.fCount = that.fCapacity = 0;
67 int count()
const {
return fCount; }
89 if (4 * fCount >= 3 * fCapacity) {
90 this->
resize(fCapacity > 0 ? fCapacity * 2 : 4);
92 return this->uncheckedSet(std::move(val));
98 int index =
hash & (fCapacity-1);
99 for (
int n = 0; n < fCapacity; n++) {
100 Slot&
s = fSlots[index];
104 if (
hash ==
s.fHash &&
key == Traits::GetKey(*
s)) {
107 index = this->next(index);
116 if (
T* p = this->
find(key)) {
126 int index =
hash & (fCapacity-1);
127 for (
int n = 0; n < fCapacity; n++) {
128 Slot&
s = fSlots[index];
132 if (
hash ==
s.fHash &&
key == Traits::GetKey(*
s)) {
133 this->removeSlot(index);
134 if (4 * fCount <= fCapacity && fCapacity > 4) {
135 this->
resize(fCapacity / 2);
139 index = this->next(index);
154 int oldCapacity = fCapacity;
159 std::unique_ptr<Slot[]> oldSlots = std::move(fSlots);
162 for (
int i = 0; i < oldCapacity; i++) {
163 Slot&
s = oldSlots[i];
165 this->uncheckedSet(*std::move(
s));
172 template <
typename Fn>
173 void foreach(Fn&& fn) {
174 for (
int i = 0; i < fCapacity; i++) {
175 if (fSlots[i].has_value()) {
182 template <
typename Fn>
183 void foreach(Fn&& fn)
const {
184 for (
int i = 0; i < fCapacity; i++) {
185 if (fSlots[i].has_value()) {
194 template <
typename SlotVal>
224 return !(*
this == that);
245 int firstPopulatedSlot()
const {
246 for (
int i = 0; i < fCapacity; i++) {
247 if (fSlots[i].has_value()) {
255 int nextPopulatedSlot(
int currentSlot)
const {
256 for (
int i = currentSlot + 1; i < fCapacity; i++) {
257 if (fSlots[i].has_value()) {
265 const T* slot(
int i)
const {
270 T* uncheckedSet(
T&& val) {
271 const K&
key = Traits::GetKey(val);
274 int index =
hash & (fCapacity-1);
275 for (
int n = 0; n < fCapacity; n++) {
276 Slot&
s = fSlots[index];
279 s.emplace(std::move(val),
hash);
283 if (
hash ==
s.fHash &&
key == Traits::GetKey(*
s)) {
286 s.emplace(std::move(val),
hash);
290 index = this->next(index);
296 void removeSlot(
int index) {
301 Slot& emptySlot = fSlots[index];
302 int emptyIndex = index;
311 index = this->next(index);
312 Slot&
s = fSlots[index];
318 originalIndex =
s.fHash & (fCapacity - 1);
319 }
while ((index <= originalIndex && originalIndex < emptyIndex)
320 || (originalIndex < emptyIndex && emptyIndex < index)
321 || (emptyIndex < index && index <= originalIndex));
323 Slot& moveFrom = fSlots[index];
324 emptySlot = std::move(moveFrom);
328 int next(
int index)
const {
330 if (index < 0) { index += fCapacity; }
334 static uint32_t Hash(
const K&
key) {
335 uint32_t
hash = Traits::Hash(
key) & 0xffffffff;
342 ~Slot() { this->
reset(); }
344 Slot(
const Slot& that) { *
this = that; }
345 Slot& operator=(
const Slot& that) {
351 fVal.fStorage = that.fVal.fStorage;
358 new (&fVal.fStorage)
T(that.fVal.fStorage);
367 Slot(Slot&& that) { *
this = std::move(that); }
368 Slot& operator=(Slot&& that) {
374 fVal.fStorage = std::move(that.fVal.fStorage);
381 new (&fVal.fStorage)
T(std::move(that.fVal.fStorage));
391 const T&
operator*() const& {
return fVal.fStorage; }
392 T&&
operator*() && {
return std::move(fVal.fStorage); }
393 const T&&
operator*() const&& {
return std::move(fVal.fStorage); }
395 Slot& emplace(
T&& v, uint32_t
h) {
397 new (&fVal.fStorage)
T(std::move(v));
402 bool has_value()
const {
return fHash != 0; }
403 explicit operator bool()
const {
return this->has_value(); }
404 bool empty()
const {
return !this->has_value(); }
425 std::unique_ptr<Slot[]> fSlots;
430template <
typename K,
typename V,
typename HashK = SkGoodHash>
443 struct Pair :
public std::pair<K, V> {
444 using std::pair<
K,
V>::pair;
450 fTable.resize(pairs.size() * 5 / 3);
451 for (
const Pair& p : pairs) {
460 int count()
const {
return fTable.count(); }
463 bool empty()
const {
return fTable.count() == 0; }
473 Pair* out = fTable.set({std::move(
key), std::move(val)});
480 if (
Pair* p = fTable.find(
key)) {
487 if (
V* val = this->
find(key)) {
500 return fTable.removeIfExists(
key);
504 template <
typename Fn,
505 std::enable_if_t<std::is_invocable_v<Fn, K, V*>>* =
nullptr>
506 void foreach(Fn&& fn) {
507 fTable.foreach([&fn](
Pair* p) { fn(p->first, &p->second); });
511 template <
typename Fn,
512 std::enable_if_t<std::is_invocable_v<Fn, K, V>>* =
nullptr>
513 void foreach(Fn&& fn)
const {
514 fTable.foreach([&fn](
const Pair& p) { fn(p.first, p.second); });
518 template <
typename Fn,
519 std::enable_if_t<std::is_invocable_v<Fn, Pair>>* =
nullptr>
520 void foreach(Fn&& fn)
const {
521 fTable.foreach([&fn](
const Pair& p) { fn(p); });
528 return Iter::MakeBegin(&fTable);
532 return Iter::MakeEnd(&fTable);
540template <
typename T,
typename HashT = SkGoodHash>
554 fTable.
resize(vals.size() * 5 / 3);
555 for (
const T& val : vals) {
573 void add(
T item) { fTable.
set(std::move(item)); }
580 const T*
find(
const T& item)
const {
return fTable.
find(item); }
589 template <
typename Fn>
590 void foreach (Fn&& fn)
const {
596 static const T& GetKey(
const T& item) {
return item; }
597 static auto Hash(
const T& item) {
return HashT()(item); }
604 return Iter::MakeBegin(&fTable);
608 return Iter::MakeEnd(&fTable);
#define SkAssertResult(cond)
static uint32_t hash(const SkShaderBase::GradientInfo &v)
static constexpr bool SkToBool(const T &x)
THashMap< K, V, HashK > & operator=(const THashMap< K, V, HashK > &that)=default
V & operator[](const K &key)
THashMap< K, V, HashK > & operator=(THashMap< K, V, HashK > &&that)=default
size_t approxBytesUsed() const
V * find(const K &key) const
THashMap(const THashMap< K, V, HashK > &that)=default
THashMap(THashMap< K, V, HashK > &&that)=default
bool removeIfExists(const K &key)
void remove(const K &key)
THashMap(std::initializer_list< Pair > pairs)
typename THashTable< Pair, K >::template Iter< std::pair< K, V > > Iter
THashSet(THashSet< T, HashT > &&that)=default
THashSet< T, HashT > & operator=(THashSet< T, HashT > &&that)=default
const T * find(const T &item) const
THashSet(std::initializer_list< T > vals)
size_t approxBytesUsed() const
bool contains(const T &item) const
THashSet< T, HashT > & operator=(const THashSet< T, HashT > &that)=default
typename THashTable< T, T, Traits >::template Iter< T > Iter
void remove(const T &item)
THashSet(const THashSet< T, HashT > &that)=default
bool operator==(const Iter &that) const
const SlotVal * operator->() const
bool operator!=(const Iter &that) const
static Iter MakeEnd(const TTable *table)
const SlotVal & operator*() const
Iter(const TTable *table, int slot)
static Iter MakeBegin(const TTable *table)
void remove(const K &key)
THashTable & operator=(THashTable &&that)
void resize(int capacity)
THashTable(const THashTable &that)
THashTable(THashTable &&that)
THashTable & operator=(const THashTable &that)
T * find(const K &key) const
T findOrNull(const K &key) const
size_t approxBytesUsed() const
bool removeIfExists(const K &key)
EMSCRIPTEN_KEEPALIVE void empty()
T __attribute__((ext_vector_type(N))) V
constexpr Color operator*(T value, const Color &c)
static auto Hash(const K &key)
static const K & GetKey(const Pair &p)