source: vis_dev/vis-2.3/src/tbl/tblUtil.c @ 84

Last change on this file since 84 was 14, checked in by cecile, 13 years ago

vis2.3

File size: 96.9 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [ tblUtil.c ]
4
5  PackageName [ tbl ]
6
7  Synopsis    [ This package is used to manipulate the table data structure ]
8
9  Description [ The table data structure is used to store the information
10               contained in the blif_mv table. This structure supports all
11               constructs in blif_mv including  the recursive constructs.
12               This is consistent with the previous version of this data-
13               structure. Note that the table package is in no way concerned
14               with the semantics of the table constructed; it makes no
15               interpretation on the correctness of a table (i.e. does
16               it represent valid hardware)]
17
18  SeeAlso     [ tbl.h, tblEntryUtil.c ]
19
20  Author      [ Gitanjali M. Swamy ]
21
22  Copyright   [Copyright (c) 1994-1996 The Regents of the Univ. of California.
23  All rights reserved.
24
25  Permission is hereby granted, without written agreement and without license
26  or royalty fees, to use, copy, modify, and distribute this software and its
27  documentation for any purpose, provided that the above copyright notice and
28  the following two paragraphs appear in all copies of this software.
29
30  IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
31  DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
32  OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
33  CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34
35  THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
36  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
37  FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS ON AN
38  "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE
39  MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]
40
41******************************************************************************/
42#include "tblInt.h"
43
44static char rcsid[] UNUSED = "$Id: tblUtil.c,v 1.19 2009/04/11 02:01:29 fabio Exp $";
45
46/*---------------------------------------------------------------------------*/
47/* Type declarations                                                    */
48/*---------------------------------------------------------------------------*/
49
50/* Structure used to sort table inputs. */
51typedef struct varOrdStruct {
52  int id;                       /* input column number */
53  int rank;                     /* low-ranked columns should go first */
54} Var_Ord_t;
55
56
57/**AutomaticStart*************************************************************/
58
59/*---------------------------------------------------------------------------*/
60/* Static function prototypes                                                */
61/*---------------------------------------------------------------------------*/
62
63static int TableEntryComputeHashVal(Tbl_Table_t *table, Tbl_Entry_t *entry);
64static array_t* TableCreatIntArray(int size);
65static char* TableObtainSignature(Tbl_Table_t * table, int outputColumn);
66static int varCompare(const void *x, const void *y);
67
68/**AutomaticEnd***************************************************************/
69
70
71/*---------------------------------------------------------------------------*/
72/* Definition of exported functions                                          */
73/*---------------------------------------------------------------------------*/
74
75/**Function***********************************************************
76
77  Synopsis      [ Allocate a new table. ]
78
79  Description   [ This functions allocates memory for and returns a new table ]
80
81  SideEffects   [ ]
82
83  SeeAlso       [ Tbl_Free ]
84**********************************************************************/
85Tbl_Table_t*
86Tbl_TableAlloc(void)
87{
88  Tbl_Table_t * table;
89
90  table = ALLOC(Tbl_Table_t,1);
91  table->inputNames = array_alloc(Var_Variable_t*,0);
92  table->outputNames = array_alloc(Var_Variable_t*,0);
93  table->data = ALLOC(Tbl_Data_t,1); 
94  TblTableReadDefaults(table) = array_alloc(Tbl_Entry_t*,0);
95  TblTableReadRefCount(table) = 1;
96  TblTableReadData(table) = array_alloc(Tbl_Row_t*,0);
97  return table;
98}
99
100
101/**Function***********************************************************
102  Synopsis      [ Free a table. ]
103
104  Description   [ Given a table, this routine decreases the table refcount. If
105  the refCount == 1 then it also frees it, i.e. it  also frees each and every
106  Tbl_Entry_t entry in the table ]
107
108  SideEffects   [ Does not free the Vars associated with the table. This is
109                  the responsibility of the user.]
110
111  SeeAlso       [ Tbl_Alloc ]
112**********************************************************************/
113void
114Tbl_TableFree(
115  Tbl_Table_t *  table /* The table to be freed */)
116{
117  int i,j,k;
118  Tbl_Row_t * row;
119  Tbl_Entry_t *entry;
120   
121   
122  if (table != NIL(Tbl_Table_t)) {
123    if (TblTableReadRefCount(table) < 2) {
124  Tbl_TableForEachEntry(table,j,i,k,entry) {
125      if (entry != NIL(Tbl_Entry_t)) {
126        Tbl_EntryFree(entry);
127      }
128    }                       
129    TblTableForEachRow(table,row,i){
130      array_free(row->inputs);
131      array_free(row->outputs);
132      FREE(row);
133    }
134    Tbl_TableForEachDefaultEntry(table,entry,i) {
135      if (entry != NIL(Tbl_Entry_t)) {
136        Tbl_EntryFree(entry);
137      }
138    }           
139    array_free(TblTableReadDefaults(table));
140    array_free(TblTableReadData(table));
141    FREE(table->data);
142 
143    }
144  else {
145    TblTableReadRefCount(table)--;;
146  }
147    array_free(table->inputNames);
148    array_free(table->outputNames);
149    FREE(table);
150  }
151}   
152
153/**Function***********************************************************
154
155  Synopsis      [ Soft Duplicate a table. ]
156
157  Description   [ This routines increases the refcounts of the table. ]
158
159  SideEffects   [ Do not modify the soft duplicate tables's entries; it
160  will modify the original table. For this use Tbl_TableHardDup]
161
162  SeeAlso       [ Tbl_TableFree Tbl_TableHardDup]
163**********************************************************************/
164Tbl_Table_t *
165Tbl_TableSoftDup(
166  Tbl_Table_t *  table /* The table to be duplicated */)
167{
168  Tbl_Table_t *tabledup;
169
170  assert(TblTableReadRefCount(table) >0);
171  tabledup = ALLOC(Tbl_Table_t,1);
172  tabledup->data = table->data;
173
174  tabledup->inputNames = array_dup(table->inputNames);
175  tabledup->outputNames = array_dup(table->outputNames);
176 
177  TblTableReadRefCount(table) ++;
178  return tabledup;
179}
180
181/**Function***********************************************************
182
183  Synopsis      [ Duplicate a table. ]
184
185  Description   [ This routines creates a duplicate of table. However
186                  table entries are copied, but not Vars.  ]
187
188  SideEffects   [  ]
189
190  SeeAlso       [ Tbl_TableFree Tbl_TableSoftDup]
191**********************************************************************/
192Tbl_Table_t *
193Tbl_TableHardDup(
194  Tbl_Table_t *  table /* The table to be duplicated */)
195{
196  Tbl_Table_t * tabledup;
197  int i;
198  Tbl_Entry_t *newEntry, *entry;
199  Var_Variable_t *var;
200  Tbl_Row_t *row;
201
202  tabledup = Tbl_TableAlloc();
203
204  Tbl_TableForEachInputVar(table,i,var){
205    Tbl_TableAddColumn(tabledup,var,0);
206  }
207
208  Tbl_TableForEachOutputVar(table,i,var){
209    Tbl_TableAddColumn(tabledup,var,1);
210  } 
211
212  Tbl_TableForEachDefaultEntry(table,entry,i) {
213    if (entry != NIL(Tbl_Entry_t)) {
214      newEntry = Tbl_EntryDup(entry);
215    }
216    else {
217      newEntry = NIL(Tbl_Entry_t);
218    }
219    (void) Tbl_TableDefaultSetEntry(tabledup,newEntry,i);
220  }
221
222  TblTableForEachRow(table,row,i){
223    TblTableSetRow(tabledup,TblRowDup(row),i);
224  }
225 
226  return tabledup;
227}
228
229
230/**Function********************************************************************
231
232  Synopsis    [Set the default value at given index]
233
234  Description [Given a Tbl_Table_t, a default Tbl_Entry_t and an index, this
235  sets the value of the default at this index to the entry. If the value of the
236  index is larger than the default array size, this return a 0, else it
237  sets the value and returns a 1.]
238
239  SideEffects []
240
241  SeeAlso     [Tbl_TableDefaultReadEntry]
242
243******************************************************************************/
244boolean
245Tbl_TableDefaultSetEntry(
246    Tbl_Table_t *table,
247    Tbl_Entry_t *entry,
248    int index)
249{
250  if (TblTableReadRefCount(table) > 1) {
251    printf(" WARNING: You are modifying more than one table by re-setting this entry\n");
252  }
253 
254  if (array_n(TblTableReadDefaults(table)) < index) {
255    return FALSE; 
256  }
257 
258  if (entry != NIL(Tbl_Entry_t)) {
259    entry->ioType = 1;
260    entry->varColNum = index;
261    /* debug */
262    if (entry->type == Tbl_EntryEqual_c)
263    assert(Tbl_EntryReadVarIndex(entry) < Tbl_TableReadNumInputs(table));   
264  }
265 
266 
267  array_insert(Tbl_Entry_t*, TblTableReadDefaults(table),index,entry);
268  return TRUE;
269}
270
271/**Function********************************************************************
272
273  Synopsis    [Read the default value at given index]
274
275  Description [Given a Tbl_Table_t and an index, this
276  reads  the value of the default entry, and returns it.
277  If the index is larger than the array size, it returns a
278  NIL entry]
279
280  SideEffects []
281
282  SeeAlso     [Tbl_TableDefaultSetEntry]
283
284******************************************************************************/
285Tbl_Entry_t*
286Tbl_TableDefaultReadEntry(
287    Tbl_Table_t *table,
288    int index)
289{
290  if (array_n(TblTableReadDefaults(table)) < index) {
291    return NIL(Tbl_Entry_t); 
292  }
293
294  return (array_fetch(Tbl_Entry_t*, TblTableReadDefaults(table),index));
295}
296
297   
298/**Function***********************************************************
299
300  Synopsis      [ Add an empty row (logically inert) to table. ]
301
302  Description   [ Given a table this function adds an empty row at the end of
303                  the table. It return the index of the row it creates]
304
305  SideEffects   [ Table has changed, and the one new row needs to be filled in ]
306
307  SeeAlso       [ optional ]
308**********************************************************************/
309int 
310Tbl_TableAddRow(
311  Tbl_Table_t *  table)
312{
313  Tbl_Row_t * row;
314  int i;
315
316  if (table != NIL(Tbl_Table_t)) {
317  if (TblTableReadRefCount(table) > 1) {
318    printf(" WARNING: You are modifying more than one table by adding this row\n");
319  }   
320      row = ALLOC(Tbl_Row_t,1);
321      row->inputs = array_alloc(Tbl_Entry_t*,0);
322      for (i=0; i < array_n(table->inputNames); i++) {
323        array_insert_last(Tbl_Entry_t*,row->inputs, NIL(Tbl_Entry_t)); 
324      }
325     
326
327      row->outputs = array_alloc(Tbl_Entry_t*,0);
328      for (i=0; i < array_n(table->outputNames); i++) {
329        array_insert_last(Tbl_Entry_t*,row->outputs, NIL(Tbl_Entry_t)); 
330      }
331                       
332      array_insert_last(Tbl_Row_t*, TblTableReadData(table),row);
333      return ( array_n(TblTableReadData(table)) -1);
334    }
335  else return -1;
336} 
337
338/**Function***********************************************************
339
340  Synopsis      [ Add an empty column with the given Var ]
341
342  Description [ Given a table this function adds an empty column at
343                the end of all columns, associates this column with a
344                Var_Variable_t (Var).  It returns the number of (input
345                or output) columns in the table. If the operation
346                fails, the program is exited.  It must also be
347                supplied with a flag to indicate whether an input or
348                output entry is being read.  It is the users
349                responsibility to ensure that the same var is not
350                already present; the table package is not concerned
351                with the semantics of the table.]
352
353  SideEffects   [  ]
354
355  SeeAlso       [ optional ]
356**********************************************************************/
357int
358Tbl_TableAddColumn(
359  Tbl_Table_t *  table /* the table */,
360  Var_Variable_t *  var /* the Var being added */,
361  int  flag /* This flag is set to 0 if it is an input and 1 if it is and output
362 */)
363{
364  int i, index;
365  Tbl_Row_t *row;
366  array_t *carray;
367 
368  assert(table !=NIL(Tbl_Table_t));
369  assert((flag==0)||(flag ==1));
370  if (TblTableReadRefCount(table) > 1) {
371    printf(" WARNING: You may be modifying more than one table by adding this column\n");
372  } 
373  index = 0;
374  for (i=0; i< array_n(TblTableReadData(table)); i++) {
375    row = array_fetch(Tbl_Row_t*,TblTableReadData(table),i);
376    if (flag==0) {
377      carray = row->inputs; 
378    }
379    else {
380      carray = row->outputs; 
381    }
382 
383    array_insert_last(Tbl_Entry_t*,carray,NIL(Tbl_Entry_t));
384 
385  }
386  if (flag==0) {
387    array_insert_last(Var_Variable_t*, table->inputNames, var);
388    index = array_n(table->inputNames);
389  }
390  else {
391      array_insert_last(Var_Variable_t*, table->outputNames, var);
392      index = array_n(table->outputNames);     
393      array_insert_last(Tbl_Entry_t*,
394                        TblTableReadDefaults(table),NIL(Tbl_Entry_t));
395    }
396
397  return index;
398}
399
400/**Function********************************************************************
401
402  Synopsis    [Deletes specified row of table]
403
404  Description [Deletes a specified row of the table. It creates a new table,
405               and copies all but the the specified row into the new table,
406               and points the original table pointer to the new table. The
407               original table is freed]
408
409  SideEffects []
410
411  SeeAlso     []
412
413******************************************************************************/
414Tbl_Table_t *
415Tbl_TableRowDelete(
416   Tbl_Table_t *originalTable,
417   int rowNumToDelete,
418   array_t *freeArray           
419   )
420{
421    Tbl_Table_t *newTable;
422    int i, rownum, newRowNum, numInputs, numOutputs;
423    Var_Variable_t *var, *newVar;
424    Tbl_Row_t *row UNUSED;
425    Tbl_Entry_t *newEntry, *origEntry, *entry, *dupEntry;
426
427    newTable = Tbl_TableAlloc();
428    Tbl_TableForEachInputVar(originalTable, i, var){
429        newVar = Var_VariableDup(var, NIL(Hrc_Node_t));
430        array_insert_last(Var_Variable_t *, freeArray, newVar);
431        (void) Tbl_TableAddColumn(newTable, newVar, 0);
432    }
433    Tbl_TableForEachOutputVar(originalTable, i, var){
434        newVar = Var_VariableDup(var, NIL(Hrc_Node_t));
435        array_insert_last(Var_Variable_t *, freeArray, newVar);
436        (void) Tbl_TableAddColumn(newTable, newVar, 1);
437    }
438    for(i = 0; i < Tbl_TableReadNumOutputs(originalTable); i++){
439        entry = Tbl_TableDefaultReadEntry(originalTable, i);
440        if(entry != NIL(Tbl_Entry_t)){
441            dupEntry = Tbl_EntryDup(entry);
442            Tbl_TableDefaultSetEntry(newTable, dupEntry, i);
443        }
444    }
445    numInputs = Tbl_TableReadNumInputs(originalTable);
446    numOutputs = Tbl_TableReadNumOutputs(originalTable);
447    TblTableForEachRow(originalTable, row, rownum){
448        if(rownum != rowNumToDelete){
449            newRowNum = Tbl_TableAddRow(newTable);
450            for(i = 0; i < numInputs; i++){
451                origEntry = Tbl_TableReadEntry(originalTable, rownum, i, 0);
452                newEntry = Tbl_EntryDup(origEntry);
453                Tbl_TableSetEntry(newTable, newEntry, newRowNum, i, 0);
454            }
455            for(i = 0; i < numOutputs; i++){
456                origEntry = Tbl_TableReadEntry(originalTable, rownum, i, 1);
457                newEntry = Tbl_EntryDup(origEntry);
458                Tbl_TableSetEntry(newTable, newEntry, newRowNum, i, 1);
459            }
460        }
461    }
462    Tbl_TableFree(originalTable);
463    return newTable;
464}
465
466/**Function***********************************************************
467
468  Synopsis      [ Find the Var of the variable (column) associated
469                 with the given index. ]
470
471  Description   [ Given an index , this functions returns the
472                  Var of the column that is represented by. If any of the
473                  input data is incorrect it exits the program.
474                  It must also be supplied with a flag to indicate whether
475                  an input or output entry is being read.]
476
477  SideEffects   [  ]
478
479  SeeAlso       [ optional ]
480**********************************************************************/
481Var_Variable_t*
482Tbl_TableReadIndexVar(
483  Tbl_Table_t *  table,
484  int index,
485  int  flag /* Set to 0 if it is an input Var and 1 if it an output Var */
486)
487{
488  array_t *carray;
489
490  assert(table !=NIL(Tbl_Table_t));
491  assert((flag==0)||(flag ==1));
492 
493  if (flag==0) {
494    carray = table->inputNames;
495  }
496  else {
497    carray = table->outputNames;
498  }
499           
500  return (array_fetch(Var_Variable_t*,carray,index));
501}
502
503/**Function********************************************************************
504
505  Synopsis    [ Returns  the entry in row i, input/output  column j,   ]
506
507  Description [ This function returns the table entry at row i and column j.
508                The item is of the Tbl_Entry_t. The flag indicates whether it
509                is an input (flag = 0)  or and output (flag =1) item.
510                If any of the input data is incorrect it exits the program]
511
512  SideEffects [  ]
513
514  SeeAlso     [ optional ]
515
516******************************************************************************/
517Tbl_Entry_t *
518Tbl_TableReadEntry(
519  Tbl_Table_t *  table ,
520  int  rowNum,
521  int  colNum,
522  int  flag )
523{
524  Tbl_Row_t *row;
525  Tbl_Entry_t *entry;
526   
527
528  assert(table !=NIL(Tbl_Table_t));
529  assert((flag==0)||(flag ==1));
530 
531  row = TblTableReadRow(table,rowNum);
532  entry = TblRowReadEntry(row,colNum,flag);
533   
534  return entry;
535}
536
537/**Function********************************************************************
538
539  Synopsis    [ Sets   the entry in row i, input/output  column j to
540  given entry   ]
541
542  Description [ This function sets the table entry at row i and column j
543                to given Tbl_Entry_t. The flag indicates whether it
544                is an input or and output item. If any of the input data is
545                incorrect it return a FALSE]
546
547  SideEffects [ Old Value is lost ]
548
549  SeeAlso     [ optional ]
550
551******************************************************************************/
552boolean
553Tbl_TableSetEntry(
554  Tbl_Table_t *  table /* The Table to be examined */,
555  Tbl_Entry_t * newEntry,
556  int  i /* Row Id */,
557  int  j /* Column Id */,
558  int  flag /* flag indicating whether it is an input or output */)
559{
560  Tbl_Row_t *row;
561  Tbl_Entry_t *entry;
562
563  assert(table !=NIL(Tbl_Table_t));
564  assert((flag==0)||(flag ==1));
565  if (TblTableReadRefCount(table) > 1) {
566    printf(" WARNING: You are modifying more than one table by  re-setting this entry\n");
567  }
568
569  entry = Tbl_TableReadEntry(table ,i,j,flag);
570 if (entry != NIL(Tbl_Entry_t)) {
571   Tbl_EntryFree(entry);
572  }
573
574  row = TblTableReadRow(table,i);
575
576  newEntry->ioType = flag;
577  newEntry->varColNum = j;
578  TblRowSetEntry(row,newEntry,j,flag);
579 
580  return TRUE;
581}
582
583/**Function********************************************************************
584
585  Synopsis    [ Sets the entry in row i,  column j, to a don't care.  ]
586
587  Description [ This function sets the table entry at row i and column j.
588                The item is of the Tbl_Entry_t. The flag indicates whether it
589                is an input or and output item. If any of the input data is
590                incorrect it exits the program]
591
592  SideEffects [ ]
593
594  SeeAlso     [ Tbl_EntrySetValue ]
595
596******************************************************************************/
597boolean
598Tbl_TableSetEntryDc(
599  Tbl_Table_t *  table,
600  int  i,
601  int  j,
602  int  flag)
603{
604  array_t *ioarray;
605  int range;
606  Tbl_Entry_t *entry;
607
608  assert(table !=NIL(Tbl_Table_t));
609  assert((flag==0)||(flag ==1));
610  if (TblTableReadRefCount(table) > 1) {
611    printf(" WARNING: You are modifying more than one table by re-setting this entry\n");
612  }
613 
614  if (flag==0) {
615    ioarray = table->inputNames;
616  }
617  else {
618    ioarray = table->outputNames;
619  }
620
621  range = Var_VariableReadNumValues(array_fetch(Var_Variable_t*,ioarray,j));
622  entry = Tbl_TableReadEntry(table,i,j,flag);
623  Tbl_EntrySetValue(entry,0,range-1);
624  return TRUE;
625}
626/**Function********************************************************************
627
628  Synopsis    [ Adds the range val1-val2 to the union in row i, column j. ]
629
630  Description [ This function when supplied with row i,col j, a table
631                and a range specified by integers val1 and val2, will
632                add range val1-val2 to the i,j th entry in the
633                table. It must also be supplied with a flag to
634                indicate whether an input or output entry is being
635                read.]
636
637  SideEffects [ ]
638
639  SeeAlso     [ ]
640
641******************************************************************************/
642void
643Tbl_TableAddEntryRange(
644  Tbl_Table_t *  table,
645  int  i,
646  int  j,
647  int  val1,
648  int  val2,
649  int  flag)
650{
651  Tbl_Entry_t *entry;
652
653  if (TblTableReadRefCount(table) > 1) {
654    printf(" WARNING: You are modifying more than one table by changing the re-setting this entry\n");
655  }
656 
657  entry = Tbl_TableReadEntry(table,i,j,flag);
658  Tbl_EntrySetValue(entry,val1,val2);
659   
660}
661 
662/**Function********************************************************************
663
664  Synopsis    [ Complements the constant or union in row i,
665                 input/output column j.  ]
666
667  Description [ This function whether supplied with row i,col j, a table will
668                complement the i,j th entry in the table. It must also be supplied with a
669                 flag to indicate whether an input or output entry is being read.]
670
671  SideEffects [ ]
672
673  SeeAlso     [ optional ]
674
675******************************************************************************/
676void
677Tbl_TableComplementEntry(
678  Tbl_Table_t *  table,
679  int  i,
680  int  j,
681  int  flag)
682{
683  Tbl_Entry_t *entry;
684   
685  entry = Tbl_TableReadEntry(table,i,j,flag);
686  Tbl_EntryComplement(entry,0,(Var_VariableReadNumValues(Tbl_EntryReadActualVar(table, entry))) -1 );
687
688}
689
690/**Function********************************************************************
691
692  Synopsis    [ Sets the io entry row i, output column j to be
693                  equal to the given Var.  ]
694
695  Description [ This function sets the entry in row i and column j to be
696  equal to the entry  specified by the given var]
697
698  SideEffects [ ]
699
700  SeeAlso     [ ]
701
702******************************************************************************/
703void
704Tbl_TableSetEquality(
705  Tbl_Table_t *  table,
706  int  i,
707  int  j,
708  int flag,
709  Var_Variable_t *  var)
710{
711  Tbl_Entry_t *entry;
712  int index,check;
713  Var_Variable_t *tblVar;
714
715  check =0;
716  entry = Tbl_TableReadEntry(table,i,j,flag);
717  Tbl_TableForEachInputVar(table, index,tblVar) {
718    if (tblVar == var) {
719      Tbl_EntrySetEqual(entry,index);
720      check =1;
721      break;
722    }
723  }
724 
725  if (check == 0) {
726    printf(" WARNING: Output Equal Another Output not supported, no change made\n ");
727  }
728}
729
730
731/**Function********************************************************************
732
733  Synopsis    [ Returns 1 if the entry in row i, input/output column j
734               is a don't care.  ]
735
736  Description [ This function returns 1 if the entry in row i and col j is
737  a DC, 0 if it isn't and -1 if it does not exist. It must also be supplied with a
738  flag to indicate whether an input or output entry is being read.]
739
740  SideEffects [ ]
741
742  SeeAlso     [ optional ]
743
744******************************************************************************/
745boolean
746Tbl_TableEntryIsDc(
747  Tbl_Table_t *  table,
748  int  i,
749  int  j,
750  int flag)
751{
752  Tbl_Range_t *range;
753  Tbl_Entry_t *entry;
754  lsGen gen;
755  Var_Variable_t *var;
756 
757  assert(table !=NIL(Tbl_Table_t));
758
759  entry = Tbl_TableReadEntry(table,i,j,flag);
760
761    if (lsLength(entry->EntryData.listOfRanges) == 1){
762      var = Tbl_EntryReadActualVar(table,entry);
763      lsForEachItem(entry->EntryData.listOfRanges, gen, range) {
764        if ((range->begin ==0)&&(range->end ==
765                                 Var_VariableReadNumValues(var)-1)){
766          lsFinish(gen);
767          return TRUE;
768        }
769      }
770    }
771  return FALSE;
772}
773
774
775/**Function********************************************************************
776
777  Synopsis    [ Returns TRUE if the output designated by outputColumnId is a constant. ]
778
779  Description [ Returns TRUE if the table has no inputs, and exactly one row,
780  and the output entry in row 0 and column outputColumnId is of type normal
781  and takes exactly one value. Note that this test is conservative, because it
782  does not take into account Boolean redundancies. It merely checks for one of
783  the following conditions 1) the table has no inputs and a constant output 2)
784  the table has only - inputs in the one row and the output is constant
785  3) the table is empty and the default value for the output is constant and
786  4) the table output has the same constant value for all inputs]
787
788  SideEffects [ ]
789
790  SeeAlso     [ Tbl_TableTestIsNonDeterministicConstant ]
791
792******************************************************************************/
793boolean
794Tbl_TableTestIsConstant(
795  Tbl_Table_t *  table,
796  int            outputColumnId)
797{
798  int colNum, rowNum;
799  boolean check;
800  Tbl_Entry_t *entry;
801  Var_Variable_t *var;
802  Tbl_Range_t *range;
803  lsGen gen;
804  int value, constant,count;
805 
806 
807  assert(table !=NIL(Tbl_Table_t));
808  assert((outputColumnId >= 0) && (outputColumnId <
809                                   Tbl_TableReadNumOutputs(table)));
810
811  if (Tbl_TableReadNumRows(table) == 1) { 
812    if (array_n(table->inputNames) == 0) {
813      entry = Tbl_TableReadEntry(table, 0, outputColumnId, 1);
814      if (entry->type == Tbl_EntryNormal_c) {
815        if (Tbl_EntryReadNumValues(entry) == 1) {
816          return TRUE;
817        }
818      }
819    }
820    else {
821      check = TRUE;
822      Tbl_TableForEachInputEntry(table,rowNum,colNum,entry) {
823        if (entry->type != Tbl_EntryNormal_c) {
824          return FALSE;
825        }
826        if (check == TRUE) {
827          check = FALSE;
828          if (lsLength(entry->EntryData.listOfRanges) == 1){
829            var = Tbl_EntryReadActualVar(table,entry);
830            lsForEachItem(entry->EntryData.listOfRanges, gen, range) {
831              if ((range->begin ==0)&&(range->end ==
832                                       Var_VariableReadNumValues(var)-1)){
833                check = TRUE;
834              }
835            }
836          }
837        }
838      }
839     
840      if (check) {
841        entry = Tbl_TableReadEntry(table,0,outputColumnId,1);
842        if (entry->type != Tbl_EntryNormal_c) {
843          return FALSE;
844        }           
845        if (Tbl_EntryReadNumValues(entry) == 1) {
846          return TRUE;
847        }
848      }
849    }
850  }
851  else if (Tbl_TableReadNumRows(table) == 0) {
852    entry = Tbl_TableDefaultReadEntry(table,outputColumnId);
853    if (entry->type != Tbl_EntryNormal_c) {
854      return FALSE;
855    }   
856    if (Tbl_EntryReadNumValues(entry) == 1) {
857      return TRUE;
858    }
859  }
860  else {
861    entry = Tbl_TableDefaultReadEntry(table,outputColumnId);   
862    if (entry == NIL(Tbl_Entry_t)){
863      constant = -1;     
864      Tbl_TableForEachOutputEntry(table,rowNum,colNum,entry) {
865        if (colNum == outputColumnId) {
866          if (entry->type != Tbl_EntryNormal_c){
867            return FALSE;
868          }         
869          count = 1;
870          Tbl_EntryForEachValue(entry,value,gen,range) {
871            lsStatus status;
872            if (count > 1) {
873              status = lsFinish(gen); 
874              assert(status == LS_OK); 
875              return FALSE;
876            }
877            else {
878              if (constant != -1) {
879                if (constant != value) {
880                  status = lsFinish(gen);
881                  assert(status == LS_OK); 
882                  return FALSE;
883                }
884              }
885              else {
886                constant = value;
887              }
888            }
889            count ++;       
890          }
891        }
892      }
893      return TRUE;
894    }
895  }
896  return FALSE;
897}
898
899
900/**Function********************************************************************
901
902  Synopsis    [ Returns TRUE if the output designated by outputColumnId is a
903  nondeterministic constant. ]
904
905  Description [ Returns TRUE if the table has no inputs, and the output
906  referred to by outputColumnId is not a constant. ]
907
908  SideEffects [ ]
909
910  SeeAlso     [ Tbl_TableTestIsConstant ]
911
912******************************************************************************/
913boolean
914Tbl_TableTestIsNonDeterministicConstant(
915  Tbl_Table_t *  table,
916  int            outputColumnId)
917{
918  assert(table !=NIL(Tbl_Table_t));
919 
920  if (array_n(table->inputNames) == 0) {
921    if (!Tbl_TableTestIsConstant(table, outputColumnId)) {
922      return TRUE;
923    }
924  }
925 
926  return FALSE;
927}
928
929
930/**Function********************************************************************
931
932  Synopsis    [ Returns TRUE if the table is deterministic. ]
933
934  Description [ This implements a sufficient but not necessary check for
935  determinism. It intersects every pair of inputs rows and compares the
936  outputs to see if they are identical.]
937
938  SideEffects [ ]
939
940  SeeAlso     [ optional ]
941
942******************************************************************************/
943int
944Tbl_TableTestIsDeterministic(
945  Tbl_Table_t *  table)
946{
947
948/* intersect every pair of input rows and
949   then compare outputs if they're not same --- */
950/* Sunil Khatri is implementing this */
951  return 0;
952}
953
954/**Function********************************************************************
955
956  Synopsis           [Test if given table has a completely specified output space]
957
958  Description        [Given a table, this function will check if the given
959  output has a completely specified output space, i.e. each output combination
960  is present in the table. If this function is called on a table with inputs,
961  it fails and exits. ]
962
963  SideEffects        [required]
964
965  SeeAlso            [optional]
966
967******************************************************************************/
968boolean
969Tbl_TableTestIsOutputSpaceComplete(
970  Tbl_Table_t *table,
971  mdd_manager *mddMgr)
972{
973  int i, offset,rowNum,colNum,oldRowNum;
974  boolean check;
975  Mvf_Function_t *mvf;
976  mdd_t *temp, *result, *function, *x;
977  Var_Variable_t *var;
978  Tbl_Entry_t *entry;
979  array_t        *faninMvfArray ;
980  array_t        *mvarValues ;
981  int             numOutputs;
982 
983  if (Tbl_TableReadNumInputs(table) != 0) {
984    return FALSE;
985  }
986
987  x = NIL(mdd_t);
988  faninMvfArray     = array_alloc(Mvf_Function_t *, 0);
989  mvarValues        = array_alloc(int, 0);
990  numOutputs         = Tbl_TableReadNumOutputs(table );
991
992 
993  /* Add mdd's for new table input variables. */
994  Tbl_TableForEachOutputVar(table, colNum, var) {
995    array_insert_last(int, mvarValues, Var_VariableReadNumValues(var));
996  }
997  offset = array_n(mdd_ret_mvar_list(mddMgr));   
998  mdd_create_variables(mddMgr,mvarValues, NIL(array_t), NIL(array_t));
999  array_free(mvarValues);
1000
1001  /*
1002   * Construct an MVF for each table input. The MVF for column i is the MVF
1003   * for MDD variable i.
1004   */
1005  for (i = 0; i < numOutputs; i++) {
1006    Mvf_Function_t *faninMvf = Mvf_FunctionCreateFromVariable(mddMgr, (i+offset));
1007    array_insert_last(Mvf_Function_t *, faninMvfArray, faninMvf);
1008  }
1009  /* Compute the MVF of the outputs */
1010
1011/* iterate over output part and compute all mvf's of rows */
1012/* add to total */
1013  function = mdd_zero(mddMgr);
1014  oldRowNum = -1;
1015  result = mdd_zero(mddMgr); 
1016  Tbl_TableForEachOutputEntry(table,rowNum,colNum,entry) {   
1017    if (rowNum != oldRowNum) {
1018      temp =function;
1019      function = mdd_or(temp,result, 1,1);
1020      mdd_free(temp);
1021      mdd_free(result);       
1022      result = mdd_one(mddMgr);
1023    }
1024    if (entry->type == Tbl_EntryNormal_c) {
1025      mvf = array_fetch(Mvf_Function_t*,faninMvfArray,colNum);
1026      x = TblEntryNormalConstructMdd(mddMgr,entry,mvf);         
1027    }
1028    else  if (entry->type == Tbl_EntryEqual_c) {
1029      printf("Failure: output equal to another output construct not supported\n");
1030      assert(FALSE);
1031    }
1032    temp = result;
1033    result = mdd_and(x,temp,1,1);
1034    mdd_free(x);
1035    mdd_free(temp);
1036    oldRowNum = rowNum;
1037  }
1038  temp =function;
1039  function = mdd_or(temp,result, 1,1);
1040  mdd_free(temp);
1041  mdd_free(result);       
1042
1043  check = mdd_is_tautology(function,1);
1044  mdd_free(function);
1045 
1046  for (i=0;i < array_n(faninMvfArray); i++){
1047    Mvf_FunctionFree(array_fetch(Mvf_Function_t *,faninMvfArray,i));
1048  }
1049  array_free(faninMvfArray);
1050  return check;
1051}
1052
1053
1054/**Function********************************************************************
1055
1056  Synopsis [Computes the inputs in the true support of a given output of a
1057  table.]
1058
1059  Description [Computes the inputs in the true support of a given output of a
1060  table.  This is done by building the MVF for the output in terms of the MVFs
1061  of the inputs, where each input is treated as a free variable. Next the
1062  function  Mvf_FunctionComputeSupport is called on the mvf.
1063  The support is returned as an array of integers corresponding
1064  to the input columns in the true support. This function must also be
1065  supplied with an mdd_manager. If
1066  the output is a constant, then this function returns a NIL(array_t), and
1067  puts the constant value in the int *value that is passed in.]
1068
1069  SideEffects [It is the user's responsibility to free the mdd_manager
1070  supplied, (use mdd_quit)]
1071
1072  SeeAlso     [Tbl_TableBuildMvfFromFanins]
1073
1074******************************************************************************/
1075array_t *
1076Tbl_TableComputeMvfAndInputDependenciesOfOutput(
1077  Tbl_Table_t *table,
1078  mdd_manager  *mddMgr, 
1079  int          outIndex,
1080  int *value)
1081{
1082  int             i, offset;
1083  Mvf_Function_t *outMvf;
1084  Var_Variable_t *var;
1085  int             colNum;
1086  array_t        *faninMvfArray     = array_alloc(Mvf_Function_t *, 0);
1087  array_t        *mvarValues        = array_alloc(int, 0);
1088  array_t        *totalSupportArray = array_alloc(int, 0);
1089  int             numInputs         = Tbl_TableReadNumInputs(table );
1090 
1091  /* Add mdd's for new table input variables. */
1092  Tbl_TableForEachInputVar(table, colNum, var) {
1093    array_insert_last(int, mvarValues, Var_VariableReadNumValues(var));
1094  }
1095  offset = array_n(mdd_ret_mvar_list(mddMgr));   
1096  mdd_create_variables(mddMgr,mvarValues, NIL(array_t), NIL(array_t));
1097  array_free(mvarValues);
1098
1099  /*
1100   * Construct an MVF for each table input. The MVF for column i is the MVF
1101   * for MDD variable i.
1102   */
1103  for (i = 0; i < numInputs; i++) {
1104    Mvf_Function_t *faninMvf = Mvf_FunctionCreateFromVariable(mddMgr, (i+offset));
1105    array_insert_last(Mvf_Function_t *, faninMvfArray, faninMvf);
1106  }
1107  /* Compute the MVF of the output indexed by outIndex. */
1108  outMvf = Tbl_TableBuildMvfFromFanins(table, outIndex, faninMvfArray, mddMgr);
1109  Mvf_FunctionArrayFree(faninMvfArray);
1110
1111
1112  totalSupportArray
1113      = Mvf_FunctionComputeSupport(outMvf,mddMgr,value);
1114 
1115  Mvf_FunctionFree(outMvf); 
1116  return totalSupportArray;
1117}
1118
1119
1120/**Function********************************************************************
1121
1122  Synopsis           [Given an output column (and maybe its mvf)
1123  return a table with the true support inputs of the given output.]
1124
1125  Description        [If a NIL(Mvf_Function_t) is supplied as input to this function
1126  , it uses Tbl_TableComputeMvfAndInputDependenciesOfOutput to compute the
1127  true support of the given output (outIndex), and then creates a
1128  new table for this output with only the true inputs.
1129  Given a non-nil Mvf of the table output, this function
1130  uses   Mvf_FunctionComputeSupport to compute the true support of
1131  the given output (index), and then creates a new table for this output
1132  with only the true inputs. It returns the new table for the output of given
1133  index. If the output is a constant, then this function returns a constant
1134  table. If a non-nil mvf is supplied, then the function must also be
1135  supplied with an int offset, such that for mddid
1136  of column j is  (j+offset) in the mvf supplied.]
1137
1138  SideEffects        [Variables may be added to the mdd manager]
1139
1140  SeeAlso            [Tbl_TableComputeMvfAndInputDependenciesOfOutput]
1141
1142******************************************************************************/
1143Tbl_Table_t*
1144Tbl_TableCreateTrueSupportTableForOutput(
1145  Tbl_Table_t *table,
1146  Mvf_Function_t *outMvf,
1147  mdd_manager *mddMgr,
1148  int offset, 
1149  int outIndex,
1150  array_t *varMap /* maps input column to mdd id */
1151  )
1152{
1153  array_t *support;
1154  Tbl_Table_t * newTable;
1155  int i, inputId, rowNum, colNum, newColNum, newEqColNum, value, eqColNum;
1156  Tbl_Entry_t *newEntry, *entry;
1157  Var_Variable_t *var;
1158  Tbl_Row_t *row UNUSED;
1159  st_table *supLookup;
1160
1161  newTable = Tbl_TableAlloc(); 
1162  /* compute dependancies and put in a hash table */
1163
1164  if (outMvf != NIL(Mvf_Function_t)) {
1165    support =
1166        Mvf_FunctionComputeSupport(outMvf,mddMgr,&value);
1167  }
1168  else {
1169    offset = array_n(mdd_ret_mvar_list(mddMgr));
1170    support =
1171        Tbl_TableComputeMvfAndInputDependenciesOfOutput(table,mddMgr,outIndex,&value);
1172  }
1173 
1174  if(support == NIL(array_t)) {
1175    /* create a constant table */
1176    var = Tbl_TableReadIndexVar(table,outIndex,1);
1177    Tbl_TableAddColumn(newTable,var,1);
1178    i  = Tbl_TableAddRow(newTable);
1179    newEntry = Tbl_EntryAlloc(Tbl_EntryNormal_c);
1180    Tbl_TableSetEntry(newTable, newEntry, 0, 0, 1);
1181    Tbl_TableAddEntryRange(newTable,0,0,value,value,1);
1182    newEntry = NIL(Tbl_Entry_t);   
1183    (void) Tbl_TableDefaultSetEntry(newTable,newEntry,0);
1184    return newTable;
1185  }
1186
1187  supLookup = st_init_table(st_numcmp, st_numhash);
1188
1189  arrayForEachItem(int, support, i, inputId) {
1190    st_insert(supLookup,(char*)((long)(inputId - offset)),(char*)((long)i));
1191  }
1192  array_free(support);
1193
1194  /* Account for multiple columns mapping to the same MDD variable.
1195   * There are two reasons why there may be fewer variables in the MVF
1196   * than there are input columns in a table:
1197   * 1. Multiple columns are tied to the same Var_Variable_t and hence
1198   *    get the same MDD variable.
1199   * 2. Variables that are in the apparent support of the table are not
1200   *    in the true support of the MVF.
1201   * The first reason is captured by varMap, the second by supLookup.
1202   * Now we merge the two and replace supLookup with the resulting table.
1203   */
1204  if (varMap != NIL(array_t)) {
1205    int mapped;
1206    int nCol = 0;
1207    Var_Ord_t *varArray = ALLOC(Var_Ord_t, array_n(varMap));
1208    arrayForEachItem(int, varMap, i, mapped) {
1209      int position;
1210      if (st_lookup_int(supLookup, (char*)(long) mapped, &position) == 1) {
1211        varArray[nCol].id = i;
1212        varArray[nCol].rank = position;
1213        nCol++;
1214      }
1215    }
1216    qsort((void *)varArray, nCol, sizeof(Var_Ord_t), varCompare);
1217    st_free_table(supLookup);
1218    supLookup = st_init_table(st_numcmp, st_numhash);
1219    for (i=0; i < nCol; i++) {
1220      st_insert(supLookup, (char*)((long)varArray[i].id), (char*)((long)i));
1221    }
1222    FREE(varArray);
1223  }
1224
1225  /* foreach input var check if in true support and then insert */
1226  Tbl_TableForEachInputVar(table,i,var){
1227    if (st_lookup_int(supLookup, (char*)(long) i, &newColNum) == 1) {
1228      Tbl_TableAddColumn(newTable,var,0);
1229    }
1230  }
1231
1232  /* insert only specified output */
1233  Tbl_TableForEachOutputVar(table,i,var){
1234    if (i == outIndex) {   
1235      Tbl_TableAddColumn(newTable,var,1);
1236    } 
1237  }
1238
1239  /* add rows to this table */
1240
1241  TblTableForEachRow(table, row, rowNum){
1242    i = Tbl_TableAddRow(newTable);
1243  }
1244
1245  for (rowNum =0; rowNum < Tbl_TableReadNumRows(table); rowNum++ ) {
1246    for (colNum =0; colNum < Tbl_TableReadNumInputs(table); colNum++) {
1247      if (st_lookup_int(supLookup, (char*)(long) colNum, &newColNum) == 1) {
1248        entry = Tbl_TableReadEntry(table,rowNum, colNum, 0);
1249        newEntry = Tbl_EntryDup(entry);             
1250        if (Tbl_EntryIsEqual(entry)) {
1251          eqColNum = Tbl_EntryReadVarIndex(entry);
1252          if (st_lookup_int(supLookup,(char*)(long)eqColNum,&newEqColNum) == 0) {
1253            fail("Entry Equal Var not in True Support\n");
1254          }
1255          else {
1256            Tbl_EntrySetEqual(newEntry,newEqColNum);
1257          }
1258        }
1259        Tbl_TableSetEntry(newTable, newEntry, rowNum, newColNum, 0);     
1260      }
1261    }
1262  }
1263
1264
1265  for (rowNum =0; rowNum < Tbl_TableReadNumRows(table); rowNum++ ) {
1266    entry = Tbl_TableReadEntry(table,rowNum, outIndex, 1);
1267    newEntry = Tbl_EntryDup(entry);
1268    if (entry->type == Tbl_EntryEqual_c) {
1269      eqColNum = Tbl_EntryReadVarIndex(entry);
1270      if (st_lookup_int(supLookup,(char*)(long)eqColNum,&newEqColNum) == 0) {
1271        fail("Entry Equal Var not in True Support\n");
1272      }
1273      else {
1274        Tbl_EntrySetEqual(newEntry,newEqColNum);
1275      }
1276    }
1277    Tbl_TableSetEntry(newTable, newEntry, rowNum, 0, 1);
1278  }
1279  st_free_table(supLookup);
1280
1281
1282  Tbl_TableForEachDefaultEntry(table,entry,i) {
1283    if (i==outIndex) {       
1284      if (entry != NIL(Tbl_Entry_t)) {
1285        if (entry->type != Tbl_EntryEqual_c) {
1286          newEntry = Tbl_EntryDup(entry);
1287        }
1288        else{
1289          eqColNum =
1290            Tbl_TableReadVarIndex(newTable,Tbl_EntryReadVar(table,entry),0);
1291          if (eqColNum != -1) {
1292            newEntry = Tbl_EntryDup(entry);
1293            Tbl_EntrySetEqual(newEntry,eqColNum);
1294          }
1295          else {
1296            newEntry = NIL(Tbl_Entry_t);
1297          }
1298        }
1299      }
1300      else {
1301        newEntry = NIL(Tbl_Entry_t);
1302      }
1303      (void) Tbl_TableDefaultSetEntry(newTable,newEntry,0);
1304    }
1305  }
1306
1307  return newTable;
1308}
1309
1310/**Function********************************************************************
1311
1312  Synopsis    [ Swap rows i and j.  ]
1313
1314  Description [ This function swaps rows i and j and return true if
1315  successful. It exits the program if data is incorrectly supplied.]
1316
1317  SideEffects [ ]
1318
1319  SeeAlso     [ optional ]
1320
1321******************************************************************************/
1322boolean
1323Tbl_TableSwapRows(
1324  Tbl_Table_t *  table,
1325  int  i,
1326  int  j)
1327{
1328  Tbl_Row_t *rowi, *rowj;
1329   
1330  assert(table !=NIL(Tbl_Table_t));
1331  if (TblTableReadRefCount(table) > 1) {
1332    printf(" WARNING: You are modifying more than one table by swapping these rows\n");
1333  }
1334 
1335  rowi = TblTableReadRow(table,i);
1336  rowj = TblTableReadRow(table,j);
1337  TblTableSetRow(table,rowi,j);
1338  TblTableSetRow(table,rowj,i);
1339
1340  return TRUE;
1341}
1342 
1343
1344/**Function********************************************************************
1345
1346  Synopsis    [ Swap input/output columns i and j.  ]
1347
1348  Description [ This functions swaps columns i and j and return true if sucessfull.
1349                It must also be supplied with a flag to indicate whether an input
1350                or output entry is being read.]]
1351
1352  SideEffects [ ]
1353
1354  SeeAlso     [ optional ]
1355
1356******************************************************************************/
1357boolean
1358Tbl_TableSwapColumns(
1359  Tbl_Table_t *  table,
1360  int  i,
1361  int  j,
1362  int  flag)
1363{
1364  int k, rowNum,colNum,flag2;
1365  Tbl_Row_t *row UNUSED;
1366  Tbl_Entry_t *coli, *colj, *entry;
1367  array_t *rowArray;
1368  Var_Variable_t *vari, *varj;
1369   
1370  assert(table !=NIL(Tbl_Table_t));
1371  assert((flag==0)||(flag ==1));
1372  if (TblTableReadRefCount(table) > 1) {
1373    printf(" WARNING: You are modifying more than one table by swapping rows\n");
1374  }
1375 
1376  TblTableForEachRow(table,row,k) {
1377    coli = Tbl_EntryDup(Tbl_TableReadEntry(table,k,i,flag));
1378    colj = Tbl_EntryDup(Tbl_TableReadEntry(table,k,j,flag));   
1379
1380    Tbl_TableSetEntry(table,coli,k,j,flag);
1381    Tbl_TableSetEntry(table,colj,k,i,flag);
1382  }
1383
1384  if (flag == 0) {
1385    rowArray = table->inputNames;
1386  }
1387  else {
1388    rowArray = table->outputNames;
1389  }
1390
1391  vari = array_fetch(Var_Variable_t*,rowArray,i);
1392  varj = array_fetch(Var_Variable_t*,rowArray,j);
1393  array_insert(Var_Variable_t*,rowArray,i,varj);
1394  array_insert(Var_Variable_t*,rowArray,j,vari);
1395
1396  /* Correct Equal entries */
1397  Tbl_TableForEachEntry(table,rowNum,colNum,flag2,entry) {
1398    if (entry->type == Tbl_EntryEqual_c) {
1399      if (Tbl_EntryReadVarIndex(entry)==i){
1400        Tbl_EntrySetEqual(entry,j);
1401      }
1402      else if (Tbl_EntryReadVarIndex(entry)==j){
1403        Tbl_EntrySetEqual(entry,i);
1404      }     
1405    }
1406  }
1407
1408 
1409  Tbl_TableForEachDefaultEntry(table,entry,colNum) {
1410    if (entry != NIL(Tbl_Entry_t)) {
1411    if (entry->type == Tbl_EntryEqual_c) {
1412      if (Tbl_EntryReadVarIndex(entry)==i){
1413        Tbl_EntrySetEqual(entry,j);
1414      }
1415      else if (Tbl_EntryReadVarIndex(entry)==j){
1416        Tbl_EntrySetEqual(entry,i);
1417      }     
1418    }
1419    }   
1420    }
1421 
1422  return TRUE;
1423}
1424     
1425/**Function******************************************************************
1426
1427   Synopsis    [ Semi-canonicalize a table]
1428
1429   Description [ Given a table (Tbl_Table_t), this function will return the
1430   semi-canonical form of  the table by ordering the rows and columns.The canonicaliztion
1431  process, assigns a linear order to the table rows an columns, based on the
1432  value of their entries. For a table with binary valued entries, this value
1433  is exactly the number of 1's in the row or column. Once this linear
1434  order is assigned, the rows and columns of the table are swapped so as to
1435  order rows and columns with higher value at the beginning of the
1436  corresponding row or column order. It is called semi-canonicalization
1437  because two tables representing the same logic function need not have the
1438  same canonical form. ]
1439
1440   SideEffects [ The original table is destroyed. The user must duplicate a table
1441   before canonicalizing, to preserve it.]
1442
1443   SeeAlso     [ ]
1444
1445****************************************************************************/
1446void
1447Tbl_TableCanonicalize(
1448    Tbl_Table_t * table)
1449{
1450  int numRows, numInputs, numOutputs, rowNum, colNum;
1451  array_t *rowValArray;
1452  Tbl_Row_t *colVal;
1453  int i, val1,val2;
1454 
1455
1456  numRows = Tbl_TableReadNumRows(table);
1457  numInputs = Tbl_TableReadNumInputs(table);
1458  numOutputs = Tbl_TableReadNumOutputs(table);
1459 
1460  rowValArray = TableCreatIntArray(numRows);
1461  colVal = ALLOC(Tbl_Row_t,1);
1462  colVal->inputs= TableCreatIntArray(numInputs);
1463  colVal->outputs= TableCreatIntArray(numOutputs);
1464
1465  for(i=0; i< numRows; i++) {
1466    for(rowNum=0; rowNum< numRows-1; rowNum++) {
1467      if (Tbl_TableRowDominatesRow(table,rowNum,rowNum+1,rowValArray)) {
1468        Tbl_TableSwapRows(table,rowNum,rowNum+1);
1469        val1 = array_fetch(int,rowValArray,rowNum);
1470        val2 =array_fetch(int,rowValArray,rowNum+1);
1471        array_insert(int,rowValArray,rowNum,val2);
1472        array_insert(int,rowValArray,rowNum+1,val1);
1473      }
1474    }
1475  }
1476
1477  for(i=0; i< numInputs; i++) { 
1478    for(colNum=0; colNum< numInputs-1; colNum++) {
1479      if (Tbl_TableColDominatesCol(table,colNum,colNum+1,0,colVal)) {
1480        Tbl_TableSwapColumns(table,colNum,colNum+1,0);
1481        val1 = array_fetch(int,TblRowReadInputs(colVal),colNum);
1482        val2 = array_fetch(int,TblRowReadInputs(colVal),colNum+1);
1483        array_insert(int,TblRowReadInputs(colVal),colNum,val2);
1484        array_insert(int,TblRowReadInputs(colVal),colNum+1,val1);
1485      }
1486    }
1487  }
1488
1489  for(i=0; i< numOutputs; i++) { 
1490    for(colNum=0; colNum< numOutputs-1; colNum++) {
1491      if (Tbl_TableColDominatesCol(table,colNum,colNum+1,1,colVal)) {
1492        Tbl_TableSwapColumns(table,colNum,colNum+1,1);
1493        val1 = array_fetch(int,TblRowReadOutputs(colVal),colNum);
1494        val2 = array_fetch(int,TblRowReadOutputs(colVal),colNum+1);
1495        array_insert(int,TblRowReadOutputs(colVal),colNum,val2);
1496        array_insert(int,TblRowReadOutputs(colVal),colNum+1,val1);       
1497      }
1498    }
1499  }
1500  TblRowFree(colVal); 
1501  array_free(rowValArray);
1502}
1503/**Function********************************************************************
1504
1505  Synopsis    [To determine if one row dominates another]
1506
1507  Description [Given a table and two row number rowa and rowb, this function
1508  returns a TRUE if rowa dominates rowb and FALSE otherwise]
1509
1510  SideEffects []
1511
1512  SeeAlso     [Tbl_TableColDominatesCol]
1513
1514******************************************************************************/
1515boolean
1516Tbl_TableRowDominatesRow(
1517  Tbl_Table_t *table,
1518  int rowa,
1519  int rowb,
1520  array_t *rowValArray) 
1521{
1522  int valuea, valueb, totala, totalb;
1523  Tbl_Entry_t *entrya, *entryb;
1524  int colNum;
1525
1526 
1527
1528  valuea = array_fetch(int,rowValArray,rowa);
1529  totala = valuea;
1530 
1531  if (valuea == -1) {
1532    totala =0;   
1533    Tbl_RowForEachInputEntry(table,rowa,entrya,colNum) {
1534      valuea = TableEntryComputeHashVal(table,entrya);
1535      totala = valuea + totala;     
1536    }
1537    Tbl_RowForEachOutputEntry(table,rowa,entrya,colNum) {
1538      valuea = TableEntryComputeHashVal(table,entrya);
1539      totala = valuea + totala;     
1540    }       
1541    array_insert(int, rowValArray,rowa,totala);
1542  }
1543
1544  valueb = array_fetch(int,rowValArray,rowb);
1545  totalb = valueb;
1546 
1547  if (valueb == -1) {
1548    totalb =0;   
1549    Tbl_RowForEachInputEntry(table,rowb,entryb,colNum) {
1550      valueb = TableEntryComputeHashVal(table,entryb);
1551      totalb = valueb + totalb;     
1552    }
1553    Tbl_RowForEachOutputEntry(table,rowb,entryb,colNum) {
1554      valueb = TableEntryComputeHashVal(table,entryb);
1555      totalb = valueb + totalb;     
1556    }       
1557    array_insert(int, rowValArray,rowb,totalb);
1558  } 
1559 
1560  if (totala < totalb ) {
1561    return FALSE;
1562  }
1563  else {
1564    return TRUE;
1565  }
1566} 
1567
1568/**Function********************************************************************
1569
1570  Synopsis    [To determine if one Col dominates another]
1571
1572  Description [Given a table, two integers for column number cola colb, and a
1573  flag set to 0 to indicate input and 1 for  output this function
1574  returns a TRUE if Cola dominates Colb and FALSE otherwise]
1575
1576  SideEffects []
1577
1578  SeeAlso     [Tbl_TableRowDominatesRow]
1579
1580******************************************************************************/
1581boolean
1582Tbl_TableColDominatesCol(
1583  Tbl_Table_t *table,
1584  int cola,
1585  int colb,
1586  int flag,
1587  Tbl_Row_t *colValArray) 
1588{
1589
1590  int valuea, valueb, totala, totalb;
1591  Tbl_Entry_t *entrya, *entryb;
1592  int colNum, rowNum;
1593 
1594  if (flag == 0) {
1595    valuea = array_fetch(int,TblRowReadInputs(colValArray),cola);
1596  }
1597  else {
1598    valuea = array_fetch(int,TblRowReadOutputs(colValArray),cola);
1599  }
1600
1601  totala = valuea;
1602  if (valuea == -1) {
1603  totala =0;
1604    if (flag ==0) {
1605      Tbl_TableForEachInputEntry(table,rowNum,colNum,entrya){
1606        if (colNum == cola) {
1607          valuea = TableEntryComputeHashVal(table,entrya);
1608          totala = valuea + totala;     
1609        }
1610      }
1611    array_insert(int, TblRowReadInputs(colValArray),cola,totala);     
1612    }
1613    else if (flag ==1) {
1614      Tbl_TableForEachOutputEntry(table,rowNum,colNum,entrya){
1615        if (colNum == cola) {   
1616          valuea = TableEntryComputeHashVal(table,entrya);
1617          totala = valuea + totala;     
1618        }
1619      }
1620    array_insert(int, TblRowReadOutputs(colValArray),cola,totala);     
1621    }
1622  }
1623
1624  if (flag ==0) {
1625    valueb = array_fetch(int,TblRowReadInputs(colValArray),colb);
1626  }
1627  else {
1628    valueb = array_fetch(int,TblRowReadOutputs(colValArray),colb);
1629  }
1630 
1631  totalb = valueb; 
1632  if (valueb == -1) {
1633  totalb =0; 
1634    if (flag ==0) {
1635      Tbl_TableForEachInputEntry(table,rowNum,colNum,entryb){
1636        if (colNum == colb) {
1637          valueb = TableEntryComputeHashVal(table,entryb);
1638          totalb = valueb + totalb;     
1639        }
1640      }
1641    array_insert(int, TblRowReadInputs(colValArray),colb,totalb);     
1642    }
1643    else if (flag ==1) {
1644      Tbl_TableForEachOutputEntry(table,rowNum,colNum,entryb){
1645        if (colNum == colb) {   
1646          valuea = TableEntryComputeHashVal(table,entryb);
1647          totalb = valueb + totalb;     
1648        }
1649      }
1650    array_insert(int, TblRowReadOutputs(colValArray),colb,totalb);     
1651    }
1652  }
1653 
1654  if (totala < totalb ) {
1655    return FALSE;
1656  }
1657  else {
1658    return TRUE;
1659  }
1660}
1661
1662/**Function******************************************************************
1663
1664   Synopsis    [ Compare two tables.]
1665
1666   Description [ Given two Tbl_Table_t's tablea and tableb, this function will
1667   compare the two tables to determine if they are the same. It returns a TRUE
1668   if they are and a FALSE if not.]
1669
1670   SideEffects [ ]
1671
1672   SeeAlso     [ ]
1673
1674****************************************************************************/
1675boolean
1676Tbl_TablesAreIdentical(
1677    Tbl_Table_t *tablea,
1678    Tbl_Table_t *tableb,
1679    int a,
1680    int b)
1681{
1682  char *signaturea;
1683  char *signatureb;
1684
1685  signaturea = TableObtainSignature(tablea, a);
1686  signatureb = TableObtainSignature(tableb, b); 
1687  if (strcmp(signaturea, signatureb) == 0) {
1688    FREE(signaturea);
1689    FREE(signatureb);   
1690    return TRUE;
1691  }
1692  FREE(signaturea);
1693  FREE(signatureb);   
1694  return FALSE;
1695}
1696
1697
1698
1699/**Function********************************************************************
1700
1701  Synopsis    [ Returns an mdd for a table row  ]
1702
1703  Description [ Given a row id i, a table, an mdd manager and an array of arrays
1704  of mdd_t*, this function returns the mdd for the corresponding row.
1705  The array of arrays of mdd_t* gives the onsets for different values of the
1706  multivalued var of each column.]
1707
1708  SideEffects [ ]
1709
1710  SeeAlso     [ ]
1711
1712******************************************************************************/
1713mdd_t *
1714Tbl_TableRowToMdd(
1715  Tbl_Table_t *  table,
1716  mdd_manager *  manager,
1717  int  i,
1718  array_t *  svArray /* array of array of mdd_t to be used */)
1719{
1720  mdd_t *result, *finalResult, *temp;
1721  int j,k;
1722  Tbl_Entry_t *entry;
1723  Mvf_Function_t *mvf1, *mvf2;
1724   
1725
1726  result = NIL(mdd_t);
1727  finalResult = mdd_one(manager);
1728   
1729  Tbl_RowForEachInputEntry(table,i,entry,j) {
1730    if ((entry->type) == Tbl_EntryNormal_c) {
1731      mvf1 = array_fetch(Mvf_Function_t*,svArray,j);
1732      result = TblEntryNormalConstructMdd(manager,entry,mvf1);
1733    }
1734    else if ((entry->type == Tbl_EntryEqual_c)) {
1735      k = Tbl_EntryReadVarIndex(entry);
1736      mvf1 = array_fetch(Mvf_Function_t*,svArray,j);
1737      mvf2 = array_fetch(Mvf_Function_t*,svArray,k);
1738      result = Mvf_FunctionsComputeEquivalentSet(mvf1,mvf2);
1739    }
1740    else if (entry->type == Tbl_EntryUnassigned_c) {
1741      return NIL(mdd_t);
1742    }
1743       
1744    temp = finalResult;
1745    finalResult = mdd_and(temp,result,1,1);
1746    mdd_free(temp);
1747    mdd_free(result);
1748  }
1749   
1750  Tbl_RowForEachOutputEntry(table,i,entry,j) {
1751    if ((entry->type) == Tbl_EntryNormal_c) {
1752      mvf1 = array_fetch(Mvf_Function_t*,svArray,j);
1753      result = TblEntryNormalConstructMdd(manager,entry,mvf1);
1754    }
1755    else if ((entry->type == Tbl_EntryEqual_c)) {
1756      k = Tbl_EntryReadVarIndex(entry);
1757      mvf1 = array_fetch(Mvf_Function_t*,svArray,j);
1758      mvf2 = array_fetch(Mvf_Function_t*,svArray,k);
1759      result = Mvf_FunctionsComputeEquivalentSet(mvf1,mvf2);
1760    }
1761    else if (entry->type == Tbl_EntryUnassigned_c) {
1762      return NIL(mdd_t);
1763    }
1764   
1765    temp = finalResult;
1766    finalResult = mdd_and(temp,result,1,1);
1767    mdd_free(temp);
1768    mdd_free(result);
1769  }
1770  return finalResult;
1771}
1772
1773
1774/**Function********************************************************************
1775
1776  Synopsis    [Compute the Mvf_Function_t for a non-deterministic constant.]
1777
1778  Description [Given a Tbl_Table_t, an integer for the  table output value
1779  index, an integer MddId, and an mdd Manager, this function builds the
1780  Mvf_Function_t associated with the output. The table cannot have
1781  any inputs; the function fails if it does. The output cannot be equal to
1782  another output, because this would make the table a relation, and that is
1783  not permissible. If this occurs, the function will fail on an assert
1784  statement.]
1785
1786  SideEffects [ Table must have no inputs.]
1787
1788  SeeAlso     []
1789
1790******************************************************************************/
1791Mvf_Function_t *
1792Tbl_TableBuildNonDetConstantMvf(
1793  Tbl_Table_t * table,
1794  int outIndex,
1795  int mddId,
1796  mdd_manager *  mddMgr)
1797{
1798
1799  lsGen gen;
1800  Tbl_Entry_t *entry;
1801  Tbl_Range_t *range;
1802  int value, rowNum, colNum;
1803  mdd_t *x;
1804  Mvf_Function_t *function;
1805 
1806  assert(Tbl_TableReadNumInputs(table) ==0);
1807
1808  value = Var_VariableReadNumValues(Tbl_TableReadIndexVar(table,outIndex,1));
1809  function = Mvf_FunctionAlloc(mddMgr,value);
1810 
1811  Tbl_TableForEachOutputEntry(table,rowNum,colNum,entry) {
1812    if (colNum == outIndex) {
1813      assert(entry->type == Tbl_EntryNormal_c);
1814      Tbl_EntryForEachValue(entry,value,gen,range) {
1815        x = mdd_eq_c(mddMgr,mddId,value);
1816        Mvf_FunctionAddMintermsToComponent(function, value,x);
1817        mdd_free(x);
1818      }
1819    }
1820  }
1821  return function;
1822}
1823
1824
1825/**Function********************************************************************
1826
1827  Synopsis    [Compute the Mvf_Function_t for a table output in terms of fanins]
1828
1829  Description [Given a Tbl_Table_t, an integer for the  table output value
1830  index, an array of fanin mdd_t* , and an mdd Manager, this function builds the
1831  Mvf_Function_t associated with the output. The output cannot be equal to
1832  another output, because this would make the table a relation, and that is
1833  not permissible.  For each row, the function will build the mdd_t for the inputs
1834  using their Mvf_Function_t's and AND them together. If the input is of the
1835  type equal, it will build the equivalent set Mdd (see See Also) and AND it in.]
1836
1837  SideEffects [ ]
1838
1839  SeeAlso     [ Mvf_FunctionComputeEquivalentSet, TblEntryNormalConstructMdd]
1840
1841******************************************************************************/
1842Mvf_Function_t *
1843Tbl_TableBuildMvfFromFanins(
1844  Tbl_Table_t * table,
1845  int outIndex,
1846  array_t * faninArray,
1847  mdd_manager *  mddMgr)
1848{
1849
1850  lsGen gen;
1851  Tbl_Entry_t *entry, *entry2,*inputEntry;
1852  Tbl_Range_t *range;
1853  int value, rowNum, colNum, rowColNum, i;
1854  mdd_t *x, *result, *temp;
1855  Mvf_Function_t *function, *mvf1, *mvf2;
1856 
1857
1858  x = NIL(mdd_t);
1859  value = Var_VariableReadNumValues(Tbl_TableReadIndexVar(table,outIndex,1));
1860  function = Mvf_FunctionAlloc(mddMgr,value);
1861 
1862  Tbl_TableForEachOutputEntry(table,rowNum,colNum,entry) {
1863    if (colNum == outIndex) {
1864      if (entry->type == Tbl_EntryNormal_c) {
1865        result = mdd_one(mddMgr);
1866        Tbl_RowForEachInputEntry(table,rowNum,inputEntry,rowColNum) {
1867          if (inputEntry->type == Tbl_EntryNormal_c) {
1868            mvf1 = array_fetch(Mvf_Function_t*,faninArray,rowColNum);
1869            x = TblEntryNormalConstructMdd(mddMgr,inputEntry,mvf1);
1870          }
1871          else if (inputEntry->type == Tbl_EntryEqual_c) {
1872            value =Tbl_EntryReadVarIndex(inputEntry);
1873            mvf1 = array_fetch(Mvf_Function_t*,faninArray,rowColNum);
1874            mvf2 = array_fetch(Mvf_Function_t*,faninArray,value);
1875            x = Mvf_FunctionsComputeEquivalentSet(mvf1,mvf2);
1876          }
1877          temp = result;
1878          result = mdd_and(x,temp,1,1);
1879          mdd_free(temp);
1880          mdd_free(x);
1881        }
1882        Tbl_EntryForEachValue(entry,value,gen,range) { 
1883          Mvf_FunctionAddMintermsToComponent(function, value,result);
1884        }
1885        mdd_free(result);
1886      }
1887      else  if (entry->type == Tbl_EntryEqual_c) {
1888        value = Tbl_EntryReadVarIndex(entry);
1889        if (value == -1) {
1890        fail("Failure: Not equal to any input var in this table\n");
1891        }
1892       
1893         
1894        /* must be equal to an input */
1895       
1896        entry2 = Tbl_TableReadEntry(table,rowNum,value,0);
1897        result = mdd_one(mddMgr);
1898        Tbl_RowForEachInputEntry(table,rowNum,inputEntry,rowColNum) {
1899          if (inputEntry->type == Tbl_EntryNormal_c) {
1900            mvf1 = array_fetch(Mvf_Function_t*,faninArray,rowColNum);
1901            x = TblEntryNormalConstructMdd(mddMgr,inputEntry,mvf1);
1902          }
1903          else if (inputEntry->type == Tbl_EntryEqual_c) {
1904            value =Tbl_EntryReadVarIndex(inputEntry);
1905            mvf1 = array_fetch(Mvf_Function_t*,faninArray,rowColNum);
1906            mvf2 = array_fetch(Mvf_Function_t*,faninArray,value);
1907            x = Mvf_FunctionsComputeEquivalentSet(mvf1,mvf2);
1908          }
1909          temp = result;
1910          result = mdd_and(x,temp,1,1);
1911          mdd_free(temp);
1912          mdd_free(x);
1913        }
1914
1915        rowColNum = Tbl_EntryReadVarIndex(entry);
1916        mvf1 = array_fetch(Mvf_Function_t*,faninArray,rowColNum);       
1917        value = Var_VariableReadNumValues(Tbl_EntryReadActualVar(table,entry2));
1918        temp = result;
1919
1920        for(i=0; i< value; i++) {
1921          x = Mvf_FunctionReadComponent(mvf1,i);
1922          result = mdd_and(temp,x,1,1);
1923          Mvf_FunctionAddMintermsToComponent(function, i,result);
1924          mdd_free(result);
1925        }
1926        mdd_free(temp);
1927      } 
1928    }
1929  }
1930
1931  /* accounting for the defaults */
1932  entry = Tbl_TableDefaultReadEntry(table,outIndex);
1933  if (entry != NIL(Tbl_Entry_t)) { 
1934    temp = Mvf_FunctionComputeDomain(function);
1935    result = mdd_not(temp);
1936    mdd_free(temp);
1937
1938    if (entry->type == Tbl_EntryNormal_c) {   
1939      Tbl_EntryForEachValue(entry,value,gen,range) {
1940        Mvf_FunctionAddMintermsToComponent(function, value,result);
1941      }
1942    }
1943    else {
1944      value = Tbl_EntryReadVarIndex(entry);
1945      if (value == -1) {
1946        fail("Failure: Not equal to any input var in this table\n");
1947      }
1948      mvf1 = array_fetch(Mvf_Function_t*,faninArray,value);
1949     
1950      Mvf_FunctionForEachComponent(mvf1,i,x) {
1951        temp = mdd_and(x,result,1,1);
1952        Mvf_FunctionAddMintermsToComponent(function, i ,temp);
1953        mdd_free(temp);
1954      }
1955    }
1956   
1957    mdd_free(result);   
1958  }
1959       
1960  return function; 
1961}
1962
1963 
1964       
1965/**Function********************************************************************
1966
1967  Synopsis    [ Return the constant value associated with an output]
1968
1969  Description [ Given a table that has no inputs and an output column index,
1970  this function returns the constant value associated with the output. It returns
1971  a -1 if the value is not a constant. Note that this test is conservative, because it
1972  does not take into account Boolean redundancies. It merely checks for one of
1973  the following conditions 1) the table has no inputs and a constant output 2)
1974  the table has only - inputs in the one row and the output is constant
1975  3) the table is empty and the default value for the output is constant and
1976  4) the table output has the same constant value for all inputs]
1977
1978  SideEffects []
1979
1980  SeeAlso     []
1981
1982******************************************************************************/
1983int
1984Tbl_TableReadConstValue(
1985  Tbl_Table_t * table,
1986  int outputColumnId)
1987{
1988  int colNum, rowNum;
1989  boolean check;
1990  Tbl_Entry_t *entry;
1991  Var_Variable_t *var;
1992  Tbl_Range_t *range;
1993  lsGen gen;
1994  int value, constant,count;
1995 
1996
1997  constant = -1;
1998  assert(table !=NIL(Tbl_Table_t));
1999  assert((outputColumnId >= 0) && (outputColumnId <
2000                                   Tbl_TableReadNumOutputs(table)));
2001
2002  if (Tbl_TableReadNumRows(table) == 1) { 
2003    if (array_n(table->inputNames) == 0) {
2004      entry = Tbl_TableReadEntry(table, 0, outputColumnId, 1);
2005      if (entry->type == Tbl_EntryNormal_c) {
2006        if (Tbl_EntryReadNumValues(entry) == 1) {
2007          Tbl_EntryForEachValue(entry,value,gen,range) {
2008            constant = value;
2009          }
2010          return constant;
2011        }
2012      }
2013    }
2014    else {
2015      check = TRUE;
2016      Tbl_TableForEachInputEntry(table,rowNum,colNum,entry) {
2017        if (entry->type != Tbl_EntryNormal_c) {
2018          return -1;
2019        }
2020        if (check == TRUE) {
2021          check = -1;
2022          if (lsLength(entry->EntryData.listOfRanges) == 1){
2023            var = Tbl_EntryReadActualVar(table,entry);
2024            lsForEachItem(entry->EntryData.listOfRanges, gen, range) {
2025              if ((range->begin ==0)&&(range->end ==
2026                                       Var_VariableReadNumValues(var)-1)){
2027                check = TRUE;
2028              }
2029            }
2030          }
2031        }
2032      }
2033     
2034      if (check) {
2035        entry = Tbl_TableReadEntry(table,0,outputColumnId,1);
2036        if (entry->type != Tbl_EntryNormal_c) {
2037          return -1;
2038        }           
2039        if (Tbl_EntryReadNumValues(entry) == 1) {
2040          Tbl_EntryForEachValue(entry,value,gen,range) {
2041            constant = value;
2042          }
2043          return constant;
2044        }
2045      }
2046    }
2047  }
2048  else if (Tbl_TableReadNumRows(table) == 0) {
2049    entry = Tbl_TableDefaultReadEntry(table,outputColumnId);
2050    if (entry->type != Tbl_EntryNormal_c) {
2051      return -1;
2052    }   
2053    if (Tbl_EntryReadNumValues(entry) == 1) {
2054      Tbl_EntryForEachValue(entry,value,gen,range) {
2055        constant = value;
2056      }
2057      return constant;     
2058    }
2059  }
2060  else {
2061    entry = Tbl_TableDefaultReadEntry(table,outputColumnId);   
2062    if (entry == NIL(Tbl_Entry_t)){
2063      constant = -1;
2064      Tbl_TableForEachOutputEntry(table,rowNum,colNum,entry) {
2065        if (colNum == outputColumnId) {
2066          count = 1;
2067        if (entry->type != Tbl_EntryNormal_c){
2068          return -1;
2069        }         
2070          Tbl_EntryForEachValue(entry,value,gen,range) {
2071            lsStatus status;
2072            if (count > 1) {
2073              status = lsFinish(gen); 
2074              assert(status == LS_OK);
2075              return -1;
2076            }
2077            else {
2078              if (constant != -1) {
2079                if (constant != value) {
2080                  status = lsFinish(gen); 
2081                  assert(status == LS_OK); 
2082                  return -1;
2083                }
2084              }
2085              else {
2086                constant = value;
2087              }
2088            }
2089            count ++;       
2090          }
2091        }
2092      }
2093      return constant;
2094    }
2095  }
2096 
2097  return -1;
2098}
2099
2100/**Function********************************************************************
2101
2102  Synopsis    [ Returns a table for an mdd ]
2103
2104  Description [ ]
2105
2106  SideEffects [ ]
2107
2108  SeeAlso     [ ]
2109
2110******************************************************************************/
2111Tbl_Table_t *
2112Tbl_MddToTable(
2113  mdd_t *  mdd,
2114  mdd_manager *  manager,
2115  st_table *  idtoVar,
2116  array_t * inputids)
2117{
2118/**Fix*******Gitanjali***********************************************************/
2119  /* use foreach cube */
2120  printf("Not implemented as yet, contact gms@ic\n");
2121  return NIL(Tbl_Table_t);
2122}
2123
2124
2125/**Function********************************************************************
2126
2127  Synopsis    [ Substitute the oldVar with the newVar.
2128                Return TRUE if successful.  ]
2129
2130  Description [ Given a table and Var_variable_t's oldVar and newVar, it replaces
2131  the oldVar with the newVar in the table. It returns true if sucessful and false
2132  otherwise.]
2133
2134  SideEffects [ The oldVar is not freed, it is the user's responsibility ]
2135
2136  SeeAlso     [ ]
2137
2138******************************************************************************/
2139boolean
2140Tbl_TableSubstituteVar(
2141  Tbl_Table_t *  table,
2142  Var_Variable_t *  oldVar,
2143  Var_Variable_t *  newVar)
2144{
2145  int i,k;
2146  int flag;
2147  Var_Variable_t *var;
2148
2149
2150  k = -1;
2151  flag =0;
2152  var = NIL(Var_Variable_t);
2153
2154  if (!Var_VariablesTestHaveSameDomain(oldVar,newVar)) return FALSE;
2155
2156  if (table != NIL(Tbl_Table_t)) {
2157    Tbl_TableForEachInputVar(table,i,var) {
2158      if (var == oldVar) {
2159        k = i;
2160        i = Tbl_TableReadNumInputs(table);
2161        flag = 0;
2162      }
2163    }
2164    if (k == -1) {
2165      Tbl_TableForEachOutputVar(table,i,var) {
2166        if (var == oldVar) {
2167          k = i;
2168          i = Tbl_TableReadNumOutputs(table);
2169          flag = 1;
2170        }
2171      }
2172    }
2173    if (k != -1) {
2174      Tbl_TableSetVar(table,k,newVar,flag);
2175      /* traverse all the entries of the table and change all the references
2176      to the old variable in the equal-to construct to the new variable */
2177      /* The above no longer has to be done as the entry refers to an
2178         index rather than the var */
2179      return TRUE;
2180    }
2181    else {
2182      return FALSE;
2183    }
2184  }
2185  return FALSE;
2186}
2187
2188/**Function********************************************************************
2189
2190  Synopsis    [Set the var in given column to given var]
2191
2192  Description [Given a table, an index and a new var for the index, this
2193  function sets the var in the table ]
2194
2195  SideEffects [The previously set var is lost]
2196
2197  SeeAlso     []
2198
2199******************************************************************************/
2200void
2201Tbl_TableSetVar(
2202  Tbl_Table_t * table,
2203  int i,
2204  Var_Variable_t * sv,
2205  int flag)
2206{
2207  array_t *svarray;
2208 
2209  if (flag==0){
2210    svarray = Tbl_TableReadInputVars(table);
2211  }
2212  else {
2213    svarray = Tbl_TableReadOutputVars(table);
2214  }
2215 
2216  array_insert(Var_Variable_t*,svarray,i,sv);
2217}
2218
2219/**Function********************************************************************
2220
2221  Synopsis    [ Split a multi-output table into a set of single output tables.  ]
2222
2223  Description [ Given a deterministic multi-output table this function splits
2224  it into an array of single-output tables.]
2225
2226  SideEffects [ Determinism is required for this to be sucessful.
2227                The user is responsible for freeing the original table]
2228
2229  SeeAlso     [ ]
2230
2231******************************************************************************/
2232array_t *
2233Tbl_TableSplit(
2234  Tbl_Table_t *  table)
2235{
2236  int i,j, rowNum, colNum;
2237  array_t *resArray;
2238  Tbl_Table_t *newtable;
2239  Var_Variable_t *output, *input;
2240  Tbl_Entry_t *entry, *newEntry;
2241   
2242
2243  resArray = array_alloc(Tbl_Table_t*,0);
2244   
2245  Tbl_TableForEachOutputVar(table,i,output) {
2246    newtable = Tbl_TableAlloc();
2247    Tbl_TableAddColumn(newtable,output,1);
2248    Tbl_TableForEachInputVar(table,colNum,input) {
2249      Tbl_TableAddColumn(newtable,input,0);
2250    }
2251    for (rowNum =0; rowNum < Tbl_TableReadNumRows(table); rowNum++) {
2252      (void) Tbl_TableAddRow(newtable);
2253    }
2254   
2255    Tbl_TableForEachEntry(table,rowNum,colNum,j,entry) {
2256      if (j==0) {
2257        newEntry = Tbl_EntryDup(entry);
2258        Tbl_TableSetEntry(newtable,newEntry,rowNum,colNum,0);
2259      }
2260      else {
2261        if (colNum ==i) {
2262          newEntry = Tbl_EntryDup(entry);
2263          Tbl_TableSetEntry(newtable,newEntry,rowNum,0,1);
2264        }
2265      }
2266    }
2267    entry = Tbl_TableDefaultReadEntry(table,i);
2268    if (entry != NIL(Tbl_Entry_t)) {
2269      newEntry = Tbl_EntryDup(entry);
2270      Tbl_TableDefaultSetEntry(newtable,newEntry,0);
2271    }
2272   
2273    array_insert_last(Tbl_Table_t*,resArray,newtable);
2274  }
2275  return resArray;
2276}
2277 
2278
2279/**Function********************************************************************
2280
2281  Synopsis    [ Return the number of inputs.  ]
2282
2283  Description [ ]
2284
2285  SideEffects [ ]
2286
2287  SeeAlso     [ ]
2288
2289******************************************************************************/
2290int 
2291Tbl_TableReadNumInputs(
2292    Tbl_Table_t * table)
2293{
2294  return(array_n(table->inputNames));
2295   
2296}
2297 
2298
2299/**Function********************************************************************
2300
2301  Synopsis    [ Return the number of outputs.  ]
2302
2303  Description [ ]
2304
2305  SideEffects [ ]
2306
2307  SeeAlso     [ ]
2308
2309******************************************************************************/
2310int
2311Tbl_TableReadNumOutputs(
2312  Tbl_Table_t *  table)
2313{
2314  return(array_n(table->outputNames));
2315}
2316 
2317/**Function********************************************************************
2318
2319  Synopsis    [return the number of input/output Vars]
2320
2321  Description [Given a table and a flag set to 0 for input and 1 for output
2322  this function returns the number of inputs or outputs.]
2323
2324  SideEffects []
2325
2326  SeeAlso     [Tbl_TableReadNumInputs Tbl_TableReadNumOutputs]
2327
2328******************************************************************************/
2329int
2330Tbl_TableReadNumVars(
2331  Tbl_Table_t *table,
2332  int flag)
2333{
2334  if (flag==0) {
2335    return Tbl_TableReadNumInputs(table);
2336  }
2337  else {
2338    return Tbl_TableReadNumOutputs(table);
2339  }
2340}
2341
2342/**Function********************************************************************
2343
2344  Synopsis    [ Return the number of rows.  ]
2345
2346  Description [ ]
2347
2348  SideEffects [ ]
2349
2350  SeeAlso     [ ]
2351
2352******************************************************************************/
2353int
2354Tbl_TableReadNumRows(
2355  Tbl_Table_t *  table)
2356{
2357  return(array_n(TblTableReadData(table)));
2358}
2359 
2360/**Function***********************************************************
2361
2362  Synopsis      [ Find the index of the variable (column) associated
2363                 with the given Var. ]
2364
2365  Description   [ Given a Var_Variable_t, this functions returns the
2366                  index of the column that is represented by. The function
2367                  returns -1 if the var does not belong to the table.
2368                  It must also be supplied with a flag to indicate whether
2369                  an input or output entry is being read.]
2370
2371  SideEffects   [  ]
2372
2373  SeeAlso       [ optional ]
2374**********************************************************************/
2375int
2376Tbl_TableReadVarIndex(
2377  Tbl_Table_t *  table,
2378  Var_Variable_t *  var,
2379  int  flag /* Set to 0 if it is an input Var and 1 if it an output Var */
2380)
2381{
2382  int i;
2383  array_t *carray;
2384  Var_Variable_t *aVar;
2385
2386  assert(table !=NIL(Tbl_Table_t));
2387  assert((flag==0)||(flag ==1)); 
2388 
2389  if (flag==0) {
2390    carray = table->inputNames; 
2391  }
2392  else {
2393    carray = table->outputNames; 
2394  }
2395           
2396  for (i=0; i< array_n(carray);i++) {
2397    aVar = array_fetch(Var_Variable_t*,carray,i);
2398    if (var==aVar) {
2399      return i;
2400    }
2401  }
2402  return -1;
2403}
2404
2405/**Function********************************************************************
2406
2407  Synopsis    [Print table statistics]
2408
2409  Description [ Prints the following information to the file: number of input
2410  columns, number of output columns, number of rows, name and cardinality of
2411  domain, of each input column, name and cardinality of domain, of each
2412  output, percentage of mxn entries with non-DC information (gives measure of
2413  sparsity)]
2414
2415  SideEffects []
2416
2417  SeeAlso     []
2418
2419******************************************************************************/
2420void
2421Tbl_TablePrintStats(
2422  Tbl_Table_t *table,
2423    FILE *fp)
2424{
2425  int rowNum, colNum,i,dc, total;
2426  Tbl_Entry_t *entry;
2427  Var_Variable_t *var;
2428  lsGen gen;
2429  Tbl_Range_t *range;
2430
2431  fprintf(fp,"Table Stats\n");   
2432  fprintf(fp,"Number of  Inputs           = %d\n",Tbl_TableReadNumInputs(table));
2433 
2434  fprintf(fp,"Inputs                      :"); 
2435  Tbl_TableForEachInputVar(table,colNum,var){
2436    fprintf(fp,"%s ",Var_VariableReadName(var));
2437  }
2438  fprintf(fp,"\n");
2439  fprintf(fp,"Values                      :");
2440 
2441  Tbl_TableForEachInputVar(table,colNum,var){
2442    fprintf(fp,"%d ",Var_VariableReadNumValues(var));
2443  }
2444  fprintf(fp,"\n"); 
2445 
2446  fprintf(fp,"Number of  Outputs          = %d\n",Tbl_TableReadNumOutputs(table));
2447 
2448  fprintf(fp,"Outputs                     :");
2449 
2450  Tbl_TableForEachOutputVar(table,colNum,var){
2451    fprintf(fp,"%s ",Var_VariableReadName(var));
2452  }
2453  fprintf(fp,"\n");
2454  fprintf(fp,"Values                      :");
2455  Tbl_TableForEachOutputVar(table,colNum,var){
2456    fprintf(fp,"%d ",Var_VariableReadNumValues(var));
2457  }
2458  fprintf(fp,"\n");   
2459  fprintf(fp,"Number of  Rows             = %d\n",Tbl_TableReadNumRows(table));
2460
2461  dc = 0;
2462  total =0;
2463  Tbl_TableForEachEntry(table,rowNum,colNum,i,entry) {
2464    total++;
2465    if(entry->type == Tbl_EntryNormal_c) {   
2466      if (lsLength(entry->EntryData.listOfRanges) == 1){
2467        var = Tbl_EntryReadActualVar(table,entry);
2468        lsForEachItem(entry->EntryData.listOfRanges, gen, range) {
2469          if ((range->begin ==0)&&(range->end == Var_VariableReadNumValues(var)-1)){
2470            dc++;
2471          }
2472        }
2473      }
2474    }
2475  }
2476  if (total > 0) {
2477    i = 100 *dc/total;
2478  }
2479  else {
2480    i = 0;
2481  }
2482 
2483  fprintf(fp,"# Don't Care entries        = %d\n",dc);
2484  fprintf(fp,"Percent Don't Care entries  = %d\n",i);   
2485}
2486
2487
2488/**Function********************************************************************
2489
2490  Synopsis    [Print table to file specified by fp in blif mv format. Appends
2491               the chars "_bufin" to the end of the output variables.]
2492
2493  Description [Given a table and file ptr, this function will print this table
2494  in blif_mv form to a file specified by the ptr. If stdout is specified this
2495  table will print it to stdout.It must also be supplied with a
2496  flag to indicate the nature of the table. If this flag is a 0, it indicates
2497  that the table is of the type .table if it is a 1, then it indicates that
2498  the table is of the type .reset.]
2499
2500  SideEffects []
2501
2502  SeeAlso     [TblEntryPrint TblEntryWriteBlif Tbl_TablePrintl]
2503
2504******************************************************************************/
2505void
2506Tbl_TableWriteBlifMvToFileSpecial(
2507    Tbl_Table_t *table,
2508    int flag,
2509    FILE *fp)
2510{
2511  int rowNum, colNum,i;
2512  Tbl_Entry_t *entry;
2513  Var_Variable_t *var;
2514   
2515
2516  if (flag ==0) {
2517    fprintf(fp,".table "); 
2518  }
2519  else {
2520    fprintf(fp,".reset ");
2521  }
2522   
2523  Tbl_TableForEachInputVar(table,colNum,var){
2524    fprintf(fp,"%s ",Var_VariableReadName(var));
2525  }
2526  fprintf(fp,"->"); 
2527  Tbl_TableForEachOutputVar(table,colNum,var){
2528    fprintf(fp,"%s_bufin ",Var_VariableReadName(var));
2529  }
2530  fprintf(fp,"\n");
2531
2532  if ((array_fetch(Tbl_Entry_t*, TblTableReadDefaults(table),0)) != NIL(Tbl_Entry_t)) {
2533    fprintf(fp,".default ");
2534    Tbl_TableForEachDefaultEntry(table,entry,colNum) {
2535      TblEntryWriteBlifMv(table,entry,fp);
2536      fprintf(fp," ");
2537    }
2538    fprintf(fp,"\n");
2539  }
2540
2541   Tbl_TableForEachEntry(table, rowNum,colNum,i,entry) { 
2542    TblEntryWriteBlifMv(table,entry,fp);
2543    fprintf(fp," ");   
2544    if ((colNum == (Tbl_TableReadNumOutputs(table) -1))&&(i==1)) {
2545      fprintf(fp,"\n");
2546    }
2547  }
2548}
2549
2550/**Function********************************************************************
2551
2552  Synopsis    [Print table to file specified by fp in blif-mv format]
2553
2554  Description [Given a table and file ptr, this function will print this table
2555  in blif_mv form to a file specified by the ptr. If stdout is specified this
2556  table will print it to stdout. It must also be supplied with a
2557  flag to indicate the nature of the table. If this flag is a 0, it indicates
2558  that the table is of the type .table.  If it is a 1, then it indicates that
2559  the table is of the type .reset.  Finally, if flag is 2, the table should
2560  be printed without header.]
2561
2562  SideEffects []
2563
2564  SeeAlso     [TblEntryPrint TblEntryWriteBlif Tbl_TablePrintl]
2565
2566******************************************************************************/
2567void
2568Tbl_TableWriteBlifMvToFile(
2569    Tbl_Table_t *table,
2570    int flag,
2571    FILE *fp)
2572{
2573  int rowNum, colNum,i;
2574  Tbl_Entry_t *entry;
2575  Var_Variable_t *var;
2576   
2577
2578  if (flag == 0) {
2579    fprintf(fp,".table "); 
2580  }
2581  else if (flag == 1) {
2582    fprintf(fp,".reset ");
2583  }
2584
2585  if (flag < 2) {
2586    Tbl_TableForEachInputVar(table,colNum,var){
2587      fprintf(fp,"%s ",Var_VariableReadName(var));
2588    }
2589    fprintf(fp,"->"); 
2590    Tbl_TableForEachOutputVar(table,colNum,var){
2591      fprintf(fp," %s",Var_VariableReadName(var));
2592    }
2593    fprintf(fp,"\n");
2594  }
2595
2596  if ((array_fetch(Tbl_Entry_t*, TblTableReadDefaults(table),0)) != NIL(Tbl_Entry_t)) {
2597    fprintf(fp,".default");
2598    Tbl_TableForEachDefaultEntry(table,entry,colNum) {
2599      fprintf(fp," ");
2600      TblEntryWriteBlifMv(table,entry,fp);
2601    }
2602    fprintf(fp,"\n");
2603  }
2604
2605   Tbl_TableForEachEntry(table,rowNum,colNum,i,entry) { 
2606    TblEntryWriteBlifMv(table,entry,fp);
2607    if ((colNum == (Tbl_TableReadNumOutputs(table) -1))&&(i==1)) {
2608      fprintf(fp,"\n");
2609    } else {
2610      fprintf(fp," ");   
2611    }
2612  }
2613}
2614
2615/**Function********************************************************************
2616
2617  Synopsis    [Print table to file specified by fp in smv format]
2618
2619  Description [Given a table and file ptr, this function will print
2620  this table in smv form to a file specified by the ptr. If stdout is
2621  specified this table will print it to stdout.It must also be
2622  supplied with a flag to indicate the nature of the table. If this
2623  flag is a 0, it indicates that the table is of the type .table if it
2624  is a 1, then it indicates that the table is of the type .reset.]
2625
2626  SideEffects []
2627
2628  SeeAlso     [TblEntryPrint TblEntryWriteBlif Tbl_TablePrintl]
2629
2630******************************************************************************/
2631void
2632Tbl_TableWriteSmvToFile(
2633    Tbl_Table_t *table,
2634    int flag,
2635    FILE *fp)
2636{
2637  int rowNum, colNum,i;
2638  Tbl_Entry_t *entry;
2639  Var_Variable_t *var;
2640
2641  if (flag ==0) { 
2642    fprintf(fp,"\n-- Table for ");
2643  }
2644  else {
2645    fprintf(fp,"\n-- Reset table for ");
2646  }
2647  Tbl_TableForEachInputVar(table,colNum,var){
2648    fprintf(fp,"%s ",Var_VariableReadName(var));
2649  }
2650  fprintf(fp,"->"); 
2651  Tbl_TableForEachOutputVar(table,colNum,var){
2652    fprintf(fp,"%s ",Var_VariableReadName(var));
2653  }
2654  fprintf(fp,"\n");
2655
2656  if (flag ==0) { 
2657
2658    fprintf(fp, "INVAR\n( ");
2659
2660    Tbl_TableForEachEntry(table, rowNum,colNum,i,entry) { 
2661      TblEntryWriteSmv(table,entry,0,fp);
2662      if ((colNum == (Tbl_TableReadNumOutputs(table) -1))&&(i==1)) {
2663        if(rowNum < Tbl_TableReadNumRows(table) -1) {
2664            fprintf(fp,") |\n( ");
2665        }
2666      } else {
2667        fprintf(fp,"& ");   
2668      }
2669    }
2670   
2671    if ((array_fetch(Tbl_Entry_t*, TblTableReadDefaults(table),0)) != NIL(Tbl_Entry_t)) {
2672      fprintf(fp,") |\n( ");
2673   
2674      if (Tbl_TableReadNumInputs(table) > 0) {
2675        fprintf(fp,"!( (");
2676      }
2677      Tbl_TableForEachInputEntry(table, rowNum,colNum,entry) { 
2678        TblEntryWriteSmv(table,entry,0,fp);
2679        if (colNum == (Tbl_TableReadNumInputs(table) -1)) {
2680          if(rowNum < Tbl_TableReadNumRows(table) -1) {
2681            fprintf(fp,") | ( ");
2682          }
2683        } else {
2684          fprintf(fp,"& ");   
2685        }
2686      }
2687      if (Tbl_TableReadNumInputs(table) > 0) {
2688        fprintf(fp,") ) & ");
2689      }
2690     
2691      Tbl_TableForEachDefaultEntry(table,entry,colNum) {
2692        TblEntryWriteSmv(table,entry,0,fp);
2693        if (colNum < (Tbl_TableReadNumOutputs(table) -1)) {
2694          fprintf(fp,"& ");   
2695        }
2696      }
2697    }
2698    fprintf(fp,")\n");
2699
2700  } else {
2701
2702    fprintf(fp,"case\n");
2703
2704    Tbl_TableForEachEntry(table, rowNum,colNum,i,entry) { 
2705      TblEntryWriteSmv(table,entry,i,fp);
2706      if ((colNum == (Tbl_TableReadNumInputs(table) -1))&&(i==0)) {
2707        fprintf(fp,": ");
2708      } else if ((colNum == (Tbl_TableReadNumOutputs(table) -1))&&(i==1)) {
2709        fprintf(fp,";\n");   
2710      } else {
2711        fprintf(fp,"& ");   
2712      }
2713    }
2714   
2715    if ((array_fetch(Tbl_Entry_t*, TblTableReadDefaults(table),0)) != NIL(Tbl_Entry_t)) {
2716      fprintf(fp,"1 : ");
2717     
2718      Tbl_TableForEachDefaultEntry(table,entry,colNum) {
2719        TblEntryWriteSmv(table,entry,1,fp);
2720      }
2721      fprintf(fp,";\n");
2722    }
2723
2724    fprintf(fp,"esac;\n");
2725  }
2726   
2727}
2728
2729 
2730
2731/**Function********************************************************************
2732
2733  Synopsis    [Writes out a table to a named blif file]
2734
2735  Description [Writes out blif files corresponding to the table given.]
2736
2737  SideEffects []
2738
2739  SeeAlso     []
2740
2741******************************************************************************/
2742void
2743Tbl_TableWriteBlifToFile(
2744  Tbl_Table_t *table,
2745  FILE *fp   
2746    )
2747{                     
2748  int numInputs, numOutputs, numRows, colnum, i, j;
2749  Var_Variable_t *var;
2750  Tbl_Entry_t *entry;
2751  lsGen gen;
2752  Tbl_Range_t *range;
2753  int value, flag;
2754
2755
2756  fprintf(fp,".names ");     
2757  for (colnum=0; colnum < Tbl_TableReadNumInputs(table); colnum++) {
2758    var = Tbl_TableReadIndexVar(table, colnum, 0);
2759    fprintf(fp,"%s ",Var_VariableReadName(var));
2760  }
2761  for (colnum=0; colnum < Tbl_TableReadNumOutputs(table); colnum++) {
2762    var = Tbl_TableReadIndexVar(table, colnum, 1);
2763    fprintf(fp,"%s ",Var_VariableReadName(var));
2764  }
2765  fprintf(fp,"\n");
2766
2767
2768  numInputs = Tbl_TableReadNumInputs(table);
2769  numOutputs = Tbl_TableReadNumOutputs(table);
2770  numRows = Tbl_TableReadNumRows(table);
2771
2772
2773  for (i=0; i < numRows; i++) {
2774    flag =1;
2775 
2776    if (numOutputs == 1) {
2777      entry =  Tbl_TableReadEntry(table, i, 0, 1);
2778      if (Tbl_EntryReadNumValues(entry) ==1 ){
2779        Tbl_EntryForEachValue(entry,value,gen,range){
2780          if (value ==0) {
2781            flag = 0;
2782          }
2783        }
2784      }
2785    }
2786    if (flag ==1) {     
2787      for(j = 0; j < numInputs; j++){
2788        entry = Tbl_TableReadEntry(table, i, j, 0);
2789        TblEntryWriteBlif(table,entry,fp);
2790      }
2791      fprintf(fp," ");
2792   
2793      for(j = 0; j < numOutputs; j++){
2794        entry = Tbl_TableReadEntry(table, i, j, 1);
2795        TblEntryWriteBlif(table,entry,fp);
2796      }
2797      fprintf(fp,"\n");     
2798    }
2799  }
2800}
2801
2802
2803/**Function********************************************************************
2804
2805  Synopsis    [Return the defaults array associated with a table.]
2806
2807  Description []
2808
2809  SideEffects [This array is NOT to be modified. The user is encouraged not
2810  to use this function. It is exported so as to make the macros for iteration over
2811  items in the table possible. The user should use these macros for accessing data.
2812  The macros that can be used are mentioned in the SeeAlso list]
2813
2814  SeeAlso     [Tbl_TableForEachEntry Tbl_TableForEachInputEntry Tbl_TableForEachOutputEntry
2815  Tbl_TableForEachInputVar Tbl_TableForEachOutputVar Tbl_TableForEachDefault]
2816
2817******************************************************************************/
2818array_t*
2819Tbl_TableReadDefaults(
2820    Tbl_Table_t * table)
2821{
2822  return (table->data->defaults);
2823}
2824
2825/**Function********************************************************************
2826
2827  Synopsis    [Return the input Var_Variable_t  array associated with a table.]
2828
2829  Description []
2830
2831  SideEffects [This array is NOT to be modified. The user is encouraged not
2832  to use this function. It is exported so as to make the macros for iteration over
2833  items in the table possible. The user should use these macros for accessing data.
2834  The macros that can be used are mentioned in the SeeAlso list]
2835
2836  SeeAlso     [Tbl_TableForEachEntry Tbl_TableForEachInputEntry Tbl_TableForEachOutputEntry
2837  Tbl_TableForEachInputVar Tbl_TableForEachOutputVar Tbl_TableForEachDefault]
2838
2839******************************************************************************/
2840array_t*
2841Tbl_TableReadInputVars(
2842    Tbl_Table_t * table)
2843{
2844  return (table->inputNames);
2845}
2846
2847/**Function********************************************************************
2848
2849  Synopsis    [Return the output Var_Variable_t  array associated with a table.]
2850
2851  Description []
2852
2853  SideEffects [This array is NOT to be modified. The user is encouraged not
2854  to use this function. It is exported so as to make the macros for iteration over
2855  items in the table possible. The user should use these macros for accessing data.
2856  The macros that can be used are mentioned in the SeeAlso list]
2857
2858  SeeAlso     [Tbl_TableForEachEntry Tbl_TableForEachInputEntry Tbl_TableForEachOutputEntry
2859  Tbl_TableForEachInputVar Tbl_TableForEachOutputVar Tbl_TableForEachDefault]
2860
2861******************************************************************************/
2862array_t*
2863Tbl_TableReadOutputVars(
2864    Tbl_Table_t * table)
2865{
2866  return (table->outputNames);
2867}
2868
2869
2870/**Function********************************************************************
2871
2872  Synopsis    [Checks to see if the input parts of two rows intersect]
2873
2874  Description [Given two rows, this function checks to see if their input parts
2875  intersect, returns a 0 if they don't, and 1 if they do]
2876
2877  SideEffects []
2878
2879  SeeAlso     [Tbl_TableIsDet]
2880
2881******************************************************************************/
2882boolean
2883Tbl_RowInputIntersect(
2884  Tbl_Table_t * table,
2885  int a,
2886  int b)
2887{
2888  int colNum, check;
2889  Tbl_Entry_t *entrya, *entryb;
2890  Tbl_Row_t *rowb;
2891 
2892  check = FALSE;
2893  rowb = TblTableReadRow(table,b);
2894 
2895  Tbl_RowForEachInputEntry(table,a, entrya, colNum){
2896    entryb = TblRowReadEntry(rowb,colNum,0);
2897    check = Tbl_EntryTestIntersectEntry(entrya,entryb);
2898
2899    if (check == FALSE) {
2900      return FALSE;
2901    }   
2902  }
2903  return TRUE;   
2904}
2905
2906
2907/**Function********************************************************************
2908
2909  Synopsis    [Checks to see if the output parts of two rows intersect]
2910
2911  Description [Given two rows, this function checks to see if their output parts
2912  intersect, returns a 0 if they don't, and 1 if they do]
2913
2914  SideEffects []
2915
2916  SeeAlso     [Tbl_TableIsDet]
2917
2918******************************************************************************/
2919boolean
2920Tbl_RowOutputIntersect(
2921  Tbl_Table_t * table,
2922  int a,
2923  int b)
2924{
2925  int colNum, check;
2926  Tbl_Entry_t *entrya, *entryb;
2927  Tbl_Row_t *rowb;
2928 
2929  check = FALSE;
2930  rowb = TblTableReadRow(table,b);
2931 
2932  Tbl_RowForEachOutputEntry(table,a, entrya, colNum){
2933    entryb = TblRowReadEntry(rowb,colNum,1);
2934    check = Tbl_EntryTestIntersectEntry(entrya,entryb);
2935
2936    if (check == FALSE) {
2937      return FALSE;
2938    }   
2939  }
2940  return TRUE;   
2941
2942}
2943
2944/*---------------------------------------------------------------------------*/
2945/* Definition of internal functions                                          */
2946/*---------------------------------------------------------------------------*/
2947/**Function********************************************************************
2948
2949  Synopsis    [Set a Row]
2950
2951  Description [Given a table, a row and an index , this function sets the row
2952  in the table]
2953
2954  SideEffects [ The previously set  row is lost ]
2955
2956  SeeAlso     []
2957
2958******************************************************************************/
2959void
2960TblTableSetRow(
2961  Tbl_Table_t *table,
2962  Tbl_Row_t *row,
2963  int i)
2964{
2965  array_insert(Tbl_Row_t*, TblTableReadData(table),i,row);
2966}
2967
2968/**Function********************************************************************
2969
2970  Synopsis    [Return the output array associated with a row.]
2971
2972  Description []
2973
2974  SideEffects [This array is NOT to be modified. The user is encouraged not
2975  to use this function. It is exported so as to make the macros for iteration over
2976  items in the table possible. The user should use these macros for accessing data.
2977  The macros that can be used are mentioned in the SeeAlso list]
2978
2979  SeeAlso     [Tbl_TableForEachEntry Tbl_TableForEachInputEntry Tbl_TableForEachOutputEntry
2980  Tbl_TableForEachInputVar Tbl_TableForEachOutputVar Tbl_TableForEachDefault]
2981
2982******************************************************************************/
2983array_t*
2984TblRowReadOutputs(
2985    Tbl_Row_t * row)
2986{
2987  return (row->outputs);
2988}
2989
2990/**Function********************************************************************
2991
2992  Synopsis    [Return the input array associated with a row.]
2993
2994  Description []
2995
2996  SideEffects [This array is NOT to be modified. The user is encouraged not
2997  to use this function. It is exported so as to make the macros for iteration over
2998  items in the table possible. The user should use these macros for accessing data.
2999  The macros that can be used are mentioned in the SeeAlso list]
3000
3001  SeeAlso     [Tbl_TableForEachEntry Tbl_TableForEachInputEntry Tbl_TableForEachOutputEntry
3002  Tbl_TableForEachInputVar Tbl_TableForEachOutputVar Tbl_TableForEachDefault]
3003
3004******************************************************************************/
3005array_t*
3006TblRowReadInputs(
3007    Tbl_Row_t * row)
3008{
3009  return (row->inputs);
3010}
3011
3012/**Function********************************************************************
3013
3014  Synopsis    [Read a table row]
3015
3016  Description [Given a table and an integer rowNum, this return the rowNumth
3017  Tbl_Row_t]
3018
3019  SideEffects []
3020
3021  SeeAlso     []
3022
3023******************************************************************************/
3024Tbl_Row_t*
3025TblTableReadRow(
3026  Tbl_Table_t *table,
3027  int rowNum)
3028{
3029  return(array_fetch(Tbl_Row_t*,TblTableReadData(table),rowNum));
3030}
3031
3032
3033/**Function********************************************************************
3034
3035  Synopsis    [Allocate space for a row]
3036
3037  Description []
3038
3039  SideEffects []
3040
3041  SeeAlso     []
3042
3043******************************************************************************/
3044Tbl_Row_t*
3045TblRowAlloc(void)
3046{
3047  Tbl_Row_t *row;
3048
3049  row = ALLOC(Tbl_Row_t,1);
3050  row->inputs = array_alloc(Tbl_Entry_t*,0);
3051  row->outputs = array_alloc(Tbl_Entry_t*,0);
3052
3053  return row;
3054}
3055
3056
3057/**Function********************************************************************
3058
3059  Synopsis    [Duplicate a table row]
3060
3061  Description []
3062
3063  SideEffects []
3064
3065  SeeAlso     []
3066
3067******************************************************************************/
3068Tbl_Row_t*
3069TblRowDup(
3070  Tbl_Row_t * row)
3071{
3072  Tbl_Row_t *newrow;
3073  Tbl_Entry_t *newEntry, *entry;
3074  int i;
3075
3076  newrow = TblRowAlloc();
3077
3078  for (i=0; i < array_n(row->inputs); i++){
3079    entry = array_fetch(Tbl_Entry_t*,row->inputs,i);
3080    if (entry != NIL(Tbl_Entry_t)) {
3081      newEntry= Tbl_EntryDup(entry);
3082    }
3083    else {
3084      newEntry = NIL(Tbl_Entry_t);
3085    }
3086    TblRowSetEntry(newrow,newEntry,i,0);
3087  }
3088
3089  for (i=0; i < array_n(row->outputs); i++){
3090    entry = array_fetch(Tbl_Entry_t*,row->outputs,i);   
3091    if (entry != NIL(Tbl_Entry_t)) {
3092      newEntry = Tbl_EntryDup(entry);
3093    }
3094    else {
3095      newEntry = NIL(Tbl_Entry_t);
3096    }     
3097    TblRowSetEntry(newrow,newEntry,i,1);
3098  }
3099  return newrow;
3100}
3101
3102/**Function********************************************************************
3103
3104  Synopsis    [Sets the entry in the given row at the given index]
3105
3106  Description [Given a row, an entry , a flag set to 0 to indicate input and
3107  1 for output, and an index, this function sets the
3108  entry in the row at the index.]
3109
3110  SideEffects [The previous entry item at the index is lost]
3111
3112  SeeAlso     []
3113
3114******************************************************************************/
3115void
3116TblRowSetEntry(
3117  Tbl_Row_t *row,
3118  Tbl_Entry_t * entry,
3119  int i,
3120  int flag)
3121{
3122  array_t *carray;
3123 
3124  if (flag ==0) {
3125    carray = TblRowReadInputs(row);
3126  }
3127  else {
3128    carray = TblRowReadOutputs(row);
3129  }
3130   
3131  if (i < array_n(carray)){
3132    array_insert(Tbl_Entry_t*,carray,i,entry);
3133  }
3134  else {
3135    array_insert_last(Tbl_Entry_t*,carray,entry);
3136  }
3137}
3138
3139/**Function********************************************************************
3140
3141  Synopsis    [Free a Tbl_Row_t]
3142
3143  Description [Given a Tbl_Row_t, this function frees all memory associated
3144  with it. ]
3145
3146  SideEffects []
3147
3148  SeeAlso     [TblRowAlloc]
3149
3150******************************************************************************/
3151void
3152TblRowFree(
3153  Tbl_Row_t *row)
3154{
3155  assert(row != NIL(Tbl_Row_t));
3156  array_free(row->inputs);
3157  array_free(row->outputs);
3158  FREE(row);
3159}
3160
3161
3162/**Function********************************************************************
3163
3164  Synopsis    [Read the specified index entry in the given row]
3165
3166  Description [Given a Tbl_Row_t* and an integer i, this function returns the
3167  Tbl_Entry_t* at the ith position in the row.It must also be supplied with a
3168  flag to indicate whether an input or output entry is being read.]
3169
3170  SideEffects []
3171
3172  SeeAlso     []
3173
3174******************************************************************************/
3175Tbl_Entry_t*
3176TblRowReadEntry(
3177    Tbl_Row_t *row,
3178    int i,
3179    int flag)
3180{
3181 
3182  if (flag==0) {
3183    return(array_fetch(Tbl_Entry_t*,TblRowReadInputs(row),i));
3184  }
3185  else {
3186    return(array_fetch(Tbl_Entry_t*, TblRowReadOutputs(row),i));
3187  }
3188}
3189
3190
3191/*---------------------------------------------------------------------------*/
3192/* Definition of static functions                                            */
3193/*---------------------------------------------------------------------------*/
3194
3195/**Function********************************************************************
3196
3197  Synopsis    [To compute a hash value for a table entry]
3198
3199  Description [Given a Tbl_Table_t *table, and a Tbl_Entry_t *entry, this function
3200  computes the hash value for the corresponding entry]
3201
3202  SideEffects []
3203
3204  SeeAlso     []
3205
3206******************************************************************************/
3207static int
3208TableEntryComputeHashVal(
3209  Tbl_Table_t *table,
3210  Tbl_Entry_t *entry)
3211{
3212  int numRows, numCols;
3213  lsGen gen;
3214  int value;
3215  Tbl_Range_t *range;
3216  int total;
3217
3218  numRows = Tbl_TableReadNumRows(table);
3219  numCols = Tbl_TableReadNumInputs(table) + Tbl_TableReadNumOutputs(table) + numRows+1;
3220  total = 0;
3221
3222  if(entry->type == Tbl_EntryNormal_c) {
3223    Tbl_EntryForEachValue(entry,value,gen,range) {
3224      total = total + (int) pow(numCols,value);
3225    }
3226  }
3227  else if(entry->type == Tbl_EntryEqual_c) {
3228    value = Var_VariableReadNumValues(Tbl_EntryReadActualVar(table,entry));
3229    total = total + (int) pow(numCols,value);
3230  }
3231 
3232  return total;
3233}
3234
3235/**Function********************************************************************
3236
3237  Synopsis    [Create a array of size entries, each intialized to -1]
3238
3239  Description [Given an integer size, this function returns an array of size
3240  that has all entries intialized to -1]
3241
3242  SideEffects []
3243
3244  SeeAlso     []
3245
3246******************************************************************************/
3247static array_t*
3248TableCreatIntArray(
3249  int size)
3250{
3251  array_t *result;
3252  int i;
3253 
3254  result = array_alloc(int,0);
3255  for (i=0; i < size; i++) {
3256    array_insert_last(int,result,-1);
3257  }
3258  return result;
3259}
3260
3261
3262/**Function********************************************************************
3263
3264  Synopsis           [Get table signature as a string]
3265
3266  Description        [optional]
3267
3268  SideEffects        [required]
3269
3270  SeeAlso            [optional]
3271
3272
3273******************************************************************************/
3274static char*
3275TableObtainSignature(Tbl_Table_t * table,
3276                     int outputColumn)
3277{
3278  char *                signature;
3279  char *                sig;            /* Signature under construction */
3280
3281  int                   row;            /* locations in the table */
3282  int                   column;
3283
3284  Tbl_Entry_t *         entry;          /* Entry at row, column */
3285
3286  int                   value;          /* Value of an entry */
3287  lsGen                 gen;            /* For Tbl_EntryForEachValue */
3288  Tbl_Range_t *         range;
3289
3290  int                   varIndex;       /* Index of the column of this variable */
3291
3292  /*
3293   * TODO: This is unsafe!
3294   */
3295
3296  signature = ALLOC( char, 10000 );
3297  sig = signature;
3298
3299  for ( row = Tbl_TableReadNumRows( table ) ; --row >=0 ; ) {
3300
3301    /*
3302     * Print each of the inputs in this row
3303     */
3304
3305    Tbl_RowForEachInputEntry( table, row, entry, column ) {
3306
3307      switch ( Tbl_EntryReadType( entry ) ) {
3308
3309        /*
3310         * An equality entry ("this column is equal to that column")
3311         */
3312
3313      case Tbl_EntryEqual_c:
3314
3315        /*
3316         * Find the column index, first assuming it's an input
3317         */
3318
3319        varIndex = Tbl_EntryReadVarIndex(entry);
3320
3321        sprintf( sig, "=%d", varIndex );
3322        sig += strlen( sig );
3323        break;
3324
3325        /*
3326         * A normal range entry - print a comma-separated list of values
3327         */
3328
3329      case Tbl_EntryNormal_c:
3330        Tbl_EntryForEachValue( entry, value, gen, range ) {
3331          sprintf(sig, "%d,", value );
3332          sig += strlen( sig );
3333        }
3334        break;
3335
3336        /*
3337         * Unassigned -- append a "?"
3338         */
3339
3340      case Tbl_EntryUnassigned_c:
3341        sig[0] = '?';
3342        sig++;
3343        break;
3344        /*
3345         * None of the Above -- we're in trouble
3346         */
3347
3348      default:
3349        assert(0);
3350        break;
3351
3352      }
3353     
3354      /*
3355       * Separate entries with spaces
3356       */
3357     
3358      sig[0] = ' ';
3359      sig++;
3360
3361    }
3362
3363    /*
3364     * Print the output column's entry
3365     */
3366
3367    entry = Tbl_TableReadEntry( table, row, outputColumn, 1 );
3368
3369    switch ( Tbl_EntryReadType( entry ) ) {
3370
3371      /*
3372       * An equality entry ("this column is equal to that column")
3373       */
3374
3375    case Tbl_EntryEqual_c:
3376
3377      /*
3378       * Find the column index, first assuming it's an input
3379       */
3380
3381      varIndex = Tbl_EntryReadVarIndex(entry);
3382
3383      sprintf( sig, "=%d", varIndex );
3384      sig += strlen( sig );
3385      break;
3386     
3387      /*
3388       * A normal range entry - print a comma-separated list of values
3389       */
3390     
3391    case Tbl_EntryNormal_c:
3392      Tbl_EntryForEachValue( entry, value, gen, range ) {
3393        sprintf(sig, "%d,", value );
3394        sig += strlen( sig );
3395      }
3396      break;
3397     
3398      /*
3399       * Unassigned -- append a "?"
3400       */
3401     
3402    case Tbl_EntryUnassigned_c:
3403      sig[0] = '?';
3404      sig++;
3405      break;
3406     
3407      /*
3408       * None of the Above -- we're in trouble
3409       */
3410     
3411    default:
3412      assert(0);
3413      break;
3414     
3415    }
3416
3417    /*
3418     * Separate rows with newlines
3419     */
3420
3421    sig[0] = '\n';
3422    sig++;
3423
3424  }
3425
3426  /*
3427   * Terminate the signature string
3428   */
3429
3430  sig[0] = '\0';
3431
3432  return signature;
3433}     
3434
3435
3436/**Function***********************************************************
3437
3438  Synopsis [Comparison function for qsort.]
3439
3440  Description [This function is used by qsort to order table inputs
3441  according to the MDD variable order in the support of the MVF.]
3442
3443  SideEffects [none]
3444
3445  SeeAlso [Tbl_TableCreateTrueSupportTableForOutput]
3446
3447**********************************************************************/
3448static int
3449varCompare(const void *x, const void *y)
3450{
3451  Var_Ord_t *a = (Var_Ord_t *) x;
3452  Var_Ord_t *b = (Var_Ord_t *) y;
3453  return(a->rank - b->rank);
3454}
Note: See TracBrowser for help on using the repository browser.