Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Merge branch 'v3_9_x' of scm.gforge.inria.fr:/gitroot/simgrid/simgrid into v3_9_x
[simgrid.git] / examples / msg / kademlia / answer.c
1 /* Copyright (c) 2012. 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 #include "answer.h"
7
8 XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(msg_kademlia_node);
9
10 /**
11   * Initialize a node answer object.
12   */
13 answer_t answer_init(unsigned int destination_id)
14 {
15   answer_t answer = xbt_new(s_answer_t, 1);
16   answer->nodes = xbt_dynar_new(sizeof(node_contact_t), NULL);
17   answer->size = 0;
18   answer->destination_id = destination_id;
19
20   return answer;
21 }
22
23 /**
24   * Destroys a node answer object.
25   */
26 void answer_free(answer_t answer)
27 {
28   unsigned int i;
29   for (i = 0; i < answer->size; i++) {
30     node_contact_free(*(void **) xbt_dynar_get_ptr(answer->nodes, i));
31   }
32   xbt_dynar_free(&answer->nodes);
33   xbt_free(answer);
34 }
35
36 /**
37   * @brief Prints a answer_t, for debugging purposes
38   */
39 void answer_print(answer_t answer)
40 {
41   unsigned int cpt;
42   node_contact_t contact;
43   XBT_INFO("Searching %08x, size %d", answer->destination_id, answer->size);
44   xbt_dynar_foreach(answer->nodes, cpt, contact) {
45     XBT_INFO("Node %08x: %08x is at distance %d", cpt, contact->id,
46              contact->distance);
47   }
48 }
49
50 /**
51   * @brief Merge two answer_t together, only keeping the best nodes
52   * @param destination the destination in which the nodes will be put
53   * @param source the source of the nodes to add
54   */
55 unsigned int answer_merge(answer_t destination, answer_t source)
56 {
57   node_contact_t contact, contact_copy;
58   unsigned int cpt;
59   unsigned int nb_added = 0;
60   /* TODO: Check if same destination */
61   xbt_dynar_foreach(source->nodes, cpt, contact) {
62     if (!answer_contains(destination, contact->id)) {
63       contact_copy = node_contact_copy(contact);
64       xbt_dynar_push(destination->nodes, &contact_copy);
65       destination->size++;
66       nb_added++;
67     }
68   }
69   answer_sort(destination);
70   answer_trim(destination);
71   return nb_added;
72 }
73
74 /**
75   * Helper to sort answer_t objects
76   */
77 static int _answer_sort_function(const void *e1, const void *e2)
78 {
79   node_contact_t c1 = *(void **) e1;
80   node_contact_t c2 = *(void **) e2;
81   if (c1->distance == c2->distance)
82     return 0;
83   else
84     if (c1->distance < c2->distance)
85       return -1;
86     else
87       return 1;
88 }
89
90 /**
91   * Sorts a answer_t, by node distance.
92   * @param answer the answer to sort
93   * @param destination_id the id of the guy we are trying to find
94   */
95 void answer_sort(answer_t answer)
96 {
97   xbt_dynar_sort(answer->nodes, &_answer_sort_function);
98 }
99
100 /**
101   * Trims a answer_t, in order for it to have a size of less or equal
102   * to "bucket_size"
103   * @param answer the answer_t to trim
104   */
105 void answer_trim(answer_t answer)
106 {
107   node_contact_t value;
108   while (answer->size > bucket_size) {
109     xbt_dynar_pop(answer->nodes, &value);
110     answer->size--;
111     node_contact_free(value);
112   }
113   xbt_assert(xbt_dynar_length(answer->nodes) == answer->size,
114              "Wrong size for the answer");
115 }
116
117 /**
118   * Adds the content of a bucket unsigned into a answer object.
119   * @param bucket the bucket we have to had unsigned into
120   * @param answer the answer object we're going  to put the data in
121   * @param destination_id the id of the guy we are trying to find.
122   */
123 void answer_add_bucket(bucket_t bucket, answer_t answer)
124 {
125   unsigned int cpt;
126   unsigned int id, distance;
127   node_contact_t contact;
128   xbt_assert((bucket != NULL), "Provided a NULL bucket");
129   xbt_assert((bucket->nodes != NULL), "Provided a bucket which nodes are NULL");
130   xbt_dynar_foreach(bucket->nodes, cpt, id) {
131     distance = id ^ answer->destination_id;
132     contact = node_contact_new(id, distance);
133     xbt_dynar_push(answer->nodes, &contact);
134     answer->size++;
135   }
136 }
137
138 /**
139   * Returns if the id supplied is in the answer.
140   * @param id : id we're looking for
141   */
142 unsigned int answer_contains(answer_t answer, unsigned int id)
143 {
144   unsigned int i = 0, size = xbt_dynar_length(answer->nodes);
145   node_contact_t contact;
146   for (i = 0; i < size; i++) {
147     contact = xbt_dynar_get_as(answer->nodes, i, node_contact_t);
148     if (id == contact->id) {
149       return 1;
150     }
151   }
152   return 0;
153 }
154
155 /**
156   * Returns if the destination we are trying to find is found
157   * @param answer the answer
158   * @return if the destination is found.
159   */
160 unsigned int answer_destination_found(answer_t answer)
161 {
162   if (xbt_dynar_length(answer->nodes) < 1) {
163     return 0;
164   }
165   node_contact_t contact_tail =
166       xbt_dynar_get_as(answer->nodes, 0, node_contact_t);
167   return contact_tail->distance == 0;
168 }