// if root directory is empty - we set default - Yura's - hash and
// warn about it
// FIXME: we look for only one name in a directory. If tea and yura
// bith have the same value - we ask user to send report to the
// mailing list
__u32 find_hash_out (struct super_block * s)
{
    int retval;
    struct inode * inode;
    struct cpu_key key;
    INITIALIZE_PATH (path);
    struct reiserfs_dir_entry de;
    __u32 hash = DEFAULT_HASH;

    inode = s->s_root->d_inode;

    do { // Some serious "goto"-hater was there ;)
	u32 teahash, r5hash, yurahash;

	make_cpu_key (&key, inode, ~0, TYPE_DIRENTRY, 3);
	retval = search_by_entry_key (s, &key, &path, &de);
	if (retval == IO_ERROR) {
	    pathrelse (&path);
	    return UNSET_HASH ;
	}
	if (retval == NAME_NOT_FOUND)
	    de.de_entry_num --;
	set_de_name_and_namelen (&de);
	if (deh_offset( &(de.de_deh[de.de_entry_num]) ) == DOT_DOT_OFFSET) {
	    /* allow override in this case */
	    if (reiserfs_rupasov_hash(s)) {
		hash = YURA_HASH ;
	    }
	    reiserfs_warning("reiserfs: FS seems to be empty, autodetect "
	                     "is using the default hash\n");
	    break;
	}
	r5hash=GET_HASH_VALUE (r5_hash (de.de_name, de.de_namelen));
	teahash=GET_HASH_VALUE (keyed_hash (de.de_name, de.de_namelen));
	yurahash=GET_HASH_VALUE (yura_hash (de.de_name, de.de_namelen));
	if ( ( (teahash == r5hash) && (GET_HASH_VALUE( deh_offset(&(de.de_deh[de.de_entry_num]))) == r5hash) ) ||
	     ( (teahash == yurahash) && (yurahash == GET_HASH_VALUE( deh_offset(&(de.de_deh[de.de_entry_num])))) ) ||
	     ( (r5hash == yurahash) && (yurahash == GET_HASH_VALUE( deh_offset(&(de.de_deh[de.de_entry_num])))) ) ) {
	    reiserfs_warning("reiserfs: Unable to automatically detect hash"
		"function for device %s\n"
		"please mount with -o hash={tea,rupasov,r5}\n", kdevname (s->s_dev));
	    hash = UNSET_HASH;
	    break;
	}
	if (GET_HASH_VALUE( deh_offset(&(de.de_deh[de.de_entry_num])) ) == yurahash)
	    hash = YURA_HASH;
	else if (GET_HASH_VALUE( deh_offset(&(de.de_deh[de.de_entry_num])) ) == teahash)
	    hash = TEA_HASH;
	else if (GET_HASH_VALUE( deh_offset(&(de.de_deh[de.de_entry_num])) ) == r5hash)
	    hash = R5_HASH;
	else {
	    reiserfs_warning("reiserfs: Unrecognised hash function for "
			     "device %s\n", kdevname (s->s_dev));
	    hash = UNSET_HASH;
	}
    } while (0);

    pathrelse (&path);
    return hash;
}

int reiserfs_link (struct dentry * old_dentry, struct inode * dir, struct dentry * dentry)
{
  struct inode *inode = old_dentry->d_inode;
  struct path path_to_entry;
  struct reiserfs_dir_entry de;
  int error;
  int windex ;
  struct reiserfs_transaction_handle th ;
  int jbegin_count = JOURNAL_PER_BALANCE_CNT * 3; 
  
  init_path (&path_to_entry);

  /* object must not be directory */
  if (S_ISDIR(inode->i_mode)) {
    return -EPERM;
  }
  
  /* file has too many links */
  if (inode->i_nlink >= REISERFS_LINK_MAX) {
    return -EMLINK;
  }

  journal_begin(&th, dir->i_sb, jbegin_count) ;
  windex = push_journal_writer("reiserfs_link") ;

  reiserfs_update_inode_transaction(inode) ;
  reiserfs_update_inode_transaction(dir) ;

  de.de_gen_number_bit_string = 0;
  if (reiserfs_find_entry (dir, dentry->d_name.name, dentry->d_name.len, &path_to_entry, &de) == POSITION_FOUND) {
    pathrelse (&path_to_entry);
    pop_journal_writer(windex) ;
    journal_end(&th, dir->i_sb, jbegin_count) ;
    return -EEXIST;
  }
  
  pathrelse (&path_to_entry);

  /* free preserve list if we should */
/*  maybe_free_preserve_list (dir->i_sb);*/

  /* create new entry */
  error = reiserfs_add_entry (&th, dir, dentry->d_name.name, dentry->d_name.len, INODE_PKEY (inode), &de, 1);
  if (error) {
    pop_journal_writer(windex) ;
    journal_end(&th, dir->i_sb, jbegin_count) ;
    return error;
  }
  inode->i_nlink++;
  inode->i_ctime = CURRENT_TIME;
  if_in_ram_update_sd (&th, inode);
  if_in_ram_update_sd (&th, dir);
  inode->i_count++;
  d_instantiate(dentry, inode);
  pop_journal_writer(windex) ;
  journal_end(&th, dir->i_sb, jbegin_count) ;
  return 0;
}

/* The function is NOT SCHEDULE-SAFE! */
int search_by_entry_key(struct super_block *sb, const struct cpu_key *key,
			struct treepath *path, struct reiserfs_dir_entry *de)
{
	int retval;

	retval = search_item(sb, key, path);
	switch (retval) {
	case ITEM_NOT_FOUND:
		if (!PATH_LAST_POSITION(path)) {
			reiserfs_error(sb, "vs-7000", "search_by_key "
				       "returned item position == 0");
			pathrelse(path);
			return IO_ERROR;
		}
		PATH_LAST_POSITION(path)--;

	case ITEM_FOUND:
		break;

	case IO_ERROR:
		return retval;

	default:
		pathrelse(path);
		reiserfs_error(sb, "vs-7002", "no path to here");
		return IO_ERROR;
	}

	set_de_item_location(de, path);

#ifdef CONFIG_REISERFS_CHECK
	if (!is_direntry_le_ih(de->de_ih) ||
	    COMP_SHORT_KEYS(&de->de_ih->ih_key, key)) {
		print_block(de->de_bh, 0, -1, -1);
		reiserfs_panic(sb, "vs-7005", "found item %h is not directory "
			       "item or does not belong to the same directory "
			       "as key %K", de->de_ih, key);
	}
#endif				/* CONFIG_REISERFS_CHECK */

	/*
	 * binary search in directory item by third component of the
	 * key. sets de->de_entry_num of de
	 */
	retval = bin_search_in_dir_item(de, cpu_key_k_offset(key));
	path->pos_in_item = de->de_entry_num;
	if (retval != NAME_NOT_FOUND) {
		/*
		 * ugly, but rename needs de_bh, de_deh, de_name,
		 * de_namelen, de_objectid set
		 */
		set_de_name_and_namelen(de);
		set_de_object_key(de);
	}
	return retval;
}

/*
 * We assign a key to each directory item, and place multiple entries in
 * a single directory item. A directory item has a key equal to the key
 * of the first directory entry in it.
 *
 * This function first calls search_by_key, then, if item whose first
 * entry matches is not found it looks for the entry inside directory
 * item found by search_by_key. Fills the path to the entry, and to the
 * entry position in the item
 */
int
search_by_entry_key(struct reiserfs_sb_info *sbi,
    const struct cpu_key *key, struct path *path,
    struct reiserfs_dir_entry *de)
{
	int retval;

	reiserfs_log(LOG_DEBUG, "searching in (objectid=%d,dirid=%d)\n",
	    key->on_disk_key.k_objectid, key->on_disk_key.k_dir_id);
	retval = search_item(sbi, key, path);
	switch (retval) {
	case ITEM_NOT_FOUND:
		if (!PATH_LAST_POSITION(path)) {
			reiserfs_log(LOG_DEBUG,
			    "search_by_key returned item position == 0");
			pathrelse(path);
			return (IO_ERROR);
		}
		PATH_LAST_POSITION(path)--;
		reiserfs_log(LOG_DEBUG, "search_by_key did not found it\n");
		break;
	case ITEM_FOUND:
		reiserfs_log(LOG_DEBUG, "search_by_key found it\n");
		break;
	case IO_ERROR:
		return (retval);
	default:
		pathrelse(path);
		reiserfs_log(LOG_DEBUG, "no path to here");
		return (IO_ERROR);
	}

	reiserfs_log(LOG_DEBUG, "set item location\n");
	set_de_item_location(de, path);

	/*
	 * Binary search in directory item by third component of the
	 * key. Sets de->de_entry_num of de
	 */
	reiserfs_log(LOG_DEBUG, "bin_search_in_dir_item\n");
	retval = bin_search_in_dir_item(de, cpu_key_k_offset(key));
	path->pos_in_item = de->de_entry_num;
	if (retval != NAME_NOT_FOUND) {
		/*
		 * Ugly, but rename needs de_bp, de_deh, de_name, de_namelen,
		 * de_objectid set
		 */
		set_de_name_and_namelen(de);
		set_de_object_key(de);
		reiserfs_log(LOG_DEBUG, "set (objectid=%d,dirid=%d)\n",
		    de->de_objectid, de->de_dir_id);
	}

	return (retval);
}

/*
** looks up the dentry of the parent directory for child.
** taken from ext2_get_parent
*/
struct dentry *reiserfs_get_parent(struct dentry *child)
{
	int retval;
	struct inode *inode = NULL;
	struct reiserfs_dir_entry de;
	INITIALIZE_PATH(path_to_entry);
	struct inode *dir = child->d_inode;

	if (dir->i_nlink == 0) {
		return ERR_PTR(-ENOENT);
	}
	de.de_gen_number_bit_string = NULL;

	reiserfs_write_lock(dir->i_sb);
	retval = reiserfs_find_entry(dir, "..", 2, &path_to_entry, &de);
	pathrelse(&path_to_entry);
	if (retval != NAME_FOUND) {
		reiserfs_write_unlock(dir->i_sb);
		return ERR_PTR(-ENOENT);
	}
	inode = reiserfs_iget(dir->i_sb, (struct cpu_key *)&(de.de_dir_id));
	reiserfs_write_unlock(dir->i_sb);

	return d_obtain_alias(inode);
}

/* 
** looks up the dentry of the parent directory for child.
** taken from ext2_get_parent
*/
struct dentry *reiserfs_get_parent(struct dentry *child)
{
    int retval;
    struct inode * inode = NULL;
    struct reiserfs_dir_entry de;
    INITIALIZE_PATH (path_to_entry);
    struct dentry *parent;
    struct inode *dir = child->d_inode ;


    if (dir->i_nlink == 0) {
	return ERR_PTR(-ENOENT);
    }
    de.de_gen_number_bit_string = NULL;

    reiserfs_write_lock(dir->i_sb);
    retval = reiserfs_find_entry (dir, "..", 2, &path_to_entry, &de);
    pathrelse (&path_to_entry);
    if (retval != NAME_FOUND) {
	reiserfs_write_unlock(dir->i_sb);
	return ERR_PTR(-ENOENT);
    }
    inode = reiserfs_iget (dir->i_sb, (struct cpu_key *)&(de.de_dir_id));
    reiserfs_write_unlock(dir->i_sb);

    if (!inode || IS_ERR(inode)) {
	return ERR_PTR(-EACCES);
    }
    parent = d_alloc_anon(inode);
    if (!parent) {
	iput(inode);
	parent = ERR_PTR(-ENOMEM);
    }
    return parent;
}

int reiserfs_remove_entry (reiserfs_filsys_t fs, struct key * key)
{
    struct path path;
    struct tree_balance tb;
    struct item_head * ih;
    struct reiserfs_de_head * deh;

    if (_search_by_entry_key (fs, key, &path) != POSITION_FOUND) {
	pathrelse (&path);
	return 1;
    }

    ih = get_ih (&path);
    if (ih_entry_count (ih) == 1) {
	_init_tb_struct (&tb, fs, &path, -(IH_SIZE + ih_item_len (ih)));
	if (fix_nodes (M_DELETE, &tb, 0) != CARRY_ON) {
	    unfix_nodes (&tb);
	    return 1;
	}
	do_balance (&tb, 0, 0, M_DELETE, 0);
	return 0;
    }

    deh = B_I_DEH (get_bh (&path), ih) + path.pos_in_item;
    _init_tb_struct (&tb, fs, &path, -(DEH_SIZE + entry_length (ih, deh, path.pos_in_item)));
    if (fix_nodes (M_CUT, &tb, 0) != CARRY_ON) {
	unfix_nodes (&tb);
	return 1;
    }
    do_balance (&tb, 0, 0, M_CUT, 0);
    return 0;
}

static int _search_by_key (reiserfs_filsys_t fs, struct key * key, struct path * path)
{
    struct buffer_head * bh;
    unsigned long block = SB_ROOT_BLOCK (fs);
    struct path_element * curr;
    int retval;
    
    path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
    while (1) {
	curr = PATH_OFFSET_PELEMENT (path, ++ path->path_length);
	bh = curr->pe_buffer = bread (fs->s_dev, block, fs->s_blocksize);
        if (bh == 0) {
	    path->path_length --;
	    pathrelse (path);
	    return ITEM_NOT_FOUND;
	}
	retval = _bin_search (key, B_N_PKEY (bh, 0), B_NR_ITEMS (bh),
			      is_leaf_node (bh) ? IH_SIZE : KEY_SIZE, &(curr->pe_position), comp_keys);
	if (retval == ITEM_FOUND) {
	    /* key found, return if this is leaf level */
	    if (is_leaf_node (bh)) {
		path->pos_in_item = 0;
		return ITEM_FOUND;
	    }
	    curr->pe_position ++;
	} else {
	    /* key not found in the node */
	    if (is_leaf_node (bh))
		return ITEM_NOT_FOUND;
	}
	block = B_N_CHILD_NUM (bh, curr->pe_position);
    }
    printf ("search_by_key: you can not get here\n");
    return ITEM_NOT_FOUND;
}

static int reiserfs_find_entry (struct inode * dir, const char * name, int namelen, struct path * path_to_entry, struct reiserfs_dir_entry * de)
{
  struct key key_to_search;
  int repeat;
  int retval;

  if (!dir || !dir->i_sb)
    return POSITION_NOT_FOUND;

  if ((unsigned int)namelen > REISERFS_MAX_NAME_LEN (dir->i_sb->s_blocksize))
    return POSITION_NOT_FOUND;

  /* there are no entries having the same third component of key, so
     fourth key component is not used */
  copy_key (&key_to_search, INODE_PKEY (dir));
  key_to_search.k_offset = get_third_component (name, namelen);
  key_to_search.k_uniqueness = DIRENTRY_UNIQUENESS;

  while (1) {
    /* search for a directory item using the formed key */
    if (search_by_key (dir->i_sb, &key_to_search, path_to_entry, &repeat, DISK_LEAF_NODE_LEVEL, READ_BLOCKS) == ITEM_NOT_FOUND) {
      /* take previous item */
#ifdef REISERFS_CHECK
      if (!PATH_LAST_POSITION (path_to_entry))
	reiserfs_panic (dir->i_sb, "vs-7010: reiserfs_find_entry: search_by_key returned bad position == 0");
#endif /* REISERFS_CHECK */
      PATH_LAST_POSITION (path_to_entry) --;
    }
    
    de->de_bh = PATH_PLAST_BUFFER (path_to_entry);
    de->de_item_num = PATH_LAST_POSITION (path_to_entry);
    de->de_ih = B_N_PITEM_HEAD (de->de_bh, de->de_item_num);
    de->de_deh = B_I_DEH (de->de_bh, de->de_ih);

#ifdef REISERFS_CHECK
    if (!I_IS_DIRECTORY_ITEM (de->de_ih) || COMP_SHORT_KEYS (&(de->de_ih->ih_key), INODE_PKEY (dir)))
      reiserfs_panic (dir->i_sb, "vs-7020: reiserfs_find_entry: item must be an item of the same directory item as inode");
#endif /* REISERFS_CHECK */

    /* we do not check whether bin_search_in_dir_item found the given key, even if so, we still have
       to compare names */
    bin_search_in_dir_item (de->de_ih, de->de_deh, &key_to_search, &(de->de_entry_num));

    /* compare names for all entries having given hash value */
    retval = linear_search_in_dir_item (&key_to_search, de, name, namelen);
    if (retval != GOTO_PREVIOUS_ITEM)
      /* there is no need to scan directory anymore. Given entry found or does not exist */
      return retval;

    /* there is left neighboring item of this directory and given entry can be there */
    key_to_search.k_offset = de->de_ih->ih_key.k_offset - 1;
    pathrelse (path_to_entry);

  } /* while (1) */
}

/*
 * May return NAME_FOUND, NAME_FOUND_INVISIBLE, NAME_NOT_FOUND
 * FIXME: should add something like IOERROR
 */
static int
reiserfs_find_entry(struct reiserfs_node *dp, const char *name, int namelen,
    struct path * path_to_entry, struct reiserfs_dir_entry *de)
{
	struct cpu_key key_to_search;
	int retval;

	if (namelen > REISERFS_MAX_NAME(dp->i_reiserfs->s_blocksize))
		return NAME_NOT_FOUND;

	/* We will search for this key in the tree */
	make_cpu_key(&key_to_search, dp,
	    get_third_component(dp->i_reiserfs, name, namelen),
	    TYPE_DIRENTRY, 3);

	while (1) {
		reiserfs_log(LOG_DEBUG, "search by entry key\n");
		retval = search_by_entry_key(dp->i_reiserfs, &key_to_search,
		    path_to_entry, de);
		if (retval == IO_ERROR) {
			reiserfs_log(LOG_DEBUG, "IO error in %s\n",
			    __FUNCTION__);
			return IO_ERROR;
		}

		/* Compare names for all entries having given hash value */
		reiserfs_log(LOG_DEBUG, "linear search for `%s'\n", name);
		retval = linear_search_in_dir_item(&key_to_search, de,
		    name, namelen);
		if (retval != GOTO_PREVIOUS_ITEM) {
			/*
			 * There is no need to scan directory anymore.
			 * Given entry found or does not exist
			 */
			reiserfs_log(LOG_DEBUG, "linear search returned "
			    "(objectid=%d,dirid=%d)\n",
			    de->de_objectid, de->de_dir_id);
			path_to_entry->pos_in_item = de->de_entry_num;
			return retval;
		}

		/*
		 * There is left neighboring item of this directory and
		 * given entry can be there
		 */
		set_cpu_key_k_offset(&key_to_search,
		    le_ih_k_offset(de->de_ih) - 1);
		pathrelse(path_to_entry);  
	} /* while (1) */
}

static struct dentry *reiserfs_lookup(struct inode *dir, struct dentry *dentry,
				      struct nameidata *nd)
{
	int retval;
	struct inode *inode = NULL;
	struct reiserfs_dir_entry de;
	INITIALIZE_PATH(path_to_entry);

	if (REISERFS_MAX_NAME(dir->i_sb->s_blocksize) < dentry->d_name.len)
		return ERR_PTR(-ENAMETOOLONG);

	reiserfs_write_lock(dir->i_sb);
	de.de_gen_number_bit_string = NULL;
	retval =
	    reiserfs_find_entry(dir, dentry->d_name.name, dentry->d_name.len,
				&path_to_entry, &de);
	pathrelse(&path_to_entry);
	if (retval == NAME_FOUND) {
		/* Hide the .reiserfs_priv directory */
		if (reiserfs_xattrs(dir->i_sb) &&
		    !old_format_only(dir->i_sb) &&
		    REISERFS_SB(dir->i_sb)->priv_root &&
		    REISERFS_SB(dir->i_sb)->priv_root->d_inode &&
		    de.de_objectid ==
		    le32_to_cpu(INODE_PKEY
				(REISERFS_SB(dir->i_sb)->priv_root->d_inode)->
				k_objectid)) {
			reiserfs_write_unlock(dir->i_sb);
			return ERR_PTR(-EACCES);
		}

		inode =
		    reiserfs_iget(dir->i_sb, (struct cpu_key *)&(de.de_dir_id));
		if (!inode || IS_ERR(inode)) {
			reiserfs_write_unlock(dir->i_sb);
			return ERR_PTR(-EACCES);
		}

		/* Propogate the priv_object flag so we know we're in the priv tree */
		if (is_reiserfs_priv_object(dir))
			reiserfs_mark_inode_private(inode);
	}
	reiserfs_write_unlock(dir->i_sb);
	if (retval == IO_ERROR) {
		return ERR_PTR(-EIO);
	}

	return d_splice_alias(inode, dentry);
}

/*
 * may return NAME_FOUND, NAME_FOUND_INVISIBLE, NAME_NOT_FOUND
 * FIXME: should add something like IOERROR
 */
static int reiserfs_find_entry(struct inode *dir, const char *name, int namelen,
			       struct treepath *path_to_entry,
			       struct reiserfs_dir_entry *de)
{
	struct cpu_key key_to_search;
	int retval;

	if (namelen > REISERFS_MAX_NAME(dir->i_sb->s_blocksize))
		return NAME_NOT_FOUND;

	/* we will search for this key in the tree */
	make_cpu_key(&key_to_search, dir,
		     get_third_component(dir->i_sb, name, namelen),
		     TYPE_DIRENTRY, 3);

	while (1) {
		retval =
		    search_by_entry_key(dir->i_sb, &key_to_search,
					path_to_entry, de);
		if (retval == IO_ERROR) {
			reiserfs_error(dir->i_sb, "zam-7001", "io error");
			return IO_ERROR;
		}

		/* compare names for all entries having given hash value */
		retval =
		    linear_search_in_dir_item(&key_to_search, de, name,
					      namelen);
		/*
		 * there is no need to scan directory anymore.
		 * Given entry found or does not exist
		 */
		if (retval != GOTO_PREVIOUS_ITEM) {
			path_to_entry->pos_in_item = de->de_entry_num;
			return retval;
		}

		/*
		 * there is left neighboring item of this directory
		 * and given entry can be there
		 */
		set_cpu_key_k_offset(&key_to_search,
				     le_ih_k_offset(de->de_ih) - 1);
		pathrelse(path_to_entry);

	}			/* while (1) */
}

/* Decrement b_count field of the all buffers in the path. */
void
decrement_counters_in_path(struct path *p_s_search_path)
{

	pathrelse(p_s_search_path);
#if 0
	int n_path_offset = p_s_search_path->path_length;

	while (n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET) {
		struct buf *bp;

		bp = PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--);
		decrement_bcount(bp);
	}

	p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
#endif
}

struct dentry * reiserfs_lookup (struct inode * dir, struct dentry * dentry)
{
  struct inode * inode = 0;
  struct reiserfs_dir_entry de;
  struct path path_to_entry;
  int error;

  init_path (&path_to_entry);

  de.de_gen_number_bit_string = 0;
  error = reiserfs_find_entry (dir, dentry->d_name.name, dentry->d_name.len, &path_to_entry, &de);
  pathrelse (&path_to_entry);
  if (error == POSITION_FOUND) {
    inode = reiserfs_iget (dir->i_sb, (struct key *)&(de.de_dir_id));
    if (!inode)
      return ERR_PTR(-EACCES);
  }

  d_add(dentry, inode);
  return NULL;
}

static struct dentry *reiserfs_lookup(struct inode *dir, struct dentry *dentry,
				      unsigned int flags)
{
	int retval;
	struct inode *inode = NULL;
	struct reiserfs_dir_entry de;
	INITIALIZE_PATH(path_to_entry);

	if (REISERFS_MAX_NAME(dir->i_sb->s_blocksize) < dentry->d_name.len)
		return ERR_PTR(-ENAMETOOLONG);

	reiserfs_write_lock(dir->i_sb);

	de.de_gen_number_bit_string = NULL;
	retval =
	    reiserfs_find_entry(dir, dentry->d_name.name, dentry->d_name.len,
				&path_to_entry, &de);
	pathrelse(&path_to_entry);
	if (retval == NAME_FOUND) {
		inode = reiserfs_iget(dir->i_sb,
				      (struct cpu_key *)&de.de_dir_id);
		if (!inode || IS_ERR(inode)) {
			reiserfs_write_unlock(dir->i_sb);
			return ERR_PTR(-EACCES);
		}

		/*
		 * Propagate the private flag so we know we're
		 * in the priv tree
		 */
		if (IS_PRIVATE(dir))
			inode->i_flags |= S_PRIVATE;
	}
	reiserfs_write_unlock(dir->i_sb);
	if (retval == IO_ERROR) {
		return ERR_PTR(-EIO);
	}

	return d_splice_alias(inode, dentry);
}

int reiserfs_unlink (struct inode * dir, struct dentry *dentry)
{
  int retval;
  struct inode * inode;
  struct reiserfs_dir_entry de;
  struct path path;
  int windex ;
  int call_journal_end = 1 ;
  struct reiserfs_transaction_handle th ;
  int jbegin_count = JOURNAL_PER_BALANCE_CNT * 3; 

  init_path (&path);

  retval = -ENOENT;
	
  journal_begin(&th, dir->i_sb, jbegin_count) ;
  windex = push_journal_writer("reiserfs_unlink") ;
  /* free preserve list if we should */
/*  maybe_free_preserve_list (dir->i_sb);*/
	
  de.de_gen_number_bit_string = 0;
  if (reiserfs_find_entry (dir, dentry->d_name.name, dentry->d_name.len, &path, &de) == POSITION_NOT_FOUND) {
    goto end_unlink;
  }

  inode = dentry->d_inode;

  reiserfs_update_inode_transaction(inode) ;
  reiserfs_update_inode_transaction(dir) ;

  retval = -EPERM;
  if (S_ISDIR (inode->i_mode)) {
    goto end_unlink;
  }
  if ((dir->i_mode & S_ISVTX) && !fsuser() &&
      current->fsuid != inode->i_uid &&
      current->fsuid != dir->i_uid) {
    goto end_unlink;
  }

  retval = -ENOENT;
  if (comp_short_keys ((struct key *)&(de.de_dir_id), INODE_PKEY (inode))) {
    goto end_unlink;
  }
  
  if (!inode->i_nlink) {
    printk("reiserfs_unlink: deleting nonexistent file (%s:%lu), %d\n",
	   kdevname(inode->i_dev), inode->i_ino, inode->i_nlink);
    inode->i_nlink = 1;
  }
  if (reiserfs_cut_from_item (&th, dir, dir->i_sb, &path, &(de.de_entry_num), &(de.de_entry_key), 0, NOTHING_SPECIAL) == 0) {
    retval = -ENOENT;
    goto end_unlink;
  }

  inode->i_nlink--;
  inode->i_ctime = CURRENT_TIME;
  if_in_ram_update_sd (&th, inode);

  dir->i_size -= (de.de_entrylen + DEH_SIZE);
  dir->i_ctime = dir->i_mtime = CURRENT_TIME;
  if_in_ram_update_sd (&th, dir) ;
  pop_journal_writer(windex) ;
  journal_end(&th, dir->i_sb, jbegin_count) ;
  call_journal_end = 0 ;
  d_delete(dentry); 
  retval = 0;

end_unlink:
  pathrelse (&path);
  pop_journal_writer(windex) ;
  if (call_journal_end) 
    journal_end(&th, dir->i_sb, jbegin_count) ;
  return retval;
}

static int reiserfs_unlink(struct inode *dir, struct dentry *dentry)
{
	int retval, err;
	struct inode *inode;
	struct reiserfs_dir_entry de;
	INITIALIZE_PATH(path);
	struct reiserfs_transaction_handle th;
	int jbegin_count;
	unsigned long savelink;
	int depth;

	dquot_initialize(dir);

	inode = dentry->d_inode;

	/* in this transaction we can be doing at max two balancings and update
	 * two stat datas, we change quotas of the owner of the directory and of
	 * the owner of the parent directory. The quota structure is possibly
	 * deleted only on iput => outside of this transaction */
	jbegin_count =
	    JOURNAL_PER_BALANCE_CNT * 2 + 2 +
	    4 * REISERFS_QUOTA_TRANS_BLOCKS(dir->i_sb);

	depth = reiserfs_write_lock_once(dir->i_sb);
	retval = journal_begin(&th, dir->i_sb, jbegin_count);
	if (retval)
		goto out_unlink;

	de.de_gen_number_bit_string = NULL;
	if ((retval =
	     reiserfs_find_entry(dir, dentry->d_name.name, dentry->d_name.len,
				 &path, &de)) == NAME_NOT_FOUND) {
		retval = -ENOENT;
		goto end_unlink;
	} else if (retval == IO_ERROR) {
		retval = -EIO;
		goto end_unlink;
	}

	reiserfs_update_inode_transaction(inode);
	reiserfs_update_inode_transaction(dir);

	if (de.de_objectid != inode->i_ino) {
		// FIXME: compare key of an object and a key found in the
		// entry
		retval = -EIO;
		goto end_unlink;
	}

	if (!inode->i_nlink) {
		reiserfs_warning(inode->i_sb, "reiserfs-7042",
				 "deleting nonexistent file (%lu), %d",
				 inode->i_ino, inode->i_nlink);
		set_nlink(inode, 1);
	}

	drop_nlink(inode);

	/*
	 * we schedule before doing the add_save_link call, save the link
	 * count so we don't race
	 */
	savelink = inode->i_nlink;

	retval =
	    reiserfs_cut_from_item(&th, &path, &(de.de_entry_key), dir, NULL,
				   0);
	if (retval < 0) {
		inc_nlink(inode);
		goto end_unlink;
	}
	inode->i_ctime = CURRENT_TIME_SEC;
	reiserfs_update_sd(&th, inode);

	dir->i_size -= (de.de_entrylen + DEH_SIZE);
	dir->i_ctime = dir->i_mtime = CURRENT_TIME_SEC;
	reiserfs_update_sd(&th, dir);

	if (!savelink)
		/* prevent file from getting lost */
		add_save_link(&th, inode, 0 /* not truncate */ );

	retval = journal_end(&th, dir->i_sb, jbegin_count);
	reiserfs_check_path(&path);
	reiserfs_write_unlock_once(dir->i_sb, depth);
	return retval;

      end_unlink:
	pathrelse(&path);
	err = journal_end(&th, dir->i_sb, jbegin_count);
	reiserfs_check_path(&path);
	if (err)
		retval = err;
      out_unlink:
	reiserfs_write_unlock_once(dir->i_sb, depth);
	return retval;
}

static int reiserfs_rmdir(struct inode *dir, struct dentry *dentry)
{
	int retval, err;
	struct inode *inode;
	struct reiserfs_transaction_handle th;
	int jbegin_count;
	INITIALIZE_PATH(path);
	struct reiserfs_dir_entry de;

	/* we will be doing 2 balancings and update 2 stat data, we change quotas
	 * of the owner of the directory and of the owner of the parent directory.
	 * The quota structure is possibly deleted only on last iput => outside
	 * of this transaction */
	jbegin_count =
	    JOURNAL_PER_BALANCE_CNT * 2 + 2 +
	    4 * REISERFS_QUOTA_TRANS_BLOCKS(dir->i_sb);

	dquot_initialize(dir);

	reiserfs_write_lock(dir->i_sb);
	retval = journal_begin(&th, dir->i_sb, jbegin_count);
	if (retval)
		goto out_rmdir;

	de.de_gen_number_bit_string = NULL;
	if ((retval =
	     reiserfs_find_entry(dir, dentry->d_name.name, dentry->d_name.len,
				 &path, &de)) == NAME_NOT_FOUND) {
		retval = -ENOENT;
		goto end_rmdir;
	} else if (retval == IO_ERROR) {
		retval = -EIO;
		goto end_rmdir;
	}

	inode = dentry->d_inode;

	reiserfs_update_inode_transaction(inode);
	reiserfs_update_inode_transaction(dir);

	if (de.de_objectid != inode->i_ino) {
		// FIXME: compare key of an object and a key found in the
		// entry
		retval = -EIO;
		goto end_rmdir;
	}
	if (!reiserfs_empty_dir(inode)) {
		retval = -ENOTEMPTY;
		goto end_rmdir;
	}

	/* cut entry from dir directory */
	retval = reiserfs_cut_from_item(&th, &path, &(de.de_entry_key), dir, NULL,	/* page */
					0 /*new file size - not used here */ );
	if (retval < 0)
		goto end_rmdir;

	if (inode->i_nlink != 2 && inode->i_nlink != 1)
		reiserfs_error(inode->i_sb, "reiserfs-7040",
			       "empty directory has nlink != 2 (%d)",
			       inode->i_nlink);

	clear_nlink(inode);
	inode->i_ctime = dir->i_ctime = dir->i_mtime = CURRENT_TIME_SEC;
	reiserfs_update_sd(&th, inode);

	DEC_DIR_INODE_NLINK(dir)
	    dir->i_size -= (DEH_SIZE + de.de_entrylen);
	reiserfs_update_sd(&th, dir);

	/* prevent empty directory from getting lost */
	add_save_link(&th, inode, 0 /* not truncate */ );

	retval = journal_end(&th, dir->i_sb, jbegin_count);
	reiserfs_check_path(&path);
      out_rmdir:
	reiserfs_write_unlock(dir->i_sb);
	return retval;

      end_rmdir:
	/* we must release path, because we did not call
	   reiserfs_cut_from_item, or reiserfs_cut_from_item does not
	   release path if operation was not complete */
	pathrelse(&path);
	err = journal_end(&th, dir->i_sb, jbegin_count);
	reiserfs_write_unlock(dir->i_sb);
	return err ? err : retval;
}

static int reiserfs_add_entry(struct reiserfs_transaction_handle *th,
			      struct inode *dir, const char *name, int namelen,
			      struct inode *inode, int visible)
{
	struct cpu_key entry_key;
	struct reiserfs_de_head *deh;
	INITIALIZE_PATH(path);
	struct reiserfs_dir_entry de;
	DECLARE_BITMAP(bit_string, MAX_GENERATION_NUMBER + 1);
	int gen_number;
	char small_buf[32 + DEH_SIZE];	/* 48 bytes now and we avoid kmalloc
					   if we create file with short name */
	char *buffer;
	int buflen, paste_size;
	int retval;

	BUG_ON(!th->t_trans_id);

	/* cannot allow items to be added into a busy deleted directory */
	if (!namelen)
		return -EINVAL;

	if (namelen > REISERFS_MAX_NAME(dir->i_sb->s_blocksize))
		return -ENAMETOOLONG;

	/* each entry has unique key. compose it */
	make_cpu_key(&entry_key, dir,
		     get_third_component(dir->i_sb, name, namelen),
		     TYPE_DIRENTRY, 3);

	/* get memory for composing the entry */
	buflen = DEH_SIZE + ROUND_UP(namelen);
	if (buflen > sizeof(small_buf)) {
		buffer = kmalloc(buflen, GFP_NOFS);
		if (!buffer)
			return -ENOMEM;
	} else
		buffer = small_buf;

	paste_size =
	    (get_inode_sd_version(dir) ==
	     STAT_DATA_V1) ? (DEH_SIZE + namelen) : buflen;

	/* fill buffer : directory entry head, name[, dir objectid | , stat data | ,stat data, dir objectid ] */
	deh = (struct reiserfs_de_head *)buffer;
	deh->deh_location = 0;	/* JDM Endian safe if 0 */
	put_deh_offset(deh, cpu_key_k_offset(&entry_key));
	deh->deh_state = 0;	/* JDM Endian safe if 0 */
	/* put key (ino analog) to de */
	deh->deh_dir_id = INODE_PKEY(inode)->k_dir_id;	/* safe: k_dir_id is le */
	deh->deh_objectid = INODE_PKEY(inode)->k_objectid;	/* safe: k_objectid is le */

	/* copy name */
	memcpy((char *)(deh + 1), name, namelen);
	/* padd by 0s to the 4 byte boundary */
	padd_item((char *)(deh + 1), ROUND_UP(namelen), namelen);

	/* entry is ready to be pasted into tree, set 'visibility' and 'stat data in entry' attributes */
	mark_de_without_sd(deh);
	visible ? mark_de_visible(deh) : mark_de_hidden(deh);

	/* find the proper place for the new entry */
	memset(bit_string, 0, sizeof(bit_string));
	de.de_gen_number_bit_string = bit_string;
	retval = reiserfs_find_entry(dir, name, namelen, &path, &de);
	if (retval != NAME_NOT_FOUND) {
		if (buffer != small_buf)
			kfree(buffer);
		pathrelse(&path);

		if (retval == IO_ERROR) {
			return -EIO;
		}

		if (retval != NAME_FOUND) {
			reiserfs_error(dir->i_sb, "zam-7002",
				       "reiserfs_find_entry() returned "
				       "unexpected value (%d)", retval);
		}

		return -EEXIST;
	}

	gen_number =
	    find_first_zero_bit(bit_string,
				MAX_GENERATION_NUMBER + 1);
	if (gen_number > MAX_GENERATION_NUMBER) {
		/* there is no free generation number */
		reiserfs_warning(dir->i_sb, "reiserfs-7010",
				 "Congratulations! we have got hash function "
				 "screwed up");
		if (buffer != small_buf)
			kfree(buffer);
		pathrelse(&path);
		return -EBUSY;
	}
	/* adjust offset of directory enrty */
	put_deh_offset(deh, SET_GENERATION_NUMBER(deh_offset(deh), gen_number));
	set_cpu_key_k_offset(&entry_key, deh_offset(deh));

//.........这里部分代码省略.........

/* add entry to the directory (entry can be hidden). Does not mark dir
   inode dirty, do it after successesfull call to it */
static int reiserfs_add_entry (struct reiserfs_transaction_handle *th, struct inode * dir, 
                               const char * name, int namelen, struct key * object_key, struct reiserfs_dir_entry * de,
			       int visible
			       )
{
  struct key entry_key;
  char * buffer;
  int buflen;
  struct reiserfs_de_head * deh;
  struct path path;
  char bit_string [MAX_GEN_NUMBER / 8 + 1];
  int gen_number;
  int repeat;
#ifdef REISERFS_ALIGNED
  int aligned_namelen = (namelen+3) & ~3;
#endif

  init_path (&path);

  if (!dir || !dir->i_sb)
    return -ENOENT;

  if ((unsigned int)namelen > REISERFS_MAX_NAME_LEN (dir->i_sb->s_blocksize))
    return -ENAMETOOLONG;

  /* each entry has unique key. compose it */
  copy_key (&entry_key, INODE_PKEY(dir));
  entry_key.k_offset = get_third_component (name, namelen);
  entry_key.k_uniqueness = DIRENTRY_UNIQUENESS;

  /* get memory for composing the entry */
#ifdef REISERFS_ALIGNED
  buflen = DEH_SIZE + aligned_namelen;
#else
  buflen = DEH_SIZE + namelen;
#endif
  buffer = reiserfs_kmalloc (buflen, GFP_KERNEL, dir->i_sb);
  if (buffer == 0)
    return -ENOMEM;

  /* fill buffer : directory entry head, name[, dir objectid | , stat data | ,stat data, dir objectid ] */
  deh = (struct reiserfs_de_head *)buffer;
  deh->deh_location = 0;
  deh->deh_offset = entry_key.k_offset;
  deh->deh_state = 0;
  /* put key (ino analog) to de */
  deh->deh_dir_id = object_key->k_dir_id;
  deh->deh_objectid = object_key->k_objectid;

  /* copy name */
#ifdef REISERFS_ALIGNED
  memset( (char*)(deh+1), '\0', aligned_namelen );
#endif
  memcpy ((char *)(deh + 1), name, namelen);

  /* entry is ready to be pasted into tree, set 'visibility' and 'stat data in entry' attributes */
  mark_de_without_sd (deh);
  visible ? mark_de_visible (deh) : mark_de_hidden (deh);

  /* find the proper place for the new entry */
  memset (bit_string, 0, sizeof (bit_string));
  de->de_gen_number_bit_string = bit_string;
  if (reiserfs_find_entry (dir, name, namelen, &path, de) == POSITION_FOUND) {
    reiserfs_panic (dir->i_sb, "vs-7030: reiserfs_add_entry: entry with this key %k already exists",
		    &entry_key);
  }

  if (find_first_nonzero_bit (bit_string, MAX_GEN_NUMBER + 1) < MAX_GEN_NUMBER + 1) {
    /* there are few names with given hash value */
    gen_number = find_first_zero_bit (bit_string, MAX_GEN_NUMBER + 1);
    if (gen_number > MAX_GEN_NUMBER) {
      /* there is no free generation number */
      reiserfs_kfree (buffer, buflen, dir->i_sb);
      pathrelse (&path);
      return -EHASHCOLLISION;
    }
    /* adjust offset of directory enrty */
    deh->deh_offset = SET_GENERATION_NUMBER (deh->deh_offset, gen_number);
    entry_key.k_offset = deh->deh_offset;

    /* find place for new entry */
    if (search_by_entry_key (dir->i_sb, &entry_key, &path, &(de->de_entry_num), &repeat)) {
      reiserfs_panic (dir->i_sb, "reiserfs_add_entry: 7032: entry with this key (%k) already exists", &entry_key);
    }
  } else {
    deh->deh_offset = SET_GENERATION_NUMBER (deh->deh_offset, 0);
    entry_key.k_offset = deh->deh_offset;    
  }
  
  /* perform the insertion of the entry that we have prepared */
  if (reiserfs_paste_into_item (th, dir->i_sb, &path, &(de->de_entry_num), &entry_key, buffer, 
                                buflen, REISERFS_KERNEL_MEM, 0) == -1) {
    reiserfs_kfree (buffer, buflen, dir->i_sb);
    return -ENOSPC;
  }

  reiserfs_kfree (buffer, buflen, dir->i_sb);
  dir->i_size += buflen;
//.........这里部分代码省略.........