1use std::mem::transmute;
2use std::ptr::{read, write, swap, copy};
3use std::slice::{from_raw_parts, from_raw_parts_mut};
4use crate::util::PointerExt;
5
6pub unsafe trait Vector {
7 type Item;
8
9 #[inline]
10 fn new() -> Self where Self: Sized {
11 Self::with_capacity(0)
12 }
13
14 fn with_capacity(cap: usize) -> Self where Self: Sized;
15
16 fn capacity(&self) -> usize;
17 fn reserve(&mut self, additional: usize);
18 fn reserve_exact(&mut self, additional: usize);
19 fn shrink_to_fit(&mut self);
20 fn into_boxed_slice(self) -> Box<[Self::Item]>;
21
22 fn truncate(&mut self, len: usize) {
23 let s_len = self.len();
24 assert!(len <= s_len);
25 let ptr = self.as_mut_ptr();
26
27 unsafe {
28 self.set_len(len);
29 for i in len..s_len {
30 read(ptr.uoffset(i));
31 }
32 }
33 }
34
35 unsafe fn set_len(&mut self, len: usize);
36
37 fn swap_remove(&mut self, index: usize) -> Self::Item {
38 let len = self.len();
39 assert!(index < len);
40 unsafe {
41 let ptr = self.as_mut_ptr();
42 let v = read(ptr.uoffset(index));
43 if index != len - 1 {
44 swap(ptr.uoffset(len - 1), ptr.uoffset(index));
45 }
46 self.set_len(len - 1);
47 v
48 }
49 }
50
51 fn insert(&mut self, index: usize, element: Self::Item) {
52 let len = self.len();
53 assert!(index <= len);
54 self.reserve(1);
55 unsafe {
56 let ptr = self.as_mut_ptr().uoffset(index);
57 copy(ptr, ptr.uoffset(1), len - index);
58 write(ptr, element);
59 self.set_len(len + 1);
60 }
61 }
62
63 fn remove(&mut self, index: usize) -> Self::Item {
64 let len = self.len();
65 assert!(index < len);
66 unsafe {
67 let ptr = self.as_mut_ptr().uoffset(index);
68 self.set_len(len - 1);
69 let v = read(ptr);
70 copy(ptr.uoffset(1), ptr, len - index - 1);
71 v
72 }
73 }
74
75 fn retain<F: FnMut(&Self::Item) -> bool>(&mut self, mut f: F) where Self: Sized {
76 let len = self.len();
77 let mut del = 0;
78 unsafe {
79 let v = self.as_mut_ptr();
80
81 for i in 0..len {
82 if !f(transmute(v.uoffset(i) as *const _)) {
83 del += 1;
84 } else if del > 0 {
85 swap(v.uoffset(i - del), v.uoffset(i));
86 }
87 }
88 }
89 if del > 0 {
90 self.truncate(len - del);
91 }
92 }
93
94 fn push(&mut self, value: Self::Item) {
95 self.reserve(1);
96 let len = self.len();
97 unsafe {
98 write(self.as_mut_ptr().uoffset(len), value);
99 self.set_len(len + 1);
100 }
101 }
102
103 fn pop(&mut self) -> Option<Self::Item> {
104 let len = self.len();
105 if len == 0 {
106 None
107 } else {
108 Some(self.swap_remove(len - 1))
109 }
110 }
111
112 #[inline]
113 fn clear(&mut self) { self.truncate(0) }
114
115 fn len(&self) -> usize;
116
117 #[inline]
118 fn is_empty(&self) -> bool { self.len() == 0 }
119
120 fn push_cap(&mut self, value: Self::Item) -> Result<(), Self::Item> {
121 if self.len() < self.capacity() {
122 self.push(value);
123 Ok(())
124 } else {
125 Err(value)
126 }
127 }
128
129 fn insert_cap(&mut self, index: usize, element: Self::Item) -> Option<Self::Item> {
130 let cap = self.capacity();
131
132 if index >= cap {
133 return Some(element);
134 }
135
136 let ret = if self.len() < cap {
137 None
138 } else {
139 self.pop()
140 };
141 self.insert(index, element);
142 ret
143 }
144
145 fn as_ptr(&self) -> *const Self::Item;
146 fn as_mut_ptr(&mut self) -> *mut Self::Item;
147
148 #[inline]
149 fn as_slice(&self) -> &[Self::Item] {
150 unsafe { from_raw_parts(self.as_ptr(), self.len()) }
151 }
152
153 #[inline]
154 fn as_mut_slice(&mut self) -> &mut [Self::Item] {
155 unsafe { from_raw_parts_mut(self.as_mut_ptr(), self.len()) }
156 }
157
158 unsafe fn uninitialized_resize(&mut self, new_len: usize) {
159 let len = self.len();
160 if new_len > len {
161 self.reserve_exact(new_len - len);
162 }
163 self.set_len(new_len);
164 }
165}
166
167unsafe impl<T> Vector for Vec<T> {
168 type Item = T;
169
170 #[inline] fn new() -> Self { Vec::new() }
171 #[inline] fn with_capacity(cap: usize) -> Self { Vec::with_capacity(cap) }
172 #[inline] fn capacity(&self) -> usize { Vec::capacity(self) }
173 #[inline] fn reserve(&mut self, additional: usize) { Vec::reserve(self, additional) }
174 #[inline] fn reserve_exact(&mut self, additional: usize) { Vec::reserve_exact(self, additional) }
175 #[inline] fn shrink_to_fit(&mut self) { Vec::shrink_to_fit(self) }
176 #[inline] fn into_boxed_slice(self) -> Box<[T]> { Vec::into_boxed_slice(self) }
177 #[inline] fn truncate(&mut self, len: usize) { Vec::truncate(self, len) }
178 #[inline] unsafe fn set_len(&mut self, len: usize) { Vec::set_len(self, len) }
179 #[inline] fn swap_remove(&mut self, index: usize) -> T { Vec::swap_remove(self, index) }
180 #[inline] fn insert(&mut self, index: usize, element: T) { Vec::insert(self, index, element) }
181 #[inline] fn remove(&mut self, index: usize) -> T { Vec::remove(self, index) }
182 #[inline] fn retain<F: FnMut(&T) -> bool>(&mut self, f: F) { Vec::retain(self, f) }
183 #[inline] fn push(&mut self, value: T) { Vec::push(self, value) }
184 #[inline] fn pop(&mut self) -> Option<T> { Vec::pop(self) }
185 #[inline] fn clear(&mut self) { Vec::clear(self) }
186 #[inline] fn len(&self) -> usize { Vec::len(self) }
187 #[inline] fn is_empty(&self) -> bool { Vec::is_empty(self) }
188 #[inline] fn as_ptr(&self) -> *const T { self[..].as_ptr() }
189 #[inline] fn as_mut_ptr(&mut self) -> *mut T { self[..].as_mut_ptr() }
190 #[inline] fn as_slice(&self) -> &[T] { &self[..] }
191 #[inline] fn as_mut_slice(&mut self) -> &mut [T] { &mut self[..] }
192}