サブフォルダ・再帰的検索

[Ma]

いつもおせわになってます。

今、あるフォルダ内のすべての音楽ファイル（特定の拡張子）を検索しリストを得ようとしています。
再帰的方法で、次々とサブフォルダから音楽ファイルを検索し、リストするプログラムを作ってみました。

しかし、　deque<string>　的なものを、再帰的にスタックしていく方法でやってみると、あっというまにオーバーフローしてしまいました。
（bad_alloc ??）
サイズがといよりも、deque<std::string>を作りすぎた・・・？

理想としては、ウィンドウズメディアプレイヤーのフォルダ登録的なものを想像しています。


失敗したやり方は単純で、再帰的検索の王道って感じです。
最初に、関数を作成。
その引数にフォルダパスを指定。戻り値はdeque<std::string>。
この関数の役目は、まず指定フォルダ中のすべてのwavファイルとサブフォルダをリスト化、そのサブフォルダパスを同じ関数に引数として渡す。戻ってきたdeque<std::string> と、wavファイルパスをリスト化したdeque<std::string>のふたつを融合、そしてreturn。
サブフォルダがない場合は、もっとも深いところとなり、wavファイルのリストのみがreturnする。

これで、フォルダ以下のすべてのwavファイルの検索ができる。（はずだと思ってた）


結果、上層を指定するとみごとにオーバーフローしました。
だいたい３階層ぐらいまではテストして成功したんですが、限度があるようで＾＾；

ユーザーが選んだフォルダ内の音声ファイル（特定の拡張子）を、すべてリスト化するのに、もう少し安全な方法はないでしょうか？

[たいちう]

> 失敗したやり方は単純で、再帰的検索の王道って感じです。

王道は失敗しません。王道から外れてしまったのでしょう。
どこで外れたかは、もっと詳しい説明を聞かないとわかりません。

[dic]

私も作って失敗した経験があります
階層が深くなると失敗するようで
string に格納する前のchar配列の大きさは大丈夫でしょうか？
フルパス入りますので、私の場合だと、このサイズが足りなくてて
エラーを起こしてました

[Ma]

再帰法を使っている部分のソースを記載します。
char 配列とか、一切使わずに作ってしまいました。。。

あと、適当に王道とかいってすいません。（汗

さきほどは、たとえとして
deque<std::string>
といいましたが、
実際は、
deque<musicFIle>

struct musicFile{
std::string filePath;
std::string title;
int soundHandle;
};
このようになってます。



deque<musicFile> searchFolder(string folderName,bool subFol){

deque<musicFile> tempReturnList;

//初期化
HANDLE hFind;
WIN32_FIND_DATA FileData;

//見つかったファイル名をいれる。
deque<string> foundThese;
deque<string> subFolders;


string folderFindPath = folderName;
folderFindPath += "/*";

hFind = FindFirstFile((LPCTSTR)folderFindPath.c_str(), &FileData);
if(hFind == INVALID_HANDLE_VALUE) {
FindClose(hFind);
MessageBeep(MB_ICONHAND);
printfDx("No file found");
}
do{
if(strcmp((const char *)FileData.cFileName,".") != 0 &&
strcmp((const char *)FileData.cFileName,"..") != 0 ){
string toAdd = (string)(const char *)FileData.cFileName;
if(toAdd.length() > 4 && toAdd.find(".wav") == toAdd.length() - 4)
foundThese.push_back(toAdd);
else if(subFol && toAdd.find(".") == string.npos)
subFolders.push_back(toAdd);
}
}while(FindNextFile(hFind, &FileData));

FindClose(hFind);

for each(string temp in foundThese){
musicFile tempSong;
tempSong.filePath = (folderName + "\\") + temp;
tempSong.soundHandle = 0;
tempSong.title = temp;
tempReturnList.push_back(tempSong);
}

if(subFol){
for each(string tempSubFolder in subFolders){
string subFolPath = (folderName + "\\") + tempSubFolder;
deque<musicFile> bigList = searchFolder(subFolPath,true);
for each(musicFile tempMusicFile in bigList){
tempReturnList.push_back(tempMusicFile);
}
}
}

return tempReturnList;
}


あと、エラーが発生する（アクセス違反が発生する）のは
xmemoryファイルの

_STD_BEGIN
// TEMPLATE FUNCTION _Allocate
template<class _Ty> inline
_Ty _FARQ *_Allocate(_SIZT _Count, _Ty _FARQ *)
{ // check for integer overflow
if (_Count <= 0)
_Count = 0;
else if (((_SIZT)(-1) / _Count) < sizeof (_Ty))
_THROW_NCEE(std::bad_alloc, NULL);

// allocate storage for _Count elements of type _Ty
return ((_Ty _FARQ *)::operator new(_Count * sizeof (_Ty)));
}


と記載されている部分の、return の部分で緑矢印が表示されて止まる感じです。
(_Count = 304　でした。)

自分で思うところといえば、欲張って構造体で再帰法しないほうがよかったかな。。。ってぐらいです。
具体的なエラー内容が正確に把握できていないので、そちらの把握も手伝っていただけると幸いです。

[Justy]

　おかしなところや無駄がいろいろありますね。
　とりあえずおかしなところは直して、スタックの消費量を抑えるように直していきましょう。

　エラーになる可能性としては今のところ二種類考えられます。
・　文字セットが Unicode環境な為、char型で扱おうとして失敗している
・　FindFirstFileに失敗した場合でも処理を続行しようとしている為、
cFileNameなどの文字列の処理に失敗する

あたりではないかと。


　あとフォルダかどうかの判定がおかしいです。

[Ma]

おぉー、Justy さんの指示にしたがったら、エラーがなくなりました。
ありがとうございまいた。

あとは、スタックの消費量減らしていって改良していきますね。
完成次第、確認のためポストさせていただきます。

[Ma]

できましたー。


//指定ディレクトリから、拡張子 wav のファイルをリスト化
deque<string> searchFolder(string folderName,bool subFol){
deque<string> tempReturnList;

//見つかったファイル名をいれる。
deque<string> subFolders;

//フォルダ名から、検索フォルダ名を作成
string folderFindPath = folderName;
folderFindPath += "/*";

//検索の前準備。
HANDLE hFind;
WIN32_FIND_DATA FileData;

//検索開始
hFind = FindFirstFile((LPCTSTR)folderFindPath.c_str(), &FileData);
//エラーなら
if(hFind == INVALID_HANDLE_VALUE) {
//エラー報告
MessageBeep(MB_ICONHAND);
printfDx("No file found");
//ハンドル閉じる
FindClose(hFind);
//エラーなので、空で戻す。
return tempReturnList;
}

do{
//ディレクトリエントリの場合は、無視。
if ( FileData.cFileName[0] != '.' ){
size_t length = strlen(FileData.cFileName);

//拡張子が、.wavの場合。(ファイル名から、.wav が探知され、かつその拡張子がファイル終端にあるならば)
if(FileData.cFileName+(length-4) == strstr(FileData.cFileName,".wav")){
string filePath = folderName + '\\' + FileData.cFileName;
tempReturnList.push_back(filePath);

}

//サブフォルダー検索フラグON　かつ、発見したファイルがディレクトリだったならば、サブフォルダとしてdequeへ登録。
else if(subFol && FileData.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY)
subFolders.push_back(FileData.cFileName);
}
//次のファイル
}while(FindNextFile(hFind, &FileData));

//ハンドルを閉じる。
FindClose(hFind);

//サブフォルダ検索フラグがONなら
if(subFol){
for each(string tempSubFolder in subFolders){
string subFolPath = (folderName + "\\") + tempSubFolder;
deque<string> bigList = searchFolder(subFolPath,true);
for each(string tempMusicFile in bigList){
tempReturnList.push_back(tempMusicFile);
}
}
}
//完成したリストを戻す。
return tempReturnList;
}



マイドキュメントのフォルダでテストしてみたところ、数秒で1000曲ヒットしました。
は、はやいｗ


ソースコードに、まだ問題がありそうならご指摘お願いします。

[Justy]

　んーと、問題と改善項目をざくっと洗い出してみました。
　好みな部分もあるので、気にならなければ無視してしまっても構いません。

・　戻り値で deque<string>を返すのは著しい無駄（大量のオブジェクトコピー）が発生する可能性が高いので、
　大元の呼び出し元から引数に参照として渡して、その参照に対してフォルダの探索をすると同時に
　どんどん追加していきましょう（戻り先で追加しなくて済みます）。
・　引数の folderName / tempSubFolderなど可能な限り const参照にして無駄なコンストラクタや
　デストラクタの呼び出しを抑制した方がいいでしょう。
・　folderFindPath変数は FindFirstFileAに渡すとき (folderName + "/*").c_str()とすれば要らなくなりますし
　生存期間も短くなります。
・　FindFirstFileに失敗したハンドルはクローズする必要はありません。
・　WIN32_FIND_DATAは環境によって変わるので、std::stringに渡すなら、WIN32_FIND_DATAAを使いましょう。
・　WIN32_FIND_DATAAを使うなら FindFirstFileA/FindNextFileAを使いましょう。
・　ディレクトリエントリの場合は無視の処理が普通のファイル・フォルダを弾く可能性があります。ex) .a.wav
・　拡張子が wavかどうかの判定で頭から検索して調べのはちょっと効率が悪いです。
　std::strncmpで最後の４文字文だけをピンポイントで比較するといいかと。

[Ma]

なるほど、勉強になります。
改良させていただきました。


//指定ディレクトリから、拡張子 wav のファイルを検索し、foundListに追加する。
void searchFolder(deque<string>& foundList,const string folderName,const bool subFol){

//見つかったサブディレクトリ名をいれる。
deque<string> subFolders;

//検索の前準備。
HANDLE hFind;
WIN32_FIND_DATAA FileData;

//検索開始
hFind = FindFirstFileA((LPCTSTR)(folderName+"/*").c_str(), &FileData);
//エラーなら
if(hFind == INVALID_HANDLE_VALUE) {
//エラーなので、空で戻す。
return;
}

do{
//ディレクトリエントリの場合は、無視。
if ( FileData.cFileName[0] != '.' || 2 < strlen(FileData.cFileName)){
size_t length = strlen(FileData.cFileName);

//拡張子が、.wavの場合。(ファイル名から、.wav が探知され、かつその拡張子がファイル終端にあるならば)
if(0 == strncmp(FileData.cFileName+length-4,".wav",4)){
string filePath = folderName + '\\' + FileData.cFileName;
foundList.push_back(filePath);

}

//サブフォルダー検索フラグON　かつ、発見したファイルがディレクトリだったならば、サブフォルダとしてdequeへ登録。
else if(subFol && FileData.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY)
subFolders.push_back(FileData.cFileName);
}
//次のファイル
}while(FindNextFileA(hFind, &FileData));

//ハンドルを閉じる。
FindClose(hFind);

//サブフォルダ検索フラグがONなら
if(subFol){
for each(const string tempSubFolder in subFolders){
searchFolder(foundList,(folderName + "\\") + tempSubFolder,true);
}
}
//完了。
return;
}

[たいちう]

"TEST.WAV"が対象外なのは仕様ですか？
そうでない場合、私ならこのように書くかな。

#include <string> // string
#include <algorithm> // transform
#include <cctype> // toupper

bool check(const string &fileName) {
size_t len = fileName.length();
if (len <= 4) return false;
string buf = fileName.substr(len - 4);
transform(buf.begin(), buf.end(), buf.begin(), toupper);
return buf == ".WAV";
}

[Justy]

　かなりよくなったと思います。
　あと少しです。

　以下の点は修正が必要だと思います。
　
・　FindFirstFileAの第一引数はLPCSTR(const char *)なので、LPCTSTR(const TCHAR*)でキャストすると
　環境によってエラーになります。std::stringから渡していますので、キャストそのものが不要です。
・　cFileNameが４文字未満だった場合不正なメモリにアクセスすることになります。


　以下の点は仕様によっては修正が必要だと思います。
・　「ディレクトリエントリの場合は、無視」が ".a"というフォルダを無視してしまいます。
・　拡張子が .WAVなど大文字が混ざる場合ヒットしない。


　以下は推奨です。

・　内容が変化しない文字列に対して２回 strlenを呼び出しています。
・　変数 filePath / tempSubFolderは const std::string&にしておくといいかと。
　今回のケースではあまり変わらないと思いますが、オブジェクトによっては余計な処理が発生しますので
　付けておいた方がいいですね。

[Ma]

思っていたよりもたくさんの指摘をいただけたのですこし驚いています。
このぐらいの長さのコードでも、正確さとスマートさを追求すれば改良の余地ってのは計り知れないなぁと、痛感です。

また、お二人の意見を取り入れて自分なりに改良してみました。どうでしょうか。


//指定ディレクトリから、拡張子 wav のファイルを検索し、foundListに追加する。
void searchFolder(deque<string>& foundList,const string folderName,const bool subFol){

//見つかったサブディレクトリ名をいれる。
deque<string> subFolders;

//検索の前準備。
HANDLE hFind;
WIN32_FIND_DATAA FileData;

//検索開始
hFind = FindFirstFileA((folderName+"/*").c_str(), &FileData);
//エラーなら
if(hFind == INVALID_HANDLE_VALUE) {
//エラーなので、空で戻す。
return;
}

do{
//ディレクトリエントリの場合は、無視。
if ( strcmp(".",FileData.cFileName) != 0 && strcmp("..",FileData.cFileName) != 0){
//長さ
size_t length = strlen(FileData.cFileName);

//XXX.wav　なら、四文字より文字数は大きい。大文字、小文字の区別なしで、ファイル名終端に.wavがあるかどうか。
if(length > 4 && 0 == _strnicmp(FileData.cFileName+length-4,".wav",4)){
foundList.push_back(folderName + '\\' + FileData.cFileName);
}

//サブフォルダー検索フラグON　かつ、発見したファイルがディレクトリだったならば、サブフォルダとしてdequeへ登録。
else if(subFol && (FileData.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY))
subFolders.push_back(FileData.cFileName);
}
//次のファイル
}while(FindNextFileA(hFind, &FileData));

//ハンドルを閉じる。
FindClose(hFind);

//サブフォルダ検索フラグがONなら
if(subFol){
for each(const string &tempSubFolder in subFolders){
searchFolder(foundList,(folderName + "\\") + tempSubFolder,true);
}
}
//完了。
return;
}

[Justy]

　おー、もう大きな問題はないですね。

　細かいところを言えば

・　No:49988でも触れましたが引数の folderNameを参照にすると無駄なコピーが無くなります。
・　？（そんなファイルがある方がおかしいといえばおかしいんですが）".wav"ファイルは
弾いてしまってもいいのでしょうか？
・　ファイル名の収拾順が少し変わるので仕様的にどうかは検討が必要ですが、
　subFolders変数にディレクトリ名を集めているところで push_backの代わりに searchFolderを
そのまま呼び出せば subFolders変数が不要になりフォルダがたくさんあったときの効率があがります。

　てところです。

[Ma]

>　No:49988でも触れましたが引数の folderNameを参照にすると無駄なコピーが無くなります。
あ、そうでしたね。

>・　？（そんなファイルがある方がおかしいといえばおかしいんですが）".wav"ファイルは
弾いてしまってもいいのでしょうか？
拡張子のみですか。想像してなかったですねｗ
length > 4
を
length >= 4
にします。

>subFolders変数
いわれてみると、確かにそのとおりですね。
これで、コードがさらにシンプルになりますねｗ



Justyさんも、たいちうさんもご協力ありがとうございました。
思っていた以上に、勉強になりました。感謝です。