2.5 - Optimisations for Keyframe Drawing in DopeSheet

Keyframes are now prepared for drawing by being added to a binary-tree structure instead of using insertion-sort on a Double-Linked List. This gives rather significant improvements on a few bad cases (*).

I've implemented a basic Red-Black Tree whose nodes/data-structures can also be used as a simple Double-Linked List (ListBase) for this purpose. The implementation of this tree currently does not have support for removing individual nodes, since such capabilities aren't needed yet. 

Stats (using keyframes from an imported .bvh animation file):
* When only the keyframes are drawn (i.e. long keyframes are not identified), the time needed to draw the DopeSheet region 10 times went down from 4000ms to about 300ms.
* When long keyframes are considered as well, the same test has gone from 6000ms to 3000ms. There is still a bottleneck there that I haven't been able to remove yet (an attempt at this made the runtimes go through the roof - 32000 ms for the test done here).

Assorted Notes:
* Added missing headers for some files
* Fixed profiling flags for mingw. There was an extra space which prevented the sound-code from compiling.

1 files changed, 101 insertions, 0 deletions

diff --git a/source/blender/blenlib/BLI_dlrbTree.h b/source/blender/blenlib/BLI_dlrbTree.h
new file mode 100644
index 00000000000..eeb224ad1f4
--- /dev/null
+++ b/source/blender/blenlib/BLI_dlrbTree.h
@@ -0,0 +1,101 @@
+/**
+ * $Id: BLI_dlrbTree.h 21514 2009-07-11 05:41:21Z aligorith $
+ *
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * 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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2009 Blender Foundation, Joshua Leung
+ * All rights reserved.
+ *
+ * Contributor(s): Joshua Leung (original author)
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef BLI_DLRB_TREE_H
+#define BLI_DLRB_TREE_H
+
+/* Double-Linked Red-Black Tree Implementation:
+ * 
+ * This is simply a Red-Black Tree implementation whose nodes can later
+ * be arranged + retrieved as elements in a Double-Linked list (i.e. ListBase).
+ * The Red-Black Tree implementation is based on the methods defined by Wikipedia.
+ */
+
+/* ********************************************** */
+/* Data Types and Type Defines  */
+
+/* Base Structs --------------------------------- */
+
+/* Basic Layout for a Node */
+typedef struct DLRBT_Node {
+	/* ListBase capabilities */
+	struct DLRBT_Node *next, *prev;		
+	
+	/* Tree Associativity settings */
+	struct DLRBT_Node *left, *right;
+	struct DLRBT_Node *parent;
+	
+	char tree_col;
+	/* ... for nice alignment, next item should usually be a char too... */
+} DLRBT_Node;
+
+/* Red/Black defines for tree_col */
+enum eDLRBT_Colors {
+	DLRBT_BLACK= 0,
+	DLRBT_RED,
+};
+
+/* -------- */
+
+/* The Tree Data */
+typedef struct DLRBT_Tree {
+	/* ListBase capabilities */
+	void *first, *last;			/* these should be based on DLRBT_Node-s */
+
+	/* Root Node */
+	void *root;					/* this should be based on DLRBT_Node-s */
+} DLRBT_Tree;
+
+/* ********************************************** */
+/* Public API */
+
+/* Create a new tree, and initialise as necessary */
+DLRBT_Tree *BLI_dlrbTree_new(void);
+
+/* Initialises some given trees */
+void BLI_dlrbTree_init(DLRBT_Tree *tree);
+
+/* Free some tree */
+void BLI_dlrbTree_free(DLRBT_Tree *tree);
+
+/* Make sure the tree's Double-Linked list representation is valid */
+void BLI_dlrbTree_linkedlist_sync(DLRBT_Tree *tree);
+
+
+
+/* Balance the tree after the given element has been added to it 
+ * (using custom code, in the Binary Tree way).
+ */
+void BLI_dlrbTree_insert(DLRBT_Tree *tree, DLRBT_Node *node);
+
+/* Remove the given element from the tree and balance again */
+// FIXME: this is not implemented yet... 
+void BLI_dlrbTree_remove(DLRBT_Tree *tree, DLRBT_Node *node);
+
+/* ********************************************** */
+
+#endif // BLI_DLRB_TREE_H