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