flatbuffers/
vector.rs

1/*
2 * Copyright 2018 Google Inc. All rights reserved.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *     http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17use core::cmp::Ordering;
18use core::fmt::{Debug, Formatter, Result};
19use core::iter::{DoubleEndedIterator, ExactSizeIterator, FusedIterator};
20#[cfg(nightly)]
21use core::iter::TrustedLen;
22use core::marker::PhantomData;
23use core::mem::{align_of, size_of};
24use core::str::from_utf8_unchecked;
25
26use crate::endian_scalar::read_scalar_at;
27use crate::follow::Follow;
28use crate::primitives::*;
29
30pub struct Vector<'a, T: 'a>(&'a [u8], usize, PhantomData<T>);
31
32impl<'a, T: 'a> Default for Vector<'a, T> {
33    fn default() -> Self {
34        // Static, length 0 vector.
35        // Note that derived default causes UB due to issues in read_scalar_at /facepalm.
36        Self(&[0; core::mem::size_of::<UOffsetT>()], 0, Default::default())
37    }
38}
39
40impl<'a, T> Debug for Vector<'a, T>
41where
42    T: 'a + Follow<'a>,
43    <T as Follow<'a>>::Inner: Debug,
44{
45    fn fmt(&self, f: &mut Formatter) -> Result {
46        f.debug_list().entries(self.iter()).finish()
47    }
48}
49
50// We cannot use derive for these two impls, as it would only implement Copy
51// and Clone for `T: Copy` and `T: Clone` respectively. However `Vector<'a, T>`
52// can always be copied, no matter that `T` you have.
53impl<'a, T> Copy for Vector<'a, T> {}
54
55impl<'a, T> Clone for Vector<'a, T> {
56    fn clone(&self) -> Self {
57        *self
58    }
59}
60
61impl<'a, T: 'a> Vector<'a, T> {
62    /// # Safety
63    ///
64    /// `buf` contains a valid vector at `loc` consisting of
65    ///
66    /// - UOffsetT element count
67    /// - Consecutive list of `T` elements
68    #[inline(always)]
69    pub unsafe fn new(buf: &'a [u8], loc: usize) -> Self {
70        Vector(buf, loc, PhantomData)
71    }
72
73    #[inline(always)]
74    pub fn len(&self) -> usize {
75        // Safety:
76        // Valid vector at time of construction starting with UOffsetT element count
77        unsafe { read_scalar_at::<UOffsetT>(self.0, self.1) as usize }
78    }
79
80    #[inline(always)]
81    pub fn is_empty(&self) -> bool {
82        self.len() == 0
83    }
84
85    #[inline(always)]
86    pub fn bytes(&self) -> &'a [u8] {
87        let sz = size_of::<T>();
88        let len = self.len();
89        &self.0[self.1 + SIZE_UOFFSET..self.1 + SIZE_UOFFSET + sz * len]
90    }
91}
92
93impl<'a, T: Follow<'a> + 'a> Vector<'a, T> {
94    #[inline(always)]
95    pub fn get(&self, idx: usize) -> T::Inner {
96        assert!(idx < self.len());
97        let sz = size_of::<T>();
98        debug_assert!(sz > 0);
99        // Safety:
100        // Valid vector at time of construction, verified that idx < element count
101        unsafe { T::follow(self.0, self.1 as usize + SIZE_UOFFSET + sz * idx) }
102    }
103
104    #[inline(always)]
105    pub fn lookup_by_key<K: Ord>(
106        &self,
107        key: K,
108        f: fn(&<T as Follow<'a>>::Inner, &K) -> Ordering,
109    ) -> Option<T::Inner> {
110        if self.is_empty() {
111            return None;
112        }
113
114        let mut left: usize = 0;
115        let mut right = self.len() - 1;
116
117        while left <= right {
118            let mid = (left + right) / 2;
119            let value = self.get(mid);
120            match f(&value, &key) {
121                Ordering::Equal => return Some(value),
122                Ordering::Less => left = mid + 1,
123                Ordering::Greater => {
124                    if mid == 0 {
125                        return None;
126                    }
127                    right = mid - 1;
128                }
129            }
130        }
131
132        None
133    }
134
135    #[inline(always)]
136    pub fn iter(&self) -> VectorIter<'a, T> {
137        VectorIter::from_vector(*self)
138    }
139}
140
141/// # Safety
142///
143/// `buf` must contain a value of T at `loc` and have alignment of 1
144pub unsafe fn follow_cast_ref<'a, T: Sized + 'a>(buf: &'a [u8], loc: usize) -> &'a T {
145    assert_eq!(align_of::<T>(), 1);
146    let sz = size_of::<T>();
147    let buf = &buf[loc..loc + sz];
148    let ptr = buf.as_ptr() as *const T;
149    // SAFETY
150    // buf contains a value at loc of type T and T has no alignment requirements
151    &*ptr
152}
153
154impl<'a> Follow<'a> for &'a str {
155    type Inner = &'a str;
156    unsafe fn follow(buf: &'a [u8], loc: usize) -> Self::Inner {
157        let len = read_scalar_at::<UOffsetT>(buf, loc) as usize;
158        let slice = &buf[loc + SIZE_UOFFSET..loc + SIZE_UOFFSET + len];
159        from_utf8_unchecked(slice)
160    }
161}
162
163impl<'a> Follow<'a> for &'a [u8] {
164    type Inner = &'a [u8];
165    unsafe fn follow(buf: &'a [u8], loc: usize) -> Self::Inner {
166        let len = read_scalar_at::<UOffsetT>(buf, loc) as usize;
167        &buf[loc + SIZE_UOFFSET..loc + SIZE_UOFFSET + len]
168    }
169}
170
171/// Implement Follow for all possible Vectors that have Follow-able elements.
172impl<'a, T: Follow<'a> + 'a> Follow<'a> for Vector<'a, T> {
173    type Inner = Vector<'a, T>;
174    unsafe fn follow(buf: &'a [u8], loc: usize) -> Self::Inner {
175        Vector::new(buf, loc)
176    }
177}
178
179/// An iterator over a `Vector`.
180#[derive(Debug)]
181pub struct VectorIter<'a, T: 'a> {
182    buf: &'a [u8],
183    loc: usize,
184    remaining: usize,
185    phantom: PhantomData<T>,
186}
187
188impl<'a, T: 'a> VectorIter<'a, T> {
189    #[inline]
190    pub fn from_vector(inner: Vector<'a, T>) -> Self {
191        VectorIter {
192            buf: inner.0,
193            // inner.1 is the location of the data for the vector.
194            // The first SIZE_UOFFSET bytes is the length. We skip
195            // that to get to the actual vector content.
196            loc: inner.1 + SIZE_UOFFSET,
197            remaining: inner.len(),
198            phantom: PhantomData,
199        }
200    }
201
202    /// Creates a new `VectorIter` from the provided slice
203    ///
204    /// # Safety
205    ///
206    /// buf must contain a contiguous sequence of `items_num` values of `T`
207    ///
208    #[inline]
209    pub unsafe fn from_slice(buf: &'a [u8], items_num: usize) -> Self {
210        VectorIter { buf, loc: 0, remaining: items_num, phantom: PhantomData }
211    }
212}
213
214impl<'a, T: Follow<'a> + 'a> Clone for VectorIter<'a, T> {
215    #[inline]
216    fn clone(&self) -> Self {
217        VectorIter {
218            buf: self.buf,
219            loc: self.loc,
220            remaining: self.remaining,
221            phantom: self.phantom,
222        }
223    }
224}
225
226impl<'a, T: Follow<'a> + 'a> Iterator for VectorIter<'a, T> {
227    type Item = T::Inner;
228
229    #[inline]
230    fn next(&mut self) -> Option<T::Inner> {
231        let sz = size_of::<T>();
232        debug_assert!(sz > 0);
233
234        if self.remaining == 0 {
235            None
236        } else {
237            // Safety:
238            // VectorIter can only be created from a contiguous sequence of `items_num`
239            // And remaining is initialized to `items_num`
240            let result = unsafe { T::follow(self.buf, self.loc) };
241            self.loc += sz;
242            self.remaining -= 1;
243            Some(result)
244        }
245    }
246
247    #[inline]
248    fn nth(&mut self, n: usize) -> Option<T::Inner> {
249        let sz = size_of::<T>();
250        debug_assert!(sz > 0);
251
252        self.remaining = self.remaining.saturating_sub(n);
253
254        // Note that this might overflow, but that is okay because
255        // in that case self.remaining will have been set to zero.
256        self.loc = self.loc.wrapping_add(sz * n);
257
258        self.next()
259    }
260
261    #[inline]
262    fn size_hint(&self) -> (usize, Option<usize>) {
263        (self.remaining, Some(self.remaining))
264    }
265}
266
267impl<'a, T: Follow<'a> + 'a> DoubleEndedIterator for VectorIter<'a, T> {
268    #[inline]
269    fn next_back(&mut self) -> Option<T::Inner> {
270        let sz = size_of::<T>();
271        debug_assert!(sz > 0);
272
273        if self.remaining == 0 {
274            None
275        } else {
276            self.remaining -= 1;
277            // Safety:
278            // VectorIter can only be created from a contiguous sequence of `items_num`
279            // And remaining is initialized to `items_num`
280            Some(unsafe { T::follow(self.buf, self.loc + sz * self.remaining) })
281        }
282    }
283
284    #[inline]
285    fn nth_back(&mut self, n: usize) -> Option<T::Inner> {
286        self.remaining = self.remaining.saturating_sub(n);
287        self.next_back()
288    }
289}
290
291impl<'a, T: 'a + Follow<'a>> ExactSizeIterator for VectorIter<'a, T> {
292    #[inline]
293    fn len(&self) -> usize {
294        self.remaining
295    }
296}
297
298#[cfg(nightly)]
299unsafe impl<'a, T: Follow<'a> + 'a> TrustedLen for VectorIter<'a, T> {}
300
301impl<'a, T: 'a + Follow<'a>> FusedIterator for VectorIter<'a, T> {}
302
303impl<'a, T: Follow<'a> + 'a> IntoIterator for Vector<'a, T> {
304    type Item = T::Inner;
305    type IntoIter = VectorIter<'a, T>;
306    #[inline]
307    fn into_iter(self) -> Self::IntoIter {
308        self.iter()
309    }
310}
311
312impl<'a, 'b, T: Follow<'a> + 'a> IntoIterator for &'b Vector<'a, T> {
313    type Item = T::Inner;
314    type IntoIter = VectorIter<'a, T>;
315    fn into_iter(self) -> Self::IntoIter {
316        self.iter()
317    }
318}
319
320#[cfg(feature = "serialize")]
321impl<'a, T> serde::ser::Serialize for Vector<'a, T>
322where
323    T: 'a + Follow<'a>,
324    <T as Follow<'a>>::Inner: serde::ser::Serialize,
325{
326    fn serialize<S>(&self, serializer: S) -> std::result::Result<S::Ok, S::Error>
327    where
328        S: serde::ser::Serializer,
329    {
330        use serde::ser::SerializeSeq;
331        let mut seq = serializer.serialize_seq(Some(self.len()))?;
332        for element in self {
333            seq.serialize_element(&element)?;
334        }
335        seq.end()
336    }
337}
flatbuffers/vector.rs

flatbuffers/
vector.rs
