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.

7 files changed, 412 insertions, 203 deletions

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 */