文件名与通配符匹配

Question

我需要实现像我自己的文件系统.一个操作是FindFirstFile.我需要检查,如果调用者传递了类似的东西.,样本*.cpp左右.我的"文件系统"实现提供了"文件名"列表作为char*的数组.

是否有任何Windows功能或任何实现此文件名匹配的源代码？

Answer 1

对于使用'*'和'？'的通配符名称匹配 试试这个(如果你想避免提升,请使用std :: tr1 :: regex):

#include <boost/regex.hpp>
#include <boost/algorithm/string/replace.hpp>

using std::string;

bool MatchTextWithWildcards(const string &text, string wildcardPattern, bool caseSensitive /*= true*/)
{
    // Escape all regex special chars
    EscapeRegex(wildcardPattern);

    // Convert chars '*?' back to their regex equivalents
    boost::replace_all(wildcardPattern, "\\?", ".");
    boost::replace_all(wildcardPattern, "\\*", ".*");

    boost::regex pattern(wildcardPattern, caseSensitive ? Regex::normal : regex::icase);

    return regex_match(text, pattern);
}

void EscapeRegex(string &regex)
{
    boost::replace_all(regex, "\\", "\\\\");
    boost::replace_all(regex, "^", "\\^");
    boost::replace_all(regex, ".", "\\.");
    boost::replace_all(regex, "$", "\\$");
    boost::replace_all(regex, "|", "\\|");
    boost::replace_all(regex, "(", "\\(");
    boost::replace_all(regex, ")", "\\)");
    boost::replace_all(regex, "{", "\\{");
    boost::replace_all(regex, "{", "\\}");
    boost::replace_all(regex, "[", "\\[");
    boost::replace_all(regex, "]", "\\]");
    boost::replace_all(regex, "*", "\\*");
    boost::replace_all(regex, "+", "\\+");
    boost::replace_all(regex, "?", "\\?");
    boost::replace_all(regex, "/", "\\/");
}

Answer 2

周围有很多这样的功能.这是一个各种实现的目录,分为递归和非递归等.

如果您不喜欢那里的许可(或链接有问题等),这里有一个匹配算法的可能实现,至少非常接近Windows使用的:

#include <string.h>
#include <iostream>

bool match(char const *needle, char const *haystack) {
    for (; *needle != '\0'; ++needle) {
        switch (*needle) {
        case '?': 
            if (*haystack == '\0')
                return false;
            ++haystack;
            break;
        case '*': {
            if (needle[1] == '\0')
                return true;
            size_t max = strlen(haystack);
            for (size_t i = 0; i < max; i++)
                if (match(needle + 1, haystack + i))
                    return true;
            return false;
        }
        default:
            if (*haystack != *needle)
                return false;
            ++haystack;
        }
    }
    return *haystack == '\0';
}

#ifdef TEST
#define CATCH_CONFIG_MAIN

#include "catch.hpp"

TEST_CASE("Matching", "[match]") {
    REQUIRE(match("a", "a") == true);
    REQUIRE(match("a", "b") == false);
    REQUIRE(match("a*", "a") == true);
    REQUIRE(match("a?", "a") == false);
    REQUIRE(match("a?", "ab") == true);
    REQUIRE(match("a*b", "ab") == true);
    REQUIRE(match("a*b", "acb") == true);
    REQUIRE(match("a*b", "abc") == false);
    REQUIRE(match("*a*??????a?????????a???????????????", 
        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa") == true);
}

#endif

由于讨论了其他一些答案的复杂性,我会注意到我认为这有O(NM)复杂性和O(M)存储使用(其中N是目标字符串的大小,M是图案的大小).

使用@masterxilo的测试对:

"*a*??????*a*?????????a???????????????", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

...这会在我的机器上找到大约3微秒的匹配.这是不是一个典型的模式慢了许多-我的大部分其他测试运行在约300纳秒左右这个特定的机器上.

与此同时,@ masterxilo的代码在同一台机器上运行大约需要11微秒,所以这仍然快3到4倍(更不用说更小更简单了).

Answer 3

看一看的POSIX的功能fnmatch,glob以及wordexp.

Answer 4

这是我对此的尝试.

它是"C++",但我故意保持它几乎完全C兼容.
所有你需要的,以将其转换为C++做的是去除template部分,变化Pattern和Text喜欢的东西char const *.

// TEST THIS before use! I've only done limited testing.

#include <stddef.h>
#include <stdlib.h>
#include <string.h>

template<class Pattern, class Text>
bool wildcard(
    Pattern const pat_begin, Pattern const pat_end,
    Text text_begin, Text const text_end)
{
    ptrdiff_t const pat_size = pat_end - pat_begin;
    ptrdiff_t stackbuf[64];
    size_t c = sizeof(stackbuf) / sizeof(*stackbuf);
    ptrdiff_t *p = stackbuf;
    size_t n = 0;
    p[n++] = 0;
    while (n > 0 && text_begin != text_end)
    {
        for (size_t i = 0; i < n; i++)
        {
            if (p[i] == pat_size)
            {
                p[i--] = p[--n];
                continue;
            }
            switch (*(pat_begin + p[i]))
            {
            case '?': ++p[i]; break;
            case '*':
                ptrdiff_t off;
                off = p[i];
                while (off < pat_size &&
                    *(pat_begin + off) == '*')
                { ++off; }
                if (n == c)
                {
                    ptrdiff_t const *const old = p;
                    c *= 2;
                    if (c == 0) { ++c; }
                    size_t const size = c * sizeof(*p);
                    p = (ptrdiff_t *)realloc(
                        old == stackbuf ? NULL : p,
                        size);
                    if (old == stackbuf)
                    { memcpy(p, old, n * sizeof(*old)); }
                }
                p[n++] = off;
                break;
            default:
                if (*(pat_begin + p[i]) == *text_begin)
                { ++p[i]; }
                else { p[i--] = p[--n]; }
                break;
            }
        }
        ++text_begin;
    }
    bool success = false;
    if (text_begin == text_end)
    {
        while (!success && n > 0)
        {
            --n;
            while (p[n] != pat_size &&
                *(pat_begin + p[n]) == '*')
            { ++p[n]; }
            if (p[n] == pat_size)
            { success = true; }
        }
    }
    if (p != stackbuf) { free(p); }
    return success;
}

bool wildcard(char const *const pattern, char const *const text)
{
    return wildcard(
        pattern,
        pattern + (pattern ? strlen(pattern) : 0),
        text,
        text + (text ? strlen(text) : 0));
}

bool wildcard(wchar_t const *const pattern, wchar_t const *const text)
{
    return wildcard(
        pattern,
        pattern + (pattern ? wcslen(pattern) : 0),
        text,
        text + (text ? wcslen(text) : 0));
}

当然,您可以随心所欲地使用代码.:)