btrfs: documented BTree class (no functional change)

Change-Id: Ib3d6247bf99fc520ba063c361a7b465224805610

btrfs

* Fixed coding style for all files under /src/add-ons/kernel/file_systems/btrfs
* rewrote crc_table.cpp to generate CRCTable.cpp that conforms to coding style.

Change-Id: I90fcc143320c7a7e9a6dc174f0ad82f40bb8a9b6
Reviewed-on: https://review.haiku-os.org/c/1194
Reviewed-by: Jérôme Duval <jerome.duval@gmail.com>

BTRFS: Add author and license.

Signed-off-by: Augustin Cavalier <waddlesplash@gmail.com>

BTRFS: Implement RemoveEntries() for BTree that will remove consecutive items and its data.

Signed-off-by: Augustin Cavalier <waddlesplash@gmail.com>

BTRFS: Implement InsertEntries() that will insert consecutive items and its data.

Signed-off-by: Augustin Cavalier <waddlesplash@gmail.com>

BTRFS: Implement CopyOnWrite relevant functions, and BTree holds new attribute that record its root level.

CopyOnWrite works like this:
* Cache original node
* Allocating new block
* Cache new block to be writable
* Copy original node to new node, and changing.
Also if a node is already be COW-ed it cannot be COW-ed again, it will be changed in-place instead.

InternalCopy does CopyOnWrite all the nodes that we don't need to change anything on them.

Signed-off-by: Augustin Cavalier <waddlesplash@gmail.com>

BTRFS: Implement some copy relevant helpers.

Copy() copys data from other node, MoveEntries() changes data on the current node.

Signed-off-by: Augustin Cavalier <waddlesplash@gmail.com>

BTRFS: Implement some space relevant helpers.

Signed-off-by: Augustin Cavalier <waddlesplash@gmail.com>

BTRFS: Reimplement TreeIterator, add some error checks and remove redundancies.

Add BTree::Path as a attribute so enhance performance, so that everytime we iterate through items it wont search all the root to leaf
again. The Iterator is initialized without rewinding to make more flexible.

Signed-off-by: Augustin Cavalier <waddlesplash@gmail.com>

BTRFS: Implement BTree::Path and change _Find.

Remove attribute fCurrentSlot in BTree::Node as it will be handled by Path explicitly. BTree control Path by passing its type in
BTree's method, Path also hold BTree type as its attribute to do some internal actions.
Add constant BTREE_KEY_TYPE_ANY, find search key has this type will success regardless of the found key's type.

Split the the _Find function into Traverse and GetEntry. Traverse will fill in the Path (nodes and slots) along way its finding,
GetEntry will get the item data, item size, key from leaf, if the slot is valid, that we have from Traverse. The _Find function also
check type if is correct and then retrieve. Doing this way there will be more flexible, the "read" flag is not needed as we only
need Path to manipulate tree, and it also enhance the performance at some points, because Path caches all the nodes from root to leaf,
so that we don't have to block_cache_put and block_cache_get after each finding.

Signed-off-by: Augustin Cavalier <waddlesplash@gmail.com>

BTRFS: Node now holding Volume instead of cache to retrieve more values

Signed-off-by: Augustin Cavalier <waddlesplash@gmail.com>

BTRFS: Fix mismatched type of item size (should be uint32), and ObjectID of first subvolume when lookup directory (described in commit bd2dab1)

Signed-off-by: Augustin Cavalier <waddlesplash@gmail.com>

BTRFS: Fix node search slot

* Not handle traversing type correctly (looks for the graph).
* Reorder the codes because *slot is uninitialized if type is BTREE_EXACT.
* Incorrect return type: int32 -> status_t

Signed-off-by: Augustin Cavalier <waddlesplash@gmail.com>

BTRFS: Some modifications of BTree _Find

* Added "read" argument, may change variable type in the future instead of just bool variable.
* Now search key's objectId is changed to found key's objectId.

BTRFS: Added retrieve Volume from BTree

BTRFS: Added logical address (root) for BTree

BTRFS: rename BNode and BPath

Changed name BNode, BPath to Node, Path and move them into BTree
as the original names are already exist in Haiku Storage Kit.

Signed-off-by: Adrien Destugues <pulkomandy@pulkomandy.tk>

BTRFS: Combine BNode and _Find

* Replaced fStream by BNode, this might fix errors when handling BTree with multiple levels because fStream remains at leaf after first allocating.
* Changed search algorithm for items (linear search -> binary search)

Signed-off-by: Adrien Destugues <pulkomandy@pulkomandy.tk>

BTRFS: Added retrieve RootBlock of BTree

Signed-off-by: Adrien Destugues <pulkomandy@pulkomandy.tk>

BTRFS: Enhanced node search slot to handle btree_traverse type

Signed-off-by: Adrien Destugues <pulkomandy@pulkomandy.tk>

BTRFS: Added SetRoot for tree. Tree root is initialized at mount time

Signed-off-by: Adrien Destugues <pulkomandy@pulkomandy.tk>

BTRFS: BlockNum -> LogicalAddress to prevent misunderstanding

Signed-off-by: Adrien Destugues <pulkomandy@pulkomandy.tk>

BTRFS: Added binary search for item slot

Signed-off-by: Adrien Destugues <pulkomandy@pulkomandy.tk>

BTRFS: Initialize BPath and BNode for tree manipulation

Signed-off-by: Adrien Destugues <pulkomandy@pulkomandy.tk>

BTRFS: Method _Compare from BTree is now in btrfs_key

Signed-off-by: Adrien Destugues <pulkomandy@pulkomandy.tk>

BTRFS: code cleanups

* Removed struct keyword for declaring variable.
* Renamed BPlusTree to BTree because BtrFS use a variant of BTree not B+Tree.

Signed-off-by: Adrien Destugues <pulkomandy@pulkomandy.tk>