/* * Name: query * Input: root node of index, root * search index key, searchKey * search non-key list, searchNonKey * validity check flag, checkValidity * output function pointer, outputQuery * Output: integer return code * Return: QUERY_SUCCESS, or * QUERY_INVALID_KEY_SEARCH_VALUE, * QUERY_INVALID_NON_KEY_SEARCH_VALUE * Description: The routine searchs the index and calls the outputQuery * routine for each consistent data object found. The routine * first uses the R-Tree index to find individual leaf nodes * which point to data objects which have index keys which are * consistent with the input search key. The found data * object's non-key attributes are then compared with the input * list of non-key search values for consistency. The input * list of non-key search values consist of the attribute code * and a character sequence. Two utility subroutines are used * to check the validity of the input search values. The input * is checked only when the validity input flag is set to TRUE * which prevents multiple checks of the same data since this * routine is applied recursively. Note that the index is * never altered by a query which means no error is fatal. Two * utility subroutines are used to determine consistency which * is intersection for the DIS application. The utility * subroutines are used to separate the specific hyper-cube * dimension and character string from the general R-Tree * algorithm. * * Once a consistent data object has been found, the input * routine outputQuery() is called for this object. It's * expected that the outputQuery() routine will place some * representation of the data object into an output buffer for * the query response. The query() routine does not define * what the representation will be, which allows the calling * program to determine the format and timing of the response * display. * Calls: consistentKey() * consistentNonKey() * errorMessage() * validKey() * validNonKey() * 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 "dataObject.h" /* for DataAttribute and DataObject definitions */ #include "errorMessage.h" /* for errorMessage() definition */ #include "index.h" /* for IndexNode and IndexEntry definitions */ #include "indexKey.h" /* for IndexKey definition */ #include "query.h" /* for query return codes */ /* * Function prototypes */ extern Boolean consistentKey( IndexKey *A, IndexKey *B ); extern Boolean consistentNonKey( Char *A, Char *B ); extern Boolean validIndexKey( IndexKey *key ); extern Boolean validAttributes( DataAttribute *attributes ); Int query( IndexNode *node, /* current node of index */ IndexKey *searchKey, /* index key search values */ DataAttribute *searchNonKey, /* non-key search values */ Boolean checkValidity, /* flag to check validity */ void (*outputQuery)( DataObject *) ) /* output valid object */ { /* beginning of query() */ static Char name[] = "query"; assert( node ); assert( searchKey ); assert( !( checkValidity != TRUE && checkValidity != FALSE ) ); /* * If flag is set, check validity of key and non-key values. */ if ( checkValidity == TRUE ) { if ( validIndexKey( searchKey ) == FALSE ) { errorMessage( "invalid index key search values", REPLACE ); errorMessage( name, PREPEND ); return ( QUERY_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 ( QUERY_INVALID_NON_KEY_SEARCH_VALUE ); } /* end validity check of non-key values */ } /* end of checkValidity == TRUE */ /* * 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 query routine on each * consistent entry. */ if ( node->level > LEAF ) { IndexEntry *entry; /* temp entry for looping through list */ /* * Loop through each entry on current node and query each consistent * child node. Note that only the key values are available for * consistency checks at any level greater than the LEAF level. */ for ( entry = node->entries; entry != NULL; entry = entry->next ) { if ( consistentKey( &entry->key, searchKey ) == TRUE ) { query( entry->child.node, searchKey, searchNonKey, FALSE, outputQuery ); } /* end of branch which is consistent */ } /* end of loop for entry */ } /* end of if ( node->level > LEAF ) */ else { IndexEntry *entry; /* temp entry for looping through list */ /* * Loop through each entry on current node and query each consistent * child node. 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. */ for ( entry = node->entries; entry != NULL; entry = entry->next ) { 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; upperBound = 0; if ( object->type == SMALL ) { upperBound = NUM_OF_SMALL_ATTRIBUTES; } /* end of type == SMALL */ else if ( object->type == MEDIUM ) { upperBound = NUM_OF_MEDIUM_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, and the outputQuery routine is called for the data * object. 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 ( acceptanceFlag == TRUE ) { outputQuery( entry->child.dataObject ); } /* end of acceptanceFlag == TRUE */ } /* end of if consistentKey == TRUE */ } /* end of loop for entry */ } /* end of if ( node->level == LEAF ) */ return ( QUERY_SUCCESS ); } /* end query() */