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