1/*
2 * Copyright 2008, Axel Dörfler, axeld@pinc-software.de.
3 * This file may be used under the terms of the MIT License.
4 */
5
6
7#include "DirectoryIterator.h"
8
9#include <string.h>
10
11#include <AutoDeleter.h>
12#include <util/VectorSet.h>
13
14#include "CachedBlock.h"
15#include "HTree.h"
16#include "Inode.h"
17
18
19//#define TRACE_EXT2
20#ifdef TRACE_EXT2
21#	define TRACE(x...) dprintf("\33[34mext2:\33[0m " x)
22#else
23#	define TRACE(x...) ;
24#endif
25
26
27struct HashedEntry
28{
29	uint8*	position;
30	uint32	hash;
31
32	bool	operator<(const HashedEntry& other)	const
33	{
34		return hash <= other.hash;
35	}
36
37	bool	operator>(const HashedEntry& other)	const
38	{
39		return hash >= other.hash;
40	}
41};
42
43
44DirectoryIterator::DirectoryIterator(Inode* directory, off_t start,
45	HTreeEntryIterator* parent)
46	:
47	fDirectory(directory),
48	fVolume(directory->GetVolume()),
49	fBlockSize(fVolume->BlockSize()),
50	fParent(parent),
51	fNumBlocks(directory->Size() == 0 ? 0
52		: (directory->Size() - 1) / fBlockSize + 1),
53	fLogicalBlock(start / fBlockSize),
54	fDisplacement(start % fBlockSize),
55	fPreviousDisplacement(fDisplacement),
56	fStartLogicalBlock(fLogicalBlock),
57	fStartDisplacement(fDisplacement)
58{
59	TRACE("DirectoryIterator::DirectoryIterator() %" B_PRIdINO ": num blocks: "
60		"%" B_PRIu32 "\n", fDirectory->ID(), fNumBlocks);
61	fIndexing = parent != NULL;
62	fInitStatus = fDirectory->FindBlock(start, fPhysicalBlock);
63	fStartPhysicalBlock = fPhysicalBlock;
64}
65
66
67DirectoryIterator::~DirectoryIterator()
68{
69	TRACE("DirectoryIterator::~DirectoryIterator(): %p, parent: %p\n", this,
70		fParent);
71	delete fParent;
72	TRACE("DirectoryIterator::~DirectoryIterator(): Deleted the parent\n");
73}
74
75
76status_t
77DirectoryIterator::InitCheck()
78{
79	return fInitStatus;
80}
81
82
83status_t
84DirectoryIterator::Get(char* name, size_t* _nameLength, ino_t* _id)
85{
86	TRACE("DirectoryIterator::Get() ID %" B_PRIdINO "\n", fDirectory->ID());
87	if (_Offset() >= fDirectory->Size()) {
88		TRACE("DirectoryIterator::Get() out of entries\n");
89		return B_ENTRY_NOT_FOUND;
90	}
91
92	CachedBlock cached(fVolume);
93	const uint8* block = cached.SetTo(fPhysicalBlock);
94	if (block == NULL)
95		return B_IO_ERROR;
96
97	TRACE("DirectoryIterator::Get(): Displacement: %" B_PRIu32 "\n",
98		fDisplacement);
99	const ext2_dir_entry* entry = (const ext2_dir_entry*)&block[fDisplacement];
100
101	if (entry->Length() == 0 || entry->InodeID() == 0)
102		return B_BAD_DATA;
103
104	if (entry->NameLength() != 0) {
105		size_t length = entry->NameLength();
106
107		TRACE("block %" B_PRIu32 ", displacement %" B_PRIu32 ": entry ino %"
108			B_PRIu32 ", length %u, name length %" B_PRIuSIZE ", type %u\n",
109			fLogicalBlock, fDisplacement, entry->InodeID(), entry->Length(),
110			length,	entry->FileType());
111
112		if (*_nameLength > 0) {
113			if (length + 1 > *_nameLength)
114				return B_BUFFER_OVERFLOW;
115
116			memcpy(name, entry->name, length);
117			name[length] = '\0';
118
119			*_nameLength = length;
120		}
121
122		*_id = entry->InodeID();
123	} else
124		*_nameLength = 0;
125
126	return B_OK;
127}
128
129
130status_t
131DirectoryIterator::GetNext(char* name, size_t* _nameLength, ino_t* _id)
132{
133	status_t status;
134	while ((status = Get(name, _nameLength, _id)) == B_BAD_DATA) {
135		status = Next();
136		if (status != B_OK)
137			return status;
138	}
139	return status;
140}
141
142
143status_t
144DirectoryIterator::Next()
145{
146	TRACE("DirectoryIterator::Next() fDirectory->ID() %" B_PRIdINO "\n",
147		fDirectory->ID());
148
149	if (_Offset() >= fDirectory->Size()) {
150		TRACE("DirectoryIterator::Next() out of entries\n");
151		return B_ENTRY_NOT_FOUND;
152	}
153
154	TRACE("DirectoryIterator::Next(): Creating cached block\n");
155
156	CachedBlock cached(fVolume);
157	ext2_dir_entry* entry;
158
159	TRACE("DirectoryIterator::Next(): Loading cached block\n");
160	const uint8* block = cached.SetTo(fPhysicalBlock);
161	if (block == NULL)
162		return B_IO_ERROR;
163
164	entry = (ext2_dir_entry*)(block + fDisplacement);
165
166	do {
167		TRACE("Checking entry at block %" B_PRIu64 ", displacement %" B_PRIu32
168			" entry inodeid %" B_PRIu32 "\n", fPhysicalBlock, fDisplacement,
169			entry->InodeID());
170
171		if (entry->Length() != 0) {
172			if (!entry->IsValid()) {
173				TRACE("invalid entry.\n");
174				return B_BAD_DATA;
175			}
176			fPreviousDisplacement = fDisplacement;
177			fDisplacement += entry->Length();
178		} else
179			fDisplacement = fBlockSize;
180
181		if (fDisplacement == fBlockSize) {
182			TRACE("Reached end of block\n");
183
184			fDisplacement = 0;
185
186			status_t status = _NextBlock();
187			if (status != B_OK)
188				return status;
189
190			if ((off_t)(_Offset() + ext2_dir_entry::MinimumSize())
191					>= fDirectory->Size()) {
192				TRACE("DirectoryIterator::Next() end of directory file\n");
193				return B_ENTRY_NOT_FOUND;
194			}
195			status = fDirectory->FindBlock(_Offset(), fPhysicalBlock);
196			if (status != B_OK)
197				return status;
198
199			block = cached.SetTo(fPhysicalBlock);
200			if (block == NULL)
201				return B_IO_ERROR;
202		} else if (fDisplacement > fBlockSize) {
203			TRACE("The entry isn't block aligned.\n");
204			// TODO: Is block alignment obligatory?
205			return B_BAD_DATA;
206		}
207
208		entry = (ext2_dir_entry*)(block + fDisplacement);
209
210		TRACE("DirectoryIterator::Next() skipping entry %d %" B_PRIu32 "\n",
211			entry->Length(), entry->InodeID());
212	} while (entry->Length() == 0 || entry->InodeID() == 0);
213
214	TRACE("DirectoryIterator::Next() entry->Length() %d entry->name %*s\n",
215			entry->Length(), entry->NameLength(), entry->name);
216
217	return B_OK;
218}
219
220
221status_t
222DirectoryIterator::Rewind()
223{
224	fDisplacement = 0;
225	fPreviousDisplacement = 0;
226	fLogicalBlock = 0;
227
228	return fDirectory->FindBlock(0, fPhysicalBlock);
229}
230
231
232void
233DirectoryIterator::Restart()
234{
235	TRACE("DirectoryIterator::Restart(): (logical, physical, displacement): "
236		"current: (%" B_PRIu32 ", %" B_PRIu64 ", %" B_PRIu32 "), start: (%"
237		B_PRIu32 ", %" B_PRIu64 ", %" B_PRIu32 ")\n", fLogicalBlock,
238		fPhysicalBlock, fDisplacement, fStartLogicalBlock, fStartPhysicalBlock,
239		fStartDisplacement);
240	fLogicalBlock = fStartLogicalBlock;
241	fPhysicalBlock = fStartPhysicalBlock;
242	fDisplacement = fPreviousDisplacement = fStartDisplacement;
243}
244
245
246status_t
247DirectoryIterator::AddEntry(Transaction& transaction, const char* name,
248	size_t _nameLength, ino_t id, uint8 type)
249{
250	TRACE("DirectoryIterator::AddEntry(%s, ...)\n", name);
251
252	uint8 nameLength = _nameLength > EXT2_NAME_LENGTH ? EXT2_NAME_LENGTH
253		: _nameLength;
254
255	status_t status = B_OK;
256	while (status == B_OK) {
257		uint16 pos = 0;
258		uint16 newLength;
259
260		status = _AllocateBestEntryInBlock(nameLength, pos, newLength);
261		if (status == B_OK) {
262			return _AddEntry(transaction, name, nameLength, id, type, newLength,
263				pos);
264		} else if (status != B_DEVICE_FULL)
265			return status;
266
267		fDisplacement = 0;
268		status = _NextBlock();
269		if (status == B_OK)
270			status = fDirectory->FindBlock(_Offset(), fPhysicalBlock);
271	}
272
273	if (status != B_ENTRY_NOT_FOUND)
274		return status;
275
276	bool firstSplit = fNumBlocks == 1 && fVolume->IndexedDirectories();
277
278	fNumBlocks++;
279
280	if (fIndexing) {
281		TRACE("DirectoryIterator::AddEntry(): Adding another HTree leaf\n");
282		fNumBlocks += fParent->BlocksNeededForNewEntry();
283	} else if (firstSplit) {
284		// Allocate another block (fNumBlocks should become 3)
285		TRACE("DirectoryIterator::AddEntry(): Creating index for directory\n");
286		fNumBlocks++;
287	} else
288		TRACE("DirectoryIterator::AddEntry(): Enlarging directory\n");
289
290	status = fDirectory->Resize(transaction, fNumBlocks * fBlockSize);
291	if (status != B_OK)
292		return status;
293
294	if (firstSplit || fIndexing) {
295		// firstSplit and fIndexing are mutually exclusive
296		return _SplitIndexedBlock(transaction, name, nameLength, id, type,
297			fNumBlocks - 1, firstSplit);
298	}
299
300	fLogicalBlock = fNumBlocks - 1;
301	status = fDirectory->FindBlock(fLogicalBlock * fBlockSize, fPhysicalBlock);
302	if (status != B_OK)
303		return status;
304
305	return _AddEntry(transaction, name, nameLength, id, type, fBlockSize, 0,
306		false);
307}
308
309
310status_t
311DirectoryIterator::FindEntry(const char* name, ino_t* _id)
312{
313	TRACE("DirectoryIterator::FindEntry(): %p %p\n", this, name);
314	char buffer[EXT2_NAME_LENGTH + 1];
315	ino_t id;
316
317	status_t status = B_OK;
318	size_t length = strlen(name);
319	while (status == B_OK) {
320		size_t nameLength = EXT2_NAME_LENGTH;
321		status = Get(buffer, &nameLength, &id);
322		if (status == B_OK) {
323			if (length == nameLength
324				&& strncmp(name, buffer, nameLength) == 0) {
325				if (_id != NULL)
326					*_id = id;
327				return B_OK;
328			}
329		} else if (status != B_BAD_DATA)
330			break;
331		status = Next();
332	}
333
334	return status;
335}
336
337
338status_t
339DirectoryIterator::RemoveEntry(Transaction& transaction)
340{
341	TRACE("DirectoryIterator::RemoveEntry()\n");
342	ext2_dir_entry* previousEntry;
343	ext2_dir_entry* dirEntry;
344	CachedBlock cached(fVolume);
345
346	uint8* block = cached.SetToWritable(transaction, fPhysicalBlock);
347
348	if (fDisplacement == 0) {
349		previousEntry = (ext2_dir_entry*)&block[fDisplacement];
350
351		fPreviousDisplacement = fDisplacement;
352		fDisplacement += previousEntry->Length();
353
354		if (fDisplacement == fBlockSize) {
355			previousEntry->SetInodeID(0);
356			fDisplacement = 0;
357			return B_OK;
358		} else if (fDisplacement > fBlockSize) {
359			TRACE("DirectoryIterator::RemoveEntry(): Entry isn't aligned to "
360				"block entry.");
361			return B_BAD_DATA;
362		}
363
364		dirEntry = (ext2_dir_entry*)&block[fDisplacement];
365		memcpy(&block[fPreviousDisplacement], &block[fDisplacement],
366			dirEntry->Length());
367
368		previousEntry->SetLength(fDisplacement - fPreviousDisplacement
369			+ previousEntry->Length());
370
371		return B_OK;
372	}
373
374	TRACE("DirectoryIterator::RemoveEntry() fDisplacement %" B_PRIu32 "\n",
375		fDisplacement);
376
377	if (fPreviousDisplacement == fDisplacement) {
378		char buffer[EXT2_NAME_LENGTH + 1];
379
380		dirEntry = (ext2_dir_entry*)&block[fDisplacement];
381
382		memcpy(buffer, dirEntry->name, (uint32)dirEntry->name_length);
383
384		fDisplacement = 0;
385		status_t status = FindEntry(dirEntry->name);
386		if (status == B_ENTRY_NOT_FOUND)
387			return B_BAD_DATA;
388		if (status != B_OK)
389			return status;
390	}
391
392	previousEntry = (ext2_dir_entry*)&block[fPreviousDisplacement];
393	dirEntry = (ext2_dir_entry*)&block[fDisplacement];
394
395	previousEntry->SetLength(previousEntry->Length() + dirEntry->Length());
396
397	memset(&block[fDisplacement], 0,
398		fPreviousDisplacement + previousEntry->Length() - fDisplacement);
399
400	return B_OK;
401}
402
403
404status_t
405DirectoryIterator::ChangeEntry(Transaction& transaction, ino_t id,
406	uint8 fileType)
407{
408	CachedBlock cached(fVolume);
409
410	uint8* block = cached.SetToWritable(transaction, fPhysicalBlock);
411	if (block == NULL)
412		return B_IO_ERROR;
413
414	ext2_dir_entry* dirEntry = (ext2_dir_entry*)&block[fDisplacement];
415	dirEntry->SetInodeID(id);
416	dirEntry->file_type = fileType;
417
418	return B_OK;
419}
420
421
422status_t
423DirectoryIterator::_AllocateBestEntryInBlock(uint8 nameLength, uint16& pos,
424	uint16& newLength)
425{
426	TRACE("DirectoryIterator::_AllocateBestEntryInBlock()\n");
427	CachedBlock cached(fVolume);
428	const uint8* block = cached.SetTo(fPhysicalBlock);
429
430	uint16 requiredLength = nameLength + 8;
431	if (requiredLength % 4 != 0)
432		requiredLength += 4 - requiredLength % 4;
433
434	uint16 bestPos = fBlockSize;
435	uint16 bestLength = fBlockSize;
436	uint16 bestRealLength = fBlockSize;
437	ext2_dir_entry* dirEntry;
438
439	while (pos < fBlockSize) {
440		dirEntry = (ext2_dir_entry*)&block[pos];
441
442		uint16 realLength = dirEntry->NameLength() + 8;
443
444		if (realLength % 4 != 0)
445			realLength += 4 - realLength % 4;
446
447		uint16 emptySpace = dirEntry->Length() - realLength;
448		if (emptySpace == requiredLength) {
449			// Found an exact match
450			TRACE("DirectoryIterator::_AllocateBestEntryInBlock(): Found an "
451				"exact length match\n");
452			newLength = realLength;
453
454			return B_OK;
455		} else if (emptySpace > requiredLength && emptySpace < bestLength) {
456			bestPos = pos;
457			bestLength = emptySpace;
458			bestRealLength = realLength;
459		}
460
461		pos += dirEntry->Length();
462	}
463
464	if (bestPos == fBlockSize)
465		return B_DEVICE_FULL;
466
467	TRACE("DirectoryIterator::_AllocateBestEntryInBlock(): Found a suitable "
468		"location: %u\n", bestPos);
469	pos = bestPos;
470	newLength = bestRealLength;
471
472	return B_OK;
473}
474
475
476status_t
477DirectoryIterator::_AddEntry(Transaction& transaction, const char* name,
478	uint8 nameLength, ino_t id, uint8 type, uint16 newLength, uint16 pos,
479	bool hasPrevious)
480{
481	TRACE("DirectoryIterator::_AddEntry(%s, %d, %" B_PRIdINO ", %d, %d, %d, "
482		"%c)\n", name, nameLength, id, type, newLength, pos,
483		hasPrevious ? 't' : 'f');
484	CachedBlock cached(fVolume);
485
486	uint8* block = cached.SetToWritable(transaction, fPhysicalBlock);
487	if (block == NULL)
488		return B_IO_ERROR;
489
490	ext2_dir_entry* dirEntry = (ext2_dir_entry*)&block[pos];
491
492	if (hasPrevious) {
493		uint16 previousLength = dirEntry->Length();
494		dirEntry->SetLength(newLength);
495
496		dirEntry = (ext2_dir_entry*)&block[pos + newLength];
497		newLength = previousLength - newLength;
498	}
499
500	dirEntry->SetLength(newLength);
501	dirEntry->name_length = nameLength;
502	dirEntry->SetInodeID(id);
503	dirEntry->file_type = type;
504	memcpy(dirEntry->name, name, nameLength);
505
506	TRACE("DirectoryIterator::_AddEntry(): Done\n");
507
508	return B_OK;
509}
510
511
512status_t
513DirectoryIterator::_SplitIndexedBlock(Transaction& transaction,
514	const char* name, uint8 nameLength, ino_t id, uint8 type,
515	uint32 newBlocksPos, bool firstSplit)
516{
517	// Block is full, split required
518	TRACE("DirectoryIterator::_SplitIndexedBlock(.., %s, %u, %" B_PRIdINO ", %"
519		B_PRIu32 ", %c)\n", name, nameLength, id, newBlocksPos,
520		firstSplit ? 't' : 'f');
521
522	// Allocate a buffer for the entries in the block
523	uint8* buffer = new(std::nothrow) uint8[fBlockSize];
524	if (buffer == NULL)
525		return B_NO_MEMORY;
526	ArrayDeleter<uint8> bufferDeleter(buffer);
527
528	fsblock_t firstPhysicalBlock = 0;
529
530	// Prepare block to hold the first half of the entries and fill the buffer
531	CachedBlock cachedFirst(fVolume);
532
533	if (firstSplit) {
534		// Save all entries to the buffer
535		status_t status = fDirectory->FindBlock(0, firstPhysicalBlock);
536		if (status != B_OK)
537			return status;
538
539		const uint8* srcBlock = cachedFirst.SetTo(firstPhysicalBlock);
540		if (srcBlock == NULL)
541			return B_IO_ERROR;
542
543		memcpy(buffer, srcBlock, fBlockSize);
544
545		status = fDirectory->FindBlock(fBlockSize, fPhysicalBlock);
546		if (status != B_OK)
547			return status;
548	}
549
550	uint8* firstBlock = cachedFirst.SetToWritable(transaction, fPhysicalBlock);
551	uint8* secondBlock = NULL;
552	if (firstBlock == NULL)
553		return B_IO_ERROR;
554
555	status_t status;
556
557	if (!firstSplit) {
558		// Save all entries to the buffer
559		memcpy(buffer, firstBlock, fBlockSize);
560	} else {
561		// Initialize the root node
562		fDirectory->Node().SetFlag(EXT2_INODE_INDEXED);
563		HTreeRoot* root;
564
565		secondBlock = cachedFirst.SetToWritable(transaction,
566			firstPhysicalBlock, true);
567		if (secondBlock == NULL)
568			return B_IO_ERROR;
569
570		status = fDirectory->WriteBack(transaction);
571		if (status != B_OK)
572			return status;
573
574		memcpy(secondBlock, buffer, 2 * (sizeof(HTreeFakeDirEntry) + 4));
575
576		root = (HTreeRoot*)secondBlock;
577
578		HTreeFakeDirEntry* dotdot = &root->dotdot;
579		dotdot->SetEntryLength(fBlockSize - (sizeof(HTreeFakeDirEntry) + 4));
580
581		root->hash_version = fVolume->DefaultHashVersion();
582		root->root_info_length = 8;
583		root->indirection_levels = 0;
584
585		root->count_limit->SetLimit((fBlockSize
586			- ((uint8*)root->count_limit - secondBlock)) / sizeof(HTreeEntry));
587		root->count_limit->SetCount(2);
588	}
589
590	// Sort entries
591	VectorSet<HashedEntry> entrySet;
592
593	HTree htree(fVolume, fDirectory);
594	status = htree.PrepareForHash();
595	if (status != B_OK)
596		return status;
597
598	uint32 displacement = firstSplit ? 2 * (sizeof(HTreeFakeDirEntry) + 4) : 0;
599
600	HashedEntry entry;
601	ext2_dir_entry* dirEntry = NULL;
602
603	while (displacement < fBlockSize) {
604		entry.position = &buffer[displacement];
605		dirEntry = (ext2_dir_entry*)entry.position;
606
607		TRACE("DirectoryIterator::_SplitIndexedBlock(): pos: %p, name "
608			"length: %u, entry length: %u\n", entry.position,
609			dirEntry->name_length,
610			dirEntry->Length());
611
612		char cbuffer[256];
613		memcpy(cbuffer, dirEntry->name, dirEntry->name_length);
614		cbuffer[dirEntry->name_length] = '\0';
615		entry.hash = htree.Hash(dirEntry->name, dirEntry->name_length);
616		TRACE("DirectoryIterator::_SplitIndexedBlock(): %s -> %" B_PRIu32 "\n",
617			cbuffer, entry.hash);
618
619		status = entrySet.Insert(entry);
620		if (status != B_OK)
621			return status;
622
623		displacement += dirEntry->Length();
624	}
625
626	// Prepare the new entry to be included as well
627	ext2_dir_entry newEntry;
628
629	uint16 newLength = (uint16)nameLength + 8;
630	if (newLength % 4 != 0)
631		newLength += 4 - newLength % 4;
632
633	newEntry.name_length = nameLength;
634	newEntry.SetLength(newLength);
635	newEntry.SetInodeID(id);
636	newEntry.file_type = type;
637	memcpy(newEntry.name, name, nameLength);
638
639	entry.position = (uint8*)&newEntry;
640	entry.hash = htree.Hash(name, nameLength);
641	TRACE("DirectoryIterator::_SplitIndexedBlock(): %s -> %" B_PRIu32 "\n",
642		name, entry.hash);
643
644	entrySet.Insert(entry);
645
646	// Move first half of entries to the first block
647	VectorSet<HashedEntry>::Iterator iterator = entrySet.Begin();
648	int32 median = entrySet.Count() / 2;
649	displacement = 0;
650	TRACE("DirectoryIterator::_SplitIndexedBlock(): Count: %" B_PRId32
651		", median: %" B_PRId32 "\n", entrySet.Count(), median);
652
653	uint32 previousHash = (*iterator).hash;
654
655	for (int32 i = 0; i < median; ++i) {
656		dirEntry = (ext2_dir_entry*)(*iterator).position;
657		previousHash = (*iterator).hash;
658
659		uint32 realLength = (uint32)dirEntry->name_length + 8;
660		if (realLength % 4 != 0)
661			realLength += 4 - realLength % 4;
662
663		dirEntry->SetLength((uint16)realLength);
664		memcpy(&firstBlock[displacement], dirEntry, realLength);
665
666		displacement += realLength;
667		iterator++;
668	}
669
670	// Update last entry in the block
671	uint16 oldLength = dirEntry->Length();
672	dirEntry = (ext2_dir_entry*)&firstBlock[displacement - oldLength];
673	dirEntry->SetLength(fBlockSize - displacement + oldLength);
674
675	bool collision = false;
676
677	while (iterator != entrySet.End() && (*iterator).hash == previousHash) {
678		// Keep collisions on the same block
679		TRACE("DirectoryIterator::_SplitIndexedBlock(): Handling collisions\n");
680
681		// This isn't the ideal solution, but it is a rare occurance
682		dirEntry = (ext2_dir_entry*)(*iterator).position;
683
684		if (displacement + dirEntry->Length() > fBlockSize) {
685			// Doesn't fit on the block
686			collision = true;
687			break;
688		}
689
690		memcpy(&firstBlock[displacement], dirEntry, dirEntry->Length());
691
692		displacement += dirEntry->Length();
693		iterator++;
694	}
695
696	// Save the hash to store in the parent
697	uint32 medianHash = (*iterator).hash;
698
699	// Update parent
700	if (firstSplit) {
701		TRACE("DirectoryIterator::_SplitIndexedBlock(): Updating root\n");
702		HTreeRoot* root = (HTreeRoot*)secondBlock;
703		HTreeEntry* htreeEntry = (HTreeEntry*)root->count_limit;
704		htreeEntry->SetBlock(1);
705
706		++htreeEntry;
707		htreeEntry->SetBlock(2);
708		htreeEntry->SetHash(medianHash);
709
710		off_t start = (off_t)root->root_info_length
711			+ 2 * (sizeof(HTreeFakeDirEntry) + 4);
712		fParent = new(std::nothrow) HTreeEntryIterator(start, fDirectory);
713		if (fParent == NULL)
714			return B_NO_MEMORY;
715
716		fLogicalBlock = 1;
717		status = fDirectory->FindBlock(fLogicalBlock * fBlockSize,
718			fPhysicalBlock);
719
720		fPreviousDisplacement = fDisplacement = 0;
721
722		status = fParent->Init();
723	}
724	else {
725		status = fParent->InsertEntry(transaction, medianHash, fNumBlocks - 1,
726			newBlocksPos, collision);
727	}
728	if (status != B_OK)
729		return status;
730
731	// Prepare last block to hold the second half of the entries
732	TRACE("DirectoryIterator::_SplitIndexedBlock(): Preparing second leaf "
733		"block\n");
734	fDisplacement = 0;
735
736	status = fDirectory->FindBlock(fDirectory->Size() - 1, fPhysicalBlock);
737	if (status != B_OK)
738		return status;
739
740	CachedBlock cachedSecond(fVolume);
741	secondBlock = cachedSecond.SetToWritable(transaction,
742		fPhysicalBlock);
743	if (secondBlock == NULL)
744		return B_IO_ERROR;
745
746	// Move the second half of the entries to the second block
747	VectorSet<HashedEntry>::Iterator end = entrySet.End();
748	displacement = 0;
749
750	while (iterator != end) {
751		dirEntry = (ext2_dir_entry*)(*iterator).position;
752
753		uint32 realLength = (uint32)dirEntry->name_length + 8;
754		if (realLength % 4 != 0)
755			realLength += 4 - realLength % 4;
756
757		dirEntry->SetLength((uint16)realLength);
758		memcpy(&secondBlock[displacement], dirEntry, realLength);
759
760		displacement += realLength;
761		iterator++;
762	}
763
764	// Update last entry in the block
765	oldLength = dirEntry->Length();
766	dirEntry = (ext2_dir_entry*)&secondBlock[displacement - oldLength];
767	dirEntry->SetLength(fBlockSize - displacement + oldLength);
768
769	TRACE("DirectoryIterator::_SplitIndexedBlock(): Done\n");
770	return B_OK;
771}
772
773
774status_t
775DirectoryIterator::_NextBlock()
776{
777	TRACE("DirectoryIterator::_NextBlock()\n");
778	if (fIndexing) {
779		TRACE("DirectoryIterator::_NextBlock(): Indexing\n");
780		if (!fParent->HasCollision()) {
781			TRACE("DirectoryIterator::_NextBlock(): next block doesn't "
782				"contain collisions from previous block\n");
783#ifndef COLLISION_TEST
784			return B_ENTRY_NOT_FOUND;
785#endif
786		}
787
788		return fParent->GetNext(fLogicalBlock);
789	}
790
791	if (++fLogicalBlock > fNumBlocks)
792		return B_ENTRY_NOT_FOUND;
793
794	return B_OK;
795}
796