/**CFile*********************************************************************** FileName [tblEntryUtil.c] PackageName [tbl] Synopsis [This package describes functions used to manipulate the Tbl_Entry_t ,Tbl_Row_t and Tbl_Range_t structs] Description [] SeeAlso [tblUtil.c] Author [Gitanjali M. Swamy] Copyright [Copyright (c) 1994-1996 The Regents of the Univ. of California. All rights reserved. Permission is hereby granted, without written agreement and without license or royalty fees, to use, copy, modify, and distribute this software and its documentation for any purpose, provided that the above copyright notice and the following two paragraphs appear in all copies of this software. IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.] ******************************************************************************/ #include "tblInt.h" static char rcsid[] UNUSED = "$Id: tblEntryUtil.c,v 1.16 2009/04/11 02:01:29 fabio Exp $"; /**AutomaticStart*************************************************************/ /*---------------------------------------------------------------------------*/ /* Static function prototypes */ /*---------------------------------------------------------------------------*/ static int RangeCompare(lsGeneric entry1, lsGeneric entry2); static void EntryCanonicalize(Tbl_Entry_t * entry); static void EntryComplement(Tbl_Entry_t * entry, int min, int max); /**AutomaticEnd***************************************************************/ /*---------------------------------------------------------------------------*/ /* Definition of exported functions */ /*---------------------------------------------------------------------------*/ /**Function******************************************************************** Synopsis [This function allocates space for a table entry.] Description [This function allocates space for a table entry and must be passed the type of the entry (Tbl_EntryEqual_c or Tbl_EntryNormal_c) as a parameter] SideEffects [] SeeAlso [TblEntryFree] ******************************************************************************/ Tbl_Entry_t* Tbl_EntryAlloc( Tbl_EntryType_t type) { Tbl_Entry_t *entry; entry = ALLOC(Tbl_Entry_t,1); entry->type = type; if (type == Tbl_EntryEqual_c) { entry->EntryData.var = -1; } else if (type == Tbl_EntryNormal_c) { entry->EntryData.listOfRanges = lsCreate(); } return entry; } /**Function******************************************************************** Synopsis [This frees a given Tbl_Entry_t] Description [This function frees the memory associated with a Tbl_Entry_t that is given as input] SideEffects [ The Var_Variable_t must be freed by the user] SeeAlso [TblEntryAlloc] ******************************************************************************/ void Tbl_EntryFree( Tbl_Entry_t * entry) { if (entry->type == Tbl_EntryNormal_c) { lsDestroy(entry->EntryData.listOfRanges,(void (*)(lsGeneric))TblRangeFree); } FREE(entry); entry = NIL(Tbl_Entry_t); } /**Function******************************************************************** Synopsis [Duplicate a Tbl_Entry_t ] Description [Given a Tbl_Entry_t, this function duplicates it. The new entry does not belong to any table.] SideEffects [Warning: For an entry of type Tbl_EntryEqual_c, this will merely duplicate the column number of the equal type with no consistancy checks. It is inadvisable to use this if you do not ensure that the column variable corresponding to this id is what it is indeed equal to] SeeAlso [Tbl_TableSetEntry] ******************************************************************************/ Tbl_Entry_t * Tbl_EntryDup( Tbl_Entry_t *entry) { Tbl_Entry_t *newEntry; lsGen gen; Tbl_Range_t *range; assert(entry != NIL(Tbl_Entry_t)); assert(entry->type != Tbl_EntryUnassigned_c); newEntry = Tbl_EntryAlloc(entry->type); newEntry->ioType = entry->ioType; newEntry->varColNum = entry->varColNum; if (entry->type == Tbl_EntryNormal_c) { lsForEachItem(entry->EntryData.listOfRanges, gen, range) { Tbl_Range_t *newRange = ALLOC(Tbl_Range_t,1); newRange->begin = range->begin; newRange->end = range->end; lsNewEnd(newEntry->EntryData.listOfRanges,(lsGeneric)newRange,LS_NH); } } else if (entry->type == Tbl_EntryEqual_c) { newEntry->EntryData.var = entry->EntryData.var; } return newEntry; } /**Function******************************************************************** Synopsis [Set value of entry to range val1-val2] Description [Given an entry and a range designated by val1-val2, this function sets the entry value to val1-val2. If the entry was already set then it adds the value to the end, and also canonicalizes the list] SideEffects [If the entry was already set then it adds the value to the end] SeeAlso [] ******************************************************************************/ void Tbl_EntrySetValue( Tbl_Entry_t * entry, int val1, int val2) { Tbl_Range_t *range; assert(val2 >= val1); assert(val1 >= 0); entry->type = Tbl_EntryNormal_c; range = ALLOC(Tbl_Range_t,1); range->begin = val1; range->end = val2; lsNewEnd(entry->EntryData.listOfRanges,(lsGeneric)range,LS_NH); EntryCanonicalize(entry); } /**Function******************************************************************** Synopsis [Given two Tbl_Entry_t's this function merges them into one.] Description [Given two Tbl_entry_t* and b , this function returns new Tbl_Entry_t* that is the union of them.] SideEffects [Both Tbl_Entries must be of the type Tbl_EntryNormal_c] SeeAlso [] ******************************************************************************/ Tbl_Entry_t* Tbl_EntryMerge( Tbl_Entry_t* entry1, Tbl_Entry_t* entry2) { lsGen gen, gen2,newGen; Tbl_Range_t *range, *newRange; Tbl_Entry_t *newEntry; if ((entry1->type == Tbl_EntryEqual_c)||(entry2->type == Tbl_EntryEqual_c)) { return NIL(Tbl_Entry_t); } if ((entry1->type == Tbl_EntryUnassigned_c)||(entry2->type == Tbl_EntryUnassigned_c)) { return NIL(Tbl_Entry_t); } newEntry = Tbl_EntryAlloc(Tbl_EntryNormal_c); newGen = lsStart(newEntry->EntryData.listOfRanges); lsForEachItem(entry1->EntryData.listOfRanges, gen, range) { newRange = ALLOC(Tbl_Range_t,1); newRange->begin = range->begin; newRange->end = range->end; lsInAfter(newGen,(lsGeneric)newRange,LS_NH); } lsForEachItem(entry2->EntryData.listOfRanges, gen2, range) { newRange = ALLOC(Tbl_Range_t,1); newRange->begin = range->begin; newRange->end = range->end; lsInAfter(newGen,(lsGeneric)newRange,LS_NH); } EntryCanonicalize(newEntry); lsFinish(newGen); return newEntry; } /**Function******************************************************************** Synopsis [Complement the entry] Description [Given an entry, and the associated minimum and maximum values of the entry, this function complements it] SideEffects [Old entry is lost] SeeAlso [] ******************************************************************************/ void Tbl_EntryComplement( Tbl_Entry_t * entry, int min, int max) { EntryComplement(entry, min, max); EntryCanonicalize(entry); } /**Function******************************************************************** Synopsis [Sets entry equal to given Var] Description [Given an Entry and an int, this sets the entry equal to the column varCol. The Var must be part of the table] SideEffects [] SeeAlso [] ******************************************************************************/ void Tbl_EntrySetEqual( Tbl_Entry_t * entry, /* Var_Variable_t * var*/ int varCol) { entry->type=Tbl_EntryEqual_c; entry->EntryData.var = varCol; } /**Function******************************************************************** Synopsis [Check if values in entry data are from val1-val2 alone.] Description [Given an entry and a range val1-val2, then this function returns a 1 if every value in the entry is in the range val1-val2.] SideEffects [] SeeAlso [] ******************************************************************************/ boolean Tbl_EntryCheckRange( Tbl_Entry_t * entry, int val1, int val2) { lsGen gen; lsGeneric data; Tbl_Range_t *range; gen = lsStart(entry->EntryData.listOfRanges); while (lsNext(gen, &data, LS_NH) == LS_OK) { range = (Tbl_Range_t*)data; if (range->begin < val1) { lsFinish(gen); return FALSE; } if (range->end > val2) { lsFinish(gen); return FALSE; } } lsFinish(gen); return TRUE; } /**Function******************************************************************** Synopsis [Test if entry is of type equal] Description [optional] SideEffects [required] SeeAlso [optional] ******************************************************************************/ boolean Tbl_EntryIsEqual( Tbl_Entry_t *entry) { return (entry->type==Tbl_EntryEqual_c); } /**Function******************************************************************** Synopsis [return the actual variable associated with an entry] Description [Given an entry and a table, this function will return the actual Var_Variable_t in the table associated with this entry] SideEffects [] SeeAlso [Tbl_EntryReadVar] ******************************************************************************/ Var_Variable_t* Tbl_EntryReadActualVar( Tbl_Table_t *table, Tbl_Entry_t *entry) { array_t *carray; if (entry->ioType==0) { carray = table->inputNames; } else if (entry->ioType==1) { carray = table->outputNames; } else return NIL(Var_Variable_t); return (array_fetch(Var_Variable_t*,carray,entry->varColNum)); } /**Function******************************************************************** Synopsis [return the equal variable associated with an entry] Description [Given an entry and a table, this function will return the Equal Var_Variable_t in the table associated with this entry] SideEffects [] SeeAlso [Tbl_EntryReadActualVar] ******************************************************************************/ Var_Variable_t* Tbl_EntryReadVar( Tbl_Table_t *table, Tbl_Entry_t *entry) { array_t *carray; carray = table->inputNames; if (array_n(carray) < Tbl_EntryReadVarIndex(entry)) { fail(" FAIL: equal to output not supported\n"); } return (array_fetch(Var_Variable_t*,carray,Tbl_EntryReadVarIndex(entry))); } /**Function******************************************************************** Synopsis [This function returns the index associated with the entry. The entry must be of the type equal] Description [] SideEffects [] SeeAlso [] ******************************************************************************/ int Tbl_EntryReadVarIndex( Tbl_Entry_t * entry) { assert(entry->type == Tbl_EntryEqual_c); return (entry->EntryData.var); } /**Function******************************************************************** Synopsis [Return Num of values in an entry] Description [Given a Tbl_Entry_t, this function will return the number of values that the variable in the entry actually takes. Note that the possible number of values might be much larger] SideEffects [] SeeAlso [] ******************************************************************************/ int Tbl_EntryReadNumValues( Tbl_Entry_t * entry) { lsGen gen; int numOfValues; Tbl_Range_t *range; numOfValues = 0; assert(entry->type == Tbl_EntryNormal_c); lsForEachItem(entry->EntryData.listOfRanges, gen, range) { numOfValues = numOfValues + (range->end - range->begin + 1); } return (numOfValues); } /**Function******************************************************************** Synopsis [Compare two entries] Description [Given two Tbl_Entry_t, this function will compare them to see if they are equal. Both the entries must be canonical, and of the type Tbl_EntryNormal_c] SideEffects [] SeeAlso [] ******************************************************************************/ boolean Tbl_EntryTestEqualEntry( Tbl_Entry_t * entrya, Tbl_Entry_t * entryb) { lsGen gena; lsGen genb; Tbl_Range_t *rangea; Tbl_Range_t *rangeb; lsGeneric data; assert(entrya->type == Tbl_EntryNormal_c); assert(entryb->type == Tbl_EntryNormal_c); if (lsLength(entrya->EntryData.listOfRanges) != \ lsLength(entryb->EntryData.listOfRanges)) { return FALSE; } genb = lsStart(entryb->EntryData.listOfRanges); lsForEachItem(entrya->EntryData.listOfRanges, gena, rangea) { if (lsNext(genb, &data,LS_NH) == LS_OK) { rangeb = (Tbl_Range_t*)data; if (rangea->begin != rangeb->begin) { lsFinish(gena); lsFinish(genb); return FALSE; } if (rangea->end != rangeb->end){ lsFinish(gena); lsFinish(genb); return FALSE; } } else { return FALSE; } } return TRUE; } /**Function******************************************************************** Synopsis [Compare two entries to see if they intersect ] Description [Given two Tbl_Entry_t, this function will compare them to see if they intersect. Both the entires must be canonical, and of the type Tbl_EntryNormal_c. The function moves over both lists of ranges, and checks to see if the begin of any range if less that or equal to the ] SideEffects [] SeeAlso [] ******************************************************************************/ boolean Tbl_EntryTestIntersectEntry( Tbl_Entry_t * entrya, Tbl_Entry_t * entryb) { lsGen gena; lsGen genb; lsGeneric dataa; lsGeneric datab; boolean checka, checkb; Tbl_Range_t *rangea = NIL(Tbl_Range_t); Tbl_Range_t *rangeb = NIL(Tbl_Range_t); assert(entrya->type == Tbl_EntryNormal_c); assert(entryb->type == Tbl_EntryNormal_c); gena = lsStart(entrya->EntryData.listOfRanges); genb = lsStart(entryb->EntryData.listOfRanges); checka = TRUE; checkb = TRUE; while((checka)||(checkb)) { if (checka) { if (lsNext(gena, &dataa,LS_NH) == LS_OK) { rangea = (Tbl_Range_t*)dataa; } else { lsFinish(gena); lsFinish(genb); return FALSE; } } if (checkb) { if (lsNext(genb, &datab,LS_NH) == LS_OK) { rangeb = (Tbl_Range_t*)datab; } else { lsFinish(gena); lsFinish(genb); return FALSE; } } if ((rangea->begin <= rangeb->end) &&(rangeb->begin <= rangea->end)) { lsFinish(gena); lsFinish(genb); return TRUE; } else if (rangea->end < rangeb->begin){ checka = TRUE; checkb = FALSE; } else { checka = FALSE; checkb = TRUE; } } lsFinish(gena); lsFinish(genb); return FALSE; } /**Function******************************************************************** Synopsis [Return lsList of values in an entry] Description [] SideEffects [This list is NOT to be modified. The user is encouraged not to use this function. It is exported so as to make the macros for iteration over items in the entry possible. The user should use these macros for accessing data. The macros that can be used are mentioned in the SeeAlso list] SeeAlso [Tbl_EntryForEachValue] ******************************************************************************/ lsList Tbl_EntryReadList( Tbl_Entry_t * entry) { return (entry->EntryData.listOfRanges); } /**Function******************************************************************** Synopsis [Return the type of the given entry] Description [Given a Tbl_Entry_t, this function returns its type, either Tbl_EntryEqual_c or Tbl_EntryNormal_c.] SideEffects [] SeeAlso [] ******************************************************************************/ Tbl_EntryType_t Tbl_EntryReadType( Tbl_Entry_t *entry) { return (entry->type); } /*---------------------------------------------------------------------------*/ /* Definition of internal functions */ /*---------------------------------------------------------------------------*/ /**Function******************************************************************** Synopsis [Returns the mdd_t* for a table entry] Description [Given an array of constituent mdd_t*, and a table entry, this returns an mdd for the entry. The array of mdd_t's must contain an mdd_t for value i in position i, for all values i.] SideEffects [] SeeAlso [] ******************************************************************************/ mdd_t * TblEntryNormalConstructMdd( mdd_manager *manager, Tbl_Entry_t * entry, array_t * mddArray) { lsGen gen; Tbl_Range_t *range; int i; mdd_t *result, *temp, *x; result = mdd_zero(manager); lsForEachItem(entry->EntryData.listOfRanges, gen, range) { for (i=range->begin; i< (range->end +1); i++) { temp = result; x = Mvf_FunctionObtainComponent(mddArray,i); result = mdd_or(temp, x,1,1); mdd_free(temp); mdd_free(x); } } return result; } /**Function******************************************************************** Synopsis [Returns the mdd_t* for a table entry] Description [Given an array of constituent mdd_t*, and a table entry, this returns an mdd for the entry. The array of mdd_t's must contain an mdd_t for value i in position i, for all values i.] SideEffects [] SeeAlso [] ******************************************************************************/ mdd_t * TblEntryEqualConstructMdd( mdd_manager *manager, Tbl_Entry_t * entry, Mvf_Function_t * mddArray, Mvf_Function_t * mddEArray) { lsGen gen; Tbl_Range_t *range; int i; mdd_t *result, *temp, *x; assert(entry->type == Tbl_EntryNormal_c); result = mdd_zero(manager); lsForEachItem(entry->EntryData.listOfRanges, gen, range) { for (i=range->begin; i< (range->end +1); i++) { temp = result; x = Mvf_FunctionObtainComponent(mddArray,i); result = mdd_or(temp, x,1,1); mdd_free(temp); temp = result; x = Mvf_FunctionObtainComponent(mddEArray,i); result = mdd_or(temp, x,1,1); mdd_free(temp); } } return result; } /**Function******************************************************************** Synopsis [print an entry in symbolic form.] Description [Given a Tbl_Entry_t , a fileptr and a table, this function prints it in blif_mv format. This function accounts for variables with symbolic values] SideEffects [] SeeAlso [Tbl_TableWriteBlif] ******************************************************************************/ void TblEntryWriteBlifMv( Tbl_Table_t *table, Tbl_Entry_t *entry, FILE *fp) { lsGen gen; Tbl_Range_t *range; Var_Variable_t *var; boolean test, testParen; int i, itemNum, length; var = Tbl_EntryReadActualVar(table,entry); test = Var_VariableTestIsSymbolic(var); testParen = TRUE; if (entry != NIL(Tbl_Entry_t)) { if (entry->type == Tbl_EntryNormal_c) { length = lsLength(entry->EntryData.listOfRanges); if (length == 1){ var = Tbl_EntryReadActualVar(table,entry); lsForEachItem(entry->EntryData.listOfRanges, gen, range) { if ((range->begin ==0)&&(range->end == Var_VariableReadNumValues(var)-1)){ fprintf(fp,"-"); lsFinish(gen); return; } } } itemNum = 1; if (length ==1) { testParen = FALSE; } lsForEachItem(entry->EntryData.listOfRanges, gen, range) { if (itemNum ==1) { if (testParen) { fprintf(fp,"("); } } if (itemNum < length) { if (test == FALSE) { if (range->end != range->begin) { fprintf(fp,"{%d-%d},", range->begin, range->end); } else { fprintf(fp,"%d,", range->end); } } else { if (range->end != range->begin) { fprintf(fp,"(%s,",Var_VariableReadSymbolicValueFromIndex(var,range->begin)); for (i= range->begin+1; i < range->end ; i++) { fprintf(fp,"%s,",Var_VariableReadSymbolicValueFromIndex(var,i)); } fprintf(fp,"%s),",Var_VariableReadSymbolicValueFromIndex(var,range->end)); } else { fprintf(fp,"%s,",Var_VariableReadSymbolicValueFromIndex(var,range->end)); } } } else { if (test == FALSE) { if (range->end != range->begin) fprintf(fp,"{%d-%d}", range->begin, range->end); else fprintf(fp,"%d", range->end); } else { if (range->end != range->begin) { fprintf(fp,"(%s,",Var_VariableReadSymbolicValueFromIndex(var,range->begin)); for (i= range->begin+1; i < range->end ; i++) { fprintf(fp,"%s,",Var_VariableReadSymbolicValueFromIndex(var,i)); } fprintf(fp,"%s)",Var_VariableReadSymbolicValueFromIndex(var,range->end)); } else { fprintf(fp,"%s",Var_VariableReadSymbolicValueFromIndex(var,range->end)); } } } itemNum++; } if (testParen) { fprintf(fp,")"); } } else if (entry->type == Tbl_EntryEqual_c) { fprintf(fp,"=%s", Var_VariableReadName(Tbl_EntryReadVar(table,entry))); } } else printf("NIL Entry "); } /**Function******************************************************************** Synopsis [print an entry in symbolic form.] Description [Given a Tbl_Entry_t , a fileptr and a table, this function prints it in smv format. This function accounts for variables with symbolic values] SideEffects [] SeeAlso [Tbl_TableWriteBlif, Tbl_TableWriteBlifMv] ******************************************************************************/ void TblEntryWriteSmv( Tbl_Table_t *table, Tbl_Entry_t *entry, boolean varnameflag, FILE *fp) { lsGen gen; Tbl_Range_t *range; Var_Variable_t *var; boolean symbolic, testParen; int i, itemNum, length; var = Tbl_EntryReadActualVar(table,entry); symbolic = Var_VariableTestIsSymbolic(var); testParen = TRUE; if (entry != NIL(Tbl_Entry_t)) { if (entry->type == Tbl_EntryNormal_c) { length = lsLength(entry->EntryData.listOfRanges); if (length == 1){ var = Tbl_EntryReadActualVar(table,entry); lsForEachItem(entry->EntryData.listOfRanges, gen, range) { if ((range->begin ==0)&&(range->end == Var_VariableReadNumValues(var)-1)){ fprintf(fp,"1"); /* A don't-care is always true */ lsFinish(gen); return; } } } if (!varnameflag) { fprintf(fp,"("); Io_SmvPrintVar(fp,var); } itemNum = 1; if (length ==1) { testParen = FALSE; } lsForEachItem(entry->EntryData.listOfRanges, gen, range) { if (!varnameflag) { if (itemNum ==1) { if (testParen) { fprintf(fp," IN {"); } else { fprintf(fp, "="); } } } if (itemNum < length) { if (symbolic == FALSE) { if (range->end != range->begin) { for (i= range->begin; i < range->end ; i++) fprintf(fp,"%d,",i); } fprintf(fp,"%d,", range->end); } else { if (range->end != range->begin) { fprintf(fp,"%s,",Var_VariableReadSymbolicValueFromIndex(var,range->begin)); for (i= range->begin+1; i < range->end ; i++) { fprintf(fp,"%s,",Var_VariableReadSymbolicValueFromIndex(var,i)); } fprintf(fp,"%s,",Var_VariableReadSymbolicValueFromIndex(var,range->end)); } else { fprintf(fp,"%s,",Var_VariableReadSymbolicValueFromIndex(var,range->end)); } } } else { if (symbolic == FALSE) { if (range->end != range->begin) { for (i= range->begin; i < range->end ; i++) fprintf(fp,"%d,",i); } fprintf(fp,"%d", range->end); } else { if (range->end != range->begin) { fprintf(fp,"%s,",Var_VariableReadSymbolicValueFromIndex(var,range->begin)); for (i= range->begin+1; i < range->end ; i++) { fprintf(fp,"%s,",Var_VariableReadSymbolicValueFromIndex(var,i)); } fprintf(fp,"%s",Var_VariableReadSymbolicValueFromIndex(var,range->end)); } else { fprintf(fp,"%s",Var_VariableReadSymbolicValueFromIndex(var,range->end)); } } } itemNum++; } if (testParen) { fprintf(fp,"} "); } if (!varnameflag) { fprintf(fp, ") "); } } else if (entry->type == Tbl_EntryEqual_c) { if (!varnameflag) { Io_SmvPrintVar(fp, var); fprintf(fp,"="); } Io_SmvPrintVar(fp, Tbl_EntryReadVar(table,entry)); } } else printf("NIL Entry "); } /**Function******************************************************************** Synopsis [print an entry in blif form.] Description [Given a Tbl_Entry_t , a fileptr and a table, this function prints it in blif format.] SideEffects [] SeeAlso [] ******************************************************************************/ void TblEntryWriteBlif( Tbl_Table_t *table, Tbl_Entry_t *entry, FILE *fp) { lsGen gen; Tbl_Range_t *range; Var_Variable_t *var; boolean test; int i, itemNum, length; var = Tbl_EntryReadActualVar(table,entry); test = Var_VariableTestIsSymbolic(var); if (entry != NIL(Tbl_Entry_t)) { if (entry->type == Tbl_EntryNormal_c) { length = lsLength(entry->EntryData.listOfRanges); if (length == 1){ var = Tbl_EntryReadActualVar(table,entry); lsForEachItem(entry->EntryData.listOfRanges, gen, range) { if ((range->begin ==0)&&(range->end == Var_VariableReadNumValues(var)-1)){ fprintf(fp,"-"); lsFinish(gen); return; } } } length = lsLength(entry->EntryData.listOfRanges); itemNum = 1; lsForEachItem(entry->EntryData.listOfRanges, gen, range) { if (itemNum < length) { if (test == FALSE) { if (range->end != range->begin) { fprintf(fp,"{%d-%d},", range->begin, range->end); } else { fprintf(fp,"%d,", range->end); } } else { if (range->end != range->begin) { for (i= range->begin; i < range->end ; i++) { fprintf(fp,"%s,",Var_VariableReadSymbolicValueFromIndex(var,i)); } fprintf(fp,"%s",Var_VariableReadSymbolicValueFromIndex(var,range->end)); } else { fprintf(fp,"%s,",Var_VariableReadSymbolicValueFromIndex(var,range->end)); } } } else { if (test == FALSE) { if (range->end != range->begin) fprintf(fp,"{%d-%d}", range->begin, range->end); else fprintf(fp,"%d", range->end); } else { if (range->end != range->begin) { for (i= range->begin; i < range->end ; i++) { fprintf(fp,"%s,",Var_VariableReadSymbolicValueFromIndex(var,i)); } fprintf(fp,"%s",Var_VariableReadSymbolicValueFromIndex(var,range->end)); } else { fprintf(fp,"%s",Var_VariableReadSymbolicValueFromIndex(var,range->end)); } } } itemNum++; } } else if (entry->type == Tbl_EntryEqual_c) { fprintf(fp," =%s ",Var_VariableReadName(Tbl_EntryReadVar(table,entry))); } } else printf("NIL Entry "); } /**Function******************************************************************** Synopsis [This frees a given Tbl_Entry_t] Description [This function frees the memory assocated with a Tbl_Entry_t that is given as input] SideEffects [ The Var_Variable_t must be freed by the user] SeeAlso [TblEntryAlloc] ******************************************************************************/ void TblRangeFree( Tbl_Range_t * range) { FREE(range); } /**Function******************************************************************** Synopsis [return the begin value of a Tbl_Range_t] Description [] SideEffects [The user is encouraged not to use this function. It is exported so as to make the macros for iteration over items in the table possible. The user should use these macros for accessing data. The macros that can be used are mentioned in the SeeAlso list] SeeAlso [] ******************************************************************************/ int Tbl_RangeBegin( Tbl_Range_t *range) { return(range->begin); } /**Function******************************************************************** Synopsis [return the end value of a Tbl_Range_t] Description [] SideEffects [The user is encouraged not to use this function. It is exported so as to make the macros for iteration over items in the table possible. The user should use these macros for accessing data. The macros that can be used are mentioned in the SeeAlso list] SeeAlso [] ******************************************************************************/ int Tbl_RangeEnd( Tbl_Range_t *range) { return(range->end); } /*---------------------------------------------------------------------------*/ /* Definition of static functions */ /*---------------------------------------------------------------------------*/ /**Function******************************************************************** Synopsis [A function for comparing 2 ranges] Description [This function return a -1 if range1 is subset of range2, a 1 if range1 is a superset of range2, and 0 if neither statement is true] SideEffects [] SeeAlso [EntryCanonicalize] ******************************************************************************/ static int RangeCompare( lsGeneric entry1, lsGeneric entry2) { Tbl_Range_t * range1 = (Tbl_Range_t *) entry1; Tbl_Range_t * range2 = (Tbl_Range_t *) entry2; int value = 0; if (range1->begin > range2->begin) { value = 1; } else if (range1->begin < range2->begin) { value = -1; } else if (range1->begin == range2->begin) { if (range1->end > range2->end) { value = 1; } else if (range1->end < range2->end) { value = -1; } } return value; } /**Function******************************************************************** Synopsis [Canonicalize a table entry] Description [Given a table entry, this canonicalizes the lsList of ranges by sorting and merging the ranges. If the entry is of Tbl_EntryEqual_c type, it returns without making any changes. Note that the gen in the list package has positions in between prev and next items, and hence after each deletion its position has to be re-adjusted. This function iterates over the entire list of ranges and checks to see if two sucessive ranges overlap. If they do, this function creates a larger list containing bothe ranges, adds it to the list and subtracts the other two.] SideEffects [The old table list of ranges is lost] SeeAlso [] ******************************************************************************/ static void EntryCanonicalize( Tbl_Entry_t * entry) { lsGen gen; Tbl_Range_t *range, *newRange, *nextRange; lsGeneric data; if (entry->type == Tbl_EntryEqual_c) { return; } if (entry->type == Tbl_EntryUnassigned_c) { return; } if (lsLength(entry->EntryData.listOfRanges) > 1) { lsSort(entry->EntryData.listOfRanges,RangeCompare); lsForEachItem(entry->EntryData.listOfRanges, gen, range) { if (lsNext(gen, &data,LS_NH) == LS_OK) { nextRange = (Tbl_Range_t*)data; if (nextRange->begin < (range->end + 2)) { if (nextRange->end > range->end) { newRange = ALLOC(Tbl_Range_t,1); newRange->begin = range->begin; newRange->end = nextRange->end; lsInAfter(gen,(lsGeneric)newRange,LS_NH); lsDelBefore(gen,(lsGeneric*)nextRange); TblRangeFree(nextRange); lsDelBefore(gen,(lsGeneric*)range); TblRangeFree(range); } else { lsDelBefore(gen,(lsGeneric*)nextRange); TblRangeFree(nextRange); if (lsPrev(gen,&data,LS_NH)!= LS_OK) { (void) lsFinish(gen); } } } else { lsPrev(gen,&data,LS_NH); } } } } } /**Function******************************************************************** Synopsis [Complement the entry of a table] Description [Given a table entry, this complement the entry by getting the complement list of ranges. Note that the list must be canonical. The list that is returned is canonical by construction. Notice that the min and max values for the Var_Variable_t associated with the entry must be provided.] SideEffects [The old table list of ranges is lost.] SeeAlso [] ******************************************************************************/ static void EntryComplement( Tbl_Entry_t * entry, int min, int max) { lsGen gen, newGen; Tbl_Range_t *range, *newRange, *nextRange; lsList newRangeList; int listMin, listMax; lsGeneric data; if (entry->type == Tbl_EntryEqual_c) { return; } if (entry->type == Tbl_EntryUnassigned_c) { return; } listMin = max; listMax = min; newRangeList = lsCreate(); newGen = lsStart(newRangeList); lsForEachItem(entry->EntryData.listOfRanges, gen, range) { if (lsNext(gen, &data, LS_NH) == LS_OK) { nextRange = (Tbl_Range_t*)data; newRange = ALLOC(Tbl_Range_t,1); newRange->begin = range->end +1; newRange->end = nextRange->begin -1; lsInAfter(newGen,(lsGeneric)newRange,LS_NH); lsPrev(gen, &data, LS_NH); } if (listMin > range->begin) listMin = range->begin; if (listMax < range->end) listMax = range->end; } lsFinish(newGen); if (min < listMin) { newRange = ALLOC(Tbl_Range_t,1); newRange->begin = min; newRange->end = listMin -1; lsNewBegin(newRangeList,(lsGeneric)newRange,LS_NH); } if (listMax < max) { newRange = ALLOC(Tbl_Range_t,1); newRange->begin = listMax +1; newRange->end = max; lsNewEnd(newRangeList,(lsGeneric)newRange,LS_NH); } lsDestroy(entry->EntryData.listOfRanges,(void (*)(lsGeneric))TblRangeFree); entry->EntryData.listOfRanges = newRangeList; }