Dope Sheet: rewrite computation of keyframe hold blocks.

Computation of hold blocks was done by storing ranges (with start and
an end, and likely overlapping) in a tree keyed only by the block start.
This cannot work well, and there even were comments that it is not
reliable in complex cases.

A much better way to deal with it is to split all ranges so they don't
overlap. The most thorough way of doing this is to split at all and every
known keyframe, and in this case the data can actually be stored in the
key column data structures, avoiding the need for a second tree.

In practice, splitting requires a pass to copy this data to newly added
keys, and the necessity to loop over all keyframes in the range being
added. Both are linear and don't add excess algorithmic complexity.

The new implementation also calls BLI_dlrbTree_linkedlist_sync for
its own needs, so the users of the *_to_keylist functions don't have
to do it themselves anymore.

Differential Revision: https://developer.blender.org/D3790

9 files changed, 244 insertions, 380 deletions

diff --git a/source/blender/blenkernel/intern/anim.c b/source/blender/blenkernel/intern/anim.c
index 1d38f8a8c71..d70f3459324 100644
--- a/source/blender/blenkernel/intern/anim.c
+++ b/source/blender/blenkernel/intern/anim.c
@@ -65,8 +65,8 @@
 
 // XXX bad level call...
 extern short compare_ak_cfraPtr(void *node, void *data);
-extern void agroup_to_keylist(struct AnimData *adt, struct bActionGroup *agrp, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks);
-extern void action_to_keylist(struct AnimData *adt, struct bAction *act, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks);
+extern void agroup_to_keylist(struct AnimData *adt, struct bActionGroup *agrp, struct DLRBT_Tree *keys);
+extern void action_to_keylist(struct AnimData *adt, struct bAction *act, struct DLRBT_Tree *keys);
 
 /* --------------------- */
 /* forward declarations */
@@ -485,13 +485,11 @@ void animviz_calc_motionpaths(Depsgraph *depsgraph,
 				bActionGroup *agrp = BKE_action_group_find_name(adt->action, mpt->pchan->name);
 
 				if (agrp) {
-					agroup_to_keylist(adt, agrp, &mpt->keys, NULL);
-					BLI_dlrbTree_linkedlist_sync(&mpt->keys);
+					agroup_to_keylist(adt, agrp, &mpt->keys);
 				}
 			}
 			else {
-				action_to_keylist(adt, adt->action, &mpt->keys, NULL);
-				BLI_dlrbTree_linkedlist_sync(&mpt->keys);
+				action_to_keylist(adt, adt->action, &mpt->keys);
 			}
 		}
 	}
diff --git a/source/blender/editors/animation/anim_draw.c b/source/blender/editors/animation/anim_draw.c
index 0ab6cdb3526..48dd310e2b4 100644
--- a/source/blender/editors/animation/anim_draw.c
+++ b/source/blender/editors/animation/anim_draw.c
@@ -551,11 +551,11 @@ static bool find_prev_next_keyframes(struct bContext *C, int *nextfra, int *prev
 	}
 
 	/* populate tree with keyframe nodes */
-	scene_to_keylist(&ads, scene, &keys, NULL);
+	scene_to_keylist(&ads, scene, &keys);
 	gpencil_to_keylist(&ads, scene->gpd, &keys, false);
 
 	if (ob) {
-		ob_to_keylist(&ads, ob, &keys, NULL);
+		ob_to_keylist(&ads, ob, &keys);
 		gpencil_to_keylist(&ads, ob->data, &keys, false);
 	}
 
@@ -564,9 +564,6 @@ static bool find_prev_next_keyframes(struct bContext *C, int *nextfra, int *prev
 		mask_to_keylist(&ads, masklay, &keys);
 	}
 
-	/* build linked-list for searching */
-	BLI_dlrbTree_linkedlist_sync(&keys);
-
 	/* find matching keyframe in the right direction */
 	do {
 		aknext = (ActKeyColumn *)BLI_dlrbTree_search_next(&keys, compare_ak_cfraPtr, &cfranext);
diff --git a/source/blender/editors/animation/keyframes_draw.c b/source/blender/editors/animation/keyframes_draw.c
index e6245fffe47..451915aff6d 100644
--- a/source/blender/editors/animation/keyframes_draw.c
+++ b/source/blender/editors/animation/keyframes_draw.c
@@ -113,8 +113,8 @@ static DLRBT_Node *nalloc_ak_bezt(void *data)
 	ak->sel = BEZT_ISSEL_ANY(bezt) ? SELECT : 0;
 	ak->key_type = BEZKEYTYPE(bezt);
 
-	/* set 'modified', since this is used to identify long keyframes */
-	ak->modified = 1;
+	/* count keyframes in this column */
+	ak->totkey = 1;
 
 	return (DLRBT_Node *)ak;
 }
@@ -127,7 +127,9 @@ static void nupdate_ak_bezt(void *node, void *data)
 
 	/* set selection status and 'touched' status */
 	if (BEZT_ISSEL_ANY(bezt)) ak->sel = SELECT;
-	ak->modified += 1;
+
+	/* count keyframes in this column */
+	ak->totkey++;
 
 	/* for keyframe type, 'proper' keyframes have priority over breakdowns (and other types for now) */
 	if (BEZKEYTYPE(bezt) == BEZT_KEYTYPE_KEYFRAME)
@@ -161,8 +163,8 @@ static DLRBT_Node *nalloc_ak_gpframe(void *data)
 	ak->sel = (gpf->flag & GP_FRAME_SELECT) ? SELECT : 0;
 	ak->key_type = gpf->key_type;
 
-	/* set 'modified', since this is used to identify long keyframes */
-	ak->modified = 1;
+	/* count keyframes in this column */
+	ak->totkey = 1;
 
 	return (DLRBT_Node *)ak;
 }
@@ -175,7 +177,9 @@ static void nupdate_ak_gpframe(void *node, void *data)
 
 	/* set selection status and 'touched' status */
 	if (gpf->flag & GP_FRAME_SELECT) ak->sel = SELECT;
-	ak->modified += 1;
+
+	/* count keyframes in this column */
+	ak->totkey++;
 
 	/* for keyframe type, 'proper' keyframes have priority over breakdowns (and other types for now) */
 	if (gpf->key_type == BEZT_KEYTYPE_KEYFRAME)
@@ -208,8 +212,8 @@ static DLRBT_Node *nalloc_ak_masklayshape(void *data)
 	ak->cfra = masklay_shape->frame;
 	ak->sel = (masklay_shape->flag & MASK_SHAPE_SELECT) ? SELECT : 0;
 
-	/* set 'modified', since this is used to identify long keyframes */
-	ak->modified = 1;
+	/* count keyframes in this column */
+	ak->totkey = 1;
 
 	return (DLRBT_Node *)ak;
 }
@@ -222,7 +226,9 @@ static void nupdate_ak_masklayshape(void *node, void *data)
 
 	/* set selection status and 'touched' status */
 	if (masklay_shape->flag & MASK_SHAPE_SELECT) ak->sel = SELECT;
-	ak->modified += 1;
+
+	/* count keyframes in this column */
+	ak->totkey++;
 }
 
 
@@ -257,64 +263,11 @@ static void add_masklay_to_keycolumns_list(DLRBT_Tree *keys, MaskLayerShape *mas
 
 /* ActKeyBlocks (Long Keyframes) ------------------------------------------ */
 
-/* Comparator callback used for ActKeyBlock and cframe float-value pointer */
-/* NOTE: this is exported to other modules that use the ActKeyBlocks for finding long-keyframes */
-short compare_ab_cfraPtr(void *node, void *data)
-{
-	ActKeyBlock *ab = (ActKeyBlock *)node;
-	const float *cframe = data;
-	float val = *cframe;
-
-	if (val < ab->start)
-		return -1;
-	else if (val > ab->start)
-		return 1;
-	else
-		return 0;
-}
-
-/* --------------- */
+static const ActKeyBlockInfo dummy_keyblock = { 0 };
 
-/* Create a ActKeyColumn for a pair of BezTriples */
-static ActKeyBlock *bezts_to_new_actkeyblock(BezTriple *prev, BezTriple *beztn)
+static void compute_keyblock_data(ActKeyBlockInfo *info, BezTriple *prev, BezTriple *beztn)
 {
-	ActKeyBlock *ab = MEM_callocN(sizeof(ActKeyBlock), "ActKeyBlock");
-
-	ab->start = prev->vec[1][0];
-	ab->end = beztn->vec[1][0];
-	ab->val = beztn->vec[1][1];
-
-	ab->sel = (BEZT_ISSEL_ANY(prev) || BEZT_ISSEL_ANY(beztn)) ? SELECT : 0;
-	ab->modified = 1;
-
-	if (BEZKEYTYPE(beztn) == BEZT_KEYTYPE_MOVEHOLD)
-		ab->flag |= ACTKEYBLOCK_FLAG_MOVING_HOLD;
-
-	return ab;
-}
-
-static void add_bezt_to_keyblocks_list(DLRBT_Tree *blocks, BezTriple *first_bezt, BezTriple *beztn)
-{
-	ActKeyBlock *new_ab = NULL;
-	BezTriple *prev = NULL;
-
-	/* get the BezTriple immediately before the given one which has the same value */
-	if (beztn != first_bezt) {
-		/* XXX: Unless I'm overlooking some details from the past, this should be sufficient?
-		 *      The old code did some elaborate stuff trying to find keyframe columns for
-		 *      the given BezTriple, then step backwards to the column before that, and find
-		 *      an appropriate BezTriple with matching values there. Maybe that was warranted
-		 *      in the past, but now, that list is only ever filled with keyframes from the
-		 *      current FCurve.
-		 *
-		 *      -- Aligorith (20140415)
-		 */
-		prev = beztn - 1;
-	}
-
-
-	/* check if block needed */
-	if (prev == NULL) return;
+	memset(info, 0, sizeof (ActKeyBlockInfo));
 
 	if (BEZKEYTYPE(beztn) == BEZT_KEYTYPE_MOVEHOLD) {
 		/* Animator tagged a "moving hold"
@@ -322,153 +275,136 @@ static void add_bezt_to_keyblocks_list(DLRBT_Tree *blocks, BezTriple *first_bezt
 		 *     we're just dealing with the first of a pair, and we don't
 		 *     want to be creating any phantom holds...
 		 */
-		if (BEZKEYTYPE(prev) != BEZT_KEYTYPE_MOVEHOLD)
-			return;
+		if (BEZKEYTYPE(prev) == BEZT_KEYTYPE_MOVEHOLD) {
+			info->flag |= ACTKEYBLOCK_FLAG_MOVING_HOLD | ACTKEYBLOCK_FLAG_ANY_HOLD;
+		}
 	}
-	else {
-		/* Check for same values...
-		 *  - Handles must have same central value as each other
-		 *  - Handles which control that section of the curve must be constant
-		 */
-		if (IS_EQF(beztn->vec[1][1], prev->vec[1][1]) == 0) return;
+
+	/* Check for same values...
+	 *  - Handles must have same central value as each other
+	 *  - Handles which control that section of the curve must be constant
+	 */
+	if (IS_EQF(beztn->vec[1][1], prev->vec[1][1])) {
+		bool hold;
 
 		/* Only check handles in case of actual bezier interpolation. */
 		if (prev->ipo == BEZT_IPO_BEZ) {
-			if (IS_EQF(beztn->vec[1][1], beztn->vec[0][1]) == 0) return;
-			if (IS_EQF(prev->vec[1][1], prev->vec[2][1]) == 0) return;
+			hold = IS_EQF(beztn->vec[1][1], beztn->vec[0][1]) && IS_EQF(prev->vec[1][1], prev->vec[2][1]);
 		}
 		/* This interpolation type induces movement even between identical keys. */
-		else if (ELEM(prev->ipo, BEZT_IPO_ELASTIC)) {
-			return;
+		else {
+			hold = !ELEM(prev->ipo, BEZT_IPO_ELASTIC);
+		}
+
+		if (hold) {
+			info->flag |= ACTKEYBLOCK_FLAG_STATIC_HOLD | ACTKEYBLOCK_FLAG_ANY_HOLD;
 		}
 	}
 
-	/* 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;
+	info->sel = BEZT_ISSEL_ANY(prev) || BEZT_ISSEL_ANY(beztn);
+}
+
+static void add_keyblock_info(ActKeyColumn *col, const ActKeyBlockInfo *block)
+{
+	/* New curve and block. */
+	if (col->totcurve <= 1 && col->totblock == 0) {
+		memcpy(&col->block, block, sizeof(ActKeyBlockInfo));
 	}
+	/* Existing curve. */
 	else {
-		ActKeyBlock *ab, *abn = NULL;
+		col->block.conflict |= (col->block.flag ^ block->flag);
+		col->block.flag |= block->flag;
+		col->block.sel |= block->sel;
+	}
 
-		/* try to find a keyblock that starts on the previous beztriple, and add a new one if none start there
-		 * Note: we perform a tree traversal here NOT a standard linked-list traversal...
-		 * Note: we can't search from end to try to optimize 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; ab = abn) {
-			/* check if this is a match, or whether we go left or right
-			 * NOTE: we now use a float threshold to prevent precision errors causing problems with summaries
-			 */
-			if (IS_EQT(ab->start, prev->vec[1][0], BEZT_BINARYSEARCH_THRESH)) {
-				/* set selection status and 'touched' status */
-				if (BEZT_ISSEL_ANY(beztn))
-					ab->sel = SELECT;
+	if (block->flag) {
+		col->totblock++;
+	}
+}
 
-				/* XXX: only when the first one was a moving hold? */
-				if (BEZKEYTYPE(beztn) == BEZT_KEYTYPE_MOVEHOLD)
-					ab->flag |= ACTKEYBLOCK_FLAG_MOVING_HOLD;
+static void add_bezt_to_keyblocks_list(DLRBT_Tree *keys, BezTriple *bezt, int num_bezt)
+{
+	ActKeyColumn *col = keys->first;
 
-				ab->modified++;
+	if (bezt && num_bezt >= 2) {
+		ActKeyBlockInfo block;
 
-				/* done... no need to insert */
-				return;
-			}
-			else {
-				ActKeyBlock **abnp = NULL; /* branch to go down - used to hook new blocks to parents */
-
-				/* 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;
+		/* Find the first key column while inserting dummy blocks. */
+		for (; col != NULL && col->cfra < bezt[0].vec[1][0]; col = col->next) {
+			add_keyblock_info(col, &dummy_keyblock);
+		}
+
+		BLI_assert(col != NULL);
+
+		/* Insert real blocks. */
+		for (int v = 1; col != NULL && v < num_bezt; v++, bezt++) {
+			BLI_assert(col->cfra == bezt[0].vec[1][0]);
+
+			compute_keyblock_data(&block, bezt, bezt + 1);
+
+			for (; col != NULL && col->cfra < bezt[1].vec[1][0]; col = col->next) {
+				add_keyblock_info(col, &block);
 			}
+
+			BLI_assert(col != NULL);
 		}
 	}
 
-	/* now, balance the tree taking into account this newly added node */
-	BLI_dlrbTree_insert(blocks, (DLRBT_Node *)new_ab);
+	/* Insert dummy blocks at the end. */
+	for (; col != NULL; col = col->next) {
+		add_keyblock_info(col, &dummy_keyblock);
+	}
 }
 
-/* --------- */
-
-/* Handle the 'touched' status of ActKeyColumn tree nodes */
-static void set_touched_actkeycolumn(ActKeyColumn *ak)
+/* Walk through columns and propagate blocks and totcurve.
+ *
+ * This must be called even by animation sources that don't generate
+ * keyblocks to keep the data structure consistent after adding columns.
+ */
+static void update_keyblocks(DLRBT_Tree *keys, BezTriple *bezt, int num_bezt)
 {
-	/* sanity check */
-	if (ak == NULL)
-		return;
+	/* Recompute the prev/next linked list. */
+	BLI_dlrbTree_linkedlist_sync(keys);
+
+	/* Find the curve count */
+	int max_curve = 0;
 
-	/* deal with self first */
-	if (ak->modified) {
-		ak->modified = 0;
-		ak->totcurve++;
+	for (ActKeyColumn *col = keys->first; col; col = col->next) {
+		max_curve = MAX2(max_curve, col->totcurve);
 	}
 
-	/* children */
-	set_touched_actkeycolumn(ak->left);
-	set_touched_actkeycolumn(ak->right);
-}
+	/* Propagate blocks to inserted keys */
+	ActKeyColumn *prev_ready = NULL;
 
-/* Handle the 'touched' status of ActKeyBlock tree nodes */
-static void set_touched_actkeyblock(ActKeyBlock *ab)
-{
-	/* sanity check */
-	if (ab == NULL)
-		return;
+	for (ActKeyColumn *col = keys->first; col; col = col->next) {
+		/* Pre-existing column. */
+		if (col->totcurve > 0) {
+			prev_ready = col;
+		}
+		/* Newly inserted column, so copy block data from previous. */
+		else if (prev_ready != NULL) {
+			col->totblock = prev_ready->totblock;
+			memcpy(&col->block, &prev_ready->block, sizeof(ActKeyBlockInfo));
+		}
 
-	/* deal with self first */
-	if (ab->modified) {
-		ab->modified = 0;
-		ab->totcurve++;
+		col->totcurve = max_curve + 1;
 	}
 
-	/* children */
-	set_touched_actkeyblock(ab->left);
-	set_touched_actkeyblock(ab->right);
+	/* Add blocks on top */
+	add_bezt_to_keyblocks_list(keys, bezt, num_bezt);
 }
 
 /* --------- */
 
 /* Checks if ActKeyBlock should exist... */
-bool actkeyblock_is_valid(ActKeyBlock *ab, DLRBT_Tree *keys)
+int actkeyblock_get_valid_hold(ActKeyColumn *ac)
 {
-	ActKeyColumn *ak;
-	short startCurves, endCurves, totCurves;
-
 	/* check that block is valid */
-	if (ab == NULL)
-		return 0;
-
-	/* find out how many curves occur at each keyframe */
-	ak = (ActKeyColumn *)BLI_dlrbTree_search_exact(keys, compare_ak_cfraPtr, &ab->start);
-	startCurves = (ak) ? ak->totcurve : 0;
-
-	ak = (ActKeyColumn *)BLI_dlrbTree_search_exact(keys, compare_ak_cfraPtr, &ab->end);
-	endCurves = (ak) ? ak->totcurve : 0;
-
-	/* only draw keyblock if it appears in at all of the keyframes at lowest end */
-	if (!startCurves && !endCurves)
+	if (ac == NULL || ac->next == NULL || ac->totblock == 0)
 		return 0;
 
-	totCurves = (startCurves > endCurves) ? endCurves : startCurves;
-	return (ab->totcurve >= totCurves);
+	const int hold_mask = (ACTKEYBLOCK_FLAG_ANY_HOLD | ACTKEYBLOCK_FLAG_STATIC_HOLD | ACTKEYBLOCK_FLAG_ANY_HOLD);
+	return (ac->block.flag & ~ac->block.conflict) & hold_mask;
 }
 
 /* *************************** Keyframe Drawing *************************** */
@@ -565,10 +501,11 @@ void draw_keyframe_shape(float x, float y, float size, bool sel, short key_type,
 	immVertex2f(pos_id, x, y);
 }
 
-static void draw_keylist(View2D *v2d, DLRBT_Tree *keys, DLRBT_Tree *blocks, float ypos, float yscale_fac, bool channelLocked)
+static void draw_keylist(View2D *v2d, DLRBT_Tree *keys, float ypos, float yscale_fac, bool channelLocked)
 {
 	const float icon_sz = U.widget_unit * 0.5f * yscale_fac;
 	const float half_icon_sz = 0.5f * icon_sz;
+	const float smaller_sz = 0.35f * icon_sz;
 
 	GPU_blend(true);
 
@@ -577,7 +514,7 @@ static void draw_keylist(View2D *v2d, DLRBT_Tree *keys, DLRBT_Tree *blocks, floa
 	float alpha = channelLocked ? 0.25f : 1.0f;
 
 	/* draw keyblocks */
-	if (blocks) {
+	if (keys) {
 		float sel_color[4], unsel_color[4];
 		float sel_mhcol[4], unsel_mhcol[4];
 
@@ -594,8 +531,8 @@ static void draw_keylist(View2D *v2d, DLRBT_Tree *keys, DLRBT_Tree *blocks, floa
 		unsel_mhcol[3] *= 0.8f;
 
 		uint block_len = 0;
-		for (ActKeyBlock *ab = blocks->first; ab; ab = ab->next) {
-			if (actkeyblock_is_valid(ab, keys)) {
+		for (ActKeyColumn *ab = keys->first; ab; ab = ab->next) {
+			if (actkeyblock_get_valid_hold(ab)) {
 				block_len++;
 			}
 		}
@@ -607,19 +544,20 @@ static void draw_keylist(View2D *v2d, DLRBT_Tree *keys, DLRBT_Tree *blocks, floa
 			immBindBuiltinProgram(GPU_SHADER_2D_FLAT_COLOR);
 
 			immBegin(GPU_PRIM_TRIS, 6 * block_len);
-			for (ActKeyBlock *ab = blocks->first; ab; ab = ab->next) {
-				if (actkeyblock_is_valid(ab, keys)) {
-					if (ab->flag & ACTKEYBLOCK_FLAG_MOVING_HOLD) {
+			for (ActKeyColumn *ab = keys->first; ab; ab = ab->next) {
+				int valid_hold = actkeyblock_get_valid_hold(ab);
+				if (valid_hold != 0) {
+					if ((valid_hold & ACTKEYBLOCK_FLAG_STATIC_HOLD) == 0) {
 						/* draw "moving hold" long-keyframe block - slightly smaller */
 						immRectf_fast_with_color(pos_id, color_id,
-						                         ab->start, ypos - half_icon_sz, ab->end, ypos + half_icon_sz,
-						                         (ab->sel) ? sel_mhcol : unsel_mhcol);
+						                         ab->cfra, ypos - smaller_sz, ab->next->cfra, ypos + smaller_sz,
+						                         (ab->block.sel) ? sel_mhcol : unsel_mhcol);
 					}
 					else {
 						/* draw standard long-keyframe block */
 						immRectf_fast_with_color(pos_id, color_id,
-						                         ab->start, ypos - half_icon_sz, ab->end, ypos + half_icon_sz,
-						                         (ab->sel) ? sel_color : unsel_color);
+						                         ab->cfra, ypos - half_icon_sz, ab->next->cfra, ypos + half_icon_sz,
+						                         (ab->block.sel) ? sel_color : unsel_color);
 					}
 				}
 			}
@@ -670,119 +608,89 @@ static void draw_keylist(View2D *v2d, DLRBT_Tree *keys, DLRBT_Tree *blocks, floa
 
 void draw_summary_channel(View2D *v2d, bAnimContext *ac, float ypos, float yscale_fac)
 {
-	DLRBT_Tree keys, blocks;
+	DLRBT_Tree keys;
 
 	BLI_dlrbTree_init(&keys);
-	BLI_dlrbTree_init(&blocks);
-
-	summary_to_keylist(ac, &keys, &blocks);
 
-	BLI_dlrbTree_linkedlist_sync(&keys);
-	BLI_dlrbTree_linkedlist_sync(&blocks);
+	summary_to_keylist(ac, &keys);
 
-	draw_keylist(v2d, &keys, &blocks, ypos, yscale_fac, false);
+	draw_keylist(v2d, &keys, ypos, yscale_fac, false);
 
 	BLI_dlrbTree_free(&keys);
-	BLI_dlrbTree_free(&blocks);
 }
 
 void draw_scene_channel(View2D *v2d, bDopeSheet *ads, Scene *sce, float ypos, float yscale_fac)
 {
-	DLRBT_Tree keys, blocks;
+	DLRBT_Tree keys;
 
 	BLI_dlrbTree_init(&keys);
-	BLI_dlrbTree_init(&blocks);
-
-	scene_to_keylist(ads, sce, &keys, &blocks);
 
-	BLI_dlrbTree_linkedlist_sync(&keys);
-	BLI_dlrbTree_linkedlist_sync(&blocks);
+	scene_to_keylist(ads, sce, &keys);
 
-	draw_keylist(v2d, &keys, &blocks, ypos, yscale_fac, false);
+	draw_keylist(v2d, &keys, ypos, yscale_fac, false);
 
 	BLI_dlrbTree_free(&keys);
-	BLI_dlrbTree_free(&blocks);
 }
 
 void draw_object_channel(View2D *v2d, bDopeSheet *ads, Object *ob, float ypos, float yscale_fac)
 {
-	DLRBT_Tree keys, blocks;
+	DLRBT_Tree keys;
 
 	BLI_dlrbTree_init(&keys);
-	BLI_dlrbTree_init(&blocks);
 
-	ob_to_keylist(ads, ob, &keys, &blocks);
+	ob_to_keylist(ads, ob, &keys);
 
-	BLI_dlrbTree_linkedlist_sync(&keys);
-	BLI_dlrbTree_linkedlist_sync(&blocks);
-
-	draw_keylist(v2d, &keys, &blocks, ypos, yscale_fac, false);
+	draw_keylist(v2d, &keys, ypos, yscale_fac, false);
 
 	BLI_dlrbTree_free(&keys);
-	BLI_dlrbTree_free(&blocks);
 }
 
 void draw_fcurve_channel(View2D *v2d, AnimData *adt, FCurve *fcu, float ypos, float yscale_fac)
 {
-	DLRBT_Tree keys, blocks;
+	DLRBT_Tree keys;
 
 	bool locked = (fcu->flag & FCURVE_PROTECTED) ||
 	              ((fcu->grp) && (fcu->grp->flag & AGRP_PROTECTED)) ||
 	              ((adt && adt->action) && ID_IS_LINKED(adt->action));
 
 	BLI_dlrbTree_init(&keys);
-	BLI_dlrbTree_init(&blocks);
 
-	fcurve_to_keylist(adt, fcu, &keys, &blocks);
+	fcurve_to_keylist(adt, fcu, &keys);
 
-	BLI_dlrbTree_linkedlist_sync(&keys);
-	BLI_dlrbTree_linkedlist_sync(&blocks);
-
-	draw_keylist(v2d, &keys, &blocks, ypos, yscale_fac, locked);
+	draw_keylist(v2d, &keys, ypos, yscale_fac, locked);
 
 	BLI_dlrbTree_free(&keys);
-	BLI_dlrbTree_free(&blocks);
 }
 
 void draw_agroup_channel(View2D *v2d, AnimData *adt, bActionGroup *agrp, float ypos, float yscale_fac)
 {
-	DLRBT_Tree keys, blocks;
+	DLRBT_Tree keys;
 
 	bool locked = (agrp->flag & AGRP_PROTECTED) ||
 	              ((adt && adt->action) && ID_IS_LINKED(adt->action));
 
 	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);
+	agroup_to_keylist(adt, agrp, &keys);
 
-	draw_keylist(v2d, &keys, &blocks, ypos, yscale_fac, locked);
+	draw_keylist(v2d, &keys, ypos, yscale_fac, locked);
 
 	BLI_dlrbTree_free(&keys);
-	BLI_dlrbTree_free(&blocks);
 }
 
 void draw_action_channel(View2D *v2d, AnimData *adt, bAction *act, float ypos, float yscale_fac)
 {
-	DLRBT_Tree keys, blocks;
+	DLRBT_Tree keys;
 
 	bool locked = (act && ID_IS_LINKED(act));
 
 	BLI_dlrbTree_init(&keys);
-	BLI_dlrbTree_init(&blocks);
-
-	action_to_keylist(adt, act, &keys, &blocks);
 
-	BLI_dlrbTree_linkedlist_sync(&keys);
-	BLI_dlrbTree_linkedlist_sync(&blocks);
+	action_to_keylist(adt, act, &keys);
 
-	draw_keylist(v2d, &keys, &blocks, ypos, yscale_fac, locked);
+	draw_keylist(v2d, &keys, ypos, yscale_fac, locked);
 
 	BLI_dlrbTree_free(&keys);
-	BLI_dlrbTree_free(&blocks);
 }
 
 void draw_gpencil_channel(View2D *v2d, bDopeSheet *ads, bGPdata *gpd, float ypos, float yscale_fac)
@@ -793,9 +701,7 @@ void draw_gpencil_channel(View2D *v2d, bDopeSheet *ads, bGPdata *gpd, float ypos
 
 	gpencil_to_keylist(ads, gpd, &keys, false);
 
-	BLI_dlrbTree_linkedlist_sync(&keys);
-
-	draw_keylist(v2d, &keys, NULL, ypos, yscale_fac, false);
+	draw_keylist(v2d, &keys, ypos, yscale_fac, false);
 
 	BLI_dlrbTree_free(&keys);
 }
@@ -810,9 +716,7 @@ void draw_gpl_channel(View2D *v2d, bDopeSheet *ads, bGPDlayer *gpl, float ypos,
 
 	gpl_to_keylist(ads, gpl, &keys);
 
-	BLI_dlrbTree_linkedlist_sync(&keys);
-
-	draw_keylist(v2d, &keys, NULL, ypos, yscale_fac, locked);
+	draw_keylist(v2d, &keys, ypos, yscale_fac, locked);
 
 	BLI_dlrbTree_free(&keys);
 }
@@ -827,16 +731,14 @@ void draw_masklay_channel(View2D *v2d, bDopeSheet *ads, MaskLayer *masklay, floa
 
 	mask_to_keylist(ads, masklay, &keys);
 
-	BLI_dlrbTree_linkedlist_sync(&keys);
-
-	draw_keylist(v2d, &keys, NULL, ypos, yscale_fac, locked);
+	draw_keylist(v2d, &keys, ypos, yscale_fac, locked);
 
 	BLI_dlrbTree_free(&keys);
 }
 
 /* *************************** Keyframe List Conversions *************************** */
 
-void summary_to_keylist(bAnimContext *ac, DLRBT_Tree *keys, DLRBT_Tree *blocks)
+void summary_to_keylist(bAnimContext *ac, DLRBT_Tree *keys)
 {
 	if (ac) {
 		ListBase anim_data = {NULL, NULL};
@@ -856,7 +758,7 @@ void summary_to_keylist(bAnimContext *ac, DLRBT_Tree *keys, DLRBT_Tree *blocks)
 
 			switch (ale->datatype) {
 				case ALE_FCURVE:
-					fcurve_to_keylist(ale->adt, ale->data, keys, blocks);
+					fcurve_to_keylist(ale->adt, ale->data, keys);
 					break;
 				case ALE_MASKLAY:
 					mask_to_keylist(ac->ads, ale->data, keys);
@@ -874,7 +776,7 @@ void summary_to_keylist(bAnimContext *ac, DLRBT_Tree *keys, DLRBT_Tree *blocks)
 	}
 }
 
-void scene_to_keylist(bDopeSheet *ads, Scene *sce, DLRBT_Tree *keys, DLRBT_Tree *blocks)
+void scene_to_keylist(bDopeSheet *ads, Scene *sce, DLRBT_Tree *keys)
 {
 	bAnimContext ac = {NULL};
 	ListBase anim_data = {NULL, NULL};
@@ -902,12 +804,12 @@ void scene_to_keylist(bDopeSheet *ads, Scene *sce, DLRBT_Tree *keys, DLRBT_Tree
 
 	/* loop through each F-Curve, grabbing the keyframes */
 	for (ale = anim_data.first; ale; ale = ale->next)
-		fcurve_to_keylist(ale->adt, ale->data, keys, blocks);
+		fcurve_to_keylist(ale->adt, ale->data, keys);
 
 	ANIM_animdata_freelist(&anim_data);
 }
 
-void ob_to_keylist(bDopeSheet *ads, Object *ob, DLRBT_Tree *keys, DLRBT_Tree *blocks)
+void ob_to_keylist(bDopeSheet *ads, Object *ob, DLRBT_Tree *keys)
 {
 	bAnimContext ac = {NULL};
 	ListBase anim_data = {NULL, NULL};
@@ -938,12 +840,12 @@ void ob_to_keylist(bDopeSheet *ads, Object *ob, DLRBT_Tree *keys, DLRBT_Tree *bl
 
 	/* loop through each F-Curve, grabbing the keyframes */
 	for (ale = anim_data.first; ale; ale = ale->next)
-		fcurve_to_keylist(ale->adt, ale->data, keys, blocks);
+		fcurve_to_keylist(ale->adt, ale->data, keys);
 
 	ANIM_animdata_freelist(&anim_data);
 }
 
-void cachefile_to_keylist(bDopeSheet *ads, CacheFile *cache_file, DLRBT_Tree *keys, DLRBT_Tree *blocks)
+void cachefile_to_keylist(bDopeSheet *ads, CacheFile *cache_file, DLRBT_Tree *keys)
 {
 	if (cache_file == NULL) {
 		return;
@@ -968,13 +870,13 @@ void cachefile_to_keylist(bDopeSheet *ads, CacheFile *cache_file, DLRBT_Tree *ke
 
 	/* loop through each F-Curve, grabbing the keyframes */
 	for (bAnimListElem *ale = anim_data.first; ale; ale = ale->next) {
-		fcurve_to_keylist(ale->adt, ale->data, keys, blocks);
+		fcurve_to_keylist(ale->adt, ale->data, keys);
 	}
 
 	ANIM_animdata_freelist(&anim_data);
 }
 
-void fcurve_to_keylist(AnimData *adt, FCurve *fcu, DLRBT_Tree *keys, DLRBT_Tree *blocks)
+void fcurve_to_keylist(AnimData *adt, FCurve *fcu, DLRBT_Tree *keys)
 {
 	BezTriple *bezt;
 	unsigned int v;
@@ -984,17 +886,13 @@ void fcurve_to_keylist(AnimData *adt, FCurve *fcu, DLRBT_Tree *keys, DLRBT_Tree
 		if (adt)
 			ANIM_nla_mapping_apply_fcurve(adt, fcu, 0, 0);
 
-		/* loop through beztriples, making ActKeysColumns and ActKeyBlocks */
+		/* loop through beztriples, making ActKeysColumns */
 		for (v = 0, bezt = fcu->bezt; v < fcu->totvert; v++, bezt++) {
 			add_bezt_to_keycolumns_list(keys, bezt);
-			if (blocks) add_bezt_to_keyblocks_list(blocks, fcu->bezt, bezt);
 		}
 
-		/* update the number of curves that elements have appeared in  */
-		if (keys)
-			set_touched_actkeycolumn(keys->root);
-		if (blocks)
-			set_touched_actkeyblock(blocks->root);
+		/* Update keyblocks. */
+		update_keyblocks(keys, fcu->bezt, fcu->totvert);
 
 		/* unapply NLA-mapping if applicable */
 		if (adt)
@@ -1002,26 +900,26 @@ void fcurve_to_keylist(AnimData *adt, FCurve *fcu, DLRBT_Tree *keys, DLRBT_Tree
 	}
 }
 
-void agroup_to_keylist(AnimData *adt, bActionGroup *agrp, DLRBT_Tree *keys, DLRBT_Tree *blocks)
+void agroup_to_keylist(AnimData *adt, bActionGroup *agrp, DLRBT_Tree *keys)
 {
 	FCurve *fcu;
 
 	if (agrp) {
 		/* loop through F-Curves */
 		for (fcu = agrp->channels.first; fcu && fcu->grp == agrp; fcu = fcu->next) {
-			fcurve_to_keylist(adt, fcu, keys, blocks);
+			fcurve_to_keylist(adt, fcu, keys);
 		}
 	}
 }
 
-void action_to_keylist(AnimData *adt, bAction *act, DLRBT_Tree *keys, DLRBT_Tree *blocks)
+void action_to_keylist(AnimData *adt, bAction *act, DLRBT_Tree *keys)
 {
 	FCurve *fcu;
 
 	if (act) {
 		/* loop through F-Curves */
 		for (fcu = act->curves.first; fcu; fcu = fcu->next) {
-			fcurve_to_keylist(adt, fcu, keys, blocks);
+			fcurve_to_keylist(adt, fcu, keys);
 		}
 	}
 }
@@ -1051,6 +949,8 @@ void gpl_to_keylist(bDopeSheet *UNUSED(ads), bGPDlayer *gpl, DLRBT_Tree *keys)
 		/* although the frames should already be in an ordered list, they are not suitable for displaying yet */
 		for (gpf = gpl->frames.first; gpf; gpf = gpf->next)
 			add_gpframe_to_keycolumns_list(keys, gpf);
+
+		update_keyblocks(keys, NULL, 0);
 	}
 }
 
@@ -1065,5 +965,7 @@ void mask_to_keylist(bDopeSheet *UNUSED(ads), MaskLayer *masklay, DLRBT_Tree *ke
 		{
 			add_masklay_to_keycolumns_list(keys, masklay_shape);
 		}
+
+		update_keyblocks(keys, NULL, 0);
 	}
 }
diff --git a/source/blender/editors/armature/pose_lib.c b/source/blender/editors/armature/pose_lib.c
index 2227bf33908..673ca587811 100644
--- a/source/blender/editors/armature/pose_lib.c
+++ b/source/blender/editors/armature/pose_lib.c
@@ -312,8 +312,7 @@ static int poselib_sanitize_exec(bContext *C, wmOperator *op)
 
 	/* determine which frames have keys */
 	BLI_dlrbTree_init(&keys);
-	action_to_keylist(NULL, act, &keys, NULL);
-	BLI_dlrbTree_linkedlist_sync(&keys);
+	action_to_keylist(NULL, act, &keys);
 
 	/* for each key, make sure there is a corresponding pose */
 	for (ak = keys.first; ak; ak = ak->next) {
diff --git a/source/blender/editors/armature/pose_slide.c b/source/blender/editors/armature/pose_slide.c
index 0a07af4ab43..3cd0897a326 100644
--- a/source/blender/editors/armature/pose_slide.c
+++ b/source/blender/editors/armature/pose_slide.c
@@ -722,13 +722,10 @@ static int pose_slide_invoke_common(bContext *C, wmOperator *op, tPoseSlideOp *p
 		/* do this for each F-Curve */
 		for (ld = pfl->fcurves.first; ld; ld = ld->next) {
 			FCurve *fcu = (FCurve *)ld->data;
-			fcurve_to_keylist(adt, fcu, &pso->keys, NULL);
+			fcurve_to_keylist(adt, fcu, &pso->keys);
 		}
 	}
 
-	/* consolidate these keyframes, and figure out the nearest ones */
-	BLI_dlrbTree_linkedlist_sync(&pso->keys);
-
 	/* cancel if no keyframes found... */
 	if (pso->keys.root) {
 		ActKeyColumn *ak;
@@ -1265,8 +1262,7 @@ typedef union tPosePropagate_ModeData {
  */
 static float pose_propagate_get_boneHoldEndFrame(Object *ob, tPChanFCurveLink *pfl, float startFrame)
 {
-	DLRBT_Tree keys, blocks;
-	ActKeyBlock *ab;
+	DLRBT_Tree keys;
 
 	AnimData *adt = ob->adt;
 	LinkData *ld;
@@ -1274,84 +1270,67 @@ static float pose_propagate_get_boneHoldEndFrame(Object *ob, tPChanFCurveLink *p
 
 	/* set up optimized data-structures for searching for relevant keyframes + holds */
 	BLI_dlrbTree_init(&keys);
-	BLI_dlrbTree_init(&blocks);
 
 	for (ld = pfl->fcurves.first; ld; ld = ld->next) {
 		FCurve *fcu = (FCurve *)ld->data;
-		fcurve_to_keylist(adt, fcu, &keys, &blocks);
+		fcurve_to_keylist(adt, fcu, &keys);
 	}
 
-	BLI_dlrbTree_linkedlist_sync(&keys);
-	BLI_dlrbTree_linkedlist_sync(&blocks);
-
 	/* find the long keyframe (i.e. hold), and hence obtain the endFrame value
 	 *	- the best case would be one that starts on the frame itself
 	 */
-	ab = (ActKeyBlock *)BLI_dlrbTree_search_exact(&blocks, compare_ab_cfraPtr, &startFrame);
-
-	if (actkeyblock_is_valid(ab, &keys) == 0) {
-		/* There are only two cases for no-exact match:
-		 *  1) the current frame is just before another key but not on a key itself
-		 *  2) the current frame is on a key, but that key doesn't link to the next
-		 *
-		 * If we've got the first case, then we can search for another block,
-		 * otherwise forget it, as we'd be overwriting some valid data.
-		 */
-		if (BLI_dlrbTree_search_exact(&keys, compare_ak_cfraPtr, &startFrame) == NULL) {
-			/* we've got case 1, so try the one after */
-			ab = (ActKeyBlock *)BLI_dlrbTree_search_next(&blocks, compare_ab_cfraPtr, &startFrame);
-
-			if (actkeyblock_is_valid(ab, &keys) == 0) {
-				/* try the block before this frame then as last resort */
-				ab = (ActKeyBlock *)BLI_dlrbTree_search_prev(&blocks, compare_ab_cfraPtr, &startFrame);
-
-				/* whatever happens, stop searching now... */
-				if (actkeyblock_is_valid(ab, &keys) == 0) {
-					/* restrict range to just the frame itself
-					 * i.e. everything is in motion, so no holds to safely overwrite
-					 */
-					ab = NULL;
-				}
-			}
-		}
-		else {
-			/* we've got case 2 - set ab to NULL just in case, since we shouldn't do anything in this case */
-			ab = NULL;
+	ActKeyColumn *ab = (ActKeyColumn *)BLI_dlrbTree_search_exact(&keys, compare_ak_cfraPtr, &startFrame);
+
+	/* There are only two cases for no-exact match:
+	 *  1) the current frame is just before another key but not on a key itself
+	 *  2) the current frame is on a key, but that key doesn't link to the next
+	 *
+	 * If we've got the first case, then we can search for another block,
+	 * otherwise forget it, as we'd be overwriting some valid data.
+	 */
+	if (ab == NULL) {
+		/* we've got case 1, so try the one after */
+		ab = (ActKeyColumn *)BLI_dlrbTree_search_next(&keys, compare_ak_cfraPtr, &startFrame);
+
+		if ((actkeyblock_get_valid_hold(ab) & ACTKEYBLOCK_FLAG_STATIC_HOLD) == 0) {
+			/* try the block before this frame then as last resort */
+			ab = (ActKeyColumn *)BLI_dlrbTree_search_prev(&keys, compare_ak_cfraPtr, &startFrame);
 		}
 	}
 
+	/* whatever happens, stop searching now... */
+	if ((actkeyblock_get_valid_hold(ab) & ACTKEYBLOCK_FLAG_STATIC_HOLD) == 0) {
+		/* restrict range to just the frame itself
+		 * i.e. everything is in motion, so no holds to safely overwrite
+		 */
+		ab = NULL;
+	}
+
 	/* check if we can go any further than we've already gone */
 	if (ab) {
 		/* go to next if it is also valid and meets "extension" criteria */
 		while (ab->next) {
-			ActKeyBlock *abn = (ActKeyBlock *)ab->next;
+			ActKeyColumn *abn = ab->next;
 
 			/* must be valid */
-			if (actkeyblock_is_valid(abn, &keys) == 0)
-				break;
-			/* should start on the same frame that the last ended on */
-			if (ab->end != abn->start)
+			if ((actkeyblock_get_valid_hold(abn) & ACTKEYBLOCK_FLAG_STATIC_HOLD) == 0) {
 				break;
+			}
 			/* should have the same number of curves */
-			if (ab->totcurve != abn->totcurve)
-				break;
-			/* should have the same value
-			 * XXX: this may be a bit fuzzy on larger data sets, so be careful
-			 */
-			if (ab->val != abn->val)
+			if (ab->totblock != abn->totblock) {
 				break;
+			}
 
 			/* we can extend the bounds to the end of this "next" block now */
 			ab = abn;
 		}
 
 		/* end frame can now take the value of the end of the block */
-		endFrame = ab->end;
+		endFrame = ab->next->cfra;
 	}
 
 	/* free temp memory */
 	BLI_dlrbTree_free(&keys);
-	BLI_dlrbTree_free(&blocks);
 
 	/* return the end frame we've found */
 	return endFrame;
diff --git a/source/blender/editors/include/ED_keyframes_draw.h b/source/blender/editors/include/ED_keyframes_draw.h
index 45a0680e0c1..93fd8238fdd 100644
--- a/source/blender/editors/include/ED_keyframes_draw.h
+++ b/source/blender/editors/include/ED_keyframes_draw.h
@@ -50,6 +50,17 @@ struct DLRBT_Tree;
 
 /* ****************************** Base Structs ****************************** */
 
+/* Information about the stretch of time from current to the next column */
+typedef struct ActKeyBlockInfo {
+	/* Combination of flags from all curves. */
+	short flag;
+	/* Mask of flags that differ between curves. */
+	short conflict;
+
+	/* Selection flag. */
+	char sel;
+} ActKeyBlockInfo;
+
 /* Keyframe Column Struct */
 typedef struct ActKeyColumn {
 	/* ListBase linkage */
@@ -65,36 +76,21 @@ typedef struct ActKeyColumn {
 	short sel;
 	float cfra;
 
-	/* only while drawing - used to determine if long-keyframe needs to be drawn */
-	short modified;
-	short totcurve;
-} ActKeyColumn;
-
-/* 'Long Keyframe' Struct */
-typedef struct ActKeyBlock {
-	/* ListBase linkage */
-	struct ActKeyBlock *next, *prev;
-
-	/* 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 flag;
-	float val;
-	float start, end;
+	ActKeyBlockInfo block;
 
-	/* only while drawing - used to determine if block needs to be drawn */
-	short modified;
-	short totcurve;
-} ActKeyBlock;
+	/* number of curves and keys in this column */
+	short totcurve, totkey, totblock;
+} ActKeyColumn;
 
-/* ActKeyBlock - Flag */
-typedef enum eActKeyBlock_Flag {
+/* ActKeyBlockInfo - Flag */
+typedef enum eActKeyBlock_Hold {
 	/* Key block represents a moving hold */
 	ACTKEYBLOCK_FLAG_MOVING_HOLD     = (1 << 0),
+	/* Key block represents a static hold */
+	ACTKEYBLOCK_FLAG_STATIC_HOLD     = (1 << 1),
+	/* Key block represents any kind of hold */
+	ACTKEYBLOCK_FLAG_ANY_HOLD        = (1 << 2),
 } eActKeyBlock_Flag;
 
 /* *********************** Keyframe Drawing ****************************** */
@@ -138,25 +134,25 @@ void draw_masklay_channel(struct View2D *v2d, struct bDopeSheet *ads, struct Mas
 
 /* Keydata Generation --------------- */
 /* F-Curve */
-void fcurve_to_keylist(struct AnimData *adt, struct FCurve *fcu, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks);
+void fcurve_to_keylist(struct AnimData *adt, struct FCurve *fcu, struct DLRBT_Tree *keys);
 /* Action Group */
-void agroup_to_keylist(struct AnimData *adt, struct bActionGroup *agrp, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks);
+void agroup_to_keylist(struct AnimData *adt, struct bActionGroup *agrp, struct DLRBT_Tree *keys);
 /* Action */
-void action_to_keylist(struct AnimData *adt, struct bAction *act, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks);
+void action_to_keylist(struct AnimData *adt, struct bAction *act, struct DLRBT_Tree *keys);
 /* Object */
-void ob_to_keylist(struct bDopeSheet *ads, struct Object *ob, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks);
+void ob_to_keylist(struct bDopeSheet *ads, struct Object *ob, struct DLRBT_Tree *keys);
 /* Cache File */
-void cachefile_to_keylist(struct bDopeSheet *ads, struct CacheFile *cache_file, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks);
+void cachefile_to_keylist(struct bDopeSheet *ads, struct CacheFile *cache_file, struct DLRBT_Tree *keys);
 /* Scene */
-void scene_to_keylist(struct bDopeSheet *ads, struct Scene *sce, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks);
+void scene_to_keylist(struct bDopeSheet *ads, struct Scene *sce, struct DLRBT_Tree *keys);
 /* DopeSheet Summary */
-void summary_to_keylist(struct bAnimContext *ac, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks);
+void summary_to_keylist(struct bAnimContext *ac, struct DLRBT_Tree *keys);
 /* Grease Pencil datablock summary */
 void gpencil_to_keylist(struct bDopeSheet *ads, struct bGPdata *gpd, struct DLRBT_Tree *keys, const bool active);
 /* Grease Pencil Layer */
 void gpl_to_keylist(struct bDopeSheet *ads, struct bGPDlayer *gpl, struct DLRBT_Tree *keys);
 /* Palette */
-void palette_to_keylist(struct bDopeSheet *ads, struct Palette *palette, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks);
+void palette_to_keylist(struct bDopeSheet *ads, struct Palette *palette, struct DLRBT_Tree *keys);
 /* Mask */
 void mask_to_keylist(struct bDopeSheet *UNUSED(ads), struct MaskLayer *masklay, struct DLRBT_Tree *keys);
 
@@ -164,10 +160,7 @@ void mask_to_keylist(struct bDopeSheet *UNUSED(ads), struct MaskLayer *masklay,
 /* Comparator callback used for ActKeyColumns and cframe float-value pointer */
 short compare_ak_cfraPtr(void *node, void *data);
 
-/* Comparator callback used for ActKeyBlocks and cframe float-value pointer */
-short compare_ab_cfraPtr(void *node, void *data);
-
-/* Checks if ActKeyBlock can be used (i.e. drawn/used to detect "holds") */
-bool actkeyblock_is_valid(ActKeyBlock *ab, struct DLRBT_Tree *keys);
+/* Checks if ActKeyColumn can be used as a block (i.e. drawn/used to detect "holds") */
+int actkeyblock_get_valid_hold(ActKeyColumn *ab);
 
 #endif  /*  __ED_KEYFRAMES_DRAW_H__ */
diff --git a/source/blender/editors/screen/screen_ops.c b/source/blender/editors/screen/screen_ops.c
index 72d5783255d..27c9f522c54 100644
--- a/source/blender/editors/screen/screen_ops.c
+++ b/source/blender/editors/screen/screen_ops.c
@@ -2627,10 +2627,10 @@ static int keyframe_jump_exec(bContext *C, wmOperator *op)
 	}
 
 	/* populate tree with keyframe nodes */
-	scene_to_keylist(&ads, scene, &keys, NULL);
+	scene_to_keylist(&ads, scene, &keys);
 
 	if (ob) {
-		ob_to_keylist(&ads, ob, &keys, NULL);
+		ob_to_keylist(&ads, ob, &keys);
 
 		if (ob->type == OB_GPENCIL) {
 			const bool active = !(scene->flag & SCE_KEYS_NO_SELONLY);
@@ -2646,9 +2646,6 @@ static int keyframe_jump_exec(bContext *C, wmOperator *op)
 		}
 	}
 
-	/* build linked-list for searching */
-	BLI_dlrbTree_linkedlist_sync(&keys);
-
 	/* find matching keyframe in the right direction */
 	if (next)
 		ak = (ActKeyColumn *)BLI_dlrbTree_search_next(&keys, compare_ak_cfraPtr, &cfra);
diff --git a/source/blender/editors/space_action/action_select.c b/source/blender/editors/space_action/action_select.c
index f85177f5228..59211ba01d7 100644
--- a/source/blender/editors/space_action/action_select.c
+++ b/source/blender/editors/space_action/action_select.c
@@ -1449,37 +1449,37 @@ static void mouse_action_keys(bAnimContext *ac, const int mval[2], short select_
 				case ALE_SCE:
 				{
 					Scene *scene = (Scene *)ale->key_data;
-					scene_to_keylist(ads, scene, &anim_keys, NULL);
+					scene_to_keylist(ads, scene, &anim_keys);
 					break;
 				}
 				case ALE_OB:
 				{
 					Object *ob = (Object *)ale->key_data;
-					ob_to_keylist(ads, ob, &anim_keys, NULL);
+					ob_to_keylist(ads, ob, &anim_keys);
 					break;
 				}
 				case ALE_ACT:
 				{
 					bAction *act = (bAction *)ale->key_data;
-					action_to_keylist(adt, act, &anim_keys, NULL);
+					action_to_keylist(adt, act, &anim_keys);
 					break;
 				}
 				case ALE_FCURVE:
 				{
 					FCurve *fcu = (FCurve *)ale->key_data;
-					fcurve_to_keylist(adt, fcu, &anim_keys, NULL);
+					fcurve_to_keylist(adt, fcu, &anim_keys);
 					break;
 				}
 			}
 		}
 		else if (ale->type == ANIMTYPE_SUMMARY) {
 			/* dopesheet summary covers everything */
-			summary_to_keylist(ac, &anim_keys, NULL);
+			summary_to_keylist(ac, &anim_keys);
 		}
 		else if (ale->type == ANIMTYPE_GROUP) {
 			// TODO: why don't we just give groups key_data too?
 			bActionGroup *agrp = (bActionGroup *)ale->data;
-			agroup_to_keylist(adt, agrp, &anim_keys, NULL);
+			agroup_to_keylist(adt, agrp, &anim_keys);
 		}
 		else if (ale->type == ANIMTYPE_GPLAYER) {
 			// TODO: why don't we just give gplayers key_data too?
diff --git a/source/blender/editors/space_nla/nla_draw.c b/source/blender/editors/space_nla/nla_draw.c
index 7dd8c7f2eed..88f2766a915 100644
--- a/source/blender/editors/space_nla/nla_draw.c
+++ b/source/blender/editors/space_nla/nla_draw.c
@@ -106,8 +106,7 @@ static void nla_action_draw_keyframes(AnimData *adt, bAction *act, float y, floa
 	/* get a list of the keyframes with NLA-scaling applied */
 	DLRBT_Tree keys;
 	BLI_dlrbTree_init(&keys);
-	action_to_keylist(adt, act, &keys, NULL);
-	BLI_dlrbTree_linkedlist_sync(&keys);
+	action_to_keylist(adt, act, &keys);
 
 	if (ELEM(NULL, act, keys.first))
 		return;