Commit | Line | Data |
---|---|---|
970ed795 EL |
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 | } |