node40.c

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

			aal_memcpy(src_ih, src_place.key.body, key_size(pol));
		}
	} else {
		dst_ih = node40_ih_at(dst_entity, dst_place.pos.item);
		aal_memcpy(dst_ih, dst_place.key.body, key_size(pol));
	}
	
	if (remove) {
		/* Like expand() does, shrink() will remove pointed item if unit
		   component is MAX_UINT32 and shrink the item pointed by pos if
		   unit component is not MAX_UINT32. */
		len = src_place.len;
		pos.unit = MAX_UINT32;

		if (pos.item == hint->pos.item)
			hint->pos.unit = MAX_UINT32;
		
		/* As item will be removed, we should update item pos in hint
		   properly. */
		if (!(hint->result & SF_MOVE_POINT) &&
		    pos.item < hint->pos.item)
		{
			hint->pos.item--;
		}
	} else {
		/* Sources item will not be removed, because it is not yet
		   empty, it will be just shrinked by @hint->units_bytes. */
		pos.unit = 0;
		len = hint->units_bytes;
	}

	/* Shrining node by @len. */
	return node40_shrink(src_entity, &pos, len, 1);
}

/* Predicts how many whole item may be shifted from @src_entity to
   @dst_entity. */
static errno_t node40_predict(reiser4_node_t *src_entity,
			      reiser4_node_t *dst_entity, 
			      shift_hint_t *hint)
{
	uint32_t pol;
	uint32_t flags;
	uint32_t space;
	void *cur, *end;
	
	uint32_t src_items;
	uint32_t dst_items;

	dst_items = nh_get_num_items(dst_entity);
	
	if (!(src_items = nh_get_num_items(src_entity)))
		return 0;

	pol = src_entity->keypol;
	space = node40_space(dst_entity);
	
	end = node40_ih_at(src_entity, src_items - 1);

	if (hint->control & SF_ALLOW_LEFT) {
		cur = node40_ih_at(src_entity, 0);
	} else {
		cur = node40_ih_at(src_entity, src_items - 1);
	}
	
	/* Estimating will be finished if @src_items value is exhausted or
	   insert point is shifted out to neighbour node. */
	flags = hint->control;
	
	while (!(hint->result & SF_MOVE_POINT) && src_items > 0) {
		uint32_t len;

		if (!(flags & SF_MOVE_POINT) && (flags & SF_ALLOW_RIGHT)) {
			if (hint->pos.item >= src_items)
				break;
		}
		
		/* Getting length of current item. */
		if (cur == end) {
			len = nh_get_free_space_start(src_entity) -
				ih_get_offset(cur, pol);
		} else {
			len = ih_get_offset((cur - ih_size(pol)), pol) -
				ih_get_offset(cur, pol);
		}

		/* We go out if there is no enough free space to shift one more
		   whole item. */
		if (space < len + node40_overhead(dst_entity))
			break;

		/* Check if we allowed to update insert point. If so, we will do
		   so and loop probably will be breaked due to insert point
		   moved to neihgbour node. Will continue until there is enough
		   of space otherwise. */
		if (flags & SF_UPDATE_POINT) {
			/* Updating insert point. */
			if (flags & SF_ALLOW_LEFT) {
				if (hint->pos.item == 0) {
					pos_t pos;
					reiser4_place_t place;
					uint32_t units;

					/* If unit component if zero, we can
					   shift whole item pointed by pos. */
					POS_INIT(&pos, 0, MAX_UINT32);
					
					if (node40_fetch(src_entity, &pos, &place))
						return -EINVAL;

					if (!place.plug->balance->units)
						return -EINVAL;
				
					units = objcall(&place, balance->units);

					/* Breaking if insert point reach the
					   end of node. */
					if (flags & SF_MOVE_POINT &&
					    (hint->pos.unit == MAX_UINT32 ||
					     hint->pos.unit >= units - 1))
					{
						/* If we are permitted to move
						   insetr point to the neigbour,
						   we doing it. */
						hint->result |= SF_MOVE_POINT;
						hint->pos.item = dst_items;
					} else
						break;
				
				} else {
					hint->pos.item--;
				}
			} else {
				/* Checking if insert point reach the end of
				   node. */
				if (hint->pos.item >= src_items - 1) {
					if (hint->pos.item == src_items - 1) {
						/* Updating insert point to be
						   lie in neighbour node. */
						if (flags & SF_MOVE_POINT &&
						    (hint->pos.unit == MAX_UINT32 ||
						     hint->pos.unit == 0))
						{
							hint->result |= SF_MOVE_POINT;
							hint->pos.item = 0;
						} else {
							if (hint->pos.unit != MAX_UINT32)
								break;
						}
					} else {
						/* Insert point stays at the non
						   existent item. So we should
						   just update hint and break
						   the loop. */
						if (flags & SF_MOVE_POINT) {
							hint->result |= SF_MOVE_POINT;
							hint->pos.item = 0;
						}
						
						break;
					}
				}
			}
		}

		/* Updating some counters and shift hint */
		hint->items_number++;
		hint->items_bytes += len;
		src_items--; dst_items++;
		
		space -= (len + node40_overhead(dst_entity));
		
		cur += (flags & SF_ALLOW_LEFT ? -ih_size(pol) :
			ih_size(pol));
	}

	/* After number of whole items was estimated, all free space will be
	   used for estimating how many units may be shifted. */
	hint->units_bytes = space;
	return 0;
}

/* Moves some amount of whole items from @src_entity to @dst_entity */
static errno_t node40_move(reiser4_node_t *src_entity,
			   reiser4_node_t *dst_entity, 
			   shift_hint_t *hint)
{	
	errno_t res;
	pos_t src_pos;
	pos_t dst_pos;
	
	uint32_t src_items;
	uint32_t dst_items;

	aal_assert("umka-1620", hint != NULL);
	aal_assert("umka-1621", src_entity != NULL);
	aal_assert("umka-1619", dst_entity != NULL);

	dst_items = nh_get_num_items(dst_entity);
	src_items = nh_get_num_items(src_entity);

	/* Calculating how many items and how many bytes may be moved from
	   @src_entity to @dst_entity. Calculating result is stored in @hint and
	   will be used later. */
	if ((res = node40_predict(src_entity, dst_entity, hint)))
		return res;

	/* No items to be shifted */
	if (hint->items_number == 0 || hint->items_bytes == 0)
		return 0;
	
	/* Initializing src and dst positions, we will used them for moving
	   items. They are initialized in different way for left and right
	   shift. */
	if (hint->control & SF_ALLOW_LEFT) {
		POS_INIT(&src_pos, 0, MAX_UINT32);
		POS_INIT(&dst_pos, dst_items, MAX_UINT32);
	} else {
		POS_INIT(&dst_pos, 0, MAX_UINT32);

		POS_INIT(&src_pos, src_items -
			 hint->items_number, MAX_UINT32);
	}
	
	/* Expanding dst node in order to make room for new items and update
	   node header. */
	if ((res = node40_expand(dst_entity, &dst_pos, hint->items_bytes,
				 hint->items_number)))
	{
		return res;
	}
		
	/* Copying items from src node to dst one */
	if ((res = node40_copy(dst_entity, &dst_pos, src_entity,
			       &src_pos, hint->items_number)))
	{
		return res;
	}

	/* Set update flag to let high levels code know, that left delemiting
	   keys should be updated. */
	hint->update = 1;
	
	/* Shrinking source node after items are copied from it into dst
	   node. */
	return node40_shrink(src_entity, &src_pos, hint->items_bytes,
			     hint->items_number);
}

/* Performs shift of items and units from @src_entity to @dst_entity.

   Shift is performed in three passes:

   (1) This pass is supposed to merge two border items in @src_entity and
   @dst_entity if they are mergeable at all. This is needed to prevent creation
   of mergeable items in the same node during consequent shift of whole items.

   (2) Second pass is supposed to move as many whole items from @src_entity to
   @dst_entity as possible. That is exactly how many how does @dst_entity free
   space allow. This is actually main job of node40_shift() function.

   (3) And finally third pass should again merge two border items in @src_entity
   and @dst_entity after some number of whole items was moved to @dst_entity. It
   is needed to use the rest of space remaining after whole items shift in
   second pass. */
static errno_t node40_shift(reiser4_node_t *src_entity,
			    reiser4_node_t *dst_entity,
			    shift_hint_t *hint)
{
	errno_t res;

	aal_assert("umka-2050", src_entity != NULL);
	aal_assert("umka-2051", dst_entity != NULL);

	/* First pass: if merge is allowed, try to merge border items; 
	   otheriwse, check that border items are not mergeable. */
	if (hint->control & SF_ALLOW_MERGE) {
		if ((res = node40_unite(src_entity, dst_entity, hint, 0))) {
			aal_error("Can't merge two nodes during "
				  "node shift operation.");
			return res;
		}
	} else {
		int left_shift;
		reiser4_place_t src_place;
		reiser4_place_t dst_place;
		
		/* Merge is not allowed by @hint->control flags. Check if border
		   items are mergeable. If so, we can't move at least one whole
		   item to @dst_entity, because we have to support all tree
		   invariants and namely there should not be mergeable items in
		   the same node. */
		left_shift = (hint->control & SF_ALLOW_LEFT);

		/* Getting border items and checking if they are mergeable. */
		if ((res = node40_border(src_entity, left_shift, &src_place)))
			return res;

		if ((res = node40_border(dst_entity, !left_shift, &dst_place)))
			return res;
		
		if (node40_core->item_ops.mergeable(&src_place, &dst_place))
			return 0;
	}

	/* Check if insert point is moved to @dst_entity. If so then shift is
	   finished. */
	if (hint->result & SF_MOVE_POINT)
		return 0;

	/* Second pass is started here. Moving some amount of whole items from
	   @src_entity to @dst_entity. */
	if ((res = node40_move(src_entity, dst_entity, hint))) {
		aal_error("Can't move items from the numde %llu to %llu.",
			  src_entity->block->nr, dst_entity->block->nr);
		return res;
	}

	/* Checking if insert point was moved into @dst_entity. If so then shift
	   gets out. */
	if (hint->result & SF_MOVE_POINT)
		return 0;

	/* Third pass is started here. Merges border items with ability to
	   create new item in the @dst_entity. Here our objective is to shift
	   into neighbour node as many units as possible and thus, to fill it
	   up. */
	if (hint->control & SF_ALLOW_MERGE) {
		if ((res = node40_unite(src_entity, dst_entity, hint, 1))) {
			aal_error("Can't unite two nodes during"
				  "node shift operation.");
			return res;
		}
	}

	/* Here is handling the case when insert point is moved to the
	   @dst_entity, but nothing was actually shifted because old insert
	   point was at rightmost node position (last item unexistent unit).
	   Thus, we should set insert point unit component to MAX_UINT32 and
	   thus, to let code on higher abstraction levels know, that unit insert
	   operation should be converted to item insert (create) one. */
	if (hint->control & SF_UPDATE_POINT &&
	    hint->result & SF_MOVE_POINT &&
	    hint->units_number == 0 && hint->create)
	{
		hint->pos.unit = MAX_UINT32;
	}

	return 0;
}

void node40_set_flags(reiser4_node_t *entity, uint32_t pos, uint16_t flags) {
	aal_assert("vpf-1535", node40_items(entity) > pos);
	
	ih_set_flags(node40_ih_at(entity, pos), flags, entity->keypol);
	node40_mkdirty(entity);
}

uint16_t node40_get_flags(reiser4_node_t *entity, uint32_t pos) {
	aal_assert("vpf-1536", node40_items(entity) > pos);
	
	return ih_get_flags(node40_ih_at(entity, pos), entity->keypol);
}

#endif

reiser4_node_plug_t node40_plug = {
	.p = {
		.id    = {NODE_REISER40_ID, 0, NODE_PLUG_TYPE},
#ifndef ENABLE_MINIMAL
		.label = "node40",
		.desc  = "Node plugin.",
#endif
	},
	
	.open		= node40_open,
	.fini		= node40_fini,
	.lookup		= node40_lookup,
	.fetch          = node40_fetch,
	.items		= node40_items,
	
	.get_key	= node40_get_key,
	.get_level	= node40_get_level,
		
#ifndef ENABLE_MINIMAL
	.init		= node40_init,
	.sync           = node40_sync,
	.merge          = node40_merge,

	.pack           = node40_pack,
	.unpack         = node40_unpack,
	
	.insert		= node40_insert,
	.write		= node40_write,
	.trunc          = node40_trunc,
	.remove		= node40_remove,
	.print		= node40_print,
	.shift		= node40_shift,
	.shrink		= node40_shrink,
	.expand		= node40_expand,
	.insert_raw     = node40_insert_raw,
	.copy           = node40_copy,

	.overhead	= node40_overhead,
	.maxspace	= node40_maxspace,
	.space		= node40_space,
	
	.set_key	= node40_set_key,
	.set_level      = node40_set_level,

	.get_mstamp	= node40_get_mstamp,
	.get_fstamp     = node40_get_fstamp,
	
	.set_mstamp	= node40_set_mstamp,
	.set_fstamp     = node40_set_fstamp,
	
	.set_flags	= node40_set_flags,
	.get_flags	= node40_get_flags,

	.set_state      = node40_set_state,
	.get_state      = node40_get_state,
	.check_struct	= node40_check_struct
#endif
};