1 files changed, 60 insertions, 70 deletions

diff --git a/libs/libcurl/src/splay.c b/libs/libcurl/src/splay.c
index 3570712d43..69af446eb5 100644
--- a/libs/libcurl/src/splay.c
+++ b/libs/libcurl/src/splay.c
@@ -5,11 +5,11 @@
  *                            | (__| |_| |  _ <| |___
  *                             \___|\___/|_| \_\_____|
  *
- * Copyright (C) 1997 - 2011, Daniel Stenberg, <daniel@haxx.se>, et al.
+ * Copyright (C) 1997 - 2017, Daniel Stenberg, <daniel@haxx.se>, et al.
  *
  * This software is licensed as described in the file COPYING, which
  * you should have received as part of this distribution. The terms
- * are also available at http://curl.haxx.se/docs/copyright.html.
+ * are also available at https://curl.haxx.se/docs/copyright.html.
  *
  * You may opt to use, copy, modify, merge, publish, distribute and/or sell
  * copies of the Software, and permit persons to whom the Software is
@@ -37,7 +37,7 @@
  * Splay using the key i (which may or may not be in the tree.) The starting
  * root is t.
  */
-struct Curl_tree *Curl_splay(struct timeval i,
+struct Curl_tree *Curl_splay(struct curltime i,
                              struct Curl_tree *t)
 {
   struct Curl_tree N, *l, *r, *y;
@@ -97,35 +97,32 @@ struct Curl_tree *Curl_splay(struct timeval i,
  *
  * @unittest: 1309
  */
-struct Curl_tree *Curl_splayinsert(struct timeval i,
+struct Curl_tree *Curl_splayinsert(struct curltime i,
                                    struct Curl_tree *t,
                                    struct Curl_tree *node)
 {
-  static struct timeval KEY_NOTUSED = {-1,-1}; /* will *NEVER* appear */
+  static const struct curltime KEY_NOTUSED = {
+    (time_t)-1, (unsigned int)-1
+  }; /* will *NEVER* appear */
 
   if(node == NULL)
     return t;
 
   if(t != NULL) {
-    t = Curl_splay(i,t);
-    if(compare(i, t->key)==0) {
+    t = Curl_splay(i, t);
+    if(compare(i, t->key) == 0) {
       /* There already exists a node in the tree with the very same key. Build
-         a linked list of nodes. We make the new 'node' struct the new master
-         node and make the previous node the first one in the 'same' list. */
+         a doubly-linked circular list of nodes. We add the new 'node' struct
+         to the end of this list. */
 
-      node->same = t;
-      node->key = i;
-      node->smaller = t->smaller;
-      node->larger = t->larger;
+      node->key = KEY_NOTUSED; /* we set the key in the sub node to NOTUSED
+                                  to quickly identify this node as a subnode */
+      node->samen = t;
+      node->samep = t->samep;
+      t->samep->samen = node;
+      t->samep = node;
 
-      t->smaller = node; /* in the sub node for this same key, we use the
-                            smaller pointer to point back to the master
-                            node */
-
-      t->key = KEY_NOTUSED; /* and we set the key in the sub node to NOTUSED
-                               to quickly identify this node as a subnode */
-
-      return node; /* new root node */
+      return t; /* the root node always stays the same */
     }
   }
 
@@ -145,16 +142,20 @@ struct Curl_tree *Curl_splayinsert(struct timeval i,
   }
   node->key = i;
 
-  node->same = NULL; /* no identical node (yet) */
+  /* no identical nodes (yet), we are the only one in the list of nodes */
+  node->samen = node;
+  node->samep = node;
   return node;
 }
 
 /* Finds and deletes the best-fit node from the tree. Return a pointer to the
-   resulting tree.  best-fit means the node with the given or lower key */
-struct Curl_tree *Curl_splaygetbest(struct timeval i,
+   resulting tree.  best-fit means the smallest node if it is not larger than
+   the key */
+struct Curl_tree *Curl_splaygetbest(struct curltime i,
                                     struct Curl_tree *t,
                                     struct Curl_tree **removed)
 {
+  static struct curltime tv_zero = {0, 0};
   struct Curl_tree *x;
 
   if(!t) {
@@ -162,49 +163,36 @@ struct Curl_tree *Curl_splaygetbest(struct timeval i,
     return NULL;
   }
 
-  t = Curl_splay(i,t);
+  /* find smallest */
+  t = Curl_splay(tv_zero, t);
   if(compare(i, t->key) < 0) {
-    /* too big node, try the smaller chain */
-    if(t->smaller)
-      t=Curl_splay(t->smaller->key, t);
-    else {
-      /* fail */
-      *removed = NULL;
-      return t;
-    }
+    /* even the smallest is too big */
+    *removed = NULL;
+    return t;
   }
 
-  if(compare(i, t->key) >= 0) {               /* found it */
-    /* FIRST! Check if there is a list with identical keys */
-    x = t->same;
-    if(x) {
-      /* there is, pick one from the list */
+  /* FIRST! Check if there is a list with identical keys */
+  x = t->samen;
+  if(x != t) {
+    /* there is, pick one from the list */
 
-      /* 'x' is the new root node */
+    /* 'x' is the new root node */
 
-      x->key = t->key;
-      x->larger = t->larger;
-      x->smaller = t->smaller;
-
-      *removed = t;
-      return x; /* new root */
-    }
+    x->key = t->key;
+    x->larger = t->larger;
+    x->smaller = t->smaller;
+    x->samep = t->samep;
+    t->samep->samen = x;
 
-    if(t->smaller == NULL) {
-      x = t->larger;
-    }
-    else {
-      x = Curl_splay(i, t->smaller);
-      x->larger = t->larger;
-    }
     *removed = t;
-
-    return x;
-  }
-  else {
-    *removed = NULL; /* no match */
-    return t;        /* It wasn't there */
+    return x; /* new root */
   }
+
+  /* we splayed the tree to the smallest element, there is no smaller */
+  x = t->larger;
+  *removed = t;
+
+  return x;
 }
 
 
@@ -223,7 +211,9 @@ int Curl_splayremovebyaddr(struct Curl_tree *t,
                            struct Curl_tree *removenode,
                            struct Curl_tree **newroot)
 {
-  static struct timeval KEY_NOTUSED = {-1,-1}; /* will *NEVER* appear */
+  static const struct curltime KEY_NOTUSED = {
+    (time_t)-1, (unsigned int)-1
+  }; /* will *NEVER* appear */
   struct Curl_tree *x;
 
   if(!t || !removenode)
@@ -231,19 +221,17 @@ int Curl_splayremovebyaddr(struct Curl_tree *t,
 
   if(compare(KEY_NOTUSED, removenode->key) == 0) {
     /* Key set to NOTUSED means it is a subnode within a 'same' linked list
-       and thus we can unlink it easily. The 'smaller' link of a subnode
-       links to the parent node. */
-    if(removenode->smaller == NULL)
+       and thus we can unlink it easily. */
+    if(removenode->samen == removenode)
+      /* A non-subnode should never be set to KEY_NOTUSED */
       return 3;
 
-    removenode->smaller->same = removenode->same;
-    if(removenode->same)
-      removenode->same->smaller = removenode->smaller;
+    removenode->samep->samen = removenode->samen;
+    removenode->samen->samep = removenode->samep;
 
     /* Ensures that double-remove gets caught. */
-    removenode->smaller = NULL;
+    removenode->samen = removenode;
 
-    /* voila, we're done! */
     *newroot = t; /* return the same root */
     return 0;
   }
@@ -262,14 +250,16 @@ int Curl_splayremovebyaddr(struct Curl_tree *t,
 
   /* Check if there is a list with identical sizes, as then we're trying to
      remove the root node of a list of nodes with identical keys. */
-  x = t->same;
-  if(x) {
+  x = t->samen;
+  if(x != t) {
     /* 'x' is the new root node, we just make it use the root node's
        smaller/larger links */
 
     x->key = t->key;
     x->larger = t->larger;
     x->smaller = t->smaller;
+    x->samep = t->samep;
+    t->samep->samen = x;
   }
   else {
     /* Remove the root node */