pi_append_vec/
lib.rs

1//! 线程安全的仅添加vec，依赖整理方法保证内存连续
2//! AppendVec保证用index访问时，是对象可见和线程安全的
3//! SafeVec保证iter访问时，是对象可见和线程安全的
4//! 整理方法settle，要求必须mut引用，这时会安全的进行内存整理
5
6use core::fmt::*;
7use std::mem::{needs_drop, take, transmute, MaybeUninit};
8use std::ops::{Index, IndexMut, Range};
9use std::sync::atomic::Ordering;
10
11use pi_arr::{Arr, Iter};
12use pi_share::ShareUsize;
13
14pub struct AppendVec<T> {
15    len: ShareUsize,
16    arr: Arr<T>,
17}
18impl<T: Default> AppendVec<T> {
19    /// Creates an empty [`AppendVec`] with the given capacity.
20    ///
21    /// # Examples
22    ///
23    /// ```
24    /// use crate::pi_append_vec::AppendVec;
25    /// let mut vec: AppendVec<&str> = AppendVec::with_capacity(3);
26    /// let welcome = vec.insert("Welcome");
27    /// let good_day = vec.insert("Good day");
28    /// let hello = vec.insert("Hello");
29    /// ```
30    #[inline(always)]
31    pub fn with_capacity(capacity: usize) -> Self {
32        Self {
33            len: ShareUsize::new(0),
34            arr: Arr::with_capacity(capacity),
35        }
36    }
37    /// 长度
38    #[inline(always)]
39    pub fn len(&self) -> usize {
40        self.len.load(Ordering::Relaxed)
41    }
42    #[inline(always)]
43    pub fn get(&self, index: usize) -> Option<&T> {
44        if index >= self.len() {
45            return None;
46        }
47        self.arr.get(index)
48    }
49    #[inline(always)]
50    pub unsafe fn get_unchecked(&self, index: usize) -> &T {
51        self.arr.get_unchecked(index)
52    }
53    #[inline(always)]
54    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
55        let len = *self.len.get_mut();
56        if index >= len {
57            return None;
58        }
59        self.arr.get_mut(index)
60    }
61
62    #[inline(always)]
63    pub unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut T {
64        self.arr.get_unchecked_mut(index)
65    }
66    #[inline(always)]
67    pub fn load(&self, index: usize) -> Option<&mut T> {
68        if index >= self.len() {
69            return None;
70        }
71        Some(self.arr.load_alloc(index))
72    }
73    #[inline(always)]
74    pub unsafe fn load_unchecked(&self, index: usize) -> &mut T {
75        debug_assert!(index < self.len());
76        self.arr.load_unchecked(index)
77    }
78    #[inline(always)]
79    pub fn alloc(&self) -> (&mut T, usize) {
80        let index = self.len.fetch_add(1, Ordering::Relaxed);
81        (self.arr.load_alloc(index), index)
82    }
83    #[inline(always)]
84    pub fn alloc_index(&self, multiple: usize) -> usize {
85        self.len.fetch_add(multiple, Ordering::Relaxed)
86    }
87    #[inline(always)]
88    pub fn insert(&self, value: T) -> usize {
89        let index = self.alloc_index(1);
90        *self.arr.load_alloc(index) = value;
91        index
92    }
93    #[inline(always)]
94    pub fn iter(&self) -> Iter<'_, T> {
95        self.slice_raw(0..self.len())
96    }
97    #[inline(always)]
98    pub fn slice(&self, range: Range<usize>) -> Iter<'_, T> {
99        let len = self.len();
100        if range.end <= len {
101            return self.slice_raw(range);
102        }
103        self.slice_raw(range.start..len)
104    }
105    #[inline(always)]
106    pub fn slice_raw(&self, range: Range<usize>) -> Iter<'_, T> {
107        self.arr.slice(range)
108    }
109    #[inline(always)]
110    pub unsafe fn set_len(&self, len: usize) {
111        self.len.store(len, Ordering::Relaxed);
112    }
113    #[inline(always)]
114    pub fn capacity(&self) -> usize {
115        self.arr.capacity(self.len())
116    }
117    #[inline(always)]
118    pub fn vec_capacity(&self) -> usize {
119        self.arr.vec_capacity()
120    }
121    /// 将arr的内容移动到vec上，让内存连续，并且没有原子操作
122    #[inline(always)]
123    pub fn settle(&mut self, additional: usize) {
124        let len = *self.len.get_mut();
125        if len == 0 {
126            return;
127        }
128        self.arr.settle(len, additional);
129    }
130    #[inline(always)]
131    pub fn remain_settle(&mut self, mut range: Range<usize>, additional: usize) {
132        let len = self.len.get_mut();
133        if *len == 0 {
134            return;
135        }
136        let old = *len;
137        if range.end > *len {
138            range.end = *len;
139        }
140        *len = range.len();
141        self.arr.remain_settle(range, old, additional);
142    }
143
144    /// 清理，并释放arr的内存
145    #[inline(always)]
146    pub fn clear(&mut self, additional: usize) {
147        let len = self.len.get_mut();
148        if *len == 0 {
149            return;
150        }
151        let len = take(len);
152        self.arr.clear(len, additional);
153    }
154}
155impl<T: Default> Index<usize> for AppendVec<T> {
156    type Output = T;
157
158    fn index(&self, index: usize) -> &Self::Output {
159        self.get(index).expect("no element found at index {index}")
160    }
161}
162impl<T: Default> IndexMut<usize> for AppendVec<T> {
163    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
164        self.get_mut(index)
165            .expect("no element found at index_mut {index}")
166    }
167}
168impl<T: Default + Debug> Debug for AppendVec<T> {
169    fn fmt(&self, f: &mut Formatter<'_>) -> Result {
170        f.debug_list().entries(self.iter()).finish()
171    }
172}
173
174impl<T: Default> Default for AppendVec<T> {
175    fn default() -> Self {
176        Self::with_capacity(0)
177    }
178}
179
180pub struct SafeVec<T> {
181    vec: AppendVec<Element<T>>,
182    len: ShareUsize,
183}
184impl<T> SafeVec<T> {
185    #[inline(always)]
186    pub fn with_capacity(capacity: usize) -> Self {
187        let vec = AppendVec::with_capacity(capacity);
188        Self {
189            vec,
190            len: ShareUsize::new(0),
191        }
192    }
193    #[inline(always)]
194    pub fn capacity(&self) -> usize {
195        self.vec.arr.capacity(self.len())
196    }
197    /// 长度
198    #[inline(always)]
199    pub fn len(&self) -> usize {
200        self.len.load(Ordering::Acquire)
201    }
202    #[inline(always)]
203    pub fn get(&self, index: usize) -> Option<&T> {
204        let len = self.len();
205        if index >= len {
206            return None;
207        }
208        self.vec.get(index).map(|r| unsafe { &*r.0.as_ptr() })
209    }
210    #[inline(always)]
211    pub unsafe fn get_unchecked(&self, index: usize) -> &T {
212        &*self.vec.get_unchecked(index).0.as_ptr()
213    }
214    #[inline(always)]
215    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
216        let len = self.len();
217        if index >= len {
218            return None;
219        }
220        self.vec
221            .get_mut(index)
222            .map(|r| unsafe { &mut *r.0.as_mut_ptr() })
223    }
224    #[inline(always)]
225    pub unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut T {
226        &mut *self.vec.get_unchecked_mut(index).0.as_mut_ptr()
227    }
228    #[inline(always)]
229    pub fn load(&self, index: usize) -> Option<&mut T> {
230        self.vec
231            .load(index)
232            .map(|r| unsafe { &mut *r.0.as_mut_ptr() })
233    }
234    #[inline(always)]
235    pub unsafe fn load_unchecked(&self, index: usize) -> &mut T {
236        &mut *self.vec.load_unchecked(index).0.as_mut_ptr()
237    }
238
239    #[inline(always)]
240    pub fn insert(&self, value: T) -> usize {
241        let (r, index) = self.vec.alloc();
242        *r = Element(MaybeUninit::new(value));
243        while self
244            .len
245            .compare_exchange(index, index + 1, Ordering::Release, Ordering::Relaxed)
246            .is_err()
247        {
248            std::hint::spin_loop();
249        }
250        index
251    }
252    #[inline(always)]
253    pub fn alloc_entry<'a>(&'a self) -> Entry<'a, T> {
254        let (value, index) = self.vec.alloc();
255        Entry {
256            index,
257            len: &self.len,
258            value,
259        }
260    }
261    #[inline(always)]
262    pub fn iter(&self) -> SafeVecIter<'_, T> {
263        SafeVecIter(self.vec.slice(0..self.len()))
264    }
265    #[inline(always)]
266    pub fn slice(&self, range: Range<usize>) -> SafeVecIter<'_, T> {
267        SafeVecIter(self.vec.slice(range))
268    }
269    pub fn vec_capacity(&self) -> usize {
270        self.vec.vec_capacity()
271    }
272    #[inline(always)]
273    pub fn settle(&mut self, additional: usize) {
274        self.vec.settle(additional);
275    }
276    #[inline(always)]
277    pub fn remain_settle(&mut self, range: Range<usize>, additional: usize) {
278        self.vec.remain_settle(range, additional);
279    }
280
281    #[inline(always)]
282    pub fn clear(&mut self, additional: usize) {
283        let len = take(self.len.get_mut());
284        if len == 0 {
285            return;
286        }
287        if needs_drop::<T>() {
288            for i in self.vec.iter() {
289                unsafe { i.0.assume_init_drop() }
290            }
291        }
292        self.vec.clear(additional);
293    }
294}
295impl<T> Index<usize> for SafeVec<T> {
296    type Output = T;
297
298    fn index(&self, index: usize) -> &Self::Output {
299        self.get(index).expect("no element found at index {index}")
300    }
301}
302impl<T> IndexMut<usize> for SafeVec<T> {
303    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
304        self.get_mut(index)
305            .expect("no element found at index_mut {index}")
306    }
307}
308impl<T> Drop for SafeVec<T> {
309    fn drop(&mut self) {
310        if needs_drop::<T>() {
311            for i in self.vec.iter() {
312                unsafe { i.0.assume_init_drop() }
313            }
314        }
315    }
316}
317impl<T> Default for SafeVec<T> {
318    fn default() -> Self {
319        SafeVec {
320            vec: Default::default(),
321            len: ShareUsize::new(0),
322        }
323    }
324}
325impl<T: Debug> Debug for SafeVec<T> {
326    fn fmt(&self, f: &mut Formatter<'_>) -> Result {
327        f.debug_list().entries(self.iter()).finish()
328    }
329}
330
331struct Element<T>(MaybeUninit<T>);
332impl<T> Default for Element<T> {
333    fn default() -> Self {
334        Self(MaybeUninit::uninit())
335    }
336}
337
338pub struct SafeVecIter<'a, T>(Iter<'a, Element<T>>);
339impl<'a, T> Iterator for SafeVecIter<'a, T> {
340    type Item = &'a mut T;
341
342    fn next(&mut self) -> Option<Self::Item> {
343        self.0.next().map(|r| unsafe { transmute(r.0.as_ptr()) })
344    }
345    fn size_hint(&self) -> (usize, Option<usize>) {
346        self.0.size_hint()
347    }
348}
349
350pub struct Entry<'a, T> {
351    index: usize,
352    len: &'a ShareUsize,
353    value: &'a mut Element<T>,
354}
355impl<'a, T> Entry<'_, T> {
356    pub fn index(&self) -> usize {
357        self.index
358    }
359    pub fn insert(self, value: T) {
360        *self.value = Element(MaybeUninit::new(value));
361    }
362}
363impl<'a, T> Drop for Entry<'_, T> {
364    fn drop(&mut self) {
365        while self
366            .len
367            .compare_exchange(
368                self.index,
369                self.index + 1,
370                Ordering::Release,
371                Ordering::Relaxed,
372            )
373            .is_err()
374        {
375            std::hint::spin_loop();
376        }
377    }
378}
379
380#[cfg(test)]
381mod tests {
382    use crate::*;
383
384    #[test]
385    fn test() {
386        println!("test start");
387        let mut vec = AppendVec::with_capacity(4);
388        let _good_day = vec.insert("Good day");
389        let _hello = vec.insert("Hello");
390        assert_eq!(vec.len(), 2);
391        let hello1 = vec.insert("Hello");
392        assert_eq!(vec[hello1], "Hello");
393        assert_eq!(unsafe { vec.get_unchecked(hello1) }, &"Hello");
394        println!("test: {:?}", 2);
395        *vec.get_mut(hello1).unwrap() = "Hello1";
396        assert_eq!(vec[hello1], "Hello1");
397        assert_eq!(vec.len(), 3);
398        println!("test: {:?}", 3);
399        println!("vec: {:?}", vec);
400    }
401    #[test]
402    fn test_removes() {
403        let mut removes: AppendVec<usize> = Default::default();
404        removes.insert(1);
405        removes.insert(2);
406        removes.clear(1);
407        removes.insert(1);
408        removes.insert(6);
409    }
410
411    #[test]
412    fn test_str() {
413        let vec = AppendVec::with_capacity(4);
414        let _good_day = vec.insert("Good day");
415        let _hello = vec.insert("Hello");
416        assert_eq!(vec.len(), 2);
417        let hello1 = vec.insert("Hello");
418        assert_eq!(vec[hello1], "Hello");
419    }
420}
pi_append_vec/lib.rs

pi_append_vec/
lib.rs
