cde40.c

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

		   from src item to dst item. */
		len = cde40_get_len(src_place, curr);

		if (space < len + en_size(pol))
			break;

		/* Updating unit pos. We will do so in the case item component
		   of insert point is the same as current item has and unit
		   component is not MAX_UINT32. */
		if (check && (flags & SF_UPDATE_POINT)) {
			if (flags & SF_ALLOW_LEFT) {
				/* Insert point is near to be moved into left
				   neighbour. Checking if we are permitted to do
				   so and updating insert point. */
				if (hint->pos.unit == 0) {
					if (flags & SF_MOVE_POINT) {
						hint->result |= SF_MOVE_POINT;
						hint->pos.unit = dst_units;
					}
					
					break;
				} else {
					hint->pos.unit--;
				}
			} else {
				if (hint->pos.unit >= src_units) {
					/* Insert point is near to be shifted in
					   right neighbour. Checking permissions
					   and updating unit component of insert
					   point int hint. */
					if (flags & SF_MOVE_POINT) {
						hint->result |= SF_MOVE_POINT;
						hint->pos.unit = 0;
					}

					break;
				}
			}
		}

		/* Updating unit number counters and some local variables needed
		   for controlling predicting main cycle. */
		src_units--;
		dst_units++;
		hint->units_number++;

		space -= (len + en_size(pol));
		curr += (flags & SF_ALLOW_LEFT ? 1 : -1);
	}

	/* Updating @hint->units_bytes. It is needed for unit shifting. This
	   value is number of bytes to be moved from @src_place to
	   @dst_place. */
	if (hint->units_number > 0)
		hint->units_bytes -= space;
	
	return 0;
}

/* Makes shift of the entries from the @src_place to the @dst_place. */
static errno_t cde40_shift_units(reiser4_place_t *src_place, 
				 reiser4_place_t *dst_place,
				 shift_hint_t *hint)
{
	uint32_t src_pos, dst_pos;
	
	aal_assert("umka-1589", hint != NULL);
	aal_assert("umka-1586", src_place != NULL);
	aal_assert("umka-1587", dst_place != NULL);

	/* Initializing cde body if we shift data to new created item. This is
	   needed for correct work of cde plugin. */
	if (hint->create) {
		hint->units_bytes -= sizeof(cde40_t);
		((cde40_t *)dst_place->body)->units = 0;
	}

	/* Calculating src and dst positions for expanding dst item, copy data
	   to it and shrinking src item. */
	if (hint->control & SF_ALLOW_LEFT) {
		src_pos = 0;
		dst_pos = cde_get_units(dst_place);
	} else {
		dst_pos = 0;
		src_pos = cde_get_units(src_place) -
			hint->units_number;
	}

	/* Preparing root for copying units into it. */
	cde40_expand(dst_place, dst_pos, hint->units_number,
		     hint->units_bytes);

	/* Copying units from @src place to @dst one. */
	cde40_copy(dst_place, dst_pos, src_place,
		   src_pos, hint->units_number);

	cde40_shrink(src_place, src_pos, hint->units_number);

	/* Updating item key by first cde key. */
	if (cde_get_units(src_place) > 0 &&
	    hint->control & SF_ALLOW_LEFT)
	{
		cde40_get_hash(src_place, 0,
			       &src_place->key);
	}

	return 0;
}

/* Estimates how many bytes will be needed to make room for inserting new
   entries. */
static errno_t cde40_prep_insert(reiser4_place_t *place, trans_hint_t *hint) {
	uint32_t i, pol;
	entry_hint_t *entry;
	    
	aal_assert("vpf-095", hint != NULL);
	aal_assert("umka-2424", place != NULL);
	aal_assert("umka-2229", hint->count > 0);

	pol = plugcall(hint->offset.plug, bodysize);
	
	entry = (entry_hint_t *)hint->specific;
	hint->len = (hint->count * en_size(pol));
    
	for (i = 0; i < hint->count; i++, entry++) {
		hint->len += ob_size(pol);

		/* Calling key plugin for in odrer to find 
		   out is passed name is long one or not. */
		if (objcall(&entry->offset, hashed)) {
			/* Okay, name is long, so we need add 
			   its length to estimated length. */
			hint->len += aal_strlen(entry->name) + 1;
		}
	}

	hint->bytes = hint->len;
	
	/* If the pos we are going to insert new units is -1, we assume 
	   it is the attempt to insert new directory item. In this case 
	   we should also count item overhead, that is cde40 header which 
	   contains the number of entries in item. */
	hint->overhead = cde40_overhead();
	
	return 0;
}

/* Inserts new entries to cde item. */
static int64_t cde40_insert_units(reiser4_place_t *place, trans_hint_t *hint) {
	void *entry;
	uint32_t pol, i, offset;
	entry_hint_t *entry_hint;
    
	aal_assert("umka-792", hint != NULL);
	aal_assert("umka-791", place != NULL);

	pol = cde40_key_pol(place);
	entry_hint = (entry_hint_t *)hint->specific;

	/* Initialize body and normalize unit pos in the case of insert new
	   item. */
	if (place->pos.unit == MAX_UINT32) {
		((cde40_t *)place->body)->units = 0;
		place->pos.unit = 0;
	}
	
	/* Expanding direntry in order to prepare the room for new entries. The
	   function cde40_expand() returns the offset of where new unit will be
	   inserted at. */
	offset = cde40_expand(place, place->pos.unit,
			      hint->count, hint->len);

	entry = cde40_entry(place, place->pos.unit);
	
	/* Creating new entries */
	for (i = 0; i < hint->count; i++, entry_hint++) {
		void *objid;
		uint64_t oid;
		uint64_t off;
		uint64_t ord;

		reiser4_key_t *hash;
		reiser4_key_t *object;

		objid = place->body + offset;
		
		/* Setting up the offset of new entry */
		en_set_offset(entry, offset, pol);
		hash = &entry_hint->offset;
		
		/* Setting up ordering component of hash */
		ord = objcall(hash, get_ordering);
		
		ha_set_ordering(entry, ord, pol);
		
		/* Setting up objectid component of hash */
		oid = objcall(hash, get_fobjectid);
		
		ha_set_objectid(entry, oid, pol);

		/* Setting up offset component of hash */
		off = objcall(hash, get_offset);

		ha_set_offset(entry, off, pol);

		/* Setting up objid fields */
		object = &entry_hint->object;

		aal_memcpy(objid, object->body,
			   ob_size(pol));

		offset += ob_size(pol);

		/* If key is long one we also count name length */
		if (objcall(&entry_hint->offset, hashed)) {
			uint32_t len = aal_strlen(entry_hint->name);

			aal_memcpy(place->body + offset,
				   entry_hint->name, len);

			offset += len;
			*((char *)place->body + offset) = '\0';
			offset++;
		}

		entry += en_size(pol);
	}
	
	cde_inc_units(place, hint->count);
	
	/* Updating item key by unit key if the first unit was changed. It is
	   needed for correct updating left delimiting keys. */
	if (place->pos.unit == 0)
		cde40_get_hash(place, 0, &place->key);

	place_mkdirty(place);
	return hint->count;
}

/* Remove some number of entries (based on passed @hint) from cde40 item
   starting from @pos. */
errno_t cde40_delete(reiser4_place_t *place, uint32_t pos,
		     trans_hint_t *hint)
{
	uint32_t pol;

	aal_assert("umka-3024", pos < cde40_units(place));

	pol = cde40_key_pol(place);
	
	/* Shrinking cde item */
	hint->bytes = hint->len = cde40_shrink(place, pos, hint->count);
	
	/* Updating item key */
	if (pos == 0 && cde40_units(place) > 0)
		cde40_get_hash(place, 0, &place->key);

	/* Setting up cde item overhead in the case we removed all units. */
	hint->overhead = (cde40_units(place) == 0) ? 
		cde40_overhead() : 0;
	
	return 0;
}

/* Removes @count entries at @pos from passed @place */
static errno_t cde40_remove_units(reiser4_place_t *place, trans_hint_t *hint) {
	aal_assert("umka-934", place != NULL);
	aal_assert("umka-2400", hint != NULL);

	return cde40_delete(place, place->pos.unit, hint);
}

/* Fuses bodies of two cde items that lie in the same node. */
static int32_t cde40_merge(reiser4_place_t *left_place, 
			   reiser4_place_t *right_place) 
{
	void *buf;
	void *entry;
	uint32_t pol;
	uint32_t size;
	uint32_t offset;
	uint32_t i, units;
	
	aal_assert("umka-2687", left_place != NULL);
	aal_assert("umka-2689", right_place != NULL);
	
	pol = cde40_key_pol(left_place);
	
	units = cde_get_units(left_place);
	
	/* Right entry headers to be copied to buffer. */
	size = cde_get_units(right_place) * en_size(pol);
	
	/* Offset of left entry bodies. */
	offset = sizeof(cde40_t) + cde_get_units(left_place) * en_size(pol);

	/* Set the correct amount of units. */
	cde_inc_units(left_place, cde_get_units(right_place));
	
	/* Eliminating right item header and return header size as space
	   released as result of merge. */
	aal_memmove(right_place->body, 
		    right_place->body + sizeof(cde40_t), 
		    right_place->len - sizeof(cde40_t));

	/* Allocate the buffer for the right entry headers and copy them. */
	buf = aal_malloc(size);
	aal_memcpy(buf, right_place->body, size);
	
	/* Move left item bodies to the right. */
	aal_memmove(left_place->body + offset + size, 
		    left_place->body + offset, 
		    left_place->len - offset);
	
	/* Copy the right entry headers to the freed space in the left item. */
	aal_memcpy(left_place->body + offset, buf, size);

	aal_free(buf);
	
	offset = size;
	entry = cde40_entry(left_place, 0);
	
	/* Update left offsets. */
	for (i = 0; i < units; i++) {
		en_inc_offset(entry, offset, pol);
		entry += en_size(pol);
	}
	
	offset = left_place->len - sizeof(cde40_t);
	entry = cde40_entry(left_place, units);
	
	/* Update right offsets. */
	for (i = units; i < cde_get_units(left_place); i++) {
		en_inc_offset(entry, offset, pol);
		entry += en_size(pol);
	}
	
	return sizeof(cde40_t);
}

/* Returns real maximal key in cde item */
static errno_t cde40_maxreal_key(reiser4_place_t *place, 
				 reiser4_key_t *key) 
{
	uint32_t units;
	
	aal_assert("umka-1651", key != NULL);
	aal_assert("umka-1650", place != NULL);

	units = cde40_units(place);
	return cde40_get_hash(place, units - 1, key);
}

static uint64_t cde40_size(reiser4_place_t *place) {
	aal_assert("umka-2677", place != NULL);
	return cde40_units(place);
}

static uint64_t cde40_bytes(reiser4_place_t *place) {
	aal_assert("vpf-1211", place != NULL);
	return (place->len - sizeof(uint16_t));
}

lookup_t cde40_collision(reiser4_place_t *place, coll_hint_t *hint) {
	reiser4_key_t hash;
	uint32_t units;
	char name[256];
	
	aal_assert("vpf-1548", place != NULL);
	aal_assert("vpf-1549", hint != NULL);
	aal_assert("vpf-1549", hint->type == DIR_ITEM);

	if (place->pos.unit == MAX_UINT32)
		place->pos.unit = 0;
	
	units = cde40_units(place);
	
	if (place->pos.unit >= units)
		return ABSENT;
	
	cde40_get_hash(place, place->pos.unit, &hash);
	
	for (; place->pos.unit < units; place->pos.unit++) {
		/* Compare the key first. If differs, there is no match. */
		if (cde40_comp_hash(place, place->pos.item, &hash))
			return ABSENT;

		/* Key matches, comp the name. It may happen only with not 
		   packed names. */
		cde40_get_name(place, place->pos.item, name, 256);

		if (!aal_strcmp(name, hint->specific))
			return PRESENT;

		/* Names are not sorted. Continue. */
	}
	
	return ABSENT;
}
#endif

/* Returns maximal possible key in passed item. It is needed during lookup and
   in other cases. */
errno_t cde40_maxposs_key(reiser4_place_t *place, 
			  reiser4_key_t *key) 
{
	reiser4_key_t *maxkey;
	
	aal_assert("umka-1649", key != NULL);
	aal_assert("umka-1648", place != NULL);
	
	aal_memcpy(key, &place->key, sizeof(*key));
	
	/* Getting maximal key from current key plugin. */
	maxkey = plugcall(key->plug, maximal);
	
	/* Setting up @key by mans of putting to it offset, ordering and
	   objectid from values from maximal key. */
    	plugcall(key->plug, set_ordering, key, objcall(maxkey, get_ordering));
    	plugcall(key->plug, set_objectid, key, objcall(maxkey, get_objectid));
	plugcall(key->plug, set_offset, key, objcall(maxkey, get_offset));
	
	return 0;
}

/* Compare the given key with the entry at the given pos. */
int cde40_comp_hash(reiser4_place_t *place, uint32_t pos, reiser4_key_t *key) {
	reiser4_key_t curr;

	cde40_get_hash(place, pos, &curr);
	return objcall(&curr, compfull, key);
}

/* Helper function that is used by lookup method for 
   comparing given key with passed entry hash. */
static int cb_comp_hash(void *array, uint32_t pos,
			void *key, void *data)
{
	return cde40_comp_hash((reiser4_place_t *)data, pos, 
			       (reiser4_key_t *)key);
}

/* Performs lookup inside cde item. Found position is stored in @pos. */
lookup_t cde40_lookup(reiser4_place_t *place,
		      lookup_hint_t *hint,
		      lookup_bias_t bias)
{
#ifndef ENABLE_MINIMAL
	int32_t i;
#endif

	aal_assert("umka-610", hint != NULL);
	aal_assert("umka-609", place != NULL);
    
	/* Bin search within the cde item to get the position of 
	   the wanted key. */
	switch (aux_bin_search(place->body, cde40_units(place),
			       hint->key, cb_comp_hash,
			       place, &place->pos.unit))
	{
	case 1:
#ifndef ENABLE_MINIMAL
		/* Making sure, that we have found right unit. This is needed
		   because of possible key collision. We move left direction
		   until we find a key smaller than passed one. */
		for (i = place->pos.unit - 1; i >= 0; i--) {
			/* Comparing keys. We break the loop when keys as not
			   equal, that means, that we have found needed pos. */
			if (!cde40_comp_hash(place, i, hint->key))
				place->pos.unit = i;
			else
				return PRESENT;
		}
#endif
		return PRESENT;
	case 0:
		return (bias == FIND_CONV ? PRESENT : ABSENT);
	default:
		return -EIO;
	}
}

static item_balance_ops_t balance_ops = {
#ifndef ENABLE_MINIMAL
	.merge		  = cde40_merge, 
	.mergeable	  = cde40_mergeable,
	.prep_shift	  = cde40_prep_shift,
	.shift_units	  = cde40_shift_units,
        .maxreal_key	  = cde40_maxreal_key,
	.update_key	  = cde40_update_key,
	.collision	  = cde40_collision,
	.overhead	  = cde40_overhead,
#endif
	.init		  = NULL,
	.units		  = cde40_units,
	.lookup		  = cde40_lookup,
	.fetch_key	  = cde40_fetch_key,
	.maxposs_key	  = cde40_maxposs_key
};

static item_object_ops_t object_ops = {
	.fetch_units	  = cde40_fetch_units,
	
#ifndef ENABLE_MINIMAL
	.prep_insert	  = cde40_prep_insert,
	.insert_units	  = cde40_insert_units,
	.remove_units	  = cde40_remove_units,
	
	.size		  = cde40_size,
	.bytes		  = cde40_bytes,
	 
	.update_units	  = NULL,
	.prep_write	  = NULL,
	.write_units	  = NULL,
	.trunc_units	  = NULL,
	.layout		  = NULL,
#endif
	.read_units	  = NULL
};

#ifndef ENABLE_MINIMAL
static item_debug_ops_t debug_ops = {
	.print		  = cde40_print
};

static item_repair_ops_t repair_ops = {
	.check_struct	  = cde40_check_struct,
	.check_layout	  = NULL,

	.prep_insert_raw  = cde40_prep_insert_raw,
	.insert_raw	  = cde40_insert_raw,

	.pack		  = NULL,
	.unpack		  = NULL
};
#endif

reiser4_item_plug_t cde40_plug = {
	.p = {
		.id    = {ITEM_CDE40_ID, DIR_ITEM, ITEM_PLUG_TYPE},
#ifndef ENABLE_MINIMAL
		.label = "cde40",
		.desc  = "Compound directory entry item plugin.",
#endif
	},
	
	.object		  = &object_ops,
	.balance	  = &balance_ops,
#ifndef ENABLE_MINIMAL
	.repair		  = &repair_ops,
	.debug		  = &debug_ops
#endif

};