Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/source/blender/blenlib/BLI_map.hh
diff options
context:
space:
mode:
Diffstat (limited to 'source/blender/blenlib/BLI_map.hh')
-rw-r--r--source/blender/blenlib/BLI_map.hh195
1 files changed, 129 insertions, 66 deletions
diff --git a/source/blender/blenlib/BLI_map.hh b/source/blender/blenlib/BLI_map.hh
index 9fa69853e44..4d254960f34 100644
--- a/source/blender/blenlib/BLI_map.hh
+++ b/source/blender/blenlib/BLI_map.hh
@@ -247,11 +247,11 @@ class Map {
{
this->add_new_as(std::move(key), std::move(value));
}
- template<typename ForwardKey, typename ForwardValue>
- void add_new_as(ForwardKey &&key, ForwardValue &&value)
+ template<typename ForwardKey, typename... ForwardValue>
+ void add_new_as(ForwardKey &&key, ForwardValue &&... value)
{
this->add_new__impl(
- std::forward<ForwardKey>(key), std::forward<ForwardValue>(value), hash_(key));
+ std::forward<ForwardKey>(key), hash_(key), std::forward<ForwardValue>(value)...);
}
/**
@@ -277,11 +277,11 @@ class Map {
{
return this->add_as(std::move(key), std::move(value));
}
- template<typename ForwardKey, typename ForwardValue>
- bool add_as(ForwardKey &&key, ForwardValue &&value)
+ template<typename ForwardKey, typename... ForwardValue>
+ bool add_as(ForwardKey &&key, ForwardValue &&... value)
{
return this->add__impl(
- std::forward<ForwardKey>(key), std::forward<ForwardValue>(value), hash_(key));
+ std::forward<ForwardKey>(key), hash_(key), std::forward<ForwardValue>(value)...);
}
/**
@@ -307,11 +307,11 @@ class Map {
{
return this->add_overwrite_as(std::move(key), std::move(value));
}
- template<typename ForwardKey, typename ForwardValue>
- bool add_overwrite_as(ForwardKey &&key, ForwardValue &&value)
+ template<typename ForwardKey, typename... ForwardValue>
+ bool add_overwrite_as(ForwardKey &&key, ForwardValue &&... value)
{
return this->add_overwrite__impl(
- std::forward<ForwardKey>(key), std::forward<ForwardValue>(value), hash_(key));
+ std::forward<ForwardKey>(key), hash_(key), std::forward<ForwardValue>(value)...);
}
/**
@@ -413,12 +413,12 @@ class Map {
{
return this->pop_default_as(key, std::move(default_value));
}
- template<typename ForwardKey, typename ForwardValue>
- Value pop_default_as(const ForwardKey &key, ForwardValue &&default_value)
+ template<typename ForwardKey, typename... ForwardValue>
+ Value pop_default_as(const ForwardKey &key, ForwardValue &&... default_value)
{
Slot *slot = this->lookup_slot_ptr(key, hash_(key));
if (slot == nullptr) {
- return std::forward<ForwardValue>(default_value);
+ return Value(std::forward<ForwardValue>(default_value)...);
}
Value value = std::move(*slot->value());
slot->remove();
@@ -525,15 +525,15 @@ class Map {
{
return this->lookup_default_as(key, default_value);
}
- template<typename ForwardKey, typename ForwardValue>
- Value lookup_default_as(const ForwardKey &key, ForwardValue &&default_value) const
+ template<typename ForwardKey, typename... ForwardValue>
+ Value lookup_default_as(const ForwardKey &key, ForwardValue &&... default_value) const
{
const Value *ptr = this->lookup_ptr_as(key);
if (ptr != nullptr) {
return *ptr;
}
else {
- return std::forward<ForwardValue>(default_value);
+ return Value(std::forward<ForwardValue>(default_value)...);
}
}
@@ -557,11 +557,11 @@ class Map {
{
return this->lookup_or_add_as(std::move(key), std::move(value));
}
- template<typename ForwardKey, typename ForwardValue>
- Value &lookup_or_add_as(ForwardKey &&key, ForwardValue &&value)
+ template<typename ForwardKey, typename... ForwardValue>
+ Value &lookup_or_add_as(ForwardKey &&key, ForwardValue &&... value)
{
return this->lookup_or_add__impl(
- std::forward<ForwardKey>(key), std::forward<ForwardValue>(value), hash_(key));
+ std::forward<ForwardKey>(key), hash_(key), std::forward<ForwardValue>(value)...);
}
/**
@@ -605,6 +605,37 @@ class Map {
}
/**
+ * Returns the key that is stored in the set that compares equal to the given key. This invokes
+ * undefined behavior when the key is not in the map.
+ */
+ const Key &lookup_key(const Key &key) const
+ {
+ return this->lookup_key_as(key);
+ }
+ template<typename ForwardKey> const Key &lookup_key_as(const ForwardKey &key) const
+ {
+ const Slot &slot = this->lookup_slot(key, hash_(key));
+ return *slot.key();
+ }
+
+ /**
+ * Returns a pointer to the key that is stored in the map that compares equal to the given key.
+ * If the key is not in the map, null is returned.
+ */
+ const Key *lookup_key_ptr(const Key &key) const
+ {
+ return this->lookup_key_ptr_as(key);
+ }
+ template<typename ForwardKey> const Key *lookup_key_ptr_as(const ForwardKey &key) const
+ {
+ const Slot *slot = this->lookup_slot_ptr(key, hash_(key));
+ if (slot == nullptr) {
+ return nullptr;
+ }
+ return slot->key();
+ }
+
+ /**
* Calls the provided callback for every key-value-pair in the map. The callback is expected
* to take a `const Key &` as first and a `const Value &` as second parameter.
*/
@@ -621,19 +652,23 @@ class Map {
}
}
- /**
- * A utility iterator that reduces the amount of code when implementing the actual iterators.
- * This uses the "curiously recurring template pattern" (CRTP).
- */
- template<typename SubIterator> struct BaseIterator {
+ /* Common base class for all iterators below. */
+ struct BaseIterator {
+ public:
using iterator_category = std::forward_iterator_tag;
using difference_type = std::ptrdiff_t;
+ protected:
+ /* We could have separate base iterators for const and non-const iterators, but that would add
+ * more complexity than benefits right now. */
Slot *slots_;
int64_t total_slots_;
int64_t current_slot_;
- BaseIterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
+ friend Map;
+
+ public:
+ BaseIterator(const Slot *slots, const int64_t total_slots, const int64_t current_slot)
: slots_(const_cast<Slot *>(slots)), total_slots_(total_slots), current_slot_(current_slot)
{
}
@@ -667,11 +702,29 @@ class Map {
return !(a != b);
}
+ protected:
+ Slot &current_slot() const
+ {
+ return slots_[current_slot_];
+ }
+ };
+
+ /**
+ * A utility iterator that reduces the amount of code when implementing the actual iterators.
+ * This uses the "curiously recurring template pattern" (CRTP).
+ */
+ template<typename SubIterator> class BaseIteratorRange : public BaseIterator {
+ public:
+ BaseIteratorRange(const Slot *slots, int64_t total_slots, int64_t current_slot)
+ : BaseIterator(slots, total_slots, current_slot)
+ {
+ }
+
SubIterator begin() const
{
- for (int64_t i = 0; i < total_slots_; i++) {
- if (slots_[i].is_occupied()) {
- return SubIterator(slots_, total_slots_, i);
+ for (int64_t i = 0; i < this->total_slots_; i++) {
+ if (this->slots_[i].is_occupied()) {
+ return SubIterator(this->slots_, this->total_slots_, i);
}
}
return this->end();
@@ -679,23 +732,18 @@ class Map {
SubIterator end() const
{
- return SubIterator(slots_, total_slots_, total_slots_);
- }
-
- Slot &current_slot() const
- {
- return slots_[current_slot_];
+ return SubIterator(this->slots_, this->total_slots_, this->total_slots_);
}
};
- class KeyIterator final : public BaseIterator<KeyIterator> {
+ class KeyIterator final : public BaseIteratorRange<KeyIterator> {
public:
using value_type = Key;
using pointer = const Key *;
using reference = const Key &;
KeyIterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
- : BaseIterator<KeyIterator>(slots, total_slots, current_slot)
+ : BaseIteratorRange<KeyIterator>(slots, total_slots, current_slot)
{
}
@@ -705,14 +753,14 @@ class Map {
}
};
- class ValueIterator final : public BaseIterator<ValueIterator> {
+ class ValueIterator final : public BaseIteratorRange<ValueIterator> {
public:
using value_type = Value;
using pointer = const Value *;
using reference = const Value &;
ValueIterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
- : BaseIterator<ValueIterator>(slots, total_slots, current_slot)
+ : BaseIteratorRange<ValueIterator>(slots, total_slots, current_slot)
{
}
@@ -722,14 +770,14 @@ class Map {
}
};
- class MutableValueIterator final : public BaseIterator<MutableValueIterator> {
+ class MutableValueIterator final : public BaseIteratorRange<MutableValueIterator> {
public:
using value_type = Value;
using pointer = Value *;
using reference = Value &;
- MutableValueIterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
- : BaseIterator<MutableValueIterator>(slots, total_slots, current_slot)
+ MutableValueIterator(Slot *slots, int64_t total_slots, int64_t current_slot)
+ : BaseIteratorRange<MutableValueIterator>(slots, total_slots, current_slot)
{
}
@@ -754,14 +802,14 @@ class Map {
}
};
- class ItemIterator final : public BaseIterator<ItemIterator> {
+ class ItemIterator final : public BaseIteratorRange<ItemIterator> {
public:
using value_type = Item;
using pointer = Item *;
using reference = Item &;
ItemIterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
- : BaseIterator<ItemIterator>(slots, total_slots, current_slot)
+ : BaseIteratorRange<ItemIterator>(slots, total_slots, current_slot)
{
}
@@ -772,14 +820,14 @@ class Map {
}
};
- class MutableItemIterator final : public BaseIterator<MutableItemIterator> {
+ class MutableItemIterator final : public BaseIteratorRange<MutableItemIterator> {
public:
using value_type = MutableItem;
using pointer = MutableItem *;
using reference = MutableItem &;
- MutableItemIterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
- : BaseIterator<MutableItemIterator>(slots, total_slots, current_slot)
+ MutableItemIterator(Slot *slots, int64_t total_slots, int64_t current_slot)
+ : BaseIteratorRange<MutableItemIterator>(slots, total_slots, current_slot)
{
}
@@ -840,6 +888,19 @@ class Map {
}
/**
+ * Remove the key-value-pair that the iterator is currently pointing at.
+ * It is valid to call this method while iterating over the map. However, after this method has
+ * been called, the removed element must not be accessed anymore.
+ */
+ void remove(const BaseIterator &iterator)
+ {
+ Slot &slot = iterator.current_slot();
+ BLI_assert(slot.is_occupied());
+ slot.remove();
+ removed_slots_++;
+ }
+
+ /**
* Print common statistics like size and collision count. This is useful for debugging purposes.
*/
void print_stats(StringRef name = "") const
@@ -982,7 +1043,7 @@ class Map {
SLOT_PROBING_BEGIN (ProbingStrategy, hash, new_slot_mask, slot_index) {
Slot &slot = new_slots[slot_index];
if (slot.is_empty()) {
- slot.occupy(std::move(*old_slot.key()), std::move(*old_slot.value()), hash);
+ slot.occupy(std::move(*old_slot.key()), hash, std::move(*old_slot.value()));
return;
}
}
@@ -996,8 +1057,8 @@ class Map {
new (this) Map(NoExceptConstructor(), allocator);
}
- template<typename ForwardKey, typename ForwardValue>
- void add_new__impl(ForwardKey &&key, ForwardValue &&value, uint64_t hash)
+ template<typename ForwardKey, typename... ForwardValue>
+ void add_new__impl(ForwardKey &&key, uint64_t hash, ForwardValue &&... value)
{
BLI_assert(!this->contains_as(key));
@@ -1005,7 +1066,7 @@ class Map {
MAP_SLOT_PROBING_BEGIN (hash, slot) {
if (slot.is_empty()) {
- slot.occupy(std::forward<ForwardKey>(key), std::forward<ForwardValue>(value), hash);
+ slot.occupy(std::forward<ForwardKey>(key), hash, std::forward<ForwardValue>(value)...);
occupied_and_removed_slots_++;
return;
}
@@ -1013,14 +1074,14 @@ class Map {
MAP_SLOT_PROBING_END();
}
- template<typename ForwardKey, typename ForwardValue>
- bool add__impl(ForwardKey &&key, ForwardValue &&value, uint64_t hash)
+ template<typename ForwardKey, typename... ForwardValue>
+ bool add__impl(ForwardKey &&key, uint64_t hash, ForwardValue &&... value)
{
this->ensure_can_add();
MAP_SLOT_PROBING_BEGIN (hash, slot) {
if (slot.is_empty()) {
- slot.occupy(std::forward<ForwardKey>(key), std::forward<ForwardValue>(value), hash);
+ slot.occupy(std::forward<ForwardKey>(key), hash, std::forward<ForwardValue>(value)...);
occupied_and_removed_slots_++;
return true;
}
@@ -1075,7 +1136,7 @@ class Map {
MAP_SLOT_PROBING_BEGIN (hash, slot) {
if (slot.is_empty()) {
- slot.occupy(std::forward<ForwardKey>(key), create_value(), hash);
+ slot.occupy(std::forward<ForwardKey>(key), hash, create_value());
occupied_and_removed_slots_++;
return *slot.value();
}
@@ -1086,14 +1147,14 @@ class Map {
MAP_SLOT_PROBING_END();
}
- template<typename ForwardKey, typename ForwardValue>
- Value &lookup_or_add__impl(ForwardKey &&key, ForwardValue &&value, uint64_t hash)
+ template<typename ForwardKey, typename... ForwardValue>
+ Value &lookup_or_add__impl(ForwardKey &&key, uint64_t hash, ForwardValue &&... value)
{
this->ensure_can_add();
MAP_SLOT_PROBING_BEGIN (hash, slot) {
if (slot.is_empty()) {
- slot.occupy(std::forward<ForwardKey>(key), std::forward<ForwardValue>(value), hash);
+ slot.occupy(std::forward<ForwardKey>(key), hash, std::forward<ForwardValue>(value)...);
occupied_and_removed_slots_++;
return *slot.value();
}
@@ -1104,15 +1165,15 @@ class Map {
MAP_SLOT_PROBING_END();
}
- template<typename ForwardKey, typename ForwardValue>
- bool add_overwrite__impl(ForwardKey &&key, ForwardValue &&value, uint64_t hash)
+ template<typename ForwardKey, typename... ForwardValue>
+ bool add_overwrite__impl(ForwardKey &&key, uint64_t hash, ForwardValue &&... value)
{
auto create_func = [&](Value *ptr) {
- new (static_cast<void *>(ptr)) Value(std::forward<ForwardValue>(value));
+ new (static_cast<void *>(ptr)) Value(std::forward<ForwardValue>(value)...);
return true;
};
auto modify_func = [&](Value *ptr) {
- *ptr = std::forward<ForwardValue>(value);
+ *ptr = Value(std::forward<ForwardValue>(value)...);
return false;
};
return this->add_or_modify__impl(
@@ -1221,16 +1282,18 @@ template<typename Key, typename Value> class StdUnorderedMapWrapper {
map_.reserve(n);
}
- template<typename ForwardKey, typename ForwardValue>
- void add_new(ForwardKey &&key, ForwardValue &&value)
+ template<typename ForwardKey, typename... ForwardValue>
+ void add_new(ForwardKey &&key, ForwardValue &&... value)
{
- map_.insert({std::forward<ForwardKey>(key), std::forward<ForwardValue>(value)});
+ map_.insert({std::forward<ForwardKey>(key), Value(std::forward<ForwardValue>(value)...)});
}
- template<typename ForwardKey, typename ForwardValue>
- bool add(ForwardKey &&key, ForwardValue &&value)
+ template<typename ForwardKey, typename... ForwardValue>
+ bool add(ForwardKey &&key, ForwardValue &&... value)
{
- return map_.insert({std::forward<ForwardKey>(key), std::forward<ForwardValue>(value)}).second;
+ return map_
+ .insert({std::forward<ForwardKey>(key), Value(std::forward<ForwardValue>(value)...)})
+ .second;
}
bool contains(const Key &key) const
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-18 05:06:59 +0300