/* * Name: delete * Input: root node of index, root * search index key, searchKey * search non-key list, searchNonKey * Output: updated node, node * Return: DELETE_SUCCESS, or * DELETE_INVALID_KEY_SEARCH_VALUE, * DELETE_INVALID_NON_KEY_SEARCH_VALUE * Description: The routine searches the current index and removes all data * objects which are consistent with the search input values, * key and non-key. The routine makes use of the recursive * routine deleteEntry() to perform the actual search and * removal of data objects in the index. The deleteEntry() * routine will also remove empty nodes from the index all the * way up to the root node. After the return from * deleteEntry(), two checks need to be made. The first checks * to see if the current root node level is not a LEAF and the * list of entries for the root node is empty, i.e., NULL. * This case indicates that the input search values completely * removed every data object in the index and thus all nodes * except the root node. For this case, the level for the root * is reset to the LEAF level and the updated root node is * returned. The second case checks to see if the root node * has only one entry in its list. The R-Tree is required to * replace any root node with only one child with the child * node, unless the root is a LEAF node. * Calls: deleteEntry() * errorMessage() * validIndexKey() * validAttributes() * System: free() * Author: M.L.Rivas * * Revision History: * * Date Name Revision * ------- --------------- ------------------------------ * 27May99 Matthew Rivas Created * * Copyright 1999, Atlantic Aerospace Electronics Corp. */ #include /* for assert() */ #include /* for free() and NULL definitions */ #include "dataManagement.h" /* for primitive type definitions */ #include "errorMessage.h" /* for errorMessage() definition */ #include "dataObject.h" /* for DataAttribute definition */ #include "index.h" /* for IndexNode and IndexEntry definitions */ #include "indexKey.h" /* for IndexKey definition */ #include "delete.h" /* for delete() return codes */ /* * Function prototypes */ extern Boolean validIndexKey( IndexKey *key ); extern Boolean validAttributes( DataAttribute *attributes ); extern void deleteEntry( IndexNode *node, IndexKey *searchKey, DataAttribute *searchNonKey, Boolean *adjustmentFlag ); Int delete( IndexNode **root, /* root node of index */ IndexKey *searchKey, /* index key search values */ DataAttribute *searchNonKey ) /* non-key search values */ { /* beginning of delete() */ Boolean adjustmentFlag; /* place-holder for deleteEntry routine */ static Char name[] = "delete"; assert( root ); assert( *root ); assert( searchKey ); assert( LEAF >= 0 ); /* * Check validity of search values */ if ( validIndexKey( searchKey ) == FALSE ) { errorMessage( "invalid index key search values", REPLACE ); errorMessage( name, PREPEND ); return ( DELETE_INVALID_KEY_SEARCH_VALUE ); } /* end validity check of key values */ else if ( validAttributes( searchNonKey ) == FALSE ) { errorMessage( "invalid non-key search values", REPLACE ); errorMessage( name, PREPEND ); return ( DELETE_INVALID_NON_KEY_SEARCH_VALUE ); } /* end validity check of non-key values */ /* * Call deleteEntry routine for root node which will recursively process * the entire index. Note that the adjustment flag is passed to * deleteEntry but its not needed for the root node since adjustments would * be made to the parent which the root node does not have. */ deleteEntry( *root, searchKey, searchNonKey, &adjustmentFlag ); /* * Check case where level of the root node is not LEAF and there are no * entries residing on root node, i.e., entries == NULL. This indicates * that the input search values completely removed all of the data objects * referenced by the index, which will also remove all index nodes and * entries in the index except for the root node. Because there are no * more objects in the index, simply set the current level of the root node * to be the LEAF level and continue. */ if ( (*root)->level > LEAF && (*root)->entries == NULL ) { (*root)->level = LEAF; } /* * If there is at least one entry on the current root node (root->entries * != NULL), but there is only one entry ((root->entries)->next == NULL), * then replace the root node with the only child unless the root node is a * LEAF node. This behavior is required by the R-Tree definition. The old * root node is deleted, but the entries is first set to EMPTY/NULL. This * prevents the deleteIndexNode() routine from removing the child entry * which has become the new root. */ while ( (*root)->level != LEAF && /* current root not LEAF */ (*root)->entries != NULL && /* at least one child entry */ ((*root)->entries)->next == NULL ) { /* only one child entry */ IndexNode *temp; /* placeholder for old root to delete */ temp = (*root); /* save old root for removal */ *root = ((*root)->entries)->child.node; /* replace root with child */ /* which is referenced by */ /* entries */ free( temp->entries ); /* delete old entry which */ /* referenced old root's */ /* child which is now the */ /* new root. */ temp->entries = NULL; /* Need to set the value to */ /* NULL which will prevent */ /* the next step from */ /* deleting the entire index */ deleteIndexNode( temp ); /* delete old root node */ } /* end of loop for checking number of entries <= 1 */ return ( DELETE_SUCCESS ); } /* end delete() */