1 /*************************************************************************** 2 * _ _ ____ _ 3 * Project ___| | | | _ \| | 4 * / __| | | | |_) | | 5 * | (__| |_| | _ <| |___ 6 * \___|\___/|_| \_\_____| 7 * 8 * Copyright (C) 1997 - 2015, Daniel Stenberg, <daniel (at) 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 289
