node.c

Go to the documentation of this file.

extern "C" {

#include "tarski.h"


/*---------------------------------------------------------------------------*/
/* Static function prototypes                                                */
/*---------------------------------------------------------------------------*/

static Fnode *node_dup_recur( Net_t *net, Fnode *formula, char *suf, st_table *processedTable );

F Fnil;
st_table *nodeHash= ( st_table * ) 0;  // unique table for formula nodes
st_table *stringHash= ( st_table * ) 0; // unique table for strings

// gen from enum types by 
// awk '{print $1}' | sed '{s/_c,//g}' | awk '{print "\"" $1 "\","}'
char *typeString[] = {
  "Undef",
  "LIST", // "List",
  "PAIR", // "Pair",
  "SI", // "ScalarPI",
  "BI", // "BooleanPI",
  "SR", // "ScalarReg",
  "BR", // "BooleanReg",
  "IntSV", // "InternalScalarVar",
  "IntBV", // "InternalBooleanVar",
  "Assign",
  "And",
  "Or",
  "Not",
  "Iff",
  "TRUE",
  "FALSE",
  "Mux",
  "EQ", //"Equal",
  "UIF1", // "UnaryFunc",
  "UIF", // "Func",
  "Reln", // "Relation"
  "Const", // "ScalarConst"
};

/*---------------------------------------------------------------------------*/
/* Definition of exported functions                                          */
/*---------------------------------------------------------------------------*/

Fnode * 
new_node(
  Operator_t type,
  Fnode * lchild,
  Fnode * rchild )
{
  Fnode * tnode;
  tnode = new_node_raw( type, lchild, rchild );
  Fnode * result = node_register( tnode );

  return result;
}


Fnode * 
new_node_raw(
  Operator_t type,
  Fnode * lchild,
  Fnode * rchild )
{
  Fnode * tnode;
                                                                           
  tnode = ( Fnode * ) malloc( sizeof( Fnode ) );
  tnode->type = type;
  tnode->lchild = lchild; tnode->rchild = rchild;

  return tnode;
}

char *
string_register(
  char *aString
)
{
  char *result;

  if ( stringHash == NIL(st_table) ) {
    stringHash = st_init_table( (int (*)()) strcmp, (int (*)()) st_strhash );
  }

  if ( st_lookup( stringHash, (char *) aString, (char **) & result ) ) {
    // don't free aString, since we don't know if it's a constant...
    return result;
  }
  else {
    st_insert( stringHash, (char *) util_strsav( aString), (char *) aString );
    return aString;
  }
}


Fnode * 
node_register(
  Fnode * aNode
)
{
  Fnode * result;
  if ( aNode == nil ) {
    printf("# attempting to register nil node\n");
    return nil;
  }

  if ( nodeHash == NIL(st_table) ) {
    nodeHash = st_init_table( (int (*)()) node_cmp, (int (*)()) node_hash );
  }

  // need to also check for multiple assigns to the same node,
  // is this the right place to do so?

  // concern - what happens if we have a reg with the same name in 
  // diff places?  
  // if ( Node_HasLeftChildNode( aNode ) ) {
  //   aNode->lchild =  (void *) rn( (F) aNode->lchild );
  // }
  // if ( Node_HasRightChildNode( aNode ) ) {
  //   aNode->rchild =  (void *) rn( (F) aNode->rchild );
  // }

  if ( st_lookup( nodeHash, (char *) aNode, (char **) & result ) ) {
    if ( result == aNode ) {
       printf("Serious problem, registering a node that's identical to existing one\n");
       assert(0);
    }
    free( aNode );
    if ( ( result->type == ScalarPI_c ) ||
        ( result->type == BooleanPI_c ) ) {
      /*printf("--Warning: already defined node %s to be an input\n", (char *) result->lchild );*/
    }
    if ( ( result->type == BooleanReg_c ) ||
        ( result->type == ScalarReg_c ) ) {
      printf("--Warning: already defined node %s to be a register\n", (char *) result->lchild );
    }
    if ( ( result->type == InternalScalarVar_c ) ||
        ( result->type == InternalBooleanVar_c ) ) {
      printf("--Warning: already defined node %s to be an internal Boolean var\n", (char *) result->lchild );
    }
    return result;
  }
  else {
    Fnode * dupNode = (Fnode *) malloc( sizeof( Fnode ) );

    dupNode->type = aNode->type;
    dupNode->lchild = aNode->lchild;
    dupNode->rchild = aNode->rchild;

    st_insert( nodeHash, (char *) dupNode, (char *) dupNode );
    // AA: somehow this free is corrupting our bryantize generated nodes
    free( aNode ); 
    return dupNode;
  }
}



int 
node_cmp(
  Fnode * aNode,
  Fnode * bNode
)
{
  if ( aNode->type < bNode->type ) {
    return -1;
  }
  else if ( aNode->type > bNode->type ) {
    return 1;
  }
  if ( aNode->lchild < bNode->lchild ) {
    return -1;
  }
  else if ( aNode->lchild > bNode->lchild ) {
    return 1;
  }
  if ( aNode->rchild < bNode->rchild ) {
    return -1;
  }
  else if ( aNode->rchild > bNode->rchild ) {
    return 1;
  }
  return 0; // must be equal on all fields
}

int 
node_hash(
  Fnode * aNode,
  int modulus
)
{
  int val = 7*( (int) aNode->type + 1) + 3*( (int) aNode->lchild) + 17*( (int) aNode->rchild);

  return ( (val < 0) ? -val : val) % modulus;
}
  


Fnode * 
node_dup(
  Net_t *net,
  Fnode * formula,
  char *suf,
  st_table *processedTable
)
{
  // HM: processedTable is now an arg to the function
  Fnode * result = node_dup_recur( net, formula, suf, processedTable );
  return result;
}



static Fnode * 
node_dup_recur(
  Net_t *net,
  Fnode * formula,
  char *suf, 
  st_table *processedTable
)
{
  Fnode * result;

  if ( formula == nil ) {
    return nil;
  }

  if ( !st_lookup( net->nodeToId, (char *) formula, (char **) 0) ) {
    // must be a string if it's not nil and not a formula
    // use rs to preserve canonicity
    char *newName = (char *) rs( util_strcat( (char *) formula, suf ) );
    return (Fnode * ) newName;
  }

  if ( st_lookup( processedTable, (char *) formula, (char **) & result ) ) {
    return result;
  }
  result = new_node_raw( formula->type, nil, nil );
  st_insert( processedTable, (char *) formula, (char *) result ); 

  Fnode * ldup;
  if ( ( formula->type == UnaryFunc_c ) || 
       ( formula->type == Func_c ) ||
       ( formula->type == ScalarConst_c ) ) {
    // these are special - we don't want to change the identifier
    ldup = (Fnode *) formula->lchild;
  }
  else {
    ldup = node_dup_recur( net, (Fnode *) formula->lchild, suf, processedTable );
  }
  Fnode *rdup = node_dup_recur( net, (Fnode *) formula->rchild, suf, processedTable );

  result->lchild = ldup;
  result->rchild = rdup;

  return result;
}


int 
F::node_print(
)
{
  Fnode *a = this->raw;
  if ( a == nil ) {
    printf(" nil \n");
    return 0;
  }
  printf("Type: %d, Left: %p, Right %p\n", a->type, a->lchild, a->rchild );  return 0;
}


Fnode *
Fnode::operator&(
  Fnode * q
) 
{
  assert( node_test_is_boolean( this ) && 
          node_test_is_boolean( q ) );

  // attempt to do some normalization
  Fnode* lchild = ( this < q ) ? this : q;
  Fnode* rchild = ( this < q ) ? q : this;

  Fnode * result = new_node_raw( And_c, lchild, rchild );
  Fnode * tmp = rn( result );
  return tmp;
}

Fnode *
Fnode::operator,(
  Fnode *q 
) 
{
  printf("You've made a mistake, don't use the comma op! q = %p\n", q);
  assert(0);
}


Fnode *
Fnode::operator!(
) 
{
  assert( node_test_is_boolean( this ) );
  Fnode * result = new_node_raw( Not_c, this, nil );
  Fnode * tmp = rn( result );
  return tmp;
}

Fnode *
Fnode::operator|(
  Fnode * q
) 
{
  assert( node_test_is_boolean( this ) && 
          node_test_is_boolean( q ) );
  // attempt to do some normalization
  Fnode* lchild = ( this < q ) ? this : q;
  Fnode* rchild = ( this < q ) ? q : this;
  Fnode * result = new_node_raw( Or_c, lchild, rchild );
  Fnode * tmp = rn( result );
  return tmp;
}

Fnode *
Fnode::operator^(
  Fnode * q
) 
{
  assert( node_test_is_boolean( this ) && 
          node_test_is_boolean( q ) );

  // attempt to do some normalization
  Fnode* lchild = ( this < q ) ? this : q;
  Fnode* rchild = ( this < q ) ? q : this;

  Fnode * notThis = ! (*lchild );
 
  Fnode * notq = ! (*rchild );

  Fnode * not_thisANDnotq = *notThis & notq;

  Fnode * not_notThisANDq = *lchild & rchild;

  Fnode * result = *not_notThisANDq | not_thisANDnotq;

  return result;
}

Fnode *
Fnode::operator%(
  Fnode * q
) 
{
  if ( !( ( ( node_test_is_scalar( this ) ) && 
          ( node_test_is_scalar( q ) ) ) ||
        ( ( node_test_is_boolean( this ) ) &&
          ( node_test_is_boolean( q ) ) ) ) ) {
    printf("Arguments to pair operator (percent) need to be \
scalar or both boolean\n");
    assert(0);
  }
  Fnode * tmp1 = new_node_raw( Pair_c, this, q );
  Fnode * tmp2 = rn( tmp1 );
  return tmp2;
}

Fnode *
Fnode::operator==(
 Fnode *B
) 
{
  if ( !( ( ( node_test_is_scalar( this ) ) && 
          ( node_test_is_scalar( B ) ) ) ||
        ( ( node_test_is_boolean( this ) ) &&
          ( node_test_is_boolean( B ) ) ) ) ) {
    printf("Arguments to operator == both need to be "
           "scalar  or both boolean\n");
    assert(0);
  }

  // attempt to do some normalization
  Fnode* lchild = ( this < B ) ? this : B;
  Fnode* rchild = ( this < B ) ? B : this;

  Fnode* result;
  if ( node_test_is_scalar( lchild ) ) {
    Fnode* tmp = new_node_raw( Equal_c, lchild, rchild );
    result = rn( tmp );
  }
  else {
    Fnode* tmp = (*lchild) ^ rchild;
    result = !(*tmp);
  }
  return result;
}


int
node_test_is_boolean(
 Fnode* A
) 
{

  int result =  ( A->type == BooleanPI_c ) ||
                ( A->type == BooleanReg_c ) ||
                ( A->type == InternalBooleanVar_c ) ||
                ( A->type == Relation_c ) ||
                ( A->type == And_c ) ||
                ( A->type == Or_c ) ||
                ( A->type == Not_c ) ||
                ( A->type == Iff_c ) ||
                ( A->type == TRUE_c ) ||
                ( A->type == FALSE_c ) ||
                ( A->type == Equal_c );

  return result;
}

int
node_test_is_scalar(
 Fnode * A
) 
{
  int result =  ( A->type == ScalarPI_c ) ||
                ( A->type == ScalarReg_c ) ||
                ( A->type == InternalScalarVar_c ) ||
                ( A->type == Mux_c ) ||
                ( A->type == UnaryFunc_c ) ||
                ( A->type == Func_c ) ||
                ( A->type == ScalarConst_c );

  return result;
}


F
TRUE()
{
  F result;
  result.raw = nn( TRUE_c, nil, nil );
  return result;
}


F
FALSE()
{
  F result;
  result.raw = nn( FALSE_c, nil, nil );
  return result;
}


F
si(
  char *name
)
{
  F result;
  char *new_name = (char *) malloc((strlen(name) + 3)*sizeof(char));
  strcpy(new_name, name);
  result.raw = nn( ScalarPI_c, (Fnode *) rs(new_name), nil );
  return result;
}


F
bi(
  char *name
)
{
  F result;
  char *new_name = (char *) malloc((strlen(name) + 3)*sizeof(char));
  strcpy(new_name, name);
  result.raw = nn( BooleanPI_c, (Fnode *) rs(new_name), nil );
  return result;
}



Fnode *
Fnode::operator<<(
  Fnode * q
) 
{
   if ( q->type != Pair_c ) {
     printf("Incorrect use of << operator, need list to tack on\n");
     assert(0);
   }
   if ( ( this-> type != BooleanReg_c ) &&
        ( this-> type != ScalarReg_c ) ) {
     printf("Can only tack on to a reg!\n");
     assert(0);
   }
   this->rchild = q;
   return this;
}




F
sr(
  char *name
)
{
  F result;
  char *new_name = (char *) malloc((strlen(name) + 3)*sizeof(char));
  strcpy(new_name, name);
  result.raw = nn( ScalarReg_c, (Fnode *) rs(new_name), nil );
  return result;
}


F
br(
  char *name
)
{
  F result;
  char *new_name = (char *) malloc((strlen(name) + 3)*sizeof(char));
  strcpy(new_name, name);
  result.raw = nn( BooleanReg_c, (Fnode *) rs(new_name), nil );
  return result;
}


F
sc(
  char *name
)
{
  F result;
  char *new_name = (char *) malloc((strlen(name) + 3)*sizeof(char));
  strcpy(new_name, name);
  result.raw = nn( ScalarConst_c, (Fnode *) rs(new_name), nil );
  return result;
}

F
bc(
  char *name
)
{
  char *new_name = (char *) malloc((strlen(name) + 3)*sizeof(char));
  strcpy(new_name, name);
  char *pi_name = util_strcat( "SC_", new_name );
  F pi = bi( pi_name );
  F reg = br( new_name );
  F pair = pi % reg;
  reg << pair;

  return reg;
}

F
uif2(
  char *name,
  F arg1,
  F arg2
)
{
  F result;
  char *new_name = (char *) malloc((strlen(name)+2)*sizeof(char));
  strcpy(new_name, name);
  result.raw = new_node( Func_c, (Fnode *) rs(new_name), (list( arg1, arg2, Fnil )).raw );
  return result;
}

F
uir3(
  char *name,
  F arg1,
  F arg2,
  F arg3
)
{
  F truenode = sc("TRUE_c");
  F tmp = uif3( name, arg1, arg2, arg3 );
  F result = (tmp == truenode );

  return result;
}

F
uif3(
  char *name,
  F arg1,
  F arg2,
  F arg3
)
{
  F result;
  char *new_name = (char *) malloc((strlen(name) + 3)*sizeof(char));
  strcpy(new_name, name);
  result.raw = new_node( Func_c, (Fnode *) rs(new_name), (list( arg1, arg2, arg3, Fnil )).raw );
  return result;
}


F
uif(
  char *name,
  F arg
)
{
  F result;
  char *new_name = (char *) malloc(sizeof(char)*(strlen(name)+2));
  strcpy(new_name, name);
  result.raw = new_node( Func_c, (Fnode *) rs(new_name), (list( arg, Fnil )).raw );
  return result;
}

F
assign(
  char *name,
  F arg
)
{
  F result;
  char *new_name = (char *) malloc((strlen(name) + 3)*sizeof(char));
  strcpy(new_name, name);
  result.raw = new_node( Assign_c, (Fnode *) rs(new_name), arg.raw );
  return result;
}


F
mux(
  F c,
  F D1,
  F D0
)
{
  F pair = D1 % D0; // create a pair, first is D1 then is D0
  F result;
  result.raw = new_node( Mux_c, c.raw, pair.raw );
  return result;
}


int
Node_HasLeftChildNode(
  Fnode* node
)
{
  if ( node == nil ) {
    return 0;
  }
  int result = ( node->type == List_c ) ||
                (node->type == Pair_c ) ||
                (node->type == Equal_c ) ||
                (node->type == And_c ) ||
                (node->type == Or_c ) ||
                (node->type == Not_c ) ||
                (node->type == Mux_c ) ||
                (node->type == Iff_c );

  return result;
}

int
Node_HasRightChildNode(
  Fnode* node
)
{
  if ( node == nil ) {
    return 0;
  }
  int result = (node->type == List_c ) ||
                (node->type == Pair_c ) ||
                (node->type == ScalarReg_c ) ||
                (node->type == BooleanReg_c ) ||
                (node->type == Relation_c ) ||
                (node->type == Assign_c ) ||
                (node->type == And_c ) ||
                (node->type == Or_c ) ||
                (node->type == Iff_c ) ||
                (node->type == Mux_c ) ||
                (node->type == Equal_c ) ||
                (node->type == UnaryFunc_c ) ||
                (node->type == Func_c );

  return result;
}

Fnode * 
cons(
  Fnode * a,
  Fnode * b )
{
  Fnode * tnode;

  tnode = ( Fnode * ) malloc( sizeof( Fnode ) );
  tnode->type = List_c; 
  tnode->lchild = a; tnode->rchild = b;
                                                                           
  return tnode;
}

Fnode * car(
  Fnode * a
)
{
  return (Fnode *) a->lchild;
}

Fnode * cdr(
  Fnode * a
)
{
  return (Fnode *) a->rchild;
}

F
list( 
  F startNode, ... ) 
{
  va_list ap;
  F p;
  array_t *tmpNodes = array_alloc( F, 0 );

  array_insert_last( F, tmpNodes, startNode );
  va_start( ap, startNode );
  p = va_arg( ap, F );
  while ( p.raw != Fnil.raw ) {
    array_insert_last( F, tmpNodes, p );
    p = va_arg(ap, F );
  }  
  va_end( ap );

  int i;
  F result;
  result.raw = nil;
  for ( i = array_n( tmpNodes ) - 1 ; i >= 0 ; i-- ) {
    F aNode = array_fetch( F, tmpNodes, i );
    result.raw = new_node( List_c, aNode.raw, result.raw );
  }
  return result;

} 



int 
listlength(
  F aList
)
{
  if ( aList.rchild() == nil ) {
    return 0;
  }
  else {
    assert (aList.type() == List_c );
    F tmp;
    tmp.raw = aList.rchild();
    return listlength( tmp ) + 1;
  }
}

F
ri(
  char *name,
  F restrictedList
)
{
  F unrestrictedInput = si( name );

  F pred;
  pred.raw = nil;
  F first;
  first.raw = restrictedList.lchild();

  F tmp = restrictedList;
  while ( tmp.raw != nil ) {
    F lchild;
    lchild.raw = tmp.lchild();
    assert( lchild.type() == ScalarConst_c );
    if ( pred.raw != nil ) {
       pred = pred | ( unrestrictedInput == lchild );
    }
    else {
      pred = ( unrestrictedInput == lchild );
    }
    tmp.raw = tmp.rchild();
  }
  F result = mux( pred, unrestrictedInput, first );
  return result;
}

  
F
restrict(
  F aNode,
  F restrictedList
)
{
  F first;
  first.raw = restrictedList.lchild();  // default

  F pred;
  pred.raw=nil;
  F tmp = restrictedList;
  while ( tmp.raw != nil ) {
    F lchild;
    lchild.raw = tmp.lchild();
    assert( lchild.type() == ScalarConst_c );
    if ( pred.raw != nil ) {
       pred = pred | ( aNode == lchild );
    }
    else {
      pred = ( aNode == lchild );
    }
    tmp.raw = tmp.rchild();
  }
  F result = mux( pred, aNode, first );
  return result;
}

Fnode *
nn(
  Operator_t a, 
  Fnode * b, 
  Fnode * c) 
{
  return new_node( a, b, c );
}
                                                                                                   
Fnode * 
rn( 
  Fnode * aNode 
) 
{ 
  return node_register( aNode );
}

char* rs( 
  char* aString 
) 
{ 
  return string_register( aString );
}

Fnode*
Mux_ThenInput( 
  Fnode* aNode 
) 
{ 
  assert( aNode->type == Mux_c); 
  return (Fnode *) ( (Fnode *) aNode->rchild)->lchild; 
}
                                                                                                   
Fnode*
Mux_ElseInput( 
  Fnode* aNode 
) 
{ 
  assert( aNode->type == Mux_c); 
  return (Fnode *) ( (Fnode *) aNode->rchild)->rchild; 
}
                                                                                                   
Fnode *
Reg_InitFunc(
  Fnode * node
)
{
  assert( ( node->type == BooleanReg_c ) || ( node->type == ScalarReg_c ) );
  return (Fnode *) ((Fnode *) ((node->rchild)->lchild));
}
                                                                                                   
Fnode *
Reg_NsFunc(
  Fnode * node
)
{
  assert( ( node->type == BooleanReg_c ) || ( node->type == ScalarReg_c ) );
  return (Fnode *) ((Fnode *) ((node->rchild)->rchild));
}

Fnode *
Func_FirstArg(
  Fnode * node
)
{
  assert( ( node->type == UnaryFunc_c ) || ( node->type == Func_c ) );
  return (Fnode *) ((Fnode *) ((node->rchild)->lchild));
}

Fnode *
Func_SecondArg(
  Fnode * node
)
{
  assert(node->type == Func_c);
  if((node->rchild != nil) && 
     ((Fnode *) node->rchild)->rchild != nil) {
    return (Fnode *) ( ((Fnode *) ((Fnode *) node->rchild)->rchild)->lchild);
  }
  else {
    return nil;
  }
}

Fnode *
Func_ThirdArg(
  Fnode * node
)
{
  assert(node->type == Func_c);
  if((node->rchild != nil) &&
     (((Fnode *) node->rchild)->rchild != nil) &&
     ((Fnode *) ((Fnode *) node->rchild)->rchild)->rchild != nil) {
    return (Fnode *) ( ((Fnode *) ((Fnode *) ((Fnode *) node->rchild)->rchild)->rchild) ->lchild);
  }
  else {
    return nil;
  }
}

Fnode *
Func_NextArg(
             Fnode * func_node,
             Fnode * rchild_node
)
{
  assert(func_node != nil);
  assert((func_node->type == Func_c) || (func_node->type == UnaryFunc_c)) ;
  if(rchild_node == nil) {
    return nil;
  }
  else {
    return (Fnode *) rchild_node->lchild;
  }
}

st_table *
nodeGetSupport(
 F aNode 
)
{
  st_table *result = st_init_table( (int (*)()) node_cmp, (int (*)()) node_hash );
  st_table *processedTable = st_init_table( (int (*)()) node_cmp, (int (*)()) node_hash );
  nodeGetSupportRecur( aNode, result, processedTable);
  st_free_table( processedTable );

  return result;
}


void
nodeGetSupportRecur(
  F aNode,
  st_table *result,
  st_table *processedTable
)
{
  if ( aNode.raw == NIL( Fnode ) ) {
    return;
  }
  assert( node_test_is_boolean( aNode.raw ) );
  if ( st_lookup( processedTable, (char *) aNode.raw, (char **) 0 ) ) {
    return;
  }
  
  F leftNodeWrapped;
  F rightNodeWrapped;
  leftNodeWrapped.raw = aNode.lchild();
  rightNodeWrapped.raw = aNode.rchild();

  Operator_t type = aNode.type();
  if ( ( type == BooleanPI_c ) || 
       ( type == BooleanReg_c ) ) {
    st_insert( result, ( char *) aNode.raw, ( char * ) 0 );
    return;
  }
  if ( ( type == InternalBooleanVar_c ) ||
       ( type == Assign_c ) ) {
    nodeGetSupportRecur( rightNodeWrapped, result, processedTable );
  }
  nodeGetSupportRecur( leftNodeWrapped, result, processedTable );
  nodeGetSupportRecur( rightNodeWrapped, result, processedTable );

  st_insert( processedTable, (char *) aNode.raw, (char *) 0 );

  return;
}

void
reg(
  F aReg,
  F nextState,
  F initState
)
{
  aReg << ( initState % nextState );
  return;
}

Fnode * 
node_GetUnique(
                  Fnode * aNode
                  ) 
{
  Fnode *unique_aNode = nil;
  if(!st_lookup( nodeHash, (char *) aNode, (char **) & unique_aNode)) {
    unique_aNode = aNode;
    st_insert( nodeHash, (char *) unique_aNode, (char *) unique_aNode );
  }
  return unique_aNode;
}

void
NodeAssignRegister(F reg,
                   F init_state,
                   F next_state)
{
 
  reg << (init_state % next_state);
}


} // extern "C"

---