[haiku-commits] haiku: hrev45602 - in src: system/boot/loader/file_systems/bfs add-ons/kernel/file_systems/bfs
- From: mmlr@xxxxxxxx
- To: haiku-commits@xxxxxxxxxxxxx
- Date: Thu, 2 May 2013 23:26:37 +0200 (CEST)
hrev45602 adds 4 changesets to branch 'master'
old head: bb169747582db8345d31662a62ec05ecda64835b
new head: 8a43cad2ef51b227d80be6e20f37b14c2a0dbde4
overview: http://cgit.haiku-os.org/haiku/log/?qt=range&q=8a43cad+%5Ebb16974
----------------------------------------------------------------------------
6b65a83: BPlusTree: Style cleanup only, no functional change.
1a5e87c: haiku_loader: Reuse BPlusTree implementation of the BFS add-on.
Instead of having an almost exact, albeit read only, duplicate of the
implementation.
50ef2db: BPlusTree: Fix GCC4 false positive of possible unintialized use.
8a43cad: BPlusTree: Fix fCurrentKey in backward TreeIterator traversal.
When reaching the next node the current key should be set to the next
valid index within that node (0 for forward and NumKeys() - 1 for
backward). This did not cause any harm as BFS uses forward traversal
only.
[ Michael Lotz <mmlr@xxxxxxxx> ]
----------------------------------------------------------------------------
6 files changed, 155 insertions(+), 1276 deletions(-)
.../kernel/file_systems/bfs/BPlusTree.cpp | 98 +-
src/add-ons/kernel/file_systems/bfs/BPlusTree.h | 66 +-
.../boot/loader/file_systems/bfs/BPlusTree.cpp | 889 -------------------
.../boot/loader/file_systems/bfs/BPlusTree.h | 374 --------
src/system/boot/loader/file_systems/bfs/Jamfile | 3 +
src/system/boot/loader/file_systems/bfs/Stream.h | 1 +
############################################################################
Commit: 6b65a838e01488536628e807b7b65bb73468f8d4
URL: http://cgit.haiku-os.org/haiku/commit/?id=6b65a83
Author: Michael Lotz <mmlr@xxxxxxxx>
Date: Thu May 2 18:09:00 2013 UTC
BPlusTree: Style cleanup only, no functional change.
----------------------------------------------------------------------------
diff --git a/src/add-ons/kernel/file_systems/bfs/BPlusTree.cpp
b/src/add-ons/kernel/file_systems/bfs/BPlusTree.cpp
index 70c9608..9b47683 100644
--- a/src/add-ons/kernel/file_systems/bfs/BPlusTree.cpp
+++ b/src/add-ons/kernel/file_systems/bfs/BPlusTree.cpp
@@ -88,7 +88,7 @@ private:
int32 fSize;
const char* fText;
};
-#endif
+#endif // DEBUG
class BitmapArray {
@@ -289,8 +289,9 @@ CachedNode::SetTo(off_t offset, const bplustree_node**
_node, bool check)
// instead)
if (offset > fTree->fHeader.MaximumSize() - fTree->fNodeSize
|| offset <= 0
- || (offset % fTree->fNodeSize) != 0)
+ || (offset % fTree->fNodeSize) != 0) {
RETURN_ERROR(B_BAD_VALUE);
+ }
if (InternalSetTo(NULL, offset) != NULL && check) {
// sanity checks (links, all_key_count)
@@ -345,8 +346,9 @@ CachedNode::MakeWritable(Transaction& transaction)
return NULL;
if (block_cache_make_writable(transaction.GetVolume()->BlockCache(),
- fBlockNumber, transaction.ID()) == B_OK)
+ fBlockNumber, transaction.ID()) == B_OK) {
return fNode;
+ }
return NULL;
}
############################################################################
Commit: 1a5e87cc6491bdc291ac44287232d66b2055deca
URL: http://cgit.haiku-os.org/haiku/commit/?id=1a5e87c
Author: Michael Lotz <mmlr@xxxxxxxx>
Date: Thu May 2 19:06:13 2013 UTC
haiku_loader: Reuse BPlusTree implementation of the BFS add-on.
Instead of having an almost exact, albeit read only, duplicate of the
implementation.
----------------------------------------------------------------------------
diff --git a/src/add-ons/kernel/file_systems/bfs/BPlusTree.cpp
b/src/add-ons/kernel/file_systems/bfs/BPlusTree.cpp
index 9b47683..b5ef6c6 100644
--- a/src/add-ons/kernel/file_systems/bfs/BPlusTree.cpp
+++ b/src/add-ons/kernel/file_systems/bfs/BPlusTree.cpp
@@ -12,9 +12,21 @@
#include "Debug.h"
#include "BPlusTree.h"
-#include "Inode.h"
#include "Utility.h"
+#if !_BOOT_MODE
+#include "Inode.h"
+#else
+#include "Stream.h"
+
+// BFS::Stream from the bootloader has the same API as Inode.
+#define Inode BFS::Stream
+
+#define strerror(x) "error message unavailable"
+
+namespace BFS {
+#endif
+
/*! Simple array used for the duplicate handling in the B+Tree. This is an
on disk structure.
@@ -91,6 +103,7 @@ private:
#endif // DEBUG
+#if !_BOOT_MODE
class BitmapArray {
public:
BitmapArray(size_t numBits);
@@ -243,6 +256,7 @@ CachedNode::UnsetUnchanged(Transaction& transaction)
fNode = NULL;
}
}
+#endif // !_BOOT_MODE
void
@@ -252,6 +266,7 @@ CachedNode::Unset()
return;
if (fNode != NULL) {
+#if !_BOOT_MODE
if (fWritable && fOffset == 0) {
// The B+tree header has been updated - we need to
update the
// BPlusTrees copy of it, as well.
@@ -260,6 +275,8 @@ CachedNode::Unset()
block_cache_put(fTree->fStream->GetVolume()->BlockCache(),
fBlockNumber);
+#endif // !_BOOT_MODE
+
fNode = NULL;
}
}
@@ -308,6 +325,7 @@ CachedNode::SetTo(off_t offset, const bplustree_node**
_node, bool check)
}
+#if !_BOOT_MODE
bplustree_node*
CachedNode::SetToWritable(Transaction& transaction, off_t offset, bool check)
{
@@ -352,6 +370,7 @@ CachedNode::MakeWritable(Transaction& transaction)
return NULL;
}
+#endif // !_BOOT_MODE
const bplustree_header*
@@ -369,6 +388,7 @@ CachedNode::SetToHeader()
}
+#if !_BOOT_MODE
bplustree_header*
CachedNode::SetToWritableHeader(Transaction& transaction)
{
@@ -393,6 +413,7 @@ CachedNode::SetToWritableHeader(Transaction& transaction)
return (bplustree_header*)fNode;
}
+#endif // !_BOOT_MODE
bplustree_node*
@@ -405,12 +426,18 @@ CachedNode::InternalSetTo(Transaction* transaction, off_t
offset)
block_run run;
if (offset < fTree->fStream->Size()
&& fTree->fStream->FindBlockRun(offset, run, fileOffset) ==
B_OK) {
+
+#if !_BOOT_MODE
Volume* volume = fTree->fStream->GetVolume();
+#else
+ Volume* volume = &fTree->fStream->GetVolume();
+#endif
int32 blockOffset = (offset - fileOffset) / volume->BlockSize();
fBlockNumber = volume->ToBlock(run) + blockOffset;
- uint8* block;
+ uint8* block = NULL;
+#if !_BOOT_MODE
if (transaction != NULL) {
block =
(uint8*)block_cache_get_writable(volume->BlockCache(),
fBlockNumber, transaction->ID());
@@ -419,6 +446,20 @@ CachedNode::InternalSetTo(Transaction* transaction, off_t
offset)
block = (uint8*)block_cache_get(volume->BlockCache(),
fBlockNumber);
fWritable = false;
}
+#else // !_BOOT_MODE
+ if (fBlock == NULL) {
+ fBlock = (uint8*)malloc(volume->BlockSize());
+ if (fBlock == NULL)
+ return NULL;
+ }
+
+ if (read_pos(volume->Device(), fBlockNumber <<
volume->BlockShift(),
+ fBlock, volume->BlockSize()) ==
(ssize_t)volume->BlockSize()) {
+ block = fBlock;
+ }
+
+ fWritable = false;
+#endif // _BOOT_MODE
if (block != NULL) {
// The node is somewhere in that block...
@@ -432,6 +473,7 @@ CachedNode::InternalSetTo(Transaction* transaction, off_t
offset)
}
+#if !_BOOT_MODE
status_t
CachedNode::Free(Transaction& transaction, off_t offset)
{
@@ -542,6 +584,7 @@ BPlusTree::BPlusTree(Transaction& transaction, Inode*
stream, int32 nodeSize)
mutex_init(&fIteratorLock, "bfs b+tree iterator");
SetTo(transaction, stream);
}
+#endif // !_BOOT_MODE
BPlusTree::BPlusTree(Inode* stream)
@@ -549,7 +592,10 @@ BPlusTree::BPlusTree(Inode* stream)
fStream(NULL),
fInTransaction(false)
{
+#if !_BOOT_MODE
mutex_init(&fIteratorLock, "bfs b+tree iterator");
+#endif
+
SetTo(stream);
}
@@ -562,12 +608,15 @@ BPlusTree::BPlusTree()
fInTransaction(false),
fStatus(B_NO_INIT)
{
+#if !_BOOT_MODE
mutex_init(&fIteratorLock, "bfs b+tree iterator");
+#endif
}
BPlusTree::~BPlusTree()
{
+#if !_BOOT_MODE
// if there are any TreeIterators left, we need to stop them
// (can happen when the tree's inode gets deleted while
// traversing the tree - a TreeIterator doesn't lock the inode)
@@ -581,9 +630,11 @@ BPlusTree::~BPlusTree()
mutex_destroy(&fIteratorLock);
ASSERT(!fInTransaction);
+#endif // !_BOOT_MODE
}
+#if !_BOOT_MODE
/*! Create a new B+Tree on the specified stream */
status_t
BPlusTree::SetTo(Transaction& transaction, Inode* stream, int32 nodeSize)
@@ -631,6 +682,7 @@ BPlusTree::SetTo(Transaction& transaction, Inode* stream,
int32 nodeSize)
return fStatus = B_OK;
}
+#endif // !_BOOT_MODE
status_t
@@ -703,6 +755,7 @@ BPlusTree::InitCheck()
}
+#if !_BOOT_MODE
status_t
BPlusTree::Validate(bool repair, bool& _errorsFound)
{
@@ -885,11 +938,13 @@ BPlusTree::ModeToKeyType(mode_t mode)
return BPLUSTREE_STRING_TYPE;
}
}
+#endif // !_BOOT_MODE
// #pragma mark - TransactionListener implementation
+#if !_BOOT_MODE
void
BPlusTree::TransactionDone(bool success)
{
@@ -946,6 +1001,7 @@ BPlusTree::_RemoveIterator(TreeIterator* iterator)
MutexLocker _(fIteratorLock);
fIterators.Remove(iterator);
}
+#endif // !_BOOT_MODE
int32
@@ -1008,7 +1064,9 @@ BPlusTree::_FindKey(const bplustree_node* node, const
uint8* key,
if (searchKey + searchLength + sizeof(off_t) + sizeof(uint16)
> (uint8*)node + fNodeSize
|| searchLength > BPLUSTREE_MAX_KEY_LENGTH) {
+#if !_BOOT_MODE
fStream->GetVolume()->Panic();
+#endif
RETURN_ERROR(B_BAD_DATA);
}
@@ -1039,6 +1097,7 @@ BPlusTree::_FindKey(const bplustree_node* node, const
uint8* key,
}
+#if !_BOOT_MODE
/*! Prepares the stack to contain all nodes that were passed while
following the key, from the root node to the leaf node that could
or should contain that key.
@@ -2198,6 +2257,7 @@ BPlusTree::Replace(Transaction& transaction, const uint8*
key, uint16 keyLength,
}
RETURN_ERROR(B_ERROR);
}
+#endif // !_BOOT_MODE
/*! Searches the key in the tree, and stores the offset found in _value,
@@ -2222,7 +2282,9 @@ BPlusTree::Find(const uint8* key, uint16 keyLength,
off_t* _value)
if (fAllowDuplicates)
RETURN_ERROR(B_BAD_TYPE);
+#if !_BOOT_MODE
ASSERT_READ_LOCKED_INODE(fStream);
+#endif
off_t nodeOffset = fHeader.RootNode();
CachedNode cached(this);
@@ -2261,6 +2323,7 @@ BPlusTree::Find(const uint8* key, uint16 keyLength,
off_t* _value)
}
+#if !_BOOT_MODE
status_t
BPlusTree::_ValidateChildren(TreeCheck& check, uint32 level, off_t offset,
const uint8* largestKey, uint16 largestKeyLength,
@@ -2484,6 +2547,7 @@ BPlusTree::_ValidateChild(TreeCheck& check, CachedNode&
cached, uint32 level,
return _ValidateChildren(check, level + 1, offset, key, keyLength,
node);
}
+#endif // !_BOOT_MODE
// #pragma mark -
@@ -2494,14 +2558,18 @@ TreeIterator::TreeIterator(BPlusTree* tree)
fTree(tree),
fCurrentNodeOffset(BPLUSTREE_NULL)
{
+#if !_BOOT_MODE
tree->_AddIterator(this);
+#endif
}
TreeIterator::~TreeIterator()
{
+#if !_BOOT_MODE
if (fTree)
fTree->_RemoveIterator(this);
+#endif
}
@@ -2511,8 +2579,10 @@ TreeIterator::Goto(int8 to)
if (fTree == NULL || fTree->fStream == NULL)
RETURN_ERROR(B_BAD_VALUE);
+#if !_BOOT_MODE
// lock access to stream
InodeReadLocker locker(fTree->fStream);
+#endif
off_t nodeOffset = fTree->fHeader.RootNode();
CachedNode cached(fTree);
@@ -2580,8 +2650,10 @@ TreeIterator::Traverse(int8 direction, void* key,
uint16* keyLength,
if (fCurrentNodeOffset == BPLUSTREE_FREE)
return B_ENTRY_NOT_FOUND;
+#if !_BOOT_MODE
// lock access to stream
InodeReadLocker locker(fTree->fStream);
+#endif
CachedNode cached(fTree);
const bplustree_node* node;
@@ -2661,7 +2733,9 @@ TreeIterator::Traverse(int8 direction, void* key, uint16*
keyLength,
if (keyStart + length + sizeof(off_t) + sizeof(uint16)
> (uint8*)node + fTree->fNodeSize
|| length > BPLUSTREE_MAX_KEY_LENGTH) {
+#if !_BOOT_MODE
fTree->fStream->GetVolume()->Panic();
+#endif
RETURN_ERROR(B_BAD_DATA);
}
@@ -2729,8 +2803,10 @@ TreeIterator::Find(const uint8* key, uint16 keyLength)
|| key == NULL)
RETURN_ERROR(B_BAD_VALUE);
+#if !_BOOT_MODE
// lock access to stream
InodeReadLocker locker(fTree->fStream);
+#endif
off_t nodeOffset = fTree->fHeader.RootNode();
@@ -2932,6 +3008,7 @@ bplustree_node::CheckIntegrity(uint32 nodeSize) const
// #pragma mark -
+#if !_BOOT_MODE
BitmapArray::BitmapArray(size_t numBits)
{
fSize = (numBits + 7) / 8;
@@ -2979,6 +3056,7 @@ BitmapArray::Set(size_t index, bool set)
fCountSet--;
}
}
+#endif // !_BOOT_MODE
// #pragma mark -
@@ -3134,3 +3212,7 @@ compareKeys(type_code type, const void* key1, int
keyLength1,
return -1;
}
+
+#if _BOOT_MODE
+} // namespace BFS
+#endif
diff --git a/src/add-ons/kernel/file_systems/bfs/BPlusTree.h
b/src/add-ons/kernel/file_systems/bfs/BPlusTree.h
index c1e1ad2..cfc4aac 100644
--- a/src/add-ons/kernel/file_systems/bfs/BPlusTree.h
+++ b/src/add-ons/kernel/file_systems/bfs/BPlusTree.h
@@ -7,8 +7,21 @@
#include "bfs.h"
+
+#include "Utility.h"
+
+#if !_BOOT_MODE
#include "Journal.h"
+class Inode;
+#else
+#define Inode BFS::Stream
+
+namespace BFS {
+class Stream;
+class Transaction;
+class TransactionListener {};
+#endif // _BOOT_MODE
// #pragma mark - on-disk structures
@@ -132,18 +145,21 @@ enum bplustree_traversing {
// #pragma mark - in-memory structures
-template<class T> class Stack;
+
class BPlusTree;
-class TreeIterator;
-class CachedNode;
-class Inode;
struct TreeCheck;
+class TreeIterator;
+
+
+#if !_BOOT_MODE
+template<class T> class Stack;
// needed for searching (utilizing a stack)
struct node_and_key {
off_t nodeOffset;
uint16 keyIndex;
};
+#endif // !_BOOT_MODE
class CachedNode {
@@ -153,6 +169,9 @@ public:
fTree(tree),
fNode(NULL)
{
+#if _BOOT_MODE
+ fBlock = NULL;
+#endif
}
CachedNode(BPlusTree* tree, off_t offset, bool check = true)
@@ -160,30 +179,40 @@ public:
fTree(tree),
fNode(NULL)
{
+#if _BOOT_MODE
+ fBlock = NULL;
+#endif
SetTo(offset, check);
}
~CachedNode()
{
Unset();
+#if _BOOT_MODE
+ free(fBlock);
+#endif
}
const bplustree_node* SetTo(off_t offset, bool check =
true);
status_t SetTo(off_t offset,
const
bplustree_node** _node,
bool
check = true);
+
+ const bplustree_header* SetToHeader();
+ void Unset();
+
+#if !_BOOT_MODE
bplustree_node* SetToWritable(Transaction&
transaction,
off_t
offset, bool check = true);
bplustree_node* MakeWritable(Transaction&
transaction);
- const bplustree_header* SetToHeader();
bplustree_header*
SetToWritableHeader(Transaction& transaction);
void
UnsetUnchanged(Transaction& transaction);
- void Unset();
status_t Free(Transaction&
transaction, off_t offset);
status_t Allocate(Transaction&
transaction,
bplustree_node** _node, off_t* _offset);
+#endif // !_BOOT_MODE
bool IsWritable() const {
return fWritable; }
bplustree_node* Node() const { return fNode; }
@@ -197,20 +226,27 @@ protected:
off_t fOffset;
off_t fBlockNumber;
bool fWritable;
+#if _BOOT_MODE
+ uint8* fBlock;
+#endif
};
class BPlusTree : public TransactionListener {
public:
+#if !_BOOT_MODE
BPlusTree(Transaction& transaction,
Inode*
stream,
int32
nodeSize = BPLUSTREE_NODE_SIZE);
+#endif
BPlusTree(Inode* stream);
BPlusTree();
~BPlusTree();
+#if !_BOOT_MODE
status_t SetTo(Transaction&
transaction, Inode* stream,
int32
nodeSize = BPLUSTREE_NODE_SIZE);
+#endif
status_t SetTo(Inode* stream);
status_t SetStream(Inode*
stream);
@@ -219,6 +255,7 @@ public:
size_t NodeSize() const {
return fNodeSize; }
Inode* Stream() const { return
fStream; }
+#if !_BOOT_MODE
status_t Validate(bool repair,
bool& _errorsFound);
status_t MakeEmpty();
@@ -249,15 +286,19 @@ public:
status_t Replace(Transaction&
transaction,
const
uint8* key, uint16 keyLength,
off_t
value);
+#endif // !_BOOT_MODE
+
status_t Find(const uint8* key,
uint16 keyLength,
off_t*
value);
+#if !_BOOT_MODE
static int32 TypeCodeToKeyType(type_code
code);
static int32 ModeToKeyType(mode_t mode);
protected:
virtual void TransactionDone(bool success);
virtual void RemovedFromTransaction();
+#endif // !_BOOT_MODE
private:
BPlusTree(const
BPlusTree& other);
@@ -269,6 +310,7 @@ private:
status_t _FindKey(const
bplustree_node* node,
const
uint8* key, uint16 keyLength,
uint16*
index = NULL, off_t* next = NULL);
+#if !_BOOT_MODE
status_t
_SeekDown(Stack<node_and_key>& stack,
const
uint8* key, uint16 keyLength);
@@ -310,6 +352,7 @@ private:
off_t
offset, off_t lastOffset,
off_t
nextOffset, const uint8* key,
uint16
keyLength);
+#endif // !_BOOT_MODE
private:
friend class TreeIterator;
@@ -322,8 +365,11 @@ private:
bool fAllowDuplicates;
bool fInTransaction;
status_t fStatus;
+
+#if !_BOOT_MODE
mutex fIteratorLock;
SinglyLinkedList<TreeIterator> fIterators;
+#endif
};
@@ -385,6 +431,7 @@ private:
// (most of them may not be needed)
+#if !_BOOT_MODE
inline status_t
BPlusTree::Remove(Transaction& transaction, const char* key, off_t value)
{
@@ -455,6 +502,7 @@ BPlusTree::Insert(Transaction& transaction, double key,
off_t value)
return B_BAD_TYPE;
return Insert(transaction, (uint8*)&key, sizeof(key), value);
}
+#endif // !_BOOT_MODE
// #pragma mark - TreeIterator inline functions
@@ -606,4 +654,10 @@ bplustree_node::MaxFragments(uint32 nodeSize)
}
+#if _BOOT_MODE
+} // namespace BFS
+
+#undef Inode
+#endif
+
#endif // B_PLUS_TREE_H
diff --git a/src/system/boot/loader/file_systems/bfs/BPlusTree.cpp
b/src/system/boot/loader/file_systems/bfs/BPlusTree.cpp
deleted file mode 100644
index 8b8ee8f..0000000
--- a/src/system/boot/loader/file_systems/bfs/BPlusTree.cpp
+++ /dev/null
@@ -1,889 +0,0 @@
-/*
- * Copyright 2001-2010, Axel Dörfler, axeld@xxxxxxxxxxxxxxxx.
- * This file may be used under the terms of the MIT License.
- *
- * Roughly based on 'btlib' written by Marcus J. Ranum - it shares
- * no code but achieves binary compatibility with the on disk format.
- */
-
-
-#include "BPlusTree.h"
-
-#include <boot/platform.h>
-#include <util/kernel_cpp.h>
-#include <util/Stack.h>
-
-#include <TypeConstants.h>
-
-#include <unistd.h>
-#include <string.h>
-#include <stdlib.h>
-#include <stdio.h>
-
-using namespace BFS;
-
-
-// Node Caching for the BPlusTree class
-//
-// With write support, there is the need for a function that allocates new
-// nodes by either returning empty nodes, or by growing the file's data stream
-//
-// !! The CachedNode class assumes that you have properly locked the stream
-// !! before asking for nodes.
-//
-// Note: This code will fail if the block size is smaller than the node size!
-// Since BFS supports block sizes of 1024 bytes or greater, and the node size
-// is hard-coded to 1024 bytes, that's not an issue now.
-
-
-void
-CachedNode::Unset()
-{
- if (fTree == NULL || fTree->fStream == NULL)
- return;
-
- if (fBlock != NULL)
- fNode = NULL;
-}
-
-
-bplustree_node *
-CachedNode::SetTo(off_t offset, bool check)
-{
- if (fTree == NULL || fTree->fStream == NULL)
- return NULL;
-
- Unset();
-
- // You can only ask for nodes at valid positions - you can't
- // even access the b+tree header with this method (use SetToHeader()
- // instead)
- if (offset > fTree->fHeader->MaximumSize() - fTree->fNodeSize
- || offset <= 0
- || (offset % fTree->fNodeSize) != 0)
- return NULL;
-
- if (InternalSetTo(offset) != NULL && check) {
- // sanity checks (links, all_key_count)
- bplustree_header *header = fTree->fHeader;
- if (!header->IsValidLink(fNode->LeftLink())
- || !header->IsValidLink(fNode->RightLink())
- || !header->IsValidLink(fNode->OverflowLink())
- || (int8 *)fNode->Values() + fNode->NumKeys() *
sizeof(off_t)
- > (int8 *)fNode + fTree->fNodeSize) {
- dprintf("invalid node read from offset %Ld, inode at
%Ld\n",
- offset, fTree->fStream->ID());
- return NULL;
- }
- }
-
- return fNode;
-}
-
-
-bplustree_header *
-CachedNode::SetToHeader()
-{
- if (fTree == NULL || fTree->fStream == NULL)
- return NULL;
-
- Unset();
-
- InternalSetTo(0LL);
- return (bplustree_header *)fNode;
-}
-
-
-bplustree_node *
-CachedNode::InternalSetTo(off_t offset)
-{
- fNode = NULL;
-
- off_t fileOffset;
- block_run run;
- if (offset < fTree->fStream->Size()
- && fTree->fStream->FindBlockRun(offset, run, fileOffset) ==
B_OK) {
- Volume &volume = fTree->fStream->GetVolume();
-
- int32 blockOffset = (offset - fileOffset) / volume.BlockSize();
- fBlockNumber = volume.ToBlock(run) + blockOffset;
-
- if (fBlock == NULL) {
- fBlock = (uint8 *)malloc(volume.BlockSize());
- if (fBlock == NULL)
- return NULL;
- }
- if (read_pos(volume.Device(), fBlockNumber <<
volume.BlockShift(),
- fBlock, volume.BlockSize()) <
(ssize_t)volume.BlockSize())
- return NULL;
-
- // the node is somewhere in that block... (confusing offset
calculation)
- fNode = (bplustree_node *)(fBlock + offset -
- (fileOffset + (blockOffset <<
volume.BlockShift())));
- }
- return fNode;
-}
-
-
-// #pragma mark -
-
-
-BPlusTree::BPlusTree(Stream *stream)
- :
- fStream(NULL),
- fHeader(NULL),
- fCachedHeader(this)
-{
- SetTo(stream);
-}
-
-
-BPlusTree::~BPlusTree()
-{
-}
-
-
-status_t
-BPlusTree::SetTo(Stream *stream)
-{
- if (stream == NULL || stream->InitCheck() != B_OK)
- return fStatus = B_BAD_VALUE;
-
- // get on-disk B+Tree header
-
- fCachedHeader.Unset();
- fStream = stream;
-
- fHeader = fCachedHeader.SetToHeader();
- if (fHeader == NULL)
- return fStatus = B_NO_INIT;
-
- // is header valid?
-
- if (fHeader->Magic() != BPLUSTREE_MAGIC
- || fHeader->MaximumSize() != stream->Size()
- || (fHeader->RootNode() % fHeader->NodeSize()) != 0
- || !fHeader->IsValidLink(fHeader->RootNode()))
- return fStatus = B_BAD_DATA;
-
- fNodeSize = fHeader->NodeSize();
-
- {
- uint32 toMode[] = {S_STR_INDEX, S_INT_INDEX, S_UINT_INDEX,
- S_LONG_LONG_INDEX, S_ULONG_LONG_INDEX, S_FLOAT_INDEX,
- S_DOUBLE_INDEX};
- uint32 mode = stream->Mode() & (S_STR_INDEX | S_INT_INDEX
- | S_UINT_INDEX | S_LONG_LONG_INDEX | S_ULONG_LONG_INDEX
- | S_FLOAT_INDEX | S_DOUBLE_INDEX);
-
- if (fHeader->DataType() > BPLUSTREE_DOUBLE_TYPE
- || ((stream->Mode() & S_INDEX_DIR) != 0
- && toMode[fHeader->DataType()] != mode)
- || !stream->IsContainer()) {
- return fStatus = B_BAD_TYPE;
- }
-
-#ifdef BPLUSTREE_SUPPORTS_DUPLICATES
- // although it's in stat.h, the S_ALLOW_DUPS flag is obviously
unused
- // in the original BFS code - we will honour it nevertheless
- fAllowDuplicates = ((stream->Mode() & S_INDEX_DIR) ==
S_INDEX_DIR
- && stream->BlockRun() != stream->Parent())
- || (stream->Mode() & S_ALLOW_DUPS) != 0;
-#endif
- }
-
- CachedNode cached(this, fHeader->RootNode());
-
- return fStatus = cached.Node() ? B_OK : B_BAD_DATA;
-}
-
-
-status_t
-BPlusTree::InitCheck()
-{
- return fStatus;
-}
-
-
-int32
-BPlusTree::TypeCodeToKeyType(type_code code)
-{
- switch (code) {
- case B_STRING_TYPE:
- return BPLUSTREE_STRING_TYPE;
- case B_INT32_TYPE:
- case B_SSIZE_T_TYPE:
- return BPLUSTREE_INT32_TYPE;
- case B_UINT32_TYPE:
- case B_SIZE_T_TYPE:
- return BPLUSTREE_UINT32_TYPE;
- case B_OFF_T_TYPE:
- case B_INT64_TYPE:
- return BPLUSTREE_INT64_TYPE;
- case B_UINT64_TYPE:
- return BPLUSTREE_UINT64_TYPE;
- case B_FLOAT_TYPE:
- return BPLUSTREE_FLOAT_TYPE;
- case B_DOUBLE_TYPE:
- return BPLUSTREE_DOUBLE_TYPE;
- }
- return -1;
-}
-
-
-int32
-BPlusTree::ModeToKeyType(mode_t mode)
-{
- switch (mode & (S_STR_INDEX | S_INT_INDEX | S_UINT_INDEX |
S_LONG_LONG_INDEX
- | S_ULONG_LONG_INDEX | S_FLOAT_INDEX |
S_DOUBLE_INDEX)) {
- case S_INT_INDEX:
- return BPLUSTREE_INT32_TYPE;
- case S_UINT_INDEX:
- return BPLUSTREE_UINT32_TYPE;
- case S_LONG_LONG_INDEX:
- return BPLUSTREE_INT64_TYPE;
- case S_ULONG_LONG_INDEX:
- return BPLUSTREE_UINT64_TYPE;
- case S_FLOAT_INDEX:
- return BPLUSTREE_FLOAT_TYPE;
- case S_DOUBLE_INDEX:
- return BPLUSTREE_DOUBLE_TYPE;
- case S_STR_INDEX:
- default:
- // default is for standard directories
- return BPLUSTREE_STRING_TYPE;
- }
-}
-
-
-int32
-BPlusTree::CompareKeys(const void *key1, int keyLength1, const void *key2, int
keyLength2)
-{
- type_code type = 0;
- switch (fHeader->DataType())
- {
- case BPLUSTREE_STRING_TYPE:
- type = B_STRING_TYPE;
- break;
- case BPLUSTREE_INT32_TYPE:
- type = B_INT32_TYPE;
- break;
- case BPLUSTREE_UINT32_TYPE:
- type = B_UINT32_TYPE;
- break;
- case BPLUSTREE_INT64_TYPE:
- type = B_INT64_TYPE;
- break;
- case BPLUSTREE_UINT64_TYPE:
- type = B_UINT64_TYPE;
- break;
- case BPLUSTREE_FLOAT_TYPE:
- type = B_FLOAT_TYPE;
- break;
- case BPLUSTREE_DOUBLE_TYPE:
- type = B_DOUBLE_TYPE;
- break;
- }
- return compareKeys(type, key1, keyLength1, key2, keyLength2);
-}
-
-
-status_t
-BPlusTree::FindKey(bplustree_node *node, const uint8 *key, uint16 keyLength,
uint16 *index,
- off_t *next)
-{
- if (node->all_key_count == 0) {
- if (index)
- *index = 0;
- if (next)
- *next = node->OverflowLink();
- return B_ENTRY_NOT_FOUND;
- }
-
- off_t *values = node->Values();
- int16 saveIndex = -1;
-
- // binary search in the key array
- for (int16 first = 0, last = node->NumKeys() - 1; first <= last;) {
- uint16 i = (first + last) >> 1;
-
- uint16 searchLength;
- uint8 *searchKey = node->KeyAt(i, &searchLength);
- if (searchKey + searchLength + sizeof(off_t) + sizeof(uint16) >
(uint8 *)node + fNodeSize
- || searchLength > BPLUSTREE_MAX_KEY_LENGTH) {
- dprintf("bfs: bad B+tree data\n");
- return B_BAD_DATA;
- }
-
- int32 cmp = CompareKeys(key, keyLength, searchKey,
searchLength);
- if (cmp < 0) {
- last = i - 1;
- saveIndex = i;
- } else if (cmp > 0) {
- saveIndex = first = i + 1;
- } else {
- if (index)
- *index = i;
- if (next)
- *next = BFS_ENDIAN_TO_HOST_INT64(values[i]);
- return B_OK;
- }
- }
-
- if (index)
- *index = saveIndex;
- if (next) {
- if (saveIndex == node->NumKeys())
- *next = node->OverflowLink();
- else
- *next = BFS_ENDIAN_TO_HOST_INT64(values[saveIndex]);
- }
- return B_ENTRY_NOT_FOUND;
-}
-
-
-/** Prepares the stack to contain all nodes that were passed while
- * following the key, from the root node to the leaf node that could
- * or should contain that key.
- */
-
-status_t
-BPlusTree::SeekDown(Stack<node_and_key> &stack, const uint8 *key, uint16
keyLength)
-{
- // set the root node to begin with
- node_and_key nodeAndKey;
- nodeAndKey.nodeOffset = fHeader->RootNode();
-
- CachedNode cached(this);
- bplustree_node *node;
- while ((node = cached.SetTo(nodeAndKey.nodeOffset)) != NULL) {
- // if we are already on leaf level, we're done
- if (node->OverflowLink() == BPLUSTREE_NULL) {
- // node that the keyIndex is not properly set here (but
it's not
- // needed in the calling functions anyway)!
- nodeAndKey.keyIndex = 0;
- stack.Push(nodeAndKey);
- return B_OK;
- }
-
- off_t nextOffset;
- status_t status = FindKey(node, key, keyLength,
&nodeAndKey.keyIndex, &nextOffset);
-
- if (status == B_ENTRY_NOT_FOUND && nextOffset ==
nodeAndKey.nodeOffset)
- return B_ERROR;
-
- // put the node offset & the correct keyIndex on the stack
- stack.Push(nodeAndKey);
-
- nodeAndKey.nodeOffset = nextOffset;
- }
- return B_ERROR;
-}
-
-
-#ifdef BPLUSTREE_SUPPORTS_DUPLICATES
-status_t
-BPlusTree::FindFreeDuplicateFragment(bplustree_node *node, CachedNode *cached,
off_t *_offset,
- bplustree_node **_fragment, uint32 *_index)
-{
- off_t *values = node->Values();
- for (int32 i = 0;i < node->all_key_count;i++) {
- // does the value link to a duplicate fragment?
- if (bplustree_node::LinkType(values[i]) !=
BPLUSTREE_DUPLICATE_FRAGMENT)
- continue;
-
- bplustree_node *fragment =
cached->SetTo(bplustree_node::FragmentOffset(
- BFS_ENDIAN_TO_HOST_INT64(values[i])), false);
- if (fragment == NULL) {
- FATAL(("Could not get duplicate fragment at
%Ld\n",values[i]));
- continue;
- }
-
- // see if there is some space left for us
- int32 num = (fNodeSize >> 3) / (NUM_FRAGMENT_VALUES + 1);
- for (int32 j = 0;j < num;j++) {
- duplicate_array *array = fragment->FragmentAt(j);
-
- if (array->count == 0) {
- *_offset = bplustree_node::FragmentOffset(
- BFS_ENDIAN_TO_HOST_INT64(values[i]));
- *_fragment = fragment;
- *_index = j;
- return B_OK;
- }
- }
- }
- return B_ENTRY_NOT_FOUND;
-}
-#endif
-
-/** Searches the key in the tree, and stores the offset found in
- * _value, if successful.
- * It's very similar to BPlusTree::SeekDown(), but doesn't fill
- * a stack while it descends the tree.
- * Returns B_OK when the key could be found, B_ENTRY_NOT_FOUND
- * if not. It can also return other errors to indicate that
- * something went wrong.
- * Note that this doesn't work with duplicates - it will just
- * return B_BAD_TYPE if you call this function on a tree where
- * duplicates are allowed.
- */
-
-status_t
-BPlusTree::Find(const uint8 *key, uint16 keyLength, off_t *_value)
-{
- if (keyLength < BPLUSTREE_MIN_KEY_LENGTH || keyLength >
BPLUSTREE_MAX_KEY_LENGTH
- || key == NULL)
- return B_BAD_VALUE;
-
-#ifdef BPLUSTREE_SUPPORTS_DUPLICATES
- if (fAllowDuplicates)
- return B_BAD_TYPE;
-#endif
-
- off_t nodeOffset = fHeader->RootNode();
- CachedNode cached(this);
- bplustree_node *node;
-
- while ((node = cached.SetTo(nodeOffset)) != NULL) {
- uint16 keyIndex = 0;
- off_t nextOffset;
- status_t status = FindKey(node, key, keyLength, &keyIndex,
&nextOffset);
-
- if (node->OverflowLink() == BPLUSTREE_NULL) {
- if (status == B_OK && _value != NULL)
- *_value =
BFS_ENDIAN_TO_HOST_INT64(node->Values()[keyIndex]);
-
- return status;
- } else if (nextOffset == nodeOffset)
- return B_ERROR;
-
- nodeOffset = nextOffset;
- }
- return B_ERROR;
-}
-
-
-// #pragma mark -
-
-
-TreeIterator::TreeIterator(BPlusTree *tree)
- :
- fTree(tree),
- fCurrentNodeOffset(BPLUSTREE_NULL)
-{
-}
-
-
-TreeIterator::~TreeIterator()
-{
-}
-
-
-status_t
-TreeIterator::Goto(int8 to)
-{
- if (fTree == NULL || fTree->fHeader == NULL)
- return B_BAD_VALUE;
-
- off_t nodeOffset = fTree->fHeader->RootNode();
- CachedNode cached(fTree);
- bplustree_node *node;
-
- while ((node = cached.SetTo(nodeOffset)) != NULL) {
- // is the node a leaf node?
- if (node->OverflowLink() == BPLUSTREE_NULL) {
- fCurrentNodeOffset = nodeOffset;
- fCurrentKey = to == BPLUSTREE_BEGIN ? -1 :
node->NumKeys();
-#ifdef BPLUSTREE_SUPPORTS_DUPLICATES
- fDuplicateNode = BPLUSTREE_NULL;
-#endif
- return B_OK;
- }
-
- // get the next node offset depending on the direction (and if
there
- // are any keys in that node at all)
- off_t nextOffset;
- if (to == BPLUSTREE_END || node->all_key_count == 0)
- nextOffset = node->OverflowLink();
- else {
- if (node->AllKeyLength() > fTree->fNodeSize
- || (uint32)node->Values() > (uint32)node +
fTree->fNodeSize - 8 * node->NumKeys())
- return B_ERROR;
-
- nextOffset =
BFS_ENDIAN_TO_HOST_INT64(node->Values()[0]);
- }
- if (nextOffset == nodeOffset)
- break;
-
- nodeOffset = nextOffset;
- }
- return B_ERROR;
-}
-
-
-/** Iterates through the tree in the specified direction.
- * When it iterates through duplicates, the "key" is only updated for the
- * first entry - if you need to know when this happens, use the "duplicate"
- * parameter which is 0 for no duplicate, 1 for the first, and 2 for all
- * the other duplicates.
- * That's not too nice, but saves the 256 bytes that would be needed to
- * store the last key - if this will ever become an issue, it will be
- * easy to change.
- * The other advantage of this is, that the queries can skip all duplicates
- * at once when they are not relevant to them.
- */
-
-status_t
-TreeIterator::Traverse(int8 direction, void *key, uint16 *keyLength, uint16
maxLength,
- off_t *value, uint16 *duplicate)
-{
- if (fTree == NULL)
- return B_INTERRUPTED;
- if (fCurrentNodeOffset == BPLUSTREE_NULL
- && Goto(direction == BPLUSTREE_FORWARD ? BPLUSTREE_BEGIN :
BPLUSTREE_END) < B_OK)
- return B_ERROR;
-
- // if the tree was emptied since the last call
- if (fCurrentNodeOffset == BPLUSTREE_FREE)
- return B_ENTRY_NOT_FOUND;
-
- CachedNode cached(fTree);
- bplustree_node *node;
-
-#ifdef BPLUSTREE_SUPPORTS_DUPLICATES
- if (fDuplicateNode != BPLUSTREE_NULL) {
- // regardless of traverse direction the duplicates are always
presented
- // in the same order; since they are all considered as equal,
this
- // shouldn't cause any problems
-
- if (!fIsFragment || fDuplicate < fNumDuplicates) {
- node =
cached.SetTo(bplustree_node::FragmentOffset(fDuplicateNode),
- false);
- } else
- node = NULL;
-
- if (node != NULL) {
- if (!fIsFragment && fDuplicate >= fNumDuplicates) {
- // if the node is out of duplicates, we go
directly to the next
- // one
- fDuplicateNode = node->right_link;
- if (fDuplicateNode != BPLUSTREE_NULL
- && (node = cached.SetTo(fDuplicateNode,
false)) != NULL) {
- fNumDuplicates
- =
node->CountDuplicates(fDuplicateNode, false);
- fDuplicate = 0;
- }
- }
- if (fDuplicate < fNumDuplicates) {
- *value = node->DuplicateAt(fDuplicateNode,
fIsFragment,
- fDuplicate++);
- if (duplicate)
- *duplicate = 2;
- return B_OK;
- }
- }
- fDuplicateNode = BPLUSTREE_NULL;
- }
-#endif /* BPLUSTREE_SUPPORTS_DUPLICATES */
-
- off_t savedNodeOffset = fCurrentNodeOffset;
- if ((node = cached.SetTo(fCurrentNodeOffset)) == NULL)
- return B_ERROR;
-
-#ifdef BPLUSTREE_SUPPORTS_DUPLICATES
- if (duplicate)
- *duplicate = 0;
-#endif
-
- fCurrentKey += direction;
-
- // is the current key in the current node?
- while ((direction == BPLUSTREE_FORWARD && fCurrentKey >=
node->NumKeys())
- || (direction == BPLUSTREE_BACKWARD && fCurrentKey < 0))
- {
- fCurrentNodeOffset = direction == BPLUSTREE_FORWARD ?
node->RightLink() : node->LeftLink();
-
- // are there any more nodes?
- if (fCurrentNodeOffset != BPLUSTREE_NULL)
- {
- node = cached.SetTo(fCurrentNodeOffset);
- if (!node)
- return B_ERROR;
-
- // reset current key
- fCurrentKey = direction == BPLUSTREE_FORWARD ? 0 :
node->NumKeys();
- }
- else
- {
- // there are no nodes left, so turn back to the last key
- fCurrentNodeOffset = savedNodeOffset;
- fCurrentKey = direction == BPLUSTREE_FORWARD ?
node->NumKeys() : -1;
-
- return B_ENTRY_NOT_FOUND;
- }
- }
-
- if (node->all_key_count == 0)
- return B_ERROR; // B_ENTRY_NOT_FOUND ?
-
- uint16 length;
- uint8 *keyStart = node->KeyAt(fCurrentKey, &length);
- if (keyStart + length + sizeof(off_t) + sizeof(uint16) > (uint8 *)node
+ fTree->fNodeSize
- || length > BPLUSTREE_MAX_KEY_LENGTH) {
- dprintf("bfs: bad b+tree data\n");
- return B_BAD_DATA;
- }
-
- length = min_c(length, maxLength);
- memcpy(key, keyStart, length);
-
- if (fTree->fHeader->DataType() == BPLUSTREE_STRING_TYPE) //
terminate string type
- {
- if (length == maxLength)
- length--;
- ((char *)key)[length] = '\0';
- }
- *keyLength = length;
-
- off_t offset = BFS_ENDIAN_TO_HOST_INT64(node->Values()[fCurrentKey]);
-
-#ifdef BPLUSTREE_SUPPORTS_DUPLICATES
- // duplicate fragments?
- uint8 type = bplustree_node::LinkType(offset);
- if (type == BPLUSTREE_DUPLICATE_FRAGMENT || type ==
BPLUSTREE_DUPLICATE_NODE)
- {
- fDuplicateNode = offset;
-
- node =
cached.SetTo(bplustree_node::FragmentOffset(fDuplicateNode), false);
- if (node == NULL)
- return B_ERROR;
-
- fIsFragment = type == BPLUSTREE_DUPLICATE_FRAGMENT;
-
- fNumDuplicates = node->CountDuplicates(offset, fIsFragment);
- if (fNumDuplicates)
- {
- offset = node->DuplicateAt(offset, fIsFragment, 0);
- fDuplicate = 1;
- if (duplicate)
- *duplicate = 1;
- }
- else
- {
- // shouldn't happen, but we're dealing here with
potentially corrupt disks...
- fDuplicateNode = BPLUSTREE_NULL;
- offset = 0;
- }
- }
-#endif /* BPLUSTREE_SUPPORTS_DUPLICATES */
- *value = offset;
-
- return B_OK;
-}
-
-
-/** This is more or less a copy of BPlusTree::Find() - but it just
- * sets the current position in the iterator, regardless of if the
- * key could be found or not.
- */
-
-status_t
-TreeIterator::Find(const uint8 *key, uint16 keyLength)
-{
- if (fTree == NULL)
- return B_INTERRUPTED;
- if (keyLength < BPLUSTREE_MIN_KEY_LENGTH || keyLength >
BPLUSTREE_MAX_KEY_LENGTH
- || key == NULL)
- return B_BAD_VALUE;
-
- off_t nodeOffset = fTree->fHeader->RootNode();
-
- CachedNode cached(fTree);
- bplustree_node *node;
- while ((node = cached.SetTo(nodeOffset)) != NULL) {
- uint16 keyIndex = 0;
- off_t nextOffset;
- status_t status = fTree->FindKey(node, key, keyLength,
&keyIndex, &nextOffset);
-
- if (node->OverflowLink() == BPLUSTREE_NULL) {
- fCurrentNodeOffset = nodeOffset;
- fCurrentKey = keyIndex - 1;
-#ifdef BPLUSTREE_SUPPORTS_DUPLICATES
- fDuplicateNode = BPLUSTREE_NULL;
-#endif
- return status;
- } else if (nextOffset == nodeOffset)
- return B_ERROR;
-
- nodeOffset = nextOffset;
- }
- return B_ERROR;
-}
-
-
-#ifdef BPLUSTREE_SUPPORTS_DUPLICATES
-void
-TreeIterator::SkipDuplicates()
-{
- fDuplicateNode = BPLUSTREE_NULL;
-}
-#endif
-
-
-// #pragma mark -
-
-
-void
-bplustree_node::Initialize()
-{
- left_link = right_link = overflow_link =
HOST_ENDIAN_TO_BFS_INT64((uint64)BPLUSTREE_NULL);
- all_key_count = 0;
- all_key_length = 0;
-}
-
-
-uint8 *
-bplustree_node::KeyAt(int32 index, uint16 *keyLength) const
-{
- if (index < 0 || index > NumKeys())
- return NULL;
-
- uint8 *keyStart = Keys();
- uint16 *keyLengths = KeyLengths();
-
- *keyLength = BFS_ENDIAN_TO_HOST_INT16(keyLengths[index])
- - (index != 0 ? BFS_ENDIAN_TO_HOST_INT16(keyLengths[index - 1])
: 0);
- if (index > 0)
- keyStart += BFS_ENDIAN_TO_HOST_INT16(keyLengths[index - 1]);
-
- return keyStart;
-}
-
-
-#ifdef BPLUSTREE_SUPPORTS_DUPLICATES
-uint8
-bplustree_node::CountDuplicates(off_t offset, bool isFragment) const
-{
- // the duplicate fragment handling is currently hard-coded to a node
size
- // of 1024 bytes - with future versions of BFS, this may be a problem
-
- if (isFragment) {
- uint32 fragment = (NUM_FRAGMENT_VALUES + 1) * ((uint64)offset &
0x3ff);
-
- return ((off_t *)this)[fragment];
- }
- return OverflowLink();
-}
-
-
-off_t
-bplustree_node::DuplicateAt(off_t offset, bool isFragment, int8 index) const
-{
- uint32 start;
- if (isFragment)
- start = 8 * ((uint64)offset & 0x3ff);
- else
- start = 2;
-
- return ((off_t *)this)[start + 1 + index];
-}
-
-
-/** Although the name suggests it, this function doesn't return the real
- * used fragment count; at least, it can only count to two: it returns
- * 0, if there is no fragment used, 1 if there is only one fragment
- * used, and 2 if there are at least 2 fragments used.
- */
-
-int32
-bplustree_node::FragmentsUsed(uint32 nodeSize)
-{
- uint32 used = 0;
- for (uint32 i = 0; i < nodeSize / ((NUM_FRAGMENT_VALUES + 1) *
sizeof(off_t)); i++) {
- duplicate_array *array = FragmentAt(i);
- if (array->count > 0 && ++used > 1)
- return used;
- }
- return used;
-}
-#endif /* BPLUSTREE_SUPPORTS_DUPLICATES */
-
-
-// #pragma mark -
-
-
-int32
-BFS::compareKeys(type_code type, const void *key1, int keyLength1, const void
*key2, int keyLength2)
-{
- // if one of the keys is NULL, bail out gracefully
- if (key1 == NULL || key2 == NULL)
- return -1;
-
- switch (type)
- {
- case B_STRING_TYPE:
- {
- int len = min_c(keyLength1, keyLength2);
- int result = strncmp((const char *)key1, (const char
*)key2, len);
-
- if (result == 0
- && !(((const char *)key1)[len] == '\0' &&
((const char *)key2)[len] == '\0'))
- result = keyLength1 - keyLength2;
-
- return result;
- }
-
- case B_SSIZE_T_TYPE:
- case B_INT32_TYPE:
- return *(int32 *)key1 - *(int32 *)key2;
-
- case B_SIZE_T_TYPE:
- case B_UINT32_TYPE:
- if (*(uint32 *)key1 == *(uint32 *)key2)
- return 0;
- else if (*(uint32 *)key1 > *(uint32 *)key2)
- return 1;
-
- return -1;
-
- case B_OFF_T_TYPE:
- case B_INT64_TYPE:
- if (*(int64 *)key1 == *(int64 *)key2)
- return 0;
- else if (*(int64 *)key1 > *(int64 *)key2)
- return 1;
-
- return -1;
-
- case B_UINT64_TYPE:
- if (*(uint64 *)key1 == *(uint64 *)key2)
- return 0;
- else if (*(uint64 *)key1 > *(uint64 *)key2)
- return 1;
-
- return -1;
-
- case B_FLOAT_TYPE:
- {
- float result = *(float *)key1 - *(float *)key2;
- if (result == 0.0f)
- return 0;
-
- return (result < 0.0f) ? -1 : 1;
- }
-
- case B_DOUBLE_TYPE:
- {
- double result = *(double *)key1 - *(double *)key2;
- if (result == 0.0)
- return 0;
-
- return (result < 0.0) ? -1 : 1;
- }
- }
-
- // if the type is unknown, the entries don't match...
- return -1;
-}
-
diff --git a/src/system/boot/loader/file_systems/bfs/BPlusTree.h
b/src/system/boot/loader/file_systems/bfs/BPlusTree.h
deleted file mode 100644
index 28b58d5..0000000
--- a/src/system/boot/loader/file_systems/bfs/BPlusTree.h
+++ /dev/null
@@ -1,374 +0,0 @@
-/*
- * Copyright 2001-2009, Axel Dörfler, axeld@xxxxxxxxxxxxxxxx.
- * This file may be used under the terms of the MIT License.
- */
-#ifndef B_PLUS_TREE_H
-#define B_PLUS_TREE_H
-
-
-#include <stdlib.h>
-
-#include "Stream.h"
-#include "Utility.h"
-
-
-template<class T> class Stack;
-
-namespace BFS {
-
-//****************** on-disk structures ********************
-
-#define BPLUSTREE_NULL -1LL
-#define BPLUSTREE_FREE -2LL
-
-struct bplustree_header {
- uint32 magic;
- uint32 node_size;
- uint32 max_number_of_levels;
- uint32 data_type;
- off_t root_node_pointer;
- off_t free_node_pointer;
- off_t maximum_size;
-
- uint32 Magic() const { return BFS_ENDIAN_TO_HOST_INT32(magic); }
- uint32 NodeSize() const { return BFS_ENDIAN_TO_HOST_INT32(node_size); }
- uint32 DataType() const { return BFS_ENDIAN_TO_HOST_INT32(data_type); }
- off_t RootNode() const { return
BFS_ENDIAN_TO_HOST_INT64(root_node_pointer); }
- off_t MaximumSize() const { return
BFS_ENDIAN_TO_HOST_INT64(maximum_size); }
-
- inline bool IsValidLink(off_t link);
-};
-
-#define BPLUSTREE_MAGIC 0x69f6c2e8
-#define BPLUSTREE_NODE_SIZE 1024
-#define BPLUSTREE_MAX_KEY_LENGTH 256
-#define BPLUSTREE_MIN_KEY_LENGTH 1
-
-enum bplustree_types {
- BPLUSTREE_STRING_TYPE = 0,
- BPLUSTREE_INT32_TYPE = 1,
- BPLUSTREE_UINT32_TYPE = 2,
- BPLUSTREE_INT64_TYPE = 3,
- BPLUSTREE_UINT64_TYPE = 4,
- BPLUSTREE_FLOAT_TYPE = 5,
- BPLUSTREE_DOUBLE_TYPE = 6
-};
-
-struct sorted_array;
-typedef sorted_array duplicate_array;
-
-struct bplustree_node {
- off_t left_link;
- off_t right_link;
- off_t overflow_link;
- uint16 all_key_count;
- uint16 all_key_length;
-
- off_t LeftLink() const { return BFS_ENDIAN_TO_HOST_INT64(left_link); }
- off_t RightLink() const { return BFS_ENDIAN_TO_HOST_INT64(right_link); }
- off_t OverflowLink() const { return
BFS_ENDIAN_TO_HOST_INT64(overflow_link); }
- uint16 NumKeys() const { return
BFS_ENDIAN_TO_HOST_INT16(all_key_count); }
- uint16 AllKeyLength() const { return
BFS_ENDIAN_TO_HOST_INT16(all_key_length); }
-
- inline uint16 *KeyLengths() const;
- inline off_t *Values() const;
- inline uint8 *Keys() const;
- inline int32 Used() const;
- uint8 *KeyAt(int32 index,uint16 *keyLength) const;
-
- inline bool IsLeaf() const;
-
- void Initialize();
-
-#ifdef BPLUSTREE_SUPPORTS_DUPLICATES
- uint8 CountDuplicates(off_t offset, bool isFragment) const;
- off_t DuplicateAt(off_t offset, bool isFragment, int8 index) const;
- int32 FragmentsUsed(uint32 nodeSize);
- inline duplicate_array *FragmentAt(int8 index);
- inline duplicate_array *DuplicateArray();
-
- static inline uint8 LinkType(off_t link);
- static inline off_t MakeLink(uint8 type, off_t link, uint32
fragmentIndex = 0);
- static inline bool IsDuplicate(off_t link);
- static inline off_t FragmentOffset(off_t link);
- static inline uint32 FragmentIndex(off_t link);
-#endif
-} __attribute__ ((__packed__));
-
-//#define BPLUSTREE_NODE 0
-#define BPLUSTREE_DUPLICATE_NODE 2
-#define BPLUSTREE_DUPLICATE_FRAGMENT 3
-
-#define NUM_FRAGMENT_VALUES 7
-#define NUM_DUPLICATE_VALUES 125
-
-//**************************************
-
-enum bplustree_traversing {
- BPLUSTREE_FORWARD = 1,
- BPLUSTREE_BACKWARD = -1,
-
- BPLUSTREE_BEGIN = 0,
- BPLUSTREE_END = 1
-};
-
-
-//****************** in-memory structures ********************
-
-class BPlusTree;
-class TreeIterator;
-class CachedNode;
-
-// needed for searching (utilizing a stack)
-struct node_and_key {
- off_t nodeOffset;
- uint16 keyIndex;
-};
-
-
-//***** Cache handling *****
-
-class CachedNode {
- public:
- CachedNode(BPlusTree *tree)
- :
- fTree(tree),
- fNode(NULL),
- fBlock(NULL)
- {
- }
-
- CachedNode(BPlusTree *tree, off_t offset, bool check = true)
- :
- fTree(tree),
- fNode(NULL),
- fBlock(NULL)
- {
- SetTo(offset, check);
- }
-
- ~CachedNode()
- {
- Unset();
- free(fBlock);
- }
-
- bplustree_node *SetTo(off_t offset, bool check = true);
- bplustree_header *SetToHeader();
- void Unset();
-
- bplustree_node *Node() const { return fNode; }
-
- protected:
- bplustree_node *InternalSetTo(off_t offset);
-
- BPlusTree *fTree;
- bplustree_node *fNode;
- uint8 *fBlock;
- off_t fBlockNumber;
-};
-
-
-//******** B+tree class *********
-
-class BPlusTree {
- public:
- BPlusTree(Stream *stream);
- ~BPlusTree();
-
- status_t SetTo(Stream *stream);
-
- status_t InitCheck();
- status_t Validate();
-
- status_t Find(const uint8 *key, uint16 keyLength, off_t
*value);
-
- static int32 TypeCodeToKeyType(type_code code);
- static int32 ModeToKeyType(mode_t mode);
-
- private:
- BPlusTree(const BPlusTree &);
- BPlusTree &operator=(const BPlusTree &);
- // no implementation
-
- int32 CompareKeys(const void *key1, int keylength1,
const void *key2, int keylength2);
- status_t FindKey(bplustree_node *node, const uint8 *key,
uint16 keyLength,
- uint16 *index = NULL, off_t
*next = NULL);
- status_t SeekDown(Stack<node_and_key> &stack, const
uint8 *key, uint16 keyLength);
-
- private:
- friend class CachedNode;
- friend class TreeIterator;
-
- Stream *fStream;
- bplustree_header *fHeader;
- CachedNode fCachedHeader;
- int32 fNodeSize;
-#ifdef BPLUSTREE_SUPPORTS_DUPLICATES
- bool fAllowDuplicates;
-#endif
- status_t fStatus;
-};
-
-
-//***** helper classes/functions *****
-
-extern int32 compareKeys(type_code type, const void *key1, int keyLength1,
- const void *key2, int keyLength2);
-
-class TreeIterator {
- public:
- TreeIterator(BPlusTree *tree);
- ~TreeIterator();
-
- status_t Goto(int8 to);
- status_t Traverse(int8 direction, void *key, uint16
*keyLength, uint16 maxLength,
- off_t *value, uint16 *duplicate
= NULL);
- status_t Find(const uint8 *key, uint16 keyLength);
-
- status_t Rewind();
- status_t GetNextEntry(void *key, uint16 *keyLength,
uint16 maxLength,
- off_t *value, uint16 *duplicate
= NULL);
- status_t GetPreviousEntry(void *key, uint16 *keyLength,
uint16 maxLength,
- off_t *value, uint16 *duplicate
= NULL);
-#ifdef BPLUSTREE_SUPPORTS_DUPLICATES
- void SkipDuplicates();
-#endif
-
- private:
- BPlusTree *fTree;
-
- off_t fCurrentNodeOffset; // traverse position
- int32 fCurrentKey;
-#ifdef BPLUSTREE_SUPPORTS_DUPLICATES
- off_t fDuplicateNode;
- uint16 fDuplicate, fNumDuplicates;
- bool fIsFragment;
-#endif
-};
-
-
-/************************ TreeIterator inline functions
************************/
-// #pragma mark -
-
-inline status_t
-TreeIterator::Rewind()
-{
- return Goto(BPLUSTREE_BEGIN);
-}
-
-inline status_t
-TreeIterator::GetNextEntry(void *key, uint16 *keyLength, uint16 maxLength,
- off_t *value, uint16 *duplicate)
-{
- return Traverse(BPLUSTREE_FORWARD, key, keyLength, maxLength, value,
duplicate);
-}
-
-inline status_t
-TreeIterator::GetPreviousEntry(void *key, uint16 *keyLength, uint16 maxLength,
- off_t *value, uint16 *duplicate)
-{
- return Traverse(BPLUSTREE_BACKWARD, key, keyLength, maxLength, value,
duplicate);
-}
-
-/************************ bplustree_header inline functions
************************/
-// #pragma mark -
-
-
-inline bool
-bplustree_header::IsValidLink(off_t link)
-{
- return link == BPLUSTREE_NULL || (link > 0 && link <= MaximumSize() -
NodeSize());
-}
-
-
-/************************ bplustree_node inline functions
************************/
-// #pragma mark -
-
-
-inline uint16 *
-bplustree_node::KeyLengths() const
-{
- return (uint16 *)(((char *)this)
- + key_align(sizeof(bplustree_node) + AllKeyLength()));
-}
-
-inline off_t *
-bplustree_node::Values() const
-{
- return (off_t *)((char *)KeyLengths() + NumKeys() * sizeof(uint16));
-}
-
-inline uint8 *
-bplustree_node::Keys() const
-{
- return (uint8 *)this + sizeof(bplustree_node);
-}
-
-inline int32
-bplustree_node::Used() const
-{
- return key_align(sizeof(bplustree_node) + AllKeyLength())
- + NumKeys() * (sizeof(uint16) + sizeof(off_t));
-}
-
-inline bool
-bplustree_node::IsLeaf() const
-{
- return OverflowLink() == BPLUSTREE_NULL;
-}
-
-
-#ifdef BPLUSTREE_SUPPORTS_DUPLICATES
-inline duplicate_array *
-bplustree_node::FragmentAt(int8 index)
-{
- return (duplicate_array *)((off_t *)this + index * (NUM_FRAGMENT_VALUES
+ 1));
-}
-
-
-inline duplicate_array *
-bplustree_node::DuplicateArray()
-{
- return (duplicate_array *)&this->overflow_link;
-}
-
-
-inline uint8
-bplustree_node::LinkType(off_t link)
-{
- return *(uint64 *)&link >> 62;
-}
-
-
-inline off_t
-bplustree_node::MakeLink(uint8 type, off_t link, uint32 fragmentIndex)
-{
- return ((off_t)type << 62) | (link & 0x3ffffffffffffc00LL) |
(fragmentIndex & 0x3ff);
-}
-
-
-inline bool
-bplustree_node::IsDuplicate(off_t link)
-{
- return (LinkType(link) & (BPLUSTREE_DUPLICATE_NODE |
BPLUSTREE_DUPLICATE_FRAGMENT)) > 0;
-}
-
-
-inline off_t
-bplustree_node::FragmentOffset(off_t link)
-{
- return link & 0x3ffffffffffffc00LL;
-}
-
-
-inline uint32
-bplustree_node::FragmentIndex(off_t link)
-{
- return (uint32)(link & 0x3ff);
-}
-#endif /* BPLUSTREE_SUPPORTS_DUPLICATES */
-
-} // namespace BFS
-
-#endif /* B_PLUS_TREE_H */
diff --git a/src/system/boot/loader/file_systems/bfs/Jamfile
b/src/system/boot/loader/file_systems/bfs/Jamfile
index e91cf72..860fb61 100644
--- a/src/system/boot/loader/file_systems/bfs/Jamfile
+++ b/src/system/boot/loader/file_systems/bfs/Jamfile
@@ -19,3 +19,6 @@ BootStaticLibrary boot_bfs :
BPlusTree.cpp
: -fno-pic
;
+
+SEARCH on [ FGristFiles BPlusTree.cpp ]
+ = [ FDirName $(HAIKU_TOP) src add-ons kernel file_systems bfs ] ;
diff --git a/src/system/boot/loader/file_systems/bfs/Stream.h
b/src/system/boot/loader/file_systems/bfs/Stream.h
index 908d0b4..19468af 100644
--- a/src/system/boot/loader/file_systems/bfs/Stream.h
+++ b/src/system/boot/loader/file_systems/bfs/Stream.h
@@ -35,6 +35,7 @@ class Stream : public bfs_inode {
bool IsContainer() const { return Mode() & (S_IFDIR |
S_INDEX_DIR | S_ATTR_DIR); }
bool IsSymlink() const { return S_ISLNK(Mode()); }
+ bool IsIndex() const { return false; }
static Node *NodeFactory(Volume &volume, off_t id);
############################################################################
Commit: 50ef2db4a80d096978fd27c5d77306c631f8a181
URL: http://cgit.haiku-os.org/haiku/commit/?id=50ef2db
Author: Michael Lotz <mmlr@xxxxxxxx>
Date: Thu May 2 19:10:46 2013 UTC
BPlusTree: Fix GCC4 false positive of possible unintialized use.
----------------------------------------------------------------------------
diff --git a/src/add-ons/kernel/file_systems/bfs/BPlusTree.cpp
b/src/add-ons/kernel/file_systems/bfs/BPlusTree.cpp
index b5ef6c6..33efc3f 100644
--- a/src/add-ons/kernel/file_systems/bfs/BPlusTree.cpp
+++ b/src/add-ons/kernel/file_systems/bfs/BPlusTree.cpp
@@ -3089,7 +3089,7 @@ duplicate_array::Insert(off_t value)
// binary search, if not, just iterate linearly to find
// the insertion point
int32 size = Count();
- int32 i;
+ int32 i = 0;
if (size > 8 ) {
if (!_FindInternal(value, i) && ValueAt(i) <= value)
i++;
############################################################################
Revision: hrev45602
Commit: 8a43cad2ef51b227d80be6e20f37b14c2a0dbde4
URL: http://cgit.haiku-os.org/haiku/commit/?id=8a43cad
Author: Michael Lotz <mmlr@xxxxxxxx>
Date: Thu May 2 19:12:55 2013 UTC
BPlusTree: Fix fCurrentKey in backward TreeIterator traversal.
When reaching the next node the current key should be set to the next
valid index within that node (0 for forward and NumKeys() - 1 for
backward). This did not cause any harm as BFS uses forward traversal
only.
----------------------------------------------------------------------------
diff --git a/src/add-ons/kernel/file_systems/bfs/BPlusTree.cpp
b/src/add-ons/kernel/file_systems/bfs/BPlusTree.cpp
index 33efc3f..ba82408 100644
--- a/src/add-ons/kernel/file_systems/bfs/BPlusTree.cpp
+++ b/src/add-ons/kernel/file_systems/bfs/BPlusTree.cpp
@@ -2715,7 +2715,7 @@ TreeIterator::Traverse(int8 direction, void* key, uint16*
keyLength,
RETURN_ERROR(B_ERROR);
// reset current key
- fCurrentKey = forward ? 0 : node->NumKeys();
+ fCurrentKey = forward ? 0 : node->NumKeys() - 1;
} else {
// there are no nodes left, so turn back to the last key
fCurrentNodeOffset = savedNodeOffset;
Other related posts:
- » [haiku-commits] haiku: hrev45602 - in src: system/boot/loader/file_systems/bfs add-ons/kernel/file_systems/bfs - mmlr
