reiserfslib.c

reiserfsprogs-3.6.19.tar.gz 源码 给有需要的人！

}


int reiserfs_search_by_key_3 (reiserfs_filsys_t * fs, struct key * key,
			      struct path * path)
{
    return reiserfs_search_by_key_x (fs, key, path, 3);
}


int reiserfs_search_by_key_4 (reiserfs_filsys_t * fs, struct key * key,
			      struct path * path)
{
    return reiserfs_search_by_key_x (fs, key, path, 4);
}


/* key is key of byte in the regular file. This searches in tree
   through items and in the found item as well */
int usearch_by_position (reiserfs_filsys_t * s, struct key * key,
			 int version, struct path * path)
{
    struct buffer_head * bh;
    struct item_head * ih;
    struct key * next_key;

    if (reiserfs_search_by_key_3 (s, key, path) == ITEM_FOUND) {
    	ih = get_ih (path);

	if (!is_direct_ih (ih) && !is_indirect_ih (ih))
	    return DIRECTORY_FOUND;

	path->pos_in_item = 0;
	return POSITION_FOUND;
    }

    bh = get_bh (path);
    ih = get_ih (path);


    if (PATH_LAST_POSITION (path) == 0) {
	/* previous item does not exist, that means we are in leftmost leaf of
	 * the tree */
	if (!not_of_one_file (&ih->ih_key, key)) {
	    if (!is_direct_ih (ih) && !is_indirect_ih (ih))
		return DIRECTORY_FOUND;
	    return POSITION_NOT_FOUND;
	}
	return FILE_NOT_FOUND;
    }

    /* take previous item */
    PATH_LAST_POSITION (path) --;
    ih --;

    if (not_of_one_file (&ih->ih_key, key) || is_stat_data_ih(ih)) {
	/* previous item belongs to another object or is a stat data, check
	 * next item */
	PATH_LAST_POSITION (path) ++;
	if (PATH_LAST_POSITION (path) < B_NR_ITEMS (bh))
	    /* next key is in the same node */
	    next_key = B_N_PKEY (bh, PATH_LAST_POSITION (path));
	else
	    next_key = uget_rkey (path);
	if (next_key == 0 || not_of_one_file (next_key, key)) {
	    /* there is no any part of such file in the tree */
	    path->pos_in_item = 0;
	    return FILE_NOT_FOUND;
	}

	if (is_direntry_key (next_key)) {
	    reiserfs_warning (stderr, "usearch_by_position: looking for %k found a directory with the same key\n",
		      next_key);
	    return DIRECTORY_FOUND;
	}

	/* next item is the part of this file */
	path->pos_in_item = 0;
	return POSITION_NOT_FOUND;
    }

    if (is_direntry_ih (ih)) {
	return DIRECTORY_FOUND;
    }

    if (is_stat_data_ih(ih)) {
	PATH_LAST_POSITION (path) ++;
	return FILE_NOT_FOUND;
    }

    /* previous item is part of desired file */
    if (I_K_KEY_IN_ITEM (ih, key, bh->b_size)) {
	path->pos_in_item = get_offset (key) - get_offset (&ih->ih_key);
	if (is_indirect_ih (ih) )
	    path->pos_in_item /= bh->b_size;
	return POSITION_FOUND;
    }

    path->pos_in_item = is_indirect_ih (ih) ? I_UNFM_NUM (ih) : get_ih_item_len (ih);
    return POSITION_NOT_FOUND;
}

static int comp_dir_entries (const void * p1, const void * p2)
{
    __u32 off1, off2;

    off1 = d32_get((__u32 *)p1, 0);
    off2 = *(__u32 *)p2;
    
    if (off1 < off2)
	return -1;
    if (off1 > off2)
	return 1;
    return 0;
}

struct key * uget_lkey (struct path * path)
{
    int pos, offset = path->path_length;
    struct buffer_head * bh;

    if (offset < FIRST_PATH_ELEMENT_OFFSET)
	die ("uget_lkey: illegal offset in the path (%d)", offset);


    /* While not higher in path than first element. */
    while (offset-- > FIRST_PATH_ELEMENT_OFFSET) {
	if (! buffer_uptodate (PATH_OFFSET_PBUFFER (path, offset)) )
	    die ("uget_lkey: parent is not uptodate");
	
	/* Parent at the path is not in the tree now. */
	if (! B_IS_IN_TREE (bh = PATH_OFFSET_PBUFFER (path, offset)))
	    die ("uget_lkey: buffer on the path is not in tree");

	/* Check whether position in the parent is correct. */
	if ((pos = PATH_OFFSET_POSITION (path, offset)) > B_NR_ITEMS (bh))
	    die ("uget_lkey: invalid position (%d) in the path", pos);

	/* Check whether parent at the path really points to the child. */
	if (get_dc_child_blocknr (B_N_CHILD (bh, pos)) != PATH_OFFSET_PBUFFER (path, offset + 1)->b_blocknr)
	    die ("uget_lkey: invalid block number (%d). Must be %ld",
		 get_dc_child_blocknr (B_N_CHILD (bh, pos)), PATH_OFFSET_PBUFFER (path, offset + 1)->b_blocknr);
	
	/* Return delimiting key if position in the parent is not equal to zero. */
	if (pos)
	    return B_N_PDELIM_KEY(bh, pos - 1);
    }

    /* there is no left delimiting key */
    return 0;
}

struct key * uget_rkey (struct path * path)
{
    int pos, offset = path->path_length;
    struct buffer_head * bh;

    if (offset < FIRST_PATH_ELEMENT_OFFSET)
	die ("uget_rkey: illegal offset in the path (%d)", offset);

    while (offset-- > FIRST_PATH_ELEMENT_OFFSET) {
	if (! buffer_uptodate (PATH_OFFSET_PBUFFER (path, offset)))
	    die ("uget_rkey: parent is not uptodate");

	/* Parent at the path is not in the tree now. */
	if (! B_IS_IN_TREE (bh = PATH_OFFSET_PBUFFER (path, offset)))
	    die ("uget_rkey: buffer on the path is not in tree");

	/* Check whether position in the parrent is correct. */
	if ((pos = PATH_OFFSET_POSITION (path, offset)) > B_NR_ITEMS (bh))
	    die ("uget_rkey: invalid position (%d) in the path", pos);

	/* Check whether parent at the path really points to the child. */
	if (get_dc_child_blocknr (B_N_CHILD (bh, pos)) != PATH_OFFSET_PBUFFER (path, offset + 1)->b_blocknr)
	    die ("uget_rkey: invalid block number (%d). Must be %ld",
		 get_dc_child_blocknr (B_N_CHILD (bh, pos)), PATH_OFFSET_PBUFFER (path, offset + 1)->b_blocknr);
	
	/* Return delimiting key if position in the parent is not the last one. */
	if (pos != B_NR_ITEMS (bh))
	    return B_N_PDELIM_KEY (bh, pos);
    }
    
    /* there is no right delimiting key */
    return 0;
}

struct key * reiserfs_next_key (struct path * path) {
    if (get_item_pos (path) < B_NR_ITEMS (get_bh (path)) - 1)
	return B_N_PKEY (get_bh (path), get_item_pos (path) + 1);

    return uget_rkey (path);
}


/* NOTE: this only should be used to look for keys who exists */
int reiserfs_search_by_entry_key (reiserfs_filsys_t * fs, struct key * key, 
				  struct path * path)
{
    struct buffer_head * bh;
    int item_pos;
    struct item_head * ih;
    struct key tmpkey;
    __u32 offset;

    if (reiserfs_search_by_key_4 (fs, key, path) == ITEM_FOUND) {
        path->pos_in_item = 0;
        return POSITION_FOUND;
    }

    bh = get_bh (path);
    item_pos = get_item_pos (path);
    ih = get_ih (path);

    if (item_pos == 0) {
	/* key is less than the smallest key in the tree */
	if (not_of_one_file (&(ih->ih_key), key))
	    /* there are no items of that directory */
	    return DIRECTORY_NOT_FOUND;

	if (!is_direntry_ih (ih)) {
	    reiserfs_panic ("reiserfs_search_by_entry_key: found item "
			    "is not of directory type %H", ih);
	}

	/* key we looked for should be here */
        path->pos_in_item = 0;
	return POSITION_NOT_FOUND;
    }

    /* take previous item */
    item_pos --;
    ih --;
    PATH_LAST_POSITION (path) --;

    if (not_of_one_file (&(ih->ih_key), key) || !is_direntry_ih (ih)) {
        /* previous item belongs to another object or is stat data, check next
           item */

	item_pos ++;
	PATH_LAST_POSITION (path) ++;

        if (item_pos < B_NR_ITEMS (bh)) {
	    /* next item is in the same node */
	    ih ++;
            if (not_of_one_file (&(ih->ih_key), key)) {
		/* there are no items of that directory */
                path->pos_in_item = 0;
                return DIRECTORY_NOT_FOUND;
            }

            if (!is_direntry_ih (ih))
		reiserfs_panic ("_search_by_entry_key: %k is not a directory",
				key);
        } else {
	    /* next item is in right neighboring node */
            struct key * next_key = uget_rkey (path);

            if (next_key == 0 || not_of_one_file (next_key, key)) {
                /* there are no items of that directory */
                path->pos_in_item = 0;
                return DIRECTORY_NOT_FOUND;
            }

            if (!is_direntry_key (next_key))
		reiserfs_panic ("_search_by_entry_key: %k is not a directory",
				key);

            /* we got right delimiting key - search for it - the entry will be
	       pasted in position 0 */
            copy_key (&tmpkey, next_key);
            pathrelse (path);
            if (reiserfs_search_by_key_4 (fs, &tmpkey, path) != ITEM_FOUND || PATH_LAST_POSITION (path) != 0)
                reiserfs_panic ("_search_by_entry_key: item corresponding to delimiting key %k not found",
				&tmpkey);
        }

        /* next item is the part of this directory */
        path->pos_in_item = 0;
        return POSITION_NOT_FOUND;
    }

    /* previous item is part of desired directory */
    offset = get_key_offset_v1 (key);
    if (reiserfs_bin_search (&offset, B_I_DEH (bh, ih), get_ih_entry_count (ih),
			     DEH_SIZE, &(path->pos_in_item), comp_dir_entries) == POSITION_FOUND)
	return POSITION_FOUND;

    return POSITION_NOT_FOUND;
}


void init_tb_struct (struct tree_balance * tb, reiserfs_filsys_t * fs,
			     struct path * path, int size)
{
    memset (tb, '\0', sizeof(struct tree_balance));
    tb->tb_fs = fs;
    tb->tb_path = path;

    PATH_OFFSET_PBUFFER(path, ILLEGAL_PATH_ELEMENT_OFFSET) = NULL;
    PATH_OFFSET_POSITION(path, ILLEGAL_PATH_ELEMENT_OFFSET) = 0;
    tb->insert_size[0] = size;
}


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 (reiserfs_search_by_entry_key (fs, key, &path) != POSITION_FOUND) {
	pathrelse (&path);
	return 1;
    }

    ih = get_ih (&path);
    if (get_ih_entry_count (ih) == 1) {
	init_tb_struct (&tb, fs, &path, -(IH_SIZE + get_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;
}



void reiserfs_paste_into_item (reiserfs_filsys_t * fs, struct path * path,
			       const void * body, int size)
{
    struct tree_balance tb;
  
    init_tb_struct (&tb, fs, path, size);

    if (fix_nodes (M_PASTE, &tb, 0/*ih*/) != CARRY_ON)
	reiserfs_panic ("reiserfs_paste_into_item: fix_nodes failed");

    do_balance (&tb, 0, body, M_PASTE, 0/*zero num*/);
}


void reiserfs_insert_item (reiserfs_filsys_t * fs, struct path * path,
			   struct item_head * ih, const void * body)
{
    struct tree_balance tb;
    
    init_tb_struct (&tb, fs, path, IH_SIZE + get_ih_item_len(ih));
    if (fix_nodes (M_INSERT, &tb, ih) != CARRY_ON)
	die ("reiserfs_insert_item: fix_nodes failed");

    do_balance (&tb, ih, body, M_INSERT, 0/*zero num*/);
}


/*===========================================================================*/

__u32 hash_value (hashf_t func, char * name, int namelen)
{
    __u32 res;

    res = func (name, namelen);
    res = GET_HASH_VALUE(res);
    if (res == 0)
	res = 128;

    return res;
}


/* if name is found in a directory - return 1 and set path to the name,
   otherwise return 0 and pathrelse path */
int reiserfs_locate_entry (reiserfs_filsys_t * fs, struct key * dir, char * name,
			   struct path * path)
{
    struct key entry_key;
    struct item_head * ih;
    struct reiserfs_de_head * deh;
    int i, retval;
    struct key * rdkey;
    
    set_key_dirid (&entry_key, get_key_dirid (dir));
    set_key_objectid (&entry_key, get_key_objectid (dir));
    set_key_offset_v1 (&entry_key, 0);
    set_key_uniqueness (&entry_key, DIRENTRY_UNIQUENESS);

 
    if (reiserfs_search_by_entry_key (fs, &entry_key, path) == DIRECTORY_NOT_FOUND) {
	pathrelse (path);
	return 0;
    }

    do {
	ih = get_ih (path);
	deh = B_I_DEH (get_bh (path), ih) + path->pos_in_item;
	for (i = path->pos_in_item; i < get_ih_entry_count (ih); i ++, deh ++) {
	    /* the name in directory has the same hash as the given name */
	    if ((name_in_entry_length (ih, deh, i) == (int)strlen (name)) &&
		!memcmp (name_in_entry (deh, i), name, strlen (name))) {
		path->pos_in_item = i;
		return 1;
	    }
	}

	rdkey = uget_rkey (path);
	if (!rdkey || not_of_one_file (rdkey, dir)) {
	    pathrelse (path);
	    return 0;
	}
	
	if (!is_direntry_key (rdkey))
	    reiserfs_panic ("reiserfs_locate_entry: can not find name in broken directory yet");

	/* first name of that item may be a name we are looking for */
	entry_key = *rdkey;
	pathrelse (path);
	retval = reiserfs_search_by_entry_key (fs, &entry_key, path);
	if (retval != POSITION_FOUND)
	    reiserfs_panic ("reiserfs_locate_entry: wrong delimiting key in the tree");

    } while (1);

    return 0;
    
}


/* returns 0 if name is not found in a directory and 1 if name is
   found. Stores key found in the entry in 'key'. Returns minimal not used
   generation counter in 'min_gen_counter'. dies if found object is not a
   directory. */
int reiserfs_find_entry (reiserfs_filsys_t * fs, struct key * dir, char * name, 
			 unsigned int * min_gen_counter, struct key * key)
{
    struct key entry_key;
    int retval;
    int i;
    INITIALIZE_PATH (path);
    struct item_head * ih;
    struct reiserfs_de_head * deh;
    struct key * rdkey;
    __u32 hash;


    set_key_dirid (&entry_key, get_key_dirid (dir));
    set_key_objectid (&entry_key, get_key_objectid (dir));
    if (!strcmp (name, "."))
	hash = DOT_OFFSET;
    else if (!strcmp (name, ".."))
	hash = DOT_DOT_OFFSET;
    else
	hash = hash_value (reiserfs_hash (fs), name, strlen (name));
    set_key_offset_v1 (&entry_key, hash);
    set_key_uniqueness (&entry_key, DIRENTRY_UNIQUENESS);

    *min_gen_counter = 0;

    if (reiserfs_search_by_entry_key (fs, &entry_key, &path) == DIRECTORY_NOT_FOUND) {
	pathrelse (&path);
	return 0;
    }