servers/
repeated_field.rs

1// Copyright (c) 2019 Stepan Koltsov
2//
3// Permission is hereby granted, free of charge, to any person obtaining a copy
4// of this software and associated documentation files (the "Software"), to deal
5// in the Software without restriction, including without limitation the rights
6// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
7// copies of the Software, and to permit persons to whom the Software is
8// furnished to do so, subject to the following conditions:
9//
10// The above copyright notice and this permission notice shall be included in all
11// copies or substantial portions of the Software.
12//
13// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
14// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
15// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
16// IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
17// DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
18// OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE
19// OR OTHER DEALINGS IN THE SOFTWARE.
20
21// The Clear trait is copied from https://github.com/stepancheg/rust-protobuf/blob/v2.28.0/protobuf/src/clear.rs
22// The RepeatedField struct is copied from https://github.com/stepancheg/rust-protobuf/blob/v2.28.0/protobuf/src/repeated.rs
23// This code is to leverage the pooling mechanism to avoid frequent heap allocation/de-allocation when decoding deeply nested structs.
24
25use std::borrow::Borrow;
26use std::cmp::Ordering;
27use std::default::Default;
28use std::hash::{Hash, Hasher};
29use std::iter::{FromIterator, IntoIterator};
30use std::ops::{Deref, DerefMut, Index, IndexMut};
31use std::{fmt, slice, vec};
32
33use bytes::Bytes;
34
35const NULL_BYTES: &[u8] = &[];
36
37/// anything that can be cleared
38pub trait Clear {
39    /// Clear this make, make it equivalent to newly created object.
40    fn clear(&mut self);
41}
42
43impl Clear for &[u8] {
44    fn clear(&mut self) {
45        *self = NULL_BYTES;
46    }
47}
48
49impl<T> Clear for Option<T> {
50    fn clear(&mut self) {
51        self.take();
52    }
53}
54
55impl Clear for String {
56    fn clear(&mut self) {
57        String::clear(self);
58    }
59}
60
61impl<T> Clear for Vec<T> {
62    fn clear(&mut self) {
63        Vec::clear(self);
64    }
65}
66
67impl Clear for Bytes {
68    fn clear(&mut self) {
69        Bytes::clear(self);
70    }
71}
72
73/// Wrapper around vector to avoid deallocations on clear.
74pub struct RepeatedField<T> {
75    vec: Vec<T>,
76    len: usize,
77}
78
79impl<T> RepeatedField<T> {
80    /// Return number of elements in this container.
81    #[inline]
82    pub fn len(&self) -> usize {
83        self.len
84    }
85
86    /// Returns true if this container is empty.
87    #[inline]
88    pub fn is_empty(&self) -> bool {
89        self.len == 0
90    }
91
92    /// Clear.
93    #[inline]
94    pub fn clear(&mut self) {
95        self.len = 0;
96    }
97}
98
99impl<T> Default for RepeatedField<T> {
100    #[inline]
101    fn default() -> RepeatedField<T> {
102        RepeatedField {
103            vec: Vec::new(),
104            len: 0,
105        }
106    }
107}
108
109impl<T> RepeatedField<T> {
110    /// Create new empty container.
111    #[inline]
112    pub fn new() -> RepeatedField<T> {
113        Default::default()
114    }
115
116    /// Create a contained with data from given vec.
117    #[inline]
118    pub fn from_vec(vec: Vec<T>) -> RepeatedField<T> {
119        let len = vec.len();
120        RepeatedField { vec, len }
121    }
122
123    /// Convert data into vec.
124    #[inline]
125    pub fn into_vec(self) -> Vec<T> {
126        let mut vec = self.vec;
127        vec.truncate(self.len);
128        vec
129    }
130
131    /// Return current capacity.
132    #[inline]
133    pub fn capacity(&self) -> usize {
134        self.vec.capacity()
135    }
136
137    /// View data as slice.
138    #[inline]
139    pub fn as_slice(&self) -> &[T] {
140        &self.vec[..self.len]
141    }
142
143    /// View data as mutable slice.
144    #[inline]
145    pub fn as_mut_slice(&mut self) -> &mut [T] {
146        &mut self.vec[..self.len]
147    }
148
149    /// Get subslice of this container.
150    #[inline]
151    pub fn slice(&self, start: usize, end: usize) -> &[T] {
152        &self.as_ref()[start..end]
153    }
154
155    /// Get slice from given index.
156    #[inline]
157    pub fn slice_from(&self, start: usize) -> &[T] {
158        &self.as_ref()[start..]
159    }
160
161    /// Get slice to given index.
162    #[inline]
163    pub fn slice_to(&self, end: usize) -> &[T] {
164        &self.as_ref()[..end]
165    }
166
167    /// View this container as two slices split at given index.
168    #[inline]
169    pub fn split_at(&self, mid: usize) -> (&[T], &[T]) {
170        self.as_ref().split_at(mid)
171    }
172
173    /// View this container as two mutable slices split at given index.
174    #[inline]
175    pub fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
176        self.as_mut_slice().split_at_mut(mid)
177    }
178
179    /// View all but first elements of this container.
180    #[inline]
181    pub fn tail(&self) -> &[T] {
182        &self.as_ref()[1..]
183    }
184
185    /// Last element of this container.
186    #[inline]
187    pub fn last(&self) -> Option<&T> {
188        self.as_ref().last()
189    }
190
191    /// Mutable last element of this container.
192    #[inline]
193    pub fn last_mut(&mut self) -> Option<&mut T> {
194        self.as_mut_slice().last_mut()
195    }
196
197    /// View all but last elements of this container.
198    #[inline]
199    pub fn init(&self) -> &[T] {
200        let s = self.as_ref();
201        &s[0..s.len() - 1]
202    }
203
204    /// Push an element to the end.
205    #[inline]
206    pub fn push(&mut self, value: T) {
207        if self.len == self.vec.len() {
208            self.vec.push(value);
209        } else {
210            self.vec[self.len] = value;
211        }
212        self.len += 1;
213    }
214
215    /// Pop last element.
216    #[inline]
217    pub fn pop(&mut self) -> Option<T> {
218        if self.len == 0 {
219            None
220        } else {
221            self.vec.truncate(self.len);
222            self.len -= 1;
223            self.vec.pop()
224        }
225    }
226
227    /// Insert an element at specified position.
228    #[inline]
229    pub fn insert(&mut self, index: usize, value: T) {
230        assert!(index <= self.len);
231        self.vec.insert(index, value);
232        self.len += 1;
233    }
234
235    /// Remove an element from specified position.
236    #[inline]
237    pub fn remove(&mut self, index: usize) -> T {
238        assert!(index < self.len);
239        self.len -= 1;
240        self.vec.remove(index)
241    }
242
243    /// Retains only the elements specified by the predicate.
244    ///
245    /// In other words, remove all elements `e` such that `f(&e)` returns `false`.
246    /// This method operates in place, visiting each element exactly once in the
247    /// original order, and preserves the order of the retained elements.
248    ///
249    /// # Examples
250    ///
251    /// ```
252    /// use servers::repeated_field::RepeatedField;
253    ///
254    /// let mut vec = RepeatedField::from(vec![1, 2, 3, 4]);
255    /// vec.retain(|&x| x % 2 == 0);
256    /// assert_eq!(vec, RepeatedField::from(vec![2, 4]));
257    /// ```
258    pub fn retain<F>(&mut self, f: F)
259    where
260        F: FnMut(&T) -> bool,
261    {
262        // suboptimal
263        self.vec.truncate(self.len);
264        self.vec.retain(f);
265        self.len = self.vec.len();
266    }
267
268    /// Truncate at specified length.
269    #[inline]
270    pub fn truncate(&mut self, len: usize) {
271        if self.len > len {
272            self.len = len;
273        }
274    }
275
276    /// Reverse in place.
277    #[inline]
278    pub fn reverse(&mut self) {
279        self.as_mut_slice().reverse()
280    }
281
282    /// Immutable data iterator.
283    #[inline]
284    pub fn iter(&self) -> slice::Iter<'_, T> {
285        self.as_ref().iter()
286    }
287
288    /// Mutable data iterator.
289    #[inline]
290    pub fn iter_mut(&mut self) -> slice::IterMut<'_, T> {
291        self.as_mut_slice().iter_mut()
292    }
293
294    /// Sort elements with given comparator.
295    #[inline]
296    pub fn sort_by<F>(&mut self, compare: F)
297    where
298        F: Fn(&T, &T) -> Ordering,
299    {
300        self.as_mut_slice().sort_by(compare)
301    }
302
303    /// Get data as raw pointer.
304    #[inline]
305    pub fn as_ptr(&self) -> *const T {
306        self.vec.as_ptr()
307    }
308
309    /// Get data a mutable raw pointer.
310    #[inline]
311    pub fn as_mut_ptr(&mut self) -> *mut T {
312        self.vec.as_mut_ptr()
313    }
314}
315
316impl<T: Default + Clear> RepeatedField<T> {
317    /// Push default value.
318    /// This operation could be faster than `rf.push(Default::default())`,
319    /// because it may reuse previously allocated and cleared element.
320    pub fn push_default(&mut self) -> &mut T {
321        if self.len == self.vec.len() {
322            self.vec.push(Default::default());
323        } else {
324            self.vec[self.len].clear();
325        }
326        self.len += 1;
327        self.last_mut().unwrap()
328    }
329}
330
331impl<T> From<Vec<T>> for RepeatedField<T> {
332    #[inline]
333    fn from(values: Vec<T>) -> RepeatedField<T> {
334        RepeatedField::from_vec(values)
335    }
336}
337
338impl<'a, T: Clone> From<&'a [T]> for RepeatedField<T> {
339    #[inline]
340    fn from(values: &'a [T]) -> RepeatedField<T> {
341        RepeatedField::from_slice(values)
342    }
343}
344
345impl<T> From<RepeatedField<T>> for Vec<T> {
346    #[inline]
347    fn from(val: RepeatedField<T>) -> Self {
348        val.into_vec()
349    }
350}
351
352impl<T: Clone> RepeatedField<T> {
353    /// Copy slice data to `RepeatedField`
354    #[inline]
355    pub fn from_slice(values: &[T]) -> RepeatedField<T> {
356        RepeatedField::from_vec(values.to_vec())
357    }
358
359    /// Copy slice data to `RepeatedField`
360    #[inline]
361    pub fn from_ref<X: AsRef<[T]>>(values: X) -> RepeatedField<T> {
362        RepeatedField::from_slice(values.as_ref())
363    }
364
365    /// Copy this data into new vec.
366    #[inline]
367    pub fn to_vec(&self) -> Vec<T> {
368        self.as_ref().to_vec()
369    }
370}
371
372impl<T: Clone> Clone for RepeatedField<T> {
373    #[inline]
374    fn clone(&self) -> RepeatedField<T> {
375        RepeatedField {
376            vec: self.to_vec(),
377            len: self.len(),
378        }
379    }
380}
381
382impl<T> FromIterator<T> for RepeatedField<T> {
383    #[inline]
384    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> RepeatedField<T> {
385        RepeatedField::from_vec(FromIterator::from_iter(iter))
386    }
387}
388
389impl<'a, T> IntoIterator for &'a RepeatedField<T> {
390    type Item = &'a T;
391    type IntoIter = slice::Iter<'a, T>;
392
393    fn into_iter(self) -> slice::Iter<'a, T> {
394        self.iter()
395    }
396}
397
398impl<'a, T> IntoIterator for &'a mut RepeatedField<T> {
399    type Item = &'a mut T;
400    type IntoIter = slice::IterMut<'a, T>;
401
402    fn into_iter(self) -> slice::IterMut<'a, T> {
403        self.iter_mut()
404    }
405}
406
407impl<T> IntoIterator for RepeatedField<T> {
408    type Item = T;
409    type IntoIter = vec::IntoIter<T>;
410
411    fn into_iter(mut self) -> vec::IntoIter<T> {
412        self.vec.truncate(self.len);
413        self.vec.into_iter()
414    }
415}
416
417impl<T: PartialEq> PartialEq for RepeatedField<T> {
418    #[inline]
419    fn eq(&self, other: &RepeatedField<T>) -> bool {
420        self.as_ref() == other.as_ref()
421    }
422}
423
424impl<T: Eq> Eq for RepeatedField<T> {}
425
426impl<T: PartialEq> PartialEq<[T]> for RepeatedField<T> {
427    fn eq(&self, other: &[T]) -> bool {
428        self.as_slice() == other
429    }
430}
431
432impl<T: PartialEq> PartialEq<RepeatedField<T>> for [T] {
433    fn eq(&self, other: &RepeatedField<T>) -> bool {
434        self == other.as_slice()
435    }
436}
437
438impl<T: PartialEq> RepeatedField<T> {
439    /// True iff this container contains given element.
440    #[inline]
441    pub fn contains(&self, value: &T) -> bool {
442        self.as_ref().contains(value)
443    }
444}
445
446impl<T: Hash> Hash for RepeatedField<T> {
447    fn hash<H: Hasher>(&self, state: &mut H) {
448        self.as_ref().hash(state);
449    }
450}
451
452impl<T> AsRef<[T]> for RepeatedField<T> {
453    #[inline]
454    fn as_ref(&self) -> &[T] {
455        &self.vec[..self.len]
456    }
457}
458
459impl<T> Borrow<[T]> for RepeatedField<T> {
460    #[inline]
461    fn borrow(&self) -> &[T] {
462        &self.vec[..self.len]
463    }
464}
465
466impl<T> Deref for RepeatedField<T> {
467    type Target = [T];
468    #[inline]
469    fn deref(&self) -> &[T] {
470        &self.vec[..self.len]
471    }
472}
473
474impl<T> DerefMut for RepeatedField<T> {
475    #[inline]
476    fn deref_mut(&mut self) -> &mut [T] {
477        &mut self.vec[..self.len]
478    }
479}
480
481impl<T> Index<usize> for RepeatedField<T> {
482    type Output = T;
483
484    #[inline]
485    fn index(&self, index: usize) -> &T {
486        &self.as_ref()[index]
487    }
488}
489
490impl<T> IndexMut<usize> for RepeatedField<T> {
491    #[inline]
492    fn index_mut(&mut self, index: usize) -> &mut T {
493        &mut self.as_mut_slice()[index]
494    }
495}
496
497impl<T> Extend<T> for RepeatedField<T> {
498    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
499        self.vec.truncate(self.len);
500        self.vec.extend(iter);
501        self.len = self.vec.len();
502    }
503}
504
505impl<'a, T: Copy + 'a> Extend<&'a T> for RepeatedField<T> {
506    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
507        self.vec.truncate(self.len);
508        self.vec.extend(iter);
509        self.len = self.vec.len();
510    }
511}
512
513impl<T: fmt::Debug> fmt::Debug for RepeatedField<T> {
514    #[inline]
515    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
516        self.as_ref().fmt(f)
517    }
518}
519
520#[cfg(test)]
521mod tests {
522    use crate::repeated_field::RepeatedField;
523
524    #[test]
525    fn test_null_ptr() {
526        let mut vec: RepeatedField<&'static [u8]> = RepeatedField::new();
527        let borrowed_value = vec.push_default();
528        *borrowed_value = b"hello";
529        vec.clear();
530        let new_value = vec.push_default();
531        assert!((*new_value).is_empty());
532    }
533}
servers/repeated_field.rs

servers/
repeated_field.rs
