node40.c

reiser4progs ReiserFS V4 ReiserFs官方已经关闭 这个是1.0.6 2006-02-22发布的 给需要的朋友

	pol = entity->keypol;
	items = nh_get_num_items(entity);

	aal_assert("umka-2685", (left_pos->item < items &&
				 right_pos->item < items));
	
	/* Check is items lie side by side. */
	delta = left_pos->item - right_pos->item;
	
	if (aal_abs(delta) > 1) {
		aal_error("Can't merge items which lie not side "
			  "by side each other.");
		return -EINVAL;
	}

	/* First stage. Fusing item bodies: we should call some item 
	   method, which will take care about item overhead, etc. */
	if (node40_fetch(entity, left_pos, &left_place)) {
		aal_error("Can't fetch the left item on fusing.");
		return -EINVAL;
	}
	
	if (node40_fetch(entity, right_pos, &right_place)) {
		aal_error("Can't fetch the right item on fusing.");
		return -EINVAL;
	}

	aal_assert("umka-2686", plug_equal(left_place.plug,
					   right_place.plug));

	/* Check if item needs some special actions to merge (like eliminate
	   header). If so, merge items. */
	if (left_place.plug->balance->merge) {
		int32_t space;

		/* Returned space is released space in node and it should be
		   counted in node header. */
		if ((space = objcall(&left_place, balance->merge, 
				     &right_place)))
		{
			right_pos->unit = 0;

			/* Shrink the right item. */
			if ((res = node40_shrink(entity, right_pos, space, 1)))
				return res;
		}
	}
	
	/* The second stage: remove the right item header. */
	left = node40_ih_at(entity, left_pos->item);
	right = node40_ih_at(entity, right_pos->item);

	if (right_pos->item < items - 1) {
		/* Move all headers after right_pos to the right. */
		delta = (items - right_pos->item - 1) * ih_size(pol);
		aal_memmove(left - delta, right - delta, delta);
	}

	nh_dec_num_items(entity, 1);
	nh_inc_free_space(entity, ih_size(pol));

	/* Now make node dirty. */
	node40_mkdirty(entity);
	return 0;
}

/* Updates key at @pos by specified @key */
static errno_t node40_set_key(reiser4_node_t *entity, 
			      pos_t *pos, reiser4_key_t *key) 
{
	void *ih;
	uint32_t key_size;

	aal_assert("umka-819", key != NULL);
    	aal_assert("umka-944", pos != NULL);
	
	aal_assert("umka-811", pos->item <
		   node40_items(entity));

	aal_assert("umka-809", entity != NULL);

	ih = node40_ih_at(entity, pos->item);
	key_size = key_size(entity->keypol);
	aal_memcpy(ih, key->body, key_size);
		
	node40_mkdirty(entity);
	return 0;
}
#endif

#ifdef ENABLE_SHORT_KEYS
/* Helper callback for comparing two keys. This is used by node lookup. */
static int cb_comp_key3(void *ih0, uint32_t pos,
			void *k2, void *data)
{
	reiser4_key_t *key2;
	void *key1;
	
	key1 = ih0 - sizeof(item_header3_t) * pos;
	key2 = (reiser4_key_t *)k2;
	
	return plugcall(key2->plug, compraw, key1, key2->body);
}
#endif

#ifdef ENABLE_LARGE_KEYS
/* Helper callback for comparing two keys. This is used by node lookup. */
static int cb_comp_key4(void *ih0, uint32_t pos,
			void *k2, void *data)
{
	reiser4_key_t *key2;
	void *key1;
	
	/* Key policy is given by @data. */
	key1 = ih0 - sizeof(item_header4_t) * pos;
	key2 = (reiser4_key_t *)k2;
	
	return plugcall(key2->plug, compraw, key1, key2->body);
}
#endif

/* Makes search inside the specified node @entity for @key and stores the result
   into @pos. This function returns 1 if key is found and 0 otherwise. */
static lookup_t node40_lookup(reiser4_node_t *entity,
			      lookup_hint_t *hint,
			      lookup_bias_t bias,
			      pos_t *pos)
{
	aux_comp_func_t func;
	void *ih;
	
	aal_assert("umka-478", pos != NULL);
	aal_assert("umka-472", hint != NULL);
	aal_assert("umka-470", entity != NULL);
	aal_assert("umka-3089", hint->key != NULL);
	aal_assert("umka-567", hint->key->body != NULL);

#if defined(ENABLE_SHORT_KEYS) && defined(ENABLE_LARGE_KEYS)
	func = (entity->keypol == 3) ? cb_comp_key3 : cb_comp_key4;
#elif defined(ENABLE_SHORT_KEYS)
	func = cb_comp_key3;
#elif defined(ENABLE_LARGE_KEYS)
	func = cb_comp_key4;
#elif
	func = NULL;
#endif
	
	ih = node40_ih_at((reiser4_node_t *)entity, 0);
	switch (aux_bin_search(ih, nh_get_num_items(entity), 
			       hint->key, func, NULL, &pos->item))
	{
	case 1:
		return PRESENT;
	case 0:
		return ABSENT;
	default:
		return -EIO;
	}
}

#ifndef ENABLE_MINIMAL
/* Checks if @place is splittable. */
static int node40_splittable(reiser4_place_t *place, shift_hint_t *hint) {
	/* Check if item's shift_units() and prep_shift() method are
	   implemented. */
	if (!place->plug->balance->shift_units ||
	    !place->plug->balance->prep_shift)
	{
		return 0;
	}
	
	/* We can't shift units from items with one unit. */
	if (!place->plug->balance->units)
		return 0;
	
	return (objcall(place, balance->units) > 0);
}

/* Initializes place by border item data (leftmost or rightmost). */
static errno_t node40_border(reiser4_node_t *entity,
			     int left_border, reiser4_place_t *place)
{
	uint32_t items;
	pos_t pos;
	
	aal_assert("umka-2669", place != NULL);
	aal_assert("umka-2670", entity != NULL);
	
	if ((items = nh_get_num_items(entity)) == 0)
		return -EINVAL;

	POS_INIT(&pos, (left_border ? 0 : items - 1),
		 MAX_UINT32);
	
	return node40_fetch(entity, &pos, place);
}

/* Merges border items of the src and dst nodes. The behavior depends on the
   passed hint pointer. */
static errno_t node40_unite(reiser4_node_t *src_entity,
			    reiser4_node_t *dst_entity, 
			    shift_hint_t *hint,
			    int create)
{
	pos_t pos;
	errno_t res;
	uint32_t pol;
	uint32_t len;
	uint32_t units;

	reiser4_place_t src_place;
	reiser4_place_t dst_place;
	
	uint32_t dst_items;
	uint32_t src_items;
	
	void *src_ih, *dst_ih;
	int left_shift, remove;
	
	aal_assert("umka-1624", hint != NULL);
	aal_assert("umka-1622", src_entity != NULL);
	aal_assert("umka-1623", dst_entity != NULL);
	
	pol = dst_entity->keypol;
	src_items = nh_get_num_items(src_entity);
	dst_items = nh_get_num_items(dst_entity);
	
	hint->units_bytes = node40_space(dst_entity);

	/* Nothing to move or not enough of space to moveat least one byte to
	   @dst_entity. */
	if (src_items == 0 || hint->units_bytes == 0)
		return 0;
	
	left_shift = (hint->control & SF_ALLOW_LEFT);
	
	/* We can't split the leftmost and rightmost items if they are the same
	   insert point points to. */
	if ((hint->control & SF_UPDATE_POINT) &&
	    hint->pos.unit == MAX_UINT32)
	{
		if ((left_shift && hint->pos.item == 0) ||
		    (!left_shift && hint->pos.item == src_items))
		{
			return 0;
		}
	}

	/* Getting src item. */
	if ((res = node40_border(src_entity, left_shift, &src_place)))
		return res;

	/* Items that do not implement prep_shift() and shift_units() methods
	   cannot be splitted. */
	if (!node40_splittable(&src_place, hint))
		return 0;
	
	/* Checking if items are mergeable. */
	if (dst_items > 0) {
		/* Getting dst item. */
		if ((res = node40_border(dst_entity, !left_shift, &dst_place)))
			return res;

		/* Check if items has the same flags. If so, they can be tried
		   to be merged. */
		src_ih = node40_ih_at(src_entity, src_place.pos.item);
		dst_ih = node40_ih_at(dst_entity, dst_place.pos.item);

		if (ih_get_flags(src_ih, pol) != ih_get_flags(dst_ih, pol))
			return 0;

		/* Check if we need to create new new item in @dst_entity in
		   order to move data to it. */
		if (left_shift) {
			hint->create = !node40_core->item_ops.mergeable(&dst_place,
									&src_place);
		} else {
			hint->create = !node40_core->item_ops.mergeable(&src_place,
									&dst_place);
		}
	} else {
		/* There are no items in dst node and we create new item in
		   neighbour node anyway. */
		hint->create = 1;
	}

	/* If items are not mergeable and we are in merge mode, we will not
	   create new item in dst node. This mode is needed for mergeing two
	   mergeable items when they lie in different nodes, and in such a way
	   to prevent creating two mergeable items in the same node. */
	if (hint->create != create)
		return 0;
	
	/* Calling item's prep_shift() method in order to estimate how many
	   units may be shifted out. This method also updates unit component of
	   insert point position. After this function is finish @units_bytes
	   will contain real number of bytes to be shifted into neighbour
	   item. */
	if (hint->create) {
		uint32_t overhead;

		/* Getting node overhead in order to substract it from
		   @units_bytes, that is from space allowed to be used. */
		overhead = node40_overhead(dst_entity);

		/* There is not of enough free space in @dst_entity even to
		   create an empty item in it. Getting out. */
		if (hint->units_bytes <= overhead)
			return 0;

		/* Substract node overhead, that is item header. */
		hint->units_bytes -= overhead;

		/* Making estimate how many units and bytes may be shifted. */
		if (objcall(&src_place, balance->prep_shift, NULL, hint))
			return -EINVAL;
		
		/* Updating item component of insert point if it was moved into
		   neighbour item. */
		if (hint->control & SF_UPDATE_POINT &&
		    hint->result & SF_MOVE_POINT)
		{
			hint->pos.item = 0;
			
			if (left_shift)
				hint->pos.item = dst_items;
		}

		/* Check if shift_units() may shift something at all. If no --
		   getting out of here. */
		if (hint->units_number == 0)
			return 0;

		/* Prepare pos new item will be created at. */
		POS_INIT(&pos, (left_shift ? dst_items : 0), MAX_UINT32);
	} else {
		/* The same for case when we will not create new item, but will
		   shift units into existent one in neighbour node. */
		if (objcall(&src_place, balance->prep_shift, &dst_place, hint))
			return -EINVAL;
		
		if (hint->control & SF_UPDATE_POINT &&
		    hint->result & SF_MOVE_POINT)
		{
			hint->pos.item = 0;

			if (left_shift)
				hint->pos.item = dst_items - 1;
		}

		/* Check if shift_units() may shift something at all. If no --
		   getting out of here. */
		if (hint->units_number == 0)
			return 0;

		/* Prepare pos, item will be expanded at. Items are mergeable,
		   so we do not need to create new item in @dst_entity. We just
		   need to expand existent dst item by @hint->units_bytes, thus
		   unit component of @pos is set to 0.*/
		POS_INIT(&pos, (left_shift ? dst_items - 1 : 0), 0);
	}

	/* Expanding node by @hint->units_bytes at @pos. */
	if (node40_expand(dst_entity, &pos, hint->units_bytes, 1)) {
		aal_error("Can't expand node for shifting units into it.");
		return -EINVAL;
	}

	if (hint->create) {
		/* Setting up new item fields such as plugin id and key. */
		dst_ih = node40_ih_at(dst_entity, pos.item);
		ih_set_pid(dst_ih, src_place.plug->p.id.id, pol);
		aal_memcpy(dst_ih, src_place.key.body, key_size(pol));

		/* Copying old item flags to new created one. This is needed,
		   because these flags may say, for instance, that item is
		   already checked by fsck and thus, new item which is created
		   by splitting old one should have the same flags. This is also
		   needed, because items with different flags will not be merged
		   and this will cause bad tree packing. */
		src_ih = node40_ih_at(src_entity, src_place.pos.item);
		ih_set_flags(dst_ih, ih_get_flags(src_ih, pol), pol); 
	}

	/* Initializing @dst_place after that item was expanded by expand()
	   function. */
	if (node40_fetch(dst_entity, &pos, &dst_place))
		return -EINVAL;

	if (hint->create) {
		uint64_t offset;
		
		/* Setting dst item key offset into max key offset of src in
		   order to let item shift method correctly calculate offset
		   of this new item later. */
		objcall(&src_place, balance->maxreal_key, &dst_place.key);
		offset = objcall(&dst_place.key, get_offset);
		objcall(&dst_place.key, set_offset, offset + 1);

	}
	
	/* Getting units number after shift. This is needed to detect correctly,
	   that src item is empty after shift and may be removed. */
	units = objcall(&src_place, balance->units);
	
	/* Shift units from @src_place to @dst_place. */
	if (objcall(&src_place, balance->shift_units, &dst_place, hint)) {
		aal_error("Can't shift units.");
		return -EINVAL;
	}

	/* Set update flag to let high levels code know, that left delemiting
	   keys should be updated. */
	hint->update = 1;
	pos.item = src_place.pos.item;

	/* We will remove src item if it has became empty and insert point does
	   not point it, that is next insert will not be dealing with it. */
	remove = (hint->units_number == units);
	
	/* Updating item's keys after shift_unit() is finished. */
	if (left_shift) {
		/* We do not need to update key of the src item which is going
		   to be removed. */
		if (!remove) {
			src_ih = node40_ih_at(src_entity, src_place.pos.item);