+/**
+ * \brief Returns the closest preceding finger of an id
+ * with respect to the finger table of the current node.
+ * \param node the current node
+ * \param id the id to find
+ * \return the closest preceding finger of that id
+ */
+int closest_preceding_node(node_t node, int id)
+{
+ int i;
+ for (i = nb_bits - 1; i >= 0; i--) {
+ if (is_in_interval(node->fingers[i].id, node->id + 1, id - 1)) {
+ return node->fingers[i].id;
+ }
+ }
+ return node->id;
+}
+
+/**
+ * \brief This function is called periodically. It checks the immediate
+ * successor of the current node.
+ * \param node the current node
+ */
+static void stabilize(node_t node)
+{
+ XBT_DEBUG("Stabilizing node");
+
+ // get the predecessor of my immediate successor
+ int candidate_id;
+ int successor_id = node->fingers[0].id;
+ if (successor_id != node->id) {
+ candidate_id = remote_get_predecessor(node, successor_id);
+ }
+ else {
+ candidate_id = node->pred_id;
+ }
+
+ // this node is a candidate to become my new successor
+ if (candidate_id != -1
+ && is_in_interval(candidate_id, node->id + 1, successor_id - 1)) {
+ set_finger(node, 0, candidate_id);
+ }
+ if (successor_id != node->id) {
+ remote_notify(node, successor_id, node->id);
+ }
+}
+
+/**
+ * \brief Notifies the current node that its predecessor may have changed.
+ * \param node the current node
+ * \param candidate_id the possible new predecessor
+ */
+static void notify(node_t node, int predecessor_candidate_id) {
+
+ if (node->pred_id == -1
+ || is_in_interval(predecessor_candidate_id, node->pred_id + 1, node->id - 1)) {
+
+ set_predecessor(node, predecessor_candidate_id);
+ print_finger_table(node);
+ }
+ else {
+ XBT_DEBUG("I don't have to change my predecessor to %d", predecessor_candidate_id);
+ }
+}
+
+/**
+ * \brief Notifies a remote node that its predecessor may have changed.
+ * \param node the current node
+ * \param notify_id id of the node to notify
+ * \param candidate_id the possible new predecessor
+ */
+static void remote_notify(node_t node, int notify_id, int predecessor_candidate_id) {
+
+ task_data_t req_data = xbt_new0(s_task_data_t, 1);
+ req_data->type = TASK_NOTIFY;
+ req_data->request_id = predecessor_candidate_id;
+ req_data->issuer_host_name = MSG_host_get_name(MSG_host_self());
+
+ // send a "Notify" request to notify_id
+ msg_task_t task = MSG_task_create(NULL, COMP_SIZE, COMM_SIZE, req_data);
+ XBT_DEBUG("Sending a 'Notify' request (task %p) to %d", task, notify_id);
+ char mailbox[MAILBOX_NAME_SIZE];
+ get_mailbox(notify_id, mailbox);
+ MSG_task_dsend(task, mailbox, task_free);
+ }
+
+/**
+ * \brief This function is called periodically.
+ * It refreshes the finger table of the current node.
+ * \param node the current node
+ */
+static void fix_fingers(node_t node) {
+
+ XBT_DEBUG("Fixing fingers");
+ int i = node->next_finger_to_fix;
+ int id = find_successor(node, node->id + powers2[i]);
+ if (id != -1) {
+
+ if (id != node->fingers[i].id) {
+ set_finger(node, i, id);
+ print_finger_table(node);
+ }
+ node->next_finger_to_fix = (i + 1) % nb_bits;
+ }
+}
+
+/**
+ * \brief This function is called periodically.
+ * It checks whether the predecessor has failed
+ * \param node the current node
+ */
+static void check_predecessor(node_t node)
+{
+ XBT_DEBUG("Checking whether my predecessor is alive");
+
+ if(node->pred_id == -1)
+ return;
+
+ int stop = 0;
+
+ char mailbox[MAILBOX_NAME_SIZE];
+ get_mailbox(node->pred_id, mailbox);
+ task_data_t req_data = xbt_new0(s_task_data_t,1);
+ req_data->type = TASK_PREDECESSOR_ALIVE;
+ req_data->request_id = node->pred_id;
+ get_mailbox(node->id, req_data->answer_to);
+ req_data->issuer_host_name = MSG_host_get_name(MSG_host_self());
+
+ msg_task_t task_sent = MSG_task_create(NULL, COMP_SIZE, COMM_SIZE, req_data);
+ XBT_DEBUG("Sending a 'Predecessor Alive' request to my predecessor %d", node->pred_id);
+
+ msg_error_t res = MSG_task_send_with_timeout(task_sent, mailbox, timeout);
+
+ if (res != MSG_OK) {
+ XBT_DEBUG("Failed to send the 'Predecessor Alive' request (task %p) to %d", task_sent, node->pred_id);
+ task_free(task_sent);
+ }else{
+
+ // receive the answer
+ XBT_DEBUG("Sent 'Predecessor Alive' request (task %p) to %d, waiting for the answer on my mailbox '%s'",
+ task_sent, node->pred_id, req_data->answer_to);
+
+ do {
+ if (node->comm_receive == NULL) { // FIXME simplify this
+ msg_task_t task_received = NULL;
+ node->comm_receive = MSG_task_irecv(&task_received, node->mailbox);
+ }
+
+ res = MSG_comm_wait(node->comm_receive, timeout);
+
+ if (res != MSG_OK) {
+ XBT_DEBUG("Failed to receive the answer to my 'Predecessor Alive' request (task %p): %d",
+ task_sent, (int)res);
+ stop = 1;
+ MSG_comm_destroy(node->comm_receive);
+ node->comm_receive = NULL;
+ node->pred_id = -1;
+ }else {
+ msg_task_t task_received = MSG_comm_get_task(node->comm_receive);
+ if (task_received != task_sent) {
+ MSG_comm_destroy(node->comm_receive);
+ node->comm_receive = NULL;
+ handle_task(node, task_received);
+ }else{
+ XBT_DEBUG("Received the answer to my 'Predecessor Alive' request (task %p) : my predecessor %d is alive", task_received, node->pred_id);
+ stop = 1;
+ MSG_comm_destroy(node->comm_receive);
+ node->comm_receive = NULL;
+ task_free(task_received);
+ }
+ }
+ } while (!stop);
+ }
+}
+
+/**
+ * \brief Performs a find successor request to a random id.
+ * \param node the current node
+ */
+static void random_lookup(node_t node)
+{
+ int random_index = RngStream_RandInt (node->stream, 0, nb_bits - 1);
+ int random_id = node->fingers[random_index].id;
+ XBT_DEBUG("Making a lookup request for id %d", random_id);
+ int res = find_successor(node, random_id);
+ XBT_DEBUG("The successor of node %d is %d", random_id, res);
+
+}
+
+/**
+ * \brief Main function.
+ */