diff options
| author | Darrick J. Wong <djwong@kernel.org> | 2023-04-12 04:00:36 +0200 |
|---|---|---|
| committer | Darrick J. Wong <djwong@kernel.org> | 2023-04-12 04:00:36 +0200 |
| commit | 6772fcc8890ae34595253fcfb8196c1aea65e111 (patch) | |
| tree | 8fffedcd2b5955ab0bf80bf50bae83e799bda0c5 /fs/xfs/scrub/bitmap.h | |
| parent | xfs: drop the _safe behavior from the xbitmap foreach macro (diff) | |
| download | linux-6772fcc8890ae34595253fcfb8196c1aea65e111.tar.xz linux-6772fcc8890ae34595253fcfb8196c1aea65e111.zip | |
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>
Diffstat (limited to 'fs/xfs/scrub/bitmap.h')
| -rw-r--r-- | fs/xfs/scrub/bitmap.h | 11 |
1 files changed, 4 insertions, 7 deletions
diff --git a/fs/xfs/scrub/bitmap.h b/fs/xfs/scrub/bitmap.h index 01e37173dc34..2ec4e1f3f24c 100644 --- a/fs/xfs/scrub/bitmap.h +++ b/fs/xfs/scrub/bitmap.h @@ -6,19 +6,14 @@ #ifndef __XFS_SCRUB_BITMAP_H__ #define __XFS_SCRUB_BITMAP_H__ -struct xbitmap_range { - struct list_head list; - uint64_t start; - uint64_t len; -}; - struct xbitmap { - struct list_head list; + struct rb_root_cached xb_root; }; void xbitmap_init(struct xbitmap *bitmap); void xbitmap_destroy(struct xbitmap *bitmap); +int xbitmap_clear(struct xbitmap *bitmap, uint64_t start, uint64_t len); int xbitmap_set(struct xbitmap *bitmap, uint64_t start, uint64_t len); int xbitmap_disunion(struct xbitmap *bitmap, struct xbitmap *sub); int xbitmap_set_btcur_path(struct xbitmap *bitmap, @@ -42,4 +37,6 @@ typedef int (*xbitmap_walk_bits_fn)(uint64_t bit, void *priv); int xbitmap_walk_bits(struct xbitmap *bitmap, xbitmap_walk_bits_fn fn, void *priv); +bool xbitmap_empty(struct xbitmap *bitmap); + #endif /* __XFS_SCRUB_BITMAP_H__ */ |