diff options
| -rw-r--r-- | fs/befs/befs_fs_types.h | 4 | ||||
| -rw-r--r-- | fs/befs/btree.c | 48 | ||||
| -rw-r--r-- | fs/befs/btree.h | 2 | ||||
| -rw-r--r-- | fs/befs/datastream.c | 6 | ||||
| -rw-r--r-- | fs/befs/inode.h | 2 | ||||
| -rw-r--r-- | fs/befs/io.h | 1 | ||||
| -rw-r--r-- | fs/befs/linuxvfs.c | 32 |
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 | */ |
| 413 | int | 413 | int |
| @@ -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 | */ |
| 601 | static int | 601 | static 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 | */ |
| 661 | static char * | 661 | static char * |
| 662 | befs_bt_keydata(struct befs_btree_node *node) | 662 | befs_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 | ||
| 6 | int befs_btree_find(struct super_block *sb, const befs_data_stream *ds, | 6 | int 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 | /** | ||
