[Bf-blender-cvs] [318f347] soc-2016-layer_manager: Store array of all layer items in the layer tree

[Julian Eisel]

Commit: 318f347cd4f224185bb2020610c12a561ea40e25
Author: Julian Eisel
Date:   Wed Jun 8 02:08:38 2016 +0200
Branches: soc-2016-layer_manager
https://developer.blender.org/rB318f347cd4f224185bb2020610c12a561ea40e25

Store array of all layer items in the layer tree

Coexists with LayerTree.items and LayerTreeItem.childs listbases which were used for recursive iterations over the layer tree (using BKE_layertree_iterate or BKE_layeritem_iterate_childs). However, it was a bit annoying having to use this everywhere, especially if many args had to be passed as void *. Also, iterative methods with arrays instead of listbases should give us a bit of speedup.
It's possible LayerTree.items will not be needed anymore, but will leave in for now.

Array is only used on BKE level so far.

===================================================================

M	source/blender/blenkernel/BKE_layer.h
M	source/blender/blenkernel/intern/layer.c
M	source/blender/makesdna/DNA_space_types.h

===================================================================

diff --git a/source/blender/blenkernel/BKE_layer.h b/source/blender/blenkernel/BKE_layer.h
index 49f8fb7..e6896cf 100644
--- a/source/blender/blenkernel/BKE_layer.h
+++ b/source/blender/blenkernel/BKE_layer.h
@@ -58,6 +58,11 @@ void BKE_layertree_delete(LayerTree *ltree);
 bool BKE_layertree_iterate(const LayerTree *ltree, LayerTreeIterFunc foreach, void *customdata, const bool inverse);
 int  BKE_layertree_get_totitems(const LayerTree *ltree);
 
+#define BKE_LAYERTREE_ITER_START(ltree, idx_name, litem_name) \
+	for (int idx_name = 0; idx_name < BKE_layertree_get_totitems(ltree); idx_name++) { \
+		LayerTreeItem *litem_name = ltree->items_all[idx_name];
+#define BKE_LAYERTREE_ITER_END } (void)0
+
 /* -------------------------------------------------------------------- */
 /* Layer Tree Item */
 
diff --git a/source/blender/blenkernel/intern/layer.c b/source/blender/blenkernel/intern/layer.c
index 1b92df3..c12ea80 100644
--- a/source/blender/blenkernel/intern/layer.c
+++ b/source/blender/blenkernel/intern/layer.c
@@ -44,6 +44,8 @@
 
 #include "MEM_guardedalloc.h"
 
+static void layeritem_free(LayerTreeItem *litem);
+
 
 /* -------------------------------------------------------------------- */
 /** \name Layer Tree
@@ -61,12 +63,16 @@ LayerTree *BKE_layertree_new(const eLayerTree_Type type)
 
 void BKE_layertree_delete(LayerTree *ltree)
 {
-	for (LayerTreeItem *litem = ltree->items.first, *next_litem; litem; litem = next_litem) {
-		next_litem = litem->next;
-		BKE_layeritem_remove(litem, true);
+	BKE_LAYERTREE_ITER_START(ltree, i, litem)
+	{
+		/* layeritem_free does all we need in this case. No un-registering needed */
+		layeritem_free(litem);
 	}
-	BLI_assert(BLI_listbase_is_empty(&ltree->items));
+	BKE_LAYERTREE_ITER_END;
 
+	if (ltree->items_all) {
+		MEM_freeN(ltree->items_all);
+	}
 	MEM_freeN(ltree);
 }
 
@@ -122,6 +128,9 @@ int BKE_layertree_get_totitems(const LayerTree *ltree)
 
 /**
  * Register an already allocated \a litem.
+ *
+ * \note Reallocates memory for item storage array, if you want to add many items at once,
+ * better do differently (e.g. _ex version that allows reserving memory)
  */
 void BKE_layeritem_register(
         LayerTree *tree, LayerTreeItem *litem, LayerTreeItem *parent,
@@ -129,6 +138,7 @@ void BKE_layeritem_register(
         const LayerItemPollFunc poll, LayerItemDrawFunc draw, LayerItemDrawSettingsFunc draw_settings)
 {
 	litem->type = type;
+	litem->index = tree->tot_items;
 	litem->tree = tree;
 	BLI_strncpy(litem->name, name, sizeof(litem->name));
 
@@ -137,7 +147,9 @@ void BKE_layeritem_register(
 	litem->draw = draw;
 	litem->draw_settings = draw_settings;
 
-	tree->tot_items++;
+	/* add to item array */
+	tree->items_all = MEM_reallocN(tree->items_all, sizeof(*tree->items_all) * ++tree->tot_items);
+	tree->items_all[tree->tot_items - 1] = litem;
 
 	if (parent) {
 		BLI_assert(ELEM(parent->type, LAYER_ITEMTYPE_GROUP));
@@ -168,29 +180,52 @@ LayerTreeItem *BKE_layeritem_add(
 	return litem;
 }
 
+static void layeritem_free(LayerTreeItem *litem)
+{
+	if (litem->free) {
+		litem->free(litem);
+	}
+	MEM_freeN(litem);
+}
+
+
 /**
- * Free and unlink \a litem from the list it's stored in.
+ * Recursive function to remove \a litem. Used to avoid multiple realloc's
+ * for LayerTree.items_all, instead caller can simply realloc once (afterwards!).
  *
  * \param remove_children: Free and unlink all children (and their children, etc) of \a litem as well.
- * \note Recursive
  */
-void BKE_layeritem_remove(LayerTreeItem *litem, const bool remove_children)
+static void layeritem_remove_ex(LayerTreeItem *litem, const bool remove_children)
 {
 	BLI_remlink(litem->parent ? &litem->parent->childs : &litem->tree->items, litem);
+
+	for (int i = litem->index + 1; i < litem->tree->tot_items; i++) {
+		litem->tree->items_all[i - 1] = litem->tree->items_all[i];
+		litem->tree->items_all[i - 1]->index--;
+	}
 	litem->tree->tot_items--;
 
 	if (remove_children) {
 		for (LayerTreeItem *child = litem->childs.first, *child_next; child; child = child_next) {
 			child_next = child->next;
-			BKE_layeritem_remove(child, true);
+			layeritem_remove_ex(child, true);
 		}
 		BLI_assert(BLI_listbase_is_empty(&litem->childs));
 	}
+	layeritem_free(litem);
+}
 
-	if (litem->free) {
-		litem->free(litem);
-	}
-	MEM_freeN(litem);
+/**
+ * Free and unlink \a litem from the list and the array it's stored in.
+ *
+ * \param remove_children: Free and unlink all children (and their children, etc) of \a litem as well.
+ * \note Calls recursive #layeritem_remove_ex.
+ */
+void BKE_layeritem_remove(LayerTreeItem *litem, const bool remove_children)
+{
+	LayerTree *ltree = litem->tree; /* store before deleting litem */
+	layeritem_remove_ex(litem, remove_children);
+	ltree->items_all = MEM_reallocN(ltree->items_all, sizeof(*ltree->items_all) * ltree->tot_items);
 }
 
 /**
diff --git a/source/blender/makesdna/DNA_space_types.h b/source/blender/makesdna/DNA_space_types.h
index f8e73db..782c3f4 100644
--- a/source/blender/makesdna/DNA_space_types.h
+++ b/source/blender/makesdna/DNA_space_types.h
@@ -1344,6 +1344,8 @@ typedef struct LayerTree {
 	/* LayerTreeItem - Only items of the first level in the hierarchy, these may have children then.
 	 * TODO check if worth using array instead */
 	ListBase items;
+	/* Array of all layer tree items, including all childs. Using array in hope it speeds up iterations. */
+	struct LayerTreeItem **items_all;
 } LayerTree;
 
 /**
@@ -1353,7 +1355,8 @@ typedef struct LayerTree {
 typedef struct LayerTreeItem {
 	struct LayerTreeItem *next, *prev;
 
-	int type, pad; /* eLayerTreeItem_Type */
+	int type;      /* eLayerTreeItem_Type */
+	int index;     /* index of the item - stored to avoid loockups */
 	char name[64]; /* MAX_NAME */
 
 	struct LayerTree *tree; /* pointer back to layer tree - TODO check if needed */