Closed5
Rust の B+Tree 実装コード読み解き
hmarui66読み解き対象
どなたかのB+Treeの実装や理解の参考になれば幸いです。
(1600行程度で収まったのでstd::collections::btree_mapより追いやすくなっていればいいなと)
標準ライブラリの BTreeMap のコードは難し過ぎたのでこちらのコードを眺めていたが、それでも分からないことが多かった。
hmarui66NonNull
NonNull でラップされている意味
参考
pub struct Unique<T: ?Sized> {
pointer: NonNull<T>,
_marker: PhantomData<T>,
}
などで使われている。
そもそも Unique とは？
- Rust の pointer の一種
- unique な所有権 semantics を表す
- Box, Vec, HashMap などの抽象化に利用
Box の宣言:
pub struct Box <
T: ? Sized、
#[unstable(feature = "allocator_api"、 issue = "32838" )] A: Allocator = Global、
>(Unique<T>、 A);
NonNull は？
- NULL ではないことが保証されている生ポインタのラッパー
- *mut T と本質的には同じだが NULL ではない不変条件が追加
- &T や &mut T のような借用やライフタイムの保証はないので unsafe
hmarui66PhantomData
参考
- スペースを消費せず、型の存在をシミュレートする Zero Sized Type: ZTS
- T の variance & drop check のための情報を compiler に提供
例
use std::marker::PhantomData;
struct MyRawPtrStruct<T> {
ptr: *mut T,
_marker: PhantomData<T>,
}
impl<T> MyRawPtrStruct<T> {
fn new(t: T) -> MyRawPtrStruct<T> {
let t = Box::new(t);
MyRawPtrStruct {
ptr: Box::into_raw(t),
_marker: PhantomData,
}
}
}
- ptr だけではライフタイムや所有権を自動的に推測できない
- PhantomData<T> によって推測可能に
使用例
- BorrowedFd
- Iter<T>
- Rc<T>
hmarui66marker
参考
hmarui66MaybeUninit
参考
- MaybeUninit を使うと変数が初期化されていないかも知れないということを示せる
例
use std::mem::MaybeUninit;
unsafe fn make_vec(out: *mut Vec<i32>) {
out.write(vec![1, 2, 3]);
}
fn main() {
let mut v = MaybeUninit::uninit();
unsafe {
make_vec(v.as_mut_ptr());
}
let v = unsafe { v.assume_init() };
println!("{:?}", v);
}
このスクラップは6ヶ月前にクローズされました