File: a00109.html

package info (click to toggle)
bmagic 3.4.0-4
links: PTS
area: main
in suites: etch, etch-m68k
size: 4,208 kB
ctags: 2,500
sloc: cpp: 9,399; ansic: 3,142; sh: 2,430; makefile: 340
file content (515 lines) | stat: -rw-r--r-- 33,541 bytes
<!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>BitMagic: bmvmin.h Source File</title>
<link href="doxygen.css" rel="stylesheet" type="text/css">
</head><body>
<!-- Generated by Doxygen 1.4.1 -->
<div class="qindex"><a class="qindex" href="index.html">Main&nbsp;Page</a> | <a class="qindex" href="modules.html">Modules</a> | <a class="qindex" href="namespaces.html">Namespace List</a> | <a class="qindex" href="hierarchy.html">Class&nbsp;Hierarchy</a> | <a class="qindex" href="classes.html">Alphabetical&nbsp;List</a> | <a class="qindex" href="annotated.html">Data&nbsp;Structures</a> | <a class="qindex" href="dirs.html">Directories</a> | <a class="qindex" href="files.html">File&nbsp;List</a> | <a class="qindex" href="namespacemembers.html">Namespace&nbsp;Members</a> | <a class="qindex" href="functions.html">Data&nbsp;Fields</a> | <a class="qindex" href="globals.html">Globals</a> | <a class="qindex" href="examples.html">Examples</a></div>
<div class="nav">
<a class="el" href="dir_000000.html">src</a></div>
<h1>bmvmin.h</h1><a href="a00081.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment">00001 <span class="comment">/*</span>
00002 <span class="comment">Copyright(c) 2002-2005 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)</span>
00003 <span class="comment"></span>
00004 <span class="comment">Permission is hereby granted, free of charge, to any person </span>
00005 <span class="comment">obtaining a copy of this software and associated documentation </span>
00006 <span class="comment">files (the "Software"), to deal in the Software without restriction, </span>
00007 <span class="comment">including without limitation the rights to use, copy, modify, merge, </span>
00008 <span class="comment">publish, distribute, sublicense, and/or sell copies of the Software, </span>
00009 <span class="comment">and to permit persons to whom the Software is furnished to do so, </span>
00010 <span class="comment">subject to the following conditions:</span>
00011 <span class="comment"></span>
00012 <span class="comment">The above copyright notice and this permission notice shall be included </span>
00013 <span class="comment">in all copies or substantial portions of the Software.</span>
00014 <span class="comment"></span>
00015 <span class="comment">THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, </span>
00016 <span class="comment">EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES </span>
00017 <span class="comment">OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. </span>
00018 <span class="comment">IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, </span>
00019 <span class="comment">DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, </span>
00020 <span class="comment">ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR </span>
00021 <span class="comment">OTHER DEALINGS IN THE SOFTWARE.</span>
00022 <span class="comment"></span>
00023 <span class="comment">For more information please visit:  http://bmagic.sourceforge.net</span>
00024 <span class="comment"></span>
00025 <span class="comment">*/</span>
00026 
00027 <span class="preprocessor">#ifndef BMVMIN__H__INCLUDED__</span>
00028 <span class="preprocessor"></span><span class="preprocessor">#define BMVMIN__H__INCLUDED__</span>
00029 <span class="preprocessor"></span>
00030 <span class="keyword">namespace </span>bm
00031 {
00032 
00033 
<a name="l00034"></a><a class="code" href="a00081.html#a0">00034</a> <span class="preprocessor">#define BM_MINISET_GAPLEN (bm::gap_len_table&lt;true&gt;::_len[0])</span>
<a name="l00035"></a><a class="code" href="a00081.html#a1">00035</a> <span class="preprocessor"></span><span class="preprocessor">#define BM_MINISET_ARRSIZE(x) ((x / 32) + ( (x % 32) &amp;&amp; 1 ))</span>
00036 <span class="preprocessor"></span><span class="comment"></span>
00037 <span class="comment">/*! @defgroup mset Small sets functionality</span>
00038 <span class="comment"> *  Templates in this group are used to keep block types in BM library.</span>
00039 <span class="comment"> *  Classes of this group can tune bvector template (MS parameter)</span>
00040 <span class="comment"> *  for best performance or minimal memory usage.</span>
00041 <span class="comment"> *  @ingroup bmagic</span>
00042 <span class="comment"> *  @{</span>
00043 <span class="comment"> */</span>
00044 
00045 <span class="comment"></span>
00046 <span class="comment">/*!</span>
00047 <span class="comment">    @brief Template class implements memory saving set functionality</span>
00048 <span class="comment">    </span>
00049 <span class="comment">    Template can be used as template parameter for bvector if we </span>
00050 <span class="comment">    want to tune bvector for minimal memory consumption.</span>
00051 <span class="comment"></span>
00052 <span class="comment">    @sa bvmini</span>
00053 <span class="comment">*/</span>
<a name="l00054"></a><a class="code" href="a00072.html">00054</a> <span class="keyword">template</span> &lt;<span class="keyword">class</span> A, size_t N&gt; <span class="keyword">class </span><a class="code" href="a00072.html">miniset</a>
00055 {
00056 <span class="keyword">public</span>:
00057 
<a name="l00058"></a><a class="code" href="a00072.html#a0">00058</a>     <a class="code" href="a00072.html#a0">miniset</a>() 
00059         : m_buf(0),
00060           m_type(1)
00061     {}
00062 
<a name="l00063"></a><a class="code" href="a00072.html#a1">00063</a>     <a class="code" href="a00072.html#a0">miniset</a>(<span class="keyword">const</span> <a class="code" href="a00072.html">miniset</a>&amp; mset)
00064     {
00065         <span class="keywordflow">if</span> (mset.m_buf)
00066         {
00067             <span class="keywordflow">if</span> (mset.m_type)
00068                 init_gapbuf(mset.m_buf);
00069             <span class="keywordflow">else</span>
00070                 init_bitbuf(mset.m_buf);
00071         }
00072         <span class="keywordflow">else</span>
00073         {
00074             m_type = mset.m_type;
00075             m_buf = 0;
00076         }
00077     }
00078 
<a name="l00079"></a><a class="code" href="a00072.html#a2">00079</a>     <a class="code" href="a00072.html#a2">~miniset</a>()
00080     {
00081         <span class="keywordflow">if</span> (m_buf)
00082         {
00083             A::deallocate(m_buf, m_type ? 
00084                 (<a class="code" href="a00081.html#a0">BM_MINISET_GAPLEN</a> / (<span class="keyword">sizeof</span>(bm::word_t) / <span class="keyword">sizeof</span>(bm::gap_word_t)))
00085                 : 
00086                 (<a class="code" href="a00081.html#a1">BM_MINISET_ARRSIZE</a>(N)));
00087         }
00088     }
00089 <span class="comment"></span>
00090 <span class="comment">    /// Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.</span>
<a name="l00091"></a><a class="code" href="a00072.html#a3">00091</a> <span class="comment"></span>    <span class="keywordtype">unsigned</span> <a class="code" href="a00072.html#a3">test</a>(bm::id_t n)<span class="keyword"> const </span>
00092 <span class="keyword">    </span>{ 
00093         <span class="keywordflow">return</span>
00094             !m_buf ? 0 
00095             :
00096             m_type ? 
00097               <a class="code" href="a00096.html#ga0">gap_test</a>((<a class="code" href="a00092.html#a19">gap_word_t</a>*)m_buf, n)
00098               : 
00099               m_buf[n&gt;&gt;bm::set_word_shift] &amp; (1&lt;&lt;(n &amp; bm::set_word_mask));
00100     }
00101 
<a name="l00102"></a><a class="code" href="a00072.html#a4">00102</a>     <span class="keywordtype">void</span> <a class="code" href="a00072.html#a4">set</a>(bm::id_t n, <span class="keywordtype">bool</span> val=<span class="keyword">true</span>)
00103     {
00104         <span class="keywordflow">if</span> (m_type == 0)
00105         {
00106             <span class="keywordflow">if</span> (!m_buf)
00107             {
00108                 <span class="keywordflow">if</span> (!val) <span class="keywordflow">return</span>;
00109                 init_bitbuf(0);
00110             }
00111 
00112             <span class="keywordtype">unsigned</span> nword  = n &gt;&gt; bm::set_word_shift; 
00113             <span class="keywordtype">unsigned</span> mask = unsigned(1) &lt;&lt; (n &amp; bm::set_word_mask);
00114 
00115             val ? (m_buf[nword] |= mask) : (m_buf[nword] &amp;= ~mask);
00116         }
00117         <span class="keywordflow">else</span>
00118         {
00119             <span class="keywordflow">if</span> (!m_buf)
00120             {
00121                 <span class="keywordflow">if</span> (!val) <span class="keywordflow">return</span>;
00122                 init_gapbuf(0);
00123             }
00124             
00125             <span class="keywordtype">unsigned</span> is_set;
00126             <span class="keywordtype">unsigned</span> new_block_len = 
00127                 <a class="code" href="a00096.html#ga4">gap_set_value</a>(val, (<a class="code" href="a00092.html#a19">gap_word_t</a>*)m_buf, n, &amp;is_set);
00128 
00129             <span class="keywordflow">if</span> (new_block_len &gt; <span class="keywordtype">unsigned</span>(<a class="code" href="a00081.html#a0">BM_MINISET_GAPLEN</a>-4))
00130             {
00131                 convert_buf();
00132             }
00133         }
00134     }
00135 
<a name="l00136"></a><a class="code" href="a00072.html#a5">00136</a>     <span class="keywordtype">unsigned</span> <a class="code" href="a00072.html#a5">mem_used</a>()<span class="keyword"> const</span>
00137 <span class="keyword">    </span>{
00138         <span class="keywordflow">return</span> <span class="keyword">sizeof</span>(*this) +
00139                m_buf ? 
00140                  (m_type ? (<a class="code" href="a00081.html#a0">BM_MINISET_GAPLEN</a> * <span class="keyword">sizeof</span>(<a class="code" href="a00092.html#a19">gap_word_t</a>))
00141                         : (<a class="code" href="a00081.html#a1">BM_MINISET_ARRSIZE</a>(N) * <span class="keyword">sizeof</span>(bm::word_t)))
00142                 : 0; 
00143     }
00144 
<a name="l00145"></a><a class="code" href="a00072.html#a6">00145</a>     <span class="keywordtype">void</span> <a class="code" href="a00072.html#a6">swap</a>(<a class="code" href="a00072.html">miniset</a>&amp; mset)
00146     {
00147         bm::word_t* buftmp = m_buf;
00148         m_buf = mset.m_buf;
00149         mset.m_buf = buftmp;
00150         <span class="keywordtype">unsigned</span> typetmp = m_type;
00151         m_type = mset.m_type;
00152         mset.m_type = typetmp;
00153     }
00154 
00155 
00156 <span class="keyword">private</span>:
00157 
00158     <span class="keywordtype">void</span> init_bitbuf(bm::word_t* buf)
00159     {
00160         <span class="keywordtype">unsigned</span> arr_size = <a class="code" href="a00081.html#a1">BM_MINISET_ARRSIZE</a>(N);
00161         m_buf = A::allocate(arr_size, 0);
00162         <span class="keywordflow">if</span> (buf)
00163         {
00164             ::memcpy(m_buf, buf, arr_size * <span class="keyword">sizeof</span>(bm::word_t));
00165         }
00166         <span class="keywordflow">else</span>
00167         {
00168             ::memset(m_buf, 0, arr_size * <span class="keyword">sizeof</span>(bm::word_t));
00169         }
00170         m_type = 0;
00171     }
00172 
00173     <span class="keywordtype">void</span> init_gapbuf(bm::word_t* buf)
00174     {
00175         <span class="keywordtype">unsigned</span> arr_size = 
00176             <a class="code" href="a00081.html#a0">BM_MINISET_GAPLEN</a> / (<span class="keyword">sizeof</span>(bm::word_t) / <span class="keyword">sizeof</span>(bm::gap_word_t));
00177         m_buf = A::allocate(arr_size, 0);
00178         <span class="keywordflow">if</span> (buf)
00179         {
00180             ::memcpy(m_buf, buf, arr_size * <span class="keyword">sizeof</span>(bm::word_t));
00181         }
00182         <span class="keywordflow">else</span>
00183         {
00184             *m_buf = 0;
00185             <a class="code" href="a00096.html#ga14">gap_set_all</a>((gap_word_t*)m_buf, bm::gap_max_bits, 0);
00186         }
00187         m_type = 1;
00188     }
00189 
00190     <span class="keywordtype">void</span> convert_buf()
00191     {
00192         <span class="keywordtype">unsigned</span> arr_size = <a class="code" href="a00081.html#a1">BM_MINISET_ARRSIZE</a>(N);
00193         bm::word_t* buf = A::allocate(arr_size, 0);
00194 
00195         <a class="code" href="a00096.html#ga10">gap_convert_to_bitset</a>(buf, (gap_word_t*) m_buf, arr_size);
00196         arr_size = 
00197             <a class="code" href="a00081.html#a0">BM_MINISET_GAPLEN</a> / (<span class="keyword">sizeof</span>(bm::word_t) / <span class="keyword">sizeof</span>(bm::gap_word_t));
00198         A::deallocate(m_buf, arr_size);
00199         m_buf = buf;
00200         m_type = 0;
00201     }
00202 
00203 <span class="keyword">private</span>:
00204     bm::word_t*   m_buf;      <span class="comment">//!&lt; Buffer pointer</span>
00205 <span class="comment"></span>    <span class="keywordtype">unsigned</span>      m_type;     <span class="comment">//!&lt; buffer type (0-bit, 1-gap)</span>
00206 <span class="comment"></span>};
00207 
00208 <span class="comment"></span>
00209 <span class="comment">/*!</span>
00210 <span class="comment">    @brief Mini bitvector used in bvector template to keep block type flags</span>
00211 <span class="comment">    </span>
00212 <span class="comment">    Template is used as a default template parameter MS for bvector  </span>
00213 <span class="comment">    Offers maximum performance comparing to miniset.</span>
00214 <span class="comment"></span>
00215 <span class="comment">    @sa miniset</span>
00216 <span class="comment">*/</span>
<a name="l00217"></a><a class="code" href="a00059.html">00217</a> <span class="keyword">template</span>&lt;size_t N&gt; <span class="keyword">class </span><a class="code" href="a00059.html">bvmini</a>
00218 {
00219 <span class="keyword">public</span>:
00220 
<a name="l00221"></a><a class="code" href="a00059.html#a0">00221</a>     <a class="code" href="a00059.html#a0">bvmini</a>(<span class="keywordtype">int</span> start_strategy = 0) 
00222     {
00223         ::memset(m_buf, 0, <span class="keyword">sizeof</span>(m_buf));
00224     }
00225 
<a name="l00226"></a><a class="code" href="a00059.html#a1">00226</a>     <a class="code" href="a00059.html#a0">bvmini</a>(<span class="keyword">const</span> <a class="code" href="a00059.html">bvmini</a>&amp; mset)
00227     {
00228         ::memcpy(m_buf, mset.m_buf, <span class="keyword">sizeof</span>(m_buf));
00229     }
00230 
00231 <span class="comment"></span>
00232 <span class="comment">    /// Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.</span>
<a name="l00233"></a><a class="code" href="a00059.html#a2">00233</a> <span class="comment"></span>    <span class="keywordtype">unsigned</span> <a class="code" href="a00059.html#a2">test</a>(bm::id_t n)<span class="keyword"> const </span>
00234 <span class="keyword">    </span>{ 
00235         <span class="keywordflow">return</span> m_buf[n&gt;&gt;bm::set_word_shift] &amp; (1&lt;&lt;(n &amp; bm::set_word_mask));
00236     }
00237 
<a name="l00238"></a><a class="code" href="a00059.html#a3">00238</a>     <span class="keywordtype">void</span> <a class="code" href="a00059.html#a3">set</a>(bm::id_t n, <span class="keywordtype">bool</span> val=<span class="keyword">true</span>)
00239     {
00240         <span class="keywordtype">unsigned</span> nword  = n &gt;&gt; bm::set_word_shift; 
00241         <span class="keywordtype">unsigned</span> mask = unsigned(1) &lt;&lt; (n &amp; bm::set_word_mask);
00242 
00243         val ? (m_buf[nword] |= mask) : (m_buf[nword] &amp;= ~mask);
00244     }
00245 
<a name="l00246"></a><a class="code" href="a00059.html#a4">00246</a>     <span class="keywordtype">unsigned</span> <a class="code" href="a00059.html#a4">mem_used</a>()<span class="keyword"> const</span>
00247 <span class="keyword">    </span>{
00248         <span class="keywordflow">return</span> <span class="keyword">sizeof</span>(*this);
00249     }
00250 
<a name="l00251"></a><a class="code" href="a00059.html#a5">00251</a>     <span class="keywordtype">void</span> <a class="code" href="a00059.html#a5">swap</a>(<a class="code" href="a00059.html">bvmini</a>&amp; mset)
00252     {
00253         <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i = 0; i &lt; <a class="code" href="a00081.html#a1">BM_MINISET_ARRSIZE</a>(N); ++i)
00254         {
00255             bm::word_t tmp = m_buf[i];
00256             m_buf[i] = mset.m_buf[i];
00257             mset.m_buf[i] = tmp;
00258         }
00259     }
00260 
00261 <span class="keyword">private</span>:
00262     bm::word_t   m_buf[<a class="code" href="a00081.html#a1">BM_MINISET_ARRSIZE</a>(N)];
00263 };
00264 
00265 <span class="comment"></span>
00266 <span class="comment">/*!@} */</span>
00267 <span class="comment"></span>
00268 <span class="comment">/*!</span>
00269 <span class="comment">    @brief Bitvector class with very limited functionality.</span>
00270 <span class="comment"></span>
00271 <span class="comment">    Class implements simple bitset and used for internal </span>
00272 <span class="comment">    and testing purposes. </span>
00273 <span class="comment">*/</span>
<a name="l00274"></a><a class="code" href="a00058.html">00274</a> <span class="keyword">template</span>&lt;<span class="keyword">class</span> A&gt; <span class="keyword">class </span><a class="code" href="a00058.html">bvector_mini</a>
00275 {
00276 <span class="keyword">public</span>:
<a name="l00277"></a><a class="code" href="a00058.html#a0">00277</a>     <a class="code" href="a00058.html#a0">bvector_mini</a>(<span class="keywordtype">unsigned</span> size) 
00278       : m_buf(0),
00279         m_size(size)
00280     {
00281         <span class="keywordtype">unsigned</span> arr_size = (size / 32) + 1; 
00282         m_buf = A::allocate(arr_size, 0);
00283         ::memset(m_buf, 0, arr_size * <span class="keyword">sizeof</span>(unsigned));
00284     }
<a name="l00285"></a><a class="code" href="a00058.html#a1">00285</a>     <a class="code" href="a00058.html#a0">bvector_mini</a>(<span class="keyword">const</span> <a class="code" href="a00058.html">bvector_mini</a>&amp; <a class="code" href="a00048.html">bvect</a>)
00286        : m_size(<a class="code" href="a00048.html">bvect</a>.m_size)
00287     {
00288         <span class="keywordtype">unsigned</span> arr_size = (m_size / 32) + 1;
00289         m_buf = A::allocate(arr_size, 0);
00290         ::memcpy(m_buf, <a class="code" href="a00048.html">bvect</a>.m_buf, arr_size * <span class="keyword">sizeof</span>(unsigned));        
00291     }
00292 
<a name="l00293"></a><a class="code" href="a00058.html#a2">00293</a>     <a class="code" href="a00058.html#a2">~bvector_mini</a>()
00294     {
00295         A::deallocate(m_buf, (m_size / 32) + 1); 
00296     }
00297 <span class="comment"></span>
00298 <span class="comment">    /// Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.</span>
<a name="l00299"></a><a class="code" href="a00058.html#a3">00299</a> <span class="comment"></span>    <span class="keywordtype">int</span> <a class="code" href="a00058.html#a3">is_bit_true</a>(<span class="keywordtype">unsigned</span> pos)<span class="keyword"> const</span>
00300 <span class="keyword">    </span>{
00301         <span class="keywordtype">unsigned</span> <span class="keywordtype">char</span>  mask = (<span class="keywordtype">unsigned</span> char)((char)0x1 &lt;&lt; (pos &amp; 7));
00302         <span class="keywordtype">unsigned</span> <span class="keywordtype">char</span>* offs = (<span class="keywordtype">unsigned</span> <span class="keywordtype">char</span>*)m_buf + (pos &gt;&gt; 3); <span class="comment">// m_buf + (pos/8)</span>
00303 
00304         <span class="keywordflow">return</span> (*offs) &amp; mask;
00305     }
00306 <span class="comment"></span>
00307 <span class="comment">    /// Sets bit number pos to 1</span>
<a name="l00308"></a><a class="code" href="a00058.html#a4">00308</a> <span class="comment"></span>    <span class="keywordtype">void</span> <a class="code" href="a00058.html#a4">set_bit</a>(<span class="keywordtype">unsigned</span> pos)
00309     {
00310         <span class="keywordtype">unsigned</span> <span class="keywordtype">char</span>  mask = (<span class="keywordtype">unsigned</span> char)(0x1 &lt;&lt; (pos &amp; 7));
00311         <span class="keywordtype">unsigned</span> <span class="keywordtype">char</span>* offs = (<span class="keywordtype">unsigned</span> <span class="keywordtype">char</span>*)m_buf + (pos &gt;&gt; 3); 
00312         *offs |= mask;
00313     }
00314 
00315 <span class="comment"></span>
00316 <span class="comment">    /// Sets bit number pos to 0</span>
<a name="l00317"></a><a class="code" href="a00058.html#a5">00317</a> <span class="comment"></span>    <span class="keywordtype">void</span> <a class="code" href="a00058.html#a5">clear_bit</a>(<span class="keywordtype">unsigned</span> pos)
00318     {
00319         <span class="keywordtype">unsigned</span> <span class="keywordtype">char</span>  mask = (<span class="keywordtype">unsigned</span> char)(0x1 &lt;&lt; (pos &amp; 7));
00320         <span class="keywordtype">unsigned</span> <span class="keywordtype">char</span>* offs = (<span class="keywordtype">unsigned</span> <span class="keywordtype">char</span>*)m_buf + (pos &gt;&gt; 3); 
00321 
00322         *offs &amp;= ~mask;
00323     }
00324 <span class="comment"></span>
00325 <span class="comment">    /// Counts number of bits ON </span>
<a name="l00326"></a><a class="code" href="a00058.html#a6">00326</a> <span class="comment"></span>    <span class="keywordtype">unsigned</span> <a class="code" href="a00058.html#a6">bit_count</a>()<span class="keyword"> const</span>
00327 <span class="keyword">    </span>{
00328         <span class="keyword">register</span> <span class="keywordtype">unsigned</span> count = 0;
00329         <span class="keyword">const</span> <span class="keywordtype">unsigned</span>* end = m_buf + (m_size / 32)+1;    
00330 
00331         <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span>* start = m_buf; start &lt; end; ++start)
00332         {
00333             <span class="keyword">register</span> <span class="keywordtype">unsigned</span> value = *start;
00334             <span class="keywordflow">for</span> (count += (value!=0); value &amp;= value - 1; ++count);
00335         }
00336         <span class="keywordflow">return</span> count;
00337     }
00338 <span class="comment"></span>
00339 <span class="comment">    /// Comparison.</span>
<a name="l00340"></a><a class="code" href="a00058.html#a7">00340</a> <span class="comment"></span>    <span class="keywordtype">int</span> <a class="code" href="a00058.html#a7">compare</a>(<span class="keyword">const</span> <a class="code" href="a00058.html">bvector_mini</a>&amp; <a class="code" href="a00048.html">bvect</a>)
00341     {
00342         <span class="keywordtype">unsigned</span> cnt1 = <a class="code" href="a00058.html#a6">bit_count</a>();
00343         <span class="keywordtype">unsigned</span> cnt2 = <a class="code" href="a00048.html">bvect</a>.bit_count();
00344 
00345         <span class="keywordflow">if</span> (!cnt1 &amp;&amp; !cnt2) <span class="keywordflow">return</span> 0;
00346 
00347         <span class="keywordtype">unsigned</span> cnt_min = cnt1 &lt; cnt2 ? cnt1 : cnt2;
00348 
00349         <span class="keywordflow">if</span> (!cnt_min) <span class="keywordflow">return</span> cnt1 ? 1 : -1;
00350 
00351         <span class="keywordtype">unsigned</span> idx1 = <a class="code" href="a00058.html#a8">get_first</a>();
00352         <span class="keywordtype">unsigned</span> idx2 = <a class="code" href="a00048.html">bvect</a>.get_first();
00353 
00354         <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i = 0; i &lt; cnt_min; ++i)
00355         {
00356             <span class="keywordflow">if</span> (idx1 != idx2)
00357             {
00358                 <span class="keywordflow">return</span> idx1 &lt; idx2 ? 1 : -1;
00359             }
00360             idx1 = <a class="code" href="a00058.html#a9">get_next</a>(idx1);
00361             idx2 = <a class="code" href="a00048.html">bvect</a>.get_next(idx2);
00362         }
00363 
00364         <a class="code" href="a00077.html#a0">BM_ASSERT</a>(idx1==0 || idx2==0);
00365 
00366         <span class="keywordflow">if</span> (idx1 != idx2)
00367         {
00368             <span class="keywordflow">if</span> (!idx1) <span class="keywordflow">return</span> -1;
00369             <span class="keywordflow">if</span> (!idx2) <span class="keywordflow">return</span>  1;
00370             <span class="keywordflow">return</span> idx1 &lt; idx2 ? 1 : -1;
00371         }
00372 
00373         <span class="keywordflow">return</span> 0;
00374     }
00375 
00376 <span class="comment"></span>
00377 <span class="comment">    /// Returns index of the first ON bit</span>
<a name="l00378"></a><a class="code" href="a00058.html#a8">00378</a> <span class="comment"></span>    <span class="keywordtype">unsigned</span> <a class="code" href="a00058.html#a8">get_first</a>()<span class="keyword"> const</span>
00379 <span class="keyword">    </span>{
00380         <span class="keywordtype">unsigned</span> pos = 0;
00381         <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">char</span>* ptr = (<span class="keywordtype">unsigned</span> <span class="keywordtype">char</span>*) m_buf;
00382 
00383         <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i = 0; i &lt; (m_size/8)+1; ++i)
00384         {
00385             <span class="keyword">register</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">char</span> w = ptr[i];
00386 
00387 
00388             <span class="keywordflow">if</span> (w != 0)
00389             {
00390                 <span class="keywordflow">while</span> ((w &amp; 1) == 0)
00391                 {
00392                     w &gt;&gt;= 1;
00393                     ++pos;
00394                 }
00395                 <span class="keywordflow">return</span> pos;
00396             }
00397             pos += <span class="keyword">sizeof</span>(<span class="keywordtype">unsigned</span> char) * 8;
00398         }
00399         <span class="keywordflow">return</span> 0;
00400     }
00401 
00402 <span class="comment"></span>
00403 <span class="comment">    /// Returns index of next bit, which is ON</span>
<a name="l00404"></a><a class="code" href="a00058.html#a9">00404</a> <span class="comment"></span>    <span class="keywordtype">unsigned</span> <a class="code" href="a00058.html#a9">get_next</a>(<span class="keywordtype">unsigned</span> idx)<span class="keyword"> const</span>
00405 <span class="keyword">    </span>{
00406         <span class="keyword">register</span> <span class="keywordtype">unsigned</span> i;
00407 
00408         <span class="keywordflow">for</span> (i = idx+1; i &lt; m_size; ++i)
00409         {
00410             <span class="keywordtype">unsigned</span> <span class="keywordtype">char</span>* offs = (<span class="keywordtype">unsigned</span> <span class="keywordtype">char</span>*)m_buf + (i &gt;&gt; 3); 
00411             <span class="keywordflow">if</span> (*offs)
00412             {
00413                 <span class="keywordtype">unsigned</span> <span class="keywordtype">char</span> mask = (<span class="keywordtype">unsigned</span> char)((char)0x1 &lt;&lt; (i &amp; 7));
00414 
00415                 <span class="keywordflow">if</span> (*offs &amp; mask)
00416                 {
00417                     <span class="keywordflow">return</span> i;
00418                 }
00419             }
00420             <span class="keywordflow">else</span>
00421             {
00422                 i += 7;
00423             }
00424         }
00425         <span class="keywordflow">return</span> 0;
00426     }
00427 
00428 
<a name="l00429"></a><a class="code" href="a00058.html#a10">00429</a>     <span class="keywordtype">void</span> <a class="code" href="a00058.html#a10">combine_and</a>(<span class="keyword">const</span> <a class="code" href="a00058.html">bvector_mini</a>&amp; <a class="code" href="a00048.html">bvect</a>)
00430     {
00431         <span class="keyword">const</span> <span class="keywordtype">unsigned</span>* end = m_buf + (m_size / 32)+1;
00432     
00433         <span class="keyword">const</span> <span class="keywordtype">unsigned</span>* src = <a class="code" href="a00048.html">bvect</a>.get_buf();
00434 
00435         <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span>* start = m_buf; start &lt; end; ++start)
00436         {
00437             *start &amp;= *src++;
00438         }
00439     }
00440 
<a name="l00441"></a><a class="code" href="a00058.html#a11">00441</a>     <span class="keywordtype">void</span> <a class="code" href="a00058.html#a11">combine_xor</a>(<span class="keyword">const</span> <a class="code" href="a00058.html">bvector_mini</a>&amp; <a class="code" href="a00048.html">bvect</a>)
00442     {
00443         <span class="keyword">const</span> <span class="keywordtype">unsigned</span>* end = m_buf + (m_size / 32)+1;
00444     
00445         <span class="keyword">const</span> <span class="keywordtype">unsigned</span>* src = <a class="code" href="a00048.html">bvect</a>.get_buf();
00446 
00447         <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span>* start = m_buf; start &lt; end; ++start)
00448         {
00449             *start ^= *src++;
00450         }
00451     }
00452 
00453 
<a name="l00454"></a><a class="code" href="a00058.html#a12">00454</a>     <span class="keywordtype">void</span> <a class="code" href="a00058.html#a12">combine_or</a>(<span class="keyword">const</span> <a class="code" href="a00058.html">bvector_mini</a>&amp; <a class="code" href="a00048.html">bvect</a>)
00455     {
00456         <span class="keyword">const</span> <span class="keywordtype">unsigned</span>* end = m_buf + (m_size / 32)+1;
00457     
00458         <span class="keyword">const</span> <span class="keywordtype">unsigned</span>* src = <a class="code" href="a00048.html">bvect</a>.get_buf();
00459 
00460         <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span>* start = m_buf; start &lt; end; ++start)
00461         {
00462             *start |= *src++;
00463         }
00464     }
00465 
<a name="l00466"></a><a class="code" href="a00058.html#a13">00466</a>     <span class="keywordtype">void</span> <a class="code" href="a00058.html#a13">combine_sub</a>(<span class="keyword">const</span> <a class="code" href="a00058.html">bvector_mini</a>&amp; <a class="code" href="a00048.html">bvect</a>)
00467     {
00468         <span class="keyword">const</span> <span class="keywordtype">unsigned</span>* end = m_buf + (m_size / 32)+1;
00469     
00470         <span class="keyword">const</span> <span class="keywordtype">unsigned</span>* src = <a class="code" href="a00048.html">bvect</a>.get_buf();
00471 
00472         <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span>* start = m_buf; start &lt; end; ++start)
00473         {
00474             *start &amp;= ~(*src++);
00475         }
00476     }
00477 
<a name="l00478"></a><a class="code" href="a00058.html#a14">00478</a>     <span class="keyword">const</span> <span class="keywordtype">unsigned</span>* <a class="code" href="a00058.html#a14">get_buf</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> m_buf; }
<a name="l00479"></a><a class="code" href="a00058.html#a15">00479</a>     <span class="keywordtype">unsigned</span> <a class="code" href="a00058.html#a15">mem_used</a>()<span class="keyword"> const</span>
00480 <span class="keyword">    </span>{
00481         <span class="keywordflow">return</span> <span class="keyword">sizeof</span>(<a class="code" href="a00058.html">bvector_mini</a>) + (m_size / 32) + 1;
00482     }
00483 
<a name="l00484"></a><a class="code" href="a00058.html#a16">00484</a>     <span class="keywordtype">void</span> <a class="code" href="a00058.html#a16">swap</a>(<a class="code" href="a00058.html">bvector_mini</a>&amp; bvm)
00485     {
00486         <a class="code" href="a00077.html#a0">BM_ASSERT</a>(m_size == bvm.m_size);
00487         bm::word_t* buftmp = m_buf;
00488         m_buf = bvm.m_buf;
00489         bvm.m_buf = buftmp;
00490     }
00491 
00492 <span class="keyword">private</span>:
00493     bm::word_t*   m_buf;
00494     <span class="keywordtype">unsigned</span>      m_size;
00495 };
00496 
00497 
00498 
00499 } <span class="comment">// namespace bm</span>
00500 
00501 <span class="preprocessor">#endif</span>
</pre></div><hr size="1"><address style="align: right;"><small>Generated on Thu Apr 20 13:28:46 2006 for BitMagic by&nbsp;
<a href="http://www.doxygen.org/index.html">
<img src="doxygen.png" alt="doxygen" align="middle" border="0"></a> 1.4.1 </small></address>
</body>
</html>