it works

8 files changed, 2144 insertions, 75 deletions

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<IpLookupTable<Ipv4Addr, u32>>
+    pub tree: Mutex<TreeBitmap<u32>>
 }
 
 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<TupleV4> 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<ResourceArc<TableResource>> {
-    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<ResourceArc<TableResource>> {
+    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<TableResource>) -> NifResult<usize> {
-    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<TableResource>,
-    ipv4: TupleV4,
+    ip: AddrTuple,
     masklen: u32,
     value: u32
-) -> NifResult<Atom>{
-    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<TableResource>,
-    ipv4: TupleV4,
+    ip: AddrTuple,
     masklen: u32
-) -> NifResult<Atom>{
-    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<TableResource>,
+    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<TableResource>,
-    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<TableResource>
+) -> 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 <LICENSE-MIT or http://opensource.org/licenses/MIT>.
+// 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<T> {
+    mem: *mut T,
+    cap: usize,
+}
+
+impl<T> RawVec<T> {
+    pub fn with_capacity(cap: usize) -> RawVec<T> {
+        let mut vec = Vec::<T>::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::<T>::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<T> Drop for RawVec<T> {
+    fn drop(&mut self) {
+        unsafe {
+            Vec::from_raw_parts(self.mem, 0, self.cap);
+        }
+    }
+}
+
+unsafe impl<T> Sync for RawVec<T> where T: Sync {}
+
+unsafe impl<T> Send for RawVec<T> 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<T> {
+    buf: RawVec<T>,
+    freelist: Vec<u32>,
+    len: u32,
+    spacing: u32,
+}
+
+impl<T: fmt::Debug> fmt::Debug for BucketVec<T> {
+    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<T: Sized> BucketVec<T> {
+    pub fn with_capacity(spacing: u32, capacity: usize) -> BucketVec<T> {
+        BucketVec {
+            buf: RawVec::with_capacity(capacity),
+            freelist: Vec::with_capacity(32),
+            len: 0,
+            spacing,
+        }
+    }
+
+    #[allow(dead_code)]
+    pub fn new(spacing: u32) -> BucketVec<T> {
+        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<T>) -> 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::<T>() * self.buf.cap()) + (self.freelist.capacity() * mem::size_of::<u32>())
+    }
+}
+
+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<T: Sized> {
+    buckets: [BucketVec<T>; 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<T: Sized> Allocator<T> {
+    /// Initialize a new allocator with default capacity.
+    #[allow(dead_code)]
+    pub fn new() -> Allocator<T> {
+        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<T> {
+        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<u32> = BucketVec::new(spacing);
+        let mut b: BucketVec<u32> = 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<u32> = 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<u32> = 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<u32> = 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<u32> = 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::<u32>::new();
+    }
+
+    #[test]
+    fn allocator_alloc1() {
+        let mut alloc = Allocator::<u32>::new();
+        let _ = alloc.alloc(1);
+    }
+
+    #[test]
+    fn allocator_fill() {
+        let mut alloc = Allocator::<u32>::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::<u64>::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::<u32>::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::<u32>::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 <LICENSE-MIT or http://opensource.org/licenses/MIT>.
+// 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<T: Sized> {
+    trienodes: Allocator<Node>,
+    results: Allocator<T>,
+    len: usize,
+    should_drop: bool, // drop contents on drop?
+}
+
+impl<T: Sized> TreeBitmap<T> {
+    /// 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<Node> = 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<T> {
+        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<T> {
+        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<T> {
+        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<T> {
+        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<T> {
+        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<T>,
+    path: Vec<PathElem>,
+    nibbles: Vec<u8>,
+}
+
+pub struct IterMut<'a, T: 'a> {
+    inner: &'a mut TreeBitmap<T>,
+    path: Vec<PathElem>,
+    nibbles: Vec<u8>,
+}
+
+#[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<T: Sized>(
+    trie: &TreeBitmap<T>,
+    path: &mut Vec<PathElem>,
+    nibbles: &mut Vec<u8>,
+) -> Option<(Vec<u8>, 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<u8>, u32, &'a T); //(nibbles, masklen, &T)
+
+    fn next(&mut self) -> Option<Self::Item> {
+        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<u8>, u32, &'a mut T); //(nibbles, masklen, &T)
+
+    fn next(&mut self) -> Option<Self::Item> {
+        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<T> {
+    inner: TreeBitmap<T>,
+    path: Vec<PathElem>,
+    nibbles: Vec<u8>,
+}
+
+impl<'a, T: 'a> Iterator for IntoIter<T> {
+    type Item = (Vec<u8>, u32, T); //(nibbles, masklen, T)
+
+    fn next(&mut self) -> Option<Self::Item> {
+        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<T> IntoIterator for TreeBitmap<T> {
+    type Item = (Vec<u8>, u32, T); //(nibbles, masklen, T)
+    type IntoIter = IntoIter<T>;
+
+    fn into_iter(mut self) -> IntoIter<T> {
+        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<T> Drop for IntoIter<T> {
+    fn drop(&mut self) {
+        for _ in self {}
+    }
+}
+
+impl<T> Drop for TreeBitmap<T> {
+    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<u32> = 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<u32> = 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<Thing> = 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<Thing> = 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 <LICENSE-MIT or http://opensource.org/licenses/MIT>.
+// 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<u32> = 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
--- a/priv/native/libtreebitmap_nif.so
+++ b/priv/native/libtreebitmap_nif.so
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