diff options
author | Campbell Barton <ideasman42@gmail.com> | 2016-07-12 04:48:04 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2016-07-12 04:56:45 +0300 |
commit | 0b3183d13cdbdcb06317fd1dd9b04ccd93a767c1 (patch) | |
tree | 84cde74eaf3706116c94920ecc813b83a1346017 /source/blender | |
parent | 7212ebd09f9720883581221be923ae5e97ff5d76 (diff) |
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.
Diffstat (limited to 'source/blender')
-rw-r--r-- | source/blender/blenloader/intern/readfile.c | 2 | ||||
-rw-r--r-- | source/blender/makesdna/DNA_genfile.h | 11 | ||||
-rw-r--r-- | source/blender/makesdna/DNA_sdna_types.h | 9 | ||||
-rw-r--r-- | source/blender/makesdna/intern/dna_genfile.c | 134 |
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) { |