examples/msg/kademlia/answer.c

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