"simple_hashing": Hash table and binary searching library in C
 Happy Hacking!

simple_hashing: データ要素の差換え・削除が可能なハッシュ・テーブルと二分探索のライブラリ

この C 言語ライブラリは、探索キーとなる複数の文字列からハッシュ値を求める形式のハッシュ・テーブル・データ構造とそれを扱う API を提供しています。このハッシュ・テーブルではデータの挿入・差換え・検索・削除が可能です。
複数のデータ要素のハッシュ値が同一になった場合 (ハッシュ値の衝突)、それらのデータ要素はすべてハッシュ・テーブル構造のエントリが指すデータ要素配列にソートされたうえで追加されていきます。ハッシュ値が衝突するデータ要素のいずれかを探索するために二分探索法を使用しています。さらに、ハッシュ・テーブルに挿入されているすべてのデータ要素を取り出すためのトラバース機構と動的獲得されているメモリ量の取得機能も提供しています。

API を使用するためのヘッダは simple_hashing.h で、API の実装は simple_hashing.c です。API の説明は、この文書で後述しています。

テスト・プログラムとして unit_test.c も記述しました。このテスト・プログラムを Cygwin および GNU/Linux 上で make して実行し次の点について検証しました。

1. すべての提供 API の不正な呼び出しの検出機能。

   API の戻り値と errno の値の組で検出 API が検出した呼び出し側エラーを返します。

2. ハッシュ・テーブルの生成と破棄
3. データ要素の挿入、差換え、削除

   数値を表す文字列・半角記号文字列・小文字英文字列・日本語半角文字列 (SJIS) それぞれについて 2000 個のデータ要素でハッシュ・テーブルを操作しています。
   文字種それぞれの操作のたびに、ハッシュ・テーブルの生成と破棄を行っています。

4. 挿入されたデータ要素すべての取り出し

   上記「データ要素の挿入、差換え、削除」の確認時に、別途作成したハッシュ・テーブルにすべてのデータ要素の複製を挿入しておき、8000 個のデータ要素を取り出しています。

5. データ挿入、差換え、要素検索と削除の性能測定

   総データ要素数を 17298 個から 172980 個まで 17298 個づつ増やしながら、ハッシュ・テーブルへの挿入、差換え、要素検索、削除を連続して行う場合の性能を測定しました。

   ハッシュ・テーブル作成 API へのヒント情報の設定をデフォルト値・挿入データ要素最大数指定・最悪ケースそれぞれの設定を行い Cygwin on Windows-ME で実行 (unit_test -P) したところ、最悪ケース以外では 17298 個づつのデータ増加に対して 1) 挿入-差換え操作は 200 ミリ秒程度づつ延びており、2) 全挿入データの検索-削除操作では最大 120 ミリ秒程度まで延長されました。検索-削除の処理時間の伸び方はデータ探索に二分探索を使用しているため、挿入データ総数 n の指数オーダ O(log n) となっていることも確認しました。

これらのソースコードをコンパイルするために Makefile を使用できます。

ライセンスは GNU Public License とします。

ハッシュ・テーブル・データ構造の説明

1. ハッシュ・テーブル構造体 Hashtable_t

   ハッシュ・テーブルを表現する構造体です。テーブル要素の挿入個数や確保したハッシュ・テーブルの大きさ、データ要素が挿入されているエントリ数などの情報とハッシュ・テーブル・エントリの配列からなります。ハッシュ・テーブル・エントリは Hashtable_elems_t として定義しています。

   Hashtable_t 構造体のメンバそれぞれは下表のとおりの意味を持っています。

   メンバ名	型	意味
   make_hash_value	ssize_t (*)(char **keys, size_t n_keys, ssize_t depth)	'n_keys' 個のキー文字列 'keys' からハッシュ値を求める「ハッシュ関数」への関数ポインタです。 ユーザが指定するハッシュ関数はハッシュ値が求められない場合に負整数を返す必要があります。ハッシュ値の範囲は 0 〜 LONG_MAX です。 API デフォルトのハッシュ関数は simple_hash_value() 静的関数として simple_hashing.c に定義しています。simple_hash_value() がエラーを起こした場合は ILLEGAL_HASH_VALUE を返しています。
   cmp_keys_element	int (*)(char **keys, size_t n_keys, void *elem)	データ要素 'elem' を 'n_keys' 個の 'keys' キー文字列と比較する「比較関数」への関数ポインタです。 この関数は API ユーザが実装して、その関数アドレスをハッシュ・テーブル作成時に指定する必要があります。比較関数の要件については create_hash_table() の説明も参考にしてください。 比較関数の実装例には、unit_test.c で定義している cmp_keys() 静的関数があります。
   elem_cnt_per_page	ssize_t	システムのメモリ・ページに格納できるデータ要素数を示します。 システムのメモリーページ・サイズは sysconf(SC_PAGESIZE) あるいは NBPG マクロのいずれかが使用できる場合はその値をとります。いずれも使用できない場合は 4096kbytes (HASHTABLE_SYSTEM_PAGESIZE_DEFAULT マクロで定義) であると仮定しています。
   depth	ssize_t	ハッシュ・テーブル生成時に指定されたエントリの大きさを示します。 この大きさは、ハッシュ値による振り分けを行いたい数より大きく、かつ、最小の素数を指定するのがよいでしょう。例えば、1000 エントリにデータ要素を振り分けるならば depth には 1009 を指定します。 100,000 番目までの素数のリストが 100000-primary-numbers.txt にあります。
   used_cnt	ssize_t	一つ以上のデータ要素を挿入したエントリの個数を示します。 この値と depth メンバの値の比が、ハッシュ・テーブルの使用率となります。 このメンバの値は get_used_cnt_hash_table() で取得することができます。
   max_insert_cnt	ssize_t	ハッシュ・テーブルに挿入できるデータ要素の最大数を示します。 API デフォルト値は LONG_MAX です。 ハッシュ・テーブルの生成に渡すヒント情報で指定できます。
   alloc_base_cnt	ssize_t	あるハッシュ・テーブル・エントリに初めてデータ挿入を行う際のデータ要素配列長を示します。 API デフォルト値は上記 elem_cnt_per_page の値です。 ハッシュ・テーブルの生成に渡すヒント情報で指定できます。
   alloc_ext_cnt	ssize_t	あるハッシュ・テーブル・エントリのデータ要素配列が不足した際に、メモリ拡張を行う増分のデータ要素数を示します。 API デフォルト値は上記 elem_cnt_per_page の値です。 ハッシュ・テーブルの生成に渡すヒント情報で指定できます。
   inserted_cnt	ssize_t	ハッシュ・テーブルに挿入されているデータ要素の総数を示します。 simple_hashing.h に、挿入されたデータ要素が最大値に達したことを確認する判別マクロ IS_HASHTABLE_TABLES_FULL が定義してあります。 このメンバの値は get_inserted_cnt_hash_table() で取得することが出来ます。
   tables	struct hashtable_elems_t [1]	depth 個のハッシュ・テーブルのエントリを配列として配置するための可変長配列です。 depth で指定されている個数のエントリがハッシュ・テーブル生成時にメモリ獲得されます。つまり、[0] から [depth - 1] までの配列添え字が有効になります。

   ハッシュ・テーブル構造体は create_hash_table() で生成し、destroy_hash_table() で破棄する必要があります。

2. ハッシュ・テーブル・エントリ構造体 Hashtable_elems_t (struct hashtable_elems_t)

   ハッシュ・テーブル構造の tables[] メンバとして使用しているエントリ構造体です。「ハッシュ関数 make_hash_value」を使用してキー文字列から求めたハッシュ値を、tables[] 配列の添え字に適用することでエントリの一つが決まります。
   エントリそれぞれには、ハッシュ値を同じくするデータ要素の個数・データ要素配列の要素数・データ要素配列として確保したメモリ領域へのポインタから構成されています。

   ハッシュ・テーブル・エントリ構造体のメンバそれぞれの意味は下表に示したとおりになります。

   メンバ名	型	意味
   duplicated_cnt	ssize_t	ハッシュ値が等しいデータ要素の個数を示します。 elements メンバが指すデータ要素ポインタ配列の [0] 〜 [duplicated_cnt - 1] の要素それぞれが挿入されているデータ要素を指すことになります。 このメンバの値は get_duplicated_cnt_hash_table() で取得できます。
   elements_len	ssize_t	データ配列ポインタ配列として確保したメモリ領域の要素数を示します。 elements メンバが指すデータ要素ポインタ配列は [0] 〜 [elements_len - 1] までの要素が確保されていることになります。 挿入したデータ要素数が最大値に達していることを確認する判定マクロ IS_HASHTABLE_ELEMS_ELEMENTS_FULL を simple_hashing.h に定義しています。
   elements	void **	データ要素ポインタの配列を指します (つまり、データ要素へのポインタのポインタ)。 データ要素ポインタ配列はデータ要素をハッシュ・テーブルに挿入する際に必要なだけ動的に確保されます。

   ハッシュ・テーブル・エントリ構造の elements メンバが指すデータ要素配列のメモリ領域は、insert_hash_table() および replace_hash_table() で必要時に動的獲得されます。また、獲得されたメモリ領域は destroy_hash_table() が呼び出されるまで解放されません。

ハッシュ関数 simple_hash_value() の説明

static ssize_t simple_hash_value(char    **keys
                               , size_t  n_keys
                               , ssize_t depth
                               )

depth 個のエントリを持つハッシュ・テーブル table の table[] 配列メンバに対して添え字として使用する「ハッシュ値」を、n_keys 個の文字列ポインタ配列 keys から算出して返します。

ハッシュ値の算出は keys 配列の文字列ポインタそれぞれについて以下の処理を繰り返した後、ハッシュ値の符号 bit を落としてから depth のモジェロを求めることで行っています。説明上、ハッシュ値の初期値はゼロとしています。

1. n 番目の文字列を strtol() で整数値に変換します。この時、文字列は 10 進整数を表す数字文字列と仮定しています。
2. 整数値に変換できたならば、ハッシュ値と変換後の整数値の排他的論理和 (^ 演算) を新たなハッシュ値とします。
3. 整数値に変換に失敗した場合、n 番目の文字列の文字それぞれについて以下の処理を行います。
   
   1. c 番目の文字の 8 bits 目を off にします。
      ※これは日本語などの wide character 文字がキー文字列に使用された場合の対処です。
   2. ハッシュ値の 1 byte 目を 4 byte 目に、2 〜 4 byte を 1 〜3 byte 目に移動します。
   3. 上記の処理を施した c 番目の文字とハッシュ値の論理和 (| 演算) を新たなハッシュ値とします

引数が不正な場合、ILLEGAL_HASH_VAL を返します。

性能測定の結果

性能測定の結果は以下の各表のようになりました。結論として、ハッシュ・テーブル生成時にはヒント情報に挿入するデータ要素数を指定するのが処理速度とメモリ獲得量のバランスがよくなっています。

    Hashtable_extend_hint_t    hint;
    hint.max_insert_cnt = <挿入データ要素総数>;
    hint.elems_base_cnt = HASHTABLE_RECOMMENDED_ELEMS_BASE_CNT;
    hint.elems_ext_cnt = HASHTABLE_RECOMMENDED_ELEMS_EXT_CNT;
    create_hash_table(..., &hint);

データ要素挿入量をハッシュ・テーブル生成時に決定できない場合は、create_hash_table() API にヒント情報に NULL を渡すのがよいでしょう。

    create_hash_table(..., NULL);

データ検索の処理時間は下表のようになっています。

データ挿入の処理時間は下表のようになっています。

データ差換の処理時間は下表のようになっています。

データ削除の処理時間は下表のようになっています。

データ要素数に対する動的メモリ獲得量は下表のようになっています。

API の説明

1. ハッシュ・テーブルを生成する create_hash_table()
   

   Hashtable_t create_hash_table(
                                  ssize_t depth
                                , ssize_t (*make_hash_value)(
                                                 char    **keys
                                               , size_t  n_keys
                                               , ssize_t depth
                                               )
                                , int     (*cmp_keys_element)(
                                                 char    **keys
                                               , size_t  n_keys
                                               , void    *elem
                                               )
                                , Hashtable_extend_hint_t *hint
                                )
   

   depth 個のエントリを持つハッシュ・テーブルを生成します。呼び出し側は、cmp_keys_element に複数キー文字列とデータ要素の大小関係を比較する関数のアドレスを必ず指定する必要があります。

   depth は 1 以上の正整数でなければいけません。指定できる最大値は LONG_MAX ですが、あまり大きなエントリ数を指定するとメモリ不足エラーを起こします。

   比較関数は「キー文字列 ＜ データ要素」では負整数を、「キー文字列 ＝ データ要素」ではゼロを、「キー文字列 ＞ データ要素」では正整数を返すように実装されている必要があります。

   make_hash_value には複数キー文字列からハッシュ値を求めるハッシュ関数のアドレスを指定できます。この引数に NULL を渡した場合は、API デフォルトのハッシュ関数 simple_hash_value() 静的関数が使用されます。

   hint はデータ挿入やデータ差換え操作でデータ要素ポインタ配列 (Hashtable_elem_t.elements が指すメモリ領域) をメモリ拡張する際のヒント情報を渡せます。NULL を渡した場合は、API のデフォルト設定が適用されます。
   ヒント情報を指定する場合、ハッシュ・テーブルに挿入する最大データ要素数を Hashtable_extend_t 構造体の max_insert_cnt に、あるハッシュ値に対応するハッシュ・エントリに初めてデータ挿入を行う際のデータ要素配列 (Hashtable_elems_t.elements) の要素数を elems_base_cnt に、そして、データ要素配列のメモリ拡張を行う際の増分データ要素数を elems_ext_cnt に設定します。
   設定するメンバそれぞれについて、API デフォルト設定を使用するには、max_insert_cnt に HASHTABLE_SYS_MAX_INSERT_CNT を、elems_base_cnt に HASHTABLE_RECOMMENDED_ELEMS_BASE_CNT を、そして elems_ext_cnt には HASHTABLE_RECOMMENDED_ELEMS_EXT_CNT を与えます。また、データ要素配列のメモリ拡張を行わないように指定するには elems_ext_cnt に HASHTABLE_NEVER_EXTEND を指定します。

   生成したハッシュ・テーブルは destroy_hash_table() で破棄する必要があります。

   ハッシュ・テーブルが正常に生成できた場合はそのアドレスを返します。なんらかのエラーが発生した場合は NULL を返します。エラーの詳細は errno の値として出力します (正常終了時の errno にはゼロが出力されます)。

   エラーが起きた際の errno の値とその意味は以下のとおりです。

   • EINVAL (22) - 渡された引数が不正です
   • ENOMEM (12) - ハッシュ・テーブルのための動的メモリが獲得できません (メモリ不足)
   
   
2. 動的獲得されているメモリ量を取得する get_allocated_size_hash_table()
   

   size_t get_allocated_size_hash_table(Hashtable_t *table)
   

   ハッシュ・テーブルを作成しデータ挿入することで動的に獲得されたメモリのバイト数を返します。

   エラーが起きた場合は戻り値にゼロが返され errno にゼロ以外の値が出力されます。正常終了時の errno には必ずゼロが出力されます。

   エラーが起きた際の errno の値とその意味は以下のとおりです。

   • EINVAL (22) - 渡された引数が不正です。
     (生成されていない/破壊されたハッシュ・テーブル構造のアドレスが渡された場合など)
   
   
3. ハッシュ・テーブルに挿入されているデータ要素の総数を取得する get_inserted_cnt_hash_table()
   

   size_t get_inserted_cnt_hash_table(Hashtable_t *table)
   

   ハッシュ・テーブル table に挿入されているデータ要素の総数を返します。

   エラーが起きた場合は戻り値に ULONG_MAX が返され errno にゼロ以外の値が出力されます。正常終了時の errno には必ずゼロが出力されます。

   エラーが起きた際の errno の値とその意味は以下のとおりです。

   • EINVAL (22) - 渡された引数が不正です。
     (生成されていない/破壊されたハッシュ・テーブル構造のアドレスが渡された場合など)
   
   
4. データ要素を挿入されているハッシュ・テーブル・エントリの個数を取得する get_used_cnt_hash_table()
   

   ssize_t get_used_cnt_hash_table(Hashtable_t *table)
   

   ハッシュ・テーブル table でデータ要素を挿入されているエントリの数を返します。

   エラーが起きた場合は戻り値に LONG_MIN が返され errno にゼロ以外の値が出力されます。正常終了時の errno には必ずゼロが出力されます。

   エラーが起きた際の errno の値とその意味は以下のとおりです。

   • EINVAL (22) - 渡された引数が不正です。
     (生成されていない/破壊されたハッシュ・テーブル構造のアドレスが渡された場合など)
   
   
5. ハッシュ・テーブルに新規のデータ要素を挿入する insert_hash_table()
   

   Hashtable_t *insert_hash_table(Hashtable_t *table
                                , char        **keys
                                , size_t      n_keys
                                , void        *elem
                                )
   

   ハッシュ・テーブル table に新たなデータ要素 elem を挿入します。挿入できた場合、戻り値に table を返します。
   挿入するデータ要素のキー文字列 keys, n_keys が既にハッシュ・テーブルに挿入されている別のデータ要素と同一である (Hashtable_t の cmp_keys_element 関数がゼロを返す) 場合、挿入は行われずエラー (NULL が返され errno に ESRCH を出力) になります。

   エラーが発生した場合は戻り値に NULL が返され errno にエラー内容が出力されます。
   エラーが起きた際の errno の値とその意味は以下のとおりです。

   • EINVAL (22) - 渡された引数が不正です。

     (生成されていない/破壊されたハッシュ・テーブル構造のアドレスが渡された場合など)

   • ERANGE (34) - キー文字列 keys からハッシュ値を求めることが出来ません。

     (make_hash_value 関数が負数を返している場合)

   • ENOENT (2) - ハッシュ・テーブルには既に挿入最大数 ULONG_MAX のデータ要素が挿入されています。
   • ENOMEM (12) - データ要素配列 elements のメモリサイズを拡張できません (メモリ不足)
     あるいは、ハッシュ・テーブル作成時のヒント情報でメモリ拡張が禁止されています
     
   • ESRCH (3) - 既にキー文字列が同一のデータ要素が挿入されているのでデータ要素 elem の挿入を中断しました。

     (挿入されているデータ要素を別のもので差し替えるには replace_hash_table() を使用します)

   
   
6. ハッシュ・テーブル中のデータ要素を差し替える replace_hash_table()
   

   Hashtable_t *replace_hash_table(Hashtable_t *table
                                   char        **keys
                                 , size_t      n_keys
                                 , void        *elem
                                 )
   

   キー文字列 keys, n_keys が同一のデータ要素がハッシュテーブル table に挿入されている場合に、データ要素 elem で差し換えます。キー文字列が一致するデータ要素がハッシュ・テーブル中に存在していない場合は、insert_hash_table() と同様に、新規データ要素として elem をハッシュ・テーブルに挿入します。

   データ要素の差し替えあるいは挿入ができた場合は、戻り値に table を返します。
   エラーが起きた場合は戻り値に NULL が返され errno にエラー内容が出力されます。

   エラーが起きた際の errno の値とその意味は以下のとおりです。

   • EINVAL (22) - 渡された引数が不正です。

     (生成されていない/破壊されたハッシュ・テーブル構造のアドレスが渡された場合など)

   • ERANGE (34) - キー文字列 keys からハッシュ値を求めることが出来ません。

     (make_hash_value 関数が負数を返している場合)

   • ENOMEM (12) - データ要素配列 elements のメモリサイズを拡張できません (メモリ不足)
     あるいは、ハッシュ・テーブル作成時のヒント情報でメモリ拡張が禁止されています
     
   • ENOMEM (12) - データ要素配列 elements のメモリサイズを拡張できません。

     (メモリ不足)

   
   
7. ハッシュ・テーブルに挿入されている同一のハッシュ値を持つデータ要素数を取得する get_duplicated_cnt_hash_table()
   

   ssize_t get_duplicated_cnt_hash_table(Hashtable_t *table
                                       , char        **keys
                                       , size_t      n_keys
                                       )
   

   ハッシュ・テーブル table に挿入されていて、キー文字列 keys, n_keys から算出するハッシュ値が同一の挿入済みデータ要素数を返します。

   エラーが起きた場合、LONG_MIN を返し errno にエラー内容を出力します。
   エラーが起きた際の errno の値とその意味は以下のとおりです。

   • EINVAL (22) - 渡された引数が不正です。

     (生成されていない/破壊されたハッシュ・テーブル構造のアドレスが渡された場合など)

   • ERANGE (34) - キー文字列 keys からハッシュ値を求めることが出来ません。

     (make_hash_value 関数が負数を返している場合)

   
   
8. ハッシュ・テーブルに挿入されているデータ要素を検索する get_elem_hash_table()
   

   void *get_elem_hash_table(Hashtable_t *table
                           , char        **keys
                           , size_t      n_keys
                           )
   

   ハッシュ・テーブル table に挿入されているデータ要素をキー文字列 keys, n_keys で検索しそのアドレスを返します。

   エラーが起きた場合、NULL を返し errno にエラー内容を出力します。
   エラーが起きた際の errno の値とその意味は以下のとおりです。

   • EINVAL (22) - 渡された引数が不正です。

     (生成されていない/破壊されたハッシュ・テーブル構造のアドレスが渡された場合など)

   • ERANGE (34) - キー文字列 keys からハッシュ値を求めることが出来ません。

     (make_hash_value 関数が負数を返している場合)

   • ENOENT (2) - キー文字列と一致するデータ要素が挿入されていません。

     (unfounded の場合に相当)

   
   
9. ハッシュ・テーブルに挿入されているデータ要素を削除する delete_hash_table()
   

   Hashtable_t *delete_hash_table(Hashtable_t *table
                                , char        **keys
                                , size_t      n_keys
                                , void        *elem
                                )
   

   ハッシュ・テーブル table に挿入されているデータ要素をキー文字列 keys, n_keys で検索し、elem が NULL でなければそのアドレスが検索したデータ要素と一致することを確認したうえで削除します。正常に削除できた場合、 table を返します。

   エラーが起きた場合、NULL を返し errno にエラー内容を出力します。
   エラーが起きた際の errno の値とその意味は以下のとおりです。

   • EINVAL (22) - 渡された引数が不正です。

     (生成されていない/破壊されたハッシュ・テーブル構造のアドレスが渡された場合など)

   • ERANGE (34) - キー文字列 keys からハッシュ値を求めることが出来ません。

     (make_hash_value 関数が負数を返している場合)

   • ENOENT (2) - キー文字列と一致しそのアドレスが削除データ要素 elem と一致するデータ要素は挿入されていません。

     (unfounded の場合に相当)

   
   
10. ハッシュ・テーブルに挿入されているすべてのデータ要素を逐次取得する get_elem_by_hashtable_cursor()
    

    void *get_elem_by_hashtable_cursor(Hashtable_t      *table
                                 , Hashtable_cursor_t **cursor
                                 , Hashtable_cursor_dir_t direct
                                 )
    

    ハッシュ・テーブルに挿入されているすべてのデータ要素を逐次取得するためのトラバース機構を提供します。この機構の実現のために、いわゆるデータ・カーソル方式をとっています。

    トラバース機構を使用するには、まず NULL 値を設定したカーソル・ポインタ cursor のアドレスをトラバースするハッシュ・テーブル table とともに渡します。正常終了した場合、カーソル・ポインタに動的メモリが割り当てられ、ハッシュ・テーブルの先頭データ要素位置で初期化され、先頭データ要素のアドレスが返されます。なお、この時は direct の値は無視されます。
    次いで、カーソルの位置からハッシュ・テーブルの先頭方向 (あるいは末尾方向) の次のデータ要素アドレスを取得するには、HASHTABLE_CURSOR_DIR_PREVIOUS (あるいは HASHTABLE_CURSOR_NEXT) を direct に渡します。既に先頭 (あるいは末尾) のデータ要素位置にカーソルがある場合に、前方 (あるいは後方) データ要素取得を行うとエラーとなり NULL が返ります (errno は EINVAL)。

    direct に HASHTABLE_CURSOR_DIR_CURRENT を渡した場合、現在のカーソル位置にあるデータ要素アドレスが返されます。

    カーソルを破棄するには direct に HASHTABLE_CURSOR_DIR_DESTROY を渡します。このとき、カーソルデータ構造のために獲得されたメモリ領域を解放します。また、この操作の正常な戻り値は table になります。

    呼び出しのそれぞれの場合でエラーが発生すると NULL が返され errno にエラー内容が出力されます。
    エラーが起きた際の errno の値とその意味は以下のとおりです。

    • EINVAL (22) - 渡された引数が不正です。

      (生成されていない/破壊されたハッシュ・テーブル構造のアドレスが渡された場合など)

    • ENOMEM (12) - カーソル・データ構造のメモリ領域を獲得できません。

      (メモリ不足)

    
    
11. ハッシュ・テーブルデータ構造を破棄する destroy_hash_table()
    

    int destroy_hash_table(Hashtable_t *table)
    

    create_hash_table() で生成したハッシュ・テーブル table に割り当てられた動的メモリを解放しハッシュ・テーブルを破棄します。破棄できたらゼロを返します。

    エラーが起きた場合は -1 を返し errno にエラー内容を出力します。
    エラーが起きた際の errno の値とその意味は以下のとおりです。

    • EINVAL (22) - 渡された引数が不正です。

      (生成されていない/破壊されたハッシュ・テーブル構造のアドレスが渡された場合など)

    
    
12. ソートされた配列で二分探索を行う bsearch_array()
    

    int bsearch_array(int (*cmp_keys_elements)(char **keys
                                             , size_t n_keys
                                             , void   *elem
                                             )
                    , void      **array
                    , ssize_t   n_array
                    , char      **keys
                    , size_t    n_keys
                    , ssize_t   *pos
                    , int       *pos_cmp_result
                    )
    

    create_hash_table() に渡すものと同等の比較関数 cmp_keys_elements を使用して配列 array, n_array のキー文字列 keys, n_keys による二分探索を行います。

    探索に成功した場合はゼロ以外の値を返します。探索に失敗した場合および不正な引数が渡された場合はゼロを返します。
    不正な引数が渡されていた場合は errno に EINVAL を出力します。

    探索できた (戻り値がゼロ以外の) 場合、pos に配列要素のインデックスを出力します。
    一方、探索に失敗した (戻り値がゼロの) 場合は、pos にはデータ要素を挿入する配列要素位置を出力し、pos の直前に挿入を行う場合には pos_cmp_result に負整数を、pos の直後に挿入する場合は正整数を出力します。

    エラーが起きた際の errno の値とその意味は以下のとおりです。

    • EINVAL (22) - 渡された引数が不正です。

      (ポインタ引数に NULL が、n_array に負数が、あるいは n_keys に 1 未満の値が渡された場合)