XORリンクリスト

XORリンク リストは、コンピュータ プログラミングで使用されるデータ構造の一種です。ビット単位の XOR演算を利用して、両方のアドレスの構成を 1 つのフィールドに格納することにより、二重リンク リストのストレージ要件を削減します。構成されたアドレスはそれ自体では意味がありませんが、トラバース中に、最後にアクセスしたノード アドレスの情報と組み合わせて、次のノードのアドレスを推測できます。

通常の二重リンク リストでは、各リスト ノードに前のリスト項目と次のリスト項目のアドレスが格納され、2 つのアドレス フィールドが必要になります。

... ABCDE ...
         –> 次へ –> 次へ –> 次へ –>
         <– 前 <– 前 <– 前 <–

XOR リンク リストは、前のアドレスと次のアドレスのビット単位の XOR (ここでは ⊕ で示される) を 1 つのフィールドに格納することにより、同じ情報を1 つのアドレス フィールドに圧縮します。

... ABCDE ...
         ⇌ A⊕C ⇌ B⊕D ⇌ C⊕E ⇌

より正式には:

  リンク(B) = addr(A)⊕addr(C)、リンク(C) = addr(B)⊕addr(D)、...

リストを左から右にトラバースする場合: カーソルが C にあると仮定すると、前の項目 B はリンク フィールドの値と XOR されます (B⊕D)。その後、D のアドレスが取得され、リストのトラバースが再開されます。同じパターンが逆方向に適用されます。

つまり addr(D) = link(C) ⊕ addr(B) 、

      リンク(C) = アドレス(B)⊕アドレス(D)

それで

      引数(D) = 引数(B)⊕引数(D) ⊕ 引数(B)           
  
      引数(D) = 引数(B)⊕引数(B) ⊕ 引数(D)

以来

       X⊕X = 0                 
       => addr(D) = 0 ⊕ addr(D)

以来

       X⊕0 = X
       => 追加(D) = 追加(D)

XOR 演算はaddr(B)式に 2 回出現するためキャンセルされ、 だけが残りますaddr(D)。

ある地点からリストをどちらの方向にも走査するには、連続する 2 つの項目のアドレスが必要です。連続する 2 つの項目のアドレスが逆の場合、リストの走査は逆方向に行われます。^[1]

重要なのは最初の演算と XOR のプロパティです。

• X⊕X = 0
• X⊕0 = X
• X⊕Y = Y⊕X
• (X⊕Y)⊕Z = X⊕(Y⊕Z)

R2 レジスタには、常に現在の項目 C のアドレスと先行項目 P のアドレスの XOR (C⊕P) が含まれます。レコードのリンク フィールドには、左と右の後続アドレスの XOR (L⊕R など) が含まれます。R2 (C⊕P) と現在のリンク フィールド (L⊕R) の XOR は、C⊕P⊕L⊕R になります。

• 先行者が L だった場合、P(=L) と L は打ち消され 、C⊕R が残ります。
• 先行者が R だった場合、P(=R) と R はキャンセルされ、C⊕L が残ります。

いずれの場合も、結果は現在のアドレスと次のアドレスの XOR です。これを R1 の現在のアドレスと XOR すると、次のアドレスが残ります。R2 には、(現在の) 現在のアドレスと前のアドレスの必要な XOR ペアが残ります。

• 1 つの項目から次の項目へのトラバースを行うには、2 つの XOR 演算で十分です。どちらの場合も同じ命令で十分です。項目のあるリストを考えてみましょう{…B C D…}。R1 と R2 はそれぞれ現在のリスト項目 (C とします) のアドレスを含むレジスタと、現在のアドレスと前のアドレス (C⊕D とします) の XOR を含む作業レジスタです。System /360命令としてキャストします。

X R2,Link R2 <- C⊕D ⊕ B⊕D （つまりB⊕C、「Link」はリンクフィールド）
                                  現在のレコードにはB⊕Dが含まれています）
XR R1,R2 R1 <- C ⊕ B⊕C (つまり B、次のレコード)

• リストの終わりは、アドレス 0 のリスト項目がエンドポイントに隣接して配置されていることを想定することで示されます (図{0 A B C…}1 を参照)。A のリンク フィールドは 0⊕B になります。上記のシーケンスでは、2 つの XOR 演算の後に、現在の項目のアドレスを生成する際にゼロの結果を検出するために追加の命令が必要です。
• リストのエンドポイントは、リンク ポインタを 0 にすることで反射的にすることができます。ゼロ ポインタはミラーです。 (左と右の隣接アドレスの XOR は同じなので、ゼロになります。)

• 汎用デバッグツールはXORチェーンをたどることができないため、デバッグが困難になります。^[2]
• メモリ使用量の減少の代償として、コードの複雑さが増し、メンテナンスのコストが高くなります。
• ほとんどのガベージ コレクションスキームは、リテラルポインタを含まないデータ構造では機能しません。
• すべての言語がポインタと整数間の型変換をサポートしているわけではなく、ポインタの XOR は一部のコンテキストでは定義されていません。
• リストをトラバースする際、次のノードのアドレスを計算するために、以前にアクセスしたノードのアドレスが必要となり、リストをトラバースしていない場合、ポインターは読み取り不可能になります (たとえば、リスト項目へのポインターが別のデータ構造に含まれていた場合)。
• XOR リンク リストでは、アドレスのみわかっている場合にリストからノードを削除する機能や、既存のノードのアドレスのみわかっている場合に既存のノードの前または後に新しいノードを挿入する機能など、二重リンク リストの重要な利点の一部が提供されません。

コンピュータ システムのメモリはますます安価で豊富になっているため、特殊な組み込みシステム以外では、ストレージのオーバーヘッドは一般に大きな問題ではありません。リンク リストのオーバーヘッドを削減することが依然として望ましい場合は、アンローリングがより実用的なアプローチを提供します (キャッシュ パフォーマンスの向上やランダム アクセスの高速化など、他の利点もあります)。

XOR リンク リストの基本原理は、あらゆる可逆なバイナリ演算に適用できます。XOR を加算または減算に置き換えると、若干異なりますが、ほぼ同等の定式化が得られます。

... ABCDE ...
          ⇌ A+C ⇌ B+D ⇌ C+E ⇌

この種のリストは、ゼロ リンク フィールドが「ミラー」ではないことを除いて、XOR リンク リストとまったく同じプロパティを持ちます。リスト内の次のノードのアドレスは、現在のノードのリンク フィールドから前のノードのアドレスを減算することによって得られます。

... ABCDE ...
          ⇌ カナダ ⇌ ドイツ ⇌ EC ⇌

この種のリストは、リストを順方向にトラバースするために必要な命令シーケンスが、リストを逆方向にトラバースするために必要なシーケンスと異なるという点で、標準の「従来の」XOR リンク リストとは異なります。順方向の次のノードのアドレスは、前のノードのアドレスにリンク フィールドを追加することによって得られます。前のノードのアドレスは、次のノードのアドレスからリンク フィールドを減算することによって得られます。

減算リンク リストは、リスト内の各アドレスに定数オフセットを追加してもリンク フィールドに格納されている値を変更する必要がないため、ポインター値のパッチを必要とせずにリスト全体をメモリ内で再配置できるという点でも特別です。(シリアル化も参照してください。) これは、XOR リンク リストと従来のリンク リストの両方に対する利点です。

XORリンクリストの概念は、XOR二分探索木に一般化することができます。^[3]

• XORスワップアルゴリズム

• Prokash Sinha (2004 年 12 月 1 日)。「メモリ効率に優れた二重リンク リスト」。Linux Journal。
• XORList: 効率的な C++ リンク リスト (MIT ライセンス)
• ライブラリ Listes での C++ での Xor リストの実装。