xbt_dynar_sort(answer->nodes, &_answer_sort_function);
}
-/** @brief Trims a answer_t, in order for it to have a size of less or equal to "bucket_size"
+/** @brief Trims a answer_t, in order for it to have a size of less or equal to "BUCKET_SIZE"
* @param answer the answer_t to trim
*/
void answer_trim(answer_t answer)
{
node_contact_t value;
- while (answer->size > bucket_size) {
+ while (answer->size > BUCKET_SIZE) {
xbt_dynar_pop(answer->nodes, &value);
answer->size--;
node_contact_free(value);
#ifndef _KADEMLIA_EXAMPLES_COMMON
#define _KADEMLIA_EXAMPLES_COMMON
-#define max_join_trials 4
-#define find_node_timeout 10
-#define find_node_global_timeout 50
+#define MAX_JOIN_TRIALS 4
-#define kademlia_alpha 3
-#define bucket_size 20
+#define FIND_NODE_TIMEOUT 10
+#define FIND_NODE_GLOBAL_TIMEOUT 50
-#define identifier_size 32
+#define KADEMLIA_ALPHA 3
+#define BUCKET_SIZE 20
-#define random_lookup_interval 100
+#define IDENTIFIER_SIZE 32
+
+#define RANDOM_LOOKUP_INTERVAL 100
#define MAILBOX_NAME_SIZE 16 /* (identifier_size / 4) (hex encoded) */
/* Main loop for the process */
static void main_loop(node_t node, double deadline)
{
- double next_lookup_time = MSG_get_clock() + random_lookup_interval;
+ double next_lookup_time = MSG_get_clock() + RANDOM_LOOKUP_INTERVAL;
XBT_VERB("Main loop start");
while (MSG_get_clock() < deadline) {
/* We search for a pseudo random node */
if (MSG_get_clock() >= next_lookup_time) {
random_lookup(node);
- next_lookup_time += random_lookup_interval;
+ next_lookup_time += RANDOM_LOOKUP_INTERVAL;
} else {
//Didn't get a task: sleep for a while...
MSG_process_sleep(1);
} else {
MSG_process_sleep(1);
}
- } while (answer_got == 0 && trial < max_join_trials);
+ } while (answer_got == 0 && trial < MAX_JOIN_TRIALS);
/* Second step: Send a FIND_NODE to a a random node in buckets */
unsigned int bucket_id = routing_table_find_bucket(node->table, id_known)->id;
- for (i = 0; ((bucket_id > i) || (bucket_id + i) <= identifier_size) && i < JOIN_BUCKETS_QUERIES; i++) {
+ for (i = 0; ((bucket_id > i) || (bucket_id + i) <= IDENTIFIER_SIZE) && i < JOIN_BUCKETS_QUERIES; i++) {
if (bucket_id > i) {
unsigned int id_in_bucket = get_id_in_prefix(node->id, bucket_id - i);
find_node(node, id_in_bucket, 0);
}
- if (bucket_id + i <= identifier_size) {
+ if (bucket_id + i <= IDENTIFIER_SIZE) {
unsigned int id_in_bucket = get_id_in_prefix(node->id, bucket_id + i);
find_node(node, id_in_bucket, 0);
}
unsigned int answers;
unsigned int destination_found = 0;
unsigned int nodes_added = 0;
- double global_timeout = MSG_get_clock() + find_node_global_timeout;
+ double global_timeout = MSG_get_clock() + FIND_NODE_GLOBAL_TIMEOUT;
unsigned int steps = 0;
/* First we build a list of who we already know */
answers = 0;
queries = send_find_node_to_best(node, node_list);
nodes_added = 0;
- double timeout = MSG_get_clock() + find_node_timeout;
+ double timeout = MSG_get_clock() + FIND_NODE_TIMEOUT;
steps++;
double time_beginreceive = MSG_get_clock();
do {
}
/**
- * Sends to the best "kademlia_alpha" nodes in the "node_list" array a "FIND_NODE" request, to ask them for their best nodes
+ * Sends to the best "KADEMLIA_ALPHA" nodes in the "node_list" array a "FIND_NODE" request, to ask them for their best
+ * nodes
*/
unsigned int send_find_node_to_best(node_t node, answer_t node_list)
{
unsigned int i = 0;
unsigned int j = 0;
unsigned int destination = node_list->destination_id;
- while (j < kademlia_alpha && i < node_list->size) {
- /* We need to have at most "kademlia_alpha" requests each time, according to the protocol */
+ while (j < KADEMLIA_ALPHA && i < node_list->size) {
+ /* We need to have at most "KADEMLIA_ALPHA" requests each time, according to the protocol */
/* Gets the node we want to send the query to */
node_contact_t node_to_query = xbt_dynar_get_as(node_list->nodes, i, node_contact_t);
if (node_to_query->id != node->id) { /* No need to query ourselves */
if (id_pos == -1) {
/* We check if the bucket is full or not. If it is, we evict old offline elements */
- if (xbt_dynar_length(bucket->nodes) < bucket_size) {
+ if (xbt_dynar_length(bucket->nodes) < BUCKET_SIZE) {
//TODO: this is not really very efficient. Maybe we should use something else than dynars ?
xbt_dynar_unshift(bucket->nodes, &id);
XBT_VERB("I'm adding to my routing table %08x", id);
/* We find the corresponding bucket for the id */
bucket_t bucket = routing_table_find_bucket(node->table, destination_id);
int bucket_id = bucket->id;
- xbt_assert((bucket_id <= identifier_size), "Bucket found has a wrong identifier");
+ xbt_assert((bucket_id <= IDENTIFIER_SIZE), "Bucket found has a wrong identifier");
/* So, we copy the contents of the bucket unsigned into our result dynar */
answer_add_bucket(bucket, answer);
- /* However, if we don't have enough elements in our bucket, we NEED to include at least "bucket_size" elements
- * (if, of course, we know at least "bucket_size" elements. So we're going to look unsigned into the other buckets.
+ /* However, if we don't have enough elements in our bucket, we NEED to include at least "BUCKET_SIZE" elements
+ * (if, of course, we know at least "BUCKET_SIZE" elements. So we're going to look unsigned into the other buckets.
*/
- for (i = 1; answer->size < bucket_size && ((bucket_id - i > 0) || (bucket_id + i < identifier_size)); i++) {
+ for (i = 1; answer->size < BUCKET_SIZE && ((bucket_id - i > 0) || (bucket_id + i < IDENTIFIER_SIZE)); i++) {
/* We check the previous buckets */
if (bucket_id - i >= 0) {
bucket_t bucket_p = &node->table->buckets[bucket_id - i];
answer_add_bucket(bucket_p, answer);
}
/* We check the next buckets */
- if (bucket_id + i <= identifier_size) {
+ if (bucket_id + i <= IDENTIFIER_SIZE) {
bucket_t bucket_n = &node->table->buckets[bucket_id + i];
answer_add_bucket(bucket_n, answer);
}
}
/* We sort the array by XOR distance */
answer_sort(answer);
- /* We trim the array to have only bucket_size or less elements */
+ /* We trim the array to have only BUCKET_SIZE or less elements */
answer_trim(answer);
return answer;
routing_table_t routing_table_init(unsigned int node_id)
{
routing_table_t table = xbt_new(s_routing_table_t, 1);
- table->buckets = xbt_new(s_bucket_t, identifier_size + 1);
- for (unsigned int i = 0; i < identifier_size + 1; i++) {
+ table->buckets = xbt_new(s_bucket_t, IDENTIFIER_SIZE + 1);
+ for (unsigned int i = 0; i < IDENTIFIER_SIZE + 1; i++) {
table->buckets[i].nodes = xbt_dynar_new(sizeof(unsigned int), NULL);
table->buckets[i].id = i;
}
{
unsigned int i;
//Free the buckets.
- for (i = 0; i <= identifier_size; i++) {
+ for (i = 0; i <= IDENTIFIER_SIZE; i++) {
xbt_dynar_free(&table->buckets[i].nodes);
}
xbt_free(table->buckets);
unsigned int value;
XBT_INFO("Routing table of %08x:", table->id);
- for (unsigned int i = 0; i <= identifier_size; i++) {
+ for (unsigned int i = 0; i <= IDENTIFIER_SIZE; i++) {
if (!xbt_dynar_is_empty(table->buckets[i].nodes)) {
XBT_INFO("Bucket number %u: ", i);
xbt_dynar_foreach(table->buckets[i].nodes, j, value) {
bucket_t routing_table_find_bucket(routing_table_t table, unsigned int id)
{
unsigned int xor_number = table->id ^ id;
- unsigned int prefix = get_node_prefix(xor_number, identifier_size);
- xbt_assert(prefix <= identifier_size, "Tried to return a bucket that doesn't exist.");
+ unsigned int prefix = get_node_prefix(xor_number, IDENTIFIER_SIZE);
+ xbt_assert(prefix <= IDENTIFIER_SIZE, "Tried to return a bucket that doesn't exist.");
bucket_t bucket = &table->buckets[prefix];
return bucket;
}
