[Bf-blender-cvs] [b45cd6b8bdc] functions: implement an actual string map that does not rely on std::string
Jacques Lucke
noreply at git.blender.org
Tue Aug 20 18:32:52 CEST 2019
Commit: b45cd6b8bdc478b95170dcedb00925aefbe9578b
Author: Jacques Lucke
Date: Tue Aug 20 18:08:17 2019 +0200
Branches: functions
https://developer.blender.org/rBb45cd6b8bdc478b95170dcedb00925aefbe9578b
implement an actual string map that does not rely on std::string
===================================================================
M source/blender/blenlib/BLI_string_map.hpp
M source/blender/simulations/bparticles/c_wrapper.cpp
M source/blender/simulations/bparticles/node_frontend.cpp
M source/blender/simulations/bparticles/particles_state.cpp
M source/blender/simulations/bparticles/particles_state.hpp
M source/blender/simulations/bparticles/simulate.cpp
M source/blender/simulations/bparticles/step_description.cpp
M source/blender/simulations/bparticles/world_state.hpp
===================================================================
diff --git a/source/blender/blenlib/BLI_string_map.hpp b/source/blender/blenlib/BLI_string_map.hpp
index ded285e434d..beebe86a9c9 100644
--- a/source/blender/blenlib/BLI_string_map.hpp
+++ b/source/blender/blenlib/BLI_string_map.hpp
@@ -28,65 +28,351 @@
#include "BLI_map.hpp"
#include "BLI_string_ref.hpp"
+#include "BLI_vector.hpp"
namespace BLI {
-template<typename V> class StringMap {
+// clang-format off
+
+#define ITER_SLOTS_BEGIN(HASH, ARRAY, OPTIONAL_CONST, R_ITEM, R_OFFSET) \
+ uint32_t hash_copy = HASH; \
+ uint32_t perturb = HASH; \
+ while (true) { \
+ uint32_t item_index = (hash_copy & ARRAY.slot_mask()) >> 2; \
+ uint8_t R_OFFSET = hash_copy & OFFSET_MASK; \
+ uint8_t initial_offset = R_OFFSET; \
+ OPTIONAL_CONST Item &R_ITEM = ARRAY.item(item_index); \
+ do {
+
+#define ITER_SLOTS_END(R_OFFSET) \
+ R_OFFSET = (R_OFFSET + 1) & OFFSET_MASK; \
+ } while (R_OFFSET != initial_offset); \
+ perturb >>= 5; \
+ hash_copy = hash_copy * 5 + 1 + perturb; \
+ } ((void)0)
+
+// clang-format on
+
+template<typename T, typename Allocator = GuardedAllocator> class StringMap {
private:
- Map<std::string, V> m_map;
+ static constexpr uint32_t OFFSET_MASK = 3;
+
+ class Item {
+ private:
+ static constexpr int32_t EMPTY = -1;
+
+ uint32_t m_hashes[4];
+ int32_t m_indices[4];
+ char m_values[sizeof(T) * 4];
+
+ public:
+ static constexpr uint slots_per_item = 4;
+
+ Item()
+ {
+ m_indices[0] = EMPTY;
+ m_indices[1] = EMPTY;
+ m_indices[2] = EMPTY;
+ m_indices[3] = EMPTY;
+ }
+
+ ~Item()
+ {
+ for (uint offset = 0; offset < 4; offset++) {
+ if (this->is_set(offset)) {
+ destruct(this->value(offset));
+ }
+ }
+ }
+
+ Item(const Item &other)
+ {
+ for (uint32_t offset = 0; offset < 4; offset++) {
+ m_indices[offset] = other.m_indices[offset];
+ if (other.is_set(offset)) {
+ m_hashes[offset] = other.m_hashes[offset];
+ new (this->value(offset)) T(*other.value(offset));
+ }
+ }
+ }
+
+ Item(Item &&other)
+ {
+ for (uint32_t offset = 0; offset < 4; offset++) {
+ m_indices[offset] = other.m_indices[offset];
+ if (other.is_set(offset)) {
+ m_hashes[offset] = other.m_hashes[offset];
+ new (this->value(offset)) T(std::move(*other.value(offset)));
+ }
+ }
+ }
+
+ uint32_t index(uint offset) const
+ {
+ return m_indices[offset];
+ }
+
+ uint32_t hash(uint offset) const
+ {
+ return m_hashes[offset];
+ }
+
+ T *value(uint offset) const
+ {
+ return (T *)POINTER_OFFSET(m_values, offset * sizeof(T));
+ }
+
+ bool is_set(uint offset) const
+ {
+ return m_indices[offset] >= 0;
+ }
+
+ bool is_empty(uint offset) const
+ {
+ return m_indices[offset] == EMPTY;
+ }
+
+ bool has_hash(uint offset, uint32_t hash) const
+ {
+ BLI_assert(this->is_set(offset));
+ return m_hashes[offset] == hash;
+ }
+
+ bool has_exact_key(uint offset, StringRef key, const Vector<char> &chars) const
+ {
+ return key == this->get_key(offset, chars);
+ }
+
+ StringRefNull get_key(uint offset, const Vector<char> &chars) const
+ {
+ const char *ptr = chars.begin() + m_indices[offset];
+ uint length = *(uint *)ptr;
+ const char *start = ptr + sizeof(uint);
+ return StringRefNull(start, length);
+ }
+
+ void move_in(uint offset, uint32_t hash, uint32_t index, T &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);
+ }
+ };
+
+ using ArrayType = OpenAddressingArray<Item, 1, Allocator>;
+ ArrayType m_array;
+ Vector<char> m_chars;
public:
StringMap() = default;
uint size() const
{
- return m_map.size();
+ return m_array.slots_set();
}
- void add_new(StringRef key, const V &value)
+ void add_new(StringRef key, const T &value)
{
- m_map.add_new(key.to_std_string(), 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);
}
- void add_override(StringRef key, const V &value)
+ bool contains(StringRef key) const
{
- m_map.add_override(key.to_std_string(), value);
+ uint32_t hash = this->compute_string_hash(key);
+ ITER_SLOTS_BEGIN (hash, m_array, const, item, offset) {
+ if (item.is_empty(offset)) {
+ return false;
+ }
+ else if (item.has_hash(offset, hash) && item.has_exact_key(offset, key, m_chars)) {
+ return true;
+ }
+ }
+ ITER_SLOTS_END(offset);
}
- V &lookup(StringRef key) const
+ T &lookup(StringRef key) const
{
- return m_map.lookup(key.to_std_string());
+ BLI_assert(this->contains(key));
+ T *found_value = nullptr;
+ uint32_t hash = this->compute_string_hash(key);
+ ITER_SLOTS_BEGIN (hash, m_array, const, item, offset) {
+ if (item.is_empty(offset)) {
+ return *found_value;
+ }
+ else if (item.has_hash(offset, hash)) {
+ if (found_value == nullptr) {
+ /* Common case: the first slot with the correct hash contains the key.
+ * However, still need to iterate until the next empty slot to make sure there is no
+ * other key with the exact same hash. */
+ /* TODO: Check if we can guarantee that every hash only exists once in some cases. */
+ found_value = item.value(offset);
+ }
+ else if (item.has_exact_key(offset, key, m_chars)) {
+ /* Found the hash more than once, now check for actual string equality. */
+ return *item.value(offset);
+ }
+ }
+ }
+ ITER_SLOTS_END(offset);
}
- V *lookup_ptr(StringRef key) const
+ T *lookup_ptr(StringRef key) const
{
- return m_map.lookup_ptr(key.to_std_string());
+ uint32_t hash = this->compute_string_hash(key);
+ ITER_SLOTS_BEGIN (hash, m_array, const, item, offset) {
+ if (item.is_empty(offset)) {
+ return nullptr;
+ }
+ else if (item.has_hash(offset, hash) && item.has_exact_key(offset, key, m_chars)) {
+ return item.value(offset);
+ }
+ }
+ ITER_SLOTS_END(offset);
}
- V lookup_default(StringRef key, const V &default_value) const
+ T lookup_default(StringRef key, const T &default_value) const
{
- return m_map.lookup_default(key.to_std_string(), default_value);
+ T *ptr = this->lookup_ptr(key);
+ if (ptr != nullptr) {
+ return *ptr;
+ }
+ else {
+ return default_value;
+ }
}
- bool contains(StringRef key) const
+ StringRefNull find_key_for_value(const T &value) const
+ {
+ for (const Item &item : m_array) {
+ for (uint offset = 0; offset < 4; offset++) {
+ if (item.is_set(offset) && value == *item.value(offset)) {
+ return item.get_key(offset, m_chars);
+ }
+ }
+ }
+ BLI_assert(false);
+ return {};
+ }
+
+ template<typename FuncT> void foreach_value(const FuncT &func)
+ {
+ for (Item &item : m_array) {
+ for (uint offset = 0; offset < 4; offset++) {
+ if (item.is_set(offset)) {
+ func(*item.value(offset));
+ }
+ }
+ }
+ }
+
+ template<typename FuncT> void foreach_key(const FuncT &func)
+ {
+ for (Item &item : m_array) {
+ for (uint offset = 0; offset < 4; offset++) {
+ if (item.is_set(offset)) {
+ StringRefNull key = item.get_key(offset, m_chars);
+ func(key);
+ }
+ }
+ }
+ }
+
+ template<typename FuncT> void foreach_key_value_pair(const FuncT &func)
{
- return m_map.contains(key.to_std_string());
+ for (Item &item : m_array) {
+ for (uint offset = 0; offset < 4; offset++) {
+ if (item.is_set(offset)) {
+ StringRefNull key = item.get_key(offset, m_chars);
+ T &value = *item.value(offset);
+ func(key, value);
+ }
+ }
+ }
}
- decltype(m_map.items()) items() const
+ private:
+ constexpr uint32_t compute_string_hash(StringRef key) const
+ {
+ /* TODO: check if this can be optimized more because we know the key length already. */
+ uint32_t hash = 5381;
+ for (char c : key) {
+ hash = hash * 33 + c;
+ }
+ return hash;
+ }
+
+ uint32_t save_key_in_array(StringRef key)
{
- return m_map.items();
+ uint index = m_chars.size();
+ uint string_size = key.size();
+ m_chars.extend(ArrayRef<char>((char *)&string_size, sizeof(uint)));
+ m_chars.extend(key);
+ m_chars.append('\0');
+ return index;
}
- decltype(m_map.keys()) keys() const
+ StringRefNull key_from_index(uint32_t index) const
{
- return m_map.keys();
+ const char *ptr = m_chars.begin() + index;
+ uint length = *(uint *)ptr;
+ const char *start = ptr + sizeof(uint);
+ return StringRefNull(start, length);
}
- decltype(m_map.values()) values() const
+ void ensure_can_add()
{
- return m_map.values();
+ if (m_array.should_grow()) {
+ this->grow(this->size() + 1);
+ }
+ }
+
+ void grow(uint min_usable_slots)
+ {
+ ArrayType new_array = m_array.init_reserved(min_usable_slots);
+ for (Item &old_item : m_array) {
+ for (uint offset = 0; offset < 4; offset++) {
+ if (old_item.is_set(offset)) {
+ this->add_after_grow(
+ *old_item.value(offset), old_item.hash(offset), old_item.index(offset), new_array);
+ }
+ }
+ }
+ m_array = std::move(new_array);
+ }
+
+ void add_after_grow(T &value, uint32_t hash, uint32_t index
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list