1 /*************************************************************************** 2 * _ _ ____ _ 3 * Project ___| | | | _ \| | 4 * / __| | | | |_) | | 5 * | (__| |_| | _ <| |___ 6 * \___|\___/|_| \_\_____| 7 * 8 * Copyright (C) 1997 - 2017, 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 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 279
