build_graph.c

intel ipp4.1性能库的一些例子。

/*********************************************************************
 * File: build_graph.c
 * Description: main routines for building the graph
 *
 * Author: Joerg Hoffmann 1998
 *
 *********************************************************************/ 
/*********************************************************************
 * (C) Copyright 1998 Albert Ludwigs University Freiburg
 *     Institute of Computer Science
 *
 * All rights reserved. Use of this software is permitted for 
 * non-commercial research purposes, and it may be copied only 
 * for that use.  All copies must include this copyright message.
 * This software is made available AS IS, and neither the authors
 * nor the  Albert Ludwigs University Freiburg make any warranty
 * about the software or its performance. 
 *********************************************************************/
/*********************************************************************
 *
 * NOTE: the commentaries in this file, sparse as they are, are all
 *       in German, cause these are thoughts that I had while working
 *       on some really tedious parts of the code (potential effects...)
 * 
 *       If you have problems understanding the code (like I do when I have
 *       a look at it now), contact me at:
 *       
 *       [e-mail]
 *
 *       and I'll be happy to answer your questions, if I can...
 *
 **********************************************************************/








#include "ipp.h"

#include "output.h"
#include "utilities.h"
#include "memory.h"

#include "build_graph.h"
#include "exclusions.h"









/**********************************
 * INITIAL GRAPH BUILDING PROCESS *
 **********************************/








Bool build_graph( int *min_time )

{

  int time = 0, j;
  Bool reached_goals = FALSE, first = TRUE;
  Integers *i;
  FtNode *ft;

  gft_table = ( FtNode_pointer * ) calloc( gnum_relevant_facts * 2, sizeof( FtNode_pointer ) );
  CHECK_PTR(gft_table);
#ifdef MEMORY_INFO
  gmemory += gnum_relevant_facts * 2 * sizeof( FtNode_pointer );
#endif
  for ( j = 0; j<2*gnum_relevant_facts; j++ ) gft_table[j] = NULL;
  gpos_facts_vector_at[0] = new_bit_vector( gft_vector_length );
  gneg_facts_vector_at[0] = new_bit_vector( gft_vector_length );

  for ( i = gbit_initial_state->positive->indices; i; i = i->next ) {
    ft = new_ft_node( 0, i->index, TRUE, FALSE );
    gft_table[i->index] = ft;
    ft->next = gall_fts_pointer;
    gall_fts_pointer = ft;
    (gpos_facts_vector_at[0])[ft->uid_block] |= ft->uid_mask;
  }

  for ( i = gbit_initial_state->negative->indices; i; i = i->next ) {
    ft = new_ft_node( 0, i->index, FALSE, FALSE );
    gft_table[NEG_ADR( i->index )] = ft;
    ft->next = gall_fts_pointer;
    gall_fts_pointer = ft;
    (gneg_facts_vector_at[0])[ft->uid_block] |= ft->uid_mask;
  }
  free_fact_info_pair( gbit_initial_state );

  if ( gcmd_line.display_info ) {
    fprintf( OUT, "time: %3d, %5d facts and %7d exclusive pairs (%5d, %7d positives)\n",
	     time, gfacts_count, gexclusions_count, gprint_ftnum, gprint_exnum );
  }

  for( ; time < *min_time; time++ ) {
    if ( first ) {
      reached_goals = are_there_non_exclusive( time,
					       gbit_goal_state->positive,
					       gbit_goal_state->negative );
      if ( reached_goals ) {
	if ( gcmd_line.display_info ) {
	  fprintf( OUT, "\ngoals first reachable in %d time steps\n\n", time);
          first = FALSE;
	}
      }
    }
    if ( gsame_as_prev_flag ) break;
    build_graph_evolution_step();
  }
  
  for( ; time < MAX_PLAN; time++ ) {
    reached_goals = are_there_non_exclusive( time,
					     gbit_goal_state->positive,
					     gbit_goal_state->negative );
    if ( reached_goals ) {
      if ( gcmd_line.display_info && time > 0 && first ) {
        fprintf( OUT, "\ngoals first reachable in %d time steps\n\n", time);
      }
      break;
    }
    if ( gsame_as_prev_flag ) break;
    build_graph_evolution_step();
  }

  *min_time = time;
  return reached_goals;

}









/*******************************************************
 * MAIN FUNCTION: ADD AN ADDTIONAL LAYER INFO TO GRAPH *
 *******************************************************/









void build_graph_evolution_step( void )

{

  static int time = 0;
  int facts_count = gfacts_count, exclusions_count = gexclusions_count;
  BitOperator *o, *prev, *tmp;
  OpNode *op, *prev_op, *tmp_op, *i;
  EfNode *j;
  FtNode *l;
  int k;

  struct tms start, end;

  /* when replanning due to rifo failure, set time back to zero 
     in first function call */
  if ( new_plan )
    {
      time = 0;
      new_plan = FALSE;
    }

  gpos_facts_vector_at[time+1] = copy_bit_vector( gpos_facts_vector_at[time],
						  gft_vector_length );
  gneg_facts_vector_at[time+1] = copy_bit_vector( gneg_facts_vector_at[time],
						  gft_vector_length );

  for ( i = gall_ops_pointer; i; i = i->next ) {
    i->info_at[time] = new_op_level_info();
    i->unconditional->info_at[time] = new_ef_level_info();
    for ( j = i->conditionals; j; j = j->next ) {
      j->info_at[time] = new_ef_level_info();
      if ( j->info_at[time-1]->is_dummy ) {
	/* effekte bleiben erstmal dummy...
	 * spaeter dann nachschauen, ob sie doch eingezogen werden koennen.
	 *
	 * ( kann sein, dass effekt erst drei runden spaeter nicht-dummy wird )
	 */ 
	j->info_at[time]->is_dummy = TRUE;
      }
    }
  }

  /* eigentlich ineffizient; unterscheidung wegen dummys noetig, die beim
   * ersterzeugen NICHT in die globale liste aufgenommen werden.
   *
   * EFFIZIENTER: extra verkettung fuer dummys erstellen.
   */

  for ( k=0; k<2*gnum_relevant_facts; k++ ) {
    if ( (l = gft_table[k]) == NULL ) continue;

    l->info_at[time+1] = new_ft_level_info( l );
    if ( l->info_at[time]->is_dummy ) {
      /* siehe oben...
       *
       * facts, die hier SO markiert sind, sind NUR DIEJENIGEN, DIE VON
       * EINEM DUMMY EFFEKT GEADDET wurden. also einfach markierung wieder
       * umstellen, sobald der entsprechende dummy effekt richtig einziehbar
       * wird!
       */
      l->info_at[time+1]->is_dummy = TRUE;
    }
  }


  gprev_level_ops_pointer = gall_ops_pointer;

  apply_noops( time );

  gprev_level_fts_pointer = gall_fts_pointer;

  op = gops_with_unactivated_effects_pointer;
  while ( op && apply_all_effects( time, op ) ) {
    tmp_op = op;
    op = op->thread;
    tmp_op->thread = NULL;
  }
  gops_with_unactivated_effects_pointer = op;
  prev_op = op;
  if ( op ) op = op->thread;
  while ( op ) {
    if ( apply_all_effects( time, op ) ) {
      prev_op->thread = op->thread;
      tmp_op = op;
      op = op->thread;
      tmp_op->thread = NULL;
    } else {
      prev_op = prev_op->thread;
      op = op->thread;
    }
  }

  o = gbit_operators;
  while ( o && apply_operator( time, o ) ) {
    tmp = o;
    o = o->next;
    free_partial_operator( tmp );
  }
  gbit_operators = o;
  prev = o;
  if ( o ) o = o->next;
  while ( o ) {
    if ( apply_operator( time, o ) ) {
      prev->next = o->next;
      tmp = o;
      o = o->next;
      free_partial_operator( tmp );
    } else {
      prev = prev->next;
      o = o->next;
    }
  }
  gop_vector_length_at[time] = ( ( int ) gops_count / gcword_size );
  if ( ( gops_count % gcword_size ) > 0 ) gop_vector_length_at[time]++;

  /* bei allen anwendbaren ops nachschauen, ob die dummy effekte
   * inzwischen einziehbar sind!
   *
   * ja->markierungen des effekts und der geaddeten facts umstellen!
   */
  integrate_potential_effects( time );

  times(&start);
  find_mutex_ops( time );
  find_mutex_facts( time + 1 );
  times(&end);
  TIME( gexcl_time );

  insert_potential_effects( time );
  
  if ( facts_count == gfacts_count &&
       exclusions_count == gexclusions_count ) {
    gsame_as_prev_flag = TRUE;
    if ( gcmd_line.display_info ) 
      fprintf( OUT, "\ngraph has leveled off at time step %d\n\n", time+1 );
    gfirst_full_time = time;
  }

  if ( gcmd_line.display_info ) {
    fprintf( OUT, "           %5d ops   and %7d exclusive pairs\n",
	     gops_count, gops_exclusions_count );
    fprintf( OUT, "time: %3d, %5d facts and %7d exclusive pairs (%5d, %7d positives)\n",
	     time+1, gfacts_count, gexclusions_count, gprint_ftnum, gprint_exnum );
  }

  time++;
  
}









/********************************************************************
 * GRAPH BUILDING FUNCTIONS; OVERSEEN BY BUILD_GRAPH_EVOLUTION_STEP *
 ********************************************************************/










void apply_noops( int time )

{

  FtNode *ft;
  BitVector *a, *b;
  OpNode *noop;
  EfNode *tmp;
  
  for ( ft = gall_fts_pointer; ft != gprev_level_fts_pointer; ft = ft->next ) {

    a = new_bit_vector( gft_vector_length );
    b = new_bit_vector( gft_vector_length );
    if ( ft->positive ) {
      a[ft->uid_block] |= ft->uid_mask;
    } else {
      b[ft->uid_block] |= ft->uid_mask;
    }
    noop = new_op_node( time, NULL, TRUE, a, b );
    insert_ft_edge( &(noop->preconds), ft );
    tmp = new_ef_node( time, noop, a, b );
    tmp->info_at[time]->cond_pos_exclusives = ft->info_at[time]->pos_exclusives;
    tmp->info_at[time]->cond_neg_exclusives = ft->info_at[time]->neg_exclusives;
    noop->unconditional = tmp;
    noop->next = gall_ops_pointer;
    gall_ops_pointer = noop;

    ft->noop = noop;

  }

}


Bool apply_operator( int time, BitOperator *op )

{

  OpNode *op_node;
  EfNode *ef_node;
  FtNode *ft_node;
  BitVector *precond_pos_exclusives, *precond_neg_exclusives;
  Integers *i;
  int j;

  if ( !get_them_non_exclusive( time, 
				op->p_preconds,	op->n_preconds,
				&precond_pos_exclusives, &precond_neg_exclusives ) ) {
    return FALSE;
  }


  op_node = new_op_node( time, op->name, FALSE,
			 op->p_preconds->vector,
			 op->n_preconds->vector );
  op_node->num_vars = op->num_vars;
  for ( j=0; j<MAX_VARS; j++ ) {
    op_node->inst_table[j] = op->inst_table[j];
  }
  op_node->next = gall_ops_pointer;
  gall_ops_pointer = op_node;

  for ( i=op->p_preconds->indices; i; i=i->next ) {
    insert_ft_edge( &(op_node->preconds), gft_table[i->index] );
    insert_op_edge( &(gft_table[i->index]->preconds), op_node );
  }
  for ( i=op->n_preconds->indices; i; i=i->next ) {
    insert_ft_edge( &(op_node->preconds), gft_table[NEG_ADR( i->index )] );
    insert_op_edge( &(gft_table[NEG_ADR( i->index )]->preconds), op_node );
  }

  ef_node = new_ef_node( time, op_node,
			 (op->unconditional ? op->unconditional->p_effects->vector :
			  new_bit_vector( gft_vector_length ) ),
			 (op->unconditional ? op->unconditional->n_effects->vector :
			  new_bit_vector( gft_vector_length ) ) );
  ef_node->info_at[time]->cond_pos_exclusives = precond_pos_exclusives;
  ef_node->info_at[time]->cond_neg_exclusives = precond_neg_exclusives;    
  op_node->unconditional = ef_node;  
  if ( op->unconditional ) {
    
    for ( i = op->unconditional->p_effects->indices; i; i=i->next ) {
      if ( (ft_node = gft_table[i->index]) == NULL ) {
	ft_node = new_ft_node( time+1, i->index, TRUE, FALSE );
	ft_node->next = gall_fts_pointer;
	gall_fts_pointer = ft_node;
	gft_table[i->index] = ft_node;
	(gpos_facts_vector_at[time+1])[ft_node->uid_block] |= ft_node->uid_mask;
      }
      insert_ef_edge( &(ft_node->adders), ef_node );
      insert_ft_edge( &(ef_node->effects), ft_node );
    }

    for ( i = op->unconditional->n_effects->indices; i; i=i->next ) {
      if ( (ft_node = gft_table[NEG_ADR( i->index )]) == NULL ) {
	ft_node = new_ft_node( time+1, i->index, FALSE, FALSE );
	ft_node->next = gall_fts_pointer;
	gall_fts_pointer = ft_node;
	gft_table[NEG_ADR( i->index )] = ft_node;
	(gneg_facts_vector_at[time+1])[ft_node->uid_block] |= ft_node->uid_mask;
      }
      insert_ef_edge( &(ft_node->adders), ef_node );
      insert_ft_edge( &(ef_node->effects), ft_node );
    }
  }

  op_node->unactivated_effects = op->conditionals;
  if ( !apply_all_effects( time, op_node ) ) {
    op_node->thread = gops_with_unactivated_effects_pointer;
    gops_with_unactivated_effects_pointer = op_node;
  }

  return TRUE;

}


Bool apply_all_effects( int time, OpNode *op_node ) 

{

  Effect *j, *tmp, *prev;


  /* FEHLER!!
   *
   * ...genau ueberpruefen, was ge freet werden darf!!
   */
  j = op_node->unactivated_effects;
  while ( j && apply_effect( time, j, op_node ) ) {
    tmp = j;
    j = j->next;
    if ( 1 ) free_partial_effect( tmp );
  }
  op_node->unactivated_effects = j;
  prev = j;
  if ( j ) j = j->next;
  while ( j ) {
    if ( apply_effect( time, j, op_node ) ) {
      prev->next = j->next;
      tmp = j;
      j = j->next;
      if ( 1 ) free_partial_effect( tmp );
    } else {
      prev = prev->next;
      j = j->next;
    }
  }