Class: Ciri::P2P::Kad::RoutingTable

Inherits:
Object
  • Object
show all
Defined in:
lib/ciri/p2p/kad.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(local_node:) ⇒ RoutingTable

Returns a new instance of RoutingTable.



163
164
165
166
 
# 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

Instance Attribute Details

#buckets ⇒ Object (readonly)

Returns the value of attribute buckets.



161
162
163
 
# File 'lib/ciri/p2p/kad.rb', line 161

def buckets
  @buckets
end

#local_node ⇒ Object (readonly)

Returns the value of attribute local_node.



161
162
163
 
# File 'lib/ciri/p2p/kad.rb', line 161

def local_node
  @local_node
end

Instance Method Details

#add_node(node) ⇒ Object

Raises:

  • (ArgumentError) 


203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
 
# 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) ⇒ Object 



219
220
221
222
223
 
# 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) ⇒ Object 



195
196
197
 
# File 'lib/ciri/p2p/kad.rb', line 195

def delete_node(node)
  find_bucket_for_node(node).delete(node)
end

#each_node(&blk) ⇒ Object 



233
234
235
236
237
238
239
 
# 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) ⇒ Object

do binary search to find node



260
261
262
263
264
 
# 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) ⇒ Object 



241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
 
# 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) ⇒ Object 



168
169
170
171
172
173
174
175
176
177
178
179
180
 
# 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 ⇒ Object 



182
183
184
185
186
187
 
# 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) ⇒ Boolean

Returns:

  • (Boolean) 


225
226
227
 
# File 'lib/ciri/p2p/kad.rb', line 225

def include?(node)
  find_bucket_for_node(node).include?(node)
end

#not_full_buckets ⇒ Object 



189
190
191
192
193
 
# File 'lib/ciri/p2p/kad.rb', line 189

def not_full_buckets
  @buckets.select do |bucket|
    !bucket.full?
  end
end

#size ⇒ Object 



229
230
231
 
# File 'lib/ciri/p2p/kad.rb', line 229

def size
  @buckets.map(&:size).sum
end

#update(raw_node_id) ⇒ Object 



199
200
201
 
# File 'lib/ciri/p2p/kad.rb', line 199

def update(raw_node_id)
  add_node(Node.new(raw_node_id))
end