
/*
 *  Name:           insertEntry
 *  Input:          node to place new entry, node
 *                  new index entry to place, entry
 *                  level to place entry, level
 *                  fan or order of index, fan
 *  Output:         updated node, node
 *  Return:         INSERT_ENTRY_SUCCESS, or
 *                  INSERT_ENTRY_CHOOSE_ENTRY_FAILURE,
 *                  INSERT_ENTRY_SPLIT_NODE_FATAL,
 *                  INSERT_ENTRY_SPLIT_NODE_NON_FATAL
 *  Description:    Inserts entry into index starting at provided input node and
 *                  at the specified level.  If the current node is not at the  
 *                  specified level, i.e., above, the method chooseEntry() is  
 *                  used to determine which branch or entry of the current node 
 *                  to use and the insertEntry() routine is recursively called  
 *                  on that branch.  This continues until the specified level  
 *                  has been reached.  At the specified level, the entry is  
 *                  placed onto the node which may cause splitting.  If so, the 
 *                  splitNode() method is used for the split. After the return  
 *                  for a recursive call to insertEntry(), the index key for the
 *                  child is adjusted to correctly enclose the lower branches.
 *  Calls:          chooseEntry()
 *                  errorMessage()
 *                  insertEntry()
 *                  keysUnion()
 *                  splitNode()
 *      System:     
 *  Author:         M.L.Rivas
 *
 *  Revision History:
 *
 *  Date    Name            Revision
 *  ------- --------------- ------------------------------
 *  24May99 Matthew Rivas   Created
 *
 *	Copyright 1999, Atlantic Aerospace Electronics Corp.
 */

#include <assert.h>         /* for assert()                                */
#include <stdlib.h>         /* for NULL definition                         */
#include "dataManagement.h" /* for primitive type definitions              */
#include "errorMessage.h"   /* for errorMessage() definition               */
#include "index.h"          /* for IndexNode and IndexEntry definitions    */
#include "splitNode.h"      /* for splitNode() and return code definitions */
#include "insertEntry.h"    /* for insertEntry() return codes              */

/*
 *  Function prototypes
 */
extern void keysUnion( IndexEntry *I, IndexKey *U );
extern IndexEntry * chooseEntry( IndexNode *node, IndexEntry *entry );

Int insertEntry( IndexNode *node,           /*  node to begin insertion     */
                 IndexEntry *entry,         /*  entry to insert into index  */
                 Int level,                 /*  level to place entry        */
                 Int fan,                   /*  fan or order of index       */
                 IndexEntry **splitEntry )  /*  possible entry after split  */
{   /* beginning of insertEntry()   */
    Int     returnCode; /* return code for various function calls */

    static Char name[] = "insertEntry";

    assert( node );
    assert( entry );
    assert( level >= LEAF );
    assert( MINIMUM_FAN_SIZE > 1 );
    assert( fan >= MINIMUM_FAN_SIZE );

    /*
     *  If the current node is not at the specified level, then choose a 
     *  branch/entry and descend until correct level is reached.
     */
    if ( node->level > level ) {
        IndexEntry *chosen;
        
        assert( node->entries != NULL );
        
        /*
         *  Since the current node is "higher" than the specified level of 
         *  insertion, a branch or entry is chosen to descend the index tree.  
         *  Note that the only way for chooseEntry() to fail is if there are no 
         *  entries residing on the current node, which indicates an invalid 
         *  index since any node whose level is greater than the LEAF level must
         *  have at least one entry for a balanced index.
         *
         *  After an entry is chosen, the insertEntry() routine is recursively 
         *  called using the chosen entry as the new node for insertion.  The 
         *  return code for the insertEntry() routine is checked for success and
         *  the three types of errors.  All errors are propogated up the 
         *  recursive call chain until the original calling routine is notified.
         */
        chosen = chooseEntry( node, entry );
        if ( chosen == NULL ) {
            errorMessage( "can't choose entry on node", REPLACE );
            errorMessage( name, PREPEND );
            return ( INSERT_ENTRY_CHOOSE_ENTRY_FAILURE );
        }
        
        returnCode = insertEntry( chosen->child.node, entry, level, fan, 
                                  splitEntry );
        if ( returnCode == INSERT_ENTRY_SUCCESS ) {
            /*
             *  The new entry has been successfully inserted somewhere beneath 
             *  the current node.  The index key is adjusted to correctly 
             *  "enclose" the lower hyper-cubes and a check is made for node 
             *  splitting.  If a split occurred, then splitEntry references a 
             *  new sibling node which should be placed onto the current node.  
             *  This may also cause splitting and that entry should be passed to
             *  the calling process.  Eventually, the splitting may reach the 
             *  root node and the index may grow (index growth is handled in the
             *  insert() routine).
             */
            keysUnion( (chosen->child.node)->entries, &chosen->key );
            
            if ( *splitEntry != NULL ) {        /*  check for node splitting  */
                IndexEntry  *lastEntry      = NULL;
                IndexEntry  *tempEntry      = NULL;
                Int         numberOfEntries = 0;
                
                /*
                 *  Determine the number of entries which currently reside on 
                 *  the node.  Also, save the last entry in the list for later 
                 *  insertion.  They are done at the same time to prevent a 
                 *  second "loop" through the index entry list.
                 */
                tempEntry = node->entries;
                lastEntry = tempEntry;
                while ( tempEntry != NULL ) {
                    numberOfEntries++;
                    lastEntry = tempEntry;
                    tempEntry = tempEntry->next;
                }   /*  end of loop for tempEntry   */

                /*
                 *  If there is room on the current node, add splitEntry to the 
                 *  entry list and set splitEntry to NULL to inform the calling 
                 *  process that no new splitting occurred.  Otherwise, split 
                 *  the current node and set splitEntry to the appropriate 
                 *  value.  Note that splitting is done via the splitNode() 
                 *  routine which may return an allocation error.  Any error 
                 *  which occurs at a level greater than the LEAF level is a 
                 *  fatal error since the index has been altered before the 
                 *  error occurs.  Since the index has been altered, no 
                 *  gaurantee can be made on the state of the index and a fatal 
                 *  error follows.
                 */
                if ( numberOfEntries < fan ) { /*  there is room on node */
                    lastEntry->next = *splitEntry;
                    *splitEntry     = NULL;
                }   /*  end of if ( numberOfEntries < fan ) */
                else { /*  no room on node - split */
                    returnCode = splitNode( node, *splitEntry, fan, &tempEntry);
                    if ( returnCode == SPLIT_NODE_SUCCESS ) {
                        *splitEntry = tempEntry;
                    }   /*  end if SPLIT_NODE_SUCCESS   */
                    else if ( returnCode == SPLIT_NODE_ALLOCATION_FAILURE ) {
                        return ( INSERT_ENTRY_SPLIT_NODE_FATAL );
                    }   /*  end if SPLIT_NODE_ALLOCATION_FAILURE    */
                }   /*  end of numberOfEntries >= fan   */
            }   /*  end of if ( *splitEntry != NULL )   */
        }   /*  end of returnCode == INSERT_ENTRY_SUCCESS   */
        else if ( returnCode == INSERT_ENTRY_CHOOSE_ENTRY_FAILURE ||
                  returnCode == INSERT_ENTRY_SPLIT_NODE_FATAL     ||
                  returnCode == INSERT_ENTRY_SPLIT_NODE_NON_FATAL ) {
            /*
             *  Any error which occurs during a recursive call to insertEntry() 
             *  will be propogated back up the recursive call "chain" until the 
             *  original calling process is informed.
             */
            return ( returnCode );
        }   /*  end of returnCode == recursive call failure */
    }   /*  end of if ( node->level > level )   */
    else {
        IndexEntry  *lastEntry      = NULL;
        IndexEntry  *tempEntry      = NULL;
        Int         numberOfEntries = 0;

        /*
         *  Determine the number of entries which currently reside on the node. 
         *  Also, save the last entry in the list for later insertion.  They are
         *  done at the same time to prevent a second "loop" through the index 
         *  entry list.
         */
        tempEntry = node->entries;
        lastEntry = tempEntry;
        while ( tempEntry != NULL ) {
            numberOfEntries++;
            lastEntry = tempEntry;
            tempEntry = tempEntry->next;
        }   /*  end of loop for tempEntry   */

        /*
         *  If there is room on the current node, add splitEntry to the entry 
         *  list and set splitEntry to NULL to inform the calling process that 
         *  no new splitting occurred.  Otherwise, split the current node and 
         *  set splitEntry to the appropriate value.  Note that splitting is 
         *  done via the splitNode() routine which may return an allocation 
         *  error.  Any error which occurs at a level greater than the LEAF 
         *  level is a fatal error since the index has been altered before the 
         *  error occurs.  Since the index has been altered, no gaurantee can be
         *  made on the state of the index and a fatal error follows.  However, 
         *  a splitNode() error which occurs for a LEAF node is non-fatal since 
         *  the index is unchanged and its state can be gauranteed.
         */
        if ( numberOfEntries < fan ) { /*  there is room on node */
            /*
             *  Note that it's possible to have an empty node at the leaf level,
             *  i.e., the node is the root, so a check must be made to ensure 
             *  that lastEntry is a valid reference.
             */
            if ( lastEntry == NULL ) {
                node->entries   = entry;
            } /* end of lastEntry == NULL */
            else {
                lastEntry->next = entry;
            } /* end of lastEntry != NULL */
            *splitEntry = NULL;
        }   /*  end of if ( numberOfEntries < fan ) */
        else { /*  no room on node - split */
            returnCode = splitNode( node, entry, fan, splitEntry );
            if ( returnCode == SPLIT_NODE_ALLOCATION_FAILURE ) {
                if ( node->level == LEAF ) {
                    errorMessage( "can't split LEAF node", REPLACE );
                    errorMessage( name, PREPEND );
                    return ( INSERT_ENTRY_SPLIT_NODE_NON_FATAL );
                }   /*  end of if ( node->level == LEAF )   */
                else {
                    errorMessage( "can't split non-LEAF node", REPLACE );
                    errorMessage( name, PREPEND );
                    return ( INSERT_ENTRY_SPLIT_NODE_FATAL );
                }   /*  end of if ( node->level != LEAF )   */
            }   /*  end of SPLIT_NODE_ALLOCATION_FAILURE    */
        }   /*  end of if ( numberOfEntries >= fan )    */
    }   /*  end of ( node->level == level ) */

    return ( INSERT_ENTRY_SUCCESS );
}   /*  end insertEntry()   */