[haiku-commits] r35473 - haiku/trunk/src/add-ons/kernel/file_systems/bfs
- From: axeld@xxxxxxxxxxxxxxxx
- To: haiku-commits@xxxxxxxxxxxxx
- Date: Mon, 15 Feb 2010 17:39:54 +0100 (CET)
Author: axeld
Date: 2010-02-15 17:39:54 +0100 (Mon, 15 Feb 2010)
New Revision: 35473
Changeset: http://dev.haiku-os.org/changeset/35473/haiku
Modified:
haiku/trunk/src/add-ons/kernel/file_systems/bfs/BPlusTree.cpp
haiku/trunk/src/add-ons/kernel/file_systems/bfs/BPlusTree.h
Log:
* BPlusTree no longer caches the header in its own block, instead, it aggregates
a copy of its structure. CachedNode is only used to write to the header, now.
This should cause the block_cache to no longer have any referenced blocks
outside of any I/O.
* Coding style cleanup.
Modified: haiku/trunk/src/add-ons/kernel/file_systems/bfs/BPlusTree.cpp
===================================================================
--- haiku/trunk/src/add-ons/kernel/file_systems/bfs/BPlusTree.cpp
2010-02-15 14:50:53 UTC (rev 35472)
+++ haiku/trunk/src/add-ons/kernel/file_systems/bfs/BPlusTree.cpp
2010-02-15 16:39:54 UTC (rev 35473)
@@ -1,11 +1,12 @@
/*
- * Copyright 2001-2009, Axel Dörfler, axeld@xxxxxxxxxxxxxxxxx
+ * Copyright 2001-2010, Axel Dörfler, axeld@xxxxxxxxxxxxxxxxx
* 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.
*/
+
//! B+Tree implementation
@@ -82,6 +83,12 @@
return;
if (fNode != NULL) {
+ if (fWritable && fOffset == 0) {
+ // The B+tree header has been updated - we need to
update the
+ // BPlusTrees copy of it, as well.
+ memcpy(&fTree->fHeader, fNode,
sizeof(bplustree_header));
+ }
+
block_cache_put(fTree->fStream->GetVolume()->BlockCache(),
fBlockNumber);
fNode = NULL;
@@ -102,14 +109,14 @@
// 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
+ if (offset > fTree->fHeader.MaximumSize() - fTree->fNodeSize
|| offset <= 0
|| (offset % fTree->fNodeSize) != 0)
return NULL;
if (InternalSetTo(NULL, offset) != NULL && check) {
// sanity checks (links, all_key_count)
- if (!fTree->fHeader->CheckNode(fNode)) {
+ if (!fTree->fHeader.CheckNode(fNode)) {
FATAL(("invalid node [%p] read from offset %" B_PRIdOFF
" (block %"
B_PRIdOFF "), inode at %" B_PRIdINO "\n",
fNode, offset,
fBlockNumber, fTree->fStream->ID()));
@@ -133,14 +140,14 @@
// 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
+ if (offset > fTree->fHeader.MaximumSize() - fTree->fNodeSize
|| offset <= 0
|| (offset % fTree->fNodeSize) != 0)
return NULL;
if (InternalSetTo(&transaction, offset) != NULL && check) {
// sanity checks (links, all_key_count)
- if (!fTree->fHeader->CheckNode(fNode)) {
+ if (!fTree->fHeader.CheckNode(fNode)) {
FATAL(("invalid node [%p] read from offset %" B_PRIdOFF
" (block %"
B_PRIdOFF "), inode at %" B_PRIdINO "\n",
fNode, offset,
fBlockNumber, fTree->fStream->ID()));
@@ -165,13 +172,6 @@
}
-bplustree_header*
-CachedNode::MakeWritableHeader(Transaction& transaction)
-{
- return (bplustree_header*)MakeWritable(transaction);
-}
-
-
const bplustree_header*
CachedNode::SetToHeader()
{
@@ -250,8 +250,8 @@
// function is called, perhaps it should be done when the directory
// inode is closed or based on some calculation or whatever...
- bplustree_header* header
- = fTree->fCachedHeader.MakeWritableHeader(transaction);
+ CachedNode cached(fTree);
+ bplustree_header* header = cached.SetToWritableHeader(transaction);
if (header == NULL)
return B_IO_ERROR;
@@ -284,7 +284,7 @@
CachedNode::Allocate(Transaction& transaction, bplustree_node** _node,
off_t* _offset)
{
- if (fTree == NULL || fTree->fHeader == NULL || fTree->fStream == NULL)
+ if (fTree == NULL || fTree->fStream == NULL)
RETURN_ERROR(B_BAD_VALUE);
Unset();
@@ -293,8 +293,9 @@
status_t status;
// if there are any free nodes, recycle them
- if (SetToWritable(transaction, fTree->fHeader->FreeNode(), false) !=
NULL) {
- header = fTree->fCachedHeader.MakeWritableHeader(transaction);
+ if (SetToWritable(transaction, fTree->fHeader.FreeNode(), false) !=
NULL) {
+ CachedNode cached(fTree);
+ header = cached.SetToWritableHeader(transaction);
if (header == NULL)
return B_IO_ERROR;
@@ -312,7 +313,8 @@
if ((status = stream->Append(transaction, fTree->fNodeSize)) < B_OK)
return status;
- header = fTree->fCachedHeader.MakeWritableHeader(transaction);
+ CachedNode cached(fTree);
+ header = cached.SetToWritableHeader(transaction);
if (header == NULL)
return B_IO_ERROR;
@@ -342,9 +344,7 @@
BPlusTree::BPlusTree(Transaction& transaction, Inode* stream, int32 nodeSize)
:
- fStream(NULL),
- fHeader(NULL),
- fCachedHeader(this)
+ fStream(NULL)
{
mutex_init(&fIteratorLock, "bfs b+tree iterator");
SetTo(transaction, stream);
@@ -353,9 +353,7 @@
BPlusTree::BPlusTree(Inode* stream)
:
- fStream(NULL),
- fHeader(NULL),
- fCachedHeader(this)
+ fStream(NULL)
{
mutex_init(&fIteratorLock, "bfs b+tree iterator");
SetTo(stream);
@@ -365,8 +363,6 @@
BPlusTree::BPlusTree()
:
fStream(NULL),
- fHeader(NULL),
- fCachedHeader(this),
fNodeSize(BPLUSTREE_NODE_SIZE),
fAllowDuplicates(true),
fStatus(B_NO_INIT)
@@ -399,19 +395,19 @@
fStream = stream;
- bplustree_header* header =
fCachedHeader.SetToWritableHeader(transaction);
+ CachedNode cached(this);
+ bplustree_header* header = cached.SetToWritableHeader(transaction);
if (header == NULL) {
// allocate space for new header + node!
fStatus = stream->SetFileSize(transaction, nodeSize * 2);
if (fStatus < B_OK)
RETURN_ERROR(fStatus);
- header = fCachedHeader.SetToWritableHeader(transaction);
+ header = cached.SetToWritableHeader(transaction);
if (header == NULL)
RETURN_ERROR(fStatus = B_ERROR);
}
- fHeader = header;
fAllowDuplicates = stream->IsIndex()
|| (stream->Mode() & S_ALLOW_DUPS) != 0;
@@ -427,9 +423,10 @@
= HOST_ENDIAN_TO_BFS_INT64((uint64)BPLUSTREE_NULL);
header->maximum_size = HOST_ENDIAN_TO_BFS_INT64(nodeSize * 2);
+ memcpy(&fHeader, header, sizeof(bplustree_header));
+
// initialize b+tree root node
- CachedNode cached(this);
- cached.SetToWritable(transaction, header->RootNode(), false);
+ cached.SetToWritable(transaction, fHeader.RootNode(), false);
if (cached.Node() == NULL)
RETURN_ERROR(B_IO_ERROR);
@@ -445,35 +442,37 @@
if (stream == NULL)
RETURN_ERROR(fStatus = B_BAD_VALUE);
+ fStream = stream;
+
// get on-disk B+Tree header
- fCachedHeader.Unset();
- fStream = stream;
+ CachedNode cached(this);
+ const bplustree_header* header = cached.SetToHeader();
+ if (header != NULL)
+ memcpy(&fHeader, header, sizeof(bplustree_header));
+ else
+ RETURN_ERROR(fStatus = B_IO_ERROR);
- fHeader = fCachedHeader.SetToHeader();
- if (fHeader == NULL)
- RETURN_ERROR(fStatus = B_NO_INIT);
-
// is header valid?
- if (fHeader->MaximumSize() != stream->Size()) {
+ if (fHeader.MaximumSize() != stream->Size()) {
dprintf("B+tree header size %" B_PRIdOFF " doesn't fit file
size %"
- B_PRIdOFF "!\n", fHeader->MaximumSize(),
stream->Size());
+ B_PRIdOFF "!\n", fHeader.MaximumSize(), stream->Size());
// we can't change the header since we don't have a transaction
- //fHeader->maximum_size =
HOST_ENDIAN_TO_BFS_INT64(stream->Size());
+ //fHeader.maximum_size =
HOST_ENDIAN_TO_BFS_INT64(stream->Size());
}
- if (fHeader->Magic() != BPLUSTREE_MAGIC
- || (fHeader->RootNode() % fHeader->NodeSize()) != 0
- || !fHeader->IsValidLink(fHeader->RootNode())
- || !fHeader->IsValidLink(fHeader->FreeNode())) {
+ if (fHeader.Magic() != BPLUSTREE_MAGIC
+ || (fHeader.RootNode() % fHeader.NodeSize()) != 0
+ || !fHeader.IsValidLink(fHeader.RootNode())
+ || !fHeader.IsValidLink(fHeader.FreeNode())) {
#ifdef DEBUG
- dump_bplustree_header(fHeader);
- dump_block((const char*)fHeader, 128);
+ dump_bplustree_header(&fHeader);
+ dump_block((const char*)&fHeader, 128);
#endif
RETURN_ERROR(fStatus = B_BAD_DATA);
}
- fNodeSize = fHeader->NodeSize();
+ fNodeSize = fHeader.NodeSize();
// validity check
static const uint32 kToMode[] = {S_STR_INDEX, S_INT_INDEX, S_UINT_INDEX,
@@ -483,11 +482,11 @@
| S_UINT_INDEX | S_LONG_LONG_INDEX | S_ULONG_LONG_INDEX
| S_FLOAT_INDEX | S_DOUBLE_INDEX);
- if (fHeader->DataType() > BPLUSTREE_DOUBLE_TYPE
+ if (fHeader.DataType() > BPLUSTREE_DOUBLE_TYPE
|| ((stream->Mode() & S_INDEX_DIR) != 0
- && kToMode[fHeader->DataType()] != mode)
+ && kToMode[fHeader.DataType()] != mode)
|| !stream->IsContainer()) {
- D( dump_bplustree_header(fHeader);
+ D( dump_bplustree_header(&fHeader);
dump_inode(&stream->Node());
);
RETURN_ERROR(fStatus = B_BAD_TYPE);
@@ -498,7 +497,7 @@
fAllowDuplicates = stream->IsIndex()
|| (stream->Mode() & S_ALLOW_DUPS) != 0;
- CachedNode cached(this, fHeader->RootNode());
+ cached.SetTo(fHeader.RootNode());
RETURN_ERROR(fStatus = cached.Node() ? B_OK : B_BAD_DATA);
}
@@ -601,7 +600,7 @@
int keyLength2)
{
type_code type = 0;
- switch (fHeader->data_type) {
+ switch (fHeader.DataType()) {
case BPLUSTREE_STRING_TYPE:
type = B_STRING_TYPE;
break;
@@ -697,7 +696,7 @@
{
// set the root node to begin with
node_and_key nodeAndKey;
- nodeAndKey.nodeOffset = fHeader->RootNode();
+ nodeAndKey.nodeOffset = fHeader.RootNode();
CachedNode cached(this);
const bplustree_node* node;
@@ -718,7 +717,7 @@
if (status == B_ENTRY_NOT_FOUND && nextOffset ==
nodeAndKey.nodeOffset)
RETURN_ERROR(B_ERROR);
- if ((uint32)stack.CountItems() > fHeader->MaxNumberOfLevels()) {
+ if ((uint32)stack.CountItems() > fHeader.MaxNumberOfLevels()) {
dprintf("BPlusTree::_SeekDown() node walked too
deep.\n");
break;
}
@@ -1331,7 +1330,7 @@
// do we need to allocate a new root node? if so, then
do
// it now
off_t newRoot = BPLUSTREE_NULL;
- if (nodeAndKey.nodeOffset == fHeader->RootNode()) {
+ if (nodeAndKey.nodeOffset == fHeader.RootNode()) {
bplustree_node* root;
status_t status =
cachedNewRoot.Allocate(transaction, &root,
&newRoot);
@@ -1388,8 +1387,9 @@
root->overflow_link = HOST_ENDIAN_TO_BFS_INT64(
nodeAndKey.nodeOffset);
+ CachedNode cached(this);
bplustree_header* header
- =
fCachedHeader.MakeWritableHeader(transaction);
+ =
cached.SetToWritableHeader(transaction);
if (header == NULL)
return B_IO_ERROR;
@@ -1734,7 +1734,7 @@
// if it's an empty root node, we have to convert it
// to a leaf node by dropping the overflow link, or,
// if it's already a leaf node, just empty it
- if (nodeAndKey.nodeOffset == fHeader->RootNode()
+ if (nodeAndKey.nodeOffset == fHeader.RootNode()
&& (node->NumKeys() == 0
|| (node->NumKeys() == 1 && node->IsLeaf()))) {
writableNode->overflow_link
@@ -1744,9 +1744,10 @@
// if we've made a leaf node out of the root node, we
need
// to reset the maximum number of levels in the header
- if (fHeader->MaxNumberOfLevels() != 1) {
+ if (fHeader.MaxNumberOfLevels() != 1) {
+ CachedNode cached(this);
bplustree_header* header
- =
fCachedHeader.MakeWritableHeader(transaction);
+ =
cached.SetToWritableHeader(transaction);
if (header == NULL)
return B_IO_ERROR;
@@ -1807,7 +1808,7 @@
ASSERT_WRITE_LOCKED_INODE(fStream);
- off_t nodeOffset = fHeader->RootNode();
+ off_t nodeOffset = fHeader.RootNode();
CachedNode cached(this);
const bplustree_node* node;
@@ -1861,7 +1862,7 @@
ASSERT_READ_LOCKED_INODE(fStream);
- off_t nodeOffset = fHeader->RootNode();
+ off_t nodeOffset = fHeader.RootNode();
CachedNode cached(this);
const bplustree_node* node;
@@ -1883,7 +1884,7 @@
*_value =
BFS_ENDIAN_TO_HOST_INT64(node->Values()[keyIndex]);
#ifdef DEBUG
- if (levels != (int32)fHeader->MaxNumberOfLevels())
+ if (levels != (int32)fHeader.MaxNumberOfLevels())
DEBUGGER(("levels don't match"));
#endif
return status;
@@ -1919,13 +1920,13 @@
status_t
TreeIterator::Goto(int8 to)
{
- if (fTree == NULL || fTree->fHeader == NULL)
+ if (fTree == NULL || fTree->fStream == NULL)
RETURN_ERROR(B_BAD_VALUE);
// lock access to stream
InodeReadLocker locker(fTree->fStream);
- off_t nodeOffset = fTree->fHeader->RootNode();
+ off_t nodeOffset = fTree->fHeader.RootNode();
CachedNode cached(fTree);
const bplustree_node* node;
@@ -2079,7 +2080,7 @@
length = min_c(length, maxLength);
memcpy(key, keyStart, length);
- if (fTree->fHeader->data_type == BPLUSTREE_STRING_TYPE) {
+ if (fTree->fHeader.DataType() == BPLUSTREE_STRING_TYPE) {
// terminate string type
if (length == maxLength)
length--;
@@ -2138,7 +2139,7 @@
// lock access to stream
InodeReadLocker locker(fTree->fStream);
- off_t nodeOffset = fTree->fHeader->RootNode();
+ off_t nodeOffset = fTree->fHeader.RootNode();
CachedNode cached(fTree);
const bplustree_node* node;
Modified: haiku/trunk/src/add-ons/kernel/file_systems/bfs/BPlusTree.h
===================================================================
--- haiku/trunk/src/add-ons/kernel/file_systems/bfs/BPlusTree.h 2010-02-15
14:50:53 UTC (rev 35472)
+++ haiku/trunk/src/add-ons/kernel/file_systems/bfs/BPlusTree.h 2010-02-15
16:39:54 UTC (rev 35473)
@@ -1,5 +1,5 @@
/*
- * Copyright 2001-2009, Axel Dörfler, axeld@xxxxxxxxxxxxxxxxx
+ * Copyright 2001-2010, Axel Dörfler, axeld@xxxxxxxxxxxxxxxxx
* This file may be used under the terms of the MIT License.
*/
#ifndef B_PLUS_TREE_H
@@ -60,45 +60,55 @@
typedef sorted_array duplicate_array;
struct bplustree_node {
- int64 left_link;
- int64 right_link;
- int64 overflow_link;
- uint16 all_key_count;
- uint16 all_key_length;
+ int64 left_link;
+ int64 right_link;
+ int64 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); }
+ 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 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;
+ inline bool IsLeaf() const;
- void Initialize();
- uint8 CountDuplicates(off_t offset, bool isFragment) const;
- off_t DuplicateAt(off_t offset, bool isFragment, int8 index) const;
- uint32 FragmentsUsed(uint32 nodeSize) const;
- inline duplicate_array* FragmentAt(int8 index) const;
- inline duplicate_array* DuplicateArray() const;
+ void Initialize();
+ uint8 CountDuplicates(off_t
offset,
+ bool
isFragment) const;
+ off_t DuplicateAt(off_t
offset, bool isFragment,
+ int8
index) const;
+ uint32 FragmentsUsed(uint32
nodeSize) const;
+ inline duplicate_array* FragmentAt(int8 index) const;
+ inline duplicate_array* DuplicateArray() const;
- 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);
- static inline uint32 MaxFragments(uint32 nodeSize);
+ 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);
+ static inline uint32 MaxFragments(uint32 nodeSize);
#ifdef DEBUG
- status_t CheckIntegrity(uint32 nodeSize) const;
+ status_t CheckIntegrity(uint32
nodeSize) const;
#endif
} _PACKED;
@@ -157,128 +167,137 @@
Unset();
}
- const bplustree_node* SetTo(off_t offset, bool check = true);
- 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);
- bplustree_header* MakeWritableHeader(Transaction& transaction);
+ const bplustree_node* SetTo(off_t offset, bool check =
true);
+ 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();
+ 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);
+ status_t Free(Transaction&
transaction, off_t offset);
+ status_t Allocate(Transaction&
transaction,
+
bplustree_node** _node, off_t* _offset);
- bool IsWritable() const { return fWritable; }
- bplustree_node* Node() const { return fNode; }
+ bool IsWritable() const {
return fWritable; }
+ bplustree_node* Node() const { return fNode; }
protected:
- bplustree_node* InternalSetTo(Transaction* transaction, off_t offset);
+ bplustree_node* InternalSetTo(Transaction*
transaction,
+ off_t
offset);
- BPlusTree* fTree;
- bplustree_node* fNode;
- off_t fOffset;
- off_t fBlockNumber;
- bool fWritable;
+ BPlusTree* fTree;
+ bplustree_node* fNode;
+ off_t fOffset;
+ off_t fBlockNumber;
+ bool fWritable;
};
class BPlusTree {
public:
- BPlusTree(Transaction&
transaction, Inode* stream,
- int32 nodeSize =
BPLUSTREE_NODE_SIZE);
- BPlusTree(Inode* stream);
- BPlusTree();
- ~BPlusTree();
+
BPlusTree(Transaction& transaction,
+ Inode*
stream,
+ int32
nodeSize = BPLUSTREE_NODE_SIZE);
+
BPlusTree(Inode* stream);
+ BPlusTree();
+ ~BPlusTree();
- status_t SetTo(Transaction& transaction, Inode*
stream,
- int32 nodeSize =
BPLUSTREE_NODE_SIZE);
- status_t SetTo(Inode* stream);
- status_t SetStream(Inode* stream);
+ status_t SetTo(Transaction&
transaction, Inode* stream,
+ int32
nodeSize = BPLUSTREE_NODE_SIZE);
+ status_t SetTo(Inode* stream);
+ status_t SetStream(Inode*
stream);
- status_t InitCheck();
- status_t Validate();
+ status_t InitCheck();
+ status_t Validate();
- status_t Remove(Transaction& transaction, const
uint8* key,
- uint16 keyLength, off_t
value);
- status_t Insert(Transaction& transaction, const
uint8* key,
- uint16 keyLength, off_t
value);
+ status_t Remove(Transaction&
transaction,
+ const
uint8* key, uint16 keyLength,
+ off_t
value);
+ status_t Insert(Transaction&
transaction,
+ const
uint8* key, uint16 keyLength,
+ off_t
value);
- status_t Remove(Transaction& transaction, const
char* key,
- off_t value);
- status_t Insert(Transaction& transaction, const
char* key,
- off_t value);
- status_t Insert(Transaction& transaction, int32
key,
- off_t value);
- status_t Insert(Transaction& transaction, uint32
key,
- off_t value);
- status_t Insert(Transaction& transaction, int64
key,
- off_t value);
- status_t Insert(Transaction& transaction, uint64
key,
- off_t value);
- status_t Insert(Transaction& transaction, float
key,
- off_t value);
- status_t Insert(Transaction& transaction, double
key,
- off_t value);
+ status_t Remove(Transaction&
transaction, const char* key,
+ off_t
value);
+ status_t Insert(Transaction&
transaction, const char* key,
+ off_t
value);
+ status_t Insert(Transaction&
transaction, int32 key,
+ off_t
value);
+ status_t Insert(Transaction&
transaction, uint32 key,
+ off_t
value);
+ status_t Insert(Transaction&
transaction, int64 key,
+ off_t
value);
+ status_t Insert(Transaction&
transaction, uint64 key,
+ off_t
value);
+ status_t Insert(Transaction&
transaction, float key,
+ off_t
value);
+ status_t Insert(Transaction&
transaction, double key,
+ off_t
value);
- status_t Replace(Transaction& transaction, const
uint8* key,
- uint16 keyLength, off_t
value);
- status_t Find(const uint8* key, uint16
keyLength, off_t* value);
+ status_t Replace(Transaction&
transaction,
+ const
uint8* key, uint16 keyLength,
+ off_t
value);
+ status_t Find(const uint8* key,
uint16 keyLength,
+ off_t*
value);
- static int32 TypeCodeToKeyType(type_code code);
- static int32 ModeToKeyType(mode_t mode);
+ static int32 TypeCodeToKeyType(type_code
code);
+ static int32 ModeToKeyType(mode_t mode);
private:
- BPlusTree(const BPlusTree&
other);
- BPlusTree& operator=(const
BPlusTree& other);
- // no implementation
+ BPlusTree(const
BPlusTree& other);
+ BPlusTree&
operator=(const BPlusTree& other);
+ // no
implementation
- int32 _CompareKeys(const void* key1, int
keylength1,
- const void* key2, int
keylength2);
- status_t _FindKey(const 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);
+ int32 _CompareKeys(const
void* key1, int keylength1,
+ const
void* key2, int keylength2);
+ status_t _FindKey(const
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);
- status_t _FindFreeDuplicateFragment(Transaction&
transaction,
- const bplustree_node*
node, CachedNode& cached,
- off_t* _offset,
bplustree_node** _fragment,
- uint32* _index);
- status_t _InsertDuplicate(Transaction&
transaction,
- CachedNode& cached,
const bplustree_node* node,
- uint16 index, off_t
value);
- void _InsertKey(bplustree_node* node, uint16
index,
- uint8* key, uint16
keyLength, off_t value);
- status_t _SplitNode(bplustree_node* node, off_t
nodeOffset,
- bplustree_node* other,
off_t otherOffset,
- uint16* _keyIndex,
uint8* key, uint16* _keyLength,
- off_t* _value);
+ status_t
_FindFreeDuplicateFragment(
+
Transaction& transaction,
+ const
bplustree_node* node,
+
CachedNode& cached, off_t* _offset,
+
bplustree_node** _fragment, uint32* _index);
+ status_t
_InsertDuplicate(Transaction& transaction,
+
CachedNode& cached,
+ const
bplustree_node* node, uint16 index,
+ off_t
value);
+ void
_InsertKey(bplustree_node* node, uint16 index,
+ uint8*
key, uint16 keyLength, off_t value);
+ status_t
_SplitNode(bplustree_node* node,
+ off_t
nodeOffset, bplustree_node* other,
+ off_t
otherOffset, uint16* _keyIndex,
+ uint8*
key, uint16* _keyLength,
+ off_t*
_value);
- status_t _RemoveDuplicate(Transaction&
transaction,
- const bplustree_node*
node, CachedNode& cached,
- uint16 keyIndex, off_t
value);
- void _RemoveKey(bplustree_node* node, uint16
index);
+ status_t
_RemoveDuplicate(Transaction& transaction,
+ const
bplustree_node* node,
+
CachedNode& cached, uint16 keyIndex,
+ off_t
value);
+ void
_RemoveKey(bplustree_node* node, uint16 index);
- void _UpdateIterators(off_t offset, off_t
nextOffset,
- uint16 keyIndex, uint16
splitAt, int8 change);
- void _AddIterator(TreeIterator* iterator);
- void _RemoveIterator(TreeIterator* iterator);
+ void _UpdateIterators(off_t
offset, off_t nextOffset,
+ uint16
keyIndex, uint16 splitAt,
+ int8
change);
+ void
_AddIterator(TreeIterator* iterator);
+ void
_RemoveIterator(TreeIterator* iterator);
private:
- friend class TreeIterator;
- friend class CachedNode;
+ friend class TreeIterator;
+ friend class CachedNode;
- Inode* fStream;
- const bplustree_header* fHeader;
- CachedNode fCachedHeader;
- int32 fNodeSize;
- bool fAllowDuplicates;
- status_t fStatus;
- mutex fIteratorLock;
+ Inode* fStream;
+ bplustree_header fHeader;
+ int32 fNodeSize;
+ bool fAllowDuplicates;
+ status_t fStatus;
+ mutex fIteratorLock;
SinglyLinkedList<TreeIterator> fIterators;
};
@@ -290,46 +309,48 @@
class TreeIterator : public SinglyLinkedListLinkImpl<TreeIterator> {
public:
- TreeIterator(BPlusTree* tree);
- ~TreeIterator();
+
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 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);
- void SkipDuplicates();
+ 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);
+ void SkipDuplicates();
- BPlusTree* Tree() const { return fTree; }
+ BPlusTree* Tree() const { return
fTree; }
#ifdef DEBUG
- void Dump();
+ void Dump();
#endif
private:
- friend class BPlusTree;
+ friend class BPlusTree;
// called by BPlusTree
- void Update(off_t offset, off_t nextOffset,
uint16 keyIndex,
- uint16 splitAt, int8
change);
- void Stop();
+ void Update(off_t offset,
off_t nextOffset,
+ uint16
keyIndex, uint16 splitAt,
+ int8
change);
+ void Stop();
private:
- BPlusTree* fTree;
- off_t fCurrentNodeOffset;
- // traverse position
- int32 fCurrentKey;
- off_t fDuplicateNode;
- uint16 fDuplicate, fNumDuplicates;
- bool fIsFragment;
+ BPlusTree* fTree;
+ off_t fCurrentNodeOffset;
+ //
traverse position
+ int32 fCurrentKey;
+ off_t fDuplicateNode;
+ uint16 fDuplicate;
+ uint16 fNumDuplicates;
+ bool fIsFragment;
};
@@ -340,7 +361,7 @@
inline status_t
BPlusTree::Remove(Transaction& transaction, const char* key, off_t value)
{
- if (fHeader->data_type != BPLUSTREE_STRING_TYPE)
+ if (fHeader.DataType() != BPLUSTREE_STRING_TYPE)
return B_BAD_TYPE;
return Remove(transaction, (uint8*)key, strlen(key), value);
}
@@ -348,7 +369,7 @@
inline status_t
BPlusTree::Insert(Transaction& transaction, const char* key, off_t value)
{
- if (fHeader->data_type != BPLUSTREE_STRING_TYPE)
+ if (fHeader.DataType() != BPLUSTREE_STRING_TYPE)
return B_BAD_TYPE;
return Insert(transaction, (uint8*)key, strlen(key), value);
}
@@ -356,7 +377,7 @@
inline status_t
BPlusTree::Insert(Transaction& transaction, int32 key, off_t value)
{
- if (fHeader->data_type != BPLUSTREE_INT32_TYPE)
+ if (fHeader.DataType() != BPLUSTREE_INT32_TYPE)
return B_BAD_TYPE;
return Insert(transaction, (uint8*)&key, sizeof(key), value);
}
@@ -364,7 +385,7 @@
inline status_t
BPlusTree::Insert(Transaction& transaction, uint32 key, off_t value)
{
- if (fHeader->data_type != BPLUSTREE_UINT32_TYPE)
+ if (fHeader.DataType() != BPLUSTREE_UINT32_TYPE)
return B_BAD_TYPE;
return Insert(transaction, (uint8*)&key, sizeof(key), value);
}
@@ -372,7 +393,7 @@
inline status_t
BPlusTree::Insert(Transaction& transaction, int64 key, off_t value)
{
- if (fHeader->data_type != BPLUSTREE_INT64_TYPE)
+ if (fHeader.DataType() != BPLUSTREE_INT64_TYPE)
return B_BAD_TYPE;
return Insert(transaction, (uint8*)&key, sizeof(key), value);
}
@@ -380,7 +401,7 @@
inline status_t
BPlusTree::Insert(Transaction& transaction, uint64 key, off_t value)
{
- if (fHeader->data_type != BPLUSTREE_UINT64_TYPE)
+ if (fHeader.DataType() != BPLUSTREE_UINT64_TYPE)
return B_BAD_TYPE;
return Insert(transaction, (uint8*)&key, sizeof(key), value);
}
@@ -388,7 +409,7 @@
inline status_t
BPlusTree::Insert(Transaction& transaction, float key, off_t value)
{
- if (fHeader->data_type != BPLUSTREE_FLOAT_TYPE)
+ if (fHeader.DataType() != BPLUSTREE_FLOAT_TYPE)
return B_BAD_TYPE;
return Insert(transaction, (uint8*)&key, sizeof(key), value);
}
@@ -396,7 +417,7 @@
inline status_t
BPlusTree::Insert(Transaction& transaction, double key, off_t value)
{
- if (fHeader->data_type != BPLUSTREE_DOUBLE_TYPE)
+ if (fHeader.DataType() != BPLUSTREE_DOUBLE_TYPE)
return B_BAD_TYPE;
return Insert(transaction, (uint8*)&key, sizeof(key), value);
}
Other related posts:
