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 #include "node.h"
   9
  10 XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(msg_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   for (i = 0; i < answer->size; i++) {
  28     node_contact_free(*(void **) xbt_dynar_get_ptr(answer->nodes, i));
  29   }
  30   xbt_dynar_free(&answer->nodes);
  31   xbt_free(answer);
  32 }
  33
  34 /** @brief Prints a answer_t, for debugging purposes */
  35 void answer_print(answer_t answer)
  36 {
  37   unsigned int cpt;
  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);
  42   }
  43 }
  44
  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
  48   */
  49 unsigned int answer_merge(answer_t destination, answer_t source)
  50 {
  51   node_contact_t contact;
  52   node_contact_t contact_copy;
  53   unsigned int cpt;
  54   unsigned int nb_added = 0;
  55   /* TODO: Check if same destination */
  56   xbt_dynar_foreach(source->nodes, cpt, contact) {
  57     if (answer_contains(destination, contact->id) == 0) {
  58       contact_copy = node_contact_copy(contact);
  59       xbt_dynar_push(destination->nodes, &contact_copy);
  60       destination->size++;
  61       nb_added++;
  62     }
  63   }
  64   answer_sort(destination);
  65   answer_trim(destination);
  66   return nb_added;
  67 }
  68
  69 /** Helper to sort answer_t objects */
  70 static int _answer_sort_function(const void *e1, const void *e2)
  71 {
  72   node_contact_t c1 = *(const node_contact_t*)e1;
  73   node_contact_t c2 = *(const node_contact_t*)e2;
  74   if (c1->distance == c2->distance)
  75     return 0;
  76   else
  77     if (c1->distance < c2->distance)
  78       return -1;
  79     else
  80       return 1;
  81 }
  82
  83 /** @brief Sorts a answer_t, by node distance.
  84   * @param answer the answer to sort
  85   * @param destination_id the id of the guy we are trying to find
  86   */
  87 void answer_sort(answer_t answer)
  88 {
  89   xbt_dynar_sort(answer->nodes, &_answer_sort_function);
  90 }
  91
  92 /** @brief Trims a answer_t, in order for it to have a size of less or equal to "BUCKET_SIZE"
  93   * @param answer the answer_t to trim
  94   */
  95 void answer_trim(answer_t answer)
  96 {
  97   node_contact_t value;
  98   while (answer->size > BUCKET_SIZE) {
  99     xbt_dynar_pop(answer->nodes, &value);
 100     answer->size--;
 101     node_contact_free(value);
 102   }
 103   xbt_assert(xbt_dynar_length(answer->nodes) == answer->size, "Wrong size for the answer");
 104 }
 105
 106 /** @brief Adds the content of a bucket unsigned into a answer object.
 107   * @param bucket the bucket we have to had unsigned into
 108   * @param answer the answer object we're going  to put the data in
 109   * @param destination_id the id of the guy we are trying to find.
 110   */
 111 void answer_add_bucket(bucket_t bucket, answer_t answer)
 112 {
 113   xbt_assert((bucket != NULL), "Provided a NULL bucket");
 114   xbt_assert((bucket->nodes != NULL), "Provided a bucket which nodes are NULL");
 115
 116   unsigned int cpt;
 117   unsigned int id;
 118   xbt_dynar_foreach(bucket->nodes, cpt, id) {
 119     unsigned int distance  = id ^ answer->destination_id;
 120     node_contact_t contact = node_contact_new(id, distance);
 121     xbt_dynar_push(answer->nodes, &contact);
 122     answer->size++;
 123   }
 124 }
 125
 126 /** @brief Returns if the id supplied is in the answer.
 127   * @param id : id we're looking for
 128   */
 129 unsigned int answer_contains(answer_t answer, unsigned int id)
 130 {
 131   unsigned int i = 0;
 132   node_contact_t contact;
 133   xbt_dynar_foreach(answer->nodes, i, contact){
 134     if (id == contact->id) {
 135       return 1;
 136     }
 137   }
 138   return 0;
 139 }
 140
 141 /** @brief Returns if the destination we are trying to find is found
 142   * @param answer the answer
 143   * @return if the destination is found.
 144   */
 145 unsigned int answer_destination_found(answer_t answer)
 146 {
 147   if (xbt_dynar_is_empty(answer->nodes)) {
 148     return 0;
 149   }
 150   node_contact_t contact_tail = xbt_dynar_get_as(answer->nodes, 0, node_contact_t);
 151   return contact_tail->distance == 0;
 152 }