1 /***************************************************************************
2  *                                  _   _ ____  _
3  *  Project                     ___| | | |  _ \| |
4  *                             / __| | | | |_) | |
5  *                            | (__| |_| |  _ <| |___
6  *                             \___|\___/|_| \_\_____|
7  *
8  * Copyright (C) 1997 - 2019, 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  */
Curl_splay(struct curltime i,struct Curl_tree * t)40 struct Curl_tree *Curl_splay(struct curltime i,
41                              struct Curl_tree *t)
42 {
43   struct Curl_tree N, *l, *r, *y;
44 
45   if(t == NULL)
46     return t;
47   N.smaller = N.larger = NULL;
48   l = r = &N;
49 
50   for(;;) {
51     long comp = compare(i, t->key);
52     if(comp < 0) {
53       if(t->smaller == NULL)
54         break;
55       if(compare(i, t->smaller->key) < 0) {
56         y = t->smaller;                           /* rotate smaller */
57         t->smaller = y->larger;
58         y->larger = t;
59         t = y;
60         if(t->smaller == NULL)
61           break;
62       }
63       r->smaller = t;                               /* link smaller */
64       r = t;
65       t = t->smaller;
66     }
67     else if(comp > 0) {
68       if(t->larger == NULL)
69         break;
70       if(compare(i, t->larger->key) > 0) {
71         y = t->larger;                          /* rotate larger */
72         t->larger = y->smaller;
73         y->smaller = t;
74         t = y;
75         if(t->larger == NULL)
76           break;
77       }
78       l->larger = t;                              /* link larger */
79       l = t;
80       t = t->larger;
81     }
82     else
83       break;
84   }
85 
86   l->larger = t->smaller;                                /* assemble */
87   r->smaller = t->larger;
88   t->smaller = N.larger;
89   t->larger = N.smaller;
90 
91   return t;
92 }
93 
94 /* Insert key i into the tree t.  Return a pointer to the resulting tree or
95  * NULL if something went wrong.
96  *
97  * @unittest: 1309
98  */
Curl_splayinsert(struct curltime i,struct Curl_tree * t,struct Curl_tree * node)99 struct Curl_tree *Curl_splayinsert(struct curltime i,
100                                    struct Curl_tree *t,
101                                    struct Curl_tree *node)
102 {
103   static const struct curltime KEY_NOTUSED = {
104     (time_t)-1, (unsigned int)-1
105   }; /* will *NEVER* appear */
106 
107   if(node == NULL)
108     return t;
109 
110   if(t != NULL) {
111     t = Curl_splay(i, t);
112     if(compare(i, t->key) == 0) {
113       /* There already exists a node in the tree with the very same key. Build
114          a doubly-linked circular list of nodes. We add the new 'node' struct
115          to the end of this list. */
116 
117       node->key = KEY_NOTUSED; /* we set the key in the sub node to NOTUSED
118                                   to quickly identify this node as a subnode */
119       node->samen = t;
120       node->samep = t->samep;
121       t->samep->samen = node;
122       t->samep = node;
123 
124       return t; /* the root node always stays the same */
125     }
126   }
127 
128   if(t == NULL) {
129     node->smaller = node->larger = NULL;
130   }
131   else if(compare(i, t->key) < 0) {
132     node->smaller = t->smaller;
133     node->larger = t;
134     t->smaller = NULL;
135 
136   }
137   else {
138     node->larger = t->larger;
139     node->smaller = t;
140     t->larger = NULL;
141   }
142   node->key = i;
143 
144   /* no identical nodes (yet), we are the only one in the list of nodes */
145   node->samen = node;
146   node->samep = node;
147   return node;
148 }
149 
150 /* Finds and deletes the best-fit node from the tree. Return a pointer to the
151    resulting tree.  best-fit means the smallest node if it is not larger than
152    the key */
Curl_splaygetbest(struct curltime i,struct Curl_tree * t,struct Curl_tree ** removed)153 struct Curl_tree *Curl_splaygetbest(struct curltime i,
154                                     struct Curl_tree *t,
155                                     struct Curl_tree **removed)
156 {
157   static struct curltime tv_zero = {0, 0};
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   /* find smallest */
166   t = Curl_splay(tv_zero, t);
167   if(compare(i, t->key) < 0) {
168     /* even the smallest is too big */
169     *removed = NULL;
170     return t;
171   }
172 
173   /* FIRST! Check if there is a list with identical keys */
174   x = t->samen;
175   if(x != t) {
176     /* there is, pick one from the list */
177 
178     /* 'x' is the new root node */
179 
180     x->key = t->key;
181     x->larger = t->larger;
182     x->smaller = t->smaller;
183     x->samep = t->samep;
184     t->samep->samen = x;
185 
186     *removed = t;
187     return x; /* new root */
188   }
189 
190   /* we splayed the tree to the smallest element, there is no smaller */
191   x = t->larger;
192   *removed = t;
193 
194   return x;
195 }
196 
197 
198 /* Deletes the very node we point out from the tree if it's there. Stores a
199  * pointer to the new resulting tree in 'newroot'.
200  *
201  * Returns zero on success and non-zero on errors!
202  * When returning error, it does not touch the 'newroot' pointer.
203  *
204  * NOTE: when the last node of the tree is removed, there's no tree left so
205  * 'newroot' will be made to point to NULL.
206  *
207  * @unittest: 1309
208  */
Curl_splayremovebyaddr(struct Curl_tree * t,struct Curl_tree * removenode,struct Curl_tree ** newroot)209 int Curl_splayremovebyaddr(struct Curl_tree *t,
210                            struct Curl_tree *removenode,
211                            struct Curl_tree **newroot)
212 {
213   static const struct curltime KEY_NOTUSED = {
214     (time_t)-1, (unsigned int)-1
215   }; /* will *NEVER* appear */
216   struct Curl_tree *x;
217 
218   if(!t || !removenode)
219     return 1;
220 
221   if(compare(KEY_NOTUSED, removenode->key) == 0) {
222     /* Key set to NOTUSED means it is a subnode within a 'same' linked list
223        and thus we can unlink it easily. */
224     if(removenode->samen == removenode)
225       /* A non-subnode should never be set to KEY_NOTUSED */
226       return 3;
227 
228     removenode->samep->samen = removenode->samen;
229     removenode->samen->samep = removenode->samep;
230 
231     /* Ensures that double-remove gets caught. */
232     removenode->samen = removenode;
233 
234     *newroot = t; /* return the same root */
235     return 0;
236   }
237 
238   t = Curl_splay(removenode->key, t);
239 
240   /* First make sure that we got the same root node as the one we want
241      to remove, as otherwise we might be trying to remove a node that
242      isn't actually in the tree.
243 
244      We cannot just compare the keys here as a double remove in quick
245      succession of a node with key != KEY_NOTUSED && same != NULL
246      could return the same key but a different node. */
247   if(t != removenode)
248     return 2;
249 
250   /* Check if there is a list with identical sizes, as then we're trying to
251      remove the root node of a list of nodes with identical keys. */
252   x = t->samen;
253   if(x != t) {
254     /* 'x' is the new root node, we just make it use the root node's
255        smaller/larger links */
256 
257     x->key = t->key;
258     x->larger = t->larger;
259     x->smaller = t->smaller;
260     x->samep = t->samep;
261     t->samep->samen = x;
262   }
263   else {
264     /* Remove the root node */
265     if(t->smaller == NULL)
266       x = t->larger;
267     else {
268       x = Curl_splay(removenode->key, t->smaller);
269       x->larger = t->larger;
270     }
271   }
272 
273   *newroot = x; /* store new root pointer */
274 
275   return 0;
276 }
277