examples/java/kademlia/RoutingTable.java

   1 /* Copyright (c) 2012-2014, 2016. The SimGrid Team.
   2  * All rights reserved.                                                     */
   3
   4 /* This program is free software; you can redistribute it and/or modify it
   5  * under the terms of the license (GNU LGPL) which comes with this package. */
   6
   7 package kademlia;
   8 import java.util.Collections;
   9 import java.util.Vector;
  10
  11 import org.simgrid.msg.Msg;
  12
  13 public class RoutingTable {
  14   /* Bucket list */
  15   private Vector<Bucket> buckets;
  16   /* Id of the routing table owner */
  17   private int id;
  18
  19   public RoutingTable(int id) {
  20     this.id = id;
  21     buckets = new Vector<Bucket>();
  22     for (int i = 0; i < Common.IDENTIFIER_SIZE + 1; i++) {
  23       buckets.add(new Bucket(i));
  24     }
  25   }
  26
  27   /**
  28    * @brief Returns an identifier which is in a specific bucket of a routing table
  29    * @param id id of the routing table owner
  30    * @param prefix id of the bucket where we want that identifier to be
  31    */
  32   public int getIdInPrefix(int id, int prefix) {
  33     if (prefix == 0) {
  34       return 0;
  35     }
  36     int identifier = 1;
  37     identifier = identifier << (prefix - 1);
  38     identifier = identifier ^ id;
  39     return identifier;
  40   }
  41
  42   /* Returns the corresponding node prefix for a given id */
  43   public int getNodePrefix(int id) {
  44     for (int j = 0; j < 32; j++) {
  45       if ((id >> (32 - 1 - j) & 0x1) != 0) {
  46         return 32 - j;
  47       }
  48     }
  49     return 0;
  50   }
  51
  52   /* Finds the corresponding bucket in a routing table for a given identifier */
  53   public Bucket findBucket(int id) {
  54     int xorNumber = id ^ this.id;
  55     int prefix = this.getNodePrefix(xorNumber);
  56     return buckets.get(prefix);
  57   }
  58
  59   /* Updates the routing table with a new value. */
  60   public void update(int id) {
  61     Bucket bucket = this.findBucket(id);
  62     if (bucket.contains(id)) {
  63       Msg.debug("Updating " + Integer.toString(id) + " in my routing table");
  64       //If the element is already in the bucket, we update it.
  65       bucket.pushToFront(id);
  66     } else {
  67       Msg.debug("Adding " + id + " to my routing table");
  68       bucket.add(id);
  69       if (bucket.size() > Common.BUCKET_SIZE)  {
  70         //TODO: Ping the least seen guy and remove him if he is offline.
  71       }
  72     }
  73   }
  74
  75   /* Returns the closest notes we know to a given id */
  76   public Answer findClosest(int destinationId) {
  77     Answer answer = new Answer(destinationId);
  78     Bucket bucket = this.findBucket(destinationId);
  79     bucket.addToAnswer(answer,destinationId);
  80
  81     for (int i = 1; answer.size() < Common.BUCKET_SIZE && ((bucket.getId() - i) >= 0 ||
  82                                     (bucket.getId() + i) <= Common.IDENTIFIER_SIZE); i++) {
  83       //Check the previous buckets
  84       if (bucket.getId() - i >= 0) {
  85         Bucket bucketP = this.buckets.get(bucket.getId() - i);
  86         bucketP.addToAnswer(answer,destinationId);
  87       }
  88       //Check the next buckets
  89       if (bucket.getId() + i <= Common.IDENTIFIER_SIZE) {
  90         Bucket bucketN = this.buckets.get(bucket.getId() + i);
  91         bucketN.addToAnswer(answer, destinationId);
  92       }
  93     }
  94     //We sort the list
  95     Collections.sort(answer.getNodes());
  96     //We trim the list
  97     while (answer.size() > Common.BUCKET_SIZE) {
  98       answer.remove(answer.size() - 1); //TODO: Not the best thing.
  99     }
 100     return answer;
 101   }
 102
 103   @Override
 104   public String toString() {
 105     String string = "RoutingTable [ id=" + id + " " ;
 106     for (int i = 0; i < buckets.size(); i++) {
 107       if (buckets.get(i).size() > 0) {
 108         string += buckets.get(i) + " ";
 109       }
 110     }
 111     return string;
 112   }
 113 }