Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Data Structures | Directories | File List | Namespace Members | Data Fields | Globals | Examples

bmfunc.h

Go to the documentation of this file.
00001 /*
00002 // Copyright(c) 2002-2005 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
00003 
00004 Permission is hereby granted, free of charge, to any person 
00005 obtaining a copy of this software and associated documentation 
00006 files (the "Software"), to deal in the Software without restriction, 
00007 including without limitation the rights to use, copy, modify, merge, 
00008 publish, distribute, sublicense, and/or sell copies of the Software, 
00009 and to permit persons to whom the Software is furnished to do so, 
00010 subject to the following conditions:
00011 
00012 The above copyright notice and this permission notice shall be included 
00013 in all copies or substantial portions of the Software.
00014 
00015 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
00016 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES 
00017 OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 
00018 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, 
00019 DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 
00020 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 
00021 OTHER DEALINGS IN THE SOFTWARE.
00022 
00023 For more information please visit:  http://bmagic.sourceforge.net
00024 
00025 */
00026 
00027 #ifndef BMFUNC__H__INCLUDED__
00028 #define BMFUNC__H__INCLUDED__
00029 
00030 #include <memory.h>
00031 
00032 
00033 #ifdef _MSC_VER
00034 # pragma warning( disable: 4146 )
00035 #endif
00036 
00037 namespace bm
00038 {
00039 
00040 
00041 /*!
00042     @brief Structure with statistical information about bitset's memory 
00043             allocation details. 
00044     @ingroup bvector
00045 */
00046 struct bv_statistics
00047 {
00048     /// Number of bit blocks.
00049     unsigned bit_blocks; 
00050     /// Number of GAP blocks.
00051     unsigned gap_blocks;  
00052     /// Estimated maximum of memory required for serialization.
00053     unsigned max_serialize_mem;
00054     /// Memory used by bitvector including temp and service blocks
00055     unsigned  memory_used;
00056     /// Array of all GAP block lengths in the bvector.
00057     gap_word_t   gap_length[bm::set_total_blocks];
00058     /// GAP lengths used by bvector
00059     gap_word_t  gap_levels[bm::gap_levels];
00060 
00061 
00062 
00063     /// cound bit block
00064     void add_bit_block()
00065     {
00066         ++bit_blocks;
00067         unsigned mem_used = sizeof(bm::word_t) * bm::set_block_size;
00068         memory_used += mem_used;
00069         max_serialize_mem += mem_used;
00070     }
00071 
00072     /// count gap block
00073     void add_gap_block(unsigned capacity, unsigned length)
00074     {
00075         ++gap_blocks;
00076         unsigned mem_used = capacity * sizeof(gap_word_t);
00077         memory_used += mem_used;
00078         max_serialize_mem += length * sizeof(gap_word_t);
00079     }
00080 };
00081 
00082 
00083 /*! @defgroup gapfunc GAP functions
00084  *  GAP functions implement different opereations on GAP compressed blocks
00085  *  and serve as a minimal building blocks.
00086  *  @ingroup bmagic
00087  *
00088  */
00089 
00090 /*! @defgroup bitfunc BIT functions
00091  *  Bit functions implement different opereations on bit blocks
00092  *  and serve as a minimal building blocks.
00093  *  @ingroup bmagic
00094  */
00095 
00096 
00097 /*! @brief Default GAP lengths table.
00098     @ingroup gapfunc
00099 */
00100 template<bool T> struct gap_len_table
00101 {
00102     static const gap_word_t _len[bm::gap_levels];
00103 };
00104 
00105 template<bool T>
00106 const gap_word_t gap_len_table<T>::_len[bm::gap_levels] = 
00107                 { 128, 256, 512, bm::gap_max_buff_len }; 
00108 
00109 
00110 /*! @brief Alternative GAP lengths table. 
00111     Good for for memory saver mode and very sparse bitsets.
00112 
00113     @ingroup gapfunc
00114 */
00115 template<bool T> struct gap_len_table_min
00116 {
00117     static const gap_word_t _len[bm::gap_levels];
00118 };
00119 
00120 template<bool T>
00121 const gap_word_t gap_len_table_min<T>::_len[bm::gap_levels] = 
00122                                 { 32, 96, 128, 512 }; 
00123 
00124 
00125 //---------------------------------------------------------------------
00126 
00127 /** Structure to aid in counting bits
00128     table contains count of bits in 0-255 diapason of numbers
00129 
00130    @ingroup bitfunc
00131 */
00132 template<bool T> struct bit_count_table 
00133 {
00134   static const unsigned char _count[256];
00135 };
00136 
00137 template<bool T>
00138 const unsigned char bit_count_table<T>::_count[256] = {
00139     0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
00140     1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
00141     1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
00142     2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
00143     1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
00144     2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
00145     2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
00146     3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
00147 };
00148 
00149 //---------------------------------------------------------------------
00150 
00151 /** Structure keeps all-left/right ON bits masks. 
00152     @ingroup bitfunc 
00153 */
00154 template<bool T> struct block_set_table
00155 {
00156     static const unsigned _left[32];
00157     static const unsigned _right[32];
00158 };
00159 
00160 template<bool T>
00161 const unsigned block_set_table<T>::_left[32] = {
00162     0x1, 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff, 0x3ff, 0x7ff,
00163     0xfff, 0x1fff, 0x3fff, 0x7fff, 0xffff, 0x1ffff, 0x3ffff, 0x7ffff,
00164     0xfffff, 0x1fffff, 0x3fffff, 0x7fffff, 0xffffff, 0x1ffffff, 0x3ffffff,
00165     0x7ffffff, 0xfffffff, 0x1fffffff, 0x3fffffff, 0x7fffffff, 0xffffffff
00166 };
00167 
00168 template<bool T>
00169 const unsigned block_set_table<T>::_right[32] = {
00170     0xffffffff, 0xfffffffe, 0xfffffffc, 0xfffffff8, 0xfffffff0,
00171     0xffffffe0, 0xffffffc0, 0xffffff80, 0xffffff00, 0xfffffe00,
00172     0xfffffc00, 0xfffff800, 0xfffff000, 0xffffe000, 0xffffc000,
00173     0xffff8000, 0xffff0000, 0xfffe0000, 0xfffc0000, 0xfff80000,
00174     0xfff00000, 0xffe00000, 0xffc00000, 0xff800000, 0xff000000,
00175     0xfe000000, 0xfc000000, 0xf8000000, 0xf0000000, 0xe0000000,
00176     0xc0000000, 0x80000000
00177 };
00178 
00179 
00180 
00181 /** Structure keeps index of first ON bit for every byte.  
00182     @ingroup bitfunc 
00183 */
00184 template<bool T> struct first_bit_table
00185 {
00186     static const char _idx[256];
00187 };
00188 
00189 template<bool T>
00190 const char first_bit_table<T>::_idx[256] = {
00191     -1,
00192     0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,
00193     1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1, 0,2,0,1,0,3,0,
00194     1,0,2,0,1,0,6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,
00195     0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,
00196     2,0,1,0,3,0,1,0,2,0,1,0,7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,
00197     0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,
00198     1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,0,1,0,2,0,1,0,3,0,1,
00199     0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,
00200     3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0 
00201 };
00202 
00203 
00204 /*! 
00205     Define calculates number of 1 bits in 32-bit word.
00206     @ingroup bitfunc 
00207 */
00208 
00209 #define BM_INCWORD_BITCOUNT(cnt, w) cnt += \
00210     bm::bit_count_table<true>::_count[(unsigned char)(w)] + \
00211     bm::bit_count_table<true>::_count[(unsigned char)((w) >> 8)] + \
00212     bm::bit_count_table<true>::_count[(unsigned char)((w) >> 16)] + \
00213     bm::bit_count_table<true>::_count[(unsigned char)((w) >> 24)];
00214 
00215 /*!
00216     Returns bit count
00217     @ingroup bitfunc 
00218 */
00219 BMFORCEINLINE
00220 bm::id_t word_bitcount(bm::id_t w)
00221 {
00222     return
00223     bm::bit_count_table<true>::_count[(unsigned char)(w)] + 
00224     bm::bit_count_table<true>::_count[(unsigned char)((w) >> 8)] + 
00225     bm::bit_count_table<true>::_count[(unsigned char)((w) >> 16)] + 
00226     bm::bit_count_table<true>::_count[(unsigned char)((w) >> 24)];
00227 }
00228 
00229 #ifdef BM64OPT
00230 /*! 
00231     Function calculates number of 1 bits in 64-bit word.
00232     @ingroup bitfunc 
00233 */
00234 inline bm::id_t word_bitcount64(bm::id64_t w)
00235 {
00236     w = (w & 0x5555555555555555LU) + (w >> 1 & 0x5555555555555555LU);
00237     w = (w & 0x3333333333333333LU) + (w >> 2 & 0x3333333333333333LU);
00238     w = w + (w >> 4) & 0x0F0F0F0F0F0F0F0FLU;
00239     w = w + (w >> 8);
00240     w = w + (w >> 16);
00241     w = w + (w >> 32) & 0x0000007F;
00242     return (bm::id_t)w;
00243 }
00244 #endif
00245 
00246 
00247 
00248 //---------------------------------------------------------------------
00249 
00250 /**
00251     Nomenclature of set operations
00252 */
00253 enum set_operation
00254 {
00255     set_AND         = 0,
00256     set_OR          = 1,
00257     set_SUB         = 2,
00258     set_XOR         = 3,
00259     set_ASSIGN      = 4,
00260     set_COUNT       = 5,
00261     set_COUNT_AND   = 6,
00262     set_COUNT_XOR   = 7,
00263     set_COUNT_OR    = 8,
00264     set_COUNT_SUB_AB= 9,
00265     set_COUNT_SUB_BA= 10,
00266     set_COUNT_A     = 11,
00267     set_COUNT_B     = 12,
00268 
00269     set_END
00270 };
00271 
00272 /// Returns true if set operation is constant (bitcount)
00273 inline
00274 bool is_const_set_operation(set_operation op)
00275 {
00276     return (int(op) >= int(set_COUNT));
00277 }
00278 
00279 /**
00280     Bit operations enumeration.
00281 */
00282 enum operation
00283 {
00284     BM_AND = set_AND,
00285     BM_OR  = set_OR,
00286     BM_SUB = set_SUB,
00287     BM_XOR = set_XOR
00288 };
00289 
00290 /**
00291     Convert set operation to operation
00292 */
00293 inline
00294 bm::operation setop2op(bm::set_operation op)
00295 {
00296     BM_ASSERT(op == set_AND || 
00297               op == set_OR  || 
00298               op == set_SUB || 
00299               op == set_XOR);
00300     return (bm::operation) op;
00301 }
00302 
00303 //---------------------------------------------------------------------
00304 
00305 /** 
00306     Structure carries pointer on bit block with all bits 1
00307     @ingroup bitfunc 
00308 */
00309 template<bool T> struct all_set
00310 {
00311     struct all_set_block
00312     {
00313         bm::word_t _p[bm::set_block_size];
00314 
00315         all_set_block()
00316         {
00317             ::memset(_p, 0xFF, sizeof(_p));
00318         }
00319     };
00320 
00321     static all_set_block  _block;
00322 };
00323 
00324 
00325 template<bool T> typename all_set<T>::all_set_block all_set<T>::_block;
00326 
00327 /// XOR swap two scalar variables
00328 template<typename W> 
00329 void xor_swap(W& x, W& y) 
00330 {
00331     BM_ASSERT(&x != &y);
00332     x ^= y;
00333     y ^= x;
00334     x ^= y;
00335 }
00336 
00337 
00338 //---------------------------------------------------------------------
00339 
00340 /*! 
00341    \brief Lexicographical comparison of two words as bit strings.
00342    Auxiliary implementation for testing and reference purposes.
00343    \param buf1 - First word.
00344    \param buf2 - Second word.
00345    \return  <0 - less, =0 - equal,  >0 - greater.
00346 
00347    @ingroup bitfunc 
00348 */
00349 template<typename T> int wordcmp0(T w1, T w2)
00350 {
00351     while (w1 != w2)
00352     {
00353         int res = (w1 & 1) - (w2 & 1);
00354         if (res != 0) return res;
00355         w1 >>= 1;
00356         w2 >>= 1;
00357     }
00358     return 0;
00359 }
00360 
00361 
00362 /*! 
00363    \brief Lexicographical comparison of two words as bit strings.
00364    Auxiliary implementation for testing and reference purposes.
00365    \param buf1 - First word.
00366    \param buf2 - Second word.
00367    \return  <0 - less, =0 - equal,  >0 - greater.
00368 
00369    @ingroup bitfunc 
00370 */
00371 /*
00372 template<typename T> int wordcmp(T w1, T w2)
00373 {
00374     T diff = w1 ^ w2;
00375     return diff ? ((w1 & diff & (diff ^ (diff - 1)))? 1 : -1) : 0; 
00376 }
00377 */
00378 
00379 template<typename T> int wordcmp(T a, T b)
00380 {
00381     T diff = a ^ b;
00382     return diff? ( (a & diff & -diff)? 1 : -1 ) : 0;
00383 }
00384 
00385 
00386 // Low bit extraction
00387 // x & (x ^ (x-1))
00388 
00389 
00390 /**
00391     Internal structure. Copyright information.
00392 */
00393 template<bool T> struct _copyright
00394 {
00395     static const char _p[];
00396 };
00397 
00398 template<bool T> const char _copyright<T>::_p[] = 
00399     "BitMagic Library. v.3.5.0 (c) 2002-2007 Anatoliy Kuznetsov.";
00400 
00401 
00402 /*! 
00403    \brief Byte orders recognized by the library.
00404 */
00405 enum ByteOrder
00406 {
00407     BigEndian    = 0,
00408     LittleEndian = 1
00409 };
00410 
00411 
00412 /**
00413     Internal structure. Different global settings.
00414 */
00415 template<bool T> struct globals
00416 {
00417     struct bo
00418     {
00419         ByteOrder  _byte_order;
00420 
00421         bo()
00422         {
00423             unsigned x;
00424             unsigned char *s = (unsigned char *)&x;
00425             s[0] = 1;
00426             s[1] = 2;
00427             s[2] = 3;
00428             s[3] = 4;
00429 
00430             if(x == 0x04030201) 
00431             {
00432                 _byte_order = LittleEndian;
00433                 return;
00434             }
00435 
00436             if(x == 0x01020304) 
00437             {
00438                 _byte_order = BigEndian;
00439                 return;
00440             }
00441 
00442             BM_ASSERT(0); // "Invalid Byte Order\n"
00443             _byte_order = LittleEndian;
00444         }
00445     };
00446 
00447     static bo  _bo;
00448 
00449     static ByteOrder byte_order() { return _bo._byte_order; }
00450 
00451 };
00452 
00453 template<bool T> typename globals<T>::bo globals<T>::_bo;
00454 
00455 
00456 
00457 
00458 
00459 
00460 /*
00461    \brief Binary search for the block where bit = pos located.
00462    \param buf - GAP buffer pointer.
00463    \param pos - index of the element.
00464    \param is_set - output. GAP value (0 or 1). 
00465    \return GAP index.
00466    @ingroup gapfunc
00467 */
00468 template<typename T> 
00469 unsigned gap_bfind(const T* buf, unsigned pos, unsigned* is_set)
00470 {
00471     BM_ASSERT(pos < bm::gap_max_bits);
00472     *is_set = (*buf) & 1;
00473 
00474     register unsigned start = 1;
00475     register unsigned end = 1 + ((*buf) >> 3);
00476 
00477     while ( start != end )
00478     {
00479         unsigned curr = (start + end) >> 1;
00480         if ( buf[curr] < pos )
00481             start = curr + 1;
00482         else
00483             end = curr;
00484     }
00485     *is_set ^= ((start-1) & 1);
00486     return start; 
00487 }
00488 
00489 
00490 /*!
00491    \brief Tests if bit = pos is true.
00492    \param buf - GAP buffer pointer.
00493    \param pos - index of the element.
00494    \return true if position is in "1" gap
00495    @ingroup gapfunc
00496 */
00497 template<typename T> unsigned gap_test(const T* buf, unsigned pos)
00498 {
00499     BM_ASSERT(pos < bm::gap_max_bits);
00500 
00501     unsigned start = 1;
00502     unsigned end = 1 + ((*buf) >> 3);
00503 
00504     if (end - start < 10)
00505     {
00506         unsigned sv = *buf & 1;
00507         unsigned sv1= sv ^ 1;
00508         if (buf[1] >= pos) return sv;
00509         if (buf[2] >= pos) return sv1;
00510         if (buf[3] >= pos) return sv;
00511         if (buf[4] >= pos) return sv1;
00512         if (buf[5] >= pos) return sv;
00513         if (buf[6] >= pos) return sv1;
00514         if (buf[7] >= pos) return sv;
00515         if (buf[8] >= pos) return sv1;
00516         if (buf[9] >= pos) return sv;
00517         BM_ASSERT(0);
00518     }
00519     else
00520     while ( start != end )
00521     {
00522         unsigned curr = (start + end) >> 1;
00523         if ( buf[curr] < pos )
00524             start = curr + 1;
00525         else
00526             end = curr;
00527     }
00528     return ((*buf) & 1) ^ ((--start) & 1); 
00529 }
00530 
00531 
00532 /*! For each non-zero block executes supplied function.
00533 */
00534 template<class T, class F> 
00535 void for_each_nzblock(T*** root, unsigned size1, unsigned size2, 
00536                       F& f)
00537 {
00538     unsigned block_idx = 0;
00539     for (unsigned i = 0; i < size1; ++i)
00540     {
00541         T** blk_blk = root[i];
00542 
00543         if (!blk_blk) 
00544         {
00545             f.on_empty_top(i);
00546             block_idx += size2;
00547             continue;
00548         }
00549 
00550         unsigned non_empty_top = 0;
00551         for (unsigned j = 0;j < size2; ++j, ++block_idx)
00552         {
00553             if (blk_blk[j]) 
00554             {
00555                 f(blk_blk[j], block_idx);
00556                 // re-check (blk_blk[j]): could be a mutation
00557                 non_empty_top += (blk_blk[j] != 0);
00558             }
00559             else
00560             {
00561                 f.on_empty_block(block_idx);
00562             }
00563         } // for j
00564         if (non_empty_top == 0)
00565         {
00566             f.on_empty_top(i);
00567         }
00568     }  // for i
00569 }
00570 
00571 /*! For each non-zero block executes supplied function-predicate.
00572     Function returns if function-predicate returns true
00573 */
00574 template<class T, class F> 
00575 bool for_each_nzblock_if(T*** root, unsigned size1, unsigned size2, F& f)
00576 {
00577     unsigned block_idx = 0;
00578     for (unsigned i = 0; i < size1; ++i)
00579     {
00580         T** blk_blk = root[i];
00581 
00582         if (!blk_blk) 
00583         {
00584             block_idx += bm::set_array_size;
00585             continue;
00586         }
00587 
00588         for (unsigned j = 0;j < size2; ++j, ++block_idx)
00589         {
00590             if (blk_blk[j]) 
00591                 if (f(blk_blk[j], block_idx)) return true;
00592         }
00593     }
00594     return false;
00595 }
00596 
00597 /*! For each block executes supplied function.
00598 */
00599 template<class T, class F> 
00600 void for_each_block(T*** root, unsigned size1, unsigned size2, F& f)
00601 {
00602     unsigned block_idx = 0;
00603 
00604     for (unsigned i = 0; i < size1; ++i)
00605     {
00606         T** blk_blk = root[i];
00607 
00608         if (blk_blk)
00609         {
00610             for (unsigned j = 0;j < size2; ++j, ++block_idx)
00611             {
00612                 f(blk_blk[j], block_idx);
00613             }
00614         }
00615         else
00616         {
00617             for (unsigned j = 0;j < size2; ++j, ++block_idx)
00618             {
00619                 f(0, block_idx);
00620             }
00621         }
00622     }  
00623 }
00624 
00625 
00626 
00627 /*! Special BM optimized analog of STL for_each
00628 */
00629 template<class T, class F> F bmfor_each(T first, T last, F f)
00630 {
00631     do
00632     {
00633         f(*first);
00634         ++first;
00635     } while (first < last);
00636     return f;
00637 }
00638 
00639 /*! Computes SUM of all elements of the sequence
00640 */
00641 template<class T> T sum_arr(T* first, T* last)
00642 {
00643     T sum = 0;
00644     while (first < last)
00645     {
00646         sum += *first;
00647         ++first;
00648     }
00649     return sum;
00650 }
00651 
00652 
00653 /*! 
00654    \brief Calculates number of bits ON in GAP buffer.
00655    \param buf - GAP buffer pointer.
00656    \return Number of non-zero bits.
00657    @ingroup gapfunc
00658 */
00659 template<typename T> unsigned gap_bit_count(const T* buf) 
00660 {
00661     register const T* pcurr = buf;
00662     register const T* pend = pcurr + (*pcurr >> 3);
00663 
00664     register unsigned bits_counter = 0;
00665     ++pcurr;
00666 
00667     if (*buf & 1)
00668     {
00669         bits_counter += *pcurr + 1;
00670         ++pcurr;
00671     }
00672     ++pcurr;  // set GAP to 1
00673 
00674     while (pcurr <= pend)
00675     {
00676         bits_counter += *pcurr - *(pcurr-1);
00677         pcurr += 2; // jump to the next positive GAP
00678     } 
00679 
00680     return bits_counter;
00681 }
00682 
00683 /*!
00684    \brief Counts 1 bits in GAP buffer in the closed [left, right] diapason.
00685    \param buf - GAP buffer pointer.
00686    \param left - leftmost bit index to start from
00687    \param right- rightmost bit index
00688    \return Number of non-zero bits.
00689 */
00690 template<typename T>
00691 unsigned gap_bit_count_range(const T* buf, T left, T right)
00692 {
00693     BM_ASSERT(left <= right);
00694     
00695     const T* pcurr = buf;
00696     const T* pend = pcurr + (*pcurr >> 3);
00697     
00698     unsigned bits_counter = 0;
00699     unsigned is_set;
00700     unsigned start_pos = gap_bfind(buf, left, &is_set);
00701 
00702     pcurr = buf + start_pos;
00703     if (right <= *pcurr) // we are in the target block right now
00704     {
00705         if (is_set)
00706             bits_counter = (right - left + 1);
00707         return bits_counter;
00708     }
00709     if (is_set)
00710         bits_counter += *pcurr - left + 1;
00711 
00712     unsigned prev_gap = *pcurr++;
00713     is_set ^= 1;
00714     while (right > *pcurr)
00715     {
00716         if (is_set)
00717             bits_counter += *pcurr - prev_gap;
00718         if (pcurr == pend) 
00719             return bits_counter;
00720         prev_gap = *pcurr++;
00721         is_set ^= 1;
00722     }
00723     if (is_set)
00724         bits_counter += right - prev_gap;
00725 
00726     return bits_counter;
00727 }
00728 
00729 
00730 
00731 /*! 
00732    \brief Lexicographical comparison of GAP buffers.
00733    \param buf1 - First GAP buffer pointer.
00734    \param buf2 - Second GAP buffer pointer.
00735    \return  <0 - less, =0 - equal,  >0 - greater.
00736 
00737    @ingroup gapfunc
00738 */
00739 template<typename T> int gapcmp(const T* buf1, const T* buf2)
00740 {
00741     const T* pcurr1 = buf1;
00742     const T* pend1 = pcurr1 + (*pcurr1 >> 3);
00743     unsigned bitval1 = *buf1 & 1;
00744     ++pcurr1;
00745 
00746     const T* pcurr2 = buf2;
00747     unsigned bitval2 = *buf2 & 1;
00748     ++pcurr2;
00749 
00750     while (pcurr1 <= pend1)
00751     {
00752         if (*pcurr1 == *pcurr2)
00753         {
00754             if (bitval1 != bitval2)
00755             {
00756                 return (bitval1) ? 1 : -1;
00757             }
00758         }
00759         else
00760         {
00761             if (bitval1 == bitval2)
00762             {
00763                 if (bitval1)
00764                 {
00765                     return (*pcurr1 < *pcurr2) ? -1 : 1;
00766                 }
00767                 else
00768                 {
00769                     return (*pcurr1 < *pcurr2) ? 1 : -1;
00770                 }
00771             }
00772             else
00773             {
00774                 return (bitval1) ? 1 : -1;
00775             }
00776         }
00777 
00778         ++pcurr1; ++pcurr2;
00779 
00780         bitval1 ^= 1;
00781         bitval2 ^= 1;
00782     }
00783 
00784     return 0;
00785 }
00786 
00787 
00788 /*!
00789    \brief Abstract operation for GAP buffers. 
00790           Receives functor F as a template argument
00791    \param dest - destination memory buffer.
00792    \param vect1 - operand 1 GAP encoded buffer.
00793    \param vect1_mask - XOR mask for starting bitflag for vector1 
00794    can be 0 or 1 (1 inverts the vector)
00795    \param vect2 - operand 2 GAP encoded buffer.
00796    \param vect2_mask - same as vect1_mask
00797    \param f - operation functor.
00798    \note Internal function.
00799 
00800    @ingroup gapfunc
00801 */
00802 template<typename T, class F> 
00803 void gap_buff_op(T*         BMRESTRICT dest, 
00804                  const T*   BMRESTRICT vect1,
00805                  unsigned   vect1_mask, 
00806                  const T*   BMRESTRICT vect2,
00807                  unsigned   vect2_mask, 
00808                  F f)
00809 {
00810     register const T*  cur1 = vect1;
00811     register const T*  cur2 = vect2;
00812 
00813     unsigned bitval1 = (*cur1++ & 1) ^ vect1_mask;
00814     unsigned bitval2 = (*cur2++ & 1) ^ vect2_mask;
00815     
00816     unsigned bitval = f(bitval1, bitval2);
00817     unsigned bitval_prev = bitval;
00818 
00819     register T* res = dest; 
00820     *res = bitval;
00821     ++res;
00822 
00823     while (1)
00824     {
00825         bitval = f(bitval1, bitval2);
00826 
00827         // Check if GAP value changes and we need to 
00828         // start the next one.
00829         if (bitval != bitval_prev)
00830         {
00831             ++res;
00832             bitval_prev = bitval;
00833         }
00834 
00835         if (*cur1 < *cur2)
00836         {
00837             *res = *cur1;
00838             ++cur1;
00839             bitval1 ^= 1;
00840         }
00841         else // >=
00842         {
00843             *res = *cur2;
00844             if (*cur2 < *cur1)
00845             {
00846                 bitval2 ^= 1;                
00847             }
00848             else  // equal
00849             {
00850                 if (*cur2 == (bm::gap_max_bits - 1))
00851                 {
00852                     break;
00853                 }
00854 
00855                 ++cur1;
00856                 bitval1 ^= 1;
00857                 bitval2 ^= 1;
00858             }
00859             ++cur2;
00860         }
00861 
00862     } // while
00863 
00864     unsigned dlen = (unsigned)(res - dest);
00865     *dest = (*dest & 7) + (dlen << 3);
00866 
00867 }
00868 
00869 /*!
00870    \brief Abstract distance test operation for GAP buffers. 
00871           Receives functor F as a template argument
00872    \param vect1 - operand 1 GAP encoded buffer.
00873    \param vect1_mask - XOR mask for starting bitflag for vector1 
00874                        can be 0 or 1 (1 inverts the vector)
00875    \param vect2 - operand 2 GAP encoded buffer.
00876    \param vect2_mask - same as vect1_mask
00877    \param f - operation functor.
00878    \note Internal function.
00879    \return non zero value if operation result returns any 1 bit 
00880 
00881    @ingroup gapfunc
00882 */
00883 template<typename T, class F> 
00884 unsigned gap_buff_any_op(const T*   BMRESTRICT vect1,
00885                          unsigned              vect1_mask, 
00886                          const T*   BMRESTRICT vect2,
00887                          unsigned              vect2_mask, 
00888                          F                     f)
00889 {
00890     register const T*  cur1 = vect1;
00891     register const T*  cur2 = vect2;
00892 
00893     unsigned bitval1 = (*cur1++ & 1) ^ vect1_mask;
00894     unsigned bitval2 = (*cur2++ & 1) ^ vect2_mask;
00895     
00896     unsigned bitval = f(bitval1, bitval2);
00897     if (bitval)
00898         return bitval;
00899     unsigned bitval_prev = bitval;
00900 
00901     while (1)
00902     {
00903         bitval = f(bitval1, bitval2);
00904         if (bitval)
00905             return bitval;
00906 
00907         if (bitval != bitval_prev)
00908             bitval_prev = bitval;
00909 
00910         if (*cur1 < *cur2)
00911         {
00912             ++cur1;
00913             bitval1 ^= 1;
00914         }
00915         else // >=
00916         {
00917             if (*cur2 < *cur1)
00918             {
00919                 bitval2 ^= 1;                
00920             }
00921             else  // equal
00922             {
00923                 if (*cur2 == (bm::gap_max_bits - 1))
00924                 {
00925                     break;
00926                 }
00927 
00928                 ++cur1;
00929                 bitval1 ^= 1;
00930                 bitval2 ^= 1;
00931             }
00932             ++cur2;
00933         }
00934 
00935     } // while
00936 
00937     return 0;
00938 }
00939 
00940 
00941 
00942 /*!
00943    \brief Abstract distance(similarity) operation for GAP buffers. 
00944           Receives functor F as a template argument
00945    \param vect1 - operand 1 GAP encoded buffer.
00946    \param vect2 - operand 2 GAP encoded buffer.
00947    \param f - operation functor.
00948    \note Internal function.
00949 
00950    @ingroup gapfunc
00951 */
00952 /*
00953 template<typename T, class F> 
00954 unsigned gap_buff_count_op(const T*  vect1, const T*  vect2, F f)
00955 {
00956     register const T* cur1 = vect1;
00957     register const T* cur2 = vect2;
00958 
00959     unsigned bitval1 = (*cur1++ & 1);
00960     unsigned bitval2 = (*cur2++ & 1);
00961     unsigned bitval = f(bitval1, bitval2);
00962     unsigned bitval_prev = bitval;
00963 
00964     unsigned count = 0;
00965     T res;
00966     T res_prev;
00967 
00968     while (1)
00969     {
00970         bitval = f(bitval1, bitval2);
00971 
00972         // Check if GAP value changes and we need to 
00973         // start the next one.
00974         if (bitval != bitval_prev)
00975         {
00976             bitval_prev = bitval;
00977         }
00978 
00979         if (*cur1 < *cur2)
00980         {
00981             if (bitval)
00982                 count += *cur1; 
00983             ++cur1;
00984             bitval1 ^= 1;
00985         }
00986         else // >=
00987         {
00988             if (bitval)
00989                 count += *cur2; 
00990             if (*cur2 < *cur1)
00991             {
00992                 bitval2 ^= 1;                
00993             }
00994             else  // equal
00995             {
00996                 if (*cur2 == (bm::gap_max_bits - 1))
00997                 {
00998                     break;
00999                 }
01000 
01001                 ++cur1;
01002                 bitval1 ^= 1;
01003                 bitval2 ^= 1;
01004             }
01005             ++cur2;
01006         }
01007 
01008     } // while
01009 
01010     return count;
01011 }
01012 */
01013 
01014 
01015 /*!
01016    \brief Sets or clears bit in the GAP buffer.
01017 
01018    \param val - new bit value
01019    \param buf - GAP buffer.
01020    \param pos - Index of bit to set.
01021    \param is_set - (OUT) flag if bit was actually set.
01022 
01023    \return New GAP buffer length. 
01024 
01025    @ingroup gapfunc
01026 */
01027 template<typename T> unsigned gap_set_value(unsigned val, 
01028                                             T* BMRESTRICT buf, 
01029                                             unsigned pos, 
01030                                             unsigned* BMRESTRICT is_set)
01031 {
01032     BM_ASSERT(pos < bm::gap_max_bits);
01033     unsigned curr = gap_bfind(buf, pos, is_set);
01034 
01035     register T end = (*buf >> 3);
01036     if (*is_set == val)
01037     {
01038         *is_set = 0;
01039         return end;
01040     }
01041     *is_set = 1;
01042 
01043     register T* pcurr = buf + curr;
01044     register T* pprev = pcurr - 1;
01045     register T* pend = buf + end;
01046 
01047     // Special case, first bit GAP operation. There is no platform beside it.
01048     // initial flag must be inverted.
01049     if (pos == 0)
01050     {
01051         *buf ^= 1;
01052         if ( buf[1] ) // We need to insert a 1 bit platform here.
01053         {
01054             ::memmove(&buf[2], &buf[1], (end - 1) * sizeof(gap_word_t));
01055             buf[1] = 0;
01056             ++end;
01057         }
01058         else // Only 1 bit in the GAP. We need to delete the first GAP.
01059         {
01060             pprev = buf + 1;
01061             pcurr = pprev + 1;
01062             do
01063             {
01064                 *pprev++ = *pcurr++;
01065             } while (pcurr < pend);
01066             --end;
01067         }
01068     }
01069     else if (curr > 1 && ((unsigned)(*pprev))+1 == pos) // Left border bit
01070     {
01071        ++(*pprev);
01072        if (*pprev == *pcurr)  // Curr. GAP to be merged with prev.GAP.
01073        {
01074             --end;
01075             if (pcurr != pend) // GAP merge: 2 GAPS to be deleted 
01076             {
01077                 --end;
01078                 ++pcurr;
01079                 do
01080                 {
01081                     *pprev++ = *pcurr++;
01082                 } while (pcurr < pend);
01083             }
01084        }    
01085     }
01086     else if (*pcurr == pos) // Rightmost bit in the GAP. Border goes left.
01087     {
01088         --(*pcurr);       
01089         if (pcurr == pend)
01090         {
01091            ++end;
01092         }
01093     }
01094     else  // Worst case we need to split current block.
01095     {
01096         ::memmove(pcurr+2, pcurr,(end - curr + 1)*sizeof(T));
01097         *pcurr++ = pos - 1;
01098         *pcurr = pos;
01099         end+=2;
01100     }
01101 
01102     // Set correct length word.
01103     *buf = (*buf & 7) + (end << 3);
01104 
01105     buf[end] = bm::gap_max_bits - 1;
01106     return end;
01107 }
01108 
01109 //------------------------------------------------------------------------
01110 
01111 /**
01112     \brief Searches for the next 1 bit in the GAP block
01113     \param buf - GAP buffer
01114     \param nbit - bit index to start checking from.
01115     \param prev - returns previously checked value
01116 
01117     @ingroup gapfunc
01118 */
01119 template<typename T> int gap_find_in_block(const T* buf, 
01120                                            unsigned nbit, 
01121                                            bm::id_t* prev)
01122 {
01123     BM_ASSERT(nbit < bm::gap_max_bits);
01124 
01125     unsigned bitval;
01126     unsigned gap_idx = bm::gap_bfind(buf, nbit, &bitval);
01127 
01128     if (bitval) // positive block.
01129     {
01130        return 1;
01131     }
01132 
01133     register unsigned val = buf[gap_idx] + 1;
01134     *prev += val - nbit;
01135  
01136     return (val != bm::gap_max_bits);  // no bug here.
01137 }
01138 
01139 
01140 
01141 /*! 
01142    \brief Sets bits to 1 in the bitblock.
01143    \param dest - Bitset buffer.
01144    \param bitpos - Offset of the start bit.
01145    \param bitcount - number of bits to set.
01146 
01147    @ingroup bitfunc
01148 */  
01149 inline void or_bit_block(unsigned* dest, 
01150                          unsigned bitpos, 
01151                          unsigned bitcount)
01152 {
01153     unsigned nbit  = unsigned(bitpos & bm::set_block_mask); 
01154     unsigned nword = unsigned(nbit >> bm::set_word_shift); 
01155     nbit &= bm::set_word_mask;
01156 
01157     bm::word_t* word = dest + nword;
01158 
01159     if (bitcount == 1)  // special case (only 1 bit to set)
01160     {
01161         *word |= unsigned(1 << nbit);
01162         return;
01163     }
01164 
01165     if (nbit) // starting position is not aligned
01166     {
01167         unsigned right_margin = nbit + bitcount;
01168 
01169         // here we checking if we setting bits only in the current
01170         // word. Example: 00111000000000000000000000000000 (32 bits word)
01171 
01172         if (right_margin < 32) 
01173         {
01174             unsigned mask = 
01175                 block_set_table<true>::_right[nbit] & 
01176                 block_set_table<true>::_left[right_margin-1];
01177             *word |= mask;
01178             return; // we are done
01179         }
01180         else
01181         {
01182             *word |= block_set_table<true>::_right[nbit];
01183             bitcount -= 32 - nbit;
01184         }
01185         ++word;
01186     }
01187 
01188     // now we are word aligned, lets find out how many words we 
01189     // can now turn ON using loop
01190 
01191     for ( ;bitcount >= 32; bitcount -= 32) 
01192     {
01193         *word++ = 0xffffffff;
01194     }
01195 
01196     if (bitcount) 
01197     {
01198         *word |= block_set_table<true>::_left[bitcount-1];
01199     }
01200 }
01201 
01202 
01203 /*! 
01204    \brief SUB (AND NOT) bit interval to 1 in the bitblock.
01205    \param dest - Bitset buffer.
01206    \param bitpos - Offset of the start bit.
01207    \param bitcount - number of bits to set.
01208 
01209    @ingroup bitfunc
01210 */  
01211 inline void sub_bit_block(unsigned* dest, 
01212                           unsigned bitpos, 
01213                           unsigned bitcount)
01214 {
01215     unsigned nbit  = unsigned(bitpos & bm::set_block_mask); 
01216     unsigned nword = unsigned(nbit >> bm::set_word_shift); 
01217     nbit &= bm::set_word_mask;
01218 
01219     bm::word_t* word = dest + nword;
01220 
01221     if (bitcount == 1)  // special case (only 1 bit to set)
01222     {
01223         *word &= ~unsigned(1 << nbit);
01224         return;
01225     }
01226 
01227     if (nbit) // starting position is not aligned
01228     {
01229         unsigned right_margin = nbit + bitcount;
01230 
01231         // here we checking if we setting bits only in the current
01232         // word. Example: 00111000000000000000000000000000 (32 bits word)
01233 
01234         if (right_margin < 32) 
01235         {
01236             unsigned mask = 
01237                 block_set_table<true>::_right[nbit] & 
01238                 block_set_table<true>::_left[right_margin-1];
01239             *word &= ~mask;
01240             return; // we are done
01241         }
01242         else
01243         {
01244             *word &= ~block_set_table<true>::_right[nbit];
01245             bitcount -= 32 - nbit;
01246         }
01247         ++word;
01248     }
01249 
01250     // now we are word aligned, lets find out how many words we 
01251     // can now turn ON using loop
01252 
01253     for ( ;bitcount >= 32; bitcount -= 32) 
01254     {
01255         *word++ = 0;
01256     }
01257 
01258     if (bitcount) 
01259     {
01260         *word &= ~block_set_table<true>::_left[bitcount-1];
01261     }
01262 }
01263 
01264 
01265 /*! 
01266    \brief XOR bit interval to 1 in the bitblock.
01267    \param dest - Bitset buffer.
01268    \param bitpos - Offset of the start bit.
01269    \param bitcount - number of bits to set.
01270 
01271    @ingroup bitfunc
01272 */  
01273 inline void xor_bit_block(unsigned* dest, 
01274                           unsigned bitpos, 
01275                           unsigned bitcount)
01276 {
01277     unsigned nbit  = unsigned(bitpos & bm::set_block_mask); 
01278     unsigned nword = unsigned(nbit >> bm::set_word_shift); 
01279     nbit &= bm::set_word_mask;
01280 
01281     bm::word_t* word = dest + nword;
01282 
01283     if (bitcount == 1)  // special case (only 1 bit to set)
01284     {
01285         *word ^= unsigned(1 << nbit);
01286         return;
01287     }
01288 
01289     if (nbit) // starting position is not aligned
01290     {
01291         unsigned right_margin = nbit + bitcount;
01292 
01293         // here we checking if we setting bits only in the current
01294         // word. Example: 00111000000000000000000000000000 (32 bits word)
01295 
01296         if (right_margin < 32) 
01297         {
01298             unsigned mask = 
01299                 block_set_table<true>::_right[nbit] & 
01300                 block_set_table<true>::_left[right_margin-1];
01301             *word ^= mask;
01302             return; // we are done
01303         }
01304         else
01305         {
01306             *word ^= block_set_table<true>::_right[nbit];
01307             bitcount -= 32 - nbit;
01308         }
01309         ++word;
01310     }
01311 
01312     // now we are word aligned, lets find out how many words we 
01313     // can now turn ON using loop
01314 
01315     for ( ;bitcount >= 32; bitcount -= 32) 
01316     {
01317         *word++ ^= 0xffffffff;
01318     }
01319 
01320     if (bitcount) 
01321     {
01322         *word ^= block_set_table<true>::_left[bitcount-1];
01323     }
01324 }
01325 
01326 
01327 /*!
01328    \brief SUB (AND NOT) GAP block to bitblock.
01329    \param dest - bitblock buffer pointer.
01330    \param buf  - GAP buffer pointer.
01331 
01332    @ingroup gapfunc
01333 */
01334 template<typename T> 
01335 void gap_sub_to_bitset(unsigned* dest, const T*  buf)
01336 {
01337     register const T* pcurr = buf;    
01338     register const T* pend = pcurr + (*pcurr >> 3);
01339     ++pcurr;
01340 
01341     if (*buf & 1)  // Starts with 1
01342     {
01343         sub_bit_block(dest, 0, *pcurr + 1);
01344         ++pcurr;
01345     }
01346     ++pcurr; // now we are in GAP "1" again
01347 
01348     while (pcurr <= pend)
01349     {
01350         unsigned bitpos = *(pcurr-1) + 1;
01351         BM_ASSERT(*pcurr > *(pcurr-1));
01352         unsigned gap_len = *pcurr - *(pcurr-1);
01353         sub_bit_block(dest, bitpos, gap_len);
01354         pcurr += 2;
01355     }
01356 }
01357 
01358 
01359 /*!
01360    \brief XOR GAP block to bitblock.
01361    \param dest - bitblock buffer pointer.
01362    \param buf  - GAP buffer pointer.
01363 
01364    @ingroup gapfunc
01365 */
01366 template<typename T> 
01367 void gap_xor_to_bitset(unsigned* dest, const T*  buf)
01368 {
01369     register const T* pcurr = buf;    
01370     register const T* pend = pcurr + (*pcurr >> 3);
01371     ++pcurr;
01372 
01373     if (*buf & 1)  // Starts with 1
01374     {
01375         xor_bit_block(dest, 0, *pcurr + 1);
01376         ++pcurr;
01377     }
01378     ++pcurr; // now we are in GAP "1" again
01379 
01380     while (pcurr <= pend)
01381     {
01382         unsigned bitpos = *(pcurr-1) + 1;
01383         BM_ASSERT(*pcurr > *(pcurr-1));
01384         unsigned gap_len = *pcurr - *(pcurr-1);
01385         xor_bit_block(dest, bitpos, gap_len);
01386         pcurr += 2;
01387     }
01388 }
01389 
01390 
01391 /*!
01392    \brief Adds(OR) GAP block to bitblock.
01393    \param dest - bitblock buffer pointer.
01394    \param buf  - GAP buffer pointer.
01395 
01396    @ingroup gapfunc
01397 */
01398 template<typename T> 
01399 void gap_add_to_bitset(unsigned* dest, const T*  buf)
01400 {
01401     register const T* pcurr = buf;    
01402     register const T* pend = pcurr + (*pcurr >> 3);
01403     ++pcurr;
01404 
01405     if (*buf & 1)  // Starts with 1
01406     {
01407         or_bit_block(dest, 0, *pcurr + 1);
01408         ++pcurr;
01409     }
01410     ++pcurr; // now we are in GAP "1" again
01411 
01412     while (pcurr <= pend)
01413     {
01414         unsigned bitpos = *(pcurr-1) + 1;
01415         BM_ASSERT(*pcurr > *(pcurr-1));
01416         unsigned gap_len = *pcurr - *(pcurr-1);
01417         or_bit_block(dest, bitpos, gap_len);
01418         pcurr += 2;
01419     }
01420 }
01421 
01422 
01423 /*!
01424    \brief ANDs GAP block to bitblock.
01425    \param dest - bitblock buffer pointer.
01426    \param buf  - GAP buffer pointer.
01427 
01428    @ingroup gapfunc
01429 */
01430 template<typename T> 
01431 void gap_and_to_bitset(unsigned* dest, const T*  buf)
01432 {
01433     register const T* pcurr = buf;    
01434     register const T* pend = pcurr + (*pcurr >> 3);
01435     ++pcurr;
01436 
01437     if (! (*buf & 1) )  // Starts with 0 
01438     {
01439         // Instead of AND we can SUB 0 gaps here 
01440         sub_bit_block(dest, 0, *pcurr + 1);
01441         ++pcurr;
01442     }
01443     ++pcurr; // now we are in GAP "0" again
01444 
01445     while (pcurr <= pend)
01446     {
01447         unsigned bitpos = *(pcurr-1) + 1;
01448         BM_ASSERT(*pcurr > *(pcurr-1));
01449         unsigned gap_len = *pcurr - *(pcurr-1);
01450         sub_bit_block(dest, bitpos, gap_len);
01451         pcurr += 2;
01452     }
01453 }
01454 
01455 
01456 /*!
01457    \brief Compute bitcount of bit block AND masked by GAP block.
01458    \param dest - bitblock buffer pointer.
01459    \param buf  - GAP buffer pointer.
01460 
01461    @ingroup gapfunc bitfunc
01462 */
01463 template<typename T> 
01464 bm::id_t gap_bitset_and_count(const unsigned* block, const T*  buf)
01465 {
01466     BM_ASSERT(block);
01467 
01468     register const T* pcurr = buf;    
01469     register const T* pend = pcurr + (*pcurr >> 3);
01470     ++pcurr;
01471 
01472     bm::id_t count = 0;
01473 
01474     if (*buf & 1)  // Starts with 1
01475     {
01476         count += bit_block_calc_count_range(block, 0, *pcurr);
01477         ++pcurr;
01478     }
01479     ++pcurr; // now we are in GAP "1" again
01480 
01481     while (pcurr <= pend)
01482     {
01483         bm::id_t c = bit_block_calc_count_range(block, *(pcurr-1)+1, *pcurr);
01484 
01485         count += c;
01486         pcurr += 2;
01487     }
01488     return count;
01489 }
01490 
01491 
01492 /*!
01493    \brief Bitcount test of bit block AND masked by GAP block.
01494    \param dest - bitblock buffer pointer.
01495    \param buf  - GAP buffer pointer.
01496 
01497    @ingroup gapfunc bitfunc
01498 */
01499 template<typename T> 
01500 bm::id_t gap_bitset_and_any(const unsigned* block, const T*  buf)
01501 {
01502     BM_ASSERT(block);
01503 
01504     register const T* pcurr = buf;    
01505     register const T* pend = pcurr + (*pcurr >> 3);
01506     ++pcurr;
01507 
01508     bm::id_t count = 0;
01509     if (*buf & 1)  // Starts with 1
01510     {
01511         count += bit_block_any_range(block, 0, *pcurr);
01512         if (count)
01513             return count;
01514         ++pcurr;
01515     }
01516     ++pcurr; // now we are in GAP "1" again
01517 
01518     while (pcurr <= pend)
01519     {
01520         bm::id_t c = bit_block_any_range(block, *(pcurr-1)+1, *pcurr);
01521         count += c;
01522         if (count)
01523             break;
01524         pcurr += 2;
01525     }
01526     return count;
01527 }
01528 
01529 
01530 
01531 /*!
01532    \brief Compute bitcount of bit block SUB masked by GAP block.
01533    \param dest - bitblock buffer pointer.
01534    \param buf  - GAP buffer pointer.
01535 
01536    @ingroup gapfunc bitfunc
01537 */
01538 template<typename T> 
01539 bm::id_t gap_bitset_sub_count(const unsigned* block, const T*  buf)
01540 {
01541     BM_ASSERT(block);
01542 
01543     register const T* pcurr = buf;    
01544     register const T* pend = pcurr + (*pcurr >> 3);
01545     ++pcurr;
01546 
01547     bm::id_t count = 0;
01548 
01549     if (!(*buf & 1))  // Starts with 0
01550     {
01551         count += bit_block_calc_count_range(block, 0, *pcurr);
01552         ++pcurr;
01553     }
01554     ++pcurr; // now we are in GAP "0" again
01555 
01556     for (;pcurr <= pend; pcurr+=2)
01557     {
01558         count += bit_block_calc_count_range(block, *(pcurr-1)+1, *pcurr);
01559     }
01560     return count;
01561 }
01562 
01563 
01564 /*!
01565    \brief Compute bitcount test of bit block SUB masked by GAP block.
01566    \param dest - bitblock buffer pointer.
01567    \param buf  - GAP buffer pointer.
01568 
01569    @ingroup gapfunc bitfunc
01570 */
01571 template<typename T> 
01572 bm::id_t gap_bitset_sub_any(const unsigned* block, const T*  buf)
01573 {
01574     BM_ASSERT(block);
01575 
01576     register const T* pcurr = buf;    
01577     register const T* pend = pcurr + (*pcurr >> 3);
01578     ++pcurr;
01579 
01580     bm::id_t count = 0;
01581 
01582     if (!(*buf & 1))  // Starts with 0
01583     {
01584         count += bit_block_any_range(block, 0, *pcurr);
01585         if (count)
01586             return count;
01587         ++pcurr;
01588     }
01589     ++pcurr; // now we are in GAP "0" again
01590 
01591     for (;pcurr <= pend; pcurr+=2)
01592     {
01593         count += bit_block_any_range(block, *(pcurr-1)+1, *pcurr);
01594         if (count)
01595             return count;
01596     }
01597     return count;
01598 }
01599 
01600 
01601 
01602 /*!
01603    \brief Compute bitcount of bit block XOR masked by GAP block.
01604    \param dest - bitblock buffer pointer.
01605    \param buf  - GAP buffer pointer.
01606 
01607    @ingroup gapfunc bitfunc
01608 */
01609 template<typename T> 
01610 bm::id_t gap_bitset_xor_count(const unsigned* block, const T*  buf)
01611 {
01612     BM_ASSERT(block);
01613 
01614     register const T* pcurr = buf;    
01615     register const T* pend = pcurr + (*pcurr >> 3);
01616     ++pcurr;
01617 
01618     unsigned bitval = *buf & 1;
01619     
01620     register bm::id_t count = bit_block_calc_count_range(block, 0, *pcurr);
01621     if (bitval)
01622     {
01623         count = *pcurr + 1 - count;
01624     }
01625     
01626     for (bitval^=1, ++pcurr; pcurr <= pend; bitval^=1, ++pcurr)
01627     {
01628         T prev = *(pcurr-1)+1;
01629         bm::id_t c = bit_block_calc_count_range(block, prev, *pcurr);
01630         
01631         if (bitval) // 1 gap; means Result = Total_Bits - BitCount;
01632         {
01633             c = (*pcurr - prev + 1) - c;
01634         }
01635         
01636         count += c;
01637     }
01638     return count;
01639 }
01640 
01641 /*!
01642    \brief Compute bitcount test of bit block XOR masked by GAP block.
01643    \param dest - bitblock buffer pointer.
01644    \param buf  - GAP buffer pointer.
01645 
01646    @ingroup gapfunc bitfunc
01647 */
01648 template<typename T> 
01649 bm::id_t gap_bitset_xor_any(const unsigned* block, const T*  buf)
01650 {
01651     BM_ASSERT(block);
01652 
01653     register const T* pcurr = buf;    
01654     register const T* pend = pcurr + (*pcurr >> 3);
01655     ++pcurr;
01656 
01657     unsigned bitval = *buf & 1;
01658     
01659     register bm::id_t count = bit_block_any_range(block, 0, *pcurr);
01660     if (bitval)
01661     {
01662         count = *pcurr + 1 - count;
01663     }
01664     
01665     for (bitval^=1, ++pcurr; pcurr <= pend; bitval^=1, ++pcurr)
01666     {
01667         T prev = *(pcurr-1)+1;
01668         bm::id_t c = bit_block_any_range(block, prev, *pcurr);
01669         
01670         if (bitval) // 1 gap; means Result = Total_Bits - BitCount;
01671         {
01672             c = (*pcurr - prev + 1) - c;
01673         }
01674         
01675         count += c;
01676         if (count)
01677             return count;
01678     }
01679     return count;
01680 }
01681 
01682 
01683 
01684 /*!
01685    \brief Compute bitcount of bit block OR masked by GAP block.
01686    \param dest - bitblock buffer pointer.
01687    \param buf  - GAP buffer pointer.
01688 
01689    @ingroup gapfunc bitfunc
01690 */
01691 template<typename T> 
01692 bm::id_t gap_bitset_or_count(const unsigned* block, const T*  buf)
01693 {
01694     BM_ASSERT(block);
01695 
01696     register const T* pcurr = buf;    
01697     register const T* pend = pcurr + (*pcurr >> 3);
01698     ++pcurr;
01699 
01700     unsigned bitval = *buf & 1;
01701     
01702     register bm::id_t count;
01703     if (bitval)
01704     {
01705         count = *pcurr + 1;
01706     } 
01707     else
01708     {
01709         count = bit_block_calc_count_range(block, 0, *pcurr);
01710     }
01711     
01712     for (bitval^=1, ++pcurr; pcurr <= pend; bitval^=1, ++pcurr)
01713     {
01714         T prev = *(pcurr-1)+1;
01715         bm::id_t c;
01716         
01717         if (bitval)
01718         {
01719             c = (*pcurr - prev + 1);
01720         }
01721         else
01722         {
01723             c = bit_block_calc_count_range(block, prev, *pcurr);
01724         }
01725         
01726         count += c;
01727     }
01728     return count;
01729 }
01730 
01731 /*!
01732    \brief Compute bitcount test of bit block OR masked by GAP block.
01733    \param dest - bitblock buffer pointer.
01734    \param buf  - GAP buffer pointer.
01735 
01736    @ingroup gapfunc bitfunc
01737 */
01738 template<typename T> 
01739 bm::id_t gap_bitset_or_any(const unsigned* block, const T*  buf)
01740 {
01741     BM_ASSERT(block);
01742 
01743     register const T* pcurr = buf;    
01744     register const T* pend = pcurr + (*pcurr >> 3);
01745     ++pcurr;
01746 
01747     unsigned bitval = *buf & 1;
01748     
01749     register bm::id_t count;
01750     if (bitval)
01751     {
01752         count = *pcurr + 1;
01753     } 
01754     else
01755     {
01756         count = bit_block_any_range(block, 0, *pcurr);
01757     }
01758     
01759     for (bitval^=1, ++pcurr; pcurr <= pend; bitval^=1, ++pcurr)
01760     {
01761         T prev = *(pcurr-1)+1;
01762         bm::id_t c;
01763         
01764         if (bitval)
01765         {
01766             c = (*pcurr - prev + 1);
01767         }
01768         else
01769         {
01770             c = bit_block_any_range(block, prev, *pcurr);
01771         }        
01772         count += c;
01773         if (count)
01774             return count;
01775     }
01776     return count;
01777 }
01778 
01779 
01780 
01781 /*!
01782    \brief Bitblock memset operation. 
01783 
01784    \param dst - destination block.
01785    \param value - value to set.
01786 
01787    @ingroup bitfunc
01788 */
01789 inline 
01790 void bit_block_set(bm::word_t* BMRESTRICT dst, bm::word_t value)
01791 {
01792 //#ifdef BMVECTOPT
01793 //    VECT_SET_BLOCK(dst, dst + bm::set_block_size, value);
01794 //#else
01795     ::memset(dst, value, bm::set_block_size * sizeof(bm::word_t));
01796 //#endif
01797 }
01798 
01799 
01800 /*!
01801    \brief GAP block to bitblock conversion.
01802    \param dest - bitblock buffer pointer.
01803    \param buf  - GAP buffer pointer.
01804 
01805    @ingroup gapfunc
01806 */
01807 template<typename T> 
01808 void gap_convert_to_bitset(unsigned* dest, const T*  buf)
01809 {
01810     bit_block_set(dest, 0);
01811     gap_add_to_bitset(dest, buf);
01812 }
01813 
01814 
01815 /*!
01816    \brief GAP block to bitblock conversion.
01817    \param dest - bitblock buffer pointer.
01818    \param buf  - GAP buffer pointer.
01819    \param dest_size - length of the destination buffer.
01820 
01821    @ingroup gapfunc
01822 */
01823 template<typename T> 
01824 void gap_convert_to_bitset(unsigned* dest, const T*  buf,  unsigned  dest_len)
01825 {
01826    ::memset(dest, 0, dest_len * sizeof(unsigned));
01827     gap_add_to_bitset(dest, buf);
01828 }
01829 
01830 
01831 
01832 /*!
01833    \brief Smart GAP block to bitblock conversion.
01834 
01835     Checks if GAP block is ALL-ZERO or ALL-ON. In those cases returns 
01836     pointer on special static bitblocks.
01837 
01838    \param dest - bitblock buffer pointer.
01839    \param buf  - GAP buffer pointer.
01840    \param set_max - max possible bitset length
01841 
01842    @ingroup gapfunc
01843 */
01844 template<typename T> 
01845         unsigned* gap_convert_to_bitset_smart(unsigned* dest,
01846                                               const T* buf, 
01847                                               id_t set_max)
01848 {
01849     if (buf[1] == set_max - 1)
01850     {
01851         return (buf[0] & 1) ? FULL_BLOCK_ADDR : 0;
01852     }
01853 
01854     gap_convert_to_bitset(dest, buf);
01855     return dest;
01856 }
01857 
01858 
01859 /*!
01860    \brief Calculates sum of all words in GAP block. (For debugging purposes)
01861    \note For debugging and testing ONLY.
01862    \param buf - GAP buffer pointer.
01863    \return Sum of all words.
01864 
01865    @ingroup gapfunc
01866 */
01867 template<typename T> unsigned gap_control_sum(const T* buf)
01868 {
01869     unsigned end = *buf >> 3;
01870 
01871     register const T* pcurr = buf;    
01872     register const T* pend = pcurr + (*pcurr >> 3);
01873     ++pcurr;
01874 
01875     if (*buf & 1)  // Starts with 1
01876     {
01877         ++pcurr;
01878     }
01879     ++pcurr; // now we are in GAP "1" again
01880 
01881     while (pcurr <= pend)
01882     {
01883         BM_ASSERT(*pcurr > *(pcurr-1));
01884         pcurr += 2;
01885     }
01886     return buf[end];
01887 
01888 }
01889 
01890 
01891 /*! 
01892    \brief Sets all bits to 0 or 1 (GAP)
01893    \param buf - GAP buffer pointer.
01894    \param set_max - max possible bitset length
01895 
01896    @ingroup gapfunc
01897 */
01898 template<class T> void gap_set_all(T* buf, 
01899                                         unsigned set_max,
01900                                         unsigned value)
01901 {
01902     BM_ASSERT(value == 0 || value == 1);
01903     *buf = (*buf & 6u) + (1u << 3) + value;
01904     *(++buf) = set_max - 1;
01905 }
01906 
01907 
01908 /*!
01909     \brief Init gap block so it has block in it (can be whole block)
01910     \param buf  - GAP buffer pointer.
01911     \param from - one block start
01912     \param to   - one block end
01913     \param value - (block value)1 or 0
01914     \param set_max - max possible bitset length
01915     
01916    @ingroup gapfunc
01917 */
01918 template<class T> 
01919 void gap_init_range_block(T*       buf,
01920                           unsigned from,
01921                           unsigned to,
01922                           unsigned value,
01923                           unsigned set_max)
01924 {
01925     BM_ASSERT(value == 0 || value == 1);
01926 
01927     unsigned gap_len;
01928     if (from == 0)
01929     {
01930         if (to == set_max - 1)
01931         {
01932             gap_set_all(buf, set_max, value);
01933         }
01934         else
01935         {
01936             gap_len = 2;
01937             buf[1] = to;
01938             buf[2] = set_max - 1;
01939             buf[0] =  (*buf & 6u) + (gap_len << 3) + value;
01940         }
01941         return;
01942     }
01943     // from != 0
01944 
01945     value = !value;
01946     if (to == set_max - 1)
01947     {
01948         gap_len = 2;
01949         buf[1] = from - 1;
01950         buf[2] = set_max - 1;
01951     }
01952     else
01953     {
01954         gap_len = 3;
01955         buf[1] = from - 1;
01956         buf[2] = to;
01957         buf[3] = set_max - 1;
01958     }
01959     buf[0] =  (*buf & 6u) + (gap_len << 3) + value;
01960 }
01961 
01962 
01963 /*! 
01964    \brief Inverts all bits in the GAP buffer.
01965    \param buf - GAP buffer pointer.
01966 
01967    @ingroup gapfunc
01968 */
01969 template<typename T> void gap_invert(T* buf)
01970 { 
01971     *buf ^= 1;
01972 }
01973 
01974 /*! 
01975    \brief Temporary inverts all bits in the GAP buffer.
01976    
01977    In this function const-ness of the buffer means nothing.
01978    Calling this function again restores the status of the buffer.
01979 
01980    \param buf - GAP buffer pointer. (Buffer IS changed) 
01981 
01982    @ingroup gapfunc
01983 */
01984 /*
01985 template<typename T> void gap_temp_invert(const T* buf)
01986 {
01987     T* buftmp = const_cast<T*>(buf);
01988     *buftmp ^= 1;
01989 }
01990 */
01991 
01992 /*!
01993    \brief Checks if GAP block is all-zero.
01994    \param buf - GAP buffer pointer.
01995    \param set_max - max possible bitset length
01996    \returns true if all-zero.
01997 
01998    @ingroup gapfunc
01999 */
02000 template<typename T> 
02001              bool gap_is_all_zero(const T* buf, unsigned set_max)
02002 {
02003     return (((*buf & 1)==0)  && (*(++buf) == set_max - 1));
02004 }
02005 
02006 /*!
02007    \brief Checks if GAP block is all-one.
02008    \param buf - GAP buffer pointer.
02009    \param set_max - max possible bitset length
02010    \returns true if all-one.
02011 
02012    @ingroup gapfunc
02013 */
02014 template<typename T> 
02015          bool gap_is_all_one(const T* buf, unsigned set_max)
02016 {
02017     return ((*buf & 1)  && (*(++buf) == set_max - 1));
02018 }
02019 
02020 /*!
02021    \brief Returs GAP block length.
02022    \param buf - GAP buffer pointer.
02023    \returns GAP block length.
02024 
02025    @ingroup gapfunc
02026 */
02027 template<typename T> unsigned gap_length(const T* buf)
02028 {
02029     return (*buf >> 3) + 1;
02030 }
02031 
02032 
02033 /*!
02034    \brief Returs GAP block capacity.
02035    \param buf - GAP buffer pointer.
02036    \returns GAP block capacity.
02037 
02038    @ingroup gapfunc
02039 */
02040 template<typename T> 
02041 unsigned gap_capacity(const T* buf, const T* glevel_len)
02042 {
02043     return glevel_len[(*buf >> 1) & 3];
02044 }
02045 
02046 
02047 /*!
02048    \brief Returs GAP block capacity limit.
02049    \param buf - GAP buffer pointer.
02050    \param glevel_len - GAP lengths table (gap_len_table)
02051    \returns GAP block limit.
02052 
02053    @ingroup gapfunc
02054 */
02055 template<typename T> 
02056 unsigned gap_limit(const T* buf, const T* glevel_len)
02057 {
02058     return glevel_len[(*buf >> 1) & 3]-4;
02059 }
02060 
02061 
02062 /*!
02063    \brief Returs GAP blocks capacity level.
02064    \param buf - GAP buffer pointer.
02065    \returns GAP block capacity level.
02066 
02067    @ingroup gapfunc
02068 */
02069 template<typename T> unsigned gap_level(const T* buf)
02070 {
02071     return (*buf >> 1) & 3;
02072 }
02073 
02074 
02075 /*!
02076    \brief Sets GAP block capacity level.
02077    \param buf - GAP buffer pointer.
02078    \param level new GAP block capacity level.
02079 
02080    @ingroup gapfunc
02081 */
02082 template<typename T> void set_gap_level(T* buf, 
02083                                         unsigned level)
02084 {
02085     BM_ASSERT(level < bm::gap_levels);
02086     *buf = ((level & 3) << 1) | (*buf & 1) | (*buf & ~7); 
02087 }
02088 
02089 
02090 /*!
02091    \brief Calculates GAP block capacity level.
02092    \param len - GAP buffer length.
02093    \param glevel_len - GAP lengths table
02094    \return GAP block capacity level. 
02095             -1 if block does not fit any level.
02096    @ingroup gapfunc
02097 */
02098 template<typename T>
02099 inline int gap_calc_level(int len, const T* glevel_len)
02100 {
02101     if (len <= (glevel_len[0]-4)) return 0;
02102     if (len <= (glevel_len[1]-4)) return 1;
02103     if (len <= (glevel_len[2]-4)) return 2;
02104     if (len <= (glevel_len[3]-4)) return 3;
02105 
02106     BM_ASSERT(bm::gap_levels == 4);
02107     return -1;
02108 }
02109 
02110 /*! @brief Returns number of free elements in GAP block array. 
02111     Difference between GAP block capacity on this level and actual GAP length.
02112     
02113     @param buf - GAP buffer pointer
02114     @parma glevel_len - GAP lengths table
02115     
02116     @return Number of free GAP elements
02117     @ingroup gapfunc
02118 */
02119 template<typename T>
02120 inline unsigned gap_free_elements(const T* buf, const T* glevel_len)
02121 {
02122     unsigned len = gap_length(buf);
02123     unsigned capacity = gap_capacity(buf, glevel_len);
02124     return capacity - len;
02125 }
02126 
02127 
02128 /*! 
02129    \brief Lexicographical comparison of BIT buffers.
02130    \param buf1 - First buffer pointer.
02131    \param buf2 - Second buffer pointer.
02132    \param len - Buffer length in elements (T).
02133    \return  <0 - less, =0 - equal,  >0 - greater.
02134 
02135    @ingroup bitfunc 
02136 */
02137 template<typename T> 
02138 int bitcmp(const T* buf1, const T* buf2, unsigned len)
02139 {
02140     BM_ASSERT(len);
02141 
02142     const T* pend1 = buf1 + len; 
02143     do
02144     {
02145         T w1 = *buf1++;
02146         T w2 = *buf2++;
02147         T diff = w1 ^ w2;
02148     
02149         if (diff)
02150         { 
02151             return (w1 & diff & -diff) ? 1 : -1;
02152         }
02153 
02154     } while (buf1 < pend1);
02155 
02156     return 0;
02157 }
02158 
02159 
02160 /*! 
02161    \brief Converts bit block to GAP. 
02162    \param dest - Destinatio GAP buffer.
02163    \param src - Source bitblock buffer.
02164    \param bits - Number of bits to convert.
02165    \param dest_len - length of the dest. buffer.
02166    \return  New ength of GAP block or 0 if conversion failed 
02167    (insufficicent space).
02168 
02169    @ingroup gapfunc
02170 */
02171 template<typename T> 
02172     unsigned bit_convert_to_gap(T* BMRESTRICT dest, 
02173                                 const unsigned* BMRESTRICT src, 
02174                                 bm::id_t bits, 
02175                                 unsigned dest_len)
02176 {
02177     register T* BMRESTRICT pcurr = dest;
02178     T* BMRESTRICT end = dest + dest_len; 
02179     register int bitval = (*src) & 1;
02180     *pcurr |= bitval;
02181 
02182     ++pcurr;
02183     *pcurr = 0;
02184     register unsigned bit_idx = 0;
02185     register int bitval_next;
02186 
02187     unsigned val = *src;
02188 
02189     do
02190     {
02191         // We can fast pace if *src == 0 or *src = 0xffffffff
02192 
02193         while (val == 0 || val == 0xffffffff)
02194         {
02195            bitval_next = val ? 1 : 0;
02196            if (bitval != bitval_next)
02197            {
02198                *pcurr++ = bit_idx-1; 
02199                BM_ASSERT((pcurr-1) == (dest+1) || *(pcurr-1) > *(pcurr-2));
02200                if (pcurr >= end)
02201                {
02202                    return 0; // OUT of memory
02203                }
02204                bitval = bitval_next;
02205            }
02206            bit_idx += sizeof(*src) * 8;
02207            if (bit_idx >= bits)
02208            {
02209                goto complete;
02210            }
02211            ++src;
02212            val = *src;
02213         }
02214 
02215 
02216         register unsigned mask = 1;
02217         while (mask)
02218         {
02219             // Now plain bitshifting. Optimization wanted.
02220 
02221             bitval_next = val & mask ? 1 : 0;
02222             if (bitval != bitval_next)
02223             {
02224                 *pcurr++ = bit_idx-1;
02225                 BM_ASSERT((pcurr-1) == (dest+1) || *(pcurr-1) > *(pcurr-2));
02226                 bitval = bitval_next;
02227                 if (pcurr >= end)
02228                 {
02229                     return 0; // OUT of memory
02230                 }
02231             }
02232 
02233             mask <<= 1;
02234             ++bit_idx;
02235 
02236         } // while mask
02237 
02238         if (bit_idx >= bits)
02239         {
02240             goto complete;
02241         }
02242 
02243         ++src;
02244         val = *src;
02245 
02246     } while(1);
02247 
02248 complete:
02249     *pcurr = bit_idx-1;
02250     unsigned len = (unsigned)(pcurr - dest);
02251     *dest = (*dest & 7) + (len << 3);
02252     return len;
02253 }
02254 
02255 
02256 /*!
02257    \brief Convert gap block into array of ints corresponding to 1 bits
02258    @ingroup gapfunc
02259 */
02260 template<typename D, typename T>
02261 D gap_convert_to_arr(D* BMRESTRICT       dest, 
02262                      const T* BMRESTRICT buf,
02263                      unsigned            dest_len)
02264 {
02265     register const T* BMRESTRICT pcurr = buf;
02266     register const T* pend = pcurr + (*pcurr >> 3);
02267 
02268     D* BMRESTRICT dest_curr = dest;
02269     ++pcurr;
02270 
02271     if (*buf & 1)
02272     {
02273         if (unsigned(*pcurr + 1) >= dest_len)
02274             return 0; // insufficient space
02275         dest_len -= *pcurr;
02276         T to = *pcurr;
02277         for (T i = 0; ;++i) 
02278         {
02279             *dest_curr++ = i;
02280             if (i == to) break;
02281         }
02282         ++pcurr;
02283     }
02284     ++pcurr;  // set GAP to 1
02285 
02286     while (pcurr <= pend)
02287     {
02288         unsigned pending = *pcurr - *(pcurr-1);
02289         if (pending >= dest_len)
02290             return 0;
02291         dest_len -= pending;
02292         T from = *(pcurr-1)+1;
02293         T to = *pcurr;
02294         for (T i = from; ;++i) 
02295         {
02296             *dest_curr++ = i;
02297             if (i == to) break;
02298         }
02299         pcurr += 2; // jump to the next positive GAP
02300     }
02301     return (D) (dest_curr - dest);
02302 }
02303 
02304 /*!
02305     \brief Convert bit block into an array of ints corresponding to 1 bits
02306     @ingroup bitfunc 
02307 */
02308 template<typename T> T bit_convert_to_arr(T* BMRESTRICT dest, 
02309                                           const unsigned* BMRESTRICT src, 
02310                                           bm::id_t bits, 
02311                                           unsigned dest_len)
02312 {
02313     register T* BMRESTRICT pcurr = dest;
02314     T* BMRESTRICT end = dest + dest_len; 
02315     register unsigned bit_idx = 0;
02316 
02317     do
02318     {
02319         register unsigned val = *src;
02320         // We can skip if *src == 0 
02321 
02322         while (val == 0)
02323         {
02324             bit_idx += sizeof(*src) * 8;
02325             if (bit_idx >= bits)
02326             {
02327                return (T)(pcurr - dest);
02328             }
02329             val = *(++src);
02330         }
02331 
02332         if (pcurr + sizeof(val)*8 > end) // insufficient space
02333         {
02334             return 0;
02335         }
02336 
02337         for (int i = 0; i < 32; i+=4)
02338         {
02339             if (val & 1)
02340                 *pcurr++ = bit_idx;
02341             val >>= 1; ++bit_idx;
02342             if (val & 1)
02343                 *pcurr++ = bit_idx;
02344             val >>= 1; ++bit_idx;
02345             if (val & 1)
02346                 *pcurr++ = bit_idx;
02347             val >>= 1; ++bit_idx;
02348             if (val & 1)
02349                 *pcurr++ = bit_idx;
02350             val >>= 1; ++bit_idx;
02351         }
02352         if (bits <= bit_idx)
02353             break;
02354 
02355         val = *(++src);
02356 
02357     } while (1);
02358 
02359     return (T)(pcurr - dest);
02360 }
02361 
02362 
02363 
02364 /*! 
02365     @brief Bitcount for bit string
02366     
02367     Function calculates number of 1 bits in the given array of words.
02368     Make sure the addresses are aligned.
02369 
02370     @ingroup bitfunc 
02371 */
02372 inline 
02373 bm::id_t bit_block_calc_count(const bm::word_t* block, 
02374                               const bm::word_t* block_end)
02375 {
02376     BM_ASSERT(block < block_end);
02377     bm::id_t count = 0;
02378 
02379 #ifdef BM64OPT
02380 
02381     // 64-bit optimized algorithm.
02382 
02383     const bm::id64_t* b1 = (bm::id64_t*) block;
02384     const bm::id64_t* b2 = (bm::id64_t*) block_end;
02385 
02386     bm::id64_t  acc = *b1++;  // accumulator (sparse vectors optimization)
02387 
02388     do
02389     {
02390         bm::id64_t in = *b1++;
02391         bm::id64_t acc_prev = acc;
02392         acc |= in;
02393 
02394         if (acc_prev &= in)  // counting bits in accumulator
02395         {
02396             acc = (acc & 0x5555555555555555LU) + (acc >> 1 & 0x5555555555555555LU);
02397             acc = (acc & 0x3333333333333333LU) + (acc >> 2 & 0x3333333333333333LU);
02398             acc = acc + (acc >> 4) & 0x0F0F0F0F0F0F0F0FLU;
02399             acc = acc + (acc >> 8);
02400             acc = acc + (acc >> 16);
02401             acc = acc + (acc >> 32) & 0x0000007F;
02402             count += (unsigned)acc;
02403 
02404             acc = acc_prev;
02405         }
02406     } while (b1 < b2);
02407     count += word_bitcount64(acc);  // count-in remaining accumulator 
02408 
02409 #else
02410     // For 32 bit code the fastest method is
02411     // to use bitcount table for each byte in the block.
02412     // As optimization for sparse bitsets used bits accumulator
02413     // to collect ON bits using bitwise OR. 
02414     bm::word_t  acc = *block++;
02415     do
02416     {
02417         bm::word_t in = *block++;
02418         bm::word_t acc_prev = acc;
02419         acc |= in;
02420         if (acc_prev &= in)  // accumulator miss: counting bits
02421         {
02422             BM_INCWORD_BITCOUNT(count, acc);
02423             acc = acc_prev;
02424         }
02425     } while (block < block_end);
02426 
02427     BM_INCWORD_BITCOUNT(count, acc); // count-in remaining accumulator 
02428 
02429 #endif
02430     
02431     return count;
02432 }
02433 
02434 /*!
02435     Function calculates number of times when bit value changed 
02436     (1-0 or 0-1).
02437     
02438     For 001 result is 2
02439         010 - 3
02440         011 - 2
02441         111 - 1
02442     
02443     @ingroup bitfunc 
02444 */
02445 
02446 inline 
02447 bm::id_t bit_count_change(bm::word_t w)
02448 {
02449     unsigned count = 1;
02450     w ^= (w >> 1);
02451 
02452     BM_INCWORD_BITCOUNT(count, w);
02453     count -= (w >> ((sizeof(w) * 8) - 1));
02454     return count;
02455 }
02456 
02457 
02458 /*!
02459     Function calculates number of times when bit value changed 
02460     (1-0 or 0-1) in the bit block.
02461         
02462     @ingroup bitfunc 
02463 */
02464 inline 
02465 bm::id_t bit_block_calc_count_change(const bm::word_t* block, 
02466                                      const bm::word_t* block_end)
02467 {
02468     BM_ASSERT(block < block_end);
02469     bm::id_t count = 1;
02470     
02471 #ifdef BM64OPT
02472 
02473     // 64-bit optimized algorithm.
02474 
02475     const bm::id64_t* b1 = (bm::id64_t*) block;
02476     const bm::id64_t* b2 = (bm::id64_t*) block_end;
02477 
02478     bm::id64_t w, w0, w_prev, w_l;
02479     w = w0 = *b1;
02480     const int w_shift = sizeof(w) * 8 - 1;
02481     w ^= (w >> 1);
02482     count += word_bitcount64(w);
02483     count -= (w_prev = (w0 >> w_shift)); // negative value correction
02484     
02485     for (++b1 ;b1 < b2; ++b1)
02486     {
02487         w = w0 = *b1;
02488         ++count;
02489         
02490         if (!w)
02491         {
02492             count -= !w_prev;
02493             w_prev = 0;
02494         }
02495         else
02496         {
02497             w ^= (w >> 1);
02498             count += word_bitcount64(w);
02499             
02500             w_l = w0 & 1;
02501             count -= (w0 >> w_shift);  // negative value correction
02502             count -= !(w_prev ^ w_l);  // word border correction
02503             
02504             w_prev = (w0 >> w_shift);
02505         }
02506     } // for
02507 
02508 #else
02509     
02510     bm::word_t  w, w0, w_prev, w_l; 
02511     
02512     w = w0 = *block;
02513     const int w_shift = sizeof(w) * 8 - 1;    
02514     w ^= (w >> 1);
02515     BM_INCWORD_BITCOUNT(count, w);
02516     count -= (w_prev = (w0 >> w_shift)); // negative value correction
02517 
02518     for (++block ;block < block_end; ++block)
02519     {
02520         w = w0 = *block;
02521         ++count;
02522 
02523         if (!w)
02524         {       
02525             count -= !w_prev;
02526             w_prev = 0;
02527         }
02528         else
02529         {
02530             w ^= (w >> 1);
02531             BM_INCWORD_BITCOUNT(count, w);
02532             
02533             w_l = w0 & 1;
02534             count -= (w0 >> w_shift);  // negative value correction
02535             count -= !(w_prev ^ w_l);  // word border correction
02536             
02537             w_prev = (w0 >> w_shift);
02538         }
02539     } // for
02540 #endif
02541     return count;
02542 }
02543 
02544 
02545 /*!
02546     Function calculates number of 1 bits in the given array of words in
02547     the range between left anf right bits (borders included)
02548     Make sure the addresses are aligned.
02549 
02550     @ingroup bitfunc
02551 */
02552 inline 
02553 bm::id_t bit_block_calc_count_range(const bm::word_t* block,
02554                                     bm::word_t left,
02555                                     bm::word_t right)
02556 {
02557     BM_ASSERT(left <= right);
02558     
02559     bm::id_t count = 0;
02560 
02561     unsigned nbit  = left; // unsigned(left & bm::set_block_mask);
02562     unsigned nword = unsigned(nbit >> bm::set_word_shift);
02563     nbit &= bm::set_word_mask;
02564 
02565     const bm::word_t* word = block + nword;
02566 
02567     if (left == right)  // special case (only 1 bit to check)
02568     {
02569         return (*word >> nbit) & 1;
02570     }
02571     unsigned acc;
02572     unsigned bitcount = right - left + 1;
02573 
02574     if (nbit) // starting position is not aligned
02575     {
02576         unsigned right_margin = nbit + (right - left);
02577 
02578         if (right_margin < 32)
02579         {
02580             unsigned mask =
02581                 block_set_table<true>::_right[nbit] &
02582                 block_set_table<true>::_left[right_margin];
02583             acc = *word & mask;
02584             
02585             BM_INCWORD_BITCOUNT(count, acc);
02586             return count;
02587         }
02588         else
02589         {
02590             acc = *word & block_set_table<true>::_right[nbit];
02591             BM_INCWORD_BITCOUNT(count, acc);
02592             bitcount -= 32 - nbit;
02593         }
02594         ++word;
02595     }
02596 
02597     // now when we are word aligned, we can count bits the usual way
02598     for ( ;bitcount >= 32; bitcount -= 32)
02599     {
02600         acc = *word++;
02601         BM_INCWORD_BITCOUNT(count, acc);
02602     }
02603 
02604     if (bitcount)  // we have a tail to count
02605     {
02606         acc = (*word) & block_set_table<true>::_left[bitcount-1];
02607         BM_INCWORD_BITCOUNT(count, acc);
02608     }
02609 
02610     return count;
02611 }
02612 
02613 
02614 /*!
02615     Function calculates if there is any number of 1 bits 
02616     in the given array of words in the range between left anf right bits 
02617     (borders included). Make sure the addresses are aligned.
02618 
02619     @ingroup bitfunc
02620 */
02621 inline 
02622 bm::id_t bit_block_any_range(const bm::word_t* block,
02623                              bm::word_t left,
02624                              bm::word_t right)
02625 {
02626     BM_ASSERT(left <= right);
02627     
02628     unsigned nbit  = left; // unsigned(left & bm::set_block_mask);
02629     unsigned nword = unsigned(nbit >> bm::set_word_shift);
02630     nbit &= bm::set_word_mask;
02631 
02632     const bm::word_t* word = block + nword;
02633 
02634     if (left == right)  // special case (only 1 bit to check)
02635     {
02636         return (*word >> nbit) & 1;
02637     }
02638     unsigned acc;
02639     unsigned bitcount = right - left + 1;
02640 
02641     if (nbit) // starting position is not aligned
02642     {
02643         unsigned right_margin = nbit + (right - left);
02644         if (right_margin < 32)
02645         {
02646             unsigned mask =
02647                 block_set_table<true>::_right[nbit] &
02648                 block_set_table<true>::_left[right_margin];
02649             acc = *word & mask;
02650             return acc;
02651         }
02652         else
02653         {
02654             acc = *word & block_set_table<true>::_right[nbit];
02655             if (acc) 
02656                 return acc;
02657             bitcount -= 32 - nbit;
02658         }
02659         ++word;
02660     }
02661 
02662     // now when we are word aligned, we can check bits the usual way
02663     for ( ;bitcount >= 32; bitcount -= 32)
02664     {
02665         acc = *word++;
02666         if (acc) 
02667             return acc;
02668     }
02669 
02670     if (bitcount)  // we have a tail to count
02671     {
02672         acc = (*word) & block_set_table<true>::_left[bitcount-1];
02673         if (acc) 
02674             return acc;
02675     }
02676 
02677     return 0;
02678 }
02679 
02680 
02681 
02682 // ----------------------------------------------------------------------
02683 
02684 /*! Function inverts block of bits 
02685     @ingroup bitfunc 
02686 */
02687 template<typename T> void bit_invert(T* start, T* end)
02688 {
02689 #ifdef BMVECTOPT
02690     VECT_INVERT_ARR(start, end);
02691 #else
02692     do
02693     {
02694         start[0] = ~start[0];
02695         start[1] = ~start[1];
02696         start[2] = ~start[2];
02697         start[3] = ~start[3];
02698         start+=4;
02699     } while (start < end);
02700 #endif
02701 }
02702 
02703 // ----------------------------------------------------------------------
02704 
02705 /*! @brief Returns "true" if all bits in the block are 1
02706     @ingroup bitfunc 
02707 */
02708 inline bool is_bits_one(const bm::wordop_t* start, 
02709                         const bm::wordop_t* end)
02710 {
02711    do
02712    {
02713         bm::wordop_t tmp = 
02714             start[0] & start[1] & start[2] & start[3];
02715         if (tmp != bm::all_bits_mask) 
02716             return false;
02717         start += 4;
02718    } while (start < end);
02719 
02720    return true;
02721 }
02722 
02723 // ----------------------------------------------------------------------
02724 
02725 
02726 /*! @brief Returns "true" if all bits in the block are 0
02727     @ingroup bitfunc 
02728 */
02729 inline bool bit_is_all_zero(const bm::wordop_t* start, 
02730                             const bm::wordop_t* end)
02731 {
02732    do
02733    {
02734         bm::wordop_t tmp = 
02735             start[0] | start[1] | start[2] | start[3];
02736        if (tmp) 
02737            return false;
02738        start += 4;
02739    } while (start < end);
02740 
02741    return true;
02742 }
02743 
02744 // ----------------------------------------------------------------------
02745 
02746 // GAP blocks manipulation functions:
02747 
02748 /*! \brief GAP and functor */
02749 inline unsigned and_op(unsigned v1, unsigned v2)
02750 {
02751     return v1 & v2;
02752 }
02753 
02754 
02755 /*! \brief GAP xor functor */
02756 inline unsigned xor_op(unsigned v1, unsigned v2)
02757 {
02758     return v1 ^ v2;
02759 }
02760 
02761 
02762 /*!
02763    \brief GAP AND operation.
02764    
02765    Function performs AND logical oparation on gap vectors.
02766    If possible function put the result into vect1 and returns this
02767    pointer.  Otherwise result is put into tmp_buf, which should be 
02768    twice of the vector size.
02769 
02770    \param vect1   - operand 1
02771    \param vect2   - operand 2
02772    \param tmp_buf - pointer on temporary buffer
02773    \return Result pointer (tmp_buf OR vect1)
02774 
02775    @ingroup gapfunc
02776 */
02777 inline gap_word_t* gap_operation_and(const gap_word_t* BMRESTRICT vect1,
02778                                      const gap_word_t* BMRESTRICT vect2,
02779                                      gap_word_t*       BMRESTRICT tmp_buf)
02780 {
02781     gap_buff_op(tmp_buf, vect1, 0, vect2, 0, and_op);
02782 
02783     return tmp_buf;
02784 }
02785 
02786 /*!
02787    \brief GAP AND operation test.
02788    
02789    Function performs AND logical oparation on gap vectors.
02790    If possible function put the result into vect1 and returns this
02791    pointer.  Otherwise result is put into tmp_buf, which should be 
02792    twice of the vector size.
02793 
02794    \param vect1   - operand 1
02795    \param vect2   - operand 2
02796    \return non zero value if operation returns any 1 bit
02797 
02798    @ingroup gapfunc
02799 */
02800 inline unsigned gap_operation_any_and(const gap_word_t* BMRESTRICT vect1,
02801                                       const gap_word_t* BMRESTRICT vect2)
02802 {
02803     return gap_buff_any_op(vect1, 0, vect2, 0, and_op);
02804 }
02805 
02806 
02807 
02808 /*!
02809    \brief GAP XOR operation.
02810    
02811    Function performs XOR logical oparation on gap vectors.
02812    If possible function put the result into vect1 and returns this
02813    pointer.  Otherwise result is put into tmp_buf, which should be 
02814    twice of the vector size.
02815 
02816    \param vect1   - operand 1
02817    \param vect2   - operand 2
02818    \param tmp_buf - pointer on temporary buffer
02819    \return Result pointer (tmp_buf)
02820 
02821    @ingroup gapfunc
02822 */
02823 inline gap_word_t* gap_operation_xor(const gap_word_t*  BMRESTRICT vect1,
02824                                      const gap_word_t*  BMRESTRICT vect2,
02825                                      gap_word_t*        BMRESTRICT tmp_buf)
02826 {
02827     gap_buff_op(tmp_buf, vect1, 0, vect2, 0, xor_op);
02828     return tmp_buf;
02829 }
02830 
02831 
02832 /*!
02833    \brief GAP XOR operation test.
02834    
02835    Function performs AND logical oparation on gap vectors.
02836    If possible function put the result into vect1 and returns this
02837    pointer.  Otherwise result is put into tmp_buf, which should be 
02838    twice of the vector size.
02839 
02840    \param vect1   - operand 1
02841    \param vect2   - operand 2
02842    \return non zero value if operation returns any 1 bit
02843 
02844    @ingroup gapfunc
02845 */
02846 inline unsigned gap_operation_any_xor(const gap_word_t* BMRESTRICT vect1,
02847                                       const gap_word_t* BMRESTRICT vect2)
02848 {
02849     return gap_buff_any_op(vect1, 0, vect2, 0, xor_op);
02850 }
02851 
02852 
02853 
02854 /*!
02855    \brief GAP OR operation.
02856    
02857    Function performs OR logical oparation on gap vectors.
02858    If possible function put the result into vect1 and returns this
02859    pointer.  Otherwise result is put into tmp_buf, which should be 
02860    twice of the vector size.
02861 
02862    \param vect1   - operand 1
02863    \param vect2   - operand 2
02864    \param tmp_buf - pointer on temporary buffer
02865    \return Result pointer (tmp_buf)
02866 
02867    @ingroup gapfunc
02868 */
02869 inline gap_word_t* gap_operation_or(const gap_word_t*  BMRESTRICT vect1,
02870                                     const gap_word_t*  BMRESTRICT vect2,
02871                                     gap_word_t*        BMRESTRICT tmp_buf)
02872 {
02873     gap_buff_op(tmp_buf, vect1, 1, vect2, 1, and_op);
02874     gap_invert(tmp_buf);
02875     return tmp_buf;
02876 }
02877 
02878 
02879 
02880 
02881 /*!
02882    \brief GAP SUB (AND NOT) operation.
02883    
02884    Function performs SUB logical oparation on gap vectors.
02885    If possible function put the result into vect1 and returns this
02886    pointer.  Otherwise result is put into tmp_buf, which should be 
02887    twice of the vector size.
02888 
02889    \param vect1   - operand 1
02890    \param vect2   - operand 2
02891    \param tmp_buf - pointer on temporary buffer
02892    \return Result pointer (tmp_buf)
02893 
02894    @ingroup gapfunc
02895 */
02896 inline gap_word_t* gap_operation_sub(const gap_word_t*  BMRESTRICT vect1,
02897                                      const gap_word_t*  BMRESTRICT vect2,
02898                                      gap_word_t*        BMRESTRICT tmp_buf)
02899 {
02900     gap_buff_op(tmp_buf, vect1, 0, vect2, 1, and_op);    
02901     return tmp_buf;
02902 }
02903 
02904 
02905 /*!
02906    \brief GAP SUB operation test.
02907    
02908    Function performs AND logical oparation on gap vectors.
02909    If possible function put the result into vect1 and returns this
02910    pointer.  Otherwise result is put into tmp_buf, which should be 
02911    twice of the vector size.
02912 
02913    \param vect1   - operand 1
02914    \param vect2   - operand 2
02915    \return non zero value if operation returns any 1 bit
02916 
02917    @ingroup gapfunc
02918 */
02919 inline unsigned gap_operation_any_sub(const gap_word_t* BMRESTRICT vect1,
02920                                       const gap_word_t* BMRESTRICT vect2)
02921 {
02922     return gap_buff_any_op(vect1, 0, vect2, 1, and_op);    
02923 }
02924 
02925 
02926 // ----------------------------------------------------------------------
02927 
02928 // BIT blocks manipulation functions:
02929 
02930 
02931 /*!
02932    \brief Bitblock copy operation. 
02933 
02934    \param dst - destination block.
02935    \param src - source block.
02936 
02937    @ingroup bitfunc
02938 */
02939 inline 
02940 void bit_block_copy(bm::word_t* BMRESTRICT dst, const bm::word_t* BMRESTRICT src)
02941 {
02942 #ifdef BMVECTOPT
02943     VECT_COPY_BLOCK(dst, src, src + bm::set_block_size);
02944 #else
02945     ::memcpy(dst, src, bm::set_block_size * sizeof(bm::word_t));
02946 #endif
02947 }
02948 
02949 
02950 /*!
02951    \brief Plain bitblock AND operation. 
02952    Function does not analyse availability of source and destination blocks.
02953 
02954    \param dst - destination block.
02955    \param src - source block.
02956 
02957    @ingroup bitfunc
02958 */
02959 inline 
02960 void bit_block_and(bm::word_t* BMRESTRICT dst, const bm::word_t* BMRESTRICT src)
02961 {
02962 #ifdef BMVECTOPT
02963     VECT_AND_ARR(dst, src, src + bm::set_block_size);
02964 #else
02965     const bm::wordop_t* BMRESTRICT wrd_ptr = (wordop_t*)src;
02966     const bm::wordop_t* BMRESTRICT wrd_end = (wordop_t*)(src + bm::set_block_size);
02967     bm::wordop_t* BMRESTRICT dst_ptr = (wordop_t*)dst;
02968 
02969     do
02970     {
02971         dst_ptr[0] &= wrd_ptr[0];
02972         dst_ptr[1] &= wrd_ptr[1];
02973         dst_ptr[2] &= wrd_ptr[2];
02974         dst_ptr[3] &= wrd_ptr[3];
02975 
02976         dst_ptr+=4;
02977         wrd_ptr+=4;
02978     } while (wrd_ptr < wrd_end);
02979 #endif
02980 }
02981 
02982 
02983 /*!
02984    \brief Function ANDs two bitblocks and computes the bitcount. 
02985    Function does not analyse availability of source blocks.
02986 
02987    \param src1     - first bit block
02988    \param src1_end - first bit block end
02989    \param src2     - second bit block
02990 
02991    @ingroup bitfunc
02992 */
02993 inline 
02994 unsigned bit_block_and_count(const bm::word_t* src1, 
02995                              const bm::word_t* src1_end,
02996                              const bm::word_t* src2)
02997 {
02998     unsigned count;
02999 #ifdef BMVECTOPT
03000     count = VECT_BITCOUNT_AND(src1, src1_end, src2);
03001 #else  
03002     count = 0;  
03003     do
03004     {
03005         BM_INCWORD_BITCOUNT(count, src1[0] & src2[0]);
03006         BM_INCWORD_BITCOUNT(count, src1[1] & src2[1]);
03007         BM_INCWORD_BITCOUNT(count, src1[2] & src2[2]);
03008         BM_INCWORD_BITCOUNT(count, src1[3] & src2[3]);
03009 
03010         src1+=4;
03011         src2+=4;
03012     } while (src1 < src1_end);
03013 #endif    
03014     return count;
03015 }
03016 
03017 
03018 /*!
03019    \brief Function ANDs two bitblocks and tests for any bit. 
03020    Function does not analyse availability of source blocks.
03021 
03022    \param src1     - first bit block
03023    \param src1_end - first bit block end
03024    \param src2     - second bit block
03025 
03026    @ingroup bitfunc
03027 */
03028 inline 
03029 unsigned bit_block_and_any(const bm::word_t* src1, 
03030                            const bm::word_t* src1_end,
03031                            const bm::word_t* src2)
03032 {
03033     unsigned count = 0;
03034     do
03035     {
03036         count = (src1[0] & src2[0]) |
03037                 (src1[1] & src2[1]) |
03038                 (src1[2] & src2[2]) |
03039                 (src1[3] & src2[3]);
03040 
03041         src1+=4; src2+=4;
03042     } while ((src1 < src1_end) && (count == 0));
03043     return count;
03044 }
03045 
03046 
03047 
03048 
03049 /*!
03050    \brief Function XORs two bitblocks and computes the bitcount. 
03051    Function does not analyse availability of source blocks.
03052 
03053    \param src1     - first bit block.
03054    \param src1_end - first bit block end
03055    \param src2     - second bit block.
03056 
03057    @ingroup bitfunc
03058 */
03059 inline 
03060 unsigned bit_block_xor_count(const bm::word_t* BMRESTRICT src1,
03061                              const bm::word_t* BMRESTRICT src1_end, 
03062                              const bm::word_t* BMRESTRICT src2)
03063 {
03064     unsigned count;
03065 #ifdef BMVECTOPT
03066     count = VECT_BITCOUNT_XOR(src1, src1_end, src2);
03067 #else  
03068     count = 0;  
03069     do
03070     {
03071         BM_INCWORD_BITCOUNT(count, src1[0] ^ src2[0]);
03072         BM_INCWORD_BITCOUNT(count, src1[1] ^ src2[1]);
03073         BM_INCWORD_BITCOUNT(count, src1[2] ^ src2[2]);
03074         BM_INCWORD_BITCOUNT(count, src1[3] ^ src2[3]);
03075 
03076         src1+=4;
03077         src2+=4;
03078     } while (src1 < src1_end);
03079 #endif
03080     return count;
03081 }
03082 
03083 
03084 /*!
03085    \brief Function XORs two bitblocks and and tests for any bit.
03086    Function does not analyse availability of source blocks.
03087 
03088    \param src1     - first bit block.
03089    \param src1_end - first bit block end
03090    \param src2     - second bit block.
03091 
03092    @ingroup bitfunc
03093 */
03094 inline 
03095 unsigned bit_block_xor_any(const bm::word_t* BMRESTRICT src1,
03096                              const bm::word_t* BMRESTRICT src1_end, 
03097                              const bm::word_t* BMRESTRICT src2)
03098 {
03099     unsigned count = 0;
03100     do
03101     {
03102         count = (src1[0] ^ src2[0]) |
03103                 (src1[1] ^ src2[1]) |
03104                 (src1[2] ^ src2[2]) |
03105                 (src1[3] ^ src2[3]);
03106 
03107         src1+=4; src2+=4;
03108     } while ((src1 < src1_end) && (count == 0));
03109     return count;
03110 }
03111 
03112 
03113 
03114 
03115 /*!
03116    \brief Function SUBs two bitblocks and computes the bitcount. 
03117    Function does not analyse availability of source blocks.
03118 
03119    \param src1     - first bit block.
03120    \param src1_end - first bit block end
03121    \param src2     - second bit block.
03122 
03123    @ingroup bitfunc
03124 */
03125 inline 
03126 unsigned bit_block_sub_count(const bm::word_t* BMRESTRICT src1, 
03127                              const bm::word_t* BMRESTRICT src1_end, 
03128                              const bm::word_t* BMRESTRICT src2)
03129 {
03130     unsigned count;
03131 #ifdef BMVECTOPT
03132     count = VECT_BITCOUNT_SUB(src1, src1_end, src2);
03133 #else  
03134     count = 0;  
03135     do
03136     {
03137         BM_INCWORD_BITCOUNT(count, src1[0] & ~src2[0]);
03138         BM_INCWORD_BITCOUNT(count, src1[1] & ~src2[1]);
03139         BM_INCWORD_BITCOUNT(count, src1[2] & ~src2[2]);
03140         BM_INCWORD_BITCOUNT(count, src1[3] & ~src2[3]);
03141 
03142         src1+=4;
03143         src2+=4;
03144     } while (src1 < src1_end);
03145 #endif
03146     return count;
03147 }
03148 
03149 /*!
03150    \brief Function SUBs two bitblocks and and tests for any bit.
03151    Function does not analyse availability of source blocks.
03152 
03153    \param src1     - first bit block.
03154    \param src1_end - first bit block end
03155    \param src2     - second bit block.
03156 
03157    @ingroup bitfunc
03158 */
03159 inline 
03160 unsigned bit_block_sub_any(const bm::word_t* BMRESTRICT src1,
03161                              const bm::word_t* BMRESTRICT src1_end, 
03162                              const bm::word_t* BMRESTRICT src2)
03163 {
03164     unsigned count = 0;
03165     do
03166     {
03167         count = (src1[0] & ~src2[0]) |
03168                 (src1[1] & ~src2[1]) |
03169                 (src1[2] & ~src2[2]) |
03170                 (src1[3] & ~src2[3]);
03171 
03172         src1+=4; src2+=4;
03173     } while ((src1 < src1_end) && (count == 0));
03174     return count;
03175 }
03176 
03177 
03178 
03179 /*!
03180    \brief Function ORs two bitblocks and computes the bitcount. 
03181    Function does not analyse availability of source blocks.
03182 
03183    \param src1     - first bit block
03184    \param src1_end - first block end
03185    \param src2     - second bit block.
03186 
03187    @ingroup bitfunc
03188 */
03189 inline 
03190 unsigned bit_block_or_count(const bm::word_t* src1, 
03191                             const bm::word_t* src1_end,
03192                             const bm::word_t* src2)
03193 {
03194     unsigned count;
03195 #ifdef BMVECTOPT
03196     count = VECT_BITCOUNT_OR(src1, src1_end, src2);
03197 #else  
03198     count = 0;  
03199     do
03200     {
03201         BM_INCWORD_BITCOUNT(count, src1[0] | src2[0]);
03202         BM_INCWORD_BITCOUNT(count, src1[1] | src2[1]);
03203         BM_INCWORD_BITCOUNT(count, src1[2] | src2[2]);
03204         BM_INCWORD_BITCOUNT(count, src1[3] | src2[3]);
03205 
03206         src1+=4;
03207         src2+=4;
03208     } while (src1 < src1_end);
03209 #endif
03210     return count;
03211 }
03212 
03213 /*!
03214    \brief Function ORs two bitblocks and and tests for any bit.
03215    Function does not analyse availability of source blocks.
03216 
03217    \param src1     - first bit block.
03218    \param src1_end - first bit block end
03219    \param src2     - second bit block.
03220 
03221    @ingroup bitfunc
03222 */
03223 inline 
03224 unsigned bit_block_or_any(const bm::word_t* BMRESTRICT src1,
03225                           const bm::word_t* BMRESTRICT src1_end, 
03226                           const bm::word_t* BMRESTRICT src2)
03227 {
03228     unsigned count = 0;
03229     do
03230     {
03231         count = (src1[0] | src2[0]) |
03232                 (src1[1] | src2[1]) |
03233                 (src1[2] | src2[2]) |
03234                 (src1[3] | src2[3]);
03235 
03236         src1+=4; src2+=4;
03237     } while ((src1 < src1_end) && (count == 0));
03238     return count;
03239 }
03240 
03241 
03242 
03243 
03244 /*!
03245    \brief bitblock AND operation. 
03246 
03247    \param dst - destination block.
03248    \param src - source block.
03249 
03250    \returns pointer on destination block. 
03251     If returned value  equal to src means that block mutation requested. 
03252     NULL is valid return value.
03253 
03254    @ingroup bitfunc
03255 */
03256 inline bm::word_t* bit_operation_and(bm::word_t* BMRESTRICT dst, 
03257                                      const bm::word_t* BMRESTRICT src)
03258 {
03259     BM_ASSERT(dst || src);
03260 
03261     bm::word_t* ret = dst;
03262 
03263     if (IS_VALID_ADDR(dst))  // The destination block already exists
03264     {
03265 
03266         if (!IS_VALID_ADDR(src))
03267         {
03268             if (IS_EMPTY_BLOCK(src))
03269             {
03270                 //If the source block is zero 
03271                 //just clean the destination block
03272                 return 0;
03273             }
03274         }
03275         else
03276         {
03277             // Regular operation AND on the whole block.
03278             bit_block_and(dst, src);
03279         }
03280     }
03281     else // The destination block does not exist yet
03282     {
03283         if(!IS_VALID_ADDR(src))
03284         {
03285             if(IS_EMPTY_BLOCK(src)) 
03286             {
03287                 // The source block is empty.
03288                 // One argument empty - all result is empty.
03289                 return 0;
03290             }
03291             // Here we have nothing to do.
03292             // Src block is all ON, dst block remains as it is
03293         }
03294         else // destination block does not exists, src - valid block
03295         {
03296             if (IS_FULL_BLOCK(dst))
03297             {
03298                 return const_cast<bm::word_t*>(src);
03299             }
03300             // Nothng to do.
03301             // Dst block is all ZERO no combination required.
03302         }
03303     }
03304 
03305     return ret;
03306 }
03307 
03308 
03309 /*!
03310    \brief Performs bitblock AND operation and calculates bitcount of the result. 
03311 
03312    \param src1     - first bit block.
03313    \param src1_end - first bit block end
03314    \param src2     - second bit block.
03315 
03316    \returns bitcount value 
03317 
03318    @ingroup bitfunc
03319 */
03320 inline 
03321 bm::id_t bit_operation_and_count(const bm::word_t* BMRESTRICT src1,
03322                                  const bm::word_t* BMRESTRICT src1_end,
03323                                  const bm::word_t* BMRESTRICT src2)
03324 {
03325     if (IS_EMPTY_BLOCK(src1) || IS_EMPTY_BLOCK(src2))
03326     {
03327         return 0;
03328     }
03329     return bit_block_and_count(src1, src1_end, src2);
03330 }
03331 
03332 /*!
03333    \brief Performs bitblock AND operation test. 
03334 
03335    \param src1     - first bit block.
03336    \param src1_end - first bit block end
03337    \param src2     - second bit block.
03338 
03339    \returns non zero if there is any value 
03340 
03341    @ingroup bitfunc
03342 */
03343 inline 
03344 bm::id_t bit_operation_and_any(const bm::word_t* BMRESTRICT src1,
03345                                const bm::word_t* BMRESTRICT src1_end,
03346                                const bm::word_t* BMRESTRICT src2)
03347 {
03348     if (IS_EMPTY_BLOCK(src1) || IS_EMPTY_BLOCK(src2))
03349     {
03350         return 0;
03351     }
03352     return bit_block_and_any(src1, src1_end, src2);
03353 }
03354 
03355 
03356 
03357 /*!
03358    \brief Performs bitblock SUB operation and calculates bitcount of the result. 
03359 
03360    \param src1      - first bit block.
03361    \param src1_end  - first bit block end
03362    \param src2      - second bit block
03363 
03364    \returns bitcount value 
03365 
03366    @ingroup bitfunc
03367 */
03368 inline 
03369 bm::id_t bit_operation_sub_count(const bm::word_t* BMRESTRICT src1, 
03370                                  const bm::word_t* BMRESTRICT src1_end,
03371                                  const bm::word_t* BMRESTRICT src2)
03372 {
03373     if (IS_EMPTY_BLOCK(src1))
03374     {
03375         return 0;
03376     }
03377     
03378     if (IS_EMPTY_BLOCK(src2)) // nothing to diff
03379     {
03380         return bit_block_calc_count(src1, src1_end);
03381     }
03382     return bit_block_sub_count(src1, src1_end, src2);
03383 }
03384 
03385 
03386 /*!
03387    \brief Performs inverted bitblock SUB operation and calculates 
03388           bitcount of the result. 
03389 
03390    \param src1      - first bit block.
03391    \param src1_end  - first bit block end
03392    \param src2      - second bit block
03393 
03394    \returns bitcount value 
03395 
03396    @ingroup bitfunc
03397 */
03398 inline 
03399 bm::id_t bit_operation_sub_count_inv(const bm::word_t* BMRESTRICT src1, 
03400                                      const bm::word_t* BMRESTRICT src1_end,
03401                                      const bm::word_t* BMRESTRICT src2)
03402 {
03403     unsigned arr_size = src1_end - src1;
03404     return bit_operation_sub_count(src2, src2+arr_size, src1);
03405 }
03406 
03407 
03408 /*!
03409    \brief Performs bitblock test of SUB operation. 
03410 
03411    \param src1      - first bit block.
03412    \param src1_end  - first bit block end
03413    \param src2      - second bit block
03414 
03415    \returns non zero value if there are any bits
03416 
03417    @ingroup bitfunc
03418 */
03419 inline 
03420 bm::id_t bit_operation_sub_any(const bm::word_t* BMRESTRICT src1, 
03421                                const bm::word_t* BMRESTRICT src1_end,
03422                                const bm::word_t* BMRESTRICT src2)
03423 {
03424     if (IS_EMPTY_BLOCK(src1))
03425     {
03426         return 0;
03427     }
03428     
03429     if (IS_EMPTY_BLOCK(src2)) // nothing to diff
03430     {
03431         return !bit_is_all_zero(src1, src1_end);
03432     }
03433     return bit_block_sub_any(src1, src1_end, src2);
03434 }
03435 
03436 
03437 
03438 /*!
03439    \brief Performs bitblock OR operation and calculates bitcount of the result. 
03440 
03441    \param src1     - first bit block.
03442    \param src1_end - first bit block end
03443    \param src2     - second bit block.
03444 
03445    \returns bitcount value 
03446 
03447    @ingroup bitfunc
03448 */
03449 inline 
03450 bm::id_t bit_operation_or_count(const bm::word_t* BMRESTRICT src1,
03451                                 const bm::word_t* BMRESTRICT src1_end, 
03452                                 const bm::word_t* BMRESTRICT src2)
03453 {
03454     if (IS_EMPTY_BLOCK(src1))
03455     {
03456         if (!IS_EMPTY_BLOCK(src2))
03457             return bit_block_calc_count(src2, src2 + (src1_end - src1));
03458         else
03459             return 0; // both blocks are empty        
03460     }
03461     else
03462     {
03463         if (IS_EMPTY_BLOCK(src2))
03464             return bit_block_calc_count(src1, src1_end);
03465     }
03466 
03467     return bit_block_or_count(src1, src1_end, src2);
03468 }
03469 
03470 /*!
03471    \brief Performs bitblock OR operation test. 
03472 
03473    \param src1     - first bit block.
03474    \param src1_end - first bit block end
03475    \param src2     - second bit block.
03476 
03477    \returns non zero value if there are any bits
03478 
03479    @ingroup bitfunc
03480 */
03481 inline 
03482 bm::id_t bit_operation_or_any(const bm::word_t* BMRESTRICT src1,
03483                               const bm::word_t* BMRESTRICT src1_end, 
03484                               const bm::word_t* BMRESTRICT src2)
03485 {
03486     if (IS_EMPTY_BLOCK(src1))
03487     {
03488         if (!IS_EMPTY_BLOCK(src2))
03489             return !bit_is_all_zero(src2, src2 + (src1_end - src1));
03490         else
03491             return 0; // both blocks are empty        
03492     }
03493     else
03494     {
03495         if (IS_EMPTY_BLOCK(src2))
03496             return !bit_is_all_zero(src1, src1_end);
03497     }
03498 
03499     return bit_block_or_any(src1, src1_end, src2);
03500 }
03501 
03502 
03503 
03504 /*!
03505    \brief Plain bitblock OR operation. 
03506    Function does not analyse availability of source and destination blocks.
03507 
03508    \param dst - destination block.
03509    \param src - source block.
03510 
03511    @ingroup bitfunc
03512 */
03513 inline void bit_block_or(bm::word_t* BMRESTRICT dst, 
03514                          const bm::word_t* BMRESTRICT src)
03515 {
03516 #ifdef BMVECTOPT
03517     VECT_OR_ARR(dst, src, src + bm::set_block_size);
03518 #else
03519     const bm::wordop_t* BMRESTRICT wrd_ptr = (wordop_t*)src;
03520     const bm::wordop_t* BMRESTRICT wrd_end = (wordop_t*)(src + set_block_size);
03521     bm::wordop_t* BMRESTRICT dst_ptr = (wordop_t*)dst;
03522 
03523     do
03524     {
03525         dst_ptr[0] |= wrd_ptr[0];
03526         dst_ptr[1] |= wrd_ptr[1];
03527         dst_ptr[2] |= wrd_ptr[2];
03528         dst_ptr[3] |= wrd_ptr[3];
03529 
03530         dst_ptr+=4;
03531         wrd_ptr+=4;
03532 
03533     } while (wrd_ptr < wrd_end);
03534 #endif
03535 }
03536 
03537 
03538 /*!
03539    \brief Block OR operation. Makes analysis if block is 0 or FULL. 
03540 
03541    \param dst - destination block.
03542    \param src - source block.
03543 
03544    \returns pointer on destination block. 
03545     If returned value  equal to src means that block mutation requested. 
03546     NULL is valid return value.
03547 
03548    @ingroup bitfunc
03549 */
03550 inline 
03551 bm::word_t* bit_operation_or(bm::word_t* BMRESTRICT dst, 
03552                              const bm::word_t* BMRESTRICT src)
03553 {
03554     BM_ASSERT(dst || src);
03555 
03556     bm::word_t* ret = dst;
03557 
03558     if (IS_VALID_ADDR(dst)) // The destination block already exists
03559     {
03560         if (!IS_VALID_ADDR(src))
03561         {
03562             if (IS_FULL_BLOCK(src))
03563             {
03564                 // if the source block is all set 
03565                 // just set the destination block
03566                 ::memset(dst, 0xFF, bm::set_block_size * sizeof(bm::word_t));
03567             }
03568         }
03569         else
03570         {
03571             // Regular operation OR on the whole block
03572             bit_block_or(dst, src);
03573         }
03574     }
03575     else // The destination block does not exist yet
03576     {
03577         if (!IS_VALID_ADDR(src))
03578         {
03579             if (IS_FULL_BLOCK(src)) 
03580             {
03581                 // The source block is all set, because dst does not exist
03582                 // we can simply replace it.
03583                 return const_cast<bm::word_t*>(FULL_BLOCK_ADDR);
03584             }
03585         }
03586         else
03587         {
03588             if (dst == 0)
03589             {
03590                 // The only case when we have to allocate the new block:
03591                 // Src is all zero and Dst does not exist
03592                 return const_cast<bm::word_t*>(src);
03593             }
03594         }
03595     }
03596     return ret;
03597 }
03598 
03599 /*!
03600    \brief Plain bitblock SUB (AND NOT) operation. 
03601    Function does not analyse availability of source and destination blocks.
03602 
03603    \param dst - destination block.
03604    \param src - source block.
03605 
03606    @ingroup bitfunc
03607 */
03608 inline 
03609 void bit_block_sub(bm::word_t* BMRESTRICT dst, 
03610                    const bm::word_t* BMRESTRICT src)
03611 {
03612 #ifdef BMVECTOPT
03613     VECT_SUB_ARR(dst, src, src + bm::set_block_size);
03614 #else
03615     const bm::wordop_t* BMRESTRICT wrd_ptr = (wordop_t*) src;
03616     const bm::wordop_t* BMRESTRICT wrd_end = 
03617                      (wordop_t*) (src + bm::set_block_size);
03618     bm::wordop_t* dst_ptr = (wordop_t*)dst;
03619     
03620     // Regular operation AND-NOT on the whole block.
03621     do
03622     {
03623         dst_ptr[0] &= ~wrd_ptr[0];
03624         dst_ptr[1] &= ~wrd_ptr[1];
03625         dst_ptr[2] &= ~wrd_ptr[2];
03626         dst_ptr[3] &= ~wrd_ptr[3];
03627 
03628         dst_ptr+=4;
03629         wrd_ptr+=4;
03630     } while (wrd_ptr < wrd_end);
03631 #endif
03632     
03633 }
03634 
03635 
03636 /*!
03637    \brief bitblock SUB operation. 
03638 
03639    \param dst - destination block.
03640    \param src - source block.
03641 
03642    \returns pointer on destination block. 
03643     If returned value  equal to src means that block mutation requested. 
03644     NULL is valid return value.
03645 
03646    @ingroup bitfunc
03647 */
03648 inline 
03649 bm::word_t* bit_operation_sub(bm::word_t* BMRESTRICT dst, 
03650                               const bm::word_t* BMRESTRICT src)
03651 {
03652     BM_ASSERT(dst || src);
03653 
03654     bm::word_t* ret = dst;
03655     if (IS_VALID_ADDR(dst))  //  The destination block already exists
03656     {
03657         if (!IS_VALID_ADDR(src))
03658         {
03659             if (IS_FULL_BLOCK(src))
03660             {
03661                 // If the source block is all set
03662                 // just clean the destination block
03663                 return 0;
03664             }
03665         }
03666         else
03667         {
03668             bit_block_sub(dst, src);
03669         }
03670     }
03671     else // The destination block does not exist yet
03672     {
03673         if (!IS_VALID_ADDR(src))
03674         {
03675             if (IS_FULL_BLOCK(src)) 
03676             {
03677                 // The source block is full
03678                 return 0;
03679             }
03680         }
03681         else
03682         {
03683             if (IS_FULL_BLOCK(dst))
03684             {
03685                 // The only case when we have to allocate the new block:
03686                 // dst is all set and src exists
03687                 return const_cast<bm::word_t*>(src);                  
03688             }
03689         }
03690     }
03691     return ret;
03692 }
03693 
03694 
03695 /*!
03696    \brief Plain bitblock XOR operation. 
03697    Function does not analyse availability of source and destination blocks.
03698 
03699    \param dst - destination block.
03700    \param src - source block.
03701 
03702    @ingroup bitfunc
03703 */
03704 inline 
03705 void bit_block_xor(bm::word_t* BMRESTRICT dst, 
03706                    const bm::word_t* BMRESTRICT src)
03707 {
03708 #ifdef BMVECTOPT
03709     VECT_XOR_ARR(dst, src, src + bm::set_block_size);
03710 #else
03711     const bm::wordop_t* BMRESTRICT wrd_ptr = (wordop_t*) src;
03712     const bm::wordop_t* BMRESTRICT wrd_end = 
03713                             (wordop_t*) (src + bm::set_block_size);
03714     bm::wordop_t* BMRESTRICT dst_ptr = (wordop_t*)dst;
03715 
03716     // Regular XOR operation on the whole block.
03717     do
03718     {
03719         dst_ptr[0] ^= wrd_ptr[0];
03720         dst_ptr[1] ^= wrd_ptr[1];
03721         dst_ptr[2] ^= wrd_ptr[2];
03722         dst_ptr[3] ^= wrd_ptr[3];
03723 
03724         dst_ptr+=4;
03725         wrd_ptr+=4;
03726     } while (wrd_ptr < wrd_end);
03727 #endif
03728     
03729 }
03730 
03731 
03732 /*!
03733    \brief bitblock XOR operation. 
03734 
03735    \param dst - destination block.
03736    \param src - source block.
03737 
03738    \returns pointer on destination block. 
03739     If returned value  equal to src means that block mutation requested. 
03740     NULL is valid return value.
03741 
03742    @ingroup bitfunc
03743 */
03744 inline 
03745 bm::word_t* bit_operation_xor(bm::word_t* BMRESTRICT dst, 
03746                               const bm::word_t* BMRESTRICT src)
03747 {
03748     BM_ASSERT(dst || src);
03749     if (src == dst) return 0;  // XOR rule  
03750 
03751     bm::word_t* ret = dst;
03752 
03753     if (IS_VALID_ADDR(dst))  //  The destination block already exists
03754     {           
03755         if (!src) return dst;
03756         
03757         bit_block_xor(dst, src);
03758     }
03759     else // The destination block does not exist yet
03760     {
03761         if (!src) return dst;      // 1 xor 0 = 1
03762 
03763         // Here we have two cases:
03764         // if dest block is full or zero if zero we need to copy the source
03765         // otherwise XOR loop against 0xFF...
03766         //BM_ASSERT(dst == 0);
03767         return const_cast<bm::word_t*>(src);  // src is the final result               
03768     }
03769     return ret;
03770 }
03771 
03772 /*!
03773    \brief Performs bitblock XOR operation and calculates bitcount of the result. 
03774 
03775    \param src1 - first bit block.
03776    \param src2 - second bit block.
03777 
03778    \returns bitcount value 
03779 
03780    @ingroup bitfunc
03781 */
03782 inline 
03783 bm::id_t bit_operation_xor_count(const bm::word_t* BMRESTRICT src1,
03784                                  const bm::word_t* BMRESTRICT src1_end,
03785                                  const bm::word_t* BMRESTRICT src2)
03786 {
03787     if (IS_EMPTY_BLOCK(src1) || IS_EMPTY_BLOCK(src2))
03788     {
03789         if (IS_EMPTY_BLOCK(src1) && IS_EMPTY_BLOCK(src2))
03790             return 0;
03791         const bm::word_t* block = IS_EMPTY_BLOCK(src1) ? src2 : src1;
03792         return bit_block_calc_count(block, block + (src1_end - src1));
03793     }
03794     return bit_block_xor_count(src1, src1_end, src2);
03795 }
03796 
03797 /*!
03798    \brief Performs bitblock XOR operation test. 
03799 
03800    \param src1 - first bit block.
03801    \param src2 - second bit block.
03802 
03803    \returns non zero value if there are bits
03804 
03805    @ingroup bitfunc
03806 */
03807 inline 
03808 bm::id_t bit_operation_xor_any(const bm::word_t* BMRESTRICT src1,
03809                                const bm::word_t* BMRESTRICT src1_end,
03810                                const bm::word_t* BMRESTRICT src2)
03811 {
03812     if (IS_EMPTY_BLOCK(src1) || IS_EMPTY_BLOCK(src2))
03813     {
03814         if (IS_EMPTY_BLOCK(src1) && IS_EMPTY_BLOCK(src2))
03815             return 0;
03816         const bm::word_t* block = IS_EMPTY_BLOCK(src1) ? src2 : src1;
03817         return !bit_is_all_zero(block, block + (src1_end - src1));
03818     }
03819     return bit_block_xor_any(src1, src1_end, src2);
03820 }
03821 
03822 
03823 /**
03824     \brief Inspects bit block for zero words at the head and at the end 
03825 
03826     If there are no head-tail zeroes output parameters 
03827     head_idx and tail_idx are going to be [0, bm::set_block_size-1].
03828     If block is all-zero head_idx is -1
03829 
03830     \param data - bit block pointer
03831     \param head_idx - index of first non-zero word in block
03832     \param tail_idx - index of the last non-zero word in block
03833 
03834     @ingroup bitfunc
03835 */
03836 inline
03837 void bit_find_head_tail(const bm::word_t* data, 
03838                         unsigned*         head_idx,
03839                         unsigned*         tail_idx)
03840 {
03841     BM_ASSERT(head_idx && tail_idx);
03842     *head_idx = (unsigned)-1;
03843     for (unsigned i = 0; i < bm::set_block_size; ++i) 
03844     {
03845         if (data[i]) 
03846         {
03847             *head_idx = i; 
03848             break;
03849         }
03850     } // for i
03851     if (*head_idx == (unsigned)-1) 
03852     {
03853         return; // all zero block
03854     }
03855 
03856     for (unsigned j = bm::set_block_size-1; j >= *head_idx; --j)
03857     {
03858         if (data[j]) 
03859         {
03860             *tail_idx = j;
03861             break;
03862         }
03863     } // for j
03864 
03865 }
03866 
03867 
03868 
03869 /**
03870     \brief Searches for the next 1 bit in the BIT block
03871     \param data - BIT buffer
03872     \param nbit - bit index to start checking from
03873     \param prev - returns previously checked value
03874 
03875     @ingroup bitfunc
03876 */
03877 inline 
03878 int bit_find_in_block(const bm::word_t* data, 
03879                       unsigned nbit, 
03880                       bm::id_t* prev)
03881 {
03882     register bm::id_t p = *prev;
03883     int found = 0;
03884 
03885     for(;;)
03886     {
03887         unsigned nword  = nbit >> bm::set_word_shift;
03888         if (nword >= bm::set_block_size) break;
03889 
03890         register bm::word_t val = data[nword] >> (p & bm::set_word_mask);
03891 
03892         if (val)
03893         {
03894             while((val & 1) == 0)
03895             {
03896                 val >>= 1;
03897                 ++nbit;
03898                 ++p;
03899             }
03900             ++found;
03901             break;
03902         }
03903         else
03904         {
03905            p    += (bm::set_word_mask + 1) - (nbit & bm::set_word_mask);
03906            nbit += (bm::set_word_mask + 1) - (nbit & bm::set_word_mask);
03907         }
03908     }
03909     *prev = p;
03910     return found;
03911 }
03912 
03913 /*!
03914    \brief Unpacks word into list of ON bit indexes
03915    \param w - value
03916    \param bits - pointer on the result array 
03917    \return number of bits in the list
03918 
03919    @ingroup bitfunc
03920 */
03921 template<typename T,typename B> unsigned bit_list(T w, B* bits)
03922 {
03923     // Note: 4-bit table method works slower than plain check approach
03924     unsigned octet = 0;
03925     B*       bp = bits;
03926     do
03927     {
03928         if (w & 1)   *bp++ = octet + 0;
03929         if (w & 2)   *bp++ = octet + 1;
03930         if (w & 4)   *bp++ = octet + 2;
03931         if (w & 8)   *bp++ = octet + 3;
03932         if (w & 16)  *bp++ = octet + 4;
03933         if (w & 32)  *bp++ = octet + 5;
03934         if (w & 64)  *bp++ = octet + 6;
03935         if (w & 128) *bp++ = octet + 7;
03936 
03937         w >>= 8;
03938         octet += 8;
03939     } while (w);
03940     return (unsigned)(bp - bits);
03941 }
03942 
03943 
03944 /*! @brief Calculates memory overhead for number of gap blocks sharing 
03945            the same memory allocation table (level lengths table).
03946     @ingroup gapfunc
03947 */
03948 template<typename T> 
03949 unsigned gap_overhead(const T* length, 
03950                       const T* length_end, 
03951                       const T* glevel_len)
03952 {
03953     BM_ASSERT(length && length_end && glevel_len);
03954 
03955     unsigned overhead = 0;
03956     for (;length < length_end; ++length)
03957     {
03958         unsigned len = *length;
03959         int level = gap_calc_level(len, glevel_len);
03960         BM_ASSERT(level >= 0 && level < (int)bm::gap_levels);
03961         unsigned capacity = glevel_len[level];
03962         BM_ASSERT(capacity >= len);
03963         overhead += capacity - len;
03964     }
03965     return overhead;
03966 }
03967 
03968 
03969 /*! @brief Finds optimal gap blocks lengths.
03970     @param length - first element of GAP lengths array
03971     @param length_end - end of the GAP lengths array
03972     @param glevel_len - destination GAP lengths array
03973     @ingroup gapfunc
03974 */
03975 
03976 template<typename T>
03977 bool improve_gap_levels(const T* length,
03978                         const T* length_end,
03979                         T*       glevel_len)
03980 {
03981     BM_ASSERT(length && length_end && glevel_len);
03982 
03983     size_t lsize = length_end - length;
03984 
03985     BM_ASSERT(lsize);
03986     
03987     gap_word_t max_len = 0;
03988     unsigned i;
03989     for (i = 0; i < lsize; ++i)
03990     {
03991         if (length[i] > max_len)
03992             max_len = length[i];
03993     }
03994     if (max_len < 5 || lsize <= bm::gap_levels)
03995     {
03996         glevel_len[0] = max_len + 4;
03997         for (i = 1; i < bm::gap_levels; ++i)
03998         {
03999             glevel_len[i] = bm::gap_max_buff_len;
04000         }
04001         return true;
04002     }
04003 
04004     glevel_len[bm::gap_levels-1] = max_len + 5;
04005 
04006     unsigned min_overhead = gap_overhead(length, length_end, glevel_len);
04007     bool is_improved = false;
04008     gap_word_t prev_value = glevel_len[bm::gap_levels-1];
04009     //
04010     // main problem solving loop
04011     //
04012     for (i = bm::gap_levels-2; ; --i)
04013     {
04014         unsigned opt_len = 0;
04015         unsigned j;
04016         bool imp_flag = false;
04017         gap_word_t gap_saved_value = glevel_len[i];
04018         for (j = 0; j < lsize; ++j)
04019         {
04020 //            if (length[j]+4 > prev_value)
04021 //                continue;
04022             
04023             glevel_len[i] = length[j]+4;
04024             unsigned ov = gap_overhead(length, length_end, glevel_len);
04025             if (ov <= min_overhead)
04026             {
04027                 min_overhead = ov;                
04028                 opt_len = length[j]+4;
04029                 imp_flag = true;
04030             }
04031         }
04032         if (imp_flag) {
04033             glevel_len[i] = opt_len; // length[opt_idx]+4;
04034             is_improved = true;
04035         }
04036         else 
04037         {
04038             glevel_len[i] = gap_saved_value;
04039         }
04040         if (i == 0) 
04041             break;
04042         prev_value = glevel_len[i];
04043     }
04044     // 
04045     // Remove duplicates
04046     //
04047 
04048     T val = *glevel_len;
04049     T* gp = glevel_len;
04050     T* res = glevel_len;
04051     for (i = 0; i < bm::gap_levels; ++i)
04052     {
04053         if (val != *gp)
04054         {
04055             val = *gp;
04056             *++res = val;
04057         }
04058         ++gp;
04059     }
04060 
04061     // Filling the "unused" part with max. possible value
04062     while (++res < (glevel_len + bm::gap_levels)) 
04063     {
04064         *res = bm::gap_max_buff_len;
04065     }
04066 
04067     return is_improved;
04068 
04069 }
04070 
04071 
04072 
04073 /**
04074     Bit-block get adapter, takes bitblock and represents it as a 
04075     get_32() accessor function
04076     /internal
04077 */
04078 class bitblock_get_adapter
04079 {
04080 public:
04081     bitblock_get_adapter(const bm::word_t* bit_block) : b_(bit_block) {}
04082     
04083     BMFORCEINLINE
04084     bm::word_t get_32() { return *b_++; }
04085 private:
04086     const bm::word_t*  b_;
04087 };
04088 
04089 
04090 /**
04091     Bit-block store adapter, takes bitblock and saves results into it
04092     /internal
04093 */
04094 class bitblock_store_adapter
04095 {
04096 public:
04097     bitblock_store_adapter(bm::word_t* bit_block) : b_(bit_block) {}
04098     BMFORCEINLINE
04099     void push_back(bm::word_t w) { *b_++ = w; }
04100 private:
04101     bm::word_t* b_;
04102 };
04103 
04104 /**
04105     Bit-block sum adapter, takes values and sums it
04106     /internal
04107 */
04108 class bitblock_sum_adapter
04109 {
04110 public:
04111     bitblock_sum_adapter() : sum_(0) {}
04112     BMFORCEINLINE
04113     void push_back(bm::word_t w) { this->sum_+= w; }
04114     /// Get accumulated sum
04115     bm::word_t sum() const { return this->sum_; }
04116 private:
04117     bm::word_t sum_;
04118 };
04119 
04120 /**
04121     Adapter to get words from a range stream 
04122     (see range serialized bit-block)
04123     \internal
04124 */
04125 template<class DEC> class decoder_range_adapter
04126 {
04127 public: 
04128     decoder_range_adapter(DEC& dec, unsigned from_idx, unsigned to_idx)
04129     : decoder_(dec),
04130       from_(from_idx),
04131       to_(to_idx),
04132       cnt_(0)
04133     {}
04134 
04135     bm::word_t get_32()
04136     {
04137         if (cnt_ < from_ || cnt_ > to_)
04138         {    
04139             ++cnt_; return 0;
04140         }
04141         ++cnt_;
04142         return decoder_.get_32();
04143     }
04144 
04145 private:
04146     DEC&     decoder_;
04147     unsigned from_;
04148     unsigned to_;
04149     unsigned cnt_;
04150 };
04151 
04152 
04153 /*!
04154     Abstract recombination algorithm for two bit-blocks
04155     Bit blocks can come as dserialization decoders or bit-streams
04156 */
04157 template<class It1, class It2, class BinaryOp, class Encoder>
04158 void bit_recomb(It1& it1, It2& it2, 
04159                 BinaryOp& op, 
04160                 Encoder& enc, 
04161                 unsigned block_size = bm::set_block_size)
04162 {
04163     for (unsigned i = 0; i < block_size; ++i)
04164     {
04165         bm::word_t w1 = it1.get_32();
04166         bm::word_t w2 = it2.get_32();
04167         bm::word_t w = op(w1, w2);
04168         enc.push_back( w );
04169     } // for
04170 }
04171 
04172 /// Bit AND functor
04173 template<typename W> struct bit_AND
04174 {
04175     W operator()(W w1, W w2) { return w1 & w2; }
04176 };
04177 
04178 /// Bit OR functor
04179 template<typename W> struct bit_OR
04180 {
04181     W operator()(W w1, W w2) { return w1 | w2; }
04182 };
04183 
04184 /// Bit SUB functor
04185 template<typename W> struct bit_SUB
04186 {
04187     W operator()(W w1, W w2) { return w1 & ~w2; }
04188 };
04189 
04190 /// Bit XOR functor
04191 template<typename W> struct bit_XOR
04192 {
04193     W operator()(W w1, W w2) { return w1 ^ w2; }
04194 };
04195 
04196 /// Bit ASSIGN functor
04197 template<typename W> struct bit_ASSIGN
04198 {
04199     W operator()(W w1, W w2) { return w2; }
04200 };
04201 
04202 /// Bit COUNT functor
04203 template<typename W> struct bit_COUNT
04204 {
04205     W operator()(W w1, W w2) 
04206     {
04207         w1 = 0;
04208         BM_INCWORD_BITCOUNT(w1, w2);
04209         return w1;
04210     }
04211 };
04212 
04213 /// Bit COUNT AND functor
04214 template<typename W> struct bit_COUNT_AND
04215 {
04216     W operator()(W w1, W w2) 
04217     {
04218         W r = 0;
04219         BM_INCWORD_BITCOUNT(r, w1 & w2);
04220         return r;
04221     }
04222 };
04223 
04224 /// Bit COUNT XOR functor
04225 template<typename W> struct bit_COUNT_XOR
04226 {
04227     W operator()(W w1, W w2) 
04228     {
04229         W r = 0;
04230         BM_INCWORD_BITCOUNT(r, w1 ^ w2);
04231         return r;
04232     }
04233 };
04234 
04235 /// Bit COUNT OR functor
04236 template<typename W> struct bit_COUNT_OR
04237 {
04238     W operator()(W w1, W w2) 
04239     {
04240         W r = 0;
04241         BM_INCWORD_BITCOUNT(r, w1 | w2);
04242         return r;
04243     }
04244 };
04245 
04246 
04247 /// Bit COUNT SUB AB functor
04248 template<typename W> struct bit_COUNT_SUB_AB
04249 {
04250     W operator()(W w1, W w2) 
04251     {
04252         W r = 0;
04253         BM_INCWORD_BITCOUNT(r, w1 & (~w2));
04254         return r;
04255     }
04256 };
04257 
04258 /// Bit SUB BA functor
04259 template<typename W> struct bit_COUNT_SUB_BA
04260 {
04261     W operator()(W w1, W w2) 
04262     {
04263         W r = 0;
04264         BM_INCWORD_BITCOUNT(r, w2 & (~w1));
04265         return r;
04266     }
04267 };
04268 
04269 /// Bit COUNT A functor
04270 template<typename W> struct bit_COUNT_A
04271 {
04272     W operator()(W w1, W w2) 
04273     {
04274         W r = 0;
04275         BM_INCWORD_BITCOUNT(r, w1);
04276         return r;
04277     }
04278 };
04279 
04280 /// Bit COUNT B functor
04281 template<typename W> struct bit_COUNT_B
04282 {
04283     W operator()(W w1, W w2) 
04284     {
04285         W r = 0;
04286         BM_INCWORD_BITCOUNT(r, w2);
04287         return r;
04288     }
04289 };
04290 
04291 typedef 
04292 void (*gap_operation_to_bitset_func_type)(unsigned*, 
04293                                           const gap_word_t*);
04294 
04295 typedef 
04296 gap_word_t* (*gap_operation_func_type)(const gap_word_t*,
04297                                        const gap_word_t*,
04298                                        gap_word_t*);
04299 
04300 typedef
04301 bm::id_t (*bit_operation_count_func_type)(const bm::word_t* ,
04302                                           const bm::word_t*, 
04303                                           const bm::word_t*);
04304 
04305 
04306 template<bool T> 
04307 struct operation_functions
04308 {
04309     static 
04310         gap_operation_to_bitset_func_type gap2bit_table_[bm::set_END];
04311     static 
04312         gap_operation_func_type gapop_table_[bm::set_END];
04313     static
04314         bit_operation_count_func_type bit_op_count_table_[bm::set_END];
04315 
04316     static
04317     gap_operation_to_bitset_func_type gap_op_to_bit(unsigned i)
04318     {
04319         return gap2bit_table_[i];
04320     }
04321 
04322     static
04323     gap_operation_func_type gap_operation(unsigned i)
04324     {
04325         return gapop_table_[i];
04326     }
04327 
04328     static
04329     bit_operation_count_func_type bit_operation_count(unsigned i)
04330     {
04331         return bit_op_count_table_[i];
04332     }
04333 };
04334 
04335 template<bool T>
04336 gap_operation_to_bitset_func_type 
04337 operation_functions<T>::gap2bit_table_[bm::set_END] = {
04338     &gap_and_to_bitset<bm::gap_word_t>,    // set_AND
04339     &gap_add_to_bitset<bm::gap_word_t>,    // set_OR
04340     &gap_sub_to_bitset<bm::gap_word_t>,    // set_SUB
04341     &gap_xor_to_bitset<bm::gap_word_t>,    // set_XOR
04342     0
04343 };
04344 
04345 template<bool T>
04346 gap_operation_func_type 
04347 operation_functions<T>::gapop_table_[bm::set_END] = {
04348     &gap_operation_and,    // set_AND
04349     &gap_operation_or,     // set_OR
04350     &gap_operation_sub,    // set_SUB
04351     &gap_operation_xor,    // set_XOR
04352     0
04353 };
04354 
04355 
04356 template<bool T>
04357 bit_operation_count_func_type 
04358 operation_functions<T>::bit_op_count_table_[bm::set_END] = {
04359     0,                            // set_AND
04360     0,                            // set_OR
04361     0,                            // set_SUB
04362     0,                            // set_XOR
04363     0,                            // set_ASSIGN
04364     0,                            // set_COUNT
04365     &bit_operation_and_count,     // set_COUNT_AND
04366     &bit_operation_xor_count,     // set_COUNT_XOR
04367     &bit_operation_or_count,      // set_COUNT_OR
04368     &bit_operation_sub_count,     // set_COUNT_SUB_AB
04369     &bit_operation_sub_count_inv, // set_COUNT_SUB_BA
04370     0,                            // set_COUNT_A
04371     0,                            // set_COUNT_B
04372 };
04373 
04374 } // namespace bm
04375 
04376 #endif
04377 

Generated on Sun Aug 5 14:12:26 2007 for BitMagic by  doxygen 1.4.1