docs/api-2.1/avl_8h.html@13b40a598d16 (annotated)
docs/api-2.1/avl_8h.html
Fri, 16 Feb 2024 20:23:48 +0100
- author
- Mike Becker <universe@uap-core.de>
- date
- Fri, 16 Feb 2024 20:23:48 +0100
- changeset 827
- 13b40a598d16
- parent 390
- d345541018fa
- permissions
- -rw-r--r--
first draft of a tree iterator
see issue #371
| 390 | 1 | <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> |
| 2 | <html xmlns="http://www.w3.org/1999/xhtml"> | |
| 3 | <head> | |
| 4 | <meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/> | |
| 5 | <meta http-equiv="X-UA-Compatible" content="IE=9"/> | |
| 6 | <meta name="generator" content="Doxygen 1.8.13"/> | |
| 7 | <meta name="viewport" content="width=device-width, initial-scale=1"/> | |
| 8 | <title>ucx: /home/mike/workspace/c/ucx/src/ucx/avl.h File Reference</title> | |
| 9 | <link href="tabs.css" rel="stylesheet" type="text/css"/> | |
| 10 | <script type="text/javascript" src="jquery.js"></script> | |
| 11 | <script type="text/javascript" src="dynsections.js"></script> | |
| 12 | <link href="search/search.css" rel="stylesheet" type="text/css"/> | |
| 13 | <script type="text/javascript" src="search/searchdata.js"></script> | |
| 14 | <script type="text/javascript" src="search/search.js"></script> | |
| 15 | <link href="doxygen.css" rel="stylesheet" type="text/css" /> | |
| 16 | </head> | |
| 17 | <body> | |
| 18 | <div id="top"><!-- do not remove this div, it is closed by doxygen! --> | |
| 19 | <div id="titlearea"> | |
| 20 | <table cellspacing="0" cellpadding="0"> | |
| 21 | <tbody> | |
| 22 | <tr style="height: 56px;"> | |
| 23 | <td id="projectlogo"><img alt="Logo" src="uaplogo.png"/></td> | |
| 24 | <td id="projectalign" style="padding-left: 0.5em;"> | |
| 25 | <div id="projectname">ucx | |
| 26 | </div> | |
| 27 | <div id="projectbrief">UAP Common Extensions</div> | |
| 28 | </td> | |
| 29 | </tr> | |
| 30 | </tbody> | |
| 31 | </table> | |
| 32 | </div> | |
| 33 | <!-- end header part --> | |
| 34 | <!-- Generated by Doxygen 1.8.13 --> | |
| 35 | <script type="text/javascript"> | |
| 36 | var searchBox = new SearchBox("searchBox", "search",false,'Search'); | |
| 37 | </script> | |
| 38 | <script type="text/javascript" src="menudata.js"></script> | |
| 39 | <script type="text/javascript" src="menu.js"></script> | |
| 40 | <script type="text/javascript"> | |
| 41 | $(function() { | |
| 42 | initMenu('',true,false,'search.php','Search'); | |
| 43 | $(document).ready(function() { init_search(); }); | |
| 44 | }); | |
| 45 | </script> | |
| 46 | <div id="main-nav"></div> | |
| 47 | <!-- window showing the filter options --> | |
| 48 | <div id="MSearchSelectWindow" | |
| 49 | onmouseover="return searchBox.OnSearchSelectShow()" | |
| 50 | onmouseout="return searchBox.OnSearchSelectHide()" | |
| 51 | onkeydown="return searchBox.OnSearchSelectKey(event)"> | |
| 52 | </div> | |
| 53 | ||
| 54 | <!-- iframe showing the search results (closed by default) --> | |
| 55 | <div id="MSearchResultsWindow"> | |
| 56 | <iframe src="javascript:void(0)" frameborder="0" | |
| 57 | name="MSearchResults" id="MSearchResults"> | |
| 58 | </iframe> | |
| 59 | </div> | |
| 60 | ||
| 61 | <div id="nav-path" class="navpath"> | |
| 62 | <ul> | |
| 63 | <li class="navelem"><a class="el" href="dir_68267d1309a1af8e8297ef4c3efbcdba.html">src</a></li><li class="navelem"><a class="el" href="dir_69f4ea29401808fe6229564976cde3ce.html">ucx</a></li> </ul> | |
| 64 | </div> | |
| 65 | </div><!-- top --> | |
| 66 | <div class="header"> | |
| 67 | <div class="summary"> | |
| 68 | <a href="#nested-classes">Data Structures</a> | | |
| 69 | <a href="#define-members">Macros</a> | | |
| 70 | <a href="#typedef-members">Typedefs</a> | | |
| 71 | <a href="#func-members">Functions</a> </div> | |
| 72 | <div class="headertitle"> | |
| 73 | <div class="title">avl.h File Reference</div> </div> | |
| 74 | </div><!--header--> | |
| 75 | <div class="contents"> | |
| 76 | ||
| 77 | <p>AVL tree implementation. | |
| 78 | <a href="#details">More...</a></p> | |
| 79 | <div class="textblock"><code>#include "<a class="el" href="ucx_8h_source.html">ucx.h</a>"</code><br /> | |
| 80 | <code>#include "<a class="el" href="allocator_8h_source.html">allocator.h</a>"</code><br /> | |
| 81 | <code>#include <inttypes.h></code><br /> | |
| 82 | </div> | |
| 83 | <p><a href="avl_8h_source.html">Go to the source code of this file.</a></p> | |
| 84 | <table class="memberdecls"> | |
| 85 | <tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="nested-classes"></a> | |
| 86 | Data Structures</h2></td></tr> | |
| 87 | <tr class="memitem:"><td class="memItemLeft" align="right" valign="top">struct  </td><td class="memItemRight" valign="bottom"><a class="el" href="structUcxAVLNode.html">UcxAVLNode</a></td></tr> | |
| 88 | <tr class="memdesc:"><td class="mdescLeft"> </td><td class="mdescRight">UCX AVL Node. <a href="structUcxAVLNode.html#details">More...</a><br /></td></tr> | |
| 89 | <tr class="separator:"><td class="memSeparator" colspan="2"> </td></tr> | |
| 90 | <tr class="memitem:"><td class="memItemLeft" align="right" valign="top">struct  </td><td class="memItemRight" valign="bottom"><a class="el" href="structUcxAVLTree.html">UcxAVLTree</a></td></tr> | |
| 91 | <tr class="memdesc:"><td class="mdescLeft"> </td><td class="mdescRight">UCX AVL Tree. <a href="structUcxAVLTree.html#details">More...</a><br /></td></tr> | |
| 92 | <tr class="separator:"><td class="memSeparator" colspan="2"> </td></tr> | |
| 93 | </table><table class="memberdecls"> | |
| 94 | <tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="define-members"></a> | |
| 95 | Macros</h2></td></tr> | |
| 96 | <tr class="memitem:ac2886d4b79b48c9fabf6408873f84cd2"><td class="memItemLeft" align="right" valign="top">#define </td><td class="memItemRight" valign="bottom"><a class="el" href="avl_8h.html#ac2886d4b79b48c9fabf6408873f84cd2">ucx_avl_default_new</a>()   <a class="el" href="avl_8h.html#af0f868d67e9dc08b4867c02a06c23ee2">ucx_avl_new_a</a>(<a class="el" href="utils_8h.html#aa174d539de3ea59be4f9640f17ce53d8">ucx_cmp_ptr</a>, <a class="el" href="allocator_8h.html#a98d2f1b341118b7a0e341fda5d8b2ebf">ucx_default_allocator</a>())</td></tr> | |
| 97 | <tr class="memdesc:ac2886d4b79b48c9fabf6408873f84cd2"><td class="mdescLeft"> </td><td class="mdescRight">Macro for initializing a new <a class="el" href="structUcxAVLTree.html" title="UCX AVL Tree. ">UcxAVLTree</a> with the default allocator and a <a class="el" href="utils_8h.html#aa174d539de3ea59be4f9640f17ce53d8" title="Compares two pointers. ">ucx_cmp_ptr()</a> compare function. <a href="#ac2886d4b79b48c9fabf6408873f84cd2">More...</a><br /></td></tr> | |
| 98 | <tr class="separator:ac2886d4b79b48c9fabf6408873f84cd2"><td class="memSeparator" colspan="2"> </td></tr> | |
| 99 | <tr class="memitem:aaaf4a6f6f661cda7791db239212285d9"><td class="memItemLeft" align="right" valign="top"><a id="aaaf4a6f6f661cda7791db239212285d9"></a> | |
| 100 | #define </td><td class="memItemRight" valign="bottom"><a class="el" href="avl_8h.html#aaaf4a6f6f661cda7791db239212285d9">UCX_AVL_FIND_EXACT</a>   0</td></tr> | |
| 101 | <tr class="memdesc:aaaf4a6f6f661cda7791db239212285d9"><td class="mdescLeft"> </td><td class="mdescRight">A mode for <a class="el" href="avl_8h.html#a664986f64d6865605199fbff06e19cd5" title="Finds a node within the tree. ">ucx_avl_find_node()</a> with the same behavior as <a class="el" href="avl_8h.html#acf42da9a4168e47dc10b4ba0d27ceb4e" title="Gets the node from the tree, that is associated with the specified key. ">ucx_avl_get_node()</a>. <br /></td></tr> | |
| 102 | <tr class="separator:aaaf4a6f6f661cda7791db239212285d9"><td class="memSeparator" colspan="2"> </td></tr> | |
| 103 | <tr class="memitem:abd2446d544d5412b6997ee8a17bd368c"><td class="memItemLeft" align="right" valign="top"><a id="abd2446d544d5412b6997ee8a17bd368c"></a> | |
| 104 | #define </td><td class="memItemRight" valign="bottom"><a class="el" href="avl_8h.html#abd2446d544d5412b6997ee8a17bd368c">UCX_AVL_FIND_LOWER_BOUNDED</a>   1</td></tr> | |
| 105 | <tr class="memdesc:abd2446d544d5412b6997ee8a17bd368c"><td class="mdescLeft"> </td><td class="mdescRight">A mode for <a class="el" href="avl_8h.html#a664986f64d6865605199fbff06e19cd5" title="Finds a node within the tree. ">ucx_avl_find_node()</a> finding the node whose key is at least as large as the specified key. <br /></td></tr> | |
| 106 | <tr class="separator:abd2446d544d5412b6997ee8a17bd368c"><td class="memSeparator" colspan="2"> </td></tr> | |
| 107 | <tr class="memitem:ac74ee7649c1e206b08b31f37dd68ca5e"><td class="memItemLeft" align="right" valign="top"><a id="ac74ee7649c1e206b08b31f37dd68ca5e"></a> | |
| 108 | #define </td><td class="memItemRight" valign="bottom"><a class="el" href="avl_8h.html#ac74ee7649c1e206b08b31f37dd68ca5e">UCX_AVL_FIND_UPPER_BOUNDED</a>   2</td></tr> | |
| 109 | <tr class="memdesc:ac74ee7649c1e206b08b31f37dd68ca5e"><td class="mdescLeft"> </td><td class="mdescRight">A mode for <a class="el" href="avl_8h.html#a664986f64d6865605199fbff06e19cd5" title="Finds a node within the tree. ">ucx_avl_find_node()</a> finding the node whose key is at most as large as the specified key. <br /></td></tr> | |
| 110 | <tr class="separator:ac74ee7649c1e206b08b31f37dd68ca5e"><td class="memSeparator" colspan="2"> </td></tr> | |
| 111 | <tr class="memitem:af16f24d74fd6af0154de041566c6603b"><td class="memItemLeft" align="right" valign="top">#define </td><td class="memItemRight" valign="bottom"><a class="el" href="avl_8h.html#af16f24d74fd6af0154de041566c6603b">UCX_AVL_FIND_CLOSEST</a>   3</td></tr> | |
| 112 | <tr class="memdesc:af16f24d74fd6af0154de041566c6603b"><td class="mdescLeft"> </td><td class="mdescRight">A mode for <a class="el" href="avl_8h.html#a664986f64d6865605199fbff06e19cd5" title="Finds a node within the tree. ">ucx_avl_find_node()</a> finding the node with a key that is as close to the specified key as possible. <a href="#af16f24d74fd6af0154de041566c6603b">More...</a><br /></td></tr> | |
| 113 | <tr class="separator:af16f24d74fd6af0154de041566c6603b"><td class="memSeparator" colspan="2"> </td></tr> | |
| 114 | </table><table class="memberdecls"> | |
| 115 | <tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="typedef-members"></a> | |
| 116 | Typedefs</h2></td></tr> | |
| 117 | <tr class="memitem:a08ba2496c2316df58548c3cc29712add"><td class="memItemLeft" align="right" valign="top">typedef struct <a class="el" href="structUcxAVLNode.html">UcxAVLNode</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="avl_8h.html#a08ba2496c2316df58548c3cc29712add">UcxAVLNode</a></td></tr> | |
| 118 | <tr class="memdesc:a08ba2496c2316df58548c3cc29712add"><td class="mdescLeft"> </td><td class="mdescRight">UCX AVL Node type. <a href="#a08ba2496c2316df58548c3cc29712add">More...</a><br /></td></tr> | |
| 119 | <tr class="separator:a08ba2496c2316df58548c3cc29712add"><td class="memSeparator" colspan="2"> </td></tr> | |
| 120 | </table><table class="memberdecls"> | |
| 121 | <tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="func-members"></a> | |
| 122 | Functions</h2></td></tr> | |
| 123 | <tr class="memitem:a11b043d65a11b7092d5d98b298e5ede3"><td class="memItemLeft" align="right" valign="top"><a class="el" href="structUcxAVLTree.html">UcxAVLTree</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="avl_8h.html#a11b043d65a11b7092d5d98b298e5ede3">ucx_avl_new</a> (<a class="el" href="ucx_8h.html#afe5e2d5dbf34778e0e97852051570791">cmp_func</a> cmpfunc)</td></tr> | |
| 124 | <tr class="memdesc:a11b043d65a11b7092d5d98b298e5ede3"><td class="mdescLeft"> </td><td class="mdescRight">Initializes a new <a class="el" href="structUcxAVLTree.html" title="UCX AVL Tree. ">UcxAVLTree</a> with a default allocator. <a href="#a11b043d65a11b7092d5d98b298e5ede3">More...</a><br /></td></tr> | |
| 125 | <tr class="separator:a11b043d65a11b7092d5d98b298e5ede3"><td class="memSeparator" colspan="2"> </td></tr> | |
| 126 | <tr class="memitem:af0f868d67e9dc08b4867c02a06c23ee2"><td class="memItemLeft" align="right" valign="top"><a class="el" href="structUcxAVLTree.html">UcxAVLTree</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="avl_8h.html#af0f868d67e9dc08b4867c02a06c23ee2">ucx_avl_new_a</a> (<a class="el" href="ucx_8h.html#afe5e2d5dbf34778e0e97852051570791">cmp_func</a> cmpfunc, <a class="el" href="structUcxAllocator.html">UcxAllocator</a> *allocator)</td></tr> | |
| 127 | <tr class="memdesc:af0f868d67e9dc08b4867c02a06c23ee2"><td class="mdescLeft"> </td><td class="mdescRight">Initializes a new <a class="el" href="structUcxAVLTree.html" title="UCX AVL Tree. ">UcxAVLTree</a> with the specified allocator. <a href="#af0f868d67e9dc08b4867c02a06c23ee2">More...</a><br /></td></tr> | |
| 128 | <tr class="separator:af0f868d67e9dc08b4867c02a06c23ee2"><td class="memSeparator" colspan="2"> </td></tr> | |
| 129 | <tr class="memitem:a2f92db538f25fce908d2cb3e5590944c"><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="avl_8h.html#a2f92db538f25fce908d2cb3e5590944c">ucx_avl_free</a> (<a class="el" href="structUcxAVLTree.html">UcxAVLTree</a> *tree)</td></tr> | |
| 130 | <tr class="memdesc:a2f92db538f25fce908d2cb3e5590944c"><td class="mdescLeft"> </td><td class="mdescRight">Destroys a <a class="el" href="structUcxAVLTree.html" title="UCX AVL Tree. ">UcxAVLTree</a>. <a href="#a2f92db538f25fce908d2cb3e5590944c">More...</a><br /></td></tr> | |
| 131 | <tr class="separator:a2f92db538f25fce908d2cb3e5590944c"><td class="memSeparator" colspan="2"> </td></tr> | |
| 132 | <tr class="memitem:a31ad7fb196ca211f1fc39f4e15f72279"><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="avl_8h.html#a31ad7fb196ca211f1fc39f4e15f72279">ucx_avl_free_content</a> (<a class="el" href="structUcxAVLTree.html">UcxAVLTree</a> *tree, <a class="el" href="ucx_8h.html#ad2b370c2809914c8b7fedab163c266b3">ucx_destructor</a> destr)</td></tr> | |
| 133 | <tr class="memdesc:a31ad7fb196ca211f1fc39f4e15f72279"><td class="mdescLeft"> </td><td class="mdescRight">Frees the contents of a <a class="el" href="structUcxAVLTree.html" title="UCX AVL Tree. ">UcxAVLTree</a>. <a href="#a31ad7fb196ca211f1fc39f4e15f72279">More...</a><br /></td></tr> | |
| 134 | <tr class="separator:a31ad7fb196ca211f1fc39f4e15f72279"><td class="memSeparator" colspan="2"> </td></tr> | |
| 135 | <tr class="memitem:acf42da9a4168e47dc10b4ba0d27ceb4e"><td class="memItemLeft" align="right" valign="top"><a class="el" href="structUcxAVLNode.html">UcxAVLNode</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="avl_8h.html#acf42da9a4168e47dc10b4ba0d27ceb4e">ucx_avl_get_node</a> (<a class="el" href="structUcxAVLTree.html">UcxAVLTree</a> *tree, intptr_t key)</td></tr> | |
| 136 | <tr class="memdesc:acf42da9a4168e47dc10b4ba0d27ceb4e"><td class="mdescLeft"> </td><td class="mdescRight">Gets the node from the tree, that is associated with the specified key. <a href="#acf42da9a4168e47dc10b4ba0d27ceb4e">More...</a><br /></td></tr> | |
| 137 | <tr class="separator:acf42da9a4168e47dc10b4ba0d27ceb4e"><td class="memSeparator" colspan="2"> </td></tr> | |
| 138 | <tr class="memitem:adbcf7ceb3f014a30c7214f7304519efe"><td class="memItemLeft" align="right" valign="top">void * </td><td class="memItemRight" valign="bottom"><a class="el" href="avl_8h.html#adbcf7ceb3f014a30c7214f7304519efe">ucx_avl_get</a> (<a class="el" href="structUcxAVLTree.html">UcxAVLTree</a> *tree, intptr_t key)</td></tr> | |
| 139 | <tr class="memdesc:adbcf7ceb3f014a30c7214f7304519efe"><td class="mdescLeft"> </td><td class="mdescRight">Gets the value from the tree, that is associated with the specified key. <a href="#adbcf7ceb3f014a30c7214f7304519efe">More...</a><br /></td></tr> | |
| 140 | <tr class="separator:adbcf7ceb3f014a30c7214f7304519efe"><td class="memSeparator" colspan="2"> </td></tr> | |
| 141 | <tr class="memitem:a664986f64d6865605199fbff06e19cd5"><td class="memItemLeft" align="right" valign="top"><a class="el" href="structUcxAVLNode.html">UcxAVLNode</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="avl_8h.html#a664986f64d6865605199fbff06e19cd5">ucx_avl_find_node</a> (<a class="el" href="structUcxAVLTree.html">UcxAVLTree</a> *tree, intptr_t key, <a class="el" href="ucx_8h.html#a0bc5bf89e556c1d45d10863d52728ac9">distance_func</a> dfnc, int mode)</td></tr> | |
| 142 | <tr class="memdesc:a664986f64d6865605199fbff06e19cd5"><td class="mdescLeft"> </td><td class="mdescRight">Finds a node within the tree. <a href="#a664986f64d6865605199fbff06e19cd5">More...</a><br /></td></tr> | |
| 143 | <tr class="separator:a664986f64d6865605199fbff06e19cd5"><td class="memSeparator" colspan="2"> </td></tr> | |
| 144 | <tr class="memitem:a51770e1614b28d7d22dea096c3704f83"><td class="memItemLeft" align="right" valign="top">void * </td><td class="memItemRight" valign="bottom"><a class="el" href="avl_8h.html#a51770e1614b28d7d22dea096c3704f83">ucx_avl_find</a> (<a class="el" href="structUcxAVLTree.html">UcxAVLTree</a> *tree, intptr_t key, <a class="el" href="ucx_8h.html#a0bc5bf89e556c1d45d10863d52728ac9">distance_func</a> dfnc, int mode)</td></tr> | |
| 145 | <tr class="memdesc:a51770e1614b28d7d22dea096c3704f83"><td class="mdescLeft"> </td><td class="mdescRight">Finds a value within the tree. <a href="#a51770e1614b28d7d22dea096c3704f83">More...</a><br /></td></tr> | |
| 146 | <tr class="separator:a51770e1614b28d7d22dea096c3704f83"><td class="memSeparator" colspan="2"> </td></tr> | |
| 147 | <tr class="memitem:aec401fab4a24a7edffa734f9baf88577"><td class="memItemLeft" align="right" valign="top">int </td><td class="memItemRight" valign="bottom"><a class="el" href="avl_8h.html#aec401fab4a24a7edffa734f9baf88577">ucx_avl_put</a> (<a class="el" href="structUcxAVLTree.html">UcxAVLTree</a> *tree, intptr_t key, void *value)</td></tr> | |
| 148 | <tr class="memdesc:aec401fab4a24a7edffa734f9baf88577"><td class="mdescLeft"> </td><td class="mdescRight">Puts a key/value pair into the tree. <a href="#aec401fab4a24a7edffa734f9baf88577">More...</a><br /></td></tr> | |
| 149 | <tr class="separator:aec401fab4a24a7edffa734f9baf88577"><td class="memSeparator" colspan="2"> </td></tr> | |
| 150 | <tr class="memitem:a32cf8955cc0226a82bacfc7b76d6474c"><td class="memItemLeft" align="right" valign="top">int </td><td class="memItemRight" valign="bottom"><a class="el" href="avl_8h.html#a32cf8955cc0226a82bacfc7b76d6474c">ucx_avl_put_s</a> (<a class="el" href="structUcxAVLTree.html">UcxAVLTree</a> *tree, intptr_t key, void *value, void **oldvalue)</td></tr> | |
| 151 | <tr class="memdesc:a32cf8955cc0226a82bacfc7b76d6474c"><td class="mdescLeft"> </td><td class="mdescRight">Puts a key/value pair into the tree. <a href="#a32cf8955cc0226a82bacfc7b76d6474c">More...</a><br /></td></tr> | |
| 152 | <tr class="separator:a32cf8955cc0226a82bacfc7b76d6474c"><td class="memSeparator" colspan="2"> </td></tr> | |
| 153 | <tr class="memitem:a9a792b7d9e58073deef74a341f8bc720"><td class="memItemLeft" align="right" valign="top">int </td><td class="memItemRight" valign="bottom"><a class="el" href="avl_8h.html#a9a792b7d9e58073deef74a341f8bc720">ucx_avl_remove_node</a> (<a class="el" href="structUcxAVLTree.html">UcxAVLTree</a> *tree, <a class="el" href="structUcxAVLNode.html">UcxAVLNode</a> *node)</td></tr> | |
| 154 | <tr class="memdesc:a9a792b7d9e58073deef74a341f8bc720"><td class="mdescLeft"> </td><td class="mdescRight">Removes a node from the AVL tree. <a href="#a9a792b7d9e58073deef74a341f8bc720">More...</a><br /></td></tr> | |
| 155 | <tr class="separator:a9a792b7d9e58073deef74a341f8bc720"><td class="memSeparator" colspan="2"> </td></tr> | |
| 156 | <tr class="memitem:a1d821119c805d7fbb7e424bc3effeba9"><td class="memItemLeft" align="right" valign="top">int </td><td class="memItemRight" valign="bottom"><a class="el" href="avl_8h.html#a1d821119c805d7fbb7e424bc3effeba9">ucx_avl_remove</a> (<a class="el" href="structUcxAVLTree.html">UcxAVLTree</a> *tree, intptr_t key)</td></tr> | |
| 157 | <tr class="memdesc:a1d821119c805d7fbb7e424bc3effeba9"><td class="mdescLeft"> </td><td class="mdescRight">Removes an element from the AVL tree. <a href="#a1d821119c805d7fbb7e424bc3effeba9">More...</a><br /></td></tr> | |
| 158 | <tr class="separator:a1d821119c805d7fbb7e424bc3effeba9"><td class="memSeparator" colspan="2"> </td></tr> | |
| 159 | <tr class="memitem:a01aeeecd6415f0cc2b623486eb28f254"><td class="memItemLeft" align="right" valign="top">int </td><td class="memItemRight" valign="bottom"><a class="el" href="avl_8h.html#a01aeeecd6415f0cc2b623486eb28f254">ucx_avl_remove_s</a> (<a class="el" href="structUcxAVLTree.html">UcxAVLTree</a> *tree, intptr_t key, intptr_t *oldkey, void **oldvalue)</td></tr> | |
| 160 | <tr class="memdesc:a01aeeecd6415f0cc2b623486eb28f254"><td class="mdescLeft"> </td><td class="mdescRight">Removes an element from the AVL tree. <a href="#a01aeeecd6415f0cc2b623486eb28f254">More...</a><br /></td></tr> | |
| 161 | <tr class="separator:a01aeeecd6415f0cc2b623486eb28f254"><td class="memSeparator" colspan="2"> </td></tr> | |
| 162 | <tr class="memitem:a92c1d41c2b22fe4a029a486ab2153e35"><td class="memItemLeft" align="right" valign="top">size_t </td><td class="memItemRight" valign="bottom"><a class="el" href="avl_8h.html#a92c1d41c2b22fe4a029a486ab2153e35">ucx_avl_count</a> (<a class="el" href="structUcxAVLTree.html">UcxAVLTree</a> *tree)</td></tr> | |
| 163 | <tr class="memdesc:a92c1d41c2b22fe4a029a486ab2153e35"><td class="mdescLeft"> </td><td class="mdescRight">Counts the nodes in the specified <a class="el" href="structUcxAVLTree.html" title="UCX AVL Tree. ">UcxAVLTree</a>. <a href="#a92c1d41c2b22fe4a029a486ab2153e35">More...</a><br /></td></tr> | |
| 164 | <tr class="separator:a92c1d41c2b22fe4a029a486ab2153e35"><td class="memSeparator" colspan="2"> </td></tr> | |
| 165 | <tr class="memitem:a0e739aeb66dda6a6a3f6eb51b50cf346"><td class="memItemLeft" align="right" valign="top"><a class="el" href="structUcxAVLNode.html">UcxAVLNode</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="avl_8h.html#a0e739aeb66dda6a6a3f6eb51b50cf346">ucx_avl_pred</a> (<a class="el" href="structUcxAVLNode.html">UcxAVLNode</a> *node)</td></tr> | |
| 166 | <tr class="memdesc:a0e739aeb66dda6a6a3f6eb51b50cf346"><td class="mdescLeft"> </td><td class="mdescRight">Finds the in-order predecessor of the given node. <a href="#a0e739aeb66dda6a6a3f6eb51b50cf346">More...</a><br /></td></tr> | |
| 167 | <tr class="separator:a0e739aeb66dda6a6a3f6eb51b50cf346"><td class="memSeparator" colspan="2"> </td></tr> | |
| 168 | <tr class="memitem:aab1ad9b027ff5e50671aa0ee84e2d541"><td class="memItemLeft" align="right" valign="top"><a class="el" href="structUcxAVLNode.html">UcxAVLNode</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="avl_8h.html#aab1ad9b027ff5e50671aa0ee84e2d541">ucx_avl_succ</a> (<a class="el" href="structUcxAVLNode.html">UcxAVLNode</a> *node)</td></tr> | |
| 169 | <tr class="memdesc:aab1ad9b027ff5e50671aa0ee84e2d541"><td class="mdescLeft"> </td><td class="mdescRight">Finds the in-order successor of the given node. <a href="#aab1ad9b027ff5e50671aa0ee84e2d541">More...</a><br /></td></tr> | |
| 170 | <tr class="separator:aab1ad9b027ff5e50671aa0ee84e2d541"><td class="memSeparator" colspan="2"> </td></tr> | |
| 171 | </table> | |
| 172 | <a name="details" id="details"></a><h2 class="groupheader">Detailed Description</h2> | |
| 173 | <div class="textblock"><p>AVL tree implementation. </p> | |
| 174 | <p>This binary search tree implementation allows average O(1) insertion and removal of elements (excluding binary search time).</p> | |
| 175 | <dl class="section author"><dt>Author</dt><dd>Mike Becker </dd> | |
| 176 | <dd> | |
| 177 | Olaf Wintermann </dd></dl> | |
| 178 | </div><h2 class="groupheader">Macro Definition Documentation</h2> | |
| 179 | <a id="ac2886d4b79b48c9fabf6408873f84cd2"></a> | |
| 180 | <h2 class="memtitle"><span class="permalink"><a href="#ac2886d4b79b48c9fabf6408873f84cd2">◆ </a></span>ucx_avl_default_new</h2> | |
| 181 | ||
| 182 | <div class="memitem"> | |
| 183 | <div class="memproto"> | |
| 184 | <table class="memname"> | |
| 185 | <tr> | |
| 186 | <td class="memname">#define ucx_avl_default_new</td> | |
| 187 | <td>(</td> | |
| 188 | <td class="paramname"></td><td>)</td> | |
| 189 | <td>   <a class="el" href="avl_8h.html#af0f868d67e9dc08b4867c02a06c23ee2">ucx_avl_new_a</a>(<a class="el" href="utils_8h.html#aa174d539de3ea59be4f9640f17ce53d8">ucx_cmp_ptr</a>, <a class="el" href="allocator_8h.html#a98d2f1b341118b7a0e341fda5d8b2ebf">ucx_default_allocator</a>())</td> | |
| 190 | </tr> | |
| 191 | </table> | |
| 192 | </div><div class="memdoc"> | |
| 193 | ||
| 194 | <p>Macro for initializing a new <a class="el" href="structUcxAVLTree.html" title="UCX AVL Tree. ">UcxAVLTree</a> with the default allocator and a <a class="el" href="utils_8h.html#aa174d539de3ea59be4f9640f17ce53d8" title="Compares two pointers. ">ucx_cmp_ptr()</a> compare function. </p> | |
| 195 | <dl class="section return"><dt>Returns</dt><dd>a new default <a class="el" href="structUcxAVLTree.html" title="UCX AVL Tree. ">UcxAVLTree</a> object </dd></dl> | |
| 196 | ||
| 197 | </div> | |
| 198 | </div> | |
| 199 | <a id="af16f24d74fd6af0154de041566c6603b"></a> | |
| 200 | <h2 class="memtitle"><span class="permalink"><a href="#af16f24d74fd6af0154de041566c6603b">◆ </a></span>UCX_AVL_FIND_CLOSEST</h2> | |
| 201 | ||
| 202 | <div class="memitem"> | |
| 203 | <div class="memproto"> | |
| 204 | <table class="memname"> | |
| 205 | <tr> | |
| 206 | <td class="memname">#define UCX_AVL_FIND_CLOSEST   3</td> | |
| 207 | </tr> | |
| 208 | </table> | |
| 209 | </div><div class="memdoc"> | |
| 210 | ||
| 211 | <p>A mode for <a class="el" href="avl_8h.html#a664986f64d6865605199fbff06e19cd5" title="Finds a node within the tree. ">ucx_avl_find_node()</a> finding the node with a key that is as close to the specified key as possible. </p> | |
| 212 | <p>If the key is present, the behavior is like <a class="el" href="avl_8h.html#acf42da9a4168e47dc10b4ba0d27ceb4e" title="Gets the node from the tree, that is associated with the specified key. ">ucx_avl_get_node()</a>. This mode only returns <code>NULL</code> on empty trees. </p> | |
| 213 | ||
| 214 | </div> | |
| 215 | </div> | |
| 216 | <h2 class="groupheader">Typedef Documentation</h2> | |
| 217 | <a id="a08ba2496c2316df58548c3cc29712add"></a> | |
| 218 | <h2 class="memtitle"><span class="permalink"><a href="#a08ba2496c2316df58548c3cc29712add">◆ </a></span>UcxAVLNode</h2> | |
| 219 | ||
| 220 | <div class="memitem"> | |
| 221 | <div class="memproto"> | |
| 222 | <table class="memname"> | |
| 223 | <tr> | |
| 224 | <td class="memname">typedef struct <a class="el" href="structUcxAVLNode.html">UcxAVLNode</a> <a class="el" href="structUcxAVLNode.html">UcxAVLNode</a></td> | |
| 225 | </tr> | |
| 226 | </table> | |
| 227 | </div><div class="memdoc"> | |
| 228 | ||
| 229 | <p>UCX AVL Node type. </p> | |
| 230 | <dl class="section see"><dt>See also</dt><dd><a class="el" href="structUcxAVLNode.html" title="UCX AVL Node. ">UcxAVLNode</a> </dd></dl> | |
| 231 | ||
| 232 | </div> | |
| 233 | </div> | |
| 234 | <h2 class="groupheader">Function Documentation</h2> | |
| 235 | <a id="a92c1d41c2b22fe4a029a486ab2153e35"></a> | |
| 236 | <h2 class="memtitle"><span class="permalink"><a href="#a92c1d41c2b22fe4a029a486ab2153e35">◆ </a></span>ucx_avl_count()</h2> | |
| 237 | ||
| 238 | <div class="memitem"> | |
| 239 | <div class="memproto"> | |
| 240 | <table class="memname"> | |
| 241 | <tr> | |
| 242 | <td class="memname">size_t ucx_avl_count </td> | |
| 243 | <td>(</td> | |
| 244 | <td class="paramtype"><a class="el" href="structUcxAVLTree.html">UcxAVLTree</a> * </td> | |
| 245 | <td class="paramname"><em>tree</em></td><td>)</td> | |
| 246 | <td></td> | |
| 247 | </tr> | |
| 248 | </table> | |
| 249 | </div><div class="memdoc"> | |
| 250 | ||
| 251 | <p>Counts the nodes in the specified <a class="el" href="structUcxAVLTree.html" title="UCX AVL Tree. ">UcxAVLTree</a>. </p> | |
| 252 | <dl class="params"><dt>Parameters</dt><dd> | |
| 253 | <table class="params"> | |
| 254 | <tr><td class="paramname">tree</td><td>the AVL tree </td></tr> | |
| 255 | </table> | |
| 256 | </dd> | |
| 257 | </dl> | |
| 258 | <dl class="section return"><dt>Returns</dt><dd>the node count </dd></dl> | |
| 259 | ||
| 260 | </div> | |
| 261 | </div> | |
| 262 | <a id="a51770e1614b28d7d22dea096c3704f83"></a> | |
| 263 | <h2 class="memtitle"><span class="permalink"><a href="#a51770e1614b28d7d22dea096c3704f83">◆ </a></span>ucx_avl_find()</h2> | |
| 264 | ||
| 265 | <div class="memitem"> | |
| 266 | <div class="memproto"> | |
| 267 | <table class="memname"> | |
| 268 | <tr> | |
| 269 | <td class="memname">void* ucx_avl_find </td> | |
| 270 | <td>(</td> | |
| 271 | <td class="paramtype"><a class="el" href="structUcxAVLTree.html">UcxAVLTree</a> * </td> | |
| 272 | <td class="paramname"><em>tree</em>, </td> | |
| 273 | </tr> | |
| 274 | <tr> | |
| 275 | <td class="paramkey"></td> | |
| 276 | <td></td> | |
| 277 | <td class="paramtype">intptr_t </td> | |
| 278 | <td class="paramname"><em>key</em>, </td> | |
| 279 | </tr> | |
| 280 | <tr> | |
| 281 | <td class="paramkey"></td> | |
| 282 | <td></td> | |
| 283 | <td class="paramtype"><a class="el" href="ucx_8h.html#a0bc5bf89e556c1d45d10863d52728ac9">distance_func</a> </td> | |
| 284 | <td class="paramname"><em>dfnc</em>, </td> | |
| 285 | </tr> | |
| 286 | <tr> | |
| 287 | <td class="paramkey"></td> | |
| 288 | <td></td> | |
| 289 | <td class="paramtype">int </td> | |
| 290 | <td class="paramname"><em>mode</em> </td> | |
| 291 | </tr> | |
| 292 | <tr> | |
| 293 | <td></td> | |
| 294 | <td>)</td> | |
| 295 | <td></td><td></td> | |
| 296 | </tr> | |
| 297 | </table> | |
| 298 | </div><div class="memdoc"> | |
| 299 | ||
| 300 | <p>Finds a value within the tree. </p> | |
| 301 | <p>See <a class="el" href="avl_8h.html#a664986f64d6865605199fbff06e19cd5" title="Finds a node within the tree. ">ucx_avl_find_node()</a> for details.</p> | |
| 302 | <dl class="params"><dt>Parameters</dt><dd> | |
| 303 | <table class="params"> | |
| 304 | <tr><td class="paramname">tree</td><td>the <a class="el" href="structUcxAVLTree.html" title="UCX AVL Tree. ">UcxAVLTree</a> </td></tr> | |
| 305 | <tr><td class="paramname">key</td><td>the key </td></tr> | |
| 306 | <tr><td class="paramname">dfnc</td><td>the distance function </td></tr> | |
| 307 | <tr><td class="paramname">mode</td><td>the find mode </td></tr> | |
| 308 | </table> | |
| 309 | </dd> | |
| 310 | </dl> | |
| 311 | <dl class="section return"><dt>Returns</dt><dd>the value (or <code>NULL</code>, if no value can be found) </dd></dl> | |
| 312 | ||
| 313 | </div> | |
| 314 | </div> | |
| 315 | <a id="a664986f64d6865605199fbff06e19cd5"></a> | |
| 316 | <h2 class="memtitle"><span class="permalink"><a href="#a664986f64d6865605199fbff06e19cd5">◆ </a></span>ucx_avl_find_node()</h2> | |
| 317 | ||
| 318 | <div class="memitem"> | |
| 319 | <div class="memproto"> | |
| 320 | <table class="memname"> | |
| 321 | <tr> | |
| 322 | <td class="memname"><a class="el" href="structUcxAVLNode.html">UcxAVLNode</a>* ucx_avl_find_node </td> | |
| 323 | <td>(</td> | |
| 324 | <td class="paramtype"><a class="el" href="structUcxAVLTree.html">UcxAVLTree</a> * </td> | |
| 325 | <td class="paramname"><em>tree</em>, </td> | |
| 326 | </tr> | |
| 327 | <tr> | |
| 328 | <td class="paramkey"></td> | |
| 329 | <td></td> | |
| 330 | <td class="paramtype">intptr_t </td> | |
| 331 | <td class="paramname"><em>key</em>, </td> | |
| 332 | </tr> | |
| 333 | <tr> | |
| 334 | <td class="paramkey"></td> | |
| 335 | <td></td> | |
| 336 | <td class="paramtype"><a class="el" href="ucx_8h.html#a0bc5bf89e556c1d45d10863d52728ac9">distance_func</a> </td> | |
| 337 | <td class="paramname"><em>dfnc</em>, </td> | |
| 338 | </tr> | |
| 339 | <tr> | |
| 340 | <td class="paramkey"></td> | |
| 341 | <td></td> | |
| 342 | <td class="paramtype">int </td> | |
| 343 | <td class="paramname"><em>mode</em> </td> | |
| 344 | </tr> | |
| 345 | <tr> | |
| 346 | <td></td> | |
| 347 | <td>)</td> | |
| 348 | <td></td><td></td> | |
| 349 | </tr> | |
| 350 | </table> | |
| 351 | </div><div class="memdoc"> | |
| 352 | ||
| 353 | <p>Finds a node within the tree. </p> | |
| 354 | <p>The following modes are supported: </p><ul> | |
| 355 | <li> | |
| 356 | <a class="el" href="avl_8h.html#aaaf4a6f6f661cda7791db239212285d9" title="A mode for ucx_avl_find_node() with the same behavior as ucx_avl_get_node(). ">UCX_AVL_FIND_EXACT</a>: the same behavior as <a class="el" href="avl_8h.html#acf42da9a4168e47dc10b4ba0d27ceb4e" title="Gets the node from the tree, that is associated with the specified key. ">ucx_avl_get_node()</a> </li> | |
| 357 | <li> | |
| 358 | <a class="el" href="avl_8h.html#abd2446d544d5412b6997ee8a17bd368c" title="A mode for ucx_avl_find_node() finding the node whose key is at least as large as the specified key...">UCX_AVL_FIND_LOWER_BOUNDED</a>: finds the node whose key is at least as large as the specified key </li> | |
| 359 | <li> | |
| 360 | <a class="el" href="avl_8h.html#ac74ee7649c1e206b08b31f37dd68ca5e" title="A mode for ucx_avl_find_node() finding the node whose key is at most as large as the specified key...">UCX_AVL_FIND_UPPER_BOUNDED</a>: finds the node whose key is at most as large as the specified key </li> | |
| 361 | <li> | |
| 362 | <a class="el" href="avl_8h.html#af16f24d74fd6af0154de041566c6603b" title="A mode for ucx_avl_find_node() finding the node with a key that is as close to the specified key as p...">UCX_AVL_FIND_CLOSEST</a>: finds the node with a key that is as close to the specified key as possible. If the key is present, the behavior is like <a class="el" href="avl_8h.html#acf42da9a4168e47dc10b4ba0d27ceb4e" title="Gets the node from the tree, that is associated with the specified key. ">ucx_avl_get_node()</a>. This mode only returns <code>NULL</code> on empty trees. </li> | |
| 363 | </ul> | |
| 364 | <p>The distance function provided MUST agree with the compare function of the AVL tree.</p> | |
| 365 | <dl class="params"><dt>Parameters</dt><dd> | |
| 366 | <table class="params"> | |
| 367 | <tr><td class="paramname">tree</td><td>the <a class="el" href="structUcxAVLTree.html" title="UCX AVL Tree. ">UcxAVLTree</a> </td></tr> | |
| 368 | <tr><td class="paramname">key</td><td>the key </td></tr> | |
| 369 | <tr><td class="paramname">dfnc</td><td>the distance function </td></tr> | |
| 370 | <tr><td class="paramname">mode</td><td>the find mode </td></tr> | |
| 371 | </table> | |
| 372 | </dd> | |
| 373 | </dl> | |
| 374 | <dl class="section return"><dt>Returns</dt><dd>the node (or <code>NULL</code>, if no node can be found) </dd></dl> | |
| 375 | ||
| 376 | </div> | |
| 377 | </div> | |
| 378 | <a id="a2f92db538f25fce908d2cb3e5590944c"></a> | |
| 379 | <h2 class="memtitle"><span class="permalink"><a href="#a2f92db538f25fce908d2cb3e5590944c">◆ </a></span>ucx_avl_free()</h2> | |
| 380 | ||
| 381 | <div class="memitem"> | |
| 382 | <div class="memproto"> | |
| 383 | <table class="memname"> | |
| 384 | <tr> | |
| 385 | <td class="memname">void ucx_avl_free </td> | |
| 386 | <td>(</td> | |
| 387 | <td class="paramtype"><a class="el" href="structUcxAVLTree.html">UcxAVLTree</a> * </td> | |
| 388 | <td class="paramname"><em>tree</em></td><td>)</td> | |
| 389 | <td></td> | |
| 390 | </tr> | |
| 391 | </table> | |
| 392 | </div><div class="memdoc"> | |
| 393 | ||
| 394 | <p>Destroys a <a class="el" href="structUcxAVLTree.html" title="UCX AVL Tree. ">UcxAVLTree</a>. </p> | |
| 395 | <p>Note, that the contents are not automatically freed. Use may use <a class="el" href="avl_8h.html#a31ad7fb196ca211f1fc39f4e15f72279" title="Frees the contents of a UcxAVLTree. ">ucx_avl_free_content()</a> before calling this function.</p> | |
| 396 | <dl class="params"><dt>Parameters</dt><dd> | |
| 397 | <table class="params"> | |
| 398 | <tr><td class="paramname">tree</td><td>the tree to destroy </td></tr> | |
| 399 | </table> | |
| 400 | </dd> | |
| 401 | </dl> | |
| 402 | <dl class="section see"><dt>See also</dt><dd><a class="el" href="avl_8h.html#a31ad7fb196ca211f1fc39f4e15f72279" title="Frees the contents of a UcxAVLTree. ">ucx_avl_free_content()</a> </dd></dl> | |
| 403 | ||
| 404 | </div> | |
| 405 | </div> | |
| 406 | <a id="a31ad7fb196ca211f1fc39f4e15f72279"></a> | |
| 407 | <h2 class="memtitle"><span class="permalink"><a href="#a31ad7fb196ca211f1fc39f4e15f72279">◆ </a></span>ucx_avl_free_content()</h2> | |
| 408 | ||
| 409 | <div class="memitem"> | |
| 410 | <div class="memproto"> | |
| 411 | <table class="memname"> | |
| 412 | <tr> | |
| 413 | <td class="memname">void ucx_avl_free_content </td> | |
| 414 | <td>(</td> | |
| 415 | <td class="paramtype"><a class="el" href="structUcxAVLTree.html">UcxAVLTree</a> * </td> | |
| 416 | <td class="paramname"><em>tree</em>, </td> | |
| 417 | </tr> | |
| 418 | <tr> | |
| 419 | <td class="paramkey"></td> | |
| 420 | <td></td> | |
| 421 | <td class="paramtype"><a class="el" href="ucx_8h.html#ad2b370c2809914c8b7fedab163c266b3">ucx_destructor</a> </td> | |
| 422 | <td class="paramname"><em>destr</em> </td> | |
| 423 | </tr> | |
| 424 | <tr> | |
| 425 | <td></td> | |
| 426 | <td>)</td> | |
| 427 | <td></td><td></td> | |
| 428 | </tr> | |
| 429 | </table> | |
| 430 | </div><div class="memdoc"> | |
| 431 | ||
| 432 | <p>Frees the contents of a <a class="el" href="structUcxAVLTree.html" title="UCX AVL Tree. ">UcxAVLTree</a>. </p> | |
| 433 | <p>This is a convenience function that iterates over the tree and passes all values to the specified destructor function.</p> | |
| 434 | <p>If no destructor is specified (<code>NULL</code>), the free() function of the tree's own allocator is used.</p> | |
| 435 | <p>You must ensure, that it is valid to pass each value in the map to the same destructor function.</p> | |
| 436 | <p>You should free the entire tree afterwards, as the contents will be invalid.</p> | |
| 437 | <dl class="params"><dt>Parameters</dt><dd> | |
| 438 | <table class="params"> | |
| 439 | <tr><td class="paramname">tree</td><td>for which the contents shall be freed </td></tr> | |
| 440 | <tr><td class="paramname">destr</td><td>optional pointer to a destructor function </td></tr> | |
| 441 | </table> | |
| 442 | </dd> | |
| 443 | </dl> | |
| 444 | <dl class="section see"><dt>See also</dt><dd><a class="el" href="avl_8h.html#a2f92db538f25fce908d2cb3e5590944c" title="Destroys a UcxAVLTree. ">ucx_avl_free()</a> </dd></dl> | |
| 445 | ||
| 446 | </div> | |
| 447 | </div> | |
| 448 | <a id="adbcf7ceb3f014a30c7214f7304519efe"></a> | |
| 449 | <h2 class="memtitle"><span class="permalink"><a href="#adbcf7ceb3f014a30c7214f7304519efe">◆ </a></span>ucx_avl_get()</h2> | |
| 450 | ||
| 451 | <div class="memitem"> | |
| 452 | <div class="memproto"> | |
| 453 | <table class="memname"> | |
| 454 | <tr> | |
| 455 | <td class="memname">void* ucx_avl_get </td> | |
| 456 | <td>(</td> | |
| 457 | <td class="paramtype"><a class="el" href="structUcxAVLTree.html">UcxAVLTree</a> * </td> | |
| 458 | <td class="paramname"><em>tree</em>, </td> | |
| 459 | </tr> | |
| 460 | <tr> | |
| 461 | <td class="paramkey"></td> | |
| 462 | <td></td> | |
| 463 | <td class="paramtype">intptr_t </td> | |
| 464 | <td class="paramname"><em>key</em> </td> | |
| 465 | </tr> | |
| 466 | <tr> | |
| 467 | <td></td> | |
| 468 | <td>)</td> | |
| 469 | <td></td><td></td> | |
| 470 | </tr> | |
| 471 | </table> | |
| 472 | </div><div class="memdoc"> | |
| 473 | ||
| 474 | <p>Gets the value from the tree, that is associated with the specified key. </p> | |
| 475 | <dl class="params"><dt>Parameters</dt><dd> | |
| 476 | <table class="params"> | |
| 477 | <tr><td class="paramname">tree</td><td>the <a class="el" href="structUcxAVLTree.html" title="UCX AVL Tree. ">UcxAVLTree</a> </td></tr> | |
| 478 | <tr><td class="paramname">key</td><td>the key </td></tr> | |
| 479 | </table> | |
| 480 | </dd> | |
| 481 | </dl> | |
| 482 | <dl class="section return"><dt>Returns</dt><dd>the value (or <code>NULL</code>, if the key is not present) </dd></dl> | |
| 483 | ||
| 484 | </div> | |
| 485 | </div> | |
| 486 | <a id="acf42da9a4168e47dc10b4ba0d27ceb4e"></a> | |
| 487 | <h2 class="memtitle"><span class="permalink"><a href="#acf42da9a4168e47dc10b4ba0d27ceb4e">◆ </a></span>ucx_avl_get_node()</h2> | |
| 488 | ||
| 489 | <div class="memitem"> | |
| 490 | <div class="memproto"> | |
| 491 | <table class="memname"> | |
| 492 | <tr> | |
| 493 | <td class="memname"><a class="el" href="structUcxAVLNode.html">UcxAVLNode</a>* ucx_avl_get_node </td> | |
| 494 | <td>(</td> | |
| 495 | <td class="paramtype"><a class="el" href="structUcxAVLTree.html">UcxAVLTree</a> * </td> | |
| 496 | <td class="paramname"><em>tree</em>, </td> | |
| 497 | </tr> | |
| 498 | <tr> | |
| 499 | <td class="paramkey"></td> | |
| 500 | <td></td> | |
| 501 | <td class="paramtype">intptr_t </td> | |
| 502 | <td class="paramname"><em>key</em> </td> | |
| 503 | </tr> | |
| 504 | <tr> | |
| 505 | <td></td> | |
| 506 | <td>)</td> | |
| 507 | <td></td><td></td> | |
| 508 | </tr> | |
| 509 | </table> | |
| 510 | </div><div class="memdoc"> | |
| 511 | ||
| 512 | <p>Gets the node from the tree, that is associated with the specified key. </p> | |
| 513 | <dl class="params"><dt>Parameters</dt><dd> | |
| 514 | <table class="params"> | |
| 515 | <tr><td class="paramname">tree</td><td>the <a class="el" href="structUcxAVLTree.html" title="UCX AVL Tree. ">UcxAVLTree</a> </td></tr> | |
| 516 | <tr><td class="paramname">key</td><td>the key </td></tr> | |
| 517 | </table> | |
| 518 | </dd> | |
| 519 | </dl> | |
| 520 | <dl class="section return"><dt>Returns</dt><dd>the node (or <code>NULL</code>, if the key is not present) </dd></dl> | |
| 521 | ||
| 522 | </div> | |
| 523 | </div> | |
| 524 | <a id="a11b043d65a11b7092d5d98b298e5ede3"></a> | |
| 525 | <h2 class="memtitle"><span class="permalink"><a href="#a11b043d65a11b7092d5d98b298e5ede3">◆ </a></span>ucx_avl_new()</h2> | |
| 526 | ||
| 527 | <div class="memitem"> | |
| 528 | <div class="memproto"> | |
| 529 | <table class="memname"> | |
| 530 | <tr> | |
| 531 | <td class="memname"><a class="el" href="structUcxAVLTree.html">UcxAVLTree</a>* ucx_avl_new </td> | |
| 532 | <td>(</td> | |
| 533 | <td class="paramtype"><a class="el" href="ucx_8h.html#afe5e2d5dbf34778e0e97852051570791">cmp_func</a> </td> | |
| 534 | <td class="paramname"><em>cmpfunc</em></td><td>)</td> | |
| 535 | <td></td> | |
| 536 | </tr> | |
| 537 | </table> | |
| 538 | </div><div class="memdoc"> | |
| 539 | ||
| 540 | <p>Initializes a new <a class="el" href="structUcxAVLTree.html" title="UCX AVL Tree. ">UcxAVLTree</a> with a default allocator. </p> | |
| 541 | <dl class="params"><dt>Parameters</dt><dd> | |
| 542 | <table class="params"> | |
| 543 | <tr><td class="paramname">cmpfunc</td><td>the compare function that shall be used </td></tr> | |
| 544 | </table> | |
| 545 | </dd> | |
| 546 | </dl> | |
| 547 | <dl class="section return"><dt>Returns</dt><dd>a new <a class="el" href="structUcxAVLTree.html" title="UCX AVL Tree. ">UcxAVLTree</a> object </dd></dl> | |
| 548 | <dl class="section see"><dt>See also</dt><dd><a class="el" href="avl_8h.html#af0f868d67e9dc08b4867c02a06c23ee2" title="Initializes a new UcxAVLTree with the specified allocator. ">ucx_avl_new_a()</a> </dd></dl> | |
| 549 | ||
| 550 | </div> | |
| 551 | </div> | |
| 552 | <a id="af0f868d67e9dc08b4867c02a06c23ee2"></a> | |
| 553 | <h2 class="memtitle"><span class="permalink"><a href="#af0f868d67e9dc08b4867c02a06c23ee2">◆ </a></span>ucx_avl_new_a()</h2> | |
| 554 | ||
| 555 | <div class="memitem"> | |
| 556 | <div class="memproto"> | |
| 557 | <table class="memname"> | |
| 558 | <tr> | |
| 559 | <td class="memname"><a class="el" href="structUcxAVLTree.html">UcxAVLTree</a>* ucx_avl_new_a </td> | |
| 560 | <td>(</td> | |
| 561 | <td class="paramtype"><a class="el" href="ucx_8h.html#afe5e2d5dbf34778e0e97852051570791">cmp_func</a> </td> | |
| 562 | <td class="paramname"><em>cmpfunc</em>, </td> | |
| 563 | </tr> | |
| 564 | <tr> | |
| 565 | <td class="paramkey"></td> | |
| 566 | <td></td> | |
| 567 | <td class="paramtype"><a class="el" href="structUcxAllocator.html">UcxAllocator</a> * </td> | |
| 568 | <td class="paramname"><em>allocator</em> </td> | |
| 569 | </tr> | |
| 570 | <tr> | |
| 571 | <td></td> | |
| 572 | <td>)</td> | |
| 573 | <td></td><td></td> | |
| 574 | </tr> | |
| 575 | </table> | |
| 576 | </div><div class="memdoc"> | |
| 577 | ||
| 578 | <p>Initializes a new <a class="el" href="structUcxAVLTree.html" title="UCX AVL Tree. ">UcxAVLTree</a> with the specified allocator. </p> | |
| 579 | <p>The cmpfunc should be capable of comparing two keys within this AVL tree. So if you want to use null terminated strings as keys, you could use the <a class="el" href="utils_8h.html#aa6a37b9d172b6a5b2803d152f9e1b258" title="Wraps the strcmp function. ">ucx_cmp_str()</a> function here.</p> | |
| 580 | <dl class="params"><dt>Parameters</dt><dd> | |
| 581 | <table class="params"> | |
| 582 | <tr><td class="paramname">cmpfunc</td><td>the compare function that shall be used </td></tr> | |
| 583 | <tr><td class="paramname">allocator</td><td>the <a class="el" href="structUcxAllocator.html" title="UCX allocator data structure containing memory management functions. ">UcxAllocator</a> that shall be used </td></tr> | |
| 584 | </table> | |
| 585 | </dd> | |
| 586 | </dl> | |
| 587 | <dl class="section return"><dt>Returns</dt><dd>a new <a class="el" href="structUcxAVLTree.html" title="UCX AVL Tree. ">UcxAVLTree</a> object </dd></dl> | |
| 588 | ||
| 589 | </div> | |
| 590 | </div> | |
| 591 | <a id="a0e739aeb66dda6a6a3f6eb51b50cf346"></a> | |
| 592 | <h2 class="memtitle"><span class="permalink"><a href="#a0e739aeb66dda6a6a3f6eb51b50cf346">◆ </a></span>ucx_avl_pred()</h2> | |
| 593 | ||
| 594 | <div class="memitem"> | |
| 595 | <div class="memproto"> | |
| 596 | <table class="memname"> | |
| 597 | <tr> | |
| 598 | <td class="memname"><a class="el" href="structUcxAVLNode.html">UcxAVLNode</a>* ucx_avl_pred </td> | |
| 599 | <td>(</td> | |
| 600 | <td class="paramtype"><a class="el" href="structUcxAVLNode.html">UcxAVLNode</a> * </td> | |
| 601 | <td class="paramname"><em>node</em></td><td>)</td> | |
| 602 | <td></td> | |
| 603 | </tr> | |
| 604 | </table> | |
| 605 | </div><div class="memdoc"> | |
| 606 | ||
| 607 | <p>Finds the in-order predecessor of the given node. </p> | |
| 608 | <dl class="params"><dt>Parameters</dt><dd> | |
| 609 | <table class="params"> | |
| 610 | <tr><td class="paramname">node</td><td>an AVL node </td></tr> | |
| 611 | </table> | |
| 612 | </dd> | |
| 613 | </dl> | |
| 614 | <dl class="section return"><dt>Returns</dt><dd>the in-order predecessor of the given node, or <code>NULL</code> if the given node is the in-order minimum </dd></dl> | |
| 615 | ||
| 616 | </div> | |
| 617 | </div> | |
| 618 | <a id="aec401fab4a24a7edffa734f9baf88577"></a> | |
| 619 | <h2 class="memtitle"><span class="permalink"><a href="#aec401fab4a24a7edffa734f9baf88577">◆ </a></span>ucx_avl_put()</h2> | |
| 620 | ||
| 621 | <div class="memitem"> | |
| 622 | <div class="memproto"> | |
| 623 | <table class="memname"> | |
| 624 | <tr> | |
| 625 | <td class="memname">int ucx_avl_put </td> | |
| 626 | <td>(</td> | |
| 627 | <td class="paramtype"><a class="el" href="structUcxAVLTree.html">UcxAVLTree</a> * </td> | |
| 628 | <td class="paramname"><em>tree</em>, </td> | |
| 629 | </tr> | |
| 630 | <tr> | |
| 631 | <td class="paramkey"></td> | |
| 632 | <td></td> | |
| 633 | <td class="paramtype">intptr_t </td> | |
| 634 | <td class="paramname"><em>key</em>, </td> | |
| 635 | </tr> | |
| 636 | <tr> | |
| 637 | <td class="paramkey"></td> | |
| 638 | <td></td> | |
| 639 | <td class="paramtype">void * </td> | |
| 640 | <td class="paramname"><em>value</em> </td> | |
| 641 | </tr> | |
| 642 | <tr> | |
| 643 | <td></td> | |
| 644 | <td>)</td> | |
| 645 | <td></td><td></td> | |
| 646 | </tr> | |
| 647 | </table> | |
| 648 | </div><div class="memdoc"> | |
| 649 | ||
| 650 | <p>Puts a key/value pair into the tree. </p> | |
| 651 | <p>Attention: use this function only, if a possible old value does not need to be preserved.</p> | |
| 652 | <dl class="params"><dt>Parameters</dt><dd> | |
| 653 | <table class="params"> | |
| 654 | <tr><td class="paramname">tree</td><td>the <a class="el" href="structUcxAVLTree.html" title="UCX AVL Tree. ">UcxAVLTree</a> </td></tr> | |
| 655 | <tr><td class="paramname">key</td><td>the key </td></tr> | |
| 656 | <tr><td class="paramname">value</td><td>the new value </td></tr> | |
| 657 | </table> | |
| 658 | </dd> | |
| 659 | </dl> | |
| 660 | <dl class="section return"><dt>Returns</dt><dd>zero, if and only if the operation succeeded </dd></dl> | |
| 661 | ||
| 662 | </div> | |
| 663 | </div> | |
| 664 | <a id="a32cf8955cc0226a82bacfc7b76d6474c"></a> | |
| 665 | <h2 class="memtitle"><span class="permalink"><a href="#a32cf8955cc0226a82bacfc7b76d6474c">◆ </a></span>ucx_avl_put_s()</h2> | |
| 666 | ||
| 667 | <div class="memitem"> | |
| 668 | <div class="memproto"> | |
| 669 | <table class="memname"> | |
| 670 | <tr> | |
| 671 | <td class="memname">int ucx_avl_put_s </td> | |
| 672 | <td>(</td> | |
| 673 | <td class="paramtype"><a class="el" href="structUcxAVLTree.html">UcxAVLTree</a> * </td> | |
| 674 | <td class="paramname"><em>tree</em>, </td> | |
| 675 | </tr> | |
| 676 | <tr> | |
| 677 | <td class="paramkey"></td> | |
| 678 | <td></td> | |
| 679 | <td class="paramtype">intptr_t </td> | |
| 680 | <td class="paramname"><em>key</em>, </td> | |
| 681 | </tr> | |
| 682 | <tr> | |
| 683 | <td class="paramkey"></td> | |
| 684 | <td></td> | |
| 685 | <td class="paramtype">void * </td> | |
| 686 | <td class="paramname"><em>value</em>, </td> | |
| 687 | </tr> | |
| 688 | <tr> | |
| 689 | <td class="paramkey"></td> | |
| 690 | <td></td> | |
| 691 | <td class="paramtype">void ** </td> | |
| 692 | <td class="paramname"><em>oldvalue</em> </td> | |
| 693 | </tr> | |
| 694 | <tr> | |
| 695 | <td></td> | |
| 696 | <td>)</td> | |
| 697 | <td></td><td></td> | |
| 698 | </tr> | |
| 699 | </table> | |
| 700 | </div><div class="memdoc"> | |
| 701 | ||
| 702 | <p>Puts a key/value pair into the tree. </p> | |
| 703 | <p>This is a secure function which saves the old value to the variable pointed at by oldvalue.</p> | |
| 704 | <dl class="params"><dt>Parameters</dt><dd> | |
| 705 | <table class="params"> | |
| 706 | <tr><td class="paramname">tree</td><td>the <a class="el" href="structUcxAVLTree.html" title="UCX AVL Tree. ">UcxAVLTree</a> </td></tr> | |
| 707 | <tr><td class="paramname">key</td><td>the key </td></tr> | |
| 708 | <tr><td class="paramname">value</td><td>the new value </td></tr> | |
| 709 | <tr><td class="paramname">oldvalue</td><td>optional: a pointer to the location where a possible old value shall be stored </td></tr> | |
| 710 | </table> | |
| 711 | </dd> | |
| 712 | </dl> | |
| 713 | <dl class="section return"><dt>Returns</dt><dd>zero, if and only if the operation succeeded </dd></dl> | |
| 714 | ||
| 715 | </div> | |
| 716 | </div> | |
| 717 | <a id="a1d821119c805d7fbb7e424bc3effeba9"></a> | |
| 718 | <h2 class="memtitle"><span class="permalink"><a href="#a1d821119c805d7fbb7e424bc3effeba9">◆ </a></span>ucx_avl_remove()</h2> | |
| 719 | ||
| 720 | <div class="memitem"> | |
| 721 | <div class="memproto"> | |
| 722 | <table class="memname"> | |
| 723 | <tr> | |
| 724 | <td class="memname">int ucx_avl_remove </td> | |
| 725 | <td>(</td> | |
| 726 | <td class="paramtype"><a class="el" href="structUcxAVLTree.html">UcxAVLTree</a> * </td> | |
| 727 | <td class="paramname"><em>tree</em>, </td> | |
| 728 | </tr> | |
| 729 | <tr> | |
| 730 | <td class="paramkey"></td> | |
| 731 | <td></td> | |
| 732 | <td class="paramtype">intptr_t </td> | |
| 733 | <td class="paramname"><em>key</em> </td> | |
| 734 | </tr> | |
| 735 | <tr> | |
| 736 | <td></td> | |
| 737 | <td>)</td> | |
| 738 | <td></td><td></td> | |
| 739 | </tr> | |
| 740 | </table> | |
| 741 | </div><div class="memdoc"> | |
| 742 | ||
| 743 | <p>Removes an element from the AVL tree. </p> | |
| 744 | <dl class="params"><dt>Parameters</dt><dd> | |
| 745 | <table class="params"> | |
| 746 | <tr><td class="paramname">tree</td><td>the <a class="el" href="structUcxAVLTree.html" title="UCX AVL Tree. ">UcxAVLTree</a> </td></tr> | |
| 747 | <tr><td class="paramname">key</td><td>the key </td></tr> | |
| 748 | </table> | |
| 749 | </dd> | |
| 750 | </dl> | |
| 751 | <dl class="section return"><dt>Returns</dt><dd>zero, if and only if an element has been removed </dd></dl> | |
| 752 | ||
| 753 | </div> | |
| 754 | </div> | |
| 755 | <a id="a9a792b7d9e58073deef74a341f8bc720"></a> | |
| 756 | <h2 class="memtitle"><span class="permalink"><a href="#a9a792b7d9e58073deef74a341f8bc720">◆ </a></span>ucx_avl_remove_node()</h2> | |
| 757 | ||
| 758 | <div class="memitem"> | |
| 759 | <div class="memproto"> | |
| 760 | <table class="memname"> | |
| 761 | <tr> | |
| 762 | <td class="memname">int ucx_avl_remove_node </td> | |
| 763 | <td>(</td> | |
| 764 | <td class="paramtype"><a class="el" href="structUcxAVLTree.html">UcxAVLTree</a> * </td> | |
| 765 | <td class="paramname"><em>tree</em>, </td> | |
| 766 | </tr> | |
| 767 | <tr> | |
| 768 | <td class="paramkey"></td> | |
| 769 | <td></td> | |
| 770 | <td class="paramtype"><a class="el" href="structUcxAVLNode.html">UcxAVLNode</a> * </td> | |
| 771 | <td class="paramname"><em>node</em> </td> | |
| 772 | </tr> | |
| 773 | <tr> | |
| 774 | <td></td> | |
| 775 | <td>)</td> | |
| 776 | <td></td><td></td> | |
| 777 | </tr> | |
| 778 | </table> | |
| 779 | </div><div class="memdoc"> | |
| 780 | ||
| 781 | <p>Removes a node from the AVL tree. </p> | |
| 782 | <p>Note: the specified node is logically removed. The tree implementation decides which memory area is freed. In most cases the here provided node is freed, so its further use is generally undefined.</p> | |
| 783 | <dl class="params"><dt>Parameters</dt><dd> | |
| 784 | <table class="params"> | |
| 785 | <tr><td class="paramname">tree</td><td>the <a class="el" href="structUcxAVLTree.html" title="UCX AVL Tree. ">UcxAVLTree</a> </td></tr> | |
| 786 | <tr><td class="paramname">node</td><td>the node to remove </td></tr> | |
| 787 | </table> | |
| 788 | </dd> | |
| 789 | </dl> | |
| 790 | <dl class="section return"><dt>Returns</dt><dd>zero, if and only if an element has been removed </dd></dl> | |
| 791 | ||
| 792 | </div> | |
| 793 | </div> | |
| 794 | <a id="a01aeeecd6415f0cc2b623486eb28f254"></a> | |
| 795 | <h2 class="memtitle"><span class="permalink"><a href="#a01aeeecd6415f0cc2b623486eb28f254">◆ </a></span>ucx_avl_remove_s()</h2> | |
| 796 | ||
| 797 | <div class="memitem"> | |
| 798 | <div class="memproto"> | |
| 799 | <table class="memname"> | |
| 800 | <tr> | |
| 801 | <td class="memname">int ucx_avl_remove_s </td> | |
| 802 | <td>(</td> | |
| 803 | <td class="paramtype"><a class="el" href="structUcxAVLTree.html">UcxAVLTree</a> * </td> | |
| 804 | <td class="paramname"><em>tree</em>, </td> | |
| 805 | </tr> | |
| 806 | <tr> | |
| 807 | <td class="paramkey"></td> | |
| 808 | <td></td> | |
| 809 | <td class="paramtype">intptr_t </td> | |
| 810 | <td class="paramname"><em>key</em>, </td> | |
| 811 | </tr> | |
| 812 | <tr> | |
| 813 | <td class="paramkey"></td> | |
| 814 | <td></td> | |
| 815 | <td class="paramtype">intptr_t * </td> | |
| 816 | <td class="paramname"><em>oldkey</em>, </td> | |
| 817 | </tr> | |
| 818 | <tr> | |
| 819 | <td class="paramkey"></td> | |
| 820 | <td></td> | |
| 821 | <td class="paramtype">void ** </td> | |
| 822 | <td class="paramname"><em>oldvalue</em> </td> | |
| 823 | </tr> | |
| 824 | <tr> | |
| 825 | <td></td> | |
| 826 | <td>)</td> | |
| 827 | <td></td><td></td> | |
| 828 | </tr> | |
| 829 | </table> | |
| 830 | </div><div class="memdoc"> | |
| 831 | ||
| 832 | <p>Removes an element from the AVL tree. </p> | |
| 833 | <p>This is a secure function which saves the old key and value data from node to the variables at the location of oldkey and oldvalue (if specified), so they can be freed afterwards (if necessary).</p> | |
| 834 | <p>Note: the returned key in oldkey is possibly not the same as the provided key for the lookup (in terms of memory location).</p> | |
| 835 | <dl class="params"><dt>Parameters</dt><dd> | |
| 836 | <table class="params"> | |
| 837 | <tr><td class="paramname">tree</td><td>the <a class="el" href="structUcxAVLTree.html" title="UCX AVL Tree. ">UcxAVLTree</a> </td></tr> | |
| 838 | <tr><td class="paramname">key</td><td>the key of the element to remove </td></tr> | |
| 839 | <tr><td class="paramname">oldkey</td><td>optional: a pointer to the location where the old key shall be stored </td></tr> | |
| 840 | <tr><td class="paramname">oldvalue</td><td>optional: a pointer to the location where the old value shall be stored </td></tr> | |
| 841 | </table> | |
| 842 | </dd> | |
| 843 | </dl> | |
| 844 | <dl class="section return"><dt>Returns</dt><dd>zero, if and only if an element has been removed </dd></dl> | |
| 845 | ||
| 846 | </div> | |
| 847 | </div> | |
| 848 | <a id="aab1ad9b027ff5e50671aa0ee84e2d541"></a> | |
| 849 | <h2 class="memtitle"><span class="permalink"><a href="#aab1ad9b027ff5e50671aa0ee84e2d541">◆ </a></span>ucx_avl_succ()</h2> | |
| 850 | ||
| 851 | <div class="memitem"> | |
| 852 | <div class="memproto"> | |
| 853 | <table class="memname"> | |
| 854 | <tr> | |
| 855 | <td class="memname"><a class="el" href="structUcxAVLNode.html">UcxAVLNode</a>* ucx_avl_succ </td> | |
| 856 | <td>(</td> | |
| 857 | <td class="paramtype"><a class="el" href="structUcxAVLNode.html">UcxAVLNode</a> * </td> | |
| 858 | <td class="paramname"><em>node</em></td><td>)</td> | |
| 859 | <td></td> | |
| 860 | </tr> | |
| 861 | </table> | |
| 862 | </div><div class="memdoc"> | |
| 863 | ||
| 864 | <p>Finds the in-order successor of the given node. </p> | |
| 865 | <dl class="params"><dt>Parameters</dt><dd> | |
| 866 | <table class="params"> | |
| 867 | <tr><td class="paramname">node</td><td>an AVL node </td></tr> | |
| 868 | </table> | |
| 869 | </dd> | |
| 870 | </dl> | |
| 871 | <dl class="section return"><dt>Returns</dt><dd>the in-order successor of the given node, or <code>NULL</code> if the given node is the in-order maximum </dd></dl> | |
| 872 | ||
| 873 | </div> | |
| 874 | </div> | |
| 875 | </div><!-- contents --> | |
| 876 | <!-- start footer part --> | |
| 877 | <hr class="footer"/><address class="footer"><small> | |
| 878 | Generated on Thu Dec 19 2019 19:58:24 for ucx by  <a href="http://www.doxygen.org/index.html"> | |
| 879 | <img class="footer" src="doxygen.png" alt="doxygen"/> | |
| 880 | </a> 1.8.13 | |
| 881 | </small></address> | |
| 882 | </body> | |
| 883 | </html> |
