diff options
Diffstat (limited to 'source/blender/blenkernel/intern/outliner_treehash.c')
| -rw-r--r-- | source/blender/blenkernel/intern/outliner_treehash.c | 238 |
1 files changed, 0 insertions, 238 deletions
diff --git a/source/blender/blenkernel/intern/outliner_treehash.c b/source/blender/blenkernel/intern/outliner_treehash.c deleted file mode 100644 index 03c327bec2f..00000000000 --- a/source/blender/blenkernel/intern/outliner_treehash.c +++ /dev/null @@ -1,238 +0,0 @@ -/* SPDX-License-Identifier: GPL-2.0-or-later */ - -/** \file - * \ingroup bke - * - * Tree hash for the outliner space. - */ - -#include <stdlib.h> -#include <string.h> - -#include "BLI_ghash.h" -#include "BLI_mempool.h" -#include "BLI_utildefines.h" - -#include "DNA_outliner_types.h" - -#include "BKE_outliner_treehash.h" - -#include "MEM_guardedalloc.h" - -typedef struct TseGroup { - TreeStoreElem **elems; - int lastused; - int size; - int allocated; -} TseGroup; - -/* Allocate structure for TreeStoreElements; - * Most of elements in treestore have no duplicates, - * so there is no need to preallocate memory for more than one pointer */ -static TseGroup *tse_group_create(void) -{ - TseGroup *tse_group = MEM_mallocN(sizeof(TseGroup), "TseGroup"); - tse_group->elems = MEM_mallocN(sizeof(TreeStoreElem *), "TseGroupElems"); - tse_group->size = 0; - tse_group->allocated = 1; - tse_group->lastused = 0; - return tse_group; -} - -static void tse_group_add_element(TseGroup *tse_group, TreeStoreElem *elem) -{ - if (UNLIKELY(tse_group->size == tse_group->allocated)) { - tse_group->allocated *= 2; - tse_group->elems = MEM_reallocN(tse_group->elems, - sizeof(TreeStoreElem *) * tse_group->allocated); - } - tse_group->elems[tse_group->size] = elem; - tse_group->size++; -} - -static void tse_group_remove_element(TseGroup *tse_group, TreeStoreElem *elem) -{ - int min_allocated = MAX2(1, tse_group->allocated / 2); - BLI_assert(tse_group->allocated == 1 || (tse_group->allocated % 2) == 0); - - tse_group->size--; - BLI_assert(tse_group->size >= 0); - for (int i = 0; i < tse_group->size; i++) { - if (tse_group->elems[i] == elem) { - memcpy(tse_group->elems[i], - tse_group->elems[i + 1], - (tse_group->size - (i + 1)) * sizeof(TreeStoreElem *)); - break; - } - } - - if (UNLIKELY(tse_group->size > 0 && tse_group->size <= min_allocated)) { - tse_group->allocated = min_allocated; - tse_group->elems = MEM_reallocN(tse_group->elems, - sizeof(TreeStoreElem *) * tse_group->allocated); - } -} - -static void tse_group_free(TseGroup *tse_group) -{ - MEM_freeN(tse_group->elems); - MEM_freeN(tse_group); -} - -static unsigned int tse_hash(const void *ptr) -{ - const TreeStoreElem *tse = ptr; - union { - short h_pair[2]; - unsigned int u_int; - } hash; - - BLI_assert((tse->type != TSE_SOME_ID) || !tse->nr); - - hash.h_pair[0] = tse->type; - hash.h_pair[1] = tse->nr; - - hash.u_int ^= BLI_ghashutil_ptrhash(tse->id); - - return hash.u_int; -} - -static bool tse_cmp(const void *a, const void *b) -{ - const TreeStoreElem *tse_a = a; - const TreeStoreElem *tse_b = b; - return tse_a->type != tse_b->type || tse_a->nr != tse_b->nr || tse_a->id != tse_b->id; -} - -static void fill_treehash(void *treehash, BLI_mempool *treestore) -{ - TreeStoreElem *tselem; - BLI_mempool_iter iter; - BLI_mempool_iternew(treestore, &iter); - - BLI_assert(treehash); - - while ((tselem = BLI_mempool_iterstep(&iter))) { - BKE_outliner_treehash_add_element(treehash, tselem); - } -} - -void *BKE_outliner_treehash_create_from_treestore(BLI_mempool *treestore) -{ - GHash *treehash = BLI_ghash_new_ex(tse_hash, tse_cmp, "treehash", BLI_mempool_len(treestore)); - fill_treehash(treehash, treestore); - return treehash; -} - -static void free_treehash_group(void *key) -{ - tse_group_free(key); -} - -void BKE_outliner_treehash_clear_used(void *treehash) -{ - GHashIterator gh_iter; - - GHASH_ITER (gh_iter, treehash) { - TseGroup *group = BLI_ghashIterator_getValue(&gh_iter); - group->lastused = 0; - } -} - -void *BKE_outliner_treehash_rebuild_from_treestore(void *treehash, BLI_mempool *treestore) -{ - BLI_assert(treehash); - - BLI_ghash_clear_ex(treehash, NULL, free_treehash_group, BLI_mempool_len(treestore)); - fill_treehash(treehash, treestore); - return treehash; -} - -void BKE_outliner_treehash_add_element(void *treehash, TreeStoreElem *elem) -{ - TseGroup *group; - void **val_p; - - if (!BLI_ghash_ensure_p(treehash, elem, &val_p)) { - *val_p = tse_group_create(); - } - group = *val_p; - group->lastused = 0; - tse_group_add_element(group, elem); -} - -void BKE_outliner_treehash_remove_element(void *treehash, TreeStoreElem *elem) -{ - TseGroup *group = BLI_ghash_lookup(treehash, elem); - - BLI_assert(group != NULL); - if (group->size <= 1) { - /* one element -> remove group completely */ - BLI_ghash_remove(treehash, elem, NULL, free_treehash_group); - } - else { - tse_group_remove_element(group, elem); - } -} - -static TseGroup *BKE_outliner_treehash_lookup_group(GHash *th, short type, short nr, struct ID *id) -{ - TreeStoreElem tse_template; - tse_template.type = type; - tse_template.nr = (type == TSE_SOME_ID) ? 0 : nr; /* we're picky! :) */ - tse_template.id = id; - - BLI_assert(th); - - return BLI_ghash_lookup(th, &tse_template); -} - -TreeStoreElem *BKE_outliner_treehash_lookup_unused(void *treehash, - short type, - short nr, - struct ID *id) -{ - TseGroup *group; - - BLI_assert(treehash); - - group = BKE_outliner_treehash_lookup_group(treehash, type, nr, id); - if (group) { - /* Find unused element, with optimization to start from previously - * found element assuming we do repeated lookups. */ - int size = group->size; - int offset = group->lastused; - - for (int i = 0; i < size; i++, offset++) { - if (offset >= size) { - offset = 0; - } - - if (!group->elems[offset]->used) { - group->lastused = offset; - return group->elems[offset]; - } - } - } - return NULL; -} - -TreeStoreElem *BKE_outliner_treehash_lookup_any(void *treehash, - short type, - short nr, - struct ID *id) -{ - TseGroup *group; - - BLI_assert(treehash); - - group = BKE_outliner_treehash_lookup_group(treehash, type, nr, id); - return group ? group->elems[0] : NULL; -} - -void BKE_outliner_treehash_free(void *treehash) -{ - BLI_assert(treehash); - - BLI_ghash_free(treehash, NULL, free_treehash_group); -} |