/*static char *SCCSID = "@(#)balance.c  6.1 90/11/17";*/
/*static char *SCCSID = "@(#)balance.c 13.2 90/01/25";*/

#define INCL_DOSERRORS
#include <os2def.h>
#include <bse.h>
#include "heap.h"
#include "api.h"
#include "const.h"
#include "misc.h"
#include "chain.h"
#include "buf.h"
#include "dir.h"
#include "volume.h"
#include "storage.h"
#include "fnode.h"
#include "tables.h"
#include "pb_ifs.h"
#include "superb.h"
#include "lw.h"
#include "frame.h"
#include "fsdata.h"
#include "pbmacros.h"
#include "assert.h"
#include "log.h"                                                 // @76193
#include "pr_BITMP.h"
#include "pr_CACHE.h"
#include "pr_DEBUG.h"
#include "pr_DEL.h"
#include "pr_DIR.h"
#include "pr_HEAP.h"
#include "pr_MISC.h"


/*  ISLEAF returns TRUE if DIRBLK is a leaf entry
 */
#define ISLEAF(db) ((FIRSTENT(db)->fFlags & DF_BTP) == 0)

/*  FIRSTENT returns pointer to first DIRENT given a DIRBLK
 */
#define FIRSTENT(t) ((PDIRENT)(&t->bFirst))


/*  DIRBLK_EMPTY returns TRUE if a DIRBLK is empty
 */
#define DIRBLK_EMPTY(x) ((x)->offulFirstFree <= (FIELDOFFSET(DIRBLK, bFirst)+ \
                                (sizeof (DIRENT)) + (sizeof(LSN)) ))

/*  GET_END returns pointer to end record in DIRBLK
 */
#define GET_END(rec)  ( (PDIRENT)( (PBYTE)rec + rec->offulFirstFree     \
                                   - sizeof (DIRENT)                    \
                                   - (FIRSTENT(rec)->fFlags & DF_BTP)))


/**     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.
 *
 *      Note that there is a node 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 node 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.
 *
 *      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.

        BUGBUG - what if there's only one in toprec, we want to split it?
                 what if there's only one in botrec, ditto?
 *
 *      HISTORY
 *  @76193  23-Nov-1993 by D.Azzarito - Change holds for LOG support
 *          19-Sep-89 by JR (John Rogers, JohnRo@Microsoft)
 *              - Avoid warnings from Microsoft C 5.2 (on slash-slash comments).
 */

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

USHORT
Balance (PDIRBLK topblk, PBUFNODE topbufp,
         PDIRBLK botblk, PBUFNODE botbufp,
         PDIRBLK nodeblk, PBUFNODE nodebufp,
         PDIRENT nodeent)
{
    LONG i;             /* scratch value */
    USHORT BTPadj;      /* = size DIR_BTP iff dirblks are leafs */
    LSN middown;        /* downpointer value from nodeent */

    ASSERT_DB(topblk);
    ASSERT_DB(botblk);
    ASSERT_DB(nodeblk);

    /*
     * Although possible, it's rare that we won't molest all three DIRBLKs,
     * so set their dirty bits and edit their change count fields.
     * Add 2 since low order bit is a flag.
     */
    topblk->culChange += 2;
    botblk->culChange += 2;
    nodeblk->culChange += 2;

#ifdef DEBUG
    /* make sure all 3 guys are held */
    if ((topbufp->cusHolds == 0) ||
        (botbufp->cusHolds == 0) ||
        (nodebufp->cusHolds == 0)) {

        dprintf ("balance: one of the 3 dirblks not held\n");
        Int3 ();
    }
#endif

    /*
     * We cannot add these up front since when we call SetDBDirt
     * with the Lzay Writer off, we write to disk.  These will be
     * dirtied later in the code so we must call SetDBDirt AFTER
     * we're done with them.
     *
     * SetDBDirt (topbufp, FALSE);
     * SetDBDirt (botbufp, FALSE);
     * SetDBDirt (nodebufp, FALSE);
     */

    /* 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) ? sizeof (LSN) : 0;
    middown = BTP(nodeent);

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


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

    if (DIRBLK_EMPTY(botblk)) {

        /* The bottom half is empty, so we must give up at least one record
         * from the top half.  Make sure that the mid point lies in the
         * top record (it could possibly fall into the nodeent)
         */

        if (i > (topblk->offulFirstFree - DIRENDSIZE -1) ) {
#ifdef DEBUG
            dprintf ("Moving last entry from top to bottom\n");
            Int3 ();
#endif
            i = (topblk->offulFirstFree - DIRENDSIZE -1);
        }
    }
    if (i < (topblk->offulFirstFree - DIRENDSIZE)) {

        PDIRENT pdent;          /* pointer to DIRENT to promote */
        PDIRENT ndent;          /* pointer to 1st DIRENT to move to endblk */
#ifndef ASM_CODE
        PDIRENT pdeTemp;        /* ptr to temp heap storage for promotion   */
#endif
        PDIRENT demotent;       /* pointer to demoted nodeent in botblk */
        USHORT topmovsiz;       /* cnt of topblk bytes to botblk */
        ULONG pdent_down = 0;   /* BTP down pointer values */

        /* the top block is the one that will give up entries.  Find the
         * guy that will become the new middle record
         *
         *   Because of quantization problems and the widely varying size of
         *   directory entrys, we need to be sure that we're handling the
         *   unusual cases:
         *
         *   ndent = 1st record      (can't happen; while loop executes
         *                            at least once)
         *   pdent = 1st record      (we'd empty toprec.  Special code for this)
         *   ndent = end record      (OK.  We promote one, direct copy none)
         *   pdent = end             (can't happen; i is too small)
         *
         *
         *       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 -= FIELDOFFSET (DIRBLK, bFirst);
        ndent = FIRSTENT(topblk);

        while (i > 0) {
            pdent = ndent;
            ndent = NEXT_ENTRY (pdent);
            i -= pdent->cchThisEntry;
        }

        if (pdent == FIRSTENT(topblk)) {
            /* balance computation wants us to empty this block.  We
             * can't do that.  We'll keep one for ourselves.
             */
            if (ndent->fFlags & DF_END)
                goto do_return; /* We only have one record here.  Return */
            pdent = ndent;              /* leave us one record */
            ndent = NEXT_ENTRY (pdent);
        }

        /* 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 = (PBYTE)GET_END(topblk) - (PBYTE)ndent;

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

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


        MkRoom (topmovsiz + nodeent->cchThisEntry - BTPadj,
                FIRSTENT(botblk),
                botblk);

        BYTE_COPY (ndent, FIRSTENT (botblk), topmovsiz);

        if (BTPadj == 0) {              /* adjust descendants, if we have 'em */
            FixUp (FIRSTENT(botblk), botblk->lsnThisDir, topmovsiz);
        }

        demotent = (PDIRENT) ( (PBYTE)&botblk->bFirst + topmovsiz);
        BYTE_COPY (nodeent, demotent, nodeent->cchThisEntry - BTPadj);
        if (BTPadj == 0) {
            FixUp (nodeent, botblk->lsnThisDir, nodeent->cchThisEntry);
        } else {
            demotent->cchThisEntry -= 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
         *
         * NOTE:  we can't just alter pdent in place, if he needs a BTP,
         * because ndent might be the end record, which we need to preserve.
         *
         */

        Closeup (nodeblk, nodeent);

#ifndef ASM_CODE
        pdeTemp = GHS (pdent->cchThisEntry + BTPadj);
        if (pdeTemp == NULL) {
#ifdef DEBUG
            dprintf("GHS returned NULL");
#endif
            goto do_return ;
        }

        BYTE_COPY (pdent, pdeTemp, pdent->cchThisEntry);

        if (BTPadj) {           /* topblk is a leaf */
            pdeTemp->cchThisEntry += sizeof (LSN);
            pdeTemp->fFlags |= DF_BTP;
        }
        BTP(pdeTemp) = middown;
        ASSERTBTP (pdeTemp);
#else
        if (BTPadj) {           /* topblk is a leaf */
            pdent->cchThisEntry += sizeof (LSN);
            pdent->fFlags |= DF_BTP;
        }
        BTP(pdent) = middown;
        ASSERTBTP(pdent);
#endif

        /* 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.
         */

        ASSERT_DB (botblk);
        SetDBDirt (botbufp, FALSE);
        DecrHoldsBUF (botbufp);  // @76193

#ifndef ASM_CODE

        if (BTPadj == 0)
            FixUp (pdeTemp, nodeblk->lsnThisDir, pdent->cchThisEntry);

        insert (nodeblk, nodebufp, pdeTemp, 0L);
        RetHeap (pdeTemp);
#else
        if (BTPadj == 0)
            FixUp (pdent, nodeblk->lsnThisDir, pdent->cchThisEntry);

        insert (nodeblk, nodebufp, pdent, 0L);
#endif
        ASSERT_DB (nodeblk);
        SetDBDirt (nodebufp, FALSE);
        DecrHoldsBUF (nodebufp);  // @76193

#ifdef DEBUG
        botbufp = nodebufp = NULL;
        botblk = nodeblk = NULL;
#endif
        /*  insert takes care of marking the dirblks dirty  */


        /* 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
         */

        BYTE_COPY (GET_END(topblk), pdent, GET_END(topblk)->cchThisEntry);


        if (BTPadj == 0) {
            BTP(pdent) = pdent_down;
            ASSERTBTP (pdent);
        }

        topblk->offulFirstFree = OFFSETOF (pdent) -
                                 OFFSETOF (topblk) + pdent->cchThisEntry;

        ASSERT_DB(topblk);
        SetDBDirt (topbufp, FALSE);
        DecrHoldsBUF (topbufp);  // @76193

        return( NO_ERROR );
    }
    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.
         *
         *   If its in the end block we make sure that we'll have at least one
         *   record left in the end block.
         */

        PDIRENT pdent;           /* pointer to DIRENT to promote */
        PDIRENT ndent;           /* pointer to 1st DIRENT to remain in endblk */
        PDIRENT addspot;         /* addspot point into topblk */
        USHORT movecnt;                    /* # of bytes to move to toprec */
        LSN  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 = offset into botrec */
        i -= topblk->offulFirstFree - DIRENDSIZE + nodeent->cchThisEntry;

        if (i < 0) {

            /* the nodeent record is the mid point.  If the top is
             * non-empty then we can just skip it.
             */
#ifdef DEBUG
            dprintf ("NodeEnt is midpoint\n");
            Int3 ();
#endif
            if (!DIRBLK_EMPTY(topblk))
                goto do_return;
            i = 0;
        }

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

        /*
         * This line is out of gordon's 1/6/89 code.  It sometimes caused
         * i to go negative.  Later in the code if i is negative then
         * pdent never gets set and it is used later.
         *
         * i -= FIELDOFFSET(DIRBLK, bFirst);
         */

#ifdef DEBUG2
        if ((i - FIELDOFFSET(DIRBLK, bFirst)) < 0) {
                dprintf ("Bal: i would have gone negative\n");
                Int3 ();
        }
#endif
        ndent = FIRSTENT(botblk);
        if (NEXT_ENTRY(ndent)->fFlags & DF_END) {
            goto do_return;
        }


        for (; i > 0; ) {
            pdent = ndent;

            ndent = NEXT_ENTRY (pdent);
            if ((ndent->fFlags & DF_END) ||
                (NEXT_ENTRY(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 = OFFSETOF(pdent) - OFFSETOF(botblk) -
                  FIELDOFFSET (DIRBLK, bFirst);
        addspot = GET_END(topblk);
        topendBTP = BTP(addspot);    /* invalid if leaf node */

        MkRoom (movecnt + nodeent->cchThisEntry - BTPadj,
                addspot, topblk);
        BYTE_COPY (nodeent, addspot, nodeent->cchThisEntry - BTPadj);

        if (BTPadj) {
            addspot->cchThisEntry -= BTPadj;
            addspot->fFlags ^= DF_BTP;    /* strip down pointer */
        } else {
            BTP(addspot) = topendBTP;
            ASSERTBTP (addspot);
        }

        BYTE_COPY (FIRSTENT(botblk), NEXT_ENTRY(addspot), movecnt);
        if (BTPadj == 0)
            FixUp (NEXT_ENTRY(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.
         */

        {
            PDIRENT pdeTemp;

            pdeTemp = GHS(pdent->cchThisEntry + sizeof(LSN));
            if (pdeTemp == NULL) {
#ifdef DEBUG
                dprintf("balance: GHS returned NULL");
#endif
                goto do_return ;
            }

            BYTE_COPY (pdent, pdeTemp, pdent->cchThisEntry);
            pdent = pdeTemp;
        }
        Closeup (nodeblk, nodeent);

        if (BTPadj) {                   /* topblk is a leaf */
            pdent->cchThisEntry += sizeof (LSN);
            pdent->fFlags |= DF_BTP;      /* now has a down pointer */
        } else {

#ifdef DEBUG
            /*
             * this fixes a C compiler code generator bug that occurs when
             * debug is on.
             */
            LSN lsn;
            lsn = BTP(pdent);
            BTP(GET_END(topblk)) = lsn;
#else
            BTP(GET_END(topblk)) = BTP(pdent);
#endif
            ASSERTBTP (GET_END(topblk));

            FixUp (GET_END(topblk), topblk->lsnThisDir,
                   GET_END(topblk)->cchThisEntry);
        }
        BTP(pdent) = middown;       /* set downpointer for promoted guy */
        ASSERTBTP (pdent);

        /*
         * We're done with the top block, so we'll release it before
         * calling insert() in case we block and somebody needs a buffer.
         */
        ASSERT_DB (topblk);
        SetDBDirt (topbufp, FALSE);
        DecrHoldsBUF (topbufp);  // @76193

#ifdef DEBUG
        topbufp = NULL;
        topblk = NULL;
#endif

        if (BTPadj == 0)
            FixUp(pdent, nodeblk->lsnThisDir, pdent->cchThisEntry);

        /*  insert takes care of marking the DIRBLK dirty  */
        insert(nodeblk, nodebufp, pdent, 0L);

        SetDBDirt (nodebufp, FALSE);
        ASSERT_DB (nodeblk);
        DecrHoldsBUF (nodebufp);  // @76193

        RetHeap(pdent);

#ifdef DEBUG
        nodebufp = NULL;
        nodeblk = NULL;
#endif

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

        /* adjust length */
        botblk->offulFirstFree -= ((PBYTE)ndent - (PBYTE)&(botblk->bFirst));
        BYTE_COPY (ndent,                   /* move from ndent */
                   &botblk->bFirst,         /* to the front */
                   (USHORT) (botblk->offulFirstFree -
                                                FIELDOFFSET (DIRBLK, bFirst)));
        SetDBDirt (botbufp, FALSE);
        DecrHoldsBUF (botbufp);  // @76193
        ASSERT_DB(botblk);
        return( NO_ERROR );

do_return:

        ASSERT_DB(topblk);
        ASSERT_DB(botblk);
        ASSERT_DB(nodeblk);

        DecrHoldsBUF (topbufp);  // @76193
        SetDBDirt (topbufp, FALSE);

        DecrHoldsBUF (botbufp);           /* unhold these guys  @76193 */
        SetDBDirt (botbufp, FALSE);

        DecrHoldsBUF (nodebufp);  // @76193
        SetDBDirt (nodebufp, FALSE);

        return( NO_ERROR );
    }
}
