/* @(#)sf_search.c 1.10 2/10/93 */ /******************************************************************************* This code was written and designed by Andrew Gene HALL of I.N. Services Pty. Ltd., Scarborough WA, Australia, for the University of Western Australia, Crawley WA, Australia. *******************************************************************************/ #include #include #include "utilitys.h" #include "sf_search.h" #include "marker.h" /* external and forwardly declared functions */ extern char *tsearch(); /* extern char tolower(); CHANGE 9/3 */ List_Value_Seq *replicate_LVS( List_Value_Seq * ); Data_Seq *replicate_DS( Data_Seq * ); char *re_comp( char * ); int re_exec( char * ); /* programming macros */ /* ASSIGN_DATA, * a shorthand for * a->data = b->data */ #define ASSIGN_DATA( a, b) \ { \ a->name = b->name; \ switch( b->tag ) { \ case DATA_ITEM: \ a->tag = DATA_ITEM; \ a->data.data_item = b->data.data_item; \ break; \ \ case LOOP: \ a->tag = LOOP; \ a->data.loop.packet_members = b->data.loop.packet_members; \ a->data.loop.values = replicate_LVS( b->data.loop.values ); \ break; \ \ case SAVE_BLOCK: \ a->tag = SAVE_BLOCK; \ a->data.save_block = replicate_DS( b->data.save_block ); \ break; \ \ default: \ ERROR_MSG("ASSIGN_DATA(): Unknown Domain in Data Sequence."); \ } \ a->next = NULL; \ } while(0) /* locate_name_in_DS * find the first occurence of a name in a Data Sequence. */ Data_Seq *locate_name_in_DS( char * name, Data_Seq * sequence, Boolean (*string_test)(char *, char *) ) { register Data_Seq * pos = NULL; if( name ) for( pos = sequence; pos; pos = pos->next) switch( pos->tag ) { case DATA_ITEM: case LOOP: case SAVE_BLOCK: if( string_test( name, pos->name) ) return( pos ); break; default: ERROR_MSG("locate_name_in_DS: unknown domain in sequence."); } return( NULL ); } /* locate_name_in_DS */ /* names_in_Data_Seq * Determine if data of a given name exist in a list of Data_Seq (sequence). * Return the the node in the list that matches, or NULL if no match. */ Data_Seq *names_in_Data_Seq( char * name, Data_Seq * sequence, Boolean (*string_test)(char *, char *) ) { register Data_Seq *pos = NULL; register Data_Seq *d = NULL; Data_Item *Root_Data_Item = NULL; Data_Seq *rtn_ds = NULL; char *save_refs = NULL; char *frame_codes = NULL; char *known_save_blocks = NULL; if( name ) { /* First get all occurences of name */ for( pos = sequence; pos; pos = pos->next) switch( pos->tag ) { case DATA_ITEM: if( string_test( name, pos->name) ) { Mark_Data_Item( pos->data.data_item, &Root_Data_Item ); if( pos->data.data_item->tag == FRAME_CODE_DI ) /* save the reference for later */ (void)tsearch(pos->data.data_item->value,&frame_codes,strcmp); } break; case LOOP: if( string_test( name, pos->name) ) Mark_LVS( pos->data.loop.values, &Root_Data_Item, &frame_codes ); break; case SAVE_BLOCK: { char *tmp_string; d = NULL; /* test for the name */ if( string_test( name, pos->name) ) { /* mark the whole contents of the save block */ for( d = pos->data.save_block; d; d = d->next ) switch( d->tag ) { case DATA_ITEM: Mark_Data_Item( d->data.data_item, &Root_Data_Item ); if( d->data.data_item->tag == FRAME_CODE_DI ) /* save the reference for later */ (void)tsearch(d->data.data_item->value,&frame_codes,strcmp); break; case LOOP: Mark_LVS(d->data.loop.values,&Root_Data_Item,&frame_codes); break; default: ERROR_MSG("names_in_Data_Seq: unknown domain in sequence."); } /* adjust save block name for later referencing */ CONVERT_TO_FRAME_CODE( tmp_string, pos->name ); (void)tsearch( tmp_string, (char **)&save_refs, strcmp); /* record this block as known */ (void)tsearch( pos->name, &known_save_blocks, strcmp); } else { Data_Seq *t; /* test for the contents of the block */ t = pos->data.save_block; while( (d = locate_name_in_DS( name, t, string_test)) ) { switch( d->tag ) { case DATA_ITEM: Mark_Data_Item( d->data.data_item, &Root_Data_Item ); if( d->data.data_item->tag == FRAME_CODE_DI ) /* save the reference for later */ (void)tsearch(d->data.data_item->value,&frame_codes,strcmp); break; case LOOP: Mark_LVS(d->data.loop.values,&Root_Data_Item,&frame_codes); break; default: ERROR_MSG("names_in_Data_Seq: unknown domain in sequence."); } /* continue the search */ t = d->next; } /* something is found */ if( t != pos->data.save_block ) { /* adjust save block name for later referencing */ CONVERT_TO_FRAME_CODE( tmp_string, pos->name ); (void)tsearch( tmp_string, (char **)&save_refs, strcmp); } } } break; default: ERROR_MSG("names_in_Data_Seq: unknown domain in sequence."); } /* Cross reference so that all Frame Codes are resolved */ refs_by_frame_codes(sequence,&Root_Data_Item,&frame_codes,&save_refs, &known_save_blocks); /* For all Save Blocks found, locate the references to them */ refs_to_SB( sequence, &save_refs, &Root_Data_Item); /* construct sequence of marked data_items */ rtn_ds = get_Marked_DS( sequence, &Root_Data_Item, &known_save_blocks ); return( rtn_ds ); } return( NULL ); } /* names_in_Data_Seq */ /* replicate_LVS * Create a new List Value Sequence from a given one, * using the same data items. * Return the beginning of the sequence */ List_Value_Seq *replicate_LVS( List_Value_Seq *list) { List_Value_Seq *tmp_list, *last_list; tmp_list = last_list = NULL; for( ; list; list = list->next) { /* add a list node */ if( last_list ) { Malloc(List_Value_Seq,last_list->next); last_list = last_list->next;} else { Malloc( List_Value_Seq, last_list ); tmp_list = last_list; } /* add the data */ last_list->tag = list->tag; switch( list->tag ) { case DATA_ITEM: last_list->element.data_item = list->element.data_item; break; case SUB_LOOP: last_list->element.sub_loop = replicate_LVS(list->element.sub_loop); break; default: ERROR_MSG("replicate_LVS(): Unknown domain in LVS."); } } return( tmp_list ); } /* replicate_LVS */ /* replicate_DS, * Given a data sequence , * reproduce its structure, using the same names and Data Items. * Return the head of the Data_Seq. */ Data_Seq *replicate_DS( Data_Seq *data) { Data_Seq *tmp_ds, *last_ds; tmp_ds = last_ds = NULL; for( ; data; data = data->next) { /* add a data node */ if( last_ds ) { Malloc( Data_Seq, last_ds->next); last_ds = last_ds->next;} else { Malloc( Data_Seq, last_ds ); tmp_ds = last_ds; } /* add the data */ last_ds->name = data->name; last_ds->tag = data->tag; switch( data->tag ) { case DATA_ITEM: last_ds->data.data_item = data->data.data_item; break; case LOOP: last_ds->data.loop.packet_members = data->data.loop.packet_members; last_ds->data.loop.values = replicate_LVS( data->data.loop.values ); break; case SAVE_BLOCK: last_ds->data.save_block = replicate_DS( data->data.save_block ); break; default: ERROR_MSG("replicate_DS(): Unknown Domain in Data Sequence."); } last_ds->next = NULL; } return( tmp_ds ); } /* replicate_DS */ /* replicate_BS */ Block_Seq *replicate_BS( Block_Seq * blocks) { register Block_Seq * last_bs = NULL; Block_Seq * tmp_bs = NULL; Global_Seq *globals = NULL; Global_Seq *tmp_globals = NULL; for(; blocks; blocks = blocks->next ) switch( blocks->tag ) { case DATA_BLOCK: /* build a new node */ if( last_bs ) { Malloc( Block_Seq, last_bs->next ); last_bs = last_bs->next; } else { Malloc( Block_Seq, last_bs ); tmp_bs = last_bs; } last_bs->name = blocks->name; last_bs->tag = DATA_BLOCK; last_bs->block.data_block.actual_data = replicate_DS(blocks->block.data_block.actual_data); last_bs->block.data_block.global_data = globals; last_bs->next = NULL; break; case GLOBAL_BLOCK: /* build a new node */ if( last_bs ) { Malloc( Block_Seq, last_bs->next ); last_bs = last_bs->next; } else { Malloc( Block_Seq, last_bs ); tmp_bs = last_bs; } last_bs->name = blocks->name; last_bs->tag = GLOBAL_BLOCK; last_bs->block.global_block = replicate_DS(blocks->block.global_block); last_bs->next = NULL; /* add this to the head of the list of globals */ Malloc( Global_Seq, tmp_globals ); tmp_globals->global_entry = last_bs; tmp_globals->next = globals; globals = tmp_globals; break; default: ERROR_MSG("replicate_BS(): unknown block in Block_Seq."); } return( tmp_bs ); } /* replicate_BS() */ /* names_in_Block_Seq * Given a name find all matches to it in the given Block_Seq (blocks). * Return a copy of the subset of the Block_Seq that matches it. */ Block_Seq *names_in_Block_Seq( char * name, Block_Seq * start_of_blocks, Boolean (*string_test)(char *, char *) ) { Data_Seq *tmp_ds; register Block_Seq * last_bs = NULL; register Block_Seq *blocks; Block_Seq * tmp_bs = NULL; Global_Seq *globals = NULL; Global_Seq *tmp_globals = NULL; Boolean name_found_in_globals = FALSE; static Boolean block_name_found = FALSE; for( blocks = start_of_blocks; blocks; blocks = blocks->next ) switch( blocks->tag ) { case DATA_BLOCK: if( string_test( name, blocks->name) ) { /* take the whole block */ if( ! block_name_found ) { /* haven't previously found this block */ block_name_found = TRUE; /* restart the search so that any leading globals are found */ return( names_in_Block_Seq( name, start_of_blocks,string_test)); } /* build a new node */ if( last_bs ) { Malloc( Block_Seq, last_bs->next ); last_bs = last_bs->next; } else { Malloc( Block_Seq, last_bs ); tmp_bs = last_bs; } last_bs->name = blocks->name; last_bs->tag = DATA_BLOCK; last_bs->block.data_block.actual_data = replicate_DS(blocks->block.data_block.actual_data); last_bs->block.data_block.global_data = globals; last_bs->next = NULL; } else { /* search the actual block */ if( (tmp_ds = names_in_Data_Seq(name, blocks->block.data_block.actual_data, string_test)) ) { if( last_bs ) { Malloc( Block_Seq, last_bs->next); last_bs = last_bs->next;} else { Malloc( Block_Seq, last_bs ); tmp_bs = last_bs; } /* add the found data */ last_bs->name = blocks->name; last_bs->tag = DATA_BLOCK; last_bs->block.data_block.actual_data = tmp_ds; last_bs->block.data_block.global_data = globals; last_bs->next = NULL; } else if( name_found_in_globals ) { /* add an empty block to satisfy the match in globals */ if( last_bs ) { Malloc( Block_Seq, last_bs->next); last_bs = last_bs->next;} else { Malloc( Block_Seq, last_bs ); tmp_bs = last_bs; } /* add the found data */ last_bs->name = blocks->name; last_bs->tag = DATA_BLOCK; last_bs->block.data_block.actual_data = NULL; last_bs->block.data_block.global_data = globals; last_bs->next = NULL; } } break; case GLOBAL_BLOCK: tmp_ds = NULL; if( string_test( name, blocks->name) ) { name_found_in_globals = TRUE; /* global_block directly found */ tmp_ds = replicate_DS(blocks->block.global_block); } else /* search the actual block */ if( (tmp_ds = names_in_Data_Seq( name, blocks->block.global_block, string_test))) name_found_in_globals = TRUE; else /* name not found in global block */ if( block_name_found ) /* implicitly include the global block */ /* get everything anyway */ tmp_ds = replicate_DS(blocks->block.global_block); if( tmp_ds ) { /* have something to add */ /* build a new node */ if( last_bs ) { Malloc( Block_Seq, last_bs->next ); last_bs = last_bs->next; } else { Malloc( Block_Seq, last_bs ); tmp_bs = last_bs; } last_bs->name = blocks->name; last_bs->tag = GLOBAL_BLOCK; last_bs->block.global_block = tmp_ds; last_bs->next = NULL; /* add this to the head of the list of globals */ Malloc( Global_Seq, tmp_globals ); tmp_globals->global_entry = last_bs; tmp_globals->next = globals; globals = tmp_globals; } break; default: ERROR_MSG("data_in_Block_Seq: unknown block in Block_Seq."); } /* reset static variable for later runs */ block_name_found = FALSE; return( tmp_bs ); } /* names_in_Block_Seq */ /* matches_re * Perform regular expression match between two strings. * Where the first string is the regular expression and the second the tested * string. * Both the reg'exp' and the candidate string are folded to lower case. * Returns TRUE if there is no match, FALSE otherwise. */ Boolean matches_re( char * re, char * string) { static char * last_re = NULL; /* compile the regular expression if necessary */ if( re != last_re ) { /* not the same reg'exp' as last time */ register char *tmp; char *err_msg = NULL; tmp = str_tolower( re ); if( (err_msg = re_comp( tmp )) ) { ERROR_MSG("matches_re: Error compiling regular expression."); ERROR_MSG( err_msg ); last_re = NULL; } else last_re = re; free( tmp ); } /* match the lowercase string against the regular expression */ switch( re_exec( str_tolower( string) ) ) { case 0: return( FALSE ); break; case 1: return( TRUE ); break; case -1: ERROR_MSG("matches_re: The regular expression was invalid."); break; default: ERROR_MSG("matches_re: Error in matching the regular expression."); } /* only get this far if there was a problem */ return( FALSE ); } /* matches_re */ /* wildcard_to_re * take a string and replace the existing * an ? for regular expression * denotation. */ /* ^...$ is necessary to force matching the whole word */ char *wildcard_to_re( char * string) { int rs_len = strlen(string) +3; /* need room for ^...$\0 */ char *s, *t, *rtn_string; DEBUG_MSG("wildcard_to_re: String to be converted ="); DEBUG_MSG(string); /* the new string will be at least as long as the old one */ if( (rtn_string = (char *)malloc( rs_len * sizeof(char) )) ) rtn_string = strcpy( rtn_string, "^"); else ERROR_MSG("wildcard_to_re: Out of memory."); s = string; while( s ) /* find next \, *, ? */ if( (t = strpbrk( s, "\\*?" )) ){ /* append the scanned characters */ rtn_string = strncat( rtn_string, s, (strlen(s) -strlen(t)) ); switch( *t ) { case '\\': /* peek at the next character */ switch( t[1] ){ case '?': /* remove the \ */ /* \? -> ? */ rtn_string = strcat( rtn_string, "?" ); s = t +2; break; case '\0': /* place the \, let the NULL sort itself out */ rtn_string = strcat( rtn_string, "\\" ); s = t +1; break; case '*': /* \* -> unchanged */ /* append as is */ default: /* anything_else -> unchanged */ rtn_string = strncat( rtn_string, t, 2 ); s = t +2; } break; case '*': if( (rtn_string = (char *)realloc(rtn_string, (rs_len += 6) * sizeof(char) )) ){ /* * -> [^\t ]* */ rtn_string = strcat( rtn_string, "[^\t ]*" ); } else ERROR_MSG("wildcard_to_re: Out of memory, in substituting * ."); s = t +1; break; case '?': /* ? -> . */ rtn_string = strcat( rtn_string, "." ); s = t +1; break; default: ERROR_MSG("wildcard_to_re: Stoped unknown character."); } } else { /* append the rest of the string */ rtn_string = strcat( rtn_string, s ); s = t; } rtn_string = strcat( rtn_string, "$" ); DEBUG_MSG("wildcard_to_re: Return String ="); DEBUG_MSG(rtn_string); return( rtn_string ); } /* wildcard_to_re */ /* str_tolowerstr * Use the tolower function to fold an entire string to lower case. */ char *str_tolower( char * string) { register char * rtn_string = NULL; register int i; if( (rtn_string = (char *)malloc( (strlen(string) +1) * sizeof(char) )) ) { for( i = 0; i < strlen(string); i++) rtn_string[i] = tolower( string[i] ); rtn_string[i] = '\0'; } else ERROR_MSG("str_tolower: Out of memory."); return( rtn_string ); } /* str_tolower */