ringbuffer
目的
push_back/pop_front/peek_frontを備 えた FIFO基盤 を提供 します。queueの内部実装 として使 える、前 から取 り出 す構造 を提供 します。
実装
- ヘッダ
[len, cap, head, data_ptr]を 16 byte の領域 として保持 します。 要素 本体 はMemPtr<.T>で管理 し、容量 不足 時 は 2倍 へ拡張 します。循環 順序 はheadとlenから論理順 を計算 します。
注意
RingBuffer<.T>は内部 ヘッダと要素 領域 の所有権 を持 ちます。ringbuffer_push_backは更新後 のRingBuffer<.T>をResultで返 します。拡張 が発生 すると、内部 データ領域 の番地 は変 わりえます。ringbuffer_free後 の再利用 は禁止 です。
計算量
len/is_empty/peek_front/pop_frontは O(1) です。push_backは償却 O(1)、拡張 発生時 の最悪 時間 計算量 は O(n) です。
RingBuffer
FIFO を
目的
[len, cap, head, data_ptr]ヘッダと要素 領域 を一体 として扱 う所有者 です。
注意
値 を move すると所有権 も move します。copy前提 の軽量 ハンドルではありません。ringbuffer_freeを呼 ぶ責任 は所有 している側 にあります。
ringbuffer_header_len_ptr
length
目的
- ヘッダ
先頭 の length欄 をMemPtr<i32>として得 ます。
実装
hdrの raw address をそのままMemPtr<i32>として包 みます。
注意
公開 API ではなく、RingBuffer内部 の補助 です。
計算量
- O(1)
ringbuffer_header_cap_ptr
capacity
目的
- ヘッダ
中 の capacity欄 をMemPtr<i32>として得 ます。
実装
- ヘッダ
先頭 から 4 byte進 めた位置 を返 します。
注意
公開 API ではなく、RingBuffer内部 の補助 です。
計算量
- O(1)
ringbuffer_header_head_ptr
head
目的
先頭 要素 の論理位置 を表 すhead欄 をMemPtr<i32>として得 ます。
実装
- ヘッダ
先頭 から 8 byte進 めた位置 を返 します。
注意
公開 API ではなく、RingBuffer内部 の補助 です。
計算量
- O(1)
ringbuffer_header_data_ptr_ptr
data pointer
目的
要素 領域 の raw address を保持 する欄 をMemPtr<i32>として得 ます。
実装
- ヘッダ
先頭 から 12 byte進 めた位置 を返 します。
注意
公開 API ではなく、RingBuffer内部 の補助 です。
計算量
- O(1)
ringbuffer_new
目的
既定 容量 8 の空 RingBuffer<.T>を作成 します。
実装
ringbuffer_with_capacity 8を呼 びます。
注意
失敗 はResult::Err Diagとして返 ります。
計算量
- O(1)
ringbuffer_with_capacity
目的
少 なくともinitial_cap個 を保持 できる空 RingBuffer<.T>を作成 します。
実装
容量 1未満 は 1 に切 り上 げます。- 16 byte のヘッダと
cap * size_of<.T>byte の要素 領域 を別々 に確保 します。
注意
確保 失敗 した場合 はdiag_out_of_memoryを返 します。- ヘッダ
確保 に失敗 した場合 、すでに確保 したデータ領域 は解放 してから失敗 します。
計算量
- O(1)
ringbuffer_len
目的
現在 保持 している要素数 を返 します。
実装
- ヘッダの length
欄 を読 むだけです。
注意
変更 を伴 わない読 み取 り API です。
計算量
- O(1)
ringbuffer_push_back
目的
末尾 にitemを追加 し、更新後 のRingBuffer<.T>を返 します。
実装
空 きがあればtail = (head + len) mod capへ直接 書 き込 みます。満杯 なら 2倍 へ拡張 し、論理順 どおりに並 べ替 えてから追加 します。
注意
拡張 が起 きるとheadは 0 に戻 ります。更新後 のRingBuffer<.T>を受 け取 る前提 なので、pipe記法 では|> push_back ... |> uwokのように束縛 し直 します。
計算量
償却 O(1)、拡張 発生時 の最悪 時間 計算量 は O(n) です。
ringbuffer_pop_front
目的
先頭 要素 を取 り出 し、存在 しなければNoneを返 します。
実装
len == 0ならNoneを返 します。要素 がある場合 はhead位置 を読 み、head = (head + 1) mod capとlen - 1を更新 します。
注意
要素 の物理位置 は循環 しているので、配列 の 0番 とは限 りません。
計算量
- O(1)
ringbuffer_peek_front
目的
先頭 要素 を削除 せずに参照 します。
実装
head位置 を読 み、その要素 だけを返 します。
注意
空 ならNoneを返 します。
計算量
- O(1)
ringbuffer_clear
目的
保持 している要素数 を 0 に戻 して空 バッファにします。
実装
len = 0とhead = 0だけを書 き換 えます。
注意
容量 と確保 ずみメモリは維持 されます。
計算量
- O(1)
ringbuffer_free
目的
要素 領域 とヘッダ領域 を両方 解放 します。
実装
cap * size_of<.T>byte の要素 領域 をdealloc_ptr<.T>し、その後 で 16 byte のヘッダをdealloc_ptr<u8>します。
注意
解放後 にrbを再利用 してはいけません。
計算量
- O(1)