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 bestfit node from the tree. Return a pointer to the


153  resulting tree. bestfit 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 nonzero 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 doubleremove 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 

