#![deny(missing_docs, trivial_numeric_casts, unused_extern_crates)]
#![warn(unused_import_braces)]
#![cfg_attr(feature = "std", warn(unstable_features))]
#![cfg_attr(feature = "clippy", plugin(clippy(conf_file = "../../clippy.toml")))]
#![cfg_attr(feature = "cargo-clippy", allow(clippy::new_without_default))]
#![cfg_attr(
feature = "cargo-clippy",
warn(
clippy::float_arithmetic,
clippy::mut_mut,
clippy::nonminimal_bool,
clippy::option_map_unwrap_or,
clippy::option_map_unwrap_or_else,
clippy::print_stdout,
clippy::unicode_not_nfc,
clippy::use_self
)
)]
#![no_std]
#![cfg_attr(not(feature = "std"), feature(alloc))]
#[cfg(test)]
#[cfg(not(feature = "std"))]
#[macro_use]
extern crate alloc as std;
#[cfg(test)]
#[cfg(feature = "std")]
#[macro_use]
extern crate std;
#[macro_use]
extern crate cranelift_entity as entity;
use crate::entity::packed_option;
use core::borrow::BorrowMut;
use core::cmp::Ordering;
mod map;
mod node;
mod path;
mod pool;
mod set;
pub use self::map::{Map, MapCursor, MapForest, MapIter};
pub use self::set::{Set, SetCursor, SetForest, SetIter};
use self::node::NodeData;
use self::path::Path;
use self::pool::NodePool;
const INNER_SIZE: usize = 8;
const MAX_PATH: usize = 16;
pub trait Comparator<K>
where
K: Copy,
{
fn cmp(&self, a: K, b: K) -> Ordering;
fn search(&self, k: K, s: &[K]) -> Result<usize, usize> {
s.binary_search_by(|x| self.cmp(*x, k))
}
}
impl<K> Comparator<K> for ()
where
K: Copy + Ord,
{
fn cmp(&self, a: K, b: K) -> Ordering {
a.cmp(&b)
}
}
trait Forest {
type Key: Copy;
type Value: Copy;
type LeafKeys: Copy + BorrowMut<[Self::Key]>;
type LeafValues: Copy + BorrowMut<[Self::Value]>;
fn splat_key(key: Self::Key) -> Self::LeafKeys;
fn splat_value(value: Self::Value) -> Self::LeafValues;
}
#[derive(Clone, Copy, PartialEq, Eq)]
struct Node(u32);
entity_impl!(Node, "node");
#[derive(Clone, Copy)]
struct SetValue();
fn slice_insert<T: Copy>(s: &mut [T], i: usize, x: T) {
for j in (i + 1..s.len()).rev() {
s[j] = s[j - 1];
}
s[i] = x;
}
fn slice_shift<T: Copy>(s: &mut [T], n: usize) {
for j in 0..s.len() - n {
s[j] = s[j + n];
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::entity::EntityRef;
#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct Ebb(u32);
entity_impl!(Ebb, "ebb");
#[test]
fn comparator() {
let ebb1 = Ebb::new(1);
let ebb2 = Ebb::new(2);
let ebb3 = Ebb::new(3);
let ebb4 = Ebb::new(4);
let vals = [ebb1, ebb2, ebb4];
let comp = ();
assert_eq!(comp.search(ebb1, &vals), Ok(0));
assert_eq!(comp.search(ebb3, &vals), Err(2));
assert_eq!(comp.search(ebb4, &vals), Ok(2));
}
#[test]
fn slice_insertion() {
let mut a = ['a', 'b', 'c', 'd'];
slice_insert(&mut a[0..1], 0, 'e');
assert_eq!(a, ['e', 'b', 'c', 'd']);
slice_insert(&mut a, 0, 'a');
assert_eq!(a, ['a', 'e', 'b', 'c']);
slice_insert(&mut a, 3, 'g');
assert_eq!(a, ['a', 'e', 'b', 'g']);
slice_insert(&mut a, 1, 'h');
assert_eq!(a, ['a', 'h', 'e', 'b']);
}
#[test]
fn slice_shifting() {
let mut a = ['a', 'b', 'c', 'd'];
slice_shift(&mut a[0..1], 1);
assert_eq!(a, ['a', 'b', 'c', 'd']);
slice_shift(&mut a[1..], 1);
assert_eq!(a, ['a', 'c', 'd', 'd']);
slice_shift(&mut a, 2);
assert_eq!(a, ['d', 'd', 'd', 'd']);
}
}