/* * 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 /* for assert() */ #include /* 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() */