/***************************************************************************
 *                                                                         *
 *   SMBAPI.C                                                              *
 *                                                                         *
 *   Copyright (c) 1987-1997 Galacticomm, Inc.    All Rights Reserved.     *
 *                                                                         *
 *   This is the header file for the library of routines for accessing     *
 *   memory data files with fixed length records.                          *
 *                                                                         *
 *                                          - W. Muharsky  5/19/97         *
 *                                                                         *
 ***************************************************************************/
#include "gcomm.h"
#include "majorbbs.h"
#include "smblock.h"
#include "smbapi.h"
#ifdef GCDOS
#include "smcache.h"
#include "smfile.h"
#include "galsmb.h"
#endif // GCDOS

#define FILREV "$Revision: 10 $"

#ifdef GCDOS
GBOOL smbInitialized=FALSE;        /* has SMB API been initialized yet?    */
#endif // GCDOS

GBOOL smbInserting=FALSE;          /*  Currently inserting a record        */

static USHORT                      /* Number of keys in structure          */
CountKeys(                         /*  Counts number of keys               */
pSMBKEYTABLE keyptr);              /*  Pointer to the key table            */

#ifndef GCDOS
static VOID
freeTree(                          /* free memory for a tree               */
SMBPTR root);                      /*   root node of tree                  */
#endif // GCDOS

static VOID
sprout(                            /*  Adds node to tree and balances      */
SMBHANDLE smb,                     /*  Pointer to current smb info         */
SMBPTR SearchRecord,               /*  Which record to load as current     */
SMBPTR NewRecordNumber,            /*  New record number                   */
const VOID *NewRecordData,         /*  Data being inserted                 */
GBOOL *Balance,                    /*  Tree is balanced                    */
pSMBRECORDINFO Parent,             /*  Pointer to parent information       */
INT BuildSide,                     /*  Which parent pointer is coming in   */
UINT Key);                         /*  Key we are searching on             */

static VOID
smbLoadRecord(                     /*  Load Record into RECORDINFO struct  */
SMBHANDLE smb,                     /*  Handle to smb information           */
SMBPTR Record,                     /*  Record Number to load               */
pSMBRECORDINFO recptr,             /*  Where to store pointer information  */
UINT Key);                         /*  Key for lookup                      */

static VOID
smbSetupRecord(                    /* set up a record's info               */
SMBHANDLE smb,                     /*  Handle to smb information           */
pSMBRECORDINFO recptr,             /*  Where to store pointer information  */
UINT Key);                         /*  Key for lookup                      */

static SMBPTR                      /* Pointer to tree number or SMBNULL    */
smbTreeSearch(                     /*  Search memory tree for node         */
SMBHANDLE smb,                     /*  Pointer to smb structure            */
const VOID *KeyInfo,               /*  Key information                     */
UINT Key);                         /*  Key number                          */

static VOID
DeleteBalanceLeft(                 /* Deletion balance left routine        */
SMBHANDLE smb,                     /*  Current SMB pointer                 */
pSMBRECORDINFO currec,             /*  Pointer to current Record           */
GBOOL *Balance);                   /*  Current balance variable            */

static VOID
DeleteBalanceRight(                /* Deletion balance right routine       */
SMBHANDLE smb,                     /*  Current SMB pointer                 */
pSMBRECORDINFO currec,             /*  Pointer to current record           */
GBOOL *Balance);                   /*  Current balance variable            */

static VOID
del(                               /* Node delete routine                  */
SMBHANDLE smb,                     /*  Pointer to current SMB              */
SMBPTR SearchRecord,               /*  Record currently searching on       */
GBOOL *Balance,                    /*  Currently balanced                  */
pSMBRECORDINFO DeleteNode,         /*  Node being deleted                  */
INT FromSide);                     /*  From which side we are deleting     */

static VOID *                      /* Pointer to data or NULL              */
GetNext(                           /*  Get next function                   */
SMBHANDLE smb,                     /*  Pointer to smb information          */
GBOOL UseEqual);                   /*  Use Equal pointers? GetGreater...   */

static VOID *                      /* Pointer to data or NULL              */
GetPrevious(                       /*  Get previous function               */
SMBHANDLE smb,                     /*  Pointer to smb information          */
GBOOL UseEqual);                   /*  Use the Equal Pointer? GETLESS...   */

static VOID
SetParent(                         /*  Set a parent for a child node       */
SMBHANDLE smb,                     /*  Handle to smb information           */
SMBPTR ChildNumber,                /*  Child number to look up             */
SMBPTR ParentNumber,               /*  Parent Number to assign             */
UINT Key);                         /*  Key number to look up as            */

static VOID
SetChildByBuild(                   /*  Set a child for a parent node       */
SMBHANDLE smb,                     /*  Handle to smb information           */
SMBPTR ParentNumber,               /*  Parent number to look up            */
SMBPTR ChildNumber,                /*  Child number to set from parent     */
INT Buildside,                     /*  Set left or right side of parent    */
UINT Key);                         /*  Key to load from                    */

static VOID
SetChildBynum(                     /*  Set a child for a parent node       */
SMBHANDLE smb,                     /*  Current smb pointer                 */
SMBPTR ParentNumber,               /*  Parent to look up                   */
SMBPTR ChildNumber,                /*  Child number to search nodes for    */
SMBPTR ChildSet,                   /*  What to set node to once found      */
UINT Key);                         /*  Key to look up by                   */

static GBOOL                       /* TRUE if Parents equal = Child        */
ParentEqual(                       /*  Check for parent equal pointer      */
SMBHANDLE smb,                     /*  Handle to smb information           */
SMBPTR ParentNumber,               /*  Parent number to look up            */
SMBPTR ChildNumber,                /*  Child number to look for            */
UINT Key);                         /*  Key number to look up on            */

static VOID
InsertRecord(                      /*  Insert into tree                    */
SMBHANDLE smb,                     /*  Handle to smb information           */
pSMBRECORDINFO Parent,             /*  Parent of record being inserted     */
SMBPTR NewRecordNumber,            /*  Record number of inserted record    */
INT BuildSide,                     /*  Side built from                     */
GBOOL *Balanced,                   /*  Current balance of tree             */
UINT Key);                         /*  Key to load record on               */

static VOID
InsertLeftRotate(                  /*  Singe Left rotation                 */
SMBHANDLE smb,                     /*  pointer to smb information          */
pSMBRECORDINFO currec,             /*  Current record (being rotated)      */
pSMBRECORDINFO LeftBranch,         /*  Pointer to current record left      */
INT BuildSide,                     /*  Side of parent that was built from  */
UINT Key);                         /*  Current key working with            */

static VOID
InsertBalanceLeft(                 /*  Balance left side                   */
SMBHANDLE smb,                     /*  Pointer to smb information          */
pSMBRECORDINFO currec,             /*  Pointer of record to balance        */
GBOOL *Balanced,                   /*  Current balance pointer             */
INT BuildSide,                     /*  Side building from                  */
UINT Key);                         /*  Current key                         */

static VOID
InsertLeftRotateDouble(            /*  Double left rotation                */
SMBHANDLE smb,                     /*  pointer to smb information          */
pSMBRECORDINFO currec,             /*  Pointer to current record           */
pSMBRECORDINFO LeftBranch,         /*  Pointer to left branch              */
pSMBRECORDINFO RightBranch,        /*  Pointer to right branch             */
INT BuildSide,                     /*  Side we build on                    */
UINT Key);                         /*  Key number loading from             */

static VOID
InsertRightRotate(                 /*  Singe Left rotation                 */
SMBHANDLE smb,                     /*  pointer to smb information          */
pSMBRECORDINFO currec,             /*  Current record (being rotated)      */
pSMBRECORDINFO RightBranch,        /*  Pointer to current record right     */
INT BuildSide,                     /*  Side of parent that was built from  */
UINT Key);                         /*  Current key working with            */

static VOID
InsertBalanceRight(                /*  Balance Right side                  */
SMBHANDLE smb,                     /*  Pointer to smb information          */
pSMBRECORDINFO currec,             /*  Pointer of record to balance        */
GBOOL *Balanced,                   /*  Current balance pointer             */
INT BuildSide,                     /*  Side building from                  */
UINT Key);                         /*  Current key                         */

static VOID
InsertRightRotateDouble(           /*  Double right rotation               */
SMBHANDLE smb,                     /*  pointer to smb information          */
pSMBRECORDINFO currec,             /*  Pointer to current record           */
pSMBRECORDINFO RightBranch,        /*  Pointer to right branch             */
pSMBRECORDINFO LeftBranch,         /*  Pointer to left branch              */
INT BuildSide,                     /*  Side we build on                    */
UINT Key);                         /*  Key number loading from             */

static VOID
DeleteEqualNode(                   /*  Delete node with Equal pointer      */
SMBHANDLE smb,                     /*  Pointer to current smb information  */
GBOOL *Balance,                    /*  Balance the tree?                   */
UINT Key);                         /*  Current key being used              */

static VOID
DeleteBalanceParents(              /*  Balance parents of deleted node     */
SMBHANDLE smb,                     /*  Pointer to current smb info         */
SMBPTR DeleteNumber,               /*  Current number to delete            */
UINT Key);                         /*  Current key working with            */

static VOID
DeleteRecord(                      /*  Delete current keyed record         */
SMBHANDLE smb,                     /*  Pointer to smb information          */
SMBPTR DeleteNumber,               /*  Record number deleting              */
UINT Key);                         /*  Key number deleting on              */

static VOID
GetNextRight(                      /*  Get greater record on right node    */
SMBHANDLE smb,                     /*  Pointer to smb information          */
pSMBRECORDINFO currec,             /*  Pointer to current record           */
UINT Key);                         /*  Key working with                    */

MARKSOURCE(smbapi);

VOID EXPORT
initwc__galsmb(VOID)               /* initialize SMB module                */
{
     smbInit();
}

VOID EXPORT
init__galsmb(VOID)                 /* initialize SMB module                */
{
     smbInit();
}

VOID
smbInit(VOID)                      /* initialize SMB API before using      */
{
#ifdef GCDOS
     HMCVFILE smbmb;

     if (smbInitialized) {
          return;
     }
     smbmb=opnmsg("galsmb.mcv");
     smfInit(rawmsg(SWAPPATH));
     clsmsg(smbmb);
     smbInitialized=TRUE;
#endif // GCDOS
}

SMBHANDLE                          /* Pointer to open file                 */
smbOpen(                           /*  Open an in memory file              */
size_t DataLength,                 /*  Maximum length of file to open      */
pSMBKEYTABLE keyptr,               /*  Pointer to the key table            */
UINT CachedRecords)                /*  Records to Cache                    */
{
     SMBHANDLE smb;                /*  Pointer to the new file to create   */
     UINT count;                   /*  Generic counter                     */

     ASSERT(keyptr != NULL);
#ifdef GCDOS
     ASSERT(smbInitialized);
#endif // GCDOS

     smb=(SMBHANDLE)alczer(sizeof(struct smbHandle));

     smb->RecordLength=DataLength;
     smb->Keys=CountKeys(keyptr);
     smb->currec.Number=SMBNULL;

     ASSERT(smb->Keys != 0);

     smb->keyptr=(pSMBKEYTABLE)alczer(sizeof(SMBKEYTABLE)*smb->Keys);
     smb->Roots=(SMBPTR *)alczer(sizeof(SMBPTR)*smb->Keys);
     for (count=0; count < smb->Keys; count++) {
          smb->keyptr[count]=keyptr[count];
          smb->Roots[count]=SMBNULL;
     }

#ifdef GCDOS
     if (CachedRecords < SMBMINCACHE) {
          catastro("smbOpen:  cache too small!");
     }
     smb->Cache=smcOpen(sizeof(SMBHEADER)*smb->Keys+smb->RecordLength,
                        CachedRecords);
     smb->SwapFile=smfOpen(sizeof(SMBHEADER)*smb->Keys+smb->RecordLength);
#else
     (VOID)CachedRecords;
#endif // GCDOS

     return(smb);
}

static USHORT                      /* Number of keys in structure          */
CountKeys(                         /*  Counts number of keys               */
pSMBKEYTABLE keyptr)               /*  Pointer to the key table            */
{
     USHORT count=0;

     while (keyptr[count].Compare != NULL) {
          count++;
     }
     return(count);
}

VOID
smbClose(                          /*  Close an SMB file                   */
SMBHANDLE smb)                     /*  Pointer to file to close            */
{
     ASSERT(smb != NULL);
     ASSERT(smb->Roots != NULL);
     ASSERT(smb->keyptr != NULL);
#ifdef GCDOS
     smcClose(smb->Cache);
     smfClose(smb->SwapFile);
#else
     freeTree(smb->Roots[0]);
#endif // GCDOS
     free(smb->Roots);
     free(smb->keyptr);
     free(smb);
}

#ifndef GCDOS

static VOID
freeTree(                          /* free memory for a tree               */
SMBPTR root)                       /*   root node of tree                  */
{
     SMBPTR curblk,nxtblk;

     if (root != SMBNULL) {
          freeTree(((SMBHEADER *)root)->Left);
          freeTree(((SMBHEADER *)root)->Right);
          curblk=((SMBHEADER *)root)->Equal;
          while (curblk != SMBNULL) {
               nxtblk=((SMBHEADER *)curblk)->Equal;
               free((VOID *)curblk);
               curblk=nxtblk;
          }
          free((VOID *)root);
     }
}

#endif // GCDOS

VOID *
smbGetEqual(                       /* Get a record from a database         */
SMBHANDLE smb,                     /*  Pointer to file to update           */
const VOID *KeyInfo,               /*  Key we are searching for            */
UINT Key)                          /*  Key number to look up by            */
{
     SMBPTR RecordNumber;          /*  Record number to look up            */

     ASSERT(smb != NULL);
     ASSERT(KeyInfo != NULL);
     ASSERT(Key < smb->Keys);

     if ((RecordNumber=smbTreeSearch(smb,KeyInfo,Key)) != SMBNULL) {
          smbLoadRecord(smb,RecordNumber,&smb->currec,Key);
          return(smbCurrentData(smb));
     }
     return(NULL);
}

VOID *                             /* Pointer to data or NULL              */
smbGetBynum(                       /*  Get record by absolute number       */
SMBHANDLE smb,                     /*  Handle to smb information           */
SMBPTR Number,                     /*  Record number to get                */
UINT Key)                          /*  Key number to load as current       */
{
     ASSERT(smb != NULL);

     smbLoadRecord(smb,Number,&smb->currec,Key);

     return(smb->currec.Number == SMBNULL ? NULL : smbCurrentData(smb));
}

static SMBPTR                      /* Pointer to tree number or SMBNULL    */
smbTreeSearch(                     /*  Search memory tree for node         */
SMBHANDLE smb,                     /*  Pointer to smb structure            */
const VOID *KeyInfo,               /*  Key information                     */
UINT Key)                          /*  Key number                          */
{
     SMBPTR CurrentRecord;         /*  Current record looking up           */

     ASSERT(smb != NULL);
     ASSERT(Key < smb->Keys);
     ASSERT(KeyInfo != NULL);

     CurrentRecord=smb->Roots[Key];

     while (CurrentRecord != SMBNULL) {
          smbLoadRecord(smb,CurrentRecord,&smb->currec,Key);

          switch (smb->keyptr[Key].Compare(KeyInfo,
           ((CHAR *)(smb->currec.Data))+smb->keyptr[Key].Offset)) {

          case LEFTHIGH:
               if (smb->currec.KeyHeader->Right == SMBNULL) {
                    return(SMBNULL);
               }
               CurrentRecord=smb->currec.KeyHeader->Right;
               break;

          case RIGHTHIGH:
               if (smb->currec.KeyHeader->Left == SMBNULL) {
                    return(SMBNULL);
               }
               CurrentRecord=smb->currec.KeyHeader->Left;
               break;

          case EQUAL:
               return(CurrentRecord);

          default:
               ASSERTM(CurrentRecord != CurrentRecord,
                "TreeSearch Switch() passed invalid option");
          }
     }
     return(SMBNULL);
}

static VOID
smbLoadRecord(                     /*  Load Record into RECORDINFO struct  */
SMBHANDLE smb,                     /*  Handle to smb information           */
SMBPTR Record,                     /*  Record Number to load               */
pSMBRECORDINFO recptr,             /*  Where to store pointer information  */
UINT Key)                          /*  Key for lookup                      */
{
     setmem(recptr,sizeof(SMBRECORDINFO),0);
     if ((recptr->Number=Record) != SMBNULL) {
          recptr->Record=smbGet(smb,recptr->Number);
     }
     smbSetupRecord(smb,recptr,Key);
}

static VOID
smbSetupRecord(                    /* set up a record's info               */
SMBHANDLE smb,                     /*  Handle to smb information           */
pSMBRECORDINFO recptr,             /*  Where to store pointer information  */
UINT Key)                          /*  Key for lookup                      */
{
     if (recptr->Record != NULL) {
          recptr->KeyHeader=&((pSMBHEADER)recptr->Record)[Key];
          recptr->Data=RecordData(smb,recptr->Record);
          recptr->Key=Key;
     }
     else {
          recptr->Number=SMBNULL;
     }
}

VOID *
smbInsert(                         /*  Insert a record into datafile       */
SMBHANDLE smb,                     /*  Pointer to file to inserto to       */
const VOID *Data)                  /*  Data to insert                      */
{
     GBOOL Balance;
     UINT count;
     SMBRECORDINFO NewRecord;

     NewRecord.Record=smbAlloc(smb,&NewRecord.Number);
     NewRecord.Data=RecordData(smb,NewRecord.Record);
     memcpy(NewRecord.Data,Data,smb->RecordLength);

     for (count=0; count < smb->Keys; count++) {
          Balance=FALSE;
          smbLoadRecord(smb,NewRecord.Number,&NewRecord,count);
          sprout(smb,smb->Roots[count],NewRecord.Number,Data,&Balance,
           NULL,EQUAL,count);

          //  This is for first insertion of keys
          if (smb->Roots[count] == SMBNULL) {
               smb->Roots[count]=NewRecord.Number;
          }
     }
     smb->currec=NewRecord;
     return(smb->currec.Data);
}

static VOID
sprout(                            /*  Adds node to tree and balances      */
SMBHANDLE smb,                     /*  Pointer to current smb info         */
SMBPTR SearchRecord,               /*  Which record to load as current     */
SMBPTR NewRecordNumber,            /*  New record number                   */
const VOID *NewRecordData,         /*  Data being inserted                 */
GBOOL *Balance,                    /*  Tree is balanced                    */
pSMBRECORDINFO Parent,             /*  Pointer to parent information       */
INT BuildSide,                     /*  Which parent pointer is coming in   */
UINT Key)                          /*  Key we are searching on             */
{
     INT Compare;
     SMBRECORDINFO currec;

     if (SearchRecord == SMBNULL) {
          InsertRecord(smb,Parent,NewRecordNumber,BuildSide,Balance,Key);
          return;
     }

     smbLoadRecord(smb,SearchRecord,&currec,Key);

     smbInserting=TRUE;
     Compare=smb->keyptr[Key].Compare(
      ((CHAR *)NewRecordData)+smb->keyptr[Key].Offset,
      ((CHAR *)currec.Data)+smb->keyptr[Key].Offset);
     smbInserting=FALSE;

     if (Compare == RIGHTHIGH) {
          sprout(smb,currec.KeyHeader->Left,NewRecordNumber,NewRecordData,
           Balance,&currec,LEFTHIGH,Key);

          smbLoadRecord(smb,SearchRecord,&currec,Key);
          if (*Balance) {
               InsertBalanceLeft(smb,&currec,Balance,BuildSide,Key);
          }
     }
     else if (Compare == LEFTHIGH) {
          sprout(smb,currec.KeyHeader->Right,NewRecordNumber,NewRecordData,
           Balance,&currec,RIGHTHIGH,Key);
          smbLoadRecord(smb,SearchRecord,&currec,Key);
          if (*Balance) {
               InsertBalanceRight(smb,&currec,Balance,BuildSide,Key);
          }
     }
     else if (Compare == EQUAL) {
          InsertRecord(smb,NULL,NewRecordNumber,EQUAL,Balance,Key);
          smbLoadRecord(smb,NewRecordNumber,&smb->currec,Key);
          smb->currec.KeyHeader->Parent=currec.Number;
          smb->currec.KeyHeader->Equal=currec.KeyHeader->Equal;
          SetParent(smb,smb->currec.KeyHeader->Equal,NewRecordNumber,
           smb->currec.Key);
          currec.KeyHeader->Equal=NewRecordNumber;
          return;
     }
}

INT                                /* LEFTHIGH, EQUAL, or RIGHTHIGH        */
smbCompareString(                  /*  Generic string compare routine      */
const VOID *target,                /*  target string                       */
const VOID *test)                  /*  string to compare to                */
{
     INT ans;

     ans=stricmp((CHAR *)target,(CHAR *)test);
     return((ans == 0 ? EQUAL : ans < 0 ? RIGHTHIGH : LEFTHIGH));
}

INT                                /* LEFTHIGH, EQUAL, or RIGHTHIGH        */
smbCompareLONG(                    /*  Generic Long comaprison             */
const VOID *target,                /*  1st LONG variable                   */
const VOID *test)                  /*  2nd LONG variable                   */
{
     LONG num1;
     LONG num2;

     num1=*((LONG *)target);
     num2=*((LONG *)test);

     return((num1 == num2 ? EQUAL : num1 > num2 ? LEFTHIGH : RIGHTHIGH));
}

INT                                /* LEFTHIGH, EQUAL, or RIGHTHIGH        */
smbCompareINT(                     /*  Generic integer compare routine     */
const VOID *target,                /*  1st INT variable                    */
const VOID *test)                  /*  2nd INT variable                    */
{
     INT num1;
     INT num2;

     num1=*((INT *)target);
     num2=*((INT *)test);

     return((num1 == num2 ? EQUAL : num1 > num2 ? LEFTHIGH: RIGHTHIGH));
}

INT                                /* LEFTHIGH, EQUAL, or RIGHTHIGH        */
smbCompareSHORT(                   /*  Generic integer compare routine     */
const VOID *target,                /*  1st SHORT variable                  */
const VOID *test)                  /*  2nd SHORT variable                  */
{
     SHORT num1;
     SHORT num2;

     num1=*((SHORT *)target);
     num2=*((SHORT *)test);

     return((num1 == num2 ? EQUAL : num1 > num2 ? LEFTHIGH: RIGHTHIGH));
}

VOID
smbDelete(                         /*  Deletes the current record pointer  */
SMBHANDLE smb)                     /*  Pointer to datafile to delete from  */
{
     SMBPTR DeleteNumber;
     UINT count;

     ASSERT(smb != NULL);
     ASSERT(smb->currec.Number != SMBNULL);
     ASSERT(smb->currec.KeyHeader != NULL);

     DeleteNumber=smb->currec.Number;

     for (count=0; count < smb->Keys; count++) {
          DeleteRecord(smb,DeleteNumber,count);
     }
     smbFree(smb,DeleteNumber);
     smb->currec.Number=SMBNULL;
}

static VOID
DeleteRecord(                      /*  Delete current keyed record         */
SMBHANDLE smb,                     /*  Pointer to smb information          */
SMBPTR DeleteNumber,               /*  Record number deleting              */
UINT Key)                          /*  Key number deleting on              */
{
     SMBRECORDINFO LeftBranch;
     SMBRECORDINFO RightBranch;
     GBOOL Balance=FALSE;

     smbLoadRecord(smb,DeleteNumber,&smb->currec,Key);

     if (smb->currec.KeyHeader->Equal != SMBNULL) {
          DeleteEqualNode(smb,&Balance,Key);
     }
     else if (ParentEqual(smb,smb->currec.KeyHeader->Parent,DeleteNumber,Key)) {
          // If this function returned TRUE, it automatically set the
          // parent equal pointer to SMBNULL.
          Balance=FALSE;
     }
     else if (smb->currec.KeyHeader->Right == SMBNULL) {
          smbLoadRecord(smb,smb->currec.KeyHeader->Left,&LeftBranch,Key);
          if (LeftBranch.Number != SMBNULL) {
               LeftBranch.KeyHeader->Parent=smb->currec.KeyHeader->Parent;
          }
          SetChildBynum(smb,smb->currec.KeyHeader->Parent,DeleteNumber,
           LeftBranch.Number,Key);
          Balance=(smb->currec.KeyHeader->Parent != SMBNULL);
     }
     else if (smb->currec.KeyHeader->Left == SMBNULL) {
          smbLoadRecord(smb,smb->currec.KeyHeader->Right,&RightBranch,Key);
          RightBranch.KeyHeader->Parent=smb->currec.KeyHeader->Parent;
          SetChildBynum(smb,RightBranch.KeyHeader->Parent,DeleteNumber,
           RightBranch.Number,Key);
          Balance=(RightBranch.KeyHeader->Parent != SMBNULL);
     }
     else {
          // This function automatically changes smb->currec to the
          // Node that is moved into the deleted nodes place so that
          // if a Balance still needs to be performed, it is done on
          // the proper record
          del(smb,smb->currec.KeyHeader->Left,&Balance,&smb->currec,LEFTHIGH);
          if (Balance) {
               DeleteBalanceLeft(smb,&smb->currec,&Balance);
          }
     }

     if (Balance) {
          DeleteBalanceParents(smb,DeleteNumber,Key);
     }
}

static VOID
DeleteBalanceParents(              /*  Balance parents of deleted node     */
SMBHANDLE smb,                     /*  Pointer to current smb info         */
SMBPTR DeleteNumber,               /*  Current number to delete            */
UINT Key)                          /*  Current key working with            */
{
     INT Compare;
     SMBRECORDINFO Parent;
     GBOOL Balance=TRUE;

     smbLoadRecord(smb,DeleteNumber,&smb->currec,Key);
     while (Balance) {
          if (smb->currec.KeyHeader->Parent == SMBNULL) {
               break;
          }
          smbLoadRecord(smb,smb->currec.KeyHeader->Parent,&Parent,Key);

          smbInserting=TRUE;
          Compare=smb->keyptr[smb->currec.Key].Compare(
           ((CHAR *)smb->currec.Data)+smb->keyptr[smb->currec.Key].Offset,
           ((CHAR *)Parent.Data)+smb->keyptr[smb->currec.Key].Offset);
          smbInserting=FALSE;

          if (Compare == EQUAL) {
               break;
          }
          if (Compare == LEFTHIGH) {
               // This function automatically updates Parent on a rotation
               DeleteBalanceRight(smb,&Parent,&Balance);
          }
          if (Compare == RIGHTHIGH) {
               // This function automatically updates Parent on a rotation
               DeleteBalanceLeft(smb,&Parent,&Balance);
          }
          smb->currec=Parent;
     }
}

static VOID
DeleteEqualNode(                   /*  Delete node with Equal pointer      */
SMBHANDLE smb,                     /*  Pointer to current smb information  */
GBOOL *Balance,                    /*  Balance the tree?                   */
UINT Key)                          /*  Current key being used              */
{
     SMBRECORDINFO EqualBranch;

     smbLoadRecord(smb,smb->currec.KeyHeader->Equal,&EqualBranch,Key);
     SetChildBynum(smb,smb->currec.KeyHeader->Parent,smb->currec.Number,
      smb->currec.KeyHeader->Equal,Key);

     EqualBranch.KeyHeader->Parent=smb->currec.KeyHeader->Parent;
     EqualBranch.KeyHeader->Right=smb->currec.KeyHeader->Right;
     EqualBranch.KeyHeader->Left=smb->currec.KeyHeader->Left;
     EqualBranch.KeyHeader->Balance=smb->currec.KeyHeader->Balance;
     SetParent(smb,EqualBranch.KeyHeader->Right,EqualBranch.Number,Key);
     SetParent(smb,EqualBranch.KeyHeader->Left,EqualBranch.Number,Key);
     *Balance=FALSE;
}

static VOID
del(                               /* Node delete routine                  */
SMBHANDLE smb,                     /*  Pointer to current SMB              */
SMBPTR SearchRecord,
GBOOL *Balance,                    /*  Currently balanced                  */
pSMBRECORDINFO DeleteNode,         /*  Node being deleted                  */
INT FromSide)                      /*  From which side we are deleting     */
{
     SMBRECORDINFO currec;
     SMBRECORDINFO Parent;

     ASSERT(SearchRecord != NULL);
     smbLoadRecord(smb,SearchRecord,&currec,smb->currec.Key);

     if (currec.KeyHeader->Right != SMBNULL) {
          del(smb,currec.KeyHeader->Right,Balance,DeleteNode,RIGHTHIGH);
          if (*Balance) {
               smbLoadRecord(smb,SearchRecord,&currec,smb->currec.Key);
               DeleteBalanceRight(smb,&currec,Balance);
          }
     }
     else if (FromSide == RIGHTHIGH) {
          ASSERT(currec.KeyHeader->Parent != SMBNULL);
          smbLoadRecord(smb,currec.KeyHeader->Parent,&Parent,smb->currec.Key);
          Parent.KeyHeader->Right=currec.KeyHeader->Left;
          SetParent(smb,Parent.KeyHeader->Right,Parent.Number,smb->currec.Key);

          currec.KeyHeader->Balance=DeleteNode->KeyHeader->Balance;
          currec.KeyHeader->Left=DeleteNode->KeyHeader->Left;
          currec.KeyHeader->Right=DeleteNode->KeyHeader->Right;
          currec.KeyHeader->Parent=DeleteNode->KeyHeader->Parent;
          SetChildBynum(smb,currec.KeyHeader->Parent,DeleteNode->Number,
                        currec.Number,currec.Key);

          ASSERT(currec.KeyHeader->Left != SMBNULL);
          ASSERT(currec.KeyHeader->Right != SMBNULL);

          SetParent(smb,currec.KeyHeader->Left,currec.Number,currec.Key);
          SetParent(smb,currec.KeyHeader->Right,currec.Number,currec.Key);

          smb->currec=currec;
          *Balance=TRUE;
     }
     else {
          ASSERT(currec.KeyHeader->Parent != SMBNULL);

          currec.KeyHeader->Right=DeleteNode->KeyHeader->Right;
          SetParent(smb,currec.KeyHeader->Right,currec.Number,currec.Key);

          currec.KeyHeader->Parent=DeleteNode->KeyHeader->Parent;
          SetChildBynum(smb,currec.KeyHeader->Parent,DeleteNode->Number,
                        currec.Number,currec.Key);

          currec.KeyHeader->Balance=DeleteNode->KeyHeader->Balance;
          smb->currec=currec;
          *Balance=TRUE;
     }
}

static VOID
DeleteBalanceLeft(                 /* Deletion balance left routine        */
SMBHANDLE smb,                     /*  Current SMB pointer                 */
pSMBRECORDINFO currec,             /*  Pointer to current Record           */
GBOOL *Balance)                    /*  Current balance variable            */
{
     SMBRECORDINFO RightBranch;
     SMBRECORDINFO LeftBranch;
     INT RightBalance;
     INT LeftBalance;

     ASSERT(smb != NULL);

     switch (currec->KeyHeader->Balance) {
     case LEFTHIGH:
          currec->KeyHeader->Balance=BALANCED;
          break;

     case BALANCED:
          currec->KeyHeader->Balance=RIGHTHIGH;
          *Balance=FALSE;
          break;

     case RIGHTHIGH:
          smbLoadRecord(smb,currec->KeyHeader->Right,&RightBranch,
           smb->currec.Key);
          RightBalance=RightBranch.KeyHeader->Balance;
          if (RightBalance == RIGHTHIGH || RightBalance == BALANCED) {

               currec->KeyHeader->Right=RightBranch.KeyHeader->Left;
               SetParent(smb,currec->KeyHeader->Right,currec->Number,currec->Key);

               RightBranch.KeyHeader->Parent=currec->KeyHeader->Parent;
               SetChildBynum(smb,RightBranch.KeyHeader->Parent,currec->Number,
                             RightBranch.Number,currec->Key);

               RightBranch.KeyHeader->Left=currec->Number;
               currec->KeyHeader->Parent=RightBranch.Number;

               if (RightBalance == BALANCED) {
                    currec->KeyHeader->Balance=RIGHTHIGH;
                    RightBranch.KeyHeader->Balance=LEFTHIGH;
                    *Balance=FALSE;
               }
               else {
                    currec->KeyHeader->Balance=BALANCED;
                    RightBranch.KeyHeader->Balance=BALANCED;
               }
               *currec=RightBranch;
          }
          else {
               smbLoadRecord(smb,RightBranch.KeyHeader->Left,&LeftBranch,
                smb->currec.Key);
               LeftBalance=LeftBranch.KeyHeader->Balance;

               RightBranch.KeyHeader->Left=LeftBranch.KeyHeader->Right;
               SetParent(smb,RightBranch.KeyHeader->Left,RightBranch.Number,
                smb->currec.Key);

               LeftBranch.KeyHeader->Right=RightBranch.Number;
               RightBranch.KeyHeader->Parent=LeftBranch.Number;

               currec->KeyHeader->Right=LeftBranch.KeyHeader->Left;
               SetParent(smb,currec->KeyHeader->Right,currec->Number,
                smb->currec.Key);

               LeftBranch.KeyHeader->Parent=currec->KeyHeader->Parent;
               SetChildBynum(smb,LeftBranch.KeyHeader->Parent,currec->Number,
                             LeftBranch.Number,currec->Key);

               LeftBranch.KeyHeader->Left=currec->Number;
               currec->KeyHeader->Parent=LeftBranch.Number;

               if (LeftBalance == RIGHTHIGH) {
               //if (LeftBalance == LEFTHIGH) {
                    currec->KeyHeader->Balance=LEFTHIGH;
               }
               else {
                    currec->KeyHeader->Balance=BALANCED;
               }
               if (LeftBalance == LEFTHIGH) {
                    RightBranch.KeyHeader->Balance=RIGHTHIGH;
               }
               else {
                    RightBranch.KeyHeader->Balance=BALANCED;
               }
               *currec=LeftBranch;
               LeftBranch.KeyHeader->Balance=BALANCED;
          }
          break;
     default:
          ASSERTM(currec->KeyHeader->Balance != currec->KeyHeader->Balance,
           "Unknown value in DeleteBalanceLeft switch");

     }
}

static VOID
DeleteBalanceRight(                /* Deletion balance right routine       */
SMBHANDLE smb,                     /*  Current SMB pointer                 */
pSMBRECORDINFO currec,             /*  Pointer to current record           */
GBOOL *Balance)                    /*  Current balance variable            */
{
     SMBRECORDINFO LeftBranch;
     SMBRECORDINFO RightBranch;
     INT RightBalance;
     INT LeftBalance;

     ASSERT(smb != NULL);

     switch (currec->KeyHeader->Balance) {
     case RIGHTHIGH:
          currec->KeyHeader->Balance=BALANCED;
          break;

     case BALANCED:
          currec->KeyHeader->Balance=LEFTHIGH;
          *Balance=FALSE;
          break;

     case LEFTHIGH:
          smbLoadRecord(smb,currec->KeyHeader->Left,&LeftBranch,smb->currec.Key);
          LeftBalance=LeftBranch.KeyHeader->Balance;
          if (LeftBalance == LEFTHIGH || LeftBalance == BALANCED) {

               currec->KeyHeader->Left=LeftBranch.KeyHeader->Right;
               SetParent(smb,currec->KeyHeader->Left,currec->Number,currec->Key);

               LeftBranch.KeyHeader->Parent=currec->KeyHeader->Parent;
               SetChildBynum(smb,LeftBranch.KeyHeader->Parent,currec->Number,
                             LeftBranch.Number,currec->Key);

               LeftBranch.KeyHeader->Right=currec->Number;
               currec->KeyHeader->Parent=LeftBranch.Number;

               if (LeftBalance == BALANCED) {
                    currec->KeyHeader->Balance=LEFTHIGH;
                    LeftBranch.KeyHeader->Balance=RIGHTHIGH;
                    *Balance=FALSE;
               }
               else {
                    currec->KeyHeader->Balance=BALANCED;
                    LeftBranch.KeyHeader->Balance=BALANCED;
               }
               *currec=LeftBranch;
          }
          else {
               smbLoadRecord(smb,LeftBranch.KeyHeader->Right,&RightBranch,
                smb->currec.Key);
               RightBalance=RightBranch.KeyHeader->Balance;

               LeftBranch.KeyHeader->Right=RightBranch.KeyHeader->Left;
               SetParent(smb,LeftBranch.KeyHeader->Right,LeftBranch.Number,
                smb->currec.Key);

               RightBranch.KeyHeader->Left=LeftBranch.Number;
               LeftBranch.KeyHeader->Parent=RightBranch.Number;

               currec->KeyHeader->Left=RightBranch.KeyHeader->Right;
               SetParent(smb,currec->KeyHeader->Left,currec->Number,
                smb->currec.Key);

               RightBranch.KeyHeader->Parent=currec->KeyHeader->Parent;
               SetChildBynum(smb,RightBranch.KeyHeader->Parent,currec->Number,
                             RightBranch.Number,currec->Key);

               RightBranch.KeyHeader->Right=currec->Number;
               currec->KeyHeader->Parent=RightBranch.Number;

               if (RightBalance == LEFTHIGH) {
                    currec->KeyHeader->Balance=RIGHTHIGH;
               }
               else {
                    currec->KeyHeader->Balance=BALANCED;
               }
               if (RightBalance == RIGHTHIGH) {
                    LeftBranch.KeyHeader->Balance=LEFTHIGH;
               }
               else {
                    LeftBranch.KeyHeader->Balance=BALANCED;
               }
               *currec=RightBranch;
               RightBranch.KeyHeader->Balance=BALANCED;
          }
          break;

     default:
          ASSERTM(currec->KeyHeader->Balance != currec->KeyHeader->Balance,
           "Unknown value in DeleteBalanceRight switch");
     }
}

VOID *                             /* Pointer to data or NULL              */
smbGetPrevious(                    /*  Get previous from current record    */
SMBHANDLE smb)                     /*  Handle to current smb pointer       */
{
     return(GetPrevious(smb,TRUE));
}

static VOID *                      /* Pointer to data or NULL              */
GetPrevious(                       /*  Get previous function               */
SMBHANDLE smb,                     /*  Pointer to smb information          */
GBOOL UseEqual)                    /*  Use the Equal Pointer? GETLESS...   */
{
     SMBRECORDINFO currec;
     SMBRECORDINFO Parent;

     ASSERT(smb != NULL);
     ASSERT(smb->currec.Data != NULL);

     smbLoadRecord(smb,smb->currec.Number,&currec,smb->currec.Key);
     if (currec.KeyHeader->Left != SMBNULL) {
          smbLoadRecord(smb,currec.KeyHeader->Left,&currec,currec.Key);
          while (currec.KeyHeader->Right != SMBNULL) {
               smbLoadRecord(smb,currec.KeyHeader->Right,&currec,currec.Key);
          }
          while (UseEqual && currec.KeyHeader->Equal != SMBNULL) {
               smbLoadRecord(smb,currec.KeyHeader->Equal,&currec,currec.Key);
          }
          smb->currec=currec;
          return(smbCurrentData(smb));
     }
     while (TRUE) {
          if (currec.KeyHeader->Parent == SMBNULL) {
               return(NULL);
          }
          smbLoadRecord(smb,currec.KeyHeader->Parent,&Parent,currec.Key);
          if (Parent.KeyHeader->Right == currec.Number) {
               smb->currec=Parent;
               while (smb->currec.KeyHeader->Equal != SMBNULL) {
                    smbLoadRecord(smb,smb->currec.KeyHeader->Equal,
                     &smb->currec,smb->currec.Key);
               }
               return(smbCurrentData(smb));
          }
          else if (UseEqual && Parent.KeyHeader->Equal == currec.Number) {
               smb->currec=Parent;
               return(smbCurrentData(smb));
          }
          currec=Parent;
     }
}

VOID *                             /* Pointer to data or NULL              */
smbGetLow(                         /*  Get the lowest record in the tree   */
SMBHANDLE smb,                     /*  Handle to smb information           */
UINT Key)                          /*  Key to get lowest on                */
{
     SMBPTR RecordNumber;

     ASSERT(smb != NULL);
     ASSERT(Key < smb->Keys);

     if ((RecordNumber=smb->Roots[Key]) == SMBNULL) {
          return(NULL);
     }
     do {
          smbLoadRecord(smb,RecordNumber,&smb->currec,Key);
     } while ((RecordNumber=smb->currec.KeyHeader->Left) != SMBNULL);

     // Do not go down the equals bracket, the get next will do that for us
     return(smbCurrentData(smb));
}

VOID *                             /* Pointer to data or NULL              */
smbGetHigh(                        /*  Get highest record in the tree      */
SMBHANDLE smb,                     /*  Handle to smb information           */
UINT Key)                          /*  Key to get highest on               */
{
     SMBPTR RecordNumber;

     ASSERT(smb != NULL);
     ASSERT(Key < smb->Keys);

     if ((RecordNumber=smb->Roots[Key]) == SMBNULL) {
          return(NULL);
     }
     do {
          smbLoadRecord(smb,RecordNumber,&smb->currec,Key);
     } while ((RecordNumber=smb->currec.KeyHeader->Right) != SMBNULL);

     // Get Previous crawls up the equals bracket, so we do need
     // to move down the equals bracket.
     while ((RecordNumber=smb->currec.KeyHeader->Equal) != SMBNULL) {
          smbLoadRecord(smb,RecordNumber,&smb->currec,Key);
     }

     return(smbCurrentData(smb));
}

VOID *                             /* Pointer to data or NULL              */
smbGetNext(                        /*  Get next from current record        */
SMBHANDLE smb)                     /*  Handle to current smb pointer       */
{
     return(GetNext(smb,TRUE));
}

static VOID *                      /* Pointer to data or NULL              */
GetNext(                           /*  Get next function                   */
SMBHANDLE smb,                     /*  Pointer to smb information          */
GBOOL UseEqual)                    /*  Use Equal pointers? GetGreater...   */
{
     SMBRECORDINFO currec;
     SMBRECORDINFO Parent;

     ASSERT(smb != NULL);
     ASSERT(smb->currec.Data != NULL);

     smbLoadRecord(smb,smb->currec.Number,&currec,smb->currec.Key);
     if (UseEqual && currec.KeyHeader->Equal != SMBNULL) {
          smbLoadRecord(smb,currec.KeyHeader->Equal,&currec,currec.Key);
          smb->currec=currec;
          return(smbCurrentData(smb));
     }
     if (currec.KeyHeader->Right != SMBNULL) {
          GetNextRight(smb,&currec,currec.Key);
          smb->currec=currec;
          return(smbCurrentData(smb));
     }
     while (TRUE) {
          if (currec.KeyHeader->Parent == SMBNULL) {
               return(NULL);
          }
          smbLoadRecord(smb,currec.KeyHeader->Parent,&Parent,currec.Key);
          if (Parent.KeyHeader->Left == currec.Number) {
               smb->currec=Parent;
               return(smbCurrentData(smb));
          }
          else if (Parent.KeyHeader->Right != currec.Number
                && Parent.KeyHeader->Right != SMBNULL) {
               GetNextRight(smb,&Parent,Parent.Key);
               smb->currec=Parent;
               return(smbCurrentData(smb));
          }
          currec=Parent;
     }
}

static VOID
GetNextRight(                      /*  Get greater record on right node    */
SMBHANDLE smb,                     /*  Pointer to smb information          */
pSMBRECORDINFO currec,             /*  Pointer to current record           */
UINT Key)                          /*  Key working with                    */
{
     smbLoadRecord(smb,currec->KeyHeader->Right,currec,Key);
     while (currec->KeyHeader->Left != SMBNULL) {
          smbLoadRecord(smb,currec->KeyHeader->Left,currec,Key);
     }
}

VOID *                             /* Pointer to data or NULL              */
smbCurrentData(                    /*  Gets data of current record         */
SMBHANDLE smb)                     /*  Pointer to smb information          */
{
     ASSERT(smb != NULL);
     ASSERT(smb->currec.Number != SMBNULL);
     ASSERT(smb->currec.Data != NULL);

     return(smb->currec.Data);
}

SMBPTR                             /* Absolute number of current record    */
smbCurrentNumber(                  /*  Gets current position of record     */
SMBHANDLE smb)                     /*  Handle to smb information           */
{
     ASSERT(smb != NULL);
     ASSERT(smb->currec.Number != SMBNULL);

     return(smb->currec.Number);
}

VOID *
smbGetGreater(                     /* Get greater than a key               */
SMBHANDLE smb,                     /*  Pointer to file to update           */
const VOID *KeyInfo,               /*  Key we are searching for            */
UINT Key)                          /*  Key number to look up by            */
{
     ASSERT(smb != NULL);
     ASSERT(KeyInfo != NULL);
     ASSERT(Key < smb->Keys);

     smbTreeSearch(smb,KeyInfo,Key);
     if (smb->currec.Number != SMBNULL) {
          if (smb->keyptr[Key].Compare(KeyInfo,((CHAR *)(smb->currec.Data))
           +smb->keyptr[Key].Offset) == RIGHTHIGH) {
               return(smbCurrentData(smb));
          }
          else {
               return(GetNext(smb,FALSE));
          }
     }
     return(NULL);
}

VOID *
smbGetLess(                        /* Get less than a key                  */
SMBHANDLE smb,                     /*  Pointer to file to update           */
const VOID *KeyInfo,               /*  Key we are searching for            */
UINT Key)                          /*  Key number to look up by            */
{
     ASSERT(smb != NULL);
     ASSERT(KeyInfo != NULL);
     ASSERT(Key < smb->Keys);

     smbTreeSearch(smb,KeyInfo,Key);

     if (smb->currec.Number != SMBNULL) {
          if (smb->keyptr[Key].Compare(KeyInfo,((CHAR *)(smb->currec.Data))
           +smb->keyptr[Key].Offset) == LEFTHIGH) {
               return(smbCurrentData(smb));
          }
          else {
               return(GetPrevious(smb,FALSE));
          }
     }
     return(NULL);
}

static VOID
SetParent(                         /*  Set a parent for a child node       */
SMBHANDLE smb,                     /*  Handle to smb information           */
SMBPTR ChildNumber,                /*  Child number to look up             */
SMBPTR ParentNumber,               /*  Parent Number to assign             */
UINT Key)                          /*  Key number to look up as            */
{
     SMBRECORDINFO Child;

     if (ChildNumber != SMBNULL) {
          smbLoadRecord(smb,ChildNumber,&Child,Key);
          Child.KeyHeader->Parent=ParentNumber;
     }
}

static VOID
SetChildBynum(                     /*  Set a child for a parent node       */
SMBHANDLE smb,                     /*  Current smb pointer                 */
SMBPTR ParentNumber,               /*  Parent to look up                   */
SMBPTR ChildNumber,                /*  Child number to search nodes for    */
SMBPTR ChildSet,                   /*  What to set node to once found      */
UINT Key)                          /*  Key to look up by                   */
{
     SMBRECORDINFO Parent;

     if (ParentNumber == SMBNULL) {
          smb->Roots[Key]=ChildSet;
     }
     else {
          smbLoadRecord(smb,ParentNumber,&Parent,Key);
          if (Parent.KeyHeader->Left == ChildNumber) {
               Parent.KeyHeader->Left=ChildSet;
          }
          else if (Parent.KeyHeader->Right == ChildNumber) {
               Parent.KeyHeader->Right=ChildSet;
          }
          else if (Parent.KeyHeader->Equal == ChildNumber) {
               Parent.KeyHeader->Equal=ChildSet;
          }
     }
}

static VOID
SetChildByBuild(                   /*  Set a child for a parent node       */
SMBHANDLE smb,                     /*  Handle to smb information           */
SMBPTR ParentNumber,               /*  Parent number to look up            */
SMBPTR ChildNumber,                /*  Child number to set from parent     */
INT BuildSide,                     /*  Set left or right side of parent    */
UINT Key)                          /*  Key to load from                    */
{
     SMBRECORDINFO Parent;

     if (ParentNumber == SMBNULL) {
          smb->Roots[Key]=ChildNumber;
     }
     else {
          smbLoadRecord(smb,ParentNumber,&Parent,Key);
          if (BuildSide == LEFTHIGH) {
               Parent.KeyHeader->Left=ChildNumber;
          }
          else if (BuildSide == RIGHTHIGH) {
               Parent.KeyHeader->Right=ChildNumber;
          }
          else if (BuildSide == EQUAL) {
               Parent.KeyHeader->Equal=ChildNumber;
          }
     }
}

static GBOOL                       /* TRUE if Parents equal = Child        */
ParentEqual(                       /*  Check for parent equal pointer      */
SMBHANDLE smb,                     /*  Handle to smb information           */
SMBPTR ParentNumber,               /*  Parent number to look up            */
SMBPTR ChildNumber,                /*  Child number to look for            */
UINT Key)                          /*  Key number to look up on            */
{
     SMBRECORDINFO Parent;

     if (ParentNumber != SMBNULL) {
          smbLoadRecord(smb,ParentNumber,&Parent,Key);
          if (Parent.KeyHeader->Equal == ChildNumber) {
               Parent.KeyHeader->Equal=SMBNULL;
               return(TRUE);
          }
     }
     return(FALSE);
}

static VOID
InsertRecord(                      /*  Insert into tree                    */
SMBHANDLE smb,                     /*  Handle to smb information           */
pSMBRECORDINFO Parent,             /*  Parent of record being inserted     */
SMBPTR NewRecordNumber,            /*  Record number of inserted record    */
INT BuildSide,                     /*  Side built from                     */
GBOOL *Balanced,                   /*  Current balance of tree             */
UINT Key)                          /*  Key to load record on               */
{
     SMBRECORDINFO Insert;

     if (Parent != NULL) {
          if (BuildSide == RIGHTHIGH) {
               Parent->KeyHeader->Right=NewRecordNumber;
          }
          else if (BuildSide == LEFTHIGH) {
               Parent->KeyHeader->Left=NewRecordNumber;
          }
          else {
               Parent->KeyHeader->Equal=NewRecordNumber;
          }
     }
     smbLoadRecord(smb,NewRecordNumber,&Insert,Key);
     Insert.KeyHeader->Left=SMBNULL;
     Insert.KeyHeader->Right=SMBNULL;
     Insert.KeyHeader->Equal=SMBNULL;
     Insert.KeyHeader->Parent=(Parent == NULL ? SMBNULL : Parent->Number);
     Insert.KeyHeader->Balance=BALANCED;

     *Balanced=(BuildSide == EQUAL ? FALSE : TRUE);
}

static VOID
InsertBalanceLeft(                 /*  Balance left side                   */
SMBHANDLE smb,                     /*  Pointer to smb information          */
pSMBRECORDINFO currec,             /*  Pointer of record to balance        */
GBOOL *Balanced,                   /*  Current balance pointer             */
INT BuildSide,                     /*  Side building from                  */
UINT Key)                          /*  Current key                         */
{
     SMBRECORDINFO LeftBranch;
     SMBRECORDINFO RightBranch;

     switch (currec->KeyHeader->Balance) {
     case RIGHTHIGH:
          currec->KeyHeader->Balance=BALANCED;
          *Balanced=FALSE;
          return;

     case BALANCED:
          currec->KeyHeader->Balance=LEFTHIGH;
          return;

     case LEFTHIGH:
          smbLoadRecord(smb,currec->KeyHeader->Left,&LeftBranch,Key);

          if (LeftBranch.KeyHeader->Balance == LEFTHIGH) {
               InsertLeftRotate(smb,currec,&LeftBranch,BuildSide,Key);
          }
          else {
               smbLoadRecord(smb,LeftBranch.KeyHeader->Right,&RightBranch,Key);
               InsertLeftRotateDouble(smb,currec,&LeftBranch,&RightBranch,
                BuildSide,Key);
          }
          currec->KeyHeader->Balance=BALANCED;
          *Balanced=FALSE;
          break;
     }
}

static VOID
InsertLeftRotate(                  /*  Single Left rotation                */
SMBHANDLE smb,                     /*  pointer to smb information          */
pSMBRECORDINFO currec,             /*  Current record (being rotated)      */
pSMBRECORDINFO LeftBranch,         /*  Pointer to current record left      */
INT BuildSide,                     /*  Side of parent that was built from  */
UINT Key)                          /*  Current key working with            */
{
     currec->KeyHeader->Left=LeftBranch->KeyHeader->Right;
     LeftBranch->KeyHeader->Right=currec->Number;
     currec->KeyHeader->Balance=BALANCED;

     // Re-Arrange the Parent pointers
     SetParent(smb,currec->KeyHeader->Left,currec->Number,Key);
     LeftBranch->KeyHeader->Parent=currec->KeyHeader->Parent;
     SetChildByBuild(smb,LeftBranch->KeyHeader->Parent,
      LeftBranch->Number,BuildSide,Key);
     currec->KeyHeader->Parent=LeftBranch->Number;

     // Finished, re-assign rotated branch
     *currec=*LeftBranch;
}

static VOID
InsertLeftRotateDouble(            /*  Double left rotation                */
SMBHANDLE smb,                     /*  pointer to smb information          */
pSMBRECORDINFO currec,             /*  Pointer to current record           */
pSMBRECORDINFO LeftBranch,         /*  Pointer to left branch              */
pSMBRECORDINFO RightBranch,        /*  Pointer to right branch             */
INT BuildSide,                     /*  Side we build on                    */
UINT Key)                          /*  Key number loading from             */
{
     LeftBranch->KeyHeader->Right=RightBranch->KeyHeader->Left;
     SetParent(smb,LeftBranch->KeyHeader->Right,LeftBranch->Number,Key);

     RightBranch->KeyHeader->Left=LeftBranch->Number;
     currec->KeyHeader->Left=RightBranch->KeyHeader->Right;
     RightBranch->KeyHeader->Right=currec->Number;

     if (RightBranch->KeyHeader->Balance == LEFTHIGH) {
          currec->KeyHeader->Balance=RIGHTHIGH;
     }
     else {
          currec->KeyHeader->Balance=BALANCED;
     }
     if (RightBranch->KeyHeader->Balance == RIGHTHIGH) {
          LeftBranch->KeyHeader->Balance=LEFTHIGH;
     }
     else {
          LeftBranch->KeyHeader->Balance=BALANCED;
     }

     // Now we re-arange the parent headers
     RightBranch->KeyHeader->Parent=currec->KeyHeader->Parent;
     SetChildByBuild(smb,RightBranch->KeyHeader->Parent,RightBranch->Number,
      BuildSide,Key);
     LeftBranch->KeyHeader->Parent=RightBranch->Number;
     currec->KeyHeader->Parent=RightBranch->Number;
     SetParent(smb,currec->KeyHeader->Left,currec->Number,Key);
     // Finished, re-assign rotated branch
     *currec=*RightBranch;
}

static VOID
InsertBalanceRight(                /*  Balance Right side                  */
SMBHANDLE smb,                     /*  Pointer to smb information          */
pSMBRECORDINFO currec,             /*  Pointer of record to balance        */
GBOOL *Balanced,                   /*  Current balance pointer             */
INT BuildSide,                     /*  Side building from                  */
UINT Key)                          /*  Current key                         */
{
     SMBRECORDINFO LeftBranch;
     SMBRECORDINFO RightBranch;

     switch (currec->KeyHeader->Balance) {
     case LEFTHIGH:
          currec->KeyHeader->Balance=BALANCED;
          *Balanced=FALSE;
          return;

     case BALANCED:
          currec->KeyHeader->Balance=RIGHTHIGH;
          return;

     case RIGHTHIGH:
          smbLoadRecord(smb,currec->KeyHeader->Right,&RightBranch,Key);
          if (RightBranch.KeyHeader->Balance == RIGHTHIGH) {
               InsertRightRotate(smb,currec,&RightBranch,BuildSide,Key);
          }
          else {
               smbLoadRecord(smb,RightBranch.KeyHeader->Left,&LeftBranch,Key);
               InsertRightRotateDouble(smb,currec,&RightBranch,&LeftBranch,
                BuildSide,Key);
          }
          currec->KeyHeader->Balance=BALANCED;
          *Balanced=FALSE;
          break;
     }
}

static VOID
InsertRightRotate(                 /*  Singe Left rotation                 */
SMBHANDLE smb,                     /*  pointer to smb information          */
pSMBRECORDINFO currec,             /*  Current record (being rotated)      */
pSMBRECORDINFO RightBranch,        /*  Pointer to current record right     */
INT BuildSide,                     /*  Side of parent that was built from  */
UINT Key)                          /*  Current key working with            */
{
     currec->KeyHeader->Right=RightBranch->KeyHeader->Left;
     RightBranch->KeyHeader->Left=currec->Number;
     currec->KeyHeader->Balance=BALANCED;

     // Now we re-arange the parent headers
     SetParent(smb,currec->KeyHeader->Right,currec->Number,Key);
     RightBranch->KeyHeader->Parent=currec->KeyHeader->Parent;
     SetChildByBuild(smb,RightBranch->KeyHeader->Parent,RightBranch->Number,
      BuildSide,Key);
     currec->KeyHeader->Parent=RightBranch->Number;

     // Finished, re-assign rotated branch
     *currec=*RightBranch;
}

static VOID
InsertRightRotateDouble(           /*  Double right rotation               */
SMBHANDLE smb,                     /*  pointer to smb information          */
pSMBRECORDINFO currec,             /*  Pointer to current record           */
pSMBRECORDINFO RightBranch,        /*  Pointer to right branch             */
pSMBRECORDINFO LeftBranch,         /*  Pointer to left branch              */
INT BuildSide,                     /*  Side we build on                    */
UINT Key)                          /*  Key number loading from             */
{
     RightBranch->KeyHeader->Left=LeftBranch->KeyHeader->Right;
     SetParent(smb,RightBranch->KeyHeader->Left,RightBranch->Number,Key);
     LeftBranch->KeyHeader->Right=RightBranch->Number;
     currec->KeyHeader->Right=LeftBranch->KeyHeader->Left;
     LeftBranch->KeyHeader->Left=currec->Number;

     if (LeftBranch->KeyHeader->Balance == RIGHTHIGH) {
          currec->KeyHeader->Balance=LEFTHIGH;
     }
     else {
          currec->KeyHeader->Balance=BALANCED;
     }
     if (LeftBranch->KeyHeader->Balance == LEFTHIGH) {
          RightBranch->KeyHeader->Balance=RIGHTHIGH;
     }
     else {
          RightBranch->KeyHeader->Balance=BALANCED;
     }

     // Now we re-arange the parent headers
     LeftBranch->KeyHeader->Parent=currec->KeyHeader->Parent;
     SetChildByBuild(smb,LeftBranch->KeyHeader->Parent,LeftBranch->Number,
      BuildSide,Key);
     RightBranch->KeyHeader->Parent=LeftBranch->Number;
     currec->KeyHeader->Parent=LeftBranch->Number;
     SetParent(smb,currec->KeyHeader->Right,currec->Number,Key);
     // Finished, re-assign rotated branch
     *currec=*LeftBranch;
}

#ifdef DEBUG

INT EXPORT
smbBruteForceCountLevels(          // count levels, ignoring balance info
SMBHANDLE smb,                     //   block handle
SMBPTR curnode,                    //   root node to count at
UINT key)                          //   key to display
{
     INT lh,rh;
     SMBPTR rnode,lnode;
     SMBRECORDINFO nodeinfo;

     if (curnode != SMBNULL) {
          smbLoadRecord(smb,curnode,&nodeinfo,key);
          lnode=nodeinfo.KeyHeader->Left;
          rnode=nodeinfo.KeyHeader->Right;
          lh=smbBruteForceCountLevels(smb,lnode,key);
          rh=smbBruteForceCountLevels(smb,rnode,key);
          return(max(lh,rh)+1);
     }
     return(0);
}

INT EXPORT
smbCountLevels(                    // count levels in tree
SMBHANDLE smb,                     //   block handle
UINT key)                          //   key to display
{
     INT n;
     SMBPTR curnode;
     SMBRECORDINFO nodeinfo;

     for (n=0,curnode=smb->Roots[key] ; curnode != SMBNULL ; ++n) {
          smbLoadRecord(smb,curnode,&nodeinfo,key);
          curnode=nodeinfo.KeyHeader->Right;
          if (nodeinfo.KeyHeader->Balance == LEFTHIGH) {
               curnode=nodeinfo.KeyHeader->Left;
          }
     }
     return(n);
}

static ULONG
smbCountEqualNodeUtil(             // count nodes on an equal list
SMBHANDLE smb,                     //   block handle
SMBPTR curnode,                    //   subtree's root node
UINT key)                          //   key to use
{
     ULONG n;
     SMBRECORDINFO nodeinfo;

     for (n=0 ; curnode != SMBNULL ; ++n,curnode=nodeinfo.KeyHeader->Equal) {
          smbLoadRecord(smb,curnode,&nodeinfo,key);
     }
     return(n);
}

static ULONG
smbCountTreeNodeUtil(              // count nodes on a subtree
SMBHANDLE smb,                     //   block handle
SMBPTR curnode,                    //   subtree's root node
UINT key)                          //   key to use
{
     SMBPTR rnode,lnode,enode;
     SMBRECORDINFO nodeinfo;

     if (curnode != SMBNULL) {
          smbLoadRecord(smb,curnode,&nodeinfo,key);
          lnode=nodeinfo.KeyHeader->Left;
          rnode=nodeinfo.KeyHeader->Right;
          enode=nodeinfo.KeyHeader->Equal;
          return(smbCountTreeNodeUtil(smb,lnode,key)
                +smbCountTreeNodeUtil(smb,rnode,key)
                +smbCountEqualNodeUtil(smb,enode,key)+1);
     }
     return(0);
}

ULONG EXPORT
smbCountNodes(                     // count total # of nodes in tree
SMBHANDLE smb)                     //   block handle
{
     return(smbCountTreeNodeUtil(smb,smb->Roots[0],0));
}

GBOOL EXPORT
smbVerifyNodeCount(                // make sure node count matches on all keys
SMBHANDLE smb)                     //   block handle
{
     INT i;
     ULONG curcnt,lastcnt;

     if (smb->Keys > 1) {
          lastcnt=smbCountTreeNodeUtil(smb,smb->Roots[0],0);
          for (i=1 ; i < smb->Keys ; ++i) {
               if ((curcnt=smbCountTreeNodeUtil(smb,smb->Roots[i],i))
                != lastcnt) {
                    return(FALSE);
               }
               lastcnt=curcnt;
          }
     }
     return(TRUE);
}

static SMBPTR                      //   returns node with error or SMBNULL
smbVerifyEqualPtrUtil(             // verify tree pointers utility
SMBHANDLE smb,                     //   block handle
SMBPTR curnode,                    //   node to verify
SMBPTR parent,                     //   this node's parent
UINT key)                          //   key to check
{
     SMBRECORDINFO nodeinfo;

     if (curnode != SMBNULL) {
          if (!smbIsValidBlock(smb,curnode)) {
               return(parent);
          }
          smbLoadRecord(smb,curnode,&nodeinfo,key);
          if (nodeinfo.KeyHeader->Parent != parent
           || nodeinfo.KeyHeader->Left != SMBNULL
           || nodeinfo.KeyHeader->Right != SMBNULL) {
               return(curnode);
          }
          return(smbVerifyEqualPtrUtil(smb,nodeinfo.KeyHeader->Equal,curnode,key));
     }
     return(SMBNULL);
}

static SMBPTR                      //   returns node with error or SMBNULL
smbVerifyTreePtrUtil(              // verify tree pointers utility
SMBHANDLE smb,                     //   block handle
SMBPTR curnode,                    //   node to verify
SMBPTR parent,                     //   this node's parent
UINT key)                          //   key to check
{
     SMBPTR rnode,lnode,enode;
     SMBRECORDINFO nodeinfo;

     if (curnode != SMBNULL) {
          if (!smbIsValidBlock(smb,curnode)) {
               return(parent);
          }
          smbLoadRecord(smb,curnode,&nodeinfo,key);
          if (nodeinfo.KeyHeader->Parent != parent) {
               return(curnode);
          }
          lnode=nodeinfo.KeyHeader->Left;
          rnode=nodeinfo.KeyHeader->Right;
          enode=nodeinfo.KeyHeader->Equal;
          if ((lnode=smbVerifyTreePtrUtil(smb,lnode,curnode,key)) != SMBNULL) {
               return(lnode);
          }
          if ((rnode=smbVerifyTreePtrUtil(smb,rnode,curnode,key)) != SMBNULL) {
               return(rnode);
          }
          return(smbVerifyEqualPtrUtil(smb,enode,curnode,key));
     }
     return(SMBNULL);
}

SMBPTR EXPORT                      //   returns node with error or SMBNULL
smbVerifyPointers(                 // verify tree's pointers
SMBHANDLE smb,                     //   block handle
UINT key)                          //   key to check
{
     if (!smbIsValidBlock(smb,smb->Roots[key])) {
          return(smb->Roots[key]);
     }
     return(smbVerifyTreePtrUtil(smb,smb->Roots[key],SMBNULL,key));
}

static SMBPTR                      //   returns node with error or SMBNULL
smbVerifyBalanceUtil(              // verify tree's balance utility
SMBHANDLE smb,                     //   block handle
SMBPTR curnode,                    //   root node to verify
UINT key)                          //   key to display
{
     INT rh,lh;
     SMBPTR rnode,lnode;
     SCHAR bal;
     SMBRECORDINFO nodeinfo;

     if (curnode != SMBNULL) {
          smbLoadRecord(smb,curnode,&nodeinfo,key);
          lnode=nodeinfo.KeyHeader->Left;
          rnode=nodeinfo.KeyHeader->Right;
          bal=nodeinfo.KeyHeader->Balance;
          lh=smbBruteForceCountLevels(smb,lnode,key);
          rh=smbBruteForceCountLevels(smb,rnode,key);
          switch (bal) {
          case LEFTHIGH:
               if (lh != rh+1) {
                    return(curnode);
               }
               break;
          case RIGHTHIGH:
               if (rh != lh+1) {
                    return(curnode);
               }
               break;
          case BALANCED:
               if (rh != lh) {
                    return(curnode);
               }
               break;
          default:
               return(curnode);
          }
          if ((lnode=smbVerifyBalanceUtil(smb,lnode,key)) != SMBNULL) {
               return(lnode);
          }
          return(smbVerifyBalanceUtil(smb,rnode,key));
     }
     return(SMBNULL);
}

SMBPTR EXPORT                      //   returns node with error or SMBNULL
smbVerifyBalance(                  // verify tree's balance values
SMBHANDLE smb,                     //   block handle
UINT key)                          //   key to display
{
     return(smbVerifyBalanceUtil(smb,smb->Roots[key],key));
}

static VOID
smbDumpLevel(                      // display a level of the tree
SMBHANDLE smb,                     //   block handle
FILE *fp,                          //   output file
smbOutputFunc outFunc,             //   element output function
SMBPTR curnode,                    //   current node for display
INT curlvl,                        //   current level
INT targlvl,                       //   target level
INT w,                             //   current element width
UINT key,                          //   key to display
GBOOL showdata)                    //   show data or lines this time?
{
     SMBRECORDINFO nodeinfo;

     if (curlvl < targlvl) {
          SMBPTR lt,gt;

          if (curnode == SMBNULL) {
               lt=gt=SMBNULL;
          }
          else {
               smbLoadRecord(smb,curnode,&nodeinfo,key);
               lt=nodeinfo.KeyHeader->Left;
               gt=nodeinfo.KeyHeader->Right;
          }
          smbDumpLevel(smb,fp,outFunc,lt,curlvl+1,targlvl,w,key,showdata);
          smbDumpLevel(smb,fp,outFunc,gt,curlvl+1,targlvl,w,key,showdata);
          return;
     }
     if (curnode == SMBNULL) {
          fprintf(fp,"%*s",w,"");
     }
     else {
          smbLoadRecord(smb,curnode,&nodeinfo,key);
          if (showdata) {
               (*outFunc)(fp,nodeinfo.Data,w);
          }
          else if (nodeinfo.KeyHeader->Left == SMBNULL
                && nodeinfo.KeyHeader->Right == SMBNULL) {
               fprintf(fp,"%*s",w,"");
          }
          else {
               int i,lts,ltl,gtl,gts;

               ltl=(w-1)/2;
               gtl=(w-1)-ltl;
               lts=ltl/2;
               ltl-=lts;
               gts=gtl/2;
               gtl-=gts;
               if (nodeinfo.KeyHeader->Left == SMBNULL) {
                    fprintf(fp,"%*s",lts+ltl,"");
               }
               else {
                    fprintf(fp,"%*s/",lts,"");
                    for (i=1 ; i < ltl ; ++i) {
                         fprintf(fp,"-");
                    }
               }
               switch (nodeinfo.KeyHeader->Balance) {
               case LEFTHIGH:
                    fprintf(fp,"<");
                    break;
               case RIGHTHIGH:
                    fprintf(fp,">");
                    break;
               case BALANCED:
                    fprintf(fp,"=");
                    break;
               }
               if (nodeinfo.KeyHeader->Right == SMBNULL) {
                    fprintf(fp,"%*s",gts+gtl,"");
               }
               else {
                    for (i=1 ; i < gtl ; ++i) {
                         fprintf(fp,"-");
                    }
                    fprintf(fp,"\\%*s",gts,"");
               }
          }
     }
}

VOID EXPORT
smbDumpTree(                       // dump binary tree to a file
SMBHANDLE smb,                     //   block handle
FILE *fp,                          //   file to output to
smbOutputFunc outFunc,             //   element output function
INT elemWidth,                     //   single element width
UINT key)                          //   key to display
{
     INT lvl,n,w;

     n=smbCountLevels(smb,key);
     w=elemWidth*(1<<(n-1));
     for (lvl=0 ; lvl < n ; ++lvl) {
          smbDumpLevel(smb,fp,outFunc,smb->Roots[key],0,lvl,w,key,TRUE);
          fprintf(fp,"\n");
          if (lvl < n-1) {
               smbDumpLevel(smb,fp,outFunc,smb->Roots[key],0,lvl,w,key,FALSE);
               fprintf(fp,"\n");
          }
          w/=2;
     }
     fprintf(fp,"\n");
}

#endif // DEBUG
