nilfs2: add bmap function to seek a valid key

[pandora-kernel.git] / fs / nilfs2 / btree.c

diff --git a/fs/nilfs2/btree.c b/fs/nilfs2/btree.c
index ecdbae1..059f371 100644 (file)
--- a/fs/nilfs2/btree.c
+++ b/fs/nilfs2/btree.c
@@ -633,6 +633,44 @@ static int nilfs_btree_do_lookup_last(const struct nilfs_bmap *btree,
        return 0;
 }
 
+/**
+ * nilfs_btree_get_next_key - get next valid key from btree path array
+ * @btree: bmap struct of btree
+ * @path: array of nilfs_btree_path struct
+ * @minlevel: start level
+ * @nextkey: place to store the next valid key
+ *
+ * Return Value: If a next key was found, 0 is returned. Otherwise,
+ * -ENOENT is returned.
+ */
+static int nilfs_btree_get_next_key(const struct nilfs_bmap *btree,
+                                   const struct nilfs_btree_path *path,
+                                   int minlevel, __u64 *nextkey)
+{
+       struct nilfs_btree_node *node;
+       int maxlevel = nilfs_btree_height(btree) - 1;
+       int index, next_adj, level;
+
+       /* Next index is already set to bp_index for leaf nodes. */
+       next_adj = 0;
+       for (level = minlevel; level <= maxlevel; level++) {
+               if (level == maxlevel)
+                       node = nilfs_btree_get_root(btree);
+               else
+                       node = nilfs_btree_get_nonroot_node(path, level);
+
+               index = path[level].bp_index + next_adj;
+               if (index < nilfs_btree_node_get_nchildren(node)) {
+                       /* Next key is in this node */
+                       *nextkey = nilfs_btree_node_get_key(node, index);
+                       return 0;
+               }
+               /* For non-leaf nodes, next index is stored at bp_index + 1. */
+               next_adj = 1;
+       }
+       return -ENOENT;
+}
+
 static int nilfs_btree_lookup(const struct nilfs_bmap *btree,
                              __u64 key, int level, __u64 *ptrp)
 {
@@ -1563,6 +1601,27 @@ out:
        return ret;
 }
 
+static int nilfs_btree_seek_key(const struct nilfs_bmap *btree, __u64 start,
+                               __u64 *keyp)
+{
+       struct nilfs_btree_path *path;
+       const int minlevel = NILFS_BTREE_LEVEL_NODE_MIN;
+       int ret;
+
+       path = nilfs_btree_alloc_path();
+       if (!path)
+               return -ENOMEM;
+
+       ret = nilfs_btree_do_lookup(btree, path, start, NULL, minlevel, 0);
+       if (!ret)
+               *keyp = start;
+       else if (ret == -ENOENT)
+               ret = nilfs_btree_get_next_key(btree, path, minlevel, keyp);
+
+       nilfs_btree_free_path(path);
+       return ret;
+}
+
 static int nilfs_btree_last_key(const struct nilfs_bmap *btree, __u64 *keyp)
 {
        struct nilfs_btree_path *path;
@@ -2298,7 +2357,9 @@ static const struct nilfs_bmap_operations nilfs_btree_ops = {
        .bop_assign             =       nilfs_btree_assign,
        .bop_mark               =       nilfs_btree_mark,
 
+       .bop_seek_key           =       nilfs_btree_seek_key,
        .bop_last_key           =       nilfs_btree_last_key,
+
        .bop_check_insert       =       NULL,
        .bop_check_delete       =       nilfs_btree_check_delete,
        .bop_gather_data        =       nilfs_btree_gather_data,
@@ -2318,7 +2379,9 @@ static const struct nilfs_bmap_operations nilfs_btree_ops_gc = {
        .bop_assign             =       nilfs_btree_assign_gc,
        .bop_mark               =       NULL,
 
+       .bop_seek_key           =       NULL,
        .bop_last_key           =       NULL,
+
        .bop_check_insert       =       NULL,
        .bop_check_delete       =       NULL,
        .bop_gather_data        =       NULL,