/* $Id$
 * reactos MCB (map control block) functions emulation of libcaptive
 * Copyright (C) 2003 Jan Kratochvil <project-captive@jankratochvil.net>
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; exactly version 2 of June 1991 is required
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */


#include "config.h"

#include "reactos/ddk/fsfuncs.h"	/* self */
#include <glib/gmessages.h>
#include "reactos/ntos/types.h"	/* for VOID */
#include <glib/gtree.h>
#include <glib/ghash.h>
#include "reactos/ddk/exfuncs.h"	/* for ExInitializeFastMutex() */
#include "captive/macros.h"


/* We use only real 'mapping' runs; we do not store 'holes' to our GTree.
 */
struct run {
	LONGLONG Vbn_start;
	LONGLONG Vbn_end;	/* Vbn_start+SectorCount; that means +1 after the last sector */
	LONGLONG Lbn_start;	/* Lbn of 'Vbn_start' */
	};

struct Mcb_priv {
	GTree *gtree;	/* map (struct run *)->(struct run *) */
	};

static const struct run *run_compare_func_last_a_run;
static const struct run *run_compare_func_last_b_run;
static const struct run *run_compare_func_minus_a_run;	/* last run where we returned -1 */
static const struct run *run_compare_func_minus_b_run;
static const struct run *run_compare_func_plus_a_run;	/* last run where we returned +1 */
static const struct run *run_compare_func_plus_b_run;

static gint run_compare_func(const struct run *a_run,const struct run *b_run,gpointer user_data /* unused */)
{
gint r;

	g_return_val_if_fail(a_run!=NULL,0);
	g_return_val_if_fail(a_run->Vbn_end>a_run->Vbn_start,0);
	g_return_val_if_fail(b_run!=NULL,0);
	g_return_val_if_fail(b_run->Vbn_end>b_run->Vbn_start,0);

	run_compare_func_last_a_run=a_run;
	run_compare_func_last_b_run=b_run;

	if (1
			&& !(r=(a_run->Vbn_start>b_run->Vbn_start)-(a_run->Vbn_start<b_run->Vbn_start))
			&& !(r=(a_run->Vbn_end  >b_run->Vbn_end  )-(a_run->Vbn_end  <b_run->Vbn_end  )))
		r=0;

	if (r<0) {
		run_compare_func_minus_a_run=a_run;
		run_compare_func_minus_b_run=b_run;
		}
	else if (r>0) {
		run_compare_func_plus_a_run=a_run;
		run_compare_func_plus_b_run=b_run;
		}

	return r;
}

static void run_destroy_func(struct run *run)
{
	g_return_if_fail(run!=NULL);

	g_log(G_LOG_DOMAIN,G_LOG_LEVEL_DEBUG,"%s: run->Vbn_start=%lld,run->Vbn_end=%lld,run->Lbn_start=%lld",
			G_STRLOC,run->Vbn_start,run->Vbn_end,run->Lbn_start);

	g_free(run);
}

/* map (LARGE_MCB *)->(struct Mcb_priv *) */
static GHashTable *Mcb_hash;

static void Mcb_hash_init(void)
{
	if (Mcb_hash)
		return;
	Mcb_hash=g_hash_table_new(
			g_direct_hash,	/* key_compare_func */
			g_direct_equal);	/* key_compare_data */
}


/**
 * FsRtlInitializeLargeMcb:
 * @Mcb: Allocated memory to be initialized as #PLARGE_MCB.
 * %NULL value is forbidden.
 * @PoolType: Memory type to use for the items. Ignored by libcaptive.
 *
 * You must use this function to be able to pass @Mcb to any other
 * FsRtl*LargeMcb*() function.
 */
VOID FsRtlInitializeLargeMcb(IN PLARGE_MCB Mcb,IN POOL_TYPE PoolType)
{
struct Mcb_priv *Mcb_priv;

	g_return_if_fail(Mcb!=NULL);

	Mcb_hash_init();
	g_return_if_fail(NULL==g_hash_table_lookup(Mcb_hash,Mcb));

	ExInitializeFastMutex(&Mcb->FastMutex);
	Mcb->MaximumPairCount=0;
	Mcb->PairCount=0;
	Mcb->PoolType=PoolType;
	Mcb->Mapping=NULL;

	captive_new(Mcb_priv);
	Mcb_priv->gtree=g_tree_new_full(
			(GCompareDataFunc)run_compare_func,	/* key_compare_func */
			NULL,	/* key_compare_data */
			(GDestroyNotify)run_destroy_func,	/* key_destroy_func */
			NULL);	/* value_destroy_func */

	g_hash_table_insert(Mcb_hash,
			Mcb,	/* key */
			Mcb_priv);	/* value */
}


/**
 * FsRtlUninitializeLargeMcb:
 * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
 * %NULL value is forbidden.
 *
 * Frees all the resources associated with @Mcb.
 * You must not pass this pointer to any FsRtl*LargeMcb*() function afterwards.
 */
VOID FsRtlUninitializeLargeMcb(IN PLARGE_MCB Mcb)
{
struct Mcb_priv *Mcb_priv;
gboolean errbool;

	g_return_if_fail(Mcb!=NULL);

	Mcb_hash_init();
	Mcb_priv=g_hash_table_lookup(Mcb_hash,Mcb);
	g_return_if_fail(Mcb_priv!=NULL);

	errbool=g_hash_table_remove(Mcb_hash,Mcb);
	g_assert(errbool==TRUE);
	g_tree_destroy(Mcb_priv->gtree);
	g_free(Mcb_priv);
}


static gint run_intersect_compare_func(const struct run *haystack_run,const struct run *needle_run)
{
gint r;
struct run common_run;

	g_return_val_if_fail(haystack_run!=NULL,0);
	g_return_val_if_fail(haystack_run->Vbn_end>haystack_run->Vbn_start,0);
	g_return_val_if_fail(needle_run!=NULL,0);
	g_return_val_if_fail(needle_run->Vbn_end>needle_run->Vbn_start,0);

	common_run.Vbn_start=MAX(haystack_run->Vbn_start,needle_run->Vbn_start);
	common_run.Vbn_end  =MIN(haystack_run->Vbn_end  ,needle_run->Vbn_end  );

	if (common_run.Vbn_end>common_run.Vbn_start)
		return 0;
	r=run_compare_func(needle_run,haystack_run,
			NULL);	/* user_data; unused */
	g_assert(r!=0);	/* otherwise we would hit it by 'common_run' */
	return r;
}


/**
 * FsRtlRemoveLargeMcbEntry:
 * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
 * %NULL value is forbidden.
 * @Vbn: Starting virtual block number to specify the range to delete.
 * @SectorCount: Length of the range to delete.
 * Value less or equal to %0 is forbidden; FIXME: Is the reject of %0 W32 compliant?
 *
 * Deletes any possible @Mcb mappings in the given range @Vbn ... @Vbn+@SectorCount-1.
 * This call has no problems if no mappings exist there yet.
 */
VOID FsRtlRemoveLargeMcbEntry(IN PLARGE_MCB Mcb,IN LONGLONG Vbn,IN LONGLONG SectorCount)
{
struct Mcb_priv *Mcb_priv;
struct run needle_run,*haystack_run;

	g_return_if_fail(Mcb!=NULL);
	g_return_if_fail(Vbn>=0);
	g_return_if_fail(SectorCount>0);
	/* FIXME: We are unable to delete the absolutely last sector G_MAXINT64 by this implementation! */
	g_return_if_fail(Vbn+SectorCount>Vbn);

	g_log(G_LOG_DOMAIN,G_LOG_LEVEL_DEBUG,"%s: Mcb=%p,Vbn=%lld,SectorCount=%lld",G_STRLOC,Mcb,Vbn,SectorCount);

	Mcb_hash_init();
	Mcb_priv=g_hash_table_lookup(Mcb_hash,Mcb);
	g_return_if_fail(Mcb_priv!=NULL);

	needle_run.Vbn_start=Vbn;
	needle_run.Vbn_end=Vbn+SectorCount;

	/* adjust/destroy all intersecting ranges */
	while ((haystack_run=g_tree_search(Mcb_priv->gtree,(GCompareFunc)run_intersect_compare_func,&needle_run))) {
		/**/ if (haystack_run->Vbn_start<needle_run.Vbn_start) {
			g_assert(haystack_run->Vbn_end  >needle_run.Vbn_start);
			haystack_run->Vbn_end  =needle_run.Vbn_start;
			}
		else if (haystack_run->Vbn_end  >needle_run.Vbn_end  ) {
			g_assert(haystack_run->Vbn_start<needle_run.Vbn_end  );
			haystack_run->Vbn_start=needle_run.Vbn_end;
			}
		else {
			g_assert(needle_run.Vbn_start>=haystack_run->Vbn_start);
			g_assert(needle_run.Vbn_end  <=haystack_run->Vbn_end  );
			g_tree_remove(Mcb_priv->gtree,haystack_run);
			}
		}
}


/**
 * FsRtlAddLargeMcbEntry:
 * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
 * %NULL value is forbidden.
 * @Vbn: Starting virtual block number of the wished range.
 * @Lbn: Starting logical block number of the wished range.
 * @SectorCount: Length of the wished range.
 * Value less or equal to %0 is forbidden; FIXME: Is the reject of %0 W32 compliant?
 *
 * Adds the specified range @Vbn ... @Vbn+@SectorCount-1 to @Mcb.
 * Any mappings previously in this range are deleted first.
 *
 * Returns: %TRUE if successful.
 */
BOOLEAN FsRtlAddLargeMcbEntry(IN PLARGE_MCB Mcb,IN LONGLONG Vbn,IN LONGLONG Lbn,IN LONGLONG SectorCount)
{
struct Mcb_priv *Mcb_priv;
struct run *insert_run,current_run,needle_run,*lower_run,*higher_run;

	g_return_val_if_fail(Mcb!=NULL,FALSE);
	g_return_val_if_fail(Vbn>=0,FALSE);
	g_return_val_if_fail(SectorCount>0,FALSE);

	g_log(G_LOG_DOMAIN,G_LOG_LEVEL_DEBUG,"%s: Mcb=%p,Vbn=%lld,Lbn=%lld,SectorCount=%lld",G_STRLOC,Mcb,Vbn,Lbn,SectorCount);

	Mcb_hash_init();
	Mcb_priv=g_hash_table_lookup(Mcb_hash,Mcb);
	g_return_val_if_fail(Mcb_priv!=NULL,FALSE);

	/* clean any possible previous entries in our range */
	FsRtlRemoveLargeMcbEntry(Mcb,Vbn,SectorCount);

	/* initially we think we will be inserted as a separate run */
	current_run.Vbn_start=Vbn;
	current_run.Vbn_end  =Vbn+SectorCount;
	current_run.Lbn_start=Lbn;

	/* optionally merge with lower run */
	needle_run.Vbn_start=current_run.Vbn_start-1;
	needle_run.Vbn_end  =needle_run.Vbn_start+1;
	if ((lower_run=g_tree_search(Mcb_priv->gtree,(GCompareFunc)run_intersect_compare_func,&needle_run))) {
		g_assert(lower_run->Vbn_end==current_run.Vbn_start);
		current_run.Vbn_start=lower_run->Vbn_start;
		g_tree_remove(Mcb_priv->gtree,lower_run);
		}

	/* optionally merge with higher run */
	needle_run.Vbn_start=current_run.Vbn_end;
	needle_run.Vbn_end  =needle_run.Vbn_start+1;
	if ((higher_run=g_tree_search(Mcb_priv->gtree,(GCompareFunc)run_intersect_compare_func,&needle_run))) {
		g_assert(higher_run->Vbn_start==current_run.Vbn_end);
		current_run.Vbn_end=higher_run->Vbn_end;
		g_tree_remove(Mcb_priv->gtree,higher_run);
		}

	/* finally insert the resulting run */
	captive_new(insert_run);
	*insert_run=current_run;
	g_tree_insert(Mcb_priv->gtree,insert_run,insert_run);

	return TRUE;	/* success */
}


static const struct run static_run_below_0={
		Vbn_start:-1,	/* ignored */
		Vbn_end:   0,
		Lbn_start:-1,	/* ignored */
		};


struct FsRtlGetNextLargeMcbEntry_input {
	gboolean first;
	ULONG RunIndex_remaining;
	const struct run *run_found;
	const struct run *run_found_lower,*run_found_higher;
	};

static gboolean FsRtlGetNextLargeMcbEntry_traverse_func
		(struct run *run /* _key */,struct run *run_value,struct FsRtlGetNextLargeMcbEntry_input *input)
{
	g_return_val_if_fail(run!=NULL,TRUE);
	g_return_val_if_fail(run_value!=NULL,TRUE);
	g_return_val_if_fail(run==run_value,TRUE);
	g_return_val_if_fail(input!=NULL,TRUE);

	if (input->first) {
		/* Take care when we must emulate missing 'hole' run at start of our run list. */
		if (run->Vbn_start>0) {
			if (input->RunIndex_remaining==0) {
				input->run_found_lower=&static_run_below_0;
				input->run_found_higher=run;
				return TRUE;	/* stop the traversal */
				}
			/* If someone wants RunIndex #1 we are already on it. */
			input->RunIndex_remaining--;
			}
		input->first=FALSE;
		}

	if (input->RunIndex_remaining>0) {
		/* FIXME: performance: non-linear direct seek to the requested RunIndex */
		input->RunIndex_remaining--;
		if (input->RunIndex_remaining==0)
			input->run_found_lower=run;
		else
			input->RunIndex_remaining--;
		return FALSE;	/* continue the traversal */
		}

	if (input->run_found_lower)
		input->run_found_higher=run;
	else
		input->run_found=run;
	return TRUE;	/* stop the traversal */
}


/**
 * FsRtlGetNextLargeMcbEntry:
 * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
 * %NULL value is forbidden.
 * @RunIndex: Requested range index to retrieve.
 * @Vbn: Returns the starting virtual block number of the wished range.
 * %NULL pointer is forbidden.
 * @Lbn: Returns the starting logical block number of the wished range (or -1 if it is a hole).
 * %NULL pointer is forbidden.
 * @SectorCount: Returns the length of the wished range.
 * %NULL pointer is forbidden.
 * Value less or equal to %0 is forbidden; FIXME: Is the reject of %0 W32 compliant?
 *
 * Retrieves the parameters of the specified run with index @RunIndex.
 * 
 * Mapping %0 always starts at virtual block %0, either as 'hole' or as 'real' mapping.
 * libcaptive does not store 'hole' information to its #GTree.
 * Last run is always a 'real' run. 'hole' runs appear as mapping to constant @Lbn value %-1.
 *
 * Returns: %TRUE if successful.
 */
BOOLEAN FsRtlGetNextLargeMcbEntry
		(IN PLARGE_MCB Mcb,IN ULONG RunIndex,OUT PLONGLONG Vbn,OUT PLONGLONG Lbn,OUT PLONGLONG SectorCount)
{
struct Mcb_priv *Mcb_priv;
struct FsRtlGetNextLargeMcbEntry_input input;

	g_return_val_if_fail(Mcb!=NULL,FALSE);
	g_return_val_if_fail(Vbn!=NULL,FALSE);
	g_return_val_if_fail(Lbn!=NULL,FALSE);
	g_return_val_if_fail(SectorCount!=NULL,FALSE);

	Mcb_hash_init();
	Mcb_priv=g_hash_table_lookup(Mcb_hash,Mcb);
	g_return_val_if_fail(Mcb_priv!=NULL,FALSE);

	input.first=TRUE;
	input.RunIndex_remaining=RunIndex;
	input.run_found=NULL;
	input.run_found_lower=NULL;
	input.run_found_higher=NULL;
	g_tree_foreach(Mcb_priv->gtree,(GTraverseFunc)FsRtlGetNextLargeMcbEntry_traverse_func,&input);

	if (input.run_found) {
		g_assert(input.run_found_lower ==NULL);
		g_assert(input.run_found_higher==NULL);
		*Vbn        =input.run_found->Vbn_start;
		*Lbn        =input.run_found->Lbn_start;
		*SectorCount=input.run_found->Vbn_end-input.run_found->Vbn_start;
		return TRUE;
		}

	if (input.run_found_lower) {
		g_assert(input.run_found_higher!=NULL);
		*Vbn        =input.run_found_lower->Vbn_end;
		*Lbn        =-1;
		*SectorCount=input.run_found_higher->Vbn_start-input.run_found_lower->Vbn_end;
		return TRUE;
		}

	g_assert(input.run_found_higher==NULL);
	return FALSE;
}


struct FsRtlLookupLargeMcbEntry_input {
	gboolean first;
	LONGLONG Vbn;
	ULONG RunIndex;
	const struct run *run_found;
	const struct run *run_found_lower,*run_found_higher;
	};

static gboolean FsRtlLookupLargeMcbEntry_traverse_func
		(struct run *run /* _key */,struct run *run_value,struct FsRtlLookupLargeMcbEntry_input *input)
{
	g_return_val_if_fail(run!=NULL,TRUE);
	g_return_val_if_fail(run_value!=NULL,TRUE);
	g_return_val_if_fail(run==run_value,TRUE);
	g_return_val_if_fail(input!=NULL,TRUE);

	if (input->first) {
		/* Take care when we must emulate missing 'hole' run at start of our run list. */
		if (run->Vbn_start>0) {
			input->RunIndex+=1;
			input->run_found_lower=&static_run_below_0;
			}
		input->first=FALSE;
		}

	if (run->Vbn_start<=input->Vbn && input->Vbn<run->Vbn_end) {
		input->run_found=run;
		input->run_found_lower=NULL;
		return TRUE;	/* stop the traversal; hit */
		}
	if (run->Vbn_end<=input->Vbn) {
		input->run_found_lower=run;
		input->RunIndex+=2;
		return FALSE;	/* continue the traversal; not yet crossed by the run */
		}
	if (input->Vbn<run->Vbn_start) {
		input->run_found_higher=run;
		input->RunIndex+=1;
		return TRUE;	/* stop the traversal; the run skipped us */
		}
	g_assert_not_reached();
	return TRUE;	/* stop the traversal */
}


/**
 * FsRtlLookupLargeMcbEntry:
 * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
 * %NULL value is forbidden.
 * @Vbn: Starting virtual block number of the requested sector.
 * @Lbn: Returns the logical block number corresponding to @Vbn (or -1 if it is a hole).
 * %NULL value is permitted.
 * @SectorCountFromLbn: Returns the number of sectors after @Vbn in the mapping found.
 * FIXME: 'after' means including current 'Lbn' or without it?
 * %NULL value is permitted.
 * @StartingLbn: Returns the first logical block number of the mapping found (or -1 if it is a hole).
 * %NULL value is permitted.
 * @SectorCountFromStartingLbn: Returns total length in blocks of the mapping found.
 * %NULL value is permitted.
 * @Index: Returns the range index of the mapping found.
 * %NULL value is permitted.
 *
 * Retrieves the information about the requested virtual block number @Vbn
 * and its mapping (either real 'mapping' or the 'hole').
 * 
 * Mapping %0 always starts at virtual block %0, either as 'hole' or as 'real' mapping.
 * libcaptive does not store 'hole' information to its #GTree.
 * Last run is always a 'real' run. 'hole' runs appear as mapping to constant @Lbn value %-1.
 *
 * Returns: %TRUE if successful.
 */
BOOLEAN FsRtlLookupLargeMcbEntry(IN PLARGE_MCB Mcb,IN LONGLONG Vbn,
		OUT PLONGLONG Lbn OPTIONAL,
		OUT PLONGLONG SectorCountFromLbn OPTIONAL,
		OUT PLONGLONG StartingLbn OPTIONAL,
		OUT PLONGLONG SectorCountFromStartingLbn OPTIONAL,
		OUT PULONG Index OPTIONAL)
{
struct Mcb_priv *Mcb_priv;
struct FsRtlLookupLargeMcbEntry_input input;

	g_return_val_if_fail(Mcb!=NULL,FALSE);
	g_return_val_if_fail(Vbn>=0,FALSE);

	Mcb_hash_init();
	Mcb_priv=g_hash_table_lookup(Mcb_hash,Mcb);
	g_return_val_if_fail(Mcb_priv!=NULL,FALSE);

	input.first=TRUE;
	input.Vbn=Vbn;
	input.RunIndex=0;
	input.run_found=NULL;
	input.run_found_lower=NULL;
	input.run_found_higher=NULL;
	g_tree_foreach(Mcb_priv->gtree,(GTraverseFunc)FsRtlLookupLargeMcbEntry_traverse_func,&input);

	if (input.run_found) {	/* hit the mapping */
		g_assert(input.run_found_lower ==NULL);
		g_assert(input.run_found_higher==NULL);
		if (Lbn)
			*Lbn=input.run_found->Lbn_start+(Vbn-input.run_found->Vbn_start);
		if (SectorCountFromLbn)	/* FIXME: 'after' means including current 'Lbn' or without it? */
			*SectorCountFromLbn=input.run_found->Vbn_end-Vbn;
		if (StartingLbn)
			*StartingLbn=input.run_found->Lbn_start;
		if (SectorCountFromStartingLbn)
			*SectorCountFromStartingLbn=input.run_found->Vbn_end-input.run_found->Vbn_start;
		if (Index)
			*Index=input.RunIndex;
		return TRUE;
		}

	if (input.run_found_higher) {	/* search for hole */
		g_assert(input.run_found_lower!=NULL);
		if (Lbn)
			*Lbn=-1;
		if (SectorCountFromLbn)	/* FIXME: 'after' means including current 'Lbn' or without it? */
			*SectorCountFromLbn=input.run_found_higher->Vbn_start-Vbn;
		if (StartingLbn)
			*StartingLbn=-1;
		if (SectorCountFromStartingLbn)
			*SectorCountFromStartingLbn=input.run_found_higher->Vbn_start-input.run_found_lower->Vbn_end;
		if (Index)
			*Index=input.RunIndex;
		return TRUE;
		}

	/* We may have some 'input.run_found_lower'. */
	return FALSE;
}


static BOOLEAN FsRtlLookupLastLargeMcbEntryAndIndex_internal
		(IN PLARGE_MCB Mcb,OUT PLONGLONG Vbn,OUT PLONGLONG Lbn,OUT PULONG Index OPTIONAL)
{
struct Mcb_priv *Mcb_priv;
const struct run needle_run_top={
		Vbn_start:G_MAXINT64-1,
		Vbn_end:G_MAXINT64,
		Lbn_start:-1,	/* ignored*/
		};
const struct run *found_run;

	g_return_val_if_fail(Mcb!=NULL,FALSE);
	g_return_val_if_fail(Vbn!=NULL,FALSE);
	g_return_val_if_fail(Lbn!=NULL,FALSE);

	Mcb_hash_init();
	Mcb_priv=g_hash_table_lookup(Mcb_hash,Mcb);
	g_return_val_if_fail(Mcb_priv!=NULL,FALSE);

	run_compare_func_last_a_run=NULL;
	run_compare_func_last_b_run=NULL;
	found_run=g_tree_lookup(Mcb_priv->gtree,&needle_run_top);
	g_assert(found_run==NULL);

	if (run_compare_func_last_a_run==NULL) {
		g_assert(run_compare_func_last_b_run==NULL);
		g_assert(g_tree_nnodes(Mcb_priv->gtree)==0);

		*Vbn=-1;
		*Lbn=-1;
		if (Index)
			*Index=0;
		return FALSE;
		}
	g_assert(run_compare_func_last_a_run!=&needle_run_top);
	g_assert(run_compare_func_last_b_run==&needle_run_top);

	*Vbn=run_compare_func_last_a_run->Vbn_end-1;
	*Lbn=run_compare_func_last_a_run->Lbn_start
			+((run_compare_func_last_a_run->Vbn_end-1)-run_compare_func_last_a_run->Vbn_start);
	if (Index) {
ULONG runs=FsRtlNumberOfRunsInLargeMcb(Mcb);

		g_assert(runs>0);	/* There must be some runs if we found _something_. */
		*Index=runs-1;
		}
	return TRUE;
}


/**
 * FsRtlLookupLastLargeMcbEntryAndIndex:
 * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
 * %NULL value is forbidden.
 * @Vbn: Returns the virtual block number of the last mapped sector.
 * %NULL pointer is forbidden.
 * @Lbn: Returns the logical block number of the last mapped sector.
 * %NULL pointer is forbidden.
 * @Index: Returns the RunIndex of the last mapped sector.
 * %NULL pointer is forbidden.
 *
 * Retrieves the mapping of the ever last sector mapped by @Mcb.
 * FIXME: W32 doc says the returned @Lbn may get value %-1 but such 'hole' is not
 * a real mapping - why not to return the previous real mapping instead?
 * How can be some trailing 'hole's present?
 *
 * Returns: %TRUE if successful. %FALSE if @Mcb is empty.
 */
BOOLEAN FsRtlLookupLastLargeMcbEntryAndIndex
		(IN PLARGE_MCB Mcb,OUT PLONGLONG Vbn,OUT PLONGLONG Lbn,OUT PULONG Index)
{
	g_return_val_if_fail(Mcb!=NULL,FALSE);
	g_return_val_if_fail(Vbn!=NULL,FALSE);
	g_return_val_if_fail(Lbn!=NULL,FALSE);
	g_return_val_if_fail(Index!=NULL,FALSE);

	return FsRtlLookupLastLargeMcbEntryAndIndex_internal(Mcb,Vbn,Lbn,Index);
}


/**
 * FsRtlLookupLastLargeMcbEntry:
 * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
 * %NULL value is forbidden.
 * @Vbn: Returns the virtual block number of the last mapped sector.
 * %NULL pointer is forbidden.
 * @Lbn: Returns the logical block number of the last mapped sector.
 * %NULL pointer is forbidden.
 *
 * Retrieves the mapping of the ever last sector mapped by @Mcb.
 * FIXME: W32 doc says the returned @Lbn may get value %-1 but such 'hole' is not
 * a real mapping - why not to return the previous real mapping instead?
 * How can be some trailing 'hole's present?
 *
 * Returns: %TRUE if successful. %FALSE if @Mcb is empty.
 */
BOOLEAN FsRtlLookupLastLargeMcbEntry(IN PLARGE_MCB Mcb,OUT PLONGLONG Vbn,OUT PLONGLONG Lbn)
{
	g_return_val_if_fail(Mcb!=NULL,FALSE);
	g_return_val_if_fail(Vbn!=NULL,FALSE);
	g_return_val_if_fail(Lbn!=NULL,FALSE);

	return FsRtlLookupLastLargeMcbEntryAndIndex_internal(Mcb,Vbn,Lbn,
			NULL);	/* Index */
}


/**
 * FsRtlNumberOfRunsInLargeMcb:
 * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
 * %NULL value is forbidden.
 *
 * Counts the number of runs mapped by @Mcb.
 * 
 * Mapping %0 always starts at virtual block %0, either as 'hole' or as 'real' mapping.
 * libcaptive does not store 'hole' information to its #GTree.
 * Last run is always a 'real' run. 'hole' runs appear as mapping to constant @Lbn value %-1.
 *
 * Returns: The sum of 'real' and 'hole' runs in @Mcb.
 * Returns value %0 if @Mcb is empty.
 * Returns odd number iff the mapping has 'real' virtual block %0.
 */
ULONG FsRtlNumberOfRunsInLargeMcb(IN PLARGE_MCB Mcb)
{
struct Mcb_priv *Mcb_priv;
gint nodes;
LONGLONG Lbn_at_Vbn_0;

	g_return_val_if_fail(Mcb!=NULL,0);

	Mcb_hash_init();
	Mcb_priv=g_hash_table_lookup(Mcb_hash,Mcb);
	g_return_val_if_fail(Mcb_priv!=NULL,0);

	nodes=g_tree_nnodes(Mcb_priv->gtree);
	if (!nodes)
		return 0;

	Lbn_at_Vbn_0=-1;
	FsRtlLookupLargeMcbEntry(Mcb,
			0,	/* Vbn */
			&Lbn_at_Vbn_0,	/* Lbn */
			NULL,NULL,NULL,NULL);	/* 4 output arguments - not interested in them */

	/* Return the number of 'real' and 'hole' runs.
	 * If we do not have sector 0 as 'real' emulate a 'hole' there.
	 */
	return nodes*2 - (Lbn_at_Vbn_0!=-1 ? 1 : 0);	/* include holes as runs */
}


struct FsRtlSplitLargeMcb_input {
	LONGLONG Vbn;
	LONGLONG Amount;
	struct Mcb_priv *Mcb_priv;
	struct run *insert_lower_run;	/* 'run' to insert after g_tree_foreach() finishes */
	};

static gboolean FsRtlSplitLargeMcb_traverse_func
		(struct run *run /* _key */,struct run *run_value,struct FsRtlSplitLargeMcb_input *input)
{
	g_return_val_if_fail(run!=NULL,TRUE);
	g_return_val_if_fail(run_value!=NULL,TRUE);
	g_return_val_if_fail(run==run_value,TRUE);
	g_return_val_if_fail(input!=NULL,TRUE);

	/* unaffected run? */
	/* FIXME: performance: effective skip of all 'lower' runs without traversing them */
	if (input->Vbn>=run->Vbn_end)
		return FALSE;	/* continue the traversal */

	/* crossing run to be split?
	 * 'lower_run' is created on the original place; just shortened.
	 * current 'run' is shifted up later
	 */
	if (input->Vbn<run->Vbn_end) {
struct run *lower_run;
		
		captive_new(lower_run);
		*lower_run=*run;
		lower_run->Vbn_end=input->Vbn;
		/* FIXME: shift 'run->Lbn_start' ? */
		run->Vbn_start=input->Vbn;

		input->insert_lower_run=lower_run;
		}

	/* Shift the current 'run'.
	 * Ordering is not changed in GTree so I hope I do not need to reinsert it.
	 */
	run->Vbn_start+=input->Amount;
	g_assert(run->Vbn_end+input->Amount>run->Vbn_end);	/* overflow? */
	run->Vbn_end+=input->Amount;
	/* FIXME: shift 'run->Lbn_start' ? */

	return FALSE;	/* continue the traversal */
}


/**
 * FsRtlSplitLargeMcb:
 * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
 * %NULL value is forbidden.
 * @Vbn: First virtual block number of blocks to shift up.
 * @Amount: The amount of sectors to shift the blocks up by.
 * Value less or equal to %0 is forbidden; FIXME: Is the reject of %0 W32 compliant?
 *
 * Takes the range of existing @Vbn..infinity 'real' block runs and shifts their
 * virtual block numbers up by @Amount. Any possible 'real' run crossed by @Vbn
 * threshold value gets split with the 'hole' of size @Amount blocks.
 *
 * FIXME: W32 doc does not say if logical block number should be also shifted.
 * libcaptive does not touch logical block numbers.
 *
 * Returns: %TRUE if we crossed some 'real' run and we needed to create new 'hole'.
 * We still may map a lot of 'real' runs and return %FALSE if no such run will be hit by @Vbn directly.
 */
BOOLEAN FsRtlSplitLargeMcb(IN PLARGE_MCB Mcb,IN LONGLONG Vbn,IN LONGLONG Amount)
{
struct Mcb_priv *Mcb_priv;
struct FsRtlSplitLargeMcb_input input;

	g_return_val_if_fail(Mcb!=NULL,FALSE);
	g_return_val_if_fail(Vbn>=0,FALSE);
	g_return_val_if_fail(Amount>0,FALSE);

	g_log(G_LOG_DOMAIN,G_LOG_LEVEL_DEBUG,"%s: Mcb=%p,Vbn=%lld,Amount=%lld",G_STRLOC,Mcb,Vbn,Amount);

	Mcb_hash_init();
	Mcb_priv=g_hash_table_lookup(Mcb_hash,Mcb);
	g_return_val_if_fail(Mcb_priv!=NULL,FALSE);

	input.Vbn=Vbn;
	input.Amount=Amount;
	input.insert_lower_run=NULL;
	input.Mcb_priv=Mcb_priv;
	g_tree_foreach(Mcb_priv->gtree,(GTraverseFunc)FsRtlSplitLargeMcb_traverse_func,&input);

	if (input.insert_lower_run)
		g_tree_insert(input.Mcb_priv->gtree,input.insert_lower_run,input.insert_lower_run);

	return (input.insert_lower_run!=NULL);	/* the hole was successfuly created? */
}


/**
 * FsRtlTruncateLargeMcb:
 * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
 * %NULL value is forbidden.
 * @Vbn: First virtual block number of blocks to delete.
 *
 * Deletes the mapping from @Vbn upwards. If no such blocks exist this function
 * does a safe NOP.
 */
VOID FsRtlTruncateLargeMcb(IN PLARGE_MCB Mcb,IN LONGLONG Vbn)
{
	g_return_if_fail(Mcb!=NULL);
	g_return_if_fail(Vbn>=0);

	g_log(G_LOG_DOMAIN,G_LOG_LEVEL_DEBUG,"%s: Mcb=%p,Vbn=%lld",G_STRLOC,Mcb,Vbn);

	FsRtlRemoveLargeMcbEntry(Mcb,Vbn,G_MAXINT64-Vbn+1);
}