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
17 use std::iter::{DoubleEndedIterator, ExactSizeIterator, FusedIterator};
18 use std::marker::PhantomData;
19 use std::mem::size_of;
20 use std::slice::from_raw_parts;
21 use std::str::from_utf8_unchecked;
22
23 use endian_scalar::read_scalar_at;
24 #[cfg(target_endian = "little")]
25 use endian_scalar::EndianScalar;
26 use follow::Follow;
27 use primitives::*;
28
29 #[derive(Debug)]
30 pub struct Vector<'a, T: 'a>(&'a [u8], usize, PhantomData<T>);
31
32 // We cannot use derive for these two impls, as it would only implement Copy
33 // and Clone for `T: Copy` and `T: Clone` respectively. However `Vector<'a, T>`
34 // can always be copied, no matter that `T` you have.
35 impl<'a, T> Copy for Vector<'a, T> {}
36 impl<'a, T> Clone for Vector<'a, T> {
clone(&self) -> Self37 fn clone(&self) -> Self {
38 *self
39 }
40 }
41
42 impl<'a, T: 'a> Vector<'a, T> {
43 #[inline(always)]
new(buf: &'a [u8], loc: usize) -> Self44 pub fn new(buf: &'a [u8], loc: usize) -> Self {
45 Vector {
46 0: buf,
47 1: loc,
48 2: PhantomData,
49 }
50 }
51
52 #[inline(always)]
len(&self) -> usize53 pub fn len(&self) -> usize {
54 read_scalar_at::<UOffsetT>(&self.0, self.1) as usize
55 }
56 #[inline(always)]
is_empty(&self) -> bool57 pub fn is_empty(&self) -> bool {
58 self.len() == 0
59 }
60 }
61
62 impl<'a, T: Follow<'a> + 'a> Vector<'a, T> {
63 #[inline(always)]
get(&self, idx: usize) -> T::Inner64 pub fn get(&self, idx: usize) -> T::Inner {
65 debug_assert!(idx < read_scalar_at::<u32>(&self.0, self.1) as usize);
66 let sz = size_of::<T>();
67 debug_assert!(sz > 0);
68 T::follow(self.0, self.1 as usize + SIZE_UOFFSET + sz * idx)
69 }
70
71 #[inline(always)]
iter(&self) -> VectorIter<'a, T>72 pub fn iter(&self) -> VectorIter<'a, T> {
73 VectorIter::new(*self)
74 }
75 }
76
77 pub trait SafeSliceAccess {}
78 impl<'a, T: SafeSliceAccess + 'a> Vector<'a, T> {
safe_slice(self) -> &'a [T]79 pub fn safe_slice(self) -> &'a [T] {
80 let buf = self.0;
81 let loc = self.1;
82 let sz = size_of::<T>();
83 debug_assert!(sz > 0);
84 let len = read_scalar_at::<UOffsetT>(&buf, loc) as usize;
85 let data_buf = &buf[loc + SIZE_UOFFSET..loc + SIZE_UOFFSET + len * sz];
86 let ptr = data_buf.as_ptr() as *const T;
87 let s: &'a [T] = unsafe { from_raw_parts(ptr, len) };
88 s
89 }
90 }
91
92 impl SafeSliceAccess for u8 {}
93 impl SafeSliceAccess for i8 {}
94 impl SafeSliceAccess for bool {}
95
96 #[cfg(target_endian = "little")]
97 mod le_safe_slice_impls {
98 impl super::SafeSliceAccess for u16 {}
99 impl super::SafeSliceAccess for u32 {}
100 impl super::SafeSliceAccess for u64 {}
101
102 impl super::SafeSliceAccess for i16 {}
103 impl super::SafeSliceAccess for i32 {}
104 impl super::SafeSliceAccess for i64 {}
105
106 impl super::SafeSliceAccess for f32 {}
107 impl super::SafeSliceAccess for f64 {}
108 }
109
110 #[cfg(target_endian = "little")]
111 pub use self::le_safe_slice_impls::*;
112
follow_cast_ref<'a, T: Sized + 'a>(buf: &'a [u8], loc: usize) -> &'a T113 pub fn follow_cast_ref<'a, T: Sized + 'a>(buf: &'a [u8], loc: usize) -> &'a T {
114 let sz = size_of::<T>();
115 let buf = &buf[loc..loc + sz];
116 let ptr = buf.as_ptr() as *const T;
117 unsafe { &*ptr }
118 }
119
120 impl<'a> Follow<'a> for &'a str {
121 type Inner = &'a str;
follow(buf: &'a [u8], loc: usize) -> Self::Inner122 fn follow(buf: &'a [u8], loc: usize) -> Self::Inner {
123 let len = read_scalar_at::<UOffsetT>(&buf, loc) as usize;
124 let slice = &buf[loc + SIZE_UOFFSET..loc + SIZE_UOFFSET + len];
125 unsafe { from_utf8_unchecked(slice) }
126 }
127 }
128
129 #[cfg(target_endian = "little")]
follow_slice_helper<T>(buf: &[u8], loc: usize) -> &[T]130 fn follow_slice_helper<T>(buf: &[u8], loc: usize) -> &[T] {
131 let sz = size_of::<T>();
132 debug_assert!(sz > 0);
133 let len = read_scalar_at::<UOffsetT>(&buf, loc) as usize;
134 let data_buf = &buf[loc + SIZE_UOFFSET..loc + SIZE_UOFFSET + len * sz];
135 let ptr = data_buf.as_ptr() as *const T;
136 let s: &[T] = unsafe { from_raw_parts(ptr, len) };
137 s
138 }
139
140 /// Implement direct slice access if the host is little-endian.
141 #[cfg(target_endian = "little")]
142 impl<'a, T: EndianScalar> Follow<'a> for &'a [T] {
143 type Inner = &'a [T];
follow(buf: &'a [u8], loc: usize) -> Self::Inner144 fn follow(buf: &'a [u8], loc: usize) -> Self::Inner {
145 follow_slice_helper::<T>(buf, loc)
146 }
147 }
148
149 /// Implement Follow for all possible Vectors that have Follow-able elements.
150 impl<'a, T: Follow<'a> + 'a> Follow<'a> for Vector<'a, T> {
151 type Inner = Vector<'a, T>;
follow(buf: &'a [u8], loc: usize) -> Self::Inner152 fn follow(buf: &'a [u8], loc: usize) -> Self::Inner {
153 Vector::new(buf, loc)
154 }
155 }
156
157 /// An iterator over a `Vector`.
158 #[derive(Debug)]
159 pub struct VectorIter<'a, T: 'a> {
160 buf: &'a [u8],
161 loc: usize,
162 remaining: usize,
163 phantom: PhantomData<T>,
164 }
165
166 impl<'a, T: 'a> VectorIter<'a, T> {
167 #[inline]
new(inner: Vector<'a, T>) -> Self168 pub fn new(inner: Vector<'a, T>) -> Self {
169 VectorIter {
170 buf: inner.0,
171 // inner.1 is the location of the data for the vector.
172 // The first SIZE_UOFFSET bytes is the length. We skip
173 // that to get to the actual vector content.
174 loc: inner.1 + SIZE_UOFFSET,
175 remaining: inner.len(),
176 phantom: PhantomData,
177 }
178 }
179 }
180
181 impl<'a, T: Follow<'a> + 'a> Clone for VectorIter<'a, T> {
182 #[inline]
clone(&self) -> Self183 fn clone(&self) -> Self {
184 VectorIter {
185 buf: self.buf,
186 loc: self.loc,
187 remaining: self.remaining,
188 phantom: self.phantom,
189 }
190 }
191 }
192
193 impl<'a, T: Follow<'a> + 'a> Iterator for VectorIter<'a, T> {
194 type Item = T::Inner;
195
196 #[inline]
next(&mut self) -> Option<T::Inner>197 fn next(&mut self) -> Option<T::Inner> {
198 let sz = size_of::<T>();
199 debug_assert!(sz > 0);
200
201 if self.remaining == 0 {
202 None
203 } else {
204 let result = T::follow(self.buf, self.loc);
205 self.loc += sz;
206 self.remaining -= 1;
207 Some(result)
208 }
209 }
210
211 #[inline]
nth(&mut self, n: usize) -> Option<T::Inner>212 fn nth(&mut self, n: usize) -> Option<T::Inner> {
213 let sz = size_of::<T>();
214 debug_assert!(sz > 0);
215
216 self.remaining = self.remaining.saturating_sub(n);
217
218 // Note that this might overflow, but that is okay because
219 // in that case self.remaining will have been set to zero.
220 self.loc = self.loc.wrapping_add(sz * n);
221
222 self.next()
223 }
224
225 #[inline]
size_hint(&self) -> (usize, Option<usize>)226 fn size_hint(&self) -> (usize, Option<usize>) {
227 (self.remaining, Some(self.remaining))
228 }
229 }
230
231 impl<'a, T: Follow<'a> + 'a> DoubleEndedIterator for VectorIter<'a, T> {
232 #[inline]
next_back(&mut self) -> Option<T::Inner>233 fn next_back(&mut self) -> Option<T::Inner> {
234 let sz = size_of::<T>();
235 debug_assert!(sz > 0);
236
237 if self.remaining == 0 {
238 None
239 } else {
240 self.remaining -= 1;
241 Some(T::follow(self.buf, self.loc + sz * self.remaining))
242 }
243 }
244
245 #[inline]
nth_back(&mut self, n: usize) -> Option<T::Inner>246 fn nth_back(&mut self, n: usize) -> Option<T::Inner> {
247 self.remaining = self.remaining.saturating_sub(n);
248 self.next_back()
249 }
250 }
251
252 impl<'a, T: 'a + Follow<'a>> ExactSizeIterator for VectorIter<'a, T> {
253 #[inline]
len(&self) -> usize254 fn len(&self) -> usize {
255 self.remaining
256 }
257 }
258
259 impl<'a, T: 'a + Follow<'a>> FusedIterator for VectorIter<'a, T> {}
260
261 impl<'a, T: Follow<'a> + 'a> IntoIterator for Vector<'a, T> {
262 type Item = T::Inner;
263 type IntoIter = VectorIter<'a, T>;
264 #[inline]
into_iter(self) -> Self::IntoIter265 fn into_iter(self) -> Self::IntoIter {
266 self.iter()
267 }
268 }
269
270 impl<'a, 'b, T: Follow<'a> + 'a> IntoIterator for &'b Vector<'a, T> {
271 type Item = T::Inner;
272 type IntoIter = VectorIter<'a, T>;
into_iter(self) -> Self::IntoIter273 fn into_iter(self) -> Self::IntoIter {
274 self.iter()
275 }
276 }
277