Christopher Palow provided the patch (edited by me) that introduces

the use of microsecond resolution keys for internal splay trees.

http://curl.haxx.se/mail/lib-2008-04/0513.html

5 files changed, 76 insertions, 51 deletions

diff --git a/CHANGES b/CHANGES
index 7fdaef117..f68c4f804 100644
--- a/CHANGES
+++ b/CHANGES
@@ -7,6 +7,10 @@
                                   Changelog
 
 
+Yang Tse (7 May 2008)
+- Christopher Palow provided the patch (edited by me) that introduces the
+  use of microsecond resolution keys for internal splay trees.
+
 Daniel Stenberg (4 May 2008)
 - Yuriy Sosov pointed out a configure fix for detecting c-ares when that is
   built debug-enabled.
diff --git a/RELEASE-NOTES b/RELEASE-NOTES
index b14f0b723..4ceb3f9eb 100644
--- a/RELEASE-NOTES
+++ b/RELEASE-NOTES
@@ -30,6 +30,7 @@ This release includes the following bugfixes:
  o CURLOPT_TCP_NODELAY crash due to getprotobyname() use
  o libcurl sometimes sent body twice when using CURLAUTH_ANY
  o configure detecting debug-enabled c-ares
+ o microsecond resolution keys for internal splay trees
 
 This release includes the following known bugs:
 
@@ -51,6 +52,6 @@ advice from friends like these:
  Michal Marek, Daniel Fandrich, Scott Barrett, Alexey Simak, Daniel Black,
  Rafa Muyo, Andre Guibert de Bruet, Brock Noland, Sandor Feldi, Stefan Krause,
  David Shaw, Norbert Frese, Bart Whiteley, Jean-Francois Bertrand, Ben Van Hof,
- Yuriy Sosov
+ Yuriy Sosov, Christopher Palow, Yang Tse
 
         Thanks! (and sorry if I forgot to mention someone)
diff --git a/lib/multi.c b/lib/multi.c
index df287129b..48e7c410a 100644
--- a/lib/multi.c
+++ b/lib/multi.c
@@ -23,9 +23,6 @@
 
 #include "setup.h"
 
-#include <stdlib.h>
-#include <string.h>
-
 #ifdef HAVE_SYS_SOCKET_H
 #include <sys/socket.h>
 #endif
@@ -177,8 +174,8 @@ struct Curl_multi {
   /* timer callback and user data pointer for the *socket() API */
   curl_multi_timer_callback timer_cb;
   void *timer_userp;
-  time_t timer_lastcall; /* the fixed time for the timeout for the previous
-                            callback */
+  struct timeval timer_lastcall; /* the fixed time for the timeout for the
+                                    previous callback */
 };
 
 static bool multi_conn_using(struct Curl_multi *multi,
@@ -1446,9 +1443,8 @@ CURLMcode curl_multi_perform(CURLM *multi_handle, int *running_handles)
    */
   do {
     struct timeval now = Curl_tvnow();
-    int key = now.tv_sec; /* drop the usec part */
 
-    multi->timetree = Curl_splaygetbest(key, multi->timetree, &t);
+    multi->timetree = Curl_splaygetbest(now, multi->timetree, &t);
     if(t) {
       struct SessionHandle *d = t->payload;
       struct timeval* tv = &d->state.expiretime;
@@ -1746,7 +1742,6 @@ static CURLMcode multi_socket(struct Curl_multi *multi,
    * handle we deal with.
    */
   do {
-    int key;
     struct timeval now;
 
     /* the first loop lap 'data' can be NULL */
@@ -1763,9 +1758,8 @@ static CURLMcode multi_socket(struct Curl_multi *multi,
        extracts a matching node if there is one */
 
     now = Curl_tvnow();
-    key = now.tv_sec; /* drop the usec part */
 
-    multi->timetree = Curl_splaygetbest(key, multi->timetree, &t);
+    multi->timetree = Curl_splaygetbest(now, multi->timetree, &t);
     if(t) {
       /* assign 'data' to be the easy handle we just removed from the splay
          tree */
@@ -1858,17 +1852,19 @@ CURLMcode curl_multi_socket_all(CURLM *multi_handle, int *running_handles)
 static CURLMcode multi_timeout(struct Curl_multi *multi,
                                long *timeout_ms)
 {
+  static struct timeval tv_zero = {0,0};
+
   if(multi->timetree) {
     /* we have a tree of expire times */
     struct timeval now = Curl_tvnow();
 
     /* splay the lowest to the bottom */
-    multi->timetree = Curl_splay(0, multi->timetree);
+    multi->timetree = Curl_splay(tv_zero, multi->timetree);
 
-    /* At least currently, the splay key is a time_t for the expire time */
-    *timeout_ms = (multi->timetree->key - now.tv_sec) * 1000 -
-      now.tv_usec/1000;
-    if(*timeout_ms < 0)
+    if(Curl_splaycomparekeys(multi->timetree->key, now) > 0)
+      /* some time left before expiration */
+      *timeout_ms = curlx_tvdiff(multi->timetree->key, now);
+    else
       /* 0 means immediately */
       *timeout_ms = 0;
   }
@@ -1908,7 +1904,7 @@ static int update_timer(struct Curl_multi *multi)
    * timeout we got the (relative) time-out time for. We can thus easily check
    * if this is the same (fixed) time as we got in a previous call and then
    * avoid calling the callback again. */
-  if(multi->timetree->key == multi->timer_lastcall)
+  if(Curl_splaycomparekeys(multi->timetree->key, multi->timer_lastcall) == 0)
     return 0;
 
   multi->timer_lastcall = multi->timetree->key;
@@ -2002,7 +1998,7 @@ void Curl_expire(struct SessionHandle *data, long milli)
 
   if(!milli) {
     /* No timeout, clear the time data. */
-    if(nowp->tv_sec) {
+    if(nowp->tv_sec || nowp->tv_usec) {
       /* Since this is an cleared time, we must remove the previous entry from
          the splay tree */
       rc = Curl_splayremovebyaddr(multi->timetree,
@@ -2030,7 +2026,7 @@ void Curl_expire(struct SessionHandle *data, long milli)
       set.tv_usec -= 1000000;
     }
 
-    if(nowp->tv_sec) {
+    if(nowp->tv_sec || nowp->tv_usec) {
       /* This means that the struct is added as a node in the splay tree.
          Compare if the new time is earlier, and only remove-old/add-new if it
          is. */
@@ -2054,7 +2050,7 @@ void Curl_expire(struct SessionHandle *data, long milli)
           (long)nowp->tv_sec, (long)nowp->tv_usec, milli);
 #endif
     data->state.timenode.payload = data;
-    multi->timetree = Curl_splayinsert((int)nowp->tv_sec,
+    multi->timetree = Curl_splayinsert(*nowp,
                                        multi->timetree,
                                        &data->state.timenode);
   }
diff --git a/lib/splay.c b/lib/splay.c
index 7377ddcbd..04aae1f0b 100644
--- a/lib/splay.c
+++ b/lib/splay.c
@@ -5,7 +5,7 @@
  *                            | (__| |_| |  _ <| |___
  *                             \___|\___/|_| \_\_____|
  *
- * Copyright (C) 1997 - 2007, Daniel Stenberg, <daniel@haxx.se>, et al.
+ * Copyright (C) 1997 - 2008, 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
@@ -23,24 +23,26 @@
 
 #include "setup.h"
 
-#include <stdio.h>
-#include <stdlib.h>
-
 #include "splay.h"
 
-#define compare(i,j) ((i)-(j))
-
-/* Set this to a key value that will *NEVER* appear otherwise */
-#define KEY_NOTUSED -1
+/*
+ * This macro compares two node keys i and j and returns:
+ *
+ *  negative value: when i is smaller than j
+ *  zero          : when i is equal   to   j
+ *  positive when : when i is larger  than j
+ */
+#define compare(i,j) Curl_splaycomparekeys((i),(j))
 
 /*
  * Splay using the key i (which may or may not be in the tree.) The starting
  * root is t.
  */
-struct Curl_tree *Curl_splay(int i, struct Curl_tree *t)
+struct Curl_tree *Curl_splay(struct timeval i,
+                             struct Curl_tree *t)
 {
   struct Curl_tree N, *l, *r, *y;
-  int comp;
+  long comp;
 
   if(t == NULL)
     return t;
@@ -93,10 +95,12 @@ struct Curl_tree *Curl_splay(int i, struct Curl_tree *t)
 
 /* Insert key i into the tree t.  Return a pointer to the resulting tree or
    NULL if something went wrong. */
-struct Curl_tree *Curl_splayinsert(int i,
+struct Curl_tree *Curl_splayinsert(struct timeval i,
                                    struct Curl_tree *t,
                                    struct Curl_tree *node)
 {
+  static struct timeval KEY_NOTUSED = {-1,-1}; /* key that will *NEVER* appear */
+
   if(node == NULL)
     return t;
 
@@ -149,7 +153,8 @@ struct Curl_tree *Curl_splayinsert(int i,
 
    Function not used in libcurl.
 */
-struct Curl_tree *Curl_splayremove(int i, struct Curl_tree *t,
+struct Curl_tree *Curl_splayremove(struct timeval i,
+                                   struct Curl_tree *t,
                                    struct Curl_tree **removed)
 {
   struct Curl_tree *x;
@@ -163,7 +168,7 @@ struct Curl_tree *Curl_splayremove(int i, struct Curl_tree *t,
   if(compare(i, t->key) == 0) {               /* found it */
 
     /* FIRST! Check if there is a list with identical sizes */
-    if((x = t->same)) {
+    if((x = t->same) != NULL) {
       /* there is, pick one from the list */
 
       /* 'x' is the new root node */
@@ -193,8 +198,9 @@ struct Curl_tree *Curl_splayremove(int i, struct Curl_tree *t,
 #endif
 
 /* 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 number */
-struct Curl_tree *Curl_splaygetbest(int i, struct Curl_tree *t,
+   resulting tree.  best-fit means the node with the given or lower key */
+struct Curl_tree *Curl_splaygetbest(struct timeval i,
+                                    struct Curl_tree *t,
                                     struct Curl_tree **removed)
 {
   struct Curl_tree *x;
@@ -217,7 +223,7 @@ struct Curl_tree *Curl_splaygetbest(int i, struct Curl_tree *t,
   }
 
   if(compare(i, t->key) >= 0) {               /* found it */
-    /* FIRST! Check if there is a list with identical sizes */
+    /* FIRST! Check if there is a list with identical keys */
     x = t->same;
     if(x) {
       /* there is, pick one from the list */
@@ -263,12 +269,13 @@ int Curl_splayremovebyaddr(struct Curl_tree *t,
                            struct Curl_tree *removenode,
                            struct Curl_tree **newroot)
 {
+  static struct timeval KEY_NOTUSED = {-1,-1}; /* key that will *NEVER* appear */
   struct Curl_tree *x;
 
   if(!t || !removenode)
     return 1;
 
-  if(KEY_NOTUSED == removenode->key) {
+  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. */
@@ -341,7 +348,11 @@ void Curl_splayprint(struct Curl_tree * t, int d, char output)
       printf("  ");
 
   if(output) {
-    printf("%d[%d]", t->key, i);
+#ifdef TEST_SPLAY
+    printf("%ld[%d]", t->key.tv_usec, i);
+#else
+    printf("%ld.%ld[%d]", t->key.tv_sec, t->key.tv_usec, i);
+#endif
   }
 
   for(count=0, node = t->same; node; node = node->same, count++)
@@ -382,18 +393,19 @@ int main(int argc, argv_item_t argv[])
   root = NULL;              /* the empty tree */
 
   for (i = 0; i < MAX; i++) {
-    int key;
+    struct timeval key;
     ptrs[i] = t = (struct Curl_tree *)malloc(sizeof(struct Curl_tree));
 
+    key.tv_sec = 0;
 #ifdef TEST2
-    key = sizes[i];
+    key.tv_usec = sizes[i];
 #elif defined(TEST1)
-    key = (541*i)%1023;
+    key.tv_usec = (541*i)%1023;
 #elif defined(TEST3)
-    key = 100;
+    key.tv_usec = 100;
 #endif
 
-    t->payload = (void *)key; /* for simplicity */
+    t->payload = (void *)key.tv_usec; /* for simplicity */
     if(!t) {
       puts("out of memory!");
       return 0;
@@ -412,8 +424,8 @@ int main(int argc, argv_item_t argv[])
     struct Curl_tree *r;
     printf("Tree look:\n");
     Curl_splayprint(root, 0, 1);
-    printf("remove pointer %d, payload %d\n", rem,
-           (int)((struct Curl_tree *)ptrs[rem])->payload);
+    printf("remove pointer %d, payload %ld\n", rem,
+           (long)((struct Curl_tree *)ptrs[rem])->payload);
     rc = Curl_splayremovebyaddr(root, (struct Curl_tree *)ptrs[rem], &root);
     if(rc)
       /* failed! */
diff --git a/lib/splay.h b/lib/splay.h
index 6e9191a63..4e6a8c16d 100644
--- a/lib/splay.h
+++ b/lib/splay.h
@@ -7,7 +7,7 @@
  *                            | (__| |_| |  _ <| |___
  *                             \___|\___/|_| \_\_____|
  *
- * Copyright (C) 1997 - 2006, Daniel Stenberg, <daniel@haxx.se>, et al.
+ * Copyright (C) 1997 - 2008, 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
@@ -27,24 +27,36 @@ 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 */
-  int key;                   /* the "sort" key */
+  struct timeval key;        /* this node's "sort" key */
   void *payload;             /* data the splay code doesn't care about */
 };
 
-struct Curl_tree *Curl_splay(int i, struct Curl_tree *t);
-struct Curl_tree *Curl_splayinsert(int key, struct Curl_tree *t,
+struct Curl_tree *Curl_splay(struct timeval i,
+                             struct Curl_tree *t);
+
+struct Curl_tree *Curl_splayinsert(struct timeval key,
+                                   struct Curl_tree *t,
                                    struct Curl_tree *newnode);
+
 #if 0
-struct Curl_tree *Curl_splayremove(int key, struct Curl_tree *t,
+struct Curl_tree *Curl_splayremove(struct timeval key,
+                                   struct Curl_tree *t,
                                    struct Curl_tree **removed);
 #endif
 
-struct Curl_tree *Curl_splaygetbest(int key, struct Curl_tree *t,
+struct Curl_tree *Curl_splaygetbest(struct timeval key,
+                                    struct Curl_tree *t,
                                     struct Curl_tree **removed);
+
 int Curl_splayremovebyaddr(struct Curl_tree *t,
                            struct Curl_tree *removenode,
                            struct Curl_tree **newroot);
 
+#define Curl_splaycomparekeys(i,j) ( ((i.tv_sec)  < (j.tv_sec))  ? -1 : \
+                                   ( ((i.tv_sec)  > (j.tv_sec))  ?  1 : \
+                                   ( ((i.tv_usec) < (j.tv_usec)) ? -1 : \
+                                   ( ((i.tv_usec) > (j.tv_usec)) ?  1 : 0 ))))
+
 #ifdef CURLDEBUG
 void Curl_splayprint(struct Curl_tree * t, int d, char output);
 #else