Logo AND Algorithmique Numérique Distribuée

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