Depsgraph: use blender::Map instead of std::map

We decided to use our own map data structure in general for better
readability and performance.

Reviewers: sergey

Differential Revision: https://developer.blender.org/D7987

source/blender/depsgraph/intern/builder/deg_builder_cache.cc

@@ -155,21 +155,16 @@ DepsgraphBuilderCache::DepsgraphBuilderCache()
 
 DepsgraphBuilderCache::~DepsgraphBuilderCache()
 {
-  for (AnimatedPropertyStorageMap::value_type &iter : animated_property_storage_map_) {
-    AnimatedPropertyStorage *animated_property_storage = iter.second;
+  for (AnimatedPropertyStorage *animated_property_storage :
+       animated_property_storage_map_.values()) {
     OBJECT_GUARDED_DELETE(animated_property_storage, AnimatedPropertyStorage);
   }
 }
 
 AnimatedPropertyStorage *DepsgraphBuilderCache::ensureAnimatedPropertyStorage(ID *id)
 {
-  AnimatedPropertyStorageMap::iterator it = animated_property_storage_map_.find(id);
-  if (it != animated_property_storage_map_.end()) {
-    return it->second;
-  }
-  AnimatedPropertyStorage *animated_property_storage = OBJECT_GUARDED_NEW(AnimatedPropertyStorage);
-  animated_property_storage_map_.insert(make_pair(id, animated_property_storage));
-  return animated_property_storage;
+  return animated_property_storage_map_.lookup_or_add_cb(
+      id, []() { return OBJECT_GUARDED_NEW(AnimatedPropertyStorage); });
 }
 
 AnimatedPropertyStorage *DepsgraphBuilderCache::ensureInitializedAnimatedPropertyStorage(ID *id)

source/blender/depsgraph/intern/builder/deg_builder_cache.h

@@ -45,8 +45,6 @@ class AnimatedPropertyID {
   AnimatedPropertyID(ID *id, StructRNA *type, void *data, const char *property_name);
 
   uint32_t hash() const;
-
-  bool operator<(const AnimatedPropertyID &other) const;
   friend bool operator==(const AnimatedPropertyID &a, const AnimatedPropertyID &b);
 
   /* Corresponds to PointerRNA.data. */
@@ -73,8 +71,6 @@ class AnimatedPropertyStorage {
   Set<AnimatedPropertyID> animated_properties_set;
 };
 
-typedef map<ID *, AnimatedPropertyStorage *> AnimatedPropertyStorageMap;
-
 /* Cached data which can be re-used by multiple builders. */
 class DepsgraphBuilderCache {
  public:
@@ -100,7 +96,7 @@ class DepsgraphBuilderCache {
     return animated_property_storage->isPropertyAnimated(args...);
   }
 
-  AnimatedPropertyStorageMap animated_property_storage_map_;
+  Map<ID *, AnimatedPropertyStorage *> animated_property_storage_map_;
 };
 
 }  // namespace DEG

source/blender/depsgraph/intern/builder/deg_builder_map.cc

@@ -42,33 +42,20 @@ bool BuilderMap::checkIsBuilt(ID *id, int tag) const
 
 void BuilderMap::tagBuild(ID *id, int tag)
 {
-  IDTagMap::iterator it = id_tags_.find(id);
-  if (it == id_tags_.end()) {
-    id_tags_.insert(make_pair(id, tag));
-    return;
-  }
-  it->second |= tag;
+  id_tags_.lookup_or_add(id, 0) |= tag;
 }
 
 bool BuilderMap::checkIsBuiltAndTag(ID *id, int tag)
 {
-  IDTagMap::iterator it = id_tags_.find(id);
-  if (it == id_tags_.end()) {
-    id_tags_.insert(make_pair(id, tag));
-    return false;
-  }
-  const bool result = (it->second & tag) == tag;
-  it->second |= tag;
+  int &id_tag = id_tags_.lookup_or_add(id, 0);
+  const bool result = (id_tag & tag) == tag;
+  id_tag |= tag;
   return result;
 }
 
 int BuilderMap::getIDTag(ID *id) const
 {
-  IDTagMap::const_iterator it = id_tags_.find(id);
-  if (it == id_tags_.end()) {
-    return 0;
-  }
-  return it->second;
+  return id_tags_.lookup_default(id, 0);
 }
 
 }  // namespace DEG

source/blender/depsgraph/intern/builder/deg_builder_map.h

@@ -75,8 +75,7 @@ class BuilderMap {
  protected:
   int getIDTag(ID *id) const;
 
-  typedef map<ID *, int> IDTagMap;
-  IDTagMap id_tags_;
+  Map<ID *, int> id_tags_;
 };
 
 }  // namespace DEG

source/blender/depsgraph/intern/builder/deg_builder_relations.cc

@@ -2887,9 +2887,7 @@ void DepsgraphRelationBuilder::build_driver_relations(IDNode *id_node)
   }
 
   // Mapping from RNA prefix -> set of driver evaluation nodes:
-  typedef Vector<Node *> DriverGroup;
-  typedef map<string, DriverGroup> DriverGroupMap;
-  DriverGroupMap driver_groups;
+  Map<string, Vector<Node *>> driver_groups;
 
   LISTBASE_FOREACH (FCurve *, fcu, &adt->drivers) {
     if (fcu->rna_path == nullptr) {
@@ -2897,33 +2895,33 @@ void DepsgraphRelationBuilder::build_driver_relations(IDNode *id_node)
     }
     // Get the RNA path except the part after the last dot.
     char *last_dot = strrchr(fcu->rna_path, '.');
-    string rna_prefix;
+    StringRef rna_prefix;
     if (last_dot != nullptr) {
-      rna_prefix = string(fcu->rna_path, last_dot);
+      rna_prefix = StringRef(fcu->rna_path, last_dot);
     }
 
     // Insert this driver node into the group belonging to the RNA prefix.
     OperationKey driver_key(
         id_orig, NodeType::PARAMETERS, OperationCode::DRIVER, fcu->rna_path, fcu->array_index);
     Node *node_driver = get_node(driver_key);
-    driver_groups[rna_prefix].append(node_driver);
+    driver_groups.lookup_or_add_default_as(rna_prefix).append(node_driver);
   }
 
-  for (pair<string, DriverGroup> prefix_group : driver_groups) {
+  for (Span<Node *> prefix_group : driver_groups.values()) {
     // For each node in the driver group, try to connect it to another node
     // in the same group without creating any cycles.
-    int num_drivers = prefix_group.second.size();
+    int num_drivers = prefix_group.size();
     if (num_drivers < 2) {
       // A relation requires two drivers.
       continue;
     }
     for (int from_index = 0; from_index < num_drivers; ++from_index) {
-      Node *op_from = prefix_group.second[from_index];
+      Node *op_from = prefix_group[from_index];
 
       // Start by trying the next node in the group.
       for (int to_offset = 1; to_offset < num_drivers; ++to_offset) {
         int to_index = (from_index + to_offset) % num_drivers;
-        Node *op_to = prefix_group.second[to_index];
+        Node *op_to = prefix_group[to_index];
 
         // Investigate whether this relation would create a dependency cycle.
         // Example graph:

source/blender/depsgraph/intern/depsgraph_type.h

@@ -54,6 +54,7 @@ namespace DEG {
 
 /* Commonly used types. */
 using blender::Map;
+using blender::Optional;
 using blender::Set;
 using blender::Span;
 using blender::StringRef;
@@ -61,9 +62,7 @@ using blender::StringRefNull;
 using blender::Vector;
 using blender::VectorSet;
 using std::deque;
-using std::map;
 using std::pair;
-using std::set;
 using std::string;
 using std::unique_ptr;
 

source/blender/depsgraph/intern/eval/deg_eval_runtime_backup_modifier.cc

@@ -35,15 +35,15 @@ ModifierDataBackupID::ModifierDataBackupID(ModifierData *modifier_data, Modifier
 {
 }
 
-bool ModifierDataBackupID::operator<(const ModifierDataBackupID &other) const
+bool operator==(const ModifierDataBackupID &a, const ModifierDataBackupID &b)
 {
-  if (modifier_data < other.modifier_data) {
-    return true;
-  }
-  if (modifier_data == other.modifier_data) {
-    return static_cast<int>(type) < static_cast<int>(other.type);
-  }
-  return false;
+  return a.modifier_data == b.modifier_data && a.type == b.type;
+}
+
+uint32_t ModifierDataBackupID::hash() const
+{
+  uintptr_t ptr = (uintptr_t)modifier_data;
+  return (ptr >> 4) ^ (uintptr_t)type;
 }
 
 }  // namespace DEG

source/blender/depsgraph/intern/eval/deg_eval_runtime_backup_modifier.h

@@ -46,13 +46,15 @@ class ModifierDataBackupID {
   ModifierDataBackupID(const Depsgraph *depsgraph);
   ModifierDataBackupID(ModifierData *modifier_data, ModifierType type);
 
-  bool operator<(const ModifierDataBackupID &other) const;
+  friend bool operator==(const ModifierDataBackupID &a, const ModifierDataBackupID &b);
+
+  uint32_t hash() const;
 
   ModifierData *modifier_data;
   ModifierType type;
 };
 
 /* Storage for backed up runtime modifier data. */
-typedef map<ModifierDataBackupID, void *> ModifierRuntimeDataBackup;
+typedef Map<ModifierDataBackupID, void *> ModifierRuntimeDataBackup;
 
 }  // namespace DEG

source/blender/depsgraph/intern/eval/deg_eval_runtime_backup_object.cc

@@ -75,7 +75,7 @@ void ObjectRuntimeBackup::backup_modifier_runtime_data(Object *object)
     }
     BLI_assert(modifier_data->orig_modifier_data != nullptr);
     ModifierDataBackupID modifier_data_id = create_modifier_data_id(modifier_data);
-    modifier_runtime_data.insert(make_pair(modifier_data_id, modifier_data->runtime));
+    modifier_runtime_data.add(modifier_data_id, modifier_data->runtime);
     modifier_data->runtime = nullptr;
   }
 }
@@ -86,7 +86,7 @@ void ObjectRuntimeBackup::backup_pose_channel_runtime_data(Object *object)
     LISTBASE_FOREACH (bPoseChannel *, pchan, &object->pose->chanbase) {
       /* This is nullptr in Edit mode. */
       if (pchan->orig_pchan != nullptr) {
-        pose_channel_runtime_data[pchan->orig_pchan] = pchan->runtime;
+        pose_channel_runtime_data.add(pchan->orig_pchan, pchan->runtime);
         BKE_pose_channel_runtime_reset(&pchan->runtime);
       }
     }
@@ -153,22 +153,16 @@ void ObjectRuntimeBackup::restore_modifier_runtime_data(Object *object)
   LISTBASE_FOREACH (ModifierData *, modifier_data, &object->modifiers) {
     BLI_assert(modifier_data->orig_modifier_data != nullptr);
     ModifierDataBackupID modifier_data_id = create_modifier_data_id(modifier_data);
-    ModifierRuntimeDataBackup::iterator runtime_data_iterator = modifier_runtime_data.find(
-        modifier_data_id);
-    if (runtime_data_iterator != modifier_runtime_data.end()) {
-      modifier_data->runtime = runtime_data_iterator->second;
-      runtime_data_iterator->second = nullptr;
+    void *runtime = modifier_runtime_data.pop_default(modifier_data_id, nullptr);
+    if (runtime != nullptr) {
+      modifier_data->runtime = runtime;
     }
   }
-  for (ModifierRuntimeDataBackup::value_type value : modifier_runtime_data) {
-    const ModifierDataBackupID modifier_data_id = value.first;
-    void *runtime = value.second;
-    if (value.second == nullptr) {
-      continue;
-    }
-    const ModifierTypeInfo *modifier_type_info = BKE_modifier_get_info(modifier_data_id.type);
+
+  for (ModifierRuntimeDataBackup::Item item : modifier_runtime_data.items()) {
+    const ModifierTypeInfo *modifier_type_info = BKE_modifier_get_info(item.key.type);
     BLI_assert(modifier_type_info != nullptr);
-    modifier_type_info->freeRuntimeData(runtime);
+    modifier_type_info->freeRuntimeData(item.value);
   }
 }
 
@@ -178,17 +172,16 @@ void ObjectRuntimeBackup::restore_pose_channel_runtime_data(Object *object)
     LISTBASE_FOREACH (bPoseChannel *, pchan, &object->pose->chanbase) {
       /* This is nullptr in Edit mode. */
       if (pchan->orig_pchan != nullptr) {
-        PoseChannelRuntimeDataBackup::iterator runtime_data_iterator =
-            pose_channel_runtime_data.find(pchan->orig_pchan);
-        if (runtime_data_iterator != pose_channel_runtime_data.end()) {
-          pchan->runtime = runtime_data_iterator->second;
-          pose_channel_runtime_data.erase(runtime_data_iterator);
+        Optional<bPoseChannel_Runtime> runtime = pose_channel_runtime_data.pop_try(
+            pchan->orig_pchan);
+        if (runtime.has_value()) {
+          pchan->runtime = runtime.extract();
         }
       }
     }
   }
-  for (PoseChannelRuntimeDataBackup::value_type &value : pose_channel_runtime_data) {
-    BKE_pose_channel_runtime_free(&value.second);
+  for (bPoseChannel_Runtime &runtime : pose_channel_runtime_data.values()) {
+    BKE_pose_channel_runtime_free(&runtime);
   }
 }
 

source/blender/depsgraph/intern/eval/deg_eval_runtime_backup_object.h

@@ -53,7 +53,7 @@ class ObjectRuntimeBackup {
   short base_flag;
   unsigned short base_local_view_bits;
   ModifierRuntimeDataBackup modifier_runtime_data;
-  PoseChannelRuntimeDataBackup pose_channel_runtime_data;
+  Map<bPoseChannel *, bPoseChannel_Runtime> pose_channel_runtime_data;
 };
 
 }  // namespace DEG

source/blender/depsgraph/intern/eval/deg_eval_runtime_backup_pose.h

@@ -27,11 +27,6 @@
 
 #include "DNA_action_types.h"
 
-struct bPoseChannel;
-
 namespace DEG {
 
-/* Storage for backed up pose channel runtime data. */
-typedef map<bPoseChannel *, bPoseChannel_Runtime> PoseChannelRuntimeDataBackup;
-
 }  // namespace DEG

source/blender/depsgraph/intern/eval/deg_eval_runtime_backup_sequencer.cc

@@ -42,7 +42,7 @@ void SequencerBackup::init_from_scene(Scene *scene)
     SequenceBackup sequence_backup(depsgraph);
     sequence_backup.init_from_sequence(sequence);
     if (!sequence_backup.isEmpty()) {
-      sequences_backup.insert(make_pair(sequence->orig_sequence, sequence_backup));
+      sequences_backup.add(sequence->orig_sequence, sequence_backup);
     }
   }
   SEQ_END;
@@ -52,17 +52,14 @@ void SequencerBackup::restore_to_scene(Scene *scene)
 {
   Sequence *sequence;
   SEQ_BEGIN (scene->ed, sequence) {
-    SequencesBackupMap::iterator it = sequences_backup.find(sequence->orig_sequence);
-    if (it == sequences_backup.end()) {
-      continue;
+    SequenceBackup *sequence_backup = sequences_backup.lookup_ptr(sequence->orig_sequence);
+    if (sequence_backup != nullptr) {
+      sequence_backup->restore_to_sequence(sequence);
     }
-    SequenceBackup &sequence_backup = it->second;
-    sequence_backup.restore_to_sequence(sequence);
   }
   SEQ_END;
   /* Cleanup audio while the scene is still known. */
-  for (SequencesBackupMap::value_type &it : sequences_backup) {
-    SequenceBackup &sequence_backup = it.second;
+  for (SequenceBackup &sequence_backup : sequences_backup.values()) {
     if (sequence_backup.scene_sound != nullptr) {
       BKE_sound_remove_scene_sound(scene, sequence_backup.scene_sound);
     }

source/blender/depsgraph/intern/eval/deg_eval_runtime_backup_sequencer.h

@@ -42,8 +42,7 @@ class SequencerBackup {
 
   const Depsgraph *depsgraph;
 
-  typedef map<Sequence *, SequenceBackup> SequencesBackupMap;
-  SequencesBackupMap sequences_backup;
+  Map<Sequence *, SequenceBackup> sequences_backup;
 };
 
 }  // namespace DEG