I don't quite understand the spacing of these blocks (this one and similar ones below). Does this mean that ED_keylist_prepare_for_direct_access() belongs more to the creation fo the keylist, rather than to the code that needs the direct access? I'd expect to opposite.

To me it would make sense to even have draw_keylist() call ED_keylist_prepare_for_direct_access(); after all, calling it more than once for the same keylist won't hurt.

const, also next function.

This needs a comment to explain what it's for.

Keys don't have a length. This "keys" probably means something else, then, but that's not clear when you read this struct from top to bottom.

Given that the runtime field is a struct and not a pointer, this struct always "has" a runtime. Maybe is_runtime_initialised or something along those lines is better?

So a field called "keys" contains "key columns"? Just call it key_columns then.

What does init mean?

What is "building"? And why are the keys built? I think that "When building" and "After building" need a comma, to separate subclause from main clause ("After building, the keys are ....")

What does this ListBase contain? How can it contain individual keys?

Why is there an index called index and another one called i? Can't they both be index?

Add a comment that explains this performs a binary search. The code is a lot easier to follow when you know what it's supposed to be doing.

const

const

(A - C < B - C) is the same as (A < B), so this expression can be simplified. Also one set of parentheses can be removed.

Also, a comment that explains why this comparison is necessary would be good. If you want to ensure best_result is the one closest to cfra, the comparison needs the subtraction, but then misses an fabsf() call.

There is a lot of commonality between the previous function and this one. Wouldn't it be possible to abstract out the binary search?

At the minimum, add a comment that explains why this is not simply ED_keylist_find_next(keylist, cfra)->prev.

This also needs BLI_assert_msg(...) because otherwise the value stored here isn't trustworthy.

I think this would be easier to read when the has_runtime cases are split up:

ActKeyColumn *first_column;
ActKeyColumn *last_column;
if (keylist->has_runtime) {
  first_column = &keylist->runtime.keys[0];
  last_column = &keylist->runtime.keys[keylist->keys_len - 1];
}
else {
  first_column = keylist->init.keys.first;
  last_column = keylist->init.keys.last;
}
r_frame_range->min = first_column->cfra;
r_frame_range->max = last_column->cfra;

Why is this doing a linear search instead of the binary search of the other functions?

Why don't these comparisons use is_cfra_lt()?

Using the "last accessed column" here looks like tight coupling with other functions. What is expected of that column? Why is it a good idea to walk from there? This needs to be documented in the code.

This needs a message. Why is it bad to call this function when it has a runtime?

What is this commented-out code? I've seen it in other places as well. I think that given the fact that is_cfra_lt() doesn't define a strict ordering (there are values where both is_cfra_lt(A, B) and is_cfra_lt(B, A) are true) it's better to just keep this a plain else.

Any reason this is a uint64_t and not a size_t?