multi: fix queueing of pending easy handles

Multi handles repeatedly invert the queue of pending easy handles when
used with CURLMOPT_MAX_TOTAL_CONNECTIONS. This is caused by a multistep
process involving Curl_splaygetbest and violates the FIFO property of
the multi handle.
This patch fixes this issue by redefining the "best" node in the
context of timeouts as the "smallest not larger than now", and
implementing the necessary data structure modifications to do this
effectively, namely:
 - splay nodes with the same key are now stored in a doubly-linked
   circular list instead of a non-circular one to enable O(1)
   insertion to the tail of the list
 - Curl_splayinsert inserts nodes with the same key to the tail of
   the same list
 - in case of multiple nodes with the same key, the one on the head of
   the list gets selected

1 files changed, 2 insertions, 1 deletions

diff --git a/lib/splay.h b/lib/splay.h
index 427bfc8eb..da81894d1 100644
--- a/lib/splay.h
+++ b/lib/splay.h
@@ -26,7 +26,8 @@
 struct Curl_tree {
   struct Curl_tree *smaller; /* smaller node */
   struct Curl_tree *larger;  /* larger node */
-  struct Curl_tree *same;    /* points to a node with identical key */
+  struct Curl_tree *samen;   /* points to the next node with identical key */
+  struct Curl_tree *samep;   /* points to the prev node with identical key */
   struct timeval key;        /* this node's "sort" key */
   void *payload;             /* data the splay code doesn't care about */
 };