[00/21] bcachefs: eytzinger code

Message

Andreas Gruenbacher Jan. 28, 2025, 4:38 p.m. UTC

Kent, to continue our discussion from last November, I've gone through
more parts of the eytzinger code and as a result, here are some patches
for you to consider.

What I've not looked at are the eytzinger_to_inorder and
inorder_to_eytzinger functions, as well as the implementation of sort.
Those functions could use a bit more documentation, but the code iself
looks reasonable.


Shuah, I've also had a quick look at converting the tests into kernel
selftests, but that hasn't gone very far because of the lack of support
for basic functions like __fls(), __ffs(), ffz(), and
rounddown_pow_of_two() in selftests.  Are there any plans for making
those kinds of primitives generally available to selftests?


Thanks,
Andreas

Andreas Gruenbacher (21):
  bcachefs: remove dead code in is_aligned
  bcachefs: bch2_blacklist_entries_gc cleanup
  bcachefs: Run the eytzinger tests on modprobe
  bcachefs: EYTZINGER_DEBUG fix
  bcachefs: eytzinger self tests: eytzinger0_for_each loop cleanups
  bcachefs: eytzinger self tests: missing newline termination
  bcachefs: eytzinger self tests: fix cmp_u16 typo
  bcachefs: eytzinger[01]_test improvement
  bcachefs: eytzinger0_find_test improvement
  bcachefs: add eytzinger0_for_each_prev
  bcachefs: improve the eytzinger0_find_le tests
  bcachefs: convert eytzinger0_find to be 1-based
  bcachefs: convert eytzinger0_find_le to be 1-based
  bcachefs: simplify eytzinger0_find_le
  bcachefs: add eytzinger0_find_gt tests
  bcachefs: implement eytzinger0_find_gt directly
  bcachefs: add eytzinger0_find_ge tests
  bcachefs: implement eytzinger0_find_ge directly
  bcachefs: convert eytzinger sort to be 1-based (1)
  bcachefs: convert eytzinger sort to be 1-based (2)
  bcachefs: eytzinger1_{next,prev} cleanup

 fs/bcachefs/eytzinger.c             |  89 +++++++-------
 fs/bcachefs/eytzinger.h             |  99 +++++++--------
 fs/bcachefs/journal_seq_blacklist.c |   7 +-
 fs/bcachefs/super.c                 |   5 +
 fs/bcachefs/util.c                  | 183 +++++++++++++++++++++-------
 fs/bcachefs/util.h                  |   4 +
 6 files changed, 240 insertions(+), 147 deletions(-)