common/Quadruple.cc

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