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

flatbuffers/
vector.rs
