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
35/// anything that can be cleared
36pub trait Clear {
37    /// Clear this make, make it equivalent to newly created object.
38    fn clear(&mut self);
39}
40
41impl Clear for &[u8] {
42    fn clear(&mut self) {}
43}
44
45impl<T> Clear for Option<T> {
46    fn clear(&mut self) {
47        self.take();
48    }
49}
50
51impl Clear for String {
52    fn clear(&mut self) {
53        String::clear(self);
54    }
55}
56
57impl<T> Clear for Vec<T> {
58    fn clear(&mut self) {
59        Vec::clear(self);
60    }
61}
62
63impl Clear for Bytes {
64    fn clear(&mut self) {
65        Bytes::clear(self);
66    }
67}
68
69/// Wrapper around vector to avoid deallocations on clear.
70pub struct RepeatedField<T> {
71    vec: Vec<T>,
72    len: usize,
73}
74
75impl<T> RepeatedField<T> {
76    /// Return number of elements in this container.
77    #[inline]
78    pub fn len(&self) -> usize {
79        self.len
80    }
81
82    /// Returns true if this container is empty.
83    #[inline]
84    pub fn is_empty(&self) -> bool {
85        self.len == 0
86    }
87
88    /// Clear.
89    #[inline]
90    pub fn clear(&mut self) {
91        self.len = 0;
92    }
93}
94
95impl<T> Default for RepeatedField<T> {
96    #[inline]
97    fn default() -> RepeatedField<T> {
98        RepeatedField {
99            vec: Vec::new(),
100            len: 0,
101        }
102    }
103}
104
105impl<T> RepeatedField<T> {
106    /// Create new empty container.
107    #[inline]
108    pub fn new() -> RepeatedField<T> {
109        Default::default()
110    }
111
112    /// Create a contained with data from given vec.
113    #[inline]
114    pub fn from_vec(vec: Vec<T>) -> RepeatedField<T> {
115        let len = vec.len();
116        RepeatedField { vec, len }
117    }
118
119    /// Convert data into vec.
120    #[inline]
121    pub fn into_vec(self) -> Vec<T> {
122        let mut vec = self.vec;
123        vec.truncate(self.len);
124        vec
125    }
126
127    /// Return current capacity.
128    #[inline]
129    pub fn capacity(&self) -> usize {
130        self.vec.capacity()
131    }
132
133    /// View data as slice.
134    #[inline]
135    pub fn as_slice(&self) -> &[T] {
136        &self.vec[..self.len]
137    }
138
139    /// View data as mutable slice.
140    #[inline]
141    pub fn as_mut_slice(&mut self) -> &mut [T] {
142        &mut self.vec[..self.len]
143    }
144
145    /// Get subslice of this container.
146    #[inline]
147    pub fn slice(&self, start: usize, end: usize) -> &[T] {
148        &self.as_ref()[start..end]
149    }
150
151    /// Get slice from given index.
152    #[inline]
153    pub fn slice_from(&self, start: usize) -> &[T] {
154        &self.as_ref()[start..]
155    }
156
157    /// Get slice to given index.
158    #[inline]
159    pub fn slice_to(&self, end: usize) -> &[T] {
160        &self.as_ref()[..end]
161    }
162
163    /// View this container as two slices split at given index.
164    #[inline]
165    pub fn split_at(&self, mid: usize) -> (&[T], &[T]) {
166        self.as_ref().split_at(mid)
167    }
168
169    /// View this container as two mutable slices split at given index.
170    #[inline]
171    pub fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
172        self.as_mut_slice().split_at_mut(mid)
173    }
174
175    /// View all but first elements of this container.
176    #[inline]
177    pub fn tail(&self) -> &[T] {
178        &self.as_ref()[1..]
179    }
180
181    /// Last element of this container.
182    #[inline]
183    pub fn last(&self) -> Option<&T> {
184        self.as_ref().last()
185    }
186
187    /// Mutable last element of this container.
188    #[inline]
189    pub fn last_mut(&mut self) -> Option<&mut T> {
190        self.as_mut_slice().last_mut()
191    }
192
193    /// View all but last elements of this container.
194    #[inline]
195    pub fn init(&self) -> &[T] {
196        let s = self.as_ref();
197        &s[0..s.len() - 1]
198    }
199
200    /// Push an element to the end.
201    #[inline]
202    pub fn push(&mut self, value: T) {
203        if self.len == self.vec.len() {
204            self.vec.push(value);
205        } else {
206            self.vec[self.len] = value;
207        }
208        self.len += 1;
209    }
210
211    /// Pop last element.
212    #[inline]
213    pub fn pop(&mut self) -> Option<T> {
214        if self.len == 0 {
215            None
216        } else {
217            self.vec.truncate(self.len);
218            self.len -= 1;
219            self.vec.pop()
220        }
221    }
222
223    /// Insert an element at specified position.
224    #[inline]
225    pub fn insert(&mut self, index: usize, value: T) {
226        assert!(index <= self.len);
227        self.vec.insert(index, value);
228        self.len += 1;
229    }
230
231    /// Remove an element from specified position.
232    #[inline]
233    pub fn remove(&mut self, index: usize) -> T {
234        assert!(index < self.len);
235        self.len -= 1;
236        self.vec.remove(index)
237    }
238
239    /// Retains only the elements specified by the predicate.
240    ///
241    /// In other words, remove all elements `e` such that `f(&e)` returns `false`.
242    /// This method operates in place, visiting each element exactly once in the
243    /// original order, and preserves the order of the retained elements.
244    ///
245    /// # Examples
246    ///
247    /// ```
248    /// use servers::repeated_field::RepeatedField;
249    ///
250    /// let mut vec = RepeatedField::from(vec![1, 2, 3, 4]);
251    /// vec.retain(|&x| x % 2 == 0);
252    /// assert_eq!(vec, RepeatedField::from(vec![2, 4]));
253    /// ```
254    pub fn retain<F>(&mut self, f: F)
255    where
256        F: FnMut(&T) -> bool,
257    {
258        // suboptimal
259        self.vec.truncate(self.len);
260        self.vec.retain(f);
261        self.len = self.vec.len();
262    }
263
264    /// Truncate at specified length.
265    #[inline]
266    pub fn truncate(&mut self, len: usize) {
267        if self.len > len {
268            self.len = len;
269        }
270    }
271
272    /// Reverse in place.
273    #[inline]
274    pub fn reverse(&mut self) {
275        self.as_mut_slice().reverse()
276    }
277
278    /// Immutable data iterator.
279    #[inline]
280    pub fn iter(&self) -> slice::Iter<T> {
281        self.as_ref().iter()
282    }
283
284    /// Mutable data iterator.
285    #[inline]
286    pub fn iter_mut(&mut self) -> slice::IterMut<T> {
287        self.as_mut_slice().iter_mut()
288    }
289
290    /// Sort elements with given comparator.
291    #[inline]
292    pub fn sort_by<F>(&mut self, compare: F)
293    where
294        F: Fn(&T, &T) -> Ordering,
295    {
296        self.as_mut_slice().sort_by(compare)
297    }
298
299    /// Get data as raw pointer.
300    #[inline]
301    pub fn as_ptr(&self) -> *const T {
302        self.vec.as_ptr()
303    }
304
305    /// Get data a mutable raw pointer.
306    #[inline]
307    pub fn as_mut_ptr(&mut self) -> *mut T {
308        self.vec.as_mut_ptr()
309    }
310}
311
312impl<T: Default + Clear> RepeatedField<T> {
313    /// Push default value.
314    /// This operation could be faster than `rf.push(Default::default())`,
315    /// because it may reuse previously allocated and cleared element.
316    pub fn push_default(&mut self) -> &mut T {
317        if self.len == self.vec.len() {
318            self.vec.push(Default::default());
319        } else {
320            self.vec[self.len].clear();
321        }
322        self.len += 1;
323        self.last_mut().unwrap()
324    }
325}
326
327impl<T> From<Vec<T>> for RepeatedField<T> {
328    #[inline]
329    fn from(values: Vec<T>) -> RepeatedField<T> {
330        RepeatedField::from_vec(values)
331    }
332}
333
334impl<'a, T: Clone> From<&'a [T]> for RepeatedField<T> {
335    #[inline]
336    fn from(values: &'a [T]) -> RepeatedField<T> {
337        RepeatedField::from_slice(values)
338    }
339}
340
341impl<T> From<RepeatedField<T>> for Vec<T> {
342    #[inline]
343    fn from(val: RepeatedField<T>) -> Self {
344        val.into_vec()
345    }
346}
347
348impl<T: Clone> RepeatedField<T> {
349    /// Copy slice data to `RepeatedField`
350    #[inline]
351    pub fn from_slice(values: &[T]) -> RepeatedField<T> {
352        RepeatedField::from_vec(values.to_vec())
353    }
354
355    /// Copy slice data to `RepeatedField`
356    #[inline]
357    pub fn from_ref<X: AsRef<[T]>>(values: X) -> RepeatedField<T> {
358        RepeatedField::from_slice(values.as_ref())
359    }
360
361    /// Copy this data into new vec.
362    #[inline]
363    pub fn to_vec(&self) -> Vec<T> {
364        self.as_ref().to_vec()
365    }
366}
367
368impl<T: Clone> Clone for RepeatedField<T> {
369    #[inline]
370    fn clone(&self) -> RepeatedField<T> {
371        RepeatedField {
372            vec: self.to_vec(),
373            len: self.len(),
374        }
375    }
376}
377
378impl<T> FromIterator<T> for RepeatedField<T> {
379    #[inline]
380    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> RepeatedField<T> {
381        RepeatedField::from_vec(FromIterator::from_iter(iter))
382    }
383}
384
385impl<'a, T> IntoIterator for &'a RepeatedField<T> {
386    type Item = &'a T;
387    type IntoIter = slice::Iter<'a, T>;
388
389    fn into_iter(self) -> slice::Iter<'a, T> {
390        self.iter()
391    }
392}
393
394impl<'a, T> IntoIterator for &'a mut RepeatedField<T> {
395    type Item = &'a mut T;
396    type IntoIter = slice::IterMut<'a, T>;
397
398    fn into_iter(self) -> slice::IterMut<'a, T> {
399        self.iter_mut()
400    }
401}
402
403impl<T> IntoIterator for RepeatedField<T> {
404    type Item = T;
405    type IntoIter = vec::IntoIter<T>;
406
407    fn into_iter(mut self) -> vec::IntoIter<T> {
408        self.vec.truncate(self.len);
409        self.vec.into_iter()
410    }
411}
412
413impl<T: PartialEq> PartialEq for RepeatedField<T> {
414    #[inline]
415    fn eq(&self, other: &RepeatedField<T>) -> bool {
416        self.as_ref() == other.as_ref()
417    }
418}
419
420impl<T: Eq> Eq for RepeatedField<T> {}
421
422impl<T: PartialEq> PartialEq<[T]> for RepeatedField<T> {
423    fn eq(&self, other: &[T]) -> bool {
424        self.as_slice() == other
425    }
426}
427
428impl<T: PartialEq> PartialEq<RepeatedField<T>> for [T] {
429    fn eq(&self, other: &RepeatedField<T>) -> bool {
430        self == other.as_slice()
431    }
432}
433
434impl<T: PartialEq> RepeatedField<T> {
435    /// True iff this container contains given element.
436    #[inline]
437    pub fn contains(&self, value: &T) -> bool {
438        self.as_ref().contains(value)
439    }
440}
441
442impl<T: Hash> Hash for RepeatedField<T> {
443    fn hash<H: Hasher>(&self, state: &mut H) {
444        self.as_ref().hash(state);
445    }
446}
447
448impl<T> AsRef<[T]> for RepeatedField<T> {
449    #[inline]
450    fn as_ref(&self) -> &[T] {
451        &self.vec[..self.len]
452    }
453}
454
455impl<T> Borrow<[T]> for RepeatedField<T> {
456    #[inline]
457    fn borrow(&self) -> &[T] {
458        &self.vec[..self.len]
459    }
460}
461
462impl<T> Deref for RepeatedField<T> {
463    type Target = [T];
464    #[inline]
465    fn deref(&self) -> &[T] {
466        &self.vec[..self.len]
467    }
468}
469
470impl<T> DerefMut for RepeatedField<T> {
471    #[inline]
472    fn deref_mut(&mut self) -> &mut [T] {
473        &mut self.vec[..self.len]
474    }
475}
476
477impl<T> Index<usize> for RepeatedField<T> {
478    type Output = T;
479
480    #[inline]
481    fn index(&self, index: usize) -> &T {
482        &self.as_ref()[index]
483    }
484}
485
486impl<T> IndexMut<usize> for RepeatedField<T> {
487    #[inline]
488    fn index_mut(&mut self, index: usize) -> &mut T {
489        &mut self.as_mut_slice()[index]
490    }
491}
492
493impl<T> Extend<T> for RepeatedField<T> {
494    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
495        self.vec.truncate(self.len);
496        self.vec.extend(iter);
497        self.len = self.vec.len();
498    }
499}
500
501impl<'a, T: Copy + 'a> Extend<&'a T> for RepeatedField<T> {
502    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
503        self.vec.truncate(self.len);
504        self.vec.extend(iter);
505        self.len = self.vec.len();
506    }
507}
508
509impl<T: fmt::Debug> fmt::Debug for RepeatedField<T> {
510    #[inline]
511    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
512        self.as_ref().fmt(f)
513    }
514}