2009年03月14日

scandirでqsortとbsearchを学ぶ

stream関連とメモリー実装について悩んでいるわけだ。これはdelphiでもそうだった。
XMLやFlashを取り扱う事を考えて連結リストなどは必須だとは思うが
scandirで得られたポインタ配列はいい例なのでこの結果をいろいろ操作して
解を得たいと思った。
今回はとりあえずbsearchの使用とディレクトリーとファイルを分離した名前順ソートあたりまでやった。
scandirで得られる配列は構造体のポインターリストになる。
これは配列の要素のサイズは必ず4になることを意味する。
この形態はdelphiではまさにTListでdelphiの場合はそれが全てだった。
qsortもあった。つまり今とりあえずはTListの実装を目指しているのだと思う。

qsortやbsearchのコールバックでは


Dirent *d0 =*(Dirent **)arg0;

と型キャストしていたのだが

関数自体をwarningだらけ覚悟で

int dir_cmp (const Dirent **d0, const Dirent **d1)

と定義すれば

k= (*d0)->d_type - (**d1).d_type;

などと使える。
コールバック自体特定の構造体用なのだからこれでいいだろう。

「この()」をつけるという事に気づかなくてエラーを喰らっていたのだが
「()」が無い場合は「*(d0->d_type)」とみなされるということなのだろう。

「->」でも「.」でもコンパイル結果は同じになるだろうけれど
結局「*」の分長さは同じだが全体の統一性を考えると「->」の方がよさそうだ。
※ブログの事を考えると->とかかかないといけないが
スペースをいれればいいのかとか微妙に考える。

比較関数だがdelphiの場合は関数型変数としては特定の型を宣言しなくてはいけなかったのだが
Cの場合はポインタ型で良い様だ。


int dir_cmp_nu2 (const Dirent **d0, const Dirent **d1)



int *dir_cmp;

に対して


dir_cmp=&dir_cmp_nu2;
qsort(namelist, d_cnt, 4, dir_cmp);

とかける。
つまりレコードポインタを引数としたクラス型にようやくたどりついたわけだ。

ポインタリストなのでqsortの効率は大きなレコード型と比べて大きい。
また構造体側が別の連結構造をもっていれば作業用のリストとしても有効ではないかと思えた。
まぁ今回はそれはやらないとしてとりあえずsortのバリエーションとbsearchによる探索を行う。

bsearchはqsortと連系するようにできているようだ。

定義は

void *bsearch(const void *key, const void *base, size_t nmemb, size_t size,
int (*compar) (const void *, const void *));


keyには比較すべきデータのポインタを渡す。

int compar( const void *arg0, const Dirent **d1 )
{
//begen
return (strcasecmp((char *)arg0,(*d1)->d_name));
}

今回はstrcasecmpを使ってみた。
strcmpは純然たるcharの値で比較するがstrcasecmpは大文字小文字を区別しない。

第一引数は探索する項目だが今回はchar*だが別にレコード型でも構わない。


int result;
result=bsearch("Etb.jpg", namelist, d_cnt, 4, compar );


resultには配列のインデクスでは無くて要素のポインターが入ってくる。


int index;
if (result)index=(result-(int)namelist)>>2; else index=0;

とすることでインデクスが得られる。
とするとインデクス「0」はデータで無い方が都合が良い。

そもそもscandirやreaddirでは最初は必ず「.」と「..」が頭にくる。
実際「. .」などという名称のファイルやディレクトリーがあればsortすると「..」より上になるが
最初から要素の2つまでをソートの対象外にすれば良い。

今度はコールバックでディレクトリーをファイルより上にするsortをしてみる。
「種類別」sortのプロトタイプだ。


int dir_cmp_nu3 ( const Dirent **d0 , const Dirent **d1 ){
//begen
if ((*d0)->d_type ==4){//dir
if ((*d1)->d_type !=4) return(-1);
} else
if ((*d1)->d_type ==4) return(1);
return (strcasecmp((*d0)->d_name,(*d1)->d_name));
}

4はディレクトリー、8がファイル、10がシンボリックリンクになる。
まず片方だけディレクトリーかどうか比較して
次に文字列比較をしている。


//var
int ix,d_cnt,dir_cmp;
*Dirent dire;


dir_cmp=&dir_cmp_nu3;
qsort(&namelist[2], d_cnt-2, 4, dir_cmp);
for (i = 2; i < d_cnt; ++i) {
printf ("%s\n", namelist[i]->d_name);
}
result=bsearch("Etb.jpg", (int)namelist+8, d_cnt-2, 4, compare );

dire=*((Dirent **)result);
if (result)ix=(result-(int)namelist-4)>>2; else ix=0;
printf("index:%d; %s \n",ix,namelist[ix+1]->d_name);


「..」の位置を「0」とする扱いにしている。
とすると「.」の位置はまったく使わないので
d_filenoにはscandir情報に関連付けたレコードをいれるなどできそうだ。
d_nameは4byteは確保される様なのでポインタは入れられる。


nm2=(int)namelist+4;
printf("%s \n",nm2[-1]->d_name);

とはなから先頭を変えておいてマイナスの添字でもアクセスできる事は確認した。

ちなみに「昇順」を「降順」にするにはstrcasecmpに渡す順番を逆にするだけで良い。
「~func +1」
とbit反転して+1することで符号を反転できるが関数を増やした方がいいだろう。
これで「名前順」ソートは充分だと思う。


posted by Xo_ox at 20:03| Comment(0) | FreeBSDアプリ | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。
×

この広告は180日以上新しい記事の投稿がないブログに表示されております。