← Back to branch summary

~ubuntu-branches/ubuntu/trusty/bmagic/trusty

« back to all changes in this revision

Viewing changes to src/bmvmin.h

  • Committer: Bazaar Package Importer
  • Author(s): Andres Salomon
  • Date: 2008-01-05 23:58:56 UTC
  • mfrom: (1.1.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20080105235856-2kmxhxkz14qjy9ia
Tags: 3.5.0-1
* New upstream release.
* Add tcpp.dpatch.  This stops tests/stress/t.cpp from including
  ncbi_pch.hpp.  As far as I can tell, NCBI is not used at all, I have
  no idea where that came from..
* Silence some lintian warnings; binary-arch-rules-but-pkg-is-arch-indep
  and ancient-standards-version.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/bmvmin.h
1
 
/*
2
 
Copyright(c) 2002-2005 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
3
 
 
4
 
Permission is hereby granted, free of charge, to any person 
5
 
obtaining a copy of this software and associated documentation 
6
 
files (the "Software"), to deal in the Software without restriction, 
7
 
including without limitation the rights to use, copy, modify, merge, 
8
 
publish, distribute, sublicense, and/or sell copies of the Software, 
9
 
and to permit persons to whom the Software is furnished to do so, 
10
 
subject to the following conditions:
11
 
 
12
 
The above copyright notice and this permission notice shall be included 
13
 
in all copies or substantial portions of the Software.
14
 
 
15
 
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
16
 
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES 
17
 
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 
18
 
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, 
19
 
DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 
20
 
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 
21
 
OTHER DEALINGS IN THE SOFTWARE.
22
 
 
23
 
For more information please visit:  http://bmagic.sourceforge.net
24
 
 
25
 
*/
26
 
 
27
 
#ifndef BMVMIN__H__INCLUDED__
28
 
#define BMVMIN__H__INCLUDED__
29
 
 
30
 
namespace bm
31
 
{
32
 
 
33
 
 
34
 
#define BM_MINISET_GAPLEN (bm::gap_len_table<true>::_len[0])
35
 
#define BM_MINISET_ARRSIZE(x) ((x / 32) + ( (x % 32) && 1 ))
36
 
 
37
 
/*! @defgroup mset Small sets functionality
38
 
 *  Templates in this group are used to keep block types in BM library.
39
 
 *  Classes of this group can tune bvector template (MS parameter)
40
 
 *  for best performance or minimal memory usage.
41
 
 *  @ingroup bmagic
42
 
 *  @{
43
 
 */
44
 
 
45
 
 
46
 
/*!
47
 
    @brief Template class implements memory saving set functionality
48
 
    
49
 
    Template can be used as template parameter for bvector if we 
50
 
    want to tune bvector for minimal memory consumption.
51
 
 
52
 
    @sa bvmini
53
 
*/
54
 
template <class A, size_t N> class miniset
55
 
{
56
 
public:
57
 
 
58
 
    miniset() 
59
 
        : m_buf(0),
60
 
          m_type(1)
61
 
    {}
62
 
 
63
 
    miniset(const miniset& mset)
64
 
    {
65
 
        if (mset.m_buf)
66
 
        {
67
 
            if (mset.m_type)
68
 
                init_gapbuf(mset.m_buf);
69
 
            else
70
 
                init_bitbuf(mset.m_buf);
71
 
        }
72
 
        else
73
 
        {
74
 
            m_type = mset.m_type;
75
 
            m_buf = 0;
76
 
        }
77
 
    }
78
 
 
79
 
    ~miniset()
80
 
    {
81
 
        if (m_buf)
82
 
        {
83
 
            A::deallocate(m_buf, m_type ? 
84
 
                (BM_MINISET_GAPLEN / (sizeof(bm::word_t) / sizeof(bm::gap_word_t)))
85
 
                : 
86
 
                (BM_MINISET_ARRSIZE(N)));
87
 
        }
88
 
    }
89
 
 
90
 
    /// Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
91
 
    unsigned test(bm::id_t n) const 
92
 
    { 
93
 
        return
94
 
            !m_buf ? 0 
95
 
            :
96
 
            m_type ? 
97
 
              gap_test((gap_word_t*)m_buf, n)
98
 
              : 
99
 
              m_buf[n>>bm::set_word_shift] & (1<<(n & bm::set_word_mask));
100
 
    }
101
 
 
102
 
    void set(bm::id_t n, bool val=true)
103
 
    {
104
 
        if (m_type == 0)
105
 
        {
106
 
            if (!m_buf)
107
 
            {
108
 
                if (!val) return;
109
 
                init_bitbuf(0);
110
 
            }
111
 
 
112
 
            unsigned nword  = n >> bm::set_word_shift; 
113
 
            unsigned mask = unsigned(1) << (n & bm::set_word_mask);
114
 
 
115
 
            val ? (m_buf[nword] |= mask) : (m_buf[nword] &= ~mask);
116
 
        }
117
 
        else
118
 
        {
119
 
            if (!m_buf)
120
 
            {
121
 
                if (!val) return;
122
 
                init_gapbuf(0);
123
 
            }
124
 
            
125
 
            unsigned is_set;
126
 
            unsigned new_block_len = 
127
 
                gap_set_value(val, (gap_word_t*)m_buf, n, &is_set);
128
 
 
129
 
            if (new_block_len > unsigned(BM_MINISET_GAPLEN-4))
130
 
            {
131
 
                convert_buf();
132
 
            }
133
 
        }
134
 
    }
135
 
 
136
 
    unsigned mem_used() const
137
 
    {
138
 
        return sizeof(*this) +
139
 
               m_buf ? 
140
 
                 (m_type ? (BM_MINISET_GAPLEN * sizeof(gap_word_t))
141
 
                        : (BM_MINISET_ARRSIZE(N) * sizeof(bm::word_t)))
142
 
                : 0; 
143
 
    }
144
 
 
145
 
    void swap(miniset& mset)
146
 
    {
147
 
        bm::word_t* buftmp = m_buf;
148
 
        m_buf = mset.m_buf;
149
 
        mset.m_buf = buftmp;
150
 
        unsigned typetmp = m_type;
151
 
        m_type = mset.m_type;
152
 
        mset.m_type = typetmp;
153
 
    }
154
 
 
155
 
 
156
 
private:
157
 
 
158
 
    void init_bitbuf(bm::word_t* buf)
159
 
    {
160
 
        unsigned arr_size = BM_MINISET_ARRSIZE(N);
161
 
        m_buf = A::allocate(arr_size, 0);
162
 
        if (buf)
163
 
        {
164
 
            ::memcpy(m_buf, buf, arr_size * sizeof(bm::word_t));
165
 
        }
166
 
        else
167
 
        {
168
 
            ::memset(m_buf, 0, arr_size * sizeof(bm::word_t));
169
 
        }
170
 
        m_type = 0;
171
 
    }
172
 
 
173
 
    void init_gapbuf(bm::word_t* buf)
174
 
    {
175
 
        unsigned arr_size = 
176
 
            BM_MINISET_GAPLEN / (sizeof(bm::word_t) / sizeof(bm::gap_word_t));
177
 
        m_buf = A::allocate(arr_size, 0);
178
 
        if (buf)
179
 
        {
180
 
            ::memcpy(m_buf, buf, arr_size * sizeof(bm::word_t));
181
 
        }
182
 
        else
183
 
        {
184
 
            *m_buf = 0;
185
 
            gap_set_all((gap_word_t*)m_buf, bm::gap_max_bits, 0);
186
 
        }
187
 
        m_type = 1;
188
 
    }
189
 
 
190
 
    void convert_buf()
191
 
    {
192
 
        unsigned arr_size = BM_MINISET_ARRSIZE(N);
193
 
        bm::word_t* buf = A::allocate(arr_size, 0);
194
 
 
195
 
        gap_convert_to_bitset(buf, (gap_word_t*) m_buf, arr_size);
196
 
        arr_size = 
197
 
            BM_MINISET_GAPLEN / (sizeof(bm::word_t) / sizeof(bm::gap_word_t));
198
 
        A::deallocate(m_buf, arr_size);
199
 
        m_buf = buf;
200
 
        m_type = 0;
201
 
    }
202
 
 
203
 
private:
204
 
    bm::word_t*   m_buf;      //!< Buffer pointer
205
 
    unsigned      m_type;     //!< buffer type (0-bit, 1-gap)
206
 
};
207
 
 
208
 
 
209
 
/*!
210
 
    @brief Mini bitvector used in bvector template to keep block type flags
211
 
    
212
 
    Template is used as a default template parameter MS for bvector  
213
 
    Offers maximum performance comparing to miniset.
214
 
 
215
 
    @sa miniset
216
 
*/
217
 
template<size_t N> class bvmini
218
 
{
219
 
public:
220
 
 
221
 
    bvmini(int start_strategy = 0) 
222
 
    {
223
 
        ::memset(m_buf, 0, sizeof(m_buf));
224
 
    }
225
 
 
226
 
    bvmini(const bvmini& mset)
227
 
    {
228
 
        ::memcpy(m_buf, mset.m_buf, sizeof(m_buf));
229
 
    }
230
 
 
231
 
 
232
 
    /// Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
233
 
    unsigned test(bm::id_t n) const 
234
 
    { 
235
 
        return m_buf[n>>bm::set_word_shift] & (1<<(n & bm::set_word_mask));
236
 
    }
237
 
 
238
 
    void set(bm::id_t n, bool val=true)
239
 
    {
240
 
        unsigned nword  = n >> bm::set_word_shift; 
241
 
        unsigned mask = unsigned(1) << (n & bm::set_word_mask);
242
 
 
243
 
        val ? (m_buf[nword] |= mask) : (m_buf[nword] &= ~mask);
244
 
    }
245
 
 
246
 
    unsigned mem_used() const
247
 
    {
248
 
        return sizeof(*this);
249
 
    }
250
 
 
251
 
    void swap(bvmini& mset)
252
 
    {
253
 
        for (unsigned i = 0; i < BM_MINISET_ARRSIZE(N); ++i)
254
 
        {
255
 
            bm::word_t tmp = m_buf[i];
256
 
            m_buf[i] = mset.m_buf[i];
257
 
            mset.m_buf[i] = tmp;
258
 
        }
259
 
    }
260
 
 
261
 
private:
262
 
    bm::word_t   m_buf[BM_MINISET_ARRSIZE(N)];
263
 
};
264
 
 
265
 
 
266
 
/*!@} */
267
 
 
268
 
/*!
269
 
    @brief Bitvector class with very limited functionality.
270
 
 
271
 
    Class implements simple bitset and used for internal 
272
 
    and testing purposes. 
273
 
*/
274
 
template<class A> class bvector_mini
275
 
{
276
 
public:
277
 
    bvector_mini(unsigned size) 
278
 
      : m_buf(0),
279
 
        m_size(size)
280
 
    {
281
 
        unsigned arr_size = (size / 32) + 1; 
282
 
        m_buf = A::allocate(arr_size, 0);
283
 
        ::memset(m_buf, 0, arr_size * sizeof(unsigned));
284
 
    }
285
 
    bvector_mini(const bvector_mini& bvect)
286
 
       : m_size(bvect.m_size)
287
 
    {
288
 
        unsigned arr_size = (m_size / 32) + 1;
289
 
        m_buf = A::allocate(arr_size, 0);
290
 
        ::memcpy(m_buf, bvect.m_buf, arr_size * sizeof(unsigned));        
291
 
    }
292
 
 
293
 
    ~bvector_mini()
294
 
    {
295
 
        A::deallocate(m_buf, (m_size / 32) + 1); 
296
 
    }
297
 
 
298
 
    /// Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
299
 
    int is_bit_true(unsigned pos) const
300
 
    {
301
 
        unsigned char  mask = (unsigned char)((char)0x1 << (pos & 7));
302
 
        unsigned char* offs = (unsigned char*)m_buf + (pos >> 3); // m_buf + (pos/8)
303
 
 
304
 
        return (*offs) & mask;
305
 
    }
306
 
 
307
 
    /// Sets bit number pos to 1
308
 
    void set_bit(unsigned pos)
309
 
    {
310
 
        unsigned char  mask = (unsigned char)(0x1 << (pos & 7));
311
 
        unsigned char* offs = (unsigned char*)m_buf + (pos >> 3); 
312
 
        *offs |= mask;
313
 
    }
314
 
 
315
 
 
316
 
    /// Sets bit number pos to 0
317
 
    void clear_bit(unsigned pos)
318
 
    {
319
 
        unsigned char  mask = (unsigned char)(0x1 << (pos & 7));
320
 
        unsigned char* offs = (unsigned char*)m_buf + (pos >> 3); 
321
 
 
322
 
        *offs &= ~mask;
323
 
    }
324
 
 
325
 
    /// Counts number of bits ON 
326
 
    unsigned bit_count() const
327
 
    {
328
 
        register unsigned count = 0;
329
 
        const unsigned* end = m_buf + (m_size / 32)+1;    
330
 
 
331
 
        for (unsigned* start = m_buf; start < end; ++start)
332
 
        {
333
 
            register unsigned value = *start;
334
 
            for (count += (value!=0); value &= value - 1; ++count);
335
 
        }
336
 
        return count;
337
 
    }
338
 
 
339
 
    /// Comparison.
340
 
    int compare(const bvector_mini& bvect)
341
 
    {
342
 
        unsigned cnt1 = bit_count();
343
 
        unsigned cnt2 = bvect.bit_count();
344
 
 
345
 
        if (!cnt1 && !cnt2) return 0;
346
 
 
347
 
        unsigned cnt_min = cnt1 < cnt2 ? cnt1 : cnt2;
348
 
 
349
 
        if (!cnt_min) return cnt1 ? 1 : -1;
350
 
 
351
 
        unsigned idx1 = get_first();
352
 
        unsigned idx2 = bvect.get_first();
353
 
 
354
 
        for (unsigned i = 0; i < cnt_min; ++i)
355
 
        {
356
 
            if (idx1 != idx2)
357
 
            {
358
 
                return idx1 < idx2 ? 1 : -1;
359
 
            }
360
 
            idx1 = get_next(idx1);
361
 
            idx2 = bvect.get_next(idx2);
362
 
        }
363
 
 
364
 
        BM_ASSERT(idx1==0 || idx2==0);
365
 
 
366
 
        if (idx1 != idx2)
367
 
        {
368
 
            if (!idx1) return -1;
369
 
            if (!idx2) return  1;
370
 
            return idx1 < idx2 ? 1 : -1;
371
 
        }
372
 
 
373
 
        return 0;
374
 
    }
375
 
 
376
 
 
377
 
    /// Returns index of the first ON bit
378
 
    unsigned get_first() const
379
 
    {
380
 
        unsigned pos = 0;
381
 
        const unsigned char* ptr = (unsigned char*) m_buf;
382
 
 
383
 
        for (unsigned i = 0; i < (m_size/8)+1; ++i)
384
 
        {
385
 
            register unsigned char w = ptr[i];
386
 
 
387
 
 
388
 
            if (w != 0)
389
 
            {
390
 
                while ((w & 1) == 0)
391
 
                {
392
 
                    w >>= 1;
393
 
                    ++pos;
394
 
                }
395
 
                return pos;
396
 
            }
397
 
            pos += sizeof(unsigned char) * 8;
398
 
        }
399
 
        return 0;
400
 
    }
401
 
 
402
 
 
403
 
    /// Returns index of next bit, which is ON
404
 
    unsigned get_next(unsigned idx) const
405
 
    {
406
 
        register unsigned i;
407
 
 
408
 
        for (i = idx+1; i < m_size; ++i)
409
 
        {
410
 
            unsigned char* offs = (unsigned char*)m_buf + (i >> 3); 
411
 
            if (*offs)
412
 
            {
413
 
                unsigned char mask = (unsigned char)((char)0x1 << (i & 7));
414
 
 
415
 
                if (*offs & mask)
416
 
                {
417
 
                    return i;
418
 
                }
419
 
            }
420
 
            else
421
 
            {
422
 
                i += 7;
423
 
            }
424
 
        }
425
 
        return 0;
426
 
    }
427
 
 
428
 
 
429
 
    void combine_and(const bvector_mini& bvect)
430
 
    {
431
 
        const unsigned* end = m_buf + (m_size / 32)+1;
432
 
    
433
 
        const unsigned* src = bvect.get_buf();
434
 
 
435
 
        for (unsigned* start = m_buf; start < end; ++start)
436
 
        {
437
 
            *start &= *src++;
438
 
        }
439
 
    }
440
 
 
441
 
    void combine_xor(const bvector_mini& bvect)
442
 
    {
443
 
        const unsigned* end = m_buf + (m_size / 32)+1;
444
 
    
445
 
        const unsigned* src = bvect.get_buf();
446
 
 
447
 
        for (unsigned* start = m_buf; start < end; ++start)
448
 
        {
449
 
            *start ^= *src++;
450
 
        }
451
 
    }
452
 
 
453
 
 
454
 
    void combine_or(const bvector_mini& bvect)
455
 
    {
456
 
        const unsigned* end = m_buf + (m_size / 32)+1;
457
 
    
458
 
        const unsigned* src = bvect.get_buf();
459
 
 
460
 
        for (unsigned* start = m_buf; start < end; ++start)
461
 
        {
462
 
            *start |= *src++;
463
 
        }
464
 
    }
465
 
 
466
 
    void combine_sub(const bvector_mini& bvect)
467
 
    {
468
 
        const unsigned* end = m_buf + (m_size / 32)+1;
469
 
    
470
 
        const unsigned* src = bvect.get_buf();
471
 
 
472
 
        for (unsigned* start = m_buf; start < end; ++start)
473
 
        {
474
 
            *start &= ~(*src++);
475
 
        }
476
 
    }
477
 
 
478
 
    const unsigned* get_buf() const { return m_buf; }
479
 
    unsigned mem_used() const
480
 
    {
481
 
        return sizeof(bvector_mini) + (m_size / 32) + 1;
482
 
    }
483
 
 
484
 
    void swap(bvector_mini& bvm)
485
 
    {
486
 
        BM_ASSERT(m_size == bvm.m_size);
487
 
        bm::word_t* buftmp = m_buf;
488
 
        m_buf = bvm.m_buf;
489
 
        bvm.m_buf = buftmp;
490
 
    }
491
 
 
492
 
private:
493
 
    bm::word_t*   m_buf;
494
 
    unsigned      m_size;
495
 
};
496
 
 
497
 
 
498
 
 
499
 
} // namespace bm
500
 
 
501
 
#endif
 
1
/*
 
2
Copyright(c) 2002-2005 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
 
3
 
 
4
Permission is hereby granted, free of charge, to any person 
 
5
obtaining a copy of this software and associated documentation 
 
6
files (the "Software"), to deal in the Software without restriction, 
 
7
including without limitation the rights to use, copy, modify, merge, 
 
8
publish, distribute, sublicense, and/or sell copies of the Software, 
 
9
and to permit persons to whom the Software is furnished to do so, 
 
10
subject to the following conditions:
 
11
 
 
12
The above copyright notice and this permission notice shall be included 
 
13
in all copies or substantial portions of the Software.
 
14
 
 
15
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
 
16
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES 
 
17
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 
 
18
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, 
 
19
DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 
 
20
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 
 
21
OTHER DEALINGS IN THE SOFTWARE.
 
22
 
 
23
For more information please visit:  http://bmagic.sourceforge.net
 
24
 
 
25
*/
 
26
 
 
27
#ifndef BMVMIN__H__INCLUDED__
 
28
#define BMVMIN__H__INCLUDED__
 
29
 
 
30
namespace bm
 
31
{
 
32
 
 
33
 
 
34
#define BM_MINISET_GAPLEN (bm::gap_len_table<true>::_len[0])
 
35
#define BM_MINISET_ARRSIZE(x) ((x / 32) + ( (x % 32) && 1 ))
 
36
 
 
37
/*! @defgroup mset Small sets functionality
 
38
 *  Templates in this group are used to keep block types in BM library.
 
39
 *  Classes of this group can tune bvector template (MS parameter)
 
40
 *  for best performance or minimal memory usage.
 
41
 *  @ingroup bmagic
 
42
 *  @{
 
43
 */
 
44
 
 
45
 
 
46
/*!
 
47
    @brief Template class implements memory saving set functionality
 
48
    
 
49
    Template can be used as template parameter for bvector if we 
 
50
    want to tune bvector for minimal memory consumption.
 
51
 
 
52
    @sa bvmini
 
53
*/
 
54
template <class A, size_t N> class miniset
 
55
{
 
56
public:
 
57
 
 
58
    miniset() 
 
59
        : m_buf(0),
 
60
          m_type(1)
 
61
    {}
 
62
 
 
63
    miniset(const miniset& mset)
 
64
    {
 
65
        if (mset.m_buf)
 
66
        {
 
67
            if (mset.m_type)
 
68
                init_gapbuf(mset.m_buf);
 
69
            else
 
70
                init_bitbuf(mset.m_buf);
 
71
        }
 
72
        else
 
73
        {
 
74
            m_type = mset.m_type;
 
75
            m_buf = 0;
 
76
        }
 
77
    }
 
78
 
 
79
    ~miniset()
 
80
    {
 
81
        if (m_buf)
 
82
        {
 
83
            A::deallocate(m_buf, m_type ? 
 
84
                (BM_MINISET_GAPLEN / (sizeof(bm::word_t) / sizeof(bm::gap_word_t)))
 
85
                : 
 
86
                (BM_MINISET_ARRSIZE(N)));
 
87
        }
 
88
    }
 
89
 
 
90
    /// Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
 
91
    unsigned test(bm::id_t n) const 
 
92
    { 
 
93
        return
 
94
            !m_buf ? 0 
 
95
            :
 
96
            m_type ? 
 
97
              gap_test((gap_word_t*)m_buf, n)
 
98
              : 
 
99
              m_buf[n>>bm::set_word_shift] & (1<<(n & bm::set_word_mask));
 
100
    }
 
101
 
 
102
    void set(bm::id_t n, bool val=true)
 
103
    {
 
104
        if (m_type == 0)
 
105
        {
 
106
            if (!m_buf)
 
107
            {
 
108
                if (!val) return;
 
109
                init_bitbuf(0);
 
110
            }
 
111
 
 
112
            unsigned nword  = n >> bm::set_word_shift; 
 
113
            unsigned mask = unsigned(1) << (n & bm::set_word_mask);
 
114
 
 
115
            val ? (m_buf[nword] |= mask) : (m_buf[nword] &= ~mask);
 
116
        }
 
117
        else
 
118
        {
 
119
            if (!m_buf)
 
120
            {
 
121
                if (!val) return;
 
122
                init_gapbuf(0);
 
123
            }
 
124
            
 
125
            unsigned is_set;
 
126
            unsigned new_block_len = 
 
127
                gap_set_value(val, (gap_word_t*)m_buf, n, &is_set);
 
128
 
 
129
            if (new_block_len > unsigned(BM_MINISET_GAPLEN-4))
 
130
            {
 
131
                convert_buf();
 
132
            }
 
133
        }
 
134
    }
 
135
 
 
136
    unsigned mem_used() const
 
137
    {
 
138
        return sizeof(*this) +
 
139
               m_buf ? 
 
140
                 (m_type ? (BM_MINISET_GAPLEN * sizeof(gap_word_t))
 
141
                        : (BM_MINISET_ARRSIZE(N) * sizeof(bm::word_t)))
 
142
                : 0; 
 
143
    }
 
144
 
 
145
    void swap(miniset& mset)
 
146
    {
 
147
        bm::word_t* buftmp = m_buf;
 
148
        m_buf = mset.m_buf;
 
149
        mset.m_buf = buftmp;
 
150
        unsigned typetmp = m_type;
 
151
        m_type = mset.m_type;
 
152
        mset.m_type = typetmp;
 
153
    }
 
154
 
 
155
 
 
156
private:
 
157
 
 
158
    void init_bitbuf(bm::word_t* buf)
 
159
    {
 
160
        unsigned arr_size = BM_MINISET_ARRSIZE(N);
 
161
        m_buf = A::allocate(arr_size, 0);
 
162
        if (buf)
 
163
        {
 
164
            ::memcpy(m_buf, buf, arr_size * sizeof(bm::word_t));
 
165
        }
 
166
        else
 
167
        {
 
168
            ::memset(m_buf, 0, arr_size * sizeof(bm::word_t));
 
169
        }
 
170
        m_type = 0;
 
171
    }
 
172
 
 
173
    void init_gapbuf(bm::word_t* buf)
 
174
    {
 
175
        unsigned arr_size = 
 
176
            BM_MINISET_GAPLEN / (sizeof(bm::word_t) / sizeof(bm::gap_word_t));
 
177
        m_buf = A::allocate(arr_size, 0);
 
178
        if (buf)
 
179
        {
 
180
            ::memcpy(m_buf, buf, arr_size * sizeof(bm::word_t));
 
181
        }
 
182
        else
 
183
        {
 
184
            *m_buf = 0;
 
185
            gap_set_all((gap_word_t*)m_buf, bm::gap_max_bits, 0);
 
186
        }
 
187
        m_type = 1;
 
188
    }
 
189
 
 
190
    void convert_buf()
 
191
    {
 
192
        unsigned arr_size = BM_MINISET_ARRSIZE(N);
 
193
        bm::word_t* buf = A::allocate(arr_size, 0);
 
194
 
 
195
        gap_convert_to_bitset(buf, (gap_word_t*) m_buf, arr_size);
 
196
        arr_size = 
 
197
            BM_MINISET_GAPLEN / (sizeof(bm::word_t) / sizeof(bm::gap_word_t));
 
198
        A::deallocate(m_buf, arr_size);
 
199
        m_buf = buf;
 
200
        m_type = 0;
 
201
    }
 
202
 
 
203
private:
 
204
    bm::word_t*   m_buf;      //!< Buffer pointer
 
205
    unsigned      m_type;     //!< buffer type (0-bit, 1-gap)
 
206
};
 
207
 
 
208
 
 
209
/*!
 
210
    @brief Mini bitvector used in bvector template to keep block type flags
 
211
    
 
212
    Template is used as a default template parameter MS for bvector  
 
213
    Offers maximum performance comparing to miniset.
 
214
 
 
215
    @sa miniset
 
216
*/
 
217
template<size_t N> class bvmini
 
218
{
 
219
public:
 
220
 
 
221
    bvmini(int start_strategy = 0) 
 
222
    {
 
223
        ::memset(m_buf, 0, sizeof(m_buf));
 
224
    }
 
225
 
 
226
    bvmini(const bvmini& mset)
 
227
    {
 
228
        ::memcpy(m_buf, mset.m_buf, sizeof(m_buf));
 
229
    }
 
230
 
 
231
 
 
232
    /// Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
 
233
    unsigned test(bm::id_t n) const 
 
234
    { 
 
235
        return m_buf[n>>bm::set_word_shift] & (1<<(n & bm::set_word_mask));
 
236
    }
 
237
 
 
238
    void set(bm::id_t n, bool val=true)
 
239
    {
 
240
        unsigned nword  = n >> bm::set_word_shift; 
 
241
        unsigned mask = unsigned(1) << (n & bm::set_word_mask);
 
242
 
 
243
        val ? (m_buf[nword] |= mask) : (m_buf[nword] &= ~mask);
 
244
    }
 
245
 
 
246
    unsigned mem_used() const
 
247
    {
 
248
        return sizeof(*this);
 
249
    }
 
250
 
 
251
    void swap(bvmini& mset)
 
252
    {
 
253
        for (unsigned i = 0; i < BM_MINISET_ARRSIZE(N); ++i)
 
254
        {
 
255
            bm::word_t tmp = m_buf[i];
 
256
            m_buf[i] = mset.m_buf[i];
 
257
            mset.m_buf[i] = tmp;
 
258
        }
 
259
    }
 
260
 
 
261
private:
 
262
    bm::word_t   m_buf[BM_MINISET_ARRSIZE(N)];
 
263
};
 
264
 
 
265
 
 
266
/*!@} */
 
267
 
 
268
/*!
 
269
    @brief Bitvector class with very limited functionality.
 
270
 
 
271
    Class implements simple bitset and used for internal 
 
272
    and testing purposes. 
 
273
*/
 
274
template<class A> class bvector_mini
 
275
{
 
276
public:
 
277
    bvector_mini(unsigned size) 
 
278
      : m_buf(0),
 
279
        m_size(size)
 
280
    {
 
281
        unsigned arr_size = (size / 32) + 1; 
 
282
        m_buf = A::allocate(arr_size, 0);
 
283
        ::memset(m_buf, 0, arr_size * sizeof(unsigned));
 
284
    }
 
285
    bvector_mini(const bvector_mini& bvect)
 
286
       : m_size(bvect.m_size)
 
287
    {
 
288
        unsigned arr_size = (m_size / 32) + 1;
 
289
        m_buf = A::allocate(arr_size, 0);
 
290
        ::memcpy(m_buf, bvect.m_buf, arr_size * sizeof(unsigned));        
 
291
    }
 
292
 
 
293
    ~bvector_mini()
 
294
    {
 
295
        A::deallocate(m_buf, (m_size / 32) + 1); 
 
296
    }
 
297
 
 
298
    /// Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
 
299
    int is_bit_true(unsigned pos) const
 
300
    {
 
301
        unsigned char  mask = (unsigned char)((char)0x1 << (pos & 7));
 
302
        unsigned char* offs = (unsigned char*)m_buf + (pos >> 3); // m_buf + (pos/8)
 
303
 
 
304
        return (*offs) & mask;
 
305
    }
 
306
 
 
307
    /// Sets bit number pos to 1
 
308
    void set_bit(unsigned pos)
 
309
    {
 
310
        unsigned char  mask = (unsigned char)(0x1 << (pos & 7));
 
311
        unsigned char* offs = (unsigned char*)m_buf + (pos >> 3); 
 
312
        *offs |= mask;
 
313
    }
 
314
 
 
315
 
 
316
    /// Sets bit number pos to 0
 
317
    void clear_bit(unsigned pos)
 
318
    {
 
319
        unsigned char  mask = (unsigned char)(0x1 << (pos & 7));
 
320
        unsigned char* offs = (unsigned char*)m_buf + (pos >> 3); 
 
321
 
 
322
        *offs &= ~mask;
 
323
    }
 
324
 
 
325
    /// Counts number of bits ON 
 
326
    unsigned bit_count() const
 
327
    {
 
328
        register unsigned count = 0;
 
329
        const unsigned* end = m_buf + (m_size / 32)+1;    
 
330
 
 
331
        for (unsigned* start = m_buf; start < end; ++start)
 
332
        {
 
333
            register unsigned value = *start;
 
334
            for (count += (value!=0); value &= value - 1; ++count);
 
335
        }
 
336
        return count;
 
337
    }
 
338
 
 
339
    /// Comparison.
 
340
    int compare(const bvector_mini& bvect)
 
341
    {
 
342
        unsigned cnt1 = bit_count();
 
343
        unsigned cnt2 = bvect.bit_count();
 
344
 
 
345
        if (!cnt1 && !cnt2) return 0;
 
346
 
 
347
        unsigned cnt_min = cnt1 < cnt2 ? cnt1 : cnt2;
 
348
 
 
349
        if (!cnt_min) return cnt1 ? 1 : -1;
 
350
 
 
351
        unsigned idx1 = get_first();
 
352
        unsigned idx2 = bvect.get_first();
 
353
 
 
354
        for (unsigned i = 0; i < cnt_min; ++i)
 
355
        {
 
356
            if (idx1 != idx2)
 
357
            {
 
358
                return idx1 < idx2 ? 1 : -1;
 
359
            }
 
360
            idx1 = get_next(idx1);
 
361
            idx2 = bvect.get_next(idx2);
 
362
        }
 
363
 
 
364
        BM_ASSERT(idx1==0 || idx2==0);
 
365
 
 
366
        if (idx1 != idx2)
 
367
        {
 
368
            if (!idx1) return -1;
 
369
            if (!idx2) return  1;
 
370
            return idx1 < idx2 ? 1 : -1;
 
371
        }
 
372
 
 
373
        return 0;
 
374
    }
 
375
 
 
376
 
 
377
    /// Returns index of the first ON bit
 
378
    unsigned get_first() const
 
379
    {
 
380
        unsigned pos = 0;
 
381
        const unsigned char* ptr = (unsigned char*) m_buf;
 
382
 
 
383
        for (unsigned i = 0; i < (m_size/8)+1; ++i)
 
384
        {
 
385
            register unsigned char w = ptr[i];
 
386
 
 
387
 
 
388
            if (w != 0)
 
389
            {
 
390
                while ((w & 1) == 0)
 
391
                {
 
392
                    w >>= 1;
 
393
                    ++pos;
 
394
                }
 
395
                return pos;
 
396
            }
 
397
            pos += sizeof(unsigned char) * 8;
 
398
        }
 
399
        return 0;
 
400
    }
 
401
 
 
402
 
 
403
    /// Returns index of next bit, which is ON
 
404
    unsigned get_next(unsigned idx) const
 
405
    {
 
406
        register unsigned i;
 
407
 
 
408
        for (i = idx+1; i < m_size; ++i)
 
409
        {
 
410
            unsigned char* offs = (unsigned char*)m_buf + (i >> 3); 
 
411
            if (*offs)
 
412
            {
 
413
                unsigned char mask = (unsigned char)((char)0x1 << (i & 7));
 
414
 
 
415
                if (*offs & mask)
 
416
                {
 
417
                    return i;
 
418
                }
 
419
            }
 
420
            else
 
421
            {
 
422
                i += 7;
 
423
            }
 
424
        }
 
425
        return 0;
 
426
    }
 
427
 
 
428
 
 
429
    void combine_and(const bvector_mini& bvect)
 
430
    {
 
431
        const unsigned* end = m_buf + (m_size / 32)+1;
 
432
    
 
433
        const unsigned* src = bvect.get_buf();
 
434
 
 
435
        for (unsigned* start = m_buf; start < end; ++start)
 
436
        {
 
437
            *start &= *src++;
 
438
        }
 
439
    }
 
440
 
 
441
    void combine_xor(const bvector_mini& bvect)
 
442
    {
 
443
        const unsigned* end = m_buf + (m_size / 32)+1;
 
444
    
 
445
        const unsigned* src = bvect.get_buf();
 
446
 
 
447
        for (unsigned* start = m_buf; start < end; ++start)
 
448
        {
 
449
            *start ^= *src++;
 
450
        }
 
451
    }
 
452
 
 
453
 
 
454
    void combine_or(const bvector_mini& bvect)
 
455
    {
 
456
        const unsigned* end = m_buf + (m_size / 32)+1;
 
457
    
 
458
        const unsigned* src = bvect.get_buf();
 
459
 
 
460
        for (unsigned* start = m_buf; start < end; ++start)
 
461
        {
 
462
            *start |= *src++;
 
463
        }
 
464
    }
 
465
 
 
466
    void combine_sub(const bvector_mini& bvect)
 
467
    {
 
468
        const unsigned* end = m_buf + (m_size / 32)+1;
 
469
    
 
470
        const unsigned* src = bvect.get_buf();
 
471
 
 
472
        for (unsigned* start = m_buf; start < end; ++start)
 
473
        {
 
474
            *start &= ~(*src++);
 
475
        }
 
476
    }
 
477
 
 
478
    const unsigned* get_buf() const { return m_buf; }
 
479
    unsigned mem_used() const
 
480
    {
 
481
        return sizeof(bvector_mini) + (m_size / 32) + 1;
 
482
    }
 
483
 
 
484
    void swap(bvector_mini& bvm)
 
485
    {
 
486
        BM_ASSERT(m_size == bvm.m_size);
 
487
        bm::word_t* buftmp = m_buf;
 
488
        m_buf = bvm.m_buf;
 
489
        bvm.m_buf = buftmp;
 
490
    }
 
491
 
 
492
private:
 
493
    bm::word_t*   m_buf;
 
494
    unsigned      m_size;
 
495
};
 
496
 
 
497
 
 
498
 
 
499
} // namespace bm
 
500
 
 
501
#endif