/* * Name: deleteEntry * Input: node of index, node * search index key, searchKey * search non-key list, searchNonKey * Output: update index node, node * boolean key adjustment flag, adjustmentFlag * Return: void * Description: The routine recursively descends index on each branch which * is consistent with the input search key values. At the leaf * level, the routine removes all data objects which are * consistent with both the input search key and non-key * values. The routine also removes empty nodes from the * index. The search over the index is performed in the same * manner as the query() routine which checks only the key * values for entries/branches at non-leaf nodes and both key * and non-key values for leaf nodes. An adjustment flag is * used to tell upper level nodes that a change has occurred in * lower nodes. If the flag is not set on return, no change * occurred, i.e., no data objects or nodes removed, and no * adjustments for the key or entry list need to be made. If * the flag is set on return, a change did occur and either the * index key needs to be changed or the node may need to be * removed. * Calls: consistentKey() * consistentNonKey() * deleteEntry() * deleteIndexEntry() * keysUnion() * System: * 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 "dataObject.h" /* for DataAttribute definition */ #include "errorMessage.h" /* for errorMessage() definition */ #include "index.h" /* for IndexNode and IndexEntry definitions */ #include "indexKey.h" /* for IndexKey definition */ /* * Function prototypes */ extern Boolean consistentKey( IndexKey *A, IndexKey *B ); extern Boolean consistentNonKey( Char *A, Char *B ); extern void keysUnion( IndexEntry *I, IndexKey *U ); void deleteEntry( IndexNode *node, /* current node of index */ IndexKey *searchKey, /* index key search values */ DataAttribute *searchNonKey, /* non-key search values */ Boolean *adjustmentFlag ) /* flag to adjust keys */ { /* beginning of deleteEntry() */ assert( node ); assert( searchKey ); assert( adjustmentFlag ); /* * Set key adjustment flag to FALSE until adjustment is necessary through a * delete or return flag. */ *adjustmentFlag = FALSE; /* * The routine is applied recursively so the current node may or may not be * a leaf node. If it is a leaf node, the child referenced by the entries * residing on the node are data objects. If it is not a leaf node, the * child referenced by the entries are other nodes. So if the current * level is not a leaf, recursively call the deleteEntry routine on each * consistent entry. */ if ( node->level > LEAF ) { IndexEntry *entry; /* temp entry for looping through list */ IndexEntry *prevEntry; /* previous entry for re-linking after delete */ /* * Loop through each entry on current node and call deleteEntry() for * each consistent child node. Note that only the key values are * available for consistency checks at any level greater than the LEAF * level. */ prevEntry = NULL; /* no previous entry for head of list */ entry = node->entries; /* set current entry to head of list */ while ( entry != NULL ) { /* loop through entries */ if ( consistentKey( &entry->key, searchKey ) == TRUE ) { Boolean tempAdjustFlag; /* flag to indicate adjustment in */ /* child node */ deleteEntry( entry->child.node, searchKey, searchNonKey, &tempAdjustFlag ); /* * After a return from the recursive deleteEntry call, the * index beneath this node is in one of three states: (1) No * entries were removed, thus no key adjustment is required, * (2) Some entries of the node were removed, but some are left * so need a key adjustment, and (3) All entries of the node * were removed, so no key adjustment (adjust what?) and * remove the entry (which also removes the empty node). The * first condition (1) does not cause any actions so there is * no check. The second(2) and third(3) conditions do require * actions, so they are checked and appropriate actions taken. */ if ( (entry->child.node)->entries == NULL ) { /* (3) */ IndexEntry *nextEntry; /* temp storage for delete */ nextEntry = entry->next; /* save entry for re-linking */ deleteIndexEntry( entry, /* delete current entry */ node->level ); entry = nextEntry; /* reset current entry */ *adjustmentFlag = TRUE; /* set adjustment flag */ /* * If the deleted entry was not the head of the list, need * to re-link the list, so set the prevEntry's next pointer * to current entry. If the deleted entry was the head of * the list, set the node->entries field to the current * entry. This allows the list to show as EMPTY if * necessary on return. */ if ( prevEntry != NULL ) { prevEntry->next = entry; } /* end of if prevEntry != NULL */ else { node->entries = entry; } /* end of if prevEntry == NULL */ } /* end of if entry->child.node.entries == NULL */ else if ( tempAdjustFlag == TRUE ) { /* (2) */ keysUnion( (entry->child.node)->entries, &(entry->key) ); *adjustmentFlag = TRUE; /* set adjustment flag */ /* * Loop to next entry and set previous entry. */ prevEntry = entry; entry = entry->next; } /* end of tempAdjustFlag == TRUE */ else { /* * Loop to next entry and set previous entry. */ prevEntry = entry; entry = entry->next; } /* end of tempAdjustFlag == TRUE */ } /* end of branch which is consistent */ else { /* * Loop to next entry and set previous entry. */ prevEntry = entry; entry = entry->next; } /* end of branch which is not consistent */ } /* end of loop for entry */ } /* end of if ( node->level > LEAF ) */ else { IndexEntry *entry; /* temp entry for looping through list */ IndexEntry *prevEntry; /* previous entry for re-linking after delete */ /* * Loop through each entry on current LEAF node and delete each data * object/entry which is consistent with the input search values. The * first consistency check is made on the key value. If the key values * are consistent, then the data object is checked for its non-key * values. A temporary upperBound value is set to prevent out-of-range * checks on the three types of data objects. */ prevEntry = NULL; /* no previous entry for head of list */ entry = node->entries; /* set current entry to head of list */ while ( entry != NULL ) { /* loop through entries */ if ( consistentKey( &entry->key, searchKey ) == TRUE ) { DataAttribute *temp; /* attribute for list loop */ DataObject *object; /* allows easier reading */ Int upperBound; /* prevents out-of-range */ Boolean acceptanceFlag; /* flag to output object */ object = entry->child.dataObject; /* convenience */ upperBound = 0; /* set upperBound */ if ( object->type == SMALL ) { /* to prevent */ upperBound = NUM_OF_SMALL_ATTRIBUTES; /* out-of-range */ } /* end of type == SMALL */ /* errors when */ else if ( object->type == MEDIUM ) { /* checking non- */ upperBound = NUM_OF_MEDIUM_ATTRIBUTES; /* key attributes */ } /* end of type == MEDIUM */ else if ( object->type == LARGE ) { upperBound = NUM_OF_LARGE_ATTRIBUTES; } /* end of type == LARGE */ /* * The loop checks each value of the non-key search list and * compares that value for that specific attribute code to the * value stored in the data object. If all of the attributes * are consistent, the flag is set to TRUE at the end of the * loop. If any of the attributes are not consistent, the flag * is set to FALSE and the loop exits and the next entry is * checked. */ acceptanceFlag = TRUE; temp = searchNonKey; while ( temp != NULL && acceptanceFlag == TRUE ) { if ( temp->code < upperBound ) { acceptanceFlag = consistentNonKey( object->attributes[ temp->code ].value.nonKey, temp->attribute.value.nonKey ); } /* end of code < upperBound */ temp = temp->next; } /* end of loop through non-key search value list */ /* * If the acceptance flag is set, the data object should be * removed. If a data object is removed, the adjustment flag is * set which notifies the routine calling deleteEntry() for * this node that something happened at this level which causes * a node removal or key adjustment. Care must be taken to * properly re-link the node.entries list. */ if ( acceptanceFlag == FALSE ) { /* * Loop to next entry and set previous entry. */ prevEntry = entry; entry = entry->next; } /* end of acceptanceFlag == TRUE */ else { IndexEntry *nextEntry; /* next entry in list */ nextEntry = entry->next; /* save entry for re-linking */ deleteIndexEntry( entry, /* delete current entry */ LEAF ); entry = nextEntry; /* reset current entry */ *adjustmentFlag = TRUE; /* set adjustment flag */ /* * If the deleted entry was not the head of the list, need * to re-link the list, so set the prevEntry's next pointer * to current entry. If the deleted entry was the head of * the list, set the node->entries field to the current * entry. This allows the list to show as EMPTY if * necessary on return. */ if ( prevEntry != NULL ) { prevEntry->next = entry; } /* end of if prevEntry != NULL */ else { node->entries = entry; } /* end of if prevEntry == NULL */ } /* end of acceptanceFlag == FALSE */ } /* end of if consistentKey == TRUE */ else { /* * Loop to next entry and set previous entry. */ prevEntry = entry; entry = entry->next; } /* end of if consistentKey == FALSE */ } /* end of loop for entry */ } /* end of if ( node->level == LEAF ) */ return; } /* end deleteEntry() */