///////////////////////////////////////////////////////////////////////////////
//                                                         
// CegoAVLIndexManager.cc
// -------------------
// Cego index manager class implementation
//                                                         
// Design and Implementation by Bjoern Lemke               
//         
// (C)opyright 2000-2013 Bjoern Lemke
//
// 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; either version 2, or (at your option)
// any later version.
// 
// 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; see the file COPYING.  If not, write to
// the Free Software Foundation, 59 Temple Place - Suite 330,
// Boston, MA 02111-1307, USA.
//
// IMPLEMENTATION MODULE
//
// Class: CegoAVLIndexManager
// 
// Description: 
//
// Status: QG-2.6
//
///////////////////////////////////////////////////////////////////////////////

// base includes
#include <lfc/Exception.h>

// cego includes
#include "CegoAVLIndexManager.h"
#include "CegoLockHandler.h"
#include "CegoAVLIndexEntry.h"
#include "CegoTupleState.h"

#include <string.h>
#include <stdlib.h>

CegoAVLIndexManager::CegoAVLIndexManager(CegoTableManager *pTM)
{
    _pLogger = pTM->getDBMng();
    _modId = pTM->getDBMng()->getModId("CegoAVLIndexManager");
    _pTM = pTM;
}

CegoAVLIndexManager::~CegoAVLIndexManager()
{
}

void CegoAVLIndexManager::insertNativeIndexTable(CegoTableObject& ioe, 
					      const CegoDataPointer& sysEntry, 
					      const CegoDataPointer& dp,
					      char* idxPtr, 
					      int idxLen, 
					      int tid, 
					      bool insertAtLastPage,
					      CegoDataPointer& ritp)
{
    // get entry pointer

    int tabSetId = ioe.getTabSetId();
    Chain indexName = ioe.getName();
    Chain tabName = ioe.getTabName();

    CegoObject::ObjectType idxType = ioe.getType();
    ListT<CegoField> schema = ioe.getSchema(); 

    CegoObjectCursor* pC = _pTM->getObjectCursor(tabSetId, tabName, indexName, idxType);

    if ( ! pC )
    {
	Chain msg = "Cannot get cursor for <" + indexName  + ">";
	throw Exception(EXLOC, msg);	
    } 
    
    CegoDataPointer rdp;
    char* p;
    int len;

    p = (char*)pC->getFirst(len, rdp);
    
    // root datapointer must not be zero
    if ( p == 0)
    {
	pC->abort();
	delete pC;	
	throw Exception(EXLOC, "Missing Index Anchor");
    }

    CegoAVLIndexEntry base;
    base.setPtr(p, len);

    CegoDataPointer nil;

    // is this the first entry ?
    if ( base.getRightBranch() == nil )
    {	
	CegoAVLIndexEntry nie(tid); 
	
	nie.initEntry(dp, idxPtr, idxLen);
	nie.setParent(rdp);
	nie.setHeight(1);
	
	CegoDataPointer dp;
 
	try {

	    CegoDataPointer nil;
	    if ( sysEntry == nil )
	    {
		dp = _pTM->insertData(ioe, (char*)nie.getPtr(), nie.getLen(), insertAtLastPage);
	    }
	    else
	    {
		dp = _pTM->insertData(sysEntry, ioe, (char*)nie.getPtr(), nie.getLen(), insertAtLastPage);
	    }
	    
	}
	catch ( Exception e )
	{
	    pC->abort();
	    delete pC;
	    throw Exception(EXLOC, "Cannot insert index", e);
	}
	
	base.setRightBranch(dp);
	
	ritp = rdp; // *pTP;

	pC->abort();
	delete pC;
	
    }
    else
    {
	ritp = rdp; // base.getRightBranch();
    
	pC->abort();
	delete pC;

	bool isUnique = false;
	
	if ( idxType == CegoObject::UINDEX || idxType == CegoObject::PINDEX )
	    isUnique = true;
	
	insertIndexTable(ioe, sysEntry, ritp, isUnique, dp, idxPtr, idxLen, tid, insertAtLastPage);

    }
}

void CegoAVLIndexManager::insertIndexTable(CegoTableObject& ioe,
					const CegoDataPointer& sysEntry,
					const CegoDataPointer& ritp, 
					bool isUnique, 
					const CegoDataPointer& dp, 
					char* idxPtr, 
					int idxLen, 
					int tid,
					bool insertAtLastPage, 
					bool allowWrite)
{

    int tabSetId = ioe.getTabSetId();
    ListT<CegoField> schema = ioe.getSchema();
 
    char* p;
    int len;

    CegoBufferPool::FixMode fixMode;

    if ( allowWrite )
	fixMode = CegoBufferPool::NOSYNC;
    else
	fixMode = CegoBufferPool::SYNC;

    unsigned long lockId = _pTM->claimDataPtr(tabSetId, CegoLockHandler::WRITE, fixMode, ritp, p, len);

    CegoAVLIndexEntry base;
    base.setPtr(p, len);

    CegoDataPointer itp = base.getRightBranch();

    CegoBufferPage pageIE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, itp, p, len);

    CegoDataPointer ptp;
    
    bool inserted = false;
    bool treatBalance = true;

    CegoAVLIndexEntry ie;

    int level = 0;
    
    while ( ! inserted )
    {
	
	ie.setPtr(p, len);
	bool leftBranch = false;
	
	TupleOrder v = compIndexValue(schema, idxPtr, ie.getIdxPtr());

	if ( v == EQU_NULL )
	{
	    if (  ALLOW_UNIQUE_NULL == true )
		v = LT;
	    else
		v = EQU;
	}

	if ( v == LT || ( v == EQU && ! isUnique ) )
	{
	    leftBranch = true;
	    ptp = itp;
	    itp = ie.getLeftBranch();
	}
	else if ( v == GT )
	{
	    leftBranch = false;
	    ptp = itp;	    
	    itp = ie.getRightBranch();
	}
	else 
	{
	    // key maybe already exists
 
	    if ( tid != 0 )
	    {
	       		
		// the key may be duplictate if an update operation occurs ( forced transaction )
		// in this case we allow double entries ( cleanup by commit )

		unsigned long dataLock;
		dataLock = _pTM->claimDataPtr(tabSetId, CegoLockHandler::READ, fixMode, ie.getData(), p, len);
		
		// skipping tid
		int dataTid = *(int*)p;
		int tastep;
		CegoTupleState ts;

		char* ptastep = p + sizeof(int);
		memcpy(&tastep, ptastep, sizeof(int));
		
		char* pts = p + sizeof(int) + sizeof(int);
		memcpy(&ts, pts, sizeof(CegoTupleState));

		_pTM->releaseDataPtr(dataLock, false);
	    
		if (tid == dataTid && ( ts == DELETED || ts == OBSOLETE ))
		{
		    leftBranch = true;
		    ptp = itp;
		    itp = ie.getLeftBranch();		    
		}
		else
		{
		    if (lockId)
			_pTM->releaseDataPtr(lockId, false);
		    
		    _pTM->releaseDataPtrUnlocked(pageIE, false);

		    throw Exception(EXLOC, Chain("Duplicate index key on unique index ") + ioe.getName() );
		    		    
		}
	    }	  
	    else
	    {
		if (lockId)
		    _pTM->releaseDataPtr(lockId, false);
		_pTM->releaseDataPtrUnlocked(pageIE, false);
		
		throw Exception(EXLOC, Chain("Duplicate index key on unique index ") + ioe.getName() );
	    }
	}  
	
	level++;
	
	if (itp.getOffset() == 0)
	{

	    CegoAVLIndexEntry nie;
	    nie.initEntry(dp, idxPtr, idxLen);
	    nie.setParent(ptp);
	    nie.setHeight(1);
	    
	    CegoDataPointer dp;
	    try {

		CegoDataPointer nil;
		if ( sysEntry == nil )
		{
		    dp = _pTM->insertData(ioe, (char*)nie.getPtr(), nie.getLen(), insertAtLastPage, allowWrite);
		}
		else
		{
		    dp = _pTM->insertData(sysEntry, ioe, (char*)nie.getPtr(), nie.getLen(), insertAtLastPage, allowWrite);
		}
		
	    }
	    catch ( Exception e )
	    {
		
		_pTM->releaseDataPtrUnlocked(pageIE, false);
		if (lockId)
		    _pTM->releaseDataPtr(lockId, false);

		throw e;
	    }
	    
	    inserted = true;
	    
	    if (leftBranch)
	    {

		ie.setLeftBranch(dp);
		if (ie.getHeight() == 1 )
		{
		    ie.setHeight(2);
		    treatBalance=true;
		}
		else
		{
		    treatBalance=false;
		}
	    }
	    else
	    {

		ie.setRightBranch(dp);
		
		if (ie.getHeight() == 1)
		{
		    ie.setHeight(2);
		    treatBalance=true;
		}
		else
		{
		    treatBalance=false;
		}
	    }   
	}
	else
	{
	    if ( pageIE.isFixed() )
	    _pTM->releaseDataPtrUnlocked(pageIE, true);
	    pageIE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, itp, p, len);

	}
    }
    
     if (level ==  1 )
     {
	 // no balance on tree level 1
	if (lockId)
	    _pTM->releaseDataPtr(lockId, true);
	if (pageIE.isFixed())
	    _pTM->releaseDataPtrUnlocked(pageIE, true);
	
	return;
     }
     
    // skip back
    itp = ptp;
    ptp = ie.getParent();

    CegoBufferPage pagePE;

    pagePE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len);

    CegoAVLIndexEntry pe;       
    pe.setPtr(p, len);

    while ( treatBalance && level > 1)
    {
	char leftHeight, rightHeight;
	getSubTreeHeight(tabSetId, fixMode, pe, leftHeight, rightHeight);

	if (pe.getRightBranch() == itp)	    
	{			    
	    if ( rightHeight - leftHeight == 1 ) 
	    {		
		pe.setHeight(rightHeight + 1);
		
		if ( pageIE.isFixed() )
		{		   
		    _pTM->releaseDataPtrUnlocked(pageIE, true);
		}

		ie = pe;
		pageIE = pagePE;
		itp = ptp;

		ptp = ie.getParent();
		
		if (ptp.getOffset())
		{   
		    pagePE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len);
		    pe.setPtr(p, len);
		}
	    }
	    else if (leftHeight == rightHeight)
	    {
		if ( leftHeight != pe.getHeight() )
		{
		    pe.setHeight(leftHeight + 1);
		}
		else
		{	    
		    treatBalance = false;
		}
	    }
	    else // if (leftHeight < rightHeight)
	    {		
		char subLeftHeight, subRightHeight;
		getSubTreeHeight(tabSetId, fixMode, ie, subLeftHeight, subRightHeight);

		if (subLeftHeight < subRightHeight)
		{		    
		    rotateRR(tabSetId, ptp, fixMode);		       
		}
		else
		{
		    rotateRL(tabSetId, ptp, fixMode);		       			
		}
		treatBalance = false;
	    }
	} 
	else 
	{	    
	    if ( leftHeight - rightHeight == 1 )
	    {
		pe.setHeight(leftHeight + 1);

		if ( pageIE.isFixed() )
		{
		    _pTM->releaseDataPtrUnlocked(pageIE, true);
		}

		pageIE = pagePE;
		ie = pe;
		itp = ptp;

		ptp = ie.getParent();

		if (ptp.getOffset())
		{
		    pagePE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len);
		    pe.setPtr(p, len);    
		}
	    }
	    else if ( leftHeight == rightHeight )
	    {
		if ( leftHeight != pe.getHeight() )
		{		    
		    pe.setHeight(leftHeight + 1);
		}
		else
		{
		    treatBalance = false;
		}
	    }
	    else // if ( leftHeight > rightHeight )
	    {		
		char subLeftHeight, subRightHeight;
		getSubTreeHeight(tabSetId, fixMode, ie, subLeftHeight, subRightHeight);
	
		if (subLeftHeight > subRightHeight)
		{		    
		    rotateLL(tabSetId, ptp, fixMode);		  
		}
		else
		{
		    rotateLR(tabSetId, ptp, fixMode);
		}
		treatBalance = false;
	    }
	}
	level--;
    }

    if ( pagePE.isFixed() )
	_pTM->releaseDataPtrUnlocked(pagePE, true);
    if ( pageIE.isFixed() )
	_pTM->releaseDataPtrUnlocked(pageIE, true);
    if (lockId)
	_pTM->releaseDataPtr(lockId, true);

}

void CegoAVLIndexManager::getSubTreeHeight(int tabSetId, CegoBufferPool::FixMode fixMode, const CegoAVLIndexEntry& pe, char& leftHeight, char& rightHeight)
{
    char* p;
    int len;
    CegoDataPointer nil;
    
    CegoDataPointer ldp = pe.getLeftBranch();
    if ( ldp == nil )
    {
	leftHeight=0;
    }
    else
    {
	CegoBufferPage pageLE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ldp, p, len);
	CegoAVLIndexEntry li;       
	li.setPtr(p, len);
	leftHeight = li.getHeight();
	if ( pageLE.isFixed() )
	    _pTM->releaseDataPtrUnlocked(pageLE, false);
    }
    
    CegoDataPointer rdp = pe.getRightBranch();
    if ( rdp == nil )
    {
	rightHeight=0;
    }
    else
    {
    
	CegoBufferPage pageRE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, rdp, p, len);
	CegoAVLIndexEntry ri;       
	ri.setPtr(p, len);
	rightHeight = ri.getHeight();
	if ( pageRE.isFixed() )
	    _pTM->releaseDataPtrUnlocked(pageRE, false);
    }
    return;
}    

void CegoAVLIndexManager::deleteIndexTable(int tabSetId, const Chain& tableName, CegoObject::ObjectType tabType, const Chain& indexName, CegoObject::ObjectType idxType, const ListT<CegoField>& schema, const CegoDataPointer& ddp, char* idxPtr, int idxLen, bool allowWrite)
{    

    CegoBufferPool::FixMode fixMode;

    if ( allowWrite )
	fixMode = CegoBufferPool::NOSYNC;
    else
	fixMode = CegoBufferPool::SYNC;

    
    ///////// get entry pointer //////////////
        
    CegoObjectCursor* pC = _pTM->getObjectCursor(tabSetId, tableName, indexName, idxType);

    if ( ! pC )
    {
	Chain msg = "Cannot get cursor for index <" + indexName  + ">";
	throw Exception(EXLOC, msg);	
    } 

    CegoDataPointer rdp;
    char* p;
    int len;
    p = (char*)pC->getFirst(len, rdp);
    
    if ( p == 0)
    {
	throw Exception(EXLOC, "Missing index anchor for index <" + indexName  + ">");
    }
    
    pC->abort();
    delete pC;

    /////////////////////////////////////////

    CegoDataPointer ptp = rdp;
    unsigned long rootLock = _pTM->claimDataPtr(tabSetId, CegoLockHandler::WRITE, fixMode,  ptp, p, len);

    // CegoTableObject ioe, toe;
    
    // getObject(tabSetId, tableName, tabType, toe);
    // getObject(tabSetId, indexName, idxType, ioe);

    CegoAVLIndexEntry ie;
    ie.setPtr(p, len);    
    
    CegoDataPointer  itp;
    itp = ie.getRightBranch();
        
    CegoBufferPage pageIE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, itp, p, len);  

    bool entryFound = false;

    bool moreIndex = true;

    CegoDataPointer nil;

    //////////////////////////////////
    // step one : found index entry //
    //////////////////////////////////

    while ( ! entryFound && moreIndex )
    {
	ie.setPtr(p, len);
	bool leftBranch = false;
	
	TupleOrder v = compIndexValue(schema, idxPtr, ie.getIdxPtr());

	if ( v == LT )
	{
	    leftBranch = true;
	    ptp = itp;
	    itp = ie.getLeftBranch();
	}
	else if ( v == GT )
	{
	    leftBranch = false;
	    ptp = itp;	    
	    itp = ie.getRightBranch();
	}
	else
	{
	    if ( ie.getData() == ddp )
	    {
		entryFound = true;
	    }
	    else
	    {
		itp = searchDataPointer(tabSetId, ddp, itp, fixMode );
		// we still must set up ptp explicit 
		if ( itp != nil ) 
		{
		    CegoBufferPage bp;
		    bp = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, itp, p, len);
		    ie.setPtr(p, len);
		    ptp = ie.getParent();
		    if ( bp.isFixed() )
			_pTM->releaseDataPtrUnlocked(bp, false);
		}
	    }
	}
	if ( itp == nil )
	{
	    moreIndex = false;
	}
        
	if ( ! entryFound && moreIndex )
	{
	
	    if (pageIE.isFixed() )
		_pTM->releaseDataPtrUnlocked(pageIE, false);
	    pageIE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, itp, p, len);
	    // cout << "claimed ptr " << itp << endl;
	}
    }
        
    //////////////////////////////////////////////////////////////////////////////
    // step two : delete index entry and perform balancing on node delete level //
    //////////////////////////////////////////////////////////////////////////////

    try 
    {
	if ( entryFound )
	{
	    if ( ie.getLeftBranch() == nil && ie.getRightBranch() == nil )
	    {
		
		// cout << "Index Delete : case I " << endl;
		
		CegoAVLIndexEntry pie;
		
		CegoBufferPage pagePE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len);
		pie.setPtr(p, len);	  	
		
		if (pie.getLeftBranch() == itp)
		{
		    // cout << "Index Delete : case Ia " << endl;
		    
		    pie.setLeftBranch(nil);

		    // balance just if not root node
		    if ( pie.getData() != nil )
		    {
			char leftHeight, rightHeight;
			getSubTreeHeight(tabSetId, fixMode, pie, leftHeight, rightHeight);
			
			if ( rightHeight - leftHeight == 1 )
			{
			    // nothing to do 
			}
			else if ( rightHeight == leftHeight )
			{
			    pie.setHeight(rightHeight + 1);
			    propagateDecrease(tabSetId, ptp, fixMode);
			}
			else // rightHeight >> leftHeight
			{
			    char h = pie.getHeight();
			    
			    CegoDataPointer nptp;
			    
			    nptp = rebalanceNode(tabSetId, ptp, fixMode);
			    
			    CegoBufferPage pageNE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, nptp, p, len);
			    
			    CegoAVLIndexEntry nie;
			    nie.setPtr(p, len);
			    
			    if ( h != nie.getHeight() )
				propagateDecrease(tabSetId, nptp, fixMode);
			    
			    _pTM->releaseDataPtrUnlocked(pageNE, true);
			    
			}
		    }
		}
		else if ( pie.getRightBranch() == itp)
		{
		    
		    // cout << "Index Delete : case Ib " << endl;
		    
		    pie.setRightBranch(nil);
		    
		    if ( pie.getData() != nil )
		    {
			char leftHeight, rightHeight;
			getSubTreeHeight(tabSetId, fixMode, pie, leftHeight, rightHeight);		
			
			if ( leftHeight - rightHeight == 1 )
			{
			    // nothing to do
			}
			else if ( leftHeight == rightHeight )
			{
			    pie.setHeight(leftHeight  + 1);
			    propagateDecrease(tabSetId, ptp, fixMode);
			}
			else //  leftHeight >> rightHeight
			{
			    
			    char h = pie.getHeight();
			    
			    CegoDataPointer nptp;
			    
			    nptp = rebalanceNode(tabSetId, ptp, fixMode);
			    
			    CegoBufferPage pageNE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, nptp, p, len);
			    
			    CegoAVLIndexEntry nie;
			    nie.setPtr(p, len);
			    
			    if ( h != nie.getHeight() )
				propagateDecrease(tabSetId, nptp, fixMode);
			    
			    _pTM->releaseDataPtrUnlocked(pageNE, true);
			    
			}
		    }
		}
		
		_pTM->releaseDataPtrUnlocked(pagePE, true);   
		_pTM->deleteData(idxType, tabSetId, itp);
		
	    } 
	    else if ( ie.getRightBranch() == nil )
	    {
		
		// cout << "Index Delete : case II " << endl;
		
		CegoDataPointer ldp = ie.getLeftBranch();
		
		CegoAVLIndexEntry pie, lie;
		
		CegoBufferPage pagePE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len);
		pie.setPtr(p, len);	  	
		
		CegoBufferPage pageLE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ldp, p, len);
		lie.setPtr(p,len);

		lie.setParent(ptp);
		_pTM->releaseDataPtrUnlocked(pageLE, true);	
		
		if ( pie.getLeftBranch() == itp )
		{
		    pie.setLeftBranch(ldp);
		    
		    if ( pie.getData() != nil )
		    {
			char leftHeight, rightHeight;
			getSubTreeHeight(tabSetId, fixMode, pie, leftHeight, rightHeight);		
			
			if ( rightHeight - leftHeight == 1 ) 
			{
			    pie.setHeight(rightHeight + 1);
			    // nothing to do
			}
			else if ( leftHeight == rightHeight )
			{
			    pie.setHeight(leftHeight + 1);
			    propagateDecrease(tabSetId, ptp, fixMode);
			}
			else // rightHeight >> leftHeight 
			{
			    
			    char h = pie.getHeight();
			    
			    CegoDataPointer nptp;
			    
			    nptp = rebalanceNode(tabSetId, ptp, fixMode);
			    
			    CegoBufferPage pageNE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, nptp, p, len);
			    
			    CegoAVLIndexEntry nie;
			    nie.setPtr(p, len);
			    
			    if ( h != nie.getHeight() )
				propagateDecrease(tabSetId, nptp, fixMode);
			    
			    _pTM->releaseDataPtrUnlocked(pageNE, true);
			    
			} 
		    }
		}
		else if ( pie.getRightBranch() == itp )
		{
		    pie.setRightBranch(ldp);
		    
		    if ( pie.getData() != nil )
		    {
			
			char leftHeight, rightHeight;
			getSubTreeHeight(tabSetId, fixMode, pie, leftHeight, rightHeight);		
			
			if (  leftHeight - rightHeight == 1 )
			{
			    // nothing to do
			}
			else if ( leftHeight == rightHeight )
			{
			    pie.setHeight(leftHeight + 1);
			    propagateDecrease(tabSetId, ptp, fixMode);
			}
			else
			{		   
	
			    char h = pie.getHeight();
			    
			    CegoDataPointer nptp;
			    
			    nptp = rebalanceNode(tabSetId, ptp, fixMode);
			    
			    CegoBufferPage pageNE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, nptp, p, len);

			    CegoAVLIndexEntry nie;
			    nie.setPtr(p, len);
			    
			    if ( h != nie.getHeight() )
				propagateDecrease(tabSetId, nptp, fixMode);
			    
			    _pTM->releaseDataPtrUnlocked(pageNE, true);
			}
		    }
		}
		
		_pTM->releaseDataPtrUnlocked(pagePE, true);	       
		_pTM->deleteData(idxType, tabSetId, itp);
		
	    }
	    else if ( ie.getLeftBranch() == nil )
	    {
		
		// cout << "Index Delete : case III " << endl;
		
		CegoDataPointer rdp = ie.getRightBranch();
		
		CegoAVLIndexEntry pie, rie;
		
		CegoBufferPage pagePE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode,  ptp, p, len);
		pie.setPtr(p, len);	  	
		
		if ( pie.getLeftBranch() == itp )
		{
		    pie.setLeftBranch(rdp);
		    
		    if ( pie.getData() != nil )
		    {
			char leftHeight, rightHeight;
			getSubTreeHeight(tabSetId, fixMode, pie, leftHeight, rightHeight);		
			
			if (  rightHeight - leftHeight == 1 )	
			{
			    // nothing to do
			}
			else if (  rightHeight - leftHeight == 0 )
			{
			    pie.setHeight(rightHeight + 1);
			    propagateDecrease(tabSetId, ptp, fixMode);
			}
			else
			{
			    char h = pie.getHeight();
			    
			    CegoDataPointer nptp;
			    
			    nptp = rebalanceNode(tabSetId, ptp, fixMode);
			    
			    CegoBufferPage pageNE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, nptp, p, len);
			    
			    CegoAVLIndexEntry nie;
			    nie.setPtr(p, len);
			    
			    if ( h != nie.getHeight() )
				propagateDecrease(tabSetId, nptp, fixMode);
			    
			    _pTM->releaseDataPtrUnlocked(pageNE, true);			    
			    
			}
		    }
		} 
		else if ( pie.getRightBranch() == itp )
		{
		    pie.setRightBranch(rdp);
		    
		    if ( pie.getData() != nil )
		    {
			
			char leftHeight, rightHeight;
			getSubTreeHeight(tabSetId, fixMode, pie, leftHeight, rightHeight);		
			
			if ( leftHeight - rightHeight == 1 ) 
			{
			    // nothing to do
			}
			else if ( leftHeight == rightHeight )
			{
			    pie.setHeight(leftHeight + 1);
			    propagateDecrease(tabSetId, ptp, fixMode);
			}
			else
			{

			    
			    char h = pie.getHeight();
			    
			    CegoDataPointer nptp;
			    
			    nptp = rebalanceNode(tabSetId, ptp, fixMode);
			    
			    CegoBufferPage pageNE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, nptp, p, len);
			    
			    CegoAVLIndexEntry nie;
			    nie.setPtr(p, len);
			    
			    if ( h != nie.getHeight() )
				propagateDecrease(tabSetId, nptp, fixMode);
			    
			    _pTM->releaseDataPtrUnlocked(pageNE, true);
			}
		    }
		}
		_pTM->releaseDataPtrUnlocked(pagePE, true);	
		
		CegoBufferPage pageR = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, rdp, p, len);
		rie.setPtr(p,len);
		rie.setParent(ptp);
		
		_pTM->releaseDataPtrUnlocked(pageR, true);
		_pTM->deleteData(idxType, tabSetId, itp);
		
	    }
	    else  
	    {
		
		// cout << "Index Delete : case IV " << endl;
		
		CegoDataPointer ndp = ie.getRightBranch();

		CegoAVLIndexEntry nie;
		
		CegoBufferPage pageNE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ndp, p, len);
		nie.setPtr(p, len);
		
		if ( nie.getLeftBranch() == nil)
		{
		    
		    // cout << "Index Delete : case IVa " << endl;
		    
		    CegoAVLIndexEntry pie, lie;
		    
		    CegoBufferPage pagePE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len);
		    pie.setPtr(p, len);
		    
		    if ( pie.getRightBranch() == itp )
		    {
			pie.setRightBranch(ndp);
		    }
		    else if ( pie.getLeftBranch() == itp )
		    {
			pie.setLeftBranch(ndp);
		    }
		    
		    nie.setParent(ptp);
		    
		    CegoDataPointer ldp = ie.getLeftBranch();
		    // cout << "LDP = " << ldp << endl;
		    CegoBufferPage pageLE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ldp, p, len);
		    
		    lie.setPtr(p, len);
		    
		    lie.setParent(ndp);
		    
		    nie.setLeftBranch(ldp);
		    
		    char leftHeight, rightHeight;
		    getSubTreeHeight(tabSetId, fixMode, nie, leftHeight, rightHeight);		
		    
		    char diff;
		    diff = leftHeight - rightHeight;
		    
		    if ( diff == 1 || diff == 0 ) 
		    {
			nie.setHeight(leftHeight + 1);
			propagateDecrease(tabSetId, ndp, fixMode);
		    }
		    else // leftHeight >> rightHeight 
		    {
			char h = nie.getHeight();
			CegoDataPointer nndp = rebalanceNode(tabSetId, ndp, fixMode);
			
			CegoBufferPage pageNN = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, nndp, p, len);
			CegoAVLIndexEntry nnie;
			nnie.setPtr(p, len);
			
			if ( h != nnie.getHeight() )
			    propagateDecrease(tabSetId, nndp, fixMode);
			
			_pTM->releaseDataPtrUnlocked(pageNN);
		    }
		    
		    _pTM->releaseDataPtrUnlocked(pagePE);
		    _pTM->releaseDataPtrUnlocked(pageLE);
		    
		    _pTM->deleteData(idxType, tabSetId, itp);
		    
		}
		else
		{
		    
		    // cout << "Index Delete : case IVb " << endl;
		    
		    CegoBufferPage pageZE;
		    CegoBufferPage pageFE;
		    CegoBufferPage pageAE;
		    CegoBufferPage pageBE;
		    CegoBufferPage pageCE;
		    
		    while ( nie.getLeftBranch() != nil )
		    {	
			ndp = nie.getLeftBranch();
			
			if (pageNE.isFixed())
			{
			    _pTM->releaseDataPtrUnlocked(pageNE, false);
			}
			
			pageNE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ndp, p, len);
			nie.setPtr(p,len);	    		
		    }
		    
		    CegoAVLIndexEntry fie;		    
		    CegoDataPointer fdp = nie.getParent();
		    pageFE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, fdp, p, len);
		    fie.setPtr(p,len);
		    
		    if ( nie.getRightBranch() != nil )
		    {
			CegoDataPointer zdp = nie.getRightBranch();
			
			CegoAVLIndexEntry zie;
			
			pageZE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, zdp, p, len);
			zie.setPtr(p,len);
			
			zie.setParent(nie.getParent());
			
			fie.setLeftBranch(zdp);
		    } 
		    else
		    {
			fie.setLeftBranch(nil);
		    }
		    
		    CegoDataPointer adp, bdp, cdp;
		    CegoAVLIndexEntry aie, bie, cie;
		    
		    adp=ie.getParent();
		    bdp=ie.getLeftBranch();
		    cdp=ie.getRightBranch();
		    
		    pageAE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, adp, p, len);
		    aie.setPtr(p,len);
		    pageBE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, bdp, p, len);
		    bie.setPtr(p,len);
		    pageCE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, cdp, p, len);
		    cie.setPtr(p,len);
		    
		    nie.setParent(adp);
		    nie.setLeftBranch(bdp);
		    nie.setRightBranch(cdp);
		    
		    char leftHeight, rightHeight;
		    getSubTreeHeight(tabSetId, fixMode, nie, leftHeight, rightHeight);		
		    nie.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);
		    
		    if ( aie.getLeftBranch() == itp )
		    {
			aie.setLeftBranch(ndp);
		    }
		    else
		    {
			aie.setRightBranch(ndp);
		    }
		    bie.setParent(ndp);
		    cie.setParent(ndp);
		    
		    getSubTreeHeight(tabSetId, fixMode, fie, leftHeight, rightHeight);		
		    
		    char diff;
		    char maxHeight;
		    
		    if ( leftHeight > rightHeight )
		    {
			diff = leftHeight - rightHeight;
			maxHeight = leftHeight;
		    }
		    else
		    {
			diff = rightHeight - leftHeight;
			maxHeight = rightHeight;
		    }
		    
		    if ( diff == 1 || diff == 0)
		    {
			fie.setHeight( maxHeight + 1);
			propagateDecrease(tabSetId, fdp, fixMode);
		    }
		    else // rightHeight >> leftHeight )
		    {
			
			char h = fie.getHeight();
			CegoDataPointer nfdp;
			
			nfdp = rebalanceNode(tabSetId, fdp, fixMode);
			
			CegoBufferPage pageRE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, nfdp, p, len);
			
			CegoAVLIndexEntry nfie;
			nfie.setPtr(p, len);
			
			if ( h != nfie.getHeight() )
			    propagateDecrease(tabSetId, nfdp, fixMode);
			
			_pTM->releaseDataPtrUnlocked(pageRE, true);
		    }
		    
		    if (pageAE.isFixed())
			_pTM->releaseDataPtrUnlocked(pageAE, true);	
		    if (pageBE.isFixed())
			_pTM->releaseDataPtrUnlocked(pageBE, true);	
		    if (pageCE.isFixed())
			_pTM->releaseDataPtrUnlocked(pageCE, true);	
		    if (pageFE.isFixed())
			_pTM->releaseDataPtrUnlocked(pageFE, true);	
		    if (pageZE.isFixed())
			_pTM->releaseDataPtrUnlocked(pageZE, true);		       
		    
		    _pTM->deleteData(idxType, tabSetId, itp);
		}
		
		if (pageNE.isFixed())
		    _pTM->releaseDataPtrUnlocked(pageNE, true);
	    }
	}
	else
	{


	    CegoField* pF = schema.First();
	    char *p = idxPtr;

	    Chain v;

	    while (pF)
	    {
				
		int flen;
		memcpy(&flen, p, sizeof(int));
		p += sizeof(int);
		
		CegoFieldValue fv;
		fv.setLength(flen);
		fv.setValue(p);

		if ( flen > 0 )
		    fv.setType(pF->getType());

		p += flen;
	    
		v += fv.valAsChain() + Chain(" ");
		pF = schema.Next();
	    }

	    Chain msg = Chain("Value for index ") + indexName + Chain(" ( value = ") + v + Chain(") not found");
	    throw Exception(EXLOC, msg);	
	}
    }
    catch ( Exception e )
    {
	
	if (rootLock)
	    _pTM->releaseDataPtr(rootLock, false);
	throw e;
    }
    
    if (pageIE.isFixed())
	_pTM->releaseDataPtrUnlocked(pageIE, false);
    
    if (rootLock)
	_pTM->releaseDataPtr(rootLock, false);
    
}

void CegoAVLIndexManager::propagateDecrease(int tabSetId, CegoDataPointer itp, CegoBufferPool::FixMode fixMode)
{

    // cout << "Propagate Decrease ..." << endl;

    char* p;
    int len;

    CegoBufferPage pageIE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, itp, p, len);
    CegoAVLIndexEntry ie;    
    ie.setPtr(p, len);	  	

    CegoDataPointer nil;

    if ( ie.getData() == nil )
    {
	if ( pageIE.isFixed() )
	    _pTM->releaseDataPtrUnlocked(pageIE, true);
	return;
    }
    CegoDataPointer ptp = ie.getParent();
    
    CegoBufferPage pagePE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len);
    CegoAVLIndexEntry pie;    
    pie.setPtr(p, len);	  	

    if ( pie.getData() == nil )
    {
	if ( pageIE.isFixed() )
	    _pTM->releaseDataPtrUnlocked(pageIE, true);
	if ( pagePE.isFixed() )
	    _pTM->releaseDataPtrUnlocked(pagePE, true);
	return;
    }
    bool treeBalanced = false;
    bool rootReached = false;

    while ( ! treeBalanced && ! rootReached)
    {
	
	char leftHeight, rightHeight;
	getSubTreeHeight(tabSetId, fixMode, pie, leftHeight, rightHeight);

	char diff;
	if ( leftHeight > rightHeight )
	    diff = leftHeight - rightHeight;
	else
	    diff = rightHeight - leftHeight;
	
	
	if ( diff == 1 )
	{
	    // nothing to do
	}
	else if ( diff == 0 )
	{	
	    pie.setHeight(leftHeight + 1);		
	}
	else
	{
	    
	    ptp = rebalanceNode(tabSetId, ptp, fixMode);
	    
	    if ( pagePE.isFixed() )
	    {
		_pTM->releaseDataPtrUnlocked(pagePE, true);
	    }
	    if (ptp.getOffset())
	    {   
		pagePE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len);
		pie.setPtr(p, len);
	    }
	}

	if ( pageIE.isFixed() ) 	       
	{
	    _pTM->releaseDataPtrUnlocked(pageIE, true);
	}
	
	itp = ptp;
	pageIE = pagePE;
	ie = pie;
	
	ptp = ie.getParent();
	
	if (ptp.getOffset())
	{   
	    pagePE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len);
	    pie.setPtr(p, len);
	}
	
	if ( pie.getData() == nil )
	{
	    pie.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);
	    rootReached = true;
	}
    }
    
    if ( pageIE.isFixed() ) 	       
	_pTM->releaseDataPtrUnlocked(pageIE, true);
    if ( pagePE.isFixed() )
	_pTM->releaseDataPtrUnlocked(pagePE, true);
    
}

CegoDataPointer CegoAVLIndexManager::rebalanceNode(int tabSetId, CegoDataPointer itp, CegoBufferPool::FixMode fixMode)
{

    // cout << "Rebalancing node " << itp << endl;
    char* p;
    int len;

    CegoDataPointer nil;

    CegoBufferPage pageIE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, itp, p, len);
    CegoAVLIndexEntry ie;    
    ie.setPtr(p, len);	  	

    char leftHeight, rightHeight;
    getSubTreeHeight(tabSetId, fixMode, ie, leftHeight, rightHeight);

    // cout << "lh=" << (int)leftHeight << " rh=" << (int)rightHeight << endl;
 
    char diff;
    if ( leftHeight > rightHeight )
	diff = leftHeight - rightHeight;
    else
	diff = rightHeight - leftHeight;

    CegoDataPointer nptp;

    if ( leftHeight > rightHeight && diff > 1  )
    {

	// decide if LL or LR Rotation
	CegoDataPointer ldp = ie.getLeftBranch();
	CegoBufferPage pageLE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ldp, p, len);
	CegoAVLIndexEntry lie;    
	lie.setPtr(p, len);	  	
	
	char leftHeight, rightHeight;
	getSubTreeHeight(tabSetId, fixMode, lie, leftHeight, rightHeight);
		
	if ( leftHeight >= rightHeight )
	{
	    nptp = rotateLL(tabSetId, itp, fixMode);
	}
	else
	{
	    nptp = rotateLR(tabSetId, itp, fixMode);
	}
	_pTM->releaseDataPtrUnlocked(pageLE, true);
	
    }
    else if ( leftHeight < rightHeight && diff > 1  )
    {

	// decide if RR or RL Rotation

	CegoDataPointer rdp = ie.getRightBranch();		
	CegoBufferPage pageRE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, rdp, p, len);
		
	CegoAVLIndexEntry rie;
	rie.setPtr(p, len);

	char leftHeight, rightHeight;
	getSubTreeHeight(tabSetId, fixMode, rie, leftHeight, rightHeight);
	
	if ( leftHeight <= rightHeight )
	{
	    nptp = rotateRR(tabSetId, itp, fixMode);
	}
	else
	{
	    nptp = rotateRL(tabSetId, itp, fixMode);
	    CegoBufferPage pageSE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, nptp, p, len);
	    
	    CegoAVLIndexEntry rie;
	    rie.setPtr(p, len);
	    CegoDataPointer rdp = rie.getRightBranch();
	    if ( rdp != nil )
	    {
		CegoDataPointer sub;
		sub = rebalanceNode(tabSetId, rdp, fixMode);
	    }
	    _pTM->releaseDataPtrUnlocked(pageSE, true);
	}
	_pTM->releaseDataPtrUnlocked(pageRE, true);
    }
    
    _pTM->releaseDataPtrUnlocked(pageIE, true);

    return nptp;
}

CegoAVLIndexManager::TupleOrder CegoAVLIndexManager::compIndexValue(const ListT<CegoField>& schema, char* p1, char* p2)
{

    CegoField* pF = schema.First();
           	
    while (pF)
    {
       
	int flen1, flen2;
	memcpy(&flen1, p1, sizeof(int));
	memcpy(&flen2, p2, sizeof(int));

	p1 += sizeof(int);
	p2 += sizeof(int);
	
	CegoFieldValue fv1, fv2;
	fv1.setLength(flen1);
	fv2.setLength(flen2);

	fv1.setValue(p1);
	fv2.setValue(p2);
	

	if ( flen1 > 0 )
	    fv1.setType(pF->getType());
	if ( flen2 > 0 )
	    fv2.setType(pF->getType());

	// both null values 
	if ( flen1 == 0 && flen2 == 0 )
	{
	    // if ( ALLOW_UNIQUE_NULL == true)
	    // 	return LT;
	    return EQU_NULL;
	}
	if ( fv1 < fv2 )
	{
	    return LT;
	}
	if ( fv1 > fv2 )
	{
	    return GT;
	}
			
	pF = schema.Next();
	if ( pF )
	{
	    p1 += flen1;
	    p2 += flen2;
	}
    }
   
    return EQU;

}


CegoDataPointer CegoAVLIndexManager::rotateRR(int tabSetId, const CegoDataPointer& ptp, CegoBufferPool::FixMode fixMode)
{

    // cout << "RotateRR" << ptp << endl;

    char *p;
    int len;

    CegoDataPointer itp, atp, ctp;
    CegoAVLIndexEntry pe, ie, ae, ce;

    CegoBufferPage pagePE;
    CegoBufferPage pageIE;

    CegoBufferPage pageAE;
    CegoBufferPage pageCE;


    // a is parent of pe
    // c is left child of ie

    pagePE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len);
    pe.setPtr(p, len);

    atp = pe.getParent();
          
    if (atp.getOffset())
    {
	pageAE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, atp, p, len);
	ae.setPtr(p, len);
    }

    itp = pe.getRightBranch();
    
    if (itp.getOffset())
    {
	pageIE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, itp, p, len);
	ie.setPtr(p, len);
    }
    else
    {
	throw Exception(EXLOC, "Invalid index reference at RR rotation");
    }
    
    ctp = ie.getLeftBranch();
    if ( ctp.getOffset() )
    {
	pageCE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ctp, p, len);
	ce.setPtr(p, len);
    }
    
    /////////////////////
    
    pe.setRightBranch(ctp);
    if (ctp.getOffset())
    {
	ce.setParent(ptp);			
    }
    
    if (atp.getOffset())
    {			
	if ( ae.getRightBranch() == ptp )
	{
	    ae.setRightBranch(itp);
	}
	else
	{
	    ae.setLeftBranch(itp);
	}
    }
    
    ie.setParent(atp);
    pe.setParent(itp);
    ie.setLeftBranch(ptp);
    
    // set up balance

    char leftHeight, rightHeight;
    getSubTreeHeight(tabSetId, fixMode, pe, leftHeight, rightHeight);				   
    pe.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);

    getSubTreeHeight(tabSetId, fixMode, ie, leftHeight, rightHeight);				   
    ie.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);

    if (atp.getOffset())
    {
	getSubTreeHeight(tabSetId, fixMode, ae, leftHeight, rightHeight);
	ae.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);
    }

    if (pagePE.isFixed())
	_pTM->releaseDataPtrUnlocked(pagePE, true);	
    if (pageIE.isFixed())
	_pTM->releaseDataPtrUnlocked(pageIE, true);	
    if (pageCE.isFixed())
	_pTM->releaseDataPtrUnlocked(pageCE, true);	
    if (pageAE.isFixed())
	_pTM->releaseDataPtrUnlocked(pageAE, true);	

    return itp;
}


CegoDataPointer CegoAVLIndexManager::rotateRL(int tabSetId, const CegoDataPointer& ptp, CegoBufferPool::FixMode fixMode)
{
    // cout << "RotateRL at " << ptp << endl;
    char *p;
    int len;
    
    CegoDataPointer itp, atp, ctp, etp, ftp;
    CegoAVLIndexEntry pe, ie, ae, ce, ee, fe;

    CegoBufferPage pagePE;
    CegoBufferPage pageIE;

    CegoBufferPage pageAE;
    CegoBufferPage pageCE;
    CegoBufferPage pageEE;
    CegoBufferPage pageFE;

    
    // a is parent of pe
    // c is left child of ie
    // e is left child of c
    // f is right child of c

    if (ptp.getOffset())
    {   
	pagePE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len);
	pe.setPtr(p, len);
    }
    else
    {
	throw Exception(EXLOC, "Invalid index reference at RL rotation");
    }

    atp = pe.getParent();
        
    if (atp.getOffset())
    {
	pageAE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, atp, p, len);
	ae.setPtr(p, len);
    }

    itp = pe.getRightBranch();    

    if (itp.getOffset())
    {
	
	pageIE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, itp, p, len);
	ie.setPtr(p, len);
    }
    else
    {
	throw Exception(EXLOC, "Invalid index reference at RL rotation");
    }
    
    ctp = ie.getLeftBranch();
    if ( ctp.getOffset() )
    {
	pageCE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ctp, p, len);
	ce.setPtr(p, len);
    }
    
    ftp = ce.getRightBranch();
    if (ftp.getOffset())
    {
	pageFE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ftp, p, len);
	fe.setPtr(p, len);
    }
        
    etp = ce.getLeftBranch();
    if ( etp.getOffset() )
    {
	pageEE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, etp, p, len);
	ee.setPtr(p, len);
    }
    
    ie.setLeftBranch(ftp);
    if ( ftp.getOffset() )
    {
	fe.setParent(itp);
    }
    
    if (atp.getOffset())
    {
	if (ae.getRightBranch() == ptp )
	{
	    ae.setRightBranch(ctp);
	}
	else
	{
	    ae.setLeftBranch(ctp);
	}
    }
    ce.setParent(atp);
    
    ce.setRightBranch(itp);
    ie.setParent(ctp);
    
    ie.setLeftBranch(ftp);
    if (ftp.getOffset())
    {
	fe.setParent(itp);
    }
    ce.setLeftBranch(ptp);
    
    pe.setParent(ctp);
    
    if (etp.getOffset())
    {
	ee.setParent(ptp);
    }		    
    pe.setRightBranch(etp);
    
    // set up balance

    char leftHeight, rightHeight;
    getSubTreeHeight(tabSetId, fixMode, pe, leftHeight, rightHeight);				   
    pe.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);

    getSubTreeHeight(tabSetId, fixMode, ie, leftHeight, rightHeight);				   
    ie.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);

    getSubTreeHeight(tabSetId, fixMode, ce, leftHeight, rightHeight);
    ce.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);

    if (atp.getOffset())
    {
	getSubTreeHeight(tabSetId, fixMode, ae, leftHeight, rightHeight);
	ae.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);
    }
    
    if (pagePE.isFixed())
	_pTM->releaseDataPtrUnlocked(pagePE, true);	
    if (pageIE.isFixed())
	_pTM->releaseDataPtrUnlocked(pageIE, true);
    if (pageCE.isFixed())
	_pTM->releaseDataPtrUnlocked(pageCE, true);	
    if (pageAE.isFixed())
	_pTM->releaseDataPtrUnlocked(pageAE, true);	
    if (pageEE.isFixed())
	_pTM->releaseDataPtrUnlocked(pageEE, true);	
    if (pageFE.isFixed())
	_pTM->releaseDataPtrUnlocked(pageFE, true);	

    return ctp;
}


CegoDataPointer CegoAVLIndexManager::rotateLL(int tabSetId, const CegoDataPointer& ptp, CegoBufferPool::FixMode fixMode)
{

    // cout << "RotateLL at " << ptp << endl;

    char *p;
    int len;
    
    CegoDataPointer itp, atp, dtp;
    CegoAVLIndexEntry pe, ie, ae, de;

    CegoBufferPage pagePE;
    CegoBufferPage pageIE;
    
    CegoBufferPage pageAE;
    CegoBufferPage pageDE;

    // a is parent of pe
    // d is right child of ie

    if (ptp.getOffset())
    {   
	pagePE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len);
	pe.setPtr(p, len);
    }
    else
    {
	throw Exception(EXLOC, "Invalid index reference at LL rotation");
    }
    
    atp = pe.getParent();
    
    if (atp.getOffset())
    {	
	pageAE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, atp, p, len);
	ae.setPtr(p, len);
    }

    itp = pe.getLeftBranch();

    if (itp.getOffset())
    {
	pageIE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, itp, p, len);
	ie.setPtr(p, len);
    }
    else
    {
	throw Exception(EXLOC, "Invalid index reference at LL rotation");
    }
    
    dtp = ie.getRightBranch();
    
    if (dtp.getOffset())
    {
	pageDE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, dtp, p, len);
	de.setPtr(p, len);
    }
        
    if (dtp.getOffset())
    {
	de.setParent(ptp);
    }
    pe.setLeftBranch(dtp);
    
    pe.setParent(itp);
    ie.setRightBranch(ptp);		
    
    if (atp.getOffset())
    {
	
	if ( ae.getRightBranch() == ptp )
	{
	    ae.setRightBranch(itp);
	}
	else
	{
	    ae.setLeftBranch(itp);
	}
    }
    ie.setParent(atp);

    char leftHeight, rightHeight;
    getSubTreeHeight(tabSetId, fixMode, pe, leftHeight, rightHeight);				   
    pe.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);

    getSubTreeHeight(tabSetId, fixMode, ie, leftHeight, rightHeight);				   
    ie.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);

    if (atp.getOffset())
    {
	getSubTreeHeight(tabSetId, fixMode, ae, leftHeight, rightHeight);				   
	ae.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);
    }

    if (pagePE.isFixed())
	_pTM->releaseDataPtrUnlocked(pagePE, true);	    
    if (pageIE.isFixed())
	_pTM->releaseDataPtrUnlocked(pageIE, true);	
    if (pageAE.isFixed())
	_pTM->releaseDataPtrUnlocked(pageAE, true);	
    if (pageDE.isFixed())
	_pTM->releaseDataPtrUnlocked(pageDE, true);	

    return itp;
} 

CegoDataPointer CegoAVLIndexManager::rotateLR(int tabSetId, const CegoDataPointer& ptp, CegoBufferPool::FixMode fixMode)
{

    // cout << "RotateLR at " << ptp  << endl;

    char *p;
    int len;
        
    CegoDataPointer itp, atp, ctp, dtp, etp;
    CegoAVLIndexEntry pe, ie, ae, ce, de, ee;

    CegoBufferPage pagePE;
    CegoBufferPage pageIE;
    
    CegoBufferPage pageAE;
    CegoBufferPage pageCE;
    CegoBufferPage pageDE;
    CegoBufferPage pageEE;


    // a is parent of pie
    // d is right child of ie
    // c is left child of d
    // e is right child of d
    
    if (ptp.getOffset())
    {   
	pagePE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len);
	pe.setPtr(p, len);
    }
    else
    {
	throw Exception(EXLOC, "Invalid index reference at LR rotation");
    }
    
    atp = pe.getParent();
    
    if (atp.getOffset())
    {
	pageAE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, atp, p, len);
	ae.setPtr(p, len);
    }

    itp = pe.getLeftBranch();
    
    if (itp.getOffset())
    {
	pageIE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, itp, p, len);
	ie.setPtr(p, len);
    }
    else
    {
	throw Exception(EXLOC, "Invalid index reference at LR rotation");
    }
    
    dtp = ie.getRightBranch();
    if (dtp.getOffset())
    {	
	pageDE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, dtp, p, len);
	de.setPtr(p, len);
    }
    else
    {
	throw Exception(EXLOC, "Invalid index reference at LR rotation");
    }

    ctp = de.getLeftBranch();
    if (ctp.getOffset())
    {
	pageCE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ctp, p, len);
	ce.setPtr(p, len);
    }

    etp = de.getRightBranch();
    if (etp.getOffset())
    {
	pageEE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, etp, p, len);
	ee.setPtr(p, len);
    }
    
    ie.setRightBranch(ctp);
    
    if (ctp.getOffset())
    {
	ce.setParent(itp);
    }
    
    ie.setParent(dtp);
    de.setLeftBranch(itp);		    
    
    if (atp.getOffset())
    {		    
	if ( ae.getRightBranch() == ptp )		    
	{
	    ae.setRightBranch(dtp);
	}
	else
	{
	    ae.setLeftBranch(dtp);
	}
    }
    
    de.setParent(atp);		 		    
    de.setRightBranch(ptp);			
    pe.setParent(dtp);		
    
    if (etp.getOffset())
    {
	ee.setParent(ptp);
    }
    pe.setLeftBranch(etp);
    

    // set up balance

    char leftHeight, rightHeight;
    getSubTreeHeight(tabSetId, fixMode, pe, leftHeight, rightHeight);				       
    pe.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);

    getSubTreeHeight(tabSetId, fixMode, ie, leftHeight, rightHeight);				   
    ie.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);

    getSubTreeHeight(tabSetId, fixMode, de, leftHeight, rightHeight); 
    de.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);

    if (atp.getOffset())
    {		    
	getSubTreeHeight(tabSetId, fixMode, ae, leftHeight, rightHeight); 
	ae.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);
    }

    if (pagePE.isFixed())
	_pTM->releaseDataPtrUnlocked(pagePE, true);	
    if (pageIE.isFixed())
	_pTM->releaseDataPtrUnlocked(pageIE, true);	
    
    if (pageAE.isFixed())
	_pTM->releaseDataPtrUnlocked(pageAE, true);	
    if (pageCE.isFixed())
	_pTM->releaseDataPtrUnlocked(pageCE, true);	
    if (pageDE.isFixed())
	_pTM->releaseDataPtrUnlocked(pageDE, true);	
    if (pageEE.isFixed())
	_pTM->releaseDataPtrUnlocked(pageEE, true);

    return dtp;
}

char CegoAVLIndexManager::checkIndex(int tabSetId, const Chain& indexName, CegoObject::ObjectType idxType)
{    


    CegoTableObject oe;
    _pTM->getObject(tabSetId, indexName, idxType, oe);
    

    CegoObjectCursor* pC = _pTM->getObjectCursor(tabSetId, oe.getTabName(), indexName, idxType);
    
    if ( ! pC )
    {
	Chain msg = "Cannot get cursor for <" + indexName  + ">";
	throw Exception(EXLOC, msg);	
    } 

    CegoDataPointer rdp;
    char* p;
    int len;
    p = (char*)pC->getFirst(len, rdp);
    
    if ( p == 0)
    {
	throw Exception(EXLOC, "Missing Index Anchor");
    }
    
    pC->abort();
    delete pC;

    /////////////////////////////////////////

    CegoDataPointer ptp = rdp;
    unsigned long rootLock = _pTM->claimDataPtr(tabSetId, CegoLockHandler::READ, CegoBufferPool::SYNC, ptp, p, len);

    CegoAVLIndexEntry ie;
    ie.setPtr(p, len);    
    
    CegoDataPointer  itp;
    itp = ie.getRightBranch();

    char h = recursiveIndexNodeCheck(tabSetId, itp);
    
    if (rootLock)
	_pTM->releaseDataPtr(rootLock, false);

    return h;
}

char CegoAVLIndexManager::recursiveIndexNodeCheck(int tabSetId, const CegoDataPointer& dp)
{

    CegoDataPointer nil;

    if ( dp == nil )
	return 0;
    
    char* p;
    int len;

    
#ifdef CGDEBUG
    _pLogger->log(_modId, Logger::DEBUG, Chain("Claiming datapointer ") +  dp.toChain());
#endif

    CegoBufferPage bp = _pTM->claimDataPtrUnlocked(tabSetId, CegoBufferPool::SYNC, dp, p, len); 

    CegoAVLIndexEntry ie;
    ie.setPtr(p, len);    

    CegoDataPointer rightBranch = ie.getRightBranch();
    CegoDataPointer leftBranch = ie.getLeftBranch();
    char nodeHeight = ie.getHeight();
#ifdef CGDEBUG
    _pLogger->log(_modId, Logger::DEBUG, Chain("Accessing datapointer ") +  dp.toChain());
#endif

    if (bp.isFixed())
    {
#ifdef CGDEBUG
	_pLogger->log(_modId, Logger::DEBUG, Chain("Releasing datapointer ") +  dp.toChain());
#endif

	_pTM->releaseDataPtrUnlocked(bp, false);
    }

    char rightHeight = recursiveIndexNodeCheck(tabSetId, rightBranch);
    if ( rightHeight == -1 )
	return -1;

    char leftHeight = recursiveIndexNodeCheck(tabSetId, leftBranch);
    if ( leftHeight == -1 )
	return -1;

    char subHeight = leftHeight > rightHeight ? leftHeight : rightHeight;

    char diff = leftHeight > rightHeight ? leftHeight - rightHeight : rightHeight - leftHeight;

    if ( diff > 1 )
    {
	return -1 ;
    }
    
    if ( nodeHeight != subHeight + 1 )
    {
	// cout << dp << " Node Height = " << (int)nodeHeight << " SubNode Height= " << (int)subHeight<< endl;
	return -1;
    }

    return nodeHeight;
 }


CegoDataPointer CegoAVLIndexManager::searchDataPointer(int tabSetId, const CegoDataPointer& ddp, const CegoDataPointer& rdp, CegoBufferPool::FixMode fixMode)
{
    CegoDataPointer itp;

    CegoDataPointer nil;

    if ( rdp == nil )
	return nil;

    char* p;
    int len;
         
    CegoBufferPage pageRE = _pTM->claimDataPtrUnlocked(tabSetId, fixMode, rdp, p, len);  

    CegoAVLIndexEntry re;
    re.setPtr(p, len);    
    
    if ( re.getData() == ddp )
    {
	itp = rdp;
    }
    else
    {	
	itp = searchDataPointer ( tabSetId, ddp, re.getLeftBranch(), fixMode);
	
	if ( itp == nil )
	{
	    itp = searchDataPointer ( tabSetId, ddp, re.getRightBranch(), fixMode);
	}
    }

    if ( pageRE.isFixed() )
	_pTM->releaseDataPtrUnlocked(pageRE, false);
    
    return itp;
}
