1/*
2 * Copyright 2017, Ch��� V�� Gia Hy, cvghy116@gmail.com.
3 * Copyright 2011, J��r��me Duval, korli@users.berlios.de.
4 * Copyright 2001-2010, Axel D��rfler, axeld@pinc-software.de.
5 * This file may be used under the terms of the MIT License.
6 */
7
8
9//! BTree implementation
10
11
12#include "BTree.h"
13#include "Journal.h"
14
15
16//#define TRACE_BTRFS
17#ifdef TRACE_BTRFS
18#	define TRACE(x...) dprintf("\33[34mbtrfs:\33[0m " x)
19#else
20#	define TRACE(x...) ;
21#endif
22#	define ERROR(x...) dprintf("\33[34mbtrfs:\33[0m " x)
23
24
25BTree::Node::Node(Volume* volume)
26	:
27	fNode(NULL),
28	fVolume(volume),
29	fBlockNumber(0),
30	fWritable(false)
31{
32}
33
34
35BTree::Node::Node(Volume* volume, off_t block)
36	:
37	fNode(NULL),
38	fVolume(volume),
39	fBlockNumber(0),
40	fWritable(false)
41{
42	SetTo(block);
43}
44
45
46BTree::Node::~Node()
47{
48	Unset();
49}
50
51
52void
53BTree::Node::Unset()
54{
55	if (fNode != NULL) {
56		block_cache_put(fVolume->BlockCache(), fBlockNumber);
57		fNode = NULL;
58	}
59}
60
61
62void
63BTree::Node::SetTo(off_t block)
64{
65	Unset();
66	fBlockNumber = block;
67	fNode = (btrfs_stream*)block_cache_get(fVolume->BlockCache(), block);
68}
69
70
71void
72BTree::Node::SetToWritable(off_t block, int32 transactionId, bool empty)
73{
74	Unset();
75	fBlockNumber = block;
76	fWritable = true;
77	if (empty) {
78		fNode = (btrfs_stream*)block_cache_get_empty(fVolume->BlockCache(),
79			block, transactionId);
80	} else {
81		fNode = (btrfs_stream*)block_cache_get_writable(fVolume->BlockCache(),
82			block, transactionId);
83	}
84}
85
86
87status_t
88BTree::Node::SearchSlot(const btrfs_key& key, int* slot, btree_traversing type)
89	const
90{
91	// binary search for item slot in a node
92	int entrySize = sizeof(btrfs_entry);
93	if (Level() != 0) {
94		// internal node
95		entrySize = sizeof(btrfs_index);
96	}
97
98	int high = ItemCount();
99	int low = 0, mid = 0, comp = 0;
100	uint8* base = (uint8*)fNode + sizeof(btrfs_header);
101	const btrfs_key* other;
102	while (low < high) {
103		mid = (low + high) / 2;
104		other = (const btrfs_key*)(base + mid * entrySize);
105		comp = key.Compare(*other);
106		if (comp < 0)
107			high = mid;
108		else if (comp > 0)
109			low = mid + 1;
110		else {
111			*slot = mid;
112			return B_OK;		// if key is in node
113		}
114	}
115
116	// |--item1--|--item2--|--item3--|--etc--|
117	//     m-1        m        m+1
118	//           k          		: comp < 0
119	//                     k		: comp > 0
120	if (type == BTREE_BACKWARD && comp < 0)
121		mid--;
122	else if (type == BTREE_FORWARD && comp > 0)
123		mid++;
124
125	if (type == BTREE_EXACT || mid < 0)
126		return B_ENTRY_NOT_FOUND;
127
128	*slot = mid;
129	TRACE("SearchSlot() found slot %" B_PRId32 " comp %" B_PRId32 "\n",
130		*slot, comp);
131	return B_OK;
132}
133
134
135int
136BTree::Node::_CalculateSpace(uint32 from, uint32 to, uint8 type) const
137{
138	if (to < from || to >= ItemCount())
139		return 0;
140
141	if (Level() != 0)
142		return sizeof(btrfs_index) * (to - from + 1);
143
144	uint32 result = 0;
145	if ((type & 1) == 1) {
146		result += sizeof(btrfs_entry) * (to - from + 1);
147	}
148	if ((type & 2) == 2) {
149		result += Item(from)->Offset() + Item(from)->Size()
150			- Item(to)->Offset();
151	}
152
153	return result;
154}
155
156
157int
158BTree::Node::SpaceUsed() const
159{
160	if (Level() == 0)
161		return _CalculateSpace(0, ItemCount() - 1, 3);
162	return _CalculateSpace(0, ItemCount() - 1, 0);
163}
164
165
166int
167BTree::Node::SpaceLeft() const
168{
169	return fVolume->BlockSize() - SpaceUsed() - sizeof(btrfs_header);
170}
171
172
173void
174BTree::Node::_Copy(const Node* origin, uint32 at, uint32 from, uint32 to,
175	int length) const
176{
177	TRACE("Node::_Copy() at: %d from: %d to: %d length: %d\n",
178		at, from, to, length);
179
180	if (Level() == 0) {
181		memcpy(Item(at), origin->Item(from), origin->_CalculateSpace(from, to));
182		// Item offset of copied node must be changed to get the
183		// item data offset correctly. length can be zero
184		// but let it there doesn't harm anything.
185		for (uint32 i = at; i - at <= to - from; ++i)
186			Item(i)->SetOffset(Item(i)->Offset() - length);
187
188		memcpy(ItemData(at + to - from), origin->ItemData(to),
189			origin->_CalculateSpace(from, to, 2));
190	} else {
191		memcpy(Index(at), origin->Index(from),
192			origin->_CalculateSpace(from, to));
193	}
194}
195
196
197status_t
198BTree::Node::_SpaceCheck(int length) const
199{
200	// this is a little bit weird here because we can't find
201	// any suitable error code
202	if (length < 0 && abs(length) >= SpaceUsed())
203		return B_DIRECTORY_NOT_EMPTY;	// not enough data to delete
204	if (length > 0 && length >= SpaceLeft())
205		return B_DEVICE_FULL;			// no spare space
206	return B_OK;
207}
208
209
210status_t
211BTree::Node::Copy(const Node* origin, uint32 start, uint32 end, int length)
212	const
213{
214	status_t status = origin->_SpaceCheck(length);
215	if (status != B_OK)
216		return status;
217
218	memcpy(fNode, origin->fNode, sizeof(btrfs_header));
219	if (length == 0) {
220		// like removing [0, start - 1] and keeping [start, end]
221		length = -origin->_CalculateSpace(0, start - 1, 2);
222		_Copy(origin, 0, start, end, length);
223	} else if (length < 0) {
224		// removing all items in [start, end]
225		if (start > 0)
226			_Copy(origin, 0, 0, start - 1, 0);	// <-- [start,...
227		if (end + 1 < origin->ItemCount()) {
228			// ..., end] -->
229			// we only care data size
230			length += origin->_CalculateSpace(start, end);
231			_Copy(origin, start, end + 1, origin->ItemCount() - 1, length);
232		}
233	} else {
234		// inserting in [start, end] - make a hole for later
235		if (start > 0)
236			_Copy(origin, 0, 0, start - 1, 0);
237		if (start < origin->ItemCount()) {
238			length -= origin->_CalculateSpace(start, end);
239			_Copy(origin, end + 1, start, origin->ItemCount() - 1, length);
240		}
241	}
242
243	return B_OK;
244}
245
246
247status_t
248BTree::Node::MoveEntries(uint32 start, uint32 end, int length) const
249{
250	status_t status = _SpaceCheck(length);
251	if (status != B_OK || length == 0/*B_OK*/)
252		return status;
253
254	int entrySize = sizeof(btrfs_entry);
255	if (Level() != 0)
256		entrySize = sizeof(btrfs_index);
257
258	uint8* base = (uint8*)fNode + sizeof(btrfs_header);
259	end++;
260	if (length < 0) {
261		// removing [start, end]
262		TRACE("Node::MoveEntries() removing ... start %" B_PRIu32 " end %"
263			B_PRIu32 " length %i\n", start, end, length);
264		length += _CalculateSpace(start, end - 1);
265	} else {
266		// length > 0
267		// inserting into [start, end] - make room for later
268		TRACE("Node::MoveEntries() inserting ... start %" B_PRIu32 " end %"
269			B_PRIu32 " length %i\n", start, end, length);
270		length -= _CalculateSpace(start, end - 1);
271		uint32 tmp = start;
272		start = end;
273		end = tmp;
274	}
275
276	if (end >= ItemCount())
277		return B_OK;
278
279	int dataSize = _CalculateSpace(end, ItemCount() - 1, 2);
280	// moving items/block pointers
281	memmove(base + start * entrySize, base + end * entrySize,
282		_CalculateSpace(end, ItemCount() - 1));
283	if (Level() == 0) {
284		// moving item data
285		int num = start - end;
286		for (uint32 i = start; i < ItemCount() + num; ++i)
287			Item(i)->SetOffset(Item(i)->Offset() - length);
288
289		memmove(ItemData(ItemCount() - 1) - length, ItemData(ItemCount() - 1),
290			dataSize);
291	}
292
293	return B_OK;
294}
295
296
297//	#pragma mark - BTree::Path implementation
298
299
300BTree::Path::Path(BTree* tree)
301	:
302	fTree(tree)
303{
304	for (int i = 0; i < BTRFS_MAX_TREE_DEPTH; ++i) {
305		fNodes[i] = NULL;
306		fSlots[i] = 0;
307	}
308}
309
310
311BTree::Path::~Path()
312{
313	for (int i = 0; i < BTRFS_MAX_TREE_DEPTH; ++i) {
314		delete fNodes[i];
315		fNodes[i] = NULL;
316		fSlots[i] = 0;
317	}
318}
319
320
321BTree::Node*
322BTree::Path::GetNode(int level, int* _slot) const
323{
324	if (_slot != NULL)
325		*_slot = fSlots[level];
326	return fNodes[level];
327}
328
329
330BTree::Node*
331BTree::Path::SetNode(off_t block, int slot)
332{
333	Node node(fTree->SystemVolume(), block);
334	return SetNode(&node, slot);
335}
336
337
338BTree::Node*
339BTree::Path::SetNode(const Node* node, int slot)
340{
341	uint8 level = node->Level();
342	if (fNodes[level] == NULL) {
343		fNodes[level] = new Node(fTree->SystemVolume(), node->BlockNum());
344		if (fNodes[level] == NULL)
345			return NULL;
346	} else
347		fNodes[level]->SetTo(node->BlockNum());
348
349	if (slot == -1)
350		fSlots[level] = fNodes[level]->ItemCount() - 1;
351	else
352		fSlots[level] = slot;
353	return fNodes[level];
354}
355
356
357int
358BTree::Path::Move(int level, int step)
359{
360	fSlots[level] += step;
361	if (fSlots[level] < 0)
362		return -1;
363	if (fSlots[level] >= fNodes[level]->ItemCount())
364		return 1;
365	return 0;
366}
367
368
369status_t
370BTree::Path::GetEntry(int slot, btrfs_key* _key, void** _value, uint32* _size,
371	uint32* _offset)
372{
373	BTree::Node* leaf = fNodes[0];
374	if (slot < 0 || slot >= leaf->ItemCount())
375		return B_ENTRY_NOT_FOUND;
376
377	if (_key != NULL)
378		*_key = leaf->Item(slot)->key;
379
380	uint32 itemSize = leaf->Item(slot)->Size();
381	if (_value != NULL) {
382		*_value = malloc(itemSize);
383		if (*_value == NULL)
384			return B_NO_MEMORY;
385
386		memcpy(*_value, leaf->ItemData(slot), itemSize);
387	}
388
389	if (_size != NULL)
390		*_size = itemSize;
391
392	if (_offset != NULL)
393		*_offset = leaf->Item(slot)->Offset();
394
395	return B_OK;
396}
397
398
399status_t
400BTree::Path::SetEntry(int slot, const btrfs_entry& entry, void* value)
401{
402	if (slot < 0)
403		return B_ENTRY_NOT_FOUND;
404
405	memcpy(fNodes[0]->Item(slot), &entry, sizeof(btrfs_entry));
406	memcpy(fNodes[0]->ItemData(slot), value, entry.Size());
407	return B_OK;
408}
409
410
411status_t
412BTree::Path::CopyOnWrite(Transaction& transaction, int level, uint32 start,
413	int num, int length)
414{
415	Node* node = fNodes[level];
416	if (node == NULL)
417		return B_BAD_VALUE;
418
419	status_t status;
420	if (transaction.HasBlock(node->BlockNum())) {
421		// cow-ed block can not be cow-ed again
422		status = node->MoveEntries(start, start + num - 1, length);
423		if (status != B_OK)
424			return status;
425
426		node->SetGeneration(transaction.SystemID());
427		if (length < 0)
428			node->SetItemCount(node->ItemCount() - num);
429		else if (length > 0)
430			node->SetItemCount(node->ItemCount() + num);
431
432		return B_OK;
433	}
434
435	uint64 address;
436	fsblock_t block;
437	status = fTree->SystemVolume()->GetNewBlock(address, block);
438	if (status != B_OK)
439		return status;
440
441	fNodes[level] = new(std::nothrow) BTree::Node(fTree->SystemVolume());
442	if (fNodes[level] == NULL)
443		return B_NO_MEMORY;
444
445	fNodes[level]->SetToWritable(block, transaction.ID(), true);
446
447	status = fNodes[level]->Copy(node, start, start + num - 1, length);
448	if (status != B_OK)
449		return status;
450
451	fNodes[level]->SetGeneration(transaction.SystemID());
452	fNodes[level]->SetLogicalAddress(address);
453	if (length < 0)
454		fNodes[level]->SetItemCount(node->ItemCount() - num);
455	else if (length > 0)
456		fNodes[level]->SetItemCount(node->ItemCount() + num);
457	else
458		fNodes[level]->SetItemCount(num);
459
460	// change pointer of this node in parent
461	int parentSlot;
462	Node* parentNode = GetNode(level + 1, &parentSlot);
463	if (parentNode != NULL)
464		parentNode->Index(parentSlot)->SetLogicalAddress(address);
465
466	if (level == fTree->RootLevel())
467		fTree->SetRoot(fNodes[level]);
468
469	delete node;
470	return B_OK;
471}
472
473
474status_t
475BTree::Path::InternalCopy(Transaction& transaction, int level)
476{
477	if (abs(level) >= fTree->RootLevel())
478		return B_OK;
479
480	TRACE("Path::InternalCopy() level %i\n", level);
481	int from, to;
482	if (level > 0) {
483		from = level;
484		to = fTree->RootLevel();
485	} else {
486
487
488		from = 0;
489		to = abs(level);
490	}
491
492	Node* node = NULL;
493	status_t status;
494	while (from <= to) {
495		node = fNodes[from];
496		status = CopyOnWrite(transaction, from, 0, node->ItemCount(), 0);
497		from++;
498		if (status != B_OK)
499			return status;
500	}
501
502	return B_OK;
503}
504
505
506//	#pragma mark - BTree implementation
507
508
509BTree::BTree(Volume* volume)
510	:
511	fRootBlock(0),
512	fRootLevel(0),
513	fVolume(volume)
514{
515	mutex_init(&fIteratorLock, "btrfs b+tree iterator");
516}
517
518
519BTree::BTree(Volume* volume, btrfs_stream* stream)
520	:
521	fRootBlock(0),
522	fRootLevel(0),
523	fVolume(volume)
524{
525	mutex_init(&fIteratorLock, "btrfs b+tree iterator");
526}
527
528
529BTree::BTree(Volume* volume, fsblock_t rootBlock)
530	:
531	fRootBlock(rootBlock),
532	fVolume(volume)
533{
534	mutex_init(&fIteratorLock, "btrfs b+tree iterator");
535}
536
537
538BTree::~BTree()
539{
540	// if there are any TreeIterators left, we need to stop them
541	// (can happen when the tree's inode gets deleted while
542	// traversing the tree - a TreeIterator doesn't lock the inode)
543	mutex_lock(&fIteratorLock);
544
545	SinglyLinkedList<TreeIterator>::Iterator iterator
546		= fIterators.GetIterator();
547	while (iterator.HasNext())
548		iterator.Next()->Stop();
549	mutex_destroy(&fIteratorLock);
550}
551
552
553int32
554btrfs_key::Compare(const btrfs_key& key) const
555{
556	if (ObjectID() > key.ObjectID())
557		return 1;
558	if (ObjectID() < key.ObjectID())
559		return -1;
560	if (Type() > key.Type())
561		return 1;
562	if (Type() < key.Type())
563		return -1;
564	if (Offset() > key.Offset())
565		return 1;
566	if (Offset() < key.Offset())
567		return -1;
568	return 0;
569}
570
571
572status_t
573BTree::Traverse(btree_traversing type, Path* path, const btrfs_key& key)
574	const
575{
576	TRACE("BTree::Traverse() objectid %" B_PRId64 " type %d offset %"
577		B_PRId64 " \n", key.ObjectID(),	key.Type(), key.Offset());
578	fsblock_t physicalBlock = fRootBlock;
579	Node node(fVolume, physicalBlock);
580	int slot;
581	status_t status = B_OK;
582
583	while (node.Level() != 0) {
584		TRACE("BTree::Traverse() level %d count %d\n", node.Level(),
585			node.ItemCount());
586		status = node.SearchSlot(key, &slot, BTREE_BACKWARD);
587		if (status != B_OK)
588			return status;
589		if (path->SetNode(&node, slot) == NULL)
590			return B_NO_MEMORY;
591
592		TRACE("BTree::Traverse() getting index %" B_PRIu32 "\n", slot);
593
594		status = fVolume->FindBlock(node.Index(slot)->LogicalAddress(),
595				physicalBlock);
596		if (status != B_OK) {
597			ERROR("BTree::Traverse() unmapped block %" B_PRId64 "\n",
598				node.Index(slot)->LogicalAddress());
599			return status;
600		}
601		node.SetTo(physicalBlock);
602	}
603
604	TRACE("BTree::Traverse() dump count %" B_PRId32 "\n", node.ItemCount());
605	status = node.SearchSlot(key, &slot, type);
606	if (status != B_OK)
607		return status;
608	if (path->SetNode(&node, slot) == NULL)
609		return B_NO_MEMORY;
610
611	TRACE("BTree::Traverse() found %" B_PRIu32 " %" B_PRIu32 "\n",
612		node.Item(slot)->Offset(), node.Item(slot)->Size());
613	return slot;
614}
615
616
617status_t
618BTree::_Find(Path* path, btrfs_key& wanted, void** _value, uint32* _size,
619	uint32* _offset, btree_traversing type) const
620{
621	status_t status = Traverse(type, path, wanted);
622	if (status < B_OK)
623		return status;
624
625	btrfs_key found;
626	status = path->GetCurrentEntry(&found, _value, _size, _offset);
627	if (status != B_OK)
628		return status;
629
630	if (found.Type() != wanted.Type() && wanted.Type() != BTRFS_KEY_TYPE_ANY) {
631		ERROR("Find() not found wanted: %" B_PRIu64 " %" B_PRIu8 " %"
632			B_PRIu64 " found: %" B_PRIu64 " %" B_PRIu8 " %" B_PRIu64 "\n",
633			wanted.ObjectID(), wanted.Type(), wanted.Offset(), found.ObjectID(),
634			found.Type(), found.Offset());
635		return B_ENTRY_NOT_FOUND;
636	}
637
638	wanted = found;
639	return B_OK;
640}
641
642
643status_t
644BTree::FindNext(Path* path, btrfs_key& key, void** _value, uint32* _size,
645	uint32* _offset) const
646{
647	return _Find(path, key, _value, _size, _offset, BTREE_FORWARD);
648}
649
650
651status_t
652BTree::FindPrevious(Path* path, btrfs_key& key, void** _value, uint32* _size,
653	uint32* _offset) const
654{
655	return _Find(path, key, _value, _size, _offset, BTREE_BACKWARD);
656}
657
658
659status_t
660BTree::FindExact(Path* path, btrfs_key& key, void** _value, uint32* _size,
661	uint32* _offset) const
662{
663	return _Find(path, key, _value, _size, _offset, BTREE_EXACT);
664}
665
666
667status_t
668BTree::MakeEntries(Transaction& transaction, Path* path,
669	const btrfs_key& startKey, int num, int length)
670{
671	TRACE("BTree::MakeEntries() num %i key (% " B_PRIu64 " %" B_PRIu8 " %"
672		B_PRIu64 ")\n", num, startKey.ObjectID(), startKey.Type(),
673		startKey.Offset());
674
675	status_t status = Traverse(BTREE_FORWARD, path, startKey);
676	if (status < B_OK)
677		return status;
678
679	int slot = status;
680	status = path->InternalCopy(transaction, 1);
681	if (status != B_OK)
682		return status;
683
684	status = path->CopyOnWrite(transaction, 0, slot, num, length);
685	if (status == B_DEVICE_FULL) {
686		// TODO: push data or split node
687		return status;
688	}
689
690	if (status != B_OK)
691		return status;
692	return slot;
693}
694
695
696status_t
697BTree::InsertEntries(Transaction& transaction, Path* path,
698	btrfs_entry* entries, void** data, int num)
699{
700	int totalLength = sizeof(btrfs_entry) * num;
701	for (int i = 0; i < num; i++)
702		totalLength += entries[i].Size();
703
704	status_t slot = MakeEntries(transaction, path, entries[0].key, num,
705		totalLength);
706	if (slot < B_OK)
707		return slot;
708
709	uint32 upperLimit;
710	if (slot > 0) {
711		path->GetEntry(slot - 1, NULL, NULL, NULL, &upperLimit);
712	} else
713		upperLimit = fVolume->BlockSize() - sizeof(btrfs_header);
714
715	TRACE("BTree::InsertEntries() num: %i upper limit %" B_PRIu32 "\n", num,
716		upperLimit);
717	for (int i = 0; i < num; i++) {
718		upperLimit -= entries[i].Size();
719		entries[i].SetOffset(upperLimit);
720		path->SetEntry(slot + i, entries[i], data[i]);
721	}
722
723	return B_OK;
724}
725
726
727status_t
728BTree::RemoveEntries(Transaction& transaction, Path* path,
729	const btrfs_key& startKey, void** _data, int num)
730{
731	TRACE("BTree::RemoveEntries() num %i key (% " B_PRIu64 " %" B_PRIu8 " %"
732		B_PRIu64 ")\n", num, startKey.ObjectID(), startKey.Type(),
733		startKey.Offset());
734
735	status_t status = Traverse(BTREE_EXACT, path, startKey);
736	if (status < B_OK)
737		return status;
738
739	int slot = status;
740	int length = -sizeof(btrfs_entry) * num;
741	for (int i = 0; i < num; i++) {
742		uint32 itemSize;
743		path->GetEntry(slot + i, NULL, &_data[i], &itemSize);
744		length -= itemSize;
745	}
746
747	status = path->InternalCopy(transaction, 1);
748	if (status != B_OK)
749		return status;
750
751	status = path->CopyOnWrite(transaction, 0, slot, num, length);
752	if (status == B_DIRECTORY_NOT_EMPTY) {
753		// TODO: merge node or push data
754	}
755
756	return status;
757}
758
759
760status_t
761BTree::PreviousLeaf(Path* path) const
762{
763	// TODO: use Traverse() ???
764	int level = 0;
765	int slot;
766	Node* node = NULL;
767	// iterate to the root until satisfy the condition
768	while (true) {
769		node = path->GetNode(level, &slot);
770		if (node == NULL || slot != 0)
771			break;
772		level++;
773	}
774
775	// the current leaf is already the left most leaf or
776	// path was not initialized
777	if (node == NULL)
778		return B_ENTRY_NOT_FOUND;
779
780	path->Move(level, BTREE_BACKWARD);
781	fsblock_t physicalBlock;
782	// change all nodes below this level and slot to the ending
783	do {
784		status_t status = fVolume->FindBlock(
785			node->Index(slot)->LogicalAddress(), physicalBlock);
786		if (status != B_OK)
787			return status;
788
789		node = path->SetNode(physicalBlock, -1);
790		if (node == NULL)
791			return B_NO_MEMORY;
792		slot = node->ItemCount() - 1;
793		level--;
794	} while (level != 0);
795
796	return B_OK;
797}
798
799
800status_t
801BTree::NextLeaf(Path* path) const
802{
803	int level = 0;
804	int slot;
805	Node* node = NULL;
806	// iterate to the root until satisfy the condition
807	while (true) {
808		node = path->GetNode(level, &slot);
809		if (node == NULL || slot < node->ItemCount() - 1)
810			break;
811		level++;
812	}
813
814	// the current leaf is already the right most leaf or
815	// path was not initialized
816	if (node == NULL)
817		return B_ENTRY_NOT_FOUND;
818
819	path->Move(level, BTREE_FORWARD);
820	fsblock_t physicalBlock;
821	// change all nodes below this level and slot to the beginning
822	do {
823		status_t status = fVolume->FindBlock(
824			node->Index(slot)->LogicalAddress(), physicalBlock);
825		if (status != B_OK)
826			return status;
827
828		node = path->SetNode(physicalBlock, 0);
829		if (node == NULL)
830			return B_NO_MEMORY;
831		slot = 0;
832		level--;
833	} while (level != 0);
834
835	return B_OK;
836}
837
838
839status_t
840BTree::SetRoot(off_t logical, fsblock_t* block)
841{
842	if (block != NULL) {
843		fRootBlock = *block;
844	} else {
845		if (fVolume->FindBlock(logical, fRootBlock) != B_OK) {
846			ERROR("SetRoot() unmapped block %" B_PRId64 " %" B_PRId64 "\n",
847				logical, fRootBlock);
848			return B_ERROR;
849		}
850	}
851
852	btrfs_header header;
853	read_pos(fVolume->Device(), fRootBlock * fVolume->BlockSize(), &header,
854		sizeof(btrfs_header));
855	fRootLevel = header.Level();
856	fLogicalRoot = header.LogicalAddress();
857	return B_OK;
858}
859
860
861void
862BTree::SetRoot(Node* root)
863{
864	fRootBlock = root->BlockNum();
865	fLogicalRoot = root->LogicalAddress();
866	fRootLevel = root->Level();
867}
868
869
870void
871BTree::_AddIterator(TreeIterator* iterator)
872{
873	MutexLocker _(fIteratorLock);
874	fIterators.Add(iterator);
875}
876
877
878void
879BTree::_RemoveIterator(TreeIterator* iterator)
880{
881	MutexLocker _(fIteratorLock);
882	fIterators.Remove(iterator);
883}
884
885
886//	#pragma mark -
887
888
889TreeIterator::TreeIterator(BTree* tree, const btrfs_key& key)
890	:
891	fTree(tree),
892	fKey(key),
893	fIteratorStatus(B_NO_INIT)
894{
895	tree->_AddIterator(this);
896	fPath = new(std::nothrow) BTree::Path(tree);
897	if (fPath == NULL)
898		fIteratorStatus = B_NO_MEMORY;
899}
900
901
902TreeIterator::~TreeIterator()
903{
904	if (fTree)
905		fTree->_RemoveIterator(this);
906
907	delete fPath;
908	fPath = NULL;
909}
910
911
912void
913TreeIterator::Rewind(bool inverse)
914{
915	if (inverse)
916		fKey.SetOffset(BTREE_END);
917	else
918		fKey.SetOffset(BTREE_BEGIN);
919	fIteratorStatus = B_NO_INIT;
920}
921
922
923status_t
924TreeIterator::_Traverse(btree_traversing direction)
925{
926	status_t status = fTree->Traverse(direction, fPath, fKey);
927	if (status < B_OK) {
928		ERROR("TreeIterator::Traverse() Find failed\n");
929		return status;
930	}
931
932	return (fIteratorStatus = B_OK);
933}
934
935
936status_t
937TreeIterator::_GetEntry(btree_traversing type, void** _value, uint32* _size,
938	uint32* _offset)
939{
940	status_t status = B_OK;
941	if (fIteratorStatus == B_NO_INIT) {
942		status = _Traverse(type);
943		if (status != B_OK)
944			return status;
945		type = BTREE_EXACT;
946	}
947
948	if (fIteratorStatus != B_OK)
949		return fIteratorStatus;
950
951	int move = fPath->Move(0, type);
952	if (move > 0)
953		status = fTree->NextLeaf(fPath);
954	else if (move < 0)
955		status = fTree->PreviousLeaf(fPath);
956	if (status != B_OK)
957		return status;
958
959	btrfs_key found;
960	status = fPath->GetCurrentEntry(&found, _value, _size, _offset);
961	if (status != B_OK)
962		return status;
963
964	fKey.SetObjectID(found.ObjectID());
965	fKey.SetOffset(found.Offset());
966	if (fKey.Type() != found.Type() && fKey.Type() != BTRFS_KEY_TYPE_ANY)
967		return B_ENTRY_NOT_FOUND;
968
969	return B_OK;
970}
971
972
973status_t
974TreeIterator::Find(const btrfs_key& key)
975{
976	if (fIteratorStatus == B_INTERRUPTED)
977		return fIteratorStatus;
978
979	fKey = key;
980	fIteratorStatus = B_NO_INIT;
981	return B_OK;
982}
983
984
985void
986TreeIterator::Stop()
987{
988	fTree = NULL;
989	fIteratorStatus = B_INTERRUPTED;
990}
991