Tetsuo Handa
from-****@I-lov*****
2009年 9月 14日 (月) 11:26:40 JST
TOMOYO
Fork 熊猫です。
Hiroshi Shinji さんは書きました：
> パス名を再帰的に指定出きるのは、便利でよいと思うのですが、
> パフォーマンス的に、どの程度影響しそうですか？
> （そんなに影響しない？）
パターンを含まない文字列同士の比較にはハッシュ値の比較および strcmp() を
使うのでまったく影響しません。
今まではパス名の深さ（文字列中の / の数）による比較を行っていましたが、
/\{dir\}/ を導入したことでパス名の深さによる比較が不可能になりました。
そのため、今まではパス名の深さ比較だけで一致する可能性が無い場合には
一致しないと判断していた処理が削られ、実際に比較を行うようになります。
これは、パフォーマンスに影響するかもしれません。
文字列の先頭から最初のパターンが出現するまでは strncmp() を使うので
まったく影響しません。また、文字列の先頭からパターンが使われること
（ /\*/\*/\*/\*/\*.html のような指定）は稀なので
/bin/true と /var/www/html/\{\*\}/\*.html のような比較は strncmp() により
この時点で一致しないと判断できるため、パス名の深さによる比較が不可能に
なったことによるパフォーマンスへの影響を減らすことができます。
最初のパターンから文字列の末尾までは /\{dir\}/ に一致しない限り
従来とほぼ同様ですので、パフォーマンスへの影響はほとんどありません。
/\{dir\}/ に一致した場合は文字列の末尾までの / の数に応じてパフォーマンスに
影響します。
実際にどの程度の影響があるかは測定プログラムを使わないと判りません。
@@ -820,6 +815,68 @@
}
/**
+ * ccs_path_matches_pattern2 - Do pathname pattern matching.
+ *
+ * @f: The start of string to check.
+ * @p: The start of pattern to compare.
+ *
+ * Returns true if @f matches @p, false otherwise.
+ */
+static bool ccs_path_matches_pattern2(const char *f, const char *p)
+{
+ const char *f_delimiter;
+ const char *p_delimiter;
+ while (*f && *p) {
+ f_delimiter = strchr(f, '/');
+ if (!f_delimiter)
+ f_delimiter = strchr(f, '\0');
+ p_delimiter = strchr(p, '/');
+ if (!p_delimiter)
+ p_delimiter = strchr(p, '\0');
+ if (*p == '\\' && *(p + 1) == '{')
+ goto recursive;
+ if (!ccs_file_matches_pattern(f, f_delimiter, p, p_delimiter))
+ return false;
+ f = f_delimiter;
+ if (*f)
+ f++;
+ p = p_delimiter;
+ if (*p)
+ p++;
+ }
+ /* Ignore trailing "\*" and "\@" in @pattern. */
+ while (*p == '\\' &&
+ (*(p + 1) == '*' || *(p + 1) == '@'))
+ p += 2;
+ return !*f && !*p;
+ recursive:
+ /*
+ * The "\{" pattern is permitted only after '/' character.
+ * This guarantees that below "*(p - 1)" is safe.
+ * Also, the "\}" pattern is permitted only before '/' character
+ * so that "\{" + "\}" pair will not break the "\-" operator.
+ */
+ if (*(p - 1) != '/' || p_delimiter <= p + 3 || *p_delimiter != '/' ||
+ *(p_delimiter - 1) != '}' || *(p_delimiter - 2) != '\\')
+ return false; /* Bad pattern. */
+ do {
+ /* Compare current component with pattern. */
+ if (!ccs_file_matches_pattern(f, f_delimiter, p + 2,
+ p_delimiter - 2))
+ break;
+ /* Proceed to next component. */
+ f = f_delimiter;
+ if (*f)
+ f++;
+ /* Continue comparison. */
+ if (ccs_path_matches_pattern2(f, p_delimiter + 1))
+ return true;
+ f_delimiter = strchr(f, '/');
+ } while (f_delimiter);
+ return false; /* Not matched. */
+}
+
+/**
* ccs_path_matches_pattern - Check whether the given filename matches the given pattern.
* @filename: The filename to check.
* @pattern: The pattern to compare.
@@ -829,16 +886,20 @@
* The following patterns are available.
* \\ \ itself.
* \ooo Octal representation of a byte.
- * \* More than or equals to 0 character other than '/'.
- * \@ More than or equals to 0 character other than '/' or '.'.
+ * \* Zero or more repetitions of characters other than '/'.
+ * \@ Zero or more repetitions of characters other than '/' or '.'.
* \? 1 byte character other than '/'.
- * \$ More than or equals to 1 decimal digit.
+ * \$ One or more repetitions of decimal digits.
* \+ 1 decimal digit.
- * \X More than or equals to 1 hexadecimal digit.
+ * \X One or more repetitions of hexadecimal digits.
* \x 1 hexadecimal digit.
- * \A More than or equals to 1 alphabet character.
+ * \A One or more repetitions of alphabet characters.
* \a 1 alphabet character.
+ *
* \- Subtraction operator.
+ *
+ * /\{dir\}/ One or more repetitions of dir (e.g. /dir/ /dir/dir/
+ * /dir/dir/dir/ ).
*/
bool ccs_path_matches_pattern(const struct ccs_path_info *filename,
const struct ccs_path_info *pattern)
@@ -853,36 +914,15 @@
/* If @pattern doesn't contain pattern, I can use strcmp(). */
if (!pattern->is_patterned)
return !ccs_pathcmp(filename, pattern);
- /* Don't compare if the number of '/' differs. */
- if (filename->depth != pattern->depth)
+ /* Don't compare directory and non-directory. */
+ if (filename->is_dir != pattern->is_dir)
return false;
/* Compare the initial length without patterns. */
if (strncmp(f, p, len))
return false;
f += len;
p += len;
- /* Main loop. Compare each directory component. */
- while (*f && *p) {
- const char *f_delimiter = strchr(f, '/');
- const char *p_delimiter = strchr(p, '/');
- if (!f_delimiter)
- f_delimiter = f + strlen(f);
- if (!p_delimiter)
- p_delimiter = p + strlen(p);
- if (!ccs_file_matches_pattern(f, f_delimiter, p, p_delimiter))
- return false;
- f = f_delimiter;
- if (*f)
- f++;
- p = p_delimiter;
- if (*p)
- p++;
- }
- /* Ignore trailing "\*" and "\@" in @pattern. */
- while (*p == '\\' &&
- (*(p + 1) == '*' || *(p + 1) == '@'))
- p += 2;
- return !*f && !*p;
+ return ccs_path_matches_pattern2(f, p);
}
/**