Rust hash prefix tree

node.rs

extern crate crypto;
use self::crypto::digest::Digest;
use self::crypto::sha2::Sha256;

use std::mem;
use std::rc::Rc;

fn main() {
  let mut hasher = Sha256::new();
  // write input message
  hasher.input_str("hello world");

  // read hash digest
  // let hex = hasher.result_str();
  let mut h: [u8; 32] = Default::default();
  hasher.result(&mut h);
  // println!("Hello, world!");
  // println!("{}", hex);

  // let a: node::::Node<String> = node_a::Node::Empty();

  let a: node::u16_4::Node<String> = node::u16_4::Node::Empty();

  let b = a.set(45, 0, String::from("hello world"));

  let c = b.set(42, 0, String::from("goodbye"));

  let d = c.set(30, 0, String::from("mello"));

  let res = d.get(30, 0);

  println!("{:#?}", b);
  println!("{:#?}", c);
  println!("{:#?}", d);
  println!("{:#?}", res);

}

fn fast_hash(buf: &[u8]) -> u32 {
  let mut hash: u32 = 0;
  for byte in buf {
    hash = hash * 101 + (*byte as u32)
  }
  return hash;
}

macro_rules! node {
  ($key:ty, $bitsize:expr) => {

    use std::mem;
    use std::rc::Rc;

    type Key = $key; // parameter, can be u8 u16 u32 u64 u164
    const key_chunk_bit_size: u16 = $bitsize as u16; // parameter, expressed in power of two
    const key_chunk_bit_mask: Key = ((1 as Key) << key_chunk_bit_size) - 1; // // 2.pow(key_chunk_bit_size) - 1
    const array_length: usize = (1 as usize) << key_chunk_bit_size; // 2.pow(key_chunk_bit_size)
    type Depth = u16;
    const depth_limit: Depth =
      ((mem::size_of::<Key>() * 8) / (key_chunk_bit_size as usize)) as Depth;
    fn get_key_chunk(key: Key, depth: Depth) -> Key {
      ((key >> (depth * (key_chunk_bit_size as Depth))) & key_chunk_bit_mask)
    }

    #[derive(Clone, Debug)]
    pub enum Node<Value> {
      Branch(Rc<Vec<Node<Value>>>),
      Leaf(Key, Value),
      Empty(),
    }

    impl<Value: Clone> Node<Value> {
      pub fn get(&self, key: Key, depth: Depth) -> Option<Value> {
        match self {
          Node::Empty() => None,
          Node::Leaf(leaf_key, value) => {
            if *leaf_key == key {
              Some(value.clone())
            } else {
              None
            }
          }
          Node::Branch(children) => {
            if depth <= depth_limit {
              children[get_key_chunk(key, depth) as usize].get(key, depth + 1)
            } else {
              None
            }
          }
        }
      }
      pub fn set(&self, key: Key, depth: Depth, value: Value) -> Node<Value> {
        match self {
          Node::Empty() => Node::Leaf(key, value),
          Node::Leaf(leaf_key, leaf_value) => {
            if *leaf_key == key {
              Node::Leaf(key, value)
            } else {
              let mut children: Vec<Node<Value>> = vec![Node::Empty(); array_length];
              children[get_key_chunk(*leaf_key, depth) as usize] =
                Node::Leaf(*leaf_key, leaf_value.clone());
              Node::Branch(Rc::new(children)).set(key, depth, value)
            }

          }
          Node::Branch(children) => {
            // mutate array in-place if no other references it
            let mut copied = if let Ok(ch) = Rc::try_unwrap(children.clone()) {
              ch
            } else {
              children.as_ref().clone()
            };
            let key_chunk = get_key_chunk(key, depth) as usize;
            copied[key_chunk] = copied[key_chunk].set(key, depth + 1, value);
            Node::Branch(Rc::new(copied))
          }
        }
      }
    }
  };
}

mod node {
  // pub mod u8_1 {
  //   node!(u8, 1);
  // }
  // pub mod u8_2 {
  //   node!(u8, 2);
  // }
  // pub mod u8_3 {
  //   node!(u8, 3);
  // }
  // pub mod u8_4 {
  //   node!(u8, 4);
  // }
  // pub mod u8_5 {
  //   node!(u8, 5);
  // }
  // pub mod u8_6 {
  //   node!(u8, 6);
  // }
  // pub mod u8_7 {
  //   node!(u8, 7);
  // }
  // pub mod u8_8 {
  //   node!(u8, 8);
  // }
  // pub mod u16_1 {
  //   node!(u16, 1);
  // }
  // pub mod u16_2 {
  //   node!(u16, 2);
  // }
  // pub mod u16_3 {
  //   node!(u16, 3);
  // }
  pub mod u16_4 {
    node!(u16, 4);
  }
  // pub mod u16_5 {
  //   node!(u16, 5);
  // }
  // pub mod u16_6 {
  //   node!(u16, 6);
  // }
  // pub mod u16_7 {
  //   node!(u16, 7);
  // }
  // pub mod u16_8 {
  //   node!(u16, 8);
  // }
  // pub mod u32_1 {
  //   node!(u32, 1);
  // }
  // pub mod u32_2 {
  //   node!(u32, 2);
  // }
  // pub mod u32_3 {
  //   node!(u32, 3);
  // }
  // pub mod u32_4 {
  //   node!(u32, 4);
  // }
  // pub mod u32_5 {
  //   node!(u32, 5);
  // }
  // pub mod u32_6 {
  //   node!(u32, 6);
  // }
  // pub mod u32_7 {
  //   node!(u32, 7);
  // }
  // pub mod u32_8 {
  //   node!(u32, 8);
  // }
  // pub mod u64_1 {
  //   node!(u64, 1);
  // }
  // pub mod u64_2 {
  //   node!(u64, 2);
  // }
  // pub mod u64_3 {
  //   node!(u64, 3);
  // }
  // pub mod u64_4 {
  //   node!(u64, 4);
  // }
  // pub mod u64_5 {
  //   node!(u64, 5);
  // }
  // pub mod u64_6 {
  //   node!(u64, 6);
  // }
  // pub mod u64_7 {
  //   node!(u64, 7);
  // }
  // pub mod u64_8 {
  //   node!(u64, 8);
  // }
  // pub mod u128_1 {
  //   node!(u128, 1);
  // }
  // pub mod u128_2 {
  //   node!(u128, 2);
  // }
  // pub mod u128_3 {
  //   node!(u128, 3);
  // }
  // pub mod u128_4 {
  //   node!(u128, 4);
  // }
  // pub mod u128_5 {
  //   node!(u128, 5);
  // }
  // pub mod u128_6 {
  //   node!(u128, 6);
  // }
  // pub mod u128_7 {
  //   node!(u128, 7);
  // }
  // pub mod u128_8 {
  //   node!(u128, 8);
  // }
}