file_corruption/fs/Directory.cpp

36 	inline	uint64				BlockIndexAt(int32 index) const;
37 			const char*			NameAt(int32 index, size_t& _nameLength) const;
42 			int32				FindSplitIndex(int32 index,
45 			void				InsertEntry(int32 index, const char* name,
47 			void				ReplaceEntryName(int32 index, const char* name,
49 			void				RemoveEntry(int32 index);
87 				int32			index;
199 DirEntryBlock::BlockIndexAt(int32 index) const
203 	return blockIndices[-index];
208 DirEntryBlock::NameAt(int32 index, size_t& _nameLength) const
211 	if (index < 0 || index >= entryCount)
214 	uint32 nameOffset = index > 0 ? fBlock->nameEnds[index - 1] : 0;
215 	_nameLength = fBlock->nameEnds[index] - nameOffset;
233 	int32 index = 0;
237 	for (; index < entryCount; index++) {
239 		size_t entryNameLength = fBlock->nameEnds[index] - nameOffset;
249 	return index;
253 /*!	Finds a good split index for an insertion of \a bytesNeeded bytes at
254 	index \a index.
257 DirEntryBlock::FindSplitIndex(int32 index, size_t bytesNeeded) const
264 		if (i == index)
276 DirEntryBlock::InsertEntry(int32 index, const char* name, size_t nameLength,
283 	uint32 nameOffset = index == 0 ? 0 : fBlock->nameEnds[index - 1];
287 	if (index < entryCount) {
290 			8 * (entryCount - index));
297 		// move the names < index by 2 bytes
298 		if (index > 0)
301 		// move and update the nameEnds entries > index
302 		for (int32 i = entryCount; i > index; i--)
312 	fBlock->nameEnds[index] = nameOffset + nameLength;
313 	blockIndices[-index] = blockIndex;
320 DirEntryBlock::ReplaceEntryName(int32 index, const char* name,
326 	ASSERT(index >= 0 && index < entryCount);
328 	uint32 nameOffset = index == 0 ? 0 : fBlock->nameEnds[index - 1];
329 	uint32 oldNameLength = fBlock->nameEnds[index] - nameOffset;
338 		if (index + 1 < entryCount) {
345 		for (int32 i = index; i < entryCount; i++)
356 DirEntryBlock::RemoveEntry(int32 index)
358 	ASSERT(index >= 0 && index < EntryCount());
370 	uint32 nameOffset = index == 0 ? 0 : fBlock->nameEnds[index - 1];
371 	uint32 nameEnd = fBlock->nameEnds[index];
375 	if (index < entryCount - 1) {
380 			8 * (entryCount - index - 1));
382 		// move and update the nameEnds entries > index
383 		for (int32 i = index + 1; i < entryCount; i++)
386 		// move the names < index by 2 bytes
387 		if (index > 0)
390 		// move the names > index
462 	// Check size: Both name ends and block index arrays must fit and we need
522 		// check the block index
525 				" has invalid block index: %" B_PRIu64, i, blockIndices[-i]);
573 		int32 index = entryBlock.FindInsertionIndex(name, nameLength,
576 		// If we haven't found an exact match, the index points to the first
579 			if (index == 0) {
585 			index--;
588 		PRINT("  level %" B_PRId32 " -> index: %" B_PRId32 " %sexact\n", level,
589 			index, exactMatch ? "" : " not ");
591 		uint64 blockIndex = entryBlock.BlockIndexAt(index);
655 		info.index = info.entryBlock.FindInsertionIndex(name, nameLength,
658 		PRINT("  level %" B_PRId32 " -> index: %" B_PRId32 " %sexact\n", level,
659 			info.index, info.exactMatch ? "" : " not ");
664 		// If we haven't found an exact match, the index points to the first
666 		if (!info.exactMatch && info.index > 0)
667 			info.index--;
669 		uint64 nextBlockIndex = info.entryBlock.BlockIndexAt(info.index);
686 		infos[depth].index++;
688 	if (infos[depth].index >= infos[depth].entryBlock.EntryCount()) {
696 			if (++info.index < info.entryBlock.EntryCount()) {
697 				PRINT("  found greater branch: level: %" B_PRId32 " -> index: %"
698 					B_PRId32 "\n", level, info.index);
712 				previousInfo.index);
724 			info.index = 0;
733 	name = info.entryBlock.NameAt(info.index, nameLength);
743 	_blockIndex = info.entryBlock.BlockIndexAt(info.index);
784 				info.index = 0;
791 		info.index = info.entryBlock.FindInsertionIndex(name, nameLength,
794 		PRINT("  level %" B_PRId32 ", block %" B_PRIu64 " -> index: %" B_PRId32
797 			info.index, info.exactMatch ? "" : " not ");
809 		// Since we haven't found an exact match, the index points to the
811 		info.index--;
813 		uint64 nextBlockIndex = info.entryBlock.BlockIndexAt(info.index);
830 	// to perform the potentially necessary updates. Insertion at index 0 of
881 		info.index = info.entryBlock.FindInsertionIndex(name, nameLength,
884 		PRINT("  level %" B_PRId32 ", block %" B_PRIu64 " -> index: %" B_PRId32
887 			info.index, info.exactMatch ? "" : " not ");
896 		// If we haven't found an exact match, the index points to the first
899 			if (info.index == 0) {
905 			info.index--;
908 		uint64 nextBlockIndex = info.entryBlock.BlockIndexAt(info.index);
925 	// the potentially necessary updates. Removal at index 0 of the block
944 		PRINT("  level: %" B_PRId32 ", index: %" B_PRId32 ": removing key "
945 			"\"%.*s\" (%" B_PRIuSIZE ")\n", level, info.index, (int)nameLength,
953 				info.entryBlock.RemoveEntry(info.index);
970 		info.entryBlock.RemoveEntry(info.index);
972 		if (info.index > 0 || level == 0)
1002 	infos[0].index = 0;
1010 		if (level == depth || info.index >= info.entryBlock.EntryCount()) {
1020 			infos[--level].index++;
1024 		uint64 nextBlockIndex = info.entryBlock.BlockIndexAt(info.index);
1158 			PRINT("  level: %" B_PRId32 ", index: %" B_PRId32 ": updating key "
1159 				"to \"%.*s\" (%" B_PRIuSIZE ")\n", level, info.index,
1163 			info.entryBlock.NameAt(info.index, oldNameLength);
1168 				info.entryBlock.ReplaceEntryName(info.index, nameToUpdate,
1170 				if (info.index == 0) {
1171 					// we updated at index 0, so we need to update this
1208 				if (info.index < splitIndex) {
1211 					info.entryBlock.ReplaceEntryName(info.index,
1213 					if (info.index == 0) {
1214 						// we updated at index 0, so we need to update this
1235 					info.index -= splitIndex;
1237 					info.entryBlock.ReplaceEntryName(info.index, nameToUpdate,
1257 				info.index++;
1259 			PRINT("  level: %" B_PRId32 ", index: %" B_PRId32 ": inserting key "
1261 				level, info.index, (int)nameLength, name, nameLength,
1265 				info.entryBlock.InsertEntry(info.index, name,
1267 				if (info.index == 0) {
1268 					// we inserted at index 0, so we need to update this
1309 			if (info.index < splitIndex) {
1312 				info.entryBlock.InsertEntry(info.index, name,
1314 				if (info.index == 0) {
1315 					// we inserted at index 0, so we need to update this
1328 				info.index -= splitIndex;
1330 				newEntryBlock.InsertEntry(info.index, name, nameLength,
1391 	newInfo.index = rootInfo.index;
1392 	rootInfo.index = 0;
1404 	int32 splitIndex = info.entryBlock.FindSplitIndex(info.index,
1407 	FUNCTION("level: %" B_PRId32 ", size needed: %" B_PRIuSIZE ", split index: "