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