ibalance.c | Explore in Territory

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

#include <linux/uaccess.h>
#include <linux/string.h>
#include <linux/time.h>
#include "reiserfs.h"
#include <linux/buffer_head.h>

/* this is one and only function that is used outside (do_balance.c) */
int balance_internal(struct tree_balance *,
		     int, int, struct item_head *, struct buffer_head **);

/*
 * modes of internal_shift_left, internal_shift_right and
 * internal_insert_childs
 */
#define INTERNAL_SHIFT_FROM_S_TO_L …
#define INTERNAL_SHIFT_FROM_R_TO_S …
#define INTERNAL_SHIFT_FROM_L_TO_S …
#define INTERNAL_SHIFT_FROM_S_TO_R …
#define INTERNAL_INSERT_TO_S …
#define INTERNAL_INSERT_TO_L …
#define INTERNAL_INSERT_TO_R …

static void internal_define_dest_src_infos(int shift_mode,
					   struct tree_balance *tb,
					   int h,
					   struct buffer_info *dest_bi,
					   struct buffer_info *src_bi,
					   int *d_key, struct buffer_head **cf)
{ … }

/*
 * Insert count node pointers into buffer cur before position to + 1.
 * Insert count items into buffer cur before position to.
 * Items and node pointers are specified by inserted and bh respectively.
 */
static void internal_insert_childs(struct buffer_info *cur_bi,
				   int to, int count,
				   struct item_head *inserted,
				   struct buffer_head **bh)
{ … }

/*
 * Delete del_num items and node pointers from buffer cur starting from
 * the first_i'th item and first_p'th pointers respectively.
 */
static void internal_delete_pointers_items(struct buffer_info *cur_bi,
					   int first_p,
					   int first_i, int del_num)
{ … }

/* delete n node pointers and items starting from given position */
static void internal_delete_childs(struct buffer_info *cur_bi, int from, int n)
{ … }

/*
 * copy cpy_num node pointers and cpy_num - 1 items from buffer src to buffer
 * dest
 * last_first == FIRST_TO_LAST means that we copy first items
 *                             from src to tail of dest
 * last_first == LAST_TO_FIRST means that we copy last items
 *                             from src to head of dest
 */
static void internal_copy_pointers_items(struct buffer_info *dest_bi,
					 struct buffer_head *src,
					 int last_first, int cpy_num)
{ … }

/*
 * Copy cpy_num node pointers and cpy_num - 1 items from buffer src to
 * buffer dest.
 * Delete cpy_num - del_par items and node pointers from buffer src.
 * last_first == FIRST_TO_LAST means, that we copy/delete first items from src.
 * last_first == LAST_TO_FIRST means, that we copy/delete last items from src.
 */
static void internal_move_pointers_items(struct buffer_info *dest_bi,
					 struct buffer_info *src_bi,
					 int last_first, int cpy_num,
					 int del_par)
{ … }

/* Insert n_src'th key of buffer src before n_dest'th key of buffer dest. */
static void internal_insert_key(struct buffer_info *dest_bi,
				/* insert key before key with n_dest number */
				int dest_position_before,
				struct buffer_head *src, int src_position)
{ … }

/*
 * Insert d_key'th (delimiting) key from buffer cfl to tail of dest.
 * Copy pointer_amount node pointers and pointer_amount - 1 items from
 * buffer src to buffer dest.
 * Replace  d_key'th key in buffer cfl.
 * Delete pointer_amount items and node pointers from buffer src.
 */
/* this can be invoked both to shift from S to L and from R to S */
static void internal_shift_left(
				/*
				 * INTERNAL_FROM_S_TO_L | INTERNAL_FROM_R_TO_S
				 */
				int mode,
				struct tree_balance *tb,
				int h, int pointer_amount)
{ … }

/*
 * Insert delimiting key to L[h].
 * Copy n node pointers and n - 1 items from buffer S[h] to L[h].
 * Delete n - 1 items and node pointers from buffer S[h].
 */
/* it always shifts from S[h] to L[h] */
static void internal_shift1_left(struct tree_balance *tb,
				 int h, int pointer_amount)
{ … }

/*
 * Insert d_key'th (delimiting) key from buffer cfr to head of dest.
 * Copy n node pointers and n - 1 items from buffer src to buffer dest.
 * Replace  d_key'th key in buffer cfr.
 * Delete n items and node pointers from buffer src.
 */
static void internal_shift_right(
				 /*
				  * INTERNAL_FROM_S_TO_R | INTERNAL_FROM_L_TO_S
				  */
				 int mode,
				 struct tree_balance *tb,
				 int h, int pointer_amount)
{ … }

/*
 * Insert delimiting key to R[h].
 * Copy n node pointers and n - 1 items from buffer S[h] to R[h].
 * Delete n - 1 items and node pointers from buffer S[h].
 */
/* it always shift from S[h] to R[h] */
static void internal_shift1_right(struct tree_balance *tb,
				  int h, int pointer_amount)
{ … }

/*
 * Delete insert_num node pointers together with their left items
 * and balance current node.
 */
static void balance_internal_when_delete(struct tree_balance *tb,
					 int h, int child_pos)
{ … }

/* Replace delimiting key of buffers L[h] and S[h] by the given key.*/
static void replace_lkey(struct tree_balance *tb, int h, struct item_head *key)
{ … }

/* Replace delimiting key of buffers S[h] and R[h] by the given key.*/
static void replace_rkey(struct tree_balance *tb, int h, struct item_head *key)
{ … }


/*
 * if inserting/pasting {
 *   child_pos is the position of the node-pointer in S[h] that
 *   pointed to S[h-1] before balancing of the h-1 level;
 *   this means that new pointers and items must be inserted AFTER
 *   child_pos
 * } else {
 *   it is the position of the leftmost pointer that must be deleted
 *   (together with its corresponding key to the left of the pointer)
 *   as a result of the previous level's balancing.
 * }
 */

int balance_internal(struct tree_balance *tb,
		     int h,	/* level of the tree */
		     int child_pos,
		     /* key for insertion on higher level    */
		     struct item_head *insert_key,
		     /* node for insertion on higher level */
		     struct buffer_head **insert_ptr)
{ … }
linux/fs/reiserfs/ibalance.c
