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 if (expr == NULL) 1163 return; 1164 1165 fTerm = ParseOr(&expr); 1166 if (fTerm != NULL && fTerm->InitCheck() < B_OK) { 1167 QUERY_FATAL("Corrupt tree in expression!\n"); 1168 delete fTerm; 1169 fTerm = NULL; 1170 } 1171 QUERY_D(if (fTerm != NULL) { 1172 fTerm->PrintToStream(); 1173 QUERY_D(__out("\n")); 1174 if (*expr != '\0') 1175 PRINT(("Unexpected end of string: \"%s\"!\n", expr)); 1176 }); 1177 fPosition = expr; 1178} 1179 1180 1181template<typename QueryPolicy> 1182Expression<QueryPolicy>::~Expression() 1183{ 1184 delete fTerm; 1185} 1186 1187 1188template<typename QueryPolicy> 1189Term<QueryPolicy>* 1190Expression<QueryPolicy>::ParseEquation(char** expr) 1191{ 1192 skipWhitespace(expr); 1193 1194 bool _not = false; 1195 if (**expr == '!') { 1196 skipWhitespace(expr, 1); 1197 if (**expr != '(') 1198 return NULL; 1199 1200 _not = true; 1201 } 1202 1203 if (**expr == ')') { 1204 // shouldn't be handled here 1205 return NULL; 1206 } else if (**expr == '(') { 1207 skipWhitespace(expr, 1); 1208 1209 Term<QueryPolicy>* term = ParseOr(expr); 1210 1211 skipWhitespace(expr); 1212 1213 if (**expr != ')') { 1214 delete term; 1215 return NULL; 1216 } 1217 1218 // If the term is negated, we just complement the tree, to get 1219 // rid of the not, a.k.a. DeMorgan's Law. 1220 if (_not) 1221 term->Complement(); 1222 1223 skipWhitespace(expr, 1); 1224 1225 return term; 1226 } 1227 1228 Equation<QueryPolicy>* equation 1229 = new(std::nothrow) Equation<QueryPolicy>(expr); 1230 if (equation == NULL || equation->InitCheck() < B_OK) { 1231 delete equation; 1232 return NULL; 1233 } 1234 return equation; 1235} 1236 1237 1238template<typename QueryPolicy> 1239Term<QueryPolicy>* 1240Expression<QueryPolicy>::ParseAnd(char** expr) 1241{ 1242 Term<QueryPolicy>* left = ParseEquation(expr); 1243 if (left == NULL) 1244 return NULL; 1245 1246 while (IsOperator(expr, '&')) { 1247 Term<QueryPolicy>* right = ParseAnd(expr); 1248 Term<QueryPolicy>* newParent = NULL; 1249 1250 if (right == NULL 1251 || (newParent = new(std::nothrow) Operator<QueryPolicy>(left, 1252 OP_AND, right)) == NULL) { 1253 delete left; 1254 delete right; 1255 1256 return NULL; 1257 } 1258 left = newParent; 1259 } 1260 1261 return left; 1262} 1263 1264 1265template<typename QueryPolicy> 1266Term<QueryPolicy>* 1267Expression<QueryPolicy>::ParseOr(char** expr) 1268{ 1269 Term<QueryPolicy>* left = ParseAnd(expr); 1270 if (left == NULL) 1271 return NULL; 1272 1273 while (IsOperator(expr, '|')) { 1274 Term<QueryPolicy>* right = ParseAnd(expr); 1275 Term<QueryPolicy>* newParent = NULL; 1276 1277 if (right == NULL 1278 || (newParent = new(std::nothrow) Operator<QueryPolicy>(left, OP_OR, 1279 right)) == NULL) { 1280 delete left; 1281 delete right; 1282 1283 return NULL; 1284 } 1285 left = newParent; 1286 } 1287 1288 return left; 1289} 1290 1291 1292template<typename QueryPolicy> 1293bool 1294Expression<QueryPolicy>::IsOperator(char** expr, char op) 1295{ 1296 char* string = *expr; 1297 1298 if (*string == op && *(string + 1) == op) { 1299 *expr += 2; 1300 return true; 1301 } 1302 return false; 1303} 1304 1305 1306template<typename QueryPolicy> 1307status_t 1308Expression<QueryPolicy>::InitCheck() 1309{ 1310 if (fTerm == NULL) 1311 return B_BAD_VALUE; 1312 1313 return B_OK; 1314} 1315 1316 1317// #pragma mark - 1318 1319 1320template<typename QueryPolicy> 1321Query<QueryPolicy>::Query(Context* context, Expression<QueryPolicy>* expression, 1322 uint32 flags, port_id port, uint32 token) 1323 : 1324 fContext(context), 1325 fExpression(expression), 1326 fCurrent(NULL), 1327 fIterator(NULL), 1328 fIndex(context), 1329 fFlags(flags), 1330 fPort(port), 1331 fToken(token), 1332 fNeedsEntry(false) 1333{ 1334 // If the expression has a valid root pointer, the whole tree has 1335 // already passed the sanity check, so that we don't have to check 1336 // every pointer 1337 if (context == NULL || expression == NULL || expression->Root() == NULL) 1338 return; 1339 1340 // create index on the stack and delete it afterwards 1341 fExpression->Root()->CalculateScore(fIndex); 1342 QueryPolicy::IndexUnset(fIndex); 1343 1344 fNeedsEntry = fExpression->Root()->NeedsEntry(); 1345 1346 Rewind(); 1347} 1348 1349 1350template<typename QueryPolicy> 1351Query<QueryPolicy>::~Query() 1352{ 1353 delete fExpression; 1354} 1355 1356 1357template<typename QueryPolicy> 1358/*static*/ status_t 1359Query<QueryPolicy>::Create(Context* context, const char* queryString, 1360 uint32 flags, port_id port, uint32 token, Query<QueryPolicy>*& _query) 1361{ 1362 Expression<QueryPolicy>* expression 1363 = new(std::nothrow) Expression<QueryPolicy>((char*)queryString); 1364 if (expression == NULL) 1365 QUERY_RETURN_ERROR(B_NO_MEMORY); 1366 1367 if (expression->InitCheck() != B_OK) { 1368 QUERY_INFORM("Could not parse query \"%s\", stopped at: \"%s\"\n", 1369 queryString, expression->Position()); 1370 1371 delete expression; 1372 QUERY_RETURN_ERROR(B_BAD_VALUE); 1373 } 1374 1375 Query<QueryPolicy>* query = new(std::nothrow) Query<QueryPolicy>(context, 1376 expression, flags, port, token); 1377 if (query == NULL) { 1378 delete expression; 1379 QUERY_RETURN_ERROR(B_NO_MEMORY); 1380 } 1381 1382 _query = query; 1383 return B_OK; 1384} 1385 1386 1387template<typename QueryPolicy> 1388status_t 1389Query<QueryPolicy>::Rewind() 1390{ 1391 // free previous stuff 1392 1393 fStack.MakeEmpty(); 1394 1395 QueryPolicy::IndexIteratorDelete(fIterator); 1396 fIterator = NULL; 1397 fCurrent = NULL; 1398 1399 // put the whole expression on the stack 1400 1401 Stack<Term<QueryPolicy>*> stack; 1402 stack.Push(fExpression->Root()); 1403 1404 Term<QueryPolicy>* term; 1405 while (stack.Pop(&term)) { 1406 if (term->Op() < OP_EQUATION) { 1407 Operator<QueryPolicy>* op = (Operator<QueryPolicy>*)term; 1408 1409 if (op->Op() == OP_OR) { 1410 stack.Push(op->Left()); 1411 stack.Push(op->Right()); 1412 } else { 1413 // For OP_AND, we can use the scoring system to decide which 1414 // path to add 1415 if (op->Right()->Score() > op->Left()->Score()) 1416 stack.Push(op->Right()); 1417 else 1418 stack.Push(op->Left()); 1419 } 1420 } else if (term->Op() == OP_EQUATION 1421 || fStack.Push((Equation<QueryPolicy>*)term) != B_OK) 1422 QUERY_FATAL("Unknown term on stack or stack error\n"); 1423 } 1424 1425 return B_OK; 1426} 1427 1428 1429template<typename QueryPolicy> 1430status_t 1431Query<QueryPolicy>::GetNextEntry(struct dirent* dirent, size_t size) 1432{ 1433 if (fIterator != NULL) 1434 QueryPolicy::IndexIteratorResume(fIterator); 1435 1436 status_t error = _GetNextEntry(dirent, size); 1437 1438 if (fIterator != NULL) 1439 QueryPolicy::IndexIteratorSuspend(fIterator); 1440 1441 return error; 1442} 1443 1444 1445template<typename QueryPolicy> 1446void 1447Query<QueryPolicy>::LiveUpdate(Entry* entry, Node* node, const char* attribute, 1448 int32 type, const uint8* oldKey, size_t oldLength, const uint8* newKey, 1449 size_t newLength) 1450{ 1451 if (fPort < 0 || fExpression == NULL || attribute == NULL) 1452 return; 1453 1454 // TODO: check if the attribute is part of the query at all... 1455 1456 // If no entry has been supplied, but the we need one for the evaluation 1457 // (i.e. the "name" attribute is used), we invoke ourselves for all entries 1458 // referring to the given node. 1459 if (entry == NULL && fNeedsEntry) { 1460 entry = QueryPolicy::NodeGetFirstReferrer(node); 1461 while (entry) { 1462 LiveUpdate(entry, node, attribute, type, oldKey, oldLength, newKey, 1463 newLength); 1464 entry = QueryPolicy::NodeGetNextReferrer(node, entry); 1465 } 1466 return; 1467 } 1468 1469 status_t oldStatus = fExpression->Root()->Match(entry, node, attribute, 1470 type, oldKey, oldLength); 1471 status_t newStatus = fExpression->Root()->Match(entry, node, attribute, 1472 type, newKey, newLength); 1473 1474 bool entryCreated = false; 1475 bool stillInQuery = false; 1476 1477 if (oldStatus != MATCH_OK) { 1478 if (newStatus != MATCH_OK) { 1479 // nothing has changed 1480 return; 1481 } 1482 entryCreated = true; 1483 } else if (newStatus != MATCH_OK) { 1484 // entry got removed 1485 entryCreated = false; 1486 } else if ((fFlags & B_ATTR_CHANGE_NOTIFICATION) != 0) { 1487 // The entry stays in the query 1488 stillInQuery = true; 1489 } else 1490 return; 1491 1492 // notify query listeners 1493 status_t (*notify)(port_id, int32, dev_t, ino_t, const char*, ino_t); 1494 1495 if (stillInQuery) 1496 notify = notify_query_attr_changed; 1497 else if (entryCreated) 1498 notify = notify_query_entry_created; 1499 else 1500 notify = notify_query_entry_removed; 1501 1502 if (entry != NULL) { 1503 _SendEntryNotification(entry, notify); 1504 } else { 1505 entry = QueryPolicy::NodeGetFirstReferrer(node); 1506 while (entry) { 1507 _SendEntryNotification(entry, notify); 1508 entry = QueryPolicy::NodeGetNextReferrer(node, entry); 1509 } 1510 } 1511} 1512 1513 1514template<typename QueryPolicy> 1515void 1516Query<QueryPolicy>::LiveUpdateRenameMove(Entry* entry, Node* node, 1517 ino_t oldDirectoryID, const char* oldName, size_t oldLength, 1518 ino_t newDirectoryID, const char* newName, size_t newLength) 1519{ 1520 if (fPort < 0 || fExpression == NULL) 1521 return; 1522 1523 // TODO: check if the attribute is part of the query at all... 1524 1525 status_t oldStatus = fExpression->Root()->Match(entry, node, "name", 1526 B_STRING_TYPE, (const uint8*)oldName, oldLength); 1527 status_t newStatus = fExpression->Root()->Match(entry, node, "name", 1528 B_STRING_TYPE, (const uint8*)newName, newLength); 1529 1530 if (oldStatus != MATCH_OK || oldStatus != newStatus) 1531 return; 1532 1533 // The entry stays in the query, notify query listeners about the rename 1534 // or move 1535 1536 // We send a notification for the given entry, if any, or otherwise for 1537 // all entries referring to the node; 1538 if (entry != NULL) { 1539 _SendEntryNotification(entry, notify_query_entry_removed); 1540 _SendEntryNotification(entry, notify_query_entry_created); 1541 } else { 1542 entry = QueryPolicy::NodeGetFirstReferrer(node); 1543 while (entry) { 1544 _SendEntryNotification(entry, notify_query_entry_removed); 1545 _SendEntryNotification(entry, notify_query_entry_created); 1546 entry = QueryPolicy::NodeGetNextReferrer(node, entry); 1547 } 1548 } 1549} 1550 1551 1552template<typename QueryPolicy> 1553status_t 1554Query<QueryPolicy>::_GetNextEntry(struct dirent* dirent, size_t size) 1555{ 1556 // If we don't have an equation to use yet/anymore, get a new one 1557 // from the stack 1558 while (true) { 1559 if (fIterator == NULL) { 1560 if (!fStack.Pop(&fCurrent) 1561 || fCurrent == NULL) 1562 return B_ENTRY_NOT_FOUND; 1563 1564 status_t status = fCurrent->PrepareQuery(fContext, fIndex, 1565 &fIterator, fFlags & B_QUERY_NON_INDEXED); 1566 if (status == B_ENTRY_NOT_FOUND) { 1567 // try next equation 1568 continue; 1569 } 1570 1571 if (status != B_OK) 1572 return status; 1573 } 1574 if (fCurrent == NULL) 1575 QUERY_RETURN_ERROR(B_ERROR); 1576 1577 status_t status = fCurrent->GetNextMatching(fContext, fIterator, dirent, 1578 size); 1579 if (status != B_OK) { 1580 QueryPolicy::IndexIteratorDelete(fIterator); 1581 fIterator = NULL; 1582 fCurrent = NULL; 1583 } else { 1584 // only return if we have another entry 1585 return B_OK; 1586 } 1587 } 1588} 1589 1590 1591template<typename QueryPolicy> 1592void 1593Query<QueryPolicy>::_SendEntryNotification(Entry* entry, 1594 status_t (*notify)(port_id, int32, dev_t, ino_t, const char*, ino_t)) 1595{ 1596 char nameBuffer[QueryPolicy::kMaxFileNameLength]; 1597 const char* name = QueryPolicy::EntryGetNameNoCopy(entry, nameBuffer, 1598 sizeof(nameBuffer)); 1599 if (name != NULL) { 1600 notify(fPort, fToken, QueryPolicy::ContextGetVolumeID(fContext), 1601 QueryPolicy::EntryGetParentID(entry), name, 1602 QueryPolicy::EntryGetNodeID(entry)); 1603 } 1604} 1605 1606 1607} // namespace QueryParser 1608 1609 1610#endif // _FILE_SYSTEMS_QUERY_PARSER_H 1611