linux/fs/bcachefs/eytzinger.h

/* SPDX-License-Identifier: GPL-2.0 */
#ifndef _EYTZINGER_H
#define _EYTZINGER_H

#include <linux/bitops.h>
#include <linux/log2.h>

#ifdef EYTZINGER_DEBUG
#define EYTZINGER_BUG_ON
#else
#define EYTZINGER_BUG_ON(cond)
#endif

/*
 * Traversal for trees in eytzinger layout - a full binary tree layed out in an
 * array.
 *
 * Consider using an eytzinger tree any time you would otherwise be doing binary
 * search over an array. Binary search is a worst case scenario for branch
 * prediction and prefetching, but in an eytzinger tree every node's children
 * are adjacent in memory, thus we can prefetch children before knowing the
 * result of the comparison, assuming multiple nodes fit on a cacheline.
 *
 * Two variants are provided, for one based indexing and zero based indexing.
 *
 * Zero based indexing is more convenient, but one based indexing has better
 * alignment and thus better performance because each new level of the tree
 * starts at a power of two, and thus if element 0 was cacheline aligned, each
 * new level will be as well.
 */

static inline unsigned eytzinger1_child(unsigned i, unsigned child)
{}

static inline unsigned eytzinger1_left_child(unsigned i)
{}

static inline unsigned eytzinger1_right_child(unsigned i)
{}

static inline unsigned eytzinger1_first(unsigned size)
{}

static inline unsigned eytzinger1_last(unsigned size)
{}

/*
 * eytzinger1_next() and eytzinger1_prev() have the nice properties that
 *
 * eytzinger1_next(0) == eytzinger1_first())
 * eytzinger1_prev(0) == eytzinger1_last())
 *
 * eytzinger1_prev(eytzinger1_first()) == 0
 * eytzinger1_next(eytzinger1_last()) == 0
 */

static inline unsigned eytzinger1_next(unsigned i, unsigned size)
{}

static inline unsigned eytzinger1_prev(unsigned i, unsigned size)
{}

static inline unsigned eytzinger1_extra(unsigned size)
{}

static inline unsigned __eytzinger1_to_inorder(unsigned i, unsigned size,
					      unsigned extra)
{}

static inline unsigned __inorder_to_eytzinger1(unsigned i, unsigned size,
					       unsigned extra)
{}

static inline unsigned eytzinger1_to_inorder(unsigned i, unsigned size)
{}

static inline unsigned inorder_to_eytzinger1(unsigned i, unsigned size)
{}

#define eytzinger1_for_each(_i, _size)

/* Zero based indexing version: */

static inline unsigned eytzinger0_child(unsigned i, unsigned child)
{}

static inline unsigned eytzinger0_left_child(unsigned i)
{}

static inline unsigned eytzinger0_right_child(unsigned i)
{}

static inline unsigned eytzinger0_first(unsigned size)
{}

static inline unsigned eytzinger0_last(unsigned size)
{}

static inline unsigned eytzinger0_next(unsigned i, unsigned size)
{}

static inline unsigned eytzinger0_prev(unsigned i, unsigned size)
{}

static inline unsigned eytzinger0_extra(unsigned size)
{}

static inline unsigned __eytzinger0_to_inorder(unsigned i, unsigned size,
					       unsigned extra)
{}

static inline unsigned __inorder_to_eytzinger0(unsigned i, unsigned size,
					       unsigned extra)
{}

static inline unsigned eytzinger0_to_inorder(unsigned i, unsigned size)
{}

static inline unsigned inorder_to_eytzinger0(unsigned i, unsigned size)
{}

#define eytzinger0_for_each(_i, _size)

/* return greatest node <= @search, or -1 if not found */
static inline int eytzinger0_find_le(void *base, size_t nr, size_t size,
				     cmp_func_t cmp, const void *search)
{}

static inline int eytzinger0_find_gt(void *base, size_t nr, size_t size,
				     cmp_func_t cmp, const void *search)
{}

static inline int eytzinger0_find_ge(void *base, size_t nr, size_t size,
				     cmp_func_t cmp, const void *search)
{}

#define eytzinger0_find(base, nr, size, _cmp, search)

void eytzinger0_sort_r(void *, size_t, size_t,
		       cmp_r_func_t, swap_r_func_t, const void *);
void eytzinger0_sort(void *, size_t, size_t, cmp_func_t, swap_func_t);

#endif /* _EYTZINGER_H */