/*
 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
 */

/* Now we have all buffers that must be used in balancing of the tree 	*/
/* Further calculations can not cause schedule(), and thus the buffer 	*/
/* tree will be stable until the balancing will be finished 		*/
/* balance the tree according to the analysis made before,		*/
/* and using buffers obtained after all above.				*/

/**
 ** balance_leaf_when_delete
 ** balance_leaf
 ** do_balance
 **
 **/

#include <asm/uaccess.h>
#include <linux/time.h>
#include <linux/reiserfs_fs.h>
#include <linux/buffer_head.h>

#ifdef CONFIG_REISERFS_CHECK

struct tree_balance *cur_tb = NULL;	/* detects whether more than one
					   copy of tb exists as a means
					   of checking whether schedule
					   is interrupting do_balance */
#endif

inline void do_balance_mark_leaf_dirty(struct tree_balance *tb,
				       struct buffer_head *bh, int flag)
{
	journal_mark_dirty(tb->transaction_handle,
			   tb->transaction_handle->t_super, bh);
}

#define do_balance_mark_internal_dirty do_balance_mark_leaf_dirty
#define do_balance_mark_sb_dirty do_balance_mark_leaf_dirty

/* summary: 
 if deleting something ( tb->insert_size[0] < 0 )
   return(balance_leaf_when_delete()); (flag d handled here)
 else
   if lnum is larger than 0 we put items into the left node
   if rnum is larger than 0 we put items into the right node
   if snum1 is larger than 0 we put items into the new node s1
   if snum2 is larger than 0 we put items into the new node s2 
Note that all *num* count new items being created.

It would be easier to read balance_leaf() if each of these summary
lines was a separate procedure rather than being inlined.  I think
that there are many passages here and in balance_leaf_when_delete() in
which two calls to one procedure can replace two passages, and it
might save cache space and improve software maintenance costs to do so.  

Vladimir made the perceptive comment that we should offload most of
the decision making in this function into fix_nodes/check_balance, and
then create some sort of structure in tb that says what actions should
be performed by do_balance.

-Hans */

/* Balance leaf node in case of delete or cut: insert_size[0] < 0
 *
 * lnum, rnum can have values >= -1
 *	-1 means that the neighbor must be joined with S
 *	 0 means that nothing should be done with the neighbor
 *	>0 means to shift entirely or partly the specified number of items to the neighbor
 */
static int balance_leaf_when_delete(struct tree_balance *tb, int flag)
{
	struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
	int item_pos = PATH_LAST_POSITION(tb->tb_path);
	int pos_in_item = tb->tb_path->pos_in_item;
	struct buffer_info bi;
	int n;
	struct item_head *ih;

	RFALSE(tb->FR[0] && B_LEVEL(tb->FR[0]) != DISK_LEAF_NODE_LEVEL + 1,
	       "vs- 12000: level: wrong FR %z", tb->FR[0]);
	RFALSE(tb->blknum[0] > 1,
	       "PAP-12005: tb->blknum == %d, can not be > 1", tb->blknum[0]);
	RFALSE(!tb->blknum[0] && !PATH_H_PPARENT(tb->tb_path, 0),
	       "PAP-12010: tree can not be empty");

	ih = B_N_PITEM_HEAD(tbS0, item_pos);

	/* Delete or truncate the item */

	switch (flag) {
	case M_DELETE:		/* delete item in S[0] */

		RFALSE(ih_item_len(ih) + IH_SIZE != -tb->insert_size[0],
		       "vs-12013: mode Delete, insert size %d, ih to be deleted %h",
		       -tb->insert_size[0], ih);

		bi.tb = tb;
		bi.bi_bh = tbS0;
		bi.bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
		bi.bi_position = PATH_H_POSITION(tb->tb_path, 1);
		leaf_delete_items(&bi, 0, item_pos, 1, -1);

		if (!item_pos && tb->CFL[0]) {
			if (B_NR_ITEMS(tbS0)) {
				replace_key(tb, tb->CFL[0], tb->lkey[0], tbS0,
					    0);
			} else {
				if (!PATH_H_POSITION(tb->tb_path, 1))
					replace_key(tb, tb->CFL[0], tb->lkey[0],
						    PATH_H_PPARENT(tb->tb_path,
								   0), 0);
			}
		}

		RFALSE(!item_pos && !tb->CFL[0],
		       "PAP-12020: tb->CFL[0]==%p, tb->L[0]==%p", tb->CFL[0],
		       tb->L[0]);

		break;

	case M_CUT:{		/* cut item in S[0] */
			bi.tb = tb;
			bi.bi_bh = tbS0;
			bi.bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
			bi.bi_position = PATH_H_POSITION(tb->tb_path, 1);
			if (is_direntry_le_ih(ih)) {

				/* UFS unlink semantics are such that you can only delete one directory entry at a time. */
				/* when we cut a directory tb->insert_size[0] means number of entries to be cut (always 1) */
				tb->insert_size[0] = -1;
				leaf_cut_from_buffer(&bi, item_pos, pos_in_item,
						     -tb->insert_size[0]);

				RFALSE(!item_pos && !pos_in_item && !tb->CFL[0],
				       "PAP-12030: can not change delimiting key. CFL[0]=%p",
				       tb->CFL[0]);

				if (!item_pos && !pos_in_item && tb->CFL[0]) {
					replace_key(tb, tb->CFL[0], tb->lkey[0],
						    tbS0, 0);
				}
			} else {
				leaf_cut_from_buffer(&bi, item_pos, pos_in_item,
						     -tb->insert_size[0]);

				RFALSE(!ih_item_len(ih),
				       "PAP-12035: cut must leave non-zero dynamic length of item");
			}
			break;
		}

	default:
		print_cur_tb("12040");
		reiserfs_panic(tb->tb_sb,
			       "PAP-12040: balance_leaf_when_delete: unexpectable mode: %s(%d)",
			       (flag ==
				M_PASTE) ? "PASTE" : ((flag ==
						       M_INSERT) ? "INSERT" :
						      "UNKNOWN"), flag);
	}

	/* the rule is that no shifting occurs unless by shifting a node can be freed */
	n = B_NR_ITEMS(tbS0);
	if (tb->lnum[0]) {	/* L[0] takes part in balancing */
		if (tb->lnum[0] == -1) {	/* L[0] must be joined with S[0] */
			if (tb->rnum[0] == -1) {	/* R[0] must be also joined with S[0] */
				if (tb->FR[0] == PATH_H_PPARENT(tb->tb_path, 0)) {
					/* all contents of all the 3 buffers will be in L[0] */
					if (PATH_H_POSITION(tb->tb_path, 1) == 0
					    && 1 < B_NR_ITEMS(tb->FR[0]))
						replace_key(tb, tb->CFL[0],
							    tb->lkey[0],
							    tb->FR[0], 1);

					leaf_move_items(LEAF_FROM_S_TO_L, tb, n,
							-1, NULL);
					leaf_move_items(LEAF_FROM_R_TO_L, tb,
							B_NR_ITEMS(tb->R[0]),
							-1, NULL);

					reiserfs_invalidate_buffer(tb, tbS0);
					reiserfs_invalidate_buffer(tb,
								   tb->R[0]);

					return 0;
				}
				/* all contents of all the 3 buffers will be in R[0] */
				leaf_move_items(LEAF_FROM_S_TO_R, tb, n, -1,
						NULL);
				leaf_move_items(LEAF_FROM_L_TO_R, tb,
						B_NR_ITEMS(tb->L[0]), -1, NULL);

				/* right_delimiting_key is correct in R[0] */
				replace_key(tb, tb->CFR[0], tb->rkey[0],
					    tb->R[0], 0);

				reiserfs_invalidate_buffer(tb, tbS0);
				reiserfs_invalidate_buffer(tb, tb->L[0]);

				return -1;
			}

			RFALSE(tb->rnum[0] != 0,
			       "PAP-12045: rnum must be 0 (%d)", tb->rnum[0]);
			/* all contents of L[0] and S[0] will be in L[0] */
			leaf_shift_left(tb, n, -1);

			reiserfs_invalidate_buffer(tb, tbS0);

			return 0;
		}
		/* a part of contents of S[0] will be in L[0] and the rest part of S[0] will be in R[0] */

		RFALSE((tb->lnum[0] + tb->rnum[0] < n) ||
		       (tb->lnum[0] + tb->rnum[0] > n + 1),
		       "PAP-12050: rnum(%d) and lnum(%d) and item number(%d) in S[0] are not consistent",
		       tb->rnum[0], tb->lnum[0], n);
		RFALSE((tb->lnum[0] + tb->rnum[0] == n) &&
		       (tb->lbytes != -1 || tb->rbytes != -1),
		       "PAP-12055: bad rbytes (%d)/lbytes (%d) parameters when items are not split",
		       tb->rbytes, tb->lbytes);
		RFALSE((tb->lnum[0] + tb->rnum[0] == n + 1) &&
		       (tb->lbytes < 1 || tb->rbytes != -1),
		       "PAP-12060: bad rbytes (%d)/lbytes (%d) parameters when items are split",
		       tb->rbytes, tb->lbytes);

		leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
		leaf_shift_right(tb, tb->rnum[0], tb->rbytes);

		reiserfs_invalidate_buffer(tb, tbS0);

		return 0;
	}

	if (tb->rnum[0] == -1) {
		/* all contents of R[0] and S[0] will be in R[0] */
		leaf_shift_right(tb, n, -1);
		reiserfs_invalidate_buffer(tb, tbS0);
		return 0;
	}

	RFALSE(tb->rnum[0],
	       "PAP-12065: bad rnum parameter must be 0 (%d)", tb->rnum[0]);
	return 0;
}

static int balance_leaf(struct tree_balance *tb, struct item_head *ih,	/* item header of inserted item (this is on little endian) */
			const char *body,	/* body  of inserted item or bytes to paste */
			int flag,	/* i - insert, d - delete, c - cut, p - paste
					   (see comment to do_balance) */
			struct item_head *insert_key,	/* in our processing of one level we sometimes determine what
							   must be inserted into the next higher level.  This insertion
							   consists of a key or two keys and their corresponding
							   pointers */
			struct buffer_head **insert_ptr	/* inserted node-ptrs for the next level */
    )
{
	struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
	int item_pos = PATH_LAST_POSITION(tb->tb_path);	/*  index into the array of item headers in S[0] 
							   of the affected item */
	struct buffer_info bi;
	struct buffer_head *S_new[2];	/* new nodes allocated to hold what could not fit into S */
	int snum[2];		/* number of items that will be placed
				   into S_new (includes partially shifted
				   items) */
	int sbytes[2];		/* if an item is partially shifted into S_new then 
				   if it is a directory item 
				   it is the number of entries from the item that are shifted into S_new
				   else
				   it is the number of bytes from the item that are shifted into S_new
				 */
	int n, i;
	int ret_val;
	int pos_in_item;
	int zeros_num;

	PROC_INFO_INC(tb->tb_sb, balance_at[0]);

	/* Make balance in case insert_size[0] < 0 */
	if (tb->insert_size[0] < 0)
		return balance_leaf_when_delete(tb, flag);

	zeros_num = 0;
	if (flag == M_INSERT && body == 0)
		zeros_num = ih_item_len(ih);

	pos_in_item = tb->tb_path->pos_in_item;
	/* for indirect item pos_in_item is measured in unformatted node
	   pointers. Recalculate to bytes */
	if (flag != M_INSERT
	    && is_indirect_le_ih(B_N_PITEM_HEAD(tbS0, item_pos)))
		pos_in_item *= UNFM_P_SIZE;

	if (tb->lnum[0] > 0) {
		/* Shift lnum[0] items from S[0] to the left neighbor L[0] */
		if (item_pos < tb->lnum[0]) {
			/* new item or it part falls to L[0], shift it too */
			n = B_NR_ITEMS(tb->L[0]);

			switch (flag) {
			case M_INSERT:	/* insert item into L[0] */

				if (item_pos == tb->lnum[0] - 1
				    && tb->lbytes != -1) {
					/* part of new item falls into L[0] */
					int new_item_len;
					int version;

					ret_val =
					    leaf_shift_left(tb, tb->lnum[0] - 1,
							    -1);

					/* Calculate item length to insert to S[0] */
					new_item_len =
					    ih_item_len(ih) - tb->lbytes;
					/* Calculate and check item length to insert to L[0] */
					put_ih_item_len(ih,
							ih_item_len(ih) -
							new_item_len);

					RFALSE(ih_item_len(ih) <= 0,
					       "PAP-12080: there is nothing to insert into L[0]: ih_item_len=%d",
					       ih_item_len(ih));

					/* Insert new item into L[0] */
					bi.tb = tb;
					bi.bi_bh = tb->L[0];
					bi.bi_parent = tb->FL[0];
					bi.bi_position =
					    get_left_neighbor_position(tb, 0);
					leaf_insert_into_buf(&bi,
							     n + item_pos -
							     ret_val, ih, body,
							     zeros_num >
							     ih_item_len(ih) ?
							     ih_item_len(ih) :
							     zeros_num);

					version = ih_version(ih);

					/* Calculate key component, item length and body to insert into S[0] */
					set_le_ih_k_offset(ih,
							   le_ih_k_offset(ih) +
							   (tb->
							    lbytes <<
							    (is_indirect_le_ih
							     (ih) ? tb->tb_sb->
							     s_blocksize_bits -
							     UNFM_P_SHIFT :
							     0)));

					put_ih_item_len(ih, new_item_len);
					if (tb->lbytes > zeros_num) {
						body +=
						    (tb->lbytes - zeros_num);
						zeros_num = 0;
					} else
						zeros_num -= tb->lbytes;

					RFALSE(ih_item_len(ih) <= 0,
					       "PAP-12085: there is nothing to insert into S[0]: ih_item_len=%d",
					       ih_item_len(ih));
				} else {
					/* new item in whole falls into L[0] */
					/* Shift lnum[0]-1 items to L[0] */
					ret_val =
					    leaf_shift_left(tb, tb->lnum[0] - 1,
							    tb->lbytes);
					/* Insert new item into L[0] */
					bi.tb = tb;
					bi.bi_bh = tb->L[0];
					bi.bi_parent = tb->FL[0];
					bi.bi_position =
					    get_left_neighbor_position(tb, 0);
					leaf_insert_into_buf(&bi,
							     n + item_pos -
							     ret_val, ih, body,
							     zeros_num);
					tb->insert_size[0] = 0;
					zeros_num = 0;
				}