diff options
Diffstat (limited to 'third_party/rust/smallbitvec')
| -rw-r--r-- | third_party/rust/smallbitvec/.cargo-checksum.json | 1 | ||||
| -rw-r--r-- | third_party/rust/smallbitvec/Cargo.toml | 28 | ||||
| -rw-r--r-- | third_party/rust/smallbitvec/LICENSE-APACHE | 201 | ||||
| -rw-r--r-- | third_party/rust/smallbitvec/LICENSE-MIT | 25 | ||||
| -rw-r--r-- | third_party/rust/smallbitvec/README.md | 9 | ||||
| -rw-r--r-- | third_party/rust/smallbitvec/benches/bench.rs | 239 | ||||
| -rw-r--r-- | third_party/rust/smallbitvec/src/lib.rs | 1061 | ||||
| -rw-r--r-- | third_party/rust/smallbitvec/src/tests.rs | 397 |
8 files changed, 1961 insertions, 0 deletions
diff --git a/third_party/rust/smallbitvec/.cargo-checksum.json b/third_party/rust/smallbitvec/.cargo-checksum.json new file mode 100644 index 0000000000..260228b30d --- /dev/null +++ b/third_party/rust/smallbitvec/.cargo-checksum.json @@ -0,0 +1 @@ +{"files":{"Cargo.toml":"2c3c147df069479810f3ec05588d3b180fb703c76d01d11688c46ad7a1a7f188","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"daa94322de7eab889e055932396160395bd8e3af82f56ae8c419d3049111da72","README.md":"4ac9c9b88726f6bcc3b454d61ce75a8224bd430584b765e304be9aa21815c327","benches/bench.rs":"5b446ae8a38d32ad08e06eafc93c3f158674d54e94b21005f871b35dd449cd39","src/lib.rs":"aed4abd2c1c347b38f89b61853ad15fa000abed0316f6f88bf680184cbb7f041","src/tests.rs":"f993740d6656eed737a1b0c7d15b10556c1ddc0ee62d91ff19aa6ad35dcb31e4"},"package":"75ce4f9dc4a41b4c3476cc925f1efb11b66df373a8fde5d4b8915fa91b5d995e"}
\ No newline at end of file diff --git a/third_party/rust/smallbitvec/Cargo.toml b/third_party/rust/smallbitvec/Cargo.toml new file mode 100644 index 0000000000..d6bd1266c6 --- /dev/null +++ b/third_party/rust/smallbitvec/Cargo.toml @@ -0,0 +1,28 @@ +# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO +# +# When uploading crates to the registry Cargo will automatically +# "normalize" Cargo.toml files for maximal compatibility +# with all versions of Cargo and also rewrite `path` dependencies +# to registry (e.g., crates.io) dependencies +# +# If you believe there's an error in this file please file an +# issue against the rust-lang/cargo repository. If you're +# editing this file be aware that the upstream Cargo.toml +# will likely look very different (and much more reasonable) + +[package] +name = "smallbitvec" +version = "2.5.1" +authors = ["Matt Brubeck <mbrubeck@limpet.net>"] +description = "A bit vector optimized for size and inline storage" +documentation = "https://docs.rs/smallbitvec" +readme = "README.md" +keywords = ["bitvec", "bitmap", "vec", "data-structures"] +categories = ["data-structures"] +license = "MIT / Apache-2.0" +repository = "https://github.com/servo/smallbitvec" +[dev-dependencies.bit-vec] +version = "0.4.4" + +[dev-dependencies.rand] +version = "0.4.2" diff --git a/third_party/rust/smallbitvec/LICENSE-APACHE b/third_party/rust/smallbitvec/LICENSE-APACHE new file mode 100644 index 0000000000..16fe87b06e --- /dev/null +++ b/third_party/rust/smallbitvec/LICENSE-APACHE @@ -0,0 +1,201 @@ + Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + +TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + +1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + +2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + +3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + +4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + +5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + +6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + +7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + +8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + +9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. + +END OF TERMS AND CONDITIONS + +APPENDIX: How to apply the Apache License to your work. + + To apply the Apache License to your work, attach the following + boilerplate notice, with the fields enclosed by brackets "[]" + replaced with your own identifying information. (Don't include + the brackets!) The text should be enclosed in the appropriate + comment syntax for the file format. We also recommend that a + file or class name and description of purpose be included on the + same "printed page" as the copyright notice for easier + identification within third-party archives. + +Copyright [yyyy] [name of copyright owner] + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License. diff --git a/third_party/rust/smallbitvec/LICENSE-MIT b/third_party/rust/smallbitvec/LICENSE-MIT new file mode 100644 index 0000000000..a9d616611d --- /dev/null +++ b/third_party/rust/smallbitvec/LICENSE-MIT @@ -0,0 +1,25 @@ +Copyright (c) 2017 Matt Brubeck + +Permission is hereby granted, free of charge, to any +person obtaining a copy of this software and associated +documentation files (the "Software"), to deal in the +Software without restriction, including without +limitation the rights to use, copy, modify, merge, +publish, distribute, sublicense, and/or sell copies of +the Software, and to permit persons to whom the Software +is furnished to do so, subject to the following +conditions: + +The above copyright notice and this permission notice +shall be included in all copies or substantial portions +of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF +ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED +TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A +PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT +SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION +OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR +IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER +DEALINGS IN THE SOFTWARE. diff --git a/third_party/rust/smallbitvec/README.md b/third_party/rust/smallbitvec/README.md new file mode 100644 index 0000000000..e4cc18152a --- /dev/null +++ b/third_party/rust/smallbitvec/README.md @@ -0,0 +1,9 @@ +# smallbitvec + +A bit vector that is only one word wide, and can store data either inline or +on the heap. Like the `bit-vec` crate but optimized for small inline size and +reduced allocations. + +* [Documentation](https://docs.rs/smallbitvec) +* [crates.io](https://crates.io/crates/smallbitvec) +* [Release notes](https://github.com/servo/smallbitvec/releases) diff --git a/third_party/rust/smallbitvec/benches/bench.rs b/third_party/rust/smallbitvec/benches/bench.rs new file mode 100644 index 0000000000..de44b6dc68 --- /dev/null +++ b/third_party/rust/smallbitvec/benches/bench.rs @@ -0,0 +1,239 @@ +// Copyright 2012-2014 The Rust Project Developers. +// Copyright 2017 Matt Brubeck. +// See the COPYRIGHT file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +#![feature(test)] + +extern crate bit_vec; +extern crate rand; +extern crate smallbitvec; +extern crate test; + +use std::hash::{Hash, Hasher}; + +use bit_vec::BitVec; +use rand::{weak_rng, Rng, XorShiftRng}; +use smallbitvec::SmallBitVec; +use test::{black_box, Bencher}; + +const BENCH_BITS: usize = 1 << 14; +const USIZE_BITS: usize = ::std::mem::size_of::<usize>() * 8; + +fn rng() -> XorShiftRng { + weak_rng() +} + +#[bench] +fn bench_bit_set_big_fixed_bv(b: &mut Bencher) { + let mut r = rng(); + let mut bit_vec = BitVec::from_elem(BENCH_BITS, false); + b.iter(|| { + for _ in 0..100 { + bit_vec.set((r.next_u64() as usize) % BENCH_BITS, true); + } + black_box(&bit_vec); + }); +} + +#[bench] +fn bench_bit_set_big_fixed_sbv(b: &mut Bencher) { + let mut r = rng(); + let mut bit_vec = SmallBitVec::from_elem(BENCH_BITS, false); + b.iter(|| { + for _ in 0..100 { + bit_vec.set(r.next_u64() as usize % BENCH_BITS, true); + } + black_box(&bit_vec); + }); +} + +#[bench] +fn bench_big_set_big_variable_bv(b: &mut Bencher) { + let mut r = rng(); + let mut bit_vec = BitVec::from_elem(BENCH_BITS, false); + b.iter(|| { + for _ in 0..100 { + bit_vec.set((r.next_u64() as usize) % BENCH_BITS, r.gen()); + } + black_box(&bit_vec); + }); +} + +#[bench] +fn bench_bit_set_big_variable_sbv(b: &mut Bencher) { + let mut r = rng(); + let mut bit_vec = SmallBitVec::from_elem(BENCH_BITS, false); + b.iter(|| { + for _ in 0..100 { + bit_vec.set(r.next_u64() as usize % BENCH_BITS, r.gen()); + } + black_box(&bit_vec); + }); +} + +#[bench] +fn bench_bit_set_small_bv(b: &mut Bencher) { + let mut r = rng(); + let mut bit_vec = BitVec::from_elem(USIZE_BITS, false); + b.iter(|| { + for _ in 0..100 { + bit_vec.set((r.next_u64() as usize) % USIZE_BITS, true); + } + black_box(&bit_vec); + }); +} + +#[bench] +fn bench_bit_set_small_sbv(b: &mut Bencher) { + let mut r = rng(); + let mut bit_vec = SmallBitVec::from_elem(USIZE_BITS, false); + b.iter(|| { + for _ in 0..100 { + bit_vec.set(r.next_u64() as usize % USIZE_BITS, true); + } + black_box(&bit_vec); + }); +} + +#[bench] +fn bench_bit_vec_small_eq_bv(b: &mut Bencher) { + let x = BitVec::from_elem(USIZE_BITS, false); + let y = BitVec::from_elem(USIZE_BITS, false); + b.iter(|| x == y); +} + +#[bench] +fn bench_bit_vec_small_eq_sbv(b: &mut Bencher) { + let x = SmallBitVec::from_elem(USIZE_BITS, false); + let y = SmallBitVec::from_elem(USIZE_BITS, false); + b.iter(|| x == y); +} + +#[bench] +fn bench_bit_vec_big_eq_bv(b: &mut Bencher) { + let x = BitVec::from_elem(BENCH_BITS, false); + let y = BitVec::from_elem(BENCH_BITS, false); + b.iter(|| x == y); +} + +#[bench] +fn bench_bit_vec_big_eq_sbv(b: &mut Bencher) { + let x = SmallBitVec::from_elem(BENCH_BITS, false); + let y = SmallBitVec::from_elem(BENCH_BITS, false); + b.iter(|| x == y); +} + +#[bench] +fn bench_bit_vec_small_iter_bv(b: &mut Bencher) { + let bit_vec = BitVec::from_elem(USIZE_BITS, false); + b.iter(|| { + let mut sum = 0; + for _ in 0..10 { + for pres in &bit_vec { + sum += pres as usize; + } + } + sum + }) +} + +#[bench] +fn bench_bit_vec_small_iter_sbv(b: &mut Bencher) { + let bit_vec = SmallBitVec::from_elem(USIZE_BITS, false); + b.iter(|| { + let mut sum = 0; + for _ in 0..10 { + for pres in &bit_vec { + sum += pres as usize; + } + } + sum + }) +} + +#[bench] +fn bench_bit_vec_big_iter_bv(b: &mut Bencher) { + let bit_vec = BitVec::from_elem(BENCH_BITS, false); + b.iter(|| { + let mut sum = 0; + for pres in &bit_vec { + sum += pres as usize; + } + sum + }) +} + +#[bench] +fn bench_bit_vec_big_iter_sbv(b: &mut Bencher) { + let bit_vec = SmallBitVec::from_elem(BENCH_BITS, false); + b.iter(|| { + let mut sum = 0; + for pres in &bit_vec { + sum += pres as usize; + } + sum + }) +} + +#[bench] +fn bench_from_elem_bv(b: &mut Bencher) { + let cap = black_box(BENCH_BITS); + let bit = black_box(true); + b.iter(|| BitVec::from_elem(cap, bit)); + b.bytes = cap as u64 / 8; +} + +#[bench] +fn bench_from_elem_sbv(b: &mut Bencher) { + let cap = black_box(BENCH_BITS); + let bit = black_box(true); + b.iter(|| SmallBitVec::from_elem(cap, bit)); + b.bytes = cap as u64 / 8; +} + +#[bench] +fn bench_remove_small(b: &mut Bencher) { + b.iter(|| { + let mut v = SmallBitVec::from_elem(USIZE_BITS, false); + for _ in 0..USIZE_BITS { + v.remove(0); + } + }); +} + +#[bench] +fn bench_remove_big(b: &mut Bencher) { + b.iter(|| { + let mut v = SmallBitVec::from_elem(BENCH_BITS, false); + for _ in 0..200 { + v.remove(0); + } + }); +} + +#[bench] +fn bench_hash_small(b: &mut Bencher) { + let mut hasher = std::collections::hash_map::DefaultHasher::new(); + let v = SmallBitVec::from_elem(USIZE_BITS, false); + b.iter(|| { + v.hash(&mut hasher); + }); + black_box(hasher.finish()); +} + +#[bench] +fn bench_hash_big(b: &mut Bencher) { + let mut hasher = std::collections::hash_map::DefaultHasher::new(); + let v = SmallBitVec::from_elem(BENCH_BITS, false); + b.iter(|| { + v.hash(&mut hasher); + }); + black_box(hasher.finish()); +} diff --git a/third_party/rust/smallbitvec/src/lib.rs b/third_party/rust/smallbitvec/src/lib.rs new file mode 100644 index 0000000000..49c443d668 --- /dev/null +++ b/third_party/rust/smallbitvec/src/lib.rs @@ -0,0 +1,1061 @@ +// Copyright 2017 Matt Brubeck. See the COPYRIGHT file at the top-level +// directory of this distribution and at http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! [`SmallBitVec`] is a bit vector, a vector of single-bit values stored compactly in memory. +//! +//! SmallBitVec grows dynamically, like the standard `Vec<T>` type. It can hold up to about one +//! word of bits inline (without a separate heap allocation). If the number of bits exceeds this +//! inline capacity, it will allocate a buffer on the heap. +//! +//! [`SmallBitVec`]: struct.SmallBitVec.html +//! +//! # Example +//! +//! ``` +//! use smallbitvec::SmallBitVec; +//! +//! let mut v = SmallBitVec::new(); +//! v.push(true); +//! v.push(false); +//! +//! assert_eq!(v[0], true); +//! assert_eq!(v[1], false); +//! ``` + +#![no_std] + +extern crate alloc; + +use alloc::{vec, vec::Vec, boxed::Box}; + +use core::cmp::max; +use core::fmt; +use core::hash; +use core::iter::{DoubleEndedIterator, ExactSizeIterator, FromIterator}; +use core::mem::{forget, replace, size_of}; +use core::ops::{Index, Range}; +use core::slice; + +/// Creates a [`SmallBitVec`] containing the arguments. +/// +/// `sbvec!` allows `SmallBitVec`s to be defined with the same syntax as array expressions. +/// There are two forms of this macro: +/// +/// - Create a [`SmallBitVec`] containing a given list of elements: +/// +/// ``` +/// # #[macro_use] extern crate smallbitvec; +/// # use smallbitvec::SmallBitVec; +/// # fn main() { +/// let v = sbvec![true, false, true]; +/// assert_eq!(v[0], true); +/// assert_eq!(v[1], false); +/// assert_eq!(v[2], true); +/// # } +/// ``` +/// +/// - Create a [`SmallBitVec`] from a given element and size: +/// +/// ``` +/// # #[macro_use] extern crate smallbitvec; +/// # use smallbitvec::SmallBitVec; +/// # fn main() { +/// let v = sbvec![true; 3]; +/// assert!(v.into_iter().eq(vec![true, true, true].into_iter())); +/// # } +/// ``` + +#[macro_export] +macro_rules! sbvec { + ($elem:expr; $n:expr) => ( + $crate::SmallBitVec::from_elem($n, $elem) + ); + ($($x:expr),*) => ( + [$($x),*].iter().cloned().collect::<$crate::SmallBitVec>() + ); + ($($x:expr,)*) => ( + sbvec![$($x),*] + ); +} + + +// FIXME: replace this with `debug_assert!` when it’s usable in `const`: +// * https://github.com/rust-lang/rust/issues/49146 +// * https://github.com/rust-lang/rust/issues/51999 +macro_rules! const_debug_assert_le { + ($left: ident <= $right: expr) => { + #[cfg(debug_assertions)] + // Causes an `index out of bounds` panic if `$left` is too large + [(); $right + 1][$left]; + } +} + +#[cfg(test)] +mod tests; + +/// A resizable bit vector, optimized for size and inline storage. +/// +/// `SmallBitVec` is exactly one word wide. Depending on the required capacity, this word +/// either stores the bits inline, or it stores a pointer to a separate buffer on the heap. +pub struct SmallBitVec { + data: usize, +} + +/// Total number of bits per word. +#[inline(always)] +const fn inline_bits() -> usize { + size_of::<usize>() * 8 +} + +/// For an inline vector, all bits except two can be used as storage capacity: +/// +/// - The rightmost bit is set to zero to signal an inline vector. +/// - The position of the rightmost nonzero bit encodes the length. +#[inline(always)] +const fn inline_capacity() -> usize { + inline_bits() - 2 +} + +/// Left shift amount to access the nth bit +#[inline(always)] +const fn inline_shift(n: usize) -> usize { + const_debug_assert_le!(n <= inline_capacity()); + // The storage starts at the leftmost bit. + inline_bits() - 1 - n +} + +/// An inline vector with the nth bit set. +#[inline(always)] +const fn inline_index(n: usize) -> usize { + 1 << inline_shift(n) +} + +/// An inline vector with the leftmost `n` bits set. +#[inline(always)] +fn inline_ones(n: usize) -> usize { + if n == 0 { + 0 + } else { + !0 << (inline_bits() - n) + } +} + +/// If the rightmost bit of `data` is set, then the remaining bits of `data` +/// are a pointer to a heap allocation. +const HEAP_FLAG: usize = 1; + +/// The allocation will contain a `Header` followed by a [Storage] buffer. +type Storage = usize; + +/// The number of bits in one `Storage`. +#[inline(always)] +fn bits_per_storage() -> usize { + size_of::<Storage>() * 8 +} + +/// Data stored at the start of the heap allocation. +/// +/// `Header` must have the same alignment as `Storage`. +struct Header { + /// The number of bits in this bit vector. + len: Storage, + + /// The number of elements in the [usize] buffer that follows this header. + buffer_len: Storage, +} + +impl Header { + /// Create a heap allocation with enough space for a header, + /// plus a buffer of at least `cap` bits, each initialized to `val`. + fn new(cap: usize, len: usize, val: bool) -> *mut Header { + let alloc_len = header_len() + buffer_len(cap); + let init = if val { !0 } else { 0 }; + + let v: Vec<Storage> = vec![init; alloc_len]; + + let buffer_len = v.capacity() - header_len(); + let header_ptr = v.as_ptr() as *mut Header; + + forget(v); + + unsafe { + (*header_ptr).len = len; + (*header_ptr).buffer_len = buffer_len; + } + header_ptr + } +} + +/// The number of `Storage` elements to allocate to hold a header. +#[inline(always)] +fn header_len() -> usize { + size_of::<Header>() / size_of::<Storage>() +} + +/// The minimum number of `Storage` elements to hold at least `cap` bits. +#[inline(always)] +fn buffer_len(cap: usize) -> usize { + (cap + bits_per_storage() - 1) / bits_per_storage() +} + +/// A typed representation of a `SmallBitVec`'s internal storage. +/// +/// The layout of the data inside both enum variants is a private implementation detail. +pub enum InternalStorage { + /// The internal representation of a `SmallBitVec` that has not spilled to a + /// heap allocation. + Inline(usize), + + /// The contents of the heap allocation of a spilled `SmallBitVec`. + Spilled(Box<[usize]>), +} + +impl SmallBitVec { + /// Create an empty vector. + #[inline] + pub const fn new() -> SmallBitVec { + SmallBitVec { + data: inline_index(0), + } + } + + /// Create a vector containing `len` bits, each set to `val`. + #[inline] + pub fn from_elem(len: usize, val: bool) -> SmallBitVec { + if len <= inline_capacity() { + return SmallBitVec { + data: if val { + inline_ones(len + 1) + } else { + inline_index(len) + }, + }; + } + let header_ptr = Header::new(len, len, val); + SmallBitVec { + data: (header_ptr as usize) | HEAP_FLAG, + } + } + + /// Create an empty vector with enough storage pre-allocated to store at least `cap` bits + /// without resizing. + #[inline] + pub fn with_capacity(cap: usize) -> SmallBitVec { + // Use inline storage if possible. + if cap <= inline_capacity() { + return SmallBitVec::new(); + } + + // Otherwise, allocate on the heap. + let header_ptr = Header::new(cap, 0, false); + SmallBitVec { + data: (header_ptr as usize) | HEAP_FLAG, + } + } + + /// The number of bits stored in this bit vector. + #[inline] + pub fn len(&self) -> usize { + if self.is_inline() { + // The rightmost nonzero bit is a sentinel. All bits to the left of + // the sentinel bit are the elements of the bit vector. + inline_bits() - self.data.trailing_zeros() as usize - 1 + } else { + self.header().len + } + } + + /// Returns `true` if this vector contains no bits. + #[inline] + pub fn is_empty(&self) -> bool { + self.len() == 0 + } + + /// The number of bits that can be stored in this bit vector without re-allocating. + #[inline] + pub fn capacity(&self) -> usize { + if self.is_inline() { + inline_capacity() + } else { + self.header().buffer_len * bits_per_storage() + } + } + + /// Get the nth bit in this bit vector. + #[inline] + pub fn get(&self, n: usize) -> Option<bool> { + if n < self.len() { + Some(unsafe { self.get_unchecked(n) }) + } else { + None + } + } + + /// Get the last bit in this bit vector. + #[inline] + pub fn last(&self) -> Option<bool> { + self.len().checked_sub(1).map(|n| unsafe { self.get_unchecked(n) }) + } + + /// Get the nth bit in this bit vector, without bounds checks. + #[inline] + pub unsafe fn get_unchecked(&self, n: usize) -> bool { + if self.is_inline() { + self.data & inline_index(n) != 0 + } else { + let buffer = self.buffer(); + let i = n / bits_per_storage(); + let offset = n % bits_per_storage(); + *buffer.get_unchecked(i) & (1 << offset) != 0 + } + } + + /// Set the nth bit in this bit vector to `val`. Panics if the index is out of bounds. + #[inline] + pub fn set(&mut self, n: usize, val: bool) { + assert!(n < self.len(), "Index {} out of bounds", n); + unsafe { + self.set_unchecked(n, val); + } + } + + /// Set the nth bit in this bit vector to `val`, without bounds checks. + #[inline] + pub unsafe fn set_unchecked(&mut self, n: usize, val: bool) { + if self.is_inline() { + if val { + self.data |= inline_index(n); + } else { + self.data &= !inline_index(n); + } + } else { + let buffer = self.buffer_mut(); + let i = n / bits_per_storage(); + let offset = n % bits_per_storage(); + if val { + *buffer.get_unchecked_mut(i) |= 1 << offset; + } else { + *buffer.get_unchecked_mut(i) &= !(1 << offset); + } + } + } + + /// Append a bit to the end of the vector. + /// + /// ``` + /// use smallbitvec::SmallBitVec; + /// let mut v = SmallBitVec::new(); + /// v.push(true); + /// + /// assert_eq!(v.len(), 1); + /// assert_eq!(v.get(0), Some(true)); + /// ``` + #[inline] + pub fn push(&mut self, val: bool) { + let idx = self.len(); + if idx == self.capacity() { + self.reserve(1); + } + unsafe { + self.set_len(idx + 1); + self.set_unchecked(idx, val); + } + } + + /// Remove the last bit from the vector and return it, if there is one. + /// + /// ``` + /// use smallbitvec::SmallBitVec; + /// let mut v = SmallBitVec::new(); + /// v.push(false); + /// + /// assert_eq!(v.pop(), Some(false)); + /// assert_eq!(v.len(), 0); + /// assert_eq!(v.pop(), None); + /// ``` + #[inline] + pub fn pop(&mut self) -> Option<bool> { + self.len().checked_sub(1).map(|last| unsafe { + let val = self.get_unchecked(last); + self.set_len(last); + val + }) + } + + /// Remove and return the bit at index `idx`, shifting all later bits toward the front. + /// + /// Panics if the index is out of bounds. + #[inline] + pub fn remove(&mut self, idx: usize) -> bool { + let len = self.len(); + let val = self[idx]; + + if self.is_inline() { + // Shift later bits, including the length bit, toward the front. + let mask = !inline_ones(idx); + let new_vals = (self.data & mask) << 1; + self.data = (self.data & !mask) | (new_vals & mask); + } else { + let first = idx / bits_per_storage(); + let offset = idx % bits_per_storage(); + let count = buffer_len(len); + { + // Shift bits within the first storage block. + let buf = self.buffer_mut(); + let mask = !0 << offset; + let new_vals = (buf[first] & mask) >> 1; + buf[first] = (buf[first] & !mask) | (new_vals & mask); + } + // Shift bits in subsequent storage blocks. + for i in (first + 1)..count { + // Move the first bit into the previous block. + let bit_idx = i * bits_per_storage(); + unsafe { + let first_bit = self.get_unchecked(bit_idx); + self.set_unchecked(bit_idx - 1, first_bit); + } + // Shift the remaining bits. + self.buffer_mut()[i] >>= 1; + } + // Decrement the length. + unsafe { + self.set_len(len - 1); + } + } + val + } + + /// Remove all elements from the vector, without deallocating its buffer. + #[inline] + pub fn clear(&mut self) { + unsafe { + self.set_len(0); + } + } + + /// Reserve capacity for at least `additional` more elements to be inserted. + /// + /// May reserve more space than requested, to avoid frequent reallocations. + /// + /// Panics if the new capacity overflows `usize`. + /// + /// Re-allocates only if `self.capacity() < self.len() + additional`. + #[inline] + pub fn reserve(&mut self, additional: usize) { + let old_cap = self.capacity(); + let new_cap = self.len() + .checked_add(additional) + .expect("capacity overflow"); + if new_cap <= old_cap { + return; + } + // Ensure the new capacity is at least double, to guarantee exponential growth. + let double_cap = old_cap.saturating_mul(2); + self.reallocate(max(new_cap, double_cap)); + } + + /// Set the length of the vector. The length must not exceed the capacity. + /// + /// If this makes the vector longer, then the values of its new elements + /// are not specified. + #[inline] + unsafe fn set_len(&mut self, len: usize) { + debug_assert!(len <= self.capacity()); + if self.is_inline() { + let sentinel = inline_index(len); + let mask = !(sentinel - 1); + self.data |= sentinel; + self.data &= mask; + } else { + self.header_mut().len = len; + } + } + + /// Returns an iterator that yields the bits of the vector in order, as `bool` values. + #[inline] + pub fn iter(&self) -> Iter { + Iter { + vec: self, + range: 0..self.len(), + } + } + + /// Returns an immutable view of a range of bits from this vec. + /// ``` + /// #[macro_use] extern crate smallbitvec; + /// let v = sbvec![true, false, true]; + /// let r = v.range(1..3); + /// assert_eq!(r[1], true); + /// ``` + #[inline] + pub fn range(&self, range: Range<usize>) -> VecRange { + assert!(range.end <= self.len(), "range out of bounds"); + VecRange { vec: &self, range } + } + + /// Returns true if all the bits in the vec are set to zero/false. + /// + /// On an empty vector, returns true. + #[inline] + pub fn all_false(&self) -> bool { + let mut len = self.len(); + if len == 0 { + return true; + } + + if self.is_inline() { + let mask = inline_ones(len); + self.data & mask == 0 + } else { + for &storage in self.buffer() { + if len >= bits_per_storage() { + if storage != 0 { + return false; + } + len -= bits_per_storage(); + } else { + let mask = (1 << len) - 1; + if storage & mask != 0 { + return false; + } + break; + } + } + true + } + } + + /// Returns true if all the bits in the vec are set to one/true. + /// + /// On an empty vector, returns true. + #[inline] + pub fn all_true(&self) -> bool { + let mut len = self.len(); + if len == 0 { + return true; + } + + if self.is_inline() { + let mask = inline_ones(len); + self.data & mask == mask + } else { + for &storage in self.buffer() { + if len >= bits_per_storage() { + if storage != !0 { + return false; + } + len -= bits_per_storage(); + } else { + let mask = (1 << len) - 1; + if storage & mask != mask { + return false; + } + break; + } + } + true + } + } + + /// Shorten the vector, keeping the first `len` elements and dropping the rest. + /// + /// If `len` is greater than or equal to the vector's current length, this has no + /// effect. + /// + /// This does not re-allocate. + pub fn truncate(&mut self, len: usize) { + unsafe { + if len < self.len() { + self.set_len(len); + } + } + } + + /// Resizes the vector so that its length is equal to `len`. + /// + /// If `len` is less than the current length, the vector simply truncated. + /// + /// If `len` is greater than the current length, `value` is appended to the + /// vector until its length equals `len`. + pub fn resize(&mut self, len: usize, value: bool) { + let old_len = self.len(); + + if len > old_len { + unsafe { + self.reallocate(len); + self.set_len(len); + for i in old_len..len { + self.set(i, value); + } + } + } else { + self.truncate(len); + } + } + + /// Resize the vector to have capacity for at least `cap` bits. + /// + /// `cap` must be at least as large as the length of the vector. + fn reallocate(&mut self, cap: usize) { + let old_cap = self.capacity(); + if cap <= old_cap { + return; + } + assert!(self.len() <= cap); + + if self.is_heap() { + let old_buffer_len = self.header().buffer_len; + let new_buffer_len = buffer_len(cap); + + let old_alloc_len = header_len() + old_buffer_len; + let new_alloc_len = header_len() + new_buffer_len; + + let old_ptr = self.header_raw() as *mut Storage; + let mut v = unsafe { Vec::from_raw_parts(old_ptr, old_alloc_len, old_alloc_len) }; + v.resize(new_alloc_len, 0); + v.shrink_to_fit(); + self.data = v.as_ptr() as usize | HEAP_FLAG; + forget(v); + + self.header_mut().buffer_len = new_buffer_len; + } else { + let old_self = replace(self, SmallBitVec::with_capacity(cap)); + unsafe { + self.set_len(old_self.len()); + for i in 0..old_self.len() { + self.set_unchecked(i, old_self.get_unchecked(i)); + } + } + } + } + + /// If the vector owns a heap allocation, returns a pointer to the start of the allocation. + /// + /// The layout of the data at this allocation is a private implementation detail. + #[inline] + pub fn heap_ptr(&self) -> Option<*const usize> { + if self.is_heap() { + Some((self.data & !HEAP_FLAG) as *const Storage) + } else { + None + } + } + + /// Converts this `SmallBitVec` into its internal representation. + /// + /// The layout of the data inside both enum variants is a private implementation detail. + #[inline] + pub fn into_storage(self) -> InternalStorage { + if self.is_heap() { + let alloc_len = header_len() + self.header().buffer_len; + let ptr = self.header_raw() as *mut Storage; + let slice = unsafe { Box::from_raw(slice::from_raw_parts_mut(ptr, alloc_len)) }; + forget(self); + InternalStorage::Spilled(slice) + } else { + InternalStorage::Inline(self.data) + } + } + + /// Creates a `SmallBitVec` directly from the internal storage of another + /// `SmallBitVec`. + /// + /// # Safety + /// + /// This is highly unsafe. `storage` needs to have been previously generated + /// via `SmallBitVec::into_storage` (at least, it's highly likely to be + /// incorrect if it wasn't.) Violating this may cause problems like corrupting the + /// allocator's internal data structures. + /// + /// # Examples + /// + /// ``` + /// # use smallbitvec::{InternalStorage, SmallBitVec}; + /// + /// fn main() { + /// let v = SmallBitVec::from_elem(200, false); + /// + /// // Get the internal representation of the SmallBitVec. + /// // unless we transfer its ownership somewhere else. + /// let storage = v.into_storage(); + /// + /// /// Make a copy of the SmallBitVec's data. + /// let cloned_storage = match storage { + /// InternalStorage::Spilled(vs) => InternalStorage::Spilled(vs.clone()), + /// inline => inline, + /// }; + /// + /// /// Create a new SmallBitVec from the coped storage. + /// let v = unsafe { SmallBitVec::from_storage(cloned_storage) }; + /// } + /// ``` + pub unsafe fn from_storage(storage: InternalStorage) -> SmallBitVec { + match storage { + InternalStorage::Inline(data) => SmallBitVec { data }, + InternalStorage::Spilled(vs) => { + let ptr = Box::into_raw(vs); + SmallBitVec { + data: (ptr as *mut usize as usize) | HEAP_FLAG, + } + } + } + } + + /// If the rightmost bit is set, then we treat it as inline storage. + #[inline] + fn is_inline(&self) -> bool { + self.data & HEAP_FLAG == 0 + } + + /// Otherwise, `data` is a pointer to a heap allocation. + #[inline] + fn is_heap(&self) -> bool { + !self.is_inline() + } + + /// Get the header of a heap-allocated vector. + #[inline] + fn header_raw(&self) -> *mut Header { + assert!(self.is_heap()); + (self.data & !HEAP_FLAG) as *mut Header + } + + #[inline] + fn header_mut(&mut self) -> &mut Header { + unsafe { &mut *self.header_raw() } + } + + #[inline] + fn header(&self) -> &Header { + unsafe { &*self.header_raw() } + } + + /// Get the buffer of a heap-allocated vector. + #[inline] + fn buffer_raw(&self) -> *mut [Storage] { + unsafe { + let header_ptr = self.header_raw(); + let buffer_len = (*header_ptr).buffer_len; + let buffer_ptr = (header_ptr as *mut Storage) + .offset((size_of::<Header>() / size_of::<Storage>()) as isize); + slice::from_raw_parts_mut(buffer_ptr, buffer_len) + } + } + + #[inline] + fn buffer_mut(&mut self) -> &mut [Storage] { + unsafe { &mut *self.buffer_raw() } + } + + #[inline] + fn buffer(&self) -> &[Storage] { + unsafe { &*self.buffer_raw() } + } +} + +// Trait implementations: + +impl fmt::Debug for SmallBitVec { + #[inline] + fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + fmt.debug_list() + .entries(self.iter().map(|b| b as u8)) + .finish() + } +} + +impl Default for SmallBitVec { + #[inline] + fn default() -> Self { + Self::new() + } +} + +impl PartialEq for SmallBitVec { + fn eq(&self, other: &Self) -> bool { + // Compare by inline representation + if self.is_inline() && other.is_inline() { + return self.data == other.data; + } + + let len = self.len(); + if len != other.len() { + return false; + } + + // Compare by heap representation + if self.is_heap() && other.is_heap() { + let buf0 = self.buffer(); + let buf1 = other.buffer(); + + let full_blocks = len / bits_per_storage(); + let remainder = len % bits_per_storage(); + + if buf0[..full_blocks] != buf1[..full_blocks] { + return false; + } + + if remainder != 0 { + let mask = (1 << remainder) - 1; + if buf0[full_blocks] & mask != buf1[full_blocks] & mask { + return false; + } + } + return true; + } + + // Representations differ; fall back to bit-by-bit comparison + Iterator::eq(self.iter(), other.iter()) + } +} + +impl Eq for SmallBitVec {} + +impl Drop for SmallBitVec { + fn drop(&mut self) { + if self.is_heap() { + unsafe { + let header_ptr = self.header_raw(); + let alloc_ptr = header_ptr as *mut Storage; + let alloc_len = header_len() + (*header_ptr).buffer_len; + Vec::from_raw_parts(alloc_ptr, alloc_len, alloc_len); + } + } + } +} + +impl Clone for SmallBitVec { + fn clone(&self) -> Self { + if self.is_inline() { + return SmallBitVec { data: self.data }; + } + + let buffer_len = self.header().buffer_len; + let alloc_len = header_len() + buffer_len; + let ptr = self.header_raw() as *mut Storage; + let raw_allocation = unsafe { slice::from_raw_parts(ptr, alloc_len) }; + + let v = raw_allocation.to_vec(); + let header_ptr = v.as_ptr() as *mut Header; + forget(v); + SmallBitVec { + data: (header_ptr as usize) | HEAP_FLAG, + } + } +} + +impl Index<usize> for SmallBitVec { + type Output = bool; + + #[inline(always)] + fn index(&self, i: usize) -> &bool { + assert!(i < self.len(), "index out of range"); + if self.get(i).unwrap() { + &true + } else { + &false + } + } +} + +impl hash::Hash for SmallBitVec { + #[inline] + fn hash<H: hash::Hasher>(&self, state: &mut H) { + let len = self.len(); + len.hash(state); + if self.is_inline() { + reverse_bits(self.data & inline_ones(len)).hash(state); + } else { + let full_blocks = len / bits_per_storage(); + let remainder = len % bits_per_storage(); + let buffer = self.buffer(); + if full_blocks != 0 { + buffer[..full_blocks].hash(state); + } + if remainder != 0 { + let mask = (1 << remainder) - 1; + (buffer[full_blocks] & mask).hash(state); + } + } + } +} + +impl Extend<bool> for SmallBitVec { + #[inline] + fn extend<I: IntoIterator<Item = bool>>(&mut self, iter: I) { + let iter = iter.into_iter(); + + let (min, _) = iter.size_hint(); + assert!(min <= usize::max_value(), "capacity overflow"); + self.reserve(min); + + for element in iter { + self.push(element) + } + } +} + +impl FromIterator<bool> for SmallBitVec { + #[inline] + fn from_iter<I: IntoIterator<Item = bool>>(iter: I) -> Self { + let mut v = SmallBitVec::new(); + v.extend(iter); + v + } +} + +impl IntoIterator for SmallBitVec { + type Item = bool; + type IntoIter = IntoIter; + + #[inline] + fn into_iter(self) -> IntoIter { + IntoIter { + range: 0..self.len(), + vec: self, + } + } +} + +impl<'a> IntoIterator for &'a SmallBitVec { + type Item = bool; + type IntoIter = Iter<'a>; + + #[inline] + fn into_iter(self) -> Iter<'a> { + self.iter() + } +} + +/// An iterator that owns a SmallBitVec and yields its bits as `bool` values. +/// +/// Returned from [`SmallBitVec::into_iter`][1]. +/// +/// [1]: struct.SmallBitVec.html#method.into_iter +pub struct IntoIter { + vec: SmallBitVec, + range: Range<usize>, +} + +impl Iterator for IntoIter { + type Item = bool; + + #[inline] + fn next(&mut self) -> Option<bool> { + self.range + .next() + .map(|i| unsafe { self.vec.get_unchecked(i) }) + } + + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + self.range.size_hint() + } +} + +impl DoubleEndedIterator for IntoIter { + #[inline] + fn next_back(&mut self) -> Option<bool> { + self.range + .next_back() + .map(|i| unsafe { self.vec.get_unchecked(i) }) + } +} + +impl ExactSizeIterator for IntoIter {} + +/// An iterator that borrows a SmallBitVec and yields its bits as `bool` values. +/// +/// Returned from [`SmallBitVec::iter`][1]. +/// +/// [1]: struct.SmallBitVec.html#method.iter +pub struct Iter<'a> { + vec: &'a SmallBitVec, + range: Range<usize>, +} + +impl<'a> Default for Iter<'a> { + #[inline] + fn default() -> Self { + const EMPTY: &'static SmallBitVec = &SmallBitVec::new(); + Self { + vec: EMPTY, + range: 0..0, + } + } +} + +impl<'a> Iterator for Iter<'a> { + type Item = bool; + + #[inline] + fn next(&mut self) -> Option<bool> { + self.range + .next() + .map(|i| unsafe { self.vec.get_unchecked(i) }) + } + + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + self.range.size_hint() + } +} + +impl<'a> DoubleEndedIterator for Iter<'a> { + #[inline] + fn next_back(&mut self) -> Option<bool> { + self.range + .next_back() + .map(|i| unsafe { self.vec.get_unchecked(i) }) + } +} + +impl<'a> ExactSizeIterator for Iter<'a> {} + +/// An immutable view of a range of bits from a borrowed SmallBitVec. +/// +/// Returned from [`SmallBitVec::range`][1]. +/// +/// [1]: struct.SmallBitVec.html#method.range +#[derive(Debug, Clone)] +pub struct VecRange<'a> { + vec: &'a SmallBitVec, + range: Range<usize>, +} + +impl<'a> VecRange<'a> { + #[inline] + pub fn iter(&self) -> Iter<'a> { + Iter { + vec: self.vec, + range: self.range.clone(), + } + } +} + +impl<'a> Index<usize> for VecRange<'a> { + type Output = bool; + + #[inline] + fn index(&self, i: usize) -> &bool { + let vec_i = i + self.range.start; + assert!(vec_i < self.range.end, "index out of range"); + &self.vec[vec_i] + } +} + +fn reverse_bits(mut value: usize) -> usize { + let mut result = 0; + for _ in 0..inline_bits() { + result <<= 1; + result |= value & 1; + value >>= 1; + } + result +} diff --git a/third_party/rust/smallbitvec/src/tests.rs b/third_party/rust/smallbitvec/src/tests.rs new file mode 100644 index 0000000000..a1906c0217 --- /dev/null +++ b/third_party/rust/smallbitvec/src/tests.rs @@ -0,0 +1,397 @@ +// Copyright 2017 Matt Brubeck. See the COPYRIGHT file at the top-level +// directory of this distribution and at http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use super::*; + +use alloc::format; + +#[cfg(target_pointer_width = "32")] +#[test] +fn test_inline_capacity() { + assert_eq!(inline_capacity(), 30); +} + +#[cfg(target_pointer_width = "64")] +#[test] +fn test_inline_capacity() { + assert_eq!(inline_capacity(), 62); +} + +#[test] +fn new() { + let v = SmallBitVec::new(); + assert_eq!(v.len(), 0); + assert_eq!(v.capacity(), inline_capacity()); + assert!(v.is_empty()); + assert!(v.is_inline()); +} + +#[test] +fn with_capacity_inline() { + for cap in 0..(inline_capacity() + 1) { + let v = SmallBitVec::with_capacity(cap); + assert_eq!(v.len(), 0); + assert_eq!(v.capacity(), inline_capacity()); + assert!(v.is_inline()); + } +} + +#[test] +fn with_capacity_heap() { + let cap = inline_capacity() + 1; + let v = SmallBitVec::with_capacity(cap); + assert_eq!(v.len(), 0); + assert!(v.capacity() > inline_capacity()); + assert!(v.is_heap()); +} + +#[test] +fn set_len_inline() { + let mut v = SmallBitVec::new(); + for i in 0..(inline_capacity() + 1) { + unsafe { + v.set_len(i); + } + assert_eq!(v.len(), i); + } + for i in (0..(inline_capacity() + 1)).rev() { + unsafe { + v.set_len(i); + } + assert_eq!(v.len(), i); + } +} + +#[test] +fn set_len_heap() { + let mut v = SmallBitVec::with_capacity(500); + unsafe { + v.set_len(30); + } + assert_eq!(v.len(), 30); +} + +#[test] +fn push_many() { + let mut v = SmallBitVec::new(); + for i in 0..500 { + v.push(i % 3 == 0); + } + assert_eq!(v.len(), 500); + + for i in 0..500 { + assert_eq!(v.get(i).unwrap(), (i % 3 == 0), "{}", i); + assert_eq!(v[i], v.get(i).unwrap()); + } +} + +#[test] +#[should_panic(expected = "index out of range")] +fn index_out_of_bounds() { + let v = SmallBitVec::new(); + v[0]; +} + +#[test] +#[should_panic(expected = "index out of range")] +fn index_out_of_bounds_nonempty() { + let mut v = SmallBitVec::new(); + v.push(true); + v[1 << 32]; +} + +#[test] +fn get_out_of_bounds() { + let v = SmallBitVec::new(); + assert!(v.get(0).is_none()); +} + +#[test] +#[should_panic] +fn set_out_of_bounds() { + let mut v = SmallBitVec::new(); + v.set(2, false); +} + +#[test] +fn all_false() { + let mut v = SmallBitVec::new(); + assert!(v.all_false()); + for _ in 0..100 { + v.push(false); + assert!(v.all_false()); + + let mut v2 = v.clone(); + v2.push(true); + assert!(!v2.all_false()); + } +} + +#[test] +fn all_true() { + let mut v = SmallBitVec::new(); + assert!(v.all_true()); + for _ in 0..100 { + v.push(true); + assert!(v.all_true()); + + let mut v2 = v.clone(); + v2.push(false); + assert!(!v2.all_true()); + } +} + +#[test] +fn iter() { + let mut v = SmallBitVec::new(); + v.push(true); + v.push(false); + v.push(false); + + let mut i = v.iter(); + assert_eq!(i.next(), Some(true)); + assert_eq!(i.next(), Some(false)); + assert_eq!(i.next(), Some(false)); + assert_eq!(i.next(), None); +} + +#[test] +fn into_iter() { + let mut v = SmallBitVec::new(); + v.push(true); + v.push(false); + v.push(false); + + let mut i = v.into_iter(); + assert_eq!(i.next(), Some(true)); + assert_eq!(i.next(), Some(false)); + assert_eq!(i.next(), Some(false)); + assert_eq!(i.next(), None); +} + +#[test] +fn iter_back() { + let mut v = SmallBitVec::new(); + v.push(true); + v.push(false); + v.push(false); + + let mut i = v.iter(); + assert_eq!(i.next_back(), Some(false)); + assert_eq!(i.next_back(), Some(false)); + assert_eq!(i.next_back(), Some(true)); + assert_eq!(i.next(), None); +} + +#[test] +fn range() { + let mut v = SmallBitVec::new(); + v.push(true); + v.push(false); + v.push(false); + v.push(true); + + let r = v.range(0..2); + let mut ri = r.iter(); + assert_eq!(ri.next(), Some(true)); + assert_eq!(ri.next(), Some(false)); + assert_eq!(ri.next(), None); + assert_eq!(r[0], true); +} + +#[test] +#[should_panic(expected = "range out of bounds")] +fn range_oob() { + let mut v = SmallBitVec::new(); + v.push(true); + + v.range(0..2); +} + +#[test] +#[should_panic(expected = "index out of range")] +fn range_index_oob() { + let mut v = SmallBitVec::new(); + v.push(true); + v.push(false); + v.push(true); + + let r = v.range(1..2); + r[1]; +} + +#[test] +fn debug() { + let mut v = SmallBitVec::new(); + v.push(true); + v.push(false); + v.push(false); + + assert_eq!(format!("{:?}", v), "[1, 0, 0]") +} + +#[test] +fn from_elem() { + for len in 0..100 { + let ones = SmallBitVec::from_elem(len, true); + assert_eq!(ones.len(), len); + assert!(ones.all_true()); + + let zeros = SmallBitVec::from_elem(len, false); + assert_eq!(zeros.len(), len); + assert!(zeros.all_false()); + } +} + +#[test] +fn remove() { + let mut v = SmallBitVec::new(); + v.push(false); + v.push(true); + v.push(false); + v.push(false); + v.push(true); + + assert_eq!(v.remove(1), true); + assert_eq!(format!("{:?}", v), "[0, 0, 0, 1]"); + assert_eq!(v.remove(0), false); + assert_eq!(format!("{:?}", v), "[0, 0, 1]"); + v.remove(2); + assert_eq!(format!("{:?}", v), "[0, 0]"); + v.remove(1); + assert_eq!(format!("{:?}", v), "[0]"); + v.remove(0); + assert_eq!(format!("{:?}", v), "[]"); +} + +#[test] +fn remove_big() { + let mut v = SmallBitVec::from_elem(256, false); + v.set(100, true); + v.set(255, true); + v.remove(0); + assert_eq!(v.len(), 255); + assert_eq!(v.get(0).unwrap(), false); + assert_eq!(v.get(99).unwrap(), true); + assert_eq!(v.get(100).unwrap(), false); + assert_eq!(v.get(253).unwrap(), false); + assert_eq!(v.get(254).unwrap(), true); + + v.remove(254); + assert_eq!(v.len(), 254); + assert_eq!(v.get(0).unwrap(), false); + assert_eq!(v.get(99).unwrap(), true); + assert_eq!(v.get(100).unwrap(), false); + assert_eq!(v.get(253).unwrap(), false); + + v.remove(99); + assert_eq!(v, SmallBitVec::from_elem(253, false)); +} + +#[test] +fn eq() { + assert_eq!(sbvec![], sbvec![]); + assert_eq!(sbvec![true], sbvec![true]); + assert_eq!(sbvec![false], sbvec![false]); + + assert_ne!(sbvec![], sbvec![false]); + assert_ne!(sbvec![true], sbvec![]); + assert_ne!(sbvec![true], sbvec![false]); + assert_ne!(sbvec![false], sbvec![true]); + + assert_eq!(sbvec![true, false], sbvec![true, false]); + assert_eq!(sbvec![true; 400], sbvec![true; 400]); + assert_eq!(sbvec![false; 400], sbvec![false; 400]); + + assert_ne!(sbvec![true, false], sbvec![true, true]); + assert_ne!(sbvec![true; 400], sbvec![true; 401]); + assert_ne!(sbvec![false; 401], sbvec![false; 400]); +} + +#[test] +fn truncate_inline() { + let mut v = sbvec![false, true, false, false, true]; + v.truncate(10); + assert_eq!(v.len(), 5); + v.truncate(3); + assert_eq!(v, sbvec![false, true, false]); + v.truncate(0); + assert_eq!(v, sbvec![]); +} + +#[test] +fn truncate_large() { + let mut v = SmallBitVec::from_elem(256, false); + v.set(2, true); + v.set(100, true); + v.set(255, true); + v.truncate(500); + assert_eq!(v.len(), 256); + v.truncate(150); + assert_eq!(v.len(), 150); + assert_eq!(v.get(0).unwrap(), false); + assert_eq!(v.get(99).unwrap(), false); + assert_eq!(v.get(100).unwrap(), true); + assert_eq!(v.get(101).unwrap(), false); + assert_eq!(v.get(149).unwrap(), false); + v.truncate(5); + assert_eq!(v.len(), 5); + assert_eq!(v, sbvec![false, false, true, false, false]); +} + +#[test] +fn resize() { + let mut v = sbvec![false, true, false, false, true]; + v.resize(3, false); + assert_eq!(v, sbvec![false, true, false]); + v.resize(8, true); + assert_eq!(v, sbvec![false, true, false, true, true, true, true, true]); + v.resize(100, false); + assert_eq!(v.len(), 100); + assert_eq!(v.get(0).unwrap(), false); + assert_eq!(v.get(1).unwrap(), true); + assert_eq!(v.get(2).unwrap(), false); + assert_eq!(v.get(3).unwrap(), true); + assert_eq!(v.get(4).unwrap(), true); + assert_eq!(v.get(7).unwrap(), true); + assert_eq!(v.get(8).unwrap(), false); + assert_eq!(v.get(9).unwrap(), false); + assert_eq!(v.get(98).unwrap(), false); + assert_eq!(v.get(99).unwrap(), false); +} + +#[test] +fn hash() { + extern crate std; + use core::hash::{Hash, Hasher}; + + let v1 = sbvec![true, false, true, false, true, true, true]; + let mut v2 = v1.clone(); + v2.reserve(100_000); + assert_eq!(v1, v2); + + let hash = |v: &SmallBitVec| { + let mut hasher = std::collections::hash_map::DefaultHasher::new(); + v.hash(&mut hasher); + hasher.finish() + }; + + assert_eq!(hash(&v1), hash(&v2)); + + let mut v3 = v1.clone(); + v3.push(false); + assert_ne!(hash(&v1), hash(&v3)); + + let mut v4 = v2.clone(); + v4.push(false); + assert_ne!(hash(&v2), hash(&v4)); + + assert_eq!(v3, v4); + assert_eq!(hash(&v3), hash(&v4)); +} |