From a15d95254170dbd98fb21d70628bc127a3b0a15b Mon Sep 17 00:00:00 2001 From: Jordan Bracco Date: Fri, 12 Nov 2021 13:13:55 +0100 Subject: it works --- lib/tree_bitmap.ex | 152 ++++- lib/tree_bitmap/nif.ex | 5 +- native/treebitmap_nif/src/lib.rs | 277 +++++++-- native/treebitmap_nif/src/tree_bitmap/allocator.rs | 554 +++++++++++++++++ native/treebitmap_nif/src/tree_bitmap/mod.rs | 657 +++++++++++++++++++++ native/treebitmap_nif/src/tree_bitmap/node.rs | 457 ++++++++++++++ priv/native/libtreebitmap_nif.so | Bin 903892 -> 933540 bytes test/tree_bitmap_test.exs | 117 +++- 8 files changed, 2144 insertions(+), 75 deletions(-) create mode 100644 native/treebitmap_nif/src/tree_bitmap/allocator.rs create mode 100644 native/treebitmap_nif/src/tree_bitmap/mod.rs create mode 100644 native/treebitmap_nif/src/tree_bitmap/node.rs diff --git a/lib/tree_bitmap.ex b/lib/tree_bitmap.ex index 6d1bc07..0da87fa 100644 --- a/lib/tree_bitmap.ex +++ b/lib/tree_bitmap.ex @@ -1,18 +1,148 @@ defmodule TreeBitmap do - @moduledoc """ - Documentation for `TreeBitmap`. - """ + alias TreeBitmap.NIF + defstruct [:i4, :i6, :ets] - @doc """ - Hello world. + @opaque t() :: %__MODULE__{} + @type masklen :: non_neg_integer() - ## Examples + def new(_opts \\ []) do + %__MODULE__{i4: NIF.new(), i6: NIF.new(), ets: :ets.new(__MODULE__, [:public])} + end + + @spec add(t(), :inet.ip_address(), masklen(), any()) :: nil | any() + def add(tree, ip, masklen, value) + + def add(tree, {a, b, c, d}, masklen, value) do + add(tree, tree.i4, {:inet4, a, b, c, d}, masklen, value) + end + + def add(tree, {a, b, c, d, e, f, g, h}, masklen, value) do + add(tree, tree.i6, {:inet6, a, b, c, d, e, f, g, h}, masklen, value) + end + + @spec remove(t(), :inet.ip_address(), masklen()) :: nil | any() + def remove(tree, ip, masklen) + + def remove(tree, {a, b, c, d}, masklen) do + remove(tree, tree.i4, {:inet4, a, b, c, d}, masklen) + end + + def remove(tree, {a, b, c, d, e, f, g, h}, masklen) do + remove(tree, tree.i6, {:inet6, a, b, c, d, e, f, g, h}, masklen) + end + + @spec longest_match(t(), :inet.ip_address()) :: map() | nil + def longest_match(tree, ip) + + def longest_match(tree, {a, b, c, d}) do + longest_match(tree, tree.i4, {:inet4, a, b, c, d}) + end + + def longest_match(tree, {a, b, c, d, e, f, g, h}) do + longest_match(tree, tree.i6, {:inet6, a, b, c, d, e, f, g, h}) + end + + @spec longest_match?(t(), :inet.ip_address()) :: boolean() + def longest_match?(tree, ip) + + def longest_match?(tree, {a, b, c, d}) do + longest_match?(tree, tree.i4, {:inet4, a, b, c, d}) + end + + def longest_match?(tree, {a, b, c, d, e, f, g, h}) do + longest_match?(tree, tree.i6, {:inet6, a, b, c, d, e, f, g, h}) + end + + @spec exact_match(t(), :inet.ip_address(), masklen()) :: map() | nil + def exact_match(tree, ip, masklen) + + def exact_match(tree, {a, b, c, d}, masklen) do + exact_match(tree, tree.i4, {:inet4, a, b, c, d}, masklen) + end + + def exact_match(tree, {a, b, c, d, e, f, g, h}, masklen) do + exact_match(tree, tree.i6, {:inet6, a, b, c, d, e, f, g, h}, masklen) + end + + @spec exact_match?(t(), :inet.ip_address(), masklen()) :: boolean() + def exact_match?(tree, ip, masklen) + + def exact_match?(tree, {a, b, c, d}, masklen) do + exact_match?(tree, tree.i4, {:inet4, a, b, c, d}, masklen) + end - iex> TreeBitmap.hello() - :world + def exact_match?(tree, {a, b, c, d, e, f, g, h}, masklen) do + exact_match?(tree, tree.i6, {:inet6, a, b, c, d, e, f, g, h}, masklen) + end + + @type tree_memory() :: {nodes :: non_neg_integer(), results :: non_neg_integer()} + @spec memory(t()) :: %{inet4: tree_memory(), inet6: tree_memory(), ets: non_neg_integer()} + def memory(tree) do + %{inet4: NIF.memory(tree.i4), inet6: NIF.memory(tree.i6), ets: :ets.info(tree.ets, :memory)} + end - """ - def hello do - :world + @spec length(t()) :: %{inet4: non_neg_integer(), inet6: non_neg_integer(), ets: non_neg_integer()} + def length(tree) do + %{inet4: NIF.length(tree.i4), inet6: NIF.length(tree.i6), ets: :ets.info(tree.ets, :size)} end + + defp add(tree, tbm, ip, masklen, value) do + id = :ets.update_counter(tree.ets, {__MODULE__, :counter}, 1, {{__MODULE__, :counter}, -1}) + :ets.insert(tree.ets, {id, value}) + {:ok, prev_id} = NIF.add(tbm, ip, masklen, id) + prev = if prev_id do + [{^prev_id, value}] = :ets.lookup(tree.ets, prev_id) + :ets.delete(tree.ets, prev_id) + value + end + prev + end + + defp remove(tree, tbm, ip, masklen) do + {:ok, id} = NIF.remove(tbm, ip, masklen) + prev = if id do + [{^id, value}] = :ets.lookup(tree.ets, id) + :ets.delete(tree.ets, id) + value + end + prev + end + + defp longest_match(tree, tbm, ip) do + case NIF.longest_match(tbm, ip) do + {:ok, prefix, masklen, id} -> + [{^id, value}] = :ets.lookup(tree.ets, id) + %{prefix: to_inet(prefix), len: masklen, value: value} + {:ok, nil} -> + nil + end + end + + defp longest_match?(_, tbm, ip) do + case NIF.longest_match(tbm, ip) do + {:ok, nil} -> false + {:ok, _, _, _} -> true + end + end + + defp exact_match(tree, tbm, ip, masklen) do + case NIF.exact_match(tbm, ip, masklen) do + {:ok, nil} -> + nil + {:ok, id} -> + [{^id, value}] = :ets.lookup(tree.ets, id) + value + end + end + + defp exact_match?(_, tbm, ip, masklen) do + case NIF.exact_match(tbm, ip, masklen) do + {:ok, nil} -> false + {:ok, _} -> true + end + end + + defp to_inet({:inet4, a, b, c, d}), do: {a, b, c, d} + defp to_inet({:inet6, a, b, c, d, e, f, g, h}), do: {a, b, c, d, e, f, g, h} + end diff --git a/lib/tree_bitmap/nif.ex b/lib/tree_bitmap/nif.ex index 740dbdf..7934f5a 100644 --- a/lib/tree_bitmap/nif.ex +++ b/lib/tree_bitmap/nif.ex @@ -2,9 +2,12 @@ defmodule TreeBitmap.NIF do use Rustler, otp_app: :tree_bitmap, crate: "treebitmap_nif" def new(), do: :erlang.nif_error(:nif_not_loaded) + def new_with_capacity(_), do: :erlang.nif_error(:nif_not_loaded) def length(_), do: :erlang.nif_error(:nif_not_loaded) def add(_, _, _, _), do: :erlang.nif_error(:nif_not_loaded) - def lookup(_, _), do: :erlang.nif_error(:nif_not_loaded) + def longest_match(_, _), do: :erlang.nif_error(:nif_not_loaded) + def exact_match(_, _, _), do: :erlang.nif_error(:nif_not_loaded) def remove(_, _, _), do: :erlang.nif_error(:nif_not_loaded) + def memory(_), do: :erlang.nif_error(:nif_not_loaded) end diff --git a/native/treebitmap_nif/src/lib.rs b/native/treebitmap_nif/src/lib.rs index 7ff0a90..2913819 100644 --- a/native/treebitmap_nif/src/lib.rs +++ b/native/treebitmap_nif/src/lib.rs @@ -1,11 +1,12 @@ use std::sync::Mutex; -use rustler::{resource::ResourceArc, NifResult, NifRecord, Encoder, Env, Term, types::atom::Atom, types::tuple::make_tuple}; -//use std::net::Ipv6Addr; -use std::net::{Ipv4Addr}; -use treebitmap::{IpLookupTable}; +use rustler::{resource::ResourceArc, NifResult, NifRecord, NifUntaggedEnum, + Encoder, Env, Term, types::tuple::make_tuple}; + +mod tree_bitmap; +use tree_bitmap::TreeBitmap; struct TableResource { - pub table: Mutex> + pub tree: Mutex> } mod atoms { @@ -16,12 +17,33 @@ mod atoms { } } +trait Address { + fn nibbles(self) -> Nibbles; + fn mask(self, masklen: u32) -> Self; +} + +#[derive(NifUntaggedEnum, Clone)] enum AddrTuple { V4(TupleV4), V6(TupleV6) } -#[derive(Debug, NifRecord)] +impl Address for AddrTuple { + fn nibbles(self) -> Nibbles { + match self { + AddrTuple::V4(tuple_v4) => tuple_v4.nibbles(), + AddrTuple::V6(tuple_v6) => tuple_v6.nibbles() + } + } + fn mask(self, masklen: u32) -> Self { + match self { + AddrTuple::V4(tuple_v4) => AddrTuple::V4(tuple_v4.mask(masklen)), + AddrTuple::V6(tuple_v6) => AddrTuple::V6(tuple_v6.mask(masklen)) + } + } +} + +#[derive(Debug, NifRecord, Clone)] #[tag = "inet4"] struct TupleV4 { pub a: u8, @@ -30,7 +52,57 @@ struct TupleV4 { pub d: u8 } -#[derive(Debug, NifRecord)] +enum Nibbles { + V4([u8; 8]), + V6([u8; 32]) +} + +impl TupleV4 { + pub fn new(a1: u8, a2: u8, a3: u8, a4: u8) -> Self { + TupleV4 { a: a1, b: a2, c: a3, d: a4 } + } + pub fn from(num: u32) -> Self { + TupleV4 { + a: (num >> 24) as u8, + b: (num >> 16) as u8, + c: (num >> 8) as u8, + d: num as u8, + } + } +} + +impl Address for TupleV4 { + fn nibbles(self) -> Nibbles { + let mut ret: [u8; 8] = [0; 8]; + let bytes: [u8; 4] = [self.a, self.b, self.c, self.d]; + for (i, byte) in bytes.iter().enumerate() { + ret[i * 2] = byte >> 4; + ret[i * 2 + 1] = byte & 0xf; + } + Nibbles::V4(ret) + } + + fn mask(self, masklen: u32) -> Self { + debug_assert!(masklen <= 32); + let ip = u32::from(self); + let masked = match masklen { + 0 => 0, + n => ip & (!0 << (32 - n)), + }; + TupleV4::from(masked) + } + +} +impl ::std::convert::From for u32 { + fn from(a: TupleV4) -> u32 { + (a.a as u32) << 24 + | (a.b as u32) << 16 + | (a.c as u32) << 8 + | (a.d as u32) << 0 + } +} + +#[derive(Debug, NifRecord, Clone)] #[tag = "inet6"] struct TupleV6 { pub a1: u16, @@ -43,63 +115,200 @@ struct TupleV6 { pub a8: u16 } +impl TupleV6 { + + fn new(a1: u16, a2: u16, a3: u16, a4: u16, a5: u16, a6: u16, a7: u16, a8: u16) -> Self { + TupleV6 { a1: a1, a2, a3: a3, a4: a4, a5: a5, a6: a6, a7: a7, a8: a8 } + } + + fn octets(self) -> [u8; 16] { + [ + (self.a1 >> 8) as u8, + self.a1 as u8, + (self.a2 >> 8) as u8, + self.a2 as u8, + (self.a3 >> 8) as u8, + self.a3 as u8, + (self.a4 >> 8) as u8, + self.a4 as u8, + (self.a5 >> 8) as u8, + self.a5 as u8, + (self.a6 >> 8) as u8, + self.a6 as u8, + (self.a7 >> 8) as u8, + self.a7 as u8, + (self.a8 >> 8) as u8, + self.a8 as u8 + ] + } + + fn segments(self) -> [u16; 8] { + let bytes = self.octets(); + [ + (bytes[0] as u16) << 8 | (bytes[1] as u16), + (bytes[2] as u16) << 8 | (bytes[3] as u16), + (bytes[4] as u16) << 8 | (bytes[5] as u16), + (bytes[6] as u16) << 8 | (bytes[7] as u16), + (bytes[8] as u16) << 8 | (bytes[9] as u16), + (bytes[10] as u16) << 8 | (bytes[11] as u16), + (bytes[12] as u16) << 8 | (bytes[13] as u16), + (bytes[14] as u16) << 8 | (bytes[15] as u16), + ] + } + +} + +impl Address for TupleV6 { + + fn nibbles(self) -> Nibbles { + let mut ret: [u8; 32] = [0; 32]; + let bytes = self.octets(); + for (i, byte) in bytes.iter().enumerate() { + ret[i * 2] = byte >> 4; + ret[i * 2 + 1] = byte & 0xf; + } + Nibbles::V6(ret) + } + + fn mask(self, masklen: u32) -> Self { + debug_assert!(masklen <= 128); + let mut ret = self.segments(); + for i in ((masklen + 15) / 16)..8 { + ret[i as usize] = 0; + } + if masklen % 16 != 0 { + ret[masklen as usize / 16] &= !0 << (16 - (masklen % 16)); + } + Self::new( + ret[0], ret[1], ret[2], ret[3], ret[4], ret[5], ret[6], ret[7], + ) + } + +} + #[rustler::nif] fn new() -> NifResult> { - let table = IpLookupTable::new(); + let tree = TreeBitmap::new(); + let resource = ResourceArc::new(TableResource { + tree: Mutex::new(tree) + }); + Ok(resource) +} + +#[rustler::nif] +fn new_with_capacity(n: usize) -> NifResult> { + let tree = TreeBitmap::with_capacity(n); let resource = ResourceArc::new(TableResource { - table: Mutex::new(table) + tree: Mutex::new(tree) }); Ok(resource) } #[rustler::nif] fn length(table_resource: ResourceArc) -> NifResult { - let table = table_resource.table.lock().unwrap(); - Ok(table.len()) + let tree = table_resource.tree.lock().unwrap(); + Ok(tree.len()) } #[rustler::nif] -fn add( +fn add<'a>( + env: Env<'a>, table_resource: ResourceArc, - ipv4: TupleV4, + ip: AddrTuple, masklen: u32, value: u32 -) -> NifResult{ - let mut table = table_resource.table.lock().unwrap(); - let addr = Ipv4Addr::new(ipv4.a, ipv4.b, ipv4.c, ipv4.d); - table.insert(addr, masklen, value); - Ok(atoms::ok()) +) -> Term { + let mut tree = table_resource.tree.lock().unwrap(); + let result = match ip.nibbles() { + Nibbles::V4(nibbles) => tree.insert(&nibbles.as_ref(), masklen, value), + Nibbles::V6(nibbles) => tree.insert(&nibbles.as_ref(), masklen, value) + }; + if let Some(value) = result { + make_tuple(env, &[atoms::ok().encode(env), value.encode(env)]) + } else { + make_tuple(env, &[atoms::ok().encode(env), atoms::nil().encode(env)]) + } } #[rustler::nif] -fn remove( +fn remove<'a>( + env: Env<'a>, table_resource: ResourceArc, - ipv4: TupleV4, + ip: AddrTuple, masklen: u32 -) -> NifResult{ - let mut table = table_resource.table.lock().unwrap(); - let addr = Ipv4Addr::new(ipv4.a, ipv4.b, ipv4.c, ipv4.d); - table.remove(addr, masklen); - Ok(atoms::ok()) +) -> Term { + let mut tree = table_resource.tree.lock().unwrap(); + let result = match ip.nibbles() { + Nibbles::V4(nibbles) => tree.remove(&nibbles.as_ref(), masklen), + Nibbles::V6(nibbles) => tree.remove(&nibbles.as_ref(), masklen), + }; + if let Some(value) = result { + make_tuple(env, &[atoms::ok().encode(env), value.encode(env)]) + } else { + make_tuple(env, &[atoms::ok().encode(env), atoms::nil().encode(env)]) + } +} + +#[rustler::nif] +fn longest_match<'a>( + env: Env<'a>, + table_resource: ResourceArc, + ip: AddrTuple +) -> Term { + let tree = table_resource.tree.lock().unwrap(); + let ip2 = ip.clone(); + let result = match ip2.nibbles() { + Nibbles::V4(nibbles) => tree.longest_match(&nibbles.as_ref()), + Nibbles::V6(nibbles) => tree.longest_match(&nibbles.as_ref()) + }; + if let Some((bits_matched, value)) = result { + let prefix = ip.mask(bits_matched); + make_tuple(env, &[atoms::ok().encode(env), prefix.encode(env), bits_matched.encode(env), value.encode(env)]) + } else { + make_tuple(env, &[atoms::ok().encode(env), atoms::nil().encode(env)]) + } } #[rustler::nif] -fn lookup<'a>( - env: rustler::Env<'a>, +fn exact_match<'a>( + env: Env<'a>, table_resource: ResourceArc, - ipv4: TupleV4 + ip: AddrTuple, + masklen: u32 ) -> Term { - let table = table_resource.table.lock().unwrap(); - let addr = Ipv4Addr::new(ipv4.a, ipv4.b, ipv4.c, ipv4.d); - if let Some((prefix, prefixlen, value)) = table.longest_match(addr) { - let addr = prefix.octets(); - make_tuple(env, &[atoms::ok().encode(env), addr.encode(env), prefixlen.encode(env), value.encode(env)]) + let tree = table_resource.tree.lock().unwrap(); + let ip2 = ip.clone(); + let result = match ip2.nibbles() { + Nibbles::V4(nibbles) => tree.exact_match(&nibbles.as_ref(), masklen), + Nibbles::V6(nibbles) => tree.exact_match(&nibbles.as_ref(), masklen) + }; + if let Some(value) = result { + make_tuple(env, &[atoms::ok().encode(env), value.encode(env)]) } else { make_tuple(env, &[atoms::ok().encode(env), atoms::nil().encode(env)]) } } -rustler::init!("Elixir.TreeBitmap.NIF", [new, length, add, remove, lookup], load = on_load); +#[rustler::nif] +fn memory<'a>( + env: Env<'a>, + table_resource: ResourceArc +) -> Term { + let tree = table_resource.tree.lock().unwrap(); + let (nodes, results) = tree.mem_usage(); + make_tuple(env, &[nodes.encode(env), results.encode(env)]) +} + +rustler::init!("Elixir.TreeBitmap.NIF", + [new, + new_with_capacity, + length, + add, + remove, + longest_match, + exact_match, + memory], + load = on_load); fn on_load(env: Env, _info: Term) -> bool { rustler::resource!(TableResource, env); diff --git a/native/treebitmap_nif/src/tree_bitmap/allocator.rs b/native/treebitmap_nif/src/tree_bitmap/allocator.rs new file mode 100644 index 0000000..08e4350 --- /dev/null +++ b/native/treebitmap_nif/src/tree_bitmap/allocator.rs @@ -0,0 +1,554 @@ +// Copyright 2016 Hroi Sigurdsson +// +// Licensed under the MIT license . +// This file may not be copied, modified, or distributed except according to those terms. + +#[cfg(feature = "alloc")] +use alloc::vec::Vec; +use std::cmp; +use std::fmt; +use std::mem; +use std::ptr; +use std::slice; + +struct RawVec { + mem: *mut T, + cap: usize, +} + +impl RawVec { + pub fn with_capacity(cap: usize) -> RawVec { + let mut vec = Vec::::with_capacity(cap); + let ptr = vec.as_mut_ptr(); + mem::forget(vec); + RawVec { mem: ptr, cap } + } + + pub fn cap(&self) -> usize { + self.cap + } + + pub fn ptr(&self) -> *mut T { + self.mem + } + + pub fn reserve(&mut self, used_cap: usize, extra_cap: usize) { + let mut vec = unsafe { Vec::::from_raw_parts(self.mem, used_cap, self.cap) }; + vec.reserve(extra_cap); + self.cap = vec.capacity(); + self.mem = vec.as_mut_ptr(); + mem::forget(vec); + } +} + +impl Drop for RawVec { + fn drop(&mut self) { + unsafe { + Vec::from_raw_parts(self.mem, 0, self.cap); + } + } +} + +unsafe impl Sync for RawVec where T: Sync {} + +unsafe impl Send for RawVec where T: Send {} + +/// A vector that contains `len / spacing` buckets and each bucket contains `spacing` elements. +/// Buckets are store contiguously in the vector. +/// So slots are multiples of `spacing`. +pub struct BucketVec { + buf: RawVec, + freelist: Vec, + len: u32, + spacing: u32, +} + +impl fmt::Debug for BucketVec { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_struct("BucketVec") + .field("spacing", &self.spacing) + .field("freelist", &self.freelist) + .field("len", &self.len) + .field("cap", &self.buf.cap()) + .field("buf", unsafe { + &slice::from_raw_parts(self.buf.ptr(), self.len as usize) + }) + .finish() + } +} + +impl BucketVec { + pub fn with_capacity(spacing: u32, capacity: usize) -> BucketVec { + BucketVec { + buf: RawVec::with_capacity(capacity), + freelist: Vec::with_capacity(32), + len: 0, + spacing, + } + } + + #[allow(dead_code)] + pub fn new(spacing: u32) -> BucketVec { + Self::with_capacity(spacing, 0) + } + + /// Allocate a bucket slot. + pub fn alloc_slot(&mut self) -> u32 { + match self.freelist.pop() { + Some(n) => n, + None => { + self.buf.reserve(self.len as usize, self.spacing as usize); + if cfg!(debug_assertions) { + unsafe { + ptr::write_bytes( + self.buf.ptr().offset(self.len as isize), + 0, + self.spacing as usize, + ); + } + } + let slot = self.len; + self.len += self.spacing; + slot + } + } + } + + /// Free a bucket slot. + pub fn free_slot(&mut self, slot: u32) { + self.freelist.push(slot) + } + + #[inline] + pub fn get_slot_entry(&self, slot: u32, index: u32) -> &T { + debug_assert!(slot % self.spacing == 0); + let offset = slot + index; + unsafe { + let src_ptr = self.buf.ptr().offset(offset as isize); + &*src_ptr + } + } + + #[inline] + pub fn get_slot_entry_mut(&mut self, slot: u32, index: u32) -> &mut T { + debug_assert!(slot % self.spacing == 0); + let offset = slot + index; + unsafe { + let src_ptr = self.buf.ptr().offset(offset as isize); + &mut *src_ptr + } + } + + pub fn set_slot_entry(&mut self, slot: u32, index: u32, value: T) { + debug_assert!(slot % self.spacing == 0); + debug_assert!(index < self.spacing); + let offset = slot + index; + unsafe { + let dst_ptr = self.buf.ptr().offset(offset as isize); + ptr::write(dst_ptr, value); + } + } + + pub fn replace_slot_entry(&mut self, slot: u32, index: u32, value: T) -> T { + debug_assert!(slot % self.spacing == 0); + debug_assert!(index < self.spacing); + let offset = slot + index; + unsafe { + let dst_ptr = self.buf.ptr().offset(offset as isize); + ptr::replace(dst_ptr, value) + } + } + + /// Insert ```value``` into ```slot``` at ```index```. Values to the right + /// of ```index``` will be moved. + /// If all values have been set the last value will be lost. + pub fn insert_slot_entry(&mut self, slot: u32, index: u32, value: T) { + debug_assert!(slot % self.spacing == 0); + let offset = slot + index; + unsafe { + let dst_ptr = self.buf.ptr().offset(offset as isize); + ptr::copy( + dst_ptr, + dst_ptr.offset(1), + (self.spacing - index - 1) as usize, + ); + ptr::write(dst_ptr, value); + } + } + + pub fn remove_slot_entry(&mut self, slot: u32, index: u32) -> T { + debug_assert!(slot % self.spacing == 0); + debug_assert!(index < self.spacing); + let offset = slot + index; + let ret: T; + unsafe { + ret = ptr::read(self.buf.ptr().offset(offset as isize)); + let dst_ptr = self.buf.ptr().offset(offset as isize); + ptr::copy( + dst_ptr.offset(1), + dst_ptr, + (self.spacing - index - 1) as usize, + ); + if cfg!(debug_assertions) { + ptr::write( + dst_ptr.offset((self.spacing - index - 1) as isize), + mem::zeroed(), + ); + } + } + ret + } + + /// Move contents from one bucket to another. + /// Returns the offset of the new location. + fn move_slot(&mut self, slot: u32, dst: &mut BucketVec) -> u32 { + let nitems = cmp::min(self.spacing, dst.spacing); + + debug_assert!(slot < self.len); + debug_assert!(slot % self.spacing == 0); + debug_assert!(nitems > 0); + debug_assert!(nitems <= self.spacing); + debug_assert!(nitems <= dst.spacing); + + let dst_slot = dst.alloc_slot(); + + unsafe { + let src_ptr = self.buf.ptr().offset(slot as isize); + let dst_ptr = dst.buf.ptr().offset(dst_slot as isize); + ptr::copy_nonoverlapping(src_ptr, dst_ptr, nitems as usize); + if cfg!(debug_assertions) { + ptr::write_bytes(src_ptr, 0, nitems as usize); + } + } + + self.free_slot(slot); + + dst_slot + } + + pub fn mem_usage(&self) -> usize { + (mem::size_of::() * self.buf.cap()) + (self.freelist.capacity() * mem::size_of::()) + } +} + +static LEN2BUCKET: [u32; 33] = [ + 0, 0, 1, 2, 2, 3, 3, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, + 8, +]; + +#[inline] +pub fn choose_bucket(len: u32) -> u32 { + debug_assert!(len < 33); + unsafe { *LEN2BUCKET.get_unchecked(len as usize) } +} + +/// ```Allocator``` stores items in exponentially sized buckets (using +/// ```BucketVec```s for backing). +/// +/// All interaction is done with an ```AllocatorHandle```used for tracking the +/// collection size and location. +/// The location of data is computed based on the collection size and base +/// pointer (stored in handle). +/// When a bucket becomes full, the contents are moved to a larger bucket. In +/// this case the allocator will update the caller's pointer. +#[derive(Debug)] +pub struct Allocator { + buckets: [BucketVec; 9], +} + +/// Tracks the size and location of the referenced collection. +#[derive(Debug)] +pub struct AllocatorHandle { + /// The current length of the collection + pub len: u32, + /// Basepointer + pub offset: u32, +} + +impl AllocatorHandle { + #[inline] + pub fn generate(len: u32, offset: u32) -> AllocatorHandle { + AllocatorHandle { len, offset } + } +} + +impl Allocator { + /// Initialize a new allocator with default capacity. + #[allow(dead_code)] + pub fn new() -> Allocator { + Allocator { + buckets: [ + BucketVec::new(1), + BucketVec::new(2), + BucketVec::new(4), + BucketVec::new(6), + BucketVec::new(8), + BucketVec::new(12), + BucketVec::new(16), + BucketVec::new(24), + BucketVec::new(32), + ], + } + } + + /// Initialize a new ```Allocator``` with specified capacity. + pub fn with_capacity(cap: usize) -> Allocator { + Allocator { + buckets: [ + BucketVec::with_capacity(1, cap), + BucketVec::with_capacity(2, cap), + BucketVec::with_capacity(4, cap), + BucketVec::with_capacity(6, cap), + BucketVec::with_capacity(8, cap), + BucketVec::with_capacity(12, cap), + BucketVec::with_capacity(16, cap), + BucketVec::with_capacity(24, cap), + BucketVec::with_capacity(32, cap), + ], + } + } + + /// Returns the amount of memory allocated, and the amount of memory + /// allocated but not used. + pub fn mem_usage(&self) -> usize { + let mut total = 0; + for buckvec in &self.buckets { + total += buckvec.mem_usage(); + } + total + } + + // pub fn shrink_to_fit(&mut self) { + // for buckvec in &mut self.buckets { + // buckvec.shrink_to_fit(); + // } + // } + + pub fn alloc(&mut self, count: u32) -> AllocatorHandle { + let bucket_index = choose_bucket(count) as usize; + let slot = self.buckets[bucket_index].alloc_slot(); + AllocatorHandle { + len: count, + offset: slot, + } + } + + pub fn free(&mut self, hdl: &mut AllocatorHandle) { + debug_assert!(hdl.len == 0, "tried to free non-empty collection"); + let bucket_index = choose_bucket(hdl.len) as usize; + self.buckets[bucket_index].free_slot(hdl.offset); + hdl.offset = 0; + } + + pub fn set(&mut self, hdl: &AllocatorHandle, index: u32, value: T) { + let bucket_index = choose_bucket(hdl.len) as usize; + self.buckets[bucket_index].set_slot_entry(hdl.offset, index, value) + } + + pub fn replace(&mut self, hdl: &AllocatorHandle, index: u32, value: T) -> T { + let bucket_index = choose_bucket(hdl.len) as usize; + self.buckets[bucket_index].replace_slot_entry(hdl.offset, index, value) + } + + #[inline] + pub fn get(&self, hdl: &AllocatorHandle, index: u32) -> &T { + let bucket_index = choose_bucket(hdl.len) as usize; + self.buckets[bucket_index].get_slot_entry(hdl.offset, index) + } + + #[inline] + pub fn get_mut(&mut self, hdl: &AllocatorHandle, index: u32) -> &mut T { + let bucket_index = choose_bucket(hdl.len) as usize; + self.buckets[bucket_index].get_slot_entry_mut(hdl.offset, index) + } + + pub fn insert(&mut self, hdl: &mut AllocatorHandle, index: u32, value: T) { + let mut bucket_index = choose_bucket(hdl.len) as usize; + let next_bucket_index = choose_bucket(hdl.len + 1) as usize; + let mut slot = hdl.offset; + + debug_assert!(self.buckets[bucket_index].len >= hdl.offset); + + if bucket_index != next_bucket_index { + // move to bigger bucket + debug_assert!(next_bucket_index > bucket_index); + let (left, right) = self.buckets.split_at_mut(bucket_index + 1); + slot = left[bucket_index] + .move_slot(slot, &mut right[next_bucket_index - bucket_index - 1]); + bucket_index = next_bucket_index; + } + + hdl.offset = slot; + hdl.len += 1; + + self.buckets[bucket_index].insert_slot_entry(slot, index, value) + } + + pub fn remove(&mut self, hdl: &mut AllocatorHandle, index: u32) -> T { + let bucket_index = choose_bucket(hdl.len) as usize; + let next_bucket_index = choose_bucket(hdl.len - 1) as usize; + let mut slot = hdl.offset; + + let ret = self.buckets[bucket_index].remove_slot_entry(slot, index); + + if bucket_index != next_bucket_index { + // move to smaller bucket + debug_assert!(next_bucket_index < bucket_index); + let (left, right) = self.buckets.split_at_mut(bucket_index); + slot = right[0].move_slot(slot, &mut left[next_bucket_index]); + } + + hdl.offset = slot; + hdl.len -= 1; + ret + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn bucketvec_move_to() { + let spacing = 32; + let mut a: BucketVec = BucketVec::new(spacing); + let mut b: BucketVec = BucketVec::new(spacing); + let slot_offset = a.alloc_slot(); + for i in 0..spacing { + a.set_slot_entry(slot_offset, i, 1000 + i); + } + let slot = a.move_slot(slot_offset, &mut b); + for i in 0..spacing { + assert_eq!(*b.get_slot_entry(slot, i), 1000 + i); + } + + let mut c: BucketVec = BucketVec::new(spacing / 2); + let slot_offset = a.alloc_slot(); + for i in 0..spacing { + a.set_slot_entry(slot_offset, i, 1000 + i); + } + let slot = a.move_slot(slot_offset, &mut c); + for i in 0..spacing / 2 { + assert_eq!(*c.get_slot_entry(slot, i), 1000 + i); + } + } + + #[test] + fn bucketvec_get_slot_entry() { + let spacing = 16; + let mut bucket: BucketVec = BucketVec::new(spacing); + let slot = bucket.alloc_slot(); + for i in 0..spacing { + bucket.set_slot_entry(slot, i, 1000 + i); + } + for i in 0..spacing { + assert_eq!(*bucket.get_slot_entry(slot, i), 1000 + i); + } + } + + #[test] + fn bucketvec_get_slot_entry_mut() { + let spacing = 16; + let mut bucket: BucketVec = BucketVec::new(spacing); + let slot = bucket.alloc_slot(); + for i in 0..spacing { + bucket.set_slot_entry(slot, i, 1000 + i); + } + for i in 0..spacing { + let mut x = bucket.get_slot_entry_mut(slot, i); + *x += 1; + } + for i in 0..spacing { + assert_eq!(*bucket.get_slot_entry_mut(slot, i), 1000 + i + 1); + } + } + + #[test] + fn bucketvec_insert_slot_entry() { + let spacing = 16; + let mut bucket: BucketVec = BucketVec::new(spacing); + let slot = bucket.alloc_slot(); + for i in 0..spacing { + bucket.insert_slot_entry(slot, 0, i); + } + bucket.insert_slot_entry(slot, 0, 123456); + assert_eq!(*bucket.get_slot_entry(slot, 0), 123456); + assert_eq!(*bucket.get_slot_entry(slot, spacing - 1), 1); + assert_eq!(*bucket.get_slot_entry(slot, spacing - 2), 2); + } + + #[test] + fn allocator_new() { + Allocator::::new(); + } + + #[test] + fn allocator_alloc1() { + let mut alloc = Allocator::::new(); + let _ = alloc.alloc(1); + } + + #[test] + fn allocator_fill() { + let mut alloc = Allocator::::new(); + let mut hdl = alloc.alloc(0); + for i in 0..32 { + alloc.insert(&mut hdl, 0, 1000 + i); + } + let mut hdl = alloc.alloc(0); + for i in 0..32 { + alloc.insert(&mut hdl, 0, 2000 + i); + } + println!("{:?}", hdl); + println!("{:#?}", alloc); + } + + #[test] + fn allocator_drain() { + let mut alloc = Allocator::::new(); + let mut hdl = alloc.alloc(0); + assert!(hdl.len == 0); + let n = 32; + for i in 0..n { + alloc.insert(&mut hdl, 0, 1000 + i); + } + assert!(hdl.len == 32); + for i in 0..n { + let item = alloc.remove(&mut hdl, 0); + assert!(item == 1031 - i); + } + assert!(hdl.len == 0); + } + + #[test] + fn allocator_set() { + let mut alloc = Allocator::::new(); + let hdl = alloc.alloc(32); + for i in 0..32 { + alloc.set(&hdl, i, 1000 + i); + } + + for i in 0..32 { + assert_eq!(*alloc.get(&hdl, i), 1000 + i); + } + } + + #[test] + fn allocator_get_mut() { + let mut alloc = Allocator::::new(); + let hdl = alloc.alloc(32); + for i in 0..32 { + alloc.set(&hdl, i, 1000 + i); + } + + for i in 0..32 { + let mut x = alloc.get_mut(&hdl, i); + *x += 1; + } + + for i in 0..32 { + assert_eq!(*alloc.get(&hdl, i), 1000 + i + 1); + } + } + +} diff --git a/native/treebitmap_nif/src/tree_bitmap/mod.rs b/native/treebitmap_nif/src/tree_bitmap/mod.rs new file mode 100644 index 0000000..49bbdf6 --- /dev/null +++ b/native/treebitmap_nif/src/tree_bitmap/mod.rs @@ -0,0 +1,657 @@ +// Copyright 2016 Hroi Sigurdsson +// +// Licensed under the MIT license . +// This file may not be copied, modified, or distributed except according to those terms. + +#[cfg(feature = "alloc")] +use alloc::vec; +#[cfg(feature = "alloc")] +use alloc::vec::Vec; +use std::cmp; + +mod allocator; +mod node; + +use self::allocator::{Allocator, AllocatorHandle}; +use self::node::{MatchResult, Node}; +use std::ptr; + +// #[derive(Debug)] +pub struct TreeBitmap { + trienodes: Allocator, + results: Allocator, + len: usize, + should_drop: bool, // drop contents on drop? +} + +impl TreeBitmap { + /// Returns ````TreeBitmap ```` with 0 start capacity. + pub fn new() -> Self { + Self::with_capacity(0) + } + + /// Returns ```TreeBitmap``` with pre-allocated buffers of size n. + pub fn with_capacity(n: usize) -> Self { + let mut trieallocator: Allocator = Allocator::with_capacity(n); + let mut root_hdl = trieallocator.alloc(0); + trieallocator.insert(&mut root_hdl, 0, Node::new()); + + TreeBitmap { + trienodes: trieallocator, + results: Allocator::with_capacity(n), + len: 0, + should_drop: true, + } + } + + /// Returns handle to root node. + fn root_handle(&self) -> AllocatorHandle { + AllocatorHandle::generate(1, 0) + } + + /// Returns the root node. + #[cfg(test)] + #[allow(dead_code)] + fn root_node(&self) -> Node { + *self.trienodes.get(&self.root_handle(), 0) + } + + /// Push down results encoded in the last 16 bits into child trie nodes. + /// Makes ```node``` into a normal node. + fn push_down(&mut self, node: &mut Node) { + debug_assert!(node.is_endnode(), "push_down: not an endnode"); + debug_assert!(node.child_ptr == 0); + // count number of internal nodes in the first 15 bits (those that will + // remain in place). + let internal_node_count = (node.internal() & 0xffff_0000).count_ones(); + let remove_at = internal_node_count; + // count how many nodes to push down + // let nodes_to_pushdown = (node.bitmap & 0x0000_ffff).count_ones(); + let nodes_to_pushdown = (node.internal() & 0x0000_ffff).count_ones(); + if nodes_to_pushdown > 0 { + let mut result_hdl = node.result_handle(); + let mut child_node_hdl = self.trienodes.alloc(0); + + for _ in 0..nodes_to_pushdown { + // allocate space for child result value + let mut child_result_hdl = self.results.alloc(0); + // put result value in freshly allocated bucket + let result_value = self.results.remove(&mut result_hdl, remove_at); + self.results.insert(&mut child_result_hdl, 0, result_value); + // create and save child node + let mut child_node = Node::new(); + child_node.set_internal(1 << 31); + child_node.result_ptr = child_result_hdl.offset; + // append trienode to collection + let insert_node_at = child_node_hdl.len; + self.trienodes + .insert(&mut child_node_hdl, insert_node_at, child_node); + } + // the result data may have moved to a smaller bucket, update the + // result pointer + node.result_ptr = result_hdl.offset; + node.child_ptr = child_node_hdl.offset; + // no results from this node remain, free the result slot + if internal_node_count == 0 && nodes_to_pushdown > 0 { + self.results.free(&mut result_hdl); + node.result_ptr = 0; + } + } + node.make_normalnode(); + // note: we do not need to touch the external bits + } + + /// longest match lookup of ```nibbles```. Returns bits matched as u32, and reference to T. + pub fn longest_match(&self, nibbles: &[u8]) -> Option<(u32, &T)> { + let mut cur_hdl = self.root_handle(); + let mut cur_index = 0; + let mut bits_matched = 0; + let mut bits_searched = 0; + let mut best_match: Option<(AllocatorHandle, u32)> = None; // result handle + index + + for nibble in nibbles { + let cur_node = *self.trienodes.get(&cur_hdl, cur_index); + let match_mask = node::MATCH_MASKS[*nibble as usize]; + + if let MatchResult::Match(result_hdl, result_index, matching_bit_index) = + cur_node.match_internal(match_mask) + { + bits_matched = bits_searched; + bits_matched += node::BIT_MATCH[matching_bit_index as usize]; + best_match = Some((result_hdl, result_index)); + } + + if cur_node.is_endnode() { + break; + } + match cur_node.match_external(match_mask) { + MatchResult::Chase(child_hdl, child_index) => { + bits_searched += 4; + cur_hdl = child_hdl; + cur_index = child_index; + continue; + } + MatchResult::None => { + break; + } + _ => unreachable!(), + } + } + + match best_match { + Some((result_hdl, result_index)) => { + Some((bits_matched, self.results.get(&result_hdl, result_index))) + } + None => None, + } + } + + pub fn insert(&mut self, nibbles: &[u8], masklen: u32, value: T) -> Option { + let mut cur_hdl = self.root_handle(); + let mut cur_index = 0; + let mut bits_left = masklen; + let mut ret = None; + + let mut loop_count = 0; + loop { + let nibble = if loop_count < nibbles.len() { + nibbles[loop_count] + } else { + 0 + }; + loop_count += 1; + let nibble = &nibble; + + let mut cur_node = *self.trienodes.get(&cur_hdl, cur_index); + let match_result = cur_node.match_segment(*nibble); + + if let MatchResult::Chase(child_hdl, index) = match_result { + if bits_left >= 4 { + // follow existing branch + bits_left -= 4; + cur_hdl = child_hdl; + cur_index = index; + continue; + } + } + + let bitmap = node::gen_bitmap(*nibble, cmp::min(4, bits_left)); + + if (cur_node.is_endnode() && bits_left <= 4) || bits_left <= 3 { + // final node reached, insert results + let mut result_hdl = match cur_node.result_count() { + 0 => self.results.alloc(0), + _ => cur_node.result_handle(), + }; + let result_index = (cur_node.internal() + >> (bitmap & node::END_BIT_MASK).trailing_zeros()) + .count_ones(); + + if cur_node.internal() & (bitmap & node::END_BIT_MASK) > 0 { + // key already exists! + ret = Some(self.results.replace(&result_hdl, result_index - 1, value)); + } else { + cur_node.set_internal(bitmap & node::END_BIT_MASK); + self.results.insert(&mut result_hdl, result_index, value); // add result + self.len += 1; + } + cur_node.result_ptr = result_hdl.offset; + self.trienodes.set(&cur_hdl, cur_index, cur_node); // save trie node + return ret; + } + // add a branch + + if cur_node.is_endnode() { + // move any result pointers out of the way, so we can add branch + self.push_down(&mut cur_node); + } + let mut child_hdl = match cur_node.child_count() { + 0 => self.trienodes.alloc(0), + _ => cur_node.child_handle(), + }; + + let child_index = (cur_node.external() >> bitmap.trailing_zeros()).count_ones(); + + if cur_node.external() & (bitmap & node::END_BIT_MASK) == 0 { + // no existing branch; create it + cur_node.set_external(bitmap & node::END_BIT_MASK); + } else { + // follow existing branch + if let MatchResult::Chase(child_hdl, index) = cur_node.match_segment(*nibble) { + self.trienodes.set(&cur_hdl, cur_index, cur_node); // save trie node + bits_left -= 4; + cur_hdl = child_hdl; + cur_index = index; + continue; + } + unreachable!() + } + + // prepare a child node + let mut child_node = Node::new(); + child_node.make_endnode(); + self.trienodes + .insert(&mut child_hdl, child_index, child_node); // save child + cur_node.child_ptr = child_hdl.offset; + self.trienodes.set(&cur_hdl, cur_index, cur_node); // save trie node + + bits_left -= 4; + cur_hdl = child_hdl; + cur_index = child_index; + } + } + + pub fn mem_usage(&self) -> (usize, usize) { + let node_bytes = self.trienodes.mem_usage(); + let result_bytes = self.results.mem_usage(); + (node_bytes, result_bytes) + } + + pub fn len(&self) -> usize { + self.len + } + + pub fn exact_match(&self, nibbles: &[u8], masklen: u32) -> Option<&T> { + let mut cur_hdl = self.root_handle(); + let mut cur_index = 0; + let mut bits_left = masklen; + + for nibble in nibbles { + let cur_node = self.trienodes.get(&cur_hdl, cur_index); + let bitmap = node::gen_bitmap(*nibble, cmp::min(bits_left, 4)) & node::END_BIT_MASK; + let reached_final_node = bits_left < 4 || (cur_node.is_endnode() && bits_left == 4); + + if reached_final_node { + match cur_node.match_internal(bitmap) { + MatchResult::Match(result_hdl, result_index, _) => { + return Some(self.results.get(&result_hdl, result_index)); + } + _ => return None, + } + } + + match cur_node.match_external(bitmap) { + MatchResult::Chase(child_hdl, child_index) => { + cur_hdl = child_hdl; + cur_index = child_index; + bits_left -= 4; + } + _ => return None, + } + } + None + } + + /// Remove prefix. Returns existing value if the prefix previously existed. + pub fn remove(&mut self, nibbles: &[u8], masklen: u32) -> Option { + debug_assert!(nibbles.len() >= (masklen / 4) as usize); + let root_hdl = self.root_handle(); + let mut root_node = *self.trienodes.get(&root_hdl, 0); + let ret = self.remove_child(&mut root_node, nibbles, masklen); + self.trienodes.set(&root_hdl, 0, root_node); + ret + } + + // remove child and result from node + fn remove_child(&mut self, node: &mut Node, nibbles: &[u8], masklen: u32) -> Option { + let nibble = nibbles[0]; + let bitmap = node::gen_bitmap(nibble, cmp::min(masklen, 4)) & node::END_BIT_MASK; + let reached_final_node = masklen < 4 || (node.is_endnode() && masklen == 4); + + if reached_final_node { + match node.match_internal(bitmap) { + MatchResult::Match(mut result_hdl, result_index, _) => { + node.unset_internal(bitmap); + let ret = self.results.remove(&mut result_hdl, result_index); + if node.result_count() == 0 { + self.results.free(&mut result_hdl); + } + node.result_ptr = result_hdl.offset; + self.len -= 1; + return Some(ret); + } + _ => return None, + } + } + + if let MatchResult::Chase(mut child_node_hdl, index) = node.match_external(bitmap) { + let mut child_node = *self.trienodes.get(&child_node_hdl, index); + let ret = self.remove_child(&mut child_node, &nibbles[1..], masklen - 4); + + if child_node.child_count() == 0 && !child_node.is_endnode() { + child_node.make_endnode(); + } + if child_node.is_empty() { + self.trienodes.remove(&mut child_node_hdl, index); + node.unset_external(bitmap); + if child_node_hdl.len == 0 { + // no child nodes + self.trienodes.free(&mut child_node_hdl); + } + node.child_ptr = child_node_hdl.offset; + } else { + node.child_ptr = child_node_hdl.offset; + self.trienodes.set(&child_node_hdl, index, child_node); + } + ret + } else { + None + } + } + + pub fn iter(&self) -> Iter { + let root_hdl = self.root_handle(); + let root_node = *self.trienodes.get(&root_hdl, 0); + Iter { + inner: self, + path: vec![PathElem { + node: root_node, + pos: 0, + }], + nibbles: vec![0], + } + } + + pub fn iter_mut(&mut self) -> IterMut { + let root_hdl = self.root_handle(); + let root_node = *self.trienodes.get(&root_hdl, 0); + IterMut { + inner: self, + path: vec![PathElem { + node: root_node, + pos: 0, + }], + nibbles: vec![0], + } + } +} + +#[derive(Debug)] +struct PathElem { + node: Node, + pos: usize, +} + +pub struct Iter<'a, T: 'a> { + inner: &'a TreeBitmap, + path: Vec, + nibbles: Vec, +} + +pub struct IterMut<'a, T: 'a> { + inner: &'a mut TreeBitmap, + path: Vec, + nibbles: Vec, +} + +#[cfg_attr(rustfmt, rustfmt_skip)] +static PREFIX_OF_BIT: [u8; 32] = [// 0 1 2 3 4 5 6 7 + 0b0000, 0b0000, 0b1000, 0b0000, 0b0100, 0b1000, 0b1100, 0b0000, + // 8 9 10 11 12 13 14 15 + 0b0010, 0b0100, 0b0110, 0b1000, 0b1010, 0b1100, 0b1110, 0, + // 16 17 18 19 20 21 22 23 + 0b0000, 0b0001, 0b0010, 0b0011, 0b0100, 0b0101, 0b0110, 0b0111, + // 24 25 26 27 28 29 30 31 + 0b1000, 0b1001, 0b1010, 0b1011, 0b1100, 0b1101, 0b1110, 0b1111]; + +fn next( + trie: &TreeBitmap, + path: &mut Vec, + nibbles: &mut Vec, +) -> Option<(Vec, u32, AllocatorHandle, u32)> { + loop { + let mut path_elem = match path.pop() { + Some(elem) => elem, + None => return None, + }; + let cur_node = path_elem.node; + let mut cur_pos = path_elem.pos; + nibbles.pop(); + // optim: + if cur_pos == 0 && cur_node.result_count() == 0 { + path_elem.pos = 16; + cur_pos = 16; + } + if path_elem.pos == 32 { + continue; + } + let nibble = PREFIX_OF_BIT[path_elem.pos]; + let bitmap = 1 << (31 - path_elem.pos); + + path_elem.pos += 1; + nibbles.push(nibble); + path.push(path_elem); + // match internal + if cur_pos < 16 || cur_node.is_endnode() { + let match_result = cur_node.match_internal(bitmap); + if let MatchResult::Match(result_hdl, result_index, matching_bit) = match_result { + let bits_matched = + ((path.len() as u32) - 1) * 4 + node::BIT_MATCH[matching_bit as usize]; + return Some((nibbles.clone(), bits_matched, result_hdl, result_index)); + } + } else if let MatchResult::Chase(child_hdl, child_index) = cur_node.match_external(bitmap) { + let child_node = trie.trienodes.get(&child_hdl, child_index); + nibbles.push(0); + path.push(PathElem { + node: *child_node, + pos: 0, + }); + } + } +} + +impl<'a, T: 'a> Iterator for Iter<'a, T> { + type Item = (Vec, u32, &'a T); //(nibbles, masklen, &T) + + fn next(&mut self) -> Option { + match next(self.inner, &mut self.path, &mut self.nibbles) { + Some((path, bits_matched, hdl, index)) => { + let value = self.inner.results.get(&hdl, index); + Some((path, bits_matched, value)) + } + None => None, + } + } +} + +impl<'a, T: 'a> Iterator for IterMut<'a, T> { + type Item = (Vec, u32, &'a mut T); //(nibbles, masklen, &T) + + fn next(&mut self) -> Option { + match next(self.inner, &mut self.path, &mut self.nibbles) { + Some((path, bits_matched, hdl, index)) => unsafe { + let ptr: *mut T = self.inner.results.get_mut(&hdl, index); + let val_ref = &mut *ptr; + Some((path, bits_matched, val_ref)) + }, + None => None, + } + } +} + +pub struct IntoIter { + inner: TreeBitmap, + path: Vec, + nibbles: Vec, +} + +impl<'a, T: 'a> Iterator for IntoIter { + type Item = (Vec, u32, T); //(nibbles, masklen, T) + + fn next(&mut self) -> Option { + match next(&self.inner, &mut self.path, &mut self.nibbles) { + Some((path, bits_matched, hdl, index)) => { + let value = self.inner.results.get(&hdl, index); + let value = unsafe { ptr::read(value) }; + Some((path, bits_matched, value)) + } + None => None, + } + } +} + +impl IntoIterator for TreeBitmap { + type Item = (Vec, u32, T); //(nibbles, masklen, T) + type IntoIter = IntoIter; + + fn into_iter(mut self) -> IntoIter { + let root_hdl = self.root_handle(); + let root_node = *self.trienodes.get(&root_hdl, 0); + self.should_drop = false; // IntoIter will drop contents + IntoIter { + inner: self, + path: vec![PathElem { + node: root_node, + pos: 0, + }], + nibbles: vec![0], + } + } +} + +impl Drop for IntoIter { + fn drop(&mut self) { + for _ in self {} + } +} + +impl Drop for TreeBitmap { + fn drop(&mut self) { + if self.should_drop { + for (_, _, item) in self.iter() { + unsafe { + ptr::read(item); + } + } + } + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn len() { + let mut tbm: TreeBitmap<&str> = TreeBitmap::new(); + assert_eq!(tbm.len(), 0); + + let (nibbles_a, mask_a) = (&[0, 10, 0, 0, 0, 0, 0, 0], 8); + let (nibbles_b, mask_b) = (&[0, 10, 0, 10, 0, 10, 0, 0], 24); + + tbm.insert(nibbles_a, mask_a, "foo"); + assert_eq!(tbm.len(), 1); + + // Insert same nibbles again + tbm.insert(nibbles_a, mask_a, "foo2"); + assert_eq!(tbm.len(), 1); + + tbm.insert(nibbles_b, mask_b, "bar"); + assert_eq!(tbm.len(), 2); + + tbm.remove(nibbles_b, mask_b); + assert_eq!(tbm.len(), 1); + + tbm.remove(nibbles_a, mask_a); + assert_eq!(tbm.len(), 0); + } + + #[test] + fn remove() { + let mut tbm: TreeBitmap<&str> = TreeBitmap::new(); + let (nibbles_a, mask_a) = (&[0, 10, 0, 0, 0, 0, 0, 0], 8); + let (nibbles_b, mask_b) = (&[0, 10, 0, 10, 0, 10, 0, 0], 24); + tbm.insert(nibbles_a, mask_a, "foo"); + tbm.insert(nibbles_b, mask_b, "bar"); + { + let value = tbm.remove(nibbles_b, mask_b); + assert_eq!(value, Some("bar")); + let lookup_result = tbm.longest_match(nibbles_b); + assert_eq!(lookup_result, Some((mask_a, &"foo"))); + } + // foo should not exist, and therefore return None + let value = tbm.remove(nibbles_b, mask_b); + assert_eq!(value, None); + } + + #[test] + fn iter() { + let mut tbm: TreeBitmap = TreeBitmap::new(); + let (nibbles_a, mask_a) = (&[0], 0); + let (nibbles_b, mask_b) = (&[0, 10], 8); + let (nibbles_c, mask_c) = (&[0, 10, 0, 10, 0, 10], 24); + let (nibbles_d, mask_d) = (&[0, 10, 0, 10, 1, 11], 24); + tbm.insert(nibbles_a, mask_a, 1); + tbm.insert(nibbles_b, mask_b, 2); + tbm.insert(nibbles_c, mask_c, 3); + tbm.insert(nibbles_d, mask_d, 4); + + let mut iter = tbm.iter(); + assert_eq!(iter.next().unwrap().2, &1); + assert_eq!(iter.next().unwrap().2, &2); + assert_eq!(iter.next().unwrap().2, &3); + assert_eq!(iter.next().unwrap().2, &4); + assert_eq!(iter.next(), None); + } + + #[test] + fn into_iter() { + let mut tbm: TreeBitmap = TreeBitmap::new(); + let (nibbles_a, mask_a) = (&[0], 0); + let (nibbles_b, mask_b) = (&[0, 10], 8); + let (nibbles_c, mask_c) = (&[0, 10, 0, 10, 0, 10], 24); + let (nibbles_d, mask_d) = (&[0, 10, 0, 10, 1, 11], 24); + tbm.insert(nibbles_a, mask_a, 1); + tbm.insert(nibbles_b, mask_b, 2); + tbm.insert(nibbles_c, mask_c, 3); + tbm.insert(nibbles_d, mask_d, 4); + + let mut iter = tbm.into_iter(); + assert_eq!(iter.next().unwrap().2, 1); + assert_eq!(iter.next().unwrap().2, 2); + assert_eq!(iter.next().unwrap().2, 3); + assert_eq!(iter.next().unwrap().2, 4); + assert_eq!(iter.next(), None); + } + + struct Thing { + id: usize, + } + impl Drop for Thing { + fn drop(&mut self) { + println!("dropping id {}", self.id); + } + } + + #[test] + fn drop() { + let mut tbm: TreeBitmap = TreeBitmap::new(); + let (nibbles_a, mask_a) = (&[0], 0); + let (nibbles_b, mask_b) = (&[0, 10], 8); + let (nibbles_c, mask_c) = (&[0, 10, 0, 10, 0, 10], 24); + let (nibbles_d, mask_d) = (&[0, 10, 0, 10, 1, 11], 24); + tbm.insert(nibbles_a, mask_a, Thing { id: 1 }); + tbm.insert(nibbles_b, mask_b, Thing { id: 2 }); + tbm.insert(nibbles_c, mask_c, Thing { id: 3 }); + tbm.insert(nibbles_d, mask_d, Thing { id: 4 }); + println!("should drop"); + } + + #[test] + fn into_iter_drop() { + let mut tbm: TreeBitmap = TreeBitmap::new(); + let (nibbles_a, mask_a) = (&[0], 0); + let (nibbles_b, mask_b) = (&[0, 10], 8); + let (nibbles_c, mask_c) = (&[0, 10, 0, 10, 0, 10], 24); + let (nibbles_d, mask_d) = (&[0, 10, 0, 10, 1, 11], 24); + tbm.insert(nibbles_a, mask_a, Thing { id: 1 }); + tbm.insert(nibbles_b, mask_b, Thing { id: 2 }); + tbm.insert(nibbles_c, mask_c, Thing { id: 3 }); + tbm.insert(nibbles_d, mask_d, Thing { id: 4 }); + let mut iter = tbm.into_iter(); + iter.next(); + iter.next(); + println!("should drop 3 - 4"); + } + +} diff --git a/native/treebitmap_nif/src/tree_bitmap/node.rs b/native/treebitmap_nif/src/tree_bitmap/node.rs new file mode 100644 index 0000000..606dba1 --- /dev/null +++ b/native/treebitmap_nif/src/tree_bitmap/node.rs @@ -0,0 +1,457 @@ +// Copyright 2016 Hroi Sigurdsson +// +// Licensed under the MIT license . +// This file may not be copied, modified, or distributed except according to those terms. + +use super::allocator::AllocatorHandle; +#[cfg(feature = "alloc")] +use alloc::format; +#[cfg(feature = "alloc")] +use alloc::vec::Vec; + +pub const INT_MASK: u32 = 0xffff_0000; +pub const EXT_MASK: u32 = 0x0000_ffff; +pub const END_BIT: u32 = 1 << 16; +pub const END_BIT_MASK: u32 = !END_BIT; // all bits except the end node bit + +type Table = [[u32; 16]; 5]; +const IS_END_NODE: u32 = 1 << 16; + +#[cfg_attr(rustfmt, rustfmt_skip)] +static INTERNAL_LOOKUP_TABLE: Table = [ + // mask = 00000, 0/0 + [1<<31, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], + // mask = 00001, 0-1/1 + [1<<30, 0, 0, 0, 0, 0, 0, 0, 1<<29, 0, 0, 0, 0, 0, 0, 0], + // mask = 00011, 0-3/2 + [1<<28, 0, 0, 0, 1<<27, 0, 0, 0, 1<<26, 0, 0, 0, 1<<25, 0, 0, 0], + // mask = 00111, 0-7/3 + [1<<24, 0, 1<<23, 0, 1<<22, 0, 1<<21, 0, 1<<20, 0, 1<<19, 0, 1<<18, 0, 1<<17, 0], + // endnode indicated in 16 bit, skip + // mask = 01111, 0-15/4 + [IS_END_NODE | 1<<15, IS_END_NODE | 1<<14, IS_END_NODE | 1<<13, IS_END_NODE | 1<<12, + IS_END_NODE | 1<<11, IS_END_NODE | 1<<10, IS_END_NODE | 1<< 9, IS_END_NODE | 1<< 8, + IS_END_NODE | 1<< 7, IS_END_NODE | 1<< 6, IS_END_NODE | 1<< 5, IS_END_NODE | 1<< 4, + IS_END_NODE | 1<< 3, IS_END_NODE | 1<< 2, IS_END_NODE | 1<< 1, IS_END_NODE | 1], +]; + +pub const MSB: u32 = 1 << 31; + +#[cfg_attr(rustfmt, rustfmt_skip)] +pub static MATCH_MASKS: [u32; 16] = [MSB | MSB >> 1 | MSB >> 3 | MSB >> 7 | MSB >> 16, // 0000 + MSB | MSB >> 1 | MSB >> 3 | MSB >> 7 | MSB >> 17, // 0001 + MSB | MSB >> 1 | MSB >> 3 | MSB >> 8 | MSB >> 18, // 0010 + MSB | MSB >> 1 | MSB >> 3 | MSB >> 8 | MSB >> 19, // 0011 + + MSB | MSB >> 1 | MSB >> 4 | MSB >> 9 | MSB >> 20, // 0100 + MSB | MSB >> 1 | MSB >> 4 | MSB >> 9 | MSB >> 21, // 0101 + MSB | MSB >> 1 | MSB >> 4 | MSB >> 10 | MSB >> 22, // 0110 + MSB | MSB >> 1 | MSB >> 4 | MSB >> 10 | MSB >> 23, // 0111 + + MSB | MSB >> 2 | MSB >> 5 | MSB >> 11 | MSB >> 24, // 1000 + MSB | MSB >> 2 | MSB >> 5 | MSB >> 11 | MSB >> 25, // 1001 + MSB | MSB >> 2 | MSB >> 5 | MSB >> 12 | MSB >> 26, // 1010 + MSB | MSB >> 2 | MSB >> 5 | MSB >> 12 | MSB >> 27, // 1011 + + MSB | MSB >> 2 | MSB >> 6 | MSB >> 13 | MSB >> 28, // 1100 + MSB | MSB >> 2 | MSB >> 6 | MSB >> 13 | MSB >> 29, // 1101 + MSB | MSB >> 2 | MSB >> 6 | MSB >> 14 | MSB >> 30, // 1110 + MSB | MSB >> 2 | MSB >> 6 | MSB >> 14 | MSB >> 31 /* 1111 */]; + +#[inline] +pub fn gen_bitmap(prefix: u8, masklen: u32) -> u32 { + debug_assert!(prefix < 16); // only nibbles allowed + debug_assert!(masklen < 5); + let ret = INTERNAL_LOOKUP_TABLE[masklen as usize][prefix as usize]; + debug_assert!(ret > 0); + ret +} + +/// ```Node ``` encodes result and child node pointers in a bitmap. +/// +/// A trie node can encode up to 31 results when acting as an "end node", or 16 +/// results and 16 children/subtrees. +/// +/// Each bit in the bitmap has the following meanings: +/// +/// | bit | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | +/// |-------|---|----|----|-----|-----|-----|-----|------| +/// | match | * | 0* | 1* | 00* | 01* | 10* | 11* | 000* | +/// +/// | bit | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | +/// |-------|------|------|------|------|------|------|------|-------------| +/// | match | 001* | 010* | 011* | 100* | 101* | 110* | 111* | endnode-bit | + +/// If the end node bit is set, the last bits are also used to match internal +/// nodes: +/// +/// | bit | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | +/// |-------|-------|-------|-------|-------|-------|-------|-------|-------| +/// | match | 0000* | 0001* | 0010* | 0011* | 0100* | 0101* | 0110* | 0111* | +/// +/// | bit | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | +/// |-------|-------|-------|-------|-------|-------|-------|-------|-------| +/// | match | 1000* | 1001* | 1010* | 1011* | 1100* | 1101* | 1110* | 1111* | + +/// The location of the result value is computed with the ```result_ptr``` base +/// pointer and the number of bits set left of the matching bit. +/// +/// If the endnode bit is not set, the last 16 bits encodes pointers to child +/// nodes. +/// If bit N is set it means that a child node with segment value N is present. +/// The pointer to the child node is then computed with the ```child_ptr``` base +/// pointer and the number of bits set left of N. +#[derive(Clone, Copy)] +pub struct Node { + /// child/result bitmap + bitmap: u32, // first 16 bits: internal, last 16 bits: child bitmap + /// child base pointer + pub child_ptr: u32, + /// results base pointer + pub result_ptr: u32, +} + +pub const BIT_MATCH: [u32; 32] = [ + 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 0, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, +]; + +#[cfg_attr(rustfmt, rustfmt_skip)] +const BIT_MEANING: &[&str] = &[ + "*", + "0*", "1*", + "00*", "01*", "10*", "11*", + "000*", "001*", "010*", "011*", "100*", "101*", "110*", "111*", + "END", + "0000*", "0001*", "0010*", "0011*", "0100*", "0101*", "0110*", "0111*", + "1000*", "1001*", "1010*", "1011*", "1100*", "1101*", "1110*", "1111*", +]; + +use std::fmt; +impl fmt::Debug for Node { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + let mut int_nodes: Vec<&str> = Vec::new(); + let mut child_nodes: Vec = Vec::new(); + let mut selector = 1 << 31; + for meaning in BIT_MEANING { + if self.internal() & selector > 0 { + int_nodes.push(meaning); + } + selector >>= 1; + } + + selector = 1 << 15; + for i in 0..16 { + if self.external() & selector > 0 { + child_nodes.push(i); + } + selector >>= 1; + } + + let bitmap_string = format!("{:016b} {:016b}", self.bitmap >> 16, self.bitmap & EXT_MASK); + + if self.is_endnode() { + return f + .debug_struct("EndNode") + .field("bitmap", &bitmap_string) + .field("internal", &int_nodes) + .field("result_ptr", &self.result_ptr) + .finish(); + } + if self.is_blank() { + return f.debug_struct("BlankNode").finish(); + } + f.debug_struct("InternalNode") + .field("bitmap", &bitmap_string) + .field("internal", &int_nodes) + .field("children", &child_nodes) + .field("child_ptr", &self.child_ptr) + .field("result_ptr", &self.result_ptr) + .finish() + } +} + +impl Node { + /// Get a fresh, blank node. + pub fn new() -> Self { + Node { + bitmap: 0, + child_ptr: 0, + result_ptr: 0, + } + } + + /// Is node blank? + pub fn is_blank(&self) -> bool { + self.bitmap == 0 && self.child_ptr == 0 && self.result_ptr == 0 + } + + /// Is node empty? + #[inline] + pub fn is_empty(&self) -> bool { + self.bitmap & END_BIT_MASK == 0 + } + + /// Is node an end node? + #[inline] + pub fn is_endnode(&self) -> bool { + self.bitmap & END_BIT > 0 + } + + /// Get internal bitmap (result entries). Any external bits are filtered. + #[inline] + pub fn internal(&self) -> u32 { + if self.is_endnode() { + self.bitmap & END_BIT_MASK // filter the end node bit + } else { + self.bitmap & INT_MASK + } + } + + /// Get external bitmap (child entries). Any internal bits are filtered. + #[inline] + pub fn external(&self) -> u32 { + if self.is_endnode() { + 0 + } else { + self.bitmap & EXT_MASK + } + } + + /// Set the endnode-bit. + /// # Panics + /// + if bit already set. + /// + if there are any external node pointers. + #[inline] + pub fn make_endnode(&mut self) { + debug_assert!(!self.is_endnode(), "make_endnode: already an endnode."); + debug_assert!( + self.external() == 0, + "cannot make into endnode when there are children present" + ); + self.bitmap |= END_BIT + } + + /// Unset the endnode-bit. + /// # Panics + /// + if not already an endnode. + #[inline] + pub fn make_normalnode(&mut self) { + debug_assert!(self.is_endnode(), "make_endnode: already a normalnode."); + self.bitmap &= END_BIT_MASK + } + + /// Get number of child pointers. + #[inline] + pub fn child_count(&self) -> u32 { + self.external().count_ones() + } + + /// Get number of result pointers. + #[inline] + pub fn result_count(&self) -> u32 { + self.internal().count_ones() + } + + /// Get handle to the results. + #[inline] + pub fn result_handle(&self) -> AllocatorHandle { + AllocatorHandle::generate(self.result_count(), self.result_ptr) + } + + /// Get handle to child nodes. + #[inline] + pub fn child_handle(&self) -> AllocatorHandle { + AllocatorHandle::generate(self.child_count(), self.child_ptr) + } + + /// Set an internal bit. + #[inline] + pub fn set_internal(&mut self, bitmap: u32) { + debug_assert!( + bitmap.count_ones() == 1, + "set_internal: bitmap must contain exactly one bit" + ); + debug_assert!( + bitmap & END_BIT == 0, + "set_internal: not permitted to set the endnode bit" + ); + debug_assert!(self.bitmap & bitmap == 0, "set_internal: bit already set"); + if !self.is_endnode() { + debug_assert!( + bitmap & EXT_MASK == 0, + "set_internal: attempted to set external bit" + ); + } + self.bitmap |= bitmap + } + + /// Unset an internal bit. + #[inline] + pub fn unset_internal(&mut self, bitmap: u32) { + debug_assert!( + bitmap.count_ones() == 1, + "unset_internal: bitmap must contain exactly one bit" + ); + debug_assert!( + bitmap & END_BIT == 0, + "unset_internal: not permitted to set the endnode bit" + ); + debug_assert!( + self.bitmap & bitmap == bitmap, + "unset_internal: bit already unset" + ); + if !self.is_endnode() { + debug_assert!( + bitmap & EXT_MASK == 0, + "unset_internal: attempted to set external bit" + ); + } + self.bitmap ^= bitmap + } + + /// Set an external bit. + #[inline] + pub fn set_external(&mut self, bitmap: u32) { + debug_assert!( + !self.is_endnode(), + "set_external: endnodes don't have external bits" + ); + debug_assert!( + bitmap & END_BIT == 0, + "set_external: not permitted to set the endnode bit" + ); + debug_assert!( + self.bitmap & bitmap == 0, + "set_external: not permitted to set an already set bit" + ); + debug_assert!( + bitmap & INT_MASK == 0, + "set_external: not permitted to set an internal bit" + ); + self.bitmap |= bitmap + } + + pub fn unset_external(&mut self, bitmap: u32) { + debug_assert!( + !self.is_endnode(), + "unset_external: endnodes don't have external bits" + ); + debug_assert!( + bitmap & END_BIT == 0, + "unset_external: not permitted to set the endnode bit" + ); + debug_assert!( + self.bitmap & bitmap == bitmap, + "unset_external: not permitted to unset an already unset bit" + ); + debug_assert!( + bitmap & INT_MASK == 0, + "unset_external: not permitted to set an internal bit" + ); + self.bitmap ^= bitmap + } + + /// Perform a match on segment/masklen. + #[inline] + pub fn match_segment(&self, segment: u8) -> MatchResult { + let match_mask = MATCH_MASKS[segment as usize]; + match self.match_external(match_mask) { + MatchResult::None => self.match_internal(match_mask), + x => x, + } + } + + #[inline] + pub fn match_internal(&self, match_mask: u32) -> MatchResult { + let result_match = self.internal() & match_mask; + if result_match > 0 { + let result_hdl = self.result_handle(); + let best_match_bit_index = 31 - result_match.trailing_zeros(); + let best_match_result_index = match best_match_bit_index { + 0 => 0, + _ => (self.internal() >> (32 - best_match_bit_index)).count_ones(), + }; + return MatchResult::Match(result_hdl, best_match_result_index, best_match_bit_index); + } + MatchResult::None + } + + #[inline] + pub fn match_external(&self, match_mask: u32) -> MatchResult { + let child_match = self.external() & match_mask; + if child_match > 0 { + let child_hdl = self.child_handle(); + let best_match_bit_index = 31 - child_match.trailing_zeros(); + let best_match_child_index = match best_match_bit_index { + 0 => 0, + _ => (self.external() >> (32 - best_match_bit_index)).count_ones(), + }; + return MatchResult::Chase(child_hdl, best_match_child_index); + } + MatchResult::None + } +} + +#[derive(Debug)] +pub enum MatchResult { + Match(AllocatorHandle, u32, u32), // result_handle, offset, matching bits + Chase(AllocatorHandle, u32), // child_handle, offset + None, // Node does not match +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_trienode_new() { + Node::new(); + } + + #[test] + fn match_segment() { + // case 1 + let mut node = Node::new(); + node.make_endnode(); + node.set_internal(MSB >> 2); // 1* + node.set_internal(MSB >> 4); // 01* + node.set_internal(MSB >> 9); // 010* + println!("{:#?}", node); + + let segment = 0b1111; + let match_result = node.match_segment(segment); + println!("match_segment({:04b}): {:?}", segment, match_result); + match match_result { + MatchResult::Match(_, _, _) => (), + _ => panic!("match failure"), + } + + let segment = 0b0011; + let match_result = node.match_segment(segment); + println!("match_segment({:04b}): {:?}", segment, match_result); + match match_result { + MatchResult::None => {} + _ => panic!("match failure"), + } + + let mut node = Node::new(); + node.set_external(MSB >> 23); // 0111* + + let segment = 0b0011; + let match_result = node.match_segment(segment); + println!("match_segment({:04b}): {:?}", segment, match_result); + match match_result { + MatchResult::None => {} + _ => panic!("match failure"), + } + + let segment = 0b0111; + let match_result = node.match_segment(segment); + println!("match_segment({:04b}): {:?}", segment, match_result); + match match_result { + MatchResult::Chase(_, _) => {} + _ => panic!("match failure"), + } + } + +} diff --git a/priv/native/libtreebitmap_nif.so b/priv/native/libtreebitmap_nif.so index 729cdbe..5d2936f 100755 Binary files a/priv/native/libtreebitmap_nif.so and b/priv/native/libtreebitmap_nif.so differ diff --git a/test/tree_bitmap_test.exs b/test/tree_bitmap_test.exs index ff1359f..aedf78f 100644 --- a/test/tree_bitmap_test.exs +++ b/test/tree_bitmap_test.exs @@ -2,66 +2,125 @@ defmodule TreeBitmapTest do use ExUnit.Case doctest TreeBitmap alias TreeBitmap.NIF + alias TreeBitmap + + test "TreeBitmap" do + t = TreeBitmap.new() + assert nil == TreeBitmap.add(t, {192, 168, 1, 0}, 24, :lan) + assert nil == TreeBitmap.add(t, {8193, 3512, 34211, 0, 0, 35374, 880, 1}, 64, :lan) + + assert %{value: :lan} = TreeBitmap.longest_match(t, {192, 168, 1, 2}) + assert true = TreeBitmap.longest_match?(t, {192, 168, 1, 2}) + assert %{value: :lan} = TreeBitmap.longest_match(t, {8193, 3512, 34211, 0, 0, 35374, 880, 29492}) + assert true = TreeBitmap.longest_match?(t, {8193, 3512, 34211, 0, 0, 35374, 880, 29492}) + + assert :lan = TreeBitmap.exact_match(t, {192, 168, 1, 1}, 24) + assert true = TreeBitmap.exact_match?(t, {192, 168, 1, 1}, 24) + assert :lan = TreeBitmap.exact_match(t, {8193, 3512, 34211, 0, 0, 35374, 880, 29492}, 64) + assert true = TreeBitmap.exact_match?(t, {8193, 3512, 34211, 0, 0, 35374, 880, 29492}, 64) + + assert nil == TreeBitmap.longest_match(t, {8, 8, 8, 8}) + assert false == TreeBitmap.longest_match?(t, {8, 8, 8, 8}) + assert nil == TreeBitmap.exact_match(t, {8, 8, 8, 8}, 32) + assert false == TreeBitmap.exact_match?(t, {8, 8, 8, 8}, 32) + + assert %{ets: 335, inet4: {1248, 1168}, inet6: {1344, 1168}} = TreeBitmap.memory(t) + + assert %{ets: 3, inet4: 1, inet6: 1} = TreeBitmap.length(t) + assert :lan = TreeBitmap.remove(t, {8193, 3512, 34211, 0, 0, 35374, 880, 1}, 64) + assert nil == TreeBitmap.longest_match(t, {8193, 3512, 34211, 0, 0, 35374, 880, 29492}) + assert %{ets: 2, inet4: 1, inet6: 0} = TreeBitmap.length(t) + + assert nil == TreeBitmap.add(t, {8193, 3512, 34211, 0, 0, 35374, 880, 1}, 64, :lan) + assert :lan = TreeBitmap.add(t, {8193, 3512, 34211, 0, 0, 35374, 880, 1}, 64, :lan2) + assert %{ets: 3, inet4: 1, inet6: 1} = TreeBitmap.length(t) + end test "new/0" do table = NIF.new() assert is_reference(table) end + test "memory/1" do + table = NIF.new() + assert {1200, 1152} == NIF.memory(table) + {:ok, _} = NIF.add(table, {:inet4, 192, 168, 1, 0}, 24, 0) + assert {1248, 1168} == NIF.memory(table) + end + + test "new_with_capacity/1" do + table = NIF.new_with_capacity(1000) + assert is_reference(table) + assert {109152, 37152} = NIF.memory(table) + end + test "length/1" do table = NIF.new() assert 0 == NIF.length(table) end - test "add/4 and lookup/2" do + test "add/4 and longest_match/2" do + table = NIF.new() + assert {:ok, _} = NIF.add(table, {:inet4, 192, 168, 1, 0}, 24, 0) + assert {:ok, _, 24, 0} = NIF.longest_match(table, {:inet4, 192, 168, 1, 1}) + assert {:ok, nil} = NIF.longest_match(table, {:inet4, 1, 1, 1, 1}) + end + + test "add/2 existing" do + table = NIF.new() + {:ok, nil} = NIF.add(table, {:inet4, 10, 69, 0, 0}, 16, 0) + assert {:ok, 0} = NIF.add(table, {:inet4, 10, 69, 0, 0}, 16, 1) + assert {:ok, _, _, 1} = NIF.longest_match(table, {:inet4, 10, 69, 1, 1}) + end + + test "remove/3" do table = NIF.new() - assert :ok == NIF.add(table, {:inet4, 192, 168, 1, 0}, 24, 0) - assert {:ok, _, 24, 0} = NIF.lookup(table, {:inet4, 192, 168, 1, 1}) - assert {:ok, nil} = NIF.lookup(table, {:inet4, 1, 1, 1, 1}) + {:ok, _} = NIF.add(table, {:inet4, 192, 168, 1, 0}, 24, 0) + assert {:ok, 0} == NIF.remove(table, {:inet4, 192, 168, 1, 0}, 24) + assert {:ok, nil} = NIF.longest_match(table, {:inet4, 192, 168, 1, 1}) end - test "remove/2" do + test "exact_match/3" do table = NIF.new() - assert :ok == NIF.add(table, {:inet4, 192, 168, 1, 0}, 24, 0) - assert {:ok, _, 24, 0} = NIF.lookup(table, {:inet4, 192, 168, 1, 1}) - assert :ok == NIF.remove(table, {:inet4, 192, 168, 1, 0}, 24) - assert {:ok, nil} = NIF.lookup(table, {:inet4, 192, 168, 1, 1}) + {:ok, _} = NIF.add(table, {:inet4, 192, 168, 1, 0}, 24, 0) + assert {:ok, 0} = NIF.exact_match(table, {:inet4, 192, 168, 1, 0}, 24) + assert {:ok, nil} = NIF.exact_match(table, {:inet4, 192, 168, 1, 1}, 32) end test "default route" do table = NIF.new() - assert :ok == NIF.add(table, {:inet4, 0, 0, 0, 0}, 0, 0) - assert {:ok, _, 0, 0} = NIF.lookup(table, {:inet4, 192, 168, 1, 1}) + assert {:ok, nil} == NIF.add(table, {:inet4, 0, 0, 0, 0}, 0, 0) + assert {:ok, _, 0, 0} = NIF.longest_match(table, {:inet4, 192, 168, 1, 1}) end test "more to less specific" do table = NIF.new() - :ok = NIF.add(table, {:inet4, 10, 69, 1, 0}, 24, 2) - :ok = NIF.add(table, {:inet4, 10, 69, 0, 0}, 16, 1) - :ok = NIF.add(table, {:inet4, 0, 0, 0, 0}, 0, 0) - assert {:ok, _, _, 0} = NIF.lookup(table, {:inet4, 8, 8, 8, 8}) - assert {:ok, _, _, 2} = NIF.lookup(table, {:inet4, 10, 69, 1, 2}) - assert {:ok, _, _, 1} = NIF.lookup(table, {:inet4, 10, 69, 2, 2}) + {:ok, _} = NIF.add(table, {:inet4, 10, 69, 1, 0}, 24, 2) + {:ok, _} = NIF.add(table, {:inet4, 10, 69, 0, 0}, 16, 1) + {:ok, _} = NIF.add(table, {:inet4, 0, 0, 0, 0}, 0, 0) + assert {:ok, _, _, 0} = NIF.longest_match(table, {:inet4, 8, 8, 8, 8}) + assert {:ok, _, _, 2} = NIF.longest_match(table, {:inet4, 10, 69, 1, 2}) + assert {:ok, _, _, 1} = NIF.longest_match(table, {:inet4, 10, 69, 2, 2}) end test "less to more specific" do table = NIF.new() - :ok = NIF.add(table, {:inet4, 0, 0, 0, 0}, 0, 0) - :ok = NIF.add(table, {:inet4, 10, 69, 0, 0}, 16, 1) - :ok = NIF.add(table, {:inet4, 10, 69, 1, 0}, 24, 2) - assert {:ok, _, _, 0} = NIF.lookup(table, {:inet4, 8, 8, 8, 8}) - assert {:ok, _, _, 2} = NIF.lookup(table, {:inet4, 10, 69, 1, 2}) - assert {:ok, _, _, 1} = NIF.lookup(table, {:inet4, 10, 69, 2, 2}) + {:ok, _} = NIF.add(table, {:inet4, 0, 0, 0, 0}, 0, 0) + {:ok, _} = NIF.add(table, {:inet4, 10, 69, 0, 0}, 16, 1) + {:ok, _} = NIF.add(table, {:inet4, 10, 69, 1, 0}, 24, 2) + assert {:ok, _, _, 0} = NIF.longest_match(table, {:inet4, 8, 8, 8, 8}) + assert {:ok, _, _, 2} = NIF.longest_match(table, {:inet4, 10, 69, 1, 2}) + assert {:ok, _, _, 1} = NIF.longest_match(table, {:inet4, 10, 69, 2, 2}) end test "multiple routes" do table = NIF.new() - :ok = NIF.add(table, {:inet4, 8, 8, 8, 0}, 24, 8) - :ok = NIF.add(table, {:inet4, 1, 1, 0, 0}, 16, 1) - :ok = NIF.add(table, {:inet4, 192, 168, 1, 1}, 32, 200) - assert {:ok, _, _, 8} = NIF.lookup(table, {:inet4, 8, 8, 8, 8}) - assert {:ok, _, _, 1} = NIF.lookup(table, {:inet4, 1, 1, 0, 0}) - assert {:ok, _, _, 200} = NIF.lookup(table, {:inet4, 192, 168, 1, 1}) + {:ok, _} = NIF.add(table, {:inet4, 8, 8, 8, 0}, 24, 8) + {:ok, _} = NIF.add(table, {:inet4, 1, 1, 0, 0}, 16, 1) + {:ok, _} = NIF.add(table, {:inet4, 192, 168, 1, 1}, 32, 200) + assert {:ok, _, _, 8} = NIF.longest_match(table, {:inet4, 8, 8, 8, 8}) + assert {:ok, _, _, 1} = NIF.longest_match(table, {:inet4, 1, 1, 0, 0}) + assert {:ok, _, _, 200} = NIF.longest_match(table, {:inet4, 192, 168, 1, 1}) end end -- cgit v1.2.3