initial commit

16 files changed, 451 insertions, 0 deletions

diff --git a/.formatter.exs b/.formatter.exs
new file mode 100644
index 0000000..d2cda26
--- /dev/null
+++ b/.formatter.exs
@@ -0,0 +1,4 @@
+# Used by "mix format"
+[
+  inputs: ["{mix,.formatter}.exs", "{config,lib,test}/**/*.{ex,exs}"]
+]
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..0347882
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,26 @@
+# The directory Mix will write compiled artifacts to.
+/_build/
+
+# If you run "mix test --cover", coverage assets end up here.
+/cover/
+
+# The directory Mix downloads your dependencies sources to.
+/deps/
+
+# Where third-party dependencies like ExDoc output generated docs.
+/doc/
+
+# Ignore .fetch files in case you like to edit your project deps locally.
+/.fetch
+
+# If the VM crashes, it generates a dump, let's ignore it too.
+erl_crash.dump
+
+# Also ignore archive artifacts (built via "mix archive.build").
+*.ez
+
+# Ignore package tarball (built via "mix hex.build").
+tree_bitmap-*.tar
+
+# Temporary files, for example, from tests.
+/tmp/
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..c175b02
--- /dev/null
+++ b/README.md
@@ -0,0 +1,21 @@
+# TreeBitmap
+
+**TODO: Add description**
+
+## Installation
+
+If [available in Hex](https://hex.pm/docs/publish), the package can be installed
+by adding `tree_bitmap` to your list of dependencies in `mix.exs`:
+
+```elixir
+def deps do
+  [
+    {:tree_bitmap, "~> 0.1.0"}
+  ]
+end
+```
+
+Documentation can be generated with [ExDoc](https://github.com/elixir-lang/ex_doc)
+and published on [HexDocs](https://hexdocs.pm). Once published, the docs can
+be found at [https://hexdocs.pm/tree_bitmap](https://hexdocs.pm/tree_bitmap).
+
diff --git a/lib/tree_bitmap.ex b/lib/tree_bitmap.ex
new file mode 100644
index 0000000..6d1bc07
--- /dev/null
+++ b/lib/tree_bitmap.ex
@@ -0,0 +1,18 @@
+defmodule TreeBitmap do
+  @moduledoc """
+  Documentation for `TreeBitmap`.
+  """
+
+  @doc """
+  Hello world.
+
+  ## Examples
+
+      iex> TreeBitmap.hello()
+      :world
+
+  """
+  def hello do
+    :world
+  end
+end
diff --git a/lib/tree_bitmap/nif.ex b/lib/tree_bitmap/nif.ex
new file mode 100644
index 0000000..740dbdf
--- /dev/null
+++ b/lib/tree_bitmap/nif.ex
@@ -0,0 +1,10 @@
+defmodule TreeBitmap.NIF do
+  use Rustler, otp_app: :tree_bitmap, crate: "treebitmap_nif"
+
+  def new(), 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 remove(_, _, _), do: :erlang.nif_error(:nif_not_loaded)
+
+end
diff --git a/mix.exs b/mix.exs
new file mode 100644
index 0000000..a6b344d
--- /dev/null
+++ b/mix.exs
@@ -0,0 +1,25 @@
+defmodule TreeBitmap.MixProject do
+  use Mix.Project
+
+  def project do
+    [
+      app: :tree_bitmap,
+      version: "0.1.0",
+      elixir: "~> 1.12-rc",
+      start_permanent: Mix.env() == :prod,
+      deps: deps()
+    ]
+  end
+
+  def application do
+    [
+      extra_applications: [:logger]
+    ]
+  end
+
+  defp deps do
+    [
+      {:rustler, "~> 0.22.2"}
+    ]
+  end
+end
diff --git a/mix.lock b/mix.lock
new file mode 100644
index 0000000..f47b7a1
--- /dev/null
+++ b/mix.lock
@@ -0,0 +1,5 @@
+%{
+  "jason": {:hex, :jason, "1.2.2", "ba43e3f2709fd1aa1dce90aaabfd039d000469c05c56f0b8e31978e03fa39052", [:mix], [{:decimal, "~> 1.0 or ~> 2.0", [hex: :decimal, repo: "hexpm", optional: true]}], "hexpm", "18a228f5f0058ee183f29f9eae0805c6e59d61c3b006760668d8d18ff0d12179"},
+  "rustler": {:hex, :rustler, "0.22.2", "f92d6dba71bef6fe5f0d955649cb071127adc92f32a78890e8fa9939e59a1b41", [:mix], [{:jason, "~> 1.2", [hex: :jason, repo: "hexpm", optional: false]}, {:toml, "~> 0.5.2", [hex: :toml, repo: "hexpm", optional: false]}], "hexpm", "56b129141e86d60a2d670af9a2b55a9071e10933ef593034565af77e84655118"},
+  "toml": {:hex, :toml, "0.5.2", "e471388a8726d1ce51a6b32f864b8228a1eb8edc907a0edf2bb50eab9321b526", [:mix], [], "hexpm", "f1e3dabef71fb510d015fad18c0e05e7c57281001141504c6b69d94e99750a07"},
+}
diff --git a/native/treebitmap_nif/.cargo/config b/native/treebitmap_nif/.cargo/config
new file mode 100644
index 0000000..1cb1d94
--- /dev/null
+++ b/native/treebitmap_nif/.cargo/config
@@ -0,0 +1,12 @@
+[target.x86_64-apple-darwin]
+rustflags = [
+    "-C", "link-arg=-undefined",
+    "-C", "link-arg=dynamic_lookup",
+]
+
+[target.aarch64-apple-darwin]
+rustflags = [
+    "-C", "link-arg=-undefined",
+    "-C", "link-arg=dynamic_lookup",
+]
+
diff --git a/native/treebitmap_nif/.gitignore b/native/treebitmap_nif/.gitignore
new file mode 100644
index 0000000..ea8c4bf
--- /dev/null
+++ b/native/treebitmap_nif/.gitignore
@@ -0,0 +1 @@
+/target
diff --git a/native/treebitmap_nif/Cargo.lock b/native/treebitmap_nif/Cargo.lock
new file mode 100644
index 0000000..c181954
--- /dev/null
+++ b/native/treebitmap_nif/Cargo.lock
@@ -0,0 +1,120 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "heck"
+version = "0.3.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "6d621efb26863f0e9924c6ac577e8275e5e6b77455db64ffa6c65c904e9e132c"
+dependencies = [
+ "unicode-segmentation",
+]
+
+[[package]]
+name = "lazy_static"
+version = "1.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e2abad23fbc42b3700f2f279844dc832adb2b2eb069b2df918f455c4e18cc646"
+
+[[package]]
+name = "proc-macro2"
+version = "1.0.27"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f0d8caf72986c1a598726adc988bb5984792ef84f5ee5aa50209145ee8077038"
+dependencies = [
+ "unicode-xid",
+]
+
+[[package]]
+name = "quote"
+version = "1.0.9"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "c3d0b9745dc2debf507c8422de05d7226cc1f0644216dfdfead988f9b1ab32a7"
+dependencies = [
+ "proc-macro2",
+]
+
+[[package]]
+name = "rustler"
+version = "0.22.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "b787d3b2a80007f41cd4c0c310cdeb3936192768159585f65ecc7e96faf97fc3"
+dependencies = [
+ "lazy_static",
+ "rustler_codegen",
+ "rustler_sys",
+]
+
+[[package]]
+name = "rustler_codegen"
+version = "0.22.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "b5a1f867002b6f0130f47abf215cac4405646db6f5d7b009b21c890980490aa4"
+dependencies = [
+ "heck",
+ "proc-macro2",
+ "quote",
+ "syn",
+]
+
+[[package]]
+name = "rustler_sys"
+version = "2.1.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "1cb382fde4f421c51555919e9920b058c0286f6bf59e53d02eb4d281eae6758b"
+dependencies = [
+ "unreachable",
+]
+
+[[package]]
+name = "syn"
+version = "1.0.73"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f71489ff30030d2ae598524f61326b902466f72a0fb1a8564c001cc63425bcc7"
+dependencies = [
+ "proc-macro2",
+ "quote",
+ "unicode-xid",
+]
+
+[[package]]
+name = "treebitmap"
+version = "0.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "6bf423939ac9ccf4083788879b883a7149176586f9cf8b0fb1fd88b66ad692b5"
+
+[[package]]
+name = "treebitmap_nif"
+version = "0.1.0"
+dependencies = [
+ "rustler",
+ "treebitmap",
+]
+
+[[package]]
+name = "unicode-segmentation"
+version = "1.8.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "8895849a949e7845e06bd6dc1aa51731a103c42707010a5b591c0038fb73385b"
+
+[[package]]
+name = "unicode-xid"
+version = "0.2.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "8ccb82d61f80a663efe1f787a51b16b5a51e3314d6ac365b08639f52387b33f3"
+
+[[package]]
+name = "unreachable"
+version = "1.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "382810877fe448991dfc7f0dd6e3ae5d58088fd0ea5e35189655f84e6814fa56"
+dependencies = [
+ "void",
+]
+
+[[package]]
+name = "void"
+version = "1.0.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "6a02e4885ed3bc0f2de90ea6dd45ebcbb66dacffe03547fadbb0eeae2770887d"
diff --git a/native/treebitmap_nif/Cargo.toml b/native/treebitmap_nif/Cargo.toml
new file mode 100644
index 0000000..0c14233
--- /dev/null
+++ b/native/treebitmap_nif/Cargo.toml
@@ -0,0 +1,14 @@
+[package]
+name = "treebitmap_nif"
+version = "0.1.0"
+authors = []
+edition = "2018"
+
+[lib]
+name = "treebitmap_nif"
+path = "src/lib.rs"
+crate-type = ["cdylib"]
+
+[dependencies]
+rustler = "0.22.0"
+treebitmap = "0.4.0"
diff --git a/native/treebitmap_nif/README.md b/native/treebitmap_nif/README.md
new file mode 100644
index 0000000..67e961c
--- /dev/null
+++ b/native/treebitmap_nif/README.md
@@ -0,0 +1,20 @@
+# NIF for Elixir.TreeBitmap.NIF
+
+## To build the NIF module:
+
+- Your NIF will now build along with your project.
+
+## To load the NIF:
+
+```elixir
+defmodule TreeBitmap.NIF do
+    use Rustler, otp_app: :tree_bitmap, crate: "treebitmap_nif"
+
+    # When your NIF is loaded, it will override this function.
+    def add(_a, _b), do: :erlang.nif_error(:nif_not_loaded)
+end
+```
+
+## Examples
+
+[This](https://github.com/hansihe/NifIo) is a complete example of a NIF written in Rust.
diff --git a/native/treebitmap_nif/src/lib.rs b/native/treebitmap_nif/src/lib.rs
new file mode 100644
index 0000000..7ff0a90
--- /dev/null
+++ b/native/treebitmap_nif/src/lib.rs
@@ -0,0 +1,107 @@
+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};
+
+struct TableResource {
+    pub table: Mutex<IpLookupTable<Ipv4Addr, u32>>
+}
+
+mod atoms {
+    rustler::atoms! {
+        ok,
+        nil,
+        error
+    }
+}
+
+enum AddrTuple {
+    V4(TupleV4),
+    V6(TupleV6)
+}
+
+#[derive(Debug, NifRecord)]
+#[tag = "inet4"]
+struct TupleV4 {
+    pub a: u8,
+    pub b: u8,
+    pub c: u8,
+    pub d: u8
+}
+
+#[derive(Debug, NifRecord)]
+#[tag = "inet6"]
+struct TupleV6 {
+    pub a1: u16,
+    pub a2: u16,
+    pub a3: u16,
+    pub a4: u16,
+    pub a5: u16,
+    pub a6: u16,
+    pub a7: u16,
+    pub a8: u16
+}
+
+#[rustler::nif]
+fn new() -> NifResult<ResourceArc<TableResource>> {
+    let table = IpLookupTable::new();
+    let resource = ResourceArc::new(TableResource {
+      table: Mutex::new(table)
+    });
+    Ok(resource)
+}
+
+#[rustler::nif]
+fn length(table_resource: ResourceArc<TableResource>) -> NifResult<usize> {
+    let table = table_resource.table.lock().unwrap();
+    Ok(table.len())
+}
+
+#[rustler::nif]
+fn add(
+    table_resource: ResourceArc<TableResource>,
+    ipv4: TupleV4,
+    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())
+}
+
+#[rustler::nif]
+fn remove(
+    table_resource: ResourceArc<TableResource>,
+    ipv4: TupleV4,
+    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())
+}
+
+#[rustler::nif]
+fn lookup<'a>(
+    env: rustler::Env<'a>,
+    table_resource: ResourceArc<TableResource>,
+    ipv4: TupleV4
+) -> 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)])
+    } 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);
+
+fn on_load(env: Env, _info: Term) -> bool {
+    rustler::resource!(TableResource, env);
+    true
+}
diff --git a/priv/native/libtreebitmap_nif.so b/priv/native/libtreebitmap_nif.so
new file mode 100755
index 0000000..729cdbe
--- /dev/null
+++ b/priv/native/libtreebitmap_nif.so
diff --git a/test/test_helper.exs b/test/test_helper.exs
new file mode 100644
index 0000000..869559e
--- /dev/null
+++ b/test/test_helper.exs
@@ -0,0 +1 @@
+ExUnit.start()
diff --git a/test/tree_bitmap_test.exs b/test/tree_bitmap_test.exs
new file mode 100644
index 0000000..ff1359f
--- /dev/null
+++ b/test/tree_bitmap_test.exs
@@ -0,0 +1,67 @@
+defmodule TreeBitmapTest do
+  use ExUnit.Case
+  doctest TreeBitmap
+  alias TreeBitmap.NIF
+
+  test "new/0" do
+    table = NIF.new()
+    assert is_reference(table)
+  end
+
+  test "length/1" do
+    table = NIF.new()
+    assert 0 == NIF.length(table)
+  end
+
+  test "add/4 and lookup/2" 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})
+  end
+
+  test "remove/2" 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})
+  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})
+  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})
+  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})
+  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})
+  end
+
+end