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 best-fit node from the tree. Return a pointer to the
|
---|
153 | resulting tree. best-fit 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 non-zero 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 double-remove 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 |
|
---|