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