bumpy_vector/lib.rs
1//! [](https://crates.io/crates/bumpy_vector)
2//!
3//! A vector-like object where elements can be larger than one item. We use
4//! this primarily to represent objects in a binary that are made up of one
5//! or more bytes.
6//!
7//! # Goal
8//!
9//! [h2gb](https://github.com/h2gb/libh2gb) is a tool for analyzing binary
10//! files. Importantly, a binary file is a series of objects, each of which
11//! take up some number of bytes. We need a datatype to represent this unusual
12//! requirement, hence coming up with BumpyVector!
13//!
14//! # Usage
15//!
16//! Instantiate with a maximum size, then use somewhat like a vector:
17//!
18//! ```
19//! use bumpy_vector::{BumpyEntry, BumpyVector};
20//!
21//! // Instantiate with a maximum size of 100 and a type of String
22//! let mut v: BumpyVector<String> = BumpyVector::new(100);
23//!
24//! // Create a 10-byte entry at the start
25//! let entry: BumpyEntry<String> = BumpyEntry {
26//! entry: String::from("hello"),
27//! size: 10,
28//! index: 0,
29//! };
30//!
31//! // Insert it into the BumpyVector
32//! assert!(v.insert(entry).is_ok());
33//!
34//! // Create another entry, this time from a tuple, that overlaps the first
35//! let entry: BumpyEntry<String> = (String::from("error"), 1, 5).into();
36//! assert!(v.insert(entry).is_err());
37//!
38//! // Create an entry that's off the end of the object
39//! let entry: BumpyEntry<String> = (String::from("error"), 1000, 5).into();
40//! assert!(v.insert(entry).is_err());
41//!
42//! // There is still one entry in this vector
43//! assert_eq!(1, v.len());
44//! ```
45//!
46//! # Serialize / deserialize
47//!
48//! When installed with the 'serialize' feature:
49//!
50//! ```toml
51//! bumpy_vector = { version = "~0.0.0", features = ["serialize"] }
52//! ```
53//!
54//! Serialization support using [serde](https://serde.rs/) is enabled. The
55//! `BumpyVector` can be serialized with any of the serializers that Serde
56//! supports, such as [ron](https://github.com/ron-rs/ron):
57//!
58//! ```ignore
59//! use bumpy_vector::BumpyVector;
60//!
61//! // Assumes "serialize" feature is enabled: `bumpy_vector = { features = ["serialize"] }`
62//! fn main() {
63//! let mut h: BumpyVector<String> = BumpyVector::new(10);
64//! h.insert((String::from("a"), 1, 2).into()).unwrap();
65//!
66//! // Serialize
67//! let serialized = ron::ser::to_string(&h).unwrap();
68//!
69//! // Deserialize
70//! let h: BumpyVector<String> = ron::de::from_str(&serialized).unwrap();
71//! }
72//! ```
73
74use std::collections::HashMap;
75
76#[cfg(feature = "serialize")]
77use serde::{Serialize, Deserialize};
78
79/// Represents a single entry.
80///
81/// An entry is comprised of an object of type `T`, a starting index, and a
82/// size.
83///
84/// # Example 1
85///
86/// Creating a basic entry is very straight forward:
87///
88/// ```
89/// use bumpy_vector::BumpyEntry;
90///
91/// let e: BumpyEntry<&str> = BumpyEntry {
92/// entry: "hello",
93/// index: 0,
94/// size: 1,
95/// };
96/// ```
97///
98/// # Example 2
99///
100/// For convenience, you can create an entry from a (T, usize, usize) tuple:
101///
102/// ```
103/// use bumpy_vector::BumpyEntry;
104///
105/// let e: BumpyEntry<&str> = ("hello", 0, 1).into();
106/// ```
107#[derive(Debug, Default, Clone)]
108#[cfg_attr(feature = "serialize", derive(Serialize, Deserialize))]
109pub struct BumpyEntry<T> {
110 pub entry: T,
111 pub index: usize,
112 pub size: usize,
113}
114
115impl<T> From<(T, usize, usize)> for BumpyEntry<T> {
116 fn from(o: (T, usize, usize)) -> Self {
117 BumpyEntry {
118 entry: o.0,
119 index: o.1,
120 size: o.2,
121 }
122 }
123}
124
125/// Represents an instance of a Bumpy Vector
126#[derive(Debug, Default, Clone)]
127#[cfg_attr(feature = "serialize", derive(Serialize, Deserialize))]
128pub struct BumpyVector<T> {
129 /// The data is represented by a HashMap, where the index is the key and
130 /// a BumpyEntry is the object.
131 data: HashMap<usize, BumpyEntry<T>>,
132
133 /// The maximum size.
134 max_size: usize,
135}
136
137/// Implement the object.
138impl<'a, T> BumpyVector<T> {
139 /// Create a new instance of BumpyVector.
140 ///
141 /// The range of the vector goes from `0` to `max_size - 1`. If any
142 /// elements beyond the end are accessed, an error will be returned.
143 pub fn new(max_size: usize) -> Self {
144 BumpyVector {
145 data: HashMap::new(),
146 max_size: max_size,
147 }
148 }
149
150 /// Get the object that starts at or overlaps the starting index.
151 ///
152 /// This private method is the core of BumpyVector. Given an arbitrary
153 /// offset within the BumpyVector, determine which entry exists in it (even
154 /// if the entry starts to the "left").
155 ///
156 /// The initial implementation is somewhat naive: loop from the
157 /// `starting_index` to 0, searching for an object. If found, check the
158 /// object's size to ensure it overlaps the `starting_index`.
159 ///
160 /// This will be a good place to optimize later.
161 fn get_entry_start(&self, starting_index: usize) -> Option<usize> {
162 // Keep a handle to the starting index
163 let mut index = starting_index;
164
165 // Loop right to zero
166 loop {
167 // Check if we have data at the index
168 match self.data.get(&index) {
169 // If there's a value, we're set!
170 Some(d) => {
171 // If we were too far away, it doesn't count. No value!
172 if d.size <= (starting_index - index) {
173 return None;
174 }
175
176 // Otherwise, we have the real index!
177 return Some(index);
178 },
179
180 // If there's no value, we keep going
181 None => {
182 if index == 0 {
183 return None;
184 }
185
186 index -= 1;
187 },
188 };
189 }
190 }
191
192 /// Insert a new entry.
193 ///
194 /// # Return
195 ///
196 /// Returns `Ok(())` if successfully inserted. If it would overlap another
197 /// entry or exceed `max_size`, return `Err(&str)` with a descriptive error
198 /// string.
199 ///
200 /// Size must be at least 1.
201 ///
202 /// # Example
203 ///
204 /// ```
205 /// use bumpy_vector::{BumpyEntry, BumpyVector};
206 ///
207 /// // Create a 10-byte `BumpyVector`
208 /// let mut v: BumpyVector<&str> = BumpyVector::new(10);
209 ///
210 /// // Insert a 2-byte value starting at index 5 (using BumpyEntry directly)
211 /// assert!(v.insert(BumpyEntry { entry: "hello", index: 5, size: 2 }).is_ok());
212 ///
213 /// // Insert another 2-byte value starting at index 7 (using into())
214 /// assert!(v.insert(("hello", 7, 2).into()).is_ok());
215 ///
216 /// // Fail to insert a value that would overlap the first
217 /// assert!(v.insert(("hello", 4, 2).into()).is_err());
218 ///
219 /// // Fail to insert a value that would overlap the second
220 /// assert!(v.insert(("hello", 6, 1).into()).is_err());
221 ///
222 /// // Fail to insert a value that would go out of bounds
223 /// assert!(v.insert(("hello", 100, 1).into()).is_err());
224 /// ```
225 pub fn insert(&mut self, entry: BumpyEntry<T>) -> Result<(), &'static str> {
226 if entry.size == 0 {
227 return Err("Zero is an invalid size for an entry");
228 }
229
230 if entry.index + entry.size > self.max_size {
231 return Err("Invalid entry: entry exceeds max size");
232 }
233
234 // Check if there's a conflict on the left
235 if self.get_entry_start(entry.index).is_some() {
236 return Err("Invalid entry: overlaps another object");
237 }
238
239 // Check if there's a conflict on the right
240 for x in entry.index..(entry.index + entry.size) {
241 if self.data.contains_key(&x) {
242 return Err("Invalid entry: overlaps another object");
243 }
244 }
245
246 // We're good, so create an entry!
247 self.data.insert(entry.index, entry);
248
249 Ok(())
250 }
251
252 /// Remove and return the entry at `index`.
253 ///
254 /// Note that the entry doesn't necessarily need to *start* at `index`,
255 /// just overlap it.
256 ///
257 /// # Example
258 ///
259 /// ```
260 /// use bumpy_vector::BumpyVector;
261 ///
262 /// // Create a 10-byte `BumpyVector`
263 /// let mut v: BumpyVector<&str> = BumpyVector::new(10);
264 ///
265 /// // Insert some data
266 /// v.insert(("hello", 0, 4).into()).unwrap();
267 /// v.insert(("hello", 4, 4).into()).unwrap();
268 ///
269 /// assert!(v.remove(0).is_some());
270 /// assert!(v.remove(0).is_none());
271 ///
272 /// assert!(v.remove(6).is_some());
273 /// assert!(v.remove(6).is_none());
274 /// ```
275 pub fn remove(&mut self, index: usize) -> Option<BumpyEntry<T>> {
276 // Try to get the real offset
277 let real_offset = self.get_entry_start(index);
278
279 // If there's no element, return none
280 if let Some(o) = real_offset {
281 // Remove it!
282 if let Some(d) = self.data.remove(&o) {
283 return Some(d);
284 }
285 }
286
287 None
288 }
289
290 /// Remove and return a range of entries.
291 ///
292 /// # Example
293 ///
294 /// ```
295 /// use bumpy_vector::BumpyVector;
296 ///
297 /// // Create a 10-byte `BumpyVector`
298 /// let mut v: BumpyVector<&str> = BumpyVector::new(10);
299 ///
300 /// // Insert some data
301 /// v.insert(("hello", 0, 4).into()).unwrap();
302 /// v.insert(("hello", 4, 4).into()).unwrap();
303 ///
304 /// assert_eq!(2, v.remove_range(0, 10).len());
305 /// assert_eq!(0, v.remove_range(0, 10).len());
306 /// ```
307 pub fn remove_range(&mut self, index: usize, length: usize) -> Vec<BumpyEntry<T>> {
308 let mut result: Vec<BumpyEntry<T>> = Vec::new();
309
310 for i in index..(index+length) {
311 if let Some(e) = self.remove(i) {
312 result.push(e);
313 }
314 }
315
316 result
317 }
318
319 /// Return a reference to an entry at the given index.
320 ///
321 /// Note that the entry doesn't necessarily need to *start* at the given
322 /// index, it can simply be contained there.
323 ///
324 /// # Example
325 ///
326 /// ```
327 /// use bumpy_vector::BumpyVector;
328 ///
329 /// // Create a 10-byte `BumpyVector`
330 /// let mut v: BumpyVector<&str> = BumpyVector::new(10);
331 ///
332 /// // Insert some data
333 /// v.insert(("hello", 0, 4).into()).unwrap();
334 ///
335 /// assert!(v.get(0).is_some());
336 /// assert!(v.get(1).is_some());
337 /// assert!(v.get(2).is_some());
338 /// assert!(v.get(3).is_some());
339 /// assert!(v.get(4).is_none());
340 /// assert!(v.get(5).is_none());
341 ///
342 /// assert_eq!("hello", v.get(0).unwrap().entry);
343 /// assert_eq!("hello", v.get(1).unwrap().entry);
344 /// assert_eq!("hello", v.get(2).unwrap().entry);
345 /// assert_eq!("hello", v.get(3).unwrap().entry);
346 /// ```
347 pub fn get(&self, index: usize) -> Option<&BumpyEntry<T>> {
348 // Try to get the real offset
349 let real_offset = self.get_entry_start(index);
350
351 // If there's no element, return none
352 if let Some(o) = real_offset {
353 // Get the entry itself from the address
354 return self.data.get(&o);
355 }
356
357 None
358 }
359
360 /// Return a mutable reference to an entry at the given index.
361 ///
362 /// # Example
363 ///
364 /// ```
365 /// use bumpy_vector::BumpyVector;
366 ///
367 /// // Create a small BumpyVector
368 /// let mut h: BumpyVector<String> = BumpyVector::new(10);
369 ///
370 /// // Insert a string to the start
371 /// h.insert((String::from("hello"), 0, 2).into()).unwrap();
372 /// assert_eq!("hello", h.get(0).unwrap().entry);
373 /// assert_eq!("hello", h.get(1).unwrap().entry);
374 ///
375 /// // Get a mutable reference to the string
376 /// let s = h.get_mut(1).unwrap();
377 ///
378 /// // Modify it somehow
379 /// s.entry.make_ascii_uppercase();
380 ///
381 /// // Verify it's changed
382 /// assert_eq!("HELLO", h.get(0).unwrap().entry);
383 /// assert_eq!("HELLO", h.get(1).unwrap().entry);
384 /// ```
385 pub fn get_mut(&mut self, index: usize) -> Option<&mut BumpyEntry<T>> {
386 // Try to get the real offset
387 let real_offset = self.get_entry_start(index);
388
389 // If there's no element, return none
390 if let Some(o) = real_offset {
391 // Get the entry itself from the address
392 return self.data.get_mut(&o);
393 }
394
395 None
396 }
397
398 /// Return a reference to an entry that *starts at* the given index.
399 ///
400 /// # Example
401 ///
402 /// ```
403 /// use bumpy_vector::BumpyVector;
404 ///
405 /// // Create a 10-byte `BumpyVector`
406 /// let mut v: BumpyVector<&str> = BumpyVector::new(10);
407 ///
408 /// // Insert some data
409 /// v.insert(("hello", 0, 4).into()).unwrap();
410 ///
411 /// assert!(v.get_exact(0).is_some());
412 /// assert!(v.get_exact(1).is_none());
413 /// assert!(v.get_exact(2).is_none());
414 /// assert!(v.get_exact(3).is_none());
415 /// assert!(v.get_exact(4).is_none());
416 /// assert!(v.get_exact(5).is_none());
417 ///
418 /// assert_eq!("hello", v.get_exact(0).unwrap().entry);
419 /// ```
420 pub fn get_exact(&self, index: usize) -> Option<&BumpyEntry<T>> {
421 self.data.get(&index)
422 }
423
424 /// Return a mutable reference to an entry at exactly the given index.
425 ///
426 /// # Example
427 ///
428 /// ```
429 /// use bumpy_vector::BumpyVector;
430 ///
431 /// // Create a small BumpyVector
432 /// let mut h: BumpyVector<String> = BumpyVector::new(10);
433 ///
434 /// // Insert a string to the start
435 /// h.insert((String::from("hello"), 0, 2).into()).unwrap();
436 /// assert_eq!("hello", h.get_exact(0).unwrap().entry);
437 /// assert!(h.get_exact(1).is_none());
438 ///
439 /// // Get a mutable reference to the string
440 /// let s = h.get_exact_mut(0).unwrap();
441 ///
442 /// // Modify it somehow
443 /// s.entry.make_ascii_uppercase();
444 ///
445 /// // Verify it's changed
446 /// assert_eq!("HELLO", h.get_exact(0).unwrap().entry);
447 /// assert!(h.get_exact(1).is_none());
448 /// ```
449 pub fn get_exact_mut(&mut self, index: usize) -> Option<&mut BumpyEntry<T>> {
450 self.data.get_mut(&index)
451 }
452
453 /// Return a vector of entries within the given range.
454 ///
455 /// Note that the first entry doesn't need to *start* at the given index
456 /// it can simply be contained there.
457 ///
458 /// # Parameters
459 ///
460 /// * `start` - The starting index.
461 /// * `length` - The length to retrieve.
462 ///
463 /// # Example
464 ///
465 /// ```
466 /// use bumpy_vector::BumpyVector;
467 ///
468 /// // Create a 10-byte `BumpyVector`
469 /// let mut v: BumpyVector<&str> = BumpyVector::new(10);
470 ///
471 /// // Insert some data with a gap in the middle
472 /// v.insert(("hello", 0, 2).into()).unwrap();
473 /// v.insert(("hello", 4, 2).into()).unwrap();
474 ///
475 /// assert_eq!(1, v.get_range(0, 1).len());
476 /// assert_eq!(1, v.get_range(0, 2).len());
477 /// assert_eq!(1, v.get_range(0, 3).len());
478 /// assert_eq!(1, v.get_range(0, 4).len());
479 /// assert_eq!(2, v.get_range(0, 5).len());
480 /// ```
481 ///
482 /// # Panics
483 ///
484 /// Panics if an entry's size is 0. That shouldn't be possible short of
485 /// tinkering with internal state (most likely modifying serialized data).
486 pub fn get_range(&self, start: usize, length: usize) -> Vec<&BumpyEntry<T>> {
487 // We're stuffing all of our data into a vector to iterate over it
488 let mut result: Vec<&BumpyEntry<T>> = Vec::new();
489
490 // Start at the first entry left of what they wanted, if it exists
491 let mut i = match self.get_entry_start(start) {
492 Some(e) => e,
493 None => start,
494 };
495
496 // Loop up to <length> bytes after the starting index
497 while i < start + length && i < self.max_size {
498 // Pull the entry out, if it exists
499 if let Some(e) = self.data.get(&i) {
500 // Add the entry to the vector, and jump over it
501 result.push(e);
502
503 // Prevent an infinite loop
504 if e.size == 0 {
505 panic!("Entry size cannot be 0!");
506 }
507
508 i += e.size;
509 } else {
510 i += 1;
511 }
512 }
513
514 result
515 }
516
517 /// Returns the number of entries.
518 pub fn len(&self) -> usize {
519 // Return the number of entries
520 return self.data.len();
521 }
522
523 pub fn max_size(&self) -> usize {
524 return self.max_size;
525 }
526}
527
528/// Convert into an iterator.
529///
530/// Naively iterate across all entries, move them into a `Vec<_>`, and convert
531/// that vector into an iterator.
532///
533impl<'a, T> IntoIterator for &'a BumpyVector<T> {
534 type Item = &'a BumpyEntry<T>;
535 type IntoIter = std::vec::IntoIter<&'a BumpyEntry<T>>;
536
537 fn into_iter(self) -> std::vec::IntoIter<&'a BumpyEntry<T>> {
538 return self.get_range(0, self.max_size).into_iter();
539 }
540}
541
542#[cfg(test)]
543mod tests {
544 use super::*;
545 use pretty_assertions::assert_eq;
546
547 #[test]
548 fn test_insert() {
549 let mut h: BumpyVector<&str> = BumpyVector::new(100);
550
551 // Insert a 5-byte value at 10
552 h.insert(("hello", 10, 5).into()).unwrap();
553 assert_eq!(1, h.len());
554
555 // Earlier values are none
556 assert!(h.get(8).is_none());
557 assert!(h.get(9).is_none());
558
559 // Middle values are all identical, no matter where in the entry we
560 // retrieve it
561 assert_eq!("hello", h.get(10).unwrap().entry);
562 assert_eq!(10, h.get(10).unwrap().index);
563 assert_eq!(5, h.get(10).unwrap().size);
564
565 assert_eq!("hello", h.get(11).unwrap().entry);
566 assert_eq!(10, h.get(11).unwrap().index);
567 assert_eq!(5, h.get(11).unwrap().size);
568
569 assert_eq!("hello", h.get(12).unwrap().entry);
570 assert_eq!(10, h.get(12).unwrap().index);
571 assert_eq!(5, h.get(12).unwrap().size);
572
573 assert_eq!("hello", h.get(13).unwrap().entry);
574 assert_eq!(10, h.get(13).unwrap().index);
575 assert_eq!(5, h.get(13).unwrap().size);
576
577 assert_eq!("hello", h.get(14).unwrap().entry);
578 assert_eq!(10, h.get(14).unwrap().index);
579 assert_eq!(5, h.get(14).unwrap().size);
580
581 // Last couple entries are none
582 assert!(h.get(15).is_none());
583 assert!(h.get(16).is_none());
584
585 // There should still be a single entry
586 assert_eq!(1, h.len());
587 }
588
589 #[test]
590 fn test_zero_sized_insert() {
591 let mut h: BumpyVector<&str> = BumpyVector::new(100);
592
593 // Insert a 0-byte array
594 assert!(h.insert(("hello", 10, 0).into()).is_err());
595 assert_eq!(0, h.len());
596 }
597
598 #[test]
599 fn test_overlapping_one_byte_inserts() {
600 let mut h: BumpyVector<&str> = BumpyVector::new(100);
601
602 // Insert a 2-byte value at 10
603 h.insert(("hello", 10, 2).into()).unwrap();
604 assert_eq!(1, h.len());
605
606 // We can insert before
607 assert!(h.insert(("ok", 8, 1).into()).is_ok());
608 assert_eq!(2, h.len());
609 assert!(h.insert(("ok", 9, 1).into()).is_ok());
610 assert_eq!(3, h.len());
611
612 // We can't insert within
613 assert!(h.insert(("error", 10, 1).into()).is_err());
614 assert!(h.insert(("error", 11, 1).into()).is_err());
615 assert_eq!(3, h.len());
616
617 // We can insert after
618 assert!(h.insert(("ok", 12, 1).into()).is_ok());
619 assert_eq!(4, h.len());
620 assert!(h.insert(("ok", 13, 1).into()).is_ok());
621 assert_eq!(5, h.len());
622 }
623
624 #[test]
625 fn test_overlapping_multi_byte_inserts() {
626 // Define 10-12, put something at 7-9 (good!)
627 let mut h: BumpyVector<&str> = BumpyVector::new(100);
628 h.insert(("hello", 10, 3).into()).unwrap();
629 assert!(h.insert(("ok", 7, 3).into()).is_ok());
630
631 // Define 10-12, try every overlapping bit
632 let mut h: BumpyVector<&str> = BumpyVector::new(100);
633 h.insert(BumpyEntry::from(("hello", 10, 3))).unwrap();
634 assert!(h.insert(("error", 8, 3).into()).is_err());
635 assert!(h.insert(("error", 9, 3).into()).is_err());
636 assert!(h.insert(("error", 10, 3).into()).is_err());
637 assert!(h.insert(("error", 11, 3).into()).is_err());
638 assert!(h.insert(("error", 12, 3).into()).is_err());
639
640 // 6-9 and 13-15 will work
641 assert!(h.insert(BumpyEntry::from(("ok", 6, 3))).is_ok());
642 assert!(h.insert(("ok", 13, 3).into()).is_ok());
643 assert_eq!(3, h.len());
644 }
645
646 #[test]
647 fn test_remove() {
648 // Define 10-12, put something at 7-9 (good!)
649 let mut h: BumpyVector<&str> = BumpyVector::new(100);
650 h.insert(("hello", 8, 2).into()).unwrap();
651 h.insert(("hello", 10, 2).into()).unwrap();
652 h.insert(("hello", 12, 2).into()).unwrap();
653 assert_eq!(3, h.len());
654
655 // Remove from the start of an entry
656 let e = h.remove(10).unwrap();
657 assert_eq!("hello", e.entry);
658 assert_eq!(10, e.index);
659 assert_eq!(2, e.size);
660 assert_eq!(2, h.len());
661 assert!(h.get(10).is_none());
662 assert!(h.get(11).is_none());
663
664 // Put it back
665 h.insert(("hello", 10, 2).into()).unwrap();
666 assert_eq!(3, h.len());
667
668 // Remove from the middle of an entry
669 let e = h.remove(11).unwrap();
670 assert_eq!("hello", e.entry);
671 assert_eq!(10, e.index);
672 assert_eq!(2, e.size);
673 assert_eq!(2, h.len());
674 assert!(h.get(10).is_none());
675 assert!(h.get(11).is_none());
676
677 // Remove 11 again, which is nothing
678 let result = h.remove(11);
679 assert!(result.is_none());
680
681 let e = h.remove(13).unwrap();
682 assert_eq!("hello", e.entry);
683 assert_eq!(12, e.index);
684 assert_eq!(2, e.size);
685 assert_eq!(1, h.len());
686 assert!(h.get(12).is_none());
687 assert!(h.get(13).is_none());
688
689 h.remove(8);
690 assert_eq!(0, h.len());
691 assert!(h.get(8).is_none());
692 assert!(h.get(9).is_none());
693 }
694
695 #[test]
696 fn test_beginning() {
697 let mut h: BumpyVector<&str> = BumpyVector::new(10);
698 h.insert(("hello", 0, 2).into()).unwrap();
699
700 assert_eq!(1, h.len());
701
702 assert_eq!("hello", h.get(0).unwrap().entry);
703 assert_eq!(0, h.get(0).unwrap().index);
704 assert_eq!(2, h.get(0).unwrap().size);
705
706 assert_eq!("hello", h.get(1).unwrap().entry);
707 assert_eq!(0, h.get(1).unwrap().index);
708 assert_eq!(2, h.get(1).unwrap().size);
709
710 assert!(h.get(2).is_none());
711 }
712
713 #[test]
714 fn test_max_size() {
715 // Inserting at 7-8-9 works
716 let mut h: BumpyVector<&str> = BumpyVector::new(10);
717 assert_eq!(10, h.max_size());
718
719 h.insert(("hello", 7, 3).into()).unwrap();
720 assert_eq!(1, h.len());
721
722 // Inserting at 8-9-10 and onward does not
723 let mut h: BumpyVector<&str> = BumpyVector::new(10);
724 assert!(h.insert(("hello", 8, 3).into()).is_err());
725 assert_eq!(0, h.len());
726
727 let mut h: BumpyVector<&str> = BumpyVector::new(10);
728 assert!(h.insert(("hello", 9, 3).into()).is_err());
729 assert_eq!(0, h.len());
730
731 let mut h: BumpyVector<&str> = BumpyVector::new(10);
732 assert!(h.insert(("hello", 10, 3).into()).is_err());
733 assert_eq!(0, h.len());
734
735 let mut h: BumpyVector<&str> = BumpyVector::new(10);
736 assert!(h.insert(("hello", 11, 3).into()).is_err());
737 assert_eq!(0, h.len());
738 }
739
740 #[test]
741 fn test_remove_range() {
742 // Create an object
743 let mut h: BumpyVector<&str> = BumpyVector::new(100);
744 h.insert(("hello", 8, 2).into()).unwrap();
745 h.insert(("hello", 10, 2).into()).unwrap();
746 h.insert(("hello", 12, 2).into()).unwrap();
747 assert_eq!(3, h.len());
748
749 // Test removing the first two entries
750 let result = h.remove_range(8, 4);
751 assert_eq!(1, h.len());
752 assert_eq!(2, result.len());
753
754 assert_eq!("hello", result[0].entry);
755 assert_eq!(8, result[0].index);
756 assert_eq!(2, result[0].size);
757
758 assert_eq!("hello", result[1].entry);
759 assert_eq!(10, result[1].index);
760 assert_eq!(2, result[1].size);
761
762 // Re-create the object
763 let mut h: BumpyVector<&str> = BumpyVector::new(100);
764 h.insert(("hello", 8, 2).into()).unwrap();
765 h.insert(("hello", 10, 2).into()).unwrap();
766 h.insert(("hello", 12, 2).into()).unwrap();
767 assert_eq!(3, h.len());
768
769 // Test where the first entry starts left of the actual starting index
770 let result = h.remove_range(9, 2);
771 assert_eq!(1, h.len());
772 assert_eq!(2, result.len());
773
774 assert_eq!("hello", result[0].entry);
775 assert_eq!(8, result[0].index);
776 assert_eq!(2, result[0].size);
777
778 assert_eq!("hello", result[1].entry);
779 assert_eq!(10, result[1].index);
780 assert_eq!(2, result[1].size);
781
782 // Re-create the object
783 let mut h: BumpyVector<&str> = BumpyVector::new(100);
784 h.insert(("hello", 8, 2).into()).unwrap();
785 h.insert(("hello", 10, 2).into()).unwrap();
786 h.insert(("hello", 12, 2).into()).unwrap();
787 assert_eq!(3, h.len());
788
789 // Test the entire object
790 let result = h.remove_range(0, 1000);
791 assert_eq!(0, h.len());
792 assert_eq!(3, result.len());
793
794 assert_eq!("hello", result[0].entry);
795 assert_eq!(8, result[0].index);
796 assert_eq!(2, result[0].size);
797
798 assert_eq!("hello", result[1].entry);
799 assert_eq!(10, result[1].index);
800 assert_eq!(2, result[1].size);
801 }
802
803 #[test]
804 fn test_get() {
805 // Create an object
806 let mut h: BumpyVector<&str> = BumpyVector::new(100);
807 h.insert(("hello", 8, 2).into()).unwrap();
808
809 // Test removing the first two entries
810 assert!(h.get(7).is_none());
811 assert!(h.get(8).is_some());
812 assert!(h.get(9).is_some());
813 assert!(h.get(10).is_none());
814 }
815
816 #[test]
817 fn test_get_mut() {
818 // Create an object
819 let mut h: BumpyVector<String> = BumpyVector::new(100);
820 h.insert((String::from("hello"), 8, 2).into()).unwrap();
821
822 // Get a mutable reference
823 let s = h.get_mut(9).unwrap();
824 s.entry.make_ascii_uppercase();
825
826 let s2 = h.get(8).unwrap();
827 assert_eq!("HELLO", s2.entry);
828 }
829
830 #[test]
831 fn test_get_exact() {
832 // Create an object
833 let mut h: BumpyVector<&str> = BumpyVector::new(100);
834 h.insert(("hello", 8, 2).into()).unwrap();
835
836 // Test removing the first two entries
837 assert!(h.get_exact(7).is_none());
838 assert!(h.get_exact(8).is_some());
839 assert!(h.get_exact(9).is_none());
840 assert!(h.get_exact(10).is_none());
841 }
842
843 #[test]
844 fn test_get_exact_mut() {
845 // Create an object
846 let mut h: BumpyVector<String> = BumpyVector::new(100);
847 h.insert((String::from("hello"), 8, 2).into()).unwrap();
848
849 // Make sure it's actually exist
850 assert!(h.get_exact_mut(9).is_none());
851
852 // Get a mutable reference
853 let s = h.get_exact_mut(8).unwrap();
854 s.entry.make_ascii_uppercase();
855
856 let s = h.get_exact(8).unwrap();
857 assert_eq!("HELLO", s.entry);
858 }
859
860 #[test]
861 fn test_get_range() {
862 // Create a BumpyVector that looks like:
863 //
864 // [--0-- --1-- --2-- --3-- --4-- --5-- --6-- --7-- --8-- --9--]
865 // +----------------- +----------------+
866 // | "a" (2)| "b" | | "c" |
867 // +----------+------ +----------------+
868 let mut h: BumpyVector<&str> = BumpyVector::new(10);
869 h.insert(("a", 1, 2).into()).unwrap();
870 h.insert(("b", 3, 1).into()).unwrap();
871 h.insert(("c", 6, 3).into()).unwrap();
872
873 // Get just the first two
874 let result = h.get_range(2, 4);
875 assert_eq!(2, result.len());
876
877 // Get the first two, then just barely the third
878 let result = h.get_range(2, 5);
879 assert_eq!(3, result.len());
880
881 // Get the first two again, starting further left
882 let result = h.get_range(1, 5);
883 assert_eq!(2, result.len());
884
885 // Get all three again
886 let result = h.get_range(1, 6);
887 assert_eq!(3, result.len());
888
889 // Get way more than everything
890 let result = h.get_range(0, 100);
891 assert_eq!(3, result.len());
892 }
893
894 #[test]
895 fn test_iterator() {
896 // Create a BumpyVector that looks like:
897 //
898 // [--0-- --1-- --2-- --3-- --4-- --5-- --6-- --7-- --8-- --9--]
899 // +----------------- +----------------+
900 // | "a" (2)| "b" | | "c" |
901 // +----------+------ +----------------+
902 let mut h: BumpyVector<&str> = BumpyVector::new(10);
903 h.insert(("a", 1, 2).into()).unwrap();
904 h.insert(("b", 3, 1).into()).unwrap();
905 h.insert(("c", 6, 3).into()).unwrap();
906
907 let mut iter = h.into_iter();
908
909 // Entry "a" (index 1-2)
910 let e = iter.next().unwrap();
911 assert_eq!("a", e.entry);
912 assert_eq!(1, e.index);
913 assert_eq!(2, e.size);
914
915 // Entry "b" (index 3)
916 let e = iter.next().unwrap();
917 assert_eq!("b", e.entry);
918 assert_eq!(3, e.index);
919 assert_eq!(1, e.size);
920
921 // Entry "c" (index 6-8)
922 let e = iter.next().unwrap();
923 assert_eq!("c", e.entry);
924 assert_eq!(6, e.index);
925 assert_eq!(3, e.size);
926
927 // That's it!
928 assert!(iter.next().is_none());
929 assert!(iter.next().is_none());
930 }
931
932 #[test]
933 #[cfg(feature = "serialize")] // Only test if we enable serialization
934 fn test_serialize() {
935 let mut h: BumpyVector<String> = BumpyVector::new(10);
936 h.insert((String::from("a"), 1, 2).into()).unwrap();
937 h.insert((String::from("b"), 3, 1).into()).unwrap();
938 h.insert((String::from("c"), 6, 3).into()).unwrap();
939
940 // Serialize
941 let serialized = ron::ser::to_string(&h).unwrap();
942
943 // Deserialize
944 let h: BumpyVector<String> = ron::de::from_str(&serialized).unwrap();
945
946 // Make sure we have the same entries
947 assert_eq!("a", h.get(2).unwrap().entry);
948 assert_eq!(1, h.get(2).unwrap().index);
949 assert_eq!(2, h.get(2).unwrap().size);
950 assert_eq!("b", h.get(3).unwrap().entry);
951 assert!(h.get(4).is_none());
952 assert!(h.get(5).is_none());
953 assert_eq!("c", h.get(6).unwrap().entry);
954 assert_eq!(6, h.get(6).unwrap().index);
955 assert_eq!(3, h.get(6).unwrap().size);
956 }
957
958 #[test]
959 fn test_clone() {
960 let mut h: BumpyVector<String> = BumpyVector::new(10);
961 h.insert((String::from("a"), 1, 2).into()).unwrap();
962 h.insert((String::from("b"), 3, 1).into()).unwrap();
963 h.insert((String::from("c"), 6, 3).into()).unwrap();
964
965 // Serialize
966 let cloned = h.clone();
967
968 // Make sure we have the same entries
969 assert_eq!("a", cloned.get(2).unwrap().entry);
970 assert_eq!(1, cloned.get(2).unwrap().index);
971 assert_eq!(2, cloned.get(2).unwrap().size);
972 assert_eq!("b", cloned.get(3).unwrap().entry);
973 assert!(cloned.get(4).is_none());
974 assert!(cloned.get(5).is_none());
975 assert_eq!("c", cloned.get(6).unwrap().entry);
976 assert_eq!(6, cloned.get(6).unwrap().index);
977 assert_eq!(3, cloned.get(6).unwrap().size);
978 }
979}