今回は Rust のビット操作について説明します。
Rust のビット演算子を下表に示します。
| 演算子 | 操作 |
|---|---|
| x & y | ビットごとの論理積 |
| x | y | ビットごとの論理和 |
| x ^ y | ビットごとの排他的論理和 |
| !x | ビットごとの否定 (Ｃ言語の ~ と同じ) |
| x << y | x を y ビット左シフト |
| x >> y | x を y ビット右シフト |
演算子 & はビットごとの論理積を返します。
5 & 3 => 1
0101
AND 0011
---------
0001
演算子 | はビットごとの論理和を返します。
5 | 3 => 7
0101
OR 0011
--------
0111
演算子 ^ はビットごとの排他的論理和を返します。
5 ^ 3 => 6
0101
XOR 0011
---------
0110
演算子 ! はビットごとの論理的な否定を返します。
!1 => -2 !0 => -1
<<, >> はビットをシフトする演算子です。左シフトの場合、下位ビットには 0 が挿入されます。右シフトの場合、正の整数 (または無符号整数) では上位ビットに 0 が挿入されます。負の整数では 1 が挿入されます。これを「算術シフト」といいます。
1 << 8 => 256 1 << 16 => 65536 256 >> 8 => 1 65536 >> 8 => 256 -256 >> 8 => -1
それでは簡単な例題として、基本的なビット操作関数を作ってみましょう。次のリストを見てください。
リスト : 基本的なビット操作
fn test_bit(x: i32, n: i32) -> bool {
x & (1 << n) != 0
}
fn set_bit(x: i32, n: i32) -> i32 {
x | (1 << n)
}
fn clear_bit(x: i32, n: i32) -> i32 {
x & !(1 << n)
}
fn main() {
println!("{}", test_bit(256, 7));
println!("{}", test_bit(256, 8));
println!("{}", test_bit(256, 9));
for i in 0 .. 8 {
let x = set_bit(0, i);
println!("{}", x);
println!("{}", clear_bit(x, i));
}
}
test_bit() は整数 x の n 番目のビットが 1 ならば true を返します。最下位 (LSB) のビットが 0 番目になります。i32 の場合、n は 0 から 31 になります。1 を n ビット左シフトして、x との論理積が 0 でなければ、n 番目のビットは 1 であることがわかります。
bit_set() は x の n 番目のビットを 1 にセットします。1 を n ビット左シフトして、x との論理和を計算すれば、n 番目のビットを 1 にすることができます。clear_bit() は x の n 番目のビットを 0 にクリアします。これは n 番目以外のビットを 1 に、n 番目のビットを 0 にして、それと x の論理積を計算すれば、n 番目のビットをクリアすることができます。1 を n ビット左シフトして、その否定を計算すると、n 番目のビット以外は 1 になります。
それでは実際に試してみましょう。
false true false 1 0 2 0 4 0 8 0 16 0 32 0 64 0 128 0
組み合わせの生成は拙作のページで取り上げました。このほかに、n 個の中から m 個を選ぶ組み合わせは、ビットの 0, 1 で表すことができます。たとえば、5 個の数字 (0 - 4) から 3 個を選ぶ場合、数字を 0 番目 から 4 番目のビットに対応させます。すると、1, 3, 4 という組み合わせは 11010 と表すことができます。簡単な例題として、ビットを使って組み合わせを求めてみましょう。
組み合わせを求めるプログラムは次のようになります。
リスト : 組み合わせの生成
fn combinations(n: i32, m: i32, func: &dyn Fn(i32) -> ()) {
fn comb_sub(n: i32, m: i32, a: i32, func: &dyn Fn(i32) -> ()) {
if m == 0 {
func(a);
} else if m == n {
func(a | ((1 << m) - 1));
} else {
comb_sub(n - 1, m, a, func);
comb_sub(n - 1, m - 1, a | (1 << (n - 1)), func);
}
}
comb_sub(n, m, 0, func);
}
fn main() {
combinations(5, 3, &|x| println!("{:x}", x));
}
関数 combinations() は n 個の中から m 個を選ぶ組み合わせを生成して、引数の関数 func() に渡します。実際の処理は関数 comb_sub() で行います。組み合わせは引数 a にセットします。m が 0 になったら、組み合わせがひとつできたので func(a) を呼び出します。n が m と等しくなったならば、残り m 個を全て選びます。(1 << m) - 1 で m 個のビットをオンにして関数 func() を呼び出します。
あとは comb_sub() を再帰呼び出しします。最初の呼び出しは n 番目の数字を選ばない場合です。n - 1 個の中から m 個を選びます。次の呼び出しが n 番目の数字を選ぶ場合で、a の n - 1 番目のビットをオンにします。そして、n - 1 個の中から m - 1 個を選びます。
それでは 5 個の中から 3 個を選ぶ combinations(5, 3) の実行例を示します。
7 b d e 13 15 16 19 1a 1c
この場合、最小値は 0x07 (111) で最大値は 0x1c (11100) になります。このように、combinations() は組み合わせを表す数を昇順で出力します。
次は、N 通りある組み合わせに 0 から N - 1 までの番号を付ける方法を紹介しましょう。たとえば、6 個の中から 3 個を選ぶ組み合わせは 20 通りありますが、この組み合わせに 0 から 19 までの番号を付けることができます。1 1 1 0 0 0 を例題に考えてみましょう。次の図を見てください。
5 4 3 2 1 0
─────────
0 0 0 1 1 1 ↑
0 0 1 0 1 1 │
0 0 1 1 0 1 │
0 0 1 1 1 0 │
0 1 0 0 1 1 │
0 1 0 1 0 1 5Ｃ3 = 10 通り
0 1 0 1 1 0 │
0 1 1 0 0 1 │
0 1 1 0 1 0 │
0 1 1 1 0 0 ↓
─────────
1 0 0 0 1 1 ↑
1 0 0 1 0 1 │
1 0 0 1 1 0 │
1 0 1 0 0 1 4Ｃ2 = 6 通り
1 0 1 0 1 0 │
1 0 1 1 0 0 ↓
────────
1 1 0 0 0 1 ↑
1 1 0 0 1 0 3Ｃ1 = 3 通り
1 1 0 1 0 0 ↓
───────
1 1 1 0 0 0 19 番目
─────────
図 : 6Ｃ3 の組み合わせ
最初に 5 をチェックします。5 を選ばない場合は \({}_5 \mathrm{C}_3\) = 10 通りありますね。この組み合わせに 0 から 9 までの番号を割り当てることにすると、5 を選ぶ組み合わせの番号は 10 から 19 までとなります。
次に、4 をチェックします。4 を選ばない場合は、\({}_4 \mathrm{C}_2\) = 6 通りあります。したがって、5 を選んで 4 を選ばない組み合わせに 10 から 15 までの番号を割り当てることにすると、5 と 4 を選ぶ組み合わせには 16 から 19 までの番号となります。
最後に、3 をチェックします。同様に 3 を選ばない場合は 3 通りあるので、これに 16 から 18 までの番号を割り当て、5, 4, 3 を選ぶ組み合わせには 19 を割り当てます。これで組み合わせ 1 1 1 0 0 0 の番号を求めることができました。
では、0 0 0 1 1 1 はどうなるのでしょうか。左から順番にチェックしていくと、最初の 1 が見つかった時点で、その数字を選ばない組み合わせは存在しません。つまり、残りの数字をすべて選ぶしかないわけです。したがって、これが 0 番目となります。
このように、数字を選ぶときに、数字を選ばない場合の組み合わせの数を足し算していけば、その組み合わせの番号を求めることができるのです。
組み合わせを番号に変換するプログラムは次のようになります。
リスト : 組み合わせを番号に変換
// 組み合わせの数
fn comb_num(n: i32, r: i32) -> i32 {
if n == r || r == 0 {
1
} else {
comb_num(n, r - 1) * (n - r + 1) / r
}
}
// 組み合わせを番号に変換
fn comb_to_num(c: i32, n: i32, r: i32) -> i32 {
fn comb_to_num_sub(c: i32, n: i32, r: i32, value: i32) -> i32 {
if r == 0 || n == r {
value
} else if test_bit(c, n - 1) {
comb_to_num_sub(c, n - 1, r - 1, value + comb_num(n - 1, r))
} else {
comb_to_num_sub(c, n - 1, r, value)
}
}
comb_to_num_sub(c, n, r, 0)
}
関数 comb_num() は組み合わせの数を求めます。comb_to_num() の引数 c はビットのオンオフで表した組み合わせ、引数 n と r は \({}_n \mathrm{C}_r\) の n と r を表しています。実際の処理は comb_to_num_sub() で行います。引数 value は求める番号を表します。n と r の値が同じになるか、もしくは r が 0 になれば、組み合わせの番号を計算できたので value を返します。
そうでない場合、c の n - 1 ビットの値を調べます。ビットがオンであれば、value に comb_num(n - 1, r) の値を足し算し、r を -1 して comb_to_num_sub() を再帰呼び出しします。そうでなければ、value と r の値はそのままで comb_to_num_sub() を再帰呼び出しします。
逆に、番号から組み合わせを求めるプログラムも簡単に作ることができます。次のリストを見てください。
リスト : 番号を組み合わせに変換
fn num_to_comb(value:i32, n: i32, r: i32) -> i32 {
fn num_to_comb_sub(value: i32, n: i32, r: i32, c: i32) -> i32 {
if r == 0 {
c
} else if n == r {
c | ((1 << n) - 1)
} else {
let k = comb_num(n - 1, r);
if value >= k {
num_to_comb_sub(value - k, n - 1, r - 1, set_bit(c, n - 1))
} else {
num_to_comb_sub(value, n - 1, r, c)
}
}
}
num_to_comb_sub(value, n, r, 0)
}
引数 value が番号で、引数 n と r は \({}_n \mathrm{C}_r\) の n と r を表しています。実際の処理は num_to_comb_sub() で行います。引数 c が求める組み合わせです。たとえば、n = 5, r = 3 の場合、ビットが 1 になるのは \({}_4 \mathrm{C}_2\) = 6 通りあり、0 になるのは \({}_4 \mathrm{C}_3\) = 4 通りあります。したがって、数値が 0 - 3 の場合はビットを 0 にし、4 - 9 の場合はビットを 1 にすればいいわけです。
ビットを 0 にした場合、残りは \({}_4 \mathrm{C}_3\) = 4 通りになるので、同様に次のビットを決定します。ビットを 1 にした場合、残りは \({}_4 \mathrm{C}_2\) = 6 通りになるので、value から 4 を引いて num_to_comb_sub() を再帰呼び出しして次のビットを決定します。
r が 0 の場合は、組み合わせが完成したので c を返します。n と r が等しい場合は、残りのビットをすべて 1 にセットしてから c を返します。それ以外の場合は、\({}_{n-1} \mathrm{C}_r\) の値を comb_num(n - 1, r) で求めて変数 k にセットします。value が k 以上であれば変数 c のビットを 1 にセットし、value から k を引き算して num_to_comb_sub() を再帰呼び出しします。そうでなければ、num_to_comb_sub() を再帰呼び出しするだけです。
それでは、n = 5, r = 3 の場合の実行例を示します。
リスト : 簡単なテスト
fn main() {
for i in 0 .. 10 {
let c = num_to_comb(i, 5, 3);
println!("{} => {:x} => {}", i, c, comb_to_num(c, 5, 3));
}
}
0 => 7 => 0 1 => b => 1 2 => d => 2 3 => e => 3 4 => 13 => 4 5 => 15 => 5 6 => 16 => 6 7 => 19 => 7 8 => 1a => 8 9 => 1c => 9
正常に動作していますね。この方法を使うと、n 個ある組み合わせの中の i 番目 (0 <= i < n) の組み合わせを簡単に求めることができます。
最も右側 (LSB 側) にある 1 を 0 にクリアする、逆に最も右側にある 0 を 1 にセットすることは簡単にできます。
(1) 右側にある 1 をクリア => x & (- x) x : 1 1 1 1 x - 1 : 1 1 1 0 ---------------- AND : 1 1 1 0 x : 1 0 0 0 x - 1 : 0 1 1 1 ---------------- AND : 0 0 0 0 (2) 右側にある 0 を 1 にセット => x | (x + 1) x : 0 0 0 0 x + 1 : 0 0 0 1 ---------------- OR : 0 0 0 1 x : 0 1 1 1 x - 1 : 1 0 0 0 ---------------- OR : 1 1 1 1
上図 (1) を見てください。x から 1 を引くと、右側から連続している 0 は桁借りにより 1 になり、最初に出現する 1 が 0 になります。したがって、x & (x - 1) を計算すると、最も右側にある 1 を 0 にクリアすることができます。
(2) の場合、x に 1 を足すと、右側から連続している 1 は桁上がりにより 0 になり、最初に出現する 0 が 1 になります。x | (x + 1) を計算すれば、最も右側にある 0 を 1 にセットすることができます。
また、最も右側にある 1 を取り出すことも簡単にできます。簡単な例として 4 ビットの整数値を考えてみます。負の整数を 2 の補数で表した場合、4 ビットで表される整数は -8 から 7 になります。次の図を見てください。
0 : 0000
1 : 0001 -1 : 1111 1 & (-1) => 0001
2 : 0010 -2 : 1110 2 & (-2) => 0010
3 : 0011 -3 : 1101 3 & (-3) => 0001
4 : 0100 -4 : 1100 4 & (-4) => 0100
5 : 0101 -5 : 1011 5 & (-5) => 0001
6 : 0110 -6 : 1010 6 & (-6) => 0010
7 : 0111 -7 : 1001 7 & (-7) => 0001
-8 : 1000
図 : 最も右側にある 1 を取り出す方法
2 の補数はビットを反転した値 (1 の補数) に 1 を加算することで求めることができます。したがって、x と -x の論理積 x & (-x) は、最も右側にある 1 だけが残り、あとのビットはすべて 0 になります。
Rust にはビットが 1 の個数を求めるメソッド count_ones() と、0 の個数を求めるメソッド count_zeros() が用意されています。
fn count_ones(self) -> u32 fn count_zeros(self) -> u32
ここではビット操作の簡単な例題として、ビットが 1 の個数を求めるプログラムを作ってみましょう。データ型を u32 とすると、プログラムは次のようになります。
リスト : ビットカウント
fn bit_count(n: u32) -> u32 {
let mut c = 0;
let mut m = n;
while m != 0 {
m &= m - 1;
c += 1;
}
c
}
整数 n の右側から順番に 1 をクリアしていき、0 になるまでの回数を求めます。とても簡単ですね。32 個のビットを順番に調べるよりも高速です。また、次の方法で 1 の個数をもっと高速に求めることができます。
リスト : ビットカウント (2)
fn bit_count1(n: u32) -> u32 {
let a = (n & 0x55555555) + ((n >> 1) & 0x55555555);
let b = (a & 0x33333333) + ((a >> 2) & 0x33333333);
let c = (b & 0x0f0f0f0f) + ((b >> 4) & 0x0f0f0f0f);
let d = (c & 0x00ff00ff) + ((c >> 8) & 0x00ff00ff);
(d & 0xffff) + (d >> 16)
}
最初に、整数を 2 bit ずつに分割して、1 の個数を求めます。たとえば、整数 n を 4 bit で考えてみましょう。5 を 2 進数で表すと 0101 になり、n と論理積を計算すると 0, 2 番目のビットが 1 であれば、結果の 0, 2 番目のビットは 1 になります。同様に n を 1 ビット右シフトして論理積を計算すると、1, 3 番目のビットが 1 であれば、結果の 0, 2 番目のビットは 1 になります。あとは、それを足し算すれば 2 bit の中にある 1 の個数を求めることができます。
変数 a には 2 ビットの中の 1 の個数が格納されています。左隣の 2 ビットの値を足し算すれば、4 ビットの中の 1 の個数を求めることができます。次に、左隣の 4 ビットの値を足し算して 8 ビットの中の 1 の個数を求め、左隣の 8 ビットの値を足し算して、というように順番に値を加算していくと 32 ビットの中にある 1 の個数を求めることができます。
bit_count() は 1 の個数が多くなると遅くなりますが、bit_count1() は 1 の個数に関係なく高速に動作します。興味のある方は実際に試してみてください。
最後に、ビット操作を使った高速化の例として N Queens Problem を取り上げます。アルゴリズムの詳しい説明は拙作のページ「お気楽Ｃ言語超入門: N Queens Problem」をお読みください。
プログラムと実行結果を示します。
リスト : N Queens Problem の高速化
use std::time::Instant;
static mut CNT: i32 = 0;
// 衝突の検出
fn attack(q: i32, qs: &Vec<i32>) -> bool {
let mut i = qs.len();
let mut d = 1;
while i > 0 {
if q + d == qs[i - 1] || q - d == qs[i - 1] { return true; }
i -= 1;
d += 1;
}
false
}
// N Queens Problem の解法
fn nqueens(n: i32) {
fn queen_sub(n: i32, qs: &mut Vec<i32>) {
if n == qs.len() as i32 {
unsafe { CNT += 1; }
} else {
for q in 1 .. n + 1 {
if !qs.contains(&q) && !attack(q, qs) {
qs.push(q);
queen_sub(n, qs);
qs.pop();
}
}
}
}
queen_sub(n, &mut vec![]);
}
// ビット操作による高速化
fn nqueens1(n: i32, right: i32, left: i32) {
if n == 0 {
unsafe { CNT += 1; }
} else {
let mut m = n;
while m > 0 {
let q = m & (-m);
if (q & (right | left)) == 0 {
nqueens1(n ^ q, (right | q) << 1, (left | q) >> 1);
}
m &= m - 1;
}
}
}
fn main() {
for n in 10 .. 16 {
let s = Instant::now();
unsafe { CNT = 0; }
nqueens(n);
unsafe { println!("{}", CNT); }
let e = s.elapsed();
println!("{}.{:03}秒経過しました。", e.as_secs(), e.subsec_nanos() / 1_000_000);
let s1 = Instant::now();
unsafe { CNT = 0; }
nqueens1((1 << n) - 1, 0, 0);
unsafe { println!("{}", CNT); }
let e1 = s1.elapsed();
println!("{}.{:03}秒経過しました。", e1.as_secs(), e1.subsec_nanos() / 1_000_000);
}
}
724 0.005秒経過しました。 724 0.000秒経過しました。 2680 0.028秒経過しました。 2680 0.003秒経過しました。 14200 0.153秒経過しました。 14200 0.018秒経過しました。 73712 0.855秒経過しました。 73712 0.094秒経過しました。 365596 5.295秒経過しました。 365596 0.548秒経過しました。 2279184 34.935秒経過しました。 2279184 3.437秒経過しました。 実行環境 : Rust 1.83.0, Ubunts 22.04 (WSL2), Intel Core i5-6200U 2.30GHz
ビットが 1 の個数を数える方法はフィンローダさんの『初級Ｃ言語Ｑ＆Ａ(15)』を参考にさせていただきました。フィンローダさんに感謝いたします。
連結リストは要素を一列に並べたデータ構造ですが、最後尾のセルと先頭のセルを連結することで要素をリング状に並べることができます。これを「循環リスト (circular list)」 といいます。次の図を見てください。
Cell の cdr を直接 Cell A に書き換える
└─────┐
Cell A ↓
car cdr car cdr car cdr
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
変数─→│・│・┼─→│・│・┼─→│・│／│
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓
１ ２ ３
┌───────────────┐
↓ │
┌─┬─┐ ┌─┬─┐ ┌─┬┼┐
変数─→│・│・┼─→│・│・┼─→│・│・│
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓
１ ２ ３
図 : 循環リスト
上図の連結リスト (1 2 3) は None で終端されています。この連結リストで、最後尾のセルの cdr を先頭のセル A に書き換えると、循環リストを作ることができます。循環リストは環状に並んだデータを表すのに便利なデータ構造です。
それでは簡単な例題として、循環リストを使って「キュー (queue)」を実装してみましょう。拙作のページ「キュー (連結リスト)」で作成したキューの構造は次のようになっています。
rear ─→ None
front ─→ None
(1) キューが空の状態
rear ─────────────────────┐
↓
┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
front ─→│・│・┼→│・│・┼→│・│・┼→│・│・┼→ None
└┼┴─┘ └┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓ ↓
data1 data2 data3 data4
(2) キューにデータがある場合
図 : 連結リストによるキューの構造
先頭のセルを参照する変数 front のほかに、最後尾のセルを参照する変数 rear を用意します。キューにデータがない場合は、(1) のように front と rear は None になっています。データがある場合は、(2) のように front は先頭のセルを参照し、rear は最後尾のセルを参照しています。これで、データの追加を効率的に行うことができます。
循環リストの場合、最後尾のセルを参照する変数 rear を用意するだけでキューを実現することができます。下図を見てください。
rear ─→ None
(1) キューが空の状態
rear ───┐
↓
┌─┬─┐
┌─→│・│・┼─┐
│ └┼┴─┘ │
│ ↓ │
│ data1 │
│ │
└────────┘
(2) キューにデータが一つある場合
rear ─────────────────────┐
↓
┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
┌─→│・│・┼→│・│・┼→│・│・┼→│・│・┼─┐
│ └┼┴─┘ └┼┴─┘ └┼┴─┘ └┼┴─┘ │
│ ↓ ↓ ↓ ↓ │
│ data1 data2 data3 data4 │
│ │
└──────────────────────────┘
(3) キューに複数のデータがある場合
図 : 循環リストによるキューの構造
循環リストの場合、最後尾のセルの次のセルが先頭になります。(3) を見てください。循環リストの場合、rear が参照する最後尾のセルの cdr は None ではありません。cdr が参照するセルがキューの先頭になるのです。
データが一つしかない場合、(2) のように rear が参照するセルの cdr は自分自身を参照しています。つまり、このセルが先頭であり最後尾でもあるわけです。キューにデータがない場合、rear の値は (1) のように None になります。
それでは、プログラムを作りましょう。最初に作成するメソッドを表に示します。
| 名前 | 機能 |
|---|---|
| fn new(n: usize) -> Queue<T> | 指定した大きさのキューを作る (コンストラクタ) |
| fn dequeue(&mut self) -> Option<T> | キューからデータを取り出して返す |
| fn enqueue(&mut self, x: T) -> bool | キューにデータを追加する |
| fn front(&self) -> Option<&T> | キューの先頭データの参照を返す |
| fn is_empty(&self) -> bool | キューが空の場合は true を、そうでなければ false を返す |
| fn is_full(&self) -> bool | キューが満杯の場合は true を、そうでなければ false を返す |
| fn len(&self) -> usize | キューに格納されたデータ数を返す |
| fn clear(&mut self) | キューを空にする |
次はデータ構造を定義します。
リスト : 循環リストによるキューの実装
use std::rc::Rc;
use std::cell::UnsafeCell;
// 連結リスト
struct List<T> {
car: T,
cdr: Link<T>
}
type Link<T> = Option<Rc<UnsafeCell<List<T>>>>;
// 循環リストによるキューの実装
struct Queue<T> {
rear: Link<T>,
size: usize
}
// メソッド
impl<T> Queue<T> {
// キューの生成
fn new() -> Queue<T> {
Queue { rear: None, size: 0 }
}
// メソッドの定義 (省略)
}
末尾のセルは Queue の rear と一つ手前のセルの 2 カ所から参照されるので、Box<T> ではなく Rc<T> を使う必要があります。それから、拙作のページ「キュー (連結リスト)」では RefCell<T> を使いましたが、メソッド front() でライフタイムのコンパイルエラーを解決できなかったので、今回は UnsafeCell<T> を使うことにしました。
次はデータを追加するメソッド enqueue() を作ります。
リスト : データの追加
fn enqueue(&mut self, item: T) {
let new_node = Rc::new(UnsafeCell::new(List { car: item, cdr: None }));
match self.rear.take() {
None => unsafe {
let p = new_node.get();
(*p).cdr = Some(new_node.clone());
},
Some(tail_node) => unsafe {
let p = tail_node.get();
let head_node = (*p).cdr.take();
let q = new_node.get();
(*q).cdr = head_node;
(*p).cdr = Some(new_node.clone());
}
}
self.rear = Some(new_node);
self.size += 1;
}
最初にデータ item を格納したセルを生成して変数 new_node にセットします。次に、self.rear.take() で末尾のセルを取り出します。None の場合、キューは空なので new_node をキューに追加します。ここで、new_node の cdr を自分自身に書き換えます。UnsafeCell の場合、メソッド get() で格納しているデータへの生ポインタを取得することができます。
fn get(&self) -> *mut T
Rc には Deref が実装されているので、new_node.get() で生ポインタを取得することができます。それを変数 p にセットすると、List<T> のフィールド car, cdr は (*p).car, (*p).cdr でアクセスすることができます。(*p).cdr に値をセットするときは、new_node を clone() することをお忘れなく。最後に、self.rear に new_node をセットします。
末尾のセル (tail_node) がある場合、その後ろに new_node を追加します。tail_node の生ポインタを取得して変数 p に、new_node の生ポインタを変数 q にセットします。次に、(*p).cdr.take() で先頭セル (head_node) を取得して (*q).cdr にセットします。これで new_node の後ろに head_node をつなぐことができます。あとは、(*p).cdr に Some(new_node.clone()) をセットすれば、head_node と tail_node の間に new_node を挿入することができます。
次はデータを取り出すメソッド dequeue() を作ります。
リスト : データの取り出し
fn dequeue(&mut self) -> Option<T> {
if self.size == 0 {
None
} else {
self.size -= 1;
if self.size == 0 {
self.rear.take().map(|node| unsafe {
let p = node.get();
(*p).cdr = None;
match Rc::try_unwrap(node) {
Ok(node) => node.into_inner().car,
Err(_) => panic!("dequeue error")
}
})
} else {
self.rear.as_mut().map(|tail| unsafe {
let p = tail.get();
(*p).cdr.take().map(|head| {
let q = head.get();
(*q).cdr.take().map(|next| {
(*p).cdr = Some(next);
});
match Rc::try_unwrap(head) {
Ok(node) => node.into_inner().car,
Err(_) => panic!("dequeue error")
}
})
}).unwrap()
}
}
}
キューが空の場合は None を返します。そうでなければ、self.size を -1 して先頭セルからデータを取り出します。self.size が 0 の場合、キューは空になりました。self.rear.take().map() で末尾セル (node) を取り出します。このとき node の参照カウンタは 2 なので、node の cdr を None に書き換えて参照カウンタを 1 にします。そして、try_unwrap() で Rc からデータを取り出し、メソッド into_inner() で UnsafeCell からセルを取り出して、その要素 car を返します。into_inner() は UnsafeCell に格納しているデータを move することに注意してください。
unsafe fn into_inner(self) -> T
キューが空にならない場合は先頭セルを取り除きます。最初に、self.rear.as_mut().map() で末尾セル (tail) を求めます。self.rear の値はそのままでよいので、mutable な参照を取得していることに注意してください。次に、tail の生ポインタを変数 p にセットします。すると、先頭セル (head) は (*p).cdr take().map() で取り出すことができます。
そのあと、head の生ポインタを変数 q にセットし、(*q).cdr.take().map() で head の次のセル next を取得します。そして、末尾セル tail の cdr を next に書き換えます。これで head を連結リストから削除することができます。最後に、head から要素を取り出します。map() を二重に使っているので、このままでは返り値が Option<Option<T>> になってしまいます。unwrap() で Option を一つはがしていることに注意してください。
なお、データが 2 つしかない場合、next は tail と同じセルになるので、tail の cdr は自分自身を指し示すことになります。これで正常に動作します。
次はメソッド front() を作ります。
リスト : 先頭要素の参照を返す
fn front(&self) -> Option<&T> {
if self.size == 0 {
None
} else if self.size == 1 {
self.rear.as_ref().map(|node| unsafe {
let p = node.get();
&((*p).car)
})
} else {
self.rear.as_ref().map(|node| unsafe {
let p = node.get();
(*p).cdr.as_ref().map(|head| {
let q = head.get();
&((*q).car)
})
}).unwrap()
}
}
self.size が 0 の場合は None を返します。self.size が 1 の場合は末尾セルが先頭セルなので、self.rear が格納している要素 car の参照を返します。それ以外の場合は末尾セル (node) から先頭セル (head) を求め、head が格納している要素 car の参照を返します。
ところで、最初は UnsafeCell のかわりに RefCell を使いました。この場合、node.borrow() ... とプログラムすることになるのですが、node.borrow() でライフタイム関連のコンパイルエラーが発生し、それを解決することができませんでした。Rust のライフタイムは難しいですね。Rust で木構造やグラフなどのデータ構造を操作する場合、unsafe な処理を使うのはやむを得ないのかもしれません。
あとのメソッドは簡単なので説明は省略します。詳細はプログラムリストをお読みください。
それでは実際に実行してみましょう。次に示す簡単なテストを行ってみました。
リスト : 簡単なテスト
fn main() {
let mut que = Queue::new();
println!("{}", que.is_empty());
println!("{}", que.is_full());
println!("{}", que.len());
for i in 0 .. 5 {
que.enqueue(i);
}
println!("{}", que.is_empty());
println!("{}", que.is_full());
println!("{}", que.len());
while !que.is_empty() {
println!("{:?}", que.front());
println!("{:?}", que.dequeue());
}
println!("{}", que.is_empty());
println!("{}", que.is_full());
println!("{}", que.len());
for i in 0 .. 10 {
que.enqueue(i + 10);
}
println!("{}", que.is_empty());
println!("{}", que.is_full());
println!("{}", que.len());
for _ in 0 .. 8 {
println!("{:?}", que.front());
println!("{:?}", que.dequeue());
}
println!("{}", que.is_empty());
println!("{}", que.is_full());
println!("{}", que.len());
que.clear();
println!("{}", que.is_empty());
println!("{}", que.is_full());
println!("{}", que.len());
}
実行結果は次のようになります。
true false 0 false false 5 Some(0) Some(0) Some(1) Some(1) Some(2) Some(2) Some(3) Some(3) Some(4) Some(4) true false 0 false false 10 Some(10) Some(10) Some(11) Some(11) Some(12) Some(12) Some(13) Some(13) Some(14) Some(14) Some(15) Some(15) Some(16) Some(16) Some(17) Some(17) false false 2 true false 0
正常に動作しているようです。興味のある方はいろいろ試してみてください。
//
// queue2.rs : 循環リストによるキューの実装
//
// Copyright (C) 2017-2024 Makoto Hiroi
//
use std::rc::Rc;
use std::cell::UnsafeCell;
// 連結リスト
struct List<T> {
car: T,
cdr: Link<T>
}
type Link<T> = Option<Rc<UnsafeCell<List<T>>>>;
// 循環リストによるキューの実装
struct Queue<T> {
rear: Link<T>,
size: usize
}
// キューのメソッド
impl<T> Queue<T> {
// キューの生成
fn new() -> Queue<T> {
Queue { rear: None, size: 0 }
}
// データの追加
fn enqueue(&mut self, item: T) {
let new_node = Rc::new(UnsafeCell::new(List { car: item, cdr: None }));
match self.rear.take() {
None => unsafe {
let p = new_node.get();
(*p).cdr = Some(new_node.clone());
},
Some(tail_node) => unsafe {
let p = tail_node.get();
let head_node = (*p).cdr.take();
let q = new_node.get();
(*q).cdr = head_node;
(*p).cdr = Some(new_node.clone());
}
}
self.rear = Some(new_node);
self.size += 1;
}
// 先頭からデータを取り出す
fn dequeue(&mut self) -> Option<T> {
if self.size == 0 {
None
} else {
self.size -= 1;
if self.size == 0 {
self.rear.take().map(|node| unsafe {
let p = node.get();
(*p).cdr = None;
match Rc::try_unwrap(node) {
Ok(node) => node.into_inner().car,
Err(_) => panic!("dequeue error")
}
})
} else {
self.rear.as_mut().map(|tail| unsafe {
let p = tail.get();
(*p).cdr.take().map(|head| {
let q = head.get();
(*q).cdr.take().map(|next| {
(*p).cdr = Some(next);
});
match Rc::try_unwrap(head) {
Ok(node) => node.into_inner().car,
Err(_) => panic!("dequeue error")
}
})
}).unwrap()
}
}
}
// 先頭要素の参照を返す
fn front(&self) -> Option<&T> {
if self.size == 0 {
None
} else if self.size == 1 {
self.rear.as_ref().map(|node| unsafe {
let p = node.get();
&((*p).car)
})
} else {
self.rear.as_ref().map(|node| unsafe {
let p = node.get();
(*p).cdr.as_ref().map(|head| {
let q = head.get();
&((*q).car)
})
}).unwrap()
}
}
// キューの要素数を返す
fn len(&self) -> usize { self.size }
// キューは空か？
fn is_empty(&self) -> bool { self.size == 0 }
// キューは満杯か？ (常に false を返す)
fn is_full(&self) -> bool { false }
// キューを空にする
fn clear(&mut self) {
match self.rear.take() {
None => (),
Some(tail) => unsafe {
let p = tail.get();
(*p).cdr = None;
self.size = 0;
}
}
}
}
// Queue を drop するときは連結リストも drop する
impl<T> Drop for Queue<T> {
fn drop(&mut self) { self.clear(); }
}
// 簡単なテスト
fn main() {
let mut que = Queue::new();
println!("{}", que.is_empty());
println!("{}", que.is_full());
println!("{}", que.len());
for i in 0 .. 5 {
que.enqueue(i);
}
println!("{}", que.is_empty());
println!("{}", que.is_full());
println!("{}", que.len());
while !que.is_empty() {
println!("{:?}", que.front());
println!("{:?}", que.dequeue());
}
println!("{}", que.is_empty());
println!("{}", que.is_full());
println!("{}", que.len());
for i in 0 .. 10 {
que.enqueue(i + 10);
}
println!("{}", que.is_empty());
println!("{}", que.is_full());
println!("{}", que.len());
for _ in 0 .. 8 {
println!("{:?}", que.front());
println!("{:?}", que.dequeue());
}
println!("{}", que.is_empty());
println!("{}", que.is_full());
println!("{}", que.len());
que.clear();
println!("{}", que.is_empty());
println!("{}", que.is_full());
println!("{}", que.len());
}