build_graph.c

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

  if ( op_node->unactivated_effects == NULL ) {
    return TRUE;
  } else {
    return FALSE;
  }

}


Bool apply_effect( int time, Effect *ef, OpNode *op_node )

{

  Integers *i;
  BitVector *cond_pos_exclusives, *cond_neg_exclusives;
  BitVector *a, *b;
  EfNode *ef_node;
  FtNode *ft_node;
  int r;

  if ( !get_them_non_exclusive( time, 
				ef->p_conds, ef->n_conds,
				&cond_pos_exclusives, &cond_neg_exclusives ) ) {
    return FALSE;
  }

  a = cond_pos_exclusives;
  b = op_node->pos_precond_vector;
  for ( r = 0; r < gft_vector_length; r++ ) {
    if ( a[r] & b[r] ) {
      free( cond_pos_exclusives );
      free( cond_neg_exclusives );
      return FALSE;
    }
  }
  a = cond_neg_exclusives;
  b = op_node->neg_precond_vector;
  for ( r = 0; r < gft_vector_length; r++ ) {
    if ( a[r] & b[r] ) {
      free( cond_pos_exclusives );
      free( cond_neg_exclusives );
      return FALSE;
    }
  }

  ef_node = new_ef_node( time, op_node,
			 ef->p_effects->vector, ef->n_effects->vector );
  ef_node->info_at[time]->cond_pos_exclusives = cond_pos_exclusives;
  ef_node->info_at[time]->cond_neg_exclusives = cond_neg_exclusives;
  for ( i=ef->p_conds->indices; i; i=i->next ) {
    insert_ft_edge( &(ef_node->conditions), gft_table[i->index] );
  }
  for ( i=ef->n_conds->indices; i; i=i->next ) {
    insert_ft_edge( &(ef_node->conditions), gft_table[NEG_ADR( i->index )] );
  }
  ef_node->next = op_node->conditionals;
  op_node->conditionals = ef_node;
    
  for ( i = ef->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 = ef->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 );
  }

  return TRUE;

}











/***************************************
 * CODE FOR APPLYING POTENTIAL EFFECTS *
 ***************************************/










void insert_potential_effects( int time )

{

  OpNode *op, *tmp_op, *prev_op;
  Bool hit = TRUE;

  while ( hit ) {
    hit = FALSE;

    op = gops_with_unactivated_effects_pointer;
    while ( op && apply_potential_effects( time, op, &hit ) ) {
      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_potential_effects( time, op, &hit ) ) {
	prev_op->thread = op->thread;
	tmp_op = op;
	op = op->thread;
	tmp_op->thread = NULL;
      } else {
	prev_op = prev_op->thread;
	op = op->thread;
      }
    }

    if ( !hit ) break;
  }

}


Bool apply_potential_effects( int time, OpNode *op_node, Bool *hit ) 

{

  Effect *j, *tmp, *prev;


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

  if ( op_node->unactivated_effects == NULL ) {
    return TRUE;
  } else {
    return FALSE;
  }

}


Bool apply_potential_effect( int time, Effect *ef, OpNode *op_node )

{

  Integers *i;
  EfNode *ef_node;
  FtNode *ft_node, *ft;

  if ( !potential_applicable( time, ef, op_node ) ) {
    return FALSE;
  }

  ef_node = new_ef_node( time, op_node,
			 ef->p_effects->vector, ef->n_effects->vector );
  ef_node->info_at[time]->is_dummy = TRUE;
  /* gesamtexclusives bleiben leer (cond_pos/neg_exclusives);
   * koennen fuer dummys nicht besonders sinnvoll angegeben werden...
   * (siehe kommentar dazu in search_plan.c)
   *
   * NACHSCHAUEN: KANN DAS ZU PROBLEMEN FUEHREN ?
   *              antwort: NEIN ! (?): falls dieser vektor nicht da ist, 
   *                       wird er in der suche sowieso berechnet.
   */
  for ( i=ef->p_conds->indices; i; i=i->next ) {
    ft = gft_table[i->index];
    insert_ft_edge( &(ef_node->conditions), ft );
    if ( !ft->info_at[time] ) {
      ft->info_at[time] = new_ft_level_info( ft );
      /* diese information wird in suche nicht verwendet!!!
       * ---> aber bei integrate potential effects
       * ---> koennte man auch anders machen und diese info ganz weglassen.
       * ...allerdings wohl zum debuggen ganz praktisch
       * und aufwand vernachlaessigbar, also was solls...
       *
       * ANMERKUNG: exclusivitaet von dummys wird nach
       * integration nachgeregelt... solange sind lediglich
       * die contradicting facts exclusiv.
       */
      ft->info_at[time]->is_dummy = TRUE;
    }
  }
  for ( i=ef->n_conds->indices; i; i=i->next ) {
    ft = gft_table[NEG_ADR( i->index )];
    insert_ft_edge( &(ef_node->conditions), ft );
    if ( !ft->info_at[time] ) {
      ft->info_at[time] = new_ft_level_info( ft );
      ft->info_at[time]->is_dummy = TRUE;
    }
  }
  ef_node->next = op_node->conditionals;
  op_node->conditionals = ef_node;
    
  for ( i = ef->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, TRUE );
      ft_node->info_at[time+1]->is_dummy = TRUE;
      gft_table[i->index] = ft_node;
      /* fact wird noch NICHT in globale liste gestellt, fuehrt eine
       * schattenexistenz mit info_at und contradict exclusives ohne
       * adders info bis es zum ersten mal wirklich da ist durch
       * regulaeres eintreten des entsprechenden efekts.
       */
      /* vector wird NICHT mit fact - bit ge ort! dadurch in 
       * get..non_exclusive funktionen fact als nicht da
       * interpretiert!! WICHTIG!!
       */
      /* kann man hier noch etwas ueber exclusives sagen...?
       *
       * ja, und zwar dass das fact die exclusives kriegt, die es
       * spaeter als richtiges fact haben wird!
       */
    }
    insert_ef_edge( &(ft_node->adders), ef_node );
    insert_ft_edge( &(ef_node->effects), ft_node );
  }

  for ( i = ef->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, TRUE );
      ft_node->info_at[time+1]->is_dummy = TRUE;
      gft_table[NEG_ADR( i->index )] = ft_node;
      /* siehe oben
       */
    }
    insert_ef_edge( &(ft_node->adders), ef_node );
    insert_ft_edge( &(ef_node->effects), ft_node );
  }
  
  return TRUE;

}


Bool potential_applicable( int time, Effect *ef, OpNode *op_node )

{

  static FtArray all_fts, dum_fts;
  int alln = 0, dumn = 0;

  Integers *in;
  FtEdge *jn;
  FtNode *ft;
  OpNode *op_node2;
  FtLevelInfo *info;
  BitVector *vec;
  EfEdge *i_ef;
  int i, j;

  for ( in = ef->p_conds->indices; in; in = in->next ) {
    ft = gft_table[in->index];
    if ( !ft ) {
      return FALSE;
    }
    if ( alln == ARRAY_SIZE ) {
      printf( "\n\nipp: increase ARRAY_SIZE( preset value: %d )", ARRAY_SIZE );
      exit( 1 );
    }
    all_fts[alln++] = ft;
    if ( !ft->info_at[time] ||
	 ft->info_at[time]->is_dummy ) {
      dum_fts[dumn++] = ft;
    }
  }
  for ( in = ef->n_conds->indices; in; in = in->next ) {
    ft = gft_table[NEG_ADR( in->index )];
    if ( !ft ) {
      return FALSE;
    }
    if ( alln == ARRAY_SIZE ) {
      printf( "\n\nipp: increase ARRAY_SIZE( preset value: %d )", ARRAY_SIZE );
      exit( 1 );
    }
    all_fts[alln++] = ft;
    if ( !ft->info_at[time] ||
	 ft->info_at[time]->is_dummy ) {
      dum_fts[dumn++] = ft;
    }
  }

  for ( i=0; i<alln; i++ ) {
    /* uebernehme fuer dummys exclusions von vorkommen auf naechstem level;
     * das kann entweder contradict sein, falls fact auf time+1 dummy
     * oder aber volle excl, falls fact auf time+1 echt.
     * hier greifen wir etwas vor: ist time+1 echt, so werden spaeter
     * fuer dummy time sowieso die time+1 excl eingetragen.
     */
    if ( !all_fts[i]->info_at[time] ||
	 all_fts[i]->info_at[time]->is_dummy ) {
      info = all_fts[i]->info_at[time+1];
    } else {
      info = all_fts[i]->info_at[time];
    }
    /* info = all_fts[i]->info_at[time] ? all_fts[i]->info_at[time] :
       all_fts[i]->info_at[time+1]; */

    for ( j = i+1; j<alln; j++ ) {
      vec = all_fts[j]->positive ? info->pos_exclusives : info->neg_exclusives;
      if ( vec[all_fts[j]->uid_block] & all_fts[j]->uid_mask ) {
	return FALSE;
      }
    }

    for ( jn = op_node->preconds; jn; jn = jn->next ) {
      vec = jn->ft->positive ? info->pos_exclusives : info->neg_exclusives;
      if ( vec[jn->ft->uid_block] & jn->ft->uid_mask ) {
	return FALSE;
      }
    }
  }

  /* gecheckt ist jetzt: - alle conditions sind zumindest im graph
   *                       (d.h. dummy oder aufm naechsten level)
   *                     - alle conditions sind zumindest nicht exclusiv
   *                       voneinander und von preconds
   *                       ACHTUNG bei facts, die auf time noch nicht da sind:
   *                               solche sind auf time + 1 jedenfalls da und
   *                               auf time mindestens so exclusive wie auf time+1
   *                       (dummys die auf time da sind, haben nur die contradicting
   *                        exclusivitaet)(genauso wie dummys auf time+1)
   */

  
  /* jetzt checken, ob dummy facts zusammen erreicht werden koennen!
   * ( bei verwendung von op_node )
   */

  for ( i=0; i<dumn; i++ ) {
    for ( i_ef = dum_fts[i]->adders; i_ef; i_ef = i_ef->next ) {
      op_node2 = i_ef->ef->op;
      if ( ( op_node->info_at[time]->exclusives[op_node2->uid_block] &
	     op_node2->uid_mask ) == 0 ) {
	break;
      }
    }
    if ( !i_ef ) return FALSE;
  }

  return TRUE;

}





void integrate_potential_effects( int time )

{

  OpNode *op;
  EfNode *ef;
  FtEdge *i, *j;

  for ( op = gall_ops_pointer; op; op = op->next ) {

    for ( ef = op->conditionals; ef; ef = ef->next ) {

      if ( !ef->info_at[time]->is_dummy ) continue;

      /* eine etwas ineffektive methode, die nicht integrierten
       * potentiellen effekte zu finden, besser waere eine
       * globale liste der entsprechenden effekte
       * mit dem ueblichen rausstreichverfahren...
       *
       * INEFFIZIENT, vielleicht spaeter mal aendern.
       */
      for ( i = ef->conditions; i; i = i->next ) {
	if ( i->ft->info_at[time]->is_dummy ) break;
      }
      if ( i ) continue;

      for ( i = ef->conditions; i; i = i->next ) {
	for ( j = i->next; j; j = j->next ) {
	  if ( ARE_MUTEX_FTS( time, i->ft, j->ft ) ) break;
	}
	if ( j ) break;

	/* conditions, die frueher dummy waren, koennen
	 * exclusiv von den preconds sein!
	 *
	 * glaub ich jez eigentlich nicht, aber riskieren wollen
	 * wers mal net. SPAETER MAL TESTEN!
	 */
	for ( j = op->preconds; j; j = j->next ) {
	  if ( ARE_MUTEX_FTS( time, i->ft, j->ft ) ) break;
	}
	if ( j ) break;
      }
      if ( i ) continue;

      /* effekt kann integriert werden!
       */
      ef->info_at[time]->is_dummy = FALSE;
      for ( i = ef->effects; i; i = i->next ) {
	/* JETZT ERST WIRD FACT VON get...non_exclusive FUNKTIONEN
	 * ANERKANNT ---> KANN IN PRECONDS VERWENDET WERDEN.
	 */
	if ( i->ft->positive ) {
	  (gpos_facts_vector_at[time+1])[i->ft->uid_block] |= i->ft->uid_mask;
	} else {
	  (gneg_facts_vector_at[time+1])[i->ft->uid_block] |= i->ft->uid_mask;
	}
	/* jetzt wirds auch von dieser funktion anerkannt...
	 * prinzipiell wuerde eine der beiden informationen schon ausreichen.
	 */
	if ( i->ft->info_at[time+1]->is_dummy ) {
	  i->ft->next = gall_fts_pointer;
	  gall_fts_pointer = i->ft;
	  i->ft->info_at[time+1]->is_dummy = FALSE;
	  gfacts_count++;
	}
      }

    }
  }

}









/********************************************
 * HELPERS HANDLING CONDITIONS AND PRECONDS *
 ********************************************/