indexed_bitvec_core/
lib.rs

1/*
2   Copyright 2018 DarkOtter
3
4   Licensed under the Apache License, Version 2.0 (the "License");
5   you may not use this file except in compliance with the License.
6   You may obtain a copy of the License at
7
8       http://www.apache.org/licenses/LICENSE-2.0
9
10   Unless required by applicable law or agreed to in writing, software
11   distributed under the License is distributed on an "AS IS" BASIS,
12   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   See the License for the specific language governing permissions and
14   limitations under the License.
15*/
16//! Core operations to create indexes used to perform
17//! fast rank & select operations on bitvectors.
18#![no_std]
19
20#[cfg(test)]
21#[macro_use]
22extern crate std;
23
24#[cfg(test)]
25extern crate rand;
26#[cfg(test)]
27extern crate rand_xorshift;
28
29#[cfg(test)]
30#[macro_use]
31extern crate quickcheck;
32
33#[cfg(test)]
34#[macro_use]
35extern crate proptest;
36
37#[cold]
38fn ceil_div_slow(n: usize, d: usize) -> usize {
39    n / d + (if n % d > 0 { 1 } else { 0 })
40}
41
42#[inline(always)]
43pub(crate) fn ceil_div(n: usize, d: usize) -> usize {
44    let nb = n.wrapping_add(d - 1);
45    if nb < n {
46        return ceil_div_slow(n, d);
47    };
48    nb / d
49}
50
51#[cold]
52fn ceil_div_u64_slow(n: u64, d: u64) -> u64 {
53    n / d + (if n % d > 0 { 1 } else { 0 })
54}
55
56#[inline(always)]
57pub(crate) fn ceil_div_u64(n: u64, d: u64) -> u64 {
58    let nb = n.wrapping_add(d - 1);
59    if nb < n {
60        return ceil_div_u64_slow(n, d);
61    };
62    nb / d
63}
64
65mod ones_or_zeros;
66
67mod word;
68
69mod bytes;
70
71pub mod bits_ref;
72
73mod with_offset;
74
75pub mod index_raw;
76
77#[cfg(test)]
78mod tests {
79    use super::*;
80    use proptest::prelude::*;
81
82    #[test]
83    fn check_max_bits_in_bytes() {
84        assert!(<u64>::max_value() / 8 <= <usize>::max_value() as u64);
85    }
86
87    #[test]
88    fn test_ceil_div_examples() {
89        assert_eq!(0, ceil_div(0, 4));
90        assert_eq!(1, ceil_div(1, 4));
91        assert_eq!(1, ceil_div(4, 4));
92        assert_eq!(2, ceil_div(5, 4));
93        assert_eq!(2, ceil_div(6, 4));
94        assert_eq!(2, ceil_div(7, 4));
95        assert_eq!(2, ceil_div(8, 4));
96
97        assert_eq!(ceil_div_slow(0, 43), ceil_div(0, 43));
98        assert_eq!(ceil_div_slow(1, 43), ceil_div(1, 43));
99        assert_eq!(
100            ceil_div_slow(usize::max_value(), 43),
101            ceil_div(usize::max_value(), 43)
102        );
103    }
104
105    #[test]
106    fn test_ceil_div_u64_examples() {
107        assert_eq!(0, ceil_div_u64(0, 4));
108        assert_eq!(1, ceil_div_u64(1, 4));
109        assert_eq!(1, ceil_div_u64(4, 4));
110        assert_eq!(2, ceil_div_u64(5, 4));
111        assert_eq!(2, ceil_div_u64(6, 4));
112        assert_eq!(2, ceil_div_u64(7, 4));
113        assert_eq!(2, ceil_div_u64(8, 4));
114
115        assert_eq!(ceil_div_u64_slow(0, 43), ceil_div_u64(0, 43));
116        assert_eq!(ceil_div_u64_slow(1, 43), ceil_div_u64(1, 43));
117        assert_eq!(
118            ceil_div_u64_slow(u64::max_value(), 43),
119            ceil_div_u64(u64::max_value(), 43)
120        );
121    }
122
123    proptest! {
124        #[test]
125        fn test_ceil_div(x in any::<usize>(), d in 1..999999usize) {
126            prop_assert_eq!(ceil_div_slow(x, d), ceil_div(x, d));
127        }
128
129        #[test]
130        fn test_ceil_div_64(x in any::<u64>(), d in 1..999999u64) {
131            prop_assert_eq!(ceil_div_u64_slow(x, d), ceil_div_u64(x, d));
132        }
133    }
134
135}
indexed_bitvec_core/lib.rs

indexed_bitvec_core/
lib.rs
