linux/fs/bcachefs/bkey_sort.c

// SPDX-License-Identifier: GPL-2.0
#include "bcachefs.h"
#include "bkey_buf.h"
#include "bkey_cmp.h"
#include "bkey_sort.h"
#include "bset.h"
#include "extents.h"

sort_cmp_fn;

static inline bool sort_iter_end(struct sort_iter *iter)
{ … }

static inline void sort_iter_sift(struct sort_iter *iter, unsigned from,
				  sort_cmp_fn cmp)
{ … }

static inline void sort_iter_sort(struct sort_iter *iter, sort_cmp_fn cmp)
{ … }

static inline struct bkey_packed *sort_iter_peek(struct sort_iter *iter)
{ … }

static inline void sort_iter_advance(struct sort_iter *iter, sort_cmp_fn cmp)
{ … }

static inline struct bkey_packed *sort_iter_next(struct sort_iter *iter,
						 sort_cmp_fn cmp)
{ … }

/*
 * If keys compare equal, compare by pointer order:
 */
static inline int key_sort_fix_overlapping_cmp(const struct btree *b,
					       const struct bkey_packed *l,
					       const struct bkey_packed *r)
{ … }

static inline bool should_drop_next_key(struct sort_iter *iter)
{ … }

struct btree_nr_keys
bch2_key_sort_fix_overlapping(struct bch_fs *c, struct bset *dst,
			      struct sort_iter *iter)
{ … }

/* Sort + repack in a new format: */
struct btree_nr_keys
bch2_sort_repack(struct bset *dst, struct btree *src,
		 struct btree_node_iter *src_iter,
		 struct bkey_format *out_f,
		 bool filter_whiteouts)
{ … }

static inline int keep_unwritten_whiteouts_cmp(const struct btree *b,
				const struct bkey_packed *l,
				const struct bkey_packed *r)
{ … }

#include "btree_update_interior.h"

/*
 * For sorting in the btree node write path: whiteouts not in the unwritten
 * whiteouts area are dropped, whiteouts in the unwritten whiteouts area are
 * dropped if overwritten by real keys:
 */
unsigned bch2_sort_keys_keep_unwritten_whiteouts(struct bkey_packed *dst, struct sort_iter *iter)
{ … }

/*
 * Main sort routine for compacting a btree node in memory: we always drop
 * whiteouts because any whiteouts that need to be written are in the unwritten
 * whiteouts area:
 */
unsigned bch2_sort_keys(struct bkey_packed *dst, struct sort_iter *iter)
{ … }