1 /* Copyright (c) 2012-2023. The SimGrid Team.
2 * All rights reserved. */
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. */
10 XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(dht_kademlia_node);
12 /** Initialize a node answer object. */
13 answer_t answer_init(unsigned int destination_id)
15 answer_t answer = xbt_new(s_answer_t, 1);
16 answer->nodes = xbt_dynar_new(sizeof(node_contact_t), NULL);
18 answer->destination_id = destination_id;
23 /** Destroys a node answer object. */
24 void answer_free(answer_t answer)
27 for (unsigned int i = 0; i < answer->size; i++)
28 node_contact_free(*(void**)xbt_dynar_get_ptr(answer->nodes, i));
29 xbt_dynar_free(&answer->nodes);
34 /** @brief Prints an answer_t, for debugging purposes */
35 void answer_print(const_answer_t answer)
38 node_contact_t contact;
39 XBT_INFO("Searching %08x, size %u", answer->destination_id, answer->size);
40 xbt_dynar_foreach (answer->nodes, cpt, contact) {
41 XBT_INFO("Node %08x: %08x is at distance %u", cpt, contact->id, contact->distance);
45 /** @brief Merge two answer_t together, only keeping the best nodes
46 * @param destination the destination in which the nodes will be put
47 * @param source the source of the nodes to add
49 unsigned int answer_merge(answer_t destination, const_answer_t source)
51 if (destination == source)
54 node_contact_t contact;
55 node_contact_t contact_copy;
57 unsigned int nb_added = 0;
58 /* TODO: Check if same destination */
59 xbt_dynar_foreach (source->nodes, cpt, contact) {
60 if (answer_contains(destination, contact->id) == 0) {
61 contact_copy = node_contact_copy(contact);
62 xbt_dynar_push(destination->nodes, &contact_copy);
67 answer_sort(destination);
68 answer_trim(destination);
72 /** Helper to sort answer_t objects */
73 static int _answer_sort_function(const void* e1, const void* e2)
75 const s_node_contact_t* c1 = *(const node_contact_t*)e1;
76 const s_node_contact_t* c2 = *(const node_contact_t*)e2;
77 if (c1->distance == c2->distance)
79 else if (c1->distance < c2->distance)
85 /** @brief Sorts an answer_t, by node distance.
86 * @param answer the answer to sort
87 * @param destination_id the id of the guy we are trying to find
89 void answer_sort(const_answer_t answer)
91 xbt_dynar_sort(answer->nodes, &_answer_sort_function);
94 /** @brief Trims an answer_t, in order for it to have a size of less or equal to "BUCKET_SIZE"
95 * @param answer the answer_t to trim
97 void answer_trim(answer_t answer)
100 while (answer->size > BUCKET_SIZE) {
101 xbt_dynar_pop(answer->nodes, &value);
103 node_contact_free(value);
105 xbt_assert(xbt_dynar_length(answer->nodes) == answer->size, "Wrong size for the answer");
108 /** @brief Adds the content of a bucket unsigned into an answer object.
109 * @param bucket the bucket we have to had unsigned into
110 * @param answer the answer object we're going to put the data in
111 * @param destination_id the id of the guy we are trying to find.
113 void answer_add_bucket(const_bucket_t bucket, answer_t answer)
115 xbt_assert((bucket != NULL), "Provided a NULL bucket");
116 xbt_assert((bucket->nodes != NULL), "Provided a bucket which nodes are NULL");
120 xbt_dynar_foreach (bucket->nodes, cpt, id) {
121 unsigned int distance = id ^ answer->destination_id;
122 node_contact_t contact = node_contact_new(id, distance);
123 xbt_dynar_push(answer->nodes, &contact);
128 /** @brief Returns if the id supplied is in the answer.
129 * @param id : id we're looking for
131 unsigned int answer_contains(const_answer_t answer, unsigned int id)
134 node_contact_t contact;
135 xbt_dynar_foreach (answer->nodes, i, contact) {
136 if (id == contact->id) {
143 /** @brief Returns if the destination we are trying to find is found
144 * @param answer the answer
145 * @return if the destination is found.
147 unsigned int answer_destination_found(const_answer_t answer)
149 if (xbt_dynar_is_empty(answer->nodes)) {
152 const s_node_contact_t* contact_tail = xbt_dynar_get_as(answer->nodes, 0, node_contact_t);
153 return contact_tail->distance == 0;