[Bf-blender-cvs] [5a1279fdce1] functions: faster adding to array lookup
Jacques Lucke
noreply at git.blender.org
Mon Apr 8 16:15:25 CEST 2019
Commit: 5a1279fdce1a8d9c92d7614bc7d4f44865a139d8
Author: Jacques Lucke
Date: Mon Apr 8 16:01:16 2019 +0200
Branches: functions
https://developer.blender.org/rB5a1279fdce1a8d9c92d7614bc7d4f44865a139d8
faster adding to array lookup
===================================================================
M source/blender/blenlib/BLI_array_lookup.hpp
M source/blender/blenlib/BLI_small_map.hpp
===================================================================
diff --git a/source/blender/blenlib/BLI_array_lookup.hpp b/source/blender/blenlib/BLI_array_lookup.hpp
index ac4e6e9fa24..b30467c5212 100644
--- a/source/blender/blenlib/BLI_array_lookup.hpp
+++ b/source/blender/blenlib/BLI_array_lookup.hpp
@@ -60,6 +60,30 @@ namespace BLI {
}
}
+ bool add(Item *array, const Key &key, Index potential_index)
+ {
+ ITER_SLOTS(key, slot, state) {
+ if (state == SLOT_EMPTY) {
+ bool map_changed = this->ensure_can_add(array);
+ if (map_changed) {
+ this->insert_index_for_key(key, potential_index);
+ }
+ else {
+ m_map[slot] = potential_index;
+ }
+ m_length++;
+ m_usable_slots--;
+ return true;
+ }
+ else if (state == SLOT_DUMMY) {
+ continue;
+ }
+ else if (GetKey(array[state]) == key) {
+ return false;
+ }
+ }
+ }
+
void add_new(Item *array, Index index)
{
this->ensure_can_add(array);
@@ -106,10 +130,10 @@ namespace BLI {
}
private:
- inline void ensure_can_add(Item *array)
+ inline bool ensure_can_add(Item *array)
{
if (LIKELY(m_usable_slots > 0)) {
- return;
+ return false;
}
this->reset_map(m_map.size() * 2);
@@ -118,6 +142,7 @@ namespace BLI {
this->insert_index_for_key(key, i);
}
m_usable_slots -= m_length;
+ return true;
}
void reset_map(uint size)
diff --git a/source/blender/blenlib/BLI_small_map.hpp b/source/blender/blenlib/BLI_small_map.hpp
index 7738ffa36d4..31a59886df0 100644
--- a/source/blender/blenlib/BLI_small_map.hpp
+++ b/source/blender/blenlib/BLI_small_map.hpp
@@ -32,13 +32,12 @@ namespace BLI {
bool add(const K &key, const V &value)
{
- if (this->contains(key)) {
- return false;
- }
- else {
- this->add_new(key, value);
- return true;
+ uint potential_index = m_entries.size();
+ bool newly_inserted = m_lookup.add(m_entries.begin(), key, potential_index);
+ if (newly_inserted) {
+ m_entries.append(Entry(key, value));
}
+ return newly_inserted;
}
void add_new(const K &key, const V &value)
More information about the Bf-blender-cvs
mailing list