file_systems/bfs/BPlusTree.cpp

165 	bool Visited(off_t offset) const
167 		return fVisited.IsSet(offset / fNodeSize);
170 	void SetVisited(off_t offset)
172 		fVisited.Set(offset / fNodeSize, true);
180 	bool VisitedFragment(off_t offset) const
182 		return fVisitedFragment.IsSet(offset / fNodeSize);
185 	void SetVisitedFragment(off_t offset)
187 		fVisitedFragment.Set(offset / fNodeSize, true);
206 	void SetPreviousOffset(uint32 level, off_t offset)
208 		fPreviousOffsets[level] = offset;
289 CachedNode::SetTo(off_t offset, bool check)
292 	if (SetTo(offset, &node, check) == B_OK)
300 CachedNode::SetTo(off_t offset, const bplustree_node** _node, bool check)
310 	if (offset > fTree->fHeader.MaximumSize() - fTree->fNodeSize
311 		|| offset <= 0
312 		|| (offset % fTree->fNodeSize) != 0) {
316 	if (InternalSetTo(NULL, offset) != NULL && check) {
319 			FATAL(("invalid node [%p] read from offset %" B_PRIdOFF " (block %"
320 				B_PRIdOFF "), inode at %" B_PRIdINO "\n", fNode, offset,
333 CachedNode::SetToWritable(Transaction& transaction, off_t offset, bool check)
345 	if (offset > fTree->fHeader.MaximumSize() - fTree->fNodeSize
346 		|| offset <= 0
347 		|| (offset % fTree->fNodeSize) != 0)
350 	if (InternalSetTo(&transaction, offset) != NULL && check) {
353 			FATAL(("invalid node [%p] read from offset %" B_PRIdOFF " (block %"
354 				B_PRIdOFF "), inode at %" B_PRIdINO "\n", fNode, offset,
423 CachedNode::InternalSetTo(Transaction* transaction, off_t offset)
426 	fOffset = offset;
430 	if (offset < fTree->fStream->Size()
431 		&& fTree->fStream->FindBlockRun(offset, run, fileOffset) == B_OK) {
439 		int32 blockOffset = (offset - fileOffset) / volume->BlockSize();
469 			// (confusing offset calculation)
470 			fNode = (bplustree_node*)(block + offset
481 CachedNode::Free(Transaction& transaction, off_t offset)
483 	if (fTree == NULL || fTree->fStream == NULL || offset == BPLUSTREE_NULL)
502 	if (offset == lastOffset) {
516 	header->free_node_pointer = HOST_ENDIAN_TO_BFS_INT64(offset);
561 	off_t offset = header->MaximumSize();
568 	if (SetToWritable(transaction, offset, false) == NULL)
573 	*_offset = offset;
869 	for (off_t offset = 2 * NodeSize(); offset < fStream->Size();
870 			offset += NodeSize()) {
871 		bplustree_node* node = cached.SetToWritable(transaction, offset, false);
873 			dprintf("--> could not open %" B_PRIdOFF "\n", offset);
876 		if (offset < fStream->Size() - (off_t)NodeSize())
877 			node->left_link = HOST_ENDIAN_TO_BFS_INT64(offset + NodeSize());
885 		if (offset % (1024 * 1024) == 0) {
978 BPlusTree::_UpdateIterators(off_t offset, off_t nextOffset, uint16 keyIndex,
989 		iterator.Next()->Update(offset, nextOffset, keyIndex, splitAt, change);
1140 		// put the node offset & the correct keyIndex on the stack
1205 	off_t offset;
1238 					offset = bplustree_node::FragmentOffset(oldValue);
1256 						&newDuplicate, &offset);
1277 						BPLUSTREE_DUPLICATE_NODE, offset));
1320 				&offset);
1325 			writableDuplicate->right_link = HOST_ENDIAN_TO_BFS_INT64(offset);
1341 			&offset, &fragment, &fragmentIndex) != B_OK) {
1343 		status = cachedDuplicate.Allocate(transaction, &fragment, &offset);
1358 		BPLUSTREE_DUPLICATE_FRAGMENT, offset, fragmentIndex));
1999 			off_t offset;
2001 					&offset, &fragment, &fragmentIndex) == B_OK) {
2008 				duplicateOffset = offset;
2265 /*!	Searches the key in the tree, and stores the offset found in _value,
2331 BPlusTree::_ValidateChildren(TreeCheck& check, uint32 level, off_t offset,
2337 			"failed!\n", fStream->ID(), offset);
2343 			"!\n", fStream->ID(), offset);
2350 	if (check.Visited(offset)) {
2352 			fStream->ID(), offset);
2357 	check.SetVisited(offset);
2373 					fStream->ID(), offset, i);
2408 						duplicateOffset, offset);
2498 				fStream->ID(), offset, childOffset, i);
2522 	off_t offset, off_t lastOffset, off_t nextOffset,
2526 	status_t status = cached.SetTo(offset, &node, true);
2532 			"read: %s\n", fStream->ID(), offset, strerror(status));
2540 			"!\n", fStream->ID(), offset, node->LeftLink(), lastOffset);
2547 			"!\n", fStream->ID(), offset, node->RightLink(), nextOffset);
2551 	return _ValidateChildren(check, level + 1, offset, key, keyLength, node);
2604 		// get the next node offset depending on the direction (and if there
2769 	off_t offset = BFS_ENDIAN_TO_HOST_INT64(node->Values()[fCurrentKey]);
2772 	uint8 type = bplustree_node::LinkType(offset);
2775 		fDuplicateNode = offset;
2784 		fNumDuplicates = node->CountDuplicates(offset, fIsFragment);
2786 			offset = node->DuplicateAt(offset, fIsFragment, 0);
2794 			offset = 0;
2797 	*value = offset;
2855 TreeIterator::Update(off_t offset, off_t nextOffset, uint16 keyIndex,
2858 	if (offset != fCurrentNodeOffset)
2949 bplustree_node::CountDuplicates(off_t offset, bool isFragment) const
2955 		uint32 fragment = (NUM_FRAGMENT_VALUES + 1) * ((uint64)offset & 0x3ff);
2964 bplustree_node::DuplicateAt(off_t offset, bool isFragment, int8 index) const
2968 		start = 8 * ((uint64)offset & 0x3ff);