writefile: remove SDNA last-hit, optimize DNA reconstruct

- Move last-hit index out of SDNA struct
  (allows for access by multiple threads).
- Replace O(n^2) search with hash lookup in DNA reconstruction.

4 files changed, 84 insertions, 72 deletions

diff --git a/source/blender/blenloader/intern/readfile.c b/source/blender/blenloader/intern/readfile.c
index 68cc060b010..27a119a4532 100644
--- a/source/blender/blenloader/intern/readfile.c
+++ b/source/blender/blenloader/intern/readfile.c
@@ -1844,7 +1844,7 @@ void blo_add_library_pointer_map(ListBase *old_mainlist, FileData *fd)
 /* ********** END OLD POINTERS ****************** */
 /* ********** READ FILE ****************** */
 
-static void switch_endian_structs(struct SDNA *filesdna, BHead *bhead)
+static void switch_endian_structs(const struct SDNA *filesdna, BHead *bhead)
 {
 	int blocksize, nblocks;
 	char *data;
diff --git a/source/blender/makesdna/DNA_genfile.h b/source/blender/makesdna/DNA_genfile.h
index 77877f7bada..1b558b11cf0 100644
--- a/source/blender/makesdna/DNA_genfile.h
+++ b/source/blender/makesdna/DNA_genfile.h
@@ -79,10 +79,13 @@ struct SDNA *DNA_sdna_from_data(
         bool do_endian_swap, bool data_alloc);
 void DNA_sdna_free(struct SDNA *sdna);
 
-int DNA_struct_find_nr(struct SDNA *sdna, const char *str);
-void DNA_struct_switch_endian(struct SDNA *oldsdna, int oldSDNAnr, char *data);
-char *DNA_struct_get_compareflags(struct SDNA *sdna, struct SDNA *newsdna);
-void *DNA_struct_reconstruct(struct SDNA *newsdna, struct SDNA *oldsdna, char *compflags, int oldSDNAnr, int blocks, void *data);
+int DNA_struct_find_nr_ex(const struct SDNA *sdna, const char *str, unsigned int *index_last);
+int DNA_struct_find_nr(const struct SDNA *sdna, const char *str);
+void DNA_struct_switch_endian(const struct SDNA *oldsdna, int oldSDNAnr, char *data);
+char *DNA_struct_get_compareflags(const struct SDNA *sdna, const struct SDNA*newsdna);
+void *DNA_struct_reconstruct(
+        const struct SDNA *newsdna, const struct SDNA *oldsdna,
+        char *compflags, int oldSDNAnr, int blocks, void *data);
 
 int DNA_elem_array_size(const char *str);
 int DNA_elem_offset(struct SDNA *sdna, const char *stype, const char *vartype, const char *name);
diff --git a/source/blender/makesdna/DNA_sdna_types.h b/source/blender/makesdna/DNA_sdna_types.h
index 791aca77558..26ea5cd4e93 100644
--- a/source/blender/makesdna/DNA_sdna_types.h
+++ b/source/blender/makesdna/DNA_sdna_types.h
@@ -35,12 +35,12 @@
 #
 #
 typedef struct SDNA {
-	const char *data;			/* full copy of 'encoded' data */
+	const char *data;	/* full copy of 'encoded' data (when data_alloc is set, otherwise borrowed). */
 	int datalen;		/* length of data */
 	bool data_alloc;
 
 	int nr_names;		/* total number of struct members */
-	const char **names;		/* struct member names */
+	const char **names;	/* struct member names */
 
 	int pointerlen;		/* size of a pointer in bytes */
 
@@ -57,11 +57,6 @@ typedef struct SDNA {
 
 	struct GHash *structs_map; /* ghash for faster lookups,
 	                            * requires WITH_DNA_GHASH to be used for now */
-
-		/* wrong place for this really, its a simple
-		 * cache for findstruct_nr.
-		 */
-	int lastfind;
 } SDNA;
 
 #
diff --git a/source/blender/makesdna/intern/dna_genfile.c b/source/blender/makesdna/intern/dna_genfile.c
index 9135d7bab7d..1d9e9718528 100644
--- a/source/blender/makesdna/intern/dna_genfile.c
+++ b/source/blender/makesdna/intern/dna_genfile.c
@@ -39,6 +39,7 @@
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
+#include <limits.h>
 
 #include "MEM_guardedalloc.h" // for MEM_freeN MEM_mallocN MEM_callocN
 
@@ -280,37 +281,16 @@ static void printstruct(SDNA *sdna, short strnr)
 #endif
 
 /**
- * Returns a pointer to the start of the struct info for the struct with the specified name.
- */
-static short *findstruct_name(SDNA *sdna, const char *str)
-{
-	int a;
-	short *sp = NULL;
-
-
-	for (a = 0; a < sdna->nr_structs; a++) {
-
-		sp = sdna->structs[a];
-		
-		if (strcmp(sdna->types[sp[0]], str) == 0) {
-			return sp;
-		}
-	}
-	
-	return NULL;
-}
-
-/**
  * Returns the index of the struct info for the struct with the specified name.
  */
-int DNA_struct_find_nr(SDNA *sdna, const char *str)
+int DNA_struct_find_nr_ex(const SDNA *sdna, const char *str, unsigned int *index_last)
 {
 	const short *sp = NULL;
 
-	if (sdna->lastfind < sdna->nr_structs) {
-		sp = sdna->structs[sdna->lastfind];
+	if (*index_last < sdna->nr_structs) {
+		sp = sdna->structs[*index_last];
 		if (strcmp(sdna->types[sp[0]], str) == 0) {
-			return sdna->lastfind;
+			return *index_last;
 		}
 	}
 
@@ -323,7 +303,7 @@ int DNA_struct_find_nr(SDNA *sdna, const char *str)
 
 		if (index_p) {
 			a = GET_INT_FROM_POINTER(*index_p);
-			sdna->lastfind = a;
+			*index_last = a;
 		}
 		else {
 			a = -1;
@@ -339,7 +319,7 @@ int DNA_struct_find_nr(SDNA *sdna, const char *str)
 			sp = sdna->structs[a];
 
 			if (strcmp(sdna->types[sp[0]], str) == 0) {
-				sdna->lastfind = a;
+				*index_last = a;
 				return a;
 			}
 		}
@@ -348,6 +328,12 @@ int DNA_struct_find_nr(SDNA *sdna, const char *str)
 #endif
 }
 
+int DNA_struct_find_nr(const SDNA *sdna, const char *str)
+{
+	unsigned int index_last_dummy = UINT_MAX;
+	return DNA_struct_find_nr_ex(sdna, str, &index_last_dummy);
+}
+
 /* ************************* END DIV ********************** */
 
 /* ************************* READ DNA ********************** */
@@ -358,16 +344,21 @@ int DNA_struct_find_nr(SDNA *sdna, const char *str)
 static void init_structDNA(SDNA *sdna, bool do_endian_swap)
 {
 	int *data, *verg, gravity_fix = -1;
-	intptr_t nr;
 	short *sp;
-	char str[8], *cp;
+	char str[8];
 	
 	verg = (int *)str;
 	data = (int *)sdna->data;
 
 	strcpy(str, "SDNA");
-	if (*data == *verg) {
-	
+	if (*data != *verg) {
+		printf("SDNA error in SDNA file\n");
+		return;
+	}
+	else {
+		intptr_t nr;
+		char *cp;
+
 		data++;
 		
 		/* load names array */
@@ -515,37 +506,52 @@ static void init_structDNA(SDNA *sdna, bool do_endian_swap)
 			
 			nr++;
 		}
+	}
 
-		/* finally pointerlen: use struct ListBase to test it, never change the size of it! */
-		sp = findstruct_name(sdna, "ListBase");
-		/* weird; i have no memory of that... I think I used sizeof(void *) before... (ton) */
-		
-		sdna->pointerlen = sdna->typelens[sp[0]] / 2;
-
-		if (sp[1] != 2 || (sdna->pointerlen != 4 && sdna->pointerlen != 8)) {
-			printf("ListBase struct error! Needs it to calculate pointerize.\n");
-			exit(1);
-			/* well, at least sizeof(ListBase) is error proof! (ton) */
-		}
-		
+	{
 		/* second part of gravity problem, setting "gravity" type to void */
 		if (gravity_fix > -1) {
-			for (nr = 0; nr < sdna->nr_structs; nr++) {
+			for (intptr_t nr = 0; nr < sdna->nr_structs; nr++) {
 				sp = sdna->structs[nr];
 				if (strcmp(sdna->types[sp[0]], "ClothSimSettings") == 0)
 					sp[10] = SDNA_TYPE_VOID;
 			}
 		}
+	}
 
 #ifdef WITH_DNA_GHASH
+	{
 		/* create a ghash lookup to speed up */
 		sdna->structs_map = BLI_ghash_str_new_ex("init_structDNA gh", sdna->nr_structs);
 
-		for (nr = 0; nr < sdna->nr_structs; nr++) {
+		for (intptr_t nr = 0; nr < sdna->nr_structs; nr++) {
 			sp = sdna->structs[nr];
 			BLI_ghash_insert(sdna->structs_map, sdna->types[sp[0]], SET_INT_IN_POINTER(nr));
 		}
+	}
 #endif
+
+	/* Calculate 'sdna->pointerlen' */
+	{
+		intptr_t nr = DNA_struct_find_nr(sdna, "ListBase");
+
+		/* should never happen, only with corrupt file for example */
+		if (UNLIKELY(nr == -1)) {
+			printf("ListBase struct error! Not found.\n");
+			exit(1);
+		}
+
+		/* finally pointerlen: use struct ListBase to test it, never change the size of it! */
+		sp = sdna->structs[nr];
+		/* weird; i have no memory of that... I think I used sizeof(void *) before... (ton) */
+
+		sdna->pointerlen = sdna->typelens[sp[0]] / 2;
+
+		if (sp[1] != 2 || (sdna->pointerlen != 4 && sdna->pointerlen != 8)) {
+			printf("ListBase struct error! Needs it to calculate pointerize.\n");
+			exit(1);
+			/* well, at least sizeof(ListBase) is error proof! (ton) */
+		}
 	}
 }
 
@@ -557,8 +563,6 @@ SDNA *DNA_sdna_from_data(
         bool do_endian_swap, bool data_alloc)
 {
 	SDNA *sdna = MEM_mallocN(sizeof(*sdna), "sdna");
-	
-	sdna->lastfind = 0;
 
 	sdna->datalen = datalen;
 	if (data_alloc) {
@@ -623,7 +627,7 @@ static void recurs_test_compflags(const SDNA *sdna, char *compflags, int structn
  * - 1  Struct is the same (can be loaded with straight memory copy after any necessary endian conversion)
  * - 2  Struct is different in some way (needs to be copied/converted field by field)
  */
-char *DNA_struct_get_compareflags(SDNA *oldsdna, SDNA *newsdna)
+char *DNA_struct_get_compareflags(const SDNA *oldsdna, const SDNA *newsdna)
 {
 	int a, b;
 	const short *sp_old, *sp_new;
@@ -640,14 +644,19 @@ char *DNA_struct_get_compareflags(SDNA *oldsdna, SDNA *newsdna)
 	/* we check all structs in 'oldsdna' and compare them with 
 	 * the structs in 'newsdna'
 	 */
+	unsigned int newsdna_index_last = 0;
 	
 	for (a = 0; a < oldsdna->nr_structs; a++) {
 		sp_old = oldsdna->structs[a];
 		
 		/* search for type in cur */
-		sp_new = findstruct_name(newsdna, oldsdna->types[sp_old[0]]);
-		
-		if (sp_new) {
+		int sp_new_index = DNA_struct_find_nr_ex(newsdna, oldsdna->types[sp_old[0]], &newsdna_index_last);
+
+		/* The next indices will almost always match */
+		newsdna_index_last++;
+
+		if (sp_new_index != -1) {
+			sp_new = newsdna->structs[sp_new_index];
 			/* initial assumption */
 			compflags[a] = SDNA_CMP_NOT_EQUAL;
 			
@@ -1037,8 +1046,8 @@ static void reconstruct_elem(
  * \param cur  Where to put converted struct contents
  */
 static void reconstruct_struct(
-        SDNA *newsdna,
-        SDNA *oldsdna,
+        const SDNA *newsdna,
+        const SDNA *oldsdna,
         const char *compflags,
 
         int oldSDNAnr,
@@ -1056,6 +1065,10 @@ static void reconstruct_struct(
 	char *cpo, *cpc;
 	const char *name, *nameo;
 
+	unsigned int oldsdna_index_last = UINT_MAX;
+	unsigned int cursdna_index_last = UINT_MAX;
+
+
 	if (oldSDNAnr == -1) return;
 	if (curSDNAnr == -1) return;
 
@@ -1090,8 +1103,8 @@ static void reconstruct_struct(
 			cpo = find_elem(oldsdna, type, name, spo, data, &sppo);
 			
 			if (cpo) {
-				oldSDNAnr = DNA_struct_find_nr(oldsdna, type);
-				curSDNAnr = DNA_struct_find_nr(newsdna, type);
+				oldSDNAnr = DNA_struct_find_nr_ex(oldsdna, type, &oldsdna_index_last);
+				curSDNAnr = DNA_struct_find_nr_ex(newsdna, type, &cursdna_index_last);
 				
 				/* array! */
 				mul = DNA_elem_array_size(name);
@@ -1132,7 +1145,7 @@ static void reconstruct_struct(
  * \param oldSDNAnr  Index of struct info within oldsdna
  * \param data  Struct data
  */
-void DNA_struct_switch_endian(SDNA *oldsdna, int oldSDNAnr, char *data)
+void DNA_struct_switch_endian(const SDNA *oldsdna, int oldSDNAnr, char *data)
 {
 	/* Recursive!
 	 * If element is a struct, call recursive.
@@ -1141,6 +1154,7 @@ void DNA_struct_switch_endian(SDNA *oldsdna, int oldSDNAnr, char *data)
 	const short *spo, *spc;
 	char *cur;
 	const char *type, *name;
+	unsigned int oldsdna_index_last = UINT_MAX;
 
 	if (oldSDNAnr == -1) return;
 	firststructtypenr = *(oldsdna->structs[0]);
@@ -1165,7 +1179,7 @@ void DNA_struct_switch_endian(SDNA *oldsdna, int oldSDNAnr, char *data)
 			/* where does the old data start (is there one?) */
 			char *cpo = find_elem(oldsdna, type, name, spo, data, NULL);
 			if (cpo) {
-				oldSDNAnr = DNA_struct_find_nr(oldsdna, type);
+				oldSDNAnr = DNA_struct_find_nr_ex(oldsdna, type, &oldsdna_index_last);
 				
 				mul = DNA_elem_array_size(name);
 				elena = elen / mul;
@@ -1223,7 +1237,9 @@ void DNA_struct_switch_endian(SDNA *oldsdna, int oldSDNAnr, char *data)
  * \param data  Array of struct data
  * \return An allocated reconstructed struct
  */
-void *DNA_struct_reconstruct(SDNA *newsdna, SDNA *oldsdna, char *compflags, int oldSDNAnr, int blocks, void *data)
+void *DNA_struct_reconstruct(
+        const SDNA *newsdna, const SDNA *oldsdna,
+        char *compflags, int oldSDNAnr, int blocks, void *data)
 {
 	int a, curSDNAnr, curlen = 0, oldlen;
 	const short *spo, *spc;
@@ -1263,7 +1279,6 @@ void *DNA_struct_reconstruct(SDNA *newsdna, SDNA *oldsdna, char *compflags, int
  */
 int DNA_elem_offset(SDNA *sdna, const char *stype, const char *vartype, const char *name)
 {
-	
 	const int SDNAnr = DNA_struct_find_nr(sdna, stype);
 	const short * const spo = sdna->structs[SDNAnr];
 	const char * const cp = find_elem(sdna, vartype, name, spo, NULL, NULL);
@@ -1273,7 +1288,6 @@ int DNA_elem_offset(SDNA *sdna, const char *stype, const char *vartype, const ch
 
 bool DNA_struct_elem_find(SDNA *sdna, const char *stype, const char *vartype, const char *name)
 {
-	
 	const int SDNAnr = DNA_struct_find_nr(sdna, stype);
 	
 	if (SDNAnr != -1) {