static void balance_leaf_do_split(struct tree_balance *tb,
struct item_head *ih,
const char *body,
int flag,
struct item_head *insert_key,
struct buffer_head **insert_ptr)
{
struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
/* index of the affected item */
int item_pos = PATH_LAST_POSITION(tb->tb_path);
struct buffer_info bi;
int n, i, ret_val;
int pos_in_item;
int zeros_num;
struct buffer_head *S_new[2];
int snum[2];
int sbytes[2];
if (!tb->blknum[0])
return;
if (!(flag == M_INSERT || flag == M_PASTE) {
reiserfs_panic(tb->tb_sb,
"PAP-12245: balance_leaf: blknum > 2: unexpectable mode: %s(%d)",
(flag == M_DELETE) ? "DELETE" :
((flag == M_CUT) ? "CUT" : "UNKNOWN"), flag);
return;
}
RFALSE(tb->blknum[0] < 1 || tb->blknum[0] > 3,
"PAP-12180: blknum can not be %d. It must be in range [1,3]",
tb->blknum[0]);
/* Fill new nodes that appear in place of S[0] */
snum[0] = tb->s1num;
snum[1] = tb->s2num;
sbytes[0] = tb->s1bytes;
sbytes[1] = tb->s2bytes;
for (i = tb->blknum[0] - 2; i >= 0; i--) {
RFALSE(!snum[i], "PAP-12200: snum[%d] == %d. Must be > 0", i, snum[i]);
/* here we shift from S to S_new nodes */
S_new[i] = get_FEB(tb);
/* initialized block type and tree level */
set_blkh_level(B_BLK_HEAD(S_new[i]), DISK_LEAF_NODE_LEVEL);
n = B_NR_ITEMS(tbS0);
if (flag == M_INSERT) {
if (!(n - snum[i] < item_pos)) {
/* new item or it part don't falls into S_new[i] */
leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
snum[i], sbytes[i], S_new[i]);
goto next;
}
goto long_tail_insert;
} else {
if (!(n - snum[i] <= item_pos)) {
/* pasted item doesn't fall into S_new[i] */
leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
snum[i], sbytes[i], S_new[i]);
goto next;
}
goto long_tail_paste;
}
long_tail_insert:
if (item_pos == n - snum[i] + 1 && sbytes[i] != -1) {
/* part of new item falls into S_new[i] */
int old_key_comp, old_len, r_zeros_number;
const char *r_body;
int version;
/* Move snum[i]-1 items from S[0] to S_new[i] */
leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
snum[i] -1, -1, S_new[i]);
/* Remember key component and item length */
version = ih_version(ih);
old_key_comp = le_ih_k_offset(ih);
old_len = ih_item_len(ih);
/*Calculate key component and item length to insert into S_new[i] */
set_le_ih_k_offset(ih,
le_ih_k_offset(ih) +
((old_len - sbytes[i]) << (is_indirect_le_ih(ih) ?
tb->tb_sb->s_blocksize_bits - UNFM_P_SHIFT : 0)));
put_ih_item_len(ih, sbytes[i]);
/* Insert part of the item into S_new[i] before 0-th item */
bi.tb = tb;
bi.bi_bh = S_new[i];
bi.bi_parent = NULL;
bi.bi_position = 0;
if ((old_len - sbytes[i]) > zeros_num) {
r_zeros_number = 0;
r_body = body + (old_len - sbytes[i]) - zeros_num;
} else {
r_body = body;
r_zeros_number = zeros_num - (old_len - sbytes[i]);
zeros_num -= r_zeros_number;
}
leaf_insert_into_buf(&bi, 0, ih, r_body, r_zeros_number);
/* Calculate key component and item length to insert into S[i] */
set_le_ih_k_offset(ih, old_key_comp);
put_ih_item_len(ih, old_len - sbytes[i]);
tb->insert_size[0] -= sbytes[i];
} else { /* whole new item falls into S_new[i] */
/* Shift snum[0] - 1 items to S_new[i] (sbytes[i] of split item) */
leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
snum[i] -1, sbytes[i], S_new[i]);
/* Insert new item into S_new[i] */
bi.tb = tb;
bi.bi_bh = S_new[i];
bi.bi_parent = NULL;
bi.bi_position = 0;
leaf_insert_into_buf(&bi, item_pos - n + snum[i] - 1,
ih, body, zeros_num);
zeros_num = tb->insert_size[0] = 0;
}
goto next;
long_tail_paste:
if (item_pos == n - snum[i] && sbytes[i] != -1) {
/* we must shift part of the appended item */
struct item_head *aux_ih;
RFALSE(ih, "PAP-12210: ih must be 0");
aux_ih = B_N_PITEM_HEAD(tbS0, item_pos);
if (is_direntry_le_ih(aux_ih)) {
/* we append to directory item */
int entry_count = ih_entry_count(aux_ih);
if (entry_count - sbytes[i] < pos_in_item
&& pos_in_item <= entry_count) {
/* new directory entry falls into S_new[i] */
RFALSE(!tb->insert_size[0],
"PAP-12215: insert_size is already 0");
RFALSE(sbytes[i] - 1 >= entry_count,
"PAP-12220: there are no so much entries (%d), only %d",
sbytes[i] - 1, entry_count);
/* Shift snum[i]-1 items in whole. Shift sbytes[i] directory entries from directory item number snum[i] */
leaf_move_items(LEAF_FROM_S_TO_SNEW, tb, snum[i],
sbytes[i] - 1, S_new[i]);
/* Paste given directory entry to directory item */
bi.tb = tb;
bi.bi_bh = S_new[i];
bi.bi_parent = NULL;
bi.bi_position = 0;
leaf_paste_in_buffer(&bi, 0,
pos_in_item - entry_count + sbytes[i] - 1,
tb->insert_size[0], body, zeros_num);
/* paste new directory entry */
leaf_paste_entries(bi.bi_bh, 0,
pos_in_item - entry_count + sbytes[i] - 1,
1,
(struct reiserfs_de_head *) body,
body + DEH_SIZE, tb->insert_size[0]);
tb->insert_size[0] = 0;
pos_in_item++;
} else {
/* new directory entry doesn't fall into S_new[i] */
leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
snum[i], sbytes[i], S_new[i]);
}
} else { /* regular object */
int n_shift, n_rem, r_zeros_number;
const char *r_body;
RFALSE(pos_in_item != ih_item_len(B_N_PITEM_HEAD(tbS0, item_pos))
|| tb->insert_size[0] <= 0,
"PAP-12225: item too short or insert_size <= 0");
/* Calculate number of bytes which must be
* shifted from appended item */
n_shift = sbytes[i] - tb->insert_size[0];
if (n_shift < 0)
n_shift = 0;
leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
snum[i], n_shift, S_new[i]);
/* Calculate number of bytes which must remain
* in body after append to S_new[i] */
n_rem = tb->insert_size[0] - sbytes[i];
if (n_rem < 0)
n_rem = 0;
/* Append part of body into S_new[0] */
bi.tb = tb;
bi.bi_bh = S_new[i];
bi.bi_parent = NULL;
bi.bi_position = 0;
if (n_rem > zeros_num) {
r_zeros_number = 0;
r_body = body + n_rem - zeros_num;
} else {
r_body = body;
r_zeros_number = zeros_num - n_rem;
zeros_num -= r_zeros_number;
}
leaf_paste_in_buffer(&bi, 0, n_shift,
tb->insert_size[0] - n_rem,
r_body, r_zeros_number);
{
/* 2008-2-16 14:19
* itis not easy to format,
* needless to say to debug HR.
*/
struct item_head *tmp;
tmp = B_N_PITEM_HEAD(S_new[i], 0);
if (is_indirect_le_ih(tmp)) {
set_ih_free_space(tmp, 0);
set_le_ih_k_offset(tmp,
le_ih_k_offset(tmp) +
(n_rem << (tb->tb_sb->s_blocksize_bits - UNFM_P_SHIFT)));
} else {
set_le_ih_k_offset(tmp,
le_ih_k_offset(tmp) + n_rem);
}
}
tb->insert_size[0] = n_rem;
if (!n_rem)
pos_in_item++;
}
} else { /* item falls wholly into S_new[i] */
int ret_val;
struct item_head *pasted;
#ifdef CONFIG_REISERFS_CHECK
struct item_head *ih = B_N_PITEM_HEAD(tbS0, item_pos);
if (!is_direntry_le_ih(ih) &&
(pos_in_item != ih_item_len(ih)
|| tb->insert_size[0] <= 0))
reiserfs_panic(tb->tb_sb,
"PAP-12235: balance_leaf: pos_in_item must be equal to ih_item_len");
#endif /* CONFIG_REISERFS_CHECK */
ret_val = leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
snum[i], sbytes[i], S_new[i]);
RFALSE(ret_val,
"PAP-12240: unexpected value returned by leaf_move_items (%d)",
ret_val);
/* paste into item */
bi.tb = tb;
bi.bi_bh = S_new[i];
bi.bi_parent = NULL;
bi.bi_position = 0;
leaf_paste_in_buffer(&bi, item_pos - n + snum[i],
pos_in_item,
tb->insert_size[0],
body, zeros_num);
pasted = B_N_PITEM_HEAD(S_new[i], item_pos - n + snum[i]);
if (is_direntry_le_ih(pasted))
leaf_paste_entries(bi.bi_bh,
item_pos - n + snum[i],
pos_in_item, 1,
(struct reiserfs_de_head *)body,
body + DEH_SIZE,
tb->insert_size[0]);
/* if we paste to indirect item update ih_free_space */
if (is_indirect_le_ih(pasted))
set_ih_free_space(pasted, 0);
zeros_num = tb->insert_size[0] = 0;
}
goto next;
next:
memcpy(insert_key + i, B_N_PKEY(S_new[i], 0), KEY_SIZE);
insert_ptr[i] = S_new[i];
RFALSE(!buffer_journaled(S_new[i])
|| buffer_journal_dirty(S_new[i])
|| buffer_dirty(S_new[i]),
"PAP-12247: S_new[%d] : (%b)", i, S_new[i]);
} /* for loop */
}
