X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/d0ffc37686edcc803601f76ab51fdfed5fc2f241..903d96f4c7e2f761608b4591faa573aab5891994:/examples/java/kademlia/RoutingTable.java diff --git a/examples/java/kademlia/RoutingTable.java b/examples/java/kademlia/RoutingTable.java index 815d1d0a21..961d38fe35 100644 --- a/examples/java/kademlia/RoutingTable.java +++ b/examples/java/kademlia/RoutingTable.java @@ -1,132 +1,113 @@ -/* Copyright (c) 2012-2013. The SimGrid Team. +/* Copyright (c) 2012-2014, 2016. The SimGrid Team. * All rights reserved. */ /* This program is free software; you can redistribute it and/or modify it * under the terms of the license (GNU LGPL) which comes with this package. */ + package kademlia; import java.util.Collections; import java.util.Vector; import org.simgrid.msg.Msg; -/** - * @brief Contains the various data of a routing table. - */ + public class RoutingTable { - /** - * Bucket list - */ - private Vector buckets; - /** - * Id of the routing table owner - */ - private int id; - /** - * Constructor - */ - public RoutingTable(int id) { - this.id = id; - buckets = new Vector(); - for (int i = 0; i < Common.IDENTIFIER_SIZE + 1; i++) { - buckets.add(new Bucket(i)); - } - } - /** - * Returns an identifier which is in a specific bucket of a routing table - * @brief id id of the routing table owner - * @brief prefix id of the bucket where we want that identifier to be - */ - public int getIdInPrefix(int id, int prefix) { - if (prefix == 0) { - return 0; - } - int identifier = 1; - identifier = identifier << (prefix - 1); - identifier = identifier ^ id; - return identifier; - } - /** - * Returns the corresponding node prefix for a given id - */ - public int getNodePrefix(int id) { - for (int j = 0; j < 32; j++) { - if ((id >> (32 - 1 - j) & 0x1) != 0) { - return 32 - j; - } - } - return 0; - } - /** - * Fins the corresponding bucket in a routing table for a given identifier - */ - public Bucket findBucket(int id) { - int xorNumber = id ^ this.id; -// Msg.info("Number:" + xorNumber.toString(16)); - int prefix = this.getNodePrefix(xorNumber); - - return buckets.get(prefix); - } - /** - * Updates the routing table with a new value. - */ - public void update(int id) { + /* Bucket list */ + private Vector buckets; + /* Id of the routing table owner */ + private int id; + + public RoutingTable(int id) { + this.id = id; + buckets = new Vector(); + for (int i = 0; i < Common.IDENTIFIER_SIZE + 1; i++) { + buckets.add(new Bucket(i)); + } + } + + /** + * @brief Returns an identifier which is in a specific bucket of a routing table + * @param id id of the routing table owner + * @param prefix id of the bucket where we want that identifier to be + */ + public int getIdInPrefix(int id, int prefix) { + if (prefix == 0) { + return 0; + } + int identifier = 1; + identifier = identifier << (prefix - 1); + identifier = identifier ^ id; + return identifier; + } + + /* Returns the corresponding node prefix for a given id */ + public int getNodePrefix(int id) { + for (int j = 0; j < 32; j++) { + if ((id >> (32 - 1 - j) & 0x1) != 0) { + return 32 - j; + } + } + return 0; + } + + /* Finds the corresponding bucket in a routing table for a given identifier */ + public Bucket findBucket(int id) { + int xorNumber = id ^ this.id; + int prefix = this.getNodePrefix(xorNumber); + return buckets.get(prefix); + } + + /* Updates the routing table with a new value. */ + public void update(int id) { + Bucket bucket = this.findBucket(id); + if (bucket.contains(id)) { + Msg.debug("Updating " + Integer.toString(id) + " in my routing table"); + //If the element is already in the bucket, we update it. + bucket.pushToFront(id); + } else { + Msg.debug("Adding " + id + " to my routing table"); + bucket.add(id); + if (bucket.size() > Common.BUCKET_SIZE) { + //TODO: Ping the least seen guy and remove him if he is offline. + } + } + } - Bucket bucket = this.findBucket(id); - if (bucket.contains(id)) { - Msg.debug("Updating " + Integer.toString(id) + " in my routing table"); - //If the element is already in the bucket, we update it. - bucket.pushToFront(id); - } - else { - Msg.debug("Adding " + id + " to my routing table"); - bucket.add(id); - if (bucket.size() > Common.BUCKET_SIZE) { - //TODO: Ping the least seen guy and remove him if he is offline. - } - } - } - /** - * Returns the closest notes we know to a given id - */ - public Answer findClosest(int destinationId) { - Answer answer = new Answer(destinationId); + /* Returns the closest notes we know to a given id */ + public Answer findClosest(int destinationId) { + Answer answer = new Answer(destinationId); + Bucket bucket = this.findBucket(destinationId); + bucket.addToAnswer(answer,destinationId); - - Bucket bucket = this.findBucket(destinationId); - bucket.addToAnswer(answer,destinationId); - - for (int i = 1; answer.size() < Common.BUCKET_SIZE && - ((bucket.getId() - i) >= 0 || - (bucket.getId() + i) <= Common.IDENTIFIER_SIZE); i++) { - //Check the previous buckets - if (bucket.getId() - i >= 0) { - Bucket bucketP = this.buckets.get(bucket.getId() - i); - bucketP.addToAnswer(answer,destinationId); - } - //Check the next buckets - if (bucket.getId() + i <= Common.IDENTIFIER_SIZE) { - Bucket bucketN = this.buckets.get(bucket.getId() + i); - bucketN.addToAnswer(answer, destinationId); - } - } - //We sort the list - Collections.sort(answer.getNodes()); - //We trim the list - while (answer.size() > Common.BUCKET_SIZE) { - answer.remove(answer.size() - 1); //TODO: Not the best thing. - } - - return answer; - } - - @Override - public String toString() { - String string = "RoutingTable [ id=" + id + " " ; - for (int i = 0; i < buckets.size(); i++) { - if (buckets.get(i).size() > 0) { - string += buckets.get(i) + " "; - } - } - return string; - } + for (int i = 1; answer.size() < Common.BUCKET_SIZE && ((bucket.getId() - i) >= 0 || + (bucket.getId() + i) <= Common.IDENTIFIER_SIZE); i++) { + //Check the previous buckets + if (bucket.getId() - i >= 0) { + Bucket bucketP = this.buckets.get(bucket.getId() - i); + bucketP.addToAnswer(answer,destinationId); + } + //Check the next buckets + if (bucket.getId() + i <= Common.IDENTIFIER_SIZE) { + Bucket bucketN = this.buckets.get(bucket.getId() + i); + bucketN.addToAnswer(answer, destinationId); + } + } + //We sort the list + Collections.sort(answer.getNodes()); + //We trim the list + while (answer.size() > Common.BUCKET_SIZE) { + answer.remove(answer.size() - 1); //TODO: Not the best thing. + } + return answer; + } + @Override + public String toString() { + String string = "RoutingTable [ id=" + id + " " ; + for (int i = 0; i < buckets.size(); i++) { + if (buckets.get(i).size() > 0) { + string += buckets.get(i) + " "; + } + } + return string; + } }