[164] | 1 | /***************************************************************************
|
---|
| 2 | * _ _ ____ _
|
---|
| 3 | * Project ___| | | | _ \| |
|
---|
| 4 | * / __| | | | |_) | |
|
---|
| 5 | * | (__| |_| | _ <| |___
|
---|
| 6 | * \___|\___/|_| \_\_____|
|
---|
| 7 | *
|
---|
| 8 | * Copyright (C) 1997 - 2015, 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 timeval 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 timeval i,
|
---|
| 101 | struct Curl_tree *t,
|
---|
| 102 | struct Curl_tree *node)
|
---|
| 103 | {
|
---|
| 104 | static const struct timeval KEY_NOTUSED = {-1, -1}; /* will *NEVER* appear */
|
---|
| 105 |
|
---|
| 106 | if(node == NULL)
|
---|
| 107 | return t;
|
---|
| 108 |
|
---|
| 109 | if(t != NULL) {
|
---|
| 110 | t = Curl_splay(i, t);
|
---|
| 111 | if(compare(i, t->key)==0) {
|
---|
| 112 | /* There already exists a node in the tree with the very same key. Build
|
---|
| 113 | a linked list of nodes. We make the new 'node' struct the new master
|
---|
| 114 | node and make the previous node the first one in the 'same' list. */
|
---|
| 115 |
|
---|
| 116 | node->same = t;
|
---|
| 117 | node->key = i;
|
---|
| 118 | node->smaller = t->smaller;
|
---|
| 119 | node->larger = t->larger;
|
---|
| 120 |
|
---|
| 121 | t->smaller = node; /* in the sub node for this same key, we use the
|
---|
| 122 | smaller pointer to point back to the master
|
---|
| 123 | node */
|
---|
| 124 |
|
---|
| 125 | t->key = KEY_NOTUSED; /* and we set the key in the sub node to NOTUSED
|
---|
| 126 | to quickly identify this node as a subnode */
|
---|
| 127 |
|
---|
| 128 | return node; /* new root node */
|
---|
| 129 | }
|
---|
| 130 | }
|
---|
| 131 |
|
---|
| 132 | if(t == NULL) {
|
---|
| 133 | node->smaller = node->larger = NULL;
|
---|
| 134 | }
|
---|
| 135 | else if(compare(i, t->key) < 0) {
|
---|
| 136 | node->smaller = t->smaller;
|
---|
| 137 | node->larger = t;
|
---|
| 138 | t->smaller = NULL;
|
---|
| 139 |
|
---|
| 140 | }
|
---|
| 141 | else {
|
---|
| 142 | node->larger = t->larger;
|
---|
| 143 | node->smaller = t;
|
---|
| 144 | t->larger = NULL;
|
---|
| 145 | }
|
---|
| 146 | node->key = i;
|
---|
| 147 |
|
---|
| 148 | node->same = NULL; /* no identical node (yet) */
|
---|
| 149 | return node;
|
---|
| 150 | }
|
---|
| 151 |
|
---|
| 152 | /* Finds and deletes the best-fit node from the tree. Return a pointer to the
|
---|
| 153 | resulting tree. best-fit means the node with the given or lower key */
|
---|
| 154 | struct Curl_tree *Curl_splaygetbest(struct timeval i,
|
---|
| 155 | struct Curl_tree *t,
|
---|
| 156 | struct Curl_tree **removed)
|
---|
| 157 | {
|
---|
| 158 | struct Curl_tree *x;
|
---|
| 159 |
|
---|
| 160 | if(!t) {
|
---|
| 161 | *removed = NULL; /* none removed since there was no root */
|
---|
| 162 | return NULL;
|
---|
| 163 | }
|
---|
| 164 |
|
---|
| 165 | t = Curl_splay(i, t);
|
---|
| 166 | if(compare(i, t->key) < 0) {
|
---|
| 167 | /* too big node, try the smaller chain */
|
---|
| 168 | if(t->smaller)
|
---|
| 169 | t=Curl_splay(t->smaller->key, t);
|
---|
| 170 | else {
|
---|
| 171 | /* fail */
|
---|
| 172 | *removed = NULL;
|
---|
| 173 | return t;
|
---|
| 174 | }
|
---|
| 175 | }
|
---|
| 176 |
|
---|
| 177 | if(compare(i, t->key) >= 0) { /* found it */
|
---|
| 178 | /* FIRST! Check if there is a list with identical keys */
|
---|
| 179 | x = t->same;
|
---|
| 180 | if(x) {
|
---|
| 181 | /* there is, pick one from the list */
|
---|
| 182 |
|
---|
| 183 | /* 'x' is the new root node */
|
---|
| 184 |
|
---|
| 185 | x->key = t->key;
|
---|
| 186 | x->larger = t->larger;
|
---|
| 187 | x->smaller = t->smaller;
|
---|
| 188 |
|
---|
| 189 | *removed = t;
|
---|
| 190 | return x; /* new root */
|
---|
| 191 | }
|
---|
| 192 |
|
---|
| 193 | if(t->smaller == NULL) {
|
---|
| 194 | x = t->larger;
|
---|
| 195 | }
|
---|
| 196 | else {
|
---|
| 197 | x = Curl_splay(i, t->smaller);
|
---|
| 198 | x->larger = t->larger;
|
---|
| 199 | }
|
---|
| 200 | *removed = t;
|
---|
| 201 |
|
---|
| 202 | return x;
|
---|
| 203 | }
|
---|
| 204 | else {
|
---|
| 205 | *removed = NULL; /* no match */
|
---|
| 206 | return t; /* It wasn't there */
|
---|
| 207 | }
|
---|
| 208 | }
|
---|
| 209 |
|
---|
| 210 |
|
---|
| 211 | /* Deletes the very node we point out from the tree if it's there. Stores a
|
---|
| 212 | * pointer to the new resulting tree in 'newroot'.
|
---|
| 213 | *
|
---|
| 214 | * Returns zero on success and non-zero on errors! TODO: document error codes.
|
---|
| 215 | * When returning error, it does not touch the 'newroot' pointer.
|
---|
| 216 | *
|
---|
| 217 | * NOTE: when the last node of the tree is removed, there's no tree left so
|
---|
| 218 | * 'newroot' will be made to point to NULL.
|
---|
| 219 | *
|
---|
| 220 | * @unittest: 1309
|
---|
| 221 | */
|
---|
| 222 | int Curl_splayremovebyaddr(struct Curl_tree *t,
|
---|
| 223 | struct Curl_tree *removenode,
|
---|
| 224 | struct Curl_tree **newroot)
|
---|
| 225 | {
|
---|
| 226 | static const struct timeval KEY_NOTUSED = {-1, -1}; /* will *NEVER* appear */
|
---|
| 227 | struct Curl_tree *x;
|
---|
| 228 |
|
---|
| 229 | if(!t || !removenode)
|
---|
| 230 | return 1;
|
---|
| 231 |
|
---|
| 232 | if(compare(KEY_NOTUSED, removenode->key) == 0) {
|
---|
| 233 | /* Key set to NOTUSED means it is a subnode within a 'same' linked list
|
---|
| 234 | and thus we can unlink it easily. The 'smaller' link of a subnode
|
---|
| 235 | links to the parent node. */
|
---|
| 236 | if(removenode->smaller == NULL)
|
---|
| 237 | return 3;
|
---|
| 238 |
|
---|
| 239 | removenode->smaller->same = removenode->same;
|
---|
| 240 | if(removenode->same)
|
---|
| 241 | removenode->same->smaller = removenode->smaller;
|
---|
| 242 |
|
---|
| 243 | /* Ensures that double-remove gets caught. */
|
---|
| 244 | removenode->smaller = NULL;
|
---|
| 245 |
|
---|
| 246 | /* voila, we're done! */
|
---|
| 247 | *newroot = t; /* return the same root */
|
---|
| 248 | return 0;
|
---|
| 249 | }
|
---|
| 250 |
|
---|
| 251 | t = Curl_splay(removenode->key, t);
|
---|
| 252 |
|
---|
| 253 | /* First make sure that we got the same root node as the one we want
|
---|
| 254 | to remove, as otherwise we might be trying to remove a node that
|
---|
| 255 | isn't actually in the tree.
|
---|
| 256 |
|
---|
| 257 | We cannot just compare the keys here as a double remove in quick
|
---|
| 258 | succession of a node with key != KEY_NOTUSED && same != NULL
|
---|
| 259 | could return the same key but a different node. */
|
---|
| 260 | if(t != removenode)
|
---|
| 261 | return 2;
|
---|
| 262 |
|
---|
| 263 | /* Check if there is a list with identical sizes, as then we're trying to
|
---|
| 264 | remove the root node of a list of nodes with identical keys. */
|
---|
| 265 | x = t->same;
|
---|
| 266 | if(x) {
|
---|
| 267 | /* 'x' is the new root node, we just make it use the root node's
|
---|
| 268 | smaller/larger links */
|
---|
| 269 |
|
---|
| 270 | x->key = t->key;
|
---|
| 271 | x->larger = t->larger;
|
---|
| 272 | x->smaller = t->smaller;
|
---|
| 273 | }
|
---|
| 274 | else {
|
---|
| 275 | /* Remove the root node */
|
---|
| 276 | if(t->smaller == NULL)
|
---|
| 277 | x = t->larger;
|
---|
| 278 | else {
|
---|
| 279 | x = Curl_splay(removenode->key, t->smaller);
|
---|
| 280 | x->larger = t->larger;
|
---|
| 281 | }
|
---|
| 282 | }
|
---|
| 283 |
|
---|
| 284 | *newroot = x; /* store new root pointer */
|
---|
| 285 |
|
---|
| 286 | return 0;
|
---|
| 287 | }
|
---|
| 288 |
|
---|