pegasus/src/Pegasus/CQL/Cql2Dnf.cpp - annotate

Return to Cql2Dnf.cpp CVS log

Up to [Pegasus] / pegasus / src / Pegasus / CQL

1 humberto 1.1.2.1 //%2003//////////////////////////////////////////////////////////////////////// 2 // 3 // Copyright (c) 2000, 2001, 2002 BMC Software, Hewlett-Packard Development 4 // Company, L. P., IBM Corp., The Open Group, Tivoli Systems. 5 // Copyright (c) 2003 BMC Software; Hewlett-Packard Development Company, L. P.; 6 // IBM Corp.; EMC Corporation, The Open Group. 7 // 8 // Permission is hereby granted, free of charge, to any person obtaining a copy 9 // of this software and associated documentation files (the "Software"), to 10 // deal in the Software without restriction, including without limitation the 11 // rights to use, copy, modify, merge, publish, distribute, sublicense, and/or 12 // sell copies of the Software, and to permit persons to whom the Software is 13 // furnished to do so, subject to the following conditions: 14 // 15 // THE ABOVE COPYRIGHT NOTICE AND THIS PERMISSION NOTICE SHALL BE INCLUDED IN 16 // ALL COPIES OR SUBSTANTIAL PORTIONS OF THE SOFTWARE. THE SOFTWARE IS PROVIDED 17 // "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT 18 // LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR 19 // PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT 20 // HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 21 // ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 22 humberto 1.1.2.1 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 23 // 24 //============================================================================== 25 // 26 // Author: Markus Mueller (sedgewick_de@yahoo.de) 27 // 28 // Modified By: Adrian Schuur, schuur@de.ibm.com 29 // 30 //%///////////////////////////////////////////////////////////////////////////// 31 32 33 //#include "CMPI_Version.h" 34 #include "Cql2Dnf.h" 35 #include <Pegasus/Common/Stack.h> 36 //#include <Pegasus/WQL/WQLParser.h> 37 38 PEGASUS_USING_STD; 39 PEGASUS_NAMESPACE_BEGIN 40 41 #define PEGASUS_ARRAY_T term_el 42 # include <Pegasus/Common/ArrayImpl.h> 43 humberto 1.1.2.1 #undef PEGASUS_ARRAY_T 44 45 #define PEGASUS_ARRAY_T eval_el 46 # include <Pegasus/Common/ArrayImpl.h> 47 #undef PEGASUS_ARRAY_T 48 49 #define PEGASUS_ARRAY_T stack_el 50 # include <Pegasus/Common/ArrayImpl.h> 51 #undef PEGASUS_ARRAY_T 52 53 // 54 // Terminal element methods 55 // 56 void term_el::negate() 57 { 58 switch (_simplePredicate.getOperation()) 59 { 60 case EQ: _simplePredicate.setOperation(NE); break; 61 case NE: _simplePredicate.setOperation(EQ); break; 62 case LT: _simplePredicate.setOperation(GE); break; 63 case LE: _simplePredicate.setOperation(GT); break; 64 humberto 1.1.2.1 case GT: _simplePredicate.setOperation(LE); break; 65 case GE: _simplePredicate.setOperation(LT); break; 66 case IS_NULL: 67 case IS_NOT_NULL: 68 case ISA: 69 case LIKE: 70 default: break; 71 } 72 }; 73 /* 74 String opnd2string(const WQLOperand &o) { 75 switch (o.getType()) { 76 case WQLOperand::PROPERTY_NAME: 77 return o.getPropertyName(); 78 case WQLOperand::STRING_VALUE: 79 return o.getStringValue(); 80 case WQLOperand::INTEGER_VALUE: 81 return Formatter::format("$0",o.getIntegerValue()); 82 case WQLOperand::DOUBLE_VALUE: 83 return Formatter::format("$0",o.getDoubleValue()); 84 case WQLOperand::BOOLEAN_VALUE: 85 humberto 1.1.2.1 return Formatter::format("$0",o.getBooleanValue()); 86 default: ; 87 } 88 return "NULL_VALUE"; 89 } 90 91 / 92 / 93 CMPIPredOp mapOperation(WQLOperation op) { 94 static CMPIPredOp ops[]={(CMPIPredOp)0,(CMPIPredOp)0,(CMPIPredOp)0, 95 CMPI_PredOp_Equals, 96 CMPI_PredOp_NotEquals, 97 CMPI_PredOp_LessThan, 98 CMPI_PredOp_LessThanOrEquals, 99 CMPI_PredOp_GreaterThan, 100 CMPI_PredOp_GreaterThanOrEquals, 101 (CMPIPredOp)0,(CMPIPredOp)0,(CMPIPredOp)0,(CMPIPredOp)0,(CMPIPredOp)0,(CMPIPredOp)0}; 102 return ops[(int)op]; 103 } 104 105 CMPIType mapType(WQLOperand::Type typ) { 106 humberto 1.1.2.1 switch (typ) { 107 case WQLOperand::PROPERTY_NAME: 108 return CMPI_nameString; 109 case WQLOperand::STRING_VALUE: 110 return CMPI_charString; 111 case WQLOperand::INTEGER_VALUE: 112 return CMPI_integerString; 113 case WQLOperand::DOUBLE_VALUE: 114 return CMPI_realString; 115 case WQLOperand::BOOLEAN_VALUE: 116 return CMPI_booleanString; 117 case WQLOperand::NULL_VALUE: 118 return CMPI_null; 119 } 120 return CMPI_null; 121 } 122 123 int term_el::toStrings(CMPIType &typ, CMPIPredOp &opr, String &o1, String &o2) const { 124 opr=mapOperation(op); 125 o1=opnd2string(opn1); 126 o2=opnd2string(opn2); 127 humberto 1.1.2.1 if (opn1.getType()==WQLOperand::PROPERTY_NAME) typ=mapType(opn2.getType()); 128 else typ=mapType(opn1.getType()); 129 return 0; 130 } 131 / 132 // 133 // Evaluation heap element methods 134 // 135 stack_el eval_el::getFirst() 136 { 137 return stack_el(opn1, is_terminal1); 138 } 139 140 stack_el eval_el::getSecond() 141 { 142 return stack_el(opn2, is_terminal2); 143 } 144 145 void eval_el::setFirst(const stack_el s) 146 { 147 opn1 = s.opn; 148 humberto 1.1.2.1 is_terminal1 = s.is_terminal; 149 } 150 151 void eval_el::setSecond(const stack_el s) 152 { 153 opn2 = s.opn; 154 is_terminal2 = s.is_terminal; 155 } 156 157 void eval_el::assign_unary_to_first(const eval_el & assignee) 158 { 159 opn1 = assignee.opn1; 160 is_terminal1 = assignee.is_terminal1; 161 } 162 163 void eval_el::assign_unary_to_second(const eval_el & assignee) 164 { 165 opn2 = assignee.opn1; 166 is_terminal2 = assignee.is_terminal1; 167 } 168 169 humberto 1.1.2.1 // Ordering operators, so that op1 > op2 for all non-terminals 170 // and terminals appear in the second operand first 171 void eval_el::order(void) 172 { 173 int k; 174 if ((!is_terminal1) && (!is_terminal2)) 175 if ((k = opn2) > opn1) 176 { 177 opn2 = opn1; 178 opn1 = k; 179 } 180 else if ((is_terminal1) && (!is_terminal2)) 181 if ((k = opn2) > opn1) 182 { 183 opn2 = opn1; 184 opn1 = k; 185 is_terminal1 = false; 186 is_terminal2 = true; 187 } 188 } 189 190 humberto 1.1.2.1 // 191 // Helper function copied from WQLSelectStatement 192 // 193 / 194 template<class T> 195 inline static Boolean _Compare(const T& x, const T& y, WQLOperation op) 196 { 197 switch (op) 198 { 199 case WQL_EQ: 200 return x == y; 201 202 case WQL_NE: 203 return x != y; 204 205 case WQL_LT: 206 return x < y; 207 case WQL_LE: 208 return x <= y; 209 210 case WQL_GT: 211 humberto 1.1.2.1 return x > y; 212 213 case WQL_GE: 214 return x >= y; 215 216 default: 217 PEGASUS_ASSERT(0); 218 } 219 220 return false; 221 } 222 223 static bool operator==(const WQLOperand& x, const WQLOperand& y) 224 { 225 if (x.getType()==y.getType()) switch (x.getType()) { 226 case WQLOperand::PROPERTY_NAME: 227 return x.getPropertyName()==y.getPropertyName(); 228 case WQLOperand::INTEGER_VALUE: 229 return x.getIntegerValue()==y.getIntegerValue(); 230 case WQLOperand::DOUBLE_VALUE: 231 return x.getDoubleValue()==y.getDoubleValue(); 232 humberto 1.1.2.1 case WQLOperand::BOOLEAN_VALUE: 233 return x.getBooleanValue()==y.getBooleanValue(); 234 case WQLOperand::STRING_VALUE: 235 return x.getStringValue()==y.getStringValue(); 236 case WQLOperand::NULL_VALUE: 237 return true; 238 } 239 return false; 240 } 241 / 242 static bool operator==(const term_el& x, const term_el& y) 243 { 244 return x._simplePredicate == y._simplePredicate; 245 } 246 / 247 static void addIfNotExists(TableauRow &tr, const term_el& el) 248 { 249 for (int i=0,m=tr.size(); i<m; i++) { 250 if (tr[i]==el) return; 251 } 252 tr.append(el); 253 humberto 1.1.2.1 } 254 / 255 / 256 static Boolean _Evaluate( 257 const WQLOperand& lhs, 258 const WQLOperand& rhs, 259 WQLOperation op) 260 { 261 switch (lhs.getType()) 262 { 263 case WQLOperand::NULL_VALUE: 264 { 265 // This cannot happen since expressions of the form 266 // OPERAND OPERATOR NULL are converted to unary form. 267 // For example: "count IS NULL" is treated as a unary 268 // operation in which IS_NULL is the unary operation 269 // and count is the the unary operand. 270 271 PEGASUS_ASSERT(0); 272 break; 273 } 274 humberto 1.1.2.1 275 case WQLOperand::INTEGER_VALUE: 276 { 277 return _Compare( 278 lhs.getIntegerValue(), 279 rhs.getIntegerValue(), 280 op); 281 } 282 283 case WQLOperand::DOUBLE_VALUE: 284 { 285 return _Compare( 286 lhs.getDoubleValue(), 287 rhs.getDoubleValue(), 288 op); 289 } 290 291 case WQLOperand::BOOLEAN_VALUE: 292 { 293 return _Compare( 294 lhs.getBooleanValue(), 295 humberto 1.1.2.1 rhs.getBooleanValue(), 296 op); 297 } 298 299 case WQLOperand::STRING_VALUE: 300 { 301 return _Compare( 302 lhs.getStringValue(), 303 rhs.getStringValue(), 304 op); 305 } 306 307 default: 308 PEGASUS_ASSERT(0); 309 } 310 311 return false; 312 } 313 / 314 315 // 316 humberto 1.1.2.1 // CQL Compiler methods 317 // 318 319 / 320 Cql2Dnf::Cql2Dnf(const String condition, const String pref) 321 { 322 WQLSelectStatement wqs; 323 WQLParser::parse(pref+condition,wqs); 324 eval_heap.reserveCapacity(16); 325 terminal_heap.reserveCapacity(16); 326 _tableau.clear(); 327 compile(&wqs); 328 } 329 / 330 Cql2Dnf::Cql2Dnf() 331 { 332 eval_heap.reserveCapacity(16); 333 terminal_heap.reserveCapacity(16); 334 //_tableau.clear(); 335 } 336 337 humberto 1.1.2.1 Cql2Dnf::Cql2Dnf(CQLSelectStatement & cqs) 338 { 339 eval_heap.reserveCapacity(16); 340 terminal_heap.reserveCapacity(16); 341 compile(&cqs); 342 } 343 344 Cql2Dnf::Cql2Dnf(CQLSelectStatement cqs) 345 { 346 eval_heap.reserveCapacity(16); 347 terminal_heap.reserveCapacity(16); 348 compile(cqs); 349 } 350
351 humberto 1.1.2.2 Cql2Dnf::Cql2Dnf(CQLPredicate& topLevel){ 352 eval_heap.reserveCapacity(16); 353 terminal_heap.reserveCapacity(16); 354 compile(topLevel); 355 } 356
357 humberto 1.1.2.1 Cql2Dnf::~Cql2Dnf() {} 358
359 humberto 1.1.2.2 void Cql2Dnf::compile(CQLSelectStatement * cqs){ 360 CQLPredicate topLevel = cqs->getPredicate(); 361 compile(topLevel); 362 } 363 364 void Cql2Dnf::compile(CQLPredicate& topLevel)
365 humberto 1.1.2.1 {
366 humberto 1.1.2.2 //if (!cqs->hasWhereClause()) return;
367 humberto 1.1.2.1
368 humberto 1.1.2.2 _strip_ops_operands(topLevel);
369 humberto 1.1.2.1 _buildEvalHeap(); 370 _pushNOTDown(); 371 _factoring(); 372 _construct(); // rebuild the statement 373 /* 374 Array<stack_el> disj; 375 _gatherDisj(disj); 376 if (disj.size() == 0) 377 if (terminal_heap.size() > 0) 378 // point to the remaining terminal element 379 disj.append(stack_el(0,true)); 380 381 for (Uint32 i=0, n =disj.size(); i< n; i++) 382 { 383 TableauRow tr; 384 Array<stack_el> conj; 385 386 if (!disj[i].is_terminal) 387 { 388 _gatherConj(conj, disj[i]); 389 for( Uint32 j=0, m = conj.size(); j < m; j++) 390 humberto 1.1.2.1 addIfNotExists(tr,terminal_heap[conj[j].opn]); 391 // tr.append(terminal_heap[conj[j].opn]); 392 } 393 else 394 addIfNotExists(tr,terminal_heap[disj[i].opn]); 395 // tr.append(terminal_heap[disj[i].opn]); 396 _tableau.append(tr); 397 } 398 / 399 eval_heap.clear(); 400 401 //print(); 402 //printTableau(); 403 //_sortTableau(); 404 } 405 / 406 Boolean CMPI_Wql2Dnf::evaluate(WQLPropertySource * source) const 407 { 408 Boolean b = false; 409 WQLOperand lhs, rhs; 410 411 humberto 1.1.2.1 for(Uint32 i=0,n = _tableau.size(); i < n; i++) 412 { 413 TableauRow tr = _tableau[i]; 414 for(Uint32 j=0,m = tr.size(); j < m; j++) 415 { 416 lhs = tr[j].opn1; 417 CMPI_Wql2Dnf::_ResolveProperty(lhs,source); 418 rhs = tr[j].opn2; 419 CMPI_Wql2Dnf::_ResolveProperty(rhs,source); 420 421 if (rhs.getType() != lhs.getType()) 422 throw TypeMismatchException(); 423 424 if (!_Evaluate(lhs, rhs, tr[j].op)) 425 { 426 b = false; 427 break; 428 } 429 else 430 b = true; 431 } 432 humberto 1.1.2.1 if (b) return true; 433 } 434 return false; 435 } 436 / 437 / 438 void Cql2Dnf::print(void) 439 { 440 for (Uint32 i=0, n=eval_heap.size();i < n;i++) { 441 WQLOperation wop = eval_heap[i].op; 442 if (wop == WQL_IS_TRUE) continue; 443 cout << "Eval element " << i << ": "; 444 if (eval_heap[i].is_terminal1) cout << "T("; 445 else cout << "E("; 446 cout << eval_heap[i].opn1 << ") "; 447 cout << WQLOperationToString(eval_heap[i].op); 448 if (eval_heap[i].is_terminal2) cout << " T("; 449 else cout << " E("; 450 cout << eval_heap[i].opn2 << ")" << endl; 451 } 452 for (Uint32 i=0, n=terminal_heap.size();i < n;i++) { 453 humberto 1.1.2.1 cout << "Terminal expression " << i << ": "; 454 cout << terminal_heap[i].opn1.toString() << " "; 455 cout << WQLOperationToString(terminal_heap[i].op) << " " 456 << terminal_heap[i].opn2.toString() << endl; 457 } 458 } 459 / 460 / 461 void CMPI_Wql2Dnf::printTableau(void) 462 { 463 for(Uint32 i=0,n = _tableau.size(); i < n; i++) 464 { 465 cout << "Tableau " << i << endl; 466 TableauRow tr = _tableau[i]; 467 for(Uint32 j=0,m = tr.size(); j < m; j++) 468 { 469 cout << tr[j].opn1.toString() << " "; 470 cout << WQLOperationToString(tr[j].op) << " " 471 << tr[j].opn2.toString() << endl; 472 } 473 474 humberto 1.1.2.1 } 475 476 } 477 / 478 void Cql2Dnf::_buildEvalHeap() 479 { 480 481 //WQLSelectStatement that = (WQLSelectStatement*)wqs; 482 483 Stack<stack_el> stack; 484 485 // Operation conversion variable from OperationType enum to ExpressionOpType enum 486 ExpressionOpType expOp; 487 488 // Counter for Operands 489 490 Uint32 j = 0; 491 492 //cerr << "Build eval heap\n"; 493 494 for (Uint32 i = 0, n = _operations.size(); i < n; i++) 495 humberto 1.1.2.1 { 496 OperationType op = _operations[i]; 497 498 switch (op) 499 { 500 case CQL_OR: 501 case CQL_AND: 502 { 503 PEGASUS_ASSERT(stack.size() >= 2); 504 505 stack_el op1 = stack.top(); 506 stack.pop(); 507 508 stack_el op2 = stack.top(); 509 510 // generate Eval expression 511 eval_heap.append(eval_el(0, op , op1.opn, op1.is_terminal, 512 op2.opn , op2.is_terminal)); 513 514 stack.top() = stack_el(eval_heap.size()-1, false); 515 516 humberto 1.1.2.1 break; 517 } 518 519 case CQL_NOT: 520 { 521 PEGASUS_ASSERT(stack.size() >= 1); 522 523 stack_el op1 = stack.top(); 524 525 // generate Eval expression 526 eval_heap.append(eval_el(0, op , op1.opn, op1.is_terminal, 527 -1, true)); 528 529 stack.top() = stack_el(eval_heap.size()-1, false); 530 531 break; 532 } 533
534 humberto 1.1.2.3 case CQL_EQ: 535 case CQL_NE: 536 case CQL_LT: 537 case CQL_LE: 538 case CQL_GT: 539 case CQL_GE:
540 humberto 1.1.2.1 { 541 PEGASUS_ASSERT(_operands.size() >= 2); 542 543 CQLExpression lhs = _operands[j++]; 544 545 CQLExpression rhs = _operands[j++]; 546
547 humberto 1.1.2.3 CQLSimplePredicate sp(lhs,rhs,_convertOpType(op)); 548 printf("****** pushing simplepredicate on terminal heap %s\n",(const char*)sp.toString().getCString());
549 humberto 1.1.2.1 terminal_heap.push(term_el(false, sp)); 550 551 stack.push(stack_el(terminal_heap.size()-1, true)); 552 553 break; 554 } 555 /* 556 case WQL_IS_TRUE: 557 case WQL_IS_NOT_FALSE: 558 { 559 PEGASUS_ASSERT(stack.size() >= 1); 560 break; 561 } 562 / 563 case CQL_IS_NULL: 564 { 565 PEGASUS_ASSERT(_operands.size() >= 1); 566 CQLExpression expression = _operands[j++]; 567 CQLSimplePredicate dummy(expression,EQ); 568 terminal_heap.push(term_el(false, dummy)); 569 570 humberto 1.1.2.1 stack.push(stack_el(terminal_heap.size()-1, true)); 571 572 break; 573 } 574 575 case CQL_IS_NOT_NULL: 576 { 577 PEGASUS_ASSERT(_operands.size() >= 1); 578 CQLExpression expression = _operands[j++]; 579 CQLSimplePredicate dummy(expression,NE); 580 terminal_heap.push(term_el(false, dummy)); 581 582 stack.push(stack_el(terminal_heap.size()-1, true)); 583 584 break; 585 } 586 case CQL_NOOP: 587 default: break; 588 } 589 } 590 591 humberto 1.1.2.1 PEGASUS_ASSERT(stack.size() == 1); 592 } 593 594 void Cql2Dnf::_pushNOTDown() 595 { 596 for (int i=eval_heap.size()-1; i >= 0; i--) 597 { 598 Boolean _found = false; 599 int k; 600 601 // Order all operators, so that op1 > op2 for non-terminals 602 // and terminals appear as second operand 603 604 eval_heap[i].order(); 605 606 // First solve the unary NOT operator 607 608 if (eval_heap[i].op == CQL_NOT) 609 { 610 // This serves as the equivalent of an empty operator 611 eval_heap[i].op = CQL_NOOP; 612 humberto 1.1.2.1 613 // Substitute this expression in all higher order eval statements 614 // so that this node becomes disconnected from the tree 615 616 for (int j=eval_heap.size()-1; j > i;j--) 617 { 618 // Test first operand 619 if ((!eval_heap[j].is_terminal1) && (eval_heap[j].opn1 == i)) 620 621 eval_heap[j].assign_unary_to_first(eval_heap[i]); 622 623 // Test second operand 624 if ((!eval_heap[j].is_terminal2) && (eval_heap[j].opn2 == i)) 625 626 eval_heap[j].assign_unary_to_second(eval_heap[i]); 627 } 628 629 // Test: Double NOT created by moving down 630 631 if (eval_heap[i].mark) 632 eval_heap[i].mark = false; 633 humberto 1.1.2.1 else 634 _found = true; 635 // else indicate a pending NOT to be pushed down further 636 } 637 638 // Simple NOT created by moving down 639 640 if (eval_heap[i].mark) 641 { 642 // Remove the mark, indicate a pending NOT to be pushed down 643 // further and switch operators (AND / OR) 644 645 eval_heap[i].mark=false; 646 if (eval_heap[i].op == CQL_OR) eval_heap[i].op = CQL_AND; 647 else if (eval_heap[i].op == CQL_AND) eval_heap[i].op = CQL_OR; 648 649 // NOT operator is already ruled out 650 _found = true; 651 } 652 653 // Push a pending NOT further down 654 humberto 1.1.2.1 if (_found) 655 { 656 // First operand 657 658 int j = eval_heap[i].opn1; 659 if (eval_heap[i].is_terminal1) 660 // Flip NOT mark 661 terminal_heap[j].negate(); 662 else 663 eval_heap[j].mark = !(eval_heap[j].mark); 664 665 //Second operand (if it exists) 666 667 if ((j = eval_heap[i].opn2) >= 0) 668 { 669 if (eval_heap[i].is_terminal2) 670 // Flip NOT mark 671 terminal_heap[j].negate(); 672 else 673 eval_heap[j].mark = !(eval_heap[j].mark); 674 } 675 humberto 1.1.2.1 } 676 } 677 } 678 679 void Cql2Dnf::_factoring(void) 680 { 681 int i = 0,n = eval_heap.size(); 682 //for (int i=eval_heap.size()-1; i >= 0; i--) 683 while (i < n) 684 { 685 int _found = 0; 686 int index = 0; 687 688 // look for expressions (A \| B) & C ---> A & C \| A & B 689 if (eval_heap[i].op == CQL_AND) 690 { 691 if (!eval_heap[i].is_terminal1) 692 { 693 index = eval_heap[i].opn1; // remember the index 694 if (eval_heap[index].op == CQL_OR) _found = 1; 695 } 696 humberto 1.1.2.1 697 if ((_found == 0) && (!eval_heap[i].is_terminal2)) 698 { 699 index = eval_heap[i].opn2; // remember the index 700 if (eval_heap[index].op == CQL_OR) _found = 2; 701 } 702 703 if (_found != 0) 704 { 705 //int u1,u1_t,u2,u2_t,u3,u3_t; 706 stack_el s; 707 708 if (_found == 1) 709 s = eval_heap[i].getSecond(); 710 else 711 s = eval_heap[i].getFirst(); 712 713 // insert two new expression before entry i 714 eval_el evl; 715 716 evl = eval_el(false, CQL_OR, i+1, false, i, false); 717 humberto 1.1.2.1 if ((Uint32 )i < eval_heap.size()-1) 718 eval_heap.insert(i+1, evl); 719 else 720 eval_heap.append(evl); 721 eval_heap.insert(i+1, evl); 722 723 for (int j=eval_heap.size()-1; j > i + 2; j--) 724 { 725 //eval_heap[j] = eval_heap[j-2]; 726 727 // adjust pointers 728 729 if ((!eval_heap[j].is_terminal1)&& 730 (eval_heap[j].opn1 >= i)) 731 eval_heap[j].opn1 += 2; 732 if ((!eval_heap[j].is_terminal2)&& 733 (eval_heap[j].opn2 >= i)) 734 eval_heap[j].opn2 += 2; 735 } 736 737 n+=2; // increase size of array 738 humberto 1.1.2.1 739 // generate the new expressions : new OR expression 740 741 742 // first new AND expression 743 eval_heap[i+1].mark = false; 744 eval_heap[i+1].op = CQL_AND; 745 eval_heap[i+1].setFirst(s); 746 eval_heap[i+1].setSecond( eval_heap[index].getFirst()); 747 eval_heap[i+1].order(); 748 749 750 // second new AND expression 751 eval_heap[i].mark = false; 752 eval_heap[i].op = CQL_AND; 753 eval_heap[i].setFirst(s); 754 eval_heap[i].setSecond( eval_heap[index].getSecond()); 755 eval_heap[i].order(); 756 757 // mark the indexed expression as inactive 758 //eval_heap[index].op = WQL_IS_TRUE; possible disconnects 759 humberto 1.1.2.1 i--; 760 761 } / endif _found > 0 / 762 763 } / endif found AND operator / 764 765 i++; // increase pointer 766 } 767 } 768 / 769 void Cql2Dnf::_gatherDisj(Array<stack_el>& stk) 770 { 771 _gather(stk, stack_el(0,true), true); 772 } 773 774 void Cql2Dnf::_gatherConj(Array<stack_el>& stk, stack_el sel) 775 { 776 _gather(stk, sel, false); 777 } 778 779 void Cql2Dnf::_gather(Array<stack_el>& stk, stack_el sel, Boolean or_flag) 780 humberto 1.1.2.1 { 781 Uint32 i = 0; 782 783 stk.clear(); 784 stk.reserveCapacity(16); 785 786 if ((i = eval_heap.size()) == 0) return; 787 788 while (eval_heap[i-1].op == WQL_IS_TRUE) 789 { 790 eval_heap.remove(i-1); 791 i--; 792 if (i == 0) return; 793 } 794 //if (i == 0) return; 795 796 if (or_flag) 797 stk.append(stack_el(i-1,false)); 798 else 799 { 800 if (sel.is_terminal) return; 801 humberto 1.1.2.1 stk.append(sel); 802 } 803 804 i = 0; 805 806 while (i<stk.size()) 807 { 808 int k = stk[i].opn; 809 810 if ((k < 0) \|\| (stk[i].is_terminal)) 811 i++; 812 else 813 { 814 if ( ((eval_heap[k].op != WQL_OR) && (or_flag)) \|\| 815 ((eval_heap[k].op != WQL_AND) && (!or_flag)) ) 816 i++; 817 else 818 { 819 // replace the element with disjunction 820 stk[i] = eval_heap[k].getSecond(); 821 stk.insert(i, eval_heap[k].getFirst()); 822 humberto 1.1.2.1 if (or_flag) 823 eval_heap[k].op = WQL_IS_TRUE; 824 } 825 } 826 } 827 } 828 */
829 humberto 1.1.2.2 void Cql2Dnf::_strip_ops_operands(CQLPredicate& topLevel)
830 humberto 1.1.2.1 { 831 // 832 // depth first search for all operations and operands 833 // extract operations and operands and store in respective arrays for later processing 834 // 835 _destruct(topLevel); 836 } 837 838 OperationType Cql2Dnf::_convertOpType(ExpressionOpType op){ 839 switch(op){ 840 case EQ: return CQL_EQ; 841 case NE: return CQL_NE; 842 case GT: return CQL_GT; 843 case LT: return CQL_LT; 844 case GE: return CQL_GE; 845 case LE: return CQL_LE; 846 case IS_NULL: return CQL_IS_NULL; 847 case IS_NOT_NULL: return CQL_IS_NOT_NULL; 848 case ISA: 849 case LIKE: 850 default: return CQL_NOOP; 851 humberto 1.1.2.1 } 852 } 853
854 humberto 1.1.2.3 ExpressionOpType Cql2Dnf::_convertOpType(OperationType op){ 855 switch(op){ 856 case CQL_EQ: return EQ; 857 case CQL_NE: return NE; 858 case CQL_GT: return GT; 859 case CQL_LT: return LT; 860 case CQL_GE: return GE; 861 case CQL_LE: return LE; 862 case CQL_IS_NULL: return IS_NULL; 863 case CQL_IS_NOT_NULL: return IS_NOT_NULL; 864 default: break; 865 } 866 } 867
868 humberto 1.1.2.1 void Cql2Dnf::_destruct(CQLPredicate& _p){ 869 if(_p.isSimple()){ 870 CQLSimplePredicate _sp = _p.getSimplePredicate(); 871 _operations.append(_convertOpType(_sp.getOperation())); 872 _operands.append(_sp.getLeftExpression()); 873 _operands.append(_sp.getRightExpression()); 874 } 875 else{ 876 Array<CQLPredicate> _preds = _p.getPredicates(); 877 Array<BooleanOpType> _boolops = _p.getOperators(); 878 for(Uint32 i=0;i<_preds.size();i++){ 879 _destruct(_preds[i]); 880 if(_preds[i].getInverted()){ 881 _operations.append(CQL_NOT); 882 } 883 if(i > 0){ 884 if(_boolops[i-1] == AND){ 885 _operations.append(CQL_AND); 886 } 887 if(_boolops[i-1] == OR){ 888 _operations.append(CQL_OR); 889 humberto 1.1.2.1 } 890 } 891 } 892 } 893 } 894 895 void Cql2Dnf::_construct(){ 896 // 897 // Each eval_el on the eval heap contains all the information needed to make a CQLPredicate. 898 // We will build a CQLPredicate for every element in the eval heap. So there is a 1 to 1 correspondence 899 // between elements in the eval heap and elements in the CQLPredicate array used below. 900 // The first eval_el on the eval heap will always contain at least one terminal if the operation is a NOT 901 // or two terminals if the operation is AND or OR. We are guaranteed to build a CQLPredicate from the first 902 // position in the eval_heap array. 903 // 904 // The key to the algorithm is the isterminalX flag. When set to true, we go to the 905 // term_heap and get the CQLSimplePredicate. When set to false, we go to the _preds array below 906 // and get the CQLPredicate. Since there is a 1 - 1 correspondence, as explained above, the index 907 // referred to by eval.opn1 or eval.opn2 is valid into the _preds array. 908 // 909 // For ANDs and ORs, we need two operands, as explained above, we get those operands 910 humberto 1.1.2.1 // from either the term_heap or the _preds array. For NOTs, we need only 1 operand, and that 911 // comes from either the term_heap or the _preds array. 912 // 913 // When finished, the last element in the _preds array contains the top level CQLPredicate (the rebuilt tree) 914 // 915 // Example: a=b^(!c=d v e=f) 916 // If the current eval_heap looks like: 917 // 0,NOT,1,True,-1,True [index = 0] 918 // 0,OR,2,True,0,False [index = 1] 919 // 0,AND,1,False,0,True [index = 2] 920 // 921 // And the current term_heap looks like: 922 // CQLSimplePredicate(a=b) [index = 0] 923 // CQLSimplePredicate(c=d) [index = 1] 924 // CQLSimplePredicate(e=f) [index = 0] 925 // 926 // The _preds array at the end would look like: 927 // CQLPredicate(!c==d) [index = 0] 928 // CQLPredicate(e==f v !c==d) [index = 1] 929 // CQLPredicate((e==f v !c==d) ^ a==b) [index = 2] (the rebuilt tree) 930 // 931 humberto 1.1.2.1
932 humberto 1.1.2.3 if(eval_heap.size() > 0){ 933 printf("** eval_heap.size = %d\n",eval_heap.size()); 934 printf("** terminal_heap.size = %d\n",terminal_heap.size()); 935 Array<CQLPredicate> _preds; 936 for(Uint32 i=0;i<eval_heap.size();i++){
937 humberto 1.1.2.1 eval_el eval = eval_heap[i]; 938 if(eval.is_terminal1 && eval.is_terminal2){ 939 switch(eval.op){ 940 case CQL_NOT: 941 { 942 _preds.append(CQLPredicate(terminal_heap[eval.opn1]._simplePredicate,true)); 943 break; 944 } 945 case CQL_NOOP: 946 { 947 _preds.append(CQLPredicate(terminal_heap[eval.opn1]._simplePredicate,false)); 948 break; 949 } 950 case CQL_AND: 951 {
952 humberto 1.1.2.3 CQLPredicate p; 953 CQLPredicate p1(terminal_heap[eval.opn2]._simplePredicate,false); 954 p.appendPredicate(p1); 955 CQLPredicate p2(terminal_heap[eval.opn1]._simplePredicate,false); 956 p.appendPredicate(p2,AND);
957 humberto 1.1.2.1 _preds.append(p); 958 break; 959 } 960 case CQL_OR: 961 {
962 humberto 1.1.2.3 CQLPredicate p; 963 CQLPredicate p1(terminal_heap[eval.opn2]._simplePredicate,false); 964 p.appendPredicate(p1); 965 CQLPredicate p2(terminal_heap[eval.opn1]._simplePredicate,false); 966 p.appendPredicate(p2,OR);
967 humberto 1.1.2.1 _preds.append(p);
968 humberto 1.1.2.3 break;
969 humberto 1.1.2.1 } 970 case CQL_EQ: 971 case CQL_NE: 972 case CQL_GT: 973 case CQL_LT: 974 case CQL_GE: 975 case CQL_LE: 976 case CQL_IS_NULL: 977 case CQL_IS_NOT_NULL: break; 978 979 } 980 }else if(eval.is_terminal1 && !eval.is_terminal2){ 981 switch(eval.op){ 982 case CQL_NOT: 983 { 984 _preds.append(CQLPredicate(terminal_heap[eval.opn1]._simplePredicate,true)); 985 break; 986 } 987 case CQL_NOOP: 988 { 989 _preds.append(CQLPredicate(terminal_heap[eval.opn1]._simplePredicate,false)); 990 humberto 1.1.2.1 break; 991 } 992 case CQL_AND: 993 {
994 humberto 1.1.2.3 CQLPredicate p; 995 CQLPredicate p1(terminal_heap[eval.opn1]._simplePredicate,false); 996 p.appendPredicate(_preds[eval.opn2]); 997 p.appendPredicate(p1,AND);
998 humberto 1.1.2.1 _preds.append(p);
999 humberto 1.1.2.3 break;
1000 humberto 1.1.2.1 } 1001 case CQL_OR: 1002 {
1003 humberto 1.1.2.3 CQLPredicate p; 1004 CQLPredicate p1(terminal_heap[eval.opn1]._simplePredicate,false); 1005 p.appendPredicate(_preds[eval.opn2]); 1006 p.appendPredicate(p1,OR);
1007 humberto 1.1.2.1 _preds.append(p);
1008 humberto 1.1.2.3 break;
1009 humberto 1.1.2.1 } 1010 case CQL_EQ: 1011 case CQL_NE: 1012 case CQL_GT: 1013 case CQL_LT: 1014 case CQL_GE: 1015 case CQL_LE: 1016 case CQL_IS_NULL: 1017 case CQL_IS_NOT_NULL: break; 1018 1019 } 1020 }else if(!eval.is_terminal1 && eval.is_terminal2){ 1021 switch(eval.op){ 1022 case CQL_NOT: 1023 { 1024 CQLPredicate p = _preds[eval.opn1]; 1025 p.setInverted(); 1026 _preds.append(p); 1027 break; 1028 } 1029 case CQL_NOOP: 1030 humberto 1.1.2.1 { 1031 _preds.append(_preds[eval.opn1]); 1032 break; 1033 } 1034 case CQL_AND: 1035 {
1036 humberto 1.1.2.3 CQLPredicate p; 1037 CQLPredicate p1(terminal_heap[eval.opn2]._simplePredicate,false); 1038 p.appendPredicate(_preds[eval.opn1]); 1039 p.appendPredicate(p1,AND);
1040 humberto 1.1.2.1 _preds.append(p);
1041 humberto 1.1.2.3 break;
1042 humberto 1.1.2.1 } 1043 case CQL_OR: 1044 {
1045 humberto 1.1.2.3 CQLPredicate p; 1046 CQLPredicate p1(terminal_heap[eval.opn2]._simplePredicate,false); 1047 p.appendPredicate(_preds[eval.opn1]); 1048 p.appendPredicate(p1,OR); 1049 _preds.append(p); 1050 break;
1051 humberto 1.1.2.1 } 1052 case CQL_EQ: 1053 case CQL_NE: 1054 case CQL_GT: 1055 case CQL_LT: 1056 case CQL_GE: 1057 case CQL_LE: 1058 case CQL_IS_NULL: 1059 case CQL_IS_NOT_NULL: break; 1060 1061 } 1062 }else{ // !eval.is_terminal1 && !eval.is_terminal2 1063 switch(eval.op){ 1064 case CQL_NOT: 1065 { 1066 CQLPredicate p = _preds[eval.opn1]; 1067 p.setInverted(); 1068 _preds.append(p); 1069 break; 1070 } 1071 case CQL_NOOP: 1072 humberto 1.1.2.1 { 1073 _preds.append(_preds[eval.opn1]); 1074 break; 1075 } 1076 case CQL_AND: 1077 {
1078 humberto 1.1.2.3 CQLPredicate p = _preds[eval.opn2]; 1079 p.appendPredicate(_preds[eval.opn1],AND);
1080 humberto 1.1.2.1 _preds.append(p);
1081 humberto 1.1.2.3 break;
1082 humberto 1.1.2.1 } 1083 case CQL_OR: 1084 {
1085 humberto 1.1.2.3 CQLPredicate p = _preds[eval.opn2]; 1086 p.appendPredicate(_preds[eval.opn1],OR);
1087 humberto 1.1.2.1 _preds.append(p);
1088 humberto 1.1.2.3 break;
1089 humberto 1.1.2.1 } 1090 case CQL_EQ: 1091 case CQL_NE: 1092 case CQL_GT: 1093 case CQL_LT: 1094 case CQL_GE: 1095 case CQL_LE: 1096 case CQL_IS_NULL: 1097 case CQL_IS_NOT_NULL: break; 1098 1099 } 1100 1101 }
1102 humberto 1.1.2.3 } // end for(...) 1103 1104 _dnfPredicate = _preds[_preds.size()-1];
1105 humberto 1.1.2.1
1106 humberto 1.1.2.3 } // end if 1107 else{ // we just have a CQLSimplePredicate on the terminal_heap 1108 PEGASUS_ASSERT(terminal_heap.size() == 1); 1109 _dnfPredicate = CQLPredicate(terminal_heap[0]._simplePredicate,false); 1110 }
1111 humberto 1.1.2.1 } 1112 1113 CQLPredicate Cql2Dnf::getDnfPredicate(){ 1114 return _dnfPredicate; 1115 } 1116 1117 PEGASUS_NAMESPACE_END

No CVS admin address has been configured