lsのソースを読みました
lsコマンドって一番使うコマンドじゃないでしょうか．おそらく僕が始めて使ったコマンドもlsだと思います．その時，lsのコマンドの出力が綺麗に整列されて出力されるのがすごく不思議でした．
今考えれば端末幅取得してごにょごにょしてるんだろうな，という事は想像できますが，本当はどうなってるのかな，と思ったのでソース見てみました．
lsには大きく分けて2つあるようで，一つはGNU版(GNU coreutils)，もう一つがBSD版(FreeBSDのもの)で，BSD版の方が読みやすいとのこと．で，そのままFreeBSD版でもいいですが今使ってるこのパソコンはmac os x なのでMac版のlsを読むことにしました(Mac版はFreeBSD版を元にしてるのでだいたい同じです)．Mac版はここのfile_cmdsから入手できます．ただし，ここからダウンロードしてlsをmakeしようとすると，membershipPriv.hがねーぞｺﾞﾙｧ( ﾟДﾟ)と怒られてしまいます．ここからmembershipPriv.hをダウンロードして一緒のディレクトリに入れてprint.cの55行目を #include "membershipPriv.h" とかすればmakeが通ります．ちなみにこのままだとmakeしたとき/tmp/ls に作られるのでMakefileの一番最後に SYMROOT = ./ と付け加えとくと多分幸せになれます．
さて，なんか少し前にlsのソースを読むのが流行った(?)みたいなので多分lsのソース解説してる人がいると思うので詳しい事は省略しますが(ぁ，適当にlsについて書きます．Cの標準ライブラリとそこで使われる構造体等の情報はman(とヘッダ)に載ってるので，困ったらmanに頼ると良いです．ref.vim超便利．
本体となるls.cですがコメントがしっかりされているので読みやすいです．BSD版のlsはFTSというディレクトリ階層を探索するための関数群を使います(ちなみにGNU版はreaddir)．
ls.cにある主な関数の流れは次の通りです
・main()
オプションの処理&ソート関数とプリント関数の選択をしてtraverse()を呼び出す．
・traverse()
ftsを使ってファイルを探索していく．一番の肝．出力候補が見つかると，display()関数を呼び出す．
・display()
ファイルのリストを受けとって，出力の準備をする．実際にプリント処理を行うのはmain()で指定したプリント関数．ちなみにこの関数で使われてるDISLAY構造体はls.hで定義されてます．
FTSについてはman 3 fts に詳しく書いてあるので，これを先に読んどくといいと思います．ざくっと説明すると，
・ fts_open() でディレクトリ探索のハンドルをゲット，この第三引数に比較関数を指定する
・ fts_read() を繰り返し呼ぶことで探索していく(戻り値がファイルを表すFTSENT*，最後はNULLが返る)
・ fts_children() を呼ぶと，fts_read()によって最近返されたディレクトリのファイルのリストが返る．
なんか分かりづらいですがソース見れば流れが掴めると思います．適当に抜粋すると(traverse()関数505 行目から)，
if ((ftsp = fts_open(argv, options, f_nosort ? NULL : mastercmp)) == NULL) err(1, "fts_open"); while ((p = fts_read(ftsp)) != NULL) switch (p->fts_info) { ... case FTS_D: // ディレクトリのとき ... chp = fts_children(ftsp, ch_options); // そのディレクトリのファイルのリスト(ソート済) ... display(p, chp); if (!f_recursive && chp != NULL) (void)fts_set(ftsp, p, FTS_SKIP); break; ...
fts_open()の第三引数ですが，lsは名前順の他にアクセスタイムやサイズなどでソートができますよね．あの関数を指定する訳です．これらの関数はcmp.cで定義されてます(実際にはmastercmpの中でさらにそれぞれの比較関数が呼ばれています)．
プリント関数はprint.cで定義されていて，次の4種類あります
・printcol();
ls -C のときの出力(複数列出力)
・printlong();
ls -l のときの出力(1行ずつ，詳細情報付き)
・printscol();
ls -1 のきの出力(1行ずつ)
・printstream();
ls -m のときの出力(カンマで区切って出力)
ということで，ls -Cするとprintcol()によって出力されます．つまり，このprintcol()を見ればどうやって複数列出力しているのか分かります．ここを見ていきます．
まず，traverse()関数で出力候補のファイル(FTSENT)のリストがあったら，display()関数を呼び出します(558行目)．display()関数でいろいろとごにょごにょやってますが*1，704行目からリストを先頭から辿って情報を集めています．ここで，729行目で次の処理をしています．
if (cur->fts_namelen > maxlen)
maxlen = cur->fts_namelen;
要するに，ファイル名が最も長いものを求めている訳です．ここで集めた情報はDISPLAY構造体に入れられて，最終的にはそれを引数としてプリント関数，printcol()が呼ばれます．
printcol()の肝となる部分を以下に示します(554行目から)
...
for (p = dp->list, num = 0; p; p = p->fts_link)
if (p->fts_number != NO_PRINT)
array[num++] = p;
colwidth = dp->maxlen; // ファイル名の最大長
...
colwidth = (colwidth + tabwidth) & ~(tabwidth - 1); //タブ幅を考慮
if (termwidth < 2 * colwidth) { // 複数出力できない場合
printscol(dp); // 一行ずつ出力
return;
}
numcols = termwidth / colwidth; // 何列出力するか
numrows = num / numcols; // 何行出力するか (numはファイルの総数)
if (num % numcols)
++numrows;
...
base = 0;
for (row = 0; row < numrows; ++row) {
endcol = colwidth;
if (!f_sortacross) // ls -C のとき
base = row;
for (col = 0, chcnt = 0; col < numcols; ++col) {
chcnt += printaname(array[base], dp->s_inode,
dp->s_block); // 出力，戻り値は出力した文字数
if (f_sortacross) // ls -x のとき
base++;
else
base += numrows;
if (base >= num)
break;
while ((cnt = ((chcnt + tabwidth) & ~(tabwidth - 1)))
<= endcol) {
if (f_sortacross && col + 1 >= numcols)
break;
(void)putchar(f_notabs ? ' ' : '\t'); // 文字幅の調整
chcnt = cnt;
}
endcol += colwidth;
}
(void)putchar('\n');
}
colwidth = (colwidth + tabwidth) & ~(tabwidth - 1) ってところがぱっと見なんじゃそりゃ，って感じですがこれはタブ文字を考慮した出力幅を求めています．これは2進数で考えると分かりやすいです．tabwidthは通常8なので，たとえばcolwidthが43のとき，43+8=51(0x33)なので， 0011 0011 & 1111 1000 = 0011 0000 (48) となります．ls -C の出力の要となるのがbaseです．これによって上手い具合に左縦から順にファイルを出力させてます．このようにして，複数列出力ができてる訳ですね．
ということでlsのソースを読んでみて，無事長年の疑問が解決しました．めでたしめでたしヽ(´ー｀)ノ
*1:ちなみに661行目のswitch分でFALLTHROUGHが活躍してます
