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