Differential D28677 Diff 83996 sys/contrib/openzfs/module/avl/avl.c

Changeset View

Standalone View

sys/contrib/openzfs/module/avl/avl.c

Show First 20 Lines • Show All 486 Lines • ▼ Show 20 Lines
{		{
avl_node_t *node;		avl_node_t *node;
avl_node_t *parent = AVL_INDEX2NODE(where);		avl_node_t *parent = AVL_INDEX2NODE(where);
int old_balance;		int old_balance;
int new_balance;		int new_balance;
int which_child = AVL_INDEX2CHILD(where);		int which_child = AVL_INDEX2CHILD(where);
size_t off = tree->avl_offset;		size_t off = tree->avl_offset;

ASSERT(tree);
#ifdef _LP64		#ifdef _LP64
ASSERT(((uintptr_t)new_data & 0x7) == 0);		ASSERT(((uintptr_t)new_data & 0x7) == 0);
#endif		#endif

node = AVL_DATA2NODE(new_data, off);		node = AVL_DATA2NODE(new_data, off);

/*		/*
* First, add the node to the tree at the indicated position.		* First, add the node to the tree at the indicated position.
▲ Show 20 Lines • Show All 170 Lines • ▼ Show 20 Lines	avl_remove(avl_tree_t tree, void data)
avl_node_t *node;		avl_node_t *node;
avl_node_t tmp;		avl_node_t tmp;
int old_balance;		int old_balance;
int new_balance;		int new_balance;
int left;		int left;
int right;		int right;
int which_child;		int which_child;
size_t off = tree->avl_offset;		size_t off = tree->avl_offset;

ASSERT(tree);

delete = AVL_DATA2NODE(data, off);		delete = AVL_DATA2NODE(data, off);

/*		/*
* Deletion is easiest with a node that has at most 1 child.		* Deletion is easiest with a node that has at most 1 child.
* We swap a node with 2 children with a sequentially valued		* We swap a node with 2 children with a sequentially valued
* neighbor node. That node will have at most 1 child. Note this		* neighbor node. That node will have at most 1 child. Note this
* has no effect on the ordering of the remaining nodes.		* has no effect on the ordering of the remaining nodes.
▲ Show 20 Lines • Show All 405 Lines • Show Last 20 Lines