diff options
author | deshevoy <deshevoy@yandex-team.ru> | 2022-02-10 16:46:57 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:46:57 +0300 |
commit | 28148f76dbfcc644d96427d41c92f36cbf2fdc6e (patch) | |
tree | b83306b6e37edeea782e9eed673d89286c4fef35 /contrib/libs/curl/lib/splay.c | |
parent | e988f30484abe5fdeedcc7a5d3c226c01a21800c (diff) | |
download | ydb-28148f76dbfcc644d96427d41c92f36cbf2fdc6e.tar.gz |
Restoring authorship annotation for <deshevoy@yandex-team.ru>. Commit 2 of 2.
Diffstat (limited to 'contrib/libs/curl/lib/splay.c')
-rw-r--r-- | contrib/libs/curl/lib/splay.c | 120 |
1 files changed, 60 insertions, 60 deletions
diff --git a/contrib/libs/curl/lib/splay.c b/contrib/libs/curl/lib/splay.c index 90e10a99f8..98baf5d871 100644 --- a/contrib/libs/curl/lib/splay.c +++ b/contrib/libs/curl/lib/splay.c @@ -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 curltime i, +struct Curl_tree *Curl_splay(struct curltime i, struct Curl_tree *t) { struct Curl_tree N, *l, *r, *y; @@ -48,7 +48,7 @@ struct Curl_tree *Curl_splay(struct curltime i, l = r = &N; for(;;) { - long comp = compare(i, t->key); + long comp = compare(i, t->key); if(comp < 0) { if(t->smaller == NULL) break; @@ -96,32 +96,32 @@ struct Curl_tree *Curl_splay(struct curltime i, * * @unittest: 1309 */ -struct Curl_tree *Curl_splayinsert(struct curltime i, +struct Curl_tree *Curl_splayinsert(struct curltime i, struct Curl_tree *t, struct Curl_tree *node) { - static const struct curltime KEY_NOTUSED = { - (time_t)-1, (unsigned int)-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 doubly-linked circular list of nodes. We add the new 'node' struct - to the end of this list. */ + a doubly-linked circular list of nodes. We add the new 'node' struct + to the end of this list. */ - 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; + 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; - return t; /* the root node always stays the same */ + return t; /* the root node always stays the same */ } } @@ -141,20 +141,20 @@ struct Curl_tree *Curl_splayinsert(struct curltime i, } node->key = i; - /* no identical nodes (yet), we are the only one in the list of nodes */ - node->samen = node; - node->samep = node; + /* 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 smallest node if it is not larger than - the key */ -struct Curl_tree *Curl_splaygetbest(struct curltime 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}; + static struct curltime tv_zero = {0, 0}; struct Curl_tree *x; if(!t) { @@ -162,36 +162,36 @@ struct Curl_tree *Curl_splaygetbest(struct curltime i, return NULL; } - /* find smallest */ - t = Curl_splay(tv_zero, t); + /* find smallest */ + t = Curl_splay(tv_zero, t); if(compare(i, t->key) < 0) { - /* even the smallest is too big */ - *removed = NULL; - return t; + /* even the smallest is too big */ + *removed = NULL; + return t; } - /* FIRST! Check if there is a list with identical keys */ - x = t->samen; - if(x != t) { - /* 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; - x->samep = t->samep; - t->samep->samen = x; + x->key = t->key; + x->larger = t->larger; + x->smaller = t->smaller; + x->samep = t->samep; + t->samep->samen = x; *removed = t; - return x; /* new root */ - } - - /* we splayed the tree to the smallest element, there is no smaller */ - x = t->larger; - *removed = t; - - return x; + return x; /* new root */ + } + + /* we splayed the tree to the smallest element, there is no smaller */ + x = t->larger; + *removed = t; + + return x; } @@ -210,9 +210,9 @@ int Curl_splayremove(struct Curl_tree *t, struct Curl_tree *removenode, struct Curl_tree **newroot) { - static const struct curltime KEY_NOTUSED = { - (time_t)-1, (unsigned int)-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) @@ -220,16 +220,16 @@ int Curl_splayremove(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. */ - if(removenode->samen == removenode) - /* A non-subnode should never be set to KEY_NOTUSED */ + and thus we can unlink it easily. */ + if(removenode->samen == removenode) + /* A non-subnode should never be set to KEY_NOTUSED */ return 3; - removenode->samep->samen = removenode->samen; - removenode->samen->samep = removenode->samep; + removenode->samep->samen = removenode->samen; + removenode->samen->samep = removenode->samep; /* Ensures that double-remove gets caught. */ - removenode->samen = removenode; + removenode->samen = removenode; *newroot = t; /* return the same root */ return 0; @@ -249,16 +249,16 @@ int Curl_splayremove(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->samen; - if(x != t) { + 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; + x->samep = t->samep; + t->samep->samen = x; } else { /* Remove the root node */ |