/src/curl/lib/splay.c

Source
/***************************************************************************
 *                                  _   _ ____  _
 *  Project                     ___| | | |  _ \| |
 *                             / __| | | | |_) | |
 *                            | (__| |_| |  _ <| |___
 *                             \___|\___/|_| \_\_____|
 *
 * Copyright (C) Daniel Stenberg, <daniel@haxx.se>, et al.
 *
 * This software is licensed as described in the file COPYING, which
 * you should have received as part of this distribution. The terms
 * are also available at https://curl.se/docs/copyright.html.
 *
 * You may opt to use, copy, modify, merge, publish, distribute and/or sell
 * copies of the Software, and permit persons to whom the Software is
 * furnished to do so, under the terms of the COPYING file.
 *
 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
 * KIND, either express or implied.
 *
 * SPDX-License-Identifier: curl
 *
 ***************************************************************************/
#include "curl_setup.h"

#include "urldata.h"
#include "splay.h"

static struct Curl_tree *splay(timediff_t key,
                               struct Curl_tree *root);

#ifdef UNITTESTS
uint32_t Curl_splayget(struct Curl_tree *node)
{
  DEBUGASSERT(node);
  return node->id;
}

#endif

void Curl_timeouts_init(struct Curl_timeouts *timeouts,
                        const struct curltime *ptime_base)
{
  struct curltime time_base = ptime_base ? *ptime_base : curlx_now();
  timeouts->tree = NULL;
  timeouts->time_base_sec = time_base.tv_sec;
}

bool Curl_timeouts_has(struct Curl_easy *data)
{
  struct Curl_tree *node = data ? &data->state.timeouts.splaynode : NULL;
  return node && node->registered;
}

timediff_t Curl_timeouts_offset_us(struct Curl_timeouts *timeouts,
                                   const struct curltime *pts)
{
  struct curltime time_base;
  time_base.tv_sec = timeouts->time_base_sec;
  time_base.tv_usec = 0;
  return curlx_ptimediff_us(pts, &time_base);
}

int Curl_timeouts_next_ms(struct Curl_timeouts *timeouts,
                          const struct curltime *pnow,
                          timediff_t *pexpire_offset_us,
                          uint32_t *pmid)
{
  if(timeouts->tree) { /* splay the lowest key to the root */
    timeouts->tree = splay(TIMEDIFF_T_MIN, timeouts->tree);
  }

  if(timeouts->tree) {
    timediff_t elapsed_us = Curl_timeouts_offset_us(timeouts, pnow);
    timediff_t delta_us = timeouts->tree->key - elapsed_us;
    if(pmid)
      *pmid = timeouts->tree->id;
    if(pexpire_offset_us)
      *pexpire_offset_us = timeouts->tree->key;
    if(delta_us > 0) { /* expires in the future */
      timediff_t ms = curlx_us_to_ceil_ms(delta_us);
      return (ms > INT_MAX) ? INT_MAX : (int)ms;
    }
    else /* has expired */
      return 0;
  }
  if(pmid)
    *pmid = UINT32_MAX;
  if(pexpire_offset_us)
    *pexpire_offset_us = 0;
  return -1;
}

/*
 * Splay using the key i (which may or may not be in the tree).
 * This rotates the tree, so:
 * - root->smaller has all nodes smaller than `key`
 * - root->larger has all nodes larger than `key`
 * - root->key may equal `key` or not
 * <https://en.wikipedia.org/wiki/Splay_tree>
 */
struct Curl_tree *splay(timediff_t key,
                             struct Curl_tree *root)
{
  struct Curl_tree N, *l, *r, *y;

  if(!root)
    return NULL;
  N.smaller = N.larger = NULL;
  l = r = &N;

  for(;;) {
    if(key < root->key) {
      /* key is somewhere in root->smaller branch */
      if(!root->smaller)  /* which is empty, done */
        break;
      if(key < root->smaller->key) {
        /* key is somewhere in root->smaller->smaller, make a "Zig step" */
        y = root->smaller;
        root->smaller = y->larger;
        y->larger = root;
        root = y;
        if(!root->smaller)
          break;
      }
      /* Making root->smaller the new root, the old root is no longer
       * referenced. Remember it in the N tree's `r`ight/larger side.
       * Everything in old root is smaller than what the right side
       * of N already has, so it gets added to r->smaller. */
      r->smaller = root;
      r = root;
      root = root->smaller;
    }
    else if(key > root->key) {
      /* key is somewhere in root->larger branch */
      if(!root->larger)  /* which is empty, done */
        break;
      if(key > root->larger->key) {
        /* key is somewhere in root->larger->larger, make a "Zig step" */
        y = root->larger;
        root->larger = y->smaller;
        y->smaller = root;
        root = y;
        if(!root->larger)
          break;
      }
      /* Making root->larger the new root, the old root is no longer
       * referenced. Remember it in the N tree's `l`eft/smaller side.
       * Everything in old root is larger than what the left side
       * of N already has, so it gets added to l->larger. */
      l->larger = root;
      l = root;
      root = root->larger;
    }
    else  /* exact match, root is key, done */
      break;
  }

  /* Put it all together again.
   * root->smaller has everything larger than current `l`.
   * root->larger has everything smaller than current `r`. */
  l->larger = root->smaller;
  r->smaller = root->larger;
  root->smaller = N.larger;
  root->larger = N.smaller;

  return root;
}

/* Insert key i into the tree t. Return a pointer to the resulting tree or
 * NULL if something went wrong.
 *
 * @unittest 1309
 */
UNITTEST struct Curl_tree *splayinsert(timediff_t key,
                                       struct Curl_tree *root,
                                       struct Curl_tree *node,
                                       uint32_t id);
UNITTEST struct Curl_tree *splayinsert(timediff_t key,
                                       struct Curl_tree *root,
                                       struct Curl_tree *node,
                                       uint32_t id)
{
  DEBUGASSERT(node);

  node->key = key;
  node->id = id;
  node->same = NULL;
  node->registered = TRUE;
  if(root) {
    root = splay(key, root);
    DEBUGASSERT(root);
    if(key == root->key) {
      /* There already exists a node in the tree with the same key.
         Append the new node to the `same` list. */
      struct Curl_tree **panchor = &root->same;
      while(*panchor)
        panchor = &(*panchor)->same;
      *panchor = node;
      return root; /* the root node always stays the same */
    }
  }

  /* node becomes the new root. Insert old root as sub-branch. */
  if(!root) {
    node->smaller = node->larger = NULL;
  }
  else if(key < root->key) {
    node->smaller = root->smaller;
    node->larger = root;
    root->smaller = NULL;
  }
  else {
    node->larger = root->larger;
    node->smaller = root;
    root->larger = NULL;
  }

  return node;
}

void Curl_timeouts_add(struct Curl_timeouts *timeouts,
                       struct Curl_easy *data,
                       timediff_t offset_us)
{
  struct Curl_tree *node = &data->state.timeouts.splaynode;
  DEBUGASSERT(!node->registered);
  timeouts->tree = splayinsert(offset_us, timeouts->tree,
                               node, data->mid);
}

/* Finds and deletes the best-fit node from the tree. Return a pointer to the
   resulting tree. best-fit means the smallest node if it is not larger than
   the key

   @unittest 1309
*/
UNITTEST struct Curl_tree *splaygetbest(timediff_t key,
                                        struct Curl_tree *root,
                                        struct Curl_tree **removed);
UNITTEST struct Curl_tree *splaygetbest(timediff_t key,
                                        struct Curl_tree *root,
                                        struct Curl_tree **removed)
{
  struct Curl_tree *x;

  if(!root) {
    *removed = NULL; /* none removed since there was no root */
    return NULL;
  }

  /* find smallest */
  root = splay(TIMEDIFF_T_MIN, root);
  DEBUGASSERT(root);
  if(key < root->key) {
    /* even the smallest is too big */
    *removed = NULL;
    return root;
  }

  /* FIRST! Check if there is a list with identical keys */
  if(root->same) {
    x = root->same;
    DEBUGASSERT(x->key == root->key);
    /* 'x' becomes the new root node */
    x->larger = root->larger;
    x->smaller = root->smaller;
    root->same = NULL;
    root->registered = FALSE;
    *removed = root;
    return x; /* new root */
  }

  /* we splayed the tree to the smallest element, there is no smaller */
  x = root->larger;
  root->registered = FALSE;
  *removed = root;

  return x;
}

bool Curl_timeouts_remove_expired(struct Curl_timeouts *timeouts,
                                  const struct curltime *ts,
                                  uint32_t *pmid)
{
  if(timeouts->tree) {
    struct Curl_tree *t = NULL;
    timediff_t elapsed_us = Curl_timeouts_offset_us(timeouts, ts);
    timeouts->tree = splaygetbest(elapsed_us, timeouts->tree, &t);
    if(t) {
      *pmid = t->id;
      return TRUE;
    }
  }
  *pmid = UINT32_MAX;
  return FALSE;
}

/* Deletes the node we point out from the tree if it is there. Stores a
 * pointer to the new resulting tree in 'newroot'.
 *
 * Returns zero on success and non-zero on errors!
 * When returning error, it does not touch the 'newroot' pointer.
 *
 * NOTE: when the last node of the tree is removed, there is no tree left so
 * 'newroot' will be made to point to NULL.
 *
 * @unittest 1309
 */
UNITTEST int splayremove(struct Curl_tree *root,
                         struct Curl_tree *removenode,
                         struct Curl_tree **newroot);
UNITTEST int splayremove(struct Curl_tree *root,
                         struct Curl_tree *removenode,
                         struct Curl_tree **newroot)
{
  struct Curl_tree *x;

  if(!root)
    return 1;

  DEBUGASSERT(removenode);
  if(!removenode->registered)
    return 2;

  root = splay(removenode->key, root);
  DEBUGASSERT(root);

  /* First make sure that we got the same root key as the one we want
     to remove, as otherwise we might be trying to remove a node that
     is not actually in the tree. */
  if(root->key != removenode->key) {
    DEBUGASSERT(0);
    return 2;
  }

  if(root != removenode) {
    /* Should be in the root->same list then */
    struct Curl_tree **panchor;
    for(panchor = &root->same; *panchor; panchor = &(*panchor)->same) {
      if(*panchor == removenode) {
        *panchor = removenode->same;
        removenode->same = NULL;
        removenode->registered = FALSE;
        *newroot = root;
        return 0;
      }
    }
    /* not found in same list, error */
    DEBUGASSERT(0);
    return 2;
  }
  /* removing the root node */
  if(root->same) {
    /* 'x' is the new root node, we make it use the root node's
       smaller/larger links */
    x = root->same;
    x->larger = root->larger;
    x->smaller = root->smaller;
    root->same = NULL;
  }
  else {
    /* Remove the root node */
    if(!root->smaller)
      x = root->larger;
    else {
      x = splay(removenode->key, root->smaller);
      DEBUGASSERT(x);
      x->larger = root->larger;
    }
  }
  removenode->registered = FALSE;
  *newroot = x; /* return new root */
  return 0;
}

bool Curl_timeouts_remove(struct Curl_timeouts *timeouts,
                          struct Curl_easy *data)
{
  struct Curl_tree *node = &data->state.timeouts.splaynode;
  if(node->registered) {
    int rc = splayremove(timeouts->tree, node, &timeouts->tree);
#ifdef DEBUGBUILD
    if(rc)
      curl_mfprintf(stderr, "Internal error removing splay node = %d\n", rc);
#else
    (void)rc;
#endif
    return TRUE;
  }
  return FALSE;
}

Coverage Report

Created: 2026-10-28 07:17

Line	Count	Source
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		#include "curl_setup.h"
25
26		#include "urldata.h"
27		#include "splay.h"
28
29		static struct Curl_tree *splay(timediff_t key,
30		struct Curl_tree *root);
31
32		#ifdef UNITTESTS
33		uint32_t Curl_splayget(struct Curl_tree *node)
34	0	{
35	0	DEBUGASSERT(node);
36	0	return node->id;
37	0	}
38
39		#endif
40
41		void Curl_timeouts_init(struct Curl_timeouts *timeouts,
42		const struct curltime *ptime_base)
43	447k	{
44	447k	struct curltime time_base = ptime_base ? *ptime_base : curlx_now();
45	447k	timeouts->tree = NULL;
46	447k	timeouts->time_base_sec = time_base.tv_sec;
47	447k	}
48
49		bool Curl_timeouts_has(struct Curl_easy *data)
50	22.5M	{
51	22.5M	struct Curl_tree *node = data ? &data->state.timeouts.splaynode : NULL;
52	22.5M	return node && node->registered;
53	22.5M	}
54
55		timediff_t Curl_timeouts_offset_us(struct Curl_timeouts *timeouts,
56		const struct curltime *pts)
57	10.1M	{
58	10.1M	struct curltime time_base;
59	10.1M	time_base.tv_sec = timeouts->time_base_sec;
60	10.1M	time_base.tv_usec = 0;
61	10.1M	return curlx_ptimediff_us(pts, &time_base);
62	10.1M	}
63
64		int Curl_timeouts_next_ms(struct Curl_timeouts *timeouts,
65		const struct curltime *pnow,
66		timediff_t *pexpire_offset_us,
67		uint32_t *pmid)
68	429k	{
69	429k	if(timeouts->tree) { /* splay the lowest key to the root */
70	392k	timeouts->tree = splay(TIMEDIFF_T_MIN, timeouts->tree);
71	392k	}
72
73	429k	if(timeouts->tree) {
74	392k	timediff_t elapsed_us = Curl_timeouts_offset_us(timeouts, pnow);
75	392k	timediff_t delta_us = timeouts->tree->key - elapsed_us;
76	392k	if(pmid)
77	392k	*pmid = timeouts->tree->id;
78	392k	if(pexpire_offset_us)
79	237k	*pexpire_offset_us = timeouts->tree->key;
80	392k	if(delta_us > 0) { /* expires in the future */
81	392k	timediff_t ms = curlx_us_to_ceil_ms(delta_us);
82	392k	return (ms > INT_MAX) ? INT_MAX : (int)ms;
83	392k	}
84	40	else /* has expired */
85	40	return 0;
86	392k	}
87	37.5k	if(pmid)
88	37.5k	*pmid = UINT32_MAX;
89	37.5k	if(pexpire_offset_us)
90	15.6k	*pexpire_offset_us = 0;
91	37.5k	return -1;
92	429k	}
93
94		/*
95		* Splay using the key i (which may or may not be in the tree).
96		* This rotates the tree, so:
97		* - root->smaller has all nodes smaller than `key`
98		* - root->larger has all nodes larger than `key`
99		* - root->key may equal `key` or not
100		* <https://en.wikipedia.org/wiki/Splay_tree>
101		*/
102		struct Curl_tree *splay(timediff_t key,
103		struct Curl_tree *root)
104	3.76M	{
105	3.76M	struct Curl_tree N, l, r, *y;
106
107	3.76M	if(!root)
108	0	return NULL;
109	3.76M	N.smaller = N.larger = NULL;
110	3.76M	l = r = &N;
111
112	3.79M	for(;;) {
113	3.79M	if(key < root->key) {
114		/* key is somewhere in root->smaller branch */
115	2.62M	if(!root->smaller) /* which is empty, done */
116	2.59M	break;
117	30.7k	if(key < root->smaller->key) {
118		/* key is somewhere in root->smaller->smaller, make a "Zig step" */
119	25.6k	y = root->smaller;
120	25.6k	root->smaller = y->larger;
121	25.6k	y->larger = root;
122	25.6k	root = y;
123	25.6k	if(!root->smaller)
124	14.1k	break;
125	25.6k	}
126		/* Making root->smaller the new root, the old root is no longer
127		* referenced. Remember it in the N tree's `r`ight/larger side.
128		* Everything in old root is smaller than what the right side
129		* of N already has, so it gets added to r->smaller. */
130	16.5k	r->smaller = root;
131	16.5k	r = root;
132	16.5k	root = root->smaller;
133	16.5k	}
134	1.16M	else if(key > root->key) {
135		/* key is somewhere in root->larger branch */
136	95.9k	if(!root->larger) /* which is empty, done */
137	76.7k	break;
138	19.2k	if(key > root->larger->key) {
139		/* key is somewhere in root->larger->larger, make a "Zig step" */
140	8.23k	y = root->larger;
141	8.23k	root->larger = y->smaller;
142	8.23k	y->smaller = root;
143	8.23k	root = y;
144	8.23k	if(!root->larger)
145	3.99k	break;
146	8.23k	}
147		/* Making root->larger the new root, the old root is no longer
148		* referenced. Remember it in the N tree's `l`eft/smaller side.
149		* Everything in old root is larger than what the left side
150		* of N already has, so it gets added to l->larger. */
151	15.2k	l->larger = root;
152	15.2k	l = root;
153	15.2k	root = root->larger;
154	15.2k	}
155	1.07M	else /* exact match, root is key, done */
156	1.07M	break;
157	3.79M	}
158
159		/* Put it all together again.
160		* root->smaller has everything larger than current `l`.
161		* root->larger has everything smaller than current `r`. */
162	3.76M	l->larger = root->smaller;
163	3.76M	r->smaller = root->larger;
164	3.76M	root->smaller = N.larger;
165	3.76M	root->larger = N.smaller;
166
167	3.76M	return root;
168	3.76M	}
169
170		/* Insert key i into the tree t. Return a pointer to the resulting tree or
171		* NULL if something went wrong.
172		*
173		* @unittest 1309
174		*/
175		UNITTEST struct Curl_tree *splayinsert(timediff_t key,
176		struct Curl_tree *root,
177		struct Curl_tree *node,
178		uint32_t id);
179		UNITTEST struct Curl_tree *splayinsert(timediff_t key,
180		struct Curl_tree *root,
181		struct Curl_tree *node,
182		uint32_t id)
183	1.08M	{
184	1.08M	DEBUGASSERT(node);
185
186	1.08M	node->key = key;
187	1.08M	node->id = id;
188	1.08M	node->same = NULL;
189	1.08M	node->registered = TRUE;
190	1.08M	if(root) {
191	65.9k	root = splay(key, root);
192	65.9k	DEBUGASSERT(root);
193	65.9k	if(key == root->key) {
194		/* There already exists a node in the tree with the same key.
195		Append the new node to the `same` list. */
196	422	struct Curl_tree **panchor = &root->same;
197	425	while(*panchor)
198	3	panchor = &(*panchor)->same;
199	422	*panchor = node;
200	422	return root; /* the root node always stays the same */
201	422	}
202	65.9k	}
203
204		/* node becomes the new root. Insert old root as sub-branch. */
205	1.08M	if(!root) {
206	1.02M	node->smaller = node->larger = NULL;
207	1.02M	}
208	65.4k	else if(key < root->key) {
209	18.6k	node->smaller = root->smaller;
210	18.6k	node->larger = root;
211	18.6k	root->smaller = NULL;
212	18.6k	}
213	46.8k	else {
214	46.8k	node->larger = root->larger;
215	46.8k	node->smaller = root;
216	46.8k	root->larger = NULL;
217	46.8k	}
218
219	1.08M	return node;
220	1.08M	}
221
222		void Curl_timeouts_add(struct Curl_timeouts *timeouts,
223		struct Curl_easy *data,
224		timediff_t offset_us)
225	1.08M	{
226	1.08M	struct Curl_tree *node = &data->state.timeouts.splaynode;
227	1.08M	DEBUGASSERT(!node->registered);
228	1.08M	timeouts->tree = splayinsert(offset_us, timeouts->tree,
229	1.08M	node, data->mid);
230	1.08M	}
231
232		/* Finds and deletes the best-fit node from the tree. Return a pointer to the
233		resulting tree. best-fit means the smallest node if it is not larger than
234		the key
235
236		@unittest 1309
237		*/
238		UNITTEST struct Curl_tree *splaygetbest(timediff_t key,
239		struct Curl_tree *root,
240		struct Curl_tree **removed);
241		UNITTEST struct Curl_tree *splaygetbest(timediff_t key,
242		struct Curl_tree *root,
243		struct Curl_tree **removed)
244	2.19M	{
245	2.19M	struct Curl_tree *x;
246
247	2.19M	if(!root) {
248	0	removed = NULL; / none removed since there was no root */
249	0	return NULL;
250	0	}
251
252		/* find smallest */
253	2.19M	root = splay(TIMEDIFF_T_MIN, root);
254	2.19M	DEBUGASSERT(root);
255	2.19M	if(key < root->key) {
256		/* even the smallest is too big */
257	2.19M	*removed = NULL;
258	2.19M	return root;
259	2.19M	}
260
261		/* FIRST! Check if there is a list with identical keys */
262	859	if(root->same) {
263	0	x = root->same;
264	0	DEBUGASSERT(x->key == root->key);
265		/* 'x' becomes the new root node */
266	0	x->larger = root->larger;
267	0	x->smaller = root->smaller;
268	0	root->same = NULL;
269	0	root->registered = FALSE;
270	0	*removed = root;
271	0	return x; /* new root */
272	0	}
273
274		/* we splayed the tree to the smallest element, there is no smaller */
275	859	x = root->larger;
276	859	root->registered = FALSE;
277	859	*removed = root;
278
279	859	return x;
280	859	}
281
282		bool Curl_timeouts_remove_expired(struct Curl_timeouts *timeouts,
283		const struct curltime *ts,
284		uint32_t *pmid)
285	2.61M	{
286	2.61M	if(timeouts->tree) {
287	2.19M	struct Curl_tree *t = NULL;
288	2.19M	timediff_t elapsed_us = Curl_timeouts_offset_us(timeouts, ts);
289	2.19M	timeouts->tree = splaygetbest(elapsed_us, timeouts->tree, &t);
290	2.19M	if(t) {
291	859	*pmid = t->id;
292	859	return TRUE;
293	859	}
294	2.19M	}
295	2.61M	*pmid = UINT32_MAX;
296	2.61M	return FALSE;
297	2.61M	}
298
299		/* Deletes the node we point out from the tree if it is there. Stores a
300		* pointer to the new resulting tree in 'newroot'.
301		*
302		* Returns zero on success and non-zero on errors!
303		* When returning error, it does not touch the 'newroot' pointer.
304		*
305		* NOTE: when the last node of the tree is removed, there is no tree left so
306		* 'newroot' will be made to point to NULL.
307		*
308		* @unittest 1309
309		*/
310		UNITTEST int splayremove(struct Curl_tree *root,
311		struct Curl_tree *removenode,
312		struct Curl_tree **newroot);
313		UNITTEST int splayremove(struct Curl_tree *root,
314		struct Curl_tree *removenode,
315		struct Curl_tree **newroot)
316	1.07M	{
317	1.07M	struct Curl_tree *x;
318
319	1.07M	if(!root)
320	0	return 1;
321
322	1.07M	DEBUGASSERT(removenode);
323	1.07M	if(!removenode->registered)
324	0	return 2;
325
326	1.07M	root = splay(removenode->key, root);
327	1.07M	DEBUGASSERT(root);
328
329		/* First make sure that we got the same root key as the one we want
330		to remove, as otherwise we might be trying to remove a node that
331		is not actually in the tree. */
332	1.07M	if(root->key != removenode->key) {
333	0	DEBUGASSERT(0);
334	0	return 2;
335	0	}
336
337	1.07M	if(root != removenode) {
338		/* Should be in the root->same list then */
339	59	struct Curl_tree **panchor;
340	59	for(panchor = &root->same; panchor; panchor = &(panchor)->same) {
341	59	if(*panchor == removenode) {
342	59	*panchor = removenode->same;
343	59	removenode->same = NULL;
344	59	removenode->registered = FALSE;
345	59	*newroot = root;
346	59	return 0;
347	59	}
348	59	}
349		/* not found in same list, error */
350	0	DEBUGASSERT(0);
351	0	return 2;
352	0	}
353		/* removing the root node */
354	1.07M	if(root->same) {
355		/* 'x' is the new root node, we make it use the root node's
356		smaller/larger links */
357	363	x = root->same;
358	363	x->larger = root->larger;
359	363	x->smaller = root->smaller;
360	363	root->same = NULL;
361	363	}
362	1.07M	else {
363		/* Remove the root node */
364	1.07M	if(!root->smaller)
365	1.03M	x = root->larger;
366	33.8k	else {
367	33.8k	x = splay(removenode->key, root->smaller);
368	33.8k	DEBUGASSERT(x);
369	33.8k	x->larger = root->larger;
370	33.8k	}
371	1.07M	}
372	1.07M	removenode->registered = FALSE;
373	1.07M	newroot = x; / return new root */
374	1.07M	return 0;
375	1.07M	}
376
377		bool Curl_timeouts_remove(struct Curl_timeouts *timeouts,
378		struct Curl_easy *data)
379	1.53M	{
380	1.53M	struct Curl_tree *node = &data->state.timeouts.splaynode;
381	1.53M	if(node->registered) {
382	1.07M	int rc = splayremove(timeouts->tree, node, &timeouts->tree);
383	1.07M	#ifdef DEBUGBUILD
384	1.07M	if(rc)
385	0	curl_mfprintf(stderr, "Internal error removing splay node = %d\n", rc);
386		#else
387		(void)rc;
388		#endif
389	1.07M	return TRUE;
390	1.07M	}
391	461k	return FALSE;
392	1.53M	}