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.

11 files changed, 898 insertions, 206 deletions

diff --git a/config/win32-mingw-config.py b/config/win32-mingw-config.py
index 1223a4c49e9..375b8c36ce8 100644
--- a/config/win32-mingw-config.py
+++ b/config/win32-mingw-config.py
@@ -148,7 +148,7 @@ LLIBS = ['-lshell32', '-lshfolder', '-lgdi32', '-lmsvcrt', '-lwinmm', '-lmingw32
 BF_DEBUG = False
 BF_DEBUG_CCFLAGS= ['-g']
 
-BF_PROFILE_CCFLAGS = ['-pg', '-g ']
+BF_PROFILE_CCFLAGS = ['-pg', '-g']
 BF_PROFILE_LINKFLAGS = ['-pg']
 BF_PROFILE_FLAGS = BF_PROFILE_CCFLAGS
 BF_PROFILE = False
diff --git a/source/blender/blenkernel/BKE_animsys.h b/source/blender/blenkernel/BKE_animsys.h
index b45917e6ca1..2447d1823af 100644
--- a/source/blender/blenkernel/BKE_animsys.h
+++ b/source/blender/blenkernel/BKE_animsys.h
@@ -1,5 +1,28 @@
-/* Testing code for new animation system in 2.5 
- * Copyright 2009, Joshua Leung
+/**
+ * $Id$
+ *
+ * ***** 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 BKE_ANIM_SYS_H
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
diff --git a/source/blender/blenlib/intern/DLRB_tree.c b/source/blender/blenlib/intern/DLRB_tree.c
new file mode 100644
index 00000000000..debe02164fb
--- /dev/null
+++ b/source/blender/blenlib/intern/DLRB_tree.c
@@ -0,0 +1,359 @@
+/**
+ * $Id: BLI_dlrbTree.c 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 *****
+ */
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_blenlib.h"
+#include "BLI_dlrbTree.h"
+
+#include "DNA_listBase.h"
+
+/* *********************************************** */
+/* Tree API */
+
+/* Create a new tree, and initialise as necessary */
+DLRBT_Tree *BLI_dlrbTree_new (void)
+{
+	/* just allocate for now */
+	return MEM_callocN(sizeof(DLRBT_Tree), "DLRBT_Tree");
+}
+
+/* Just zero out the pointers used */
+void BLI_dlrbTree_init (DLRBT_Tree *tree) 
+{
+	if (tree == NULL)
+		return;
+		
+	tree->first= tree->last= tree->root= NULL;
+}
+
+/* Helper for traversing tree and freeing sub-nodes */
+static void recursive_tree_free_nodes (DLRBT_Node *node)
+{
+	/* sanity check */
+	if (node == NULL)
+		return;
+	
+	/* free child nodes + subtrees */
+	recursive_tree_free_nodes(node->left);
+	recursive_tree_free_nodes(node->right);
+	
+	/* free self */
+	MEM_freeN(node);
+}
+
+/* Free the given tree's data but not the tree itself */
+void BLI_dlrbTree_free (DLRBT_Tree *tree)
+{
+	if (tree == NULL)
+		return;
+	
+	/* if the list-base stuff is set, just use that (and assume its set), 
+	 * otherwise, we'll need to traverse the tree...
+	 */
+	if (tree->first) {
+		/* free list */
+		BLI_freelistN((ListBase *)tree);
+	}
+	else {
+		/* traverse tree, freeing sub-nodes */
+		recursive_tree_free_nodes(tree->root);
+	}
+	
+	/* clear pointers */
+	tree->first= tree->last= tree->root= NULL;
+}
+
+/* ------- */
+
+/* Helper function - used for traversing down the tree from the root to add nodes in order */
+static void linkedlist_sync_add_node (DLRBT_Tree *tree, DLRBT_Node *node)
+{
+	/* sanity checks */
+	if ((tree == NULL) || (node == NULL))
+		return;
+	
+	/* add left-node (and its subtree) */
+	linkedlist_sync_add_node(tree, node->left);
+	
+	/* now add self
+	 *	- must remove detach from other links first
+	 *	  (for now, only clear own pointers)
+	 */
+	node->prev= node->next= NULL;
+	BLI_addtail((ListBase *)tree, (Link *)node);
+	
+	/* finally, add right node (and its subtree) */
+	linkedlist_sync_add_node(tree, node->right);
+}
+
+/* Make sure the tree's Double-Linked list representation is valid */
+void BLI_dlrbTree_linkedlist_sync (DLRBT_Tree *tree)
+{
+	/* sanity checks */
+	if (tree == NULL)
+		return;
+		
+	/* clear list-base pointers so that the new list can be added properly */
+	tree->first= tree->last= NULL;
+	
+	/* start adding items from the root */
+	linkedlist_sync_add_node(tree, tree->root);
+}
+
+/* *********************************************** */
+/* Tree Relationships Utilities */
+
+/* get the 'grandparent' - the parent of the parent - of the given node */
+static DLRBT_Node *get_grandparent (DLRBT_Node *node)
+{
+	if (node && node->parent)
+		return node->parent->parent;
+	else
+		return NULL;
+}
+
+/* get the 'uncle' - the sibling of the parent - of the given node */
+static DLRBT_Node *get_uncle (DLRBT_Node *node)
+{
+	DLRBT_Node *gpn= get_grandparent(node);
+	
+	/* return the child of the grandparent which isn't the node's parent */
+	if (gpn) {
+		if (gpn->left == node->parent)
+			return gpn->right;
+		else
+			return gpn->left;
+	}
+	
+	/* not found */
+	return NULL;
+}
+
+/* *********************************************** */
+/* Tree Rotation Utilities */
+
+/* Left Rotation is only done for Right-Right Case, and Left-Right Case */
+static void rotate_left (DLRBT_Tree *tree, DLRBT_Node *root)
+{
+	DLRBT_Node **root_slot, *pivot;
+	
+	/* pivot is simply the root's right child, to become the root's parent */
+	pivot= root->right;
+	if (pivot == NULL)
+		return;
+	
+	if (root->parent) {
+		if (root == root->parent->left)
+			root_slot= &root->parent->left;
+		else
+			root_slot= &root->parent->right;
+	}
+	else
+		root_slot= ((DLRBT_Node**)&tree->root);//&((DLRBT_Node*)tree->root);
+		
+	/* - pivot's left child becomes root's right child
+	 * - root now becomes pivot's left child  
+	 */
+	root->right= pivot->left;	
+	if (pivot->left) pivot->left->parent= root;
+	
+	pivot->left= root;
+	pivot->parent= root->parent;
+	root->parent= pivot;
+	
+	/* make the pivot the new root */
+	if (root_slot)
+		*root_slot= pivot;
+}
+
+static void rotate_right (DLRBT_Tree *tree, DLRBT_Node *root)
+{
+	DLRBT_Node **root_slot, *pivot;
+	
+	/* pivot is simply the root's left child, to become the root's parent */
+	pivot= root->left;
+	if (pivot == NULL)
+		return;
+	
+	if (root->parent) {
+		if (root == root->parent->left)
+			root_slot= &root->parent->left;
+		else
+			root_slot= &root->parent->right;
+	}
+	else
+		root_slot= ((DLRBT_Node**)&tree->root);//&((DLRBT_Node*)tree->root);
+		
+	/* - pivot's right child becomes root's left child
+	 * - root now becomes pivot's right child  
+	 */
+	root->left= pivot->right;	
+	if (pivot->right) pivot->right->parent= root;
+	
+	pivot->right= root;
+	pivot->parent= root->parent;
+	root->parent= pivot;
+	
+	/* make the pivot the new root */
+	if (root_slot)
+		*root_slot= pivot;
+}
+
+/* *********************************************** */
+/* Post-Insertion Balancing  */
+
+/* forward defines for insertion checks */
+static void insert_check_1(DLRBT_Tree *tree, DLRBT_Node *node);
+static void insert_check_2(DLRBT_Tree *tree, DLRBT_Node *node);
+static void insert_check_3(DLRBT_Tree *tree, DLRBT_Node *node);
+static void insert_check_4(DLRBT_Tree *tree, DLRBT_Node *node);
+
+/* ----- */
+
+/* W. 1) Root must be black (so that the 2nd-generation can have a black parent) */
+static void insert_check_1 (DLRBT_Tree *tree, DLRBT_Node *node)
+{
+	if (node) {
+		/* if this is the root, just ensure that it is black */
+		if (node->parent == NULL)
+			node->tree_col= DLRBT_BLACK;
+		else
+			insert_check_2(tree, node);
+	}
+}
+
+/* W. 2+3) Parent of node must be black, otherwise recolor and flush */
+static void insert_check_2 (DLRBT_Tree *tree, DLRBT_Node *node)
+{
+	/* if the parent is not black, we need to change that... */
+	if (node && node->parent && node->parent->tree_col) {
+		DLRBT_Node *unc= get_uncle(node);
+		
+		/* if uncle and parent are both red, need to change them to black and make 
+		 * the parent black in order to satisfy the criteria of each node having the
+		 * same number of black nodes to its leaves
+		 */
+		if (unc && unc->tree_col) {
+			DLRBT_Node *gp= get_grandparent(node);
+			
+			/* make the n-1 generation nodes black */
+			node->parent->tree_col= unc->tree_col= DLRBT_BLACK;
+			
+			/* - make the grandparent red, so that we maintain alternating red/black property 
+			 *  (it must exist, so no need to check for NULL here),
+			 * - as the grandparent may now cause inconsistencies with the rest of the tree, 
+			 *   we must flush up the tree and perform checks/rebalancing/repainting, using the 
+			 * 	grandparent as the node of interest
+			 */
+			gp->tree_col= DLRBT_RED;
+			insert_check_1(tree, gp);
+		}
+		else {
+			/* we've got an unbalanced branch going down the grandparent to the parent,
+			 * so need to perform some rotations to re-balance the tree
+			 */
+			insert_check_3(tree, node);
+		}
+	}
+}
+
+/* W. 4) Perform rotation on sub-tree containing the 'new' node */
+static void insert_check_3 (DLRBT_Tree *tree, DLRBT_Node *node)
+{
+	DLRBT_Node *gp= get_grandparent(node);
+	
+	/* check that grandparent and node->parent exist (jut in case... really shouldn't happen on a good tree) */
+	if (node && node->parent && gp) {
+		/* a left rotation will switch the roles of node and its parent, assuming that
+		 * the parent is the left child of the grandparent... otherwise, rotation direction
+		 * should be swapped
+		 */
+		if ((node == node->parent->right) && (node->parent == gp->left)) {
+			rotate_left(tree, node);
+			node= node->left;
+		}
+		else if ((node == node->parent->left) && (node->parent == gp->right)) {
+			rotate_right(tree, node); 
+			node= node->right;
+		}
+		// TODO: what about other cases?
+		
+		/* fix old parent's color-tagging */
+		insert_check_4(tree, node);
+	}
+}
+
+/* W. 5) Perform rotation in the opposite direction on the parent of the given node */
+static void insert_check_4 (DLRBT_Tree *tree, DLRBT_Node *node)
+{
+	DLRBT_Node *gp= get_grandparent(node);
+	
+	if (node == NULL)
+		return;
+	
+	/* modify the coloring of the grandparent and parent so that they still satisfy the constraints */
+	node->parent->tree_col= DLRBT_BLACK;
+	gp->tree_col= DLRBT_RED;
+	
+	/* if there are several nodes that all form a left chain, do a right rotation to correct this
+	 * (or a rotation in the opposite direction if they all form a right chain)
+	 */
+	if ((node == node->parent->left) && (node->parent == gp->left))
+		rotate_right(tree, gp);
+	else /* ((node == node->parent->right) && (node->parent == gp->right)) */
+		rotate_left(tree, gp);
+}
+
+/* ----- */
+
+/* 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)
+{
+	/* sanity checks */
+	if ((tree == NULL) || (node == NULL))
+		return;
+		
+	/* firstly, the node we just added should be red by default */
+	node->tree_col= DLRBT_RED;
+		
+	/* start from case 1, an trek through the tail-recursive insertion checks */
+	insert_check_1(tree, node);
+}
+
+/* *********************************************** */
+/* Remove */
+
+// TODO: this hasn't been coded yet, since this functionality was not needed by the author
+
+/* *********************************************** */
diff --git a/source/blender/editors/animation/keyframes_draw.c b/source/blender/editors/animation/keyframes_draw.c
index 64e008b92ca..78ceb4a0149 100644
--- a/source/blender/editors/animation/keyframes_draw.c
+++ b/source/blender/editors/animation/keyframes_draw.c
@@ -17,12 +17,12 @@
  * 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) 2001-2002 by NaN Holding BV.
+ * The Original Code is Copyright (C) 2009 Blender Foundation, Joshua Leung
  * All rights reserved.
  *
  * The Original Code is: all of this file.
  *
- * Contributor(s): Joshua Leung
+ * Contributor(s): Joshua Leung (full recode)
  *
  * ***** END GPL LICENSE BLOCK *****
  */
@@ -42,8 +42,7 @@
 
 #include "BLI_blenlib.h"
 #include "BLI_arithb.h"
-
-/* Types --------------------------------------------------------------- */
+#include "BLI_dlrbTree.h"
 
 #include "DNA_listBase.h"
 #include "DNA_anim_types.h"
@@ -75,8 +74,6 @@
 #include "BKE_context.h"
 #include "BKE_utildefines.h"
 
-/* Everything from source (BIF, BDR, BSE) ------------------------------ */ 
-
 #include "BIF_gl.h"
 #include "BIF_glutil.h"
 
@@ -93,53 +90,99 @@
 
 /* *************************** Keyframe Processing *************************** */
 
-/* The equivalent of add_to_cfra_elem except this version 
- * makes ActKeyColumns - one of the two datatypes required
- * for DopeSheet drawing.
- */
-static void add_bezt_to_keycolumnslist(ListBase *keys, BezTriple *bezt)
+/* Create a ActKeyColumn from a BezTriple */
+static ActKeyColumn *bezt_to_new_actkeycolumn(BezTriple *bezt)
 {
-	ActKeyColumn *ak, *akn;
+	ActKeyColumn *ak= MEM_callocN(sizeof(ActKeyColumn), "ActKeyColumn");
 	
-	if (ELEM(NULL, keys, bezt)) return;
+	/* store settings based on state of BezTriple */
+	ak->cfra= bezt->vec[1][0];
+	ak->sel= BEZSELECTED(bezt) ? SELECT : 0;
 	
-	/* try to any existing key to replace, or where to insert after */
-	for (ak= keys->last; ak; ak= ak->prev) {
-		/* do because of double keys */
-		if (ak->cfra == bezt->vec[1][0]) {			
-			/* set selection status and 'touched' status */
-			if (BEZSELECTED(bezt)) ak->sel = SELECT;
-			ak->modified += 1;
-			
-			return;
+	// TODO: handle type = bezt->h1 or bezt->h2
+	ak->handle_type= 0; 
+	
+	/* set 'modified', since this is used to identify long keyframes */
+	ak->modified = 1;
+	
+	return ak;
+}
+
+/* Add the given BezTriple to the given 'list' of Keyframes */
+static void add_bezt_to_keycolumns_list(DLRBT_Tree *keys, BezTriple *bezt)
+{
+	ActKeyColumn *new_ak=NULL;
+	
+	if ELEM(NULL, keys, bezt) return;
+	
+	/* if there are no keys already, just add as root */
+	if (keys->root == NULL) {
+		/* just add this as the root, then call the tree-balancing functions to validate */
+		new_ak= bezt_to_new_actkeycolumn(bezt);
+		keys->root= (DLRBT_Node *)new_ak;
+	}
+	else {
+		ActKeyColumn *ak, *akp=NULL, *akn=NULL;
+		
+		/* traverse tree to find an existing entry to update the status of, 
+		 * or a suitable point to add at
+		 */
+		for (ak= keys->root; ak; akp= ak, ak= akn) {
+			/* check if this is a match, or whether we go left or right */
+			if (ak->cfra == bezt->vec[1][0]) {
+				/* set selection status and 'touched' status */
+				if (BEZSELECTED(bezt)) ak->sel = SELECT;
+				ak->modified += 1;
+				
+				/* done... no need to insert */
+				return;
+			}
+			else {
+				ActKeyColumn **aknp= NULL; 
+				
+				/* check if go left or right, but if not available, add new node */
+				if (ak->cfra < bezt->vec[1][0]) 
+					aknp= &ak->right;
+				else
+					aknp= &ak->left;
+					
+				/* if this does not exist, add a new node, otherwise continue... */
+				if (*aknp == NULL) {
+					/* add a new node representing this, and attach it to the relevant place */
+					new_ak= bezt_to_new_actkeycolumn(bezt);
+					new_ak->parent= ak;
+					*aknp= new_ak;
+					break;
+				}
+				else
+					akn= *aknp;
+			}
 		}
-		else if (ak->cfra < bezt->vec[1][0]) break;
 	}
 	
-	/* add new block */
-	akn= MEM_callocN(sizeof(ActKeyColumn), "ActKeyColumn");
-	if (ak) BLI_insertlinkafter(keys, ak, akn);
-	else BLI_addtail(keys, akn);
+	/* now, balance the tree taking into account this newly added node */
+	BLI_dlrbTree_insert(keys, (DLRBT_Node *)new_ak);
+}
+
+
+/* Create a ActKeyColumn for a pair of BezTriples */
+static ActKeyBlock *bezts_to_new_actkeyblock(BezTriple *prev, BezTriple *beztn)
+{
+	ActKeyBlock *ab= MEM_callocN(sizeof(ActKeyBlock), "ActKeyBlock");
 	
-	akn->cfra= bezt->vec[1][0];
-	akn->modified += 1;
+	ab->start= prev->vec[1][0];
+	ab->end= beztn->vec[1][0];
+	ab->val= beztn->vec[1][1];
 	
-	// TODO: handle type = bezt->h1 or bezt->h2
-	akn->handle_type= 0; 
+	ab->sel= (BEZSELECTED(prev) || BEZSELECTED(beztn)) ? SELECT : 0;
+	ab->modified = 1;
 	
-	if (BEZSELECTED(bezt))
-		akn->sel = SELECT;
-	else
-		akn->sel = 0;
+	return ab;
 }
 
-/* The equivalent of add_to_cfra_elem except this version 
- * makes ActKeyBlocks - one of the two datatypes required
- * for DopeSheet drawing.
- */
-static void add_bezt_to_keyblockslist(ListBase *blocks, FCurve *fcu, int index)
+static void add_bezt_to_keyblocks_list(DLRBT_Tree *blocks, FCurve *fcu, int index)
 {
-	ActKeyBlock *ab, *abn;
+	ActKeyBlock *new_ab= NULL;
 	BezTriple *beztn=NULL, *prev=NULL;
 	BezTriple *bezt;
 	int v;
@@ -148,6 +191,7 @@ static void add_bezt_to_keyblockslist(ListBase *blocks, FCurve *fcu, int index)
 	beztn= (fcu->bezt + index);
 	
 	/* we need to go through all beztriples, as they may not be in order (i.e. during transform) */
+	// TODO: this seems to be a bit of a bottleneck
 	for (v=0, bezt=fcu->bezt; v < fcu->totvert; v++, bezt++) {
 		/* skip if beztriple is current */
 		if (v != index) {
@@ -174,68 +218,119 @@ static void add_bezt_to_keyblockslist(ListBase *blocks, FCurve *fcu, int index)
 	if (IS_EQ(beztn->vec[1][1], beztn->vec[0][1])==0) return;
 	if (IS_EQ(prev->vec[1][1], prev->vec[2][1])==0) return;
 	
-	/* try to find a keyblock that starts on the previous beztriple 
-	 * Note: we can't search from end to try to optimise this as it causes errors there's
-	 * 		an A ___ B |---| B situation
-	 */
-	// FIXME: here there is a bug where we are trying to get the summary for the following channels
-	//		A|--------------|A ______________ B|--------------|B
-	//		A|------------------------------------------------|A
-	//		A|----|A|---|A|-----------------------------------|A
-	for (ab= blocks->first; ab; ab= ab->next) {
-		/* check if alter existing block or add new block */
-		if (ab->start == prev->vec[1][0]) {			
-			/* set selection status and 'touched' status */
-			if (BEZSELECTED(beztn)) ab->sel = SELECT;
-			ab->modified += 1;
-			
-			return;
+	
+	/* if there are no blocks already, just add as root */
+	if (blocks->root == NULL) {
+		/* just add this as the root, then call the tree-balancing functions to validate */
+		new_ab= bezts_to_new_actkeyblock(prev, beztn);
+		blocks->root= (DLRBT_Node *)new_ab;
+	}
+	else {
+		ActKeyBlock *ab, *abp=NULL, *abn=NULL;
+		
+		/* try to find a keyblock that starts on the previous beztriple, and add a new one if none start there
+		 * Note: we can't search from end to try to optimise this as it causes errors there's
+		 * 		an A ___ B |---| B situation
+		 */
+		// FIXME: here there is a bug where we are trying to get the summary for the following channels
+		//		A|--------------|A ______________ B|--------------|B
+		//		A|------------------------------------------------|A
+		//		A|----|A|---|A|-----------------------------------|A
+		for (ab= blocks->root; ab; abp= ab, ab= abn) {
+			/* check if this is a match, or whether we go left or right */
+			if (ab->start == prev->vec[1][0]) {
+				/* set selection status and 'touched' status */
+				if (BEZSELECTED(beztn)) ab->sel = SELECT;
+				ab->modified += 1;
+				
+				/* done... no need to insert */
+				return;
+			}
+			else {
+				ActKeyBlock **abnp= NULL; 
+				
+				/* check if go left or right, but if not available, add new node */
+				if (ab->start < prev->vec[1][0]) 
+					abnp= &ab->right;
+				else
+					abnp= &ab->left;
+					
+				/* if this does not exist, add a new node, otherwise continue... */
+				if (*abnp == NULL) {
+					/* add a new node representing this, and attach it to the relevant place */
+					new_ab= bezts_to_new_actkeyblock(prev, beztn);
+					new_ab->parent= ab;
+					*abnp= new_ab;
+					break;
+				}
+				else
+					abn= *abnp;
+			}
 		}
-		else if (ab->start < prev->vec[1][0]) break;
 	}
 	
-	/* add new block */
-	abn= MEM_callocN(sizeof(ActKeyBlock), "ActKeyBlock");
-	if (ab) BLI_insertlinkbefore(blocks, ab, abn);
-	else BLI_addtail(blocks, abn);
+	/* now, balance the tree taking into account this newly added node */
+	BLI_dlrbTree_insert(blocks, (DLRBT_Node *)new_ab);
+}
+
+/* --------- */
+
+/* Handle the 'touched' status of ActKeyColumn tree nodes */
+static void set_touched_actkeycolumn (ActKeyColumn *ak)
+{
+	/* sanity check */
+	if (ak == NULL)
+		return;
+		
+	/* deal with self first */
+	if (ak->modified) {
+		ak->modified= 0;
+		ak->totcurve++;
+	}
 	
-	abn->start= prev->vec[1][0];
-	abn->end= beztn->vec[1][0];
-	abn->val= beztn->vec[1][1];
+	/* children */
+	set_touched_actkeycolumn(ak->left);
+	set_touched_actkeycolumn(ak->right);
+}
+
+/* Handle the 'touched' status of ActKeyBlock tree nodes */
+static void set_touched_actkeyblock (ActKeyBlock *ab)
+{
+	/* sanity check */
+	if (ab == NULL)
+		return;
+		
+	/* deal with self first */
+	if (ab->modified) {
+		ab->modified= 0;
+		ab->totcurve++;
+	}
 	
-	if (BEZSELECTED(prev) || BEZSELECTED(beztn))
-		abn->sel = SELECT;
-	else
-		abn->sel = 0;
-	abn->modified = 1;
+	/* children */
+	set_touched_actkeyblock(ab->left);
+	set_touched_actkeyblock(ab->right);
 }
 
 /* *************************** Keyframe Drawing *************************** */
 
 /* helper function - find actkeycolumn that occurs on cframe */
-static ActKeyColumn *cfra_find_actkeycolumn (ListBase *keys, float cframe)
+static ActKeyColumn *cfra_find_actkeycolumn (ActKeyColumn *ak, float cframe)
 {
-	ActKeyColumn *ak, *ak2;
-	
-	if (keys==NULL) 
+	/* sanity checks */
+	if (ak == NULL)
 		return NULL;
-	 
-	/* search from both ends at the same time, and stop if we find match or if both ends meet */ 
-	for (ak=keys->first, ak2=keys->last; ak && ak2; ak=ak->next, ak2=ak2->prev) {
-		/* return whichever end encounters the frame */
-		if (ak->cfra == cframe)
-			return ak;
-		if (ak2->cfra == cframe)
-			return ak2;
-		
-		/* no matches on either end, so return NULL */
-		if (ak == ak2)
-			return NULL;
-	}
 	
-	return NULL;
+	/* check if this is a match, or whether it is in some subtree */
+	if (cframe < ak->cfra)
+		return cfra_find_actkeycolumn(ak->left, cframe);
+	else if (cframe > ak->cfra)
+		return cfra_find_actkeycolumn(ak->right, cframe);
+	else
+		return ak; /* match */
 }
 
+/* -------- */
+
 /* coordinates for diamond shape */
 static const float _unit_diamond_shape[4][2] = {
 	{0.0f, 1.0f},	/* top vert */
@@ -306,7 +401,7 @@ void draw_keyframe_shape (float x, float y, float xscale, float hsize, short sel
 	glTranslatef(-x, -y, 0.0f);
 }
 
-static void draw_keylist(View2D *v2d, ListBase *keys, ListBase *blocks, float ypos)
+static void draw_keylist(View2D *v2d, DLRBT_Tree *keys, DLRBT_Tree *blocks, float ypos)
 {
 	ActKeyColumn *ak;
 	ActKeyBlock *ab;
@@ -323,10 +418,10 @@ static void draw_keylist(View2D *v2d, ListBase *keys, ListBase *blocks, float yp
 			short startCurves, endCurves, totCurves;
 			
 			/* find out how many curves occur at each keyframe */
-			ak= cfra_find_actkeycolumn(keys, ab->start);
+			ak= cfra_find_actkeycolumn((ActKeyColumn *)keys->root, ab->start);
 			startCurves = (ak)? ak->totcurve: 0;
 			
-			ak= cfra_find_actkeycolumn(keys, ab->end);
+			ak= cfra_find_actkeycolumn((ActKeyColumn *)keys->root, ab->end);
 			endCurves = (ak)? ak->totcurve: 0;
 			
 			/* only draw keyblock if it appears in at all of the keyframes at lowest end */
@@ -382,76 +477,112 @@ static void draw_keylist(View2D *v2d, ListBase *keys, ListBase *blocks, float yp
 
 void draw_scene_channel(View2D *v2d, bDopeSheet *ads, Scene *sce, float ypos)
 {
-	ListBase keys = {0, 0};
-	ListBase blocks = {0, 0};
-
-	scene_to_keylist(ads, sce, &keys, &blocks);
-	draw_keylist(v2d, &keys, &blocks, ypos);
+	DLRBT_Tree keys, blocks;
+	
+	BLI_dlrbTree_init(&keys);
+	BLI_dlrbTree_init(&blocks);
+	
+		scene_to_keylist(ads, sce, &keys, &blocks);
 	
-	BLI_freelistN(&keys);
-	BLI_freelistN(&blocks);
+	BLI_dlrbTree_linkedlist_sync(&keys);
+	BLI_dlrbTree_linkedlist_sync(&blocks);
+	
+		draw_keylist(v2d, &keys, &blocks, ypos);
+	
+	BLI_dlrbTree_free(&keys);
+	BLI_dlrbTree_free(&blocks);
 }
 
 void draw_object_channel(View2D *v2d, bDopeSheet *ads, Object *ob, float ypos)
 {
-	ListBase keys = {0, 0};
-	ListBase blocks = {0, 0};
-
-	ob_to_keylist(ads, ob, &keys, &blocks);
-	draw_keylist(v2d, &keys, &blocks, ypos);
+	DLRBT_Tree keys, blocks;
 	
-	BLI_freelistN(&keys);
-	BLI_freelistN(&blocks);
+	BLI_dlrbTree_init(&keys);
+	BLI_dlrbTree_init(&blocks);
+	
+		ob_to_keylist(ads, ob, &keys, &blocks);
+	
+	BLI_dlrbTree_linkedlist_sync(&keys);
+	BLI_dlrbTree_linkedlist_sync(&blocks);
+	
+		draw_keylist(v2d, &keys, &blocks, ypos);
+	
+	BLI_dlrbTree_free(&keys);
+	BLI_dlrbTree_free(&blocks);
 }
 
 void draw_fcurve_channel(View2D *v2d, AnimData *adt, FCurve *fcu, float ypos)
 {
-	ListBase keys = {0, 0};
-	ListBase blocks = {0, 0};
-
-	fcurve_to_keylist(adt, fcu, &keys, &blocks);
-	draw_keylist(v2d, &keys, &blocks, ypos);
+	DLRBT_Tree keys, blocks;
+	
+	BLI_dlrbTree_init(&keys);
+	BLI_dlrbTree_init(&blocks);
+	
+		fcurve_to_keylist(adt, fcu, &keys, &blocks);
 	
-	BLI_freelistN(&keys);
-	BLI_freelistN(&blocks);
+	BLI_dlrbTree_linkedlist_sync(&keys);
+	BLI_dlrbTree_linkedlist_sync(&blocks);
+	
+		draw_keylist(v2d, &keys, &blocks, ypos);
+	
+	BLI_dlrbTree_free(&keys);
+	BLI_dlrbTree_free(&blocks);
 }
 
 void draw_agroup_channel(View2D *v2d, AnimData *adt, bActionGroup *agrp, float ypos)
 {
-	ListBase keys = {0, 0};
-	ListBase blocks = {0, 0};
-
-	agroup_to_keylist(adt, agrp, &keys, &blocks);
-	draw_keylist(v2d, &keys, &blocks, ypos);
+	DLRBT_Tree keys, blocks;
+	
+	BLI_dlrbTree_init(&keys);
+	BLI_dlrbTree_init(&blocks);
+	
+		agroup_to_keylist(adt, agrp, &keys, &blocks);
+	
+	BLI_dlrbTree_linkedlist_sync(&keys);
+	BLI_dlrbTree_linkedlist_sync(&blocks);
 	
-	BLI_freelistN(&keys);
-	BLI_freelistN(&blocks);
+		draw_keylist(v2d, &keys, &blocks, ypos);
+	
+	BLI_dlrbTree_free(&keys);
+	BLI_dlrbTree_free(&blocks);
 }
 
 void draw_action_channel(View2D *v2d, AnimData *adt, bAction *act, float ypos)
 {
-	ListBase keys = {0, 0};
-	ListBase blocks = {0, 0};
-
-	action_to_keylist(adt, act, &keys, &blocks);
-	draw_keylist(v2d, &keys, &blocks, ypos);
+	DLRBT_Tree keys, blocks;
+	
+	BLI_dlrbTree_init(&keys);
+	BLI_dlrbTree_init(&blocks);
+	
+		action_to_keylist(adt, act, &keys, &blocks);
 	
-	BLI_freelistN(&keys);
-	BLI_freelistN(&blocks);
+	BLI_dlrbTree_linkedlist_sync(&keys);
+	BLI_dlrbTree_linkedlist_sync(&blocks);
+	
+		draw_keylist(v2d, &keys, &blocks, ypos);
+	
+	BLI_dlrbTree_free(&keys);
+	BLI_dlrbTree_free(&blocks);
 }
 
 void draw_gpl_channel(View2D *v2d, bDopeSheet *ads, bGPDlayer *gpl, float ypos)
 {
-	ListBase keys = {0, 0};
+	DLRBT_Tree keys;
+	
+	BLI_dlrbTree_init(&keys);
 	
-	gpl_to_keylist(ads, gpl, &keys, NULL);
-	draw_keylist(v2d, &keys, NULL, ypos);
-	BLI_freelistN(&keys);
+		gpl_to_keylist(ads, gpl, &keys, NULL);
+	
+	BLI_dlrbTree_linkedlist_sync(&keys);
+	
+		draw_keylist(v2d, &keys, NULL, ypos);
+	
+	BLI_dlrbTree_free(&keys);
 }
 
 /* *************************** Keyframe List Conversions *************************** */
 
-void scene_to_keylist(bDopeSheet *ads, Scene *sce, ListBase *keys, ListBase *blocks)
+void scene_to_keylist(bDopeSheet *ads, Scene *sce, DLRBT_Tree *keys, DLRBT_Tree *blocks)
 {
 	if (sce) {
 		AnimData *adt;
@@ -483,7 +614,7 @@ void scene_to_keylist(bDopeSheet *ads, Scene *sce, ListBase *keys, ListBase *blo
 	}
 }
 
-void ob_to_keylist(bDopeSheet *ads, Object *ob, ListBase *keys, ListBase *blocks)
+void ob_to_keylist(bDopeSheet *ads, Object *ob, DLRBT_Tree *keys, DLRBT_Tree *blocks)
 {
 	Key *key= ob_get_key(ob);
 
@@ -508,12 +639,9 @@ void ob_to_keylist(bDopeSheet *ads, Object *ob, ListBase *keys, ListBase *blocks
 	}
 }
 
-
-void fcurve_to_keylist(AnimData *adt, FCurve *fcu, ListBase *keys, ListBase *blocks)
+void fcurve_to_keylist(AnimData *adt, FCurve *fcu, DLRBT_Tree *keys, DLRBT_Tree *blocks)
 {
 	BezTriple *bezt;
-	ActKeyColumn *ak, *ak2;
-	ActKeyBlock *ab, *ab2;
 	int v;
 	
 	if (fcu && fcu->totvert && fcu->bezt) {
@@ -525,51 +653,23 @@ void fcurve_to_keylist(AnimData *adt, FCurve *fcu, ListBase *keys, ListBase *blo
 		bezt= fcu->bezt;
 		
 		for (v=0; v < fcu->totvert; v++, bezt++) {
-			/* only if keyframe is in range (optimisation) */
-			add_bezt_to_keycolumnslist(keys, bezt);
-			if (blocks) add_bezt_to_keyblockslist(blocks, fcu, v);
+			add_bezt_to_keycolumns_list(keys, bezt);
+			if (blocks) add_bezt_to_keyblocks_list(blocks, fcu, v);
 		}
 		
 		/* update the number of curves that elements have appeared in  */
-		if (keys) {
-			for (ak=keys->first, ak2=keys->last; ak && ak2; ak=ak->next, ak2=ak2->prev) {
-				if (ak->modified) {
-					ak->modified = 0;
-					ak->totcurve += 1;
-				}
-				
-				if (ak == ak2)
-					break;
-				
-				if (ak2->modified) {
-					ak2->modified = 0;
-					ak2->totcurve += 1;
-				}
-			}
-		}
-		if (blocks) {
-			for (ab=blocks->first, ab2=blocks->last; ab && ab2; ab=ab->next, ab2=ab2->prev) {
-				if (ab->modified) {
-					ab->modified = 0;
-					ab->totcurve += 1;
-				}
-				
-				if (ab == ab2)
-					break;
-				
-				if (ab2->modified) {
-					ab2->modified = 0;
-					ab2->totcurve += 1;
-				}
-			}
-		}
+		// FIXME: this is broken with the new tree structure for now...
+		if (keys)
+			set_touched_actkeycolumn(keys->root);
+		if (blocks)
+			set_touched_actkeyblock(blocks->root);
 		
 		/* unapply NLA-mapping if applicable */
 		ANIM_nla_mapping_apply_fcurve(adt, fcu, 1, 1);
 	}
 }
 
-void agroup_to_keylist(AnimData *adt, bActionGroup *agrp, ListBase *keys, ListBase *blocks)
+void agroup_to_keylist(AnimData *adt, bActionGroup *agrp, DLRBT_Tree *keys, DLRBT_Tree *blocks)
 {
 	FCurve *fcu;
 
@@ -581,7 +681,7 @@ void agroup_to_keylist(AnimData *adt, bActionGroup *agrp, ListBase *keys, ListBa
 	}
 }
 
-void action_to_keylist(AnimData *adt, bAction *act, ListBase *keys, ListBase *blocks)
+void action_to_keylist(AnimData *adt, bAction *act, DLRBT_Tree *keys, DLRBT_Tree *blocks)
 {
 	FCurve *fcu;
 
@@ -594,7 +694,7 @@ void action_to_keylist(AnimData *adt, bAction *act, ListBase *keys, ListBase *bl
 }
 
 
-void gpl_to_keylist(bDopeSheet *ads, bGPDlayer *gpl, ListBase *keys, ListBase *blocks)
+void gpl_to_keylist(bDopeSheet *ads, bGPDlayer *gpl, DLRBT_Tree *keys, DLRBT_Tree *blocks)
 {
 	bGPDframe *gpf;
 	ActKeyColumn *ak;
@@ -603,7 +703,7 @@ void gpl_to_keylist(bDopeSheet *ads, bGPDlayer *gpl, ListBase *keys, ListBase *b
 		/* loop over frames, converting directly to 'keyframes' (should be in order too) */
 		for (gpf= gpl->frames.first; gpf; gpf= gpf->next) {
 			ak= MEM_callocN(sizeof(ActKeyColumn), "ActKeyColumn");
-			BLI_addtail(keys, ak);
+			BLI_addtail((ListBase *)keys, ak);
 			
 			ak->cfra= (float)gpf->framenum;
 			ak->modified = 1;
diff --git a/source/blender/editors/armature/poselib.c b/source/blender/editors/armature/poselib.c
index 93611a30bd8..d0a99e4ad13 100644
--- a/source/blender/editors/armature/poselib.c
+++ b/source/blender/editors/armature/poselib.c
@@ -37,6 +37,7 @@
 #include "BLI_arithb.h"
 #include "BLI_blenlib.h"
 #include "BLI_dynstr.h"
+#include "BLI_dlrbTree.h"
 
 #include "DNA_listBase.h"
 #include "DNA_anim_types.h"
@@ -216,7 +217,7 @@ bAction *poselib_validate (Object *ob)
 // TODO: operatorfy me!
 void poselib_validate_act (bAction *act)
 {
-	ListBase keys = {NULL, NULL};
+	DLRBT_Tree keys = {NULL, NULL};
 	ActKeyColumn *ak;
 	TimeMarker *marker, *markern;
 	
@@ -227,7 +228,9 @@ void poselib_validate_act (bAction *act)
 	}
 	
 	/* determine which frames have keys */
+	BLI_dlrbTree_init(&keys);
 	action_to_keylist(NULL, act, &keys, NULL);
+	BLI_dlrbTree_linkedlist_sync(&keys);
 	
 	/* for each key, make sure there is a correspnding pose */
 	for (ak= keys.first; ak; ak= ak->next) {
diff --git a/source/blender/editors/include/ED_keyframes_draw.h b/source/blender/editors/include/ED_keyframes_draw.h
index 63adcf39c12..e940aaed36e 100644
--- a/source/blender/editors/include/ED_keyframes_draw.h
+++ b/source/blender/editors/include/ED_keyframes_draw.h
@@ -17,12 +17,12 @@
  * 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) 2001-2002 by NaN Holding BV.
+ * The Original Code is Copyright (C) (C) 2009 Blender Foundation, Joshua Leung
  * All rights reserved.
  *
  * The Original Code is: all of this file.
  *
- * Contributor(s): none yet.
+ * Contributor(s): Joshua Leung (full recode)
  *
  * ***** END GPL LICENSE BLOCK *****
  */
@@ -41,13 +41,23 @@ struct ListBase;
 struct bGPDlayer;
 struct Scene;
 struct View2D;
+struct DLRBT_Tree;
 
 /* ****************************** Base Structs ****************************** */
 
 /* Keyframe Column Struct */
 typedef struct ActKeyColumn {
+		/* ListBase linkage */
 	struct ActKeyColumn *next, *prev;
-	short sel, handle_type;
+	
+		/* sorting-tree linkage */
+	struct ActKeyColumn *left, *right;	/* 'children' of this node, less than and greater than it (respectively) */
+	struct ActKeyColumn *parent;		/* parent of this node in the tree */
+	char tree_col;						/* DLRB_BLACK or DLRB_RED */
+	
+		/* keyframe info */
+	char sel;
+	short handle_type;
 	float cfra;
 	
 	/* only while drawing - used to determine if long-keyframe needs to be drawn */
@@ -57,8 +67,17 @@ typedef struct ActKeyColumn {
 
 /* 'Long Keyframe' Struct */
 typedef struct ActKeyBlock {
+		/* ListBase linkage */
 	struct ActKeyBlock *next, *prev;
-	short sel, handle_type;
+	
+		/* sorting-tree linkage */
+	struct ActKeyBlock *left, *right;	/* 'children' of this node, less than and greater than it (respectively) */
+	struct ActKeyBlock *parent;			/* parent of this node in the tree */
+	char tree_col;						/* DLRB_BLACK or DLRB_RED */
+	
+		/* key-block info */
+	char sel;
+	short handle_type;
 	float val;
 	float start, end;
 	
@@ -67,7 +86,6 @@ typedef struct ActKeyBlock {
 	short totcurve; 
 } ActKeyBlock;
 
-
 /* *********************** Keyframe Drawing ****************************** */
 
 /* options for keyframe shape drawing */
@@ -94,12 +112,12 @@ void draw_scene_channel(struct View2D *v2d, struct bDopeSheet *ads, struct Scene
 void draw_gpl_channel(struct View2D *v2d, struct bDopeSheet *ads, struct bGPDlayer *gpl, float ypos);
 
 /* Keydata Generation */
-void fcurve_to_keylist(struct AnimData *adt, struct FCurve *fcu, ListBase *keys, ListBase *blocks);
-void agroup_to_keylist(struct AnimData *adt, struct bActionGroup *agrp, ListBase *keys, ListBase *blocks);
-void action_to_keylist(struct AnimData *adt, struct bAction *act, ListBase *keys, ListBase *blocks);
-void ob_to_keylist(struct bDopeSheet *ads, struct Object *ob, ListBase *keys, ListBase *blocks);
-void scene_to_keylist(struct bDopeSheet *ads, struct Scene *sce, ListBase *keys, ListBase *blocks);
-void gpl_to_keylist(struct bDopeSheet *ads, struct bGPDlayer *gpl, ListBase *keys, ListBase *blocks);
+void fcurve_to_keylist(struct AnimData *adt, struct FCurve *fcu, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks);
+void agroup_to_keylist(struct AnimData *adt, struct bActionGroup *agrp, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks);
+void action_to_keylist(struct AnimData *adt, struct bAction *act, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks);
+void ob_to_keylist(struct bDopeSheet *ads, struct Object *ob, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks);
+void scene_to_keylist(struct bDopeSheet *ads, struct Scene *sce, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks);
+void gpl_to_keylist(struct bDopeSheet *ads, struct bGPDlayer *gpl, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks);
 
 #endif  /*  ED_KEYFRAMES_DRAW_H */
 
diff --git a/source/blender/editors/space_action/action_ops.c b/source/blender/editors/space_action/action_ops.c
index d1c9e1deac3..c4dbe92985a 100644
--- a/source/blender/editors/space_action/action_ops.c
+++ b/source/blender/editors/space_action/action_ops.c
@@ -32,6 +32,7 @@
 #include "MEM_guardedalloc.h"
 
 #include "DNA_listBase.h"
+#include "DNA_anim_types.h"
 #include "DNA_action_types.h"
 #include "DNA_scene_types.h"
 #include "DNA_screen_types.h"
@@ -57,6 +58,70 @@
 #include "WM_types.h"
 
 
+/* ------------- */
+
+#include "BLI_dlrbTree.h"
+#include "ED_anim_api.h"
+#include "ED_keyframes_draw.h"
+#include "DNA_object_types.h"
+
+static int act_drawtree_test_exec (bContext *C, wmOperator *op)
+{
+	bAnimContext ac;
+	bDopeSheet *ads;
+	ListBase anim_data = {NULL, NULL};
+	bAnimListElem *ale;
+	int filter, items;
+	
+	ANIM_animdata_get_context(C, &ac);
+	ads= ac.data;
+	
+	/* build list of channels to draw */
+	filter= (ANIMFILTER_VISIBLE|ANIMFILTER_CHANNELS);
+	items= ANIM_animdata_filter(&ac, &anim_data, filter, ac.data, ac.datatype);
+	
+	if (items) {
+		for (ale= anim_data.first; ale; ale= ale->next) {
+			AnimData *adt= BKE_animdata_from_id(ale->id);
+			
+			
+			if (ale->type == ANIMTYPE_GROUP) {
+				DLRBT_Tree keys;
+				ActKeyColumn *ak;
+				
+				BLI_dlrbTree_init(&keys);
+				
+					agroup_to_keylist(adt, ale->data, &keys, NULL);
+				
+				BLI_dlrbTree_linkedlist_sync(&keys);
+				
+					printf("printing sorted list of object keyframes --------------- \n");
+					for (ak= keys.first; ak; ak= ak->next) {
+						printf("\t%p (%f) | L:%p R:%p P:%p \n", ak, ak->cfra, ak->left, ak->right, ak->parent);
+					}	
+
+					printf("printing tree ---------------- \n");
+					for (ak= keys.root; ak; ak= ak->next) {
+						printf("\t%p (%f) | L:%p R:%p P:%p \n", ak, ak->cfra, ak->left, ak->right, ak->parent);
+					}
+				
+				BLI_dlrbTree_free(&keys);
+				
+				break;
+			}
+		}
+		
+		BLI_freelistN(&anim_data);
+	}
+}
+
+void ACT_OT_test (wmOperatorType *ot)
+{
+	ot->idname= "ACT_OT_test";
+	
+	ot->exec= act_drawtree_test_exec;
+}
+
 /* ************************** registration - operator types **********************************/
 
 void action_operatortypes(void)
@@ -85,6 +150,9 @@ void action_operatortypes(void)
 	
 	WM_operatortype_append(ACT_OT_previewrange_set);
 	WM_operatortype_append(ACT_OT_view_all);
+	
+	// test
+	WM_operatortype_append(ACT_OT_test);
 }
 
 /* ************************** registration - keymaps **********************************/
@@ -154,6 +222,9 @@ static void action_keymap_keyframes (wmWindowManager *wm, ListBase *keymap)
 	
 	/* transform system */
 	transform_keymap_for_space(wm, keymap, SPACE_ACTION);
+	
+		/* test */
+	WM_keymap_add_item(keymap, "ACT_OT_test", QKEY, KM_PRESS, 0, 0);
 }
 
 /* --------------- */
diff --git a/source/blender/editors/space_action/action_select.c b/source/blender/editors/space_action/action_select.c
index ef1b392815d..e358f559b14 100644
--- a/source/blender/editors/space_action/action_select.c
+++ b/source/blender/editors/space_action/action_select.c
@@ -37,6 +37,7 @@
 
 #include "BLI_blenlib.h"
 #include "BLI_arithb.h"
+#include "BLI_dlrbTree.h"
 
 #include "DNA_anim_types.h"
 #include "DNA_action_types.h"
@@ -224,7 +225,6 @@ static void borderselect_action (bAnimContext *ac, rcti rect, short mode, short
 	BeztEditFunc ok_cb, select_cb;
 	View2D *v2d= &ac->ar->v2d;
 	rctf rectf;
-	//float ymin=0, ymax=(float)(-ACHANNEL_HEIGHT);
 	float ymin=0, ymax=(float)(-ACHANNEL_HEIGHT_HALF);
 	
 	/* convert mouse coordinates to frame ranges and channel coordinates corrected for view pan/zoom */
@@ -745,7 +745,7 @@ static void actkeys_mselect_column(bAnimContext *ac, short select_mode, float se
 static void mouse_action_keys (bAnimContext *ac, int mval[2], short select_mode, short column)
 {
 	ListBase anim_data = {NULL, NULL};
-	ListBase anim_keys = {NULL, NULL};
+	DLRBT_Tree anim_keys;
 	bAnimListElem *ale;
 	int filter;
 	
@@ -784,10 +784,12 @@ static void mouse_action_keys (bAnimContext *ac, int mval[2], short select_mode,
 	else {
 		/* found match - must return here... */
 		AnimData *adt= ANIM_nla_mapping_get(ac, ale);
-		ActKeyColumn *ak;
+		ActKeyColumn *ak, *akn=NULL;
 		
 		/* make list of keyframes */
 		// TODO: it would be great if we didn't have to apply this to all the keyframes to do this...
+		BLI_dlrbTree_init(&anim_keys);
+		
 		if (ale->key_data) {
 			switch (ale->datatype) {
 				case ALE_OB:
@@ -825,8 +827,11 @@ static void mouse_action_keys (bAnimContext *ac, int mval[2], short select_mode,
 			gpl_to_keylist(ads, gpl, &anim_keys, NULL);
 		}
 		
-		/* loop through keyframes, finding one that was clicked on */
-		for (ak= anim_keys.first; ak; ak= ak->next) {
+		// the call below is not strictly necessary, since we have adjacency info anyway
+		//BLI_dlrbTree_linkedlist_sync(&anim_keys);
+		
+		/* loop through keyframes, finding one that was within the range clicked on */
+		for (ak= anim_keys.root; ak; ak= akn) {
 			if (IN_RANGE(ak->cfra, rectf.xmin, rectf.xmax)) {
 				/* set the frame to use, and apply inverse-correction for NLA-mapping 
 				 * so that the frame will get selected by the selection functiosn without
@@ -836,14 +841,17 @@ static void mouse_action_keys (bAnimContext *ac, int mval[2], short select_mode,
 				found= 1;
 				break;
 			}
+			else if (ak->cfra < rectf.xmin)
+				akn= ak->right;
+			else
+				akn= ak->left;
 		}
 		
 		/* remove active channel from list of channels for separate treatment (since it's needed later on) */
 		BLI_remlink(&anim_data, ale);
 		
 		/* cleanup temporary lists */
-		BLI_freelistN(&anim_keys);
-		anim_keys.first = anim_keys.last = NULL;
+		BLI_dlrbTree_free(&anim_keys);
 		
 		/* free list of channels, since it's not used anymore */
 		BLI_freelistN(&anim_data);
diff --git a/source/blender/editors/space_nla/nla_draw.c b/source/blender/editors/space_nla/nla_draw.c
index 8d56670a149..9e60651081f 100644
--- a/source/blender/editors/space_nla/nla_draw.c
+++ b/source/blender/editors/space_nla/nla_draw.c
@@ -56,6 +56,7 @@
 #include "BLI_blenlib.h"
 #include "BLI_arithb.h"
 #include "BLI_rand.h"
+#include "BLI_dlrbTree.h"
 
 #include "BKE_animsys.h"
 #include "BKE_fcurve.h"
@@ -127,13 +128,15 @@ static void nla_action_get_color (AnimData *adt, bAction *act, float color[4])
 /* draw the keyframes in the specified Action */
 static void nla_action_draw_keyframes (AnimData *adt, bAction *act, View2D *v2d, float y, float ymin, float ymax)
 {
-	ListBase keys = {NULL, NULL};
+	DLRBT_Tree keys;
 	ActKeyColumn *ak;
 	float xscale, f1, f2;
 	float color[4];
 	
 	/* get a list of the keyframes with NLA-scaling applied */
+	BLI_dlrbTree_init(&keys);
 	action_to_keylist(adt, act, &keys, NULL);
+	BLI_dlrbTree_linkedlist_sync(&keys);
 	
 	if ELEM(NULL, act, keys.first)
 		return;
@@ -165,7 +168,7 @@ static void nla_action_draw_keyframes (AnimData *adt, bAction *act, View2D *v2d,
 		draw_keyframe_shape(ak->cfra, y, xscale, 3.0f, 0, KEYFRAME_SHAPE_FRAME);
 	
 	/* free icons */
-	BLI_freelistN(&keys);
+	BLI_dlrbTree_free(&keys);
 }
 
 /* Strips (Proper) ---------------------- */
diff --git a/source/blender/editors/space_view3d/drawarmature.c b/source/blender/editors/space_view3d/drawarmature.c
index ec3b716e616..b698b404825 100644
--- a/source/blender/editors/space_view3d/drawarmature.c
+++ b/source/blender/editors/space_view3d/drawarmature.c
@@ -52,6 +52,7 @@
 
 #include "BLI_blenlib.h"
 #include "BLI_arithb.h"
+#include "BLI_dlrbTree.h"
 
 #include "BKE_animsys.h"
 #include "BKE_action.h"
@@ -2026,7 +2027,7 @@ static void draw_pose_paths(Scene *scene, View3D *v3d, RegionView3D *rv3d, Objec
 	bArmature *arm= ob->data;
 	bPoseChannel *pchan;
 	ActKeyColumn *ak;
-	ListBase keys;
+	DLRBT_Tree keys;
 	float *fp, *fp_start;
 	int a, stepsize;
 	int sfra, efra, len;
@@ -2168,12 +2169,14 @@ static void draw_pose_paths(Scene *scene, View3D *v3d, RegionView3D *rv3d, Objec
 				/* Keyframes - dots and numbers */
 				if (arm->pathflag & ARM_PATH_KFRAS) {
 					/* build list of all keyframes in active action for pchan */
-					keys.first = keys.last = NULL;	
+					BLI_dlrbTree_init(&keys);
 					
 					if (adt) {
 						bActionGroup *agrp= action_groups_find_named(adt->action, pchan->name);
-						if (agrp)
+						if (agrp) {
 							agroup_to_keylist(adt, agrp, &keys, NULL);
+							BLI_dlrbTree_linkedlist_sync(&keys);
+						}
 					}
 					
 					/* Draw slightly-larger yellow dots at each keyframe */
@@ -2205,7 +2208,7 @@ static void draw_pose_paths(Scene *scene, View3D *v3d, RegionView3D *rv3d, Objec
 						}
 					}
 					
-					BLI_freelistN(&keys);
+					BLI_dlrbTree_free(&keys);
 				}
 			}
 		}
@@ -2319,7 +2322,7 @@ static void draw_ghost_poses_keys(Scene *scene, View3D *v3d, RegionView3D *rv3d,
 	bAction *act= (adt) ? adt->action : NULL;
 	bArmature *arm= ob->data;
 	bPose *posen, *poseo;
-	ListBase keys= {NULL, NULL};
+	DLRBT_Tree keys;
 	ActKeyColumn *ak, *akn;
 	float start, end, range, colfac, i;
 	int cfrao, flago;
@@ -2330,13 +2333,16 @@ static void draw_ghost_poses_keys(Scene *scene, View3D *v3d, RegionView3D *rv3d,
 		return;
 	
 	/* get keyframes - then clip to only within range */
+	BLI_dlrbTree_init(&keys);
 	action_to_keylist(adt, act, &keys, NULL);
+	BLI_dlrbTree_linkedlist_sync(&keys);
+	
 	range= 0;
 	for (ak= keys.first; ak; ak= akn) {
 		akn= ak->next;
 		
 		if ((ak->cfra < start) || (ak->cfra > end))
-			BLI_freelinkN(&keys, ak);
+			BLI_freelinkN((ListBase *)&keys, ak);
 		else
 			range++;
 	}
@@ -2374,7 +2380,7 @@ static void draw_ghost_poses_keys(Scene *scene, View3D *v3d, RegionView3D *rv3d,
 	if (v3d->zbuf) glEnable(GL_DEPTH_TEST);
 
 	ghost_poses_tag_unselected(ob, 1);		/* unhide unselected bones if need be */
-	BLI_freelistN(&keys);
+	BLI_dlrbTree_free(&keys);
 	free_pose(posen);
 	
 	/* restore */