[337] | 1 | /***************************************************************************
|
---|
| 2 | * _ _ ____ _
|
---|
| 3 | * Project ___| | | | _ \| |
|
---|
| 4 | * / __| | | | |_) | |
|
---|
| 5 | * | (__| |_| | _ <| |___
|
---|
| 6 | * \___|\___/|_| \_\_____|
|
---|
| 7 | *
|
---|
| 8 | * Copyright (C) 1997 - 2017, Daniel Stenberg, <daniel@haxx.se>, et al.
|
---|
| 9 | *
|
---|
| 10 | * This software is licensed as described in the file COPYING, which
|
---|
| 11 | * you should have received as part of this distribution. The terms
|
---|
| 12 | * are also available at https://curl.haxx.se/docs/copyright.html.
|
---|
| 13 | *
|
---|
| 14 | * You may opt to use, copy, modify, merge, publish, distribute and/or sell
|
---|
| 15 | * copies of the Software, and permit persons to whom the Software is
|
---|
| 16 | * furnished to do so, under the terms of the COPYING file.
|
---|
| 17 | *
|
---|
| 18 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
|
---|
| 19 | * KIND, either express or implied.
|
---|
| 20 | *
|
---|
| 21 | ***************************************************************************/
|
---|
| 22 |
|
---|
| 23 | #include "curl_setup.h"
|
---|
| 24 |
|
---|
| 25 | #include "splay.h"
|
---|
| 26 |
|
---|
| 27 | /*
|
---|
| 28 | * This macro compares two node keys i and j and returns:
|
---|
| 29 | *
|
---|
| 30 | * negative value: when i is smaller than j
|
---|
| 31 | * zero : when i is equal to j
|
---|
| 32 | * positive when : when i is larger than j
|
---|
| 33 | */
|
---|
| 34 | #define compare(i,j) Curl_splaycomparekeys((i),(j))
|
---|
| 35 |
|
---|
| 36 | /*
|
---|
| 37 | * Splay using the key i (which may or may not be in the tree.) The starting
|
---|
| 38 | * root is t.
|
---|
| 39 | */
|
---|
| 40 | struct Curl_tree *Curl_splay(struct curltime i,
|
---|
| 41 | struct Curl_tree *t)
|
---|
| 42 | {
|
---|
| 43 | struct Curl_tree N, *l, *r, *y;
|
---|
| 44 | long comp;
|
---|
| 45 |
|
---|
| 46 | if(t == NULL)
|
---|
| 47 | return t;
|
---|
| 48 | N.smaller = N.larger = NULL;
|
---|
| 49 | l = r = &N;
|
---|
| 50 |
|
---|
| 51 | for(;;) {
|
---|
| 52 | comp = compare(i, t->key);
|
---|
| 53 | if(comp < 0) {
|
---|
| 54 | if(t->smaller == NULL)
|
---|
| 55 | break;
|
---|
| 56 | if(compare(i, t->smaller->key) < 0) {
|
---|
| 57 | y = t->smaller; /* rotate smaller */
|
---|
| 58 | t->smaller = y->larger;
|
---|
| 59 | y->larger = t;
|
---|
| 60 | t = y;
|
---|
| 61 | if(t->smaller == NULL)
|
---|
| 62 | break;
|
---|
| 63 | }
|
---|
| 64 | r->smaller = t; /* link smaller */
|
---|
| 65 | r = t;
|
---|
| 66 | t = t->smaller;
|
---|
| 67 | }
|
---|
| 68 | else if(comp > 0) {
|
---|
| 69 | if(t->larger == NULL)
|
---|
| 70 | break;
|
---|
| 71 | if(compare(i, t->larger->key) > 0) {
|
---|
| 72 | y = t->larger; /* rotate larger */
|
---|
| 73 | t->larger = y->smaller;
|
---|
| 74 | y->smaller = t;
|
---|
| 75 | t = y;
|
---|
| 76 | if(t->larger == NULL)
|
---|
| 77 | break;
|
---|
| 78 | }
|
---|
| 79 | l->larger = t; /* link larger */
|
---|
| 80 | l = t;
|
---|
| 81 | t = t->larger;
|
---|
| 82 | }
|
---|
| 83 | else
|
---|
| 84 | break;
|
---|
| 85 | }
|
---|
| 86 |
|
---|
| 87 | l->larger = t->smaller; /* assemble */
|
---|
| 88 | r->smaller = t->larger;
|
---|
| 89 | t->smaller = N.larger;
|
---|
| 90 | t->larger = N.smaller;
|
---|
| 91 |
|
---|
| 92 | return t;
|
---|
| 93 | }
|
---|
| 94 |
|
---|
| 95 | /* Insert key i into the tree t. Return a pointer to the resulting tree or
|
---|
| 96 | * NULL if something went wrong.
|
---|
| 97 | *
|
---|
| 98 | * @unittest: 1309
|
---|
| 99 | */
|
---|
| 100 | struct Curl_tree *Curl_splayinsert(struct curltime i,
|
---|
| 101 | struct Curl_tree *t,
|
---|
| 102 | struct Curl_tree *node)
|
---|
| 103 | {
|
---|
| 104 | static const struct curltime KEY_NOTUSED = {
|
---|
| 105 | (time_t)-1, (unsigned int)-1
|
---|
| 106 | }; /* will *NEVER* appear */
|
---|
| 107 |
|
---|
| 108 | if(node == NULL)
|
---|
| 109 | return t;
|
---|
| 110 |
|
---|
| 111 | if(t != NULL) {
|
---|
| 112 | t = Curl_splay(i, t);
|
---|
| 113 | if(compare(i, t->key)==0) {
|
---|
| 114 | /* There already exists a node in the tree with the very same key. Build
|
---|
| 115 | a doubly-linked circular list of nodes. We add the new 'node' struct
|
---|
| 116 | to the end of this list. */
|
---|
| 117 |
|
---|
| 118 | node->key = KEY_NOTUSED; /* we set the key in the sub node to NOTUSED
|
---|
| 119 | to quickly identify this node as a subnode */
|
---|
| 120 | node->samen = t;
|
---|
| 121 | node->samep = t->samep;
|
---|
| 122 | t->samep->samen = node;
|
---|
| 123 | t->samep = node;
|
---|
| 124 |
|
---|
| 125 | return t; /* the root node always stays the same */
|
---|
| 126 | }
|
---|
| 127 | }
|
---|
| 128 |
|
---|
| 129 | if(t == NULL) {
|
---|
| 130 | node->smaller = node->larger = NULL;
|
---|
| 131 | }
|
---|
| 132 | else if(compare(i, t->key) < 0) {
|
---|
| 133 | node->smaller = t->smaller;
|
---|
| 134 | node->larger = t;
|
---|
| 135 | t->smaller = NULL;
|
---|
| 136 |
|
---|
| 137 | }
|
---|
| 138 | else {
|
---|
| 139 | node->larger = t->larger;
|
---|
| 140 | node->smaller = t;
|
---|
| 141 | t->larger = NULL;
|
---|
| 142 | }
|
---|
| 143 | node->key = i;
|
---|
| 144 |
|
---|
| 145 | /* no identical nodes (yet), we are the only one in the list of nodes */
|
---|
| 146 | node->samen = node;
|
---|
| 147 | node->samep = node;
|
---|
| 148 | return node;
|
---|
| 149 | }
|
---|
| 150 |
|
---|
| 151 | /* Finds and deletes the best-fit node from the tree. Return a pointer to the
|
---|
| 152 | resulting tree. best-fit means the smallest node if it is not larger than
|
---|
| 153 | the key */
|
---|
| 154 | struct Curl_tree *Curl_splaygetbest(struct curltime i,
|
---|
| 155 | struct Curl_tree *t,
|
---|
| 156 | struct Curl_tree **removed)
|
---|
| 157 | {
|
---|
| 158 | static struct curltime tv_zero = {0, 0};
|
---|
| 159 | struct Curl_tree *x;
|
---|
| 160 |
|
---|
| 161 | if(!t) {
|
---|
| 162 | *removed = NULL; /* none removed since there was no root */
|
---|
| 163 | return NULL;
|
---|
| 164 | }
|
---|
| 165 |
|
---|
| 166 | /* find smallest */
|
---|
| 167 | t = Curl_splay(tv_zero, t);
|
---|
| 168 | if(compare(i, t->key) < 0) {
|
---|
| 169 | /* even the smallest is too big */
|
---|
| 170 | *removed = NULL;
|
---|
| 171 | return t;
|
---|
| 172 | }
|
---|
| 173 |
|
---|
| 174 | /* FIRST! Check if there is a list with identical keys */
|
---|
| 175 | x = t->samen;
|
---|
| 176 | if(x != t) {
|
---|
| 177 | /* there is, pick one from the list */
|
---|
| 178 |
|
---|
| 179 | /* 'x' is the new root node */
|
---|
| 180 |
|
---|
| 181 | x->key = t->key;
|
---|
| 182 | x->larger = t->larger;
|
---|
| 183 | x->smaller = t->smaller;
|
---|
| 184 | x->samep = t->samep;
|
---|
| 185 | t->samep->samen = x;
|
---|
| 186 |
|
---|
| 187 | *removed = t;
|
---|
| 188 | return x; /* new root */
|
---|
| 189 | }
|
---|
| 190 |
|
---|
| 191 | /* we splayed the tree to the smallest element, there is no smaller */
|
---|
| 192 | x = t->larger;
|
---|
| 193 | *removed = t;
|
---|
| 194 |
|
---|
| 195 | return x;
|
---|
| 196 | }
|
---|
| 197 |
|
---|
| 198 |
|
---|
| 199 | /* Deletes the very node we point out from the tree if it's there. Stores a
|
---|
| 200 | * pointer to the new resulting tree in 'newroot'.
|
---|
| 201 | *
|
---|
| 202 | * Returns zero on success and non-zero on errors! TODO: document error codes.
|
---|
| 203 | * When returning error, it does not touch the 'newroot' pointer.
|
---|
| 204 | *
|
---|
| 205 | * NOTE: when the last node of the tree is removed, there's no tree left so
|
---|
| 206 | * 'newroot' will be made to point to NULL.
|
---|
| 207 | *
|
---|
| 208 | * @unittest: 1309
|
---|
| 209 | */
|
---|
| 210 | int Curl_splayremovebyaddr(struct Curl_tree *t,
|
---|
| 211 | struct Curl_tree *removenode,
|
---|
| 212 | struct Curl_tree **newroot)
|
---|
| 213 | {
|
---|
| 214 | static const struct curltime KEY_NOTUSED = {
|
---|
| 215 | (time_t)-1, (unsigned int)-1
|
---|
| 216 | }; /* will *NEVER* appear */
|
---|
| 217 | struct Curl_tree *x;
|
---|
| 218 |
|
---|
| 219 | if(!t || !removenode)
|
---|
| 220 | return 1;
|
---|
| 221 |
|
---|
| 222 | if(compare(KEY_NOTUSED, removenode->key) == 0) {
|
---|
| 223 | /* Key set to NOTUSED means it is a subnode within a 'same' linked list
|
---|
| 224 | and thus we can unlink it easily. */
|
---|
| 225 | if(removenode->samen == removenode)
|
---|
| 226 | /* A non-subnode should never be set to KEY_NOTUSED */
|
---|
| 227 | return 3;
|
---|
| 228 |
|
---|
| 229 | removenode->samep->samen = removenode->samen;
|
---|
| 230 | removenode->samen->samep = removenode->samep;
|
---|
| 231 |
|
---|
| 232 | /* Ensures that double-remove gets caught. */
|
---|
| 233 | removenode->samen = removenode;
|
---|
| 234 |
|
---|
| 235 | *newroot = t; /* return the same root */
|
---|
| 236 | return 0;
|
---|
| 237 | }
|
---|
| 238 |
|
---|
| 239 | t = Curl_splay(removenode->key, t);
|
---|
| 240 |
|
---|
| 241 | /* First make sure that we got the same root node as the one we want
|
---|
| 242 | to remove, as otherwise we might be trying to remove a node that
|
---|
| 243 | isn't actually in the tree.
|
---|
| 244 |
|
---|
| 245 | We cannot just compare the keys here as a double remove in quick
|
---|
| 246 | succession of a node with key != KEY_NOTUSED && same != NULL
|
---|
| 247 | could return the same key but a different node. */
|
---|
| 248 | if(t != removenode)
|
---|
| 249 | return 2;
|
---|
| 250 |
|
---|
| 251 | /* Check if there is a list with identical sizes, as then we're trying to
|
---|
| 252 | remove the root node of a list of nodes with identical keys. */
|
---|
| 253 | x = t->samen;
|
---|
| 254 | if(x != t) {
|
---|
| 255 | /* 'x' is the new root node, we just make it use the root node's
|
---|
| 256 | smaller/larger links */
|
---|
| 257 |
|
---|
| 258 | x->key = t->key;
|
---|
| 259 | x->larger = t->larger;
|
---|
| 260 | x->smaller = t->smaller;
|
---|
| 261 | x->samep = t->samep;
|
---|
| 262 | t->samep->samen = x;
|
---|
| 263 | }
|
---|
| 264 | else {
|
---|
| 265 | /* Remove the root node */
|
---|
| 266 | if(t->smaller == NULL)
|
---|
| 267 | x = t->larger;
|
---|
| 268 | else {
|
---|
| 269 | x = Curl_splay(removenode->key, t->smaller);
|
---|
| 270 | x->larger = t->larger;
|
---|
| 271 | }
|
---|
| 272 | }
|
---|
| 273 |
|
---|
| 274 | *newroot = x; /* store new root pointer */
|
---|
| 275 |
|
---|
| 276 | return 0;
|
---|
| 277 | }
|
---|
| 278 |
|
---|