Merging upstream version 3.3.9.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 102 insertions, 97 deletions

diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_ksl.c b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_ksl.c
index a7284bd..df2b640 100644
--- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_ksl.c
+++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_ksl.c
@@ -38,8 +38,10 @@ static ngtcp2_ksl_blk null_blk = {{{NULL, NULL, 0, 0, {0}}}};
 ngtcp2_objalloc_def(ksl_blk, ngtcp2_ksl_blk, oplent);
 
 static size_t ksl_nodelen(size_t keylen) {
-  return (sizeof(ngtcp2_ksl_node) + keylen - sizeof(uint64_t) + 0xfu) &
-         ~(uintptr_t)0xfu;
+  assert(keylen >= sizeof(uint64_t));
+
+  return (sizeof(ngtcp2_ksl_node) + keylen - sizeof(uint64_t) + 0x7u) &
+         ~(uintptr_t)0x7u;
 }
 
 static size_t ksl_blklen(size_t nodelen) {
@@ -65,9 +67,9 @@ void ngtcp2_ksl_init(ngtcp2_ksl *ksl, ngtcp2_ksl_compar compar, size_t keylen,
   ksl->head = NULL;
   ksl->front = ksl->back = NULL;
   ksl->compar = compar;
+  ksl->n = 0;
   ksl->keylen = keylen;
   ksl->nodelen = nodelen;
-  ksl->n = 0;
 }
 
 static ngtcp2_ksl_blk *ksl_blk_objalloc_new(ngtcp2_ksl *ksl) {
@@ -81,6 +83,7 @@ static void ksl_blk_objalloc_del(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk) {
 
 static int ksl_head_init(ngtcp2_ksl *ksl) {
   ngtcp2_ksl_blk *head = ksl_blk_objalloc_new(ksl);
+
   if (!head) {
     return NGTCP2_ERR_NOMEM;
   }
@@ -142,21 +145,22 @@ static ngtcp2_ksl_blk *ksl_split_blk(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk) {
 
   rblk->next = blk->next;
   blk->next = rblk;
+
   if (rblk->next) {
     rblk->next->prev = rblk;
   } else if (ksl->back == blk) {
     ksl->back = rblk;
   }
+
   rblk->prev = blk;
   rblk->leaf = blk->leaf;
 
   rblk->n = blk->n / 2;
+  blk->n -= rblk->n;
 
-  memcpy(rblk->nodes, blk->nodes + ksl->nodelen * (blk->n - rblk->n),
+  memcpy(rblk->nodes, blk->nodes + ksl->nodelen * blk->n,
          ksl->nodelen * rblk->n);
 
-  blk->n -= rblk->n;
-
   assert(blk->n >= NGTCP2_KSL_MIN_NBLK);
   assert(rblk->n >= NGTCP2_KSL_MIN_NBLK);
 
@@ -172,7 +176,7 @@ static ngtcp2_ksl_blk *ksl_split_blk(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk) {
  * codes:
  *
  * NGTCP2_ERR_NOMEM
- *   Out of memory.
+ *     Out of memory.
  */
 static int ksl_split_node(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, size_t i) {
   ngtcp2_ksl_node *node;
@@ -206,7 +210,7 @@ static int ksl_split_node(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, size_t i) {
  * codes:
  *
  * NGTCP2_ERR_NOMEM
- *   Out of memory.
+ *     Out of memory.
  */
 static int ksl_split_head(ngtcp2_ksl *ksl) {
   ngtcp2_ksl_blk *rblk = NULL, *lblk, *nhead = NULL;
@@ -220,10 +224,12 @@ static int ksl_split_head(ngtcp2_ksl *ksl) {
   lblk = ksl->head;
 
   nhead = ksl_blk_objalloc_new(ksl);
+
   if (nhead == NULL) {
     ksl_blk_objalloc_del(ksl, rblk);
     return NGTCP2_ERR_NOMEM;
   }
+
   nhead->next = nhead->prev = NULL;
   nhead->n = 2;
   nhead->leaf = 0;
@@ -242,9 +248,9 @@ static int ksl_split_head(ngtcp2_ksl *ksl) {
 }
 
 /*
- * insert_node inserts a node whose key is |key| with the associated
- * |data| at the index of |i|.  This function assumes that the number
- * of nodes contained by |blk| is strictly less than
+ * ksl_insert_node inserts a node whose key is |key| with the
+ * associated |data| at the index of |i|.  This function assumes that
+ * the number of nodes contained by |blk| is strictly less than
  * NGTCP2_KSL_MAX_NBLK.
  */
 static void ksl_insert_node(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, size_t i,
@@ -263,8 +269,8 @@ static void ksl_insert_node(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, size_t i,
   ++blk->n;
 }
 
-static size_t ksl_bsearch(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk,
-                          const ngtcp2_ksl_key *key, ngtcp2_ksl_compar compar) {
+static size_t ksl_search(const ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk,
+                         const ngtcp2_ksl_key *key, ngtcp2_ksl_compar compar) {
   size_t i;
   ngtcp2_ksl_node *node;
 
@@ -290,18 +296,17 @@ int ngtcp2_ksl_insert(ngtcp2_ksl *ksl, ngtcp2_ksl_it *it,
     }
   }
 
-  blk = ksl->head;
-
-  if (blk->n == NGTCP2_KSL_MAX_NBLK) {
+  if (ksl->head->n == NGTCP2_KSL_MAX_NBLK) {
     rv = ksl_split_head(ksl);
     if (rv != 0) {
       return rv;
     }
-    blk = ksl->head;
   }
 
+  blk = ksl->head;
+
   for (;;) {
-    i = ksl_bsearch(ksl, blk, key, ksl->compar);
+    i = ksl_search(ksl, blk, key, ksl->compar);
 
     if (blk->leaf) {
       if (i < blk->n &&
@@ -309,13 +314,17 @@ int ngtcp2_ksl_insert(ngtcp2_ksl *ksl, ngtcp2_ksl_it *it,
         if (it) {
           *it = ngtcp2_ksl_end(ksl);
         }
+
         return NGTCP2_ERR_INVALID_ARGUMENT;
       }
+
       ksl_insert_node(ksl, blk, i, key, data);
       ++ksl->n;
+
       if (it) {
         ngtcp2_ksl_it_init(it, ksl, blk, i);
       }
+
       return 0;
     }
 
@@ -328,16 +337,21 @@ int ngtcp2_ksl_insert(ngtcp2_ksl *ksl, ngtcp2_ksl_it *it,
           if (rv != 0) {
             return rv;
           }
+
           node = ngtcp2_ksl_nth_node(ksl, blk, blk->n - 1);
         }
+
         ksl_node_set_key(ksl, node, key);
         blk = node->blk;
       }
+
       ksl_insert_node(ksl, blk, blk->n, key, data);
       ++ksl->n;
+
       if (it) {
         ngtcp2_ksl_it_init(it, ksl, blk, blk->n - 1);
       }
+
       return 0;
     }
 
@@ -348,8 +362,10 @@ int ngtcp2_ksl_insert(ngtcp2_ksl *ksl, ngtcp2_ksl_it *it,
       if (rv != 0) {
         return rv;
       }
+
       if (ksl->compar((ngtcp2_ksl_key *)node->key, key)) {
         node = ngtcp2_ksl_nth_node(ksl, blk, i + 1);
+
         if (ksl->compar((ngtcp2_ksl_key *)node->key, key)) {
           ksl_node_set_key(ksl, node, key);
         }
@@ -375,19 +391,22 @@ static void ksl_remove_node(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, size_t i) {
  * ksl_merge_node merges 2 nodes which are the nodes at the index of
  * |i| and |i + 1|.
  *
- * If |blk| is the direct descendant of head (root) block and the head
- * block contains just 2 nodes, the merged block becomes head block,
- * which decreases the height of |ksl| by 1.
+ * If |blk| is the head (root) block and it contains just 2 nodes
+ * before merging nodes, the merged block becomes head block, which
+ * decreases the height of |ksl| by 1.
  *
  * This function returns the pointer to the merged block.
  */
 static ngtcp2_ksl_blk *ksl_merge_node(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk,
                                       size_t i) {
+  ngtcp2_ksl_node *lnode;
   ngtcp2_ksl_blk *lblk, *rblk;
 
   assert(i + 1 < blk->n);
 
-  lblk = ngtcp2_ksl_nth_node(ksl, blk, i)->blk;
+  lnode = ngtcp2_ksl_nth_node(ksl, blk, i);
+
+  lblk = lnode->blk;
   rblk = ngtcp2_ksl_nth_node(ksl, blk, i + 1)->blk;
 
   assert(lblk->n + rblk->n < NGTCP2_KSL_MAX_NBLK);
@@ -397,6 +416,7 @@ static ngtcp2_ksl_blk *ksl_merge_node(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk,
 
   lblk->n += rblk->n;
   lblk->next = rblk->next;
+
   if (lblk->next) {
     lblk->next->prev = lblk;
   } else if (ksl->back == rblk) {
@@ -410,7 +430,7 @@ static ngtcp2_ksl_blk *ksl_merge_node(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk,
     ksl->head = lblk;
   } else {
     ksl_remove_node(ksl, blk, i + 1);
-    ksl_node_set_key(ksl, ngtcp2_ksl_nth_node(ksl, blk, i),
+    ksl_node_set_key(ksl, lnode,
                      ngtcp2_ksl_nth_node(ksl, lblk, lblk->n - 1)->key);
   }
 
@@ -424,6 +444,7 @@ static ngtcp2_ksl_blk *ksl_merge_node(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk,
  */
 static void ksl_shift_left(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, size_t i) {
   ngtcp2_ksl_node *lnode, *rnode;
+  ngtcp2_ksl_blk *lblk, *rblk;
   size_t n;
 
   assert(i > 0);
@@ -431,35 +452,37 @@ static void ksl_shift_left(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, size_t i) {
   lnode = ngtcp2_ksl_nth_node(ksl, blk, i - 1);
   rnode = ngtcp2_ksl_nth_node(ksl, blk, i);
 
-  assert(lnode->blk->n < NGTCP2_KSL_MAX_NBLK);
-  assert(rnode->blk->n > NGTCP2_KSL_MIN_NBLK);
+  lblk = lnode->blk;
+  rblk = rnode->blk;
+
+  assert(lblk->n < NGTCP2_KSL_MAX_NBLK);
+  assert(rblk->n > NGTCP2_KSL_MIN_NBLK);
 
-  n = (lnode->blk->n + rnode->blk->n + 1) / 2 - lnode->blk->n;
+  n = (lblk->n + rblk->n + 1) / 2 - lblk->n;
 
   assert(n > 0);
-  assert(lnode->blk->n <= NGTCP2_KSL_MAX_NBLK - n);
-  assert(rnode->blk->n >= NGTCP2_KSL_MIN_NBLK + n);
+  assert(lblk->n <= NGTCP2_KSL_MAX_NBLK - n);
+  assert(rblk->n >= NGTCP2_KSL_MIN_NBLK + n);
 
-  memcpy(lnode->blk->nodes + ksl->nodelen * lnode->blk->n, rnode->blk->nodes,
-         ksl->nodelen * n);
+  memcpy(lblk->nodes + ksl->nodelen * lblk->n, rblk->nodes, ksl->nodelen * n);
 
-  lnode->blk->n += (uint32_t)n;
-  rnode->blk->n -= (uint32_t)n;
+  lblk->n += (uint32_t)n;
+  rblk->n -= (uint32_t)n;
 
-  ksl_node_set_key(
-      ksl, lnode, ngtcp2_ksl_nth_node(ksl, lnode->blk, lnode->blk->n - 1)->key);
+  ksl_node_set_key(ksl, lnode,
+                   ngtcp2_ksl_nth_node(ksl, lblk, lblk->n - 1)->key);
 
-  memmove(rnode->blk->nodes, rnode->blk->nodes + ksl->nodelen * n,
-          ksl->nodelen * rnode->blk->n);
+  memmove(rblk->nodes, rblk->nodes + ksl->nodelen * n, ksl->nodelen * rblk->n);
 }
 
 /*
  * ksl_shift_right moves the last nodes in blk->nodes[i]->blk->nodes
  * to blk->nodes[i + 1]->blk->nodes in a manner that they have the
- * same amount of nodes as much as possible..
+ * same amount of nodes as much as possible.
  */
 static void ksl_shift_right(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, size_t i) {
   ngtcp2_ksl_node *lnode, *rnode;
+  ngtcp2_ksl_blk *lblk, *rblk;
   size_t n;
 
   assert(i < blk->n - 1);
@@ -467,26 +490,27 @@ static void ksl_shift_right(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, size_t i) {
   lnode = ngtcp2_ksl_nth_node(ksl, blk, i);
   rnode = ngtcp2_ksl_nth_node(ksl, blk, i + 1);
 
-  assert(lnode->blk->n > NGTCP2_KSL_MIN_NBLK);
-  assert(rnode->blk->n < NGTCP2_KSL_MAX_NBLK);
+  lblk = lnode->blk;
+  rblk = rnode->blk;
 
-  n = (lnode->blk->n + rnode->blk->n + 1) / 2 - rnode->blk->n;
+  assert(lblk->n > NGTCP2_KSL_MIN_NBLK);
+  assert(rblk->n < NGTCP2_KSL_MAX_NBLK);
+
+  n = (lblk->n + rblk->n + 1) / 2 - rblk->n;
 
   assert(n > 0);
-  assert(lnode->blk->n >= NGTCP2_KSL_MIN_NBLK + n);
-  assert(rnode->blk->n <= NGTCP2_KSL_MAX_NBLK - n);
+  assert(lblk->n >= NGTCP2_KSL_MIN_NBLK + n);
+  assert(rblk->n <= NGTCP2_KSL_MAX_NBLK - n);
 
-  memmove(rnode->blk->nodes + ksl->nodelen * n, rnode->blk->nodes,
-          ksl->nodelen * rnode->blk->n);
+  memmove(rblk->nodes + ksl->nodelen * n, rblk->nodes, ksl->nodelen * rblk->n);
 
-  rnode->blk->n += (uint32_t)n;
-  lnode->blk->n -= (uint32_t)n;
+  rblk->n += (uint32_t)n;
+  lblk->n -= (uint32_t)n;
 
-  memcpy(rnode->blk->nodes, lnode->blk->nodes + ksl->nodelen * lnode->blk->n,
-         ksl->nodelen * n);
+  memcpy(rblk->nodes, lblk->nodes + ksl->nodelen * lblk->n, ksl->nodelen * n);
 
-  ksl_node_set_key(
-      ksl, lnode, ngtcp2_ksl_nth_node(ksl, lnode->blk, lnode->blk->n - 1)->key);
+  ksl_node_set_key(ksl, lnode,
+                   ngtcp2_ksl_nth_node(ksl, lblk, lblk->n - 1)->key);
 }
 
 /*
@@ -530,23 +554,24 @@ int ngtcp2_ksl_remove(ngtcp2_ksl *ksl, ngtcp2_ksl_it *it,
   ngtcp2_ksl_node *node;
   size_t i;
 
-  if (!ksl->head) {
+  if (!blk) {
     return NGTCP2_ERR_INVALID_ARGUMENT;
   }
 
   if (!blk->leaf && blk->n == 2 &&
       ngtcp2_ksl_nth_node(ksl, blk, 0)->blk->n == NGTCP2_KSL_MIN_NBLK &&
       ngtcp2_ksl_nth_node(ksl, blk, 1)->blk->n == NGTCP2_KSL_MIN_NBLK) {
-    blk = ksl_merge_node(ksl, ksl->head, 0);
+    blk = ksl_merge_node(ksl, blk, 0);
   }
 
   for (;;) {
-    i = ksl_bsearch(ksl, blk, key, ksl->compar);
+    i = ksl_search(ksl, blk, key, ksl->compar);
 
     if (i == blk->n) {
       if (it) {
         *it = ngtcp2_ksl_end(ksl);
       }
+
       return NGTCP2_ERR_INVALID_ARGUMENT;
     }
 
@@ -555,10 +580,13 @@ int ngtcp2_ksl_remove(ngtcp2_ksl *ksl, ngtcp2_ksl_it *it,
         if (it) {
           *it = ngtcp2_ksl_end(ksl);
         }
+
         return NGTCP2_ERR_INVALID_ARGUMENT;
       }
+
       ksl_remove_node(ksl, blk, i);
       --ksl->n;
+
       if (it) {
         if (blk->n == i && blk->next) {
           ngtcp2_ksl_it_init(it, ksl, blk->next, 0);
@@ -566,6 +594,7 @@ int ngtcp2_ksl_remove(ngtcp2_ksl *ksl, ngtcp2_ksl_it *it,
           ngtcp2_ksl_it_init(it, ksl, blk, i);
         }
       }
+
       return 0;
     }
 
@@ -582,6 +611,7 @@ int ngtcp2_ksl_remove(ngtcp2_ksl *ksl, ngtcp2_ksl_it *it,
         ngtcp2_ksl_nth_node(ksl, blk, i + 1)->blk->n > NGTCP2_KSL_MIN_NBLK) {
       ksl_shift_left(ksl, blk, i + 1);
       blk = node->blk;
+
       continue;
     }
 
@@ -589,6 +619,7 @@ int ngtcp2_ksl_remove(ngtcp2_ksl *ksl, ngtcp2_ksl_it *it,
         ngtcp2_ksl_nth_node(ksl, blk, i - 1)->blk->n > NGTCP2_KSL_MIN_NBLK) {
       ksl_shift_right(ksl, blk, i - 1);
       blk = node->blk;
+
       continue;
     }
 
@@ -603,48 +634,12 @@ int ngtcp2_ksl_remove(ngtcp2_ksl *ksl, ngtcp2_ksl_it *it,
   }
 }
 
-ngtcp2_ksl_it ngtcp2_ksl_lower_bound(ngtcp2_ksl *ksl,
+ngtcp2_ksl_it ngtcp2_ksl_lower_bound(const ngtcp2_ksl *ksl,
                                      const ngtcp2_ksl_key *key) {
-  ngtcp2_ksl_blk *blk = ksl->head;
-  ngtcp2_ksl_it it;
-  size_t i;
-
-  if (!blk) {
-    ngtcp2_ksl_it_init(&it, ksl, &null_blk, 0);
-    return it;
-  }
-
-  for (;;) {
-    i = ksl_bsearch(ksl, blk, key, ksl->compar);
-
-    if (blk->leaf) {
-      if (i == blk->n && blk->next) {
-        blk = blk->next;
-        i = 0;
-      }
-      ngtcp2_ksl_it_init(&it, ksl, blk, i);
-      return it;
-    }
-
-    if (i == blk->n) {
-      /* This happens if descendant has smaller key.  Fast forward to
-         find last node in this subtree. */
-      for (; !blk->leaf; blk = ngtcp2_ksl_nth_node(ksl, blk, blk->n - 1)->blk)
-        ;
-      if (blk->next) {
-        blk = blk->next;
-        i = 0;
-      } else {
-        i = blk->n;
-      }
-      ngtcp2_ksl_it_init(&it, ksl, blk, i);
-      return it;
-    }
-    blk = ngtcp2_ksl_nth_node(ksl, blk, i)->blk;
-  }
+  return ngtcp2_ksl_lower_bound_compar(ksl, key, ksl->compar);
 }
 
-ngtcp2_ksl_it ngtcp2_ksl_lower_bound_compar(ngtcp2_ksl *ksl,
+ngtcp2_ksl_it ngtcp2_ksl_lower_bound_compar(const ngtcp2_ksl *ksl,
                                             const ngtcp2_ksl_key *key,
                                             ngtcp2_ksl_compar compar) {
   ngtcp2_ksl_blk *blk = ksl->head;
@@ -657,14 +652,16 @@ ngtcp2_ksl_it ngtcp2_ksl_lower_bound_compar(ngtcp2_ksl *ksl,
   }
 
   for (;;) {
-    i = ksl_bsearch(ksl, blk, key, compar);
+    i = ksl_search(ksl, blk, key, compar);
 
     if (blk->leaf) {
       if (i == blk->n && blk->next) {
         blk = blk->next;
         i = 0;
       }
+
       ngtcp2_ksl_it_init(&it, ksl, blk, i);
+
       return it;
     }
 
@@ -673,15 +670,19 @@ ngtcp2_ksl_it ngtcp2_ksl_lower_bound_compar(ngtcp2_ksl *ksl,
          find last node in this subtree. */
       for (; !blk->leaf; blk = ngtcp2_ksl_nth_node(ksl, blk, blk->n - 1)->blk)
         ;
+
       if (blk->next) {
         blk = blk->next;
         i = 0;
       } else {
         i = blk->n;
       }
+
       ngtcp2_ksl_it_init(&it, ksl, blk, i);
+
       return it;
     }
+
     blk = ngtcp2_ksl_nth_node(ksl, blk, i)->blk;
   }
 }
@@ -695,7 +696,7 @@ void ngtcp2_ksl_update_key(ngtcp2_ksl *ksl, const ngtcp2_ksl_key *old_key,
   assert(ksl->head);
 
   for (;;) {
-    i = ksl_bsearch(ksl, blk, old_key, ksl->compar);
+    i = ksl_search(ksl, blk, old_key, ksl->compar);
 
     assert(i < blk->n);
     node = ngtcp2_ksl_nth_node(ksl, blk, i);
@@ -703,6 +704,7 @@ void ngtcp2_ksl_update_key(ngtcp2_ksl *ksl, const ngtcp2_ksl_key *old_key,
     if (blk->leaf) {
       assert(key_equal(ksl->compar, (ngtcp2_ksl_key *)node->key, old_key));
       ksl_node_set_key(ksl, node, new_key);
+
       return;
     }
 
@@ -715,7 +717,7 @@ void ngtcp2_ksl_update_key(ngtcp2_ksl *ksl, const ngtcp2_ksl_key *old_key,
   }
 }
 
-size_t ngtcp2_ksl_len(ngtcp2_ksl *ksl) { return ksl->n; }
+size_t ngtcp2_ksl_len(const ngtcp2_ksl *ksl) { return ksl->n; }
 
 void ngtcp2_ksl_clear(ngtcp2_ksl *ksl) {
   if (!ksl->head) {
@@ -733,7 +735,8 @@ void ngtcp2_ksl_clear(ngtcp2_ksl *ksl) {
 }
 
 #ifndef WIN32
-static void ksl_print(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, size_t level) {
+static void ksl_print(const ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk,
+                      size_t level) {
   size_t i;
   ngtcp2_ksl_node *node;
 
@@ -744,7 +747,9 @@ static void ksl_print(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, size_t level) {
       node = ngtcp2_ksl_nth_node(ksl, blk, i);
       fprintf(stderr, " %" PRId64, *(int64_t *)(void *)node->key);
     }
+
     fprintf(stderr, "\n");
+
     return;
   }
 
@@ -753,7 +758,7 @@ static void ksl_print(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, size_t level) {
   }
 }
 
-void ngtcp2_ksl_print(ngtcp2_ksl *ksl) {
+void ngtcp2_ksl_print(const ngtcp2_ksl *ksl) {
   if (!ksl->head) {
     return;
   }