Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
factoring
[simgrid.git] / examples / msg / dht-kademlia / node.c
1 /* Copyright (c) 2010, 2012-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 #include "node.h"
8 #include "routing_table.h"
9 #include "simgrid/msg.h"
10
11 XBT_LOG_NEW_DEFAULT_CATEGORY(msg_kademlia_node, "Messages specific for this msg example");
12
13 /** @brief Initialization of a node
14   * @param node_id the id of the node
15   * @return the node created
16   */
17 node_t node_init(unsigned int node_id)
18 {
19   node_t node = xbt_new(s_node_t, 1);
20
21   node->id = node_id;
22   node->table = routing_table_init(node_id);
23   sprintf(node->mailbox, "%0*x", MAILBOX_NAME_SIZE, node_id);
24   node->find_node_failed = 0;
25   node->find_node_success = 0;
26
27   node->task_received = NULL;
28   node->receive_comm = NULL;
29
30   return node;
31 }
32
33 /* @brief Node destructor  */
34 void node_free(node_t node)
35 {
36   routing_table_free(node->table);
37   xbt_free(node);
38 }
39
40 /** @brief Updates/Puts the node id unsigned into our routing table
41   * @param node Our node data
42   * @param id The id of the node we need to add unsigned into our routing table
43   */
44 void node_routing_table_update(node_t node, unsigned int id)
45 {
46   routing_table_t table = node->table;
47   //retrieval of the bucket in which the should be
48   bucket_t bucket = routing_table_find_bucket(table, id);
49
50   //check if the id is already in the bucket.
51   unsigned int id_pos = bucket_find_id(bucket, id);
52
53   if (id_pos == -1) {
54     /* We check if the bucket is full or not. If it is, we evict old offline elements */
55     if (xbt_dynar_length(bucket->nodes) < bucket_size) {
56       //TODO: this is not really very efficient. Maybe we should use something else than dynars ?
57       xbt_dynar_unshift(bucket->nodes, &id);
58       XBT_VERB("I'm adding to my routing table %08x", id);
59     } else {
60       /* TODO: we need to evict the old elements: that's why this function is in "node" instead of "routing table".
61        * This is not implemented yet. */
62     }
63   } else {
64     //We push to the front of the dynar the element.
65     unsigned int element = xbt_dynar_get_as(bucket->nodes, id_pos, unsigned int);
66     xbt_dynar_remove_at(bucket->nodes, id_pos, NULL);
67     xbt_dynar_unshift(bucket->nodes, &element);
68     XBT_VERB("I'm updating %08x", element);
69   }
70 }
71
72 /** @brief Finds the closest nodes to the node given.
73   * @param node : our node
74   * @param destination_id : the id of the guy we are trying to find
75   */
76 answer_t node_find_closest(node_t node, unsigned int destination_id)
77 {
78   int i;
79   answer_t answer = answer_init(destination_id);
80   /* We find the corresponding bucket for the id */
81   bucket_t bucket = routing_table_find_bucket(node->table, destination_id);
82   int bucket_id = bucket->id;
83   xbt_assert((bucket_id <= identifier_size), "Bucket found has a wrong identifier");
84   /* So, we copy the contents of the bucket unsigned into our result dynar */
85   answer_add_bucket(bucket, answer);
86
87   /* However, if we don't have enough elements in our bucket, we NEED to include at least "bucket_size" elements
88    * (if, of course, we know at least "bucket_size" elements. So we're going to look unsigned into the other buckets.
89    */
90   for (i = 1; answer->size < bucket_size && ((bucket_id - i > 0) || (bucket_id + i < identifier_size)); i++) {
91     /* We check the previous buckets */
92     if (bucket_id - i >= 0) {
93       bucket_t bucket_p = &node->table->buckets[bucket_id - i];
94       answer_add_bucket(bucket_p, answer);
95     }
96     /* We check the next buckets */
97     if (bucket_id + i <= identifier_size) {
98       bucket_t bucket_n = &node->table->buckets[bucket_id + i];
99       answer_add_bucket(bucket_n, answer);
100     }
101   }
102   /* We sort the array by XOR distance */
103   answer_sort(answer);
104   /* We trim the array to have only bucket_size or less elements */
105   answer_trim(answer);
106
107   return answer;
108 }
109
110 /**@brief Returns an identifier which is in a specific bucket of a routing table
111  * @param id id of the routing table owner
112  * @param prefix id of the bucket where we want that identifier to be
113  */
114 unsigned int get_id_in_prefix(unsigned int id, unsigned int prefix)
115 {
116   if (prefix == 0) {
117     return 0;
118   }
119   unsigned int n = 1 << (prefix - 1);
120   return n ^ id;
121 }
122
123 /** @brief Returns the prefix of an identifier.
124   * The prefix is the id of the bucket in which the remote identifier xor our identifier should be stored.
125   * @param id : bigunsigned int id to test
126   * @param nb_bits : key size
127   */
128 unsigned int get_node_prefix(unsigned int id, unsigned int nb_bits)
129 {
130   unsigned int j, size = sizeof(unsigned int) * 8;
131   for (j = 0; j < size; j++) {
132     if (((id >> (size - 1 - j)) & 0x1) != 0) {
133       return nb_bits - (j);
134     }
135   }
136   return 0;
137 }
138
139 /** @brief Gets the mailbox name of a host given its identifier
140   */
141 void get_node_mailbox(unsigned int id, char *mailbox)
142 {
143   sprintf(mailbox, "%0*x", MAILBOX_NAME_SIZE, id);
144 }
145
146 /** Constructor, build a new contact information. */
147 node_contact_t node_contact_new(unsigned int id, unsigned int distance)
148 {
149   node_contact_t contact = xbt_new(s_node_contact_t, 1);
150
151   contact->id = id;
152   contact->distance = distance;
153
154   return contact;
155 }
156
157 /** Builds a contact information from a contact information */
158 node_contact_t node_contact_copy(node_contact_t node_contact)
159 {
160   node_contact_t contact = xbt_new(s_node_contact_t, 1);
161
162   contact->id = node_contact->id;
163   contact->distance = node_contact->distance;
164
165   return contact;
166 }
167
168 /** Destructor */
169 void node_contact_free(node_contact_t contact)
170 {
171   xbt_free(contact);
172 }