NCBI C++ ToolKit
bmrs.h
Go to the documentation of this file.

Go to the SVN repository for this file.

1 #ifndef BMRS__H__INCLUDED__
2 #define BMRS__H__INCLUDED__
3 /*
4 Copyright(c) 2002-2019 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
5 
6 Licensed under the Apache License, Version 2.0 (the "License");
7 you may not use this file except in compliance with the License.
8 You may obtain a copy of the License at
9 
10  http://www.apache.org/licenses/LICENSE-2.0
11 
12 Unless required by applicable law or agreed to in writing, software
13 distributed under the License is distributed on an "AS IS" BASIS,
14 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 See the License for the specific language governing permissions and
16 limitations under the License.
17 
18 For more information please visit: http://bitmagic.io
19 */
20 
21 /*! \file bmrs.h
22  \brief Rank-Select index structures
23 */
24 
25 namespace bm
26 {
27 
28 /**
29  @brief Rank-Select acceleration index
30 
31  Index uses two-level acceleration structure:
32  bcount - running total popcount for all (possible) blocks
33  (missing blocks give duplicate counts as POPCNT(N-1) + 0).
34  subcount - sub-count inside blocks
35 
36  @ingroup bvector
37  @internal
38 */
39 template<typename BVAlloc>
40 class rs_index
41 {
42 public:
43  typedef BVAlloc bv_allocator_type;
44 
45 #ifdef BM64ADDR
46  typedef bm::id64_t size_type;
47  typedef bm::id64_t block_idx_type;
49 #else
53 #endif
54 
56 
57 public:
59  rs_index(const rs_index& rsi);
60 
61  /// init arrays to zeros
62  void init() BMNOEXCEPT;
63 
64  /// copy rs index
65  void copy_from(const rs_index& rsi);
66 
67  // -----------------------------------------------------------------
68 
69  /// set empty (no bits set super-block)
70  void set_null_super_block(unsigned i) BMNOEXCEPT;
71 
72  /// set FULL (all bits set super-block)
73  void set_full_super_block(unsigned i) BMNOEXCEPT;
74 
75  /// set super block count
76  void set_super_block(unsigned i, size_type bcount) BMNOEXCEPT;
77 
78  /// return bit-count in super-block
79  unsigned get_super_block_count(unsigned i) const BMNOEXCEPT;
80 
81  /// return running bit-count in super-block
83 
84  /// return number of super-blocks
86 
87  /// Find super-block with specified rank
89 
90 
91  /// set size of true super-blocks (not NULL and not FFFFF)
93 
94  /// Add block list belonging to one super block
95  void register_super_block(unsigned i,
96  const unsigned* bcount,
98 
99  /// find block position and sub-range for the specified rank
100  bool find(size_type* rank,
101  block_idx_type* nb, bm::gap_word_t* sub_range) const;
102 
103  /// return sub-clock counts (64-bit for additional information)
105 
106 
107  // -----------------------------------------------------------------
108 
109  /// reserve the capacity for block count
110  void resize(block_idx_type new_size);
111 
112  /// set total blocks
114 
115  /// get total blocks
116  size_type get_total() const { return total_blocks_; }
117 
118  /// return bit-count for specified block
119  unsigned count(block_idx_type nb) const;
120 
121  /// return total bit-count for the index
122  size_type count() const;
123 
124  /// return running bit-count for specified block
125  size_type rcount(block_idx_type nb) const;
126 
127  /// determine the sub-range within a bit-block
128  static
129  unsigned find_sub_range(unsigned block_bit_pos) BMNOEXCEPT;
130 
131  /// determine block sub-range for rank search
133  size_type& rank) const BMNOEXCEPT;
134 
135  /// find block position for the specified rank
137 
138 private:
144 
146 
147 private:
148  unsigned sblock_rows_;
149  sblock_count_vector_type sblock_count_; ///< super-block accumulated counts
150  sblock_row_vector_type sblock_row_idx_; ///< super-block row numbers
151  blocks_matrix_type block_matr_; ///< blocks within super-blocks (matrix)
152  blocks_matrix64_type sub_block_matr_; ///< sub-block counts
153  size_type total_blocks_; ///< total bit-blocks in the index
154  unsigned max_sblock_; ///< max. superblock index
155 };
156 
157 /**
158  Precalculated decision table fdr interval selection
159  @internal
160  */
161 template<bool T> struct rs_intervals
162 {
163  struct codes
164  {
165  const unsigned char _lut[65536] = {0, }; // nibble lookup table
166 
168  {
169  #if defined(BM64_SSE4) || defined(BM64_AVX2) || defined(BM64_AVX512)
170  const unsigned cutoff_bias = rs3_half_span/8;
171  #else
172  const unsigned cutoff_bias = 0;
173  #endif
174 
175  for (unsigned nbit_right = 0; nbit_right < 65536; ++nbit_right)
176  {
177  unsigned sub = (nbit_right <= rs3_border0) ? 0 :
178  (nbit_right > rs3_border1) ? 2 : 1;
179  switch(sub) // sub-range rank calc
180  {
181  case 0:
182  // |--x-----[0]-----------[1]----------|
183  if (nbit_right <= rs3_border0/2 + cutoff_bias)
184  sub = 0;
185  else // |--------[x]-----------[1]----------|
186  if (nbit_right == rs3_border0)
187  sub = 1;
188  else // |------x-[0]-----------[1]----------|
189  sub = 2;
190  break;
191 
192  case 1:
193  // |--------[0]-x---------[1]----------|
194  if (nbit_right <= rs3_border0_1 + cutoff_bias)
195  sub = 3;
196  else
197  {
198  // |--------[0]-----------[x]----------|
199  if (nbit_right == rs3_border1)
200  sub = 4;
201  else
202  {
203  // |--------[0]--------x--[1]----------|
204  unsigned d1 = nbit_right - bm::rs3_border0_1;
205  unsigned d2 = rs3_border1 - nbit_right;
206  if (d2 < d1) // |--------[0]----|----x-[1]--------|
207  sub = 5;
208  else // |--------[0]----|-x----[1]----------|
209  sub = 6;
210  }
211  }
212  break;
213 
214  case 2:
215  // |--------[0]-----------[1]-x---*----|
216  if (nbit_right <= rs3_border1_1)
217  {
218  unsigned d1 = nbit_right - bm::rs3_border1;
219  unsigned d2 = (rs3_border1_1 + cutoff_bias) - nbit_right;
220  if (d1 < d2) // |--------[0]-----------[1]-x---*----|
221  sub = 7;
222  else // |--------[0]-----------[1]---x-*----|
223  {
224  if (nbit_right == rs3_border1_1)
225  sub = 8;
226  else
227  sub = 9;
228  }
229  }
230  else
231  {
232  // |--------[0]-----------[1]----------x
233  if (nbit_right == bm::gap_max_bits-1)
234  sub = 10;
235  else
236  {
237  // |--------[0]-----------[1]-------x--|
238  BM_ASSERT(nbit_right > bm::rs3_border1_1);
239  unsigned d1 = nbit_right - bm::rs3_border1_1;
240  unsigned d2 = bm::gap_max_bits - nbit_right;
241  if (d2 < d1) // |--------[0]----------[1]----*---x-|
242  sub = 11;
243  else // |--------[0]----------[1]----*-x---|
244  sub = 12;
245  }
246  }
247  break;
248 
249  default:
250  BM_ASSERT(0);
251  sub = 0;
252  } // switch
253 
255  const_cast<unsigned char*>(_lut),
256  nbit_right, (unsigned char)sub);
257 
258  BM_ASSERT((unsigned char)sub ==
259  bm::get_nibble(const_cast<unsigned char*>(_lut), nbit_right));
260 
261  } // for
262  }
263  };
264  static codes _c;
265 };
266 template<bool T> typename rs_intervals<T>::codes rs_intervals<T>::_c;
267 
268 
269 //---------------------------------------------------------------------
270 //
271 //---------------------------------------------------------------------
272 
273 template<typename BVAlloc>
275 {
276  copy_from(rsi);
277 }
278 
279 //---------------------------------------------------------------------
280 
281 
282 template<typename BVAlloc>
284 {
285  sblock_count_.resize(0);
286  sblock_row_idx_.resize(0);
287  block_matr_.resize(0, 0, false);
288  sub_block_matr_.resize(0, 0, false);
289 
290  total_blocks_ = sblock_rows_ = max_sblock_ = 0;
291 }
292 
293 //---------------------------------------------------------------------
294 
295 template<typename BVAlloc>
297 {
298  sblock_rows_ = 0;
299 
300  block_idx_type sblock_count = (new_size >> bm::set_array_shift) + 3;
301  BM_ASSERT(sblock_count == (new_size / 256) + 3);
302  sblock_count_.resize(sblock_count);
303  sblock_row_idx_.resize(sblock_count);
304 }
305 
306 //---------------------------------------------------------------------
307 
308 template<typename BVAlloc>
310 {
311  sblock_rows_ = rsi.sblock_rows_;
312  sblock_count_ = rsi.sblock_count_;
313  sblock_row_idx_ = rsi.sblock_row_idx_;
314  block_matr_ = rsi.block_matr_;
315  sub_block_matr_ = rsi.sub_block_matr_;
316 
317  total_blocks_ = rsi.total_blocks_;
318  max_sblock_ = rsi.max_sblock_;
319 }
320 
321 //---------------------------------------------------------------------
322 
323 template<typename BVAlloc>
325 {
326  if (nb >= total_blocks_)
327  return 0;
328  unsigned i = unsigned(nb >> bm::set_array_shift);
329  size_type sb_count = get_super_block_count(i);
330 
331  if (!sb_count)
332  return 0;
333  if (sb_count == (bm::set_sub_array_size * bm::gap_max_bits)) // FULL BLOCK
334  return bm::gap_max_bits;
335 
336  unsigned j = unsigned(nb & bm::set_array_mask);
337 
338  unsigned row_idx = sblock_row_idx_[i+1];
339  const unsigned* row = block_matr_.row(row_idx);
340  unsigned bc;
341 
342  bc = (!j) ? row[j] : row[j] - row[j-1];
343  return bc;
344 }
345 
346 //---------------------------------------------------------------------
347 
348 template<typename BVAlloc>
351 {
352  if (!total_blocks_)
353  return 0;
354  return sblock_count_[max_sblock_ + 1];
355 }
356 
357 //---------------------------------------------------------------------
358 
359 template<typename BVAlloc>
362 {
363  unsigned i = unsigned(nb >> bm::set_array_shift);
364  size_type sb_rcount = i ? get_super_block_rcount(i-1) : i;
365 
366  unsigned sb_count = get_super_block_count(i);
367  if (!sb_count)
368  return sb_rcount;
369 
370  unsigned j = unsigned(nb & bm::set_array_mask);
371  if (sb_count == (bm::set_sub_array_size * bm::gap_max_bits)) // FULL BLOCK
372  {
373  sb_count = (j+1) * bm::gap_max_bits;
374  sb_rcount += sb_count;
375  return sb_rcount;
376  }
377 
378  unsigned row_idx = sblock_row_idx_[i+1];
379  const unsigned* row = block_matr_.row(row_idx);
380  unsigned bc = row[j];
381  sb_rcount += bc;
382  return sb_rcount;
383 
384 }
385 
386 //---------------------------------------------------------------------
387 
388 template<typename BVAlloc>
389 unsigned rs_index<BVAlloc>::find_sub_range(unsigned block_bit_pos) BMNOEXCEPT
390 {
391  return (block_bit_pos <= rs3_border0) ? 0 :
392  (block_bit_pos > rs3_border1) ? 2 : 1;
393 }
394 
395 //---------------------------------------------------------------------
396 
397 template<typename BVAlloc>
399  block_idx_type nb,
400  size_type& rank) const BMNOEXCEPT
401 {
402  bm::id64_t sub = sub_count(nb);
403  unsigned sub_cnt = unsigned(sub);
404  unsigned first = sub_cnt & 0xFFFF;
405  unsigned second = sub_cnt >> 16;
406 
407  if (rank > first)
408  {
409  rank -= first;
410  if (rank > second)
411  {
412  rank -= second;
413  return rs3_border1 + 1;
414  }
415  else
416  return rs3_border0 + 1;
417  }
418  return 0;
419 }
420 
421 //---------------------------------------------------------------------
422 
423 template<typename BVAlloc>
426 {
427  BM_ASSERT(rank);
428 
429  unsigned i = find_super_block(rank);
430  BM_ASSERT(i < super_block_size());
431 
432  size_type prev_rc = sblock_count_[i];
433  size_type curr_rc = sblock_count_[i+1];
434  size_type bc = curr_rc - prev_rc;
435 
436  BM_ASSERT(bc);
437 
438  unsigned j;
439  rank -= prev_rc;
440  if (bc == (bm::set_sub_array_size * bm::gap_max_bits)) // FULL BLOCK
441  {
442  for (j = 0; j < bm::set_sub_array_size; ++j)
443  {
444  if (rank <= bm::gap_max_bits)
445  break;
446  rank -= bm::gap_max_bits;
447  } // for j
448  }
449  else
450  {
451  unsigned row_idx = sblock_row_idx_[i+1];
452  const unsigned* row = block_matr_.row(row_idx);
454  j = bm::lower_bound_u32(row, unsigned(rank), 0, bm::set_sub_array_size-1);
455  }
457 
459  return nb;
460 }
461 
462 //---------------------------------------------------------------------
463 template<typename BVAlloc>
465 {
466  if (nb >= total_blocks_)
467  return 0;
468 
469  unsigned i = unsigned(nb >> bm::set_array_shift);
470  size_type sb_count = get_super_block_count(i);
471  if (!sb_count)
472  return 0;
473 
474  if (sb_count == (bm::set_sub_array_size * bm::gap_max_bits)) // FULL BLOCK
475  {
476  unsigned first = rs3_border0 + 1;
477  unsigned second = rs3_border1 - first + 1;
478  bm::id64_t aux0 = bm::rs3_border0_1 + 1;
479  bm::id64_t aux1 = bm::rs3_border1_1 + 1;
480  return (aux0 << 32) | (aux1 << 48) | (second << 16) | first;
481  }
482 
483  unsigned row_idx = sblock_row_idx_[i+1];
484  const bm::id64_t* sub_row = sub_block_matr_.row(row_idx);
485  return sub_row[nb & bm::set_array_mask]; // j - coordinate element
486 }
487 
488 
489 //---------------------------------------------------------------------
490 
491 template<typename BVAlloc>
493  block_idx_type* nb,
494  bm::gap_word_t* sub_range) const
495 {
496  BM_ASSERT(rank);
497  BM_ASSERT(nb);
498  BM_ASSERT(sub_range);
499 
500  unsigned i = find_super_block(*rank);
501  if (i > max_sblock_)
502  return false;
503 
504  size_type prev_rc = sblock_count_[i];
505  size_type curr_rc = sblock_count_[i+1];
506  size_type bc = curr_rc - prev_rc;
507 
508  BM_ASSERT(bc);
509 
510  unsigned j;
511  *rank -= prev_rc;
512  if (bc == (bm::set_sub_array_size * bm::gap_max_bits)) // FULL BLOCK
513  {
514  // TODO: optimize
515  size_type r = *rank;
516  for (j = 0; j < bm::set_sub_array_size; ++j)
517  {
518  if (r <= bm::gap_max_bits)
519  break;
520  r -= bm::gap_max_bits;
521  } // for j
522  *rank = r;
523 
524  unsigned first = rs3_border0 + 1;
525  unsigned second = rs3_border1 - first + 1;
526  if (*rank > first)
527  {
528  *rank -= first;
529  if (*rank > second)
530  {
531  *rank -= second;
532  *sub_range = bm::rs3_border1 + 1;
533  }
534  else
535  {
536  *sub_range = bm::rs3_border0 + 1;
537  }
538  }
539  else
540  {
541  *sub_range = 0;
542  }
543  }
544  else
545  {
546  unsigned row_idx = sblock_row_idx_[i+1];
547  const unsigned* row = block_matr_.row(row_idx);
548 
550  j = bm::lower_bound_u32(row, unsigned(*rank), 0, bm::set_sub_array_size-1);
552  if (j)
553  *rank -= row[j-1];
554 
555  const bm::id64_t* sub_row = sub_block_matr_.row(row_idx);
556  unsigned first = sub_row[j] & 0xFFFF;
557  unsigned second = (sub_row[j] >> 16) & 0xFFFF;
558  if (*rank > first)
559  {
560  *rank -= first;
561  if (*rank > second)
562  {
563  *rank -= second;
564  *sub_range = bm::rs3_border1 + 1;
565  }
566  else
567  {
568  *sub_range = bm::rs3_border0 + 1;
569  }
570  }
571  else
572  {
573  *sub_range = 0;
574  }
575  }
577  *nb = (i * bm::set_sub_array_size) + j;
578 
579  return true;
580 
581 }
582 
583 //---------------------------------------------------------------------
584 
585 template<typename BVAlloc>
587 {
588  if (i > max_sblock_)
589  max_sblock_ = i;
590  sblock_count_[i+1] = sblock_count_[i];
591  sblock_row_idx_[i+1] = 0U;
592 }
593 
594 //---------------------------------------------------------------------
595 
596 template<typename BVAlloc>
598 {
599  set_super_block(i, bm::set_sub_array_size * bm::gap_max_bits);
600 }
601 
602 //---------------------------------------------------------------------
603 
604 template<typename BVAlloc>
606 {
607  if (i > max_sblock_)
608  max_sblock_ = i;
609 
610  sblock_count_[i+1] = sblock_count_[i] + bcount;
611  if (bcount == (bm::set_sub_array_size * bm::gap_max_bits)) // FULL BLOCK
612  {
613  sblock_row_idx_[i+1] = 0;
614  }
615  else
616  {
617  sblock_row_idx_[i+1] = sblock_rows_;
618  ++sblock_rows_;
619  }
620 }
621 
622 //---------------------------------------------------------------------
623 
624 template<typename BVAlloc>
626 {
627  if (i > max_sblock_)
628  return 0;
629  size_type prev = sblock_count_[i];
630  size_type curr = sblock_count_[i + 1];
631  size_type cnt = curr - prev;
633  return unsigned(cnt);
634 }
635 
636 //---------------------------------------------------------------------
637 
638 template<typename BVAlloc>
641 {
642  if (i > max_sblock_)
643  i = max_sblock_;
644  return sblock_count_[i+1];
645 }
646 
647 //---------------------------------------------------------------------
648 
649 template<typename BVAlloc>
651 {
652  const sblock_count_type* bcount_arr = sblock_count_.begin();
653  unsigned i;
654 
655  #ifdef BM64ADDR
656  i = bm::lower_bound_u64(bcount_arr, rank, 1, max_sblock_+1);
657  #else
658  i = bm::lower_bound_u32(bcount_arr, rank, 1, max_sblock_+1);
659  #endif
660  return i-1;
661 }
662 
663 //---------------------------------------------------------------------
664 
665 template<typename BVAlloc>
668 {
669 
670  size_type total_sblocks = (size_type)sblock_count_.size();
671  if (total_sblocks)
672  return max_sblock_ + 1;
673  return 0;
674 }
675 
676 //---------------------------------------------------------------------
677 
678 template<typename BVAlloc>
680 {
681  block_matr_.resize(sb_eff+1, bm::set_sub_array_size);
682  sub_block_matr_.resize(sb_eff+1, bm::set_sub_array_size);
683 }
684 
685 //---------------------------------------------------------------------
686 
687 template<typename BVAlloc>
689  const unsigned* bcount,
690  const bm::id64_t* sub_count_in)
691 {
692  BM_ASSERT(bcount);
693  BM_ASSERT(sub_count_in);
694 
695  if (i > max_sblock_)
696  max_sblock_ = i;
697 
698 
699  sblock_row_idx_[i+1] = sblock_rows_;
700  unsigned* row = block_matr_.row(sblock_rows_);
701  bm::id64_t* sub_row = sub_block_matr_.row(sblock_rows_);
702  ++sblock_rows_;
703 
704  unsigned bc = 0;
705  for (unsigned j = 0; j < bm::set_sub_array_size; ++j)
706  {
707  bc += bcount[j];
708  row[j] = bc;
709  sub_row[j] = sub_count_in[j];
710  BM_ASSERT(bcount[j] >=
711  ((sub_count_in[j] >> 16) & bm::set_block_mask) +
712  (sub_count_in[j] & bm::set_block_mask));
713  } // for j
714  sblock_count_[i+1] = sblock_count_[i] + bc;
715 }
716 
717 //---------------------------------------------------------------------
718 
719 }
720 #endif
#define BMNOEXCEPT
Definition: bmdef.h:82
#define BM_ASSERT
Definition: bmdef.h:139
Rank-Select acceleration index.
Definition: bmrs.h:41
sblock_count_vector_type sblock_count_
super-block accumulated counts
Definition: bmrs.h:149
void init() BMNOEXCEPT
init arrays to zeros
Definition: bmrs.h:283
bm::id64_t sub_count(block_idx_type nb) const BMNOEXCEPT
return sub-clock counts (64-bit for additional information)
Definition: bmrs.h:464
size_type super_block_size() const BMNOEXCEPT
return number of super-blocks
Definition: bmrs.h:667
unsigned get_super_block_count(unsigned i) const BMNOEXCEPT
return bit-count in super-block
Definition: bmrs.h:625
bm::heap_vector< unsigned, bv_allocator_type, false > sblock_row_vector_type
Definition: bmrs.h:142
bm::dynamic_heap_matrix< bm::id64_t, bv_allocator_type > blocks_matrix64_type
Definition: bmrs.h:145
void set_super_block(unsigned i, size_type bcount) BMNOEXCEPT
set super block count
Definition: bmrs.h:605
rs_index()
Definition: bmrs.h:58
blocks_matrix_type block_matr_
blocks within super-blocks (matrix)
Definition: bmrs.h:151
static unsigned find_sub_range(unsigned block_bit_pos) BMNOEXCEPT
determine the sub-range within a bit-block
Definition: bmrs.h:389
size_type get_super_block_rcount(unsigned i) const BMNOEXCEPT
return running bit-count in super-block
Definition: bmrs.h:640
bm::pair< bm::gap_word_t, bm::gap_word_t > sb_pair_type
Definition: bmrs.h:55
bm::id_t sblock_count_type
Definition: bmrs.h:52
unsigned sblock_rows_
Definition: bmrs.h:148
size_type rcount(block_idx_type nb) const
return running bit-count for specified block
Definition: bmrs.h:361
blocks_matrix64_type sub_block_matr_
sub-block counts
Definition: bmrs.h:152
size_type count() const
return total bit-count for the index
Definition: bmrs.h:350
void resize(block_idx_type new_size)
reserve the capacity for block count
Definition: bmrs.h:296
unsigned find_super_block(size_type rank) const BMNOEXCEPT
Find super-block with specified rank.
Definition: bmrs.h:650
bm::id_t block_idx_type
Definition: bmrs.h:51
void resize_effective_super_blocks(size_type sb_eff)
set size of true super-blocks (not NULL and not FFFFF)
Definition: bmrs.h:679
bm::heap_vector< sblock_count_type, bv_allocator_type, false > sblock_count_vector_type
Definition: bmrs.h:140
void set_full_super_block(unsigned i) BMNOEXCEPT
set FULL (all bits set super-block)
Definition: bmrs.h:597
void copy_from(const rs_index &rsi)
copy rs index
Definition: bmrs.h:309
bm::dynamic_heap_matrix< unsigned, bv_allocator_type > blocks_matrix_type
Definition: bmrs.h:143
sblock_row_vector_type sblock_row_idx_
super-block row numbers
Definition: bmrs.h:150
size_type total_blocks_
total bit-blocks in the index
Definition: bmrs.h:153
bm::gap_word_t select_sub_range(block_idx_type nb, size_type &rank) const BMNOEXCEPT
determine block sub-range for rank search
Definition: bmrs.h:398
size_type get_total() const
get total blocks
Definition: bmrs.h:116
unsigned max_sblock_
max. superblock index
Definition: bmrs.h:154
bool find(size_type *rank, block_idx_type *nb, bm::gap_word_t *sub_range) const
find block position and sub-range for the specified rank
Definition: bmrs.h:492
void set_null_super_block(unsigned i) BMNOEXCEPT
set empty (no bits set super-block)
Definition: bmrs.h:586
bm::id_t size_type
Definition: bmrs.h:50
BVAlloc bv_allocator_type
Definition: bmrs.h:43
void set_total(size_type t)
set total blocks
Definition: bmrs.h:113
void register_super_block(unsigned i, const unsigned *bcount, const bm::id64_t *sub_count)
Add block list belonging to one super block.
Definition: bmrs.h:688
static DLIST_TYPE *DLIST_NAME() first(DLIST_LIST_TYPE *list)
Definition: dlist.tmpl.h:46
static DLIST_TYPE *DLIST_NAME() prev(DLIST_LIST_TYPE *list, DLIST_TYPE *item)
Definition: dlist.tmpl.h:61
int i
#include<zmmintrin.h>
Definition: bm.h:78
const unsigned set_array_mask
Definition: bmconst.h:97
const unsigned set_block_mask
Definition: bmconst.h:57
const unsigned set_sub_array_size
Definition: bmconst.h:95
const unsigned rs3_half_span
Definition: bmconst.h:121
void set_nibble(unsigned char *arr, unsigned idx, unsigned char v) noexcept
set nibble in the array
Definition: bmfunc.h:10251
unsigned char get_nibble(const unsigned char *arr, unsigned idx) noexcept
get nibble from the array
Definition: bmfunc.h:10280
unsigned long long int id64_t
Definition: bmconst.h:35
const unsigned rs3_border0_1
Definition: bmconst.h:122
unsigned int id_t
Definition: bmconst.h:38
const unsigned rs3_border1
Definition: bmconst.h:120
unsigned lower_bound_u32(const unsigned *arr, unsigned target, unsigned from, unsigned to) noexcept
Hybrid, binary-linear lower bound search in unsigned array.
Definition: bmfunc.h:9953
const unsigned set_array_shift
Definition: bmconst.h:96
unsigned short gap_word_t
Definition: bmconst.h:78
const unsigned rs3_border1_1
Definition: bmconst.h:123
const unsigned rs3_border0
Definition: bmconst.h:119
const unsigned gap_max_bits
Definition: bmconst.h:81
unsigned lower_bound_u64(const unsigned long long *arr, unsigned long long target, unsigned from, unsigned to) noexcept
Hybrid, binary-linear lower bound search in unsigned LONG array.
Definition: bmfunc.h:9988
EIPRangeType t
Definition: ncbi_localip.c:101
double r(size_t dimension_, const Int4 *score_, const double *prob_, double theta_)
static unsigned cnt[256]
#define row(bind, expected)
Definition: string_bind.c:73
Pair type.
Definition: bmfunc.h:154
const unsigned char _lut[65536]
Definition: bmrs.h:165
Precalculated decision table fdr interval selection.
Definition: bmrs.h:162
static codes _c
Definition: bmrs.h:264
#define const
Definition: zconf.h:232
Modified on Wed Apr 17 13:08:48 2024 by modify_doxy.py rev. 669887