Readfile: use hash lookup for bones

Bone loop for reconstructing links was O(n^2)

3 files changed, 72 insertions, 31 deletions

diff --git a/source/blender/blenkernel/BKE_armature.h b/source/blender/blenkernel/BKE_armature.h
index e1885e46b24..6d00110e318 100644
--- a/source/blender/blenkernel/BKE_armature.h
+++ b/source/blender/blenkernel/BKE_armature.h
@@ -34,6 +34,7 @@
  */
 
 struct Bone;
+struct GHash;
 struct Main;
 struct bArmature;
 struct bPoseChannel;
@@ -72,6 +73,7 @@ extern "C" {
 
 struct bArmature *BKE_armature_add(struct Main *bmain, const char *name);
 struct bArmature *BKE_armature_from_object(struct Object *ob);
+int  BKE_armature_bonelist_count(struct ListBase *lb);
 void BKE_armature_bonelist_free(struct ListBase *lb);
 void BKE_armature_free(struct bArmature *arm);
 void BKE_armature_make_local(struct bArmature *arm);
@@ -84,7 +86,8 @@ bool BKE_pose_minmax(struct Object *ob, float r_min[3], float r_max[3], bool use
 
 int bone_autoside_name(char name[64], int strip_number, short axis, float head, float tail);
 
-struct Bone *BKE_armature_find_bone_name(struct bArmature *arm, const char *name);
+struct Bone  *BKE_armature_find_bone_name(struct bArmature *arm, const char *name);
+struct GHash *BKE_armature_bone_from_name_map(struct bArmature *arm);
 
 bool         BKE_armature_bone_flag_test_recursive(const struct Bone *bone, int flag);
 
diff --git a/source/blender/blenkernel/intern/armature.c b/source/blender/blenkernel/intern/armature.c
index f5d732b5551..74fffdd664f 100644
--- a/source/blender/blenkernel/intern/armature.c
+++ b/source/blender/blenkernel/intern/armature.c
@@ -38,7 +38,9 @@
 #include "MEM_guardedalloc.h"
 
 #include "BLI_math.h"
-#include "BLI_blenlib.h"
+#include "BLI_listbase.h"
+#include "BLI_string.h"
+#include "BLI_ghash.h"
 #include "BLI_utildefines.h"
 
 #include "DNA_anim_types.h"
@@ -91,6 +93,16 @@ bArmature *BKE_armature_from_object(Object *ob)
 	return NULL;
 }
 
+int BKE_armature_bonelist_count(ListBase *lb)
+{
+	int i = 0;
+	for (Bone *bone = lb->first; bone; bone = bone->next) {
+		i += 1 + BKE_armature_bonelist_count(&bone->childbase);
+	}
+
+	return i;
+}
+
 void BKE_armature_bonelist_free(ListBase *lb)
 {
 	Bone *bone;
@@ -229,15 +241,15 @@ bArmature *BKE_armature_copy(bArmature *arm)
 	return newArm;
 }
 
-static Bone *get_named_bone_bonechildren(Bone *bone, const char *name)
+static Bone *get_named_bone_bonechildren(ListBase *lb, const char *name)
 {
 	Bone *curBone, *rbone;
 
-	if (STREQ(bone->name, name))
-		return bone;
+	for (curBone = lb->first; curBone; curBone = curBone->next) {
+		if (STREQ(curBone->name, name))
+			return curBone;
 
-	for (curBone = bone->childbase.first; curBone; curBone = curBone->next) {
-		rbone = get_named_bone_bonechildren(curBone, name);
+		rbone = get_named_bone_bonechildren(&curBone->childbase, name);
 		if (rbone)
 			return rbone;
 	}
@@ -246,21 +258,38 @@ static Bone *get_named_bone_bonechildren(Bone *bone, const char *name)
 }
 
 
-/* Walk the list until the bone is found */
+/**
+ * Walk the list until the bone is found (slow!),
+ * use #BKE_armature_bone_from_name_map for multiple lookups.
+ */
 Bone *BKE_armature_find_bone_name(bArmature *arm, const char *name)
 {
-	Bone *bone = NULL, *curBone;
-
 	if (!arm)
 		return NULL;
 
-	for (curBone = arm->bonebase.first; curBone; curBone = curBone->next) {
-		bone = get_named_bone_bonechildren(curBone, name);
-		if (bone)
-			return bone;
+	return get_named_bone_bonechildren(&arm->bonebase, name);
+}
+
+static void armature_bone_from_name_insert_recursive(GHash *bone_hash, ListBase *lb)
+{
+	for (Bone *bone = lb->first; bone; bone = bone->next) {
+		BLI_ghash_insert(bone_hash, bone->name, bone);
+		armature_bone_from_name_insert_recursive(bone_hash, &bone->childbase);
 	}
+}
 
-	return bone;
+/**
+ * Create a (name -> bone) map.
+ *
+ * \note typically #bPose.chanhash us used via #BKE_pose_channel_find_name
+ * this is for the cases we can't use pose channels.
+ */
+GHash *BKE_armature_bone_from_name_map(bArmature *arm)
+{
+	const int bones_count = BKE_armature_bonelist_count(&arm->bonebase);
+	GHash *bone_hash = BLI_ghash_str_new_ex(__func__, bones_count);
+	armature_bone_from_name_insert_recursive(bone_hash, &arm->bonebase);
+	return bone_hash;
 }
 
 bool BKE_armature_bone_flag_test_recursive(const Bone *bone, int flag)
diff --git a/source/blender/blenloader/intern/readfile.c b/source/blender/blenloader/intern/readfile.c
index 84565fcb89f..fd144c0ebc0 100644
--- a/source/blender/blenloader/intern/readfile.c
+++ b/source/blender/blenloader/intern/readfile.c
@@ -3185,18 +3185,23 @@ static void direct_link_constraints(FileData *fd, ListBase *lb)
 
 static void lib_link_pose(FileData *fd, Main *bmain, Object *ob, bPose *pose)
 {
-	bPoseChannel *pchan;
 	bArmature *arm = ob->data;
-	int rebuild = 0;
 	
 	if (!pose || !arm)
 		return;
 	
 	/* always rebuild to match proxy or lib changes, but on Undo */
-	if (fd->memfile == NULL)
-		if (ob->proxy || (ob->id.lib==NULL && arm->id.lib))
-			rebuild = 1;
-	
+	bool rebuild = false;
+
+	if (fd->memfile == NULL) {
+		if (ob->proxy || (ob->id.lib==NULL && arm->id.lib)) {
+			rebuild = true;
+		}
+	}
+
+	/* avoid string */
+	GHash *bone_hash = BKE_armature_bone_from_name_map(arm);
+
 	if (ob->proxy) {
 		/* sync proxy layer */
 		if (pose->proxy_layer)
@@ -3204,28 +3209,32 @@ static void lib_link_pose(FileData *fd, Main *bmain, Object *ob, bPose *pose)
 		
 		/* sync proxy active bone */
 		if (pose->proxy_act_bone[0]) {
-			Bone *bone = BKE_armature_find_bone_name(arm, pose->proxy_act_bone);
-			if (bone)
+			Bone *bone = BLI_ghash_lookup(bone_hash, pose->proxy_act_bone);
+			if (bone) {
 				arm->act_bone = bone;
+			}
 		}
 	}
-	
-	for (pchan = pose->chanbase.first; pchan; pchan=pchan->next) {
+
+	for (bPoseChannel *pchan = pose->chanbase.first; pchan; pchan = pchan->next) {
 		lib_link_constraints(fd, (ID *)ob, &pchan->constraints);
-		
-		/* hurms... loop in a loop, but yah... later... (ton) */
-		pchan->bone = BKE_armature_find_bone_name(arm, pchan->name);
+
+		pchan->bone = BLI_ghash_lookup(bone_hash, pchan->name);
 		
 		pchan->custom = newlibadr_us(fd, arm->id.lib, pchan->custom);
-		if (pchan->bone == NULL)
-			rebuild= 1;
-		else if (ob->id.lib==NULL && arm->id.lib) {
+		if (UNLIKELY(pchan->bone == NULL)) {
+			rebuild = true;
+		}
+		else if ((ob->id.lib == NULL) && arm->id.lib) {
 			/* local pose selection copied to armature, bit hackish */
 			pchan->bone->flag &= ~BONE_SELECTED;
 			pchan->bone->flag |= pchan->selectflag;
 		}
 	}
+
+	BLI_ghash_free(bone_hash, NULL, NULL);
 	
+
 	if (rebuild) {
 		DAG_id_tag_update_ex(bmain, &ob->id, OB_RECALC_OB | OB_RECALC_DATA | OB_RECALC_TIME);
 		BKE_pose_tag_recalc(bmain, pose);