1<!-- 2Copyright (C) Daniel Stenberg, <daniel@haxx.se>, et al. 3 4SPDX-License-Identifier: curl 5--> 6 7# `splay` 8 9 #include "splay.h" 10 11This is an internal module for splay tree management. A splay tree is a binary 12search tree with the additional property that recently accessed elements are 13quick to access again. A self-balancing tree. 14 15Nodes are added to the tree, they are accessed and removed from the tree and 16it automatically rebalances itself in each operation. 17 18## libcurl use 19 20libcurl adds fixed timeout expiry timestamps to the splay tree, and is meant 21to scale up to holding a huge amount of pending timeouts with decent 22performance. 23 24The splay tree is used to: 25 261. figure out the next timeout expiry value closest in time 272. iterate over timeouts that already have expired 28 29This splay tree rebalances itself based on the time value. 30 31Each node in the splay tree points to a `struct Curl_easy`. Each `Curl_easy` 32struct is represented only once in the tree. To still allow each easy handle 33to have a large number of timeouts per handle, each handle has a sorted linked 34list of pending timeouts. Only the handle's timeout that is closest to expire 35is the timestamp used for the splay tree node. 36 37When a specific easy handle's timeout expires, the node gets removed from the 38splay tree and from the handle's linked list of timeouts. The next timeout for 39that handle is then first in line and becomes the new timeout value as the 40node is re-added to the splay. 41 42## `Curl_splay` 43 44~~~c 45struct Curl_tree *Curl_splay(struct curltime i, struct Curl_tree *t); 46~~~ 47 48Rearranges the tree `t` after the provide time `i`. 49 50## `Curl_splayinsert` 51 52~~~c 53struct Curl_tree *Curl_splayinsert(struct curltime key, 54 struct Curl_tree *t, 55 struct Curl_tree *node); 56~~~ 57 58This function inserts a new `node` in the tree, using the given `key` 59timestamp. The `node` struct has a field called `->payload` that can be set to 60point to anything. libcurl sets this to the `struct Curl_easy` handle that is 61associated with the timeout value set in `key`. 62 63The splay insert function does not allocate any memory, it assumes the caller 64has that arranged. 65 66It returns a pointer to the new tree root. 67 68## `Curl_splaygetbest` 69 70~~~c 71struct Curl_tree *Curl_splaygetbest(struct curltime key, 72 struct Curl_tree *tree, 73 struct Curl_tree **removed); 74~~~ 75 76If there is a node in the `tree` that has a time value that is less than the 77provided `key`, this function removes that node from the tree and provides it 78in the `*removed` pointer (or NULL if there was no match). 79 80It returns a pointer to the new tree root. 81 82## `Curl_splayremove` 83 84~~~c 85int Curl_splayremove(struct Curl_tree *tree, 86 struct Curl_tree *node, 87 struct Curl_tree **newroot); 88~~~ 89 90Removes a given `node` from a splay `tree`, and returns the `newroot` 91identifying the new tree root. 92 93Note that a clean tree without any nodes present implies a NULL pointer. 94 95## `Curl_splayset` 96 97~~~c 98void Curl_splayset(struct Curl_tree *node, void *payload); 99~~~ 100 101Set a custom pointer to be stored in the splay node. This pointer is not used 102by the splay code itself and can be retrieved again with `Curl_splayget`. 103 104## `Curl_splayget` 105 106~~~c 107void *Curl_splayget(struct Curl_tree *node); 108~~~ 109 110Get the custom pointer from the splay node that was previously set with 111`Curl_splayset`. If no pointer was set before, it returns NULL. 112
