examples/msg/kademlia/answer.c

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