common/Quadruple.cc

   1 /******************************************************************************
   2  * Copyright (c) 2000-2016 Ericsson Telecom AB
   3  * All rights reserved. This program and the accompanying materials
   4  * are made available under the terms of the Eclipse Public License v1.0
   5  * which accompanies this distribution, and is available at
   6  * http://www.eclipse.org/legal/epl-v10.html
   7  *
   8  * Contributors:
   9  *   Balasko, Jeno
  10  *   Raduly, Csaba
  11  *   Zalanyi, Balazs Andor
  12  *
  13  ******************************************************************************/
  14 #include "memory.h"
  15 #include "pattern.hh"
  16 #include "Quadruple.hh"
  17
  18 Quad::Quad() : u() {
  19   u.value = 0;
  20 }
  21
  22 Quad::Quad(unsigned int value) : u() {
  23   u.value = value;
  24 }
  25
  26 Quad::Quad(unsigned char group, unsigned char plane, unsigned char row,
  27   unsigned char cell) : u() {
  28   u.comp.group = group;
  29   u.comp.plane = plane;
  30   u.comp.row = row;
  31   u.comp.cell = cell;
  32 }
  33
  34 Quad::Quad(const Quad& rhs) : u() {
  35   u.value = rhs.u.value;
  36 }
  37
  38 unsigned int Quad::get_value() const {
  39   return u.value;
  40 }
  41
  42 void Quad::set(int field, unsigned char c) {
  43   switch (field) {
  44   case 0:
  45     u.comp.group = c;
  46     break;
  47   case 1:
  48     u.comp.plane = c;
  49     break;
  50   case 2:
  51     u.comp.row = c;
  52     break;
  53   case 3:
  54     u.comp.cell = c;
  55     break;
  56   }
  57 }
  58
  59 void Quad::set(unsigned char group, unsigned char plane, unsigned char row,
  60   unsigned char cell) {
  61   u.comp.group = group;
  62   u.comp.plane = plane;
  63   u.comp.row = row;
  64   u.comp.cell = cell;
  65 }
  66
  67 const Quad Quad::operator-(const Quad& rhs) const {
  68   return Quad(u.value - rhs.u.value);
  69 }
  70
  71 const Quad& Quad::operator=(const Quad& rhs) {
  72   u.value = rhs.u.value;
  73   return *this;
  74 }
  75
  76 bool Quad::operator==(unsigned int i) const {
  77   return u.value == i;
  78 }
  79
  80 bool Quad::operator==(const Quad& rhs) const {
  81   return u.value == rhs.u.value;
  82 }
  83
  84 bool Quad::operator<=(const Quad& rhs) const {
  85   return u.value <= rhs.u.value;
  86 }
  87
  88 bool Quad::operator>=(const Quad& rhs) const {
  89   return u.value >= rhs.u.value;
  90 }
  91
  92 bool Quad::operator<(const Quad& rhs) const {
  93   return u.value < rhs.u.value;
  94 }
  95
  96 bool Quad::operator<(const QuadInterval& rhs) const {
  97   return u.value < rhs.lower.u.value;
  98 }
  99
 100 unsigned char Quad::operator[](int i) const {
 101   switch(i) {
 102   case 0:
 103     return u.comp.group;
 104   case 1:
 105     return u.comp.plane;
 106   case 2:
 107     return u.comp.row;
 108   case 3:
 109     return u.comp.cell;
 110   default:
 111     TTCN_pattern_error("Accessing a nonexistent field of a quadruple: %d.", i);
 112   }
 113   return 0; // to get rid of the warning
 114 }
 115
 116 char* Quad::get_hexrepr() const {
 117   return Quad::get_hexrepr(u.value);
 118 }
 119
 120 char* Quad::get_hexrepr(unsigned int value) {
 121   char hex[9];
 122   hex[8] = '\0';
 123   get_hexrepr(value, hex);
 124   return mcopystr(hex);
 125 }
 126
 127 void Quad::get_hexrepr(const Quad& q, char* const str) {
 128   str[0] = 'A' + (q.u.comp.group >> 4); // high end
 129   str[1] = 'A' + (q.u.comp.group & 15);
 130   str[2] = 'A' + (q.u.comp.plane >> 4);
 131   str[3] = 'A' + (q.u.comp.plane & 15);
 132   str[4] = 'A' + (q.u.comp.row   >> 4);
 133   str[5] = 'A' + (q.u.comp.row   & 15);
 134   str[6] = 'A' + (q.u.comp.cell  >> 4);
 135   str[7] = 'A' + (q.u.comp.cell  & 15); // low end
 136 }
 137
 138 char* Quad::char_hexrepr(unsigned char c) {
 139   char hex[3];
 140   hex[2] = '\0';
 141   hex[1] = (c & 15) + 'A';
 142   hex[0] = (c >> 4) + 'A';
 143   return mcopystr(hex);
 144 }
 145
 146 // QuadInterval ----------------------------------------------------------------
 147
 148 QuadInterval::QuadInterval(Quad p_lower, Quad p_upper) :
 149   lower(p_lower), upper(p_upper)
 150 {
 151 }
 152
 153 QuadInterval::QuadInterval(const QuadInterval& rhs)
 154 : lower(rhs.lower), upper(rhs.upper) {
 155 }
 156
 157 const Quad& QuadInterval::get_lower() const {
 158   return lower;
 159 }
 160
 161 const Quad& QuadInterval::get_upper() const {
 162   return upper;
 163 }
 164
 165 bool QuadInterval::contains(const Quad& rhs) const {
 166   return lower <= rhs && upper >= rhs;
 167 }
 168
 169 bool QuadInterval::contains(const QuadInterval& rhs) const {
 170   return lower <= rhs.lower && upper >= rhs.upper;
 171 }
 172
 173 bool QuadInterval::has_intersection(const QuadInterval& rhs) const {
 174   return (rhs.lower <= upper && rhs.lower >= lower) ||
 175   (rhs.upper <= upper && rhs.upper >= lower);
 176 }
 177
 178 void QuadInterval::join(const QuadInterval& rhs) {
 179   if (rhs.lower <= lower)
 180     lower = rhs.lower;
 181   if (rhs.upper >= upper)
 182     upper = rhs.upper;
 183 }
 184
 185 bool QuadInterval::operator <(const Quad& rhs) const {
 186   return upper < rhs;
 187 }
 188
 189 bool QuadInterval::operator <(const QuadInterval& rhs) const {
 190   return !has_intersection(rhs) && upper < rhs.lower;
 191 }
 192
 193 unsigned int QuadInterval::width() const {
 194   return (upper - lower).get_value();
 195 }
 196
 197 char* QuadInterval::generate_posix() {
 198   expstring_t res = memptystr();
 199   expstring_t str = 0;
 200   int diff[4];
 201   int i, j, c, k;
 202   for (i = 0; i < 4; i++)
 203     diff[i] = upper[i] - lower[i];
 204   Quad q1, q2;
 205   for (c = 0; c < 4 && diff[c] == 0; c++) ;
 206   while (c < 4) {
 207     if (c < 3)
 208       for (i = 0; i <= diff[c]; i++) {
 209         if (i > 0)
 210           res = mputc(res, '|');
 211         if (diff[c] > 0) {
 212           if (i == 0) {
 213             res = mputc(res, '(');
 214             q1 = q2 = lower;
 215             bool pipe = true;
 216             for (j = 3; j > c; j--) {
 217               if (j == 3 || (j < 3 && q1[j] < 255)) {
 218                 if (j < 3 && pipe)
 219                   res = mputc(res, '|');
 220                 for (k = 0; k < j; k++) {
 221                   res = mputprintf(res, "%s", str = Quad::char_hexrepr(q1[k]));
 222                   Free(str);
 223                 }
 224                 q2.set(j, 255);
 225                 res = mputprintf(res, "%s",
 226                   str = generate_hex_interval(q1[j], q2[j]));
 227                 Free(str);
 228                 q1.set(j, 0);
 229                 if (j > 0 && q1[j-1] < 255)
 230                   q1.set(j - 1, q1[j-1] + 1);
 231                 for (k = j + 1; k < 4; k++) {
 232                   res = mputprintf(res, "%s",
 233                     str = generate_hex_interval(0, 255));
 234                   Free(str);
 235                 }
 236                 pipe = true;
 237               } else
 238                 pipe = false;
 239             }
 240             res = mputc(res, ')');
 241           } else if (i < diff[c]) {
 242             for (j = 0; j < c; j++) {
 243               res = mputstr(res, str = Quad::char_hexrepr(lower[j]));
 244               Free(str);
 245             }
 246             str = generate_hex_interval(lower[c] + 1,
 247               (unsigned char)(lower[c] + diff[c] - 1));
 248             res = mputprintf(res, "%s", str);
 249             Free(str);
 250             k = (3 - c) * 2;
 251             if (k < 6) {
 252               for (j = 0; j < k; j++)
 253                 res = mputc(res, '.');
 254             } else
 255               res = mputprintf(res, ".\\{%d\\}", k);
 256             i = diff[c] - 1;
 257           } else {
 258             res = mputc(res, '(');
 259             for (k = c; k < 4 && c < 3; k++) {
 260               q1 = 0;
 261               q2 = upper;
 262               for (j = 0; j <= c; j++) {
 263                 q1.set(j, upper[j]);
 264                 res = mputstr(res, str = Quad::char_hexrepr(q1[j]));
 265                 Free(str);
 266               }
 267               c++;
 268               if (c < 3)
 269                 q2.set(c, upper[c] - 1);
 270               res = mputstr(res, str = generate_hex_interval(q1[c], q2[c]));
 271               Free(str);
 272               for (j = c + 1; j < 4; j++) {
 273                 q2.set(j, 255);
 274                 res = mputstr(res, str = generate_hex_interval(q1[j], q2[j]));
 275                 Free(str);
 276               }
 277               if (k < 3 && c < 3) {
 278                 res = mputc(res, '|');
 279               }
 280             }
 281             res = mputc(res, ')');
 282             return res;
 283           }
 284         } else if (diff[c] == 0) {
 285           c++;
 286           i = diff[c];
 287         } else {
 288           TTCN_pattern_error("In set interval: end is lower than start.");
 289           Free(res);
 290           return 0;
 291         }
 292       }
 293     else {
 294       for (j = 0; j < 3; j++) {
 295         res = mputstr(res, str = Quad::char_hexrepr(lower[j]));
 296         Free(str);
 297       }
 298       res = mputstr(res, str = generate_hex_interval(lower[3], upper[3]));
 299       Free(str);
 300       return res;
 301     }
 302   }
 303   return res;
 304 }
 305
 306 char* QuadInterval::generate_hex_interval(unsigned char source,
 307   unsigned char dest) {
 308   expstring_t res = memptystr();
 309   int s_lo, s_hi, d_lo, d_hi, lo, hi;
 310   s_lo = (source & 15) + 'A';
 311   s_hi = (source >> 4) + 'A';
 312   d_lo = (dest & 15) + 'A';
 313   d_hi = (dest >> 4) + 'A';
 314   lo = d_lo - s_lo;
 315   hi = d_hi - s_hi;
 316   if (hi > 0)
 317     res = mputc(res, '(');
 318
 319   if (hi == 0) {
 320     if (lo < 0) { // This is possibly reported during parsing.
 321       TTCN_pattern_error("Illegal interval in set: start > end.");
 322     } else if (lo > 0) {
 323       res = mputc(res, (char)s_hi);
 324       if (s_lo == 'A' && d_lo == 'P')
 325         res = mputc(res, '.');
 326       else
 327         res = mputprintf(res, "[%c-%c]", s_lo, d_lo);
 328     } else {
 329       res = mputc(res, (char)s_hi);
 330       res = mputc(res, (char)s_lo);
 331     }
 332     return res;
 333   }
 334
 335   bool alt = false;
 336   if (hi > 0) {
 337     if (s_lo != 'A') {
 338       res = mputprintf(res, "%c[%c-P]", s_hi, s_lo);
 339       s_hi++;
 340       alt = true;
 341     }
 342     if (d_lo != 'P') {
 343       if (alt)
 344         res = mputc(res, '|');
 345       else
 346         alt = true;
 347       res = mputprintf(res, "%c[A-%c]", d_hi, d_lo);
 348       d_hi--;
 349     }
 350     if (d_hi > s_hi) {
 351       if (alt)
 352         res = mputc(res, '|');
 353       if (s_hi == 'A' && d_hi == 'P')
 354         res = mputc(res, '.');
 355       else
 356         res = mputprintf(res, "[%c-%c]", s_hi, d_hi);
 357       res = mputc(res, '.');
 358     }
 359   }
 360
 361   if (hi > 0)
 362     res = mputc(res, ')');
 363   return res;
 364 }
 365
 366 // -------- QuadSet ------------------------------------------------------------
 367
 368 QuadSet::QuadSet() :
 369   set(0), negate(false)
 370 {
 371 }
 372
 373 bool QuadSet::add(Quad* p_quad) {
 374   bool contains = false;
 375   quadset_node_t* it = set;
 376   quadset_node_t* after = 0, *it_old = 0;
 377   while (it) {
 378     switch (it->etype) {
 379     case QSET_QUAD:
 380       contains = *(it->u.p_quad) == *p_quad;
 381       if (!contains && *p_quad < *(it->u.p_quad))
 382         after = it_old;
 383       break;
 384     case QSET_INTERVAL:
 385       contains = it->u.p_interval->contains(*p_quad);
 386       if (!contains && *p_quad < *(it->u.p_quad))
 387         after = it_old;
 388       break;
 389     }
 390     it_old = it;
 391     it = it->next;
 392   }
 393   if (!contains) {
 394     quadset_node_t* newnode = new quadset_node_t;
 395     newnode->etype = QSET_QUAD;
 396     newnode->u.p_quad = p_quad;
 397     if (after == 0) { // largest element in the set so far
 398       newnode->next = 0;
 399       if (it_old != 0)
 400         it_old->next = newnode;
 401       else
 402         set = newnode;
 403     } else {
 404       newnode->next = after->next;
 405       after->next = newnode;
 406     }
 407     return true;
 408   } else {
 409     delete p_quad;
 410     return false;
 411   }
 412 }
 413
 414 void QuadSet::add(QuadInterval* interval) {
 415   bool contains = false;
 416   quadset_node_t* it = set;
 417   quadset_node_t* after = 0, *it_old = 0;
 418   while (it) {
 419     switch (it->etype) {
 420     case QSET_QUAD:
 421       if (interval->contains(*(it->u.p_quad))) {  // delete the quad
 422         delete it->u.p_quad;
 423         if (it == set)
 424           set = it->next;
 425         quadset_node_t* p = it;
 426         it = it->next;
 427         delete p;
 428         continue;
 429       } else if (*interval < *(it->u.p_quad)) {
 430         after = it_old;
 431       }
 432       break;
 433     case QSET_INTERVAL:
 434       contains = it->u.p_interval->contains(*interval);
 435       if (!contains) {
 436         if (it->u.p_interval->has_intersection(*interval)) {  // merge
 437           it->u.p_interval->join(*interval);
 438           delete interval;
 439           join_if_possible(it);
 440           return;
 441         } else if (*interval < *(it->u.p_interval))
 442           after = it_old;
 443       }
 444       break;
 445     }
 446     it_old = it;
 447     it = it->next;
 448   }
 449   if (!contains) {
 450     quadset_node_t* newnode = new quadset_node_t;
 451     newnode->etype = QSET_INTERVAL;
 452     newnode->u.p_interval = interval;
 453     if (after == 0) { // largest element in the set so far
 454       newnode->next = 0;
 455       if (it_old != 0)
 456         it_old->next = newnode;
 457       else
 458         set = newnode;
 459     } else {
 460       newnode->next = after->next;
 461       after->next = newnode;
 462     }
 463   } else {
 464     delete interval;
 465   }
 466 }
 467
 468 void QuadSet::join(QuadSet* rhs) {
 469   quadset_node_t* it = rhs->set;
 470   while (it) {
 471     switch (it->etype) {
 472     case QSET_QUAD:
 473       add(new Quad(*(it->u.p_quad)));
 474       break;
 475     case QSET_INTERVAL:
 476       add(new QuadInterval(*(it->u.p_interval)));
 477       break;
 478     }
 479     it = it->next;
 480   }
 481 }
 482
 483 void QuadSet::set_negate(bool neg) {
 484   negate = neg;
 485 }
 486
 487 bool QuadSet::has_quad(const Quad& q) const {
 488   quadset_node_t* it = set;
 489   while (it) {
 490     switch(it->etype) {
 491     case QSET_QUAD:
 492       if (q == *(it->u.p_quad))
 493         return true;
 494       break;
 495     case QSET_INTERVAL:
 496       if (it->u.p_interval->contains(q))
 497         return true;
 498     }
 499     it = it->next;
 500   }
 501   return false;
 502 }
 503
 504 bool QuadSet::is_empty() const {
 505   return 0 == set;
 506 }
 507
 508 char* QuadSet::generate_posix() {
 509   expstring_t str = 0;
 510   if (negate)
 511     do_negate();
 512   char* res = memptystr();
 513   res = mputc(res, '(');
 514   quadset_node_t* it = set;
 515   while (it) {
 516     if (it != set)
 517       res = mputc(res, '|');
 518     switch (it->etype) {
 519     case QSET_QUAD:
 520       str = it->u.p_quad->get_hexrepr();
 521       res = mputprintf(res, "%s", str);
 522       Free(str);
 523       break;
 524     case QSET_INTERVAL:
 525       str = it->u.p_interval->generate_posix();
 526       res = mputprintf(res, "%s", str);
 527       Free(str);
 528       break;
 529     }
 530     it = it->next;
 531   }
 532   res = mputc(res, ')');
 533   return res;
 534 }
 535
 536 QuadSet::~QuadSet() {
 537   clean(set);
 538 }
 539
 540 void QuadSet::clean(quadset_node_t* start) {
 541   quadset_node_t* it = start;
 542   while (it) {
 543     switch (it->etype) {
 544     case QSET_QUAD:
 545       delete it->u.p_quad;
 546       break;
 547     case QSET_INTERVAL:
 548       delete it->u.p_interval;
 549       break;
 550     }
 551     quadset_node_t* p = it;
 552     it = it->next;
 553     delete p;
 554   }
 555 }
 556
 557 void QuadSet::do_negate() {
 558   QuadSet* qs = new QuadSet();
 559   quadset_node_t* it = set;
 560   Quad q1, q2;
 561   while (it) {
 562     switch (it->etype) {
 563     case QSET_QUAD:
 564       q2 = it->u.p_quad->get_value() - 1;
 565       qs->add_negate_interval(q1, q2);
 566       q1 = q2.get_value() + 1;
 567       break;
 568     case QSET_INTERVAL:
 569       q2 = it->u.p_interval->get_lower().get_value() - 1;
 570       qs->add_negate_interval(q1, q2);
 571       q1 = it->u.p_interval->get_upper().get_value() + 1;
 572       break;
 573     }
 574     it = it->next;
 575   }
 576   if (!(q1 == 0)) {
 577     q2.set(255, 255, 255, 255);
 578     qs->add_negate_interval(q1, q2);
 579   }/* else
 580     delete q1;*/
 581   clean(set);
 582   set = qs->set;
 583   qs->set = 0;
 584   delete qs;
 585 }
 586
 587 void QuadSet::add_negate_interval(const Quad& q1, const Quad& q2) {
 588   unsigned int w;
 589   if (q2 >= q1) {
 590     w = q2.get_value() - q1.get_value();
 591     if (w > 0)
 592       add(new QuadInterval(q1, q2));
 593     else {
 594       add(new Quad(q2));
 595     }
 596   }
 597 }
 598
 599 void QuadSet::join_if_possible(quadset_node_t* start) {
 600   quadset_node_t* it = start->next;
 601   while (it) {
 602     switch (it->etype) {
 603     case QSET_QUAD:
 604       if (start->u.p_interval->contains(*(it->u.p_quad))) {
 605         delete it->u.p_quad;
 606         quadset_node_t* p = it;
 607         it = it->next;
 608         delete p;
 609         continue;
 610       }
 611       break;
 612     case QSET_INTERVAL:
 613       if (start->u.p_interval->has_intersection(*(it->u.p_interval))) {
 614         start->u.p_interval->join(*(it->u.p_interval));
 615         delete it->u.p_interval;
 616         quadset_node_t* p = it;
 617         it = it->next;
 618         delete p;
 619         continue;
 620       }
 621       break;
 622     }
 623     it = it->next;
 624   }
 625 }