btree.c File Reference

#include "lib/trace.h"
#include "lib/errno.h"
#include "lib/finject.h"
#include "lib/misc.h"
#include "be/alloc.h"
#include "be/btree.h"
#include "be/btree_internal.h"
#include "be/seg.h"
#include "be/tx.h"

Include dependency graph for btree.c:

Go to the source code of this file.

Data Structures
struct	btree_node_pos

Macros
#define	M0_TRACE_SUBSYSTEM   M0_TRACE_SUBSYS_BTREE

Enumerations
enum	{ BTREE_ALLOC_SHIFT = 0 }
enum	btree_save_optype { BTREE_SAVE_INSERT, BTREE_SAVE_UPDATE, BTREE_SAVE_OVERWRITE }
enum	position_t { P_LEFT = -1, P_RIGHT = 1 }

Functions
static struct m0_be_op__btree *	op_tree (struct m0_be_op *op)
static struct m0_rwlock *	btree_rwlock (struct m0_be_btree *tree)
static struct be_btree_key_val *	be_btree_search (struct m0_be_btree *btree, void *key)
static void	btree_root_set (struct m0_be_btree *btree, struct m0_be_bnode *new_root)
static void	btree_op_fill (struct m0_be_op *op, struct m0_be_btree *btree, struct m0_be_tx *tx, enum m0_be_btree_op optype, struct m0_be_btree_anchor *anchor)
static struct m0_be_allocator *	tree_allocator (const struct m0_be_btree *btree)
static void	mem_free (const struct m0_be_btree *btree, struct m0_be_tx *tx, void *ptr)
static void	mem_update (const struct m0_be_btree *btree, struct m0_be_tx *tx, void *ptr, m0_bcount_t size)
static void *	mem_alloc (const struct m0_be_btree *btree, struct m0_be_tx *tx, m0_bcount_t size, uint64_t zonemask)
static void	btree_mem_alloc_credit (const struct m0_be_btree *btree, m0_bcount_t size, struct m0_be_tx_credit *accum)
static void	btree_mem_free_credit (const struct m0_be_btree *btree, m0_bcount_t size, struct m0_be_tx_credit *accum)
static m0_bcount_t	be_btree_ksize (const struct m0_be_btree *btree, const void *key)
static m0_bcount_t	be_btree_vsize (const struct m0_be_btree *btree, const void *data)
static int	be_btree_compare (const struct m0_be_btree *btree, const void *key0, const void *key1)
static int	key_lt (const struct m0_be_btree *btree, const void *key0, const void *key1)
static int	key_gt (const struct m0_be_btree *btree, const void *key0, const void *key1)
static int	key_eq (const struct m0_be_btree *btree, const void *key0, const void *key1)
static struct m0_be_bnode *	be_btree_node_alloc (const struct m0_be_btree *btree, struct m0_be_tx *tx)
static void	btree_node_free (struct m0_be_bnode *node, const struct m0_be_btree *btree, struct m0_be_tx *tx)
static void	btree_pair_release (struct m0_be_btree *btree, struct m0_be_tx *tx, struct be_btree_key_val *kv)
static struct btree_node_pos	be_btree_get_btree_node (struct m0_be_btree_cursor *it, const void *key, bool slant)
static void	be_btree_delete_key_from_node (struct m0_be_btree *tree, struct m0_be_tx *tx, struct btree_node_pos *node_pos)
static void	be_btree_move_parent_key (struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_bnode *node, enum position_t pos, unsigned int index)
static void	be_btree_get_max_key_pos (struct m0_be_bnode *node, struct btree_node_pos *pos)
static void	be_btree_get_min_key_pos (struct m0_be_bnode *node, struct btree_node_pos *pos)
static int	iter_prepare (struct m0_be_bnode *node, bool print)
static bool	btree_backlink_invariant (const struct m0_be_btree_backlink *h, const struct m0_be_seg *seg, const uint64_t *parent)
static bool	btree_node_invariant (const struct m0_be_btree *btree, const struct m0_be_bnode *node, bool root)
static bool	btree_node_subtree_invariant (const struct m0_be_btree *btree, const struct m0_be_bnode *node)
static bool	btree_invariant (const struct m0_be_btree *btree)
static void	btree_node_update (struct m0_be_bnode *node, const struct m0_be_btree *btree, struct m0_be_tx *tx)
static void	btree_node_keyval_update (struct m0_be_bnode *node, const struct m0_be_btree *btree, struct m0_be_tx *tx, unsigned int index)
static void	btree_create (struct m0_be_btree *btree, struct m0_be_tx *tx, const struct m0_fid *btree_fid)
static void	be_btree_set_node_params (struct m0_be_bnode *p_node, unsigned int num_active_key, unsigned int level, bool isleaf)
static void	be_btree_split_child (struct m0_be_btree *btree, struct m0_be_tx *tx, struct m0_be_bnode *parent, unsigned int index)
static void	be_btree_insert_into_nonfull (struct m0_be_btree *btree, struct m0_be_tx *tx, struct m0_be_bnode *node, struct be_btree_key_val *kv)
static void	be_btree_insert_newkey (struct m0_be_btree *btree, struct m0_be_tx *tx, struct be_btree_key_val *kv)
static void	be_btree_shift_key_vals (struct m0_be_bnode *dest, struct m0_be_bnode *src, unsigned int start_index, unsigned int key_src_offset, unsigned int key_dest_offset, unsigned int child_src_offset, unsigned int child_dest_offset, unsigned int stop_index)
static struct m0_be_bnode *	be_btree_merge_siblings (struct m0_be_tx *tx, struct m0_be_btree *tree, struct m0_be_bnode *parent, unsigned int idx)
static void	be_btree_move_parent_key_to_right_child (struct m0_be_bnode *parent, struct m0_be_bnode *lch, struct m0_be_bnode *rch, unsigned int idx)
static void	be_btree_move_parent_key_to_left_child (struct m0_be_bnode *parent, struct m0_be_bnode *lch, struct m0_be_bnode *rch, unsigned int idx)
static void	btree_node_child_delete (struct m0_be_btree *btree, struct m0_be_tx *tx, struct m0_be_bnode *node, unsigned index, struct btree_node_pos *child, bool left)
static int	be_btree_delete_key (struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_bnode *bnode, void *key)
static void	node_push (struct m0_be_btree_cursor *it, struct m0_be_bnode *node, int idx)
static struct m0_be_bnode *	node_pop (struct m0_be_btree_cursor *it, int *idx)
static void	be_btree_destroy (struct m0_be_btree *btree, struct m0_be_tx *tx)
static void	btree_truncate (struct m0_be_btree *btree, struct m0_be_tx *tx, m0_bcount_t limit)
static void *	be_btree_get_max_key (struct m0_be_btree *tree)
static void *	be_btree_get_min_key (struct m0_be_btree *tree)
static void	btree_save (struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_op *op, const struct m0_buf *key, const struct m0_buf *val, struct m0_be_btree_anchor *anchor, enum btree_save_optype optype, uint64_t zonemask)
M0_INTERNAL void	m0_be_btree_init (struct m0_be_btree *tree, struct m0_be_seg *seg, const struct m0_be_btree_kv_ops *ops)
M0_INTERNAL void	m0_be_btree_fini (struct m0_be_btree *tree)
M0_INTERNAL void	m0_be_btree_create (struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_op *op, const struct m0_fid *btree_fid)
M0_INTERNAL void	m0_be_btree_destroy (struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_op *op)
M0_INTERNAL void	m0_be_btree_truncate (struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_op *op, m0_bcount_t limit)
static void	btree_node_alloc_credit (const struct m0_be_btree *tree, struct m0_be_tx_credit *accum)
static void	btree_node_update_credit (struct m0_be_tx_credit *accum, m0_bcount_t nr)
static void	btree_node_free_credit (const struct m0_be_btree *tree, struct m0_be_tx_credit *accum)
static void	btree_credit (const struct m0_be_btree *tree, struct m0_be_tx_credit *accum)
static void	btree_rebalance_credit (const struct m0_be_btree *tree, struct m0_be_tx_credit *accum)
static void	kv_insert_credit (const struct m0_be_btree *tree, m0_bcount_t ksize, m0_bcount_t vsize, struct m0_be_tx_credit *accum)
static void	kv_delete_credit (const struct m0_be_btree *tree, m0_bcount_t ksize, m0_bcount_t vsize, struct m0_be_tx_credit *accum)
static void	btree_node_split_child_credit (const struct m0_be_btree *tree, struct m0_be_tx_credit *accum)
static void	insert_credit (const struct m0_be_btree *tree, m0_bcount_t nr, m0_bcount_t ksize, m0_bcount_t vsize, struct m0_be_tx_credit *accum, bool use_current_height)
static void	delete_credit (const struct m0_be_btree *tree, m0_bcount_t nr, m0_bcount_t ksize, m0_bcount_t vsize, struct m0_be_tx_credit *accum)
M0_INTERNAL void	m0_be_btree_insert_credit (const struct m0_be_btree *tree, m0_bcount_t nr, m0_bcount_t ksize, m0_bcount_t vsize, struct m0_be_tx_credit *accum)
M0_INTERNAL void	m0_be_btree_insert_credit2 (const struct m0_be_btree *tree, m0_bcount_t nr, m0_bcount_t ksize, m0_bcount_t vsize, struct m0_be_tx_credit *accum)
M0_INTERNAL void	m0_be_btree_delete_credit (const struct m0_be_btree *tree, m0_bcount_t nr, m0_bcount_t ksize, m0_bcount_t vsize, struct m0_be_tx_credit *accum)
M0_INTERNAL void	m0_be_btree_update_credit (const struct m0_be_btree *tree, m0_bcount_t nr, m0_bcount_t vsize, struct m0_be_tx_credit *accum)
M0_INTERNAL void	m0_be_btree_update_credit2 (const struct m0_be_btree *tree, m0_bcount_t nr, m0_bcount_t ksize, m0_bcount_t vsize, struct m0_be_tx_credit *accum)
M0_INTERNAL void	m0_be_btree_create_credit (const struct m0_be_btree *tree, m0_bcount_t nr, struct m0_be_tx_credit *accum)
static int	btree_count_items (struct m0_be_btree *tree, m0_bcount_t *ksize, m0_bcount_t *vsize)
M0_INTERNAL void	m0_be_btree_destroy_credit (struct m0_be_btree *tree, struct m0_be_tx_credit *accum)
M0_INTERNAL void	m0_be_btree_clear_credit (struct m0_be_btree *tree, struct m0_be_tx_credit *fixed_part, struct m0_be_tx_credit *single_record, m0_bcount_t *records_nr)
static void	be_btree_insert (struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_op *op, const struct m0_buf *key, const struct m0_buf *val, struct m0_be_btree_anchor *anchor, uint64_t zonemask)
M0_INTERNAL void	m0_be_btree_save (struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_op *op, const struct m0_buf *key, const struct m0_buf *val, bool overwrite)
M0_INTERNAL void	m0_be_btree_insert (struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_op *op, const struct m0_buf *key, const struct m0_buf *val)
M0_INTERNAL void	m0_be_btree_update (struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_op *op, const struct m0_buf *key, const struct m0_buf *val)
M0_INTERNAL void	m0_be_btree_delete (struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_op *op, const struct m0_buf *key)
static void	be_btree_lookup (struct m0_be_btree *tree, struct m0_be_op *op, const struct m0_buf *key_in, struct m0_buf *key_out, struct m0_buf *value)
M0_INTERNAL void	m0_be_btree_lookup (struct m0_be_btree *tree, struct m0_be_op *op, const struct m0_buf *key, struct m0_buf *value)
M0_INTERNAL void	m0_be_btree_lookup_slant (struct m0_be_btree *tree, struct m0_be_op *op, struct m0_buf *key, struct m0_buf *value)
M0_INTERNAL void	m0_be_btree_maxkey (struct m0_be_btree *tree, struct m0_be_op *op, struct m0_buf *out)
M0_INTERNAL void	m0_be_btree_minkey (struct m0_be_btree *tree, struct m0_be_op *op, struct m0_buf *out)
M0_INTERNAL void	m0_be_btree_update_inplace (struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_op *op, const struct m0_buf *key, struct m0_be_btree_anchor *anchor)
M0_INTERNAL void	m0_be_btree_insert_inplace (struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_op *op, const struct m0_buf *key, struct m0_be_btree_anchor *anchor, uint64_t zonemask)
M0_INTERNAL void	m0_be_btree_save_inplace (struct m0_be_btree *tree, struct m0_be_tx *tx, struct m0_be_op *op, const struct m0_buf *key, struct m0_be_btree_anchor *anchor, bool overwrite, uint64_t zonemask)
M0_INTERNAL void	m0_be_btree_lookup_inplace (struct m0_be_btree *tree, struct m0_be_op *op, const struct m0_buf *key, struct m0_be_btree_anchor *anchor)
M0_INTERNAL void	m0_be_btree_release (struct m0_be_tx *tx, struct m0_be_btree_anchor *anchor)
static void	print_single_node (struct m0_be_bnode *node)
M0_INTERNAL void	m0_be_btree_cursor_init (struct m0_be_btree_cursor *cur, struct m0_be_btree *btree)
M0_INTERNAL void	m0_be_btree_cursor_fini (struct m0_be_btree_cursor *cursor)
M0_INTERNAL void	m0_be_btree_cursor_get (struct m0_be_btree_cursor *cur, const struct m0_buf *key, bool slant)
M0_INTERNAL int	m0_be_btree_cursor_get_sync (struct m0_be_btree_cursor *cur, const struct m0_buf *key, bool slant)
static int	btree_cursor_seek (struct m0_be_btree_cursor *cur, void *key)
M0_INTERNAL int	m0_be_btree_cursor_first_sync (struct m0_be_btree_cursor *cur)
M0_INTERNAL int	m0_be_btree_cursor_last_sync (struct m0_be_btree_cursor *cur)
M0_INTERNAL void	m0_be_btree_cursor_next (struct m0_be_btree_cursor *cur)
M0_INTERNAL void	m0_be_btree_cursor_prev (struct m0_be_btree_cursor *cur)
M0_INTERNAL int	m0_be_btree_cursor_next_sync (struct m0_be_btree_cursor *cur)
M0_INTERNAL int	m0_be_btree_cursor_prev_sync (struct m0_be_btree_cursor *cur)
M0_INTERNAL void	m0_be_btree_cursor_put (struct m0_be_btree_cursor *cursor)
M0_INTERNAL void	m0_be_btree_cursor_kv_get (struct m0_be_btree_cursor *cur, struct m0_buf *key, struct m0_buf *val)
M0_INTERNAL bool	m0_be_btree_is_empty (struct m0_be_btree *tree)
M0_INTERNAL void	btree_dbg_print (struct m0_be_btree *tree)

Variables
enum { ... }	M0_XCA_DOMAIN
M0_INTERNAL const struct m0_fid_type	m0_btree_fid_type