<!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>
<div class="header">
<div class="summary">
<a href="#define-members">Defines</a> |
<a href="#func-members">Functions</a> |
<a href="#var-members">Variables</a> </div>
<div class="headertitle">
<div class="title">rbtree.c File Reference</div> </div>
</div>
<div class="contents">
<p>Implementation of a redblack tree.
<a href="#details">More...</a></p>
<p><a href="rbtree_8c_source.html">Go to the source code of this file.</a></p>
<table class="memberdecls">
<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_8c.html#a7b3b25cba33b07c303f3060fe41887f6">BLACK</a>   0</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Node colour black. <a href="#a7b3b25cba33b07c303f3060fe41887f6"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">#define </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8c.html#a8d23feea868a983c8c2b661e1e16972f">RED</a>   1</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Node colour red. <a href="#a8d23feea868a983c8c2b661e1e16972f"></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_8c.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_8c.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">void </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8c.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_8c.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_8c.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"><a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8c.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"><a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8c.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">int </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8c.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_8c.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_8c.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_8c.html#aabc52dfc43c1df5841be22543be1e5fe">ldns_rbtree_next</a> (<a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a> *node)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Returns next larger node in the tree. <a href="#aabc52dfc43c1df5841be22543be1e5fe"></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_8c.html#a689087edc98b6726de13cc0d9c41a400">ldns_rbtree_previous</a> (<a class="el" href="structldns__rbnode__t.html">ldns_rbnode_t</a> *node)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Returns previous smaller node in the tree. <a href="#a689087edc98b6726de13cc0d9c41a400"></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_8c.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 <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_8c.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_8c.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_8c.html#a9c65c464bbd4a3b574515a2547d3a268">ldns_rbtree_null_node</a></td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">the NULL node, global alloc <a href="#a9c65c464bbd4a3b574515a2547d3a268"></a><br/></td></tr>
</table>
<hr/><a name="details" id="details"></a><h2>Detailed Description</h2>
<div class="textblock"><p>Implementation of a redblack tree. </p>
<p>Definition in file <a class="el" href="rbtree_8c_source.html">rbtree.c</a>.</p>
</div><hr/><h2>Define Documentation</h2>
<a class="anchor" id="a7b3b25cba33b07c303f3060fe41887f6"></a><!-- doxytag: member="rbtree.c::BLACK" ref="a7b3b25cba33b07c303f3060fe41887f6" args="" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">#define BLACK   0</td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Node colour black. </p>
<p>Definition at line <a class="el" href="rbtree_8c_source.html#l00049">49</a> of file <a class="el" href="rbtree_8c_source.html">rbtree.c</a>.</p>
</div>
</div>
<a class="anchor" id="a8d23feea868a983c8c2b661e1e16972f"></a><!-- doxytag: member="rbtree.c::RED" ref="a8d23feea868a983c8c2b661e1e16972f" args="" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">#define RED   1</td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Node colour red. </p>
<p>Definition at line <a class="el" href="rbtree_8c_source.html#l00051">51</a> of file <a class="el" href="rbtree_8c_source.html">rbtree.c</a>.</p>
</div>
</div>
<hr/><h2>Function Documentation</h2>
<a class="anchor" id="a1319e3ff5b8355d6e1e7b65554bc854d"></a><!-- doxytag: member="rbtree.c::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="abfc60e1266fe66bda7d3fd7305787401"></a><!-- doxytag: member="rbtree.c::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="a3762aeeab2725b04a9e0dfaf817c062f"></a><!-- doxytag: member="rbtree.c::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="a7cfa1759127e6133df02b04731b05dc9"></a><!-- doxytag: member="rbtree.c::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="af7453903aed843b18ec24de879faf98f"></a><!-- doxytag: member="rbtree.c::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="ab95e41509757f1f9652011ce18475d5a"></a><!-- doxytag: member="rbtree.c::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="ab6d2736cd058aaee5af1bf4d59265764"></a><!-- doxytag: member="rbtree.c::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="aaf5f35e7648861e0d1006f5de1199b14"></a><!-- doxytag: member="rbtree.c::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.c::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.c::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="aabc52dfc43c1df5841be22543be1e5fe"></a><!-- doxytag: member="rbtree.c::ldns_rbtree_next" ref="aabc52dfc43c1df5841be22543be1e5fe" args="(ldns_rbnode_t *node)" -->
<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="a689087edc98b6726de13cc0d9c41a400"></a><!-- doxytag: member="rbtree.c::ldns_rbtree_previous" ref="a689087edc98b6726de13cc0d9c41a400" args="(ldns_rbnode_t *node)" -->
<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.c::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 </p>
<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.c::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.c::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.c::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">
<b>Initial value:</b><div class="fragment"><pre class="fragment"> {
&<a class="code" href="rbtree_8c.html#a9c65c464bbd4a3b574515a2547d3a268" title="the NULL node, global alloc">ldns_rbtree_null_node</a> ,
&<a class="code" href="rbtree_8c.html#a9c65c464bbd4a3b574515a2547d3a268" title="the NULL node, global alloc">ldns_rbtree_null_node</a> ,
&<a class="code" href="rbtree_8c.html#a9c65c464bbd4a3b574515a2547d3a268" title="the NULL node, global alloc">ldns_rbtree_null_node</a> ,
NULL,
NULL,
0
}
</pre></div>
<p>the NULL node, global alloc </p>
<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>
