Use more-or-equal (some machines are fast enough)

[oweals/gnunet.git] / src / testbed / testbed_api_topology.c

diff --git a/src/testbed/testbed_api_topology.c b/src/testbed/testbed_api_topology.c
index 374e42ad41a5406235a3e85ff8858e84806724dd..8d8883c96420e7a92ecfa2b75a612f92277408d3 100644 (file)
--- a/src/testbed/testbed_api_topology.c
+++ b/src/testbed/testbed_api_topology.c
@@ -89,7 +89,7 @@ struct RetryListEntry
    * the prev pointer for the DLL
    */
   struct RetryListEntry *prev;
-  
+
   /**
    * The link to be retired
    */
@@ -136,7 +136,7 @@ struct TopologyContext
    * DLL tail for retry list
    */
   struct RetryListEntry *rl_tail;
-  
+
   /**
    * The number of peers
    */
@@ -292,7 +292,7 @@ overlay_link_completed (void *cls, struct GNUNET_TESTBED_Operation *op,
     tc->nlinks = 0;
     while (NULL != (retry_entry = tc->rl_head))
     {
-      link = retry_entry->link;      
+      link = retry_entry->link;
       link->op =
           GNUNET_TESTBED_overlay_connect (tc->op_cls, &overlay_link_completed,
                                           link, tc->peers[link->A],
@@ -596,51 +596,82 @@ gen_topo_random (struct TopologyContext *tc, unsigned int links, int append)
 static void
 gen_scale_free (struct TopologyContext *tc, uint16_t cap, uint8_t m)
 {
+  unsigned int *deg;
+  unsigned int *etab;
+  unsigned int *used;
+  unsigned int etaboff;
   unsigned int cnt;
   unsigned int cnt2;
   unsigned int peer;
-  unsigned int *etab;
-  unsigned int *used;
+  unsigned int random_peer;
   unsigned int links;
-  unsigned int random;
+  unsigned int off;
+  unsigned int redo_threshold;
 
-  links = 0;
+  etaboff = 0;
   tc->link_array_size = tc->num_peers * m;
   tc->link_array = GNUNET_malloc_large (sizeof (struct OverlayLink) *
                                         tc->link_array_size);
   etab = GNUNET_malloc_large (sizeof (unsigned int) * 2 * tc->link_array_size);
-
+  deg = GNUNET_malloc (sizeof (unsigned int) * tc->num_peers);
   used = GNUNET_malloc (sizeof (unsigned int) * m);
-
-  make_link (&tc->link_array[0], 0, 1, tc); /* Initially connect peer 1 to peer 0 */
-  etab[2 * links] = 0;
-  etab[(2 * links) + 1] = 1;
+  /* start by connecting peer 1 to peer 0 */
+  make_link (&tc->link_array[0], 0, 1, tc);
+  deg[0]++;
+  deg[1]++;
+  etab[etaboff++] = 0;
+  etab[etaboff++] = 1;
   links = 1;
   for (peer = 2; peer < tc->num_peers; peer++)
   {
+    if (cap < deg[peer])
+      continue;
     for (cnt = 0; cnt < GNUNET_MIN (peer, m); cnt++)
     {
+      redo_threshold = 0;
     redo:
-      random = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, (2 * links)
-                                         + cnt);
+      off = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, etaboff);
+      random_peer = etab[off];
+      if (cap < deg[random_peer])
+      {
+        if (++redo_threshold > GNUNET_MAX (1, cap / 2))
+        {
+          redo_threshold = 0;
+          off = 0;
+          for (cnt2 = 0; cnt2 < etaboff; cnt2++)
+          {
+            if (random_peer == etab[cnt2])
+            {
+              off++;
+              continue;
+            }
+            etab[cnt2 - off] = etab[cnt2];
+          }
+          etaboff -= off;
+        }
+        goto redo;
+      }
       for (cnt2 = 0; cnt2 < cnt; cnt2++)
-        if (etab[random] == used[cnt2])
+        if (random_peer == used[cnt2])
           goto redo;
-      make_link (&tc->link_array[links + cnt], etab[random], peer, tc);
-      etab[(2 * links) + cnt] = etab[random];
-      used[cnt] = etab[random];
+      make_link (&tc->link_array[links + cnt], random_peer, peer, tc);
+      deg[random_peer]++;
+      deg[peer]++;
+      used[cnt] = random_peer;
     }
     for (cnt = 0; cnt < GNUNET_MIN (peer, m); cnt++)
     {
-      etab[(2 * links) + cnt + 1] = peer;
+      etab[etaboff++] = used[cnt];
+      etab[etaboff++] = peer;
     }
     links += GNUNET_MIN (peer, m);
   }
   GNUNET_free (etab);
   GNUNET_free (used);
+  GNUNET_free (deg);
   GNUNET_assert (links <= tc->link_array_size);
   tc->link_array_size = links;
-  tc->link_array = 
+  tc->link_array =
       GNUNET_realloc (tc->link_array,
                       sizeof (struct OverlayLink) * tc->link_array_size);
 }
@@ -950,7 +981,7 @@ GNUNET_TESTBED_overlay_configure_topology_va (void *op_cls,
     {
       uint16_t cap;
       uint8_t m;
-      
+
       cap = (uint16_t) va_arg (va, unsigned int);
       m = (uint8_t) va_arg (va, unsigned int);
       gen_scale_free (tc, cap, m);
@@ -1042,7 +1073,7 @@ GNUNET_TESTBED_overlay_configure_topology (void *op_cls,
   GNUNET_assert (topo < GNUNET_TESTBED_TOPOLOGY_OPTION_END);
   va_start (vargs, topo);
   op = GNUNET_TESTBED_overlay_configure_topology_va (op_cls, num_peers, peers,
-                                                     max_connections, 
+                                                     max_connections,
                                                      comp_cb, comp_cb_cls,
                                                      topo,
                                                      vargs);