Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Fix doxygen comments.
[simgrid.git] / examples / lua / kademlia / routing_table.lua
1 -- Routing table data
2 routing_table = {
3 buckets = {},
4 }
5 -- Initialize the routing table
6 function routing_table_init(id) 
7         routing_table.id = id
8         -- Bucket initialization
9         for i = 0,common.IDENTIFIER_SIZE do
10                 routing_table.buckets[i] = {id = i, set = {}, list = {}}
11         end
12 end
13 -- Returns an identifier which is in a specific bucket of a routing table
14 function get_id_in_prefix(id, prefix)
15         if id == 0 then
16                 return 0
17         end
18         local identifier = 1
19         identifier = math.pow(identifier,prefix - 1)
20         identifier = bxor(identifier,id)
21         return identifier
22 end
23 -- Returns the corresponding node prefix for a given id
24 function get_node_prefix(id)
25         for i = 0,32 do
26                 if is_integer(id / math.pow(2,i)) and (id / math.pow(2,i)) % 2 == 1 then
27                         return 31 - i
28                 end
29         end 
30         return 0
31 end
32 -- Finds the corresponding bucket in a routing table for a given identifier
33 function find_bucket(id)
34         local xor_number = bxor(id,routing_table.id)
35         local prefix = get_node_prefix(xor_number)
36         --simgrid.info("Prefix:" .. prefix .. " number:" .. xor_number)
37         return routing_table.buckets[prefix]
38 end
39 -- Updates the routing table with a new value.
40 function routing_table_update(id)
41         if id == routing_table.id then
42                 return
43         end
44         local bucket = find_bucket(id)
45         if bucket.set[id] ~= nil then
46                 simgrid.debug("Updating " .. id .. " in my routing table")
47                 -- If the element is already in the bucket, we update it.
48                 table.remove(bucket.list,index_of(bucket.list,id))
49                 table.insert(bucket.list,0,id)
50         else    
51                 simgrid.debug("Insert " .. id .. " in my routing table in bucket " .. bucket.id)
52                 table.insert(bucket.list,id)
53                 bucket.set[id] = true
54         end
55 end
56 -- Returns the closest notes we know to a given id 
57 function find_closest(destination_id)
58         local answer = {destination = destination_id, nodes = {}}
59         
60         local bucket = find_bucket(destination_id)
61         for i,v in pairs(bucket.list) do
62                 table.insert(answer.nodes,{id = v, distance = bxor(v,destination_id)})
63         end
64         
65         local i = 1
66         
67         while #answer.nodes < common.BUCKET_SIZE and ((bucket.id - i) >= 0 or (bucket.id + i) <= common.IDENTIFIER_SIZE) do
68                 -- Check the previous buckets
69                 if bucket.id - i >= 0 then
70                         local bucket_p = routing_table.buckets[bucket.id - i]
71                         for i,v in pairs(bucket_p.list) do
72                                 table.insert(answer.nodes,{id = v, distance = bxor(v,destination_id)})
73                         end
74                 end                     
75                 -- Check the next buckets
76                 if bucket.id + i <= common.IDENTIFIER_SIZE then
77                         local bucket_n = routing_table.buckets[bucket.id + i]
78                         for i,v in pairs(bucket_n.list) do
79                                 table.insert(answer.nodes,{id = v, distance = bxor(v,destination_id)})
80                         end                     
81                 end
82                 i = i + 1
83         end
84         -- Sort the list
85         table.sort(answer.nodes, function(a,b) return a.distance < b.distance end)
86         -- Trim the list
87         while #answer.nodes > common.BUCKET_SIZE do
88                 table.remove(answer.nodes)
89         end
90         
91         return answer
92 end