1 files changed, 502 insertions, 0 deletions
diff --git a/tests/ngtcp2_ksl_test.c b/tests/ngtcp2_ksl_test.c
new file mode 100644
index 0000000..54bdd1b
--- /dev/null
+++ b/tests/ngtcp2_ksl_test.c
@@ -0,0 +1,502 @@
+/*
+ * ngtcp2
+ *
+ * Copyright (c) 2018 ngtcp2 contributors
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to
+ * permit persons to whom the Software is furnished to do so, subject to
+ * the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+ * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+ * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+ * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ */
+#include "ngtcp2_ksl_test.h"
+
+#include <CUnit/CUnit.h>
+
+#include "ngtcp2_ksl.h"
+#include "ngtcp2_test_helper.h"
+
+static int less(const ngtcp2_ksl_key *lhs, const ngtcp2_ksl_key *rhs) {
+  return *(int64_t *)lhs < *(int64_t *)rhs;
+}
+
+void test_ngtcp2_ksl_insert(void) {
+  static const int64_t keys[] = {10, 3,  8, 11, 16, 12, 1, 5, 4,
+                                 0,  13, 7, 9,  2,  14, 6, 15};
+  ngtcp2_ksl ksl;
+  const ngtcp2_mem *mem = ngtcp2_mem_default();
+  size_t i;
+  ngtcp2_ksl_it it;
+  int64_t k;
+
+  ngtcp2_ksl_init(&ksl, less, sizeof(int64_t), mem);
+
+  for (i = 0; i < ngtcp2_arraylen(keys); ++i) {
+    CU_ASSERT(0 == ngtcp2_ksl_insert(&ksl, NULL, &keys[i], NULL));
+    it = ngtcp2_ksl_lower_bound(&ksl, &keys[i]);
+
+    CU_ASSERT(keys[i] == *(int64_t *)ngtcp2_ksl_it_key(&it));
+  }
+
+  for (i = 0; i < ngtcp2_arraylen(keys); ++i) {
+    CU_ASSERT(0 == ngtcp2_ksl_remove(&ksl, NULL, &keys[i]));
+    it = ngtcp2_ksl_lower_bound(&ksl, &keys[i]);
+    if (!ngtcp2_ksl_it_end(&it)) {
+      CU_ASSERT(keys[i] < *(int64_t *)ngtcp2_ksl_it_key(&it));
+    }
+  }
+
+  ngtcp2_ksl_free(&ksl);
+
+  /* check the case that the right end range is removed */
+  ngtcp2_ksl_init(&ksl, less, sizeof(int64_t), mem);
+
+  for (i = 0; i < 32; ++i) {
+    k = (int64_t)i;
+    CU_ASSERT(0 == ngtcp2_ksl_insert(&ksl, NULL, &k, NULL));
+  }
+
+  /* Removing 15 which is the last node in a blk. */
+  k = 15;
+  CU_ASSERT(0 == ngtcp2_ksl_remove(&ksl, &it, &k));
+
+  CU_ASSERT(16 == *(int64_t *)ngtcp2_ksl_it_key(&it));
+
+  /* Insert 15 again works */
+  CU_ASSERT(0 == ngtcp2_ksl_insert(&ksl, NULL, &k, NULL));
+
+  k = 15;
+  it = ngtcp2_ksl_lower_bound(&ksl, &k);
+
+  CU_ASSERT(15 == *(int64_t *)ngtcp2_ksl_it_key(&it));
+
+  ngtcp2_ksl_free(&ksl);
+
+  /* Check the case that the intermediate node contains smaller key
+     than ancestor node.  Make sure that inserting key larger than
+     that still works.*/
+  ngtcp2_ksl_init(&ksl, less, sizeof(int64_t), mem);
+
+  for (i = 0; i < 760; ++i) {
+    k = (int64_t)i;
+    CU_ASSERT(0 == ngtcp2_ksl_insert(&ksl, NULL, &k, NULL));
+  }
+
+  k = 255;
+  CU_ASSERT(0 == ngtcp2_ksl_remove(&ksl, NULL, &k));
+  k = 254;
+  CU_ASSERT(0 == ngtcp2_ksl_remove(&ksl, NULL, &k));
+  k = 253;
+  CU_ASSERT(0 == ngtcp2_ksl_remove(&ksl, NULL, &k));
+
+  k = 253;
+  CU_ASSERT(0 == ngtcp2_ksl_insert(&ksl, NULL, &k, NULL));
+  it = ngtcp2_ksl_lower_bound(&ksl, &k);
+
+  CU_ASSERT(253 == *(int64_t *)ngtcp2_ksl_it_key(&it));
+
+  ngtcp2_ksl_free(&ksl);
+
+  /* check merge node (head) */
+  ngtcp2_ksl_init(&ksl, less, sizeof(int64_t), mem);
+
+  for (i = 0; i < 32; ++i) {
+    k = (int64_t)i;
+    CU_ASSERT(0 == ngtcp2_ksl_insert(&ksl, NULL, &k, NULL));
+  }
+
+  /* Removing these 3 nodes kicks merging 2 nodes under head */
+  k = 15;
+  CU_ASSERT(0 == ngtcp2_ksl_remove(&ksl, NULL, &k));
+  k = 14;
+  CU_ASSERT(0 == ngtcp2_ksl_remove(&ksl, NULL, &k));
+  k = 13;
+  CU_ASSERT(0 == ngtcp2_ksl_remove(&ksl, NULL, &k));
+
+  CU_ASSERT(29 == ksl.head->n);
+
+  ngtcp2_ksl_free(&ksl);
+
+  /* check merge node (non head) */
+  ngtcp2_ksl_init(&ksl, less, sizeof(int64_t), mem);
+
+  for (i = 0; i < 32 + 18; ++i) {
+    k = (int64_t)i;
+    CU_ASSERT(0 == ngtcp2_ksl_insert(&ksl, NULL, &k, NULL));
+  }
+
+  /* Removing these 3 nodes kicks merging 2 nodes */
+  k = 15;
+  CU_ASSERT(0 == ngtcp2_ksl_remove(&ksl, NULL, &k));
+  k = 14;
+  CU_ASSERT(0 == ngtcp2_ksl_remove(&ksl, NULL, &k));
+  k = 13;
+  CU_ASSERT(0 == ngtcp2_ksl_remove(&ksl, NULL, &k));
+
+  CU_ASSERT(2 == ksl.head->n);
+  CU_ASSERT(29 == ngtcp2_ksl_nth_node(&ksl, ksl.head, 0)->blk->n);
+  CU_ASSERT(18 == ngtcp2_ksl_nth_node(&ksl, ksl.head, 1)->blk->n);
+
+  ngtcp2_ksl_free(&ksl);
+
+  /* Iterate backwards */
+  ngtcp2_ksl_init(&ksl, less, sizeof(int64_t), mem);
+
+  /* split nodes */
+  for (i = 0; i < 100; ++i) {
+    k = (int64_t)i;
+    CU_ASSERT(0 == ngtcp2_ksl_insert(&ksl, NULL, &k, NULL));
+  }
+
+  /* merge nodes */
+  for (i = 0; i < 50; ++i) {
+    k = (int64_t)i;
+    CU_ASSERT(0 == ngtcp2_ksl_remove(&ksl, NULL, &k));
+  }
+
+  i = 99;
+  for (it = ngtcp2_ksl_end(&ksl); !ngtcp2_ksl_it_begin(&it);) {
+    ngtcp2_ksl_it_prev(&it);
+
+    CU_ASSERT((int64_t)i-- == *(int64_t *)ngtcp2_ksl_it_key(&it));
+  }
+
+  /* head only */
+  for (i = 50; i < 88; ++i) {
+    k = (int64_t)i;
+    CU_ASSERT(0 == ngtcp2_ksl_remove(&ksl, NULL, &k));
+  }
+
+  i = 99;
+  for (it = ngtcp2_ksl_end(&ksl); !ngtcp2_ksl_it_begin(&it);) {
+    ngtcp2_ksl_it_prev(&it);
+
+    CU_ASSERT((int64_t)i-- == *(int64_t *)ngtcp2_ksl_it_key(&it));
+  }
+
+  ngtcp2_ksl_free(&ksl);
+}
+
+void test_ngtcp2_ksl_clear(void) {
+  ngtcp2_ksl ksl;
+  const ngtcp2_mem *mem = ngtcp2_mem_default();
+  ngtcp2_ksl_it it;
+  size_t i;
+  int64_t k;
+
+  ngtcp2_ksl_init(&ksl, less, sizeof(int64_t), mem);
+
+  for (i = 0; i < 100; ++i) {
+    k = (int64_t)i;
+    CU_ASSERT(0 == ngtcp2_ksl_insert(&ksl, NULL, &k, NULL));
+  }
+
+  ngtcp2_ksl_clear(&ksl);
+
+  CU_ASSERT(0 == ngtcp2_ksl_len(&ksl));
+
+  it = ngtcp2_ksl_begin(&ksl);
+
+  CU_ASSERT(ngtcp2_ksl_it_end(&it));
+
+  it = ngtcp2_ksl_end(&ksl);
+
+  CU_ASSERT(ngtcp2_ksl_it_end(&it));
+
+  ngtcp2_ksl_free(&ksl);
+}
+
+void test_ngtcp2_ksl_range(void) {
+  static const ngtcp2_range keys[] = {
+      {10, 11},   {3, 4},     {8, 9},     {11, 12},   {16, 17},   {12, 13},
+      {1, 2},     {5, 6},     {4, 5},     {0, 1},     {13, 14},   {7, 8},
+      {9, 10},    {2, 3},     {14, 15},   {6, 7},     {15, 16},   {17, 18},
+      {18, 19},   {19, 20},   {20, 21},   {202, 203}, {203, 204}, {204, 205},
+      {205, 206}, {206, 207}, {207, 208}, {208, 209}, {209, 210}, {210, 211},
+      {211, 212}, {212, 213}, {213, 214}, {214, 215}, {215, 216}};
+  ngtcp2_ksl ksl;
+  const ngtcp2_mem *mem = ngtcp2_mem_default();
+  size_t i;
+  ngtcp2_range r;
+  ngtcp2_ksl_it it;
+  ngtcp2_ksl_node *node;
+
+  ngtcp2_ksl_init(&ksl, ngtcp2_ksl_range_compar, sizeof(ngtcp2_range), mem);
+
+  for (i = 0; i < ngtcp2_arraylen(keys); ++i) {
+    CU_ASSERT(0 == ngtcp2_ksl_insert(&ksl, NULL, &keys[i], NULL));
+    it = ngtcp2_ksl_lower_bound_compar(&ksl, &keys[i],
+                                       ngtcp2_ksl_range_exclusive_compar);
+    r = *(ngtcp2_range *)ngtcp2_ksl_it_key(&it);
+
+    CU_ASSERT(ngtcp2_range_eq(&keys[i], &r));
+  }
+
+  for (i = 0; i < ngtcp2_arraylen(keys); ++i) {
+    CU_ASSERT(0 == ngtcp2_ksl_remove(&ksl, NULL, &keys[i]));
+    it = ngtcp2_ksl_lower_bound_compar(&ksl, &keys[i],
+                                       ngtcp2_ksl_range_exclusive_compar);
+
+    if (!ngtcp2_ksl_it_end(&it)) {
+      r = *(ngtcp2_range *)ngtcp2_ksl_it_key(&it);
+
+      CU_ASSERT(keys[i].end <= r.begin);
+    }
+  }
+
+  ngtcp2_ksl_free(&ksl);
+
+  /* check merge node (head) */
+  ngtcp2_ksl_init(&ksl, ngtcp2_ksl_range_compar, sizeof(ngtcp2_range), mem);
+
+  for (i = 0; i < 32; ++i) {
+    ngtcp2_range_init(&r, i, i + 1);
+    CU_ASSERT(0 == ngtcp2_ksl_insert(&ksl, NULL, &r, NULL));
+  }
+
+  /* Removing these 3 nodes kicks merging 2 nodes under head */
+  ngtcp2_range_init(&r, 13, 14);
+  CU_ASSERT(0 == ngtcp2_ksl_remove(&ksl, NULL, &r));
+
+  ngtcp2_range_init(&r, 14, 15);
+  CU_ASSERT(0 == ngtcp2_ksl_remove(&ksl, NULL, &r));
+
+  ngtcp2_range_init(&r, 15, 16);
+  CU_ASSERT(0 == ngtcp2_ksl_remove(&ksl, NULL, &r));
+
+  CU_ASSERT(29 == ksl.head->n);
+
+  ngtcp2_ksl_free(&ksl);
+
+  /* check merge node (non head) */
+  ngtcp2_ksl_init(&ksl, ngtcp2_ksl_range_compar, sizeof(ngtcp2_range), mem);
+
+  for (i = 0; i < 32 + 18; ++i) {
+    ngtcp2_range_init(&r, i, i + 1);
+    CU_ASSERT(0 == ngtcp2_ksl_insert(&ksl, NULL, &r, NULL));
+  }
+
+  /* Removing these 3 nodes kicks merging 2 nodes */
+  ngtcp2_range_init(&r, 13, 14);
+  CU_ASSERT(0 == ngtcp2_ksl_remove(&ksl, NULL, &r));
+
+  ngtcp2_range_init(&r, 14, 15);
+  CU_ASSERT(0 == ngtcp2_ksl_remove(&ksl, NULL, &r));
+
+  ngtcp2_range_init(&r, 15, 16);
+  CU_ASSERT(0 == ngtcp2_ksl_remove(&ksl, NULL, &r));
+
+  CU_ASSERT(2 == ksl.head->n);
+  CU_ASSERT(29 == ngtcp2_ksl_nth_node(&ksl, ksl.head, 0)->blk->n);
+  CU_ASSERT(18 == ngtcp2_ksl_nth_node(&ksl, ksl.head, 1)->blk->n);
+
+  ngtcp2_ksl_free(&ksl);
+
+  /* shift_left */
+  ngtcp2_ksl_init(&ksl, ngtcp2_ksl_range_compar, sizeof(ngtcp2_range), mem);
+
+  for (i = 1; i < 6400; i += 100) {
+    ngtcp2_range_init(&r, i, i + 1);
+    CU_ASSERT(0 == ngtcp2_ksl_insert(&ksl, NULL, &r, NULL));
+  }
+
+  ngtcp2_range_init(&r, 1501, 1502);
+  CU_ASSERT(0 == ngtcp2_ksl_remove(&ksl, NULL, &r));
+  ngtcp2_range_init(&r, 1401, 1402);
+  CU_ASSERT(0 == ngtcp2_ksl_remove(&ksl, NULL, &r));
+
+  r = *(ngtcp2_range *)(void *)ngtcp2_ksl_nth_node(
+           &ksl, ngtcp2_ksl_nth_node(&ksl, ksl.head, 1)->blk, 0)
+           ->key;
+
+  CU_ASSERT(1701 == r.begin);
+
+  ngtcp2_ksl_free(&ksl);
+
+  /* shift_right */
+  ngtcp2_ksl_init(&ksl, ngtcp2_ksl_range_compar, sizeof(ngtcp2_range), mem);
+
+  for (i = 0; i < 32; ++i) {
+    ngtcp2_range_init(&r, i, i + 1);
+    CU_ASSERT(0 == ngtcp2_ksl_insert(&ksl, NULL, &r, NULL));
+  }
+
+  ngtcp2_range_init(&r, 17, 18);
+  CU_ASSERT(0 == ngtcp2_ksl_remove(&ksl, NULL, &r));
+  ngtcp2_range_init(&r, 16, 17);
+  CU_ASSERT(0 == ngtcp2_ksl_remove(&ksl, NULL, &r));
+
+  node = ngtcp2_ksl_nth_node(&ksl, ksl.head, 0);
+  r = *(ngtcp2_range *)(void *)ngtcp2_ksl_nth_node(&ksl, node->blk,
+                                                   node->blk->n - 1)
+           ->key;
+
+  CU_ASSERT(14 == r.begin);
+
+  ngtcp2_ksl_free(&ksl);
+}
+
+void test_ngtcp2_ksl_update_key_range(void) {
+  static ngtcp2_range ranges[] = {
+      {0, 5},     {10, 15},   {20, 25},   {30, 35},   {40, 45},   {50, 55},
+      {60, 65},   {70, 75},   {80, 85},   {90, 95},   {100, 105}, {110, 115},
+      {120, 125}, {130, 135}, {140, 145}, {150, 155}, {160, 165}, {170, 175}};
+  ngtcp2_ksl ksl;
+  const ngtcp2_mem *mem = ngtcp2_mem_default();
+  size_t i;
+  ngtcp2_range r;
+  ngtcp2_ksl_it it;
+
+  ngtcp2_ksl_init(&ksl, ngtcp2_ksl_range_compar, sizeof(ngtcp2_range), mem);
+
+  for (i = 0; i < ngtcp2_arraylen(ranges); ++i) {
+    CU_ASSERT(0 == ngtcp2_ksl_insert(&ksl, NULL, &ranges[i], NULL));
+  }
+
+  r.begin = 70;
+  r.end = 72;
+  ngtcp2_ksl_update_key(&ksl, &ranges[7], &r);
+
+  r.begin = 73;
+  r.end = 74;
+  CU_ASSERT(0 == ngtcp2_ksl_insert(&ksl, NULL, &r, NULL));
+
+  r.begin = 74;
+  r.end = 75;
+  CU_ASSERT(0 == ngtcp2_ksl_insert(&ksl, NULL, &r, NULL));
+
+  r.begin = 74;
+  r.end = 75;
+  it = ngtcp2_ksl_lower_bound_compar(&ksl, &r,
+                                     ngtcp2_ksl_range_exclusive_compar);
+
+  r = *(ngtcp2_range *)ngtcp2_ksl_it_key(&it);
+
+  CU_ASSERT(r.begin == 74);
+  CU_ASSERT(r.end == 75);
+
+  ngtcp2_ksl_free(&ksl);
+}
+
+static void shuffle(int64_t *a, size_t n) {
+  size_t i, j;
+  int64_t t;
+
+  for (i = n - 1; i >= 1; --i) {
+    j = (size_t)((double)(i + 1) * rand() / (RAND_MAX + 1.0));
+    t = a[j];
+    a[j] = a[i];
+    a[i] = t;
+  }
+}
+
+void test_ngtcp2_ksl_dup(void) {
+  static int64_t keys[16000];
+  size_t i, j;
+  ngtcp2_ksl ksl;
+  const ngtcp2_mem *mem = ngtcp2_mem_default();
+  ngtcp2_ksl_it it;
+
+  for (i = 0; i < ngtcp2_arraylen(keys); ++i) {
+    keys[i] = (int64_t)i;
+  }
+
+  for (j = 0; j < 10; ++j) {
+    ngtcp2_ksl_init(&ksl, less, sizeof(int64_t), mem);
+
+    shuffle(keys, ngtcp2_arraylen(keys));
+
+    for (i = 0; i < ngtcp2_arraylen(keys); ++i) {
+      CU_ASSERT(0 == ngtcp2_ksl_insert(&ksl, NULL, &keys[i], NULL));
+      CU_ASSERT(NGTCP2_ERR_INVALID_ARGUMENT ==
+                ngtcp2_ksl_insert(&ksl, NULL, &keys[i], NULL));
+
+      it = ngtcp2_ksl_lower_bound(&ksl, &keys[i]);
+
+      CU_ASSERT(keys[i] == *(int64_t *)ngtcp2_ksl_it_key(&it));
+    }
+
+    shuffle(keys, ngtcp2_arraylen(keys));
+
+    for (i = 0; i < ngtcp2_arraylen(keys); ++i) {
+      CU_ASSERT(0 == ngtcp2_ksl_remove(&ksl, NULL, &keys[i]));
+
+      it = ngtcp2_ksl_begin(&ksl);
+
+      CU_ASSERT(NGTCP2_ERR_INVALID_ARGUMENT ==
+                ngtcp2_ksl_remove(&ksl, &it, &keys[i]));
+      CU_ASSERT(ngtcp2_ksl_it_end(&it));
+
+      it = ngtcp2_ksl_lower_bound(&ksl, &keys[i]);
+
+      CU_ASSERT(ngtcp2_ksl_it_end(&it) ||
+                keys[i] < *(int64_t *)ngtcp2_ksl_it_key(&it));
+
+      CU_ASSERT(0 == ngtcp2_ksl_insert(&ksl, NULL, &keys[i], NULL));
+
+      it = ngtcp2_ksl_begin(&ksl);
+
+      CU_ASSERT(NGTCP2_ERR_INVALID_ARGUMENT ==
+                ngtcp2_ksl_insert(&ksl, &it, &keys[i], NULL));
+      CU_ASSERT(ngtcp2_ksl_it_end(&it));
+
+      it = ngtcp2_ksl_lower_bound(&ksl, &keys[i]);
+      CU_ASSERT(keys[i] == *(int64_t *)ngtcp2_ksl_it_key(&it));
+    }
+
+    ngtcp2_ksl_free(&ksl);
+  }
+}
+
+void test_ngtcp2_ksl_remove_hint(void) {
+  static int64_t keys[16000];
+  ngtcp2_ksl ksl;
+  const ngtcp2_mem *mem = ngtcp2_mem_default();
+  ngtcp2_ksl_it it;
+  size_t i, j;
+
+  for (i = 0; i < ngtcp2_arraylen(keys); ++i) {
+    keys[i] = (int64_t)i;
+  }
+
+  for (j = 0; j < 10; ++j) {
+    ngtcp2_ksl_init(&ksl, less, sizeof(int64_t), mem);
+
+    shuffle(keys, ngtcp2_arraylen(keys));
+
+    for (i = 0; i < ngtcp2_arraylen(keys); ++i) {
+      CU_ASSERT(0 == ngtcp2_ksl_insert(&ksl, NULL, &keys[i], NULL));
+    }
+
+    shuffle(keys, ngtcp2_arraylen(keys));
+
+    for (i = 0; i < ngtcp2_arraylen(keys); ++i) {
+      it = ngtcp2_ksl_lower_bound(&ksl, &keys[i]);
+
+      CU_ASSERT(!ngtcp2_ksl_it_end(&it));
+      CU_ASSERT(keys[i] == *(int64_t *)ngtcp2_ksl_it_key(&it));
+      CU_ASSERT(0 == ngtcp2_ksl_remove_hint(&ksl, &it, &it, &keys[i]));
+
+      it = ngtcp2_ksl_lower_bound(&ksl, &keys[i]);
+
+      CU_ASSERT(ngtcp2_ksl_it_end(&it) ||
+                keys[i] != *(int64_t *)ngtcp2_ksl_it_key(&it));
+      CU_ASSERT(ngtcp2_arraylen(keys) - i - 1 == ngtcp2_ksl_len(&ksl));
+    }
+
+    ngtcp2_ksl_free(&ksl);
+  }
+}