Cleanup: Hide implementation details for ED_keyframe_keylist.

For T78995 we want to change the data structure of keylists to
improve performance. (Probably a Vector with bin-search capabilities).

This patch hides the internal structure of the keylists behind `AnimKeylist`
structure. This allows us to change the internals without 'breaking' where it is
being used.

The change adds functions to create, free, find and walk over the
keylist.

Reviewed By: sybren

Maniphest Tasks: T78995

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

12 files changed, 364 insertions, 265 deletions

diff --git a/source/blender/blenlib/BLI_range.h b/source/blender/blenlib/BLI_range.h
new file mode 100644
index 00000000000..ad4cd6c162e
--- /dev/null
+++ b/source/blender/blenlib/BLI_range.h
@@ -0,0 +1,34 @@
+/*
+ * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#pragma once
+
+/** \file
+ * \ingroup bli
+ */
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+typedef struct Range2f {
+  float min;
+  float max;
+} Range2f;
+
+#ifdef __cplusplus
+}
+#endif
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index ea5572f1c8a..b6603dce378 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -265,6 +265,7 @@ set(SRC
   BLI_quadric.h
   BLI_rand.h
   BLI_rand.hh
+  BLI_range.h
   BLI_rect.h
   BLI_resource_scope.hh
   BLI_scanfill.h
diff --git a/source/blender/editors/animation/anim_draw.c b/source/blender/editors/animation/anim_draw.c
index baf8adf28d0..6469c47ab11 100644
--- a/source/blender/editors/animation/anim_draw.c
+++ b/source/blender/editors/animation/anim_draw.c
@@ -494,7 +494,7 @@ static bool find_prev_next_keyframes(struct bContext *C, int *r_nextfra, int *r_
   Object *ob = CTX_data_active_object(C);
   Mask *mask = CTX_data_edit_mask(C);
   bDopeSheet ads = {NULL};
-  DLRBT_Tree keys;
+  struct AnimKeylist *keylist = ED_keylist_create();
   ActKeyColumn *aknext, *akprev;
   float cfranext, cfraprev;
   bool donenext = false, doneprev = false;
@@ -502,9 +502,6 @@ static bool find_prev_next_keyframes(struct bContext *C, int *r_nextfra, int *r_
 
   cfranext = cfraprev = (float)(CFRA);
 
-  /* init binarytree-list for getting keyframes */
-  BLI_dlrbTree_init(&keys);
-
   /* seed up dummy dopesheet context with flags to perform necessary filtering */
   if ((scene->flag & SCE_KEYS_NO_SELONLY) == 0) {
     /* only selected channels are included */
@@ -512,22 +509,22 @@ static bool find_prev_next_keyframes(struct bContext *C, int *r_nextfra, int *r_
   }
 
   /* populate tree with keyframe nodes */
-  scene_to_keylist(&ads, scene, &keys, 0);
-  gpencil_to_keylist(&ads, scene->gpd, &keys, false);
+  scene_to_keylist(&ads, scene, keylist, 0);
+  gpencil_to_keylist(&ads, scene->gpd, keylist, false);
 
   if (ob) {
-    ob_to_keylist(&ads, ob, &keys, 0);
-    gpencil_to_keylist(&ads, ob->data, &keys, false);
+    ob_to_keylist(&ads, ob, keylist, 0);
+    gpencil_to_keylist(&ads, ob->data, keylist, false);
   }
 
   if (mask) {
     MaskLayer *masklay = BKE_mask_layer_active(mask);
-    mask_to_keylist(&ads, masklay, &keys);
+    mask_to_keylist(&ads, masklay, keylist);
   }
 
   /* find matching keyframe in the right direction */
   do {
-    aknext = (ActKeyColumn *)BLI_dlrbTree_search_next(&keys, compare_ak_cfraPtr, &cfranext);
+    aknext = ED_keylist_find_next(keylist, cfranext);
 
     if (aknext) {
       if (CFRA == (int)aknext->cfra) {
@@ -545,7 +542,7 @@ static bool find_prev_next_keyframes(struct bContext *C, int *r_nextfra, int *r_
   } while ((aknext != NULL) && (donenext == false));
 
   do {
-    akprev = (ActKeyColumn *)BLI_dlrbTree_search_prev(&keys, compare_ak_cfraPtr, &cfraprev);
+    akprev = ED_keylist_find_prev(keylist, cfraprev);
 
     if (akprev) {
       if (CFRA == (int)akprev->cfra) {
@@ -562,7 +559,7 @@ static bool find_prev_next_keyframes(struct bContext *C, int *r_nextfra, int *r_
   } while ((akprev != NULL) && (doneprev == false));
 
   /* free temp stuff */
-  BLI_dlrbTree_free(&keys);
+  ED_keylist_free(keylist);
 
   /* any success? */
   if (doneprev || donenext) {
diff --git a/source/blender/editors/animation/anim_motion_paths.c b/source/blender/editors/animation/anim_motion_paths.c
index bddd5dbff55..2a3ae35aab0 100644
--- a/source/blender/editors/animation/anim_motion_paths.c
+++ b/source/blender/editors/animation/anim_motion_paths.c
@@ -55,7 +55,7 @@ typedef struct MPathTarget {
 
   bMotionPath *mpath; /* motion path in question */
 
-  DLRBT_Tree keys; /* temp, to know where the keyframes are */
+  struct AnimKeylist *keylist; /* temp, to know where the keyframes are */
 
   /* Original (Source Objects) */
   Object *ob;          /* source object */
@@ -187,7 +187,7 @@ static void motionpaths_calc_bake_targets(ListBase *targets, int cframe)
     float mframe = (float)(cframe);
 
     /* Tag if it's a keyframe */
-    if (BLI_dlrbTree_search_exact(&mpt->keys, compare_ak_cfraPtr, &mframe)) {
+    if (ED_keylist_find_exact(mpt->keylist, mframe)) {
       mpv->flag |= MOTIONPATH_VERT_KEY;
     }
     else {
@@ -234,52 +234,54 @@ static void motionpath_get_global_framerange(ListBase *targets, int *r_sfra, int
   }
 }
 
-static int motionpath_get_prev_keyframe(MPathTarget *mpt, DLRBT_Tree *fcu_keys, int current_frame)
+static int motionpath_get_prev_keyframe(MPathTarget *mpt,
+                                        struct AnimKeylist *keylist,
+                                        int current_frame)
 {
   if (current_frame <= mpt->mpath->start_frame) {
     return mpt->mpath->start_frame;
   }
 
   float current_frame_float = current_frame;
-  DLRBT_Node *node = BLI_dlrbTree_search_prev(fcu_keys, compare_ak_cfraPtr, &current_frame_float);
-  if (node == NULL) {
+  const ActKeyColumn *ak = ED_keylist_find_prev(keylist, current_frame_float);
+  if (ak == NULL) {
     return mpt->mpath->start_frame;
   }
 
-  ActKeyColumn *key_data = (ActKeyColumn *)node;
-  return key_data->cfra;
+  return ak->cfra;
 }
 
 static int motionpath_get_prev_prev_keyframe(MPathTarget *mpt,
-                                             DLRBT_Tree *fcu_keys,
+                                             struct AnimKeylist *keylist,
                                              int current_frame)
 {
-  int frame = motionpath_get_prev_keyframe(mpt, fcu_keys, current_frame);
-  return motionpath_get_prev_keyframe(mpt, fcu_keys, frame);
+  int frame = motionpath_get_prev_keyframe(mpt, keylist, current_frame);
+  return motionpath_get_prev_keyframe(mpt, keylist, frame);
 }
 
-static int motionpath_get_next_keyframe(MPathTarget *mpt, DLRBT_Tree *fcu_keys, int current_frame)
+static int motionpath_get_next_keyframe(MPathTarget *mpt,
+                                        struct AnimKeylist *keylist,
+                                        int current_frame)
 {
   if (current_frame >= mpt->mpath->end_frame) {
     return mpt->mpath->end_frame;
   }
 
   float current_frame_float = current_frame;
-  DLRBT_Node *node = BLI_dlrbTree_search_next(fcu_keys, compare_ak_cfraPtr, &current_frame_float);
-  if (node == NULL) {
+  const ActKeyColumn *ak = ED_keylist_find_next(keylist, current_frame_float);
+  if (ak == NULL) {
     return mpt->mpath->end_frame;
   }
 
-  ActKeyColumn *key_data = (ActKeyColumn *)node;
-  return key_data->cfra;
+  return ak->cfra;
 }
 
 static int motionpath_get_next_next_keyframe(MPathTarget *mpt,
-                                             DLRBT_Tree *fcu_keys,
+                                             struct AnimKeylist *keylist,
                                              int current_frame)
 {
-  int frame = motionpath_get_next_keyframe(mpt, fcu_keys, current_frame);
-  return motionpath_get_next_keyframe(mpt, fcu_keys, frame);
+  int frame = motionpath_get_next_keyframe(mpt, keylist, current_frame);
+  return motionpath_get_next_keyframe(mpt, keylist, frame);
 }
 
 static bool motionpath_check_can_use_keyframe_range(MPathTarget *UNUSED(mpt),
@@ -324,17 +326,16 @@ static void motionpath_calculate_update_range(MPathTarget *mpt,
    * Could be optimized further by storing some flags about which channels has been modified so
    * we ignore all others (which can potentially make an update range unnecessary wide). */
   for (FCurve *fcu = fcurve_list->first; fcu != NULL; fcu = fcu->next) {
-    DLRBT_Tree fcu_keys;
-    BLI_dlrbTree_init(&fcu_keys);
-    fcurve_to_keylist(adt, fcu, &fcu_keys, 0);
+    struct AnimKeylist *keylist = ED_keylist_create();
+    fcurve_to_keylist(adt, fcu, keylist, 0);
 
-    int fcu_sfra = motionpath_get_prev_prev_keyframe(mpt, &fcu_keys, current_frame);
-    int fcu_efra = motionpath_get_next_next_keyframe(mpt, &fcu_keys, current_frame);
+    int fcu_sfra = motionpath_get_prev_prev_keyframe(mpt, keylist, current_frame);
+    int fcu_efra = motionpath_get_next_next_keyframe(mpt, keylist, current_frame);
 
     /* Extend range further, since acceleration compensation propagates even further away. */
     if (fcu->auto_smoothing != FCURVE_SMOOTH_NONE) {
-      fcu_sfra = motionpath_get_prev_prev_keyframe(mpt, &fcu_keys, fcu_sfra);
-      fcu_efra = motionpath_get_next_next_keyframe(mpt, &fcu_keys, fcu_efra);
+      fcu_sfra = motionpath_get_prev_prev_keyframe(mpt, keylist, fcu_sfra);
+      fcu_efra = motionpath_get_next_next_keyframe(mpt, keylist, fcu_efra);
     }
 
     if (fcu_sfra <= fcu_efra) {
@@ -342,14 +343,14 @@ static void motionpath_calculate_update_range(MPathTarget *mpt,
       *r_efra = max_ii(*r_efra, fcu_efra);
     }
 
-    BLI_dlrbTree_free(&fcu_keys);
+    ED_keylist_free(keylist);
   }
 }
 
 static void motionpath_free_free_tree_data(ListBase *targets)
 {
   LISTBASE_FOREACH (MPathTarget *, mpt, targets) {
-    BLI_dlrbTree_free(&mpt->keys);
+    ED_keylist_free(mpt->keylist);
   }
 }
 
@@ -418,7 +419,7 @@ void animviz_calc_motionpaths(Depsgraph *depsgraph,
     AnimData *adt = BKE_animdata_from_id(&mpt->ob_eval->id);
 
     /* build list of all keyframes in active action for object or pchan */
-    BLI_dlrbTree_init(&mpt->keys);
+    mpt->keylist = ED_keylist_create();
 
     ListBase *fcurve_list = NULL;
     if (adt) {
@@ -433,12 +434,12 @@ void animviz_calc_motionpaths(Depsgraph *depsgraph,
 
         if (agrp) {
           fcurve_list = &agrp->channels;
-          agroup_to_keylist(adt, agrp, &mpt->keys, 0);
+          agroup_to_keylist(adt, agrp, mpt->keylist, 0);
         }
       }
       else {
         fcurve_list = &adt->action->curves;
-        action_to_keylist(adt, adt->action, &mpt->keys, 0);
+        action_to_keylist(adt, adt->action, mpt->keylist, 0);
       }
     }
 
@@ -502,7 +503,7 @@ void animviz_calc_motionpaths(Depsgraph *depsgraph,
     avs->recalc &= ~ANIMVIZ_RECALC_PATHS;
 
     /* Clean temp data */
-    BLI_dlrbTree_free(&mpt->keys);
+    ED_keylist_free(mpt->keylist);
 
     /* Free previous batches to force update. */
     GPU_VERTBUF_DISCARD_SAFE(mpath->points_vbo);
diff --git a/source/blender/editors/animation/keyframes_draw.c b/source/blender/editors/animation/keyframes_draw.c
index 4f512c9d7ca..deed79942ac 100644
--- a/source/blender/editors/animation/keyframes_draw.c
+++ b/source/blender/editors/animation/keyframes_draw.c
@@ -184,16 +184,12 @@ void draw_keyframe_shape(float x,
 }
 
 static void draw_keylist(View2D *v2d,
-                         DLRBT_Tree *keys,
+                         const struct AnimKeylist *keylist,
                          float ypos,
                          float yscale_fac,
                          bool channelLocked,
                          int saction_flag)
 {
-  if (keys == NULL) {
-    return;
-  }
-
   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;
@@ -228,6 +224,8 @@ static void draw_keylist(View2D *v2d,
   copy_v4_v4(ipo_color_mix, ipo_color);
   ipo_color_mix[3] *= 0.5f;
 
+  const ListBase *keys = ED_keylist_listbase(keylist);
+
   LISTBASE_FOREACH (ActKeyColumn *, ab, keys) {
     /* Draw grease pencil bars between keyframes. */
     if ((ab->next != NULL) && (ab->block.flag & ACTKEYBLOCK_FLAG_GPENCIL)) {
@@ -378,134 +376,118 @@ static void draw_keylist(View2D *v2d,
 void draw_summary_channel(
     View2D *v2d, bAnimContext *ac, float ypos, float yscale_fac, int saction_flag)
 {
-  DLRBT_Tree keys;
+  struct AnimKeylist *keylist = ED_keylist_create();
 
   saction_flag &= ~SACTION_SHOW_EXTREMES;
 
-  BLI_dlrbTree_init(&keys);
+  summary_to_keylist(ac, keylist, saction_flag);
 
-  summary_to_keylist(ac, &keys, saction_flag);
+  draw_keylist(v2d, keylist, ypos, yscale_fac, false, saction_flag);
 
-  draw_keylist(v2d, &keys, ypos, yscale_fac, false, saction_flag);
-
-  BLI_dlrbTree_free(&keys);
+  ED_keylist_free(keylist);
 }
 
 void draw_scene_channel(
     View2D *v2d, bDopeSheet *ads, Scene *sce, float ypos, float yscale_fac, int saction_flag)
 {
-  DLRBT_Tree keys;
+  struct AnimKeylist *keylist = ED_keylist_create();
 
   saction_flag &= ~SACTION_SHOW_EXTREMES;
 
-  BLI_dlrbTree_init(&keys);
-
-  scene_to_keylist(ads, sce, &keys, saction_flag);
+  scene_to_keylist(ads, sce, keylist, saction_flag);
 
-  draw_keylist(v2d, &keys, ypos, yscale_fac, false, saction_flag);
+  draw_keylist(v2d, keylist, ypos, yscale_fac, false, saction_flag);
 
-  BLI_dlrbTree_free(&keys);
+  ED_keylist_free(keylist);
 }
 
 void draw_object_channel(
     View2D *v2d, bDopeSheet *ads, Object *ob, float ypos, float yscale_fac, int saction_flag)
 {
-  DLRBT_Tree keys;
+  struct AnimKeylist *keylist = ED_keylist_create();
 
   saction_flag &= ~SACTION_SHOW_EXTREMES;
 
-  BLI_dlrbTree_init(&keys);
-
-  ob_to_keylist(ads, ob, &keys, saction_flag);
+  ob_to_keylist(ads, ob, keylist, saction_flag);
 
-  draw_keylist(v2d, &keys, ypos, yscale_fac, false, saction_flag);
+  draw_keylist(v2d, keylist, ypos, yscale_fac, false, saction_flag);
 
-  BLI_dlrbTree_free(&keys);
+  ED_keylist_free(keylist);
 }
 
 void draw_fcurve_channel(
     View2D *v2d, AnimData *adt, FCurve *fcu, float ypos, float yscale_fac, int saction_flag)
 {
-  DLRBT_Tree keys;
+  struct AnimKeylist *keylist = ED_keylist_create();
 
   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);
+  fcurve_to_keylist(adt, fcu, keylist, saction_flag);
 
-  fcurve_to_keylist(adt, fcu, &keys, saction_flag);
+  draw_keylist(v2d, keylist, ypos, yscale_fac, locked, saction_flag);
 
-  draw_keylist(v2d, &keys, ypos, yscale_fac, locked, saction_flag);
-
-  BLI_dlrbTree_free(&keys);
+  ED_keylist_free(keylist);
 }
 
 void draw_agroup_channel(
     View2D *v2d, AnimData *adt, bActionGroup *agrp, float ypos, float yscale_fac, int saction_flag)
 {
-  DLRBT_Tree keys;
+  struct AnimKeylist *keylist = ED_keylist_create();
 
   bool locked = (agrp->flag & AGRP_PROTECTED) ||
                 ((adt && adt->action) && ID_IS_LINKED(adt->action));
 
-  BLI_dlrbTree_init(&keys);
-
-  agroup_to_keylist(adt, agrp, &keys, saction_flag);
+  agroup_to_keylist(adt, agrp, keylist, saction_flag);
 
-  draw_keylist(v2d, &keys, ypos, yscale_fac, locked, saction_flag);
+  draw_keylist(v2d, keylist, ypos, yscale_fac, locked, saction_flag);
 
-  BLI_dlrbTree_free(&keys);
+  ED_keylist_free(keylist);
 }
 
 void draw_action_channel(
     View2D *v2d, AnimData *adt, bAction *act, float ypos, float yscale_fac, int saction_flag)
 {
-  DLRBT_Tree keys;
+  struct AnimKeylist *keylist = ED_keylist_create();
 
   bool locked = (act && ID_IS_LINKED(act));
 
   saction_flag &= ~SACTION_SHOW_EXTREMES;
 
-  BLI_dlrbTree_init(&keys);
-
-  action_to_keylist(adt, act, &keys, saction_flag);
+  action_to_keylist(adt, act, keylist, saction_flag);
 
-  draw_keylist(v2d, &keys, ypos, yscale_fac, locked, saction_flag);
+  draw_keylist(v2d, keylist, ypos, yscale_fac, locked, saction_flag);
 
-  BLI_dlrbTree_free(&keys);
+  ED_keylist_free(keylist);
 }
 
 void draw_gpencil_channel(
     View2D *v2d, bDopeSheet *ads, bGPdata *gpd, float ypos, float yscale_fac, int saction_flag)
 {
-  DLRBT_Tree keys;
+  struct AnimKeylist *keylist = ED_keylist_create();
 
   saction_flag &= ~SACTION_SHOW_EXTREMES;
 
-  BLI_dlrbTree_init(&keys);
+  gpencil_to_keylist(ads, gpd, keylist, false);
 
-  gpencil_to_keylist(ads, gpd, &keys, false);
+  draw_keylist(v2d, keylist, ypos, yscale_fac, false, saction_flag);
 
-  draw_keylist(v2d, &keys, ypos, yscale_fac, false, saction_flag);
-
-  BLI_dlrbTree_free(&keys);
+  ED_keylist_free(keylist);
 }
 
 void draw_gpl_channel(
     View2D *v2d, bDopeSheet *ads, bGPDlayer *gpl, float ypos, float yscale_fac, int saction_flag)
 {
-  DLRBT_Tree keys;
+  struct AnimKeylist *keylist = ED_keylist_create();
 
   bool locked = (gpl->flag & GP_LAYER_LOCKED) != 0;
 
-  BLI_dlrbTree_init(&keys);
-
-  gpl_to_keylist(ads, gpl, &keys);
+  gpl_to_keylist(ads, gpl, keylist);
 
-  draw_keylist(v2d, &keys, ypos, yscale_fac, locked, saction_flag);
+  draw_keylist(v2d, keylist, ypos, yscale_fac, locked, saction_flag);
 
-  BLI_dlrbTree_free(&keys);
+  ED_keylist_free(keylist);
 }
 
 void draw_masklay_channel(View2D *v2d,
@@ -515,15 +497,13 @@ void draw_masklay_channel(View2D *v2d,
                           float yscale_fac,
                           int saction_flag)
 {
-  DLRBT_Tree keys;
+  struct AnimKeylist *keylist = ED_keylist_create();
 
   bool locked = (masklay->flag & MASK_LAYERFLAG_LOCKED) != 0;
 
-  BLI_dlrbTree_init(&keys);
-
-  mask_to_keylist(ads, masklay, &keys);
+  mask_to_keylist(ads, masklay, keylist);
 
-  draw_keylist(v2d, &keys, ypos, yscale_fac, locked, saction_flag);
+  draw_keylist(v2d, keylist, ypos, yscale_fac, locked, saction_flag);
 
-  BLI_dlrbTree_free(&keys);
+  ED_keylist_free(keylist);
 }
diff --git a/source/blender/editors/animation/keyframes_keylist.c b/source/blender/editors/animation/keyframes_keylist.c
index 47ed2b56300..8f0f6d753be 100644
--- a/source/blender/editors/animation/keyframes_keylist.c
+++ b/source/blender/editors/animation/keyframes_keylist.c
@@ -32,6 +32,7 @@
 
 #include "BLI_dlrbTree.h"
 #include "BLI_listbase.h"
+#include "BLI_range.h"
 #include "BLI_utildefines.h"
 
 #include "DNA_anim_types.h"
@@ -48,6 +49,83 @@
 
 /* *************************** Keyframe Processing *************************** */
 
+typedef struct AnimKeylist {
+  DLRBT_Tree keys;
+} AnimKeylist;
+
+static void ED_keylist_init(AnimKeylist *keylist)
+{
+  BLI_dlrbTree_init(&keylist->keys);
+}
+
+AnimKeylist *ED_keylist_create(void)
+{
+  AnimKeylist *keylist = MEM_callocN(sizeof(AnimKeylist), __func__);
+  ED_keylist_init(keylist);
+  return keylist;
+}
+
+void ED_keylist_free(AnimKeylist *keylist)
+{
+  BLI_assert(keylist);
+  BLI_dlrbTree_free(&keylist->keys);
+  MEM_freeN(keylist);
+}
+
+ActKeyColumn *ED_keylist_find_exact(const AnimKeylist *keylist, float cfra)
+{
+  return (ActKeyColumn *)BLI_dlrbTree_search_exact(&keylist->keys, compare_ak_cfraPtr, &cfra);
+}
+
+ActKeyColumn *ED_keylist_find_next(const AnimKeylist *keylist, float cfra)
+{
+  return (ActKeyColumn *)BLI_dlrbTree_search_next(&keylist->keys, compare_ak_cfraPtr, &cfra);
+}
+
+ActKeyColumn *ED_keylist_find_prev(const AnimKeylist *keylist, float cfra)
+{
+  return (ActKeyColumn *)BLI_dlrbTree_search_prev(&keylist->keys, compare_ak_cfraPtr, &cfra);
+}
+
+/* TODO(jbakker): Should we change this to use `ED_keylist_find_next(keys, min_fra)` and only check
+ * boundary of `max_fra`. */
+ActKeyColumn *ED_keylist_find_any_between(const AnimKeylist *keylist, float min_fra, float max_fra)
+{
+  for (ActKeyColumn *ak = keylist->keys.root; ak;
+       ak = (ak->cfra < min_fra) ? ak->right : ak->left) {
+    if (IN_RANGE(ak->cfra, min_fra, max_fra)) {
+      return ak;
+    }
+  }
+  return NULL;
+}
+
+bool ED_keylist_is_empty(const struct AnimKeylist *keylist)
+{
+  return keylist->keys.root == NULL;
+}
+
+const struct ListBase *ED_keylist_listbase(const AnimKeylist *keylist)
+{
+  return (ListBase *)&keylist->keys;
+}
+
+bool ED_keylist_frame_range(const struct AnimKeylist *keylist, Range2f *r_frame_range)
+{
+  BLI_assert(r_frame_range);
+
+  if (ED_keylist_is_empty(keylist)) {
+    return false;
+  }
+
+  const ActKeyColumn *first_column = (const ActKeyColumn *)keylist->keys.first;
+  r_frame_range->min = first_column->cfra;
+
+  const ActKeyColumn *last_column = (const ActKeyColumn *)keylist->keys.last;
+  r_frame_range->max = last_column->cfra;
+
+  return true;
+}
 /* ActKeyColumns (Keyframe Columns) ------------------------------------------ */
 
 BLI_INLINE bool is_cfra_eq(float a, float b)
@@ -323,33 +401,33 @@ static void nupdate_ak_masklayshape(void *node, void *data)
 /* --------------- */
 
 /* Add the given BezTriple to the given 'list' of Keyframes */
-static void add_bezt_to_keycolumns_list(DLRBT_Tree *keys, BezTripleChain *bezt)
+static void add_bezt_to_keycolumns_list(AnimKeylist *keylist, BezTripleChain *bezt)
 {
-  if (ELEM(NULL, keys, bezt)) {
+  if (ELEM(NULL, keylist, bezt)) {
     return;
   }
 
-  BLI_dlrbTree_add(keys, compare_ak_bezt, nalloc_ak_bezt, nupdate_ak_bezt, bezt);
+  BLI_dlrbTree_add(&keylist->keys, compare_ak_bezt, nalloc_ak_bezt, nupdate_ak_bezt, bezt);
 }
 
 /* Add the given GPencil Frame to the given 'list' of Keyframes */
-static void add_gpframe_to_keycolumns_list(DLRBT_Tree *keys, bGPDframe *gpf)
+static void add_gpframe_to_keycolumns_list(AnimKeylist *keylist, bGPDframe *gpf)
 {
-  if (ELEM(NULL, keys, gpf)) {
+  if (ELEM(NULL, keylist, gpf)) {
     return;
   }
 
-  BLI_dlrbTree_add(keys, compare_ak_gpframe, nalloc_ak_gpframe, nupdate_ak_gpframe, gpf);
+  BLI_dlrbTree_add(&keylist->keys, compare_ak_gpframe, nalloc_ak_gpframe, nupdate_ak_gpframe, gpf);
 }
 
 /* Add the given MaskLayerShape Frame to the given 'list' of Keyframes */
-static void add_masklay_to_keycolumns_list(DLRBT_Tree *keys, MaskLayerShape *masklay_shape)
+static void add_masklay_to_keycolumns_list(AnimKeylist *keylist, MaskLayerShape *masklay_shape)
 {
-  if (ELEM(NULL, keys, masklay_shape)) {
+  if (ELEM(NULL, keylist, masklay_shape)) {
     return;
   }
 
-  BLI_dlrbTree_add(keys,
+  BLI_dlrbTree_add(&keylist->keys,
                    compare_ak_masklayshape,
                    nalloc_ak_masklayshape,
                    nupdate_ak_masklayshape,
@@ -423,9 +501,9 @@ static void add_keyblock_info(ActKeyColumn *col, const ActKeyBlockInfo *block)
   }
 }
 
-static void add_bezt_to_keyblocks_list(DLRBT_Tree *keys, BezTriple *bezt, int bezt_len)
+static void add_bezt_to_keyblocks_list(AnimKeylist *keylist, BezTriple *bezt, int bezt_len)
 {
-  ActKeyColumn *col = keys->first;
+  ActKeyColumn *col = keylist->keys.first;
 
   if (bezt && bezt_len >= 2) {
     ActKeyBlockInfo block;
@@ -444,7 +522,7 @@ static void add_bezt_to_keyblocks_list(DLRBT_Tree *keys, BezTriple *bezt, int be
         /* Backtrack to find the right location. */
         if (is_cfra_lt(bezt[1].vec[1][0], col->cfra)) {
           ActKeyColumn *newcol = (ActKeyColumn *)BLI_dlrbTree_search_exact(
-              keys, compare_ak_cfraPtr, &bezt[1].vec[1][0]);
+              &keylist->keys, compare_ak_cfraPtr, &bezt[1].vec[1][0]);
 
           if (newcol != NULL) {
             col = newcol;
@@ -486,22 +564,22 @@ static void add_bezt_to_keyblocks_list(DLRBT_Tree *keys, BezTriple *bezt, int be
  * 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 bezt_len)
+static void update_keyblocks(AnimKeylist *keylist, BezTriple *bezt, int bezt_len)
 {
   /* Recompute the prev/next linked list. */
-  BLI_dlrbTree_linkedlist_sync(keys);
+  BLI_dlrbTree_linkedlist_sync(&keylist->keys);
 
   /* Find the curve count */
   int max_curve = 0;
 
-  LISTBASE_FOREACH (ActKeyColumn *, col, keys) {
+  LISTBASE_FOREACH (ActKeyColumn *, col, &keylist->keys) {
     max_curve = MAX2(max_curve, col->totcurve);
   }
 
   /* Propagate blocks to inserted keys */
   ActKeyColumn *prev_ready = NULL;
 
-  LISTBASE_FOREACH (ActKeyColumn *, col, keys) {
+  LISTBASE_FOREACH (ActKeyColumn *, col, &keylist->keys) {
     /* Pre-existing column. */
     if (col->totcurve > 0) {
       prev_ready = col;
@@ -516,7 +594,7 @@ static void update_keyblocks(DLRBT_Tree *keys, BezTriple *bezt, int bezt_len)
   }
 
   /* Add blocks on top */
-  add_bezt_to_keyblocks_list(keys, bezt, bezt_len);
+  add_bezt_to_keyblocks_list(keylist, bezt, bezt_len);
 }
 
 /* --------- */
@@ -540,7 +618,7 @@ int actkeyblock_get_valid_hold(ActKeyColumn *ac)
 
 /* *************************** Keyframe List Conversions *************************** */
 
-void summary_to_keylist(bAnimContext *ac, DLRBT_Tree *keys, int saction_flag)
+void summary_to_keylist(bAnimContext *ac, AnimKeylist *keylist, int saction_flag)
 {
   if (ac) {
     ListBase anim_data = {NULL, NULL};
@@ -561,13 +639,13 @@ void summary_to_keylist(bAnimContext *ac, DLRBT_Tree *keys, int saction_flag)
 
       switch (ale->datatype) {
         case ALE_FCURVE:
-          fcurve_to_keylist(ale->adt, ale->data, keys, saction_flag);
+          fcurve_to_keylist(ale->adt, ale->data, keylist, saction_flag);
           break;
         case ALE_MASKLAY:
-          mask_to_keylist(ac->ads, ale->data, keys);
+          mask_to_keylist(ac->ads, ale->data, keylist);
           break;
         case ALE_GPFRAME:
-          gpl_to_keylist(ac->ads, ale->data, keys);
+          gpl_to_keylist(ac->ads, ale->data, keylist);
           break;
         default:
           // printf("%s: datatype %d unhandled\n", __func__, ale->datatype);
@@ -579,7 +657,7 @@ void summary_to_keylist(bAnimContext *ac, DLRBT_Tree *keys, int saction_flag)
   }
 }
 
-void scene_to_keylist(bDopeSheet *ads, Scene *sce, DLRBT_Tree *keys, int saction_flag)
+void scene_to_keylist(bDopeSheet *ads, Scene *sce, AnimKeylist *keylist, int saction_flag)
 {
   bAnimContext ac = {NULL};
   ListBase anim_data = {NULL, NULL};
@@ -608,13 +686,13 @@ void scene_to_keylist(bDopeSheet *ads, Scene *sce, DLRBT_Tree *keys, int saction
 
   /* 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, saction_flag);
+    fcurve_to_keylist(ale->adt, ale->data, keylist, saction_flag);
   }
 
   ANIM_animdata_freelist(&anim_data);
 }
 
-void ob_to_keylist(bDopeSheet *ads, Object *ob, DLRBT_Tree *keys, int saction_flag)
+void ob_to_keylist(bDopeSheet *ads, Object *ob, AnimKeylist *keylist, int saction_flag)
 {
   bAnimContext ac = {NULL};
   ListBase anim_data = {NULL, NULL};
@@ -646,7 +724,7 @@ void ob_to_keylist(bDopeSheet *ads, Object *ob, DLRBT_Tree *keys, int saction_fl
 
   /* 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, saction_flag);
+    fcurve_to_keylist(ale->adt, ale->data, keylist, saction_flag);
   }
 
   ANIM_animdata_freelist(&anim_data);
@@ -654,7 +732,7 @@ void ob_to_keylist(bDopeSheet *ads, Object *ob, DLRBT_Tree *keys, int saction_fl
 
 void cachefile_to_keylist(bDopeSheet *ads,
                           CacheFile *cache_file,
-                          DLRBT_Tree *keys,
+                          AnimKeylist *keylist,
                           int saction_flag)
 {
   if (cache_file == NULL) {
@@ -680,13 +758,13 @@ void cachefile_to_keylist(bDopeSheet *ads,
 
   /* loop through each F-Curve, grabbing the keyframes */
   LISTBASE_FOREACH (bAnimListElem *, ale, &anim_data) {
-    fcurve_to_keylist(ale->adt, ale->data, keys, saction_flag);
+    fcurve_to_keylist(ale->adt, ale->data, keylist, saction_flag);
   }
 
   ANIM_animdata_freelist(&anim_data);
 }
 
-void fcurve_to_keylist(AnimData *adt, FCurve *fcu, DLRBT_Tree *keys, int saction_flag)
+void fcurve_to_keylist(AnimData *adt, FCurve *fcu, AnimKeylist *keylist, int saction_flag)
 {
   if (fcu && fcu->totvert && fcu->bezt) {
     /* apply NLA-mapping (if applicable) */
@@ -710,11 +788,11 @@ void fcurve_to_keylist(AnimData *adt, FCurve *fcu, DLRBT_Tree *keys, int saction
         chain.next = (v + 1 < fcu->totvert) ? &fcu->bezt[v + 1] : is_cyclic ? &fcu->bezt[1] : NULL;
       }
 
-      add_bezt_to_keycolumns_list(keys, &chain);
+      add_bezt_to_keycolumns_list(keylist, &chain);
     }
 
     /* Update keyblocks. */
-    update_keyblocks(keys, fcu->bezt, fcu->totvert);
+    update_keyblocks(keylist, fcu->bezt, fcu->totvert);
 
     /* unapply NLA-mapping if applicable */
     if (adt) {
@@ -723,71 +801,71 @@ void fcurve_to_keylist(AnimData *adt, FCurve *fcu, DLRBT_Tree *keys, int saction
   }
 }
 
-void agroup_to_keylist(AnimData *adt, bActionGroup *agrp, DLRBT_Tree *keys, int saction_flag)
+void agroup_to_keylist(AnimData *adt, bActionGroup *agrp, AnimKeylist *keylist, int saction_flag)
 {
   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, saction_flag);
+      fcurve_to_keylist(adt, fcu, keylist, saction_flag);
     }
   }
 }
 
-void action_to_keylist(AnimData *adt, bAction *act, DLRBT_Tree *keys, int saction_flag)
+void action_to_keylist(AnimData *adt, bAction *act, AnimKeylist *keylist, int saction_flag)
 {
   FCurve *fcu;
 
   if (act) {
     /* loop through F-Curves */
     for (fcu = act->curves.first; fcu; fcu = fcu->next) {
-      fcurve_to_keylist(adt, fcu, keys, saction_flag);
+      fcurve_to_keylist(adt, fcu, keylist, saction_flag);
     }
   }
 }
 
-void gpencil_to_keylist(bDopeSheet *ads, bGPdata *gpd, DLRBT_Tree *keys, const bool active)
+void gpencil_to_keylist(bDopeSheet *ads, bGPdata *gpd, AnimKeylist *keylist, const bool active)
 {
   bGPDlayer *gpl;
 
-  if (gpd && keys) {
+  if (gpd && keylist) {
     /* for now, just aggregate out all the frames, but only for visible layers */
     for (gpl = gpd->layers.last; gpl; gpl = gpl->prev) {
       if ((gpl->flag & GP_LAYER_HIDE) == 0) {
         if ((!active) || ((active) && (gpl->flag & GP_LAYER_SELECT))) {
-          gpl_to_keylist(ads, gpl, keys);
+          gpl_to_keylist(ads, gpl, keylist);
         }
       }
     }
   }
 }
 
-void gpl_to_keylist(bDopeSheet *UNUSED(ads), bGPDlayer *gpl, DLRBT_Tree *keys)
+void gpl_to_keylist(bDopeSheet *UNUSED(ads), bGPDlayer *gpl, AnimKeylist *keylist)
 {
   bGPDframe *gpf;
 
-  if (gpl && keys) {
+  if (gpl && keylist) {
     /* 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);
+      add_gpframe_to_keycolumns_list(keylist, gpf);
     }
 
-    update_keyblocks(keys, NULL, 0);
+    update_keyblocks(keylist, NULL, 0);
   }
 }
 
-void mask_to_keylist(bDopeSheet *UNUSED(ads), MaskLayer *masklay, DLRBT_Tree *keys)
+void mask_to_keylist(bDopeSheet *UNUSED(ads), MaskLayer *masklay, AnimKeylist *keylist)
 {
   MaskLayerShape *masklay_shape;
 
-  if (masklay && keys) {
+  if (masklay && keylist) {
     for (masklay_shape = masklay->splines_shapes.first; masklay_shape;
          masklay_shape = masklay_shape->next) {
-      add_masklay_to_keycolumns_list(keys, masklay_shape);
+      add_masklay_to_keycolumns_list(keylist, masklay_shape);
     }
 
-    update_keyblocks(keys, NULL, 0);
+    update_keyblocks(keylist, NULL, 0);
   }
 }
diff --git a/source/blender/editors/armature/pose_lib.c b/source/blender/editors/armature/pose_lib.c
index cb70b2810d1..646356e7a45 100644
--- a/source/blender/editors/armature/pose_lib.c
+++ b/source/blender/editors/armature/pose_lib.c
@@ -304,8 +304,6 @@ static int poselib_sanitize_exec(bContext *C, wmOperator *op)
 {
   Object *ob = get_poselib_object(C);
   bAction *act = (ob) ? ob->poselib : NULL;
-  DLRBT_Tree keys;
-  ActKeyColumn *ak;
   TimeMarker *marker, *markern;
 
   /* validate action */
@@ -315,11 +313,11 @@ static int poselib_sanitize_exec(bContext *C, wmOperator *op)
   }
 
   /* determine which frames have keys */
-  BLI_dlrbTree_init(&keys);
-  action_to_keylist(NULL, act, &keys, 0);
+  struct AnimKeylist *keylist = ED_keylist_create();
+  action_to_keylist(NULL, act, keylist, 0);
 
   /* for each key, make sure there is a corresponding pose */
-  for (ak = keys.first; ak; ak = ak->next) {
+  LISTBASE_FOREACH (const ActKeyColumn *, ak, ED_keylist_listbase(keylist)) {
     /* check if any pose matches this */
     /* TODO: don't go looking through the list like this every time... */
     for (marker = act->markers.first; marker; marker = marker->next) {
@@ -356,7 +354,7 @@ static int poselib_sanitize_exec(bContext *C, wmOperator *op)
   }
 
   /* free temp memory */
-  BLI_dlrbTree_free(&keys);
+  ED_keylist_free(keylist);
 
   /* send notifiers for this - using keyframe editing notifiers, since action
    * may be being shown in anim editors as active action
diff --git a/source/blender/editors/armature/pose_slide.c b/source/blender/editors/armature/pose_slide.c
index 38f562ebf25..238799650a0 100644
--- a/source/blender/editors/armature/pose_slide.c
+++ b/source/blender/editors/armature/pose_slide.c
@@ -146,7 +146,7 @@ typedef struct tPoseSlideOp {
   /** links between posechannels and f-curves for all the pose objects. */
   ListBase pfLinks;
   /** binary tree for quicker searching for keyframes (when applicable) */
-  DLRBT_Tree keys;
+  struct AnimKeylist *keylist;
 
   /** current frame number - global time */
   int cframe;
@@ -277,7 +277,7 @@ static int pose_slide_init(bContext *C, wmOperator *op, ePoseSlide_Modes mode)
 
   /* Do basic initialize of RB-BST used for finding keyframes, but leave the filling of it up
    * to the caller of this (usually only invoke() will do it, to make things more efficient). */
-  BLI_dlrbTree_init(&pso->keys);
+  pso->keylist = ED_keylist_create();
 
   /* Initialize numeric input. */
   initNumInput(&pso->num);
@@ -306,7 +306,7 @@ static void pose_slide_exit(bContext *C, wmOperator *op)
   poseAnim_mapping_free(&pso->pfLinks);
 
   /* Free RB-BST for keyframes (if it contained data). */
-  BLI_dlrbTree_free(&pso->keys);
+  ED_keylist_free(pso->keylist);
 
   if (pso->ob_data_array != NULL) {
     MEM_freeN(pso->ob_data_array);
@@ -971,60 +971,56 @@ static int pose_slide_invoke_common(bContext *C, wmOperator *op, const wmEvent *
     /* Do this for each F-Curve. */
     for (ld = pfl->fcurves.first; ld; ld = ld->next) {
       FCurve *fcu = (FCurve *)ld->data;
-      fcurve_to_keylist(pfl->ob->adt, fcu, &pso->keys, 0);
+      fcurve_to_keylist(pfl->ob->adt, fcu, pso->keylist, 0);
     }
   }
 
   /* Cancel if no keyframes found. */
-  if (pso->keys.root) {
-    ActKeyColumn *ak;
-    float cframe = (float)pso->cframe;
-
-    /* Firstly, check if the current frame is a keyframe. */
-    ak = (ActKeyColumn *)BLI_dlrbTree_search_exact(&pso->keys, compare_ak_cfraPtr, &cframe);
-
-    if (ak == NULL) {
-      /* Current frame is not a keyframe, so search. */
-      ActKeyColumn *pk = (ActKeyColumn *)BLI_dlrbTree_search_prev(
-          &pso->keys, compare_ak_cfraPtr, &cframe);
-      ActKeyColumn *nk = (ActKeyColumn *)BLI_dlrbTree_search_next(
-          &pso->keys, compare_ak_cfraPtr, &cframe);
-
-      /* New set the frames. */
-      /* Prev frame. */
-      pso->prevFrame = (pk) ? (pk->cfra) : (pso->cframe - 1);
-      RNA_int_set(op->ptr, "prev_frame", pso->prevFrame);
-      /* Next frame. */
-      pso->nextFrame = (nk) ? (nk->cfra) : (pso->cframe + 1);
-      RNA_int_set(op->ptr, "next_frame", pso->nextFrame);
-    }
-    else {
-      /* Current frame itself is a keyframe, so just take keyframes on either side. */
-      /* Prev frame. */
-      pso->prevFrame = (ak->prev) ? (ak->prev->cfra) : (pso->cframe - 1);
-      RNA_int_set(op->ptr, "prev_frame", pso->prevFrame);
-      /* Next frame. */
-      pso->nextFrame = (ak->next) ? (ak->next->cfra) : (pso->cframe + 1);
-      RNA_int_set(op->ptr, "next_frame", pso->nextFrame);
-    }
-
-    /* Apply NLA mapping corrections so the frame look-ups work. */
-    for (uint ob_index = 0; ob_index < pso->objects_len; ob_index++) {
-      tPoseSlideObject *ob_data = &pso->ob_data_array[ob_index];
-      if (ob_data->valid) {
-        ob_data->prevFrameF = BKE_nla_tweakedit_remap(
-            ob_data->ob->adt, pso->prevFrame, NLATIME_CONVERT_UNMAP);
-        ob_data->nextFrameF = BKE_nla_tweakedit_remap(
-            ob_data->ob->adt, pso->nextFrame, NLATIME_CONVERT_UNMAP);
-      }
-    }
-  }
-  else {
+  if (ED_keylist_is_empty(pso->keylist)) {
     BKE_report(op->reports, RPT_ERROR, "No keyframes to slide between");
     pose_slide_exit(C, op);
     return OPERATOR_CANCELLED;
   }
 
+  float cframe = (float)pso->cframe;
+
+  /* Firstly, check if the current frame is a keyframe. */
+  const ActKeyColumn *ak = ED_keylist_find_exact(pso->keylist, cframe);
+
+  if (ak == NULL) {
+    /* Current frame is not a keyframe, so search. */
+    const ActKeyColumn *pk = ED_keylist_find_prev(pso->keylist, cframe);
+    const ActKeyColumn *nk = ED_keylist_find_next(pso->keylist, cframe);
+
+    /* New set the frames. */
+    /* Prev frame. */
+    pso->prevFrame = (pk) ? (pk->cfra) : (pso->cframe - 1);
+    RNA_int_set(op->ptr, "prev_frame", pso->prevFrame);
+    /* Next frame. */
+    pso->nextFrame = (nk) ? (nk->cfra) : (pso->cframe + 1);
+    RNA_int_set(op->ptr, "next_frame", pso->nextFrame);
+  }
+  else {
+    /* Current frame itself is a keyframe, so just take keyframes on either side. */
+    /* Prev frame. */
+    pso->prevFrame = (ak->prev) ? (ak->prev->cfra) : (pso->cframe - 1);
+    RNA_int_set(op->ptr, "prev_frame", pso->prevFrame);
+    /* Next frame. */
+    pso->nextFrame = (ak->next) ? (ak->next->cfra) : (pso->cframe + 1);
+    RNA_int_set(op->ptr, "next_frame", pso->nextFrame);
+  }
+
+  /* Apply NLA mapping corrections so the frame look-ups work. */
+  for (uint ob_index = 0; ob_index < pso->objects_len; ob_index++) {
+    tPoseSlideObject *ob_data = &pso->ob_data_array[ob_index];
+    if (ob_data->valid) {
+      ob_data->prevFrameF = BKE_nla_tweakedit_remap(
+          ob_data->ob->adt, pso->prevFrame, NLATIME_CONVERT_UNMAP);
+      ob_data->nextFrameF = BKE_nla_tweakedit_remap(
+          ob_data->ob->adt, pso->nextFrame, NLATIME_CONVERT_UNMAP);
+    }
+  }
+
   /* Initial apply for operator. */
   /* TODO: need to calculate factor for initial round too. */
   if (!ELEM(pso->mode, POSESLIDE_PUSH_REST, POSESLIDE_RELAX_REST)) {
@@ -1705,26 +1701,22 @@ typedef union tPosePropagate_ModeData {
  */
 static float pose_propagate_get_boneHoldEndFrame(tPChanFCurveLink *pfl, float startFrame)
 {
-  DLRBT_Tree keys;
+  struct AnimKeylist *keylist = ED_keylist_create();
 
   Object *ob = pfl->ob;
   AnimData *adt = ob->adt;
   LinkData *ld;
   float endFrame = startFrame;
 
-  /* Set up optimized data-structures for searching for relevant keyframes + holds. */
-  BLI_dlrbTree_init(&keys);
-
   for (ld = pfl->fcurves.first; ld; ld = ld->next) {
     FCurve *fcu = (FCurve *)ld->data;
-    fcurve_to_keylist(adt, fcu, &keys, 0);
+    fcurve_to_keylist(adt, fcu, keylist, 0);
   }
 
   /* 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
    */
-  ActKeyColumn *ab = (ActKeyColumn *)BLI_dlrbTree_search_exact(
-      &keys, compare_ak_cfraPtr, &startFrame);
+  ActKeyColumn *ab = ED_keylist_find_exact(keylist, 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
@@ -1735,11 +1727,11 @@ static float pose_propagate_get_boneHoldEndFrame(tPChanFCurveLink *pfl, float st
    */
   if (ab == NULL) {
     /* We've got case 1, so try the one after. */
-    ab = (ActKeyColumn *)BLI_dlrbTree_search_next(&keys, compare_ak_cfraPtr, &startFrame);
+    ab = ED_keylist_find_next(keylist, 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);
+      ab = ED_keylist_find_prev(keylist, startFrame);
     }
   }
 
@@ -1774,7 +1766,7 @@ static float pose_propagate_get_boneHoldEndFrame(tPChanFCurveLink *pfl, float st
   }
 
   /* Free temp memory. */
-  BLI_dlrbTree_free(&keys);
+  ED_keylist_free(keylist);
 
   /* Return the end frame we've found. */
   return endFrame;
diff --git a/source/blender/editors/include/ED_keyframes_keylist.h b/source/blender/editors/include/ED_keyframes_keylist.h
index be3eac66771..92b57b89cf8 100644
--- a/source/blender/editors/include/ED_keyframes_keylist.h
+++ b/source/blender/editors/include/ED_keyframes_keylist.h
@@ -37,9 +37,12 @@ struct Scene;
 struct bAnimContext;
 struct bDopeSheet;
 struct bGPDlayer;
+struct Range2f;
 
 /* ****************************** Base Structs ****************************** */
 
+struct AnimKeylist;
+
 /* Information about the stretch of time from current to the next column */
 typedef struct ActKeyBlockInfo {
   /* Combination of flags from all curves. */
@@ -133,49 +136,61 @@ typedef enum eKeyframeExtremeDrawOpts {
 
 /* ******************************* Methods ****************************** */
 
+struct AnimKeylist *ED_keylist_create(void);
+void ED_keylist_free(struct AnimKeylist *keylist);
+struct ActKeyColumn *ED_keylist_find_exact(const struct AnimKeylist *keylist, float cfra);
+struct ActKeyColumn *ED_keylist_find_next(const struct AnimKeylist *keylist, float cfra);
+struct ActKeyColumn *ED_keylist_find_prev(const struct AnimKeylist *keylist, float cfra);
+struct ActKeyColumn *ED_keylist_find_any_between(const struct AnimKeylist *keylist,
+                                                 float min_fra,
+                                                 float max_fra);
+bool ED_keylist_is_empty(const struct AnimKeylist *keylist);
+const struct ListBase /* ActKeyColumn */ *ED_keylist_listbase(const struct AnimKeylist *keylist);
+bool ED_keylist_frame_range(const struct AnimKeylist *keylist, struct Range2f *r_frame_range);
+
 /* Key-data Generation --------------- */
 
 /* F-Curve */
 void fcurve_to_keylist(struct AnimData *adt,
                        struct FCurve *fcu,
-                       struct DLRBT_Tree *keys,
+                       struct AnimKeylist *keys,
                        int saction_flag);
 /* Action Group */
 void agroup_to_keylist(struct AnimData *adt,
                        struct bActionGroup *agrp,
-                       struct DLRBT_Tree *keys,
+                       struct AnimKeylist *keys,
                        int saction_flag);
 /* Action */
 void action_to_keylist(struct AnimData *adt,
                        struct bAction *act,
-                       struct DLRBT_Tree *keys,
+                       struct AnimKeylist *keys,
                        int saction_flag);
 /* Object */
 void ob_to_keylist(struct bDopeSheet *ads,
                    struct Object *ob,
-                   struct DLRBT_Tree *keys,
+                   struct AnimKeylist *keys,
                    int saction_flag);
 /* Cache File */
 void cachefile_to_keylist(struct bDopeSheet *ads,
                           struct CacheFile *cache_file,
-                          struct DLRBT_Tree *keys,
+                          struct AnimKeylist *keys,
                           int saction_flag);
 /* Scene */
 void scene_to_keylist(struct bDopeSheet *ads,
                       struct Scene *sce,
-                      struct DLRBT_Tree *keys,
+                      struct AnimKeylist *keys,
                       int saction_flag);
 /* DopeSheet Summary */
-void summary_to_keylist(struct bAnimContext *ac, struct DLRBT_Tree *keys, int saction_flag);
+void summary_to_keylist(struct bAnimContext *ac, struct AnimKeylist *keys, int saction_flag);
 /* Grease Pencil datablock summary */
 void gpencil_to_keylist(struct bDopeSheet *ads,
                         struct bGPdata *gpd,
-                        struct DLRBT_Tree *keys,
+                        struct AnimKeylist *keys,
                         const bool active);
 /* Grease Pencil Layer */
-void gpl_to_keylist(struct bDopeSheet *ads, struct bGPDlayer *gpl, struct DLRBT_Tree *keys);
+void gpl_to_keylist(struct bDopeSheet *ads, struct bGPDlayer *gpl, struct AnimKeylist *keys);
 /* Mask */
-void mask_to_keylist(struct bDopeSheet *ads, struct MaskLayer *masklay, struct DLRBT_Tree *keys);
+void mask_to_keylist(struct bDopeSheet *ads, struct MaskLayer *masklay, struct AnimKeylist *keys);
 
 /* ActKeyColumn API ---------------- */
 /* Comparator callback used for ActKeyColumns and cframe float-value pointer */
diff --git a/source/blender/editors/screen/screen_ops.c b/source/blender/editors/screen/screen_ops.c
index f172e22ea56..107466a8a0b 100644
--- a/source/blender/editors/screen/screen_ops.c
+++ b/source/blender/editors/screen/screen_ops.c
@@ -3057,8 +3057,7 @@ static int keyframe_jump_exec(bContext *C, wmOperator *op)
   float cfra = (float)(CFRA);
 
   /* init binarytree-list for getting keyframes */
-  DLRBT_Tree keys;
-  BLI_dlrbTree_init(&keys);
+  struct AnimKeylist *keylist = ED_keylist_create();
 
   /* seed up dummy dopesheet context with flags to perform necessary filtering */
   if ((scene->flag & SCE_KEYS_NO_SELONLY) == 0) {
@@ -3067,14 +3066,14 @@ static int keyframe_jump_exec(bContext *C, wmOperator *op)
   }
 
   /* populate tree with keyframe nodes */
-  scene_to_keylist(&ads, scene, &keys, 0);
+  scene_to_keylist(&ads, scene, keylist, 0);
 
   if (ob) {
-    ob_to_keylist(&ads, ob, &keys, 0);
+    ob_to_keylist(&ads, ob, keylist, 0);
 
     if (ob->type == OB_GPENCIL) {
       const bool active = !(scene->flag & SCE_KEYS_NO_SELONLY);
-      gpencil_to_keylist(&ads, ob->data, &keys, active);
+      gpencil_to_keylist(&ads, ob->data, keylist, active);
     }
   }
 
@@ -3082,17 +3081,17 @@ static int keyframe_jump_exec(bContext *C, wmOperator *op)
     Mask *mask = CTX_data_edit_mask(C);
     if (mask) {
       MaskLayer *masklay = BKE_mask_layer_active(mask);
-      mask_to_keylist(&ads, masklay, &keys);
+      mask_to_keylist(&ads, masklay, keylist);
     }
   }
 
   /* find matching keyframe in the right direction */
   ActKeyColumn *ak;
   if (next) {
-    ak = (ActKeyColumn *)BLI_dlrbTree_search_next(&keys, compare_ak_cfraPtr, &cfra);
+    ak = ED_keylist_find_next(keylist, cfra);
   }
   else {
-    ak = (ActKeyColumn *)BLI_dlrbTree_search_prev(&keys, compare_ak_cfraPtr, &cfra);
+    ak = ED_keylist_find_prev(keylist, cfra);
   }
 
   while ((ak != NULL) && (done == false)) {
@@ -3113,7 +3112,7 @@ static int keyframe_jump_exec(bContext *C, wmOperator *op)
   }
 
   /* free temp stuff */
-  BLI_dlrbTree_free(&keys);
+  ED_keylist_free(keylist);
 
   /* any success? */
   if (done == false) {
diff --git a/source/blender/editors/space_action/action_select.c b/source/blender/editors/space_action/action_select.c
index 59d2063ea84..64ccca2c907 100644
--- a/source/blender/editors/space_action/action_select.c
+++ b/source/blender/editors/space_action/action_select.c
@@ -93,7 +93,7 @@ static bAnimListElem *actkeys_find_list_element_at_position(bAnimContext *ac,
 }
 
 static void actkeys_list_element_to_keylist(bAnimContext *ac,
-                                            DLRBT_Tree *anim_keys,
+                                            struct AnimKeylist *keylist,
                                             bAnimListElem *ale)
 {
   AnimData *adt = ANIM_nla_mapping_get(ac, ale);
@@ -107,44 +107,44 @@ static void actkeys_list_element_to_keylist(bAnimContext *ac,
     switch (ale->datatype) {
       case ALE_SCE: {
         Scene *scene = (Scene *)ale->key_data;
-        scene_to_keylist(ads, scene, anim_keys, 0);
+        scene_to_keylist(ads, scene, keylist, 0);
         break;
       }
       case ALE_OB: {
         Object *ob = (Object *)ale->key_data;
-        ob_to_keylist(ads, ob, anim_keys, 0);
+        ob_to_keylist(ads, ob, keylist, 0);
         break;
       }
       case ALE_ACT: {
         bAction *act = (bAction *)ale->key_data;
-        action_to_keylist(adt, act, anim_keys, 0);
+        action_to_keylist(adt, act, keylist, 0);
         break;
       }
       case ALE_FCURVE: {
         FCurve *fcu = (FCurve *)ale->key_data;
-        fcurve_to_keylist(adt, fcu, anim_keys, 0);
+        fcurve_to_keylist(adt, fcu, keylist, 0);
         break;
       }
     }
   }
   else if (ale->type == ANIMTYPE_SUMMARY) {
     /* dopesheet summary covers everything */
-    summary_to_keylist(ac, anim_keys, 0);
+    summary_to_keylist(ac, keylist, 0);
   }
   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, 0);
+    agroup_to_keylist(adt, agrp, keylist, 0);
   }
   else if (ale->type == ANIMTYPE_GPLAYER) {
     /* TODO: why don't we just give gplayers key_data too? */
     bGPDlayer *gpl = (bGPDlayer *)ale->data;
-    gpl_to_keylist(ads, gpl, anim_keys);
+    gpl_to_keylist(ads, gpl, keylist);
   }
   else if (ale->type == ANIMTYPE_MASKLAYER) {
     /* TODO: why don't we just give masklayers key_data too? */
     MaskLayer *masklay = (MaskLayer *)ale->data;
-    mask_to_keylist(ads, masklay, anim_keys);
+    mask_to_keylist(ads, masklay, keylist);
   }
 }
 
@@ -160,9 +160,8 @@ static void actkeys_find_key_in_list_element(bAnimContext *ac,
 
   View2D *v2d = &ac->region->v2d;
 
-  DLRBT_Tree anim_keys;
-  BLI_dlrbTree_init(&anim_keys);
-  actkeys_list_element_to_keylist(ac, &anim_keys, ale);
+  struct AnimKeylist *keylist = ED_keylist_create();
+  actkeys_list_element_to_keylist(ac, keylist, ale);
 
   AnimData *adt = ANIM_nla_mapping_get(ac, ale);
 
@@ -174,22 +173,21 @@ static void actkeys_find_key_in_list_element(bAnimContext *ac,
   float xmin = UI_view2d_region_to_view_x(v2d, region_x - (int)key_hsize);
   float xmax = UI_view2d_region_to_view_x(v2d, region_x + (int)key_hsize);
 
-  for (ActKeyColumn *ak = anim_keys.root; ak; ak = (ak->cfra < xmin) ? ak->right : ak->left) {
-    if (IN_RANGE(ak->cfra, xmin, xmax)) {
-      /* set the frame to use, and apply inverse-correction for NLA-mapping
-       * so that the frame will get selected by the selection functions without
-       * requiring to map each frame once again...
-       */
-      *r_selx = BKE_nla_tweakedit_remap(adt, ak->cfra, NLATIME_CONVERT_UNMAP);
-      *r_frame = ak->cfra;
-      *r_found = true;
-      *r_is_selected = (ak->sel & SELECT) != 0;
-      break;
-    }
+  const ActKeyColumn *ak = ED_keylist_find_any_between(keylist, xmin, xmax);
+  if (ak) {
+
+    /* set the frame to use, and apply inverse-correction for NLA-mapping
+     * so that the frame will get selected by the selection functions without
+     * requiring to map each frame once again...
+     */
+    *r_selx = BKE_nla_tweakedit_remap(adt, ak->cfra, NLATIME_CONVERT_UNMAP);
+    *r_frame = ak->cfra;
+    *r_found = true;
+    *r_is_selected = (ak->sel & SELECT) != 0;
   }
 
   /* cleanup temporary lists */
-  BLI_dlrbTree_free(&anim_keys);
+  ED_keylist_free(keylist);
 }
 
 static void actkeys_find_key_at_position(bAnimContext *ac,
diff --git a/source/blender/editors/space_nla/nla_draw.c b/source/blender/editors/space_nla/nla_draw.c
index c96047da0c8..2bf4c7d4344 100644
--- a/source/blender/editors/space_nla/nla_draw.c
+++ b/source/blender/editors/space_nla/nla_draw.c
@@ -35,6 +35,7 @@
 
 #include "BLI_blenlib.h"
 #include "BLI_dlrbTree.h"
+#include "BLI_range.h"
 #include "BLI_utildefines.h"
 
 #include "BKE_context.h"
@@ -95,12 +96,16 @@ void nla_action_get_color(AnimData *adt, bAction *act, float color[4])
 static void nla_action_draw_keyframes(
     View2D *v2d, AnimData *adt, bAction *act, float y, float ymin, float ymax)
 {
+  if (act == NULL) {
+    return;
+  }
+
   /* get a list of the keyframes with NLA-scaling applied */
-  DLRBT_Tree keys;
-  BLI_dlrbTree_init(&keys);
-  action_to_keylist(adt, act, &keys, 0);
+  struct AnimKeylist *keylist = ED_keylist_create();
+  action_to_keylist(adt, act, keylist, 0);
 
-  if (ELEM(NULL, act, keys.first)) {
+  if (ED_keylist_is_empty(keylist)) {
+    ED_keylist_free(keylist);
     return;
   }
 
@@ -122,15 +127,16 @@ static void nla_action_draw_keyframes(
   /* - draw a rect from the first to the last frame (no extra overlaps for now)
    *   that is slightly stumpier than the track background (hardcoded 2-units here)
    */
-  float f1 = ((ActKeyColumn *)keys.first)->cfra;
-  float f2 = ((ActKeyColumn *)keys.last)->cfra;
 
-  immRectf(pos_id, f1, ymin + 2, f2, ymax - 2);
+  Range2f frame_range;
+  ED_keylist_frame_range(keylist, &frame_range);
+  immRectf(pos_id, frame_range.min, ymin + 2, frame_range.max, ymax - 2);
   immUnbindProgram();
 
   /* Count keys before drawing. */
   /* NOTE: It's safe to cast #DLRBT_Tree, as it's designed to degrade down to a #ListBase. */
-  uint key_len = BLI_listbase_count((ListBase *)&keys);
+  const ListBase *keys = ED_keylist_listbase(keylist);
+  uint key_len = BLI_listbase_count(keys);
 
   if (key_len > 0) {
     format = immVertexFormat();
@@ -151,7 +157,7 @@ static void nla_action_draw_keyframes(
     /* - disregard the selection status of keyframes so they draw a certain way
      * - size is 6.0f which is smaller than the editable keyframes, so that there is a distinction
      */
-    LISTBASE_FOREACH (ActKeyColumn *, ak, &keys) {
+    LISTBASE_FOREACH (const ActKeyColumn *, ak, keys) {
       draw_keyframe_shape(ak->cfra,
                           y,
                           6.0f,
@@ -174,7 +180,7 @@ static void nla_action_draw_keyframes(
   }
 
   /* free icons */
-  BLI_dlrbTree_free(&keys);
+  ED_keylist_free(keylist);
 }
 
 /* Strip Markers ------------------------ */