2
0

splay.c 7.4 KB

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