use common_bits::*;
use sodiumoxide::crypto;
use std::cmp;
use std::usize;
use types::{DhtId, PublicPmid, RoutingTrait, closer_to_target};
static BUCKET_SIZE: usize = 1;
static GROUP_SIZE: usize = 23;
static QUORUM_SIZE: usize = 19;
pub static PARALLELISM: usize = 4;
static OPTIMAL_SIZE: usize = 64;
#[derive(Clone)]
pub struct KeyFob {
pub id: DhtId,
keys: (crypto::sign::PublicKey, crypto::asymmetricbox::PublicKey),
signature: crypto::sign::Signature,
}
#[derive(Clone, Debug)]
pub struct NodeInfo {
pub id: DhtId, pub fob: PublicPmid,
pub connected: bool,
}
impl NodeInfo {
pub fn new(fob: PublicPmid, connected: bool)
-> NodeInfo {
NodeInfo {
id : fob.get_name(),
fob : fob,
connected : connected
}
}
}
pub struct RoutingTable {
routing_table: Vec<NodeInfo>,
our_id: DhtId,
}
impl Clone for RoutingTable {
fn clone(&self) -> RoutingTable {
RoutingTable {
routing_table: self.routing_table.clone(),
our_id: self.our_id.clone(),
}
}
}
impl RoutingTable {
pub fn new(our_id: DhtId) -> RoutingTable {
RoutingTable { routing_table: Vec::<NodeInfo>::new(), our_id: our_id }
}
pub fn get_bucket_size() -> usize { BUCKET_SIZE }
pub fn get_parallelism() -> usize { PARALLELISM }
pub fn get_optimal_size() -> usize { OPTIMAL_SIZE }
pub fn get_group_size() -> usize { GROUP_SIZE }
pub fn get_quorum_size() -> usize { QUORUM_SIZE }
pub fn add_node(&mut self, their_info: NodeInfo)->(bool, Option<NodeInfo>) {
assert!(their_info.id.is_valid());
if self.our_id == their_info.id {
return (false, None);
}
if self.has_node(&their_info.id) {
return (false, None);
}
if self.routing_table.len() < RoutingTable::get_optimal_size() {
self.push_back_then_sort(their_info);
return (true, None);
}
if closer_to_target(&their_info.id, &self.routing_table[RoutingTable::get_group_size()].id, &self.our_id) {
self.push_back_then_sort(their_info);
let removal_node_index = self.find_candidate_for_removal();
if removal_node_index == usize::MAX {
return (true, None);
} else {
let removal_node = self.routing_table[removal_node_index].clone();
self.routing_table.remove(removal_node_index);
return (true, Some(removal_node));
}
}
let removal_node_index = self.find_candidate_for_removal();
if removal_node_index != usize::MAX &&
self.new_node_is_better_than_existing(&their_info.id, removal_node_index) {
let removal_node = self.routing_table[removal_node_index].clone();
self.routing_table.remove(removal_node_index);
self.push_back_then_sort(their_info);
return (true, Some(removal_node));
}
(false, None)
}
pub fn check_node(&self, their_id: &DhtId)->bool {
if !self.our_id.is_valid() {
panic!("Routing Table id is not valid");
}
if self.our_id == *their_id {
return false;
}
if self.has_node(their_id) {
return false;
}
if self.routing_table.len() < RoutingTable::get_optimal_size() {
return true;
}
let group_size = RoutingTable::get_group_size() - 1;
let thier_id_clone = their_id.clone();
if closer_to_target(&their_id, &self.routing_table[group_size].id, &self.our_id) {
return true;
}
self.new_node_is_better_than_existing(&their_id, self.find_candidate_for_removal())
}
pub fn drop_node(&mut self, node_to_drop: &DhtId) {
if node_to_drop.is_valid() {
let mut index_of_removal = usize::MAX;
for i in 0..self.routing_table.len() {
if self.routing_table[i].id == *node_to_drop {
index_of_removal = i;
break;
}
}
if index_of_removal < self.routing_table.len() {
self.routing_table.remove(index_of_removal);
}
}
}
pub fn target_nodes(&self, target: DhtId)->Vec<NodeInfo> {
let mut our_close_group = Vec::new();
let mut closest_to_target = Vec::new();
let mut result: Vec<NodeInfo> = Vec::new();
let mut iterations = 0usize;
let parallelism = if RoutingTable::get_parallelism() < self.routing_table.len() {
RoutingTable::get_parallelism()
} else {
self.routing_table.len()
};
for iter in self.routing_table.iter() {
if iterations < RoutingTable::get_group_size() {
our_close_group.push(iter.clone());
}
closest_to_target.push(iter.clone());
iterations += 1;
}
if closest_to_target.is_empty() {
return result;
}
closest_to_target.sort_by(
|a, b| if closer_to_target(&a.id, &b.id, &target) {
cmp::Ordering::Less
} else {
cmp::Ordering::Greater
});
if RoutingTable::is_any_of(&our_close_group, &closest_to_target) {
for iter in our_close_group.iter() {
result.push(iter.clone());
}
} else {
for iter in closest_to_target.iter().take(parallelism) {
result.push(iter.clone());
}
}
result
}
pub fn our_close_group(&self) -> Vec<NodeInfo> {
let group_size = RoutingTable::get_group_size();
let size = cmp::min(group_size, self.routing_table.len());
let mut result = Vec::new();
for i in 0..size {
result.push(self.routing_table[i].clone());
}
result
}
pub fn get_public_key(&self, their_id: DhtId)->Option<crypto::asymmetricbox::PublicKey> {
if !their_id.is_valid() {
panic!("Id is not valid");
}
if !self.is_nodes_sorted() {
panic!("Nodes are not sorted");
}
let found_node_option = self.routing_table.iter().find(
|&node_info| {
node_info.id == their_id
});
match found_node_option {
Some(node) => { Some(node.fob.public_key.get_crypto_public_key()) }
None => {None}
}
}
pub fn size(&self)->usize {
self.routing_table.len()
}
fn find_candidate_for_removal(&self) -> usize {
assert!(self.routing_table.len() >= RoutingTable::get_optimal_size());
let mut number_in_bucket = 0usize;
let mut current_bucket = 0usize;
let mut counter = self.routing_table.len() - 1;
let mut furthest_in_this_bucket = counter;
let finish = RoutingTable::get_group_size();
while counter >= finish {
let bucket_index = self.bucket_index(&self.routing_table[counter].id);
if bucket_index != current_bucket {
current_bucket = bucket_index;
number_in_bucket = 0;
furthest_in_this_bucket = counter;
}
number_in_bucket += 1;
if number_in_bucket > RoutingTable::get_bucket_size() {
break;
}
counter -= 1;
}
if counter < finish {
usize::MAX
} else {
furthest_in_this_bucket
}
}
fn bucket_index(&self, id: &DhtId) -> usize {
let mut index_of_mismatch = 0usize;
while index_of_mismatch < self.our_id.0.len() {
if id.0[index_of_mismatch] != self.our_id.0[index_of_mismatch] {
break;
}
index_of_mismatch += 1;
}
if index_of_mismatch == self.our_id.0.len() {
return 8 * self.our_id.0.len();
}
let common_bits = K_COMMON_BITS[self.our_id.0[index_of_mismatch] as usize]
[id.0[index_of_mismatch] as usize];
8 * index_of_mismatch + common_bits as usize
}
fn has_node(&self, node_id: &DhtId) -> bool {
for node_info in &self.routing_table {
if node_info.id == *node_id {
return true;
}
}
false
}
fn push_back_then_sort(&mut self, node_info: NodeInfo) {
self.routing_table.push(node_info);
let our_id = &self.our_id;
self.routing_table.sort_by(
|a, b| if closer_to_target(&a.id, &b.id, our_id) {
cmp::Ordering::Less
} else {
cmp::Ordering::Greater
});
}
fn is_nodes_sorted(&self) -> bool {
for i in 1..self.routing_table.len() {
if closer_to_target(&self.routing_table[i].id, &self.routing_table[i - 1].id, &self.our_id) {
return false;
}
}
true
}
fn new_node_is_better_than_existing (&self, new_node: &DhtId,
removal_node_index: usize) -> bool {
if removal_node_index >= self.routing_table.len() {
return false;
}
let removal_node = &self.routing_table[removal_node_index];
self.bucket_index(new_node) > self.bucket_index(&removal_node.id)
}
fn is_any_of(vec_close_group: &Vec<NodeInfo>, vec_closest_to_target: &Vec<NodeInfo>) -> bool {
for iter in vec_close_group.iter() {
if iter.id == vec_closest_to_target[0].id {
return true;
}
}
false
}
}
#[cfg(test)]
mod test {
use super::*;
use sodiumoxide::crypto;
use std::cmp;
use std::collections::BitVec;
use std::net::*;
use std::fmt;
use types::{DhtId, PublicPmid, RoutingTrait, closer_to_target};
use types;
use rand;
enum ContactType {
Far,
Mid,
Close,
}
fn get_contact(farthest_from_tables_own_id: &DhtId, index: usize,
contact_type: ContactType) -> DhtId {
let mut binary_id = BitVec::from_bytes(&farthest_from_tables_own_id.0);
if index > 0 {
for i in 0..index {
let bit = binary_id.get(i).unwrap();
binary_id.set(i, !bit);
}
}
match contact_type {
ContactType::Mid => {
let bit_num = binary_id.len() - 1;
let bit = binary_id.get(bit_num).unwrap();
binary_id.set(bit_num, !bit);
},
ContactType::Close => {
let bit_num = binary_id.len() - 2;
let bit = binary_id.get(bit_num).unwrap();
binary_id.set(bit_num, !bit);
},
ContactType::Far => {},
};
DhtId(binary_id.to_bytes())
}
struct Bucket {
index: usize,
far_contact: DhtId,
mid_contact: DhtId,
close_contact: DhtId,
}
impl Bucket {
fn new(farthest_from_tables_own_id: DhtId, index: usize) -> Bucket {
Bucket {
index: index,
far_contact: get_contact(&farthest_from_tables_own_id, index, ContactType::Far),
mid_contact: get_contact(&farthest_from_tables_own_id, index, ContactType::Mid),
close_contact: get_contact(&farthest_from_tables_own_id, index, ContactType::Close),
}
}
}
struct RoutingTableUnitTest {
our_id: DhtId,
table: RoutingTable,
buckets: Vec<Bucket>,
node_info: NodeInfo,
initial_count: usize,
added_ids: Vec<DhtId>,
}
impl RoutingTableUnitTest {
fn new() -> RoutingTableUnitTest {
let node_info = create_random_node_info();
let table = RoutingTableUnitTest {
our_id: node_info.id.clone(),
table: RoutingTable {
our_id: node_info.id.clone(), routing_table: Vec::new(),
},
buckets: initialise_buckets(&node_info.id),
node_info: node_info,
initial_count: (rand::random::<usize>() % (RoutingTable::get_group_size() - 1)) + 1,
added_ids: Vec::new(),
};
for i in 0..99 {
assert!(closer_to_target(&table.buckets[i].mid_contact,
&table.buckets[i].far_contact, &table.our_id));
assert!(closer_to_target(&table.buckets[i].close_contact,
&table.buckets[i].mid_contact, &table.our_id));
assert!(closer_to_target(&table.buckets[i + 1].far_contact,
&table.buckets[i].close_contact, &table.our_id));
}
assert!(closer_to_target(&table.buckets[99].mid_contact,
&table.buckets[99].far_contact, &table.our_id));
assert!(closer_to_target(&table.buckets[99].close_contact,
&table.buckets[99].mid_contact, &table.our_id));
table
}
fn partially_fill_table(&mut self) {
for i in 0..self.initial_count {
self.node_info.id = self.buckets[i].mid_contact.clone();
self.added_ids.push(self.node_info.id.clone());
assert!(self.table.add_node(self.node_info.clone()).0);
}
assert_eq!(self.initial_count, self.table.size());
}
fn complete_filling_table(&mut self) {
for i in self.initial_count..RoutingTable::get_optimal_size() {
self.node_info.id = self.buckets[i].mid_contact.clone();
self.added_ids.push(self.node_info.id.clone());
assert!(self.table.add_node(self.node_info.clone()).0);
}
assert_eq!(RoutingTable::get_optimal_size(), self.table.size());
}
}
fn to_hex(char: u8) -> String {
let hex = fmt::format(format_args!("{:x}", char));
if hex.len() == 1 {
let mut s = String::from_str("0");
s.push_str(hex.as_str());
s
} else {
hex
}
}
fn debug_id(id: &DhtId) -> String {
let id_as_bytes = id.0.clone();
fmt::format(format_args!("{}{}{}..{}{}{}",
to_hex(id_as_bytes[0]),
to_hex(id_as_bytes[1]),
to_hex(id_as_bytes[2]),
to_hex(id_as_bytes[61]),
to_hex(id_as_bytes[62]),
to_hex(id_as_bytes[63])))
}
fn initialise_buckets(our_id: &DhtId) -> Vec<Bucket> {
let arr = [255u8; 64];
let mut arr_res = [0u8; 64];
for i in 0..64 {
arr_res[i] = arr[i] ^ our_id.0[i];
}
let farthest_from_tables_own_id = DhtId::new(&arr_res);
let mut buckets = Vec::new();
for i in 0..100 {
buckets.push(Bucket::new(farthest_from_tables_own_id.clone(), i));
}
buckets
}
fn create_random_socket_address() -> SocketAddr {
SocketAddr::V4(SocketAddrV4::new(
Ipv4Addr::new(rand::random::<u8>(),
rand::random::<u8>(),
rand::random::<u8>(),
rand::random::<u8>()),
rand::random::<u16>()))
}
fn create_random_arr() -> [u8; 64] {
let mut arr = [0u8; 64];
for i in 0..arr.len() {
arr[i] = rand::random::<u8>();
}
arr
}
fn create_random_node_info() -> NodeInfo {
let public_pmid = types::PublicPmid::new(&types::Pmid::new());
NodeInfo {
id : public_pmid.get_name(),
fob: public_pmid,
connected: false,
}
}
fn create_random_routing_tables(num_of_tables: usize) -> Vec<RoutingTable> {
let mut vector: Vec<RoutingTable> = Vec::with_capacity(num_of_tables);
for i in 0..num_of_tables {
vector.push(RoutingTable { routing_table: Vec::new(), our_id: DhtId::generate_random() });
}
vector
}
#[test]
fn add_check_nodes_test() {
let num_of_tables = 50usize;
let mut tables = create_random_routing_tables(num_of_tables);
for i in 0..num_of_tables {
for j in 0..num_of_tables {
let mut node_info = create_random_node_info();
node_info.id = tables[j].our_id.clone();
if tables[i].check_node(&node_info.id) {
let removed_node = tables[i].add_node(node_info);
assert!(removed_node.0);
}
}
}
}
#[test]
fn routing_table_test() {
let mut table = RoutingTable {
routing_table: Vec::new(),
our_id: DhtId::generate_random()
};
for i in 0..RoutingTable::get_group_size() {
let id = DhtId::generate_random();
assert!(table.check_node(&id));
}
assert_eq!(table.size(), 0);
for i in 0..RoutingTable::get_group_size() {
let node_info = create_random_node_info();
assert!(table.add_node(node_info).0);
}
assert_eq!(table.size(), RoutingTable::get_group_size());
}
#[test]
fn add_check_close_group_test() {
let num_of_tables = 50usize;
let mut tables = create_random_routing_tables(num_of_tables);
let mut addresses: Vec<DhtId> = Vec::with_capacity(num_of_tables);
for i in 0..num_of_tables {
addresses.push(tables[i].our_id.clone());
for j in 0..num_of_tables {
let mut node_info = create_random_node_info();
node_info.id = tables[j].our_id.clone();
tables[i].add_node(node_info);
}
}
for it in tables.iter() {
let id = it.our_id.clone();
addresses.sort_by(
|a, b| if closer_to_target(&a, &b, &id) {
cmp::Ordering::Less
} else {
cmp::Ordering::Greater
});
let mut groups = it.our_close_group();
assert_eq!(groups.len(), RoutingTable::get_group_size());
if groups.len() > 1 {
let mut new_end = 1usize;
for i in 1..groups.len() {
if groups[new_end - 1].id != groups[i].id {
if new_end != i {
groups[new_end] = groups[i].clone();
}
new_end += 1;
}
}
assert_eq!(new_end, groups.len());
}
assert_eq!(groups.len(), RoutingTable::get_group_size());
for i in 0..RoutingTable::get_group_size() {
assert!(groups[i].id == addresses[i + 1]);
}
}
}
#[test]
fn add_node_test() {
let mut test = RoutingTableUnitTest::new();
assert_eq!(test.table.size(), 0);
test.node_info.id = test.table.our_id.clone();
let mut result_of_add = test.table.add_node(test.node_info.clone());
assert!(!result_of_add.0);
match result_of_add.1 {
Some(_) => panic!("Unexpected"),
None => {},
};
assert_eq!(test.table.size(), 0);
test.node_info.id = test.buckets[0].far_contact.clone();
result_of_add = test.table.add_node(test.node_info.clone());
assert!(result_of_add.0);
match result_of_add.1 {
Some(_) => panic!("Unexpected"),
None => {},
};
assert_eq!(test.table.size(), 1);
result_of_add = test.table.add_node(test.node_info.clone());
assert!(!result_of_add.0);
match result_of_add.1 {
Some(_) => panic!("Unexpected"),
None => {},
};
assert_eq!(test.table.size(), 1);
test.node_info.id = test.buckets[0].mid_contact.clone();
result_of_add = test.table.add_node(test.node_info.clone());
assert!(result_of_add.0);
match result_of_add.1 {
Some(_) => panic!("Unexpected"),
None => {},
};
assert_eq!(2, test.table.size());
result_of_add = test.table.add_node(test.node_info.clone());
assert!(!result_of_add.0);
match result_of_add.1 {
Some(_) => panic!("Unexpected"),
None => {},
};
assert_eq!(2, test.table.size());
test.node_info.id = test.buckets[0].close_contact.clone();
result_of_add = test.table.add_node(test.node_info.clone());
assert!(result_of_add.0);
match result_of_add.1 {
Some(_) => panic!("Unexpected"),
None => {},
};
assert_eq!(3, test.table.size());
result_of_add = test.table.add_node(test.node_info.clone());
assert!(!result_of_add.0);
match result_of_add.1 {
Some(_) => panic!("Unexpected"),
None => {},
};
assert_eq!(3, test.table.size());
test.node_info.id = test.buckets[1].far_contact.clone();
result_of_add = test.table.add_node(test.node_info.clone());
assert!(result_of_add.0);
match result_of_add.1 {
Some(_) => panic!("Unexpected"),
None => {},
};
assert_eq!(4, test.table.size());
result_of_add = test.table.add_node(test.node_info.clone());
assert!(!result_of_add.0);
match result_of_add.1 {
Some(_) => panic!("Unexpected"),
None => {},
};
assert_eq!(4, test.table.size());
test.node_info.id = test.buckets[1].mid_contact.clone();
result_of_add = test.table.add_node(test.node_info.clone());
assert!(result_of_add.0);
match result_of_add.1 {
Some(_) => panic!("Unexpected"),
None => {},
};
assert_eq!(5, test.table.size());
result_of_add = test.table.add_node(test.node_info.clone());
assert!(!result_of_add.0);
match result_of_add.1 {
Some(_) => panic!("Unexpected"),
None => {},
};
assert_eq!(5, test.table.size());
test.node_info.id = test.buckets[1].close_contact.clone();
result_of_add = test.table.add_node(test.node_info.clone());
assert!(result_of_add.0);
match result_of_add.1 {
Some(_) => panic!("Unexpected"),
None => {},
};
assert_eq!(6, test.table.size());
result_of_add = test.table.add_node(test.node_info.clone());
assert!(!result_of_add.0);
match result_of_add.1 {
Some(_) => panic!("Unexpected"),
None => {},
};
assert_eq!(6, test.table.size());
for i in 2..(RoutingTable::get_optimal_size() - 4) {
test.node_info.id = test.buckets[i].mid_contact.clone();
result_of_add = test.table.add_node(test.node_info.clone());
assert!(result_of_add.0);
match result_of_add.1 {
Some(_) => panic!("Unexpected"),
None => {},
};
assert_eq!(i + 5, test.table.size());
result_of_add = test.table.add_node(test.node_info.clone());
assert!(!result_of_add.0);
match result_of_add.1 {
Some(_) => panic!("Unexpected"),
None => {},
};
assert_eq!(i + 5, test.table.size());
}
let mut dropped: Vec<DhtId> = Vec::new();
for i in (RoutingTable::get_optimal_size() - 4)..RoutingTable::get_optimal_size() {
test.node_info.id = test.buckets[i].mid_contact.clone();
result_of_add = test.table.add_node(test.node_info.clone());
assert!(result_of_add.0);
match result_of_add.1 {
Some(dropped_info) => { dropped.push(dropped_info.id) },
None => panic!("Unexpected"),
};
assert_eq!(RoutingTable::get_optimal_size(), test.table.size());
result_of_add = test.table.add_node(test.node_info.clone());
assert!(!result_of_add.0);
match result_of_add.1 {
Some(_) => panic!("Unexpected"),
None => {},
};
assert_eq!(RoutingTable::get_optimal_size(), test.table.size());
}
assert!(test.buckets[0].far_contact == dropped[0]);
assert!(test.buckets[0].mid_contact == dropped[1]);
assert!(test.buckets[1].far_contact == dropped[2]);
assert!(test.buckets[1].mid_contact == dropped[3]);
for far_contact in dropped {
test.node_info.id = far_contact.clone();
result_of_add = test.table.add_node(test.node_info.clone());
assert!(!result_of_add.0);
match result_of_add.1 {
Some(_) => panic!("Unexpected"),
None => {},
};
assert_eq!(RoutingTable::get_optimal_size(), test.table.size());
}
test.node_info.id = test.buckets[RoutingTable::get_optimal_size()].mid_contact.clone();
result_of_add = test.table.add_node(test.node_info.clone());
assert!(result_of_add.0);
match result_of_add.1 {
Some(_) => panic!("Unexpected"),
None => {},
};
assert_eq!(RoutingTable::get_optimal_size() + 1, test.table.size());
result_of_add = test.table.add_node(test.node_info.clone());
assert!(!result_of_add.0);
match result_of_add.1 {
Some(_) => panic!("Unexpected"),
None => {},
};
assert_eq!(RoutingTable::get_optimal_size() + 1, test.table.size());
}
#[test]
fn drop_node_test() {
let mut test = RoutingTableUnitTest::new();
assert_eq!(test.table.size(), 0);
test.partially_fill_table();
test.complete_filling_table();
test.table.drop_node(&DhtId::new(&[0u8;64]));
assert_eq!(RoutingTable::get_optimal_size(), test.table.size());
let drop_id = test.table.our_id.clone();
test.table.drop_node(&drop_id);
assert_eq!(RoutingTable::get_optimal_size(), test.table.size());
test.table.drop_node(&test.buckets[0].far_contact);
assert_eq!(RoutingTable::get_optimal_size(), test.table.size());
let mut size = test.table.size();
for id in test.added_ids {
size -= 1;
test.table.drop_node(&id);
assert_eq!(size, test.table.size());
}
}
#[test]
fn check_node_test() {
let mut routing_table_utest = RoutingTableUnitTest::new();
assert_eq!(routing_table_utest.table.check_node(&routing_table_utest.table.our_id), false);
assert!(routing_table_utest.table.check_node(&routing_table_utest.buckets[0].far_contact));
let mut new_node_0 = create_random_node_info();
new_node_0.id = routing_table_utest.buckets[0].far_contact.clone();
assert!(routing_table_utest.table.add_node(new_node_0).0);
assert_eq!(
routing_table_utest.table.check_node(&routing_table_utest.buckets[0].far_contact.clone()),
false);
let mut new_node_1 = create_random_node_info();
new_node_1.id = routing_table_utest.buckets[0].mid_contact.clone();
assert!(routing_table_utest.table.check_node(&new_node_1.id));
assert!(routing_table_utest.table.add_node(new_node_1).0);
assert_eq!(routing_table_utest.table.check_node(
&routing_table_utest.buckets[0].mid_contact.clone()), false);
let mut new_node_2 = create_random_node_info();
new_node_2.id = routing_table_utest.buckets[0].close_contact.clone();
assert!(routing_table_utest.table.check_node(&new_node_2.id));
assert!(routing_table_utest.table.add_node(new_node_2).0);
assert_eq!(routing_table_utest.table.check_node(
&routing_table_utest.buckets[0].close_contact.clone()), false);
let mut new_node_3 = create_random_node_info();
new_node_3.id = routing_table_utest.buckets[1].far_contact.clone();
assert!(routing_table_utest.table.check_node(&new_node_3.id));
assert!(routing_table_utest.table.add_node(new_node_3).0);
assert_eq!(routing_table_utest.table.check_node(
&routing_table_utest.buckets[1].far_contact.clone()), false);
let mut new_node_4 = create_random_node_info();
new_node_4.id = routing_table_utest.buckets[1].mid_contact.clone();
assert!(routing_table_utest.table.check_node(&new_node_4.id));
assert!(routing_table_utest.table.add_node(new_node_4).0);
assert_eq!(routing_table_utest.table.check_node(
&routing_table_utest.buckets[1].mid_contact.clone()), false);
let mut new_node_5 = create_random_node_info();
new_node_5.id = routing_table_utest.buckets[1].close_contact.clone();
assert!(routing_table_utest.table.check_node(&new_node_5.id));
assert!(routing_table_utest.table.add_node(new_node_5).0);
assert_eq!(routing_table_utest.table.check_node(
&routing_table_utest.buckets[1].close_contact.clone()), false);
for i in 2..(RoutingTable::get_optimal_size() - 4) {
let mut new_node = create_random_node_info();
new_node.id = routing_table_utest.buckets[i].mid_contact.clone();
assert!(routing_table_utest.table.check_node(&new_node.id));
assert!(routing_table_utest.table.add_node(new_node).0);
assert_eq!(routing_table_utest.table.check_node(
&routing_table_utest.buckets[i].mid_contact.clone()), false);
}
assert_eq!(RoutingTable::get_optimal_size(), routing_table_utest.table.routing_table.len());
for i in (RoutingTable::get_optimal_size() - 4)..RoutingTable::get_optimal_size() {
let mut new_node = create_random_node_info();
new_node.id = routing_table_utest.buckets[i].mid_contact.clone();
assert!(routing_table_utest.table.check_node(&new_node.id));
assert!(routing_table_utest.table.add_node(new_node).0);
assert_eq!(routing_table_utest.table.check_node(
&routing_table_utest.buckets[i].mid_contact.clone()), false);
assert_eq!(RoutingTable::get_optimal_size(),
routing_table_utest.table.routing_table.len());
}
assert_eq!(routing_table_utest.table.check_node(
&routing_table_utest.buckets[0].far_contact.clone()), false);
assert_eq!(routing_table_utest.table.check_node(
&routing_table_utest.buckets[0].mid_contact.clone()), false);
assert_eq!(routing_table_utest.table.check_node(
&routing_table_utest.buckets[1].far_contact.clone()), false);
assert_eq!(routing_table_utest.table.check_node(
&routing_table_utest.buckets[1].mid_contact.clone()), false);
assert!(routing_table_utest.table.check_node(
&routing_table_utest.buckets[RoutingTable::get_optimal_size()].mid_contact.clone()));
}
#[test]
fn churn_test() {
let network_size = 200usize;
let nodes_to_remove = 20usize;
let mut tables = create_random_routing_tables(network_size);
let mut addresses: Vec<DhtId> = Vec::with_capacity(network_size);
for i in 0..tables.len() {
addresses.push(tables[i].our_id.clone());
for j in 0..tables.len() {
let mut node_info = create_random_node_info();
node_info.id = tables[j].our_id.clone();
tables[i].add_node(node_info);
}
}
let mut drop_vec: Vec<DhtId> = Vec::with_capacity(nodes_to_remove);
for i in 0..nodes_to_remove {
drop_vec.push(addresses[i].clone());
}
tables = tables.split_off(nodes_to_remove);
for i in 0..tables.len() {
for j in 0..drop_vec.len() {
tables[i].drop_node(&drop_vec[j]);
}
}
addresses = addresses.split_off(nodes_to_remove);
for i in 0..tables.len() {
let size = if RoutingTable::get_group_size() < tables[i].size() {
RoutingTable::get_group_size()
} else {
tables[i].size()
};
let id = tables[i].our_id.clone();
addresses.sort_by(
|a, b| if closer_to_target(&a, &b, &id) {
cmp::Ordering::Less
} else {
cmp::Ordering::Greater
});
let groups = tables[i].our_close_group();
assert_eq!(groups.len(), size);
}
}
#[test]
fn target_nodes_group_test() {
let network_size = 100usize;
let mut tables = create_random_routing_tables(network_size);
let mut addresses: Vec<DhtId> = Vec::with_capacity(network_size);
for i in 0..tables.len() {
addresses.push(tables[i].our_id.clone());
for j in 0..tables.len() {
let mut node_info = create_random_node_info();
node_info.id = tables[j].our_id.clone();
tables[i].add_node(node_info);
}
}
for i in 0..tables.len() {
addresses.sort_by(
|a, b| if closer_to_target(&a, &b, &tables[i].our_id) {
cmp::Ordering::Less
} else {
cmp::Ordering::Greater
});
for j in 1..(RoutingTable::get_group_size() - RoutingTable::get_quorum_size()) {
let target_close_group = tables[i].target_nodes(addresses[j].clone());
assert_eq!(RoutingTable::get_group_size(), target_close_group.len());
for k in 0..target_close_group.len() {
assert!(target_close_group[k].id == addresses[k + 1]);
}
}
}
}
#[test]
fn our_close_group_test() {
let mut table_unit_test = RoutingTableUnitTest::new();
assert!(table_unit_test.table.our_close_group().is_empty());
table_unit_test.partially_fill_table();
assert_eq!(table_unit_test.initial_count, table_unit_test.table.our_close_group().len());
for i in 0..table_unit_test.initial_count {
assert!(table_unit_test.table.our_close_group().iter().filter(
|&node| { node.id == table_unit_test.buckets[i].mid_contact }).count() > 0);
}
table_unit_test.complete_filling_table();
assert_eq!(RoutingTable::get_group_size(), table_unit_test.table.our_close_group().len());
table_unit_test.table.our_close_group().sort_by(
|a, b| if closer_to_target(&a.id, &b.id, &table_unit_test.our_id) {
cmp::Ordering::Less
} else {
cmp::Ordering::Greater
});
for close_node in table_unit_test.table.our_close_group().iter() {
assert!(table_unit_test.added_ids.iter().filter(
|&node| { node == &close_node.id }).count() > 0);
}
}
#[test]
fn target_nodes_test() {
let mut routing_table_utest = RoutingTableUnitTest::new();
let mut target_nodes_ = routing_table_utest.table.target_nodes(DhtId::generate_random());
assert_eq!(target_nodes_.len(), 0);
routing_table_utest.partially_fill_table();
target_nodes_ = routing_table_utest.table.target_nodes(DhtId::generate_random());
assert_eq!(routing_table_utest.initial_count, target_nodes_.len());
for i in 0..routing_table_utest.initial_count {
let mut assert_checker = 0;
for j in 0..target_nodes_.len() {
if target_nodes_[j].id == routing_table_utest.buckets[i].mid_contact {
assert_checker = 1;
break;
}
}
assert!(assert_checker == 1);
}
routing_table_utest.complete_filling_table();
target_nodes_ =
routing_table_utest.table.target_nodes(routing_table_utest.table.our_id.clone());
assert_eq!(RoutingTable::get_group_size(), target_nodes_.len());
for i in ((RoutingTable::get_optimal_size() - RoutingTable::get_group_size())..
RoutingTable::get_optimal_size() - 1).rev() {
let mut assert_checker = 0;
for j in 0..target_nodes_.len() {
if target_nodes_[j].id == routing_table_utest.buckets[i].mid_contact {
assert_checker = 1;
break;
}
}
assert!(assert_checker == 1);
}
let mut target: DhtId;
for count in 0..2 {
for i in 0..(RoutingTable::get_optimal_size() - RoutingTable::get_group_size()) {
target = if count == 0 {
routing_table_utest.buckets[i].far_contact.clone()
} else {
routing_table_utest.buckets[i].mid_contact.clone()
};
target_nodes_ = routing_table_utest.table.target_nodes(target);
assert_eq!(RoutingTable::get_parallelism(), target_nodes_.len());
routing_table_utest.table.our_close_group().sort_by(
|a, b| if closer_to_target(&a.id, &b.id, &routing_table_utest.our_id) {
cmp::Ordering::Less
} else {
cmp::Ordering::Greater
});
for i in 0..target_nodes_.len() {
let mut assert_checker = 0;
for j in 0..routing_table_utest.added_ids.len() {
if target_nodes_[i].id == routing_table_utest.added_ids[j] {
assert_checker = 1;
continue;
}
}
assert!(assert_checker == 1);
}
}
}
for count in 0..2 {
for i in (RoutingTable::get_optimal_size() - RoutingTable::get_group_size())..
RoutingTable::get_optimal_size() {
target = if count == 0 {
routing_table_utest.buckets[i].far_contact.clone()
} else {
routing_table_utest.buckets[i].mid_contact.clone()
};
target_nodes_ = routing_table_utest.table.target_nodes(target);
assert_eq!(RoutingTable::get_group_size(), target_nodes_.len());
routing_table_utest.table.our_close_group().sort_by(
|a, b| if closer_to_target(&a.id, &b.id, &routing_table_utest.our_id) {
cmp::Ordering::Less
} else {
cmp::Ordering::Greater
});
for i in 0..target_nodes_.len() {
let mut assert_checker = 0;
for j in 0..routing_table_utest.added_ids.len() {
if target_nodes_[i].id == routing_table_utest.added_ids[j] {
assert_checker = 1;
continue;
}
}
assert!(assert_checker == 1);
}
}
}
}
#[test]
fn trivial_functions_test() {
let mut table_unit_test = RoutingTableUnitTest::new();
match table_unit_test.table.get_public_key(table_unit_test.buckets[0].mid_contact.clone()) {
Some(crypto::asymmetricbox::PublicKey(p)) => panic!("PublicKey Exits"),
None => {},
}
assert!(table_unit_test.our_id == table_unit_test.table.our_id);
assert_eq!(0, table_unit_test.table.routing_table.len());
table_unit_test.partially_fill_table();
let test_node = create_random_node_info();
table_unit_test.node_info = test_node.clone();
assert!(table_unit_test.table.add_node(table_unit_test.node_info.clone()).0);
match table_unit_test.table.get_public_key(table_unit_test.node_info.id.clone()) {
Some(crypto::asymmetricbox::PublicKey(p)) => {},
None => panic!("PublicKey None"),
}
match table_unit_test.table.get_public_key(
table_unit_test.buckets[table_unit_test.buckets.len() - 1].far_contact.clone()) {
Some(crypto::asymmetricbox::PublicKey(p)) => panic!("PublicKey Exits"),
None => {}
}
assert!(table_unit_test.our_id == table_unit_test.table.our_id);
assert_eq!(table_unit_test.initial_count + 1, table_unit_test.table.routing_table.len());
table_unit_test.table.drop_node(&test_node.id.clone());
table_unit_test.complete_filling_table();
table_unit_test.table.drop_node(&table_unit_test.buckets[0].mid_contact.clone());
table_unit_test.node_info = test_node.clone();
assert!(table_unit_test.table.add_node(table_unit_test.node_info.clone()).0);
match table_unit_test.table.get_public_key(table_unit_test.node_info.id.clone()) {
Some(crypto::asymmetricbox::PublicKey(p)) => {},
None => panic!("PublicKey None"),
}
match table_unit_test.table.get_public_key(
table_unit_test.buckets[table_unit_test.buckets.len() - 1].far_contact.clone()) {
Some(crypto::asymmetricbox::PublicKey(p)) => panic!("PublicKey Exits"),
None => {}
}
assert!(table_unit_test.our_id == table_unit_test.table.our_id);
assert_eq!(RoutingTable::get_optimal_size(), table_unit_test.table.routing_table.len());
}
}