« back to all changes in this revision
Viewing changes to src/bmblocks.h
- browse files at revision 4
- compare with another revision
- download diff
- download tarball
- view history from revision 4
- 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.
* 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.
- files added:
- debian/patches/tcpp.dpatch
- doc
- files removed:
- html/a00034.html
- files modified:
- Doxyfile *
- Makefile *
- bm.dsw *
- html/dir_000000_dep.map *
- html/dir_000000_dep.png *
- html/dir_000001_dep.map *
- html/dir_000001_dep.png *
- html/dir_000002_dep.map *
- html/dir_000002_dep.png *
- html/dir_000003_dep.map *
- html/dir_000003_dep.png *
- html/dir_000004_dep.map *
- html/dir_000004_dep.png *
- html/dir_000005_dep.map *
- html/dir_000005_dep.png *
- html/dir_000006_dep.map *
- html/dir_000006_dep.png *
- html/dir_000007_dep.map *
- html/dir_000007_dep.png *
- html/dir_000008_dep.map *
- html/dir_000008_dep.png *
- html/dir_000009_dep.map *
- html/dir_000009_dep.png *
- html/dir_000010_dep.map *
- html/dir_000010_dep.png *
- html/doxygen.css *
- html/doxygen.png *
- html/graph_legend.dot *
- html/graph_legend.png *
- license.txt *
- makefile.in *
- platforms/alpha-osf51.mk *
- platforms/cygwin.mk *
- platforms/intel-solaris.mk *
- platforms/mips-irix6.5.mk *
- platforms/rs6000.mk *
- platforms/sparc-solaris2.mk *
- readme *
- samples/sample1/Makefile *
- samples/sample1/sample1.dsp *
- samples/sample2/Makefile *
- samples/sample2/sample2.dsp *
- samples/sample3/Makefile *
- samples/sample3/sample3.dsp *
- samples/sample4/Makefile *
- samples/sample4/sample4.dsp *
- samples/sample5/Makefile *
- samples/sample5/sample5.dsp *
- samples/sample6/Makefile *
- samples/sample6/sample6.dsp *
- samples/sample7/Makefile *
- samples/sample7/sample7.dsp *
- samples/sample9/Makefile *
- src/bm.dsp *
- src/bm.h *
- tests/perf/Makefile *
- tests/perf/perf.cpp *
- tests/perf/perf.dsp *
- tests/stress/Makefile *
- tests/stress/rlebtv.h *
- tests/stress/test.dsp *
added
removed
src/bmblocks.h
1
/*
2
Copyright(c) 2002-2005 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
3
4
PermiFor more information please visit: http://bmagic.sourceforge.net
5
ssion is hereby granted, free of charge, to any person
6
obtaining a copy of this software and associated documentation
7
files (the "Software"), to deal in the Software without restriction,
8
including without limitation the rights to use, copy, modify, merge,
9
publish, distribute, sublicense, and/or sell copies of the Software,
10
and to permit persons to whom the Software is furnished to do so,
11
subject to the following conditions:
12
13
The above copyright notice and this permission notice shall be included
14
in all copies or substantial portions of the Software.
15
16
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
18
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
19
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
20
DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
21
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
22
OTHER DEALINGS IN THE SOFTWARE.
23
24
For more information please visit: http://bmagic.sourceforge.net
25
26
*/
27
28
29
#ifndef BM_BLOCKS__H__INCLUDED__
30
#define BM_BLOCKS__H__INCLUDED__
31
32
#include "bmfwd.h"
33
34
namespace bm
35
{
36
37
/*!
38
@brief bitvector blocks manager
39
Embedded class managing bit-blocks on very low level.
40
Includes number of functor classes used in different bitset algorithms.
41
@ingroup bvector
42
@internal
43
*/
44
45
template<class Alloc, class MS>
46
class blocks_manager
47
{
48
public:
49
50
typedef Alloc allocator_type;
51
52
/** Base functor class */
53
class bm_func_base
54
{
55
public:
56
bm_func_base(blocks_manager& bman) : bm_(bman) {}
57
58
protected:
59
blocks_manager& bm_;
60
};
61
62
63
/** Base functor class connected for "constant" functors*/
64
class bm_func_base_const
65
{
66
public:
67
bm_func_base_const(const blocks_manager& bman) : bm_(bman) {}
68
69
protected:
70
const blocks_manager& bm_;
71
};
72
73
74
/** Base class for bitcounting functors */
75
class block_count_base : public bm_func_base_const
76
{
77
protected:
78
block_count_base(const blocks_manager& bm)
79
: bm_func_base_const(bm) {}
80
81
bm::id_t block_count(const bm::word_t* block, unsigned idx) const
82
{
83
id_t count = 0;
84
if (IS_FULL_BLOCK(block))
85
{
86
count = bm::bits_in_block;
87
}
88
else
89
{
90
if (BM_IS_GAP(this->bm_, block, idx))
91
{
92
count = gap_bit_count(BMGAP_PTR(block));
93
}
94
else // bitset
95
{
96
count =
97
bit_block_calc_count(block,
98
block + bm::set_block_size);
99
}
100
}
101
return count;
102
}
103
};
104
105
106
/** Bitcounting functor */
107
class block_count_func : public block_count_base
108
{
109
public:
110
block_count_func(const blocks_manager& bm)
111
: block_count_base(bm), count_(0) {}
112
113
bm::id_t count() const { return count_; }
114
115
void operator()(const bm::word_t* block, unsigned idx)
116
{
117
count_ += this->block_count(block, idx);
118
}
119
120
private:
121
bm::id_t count_;
122
};
123
124
125
/** Bitcounting functor filling the block counts array*/
126
class block_count_arr_func : public block_count_base
127
{
128
public:
129
block_count_arr_func(const blocks_manager& bm, unsigned* arr)
130
: block_count_base(bm), arr_(arr), last_idx_(0)
131
{
132
arr_[0] = 0;
133
}
134
135
void operator()(const bm::word_t* block, unsigned idx)
136
{
137
while (++last_idx_ < idx)
138
{
139
arr_[last_idx_] = 0;
140
}
141
arr_[idx] = this->block_count(block, idx);
142
last_idx_ = idx;
143
}
144
145
unsigned last_block() const { return last_idx_; }
146
147
private:
148
unsigned* arr_;
149
unsigned last_idx_;
150
};
151
152
/** bit value change counting functor */
153
class block_count_change_func : public bm_func_base_const
154
{
155
public:
156
block_count_change_func(const blocks_manager& bm)
157
: bm_func_base_const(bm),
158
count_(0),
159
prev_block_border_bit_(0)
160
{}
161
162
bm::id_t block_count(const bm::word_t* block, unsigned idx)
163
{
164
bm::id_t count = 0;
165
bm::id_t first_bit;
166
167
if (IS_FULL_BLOCK(block) || (block == 0))
168
{
169
count = 1;
170
if (idx)
171
{
172
first_bit = block ? 1 : 0;
173
count -= !(prev_block_border_bit_ ^ first_bit);
174
}
175
prev_block_border_bit_ = block ? 1 : 0;
176
}
177
else
178
{
179
if (BM_IS_GAP(this->bm_, block, idx))
180
{
181
gap_word_t* gap_block = BMGAP_PTR(block);
182
count = gap_length(gap_block) - 1;
183
if (idx)
184
{
185
first_bit = gap_test(gap_block, 0);
186
count -= !(prev_block_border_bit_ ^ first_bit);
187
}
188
189
prev_block_border_bit_ =
190
gap_test(gap_block, gap_max_bits-1);
191
}
192
else // bitset
193
{
194
count = bit_block_calc_count_change(block,
195
block + bm::set_block_size);
196
if (idx)
197
{
198
first_bit = block[0] & 1;
199
count -= !(prev_block_border_bit_ ^ first_bit);
200
}
201
prev_block_border_bit_ =
202
block[set_block_size-1] >> ((sizeof(block[0]) * 8) - 1);
203
204
}
205
}
206
return count;
207
}
208
209
bm::id_t count() const { return count_; }
210
211
void operator()(const bm::word_t* block, unsigned idx)
212
{
213
count_ += block_count(block, idx);
214
}
215
216
private:
217
bm::id_t count_;
218
bm::id_t prev_block_border_bit_;
219
};
220
221
222
/** Functor detects if any bit set*/
223
class block_any_func : public bm_func_base_const
224
{
225
public:
226
block_any_func(const blocks_manager& bm)
227
: bm_func_base_const(bm)
228
{}
229
230
bool operator()(const bm::word_t* block, unsigned idx)
231
{
232
if (IS_FULL_BLOCK(block)) return true;
233
234
if (BM_IS_GAP(this->bm_, block, idx)) // gap block
235
{
236
if (!gap_is_all_zero(BMGAP_PTR(block), bm::gap_max_bits))
237
{
238
return true;
239
}
240
}
241
else // bitset
242
{
243
bm::wordop_t* blk1 = (wordop_t*)block;
244
bm::wordop_t* blk2 =
245
(wordop_t*)(block + bm::set_block_size);
246
if (!bit_is_all_zero(blk1, blk2))
247
{
248
return true;
249
}
250
}
251
return false;
252
}
253
};
254
255
/*! Change GAP level lengths functor */
256
class gap_level_func : public bm_func_base
257
{
258
public:
259
gap_level_func(blocks_manager& bm, const gap_word_t* glevel_len)
260
: bm_func_base(bm),
261
glevel_len_(glevel_len)
262
{
263
BM_ASSERT(glevel_len);
264
}
265
266
void operator()(bm::word_t* block, unsigned idx)
267
{
268
blocks_manager& bman = this->bm_;
269
270
if (!BM_IS_GAP(bman, block, idx))
271
return;
272
273
gap_word_t* gap_blk = BMGAP_PTR(block);
274
275
// TODO: Use the same code as in the optimize functor
276
if (gap_is_all_zero(gap_blk, bm::gap_max_bits))
277
{
278
bman.set_block_ptr(idx, 0);
279
goto free_block;
280
}
281
else
282
if (gap_is_all_one(gap_blk, bm::gap_max_bits))
283
{
284
bman.set_block_ptr(idx, FULL_BLOCK_ADDR);
285
free_block:
286
bman.get_allocator().free_gap_block(gap_blk,
287
bman.glen());
288
bman.set_block_bit(idx);
289
return;
290
}
291
292
unsigned len = gap_length(gap_blk);
293
int level = gap_calc_level(len, glevel_len_);
294
if (level == -1)
295
{
296
bm::word_t* blk =
297
bman.get_allocator().alloc_bit_block();
298
bman.set_block_ptr(idx, blk);
299
bman.set_block_bit(idx);
300
gap_convert_to_bitset(blk, gap_blk);
301
}
302
else
303
{
304
gap_word_t* gap_blk_new =
305
bman.allocate_gap_block(level, gap_blk, glevel_len_);
306
307
bm::word_t* p = (bm::word_t*) gap_blk_new;
308
BMSET_PTRGAP(p);
309
bman.set_block_ptr(idx, p);
310
}
311
bman.get_allocator().free_gap_block(gap_blk, bman.glen());
312
}
313
314
private:
315
const gap_word_t* glevel_len_;
316
};
317
318
319
/*! Bitblock optimization functor */
320
class block_opt_func : public bm_func_base
321
{
322
public:
323
block_opt_func(blocks_manager& bm,
324
bm::word_t* temp_block,
325
int opt_mode)
326
: bm_func_base(bm),
327
temp_block_(temp_block),
328
opt_mode_(opt_mode)
329
{
330
BM_ASSERT(temp_block);
331
}
332
333
void operator()(bm::word_t* block, unsigned idx)
334
{
335
blocks_manager& bman = this->bm_;
336
if (IS_FULL_BLOCK(block)) return;
337
338
gap_word_t* gap_blk;
339
340
if (BM_IS_GAP(bman, block, idx)) // gap block
341
{
342
gap_blk = BMGAP_PTR(block);
343
344
if (gap_is_all_zero(gap_blk, bm::gap_max_bits))
345
{
346
bman.set_block_ptr(idx, 0);
347
goto free_block;
348
}
349
else
350
if (gap_is_all_one(gap_blk, bm::gap_max_bits))
351
{
352
bman.set_block_ptr(idx, FULL_BLOCK_ADDR);
353
free_block:
354
bman.get_allocator().free_gap_block(gap_blk,
355
bman.glen());
356
bman.set_block_bit(idx);
357
}
358
}
359
else // bit block
360
{
361
if (opt_mode_ < 3) // free_01 optimization
362
{
363
bm::wordop_t* blk1 = (wordop_t*)block;
364
bm::wordop_t* blk2 =
365
(wordop_t*)(block + bm::set_block_size);
366
367
bool b = bit_is_all_zero(blk1, blk2);
368
if (b)
369
{
370
bman.get_allocator().free_bit_block(block);
371
bman.set_block_ptr(idx, 0);
372
return;
373
}
374
if (opt_mode_ == 2) // check if it is all 1 block
375
{
376
b = is_bits_one(blk1, blk2);
377
if (b)
378
{
379
bman.get_allocator().free_bit_block(block);
380
bman.set_block_ptr(idx, FULL_BLOCK_ADDR);
381
return;
382
}
383
}
384
return;
385
}
386
387
// try to compress
388
389
gap_word_t* tmp_gap_blk = (gap_word_t*)temp_block_;
390
*tmp_gap_blk = bm::gap_max_level << 1;
391
392
unsigned threashold = bman.glen(bm::gap_max_level)-4;
393
394
unsigned len = bit_convert_to_gap(tmp_gap_blk,
395
block,
396
bm::gap_max_bits,
397
threashold);
398
399
400
if (!len) return;
401
402
// convertion successful
403
404
bman.get_allocator().free_bit_block(block);
405
406
// check if new gap block can be eliminated
407
408
if (gap_is_all_zero(tmp_gap_blk, bm::gap_max_bits))
409
{
410
bman.set_block_ptr(idx, 0);
411
}
412
else if (gap_is_all_one(tmp_gap_blk, bm::gap_max_bits))
413
{
414
bman.set_block_ptr(idx, FULL_BLOCK_ADDR);
415
}
416
else
417
{
418
int level = bm::gap_calc_level(len, bman.glen());
419
420
gap_blk =
421
bman.allocate_gap_block(level, tmp_gap_blk);
422
bman.set_block_ptr(idx, (bm::word_t*)gap_blk);
423
bman.set_block_gap(idx);
424
}
425
426
427
}
428
429
}
430
private:
431
bm::word_t* temp_block_;
432
int opt_mode_;
433
};
434
435
/** Bitblock invert functor */
436
class block_invert_func : public bm_func_base
437
{
438
public:
439
block_invert_func(blocks_manager& bm)
440
: bm_func_base(bm) {}
441
442
void operator()(bm::word_t* block, unsigned idx)
443
{
444
if (!block)
445
{
446
this->bm_.set_block(idx, FULL_BLOCK_ADDR);
447
}
448
else
449
if (IS_FULL_BLOCK(block))
450
{
451
this->bm_.set_block_ptr(idx, 0);
452
}
453
else
454
{
455
if (BM_IS_GAP(this->bm_, block, idx)) // gap block
456
{
457
gap_invert(BMGAP_PTR(block));
458
}
459
else // bit block
460
{
461
bm::wordop_t* wrd_ptr = (wordop_t*) block;
462
bm::wordop_t* wrd_end =
463
(wordop_t*) (block + bm::set_block_size);
464
bit_invert(wrd_ptr, wrd_end);
465
}
466
}
467
468
}
469
};
470
471
/** Set block zero functor */
472
class block_zero_func : public bm_func_base
473
{
474
public:
475
block_zero_func(blocks_manager& bm, bool free_mem)
476
: bm_func_base(bm),
477
free_mem_(free_mem)
478
{}
479
480
void operator()(bm::word_t* block, unsigned idx)
481
{
482
blocks_manager& bman = this->bm_;
483
if (IS_FULL_BLOCK(block))
484
{
485
bman.set_block_ptr(idx, 0);
486
}
487
else
488
{
489
if (BM_IS_GAP(bman, block, idx))
490
{
491
gap_set_all(BMGAP_PTR(block), bm::gap_max_bits, 0);
492
}
493
else // BIT block
494
{
495
if (free_mem_)
496
{
497
bman.get_allocator().free_bit_block(block);
498
bman.set_block_ptr(idx, 0);
499
}
500
else
501
{
502
bit_block_set(block, 0);
503
}
504
}
505
}
506
}
507
private:
508
bool free_mem_; //!< If "true" frees bitblocks memsets to '0'
509
};
510
511
/** Fill block with all-one bits functor */
512
class block_one_func : public bm_func_base
513
{
514
public:
515
block_one_func(blocks_manager& bm) : bm_func_base(bm) {}
516
517
void operator()(bm::word_t* block, unsigned idx)
518
{
519
if (!IS_FULL_BLOCK(block))
520
{
521
this->bm_.set_block_all_set(idx);
522
}
523
}
524
};
525
526
/** Block deallocation functor */
527
class block_free_func : public bm_func_base
528
{
529
public:
530
block_free_func(blocks_manager& bm) : bm_func_base(bm) {}
531
532
void operator()(bm::word_t* block, unsigned idx)
533
{
534
blocks_manager& bman = this->bm_;
535
if (BM_IS_GAP(bman, block, idx)) // gap block
536
{
537
bman.get_allocator().free_gap_block(BMGAP_PTR(block),
538
bman.glen());
539
}
540
else
541
{
542
bman.get_allocator().free_bit_block(block);
543
}
544
}
545
};
546
547
/** Block copy functor */
548
class block_copy_func : public bm_func_base
549
{
550
public:
551
block_copy_func(blocks_manager& bm_target,
552
const blocks_manager& bm_src)
553
: bm_func_base(bm_target),
554
bm_src_(bm_src)
555
{}
556
557
void operator()(bm::word_t* block, unsigned idx)
558
{
559
bool gap = bm_src_.is_block_gap(idx);
560
bm::word_t* new_blk;
561
562
blocks_manager& bman = this->bm_;
563
564
if (gap)
565
{
566
bm::gap_word_t* gap_block = BMGAP_PTR(block);
567
unsigned level = gap_level(gap_block);
568
new_blk = (bm::word_t*)
569
bman.get_allocator().alloc_gap_block(level,
570
bman.glen());
571
int len = gap_length(BMGAP_PTR(block));
572
::memcpy(new_blk, gap_block, len * sizeof(gap_word_t));
573
BMSET_PTRGAP(new_blk);
574
}
575
else
576
{
577
if (IS_FULL_BLOCK(block))
578
{
579
new_blk = block;
580
}
581
else
582
{
583
new_blk = bman.get_allocator().alloc_bit_block();
584
bit_block_copy(new_blk, block);
585
}
586
}
587
bman.set_block(idx, new_blk);
588
}
589
590
private:
591
const blocks_manager& bm_src_;
592
};
593
594
595
public:
596
597
blocks_manager(const gap_word_t* glevel_len,
598
bm::id_t max_bits,
599
const Alloc& alloc = Alloc())
600
: temp_block_(0),
601
alloc_(alloc)
602
{
603
::memcpy(glevel_len_, glevel_len, sizeof(glevel_len_));
604
605
if (max_bits)
606
{
607
top_block_size_ = compute_top_block_size(max_bits);
608
// allocate first level descr. of blocks
609
blocks_ = (bm::word_t***) alloc_.alloc_ptr(top_block_size_);
610
::memset(blocks_, 0, top_block_size_ * sizeof(bm::word_t**));
611
}
612
else
613
{
614
top_block_size_ = 0;
615
blocks_ = 0;
616
}
617
volatile const char* vp = _copyright<true>::_p;
618
char c = *vp;
619
c = 0;
620
}
621
622
blocks_manager(const blocks_manager& blockman)
623
: blocks_(0),
624
top_block_size_(blockman.top_block_size_),
625
#ifdef BM_DISBALE_BIT_IN_PTR
626
gap_flags_(blockman.gap_flags_),
627
#endif
628
temp_block_(0),
629
alloc_(blockman.alloc_)
630
{
631
::memcpy(glevel_len_, blockman.glevel_len_, sizeof(glevel_len_));
632
633
blocks_ = (bm::word_t***)alloc_.alloc_ptr(top_block_size_);
634
::memset(blocks_, 0, top_block_size_ * sizeof(bm::word_t**));
635
636
blocks_manager* bm =
637
const_cast<blocks_manager*>(&blockman);
638
639
word_t*** blk_root = bm->blocks_root();
640
641
block_copy_func copy_func(*this, blockman);
642
for_each_nzblock(blk_root, top_block_size_,
643
bm::set_array_size, copy_func);
644
}
645
646
~blocks_manager()
647
{
648
alloc_.free_bit_block(temp_block_);
649
deinit_tree();
650
}
651
652
void free_ptr(bm::word_t** ptr)
653
{
654
if (ptr) alloc_.free_ptr(ptr);
655
}
656
657
/**
658
\brief Compute size of the block array needed to store bits
659
\param bits_to_store - supposed capacity (number of bits)
660
\return size of the top level block
661
*/
662
unsigned compute_top_block_size(bm::id_t bits_to_store)
663
{
664
if (bits_to_store == bm::id_max) // working in full-range mode
665
{
666
return bm::set_array_size;
667
}
668
669
unsigned top_block_size =
670
bits_to_store / (bm::set_block_size * sizeof(bm::word_t) *
671
bm::set_array_size * 8);
672
if (top_block_size < bm::set_array_size) ++top_block_size;
673
return top_block_size;
674
}
675
676
/**
677
Returns current capacity (bits)
678
*/
679
bm::id_t capacity() const
680
{
681
// arithmetic overflow protection...
682
return top_block_size_ == bm::set_array_size ? bm::id_max :
683
top_block_size_ * bm::set_array_size * bm::bits_in_block;
684
}
685
686
/**
687
\brief Finds block in 2-level blocks array
688
\param nb - Index of block (logical linear number)
689
\return block adress or NULL if not yet allocated
690
*/
691
bm::word_t* get_block(unsigned nb) const
692
{
693
unsigned block_idx = nb >> bm::set_array_shift;
694
if (block_idx >= top_block_size_)
695
{
696
return 0;
697
}
698
bm::word_t** blk_blk = blocks_[block_idx];
699
return blk_blk ? blk_blk[nb & bm::set_array_mask] : 0;
700
}
701
702
/**
703
\brief Finds block in 2-level blocks array
704
Specilized version of get_block(unsigned), returns an additional
705
condition when there are no more blocks
706
707
\param nb - Index of block (logical linear number)
708
\param no_more_blocks - 1 if there are no more blocks at all
709
\return block adress or NULL if not yet allocated
710
*/
711
bm::word_t* get_block(unsigned nb, int* no_more_blocks) const
712
{
713
unsigned block_idx = nb >> bm::set_array_shift;
714
if (block_idx >= top_block_size_)
715
{
716
*no_more_blocks = 1;
717
return 0;
718
}
719
*no_more_blocks = 0;
720
bm::word_t** blk_blk = blocks_[block_idx];
721
return blk_blk ? blk_blk[nb & bm::set_array_mask] : 0;
722
}
723
724
bool is_no_more_blocks(unsigned nb) const
725
{
726
unsigned block = nb;
727
unsigned block_idx = nb >> bm::set_array_shift;
728
for (unsigned i = block_idx; i < top_block_size_; ++i) {
729
bm::word_t** blk_blk = blocks_[i];
730
if (blk_blk)
731
{
732
for (unsigned j = block & bm::set_array_mask;
733
j < bm::set_array_size; ++j)
734
{
735
bm::word_t* blk = blk_blk[j];
736
if (blk && !is_block_zero(i, blk))
737
{
738
return false;
739
}
740
++block;
741
}
742
}
743
else
744
{
745
block += bm::set_array_size;
746
}
747
}
748
return true;
749
}
750
751
/**
752
\brief Finds block in 2-level blocks array
753
\param i - top level block index
754
\param j - second level block index
755
\return block adress or NULL if not yet allocated
756
*/
757
const bm::word_t* get_block(unsigned i, unsigned j) const
758
{
759
if (i >= top_block_size_) return 0;
760
const bm::word_t* const* blk_blk = blocks_[i];
761
return (blk_blk == 0) ? 0 : blk_blk[j];
762
}
763
764
/**
765
\brief Function returns top-level block in 2-level blocks array
766
\param i - top level block index
767
\return block adress or NULL if not yet allocated
768
*/
769
const bm::word_t* const * get_topblock(unsigned i) const
770
{
771
return (i >= top_block_size_) ? 0 : blocks_[i];
772
}
773
774
/**
775
\brief Returns root block in the tree.
776
*/
777
bm::word_t*** get_rootblock() const
778
{
779
blocks_manager* bm =
780
const_cast<blocks_manager*>(this);
781
return bm->blocks_root();
782
}
783
784
void set_block_all_set(unsigned nb)
785
{
786
bm::word_t* block = this->get_block(nb);
787
set_block(nb, const_cast<bm::word_t*>(FULL_BLOCK_ADDR));
788
789
// If we keep block type flag in pointer itself we dp not need
790
// to clear gap bit
791
#ifdef BM_DISBALE_BIT_IN_PTR
792
set_block_bit(nb);
793
#endif
794
795
if (BM_IS_GAP((*this), block, nb))
796
{
797
alloc_.free_gap_block(BMGAP_PTR(block), glevel_len_);
798
}
799
else
800
{
801
alloc_.free_bit_block(block);
802
}
803
}
804
805
/**
806
Function checks if block is not yet allocated, allocates it and sets to
807
all-zero or all-one bits.
808
809
If content_flag == 1 (ALLSET block) requested and taken block is already ALLSET,
810
function will return NULL
811
812
initial_block_type and actual_block_type : 0 - bitset, 1 - gap
813
*/
814
bm::word_t* check_allocate_block(unsigned nb,
815
unsigned content_flag,
816
int initial_block_type,
817
int* actual_block_type,
818
bool allow_null_ret=true)
819
{
820
bm::word_t* block = this->get_block(nb);
821
822
if (!IS_VALID_ADDR(block)) // NULL block or ALLSET
823
{
824
// if we wanted ALLSET and requested block is ALLSET return NULL
825
unsigned block_flag = IS_FULL_BLOCK(block);
826
*actual_block_type = initial_block_type;
827
if (block_flag == content_flag && allow_null_ret)
828
{
829
return 0; // it means nothing to do for the caller
830
}
831
832
if (initial_block_type == 0) // bitset requested
833
{
834
block = alloc_.alloc_bit_block();
835
836
// initialize block depending on its previous status
837
838
bit_block_set(block, block_flag ? 0xFF : 0);
839
840
set_block(nb, block);
841
}
842
else // gap block requested
843
{
844
bm::gap_word_t* gap_block = allocate_gap_block(0);
845
gap_set_all(gap_block, bm::gap_max_bits, block_flag);
846
set_block(nb, (bm::word_t*)gap_block);
847
848
set_block_gap(nb);
849
850
return (bm::word_t*)gap_block;
851
}
852
853
}
854
else // block already exists
855
{
856
*actual_block_type = BM_IS_GAP((*this), block, nb);
857
}
858
859
return block;
860
}
861
862
/*! @brief Fills all blocks with 0.
863
@param free_mem - if true function frees the resources
864
*/
865
void set_all_zero(bool free_mem)
866
{
867
block_zero_func zero_func(*this, free_mem);
868
for_each_nzblock(blocks_, top_block_size_,
869
bm::set_array_size, zero_func);
870
}
871
872
/*! Replaces all blocks with ALL_ONE block.
873
*/
874
void set_all_one()
875
{
876
block_one_func func(*this);
877
for_each_block(blocks_, top_block_size_,
878
bm::set_array_size, func);
879
}
880
881
/**
882
Places new block into descriptors table, returns old block's address.
883
Old block is not deleted.
884
*/
885
bm::word_t* set_block(unsigned nb, bm::word_t* block)
886
{
887
bm::word_t* old_block;
888
889
// top block index
890
register unsigned nblk_blk = nb >> bm::set_array_shift;
891
892
// auto-resize the top block array
893
if (nblk_blk >= top_block_size_)
894
reserve_top_blocks(nblk_blk + 1);
895
896
// If first level array not yet allocated, allocate it and
897
// assign block to it
898
if (blocks_[nblk_blk] == 0)
899
{
900
blocks_[nblk_blk] = (bm::word_t**)alloc_.alloc_ptr();
901
::memset(blocks_[nblk_blk], 0,
902
bm::set_array_size * sizeof(bm::word_t*));
903
904
old_block = 0;
905
}
906
else
907
{
908
old_block = blocks_[nblk_blk][nb & bm::set_array_mask];
909
}
910
911
// NOTE: block will be replaced without freeing,
912
// potential memory leak may lay here....
913
blocks_[nblk_blk][nb & bm::set_array_mask] = block; // equivalent to %
914
915
return old_block;
916
}
917
918
/**
919
Places new block into blocks table.
920
*/
921
void set_block_ptr(unsigned nb, bm::word_t* block)
922
{
923
blocks_[nb >> bm::set_array_shift][nb & bm::set_array_mask] = block;
924
}
925
926
/**
927
\brief Converts block from type gap to conventional bitset block.
928
\param nb - Block's index.
929
\param gap_block - Pointer to the gap block,
930
if NULL block nb will be taken
931
\return new gap block's memory
932
*/
933
bm::word_t* convert_gap2bitset(unsigned nb, gap_word_t* gap_block=0)
934
{
935
bm::word_t* block = this->get_block(nb);
936
if (gap_block == 0)
937
{
938
gap_block = BMGAP_PTR(block);
939
}
940
941
BM_ASSERT(IS_VALID_ADDR((bm::word_t*)gap_block));
942
BM_ASSERT(is_block_gap(nb)); // must be GAP type
943
944
bm::word_t* new_block = alloc_.alloc_bit_block();
945
946
gap_convert_to_bitset(new_block, gap_block);
947
948
// new block will replace the old one(no deletion)
949
set_block_ptr(nb, new_block);
950
951
alloc_.free_gap_block(BMGAP_PTR(block), glen());
952
953
// If GAP flag is in block pointer no need to clean the gap bit twice
954
#ifdef BM_DISBALE_BIT_IN_PTR
955
set_block_bit(nb);
956
#endif
957
958
return new_block;
959
}
960
961
/**
962
\brief Extends GAP block to the next level or converts it to bit block.
963
\param nb - Block's linear index.
964
\param blk - Blocks's pointer
965
*/
966
void extend_gap_block(unsigned nb, gap_word_t* blk)
967
{
968
unsigned level = bm::gap_level(blk);
969
unsigned len = bm::gap_length(blk);
970
if (level == bm::gap_max_level || len >= gap_max_buff_len)
971
{
972
convert_gap2bitset(nb);
973
}
974
else
975
{
976
bm::word_t* new_blk = (bm::word_t*)allocate_gap_block(++level, blk);
977
978
BMSET_PTRGAP(new_blk);
979
980
set_block_ptr(nb, new_blk);
981
alloc_.free_gap_block(blk, glen());
982
}
983
}
984
985
bool is_block_gap(unsigned nb) const
986
{
987
#ifdef BM_DISBALE_BIT_IN_PTR
988
return gap_flags_.test(nb)!=0;
989
#else
990
bm::word_t* block = get_block(nb);
991
return BMPTR_TESTBIT0(block) != 0;
992
#endif
993
}
994
995
void set_block_bit(unsigned nb)
996
{
997
#ifdef BM_DISBALE_BIT_IN_PTR
998
gap_flags_.set(nb, false);
999
#else
1000
bm::word_t* block = get_block(nb);
1001
block = (bm::word_t*) BMPTR_CLEARBIT0(block);
1002
set_block_ptr(nb, block);
1003
#endif
1004
}
1005
1006
void set_block_gap(unsigned nb)
1007
{
1008
#ifdef BM_DISBALE_BIT_IN_PTR
1009
gap_flags_.set(nb);
1010
#else
1011
bm::word_t* block = get_block(nb);
1012
block = (bm::word_t*)BMPTR_SETBIT0(block);
1013
set_block_ptr(nb, block);
1014
#endif
1015
}
1016
1017
/**
1018
\fn bool bm::bvector::blocks_manager::is_block_zero(unsigned nb, bm::word_t* blk)
1019
\brief Checks all conditions and returns true if block consists of only 0 bits
1020
\param nb - Block's linear index.
1021
\param blk - Blocks's pointer
1022
\returns true if all bits are in the block are 0.
1023
*/
1024
bool is_block_zero(unsigned nb, const bm::word_t* blk) const
1025
{
1026
if (blk == 0) return true;
1027
1028
if (BM_IS_GAP((*this), blk, nb)) // GAP
1029
{
1030
gap_word_t* b = BMGAP_PTR(blk);
1031
return gap_is_all_zero(b, bm::gap_max_bits);
1032
}
1033
1034
// BIT
1035
for (unsigned i = 0; i < bm::set_block_size; ++i)
1036
{
1037
if (blk[i] != 0)
1038
return false;
1039
}
1040
return true;
1041
}
1042
1043
/**
1044
\brief Checks if block has only 1 bits
1045
\param nb - Index of the block.
1046
\param blk - Block's pointer
1047
\return true if block consists of 1 bits.
1048
*/
1049
bool is_block_one(unsigned nb, const bm::word_t* blk) const
1050
{
1051
if (blk == 0) return false;
1052
1053
if (BM_IS_GAP((*this), blk, nb)) // GAP
1054
{
1055
gap_word_t* b = BMGAP_PTR(blk);
1056
return gap_is_all_one(b, bm::gap_max_bits);
1057
}
1058
1059
// BIT block
1060
1061
if (IS_FULL_BLOCK(blk))
1062
{
1063
return true;
1064
}
1065
return is_bits_one((wordop_t*)blk,
1066
(wordop_t*)(blk + bm::set_block_size));
1067
}
1068
1069
/*! Returns temporary block, allocates if needed. */
1070
bm::word_t* check_allocate_tempblock()
1071
{
1072
return temp_block_ ? temp_block_
1073
: (temp_block_ = alloc_.alloc_bit_block());
1074
}
1075
1076
/*! Assigns new GAP lengths vector */
1077
void set_glen(const gap_word_t* glevel_len)
1078
{
1079
::memcpy(glevel_len_, glevel_len, sizeof(glevel_len_));
1080
}
1081
1082
1083
bm::gap_word_t* allocate_gap_block(unsigned level,
1084
gap_word_t* src = 0,
1085
const gap_word_t* glevel_len = 0)
1086
{
1087
if (!glevel_len)
1088
glevel_len = glevel_len_;
1089
gap_word_t* ptr = alloc_.alloc_gap_block(level, glevel_len);
1090
if (src)
1091
{
1092
unsigned len = gap_length(src);
1093
::memcpy(ptr, src, len * sizeof(gap_word_t));
1094
// Reconstruct the mask word using the new level code.
1095
*ptr = ((len-1) << 3) | (level << 1) | (*src & 1);
1096
}
1097
else
1098
{
1099
*ptr = level << 1;
1100
}
1101
return ptr;
1102
}
1103
1104
unsigned mem_used() const
1105
{
1106
unsigned mem_used = sizeof(*this);
1107
mem_used += temp_block_ ? sizeof(word_t) * bm::set_block_size : 0;
1108
mem_used += sizeof(bm::word_t**) * top_block_size_;
1109
1110
#ifdef BM_DISBALE_BIT_IN_PTR
1111
mem_used += gap_flags_.mem_used() - sizeof(gap_flags_);
1112
#endif
1113
1114
for (unsigned i = 0; i < top_block_size_; ++i)
1115
{
1116
mem_used += blocks_[i] ? sizeof(void*) * bm::set_array_size : 0;
1117
}
1118
1119
return mem_used;
1120
}
1121
1122
/** Returns true if second level block pointer is 0.
1123
*/
1124
bool is_subblock_null(unsigned nsub) const
1125
{
1126
return blocks_[nsub] == NULL;
1127
}
1128
1129
1130
bm::word_t*** blocks_root()
1131
{
1132
return blocks_;
1133
}
1134
1135
/*! \brief Returns current GAP level vector
1136
*/
1137
const gap_word_t* glen() const
1138
{
1139
return glevel_len_;
1140
}
1141
1142
/*! \brief Returns GAP level length for specified level
1143
\param level - level number
1144
*/
1145
unsigned glen(unsigned level) const
1146
{
1147
return glevel_len_[level];
1148
}
1149
1150
/*! \brief Swaps content
1151
\param bm another blocks manager
1152
*/
1153
void swap(blocks_manager& bm)
1154
{
1155
BM_ASSERT(this != &bm);
1156
1157
word_t*** btmp = blocks_;
1158
blocks_ = bm.blocks_;
1159
bm.blocks_ = btmp;
1160
1161
#ifdef BM_DISBALE_BIT_IN_PTR
1162
gap_flags_.swap(bm.gap_flags_);
1163
#endif
1164
1165
xor_swap(this->top_block_size_, bm.top_block_size_);
1166
1167
BM_ASSERT(sizeof(glevel_len_) / sizeof(glevel_len_[0])
1168
== bm::gap_levels); // paranoiya check
1169
for (unsigned i = 0; i < bm::gap_levels; ++i)
1170
{
1171
xor_swap(glevel_len_[i], bm.glevel_len_[i]);
1172
}
1173
}
1174
1175
/*! \brief Returns size of the top block array in the tree
1176
*/
1177
unsigned top_block_size() const
1178
{
1179
return top_block_size_;
1180
}
1181
1182
/**
1183
\brief reserve capacity for specified number of bits
1184
*/
1185
void reserve(unsigned max_bits)
1186
{
1187
if (max_bits)
1188
{
1189
unsigned b = compute_top_block_size(max_bits);
1190
reserve_top_blocks(b);
1191
}
1192
}
1193
1194
/*!
1195
\brief Make sure blocks manager has enough blocks capacity
1196
*/
1197
void reserve_top_blocks(unsigned top_blocks)
1198
{
1199
BM_ASSERT(top_blocks <= bm::set_array_size);
1200
if (top_blocks <= top_block_size_) return; // nothing to do
1201
bm::word_t*** new_blocks =
1202
(bm::word_t***)alloc_.alloc_ptr(top_blocks);
1203
1204
for (unsigned i = 0; i < top_block_size_; ++i)
1205
{
1206
new_blocks[i] = blocks_[i];
1207
}
1208
for (unsigned j = top_block_size_; j < top_blocks; ++j)
1209
{
1210
new_blocks[j] = 0;
1211
}
1212
alloc_.free_ptr(blocks_, top_block_size_);
1213
blocks_ = new_blocks;
1214
top_block_size_ = top_blocks;
1215
}
1216
1217
/** \brief Returns reference on the allocator
1218
*/
1219
allocator_type& get_allocator() { return alloc_; }
1220
1221
/** \brief Returns allocator
1222
*/
1223
allocator_type get_allocator() const { return alloc_; }
1224
1225
private:
1226
1227
void operator =(const blocks_manager&);
1228
1229
void deinit_tree()
1230
{
1231
if (blocks_ == 0) return;
1232
1233
block_free_func free_func(*this);
1234
for_each_nzblock(blocks_, top_block_size_,
1235
bm::set_array_size, free_func);
1236
1237
for(unsigned i = 0; i < top_block_size_; ++i)
1238
{
1239
bm::word_t** blk_blk = blocks_[i];
1240
if (blk_blk)
1241
alloc_.free_ptr(blk_blk);
1242
}
1243
alloc_.free_ptr(blocks_, top_block_size_);
1244
}
1245
1246
private:
1247
/// Tree of blocks.
1248
bm::word_t*** blocks_;
1249
/// Size of the top level block array in blocks_ tree
1250
unsigned top_block_size_;
1251
#ifdef BM_DISBALE_BIT_IN_PTR
1252
/// mini bitvector used to indicate gap blocks
1253
MS gap_flags_;
1254
#endif
1255
/// Temp block.
1256
bm::word_t* temp_block_;
1257
/// vector defines gap block lengths for different levels
1258
gap_word_t glevel_len_[bm::gap_levels];
1259
/// allocator
1260
allocator_type alloc_;
1261
};
1262
1263
1264
}
1265
1266
#endif
1267
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
28
#ifndef BM_BLOCKS__H__INCLUDED__
29
#define BM_BLOCKS__H__INCLUDED__
30
31
#include "bmfwd.h"
32
33
namespace bm
34
{
35
36
37
/*!
38
@brief bitvector blocks manager
39
Embedded class managing bit-blocks on very low level.
40
Includes number of functor classes used in different bitset algorithms.
41
@ingroup bvector
42
@internal
43
*/
44
45
template<class Alloc, class MS>
46
class blocks_manager
47
{
48
public:
49
50
typedef Alloc allocator_type;
51
52
/** Base functor class (block visitor)*/
53
class bm_func_base
54
{
55
public:
56
bm_func_base(blocks_manager& bman) : bm_(bman) {}
57
58
void on_empty_top(unsigned /* top_block_idx*/ ) {}
59
void on_empty_block(unsigned /* block_idx*/ ) {}
60
protected:
61
blocks_manager& bm_;
62
};
63
64
65
/** Base functor class connected for "constant" functors*/
66
class bm_func_base_const
67
{
68
public:
69
bm_func_base_const(const blocks_manager& bman) : bm_(bman) {}
70
71
void on_empty_top(unsigned /* top_block_idx*/ ) {}
72
void on_empty_block(unsigned /* block_idx*/ ) {}
73
protected:
74
const blocks_manager& bm_;
75
};
76
77
78
/** Base class for bitcounting functors */
79
class block_count_base : public bm_func_base_const
80
{
81
protected:
82
block_count_base(const blocks_manager& bm)
83
: bm_func_base_const(bm) {}
84
85
bm::id_t block_count(const bm::word_t* block, unsigned idx) const
86
{
87
return this->bm_.block_bitcount(block, idx);
88
}
89
};
90
91
92
/** Bitcounting functor */
93
class block_count_func : public block_count_base
94
{
95
public:
96
block_count_func(const blocks_manager& bm)
97
: block_count_base(bm), count_(0) {}
98
99
bm::id_t count() const { return count_; }
100
101
void operator()(const bm::word_t* block, unsigned idx)
102
{
103
count_ += this->block_count(block, idx);
104
}
105
106
private:
107
bm::id_t count_;
108
};
109
110
111
/** Bitcounting functor filling the block counts array*/
112
class block_count_arr_func : public block_count_base
113
{
114
public:
115
block_count_arr_func(const blocks_manager& bm, unsigned* arr)
116
: block_count_base(bm), arr_(arr), last_idx_(0)
117
{
118
arr_[0] = 0;
119
}
120
121
void operator()(const bm::word_t* block, unsigned idx)
122
{
123
while (++last_idx_ < idx)
124
{
125
arr_[last_idx_] = 0;
126
}
127
arr_[idx] = this->block_count(block, idx);
128
last_idx_ = idx;
129
}
130
131
unsigned last_block() const { return last_idx_; }
132
133
private:
134
unsigned* arr_;
135
unsigned last_idx_;
136
};
137
138
/** bit value change counting functor */
139
class block_count_change_func : public bm_func_base_const
140
{
141
public:
142
block_count_change_func(const blocks_manager& bm)
143
: bm_func_base_const(bm),
144
count_(0),
145
prev_block_border_bit_(0)
146
{}
147
148
bm::id_t block_count(const bm::word_t* block, unsigned idx)
149
{
150
bm::id_t count = 0;
151
bm::id_t first_bit;
152
153
if (IS_FULL_BLOCK(block) || (block == 0))
154
{
155
count = 1;
156
if (idx)
157
{
158
first_bit = block ? 1 : 0;
159
count -= !(prev_block_border_bit_ ^ first_bit);
160
}
161
prev_block_border_bit_ = block ? 1 : 0;
162
}
163
else
164
{
165
if (BM_IS_GAP(*this, block, idx))
166
{
167
gap_word_t* gap_block = BMGAP_PTR(block);
168
count = gap_length(gap_block) - 1;
169
if (idx)
170
{
171
first_bit = gap_test(gap_block, 0);
172
count -= !(prev_block_border_bit_ ^ first_bit);
173
}
174
175
prev_block_border_bit_ =
176
gap_test(gap_block, gap_max_bits-1);
177
}
178
else // bitset
179
{
180
count = bit_block_calc_count_change(block,
181
block + bm::set_block_size);
182
if (idx)
183
{
184
first_bit = block[0] & 1;
185
count -= !(prev_block_border_bit_ ^ first_bit);
186
}
187
prev_block_border_bit_ =
188
block[set_block_size-1] >> ((sizeof(block[0]) * 8) - 1);
189
190
}
191
}
192
return count;
193
}
194
195
bm::id_t count() const { return count_; }
196
197
void operator()(const bm::word_t* block, unsigned idx)
198
{
199
count_ += block_count(block, idx);
200
}
201
202
private:
203
bm::id_t count_;
204
bm::id_t prev_block_border_bit_;
205
};
206
207
208
/** Functor detects if any bit set*/
209
class block_any_func : public bm_func_base_const
210
{
211
public:
212
block_any_func(const blocks_manager& bm)
213
: bm_func_base_const(bm)
214
{}
215
216
bool operator()(const bm::word_t* block, unsigned idx)
217
{
218
if (IS_FULL_BLOCK(block)) return true;
219
220
if (BM_IS_GAP(*this, block, idx)) // gap block
221
{
222
if (!gap_is_all_zero(BMGAP_PTR(block), bm::gap_max_bits))
223
{
224
return true;
225
}
226
}
227
else // bitset
228
{
229
bm::wordop_t* blk1 = (wordop_t*)block;
230
bm::wordop_t* blk2 =
231
(wordop_t*)(block + bm::set_block_size);
232
if (!bit_is_all_zero(blk1, blk2))
233
{
234
return true;
235
}
236
}
237
return false;
238
}
239
};
240
241
/*! Change GAP level lengths functor */
242
class gap_level_func : public bm_func_base
243
{
244
public:
245
gap_level_func(blocks_manager& bm, const gap_word_t* glevel_len)
246
: bm_func_base(bm),
247
glevel_len_(glevel_len)
248
{
249
BM_ASSERT(glevel_len);
250
}
251
252
void operator()(bm::word_t* block, unsigned idx)
253
{
254
blocks_manager& bman = this->bm_;
255
256
if (!BM_IS_GAP(*this, block, idx))
257
return;
258
259
gap_word_t* gap_blk = BMGAP_PTR(block);
260
261
// TODO: Use the same code as in the optimize functor
262
if (gap_is_all_zero(gap_blk, bm::gap_max_bits))
263
{
264
bman.set_block_ptr(idx, 0);
265
goto free_block;
266
}
267
else
268
if (gap_is_all_one(gap_blk, bm::gap_max_bits))
269
{
270
bman.set_block_ptr(idx, FULL_BLOCK_ADDR);
271
free_block:
272
bman.get_allocator().free_gap_block(gap_blk,
273
bman.glen());
274
bman.set_block_bit(idx);
275
return;
276
}
277
278
unsigned len = gap_length(gap_blk);
279
int level = gap_calc_level(len, glevel_len_);
280
if (level == -1)
281
{
282
bm::word_t* blk =
283
bman.get_allocator().alloc_bit_block();
284
bman.set_block_ptr(idx, blk);
285
bman.set_block_bit(idx);
286
gap_convert_to_bitset(blk, gap_blk);
287
}
288
else
289
{
290
gap_word_t* gap_blk_new =
291
bman.allocate_gap_block(level, gap_blk, glevel_len_);
292
293
bm::word_t* p = (bm::word_t*) gap_blk_new;
294
BMSET_PTRGAP(p);
295
bman.set_block_ptr(idx, p);
296
}
297
bman.get_allocator().free_gap_block(gap_blk, bman.glen());
298
}
299
300
private:
301
const gap_word_t* glevel_len_;
302
};
303
304
305
/*! Bitblock optimization functor */
306
class block_opt_func : public bm_func_base
307
{
308
public:
309
block_opt_func(blocks_manager& bm,
310
bm::word_t* temp_block,
311
int opt_mode,
312
bv_statistics* bv_stat=0)
313
: bm_func_base(bm),
314
temp_block_(temp_block),
315
opt_mode_(opt_mode),
316
stat_(bv_stat),
317
empty_(0)
318
{
319
BM_ASSERT(temp_block);
320
}
321
322
void on_empty_top(unsigned i)
323
{
324
bm::word_t*** blk_root = this->bm_.get_rootblock();
325
bm::word_t** blk_blk = blk_root[i];
326
if (blk_blk)
327
{
328
this->bm_.get_allocator().free_ptr(blk_blk);
329
blk_root[i] = 0;
330
}
331
if (stat_)
332
{
333
stat_->max_serialize_mem += sizeof(unsigned) + 1;
334
}
335
}
336
void on_empty_block(unsigned /* block_idx*/ ) { ++empty_; }
337
338
void operator()(bm::word_t* block, unsigned idx)
339
{
340
blocks_manager& bman = this->bm_;
341
if (IS_FULL_BLOCK(block))
342
{
343
++empty_;
344
return;
345
}
346
347
if (stat_)
348
{
349
stat_->max_serialize_mem += empty_ << 2;
350
empty_ = 0;
351
}
352
353
gap_word_t* gap_blk;
354
if (BM_IS_GAP(*this, block, idx)) // gap block
355
{
356
gap_blk = BMGAP_PTR(block);
357
// check if block is empty (or all 1)
358
if (gap_is_all_zero(gap_blk, bm::gap_max_bits))
359
{
360
bman.set_block_ptr(idx, 0);
361
this->free_block(gap_blk, idx);
362
++empty_;
363
}
364
else
365
if (gap_is_all_one(gap_blk, bm::gap_max_bits))
366
{
367
bman.set_block_ptr(idx, FULL_BLOCK_ADDR);
368
this->free_block(gap_blk, idx);
369
++empty_;
370
}
371
else
372
{
373
// regular gap block - compute statistics
374
if (stat_)
375
{
376
stat_->add_gap_block(
377
bm::gap_capacity(gap_blk, bman.glen()),
378
bm::gap_length(gap_blk));
379
}
380
}
381
}
382
else // bit block
383
{
384
if (opt_mode_ < 3) // free_01 optimization
385
{
386
bm::wordop_t* blk1 = (wordop_t*)block;
387
bm::wordop_t* blk2 =
388
(wordop_t*)(block + bm::set_block_size);
389
390
bool b = bit_is_all_zero(blk1, blk2);
391
if (b)
392
{
393
bman.get_allocator().free_bit_block(block);
394
bman.set_block_ptr(idx, 0);
395
++empty_;
396
}
397
else
398
if (opt_mode_ == 2) // check if it is all 1 block
399
{
400
b = is_bits_one(blk1, blk2);
401
if (b)
402
{
403
bman.get_allocator().free_bit_block(block);
404
bman.set_block_ptr(idx, FULL_BLOCK_ADDR);
405
++empty_;
406
}
407
}
408
409
if (!b && stat_)
410
stat_->add_bit_block();
411
412
return;
413
}
414
415
// try to compress
416
417
gap_word_t* tmp_gap_blk = (gap_word_t*)temp_block_;
418
*tmp_gap_blk = bm::gap_max_level << 1;
419
420
unsigned threashold = bman.glen(bm::gap_max_level)-4;
421
422
unsigned len = bit_convert_to_gap(tmp_gap_blk,
423
block,
424
bm::gap_max_bits,
425
threashold);
426
if (len) // compression successful
427
{
428
bman.get_allocator().free_bit_block(block);
429
430
// check if new gap block can be eliminated
431
if (gap_is_all_zero(tmp_gap_blk, bm::gap_max_bits))
432
{
433
bman.set_block_ptr(idx, 0);
434
++empty_;
435
}
436
else if (gap_is_all_one(tmp_gap_blk, bm::gap_max_bits))
437
{
438
bman.set_block_ptr(idx, FULL_BLOCK_ADDR);
439
++empty_;
440
}
441
else
442
{
443
int level = bm::gap_calc_level(len, bman.glen());
444
445
gap_blk =
446
bman.allocate_gap_block(level, tmp_gap_blk);
447
bman.set_block_ptr(idx, (bm::word_t*)gap_blk);
448
bman.set_block_gap(idx);
449
if (stat_)
450
{
451
stat_->add_gap_block(
452
bm::gap_capacity(gap_blk, bman.glen()),
453
bm::gap_length(gap_blk));
454
}
455
}
456
}
457
else // non-compressable bit-block
458
{
459
if (stat_)
460
stat_->add_bit_block();
461
}
462
}
463
}
464
private:
465
void free_block(gap_word_t* gap_blk, unsigned idx)
466
{
467
this->bm_.get_allocator().free_gap_block(gap_blk,
468
this->bm_.glen());
469
this->bm_.set_block_bit(idx);
470
}
471
472
private:
473
bm::word_t* temp_block_;
474
int opt_mode_;
475
bv_statistics* stat_;
476
unsigned empty_;
477
};
478
479
/** Bitblock invert functor */
480
class block_invert_func : public bm_func_base
481
{
482
public:
483
block_invert_func(blocks_manager& bm)
484
: bm_func_base(bm) {}
485
486
void operator()(bm::word_t* block, unsigned idx)
487
{
488
if (!block)
489
{
490
this->bm_.set_block(idx, FULL_BLOCK_ADDR);
491
}
492
else
493
if (IS_FULL_BLOCK(block))
494
{
495
this->bm_.set_block_ptr(idx, 0);
496
}
497
else
498
{
499
if (BM_IS_GAP(*this, block, idx)) // gap block
500
{
501
gap_invert(BMGAP_PTR(block));
502
}
503
else // bit block
504
{
505
bm::wordop_t* wrd_ptr = (wordop_t*) block;
506
bm::wordop_t* wrd_end =
507
(wordop_t*) (block + bm::set_block_size);
508
bit_invert(wrd_ptr, wrd_end);
509
}
510
}
511
512
}
513
};
514
515
/** Set block zero functor */
516
class block_zero_func : public bm_func_base
517
{
518
public:
519
block_zero_func(blocks_manager& bm, bool free_mem)
520
: bm_func_base(bm),
521
free_mem_(free_mem)
522
{}
523
524
void operator()(bm::word_t* block, unsigned idx)
525
{
526
blocks_manager& bman = this->bm_;
527
if (IS_FULL_BLOCK(block))
528
{
529
bman.set_block_ptr(idx, 0);
530
}
531
else
532
{
533
if (BM_IS_GAP(*this, block, idx))
534
{
535
gap_set_all(BMGAP_PTR(block), bm::gap_max_bits, 0);
536
}
537
else // BIT block
538
{
539
if (free_mem_)
540
{
541
bman.get_allocator().free_bit_block(block);
542
bman.set_block_ptr(idx, 0);
543
}
544
else
545
{
546
bit_block_set(block, 0);
547
}
548
}
549
}
550
}
551
private:
552
bool free_mem_; //!< If "true" frees bitblocks memsets to '0'
553
};
554
555
/** Fill block with all-one bits functor */
556
class block_one_func : public bm_func_base
557
{
558
public:
559
block_one_func(blocks_manager& bm) : bm_func_base(bm) {}
560
561
void operator()(bm::word_t* block, unsigned idx)
562
{
563
if (!IS_FULL_BLOCK(block))
564
{
565
this->bm_.set_block_all_set(idx);
566
}
567
}
568
};
569
570
/** Block deallocation functor */
571
class block_free_func : public bm_func_base
572
{
573
public:
574
block_free_func(blocks_manager& bm) : bm_func_base(bm) {}
575
576
void operator()(bm::word_t* block, unsigned idx)
577
{
578
blocks_manager& bman = this->bm_;
579
if (BM_IS_GAP(bman, block, idx)) // gap block
580
{
581
bman.get_allocator().free_gap_block(BMGAP_PTR(block),
582
bman.glen());
583
}
584
else
585
{
586
bman.get_allocator().free_bit_block(block);
587
}
588
}
589
};
590
591
/** Block copy functor */
592
class block_copy_func : public bm_func_base
593
{
594
public:
595
block_copy_func(blocks_manager& bm_target,
596
const blocks_manager& bm_src)
597
: bm_func_base(bm_target),
598
bm_src_(bm_src)
599
{}
600
601
void operator()(bm::word_t* block, unsigned idx)
602
{
603
bool is_gap = bm_src_.is_block_gap(idx);
604
bm::word_t* new_blk;
605
606
blocks_manager& bman = this->bm_;
607
608
if (is_gap)
609
{
610
bm::gap_word_t* gap_block = BMGAP_PTR(block);
611
unsigned level = gap_level(gap_block);
612
new_blk = (bm::word_t*)
613
bman.get_allocator().alloc_gap_block(level,
614
bman.glen());
615
int len = gap_length(BMGAP_PTR(block));
616
::memcpy(new_blk, gap_block, len * sizeof(gap_word_t));
617
//BMSET_PTRGAP(new_blk);
618
}
619
else
620
{
621
if (IS_FULL_BLOCK(block))
622
{
623
new_blk = block;
624
}
625
else
626
{
627
new_blk = bman.get_allocator().alloc_bit_block();
628
bit_block_copy(new_blk, block);
629
}
630
}
631
bman.set_block(idx, new_blk, is_gap);
632
}
633
634
private:
635
const blocks_manager& bm_src_;
636
};
637
638
639
public:
640
641
blocks_manager(const gap_word_t* glevel_len,
642
bm::id_t max_bits,
643
const Alloc& alloc = Alloc())
644
: temp_block_(0),
645
alloc_(alloc)
646
{
647
::memcpy(glevel_len_, glevel_len, sizeof(glevel_len_));
648
649
if (max_bits)
650
{
651
top_block_size_ = compute_top_block_size(max_bits);
652
// allocate first level descr. of blocks
653
blocks_ = (bm::word_t***) alloc_.alloc_ptr(top_block_size_);
654
::memset(blocks_, 0, top_block_size_ * sizeof(bm::word_t**));
655
}
656
else
657
{
658
top_block_size_ = 0;
659
blocks_ = 0;
660
}
661
volatile const char* vp = _copyright<true>::_p;
662
char c = *vp;
663
c = 0;
664
effective_top_block_size_ = 1;
665
}
666
667
blocks_manager(const blocks_manager& blockman)
668
: blocks_(0),
669
top_block_size_(blockman.top_block_size_),
670
effective_top_block_size_(blockman.effective_top_block_size_),
671
#ifdef BM_DISBALE_BIT_IN_PTR
672
gap_flags_(blockman.gap_flags_),
673
#endif
674
temp_block_(0),
675
alloc_(blockman.alloc_)
676
{
677
::memcpy(glevel_len_, blockman.glevel_len_, sizeof(glevel_len_));
678
679
blocks_ = (bm::word_t***)alloc_.alloc_ptr(top_block_size_);
680
::memset(blocks_, 0, top_block_size_ * sizeof(bm::word_t**));
681
682
blocks_manager* bm =
683
const_cast<blocks_manager*>(&blockman);
684
685
word_t*** blk_root = bm->blocks_root();
686
687
block_copy_func copy_func(*this, blockman);
688
for_each_nzblock(blk_root, top_block_size_,
689
bm::set_array_size, copy_func);
690
}
691
692
~blocks_manager()
693
{
694
alloc_.free_bit_block(temp_block_);
695
deinit_tree();
696
}
697
698
void free_ptr(bm::word_t** ptr)
699
{
700
if (ptr) alloc_.free_ptr(ptr);
701
}
702
703
/**
704
\brief Compute size of the block array needed to store bits
705
\param bits_to_store - supposed capacity (number of bits)
706
\return size of the top level block
707
*/
708
unsigned compute_top_block_size(bm::id_t bits_to_store)
709
{
710
if (bits_to_store == bm::id_max) // working in full-range mode
711
{
712
return bm::set_array_size;
713
}
714
715
unsigned top_block_size =
716
bits_to_store / (bm::set_block_size * sizeof(bm::word_t) *
717
bm::set_array_size * 8);
718
if (top_block_size < bm::set_array_size) ++top_block_size;
719
return top_block_size;
720
}
721
722
/**
723
Returns current capacity (bits)
724
*/
725
bm::id_t capacity() const
726
{
727
// arithmetic overflow protection...
728
return top_block_size_ == bm::set_array_size ? bm::id_max :
729
top_block_size_ * bm::set_array_size * bm::bits_in_block;
730
}
731
732
/**
733
\brief Finds block in 2-level blocks array
734
\param nb - Index of block (logical linear number)
735
\return block adress or NULL if not yet allocated
736
*/
737
bm::word_t* get_block(unsigned nb) const
738
{
739
unsigned block_idx = nb >> bm::set_array_shift;
740
if (block_idx >= top_block_size_)
741
{
742
return 0;
743
}
744
bm::word_t** blk_blk = blocks_[block_idx];
745
return blk_blk ? blk_blk[nb & bm::set_array_mask] : 0;
746
}
747
748
/**
749
\brief Finds block in 2-level blocks array
750
Specilized version of get_block(unsigned), returns an additional
751
condition when there are no more blocks
752
753
\param nb - Index of block (logical linear number)
754
\param no_more_blocks - 1 if there are no more blocks at all
755
\return block adress or NULL if not yet allocated
756
*/
757
bm::word_t* get_block(unsigned nb, int* no_more_blocks) const
758
{
759
unsigned block_idx = nb >> bm::set_array_shift;
760
if (block_idx >= top_block_size_)
761
{
762
*no_more_blocks = 1;
763
return 0;
764
}
765
*no_more_blocks = 0;
766
bm::word_t** blk_blk = blocks_[block_idx];
767
return blk_blk ? blk_blk[nb & bm::set_array_mask] : 0;
768
}
769
770
/**
771
Recalculate absolute block address into coordinates
772
*/
773
void get_block_coord(unsigned nb, unsigned* i, unsigned* j) const
774
{
775
BM_ASSERT(i);
776
BM_ASSERT(j);
777
778
*i = nb >> bm::set_array_shift; // top block address
779
*j = nb & bm::set_array_mask; // address in sub-block
780
}
781
782
bool is_no_more_blocks(unsigned nb) const
783
{
784
unsigned i,j;
785
get_block_coord(nb, &i, &j);
786
for (;i < effective_top_block_size_; ++i)
787
{
788
bm::word_t** blk_blk = blocks_[i];
789
if (!blk_blk)
790
{
791
nb += bm::set_array_size;
792
}
793
else
794
for (;j < bm::set_array_size; ++j, ++nb)
795
{
796
bm::word_t* blk = blk_blk[j];
797
if (blk && !is_block_zero(nb, blk))
798
{
799
return false;
800
}
801
} // for j
802
j = 0;
803
} // for i
804
return true;
805
}
806
807
/**
808
\brief Finds block in 2-level blocks array
809
\param i - top level block index
810
\param j - second level block index
811
\return block adress or NULL if not yet allocated
812
*/
813
const bm::word_t* get_block(unsigned i, unsigned j) const
814
{
815
if (i >= top_block_size_) return 0;
816
const bm::word_t* const* blk_blk = blocks_[i];
817
return (blk_blk == 0) ? 0 : blk_blk[j];
818
}
819
820
/**
821
\brief Function returns top-level block in 2-level blocks array
822
\param i - top level block index
823
\return block adress or NULL if not yet allocated
824
*/
825
const bm::word_t* const * get_topblock(unsigned i) const
826
{
827
return (i >= top_block_size_) ? 0 : blocks_[i];
828
}
829
830
/**
831
\brief Returns root block in the tree.
832
*/
833
bm::word_t*** get_rootblock() const
834
{
835
blocks_manager* bm =
836
const_cast<blocks_manager*>(this);
837
return bm->blocks_root();
838
}
839
840
void set_block_all_set(unsigned nb)
841
{
842
bm::word_t* block = this->get_block(nb);
843
set_block(nb, const_cast<bm::word_t*>(FULL_BLOCK_ADDR));
844
845
// If we keep block type flag in pointer itself we dp not need
846
// to clear gap bit
847
#ifdef BM_DISBALE_BIT_IN_PTR
848
set_block_bit(nb);
849
#endif
850
851
if (BM_IS_GAP(*this, block, nb))
852
{
853
alloc_.free_gap_block(BMGAP_PTR(block), glevel_len_);
854
}
855
else
856
{
857
alloc_.free_bit_block(block);
858
}
859
}
860
861
/**
862
Create all-zeros bit block. Old block (if exists) is deleted.
863
*/
864
bm::word_t* make_bit_block(unsigned nb)
865
{
866
bm::word_t* block = this->get_allocator().alloc_bit_block();
867
bit_block_set(block, 0);
868
bm::word_t* old_block = set_block(nb, block);
869
if (IS_VALID_ADDR(old_block))
870
{
871
if (BM_IS_GAP(*this, old_block, nb))
872
{
873
alloc_.free_gap_block(BMGAP_PTR(old_block), glen());
874
}
875
else
876
{
877
alloc_.free_bit_block(old_block);
878
}
879
}
880
return block;
881
}
882
883
/**
884
Function checks if block is not yet allocated, allocates it and sets to
885
all-zero or all-one bits.
886
887
If content_flag == 1 (ALLSET block) requested and taken block is already ALLSET,
888
function will return NULL
889
890
initial_block_type and actual_block_type : 0 - bitset, 1 - gap
891
*/
892
bm::word_t* check_allocate_block(unsigned nb,
893
unsigned content_flag,
894
int initial_block_type,
895
int* actual_block_type,
896
bool allow_null_ret=true)
897
{
898
bm::word_t* block = this->get_block(nb);
899
900
if (!IS_VALID_ADDR(block)) // NULL block or ALLSET
901
{
902
// if we wanted ALLSET and requested block is ALLSET return NULL
903
unsigned block_flag = IS_FULL_BLOCK(block);
904
*actual_block_type = initial_block_type;
905
if (block_flag == content_flag && allow_null_ret)
906
{
907
return 0; // it means nothing to do for the caller
908
}
909
910
if (initial_block_type == 0) // bitset requested
911
{
912
block = alloc_.alloc_bit_block();
913
// initialize block depending on its previous status
914
bit_block_set(block, block_flag ? 0xFF : 0);
915
set_block(nb, block);
916
}
917
else // gap block requested
918
{
919
bm::gap_word_t* gap_block = allocate_gap_block(0);
920
gap_set_all(gap_block, bm::gap_max_bits, block_flag);
921
set_block(nb, (bm::word_t*)gap_block, true/*gap*/);
922
return (bm::word_t*)gap_block;
923
}
924
}
925
else // block already exists
926
{
927
*actual_block_type = BM_IS_GAP((*this), block, nb);
928
}
929
930
return block;
931
}
932
933
/*! @brief Fills all blocks with 0.
934
@param free_mem - if true function frees the resources
935
*/
936
void set_all_zero(bool free_mem)
937
{
938
block_zero_func zero_func(*this, free_mem);
939
for_each_nzblock(blocks_, top_block_size_,
940
bm::set_array_size, zero_func);
941
}
942
943
/*! Replaces all blocks with ALL_ONE block.
944
*/
945
void set_all_one()
946
{
947
block_one_func func(*this);
948
for_each_block(blocks_, top_block_size_,
949
bm::set_array_size, func);
950
}
951
952
/**
953
Places new block into descriptors table, returns old block's address.
954
Old block is not deleted.
955
*/
956
bm::word_t* set_block(unsigned nb, bm::word_t* block)
957
{
958
bm::word_t* old_block;
959
960
// top block index
961
register unsigned nblk_blk = nb >> bm::set_array_shift;
962
963
// auto-resize the top block array
964
if (nblk_blk >= top_block_size_)
965
reserve_top_blocks(nblk_blk + 1);
966
if (nblk_blk >= effective_top_block_size_)
967
effective_top_block_size_ = nblk_blk + 1;
968
969
// If first level array not yet allocated, allocate it and
970
// assign block to it
971
if (blocks_[nblk_blk] == 0)
972
{
973
blocks_[nblk_blk] = (bm::word_t**)alloc_.alloc_ptr();
974
::memset(blocks_[nblk_blk], 0,
975
bm::set_array_size * sizeof(bm::word_t*));
976
977
old_block = 0;
978
}
979
else
980
{
981
old_block = blocks_[nblk_blk][nb & bm::set_array_mask];
982
}
983
984
// NOTE: block will be replaced without freeing,
985
// potential memory leak may lay here....
986
blocks_[nblk_blk][nb & bm::set_array_mask] = block; // equivalent to %
987
988
return old_block;
989
}
990
991
/**
992
Places new block into descriptors table, returns old block's address.
993
Old block is not deleted.
994
*/
995
bm::word_t* set_block(unsigned nb, bm::word_t* block, bool gap)
996
{
997
bm::word_t* old_block;
998
999
if (block)
1000
{
1001
if (gap)
1002
{
1003
#ifdef BM_DISBALE_BIT_IN_PTR
1004
gap_flags_.set(nb);
1005
#else
1006
block = (bm::word_t*)BMPTR_SETBIT0(block);
1007
#endif
1008
}
1009
else
1010
{
1011
#ifdef BM_DISBALE_BIT_IN_PTR
1012
gap_flags_.set(nb, false);
1013
#else
1014
block = (bm::word_t*)BMPTR_CLEARBIT0(block);
1015
#endif
1016
}
1017
}
1018
1019
// top block index
1020
register unsigned nblk_blk = nb >> bm::set_array_shift;
1021
1022
// auto-resize the top block array
1023
if (nblk_blk >= top_block_size_)
1024
reserve_top_blocks(nblk_blk + 1);
1025
if (nblk_blk >= effective_top_block_size_)
1026
effective_top_block_size_ = nblk_blk + 1;
1027
1028
// If first level array not yet allocated, allocate it and
1029
// assign block to it
1030
if (blocks_[nblk_blk] == 0)
1031
{
1032
blocks_[nblk_blk] = (bm::word_t**)alloc_.alloc_ptr();
1033
::memset(blocks_[nblk_blk], 0,
1034
bm::set_array_size * sizeof(bm::word_t*));
1035
1036
old_block = 0;
1037
}
1038
else
1039
{
1040
old_block = blocks_[nblk_blk][nb & bm::set_array_mask];
1041
}
1042
1043
// NOTE: block will be replaced without freeing,
1044
// potential memory leak may lay here....
1045
blocks_[nblk_blk][nb & bm::set_array_mask] = block; // equivalent to %
1046
1047
return old_block;
1048
}
1049
1050
/**
1051
Places new block into blocks table.
1052
*/
1053
void set_block_ptr(unsigned nb, bm::word_t* block)
1054
{
1055
BM_ASSERT((nb >> bm::set_array_shift) < effective_top_block_size_);
1056
blocks_[nb >> bm::set_array_shift][nb & bm::set_array_mask] = block;
1057
}
1058
1059
/**
1060
\brief Converts block from type gap to conventional bitset block.
1061
\param nb - Block's index.
1062
\param gap_block - Pointer to the gap block,
1063
if NULL block nb will be taken
1064
\return new bit block's memory
1065
*/
1066
bm::word_t* convert_gap2bitset(unsigned nb, gap_word_t* gap_block=0)
1067
{
1068
bm::word_t* block = this->get_block(nb);
1069
if (gap_block == 0)
1070
{
1071
gap_block = BMGAP_PTR(block);
1072
}
1073
1074
BM_ASSERT(IS_VALID_ADDR((bm::word_t*)gap_block));
1075
BM_ASSERT(is_block_gap(nb)); // must be GAP type
1076
1077
bm::word_t* new_block = alloc_.alloc_bit_block();
1078
1079
gap_convert_to_bitset(new_block, gap_block);
1080
1081
// new block will replace the old one(no deletion)
1082
set_block_ptr(nb, new_block);
1083
1084
alloc_.free_gap_block(BMGAP_PTR(block), glen());
1085
1086
// If GAP flag is in block pointer no need to clean the gap bit twice
1087
#ifdef BM_DISBALE_BIT_IN_PTR
1088
set_block_bit(nb);
1089
#endif
1090
1091
return new_block;
1092
}
1093
1094
/**
1095
Make sure block turns into true bit-block if it is GAP or a full block
1096
*/
1097
bm::word_t* deoptimize_block(unsigned nb)
1098
{
1099
bm::word_t* block = this->get_block(nb);
1100
if (BM_IS_GAP(*this, block, nb))
1101
{
1102
return convert_gap2bitset(nb);
1103
}
1104
if (IS_FULL_BLOCK(block))
1105
{
1106
bm::word_t* new_block = get_allocator().alloc_bit_block();
1107
bit_block_copy(new_block, block);
1108
set_block(nb, new_block);
1109
return new_block;
1110
}
1111
return block;
1112
}
1113
1114
/**
1115
Free block, make it zero pointer in the tree
1116
*/
1117
bm::word_t* zero_block(unsigned nb)
1118
{
1119
bm::word_t* block = this->get_block(nb);
1120
if (!block) return block;
1121
if (BM_IS_GAP(*this, block, nb)) // gap block
1122
{
1123
get_allocator().free_gap_block(BMGAP_PTR(block), glen());
1124
}
1125
else
1126
{
1127
// deallocates only valid pointers
1128
get_allocator().free_bit_block(block);
1129
}
1130
set_block(nb, 0);
1131
return 0;
1132
}
1133
1134
/**
1135
Count number of bits ON in the block
1136
*/
1137
bm::id_t block_bitcount(const bm::word_t* block, unsigned idx) const
1138
{
1139
id_t count = 0;
1140
if (!block) return count;
1141
if (IS_FULL_BLOCK(block))
1142
count = bm::bits_in_block;
1143
else
1144
{
1145
if (BM_IS_GAP(*this, block, idx))
1146
{
1147
count = gap_bit_count(BMGAP_PTR(block));
1148
}
1149
else // bitset
1150
{
1151
count =
1152
bit_block_calc_count(block,
1153
block + bm::set_block_size);
1154
}
1155
}
1156
return count;
1157
}
1158
1159
/**
1160
\brief Extends GAP block to the next level or converts it to bit block.
1161
\param nb - Block's linear index.
1162
\param blk - Blocks's pointer
1163
*/
1164
void extend_gap_block(unsigned nb, gap_word_t* blk)
1165
{
1166
unsigned level = bm::gap_level(blk);
1167
unsigned len = bm::gap_length(blk);
1168
if (level == bm::gap_max_level || len >= gap_max_buff_len)
1169
{
1170
convert_gap2bitset(nb);
1171
}
1172
else
1173
{
1174
bm::word_t* new_blk = (bm::word_t*)allocate_gap_block(++level, blk);
1175
1176
BMSET_PTRGAP(new_blk);
1177
1178
set_block_ptr(nb, new_blk);
1179
alloc_.free_gap_block(blk, glen());
1180
}
1181
}
1182
1183
bool is_block_gap(unsigned nb) const
1184
{
1185
#ifdef BM_DISBALE_BIT_IN_PTR
1186
return gap_flags_.test(nb)!=0;
1187
#else
1188
bm::word_t* block = get_block(nb);
1189
return BMPTR_TESTBIT0(block) != 0;
1190
#endif
1191
}
1192
1193
void set_block_bit(unsigned nb)
1194
{
1195
#ifdef BM_DISBALE_BIT_IN_PTR
1196
gap_flags_.set(nb, false);
1197
#else
1198
bm::word_t* block = get_block(nb);
1199
block = (bm::word_t*) BMPTR_CLEARBIT0(block);
1200
set_block_ptr(nb, block);
1201
#endif
1202
}
1203
1204
void set_block_gap(unsigned nb)
1205
{
1206
#ifdef BM_DISBALE_BIT_IN_PTR
1207
gap_flags_.set(nb);
1208
#else
1209
bm::word_t* block = get_block(nb);
1210
block = (bm::word_t*)BMPTR_SETBIT0(block);
1211
set_block_ptr(nb, block);
1212
#endif
1213
}
1214
1215
/**
1216
\fn bool bm::bvector::blocks_manager::is_block_zero(unsigned nb, bm::word_t* blk)
1217
\brief Checks all conditions and returns true if block consists of only 0 bits
1218
\param nb - Block's linear index.
1219
\param blk - Blocks's pointer
1220
\returns true if all bits are in the block are 0.
1221
*/
1222
bool is_block_zero(unsigned nb, const bm::word_t* blk) const
1223
{
1224
if (blk == 0) return true;
1225
1226
if (BM_IS_GAP(*this, blk, nb)) // GAP
1227
{
1228
gap_word_t* b = BMGAP_PTR(blk);
1229
return gap_is_all_zero(b, bm::gap_max_bits);
1230
}
1231
1232
// BIT
1233
for (unsigned i = 0; i < bm::set_block_size; ++i)
1234
{
1235
if (blk[i] != 0)
1236
return false;
1237
}
1238
return true;
1239
}
1240
1241
/**
1242
\brief Checks if block has only 1 bits
1243
\param nb - Index of the block.
1244
\param blk - Block's pointer
1245
\return true if block consists of 1 bits.
1246
*/
1247
bool is_block_one(unsigned nb, const bm::word_t* blk) const
1248
{
1249
if (blk == 0) return false;
1250
1251
if (BM_IS_GAP(*this, blk, nb)) // GAP
1252
{
1253
gap_word_t* b = BMGAP_PTR(blk);
1254
return gap_is_all_one(b, bm::gap_max_bits);
1255
}
1256
1257
// BIT block
1258
1259
if (IS_FULL_BLOCK(blk))
1260
{
1261
return true;
1262
}
1263
return is_bits_one((wordop_t*)blk,
1264
(wordop_t*)(blk + bm::set_block_size));
1265
}
1266
1267
/*! Returns temporary block, allocates if needed. */
1268
bm::word_t* check_allocate_tempblock()
1269
{
1270
return temp_block_ ? temp_block_
1271
: (temp_block_ = alloc_.alloc_bit_block());
1272
}
1273
1274
/*! Assigns new GAP lengths vector */
1275
void set_glen(const gap_word_t* glevel_len)
1276
{
1277
::memcpy(glevel_len_, glevel_len, sizeof(glevel_len_));
1278
}
1279
1280
1281
bm::gap_word_t* allocate_gap_block(unsigned level,
1282
gap_word_t* src = 0,
1283
const gap_word_t* glevel_len = 0)
1284
{
1285
if (!glevel_len)
1286
glevel_len = glevel_len_;
1287
gap_word_t* ptr = alloc_.alloc_gap_block(level, glevel_len);
1288
if (src)
1289
{
1290
unsigned len = gap_length(src);
1291
::memcpy(ptr, src, len * sizeof(gap_word_t));
1292
// Reconstruct the mask word using the new level code.
1293
*ptr = ((len-1) << 3) | (level << 1) | (*src & 1);
1294
}
1295
else
1296
{
1297
*ptr = level << 1;
1298
}
1299
return ptr;
1300
}
1301
1302
unsigned mem_used() const
1303
{
1304
unsigned mem_used = sizeof(*this);
1305
mem_used += temp_block_ ? sizeof(word_t) * bm::set_block_size : 0;
1306
mem_used += sizeof(bm::word_t**) * top_block_size_;
1307
1308
#ifdef BM_DISBALE_BIT_IN_PTR
1309
mem_used += gap_flags_.mem_used() - sizeof(gap_flags_);
1310
#endif
1311
1312
for (unsigned i = 0; i < top_block_size_; ++i)
1313
{
1314
mem_used += blocks_[i] ? sizeof(void*) * bm::set_array_size : 0;
1315
}
1316
1317
return mem_used;
1318
}
1319
1320
/** Returns true if second level block pointer is 0.
1321
*/
1322
bool is_subblock_null(unsigned nsub) const
1323
{
1324
return blocks_[nsub] == NULL;
1325
}
1326
1327
1328
bm::word_t*** blocks_root()
1329
{
1330
return blocks_;
1331
}
1332
1333
/*! \brief Returns current GAP level vector
1334
*/
1335
const gap_word_t* glen() const
1336
{
1337
return glevel_len_;
1338
}
1339
1340
/*! \brief Returns GAP level length for specified level
1341
\param level - level number
1342
*/
1343
unsigned glen(unsigned level) const
1344
{
1345
return glevel_len_[level];
1346
}
1347
1348
/*! \brief Swaps content
1349
\param bm another blocks manager
1350
*/
1351
void swap(blocks_manager& bm)
1352
{
1353
BM_ASSERT(this != &bm);
1354
1355
word_t*** btmp = blocks_;
1356
blocks_ = bm.blocks_;
1357
bm.blocks_ = btmp;
1358
1359
#ifdef BM_DISBALE_BIT_IN_PTR
1360
gap_flags_.swap(bm.gap_flags_);
1361
#endif
1362
1363
xor_swap(this->top_block_size_, bm.top_block_size_);
1364
xor_swap(this->effective_top_block_size_, bm.effective_top_block_size_);
1365
1366
BM_ASSERT(sizeof(glevel_len_) / sizeof(glevel_len_[0])
1367
== bm::gap_levels); // paranoiya check
1368
for (unsigned i = 0; i < bm::gap_levels; ++i)
1369
{
1370
xor_swap(glevel_len_[i], bm.glevel_len_[i]);
1371
}
1372
}
1373
1374
/*! \brief Returns size of the top block array in the tree
1375
*/
1376
unsigned top_block_size() const
1377
{
1378
return top_block_size_;
1379
}
1380
1381
/*! \brief Returns effective size of the top block array in the tree
1382
Effective size excludes NULL pointers at the top descriptor end
1383
*/
1384
unsigned effective_top_block_size() const
1385
{
1386
return effective_top_block_size_;
1387
/*
1388
unsigned i = top_block_size();
1389
if (!i) return 0;
1390
for (--i; i > 0; --i)
1391
{
1392
if (blocks_[i] != 0)
1393
{
1394
if (this->effective_top_block_size_ < i+1)
1395
{
1396
printf("Effective size error!\n");
1397
exit(1);
1398
}
1399
return i+1;
1400
}
1401
}
1402
BM_ASSERT(this->effective_top_block_size_ >= 1);
1403
return 1;
1404
*/
1405
1406
}
1407
1408
/**
1409
\brief reserve capacity for specified number of bits
1410
*/
1411
void reserve(unsigned max_bits)
1412
{
1413
if (max_bits)
1414
{
1415
unsigned b = compute_top_block_size(max_bits);
1416
reserve_top_blocks(b);
1417
}
1418
}
1419
1420
/*!
1421
\brief Make sure blocks manager has enough blocks capacity
1422
*/
1423
void reserve_top_blocks(unsigned top_blocks)
1424
{
1425
BM_ASSERT(top_blocks <= bm::set_array_size);
1426
if (top_blocks <= top_block_size_) return; // nothing to do
1427
bm::word_t*** new_blocks =
1428
(bm::word_t***)alloc_.alloc_ptr(top_blocks);
1429
1430
for (unsigned i = 0; i < top_block_size_; ++i)
1431
{
1432
new_blocks[i] = blocks_[i];
1433
}
1434
for (unsigned j = top_block_size_; j < top_blocks; ++j)
1435
{
1436
new_blocks[j] = 0;
1437
}
1438
alloc_.free_ptr(blocks_, top_block_size_);
1439
blocks_ = new_blocks;
1440
top_block_size_ = top_blocks;
1441
}
1442
1443
/** \brief Returns reference on the allocator
1444
*/
1445
allocator_type& get_allocator() { return alloc_; }
1446
1447
/** \brief Returns allocator
1448
*/
1449
allocator_type get_allocator() const { return alloc_; }
1450
1451
private:
1452
1453
void operator =(const blocks_manager&);
1454
1455
void deinit_tree()
1456
{
1457
if (blocks_ == 0) return;
1458
unsigned top_size = this->effective_top_block_size();
1459
block_free_func free_func(*this);
1460
for_each_nzblock(blocks_, top_size,
1461
bm::set_array_size, free_func);
1462
1463
for(unsigned i = 0; i < top_size; ++i)
1464
{
1465
bm::word_t** blk_blk = blocks_[i];
1466
if (blk_blk)
1467
alloc_.free_ptr(blk_blk);
1468
}
1469
alloc_.free_ptr(blocks_, top_block_size_);
1470
}
1471
1472
private:
1473
/// Tree of blocks.
1474
bm::word_t*** blocks_;
1475
/// Size of the top level block array in blocks_ tree
1476
unsigned top_block_size_;
1477
/// Effective size of the top level block array in blocks_ tree
1478
unsigned effective_top_block_size_;
1479
#ifdef BM_DISBALE_BIT_IN_PTR
1480
/// mini bitvector used to indicate gap blocks
1481
MS gap_flags_;
1482
#endif
1483
/// Temp block.
1484
bm::word_t* temp_block_;
1485
/// vector defines gap block lengths for different levels
1486
gap_word_t glevel_len_[bm::gap_levels];
1487
/// allocator
1488
allocator_type alloc_;
1489
};
1490
1491
/**
1492
Bit block buffer guard
1493
\internal
1494
*/
1495
template<class BlocksManager>
1496
class bit_block_guard
1497
{
1498
public:
1499
bit_block_guard(BlocksManager& bman, bm::word_t* blk=0)
1500
: bman_(bman),
1501
block_(blk)
1502
{}
1503
~bit_block_guard()
1504
{
1505
bman_.get_allocator().free_bit_block(block_);
1506
}
1507
void attach(bm::word_t* blk)
1508
{
1509
bman_.get_allocator().free_bit_block(block_);
1510
block_ = blk;
1511
}
1512
bm::word_t* allocate()
1513
{
1514
attach(bman_.get_allocator().alloc_bit_block());
1515
return block_;
1516
}
1517
bm::word_t* get() { return block_; }
1518
private:
1519
BlocksManager& bman_;
1520
bm::word_t* block_;
1521
};
1522
1523
1524
}
1525
1526
#endif
1527
Loggerhead is a web-based interface for Breezy
Version: 2.0.1