examples/c/dht-kademlia/answer.c

   1 /* Copyright (c) 2012-2020. 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 #include "node.h"
   9
  10 XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(dht_kademlia_node);
  11
  12 /** Initialize a node answer object. */
  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 /** Destroys a node answer object. */
  24 void answer_free(answer_t answer)
  25 {
  26   unsigned int i;
  27   if (answer) {
  28     for (i = 0; i < answer->size; i++) {
  29       node_contact_free(*(void**)xbt_dynar_get_ptr(answer->nodes, i));
  30     }
  31     xbt_dynar_free(&answer->nodes);
  32   }
  33   xbt_free(answer);
  34 }
  35
  36 /** @brief Prints a answer_t, for debugging purposes */
  37 void answer_print(const_answer_t answer)
  38 {
  39   unsigned int cpt;
  40   node_contact_t contact;
  41   XBT_INFO("Searching %08x, size %u", answer->destination_id, answer->size);
  42   xbt_dynar_foreach (answer->nodes, cpt, contact) {
  43     XBT_INFO("Node %08x: %08x is at distance %u", cpt, contact->id, contact->distance);
  44   }
  45 }
  46
  47 /** @brief Merge two answer_t together, only keeping the best nodes
  48  * @param destination the destination in which the nodes will be put
  49  * @param source the source of the nodes to add
  50  */
  51 unsigned int answer_merge(answer_t destination, const_answer_t source)
  52 {
  53   if (destination == source)
  54     return 0;
  55
  56   node_contact_t contact;
  57   node_contact_t 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) == 0) {
  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 /** Helper to sort answer_t objects */
  75 static int _answer_sort_function(const void* e1, const void* e2)
  76 {
  77   const s_node_contact_t* c1 = *(const node_contact_t*)e1;
  78   const s_node_contact_t* c2 = *(const node_contact_t*)e2;
  79   if (c1->distance == c2->distance)
  80     return 0;
  81   else if (c1->distance < c2->distance)
  82     return -1;
  83   else
  84     return 1;
  85 }
  86
  87 /** @brief Sorts a answer_t, by node distance.
  88  * @param answer the answer to sort
  89  * @param destination_id the id of the guy we are trying to find
  90  */
  91 void answer_sort(const_answer_t answer)
  92 {
  93   xbt_dynar_sort(answer->nodes, &_answer_sort_function);
  94 }
  95
  96 /** @brief Trims a answer_t, in order for it to have a size of less or equal to "BUCKET_SIZE"
  97  * @param answer the answer_t to trim
  98  */
  99 void answer_trim(answer_t answer)
 100 {
 101   node_contact_t value;
 102   while (answer->size > BUCKET_SIZE) {
 103     xbt_dynar_pop(answer->nodes, &value);
 104     answer->size--;
 105     node_contact_free(value);
 106   }
 107   xbt_assert(xbt_dynar_length(answer->nodes) == answer->size, "Wrong size for the answer");
 108 }
 109
 110 /** @brief Adds the content of a bucket unsigned into a answer object.
 111  * @param bucket the bucket we have to had unsigned into
 112  * @param answer the answer object we're going  to put the data in
 113  * @param destination_id the id of the guy we are trying to find.
 114  */
 115 void answer_add_bucket(const_bucket_t bucket, answer_t answer)
 116 {
 117   xbt_assert((bucket != NULL), "Provided a NULL bucket");
 118   xbt_assert((bucket->nodes != NULL), "Provided a bucket which nodes are NULL");
 119
 120   unsigned int cpt;
 121   unsigned int id;
 122   xbt_dynar_foreach (bucket->nodes, cpt, id) {
 123     unsigned int distance  = id ^ answer->destination_id;
 124     node_contact_t contact = node_contact_new(id, distance);
 125     xbt_dynar_push(answer->nodes, &contact);
 126     answer->size++;
 127   }
 128 }
 129
 130 /** @brief Returns if the id supplied is in the answer.
 131  * @param id : id we're looking for
 132  */
 133 unsigned int answer_contains(const_answer_t answer, unsigned int id)
 134 {
 135   unsigned int i = 0;
 136   node_contact_t contact;
 137   xbt_dynar_foreach (answer->nodes, i, contact) {
 138     if (id == contact->id) {
 139       return 1;
 140     }
 141   }
 142   return 0;
 143 }
 144
 145 /** @brief Returns if the destination we are trying to find is found
 146  * @param answer the answer
 147  * @return if the destination is found.
 148  */
 149 unsigned int answer_destination_found(const_answer_t answer)
 150 {
 151   if (xbt_dynar_is_empty(answer->nodes)) {
 152     return 0;
 153   }
 154   const s_node_contact_t* contact_tail = xbt_dynar_get_as(answer->nodes, 0, node_contact_t);
 155   return contact_tail->distance == 0;
 156 }