file_vec/
iter.rs

1impl<'a,E,F:FnMut(&mut E)->bool> Drop for ExtractIf<'a,E,F>{
2	fn drop(&mut self){									// vec structure like (head: 0..pw, pgap: pw..pr, remaining: pr..qr, qgap: qr..qw, tail: qw..len)
3		unsafe{											// bounds were checked on construction for soundness, and presumably remained sound
4			let (pr,pw)=(self.pr,self.pw);
5			let (qr,qw)=(self.qr,self.qw);
6			let items=self.items;
7			let len=self.len;
8														// compute gap lengths and total items removed by the difference between the read and write pointers
9			let (pg,qg)=(pr.offset_from(pw) as usize,qw.offset_from(qr) as usize);
10			let remaining=qr.offset_from(pr) as usize;
11			let totalremoved=pg+qg;
12														// fill the two gaps from forward and reverse iteration
13			ptr::copy(pr,pw,remaining);
14			ptr::copy(qw,pw.add(remaining),items.add(*len).offset_from(qw) as usize);
15														// adjust len
16			*len-=totalremoved;
17		}
18	}
19}
20impl<'a,E,F:FnMut(&mut E)->bool> DoubleEndedIterator for ExtractIf<'a,E,F>{
21	fn next_back(&mut self)->Option<Self::Item>{
22		let (mut qr,mut qw)=(self.qr,self.qw);
23		let pr=self.pr;
24
25		let f=&mut self.f;
26		let item=loop{
27			unsafe{
28				let mut item=if pr<qr{ptr::read(qr.offset(-1))}else{break None};
29				qr=qr.offset(-1);
30
31				if f(&mut item){break Some(item)}
32				ptr::write(qw.offset(-1),item);
33				qw=qw.offset(-1);
34			}
35		};
36
37		(self.qr,self.qw)=(qr,qw);
38		item
39	}
40}
41impl<'a,E,F:FnMut(&mut E)->bool> ExtractIf<'a,E,F>{
42	/// create a new extract if from the file
43	pub fn new<R:RangeBounds<usize>>(vec:&'a mut FileVec<E>,range:R,f:F)->Self{
44		let begin=range.start_bound();
45		let end=range.end_bound();
46		let start=match begin{							// normalize bounds
47			Bound::Excluded(&n)=>n.saturating_add(1),
48			Bound::Included(&n)=>n,
49			Bound::Unbounded   =>0
50		};
51		let stop= match end{
52			Bound::Excluded(&n)=>n,
53			Bound::Included(&n)=>n.saturating_add(1),
54			Bound::Unbounded   =>vec.len()
55		};
56														// bounds check
57		assert!(start<=vec.len());
58		assert!(start<=stop);
59		assert!(stop <=vec.len());
60
61		let marker=PhantomData;
62		let len=unsafe{vec.len_mut() as *mut usize};
63		let items=vec.as_mut_ptr();
64
65		let pr=unsafe{items.add(start)};
66		let qr=unsafe{items.add(stop)};
67
68		let (pw,qw)=(pr,qr);
69
70		Self{f,items,len,marker,pr,pw,qr,qw}
71	}
72}
73impl<'a,E,F:FnMut(&mut E)->bool> Iterator for ExtractIf<'a,E,F>{
74	fn next(&mut self)->Option<Self::Item>{
75		let (mut pr,mut pw)=(self.pr,self.pw);
76		let qr=self.qr;
77
78		let f=&mut self.f;
79		let item=loop{
80			unsafe{
81				let mut item=if pr<qr{ptr::read(pr)}else{break None};
82				pr=pr.add(1);
83
84				if f(&mut item){break Some(item)}
85				ptr::write(pw,item);
86				pw=pw.add(1);
87			}
88		};
89
90		(self.pr,self.pw)=(pr,pw);
91		item
92	}
93	fn size_hint(&self)->(usize,Option<usize>){
94		let remaining=unsafe{self.qr.offset_from(self.pr) as usize};
95		(0,Some(remaining))
96	}
97	type Item=E;
98}
99impl<'a,E> AsMut<[E]> for Drain<'a,E>{
100	fn as_mut(&mut self)->&mut [E]{self.as_mut_slice()}
101}
102impl<'a,E> AsMut<Self> for Drain<'a,E>{
103	fn as_mut(&mut self)->&mut Self{self}
104}
105impl<'a,E> AsRef<[E]> for Drain<'a,E>{
106	fn as_ref(&self)->&[E]{self.as_slice()}
107}
108impl<'a,E> AsRef<Self> for Drain<'a,E>{
109	fn as_ref(&self)->&Self{self}
110}
111impl<'a,E> Borrow<[E]> for Drain<'a,E>{
112	fn borrow(&self)->&[E]{self.as_slice()}
113}
114impl<'a,E> BorrowMut<[E]> for Drain<'a,E>{
115	fn borrow_mut(&mut self)->&mut [E]{self.as_mut_slice()}
116}
117impl<'a,E> Deref for Drain<'a,E>{
118	fn deref(&self)->&Self::Target{self.as_slice()}
119	type Target=[E];
120}
121impl<'a,E> DerefMut for Drain<'a,E>{
122	fn deref_mut(&mut self)->&mut Self::Target{self.as_mut_slice()}
123}
124impl<'a,E> DoubleEndedIterator for Drain<'a,E>{
125	fn next_back(&mut self)->Option<E>{
126		let q=self.q;
127
128		if q<=self.p{return None}
129		unsafe{
130			let item=ptr::read(q.offset(-1));
131			self.q=q.offset(-1);
132
133			Some(item)
134		}
135	}
136	fn nth_back(&mut self,n:usize)->Option<E>{
137		if mem::needs_drop::<E>(){
138			for item in self.rev().take(n){mem::drop(item)}
139		}else if n<self.len(){
140			unsafe{					// p isn't allowed past q, but since the slice is from p to q, p+n<q is guaranteed by n being less than len
141				self.q=self.q.offset(-(n as isize))
142			}
143		}
144		self.next_back()
145	}
146}
147impl<'a,E> Drain<'a,E>{
148	/// reference the remaining items
149	pub fn as_slice(&self)->&[E]{
150		unsafe{
151			let len=self.q.offset_from(self.p) as usize;
152			let p=self.p;
153
154			slice::from_raw_parts(p,len)
155		}
156	}
157	/// reference the remaining items
158	pub fn as_mut_slice(&mut self)->&mut [E]{
159		unsafe{
160			let len=self.q.offset_from(self.p) as usize;
161			let p=self.p;
162
163			slice::from_raw_parts_mut(p,len)
164		}
165	}
166	/// clear the drain, returning the remaining items
167	pub fn keep_rest(&mut self){
168		unsafe{											// bounds were checked on construction for soundness, and presumably remained sound
169			let (start,stop)=(self.start,self.stop);
170			let items=self.items;
171			let len=self.len.as_mut().unwrap_unchecked();
172			let remaining=self.q.offset_from(self.p) as usize;
173			let pstart=items.add(start);
174			let pstop= items.add(stop);
175														// copy items remaining in the range to the start of the drained area, copy items after the range to fill the gap
176			ptr::copy(self.p,pstart,remaining);
177			ptr::copy(pstop,pstart.add(remaining),*len-stop);
178														// adjust len and make the iteration pointers equal so self thinks it's an empty range and doesn't need to drop anything
179			*len-=stop-start-remaining;
180			self.p=self.q;
181			self.start=self.stop;
182		}
183	}
184	/// create a new drain structure from the file vec
185	pub fn new<R:RangeBounds<usize>>(file:&'a mut FileVec<E>,range:R)->Self{
186		let begin=range.start_bound();
187		let end=range.end_bound();
188		let start=match begin{							// normalize bounds
189			Bound::Excluded(&n)=>n.saturating_add(1),
190			Bound::Included(&n)=>n,
191			Bound::Unbounded   =>0
192		};
193		let stop= match end{
194			Bound::Excluded(&n)=>n,
195			Bound::Included(&n)=>n.saturating_add(1),
196			Bound::Unbounded   =>file.len()
197		};
198														// bounds check
199		assert!(start<=file.len());
200		assert!(start<=stop);
201		assert!(stop <=file.len());
202
203		let marker=PhantomData;
204		let len=unsafe{file.len_mut() as *mut usize};
205		let items=file.as_mut_ptr();
206
207		let p=unsafe{items.add(start)};
208		let q=unsafe{items.add(stop)};
209
210		Self{items,len,marker,p,q,start,stop}
211	}
212}
213impl<'a,E> Drop for Drain<'a,E>{
214	fn drop(&mut self){
215		unsafe{											// bounds were checked on construction for soundness, and presumably remained sound
216			let (start,stop)=(self.start,self.stop);
217			if start==stop{return}						// no need to do anything with an empty range. This usually works implicitly; the explicit edge case is needed when the results of keep_rest aren't compatible with the normal drop process. In this situation, the keep_rest function handles the drop and sets start=stop.
218														// finalize by copy items after the range to fill the gap, then adjust the length
219			let finalize=FinalizeDrop::new(||{
220				let (items,len)=(self.items,self.len);
221														// the tail (items after removal range) are copied so it starts where the removal range started
222				ptr::copy(items.add(stop),items.add(start),*len-stop);
223				*len-=stop-start;
224			});
225			if mem::needs_drop::<E>(){
226				let mut p=self.p;
227				let     q=self.q;
228														// drop remaining items in the range if needed
229				while p<q{
230					ptr::drop_in_place(p);
231					p=p.add(1);
232				}
233			}											// finalize
234			mem::drop(finalize);
235		}
236	}
237}
238impl<'a,E> ExactSizeIterator for Drain<'a,E>{
239	fn len(&self)->usize{
240		unsafe{self.q.offset_from(self.p) as usize}
241	}
242}
243impl<'a,E> FusedIterator for Drain<'a,E>{}
244impl<'a,E> Iterator for Drain<'a,E>{
245	fn next(&mut self)->Option<E>{
246		let p=self.p;
247
248		if p>=self.q{return None}
249		unsafe{
250			let item=ptr::read(p);
251			self.p=p.add(1);
252
253			Some(item)
254		}
255	}
256	fn nth(&mut self,n:usize)->Option<E>{
257		if mem::needs_drop::<E>(){
258			for item in self.take(n){mem::drop(item)}
259		}else if n<self.len(){
260			unsafe{					// p isn't allowed past q, but since the slice is from p to q, p+n<q is guaranteed by n being less than len
261				self.p=self.p.add(n)
262			}
263		}
264		self.next()
265	}
266	fn size_hint(&self)->(usize,Option<usize>){
267		let len=self.len();
268		(len,Some(len))
269	}
270	type Item=E;
271}
272
273#[derive(Debug)]
274/// file vec drain structure
275pub struct Drain<'a,E>{items:*mut E,len:*mut usize,marker:PhantomData<&'a mut FileVec<E>>,p:*mut E,q:*mut E,start:usize,stop:usize}
276#[derive(Debug)]
277/// file vec extract if structure
278pub struct ExtractIf<'a,E,F:FnMut(&mut E)->bool>{f:F,items:*mut E,len:*mut usize,marker:PhantomData<&'a mut FileVec<E>>,pr:*mut E,pw:*mut E,qr:*mut E,qw:*mut E}
279
280unsafe impl<'a,E:Send,F:FnMut(&mut E)->bool+Send> Send for ExtractIf<'a,E,F>{}
281unsafe impl<'a,E:Send> Send for Drain<'a,E>{}
282unsafe impl<'a,E:Sync,F:FnMut(&mut E)->bool+Sync> Sync for ExtractIf<'a,E,F>{}
283unsafe impl<'a,E:Sync> Sync for Drain<'a,E>{}
284
285use crate::{FileVec,FinalizeDrop};
286use std::{
287	borrow::{Borrow,BorrowMut},iter::FusedIterator,marker::PhantomData,mem,ops::{Bound,Deref,DerefMut,RangeBounds},ptr,slice
288};
file_vec/iter.rs

file_vec/
iter.rs
