<!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="headertitle">
<div class="title">rbtree.h</div> </div>
</div>
<div class="contents">
<a href="rbtree_8h.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">/*</span>
<a name="l00002"></a>00002 <span class="comment"> * rbtree.h -- generic red-black tree</span>
<a name="l00003"></a>00003 <span class="comment"> *</span>
<a name="l00004"></a>00004 <span class="comment"> * Copyright (c) 2001-2008, NLnet Labs. All rights reserved.</span>
<a name="l00005"></a>00005 <span class="comment"> *</span>
<a name="l00006"></a>00006 <span class="comment"> * This software is open source.</span>
<a name="l00007"></a>00007 <span class="comment"> *</span>
<a name="l00008"></a>00008 <span class="comment"> * Redistribution and use in source and binary forms, with or without</span>
<a name="l00009"></a>00009 <span class="comment"> * modification, are permitted provided that the following conditions</span>
<a name="l00010"></a>00010 <span class="comment"> * are met:</span>
<a name="l00011"></a>00011 <span class="comment"> *</span>
<a name="l00012"></a>00012 <span class="comment"> * Redistributions of source code must retain the above copyright notice,</span>
<a name="l00013"></a>00013 <span class="comment"> * this list of conditions and the following disclaimer.</span>
<a name="l00014"></a>00014 <span class="comment"> *</span>
<a name="l00015"></a>00015 <span class="comment"> * Redistributions in binary form must reproduce the above copyright notice,</span>
<a name="l00016"></a>00016 <span class="comment"> * this list of conditions and the following disclaimer in the documentation</span>
<a name="l00017"></a>00017 <span class="comment"> * and/or other materials provided with the distribution.</span>
<a name="l00018"></a>00018 <span class="comment"> *</span>
<a name="l00019"></a>00019 <span class="comment"> * Neither the name of the NLNET LABS nor the names of its contributors may</span>
<a name="l00020"></a>00020 <span class="comment"> * be used to endorse or promote products derived from this software without</span>
<a name="l00021"></a>00021 <span class="comment"> * specific prior written permission.</span>
<a name="l00022"></a>00022 <span class="comment"> *</span>
<a name="l00023"></a>00023 <span class="comment"> * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS</span>
<a name="l00024"></a>00024 <span class="comment"> * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED</span>
<a name="l00025"></a>00025 <span class="comment"> * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR</span>
<a name="l00026"></a>00026 <span class="comment"> * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE</span>
<a name="l00027"></a>00027 <span class="comment"> * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR</span>
<a name="l00028"></a>00028 <span class="comment"> * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF</span>
<a name="l00029"></a>00029 <span class="comment"> * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS</span>
<a name="l00030"></a>00030 <span class="comment"> * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN</span>
<a name="l00031"></a>00031 <span class="comment"> * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)</span>
<a name="l00032"></a>00032 <span class="comment"> * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE</span>
<a name="l00033"></a>00033 <span class="comment"> * POSSIBILITY OF SUCH DAMAGE.</span>
<a name="l00034"></a>00034 <span class="comment"> *</span>
<a name="l00035"></a>00035 <span class="comment"> */</span>
<a name="l00036"></a>00036
<a name="l00043"></a>00043 <span class="preprocessor">#ifndef LDNS_RBTREE_H_</span>
<a name="l00044"></a>00044 <span class="preprocessor"></span><span class="preprocessor">#define LDNS_RBTREE_H_</span>
<a name="l00045"></a>00045 <span class="preprocessor"></span>
<a name="l00046"></a>00046 <span class="preprocessor">#ifdef __cplusplus</span>
<a name="l00047"></a>00047 <span class="preprocessor"></span><span class="keyword">extern</span> <span class="stringliteral">"C"</span> {
<a name="l00048"></a>00048 <span class="preprocessor">#endif</span>
<a name="l00049"></a>00049 <span class="preprocessor"></span>
<a name="l00056"></a><a class="code" href="rbtree_8h.html#afe02fd4e8e5d36ff36fbe24832284505">00056</a> <span class="keyword">typedef</span> <span class="keyword">struct </span><a class="code" href="structldns__rbnode__t.html" title="The rbnode_t struct definition.">ldns_rbnode_t</a> <a class="code" href="structldns__rbnode__t.html" title="The rbnode_t struct definition.">ldns_rbnode_t</a>;
<a name="l00060"></a><a class="code" href="structldns__rbnode__t.html">00060</a> <span class="keyword">struct </span><a class="code" href="structldns__rbnode__t.html" title="The rbnode_t struct definition.">ldns_rbnode_t</a> {
<a name="l00062"></a><a class="code" href="structldns__rbnode__t.html#ad336f8689a228766cff8fadd306eff7b">00062</a> <a class="code" href="structldns__rbnode__t.html" title="The rbnode_t struct definition.">ldns_rbnode_t</a> *<a class="code" href="structldns__rbnode__t.html#ad336f8689a228766cff8fadd306eff7b" title="parent in rbtree, RBTREE_NULL for root">parent</a>;
<a name="l00064"></a><a class="code" href="structldns__rbnode__t.html#af31105c7c53f42b9af14c8bcdadf9a5f">00064</a> <a class="code" href="structldns__rbnode__t.html" title="The rbnode_t struct definition.">ldns_rbnode_t</a> *<a class="code" href="structldns__rbnode__t.html#af31105c7c53f42b9af14c8bcdadf9a5f" title="left node (smaller items)">left</a>;
<a name="l00066"></a><a class="code" href="structldns__rbnode__t.html#ac9f7ea4d4c64cb094b56f1c48fb16ba2">00066</a> <a class="code" href="structldns__rbnode__t.html" title="The rbnode_t struct definition.">ldns_rbnode_t</a> *<a class="code" href="structldns__rbnode__t.html#ac9f7ea4d4c64cb094b56f1c48fb16ba2" title="right node (larger items)">right</a>;
<a name="l00068"></a><a class="code" href="structldns__rbnode__t.html#ad6646f5af0664e6ddedbf78b9deed2dc">00068</a> <span class="keyword">const</span> <span class="keywordtype">void</span> *<a class="code" href="structldns__rbnode__t.html#ad6646f5af0664e6ddedbf78b9deed2dc" title="pointer to sorting key">key</a>;
<a name="l00070"></a><a class="code" href="structldns__rbnode__t.html#aa0988cf7f89971338f5aa79c9352a1df">00070</a> <span class="keyword">const</span> <span class="keywordtype">void</span> *<a class="code" href="structldns__rbnode__t.html#aa0988cf7f89971338f5aa79c9352a1df" title="pointer to data">data</a>;
<a name="l00072"></a><a class="code" href="structldns__rbnode__t.html#af9a5631a7bae634d6f983307c406624a">00072</a> uint8_t <a class="code" href="structldns__rbnode__t.html#af9a5631a7bae634d6f983307c406624a" title="colour of this node">color</a>;
<a name="l00073"></a>00073 };
<a name="l00074"></a>00074
<a name="l00076"></a><a class="code" href="rbtree_8h.html#ab30c305b53af0832956712d035d96631">00076</a> <span class="preprocessor">#define LDNS_RBTREE_NULL &ldns_rbtree_null_node</span>
<a name="l00077"></a>00077 <span class="preprocessor"></span>
<a name="l00078"></a>00078 <span class="keyword">extern</span> <a class="code" href="structldns__rbnode__t.html" title="The rbnode_t struct definition.">ldns_rbnode_t</a> <a class="code" href="rbtree_8c.html#a9c65c464bbd4a3b574515a2547d3a268" title="the NULL node, global alloc">ldns_rbtree_null_node</a>;
<a name="l00079"></a>00079
<a name="l00081"></a><a class="code" href="rbtree_8h.html#ae362fd6665ea1d8409bb413610425482">00081</a> <span class="keyword">typedef</span> <span class="keyword">struct </span><a class="code" href="structldns__rbtree__t.html" title="definition for tree struct">ldns_rbtree_t</a> <a class="code" href="structldns__rbtree__t.html" title="definition for tree struct">ldns_rbtree_t</a>;
<a name="l00083"></a><a class="code" href="structldns__rbtree__t.html">00083</a> <span class="keyword">struct </span><a class="code" href="structldns__rbtree__t.html" title="definition for tree struct">ldns_rbtree_t</a> {
<a name="l00085"></a><a class="code" href="structldns__rbtree__t.html#abfa0bbc0290bf80cfcb4b239a3e84046">00085</a> <a class="code" href="structldns__rbnode__t.html" title="The rbnode_t struct definition.">ldns_rbnode_t</a> *<a class="code" href="structldns__rbtree__t.html#abfa0bbc0290bf80cfcb4b239a3e84046" title="The root of the red-black tree.">root</a>;
<a name="l00086"></a>00086
<a name="l00088"></a><a class="code" href="structldns__rbtree__t.html#aab8a0fa563b0fe3cf66e0ecafd95e217">00088</a> <span class="keywordtype">size_t</span> <a class="code" href="structldns__rbtree__t.html#aab8a0fa563b0fe3cf66e0ecafd95e217" title="The number of the nodes in the tree.">count</a>;
<a name="l00089"></a>00089
<a name="l00094"></a><a class="code" href="structldns__rbtree__t.html#ab8821c5723a7ac7304bc8f3d225395be">00094</a> int (*<a class="code" href="structldns__rbtree__t.html#ab8821c5723a7ac7304bc8f3d225395be" title="Key compare function.">cmp</a>) (<span class="keyword">const</span> <span class="keywordtype">void</span> *, <span class="keyword">const</span> <span class="keywordtype">void</span> *);
<a name="l00095"></a>00095 };
<a name="l00096"></a>00096
<a name="l00102"></a>00102 <a class="code" href="structldns__rbtree__t.html" title="definition for tree struct">ldns_rbtree_t</a> *<a class="code" href="rbtree_8c.html#a1319e3ff5b8355d6e1e7b65554bc854d" title="Create new tree (malloced) with given key compare function.">ldns_rbtree_create</a>(<span class="keywordtype">int</span> (*cmpf)(<span class="keyword">const</span> <span class="keywordtype">void</span> *, <span class="keyword">const</span> <span class="keywordtype">void</span> *));
<a name="l00103"></a>00103
<a name="l00108"></a>00108 <span class="keywordtype">void</span> <a class="code" href="rbtree_8c.html#a3762aeeab2725b04a9e0dfaf817c062f" title="Free the complete tree (but not its keys)">ldns_rbtree_free</a>(<a class="code" href="structldns__rbtree__t.html" title="definition for tree struct">ldns_rbtree_t</a> *rbtree);
<a name="l00109"></a>00109
<a name="l00115"></a>00115 <span class="keywordtype">void</span> <a class="code" href="rbtree_8c.html#abfc60e1266fe66bda7d3fd7305787401" title="Init a new tree (malloced by caller) with given key compare function.">ldns_rbtree_init</a>(<a class="code" href="structldns__rbtree__t.html" title="definition for tree struct">ldns_rbtree_t</a> *rbtree, <span class="keywordtype">int</span> (*cmpf)(<span class="keyword">const</span> <span class="keywordtype">void</span> *, <span class="keyword">const</span> <span class="keywordtype">void</span> *));
<a name="l00116"></a>00116
<a name="l00123"></a>00123 <a class="code" href="structldns__rbnode__t.html" title="The rbnode_t struct definition.">ldns_rbnode_t</a> *<a class="code" href="rbtree_8c.html#af7453903aed843b18ec24de879faf98f" title="Insert data into the tree.">ldns_rbtree_insert</a>(<a class="code" href="structldns__rbtree__t.html" title="definition for tree struct">ldns_rbtree_t</a> *rbtree, <a class="code" href="structldns__rbnode__t.html" title="The rbnode_t struct definition.">ldns_rbnode_t</a> *data);
<a name="l00124"></a>00124
<a name="l00131"></a>00131 <span class="keywordtype">void</span> <a class="code" href="rbtree_8c.html#a7cfa1759127e6133df02b04731b05dc9" title="Insert data into the tree (reversed arguments, for use as callback)">ldns_rbtree_insert_vref</a>(<a class="code" href="structldns__rbnode__t.html" title="The rbnode_t struct definition.">ldns_rbnode_t</a> *data, <span class="keywordtype">void</span> *rbtree);
<a name="l00132"></a>00132
<a name="l00140"></a>00140 <a class="code" href="structldns__rbnode__t.html" title="The rbnode_t struct definition.">ldns_rbnode_t</a> *<a class="code" href="rbtree_8c.html#ab6d2736cd058aaee5af1bf4d59265764" title="Delete element from tree.">ldns_rbtree_delete</a>(<a class="code" href="structldns__rbtree__t.html" title="definition for tree struct">ldns_rbtree_t</a> *rbtree, <span class="keyword">const</span> <span class="keywordtype">void</span> *key);
<a name="l00141"></a>00141
<a name="l00148"></a>00148 <a class="code" href="structldns__rbnode__t.html" title="The rbnode_t struct definition.">ldns_rbnode_t</a> *<a class="code" href="rbtree_8c.html#ab95e41509757f1f9652011ce18475d5a" title="Find key in tree.">ldns_rbtree_search</a>(<a class="code" href="structldns__rbtree__t.html" title="definition for tree struct">ldns_rbtree_t</a> *rbtree, <span class="keyword">const</span> <span class="keywordtype">void</span> *key);
<a name="l00149"></a>00149
<a name="l00159"></a>00159 <span class="keywordtype">int</span> <a class="code" href="rbtree_8c.html#aaf5f35e7648861e0d1006f5de1199b14" title="Find, but match does not have to be exact.">ldns_rbtree_find_less_equal</a>(<a class="code" href="structldns__rbtree__t.html" title="definition for tree struct">ldns_rbtree_t</a> *rbtree, <span class="keyword">const</span> <span class="keywordtype">void</span> *key,
<a name="l00160"></a>00160 <a class="code" href="structldns__rbnode__t.html" title="The rbnode_t struct definition.">ldns_rbnode_t</a> **result);
<a name="l00161"></a>00161
<a name="l00167"></a>00167 <a class="code" href="structldns__rbnode__t.html" title="The rbnode_t struct definition.">ldns_rbnode_t</a> *<a class="code" href="rbtree_8c.html#a76946c6350e5d16e645c5c0bbecfe017" title="Returns first (smallest) node in the tree.">ldns_rbtree_first</a>(<a class="code" href="structldns__rbtree__t.html" title="definition for tree struct">ldns_rbtree_t</a> *rbtree);
<a name="l00168"></a>00168
<a name="l00174"></a>00174 <a class="code" href="structldns__rbnode__t.html" title="The rbnode_t struct definition.">ldns_rbnode_t</a> *<a class="code" href="rbtree_8c.html#a627e270f8f549b2077c807ab2dd7b54a" title="Returns last (largest) node in the tree.">ldns_rbtree_last</a>(<a class="code" href="structldns__rbtree__t.html" title="definition for tree struct">ldns_rbtree_t</a> *rbtree);
<a name="l00175"></a>00175
<a name="l00181"></a>00181 <a class="code" href="structldns__rbnode__t.html" title="The rbnode_t struct definition.">ldns_rbnode_t</a> *<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> *rbtree);
<a name="l00182"></a>00182
<a name="l00188"></a>00188 <a class="code" href="structldns__rbnode__t.html" title="The rbnode_t struct definition.">ldns_rbnode_t</a> *<a class="code" href="rbtree_8c.html#a689087edc98b6726de13cc0d9c41a400" title="Returns previous smaller node in the tree.">ldns_rbtree_previous</a>(<a class="code" href="structldns__rbnode__t.html" title="The rbnode_t struct definition.">ldns_rbnode_t</a> *rbtree);
<a name="l00189"></a>00189
<a name="l00195"></a>00195 <a class="code" href="structldns__rbtree__t.html" title="definition for tree struct">ldns_rbtree_t</a> *<a class="code" href="rbtree_8c.html#a211164b6238ae3aa0c6ad567e8c78944" title="split off elements number of elements from the start of the name tree and return a new tree...">ldns_rbtree_split</a>(<a class="code" href="structldns__rbtree__t.html" title="definition for tree struct">ldns_rbtree_t</a> *tree, <span class="keywordtype">size_t</span> elements);
<a name="l00196"></a>00196
<a name="l00201"></a>00201 <span class="keywordtype">void</span> <a class="code" href="rbtree_8c.html#abf2881787d48cdf3052dd1aee89520c0" title="add all node from the second tree to the first (removing them from the second), and fix up nsec(3)s i...">ldns_rbtree_join</a>(<a class="code" href="structldns__rbtree__t.html" title="definition for tree struct">ldns_rbtree_t</a> *tree1, <a class="code" href="structldns__rbtree__t.html" title="definition for tree struct">ldns_rbtree_t</a> *tree2);
<a name="l00202"></a>00202
<a name="l00207"></a><a class="code" href="rbtree_8h.html#aac9e2938a0a05c3817dede8d62070ce7">00207</a> <span class="preprocessor">#define LDNS_RBTREE_FOR(node, type, rbtree) \</span>
<a name="l00208"></a>00208 <span class="preprocessor"> for(node=(type)ldns_rbtree_first(rbtree); \</span>
<a name="l00209"></a>00209 <span class="preprocessor"> (ldns_rbnode_t*)node != LDNS_RBTREE_NULL; \</span>
<a name="l00210"></a>00210 <span class="preprocessor"> node = (type)ldns_rbtree_next((ldns_rbnode_t*)node))</span>
<a name="l00211"></a>00211 <span class="preprocessor"></span>
<a name="l00223"></a>00223 <span class="keywordtype">void</span> <a class="code" href="rbtree_8c.html#a1f41891c270cf01b4c73b706eb8f6d67" title="Call function for all elements in the redblack tree, such that leaf elements are called before parent...">ldns_traverse_postorder</a>(<a class="code" href="structldns__rbtree__t.html" title="definition for tree struct">ldns_rbtree_t</a>* tree,
<a name="l00224"></a>00224 <span class="keywordtype">void</span> (*func)(<a class="code" href="structldns__rbnode__t.html" title="The rbnode_t struct definition.">ldns_rbnode_t</a>*, <span class="keywordtype">void</span>*), <span class="keywordtype">void</span>* arg);
<a name="l00225"></a>00225
<a name="l00226"></a>00226 <span class="preprocessor">#ifdef __cplusplus</span>
<a name="l00227"></a>00227 <span class="preprocessor"></span>}
<a name="l00228"></a>00228 <span class="preprocessor">#endif</span>
<a name="l00229"></a>00229 <span class="preprocessor"></span>
<a name="l00230"></a>00230 <span class="preprocessor">#endif </span><span class="comment">/* UTIL_RBTREE_H_ */</span>
</pre></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>
