/*static char *SCCSID = "@(#)delete.c	6.1 90/11/18";*/
/*static char *SCCSID = "@(#)delete.c 13.4 90/03/05";*/
/*
 * This file is based on the delete.c in the PINBALL server tree with
 * the last two modification entries of:
 *

06-21-89@15:15	KARENWH1 in	 delete.c     add copyright message
06-21-89@19:05	GORDON4 in	delete.c     handle no heap space available

 */

#include "ldefs.h"
#include "ltypes.h"
#include "globals.h"
#include <pr_chk.h>
#include <pr_fsys.h>

/*  if two sibling blocks together are less full then this, merge them
 *	This number is choosen carefully to guarantee that when we identify
 *	the record which will seperate the lead and trailing subordinate blocks
 *	we're guaranteed that there is at least one record in the lead and trailing
 *	block.	This saves us from having special cases.  */

#define MERGETHRESHOLD (2*(MAX_DIRENT + FIELDOFFSET(struct DIRBLK, bFirst)) + DIRSIZP + sizeof(BYTE))

/*	Get address of first directory entry given a dirblock address */

#define FIRSTENT(t) (( DIRENT *)(&t->bFirst))

#define DIRBLK_EMPTY(x) (FIRSTENT(x)->fFlags & DF_END)

/*	Get next dirent given the address of the previous one */

#define NEXTREC(p) (( DIRENT *)(p->cchThisEntry + (char *)p))

#define STRUCTOFF(structure, field)  ((int) &(((struct structure *) 0)->field))

#define GET_BTP(rec)  (*(unsigned long *)((char *)rec-SIZE_DIR_BTP+rec->cchThisEntry))

#define GET_END(rec)  ( ( DIRENT *)( (char *)rec + rec->offulFirstFree - sizeof (struct DIRENT)-(FIRSTENT(rec)->fFlags & DF_BTP)))

#define ISLEAF(db) ((FIRSTENT(db)->fFlags & DF_BTP) == 0)

/**	Adjust - Adjust Directory Block Contents
 *
 *	Adjust is called when a directory block contains too few
 *	entrys.  It adjusts the situation by shuffling over entries
 *	from the before or after blocks at this level.	If this
 *	isn't sufficient then this directory block is merged with
 *	either the before or after one and the parent dirblk is
 *	edited.
 *
 *	If we're the topmost block in the BTREE and we're zero length
 *	we just delete that block and shorten the tree one level.
 */

int  adjust (sector)
    long sector;
{
    register  DIRBLK *targblk;	       /* pointer to block we're to adjust */
     BUFNODE *targbufp;	      /* pointer to target cache block */
     BUFNODE *bufp2;	      /* scratch pointer to buffer header */
     FNODE  *fnodep;
     DIRENT *forerec, *backrec;


    targblk = ( DIRBLK *)readbuf(sector, &targbufp);

    ERRRET (targblk, trap);	/* return if hard error */

    if (targblk->culChange & 1)
      if (DIRBLK_EMPTY(targblk)) {

	/* we're the topmost block and we're zero length..
	 * remove this block and promote our sole descendent
	 */

	long fnodesec;
	long childsec;

	targblk->sig = 0;			/* wipe his signature */
	fnodesec = targblk->lsnParent;
	childsec = GET_BTP(FIRSTENT(targblk));	/* block # to be promoted */
	targbufp->bDirtMask = TRUE;		/* dirtied by sig removal */
	_FreeDB (targblk->lsnThisDir);		/* release this block */
	fnodep = ( FNODE *)readbuf(fnodesec, &bufp2);
	ERRRET (fnodep, trap);		/* return if hard error */
	fnodep->fst.a.aall[0].lsnPhys = childsec;     /* fnode points to new top guy */
	bufp2->bDirtMask = TRUE;		/* dirty fnode */
	targblk = ( DIRBLK *)readbuf(childsec, &targbufp);
	ERRRET (targblk, trap);		/* return if hard error */
	targblk->lsnParent = fnodesec;		/* point new top back at FNODE */
	targblk->culChange |= 1;			/* mark new top as top */
	targbufp->bDirtMask = TRUE;	/* we'll dirty directory sector */
	return(0);
      }
#ifdef	DEBUG
	else trap();	/* we're topmost but not empty, shouldn't be called */
#endif

    /*	We're not topmost.  Find our forward and backward siblings
     *	and the parent records that belong at the junction between this
     *	record and those siblings
     *
     *	The "target" refers to the directory block we were called to adjust
     *	(i.e., it's too small).  "node" refers to the parent directory block.
     *	We know that we have a parent because the topmost guy can't become zero
     *	length and require adjustment, and our callers won't ask us to do a
     *	performace optimization balancing on the root node.
     *	"fore" refers to the sibling block with entrys before the target entrys.
     *	"back" refers to sibling with entrys after the target entrys.
     */

    {
     DIRBLK *foreblk;	      /* first of two blocks */
     DIRBLK *backblk;	      /* second of two blocks */
     DIRBLK *nodeblk;	      /* parent block */
    long targsize, backsize, foresize;
     BUFNODE *nodebufp;	      /* pointer to target cache block */
     BUFNODE *forebufp;
     BUFNODE *backbufp;

    targbufp->cusHolds++;
    targsize = targblk->offulFirstFree;
    nodeblk = ( DIRBLK *)readbuf(targblk->lsnParent, &nodebufp);
					     /* read node block */
    ERRGOTO(nodeblk, he130, trap);

    nodebufp->cusHolds++;		     /* hold node block */
    /*printf ("Target block = %06lx, targsiz = %d, nodeblk = %06lx\n", targblk, targsize, nodeblk);*/

    findpnode (nodeblk, sector, &backrec, &forerec);

    /*	Compute size of preceeding peer block. */

    if (backrec) {
	backblk = ( DIRBLK *)readbuf(GET_BTP(backrec), &backbufp);
					    /* read back block */
	ERRGOTO (backblk, he120, trap);
	backsize = backblk->offulFirstFree + backrec->cchThisEntry;
	backbufp->cusHolds++;
    } else
	backsize = 0;
    /*printf ("Backsize = %d, backblk = %x\n", backsize, backblk);	*/

    /* Compute size of following peer block */

    if ((forerec->fFlags & DF_END) == 0) {
	foreblk = ( DIRBLK *)readbuf(GET_BTP(NEXTREC(forerec)), &forebufp);
					    /* read fore block */
	ERRGOTO (foreblk, he110, trap);		/* if hard error */
	foresize = foreblk->offulFirstFree + forerec->cchThisEntry;
	forebufp->cusHolds++;
    } else
	foresize = 0;
    /*printf ("foresize = %d, foreblk = %x\n", foresize, foreblk); */

    /* Now decide whether we'll balance with the largest or merge with the smallest */

    if (backsize == 0) {
	/* we gotta balance or merge with the fore guy, there is no back */

	/*printf ("Backsize==0; forsize %d + targsize %d = %d\n", foresize, targsize, foresize+targsize); */
	if ((foresize + targsize) > MERGETHRESHOLD)
		balance (targblk, targbufp, foreblk, forebufp, nodeblk, nodebufp, forerec);
	else
		join	(targblk, targbufp, foreblk, forebufp, nodeblk, nodebufp, forerec);
    } else
    if (foresize == 0) {
	/* we gotta balance or merge with the back guy, there is no fore */
	/*printf ("foresize==0; baksize %d + targsize %d = %d\n", backsize, targsize, backsize+targsize);*/
	if ((backsize + targsize) > MERGETHRESHOLD)
		balance (backblk, backbufp, targblk, targbufp, nodeblk, nodebufp, backrec);
	else
		join	(backblk, backbufp, targblk, targbufp, nodeblk, nodebufp, backrec);
    } else

    /* we get a choice of merging or balancing.  We'll balance if we can, merge elsewise */

    if (backsize > foresize) {
	/*printf ("mid adjust, back=%d fore=%d targ=%d\n", backsize, foresize, targsize);
	  printf ("  back > fore: baksize %d + targsize %d = %d\n", backsize, targsize, backsize+targsize);*/
	if ((backsize + targsize) > MERGETHRESHOLD) {
	    forebufp->cusHolds--;		/* not needed anymore */
	    balance (backblk, backbufp, targblk, targbufp, nodeblk, nodebufp, backrec);
	} else {
	    backbufp->cusHolds--;		/* not needed anymore */
	    join    (targblk, targbufp, foreblk, forebufp, nodeblk, nodebufp, forerec);
	}
    } else {
	/*printf ("mid adjust, back=%d fore=%d targ=%d\n", backsize, foresize, targsize);
	printf ("  Back<=fore:  forsize %d + targsize %d = %d\n", foresize, targsize, foresize+targsize); */
	if ((foresize + targsize) > MERGETHRESHOLD) {
	    backbufp->cusHolds--;		/* not needed anymore */
	    balance (targblk, targbufp, foreblk, forebufp, nodeblk, nodebufp, forerec);
	} else {
	    forebufp->cusHolds--;		/* not needed anymore */
	    join    (backblk, backbufp, targblk, targbufp, nodeblk, nodebufp, backrec);
	}
     }
  return(0);

/*	Hard Error.  forebufp held if (foresize) */

/*
he100:
*/
	if (foresize)
		forebufp->cusHolds--;

/*	Hard Error.  backbufp held if (backsize) */

he110:	if (backsize)
		backbufp->cusHolds--;

/*	Hard error - nodebufp held */

he120:	nodebufp->cusHolds--;

/*	hard error - targbufp held */

he130:	targbufp->cusHolds--;
	return(1);
  }
#ifdef DEBUG
	trap();			/* shouldn't come here */
#endif
}


/**	Insert - Insert Record
 *
 *	Insert inserts a record into a directory block.
 *	We know that the block isn't a leaf block because
 *	insertions there are only done by LDE() and he does them
 *	in assembly language for speed.  We're called to insert
 *	records into non-leaf blocks because that's a rarer situation.
 *	(Note that LDE() does some non-leaf insertion too; the easy
 *	 common case)
 *
 *	Note that if we're doing an insert as a result of a split, our
 *	new record will point to the first of the new dirblk pair, and
 *	will go into the parent dirblk right before the guy who used
 *	to point to that block (before we split the last part off).
 *	In this case, the newdp argument specifies the new downpointer
 *	for this record which will immediately follow us.
 *
 *	If there's enough room then it's easy; we just make a hole and
 *	copy it in.  Otherwise, we'll split this block.
 *
 *	The caller has held the block we're called to insert in.
 *	We leave it held.  Caller must have locked the SBDIR.
 */

int  insert (blkptr, blkbufp, newrec, newdp)
     DIRBLK *blkptr;	  /* pointer to insert dirblk */
     DIRENT *newrec;	  /* pointer to new DIRENT */
     BUFNODE *blkbufp;	  /* pointer to dirblk BUF */
    long newdp;			/* sector # of 2nd half if split insertion */
				/*   Zero if not a splitting insertion */
{

	register  DIRENT *pdirent;
	 DIRENT *promote;	  /* buffer for promotion entry */
	 DIRBLK *botblk;	  /* bottom half after a split */
	 BUFNODE *botbufp;	  /* buffer header for new bottom half */

/*	See if we can just do a simple insert of the record */

	_chkheld (blkbufp);
	/* printf ("In Insert, blk=%06lx buf=%06lx new=%06lx\n", blkptr, blkbufp, newrec); */
	pdirent = FIRSTENT(blkptr);

/*	Scan looking for the right spot to insert */

	while (_namecmp(pdirent, newrec) == 0)
		pdirent = NEXTREC(pdirent);

/*	We've got our spot.  Adjust the following down pointer */

	if (newdp) {
		/*printf ("in newdp %06lx %06lx %06lx\n",
		       blkptr, pdirent, newrec); trap(); */
#ifdef DEBUG
	    if (GET_BTP(newrec) != GET_BTP(pdirent)) {
		printf ("insert: downpointers don't match %06lx %06lx %06lx\n",
		       blkptr, pdirent, newrec);
		trap();
	    }
#endif
	    GET_BTP(pdirent) = newdp;
	}

/*	Insert new record if we've got room */
/*	Mkroom updates the culChange field    */

	if ((long)chk_makeroom ((USHORT)newrec->cchThisEntry, blkptr, (char *)pdirent)) {
		memmove (pdirent, newrec, (size_t)newrec->cchThisEntry);  /* copy in */
		blkbufp->bDirtMask = TRUE;			 /* mark dirty */
		return(0);		/* inserted */
	}

/*	We weren't able to insert.  We've got to split this block
 *	Splitdir takes care of the dirty bits and the CCNT field.
 *	Splitdir puts a second hold on the cache block
 */

#ifdef DEBUG
	GET_BTP(pdirent) = GET_BTP(newrec);	  /* temporarily restore obsolete
			  downpointer value so that debug code won't trap */
#endif
	/*printf ("======= INSERT - gotta split ========\007\007\n");*/
	promote = (PDIRENT)malloc(sizeof (DIRENT) + 256);
	blkbufp->bDirtMask = TRUE;
	botblk = chk_split_dir (blkptr, blkbufp, (PUCHAR)promote);

	/* find which half our insert guy fits into and put him there
	 * Both the topblk and the botblk are now held */

	botbufp = _adr_to_bhdr(botblk);
	_chkheld(blkbufp);		_chkheld(botbufp);

	if (_namecmp(promote, newrec))
		insert (blkptr, blkbufp, newrec,newdp);	    /* goes in 1st half */
	else
		insert (botblk, botbufp, newrec,newdp);	    /* goes in 2nd half */

	/* for all the guys in the 2nd half, read them in and update their
	 * parent pointer */

	_chkheld(_adr_to_bhdr(botblk));
	FixUp (FIRSTENT(botblk), botblk->lsnThisDir, -1);

	if ((blkptr->culChange &1) == 0) {

	    /* we just split a non-root block, so promote to it's parent */

	    blkbufp->cusHolds--;			    /* release second hold on top */
	    botbufp->cusHolds--;			    /* release the bottom half */

	    /* recursively call ourselves and insert into our parent */

	    newdp = botblk->lsnThisDir;
	    /*printf ("New down pointer botblk = %lx\n", newdp);*/
	    blkptr = ( DIRBLK *)readbuf(botblk->lsnParent, &blkbufp);
	    ERRGOTO (blkptr, ins100, trap);	/* if hard error */
	    blkbufp->cusHolds++;
	    insert (blkptr, blkbufp, promote, newdp);	 /* insert record into parent */
	    blkbufp->cusHolds--;
	    free ((char *)promote);
	    return(0);

ins100:	    free ((char *)promote);	/* hard error */
	    return(1);
	}  else {

	     BUFNODE *newrootbufp;
	     DIRBLK  *newrootblk;

	    /* we just split the root dirblk, so we have to make a new root
	     * and update the directory FNODE and SBDIR structure
	     *	NewDirRoot releases one hold each on the blkptr and botblk */

	    /*printf ("Insert - create new dirblk.  Old one was %06lx %06lx\n",
		    blkptr, promote); */
	    blkptr->culChange--;			/* remove flag from old root */
	    NewDirRoot (promote, blkptr, botblk, &newrootbufp, &newrootblk);
#if 0
		trap();		/* hard error */
		newrootbufp->cusHolds--;		    /* unhold root */
		free ((char *)promote);
		return(0);
	    }
#endif
	    newrootbufp->cusHolds--;		/* unhold root */
	    newrootbufp->bDirtMask = TRUE;	     /* mark dirty */
	    free ((char *)promote);
	    return(0);
	}
#ifdef	DEBUG
	trap();		/* shouldn't come here */
#endif
}


/**	Balance - Balance Node Contents
 *
 *	Balance is called to balance the contents of two
 *	directory blocks which are on the same level, and ajacent,
 *	in the BTREE.  The contents are split evenly between the
 *	two.
 *
 *	There is a record in the superior directory
 *	block which is the dividing record between the two blocks.
 *	This record has to be included in the balancing.  The balancing
 *	will replace this record with another one from the larger
 *	block which may cause the parent to overflow.
 *
 *	Balancing can be difficult because of the differing record sizes.
 *	For example, the last record in the botblk may be so large that
 *	the most balanced configuration is to promote that record and to
 *	leave botblk empty.  We've got to check for this stuff and make
 *	sure that it doesn't happen.  The rules are:
 *
 *	Balance will not return any DIRBLK with zero non-END entries
 *	If Balance is called with topblk or botblk empty, the other block must
 *	hold at least two entries so that a non-zero balance can be achieved.
 *	This stuff is simplified by the MERGETHRESHOLD value which is computed
 *	such that we won't try to balance a grouping with insufficent records.
 *
 *	The caller has held all three blocks in the process of getting them in.
 *	we'll release these holds before we finish or request any more buffer
 *	activities.
 */

#define DIRENDSIZE (sizeof ( DIRENT) + SIZE_DIR_BTP - BTPadj)

int  balance (topblk, topbufp, botblk, botbufp, nodeblk, nodebufp, nodeent)
     DIRBLK *topblk;
    register  DIRBLK *botblk;
     DIRBLK  *nodeblk;
    register  DIRENT *nodeent;
     BUFNODE *topbufp, *botbufp, *nodebufp;
{
    int i;	    /* scratch value */
    int BTPadj;	    /* = size DIR_BTP iff dirblks are leafs */
    long middown;   /* downpointer value from nodeent */

  /*printf ("In Balance Top=%06lx/%06lx Bot=%06lx/%06lx Node=%06lx/%06lx\n\tnodeent=%06lx\n",
	topblk, topbufp, botblk, botbufp, nodeblk, nodebufp, nodeent); */

    /* although possible, it's rare that we won't molest all three DIRBLKs,
     * so edit theirn CCNT fields. */

    topblk->culChange += 2;
    botblk->culChange += 2;
    nodeblk->culChange += 2;

    _chkheld(topbufp);
    _chkheld(botbufp);
    _chkheld(nodebufp);

    /* Set BTPadj to sizeof DIR_BTP if this is a leaf block, because we'll
     * have to adjust the size of records that we promote/demote. */

    BTPadj = ISLEAF(botblk)? SIZE_DIR_BTP : 0;
    middown = GET_BTP(nodeent);

    /*	Find the new midpoint.	Compute the length of all of the records
     *	subtracting out the end records, but keeping the DIRBLK headers */

   /*printf ("    balance %ld + %ld + %ld to ",
	topblk->offulFirstFree-DIRENDSIZE-STRUCTOFF(DIRBLK, bFirst),
	nodeent->cchThisEntry,
	botblk->offulFirstFree-DIRENDSIZE-STRUCTOFF(DIRBLK, bFirst)); */

    i = (int)((topblk->offulFirstFree + botblk->offulFirstFree + nodeent->cchThisEntry
		-2*DIRENDSIZE)/2);

#ifdef	DEBUG
    if (DIRBLK_EMPTY(botblk))
	 if (i > (int)(topblk->offulFirstFree - DIRENDSIZE -1) )
	     trap();		/* bad merge layout */
#endif
    if (i < (int)(topblk->offulFirstFree - DIRENDSIZE)) {

	 DIRENT *pdent;		  /* pointer to DIRENT to promote */
	 DIRENT *ndent;		  /* pointer to 1st DIRENT to move to endblk */
	 DIRENT *demotent;	  /* pointer to demoted nodeent in botblk */
	int topmovsiz;			/* cnt of topblk bytes to botblk */
	long pdent_down = 0;		/* BTP down pointer values */
#ifdef DEBUG
	long botnewsiz;			/* used for debug printf */
#endif

	/* the top block is the one that will give up entries.	Find the
	 * guy that will become the new middle record
	 *
	 *	 TopBlk
	 *		 records that stay	 (must be at least 1)
	 *
	 *   pdent ->	 record that promotes	 (exactly 1)
	 *
	 *   ndent ->	 records that move to botblk  (0 or more)
	 *
	 * MidBlk
	 *	      middle record moved to botblk
	 *		      downpointer to TopBlk
	 *
	 *	 BotBlk
	 *		 [records from TopBlk go here]
	 *
	 * demotent->	 [ demoted MidBlk record here]
	 *
	 *		 any existing Botblk records
	 *
	 */

	i -= STRUCTOFF (DIRBLK, bFirst);
	ndent = FIRSTENT(topblk);
	/*printf ("TopBlk will give entries to the bottom, i=%ld\n",i);*/

	while (i > 0) {
		pdent = ndent;
		ndent = NEXTREC (pdent);
		i -= pdent->cchThisEntry;
	}
#ifdef	DEBUG
	if (pdent == FIRSTENT(topblk))
		trap();		/* bad computation - would empty us */
#endif

	/* Copy the remaining records into the bottom block.
	 *
	 *  If Topblk and Botblk are leaf nodes:
	 *
	 *     1.  The pdent record, being promoted to nodeblk, is extended
	 *	   to have a BTP and points to the topblk.
	 *
	 *     2.  The nodeent record is stripped of it's downpointer when
	 *	   it's demoted
	 *
	 * if TopBlk and Botblk are not leaf nodes
	 *
	 *     1.  The downpointer for the topblk end record
	 *	   is given to the demoted midblk record.
	 *
	 *     2.  The middle record's old down pointer is
	 *	   picked up by the pdent record.
	 *
	 *     3.  The pdent record's old down pointer becomes the topblk's
	 *	   end record down pointer.
	 *
	 *	Pdent = record to move into parent dirblk
	 *	ndent = first record to move to later block
	 */

	topmovsiz = (int)GET_END(topblk) - (int)ndent;

	if (BTPadj == 0) {	 /* top and bot are not leaf blocks */
		GET_BTP(nodeent) = GET_BTP (GET_END(topblk));  /* step #1 */
		pdent_down = GET_BTP(pdent);
	}

	/* Move the endblk stuff down, adjusting it's size.
	 * Move in the stuff from the topblk followed by the node record.
	 */

	/*printf ("Moving %ld topblk bytes and %ld noderec bytes\n",
		topmovsiz, nodeent->cchThisEntry-BTPadj); */

	chk_makeroom ((USHORT)((long)topmovsiz + (long)nodeent->cchThisEntry-BTPadj), botblk, (char *)FIRSTENT(botblk));
	memmove	(FIRSTENT(botblk), ndent, (size_t)topmovsiz);
	if (BTPadj == 0) {		/* adjust descendents, if we have 'em */
	    _chkheld(_adr_to_bhdr(botblk));
	    FixUp (FIRSTENT(botblk), botblk->lsnThisDir, topmovsiz);
	}
	demotent = ( DIRENT *) ( (char *)&botblk->bFirst + topmovsiz);
	memmove	(demotent, nodeent, (size_t)((long)nodeent->cchThisEntry-BTPadj));
	if (BTPadj == 0) {
	    FixUp (nodeent, botblk->lsnThisDir, nodeent->cchThisEntry);
	} else {
	    demotent->cchThisEntry -= (short) BTPadj;
	    demotent->fFlags ^= DF_BTP;
	}

	/* Take out the old parent node record and replace with the promoted
	 * one, which is still sitting in topblk.
	 *
	 * we've already moved the record following pdent so we can go ahead
	 * and grow pdent to take a DIR_BTP record, if it didn't already have one
	 * Keep pdent accurate cause we'll use him to create our new END record
	 */

	_closeup (nodeblk, nodeent);
	if (BTPadj) {		/* topblk is a leaf */
		pdent->cchThisEntry += SIZE_DIR_BTP;
		pdent->fFlags |= DF_BTP;
	}
	GET_BTP(pdent) = middown;

	/* We're about to insert into the parent block.  This could involve disk
	 * I/O, so we'll release the bottom block cause we're done with it.
	 * we also release the node block because we're done with it; Insert
	 * can look after himself.  We keep the top block locked.
	 */

	/*printf ("Done with bottom guy at %06lx (top=%06lx node=%06lx)\n",
		botblk, topblk, nodeblk); */
#ifdef DEBUG
	botnewsiz = botblk->offulFirstFree - DIRENDSIZE-STRUCTOFF(DIRBLK, bFirst);
#endif

	botbufp->bDirtMask = TRUE;
	botbufp->cusHolds--;
	if (BTPadj == 0)
	    FixUp (pdent, nodeblk->lsnThisDir, pdent->cchThisEntry);
	insert (nodeblk, nodebufp, pdent, 0L);
	nodebufp->bDirtMask = TRUE;
	nodebufp->cusHolds--;

#ifdef DEBUG
	botbufp = nodebufp = ( BUFNODE *)0;
	botblk	= nodeblk  = ( DIRBLK *)0;
#endif

	/* We've copied all of our records around.  All that's left is to
	 * construct a new end record for the toprec and to adjust it's size
	 */

	memmove (pdent, GET_END(topblk), (size_t)GET_END(topblk)->cchThisEntry);
	if (BTPadj == 0) {
		GET_BTP(pdent) = pdent_down;
	}
	topblk->offulFirstFree = (int)pdent - (int)topblk + pdent->cchThisEntry;
	/*printf ("Finished with new top blk at %06lx\n", topblk);
	  printf ("%ld + %ld\n", topblk->offulFirstFree-DIRENDSIZE-STRUCTOFF(DIRBLK, bFirst), botnewsiz);*/

	topbufp->bDirtMask = TRUE;
	topbufp->cusHolds--;
	return(0);

    } else {

	/* The midpoint is not in the top block.
	 *
	 *   If it's in the middle record and the top record is empty then we
	 *   have to move one record into the top block.  Otherwise, we
	 *   do nothing.
	 */

	 DIRENT *pdent;		  /* pointer to DIRENT to promote */
	 DIRENT *ndent;		  /* pointer to 1st DIRENT to remain in endblk */
	 DIRENT *addspot;	  /* addspot point into topblk */
	int movecnt;			/* # of bytes to move to toprec */
	long topendBTP;			/* BTP value from topblk end record */

	/** The bottom block is the one that has to give up entrys.  We find
	 *  the bottom record that should become the parent node.
	 */

	i -= (int)(topblk->offulFirstFree - DIRENDSIZE + nodeent->cchThisEntry);	     /* i = offset into botrec */
	/*printf ("Bot Block will give.  New i = %ld\n", i);*/
	if (i < 0) {

	    /* the nodeent record is the mid point.  */
#ifdef	DEBUG
	    if (DIRBLK_EMPTY(topblk))
		trap();		/* internal error - can't be empty and mid */
#endif
		goto do_return;
	}

	/*	Find the record which should be promoted to middle.  Make
	 *	sure that we leave at least one record in this block */

	ndent = FIRSTENT(botblk);
#ifdef	DEBUG
	if (NEXTREC(ndent)->fFlags & DF_END) {
	    trap();	    /* error - bad format */
	}
#endif
	for (; i > 0; ) {
		pdent = ndent;
		ndent = NEXTREC (pdent);
		if ((ndent->fFlags & DF_END) || (NEXTREC(ndent)->fFlags & DF_END))
			break;
		i -= pdent->cchThisEntry;
	}

	/* We've got the bottom entrys in three groups - the part to be moved
	 * to the top record, the record to be promoted, and the records to
	 * remain.  Grow the top block and move the stuff into it
	 *
	 *	The promoted record takes the nodeent's down pointer.
	 *	If the two dirblks aren't leaf blocks, the old nodeent record
	 *	gets the downpointer from the topblk end record.
	 *	The downpointer from the record which is promoted to the parent
	 *	block is given to the top block end record.  No downpointer
	 *	manipulation is needed in the bottom record.
	 *
	 *	pdent = record to promote
	 *	ndent = record which will be first when we're done
	 *	botblk records until pdent are to be moved to topblk
	 */

	movecnt = (int)pdent - (int)botblk - STRUCTOFF (DIRBLK, bFirst);
	addspot = GET_END(topblk);
	topendBTP = GET_BTP(addspot);	 /* invalid if leaf node */
	/*printf ("Ready to move.  Movecnt=%lx topblk=%06lx botblk=%06lx nodeent=%06lx\n",
		movecnt, topblk, botblk, nodeent); */
	chk_makeroom ((USHORT)((long)movecnt + (long)nodeent->cchThisEntry - BTPadj), topblk, (char *)addspot);
	memmove	(addspot, nodeent, (size_t)((long)nodeent->cchThisEntry - BTPadj));
	if (BTPadj) {
		addspot->cchThisEntry -= (short) BTPadj;
		addspot->fFlags ^= DF_BTP;    /* strip down pointer */
	} else {
		GET_BTP(addspot) = topendBTP;
	}
	memmove	 (NEXTREC(addspot), FIRSTENT(botblk), (size_t)movecnt);
	if (BTPadj == 0)
	    FixUp (NEXTREC(addspot), topblk->lsnThisDir, movecnt);

	/* replace the parent node record with the one we're to promote.
	 *
	 * If we're balancing two leaf nodes, the record which is to be
	 * promoted will have to be lenghened to take a DIR_BTP entry.
	 * We can't lengthen it in place because that would damage
	 * the record following it (which will become the first record
	 * in the bottom block).  We could just mark it as longer
	 * and then fill in the value after it's been inserted, but
	 * due to possible splits it may be a pain finding the thing
	 * again after the insert.  So, we'll copy it to some heap
	 * space and work from there.
	 */

	{
		 DIRENT * temp;

		temp = (PDIRENT)malloc((size_t)pdent->cchThisEntry + SIZE_DIR_BTP);
		memmove (temp, pdent, (size_t)pdent->cchThisEntry);
		pdent = temp;
	}
	_closeup (nodeblk, nodeent);

	if (BTPadj) {			/* topblk is a leaf */
		pdent->cchThisEntry += SIZE_DIR_BTP;
		pdent->fFlags |= DF_BTP;      /* now has a down pointer */
	} else {
		GET_BTP(GET_END(topblk)) = GET_BTP(pdent);
		FixUp(GET_END(topblk), topblk->lsnThisDir, GET_END(topblk)->cchThisEntry);
	}
	GET_BTP(pdent) = middown;	/* set downpointer for promoted guy */
	topbufp->bDirtMask = TRUE;
	topbufp->cusHolds--;		/* we're done with the top block */
#ifdef DEBUG
	topbufp = ( BUFNODE *)0;
	topblk	= ( DIRBLK *)0;
#endif

	if (BTPadj == 0)
	    FixUp(pdent, nodeblk->lsnThisDir, pdent->cchThisEntry);
	insert (nodeblk, nodebufp, pdent, 0L);
	nodebufp->bDirtMask = TRUE;
	nodebufp->cusHolds--;
	free((char *)pdent);
#ifdef DEBUG
	nodebufp = ( BUFNODE *)0;
	nodeblk	 = ( DIRBLK *)0;
#endif

	/* Move up the remaining records from the bottom and adjust it's length
	 *
	 * ndent = directory entry which should become first
	 */

	botblk->offulFirstFree -= ((char *)ndent - (char *)&botblk->bFirst);  /* adjust length */
	memmove((PDIRENT)&botblk->bFirst,	 /* to the front */
	       ndent,			/* move from ndent */
	(size_t)(botblk->offulFirstFree - STRUCTOFF (DIRBLK, bFirst)));
	botbufp->bDirtMask = TRUE;
	botbufp->cusHolds--;
	return(0);

do_return:
	topbufp->bDirtMask = TRUE;	topbufp->cusHolds--;
	botbufp->bDirtMask = TRUE;	botbufp->cusHolds--;	     /* unhold these guys */
	nodebufp->bDirtMask = TRUE; nodebufp->cusHolds--;

	return(0);
    }
}



/**	Join - Join two Directory Blocks
 *
 *	Join is called when two ajacent directory blocks are
 *	below a size threshold.  They are joined together (along with
 *	their seperator node) and the seperator is removed from
 *	the parent block.
 *
 *	The caller guarantees that the two blocks, together with the
 *	middle parent record, will fit into one block.
 *
 *	Caller has held all three blocks.  The directory needs to be
 *	locked at the SBDIR level; caller will have handled this.
 */

int  join (topblk, topbufp, botblk, botbufp, nodeblk, nodebufp, nodeent)
     DIRBLK *topblk;
    register  DIRBLK *botblk;
     DIRBLK  *nodeblk;
    register  DIRENT *nodeent;
     BUFNODE *topbufp, *botbufp, *nodebufp;
{
	int BTPadj;	/* = size DIR_BTP iff dirblks are leafs */
	int botsiz;	/* size of records in bottom block */
	long endBTP;	/* BTP pointer of end record in topblk */
	 DIRENT *inpoint;	  /* insert point in topblk */

    /* We'll molest all three DIRBLKs,
     * so set their dirty bits and edit their CCNT fields. */

    _chkheld(topbufp);
    _chkheld(botbufp);
    _chkheld(nodebufp);

  /*printf ("In Join Top=%06lx/%06lx Bot=%06lx/%06lx Node=%06lx/%06lx\n\tnodeent=%06lx\n",
	topblk, topbufp, botblk, botbufp, nodeblk, nodebufp, nodeent); */
    topblk->culChange += 2;
    nodeblk->culChange += 2;

    /* Set xTPadj to sizeof DIR_BTP if this is a leaf block, because we'll
     * have to adjust the size of records that we promote/demote. */

    BTPadj = ISLEAF(botblk)? SIZE_DIR_BTP : 0;

    /* Make room in top block for the middle record and the botblk records */

    botsiz = (int)(botblk->offulFirstFree - DIRENDSIZE - STRUCTOFF (DIRBLK, bFirst));
    inpoint = GET_END(topblk);
    endBTP = GET_BTP(inpoint);		/* only valid if not leaf block */
    /*printf ("    Insert in Topblk (%d) at %06lx.  endBTP=%lx, botsiz=%lx, BTPadj=%ld\n",
	topblk->offulFirstFree, inpoint, endBTP, botsiz, BTPadj); */

    chk_makeroom ((USHORT)((long)botsiz + (long)nodeent->cchThisEntry - BTPadj), topblk, (char *)inpoint);

    /* move nodeent into top block.  Correct if dropping BTP value */

    memmove (inpoint, nodeent, (size_t)((long)nodeent->cchThisEntry - BTPadj));
    if (BTPadj) {
	inpoint->cchThisEntry -= (short) BTPadj;
	inpoint->fFlags ^= DF_BTP;
    } else {
	GET_BTP(inpoint) = endBTP;	/* give it a new down pointer */
    }
    /* copy bottom records into top block.  We'll copy the bottom END record
     * overtop the top end record as an easy way to get it's BTP value */

    if (BTPadj == 0)
	FixUp(FIRSTENT(botblk), topblk->lsnThisDir, botsiz + DIRENDSIZE);
    memmove (NEXTREC (inpoint), FIRSTENT(botblk), (size_t)((long)botsiz + DIRENDSIZE));
    /*printf ("Bot Blk deleted = %06lx\n", botblk->lsnThisDir);*/
#ifdef DEBUG
    if (GET_BTP(NEXTREC(nodeent)) != botblk->lsnThisDir) {
	printf ("Botblk sector # not in parent record!\n"); trap();
    }
#endif
    _FreeDB (botblk->lsnThisDir);		/* release these blocks */
    botblk->sig = 0;		/* clear signature for CHKDSK */

    /* closeup the parent record.  The downpointer of the record
     * after the one we demoted pointed to our botblk.	Adjust it
     * to point to the remaining Topblk.  */

    GET_BTP(NEXTREC(nodeent)) = topblk->lsnThisDir;
    _closeup (nodeblk, nodeent);

    topbufp->bDirtMask = TRUE;	topbufp->cusHolds--;
    botbufp->bDirtMask = TRUE;	botbufp->cusHolds--;	/* botblk only looses it's signature */
    _chkheld(nodebufp);
    nodebufp->bDirtMask = TRUE;	nodebufp->cusHolds--;

    if (DIRBLK_EMPTY(nodeblk)) {
	/*printf ("Adjusting emptied parent block %06lx\n", nodeblk);*/
	return(adjust (nodeblk->lsnThisDir));
    }
}


/**	FixUp - Fix Child Dirblk UpPointers
 *
 *	When we split, balance, or join dirblks we may move entries
 *	between different directory blocks.  If those entries have
 *	descendents (DIR_BTP fields) then their lsnParent pointers
 *	will have to be adjusted to their parent entry's new DIRBLK.
 *
 *	FixUp (DirPtr, NewSec, Cnt)
 *
 *		DirPtr = Pointer to first moved parent DirEnt
 *		NewSec = sector # of new parent DIRBLK
 *		Cnt    = # of bytes of dirent's to process
 *
 *	FixUp always stops at an entry marked DF_END so a CNT value of
 *	-1 means 'process till the end'
 *
 *	Since we're not going to look at these lower guys, if we get a hard
 *	error we just make sure that we mark the DIRBLK fucked.  We don't
 *	need to return an error code
 *
 *	The caller has held this dirblk.
 */

void FixUp (dirptr, newsec, cnt)
    register  DIRENT *dirptr;
    int cnt;
    unsigned long newsec;
{
	register  DIRBLK *tdirblk;
	 BUFNODE *tdirbuf;

	while (cnt != 0) {
	    tdirblk = ( DIRBLK *)readbuf(GET_BTP(dirptr), &tdirbuf);
	    if (tdirblk == 0) {
#ifdef DEBUG
		trap();		/* hard error */
#endif
		return;
	    }
	    tdirblk->lsnParent = newsec;
	    tdirbuf->bDirtMask = TRUE;
	    if (dirptr->fFlags & DF_END) {
#ifdef DEBUG
		if ((cnt >= 0) && (cnt != dirptr->cchThisEntry)) {
			printf ("FixUp - Bad Cnt Value %06lx %06lx %ld\n",
				dirptr,newsec, cnt); trap();
		}
#endif
		return;
	    }
#ifdef DEBUG
	    if ((cnt > 0) && (cnt < dirptr->cchThisEntry)) {
		printf ("FixUp - Small Cnt Value %06lx %06lx %ld\n",
			dirptr,newsec, cnt); trap();
	    }
#endif
	    cnt -= dirptr->cchThisEntry;
	    dirptr = NEXTREC(dirptr);
	}
	return;
}

#ifdef	DEBUG

/**	DumpHeap - Dump Heap Structure Sizes
 *
 *	Print out a report on the heap, listing each item, it's size,
 *	and it's allocation address.
 *
 *	addr	type	len	alocaddr
 */

void DumpHeap (addr)
    register unsigned char *addr;
{
	register unsigned int u;
	register int i = 0;

    while ( (*addr & 1) == 0) {

	u = * (unsigned int *)addr;
	printf ("%06lx  ", addr);
	if (u >> 31) {
		/* the thing is free */
		addr += (0x80000004+u);
		printf ("free  %06lx  ", u - 0x80000000);
	} else {
		/* the thing is busy */
		addr += u;
		printf ("BUSY  %06lx  ", u);
	}
	printf ("%04lx", *(unsigned int *)(addr-4));
	if (++i & 1)
		printf ("    ");
	else
		printf ("\n");
    }
    printf ("\n* * * END at %08lx * * *\n", addr);
}


#endif
