MultiSource/Benchmarks/VersaBench/dbms/splitNode.c

/*
 *  Name:           splitNode
 *  Input:          index node to split, nodeToSplit
 *                  integer fan value, fan
 *                  new index entry which caused split, entry
 *  Output:         index entry of new node after splitting, splitEntry
 *  Return:         SPLIT_NODE_SUCCESS, or
 *                  SPLIT_NODE_ALLOCATION_FAILURE
 *  Description:    This routine splits and index node.  An index node needs to 
 *                  split whenever a new index entry is added to the node and 
 *                  the node is full, i.e., the current number of entries 
 *                  residing on the node is equal to the fan or order of the 
 *                  index tree.  A node split consists of dividing the current 
 *                  entries of a node and the new entry into two groups via a 
 *                  partitionEntries routine.  One group is placed onto the 
 *                  node and the other group is placed onto a new node created 
 *                  for that purpose.  A new index entry is created for the new 
 *                  node and is returned as the splitEntry in the output.  
 *                  Since both a new index node and a new index entry are 
 *                  created during the splitting process, a memory allocation 
 *                  failure is possible during the execution of this 
 *                  subroutine.  The allocation failure is fatal for most uses 
 *                  of the method, but in certain cases, splitting a leaf node 
 *                  for instance, a recovery is possible at a higher level.  
 *                  For this reason, the splitNode routine will "clean-up" 
 *                  before returning, i.e., free memory, etc.
 *  Calls:          createIndexEntry()
 *                  createIndexNode()
 *                  deleteIndexNode()
 *                  errorMessage()
 *                  keysUnion()
 *                  partitionEntries()
 *      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() return codes             */

/*
 *  Function prototypes
 */
extern void partitionEntries( IndexEntry *I, Int fan, IndexEntry **A, 
                              IndexEntry **B );
extern void keysUnion( IndexEntry *I, IndexKey *U );

Int splitNode( IndexNode *nodeToSplit,      /* node to split            */
               IndexEntry *entry,           /* entry which caused split */
               Int fan,                     /* fan of index             */
               IndexEntry **splitEntry )    /* output entry of new node */
{   /* beginning of splitNode() */
    IndexEntry  *listOfEntries; /* union of entries of nodeToSplit and entry */
    IndexNode   *splitNode;     /* new split node referenced by splitEntry   */

    static Char name[] = "splitNode";

    assert( nodeToSplit );
    assert( nodeToSplit->entries );
    assert( entry );
    assert( MINIMUM_FAN_SIZE > 1 );
    assert( fan >= MINIMUM_FAN_SIZE );

    /*
     *  Create new index entry which will reference the newly created node.  
     *  Check for memory allocation failure.  Also, create new node for 
     *  partitioning.  The new node is a "sibling" of the input node, so its 
     *  level is the same.  If memory allocation failure, free index entry 
     *  allocation in previous step, place message in error buffer, and return.
     */
    *splitEntry = createIndexEntry();
    if ( *splitEntry == NULL ) {
        errorMessage( "allocation failure - split entry", REPLACE );
        errorMessage( name, PREPEND );
        return ( SPLIT_NODE_ALLOCATION_FAILURE );
    }   /*  end of if ( *splitEntry == NULL )  */
    else {
        splitNode = createIndexNode( nodeToSplit->level );
        if ( splitNode == NULL ) {
            deleteIndexEntry( *splitEntry, nodeToSplit->level );
            errorMessage( "allocation failure - sibling node", REPLACE );
            errorMessage( name, PREPEND );
            return ( SPLIT_NODE_ALLOCATION_FAILURE );
        }   /*  end of if ( splitNode == NULL )  */
    }   /*  end of split entry and node allocation  */

    /*
     *  Create a list which is the union of the current entries of the node to
     *  split and the entry which caused the split to occur.
     */
    listOfEntries           = entry;
    listOfEntries->next     = nodeToSplit->entries;
    nodeToSplit->entries    = NULL;
    splitNode->entries      = NULL;

    /*
     *  Partition entries unto old nodeToSplit and new temporary node.
     */
    partitionEntries( listOfEntries,              /*  entries to partition    */
                      fan,                        /*  fan of index            */
                      &(nodeToSplit->entries),    /*  1st partitioned group   */
                      &(splitNode->entries) );    /*  2nd partitioned group   */
    
    /*
     *  Set reference of splitEntry to new split node and adjust 
     *  key of splitEntry for new node.  Note that the key of the entry 
     *  for nodeToSplit is adjusted in the same process that called splitNode.
     */
    keysUnion( splitNode->entries, &((*splitEntry)->key) );
    (*splitEntry)->child.node = splitNode;

    return ( SPLIT_NODE_SUCCESS );
}   /*  end splitNode() */