/*
 * Copyright 2010, Haiku Inc. All rights reserved.
 * This file may be used under the terms of the MIT License.
 *
 * Authors:
 *		Janito V. Ferreira Filho
 */
#ifndef HTREE_H
#define HTREE_H


#include <AutoDeleter.h>

#include "ext2.h"
#include "DirectoryIterator.h"
#include "HTreeEntryIterator.h"
#include "Inode.h"


#define HTREE_HASH_LEGACY	0
#define HTREE_HASH_HALF_MD4	1
#define HTREE_HASH_TEA		2


struct JournalRevokeHeader;


struct HTreeFakeDirEntry {
	uint32				inode_id;
	uint16				entry_length;
	uint8				name_length;
	uint8				file_type;
	char				file_name[0];
	
	uint32				InodeID() const
		{ return B_LENDIAN_TO_HOST_INT32(inode_id); }


	void				SetEntryLength(uint16 entryLength)
		{ entry_length = B_HOST_TO_LENDIAN_INT16(entryLength); }
} _PACKED;

struct HTreeCountLimit {
	uint16				limit;
	uint16				count;
	
	uint16				Limit() const
		{ return B_LENDIAN_TO_HOST_INT16(limit); }
	uint16				Count() const
		{ return B_LENDIAN_TO_HOST_INT16(count); }
	bool				IsFull() const
		{ return limit == count; }

	void				SetLimit(uint16 value)
		{ limit = B_HOST_TO_LENDIAN_INT16(value); }

	void				SetCount(uint16 value)
		{ count = B_HOST_TO_LENDIAN_INT16(value); }
} _PACKED;

struct HTreeEntry {
	uint32				hash;
	uint32				block;
	
	uint32				Hash() const
		{ return B_LENDIAN_TO_HOST_INT32(hash); }
	uint32				Block() const
		{ return B_LENDIAN_TO_HOST_INT32(block); }

	void				SetHash(uint32 newHash)
		{ hash = B_HOST_TO_LENDIAN_INT32(newHash); }

	void				SetBlock(uint32 newBlock)
		{ block = B_HOST_TO_LENDIAN_INT32(newBlock); }
} _PACKED;

struct HTreeRoot {
	HTreeFakeDirEntry	dot;
	char				dot_entry_name[4];
	HTreeFakeDirEntry	dotdot;
	char				dotdot_entry_name[4];
	
	uint32				reserved;
	uint8				hash_version;
	uint8				root_info_length;
	uint8				indirection_levels;
	uint8				flags;

	HTreeCountLimit		count_limit[0];
	
	bool				IsValid() const;
		// Implemented in HTree.cpp
} _PACKED;

struct HTreeIndirectNode {
	HTreeFakeDirEntry	fake_entry;
	HTreeEntry			entries[0];
} _PACKED;


/*! Hash implementations:
 * References:
 * Main reference: Linux htree patch:
 *    http://thunk.org/tytso/linux/ext3-dxdir/patch-ext3-dxdir-2.5.40
 *  Original MD4 hash: (Modified version used)
 *    http://tools.ietf.org/html/rfc1320
 *  TEA Wikipedia article: (Modified version used)
 *    http://en.wikipedia.org/Tiny_Encryption_Algorithm
 */


class HTree {
public:
								HTree(Volume* volume, Inode* directory);
								~HTree();

			status_t			PrepareForHash();
			uint32				Hash(const char* name, uint8 length);

			status_t			Lookup(const char* name, 
									DirectoryIterator** directory);

	static	status_t			InitDir(Transaction& transaction, Inode* inode,
									Inode* parent);

private:
			status_t			_LookupInNode(uint32 hash, off_t& firstEntry,
									off_t& lastEntry, 
									uint32 remainingIndirects);
			
			uint32				_HashLegacy(const char* name, uint8 length);

	inline	uint32				_MD4F(uint32 x, uint32 y, uint32 z);
	inline	uint32				_MD4G(uint32 x, uint32 y, uint32 z);
	inline	uint32				_MD4H(uint32 x, uint32 y, uint32 z);
	inline	void				_MD4RotateVars(uint32& a, uint32& b, 
									uint32& c, uint32& d);
			void				_HalfMD4Transform(uint32 buffer[4],
									uint32 blocks[8]);
			uint32				_HashHalfMD4(const char* name, uint8 length);
			
			void				_TEATransform(uint32 buffer[4],
									uint32 blocks[4]);
			uint32				_HashTEA(const char* name, uint8 length);
			
			void				_PrepareBlocksForHash(const char* string,
									uint32 length, uint32* blocks, uint32 numBlocks);

	inline	status_t			_FallbackToLinearIteration(
									DirectoryIterator** iterator);

			bool				fIndexed;
			uint32				fBlockSize;
			Inode*				fDirectory;
			uint8				fHashVersion;
			uint32				fHashSeed[4];
			HTreeEntryIterator*	fRootEntry;
			ObjectDeleter<HTreeEntryIterator> fRootEntryDeleter;
};

#endif	// HTREE_H