splay.c (7964B)
1 /*************************************************************************** 2 * _ _ ____ _ 3 * Project ___| | | | _ \| | 4 * / __| | | | |_) | | 5 * | (__| |_| | _ <| |___ 6 * \___|\___/|_| \_\_____| 7 * 8 * Copyright (C) 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.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 * SPDX-License-Identifier: curl 22 * 23 ***************************************************************************/ 24 25 #include "curl_setup.h" 26 27 #include "curlx/timeval.h" 28 #include "splay.h" 29 30 /* 31 * This macro compares two node keys i and j and returns: 32 * 33 * negative value: when i is smaller than j 34 * zero : when i is equal to j 35 * positive when : when i is larger than j 36 */ 37 #define compare(i,j) curlx_timediff_us(i,j) 38 39 /* 40 * Splay using the key i (which may or may not be in the tree.) The starting 41 * root is t. 42 */ 43 struct Curl_tree *Curl_splay(struct curltime i, 44 struct Curl_tree *t) 45 { 46 struct Curl_tree N, *l, *r, *y; 47 48 if(!t) 49 return NULL; 50 N.smaller = N.larger = NULL; 51 l = r = &N; 52 53 for(;;) { 54 timediff_t comp = compare(i, t->key); 55 if(comp < 0) { 56 if(!t->smaller) 57 break; 58 if(compare(i, t->smaller->key) < 0) { 59 y = t->smaller; /* rotate smaller */ 60 t->smaller = y->larger; 61 y->larger = t; 62 t = y; 63 if(!t->smaller) 64 break; 65 } 66 r->smaller = t; /* link smaller */ 67 r = t; 68 t = t->smaller; 69 } 70 else if(comp > 0) { 71 if(!t->larger) 72 break; 73 if(compare(i, t->larger->key) > 0) { 74 y = t->larger; /* rotate larger */ 75 t->larger = y->smaller; 76 y->smaller = t; 77 t = y; 78 if(!t->larger) 79 break; 80 } 81 l->larger = t; /* link larger */ 82 l = t; 83 t = t->larger; 84 } 85 else 86 break; 87 } 88 89 l->larger = t->smaller; /* assemble */ 90 r->smaller = t->larger; 91 t->smaller = N.larger; 92 t->larger = N.smaller; 93 94 return t; 95 } 96 97 /* Insert key i into the tree t. Return a pointer to the resulting tree or 98 * NULL if something went wrong. 99 * 100 * @unittest: 1309 101 */ 102 struct Curl_tree *Curl_splayinsert(struct curltime i, 103 struct Curl_tree *t, 104 struct Curl_tree *node) 105 { 106 static const struct curltime KEY_NOTUSED = { 107 ~0, -1 108 }; /* will *NEVER* appear */ 109 110 DEBUGASSERT(node); 111 112 if(t) { 113 t = Curl_splay(i, t); 114 DEBUGASSERT(t); 115 if(compare(i, t->key) == 0) { 116 /* There already exists a node in the tree with the same key. Build a 117 doubly-linked circular list of nodes. We add the new 'node' struct to 118 the end of this list. */ 119 120 node->key = KEY_NOTUSED; /* we set the key in the sub node to NOTUSED 121 to quickly identify this node as a subnode */ 122 node->samen = t; 123 node->samep = t->samep; 124 t->samep->samen = node; 125 t->samep = node; 126 127 return t; /* the root node always stays the same */ 128 } 129 } 130 131 if(!t) { 132 node->smaller = node->larger = NULL; 133 } 134 else if(compare(i, t->key) < 0) { 135 node->smaller = t->smaller; 136 node->larger = t; 137 t->smaller = NULL; 138 139 } 140 else { 141 node->larger = t->larger; 142 node->smaller = t; 143 t->larger = NULL; 144 } 145 node->key = i; 146 147 /* no identical nodes (yet), we are the only one in the list of nodes */ 148 node->samen = node; 149 node->samep = node; 150 return node; 151 } 152 153 /* Finds and deletes the best-fit node from the tree. Return a pointer to the 154 resulting tree. best-fit means the smallest node if it is not larger than 155 the key */ 156 struct Curl_tree *Curl_splaygetbest(struct curltime i, 157 struct Curl_tree *t, 158 struct Curl_tree **removed) 159 { 160 static const struct curltime tv_zero = {0, 0}; 161 struct Curl_tree *x; 162 163 if(!t) { 164 *removed = NULL; /* none removed since there was no root */ 165 return NULL; 166 } 167 168 /* find smallest */ 169 t = Curl_splay(tv_zero, t); 170 DEBUGASSERT(t); 171 if(compare(i, t->key) < 0) { 172 /* even the smallest is too big */ 173 *removed = NULL; 174 return t; 175 } 176 177 /* FIRST! Check if there is a list with identical keys */ 178 x = t->samen; 179 if(x != t) { 180 /* there is, pick one from the list */ 181 182 /* 'x' is the new root node */ 183 184 x->key = t->key; 185 x->larger = t->larger; 186 x->smaller = t->smaller; 187 x->samep = t->samep; 188 t->samep->samen = x; 189 190 *removed = t; 191 return x; /* new root */ 192 } 193 194 /* we splayed the tree to the smallest element, there is no smaller */ 195 x = t->larger; 196 *removed = t; 197 198 return x; 199 } 200 201 202 /* Deletes the node we point out from the tree if it is there. Stores a 203 * pointer to the new resulting tree in 'newroot'. 204 * 205 * Returns zero on success and non-zero on errors! 206 * When returning error, it does not touch the 'newroot' pointer. 207 * 208 * NOTE: when the last node of the tree is removed, there is no tree left so 209 * 'newroot' will be made to point to NULL. 210 * 211 * @unittest: 1309 212 */ 213 int Curl_splayremove(struct Curl_tree *t, 214 struct Curl_tree *removenode, 215 struct Curl_tree **newroot) 216 { 217 static const struct curltime KEY_NOTUSED = { 218 ~0, -1 219 }; /* will *NEVER* appear */ 220 struct Curl_tree *x; 221 222 if(!t) 223 return 1; 224 225 DEBUGASSERT(removenode); 226 227 if(compare(KEY_NOTUSED, removenode->key) == 0) { 228 /* Key set to NOTUSED means it is a subnode within a 'same' linked list 229 and thus we can unlink it easily. */ 230 if(removenode->samen == removenode) 231 /* A non-subnode should never be set to KEY_NOTUSED */ 232 return 3; 233 234 removenode->samep->samen = removenode->samen; 235 removenode->samen->samep = removenode->samep; 236 237 /* Ensures that double-remove gets caught. */ 238 removenode->samen = removenode; 239 240 *newroot = t; /* return the same root */ 241 return 0; 242 } 243 244 t = Curl_splay(removenode->key, t); 245 DEBUGASSERT(t); 246 247 /* First make sure that we got the same root node as the one we want 248 to remove, as otherwise we might be trying to remove a node that 249 is not actually in the tree. 250 251 We cannot just compare the keys here as a double remove in quick 252 succession of a node with key != KEY_NOTUSED && same != NULL 253 could return the same key but a different node. */ 254 if(t != removenode) 255 return 2; 256 257 /* Check if there is a list with identical sizes, as then we are trying to 258 remove the root node of a list of nodes with identical keys. */ 259 x = t->samen; 260 if(x != t) { 261 /* 'x' is the new root node, we just make it use the root node's 262 smaller/larger links */ 263 264 x->key = t->key; 265 x->larger = t->larger; 266 x->smaller = t->smaller; 267 x->samep = t->samep; 268 t->samep->samen = x; 269 } 270 else { 271 /* Remove the root node */ 272 if(!t->smaller) 273 x = t->larger; 274 else { 275 x = Curl_splay(removenode->key, t->smaller); 276 DEBUGASSERT(x); 277 x->larger = t->larger; 278 } 279 } 280 281 *newroot = x; /* store new root pointer */ 282 283 return 0; 284 } 285 286 /* set and get the custom payload for this tree node */ 287 void Curl_splayset(struct Curl_tree *node, void *payload) 288 { 289 DEBUGASSERT(node); 290 node->ptr = payload; 291 } 292 293 void *Curl_splayget(struct Curl_tree *node) 294 { 295 DEBUGASSERT(node); 296 return node->ptr; 297 }