/*  File: bstree.c
 *  Author: R.Durbin & J.Thierry-Mieg.
 *  Copyright (c) J Thierry-Mieg and R Durbin, 1999
 * -------------------------------------------------------------------
 * Acedb 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
 * of the License, 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; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 * or see the on-line version at http://www.gnu.org/copyleft/gpl.txt
 * -------------------------------------------------------------------
 * This file is part of the ACEDB genome database package, written by
 * 	Richard Durbin (Sanger Centre, UK) rd@sanger.ac.uk, and
 *	Jean Thierry-Mieg (CRBM du CNRS, France) mieg@kaa.crbm.cnrs-mop.fr
 *
 * Description: Transforms back and forth the B blocks into BS trees 
 * Exported functions: 
 * HISTORY:
 * Last edited: Nov  9 13:53 1999 (fw)
 * * Aug 26 17:01 1999 (fw): added this header
 * Created: Thu Aug 26 16:59:46 1999 (fw)
 * CVS info:   $Id: bstree.c,v 1.23 1999/11/09 13:54:10 fw Exp $
 *-------------------------------------------------------------------
 */

#ifdef ACEDB5
void compilersDoNotLike4 (void *emptyFiles) {return ; }
#else  /* !ACEDB5 */

#include "acedb.h"

#include "bs_.h"
#include "b_.h"
#include "block.h"
#include "lex.h"
#include "whooks/systags.h"
#include "whooks/sysclass.h"
#include "chrono.h"
#include "byteswap.h"

#include <ctype.h>

#if defined(MACINTOSH)
#include "memory.h"
#endif

static BS     bsTreeRead     (BP bp,NODE nn,BS b0,BOOL doUnbreakComment);
static void   bsTreeReadCont  (BS *bsp);
static BP     bsTreeFindBlock  (BS  bs,KEY *kp) ;
static void   bsTreeStore2   (BP bp, KEY kk, BS  bs); 
static NODE   bsTreeSt2      (BS  bs,BP bp);
static void   bsTreeStoreContinuation  (KEY k,BP *bpp, BS  bs) ;
static int    bsTreeCellSize     (BS  bs);
static int    bsTreeBreakComment(BS bs);
static void   bsTreeUnbreakComment(BS bs, BS bs1); 
static void   bsPackTimeStamps (BS bs, KEY currStamp) ;
static void   bsUnpackTimeStamps (BS bs, KEY currStamp) ;

/* extern int BSTEST; */       
int bsTreeTEST = FALSE ;
static  char BSbuffer[BLOC_SIZE];  /*to allow for the \t*/

/**************************************************************/
/**************************************************************/
                 /* cannot fail */
BS bsTreeGet(KEY key) 
{
 NODE nn;
 BP bp;
 BS bs;
 
 chrono("bsTreeGet") ;

 if(!iskeyold(key))
   { bs=BSalloc() ;
     bs->key=key;
   }
 else
   {
     Bget(&bp,&nn,key) ;  /* *bp,*nn becomes the origin of the branch*/
     bs = bsTreeRead(bp,nn,(BS)0,TRUE);

     bsUnpackTimeStamps (bs->right, 0) ;
     
     blockunpinn(key);
   }
 
 chronoReturn(); 
 return bs ;
}

/********************************************************************/
                 /*store => free*/
        /* because the splitting of big objects destroys the tree */

void bsTreeStore (BS  bs)
{ static Array warn = 0 ;
  
  KEY key=bs->key,kk ;
  int
    nc=0,         /*number of continuation blocks*/
    ncells, nl=0, nr=0,  nmax ;
  BS bs2, bsl,bsr, bsu, bsn, bsc;
  BP bp , bpc;

  chrono("bsTreeStore") ;

  bsPackTimeStamps (bs->right, 0) ;

           /* set bs -> size, no more recursive sizing needed later */
  ncells=bsTreeCellSize(bs);
           /* set bp to a proper top block */
  if (ncells > 100000)
    { BS bb = bs ;
      int n ;

      while (bb->up) bb = bb->up ;
      n = class(bb->key) ;
      if (!warn) warn = arrayCreate(256, int) ;
      array(warn,n,int)++ ;
      if (array(warn,n,int) == 1)
	messdump ("Class %s, object %s has %d > 100000 cells.\n"
		  "This is just a warning, acedb has no hard limits on the mumber of cells per object,\n"
		  "but the performance degrades on very large objects, and it possible you should \n"
		  "reconsider your models design.  In particular, you may be overusing XREF or ?Text.\n"
		  "This message is issued once per offending class and per code run\n",
		  className(bb->key), name(bb->key), ncells) ;
    }
  
  bpc = bp = bsTreeFindBlock(bs,&kk) ;
  nmax = BNODEMAX-2 ;
  while ((ncells=bs->size) >= BNODEMAX)
    {
      bs2=bs;

      while (ncells > nmax)
        { bsl = bs2->down ; bsr = bs2->right ;
          nl = bsl ? bsl->size : 0 ;
          nr = bsr ? bsr->size : 0 ;
	  if (nl > nr)
	    { ncells = nl ; bs2 = bsl ; }
	  else
	    { ncells = nr ; bs2 = bsr ; }
        }

      if (!bs2 || ncells < 12)
        messcrash (" Error in bsTreeStore , check bsTreeCellSize() :\n%s",
		   name(bs->key));

      /* bs2 is unhooked from bsu and hooked to the new bsn */

      nc++ ;
      bsn = BSalloc() ;
      bsn->key = key ;
      bsn->right = bs2 ;
      bsu = bs2->up ; bs2->up = bsn ;
      bsTreeStoreContinuation (key, &bpc, bsn) ;
      		   /* bsc will now replace the bs2 tree under bsu */
      bsc = BSalloc () ;
      bsc->up = bsu ;
      if (nl > nr)
        bsu->down = bsc;
      else
        bsu->right = bsc;
      bsc->key = _continuationKey  ;
      bsc->n.i = nc ;
      bsc->size = 2;
      ncells -= 2 ; /* The tree is pruned change the size above bsc*/
      while(bsu)
        {
          bsu->size -= ncells;
          bsu = bsu->up;
        }
    }
				/* save top of tree in original block */
  bsTreeStore2 (bp,kk,bs) ;
				/* discard anything further down */
  blockSetEnd (bpc) ;
  blockrewrite (kk) ;
  
  chronoReturn () ;
}

/******************************************************************/
                 /* recursive pice,  calls bsTreeBreakComment */
static BS bsxxx ;
static int sizexxx ;
static void  bsTreeCellSize2   ()

{
  if(!bsxxx)
    return ;

  bsxxx->size = 0;

  if(bsxxx->down) 
    {
     bsxxx = bsxxx->down ;
     bsTreeCellSize2() ;
     bsxxx = bsxxx->up ;
     bsxxx->size += sizexxx ;
   }

  if(bsxxx->right) 
    {
     bsxxx = bsxxx->right ;
     bsTreeCellSize2() ;
     bsxxx = bsxxx->up ;
     bsxxx->size+= sizexxx ;
   }

  if  (bsxxx->key<=_LastC)
    {
      if(bsxxx->bt && bsxxx->bt->cp)
	{
	  register int i = strlen(bsxxx->bt->cp) ;
	  if(i > NODEX * BNODEMAX /2)
	    {
	      sizexxx = bsTreeBreakComment(bsxxx);
	      return ;
	    }
	  else 
	    { if (i == 0)
		bsxxx->size += 2; /* SRK - empty string takes two also */
	      else
		bsxxx->size+=1+(i+NODEX-1)/NODEX;
	    }
	}
      else   /* a null comment occupies 2 keys, sorry */
	  bsxxx->size+=2;
    }

  else if(bsxxx->key<=_LastN)
    bsxxx->size += 2 ;

  else
    bsxxx->size += 1 ;  /* generic case of a KEY */

  sizexxx = bsxxx->size ;
  return ;
}

/******************************************************************/
                 /* calls bsTreeBreakComment */
static int    bsTreeCellSize    (BS bs)
{
  if(!bs)return(0);

  chrono("bsTreeCellSize") ;
  bsxxx = bs ;
  bsTreeCellSize2() ;  

  chronoReturn(); return(bs->size);
}
/**************************************************************/
static int  bsTreeBreakComment(BS bs)
{
 char * old = bs->bt->cp,
      * line,
      * cq ;
 BS bs1, bsu;
   
 int n ;

 chrono("bsTreeBreakComments") ;

 uLinesText(old, (BNODEMAX * NODEX)/ 2);
 line = uPopLine(old) ;

 while(TRUE)
   {
     cq = messalloc(strlen(line) + 1);

     strcpy(cq, line);
     if (!bs->bt)
       bs->bt = BTalloc() ;
     bs->bt->cp = cq;
     n = 2+(strlen(bs->bt->cp)+NODEX-1)/NODEX;  /* michel  was 1+.. */
     if (bs->down)
       n += bs->down->size ;
     if (bs->right)
       n += bs->right->size ;
     bs->size = n ;
     
     line = uPopLine(old);
     if (!line)
       break;
     bs1 = BSalloc();

     bs1 -> key = bs->key ;
     bs -> key = _NextC;
     
     bs1->up = bs->up;
     bs->up = bs1;
     bs1->down = bs;       /* move the right hook to the top */
     bs1->right = bs->right ;
     if(bs1->right)
       {
	 bs1->right->up = bs1 ;
	 bs->size -=  bs->right->size ;
       }
     bs->right = 0 ;

     bsu = bs1->up;
     if (bsu)
       {
	 if (bsu->down == bs) bsu->down = bs1;
	 else
	   if (bsu->right == bs) bsu->right = bs1;
	   else
	     messcrash("link missing in bsTreeBreakComment");
       }
     bs = bs1;
   }
 messfree(old);
 bsxxx = bs ;
 chronoReturn(); return n;
}

/**************************************************************/
static void bsTreeUnbreakComment(BS bs, BS bs1)
{

 char * u = bs->bt ? bs->bt->cp : 0 ,
      * v = bs1->bt ? bs1->bt->cp : 0 ,
      * cq ;
 int n = ( u ? strlen(u) : 0 )  + ( v ? strlen(v) : 0 ) ;    

 chrono("bsTreeUnbreakComments") ;

 cq = messalloc(n + 1);
 *cq = 0;
 if(u)
   {
     strcat(cq,u);
     messfree(bs->bt->cp);
   }
 if(v)
   {
     strcat(cq,v);
     messfree(bs1->bt->cp);
   }

 
 if (!bs->bt)
   bs->bt = BTalloc() ;
 bs->bt->cp = cq;
                 /* The right hook is already on bs */
 if ((bs->down = bs1->down)) /* i do mean =, not == */
   bs->down->up = bs ;
 bs1->down = bs1->right =  bs1->up = 0;
 BSfree(bs1);
 chronoReturn() ;

}

/**************************************************************/
      /*note that if b0=0 we do not read bs->down */

static BS  bsTreeRead (BP bp,NODE nn,BS b0, BOOL doUnbreakComment)
{
 NODEP r=bp->n+nn ;
 BS bs=BSalloc() ;
 BS bs1 ;

 chrono("bsTreeRead") ;

 bs->up=b0;
#ifdef ACEDB4
 bs->key=maybeSwapKEY(r->ck.key);
#else
 bs->key=r->ck.key;
#endif
                                    /* down hook */
 bs->down = (b0 && r->d1) ? 
   bsTreeRead(bp,r->d1,bs,doUnbreakComment) : NULL;

 if (bs->key<=_LastC)
   {
     if(r->d2)
       {
	 Bnode2str(BSbuffer,bp,&r);
	 bs->bt = BTalloc();
	 bs->bt->cp = messalloc(strlen(BSbuffer)+1);
	 strcpy(bs->bt->cp,BSbuffer);
	 
         /* special right hook for compatibility with earlier version*/
	 bs->right = r->d1  ? 
	   bsTreeRead(bp,r->d1,bs,doUnbreakComment) : NULL;
       }
     if(    doUnbreakComment
        && (bs1 = bs->down)
        && (bs1->key == _NextC) )
        bsTreeUnbreakComment(bs, bs1) ;
     chronoReturn(); return(bs);
        /* this call may have changed r1 */
   }

 else  if(bs->key<=_LastN)
   {           /* In a number a BS cell corrresponds to 2 nodes */
     nn=r->d2;
     r = bp->n + nn ; /* Thus the right hook
			 will start from the second cell */
#ifdef ACEDB4
     bs->n.i  = maybeSwapInt(r->ck.x.i) ;
#else
     bs->n = r->ck.x ;
#endif
     if(bs->key == _continuationKey)
       {
	 bsTreeReadCont(&bs) ;
	 chronoReturn(); return(bs);
       }
   }

                                                       /* right hook */
    bs->right = r->d2  ? bsTreeRead(bp,r->d2,bs,doUnbreakComment) : NULL;

    chronoReturn(); return(bs);
}

/**************************************************************/
                 /* replaces *bsp by the top
                    of the corresponding tree
                    freeing the relevant cells
                    */

static void  bsTreeReadCont(BS *bsp)
{
  NODE nn;
  BP bp;
  BS bs = *bsp,
     up = bs->up,
     bs1 = 0,
     bs2 = 0;

  chrono("bsTreeReadCont") ;

  bp = blockGetContinuation(bs->n.i) ;
  nn= bp->hat.top ;
  bs1=bsTreeRead(bp,nn,(BS)0,TRUE);

  if(bs1)
    bs2 = bs1->right;
  if(!bs2)
       messcrash("Anomaly  bs2 =0 in bsTreeReadCont " );
  if(!up || bs->down || bs->right )
       messcrash("Anomaly in bs in bsTreeReadCont ");
  bs2->up = up;
  BSfree(bs);
  BSfree(bs1);
  *bsp = bs2;
  chronoReturn();
}

/**************************************************************/

static BP  bsTreeFindBlock  (BS  bs, KEY *kkp)
{
  KEY key = bs->key, kk, k2 ;
  int
    freecells, n1,
    ncells   = bs->size,	/* number of cells needed to store bs */
    isold    = iskeyold (key),
    ispruned = FALSE;
  BP bp;
  BS bs2;
  NODE nn ;
  NODEP r;
  
  chrono("bsTreeFindBlock") ;

  if (isold || ncells > BNODEMAX/2)
    kk = key ;
  else				/* find an existing block */
    kk = blockfriend (key) ;
  
  if (isold || iskeyold(kk))
    Bget (&bp, &nn, kk) ; /* *bp,*nn becomes the origin of the branch */
  else
    { blockpinn (kk, &bp) ;
      nn = 0 ;
      Binit (bp) ;
    }
				/* bp is pinned now */
  if (isold && nn)
    { Bprune (bp, nn, 0) ;
      ispruned = TRUE ;
    }
  
	/**** 940802: IMPORTANT CHANGE HERE (I think) *****/
  if (bp->hat.top)		/* something left in the block */
    { freecells = Bfreelen (bp) ;
      if (ncells > freecells)
	{ if (ncells < BNODEMAX/2) /* stay shared */
	    { r = bp->n + bp->hat.top; /* find the top object */
	      k2 = kk ; 
#ifdef ACEDB4
	      kk = maybeSwapKEY(r->ck.key) ;
#else
	      kk = r->ck.key ;
#endif
	      blockunpinn (k2) ;
	      Bget (&bp, &nn, kk) ;
	      nn = bp->hat.top ;
	      n1 = Bbranchlen (bp, nn) ;
	      while (ncells + n1 > BNODEMAX/2)
		{ r = bp->n + nn ; nn = r->d1 ;
		  if (!nn) break;
		  n1 = Bbranchlen (bp, nn) ;
		}
	      if (nn)
		{ bs2 = bs ;
		  while (bs2->down) bs2 = bs2->down ;
		  bs2->down = bsTreeRead (bp, nn, bs2, FALSE);
		  Bprune (bp, nn, TRUE) ;
		  ispruned = TRUE ;
		}
	    }
      
	  if (ispruned)
	    blockrewrite (kk) ;
	  else 
	    blockunpinn (kk) ;
      
	  kk = key ;
	  blockreallocate (kk, &bp) ;
	  Binit (bp) ;
	}
    }
  
  *kkp = kk ;
  chronoReturn () ;
  return bp ;
}

/**************************************************************/
     /* Removes key from cache1, hence from disk. Needed by bsFuseObjects */
void bsTreeKill  (KEY key)
{
  BP bp;
  NODE nn ; 
  
  chrono("bsTreeKill") ;
  
  if (!iskeyold(key))
    return ;
 
  Bget(&bp,&nn,key);   /* *bp,*nn becomes the origin of the branch*/
  if(nn)
    Bprune(bp,nn,0);
  
  if (bp->hat.top)   /* There is something else on the block */
    { NODEP r ; KEY kk ;

      blockunpinn(key);
      r=bp->n+bp->hat.top;   /*Find the top object*/
#ifdef ACEDB4
      kk=maybeSwapKEY(r->ck.key);
#else
      kk=r->ck.key;
#endif
      Bget(&bp,&nn,kk);
      
      blockSetEnd(bp) ;    /* discard anything further down */
      blockrewrite(kk) ;
    }
  else
    blockSetEmpty(bp) ;
 lexkill (key) ;           /* discard reference from lex1 */
 chronoReturn() ;
}

/**************************************************************/

static void bsTreeStore2 (BP bp, KEY kk, BS bs)
{
  NODE nn,nn2;
  NODEP r;

  chrono("bsTreeStore2") ;
  if (bs->size > Bfreelen(bp))
    { bsTreeDump(bs) ; 
      messcrash ("Overflow in bsTreeStore2 (%s): bs->size = %d, Bfreelen = %d\n",
		 name(kk), bs->size, Bfreelen(bp)) ;
    }

  nn=bsTreeSt2(bs,bp);
  nn2=nn;
  while(r=bp->n+nn2,r->d1) nn2=r->d1;
  r->d1=bp->hat.top;
  bp->hat.top=nn;
  
  bsTreePrune(bs);
  chronoReturn() ;
}

/**************************************************************/

static void bsTreeStoreContinuation  (KEY key, BP *bpp, BS  bs)
{ NODE nn ;
  chrono("bsTreeStoreContinuation") ;
  
  blockSetNext(bpp) ;
		/******* IMPORTANT CHANGE HERE ********/
  if ((*bpp)->hat.h.disk)	/* reused, not grabbed */
    { BLOCKHEADER h = (*bpp)->hat.h ; /* save disk header info */
      Binit (*bpp) ;
      (*bpp)->hat.h = h ; /* restore disk linking */
      (*bpp)->hat.top = 0 ;
      (*bpp)->hat.free = 1 ;
    }
  else
    Binit (*bpp) ;

  if (bs->size > Bfreelen(*bpp))
    { bsTreeDump(bs) ; 
      messcrash ("Overflow in bsTreeStoreContinuation (%s): bs->size = %d, Bfreelen = %d\n",
		 name(key), bs->size, Bfreelen(*bpp)) ;
    }

  nn = bsTreeSt2 (bs, *bpp) ; /* 2 instructions needed si *bpp change */
  (*bpp)->hat.top = nn ;
  
  bsTreePrune (bs) ;
  chronoReturn () ;
}

/************************************************************************/

static NODE bsTreeSt2 (BS bs,BP bp)
{
  NODEP r = Bnewnode(bp) ;

#ifdef ACEDB4
  r->ck.key=maybeSwapKEY(bs->key);
#else
  r->ck.key=bs->key;
#endif

  if(bs->down) r->d1=bsTreeSt2(bs->down,bp);

  if((bs->key)<=_LastC)
    {  NODEP rnew = r ;  /* Bstr2node will grab additional nodes */
       Bstr2node(bs,bp,&rnew);
           /* comments  support right hooks in funny way */
       if(bs->right)
	 rnew->d1 = bsTreeSt2(bs->right,bp) ;
     }
  
  else if((bs->key)<=_LastN) 
	{	     /* grab a second node to write the Union */
	  NODEP rnew = Bnewnode(bp) ;

#ifdef ACEDB4
	  r->ck.key = maybeSwapKEY(bs->key) ;
	  rnew->ck.x.i = maybeSwapInt(bs->n.i) ;
#else
	  r->ck.key = bs->key ;
	  rnew->ck.x = bs->n ;
#endif
	  r->d2 = (NODE) (rnew  - bp->n) ;
	  if(bs->right) 
	    rnew->d2=bsTreeSt2(bs->right,bp);
	}
  
  else                 /* standard key */
    if(bs->right) r->d2=bsTreeSt2(bs->right,bp);
  
  return (NODE) ( r - bp->n) ;
}

/************************************************************************/
/* Next two routines recursively unpack/pack the timestamp information. */
/* As usual, they loop over a column of bs nodes, and recurse right.    */
/* In the new bs -> array packing, could be done as data are packed.    */
/************************************************************************/

static void bsUnpackTimeStamps (BS bs, KEY currStamp)
{
  while (bs)
    if (class(bs->key) == _VUserSession)
      { currStamp = bs->key ;
	if (bs->up->right == bs)
	  bs->up->right = bs->down ;
	else
	  bs->up->down = bs->down ;
	if (bs->down)
	  bs->down->up = bs->up ;
	{ BS condemned = bs ; bs = bs->down ; BSfree (condemned) ; }
      }
    else
      { bs->timeStamp = currStamp ;
	if (bs->right)				/* recursion */
	  bsUnpackTimeStamps (bs->right, currStamp) ;
	bs = bs->down ;
      }
}

static void bsPackTimeStamps (BS bs, KEY currStamp)
{
  while (bs)
    { if (bs->timeStamp != currStamp) /* add in a timestamp */
	{ BS new = BSalloc() ;
	  currStamp = bs->timeStamp ;
	  new->key = currStamp ;
	  new->up = bs->up ;
	  if (bs->up->right == bs)
	    bs->up->right = new ;
	  else
	    bs->up->down = new ;
	  bs->up = new ;
	  new->down = bs ;
	}
      if (bs->right)
	bsPackTimeStamps (bs->right, currStamp) ;
      bs = bs->down ;
    }
}

/************************************************************************/
/************************************************************************/
#endif /* !ACEDB5 */