K&R プログラミング言語Ｃ ～ 構造体の配列

「K&R プログラミング言語Ｃ」の　「6.3 構造体の配列」で紹介されていた関数をまとめて、C のキーワードの出現頻度を数えるプログラムを動かしてみました。
ソースコードは一番最後に載せましたので、以下のようにコンパイルして実行ファイルを作成してください。

$ gcc -Wall -o keycount keycount.c

以下のように、例えば keycount.c ファイルを入力として実行すると、

$ ./keycount < keycount.c

keycount.c の中で C のキーワードが出現した回数を表示させることができます。以下は実行結果です。

   1 auto
   2 break
   1 case
   9 char
   1 const
   1 continue
   1 default
   1 do
   1 double
   4 else
   1 enum
   1 extern
   1 float
   3 for
   1 goto
  10 if
  19 int
   1 long
   1 register
   7 return
   1 short
   1 signed
   3 sizeof
   1 static
   4 struct
   1 switch
   1 typedef
   1 union
   1 unsigned
   6 void
   1 volatile
   4 while

引き数なしで keycount を起動させてから、文字列を入力することもできます。

$ ./keycount
if print for struct (for (int)
   2 for
   1 if
   1 int
   1 struct

文字列入力後の行頭で Ctrl-d を入力すると、プログラムに EOF が送られます。試しにキーワードの前後に色々な文字を付けて、いくつか入力してみてください。

1. main 関数

main 関数の概要は以下の通りです。K&R の本文では、単語とは「( 英字で始まる ) 英字もしくは数字の文字列」と定義されています。

NKEYS: キーワードの数
getword: 入力から単語を抽出して word[] に格納する。
         入力が英数字(空白はスキップ)以外の場合はその文字、
         英数字からなる単語の場合は先頭文字を返す
binsearch: 単語がキーワードと一致するか調べ、一致したキーワードのインデックスを返す

while (getword( ) の戻り値が EOF でない) {
    if ( 単語の先頭文字が英字である )
        if ( binsearch( ) の戻り値 n が 0 以上 )
            キーワード[n] の count を 1 増やす
}
for ( n:0 ～ NKEYS - 1) {
    if ( キーワード[n] の count > 0)
        キーワード[n] の count と word を印字
}

     1  #include <stdio.h>
     2  #include <ctype.h>
     3  #include <string.h>
     4
     5  #define MAXWORD 100
     6  #define NKEYS (sizeof keytab / sizeof keytab[0])
     7
     8  struct key {
     9      char *word;
    10      int count;
    11  } keytab[] = {
    12      {"auto",    0}, {"break",   0}, {"case",    0}, {"char",    0},
    13      {"const",   0}, {"continue",0}, {"default", 0}, {"do",      0},
    14      {"double",  0}, {"else",    0}, {"enum",    0}, {"extern",  0},
    15      {"float",   0}, {"for",     0}, {"goto",    0}, {"if",      0},
    16      {"int",     0}, {"long",    0}, {"register",0}, {"return",  0},
    17      {"short",   0}, {"signed",  0}, {"sizeof",  0}, {"static",  0},
    18      {"struct",  0}, {"switch",  0}, {"typedef", 0}, {"union",   0},
    19      {"unsigned",0}, {"void",    0}, {"volatile",0}, {"while",   0},
    20  };
    21
    22  int getword(char *, int);
    23  int binsearch(char *, struct key *, int);
    24
    25  /* C のキーワードを数える */
    26  int main(void)
b+  27  {
    28      int n;
    29      char word[MAXWORD] = {};  /* '\0'で初期化　*/
    30
    31      while (getword(word, MAXWORD) != EOF)
    32          if (isalpha(word[0]))
    33              if ((n = binsearch(word, keytab, NKEYS)) >= 0)
    34                  keytab[n].count++;
    35      for (n = 0; n < NKEYS; n++)
    36          if (keytab[n].count > 0)
    37              printf("%4d %s\n", keytab[n].count, keytab[n].word);
    38
    39      return 0;
    40  }
    41

gdb ( デバッガ ) を使ってmain 関数の動作を検証してみます。以下のように、-g オプションを付けてコンパイルすると、デバッグ情報が付加された実行ファイルができます。
※ よく使うgdbコマンド覚書 をご参照ください。

$ gcc -g -Wall -o keycount keycount.c

• gdb を起動します。

$ gdb keycount
  ....

• b main コマンドで、main 関数の入り口にブレークポイントを設定し、r コマンドでプログラムをスタートさせます。

(gdb) b main
Breakpoint 1 at 0x11f5: file keycount.c, line 27.
(gdb) r
Starting program: /home/ .... /keycount

• プログラムは、設定したブレークポイントの手前で停止します。
• n コマンドで 1 ステップずつ進めてみます。
• n コマンドは、直前の 1 文を処理して、直後の文の手前で停止します。
• プログラム中に現れた関数は停止しないで実行されます。

Breakpoint 1, main () at keycount.c:27
27      {
(gdb) n
29          char word[MAXWORD] = {};  // '\0' で初期化
(gdb) n
31          while (getword(word, MAXWORD) != EOF)
(gdb) n

• 入力待ちの状態になるので、"int <Enter>" と入力します。

int <Enter>
32              if (isalpha(word[0]))
(gdb) p word
$1 = "int", '\000' <repeats 96 times>

• p コマンドで word を表示させると、"int" が格納されていることがわかります。

(gdb) n
33                  if ((n = binsearch(word, keytab, NKEYS)) >= 0)
(gdb) n
34                      keytab[n].count++;
(gdb) n
31          while (getword(word, MAXWORD) != EOF)
(gdb) p n
$2 = 16
(gdb) p keytab[n].count
$3 = 1

• n コマンドで 33, 34 行を実行した後に、P コマンドで、n と keytab[n] を表示させると、n = 16, count = 1 になっています。
• n コマンドで 31 行を実行すると、入力待ちの状態になるので、<Ctrl-d> ( EOF ) を入力します。
• 31 行の while ループから抜けます。

(gdb) n
<Ctrl-d>
35          for (n = 0; n < NKEYS; n++)
(gdb) n
36              if (keytab[n].count > 0)
(gdb) n
35          for (n = 0; n < NKEYS; n++)
(gdb) u
   1 int
39          return 0;
(gdb) c
Continuing.
[Inferior 1 (process 4909) exited normally]
(gdb)

• 結果を表示する for ループ ( 32 回繰り返す ) に入りますが、途中で u コマンドを入力すると、ループから抜けます。
• キーボード入力の文字列には int というキーワードが 1 回出現したという結果が得られます。
• 最後に c コマンドでプログラムを最後まで走らせて終了します。

2. 構造体 ( キーワード、カウント ) の配列

キーワード ( char *word ) と出現回数 ( int count ) をメンバーとする構造体 ( key ) を定義し、それを要素とする配列 ( keytab[ ] ) を定義して初期化します。( 8 ～ 20 行 )

gdb ( デバッガ ) を使って配列や構造体のサイズを調べてみます。以下のように、-g オプションを付けてコンパイルすると、デバッグ情報が付加された実行ファイルができます。

$ gcc -g -Wall -o keycount keycount.c

gdb を起動します。

$ gdb keycount
  ....

b main コマンドで、main 関数の入り口にブレークポイントを設定し、r コマンドでプログラムをスタートさせます。

(gdb) b main
Breakpoint 1 at 0x11f5: file keycount.c, line 27.
(gdb) r
Starting program: /home/ .... /keycount

プログラムがブレークポイントの手前で停止した後に、p コマンドで sizeof keytab / sizeof keytab[0] を表示させます。

Breakpoint 1, main () at keycount.c:27
27      {
(gdb) p sizeof keytab / sizeof keytab[0]
$1 = 32

さらに、配列のサイズ sizeof keytab と 構造体のサイズ sizeof keytab[0] を表示させます。

(gdb) p sizeof keytab
$2 = 512
(gdb) p sizeof keytab[0]
$3 = 16

メンバーが実際にどのようにメモリ上に配置されているのか調べてみます。p コマンドで、メンバーのアドレスを表示させます。

(gdb) p &keytab[0].word
$4 = (char **) 0x555555558020 <keytab>
(gdb) p &keytab[0].count
$5 = (int *) 0x555555558028 <keytab+8>
(gdb) p &keytab[1].word
$6 = (char **) 0x555555558030 <keytab+16>
(gdb) p &keytab[1].count
$7 = (int *) 0x555555558038 <keytab+24>
(gdb) p &keytab[2].word
$8 = (char **) 0x555555558040 <keytab+32>
(gdb) p &keytab[2].count
$9 = (int *) 0x555555558048 <keytab+40>

以下のように整理できて、word ( 8 バイト ) と count ( 4 バイト ) が交互に配置されています。

&keytab[0].word   0x555555558020:[][][][][][][][]
&keytab[0].count  0x555555558028:[][][][]・・・・
&keytab[1].word   0x555555558030:[][][][][][][][]
&keytab[1].count  0x555555558038:[][][][]・・・・
&keytab[2].word   0x555555558040:[][][][][][][][]
&keytab[2].count  0x555555558048:[][][][]・・・・

p コマンドで、keytab[0] ～ keytab[2] を表示させてみます。word の 8 バイトのアドレスには、各キーワードを指すポインタのアドレスが入っています。・・・・部分はパディングされて、8 の倍数で効率的にメモリアクセスできるようになっています。

(gdb) p keytab[0]
$10 = {word = 0x555555556004 "auto", count = 0}
(gdb) p keytab[1]
$11 = {word = 0x555555556009 "break", count = 0}
(gdb) p keytab[2]
$12 = {word = 0x55555555600f "case", count = 0}

つまり、実際にはキーワードの文字列は、以下のようにメモリ上に配置されていることがわかります。

0x555555556004:[a][u][t][o][\0]
0x555555556009:[b][r][e][a][k][\0]
0x55555555600f:[c][a][s][e][\0]

3. 単語の抽出 ( getword 関数 )

K&R の本文では、単語とは「( 英字で始まる ) 英字もしくは数字の文字列」と定義されています。主要な関数、配列、ポインタの説明は、以下の通りです。

関数、配列、ポインタ	説　　　明
getword( )	入力を 1 文字ずつ読み込みながら単語を抽出して word[ ] に格納します。入力が英数字以外の場合はその文字、英数字からなる単語の場合は先頭文字を返します
char word[ ]	単語の格納用配列 ( 最大 99 文字 )
char *w	word と同じアドレスを持つポインタ
getch( )	バッファに文字があればその文字を読み込む。なければ入力から 1 文字読み込む
ungetch( )	バッファに 1 文字保存する

単語は非英数字を検出したときに、単語が完結します。この非英数字は ungetch でバッファ buf[ ] に保存し、次の文字を読み込むときには、バッファに文字があればまずその文字から読み込むようにしています。

この動作をデバッガを使って検証してみます。

gdb を起動します。

$ gdb keycount
  ....

とりあえず、main, getword, binsearch, getch, ungetch 関数の入り口にのところにブレークポイントを設定します。ブレークポイントは b コマンドで設定できますが、gdb を終了すると消えてしまうので、以下のように書いたファイル bp を source コマンドで読み込みます。

b main
b getword
b binsearch
b getch
b ungetch

(gdb) source bp
Breakpoint 1 at 0x11f5: file keycount.c, line 27.
Breakpoint 2 at 0x143b: file keycount.c, line 68.
Breakpoint 3 at 0x13a3: file keycount.c, line 48.
Breakpoint 4 at 0x1528: file keycount.c, line 94.
Breakpoint 5 at 0x156f: file keycount.c, line 99.

ブレークポイントの設定箇所をソースコード上に Bp1～5 で示します。

    25  /* C のキーワードを数える */
    26  int main(void)
Bp1 27  {
    28      int n;
    29      char word[MAXWORD] = {};  // '\0' で初期化
    30
    31      while (getword(word, MAXWORD) != EOF)
    32          if (isalpha(word[0]))
    33              if ((n = binsearch(word, keytab, NKEYS)) >= 0)
    34                  keytab[n].count++;
    35      for (n = 0; n < NKEYS; n++)
    36          if (keytab[n].count > 0)
    37              printf("%4d %s\n", keytab[n].count, keytab[n].word);
    38
    39      return 0;
    40  }
    41
    42  /* binsearch: tab[0]...tab[n-1] の中の語を探す */
    43  int binsearch(char *word, struct key tab[], int n)
    44  {
    45      int cond;
    46      int low, high, mid;
    47
Bp2 48      low = 0;
    49      high = n - 1;
    50      while(low <= high) {
    51          mid = (low + high) / 2;
    52          if ((cond = strcmp(word, tab[mid].word)) < 0)
    53              high = mid - 1;
    54          else if (cond > 0)
    55              low = mid + 1;
    56          else
    57              return mid;
    58    }
    59
    60    return -1;
    61  }
    62
    63  /* getword: 入力から次の語、または文字を求める */
    64  int getword(char *word, int lim)
    65  {
    66      int c, getch(void);
    67      void ungetch(int);
Bp3 68      char *w = word;
    69
    70      while (isspace(c = getch()))
    71          ;
    72      if (c != EOF)
    73          *w++ = c;
    74      if (!isalpha(c)) {
    75          *w = '\0';
    76          return c;
    77      }
    78      for ( ; --lim > 0; w++)
    79          if (!isalnum(*w = getch()))
    80              ungetch(*w);
    81              break;
    82          }
    83      *w = '\0';
    84      return word[0];
    85  }
    86
    87  #define BUFSIZE 100
    88
    89  char buf[BUFSIZE];  /* ungetch 用のバッファ */
    90  int bufp = 0;       /* buf 中の次の空き位置 */
    91
    92  int getch(void) /* (押し戻された可能性もある) 1 文字を取って来る */
    93  {
Bp4 94      return (bufp > 0) ? buf[--bufp] : getchar();
    95  }
    96
    97  void ungetch(int c) /* 文字を入力に戻す */
    98  {
Bp5 99      if (bufp >= BUFSIZE)
   100          printf("ungetch: too many characters\n");
   101      else
   102          buf[bufp++] = c;
   103  }
   104

r コマンドで、プログラムをスタートさせます。
最初のブレークポイント ( Bp1 : 27 行 ) の手前までプログラムが実行されます。

(gdb) r
Starting program: /home/ .... /keycount
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".

Breakpoint 1, main () at keycount.c:27

n コマンドによって、 main 関数で getword 関数が呼び出されて、また main 関数に戻ってくるまでを追いかけてみます。
入力文字列は "int <Enter>"、つまり "int\n" です。

① 1 文字目 の読み込みと word[] への書き込み

Breakpoint 1, main () at keycount.c:27
27      {
(gdb) n
29          char word[MAXWORD] = {};  // '\0' で初期化
(gdb) n
31          while (getword(word, MAXWORD) != EOF)
(gdb) n

Breakpoint 2, getword (word=0x7fffffffdf20 "", lim=100) at keycount.c:68
68          char *w = word;
(gdb) n
70          while (isspace(c = getch()))
(gdb) n

Breakpoint 4, getch () at keycount.c:94
94          return (bufp > 0) ? buf[--bufp] : getchar();
(gdb) n
int
95      }
(gdb) n

プログラムのステップごとの説明

31  while(getword(word, MAXWORD) != EOF)
    |   *w = *word = "", lim = 100
70  |   while(isspace(c = getch()))
94  |   |   return (bufp > 0) ? buf[--bufp] : getchar()
    |   |       --> return(0 > 0) ? buf[--bufp] : getchar()
    |   |       --> return(False) ? buf[--bufp] : getchar()
    |   |       --> return getchar() --> "int <Enter>" と入力
    |   |       --> return 'i'
70  |   while(isspace(c = 'i') --> while(isspace('i'))--> while(False)

② 2 文字目の読み込み

getword (word=0x7fffffffdf20 "", lim=100) at keycount.c:72
72          if (c != EOF)
(gdb) n
73              *w++ = c;
(gdb) n
74          if (!isalpha(c)) {
(gdb) n
79              if (!isalnum(*w = getch())) {
(gdb) n

Breakpoint 4, getch () at keycount.c:94
94          return (bufp > 0) ? buf[--bufp] : getchar();
(gdb) n
95      }
(gdb) n

プログラムのステップごとの説明

72  |   if(c != EOF) --> if('i' != EOF) --> if(True)
73  |       *w++ = 'i' --> *w = 'i', w++, char *word = "i"
74  |   if(!isalpha(c)) --> if(!isalpha('i') --> if(False)
78  |   for( ; --lim > 0; ) --> for( ; 99 > 0; )--> for( ; True; )
    |   {
79  |   |   if(!isalnum(*w = getch()))
94  |   |   |    return (bufp > 0) ? buf[--bufp] : getchar()
    |   |   |        --> return(0 > 0) ? buf[--bufp] : getchar()
    |   |   |        --> return(False) ? buf[--bufp] : getchar()
    |   |   |        --> return getchar() --> return 'n'
79  |   |   if(!isalnum(*w = 'n')), char *word = "in"
    |   |       --> if(!isalnum('n')) --> if(False)
    |   }

③ 3 文字目の読み込み

getword (word=0x7fffffffdf20 "in", lim=99) at keycount.c:78
78          for ( ; --lim > 0; w++)
(gdb) n
79              if (!isalnum(*w = getch())) {
(gdb) n

Breakpoint 4, getch () at keycount.c:94
94          return (bufp > 0) ? buf[--bufp] : getchar();
(gdb) n
95      }
(gdb) n

プログラムのステップごとの説明

78  |   for( ; --lim > 0; w++) --> for(; 98 > 0; w++)
    |   {
79  |   |   if(!isalnum(*w = getch()))
    |   |   |   return (bufp > 0) ? buf[--bufp] : getchar()
94  |   |   |       --> return(0 > 0) ? buf[--bufp] : getchar()
    |   |   |       --> return(False) ? buf[--bufp] : getchar()
    |   |   |       --> return getchar() --> return 't'    
79  |   |   if(!isalnum(*w = getch()) --> if(!isalnum(*w = 't'))
    |   |       --> if(!isalnum('t') --> if(False), char *word = "int"
    |   }

④ 4 文字目の読み込み

getword (word=0x7fffffffdf10 "int", lim=98) at keycount.c:78
78          for ( ; --lim > 0; w++)
(gdb) n
79              if (!isalnum(*w = getch())) {
(gdb) n

Breakpoint 4, getch () at keycount.c:94
94          return (bufp > 0) ? buf[--bufp] : getchar();
(gdb) n
95      }
(gdb) n
getword (word=0x7fffffffdf20 "int\n", lim=97) at keycount.c:80
80                  ungetch(*w);
(gdb) n

Breakpoint 5, ungetch (c=10) at keycount.c:99
99          if (bufp >= BUFSIZE)
(gdb) n
102             buf[bufp++] = c;
(gdb) n
103     }
(gdb) n
getword (word=0x7fffffffdf20 "int\n", lim=97) at keycount.c:81
81                  break;
(gdb) n
83          *w = '\0';
(gdb) n
84          return word[0];
(gdb) n
85      }
(gdb) n

プログラムのステップごとの説明

78  |   for( ; --lim > 0; w++) --> for(; 97 > 0; w++)
    |   {
79  |   |   if(!isalnum(*w = getch()))
    |   |   |   return (bufp > 0) ? buf[--bufp] : getchar()
94  |   |   |       --> return(0 > 0) ? buf[--bufp] : getchar()
    |   |   |       --> return(False) ? buf[--bufp] : getchar()
    |   |   |       --> return getchar() --> return '\n'    
79  |   |   if(!isalnum(*w = getch()) --> if(!isalnum(*w = '\n'))
    |   |       --> if(!isalnum('\n') --> if(True), char *word = "int\n"
    |   |   {
80  |   |   |    ungetch(*w) --> ungetch('\n'), 
    |   |   |       c = *w
99  |   |   |       if(bufp >= BUFSIZE) --> if(0 >= 100) --> if(False)
    |   |   |       else
102 |   |   |           buf[bufp++] = c --> buf[0] = '\n', bufp++
81  |   |   |    break
    |   |   }
    |   }
83  |   *w = '\0', word = "int\0"
84  |   return word[0] --> return 'i'
31  while('i' != EOF) --> while(True)

各ステップで、スコープ内に限られますが、変数や配列の内容を p コマンドで確かめながら検証してみて下さい。条件判断のステップが時々飛んでしまうこともありますが、プログラムの実行順序は確実にトレースできます。

4. 二分探索( binsearch( ) 関数 )

入力から getword 関数 によって抽出された単語が、キーワードと一致するかどうかを binserach という関数で調べ、一致していたら count を 1 増やします。binsearch 関数には二分探索法が使われていますが、この動作をデバッガを使って検証してみます。
gdb を起動して、ブレークポイントを binsearch 関数の入り口 ( 48 行 ) に設定し、プログラムを実行します。

    42  /* binsearch: tab[0]...tab[n-1] の中の語を探す */
    43  int binsearch(char *word, struct key tab[], int n)
    44  {
    45      int cond;
    46      int low, high, mid;
    47
b+  48      low = 0;
    49      high = n - 1;
    50      while(low <= high) {
    51          mid = (low + high) / 2;
    52          if ((cond = strcmp(word, tab[mid].word)) < 0)
    53              high = mid - 1;
    54          else if (cond > 0)
    55              low = mid + 1;
    56          else
    57              return mid;
    58    }
    59
    60    return -1;
    61  }
    62

$ gdb keycount
  ....
(gdb) b binsearch
Breakpoint 1 at 0x133c: file keycount.c, line 48.
(gdb) r
Starting program: /home/ .... /keycount

• 入力待ちの状態になるので、例えば "int <Enter>" を入力します。

int <Enter>

Breakpoint 1, binsearch (word=0x7fffffffdee0 "int", tab=0x555555558020 <keytab>, n=32)
    at keycount.c:48
48          low = 0;
(gdb) n

• 48 行目が実行される前の状態でプログラムは停止します。word には "int" が代入され、tab は keytab の先頭を指し、n には NKEYS = 32 が代入されています。

• s コマンドはライブラリ関数 ( ここでは strcmp( ) ) の中まで入ってしまうので、n コマンドで 1 ステップずつ進めていきます。

• n コマンドで、48 行目が実行され、プログラムは 49 行で停止します。

• p コマンドで low が　0 であることを確かめます。

• n コマンドで 1 ステップ進めて、p コマンドで high が 32 - 1 = 31 であることを確認します。

49          high = n - 1;
(gdb) p low
$1 = 0
(gdb) n
50          while(low <= high) {
(gdb) p high
$2 = 31
(gdb)

• n コマンドで 1 ステップ進めて、while の条件式が判定されて真となるので、while ループに入って 51 行で停止します。
• n コマンドで 1 ステップ進めて、p コマンドで mid が ( low + high ) / 2 = 15 であることを確認します。

(gdb) n
51              mid = (low + high) / 2;
(gdb) n
52              if ((cond = strcmp(word, tab[mid].word)) < 0)
(gdb) p mid
$3 = 15
(gdb)

• n コマンドで 1 ステップ進めて、52 行の if 文の条件式が判定されて False になるので、54 行にジャンプして停止します。
• p コマンドで、tab[mid].word を表示させます。
• 続いて、p コマンドで、cond が 8 であることを確認します。

strcmp("int", "if") は、1 文字目は同じ i なので、2 文字目の n ( 110 ) と f ( 102 ) を比較 ( 引き算 ) して 8 を返します。

(gdb) n
54              else if (cond > 0)
(gdb) p tab[mid].word
$5 = 0x55555555605a "if"
(gdb) p cond
$4 = 8
(gdb)

• n コマンドで 1 ステップ進めて、54 行の if 文の条件式が判定されて True になるので、55 行に進んで停止します。
• n コマンドで 1 ステップ進めて、p コマンドで、low が mid + 1 = 16 であることを確認します。
• プログラムは while ループの先頭に戻って停止します。

(gdb) n
55                  low = mid + 1;
(gdb) n
50          while(low <= high) {
(gdb) p low
$6 = 16
(gdb)

プログラムのステップごとの説明

low = 0, high = NKEYS - 1 = 31, NKEYS = 32, word[] = "int"
50  while(low <= high) --> while(0 <= 31) --> while(True)
    {
51  |   mid = (low + high) / 2 --> mid = 15
52  |   if((cond = strcmp(word, tab[mid].word)) < 0)
    |       --> if((cond = strcmp("int", "if")) < 0)
    |       --> if((cond = 8) < 0) -->if(False)
54  |   else if(cond > 0) --> if(8 > 0) --> if(True)
55  |       low = mid + 1 --> low = 16
50  while(low <= hight) --> while(16 <= 31)) --> while(True)
51  |   mid = (low + high) / 2 --> mid = 19
52  |   if((cond = strcmp(word, tab[mid].word)) < 0)
    |       --> if((cond = strcmp("int", "return")) < 0)
    |       --> if((cond = -9) < 0) -->if(True)
53  |       high = mid - 1 = 18
50  while(low <= high) --> while(16 <= 18)) --> while(True)
51  |   mid = (low + high) / 2 --> mid = 17
52  |   if((cond = strcmp(word, tab[mid].word)) < 0)
    |       --> if((cond = strcmp("int", "long")) < 0)
    |       --> if((cond = -3) < 0) -->if(True)
53  |       high = mid - 1 = 16
50  while(low <= high) --> while(16 <= 16)) --> while(True)
51  |   mid = (low + high) / 2 --> mid = 16
52  |   if((cond = strcmp(word, tab[mid].word)) < 0)
    |       --> if((cond = strcmp("int", "int")) < 0)
    |       --> if((cond = -3) < 0) -->if(False)
54  |   else if(cond > 0) --> else if(-3 > 0) --> else if(False)
56  |   else
57  |       return mid --> return 16
    }

• main 関数の 33 行に戻って、34 行で keytab[16].count を 1 増やします。

33      if((n = binsearch()) >= 0) --> if((n = 16) >= ) --> if(True)
34          keytab[n].count++ --> keytab[16].count++ --> "int"の count を +1

5. ソースコード : keycount.c

#include <stdio.h>
#include <ctype.h>
#include <string.h>

#define MAXWORD 100
#define NKEYS (sizeof keytab / sizeof keytab[0])

struct key {
    char *word;
    int count;
} keytab[] = {
    {"auto",    0}, {"break",   0}, {"case",    0}, {"char",    0},
    {"const",   0}, {"continue",0}, {"default", 0}, {"do",      0},
    {"double",  0}, {"else",    0}, {"enum",    0}, {"extern",  0},
    {"float",   0}, {"for",     0}, {"goto",    0}, {"if",      0},
    {"int",     0}, {"long",    0}, {"register",0}, {"return",  0},
    {"short",   0}, {"signed",  0}, {"sizeof",  0}, {"static",  0},
    {"struct",  0}, {"switch",  0}, {"typedef", 0}, {"union",   0},
    {"unsigned",0}, {"void",    0}, {"volatile",0}, {"while",   0},
};

int getword(char *, int);
int binsearch(char *, struct key *, int);

/* C のキーワードを数える */
int main(void)
{   // 27行目
    int n;
    char word[MAXWORD] = {};  /* '\0'で初期化 */

    while (getword(word, MAXWORD) != EOF)
        if (isalpha(word[0]))
            if ((n = binsearch(word, keytab, NKEYS)) >= 0)
                keytab[n].count++;
    for (n = 0; n < NKEYS; n++)
        if (keytab[n].count > 0)
            printf("%4d %s\n", keytab[n].count, keytab[n].word);

    return 0;
}

/* binsearch: tab[0]...tab[n-1] の中の語を探す */
int binsearch(char *word, struct key tab[], int n)
{
    int cond;
    int low, high, mid;

    low = 0;
    high = n - 1;
    while(low <= high) {
        mid = (low + high) / 2;
        if ((cond = strcmp(word, tab[mid].word)) < 0)
            high = mid - 1;
        else if (cond > 0)
            low = mid + 1;
        else
            return mid;
    }

    return -1;
}

/* getword: 入力から次の語、または文字を求める */
int getword(char *word, int lim)
{
    int c, getch(void);
    void ungetch(int);
    char *w = word;

    while (isspace(c = getch()))
        ;
    if (c != EOF)
        *w++ = c;
    if (!isalpha(c)) {
        *w = '\0';
        return c;
    }
    for ( ; --lim > 0; w++)
        if (!isalnum(*w = getch())) {
            ungetch(*w);
            break;
        }
    *w = '\0';
    return word[0];
}

#define BUFSIZE 100

char buf[BUFSIZE];  /* ungetch 用のバッファ */
int bufp = 0;       /* buf 中の次の空き位置 */

int getch(void) /* (押し戻された可能性もある) 1 文字を取って来る */
{
    return (bufp > 0) ? buf[--bufp] : getchar();
}

void ungetch(int c) /* 文字を入力に戻す */
{
    if (bufp >= BUFSIZE)
        printf("ungetch: too many characters\n");
    else
        buf[bufp++] = c;
}