From f5ca34d0b41b88e02e373d810ee8a6718e0c6f41 Mon Sep 17 00:00:00 2001 From: Jacques Lucke Date: Mon, 24 Aug 2020 19:02:41 +0200 Subject: BLI: simplify lookup methods in Map No functional changes expected. --- source/blender/blenlib/BLI_map.hh | 164 ++++++++++++++------------------------ 1 file changed, 61 insertions(+), 103 deletions(-) (limited to 'source/blender/blenlib/BLI_map.hh') diff --git a/source/blender/blenlib/BLI_map.hh b/source/blender/blenlib/BLI_map.hh index e901b2de4bf..08fe1a3cdbc 100644 --- a/source/blender/blenlib/BLI_map.hh +++ b/source/blender/blenlib/BLI_map.hh @@ -316,7 +316,7 @@ class Map { } template bool contains_as(const ForwardKey &key) const { - return this->contains__impl(key, hash_(key)); + return this->lookup_slot_ptr(key, hash_(key)) != nullptr; } /** @@ -331,7 +331,13 @@ class Map { } template bool remove_as(const ForwardKey &key) { - return this->remove__impl(key, hash_(key)); + Slot *slot = this->lookup_slot_ptr(key, hash_(key)); + if (slot == nullptr) { + return false; + } + slot->remove(); + removed_slots_++; + return true; } /** @@ -344,7 +350,9 @@ class Map { } template void remove_contained_as(const ForwardKey &key) { - this->remove_contained__impl(key, hash_(key)); + Slot &slot = this->lookup_slot(key, hash_(key)); + slot.remove(); + removed_slots_++; } /** @@ -357,7 +365,11 @@ class Map { } template Value pop_as(const ForwardKey &key) { - return this->pop__impl(key, hash_(key)); + Slot &slot = this->lookup_slot(key, hash_(key)); + Value value = std::move(*slot.value()); + slot.remove(); + removed_slots_++; + return value; } /** @@ -370,7 +382,14 @@ class Map { } template std::optional pop_try_as(const ForwardKey &key) { - return this->pop_try__impl(key, hash_(key)); + Slot *slot = this->lookup_slot_ptr(key, hash_(key)); + if (slot == nullptr) { + return {}; + } + std::optional value = std::move(*slot->value()); + slot->remove(); + removed_slots_++; + return value; } /** @@ -388,7 +407,14 @@ class Map { template Value pop_default_as(const ForwardKey &key, ForwardValue &&default_value) { - return this->pop_default__impl(key, std::forward(default_value), hash_(key)); + Slot *slot = this->lookup_slot_ptr(key, hash_(key)); + if (slot == nullptr) { + return std::forward(default_value); + } + Value value = std::move(*slot->value()); + slot->remove(); + removed_slots_++; + return value; } /** @@ -449,11 +475,12 @@ class Map { } template const Value *lookup_ptr_as(const ForwardKey &key) const { - return this->lookup_ptr__impl(key, hash_(key)); + const Slot *slot = this->lookup_slot_ptr(key, hash_(key)); + return (slot != nullptr) ? slot->value() : nullptr; } template Value *lookup_ptr_as(const ForwardKey &key) { - return const_cast(this->lookup_ptr__impl(key, hash_(key))); + return const_cast(const_cast(this)->lookup_ptr_as(key)); } /** @@ -925,19 +952,6 @@ class Map { new (this) Map(NoExceptConstructor(), allocator); } - template bool contains__impl(const ForwardKey &key, uint64_t hash) const - { - MAP_SLOT_PROBING_BEGIN (hash, slot) { - if (slot.is_empty()) { - return false; - } - if (slot.contains(key, is_equal_, hash)) { - return true; - } - } - MAP_SLOT_PROBING_END(); - } - template void add_new__impl(ForwardKey &&key, ForwardValue &&value, uint64_t hash) { @@ -973,84 +987,6 @@ class Map { MAP_SLOT_PROBING_END(); } - template bool remove__impl(const ForwardKey &key, uint64_t hash) - { - MAP_SLOT_PROBING_BEGIN (hash, slot) { - if (slot.contains(key, is_equal_, hash)) { - slot.remove(); - removed_slots_++; - return true; - } - if (slot.is_empty()) { - return false; - } - } - MAP_SLOT_PROBING_END(); - } - - template void remove_contained__impl(const ForwardKey &key, uint64_t hash) - { - BLI_assert(this->contains_as(key)); - - MAP_SLOT_PROBING_BEGIN (hash, slot) { - if (slot.contains(key, is_equal_, hash)) { - slot.remove(); - removed_slots_++; - return; - } - } - MAP_SLOT_PROBING_END(); - } - - template Value pop__impl(const ForwardKey &key, uint64_t hash) - { - BLI_assert(this->contains_as(key)); - - MAP_SLOT_PROBING_BEGIN (hash, slot) { - if (slot.contains(key, is_equal_, hash)) { - Value value = std::move(*slot.value()); - slot.remove(); - removed_slots_++; - return value; - } - } - MAP_SLOT_PROBING_END(); - } - - template - std::optional pop_try__impl(const ForwardKey &key, uint64_t hash) - { - MAP_SLOT_PROBING_BEGIN (hash, slot) { - if (slot.contains(key, is_equal_, hash)) { - std::optional value = std::move(*slot.value()); - slot.remove(); - removed_slots_++; - return value; - } - if (slot.is_empty()) { - return {}; - } - } - MAP_SLOT_PROBING_END(); - } - - template - Value pop_default__impl(const ForwardKey &key, ForwardValue &&default_value, uint64_t hash) - { - MAP_SLOT_PROBING_BEGIN (hash, slot) { - if (slot.contains(key, is_equal_, hash)) { - Value value = std::move(*slot.value()); - slot.remove(); - removed_slots_++; - return value; - } - if (slot.is_empty()) { - return std::forward(default_value); - } - } - MAP_SLOT_PROBING_END(); - } - template auto add_or_modify__impl(ForwardKey &&key, const CreateValueF &create_value, @@ -1140,19 +1076,41 @@ class Map { } template - const Value *lookup_ptr__impl(const ForwardKey &key, uint64_t hash) const + const Slot &lookup_slot(const ForwardKey &key, const uint64_t hash) const { + BLI_assert(this->contains_as(key)); MAP_SLOT_PROBING_BEGIN (hash, slot) { - if (slot.is_empty()) { - return nullptr; + if (slot.contains(key, is_equal_, hash)) { + return slot; } + } + MAP_SLOT_PROBING_END(); + } + + template Slot &lookup_slot(const ForwardKey &key, const uint64_t hash) + { + return const_cast(const_cast(this)->lookup_slot(key, hash)); + } + + template + const Slot *lookup_slot_ptr(const ForwardKey &key, const uint64_t hash) const + { + MAP_SLOT_PROBING_BEGIN (hash, slot) { if (slot.contains(key, is_equal_, hash)) { - return slot.value(); + return &slot; + } + if (slot.is_empty()) { + return nullptr; } } MAP_SLOT_PROBING_END(); } + template Slot *lookup_slot_ptr(const ForwardKey &key, const uint64_t hash) + { + return const_cast(const_cast(this)->lookup_slot_ptr(key, hash)); + } + template int64_t count_collisions__impl(const ForwardKey &key, uint64_t hash) const { -- cgit v1.2.3