class Ciri::P2P::Kad::RoutingTable

Attributes

buckets[R]
local_node[R]

Public Class Methods

new(local_node:) click to toggle source
# File lib/ciri/p2p/kad.rb, line 163
def initialize(local_node:)
  @local_node = local_node
  @buckets = [KBucket.new(start_id: 0, end_id: K_MAX_NODE_ID)]
end

Public Instance Methods

add_node(node) click to toggle source
# File lib/ciri/p2p/kad.rb, line 203
def add_node(node)
  raise ArgumentError.new("can't add local_node") if @local_node == node
  bucket = find_bucket_for_node(node)
  eviction_candidate = bucket.add(node)
  # bucket is full, otherwise will return nil
  if eviction_candidate
    depth = compute_shared_prefix_bits(bucket.nodes)
    if bucket.cover?(@local_node) || (depth % K_BITS != 0 && depth != K_ID_SIZE)
      split_bucket(@buckets.index(bucket))
      return add_node(node)
    end
    return eviction_candidate
  end
  nil
end
buckets_by_distance_to(id) click to toggle source
# File lib/ciri/p2p/kad.rb, line 219
def buckets_by_distance_to(id)
  @buckets.sort_by do |bucket|
    bucket.distance_to(id)
  end
end
delete_node(node) click to toggle source
# File lib/ciri/p2p/kad.rb, line 195
def delete_node(node)
  find_bucket_for_node(node).delete(node)
end
each_node(&blk) click to toggle source
# File lib/ciri/p2p/kad.rb, line 233
def each_node(&blk)
  @buckets.each do |bucket|
    bucket.nodes do |node|
      blk.call(node)
    end
  end
end
find_bucket_for_node(node) click to toggle source

do binary search to find node

# File lib/ciri/p2p/kad.rb, line 260
def find_bucket_for_node(node)
  @buckets.bsearch do |bucket|
    bucket.end_id >= node.id
  end
end
find_neighbours(id, k: K_BUCKET_SIZE) click to toggle source
# File lib/ciri/p2p/kad.rb, line 241
def find_neighbours(id, k: K_BUCKET_SIZE)
  # convert id to integer
  unless id.is_a?(Integer)
    id = Node.new(id).id
  end
  nodes = []
  buckets_by_distance_to(id).each do |bucket|
    bucket.nodes_by_distance_to(id).each do |node|
      if node.id != id
        nodes << node
        # find 2 * k nodes to avoid edge cases
        break if nodes.size == k * 2
      end
    end
  end
  sort_by_distance(nodes, id)[0...k]
end
get_random_nodes(count) click to toggle source
# File lib/ciri/p2p/kad.rb, line 168
def get_random_nodes(count)
  count = size if count > size
  nodes = []
  while nodes.size < count
    bucket = @buckets.sample
    next if bucket.nodes.empty?
    node = bucket.nodes.sample
    unless nodes.include?(node)
      nodes << node
    end
  end
  nodes
end
idle_buckets() click to toggle source
# File lib/ciri/p2p/kad.rb, line 182
def idle_buckets
  bucket_idled_at = Time.now.to_i - K_IDLE_BUCKET_REFRESH_INTERVAL
  @buckets.select do |bucket| 
    bucket.last_updated < bucket_idled_at
  end
end
include?(node) click to toggle source
# File lib/ciri/p2p/kad.rb, line 225
def include?(node)
  find_bucket_for_node(node).include?(node)
end
not_full_buckets() click to toggle source
# File lib/ciri/p2p/kad.rb, line 189
def not_full_buckets
  @buckets.select do |bucket|
    !bucket.full?
  end
end
size() click to toggle source
# File lib/ciri/p2p/kad.rb, line 229
def size
  @buckets.map(&:size).sum
end
update(raw_node_id) click to toggle source
# File lib/ciri/p2p/kad.rb, line 199
def update(raw_node_id)
  add_node(Node.new(raw_node_id))
end

Private Instance Methods

compute_shared_prefix_bits(nodes) click to toggle source
# File lib/ciri/p2p/kad.rb, line 275
def compute_shared_prefix_bits(nodes)
  return K_ID_SIZE if nodes.size < 2
  bits = nodes.map{|node| to_binary(node.id) }
  (1..K_ID_SIZE).each do |i|
    # check common prefix shared by nodes
    if bits.map{|b| b[0..i]}.uniq.size != 1
      return i - 1
    end
  end
end
sort_by_distance(nodes, target_id) click to toggle source
# File lib/ciri/p2p/kad.rb, line 286
def sort_by_distance(nodes, target_id)
  nodes.sort_by do |node|
    node.distance_to(target_id)
  end
end
split_bucket(index) click to toggle source
# File lib/ciri/p2p/kad.rb, line 268
def split_bucket(index)
  bucket = @buckets[index]
  a, b = bucket.split
  @buckets[index] = a
  @buckets.insert(index + 1, b)
end
to_binary(x) click to toggle source
# File lib/ciri/p2p/kad.rb, line 292
def to_binary(x)
  x.to_s(2).b.rjust(K_ID_SIZE, "\x00".b)
end