Differential D11057 Diff 36450 source/blender/blenlib/BLI_map.hh

Changeset View

Standalone View

source/blender/blenlib/BLI_map.hh

Show First 20 Lines • Show All 241 Lines • ▼ Show 20 Lines	public:
void add_new(Key &&key, const Value &value)		void add_new(Key &&key, const Value &value)
{		{
this->add_new_as(std::move(key), value);		this->add_new_as(std::move(key), value);
}		}
void add_new(Key &&key, Value &&value)		void add_new(Key &&key, Value &&value)
{		{
this->add_new_as(std::move(key), std::move(value));		this->add_new_as(std::move(key), std::move(value));
}		}
template<typename ForwardKey, typename ForwardValue>		template<typename ForwardKey, typename... ForwardValue>
void add_new_as(ForwardKey &&key, ForwardValue &&value)		void add_new_as(ForwardKey &&key, ForwardValue &&... value)
{		{
this->add_new__impl(		this->add_new__impl(
std::forward<ForwardKey>(key), std::forward<ForwardValue>(value), hash_(key));		std::forward<ForwardKey>(key), hash_(key), std::forward<ForwardValue>(value)...);
}		}

/**		/**
* Add a key-value-pair to the map. If the map contains the key already, nothing is changed.		* Add a key-value-pair to the map. If the map contains the key already, nothing is changed.
* If you want to replace the currently stored value, use `add_overwrite`.		* If you want to replace the currently stored value, use `add_overwrite`.
* Returns true when the key has been newly added.		* Returns true when the key has been newly added.
*		*
* This is similar to std::unordered_map::insert.		* This is similar to std::unordered_map::insert.
Show All 9 Lines	public:
bool add(Key &&key, const Value &value)		bool add(Key &&key, const Value &value)
{		{
return this->add_as(std::move(key), value);		return this->add_as(std::move(key), value);
}		}
bool add(Key &&key, Value &&value)		bool add(Key &&key, Value &&value)
{		{
return this->add_as(std::move(key), std::move(value));		return this->add_as(std::move(key), std::move(value));
}		}
template<typename ForwardKey, typename ForwardValue>		template<typename ForwardKey, typename... ForwardValue>
bool add_as(ForwardKey &&key, ForwardValue &&value)		bool add_as(ForwardKey &&key, ForwardValue &&... value)
{		{
return this->add__impl(		return this->add__impl(
std::forward<ForwardKey>(key), std::forward<ForwardValue>(value), hash_(key));		std::forward<ForwardKey>(key), hash_(key), std::forward<ForwardValue>(value)...);
}		}

/**		/**
* Adds a key-value-pair to the map. If the map contained the key already, the corresponding		* Adds a key-value-pair to the map. If the map contained the key already, the corresponding
* value will be replaced.		* value will be replaced.
* Returns true when the key has been newly added.		* Returns true when the key has been newly added.
*		*
* This is similar to std::unordered_map::insert_or_assign.		* This is similar to std::unordered_map::insert_or_assign.
Show All 9 Lines	public:
bool add_overwrite(Key &&key, const Value &value)		bool add_overwrite(Key &&key, const Value &value)
{		{
return this->add_overwrite_as(std::move(key), value);		return this->add_overwrite_as(std::move(key), value);
}		}
bool add_overwrite(Key &&key, Value &&value)		bool add_overwrite(Key &&key, Value &&value)
{		{
return this->add_overwrite_as(std::move(key), std::move(value));		return this->add_overwrite_as(std::move(key), std::move(value));
}		}
template<typename ForwardKey, typename ForwardValue>		template<typename ForwardKey, typename... ForwardValue>
bool add_overwrite_as(ForwardKey &&key, ForwardValue &&value)		bool add_overwrite_as(ForwardKey &&key, ForwardValue &&... value)
{		{
return this->add_overwrite__impl(		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)...);
}		}

/**		/**
* Returns true if there is a key in the map that compares equal to the given key.		* Returns true if there is a key in the map that compares equal to the given key.
*		*
* This is similar to std::unordered_map::contains.		* This is similar to std::unordered_map::contains.
*/		*/
bool contains(const Key &key) const		bool contains(const Key &key) const
▲ Show 20 Lines • Show All 85 Lines • ▼ Show 20 Lines	public:
Value pop_default(const Key &key, const Value &default_value)		Value pop_default(const Key &key, const Value &default_value)
{		{
return this->pop_default_as(key, default_value);		return this->pop_default_as(key, default_value);
}		}
Value pop_default(const Key &key, Value &&default_value)		Value pop_default(const Key &key, Value &&default_value)
{		{
return this->pop_default_as(key, std::move(default_value));		return this->pop_default_as(key, std::move(default_value));
}		}
template<typename ForwardKey, typename ForwardValue>		template<typename ForwardKey, typename... ForwardValue>
Value pop_default_as(const ForwardKey &key, ForwardValue &&default_value)		Value pop_default_as(const ForwardKey &key, ForwardValue &&... default_value)
{		{
Slot *slot = this->lookup_slot_ptr(key, hash_(key));		Slot *slot = this->lookup_slot_ptr(key, hash_(key));
if (slot == nullptr) {		if (slot == nullptr) {
return std::forward<ForwardValue>(default_value);		return Value(std::forward<ForwardValue>(default_value)...);
}		}
Value value = std::move(*slot->value());		Value value = std::move(*slot->value());
slot->remove();		slot->remove();
removed_slots_++;		removed_slots_++;
return value;		return value;
}		}

/**		/**
▲ Show 20 Lines • Show All 90 Lines • ▼ Show 20 Lines	public:
/**		/**
* Returns a copy of the value that corresponds to the given key. If the key is not in the		* Returns a copy of the value that corresponds to the given key. If the key is not in the
* map, the provided default_value is returned.		* map, the provided default_value is returned.
*/		*/
Value lookup_default(const Key &key, const Value &default_value) const		Value lookup_default(const Key &key, const Value &default_value) const
{		{
return this->lookup_default_as(key, default_value);		return this->lookup_default_as(key, default_value);
}		}
template<typename ForwardKey, typename ForwardValue>		template<typename ForwardKey, typename... ForwardValue>
Value lookup_default_as(const ForwardKey &key, ForwardValue &&default_value) const		Value lookup_default_as(const ForwardKey &key, ForwardValue &&... default_value) const
{		{
const Value *ptr = this->lookup_ptr_as(key);		const Value *ptr = this->lookup_ptr_as(key);
if (ptr != nullptr) {		if (ptr != nullptr) {
return *ptr;		return *ptr;
}		}
else {		else {
return std::forward<ForwardValue>(default_value);		return Value(std::forward<ForwardValue>(default_value)...);
}		}
}		}

/**		/**
* Returns a reference to the value corresponding to the given key. If the key is not in the map,		* Returns a reference to the value corresponding to the given key. If the key is not in the map,
* a new key-value-pair is added and a reference to the value in the map is returned.		* a new key-value-pair is added and a reference to the value in the map is returned.
*/		*/
Value &lookup_or_add(const Key &key, const Value &value)		Value &lookup_or_add(const Key &key, const Value &value)
{		{
return this->lookup_or_add_as(key, value);		return this->lookup_or_add_as(key, value);
}		}
Value &lookup_or_add(const Key &key, Value &&value)		Value &lookup_or_add(const Key &key, Value &&value)
{		{
return this->lookup_or_add_as(key, std::move(value));		return this->lookup_or_add_as(key, std::move(value));
}		}
Value &lookup_or_add(Key &&key, const Value &value)		Value &lookup_or_add(Key &&key, const Value &value)
{		{
return this->lookup_or_add_as(std::move(key), value);		return this->lookup_or_add_as(std::move(key), value);
}		}
Value &lookup_or_add(Key &&key, Value &&value)		Value &lookup_or_add(Key &&key, Value &&value)
{		{
return this->lookup_or_add_as(std::move(key), std::move(value));		return this->lookup_or_add_as(std::move(key), std::move(value));
}		}
template<typename ForwardKey, typename ForwardValue>		template<typename ForwardKey, typename... ForwardValue>
Value &lookup_or_add_as(ForwardKey &&key, ForwardValue &&value)		Value &lookup_or_add_as(ForwardKey &&key, ForwardValue &&... value)
{		{
return this->lookup_or_add__impl(		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)...);
}		}

/**		/**
* Returns a reference to the value that corresponds to the given key. If the key is not yet in		* Returns a reference to the value that corresponds to the given key. If the key is not yet in
* the map, it will be newly added.		* the map, it will be newly added.
*		*
* The create_value callback is only called when the key did not exist yet. It is expected to		* The create_value callback is only called when the key did not exist yet. It is expected to
* take no parameters and return the value to be inserted.		* take no parameters and return the value to be inserted.
▲ Show 20 Lines • Show All 404 Lines • ▼ Show 20 Lines	private:
}		}

void add_after_grow(Slot &old_slot, SlotArray &new_slots, uint64_t new_slot_mask)		void add_after_grow(Slot &old_slot, SlotArray &new_slots, uint64_t new_slot_mask)
{		{
uint64_t hash = old_slot.get_hash(Hash());		uint64_t hash = old_slot.get_hash(Hash());
SLOT_PROBING_BEGIN (ProbingStrategy, hash, new_slot_mask, slot_index) {		SLOT_PROBING_BEGIN (ProbingStrategy, hash, new_slot_mask, slot_index) {
Slot &slot = new_slots[slot_index];		Slot &slot = new_slots[slot_index];
if (slot.is_empty()) {		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;		return;
}		}
}		}
SLOT_PROBING_END();		SLOT_PROBING_END();
}		}

void noexcept_reset() noexcept		void noexcept_reset() noexcept
{		{
Allocator allocator = slots_.allocator();		Allocator allocator = slots_.allocator();
this->~Map();		this->~Map();
new (this) Map(NoExceptConstructor(), allocator);		new (this) Map(NoExceptConstructor(), allocator);
}		}

template<typename ForwardKey, typename ForwardValue>		template<typename ForwardKey, typename... ForwardValue>
void add_new__impl(ForwardKey &&key, ForwardValue &&value, uint64_t hash)		void add_new__impl(ForwardKey &&key, uint64_t hash, ForwardValue &&... value)
{		{
BLI_assert(!this->contains_as(key));		BLI_assert(!this->contains_as(key));

this->ensure_can_add();		this->ensure_can_add();

MAP_SLOT_PROBING_BEGIN (hash, slot) {		MAP_SLOT_PROBING_BEGIN (hash, slot) {
if (slot.is_empty()) {		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_++;		occupied_and_removed_slots_++;
return;		return;
}		}
}		}
MAP_SLOT_PROBING_END();		MAP_SLOT_PROBING_END();
}		}

template<typename ForwardKey, typename ForwardValue>		template<typename ForwardKey, typename... ForwardValue>
bool add__impl(ForwardKey &&key, ForwardValue &&value, uint64_t hash)		bool add__impl(ForwardKey &&key, uint64_t hash, ForwardValue &&... value)
{		{
this->ensure_can_add();		this->ensure_can_add();

MAP_SLOT_PROBING_BEGIN (hash, slot) {		MAP_SLOT_PROBING_BEGIN (hash, slot) {
if (slot.is_empty()) {		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_++;		occupied_and_removed_slots_++;
return true;		return true;
}		}
if (slot.contains(key, is_equal_, hash)) {		if (slot.contains(key, is_equal_, hash)) {
return false;		return false;
}		}
}		}
MAP_SLOT_PROBING_END();		MAP_SLOT_PROBING_END();
Show All 38 Lines	private:

template<typename ForwardKey, typename CreateValueF>		template<typename ForwardKey, typename CreateValueF>
Value &lookup_or_add_cb__impl(ForwardKey &&key, const CreateValueF &create_value, uint64_t hash)		Value &lookup_or_add_cb__impl(ForwardKey &&key, const CreateValueF &create_value, uint64_t hash)
{		{
this->ensure_can_add();		this->ensure_can_add();

MAP_SLOT_PROBING_BEGIN (hash, slot) {		MAP_SLOT_PROBING_BEGIN (hash, slot) {
if (slot.is_empty()) {		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_++;		occupied_and_removed_slots_++;
return *slot.value();		return *slot.value();
}		}
if (slot.contains(key, is_equal_, hash)) {		if (slot.contains(key, is_equal_, hash)) {
return *slot.value();		return *slot.value();
}		}
}		}
MAP_SLOT_PROBING_END();		MAP_SLOT_PROBING_END();
}		}

template<typename ForwardKey, typename ForwardValue>		template<typename ForwardKey, typename... ForwardValue>
Value &lookup_or_add__impl(ForwardKey &&key, ForwardValue &&value, uint64_t hash)		Value &lookup_or_add__impl(ForwardKey &&key, uint64_t hash, ForwardValue &&... value)
{		{
this->ensure_can_add();		this->ensure_can_add();

MAP_SLOT_PROBING_BEGIN (hash, slot) {		MAP_SLOT_PROBING_BEGIN (hash, slot) {
if (slot.is_empty()) {		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_++;		occupied_and_removed_slots_++;
return *slot.value();		return *slot.value();
}		}
if (slot.contains(key, is_equal_, hash)) {		if (slot.contains(key, is_equal_, hash)) {
return *slot.value();		return *slot.value();
}		}
}		}
MAP_SLOT_PROBING_END();		MAP_SLOT_PROBING_END();
}		}

template<typename ForwardKey, typename ForwardValue>		template<typename ForwardKey, typename... ForwardValue>
bool add_overwrite__impl(ForwardKey &&key, ForwardValue &&value, uint64_t hash)		bool add_overwrite__impl(ForwardKey &&key, uint64_t hash, ForwardValue &&... value)
{		{
auto create_func = [&](Value *ptr) {		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;		return true;
};		};
auto modify_func = [&](Value *ptr) {		auto modify_func = [&](Value *ptr) {
*ptr = std::forward<ForwardValue>(value);		*ptr = Value(std::forward<ForwardValue>(value)...);
return false;		return false;
};		};
return this->add_or_modify__impl(		return this->add_or_modify__impl(
std::forward<ForwardKey>(key), create_func, modify_func, hash);		std::forward<ForwardKey>(key), create_func, modify_func, hash);
}		}

template<typename ForwardKey>		template<typename ForwardKey>
const Slot &lookup_slot(const ForwardKey &key, const uint64_t hash) const		const Slot &lookup_slot(const ForwardKey &key, const uint64_t hash) const
▲ Show 20 Lines • Show All 92 Lines • ▼ Show 20 Lines	bool is_empty() const
return map_.empty();		return map_.empty();
}		}

void reserve(int64_t n)		void reserve(int64_t n)
{		{
map_.reserve(n);		map_.reserve(n);
}		}

template<typename ForwardKey, typename ForwardValue>		template<typename ForwardKey, typename... ForwardValue>
void add_new(ForwardKey &&key, ForwardValue &&value)		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>		template<typename ForwardKey, typename... ForwardValue>
bool add(ForwardKey &&key, ForwardValue &&value)		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		bool contains(const Key &key) const
{		{
return map_.find(key) != map_.end();		return map_.find(key) != map_.end();
}		}

bool remove(const Key &key)		bool remove(const Key &key)
Show All 25 Lines