src/xbt/automaton/automaton.c

   1 /* automaton - representation of büchi automaton */
   2
   3 /* Copyright (c) 2011-2014. The SimGrid Team.
   4  * All rights reserved.                                                     */
   5
   6 /* This program is free software; you can redistribute it and/or modify it
   7  * under the terms of the license (GNU LGPL) which comes with this package. */
   8
   9 #include "xbt/automaton.h"
  10 #include <stdio.h> /* printf */
  11
  12 struct xbt_automaton_propositional_symbol{
  13   char* pred;
  14   /** Callback used to evaluate the value of the symbol */
  15   int (*function)(void*);
  16   /** Additional data for the callback.
  17       Alternatively it can be used as a pointer to the data. */
  18   void* data;
  19   //** Optional callback used to free the data field */
  20   void (*free_function)(void*);
  21 };
  22
  23 int xbt_automaton_propositional_symbol_evaluate(xbt_automaton_propositional_symbol_t symbol)
  24 {
  25   if (symbol->function)
  26     return (symbol->function)(symbol->data);
  27   else
  28     return *(int*) symbol->data;
  29 }
  30
  31 char* xbt_automaton_propositional_symbol_get_name(xbt_automaton_propositional_symbol_t symbol)
  32 {
  33   return symbol->pred;
  34 }
  35
  36 xbt_automaton_t xbt_automaton_new(){
  37   xbt_automaton_t automaton = NULL;
  38   automaton = xbt_new0(struct xbt_automaton, 1);
  39   automaton->states = xbt_dynar_new(sizeof(xbt_automaton_state_t), xbt_automaton_state_free_voidp);
  40   automaton->transitions = xbt_dynar_new(sizeof(xbt_automaton_transition_t), xbt_automaton_transition_free_voidp);
  41   automaton->propositional_symbols = xbt_dynar_new(sizeof(xbt_automaton_propositional_symbol_t), xbt_automaton_propositional_symbol_free_voidp);
  42   return automaton;
  43 }
  44
  45 xbt_automaton_state_t xbt_automaton_state_new(xbt_automaton_t a, int type, char* id){
  46   xbt_automaton_state_t state = NULL;
  47   state = xbt_new0(struct xbt_automaton_state, 1);
  48   state->type = type;
  49   state->id = strdup(id);
  50   state->in = xbt_dynar_new(sizeof(xbt_automaton_transition_t), xbt_automaton_transition_free_voidp);
  51   state->out = xbt_dynar_new(sizeof(xbt_automaton_transition_t), xbt_automaton_transition_free_voidp);
  52   xbt_dynar_push(a->states, &state);
  53   return state;
  54 }
  55
  56 xbt_automaton_transition_t xbt_automaton_transition_new(xbt_automaton_t a, xbt_automaton_state_t src, xbt_automaton_state_t dst, xbt_automaton_exp_label_t label){
  57   xbt_automaton_transition_t transition = NULL;
  58   transition = xbt_new0(struct xbt_automaton_transition, 1);
  59   if(src != NULL){
  60     xbt_dynar_push(src->out, &transition);
  61     transition->src = src;
  62   }
  63   if(dst != NULL){
  64     xbt_dynar_push(dst->in, &transition);
  65     transition->dst = dst;
  66   }
  67   transition->label = label;
  68   xbt_dynar_push(a->transitions, &transition);
  69   return transition;
  70 }
  71
  72 xbt_automaton_exp_label_t xbt_automaton_exp_label_new(int type, ...){
  73   xbt_automaton_exp_label_t label = NULL;
  74   label = xbt_new0(struct xbt_automaton_exp_label, 1);
  75   label->type = type;
  76
  77   va_list ap;
  78   va_start(ap, type);
  79   switch(type){
  80   case 0 : {
  81     xbt_automaton_exp_label_t left = va_arg(ap, xbt_automaton_exp_label_t);
  82     xbt_automaton_exp_label_t right = va_arg(ap, xbt_automaton_exp_label_t);
  83     label->u.or_and.left_exp = left;
  84     label->u.or_and.right_exp = right;
  85     break;
  86   }
  87   case 1 : {
  88     xbt_automaton_exp_label_t left = va_arg(ap, xbt_automaton_exp_label_t);
  89     xbt_automaton_exp_label_t right = va_arg(ap, xbt_automaton_exp_label_t);
  90     label->u.or_and.left_exp = left;
  91     label->u.or_and.right_exp = right;
  92     break;
  93   }
  94   case 2 : {
  95     xbt_automaton_exp_label_t exp_not = va_arg(ap, xbt_automaton_exp_label_t);
  96     label->u.exp_not = exp_not;
  97     break;
  98   }
  99   case 3 :{
 100     char* p = va_arg(ap, char*);
 101     label->u.predicat = strdup(p);
 102     break;
 103   }
 104   }
 105   va_end(ap);
 106   return label;
 107 }
 108
 109
 110 xbt_dynar_t xbt_automaton_get_states(xbt_automaton_t a){
 111   return a->states;
 112 }
 113
 114 xbt_dynar_t xbt_automaton_get_transitions(xbt_automaton_t a){
 115   return a->transitions;
 116 }
 117
 118 xbt_automaton_transition_t xbt_automaton_get_transition(xbt_automaton_t a, xbt_automaton_state_t src, xbt_automaton_state_t dst){
 119   xbt_automaton_transition_t transition;
 120   unsigned int cursor;
 121   xbt_dynar_foreach(src->out, cursor, transition){
 122     if((transition->src == src) && (transition->dst == dst))
 123       return transition;
 124   }
 125   return NULL;
 126 }
 127
 128 xbt_automaton_state_t xbt_automaton_transition_get_source(xbt_automaton_transition_t t){
 129   return t->src;
 130 }
 131
 132 xbt_automaton_state_t xbt_automaton_transition_get_destination(xbt_automaton_transition_t t){
 133   return t->dst;
 134 }
 135
 136 void xbt_automaton_transition_set_source(xbt_automaton_transition_t t, xbt_automaton_state_t src){
 137   t->src = src;
 138   xbt_dynar_push(src->out,&t);
 139 }
 140
 141 void xbt_automaton_transition_set_destination(xbt_automaton_transition_t t, xbt_automaton_state_t dst){
 142   t->dst = dst;
 143   xbt_dynar_push(dst->in,&t);
 144 }
 145
 146 xbt_dynar_t xbt_automaton_state_get_out_transitions(xbt_automaton_state_t s){
 147   return s->out;
 148 }
 149
 150 xbt_dynar_t xbt_automaton_state_get_in_transitions(xbt_automaton_state_t s){
 151   return s->in;
 152 }
 153
 154 xbt_automaton_state_t xbt_automaton_state_exists(xbt_automaton_t a, char *id){
 155   xbt_automaton_state_t state = NULL;
 156   unsigned int cursor = 0;
 157   xbt_dynar_foreach(a->states, cursor, state){
 158    if(strcmp(state->id, id)==0)
 159      return state;
 160   }
 161   return NULL;
 162 }
 163
 164 void xbt_automaton_display(xbt_automaton_t a){
 165   unsigned int cursor = 0;
 166   xbt_automaton_state_t state = NULL;
 167
 168   printf("\n\nEtat courant : %s\n", a->current_state->id);
 169
 170   printf("\nListe des états : %lu\n\n", xbt_dynar_length(a->states));
 171
 172
 173   xbt_dynar_foreach(a->states, cursor, state){
 174     printf("ID : %s, type : %d\n", state->id, state->type);
 175   }
 176
 177   cursor=0;
 178   xbt_automaton_transition_t transition = NULL;
 179   printf("\nListe des transitions : %lu\n\n", xbt_dynar_length(a->transitions));
 180
 181   xbt_dynar_foreach(a->transitions, cursor, transition){
 182     printf("label :");
 183     xbt_automaton_exp_label_display(transition->label);
 184     printf(", %s -> %s\n", transition->src->id, transition->dst->id);
 185   }
 186 }
 187
 188 void xbt_automaton_exp_label_display(xbt_automaton_exp_label_t label){
 189
 190   switch(label->type){
 191   case 0 :
 192     printf("(");
 193     xbt_automaton_exp_label_display(label->u.or_and.left_exp);
 194     printf(" || ");
 195     xbt_automaton_exp_label_display(label->u.or_and.right_exp);
 196     printf(")");
 197     break;
 198   case 1 :
 199     printf("(");
 200     xbt_automaton_exp_label_display(label->u.or_and.left_exp);
 201     printf(" && ");
 202     xbt_automaton_exp_label_display(label->u.or_and.right_exp);
 203     printf(")");
 204     break;
 205   case 2 :
 206     printf("(!");
 207     xbt_automaton_exp_label_display(label->u.exp_not);
 208     printf(")");
 209     break;
 210   case 3 :
 211     printf("(%s)",label->u.predicat);
 212     break;
 213   case 4 :
 214     printf("(1)");
 215     break;
 216   }
 217
 218 }
 219
 220 xbt_automaton_state_t xbt_automaton_get_current_state(xbt_automaton_t a){
 221   return a->current_state;
 222 }
 223
 224 static int call_simple_function(void* function)
 225 {
 226   return ((int (*)(void)) function)();
 227 }
 228
 229 xbt_automaton_propositional_symbol_t xbt_automaton_propositional_symbol_new(xbt_automaton_t a, const char* id, int(*fct)(void)){
 230   xbt_automaton_propositional_symbol_t prop_symb = NULL;
 231   prop_symb = xbt_new0(struct xbt_automaton_propositional_symbol, 1);
 232   prop_symb->pred = strdup(id);
 233   prop_symb->function = call_simple_function;
 234   prop_symb->data = fct;
 235   prop_symb->free_function = NULL;
 236   xbt_dynar_push(a->propositional_symbols, &prop_symb);
 237   return prop_symb;
 238 }
 239
 240 int xbt_automaton_state_compare(xbt_automaton_state_t s1, xbt_automaton_state_t s2){
 241
 242   /* single id for each state, id and type sufficient for comparison*/
 243
 244   if(strcmp(s1->id, s2->id))
 245     return 1;
 246
 247   if(s1->type != s2->type)
 248     return 1;
 249
 250   return 0;
 251
 252 }
 253
 254 int xbt_automaton_transition_compare(const void *t1, const void *t2){
 255
 256   if(xbt_automaton_state_compare(((xbt_automaton_transition_t)t1)->src, ((xbt_automaton_transition_t)t2)->src))
 257     return 1;
 258
 259   if(xbt_automaton_state_compare(((xbt_automaton_transition_t)t1)->dst, ((xbt_automaton_transition_t)t2)->dst))
 260     return 1;
 261
 262   if(xbt_automaton_exp_label_compare(((xbt_automaton_transition_t)t1)->label,((xbt_automaton_transition_t)t2)->label))
 263     return 1;
 264
 265   return 0;
 266
 267 }
 268
 269 int xbt_automaton_exp_label_compare(xbt_automaton_exp_label_t l1, xbt_automaton_exp_label_t l2){
 270
 271   if(l1->type != l2->type)
 272     return 1;
 273
 274   switch(l1->type){
 275
 276   case 0 : // OR
 277   case 1 : // AND
 278     if(xbt_automaton_exp_label_compare(l1->u.or_and.left_exp, l2->u.or_and.left_exp))
 279       return 1;
 280     else
 281       return xbt_automaton_exp_label_compare(l1->u.or_and.right_exp, l2->u.or_and.right_exp);
 282     break;
 283
 284   case 2 : // NOT
 285     return xbt_automaton_exp_label_compare(l1->u.exp_not, l2->u.exp_not);
 286     break;
 287
 288   case 3 : // predicat
 289     return (strcmp(l1->u.predicat, l2->u.predicat));
 290     break;
 291
 292   case 4 : // 1
 293     return 0;
 294     break;
 295
 296   default :
 297     return -1;
 298     break;
 299
 300   }
 301
 302 }
 303
 304
 305 int xbt_automaton_propositional_symbols_compare_value(xbt_dynar_t s1, xbt_dynar_t s2){
 306
 307   int *iptr1, *iptr2;
 308   unsigned int cursor;
 309   unsigned int nb_elem = xbt_dynar_length(s1);
 310
 311   for(cursor=0;cursor<nb_elem;cursor++){
 312     iptr1 = xbt_dynar_get_ptr(s1, cursor);
 313     iptr2 = xbt_dynar_get_ptr(s2, cursor);
 314     if(*iptr1 != *iptr2)
 315       return 1;
 316   }
 317
 318   return 0;
 319 }
 320
 321 /************ Free functions ****************/
 322
 323 static void xbt_automaton_transition_free(xbt_automaton_transition_t t);
 324 static void xbt_automaton_exp_label_free(xbt_automaton_exp_label_t e);
 325 static void xbt_automaton_propositional_symbol_free(xbt_automaton_propositional_symbol_t ps);
 326
 327 void xbt_automaton_state_free(xbt_automaton_state_t s){
 328   if(s){
 329     xbt_free(s->id);
 330     xbt_dynar_free(&(s->in));
 331     xbt_dynar_free(&(s->out));
 332     xbt_free(s);
 333     s = NULL;
 334   }
 335 }
 336
 337 void xbt_automaton_state_free_voidp(void *s){
 338   xbt_automaton_state_free((xbt_automaton_state_t) * (void **) s);
 339 }
 340
 341 static void xbt_automaton_transition_free(xbt_automaton_transition_t t){
 342   if(t){
 343     xbt_automaton_exp_label_free(t->label);
 344     xbt_free(t);
 345     t = NULL;
 346   }
 347 }
 348
 349 void xbt_automaton_transition_free_voidp(void *t){
 350   xbt_automaton_transition_free((xbt_automaton_transition_t) * (void **) t);
 351 }
 352
 353 static void xbt_automaton_exp_label_free(xbt_automaton_exp_label_t e){
 354   if(e){
 355     switch(e->type){
 356     case 0:
 357     case 1:
 358       xbt_automaton_exp_label_free(e->u.or_and.left_exp);
 359       xbt_automaton_exp_label_free(e->u.or_and.right_exp);
 360       break;
 361     case 2:
 362       xbt_automaton_exp_label_free(e->u.exp_not);
 363       break;
 364     case 3:
 365       xbt_free(e->u.predicat);
 366       break;
 367     default:
 368       break;
 369     }
 370     xbt_free(e);
 371     e = NULL;
 372   }
 373 }
 374
 375 void xbt_automaton_exp_label_free_voidp(void *e){
 376   xbt_automaton_exp_label_free((xbt_automaton_exp_label_t) * (void **) e);
 377 }
 378
 379 static void xbt_automaton_propositional_symbol_free(xbt_automaton_propositional_symbol_t ps){
 380   if(ps){
 381     xbt_free(ps->pred);
 382     xbt_free(ps);
 383     ps = NULL;
 384   }
 385 }
 386
 387 void xbt_automaton_propositional_symbol_free_voidp(void *ps){
 388   xbt_automaton_propositional_symbol_t symbol = (xbt_automaton_propositional_symbol_t) * (void **) ps;
 389   if (symbol->free_function)
 390     symbol->free_function(symbol->data);
 391   xbt_free(symbol->pred);
 392   xbt_automaton_propositional_symbol_free(symbol);
 393 }
 394
 395 void xbt_automaton_free(xbt_automaton_t a){
 396   if(a){
 397     xbt_dynar_free(&(a->propositional_symbols));
 398     xbt_dynar_free(&(a->transitions));
 399     xbt_dynar_free(&(a->states));
 400     xbt_automaton_state_free(a->current_state);
 401     xbt_free(a);
 402     a = NULL;
 403   }
 404 }