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