src/xbt/automaton/automaton.c

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