diff options
Diffstat (limited to 'source/blender/blenkernel/intern/fcurve_cache.c')
| -rw-r--r-- | source/blender/blenkernel/intern/fcurve_cache.c | 189 |
1 files changed, 189 insertions, 0 deletions
diff --git a/source/blender/blenkernel/intern/fcurve_cache.c b/source/blender/blenkernel/intern/fcurve_cache.c new file mode 100644 index 00000000000..8142b871edd --- /dev/null +++ b/source/blender/blenkernel/intern/fcurve_cache.c @@ -0,0 +1,189 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +/** \file + * \ingroup bke + * + * Cache F-Curve look-ups. + */ + +#include <stdlib.h> +#include <string.h> + +#include "MEM_guardedalloc.h" + +#include "DNA_anim_types.h" + +#include "BLI_ghash.h" +#include "BLI_listbase.h" + +#include "BKE_fcurve.h" + +/* -------------------------------------------------------------------- */ +/** \name F-Curve Path Cache + * + * Cache for finding curves by RNA path & array index. + * \{ */ + +struct FCurvePathCache_Span { + /** Index in the #FCurvePathCache.fcurve_array indicating the start of the span. */ + uint index; + /** Number of items in the span in #FCurvePathCache.fcurve_array that share an RNA path. */ + uint len; +}; + +struct FCurvePathCache { + /** All curves sorted by (#FCurve.rna_path, #FCurve.array_index) */ + FCurve **fcurve_array; + uint fcurve_array_len; + /** Storage for values of `span_from_rna_path`. */ + struct FCurvePathCache_Span *span_table; + /** Map `FCurve.rna_path` to elements in #FCurvePathCache.span_table */ + GHash *span_from_rna_path; +}; + +/** + * #qsort callback for an #FCurve array. + */ +static int fcurve_cmp_for_cache(const void *fcu_a_p, const void *fcu_b_p) +{ + const FCurve *fcu_a = *((const FCurve **)fcu_a_p); + const FCurve *fcu_b = *((const FCurve **)fcu_b_p); + const int cmp = strcmp(fcu_a->rna_path, fcu_b->rna_path); + if (cmp != 0) { + return cmp; + } + if (fcu_a->array_index < fcu_b->array_index) { + return -1; + } + if (fcu_a->array_index > fcu_b->array_index) { + return 1; + } + return 0; +} + +struct FCurvePathCache *BKE_fcurve_pathcache_create(ListBase *list) +{ + const uint fcurve_array_len = BLI_listbase_count(list); + FCurve **fcurve_array = MEM_mallocN(sizeof(*fcurve_array) * fcurve_array_len, __func__); + uint i; + LISTBASE_FOREACH_INDEX (FCurve *, fcu, list, i) { + fcurve_array[i] = fcu; + } + qsort(fcurve_array, fcurve_array_len, sizeof(FCurve *), fcurve_cmp_for_cache); + + /* Allow for the case no F-curves share an RNA-path, otherwise this is over-allocated. + * Although in practice it's likely to only be 3-4x as large as is needed + * (with transform channels for e.g.). */ + struct FCurvePathCache_Span *span_table = MEM_mallocN(sizeof(*span_table) * fcurve_array_len, + __func__); + + /* May over reserve, harmless. */ + GHash *span_from_rna_path = BLI_ghash_str_new_ex(__func__, fcurve_array_len); + uint span_index = 0; + i = 0; + while (i < fcurve_array_len) { + uint i_end; + for (i_end = i + 1; i_end < fcurve_array_len; i_end++) { + /* As the indices are sorted, we know a decrease means a new RNA path is found. */ + if (fcurve_array[i]->array_index > fcurve_array[i_end]->array_index) { + BLI_assert(!STREQ(fcurve_array[i]->rna_path, fcurve_array[i_end]->rna_path)); + break; + } + if (!STREQ(fcurve_array[i]->rna_path, fcurve_array[i_end]->rna_path)) { + break; + } + } + + struct FCurvePathCache_Span *span = &span_table[span_index++]; + span->index = i; + span->len = i_end - i; + BLI_ghash_insert(span_from_rna_path, fcurve_array[i]->rna_path, span); + i = i_end; + } + + struct FCurvePathCache *fcache = MEM_callocN(sizeof(struct FCurvePathCache), __func__); + fcache->fcurve_array = fcurve_array; + fcache->fcurve_array_len = fcurve_array_len; + fcache->span_table = span_table; + fcache->span_from_rna_path = span_from_rna_path; + + return fcache; +} + +void BKE_fcurve_pathcache_destroy(struct FCurvePathCache *fcache) +{ + MEM_freeN(fcache->fcurve_array); + MEM_freeN(fcache->span_table); + BLI_ghash_free(fcache->span_from_rna_path, NULL, NULL); + MEM_freeN(fcache); +} + +FCurve *BKE_fcurve_pathcache_find(struct FCurvePathCache *fcache, + const char *rna_path, + const int array_index) +{ + const struct FCurvePathCache_Span *span = BLI_ghash_lookup(fcache->span_from_rna_path, rna_path); + if (span == NULL) { + return NULL; + } + + FCurve **fcurve = fcache->fcurve_array + span->index; + const uint len = span->len; + for (int i = 0; i < len; i++) { + if (fcurve[i]->array_index == array_index) { + return fcurve[i]; + } + /* As these are sorted, early exit. */ + if (fcurve[i]->array_index > array_index) { + break; + } + } + return NULL; +} + +/** + * Fill in an array of F-Curve, leave NULL when not found. + * + * \return The number of F-Curves found. + */ +int BKE_fcurve_pathcache_find_array(struct FCurvePathCache *fcache, + const char *rna_path, + FCurve **fcurve_result, + int fcurve_result_len) +{ + memset(fcurve_result, 0x0, sizeof(*fcurve_result) * fcurve_result_len); + + const struct FCurvePathCache_Span *span = BLI_ghash_lookup(fcache->span_from_rna_path, rna_path); + if (span == NULL) { + return 0; + } + + int found = 0; + FCurve **fcurve = fcache->fcurve_array + span->index; + const uint len = span->len; + for (int i = 0; i < len; i++) { + /* As these are sorted, early exit. */ + if ((uint)fcurve[i]->array_index > (uint)fcurve_result_len) { + break; + } + fcurve_result[fcurve[i]->array_index] = fcurve[i]; + found += 1; + } + return found; +} + +/** \} */ |