Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Capitalize constants.
[simgrid.git] / examples / deprecated / msg / dht-kademlia / answer.c
1 /* Copyright (c) 2012-2019. 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 %u", answer->destination_id, answer->size);
39   xbt_dynar_foreach(answer->nodes, cpt, contact) {
40     XBT_INFO("Node %08x: %08x is at distance %u", 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;
51   node_contact_t contact_copy;
52   unsigned int cpt;
53   unsigned int nb_added = 0;
54   /* TODO: Check if same destination */
55   xbt_dynar_foreach(source->nodes, cpt, contact) {
56     if (answer_contains(destination, contact->id) == 0) {
57       contact_copy = node_contact_copy(contact);
58       xbt_dynar_push(destination->nodes, &contact_copy);
59       destination->size++;
60       nb_added++;
61     }
62   }
63   answer_sort(destination);
64   answer_trim(destination);
65   return nb_added;
66 }
67
68 /** Helper to sort answer_t objects */
69 static int _answer_sort_function(const void *e1, const void *e2)
70 {
71   node_contact_t c1 = *(void **) e1;
72   node_contact_t c2 = *(void **) e2;
73   if (c1->distance == c2->distance)
74     return 0;
75   else
76     if (c1->distance < c2->distance)
77       return -1;
78     else
79       return 1;
80 }
81
82 /** @brief Sorts a answer_t, by node distance.
83   * @param answer the answer to sort
84   * @param destination_id the id of the guy we are trying to find
85   */
86 void answer_sort(answer_t answer)
87 {
88   xbt_dynar_sort(answer->nodes, &_answer_sort_function);
89 }
90
91 /** @brief Trims a answer_t, in order for it to have a size of less or equal to "BUCKET_SIZE"
92   * @param answer the answer_t to trim
93   */
94 void answer_trim(answer_t answer)
95 {
96   node_contact_t value;
97   while (answer->size > BUCKET_SIZE) {
98     xbt_dynar_pop(answer->nodes, &value);
99     answer->size--;
100     node_contact_free(value);
101   }
102   xbt_assert(xbt_dynar_length(answer->nodes) == answer->size, "Wrong size for the answer");
103 }
104
105 /** @brief Adds the content of a bucket unsigned into a answer object.
106   * @param bucket the bucket we have to had unsigned into
107   * @param answer the answer object we're going  to put the data in
108   * @param destination_id the id of the guy we are trying to find.
109   */
110 void answer_add_bucket(bucket_t bucket, answer_t answer)
111 {
112   xbt_assert((bucket != NULL), "Provided a NULL bucket");
113   xbt_assert((bucket->nodes != NULL), "Provided a bucket which nodes are NULL");
114
115   unsigned int cpt;
116   unsigned int id;
117   xbt_dynar_foreach(bucket->nodes, cpt, id) {
118     unsigned int distance  = id ^ answer->destination_id;
119     node_contact_t contact = node_contact_new(id, distance);
120     xbt_dynar_push(answer->nodes, &contact);
121     answer->size++;
122   }
123 }
124
125 /** @brief Returns if the id supplied is in the answer.
126   * @param id : id we're looking for
127   */
128 unsigned int answer_contains(answer_t answer, unsigned int id)
129 {
130   unsigned int i = 0;
131   node_contact_t contact;
132   xbt_dynar_foreach(answer->nodes, i, contact){
133     if (id == contact->id) {
134       return 1;
135     }
136   }
137   return 0;
138 }
139
140 /** @brief Returns if the destination we are trying to find is found
141   * @param answer the answer
142   * @return if the destination is found.
143   */
144 unsigned int answer_destination_found(answer_t answer)
145 {
146   if (xbt_dynar_is_empty(answer->nodes)) {
147     return 0;
148   }
149   node_contact_t contact_tail = xbt_dynar_get_as(answer->nodes, 0, node_contact_t);
150   return contact_tail->distance == 0;
151 }