/***********************************
  (C) Copyright 1992-1993; dit/upm
  Distributed under the conditions stated in the
  TOPO General Public License (see file LICENSE)
  ***********************************/

/***********************************

  David Larrabeiti Lopez

  March  5 1991

  Module to detect & manage duplicated behaviours
  through a Behaviour Hash Table.

  The elements to be stored are cells like this:

  BehaviourC
  name
  copy
  B1   B2

  where B2 is the behaviour to be processed,
  and name := -1 | BehHashKey(B2);


  COMPILATION OPTIONS: The behaviour of this module can be modified
  by the following compilation flags:

  (none)

  ************************************/

/* LINTLIBRARY */

#include "limisc.h"
#include "lilists.h"
#include "lihash.h"
#include "licell.h"
#include "baexpr.h"
#include "baattr.h"
#include "badefca.h"
#include "batables.h"
#include "excomp.h"
#include "exdupbeh.h"
#include "baprint.h"



/******************************************************************
 *                                *
 *            Behaviour Hash Key                  *
 *                                *
 *******************************************************************/

/* Maximum level in the behaviour tree used to calculate the hash-key. */

#define HASHMAXLEVEL 2

/*----------------------------------------------------------------*/

#define LEFT_BIT ~((~0)>>1)

/*----------------------------------------------------------------*/

/* hk_value
 * the hash key is stored in this variable.
 */
static unsigned hk_value;

/*----------------------------------------------------------------*/

static void update_hk(v)
  /* KJT 22/01/23: changed type to "unsigned long" */
  unsigned long v;
{
  /*
     hk_value = ( (hk_value<<1) | (hk_value & LEFT_BIT) ) ^ (hk_value + v);
     hk_value ^= ( ((v+hk_value)<<1) | (hk_value & LEFT_BIT) ) ;
     */
  if ( v >> (WORDLENGTH-1) == 0 )
    hk_value ^=  (v+hk_value) << 1 ;
  else
    hk_value ^= ( ((v+hk_value)<<1) ^ 338217 ) ;
}

/*----------------------------------------------------------------*/

static void ExprHashKey( e )
     ExprTyp e;
{
  int i;

  if ( IsOperationE(e) ) {
    update_hk((unsigned)LookNameE(e));
    for (i=NumArgE(e) ; i>0 ; i--)
      ExprHashKey(LookArgE(e,i));
  }
  else
    update_hk((unsigned)GetV_sort(LookNameE(e)));
}

/*----------------------------------------------------------------*/

static void BHK( beh, n )
     BehTyp beh;
     int n;
{
  DescriptorTyp    type;
  GateListTyp      gl;
  OfferListTyp     ol;
  VarAssignListTyp val;
  RelabFuncListTyp rfl;
  GateSetTyp       gs;
  PredicateTyp     pred;
  ExprListTyp      el;
  GateDecListTyp   gdl;
  PGateDecTyp      gd;
  ITContListTyp    itcl;
  PITContTyp       itc;
  int              i;

  while ( beh!=NULL ) {
    type = LookTypeB(beh);
    switch(type)
      { case GateC:
	  update_hk((unsigned)(1024+type+n+LookNameB(beh)));
	  pred = (PredicateTyp)LookAInfo(LookA(beh,PA));
	  if ( pred != NULL )
	    ExprHashKey(LookRwPred(pred));
	case ExitC:
	  update_hk((unsigned)(type+n));
	  ol = (OfferListTyp)LookAInfo(LookA(beh,OLA));
	  for ( ; ol!=NULL; ol=MvNextOffer(ol) ) {
	    update_hk((unsigned)(128+LookKindOffer(ol)));
	    ExprHashKey( LookExprOffer(ol) );
	  }
	  beh = (--n == 0) ? NULL : LookArgB(beh,1);
	  break;

	case IC:
	  update_hk((unsigned)(type+n));
	  beh = LookArgB(beh,1);
	  break;

	case StopC:
	  update_hk((unsigned)(type+n));
	  beh = NULL;
	  break;

	case AlternativeC:
	  update_hk((unsigned)(2048+type+n));
	  for (i=NumArgB(beh) ; i>1 ; i--)
	    BHK(LookArgB(beh,i),n);
	  beh = LookArgB(beh,1);
	  break;

	case ParallelC:
	  update_hk((unsigned)(256+type+n+LookNameB(beh)));
	  BHK( LookArgB(beh,2), n );
	case HidingC:
	  gs = (GateSetTyp)LookAInfo( LookA( beh, GSA ) );
	  update_hk((unsigned)(type+n));
	  if ( gs!=NULL )
	    update_hk(gs[0]);
	  beh = LookArgB(beh,1);
	  break;

	case PletC:
	  val = (VarAssignListTyp)LookAInfo(LookA(beh,VALA));
	  if ( ! IsVoidVAL(val) ) {
	    update_hk((unsigned)(4096+type+n));
	    for ( ; val!=NULL; val=Next_list(val) ) {
	      if (LookVarVAL(val) != LookNameE(LookExprVAL(val))) {
		update_hk((unsigned)GetV_sort(LookVarVAL(val)));
		ExprHashKey(LookExprVAL(val));
	      }
	    }
	  }
	  beh = LookArgB(beh,1);
	  break;

	case LetC:
	  update_hk((unsigned)(type+n));
	  val = (VarAssignListTyp)LookAInfo(LookA(beh,VALA));
	  for ( ; val!=NULL; val=Next_list(val) ) {
	    update_hk((unsigned)GetV_sort(LookVarVAL(val)));
	    ExprHashKey(LookExprVAL(val));
	  }
	  beh = LookArgB(beh,1);
	  break;

	case RelabellingC:
	  update_hk((unsigned)(type+n));
	  rfl = (RelabFuncListTyp)LookAInfo(LookA(beh,RFLA));
	  for ( ; rfl!=NULL; rfl = Next_list(rfl) ) {
	    update_hk((unsigned)LookActGateRF(rfl));
	    update_hk((unsigned)LookForGateRF(rfl));
	  }
	  beh  = LookArgB(beh,1);
	  break;

	case GuardC:
	  update_hk((unsigned)(type+n));
	  pred = (PredicateTyp)LookAInfo(LookA(beh,PA));
	  ExprHashKey(LookRwPred(pred));
	  beh = LookArgB(beh,1);
	  break;

	case ProcessInstC:
	  update_hk((unsigned)(type+n+LookNameB(beh)));
	  gl = (GateListTyp)LookAInfo(LookA(beh,GLA));
	  for ( ; gl!=NULL; gl=Next_list(gl) )
	    update_hk((unsigned)LookInfo_list(gl));
	  el = (ExprListTyp)LookAInfo(LookA(beh,ELA));
	  for ( ; el!=NULL; el=Next_list(el) )
	    ExprHashKey((ExprTyp)LookInfo_list(el));
	  beh = NULL;
	  break;

	case ChoiceC:
	  update_hk((unsigned)(type+n));
	  el = (ExprListTyp)LookAInfo(LookA(beh,ELA));
	  for ( ; el!=NULL; el=Next_list(el) )
	    ExprHashKey((ExprTyp)LookInfo_list(el));
	  beh = LookArgB(beh,1);
	  break;

	case EnablingC:
	  update_hk((unsigned)(type+n));
	  el = (ExprListTyp)LookAInfo(LookA(beh,ELA));
	  for ( ; el!=NULL; el=Next_list(el) )
	    ExprHashKey((ExprTyp)LookInfo_list(el));
	  BHK( LookArgB(beh,2), n );
	  beh = LookArgB(beh,1);
	  break;

	case DisablingC:
	  update_hk((unsigned)(type+n));
	  BHK( LookArgB(beh,2), n );
	  beh = LookArgB(beh,1);
	  break;

	case ParC:
	case GateChoiceC:
	  update_hk((unsigned)(type+n));
	  gdl = (GateDecListTyp)LookAInfo(LookA(beh,GDLA));
	  for ( ; gdl!=NULL; gdl=Next_list(gdl) ) {
	    gd = (PGateDecTyp)LookInfo_list(gdl);
	    gl = gd->agl;
	    for ( ; gl!=NULL ; gl=Next_list(gl) )
	      update_hk((unsigned)LookInfo_list(gl));
	    update_hk((unsigned)(gd->fgs[0]));
	  }
	  beh = LookArgB(beh,1);
	  break;

	case InterleavedC:
	  update_hk((unsigned)(type+n));
	  BHK( LookArgB(beh,1), n );
	  beh = LookArgB(beh,2);
	  break;

	case ContSetC:
	  update_hk((unsigned)(type+n));
	  itcl = (ITContListTyp)LookAInfo(LookA(beh,ITCLA));
	  for ( ; itcl!=NULL; itcl=Next_list(itcl) ){
	    itc = (PITContTyp)LookInfo_list(itcl);
	    update_hk((unsigned)LookNameB(itc->label));
	  }
	  beh = NULL;
	  break;

	case TerminationC:
	  update_hk((unsigned)(type+n));
	  update_hk((unsigned)LookNameB(beh));
	  el = (ExprListTyp)LookAInfo(LookA(beh,ELA));
	  for ( ; el!=NULL; el=Next_list(el) )
	    ExprHashKey((ExprTyp)LookInfo_list(el));
	  beh = NULL;
	  break;

	default :
	  Error("Unexpected Cell Type");
	  break;
	}
  }
}

/*----------------------------------------------------------------*/

/* BehHashKey
 * Calculates the hash key of the behaviour beh.
 */
int BehHashKey( beh )
     BehTyp beh;
{
  hk_value = 123532;
  BHK(beh,HASHMAXLEVEL);
  return hk_value;
}



/******************************************************************
 *                                                                *
 *      Behaviour HashTable Management                            *
 *                                                                *
 *******************************************************************/


static boolean CompareBehaviorBH( b1, b2 )
     BehTyp b1,b2;
{
  boolean equal;

  if ( LookNameB(b1)!=LookNameB(b2) )
    return FALSE;
  Init_VPTable();
  equal = Comp_Beh( LookB2(b1), LookB2(b2) );

  return equal;
}

/*----------------------------------------------------------------*/

static void PrintHBD( pstr , bd )
     void (*pstr)();
     BehTyp bd;
{
  pstr("\n Behaviour : ");
  PrintInt(pstr,LookNameB(bd));
  pstr(" . B2 = \n");
  PrintBeh(LookArgB(bd,2),-1,NO_PROC,FALSE,"",pstr,TRUE,FALSE);
}

/*----------------------------------------------------------------*/

/* InitHashBehDef
 * Inits the behaviour hash table.
 * It must be called whenever an expansion with duplicated behaviour
 * size is the number of slots.
 * detection is going to be performed.
 * If owner is TRUE the behaviours in the tables are owned by the hash table
 *    so that they will be freed with FreeB when FreeHashBehDef is called.
 * otherwise
 *    no behaviour release will be done.
 */
BehHashTabTyp InitHashBehDef( size, owner )
     int     size;
     boolean owner;
{
  if (owner)
    return (BehHashTabTyp)Create_HT( size, FreeB,
				    LookNameB,CompareBehaviorBH, PrintHBD );
  else
    return (BehHashTabTyp)Create_HT( size, (void(*)())NULL,
				    LookNameB,CompareBehaviorBH, PrintHBD );
}

/*----------------------------------------------------------------*/

/* FreeHashBehDef
 * Frees the hash table.
 * It must be called when the expansion has finished.
 */
void FreeHashBehDef( bhtd )
     BehHashTabTyp bhtd;
{
  Free_HT( bhtd );
}

/*----------------------------------------------------------------*/

/* CopyVar
 * copies a variable cell
 */
static ExprTyp CopyVar( v )
     ExprTyp v;
{
  return ShareE(MakeE(LookNameE(v),VariableC));
}

/*----------------------------------------------------------------*/

/* GetHashBehDef
 * Looks for a duplicated behaviour of beh.
 * If it does exist then returns the duplicated behaviour and the
 * expression and variable list needed to make the instantiations.
 * If beh has not a duplicated behaviour it is inserted in the table
 * and NULL is returned.
 */
BehTyp GetHashBehDef( bhtd, beh, dblPt )
     BehHashTabTyp bhtd;
     BehTyp beh;
     PDupBehListsTyp dblPt;
{
  BehTyp dupBeh;

  LASSERT( LookTypeB(beh)==BehaviourC );

  PutNameB( beh, (DescriptorTyp)BehHashKey(LookArgB(beh,2)) );

  dupBeh = (BehTyp)LookFor_HT( bhtd, (DataHashTyp)beh );
  if ( dupBeh != NULL ) {
    dblPt->DupBehActEL1 = Mk_VPTable_VL1();       /* from beh */
    dblPt->DupBehActEL2 = Mk_VPTable_VL2();       /* from the Hash Table */
    dblPt->DupBehForVL  = Copy_list(dblPt->DupBehActEL2,
				    (DataListTyp(*)()) CopyVar);
  }
  else {
    Insert_HT( bhtd, (DataHashTyp)beh );
  }
  Init_VPTable();

  return dupBeh;
}

/*----------------------------------------------------------------*/

/* PrintHashBehDef
 * Prints the duplicated behaviour hash table.
 */
void PrintHashBehDef( bhtd )
     BehHashTabTyp bhtd;
{
  Print_HT( bhtd, printMsgs );
}

/*----------------------------------------------------------------*/

/* StatHashBehDef
 * Displays statistics about table occupation and collisions.
 */
void StatHashBehDef( bhtd )
     BehHashTabTyp bhtd;
{
  char buff[128];

  int slots,total;
  Stat_HT( bhtd, &slots, &total );
  (void)sprintf(buff,"\nHash statistics ( beh = %d, collision = ",total);
  printMsgs(buff);
  if (total==0)
    printMsgs("0 % )\n");
  else {
    (void)sprintf(buff,"%2.2f %% )\n",100-(100.0*(float)slots/total));
    printMsgs(buff);
  }
}

/*----------------------------------------------------------------*/




