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 "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) Curl_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 */
Curl_splay(struct curltime i,struct Curl_tree * t)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 */
Curl_splayinsert(struct curltime i,struct Curl_tree * t,struct Curl_tree * node)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 very same key. Build
117 a doubly-linked circular list of nodes. We add the new 'node' struct
118 to 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 */
Curl_splaygetbest(struct curltime i,struct Curl_tree * t,struct Curl_tree ** removed)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 very 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 */
Curl_splayremove(struct Curl_tree * t,struct Curl_tree * removenode,struct Curl_tree ** newroot)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 */
Curl_splayset(struct Curl_tree * node,void * payload)287 void Curl_splayset(struct Curl_tree *node, void *payload)
288 {
289 DEBUGASSERT(node);
290 node->ptr = payload;
291 }
292
Curl_splayget(struct Curl_tree * node)293 void *Curl_splayget(struct Curl_tree *node)
294 {
295 DEBUGASSERT(node);
296 return node->ptr;
297 }
298
