(57)【要約】  メモリ・コンテナ中の検索対象のアイテムに対する開始メモリ・スロットが計算される。当該アイテムが開始メモリ・スロットを占めていないのに応じて、開始メモリ・スロットの直後の第一所定数のメモリ・スロットが探査される。当該アイテムが、それらのメモリ・スロットの１つを占めているのに応じて、そのアイテムがアプリケーションに返される。当該アイテムが、それらのメモリ・スロットの１つを占めていないのに応じて、第一所定数のメモリ・スロットの最終部に関連付けてバリア・ビットが設定されているかどうかの判断が行われる。設定されていれば、当該アイテムについてメモリ・コンテナの少なくとも部分が探査され、見付かれば、そのアイテムはアプリケーションに返される。バリア・ビットが設定されていなければ、通知がアプリケーションに返される。
2020535510.tif 000002
【特許請求の範囲】
【請求項１】
データ処理システムにおいて、メモリ・コンテナに関連して開アドレス法探査バリアを利用する方法であって、前記方法は、
前記メモリ・コンテナ中の或るアイテムを見出す要求をアプリケーションから受信するのに応じて、前記アイテムに対する開始メモリ・スロットを計算するステップと、
前記アイテムが前記開始メモリ・スロットを占めていないのに応じて、前記アイテムについて前記開始メモリ・スロットの直後の第一所定数のメモリ・スロットを探査するステップと、
前記アイテムが、前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの１つを占めているのに応じて、前記アイテムを前記アプリケーションに返すステップと、
前記アイテムが、前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの１つを占めていないのに応じて、前記第一所定数のメモリ・スロットの最後に関連付けてバリア・ビットが設定されているかどうかを判断するステップと、
前記バリア・ビットが設定されているのに応じて、前記アイテムについて前記メモリ・コンテナの少なくとも部分を探査し、前記メモリ・コンテナの前記部分に前記アイテムが見出されたのに応じて、前記アイテムを前記アプリケーションに返すステップと、
前記バリア・ビットが設定されていないのに応じて、前記アイテムが前記メモリ・コンテナ中に存在しないことの通知を前記アプリケーションに返すステップと、
を含む、方法。
【請求項２】
前記メモリ・コンテナの前記部分が、前記メモリ・コンテナの全ての未探査のメモリ・スロットである、請求項１に記載の方法。
【請求項３】
前記メモリ・コンテナの前記部分が、前記開始スロットの直後の第二所定数のメモリ・スロットであり、前記方法が、
前記アイテムが、前記開始メモリ・スロットの直後の前記第二所定数のメモリ・スロットの１つを占めているのに応じて、前記アイテムを前記アプリケーションに返すステップと、
前記アイテムが、前記開始メモリ・スロットの直後の前記第二所定数のメモリ・スロットの１つを占めていないのに応じて、前記アイテムが前記メモリ・コンテナ中に存在しないことの通知を前記アプリケーションに返すステップと、
をさらに含む、請求項１に記載の方法。
【請求項４】
前記アイテムが前記開始メモリ・スロットを占めているのに応じて、前記開始メモリ・スロットからの前記アイテムを前記アプリケーションに返すステップ、
をさらに含む、請求項１に記載の方法。
【請求項５】
前記開始メモリ・スロットがハッシュ・アルゴリズムを使って計算される、請求項１に記載の方法。
【請求項６】
前記アイテムが、前記メモリ・コンテナ中の複数のメモリ・スロットの１つの中に、
前記アイテムを、前記メモリ・コンテナ中の前記複数のメモリ・スロットの１つの中に挿入する要求を受信するのに応じて、前記アイテムに対する前記開始メモリ・スロットを計算するステップと、
前記開始メモリ・スロットが空であるのに応じて、前記アイテムを前記開始メモリ・スロット中に格納するステップと、
前記開始メモリ・スロットが占有されているのに応じて、前記アイテムについて、前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットを探査するステップと、
前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの１つが空であるのに応じて、前記アイテムを前記空のメモリ・スロットに格納するステップと、
前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの全てが占有されているのに応じて、空のメモリ・スロットについて前記メモリ・コンテナの少なくとも前記部分を探査するステップと、
前記空のメモリ・スロットが識別されたのに応じて、前記アイテムを前記空のメモリ・スロットに格納し、前記第一所定数のメモリ・スロットの最後に関連付けて設定される前記バリア・ビットを設定するステップと、
前記空のメモリ・スロットが識別できなかったのに応じて、前記アイテムを前記メモリ・コンテナ中に格納できないことの通知を前記アプリケーションに返すステップと、
を含む方法によって挿入される、請求項１に記載の方法。
【請求項７】
前記メモリ・コンテナの前記部分が前記メモリ・コンテナの全ての未探査のメモリ・スロットである、請求項６に記載の方法。
【請求項８】
前記メモリ・コンテナの前記部分が前記開始メモリ・スロットの直後の第二所定数のメモリ・スロットであり、前記方法が、
前記開始メモリ・スロットの直後の前記第二所定数のメモリ・スロットの１つに空のスロットを前記識別したのに応じて、前記アイテムを前記空のメモリ・スロットに格納するステップと
前記開始メモリ・スロットの直後の前記第二所定数のメモリ・スロットの１つに空のスロットを識別できなかったのに応じて、前記アイテムを前記メモリ・コンテナ中に格納できないことの通知を前記アプリケーションに返すステップと、
をさらに含む、請求項６に記載の方法。
【請求項９】
前記アイテムが、前記メモリ・コンテナ中の複数のメモリ・スロットの１つから、
前記メモリ・コンテナ中の或るアイテムを削除する要求を受信するのに応じて、前記アイテムに対する前記開始メモリを計算するステップと、
前記アイテムが前記開始メモリ・スロットを占めていないのに応じて、前記アイテムについて前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットを探査するステップと、
前記アイテムが、前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの１つを占めているのに応じて、前記メモリ・スロットから前記アイテムを削除するステップと、
前記アイテムが、前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの１つを占めていないのに応じて、前記第一所定数のメモリ・スロットの最後に関連付けて前記バリア・ビットが設定されているかどうかを判断するステップと、
前記バリア・ビットが設定されているのに応じて、前記アイテムについて前記メモリ・コンテナの少なくとも前記部分を探査し、前記メモリ・コンテナの前記部分に前記アイテムが見出されたのに応じて、前記メモリ・スロットから前記アイテムを削除するステップと、
前記バリア・ビットが設定されていないのに応じて、前記アイテムが前記メモリ・コンテナ中に存在しないことの通知を前記アプリケーションに返すステップと、
を含む方法によって削除される、請求項１に記載の方法。
【請求項１０】
前記メモリ・コンテナの前記部分が前記開始メモリ・スロットの直後の第二所定数のメモリ・スロットであり、前記方法が、
前記アイテムが、前記開始メモリ・スロットの直後の前記第二所定数のメモリ・スロットの１つを占めているのに応じて、前記アイテムを前記メモリ・スロットから削除するステップと、
前記アイテムが、前記開始メモリ・スロットの直後の前記第二所定数のメモリ・スロットの１つを占めていないのに応じて、前記アイテムが前記メモリ・コンテナ中に存在しないことの通知を前記アプリケーションに返すステップと、
をさらに含む、請求項９に記載の方法。
【請求項１１】
中に格納されたコンピュータ可読プログラムを有するコンピュータ可読ストレージ媒体を含むコンピュータ・プログラム製品であって、前記コンピュータ可読プログラムは、コンピューティング・デバイス上で実行されると、前記コンピューティング・デバイスに、
メモリ・コンテナ中の或るアイテムを見出す要求をアプリケーションから受信するのに応じて、前記アイテムに対する開始メモリ・スロットを計算させ、
前記アイテムが前記開始メモリ・スロットを占めていないのに応じて、前記アイテムについて前記開始メモリ・スロットの直後の第一所定数のメモリ・スロットを探査させ、
前記アイテムが、前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの１つを占めているのに応じて、前記アイテムを前記アプリケーションに返させ、
前記アイテムが、前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの１つを占めていないのに応じて、前記第一所定数のメモリ・スロットの最後に関連付けてバリア・ビットが設定されているかどうかを判断させ、
前記バリア・ビットが設定されているのに応じて、前記アイテムについて前記メモリ・コンテナの少なくとも部分を探査させ、前記メモリ・コンテナの部分に前記アイテムが見出されたのに応じて、前記アプリケーションに前記アイテムを返させ、且つ
前記バリア・ビットが設定されていないのに応じて、前記アイテムが前記メモリ・コンテナ中に存在しないことの通知を前記アプリケーションに返させる、
コンピュータ・プログラム製品。
【請求項１２】
前記メモリ・コンテナの前記部分が前記メモリ・コンテナの全ての未探査のメモリ・スロットである、請求項１１に記載のコンピュータ・プログラム製品。
【請求項１３】
前記メモリ・コンテナの前記部分が前記開始メモリ・スロットの直後の第二所定数のメモリ・スロットであり、前記コンピュータ可読プログラムは、前記コンピューティング・デバイスにさらに、
前記アイテムが前記開始メモリ・スロットの直後の前記第二所定数のメモリ・スロットの１つを占めているのに応じて、前記アイテムを前記アプリケーションに返させ、且つ
前記アイテムが、前記開始メモリ・スロットの直後の前記第二所定数のメモリ・スロットの１つを占めていないのに応じて、前記アイテムが前記メモリ・コンテナ中に存在しないことの通知を前記アプリケーションに返させる、
請求項１１に記載のコンピュータ・プログラム製品。
【請求項１４】
前記コンピュータ可読プログラムが、前記コンピューティング・デバイスにさらに、
前記アイテムが前記開始メモリ・スロットを占めているのに応じて、前記開始メモリ・スロットからの前記アイテムを前記アプリケーションに返させる、
請求項１１に記載のコンピュータ・プログラム製品。
【請求項１５】
前記アイテムが、前記メモリ・コンテナ中の複数のメモリ・スロットの１つの中に、前記コンピューティング・デバイスにさらに、
前記アイテムを前記メモリ・コンテナ中の前記複数のメモリ・スロットの１つの中に挿入する要求を受信するのに応じて、前記アイテムに対する前記開始メモリ・スロットを計算させ、
前記開始メモリ・スロットが空であるのに応じて、前記開始メモリ・スロット中に前記アイテムを格納させ、
前記開始メモリ・スロットが占有されているのに応じて、前記アイテムついて、前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットを探査させ、
前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの１つが空であるのに応じて、前記アイテムを前記空のメモリ・スロットに格納させ、
前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの全てが占有されているのに応じて、空のメモリ・スロットについて前記メモリ・コンテナの少なくとも前記部分を探査させ、
前記空のメモリ・スロットが識別されたのに応じて、前記アイテムを前記空のメモリ・スロットに格納し、前記第一所定数のメモリ・スロットの最後に関連付けて設定された前記バリア・ビットを設定させ、
前記空のメモリ・スロットが識別できなかったのに応じて、前記アイテムを前記メモリ・コンテナ中に格納できないことの通知を前記アプリケーションに返させる、
前記コンピュータ可読プログラムによって挿入される、
請求項１１に記載のコンピュータ・プログラム製品。
【請求項１６】
前記メモリ・コンテナの前記部分が前記メモリ・コンテナの全ての未探査のメモリ・スロットである、請求項１５に記載のコンピュータ・プログラム製品。
【請求項１７】
前記メモリ・コンテナの前記部分が前記開始メモリ・スロットの直後の第二所定数のメモリ・スロットであり、前記コンピュータ可読プログラムが、前記コンピューティング・デバイスにさらに、
前記開始メモリ・スロットの直後の前記第二所定数のメモリ・スロットの１つに空のスロットを前記識別するのに応じて、前記アイテムを前記空のメモリ・スロットに格納させ、且つ
前記開始メモリ・スロットの直後の前記第二所定数のメモリ・スロットの１つに空のスロットを識別できなかったのに応じて、前記アイテムを前記メモリ・コンテナに格納できないことの通知を前記アプリケーションに返させる、
請求項１５に記載のコンピュータ・プログラム製品。
【請求項１８】
前記アイテムが、前記メモリ・コンテナ中の複数のメモリ・スロットの１つから、前記コンピューティング・デバイスにさらに、
前記メモリ・コンテナ中の或るアイテムを削除する要求を受信するのに応じて、前記アイテムに対する前記開始メモリを計算させ、
前記アイテムが前記開始メモリ・スロットを占めていないのに応じて、前記アイテムについて前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットを探査させ、
前記アイテムが、前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの１つを占めているのに応じて、前記メモリ・スロットから前記アイテムを削除させ、
前記アイテムが、前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの１つを占めていないのに応じて、前記第一所定数のメモリ・スロットの最後に関連付けて前記バリア・ビットが設定されているかどうかを判断させ、
前記バリア・ビットが設定されているのに応じて、前記アイテムについて前記メモリ・コンテナの少なくとも前記部分を探査し、前記メモリ・コンテナの前記部分に前記アイテムが見出されたのに応じて、前記メモリ・スロットから前記アイテムを削除させ、
前記バリア・ビットが設定されていないのに応じて、前記アイテムが前記メモリ・コンテナ中に存在しないことの通知を前記アプリケーションに返させる、
前記コンピュータ可読プログラムによって削除される、
請求項１１に記載のコンピュータ・プログラム製品。
【請求項１９】
前記メモリ・コンテナの前記部分が前記開始メモリ・スロットの直後の第二所定数のメモリ・スロットであり、前記コンピュータ可読プログラムが、前記コンピューティング・デバイスにさらに、
前記アイテムが、前記開始メモリ・スロットの直後の前記第二所定数のメモリ・スロットの１つを占めているのに応じて、前記アイテムを前記メモリ・スロットから削除させ、且つ
前記アイテムが、前記開始メモリ・スロットの直後の前記第二所定数のメモリ・スロットの１つを占めていないのに応じて、前記アイテムが前記メモリ・コンテナ中に存在しないことの通知を前記アプリケーションに返させる、
請求項１８に記載のコンピュータ・プログラム製品。
【請求項２０】
プロセッサと、
前記プロセッサに連結されたメモリであって、前記メモリは、前記プロセッサによって実行されると前記プロセッサに、
前記メモリ・コンテナ中の或るアイテムを見出す要求をアプリケーションから受信するのに応じて、前記アイテムに対する開始メモリ・スロットを計算させ、
前記アイテムが前記開始メモリ・スロットを占めていないのに応じて、前記アイテムについて前記開始メモリ・スロットの直後の第一所定数のメモリ・スロットを探査させ、
前記アイテムが、前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの１つを占めているのに応じて、前記アイテムを前記アプリケーションに返させ、
前記アイテムが、前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの１つを占めていないのに応じて、前記第一所定数のメモリ・スロットの最後に関連付けてバリア・ビットが設定されているかどうかを判断させ、
前記バリア・ビットが設定されているのに応じて、前記アイテムについて前記メモリ・コンテナの少なくとも部分を探査し、前記メモリ・コンテナの前記部分に前記アイテムが見出されたのに応じて、前記アプリケーションに前記アイテムを返させ、且つ
前記バリア・ビットが設定されていないのに応じて、前記アイテムが前記メモリ・コンテナ中に存在しないことの通知を前記アプリケーションに返させる、
命令を含む、前記メモリと、
を含む装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、一般に改良されたデータ処理装置および方法に関し、さらに具体的には開アドレス法探査バリアのためのメカニズムに関する。
【背景技術】
【０００２】
キー・バリュー・ストア、またはキー・バリュー・データベースは、連想配列を格納し、読み出し、および管理するために設計されたデータ・ストレージ・パラダイムであり、そのデータ構造は、ディクショナリまたはハッシュ・テーブルとしてより一般的に知られている。ディクショナリ、ハッシュ・テーブルまたは同種のものは、オブジェクト、レコードなどのコレクションを含み、そして、これは、それぞれがデータを包含する様々なフィールドを有する。これらのレコードは、レコードを一意的に識別しデータ構造体内のデータを迅速に見出すために使用されるハッシュベースのキーを用いて格納され、読み出される。
【０００３】
キー・バリュー・ストアは、より周知されている関係データベース（ＲＤＢ：ｒｅｌａｔｉｏｎａｌ  ｄａｔａｂａｓｅ）とは極めて異なる仕方で機能する。ＲＤＢは、データベース中のデータ構造を、明確に定義されたデータ型を備えるフィールドを含む一連のテーブルとして事前定義する。データベース・プログラムに対しデータ型を顕在化することによって、該プログラムがいくつかの最適化を適用することを可能にする。これに対し、キー・バリュー・ストアは、データを、各々のレコードに対し異なるフィールドを有することが可能な、単一の不透明なコレクションとして取り扱う。これは、かなりの柔軟性を提供し、オブジェクト指向プログラミングのような近代的概念により密接に従う。任意の値が、ほとんどのＲＤＢのようにはプレースホルダによって代表されていないので、キー・バリュー・ストアは、多くの場合、同じデータベースを格納するのにはるかに少ないメモリを用い、或る種の作業負荷においては大きなパフォーマンス利得をもたらすことができる。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明は、ハッシュベースのキー・バリュー格納メカニズムにおける各種ハッシュ・アルゴリズムに関連して、パフォーマンスおよび収容能力利用度の両方に有益な開アドレス法探査バリアを提供する。
【課題を解決するための手段】
【０００５】
以下の要約は、本明細書中の、発明を実装するための形態においてさらに説明される概念の抜粋を簡易化した形で紹介するために提供される。本要約は、特許請求の主題の主要素または本質的特徴を識別することは意図されておらず、特許請求の主題の範囲を限定するために用いることも意図されていない。
【０００６】
一例示的な実施形態において、データ処理システムにおいて、メモリ・コンテナと関連して開アドレス法探査バリアを利用するための方法が提供される。本例示的な実施形態は、メモリ・コンテナ中の或るアイテムを見出す要求をアプリケーションから受信するのに応じて、そのアイテムに対する開始メモリ・スロットを計算する。本例示的な実施形態は、当該アイテムが開始メモリ・スロットを占めていないのに応じて、該アイテムについて、開始メモリ・スロットの直後の第一所定数のメモリ・スロットを探査する。本例示的な実施形態は、当該アイテムが、開始メモリ・スロットの直後の第一所定数のメモリ・スロットの１つを占めているのに応じて、そのアイテムをアプリケーションに返す。本例示的な実施形態は、当該アイテムが、開始メモリ・スロットの直後の第一所定数のメモリ・スロットの１つを占めていないのに応じて、第一所定数のメモリ・スロットの最後に関連付けてバリア・ビットが設定されているかどうかを判断する。本例示的な実施形態は、バリア・ビットが設定されているのに応じて、当該アイテムについてメモリ・コンテナの少なくとも部分を探査し、メモリ・コンテナのその部分にアイテムが見出されたのに応じて、そのアイテムをアプリケーションに返す。本例示的な実施形態は、バリア・ビットが設定されていないのに応じて、当該アイテムがメモリ・コンテナ中に存在しないことの通知をアプリケーションに返す。
【０００７】
他の例示的な実施形態において、コンピュータ可読プログラムを有するコンピュータ可用または可読媒体を含むコンピュータ・プログラム製品が提供される。本コンピュータ可読プログラムは、コンピューティング・デバイス上で実行されると、そのコンピューティング・デバイスに、方法の例示的な実施形態に関して上記で略述したオペレーションの各種またはそれらの組み合せを実行させる。
【０００８】
さらに別の例示的な実施形態において、システム／装置が提供される。本システム／装置は、１つ以上のプロセッサ、および該１つ以上のプロセッサに連結されたメモリを含んでよい。このメモリは、該１つ以上のプロセッサによって実行されると、その１つ以上のプロセッサに方法の例示的な実施形態に関して上記で略述したオペレーションの各種またはそれらの組み合せを実行させる命令、を含むことができる。
【０００９】
一態様によれば、データ処理システムにおいて、メモリ・コンテナに関連して開アドレス探査バリアを用いる方法が提供され、本方法は、メモリ・コンテナ中の或るアイテムを見出す要求をアプリケーションから受信するのに応じて、そのアイテムに対する開始メモリ・スロットを計算するステップと、当該アイテムが開始メモリ・スロットを占めていないのに応じて、該アイテムについて、開始メモリ・スロットの直後の第一所定数のメモリ・スロットを探査するステップと、当該アイテムが、開始メモリ・スロットの直後の第一所定数のメモリ・スロットの１つを占めているのに応じて、そのアイテムをアプリケーションに返すステップと、当該アイテムが、開始メモリ・スロットの直後の第一所定数のメモリ・スロットの１つを占めていないのに応じて、第一所定数のメモリ・スロットの最後に関連させてバリア・ビットが設定されているかどうかを判断するステップと、バリア・ビットが設定されているのに応じて、当該アイテムについてメモリ・コンテナの少なくとも部分を探査し、メモリ・コンテナのその部分にアイテムが見出されたのに応じて、そのアイテムをアプリケーションに返すステップと、バリア・ビットが設定されていないのに応じて、当該アイテムがメモリ・コンテナ中に存在しないことの通知をアプリケーションに返すステップと、を含む。
【００１０】
別の態様によれば、中に格納されたコンピュータ可読プログラムを有するコンピュータ可読ストレージ媒体を含むコンピュータ・プログラム製品が提供され、該コンピュータ可読プログラムは、コンピューティング・デバイス上で実行されると、そのコンピューティング・デバイスに、メモリ・コンテナ中の或るアイテムを見出す要求をアプリケーションから受信するのに応じて、そのアイテムに対する開始メモリ・スロットを計算させ、当該アイテムが開始メモリ・スロットを占めていないのに応じて、該アイテムについて、開始メモリ・スロットの直後の第一所定数のメモリ・スロットを探査させ、当該アイテムが、開始メモリ・スロットの直後の第一所定数のメモリ・スロットの１つを占めているのに応じて、そのアイテムをアプリケーションに返させ、当該アイテムが、開始メモリ・スロットの直後の第一所定数のメモリ・スロットの１つを占めていないのに応じて、第一所定数のメモリ・スロットの最後に関連付けてバリア・ビットが設定されているかどうかを判断させ、バリア・ビットが設定されているのに応じて、当該アイテムについてメモリ・コンテナの少なくとも部分を探査させ、且つ、メモリ・コンテナのその部分にアイテムが見出されたのに応じて、アプリケーションにそのアイテムを返させる。
【００１１】
別の態様によれば、プロセッサ、および該プロセッサに連結されたメモリを含む装置が提供され、このメモリは命令群を含み、これら命令は、プロセッサに実行されると、該プロセッサに、メモリ・コンテナ中の或るアイテムを見出す要求をアプリケーションから受信するのに応じて、そのアイテムに対する開始メモリ・スロットを計算させ、当該アイテムが開始メモリ・スロットを占めていないのに応じて、該アイテムについて開始メモリ・スロットの直後の第一所定数のメモリ・スロットを探査させ、当該アイテムが、開始メモリ・スロットの直後の第一所定数のメモリ・スロットの１つを占めているのに応じて、そのアイテムをアプリケーションに返させ、当該アイテムが、開始メモリ・スロットの直後の第一所定数のメモリ・スロットの１つを占めていないのに応じて、第一所定数のメモリ・スロットの最後に関連させてバリア・ビットが設定されているかどうかを判断させ、バリア・ビットが設定されているのに応じて、当該アイテムについてメモリ・コンテナの少なくとも部分を探査させ、メモリ・コンテナのその部分にアイテムが見出されたのに応じて、そのアイテムをアプリケーションに返させ、且つ、バリア・ビットが設定されていないのに応じて、当該アイテムがメモリ・コンテナ中に存在しないことの通知をアプリケーションに返させる。
【００１２】
本発明のこれらのおよび他の特徴および利点は、以降の本発明の例示の諸実施形態の詳細な説明で述べることとし、これらの説明を考慮することにより当業者に明らかとなろう。
【００１３】
以降において、本発明の好適な諸実施形態を、単に例示のために、以下の図面を参照しながら説明することとする。
【図面の簡単な説明】
【００１４】
【図１】例示的な実施形態の諸態様が実装可能なコンピューティング・デバイスの例示のブロック図である。
【図２】或る例示的な実施形態による、開アドレス法探査バリア・スキームを実装したメカニズムの機能ブロック図を表す。
【図３】或る例示的な実施形態による、メモリ・コンテナ中のアイテム群の物理ストレージの論理的表現を表す。
【図４】或る例示的な実施形態による、走査バリアを使わない探査と走査バリアを使った探査とに対する、検索時間（ナノ秒単位）対使用率のグラフを表す。
【図５】或る例示的な実施形態による、開アドレス法探査バリア・メカニズムによって行われる挿入オペレーションの典型的な流れ図を表す。
【図６】或る例示的な実施形態による、開アドレス法探査バリア・メカニズムによって行われる検索オペレーションの典型的な流れ図を表す。
【図７】或る例示的な実施形態による、開アドレス法探査バリア・メカニズムによって行われる削除オペレーションの典型的な流れ図を表す。
【発明を実施するための形態】
【００１５】
これら例示的な諸実施形態は、開アドレス法探査バリアのためのメカニズムを提供する。前に述べたように、キー・バリュー・ストア、またはキー・バリュー・データベースは、連想配列を格納し、読み出し、および管理するために設計されたデータ・ストレージ・パラダイムであり、そのデータ構造は、ディクショナリまたはハッシュ・テーブルとしてより一般的に知られている。ディクショナリ、ハッシュ・テーブルまたは同種のものは、アイテム、オブジェクト、レコードまたは同種のもののコレクションを含み、それらは、その中にそれぞれがデータを含む様々なフィールドを有する。アイテムは、レコードを一意的に識別しデータ構造体内のデータを迅速に見出すために使用されるハッシュベースのキーを用いて格納され、読み出される。
【００１６】
しかしながら、ハッシュベースのキー・バリュー・ストアでは、衝突を解決するメカニズムが要求される。衝突は、ハッシュ・アルゴリズムがキー・バリュー・ストア中の同じ場所に複数のアイテムをマップしたときに生ずる。衝突解決の１つの現今のやり方はチェイニングである。チェイニングは、複数のアイテムを包含するため、データ構造中に特定の場所、バケット、スロットなどを割り当てる。チェイニングは極めて一般的な解決法であるが、チェイニングは、特に小アイテムの場合に不利益がある。このデータ構造中のスロットの深さは変わり得るので、通常、動的なメモリ割り当てが用いられる。しかしながら、メモリ割り当てはパフォーマンスに不利な条件を伴い、リアルタイム・システムなどにおいては必ずしも可能ではない。加えて、チェイニングは、メモリのオーバーヘッドをもたらす。例えば、次のアイテムへの単一のポインタが８バイトのオーバーヘッドであり、アイテムのサイズが小さい場合にこれはかなりのものとなり得る。
【００１７】
衝突解決の別の現今のやり方は開アドレス法である。挿入時に当該スロットが既に使われている場合、新規または既存のアイテムは、別のスロットに配置されることになる。どの別のスロットを使用するか、どのようにアイテムの検索を行うかを定義するため一組のルールが必要となる。開アドレス法には、チェイニングと同種の不利益はなく、また、良好なキャッシュ・ライニングを有する。
しかしながら、開アドレス法にも、
・  全てのスロットを利用することはできない。すなわち、効率的に実行するには、データ構造体が７０％〜８０％の利用率に達したときサイズ変更が必要となる、
・  実装の如何によっては、挿入もしくは検索に多くのステップが必要となり得る、
などの欠点がある。
【００１８】
開アドレス法でのハッシュ・テーブルの使用は、多くの既存研究のある成熟分野である。以下のリストは、開アドレス法ハッシュ・アルゴリズムのいくつかの関連する例である。
・  線形探査  −当該スロットが使われている場合、空のスロットが見つかるまで次のスロット（間隔は１より大きくてもよい）に移動する。線形探査は実装が極めて単純で、良好なキャッシュ・ヒット率を有するが、利用度が高い場合は挿入および検索両方が高コストになり得る。
・  カッコー・ハッシュ法  −各エントリを２つの見込みスロットにマップするため２つのハッシュ関数を使用する。両方のスロットが使用されている場合、既存のエントリは別のスロットに移動される。このアルゴリズムは検索が極めて効率的であるが、挿入は、利用度が高いと高コストである。カッコー・ハッシュ法の別の不利点は、挿入の都度、イテレータが無効になることである。
開アドレス法で使われているさらなるハッシュ・アルゴリズムがあり、そのいくつかは、線形探査およびカッコー・ハッシュ法の概念の混成である。
【００１９】
本例示的な諸実施形態は、ハッシュベースのキー・バリュー格納メカニズムにおける各種ハッシュ・アルゴリズムに関連して、パフォーマンスおよび収容能力利用度の両方に有益な開アドレス法探査バリアを提供する。提案される開アドレス法探査バリアは、任意の種類のハッシュベースのキー・バリュー格納メカニズムに実装が可能であるが、以下では、網羅的であることまたは本発明を開示された形態に限定することを意図せずに、１つの例として、線形探査アルゴリズムに関連させて開アドレス法探査バリアを説明する。本例示的な諸実施形態において、ユーザ設定が可能な定数である探査バリアＮは、或る特定のアイテムに対する探査プロセスを限定する。Ｎは、コンテナの収容能力およびパフォーマンスに基づいて選択される。例えば、探査プロセス（すなわち、検索オペレーション）がスロットＳｉにある場合、例えば、探査バリアＮが３であるとすれば、この探査プロセスは、所望のアイテムが識別されるまで、または見出せないまま、スロットＳｉおよび後続の３つのスロットを走査することになる。４番目のスロットに到達しても所望のアイテムが見つからなければ、その探査プロセスは終了する。
【００２０】
また一方、一例示的な実施形態において、走査バリア・ビットが設定されている場合、探査バリアは突破されてもよい。走査バリアは、探査免除バリアとして機能する、開アドレス法ハッシュ・テーブルのエントリに付加された単一ビットである。すなわち、アイテムの当初の挿入において、探査バリアＮが突破された場合、つまり、当該アイテムがハッシュされた開始スロットから探査バリアＮを通り過ぎたスロット中に挿入された場合、走査バリアはＳｉ＋（Ｎ−１）に設定される。しかして、或るアイテムの探査において、所望のアイテムを見出せずに４番目のスロットに到達し、走査バリア・ビットが設定されていない場合、探査プロセスは終了する。すなわち、前に挿入されていたアイテムは決して探査バリアを越えることはなく、したがって探査は停止する。また一方、或るアイテムの探査において、所望のアイテムを見出せずに４番目のスロットに到達し、走査バリア・ビットが設定されている場合、探査は、空のスロットに到達するか、または全スロットが探査完了するまで続行される。
【００２１】
別の例示的な実施形態において、拡張探査すなわちアイテムが見出せず且つ走査バリア・ビットが設定されているときの探査は、例えば、Ｎの倍数、例えば２Ｎ、３Ｎ、４ＮなどＮより大きな任意の数の拡張探査バリア、例として、探査バリアはＮに等しく拡張探査バリアはＮ＋Ｍに等しい拡張探査バリアを使って、あるいは、探査バリアＮより大きな拡張探査バリアを有する任意の他の方法を使ってキャンセルすることが可能である。以下の例は、２Ｎの拡張探査バリアを用いている。前述の実施形態において、Ｓｉ＋Ｎに到達し、走査バリア・ビットが設定されている場合、探査は、空のスロットに到達するまで、または全スロットが探査完了するまで続行される。この実施形態において、Ｓｉ＋Ｎに到達し、探査バリア・ビットが設定されている場合、探査は、パフォーマンスおよび収容能力をより向上するため、空のスロットに到達するか、またはＳｉ＋２Ｎに到達するときまでだけ続行される。両方の実施形態において、空のスロットに到達した場合、または全スロットが探査完了した場合（第一実施形態）、またはＳｉ＋２Ｎのスロットが探査完了した場合（第二実施形態）、不在であることが返される。所望のアイテムが見出された場合は、そのアイテムが返される。これら例示的な実施形態は、２つの探査バリアだけを例示しているが、本例示的な所実施形態はこれらの実施形態だけに限定されない。すなわち、２より多い探査バリアがあってよく、探査バリアの間の間隔が線形である必要はない。
【００２２】
本例示的な諸実施形態の様々な態様の説明を始める前に、まず、本説明を通貫して、様々なオペレーション、機能などを実行する本発明の要素を言及するために、用語「メカニズム」が用いられることをよく理解しておく必要がある。本明細書で用いられる用語「メカニズム」は、装置、手順、またはコンピュータ・プログラム製品の形での、例示的な諸実施形態の機能または態様の実装であり得る。手順の場合、その手順は、１つ以上のデバイス、装置、コンピュータ、データ処理システムなどによって実装される。コンピュータ・プログラム製品の場合、そのコンピュータ・プログラム製品中／上に具現化されたコンピュータ・コードまたは命令によって表されるロジックは、特定の「メカニズム」に関連する機能を実装するためまたはオペレーションを実行するために、１つ以上のハードウェア・デバイスによって実行される。しかして、本明細書で説明するメカニズムは、特殊化されたハードウェア、汎用ハードウェア上で実行されるソフトウェア、特殊化されたもしくは汎用のハードウェアによって容易に実行可能なように媒体上に格納されたソフトウェア命令、諸機能を実行するための手順もしくは方法、または上記のいずれかの組み合せとして実装されてよい。
【００２３】
本明細書および特許請求の範囲において、例示的な諸実施形態の特定の機能および要素に関し、語句「或る（ａ）」、「の少なくとも１つ」および「の１つ以上」が使用されることがある。当然のことながら、これらの用語および成句は、特定の例示的な実施形態中に、それら特定の機能または要素の少なくとも１つがあるが、１より多くも存在し得ることを述べることを意図されている。すなわち、これらの用語／成句は、本明細書または特許請求の範囲を単一の機能／要素の存在に限定したり、または複数のかかる機能／要素の存在を必要とすることを意図されていはいない。反対に、これらの用語／成句は、本明細書および特許請求項の範囲内に複数の機能／要素がある可能性とともに、少なくとも単一のかかる機能／要素を要求しているだけである。
【００２４】
さらに、本発明の実施形態および特徴の説明に関し、用語「エンジン」の使用は、本明細書で用いられる場合、アクション、ステップ、プロセスなどを達成するもしくは実行するまたはその両方を行うため、エンジンに起因してもしくはエンジンによって行われるまたはその両方の何らかの特定の実行に限定することは意図されていないことをよく理解すべきである。エンジンは、以下に限らないが、マシン可読のメモリ中にロード、格納され、プロセッサによって実行される適切なソフトウェアと組み合された、汎用もしくは特殊プロセッサまたはその両方の任意の使用を含む、特定の機能を実行するソフトウェア、ハードウェア、もしくはファームウェア、またはこれらの任意の組み合せであってよい。さらに、特定のエンジンに関連する一切の名称は、別途に指定されている場合を除き、参照の便宜のためのものであり、特定の実装に限定することは意図されていない。加えて、或るエンジンに帰する一切の機能は、同じまたは異なる種類の別のエンジンの機能の中に組み込まれたもしくは組み合されたまたはその両方による、複数のエンジンによって同様に実行可能であり、あるいは様々な構成の１つ以上のエンジンに亘って分散することが可能である。
【００２５】
さらに、以降の説明において、本例示的な諸実施形態の実装例をさらに示しこれら例示的な諸実施形態のメカニズムの理解を助力するために、これら例示的な諸実施形態の様々な要素に対する複数の様々な例が用いられることをよく理解すべきである。これらの例は、非限定であり、例示的な諸実施形態のメカニズムを実装するための様々な可能性を網羅するものでないことが意図されている。当業者には、本発明の趣旨および範囲から逸脱することなく、本説明を考慮に入れて、本明細書に提示された諸例に加えまたはそれらの替わりに使用が可能な、これら様々な要素に対する、多くの他の代替の実装があり得ることが明らかであろう。
【００２６】
しかして、本例示的な諸実施形態は、多く様々な種類のデータ処理環境において活用が可能である。本例示的な諸実施形態の具体的な要素および機能の説明についてのコンテキストを提供するために、これら例示的な諸実施形態または諸態様が実装可能な環境の例として、以下に図１を提示する。当然のことながら、図１は単なる例であって、本発明の諸態様または諸実施形態が実装可能な環境に関していかなる限定をも主張または暗示することは意図されていない。本発明の趣旨および範囲から逸脱することなく、図示の環境に多くの修改を加えることが可能である。
【００２７】
図１に示されるように、これらコンピューティング・デバイスの１つ以上は、開アドレス法探査バリアを実装するように特化して構成することができる。このコンピューティング・デバイスの構成は、本例示的な諸実施形態に関連して本明細書で説明するオペレーションの実行、およびアウトプットの生成を促進するための、特定用途向けハードウェア、ファームウェアなどを用意することを含んでよい。このコンピューティング・デバイスの構成は、該構成に加えてまたはそれに換えて、コンピューティング・デバイスの１つ以上のハードウェア・プロセッサに、それらプロセッサが本例示的な諸実施形態に関連して本明細書で説明されたオペレーションを実行しアウトプットを生成するように構成されたソフトウェア・アプリケーションを実行させるため、１つ以上のストレージ・デバイス中に格納され、コンピューティング・デバイスのメモリ中にロードされるソフトウェア・アプリケーションを用意することも含んでよい。さらに、本例示的な諸実施形態の趣旨および範囲から逸脱することなく、特定用途向けハードウェア、ファームウェア、ハードウェア上で実行されるソフトウェア・アプリケーションなどの任意の組み合せを用いることが可能である。
【００２８】
コンピューティング・デバイスがこれらのうちの１つの仕方で構成されたならば、そのコンピューティング・デバイスは、本例示的な諸実施形態のメカニズムを実装するよう特化して構成された特化コンピューティング・デバイスとなり、汎用コンピューティング・デバイスではないことをよく理解すべきである。さらに、後記で説明するように、本例示的な諸実施形態のメカニズムの実装は、コンピューティング・デバイスの機能を改良し、開アドレス法探査バリアを促進する有用で具体的な結果を提供する。
【００２９】
本例示的な諸実施形態のメカニズムは、開アドレス法探査バリアのためのオペレーションを行うために、特化して構成されたコンピューティング・デバイス、またはデータ処理システムを用いる。これらのコンピューティング・デバイスまたはデータ処理システムは、本明細書で説明するシステム／サブシステムの１つ以上を実装するために、ハードウェア構成、ソフトウェア構成、またはハードウェア構成とソフトウェア構成との組み合せのいずれかを介し特化して構成された様々なハードウェア要素を含んでよい。図１は、本例示的な諸実施形態の諸態様が実装可能なデータ処理システムの単なる一例のブロック図である。データ処理システム１００は、本明細書で説明する例示的な諸実施形態のオペレーション、アウトプット、および外部効果を達成するために、本発明の例示的な諸実施形態のプロセスおよび態様を実装するコンピュータ可用コードまたは命令が、配置できもしくは実行できまたはその両方ができるコンピュータの一例である。
【００３０】
図示された例において、データ処理システム１００は、ノース・ブリッジおよびメモリ・コントローラ・ハブ（ＮＢ／ＭＣＨ：ｎｏｒｔｈ  ｂｒｉｄｇｅ  ａｎｄ  ｍｅｍｏｒｙ  ｃｏｎｔｒｏｌｌｅｒ  ｈｕｂ）１０２と、サウス・ブリッジおよび入力／出力（Ｉ／Ｏ：ｉｎｐｕｔ／ｏｕｔｐｕｔ）コントローラ・ハブ（ＳＢ／ＩＣＨ：ｓｏｕｔｈ  ｂｒｉｄｇｅ  ａｎｄ  ｉｎｐｕｔ／ｏｕｔｐｕｔ  ｃｏｎｔｒｏｌｌｅｒ  ｈｕｂ）１０４とを含むハブ・アーキテクチャを用いている。処理装置１０６、主メモリ１０８、およびグラフィック・プロセッサ１１０は、ＮＢ／ＭＣＨ１０２に連結されている。グラフィック・プロセッサ１１０は、アクセラレイティッド・グラフィックス・ポート（ＡＧＰ：ａｃｃｅｌｅｒａｔｅｄ  ｇｒａｐｈｉｃｓ  ｐｏｒｔ）を介してＮＢ／ＭＣＨ１０２に連結されている。
【００３１】
この図示の例において、ローカル・エリア・ネットワーク（ＬＡＮ：ｌｏｃａｌ  ａｒｅａ  ｎｅｔｗｏｒｋ）アダプタ１１２はＳＢ／ＩＣＨ１０４に連結している。オーディオ・アダプタ１１６、キーボードおよびマウス・アダプタ１２０、モデム１２２、読み取り専用メモリ（ＲＯＭ：ｒｅａｄ  ｏｎｌｙ  ｍｅｍｏｒｙ）１２４、ハード・ディスク・ドライブ（ＨＤＤ：ｈａｒｄ  ｄｉｓｋ  ｄｒｉｖｅ）１２６、ＣＤ−ＲＯＭドライブ１３０、ユニバーサル・シリアル・バス（ＵＳＢ：ｕｎｉｖｅｒｓａｌ  ｓｅｒｉａｌ  ｂｕｓ）および他の通信ポート１３２、およびＰＣＩ／ＰＣＩｅデバイス１３４は、バス１３８およびバス１４０を介してＳＢ／ＩＣＨ１０４に連結している。ＰＣＩ／ＰＣＩｅデバイスは、例えば、イーサネット（登録商標）アダプタ、アドイン・カード、およびノート型コンピュータ用のＰＣカードを含むことが可能である。ＰＣＩは、カード・バス・コントローラを使うが、ＰＣＩｅは使わない。ＲＯＭ１２４は、例えば、フラッシュ基本入出力システム（ＢＩＯＳ：ｂａｓｉｃ  ｉｎｐｕｔ／ｏｕｔｐｕｔ  ｓｙｓｔｅｍ）であってよい。
【００３２】
ＨＤＤ１２６およびＣＤ−ＲＯＭドライブ１３０は、バス１４０を介してＳＢ／ＩＣＨ１０４に連結している。ＨＤＤ１２６およびＣＤ−ＲＯＭドライブ１３０は、例えば、統合ドライブ・エレクトロニクス（ＩＤＥ：ｉｎｔｅｇｒａｔｅｄ  ｄｒｉｖｅ  ｅｌｅｃｔｒｏｎｉｃｓ）またはシリアル・アドバンスド・テクノロジー・アタッチメント（ＳＡＴＡ：ｓｅｒｉａｌ  ａｄｖａｎｃｅｄ  ｔｅｃｈｎｏｌｏｇｙ  ａｔｔａｃｈｍｅｎｔ）インターフェースを使ってよい。ＳＢ／ＩＣＨ１０４に、スーパーＩ／Ｏ（ＳＩＯ：Ｓｕｐｅｒ  Ｉ／Ｏ）デバイス１３６を連結することが可能である。
【００３３】
オペレーティング・システムは処理装置１０６上で実行される。このオペレーティング・システムは、図１中のデータ処理システム１００内の様々なコンポーネントを調整し、それらの制御を提供する。クライアントとしては、このオペレーティング・システムはマイクロソフト（登録商標）のＷｉｎｄｏｗｓ７（登録商標）など市販のオペレーティング・システムであってよい。このオペレーティング・システムと合わせてＪａｖａ（登録商標）プログラミング・システムなどのオブジェクト指向プログラミング・システムを実行することが可能で、これは、データ処理システム１００上で実行されるＪａｖａ（登録商標）プログラムまたはアプリケーションからオペレーティング・システムへのコールを提供する。
【００３４】
サーバとしては、データ処理システム１００は、例えば、アドバンスト・インタラクティブエグゼクティブ（ＡＩＸ：Ａｄｖａｎｃｅｄ  Ｉｎｔｅｒａｃｔｉｖｅ  Ｅｘｅｃｕｔｉｖｅ）（ＩＢＭ社の登録商標）オペレーティング・システム、またはＬＩＮＵＸ（登録商標）オペレーティング・システムを実行する、ＩＢＭのｅＳｅｒｖｅｒ（ＩＢＭ社の登録商標）Ｓｙｓｔｅｍ  ｐコンピュータ・システム、Ｐｏｗｅｒ（ＩＢＭ社の登録商標）プロセッサ・ベースのコンピュータ・システムなどであってよい。データ処理システム１００は、処理装置１０６中に複数のプロセッサを含む、対称マルチプロセッサ（ＳＭＰ：ｓｙｍｍｅｔｒｉｃ  ｍｕｌｔｉｐｒｏｃｅｓｓｏｒ）システムとすることが可能である。あるいは、単一プロセッサ・システムを用いてもよい。
【００３５】
Ｌｉｎｕｘは、米国、他の国々またはその両方におけるＬｉｎｕｓ  Ｔｏｒｖａｌｄｓ社の登録商標である。マイクロソフト、Ｗｉｎｄｏｗｓ、ＷｉｎｄｏｗｓＮＴ、およびＷｉｎｄｏｗｓのロゴは、米国、他の国々またはその両方におけるＭｉｃｒｏｓｏｆｔ  Ｃｏｒｐｏｒａｔｉｏｎ社の登録商標である。ＪａｖａおよびＪａｖａベースの商標およびロゴは、Ｏｒａｃｌｅ社もしくはその関係会社またはその両方の商標または登録商標である。ＩＢＭ、ｅＳｅｒｖｅｒ、Ｐｏｗｅｒ、およびＡＩＸは、米国、他の国々またはその両方におけるＩｎｔｅｒｎａｔｉｏｎａｌ  Ｂｕｓｉｎｅｓｓ  Ｍａｃｈｉｎｅｓ  Ｃｏｒｐｏｒａｔｉｏｎ社の登録商標である。
【００３６】
オペレーティング・システム、オブジェクト指向プログラミング・システム、およびアプリケーションまたはプログラムのための命令は、ＨＤＤ１２６などのストレージ・デバイスに配置され、処理装置１０６による実行のため主メモリ１０８中にロードすることが可能である。本発明の例示的な諸実施形態のためのプロセスは、コンピュータ可用のプログラム・コードを用い、処理装置１０６によって実行することができ、これらプログラムは、例えば、主メモリ１０８、ＲＯＭ１２４、または例えば１つ以上の周辺デバイス１２６および１３０などのメモリ中に配置することが可能である。
【００３７】
図１に示されたバス１３８またはバス１４０などのバス・システムは、１つ以上のバスで構成されてよい。当然ながら、バス・システムは、ファブリックまたはアーキテクチャに付随する各種のコンポーネントまたはデバイスの間でのデータの伝送を提供する任意の種類の通信ファブリックまたはアーキテクチャを用いて実装することが可能である。図１のモデム１２２またはネットワーク・アダプタ１１２などの通信ユニットは、データを送信および受信するために使われる１つ以上のデバイスを含んでよい。メモリは、例えば、図１中の主メモリ１０８、ＲＯＭ１２４、またはＮＢ／ＭＣＨ１０２中に見られるようなキャッシュであってよい。
【００３８】
前述したように、いくつかの例示的な諸実施形態において、本例示的な諸実施形態のメカニズムは、特定用途向けハードウェア、ファームウェアなど、または、ＨＤＤ１２６などのストレージ・デバイス中に格納され、処理装置１０６などの１つ以上のハードウェア・プロセッサによる実行のため主メモリ１０８などのメモリ中にロードされるアプリケーション・ソフトウェアとして実装することが可能である。しかして、図１に示されたコンピューティング・デバイスは、本例示的な諸実施形態のメカニズムを実装するよう特化して構成され、開アドレス法探査バリアに関連するオペレーションを実行し、後記で説明するアウトプットを生成するように特化して構成される。
【００３９】
当業者は、図１中のハードウェアが実装の如何によって変わり得ることをよく理解していよう。図１に示されたハードウェアに加えてまたはそれらに換えて、フラッシュ・メモリ、同等な不揮発性メモリ、または光ディスク・ドライブなど、他の内部ハードウェアまたは周辺デバイスを使用することが可能である。また、本例示的な諸実施形態の諸プロセスは、本発明の趣旨および範囲から逸脱することなく、前述したＳＭＰシステム以外のマルチプロセッサ・データ処理システムに適用することができる。
【００４０】
さらに、データ処理システム１００は、クライアント・コンピューティングシステム、サーバ・コンピューティングシステム、タブレット・コンピュータ、ラップトップ・コンピュータ、電話または他の通信デバイス、携帯端末情報（ＰＤＡ：ｐｅｒｓｏｎａｌ  ｄｉｇｉｔａｌ  ａｓｓｉｓｔａｎｔ）などを含め、多くの様々なデータ処理システムの任意の形を取ることが可能である。いくつかの用例において、データ処理システム１００は、例えば、オペレーティング・システム・ファイルもしくはユーザ生成のデータまたはその両方を格納するための不揮発性メモリを提供するフラッシュ・メモリを使って構成された携帯型コンピューティング・デバイスであってよい。基本的には、データ処理システム１００は、アーキテクチャの限定なしに、任意の既知のまたは将来開発されるデータ処理システムとすることができる。
【００４１】
図２は、或る例示的な実施形態による、開アドレス法探査バリア・スキームを実装したメカニズムの機能ブロック図を表す。図１中のデータ処理システム１００などのデータ処理システムとすることが可能なデータ処理システム２００は、ランダム・アクセス・メモリ（ＲＡＭ：ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）、読み取り専用メモリ（ＲＯＭ）、消去およびプログラム可能読み取り専用メモリ（ＥＰＲＯＭ：ｅｒａｓａｂｌｅ  ｐｒｏｇｒａｍｍａｂｌｅ  ｒｅａｄ−ｏｎｌｙ  ｍｅｍｏｒｙまたはフラッシュ・メモリ）などのメモリ２０４内の複数のメモリ・コンテナ２０６を制御するメモリ・コントローラ２０２を含む。各メモリ・コンテナ２０６は複数のメモリ・スロット２０８を含み、各メモリ・スロット２０８は、次の３つの状態のうちの１つを有する。
・  使用／占有  −現在、或るアイテムがメモリ・スロット２０８を占めている。
・  空  −メモリ・スロット２０８に今までにアイテムが配置されたことがない。
・  削除済み  −過去にメモリ・スロット２０８中にアイテムがあったが、そのアイテムはメモリ・スロット２０８から削除され、メモリ・スロット２０８は、現在新規のアイテムのため使用が可能である。
【００４２】
メモリ・コンテナ２０６が最初に初期化されたときには、メモリ・コンテナ２０６中の全メモリ・スロット２０８は空である。しかして、各メモリ・スロット２０８について考慮するべき３つの基本オペレーション、挿入（書込み）、検索（読み取り）および削除がある。開アドレス法探査バリア・スキームに関連して、これらオペレーションのそれぞれについて以下に説明する。挿入オペレーションに関し、図３を参照すると、本図は、或る例示的な実施形態による、メモリ・コンテナ２０６中のアイテム群の物理ストレージの論理的表現であり、挿入オペレーションにおいて、メモリ・コントローラ２０２は、アイテムを挿入するための開始メモリ・スロットを計算するハッシュ・メカニズム２１０を実行する。例えば、アイテムＡに対し、ハッシュ・メカニズム２１０が開始スロット１を計算し、メモリ・コントローラ２０２が、或るアイテムが既にメモリ・スロット１を占めているかどうかを判断するためメモリ・スロット１を探査する。メモリ・スロット１を既に占めているアイテムがなければ、メモリ・コントローラ２０２は、アイテムＡをメモリ・スロット１中に挿入する。本例を続けると、アイテムＢに対し、ハッシュ・メカニズム２１０が開始スロット６を計算し、メモリ・コントローラ２０２が、或るアイテムが既にメモリ・スロット６を占めているかどうかを判断するためメモリ・スロット６を探査する。メモリ・スロット６を既に占めているアイテムがなければ、メモリ・コントローラ２０２は、アイテムＢをメモリ・スロット６中に挿入する。アイテムＣに対し、ハッシュ・メカニズム２１０が開始スロット３を計算し、メモリ・コントローラ２０２が、或るアイテムが既にメモリ・スロット３を占めているかどうかを判断するためメモリ・スロット３を探査する。メモリ・スロット３を既に占めているアイテムがなければ、メモリ・コントローラ２０２は、アイテムＣをメモリ・スロット３中に挿入する。アイテムＤに対し、ハッシュ・メカニズム２１０が開始スロット５を計算し、メモリ・コントローラ２０２が、或るアイテムが既にメモリ・スロット５を占めているかどうかを判断するためメモリ・スロット５を探査する。メモリ・スロット５を既に占めているアイテムがなければ、メモリ・コントローラ２０２は、アイテムＤをメモリ・スロット５中に挿入する。
【００４３】
これまでは、ハッシュされたメモリ・スロットを既に占めていたアイテムがなかったので全ての挿入オペレーションは通常通りのものであった。しかしながら、以下では、探査バリアＮおよび走査バリア・ビットの使用について例示する。以下では探査バリアＮを用い、このＮは２に等しい。本例を続けると、アイテムＥに対し、ハッシュ・メカニズム２１０が開始スロット１を計算し、メモリ・コントローラ２０２が、或るアイテムが既にメモリ・スロット１を占めているかどうかを判断するためメモリ・スロット１を探査すると、この例では該スロットはアイテムＡを格納している。メモリ・スロット１がアイテムＡを格納しているので、メモリ・コントローラ２０２は、最初の空のメモリ・スロットに到達するか、またはＳｉ＋Ｎのメモリ・スロットが探査されるまで探査を続ける。しかして、この例では、メモリ・コントローラ２０２は、メモリ・スロット２を探査し、メモリ・スロット２が空なので、メモリ・コントローラ２０２はアイテムＥをメモリ・スロット２中に挿入する。アイテムＦに対し、ハッシュ・メカニズム２１０が開始スロット６を計算し、メモリ・コントローラ２０２が、或るアイテムが既にメモリ・スロット６を占めているかどうかを判断するためメモリ・スロット６を探査すると、この例では該スロットはアイテムＢを格納している。メモリ・スロット６がアイテムＢを格納しているので、メモリ・コントローラ２０２は、最初の空のメモリ・スロットに到達するか、またはＳｉ＋Ｎのメモリ・スロットが探査されるまで探査を続ける。しかして、この例では、メモリ・コントローラ２０２は、メモリ・スロット７を探査し、メモリ・スロット７が空なので、メモリ・コントローラ２０２はアイテムＦをメモリ・スロット７中に挿入する。アイテムＧに対し、ハッシュ・メカニズム２１０が開始スロット７を計算し、メモリ・コントローラ２０２が、或るアイテムが既にメモリ・スロット７を占めているかどうかを判断するためメモリ・スロット７を探査すると、この例では該スロットはアイテムＦを格納している。メモリ・スロット７がアイテムＦを格納しているので、メモリ・コントローラ２０２は、最初の空のメモリ・スロットに到達するか、またはＳｉ＋Ｎのメモリ・スロットが探査されるまで探査を続ける。しかして、この例では、メモリ・コントローラ２０２は、メモリ・スロット８を探査し、メモリ・スロット８が空なので、メモリ・コントローラ２０２はアイテムＧをメモリ・スロット８中に挿入する。
【００４４】
以下の例では、メモリ・コントローラ２０２が、本例示的な諸実施形態の走査バリアを有効化する場合、すなわち、ハッシュされたメモリ・スロットＳｉまたは該ハッシュされたメモリ・スロットの後のＳｉ＋Ｎのメモリ・スロット中にオープンなメモリ・スロットがないので走査バリアを設定する場合について説明する。アイテムＨに対し、ハッシュ・メカニズム２１０が開始スロット１を計算し、メモリ・コントローラ２０２が、或るアイテムが既にメモリ・スロット１を占めているかどうかを判断するためメモリ・スロット１を探査すると、この例では該スロットはアイテムＡを格納している。メモリ・スロット１がアイテムＡを格納しているので、メモリ・コントローラ２０２は、最初の空のメモリ・スロットに到達するか、またはＳｉ＋Ｎのメモリ・スロットが探査されるまで探査を続ける。しかしながら、メモリ・スロット２はアイテムＥを格納しており、メモリ・スロット３はアイテムＣを格納しているので、Ｓｉ＋Ｎ（１＋２）の探査バリアによって、この探査はメモリ・スロット３で終わることになろう。したがって、アイテムＨに対する挿入を続けるため、メモリ・コントローラ２０２は、メモリ・スロット３で走査バリアを有効化し、これはＮ個の探査バリアを通り過ぎて探査を進めることを可能にし、ここでのＮは２である。メモリ・コントローラ２０２は、次いでメモリ・スロット４を探査し、メモリ・スロット４が空なので、メモリ・コントローラ２０２は、アイテムＨをメモリ・スロット４中に挿入する。
【００４５】
メモリ・コントローラ２０２が走査バリアを有効化する別の例として、アイテムＩに対し、ハッシュ・メカニズム２１０が開始スロット５を計算し、メモリ・コントローラ２０２が、或るアイテムが既にメモリ・スロット５を占めているかどうかを判断するためメモリ・スロット５を探査すると、この例では該スロットはアイテムＤを格納している。メモリ・スロット５がアイテムＤを格納しているので、メモリ・コントローラ２０２は、最初の空のメモリ・スロットに到達するか、またはＳｉ＋Ｎのメモリ・スロットが探査されるまで探査を続ける。しかしながら、メモリ・スロット６はアイテムＢを格納しており、メモリ・スロット７はアイテムＦを格納しているので、Ｓｉ＋Ｎ（１＋２）の探査バリアによって、この探査は終わることになろう。アイテムＩに対する挿入を続けるため、メモリ・コントローラ２０２は、メモリ・スロット７で走査バリアを有効化し、これはＮ個の探査バリアを通り過ぎて探査を進めることを可能にし、ここでのＮは２である。メモリ・コントローラ２０２は、次いでメモリ・スロット８を探査し、これはアイテムＧを格納している。この例では、メモリ・スロット８は最後のメモリ・スロットなので、メモリ・コントローラ２０２は、メモリ・コンテナ２０６の開始点、すなわちメモリ・スロット０に戻る。メモリ・コントローラ２０２は、次いでメモリ・スロット０を探査し、メモリ・スロット０が空なので、メモリ・コントローラ２０２はアイテムＩをメモリ・スロット０中に挿入する。
【００４６】
検索オペレーションに関しては、アイテムＡがメモリ・コンテナ２０６からの読出し対象である場合、メモリ・コントローラ２０２は、アイテムＡに対しハッシュ・メカニズム２１０を実行し、該メカニズムがアイテムＡを検索するための開始メモリ・スロットを計算する。例えば、アイテムＡに対し、ハッシュ・メカニズム２１０が開始スロット１を計算する。メモリ・コントローラ２０２は、開始スロット１から、以下の最初の事項が生じるまで探査を行う。
ｉ．  要求されたアイテムが見つかる。見つかった場合、メモリ・コントローラ２０２はその見つかったアイテムを返す。
ｉｉ．  空のメモリ・スロットに到達する。それが識別された場合、メモリ・コントローラ２０２は当該アイテムが存在しない旨を返す。
ｉｉｉ．  Ｓｉ＋Ｎのメモリ・スロットに到達し、「バリア」ビットが設定されていない。到達した場合、メモリ・コントローラ２０２は、当該アイテムが存在しない旨を返す。または
ｉｖ．  Ｓｉ＋Ｎのメモリ・スロットに到達し、「バリア」ビットが設定されている。到達した場合、メモリ・コントローラ２０２は、メモリ・スロットの全てを調べ終わるか、もしくは拡張探査バリアを利用するのに応じて、Ｓｉ＋２Ｎに到達するまで探査を続ける。拡張探査の過程で空のスロットに到達した場合、または全スロットが探査された（第一実施形態）が当該アイテムが見つからない場合、またはＳｉ＋２Ｎのスロットが探査された（第二実施形態）が当該アイテムが見つからない場合、メモリ・コントローラ２０２は、当該アイテムが存在しない旨を返す。所望のアイテムが見つかった場合、メモリ・コントローラ２０２はそのアイテムを返す。
しかして、本例では、アイテムＡがメモリ・スロット１中に存在するので、メモリ・コントローラ２０２は、上記のリスト中の一番目の探査ステップに達するだけで、アイテムＡを返すことになろう。アイテムＢ、Ｃ、およびＤについても同様な処理が行われることになろう。
【００４７】
アイテムＥに対し、ハッシュ・メカニズム２１０が開始スロット１を計算する。開始スロット１から、メモリ・コントローラ２０２はメモリ・スロット１を探査し、このスロットはアイテムＡを格納している。したがって、メモリ・コントローラ２０２は、他の探査ステップに移行し、それらステップで空のメモリ・スロットに到達せずにＳｉ＋Ｎのメモリ・スロットが探査される。この例において、メモリ・コントローラ２０２はメモリ・スロット２を探査し、メモリ・スロット２がアイテムＥを格納しているので、メモリ・コントローラ２０２は、アイテムＥを返す。アイテムＦに対し、ハッシュ・メカニズム２１０が開始スロット６を計算する。開始スロット６から、メモリ・コントローラ２０２はメモリ・スロット６を探査し、このスロットはアイテムＢを格納している。したがって、メモリ・コントローラ２０２は、他の探査ステップに移行し、それらステップで空のメモリ・スロットに到達せずにＳｉ＋Ｎのメモリ・スロットが探査される。この例において、メモリ・コントローラ２０２はメモリ・スロット７を探査し、メモリ・スロット７がアイテムＦを格納しているので、メモリ・コントローラ２０２は、アイテムＦを返す。アイテムＧに対し、ハッシュ・メカニズム２１０が開始スロット１を計算する。開始スロット７から、メモリ・コントローラ２０２はメモリ・スロット７を探査し、このスロットはアイテムＦを格納している。したがって、メモリ・コントローラ２０２は、他の探査ステップに移行し、それらステップで空のメモリ・スロットに到達せずにＳｉ＋Ｎのメモリ・スロットが探査される。この例において、メモリ・コントローラ２０２はメモリ・スロット８を探査し、メモリ・スロット８がアイテムＧを格納しているので、メモリ・コントローラ２０２は、アイテムＧを返す。なお、Ｓｉ＋Ｎのメモリ・スロットの探査の過程で空のメモリ・スロットに到達した場合、メモリ・コントローラ２０２は、当該アイテムが存在しないとの応答を返すことになろう。さらに、Ｓｉ＋Ｎのメモリ・スロットに到達し、Ｓｉ＋Ｎのメモリ・スロットに探査バリアが設定されていない場合も、メモリ・コントローラ２０２は、当該アイテムが存在しないとの応答を返すことになろう。
【００４８】
アイテムＨに対し、ハッシュ・メカニズム２１０が開始スロット１を計算する。開始スロット１から、メモリ・コントローラ２０２はメモリ・スロット１を探査し、このスロットはアイテムＡを格納している。したがって、メモリ・コントローラ２０２は、他の探査ステップに移行し、それらステップで空のメモリ・スロットに到達せずにＳｉ＋Ｎのメモリ・スロットが探査される。この例において、メモリ・コントローラ２０２は、アイテムＥを格納しているメモリ・スロット２、およびアイテムＣを格納しているメモリ・スロット３を探査する。メモリ・スロット３は、アイテムＨに対し計算された開始スロットに対するＳｉ＋Ｎに相等するので、メモリ・コントローラ２０２は、上記最後の探査ステップに移行し、該ステップで、メモリ・コントローラ２０２はバリア・ビットが設定されているかどうかを判断する。この例において、もしメモリ・スロット３に関連付けられたバリア・ビットが設定されていなければ、メモリ・コントローラ２０２は、当該アイテムは存在しないとの応答を返すことになろう。但し、この例では、メモリ・スロット３にバリア・ビットが設定されているので、メモリ・コントローラ２０２は、メモリ・スロット４に探査を続ける。この例において、メモリ・コントローラ２０２はメモリ・スロット４を探査し、メモリ・スロット４がアイテムＨを格納しているので、メモリ・コントローラ２０２はアイテムＨを返す。
【００４９】
同様にアイテムＩに対し、ハッシュ・メカニズム２１０が開始スロット５を計算する。開始スロット５から、メモリ・コントローラ２０２はメモリ・スロット５を探査し、このスロットはアイテムＤを格納している。したがって、メモリ・コントローラ２０２は、他の探査ステップに移行し、それらステップで空のメモリ・スロットに到達せずにＳｉ＋Ｎのメモリ・スロットが探査される。この例において、メモリ・コントローラ２０２は、アイテムＢを格納しているメモリ・スロット６、およびアイテムＦを格納しているメモリ・スロット７を探査する。メモリ・スロット７は、アイテムＩに対し計算された開始スロットに対するＳｉ＋Ｎに相等するので、メモリ・コントローラ２０２は、上記最後の探査ステップに移行し、該ステップで、メモリ・コントローラ２０２は、バリア・ビットが設定されているかどうかを判断する。この例において、メモリ・スロット７にバリア・ビットが設定されており、しかして、メモリ・コントローラ２０２は、メモリ・スロット８に探査を続け、このスロットはアイテムＧを格納している。この例では、メモリ・スロット８は最後のメモリ・スロットなので、メモリ・コントローラ２０２は、メモリ・コンテナ２０６の開始点、すなわちメモリ・スロット０に戻る。メモリ・コントローラ２０２は、メモリ・スロット０を探査し、メモリ・スロット０がアイテムＩを格納しているので、メモリ・コントローラ２０２はアイテムＩを返す。しかして、この検索オペレーションにおいて、挿入の過程で設定されるバリア・ビットが設定されている場合にのみ、Ｓｉ＋Ｎの探査バリアに到達した後でだけ探査が続けられ，これによりパフォーマンスと利用度とが向上する。
【００５０】
削除オペレーションでは、検索オペレーションと類似のオペレーションが行われる。すなわち、削除オペレーションで、メモリ・コントローラ２０２は、ハッシュ・メカニズムが開始スロットを算定したならば、以下の最初の事項が生じるまで探査を行う。
ｉ．  要求されたアイテムが見つかる。見つかった場合、メモリ・コントローラ２０２はそのメモリ・スロットに削除済みの標識をする。
ｉｉ．  空のメモリ・スロットに到達する。それが識別された場合、メモリ・コントローラ２０２は当該アイテムが存在しない旨を返す。
ｉｉｉ．  Ｓｉ＋Ｎのメモリ・スロットに到達し、「バリア」ビットが設定されていない。到達した場合、メモリ・コントローラ２０２は、当該アイテムが存在しない旨を返す。または
ｉｖ．  Ｓｉ＋Ｎのメモリ・スロットに到達し、「バリア」ビットが設定されている。到達した場合、メモリ・コントローラ２０２は、メモリ・スロットの全てが調べられるか、もしくは拡張探査バリアを利用するのに応じて、Ｓｉ＋２Ｎに到達するまで探査を続ける。拡張探査の過程で空のスロットに到達した場合、または全スロットが探査された（第一実施形態）が当該アイテムが見つからない場合、またはＳｉ＋２Ｎのスロットが探査された（第二実施形態）が当該アイテムが見つからない場合、メモリ・コントローラ２０２は、当該アイテムが存在しない旨を返す。所望のアイテムが見つかった場合、メモリ・コントローラ２０２は、そのメモリ・スロットに削除済みの標識をする。
【００５１】
これらのステップの例を提示すると、アイテムＡがメモリ・コンテナ２０６からの削除の対象である場合、メモリ・コントローラ２０２は、アイテムＡに対し、ハッシュ・メカニズム２１０を実行し、該メカニズムはアイテムＡを見出すための開始メモリ・スロットを計算する。例えば、アイテムＡに対し、ハッシュ・メカニズム２１０が開始メモリ・スロット１を計算する。メモリ・コントローラ２０２は、メモリ・スロット１を探査し、アイテムＡがメモリ・スロット１中に存在するので、メモリ・コントローラ２０２は、上記のリストの最初の探査ステップのみに到達するだけで、アイテムＡを削除する。アイテムＢ、Ｃ、およびＤについても同様な処理が行われることになろう。
【００５２】
アイテムＥに対し、ハッシュ・メカニズム２１０が開始スロット１を計算する。開始スロット１から、メモリ・コントローラ２０２はメモリ・スロット１を探査し、このスロットはアイテムＡを格納している。したがって、メモリ・コントローラ２０２は、他の探査ステップに移行し、それらステップで空のメモリ・スロットに到達せずにＳｉ＋Ｎのメモリ・スロットが探査される。この例において、メモリ・コントローラ２０２はメモリ・スロット２を探査し、メモリ・スロット２がアイテムＥを格納しているので、メモリ・コントローラ２０２は、アイテムＥを削除することになろう。アイテムＦに対し、ハッシュ・メカニズム２１０が開始スロット６を計算する。開始スロット６から、メモリ・コントローラ２０２はメモリ・スロット６を探査し、このスロットはアイテムＢを格納している。したがって、メモリ・コントローラ２０２は、他の探査ステップに移行し、それらステップで空のメモリ・スロットに到達せずにＳｉ＋Ｎのメモリ・スロットが探査される。この例において、メモリ・コントローラ２０２はメモリ・スロット７を探査し、メモリ・スロット７がアイテムＦを格納しているので、メモリ・コントローラ２０２は、アイテムＦを削除することになろう。アイテムＧに対し、ハッシュ・メカニズム２１０が開始スロット７を計算する。開始スロット７から、メモリ・コントローラ２０２はメモリ・スロット７を探査し、このスロットはアイテムＦを格納している。したがって、メモリ・コントローラ２０２は、他の探査ステップに移行し、それらステップで空のメモリ・スロットに到達せずにＳｉ＋Ｎのメモリ・スロットが探査される。この例において、メモリ・コントローラ２０２はメモリ・スロット８を探査し、メモリ・スロット８がアイテムＧを格納しているので、メモリ・コントローラ２０２は、アイテムＧを削除することになろう。なお、Ｓｉ＋Ｎのメモリ・スロットの探査の過程で空のメモリ・スロットに到達した場合、メモリ・コントローラ２０２は、当該アイテムが存在しないとの応答を返すことになろう。さらに、Ｓｉ＋Ｎのメモリ・スロットに到達し、Ｓｉ＋Ｎのメモリ・スロットに探査バリアが設定されていない場合も、メモリ・コントローラ２０２は、当該アイテムが存在しないとの応答を返すことになろう。
【００５３】
アイテムＨに対し、ハッシュ・メカニズム２１０が開始スロット１を計算する。開始スロット１から、メモリ・コントローラ２０２はメモリ・スロット１を探査し、このスロットはアイテムＡを格納している。したがって、メモリ・コントローラ２０２は、他の探査ステップに移行し、それらステップで空のメモリ・スロットに到達せずにＳｉ＋Ｎのメモリ・スロットが探査される。この例において、メモリ・コントローラ２０２は、アイテムＥを格納しているメモリ・スロット２、およびアイテムＣを格納しているメモリ・スロット３を探査する。メモリ・スロット３は、アイテムＨに対し計算された開始スロットのＳｉ＋Ｎに相等するので、メモリ・コントローラ２０２は、上記最後の探査ステップに移行し、該ステップで、メモリ・コントローラ２０２は、バリア・ビットが設定されているかどうかを判断する。この例において、もしメモリ・スロット３に関連付けられたバリア・ビットが設定されていなければ、メモリ・コントローラ２０２は、当該アイテムは存在しないとの応答を返すことになろう。但し、この例では、メモリ・スロット３にバリア・ビットが設定されているので、メモリ・コントローラ２０２は、メモリ・スロット４に探査を続ける。この例において、メモリ・コントローラ２０２はメモリ・スロット４を探査し、メモリ・スロット４がアイテムＨを格納しているので、メモリ・コントローラ２０２は、アイテムＨを削除することになろう。なお、バリア・ビットが設定されていたアイテムが削除されたとき、そのバリア・ビットはリセットされる。
【００５４】
同様にアイテムＩに対し、ハッシュ・メカニズム２１０が開始スロット５を計算する。開始スロット５から、メモリ・コントローラ２０２はメモリ・スロット５を探査し、このスロットはアイテムＤを格納している。したがって、メモリ・コントローラ２０２は、他の探査ステップに移行し、それらステップで空のメモリ・スロットに到達せずにＳｉ＋Ｎのメモリ・スロットが探査される。この例において、メモリ・コントローラ２０２は、アイテムＢを格納しているメモリ・スロット６、およびアイテムＦを格納しているメモリ・スロット７を探査する。メモリ・スロット７は、アイテムＩに対し計算された開始スロットのＳｉ＋Ｎに相等するので、メモリ・コントローラ２０２は、上記最後の探査ステップに移行し、該ステップで、メモリ・コントローラ２０２は、バリア・ビットが設定されているかどうかを判断する。この例において、メモリ・スロット７にバリア・ビットが設定されており、しかして、メモリ・コントローラ２０２は、メモリ・スロット８に探査を続け、このスロットはアイテムＧを格納している。この例では、メモリ・スロット８は最後のメモリ・スロットなので、メモリ・コントローラ２０２は、メモリ・コンテナ２０６の開始点、すなわちメモリ・スロット０に戻る。メモリ・コントローラ２０２は、メモリ・スロット０を探査し、メモリ・スロット０がアイテムＩを格納しているので、メモリ・コントローラ２０２はアイテムＩを削除することになろう。しかして、この検索オペレーションにおいて、挿入の過程で設定されるバリア・ビットが設定されている場合にのみ、Ｓｉ＋Ｎの探査バリアに到達した後でだけ探査が続けられ，これによりパフォーマンスと利用度とが向上する。なお、バリア・ビットが設定されていたアイテムが削除されたとき、そのバリア・ビットはリセットされる。
【００５５】
なお、削除済みのスロットの数および空のスロットの数は、探査の深度に直接的影響を有する。効率的に機能するためには、占有率は７０％〜８０％を超えることはできない。たとえ、削除済みのスロットがあったとしても、空のスロットの存在がこの深度を決める主要因である。時間が経過するにつれ、空のスロットの数は減少し、これにより遂には再ハッシュが不可避となる。この再ハッシュでは、全アイテムがリパックされ、削除済みスロットが空の状態に戻される。
【００５６】
探査バリア（群）およびバリア・ビットの実装以前の従来のメモリ実装においては、削除済みスロットの数および空のスロットの数が探査の深度に直接的な影響を有していた。しかして、従来の実装では、複数の空でない連続するスロットがあると、メモリ・コンテナの全長に亘って探査を続けなければならない可能性があった。しかしながら、本例示的な諸実施形態においては、探査はＳｉ＋Ｎのメモリ・スロットだけ続き、その後はバリア・ビットが設定されているときにだけポイントされる。図４は、或る例示的な実施形態による、走査バリアを使わない探査と走査バリアを使った探査とに対する、検索時間（ナノ秒単位）対利用率のグラフを表す。図４に示されるように、破線で示された従来の実装は、利用率が増すにつれて平均検索時間が劇的に増大している結果が示されている。その一方、本例示的な諸実施形態では、平均検索時間は、利用度が増加するほどには増大していない。
【００５７】
本発明は、システム、方法、もしくはコンピュータ・プログラム製品またはこれらの組み合せとすることができる。このコンピュータ・プログラム製品は、プロセッサに本発明の態様を実行させるためのコンピュータ可読プログラムを有するコンピュータ可読ストレージ媒体（または媒体群）を含むことが可能である。
【００５８】
このコンピュータ可読ストレージ媒体は、命令実行デバイスが使用するための命令を保持し格納できる有形のデバイスとすることができる。このコンピュータ可読ストレージ媒体は、例えば、以下に限らないが、電子ストレージ・デバイス、磁気ストレージ・デバイス、光ストレージ・デバイス、電磁気ストレージ・デバイス、半導体ストレージ・デバイス、または前述のデバイスの任意の適切な組み合せであってよい。コンピュータ可読ストレージ媒体のさらに具体的な例の非包括的リストには、携帯型コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、消去およびプログラム可能読み取り専用メモリ（ＥＰＲＯＭ：ｅｒａｓａｂｌｅ  ｐｒｏｇｒａｍｍａｂｌｅ  ｒｅａｄ−ｏｎｌｙ  ｍｅｍｏｒｙまたはフラッシュ・メモリ）、静的ランダム・アクセス・メモリ（ＳＲＡＭ：ｓｔａｔｉｃ  ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）、携帯型コンパクト・ディスク読み取り専用メモリ（ＣＤ−ＲＯＭ：ｃｏｍｐａｃｔ  ｄｉｓｃ  ｒｅａｄ−ｏｎｌｙ  ｍｅｍｏｒｙ）、デジタル多用途ディスク（ＤＶＤ：ｄｉｇｉｔａｌ  ｖｅｒｓａｔｉｌｅ  ｄｉｓｋ）、メモリ・スティック、フレキシブル・ディスク、パンチカードまたは記録された命令を有する溝中の嵩上げ構造体などの機械的符号化デバイス、および前述の任意の適切な組み合せが含まれる。本明細書で用いられるコンピュータ可読ストレージ媒体は、無線波または他の自由に伝播する電磁波、ウェーブガイドまたは他の送信媒体（例えば、光ファイバを通過する光パルス）、またはワイヤを通って送信される電気信号など、本質的に一時的な信号であると解釈されるものではない。
【００５９】
本明細書に述べられたコンピュータ可読プログラム命令は、コンピュータ可読ストレージ媒体から、それぞれのコンピューティング／処理デバイスに、または、例えばインターネット、ローカル・エリア・ネットワーク、広域ネットワークもしくはワイヤレス・ネットワークまたはこれらの組み合せなどのネットワークを介して、外部のコンピュータもしくは外部のストレージ・デバイスにダウンロードすることが可能である。このネットワークには、銅送信ケーブル、光送信ファイバ、ワイヤレス通信、ルータ、ファイアウォール、スイッチ、ゲートウェイ・コンピュータ、もしくはエッジ・サーバまたはこれらの組み合せが含まれてよい。それぞれのコンピューティング／処理デバイス中のネットワーク・アダプタ・カードまたはネットワーク・インターフェースは、ネットワークからコンピュータ可読プログラム命令を受信し、そのコンピュータ可読プログラム命令を、ストレージのため、それぞれのコンピューティング／処理デバイス内のコンピュータ可読ストレージ媒体の中に転送する。
【００６０】
本発明のオペレーションを実行するためのコンピュータ可読プログラム命令は、アセンブラ命令、命令集合アーキテクチャ（ＩＳＡ：ｉｎｓｔｒｕｃｔｉｏｎ−ｓｅｔ−ａｒｃｈｉｔｅｃｔｕｒｅ）命令、マシン命令、マシン依存命令、マイクロコード、ファームウェア命令、状態設定データ、または、Ｓｍａｌｌｔａｌｋ、Ｃ＋＋などのオブジェクト指向プログラミング言語、および「Ｃ」プログラミング言語もしくは類似のプログラミング言語などの従来式の手続き型プログラミング言語を含む、１つ以上のプログラミング言語の任意の組み合せで記述されたソース・コードもしくはオブジェクト・コードであってよい。このコンピュータ可読プログラム命令は、スタンドアロン・ソフトウェア・パッケージとしてユーザのコンピュータで専ら実行することも、ユーザのコンピュータで部分的に実行することもでき、一部をユーザのコンピュータで一部を遠隔コンピュータで実行することもでき、あるいは遠隔のコンピュータまたはサーバで専ら実行することもできる。後者の場合は、ローカル・エリア・ネットワーク（ＬＡＮ：ｌｏｃａｌ  ａｒｅａ  ｎｅｔｗｏｒｋ）または広域ネットワーク（ＷＡＮ：ｗｉｄｅ  ａｒｅａ  ｎｅｔｗｏｒｋ）を含む任意の種類のネットワークを介して、遠隔コンピュータをユーザのコンピュータに接続することもでき、あるいは（例えばインターネット・サービス・プロバイダを使いインターネットを介し）外部のコンピュータへの接続を行うことも可能である。いくつかの実施形態において、例えば、プログラム可能論理回路、フィールドプログラム可能ゲート・アレイ（ＦＰＧＡ：ｆｉｅｌｄ−ｐｒｏｇｒａｍｍａｂｌｅ  ｇａｔｅ  ａｒｒａｙ）、またはプログラム可能論理アレイ（ＰＬＡ：ｐｒｏｇｒａｍｍａｂｌｅ  ｌｏｇｉｃ  ａｒｒａｙ）を含む電子回路は、本発明の諸態様を実行すべく、該電子回路をカスタマイズするためコンピュータ可読プログラム命令の状態情報を利用することによって、該コンピュータ可読プログラム命令を実行することができる。
【００６１】
本発明の諸態様は、本発明の諸実施形態による方法、装置（システム）、およびコンピュータ・プログラム製品のフローチャート図もしくはブロック図またはその両方を参照しながら本明細書で説明されている。当然のことながら、フローチャート図もしくはブロック図またはその両方の各ブロック、およびフローチャート図もしくはブロック図またはその両方のブロックの組み合せは、コンピュータ可読プログラム命令によって実装することが可能である。
【００６２】
これらのコンピュータ可読プログラム命令を、汎用コンピュータ、特殊用途コンピュータ、またはマシンを形成する他のプログラム可能データ処理装置のプロセッサに提供し、そのコンピュータまたは他のプログラム可能データ処理装置のプロセッサを介して実行されるこれらの命令が、フローチャートもしくはブロック図またはその両方のブロックもしくはブロック群中に特定されている機能群／動作群を実装するための手段を生成するようにすることができる。また、コンピュータ、他のプログラム可能データ処理装置、または他のデバイスに対し特定の仕方で機能するよう命令することが可能なこれらのコンピュータ可読プログラム命令を、コンピュータ可読媒体に格納し、そのコンピュータ可読媒体に格納された命令が、フローチャートもしくはブロック図またはその両方のブロックまたはブロック群中に特定されている機能／動作を実装する命令群を包含する製造品を作り出すようにすることができる。
【００６３】
さらに、コンピュータ可読プログラム命令を、コンピュータ、他のプログラム可能データ処理装置、または他のデバイスにロードし、そのコンピュータ上、他のプログラム可能装置上、または他のデバイス上で一連のオペレーション・ステップを実施させて、コンピュータ実装のプロセスを作り出し、当該コンピュータ上、他のプログラム可能装置上、または他のデバイス上で実行される命令が、フローチャートもしくはブロック図またはその両方のブロックもしくはブロック群中に特定されている機能群／動作群を実装するためのプロセスを提供するようにすることも可能である。
【００６４】
図５は、或る例示的な実施形態による、開アドレス法探査バリア・メカニズムによって行われる挿入オペレーションの典型的な流れ図を表す。オペレーションが開始されると、本メカニズムは、メモリ・コンテナ中のメモリ・スロットにアイテムを挿入する、書込む、などの要求をアプリケーションから受信する（ステップ５０２）。本メカニズムは、当該アイテムに対するハッシュ値を計算することによって開始メモリ・スロット（Ｓｉ）を算定する（ステップ５０４）。本メカニズムは、開始メモリ・スロット（Ｓｉ）を使い、メモリ・コンテナ中の該開始メモリ・スロット（Ｓｉ）が空かどうかを判断する（ステップ５０６）。ステップ５０６で、本メカニズムが開始メモリ・スロット（Ｓｉ）が空であると判断した場合、本メカニズムは、当該アイテムを開始メモリ・スロット（Ｓｉ）に格納し（ステップ５０８）、その後このオペレーションは終了する。
【００６５】
ステップ５０６で、本メカニズムが開始メモリ・スロット（Ｓｉ）が占有されていると判断した場合、本メカニズムは、メモリ・コンテナ中の開始メモリ・スロットの直後のＮ個のメモリ・スロット（Ｓｉ＋Ｎ）の最初の空のメモリ・スロットを識別するために、それら直後のＮ個のスロット探査する（ステップ５１０）。本例示的な諸実施形態において、Ｎは探査バリアであり、これはユーザ設定が可能な定数であって、或る特定のアイテムに対する探査プロセスを限定する。ステップ５１０で、本メカニズムが、メモリ・コンテナ中の開始メモリ・スロットの直後のＮ個のメモリ・スロット（Ｓｉ＋Ｎ）の最初の空のメモリ・スロットを識別した場合、本メカニズムは、当該アイテムをその最初の空のメモリ・スロットに格納し（ステップ５１２）、その後このオペレーションは終了する。
【００６６】
ステップ５１０で、本メカニズムが、メモリ・コンテナ中の開始メモリ・スロットの直後のＮ個のメモリ・スロット（Ｓｉ＋Ｎ）の最初の空のメモリ・スロットを識別できなかった場合、本メカニズムは、最初の空のメモリ・スロットを識別するために、メモリ・コンテナ中のＳｉ＋Ｎメモリ・スロットに続く残りのメモリ・スロットの探査に進む（ステップ５１４）。ステップ５１４で、本メカニズムが、メモリ・コンテナ中のＳｉ＋Ｎメモリ・スロットに続く残りのメモリ・スロット中で最初の空のメモリ・スロットを識別した場合、本メカニズムは、当該アイテムをその最初の空のメモリ・スロットに格納する（ステップ５１６）。また、本メカニズムは、後での検索オペレーションおよび削除オペレーションでの探査が、探査バリアＮを通り過ぎて進めることができるように、（Ｓｉ＋Ｎ）メモリ・スロットに関連付けてバリア・ビットを設定し（ステップ５１８）、その後このオペレーションは終了する。ステップ５１４で、本メカニズムが、メモリ・コンテナ中のＳｉ＋Ｎメモリ・スロットに続く残りのメモリ・スロット中に最初の空のメモリ・スロットを識別できなかった場合、本メカニズムは、メモリ・コンテナ中に当該アイテムが格納されていない可能性があることを示す通知をアプリケーションに返し（ステップ５２０）、その後このオペレーションは終了する。
【００６７】
図６は、或る例示的な実施形態による、開アドレス法探査バリア・メカニズムによって行われる検索オペレーションの典型的な流れ図を表す。オペレーションが開始されると、本メカニズムは、メモリ・コンテナ中の或るアイテムを見出す、読み出す、または検索する要求をアプリケーションから受信する（ステップ６０２）。本メカニズムは、当該アイテムに対するハッシュ値を計算することによって開始メモリ・スロット（Ｓｉ）を計算する（ステップ６０４）。本メカニズムは、開始メモリ・スロット（Ｓｉ）を用い、当該アイテムが開始メモリ・スロット（Ｓｉ）中にあるかどうかを判断するために、該メモリ・スロットを探査する（ステップ６０６）。ステップ６０６で、本メカニズムが、当該アイテムが開始メモリ・スロット（Ｓｉ）を占めていると判断した場合、本メカニズムは、該開始メモリ・スロット（Ｓｉ）からの当該アイテムをアプリケーションに返し（ステップ６０８）、その後このオペレーションは終了する。
【００６８】
ステップ６０６で、本メカニズムが、当該アイテムが開始メモリ・スロット（Ｓｉ）を占めていないと判断した場合、本メカニズムは、当該アイテムがメモリ・コンテナ中の開始メモリ・スロットの直後のＮ個のメモリ・スロット（Ｓｉ＋Ｎ）の１つを占めているかどうかを識別するために、該直後のＮ個のスロットを探査する（ステップ６１０）。本例示的な諸実施形態において、Ｎは探査バリアであり、これはユーザ設定が可能な定数であり、或る特定のアイテムに対する探査プロセスを限定する。ステップ６１０で、本メカニズムが、メモリ・コンテナ中の開始メモリ・スロットの直後のＮ個のメモリ・スロット（Ｓｉ＋Ｎ）の１つの中に当該アイテムを識別した場合、本メカニズムは、そのメモリからの当該アイテムをアプリケーションに返し（ステップ６１２）、その後このオペレーションは終了する。
【００６９】
ステップ６１０で、本メカニズムが、メモリ・コンテナ中の開始メモリ・スロットの直後のＮ個のメモリ・スロット（Ｓｉ＋Ｎ）の１つの中に当該アイテムを識別できなかった場合、本メカニズムは、（Ｓｉ＋Ｎ）メモリ・スロットに関連付けられたバリア・ビットが設定されているかどうかを判断する（ステップ６１４）。ステップ６１４で、本メカニズムが、（Ｓｉ＋Ｎ）メモリ・スロットに関連付けられたバリア・ビットが設定されていないと判断した場合、本メカニズムは、アプリケーションに、当該アイテムが存在しないことを示す通知を返し（ステップ６１６）、その後このオペレーションは終了する。ステップ６１４で、本メカニズムが、（Ｓｉ＋Ｎ）メモリ・スロットに関連付けられたバリア・ビットが設定されていると判断した場合、本メカニズムは、メモリ・コンテナに関連付けられた第二探査バリア（２Ｎ）があるかどうかを判断する（ステップ６１８）。ステップ６１８で、本メカニズムが、第二探査バリア（２Ｎ）がないと判断した場合、本メカニズムは、当該アイテムについて残りの全てのメモリ・スロットを探査する（ステップ６２０）。ステップ６２０で、本メカニズムが当該アイテムを見出した場合、本メカニズムは、メモリ・スロットからの当該アイテムをアプリケーションに返し（ステップ６２２）、その後このオペレーションは終了する。ステップ６２０で、本メカニズムが当該アイテムを見出せなかった場合、本メカニズムは、アプリケーションに、当該アイテムが存在しないことを示す通知を返し（ステップ６２４）、その後このオペレーションは終了する。
【００７０】
ステップ６１８で、本メカニズムが、第二探査バリア（２Ｎ）があると判断した場合、本メカニズムは、当該アイテムがメモリ・コンテナ中の開始メモリ・スロットの直後のＮ個のメモリ・スロット（Ｓｉ＋２Ｎ）の１つを占めているかどうかを識別するために、該直後の２Ｎのスロットを探査する（ステップ６２６）。ステップ６２６で、本メカニズムが、メモリ・コンテナ中の開始メモリ・スロットの直後の２Ｎ個のメモリ・スロット（Ｓｉ＋２Ｎ）の１つ中で当該アイテムを識別した場合、本メカニズムは、メモリ・スロットからの当該アイテムをアプリケーションに返し（ステップ６２８）、その後このオペレーションは終了する。ステップ６２６で、本メカニズムが、メモリ・コンテナ中の開始メモリ・スロットの直後の２Ｎ個のメモリ・スロット（Ｓｉ＋２Ｎ）の１つ中に当該アイテムを識別できなかった場合、本メカニズムは、アプリケーションに、当該アイテムが存在しないことを示す通知を返し（ステップ６３０）、その後このオペレーションは終了する。
【００７１】
図７は、或る例示的な実施形態による、開アドレス法探査バリア・メカニズムによって行われる削除オペレーションの典型的な流れ図を表す。オペレーションが開始されると、本メカニズムは、メモリ・コンテナ中の或るアイテムを削除する要求をアプリケーションから受信する（ステップ７０２）。本メカニズムは、当該アイテムに対するハッシュ値を計算することによって開始メモリ・スロット（Ｓｉ）を計算する（ステップ７０４）。本メカニズムは、開始メモリ・スロット（Ｓｉ）を用い、当該アイテムが開始メモリ・スロット中にあるかどうかを判断するため該メモリ・スロット（Ｓｉ）を探査する（ステップ７０６）。ステップ７０６で、本メカニズムが、当該アイテムが開始メモリ・スロット（Ｓｉ）を占めていると判断した場合、本メカニズムは、開始メモリ・スロット（Ｓｉ）から当該アイテムを削除し（ステップ７０８）、その後このオペレーションは終了する。
【００７２】
ステップ７０６で、本メカニズムが、当該アイテムが開始メモリ・スロット（Ｓｉ）を占めていないと判断した場合、本メカニズムは、当該アイテムがメモリ・コンテナ中の開始メモリ・スロットの直後のＮ個のメモリ・スロット（Ｓｉ＋Ｎ）の１つを占めているかどうかを識別するために、該直後のＮ個のスロットを探査する（ステップ７１０）。本例示的な諸実施形態において、Ｎは探査バリアであり、これはユーザ設定が可能な定数であり、或る特定のアイテムに対する探査プロセスを限定する。ステップ７１０で、本メカニズムが、メモリ・コンテナ中の開始メモリ・スロットの直後のＮ個のメモリ・スロット（Ｓｉ＋Ｎ）の１つの中に当該アイテムを識別した場合、本メカニズムは、そのメモリ・スロットから当該アイテムを削除し（ステップ７１２）、その後このオペレーションは終了する。
【００７３】
ステップ７１０で、本メカニズムが、メモリ・コンテナ中の開始メモリ・スロットの直後のＮ個のメモリ・スロット（Ｓｉ＋Ｎ）の１つの中に当該アイテムを識別できなかった場合、本メカニズムは、（Ｓｉ＋Ｎ）メモリ・スロットに関連付けられたバリア・ビットが設定されているかどうかを判断する（ステップ７１４）。ステップ７１４で、本メカニズムが、（Ｓｉ＋Ｎ）メモリ・スロットに関連付けられたバリア・ビットが設定されていないと判断した場合、本メカニズムは、アプリケーションに、当該アイテムが存在しないことを示す通知を返し（ステップ７１６）、その後このオペレーションは終了する。ステップ７１４で、本メカニズムが、（Ｓｉ＋Ｎ）メモリ・スロットに関連付けられたバリア・ビットが設定されていると判断した場合、本メカニズムは、メモリ・コンテナに関連付けられた第二探査バリア（２Ｎ）があるかどうかを判断する（ステップ７１８）。ステップ７１８で、本メカニズムが、第二探査バリア（２Ｎ）がないと判断した場合、本メカニズムは、当該アイテムについて残りの全てのメモリ・スロットを探査する（ステップ７２０）。ステップ７２０で、本メカニズムが当該アイテムを見出した場合、本メカニズムは、メモリ・スロットから当該アイテムを削除し（ステップ７２２）、（Ｓｉ＋Ｎ）メモリ・スロットに関連付けて設定されたバリア・ビットをリセットし（ステップ７２４）、その後このオペレーションは終了する。ステップ７２０で、本メカニズムが当該アイテムを見出せなかった場合、本メカニズムは、当該アイテムが存在しないことを示す通知をアプリケーションに返し（ステップ７２６）、その後このオペレーションは終了する。
【００７４】
ステップ７１８で、本メカニズムが、第二探査バリア（２Ｎ）があると判断した場合、本メカニズムは、当該アイテムがメモリ・コンテナ中の開始メモリ・スロットの直後のＮ個のメモリ・スロット（Ｓｉ＋２Ｎ）の１つを占めているかどうかを識別するために、該直後の２Ｎ個のスロットを探査する（ステップ７２８）。ステップ７２８で、本メカニズムが、メモリ・コンテナ中の開始メモリ・スロットの直後の２Ｎ個のメモリ・スロット（Ｓｉ＋２Ｎ）の１つ中で当該アイテムを識別した場合、本メカニズムは、メモリ・スロットからそのアイテムを削除し（ステップ７３０）、（Ｓｉ＋Ｎ）メモリ・スロットに関連付けて設定されたバリア・ビットをリセットし（ステップ７３２）、その後このオペレーションは終了する。ステップ７２８で、本メカニズムが、メモリ・コンテナ中の開始メモリ・スロットの直後の２Ｎ個のメモリ・スロット（Ｓｉ＋２Ｎ）の１つ中に当該アイテムを識別できなかった場合、本メカニズムは、アプリケーションに、当該アイテムが存在しないことを示す通知を返し（ステップ７３４）、その後このオペレーションは終了する。
【００７５】
諸図面中のフローチャートおよびブロック図は、本発明の様々な実施形態による、システム、方法、およびコンピュータ・プログラム製品から可能となる実装のアーキテクチャ、機能性、およびオペレーションを表している。この点に関し、フローチャートまたはブロック図中の各ブロックは、特定の論理機能（群）を実装するための一つ以上の実行可能命令を含む、モジュール、セグメント、または命令の部分を表し得る。いくつかの別の実装においては、ブロック中に記載された機能が、図面に記載された順序から外れて行われてもよい。例えば、連続して示された２つのブロックが、関与する機能性に応じ、実際にはほぼ同時に実行されることがあり、時にはこれらのブロックが逆の順序で実行されることもあり得る。さらに、ブロック図もしくはフローチャート図またはその両方の各ブロック、およびブロック図もしくはフローチャート図またはその両方中のブロック群の組み合せは、特定の機能または動作を実施する特殊用途ハードウェア・ベースのシステムによって実装でき、または特殊用途ハードウェアとコンピュータ命令との組み合せによって実行できることにも留意すべきである。
【００７６】
しかして、本例示的な諸実施形態は、ハッシュベースのキー・バリュー格納メカニズムにおける、様々な種類のハッシュ・アルゴリズムに関連するパフォーマンスおよび収容能力利用度の両方に有益な、開アドレス法探査バリアのためのメカニズムを提供する。本例示的な諸実施形態において用いられる開アドレス法探査バリア・スキームは、全オペレーションのより良好なパフォーマンス、より高い占有利用率、必要な再ハッシュの回数の低減、全体的キャッシュ局所性、小さなメモリ・オーバーヘッド、バリアの数の設定可能性、バリア間の間隔設定など、および再ハッシュ、イテレータの無効化のない挿入を提供する。
【００７７】
前に述べたように、当然のことながら、これら例示的な諸実施形態は、全体がハードウェアの実施形態、全体がソフトウェアの実施形態、またはハードウェアとソフトウェアとの要素を包含する実施形態の形を取ることが可能である。一例示の実施形態において、本例示的な諸実施形態のメカニズムは、ソフトウェアまたはプログラム・コードで実装され、これには、以下に限らないが、ファームウェア、常駐ソフトウェア、マイクロコードなどが含まれる。
【００７８】
プログラム・コードを格納もしくは実行、またはその両方を行うために適したデータ処理システムには、例えばシステムバスなどの通信バスを介して直接的または間接的にメモリ素子に連結された、少なくとも１つのプロセッサが含まれることになろう。これらメモリ素子には、プログラム・コードの実際の実行の過程で用いられるローカル・メモリ、バルク・ストレージ、および、実行の過程でコードをバルク・ストレージから読み出す必要回数を減らすために、少なくとも一部のプログラム・コードの一時的ストレージを提供するキャッシュ・メモリが含まれてよい。このメモリは、以下に限らないが、ＲＯＭ、ＰＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、ＤＲＡＭ、ＳＲＡＭ、フラッシュ・メモリ、固体メモリなどを含む、様々な種類であってよい。
【００７９】
本システムには、直接に、あるいは、介在する有線またはワイヤレスＩ／Ｏインターフェースもしくはコントローラまたはその両方などを介して、入力／出力またはＩ／Ｏデバイス（以下に限らないが、キーボード、ディスプレイ、ポインティング・デバイスなどを含む）を連結することができる。Ｉ／Ｏデバイスは、従来のキーボード、ディスプレイ、ポインティング・デバイスなど以外に、例えば、以下に限らないが、スマートフォン、タブレット・コンピュータ、タッチ・スクリーン・デバイス、音声認識デバイスなどを含め、有線またはワイヤレス接続を介して連結された通信デバイスなど、様々な形を取ることが可能である。一切の既存のまたは将来開発されるＩ／Ｏデバイスが本例示的な諸実施形態の範囲の内として意図されている。
【００８０】
また、データ処理システムが、介在する私設または公衆ネットワークを介して他のデータ処理システム、または遠隔のプリンタもしくはストレージ・デバイスに連結できるようにするため、システムにネットワーク・アダプタが連結されてよい。モデム、ケーブル・モデム、およびイーサネット（登録商標）カードは、有線通信のため現在利用可能なネットワーク・アダプタの種類のほんの一部である。また、以下に限らないが、８０２．１１／ａ／ｂ／ｇ／ｎワイヤレス通信アダプタ、ブルートゥース（登録商標）ワイヤレス・アダプタなどを含め、ワイヤレス通信ベースのネットワーク・アダプタも利用が可能である。一切の既存のまたは将来開発されるネットワーク・アダプタが本発明の趣旨および範囲の内として意図されている。
【００８１】
本発明の記述は、例示および説明の目的で提示されたものであり、網羅的であることも、または本発明を開示した形態に限定することも意図されていない。当業者には、本発明の範囲および趣旨から逸脱することのない多くの修改および別形が明白であろう。諸実施形態は、本発明の原理および実際的な応用を最善に説明し、他の当業者が、意図する特定の用途に適したさまざまな修改を加えた様々な実施形態に関連して、本発明を理解できるように選択し説明されたものである。本明細書で用いられた用語は、諸実施形態の原理、実際上の応用、または市販の技術の技術的な改良を最善に説明し、または他の当業者が本明細書に開示された諸実施形態を理解できるように選択されたものである。
【図１】
2020535510.tif 000003
【図２】
2020535510.tif 000004
【図３】
2020535510.tif 000005
【図４】
2020535510.tif 000006
【図５】
2020535510.tif 000007
【図６】
2020535510.tif 000008
【図７】
2020535510.tif 000009
【手続補正書】
【提出日】令和2年4月7日(2020.4.7)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データ処理システムにおいて、メモリ・コンテナに関連して開アドレス法探査バリアを利用する方法であって、前記方法は、
前記メモリ・コンテナ中の或るアイテムを見出す要求をアプリケーションから受信するのに応じて、前記アイテムに対する開始メモリ・スロットを計算するステップと、
前記アイテムが前記開始メモリ・スロットを占めていないのに応じて、前記アイテムについて前記開始メモリ・スロットの直後の第一所定数のメモリ・スロットを探査するステップと、
前記アイテムが、前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの１つを占めているのに応じて、前記アイテムを前記アプリケーションに返すステップと、
前記アイテムが、前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの１つを占めていないのに応じて、前記第一所定数のメモリ・スロットの最後に関連付けてバリア・ビットが設定されているかどうかを判断するステップと、
前記バリア・ビットが設定されているのに応じて、前記アイテムについて前記メモリ・コンテナの少なくとも部分を探査し、前記メモリ・コンテナの前記部分に前記アイテムが見出されたのに応じて、前記アイテムを前記アプリケーションに返すステップと、
前記バリア・ビットが設定されていないのに応じて、前記アイテムが前記メモリ・コンテナ中に存在しないことの通知を前記アプリケーションに返すステップと、
を含む、方法。
【請求項２】
前記メモリ・コンテナの前記部分が、前記メモリ・コンテナの全ての未探査のメモリ・スロットである、請求項１に記載の方法。
【請求項３】
前記メモリ・コンテナの前記部分が、前記開始スロットの直後の第二所定数のメモリ・スロットであり、前記方法が、
前記アイテムが、前記開始メモリ・スロットの直後の前記第二所定数のメモリ・スロットの１つを占めているのに応じて、前記アイテムを前記アプリケーションに返すステップと、
前記アイテムが、前記開始メモリ・スロットの直後の前記第二所定数のメモリ・スロットの１つを占めていないのに応じて、前記アイテムが前記メモリ・コンテナ中に存在しないことの通知を前記アプリケーションに返すステップと、
をさらに含む、請求項１に記載の方法。
【請求項４】
前記アイテムが前記開始メモリ・スロットを占めているのに応じて、前記開始メモリ・スロットからの前記アイテムを前記アプリケーションに返すステップ、
をさらに含む、請求項１〜３のいずれか１項に記載の方法。
【請求項５】
前記開始メモリ・スロットがハッシュ・アルゴリズムを使って計算される、請求項１〜４のいずれか１項に記載の方法。
【請求項６】
前記アイテムが、前記メモリ・コンテナ中の複数のメモリ・スロットの１つの中に、
前記アイテムを、前記メモリ・コンテナ中の前記複数のメモリ・スロットの１つの中に挿入する要求を受信するのに応じて、前記アイテムに対する前記開始メモリ・スロットを計算するステップと、
前記開始メモリ・スロットが空であるのに応じて、前記アイテムを前記開始メモリ・スロット中に格納するステップと、
前記開始メモリ・スロットが占有されているのに応じて、前記アイテムについて、前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットを探査するステップと、
前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの１つが空であるのに応じて、前記アイテムを前記空のメモリ・スロットに格納するステップと、
前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの全てが占有されているのに応じて、空のメモリ・スロットについて前記メモリ・コンテナの少なくとも前記部分を探査するステップと、
前記空のメモリ・スロットが識別されたのに応じて、前記アイテムを前記空のメモリ・スロットに格納し、前記第一所定数のメモリ・スロットの最後に関連付けて設定される前記バリア・ビットを設定するステップと、
前記空のメモリ・スロットが識別できなかったのに応じて、前記アイテムを前記メモリ・コンテナ中に格納できないことの通知を前記アプリケーションに返すステップと、
を含む方法によって挿入される、請求項１に記載の方法。
【請求項７】
前記メモリ・コンテナの前記部分が前記メモリ・コンテナの全ての未探査のメモリ・スロットである、請求項６に記載の方法。
【請求項８】
前記メモリ・コンテナの前記部分が前記開始メモリ・スロットの直後の第二所定数のメモリ・スロットであり、前記方法が、
前記開始メモリ・スロットの直後の前記第二所定数のメモリ・スロットの１つに空のスロットを前記識別したのに応じて、前記アイテムを前記空のメモリ・スロットに格納するステップと
前記開始メモリ・スロットの直後の前記第二所定数のメモリ・スロットの１つに空のスロットを識別できなかったのに応じて、前記アイテムを前記メモリ・コンテナ中に格納できないことの通知を前記アプリケーションに返すステップと、
をさらに含む、請求項６に記載の方法。
【請求項９】
前記アイテムが、前記メモリ・コンテナ中の複数のメモリ・スロットの１つから、
前記メモリ・コンテナ中の或るアイテムを削除する要求を受信するのに応じて、前記アイテムに対する前記開始メモリを計算するステップと、
前記アイテムが前記開始メモリ・スロットを占めていないのに応じて、前記アイテムについて前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットを探査するステップと、
前記アイテムが、前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの１つを占めているのに応じて、前記メモリ・スロットから前記アイテムを削除するステップと、
前記アイテムが、前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの１つを占めていないのに応じて、前記第一所定数のメモリ・スロットの最後に関連付けて前記バリア・ビットが設定されているかどうかを判断するステップと、
前記バリア・ビットが設定されているのに応じて、前記アイテムについて前記メモリ・コンテナの少なくとも前記部分を探査し、前記メモリ・コンテナの前記部分に前記アイテムが見出されたのに応じて、前記メモリ・スロットから前記アイテムを削除するステップと、
前記バリア・ビットが設定されていないのに応じて、前記アイテムが前記メモリ・コンテナ中に存在しないことの通知を前記アプリケーションに返すステップと、
を含む方法によって削除される、請求項１に記載の方法。
【請求項１０】
前記メモリ・コンテナの前記部分が前記開始メモリ・スロットの直後の第二所定数のメモリ・スロットであり、前記方法が、
前記アイテムが、前記開始メモリ・スロットの直後の前記第二所定数のメモリ・スロットの１つを占めているのに応じて、前記アイテムを前記メモリ・スロットから削除するステップと、
前記アイテムが、前記開始メモリ・スロットの直後の前記第二所定数のメモリ・スロットの１つを占めていないのに応じて、前記アイテムが前記メモリ・コンテナ中に存在しないことの通知を前記アプリケーションに返すステップと、
をさらに含む、請求項９に記載の方法。
【請求項１１】
中に格納されたコンピュータ可読プログラムを有するコンピュータ可読ストレージ媒体を含むコンピュータ・プログラム製品であって、前記コンピュータ可読プログラムは、コンピューティング・デバイス上で実行されると、前記コンピューティング・デバイスに、
メモリ・コンテナ中の或るアイテムを見出す要求をアプリケーションから受信するのに応じて、前記アイテムに対する開始メモリ・スロットを計算させ、
前記アイテムが前記開始メモリ・スロットを占めていないのに応じて、前記アイテムについて前記開始メモリ・スロットの直後の第一所定数のメモリ・スロットを探査させ、
前記アイテムが、前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの１つを占めているのに応じて、前記アイテムを前記アプリケーションに返させ、
前記アイテムが、前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの１つを占めていないのに応じて、前記第一所定数のメモリ・スロットの最後に関連付けてバリア・ビットが設定されているかどうかを判断させ、
前記バリア・ビットが設定されているのに応じて、前記アイテムについて前記メモリ・コンテナの少なくとも部分を探査させ、前記メモリ・コンテナの部分に前記アイテムが見出されたのに応じて、前記アプリケーションに前記アイテムを返させ、且つ
前記バリア・ビットが設定されていないのに応じて、前記アイテムが前記メモリ・コンテナ中に存在しないことの通知を前記アプリケーションに返させる、
コンピュータ・プログラム。
【請求項１２】
前記メモリ・コンテナの前記部分が前記メモリ・コンテナの全ての未探査のメモリ・スロットである、請求項１１に記載のコンピュータ・プログラム。
【請求項１３】
前記メモリ・コンテナの前記部分が前記開始メモリ・スロットの直後の第二所定数のメモリ・スロットであり、前記コンピュータ可読プログラムは、前記コンピューティング・デバイスにさらに、
前記アイテムが前記開始メモリ・スロットの直後の前記第二所定数のメモリ・スロットの１つを占めているのに応じて、前記アイテムを前記アプリケーションに返させ、且つ
前記アイテムが、前記開始メモリ・スロットの直後の前記第二所定数のメモリ・スロットの１つを占めていないのに応じて、前記アイテムが前記メモリ・コンテナ中に存在しないことの通知を前記アプリケーションに返させる、
請求項１１に記載のコンピュータ・プログラム。
【請求項１４】
前記コンピュータ可読プログラムが、前記コンピューティング・デバイスにさらに、
前記アイテムが前記開始メモリ・スロットを占めているのに応じて、前記開始メモリ・スロットからの前記アイテムを前記アプリケーションに返させる、
請求項１１〜１３のいずれか１項に記載のコンピュータ・プログラム。
【請求項１５】
前記アイテムが、前記メモリ・コンテナ中の複数のメモリ・スロットの１つの中に、前記コンピューティング・デバイスにさらに、
前記アイテムを前記メモリ・コンテナ中の前記複数のメモリ・スロットの１つの中に挿入する要求を受信するのに応じて、前記アイテムに対する前記開始メモリ・スロットを計算させ、
前記開始メモリ・スロットが空であるのに応じて、前記開始メモリ・スロット中に前記アイテムを格納させ、
前記開始メモリ・スロットが占有されているのに応じて、前記アイテムついて、前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットを探査させ、
前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの１つが空であるのに応じて、前記アイテムを前記空のメモリ・スロットに格納させ、
前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの全てが占有されているのに応じて、空のメモリ・スロットについて前記メモリ・コンテナの少なくとも前記部分を探査させ、
前記空のメモリ・スロットが識別されたのに応じて、前記アイテムを前記空のメモリ・スロットに格納し、前記第一所定数のメモリ・スロットの最後に関連付けて設定された前記バリア・ビットを設定させ、
前記空のメモリ・スロットが識別できなかったのに応じて、前記アイテムを前記メモリ・コンテナ中に格納できないことの通知を前記アプリケーションに返させる、
前記コンピュータ可読プログラムによって挿入される、
請求項１１に記載のコンピュータ・プログラム。
【請求項１６】
前記メモリ・コンテナの前記部分が前記メモリ・コンテナの全ての未探査のメモリ・スロットである、請求項１５に記載のコンピュータ・プログラム。
【請求項１７】
前記メモリ・コンテナの前記部分が前記開始メモリ・スロットの直後の第二所定数のメモリ・スロットであり、前記コンピュータ可読プログラムが、前記コンピューティング・デバイスにさらに、
前記開始メモリ・スロットの直後の前記第二所定数のメモリ・スロットの１つに空のスロットを前記識別するのに応じて、前記アイテムを前記空のメモリ・スロットに格納させ、且つ
前記開始メモリ・スロットの直後の前記第二所定数のメモリ・スロットの１つに空のスロットを識別できなかったのに応じて、前記アイテムを前記メモリ・コンテナに格納できないことの通知を前記アプリケーションに返させる、
請求項１５に記載のコンピュータ・プログラム。
【請求項１８】
前記アイテムが、前記メモリ・コンテナ中の複数のメモリ・スロットの１つから、前記コンピューティング・デバイスにさらに、
前記メモリ・コンテナ中の或るアイテムを削除する要求を受信するのに応じて、前記アイテムに対する前記開始メモリを計算させ、
前記アイテムが前記開始メモリ・スロットを占めていないのに応じて、前記アイテムについて前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットを探査させ、
前記アイテムが、前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの１つを占めているのに応じて、前記メモリ・スロットから前記アイテムを削除させ、
前記アイテムが、前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの１つを占めていないのに応じて、前記第一所定数のメモリ・スロットの最後に関連付けて前記バリア・ビットが設定されているかどうかを判断させ、
前記バリア・ビットが設定されているのに応じて、前記アイテムについて前記メモリ・コンテナの少なくとも前記部分を探査し、前記メモリ・コンテナの前記部分に前記アイテムが見出されたのに応じて、前記メモリ・スロットから前記アイテムを削除させ、
前記バリア・ビットが設定されていないのに応じて、前記アイテムが前記メモリ・コンテナ中に存在しないことの通知を前記アプリケーションに返させる、
前記コンピュータ可読プログラムによって削除される、
請求項１１に記載のコンピュータ・プログラム。
【請求項１９】
前記メモリ・コンテナの前記部分が前記開始メモリ・スロットの直後の第二所定数のメモリ・スロットであり、前記コンピュータ可読プログラムが、前記コンピューティング・デバイスにさらに、
前記アイテムが、前記開始メモリ・スロットの直後の前記第二所定数のメモリ・スロットの１つを占めているのに応じて、前記アイテムを前記メモリ・スロットから削除させ、且つ
前記アイテムが、前記開始メモリ・スロットの直後の前記第二所定数のメモリ・スロットの１つを占めていないのに応じて、前記アイテムが前記メモリ・コンテナ中に存在しないことの通知を前記アプリケーションに返させる、
請求項１８に記載のコンピュータ・プログラム。
【請求項２０】
プロセッサと、
前記プロセッサに連結されたメモリであって、前記メモリは、前記プロセッサによって実行されると前記プロセッサに、
前記メモリ・コンテナ中の或るアイテムを見出す要求をアプリケーションから受信するのに応じて、前記アイテムに対する開始メモリ・スロットを計算させ、
前記アイテムが前記開始メモリ・スロットを占めていないのに応じて、前記アイテムについて前記開始メモリ・スロットの直後の第一所定数のメモリ・スロットを探査させ、
前記アイテムが、前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの１つを占めているのに応じて、前記アイテムを前記アプリケーションに返させ、
前記アイテムが、前記開始メモリ・スロットの直後の前記第一所定数のメモリ・スロットの１つを占めていないのに応じて、前記第一所定数のメモリ・スロットの最後に関連付けてバリア・ビットが設定されているかどうかを判断させ、
前記バリア・ビットが設定されているのに応じて、前記アイテムについて前記メモリ・コンテナの少なくとも部分を探査し、前記メモリ・コンテナの前記部分に前記アイテムが見出されたのに応じて、前記アプリケーションに前記アイテムを返させ、且つ
前記バリア・ビットが設定されていないのに応じて、前記アイテムが前記メモリ・コンテナ中に存在しないことの通知を前記アプリケーションに返させる、
命令を含む、前記メモリと、
を含む装置。
【国際調査報告】
2020535510.tif 000010
2020535510.tif 000011