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