GNU catを読む - next_line_num()編

昨日、catのソースを読んでいて謎だったnext_line_num()の処理を解析してみた。

実際の動作を確認する。

cat -nで行番号表示が出来る。

% cat -n next_line_num.c
     1  #include <stdio.h>
     2  #include <stdlib.h>
     3
     4  #define LINE_COUNTER_BUF_LEN 20
     5  static char line_buf[LINE_COUNTER_BUF_LEN] =

表示桁数が固定なのが痛いが、catで行番号を表示することはまず無さそうなので、こんなもんかなぁと思う。

解析してみる。

next_line_num()を抜き出して遊んでみた結果。

解析結果はコメントに書いた。

#include <stdio.h>
#include <stdlib.h>

// 頭悪すぎコメント。
/* Buffer for line numbers.
   An 11 digit counter may overflow within an hour on a P2/466,
   an 18 digit counter needs about 1000y */
#define LINE_COUNTER_BUF_LEN 20
static char line_buf[LINE_COUNTER_BUF_LEN] =
  {
    ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ',
    ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '0',
    '\t', '\0'
  };

/* Position in `line_buf' where printing starts.  This will not change
   unless the number of lines is larger than 999999.  */
static char *line_num_print = line_buf + LINE_COUNTER_BUF_LEN - 8;

/* Position of the first digit in `line_buf'.  */
static char *line_num_start = line_buf + LINE_COUNTER_BUF_LEN - 3;

/* Position of the last digit in `line_buf'.  */
static char *line_num_end = line_buf + LINE_COUNTER_BUF_LEN - 3;

static void
next_line_num (void)
{
  char *endp = line_num_end; // 最後の数字ポインタ 999
                             //                     ^
  do
    {
      if ((*endp)++ < '9') // 数字をインクリメント桁が増えなければループ終了。
	return;
      *endp-- = '0';       // 990 900 000
    }
  while (endp >= line_num_start); // 新桁がなければここまで(めっさはえぇ)
  
  if (line_num_start > line_buf)
      *--line_num_start = '1'; // 1000 & startを一個増やす
  else
      *line_buf = '>';         // 桁が溢れたら>0000

  if (line_num_start < line_num_print)
    line_num_print--;          // 表示用桁を増やす(初期は6桁)
}

int main(void)
{
    int i;
    for(i = 1; i <= 100000000; i++)
        next_line_num();
    printf("%s\n", line_buf);

    exit(EXIT_SUCCESS);
}

文字列テーブルを使った低レベルなインクリメント処理。ポインタを下桁から順にインクリメントしていきますが、インクリメント処理は僅か1行。他は全て桁が増えたときの処理です。うまくまとまっていると思います。

殆どの場合、do~while内で処理が完了。しかも下1桁が9でなければ、一瞬でループ終了。かなり早い。

どんなもんか速度を計ってみた。

% time ./next_line_num
         100000000
./next_line_num  2.00s user 0.00s system 77% cpu 2.566 total

1億回ループを回しても2秒。はえぇぇ。

まとめ

  • コメントはユーモアを交えよう。
  • GNUのコードは変数名がわかりやすい。
  • GNUは速度、移植性に優れている。
  • 低レベルな処理はC言語がいいみたい。