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 の本文では、単語とは「( 英字で始まる ) 英字もしくは数字の文字列」と定義されています。
```py
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 を印字
}
```
```c
     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コマンド覚書](https://zenn.dev/hosu/articles/5d0eb1cf475bf4) をご参照ください。
```
$ gcc -g -Wall -o keycount keycount.c
```
- **gdb** を起動します。
```
$ gdb keycount
  ....
```
- **b main** コマンドで、**main** 関数の入り口にブレークポイントを設定し、**r** コマンドでプログラムをスタートさせます。
```c
(gdb) b main
Breakpoint 1 at 0x11f5: file keycount.c, line 27.
(gdb) r
Starting program: /home/ .... /keycount
```
- プログラムは、設定したブレークポイントの手前で停止します。
- **n** コマンドで 1 ステップずつ進めてみます。
- **n** コマンドは、直前の 1 文を処理して、直後の文の手前で停止します。
- プログラム中に現れた関数は停止しないで実行されます。
```c
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>"** と入力します。
```c
int <Enter>
32              if (isalpha(word[0]))
(gdb) p word
$1 = "int", '\000' <repeats 96 times>
```
- **p** コマンドで **word** を表示させると、**"int"** が格納されていることがわかります。
```c
(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** ループから抜けます。
```c
(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** コマンドでプログラムをスタートさせます。
```c
(gdb) b main
Breakpoint 1 at 0x11f5: file keycount.c, line 27.
(gdb) r
Starting program: /home/ .... /keycount
```
プログラムがブレークポイントの手前で停止した後に、**p** コマンドで **sizeof keytab / sizeof keytab[0]** を表示させます。
```c
Breakpoint 1, main () at keycount.c:27
27      {
(gdb) p sizeof keytab / sizeof keytab[0]
$1 = 32
```
さらに、配列のサイズ **sizeof keytab** と 構造体のサイズ **sizeof keytab[0]** を表示させます。
```c
(gdb) p sizeof keytab
$2 = 512
(gdb) p sizeof keytab[0]
$3 = 16
```
メンバーが実際にどのようにメモリ上に配置されているのか調べてみます。**p** コマンドで、メンバーのアドレスを表示させます。
```c
(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 バイト ) が交互に配置されています。
```c
&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 の倍数で効率的にメモリアクセスできるようになっています。
```c
(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}
```
つまり、実際にはキーワードの文字列は、以下のようにメモリ上に配置されていることがわかります。
```c
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** で示します。
```c
    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 行 ) の手前までプログラムが実行されます。
```c
(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[] への書き込み
```c
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
```
:writing_hand_tone1: プログラムのステップごとの説明
```py
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 文字目の読み込み
```c
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
```
:writing_hand_tone1: プログラムのステップごとの説明
```py
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 文字目の読み込み
```c
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
```
:writing_hand_tone1: プログラムのステップごとの説明
```py
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 文字目の読み込み
```c
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
```
:writing_hand_tone1: プログラムのステップごとの説明
```py
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 行 ) に設定し、プログラムを実行します。
```c
    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>"** を入力します。
```c
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 であることを確認します。
```c
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 であることを確認します。
```c
(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 を返します。
```c
(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** ループの先頭に戻って停止します。
```c
(gdb) n
55                  low = mid + 1;
(gdb) n
50          while(low <= high) {
(gdb) p low
$6 = 16
(gdb)
```
:writing_hand_tone1: プログラムのステップごとの説明

```c
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 増やします。
```c
33      if((n = binsearch()) >= 0) --> if((n = 16) >= ) --> if(True)
34          keytab[n].count++ --> keytab[16].count++ --> "int"の count を +1
```

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

```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;
}
```