diff options
author | Elliott Hughes <enh@google.com> | 2017-09-20 17:00:17 -0700 |
---|---|---|
committer | Elliott Hughes <enh@google.com> | 2017-09-21 09:38:15 -0700 |
commit | 82be86df6ec7baa34d6169c053fd1dfe56fa858e (patch) | |
tree | afd04b931f1f59dfe81b0daa450306ff0204319b /lib/splay.c | |
parent | bfa505f61d33429f40bf843b7871fc793dd017d4 (diff) | |
download | external_curl-82be86df6ec7baa34d6169c053fd1dfe56fa858e.tar.gz external_curl-82be86df6ec7baa34d6169c053fd1dfe56fa858e.tar.bz2 external_curl-82be86df6ec7baa34d6169c053fd1dfe56fa858e.zip |
Update libcurl from 7.54.1 to 7.55.1.
Bug: http://b/64610131
Test: builds, boots, `vendor/google/tools/fake-ota on streaming` works
Change-Id: I7ecaf9c83e9496ac4a379507791bec637deaa4cb
Diffstat (limited to 'lib/splay.c')
-rw-r--r-- | lib/splay.c | 124 |
1 files changed, 57 insertions, 67 deletions
diff --git a/lib/splay.c b/lib/splay.c index 7aa2e4ba..68ff9c5d 100644 --- a/lib/splay.c +++ b/lib/splay.c @@ -5,7 +5,7 @@ * | (__| |_| | _ <| |___ * \___|\___/|_| \_\_____| * - * Copyright (C) 1997 - 2015, 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 @@ -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,11 +97,13 @@ 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 const 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; @@ -110,22 +112,17 @@ struct Curl_tree *Curl_splayinsert(struct timeval i, 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 const 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 */ |