2005年11月24日

Boostの正規表現クラスを使う

Boost の正規表現クラスを使ってみよう思い、ディレクトリ以下のファイルに対して再帰的に grep を行うコードを書いてみました。

 

以下がそのコードです。再帰的な grep はGNU grep の --recursive オプションでできるので実用的な意味はありません。

#include <assert.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <boost/bind.hpp>
#include <boost/filesystem/operations.hpp>
#include <boost/filesystem/path.hpp>
#include <boost/regex.hpp>

using namespace std;
namespace fs = boost::filesystem;

class grep {
public:
    grep(const fs::path& directory, const string& pattern) :
        directory_(directory), regex_(pattern) {}

    void perform() const {
        traverse(directory_, boost::bind(&grep::grep_file, this, _1));
    }

private:
    const fs::path directory_;
    const boost::regex regex_;

    template <typename visitor>
    void traverse(const fs::path& directory, const visitor& func) const {
        fs::directory_iterator end;
        for (fs::directory_iterator it(directory); it != end; ++it) {
            if (fs::is_directory(*it)) {
                traverse(*it, func);
            } else {
                func(*it);
            }
        }
    }

    void grep_file(const fs::path& path) const {
        const int fd = open(path.string().c_str(), O_RDONLY);
        assert(fd != -1);
        struct stat stat;
        assert(fstat(fd, &stat) != -1);
        if (stat.st_size > 0) {
            char* const map =
                static_cast<char*>(mmap(0, stat.st_size,
                                        PROT_READ, MAP_SHARED, fd, 0));
            assert(map != MAP_FAILED);
            assert(madvise(map, stat.st_size, MADV_SEQUENTIAL) != -1);
            grep_core(map, stat.st_size);
            assert(munmap(map, stat.st_size) != -1);
        }
        assert(close(fd) != -1);
    }

    void grep_core(const char* const map, size_t size) const {
        const char* const bof = map;
        const char* const eof = map + size;
        const char* bol = bof;
        while (bol < eof) {
            const char* eol = strchr(bol, '\n');
            if (eol == 0) {
                eol = eof;
            }

            if (boost::regex_search(bol, eol, regex_)) {
                fwrite(bol, 1, eol - bol, stdout);
                fputc('\n', stdout);
            }
            bol = eol + 1;
        }
    }
};

int main(int argc, char **argv) {
    assert(argc == 3);
    const string pattern(argv[1]);
    const fs::path directory(argv[2]);
    const grep grep(directory, pattern);
    grep.perform();
    return 0;
}

Debian GNU/Linux sarge では以下のように実行してコンパイルしました。

% sudo apt-get install libboost-filesystem-dev
% sudo apt-get install libboost-regex-dev
% g++ -o recgrep -Wall recgrep.cpp -pthread -lboost_filesystem -lboost_regex

実行速度は LANG=C で実行したときの GNU grep 2.5.1 の方が断然高速でした。最近の GNU grep は環境変数 LANG を ja_JP.utf8 などに設定すると何十倍も遅くなるようです。

% repeat 3 time LANG=C egrep -R foo /usr/share/emacs >/dev/null
0.15s total : 0.10s user 0.06s system 104% cpu
0.15s total : 0.06s user 0.09s system 100% cpu
0.14s total : 0.09s user 0.05s system 97% cpu

% repeat 3 time ./recgrep foo /usr/share/emacs > /dev/null
2.44s total : 2.39s user 0.05s system 99% cpu
2.44s total : 2.35s user 0.09s system 99% cpu
2.46s total : 2.39s user 0.06s system 99% cpu

% repeat 3 time LANG=ja_JP.utf8 egrep -R foo /usr/share/emacs >/dev/null
9.46s total : 9.34s user 0.11s system 99% cpu
9.60s total : 9.42s user 0.12s system 99% cpu
9.37s total : 9.23s user 0.14s system 100% cpu

ところで、上のコードの traverse の第2引数に対して boost::bind() を使ってメンバ関数 grep::grep_file をファンクタ化して渡しています。メンバ関数のポインタで渡す場合は以下のようになります。そもそも traverse は第2引数を取る必要はないのですが (直接 grep_file() を呼べばいい)、遊びでやっています。

        traverse(directory_, &grep::grep_file);
        ...
    void traverse(const fs::path& directory, 
                  void (grep::*func)(const fs::path&)) const {
        ...
                (this->*func)(*it);

まとめ

今回は Boost の正規表現のクラスを使いました。Boost には他にも便利なものがたくさん入っていて C++ でプログラムを書くのに大変便利です。Boost を使うにあたっては Let's Boostが参考になります。