<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head><meta http-equiv="Content-Type" content="text/html;charset=UTF-8">
<title>unbound: util/rbtree.h File Reference</title>
<link href="tabs.css" rel="stylesheet" type="text/css">
<link href="doxygen.css" rel="stylesheet" type="text/css">
</head><body>
<!-- Generated by Doxygen 1.5.9 -->
<div class="navigation" id="top">
<div class="tabs">
<ul>
<li><a href="index.html"><span>Main Page</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 class="tabs">
<ul>
<li><a href="files.html"><span>File List</span></a></li>
<li><a href="globals.html"><span>Globals</span></a></li>
</ul>
</div>
<div class="navpath"><a class="el" href="dir_4b581c88b01efb1cf178857b56f0f2fb.html">util</a>
</div>
</div>
<div class="contents">
<h1>rbtree.h File Reference</h1>Red black tree.
<a href="#_details">More...</a>
<p>
<table border="0" cellpadding="0" cellspacing="0">
<tr><td></td></tr>
<tr><td colspan="2"><br><h2>Data Structures</h2></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">struct </td><td class="memItemRight" valign="bottom"><a class="el" href="structrbnode__t.html">rbnode_t</a></td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">The <a class="el" href="structrbnode__t.html" title="The rbnode_t struct definition.">rbnode_t</a> struct definition. <a href="structrbnode__t.html#_details">More...</a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">struct </td><td class="memItemRight" valign="bottom"><a class="el" href="structrbtree__t.html">rbtree_t</a></td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">definition for tree struct <a href="structrbtree__t.html#_details">More...</a><br></td></tr>
<tr><td colspan="2"><br><h2>Defines</h2></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="08604873b3deea426c615400bda39a22"></a><!-- doxytag: member="rbtree.h::RBTREE_NULL" ref="08604873b3deea426c615400bda39a22" args="" -->
#define </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#08604873b3deea426c615400bda39a22">RBTREE_NULL</a> &<a class="el" href="rbtree_8h.html#0ae8d135599a329ddbe8cdc27980bd82">rbtree_null_node</a></td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">The nullpointer, points to empty node. <br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">#define </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#8e374b4514e5efd6219d3696ae6d482c">RBTREE_FOR</a>(node, type, rbtree)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Call with node=variable of struct* with <a class="el" href="structrbnode__t.html" title="The rbnode_t struct definition.">rbnode_t</a> as first element. <a href="#8e374b4514e5efd6219d3696ae6d482c"></a><br></td></tr>
<tr><td colspan="2"><br><h2>Typedefs</h2></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">typedef struct <a class="el" href="structrbnode__t.html">rbnode_t</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#950a6c8c277882fcdd21106d38713a9c">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="#950a6c8c277882fcdd21106d38713a9c"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="3c68893017f35e6849d710891cbe236c"></a><!-- doxytag: member="rbtree.h::rbtree_t" ref="3c68893017f35e6849d710891cbe236c" args="" -->
typedef struct <a class="el" href="structrbtree__t.html">rbtree_t</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#3c68893017f35e6849d710891cbe236c">rbtree_t</a></td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">An entire red black tree. <br></td></tr>
<tr><td colspan="2"><br><h2>Functions</h2></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="structrbtree__t.html">rbtree_t</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#bf9d2105e685ba42b87919a8096da1db">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="#bf9d2105e685ba42b87919a8096da1db"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#0a41a7694a94e5ca7e11dc849ca32d99">rbtree_init</a> (<a class="el" href="structrbtree__t.html">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="#0a41a7694a94e5ca7e11dc849ca32d99"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="structrbnode__t.html">rbnode_t</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#9f79e41785720776cff2804003c54048">rbtree_insert</a> (<a class="el" href="structrbtree__t.html">rbtree_t</a> *rbtree, <a class="el" href="structrbnode__t.html">rbnode_t</a> *data)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Insert data into the tree. <a href="#9f79e41785720776cff2804003c54048"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="structrbnode__t.html">rbnode_t</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#805e9d8f61273a06e439468e5d87881b">rbtree_delete</a> (<a class="el" href="structrbtree__t.html">rbtree_t</a> *rbtree, const void *key)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Delete element from tree. <a href="#805e9d8f61273a06e439468e5d87881b"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="structrbnode__t.html">rbnode_t</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#a22866ff6778c5b62ea1572ca2baf3cc">rbtree_search</a> (<a class="el" href="structrbtree__t.html">rbtree_t</a> *rbtree, const void *key)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Find key in tree. <a href="#a22866ff6778c5b62ea1572ca2baf3cc"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">int </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#10c4f10ea5b0d9654b0d11f8b6b3cfbd">rbtree_find_less_equal</a> (<a class="el" href="structrbtree__t.html">rbtree_t</a> *rbtree, const void *key, <a class="el" href="structrbnode__t.html">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="#10c4f10ea5b0d9654b0d11f8b6b3cfbd"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="structrbnode__t.html">rbnode_t</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#802889c59a94f03b88029fb6bbf6b26b">rbtree_first</a> (<a class="el" href="structrbtree__t.html">rbtree_t</a> *rbtree)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Returns first (smallest) node in the tree. <a href="#802889c59a94f03b88029fb6bbf6b26b"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="structrbnode__t.html">rbnode_t</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#6dc8aef7a605543d58c1a3e2d698713f">rbtree_last</a> (<a class="el" href="structrbtree__t.html">rbtree_t</a> *rbtree)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Returns last (largest) node in the tree. <a href="#6dc8aef7a605543d58c1a3e2d698713f"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="structrbnode__t.html">rbnode_t</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#62a3d87bc27686ddb44213b595866648">rbtree_next</a> (<a class="el" href="structrbnode__t.html">rbnode_t</a> *rbtree)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Returns next larger node in the tree. <a href="#62a3d87bc27686ddb44213b595866648"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="structrbnode__t.html">rbnode_t</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#3683bab8ebdbc21ddf8a5366d6b1fde2">rbtree_previous</a> (<a class="el" href="structrbnode__t.html">rbnode_t</a> *rbtree)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Returns previous smaller node in the tree. <a href="#3683bab8ebdbc21ddf8a5366d6b1fde2"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#a381538313cc1160562faf1c888c0ebf">traverse_postorder</a> (<a class="el" href="structrbtree__t.html">rbtree_t</a> *tree, void(*func)(<a class="el" href="structrbnode__t.html">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="#a381538313cc1160562faf1c888c0ebf"></a><br></td></tr>
<tr><td colspan="2"><br><h2>Variables</h2></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="0ae8d135599a329ddbe8cdc27980bd82"></a><!-- doxytag: member="rbtree.h::rbtree_null_node" ref="0ae8d135599a329ddbe8cdc27980bd82" args="" -->
<a class="el" href="structrbnode__t.html">rbnode_t</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="rbtree_8h.html#0ae8d135599a329ddbe8cdc27980bd82">rbtree_null_node</a></td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">the global empty node <br></td></tr>
</table>
<hr><h2>Detailed Description</h2>
Red black tree.
<p>
Implementation taken from NSD 3.0.5, adjusted for use in unbound (memory allocation, logging and so on). <hr><h2>Define Documentation</h2>
<a class="anchor" name="8e374b4514e5efd6219d3696ae6d482c"></a><!-- doxytag: member="rbtree.h::RBTREE_FOR" ref="8e374b4514e5efd6219d3696ae6d482c" args="(node, type, rbtree)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">#define RBTREE_FOR </td>
<td>(</td>
<td class="paramtype">node, <tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">type, <tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">rbtree </td>
<td class="paramname"> </td>
<td> ) </td>
<td></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
<b>Value:</b><div class="fragment"><pre class="fragment"><span class="keywordflow">for</span>(node=(type)<a class="code" href="rbtree_8c.html#802889c59a94f03b88029fb6bbf6b26b" title="Returns first (smallest) node in the tree.">rbtree_first</a>(rbtree); \
(<a class="code" href="structrbnode__t.html" title="The rbnode_t struct definition.">rbnode_t</a>*)node != <a class="code" href="rbtree_8h.html#08604873b3deea426c615400bda39a22" title="The nullpointer, points to empty node.">RBTREE_NULL</a>; \
node = (type)<a class="code" href="rbtree_8c.html#1865e26a84be590d623043f823a16e2c" title="Returns next larger node in the tree.">rbtree_next</a>((<a class="code" href="structrbnode__t.html" title="The rbnode_t struct definition.">rbnode_t</a>*)node))
</pre></div>Call with node=variable of struct* with <a class="el" href="structrbnode__t.html" title="The rbnode_t struct definition.">rbnode_t</a> as first element.
<p>
with type is the type of a pointer to that struct.
<p>Referenced by <a class="el" href="dnstree_8c_source.html#l00107">addr_tree_init_parents()</a>, <a class="el" href="unitneg_8c_source.html#l00469">check_neg_invariants()</a>, <a class="el" href="lock__verify_8c_source.html#l00367">check_order()</a>, <a class="el" href="unitneg_8c_source.html#l00414">checkzonetree()</a>, <a class="el" href="remote_8c_source.html#l01429">do_dump_requestlist()</a>, <a class="el" href="mesh_8c_source.html#l00998">find_in_subsub()</a>, <a class="el" href="iter__fwd_8c_source.html#l00124">fwd_init_parents()</a>, <a class="el" href="remote_8c_source.html#l01376">get_mesh_status()</a>, <a class="el" href="localzone_8c_source.html#l00706">init_parents()</a>, <a class="el" href="localzone_8c_source.html#l00929">local_zone_out()</a>, <a class="el" href="localzone_8c_source.html#l00942">local_zones_print()</a>, <a class="el" href="mesh_8c_source.html#l00528">mesh_detach_subs()</a>, <a class="el" href="mesh_8c_source.html#l00984">mesh_get_mem()</a>, <a class="el" href="mesh_8c_source.html#l00923">mesh_log_list()</a>, <a class="el" href="mesh_8c_source.html#l00491">mesh_state_delete()</a>, <a class="el" href="mesh_8c_source.html#l00754">mesh_walk_supers()</a>, <a class="el" href="dnstree_8c_source.html#l00133">name_tree_init_parents()</a>, <a class="el" href="outside__network_8c_source.html#l01664">outnet_get_mem()</a>, <a class="el" href="unitneg_8c_source.html#l00053">print_neg_cache()</a>, <a class="el" href="memstats_8c_source.html#l00215">printstats()</a>, <a class="el" href="val__sigcrypt_8c_source.html#l00968">rrset_canonical()</a>, <a class="el" href="lock__verify_8c_source.html#l00323">search_cycle()</a>, <a class="el" href="unitneg_8c_source.html#l00362">sum_subtree_inuse()</a>, <a class="el" href="unitneg_8c_source.html#l00377">sum_zone_subtree_inuse()</a>, <a class="el" href="unitneg_8c_source.html#l00307">sumtrees_all()</a>, and <a class="el" href="unitneg_8c_source.html#l00318">sumtrees_inuse()</a>.</p>
</div>
</div><p>
<hr><h2>Typedef Documentation</h2>
<a class="anchor" name="950a6c8c277882fcdd21106d38713a9c"></a><!-- doxytag: member="rbtree.h::rbnode_t" ref="950a6c8c277882fcdd21106d38713a9c" args="" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">typedef struct <a class="el" href="structrbnode__t.html">rbnode_t</a> <a class="el" href="structrbnode__t.html">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>
This allows easy casting between an <a class="el" href="structrbnode__t.html" title="The rbnode_t struct definition.">rbnode_t</a> and the user data (poor man's inheritance).
</div>
</div><p>
<hr><h2>Function Documentation</h2>
<a class="anchor" name="bf9d2105e685ba42b87919a8096da1db"></a><!-- doxytag: member="rbtree.h::rbtree_create" ref="bf9d2105e685ba42b87919a8096da1db" args="(int(*cmpf)(const void *, const void *))" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname"><a class="el" href="structrbtree__t.html">rbtree_t</a>* 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 compact><dt><b>Parameters:</b></dt><dd>
<table border="0" cellspacing="2" cellpadding="0">
<tr><td valign="top"></td><td valign="top"><em>cmpf,:</em> </td><td>compare function (like strcmp) takes pointers to two keys. </td></tr>
</table>
</dl>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>: new tree, empty. </dd></dl>
<p>References <a class="el" href="rbtree_8c_source.html#l00094">rbtree_init()</a>.</p>
<p>Referenced by <a class="el" href="val__anchor_8c_source.html#l00071">anchors_create()</a>, <a class="el" href="iter__fwd_8c_source.html#l00297">forwards_apply_cfg()</a>, <a class="el" href="lock__verify_8c_source.html#l00210">insert_lock()</a>, <a class="el" href="lock__verify_8c_source.html#l00389">main()</a>, <a class="el" href="outside__network_8c_source.html#l00468">outside_network_create()</a>, and <a class="el" href="lock__verify_8c_source.html#l00181">read_create()</a>.</p>
</div>
</div><p>
<a class="anchor" name="0a41a7694a94e5ca7e11dc849ca32d99"></a><!-- doxytag: member="rbtree.h::rbtree_init" ref="0a41a7694a94e5ca7e11dc849ca32d99" args="(rbtree_t *rbtree, int(*cmpf)(const void *, const void *))" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">void rbtree_init </td>
<td>(</td>
<td class="paramtype"><a class="el" href="structrbtree__t.html">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><td> </td>
</tr>
<tr>
<td></td>
<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 compact><dt><b>Parameters:</b></dt><dd>
<table border="0" cellspacing="2" cellpadding="0">
<tr><td valign="top"></td><td valign="top"><em>rbtree,:</em> </td><td>uninitialised memory for new tree, returned empty. </td></tr>
<tr><td valign="top"></td><td valign="top"><em>cmpf,:</em> </td><td>compare function (like strcmp) takes pointers to two keys. </td></tr>
</table>
</dl>
<p>References <a class="el" href="structrbtree__t.html#5dbde9e21cb2aadd97ea1fc2f9c3253a">rbtree_t::cmp</a>, <a class="el" href="rbtree_8h_source.html#l00081">rbtree_t::count</a>, <a class="el" href="rbtree_8h_source.html#l00069">RBTREE_NULL</a>, and <a class="el" href="rbtree_8h_source.html#l00078">rbtree_t::root</a>.</p>
<p>Referenced by <a class="el" href="dnstree_8c_source.html#l00079">addr_tree_init()</a>, <a class="el" href="localzone_8c_source.html#l00147">local_zone_create()</a>, <a class="el" href="localzone_8c_source.html#l00053">local_zones_create()</a>, <a class="el" href="mesh_8c_source.html#l00156">mesh_create()</a>, <a class="el" href="mesh_8c_source.html#l00215">mesh_delete_all()</a>, <a class="el" href="mesh_8c_source.html#l00528">mesh_detach_subs()</a>, <a class="el" href="mesh_8c_source.html#l00405">mesh_state_create()</a>, <a class="el" href="dnstree_8c_source.html#l00074">name_tree_init()</a>, <a class="el" href="val__neg_8c_source.html#l00440">neg_setup_zone_node()</a>, <a class="el" href="unitverify_8c_source.html#l00429">nsec3_hash_test()</a>, <a class="el" href="val__nsec3_8c_source.html#l01045">nsec3_prove_nameerror()</a>, <a class="el" href="val__nsec3_8c_source.html#l01180">nsec3_prove_nodata()</a>, <a class="el" href="val__nsec3_8c_source.html#l01261">nsec3_prove_nods()</a>, <a class="el" href="val__nsec3_8c_source.html#l01329">nsec3_prove_nxornodata()</a>, <a class="el" href="val__nsec3_8c_source.html#l01199">nsec3_prove_wildcard()</a>, <a class="el" href="rbtree_8c_source.html#l00077">rbtree_create()</a>, <a class="el" href="val__sigcrypt_8c_source.html#l00968">rrset_canonical()</a>, <a class="el" href="libunbound_8c_source.html#l00064">ub_ctx_create()</a>, and <a class="el" href="val__neg_8c_source.html#l00078">val_neg_create()</a>.</p>
</div>
</div><p>
<a class="anchor" name="9f79e41785720776cff2804003c54048"></a><!-- doxytag: member="rbtree.h::rbtree_insert" ref="9f79e41785720776cff2804003c54048" args="(rbtree_t *rbtree, rbnode_t *data)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname"><a class="el" href="structrbnode__t.html">rbnode_t</a>* rbtree_insert </td>
<td>(</td>
<td class="paramtype"><a class="el" href="structrbtree__t.html">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="structrbnode__t.html">rbnode_t</a> * </td>
<td class="paramname"> <em>data</em></td><td> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td><td></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Insert data into the tree.
<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
<table border="0" cellspacing="2" cellpadding="0">
<tr><td valign="top"></td><td valign="top"><em>rbtree,:</em> </td><td>tree to insert to. </td></tr>
<tr><td valign="top"></td><td valign="top"><em>data,:</em> </td><td>element to insert. </td></tr>
</table>
</dl>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>: data ptr or NULL if key already present. </dd></dl>
<p>References <a class="el" href="structrbtree__t.html#5dbde9e21cb2aadd97ea1fc2f9c3253a">rbtree_t::cmp</a>, <a class="el" href="rbtree_8h_source.html#l00065">rbnode_t::color</a>, <a class="el" href="rbtree_8h_source.html#l00081">rbtree_t::count</a>, <a class="el" href="fptr__wlist_8h_source.html#l00067">fptr_ok</a>, <a class="el" href="fptr__wlist_8c_source.html#l00164">fptr_whitelist_rbtree_cmp()</a>, <a class="el" href="rbtree_8h_source.html#l00063">rbnode_t::key</a>, <a class="el" href="rbtree_8h_source.html#l00059">rbnode_t::left</a>, <a class="el" href="rbtree_8h_source.html#l00057">rbnode_t::parent</a>, <a class="el" href="rbtree_8c_source.html#l00157">rbtree_insert_fixup()</a>, <a class="el" href="rbtree_8h_source.html#l00069">RBTREE_NULL</a>, <a class="el" href="rbtree_8c_source.html#l00050">RED</a>, <a class="el" href="rbtree_8h_source.html#l00061">rbnode_t::right</a>, and <a class="el" href="rbtree_8h_source.html#l00078">rbtree_t::root</a>.</p>
<p>Referenced by <a class="el" href="dnstree_8c_source.html#l00096">addr_tree_insert()</a>, <a class="el" href="val__anchor_8c_source.html#l00147">anchor_new_ta()</a>, <a class="el" href="val__sigcrypt_8c_source.html#l00800">canonical_sort()</a>, <a class="el" href="context_8c_source.html#l00232">context_deserialize_new_query()</a>, <a class="el" href="context_8c_source.html#l00127">context_new()</a>, <a class="el" href="iter__fwd_8c_source.html#l00093">forwards_insert_data()</a>, <a class="el" href="memstats_8c_source.html#l00100">get_codeline()</a>, <a class="el" href="lock__verify_8c_source.html#l00210">insert_lock()</a>, <a class="el" href="localzone_8c_source.html#l01186">local_zones_add_zone()</a>, <a class="el" href="localzone_8c_source.html#l00174">lz_enter_zone_dname()</a>, <a class="el" href="localzone_8c_source.html#l00405">lz_find_create_node()</a>, <a class="el" href="mesh_8c_source.html#l00548">mesh_attach_sub()</a>, <a class="el" href="mesh_8c_source.html#l00344">mesh_new_callback()</a>, <a class="el" href="mesh_8c_source.html#l00268">mesh_new_client()</a>, <a class="el" href="mesh_8c_source.html#l00583">mesh_state_attachment()</a>, <a class="el" href="mesh_8c_source.html#l00754">mesh_walk_supers()</a>, <a class="el" href="dnstree_8c_source.html#l00084">name_tree_insert()</a>, <a class="el" href="val__neg_8c_source.html#l00521">neg_create_zone()</a>, <a class="el" href="val__neg_8c_source.html#l00739">neg_insert_data()</a>, <a class="el" href="val__nsec3_8c_source.html#l00634">nsec3_hash_name()</a>, <a class="el" href="lock__verify_8c_source.html#l00181">read_create()</a>, <a class="el" href="lock__verify_8c_source.html#l00223">read_lock()</a>, <a class="el" href="outside__network_8c_source.html#l00769">select_id()</a>, and <a class="el" href="outside__network_8c_source.html#l01072">serviced_create()</a>.</p>
</div>
</div><p>
<a class="anchor" name="805e9d8f61273a06e439468e5d87881b"></a><!-- doxytag: member="rbtree.h::rbtree_delete" ref="805e9d8f61273a06e439468e5d87881b" args="(rbtree_t *rbtree, const void *key)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname"><a class="el" href="structrbnode__t.html">rbnode_t</a>* rbtree_delete </td>
<td>(</td>
<td class="paramtype"><a class="el" href="structrbtree__t.html">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><td> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td><td></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Delete element from tree.
<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
<table border="0" cellspacing="2" cellpadding="0">
<tr><td valign="top"></td><td valign="top"><em>rbtree,:</em> </td><td>tree to delete from. </td></tr>
<tr><td valign="top"></td><td valign="top"><em>key,:</em> </td><td>key of item to delete. </td></tr>
</table>
</dl>
<dl class="return" compact><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>References <a class="el" href="rbtree_8c_source.html#l00048">BLACK</a>, <a class="el" href="rbtree_8c_source.html#l00318">change_child_ptr()</a>, <a class="el" href="rbtree_8c_source.html#l00304">change_parent_ptr()</a>, <a class="el" href="rbtree_8h_source.html#l00065">rbnode_t::color</a>, <a class="el" href="rbtree_8h_source.html#l00081">rbtree_t::count</a>, <a class="el" href="rbtree_8h_source.html#l00059">rbnode_t::left</a>, <a class="el" href="log_8h_source.html#l00185">log_assert</a>, <a class="el" href="rbtree_8h_source.html#l00057">rbnode_t::parent</a>, <a class="el" href="rbtree_8c_source.html#l00403">rbtree_delete_fixup()</a>, <a class="el" href="rbtree_8h_source.html#l00069">RBTREE_NULL</a>, <a class="el" href="rbtree_8c_source.html#l00280">rbtree_search()</a>, <a class="el" href="rbtree_8c_source.html#l00050">RED</a>, <a class="el" href="rbtree_8h_source.html#l00061">rbnode_t::right</a>, <a class="el" href="rbtree_8c_source.html#l00292">swap_int8()</a>, and <a class="el" href="rbtree_8c_source.html#l00298">swap_np()</a>.</p>
<p>Referenced by <a class="el" href="libworker_8c_source.html#l00540">add_bg_result()</a>, <a class="el" href="val__anchor_8c_source.html#l00886">anchors_assemble_rrsets()</a>, <a class="el" href="localzone_8c_source.html#l01277">del_empty_term()</a>, <a class="el" href="iter__fwd_8c_source.html#l00374">forwards_delete_zone()</a>, <a class="el" href="libworker_8c_source.html#l00577">libworker_bg_done_cb()</a>, <a class="el" href="localzone_8c_source.html#l01214">local_zones_del_zone()</a>, <a class="el" href="mesh_8c_source.html#l00528">mesh_detach_subs()</a>, <a class="el" href="mesh_8c_source.html#l00886">mesh_run()</a>, <a class="el" href="mesh_8c_source.html#l00491">mesh_state_delete()</a>, <a class="el" href="val__neg_8c_source.html#l00218">neg_delete_data()</a>, <a class="el" href="val__neg_8c_source.html#l00189">neg_delete_zone()</a>, <a class="el" href="outside__network_8c_source.html#l01556">outnet_serviced_query()</a>, <a class="el" href="outside__network_8c_source.html#l01615">outnet_serviced_query_stop()</a>, <a class="el" href="outside__network_8c_source.html#l00303">outnet_udp_cb()</a>, <a class="el" href="outside__network_8c_source.html#l00709">pending_delete()</a>, <a class="el" href="libunbound_8c_source.html#l00366">process_answer_detail()</a>, <a class="el" href="outside__network_8c_source.html#l01308">serviced_callbacks()</a>, <a class="el" href="libunbound_8c_source.html#l00635">ub_cancel()</a>, <a class="el" href="libunbound_8c_source.html#l00528">ub_resolve()</a>, and <a class="el" href="libunbound_8c_source.html#l00572">ub_resolve_async()</a>.</p>
</div>
</div><p>
<a class="anchor" name="a22866ff6778c5b62ea1572ca2baf3cc"></a><!-- doxytag: member="rbtree.h::rbtree_search" ref="a22866ff6778c5b62ea1572ca2baf3cc" args="(rbtree_t *rbtree, const void *key)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname"><a class="el" href="structrbnode__t.html">rbnode_t</a>* rbtree_search </td>
<td>(</td>
<td class="paramtype"><a class="el" href="structrbtree__t.html">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><td> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td><td></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Find key in tree.
<p>
Returns NULL if not found. <dl compact><dt><b>Parameters:</b></dt><dd>
<table border="0" cellspacing="2" cellpadding="0">
<tr><td valign="top"></td><td valign="top"><em>rbtree,:</em> </td><td>tree to find in. </td></tr>
<tr><td valign="top"></td><td valign="top"><em>key,:</em> </td><td>key that must match. </td></tr>
</table>
</dl>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>: node that fits or NULL. </dd></dl>
<p>References <a class="el" href="rbtree_8c_source.html#l00507">rbtree_find_less_equal()</a>.</p>
<p>Referenced by <a class="el" href="val__anchor_8c_source.html#l00129">anchor_find()</a>, <a class="el" href="context_8c_source.html#l00309">context_deserialize_answer()</a>, <a class="el" href="context_8c_source.html#l00348">context_deserialize_cancel()</a>, <a class="el" href="context_8c_source.html#l00265">context_lookup_new_query()</a>, <a class="el" href="context_8c_source.html#l00113">find_id()</a>, <a class="el" href="iter__fwd_8c_source.html#l00374">forwards_delete_zone()</a>, <a class="el" href="memstats_8c_source.html#l00100">get_codeline()</a>, <a class="el" href="localzone_8c_source.html#l01016">local_data_answer()</a>, <a class="el" href="localzone_8c_source.html#l00914">local_zones_find()</a>, <a class="el" href="outside__network_8c_source.html#l01056">lookup_serviced()</a>, <a class="el" href="localzone_8c_source.html#l00541">lz_exists()</a>, <a class="el" href="localzone_8c_source.html#l00393">lz_find_node()</a>, <a class="el" href="mesh_8c_source.html#l00769">mesh_area_find()</a>, <a class="el" href="dnstree_8c_source.html#l00159">name_tree_find()</a>, <a class="el" href="iter__fwd_8c_source.html#l00248">need_hole_insert()</a>, <a class="el" href="val__neg_8c_source.html#l00295">neg_find_data()</a>, <a class="el" href="val__neg_8c_source.html#l00271">neg_find_zone()</a>, <a class="el" href="val__nsec3_8c_source.html#l00634">nsec3_hash_name()</a>, <a class="el" href="outside__network_8c_source.html#l00303">outnet_udp_cb()</a>, <a class="el" href="rbtree_8c_source.html#l00326">rbtree_delete()</a>, <a class="el" href="lock__verify_8c_source.html#l00181">read_create()</a>, <a class="el" href="lock__verify_8c_source.html#l00223">read_lock()</a>, and <a class="el" href="libunbound_8c_source.html#l00635">ub_cancel()</a>.</p>
</div>
</div><p>
<a class="anchor" name="10c4f10ea5b0d9654b0d11f8b6b3cfbd"></a><!-- doxytag: member="rbtree.h::rbtree_find_less_equal" ref="10c4f10ea5b0d9654b0d11f8b6b3cfbd" args="(rbtree_t *rbtree, const void *key, rbnode_t **result)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">int rbtree_find_less_equal </td>
<td>(</td>
<td class="paramtype"><a class="el" href="structrbtree__t.html">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="structrbnode__t.html">rbnode_t</a> ** </td>
<td class="paramname"> <em>result</em></td><td> </td>
</tr>
<tr>
<td></td>
<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 compact><dt><b>Parameters:</b></dt><dd>
<table border="0" cellspacing="2" cellpadding="0">
<tr><td valign="top"></td><td valign="top"><em>rbtree,:</em> </td><td>tree to find in. </td></tr>
<tr><td valign="top"></td><td valign="top"><em>key,:</em> </td><td>key to find position of. </td></tr>
<tr><td valign="top"></td><td valign="top"><em>result,:</em> </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>
</dl>
<dl class="return" compact><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>References <a class="el" href="structrbtree__t.html#5dbde9e21cb2aadd97ea1fc2f9c3253a">rbtree_t::cmp</a>, <a class="el" href="fptr__wlist_8h_source.html#l00067">fptr_ok</a>, <a class="el" href="fptr__wlist_8c_source.html#l00164">fptr_whitelist_rbtree_cmp()</a>, <a class="el" href="rbtree_8h_source.html#l00063">rbnode_t::key</a>, <a class="el" href="rbtree_8h_source.html#l00059">rbnode_t::left</a>, <a class="el" href="log_8h_source.html#l00185">log_assert</a>, <a class="el" href="rbtree_8h_source.html#l00069">RBTREE_NULL</a>, <a class="el" href="rbtree_8h_source.html#l00061">rbnode_t::right</a>, and <a class="el" href="rbtree_8h_source.html#l00078">rbtree_t::root</a>.</p>
<p>Referenced by <a class="el" href="dnstree_8c_source.html#l00203">addr_tree_lookup()</a>, <a class="el" href="val__anchor_8c_source.html#l01008">anchors_lookup()</a>, <a class="el" href="iter__fwd_8c_source.html#l00315">forwards_lookup()</a>, <a class="el" href="localzone_8c_source.html#l00881">local_zones_lookup()</a>, <a class="el" href="dnstree_8c_source.html#l00171">name_tree_lookup()</a>, <a class="el" href="val__neg_8c_source.html#l00893">neg_closest_data()</a>, <a class="el" href="val__neg_8c_source.html#l00401">neg_closest_data_parent()</a>, <a class="el" href="val__neg_8c_source.html#l00361">neg_closest_zone_parent()</a>, and <a class="el" href="rbtree_8c_source.html#l00280">rbtree_search()</a>.</p>
</div>
</div><p>
<a class="anchor" name="802889c59a94f03b88029fb6bbf6b26b"></a><!-- doxytag: member="rbtree.h::rbtree_first" ref="802889c59a94f03b88029fb6bbf6b26b" args="(rbtree_t *rbtree)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname"><a class="el" href="structrbnode__t.html">rbnode_t</a>* rbtree_first </td>
<td>(</td>
<td class="paramtype"><a class="el" href="structrbtree__t.html">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 compact><dt><b>Parameters:</b></dt><dd>
<table border="0" cellspacing="2" cellpadding="0">
<tr><td valign="top"></td><td valign="top"><em>rbtree,:</em> </td><td>tree </td></tr>
</table>
</dl>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>: smallest element or NULL if tree empty. </dd></dl>
<p>References <a class="el" href="rbtree_8h_source.html#l00059">rbnode_t::left</a>, <a class="el" href="rbtree_8h_source.html#l00069">RBTREE_NULL</a>, and <a class="el" href="rbtree_8h_source.html#l00078">rbtree_t::root</a>.</p>
<p>Referenced by <a class="el" href="val__anchor_8c_source.html#l00886">anchors_assemble_rrsets()</a>, <a class="el" href="unitneg_8c_source.html#l00240">remove_item()</a>, and <a class="el" href="unitneg_8c_source.html#l00318">sumtrees_inuse()</a>.</p>
</div>
</div><p>
<a class="anchor" name="6dc8aef7a605543d58c1a3e2d698713f"></a><!-- doxytag: member="rbtree.h::rbtree_last" ref="6dc8aef7a605543d58c1a3e2d698713f" args="(rbtree_t *rbtree)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname"><a class="el" href="structrbnode__t.html">rbnode_t</a>* rbtree_last </td>
<td>(</td>
<td class="paramtype"><a class="el" href="structrbtree__t.html">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 compact><dt><b>Parameters:</b></dt><dd>
<table border="0" cellspacing="2" cellpadding="0">
<tr><td valign="top"></td><td valign="top"><em>rbtree,:</em> </td><td>tree </td></tr>
</table>
</dl>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>: largest element or NULL if tree empty. </dd></dl>
<p>References <a class="el" href="rbtree_8h_source.html#l00069">RBTREE_NULL</a>, <a class="el" href="rbtree_8h_source.html#l00061">rbnode_t::right</a>, and <a class="el" href="rbtree_8h_source.html#l00078">rbtree_t::root</a>.</p>
<p>Referenced by <a class="el" href="val__neg_8c_source.html#l01199">neg_nsec3_getnc()</a>.</p>
</div>
</div><p>
<a class="anchor" name="62a3d87bc27686ddb44213b595866648"></a><!-- doxytag: member="rbtree.h::rbtree_next" ref="62a3d87bc27686ddb44213b595866648" args="(rbnode_t *rbtree)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname"><a class="el" href="structrbnode__t.html">rbnode_t</a>* rbtree_next </td>
<td>(</td>
<td class="paramtype"><a class="el" href="structrbnode__t.html">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 compact><dt><b>Parameters:</b></dt><dd>
<table border="0" cellspacing="2" cellpadding="0">
<tr><td valign="top"></td><td valign="top"><em>rbtree,:</em> </td><td>tree </td></tr>
</table>
</dl>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>: next larger element or NULL if no larger in tree. </dd></dl>
<p>References <a class="el" href="rbtree_8h_source.html#l00059">rbnode_t::left</a>, <a class="el" href="rbtree_8h_source.html#l00057">rbnode_t::parent</a>, <a class="el" href="rbtree_8h_source.html#l00069">RBTREE_NULL</a>, and <a class="el" href="rbtree_8h_source.html#l00061">rbnode_t::right</a>.</p>
<p>Referenced by <a class="el" href="val__anchor_8c_source.html#l00886">anchors_assemble_rrsets()</a>, <a class="el" href="localzone_8c_source.html#l01262">is_terminal()</a>, <a class="el" href="unitneg_8c_source.html#l00240">remove_item()</a>, <a class="el" href="localzone_8c_source.html#l01162">set_kiddo_parents()</a>, and <a class="el" href="val__neg_8c_source.html#l00664">wipeout()</a>.</p>
</div>
</div><p>
<a class="anchor" name="3683bab8ebdbc21ddf8a5366d6b1fde2"></a><!-- doxytag: member="rbtree.h::rbtree_previous" ref="3683bab8ebdbc21ddf8a5366d6b1fde2" args="(rbnode_t *rbtree)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname"><a class="el" href="structrbnode__t.html">rbnode_t</a>* rbtree_previous </td>
<td>(</td>
<td class="paramtype"><a class="el" href="structrbnode__t.html">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 compact><dt><b>Parameters:</b></dt><dd>
<table border="0" cellspacing="2" cellpadding="0">
<tr><td valign="top"></td><td valign="top"><em>rbtree,:</em> </td><td>tree </td></tr>
</table>
</dl>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>: previous smaller element or NULL if no previous in tree. </dd></dl>
<p>References <a class="el" href="rbtree_8h_source.html#l00059">rbnode_t::left</a>, <a class="el" href="rbtree_8h_source.html#l00057">rbnode_t::parent</a>, <a class="el" href="rbtree_8h_source.html#l00069">RBTREE_NULL</a>, and <a class="el" href="rbtree_8h_source.html#l00061">rbnode_t::right</a>.</p>
</div>
</div><p>
<a class="anchor" name="a381538313cc1160562faf1c888c0ebf"></a><!-- doxytag: member="rbtree.h::traverse_postorder" ref="a381538313cc1160562faf1c888c0ebf" args="(rbtree_t *tree, void(*func)(rbnode_t *, void *), void *arg)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">void traverse_postorder </td>
<td>(</td>
<td class="paramtype"><a class="el" href="structrbtree__t.html">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="structrbnode__t.html">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><td> </td>
</tr>
<tr>
<td></td>
<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>
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. <dl compact><dt><b>Parameters:</b></dt><dd>
<table border="0" cellspacing="2" cellpadding="0">
<tr><td valign="top"></td><td valign="top"><em>tree,:</em> </td><td>the tree </td></tr>
<tr><td valign="top"></td><td valign="top"><em>func,:</em> </td><td>function called with element and user arg. The function must not alter the rbtree. </td></tr>
<tr><td valign="top"></td><td valign="top"><em>arg,:</em> </td><td>user argument. </td></tr>
</table>
</dl>
<p>References <a class="el" href="rbtree_8h_source.html#l00078">rbtree_t::root</a>, and <a class="el" href="rbtree_8c_source.html#l00605">traverse_post()</a>.</p>
<p>Referenced by <a class="el" href="localzone_8c_source.html#l00075">local_zones_delete()</a>, <a class="el" href="val__neg_8c_source.html#l00125">neg_cache_delete()</a>, <a class="el" href="val__neg_8c_source.html#l00115">neg_clear_zones()</a>, <a class="el" href="outside__network_8c_source.html#l00624">outside_network_delete()</a>, and <a class="el" href="libunbound_8c_source.html#l00153">ub_ctx_delete()</a>.</p>
</div>
</div><p>
</div>
<hr size="1"><address style="text-align: right;"><small>Generated on Tue Oct 13 06:46:32 2009 for unbound by
<a href="http://www.doxygen.org/index.html">
<img src="doxygen.png" alt="doxygen" align="middle" border="0"></a> 1.5.9 </small></address>
</body>
</html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
550bbe86d83a7870fdddc73c68e5d2b2
>
files
>
234
