diff options
| -rw-r--r-- | CHANGES | 4 | ||||
| -rw-r--r-- | RELEASE-NOTES | 3 | ||||
| -rw-r--r-- | lib/multi.c | 34 | ||||
| -rw-r--r-- | lib/splay.c | 62 | ||||
| -rw-r--r-- | lib/splay.h | 24 |
5 files changed, 76 insertions, 51 deletions
@@ -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 |