/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-09-14 07:10

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	17.2k	{
44	17.2k	struct curltime time_base = ptime_base ? *ptime_base : curlx_now();
45	17.2k	timeouts->tree = NULL;
46	17.2k	timeouts->time_base_sec = time_base.tv_sec;
47	17.2k	}
48
49		bool Curl_timeouts_has(struct Curl_easy *data)
50	195k	{
51	195k	struct Curl_tree *node = data ? &data->state.timeouts.splaynode : NULL;
52	195k	return node && node->registered;
53	195k	}
54
55		timediff_t Curl_timeouts_offset_us(struct Curl_timeouts *timeouts,
56		const struct curltime *pts)
57	477k	{
58	477k	struct curltime time_base;
59	477k	time_base.tv_sec = timeouts->time_base_sec;
60	477k	time_base.tv_usec = 0;
61	477k	return curlx_ptimediff_us(pts, &time_base);
62	477k	}
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	8.24k	{
69	8.24k	if(timeouts->tree) { /* splay the lowest key to the root */
70	8.24k	timeouts->tree = splay(TIMEDIFF_T_MIN, timeouts->tree);
71	8.24k	}
72
73	8.24k	if(timeouts->tree) {
74	8.24k	timediff_t elapsed_us = Curl_timeouts_offset_us(timeouts, pnow);
75	8.24k	timediff_t delta_us = timeouts->tree->key - elapsed_us;
76	8.24k	if(pmid)
77	8.24k	*pmid = timeouts->tree->id;
78	8.24k	if(pexpire_offset_us)
79	0	*pexpire_offset_us = timeouts->tree->key;
80	8.24k	if(delta_us > 0) { /* expires in the future */
81	8.19k	timediff_t ms = curlx_us_to_ceil_ms(delta_us);
82	8.19k	return (ms > INT_MAX) ? INT_MAX : (int)ms;
83	8.19k	}
84	45	else /* has expired */
85	45	return 0;
86	8.24k	}
87	0	if(pmid)
88	0	*pmid = UINT32_MAX;
89	0	if(pexpire_offset_us)
90	0	*pexpire_offset_us = 0;
91	0	return -1;
92	8.24k	}
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	500k	{
105	500k	struct Curl_tree N, l, r, *y;
106
107	500k	if(!root)
108	0	return NULL;
109	500k	N.smaller = N.larger = NULL;
110	500k	l = r = &N;
111
112	514k	for(;;) {
113	514k	if(key < root->key) {
114		/* key is somewhere in root->smaller branch */
115	419k	if(!root->smaller) /* which is empty, done */
116	406k	break;
117	12.9k	if(key < root->smaller->key) {
118		/* key is somewhere in root->smaller->smaller, make a "Zig step" */
119	12.3k	y = root->smaller;
120	12.3k	root->smaller = y->larger;
121	12.3k	y->larger = root;
122	12.3k	root = y;
123	12.3k	if(!root->smaller)
124	12.3k	break;
125	12.3k	}
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	620	r->smaller = root;
131	620	r = root;
132	620	root = root->smaller;
133	620	}
134	94.9k	else if(key > root->key) {
135		/* key is somewhere in root->larger branch */
136	38.2k	if(!root->larger) /* which is empty, done */
137	25.6k	break;
138	12.6k	if(key > root->larger->key) {
139		/* key is somewhere in root->larger->larger, make a "Zig step" */
140	0	y = root->larger;
141	0	root->larger = y->smaller;
142	0	y->smaller = root;
143	0	root = y;
144	0	if(!root->larger)
145	0	break;
146	0	}
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	12.6k	l->larger = root;
152	12.6k	l = root;
153	12.6k	root = root->larger;
154	12.6k	}
155	56.7k	else /* exact match, root is key, done */
156	56.7k	break;
157	514k	}
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	500k	l->larger = root->smaller;
163	500k	r->smaller = root->larger;
164	500k	root->smaller = N.larger;
165	500k	root->larger = N.smaller;
166
167	500k	return root;
168	500k	}
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	57.3k	{
184	57.3k	DEBUGASSERT(node);
185
186	57.3k	node->key = key;
187	57.3k	node->id = id;
188	57.3k	node->same = NULL;
189	57.3k	node->registered = TRUE;
190	57.3k	if(root) {
191	15.1k	root = splay(key, root);
192	15.1k	DEBUGASSERT(root);
193	15.1k	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	0	struct Curl_tree **panchor = &root->same;
197	0	while(*panchor)
198	0	panchor = &(*panchor)->same;
199	0	*panchor = node;
200	0	return root; /* the root node always stays the same */
201	0	}
202	15.1k	}
203
204		/* node becomes the new root. Insert old root as sub-branch. */
205	57.3k	if(!root) {
206	42.1k	node->smaller = node->larger = NULL;
207	42.1k	}
208	15.1k	else if(key < root->key) {
209	2.15k	node->smaller = root->smaller;
210	2.15k	node->larger = root;
211	2.15k	root->smaller = NULL;
212	2.15k	}
213	12.9k	else {
214	12.9k	node->larger = root->larger;
215	12.9k	node->smaller = root;
216	12.9k	root->larger = NULL;
217	12.9k	}
218
219	57.3k	return node;
220	57.3k	}
221
222		void Curl_timeouts_add(struct Curl_timeouts *timeouts,
223		struct Curl_easy *data,
224		timediff_t offset_us)
225	57.3k	{
226	57.3k	struct Curl_tree *node = &data->state.timeouts.splaynode;
227	57.3k	DEBUGASSERT(!node->registered);
228	57.3k	timeouts->tree = splayinsert(offset_us, timeouts->tree,
229	57.3k	node, data->mid);
230	57.3k	}
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	408k	{
245	408k	struct Curl_tree *x;
246
247	408k	if(!root) {
248	0	removed = NULL; / none removed since there was no root */
249	0	return NULL;
250	0	}
251
252		/* find smallest */
253	408k	root = splay(TIMEDIFF_T_MIN, root);
254	408k	DEBUGASSERT(root);
255	408k	if(key < root->key) {
256		/* even the smallest is too big */
257	408k	*removed = NULL;
258	408k	return root;
259	408k	}
260
261		/* FIRST! Check if there is a list with identical keys */
262	22	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	22	x = root->larger;
276	22	root->registered = FALSE;
277	22	*removed = root;
278
279	22	return x;
280	22	}
281
282		bool Curl_timeouts_remove_expired(struct Curl_timeouts *timeouts,
283		const struct curltime *ts,
284		uint32_t *pmid)
285	425k	{
286	425k	if(timeouts->tree) {
287	408k	struct Curl_tree *t = NULL;
288	408k	timediff_t elapsed_us = Curl_timeouts_offset_us(timeouts, ts);
289	408k	timeouts->tree = splaygetbest(elapsed_us, timeouts->tree, &t);
290	408k	if(t) {
291	22	*pmid = t->id;
292	22	return TRUE;
293	22	}
294	408k	}
295	425k	*pmid = UINT32_MAX;
296	425k	return FALSE;
297	425k	}
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	56.7k	{
317	56.7k	struct Curl_tree *x;
318
319	56.7k	if(!root)
320	0	return 1;
321
322	56.7k	DEBUGASSERT(removenode);
323	56.7k	if(!removenode->registered)
324	0	return 2;
325
326	56.7k	root = splay(removenode->key, root);
327	56.7k	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	56.7k	if(root->key != removenode->key) {
333	0	DEBUGASSERT(0);
334	0	return 2;
335	0	}
336
337	56.7k	if(root != removenode) {
338		/* Should be in the root->same list then */
339	0	struct Curl_tree **panchor;
340	0	for(panchor = &root->same; panchor; panchor = &(panchor)->same) {
341	0	if(*panchor == removenode) {
342	0	*panchor = removenode->same;
343	0	removenode->same = NULL;
344	0	removenode->registered = FALSE;
345	0	*newroot = root;
346	0	return 0;
347	0	}
348	0	}
349		/* not found in same list, error */
350	0	DEBUGASSERT(0);
351	0	return 2;
352	0	}
353		/* removing the root node */
354	56.7k	if(root->same) {
355		/* 'x' is the new root node, we make it use the root node's
356		smaller/larger links */
357	0	x = root->same;
358	0	x->larger = root->larger;
359	0	x->smaller = root->smaller;
360	0	root->same = NULL;
361	0	}
362	56.7k	else {
363		/* Remove the root node */
364	56.7k	if(!root->smaller)
365	44.0k	x = root->larger;
366	12.6k	else {
367	12.6k	x = splay(removenode->key, root->smaller);
368	12.6k	DEBUGASSERT(x);
369	12.6k	x->larger = root->larger;
370	12.6k	}
371	56.7k	}
372	56.7k	removenode->registered = FALSE;
373	56.7k	newroot = x; / return new root */
374	56.7k	return 0;
375	56.7k	}
376
377		bool Curl_timeouts_remove(struct Curl_timeouts *timeouts,
378		struct Curl_easy *data)
379	73.9k	{
380	73.9k	struct Curl_tree *node = &data->state.timeouts.splaynode;
381	73.9k	if(node->registered) {
382	56.7k	int rc = splayremove(timeouts->tree, node, &timeouts->tree);
383	56.7k	#ifdef DEBUGBUILD
384	56.7k	if(rc)
385	0	curl_mfprintf(stderr, "Internal error removing splay node = %d\n", rc);
386		#else
387		(void)rc;
388		#endif
389	56.7k	return TRUE;
390	56.7k	}
391	17.2k	return FALSE;
392	73.9k	}