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

4 files changed, 203 insertions, 147 deletions

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);
   }
 }