BLI: Improve forwarding semantics of some data structures

This makes it possible to use e.g. `std::unique_ptr` in a map.
This commit is contained in:
Jacques Lucke 2019-09-14 12:11:14 +02:00
parent ca76ecfa0e
commit 79e1165bd7
13 changed files with 345 additions and 152 deletions

View File

@ -89,6 +89,13 @@ template<typename T> struct DefaultHash<T *> {
}
};
template<typename T> struct DefaultHash<std::unique_ptr<T>> {
uint32_t operator()(const std::unique_ptr<T> &value) const
{
return DefaultHash<T *>{}(value.get());
}
};
template<typename T1, typename T2> struct DefaultHash<std::pair<T1, T2>> {
uint32_t operator()(const std::pair<T1, T2> &value) const
{

View File

@ -142,20 +142,13 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
return (ValueT *)(m_values + offset * sizeof(ValueT));
}
void copy_in(uint offset, const KeyT &key, const ValueT &value)
template<typename ForwardKeyT, typename ForwardValueT>
void store(uint offset, ForwardKeyT &&key, ForwardValueT &&value)
{
BLI_assert(m_status[offset] != IS_SET);
m_status[offset] = IS_SET;
new (this->key(offset)) KeyT(key);
new (this->value(offset)) ValueT(value);
}
void move_in(uint offset, KeyT &key, ValueT &value)
{
BLI_assert(m_status[offset] != IS_SET);
m_status[offset] = IS_SET;
new (this->key(offset)) KeyT(std::move(key));
new (this->value(offset)) ValueT(std::move(value));
new (this->key(offset)) KeyT(std::forward<ForwardKeyT>(key));
new (this->value(offset)) ValueT(std::forward<ForwardValueT>(value));
}
void set_dummy(uint offset)
@ -199,17 +192,19 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
*/
void add_new(const KeyT &key, const ValueT &value)
{
BLI_assert(!this->contains(key));
this->ensure_can_add();
ITER_SLOTS_BEGIN (key, m_array, , item, offset) {
if (item.is_empty(offset)) {
item.copy_in(offset, key, value);
m_array.update__empty_to_set();
return;
}
}
ITER_SLOTS_END(offset);
this->add_new__impl(key, value);
}
void add_new(const KeyT &key, ValueT &&value)
{
this->add_new__impl(key, std::move(value));
}
void add_new(KeyT &&key, const ValueT &value)
{
this->add_new__impl(std::move(key), value);
}
void add_new(KeyT &&key, ValueT &&value)
{
this->add_new__impl(std::move(key), std::move(value));
}
/**
@ -218,19 +213,19 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
*/
bool add(const KeyT &key, const ValueT &value)
{
this->ensure_can_add();
ITER_SLOTS_BEGIN (key, m_array, , item, offset) {
if (item.is_empty(offset)) {
item.copy_in(offset, key, value);
m_array.update__empty_to_set();
return true;
}
else if (item.has_key(offset, key)) {
return false;
}
}
ITER_SLOTS_END(offset);
return this->add__impl(key, value);
}
bool add(const KeyT &key, ValueT &&value)
{
return this->add__impl(key, std::move(value));
}
bool add(KeyT &&key, const ValueT &value)
{
return this->add__impl(std::move(key), value);
}
bool add(KeyT &&key, ValueT &&value)
{
return this->add__impl(std::move(key), std::move(value));
}
/**
@ -295,20 +290,14 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
const CreateValueF &create_value,
const ModifyValueF &modify_value)
{
this->ensure_can_add();
ITER_SLOTS_BEGIN (key, m_array, , item, offset) {
if (item.is_empty(offset)) {
item.copy_in(offset, key, create_value());
m_array.update__empty_to_set();
return true;
}
else if (item.has_key(offset, key)) {
modify_value(*item.value(offset));
return false;
}
}
ITER_SLOTS_END(offset);
return this->add_or_modify__impl(key, create_value, modify_value);
}
template<typename CreateValueF, typename ModifyValueF>
bool add_or_modify(KeyT &&key,
const CreateValueF &create_value,
const ModifyValueF &modify_value)
{
return this->add_or_modify__impl(std::move(key), create_value, modify_value);
}
/**
@ -316,8 +305,19 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
*/
bool add_override(const KeyT &key, const ValueT &value)
{
return this->add_or_modify(
key, [&value]() { return value; }, [&value](ValueT &old_value) { old_value = value; });
return this->add_override__impl(key, value);
}
bool add_override(const KeyT &key, ValueT &&value)
{
return this->add_override__impl(key, std::move(value));
}
bool add_override(KeyT &&key, const ValueT &value)
{
return this->add_override__impl(std::move(key), value);
}
bool add_override(KeyT &&key, ValueT &&value)
{
return this->add_override__impl(std::move(key), std::move(value));
}
/**
@ -384,19 +384,12 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
template<typename CreateValueF>
ValueT &lookup_or_add(const KeyT &key, const CreateValueF &create_value)
{
this->ensure_can_add();
ITER_SLOTS_BEGIN (key, m_array, , item, offset) {
if (item.is_empty(offset)) {
item.copy_in(offset, key, create_value());
m_array.update__empty_to_set();
return *item.value(offset);
}
else if (item.has_key(offset, key)) {
return *item.value(offset);
}
}
ITER_SLOTS_END(offset);
return this->lookup_or_add__impl(key, create_value);
}
template<typename CreateValueF>
ValueT &lookup_or_add(KeyT &&key, const CreateValueF &create_value)
{
return this->lookup_or_add__impl(std::move(key), create_value);
}
/**
@ -608,12 +601,94 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
{
ITER_SLOTS_BEGIN (key, new_array, , item, offset) {
if (item.is_empty(offset)) {
item.move_in(offset, key, value);
item.store(offset, std::move(key), std::move(value));
return;
}
}
ITER_SLOTS_END(offset);
}
template<typename ForwardKeyT, typename ForwardValueT>
bool add_override__impl(ForwardKeyT &&key, ForwardValueT &&value)
{
return this->add_or_modify(
std::forward<ForwardKeyT>(key),
[&]() { return std::forward<ForwardValueT>(value); },
[&](ValueT &old_value) { old_value = std::forward<ForwardValueT>(value); });
}
template<typename ForwardKeyT, typename ForwardValueT>
bool add__impl(ForwardKeyT &&key, ForwardValueT &&value)
{
this->ensure_can_add();
ITER_SLOTS_BEGIN (key, m_array, , item, offset) {
if (item.is_empty(offset)) {
item.store(offset, std::forward<ForwardKeyT>(key), std::forward<ForwardValueT>(value));
m_array.update__empty_to_set();
return true;
}
else if (item.has_key(offset, key)) {
return false;
}
}
ITER_SLOTS_END(offset);
}
template<typename ForwardKeyT, typename ForwardValueT>
void add_new__impl(ForwardKeyT &&key, ForwardValueT &&value)
{
BLI_assert(!this->contains(key));
this->ensure_can_add();
ITER_SLOTS_BEGIN (key, m_array, , item, offset) {
if (item.is_empty(offset)) {
item.store(offset, std::forward<ForwardKeyT>(key), std::forward<ForwardValueT>(value));
m_array.update__empty_to_set();
return;
}
}
ITER_SLOTS_END(offset);
}
template<typename ForwardKeyT, typename CreateValueF, typename ModifyValueF>
bool add_or_modify__impl(ForwardKeyT &&key,
const CreateValueF &create_value,
const ModifyValueF &modify_value)
{
this->ensure_can_add();
ITER_SLOTS_BEGIN (key, m_array, , item, offset) {
if (item.is_empty(offset)) {
item.store(offset, std::forward<ForwardKeyT>(key), create_value());
m_array.update__empty_to_set();
return true;
}
else if (item.has_key(offset, key)) {
modify_value(*item.value(offset));
return false;
}
}
ITER_SLOTS_END(offset);
}
template<typename ForwardKeyT, typename CreateValueF>
ValueT &lookup_or_add__impl(ForwardKeyT &&key, const CreateValueF &create_value)
{
this->ensure_can_add();
ITER_SLOTS_BEGIN (key, m_array, , item, offset) {
if (item.is_empty(offset)) {
item.store(offset, std::forward<ForwardKeyT>(key), create_value());
m_array.update__empty_to_set();
return *item.value(offset);
}
else if (item.has_key(offset, key)) {
return *item.value(offset);
}
}
ITER_SLOTS_END(offset);
}
};
#undef ITER_SLOTS_BEGIN

View File

@ -117,20 +117,12 @@ template<typename T, typename Allocator = GuardedAllocator> class Set {
return (T *)(m_values + offset * sizeof(T));
}
void copy_in(uint offset, const T &value)
template<typename ForwardT> void store(uint offset, ForwardT &&value)
{
BLI_assert(m_status[offset] != IS_SET);
m_status[offset] = IS_SET;
T *dst = this->value(offset);
new (dst) T(value);
}
void move_in(uint offset, T &value)
{
BLI_assert(m_status[offset] != IS_SET);
m_status[offset] = IS_SET;
T *dst = this->value(offset);
new (dst) T(std::move(value));
new (dst) T(std::forward<ForwardT>(value));
}
void set_dummy(uint offset)
@ -201,17 +193,11 @@ template<typename T, typename Allocator = GuardedAllocator> class Set {
*/
void add_new(const T &value)
{
BLI_assert(!this->contains(value));
this->ensure_can_add();
ITER_SLOTS_BEGIN (value, m_array, , item, offset) {
if (item.is_empty(offset)) {
item.copy_in(offset, value);
m_array.update__empty_to_set();
return;
}
}
ITER_SLOTS_END(offset);
this->add_new__impl(value);
}
void add_new(T &&value)
{
this->add_new__impl(std::move(value));
}
/**
@ -219,19 +205,11 @@ template<typename T, typename Allocator = GuardedAllocator> class Set {
*/
bool add(const T &value)
{
this->ensure_can_add();
ITER_SLOTS_BEGIN (value, m_array, , item, offset) {
if (item.is_empty(offset)) {
item.copy_in(offset, value);
m_array.update__empty_to_set();
return true;
}
else if (item.has_value(offset, value)) {
return false;
}
}
ITER_SLOTS_END(offset);
return this->add__impl(value);
}
bool add(T &&value)
{
return this->add__impl(std::move(value));
}
/**
@ -445,7 +423,7 @@ template<typename T, typename Allocator = GuardedAllocator> class Set {
{
ITER_SLOTS_BEGIN (old_value, new_array, , item, offset) {
if (item.is_empty(offset)) {
item.move_in(offset, old_value);
item.store(offset, std::move(old_value));
return;
}
}
@ -463,6 +441,38 @@ template<typename T, typename Allocator = GuardedAllocator> class Set {
}
ITER_SLOTS_END(offset);
}
template<typename ForwardT> void add_new__impl(ForwardT &&value)
{
BLI_assert(!this->contains(value));
this->ensure_can_add();
ITER_SLOTS_BEGIN (value, m_array, , item, offset) {
if (item.is_empty(offset)) {
item.store(offset, std::forward<ForwardT>(value));
m_array.update__empty_to_set();
return;
}
}
ITER_SLOTS_END(offset);
}
template<typename ForwardT> bool add__impl(ForwardT &&value)
{
this->ensure_can_add();
ITER_SLOTS_BEGIN (value, m_array, , item, offset) {
if (item.is_empty(offset)) {
item.store(offset, std::forward<ForwardT>(value));
m_array.update__empty_to_set();
return true;
}
else if (item.has_value(offset, value)) {
return false;
}
}
ITER_SLOTS_END(offset);
}
};
#undef ITER_SLOTS_BEGIN

View File

@ -147,15 +147,11 @@ template<typename T, typename Allocator = GuardedAllocator> class SetVector {
*/
void add_new(const T &value)
{
BLI_assert(!this->contains(value));
this->ensure_can_add();
ITER_SLOTS_BEGIN (value, m_array, , slot) {
if (slot.is_empty()) {
this->add_new_in_slot(slot, value);
return;
}
}
ITER_SLOTS_END;
this->add_new__impl(value);
}
void add_new(T &&value)
{
this->add_new__impl(std::move(value));
}
/**
@ -163,17 +159,11 @@ template<typename T, typename Allocator = GuardedAllocator> class SetVector {
*/
bool add(const T &value)
{
this->ensure_can_add();
ITER_SLOTS_BEGIN (value, m_array, , slot) {
if (slot.is_empty()) {
this->add_new_in_slot(slot, value);
return true;
}
else if (slot.has_value(value, m_elements)) {
return false;
}
}
ITER_SLOTS_END;
return this->add__impl(value);
}
bool add(T &&value)
{
return this->add__impl(std::move(value));
}
/**
@ -332,11 +322,11 @@ template<typename T, typename Allocator = GuardedAllocator> class SetVector {
ITER_SLOTS_END;
}
void add_new_in_slot(Slot &slot, const T &value)
template<typename ForwardT> void add_new_in_slot(Slot &slot, ForwardT &&value)
{
uint index = m_elements.size();
slot.set_index(index);
m_elements.append(value);
m_elements.append(std::forward<ForwardT>(value));
m_array.update__empty_to_set();
}
@ -369,6 +359,34 @@ template<typename T, typename Allocator = GuardedAllocator> class SetVector {
}
ITER_SLOTS_END;
}
template<typename ForwardT> void add_new__impl(ForwardT &&value)
{
BLI_assert(!this->contains(value));
this->ensure_can_add();
ITER_SLOTS_BEGIN (value, m_array, , slot) {
if (slot.is_empty()) {
this->add_new_in_slot(slot, std::forward<ForwardT>(value));
return;
}
}
ITER_SLOTS_END;
}
template<typename ForwardT> bool add__impl(ForwardT &&value)
{
this->ensure_can_add();
ITER_SLOTS_BEGIN (value, m_array, , slot) {
if (slot.is_empty()) {
this->add_new_in_slot(slot, std::forward<ForwardT>(value));
return true;
}
else if (slot.has_value(value, m_elements)) {
return false;
}
}
ITER_SLOTS_END;
}
};
#undef ITER_SLOTS_BEGIN

View File

@ -73,7 +73,7 @@ template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class St
void push(T &&value)
{
m_elements.append(std::forward<T>(value));
m_elements.append(std::move(value));
}
/**

View File

@ -152,20 +152,13 @@ template<typename T, typename Allocator = GuardedAllocator> class StringMap {
return StringRefNull(start, length);
}
void move_in(uint offset, uint32_t hash, uint32_t index, T &value)
template<typename ForwardT>
void store(uint offset, uint32_t hash, uint32_t index, ForwardT &&value)
{
BLI_assert(!this->is_set(offset));
m_hashes[offset] = hash;
m_indices[offset] = index;
new (this->value(offset)) T(std::move(value));
}
void copy_in(uint offset, uint32_t hash, uint32_t index, const T &value)
{
BLI_assert(!this->is_set(offset));
m_hashes[offset] = hash;
m_indices[offset] = index;
new (this->value(offset)) T(value);
new (this->value(offset)) T(std::forward<ForwardT>(value));
}
};
@ -189,18 +182,11 @@ template<typename T, typename Allocator = GuardedAllocator> class StringMap {
*/
void add_new(StringRef key, const T &value)
{
BLI_assert(!this->contains(key));
this->ensure_can_add();
uint32_t hash = this->compute_string_hash(key);
ITER_SLOTS_BEGIN (hash, m_array, , item, offset) {
if (item.is_empty(offset)) {
uint32_t index = this->save_key_in_array(key);
item.copy_in(offset, hash, index, value);
m_array.update__empty_to_set();
return;
}
}
ITER_SLOTS_END(offset);
this->add_new__impl(key, value);
}
void add_new(StringRef key, T &&value)
{
this->add_new__impl(key, std::move(value));
}
/**
@ -407,7 +393,23 @@ template<typename T, typename Allocator = GuardedAllocator> class StringMap {
{
ITER_SLOTS_BEGIN (hash, new_array, , item, offset) {
if (item.is_empty(offset)) {
item.move_in(offset, hash, index, value);
item.store(offset, hash, index, std::move(value));
return;
}
}
ITER_SLOTS_END(offset);
}
template<typename ForwardT> void add_new__impl(StringRef key, ForwardT &&value)
{
BLI_assert(!this->contains(key));
this->ensure_can_add();
uint32_t hash = this->compute_string_hash(key);
ITER_SLOTS_BEGIN (hash, m_array, , item, offset) {
if (item.is_empty(offset)) {
uint32_t index = this->save_key_in_array(key);
item.store(offset, hash, index, std::forward<ForwardT>(value));
m_array.update__empty_to_set();
return;
}
}

View File

@ -419,7 +419,7 @@ template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Ve
{
BLI_assert(!this->empty());
m_end--;
T value = *m_end;
T value = std::move(*m_end);
destruct(m_end);
UPDATE_VECTOR_SIZE(this);
return value;
@ -435,7 +435,7 @@ template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Ve
T *element_to_remove = m_begin + index;
m_end--;
if (element_to_remove < m_end) {
*element_to_remove = *m_end;
*element_to_remove = std::move(*m_end);
}
destruct(m_end);
UPDATE_VECTOR_SIZE(this);

View File

@ -2,7 +2,8 @@
#include "BLI_map.h"
#include "BLI_set.h"
using IntFloatMap = BLI::Map<int, float>;
using BLI::Map;
using IntFloatMap = Map<int, float>;
TEST(map, DefaultConstructor)
{
@ -258,3 +259,24 @@ TEST(map, Clear)
EXPECT_FALSE(map.contains(1));
EXPECT_FALSE(map.contains(2));
}
TEST(map, UniquePtrValue)
{
auto value1 = std::unique_ptr<int>(new int());
auto value2 = std::unique_ptr<int>(new int());
auto value3 = std::unique_ptr<int>(new int());
int *value1_ptr = value1.get();
Map<int, std::unique_ptr<int>> map;
map.add_new(1, std::move(value1));
map.add(2, std::move(value2));
map.add_override(3, std::move(value3));
map.lookup_or_add(4, []() { return std::unique_ptr<int>(new int()); });
map.add_new(5, std::unique_ptr<int>(new int()));
map.add(6, std::unique_ptr<int>(new int()));
map.add_override(7, std::unique_ptr<int>(new int()));
EXPECT_EQ(map.lookup(1).get(), value1_ptr);
EXPECT_EQ(map.lookup_ptr(100), nullptr);
}

View File

@ -1,7 +1,10 @@
#include "testing/testing.h"
#include "BLI_set.h"
#include "BLI_vector.h"
using IntSet = BLI::Set<int>;
using BLI::Set;
using BLI::Vector;
using IntSet = Set<int>;
TEST(set, Defaultconstructor)
{
@ -187,3 +190,14 @@ TEST(set, OftenAddRemove)
EXPECT_EQ(set.size(), 0);
}
}
TEST(set, UniquePtrValues)
{
Set<std::unique_ptr<int>> set;
set.add_new(std::unique_ptr<int>(new int()));
auto value1 = std::unique_ptr<int>(new int());
set.add_new(std::move(value1));
set.add(std::unique_ptr<int>(new int()));
EXPECT_EQ(set.size(), 3);
}

View File

@ -1,7 +1,8 @@
#include "testing/testing.h"
#include "BLI_set_vector.h"
using IntSetVector = BLI::SetVector<int>;
using BLI::SetVector;
using IntSetVector = SetVector<int>;
TEST(set_vector, DefaultConstructor)
{
@ -100,3 +101,13 @@ TEST(set_vector, Remove)
set.remove(7);
EXPECT_EQ(set.size(), 0);
}
TEST(set_vector, UniquePtrValue)
{
SetVector<std::unique_ptr<int>> set;
set.add_new(std::unique_ptr<int>(new int()));
set.add(std::unique_ptr<int>(new int()));
set.index_try(std::unique_ptr<int>(new int()));
std::unique_ptr<int> value = set.pop();
UNUSED_VARS(value);
}

View File

@ -1,7 +1,8 @@
#include "testing/testing.h"
#include "BLI_stack_cxx.h"
using IntStack = BLI::Stack<int>;
using BLI::Stack;
using IntStack = Stack<int>;
TEST(stack, DefaultConstructor)
{
@ -50,3 +51,13 @@ TEST(stack, Peek)
stack.pop();
EXPECT_EQ(stack.peek(), 3);
}
TEST(stack, UniquePtrValues)
{
Stack<std::unique_ptr<int>> stack;
stack.push(std::unique_ptr<int>(new int()));
stack.push(std::unique_ptr<int>(new int()));
std::unique_ptr<int> a = stack.pop();
std::unique_ptr<int> &b = stack.peek();
UNUSED_VARS(a, b);
}

View File

@ -199,3 +199,12 @@ TEST(string_map, WithVectors)
EXPECT_EQ(map.lookup("A").size(), 3);
EXPECT_EQ(map.lookup("B").size(), 7);
}
TEST(string_map, UniquePtrValues)
{
StringMap<std::unique_ptr<int>> map;
map.add_new("A", std::unique_ptr<int>(new int()));
std::unique_ptr<int> &a = map.lookup("A");
std::unique_ptr<int> *b = map.lookup_ptr("A");
EXPECT_EQ(a.get(), b->get());
}

View File

@ -398,3 +398,17 @@ TEST(vector, AppendNTimes)
EXPECT_EQ(a[3], 2);
EXPECT_EQ(a[4], 2);
}
TEST(vector, UniquePtrValue)
{
Vector<std::unique_ptr<int>> vec;
vec.append(std::unique_ptr<int>(new int()));
vec.append(std::unique_ptr<int>(new int()));
vec.append(std::unique_ptr<int>(new int()));
std::unique_ptr<int> &a = vec.last();
std::unique_ptr<int> b = vec.pop_last();
vec.remove_and_reorder(0);
UNUSED_VARS(a, b);
}