aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--fs/befs/befs_fs_types.h4
-rw-r--r--fs/befs/btree.c48
-rw-r--r--fs/befs/btree.h2
-rw-r--r--fs/befs/datastream.c6
-rw-r--r--fs/befs/inode.h2
-rw-r--r--fs/befs/io.h1
-rw-r--r--fs/befs/linuxvfs.c32
7 files changed, 47 insertions, 48 deletions
diff --git a/fs/befs/befs_fs_types.h b/fs/befs/befs_fs_types.h
index eda332593ecc..69c9d8cde955 100644
--- a/fs/befs/befs_fs_types.h
+++ b/fs/befs/befs_fs_types.h
@@ -79,7 +79,7 @@ enum inode_flags {
79 BEFS_INODE_WAS_WRITTEN = 0x00020000, 79 BEFS_INODE_WAS_WRITTEN = 0x00020000,
80 BEFS_NO_TRANSACTION = 0x00040000, 80 BEFS_NO_TRANSACTION = 0x00040000,
81}; 81};
82/* 82/*
83 * On-Disk datastructures of BeFS 83 * On-Disk datastructures of BeFS
84 */ 84 */
85 85
@@ -139,7 +139,7 @@ typedef struct {
139 139
140} PACKED befs_super_block; 140} PACKED befs_super_block;
141 141
142/* 142/*
143 * Note: the indirect and dbl_indir block_runs may 143 * Note: the indirect and dbl_indir block_runs may
144 * be longer than one block! 144 * be longer than one block!
145 */ 145 */
diff --git a/fs/befs/btree.c b/fs/befs/btree.c
index 7e135ea73fdd..d509887c580c 100644
--- a/fs/befs/btree.c
+++ b/fs/befs/btree.c
@@ -12,8 +12,8 @@
12 * 12 *
13 * Dominic Giampaolo, author of "Practical File System 13 * Dominic Giampaolo, author of "Practical File System
14 * Design with the Be File System", for such a helpful book. 14 * Design with the Be File System", for such a helpful book.
15 * 15 *
16 * Marcus J. Ranum, author of the b+tree package in 16 * Marcus J. Ranum, author of the b+tree package in
17 * comp.sources.misc volume 10. This code is not copied from that 17 * comp.sources.misc volume 10. This code is not copied from that
18 * work, but it is partially based on it. 18 * work, but it is partially based on it.
19 * 19 *
@@ -38,38 +38,38 @@
38 */ 38 */
39 39
40/* Befs B+tree structure: 40/* Befs B+tree structure:
41 * 41 *
42 * The first thing in the tree is the tree superblock. It tells you 42 * The first thing in the tree is the tree superblock. It tells you
43 * all kinds of useful things about the tree, like where the rootnode 43 * all kinds of useful things about the tree, like where the rootnode
44 * is located, and the size of the nodes (always 1024 with current version 44 * is located, and the size of the nodes (always 1024 with current version
45 * of BeOS). 45 * of BeOS).
46 * 46 *
47 * The rest of the tree consists of a series of nodes. Nodes contain a header 47 * The rest of the tree consists of a series of nodes. Nodes contain a header
48 * (struct befs_btree_nodehead), the packed key data, an array of shorts 48 * (struct befs_btree_nodehead), the packed key data, an array of shorts
49 * containing the ending offsets for each of the keys, and an array of 49 * containing the ending offsets for each of the keys, and an array of
50 * befs_off_t values. In interior nodes, the keys are the ending keys for 50 * befs_off_t values. In interior nodes, the keys are the ending keys for
51 * the childnode they point to, and the values are offsets into the 51 * the childnode they point to, and the values are offsets into the
52 * datastream containing the tree. 52 * datastream containing the tree.
53 */ 53 */
54 54
55/* Note: 55/* Note:
56 * 56 *
57 * The book states 2 confusing things about befs b+trees. First, 57 * The book states 2 confusing things about befs b+trees. First,
58 * it states that the overflow field of node headers is used by internal nodes 58 * it states that the overflow field of node headers is used by internal nodes
59 * to point to another node that "effectively continues this one". Here is what 59 * to point to another node that "effectively continues this one". Here is what
60 * I believe that means. Each key in internal nodes points to another node that 60 * I believe that means. Each key in internal nodes points to another node that
61 * contains key values less than itself. Inspection reveals that the last key 61 * contains key values less than itself. Inspection reveals that the last key
62 * in the internal node is not the last key in the index. Keys that are 62 * in the internal node is not the last key in the index. Keys that are
63 * greater than the last key in the internal node go into the overflow node. 63 * greater than the last key in the internal node go into the overflow node.
64 * I imagine there is a performance reason for this. 64 * I imagine there is a performance reason for this.
65 * 65 *
66 * Second, it states that the header of a btree node is sufficient to 66 * Second, it states that the header of a btree node is sufficient to
67 * distinguish internal nodes from leaf nodes. Without saying exactly how. 67 * distinguish internal nodes from leaf nodes. Without saying exactly how.
68 * After figuring out the first, it becomes obvious that internal nodes have 68 * After figuring out the first, it becomes obvious that internal nodes have
69 * overflow nodes and leafnodes do not. 69 * overflow nodes and leafnodes do not.
70 */ 70 */
71 71
72/* 72/*
73 * Currently, this code is only good for directory B+trees. 73 * Currently, this code is only good for directory B+trees.
74 * In order to be used for other BFS indexes, it needs to be extended to handle 74 * In order to be used for other BFS indexes, it needs to be extended to handle
75 * duplicate keys and non-string keytypes (int32, int64, float, double). 75 * duplicate keys and non-string keytypes (int32, int64, float, double).
@@ -237,8 +237,8 @@ befs_bt_read_node(struct super_block *sb, const befs_data_stream *ds,
237 * with @key (usually the disk block number of an inode). 237 * with @key (usually the disk block number of an inode).
238 * 238 *
239 * On failure, returns BEFS_ERR or BEFS_BT_NOT_FOUND. 239 * On failure, returns BEFS_ERR or BEFS_BT_NOT_FOUND.
240 * 240 *
241 * Algorithm: 241 * Algorithm:
242 * Read the superblock and rootnode of the b+tree. 242 * Read the superblock and rootnode of the b+tree.
243 * Drill down through the interior nodes using befs_find_key(). 243 * Drill down through the interior nodes using befs_find_key().
244 * Once at the correct leaf node, use befs_find_key() again to get the 244 * Once at the correct leaf node, use befs_find_key() again to get the
@@ -402,12 +402,12 @@ befs_find_key(struct super_block *sb, struct befs_btree_node *node,
402 * 402 *
403 * Here's how it works: Key_no is the index of the key/value pair to 403 * Here's how it works: Key_no is the index of the key/value pair to
404 * return in keybuf/value. 404 * return in keybuf/value.
405 * Bufsize is the size of keybuf (BEFS_NAME_LEN+1 is a good size). Keysize is 405 * Bufsize is the size of keybuf (BEFS_NAME_LEN+1 is a good size). Keysize is
406 * the number of characters in the key (just a convenience). 406 * the number of characters in the key (just a convenience).
407 * 407 *
408 * Algorithm: 408 * Algorithm:
409 * Get the first leafnode of the tree. See if the requested key is in that 409 * Get the first leafnode of the tree. See if the requested key is in that
410 * node. If not, follow the node->right link to the next leafnode. Repeat 410 * node. If not, follow the node->right link to the next leafnode. Repeat
411 * until the (key_no)th key is found or the tree is out of keys. 411 * until the (key_no)th key is found or the tree is out of keys.
412 */ 412 */
413int 413int
@@ -536,7 +536,7 @@ befs_btree_read(struct super_block *sb, const befs_data_stream *ds,
536 * @node_off: Pointer to offset of current node within datastream. Modified 536 * @node_off: Pointer to offset of current node within datastream. Modified
537 * by the function. 537 * by the function.
538 * 538 *
539 * Helper function for btree traverse. Moves the current position to the 539 * Helper function for btree traverse. Moves the current position to the
540 * start of the first leaf node. 540 * start of the first leaf node.
541 * 541 *
542 * Also checks for an empty tree. If there are no keys, returns BEFS_BT_EMPTY. 542 * Also checks for an empty tree. If there are no keys, returns BEFS_BT_EMPTY.
@@ -592,10 +592,10 @@ befs_btree_seekleaf(struct super_block *sb, const befs_data_stream *ds,
592} 592}
593 593
594/** 594/**
595 * befs_leafnode - Determine if the btree node is a leaf node or an 595 * befs_leafnode - Determine if the btree node is a leaf node or an
596 * interior node 596 * interior node
597 * @node: Pointer to node structure to test 597 * @node: Pointer to node structure to test
598 * 598 *
599 * Return 1 if leaf, 0 if interior 599 * Return 1 if leaf, 0 if interior
600 */ 600 */
601static int 601static int
@@ -656,7 +656,7 @@ befs_bt_valarray(struct befs_btree_node *node)
656 * @node: Pointer to the node structure to find the keydata array within 656 * @node: Pointer to the node structure to find the keydata array within
657 * 657 *
658 * Returns a pointer to the start of the keydata array 658 * Returns a pointer to the start of the keydata array
659 * of the node pointed to by the node header 659 * of the node pointed to by the node header
660 */ 660 */
661static char * 661static char *
662befs_bt_keydata(struct befs_btree_node *node) 662befs_bt_keydata(struct befs_btree_node *node)
@@ -702,7 +702,7 @@ befs_bt_get_key(struct super_block *sb, struct befs_btree_node *node,
702 702
703/** 703/**
704 * befs_compare_strings - compare two strings 704 * befs_compare_strings - compare two strings
705 * @key1: pointer to the first key to be compared 705 * @key1: pointer to the first key to be compared
706 * @keylen1: length in bytes of key1 706 * @keylen1: length in bytes of key1
707 * @key2: pointer to the second key to be compared 707 * @key2: pointer to the second key to be compared
708 * @keylen2: length in bytes of key2 708 * @keylen2: length in bytes of key2
diff --git a/fs/befs/btree.h b/fs/befs/btree.h
index 3da90f56cfd4..60c6c728e64e 100644
--- a/fs/befs/btree.h
+++ b/fs/befs/btree.h
@@ -1,6 +1,6 @@
1/* 1/*
2 * btree.h 2 * btree.h
3 * 3 *
4 */ 4 */
5 5
6int befs_btree_find(struct super_block *sb, const befs_data_stream *ds, 6int befs_btree_find(struct super_block *sb, const befs_data_stream *ds,
diff --git a/fs/befs/datastream.c b/fs/befs/datastream.c
index 56c0564e6787..720b3bc5c16a 100644
--- a/fs/befs/datastream.c
+++ b/fs/befs/datastream.c
@@ -84,9 +84,9 @@ befs_read_datastream(struct super_block *sb, const befs_data_stream *ds,
84 * 84 *
85 * Takes a file position and gives back a brun who's starting block 85 * Takes a file position and gives back a brun who's starting block
86 * is block number fblock of the file. 86 * is block number fblock of the file.
87 * 87 *
88 * Returns BEFS_OK or BEFS_ERR. 88 * Returns BEFS_OK or BEFS_ERR.
89 * 89 *
90 * Calls specialized functions for each of the three possible 90 * Calls specialized functions for each of the three possible
91 * datastream regions. 91 * datastream regions.
92 */ 92 */
@@ -118,7 +118,7 @@ befs_fblock2brun(struct super_block *sb, const befs_data_stream *data,
118 118
119/**