#![no_std]
#![forbid(unsafe_code)]
#[cfg_attr(test, macro_use)]
extern crate alloc;
use alloc::borrow::Cow;
use alloc::vec::Vec;
use core::iter::FusedIterator;
use core::slice;
fn find_subregion(sup: &[u8], sub: &[u8]) -> Option<usize> {
if sub.is_empty() { return Some(0) }
for (i, w) in sup.windows(sub.len()).enumerate() {
if w == sub { return Some(i) }
}
None
}
#[test]
fn test_find_subregion() {
assert_eq!(find_subregion(&[1, 2, 3], &[1]), Some(0));
assert_eq!(find_subregion(&[1, 2, 3], &[2]), Some(1));
assert_eq!(find_subregion(&[1, 2, 3], &[3]), Some(2));
assert_eq!(find_subregion(&[1, 2, 3, 3, 2, 3, 4], &[2, 3]), Some(1));
assert_eq!(find_subregion(&[1, 2, 3, 3, 2, 3, 4], &[2, 3, 3]), Some(1));
assert_eq!(find_subregion(&[1, 2, 3, 3, 2, 3, 4], &[2, 3, 4]), Some(4));
assert_eq!(find_subregion(&[1, 2, 3, 3, 2, 3, 4], &[2, 3, 4, 5]), None);
assert_eq!(find_subregion(&[1, 2, 3, 3, 2, 3, 4], &[1, 2, 3, 3, 2, 3, 4]), Some(0));
assert_eq!(find_subregion(&[1, 2, 3, 3, 2, 3, 4], &[1, 2, 3, 3, 2, 3, 4, 1]), None);
}
#[derive(Clone, Copy, Debug)]
pub struct SliceInfo {
pub src: usize,
pub start: usize,
pub length: usize,
}
#[derive(Default, Clone, Debug)]
pub struct BinPool {
data: Vec<Vec<u8>>, slices: Vec<SliceInfo>, }
impl BinPool {
pub fn new() -> Self {
Default::default()
}
fn add_internal(&mut self, value: Cow<[u8]>) -> usize {
for (i, other) in self.iter().enumerate() {
if other == &*value { return i; }
}
let ret = self.slices.len(); for (i, top) in self.data.iter().enumerate() {
if let Some(start) = find_subregion(top, &value) {
self.slices.push(SliceInfo { src: i, start, length: value.len() });
return ret;
}
}
for i in 0..self.data.len() {
if let Some(start) = find_subregion(&value, &self.data[i]) {
self.data[i] = value.into_owned();
for slice in self.slices.iter_mut() {
if slice.src == i { slice.start += start; }
}
let mut j = i + 1;
while j < self.data.len() {
if let Some(start) = find_subregion(&self.data[i], &self.data[j]) {
self.data.swap_remove(j);
for slice in self.slices.iter_mut() {
if slice.src == j {
slice.src = i;
slice.start += start;
}
else if slice.src == self.data.len() {
slice.src = j;
}
}
}
else { j += 1; } }
self.slices.push(SliceInfo { src: i, start: 0, length: self.data[i].len() });
return ret;
}
}
let length = value.len();
self.data.push(value.into_owned());
self.slices.push(SliceInfo { src: self.data.len() - 1, start: 0, length });
ret
}
pub fn add<'a, T>(&mut self, value: T) -> usize where T: Into<Cow<'a, [u8]>> {
self.add_internal(value.into())
}
pub fn clear(&mut self) {
self.data.clear();
self.slices.clear();
}
pub fn len(&self) -> usize {
self.slices.len()
}
pub fn is_empty(&self) -> bool {
self.slices.is_empty()
}
pub fn iter(&self) -> Iter {
Iter { data: &self.data, iter: self.slices.iter() }
}
pub fn get(&self, index: usize) -> Option<&[u8]> {
self.slices.get(index).map(|s| &self.data[s.src][s.start..s.start+s.length])
}
pub fn bytes(&self) -> usize {
self.slices.iter().fold(0, |v, s| v + s.length)
}
pub fn backing_bytes(&self) -> usize {
self.data.iter().fold(0, |v, s| v + s.len())
}
pub fn as_backing(&self) -> (&Vec<Vec<u8>>, &Vec<SliceInfo>) {
(&self.data, &self.slices)
}
pub fn into_backing(self) -> (Vec<Vec<u8>>, Vec<SliceInfo>) {
(self.data, self.slices)
}
}
pub struct Iter<'a> {
data: &'a [Vec<u8>],
iter: slice::Iter<'a, SliceInfo>,
}
impl<'a> Iterator for Iter<'a> {
type Item = &'a [u8];
fn next(&mut self) -> Option<Self::Item> {
self.iter.next().map(|s| &self.data[s.src][s.start..s.start+s.length])
}
}
impl<'a> FusedIterator for Iter<'a> {}
#[test]
fn test_binary_pool() {
let mut s = BinPool::new();
let checked_add = |s: &mut BinPool, v: Vec<u8>| {
let res = s.add(&v);
assert_eq!(s.get(res).unwrap(), &v);
res
};
assert_eq!(s.len(), 0);
assert!(s.is_empty());
assert_eq!(s.iter().count(), 0);
assert_eq!(s.bytes(), 0);
assert_eq!(s.backing_bytes(), 0);
assert_eq!(checked_add(&mut s, vec![1, 2, 3]), 0);
assert_eq!(s.len(), 1);
assert!(!s.is_empty());
assert_eq!(s.iter().collect::<Vec<_>>(), vec![[1, 2, 3].as_ref()]);
assert_eq!(s.data, &[[1, 2, 3].as_ref()]);
assert_eq!(s.bytes(), 3);
assert_eq!(s.backing_bytes(), 3);
assert_eq!(checked_add(&mut s, vec![2, 3]), 1);
assert_eq!(s.len(), 2);
assert_eq!(s.iter().collect::<Vec<_>>(), vec![[1, 2, 3].as_ref(), [2, 3].as_ref()]);
assert_eq!(s.data, &[[1, 2, 3].as_ref()]);
assert_eq!(s.bytes(), 5);
assert_eq!(s.backing_bytes(), 3);
assert_eq!(checked_add(&mut s, vec![2, 3]), 1);
assert_eq!(s.len(), 2);
assert_eq!(s.iter().collect::<Vec<_>>(), vec![[1, 2, 3].as_ref(), [2, 3].as_ref()]);
assert_eq!(s.data, &[[1, 2, 3].as_ref()]);
assert_eq!(s.bytes(), 5);
assert_eq!(s.backing_bytes(), 3);
assert_eq!(checked_add(&mut s, vec![1, 2, 3]), 0);
assert_eq!(s.len(), 2);
assert_eq!(s.iter().collect::<Vec<_>>(), vec![[1, 2, 3].as_ref(), [2, 3].as_ref()]);
assert_eq!(s.data, &[[1, 2, 3].as_ref()]);
assert_eq!(s.bytes(), 5);
assert_eq!(s.backing_bytes(), 3);
assert_eq!(checked_add(&mut s, vec![2, 3, 4, 5]), 2);
assert_eq!(s.len(), 3);
assert_eq!(s.iter().collect::<Vec<_>>(), vec![[1, 2, 3].as_ref(), [2, 3].as_ref(), [2, 3, 4, 5].as_ref()]);
assert_eq!(s.data, &[[1, 2, 3].as_ref(), [2, 3, 4, 5].as_ref()]);
assert_eq!(s.bytes(), 9);
assert_eq!(s.backing_bytes(), 7);
assert_eq!(checked_add(&mut s, vec![2, 3, 4, 5]), 2);
assert_eq!(s.len(), 3);
assert_eq!(s.iter().collect::<Vec<_>>(), vec![[1, 2, 3].as_ref(), [2, 3].as_ref(), [2, 3, 4, 5].as_ref()]);
assert_eq!(s.data, &[[1, 2, 3].as_ref(), [2, 3, 4, 5].as_ref()]);
assert_eq!(s.bytes(), 9);
assert_eq!(s.backing_bytes(), 7);
assert_eq!(checked_add(&mut s, vec![1, 2, 3, 4]), 3);
assert_eq!(s.len(), 4);
assert_eq!(s.iter().collect::<Vec<_>>(), vec![[1, 2, 3].as_ref(), [2, 3].as_ref(), [2, 3, 4, 5].as_ref(), [1, 2, 3, 4].as_ref()]);
assert_eq!(s.data, &[[1, 2, 3, 4].as_ref(), [2, 3, 4, 5].as_ref()]);
assert_eq!(s.bytes(), 13);
assert_eq!(s.backing_bytes(), 8);
{
let mut s = s.clone();
assert_eq!(checked_add(&mut s, vec![255, 69, 1, 2, 3, 4, 5, 0, 0, 10, 20]), 4);
assert_eq!(s.len(), 5);
assert_eq!(s.iter().collect::<Vec<_>>(), vec![[1, 2, 3].as_ref(), [2, 3].as_ref(), [2, 3, 4, 5].as_ref(), [1, 2, 3, 4].as_ref(),
[255, 69, 1, 2, 3, 4, 5, 0, 0, 10, 20].as_ref()]);
assert_eq!(s.data, &[[255, 69, 1, 2, 3, 4, 5, 0, 0, 10, 20].as_ref()]);
assert_eq!(s.bytes(), 24);
assert_eq!(s.backing_bytes(), 11);
}
{
let mut s = s.clone();
assert_eq!(checked_add(&mut s, vec![2, 3, 4, 5, 0, 0, 10, 20]), 4);
assert_eq!(s.len(), 5);
assert_eq!(s.iter().collect::<Vec<_>>(), vec![[1, 2, 3].as_ref(), [2, 3].as_ref(), [2, 3, 4, 5].as_ref(), [1, 2, 3, 4].as_ref(),
[2, 3, 4, 5, 0, 0, 10, 20].as_ref()]);
assert_eq!(s.data, &[[1, 2, 3, 4].as_ref(), [2, 3, 4, 5, 0, 0, 10, 20].as_ref()]);
assert_eq!(s.bytes(), 21);
assert_eq!(s.backing_bytes(), 12);
}
{
let mut s = s.clone();
assert_eq!(checked_add(&mut s, vec![255, 69, 1, 2, 3, 4]), 4);
assert_eq!(s.len(), 5);
assert_eq!(s.iter().collect::<Vec<_>>(), vec![[1, 2, 3].as_ref(), [2, 3].as_ref(), [2, 3, 4, 5].as_ref(), [1, 2, 3, 4].as_ref(),
[255, 69, 1, 2, 3, 4].as_ref()]);
assert_eq!(s.data, &[[255, 69, 1, 2, 3, 4].as_ref(), [2, 3, 4, 5].as_ref()]);
assert_eq!(s.bytes(), 19);
assert_eq!(s.backing_bytes(), 10);
}
s.clear();
assert_eq!(s.len(), 0);
assert!(s.is_empty());
assert_eq!(s.iter().count(), 0);
assert_eq!(s.bytes(), 0);
assert_eq!(s.backing_bytes(), 0);
assert_eq!(checked_add(&mut s, vec![6, 6, 6]), 0);
assert_eq!(s.len(), 1);
assert!(!s.is_empty());
assert_eq!(s.iter().collect::<Vec<_>>(), vec![[6, 6, 6].as_ref()]);
assert_eq!(s.data, &[[6, 6, 6].as_ref()]);
assert_eq!(s.bytes(), 3);
assert_eq!(s.backing_bytes(), 3);
assert_eq!(checked_add(&mut s, vec![2, 3, 4]), 1);
assert_eq!(s.len(), 2);
assert_eq!(s.iter().collect::<Vec<_>>(), vec![[6, 6, 6].as_ref(), [2, 3, 4].as_ref()]);
assert_eq!(s.data, &[[6, 6, 6].as_ref(), [2, 3, 4].as_ref()]);
assert_eq!(s.bytes(), 6);
assert_eq!(s.backing_bytes(), 6);
assert_eq!(checked_add(&mut s, vec![2, 3]), 2);
assert_eq!(s.len(), 3);
assert_eq!(s.iter().collect::<Vec<_>>(), vec![[6, 6, 6].as_ref(), [2, 3, 4].as_ref(), [2, 3].as_ref()]);
assert_eq!(s.data, &[[6, 6, 6].as_ref(), [2, 3, 4].as_ref()]);
assert_eq!(s.bytes(), 8);
assert_eq!(s.backing_bytes(), 6);
assert_eq!(checked_add(&mut s, vec![1, 2, 3, 6, 6, 6]), 3);
assert_eq!(s.len(), 4);
assert_eq!(s.iter().collect::<Vec<_>>(), vec![[6, 6, 6].as_ref(), [2, 3, 4].as_ref(), [2, 3].as_ref(), [1, 2, 3, 6, 6, 6].as_ref()]);
assert_eq!(s.data, &[[1, 2, 3, 6, 6, 6].as_ref(), [2, 3, 4].as_ref()]);
assert_eq!(s.bytes(), 14);
assert_eq!(s.backing_bytes(), 9);
assert_eq!(checked_add(&mut s, vec![2, 3]), 2);
assert_eq!(s.len(), 4);
assert_eq!(s.iter().collect::<Vec<_>>(), vec![[6, 6, 6].as_ref(), [2, 3, 4].as_ref(), [2, 3].as_ref(), [1, 2, 3, 6, 6, 6].as_ref()]);
assert_eq!(s.data, &[[1, 2, 3, 6, 6, 6].as_ref(), [2, 3, 4].as_ref()]);
assert_eq!(s.bytes(), 14);
assert_eq!(s.backing_bytes(), 9);
{
let mut s = BinPool::new();
assert_eq!(checked_add(&mut s, vec![0]), 0);
assert_eq!(checked_add(&mut s, vec![1]), 1);
assert_eq!(s.iter().collect::<Vec<_>>(), vec![[0].as_ref(), [1].as_ref()]);
assert_eq!(s.data, vec![[0].as_ref(), [1].as_ref()]);
assert_eq!(checked_add(&mut s, vec![0, 1]), 2);
assert_eq!(s.iter().collect::<Vec<_>>(), vec![[0].as_ref(), [1].as_ref(), [0, 1].as_ref()]);
assert_eq!(s.data, vec![[0, 1].as_ref()]);
}
{
let mut s = BinPool::new();
assert_eq!(checked_add(&mut s, vec![0]), 0);
assert_eq!(checked_add(&mut s, vec![1]), 1);
assert_eq!(s.iter().collect::<Vec<_>>(), vec![[0].as_ref(), [1].as_ref()]);
assert_eq!(s.data, vec![[0].as_ref(), [1].as_ref()]);
assert_eq!(checked_add(&mut s, vec![1, 0]), 2);
assert_eq!(s.iter().collect::<Vec<_>>(), vec![[0].as_ref(), [1].as_ref(), [1, 0].as_ref()]);
assert_eq!(s.data, vec![[1, 0].as_ref()]);
}
{
let mut s = BinPool::new();
assert_eq!(checked_add(&mut s, vec![]), 0);
assert_eq!(s.iter().collect::<Vec<_>>(), vec![[].as_ref()]);
assert_eq!(s.data, vec![[].as_ref()]);
assert_eq!(checked_add(&mut s, vec![5]), 1);
assert_eq!(s.iter().collect::<Vec<_>>(), vec![[].as_ref(), [5].as_ref()]);
assert_eq!(s.data, vec![[5].as_ref()]);
}
{
let mut s = BinPool::new();
assert_eq!(checked_add(&mut s, vec![7]), 0);
assert_eq!(s.iter().collect::<Vec<_>>(), vec![[7].as_ref()]);
assert_eq!(s.data, vec![[7].as_ref()]);
assert_eq!(checked_add(&mut s, vec![]), 1);
assert_eq!(s.iter().collect::<Vec<_>>(), vec![[7].as_ref(), [].as_ref()]);
assert_eq!(s.data, vec![[7].as_ref()]);
}
}