examples/msg/kademlia/routing_table.c

   1 /* Copyright (c) 2012-2015. 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 "routing_table.h"
   8 #include "node.h"
   9 #include "simgrid/msg.h"
  10 #include "xbt/log.h"
  11 #include "xbt/asserts.h"
  12 XBT_LOG_NEW_DEFAULT_CATEGORY(msg_kademlia_routing_table,
  13                              "Messages specific for this msg example");
  14 /**
  15   * \brief Initialization of a node routing table.
  16   */
  17 routing_table_t routing_table_init(unsigned int node_id)
  18 {
  19   unsigned int i;
  20   routing_table_t table = xbt_new(s_routing_table_t, 1);
  21   table->buckets = xbt_new(s_bucket_t, identifier_size + 1);
  22   for (i = 0; i < identifier_size + 1; i++) {
  23     table->buckets[i].nodes = xbt_dynar_new(sizeof(unsigned int), NULL);
  24     table->buckets[i].id = i;
  25   }
  26   table->id = node_id;
  27   return table;
  28 }
  29
  30 /**
  31   * \brief Frees the routing table
  32   */
  33 void routing_table_free(routing_table_t table)
  34 {
  35   unsigned int i;
  36   //Free the buckets.
  37   for (i = 0; i <= identifier_size; i++) {
  38     xbt_dynar_free(&table->buckets[i].nodes);
  39   }
  40   xbt_free(table->buckets);
  41   xbt_free(table);
  42 }
  43
  44 /**
  45   * Returns if the routing table contains the id.
  46   */
  47 unsigned int routing_table_contains(routing_table_t table, unsigned int node_id)
  48 {
  49   bucket_t bucket = routing_table_find_bucket(table, node_id);
  50   return bucket_contains(bucket, node_id);
  51 }
  52
  53 /**
  54   * @brief prints the routing table, to debug stuff.
  55   */
  56 void routing_table_print(routing_table_t table)
  57 {
  58   unsigned int i, j, value;
  59   XBT_INFO("Routing table of %08x:", table->id);
  60
  61   for (i = 0; i <= identifier_size; i++) {
  62     if (!xbt_dynar_is_empty(table->buckets[i].nodes)) {
  63       XBT_INFO("Bucket number %d: ", i);
  64       xbt_dynar_foreach(table->buckets[i].nodes, j, value) {
  65         XBT_INFO("Element %d: %08x", j, value);
  66       }
  67     }
  68   }
  69 }
  70
  71 /**
  72   * Finds an identifier in a bucket and returns its position
  73   * or returns -1 if it doesn't exists
  74   * @param bucket the bucket in which we try to find our identifier
  75   * @param id the id
  76   */
  77 unsigned int bucket_find_id(bucket_t bucket, unsigned int id)
  78 {
  79   unsigned int i, length = xbt_dynar_length(bucket->nodes);
  80   for (i = 0; i < length; i++) {        //TODO: Use foreach maybe ?
  81     if (id == xbt_dynar_get_as(bucket->nodes, i, unsigned int)) {
  82       return i;
  83     }
  84   }
  85   return -1;
  86 }
  87
  88 /**
  89   * Returns if the bucket contains an identifier.
  90   */
  91 unsigned int bucket_contains(bucket_t bucket, unsigned int id)
  92 {
  93   unsigned int length = xbt_dynar_length(bucket->nodes), i = 0;
  94   for (i = 0; i < length; i++) {
  95     if (id == xbt_dynar_get_as(bucket->nodes, i, unsigned int)) {
  96       return 1;
  97     }
  98   }
  99   return 0;
 100 }
 101
 102 /**
 103   * Fins the corresponding bucket in a routing table for a given identifier
 104   * @param table the routing table
 105   * @param id the identifier
 106   * @return the bucket in which the the identifier would be.
 107   */
 108 bucket_t routing_table_find_bucket(routing_table_t table, unsigned int id)
 109 {
 110   unsigned int xor_number = table->id ^ id;
 111   unsigned int prefix = get_node_prefix(xor_number, identifier_size);
 112   xbt_assert(prefix >= 0
 113              && prefix <= identifier_size,
 114              "Tried to return a  bucket that doesn't exist.");
 115   bucket_t bucket = &table->buckets[prefix];
 116   return bucket;
 117 }