[syslinux:elflink] xfs: Add full B+tree search support in xfs_dir2_node_find_entry()
syslinux-bot for Chen Baozi
baozich at gmail.com
Tue Nov 27 12:57:24 PST 2012
Commit-ID: 4db137eaa7ac68966660f6fbf4dc13a2244bf8b2
Gitweb: http://www.syslinux.org/commit/4db137eaa7ac68966660f6fbf4dc13a2244bf8b2
Author: Chen Baozi <baozich at gmail.com>
AuthorDate: Wed, 15 Aug 2012 17:32:40 +0800
Committer: Paulo Alcantara <pcacjr at zytor.com>
CommitDate: Sun, 2 Sep 2012 19:12:47 -0300
xfs: Add full B+tree search support in xfs_dir2_node_find_entry()
According to the manual, the difference between B+tree directory
and node directory is that the node/leaf trees can be more than
one level deep in the B+tree format. That is to say we do not
need to reimplemented a completely new function in B+tree case.
What we've done here is to modify xfs_dir2_node_find_entry() to
support searching in a B+tree more than one level.
Signed-off-by: Chen Baozi <baozich at gmail.com>
Signed-off-by: Paulo Alcantara <pcacjr at zytor.com>
---
core/fs/xfs/xfs_dir2.c | 108 ++++++++++++++++++++++++-------------------------
1 file changed, 54 insertions(+), 54 deletions(-)
diff --git a/core/fs/xfs/xfs_dir2.c b/core/fs/xfs/xfs_dir2.c
index 30db8cc..e6ae92f 100644
--- a/core/fs/xfs/xfs_dir2.c
+++ b/core/fs/xfs/xfs_dir2.c
@@ -493,68 +493,73 @@ struct inode *xfs_dir2_node_find_entry(const char *dname, struct inode *parent,
} while (irec.br_startoff <
xfs_dir2_byte_to_db(parent->fs, XFS_DIR2_LEAF_OFFSET));
+ hashwant = xfs_dir2_da_hashname((uint8_t *)dname, strlen(dname));
+
fsblkno = fsblock_to_bytes(parent->fs, irec.br_startblock) >>
BLOCK_SHIFT(parent->fs);
-
node = (xfs_da_intnode_t *)xfs_dir2_get_dirblks(parent->fs, fsblkno, 1);
if (be16_to_cpu(node->hdr.info.magic) != XFS_DA_NODE_MAGIC) {
xfs_error("Node's magic number does not match!");
goto out;
}
- if (!node->hdr.count)
- goto out;
-
- hashwant = xfs_dir2_da_hashname((uint8_t *)dname, strlen(dname));
+ do {
+ if (!node->hdr.count)
+ goto out;
+
+ /* Given a hash to lookup, you read the node's btree array and first
+ * "hashval" in the array that exceeds the given hash and it can then
+ * be found in the block pointed by the "before" value.
+ */
+ max = be16_to_cpu(node->hdr.count);
+
+ probe = span = max/2;
+ for (btree = &node->btree[probe];
+ span > 4; btree = &node->btree[probe]) {
+ span /= 2;
+ hash = be32_to_cpu(btree->hashval);
+ if (hash < hashwant)
+ probe += span;
+ else if (hash > hashwant)
+ probe -= span;
+ else
+ break;
+ }
- /* Given a hash to lookup, you read the node's btree array and first
- * "hashval" in the array that exceeds the given hash and it can then
- * be found in the block pointed by the "before" value.
- */
- max = be16_to_cpu(node->hdr.count);
+ while ((probe > 0) && (be32_to_cpu(btree->hashval) >= hashwant)) {
+ btree--;
+ probe--;
+ }
+ while ((probe < max) && (be32_to_cpu(btree->hashval) < hashwant)) {
+ btree++;
+ probe++;
+ }
- probe = span = max/2;
- for (btree = &node->btree[probe]; span > 4; btree = &node->btree[probe]) {
- span /= 2;
- hash = be32_to_cpu(btree->hashval);
- if (hash < hashwant)
- probe += span;
- else if (hash > hashwant)
- probe -= span;
+ if (probe == max)
+ fsblkno = be32_to_cpu(node->btree[max-1].before);
else
- break;
- }
-
- while ((probe > 0) && (be32_to_cpu(btree->hashval) >= hashwant)) {
- btree--;
- probe--;
- }
- while ((probe < max) && (be32_to_cpu(btree->hashval) < hashwant)) {
- btree++;
- probe++;
- }
-
- if (probe == max)
- fsblkno = be32_to_cpu(node->btree[max-1].before);
- else
- fsblkno = be32_to_cpu(node->btree[probe].before);
-
- fsblkno = xfs_dir2_get_right_blk(parent->fs, core, node_off + 1,
- be32_to_cpu(core->di_nextents) - 1,
- fsblkno, &error);
- if (error) {
- xfs_error("Cannot find leaf rec!");
- goto out;
- }
+ fsblkno = be32_to_cpu(node->btree[probe].before);
+
+ fsblkno = xfs_dir2_get_right_blk(parent->fs, core, node_off + 1,
+ be32_to_cpu(core->di_nextents) - 1,
+ fsblkno, &error);
+ if (error) {
+ xfs_error("Cannot find right rec!");
+ goto out;
+ }
+ free(node);
+ node = (xfs_da_intnode_t *)xfs_dir2_get_dirblks(parent->fs,
+ fsblkno, 1);
+ } while(be16_to_cpu(node->hdr.info.magic) == XFS_DA_NODE_MAGIC);
- leaf = (xfs_dir2_leaf_t*)xfs_dir2_get_dirblks(parent->fs, fsblkno, 1);
+ leaf = (xfs_dir2_leaf_t*)node;
if (be16_to_cpu(leaf->hdr.info.magic) != XFS_DIR2_LEAFN_MAGIC) {
xfs_error("Leaf's magic number does not match!");
- goto out1;
+ goto out;
}
if (!leaf->hdr.count)
- goto out1;
+ goto out;
for (lep = leaf->ents, low = 0, high = be16_to_cpu(leaf->hdr.count) - 1;
low <= high; ) {
@@ -571,7 +576,7 @@ struct inode *xfs_dir2_node_find_entry(const char *dname, struct inode *parent,
* entry we're looking for and there is nothing to do anymore.
*/
if (hash != hashwant)
- goto out1;
+ goto out;
while (mid > 0 && be32_to_cpu(lep[mid - 1].hashval) == hashwant)
mid--;
@@ -593,14 +598,14 @@ struct inode *xfs_dir2_node_find_entry(const char *dname, struct inode *parent,
newdb, &error);
if (error) {
xfs_error("Cannot find data block!");
- goto out1;
+ goto out;
}
buf = xfs_dir2_get_dirblks(parent->fs, fsblkno, 1);
data_hdr = (xfs_dir2_data_hdr_t *)buf;
if (be32_to_cpu(data_hdr->magic) != XFS_DIR2_DATA_MAGIC) {
xfs_error("Leaf directory's data magic No. does not match!");
- goto out2;
+ goto out1;
}
curdb = newdb;
}
@@ -617,11 +622,8 @@ struct inode *xfs_dir2_node_find_entry(const char *dname, struct inode *parent,
free(name);
}
-out2:
- free(buf);
-
out1:
- free(leaf);
+ free(buf);
out:
free(node);
@@ -655,7 +657,6 @@ found:
xfs_debug("entry inode's number %lu", ino);
free(buf);
- free(leaf);
free(node);
return ip;
@@ -663,7 +664,6 @@ found:
failed:
free(ip);
free(buf);
- free(leaf);
free(node);
return NULL;
More information about the Syslinux-commits
mailing list