rs_alloc/
vec.rs

1//
2// Copyright 2020-Present (c) Raja Lehtihet & Wael El Oraiby
3//
4// Redistribution and use in source and binary forms, with or without
5// modification, are permitted provided that the following conditions are met:
6//
7// 1. Redistributions of source code must retain the above copyright notice,
8// this list of conditions and the following disclaimer.
9//
10// 2. Redistributions in binary form must reproduce the above copyright notice,
11// this list of conditions and the following disclaimer in the documentation
12// and/or other materials provided with the distribution.
13//
14// 3. Neither the name of the copyright holder nor the names of its contributors
15// may be used to endorse or promote products derived from this software without
16// specific prior written permission.
17//
18// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
22// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
23// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
26// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
27// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
28// POSSIBILITY OF SUCH DAMAGE.
29//
30
31use core::*;
32use core::ops::*;
33use core::slice::*;
34use crate::*;
35
36
37#[repr(C)]
38pub struct Vec<T> {
39    elements    : *mut T,
40    count       : usize,
41    capacity    : usize,
42}
43
44impl<T> Vec<T> {
45    pub fn with_capacity(c: usize) -> Self {
46        if c == 0 { Self::new() }
47        else {
48            Self {
49                elements: unsafe { alloc_array(c) },
50                count   : 0,
51                capacity: c,
52            }
53        }
54    }
55
56    pub fn new() -> Self {
57        Self {
58            elements: ptr::null_mut(),
59            count   : 0,
60            capacity: 0,
61        }
62    }
63
64    #[inline]
65    pub fn as_slice(&self) -> &[T] { unsafe { core::slice::from_raw_parts(self.elements, self.count) } }
66
67    #[inline]
68    pub fn as_mut_slice(&mut self) -> &mut [T] { unsafe { core::slice::from_raw_parts_mut(self.elements, self.count) } }
69
70    pub fn len(&self) -> usize { self.count }
71
72    pub fn push(&mut self, t: T) {
73        if self.count >= self.capacity {
74            let new_size    = if self.capacity == 0 { 16 } else { self.capacity * 2 };
75            let new_ptr     = unsafe { alloc_array::<T>(new_size) };
76            let old_ptr     = self.elements;
77
78            for i in 0..self.count {
79                let v = unsafe { old_ptr.offset(i as isize).read() };    // v = old[i];
80                unsafe { new_ptr.offset(i as isize).write(v) };          // new[i] = v;
81            }
82            unsafe { free_array_ptr(self.elements, self.capacity) };
83            self.elements   = new_ptr;
84            self.capacity   = new_size;
85        }
86
87        unsafe { self.elements.offset(self.count as isize).write(t) };
88        self.count += 1
89    }
90
91    pub fn pop(&mut self) -> Option<T> {
92        if self.count == 0 { None }
93        else {
94            let nc = self.count - 1;
95            let v = unsafe { ptr::read(self.get_unchecked(nc) as *const _) };
96            self.count -= 1;
97            Some(v)
98        }
99    }
100
101    #[inline]
102    pub fn get_unchecked(&self, idx: usize) -> &T {
103        let arr      = unsafe { core::slice::from_raw_parts(self.elements, self.count) };
104        &arr[idx]
105    }
106
107    #[inline]
108    pub fn get_unchecked_mut(&mut self, idx: usize) -> &mut T {
109        let arr      = unsafe { core::slice::from_raw_parts_mut(self.elements, self.count) };
110        &mut arr[idx]
111    }
112
113    fn drop_elements(&mut self) {
114        let arr      = unsafe { core::slice::from_raw_parts_mut(self.elements, self.count) };
115        for i in 0..self.count {
116            unsafe { ptr::drop_in_place(&arr[i] as *const T as *mut T) };
117        }
118    }
119
120    pub fn to_iter<'a>(&self) -> ::core::slice::Iter<'a, T> {
121        let arr      = unsafe { core::slice::from_raw_parts(self.elements, self.count) };
122        arr.into_iter()
123    }
124
125    pub fn last(&self) -> Option<&T> {
126        if self.count == 0 {
127            None
128        } else {
129            Some(&self[self.count - 1])
130        }
131    }
132
133    pub fn capacity(&self) -> usize { self.capacity }
134
135    pub fn iter(&self) -> slice::Iter<T> {
136        self.as_slice().into_iter()
137    }
138
139    pub fn iter_mut(&mut self) -> slice::IterMut<T> {
140        self.as_mut_slice().into_iter()
141    }
142
143    pub fn from_raw_parts(ptr: *mut T, len: usize, cap: usize) -> Self {
144        Self { elements: ptr, count: len, capacity: cap }
145    }
146}
147
148impl<'a, T> IntoIterator for &'a Vec<T> {
149    type Item = &'a T;
150    type IntoIter = slice::Iter<'a, T>;
151
152    fn into_iter(self) -> slice::Iter<'a, T> {
153        self.iter()
154    }
155}
156
157impl<'a, T> IntoIterator for &'a mut Vec<T> {
158    type Item = &'a mut T;
159    type IntoIter = slice::IterMut<'a, T>;
160
161    fn into_iter(self) -> slice::IterMut<'a, T> {
162        self.iter_mut()
163    }
164}
165
166impl<A> iter::FromIterator<A> for Vec<A> {
167    fn from_iter<I: IntoIterator<Item = A>>(iter: I) -> Self {
168        let mut v = Vec::new();
169        let mut it = iter.into_iter();
170        loop {
171            match it.next() {
172                Some(r) => v.push(r),
173                None => break,
174            }
175        }
176        v
177    }
178}
179
180pub trait VecAppend<E: Copy> {
181    fn append(&mut self, arr: &[E]);
182}
183
184impl<T : Copy> VecAppend<T> for Vec<T> {
185    fn append(&mut self, arr: &[T]) {
186        // TODO: optimize this
187        for e in arr {
188            self.push(e.clone());
189        }
190    }
191}
192
193impl<T, I: SliceIndex<[T]>> Index<I> for Vec<T> {
194    type Output = I::Output;
195
196    #[inline]
197    fn index(&self, index: I) -> &Self::Output {
198        Index::index(self.as_slice(), index)
199    }
200}
201
202impl<T, I: SliceIndex<[T]>> IndexMut<I> for Vec<T> {
203    #[inline]
204    fn index_mut(&mut self, index: I) -> &mut Self::Output {
205        IndexMut::index_mut(self.as_mut_slice(), index)
206    }
207}
208
209impl<T> Drop for Vec<T> {
210    fn drop(&mut self) {
211        self.drop_elements();
212        unsafe { free_array_ptr(self.elements, self.capacity) }
213    }
214}
215
216impl<T : Clone> Clone for Vec<T> {
217    fn clone(&self) -> Self {
218        let mut c = Vec::<T>::new();
219        for i in 0..self.count {
220            let v = self.get_unchecked(i);
221            c.push(v.clone());
222        }
223        c
224    }
225}
226
227
228#[cfg(test)]
229mod tests {
230    use super::*;
231
232    #[test]
233    fn test_destructor() {
234        let mut v = Vec::<Vec<i32>>::new();
235        for i in 0..100 {
236            let  mut vj = Vec::<i32>::new();
237            for j in 0..100 {
238                vj.push(j * i);
239            }
240            v.push(vj);
241        }
242    }
243
244    #[test]
245    fn test_iter() {
246        let mut v = Vec::new();
247        for i in 0..4 {
248            v.push(i);
249            assert!(v[i] == i);
250        }
251
252        let mut counter = 0;
253        for i in v.to_iter() {
254            if *i != counter { panic!("invalid {} != {}", i, counter) }
255            counter += 1;
256        }
257    }
258    #[test]
259    fn test_pop_destructor() {
260        let mut v = Vec::<Vec<i32>>::new();
261        for i in 0..100 {
262            let  mut vj = Vec::<i32>::new();
263            for j in 0..100 {
264                vj.push(j * i);
265            }
266            v.push(vj);
267        }
268
269        assert!(v.len() == 100);
270        for _ in 0..100 {
271            v.pop();
272        }
273        assert!(v.len() == 0);
274    }
275
276    #[test]
277    fn test_pop_destructor_push() {
278        let mut v = Vec::<Vec<i32>>::new();
279        for i in 0..100 {
280            let  mut vj = Vec::<i32>::new();
281            for j in 0..100 {
282                vj.push(j * i);
283            }
284            v.push(vj);
285        }
286
287        for _ in 0..100 {
288            v.pop();
289        }
290
291        assert!(v.len() == 0);
292
293        for i in 0..100 {
294            let  mut vj = Vec::<i32>::new();
295            for j in 0..100 {
296                vj.push(j * i);
297            }
298            v.push(vj);
299        }
300
301        assert!(v.len() == 100);
302    }
303}
rs_alloc/vec.rs

rs_alloc/
vec.rs
