diff options
Diffstat (limited to 'absl/container/internal/raw_hash_set.cc')
-rw-r--r-- | absl/container/internal/raw_hash_set.cc | 26 |
1 files changed, 18 insertions, 8 deletions
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc index bfef071f..c63a2e02 100644 --- a/absl/container/internal/raw_hash_set.cc +++ b/absl/container/internal/raw_hash_set.cc @@ -23,7 +23,17 @@ namespace absl { ABSL_NAMESPACE_BEGIN namespace container_internal { +// A single block of empty control bytes for tables without any slots allocated. +// This enables removing a branch in the hot path of find(). +alignas(16) ABSL_CONST_INIT ABSL_DLL const ctrl_t kEmptyGroup[16] = { + ctrl_t::kSentinel, ctrl_t::kEmpty, ctrl_t::kEmpty, ctrl_t::kEmpty, + ctrl_t::kEmpty, ctrl_t::kEmpty, ctrl_t::kEmpty, ctrl_t::kEmpty, + ctrl_t::kEmpty, ctrl_t::kEmpty, ctrl_t::kEmpty, ctrl_t::kEmpty, + ctrl_t::kEmpty, ctrl_t::kEmpty, ctrl_t::kEmpty, ctrl_t::kEmpty}; + +#ifdef ABSL_INTERNAL_NEED_REDUNDANT_CONSTEXPR_DECL constexpr size_t Group::kWidth; +#endif // Returns "random" seed. inline size_t RandomSeed() { @@ -37,24 +47,24 @@ inline size_t RandomSeed() { return value ^ static_cast<size_t>(reinterpret_cast<uintptr_t>(&counter)); } -bool ShouldInsertBackwards(size_t hash, ctrl_t* ctrl) { +bool ShouldInsertBackwards(size_t hash, const ctrl_t* ctrl) { // To avoid problems with weak hashes and single bit tests, we use % 13. // TODO(kfm,sbenza): revisit after we do unconditional mixing return (H1(hash, ctrl) ^ RandomSeed()) % 13 > 6; } -void ConvertDeletedToEmptyAndFullToDeleted( - ctrl_t* ctrl, size_t capacity) { - assert(ctrl[capacity] == kSentinel); +void ConvertDeletedToEmptyAndFullToDeleted(ctrl_t* ctrl, size_t capacity) { + assert(ctrl[capacity] == ctrl_t::kSentinel); assert(IsValidCapacity(capacity)); - for (ctrl_t* pos = ctrl; pos != ctrl + capacity + 1; pos += Group::kWidth) { + for (ctrl_t* pos = ctrl; pos < ctrl + capacity; pos += Group::kWidth) { Group{pos}.ConvertSpecialToEmptyAndFullToDeleted(pos); } // Copy the cloned ctrl bytes. - std::memcpy(ctrl + capacity + 1, ctrl, Group::kWidth); - ctrl[capacity] = kSentinel; + std::memcpy(ctrl + capacity + 1, ctrl, NumClonedBytes()); + ctrl[capacity] = ctrl_t::kSentinel; } - +// Extern template instantiotion for inline function. +template FindInfo find_first_non_full(const ctrl_t*, size_t, size_t); } // namespace container_internal ABSL_NAMESPACE_END |