<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> <html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1"> <title>ldns documentation</title> <link href="doxygen.css" rel="stylesheet" type="text/css"> <link href="tabs.css" rel="stylesheet" type="text/css"> </head><body> <div class="logo"> <img src="LogoInGradientBar2-y100.png"/> </div> <!-- Generated by Doxygen 1.7.4 --> <div id="navrow1" class="tabs"> <ul class="tablist"> <li><a href="index.html"><span>Main Page</span></a></li> <li><a href="pages.html"><span>Related Pages</span></a></li> <li><a href="annotated.html"><span>Data Structures</span></a></li> <li class="current"><a href="files.html"><span>Files</span></a></li> <li><a href="dirs.html"><span>Directories</span></a></li> </ul> </div> <div id="navrow2" class="tabs2"> <ul class="tablist"> <li><a href="files.html"><span>File List</span></a></li> <li><a href="globals.html"><span>Globals</span></a></li> </ul> </div> <div id="nav-path" class="navpath"> <ul> <li class="navelem"><a class="el" href="dir_7a7a565456b510ac01baf8655647d8a2.html">ldns</a> </li> </ul> </div> </div> <div class="header"> <div class="summary"> <a href="#nested-classes">Data Structures</a> | <a href="#define-members">Defines</a> | <a href="#typedef-members">Typedefs</a> | <a href="#func-members">Functions</a> | <a href="#var-members">Variables</a> </div> <div class="headertitle"> <div class="title">rbtree.h File Reference</div> </div> </div> <div class="contents"> <p>Red black tree. <a href="#details">More...</a></p> <p><a href="rbtree_8h_source.html">Go to the source code of this file.</a></p> <table class="memberdecls"> <tr><td colspan="2"><h2><a name="nested-classes"></a> Data Structures</h2></td></tr> <tr><td class="memItemLeft" align="right" valign="top">struct  </td><td class="memItemRight" valign="bottom"><a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a></td></tr> <tr><td class="mdescLeft"> </td><td class="mdescRight">The rbnode_t struct definition. <a href="structldns__rbnode__t.html#details">More...</a><br/></td></tr> <tr><td class="memItemLeft" align="right" valign="top">struct  </td><td class="memItemRight" valign="bottom"><a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a></td></tr> <tr><td class="mdescLeft"> </td><td class="mdescRight">definition for tree struct <a href="structldns__rbtree__t.html#details">More...</a><br/></td></tr> <tr><td colspan="2"><h2><a name="define-members"></a> Defines</h2></td></tr> <tr><td class="memItemLeft" align="right" valign="top">#define </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#ab30c305b53af0832956712d035d96631">LDNS_RBTREE_NULL</a>   &<a class="el" href="rbtree_8h.html#a9c65c464bbd4a3b574515a2547d3a268">ldns_rbtree_null_node</a></td></tr> <tr><td class="mdescLeft"> </td><td class="mdescRight">The nullpointer, points to empty node. <a href="#ab30c305b53af0832956712d035d96631"></a><br/></td></tr> <tr><td class="memItemLeft" align="right" valign="top">#define </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#aac9e2938a0a05c3817dede8d62070ce7">LDNS_RBTREE_FOR</a>(node, type, rbtree)</td></tr> <tr><td class="mdescLeft"> </td><td class="mdescRight">Call with node=variable of struct* with rbnode_t as first element. <a href="#aac9e2938a0a05c3817dede8d62070ce7"></a><br/></td></tr> <tr><td colspan="2"><h2><a name="typedef-members"></a> Typedefs</h2></td></tr> <tr><td class="memItemLeft" align="right" valign="top">typedef struct <a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#afe02fd4e8e5d36ff36fbe24832284505">ldns_rbnode_t</a></td></tr> <tr><td class="mdescLeft"> </td><td class="mdescRight">This structure must be the first member of the data structure in the rbtree. <a href="#afe02fd4e8e5d36ff36fbe24832284505"></a><br/></td></tr> <tr><td class="memItemLeft" align="right" valign="top">typedef struct <a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#ae362fd6665ea1d8409bb413610425482">ldns_rbtree_t</a></td></tr> <tr><td class="mdescLeft"> </td><td class="mdescRight">An entire red black tree. <a href="#ae362fd6665ea1d8409bb413610425482"></a><br/></td></tr> <tr><td colspan="2"><h2><a name="func-members"></a> Functions</h2></td></tr> <tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#a1319e3ff5b8355d6e1e7b65554bc854d">ldns_rbtree_create</a> (int(*cmpf)(const void *, const void *))</td></tr> <tr><td class="mdescLeft"> </td><td class="mdescRight">Create new tree (malloced) with given key compare function. <a href="#a1319e3ff5b8355d6e1e7b65554bc854d"></a><br/></td></tr> <tr><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#a3762aeeab2725b04a9e0dfaf817c062f">ldns_rbtree_free</a> (<a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> *rbtree)</td></tr> <tr><td class="mdescLeft"> </td><td class="mdescRight">Free the complete tree (but not its keys) <a href="#a3762aeeab2725b04a9e0dfaf817c062f"></a><br/></td></tr> <tr><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#abfc60e1266fe66bda7d3fd7305787401">ldns_rbtree_init</a> (<a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> *rbtree, int(*cmpf)(const void *, const void *))</td></tr> <tr><td class="mdescLeft"> </td><td class="mdescRight">Init a new tree (malloced by caller) with given key compare function. <a href="#abfc60e1266fe66bda7d3fd7305787401"></a><br/></td></tr> <tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#af7453903aed843b18ec24de879faf98f">ldns_rbtree_insert</a> (<a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> *rbtree, <a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a> *data)</td></tr> <tr><td class="mdescLeft"> </td><td class="mdescRight">Insert data into the tree. <a href="#af7453903aed843b18ec24de879faf98f"></a><br/></td></tr> <tr><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#a7cfa1759127e6133df02b04731b05dc9">ldns_rbtree_insert_vref</a> (<a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a> *data, void *rbtree)</td></tr> <tr><td class="mdescLeft"> </td><td class="mdescRight">Insert data into the tree (reversed arguments, for use as callback) <a href="#a7cfa1759127e6133df02b04731b05dc9"></a><br/></td></tr> <tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#ab6d2736cd058aaee5af1bf4d59265764">ldns_rbtree_delete</a> (<a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> *rbtree, const void *key)</td></tr> <tr><td class="mdescLeft"> </td><td class="mdescRight">Delete element from tree. <a href="#ab6d2736cd058aaee5af1bf4d59265764"></a><br/></td></tr> <tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#ab95e41509757f1f9652011ce18475d5a">ldns_rbtree_search</a> (<a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> *rbtree, const void *key)</td></tr> <tr><td class="mdescLeft"> </td><td class="mdescRight">Find key in tree. <a href="#ab95e41509757f1f9652011ce18475d5a"></a><br/></td></tr> <tr><td class="memItemLeft" align="right" valign="top">int </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#aaf5f35e7648861e0d1006f5de1199b14">ldns_rbtree_find_less_equal</a> (<a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> *rbtree, const void *key, <a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a> **result)</td></tr> <tr><td class="mdescLeft"> </td><td class="mdescRight">Find, but match does not have to be exact. <a href="#aaf5f35e7648861e0d1006f5de1199b14"></a><br/></td></tr> <tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#a76946c6350e5d16e645c5c0bbecfe017">ldns_rbtree_first</a> (<a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> *rbtree)</td></tr> <tr><td class="mdescLeft"> </td><td class="mdescRight">Returns first (smallest) node in the tree. <a href="#a76946c6350e5d16e645c5c0bbecfe017"></a><br/></td></tr> <tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#a627e270f8f549b2077c807ab2dd7b54a">ldns_rbtree_last</a> (<a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> *rbtree)</td></tr> <tr><td class="mdescLeft"> </td><td class="mdescRight">Returns last (largest) node in the tree. <a href="#a627e270f8f549b2077c807ab2dd7b54a"></a><br/></td></tr> <tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#a1700685fdaad3700634fa50a0a899a3e">ldns_rbtree_next</a> (<a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a> *rbtree)</td></tr> <tr><td class="mdescLeft"> </td><td class="mdescRight">Returns next larger node in the tree. <a href="#a1700685fdaad3700634fa50a0a899a3e"></a><br/></td></tr> <tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#a50d8a3fcf5969a79866c887070f13f98">ldns_rbtree_previous</a> (<a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a> *rbtree)</td></tr> <tr><td class="mdescLeft"> </td><td class="mdescRight">Returns previous smaller node in the tree. <a href="#a50d8a3fcf5969a79866c887070f13f98"></a><br/></td></tr> <tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#a211164b6238ae3aa0c6ad567e8c78944">ldns_rbtree_split</a> (<a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> *tree, size_t elements)</td></tr> <tr><td class="mdescLeft"> </td><td class="mdescRight">split off 'elements' number of elements from the start of the name tree and return a new tree containing those elements <a href="#a211164b6238ae3aa0c6ad567e8c78944"></a><br/></td></tr> <tr><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#abf2881787d48cdf3052dd1aee89520c0">ldns_rbtree_join</a> (<a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> *tree1, <a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> *tree2)</td></tr> <tr><td class="mdescLeft"> </td><td class="mdescRight">add all node from the second tree to the first (removing them from the second), and fix up nsec(3)s if present <a href="#abf2881787d48cdf3052dd1aee89520c0"></a><br/></td></tr> <tr><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#a1f41891c270cf01b4c73b706eb8f6d67">ldns_traverse_postorder</a> (<a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> *tree, void(*func)(<a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a> *, void *), void *arg)</td></tr> <tr><td class="mdescLeft"> </td><td class="mdescRight">Call function for all elements in the redblack tree, such that leaf elements are called before parent elements. <a href="#a1f41891c270cf01b4c73b706eb8f6d67"></a><br/></td></tr> <tr><td colspan="2"><h2><a name="var-members"></a> Variables</h2></td></tr> <tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#a9c65c464bbd4a3b574515a2547d3a268">ldns_rbtree_null_node</a></td></tr> <tr><td class="mdescLeft"> </td><td class="mdescRight">the global empty node <a href="#a9c65c464bbd4a3b574515a2547d3a268"></a><br/></td></tr> </table> <hr/><a name="details" id="details"></a><h2>Detailed Description</h2> <div class="textblock"><p>Red black tree. </p> <p>Implementation taken from NSD 3.0.5, adjusted for use in unbound (memory allocation, logging and so on). </p> <p>Definition in file <a class="el" href="rbtree_8h_source.html">rbtree.h</a>.</p> </div><hr/><h2>Define Documentation</h2> <a class="anchor" id="ab30c305b53af0832956712d035d96631"></a><!-- doxytag: member="rbtree.h::LDNS_RBTREE_NULL" ref="ab30c305b53af0832956712d035d96631" args="" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname">#define LDNS_RBTREE_NULL   &<a class="el" href="rbtree_8h.html#a9c65c464bbd4a3b574515a2547d3a268">ldns_rbtree_null_node</a></td> </tr> </table> </div> <div class="memdoc"> <p>The nullpointer, points to empty node. </p> <p>Definition at line <a class="el" href="rbtree_8h_source.html#l00076">76</a> of file <a class="el" href="rbtree_8h_source.html">rbtree.h</a>.</p> </div> </div> <a class="anchor" id="aac9e2938a0a05c3817dede8d62070ce7"></a><!-- doxytag: member="rbtree.h::LDNS_RBTREE_FOR" ref="aac9e2938a0a05c3817dede8d62070ce7" args="(node, type, rbtree)" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname">#define LDNS_RBTREE_FOR</td> <td>(</td> <td class="paramtype"> </td> <td class="paramname">node, </td> </tr> <tr> <td class="paramkey"></td> <td></td> <td class="paramtype"> </td> <td class="paramname">type, </td> </tr> <tr> <td class="paramkey"></td> <td></td> <td class="paramtype"> </td> <td class="paramname">rbtree </td> </tr> <tr> <td></td> <td>)</td> <td></td><td></td> </tr> </table> </div> <div class="memdoc"> <b>Value:</b><div class="fragment"><pre class="fragment"><span class="keywordflow">for</span>(node=(type)<a class="code" href="rbtree_8c.html#a76946c6350e5d16e645c5c0bbecfe017" title="Returns first (smallest) node in the tree.">ldns_rbtree_first</a>(rbtree); \ (<a class="code" href="structldns__rbnode__t.html" title="The rbnode_t struct definition.">ldns_rbnode_t</a>*)node != <a class="code" href="rbtree_8h.html#ab30c305b53af0832956712d035d96631" title="The nullpointer, points to empty node.">LDNS_RBTREE_NULL</a>; \ node = (type)<a class="code" href="rbtree_8c.html#aabc52dfc43c1df5841be22543be1e5fe" title="Returns next larger node in the tree.">ldns_rbtree_next</a>((<a class="code" href="structldns__rbnode__t.html" title="The rbnode_t struct definition.">ldns_rbnode_t</a>*)node)) </pre></div> <p>Call with node=variable of struct* with rbnode_t as first element. </p> <p>with type is the type of a pointer to that struct. </p> <p>Definition at line <a class="el" href="rbtree_8h_source.html#l00207">207</a> of file <a class="el" href="rbtree_8h_source.html">rbtree.h</a>.</p> </div> </div> <hr/><h2>Typedef Documentation</h2> <a class="anchor" id="afe02fd4e8e5d36ff36fbe24832284505"></a><!-- doxytag: member="rbtree.h::ldns_rbnode_t" ref="afe02fd4e8e5d36ff36fbe24832284505" args="" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname">typedef struct <a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a> <a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a></td> </tr> </table> </div> <div class="memdoc"> <p>This structure must be the first member of the data structure in the rbtree. </p> <p>This allows easy casting between an rbnode_t and the user data (poor man's inheritance). Or you can use the data pointer member to get to your data item. </p> <p>Definition at line <a class="el" href="rbtree_8h_source.html#l00056">56</a> of file <a class="el" href="rbtree_8h_source.html">rbtree.h</a>.</p> </div> </div> <a class="anchor" id="ae362fd6665ea1d8409bb413610425482"></a><!-- doxytag: member="rbtree.h::ldns_rbtree_t" ref="ae362fd6665ea1d8409bb413610425482" args="" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname">typedef struct <a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> <a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a></td> </tr> </table> </div> <div class="memdoc"> <p>An entire red black tree. </p> <p>Definition at line <a class="el" href="rbtree_8h_source.html#l00081">81</a> of file <a class="el" href="rbtree_8h_source.html">rbtree.h</a>.</p> </div> </div> <hr/><h2>Function Documentation</h2> <a class="anchor" id="a1319e3ff5b8355d6e1e7b65554bc854d"></a><!-- doxytag: member="rbtree.h::ldns_rbtree_create" ref="a1319e3ff5b8355d6e1e7b65554bc854d" args="(int(*cmpf)(const void *, const void *))" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname"><a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a>* ldns_rbtree_create </td> <td>(</td> <td class="paramtype">int(*)(const void *, const void *) </td> <td class="paramname"><em>cmpf</em></td><td>)</td> <td></td> </tr> </table> </div> <div class="memdoc"> <p>Create new tree (malloced) with given key compare function. </p> <dl><dt><b>Parameters:</b></dt><dd> <table class="params"> <tr><td class="paramname">cmpf,:</td><td>compare function (like strcmp) takes pointers to two keys. </td></tr> </table> </dd> </dl> <dl class="return"><dt><b>Returns:</b></dt><dd>: new tree, empty. </dd></dl> <p>Definition at line <a class="el" href="rbtree_8c_source.html#l00079">79</a> of file <a class="el" href="rbtree_8c_source.html">rbtree.c</a>.</p> <p>References <a class="el" href="rbtree_8c_source.html#l00096">ldns_rbtree_init()</a>.</p> </div> </div> <a class="anchor" id="a3762aeeab2725b04a9e0dfaf817c062f"></a><!-- doxytag: member="rbtree.h::ldns_rbtree_free" ref="a3762aeeab2725b04a9e0dfaf817c062f" args="(ldns_rbtree_t *rbtree)" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname">void ldns_rbtree_free </td> <td>(</td> <td class="paramtype"><a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> * </td> <td class="paramname"><em>rbtree</em></td><td>)</td> <td></td> </tr> </table> </div> <div class="memdoc"> <p>Free the complete tree (but not its keys) </p> <dl><dt><b>Parameters:</b></dt><dd> <table class="params"> <tr><td class="paramname">rbtree</td><td>The tree to free </td></tr> </table> </dd> </dl> <p>Definition at line <a class="el" href="rbtree_8c_source.html#l00105">105</a> of file <a class="el" href="rbtree_8c_source.html">rbtree.c</a>.</p> </div> </div> <a class="anchor" id="abfc60e1266fe66bda7d3fd7305787401"></a><!-- doxytag: member="rbtree.h::ldns_rbtree_init" ref="abfc60e1266fe66bda7d3fd7305787401" args="(ldns_rbtree_t *rbtree, int(*cmpf)(const void *, const void *))" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname">void ldns_rbtree_init </td> <td>(</td> <td class="paramtype"><a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> * </td> <td class="paramname"><em>rbtree</em>, </td> </tr> <tr> <td class="paramkey"></td> <td></td> <td class="paramtype">int(*)(const void *, const void *) </td> <td class="paramname"><em>cmpf</em> </td> </tr> <tr> <td></td> <td>)</td> <td></td><td></td> </tr> </table> </div> <div class="memdoc"> <p>Init a new tree (malloced by caller) with given key compare function. </p> <dl><dt><b>Parameters:</b></dt><dd> <table class="params"> <tr><td class="paramname">rbtree,:</td><td>uninitialised memory for new tree, returned empty. </td></tr> <tr><td class="paramname">cmpf,:</td><td>compare function (like strcmp) takes pointers to two keys. </td></tr> </table> </dd> </dl> <p>Definition at line <a class="el" href="rbtree_8c_source.html#l00096">96</a> of file <a class="el" href="rbtree_8c_source.html">rbtree.c</a>.</p> <p>References <a class="el" href="rbtree_8h_source.html#l00094">ldns_rbtree_t::cmp</a>, <a class="el" href="rbtree_8h_source.html#l00088">ldns_rbtree_t::count</a>, <a class="el" href="rbtree_8h_source.html#l00076">LDNS_RBTREE_NULL</a>, and <a class="el" href="rbtree_8h_source.html#l00085">ldns_rbtree_t::root</a>.</p> </div> </div> <a class="anchor" id="af7453903aed843b18ec24de879faf98f"></a><!-- doxytag: member="rbtree.h::ldns_rbtree_insert" ref="af7453903aed843b18ec24de879faf98f" args="(ldns_rbtree_t *rbtree, ldns_rbnode_t *data)" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname"><a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a>* ldns_rbtree_insert </td> <td>(</td> <td class="paramtype"><a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> * </td> <td class="paramname"><em>rbtree</em>, </td> </tr> <tr> <td class="paramkey"></td> <td></td> <td class="paramtype"><a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a> * </td> <td class="paramname"><em>data</em> </td> </tr> <tr> <td></td> <td>)</td> <td></td><td></td> </tr> </table> </div> <div class="memdoc"> <p>Insert data into the tree. </p> <dl><dt><b>Parameters:</b></dt><dd> <table class="params"> <tr><td class="paramname">rbtree,:</td><td>tree to insert to. </td></tr> <tr><td class="paramname">data,:</td><td>element to insert. </td></tr> </table> </dd> </dl> <dl class="return"><dt><b>Returns:</b></dt><dd>: data ptr or NULL if key already present. </dd></dl> <p>Definition at line <a class="el" href="rbtree_8c_source.html#l00241">241</a> of file <a class="el" href="rbtree_8c_source.html">rbtree.c</a>.</p> <p>References <a class="el" href="rbtree_8h_source.html#l00094">ldns_rbtree_t::cmp</a>, <a class="el" href="rbtree_8h_source.html#l00072">ldns_rbnode_t::color</a>, <a class="el" href="rbtree_8h_source.html#l00088">ldns_rbtree_t::count</a>, <a class="el" href="rbtree_8h_source.html#l00068">ldns_rbnode_t::key</a>, <a class="el" href="rbtree_8h_source.html#l00076">LDNS_RBTREE_NULL</a>, <a class="el" href="rbtree_8h_source.html#l00064">ldns_rbnode_t::left</a>, <a class="el" href="rbtree_8h_source.html#l00062">ldns_rbnode_t::parent</a>, <a class="el" href="rbtree_8c_source.html#l00051">RED</a>, <a class="el" href="rbtree_8h_source.html#l00066">ldns_rbnode_t::right</a>, and <a class="el" href="rbtree_8h_source.html#l00085">ldns_rbtree_t::root</a>.</p> </div> </div> <a class="anchor" id="a7cfa1759127e6133df02b04731b05dc9"></a><!-- doxytag: member="rbtree.h::ldns_rbtree_insert_vref" ref="a7cfa1759127e6133df02b04731b05dc9" args="(ldns_rbnode_t *data, void *rbtree)" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname">void ldns_rbtree_insert_vref </td> <td>(</td> <td class="paramtype"><a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a> * </td> <td class="paramname"><em>data</em>, </td> </tr> <tr> <td class="paramkey"></td> <td></td> <td class="paramtype">void * </td> <td class="paramname"><em>rbtree</em> </td> </tr> <tr> <td></td> <td>)</td> <td></td><td></td> </tr> </table> </div> <div class="memdoc"> <p>Insert data into the tree (reversed arguments, for use as callback) </p> <dl><dt><b>Parameters:</b></dt><dd> <table class="params"> <tr><td class="paramdir">[in]</td><td class="paramname">data</td><td>element to insert </td></tr> <tr><td class="paramdir">[out]</td><td class="paramname">rbtree</td><td>tree to insert in to </td></tr> </table> </dd> </dl> <dl class="return"><dt><b>Returns:</b></dt><dd>data ptr or NULL if key is already present </dd></dl> <p>Definition at line <a class="el" href="rbtree_8c_source.html#l00228">228</a> of file <a class="el" href="rbtree_8c_source.html">rbtree.c</a>.</p> <p>References <a class="el" href="rbtree_8c_source.html#l00241">ldns_rbtree_insert()</a>.</p> </div> </div> <a class="anchor" id="ab6d2736cd058aaee5af1bf4d59265764"></a><!-- doxytag: member="rbtree.h::ldns_rbtree_delete" ref="ab6d2736cd058aaee5af1bf4d59265764" args="(ldns_rbtree_t *rbtree, const void *key)" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname"><a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a>* ldns_rbtree_delete </td> <td>(</td> <td class="paramtype"><a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> * </td> <td class="paramname"><em>rbtree</em>, </td> </tr> <tr> <td class="paramkey"></td> <td></td> <td class="paramtype">const void * </td> <td class="paramname"><em>key</em> </td> </tr> <tr> <td></td> <td>)</td> <td></td><td></td> </tr> </table> </div> <div class="memdoc"> <p>Delete element from tree. </p> <dl><dt><b>Parameters:</b></dt><dd> <table class="params"> <tr><td class="paramname">rbtree,:</td><td>tree to delete from. </td></tr> <tr><td class="paramname">key,:</td><td>key of item to delete. </td></tr> </table> </dd> </dl> <dl class="return"><dt><b>Returns:</b></dt><dd>: node that is now unlinked from the tree. User to delete it. returns 0 if node not present </dd></dl> <p>Definition at line <a class="el" href="rbtree_8c_source.html#l00335">335</a> of file <a class="el" href="rbtree_8c_source.html">rbtree.c</a>.</p> <p>References <a class="el" href="rbtree_8c_source.html#l00049">BLACK</a>, <a class="el" href="rbtree_8h_source.html#l00072">ldns_rbnode_t::color</a>, <a class="el" href="rbtree_8h_source.html#l00088">ldns_rbtree_t::count</a>, <a class="el" href="rbtree_8h_source.html#l00076">LDNS_RBTREE_NULL</a>, <a class="el" href="rbtree_8c_source.html#l00293">ldns_rbtree_search()</a>, <a class="el" href="rbtree_8h_source.html#l00064">ldns_rbnode_t::left</a>, <a class="el" href="rbtree_8h_source.html#l00062">ldns_rbnode_t::parent</a>, <a class="el" href="rbtree_8c_source.html#l00051">RED</a>, and <a class="el" href="rbtree_8h_source.html#l00066">ldns_rbnode_t::right</a>.</p> </div> </div> <a class="anchor" id="ab95e41509757f1f9652011ce18475d5a"></a><!-- doxytag: member="rbtree.h::ldns_rbtree_search" ref="ab95e41509757f1f9652011ce18475d5a" args="(ldns_rbtree_t *rbtree, const void *key)" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname"><a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a>* ldns_rbtree_search </td> <td>(</td> <td class="paramtype"><a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> * </td> <td class="paramname"><em>rbtree</em>, </td> </tr> <tr> <td class="paramkey"></td> <td></td> <td class="paramtype">const void * </td> <td class="paramname"><em>key</em> </td> </tr> <tr> <td></td> <td>)</td> <td></td><td></td> </tr> </table> </div> <div class="memdoc"> <p>Find key in tree. </p> <p>Returns NULL if not found. </p> <dl><dt><b>Parameters:</b></dt><dd> <table class="params"> <tr><td class="paramname">rbtree,:</td><td>tree to find in. </td></tr> <tr><td class="paramname">key,:</td><td>key that must match. </td></tr> </table> </dd> </dl> <dl class="return"><dt><b>Returns:</b></dt><dd>: node that fits or NULL. </dd></dl> <p>Definition at line <a class="el" href="rbtree_8c_source.html#l00293">293</a> of file <a class="el" href="rbtree_8c_source.html">rbtree.c</a>.</p> <p>References <a class="el" href="rbtree_8c_source.html#l00513">ldns_rbtree_find_less_equal()</a>.</p> </div> </div> <a class="anchor" id="aaf5f35e7648861e0d1006f5de1199b14"></a><!-- doxytag: member="rbtree.h::ldns_rbtree_find_less_equal" ref="aaf5f35e7648861e0d1006f5de1199b14" args="(ldns_rbtree_t *rbtree, const void *key, ldns_rbnode_t **result)" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname">int ldns_rbtree_find_less_equal </td> <td>(</td> <td class="paramtype"><a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> * </td> <td class="paramname"><em>rbtree</em>, </td> </tr> <tr> <td class="paramkey"></td> <td></td> <td class="paramtype">const void * </td> <td class="paramname"><em>key</em>, </td> </tr> <tr> <td class="paramkey"></td> <td></td> <td class="paramtype"><a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a> ** </td> <td class="paramname"><em>result</em> </td> </tr> <tr> <td></td> <td>)</td> <td></td><td></td> </tr> </table> </div> <div class="memdoc"> <p>Find, but match does not have to be exact. </p> <dl><dt><b>Parameters:</b></dt><dd> <table class="params"> <tr><td class="paramname">rbtree,:</td><td>tree to find in. </td></tr> <tr><td class="paramname">key,:</td><td>key to find position of. </td></tr> <tr><td class="paramname">result,:</td><td>set to the exact node if present, otherwise to element that precedes the position of key in the tree. NULL if no smaller element. </td></tr> </table> </dd> </dl> <dl class="return"><dt><b>Returns:</b></dt><dd>: true if exact match in result. Else result points to <= element, or NULL if key is smaller than the smallest key. </dd></dl> <p>Definition at line <a class="el" href="rbtree_8c_source.html#l00513">513</a> of file <a class="el" href="rbtree_8c_source.html">rbtree.c</a>.</p> <p>References <a class="el" href="rbtree_8h_source.html#l00094">ldns_rbtree_t::cmp</a>, <a class="el" href="rbtree_8h_source.html#l00068">ldns_rbnode_t::key</a>, <a class="el" href="rbtree_8h_source.html#l00076">LDNS_RBTREE_NULL</a>, <a class="el" href="rbtree_8h_source.html#l00064">ldns_rbnode_t::left</a>, <a class="el" href="rbtree_8h_source.html#l00066">ldns_rbnode_t::right</a>, and <a class="el" href="rbtree_8h_source.html#l00085">ldns_rbtree_t::root</a>.</p> </div> </div> <a class="anchor" id="a76946c6350e5d16e645c5c0bbecfe017"></a><!-- doxytag: member="rbtree.h::ldns_rbtree_first" ref="a76946c6350e5d16e645c5c0bbecfe017" args="(ldns_rbtree_t *rbtree)" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname"><a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a>* ldns_rbtree_first </td> <td>(</td> <td class="paramtype"><a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> * </td> <td class="paramname"><em>rbtree</em></td><td>)</td> <td></td> </tr> </table> </div> <div class="memdoc"> <p>Returns first (smallest) node in the tree. </p> <dl><dt><b>Parameters:</b></dt><dd> <table class="params"> <tr><td class="paramname">rbtree,:</td><td>tree </td></tr> </table> </dd> </dl> <dl class="return"><dt><b>Returns:</b></dt><dd>: smallest element or NULL if tree empty. </dd></dl> <p>Definition at line <a class="el" href="rbtree_8c_source.html#l00547">547</a> of file <a class="el" href="rbtree_8c_source.html">rbtree.c</a>.</p> <p>References <a class="el" href="rbtree_8h_source.html#l00076">LDNS_RBTREE_NULL</a>, <a class="el" href="rbtree_8h_source.html#l00064">ldns_rbnode_t::left</a>, and <a class="el" href="rbtree_8h_source.html#l00085">ldns_rbtree_t::root</a>.</p> </div> </div> <a class="anchor" id="a627e270f8f549b2077c807ab2dd7b54a"></a><!-- doxytag: member="rbtree.h::ldns_rbtree_last" ref="a627e270f8f549b2077c807ab2dd7b54a" args="(ldns_rbtree_t *rbtree)" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname"><a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a>* ldns_rbtree_last </td> <td>(</td> <td class="paramtype"><a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> * </td> <td class="paramname"><em>rbtree</em></td><td>)</td> <td></td> </tr> </table> </div> <div class="memdoc"> <p>Returns last (largest) node in the tree. </p> <dl><dt><b>Parameters:</b></dt><dd> <table class="params"> <tr><td class="paramname">rbtree,:</td><td>tree </td></tr> </table> </dd> </dl> <dl class="return"><dt><b>Returns:</b></dt><dd>: largest element or NULL if tree empty. </dd></dl> <p>Definition at line <a class="el" href="rbtree_8c_source.html#l00558">558</a> of file <a class="el" href="rbtree_8c_source.html">rbtree.c</a>.</p> <p>References <a class="el" href="rbtree_8h_source.html#l00076">LDNS_RBTREE_NULL</a>, <a class="el" href="rbtree_8h_source.html#l00066">ldns_rbnode_t::right</a>, and <a class="el" href="rbtree_8h_source.html#l00085">ldns_rbtree_t::root</a>.</p> </div> </div> <a class="anchor" id="a1700685fdaad3700634fa50a0a899a3e"></a><!-- doxytag: member="rbtree.h::ldns_rbtree_next" ref="a1700685fdaad3700634fa50a0a899a3e" args="(ldns_rbnode_t *rbtree)" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname"><a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a>* ldns_rbtree_next </td> <td>(</td> <td class="paramtype"><a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a> * </td> <td class="paramname"><em>rbtree</em></td><td>)</td> <td></td> </tr> </table> </div> <div class="memdoc"> <p>Returns next larger node in the tree. </p> <dl><dt><b>Parameters:</b></dt><dd> <table class="params"> <tr><td class="paramname">rbtree,:</td><td>tree </td></tr> </table> </dd> </dl> <dl class="return"><dt><b>Returns:</b></dt><dd>: next larger element or NULL if no larger in tree. </dd></dl> <p>Definition at line <a class="el" href="rbtree_8c_source.html#l00573">573</a> of file <a class="el" href="rbtree_8c_source.html">rbtree.c</a>.</p> <p>References <a class="el" href="rbtree_8h_source.html#l00076">LDNS_RBTREE_NULL</a>, <a class="el" href="rbtree_8h_source.html#l00064">ldns_rbnode_t::left</a>, <a class="el" href="rbtree_8h_source.html#l00062">ldns_rbnode_t::parent</a>, and <a class="el" href="rbtree_8h_source.html#l00066">ldns_rbnode_t::right</a>.</p> </div> </div> <a class="anchor" id="a50d8a3fcf5969a79866c887070f13f98"></a><!-- doxytag: member="rbtree.h::ldns_rbtree_previous" ref="a50d8a3fcf5969a79866c887070f13f98" args="(ldns_rbnode_t *rbtree)" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname"><a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a>* ldns_rbtree_previous </td> <td>(</td> <td class="paramtype"><a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a> * </td> <td class="paramname"><em>rbtree</em></td><td>)</td> <td></td> </tr> </table> </div> <div class="memdoc"> <p>Returns previous smaller node in the tree. </p> <dl><dt><b>Parameters:</b></dt><dd> <table class="params"> <tr><td class="paramname">rbtree,:</td><td>tree </td></tr> </table> </dd> </dl> <dl class="return"><dt><b>Returns:</b></dt><dd>: previous smaller element or NULL if no previous in tree. </dd></dl> <p>Definition at line <a class="el" href="rbtree_8c_source.html#l00594">594</a> of file <a class="el" href="rbtree_8c_source.html">rbtree.c</a>.</p> <p>References <a class="el" href="rbtree_8h_source.html#l00076">LDNS_RBTREE_NULL</a>, <a class="el" href="rbtree_8h_source.html#l00064">ldns_rbnode_t::left</a>, <a class="el" href="rbtree_8h_source.html#l00062">ldns_rbnode_t::parent</a>, and <a class="el" href="rbtree_8h_source.html#l00066">ldns_rbnode_t::right</a>.</p> </div> </div> <a class="anchor" id="a211164b6238ae3aa0c6ad567e8c78944"></a><!-- doxytag: member="rbtree.h::ldns_rbtree_split" ref="a211164b6238ae3aa0c6ad567e8c78944" args="(ldns_rbtree_t *tree, size_t elements)" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname"><a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a>* ldns_rbtree_split </td> <td>(</td> <td class="paramtype"><a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> * </td> <td class="paramname"><em>tree</em>, </td> </tr> <tr> <td class="paramkey"></td> <td></td> <td class="paramtype">size_t </td> <td class="paramname"><em>elements</em> </td> </tr> <tr> <td></td> <td>)</td> <td></td><td></td> </tr> </table> </div> <div class="memdoc"> <p>split off 'elements' number of elements from the start of the name tree and return a new tree containing those elements </p> <p>Definition at line <a class="el" href="rbtree_8c_source.html#l00619">619</a> of file <a class="el" href="rbtree_8c_source.html">rbtree.c</a>.</p> <p>References <a class="el" href="rbtree_8h_source.html#l00094">ldns_rbtree_t::cmp</a>, <a class="el" href="rbtree_8h_source.html#l00068">ldns_rbnode_t::key</a>, <a class="el" href="rbtree_8c_source.html#l00079">ldns_rbtree_create()</a>, <a class="el" href="rbtree_8c_source.html#l00335">ldns_rbtree_delete()</a>, <a class="el" href="rbtree_8c_source.html#l00547">ldns_rbtree_first()</a>, <a class="el" href="rbtree_8c_source.html#l00241">ldns_rbtree_insert()</a>, and <a class="el" href="rbtree_8h_source.html#l00076">LDNS_RBTREE_NULL</a>.</p> </div> </div> <a class="anchor" id="abf2881787d48cdf3052dd1aee89520c0"></a><!-- doxytag: member="rbtree.h::ldns_rbtree_join" ref="abf2881787d48cdf3052dd1aee89520c0" args="(ldns_rbtree_t *tree1, ldns_rbtree_t *tree2)" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname">void ldns_rbtree_join </td> <td>(</td> <td class="paramtype"><a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> * </td> <td class="paramname"><em>tree1</em>, </td> </tr> <tr> <td class="paramkey"></td> <td></td> <td class="paramtype"><a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> * </td> <td class="paramname"><em>tree2</em> </td> </tr> <tr> <td></td> <td>)</td> <td></td><td></td> </tr> </table> </div> <div class="memdoc"> <p>add all node from the second tree to the first (removing them from the second), and fix up nsec(3)s if present </p> <p>Definition at line <a class="el" href="rbtree_8c_source.html#l00645">645</a> of file <a class="el" href="rbtree_8c_source.html">rbtree.c</a>.</p> <p>References <a class="el" href="rbtree_8c_source.html#l00228">ldns_rbtree_insert_vref()</a>, and <a class="el" href="rbtree_8c_source.html#l00665">ldns_traverse_postorder()</a>.</p> </div> </div> <a class="anchor" id="a1f41891c270cf01b4c73b706eb8f6d67"></a><!-- doxytag: member="rbtree.h::ldns_traverse_postorder" ref="a1f41891c270cf01b4c73b706eb8f6d67" args="(ldns_rbtree_t *tree, void(*func)(ldns_rbnode_t *, void *), void *arg)" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname">void ldns_traverse_postorder </td> <td>(</td> <td class="paramtype"><a class="el" href="structldns__rbtree__t.html">ldns_rbtree_t</a> * </td> <td class="paramname"><em>tree</em>, </td> </tr> <tr> <td class="paramkey"></td> <td></td> <td class="paramtype">void(*)(<a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a> *, void *) </td> <td class="paramname"><em>func</em>, </td> </tr> <tr> <td class="paramkey"></td> <td></td> <td class="paramtype">void * </td> <td class="paramname"><em>arg</em> </td> </tr> <tr> <td></td> <td>)</td> <td></td><td></td> </tr> </table> </div> <div class="memdoc"> <p>Call function for all elements in the redblack tree, such that leaf elements are called before parent elements. </p> <p>So that all elements can be safely free()d. Note that your function must not remove the nodes from the tree. Since that may trigger rebalances of the rbtree. </p> <dl><dt><b>Parameters:</b></dt><dd> <table class="params"> <tr><td class="paramname">tree,:</td><td>the tree </td></tr> <tr><td class="paramname">func,:</td><td>function called with element and user arg. The function must not alter the rbtree. </td></tr> <tr><td class="paramname">arg,:</td><td>user argument. </td></tr> </table> </dd> </dl> <p>Definition at line <a class="el" href="rbtree_8c_source.html#l00665">665</a> of file <a class="el" href="rbtree_8c_source.html">rbtree.c</a>.</p> <p>References <a class="el" href="rbtree_8h_source.html#l00085">ldns_rbtree_t::root</a>.</p> </div> </div> <hr/><h2>Variable Documentation</h2> <a class="anchor" id="a9c65c464bbd4a3b574515a2547d3a268"></a><!-- doxytag: member="rbtree.h::ldns_rbtree_null_node" ref="a9c65c464bbd4a3b574515a2547d3a268" args="" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname"><a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a> <a class="el" href="rbtree_8h.html#a9c65c464bbd4a3b574515a2547d3a268">ldns_rbtree_null_node</a></td> </tr> </table> </div> <div class="memdoc"> <p>the global empty node </p> <p>Definition at line <a class="el" href="rbtree_8c_source.html#l00054">54</a> of file <a class="el" href="rbtree_8c_source.html">rbtree.c</a>.</p> </div> </div> </div> <hr class="footer"/><address class="footer"><small>Generated on Wed Jan 11 2012 for ldns by  <a href="http://www.doxygen.org/index.html"> <img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.7.4 </small></address> </body> </html>