Clean up peer re-distribution between single bucket vectors and bucket lists, add tests

2 files changed, 107 insertions, 5 deletions

diff --git a/ot_vector.c b/ot_vector.c
index c4cd171..7f18246 100644
--- a/ot_vector.c
+++ b/ot_vector.c
@@ -8,7 +8,6 @@
 #include <stdint.h>
 #include <stdlib.h>
 #include <string.h>
-#include <strings.h>
 
 /* Opentracker */
 #include "trackerlogic.h"
@@ -174,7 +173,7 @@ void vector_clean_list(ot_vector *vector, size_t num_buckets) {
 }
 
 void vector_redistribute_buckets(ot_peerlist *peer_list, size_t peer_size) {
-  size_t     tmp, bucket, bucket_size_new, num_buckets_new, num_buckets_old = 1;
+  size_t     bucket, bucket_size_new, num_buckets_new, num_buckets_old = 1;
   ot_vector *bucket_list_new, *bucket_list_old = &peer_list->peers;
   int (*sort_func)(const void *, const void *) = peer_size == OT_PEER_SIZE6 ? &vector_compare_peer6 : &vector_compare_peer4;
 
@@ -205,11 +204,10 @@ void vector_redistribute_buckets(ot_peerlist *peer_list, size_t peer_size) {
   bucket_list_new = malloc(num_buckets_new * sizeof(ot_vector));
   if (!bucket_list_new)
     return;
-  bzero(bucket_list_new, num_buckets_new * sizeof(ot_vector));
+  memset(bucket_list_new, 0, num_buckets_new * sizeof(ot_vector));
 
-  tmp             = peer_list->peer_count / num_buckets_new;
   bucket_size_new = OT_VECTOR_MIN_MEMBERS;
-  while (bucket_size_new < tmp)
+  while (bucket_size_new * num_buckets_new < peer_list->peer_count)
     bucket_size_new *= OT_VECTOR_GROW_RATIO;
 
   /* preallocate vectors to hold all peers */
diff --git a/tests/t_vector.c b/tests/t_vector.c
index fee336b..a8186b2 100644
--- a/tests/t_vector.c
+++ b/tests/t_vector.c
@@ -4,10 +4,12 @@
    $id$ */
 
 /* System */
+#include <stdint.h>
 #include <stdlib.h>
 #include <string.h>
 
 /* Opentracker */
+#include "ot_vector.h"
 #include "trackerlogic.h"
 #include "test.h"
 
@@ -149,6 +151,105 @@ static void case_insert_compare_prefix(void) {
   free(vector.data);
 }
 
+/* ------------------------------------------------- bucket redistribution */
+
+/* A flat peer list of count distinct v4 peers. The low byte of the index goes
+   into the first address byte, so the peers are distinct but arrive in no
+   particular order: a list generated in ascending order would come back
+   sorted whether or not vector_redistribute_buckets sorted it. */
+static void build_flat_peerlist(ot_peerlist *peer_list, size_t count) {
+  size_t i;
+
+  memset(peer_list, 0, sizeof(*peer_list));
+  peer_list->peers.data  = malloc(count * OT_PEER_SIZE4);
+  peer_list->peers.size  = count;
+  peer_list->peers.space = count;
+  peer_list->peer_count  = count;
+
+  for (i = 0; i < count; ++i) {
+    uint8_t *peer = (uint8_t *)peer_list->peers.data + i * OT_PEER_SIZE4;
+
+    memset(peer, 0, OT_PEER_SIZE4);
+    peer[0] = (uint8_t)i;
+    peer[1] = (uint8_t)(i >> 8);
+    peer[2] = (uint8_t)(i >> 16);
+    peer[3] = 1;
+  }
+}
+
+static void case_redistribute_holds_every_peer(void) {
+  const size_t count = 513;
+  ot_peerlist  peer_list;
+  size_t       bucket, total_size = 0, empty = 0, largest = 0;
+  ot_vector   *buckets;
+
+  test_case("a peer list past the threshold is split into buckets");
+  build_flat_peerlist(&peer_list, count);
+  CHECK(peer_list.peers.data != NULL);
+  vector_redistribute_buckets(&peer_list, OT_PEER_SIZE4);
+  CHECK_INT(OT_PEERLIST_HASBUCKETS(&peer_list), 1);
+  CHECK_INT(peer_list.peers.size, 16);
+
+  buckets = peer_list.peers.data;
+  for (bucket = 0; bucket < peer_list.peers.size; ++bucket) {
+    total_size += buckets[bucket].size;
+    if (!buckets[bucket].size)
+      ++empty;
+    if (buckets[bucket].size > largest)
+      largest = buckets[bucket].size;
+  }
+
+  test_case("no peer is lost on the way");
+  CHECK_INT(total_size, count);
+
+  /* The point of the exercise is that a lookup only searches one bucket, so
+     a hash that piled everything into one would defeat it. The input and the
+     hash are both fixed, so this is not a matter of luck. */
+  test_case("and they are spread over the buckets rather than piled up");
+  CHECK_INT(empty, 0);
+  CHECK(largest < count / 2);
+
+  vector_clean_list(peer_list.peers.data, peer_list.peers.size);
+}
+
+static void case_redistribute_sorts_each_bucket(void) {
+  const size_t count = 1000;
+  ot_peerlist  peer_list;
+  size_t       bucket, i, out_of_order = 0;
+  ot_vector   *buckets;
+
+  test_case("every bucket comes back sorted, so bsearch can be used on it");
+  build_flat_peerlist(&peer_list, count);
+  CHECK(peer_list.peers.data != NULL);
+  vector_redistribute_buckets(&peer_list, OT_PEER_SIZE4);
+  CHECK_INT(OT_PEERLIST_HASBUCKETS(&peer_list), 1);
+
+  buckets = peer_list.peers.data;
+  for (bucket = 0; bucket < peer_list.peers.size; ++bucket)
+    for (i = 1; i < buckets[bucket].size; ++i) {
+      const uint8_t *prev = (uint8_t *)buckets[bucket].data + (i - 1) * OT_PEER_SIZE4;
+      const uint8_t *next = (uint8_t *)buckets[bucket].data + i * OT_PEER_SIZE4;
+
+      if (memcmp(prev, next, OT_PEER_COMPARE_SIZE4) >= 0)
+        ++out_of_order;
+    }
+  CHECK_INT(out_of_order, 0);
+
+  vector_clean_list(peer_list.peers.data, peer_list.peers.size);
+}
+
+static void case_redistribute_below_threshold(void) {
+  ot_peerlist peer_list;
+
+  test_case("a small peer list is left flat");
+  build_flat_peerlist(&peer_list, 100);
+  CHECK(peer_list.peers.data != NULL);
+  vector_redistribute_buckets(&peer_list, OT_PEER_SIZE4);
+  CHECK_INT(OT_PEERLIST_HASBUCKETS(&peer_list), 0);
+  CHECK_INT(peer_list.peers.size, 100);
+  free(peer_list.peers.data);
+}
+
 void test_vector(void) {
   case_search_finds_member();
   case_search_finds_first_and_last();
@@ -158,4 +259,7 @@ void test_vector(void) {
   case_insert_keeps_order();
   case_insert_finds_existing();
   case_insert_compare_prefix();
+  case_redistribute_holds_every_peer();
+  case_redistribute_sorts_each_bucket();
+  case_redistribute_below_threshold();
 }