Initial checkin of gRPC to third_party/

third_party/grpc/test/core/iomgr/timer_heap_test.c

Index: third_party/grpc/test/core/iomgr/timer_heap_test.c
diff --git a/third_party/grpc/test/core/iomgr/timer_heap_test.c b/third_party/grpc/test/core/iomgr/timer_heap_test.c
new file mode 100644
index 0000000000000000000000000000000000000000..cd34696f7ddeb15d8be27a90d48e21bb3a316dfd
--- /dev/null
+++ b/third_party/grpc/test/core/iomgr/timer_heap_test.c
@@ -0,0 +1,315 @@
+/*
+ *
+ * Copyright 2015-2016, Google Inc.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ *     * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *     * Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following disclaimer
+ * in the documentation and/or other materials provided with the
+ * distribution.
+ *     * Neither the name of Google Inc. nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ */
+
+#include "src/core/iomgr/timer_heap.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+#include <grpc/support/alloc.h>
+#include <grpc/support/log.h>
+#include <grpc/support/useful.h>
+
+#include "test/core/util/test_config.h"
+
+static gpr_timespec random_deadline(void) {
+  gpr_timespec ts;
+  ts.tv_sec = rand();
+  ts.tv_nsec = rand();
+  ts.clock_type = GPR_CLOCK_REALTIME;
+  return ts;
+}
+
+static grpc_timer *create_test_elements(size_t num_elements) {
+  grpc_timer *elems = gpr_malloc(num_elements * sizeof(grpc_timer));
+  size_t i;
+  for (i = 0; i < num_elements; i++) {
+    elems[i].deadline = random_deadline();
+  }
+  return elems;
+}
+
+static int contains(grpc_timer_heap *pq, grpc_timer *el) {
+  size_t i;
+  for (i = 0; i < pq->timer_count; i++) {
+    if (pq->timers[i] == el) return 1;
+  }
+  return 0;
+}
+
+static void check_valid(grpc_timer_heap *pq) {
+  size_t i;
+  for (i = 0; i < pq->timer_count; ++i) {
+    size_t left_child = 1u + 2u * i;
+    size_t right_child = left_child + 1u;
+    if (left_child < pq->timer_count) {
+      GPR_ASSERT(gpr_time_cmp(pq->timers[i]->deadline,
+                              pq->timers[left_child]->deadline) <= 0);
+    }
+    if (right_child < pq->timer_count) {
+      GPR_ASSERT(gpr_time_cmp(pq->timers[i]->deadline,
+                              pq->timers[right_child]->deadline) <= 0);
+    }
+  }
+}
+
+/*******************************************************************************
+ * test1
+ */
+
+static void test1(void) {
+  grpc_timer_heap pq;
+  const size_t num_test_elements = 200;
+  const size_t num_test_operations = 10000;
+  size_t i;
+  grpc_timer *test_elements = create_test_elements(num_test_elements);
+  uint8_t *inpq = gpr_malloc(num_test_elements);
+
+  gpr_log(GPR_INFO, "test1");
+
+  grpc_timer_heap_init(&pq);
+  memset(inpq, 0, num_test_elements);
+  GPR_ASSERT(grpc_timer_heap_is_empty(&pq));
+  check_valid(&pq);
+  for (i = 0; i < num_test_elements; ++i) {
+    GPR_ASSERT(!contains(&pq, &test_elements[i]));
+    grpc_timer_heap_add(&pq, &test_elements[i]);
+    check_valid(&pq);
+    GPR_ASSERT(contains(&pq, &test_elements[i]));
+    inpq[i] = 1;
+  }
+  for (i = 0; i < num_test_elements; ++i) {
+    /* Test that check still succeeds even for element that wasn't just
+       inserted. */
+    GPR_ASSERT(contains(&pq, &test_elements[i]));
+  }
+
+  GPR_ASSERT(pq.timer_count == num_test_elements);
+
+  check_valid(&pq);
+
+  for (i = 0; i < num_test_operations; ++i) {
+    size_t elem_num = (size_t)rand() % num_test_elements;
+    grpc_timer *el = &test_elements[elem_num];
+    if (!inpq[elem_num]) { /* not in pq */
+      GPR_ASSERT(!contains(&pq, el));
+      el->deadline = random_deadline();
+      grpc_timer_heap_add(&pq, el);
+      GPR_ASSERT(contains(&pq, el));
+      inpq[elem_num] = 1;
+      check_valid(&pq);
+    } else {
+      GPR_ASSERT(contains(&pq, el));
+      grpc_timer_heap_remove(&pq, el);
+      GPR_ASSERT(!contains(&pq, el));
+      inpq[elem_num] = 0;
+      check_valid(&pq);
+    }
+  }
+
+  grpc_timer_heap_destroy(&pq);
+  gpr_free(test_elements);
+  gpr_free(inpq);
+}
+
+/*******************************************************************************
+ * test2
+ */
+
+typedef struct {
+  grpc_timer elem;
+  bool inserted;
+} elem_struct;
+
+static elem_struct *search_elems(elem_struct *elems, size_t count,
+                                 bool inserted) {
+  size_t *search_order = gpr_malloc(count * sizeof(*search_order));
+  for (size_t i = 0; i < count; i++) {
+    search_order[i] = i;
+  }
+  for (size_t i = 0; i < count * 2; i++) {
+    size_t a = (size_t)rand() % count;
+    size_t b = (size_t)rand() % count;
+    GPR_SWAP(size_t, search_order[a], search_order[b]);
+  }
+  elem_struct *out = NULL;
+  for (size_t i = 0; out == NULL && i < count; i++) {
+    if (elems[search_order[i]].inserted == inserted) {
+      out = &elems[search_order[i]];
+    }
+  }
+  gpr_free(search_order);
+  return out;
+}
+
+static void test2(void) {
+  gpr_log(GPR_INFO, "test2");
+
+  grpc_timer_heap pq;
+
+  elem_struct elems[1000];
+  size_t num_inserted = 0;
+
+  grpc_timer_heap_init(&pq);
+  memset(elems, 0, sizeof(elems));
+
+  for (size_t round = 0; round < 10000; round++) {
+    int r = rand() % 1000;
+    if (r <= 550) {
+      /* 55% of the time we try to add something */
+      elem_struct *el = search_elems(elems, GPR_ARRAY_SIZE(elems), false);
+      if (el != NULL) {
+        el->elem.deadline = random_deadline();
+        grpc_timer_heap_add(&pq, &el->elem);
+        el->inserted = true;
+        num_inserted++;
+        check_valid(&pq);
+      }
+    } else if (r <= 650) {
+      /* 10% of the time we try to remove something */
+      elem_struct *el = search_elems(elems, GPR_ARRAY_SIZE(elems), true);
+      if (el != NULL) {
+        grpc_timer_heap_remove(&pq, &el->elem);
+        el->inserted = false;
+        num_inserted--;
+        check_valid(&pq);
+      }
+    } else {
+      /* the remaining times we pop */
+      if (num_inserted > 0) {
+        grpc_timer *top = grpc_timer_heap_top(&pq);
+        grpc_timer_heap_pop(&pq);
+        for (size_t i = 0; i < GPR_ARRAY_SIZE(elems); i++) {
+          if (top == &elems[i].elem) {
+            GPR_ASSERT(elems[i].inserted);
+            elems[i].inserted = false;
+          }
+        }
+        num_inserted--;
+        check_valid(&pq);
+      }
+    }
+
+    if (num_inserted) {
+      gpr_timespec *min_deadline = NULL;
+      for (size_t i = 0; i < GPR_ARRAY_SIZE(elems); i++) {
+        if (elems[i].inserted) {
+          if (min_deadline == NULL) {
+            min_deadline = &elems[i].elem.deadline;
+          } else {
+            if (gpr_time_cmp(elems[i].elem.deadline, *min_deadline) < 0) {
+              min_deadline = &elems[i].elem.deadline;
+            }
+          }
+        }
+      }
+      GPR_ASSERT(
+          0 == gpr_time_cmp(grpc_timer_heap_top(&pq)->deadline, *min_deadline));
+    }
+  }
+
+  grpc_timer_heap_destroy(&pq);
+}
+
+static void shrink_test(void) {
+  gpr_log(GPR_INFO, "shrink_test");
+
+  grpc_timer_heap pq;
+  size_t i;
+  size_t expected_size;
+
+  /* A large random number to allow for multiple shrinkages, at least 512. */
+  const size_t num_elements = (size_t)rand() % 2000 + 512;
+
+  grpc_timer_heap_init(&pq);
+
+  /* Create a priority queue with many elements.  Make sure the Size() is
+     correct. */
+  for (i = 0; i < num_elements; ++i) {
+    GPR_ASSERT(i == pq.timer_count);
+    grpc_timer_heap_add(&pq, create_test_elements(1));
+  }
+  GPR_ASSERT(num_elements == pq.timer_count);
+
+  /* Remove elements until the Size is 1/4 the original size. */
+  while (pq.timer_count > num_elements / 4) {
+    grpc_timer *const te = pq.timers[pq.timer_count - 1];
+    grpc_timer_heap_remove(&pq, te);
+    gpr_free(te);
+  }
+  GPR_ASSERT(num_elements / 4 == pq.timer_count);
+
+  /* Expect that Capacity is in the right range:
+     Size * 2 <= Capacity <= Size * 4 */
+  GPR_ASSERT(pq.timer_count * 2 <= pq.timer_capacity);
+  GPR_ASSERT(pq.timer_capacity <= pq.timer_count * 4);
+  check_valid(&pq);
+
+  /* Remove the rest of the elements.  Check that the Capacity is not more than
+     4 times the Size and not less than 2 times, but never goes below 16. */
+  expected_size = pq.timer_count;
+  while (pq.timer_count > 0) {
+    const size_t which = (size_t)rand() % pq.timer_count;
+    grpc_timer *te = pq.timers[which];
+    grpc_timer_heap_remove(&pq, te);
+    gpr_free(te);
+    expected_size--;
+    GPR_ASSERT(expected_size == pq.timer_count);
+    GPR_ASSERT(pq.timer_count * 2 <= pq.timer_capacity);
+    if (pq.timer_count >= 8) {
+      GPR_ASSERT(pq.timer_capacity <= pq.timer_count * 4);
+    } else {
+      GPR_ASSERT(16 <= pq.timer_capacity);
+    }
+    check_valid(&pq);
+  }
+
+  GPR_ASSERT(0 == pq.timer_count);
+  GPR_ASSERT(pq.timer_capacity >= 16 && pq.timer_capacity < 32);
+
+  grpc_timer_heap_destroy(&pq);
+}
+
+int main(int argc, char **argv) {
+  int i;
+
+  grpc_test_init(argc, argv);
+
+  for (i = 0; i < 5; i++) {
+    test1();
+    test2();
+    shrink_test();
+  }
+
+  return 0;
+}