1 /* Query - query parsing and evaluation 2 * 3 * The pattern matching is roughly based on code originally written 4 * by J. Kercheval, and on code written by Kenneth Almquist, though 5 * it shares no code. 6 * 7 * Copyright 2001-2006, Axel Dörfler, axeld@pinc-software.de. 8 * This file may be used under the terms of the MIT License. 9 */ 10 11 // Adjusted by Ingo Weinhold <bonefish@cs.tu-berlin.de> for usage in RAM FS. 12 13 14 #include "Query.h" 15 #include "Debug.h" 16 #include "Directory.h" 17 #include "Entry.h" 18 #include "Misc.h" 19 #include "Node.h" 20 #include "Volume.h" 21 #include "Index.h" 22 23 #include <SupportDefs.h> 24 #include <TypeConstants.h> 25 #include <AppDefs.h> 26 #include <fs_query.h> 27 28 #include <malloc.h> 29 #include <stdio.h> 30 #include <string.h> 31 32 33 // IndexWrapper 34 35 // constructor 36 IndexWrapper::IndexWrapper(Volume *volume) 37 : fVolume(volume), 38 fIndex(NULL) 39 { 40 } 41 42 // SetTo 43 status_t 44 IndexWrapper::SetTo(const char *name) 45 { 46 fIndex = NULL; 47 if (fVolume) 48 fIndex = fVolume->FindIndex(name); 49 return (fIndex ? B_OK : B_ENTRY_NOT_FOUND); 50 } 51 52 // Unset 53 void 54 IndexWrapper::Unset() 55 { 56 fIndex = NULL; 57 } 58 59 // Type 60 uint32 61 IndexWrapper::Type() const 62 { 63 return (fIndex ? fIndex->GetType() : 0); 64 } 65 66 // GetSize 67 off_t 68 IndexWrapper::GetSize() const 69 { 70 // Compute a fake "index size" based on the number of entries 71 // (1024 + 16 * entry count), so we don't need to adjust the code using it. 72 return 1024LL + (fIndex ? fIndex->CountEntries() : 0) * 16LL; 73 } 74 75 // KeySize 76 int32 77 IndexWrapper::KeySize() const 78 { 79 return (fIndex ? fIndex->GetKeyLength() : 0); 80 } 81 82 83 // IndexIterator 84 85 // constructor 86 IndexIterator::IndexIterator(IndexWrapper *indexWrapper) 87 : fIndexWrapper(indexWrapper), 88 fIterator(), 89 fInitialized(false) 90 { 91 } 92 93 // Find 94 status_t 95 IndexIterator::Find(const uint8 *const key, size_t keyLength) 96 { 97 status_t error = B_ENTRY_NOT_FOUND; 98 if (fIndexWrapper && fIndexWrapper->fIndex) { 99 // TODO: We actually don't want an exact Find() here, but rather a 100 // FindClose(). 101 fInitialized = fIndexWrapper->fIndex->Find(key, keyLength, &fIterator); 102 if (fInitialized) 103 error = B_OK; 104 } 105 return error; 106 } 107 108 // GetNextEntry 109 status_t 110 IndexIterator::GetNextEntry(uint8 *buffer, uint16 *_keyLength, 111 size_t /*bufferSize*/, Entry **_entry) 112 { 113 status_t error = B_ENTRY_NOT_FOUND; 114 if (fIndexWrapper && fIndexWrapper->fIndex) { 115 // init iterator, if not done yet 116 if (!fInitialized) { 117 fIndexWrapper->fIndex->GetIterator(&fIterator); 118 fInitialized = true; 119 } 120 121 // get key 122 size_t keyLength; 123 if (Entry *entry = fIterator.GetCurrent(buffer, &keyLength)) { 124 *_keyLength = keyLength; 125 *_entry = entry; 126 error = B_OK; 127 } 128 129 // get next entry 130 fIterator.GetNext(); 131 } 132 return error; 133 } 134 135 136 // compare_integral 137 template<typename Key> 138 static inline 139 int 140 compare_integral(const Key &a, const Key &b) 141 { 142 if (a < b) 143 return -1; 144 else if (a > b) 145 return 1; 146 return 0; 147 } 148 149 // compare_keys 150 static 151 int 152 compare_keys(const uint8 *key1, size_t length1, const uint8 *key2, 153 size_t length2, uint32 type) 154 { 155 switch (type) { 156 case B_INT32_TYPE: 157 return compare_integral(*(int32*)key1, *(int32*)key2); 158 case B_UINT32_TYPE: 159 return compare_integral(*(uint32*)key1, *(uint32*)key2); 160 case B_INT64_TYPE: 161 return compare_integral(*(int64*)key1, *(int64*)key2); 162 case B_UINT64_TYPE: 163 return compare_integral(*(uint64*)key1, *(uint64*)key2); 164 case B_FLOAT_TYPE: 165 return compare_integral(*(float*)key1, *(float*)key2); 166 case B_DOUBLE_TYPE: 167 return compare_integral(*(double*)key1, *(double*)key2); 168 case B_STRING_TYPE: 169 { 170 int result = strncmp((const char*)key1, (const char*)key2, 171 min(length1, length2)); 172 if (result == 0) { 173 result = compare_integral(strnlen((const char*)key1, length1), 174 strnlen((const char*)key2, length2)); 175 } 176 return result; 177 } 178 } 179 return -1; 180 } 181 182 // compareKeys 183 static inline 184 int 185 compareKeys(uint32 type, const uint8 *key1, size_t length1, const uint8 *key2, 186 size_t length2) 187 { 188 return compare_keys(key1, length1, key2, length2, type); 189 } 190 191 192 193 194 195 // The parser has a very static design, but it will do what is required. 196 // 197 // ParseOr(), ParseAnd(), ParseEquation() are guarantying the operator 198 // precedence, that is =,!=,>,<,>=,<= .. && .. ||. 199 // Apparently, the "!" (not) can only be used with brackets. 200 // 201 // If you think that there are too few NULL pointer checks in some places 202 // of the code, just read the beginning of the query constructor. 203 // The API is not fully available, just the Query and the Expression class 204 // are. 205 206 207 enum ops { 208 OP_NONE, 209 210 OP_AND, 211 OP_OR, 212 213 OP_EQUATION, 214 215 OP_EQUAL, 216 OP_UNEQUAL, 217 OP_GREATER_THAN, 218 OP_LESS_THAN, 219 OP_GREATER_THAN_OR_EQUAL, 220 OP_LESS_THAN_OR_EQUAL, 221 }; 222 223 enum match { 224 NO_MATCH = 0, 225 MATCH_OK = 1, 226 227 MATCH_BAD_PATTERN = -2, 228 MATCH_INVALID_CHARACTER 229 }; 230 231 // return values from isValidPattern() 232 enum { 233 PATTERN_INVALID_ESCAPE = -3, 234 PATTERN_INVALID_RANGE, 235 PATTERN_INVALID_SET 236 }; 237 238 union value { 239 int64 Int64; 240 uint64 Uint64; 241 int32 Int32; 242 uint32 Uint32; 243 float Float; 244 double Double; 245 char CString[kMaxIndexKeyLength]; 246 }; 247 248 // B_MIME_STRING_TYPE is defined in storage/Mime.h, but we 249 // don't need the whole file here; the type can't change anyway 250 #ifndef _MIME_H 251 # define B_MIME_STRING_TYPE 'MIMS' 252 #endif 253 254 class Term { 255 public: 256 Term(int8 op) : fOp(op), fParent(NULL) {} 257 virtual ~Term() {} 258 259 int8 Op() const { return fOp; } 260 261 void SetParent(Term *parent) { fParent = parent; } 262 Term *Parent() const { return fParent; } 263 264 virtual status_t Match(Entry *entry, Node* node, 265 const char *attribute = NULL, int32 type = 0, 266 const uint8 *key = NULL, size_t size = 0) = 0; 267 virtual void Complement() = 0; 268 269 virtual void CalculateScore(IndexWrapper &index) = 0; 270 virtual int32 Score() const = 0; 271 272 virtual status_t InitCheck() = 0; 273 274 virtual bool NeedsEntry() = 0; 275 276 #ifdef DEBUG 277 virtual void PrintToStream() = 0; 278 #endif 279 280 protected: 281 int8 fOp; 282 Term *fParent; 283 }; 284 285 // Although an Equation object is quite independent from the volume on which 286 // the query is run, there are some dependencies that are produced while 287 // querying: 288 // The type/size of the value, the score, and if it has an index or not. 289 // So you could run more than one query on the same volume, but it might return 290 // wrong values when it runs concurrently on another volume. 291 // That's not an issue right now, because we run single-threaded and don't use 292 // queries more than once. 293 294 class Equation : public Term { 295 public: 296 Equation(char **expr); 297 virtual ~Equation(); 298 299 virtual status_t InitCheck(); 300 301 status_t ParseQuotedString(char **_start, char **_end); 302 char *CopyString(char *start, char *end); 303 304 virtual status_t Match(Entry *entry, Node* node, 305 const char *attribute = NULL, int32 type = 0, 306 const uint8 *key = NULL, size_t size = 0); 307 virtual void Complement(); 308 309 status_t PrepareQuery(Volume *volume, IndexWrapper &index, IndexIterator **iterator, 310 bool queryNonIndexed); 311 status_t GetNextMatching(Volume *volume, IndexIterator *iterator, 312 struct dirent *dirent, size_t bufferSize); 313 314 virtual void CalculateScore(IndexWrapper &index); 315 virtual int32 Score() const { return fScore; } 316 317 virtual bool NeedsEntry(); 318 319 #ifdef DEBUG 320 virtual void PrintToStream(); 321 #endif 322 323 private: 324 Equation(const Equation &); 325 Equation &operator=(const Equation &); 326 // no implementation 327 328 status_t ConvertValue(type_code type); 329 bool CompareTo(const uint8 *value, uint16 size); 330 uint8 *Value() const { return (uint8 *)&fValue; } 331 status_t MatchEmptyString(); 332 333 char *fAttribute; 334 char *fString; 335 union value fValue; 336 type_code fType; 337 size_t fSize; 338 bool fIsPattern; 339 340 int32 fScore; 341 bool fHasIndex; 342 }; 343 344 class Operator : public Term { 345 public: 346 Operator(Term *,int8,Term *); 347 virtual ~Operator(); 348 349 Term *Left() const { return fLeft; } 350 Term *Right() const { return fRight; } 351 352 virtual status_t Match(Entry *entry, Node* node, 353 const char *attribute = NULL, int32 type = 0, 354 const uint8 *key = NULL, size_t size = 0); 355 virtual void Complement(); 356 357 virtual void CalculateScore(IndexWrapper &index); 358 virtual int32 Score() const; 359 360 virtual status_t InitCheck(); 361 362 virtual bool NeedsEntry(); 363 364 //Term *Copy() const; 365 #ifdef DEBUG 366 virtual void PrintToStream(); 367 #endif 368 369 private: 370 Operator(const Operator &); 371 Operator &operator=(const Operator &); 372 // no implementation 373 374 Term *fLeft,*fRight; 375 }; 376 377 378 //--------------------------------- 379 380 381 void 382 skipWhitespace(char **expr, int32 skip = 0) 383 { 384 char *string = (*expr) + skip; 385 while (*string == ' ' || *string == '\t') string++; 386 *expr = string; 387 } 388 389 390 void 391 skipWhitespaceReverse(char **expr,char *stop) 392 { 393 char *string = *expr; 394 while (string > stop && (*string == ' ' || *string == '\t')) string--; 395 *expr = string; 396 } 397 398 399 // #pragma mark - 400 401 402 uint32 403 utf8ToUnicode(char **string) 404 { 405 uint8 *bytes = (uint8 *)*string; 406 int32 length; 407 uint8 mask = 0x1f; 408 409 switch (bytes[0] & 0xf0) { 410 case 0xc0: 411 case 0xd0: length = 2; break; 412 case 0xe0: length = 3; break; 413 case 0xf0: 414 mask = 0x0f; 415 length = 4; 416 break; 417 default: 418 // valid 1-byte character 419 // and invalid characters 420 (*string)++; 421 return bytes[0]; 422 } 423 uint32 c = bytes[0] & mask; 424 int32 i = 1; 425 for (;i < length && (bytes[i] & 0x80) > 0;i++) 426 c = (c << 6) | (bytes[i] & 0x3f); 427 428 if (i < length) { 429 // invalid character 430 (*string)++; 431 return (uint32)bytes[0]; 432 } 433 *string += length; 434 return c; 435 } 436 437 438 int32 439 getFirstPatternSymbol(char *string) 440 { 441 char c; 442 443 for (int32 index = 0;(c = *string++);index++) { 444 if (c == '*' || c == '?' || c == '[') 445 return index; 446 } 447 return -1; 448 } 449 450 451 bool 452 isPattern(char *string) 453 { 454 return getFirstPatternSymbol(string) >= 0 ? true : false; 455 } 456 457 458 status_t 459 isValidPattern(char *pattern) 460 { 461 while (*pattern) { 462 switch (*pattern++) { 463 case '\\': 464 // the escape character must not be at the end of the pattern 465 if (!*pattern++) 466 return PATTERN_INVALID_ESCAPE; 467 break; 468 469 case '[': 470 if (pattern[0] == ']' || !pattern[0]) 471 return PATTERN_INVALID_SET; 472 473 while (*pattern != ']') { 474 if (*pattern == '\\' && !*++pattern) 475 return PATTERN_INVALID_ESCAPE; 476 477 if (!*pattern) 478 return PATTERN_INVALID_SET; 479 480 if (pattern[0] == '-' && pattern[1] == '-') 481 return PATTERN_INVALID_RANGE; 482 483 pattern++; 484 } 485 break; 486 } 487 } 488 return B_OK; 489 } 490 491 492 /** Matches the string against the given wildcard pattern. 493 * Returns either MATCH_OK, or NO_MATCH when everything went fine, 494 * or values < 0 (see enum at the top of Query.cpp) if an error 495 * occurs 496 */ 497 498 status_t 499 matchString(char *pattern, char *string) 500 { 501 while (*pattern) { 502 // end of string == valid end of pattern? 503 if (!string[0]) { 504 while (pattern[0] == '*') 505 pattern++; 506 return !pattern[0] ? MATCH_OK : NO_MATCH; 507 } 508 509 switch (*pattern++) { 510 case '?': 511 { 512 // match exactly one UTF-8 character; we are 513 // not interested in the result 514 utf8ToUnicode(&string); 515 break; 516 } 517 518 case '*': 519 { 520 // compact pattern 521 while (true) { 522 if (pattern[0] == '?') { 523 if (!*++string) 524 return NO_MATCH; 525 } else if (pattern[0] != '*') 526 break; 527 528 pattern++; 529 } 530 531 // if the pattern is done, we have matched the string 532 if (!pattern[0]) 533 return MATCH_OK; 534 535 while(true) { 536 // we have removed all occurences of '*' and '?' 537 if (pattern[0] == string[0] 538 || pattern[0] == '[' 539 || pattern[0] == '\\') { 540 status_t status = matchString(pattern,string); 541 if (status < B_OK || status == MATCH_OK) 542 return status; 543 } 544 545 // we could be nice here and just jump to the next 546 // UTF-8 character - but we wouldn't gain that much 547 // and it'd be slower (since we're checking for 548 // equality before entering the recursion) 549 if (!*++string) 550 return NO_MATCH; 551 } 552 break; 553 } 554 555 case '[': 556 { 557 bool invert = false; 558 if (pattern[0] == '^' || pattern[0] == '!') { 559 invert = true; 560 pattern++; 561 } 562 563 if (!pattern[0] || pattern[0] == ']') 564 return MATCH_BAD_PATTERN; 565 566 uint32 c = utf8ToUnicode(&string); 567 bool matched = false; 568 569 while (pattern[0] != ']') { 570 if (!pattern[0]) 571 return MATCH_BAD_PATTERN; 572 573 if (pattern[0] == '\\') 574 pattern++; 575 576 uint32 first = utf8ToUnicode(&pattern); 577 578 // Does this character match, or is this a range? 579 if (first == c) { 580 matched = true; 581 break; 582 } else if (pattern[0] == '-' && pattern[1] != ']' && pattern[1]) { 583 pattern++; 584 585 if (pattern[0] == '\\') { 586 pattern++; 587 if (!pattern[0]) 588 return MATCH_BAD_PATTERN; 589 } 590 uint32 last = utf8ToUnicode(&pattern); 591 592 if (c >= first && c <= last) { 593 matched = true; 594 break; 595 } 596 } 597 } 598 599 if (invert) 600 matched = !matched; 601 602 if (matched) { 603 while (pattern[0] != ']') { 604 if (!pattern[0]) 605 return MATCH_BAD_PATTERN; 606 pattern++; 607 } 608 pattern++; 609 break; 610 } 611 return NO_MATCH; 612 } 613 614 case '\\': 615 if (!pattern[0]) 616 return MATCH_BAD_PATTERN; 617 // supposed to fall through 618 default: 619 if (pattern[-1] != string[0]) 620 return NO_MATCH; 621 string++; 622 break; 623 } 624 } 625 626 if (string[0]) 627 return NO_MATCH; 628 629 return MATCH_OK; 630 } 631 632 633 // #pragma mark - 634 635 636 Equation::Equation(char **expr) 637 : Term(OP_EQUATION), 638 fAttribute(NULL), 639 fString(NULL), 640 fType(0), 641 fIsPattern(false) 642 { 643 char *string = *expr; 644 char *start = string; 645 char *end = NULL; 646 647 // Since the equation is the integral part of any query, we're just parsing 648 // the whole thing here. 649 // The whitespace at the start is already removed in Expression::ParseEquation() 650 651 if (*start == '"' || *start == '\'') { 652 // string is quoted (start has to be on the beginning of a string) 653 if (ParseQuotedString(&start, &end) < B_OK) 654 return; 655 656 // set string to a valid start of the equation symbol 657 string = end + 2; 658 skipWhitespace(&string); 659 if (*string != '=' && *string != '<' && *string != '>' && *string != '!') { 660 *expr = string; 661 return; 662 } 663 } else { 664 // search the (in)equation for the actual equation symbol (and for other operators 665 // in case the equation is malformed) 666 while (*string && *string != '=' && *string != '<' && *string != '>' && *string != '!' 667 && *string != '&' && *string != '|') 668 string++; 669 670 // get the attribute string (and trim whitespace), in case 671 // the string was not quoted 672 end = string - 1; 673 skipWhitespaceReverse(&end, start); 674 } 675 676 // attribute string is empty (which is not allowed) 677 if (start > end) 678 return; 679 680 // at this point, "start" points to the beginning of the string, "end" points 681 // to the last character of the string, and "string" points to the first 682 // character of the equation symbol 683 684 // test for the right symbol (as this doesn't need any memory) 685 switch (*string) { 686 case '=': 687 fOp = OP_EQUAL; 688 break; 689 case '>': 690 fOp = *(string + 1) == '=' ? OP_GREATER_THAN_OR_EQUAL : OP_GREATER_THAN; 691 break; 692 case '<': 693 fOp = *(string + 1) == '=' ? OP_LESS_THAN_OR_EQUAL : OP_LESS_THAN; 694 break; 695 case '!': 696 if (*(string + 1) != '=') 697 return; 698 fOp = OP_UNEQUAL; 699 break; 700 701 // any invalid characters will be rejected 702 default: 703 *expr = string; 704 return; 705 } 706 // lets change "start" to point to the first character after the symbol 707 if (*(string + 1) == '=') 708 string++; 709 string++; 710 skipWhitespace(&string); 711 712 // allocate & copy the attribute string 713 714 fAttribute = CopyString(start, end); 715 if (fAttribute == NULL) 716 return; 717 718 start = string; 719 if (*start == '"' || *start == '\'') { 720 // string is quoted (start has to be on the beginning of a string) 721 if (ParseQuotedString(&start, &end) < B_OK) 722 return; 723 724 string = end + 2; 725 skipWhitespace(&string); 726 } else { 727 while (*string && *string != '&' && *string != '|' && *string != ')') 728 string++; 729 730 end = string - 1; 731 skipWhitespaceReverse(&end, start); 732 } 733 734 // at this point, "start" will point to the first character of the value, 735 // "end" will point to its last character, and "start" to the first non- 736 // whitespace character after the value string 737 738 fString = CopyString(start, end); 739 if (fString == NULL) 740 return; 741 742 // patterns are only allowed for these operations (and strings) 743 if (fOp == OP_EQUAL || fOp == OP_UNEQUAL) { 744 fIsPattern = isPattern(fString); 745 if (fIsPattern && isValidPattern(fString) < B_OK) { 746 // we only want to have valid patterns; setting fString 747 // to NULL will cause InitCheck() to fail 748 free(fString); 749 fString = NULL; 750 } 751 } 752 753 *expr = string; 754 } 755 756 757 Equation::~Equation() 758 { 759 if (fAttribute != NULL) 760 free(fAttribute); 761 if (fString != NULL) 762 free(fString); 763 } 764 765 766 status_t 767 Equation::InitCheck() 768 { 769 if (fAttribute == NULL 770 || fString == NULL 771 || fOp == OP_NONE) 772 return B_BAD_VALUE; 773 774 return B_OK; 775 } 776 777 778 status_t 779 Equation::ParseQuotedString(char **_start, char **_end) 780 { 781 char *start = *_start; 782 char quote = *start++; 783 char *end = start; 784 785 for (;*end && *end != quote;end++) { 786 if (*end == '\\') 787 end++; 788 } 789 if (*end == '\0') 790 return B_BAD_VALUE; 791 792 *_start = start; 793 *_end = end - 1; 794 795 return B_OK; 796 } 797 798 799 char * 800 Equation::CopyString(char *start, char *end) 801 { 802 // end points to the last character of the string - and the length 803 // also has to include the null-termination 804 int32 length = end + 2 - start; 805 // just to make sure; since that's the max. attribute name length and 806 // the max. string in an index, it make sense to have it that way 807 if (length > (int32)kMaxIndexKeyLength || length <= 0) 808 return NULL; 809 810 char *copy = (char *)malloc(length); 811 if (copy == NULL) 812 return NULL; 813 814 memcpy(copy,start,length - 1); 815 copy[length - 1] = '\0'; 816 817 return copy; 818 } 819 820 821 status_t 822 Equation::ConvertValue(type_code type) 823 { 824 // Has the type already been converted? 825 if (type == fType) 826 return B_OK; 827 828 char *string = fString; 829 830 switch (type) { 831 case B_MIME_STRING_TYPE: 832 type = B_STRING_TYPE; 833 // supposed to fall through 834 case B_STRING_TYPE: 835 strncpy(fValue.CString, string, kMaxIndexKeyLength); 836 fValue.CString[kMaxIndexKeyLength - 1] = '\0'; 837 fSize = strlen(fValue.CString); 838 break; 839 case B_INT32_TYPE: 840 fValue.Int32 = strtol(string, &string, 0); 841 fSize = sizeof(int32); 842 break; 843 case B_UINT32_TYPE: 844 fValue.Int32 = strtoul(string, &string, 0); 845 fSize = sizeof(uint32); 846 break; 847 case B_INT64_TYPE: 848 fValue.Int64 = strtoll(string, &string, 0); 849 fSize = sizeof(int64); 850 break; 851 case B_UINT64_TYPE: 852 fValue.Uint64 = strtoull(string, &string, 0); 853 fSize = sizeof(uint64); 854 break; 855 case B_FLOAT_TYPE: 856 fValue.Float = strtod(string, &string); 857 fSize = sizeof(float); 858 break; 859 case B_DOUBLE_TYPE: 860 fValue.Double = strtod(string, &string); 861 fSize = sizeof(double); 862 break; 863 default: 864 FATAL(("query value conversion to 0x%lx requested!\n", type)); 865 // should we fail here or just do a safety int32 conversion? 866 return B_ERROR; 867 } 868 869 fType = type; 870 871 // patterns are only allowed for string types 872 if (fType != B_STRING_TYPE && fIsPattern) 873 fIsPattern = false; 874 875 return B_OK; 876 } 877 878 879 /** Returns true when the key matches the equation. You have to 880 * call ConvertValue() before this one. 881 */ 882 883 bool 884 Equation::CompareTo(const uint8 *value, uint16 size) 885 { 886 int32 compare; 887 888 // fIsPattern is only true if it's a string type, and fOp OP_EQUAL, or OP_UNEQUAL 889 if (fIsPattern) { 890 // we have already validated the pattern, so we don't check for failing 891 // here - if something is broken, and matchString() returns an error, 892 // we just don't match 893 compare = matchString(fValue.CString, (char *)value) == MATCH_OK ? 0 : 1; 894 } else 895 compare = compareKeys(fType, value, size, Value(), fSize); 896 897 switch (fOp) { 898 case OP_EQUAL: 899 return compare == 0; 900 case OP_UNEQUAL: 901 return compare != 0; 902 case OP_LESS_THAN: 903 return compare < 0; 904 case OP_LESS_THAN_OR_EQUAL: 905 return compare <= 0; 906 case OP_GREATER_THAN: 907 return compare > 0; 908 case OP_GREATER_THAN_OR_EQUAL: 909 return compare >= 0; 910 } 911 FATAL(("Unknown/Unsupported operation: %d\n", fOp)); 912 return false; 913 } 914 915 916 void 917 Equation::Complement() 918 { 919 D(if (fOp <= OP_EQUATION || fOp > OP_LESS_THAN_OR_EQUAL) { 920 FATAL(("op out of range!")); 921 return; 922 }); 923 924 int8 complementOp[] = {OP_UNEQUAL, OP_EQUAL, OP_LESS_THAN_OR_EQUAL, 925 OP_GREATER_THAN_OR_EQUAL, OP_LESS_THAN, OP_GREATER_THAN}; 926 fOp = complementOp[fOp - OP_EQUAL]; 927 } 928 929 930 status_t 931 Equation::MatchEmptyString() 932 { 933 // there is no matching attribute, we will just bail out if we 934 // already know that our value is not of a string type. 935 // If not, it will be converted to a string - and then be compared with "". 936 // That's why we have to call ConvertValue() here - but it will be 937 // a cheap call for the next time 938 // Should we do this only for OP_UNEQUAL? 939 if (fType != 0 && fType != B_STRING_TYPE) 940 return NO_MATCH; 941 942 status_t status = ConvertValue(B_STRING_TYPE); 943 if (status == B_OK) 944 status = CompareTo((const uint8 *)"", fSize) ? MATCH_OK : NO_MATCH; 945 946 return status; 947 } 948 949 950 /** Matches the inode's attribute value with the equation. 951 * Returns MATCH_OK if it matches, NO_MATCH if not, < 0 if something went wrong 952 */ 953 954 status_t 955 Equation::Match(Entry *entry, Node* node, const char *attributeName, int32 type, 956 const uint8 *key, size_t size) 957 { 958 // get a pointer to the attribute in question 959 union value value; 960 const uint8 *buffer; 961 962 // first, check if we are matching for a live query and use that value 963 if (attributeName != NULL && !strcmp(fAttribute, attributeName)) { 964 if (key == NULL) { 965 if (type == B_STRING_TYPE) { 966 // special case: a NULL "name" means the entry has been removed 967 // or not yet been added -- we refuse to match, whatever the 968 // pattern 969 if (!strcmp(fAttribute, "name")) 970 return NO_MATCH; 971 972 return MatchEmptyString(); 973 } 974 975 return NO_MATCH; 976 } 977 buffer = const_cast<uint8 *>(key); 978 } else if (!strcmp(fAttribute, "name")) { 979 // if not, check for "fake" attributes, "name", "size", "last_modified", 980 if (!entry) 981 return B_ERROR; 982 buffer = (uint8 *)entry->GetName(); 983 if (buffer == NULL) 984 return B_ERROR; 985 986 type = B_STRING_TYPE; 987 size = strlen((const char *)buffer); 988 } else if (!strcmp(fAttribute,"size")) { 989 value.Int64 = node->GetSize(); 990 buffer = (uint8 *)&value; 991 type = B_INT64_TYPE; 992 } else if (!strcmp(fAttribute,"last_modified")) { 993 value.Int32 = node->GetMTime(); 994 buffer = (uint8 *)&value; 995 type = B_INT32_TYPE; 996 } else { 997 // then for attributes 998 Attribute *attribute = NULL; 999 1000 if (node->FindAttribute(fAttribute, &attribute) == B_OK) { 1001 attribute->GetKey(&buffer, &size); 1002 type = attribute->GetType(); 1003 } else 1004 return MatchEmptyString(); 1005 } 1006 // prepare own value for use, if it is possible to convert it 1007 status_t status = ConvertValue(type); 1008 if (status == B_OK) 1009 status = CompareTo(buffer, size) ? MATCH_OK : NO_MATCH; 1010 1011 RETURN_ERROR(status); 1012 } 1013 1014 1015 void 1016 Equation::CalculateScore(IndexWrapper &index) 1017 { 1018 // As always, these values could be tuned and refined. 1019 // And the code could also need some real world testing :-) 1020 1021 // do we have to operate on a "foreign" index? 1022 if (fOp == OP_UNEQUAL || index.SetTo(fAttribute) < B_OK) { 1023 fScore = 0; 1024 return; 1025 } 1026 1027 // if we have a pattern, how much does it help our search? 1028 if (fIsPattern) 1029 fScore = getFirstPatternSymbol(fString) << 3; 1030 else { 1031 // Score by operator 1032 if (fOp == OP_EQUAL) 1033 // higher than pattern="255 chars+*" 1034 fScore = 2048; 1035 else 1036 // the pattern search is regarded cheaper when you have at 1037 // least one character to set your index to 1038 fScore = 5; 1039 } 1040 1041 // take index size into account (1024 is the current node size 1042 // in our B+trees) 1043 // 2048 * 2048 == 4194304 is the maximum score (for an empty 1044 // tree, since the header + 1 node are already 2048 bytes) 1045 fScore = fScore * ((2048 * 1024LL) / index.GetSize()); 1046 } 1047 1048 1049 status_t 1050 Equation::PrepareQuery(Volume */*volume*/, IndexWrapper &index, IndexIterator **iterator, bool queryNonIndexed) 1051 { 1052 status_t status = index.SetTo(fAttribute); 1053 1054 // if we should query attributes without an index, we can just proceed here 1055 if (status < B_OK && !queryNonIndexed) 1056 return B_ENTRY_NOT_FOUND; 1057 1058 type_code type; 1059 1060 // special case for OP_UNEQUAL - it will always operate through the whole index 1061 // but we need the call to the original index to get the correct type 1062 if (status < B_OK || fOp == OP_UNEQUAL) { 1063 // Try to get an index that holds all files (name) 1064 // Also sets the default type for all attributes without index 1065 // to string. 1066 type = status < B_OK ? B_STRING_TYPE : index.Type(); 1067 1068 if (index.SetTo("name") < B_OK) 1069 return B_ENTRY_NOT_FOUND; 1070 1071 fHasIndex = false; 1072 } else { 1073 fHasIndex = true; 1074 type = index.Type(); 1075 } 1076 1077 if (ConvertValue(type) < B_OK) 1078 return B_BAD_VALUE; 1079 1080 *iterator = new IndexIterator(&index); 1081 if (*iterator == NULL) 1082 return B_NO_MEMORY; 1083 1084 if ((fOp == OP_EQUAL || fOp == OP_GREATER_THAN || fOp == OP_GREATER_THAN_OR_EQUAL 1085 || fIsPattern) 1086 && fHasIndex) { 1087 // set iterator to the exact position 1088 1089 int32 keySize = index.KeySize(); 1090 1091 // at this point, fIsPattern is only true if it's a string type, and fOp 1092 // is either OP_EQUAL or OP_UNEQUAL 1093 if (fIsPattern) { 1094 // let's see if we can use the beginning of the key for positioning 1095 // the iterator and adjust the key size; if not, just leave the 1096 // iterator at the start and return success 1097 keySize = getFirstPatternSymbol(fString); 1098 if (keySize <= 0) 1099 return B_OK; 1100 } 1101 1102 if (keySize == 0) { 1103 // B_STRING_TYPE doesn't have a fixed length, so it was set 1104 // to 0 before - we compute the correct value here 1105 if (fType == B_STRING_TYPE) { 1106 keySize = strlen(fValue.CString); 1107 1108 // The empty string is a special case - we normally don't check 1109 // for the trailing null byte, in the case for the empty string 1110 // we do it explicitly, because there can't be keys in the B+tree 1111 // with a length of zero 1112 if (keySize == 0) 1113 keySize = 1; 1114 } else 1115 RETURN_ERROR(B_ENTRY_NOT_FOUND); 1116 } 1117 1118 status = (*iterator)->Find(Value(), keySize); 1119 if (fOp == OP_EQUAL && !fIsPattern) 1120 return status; 1121 else if (status == B_ENTRY_NOT_FOUND 1122 && (fIsPattern || fOp == OP_GREATER_THAN || fOp == OP_GREATER_THAN_OR_EQUAL)) 1123 return B_OK; 1124 1125 RETURN_ERROR(status); 1126 } 1127 1128 return B_OK; 1129 } 1130 1131 1132 status_t 1133 Equation::GetNextMatching(Volume *volume, IndexIterator *iterator, 1134 struct dirent *dirent, size_t bufferSize) 1135 { 1136 while (true) { 1137 union value indexValue; 1138 uint16 keyLength; 1139 Entry *entry = NULL; 1140 1141 status_t status = iterator->GetNextEntry((uint8*)&indexValue, &keyLength, 1142 (uint16)sizeof(indexValue), &entry); 1143 if (status < B_OK) 1144 return status; 1145 1146 // only compare against the index entry when this is the correct 1147 // index for the equation 1148 if (fHasIndex && !CompareTo((uint8 *)&indexValue, keyLength)) { 1149 // They aren't equal? let the operation decide what to do 1150 // Since we always start at the beginning of the index (or the correct 1151 // position), only some needs to be stopped if the entry doesn't fit. 1152 if (fOp == OP_LESS_THAN 1153 || fOp == OP_LESS_THAN_OR_EQUAL 1154 || (fOp == OP_EQUAL && !fIsPattern)) 1155 return B_ENTRY_NOT_FOUND; 1156 1157 continue; 1158 } 1159 1160 // ToDo: check user permissions here - but which one?! 1161 // we could filter out all those where we don't have 1162 // read access... (we should check for every parent 1163 // directory if the X_OK is allowed) 1164 // Although it's quite expensive to open all parents, 1165 // it's likely that the application that runs the 1166 // query will do something similar (and we don't have 1167 // to do it for root, either). 1168 1169 // go up in the tree until a &&-operator is found, and check if the 1170 // inode matches with the rest of the expression - we don't have to 1171 // check ||-operators for that 1172 Term *term = this; 1173 status = MATCH_OK; 1174 1175 if (!fHasIndex) 1176 status = Match(entry, entry->GetNode()); 1177 1178 while (term != NULL && status == MATCH_OK) { 1179 Operator *parent = (Operator *)term->Parent(); 1180 if (parent == NULL) 1181 break; 1182 1183 if (parent->Op() == OP_AND) { 1184 // choose the other child of the parent 1185 Term *other = parent->Right(); 1186 if (other == term) 1187 other = parent->Left(); 1188 1189 if (other == NULL) { 1190 FATAL(("&&-operator has only one child... (parent = %p)\n", parent)); 1191 break; 1192 } 1193 status = other->Match(entry, entry->GetNode()); 1194 if (status < 0) { 1195 REPORT_ERROR(status); 1196 status = NO_MATCH; 1197 } 1198 } 1199 term = (Term *)parent; 1200 } 1201 1202 if (status == MATCH_OK) { 1203 size_t nameLen = strlen(entry->GetName()); 1204 1205 // check, whether the entry fits into the buffer, 1206 // and fill it in 1207 size_t length = (dirent->d_name + nameLen + 1) - (char*)dirent; 1208 if (length > bufferSize) 1209 RETURN_ERROR(B_BUFFER_OVERFLOW); 1210 1211 dirent->d_dev = volume->GetID(); 1212 dirent->d_ino = entry->GetNode()->GetID(); 1213 dirent->d_pdev = volume->GetID(); 1214 dirent->d_pino = entry->GetParent()->GetID(); 1215 1216 memcpy(dirent->d_name, entry->GetName(), nameLen); 1217 dirent->d_name[nameLen] = '\0'; 1218 dirent->d_reclen = length; 1219 } 1220 1221 if (status == MATCH_OK) 1222 return B_OK; 1223 } 1224 RETURN_ERROR(B_ERROR); 1225 } 1226 1227 1228 bool 1229 Equation::NeedsEntry() 1230 { 1231 return strcmp(fAttribute, "name") == 0; 1232 } 1233 1234 1235 // #pragma mark - 1236 1237 1238 Operator::Operator(Term *left, int8 op, Term *right) 1239 : Term(op), 1240 fLeft(left), 1241 fRight(right) 1242 { 1243 if (left) 1244 left->SetParent(this); 1245 if (right) 1246 right->SetParent(this); 1247 } 1248 1249 1250 Operator::~Operator() 1251 { 1252 delete fLeft; 1253 delete fRight; 1254 } 1255 1256 1257 status_t 1258 Operator::Match(Entry *entry, Node* node, const char *attribute, 1259 int32 type, const uint8 *key, size_t size) 1260 { 1261 if (fOp == OP_AND) { 1262 status_t status = fLeft->Match(entry, node, attribute, type, key, size); 1263 if (status != MATCH_OK) 1264 return status; 1265 1266 return fRight->Match(entry, node, attribute, type, key, size); 1267 } else { 1268 // choose the term with the better score for OP_OR 1269 if (fRight->Score() > fLeft->Score()) { 1270 status_t status = fRight->Match(entry, node, attribute, type, key, 1271 size); 1272 if (status != NO_MATCH) 1273 return status; 1274 } 1275 return fLeft->Match(entry, node, attribute, type, key, size); 1276 } 1277 } 1278 1279 1280 void 1281 Operator::Complement() 1282 { 1283 if (fOp == OP_AND) 1284 fOp = OP_OR; 1285 else 1286 fOp = OP_AND; 1287 1288 fLeft->Complement(); 1289 fRight->Complement(); 1290 } 1291 1292 1293 void 1294 Operator::CalculateScore(IndexWrapper &index) 1295 { 1296 fLeft->CalculateScore(index); 1297 fRight->CalculateScore(index); 1298 } 1299 1300 1301 int32 1302 Operator::Score() const 1303 { 1304 if (fOp == OP_AND) { 1305 // return the one with the better score 1306 if (fRight->Score() > fLeft->Score()) 1307 return fRight->Score(); 1308 1309 return fLeft->Score(); 1310 } 1311 1312 // for OP_OR, be honest, and return the one with the worse score 1313 if (fRight->Score() < fLeft->Score()) 1314 return fRight->Score(); 1315 1316 return fLeft->Score(); 1317 } 1318 1319 1320 status_t 1321 Operator::InitCheck() 1322 { 1323 if (fOp != OP_AND && fOp != OP_OR 1324 || fLeft == NULL || fLeft->InitCheck() < B_OK 1325 || fRight == NULL || fRight->InitCheck() < B_OK) 1326 return B_ERROR; 1327 1328 return B_OK; 1329 } 1330 1331 1332 bool 1333 Operator::NeedsEntry() 1334 { 1335 return ((fLeft && fLeft->NeedsEntry()) || (fRight && fRight->NeedsEntry())); 1336 } 1337 1338 1339 #if 0 1340 Term * 1341 Operator::Copy() const 1342 { 1343 if (fEquation != NULL) { 1344 Equation *equation = new Equation(*fEquation); 1345 if (equation == NULL) 1346 return NULL; 1347 1348 Term *term = new Term(equation); 1349 if (term == NULL) 1350 delete equation; 1351 1352 return term; 1353 } 1354 1355 Term *left = NULL, *right = NULL; 1356 1357 if (fLeft != NULL && (left = fLeft->Copy()) == NULL) 1358 return NULL; 1359 if (fRight != NULL && (right = fRight->Copy()) == NULL) { 1360 delete left; 1361 return NULL; 1362 } 1363 1364 Term *term = new Term(left,fOp,right); 1365 if (term == NULL) { 1366 delete left; 1367 delete right; 1368 return NULL; 1369 } 1370 return term; 1371 } 1372 #endif 1373 1374 1375 // #pragma mark - 1376 1377 #ifdef DEBUG 1378 void 1379 Operator::PrintToStream() 1380 { 1381 D(__out("( ")); 1382 if (fLeft != NULL) 1383 fLeft->PrintToStream(); 1384 1385 char *op; 1386 switch (fOp) { 1387 case OP_OR: op = "OR"; break; 1388 case OP_AND: op = "AND"; break; 1389 default: op = "?"; break; 1390 } 1391 D(__out(" %s ",op)); 1392 1393 if (fRight != NULL) 1394 fRight->PrintToStream(); 1395 1396 D(__out(" )")); 1397 } 1398 1399 1400 void 1401 Equation::PrintToStream() 1402 { 1403 char *symbol = "???"; 1404 switch (fOp) { 1405 case OP_EQUAL: symbol = "=="; break; 1406 case OP_UNEQUAL: symbol = "!="; break; 1407 case OP_GREATER_THAN: symbol = ">"; break; 1408 case OP_GREATER_THAN_OR_EQUAL: symbol = ">="; break; 1409 case OP_LESS_THAN: symbol = "<"; break; 1410 case OP_LESS_THAN_OR_EQUAL: symbol = "<="; break; 1411 } 1412 D(__out("[\"%s\" %s \"%s\"]", fAttribute, symbol, fString)); 1413 } 1414 1415 #endif /* DEBUG */ 1416 1417 // #pragma mark - 1418 1419 1420 Expression::Expression(char *expr) 1421 { 1422 if (expr == NULL) 1423 return; 1424 1425 fTerm = ParseOr(&expr); 1426 if (fTerm != NULL && fTerm->InitCheck() < B_OK) { 1427 FATAL(("Corrupt tree in expression!\n")); 1428 delete fTerm; 1429 fTerm = NULL; 1430 } 1431 D(if (fTerm != NULL) { 1432 fTerm->PrintToStream(); 1433 D(__out("\n")); 1434 if (*expr != '\0') 1435 PRINT(("Unexpected end of string: \"%s\"!\n", expr)); 1436 }); 1437 fPosition = expr; 1438 } 1439 1440 1441 Expression::~Expression() 1442 { 1443 delete fTerm; 1444 } 1445 1446 1447 Term * 1448 Expression::ParseEquation(char **expr) 1449 { 1450 skipWhitespace(expr); 1451 1452 bool nott = false; // note: not is a C++ keyword 1453 if (**expr == '!') { 1454 skipWhitespace(expr, 1); 1455 if (**expr != '(') 1456 return NULL; 1457 1458 nott = true; 1459 } 1460 1461 if (**expr == ')') { 1462 // shouldn't be handled here 1463 return NULL; 1464 } else if (**expr == '(') { 1465 skipWhitespace(expr, 1); 1466 1467 Term *term = ParseOr(expr); 1468 1469 skipWhitespace(expr); 1470 1471 if (**expr != ')') { 1472 delete term; 1473 return NULL; 1474 } 1475 1476 // If the term is negated, we just complement the tree, to get 1477 // rid of the not, a.k.a. DeMorgan's Law. 1478 if (nott) 1479 term->Complement(); 1480 1481 skipWhitespace(expr, 1); 1482 1483 return term; 1484 } 1485 1486 Equation *equation = new Equation(expr); 1487 if (equation == NULL || equation->InitCheck() < B_OK) { 1488 delete equation; 1489 return NULL; 1490 } 1491 return equation; 1492 } 1493 1494 1495 Term * 1496 Expression::ParseAnd(char **expr) 1497 { 1498 Term *left = ParseEquation(expr); 1499 if (left == NULL) 1500 return NULL; 1501 1502 while (IsOperator(expr,'&')) { 1503 Term *right = ParseAnd(expr); 1504 Term *newParent = NULL; 1505 1506 if (right == NULL || (newParent = new Operator(left, OP_AND, right)) == NULL) { 1507 delete left; 1508 delete right; 1509 1510 return NULL; 1511 } 1512 left = newParent; 1513 } 1514 1515 return left; 1516 } 1517 1518 1519 Term * 1520 Expression::ParseOr(char **expr) 1521 { 1522 Term *left = ParseAnd(expr); 1523 if (left == NULL) 1524 return NULL; 1525 1526 while (IsOperator(expr,'|')) { 1527 Term *right = ParseAnd(expr); 1528 Term *newParent = NULL; 1529 1530 if (right == NULL || (newParent = new Operator(left, OP_OR, right)) == NULL) { 1531 delete left; 1532 delete right; 1533 1534 return NULL; 1535 } 1536 left = newParent; 1537 } 1538 1539 return left; 1540 } 1541 1542 1543 bool 1544 Expression::IsOperator(char **expr, char op) 1545 { 1546 char *string = *expr; 1547 1548 if (*string == op && *(string + 1) == op) { 1549 *expr += 2; 1550 return true; 1551 } 1552 return false; 1553 } 1554 1555 1556 status_t 1557 Expression::InitCheck() 1558 { 1559 if (fTerm == NULL) 1560 return B_BAD_VALUE; 1561 1562 return B_OK; 1563 } 1564 1565 1566 // #pragma mark - 1567 1568 1569 Query::Query(Volume *volume, Expression *expression, uint32 flags) 1570 : 1571 fVolume(volume), 1572 fExpression(expression), 1573 fCurrent(NULL), 1574 fIterator(NULL), 1575 fIndex(volume), 1576 fFlags(flags), 1577 fPort(-1), 1578 fNeedsEntry(false) 1579 { 1580 // if the expression has a valid root pointer, the whole tree has 1581 // already passed the sanity check, so that we don't have to check 1582 // every pointer 1583 if (volume == NULL || expression == NULL || expression->Root() == NULL) 1584 return; 1585 1586 // create index on the stack and delete it afterwards 1587 fExpression->Root()->CalculateScore(fIndex); 1588 fIndex.Unset(); 1589 1590 fNeedsEntry = fExpression->Root()->NeedsEntry(); 1591 1592 Rewind(); 1593 1594 if (fFlags & B_LIVE_QUERY) 1595 volume->AddQuery(this); 1596 } 1597 1598 1599 Query::~Query() 1600 { 1601 if (fFlags & B_LIVE_QUERY) 1602 fVolume->RemoveQuery(this); 1603 } 1604 1605 1606 status_t 1607 Query::Rewind() 1608 { 1609 // free previous stuff 1610 1611 fStack.MakeEmpty(); 1612 1613 delete fIterator; 1614 fIterator = NULL; 1615 fCurrent = NULL; 1616 1617 // put the whole expression on the stack 1618 1619 Stack<Term *> stack; 1620 stack.Push(fExpression->Root()); 1621 1622 Term *term; 1623 while (stack.Pop(&term)) { 1624 if (term->Op() < OP_EQUATION) { 1625 Operator *op = (Operator *)term; 1626 1627 if (op->Op() == OP_OR) { 1628 stack.Push(op->Left()); 1629 stack.Push(op->Right()); 1630 } else { 1631 // For OP_AND, we can use the scoring system to decide which path to add 1632 if (op->Right()->Score() > op->Left()->Score()) 1633 stack.Push(op->Right()); 1634 else 1635 stack.Push(op->Left()); 1636 } 1637 } else if (term->Op() == OP_EQUATION || fStack.Push((Equation *)term) < B_OK) 1638 FATAL(("Unknown term on stack or stack error")); 1639 } 1640 1641 return B_OK; 1642 } 1643 1644 1645 status_t 1646 Query::GetNextEntry(struct dirent *dirent, size_t size) 1647 { 1648 // If we don't have an equation to use yet/anymore, get a new one 1649 // from the stack 1650 while (true) { 1651 if (fIterator == NULL) { 1652 if (!fStack.Pop(&fCurrent) 1653 || fCurrent == NULL 1654 || fCurrent->PrepareQuery(fVolume, fIndex, &fIterator, 1655 fFlags & B_QUERY_NON_INDEXED) < B_OK) 1656 return B_ENTRY_NOT_FOUND; 1657 } 1658 if (fCurrent == NULL) 1659 RETURN_ERROR(B_ERROR); 1660 1661 status_t status = fCurrent->GetNextMatching(fVolume, fIterator, dirent, size); 1662 if (status < B_OK) { 1663 delete fIterator; 1664 fIterator = NULL; 1665 fCurrent = NULL; 1666 } else { 1667 // only return if we have another entry 1668 return B_OK; 1669 } 1670 } 1671 } 1672 1673 1674 void 1675 Query::SetLiveMode(port_id port, int32 token) 1676 { 1677 fPort = port; 1678 fToken = token; 1679 1680 if ((fFlags & B_LIVE_QUERY) == 0) { 1681 // you can decide at any point to set the live query mode, 1682 // only live queries have to be updated by attribute changes 1683 fFlags |= B_LIVE_QUERY; 1684 fVolume->AddQuery(this); 1685 } 1686 } 1687 1688 1689 static void 1690 send_entry_notification(port_id port, int32 token, Volume* volume, Entry* entry, 1691 bool created) 1692 { 1693 if (created) { 1694 notify_query_entry_created(port, token, volume->GetID(), 1695 entry->GetParent()->GetID(), entry->GetName(), 1696 entry->GetNode()->GetID()); 1697 } else { 1698 notify_query_entry_removed(port, token, volume->GetID(), 1699 entry->GetParent()->GetID(), entry->GetName(), 1700 entry->GetNode()->GetID()); 1701 } 1702 } 1703 1704 1705 void 1706 Query::LiveUpdate(Entry *entry, Node* node, const char *attribute, int32 type, 1707 const uint8 *oldKey, size_t oldLength, const uint8 *newKey, 1708 size_t newLength) 1709 { 1710 PRINT(("%p->Query::LiveUpdate(%p, %p, \"%s\", 0x%lx, %p, %lu, %p, %lu)\n", 1711 this, entry, node, attribute, type, oldKey, oldLength, newKey, newLength)); 1712 if (fPort < 0 || fExpression == NULL || node == NULL || attribute == NULL) 1713 return; 1714 1715 // ToDo: check if the attribute is part of the query at all... 1716 1717 // If no entry has been supplied, but the we need one for the evaluation 1718 // (i.e. the "name" attribute is used), we invoke ourselves for all entries 1719 // referring to the given node. 1720 if (!entry && fNeedsEntry) { 1721 entry = node->GetFirstReferrer(); 1722 while (entry) { 1723 LiveUpdate(entry, node, attribute, type, oldKey, oldLength, newKey, 1724 newLength); 1725 entry = node->GetNextReferrer(entry); 1726 } 1727 return; 1728 } 1729 1730 status_t oldStatus = fExpression->Root()->Match(entry, node, attribute, 1731 type, oldKey, oldLength); 1732 status_t newStatus = fExpression->Root()->Match(entry, node, attribute, 1733 type, newKey, newLength); 1734 PRINT((" oldStatus: 0x%lx, newStatus: 0x%lx\n", oldStatus, newStatus)); 1735 1736 bool created; 1737 if (oldStatus == MATCH_OK && newStatus == MATCH_OK) { 1738 // only send out a notification if the name was changed 1739 if (oldKey == NULL || strcmp(attribute,"name")) 1740 return; 1741 1742 if (entry) { 1743 // entry should actually always be given, when the changed 1744 // attribute is the entry name 1745 PRINT(("notification: old: removed\n")); 1746 notify_query_entry_removed(fPort, fToken, fVolume->GetID(), 1747 entry->GetParent()->GetID(), (const char *)oldKey, 1748 entry->GetNode()->GetID()); 1749 } 1750 created = true; 1751 } else if (oldStatus != MATCH_OK && newStatus != MATCH_OK) { 1752 // nothing has changed 1753 return; 1754 } else if (oldStatus == MATCH_OK && newStatus != MATCH_OK) 1755 created = false; 1756 else 1757 created = true; 1758 1759 // We send a notification for the given entry, if any, or otherwise for 1760 // all entries referring to the node; 1761 if (entry) { 1762 PRINT(("notification: new: %s\n", (created ? "created" : "removed"))); 1763 send_entry_notification(fPort, fToken, fVolume, entry, created); 1764 } else { 1765 entry = node->GetFirstReferrer(); 1766 while (entry) { 1767 send_entry_notification(fPort, fToken, fVolume, entry, created); 1768 entry = node->GetNextReferrer(entry); 1769 } 1770 } 1771 } 1772 1773