Logo AND Algorithmique Numérique Distribuée

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