examples/msg/kademlia/answer.c

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