xfs: convert xbitmap to interval tree
authorDarrick J. Wong <djwong@kernel.org>
Wed, 12 Apr 2023 02:00:36 +0000 (19:00 -0700)
committerDarrick J. Wong <djwong@kernel.org>
Wed, 12 Apr 2023 02:00:36 +0000 (19:00 -0700)
commit6772fcc8890ae34595253fcfb8196c1aea65e111
tree8fffedcd2b5955ab0bf80bf50bae83e799bda0c5
parent7296a6d6fb8fef515352dac5d8af2ffe7a78e5cf
xfs: convert xbitmap to interval tree

Convert the xbitmap code to use interval trees instead of linked lists.
This reduces the amount of coding required to handle the disunion
operation and in the future will make it easier to set bits in arbitrary
order yet later be able to extract maximally sized extents, which we'll
need for rebuilding certain structures.  We define our own interval tree
type so that it can deal with 64-bit indices even on 32-bit machines.

Signed-off-by: Darrick J. Wong <djwong@kernel.org>
Reviewed-by: Dave Chinner <dchinner@redhat.com>
fs/xfs/scrub/agheader_repair.c
fs/xfs/scrub/bitmap.c
fs/xfs/scrub/bitmap.h