splay.c 7.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288
  1. /***************************************************************************
  2. * _ _ ____ _
  3. * Project ___| | | | _ \| |
  4. * / __| | | | |_) | |
  5. * | (__| |_| | _ <| |___
  6. * \___|\___/|_| \_\_____|
  7. *
  8. * Copyright (C) 1997 - 2014, 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 http://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. #include "curl_setup.h"
  23. #include "splay.h"
  24. /*
  25. * This macro compares two node keys i and j and returns:
  26. *
  27. * negative value: when i is smaller than j
  28. * zero : when i is equal to j
  29. * positive when : when i is larger than j
  30. */
  31. #define compare(i,j) Curl_splaycomparekeys((i),(j))
  32. /*
  33. * Splay using the key i (which may or may not be in the tree.) The starting
  34. * root is t.
  35. */
  36. struct Curl_tree *Curl_splay(struct timeval i,
  37. struct Curl_tree *t)
  38. {
  39. struct Curl_tree N, *l, *r, *y;
  40. long comp;
  41. if(t == NULL)
  42. return t;
  43. N.smaller = N.larger = NULL;
  44. l = r = &N;
  45. for(;;) {
  46. comp = compare(i, t->key);
  47. if(comp < 0) {
  48. if(t->smaller == NULL)
  49. break;
  50. if(compare(i, t->smaller->key) < 0) {
  51. y = t->smaller; /* rotate smaller */
  52. t->smaller = y->larger;
  53. y->larger = t;
  54. t = y;
  55. if(t->smaller == NULL)
  56. break;
  57. }
  58. r->smaller = t; /* link smaller */
  59. r = t;
  60. t = t->smaller;
  61. }
  62. else if(comp > 0) {
  63. if(t->larger == NULL)
  64. break;
  65. if(compare(i, t->larger->key) > 0) {
  66. y = t->larger; /* rotate larger */
  67. t->larger = y->smaller;
  68. y->smaller = t;
  69. t = y;
  70. if(t->larger == NULL)
  71. break;
  72. }
  73. l->larger = t; /* link larger */
  74. l = t;
  75. t = t->larger;
  76. }
  77. else
  78. break;
  79. }
  80. l->larger = t->smaller; /* assemble */
  81. r->smaller = t->larger;
  82. t->smaller = N.larger;
  83. t->larger = N.smaller;
  84. return t;
  85. }
  86. /* Insert key i into the tree t. Return a pointer to the resulting tree or
  87. * NULL if something went wrong.
  88. *
  89. * @unittest: 1309
  90. */
  91. struct Curl_tree *Curl_splayinsert(struct timeval i,
  92. struct Curl_tree *t,
  93. struct Curl_tree *node)
  94. {
  95. static const struct timeval KEY_NOTUSED = {-1,-1}; /* will *NEVER* appear */
  96. if(node == NULL)
  97. return t;
  98. if(t != NULL) {
  99. t = Curl_splay(i,t);
  100. if(compare(i, t->key)==0) {
  101. /* There already exists a node in the tree with the very same key. Build
  102. a linked list of nodes. We make the new 'node' struct the new master
  103. node and make the previous node the first one in the 'same' list. */
  104. node->same = t;
  105. node->key = i;
  106. node->smaller = t->smaller;
  107. node->larger = t->larger;
  108. t->smaller = node; /* in the sub node for this same key, we use the
  109. smaller pointer to point back to the master
  110. node */
  111. t->key = KEY_NOTUSED; /* and we set the key in the sub node to NOTUSED
  112. to quickly identify this node as a subnode */
  113. return node; /* new root node */
  114. }
  115. }
  116. if(t == NULL) {
  117. node->smaller = node->larger = NULL;
  118. }
  119. else if(compare(i, t->key) < 0) {
  120. node->smaller = t->smaller;
  121. node->larger = t;
  122. t->smaller = NULL;
  123. }
  124. else {
  125. node->larger = t->larger;
  126. node->smaller = t;
  127. t->larger = NULL;
  128. }
  129. node->key = i;
  130. node->same = NULL; /* no identical node (yet) */
  131. return node;
  132. }
  133. /* Finds and deletes the best-fit node from the tree. Return a pointer to the
  134. resulting tree. best-fit means the node with the given or lower key */
  135. struct Curl_tree *Curl_splaygetbest(struct timeval i,
  136. struct Curl_tree *t,
  137. struct Curl_tree **removed)
  138. {
  139. struct Curl_tree *x;
  140. if(!t) {
  141. *removed = NULL; /* none removed since there was no root */
  142. return NULL;
  143. }
  144. t = Curl_splay(i,t);
  145. if(compare(i, t->key) < 0) {
  146. /* too big node, try the smaller chain */
  147. if(t->smaller)
  148. t=Curl_splay(t->smaller->key, t);
  149. else {
  150. /* fail */
  151. *removed = NULL;
  152. return t;
  153. }
  154. }
  155. if(compare(i, t->key) >= 0) { /* found it */
  156. /* FIRST! Check if there is a list with identical keys */
  157. x = t->same;
  158. if(x) {
  159. /* there is, pick one from the list */
  160. /* 'x' is the new root node */
  161. x->key = t->key;
  162. x->larger = t->larger;
  163. x->smaller = t->smaller;
  164. *removed = t;
  165. return x; /* new root */
  166. }
  167. if(t->smaller == NULL) {
  168. x = t->larger;
  169. }
  170. else {
  171. x = Curl_splay(i, t->smaller);
  172. x->larger = t->larger;
  173. }
  174. *removed = t;
  175. return x;
  176. }
  177. else {
  178. *removed = NULL; /* no match */
  179. return t; /* It wasn't there */
  180. }
  181. }
  182. /* Deletes the very node we point out from the tree if it's there. Stores a
  183. * pointer to the new resulting tree in 'newroot'.
  184. *
  185. * Returns zero on success and non-zero on errors! TODO: document error codes.
  186. * When returning error, it does not touch the 'newroot' pointer.
  187. *
  188. * NOTE: when the last node of the tree is removed, there's no tree left so
  189. * 'newroot' will be made to point to NULL.
  190. *
  191. * @unittest: 1309
  192. */
  193. int Curl_splayremovebyaddr(struct Curl_tree *t,
  194. struct Curl_tree *removenode,
  195. struct Curl_tree **newroot)
  196. {
  197. static const struct timeval KEY_NOTUSED = {-1,-1}; /* will *NEVER* appear */
  198. struct Curl_tree *x;
  199. if(!t || !removenode)
  200. return 1;
  201. if(compare(KEY_NOTUSED, removenode->key) == 0) {
  202. /* Key set to NOTUSED means it is a subnode within a 'same' linked list
  203. and thus we can unlink it easily. The 'smaller' link of a subnode
  204. links to the parent node. */
  205. if(removenode->smaller == NULL)
  206. return 3;
  207. removenode->smaller->same = removenode->same;
  208. if(removenode->same)
  209. removenode->same->smaller = removenode->smaller;
  210. /* Ensures that double-remove gets caught. */
  211. removenode->smaller = NULL;
  212. /* voila, we're done! */
  213. *newroot = t; /* return the same root */
  214. return 0;
  215. }
  216. t = Curl_splay(removenode->key, t);
  217. /* First make sure that we got the same root node as the one we want
  218. to remove, as otherwise we might be trying to remove a node that
  219. isn't actually in the tree.
  220. We cannot just compare the keys here as a double remove in quick
  221. succession of a node with key != KEY_NOTUSED && same != NULL
  222. could return the same key but a different node. */
  223. if(t != removenode)
  224. return 2;
  225. /* Check if there is a list with identical sizes, as then we're trying to
  226. remove the root node of a list of nodes with identical keys. */
  227. x = t->same;
  228. if(x) {
  229. /* 'x' is the new root node, we just make it use the root node's
  230. smaller/larger links */
  231. x->key = t->key;
  232. x->larger = t->larger;
  233. x->smaller = t->smaller;
  234. }
  235. else {
  236. /* Remove the root node */
  237. if(t->smaller == NULL)
  238. x = t->larger;
  239. else {
  240. x = Curl_splay(removenode->key, t->smaller);
  241. x->larger = t->larger;
  242. }
  243. }
  244. *newroot = x; /* store new root pointer */
  245. return 0;
  246. }