elastic_array/
lib.rs

1
2#![cfg_attr(not(feature = "std"), no_std)]
3
4#[cfg(feature = "std")]
5extern crate heapsize;
6
7#[cfg(not(feature = "std"))]
8extern crate alloc;
9
10// Re-export libcore using an alias so that the macros can work without
11// requiring `extern crate core` downstream.
12#[doc(hidden)]
13pub extern crate core as core_;
14
15use core_::{
16	cmp::Ordering,
17	hash::{Hash, Hasher},
18	fmt,
19	ops::Deref,
20};
21
22#[cfg(not(feature = "std"))]
23use alloc::vec::Vec;
24
25#[cfg(feature = "std")]
26use heapsize::HeapSizeOf;
27
28#[macro_export]
29macro_rules! impl_elastic_array {
30	($name: ident, $dummy: ident, $size: expr) => (
31		#[doc(hidden)]
32		enum $dummy<T> {
33			Arr([T; $size]),
34			Vec(Vec<T>)
35		}
36
37		impl<T> $dummy<T> {
38			#[doc(hidden)]
39			pub fn slice(&self) -> &[T] {
40				match *self {
41					$dummy::Arr(ref v) => v,
42					$dummy::Vec(ref v) => v
43				}
44			}
45		}
46
47		impl<T> Clone for $dummy<T> where T: Copy {
48			fn clone(&self) -> $dummy<T> {
49				match *self {
50					$dummy::Arr(ref a) => $dummy::Arr(*a),
51					$dummy::Vec(ref v) => $dummy::Vec(v.clone()),
52				}
53			}
54		}
55
56		pub struct $name<T> {
57			raw: $dummy<T>,
58			len: usize
59		}
60
61		impl<T> Eq for $name<T> where T: Eq { }
62
63		impl<T> fmt::Debug for $name<T> where T: fmt::Debug {
64			fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
65				match self.raw {
66					$dummy::Arr(ref a) => (&a[..self.len]).fmt(f),
67					$dummy::Vec(ref v) => v.fmt(f),
68				}
69			}
70		}
71
72		impl<T, U> PartialEq<U> for $name<T> where T: PartialEq, U: Deref<Target=[T]> {
73			fn eq(&self, other: &U) -> bool {
74				self.slice() == &**other
75			}
76		}
77
78		impl<T, U> PartialOrd<U> for $name<T> where T: PartialOrd, U: Deref<Target=[T]> {
79			fn partial_cmp(&self, other: &U) -> Option<Ordering> {
80				(&**self).partial_cmp(&*other)
81			}
82		}
83
84		impl<T> Ord for $name<T> where T: Ord {
85			fn cmp(&self, other: &Self) -> Ordering {
86				(&**self).cmp(&*other)
87			}
88		}
89
90		impl<T> Hash for $name<T> where T: Hash {
91			fn hash<H>(&self, state: &mut H) where H: Hasher {
92				self.slice().hash(state)
93			}
94		}
95
96		#[cfg(feature = "std")]
97		impl<T> HeapSizeOf for $name<T> where T: HeapSizeOf {
98			fn heap_size_of_children(&self) -> usize {
99				match self.raw {
100					$dummy::Arr(_) => 0,
101					$dummy::Vec(ref v) => v.heap_size_of_children()
102				}
103			}
104		}
105
106		impl<T> Clone for $name<T> where T: Copy {
107			fn clone(&self) -> $name<T> {
108				$name {
109					raw: self.raw.clone(),
110					len: self.len,
111				}
112			}
113		}
114
115		impl<T> Default for $name<T> where T: Copy + Default {
116			fn default() -> $name<T> {
117				Self::new()
118			}
119		}
120
121		impl<T> $name<T> where T: Copy + Default {
122			pub fn new() -> $name<T> {
123				$name {
124					raw: $dummy::Arr([T::default(); $size]),
125					len: 0
126				}
127			}
128
129			pub fn from_slice(slice: &[T]) -> $name<T> {
130				let mut v = $name::new();
131				v.append_slice(slice);
132				v
133			}
134
135			pub fn from_vec(vec: Vec<T>) -> $name<T> {
136				$name {
137					len: vec.len(),
138					raw: $dummy::Vec(vec),
139				}
140			}
141
142			pub fn push(&mut self, e: T) {
143				match self.raw {
144					$dummy::Arr(ref mut a) if self.len < a.len() => {
145						unsafe {
146							*a.get_unchecked_mut(self.len) = e;
147						}
148					},
149					$dummy::Arr(_) => {
150						let mut vec = Vec::new();
151						vec.reserve(self.len + 1);
152
153						unsafe {
154							$crate::core_::ptr::copy(self.raw.slice().as_ptr(), vec.as_mut_ptr(), self.len);
155							vec.set_len(self.len);
156						}
157
158						vec.push(e);
159						self.raw = $dummy::Vec(vec);
160					},
161					$dummy::Vec(ref mut v) => v.push(e)
162				}
163				self.len += 1;
164			}
165
166			pub fn pop(&mut self) -> Option<T> {
167				if self.len == 0 {
168					return None;
169				}
170
171				self.len -= 1;
172				match self.raw {
173					$dummy::Arr(ref a) => Some(a[self.len]),
174					$dummy::Vec(ref mut v) => v.pop()
175				}
176			}
177
178			pub fn clear(&mut self) {
179				self.raw = $dummy::Arr([T::default(); $size]);
180				self.len = 0;
181			}
182
183			pub fn append_slice(&mut self, elements: &[T]) {
184				let len = self.len;
185				self.insert_slice(len, elements)
186			}
187
188			pub fn into_vec(self) -> Vec<T> {
189				match self.raw {
190					$dummy::Arr(a) => {
191						let mut vec = Vec::new();
192						vec.reserve(self.len);
193						unsafe {
194							$crate::core_::ptr::copy(a.as_ptr(), vec.as_mut_ptr(), self.len);
195							vec.set_len(self.len);
196						}
197						vec
198					}
199					$dummy::Vec(v) => v
200				}
201			}
202
203			pub fn insert_slice(&mut self, index: usize, elements: &[T]) {
204				use $crate::core_::ptr;
205
206				let elen = elements.len();
207
208				if elen == 0 {
209					return;
210				}
211
212				let len = self.len;
213				assert!(index <= len);
214
215				match self.raw {
216					// it fits in array
217					$dummy::Arr(ref mut a) if len + elen <= a.len() => unsafe {
218						let p = a.as_mut_ptr().offset(index as isize);
219						let ep = elements.as_ptr();
220
221						// shift everything by elen, to make space
222						ptr::copy(p, p.offset(elen as isize), len - index);
223						// write new elements
224						ptr::copy(ep, p, elen);
225					},
226					// it deosn't, must be rewritten to vec
227					$dummy::Arr(_) => unsafe {
228						let mut vec = Vec::new();
229						vec.reserve(self.len + elen);
230						{
231							let p = vec.as_mut_ptr();
232							let ob = self.raw.slice().as_ptr();
233							let ep = elements.as_ptr();
234							let oe = ob.offset(index as isize);
235
236							// copy begining of an array
237							ptr::copy(ob, p, index);
238
239							// copy new elements
240							ptr::copy(ep, p.offset(index as isize), elen);
241
242							// copy end of an array
243							ptr::copy(oe, p.offset((index + elen) as isize), len - index);
244						}
245						vec.set_len(self.len + elen);
246						self.raw = $dummy::Vec(vec);
247					},
248					// just insert it in to vec
249					$dummy::Vec(ref mut v) => unsafe {
250						v.reserve(elen);
251
252						let p = v.as_mut_ptr().offset(index as isize);
253						let ep = elements.as_ptr();
254
255						// shift everything by elen, to make space
256						ptr::copy(p, p.offset(elen as isize), len - index);
257						// write new elements
258						ptr::copy(ep, p, elen);
259
260						v.set_len(self.len + elen);
261					}
262				}
263				self.len += elen;
264			}
265		}
266
267		impl<T> $name<T> {
268			fn slice(&self) -> &[T] {
269				match self.raw {
270					$dummy::Arr(ref a) => &a[..self.len],
271					$dummy::Vec(ref v) => v
272				}
273			}
274		}
275
276		impl<T> Deref for $name<T> {
277			type Target = [T];
278
279			#[inline]
280			fn deref(&self) -> &[T] {
281				self.slice()
282			}
283		}
284
285		impl<T> $crate::core_::convert::AsRef<[T]> for $name<T> {
286			#[inline]
287			fn as_ref(&self) -> &[T] {
288				self.slice()
289			}
290		}
291
292		impl<T> $crate::core_::borrow::Borrow<[T]> for $name<T> {
293			#[inline]
294			fn borrow(&self) -> &[T] {
295				self.slice()
296			}
297		}
298
299		impl<T> $crate::core_::ops::DerefMut for $name<T> {
300			#[inline]
301			fn deref_mut(&mut self) -> &mut [T] {
302				match self.raw {
303					$dummy::Arr(ref mut a) => &mut a[..self.len],
304					$dummy::Vec(ref mut v) => v
305				}
306			}
307		}
308
309		impl<'a, T> From<&'a [T]> for $name<T> where T: 'a + Copy + Default {
310			fn from(s: &'a [T]) -> Self { Self::from_slice(s) }
311		}
312	)
313}
314
315impl_elastic_array!(ElasticArray2, ElasticArray2Dummy, 2);
316impl_elastic_array!(ElasticArray4, ElasticArray4Dummy, 4);
317impl_elastic_array!(ElasticArray8, ElasticArray8Dummy, 8);
318impl_elastic_array!(ElasticArray16, ElasticArray16Dummy, 16);
319impl_elastic_array!(ElasticArray32, ElasticArray32Dummy, 32);
320impl_elastic_array!(ElasticArray36, ElasticArray36Dummy, 36);
321impl_elastic_array!(ElasticArray64, ElasticArray64Dummy, 64);
322impl_elastic_array!(ElasticArray128, ElasticArray128Dummy, 128);
323impl_elastic_array!(ElasticArray256, ElasticArray256Dummy, 256);
324impl_elastic_array!(ElasticArray512, ElasticArray512Dummy, 512);
325impl_elastic_array!(ElasticArray1024, ElasticArray1024Dummy, 1024);
326impl_elastic_array!(ElasticArray2048, ElasticArray2048Dummy, 2048);
327
328#[cfg(test)]
329mod tests {
330
331	type BytesShort = super::ElasticArray2<u8>;
332
333	#[test]
334	fn it_works() {
335		let mut bytes = BytesShort::new();
336		assert_eq!(bytes.len(), 0);
337		bytes.push(1);
338		assert_eq!(bytes.len(), 1);
339		assert_eq!(bytes[0], 1);
340		bytes.push(2);
341		assert_eq!(bytes[1], 2);
342		assert_eq!(bytes.len(), 2);
343		bytes.push(3);
344		assert_eq!(bytes[2], 3);
345		assert_eq!(bytes.len(), 3);
346		assert_eq!(bytes.pop(), Some(3));
347		assert_eq!(bytes.len(), 2);
348		assert_eq!(bytes.pop(), Some(2));
349		assert_eq!(bytes.pop(), Some(1));
350		assert_eq!(bytes.pop(), None);
351	}
352
353	#[test]
354	fn test_insert_slice() {
355		let mut bytes = BytesShort::new();
356		bytes.push(1);
357		bytes.push(2);
358		bytes.insert_slice(1, &[3, 4]);
359		assert_eq!(bytes.len(), 4);
360		let r: &[u8] = &bytes;
361		assert_eq!(r, &[1, 3, 4, 2]);
362	}
363
364	#[test]
365	fn append_slice() {
366		let mut bytes = BytesShort::new();
367		bytes.push(1);
368		bytes.append_slice(&[3, 4]);
369		let r: &[u8] = &bytes;
370		assert_eq!(r.len(), 3);
371		assert_eq!(r, &[1, 3 ,4]);
372	}
373
374	#[test]
375	fn use_in_map() {
376		#[cfg(feature = "std")]
377		use std::collections::BTreeMap;
378		#[cfg(not(feature = "std"))]
379		use alloc::collections::BTreeMap;
380		use ::core_::borrow::Borrow;
381		let mut map: BTreeMap<BytesShort, i32> = Default::default();
382		let mut bytes = BytesShort::new();
383		bytes.append_slice(&[3, 4]);
384		assert_eq!(bytes.borrow() as &[u8], &[3, 4][..]);
385		map.insert(bytes, 1);
386		assert_eq!(map.get(&[3, 4][..]), Some(&1i32));
387	}
388
389}
elastic_array/lib.rs

elastic_array/
lib.rs
