アレゴ丿ス 0 テータ構造入門 には , 必ずこの関数を呼び出さなければな り , バケットは構造体 BUCKET 型て表現さ りません。 れます。 関数 find( ) は , 探索を行う関数てす。キー typedef struct bucket { 再ハッシュ手順 のハッシュ値て示されるバケットから始め KEY key ; て , ( a ) 一致するキーが見つかるか , ( b ) 空の DATA data ; バケット ( 値 EMPTY をもつ ) に出会うまて , } BUCKET ; オープンアドレス法ては , 衝突が発生し 再ハッシュしながら調べていきます。 (a) は たときに再ハッシュによって別のバケット ハッシュ表は BUCKET 型の配列として次 目的のデータが見つかったことになり , (b) のように定義されます。ここて , BUCKET にデータを入れます。先ほど紹介した方式 は目的のデータは存在しないことになりま S に E はハッシュ表の大きさを表す定数て , ては , あるバケットがふさがっていたら , あらかじめマクロ定義しておきます。 す。 次のバケット , その次のバケット , と順番 BUCKET ね e [BUCKET SIZE] ; ところて , もしすべてのバケットがふさ に調べていきます。 がっているとき , ハッシュ表に存在しない また , KEY 型は , データがもっキーの値 しかし , ひとたび衝突が発生すると , 連 キーを探索すると何が起きるてしようか ? 空 のほかに , バケットが空てあることを示す 続したバケットがふさがり , さらに衝突が のバケットが存在しないのて , 38 行目の wh ⅱ e EM PTY とデータが削除されたことを示す 発生しやすくなる , という悪循環が起きま 文の条件はつねに成立するのて , 永久に探 す。このような塊が発生すると , ハッシュ DELETED のふたつの特別な値をもっことが し続けることになります。そこて , 再ハッ 表操作の性能が低下することは直感的に理 てきなければなりません。もし KEY 型ては シュした回数をカウントする変数 cou 猷を導 EMPTY や DELETED のような特殊な値を表現 解てきます。 入して , バケットの数だけループしたら探 てきない場合には , BUCKET 型にこの情報 そこて , 再ハッシュの手順をくふうして , 索を打ち切って , データは見つからなかっ なるべく塊が発生しないようにします。ち を入れるためのメンバを追加します。また ょっと考えると , チェイン法と同様にハッシュ値を求める関 たと判断します。 関数 inse 「 t ( ) は , ハッシュ表にデータを挿 数 hash ( ) とキーの比較を行う関数 keye (h(x) + (k) mod B hk (x) 入しますが , 基本的な仕組みは探索と似て ( c は定数 ) qual( ) を使います。 います。キーのハッシュ値て示されるバケ とすればよいような気がします。ちなみに オープンアドレス法によるプログラムを ットから始めて , ( a ) 「空」か「削除ずみ」のバ これは , c 個目ごとのバケットを順々に調べ List 3 ( 付録ディスク収録 LIST3. TXT 参 ケットに出会うか , ( b ) 一致するキーが見つ ていくものてす。 c=5 とすると , List 3 ( 付 照 ) に示します。オープンアドレス法ても , かるまて , 再ハッシュを繰り返しながら調 録ディスク収録 ) の関数「 ehash ( ) は次のよう チェイン法と同様に init( ) , find( ) , べていきます。 ( a ) の場合には , そのバケッ になります。 insert( ),delete( ) という 4 つの関数から成り トにデータを登録します。 ( b ) の場合には , int rehash(int h) 立っています。 すてにそのキーをもっデータは登録されて また , このほかに再ハッシュを行うため いるのて , 工ラーとなります ( 具体的には何 の関数 rehash( ) を用意します。再ハッシュ return (h 十 5 ) % BUCKET SIZE ; もせずに 1 を返します ) 。 手順としては , 次のバケットを調べる , と 探索と同様に , 変数 count によって再ハッ たとえば , あるキー a のハッシュ値が 7 だと いうものを採用します。関数 rehash( ) シュの回数を監視します。再ハッシュの回 すると , 再ハッシュの手順てはバケット 12 , ( 14 ~ 17 行目 ) は , 現在のハッシュ値をパラ 数がバケットの数を越えたら , 空きバケッ メータとして受け取り , 再ハッシュした値 17 , 22 ・・・・・・を順番に見ていきます。しかし , トが存在しないのて , テープルが満杯とい この方法ては , たしかに塊が発生しにくく を返します。 うメッセージを出力してプログラムを終了 こて、は , たんに現在のハッシュ値を 1 だ はなるものの , 実際には c 個おきのバケット します。オープンアドレス法ては , ハッシ が続けてふさがってしまうのて , 本質的な け増やして ,BUCKET S に E て除算した余り ュ表が満杯になったらお手上げて , どうし 解決にはなりません。一般的にいって , 現 を返します。たとえば , パラメータの値が ようもありません。 在のバケットの位置のみをもとにして次の 3 なら 4 を , 4 なら 5 を返します。 関数 d 引 ete ( ) は , 探索とほとんど同じコー バケットを決める方式ては , このような塊 関数 init( ) は , ハッシュ表を初期化するも ドになっています。対象となるデータが見 のてす。ハッシュ表の全要素のメンバ key を避けることはてきないことが知られてい っかったとき , そのバケットのキー部分に に , バケットが空てあることを示す値 EMPTY ます。 DELETED という値をセットして「削除ずみ」 再ハッシュのたびに調べるバケットを「ラ をセットします。ハッシュ表を利用する前 にします。 アルゴリズムとデータ構造入門 85

ようにします。たとえば , 「文字列の 1 文字 個 , 90 % のとき 5.5 個のバケットを調べる必 ンダム」に選択するようにすれば塊の発生を 要があります。また , 「ランダムな数列によ 目をそのままハッシュ値とする」というのも 防ぐことが可能てす。これを実現するため ってバケットを調べる」方法ては , 使用率が 立派なハッシュ関数には違いありませんが , には , 1 から B ー 1 まての数が必ず 1 回だけラ 80 % のとき 2.0 個 , 90 % のとき 2.6 個となり それよりは List 1 のように「すべての文字コ ンダムに出現する数列 nl , n2 ・・・・・ nB ー 1 を用意 ードの和をハッシュ値とする」というほうが ます。 しておいて , よいてしよう。また , 「キーの値を 2 乗して この結果から , 大まかにいって , 前者て hk (x) (h(x) 十 m) mod B その中央をとる ( 平方採中法 ) 」という方法に は 80 % , 後者ては 90 % が最大使用率の目安 とします。たとえば , 10 個のバケットがあ よって , ランダムな値が得られることがし と考えられます。このリミットを越えてデ るハッシュ表に対して , ータを登録すると , 調べるバケットの個数 られています。 6 , 1 , 4 , 7 , 2 , 9 , 8 , 3 , 5 は急激に増加して , 探索時間は一定とみな という ( ランダムな ) 数列を用意します。ハ ッシュ値 3 をもっキーに対しては , 次の順番 せなくなります。 ハッシュの応用 てバケットを順に調べます。 ハッシュ関数 ところて , ハッシュという概念は表の探 同様にしてハッシュ値 1 をもつキーに対し 索以外にも応用することがてきます。大き ては , チェイン法て、もオープンアドレス法ても , なデータを , 大量に比較するような場合 , 7 , 2 , 5 , 8 , 3 , 0 , 9 , 4 , 6 ・・・・・・ ( b ) ハッシュ法を応用して処理時間を短縮する ハッシュ関数が均等なハッシュ値を発生す となります。ここて , 再ハッシュ系列 ( a ) て ることを前提としています。ここていう「均 ことがてきます。 はバケット 7 の次はバケット 0 になりますが , あらかじめ各データのハッシュ値を計算 等」とは , すべての可能なキー値を対象とし 再ハッシュ系列 ( b ) によればバケット 7 の次は しておきます。そして次の手順て比較を行 たときに , ハッシュ値が均等に等確率て、生 バケット 2 になります。このように , バケッ います。まず , ハッシュ値を比較して , も 成される ( 静的に均等 ) だけては不十分て、す。 トが衝突したとしても , 次に選択されるバ しハッシュ値が等しくなければ , この時点 実際には , すべてのキーの値が等確率て、出 ケットが別なのて、 , 塊がてきる現象を回避 て , ふたつのデータの値は異なっているこ 現するわけて、はなく , キーの値はかなり偏 てきます。 とがわかります。ハッシュ値が等しければ , オープンアドレス法の データ本体が等しいかどうかを比較します。 キーとして実際に出現する値に対して , ハ 解析 ッシュ値が均等に振り分けられる ( 動的に均 この方法ては , ①データが等しい 等 ) ことが望まれます。 ②データは等しくないが , たまたまハ プログラム中の変数名を考えると , al, オープンアドレス法の解析は難しいのて , ッシュ値が一致した ・・といった系統的な変数名を使用する 計算の過程を省いて結果だけを Table 3 に示 a2 ・・ という場合にかぎって , データ本体の比較 のはよくあることて、しよう ( こういった無機 しましよう。詳しくは , 参考文献 [ 1 ] [ 2 ] が行われます。てすから , ほとんどの場合 的な変数名のつけ方は , 悪いプログラミン を当たってください グスタイルて、すが , ここて、は例として考え にデータが等しくないようならば , ハッシ TabIe 3 は , 探索を行ったときに平均する ュ値の比較だけてすむのて、処理時間が大幅 てください。また , プログラムを自動生成 と何個のバケットを調べなければならない するようなツールは , 通常このような名前 に短縮されます。 かを , ハッシェ表の使用率の関数として表 ところて、 , この手法は , 計算量のオーダ を発生します ) 。たとえば , 先ほどの List 1 しています。また , この表て、は , 探索が成 ーを下げずに , たんに定数係数を下げるだ て示したハッシュ関数ては , al と a2 , a12 と 功したとき ( データが見つかったとき ) と探 けのいわばセコい技法て、すが , 大量の比較 a21 に対して同じハッシュ値を生成してしま 索が失敗したとき ( データが見つからなかっ を行うプログラム ( たとえば diff) ては実行の います。プログラムを書くにあたっては , たとき ) に場合分けされています。探索に成 実験を行って , 生成されるハッシュ値が均 向上にかなり寄与します。 功したときがハッシュ法の性能を表現する この方式は , データが等しいか等しくな 等に分散することを確かめる必要がありま と考えられます。 いかの比較しか扱えないのて , データの大 実際に値を代入して計算すると , 「再ハッ す。 小が問題になる場合には利用て、きません。 シュ時に順番にバケットを調べる」という単 ハッシュ関数は , て、きるかぎりキーのす べてのビットがハッシュ値に影響を与える 純な方法ては , 表の使用率が 80 % のとき 3.0 9 , 4 , 7 , 0 , 5 , 2 , 1 , 6 , 8 ・・・・・・ ( a ) 86 CMAGAZINE 19 11

最新 コンバイラレポート ソフト開発用に最適′ 豊富に揃った C 言語用 ライプラリ 1 . マルチ画面ライフラリ ( キャラクタータイプ ) TabIe 3 テスト結果 番号 〔容量約 20KB 定価 2 万円〕 画面テータの、 C 言語の関数コール及びデ ータファイルの読み込みの両方で作成を 可能にします。作成したマルチ画面は、キ ーボードからの入力も可能。しかもマルチ 画面は階層的に表示し、メニューをマウス クイックすることにより、設定した関数ポ インタへのコールが行えます。テータ部の メモリー容量は 64KB ( 標準画面約 10 枚分 ) まで指定可能です。 判定 テスト内容 円記号で終わる行の連結処理 コメント , 文字列リテラル連結 トリグラフシーケンス limit. h froat. h 識別子の有効長 スコープ規則 ( 変数名とラベル ) スコープ規則 ( メンバ名 ) テータ型 (long, double, unsigned, signed char) 型指定子 unsigned, long 型定数 文字定数 Ox 幵 工スケープシーケンス wcha 「 -t 型 int 型定数の型変換 float 演算 配列 , 関数のポインタ 関数へのポインタ変換 void 型へのキャスト void 型汎用ポインタ 関数プロトタイプ 十単項演算子 右辺値の sizeof 構造体の代入 , 関数への引渡し , 戻し スコープ規則 const 型指定子 vo t ⅱ e 型指定子 引数省路 関数プロトタイプ 構造体 , 配列の初期化 変数の初期化 switch, case 文のテータ型 stati c の仮定義 条件っきコンバイル マクロ定義名でのインクルード # define トークン連結 , マクロ展開 # pragma 定義ずみマクロ errn 0 変数 0 幵 setof 関数 assert マクロ ctype. h locale. h math. h setjmp. h signal. h stdarg. h stdio. h, 複数回インクルード FOPEN-MAX, FILENAME MAX 記号定数 ファイルストリーム関数 rename, remove 関数 scanf, printf, ungetc 関数 可変長引数 fsetpos, fgetpos 関数 stdlib. h st 0 ⅵ関数のテスト 子プロセス関数 div, 旧ⅳ関数 string. h St 「 e 「「 0 「関数 time. h x △〇〇 x 〇 x 〇〇△〇 x 〇〇〇〇〇 x △〇〇〇〇〇〇〇〇〇〇〇〇〇〇 x 〇〇〇〇 x 0 〇〇〇〇〇 x 〇〇〇〇〇〇〇〇〇〇〇〇 x 〇〇〇〇〇 9 っ一 7 5 8 6 8 7 0 っ 4 6 6 5 5 っ 4 ( 0 3 4 8 0 3 4 5 6 7 8 9 0 1 2 3 4 5 6 8 9 0 1 ' 3 4 5 6 8 9 1 2 ( 0 5 6 8 9 0 1 2 3 4 5 7 9 0 1 っ 4 3 4 5 6 8 9 0 1 っム 3 4 6 7 1 っ 4 3 4 5 6 7 9 1 1 1 1 1 1 1 1 っ 4 2 2 っ 4 2 2 2 っ 4 2 3 3 3 3 3 っ 0 3 3 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 2. グラフィック・ライフラリ 〔容量約 1 .5KB ~ 定価 5 千円 ~ 〕 グラフィックドライバー、凵 O 、 BIOS を C 言語からコールするライブラリー及び、 BAS ℃等と同じウインドウ機能を持たせ る拡張ライブラリーです。 3. マウス・ライフラリ 〔容量約 1 値段 5 千円 ~ 〕 マウスドライバー・ BIOS を C 言語からコ ールするライブラリーです。マウス割り込 みによるユーサー定義サブルーチンを C 言 語で作成可能です。 4. RS ー 232C ・ライフラリ 〔容量約 1 KBæ値段 5 千円 ~ 〕 RS -232C の B ℃ S を C 言語からコールす るライブラリー及び拡張入出力ライブラリ ーです。標準・拡張ボードそれぞれからの 操作が可能です。 ・マルチ画面ライブラリー以外のライブラリーはアセ ンブラソースの提供も可能です。 ・出荷品には取り扱い説明書及びサンプルソフト (C 言語ソース ) が付いています。具体的な使用方法の 確認、テスト等はサンプルソフトで簡単に行えます。 ・上記のライブラリーは NEC の PC -98XA 、 PC- 9801 L V で開発、動作確認しています。ハイリゾモ ード、ノーマルモード両タイプを用意しています。 OS は MS-DOS(Ver3. 3A ) 、開発ツールは MS - DOS マクロアセンブラ ( Ver2.0 ) 及び MS-C (Ver5. 1 ) を使用しています。 PC シリーズの他の 機種での適合性は確認していません。 ☆詳しい資料をこ用意致しております。 お気軽にお申し込みください。 ☆購入後、使用不適合とわかった場合は一週間以内に こ返送ください。 ( おそれ入りますが送料はこ負担願います ) ※ MS - DOS および MS - C 、 MS - DOS マクロアセ ンプラはマイクロソフト社の登録商標です。 0 資料請求・こ注文は 62 円切手同封の上、直接下記住、 所まで封書にてこ連絡ください。 ※電話は対応不可能な場合 ( 留守電 ) がありますのでヨ こ遠慮ください 6 〒 571 大阪府門真市下島町 9 の 16 石川聖昭 ( TEL07 加ー 81 ー 87 留守番電話 ) く資料請求番号 158 〉 最新 C コンバイラレポート 1 141

な振舞いをします。このことは , 十分に注 ルした結果は Fig. 2 のように , table はコー 割り込み処理 意する必要があります。 ドセグメント ( ROM ) におかれ , tb ゆはデータ ROM プログラムにおけるイニシャライザ セグメント ( RAM ) におかれます。 LSIC て、は , 割り込み処理もて、きます。た の役割りは「定数テープルを実現する」こと だし , 「割り込み手続き宣言」などは用意さ て、あり , 変数を初期化することて、はありま アセンプラと C のリンク れていません。て、すから , コンパイラは割 せん。変数の初期化は , 明示的に代入文て、 り込みの入り口て、の全レジスタの待避 , 出 行う必要があります。また , 文字列は「記憶 関数引数の受け渡しにはレジスタ A, ロて、のレジスタの回復 , そして割り込みマ クラス static て、ある初期化された文字の配列」 HL, DE, BC とスタックが使われます。レ スクの解除といったシーケンスは生成しな て、あり , コードセグメントに配置されるた ジスタが使われるため , 関数呼び出しのオ いのて、 , こういった処理はアセンプリ言語 めに , ROM に書き込んだ場合にはその値を ーバヘッドは非常に軽くなっています。 て、書かなくてはなりません。 変えることはて、きません。 レジスタに割り当てられる対象となるの C プログラムの中て、 , 割り込みを禁止した 例を示します。 List 4 のソースをコンパイ は , データの大きさが 2 バイト以下て、 3 番目 り , 解除したりという処理が必要な場合は , ヘッダファイル machine. h の中て、定義されて いる di マクロと ei マクロを使用します。 また , 割り込み処理と , 通常の処理の両 方から呼ばれる関数がある場合 , その関数 は recursive にしておく必要があります。再 帰呼び出しはしていなくても , 再入の可能 性が要求される場合は , recursive にしなけ ればいけません。 Z80 の割り込み処理も行うことがて、きま す。次の例は , CTC を使った Z80 の MODE 2 の割り込み処理記述例て、す ( List 3 ) 。 List 3 のようにザイログニーモニックて、書 かれているアセンプリ言語は LSI C ー 80 のア センプラ r80 て、はアセンプルて、きません。岩 崎技研工業の PROASM-II または Microsoft 社の M80 て、アセンプルします。 定数テープレの扱い イニシャライズされている変数のうち , 己憶クラスが static と extern のものはコード セグメント ( CSEG ) に配置されます。 CP/M 環境下のように RAM 上て、プログラムを動か す場合には , これらの変数の値を変更する ことがて、きます。しかし , そのプログラム を ROM に書き込んだ場合にはどうなるて、し ようか ? これらの変数はコードセグメント に置かれるのて、値を書き換えることがて、き なくなり , あたかも「定数」て、あるかのよう 72 CMAGAZINE 1990 11 lSt アセンプリ言語 : EXTRN CSEG i n t0 ma 1 n : 初期設定を行う。 START : SP, スタックのアドレス A,HIGH INTVEC 2 : CTC の割り込みべクタの設定を行う ( し 0 W I NTV EC の設定 ) JR ma 1 n : 割り込みべクタテープル ページバウンダリーにする。 INTVEC: CTCINTO CTCINTI CTCINT2 CTCINT3 : 割り込みルーチン CTCINTO: PUSH AF PUSH BC PUSH DE PUSH H し CA しし int0 POP H し POP DE POP POP AF RETI : C 言語の関数を呼び出す。 一三ロ 語 int0() VO i d

ROM 化 考察 プログラミン モデルが考えられる。 る。これらの 8086 と異なる点は , 各セグメ ないリテラルデータ , たとえば文字列定数 まず , 全ページレジスタを同じ値にして ントの一部がほかのセグメントと重なるこ や多くの CPU て、の doub 形の定数 , そして おけば , ニマムモードのとき , 同じく 8080 とはありえないということて、ある。 型修飾子 const がつけられた静的変数 ( 定 モデルになる。 数 ? ) などはすべてリテラルになる。 メップの考え方 そして , CP レジスタと DP レジスタの値を データは , 実行前にある特定の内容に初 変えることによって , プログラムとデータ 期化される静的変数て、ある。 のアドレス空間を別々に取ることがて、きる 0 初期化データは , 初期値として 0 をもつ ようになる。ページレジスタはアドレッシ ROM 化可能なプログラムの書き方は前述 静的変数て、ある。 ングの際に 24 ビット長て、表される全アドレ したとおりて、あるが , それを実際に ROM に そしてこれらのデータを 3 種類の記憶領域 焼き付けるためには , 静的変数を具体的に ス空間の上位 8 ビットになり , 下位 16 ビット ( テキスト領域 , データ領域 , BSS 領域 ) に が汎用レジスタまたはプログラムカウンタ メモリのどこへ割り当てるかを決定する必 任意に割り当てる。これらは物理的な記憶 ( 以下 PC レジスタ ) や絶対アドレス指定の値 要がある。 WSL C て、はそれらについて柔軟 領域にそのまま対応する。 に指定することがて、きる。 テキスト領域は書き換えられない領域て、 になるから , アドレス空間は 64K バイト単位 のセグメントに分割される。そこて、 , 8086 WSL C て、のデータは , 関数 , リテラル , ある。書き換えられることのないデータ , データ , 0 初期化データの 4 種類に分類され すなわち関数や定数のために使用て、きる。 と同じようにスモールモデル ( プログラム 1 セグメント , データ 1 セグメント ) , ミディ この領域は書き換えられないのて、 ROM に割 アムモデル ( プログラム複数セグメント , デ 関数とはその名のとおりプログラムの実 り当てることがて、きる。 ータ 1 セグメント ) , コンパクトモデル ( プロ 行部分本体て、あり , 残り 3 つが実データにな データ領域は実行前にある特定の内容に グラム 1 セグメント , データ複数セグメン 初期化される領域てある。定数や静的変数 る。 ト ) , ラージモデル ( プログラム複数セグメ リテラルとは定数のことて、ある。プログ のために使用て、きる。この領域には初期値 ント , データ複数セグメント ) が考えられ ラム中のインストラクション中に展開て、き があり , そしてそれらは書き換えることが て、きる。したがって , C プログラムの ROM マナーの悪いプログラム例 化の際に , この領域を単純に ROM か RAM のいずれに割り当てるとはいえない。この 間題に対して , 何通りかの方法が考えられ ① この領域にデータを出さない。つま り , めんどうなこの領域をプログラ ム中からなくしてしまう ② この領域を ROM に割り当て , プログ ラム中で書き換えを行わないように コーディングする ③ この領域を RAM に割り当て , 初期値 をプログラムの実行前または入口で ROM からロードする ③の方法はもっとも汎用性が高く , ROM 化にあたっても , 通常のオペレーティング システム上て、のプログラミングとなんら変 わらないのて、 , プログラミングの上て、はよ いのて、あるが , 実現のために仕掛けが必要 なことと , ROM と RAM の両方を消費しメ モリが無駄て、あるなどの問題がある。 特集 ROM 化プログラミング考察 57 lSt ィー 4 ワっ 0 4 ・ ^. 0 っー char *P : ” abC ” : P p [ 2 ] Fig 1 C プロクラムのメモリへのマッピンク、 ・関数 ・テキスト領域 初期値あり 書き換えなし ・テータ領域 初期値あり 書き換えあり —x6 ROM ・リテラル const int X = 3 ; abc ・テータ inty=4, ・セロ初期化テータ int2=O; —x4 RAM ・ BSS 領域 初期値は 0 のみ 書き換えあり

split-dir() 関数 List を思い出せるようにしておくべきてした。 その前の配列もグローバル変数なのて , やはり名前は Drive [ ] , Dir [ ] などにすべ きだったて、しよう。 ファイルを , MS-DOS の DEL コマンドて、 消去すると , ディスク上のディレクトリ項 目 ( = ファイル情報項目 ) の , ファイル名の 箇所の第 1 バイトが , 0xe5 という値に書き換 わってしまうのて、す。そこて , 後て、元のフ ァイル名を復活させるために , コマンド行 て、指定されたファイル名の , 第 1 バイトを , 変数 R にセープしておくのてす。 なお , この 0xe5 という値は , dosfat. h の中 て , DLTD という名前に #define してありま す。それが早速 , 21 行て使われています。 21 行て、は , 逆に , ファイル名文字列の冒 頭バイトを , 消去ファイルのシルシてある 0xe5 に変えています。つまりそれは , 冒頭 バイトが 0xe5 てある文字列として , 消去フ ったのて、奇妙なバグに悩まされました ) , 両 に読み込んて、います。 関数を私が書き改めなければなりませんて ァイルの名前を , 後て探索しなければなら List 4 の r07 行てやっているのは ,FAT と ないからてす。 予備 FAT の内容が同じて、なかったら , その した。 ディスクはエラーディスクてある , という さて , main( ) 関数の 27 ー 33 行て、は , depth 22 ー 25 行ては , グローバル変数 D Ⅳ num ( 深さ ) というものを求めています。それは , に , 指定パス名のドライプを , 値 (): = 0 , チェックて、す。 求めるファイルが存在するディレクトリの 上記にはいろいろな名前が使われていま etc. ) として得ています。 22 ー 23 行は , コマン 深さて、す。ルートディレクトリにあるなら , ド行にドライプの指定がなかった場合の対 すが , それらはすべて , MS-DOS の FAT に 策て、す ( 標準ライプラリ関数の getdisk( ) 関数 固有の定数などとして dosfat. h て定義されて depth = 0 て、す ( 27 ー 28 行 ) 。 に , カレントドライプを問い合わせていま います。 27 行の , す。つまり無指定はカレントドライプとみ direrror( ) 関数はエラー表示ルーチンてあ if( ( fn & D 旧 ECTORY ) は , fnsp 川 ) 関数の解析結果として , ディレ なします ) 。 り , 本稿ては紹介を略します。 e 「 rno は , 処 クトリ ( = サプディレクトリ ) の指定がパス 理系定義のグローバル変数て , システムコ 26 行の readFAT( ) 関数は , dosfat. h< 定義 されている関数てす。その名のとおり , 引 ールのエラーの種類を表す番号が自動的に 名中にないという事態てす。すなわち , 指 数て指定したドライプの FAT ( ファイル配置 定ファイルはルートディレクトリにありま 入ります。ここては , 必要な情報だけをフ 表 [FiIe AIIocation Table] ) を読み込むの イルタするために , Ox0f と AND していま す。 そして , サプディレクトリの指定があっ てす。 す。 FAT とは , ディスク上の各ファイルが , ともかく , FAT の情報を頼りにして , 消 たなら ,split_dir( ) 関数をコールして , depth 何番目のセクタから何番目のセクタにかけ えたファイルの各セクタを突き止めていく を求めます。この関数も dosfat. h に定義され て ( そのファイルの内容が ) 存在しているか のてすから , ここ <FAT をメモリ上に読み ています (List 5 ) 。 を記述している表てす ( List 4 ) 。 込んておくことは必須なのてす。 sp ⅱ t ー di 「 ( ) 関数には引数として , 分解した ご覧のように , readFAT( ) 関数は , Turbo なお , Turbo C は , Ver. 1.5 の段階ては , パス名の中の , ディレクトリ名を入れた配 列てある dir [ ] を与えます。 C の標準ライプラリ関数 absread( ) を使っ absread( ) 関数と abswrite( ) 関数に , コール 上記の S07 行が何を判断しているかという て , ディスク上の FAT と予備 FAT をそれぞ 側のレジスタ変数をセープしていない と れ , グローバルな配列 FAT [ ] と rFAT [ ] と , * p が文字て * ( p 十 1 ) 0 なら , ディ いうバグがあり ( 最初そのことがわからなか ー亂。い int split_dir(char *cmdlindir) S01 : S02 : S03 : int n = 0 , depth=0; S04 : byte *p, *q; S05 : S06 : p=cm d 1 i nd i r : S07 : S08 : S09 : s 10 : 十十 I en : if((DirnamCdepth]=(byte *)malloc(len + I))==NULL) s 11 : return(0) : s 12 : memcpy (Dirnam[depth] , p + 1 , s 13 : len); *(DirnamCdepth] + len)=0; s 14 : / * 文字列終端子 / * 次の ' Y' をポイントする s 15 : S16 : + + depth; s 17 : len=0; s 18 : if(depth>ll) s 19 : direrror(16) : S20 : DirnamCdepth]=NULL; S21 : return(depth) : S22 : S23 : } / * 最後の ' \ ・を無視するため / * ポインタのリストの終端子 * / C 言語フォーラム 115

0 「 m 面 on from (ompiler ma 「 5 シス弘・ワン Power Ctrace Power Ctrace を 使用した効果的な テパッグ Power Ctrace ( 以下 PCT) を使 用して C プログラムをデバッグした 場合の利点について説明します。 PCT の提供している機能は , ほ かのソースレベルデノヾッガと大差 ありませんが , 高性能な機能を簡 略な操作て、提供し , デバッグ時の 負担を軽減している点に特徴があ ります。 基本的にキーひとつの入力て、操 作がてき , ウインドウごとにまと められた簡易ヘルプ画面を参照す ることて , 操作方法を容易に理解 て、きるようになっています。 こては PCT の機能のうち , よ く使用するものについて述べてお きます。 複数ウインドウの 同時表示 PCT て、は , Table 1 に示す 8 種類 のウインドウから , 同時に 4 つまて のウインドウを表示てきます。 のほかにコマンドキーの一覧を表 示するヘルプ画面があります OPCT 全体にわたる共通コマンドのヘル プ画面と , 現在選択されているウ インドウの固有のコマンドのヘル プ画面とがあり , それぞれファン クションキー亘 , て、表示 されます。 PCT< は , デバッグ時の状況に 応じた適切なウインドウを選択す ることにより , 必要な情報が瞬時 に得られ , デバッグ効率が高くな ります。 たとえば , ソースウインドウ , 出力ウインドウ , 変数ウインドウ を表示すれば , プログラムの流れ を追いながら , プログラムの進行 に伴って変化していく変数の内容 や標準出力画面のようすを確認て きます。 変数の自動表示 / 階層化表示 変数ウインドウては , 使用され ている変数の内容を自動的に表示 します。このため , 変数の名称や 型を覚えておく必要はなくなりま す。 変数ウインドウて表示する変数 には 2 種類あり , ローカル変数とグ ローバル変数に分けられます。ロ ーカル変数は関数ごとに固有なた め , トレースの対象となる関数に 応じて随時変わります。グローバ ル変数は , あらゆる場所から参照 可能なため , 常時表示されていま す。 とくに注目している変数や , 変 数ウインドウのサイズと表示順序 により常時表示てきない変数につ いては , ウォッチウインドウに登 録することにより , 常時参照可能 となります。 また , PCT て、は , ポインタや配 列 , 構造体などについては , 変数 の内容を展開して , さらに詳しい 情報を表示させることがてきます。 この機能により , 変数の個々の要 素をすべて見ることがて、きます。 プレークポイントの 多目的利用 PCT て、のトレースには , 1 ステッ プ実行 , トレーススヒ。ード実行 , フルスヒ。ード実行の 3 つの方法があ ります。このうちトレーススヒ。ー ド実行 , フルスヒ。ード実行ては特 定の場所に到達したり , 特定の条 件を満した場合には , 実行が停止 します。 前者のように , 実行を停止させ るために指定する場所をプレーク ポイントといいます。プレークポ イントは Table 2 て、示す場所に設 定することがて、きます。 プレークポイントは , チェック 済みの部分を飛ばしてトレースし たい場所に移動する場合や , 関数 呼び出しやループて、特定の回数だ け実行してみるといった場合に使 用されます。なお , プレークポイ ントの設定数には制限がありませ ん。 後者のように , 実行を停止させ るために指定する条件をウォッチ ポイントといいます。ウォッチボ イントとして設定てきる条件は , Table 3 に示すものが挙げられま す。 ウォッチボイントては , プレー クポイントと同様に特定の場所ま てスキップしたり , 特定の変数や メモリの内容に注目しながら実行 を止め , 条件成立時の状況を解析 などに使用されます。 なお , ウォッチボイントは最大 32 個まて、設定することがてきます。 TabIe 1 表示可能なウインドウの種類 1 2 3 4 5 6 7 8 ソースウインドウ 出力ウインドウ 変数ウインドウ ウォッチウインドウ メモリウインドウ シンボルウインドウ アセンプラウインドウ 87 ウインドウ C のソースコードを表示 プログラムの標準出力画面を表示 変数の値を表示 ウォッチボイントの設定状態を表示 メモリの内容を表示 外部変数 , 関数のアドレスを表示 逆アセンプルを表示 8087 / 287 の状態を表示 Table 2 プレークポイントの設定場所 1 C ソースコードの 1 ステップ ( ソースウインドウ ) 2 アセンプリコードの 1 命令 ( アセンプラウインドウ ) 3 関数のエントリアドレス ( シンホルウインドウ ) TabIe 3 ウォッチボイントの設定条件 1 2 3 変数の監視 ( 変数ウインドウ ) メモリの監視 ( メモリウインドウ ) 実行状態 ( 実行カウンタ / 関数の深さ ) の監視 lnformation from Compiler Makers 155

プログラムが使用するマクロ定義 List 上記 14 行目の , 表示用文字列は , 現状の , ” usage: REV D 「 ive:%Path*File*n ” て、は , ディレクトリのセパレータ文字てあ るヾ \ 〃が表示されません。次のように書き直 す必要があります。 ” usage: REV Drive:**Path*%File*n ” なお , 余計なことて、すが , 文字列の中な どに \ x 〃という 2 文字のシーケンスがあっ て , それがエスケープシーケンスとして定 義されていない場合 , 結果は , ANSI C< は , 「不定」となっていたと思います。つま り , 処理系が何をやってもよいのて、す。 Turbo こて、注意しなければならないのは , drive C ては , その場合 , 単純に \ クをスキップ ともかく , 19 行ては , コマンド行の指定 [ ] にはコロンを含むドライプ指定 , つま するだけてす。したがって , 上記の未変更 パス名を分解するとともに , それをやった り文字列 : 〃などが入る , dir [ ] には先頭 fnsplit( ) 関数の戻り値が , ローカル変数 fn に の状態ては , usage: REV Drive:PathFile と ・と最後の蹕〃文字を含むディレクトリ指定文 入ります。 表示されてしまいます。 字 , たとえば文字列 $*TC*INCLUDE*S 20 行のヾ甲が , 何だかわからないてしよ 17 行目の bottom erase( ) 関数は , 通常は YS*" などが入る , ext [ ] には先頭のピリ MS-DOS が使用している , 画面の最下の 25 う。これは , char と定義されているグロー オドも含む拡張子 , たとえば文字列ツ TXT ク 行目を , プログラムが使用するというマク バル変数なのて、あります。 ロて、す。それは , 次のようなふたつの定義 などが入るなどの fnsp ⅱ t ( ) 関数の振る舞いの 特殊性てす。 (List 2 ) の組み合わせとして , 私はいろいろ 後から読んでもわかりやすいための , これを知っておかないと , 後のほうて , なプログラムて使用しています。 ソースの書き方の原則① 何のために何をやっているのか , 理解しづ いうまて、もなく , bo れ om 「 esto 「 e ( ) 関数 は , 画面最下行を MS ー DOS に戻すためのマ らい箇所が出てきます。 名前の書き方に区別を設けよ。たとえば 1 ) #define 名はすべて大文字 なお , fnsplit( ) 関数は , 解析したパス名の クロてす。 18 行目の st 「 up 「 ( ) 関数は , 標準ライプラリ 中に「何があったか」という結果を戻り値と 2 ) グローバル変数は頭だけ大文字 3 ) ローカル変数はすべて小文字 して返します。それは , EXTENSION( 拡 関数てす。コマンド行が小文字て、打ち込ま れた場合には , それをすべて , 大文字に変 張子があった ) , FILENAME ( ファイル名が したがって , R ては , いったい何を表して あった ) , DIRECTORY ( ディレクトリ名が えてしまい , 後ての扱いを楽にします。 いるのかわからないのて , たとえば First létter あった ) , DRIVE ( ドライプ名があった ) , 19 行は標準ライプラリ関数 fnsplit( ) を使っ などという名前にして , グローバル変数て て , コマンド行て、指定されたパス名を分解 WILDCARD ( ワイルドカードがあった ) とい あることと , ファイル名の最初の 1 文字 ( 1 バ う 5 つの値の , OR を取った値てす。これら しています。 イト ) をセープするための変数だということ すなわち , argv [ 1 ] の文字列を分解し の実値は , < dir. h > に定義されています。 て , ドライプ名は配列 drive [ ] に , ディレ readFAT() 関数 クトリ名は配列 di 「 [ ] に , ファイル名は配 列 fname[] に , そして拡張子は配列 ext [ ] に , それぞれ収納します。 これらの配列は , グローバル変数として , List 3 のように定義しています。 MAXDRIVE など , 配列のサイズを指定し ている各定数の値は , Turbo C のリファレ ンスガイドを見れば一目瞭然なのてすが , #define bottom-erase() puts ("Yx1b [ 〉 lh " ) #define bottom-restore() puts("Yx1b[>1 ド ) 配列の定義 List char driveCMAXDRIVE], dir[MAXDIR], fname[MAXFILE] , extCMAXEXT) : Li st VOid readFAT(int drive) r01 : r02 : if( absread( drive, Fat_Ien, Fat_start, FAT ) ! = 0 ) r03 : direrror( errno & 0x0f ) : r04 : if( absread( drive, Fat_len, Fat_start + 2, rFAT ) r05 : direrror( errno & 0x0f ) : r06 : if( memcmp( FAT, rPAT, Secsize*2 ) ! = 0 ) r07 : direrror(13); r08 : r09 : } 114 CMAGAZINE 19 11

フラグをつけることによって , —x フラグて、 て、は , 基本的に①②の方法を考えることに メーデレによる データが指定されたのとデータと同じ領域 するが , 場合によっては , ③以外の方法が ツ違い へ割り振ることがて、きる。 使えない場合もあるのて、 , ③についても最 後に簡単に触れることにする。 —x フラグはそのあとに数値をとり , それ ニマムモードては , 前述したとおり , ①②は , 最初に説明した , ROM 化可能な が指定になる。その数値の意味は , 関数ビ 8080 モデルになる。この状態て、は関数とデ プログラムをどう書くかという問題になる。 ット ( 04 ) , リテラルビット ( 02 ) , データビ ット ( 01 ) のそれぞれが 1 ならばテキスト領 すなわち , 0 以外の値て、初期化される静的変 ータは同一のアドレス空間上にあるのて、 , 数は書き換えてはいけないということて、あ 域 , 0 ならばデータ領域という意味になる。 アドレス空間を気にすることなくマップす る。そのうえて、 , 後述するように , コンパ 通常 , ー x6 かー x4 が用いられる。 ることがて、きる。 イル時の指定などて定数や変数をそれぞれ ー x6 は関数とリテラルのビットが立って そこて、通常は , 関数とリテラルをテキス いるから , 関数とリテラルがテキスト領域 テキスト領域に割り振るかデータ領域に割 ト領域に , データをデータ領域に , 0 初期化 り振るかを指定てきるようになっている。 へ , データがデータ領域へマップされる。 データを BSS 領域に割り当てる。 マキシマムモードて、は , 8080 モデルて、あ これはミニマムモードて、用いられる。 その一方て、 ( これも後述するが ) , マキシ マムモードて、は , ①の方法は一般には不可 ー x4 て、は関数ビットのみが立っているの る場合を除いて , 関数とデータは異なるア ドレス空間上にあることになる。すなわち , て、 , 関数のみテキスト領域へ , リテラルと 能になる。 BSS 領域は , 実行前にすべて 0 に初期化さ 関数は CP レジスタに示されるセグメン・ト データはデータ領域へマップされる。これ はマキシマムモードて、用いられる。 れる領域て、ある。初期値として 0 をもつ静的 に , データは DP レジスタに示されるセグメ 変数や , 初期値をとくに指定されていない ントに配置する必要がある。 静的変数に使用てきる。この領域も書き換 通常は , 関数をテキスト領域に , リテラ えられるのて、 RAM に割り当てられる必要が ルとデータをデブタ領域に , 0 初期化データ あるのだが , 実行前または実行時のいちば を BSS 領域に割り当てる。 こうすることに 実行形式オプジェクトは , スタートアッ ん最初にすべて 0 にクリアされる必要があ よって , リテラルについてもほかのデータ プ部 , プログラムをコンパイルしたオプジ る。 ROM 化にあたっても , この領域を使用 と同じようにアクセスて、きるようになる。 ェクト , 実行時ライプラリの 3 つをリンカて、 することにとくに問題はないが , 0 にクリア これを 8080 モデルの場合と同じようにリ リンクすることによってて、きあがる。実行 するという作業は必要て、ある。 テラルもテキスト領域にマップすると , リ 時ライプラリは C の標準的なライプラリて、あ テラルにアクセスするたびに , 一時的に DP なお , BSS 領域に似たものにスタックヒ レジスタまたは EP レジスタを CP レジスタと り , これを使わないて、プログラムを書くこ ープ領域がある。その名のとおり , スタッ 同じ値にする必要があり , コードサイズお ともて、きるが , 非生産的て、ある。 クがここに置かれる。 auto 変数は基本的にスタック上に確保さ よび実行速度の両面て、不利になる。また , そして , リンク時に各記憶領域のマップ されるアドレスも決定される。そのときに れる。また , ma Ⅱ oc ( ) 関数などの標準関数 リテラルへのポインタとデータへのポイン て、確保される動的メモリもこの領域に確保 タの間の整合性が保証て、きなくなり , 正常 ROM 領域と RAM 領域が最終決定されるわ されることがある。 にアクセスて、きなくなる場合もある。 けて、あるが , 最初に述べた ROM 化可能なプ この領域は当然 RAM に割り当てられ , 初 この場合 , リテラルをデータ領域にマッ ログラムて、あれば , テキスト領域は ROM, 期化の必要もない。プログラムの実行前ま プしているのて、 , データ領域は ROM て、ある BSS 領域は RAM に割り当てることがて、きる たは実行時の入口て、スタックポインタ ( H8 / 必要がある。 て、あろう。 WSL C のコードジェネレータ ( p2. h85 ) に 500 ては R7 レジスタがスタックポインタにな データ領域はコードジェネレータ (p2. h85 ) る。以下 SP レジスタ ) をこの領域のもっとも は , オプションフラグとして「一 x 」というも へのフラグが一 x4 の場合は ROM て、ある必要 大きいアドレスにセットする必要がある。 のがある。これは関数 , リテラル , データ があるが , ー x6 の場合はプログラム中て初期 をテキスト領域 , データ領域のどちらに割 以上 , 4 種類のデータを 3 種類の記憶領域 値のあるものにすべて const をつけてリテラ にマップするのてあるが , H8 / 500 て、は CPU り振るかを指定するものて、ある。 ルにしてあればなくなってしまうはずてあ のモードによって多少考え方が変わる ( Fig. 0 初期化データについては必ず BSS 領域に 割り振られるが , 「—bss 」というオプション スタートアップ部ては , 今まて、出てきた アップ 1 参照 ) 。 58 CMAGAZINE 1990 11

アルゴリズム 0 テータ構造入門 0 を返します。この関数も , 今まて説明した 個数に対して十分なバケットを準備してお ったデータが見当たらなかった場合には , find( ) , insert( ) と同様に , まず最初にバケ けば , 一定時間て探索 , 挿入 , 削除の各操 NULL を返します。データは CELL 型て表現 ットを決め , そのバケットに属する連結リ 作を行えることになります。たとえば , 50 したセル内に入っているのて , ここて返さ ストに対して削除の処理を行います。とこ 個のバケットを用意して , そこに 200 個のデ れるのは構造体 CELL 型のメンバ data へのポ ろて , delete( ) は , find( ) や insert( ) に比べ ータを登録する場合 , これらの操作は 0 ( 1 ) インタになります。 るとかなり長くなっています。これは境界 てあるとみなすことがてきるてしよう。し fo 「文の初期化の部分 ( 28 行目の p=table 条件を扱うために場合分けをしているため かし , 50 個のバケットに 10000 個のデータを [hash(key)])<, そのキーが所属している 登録する場合には , もはや N / B を定数とみ てす。 ( べき ) バケットから連結リストへのポイン なすことはてきません。このとき B を一定と タを取り出しています。そして , for ループ すると計算量は 0 ( 1 十 N / B ) = O ( N / B ) = 本体ては , 連結リストをたどりながらリニ チェイン法の分析 O(N) となってしまいます。 アサーチをします。キーが等しいかどうか チェイン法は , 連結リストによるリニア を調べるのに , 先ほど説明した関数 keye さて , ここてチェイン法がどのような性 サーチを改善したものと考えることがて、き qual( ) を使っています。この関数は , ふた 質をもっているかを考察しましよう。バケ ます。バケットに振り分けるという前処理 つのキーが等しければ 1 を , そうてなければ ットの数を B , 登録するデータの数を N とし によって , 連結リストの長さを短かく保ち , 0 を返します。 ます。また , ハッシュ関数は , 全データを リニアサーチても一定時間て探索を行うこ 関数 insert( ) は , ふたつのパラメータを受 すべてのバケットに均等に振り分けるよう とを可能にしているわけてす。 け取ります。ひとつ目のパラメータ key は挿 なハッシュ値を生成すると仮定します。 データの数に比べてバケットの数が少な 入するデータがもっているキーの値て , KEY のとき各バケットには平均 N / B 個のデータ すぎると , 連結リストが長くなってしまい , 型てす。ふたつ目のパラメータ data は DATA 探索にかかる時間を一定時間とみなせなく が入ることになります。 * 型となっていて , 挿入するデータへのポ 探索を行うには , まずハッシュ値を求め なります。 インタてす。データを登録する際には , す てどのバケットを探すべきかを決めます。 チェイン法ては N/B が大きくならないよ てに同じキーをもつデータが登録されてい この計算量は 0 ( 1 ) てす。次に連結リストを うにする必要があります。あらかじめデー るどうかをチェックします。もし , キーが リニアサーチするわけてすが , リストの長 タの個数を見積り , 十分な数のバケットを 重複していたら , 何もしないて挿入に失敗 さは N / B なのて計算量は O ( N / B ) になりま 用意しておきます。もしメモリ容量が許す ことを示す値 0 を返します。キーが重複 す。したがって , 探索全体ての計算量は O ( 1 十 のなら , バケットの数をデータの数より大 していないなら , データを登録して , 挿入 きくしておくこともてきます。 N/B) となります。 に成功したことを示す値 1 を返します。キー 挿入そのものの計算量は , 連結リストの の重複をチェックするために関数 find ( ) を呼び 先頭に要素を挿入するだけなのて O ( 1 ) てす 出しています ( 43 行目 ) 。 オープンアドレス法 みます。しかし , キーの重複チェックのた キーが重複していなかったら , 標準ライ めに探索をするのて , 計算量は結局 0 ( 1 十 N / プラリ関数 ma Ⅱ oc ( ) を呼び出してデータを チェイン法ては , 同じハッシュ値をもつ B) になります。 格納するセルを割り当てます。もし , セル 削除についても , 実際に連結リストから データを連結リストにつなぐことによって , の割り当てに失敗したらプログラムの実行 データを取り除くのは O ( 1 ) てすみますが , 衝突に対処していました。これに対して , を中止します ( 45 ~ 48 行目 ) 。セルを割り当 対象となるデータを探し出すのに探索と同 オープンアドレス法ては , 衝突が発生した てたら , セルにキーとデータをセットして , じだけの手間がかかるのて , 結局は計算量 ときに一定の手順にしたがって別のバケッ キーの値に対応するバケットに連結します トにデータを格納します。この手順のこと は 0 ( 1 十 N / B ) かかります。 ( 49 ~ 53 行目 ) 。 を再ハッシュ (rehash) と呼びます。 ところて , 0 ( 1 十 N / B ) という計算量は , 最後は , 削除を行うための関数 de 回 e ( ) て 実際にどの程度のものなのかを考えてみま チェイン法ては , データそのものてはな す。この関数は , パラメータとして削除し しよう。データの個数 N に対してバケットの く , 連結リストへのポインタをハッシュ表 たいキーを受け取ります。該当するキーを 数 B が十分に大きければ , N / B は定数とみな に登録しました。これに対して , オープン もったデータが存在すれば , そのデータを すことがてきます。このとき計算量は 0 ( 1 十 アドレス法ては , ハッシュ表のバケットに 削除して 1 を返します。該当するキーをもっ N / B ) = 0 ( 1 ) となります。つまり , データの はデータそのものがセットされます。 たデータが見つからなければ何もしないて アルゴリズムとデータ構造入門 83