summaryrefslogtreecommitdiff
path: root/vendor/fixedbitset
diff options
context:
space:
mode:
authormo khan <mo@mokhan.ca>2025-07-15 16:37:08 -0600
committermo khan <mo@mokhan.ca>2025-07-17 16:30:22 -0600
commit45df4d0d9b577fecee798d672695fe24ff57fb1b (patch)
tree1b99bf645035b58e0d6db08c7a83521f41f7a75b /vendor/fixedbitset
parentf94f79608393d4ab127db63cc41668445ef6b243 (diff)
feat: migrate from Cedar to SpiceDB authorization system
This is a major architectural change that replaces the Cedar policy-based authorization system with SpiceDB's relation-based authorization. Key changes: - Migrate from Rust to Go implementation - Replace Cedar policies with SpiceDB schema and relationships - Switch from envoy `ext_authz` with Cedar to SpiceDB permission checks - Update build system and dependencies for Go ecosystem - Maintain Envoy integration for external authorization This change enables more flexible permission modeling through SpiceDB's Google Zanzibar inspired relation-based system, supporting complex hierarchical permissions that were difficult to express in Cedar. Breaking change: Existing Cedar policies and Rust-based configuration will no longer work and need to be migrated to SpiceDB schema.
Diffstat (limited to 'vendor/fixedbitset')
-rw-r--r--vendor/fixedbitset/.cargo-checksum.json1
-rw-r--r--vendor/fixedbitset/Cargo.toml45
-rw-r--r--vendor/fixedbitset/LICENSE-APACHE201
-rw-r--r--vendor/fixedbitset/LICENSE-MIT25
-rw-r--r--vendor/fixedbitset/README.md125
-rw-r--r--vendor/fixedbitset/src/block/avx.rs92
-rw-r--r--vendor/fixedbitset/src/block/avx2.rs88
-rw-r--r--vendor/fixedbitset/src/block/default.rs70
-rw-r--r--vendor/fixedbitset/src/block/mod.rs114
-rw-r--r--vendor/fixedbitset/src/block/sse2.rs104
-rw-r--r--vendor/fixedbitset/src/block/wasm.rs80
-rw-r--r--vendor/fixedbitset/src/lib.rs1711
-rw-r--r--vendor/fixedbitset/src/range.rs45
-rw-r--r--vendor/fixedbitset/src/serde_impl.rs150
-rw-r--r--vendor/fixedbitset/tests/tests.rs1313
15 files changed, 0 insertions, 4164 deletions
diff --git a/vendor/fixedbitset/.cargo-checksum.json b/vendor/fixedbitset/.cargo-checksum.json
deleted file mode 100644
index ad86ebcb..00000000
--- a/vendor/fixedbitset/.cargo-checksum.json
+++ /dev/null
@@ -1 +0,0 @@
-{"files":{"Cargo.toml":"8d265c4f6d6f71a27e1671cc712dbe77274dae1431f455b99b347b8650c1ece0","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"ce592787ff2321feab698a4c612237f4378cc658ebb1d472913e5802cc47afb4","README.md":"6fd4e5b612e6e23c354afb49340542f150dccef380461581a4a24490bced73dd","src/block/avx.rs":"ebdfa85c3692f164d8934bc2ec38924730cfb8cee2f98cfe565376d35969fbd7","src/block/avx2.rs":"c6a0aae98abb06c8a2eadecd64ce012a4b11c03e1b406fa78e667d4ab1b8d4ae","src/block/default.rs":"f86de8ab1097ed4daa71cee927b1742bd6c4bfb7b7a568a8458055e1077522bf","src/block/mod.rs":"a3987ac6bd5116e0d2d8bb3ebdd79a860802ca4bc077166d60b0911fd979b334","src/block/sse2.rs":"c3d59f76daf0d0a37730340fdbaf1866221e55ab2efea3e1fe156cfcbc3cc560","src/block/wasm.rs":"83f7807f8c5f74881eb1956e37bec6fd1b03c7311355aa960618f9868d670062","src/lib.rs":"58c749d9ed8e27c3750db1490e01c59bf524c5a098415e95b75652d0373a5903","src/range.rs":"28b53952f40b3e6bf83efc1e427c671c94d6ce4b3a76b6c5d1f766e965f71911","src/serde_impl.rs":"0741352978b722c44d33a0cdd3e987055c296aa55f9ac3448edec4951a472937","tests/tests.rs":"6026b6a46ad2c8fb4057557fb0f7128a22577fb21d01b5ac357d0c026068400b"},"package":"1d674e81391d1e1ab681a28d99df07927c6d4aa5b027d7da16ba32d1d21ecd99"} \ No newline at end of file
diff --git a/vendor/fixedbitset/Cargo.toml b/vendor/fixedbitset/Cargo.toml
deleted file mode 100644
index e5268803..00000000
--- a/vendor/fixedbitset/Cargo.toml
+++ /dev/null
@@ -1,45 +0,0 @@
-# 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 are reading this file be aware that the original Cargo.toml
-# will likely look very different (and much more reasonable).
-# See Cargo.toml.orig for the original contents.
-
-[package]
-edition = "2021"
-rust-version = "1.56"
-name = "fixedbitset"
-version = "0.5.7"
-authors = ["bluss"]
-description = "FixedBitSet is a simple bitset collection"
-documentation = "https://docs.rs/fixedbitset/"
-readme = "README.md"
-keywords = [
- "container",
- "data-structure",
- "bitvec",
- "bitset",
- "no_std",
-]
-categories = ["data-structures"]
-license = "MIT OR Apache-2.0"
-repository = "https://github.com/petgraph/fixedbitset"
-
-[package.metadata.release]
-no-dev-version = true
-tag-name = "{{version}}"
-
-[dependencies.serde]
-version = "1.0"
-optional = true
-
-[dev-dependencies.serde_json]
-version = "1.0"
-
-[features]
-default = ["std"]
-std = []
diff --git a/vendor/fixedbitset/LICENSE-APACHE b/vendor/fixedbitset/LICENSE-APACHE
deleted file mode 100644
index 16fe87b0..00000000
--- a/vendor/fixedbitset/LICENSE-APACHE
+++ /dev/null
@@ -1,201 +0,0 @@
- 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/vendor/fixedbitset/LICENSE-MIT b/vendor/fixedbitset/LICENSE-MIT
deleted file mode 100644
index 327cc617..00000000
--- a/vendor/fixedbitset/LICENSE-MIT
+++ /dev/null
@@ -1,25 +0,0 @@
-Copyright (c) 2015-2017
-
-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/vendor/fixedbitset/README.md b/vendor/fixedbitset/README.md
deleted file mode 100644
index 929ee32e..00000000
--- a/vendor/fixedbitset/README.md
+++ /dev/null
@@ -1,125 +0,0 @@
-fixedbitset
----
-
-A simple fixed size bitset container for Rust.
-
-Please read the [API documentation here](https://docs.rs/fixedbitset/)
-
-[![build\_status](https://github.com/petgraph/fixedbitset/workflows/Continuous%20integration/badge.svg?branch=master)](https://github.com/petgraph/fixedbitset/actions)
-[![crates](https://img.shields.io/crates/v/fixedbitset.svg)](https://crates.io/crates/fixedbitset)
-
-# Recent Changes
-
-- 0.5.7
- - [#127](https://github.com/petgraph/fixedbitset/pull/127) and [#128](https://github.com/petgraph/fixedbitset/pull/128): Optimize `Clone::clone_from` to avoid
- extra allocations and copies.
-- 0.5.6
- - Fixed FixedBitset not implementing Send/Sync due to the stack size shrink.
-- 0.5.5 (yanked)
- - [#116](https://github.com/petgraph/fixedbitset/pull/116): Add functions for counting the results of a set operation (`union_count`,
- `intersection_count`, `difference_count`, `symmetric_difference_count`) by @james7132.
- - [#118](https://github.com/petgraph/fixedbitset/pull/118): Shrink the stack size of FixedBitset. There should be zero stack size overhead
- compared to a Vec.
- - [#119](https://github.com/petgraph/fixedbitset/pull/119): Fix builds for wasm32.
- - [#120](https://github.com/petgraph/fixedbitset/pull/119): Add more utility functions that were previously missing from the public interface:
- `contains_any_in_range`, `contains_all_in_range`, `minimum`, `maximum`, `is_full`, `count_zeroes`, and `remove_range`.
- - [#121](https://github.com/petgraph/fixedbitset/pull/121): Add support for SIMD acceleration for AVX builds.
-- 0.5.4
- - [#112](https://github.com/petgraph/fixedbitset/pull/112): Fix undefined behavior in IntoOnes and setup testing with MIRI by @SkiFire13
-- 0.5.3 (yanked)
- - [#109](https://github.com/petgraph/fixedbitset/pull/109): Fix non-x86(_64) builds by @james7132
-- 0.5.2 (yanked)
- - [#86](https://github.com/petgraph/fixedbitset/pull/86): Explicit SIMD vectorization for set operations by @james7132.
-- 0.5.1
- - [#102](https://github.com/petgraph/fixedbitset/pull/102): Added `contains_unchecked`, `insert_unchecked`, `put_unchecked`,
- `set_unchecked`, `toggle_unchecked`, `removed_unchecked`, `copy_bit_unchecked` unsafe variants of the safe functions, by @james7132
- - [#103](https://github.com/petgraph/fixedbitset/pull/103): Added `into_ones` which returns a owned iterator over the one
- values from a bitset, by @james7132.
- - [#104](https://github.com/petgraph/fixedbitset/pull/104): Implemented `DoubleEndedIterator` for `Union`, `Intersection`,
- `Difference`, and `SymmetricDifference` , by @james7132.
-- 0.5.0
- - [#74](https://github.com/petgraph/fixedbitset/pull/74): Accelerated set operations (union, intersection, difference,
- symmetric difference) by using larger blocks internally, by @james7132.
- - [#88](https://github.com/petgraph/fixedbitset/pull/88): Added `FixedBitSet::remove` by @james7132.
- - [#89](https://github.com/petgraph/fixedbitset/pull/89): Added `FixedBitSet::zeros` and the `Zeros` iterator by @james7132.
- - [#92](https://github.com/petgraph/fixedbitset/pull/92): Added `FixedBitSet::grow_and_insert` function, a
- non-panicking version of `insert` that grows the underlying storage as need, by @shuoli84.
- - [#98](https://github.com/petgraph/fixedbitset/pull/98): `Ones` now implements `DoubleEndedIterator`, by @tikhu.
- - [#99](https://github.com/petgraph/fixedbitset/pull/99): **Breaking change**: serde now serializes and deserializes from a little-endian encoded
- raw byte buffer. Existing stored instances of the serialized bitsets will need to be
- re-encoded.
- - Bumped MSRV to 1.56.
-- 0.4.2
- - [#79](https://github.com/petgraph/fixedbitset/pull/79): Add `is_clear`,
- clarify `is_empty` and `len` documentation by \@nicopap.
-- 0.4.1
- - Documentation and formatting fixes.
-- 0.4.0
- - [#61](https://github.com/petgraph/fixedbitset/pull/61): Require
- Rust 1.39.
- - [#60](https://github.com/petgraph/fixedbitset/pull/60): Add
- `const` `FixedBitSet::new` consructor
- by \@jakobhellermann.
- - [#59](https://github.com/petgraph/fixedbitset/pull/59): Add
- optional `serde` support by \@keshavsn.
-- 0.3.2
- - [#18](https://github.com/petgraph/fixedbitset/pull/18): Optimize
- `ones` using `trailing_zeroes` by \@vks
-- 0.3.1
- - Add bit assign operators for references by \@flaghacker
- - Improve assertion error messages by \@lovasoa
- - Add documentation examples for `with_capacity_and_blocks`
-- 0.3.0
- - Add `with_capacity_and_blocks` by \@luizirber
- - Add `difference_with` by \@sunshowers
- - Implement `Binary` and `Display` traits by \@Dolphindalt
- - Add `toggle_range` by \@wirelyre
-- 0.2.0
- - Add assign operators for the bit operations by \@jrraymond
- - Add `symmetric_difference`, `union_with`, `intersection_with` by
- \@jrraymond
- - Add `is_subset`, `is_superset`, `is_disjoint` by \@nwn
- - Add `.toggle(i)` method by \@ShiroUsagi-san
- - Add default feature \"std\" which can be disabled to make the
- crate not link the std library. By \@jonimake and \@bluss
- - Require Rust 1.31.
-- 0.1.9
- - Add intersection, union, difference iterators by \@jrraymond
- - Add intersection: `&` and union: `|` operator implementations by
- \@jrraymond
- - Add Extend and FromIterator implementations (from sequences of
- bit indices) by \@jrraymond
-- 0.1.8
- - Add missing `#[inline]` on the ones iterator
- - Fix docs for `insert_range, set_range`
-- 0.1.7
- - Add fast methods `.insert_range`, `.set_range` by \@kennytm
-- 0.1.6
- - Add iterator `.ones()` by \@mneumann
- - Fix bug with `.count_ones()` where it would erronously have an
- out-of-bounds panic for even block endpoints
-- 0.1.5
- - Add method `.count_ones(range)`.
-- 0.1.4
- - Remove an assertion in `.copy_bit(from, to)` so that it is in
- line with the documentation. The `from` bit does not need to be
- in bounds.
- - Improve `.grow()` to use `Vec::resize` internally.
-- 0.1.3
- - Add method `.put()` to enable a bit and return previous value
-- 0.1.2
- - Add method `.copy_bit()` (by fuine)
- - impl Default
-- 0.1.1
- - Update documentation URL
-- 0.1.0
- - Add method `.grow()`
-
-# License
-
-Dual-licensed to be compatible with the Rust project.
-
-Licensed under the [Apache License, Version 2.0](https://www.apache.org/licenses/LICENSE-2.0)
- or the [MIT license](https://opensource.org/licenses/MIT),
- at your option. This file may not be copied, modified, or distributed except
-according to those terms.
diff --git a/vendor/fixedbitset/src/block/avx.rs b/vendor/fixedbitset/src/block/avx.rs
deleted file mode 100644
index 33ba100f..00000000
--- a/vendor/fixedbitset/src/block/avx.rs
+++ /dev/null
@@ -1,92 +0,0 @@
-#[cfg(target_arch = "x86")]
-use core::arch::x86::*;
-#[cfg(target_arch = "x86_64")]
-use core::arch::x86_64::*;
-use core::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Not};
-
-#[derive(Copy, Clone, Debug)]
-#[repr(transparent)]
-pub struct Block(pub(super) __m256d);
-
-impl Block {
- #[inline]
- pub fn is_empty(self) -> bool {
- unsafe {
- let value = _mm256_castpd_si256(self.0);
- _mm256_testz_si256(value, value) == 1
- }
- }
-
- #[inline]
- pub fn andnot(self, other: Self) -> Self {
- unsafe { Self(_mm256_andnot_pd(other.0, self.0)) }
- }
-}
-
-impl Not for Block {
- type Output = Block;
- #[inline]
- fn not(self) -> Self::Output {
- unsafe { Self(_mm256_xor_pd(self.0, Self::ALL.0)) }
- }
-}
-
-impl BitAnd for Block {
- type Output = Block;
- #[inline]
- fn bitand(self, other: Self) -> Self::Output {
- unsafe { Self(_mm256_and_pd(self.0, other.0)) }
- }
-}
-
-impl BitAndAssign for Block {
- #[inline]
- fn bitand_assign(&mut self, other: Self) {
- unsafe {
- self.0 = _mm256_and_pd(self.0, other.0);
- }
- }
-}
-
-impl BitOr for Block {
- type Output = Block;
- #[inline]
- fn bitor(self, other: Self) -> Self::Output {
- unsafe { Self(_mm256_or_pd(self.0, other.0)) }
- }
-}
-
-impl BitOrAssign for Block {
- #[inline]
- fn bitor_assign(&mut self, other: Self) {
- unsafe {
- self.0 = _mm256_or_pd(self.0, other.0);
- }
- }
-}
-
-impl BitXor for Block {
- type Output = Block;
- #[inline]
- fn bitxor(self, other: Self) -> Self::Output {
- unsafe { Self(_mm256_xor_pd(self.0, other.0)) }
- }
-}
-
-impl BitXorAssign for Block {
- #[inline]
- fn bitxor_assign(&mut self, other: Self) {
- unsafe { self.0 = _mm256_xor_pd(self.0, other.0) }
- }
-}
-
-impl PartialEq for Block {
- #[inline]
- fn eq(&self, other: &Self) -> bool {
- unsafe {
- let new = _mm256_xor_pd(self.0, other.0);
- let neq = _mm256_castpd_si256(new);
- _mm256_testz_si256(neq, neq) == 1
- }
- }
-}
diff --git a/vendor/fixedbitset/src/block/avx2.rs b/vendor/fixedbitset/src/block/avx2.rs
deleted file mode 100644
index b3593773..00000000
--- a/vendor/fixedbitset/src/block/avx2.rs
+++ /dev/null
@@ -1,88 +0,0 @@
-#[cfg(target_arch = "x86")]
-use core::arch::x86::*;
-#[cfg(target_arch = "x86_64")]
-use core::arch::x86_64::*;
-use core::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Not};
-
-#[derive(Copy, Clone, Debug)]
-#[repr(transparent)]
-pub struct Block(pub(super) __m256i);
-
-impl Block {
- #[inline]
- pub fn is_empty(self) -> bool {
- unsafe { _mm256_testz_si256(self.0, self.0) == 1 }
- }
-
- #[inline]
- pub fn andnot(self, other: Self) -> Self {
- Self(unsafe { _mm256_andnot_si256(other.0, self.0) })
- }
-}
-
-impl Not for Block {
- type Output = Block;
- #[inline]
- fn not(self) -> Self::Output {
- unsafe { Self(_mm256_xor_si256(self.0, Self::ALL.0)) }
- }
-}
-
-impl BitAnd for Block {
- type Output = Block;
- #[inline]
- fn bitand(self, other: Self) -> Self::Output {
- unsafe { Self(_mm256_and_si256(self.0, other.0)) }
- }
-}
-
-impl BitAndAssign for Block {
- #[inline]
- fn bitand_assign(&mut self, other: Self) {
- unsafe {
- self.0 = _mm256_and_si256(self.0, other.0);
- }
- }
-}
-
-impl BitOr for Block {
- type Output = Block;
- #[inline]
- fn bitor(self, other: Self) -> Self::Output {
- unsafe { Self(_mm256_or_si256(self.0, other.0)) }
- }
-}
-
-impl BitOrAssign for Block {
- #[inline]
- fn bitor_assign(&mut self, other: Self) {
- unsafe {
- self.0 = _mm256_or_si256(self.0, other.0);
- }
- }
-}
-
-impl BitXor for Block {
- type Output = Block;
- #[inline]
- fn bitxor(self, other: Self) -> Self::Output {
- unsafe { Self(_mm256_xor_si256(self.0, other.0)) }
- }
-}
-
-impl BitXorAssign for Block {
- #[inline]
- fn bitxor_assign(&mut self, other: Self) {
- unsafe { self.0 = _mm256_xor_si256(self.0, other.0) }
- }
-}
-
-impl PartialEq for Block {
- #[inline]
- fn eq(&self, other: &Self) -> bool {
- unsafe {
- let neq = _mm256_xor_si256(self.0, other.0);
- _mm256_testz_si256(neq, neq) == 1
- }
- }
-}
diff --git a/vendor/fixedbitset/src/block/default.rs b/vendor/fixedbitset/src/block/default.rs
deleted file mode 100644
index 7fc460fb..00000000
--- a/vendor/fixedbitset/src/block/default.rs
+++ /dev/null
@@ -1,70 +0,0 @@
-use core::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Not};
-
-#[derive(Copy, Clone, PartialEq, Debug)]
-#[repr(transparent)]
-pub struct Block(pub(super) usize);
-
-impl Block {
- #[inline]
- pub const fn is_empty(self) -> bool {
- self.0 == Self::NONE.0
- }
-
- #[inline]
- pub fn andnot(self, other: Self) -> Self {
- Self(!other.0 & self.0)
- }
-}
-
-impl Not for Block {
- type Output = Block;
- #[inline]
- fn not(self) -> Self::Output {
- Self(self.0.not())
- }
-}
-
-impl BitAnd for Block {
- type Output = Block;
- #[inline]
- fn bitand(self, other: Self) -> Self::Output {
- Self(self.0.bitand(other.0))
- }
-}
-
-impl BitAndAssign for Block {
- #[inline]
- fn bitand_assign(&mut self, other: Self) {
- self.0.bitand_assign(other.0);
- }
-}
-
-impl BitOr for Block {
- type Output = Block;
- #[inline]
- fn bitor(self, other: Self) -> Self::Output {
- Self(self.0.bitor(other.0))
- }
-}
-
-impl BitOrAssign for Block {
- #[inline]
- fn bitor_assign(&mut self, other: Self) {
- self.0.bitor_assign(other.0)
- }
-}
-
-impl BitXor for Block {
- type Output = Block;
- #[inline]
- fn bitxor(self, other: Self) -> Self::Output {
- Self(self.0.bitxor(other.0))
- }
-}
-
-impl BitXorAssign for Block {
- #[inline]
- fn bitxor_assign(&mut self, other: Self) {
- self.0.bitxor_assign(other.0)
- }
-}
diff --git a/vendor/fixedbitset/src/block/mod.rs b/vendor/fixedbitset/src/block/mod.rs
deleted file mode 100644
index ae7c2220..00000000
--- a/vendor/fixedbitset/src/block/mod.rs
+++ /dev/null
@@ -1,114 +0,0 @@
-#![allow(clippy::undocumented_unsafe_blocks)]
-#![allow(dead_code)]
-// TODO: Remove once the transmutes are fixed
-#![allow(unknown_lints)]
-#![allow(clippy::missing_transmute_annotations)]
-
-use core::cmp::Ordering;
-use core::hash::{Hash, Hasher};
-
-#[cfg(all(
- not(all(target_family = "wasm", target_feature = "simd128")),
- not(target_feature = "sse2"),
- not(target_feature = "avx"),
- not(target_feature = "avx2"),
-))]
-mod default;
-#[cfg(all(
- not(all(target_family = "wasm", target_feature = "simd128")),
- not(target_feature = "sse2"),
- not(target_feature = "avx"),
- not(target_feature = "avx2"),
-))]
-pub use self::default::*;
-
-#[cfg(all(
- any(target_arch = "x86", target_arch = "x86_64"),
- target_feature = "sse2",
- not(target_feature = "avx"),
- not(target_feature = "avx2"),
-))]
-mod sse2;
-#[cfg(all(
- any(target_arch = "x86", target_arch = "x86_64"),
- target_feature = "sse2",
- not(target_feature = "avx"),
- not(target_feature = "avx2"),
-))]
-pub use self::sse2::*;
-
-#[cfg(all(
- any(target_arch = "x86", target_arch = "x86_64"),
- target_feature = "avx",
- not(target_feature = "avx2")
-))]
-mod avx;
-#[cfg(all(
- any(target_arch = "x86", target_arch = "x86_64"),
- target_feature = "avx",
- not(target_feature = "avx2")
-))]
-pub use self::avx::*;
-
-#[cfg(all(
- any(target_arch = "x86", target_arch = "x86_64"),
- target_feature = "avx2"
-))]
-mod avx2;
-#[cfg(all(
- any(target_arch = "x86", target_arch = "x86_64"),
- target_feature = "avx2"
-))]
-pub use self::avx2::*;
-
-#[cfg(all(target_family = "wasm", target_feature = "simd128"))]
-mod wasm;
-#[cfg(all(target_family = "wasm", target_feature = "simd128"))]
-pub use self::wasm::*;
-
-impl Block {
- pub const USIZE_COUNT: usize = core::mem::size_of::<Self>() / core::mem::size_of::<usize>();
- pub const NONE: Self = Self::from_usize_array([0; Self::USIZE_COUNT]);
- pub const ALL: Self = Self::from_usize_array([usize::MAX; Self::USIZE_COUNT]);
- pub const BITS: usize = core::mem::size_of::<Self>() * 8;
-
- #[inline]
- pub fn into_usize_array(self) -> [usize; Self::USIZE_COUNT] {
- unsafe { core::mem::transmute(self.0) }
- }
-
- #[inline]
- pub const fn from_usize_array(array: [usize; Self::USIZE_COUNT]) -> Self {
- Self(unsafe { core::mem::transmute(array) })
- }
-}
-
-impl Eq for Block {}
-
-impl PartialOrd for Block {
- #[inline]
- fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
- Some(self.cmp(other))
- }
-}
-
-impl Ord for Block {
- #[inline]
- fn cmp(&self, other: &Self) -> Ordering {
- self.into_usize_array().cmp(&other.into_usize_array())
- }
-}
-
-impl Default for Block {
- #[inline]
- fn default() -> Self {
- Self::NONE
- }
-}
-
-impl Hash for Block {
- #[inline]
- fn hash<H: Hasher>(&self, hasher: &mut H) {
- Hash::hash_slice(&self.into_usize_array(), hasher);
- }
-}
diff --git a/vendor/fixedbitset/src/block/sse2.rs b/vendor/fixedbitset/src/block/sse2.rs
deleted file mode 100644
index 6db08f7e..00000000
--- a/vendor/fixedbitset/src/block/sse2.rs
+++ /dev/null
@@ -1,104 +0,0 @@
-#![allow(clippy::undocumented_unsafe_blocks)]
-
-#[cfg(target_arch = "x86")]
-use core::arch::x86::*;
-#[cfg(target_arch = "x86_64")]
-use core::arch::x86_64::*;
-use core::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Not};
-
-#[derive(Copy, Clone, Debug)]
-#[repr(transparent)]
-pub struct Block(pub(super) __m128i);
-
-impl Block {
- #[inline]
- pub fn is_empty(self) -> bool {
- #[cfg(not(target_feature = "sse4.1"))]
- {
- self == Self::NONE
- }
- #[cfg(target_feature = "sse4.1")]
- {
- unsafe { _mm_test_all_zeros(self.0, self.0) == 1 }
- }
- }
-
- #[inline]
- pub fn andnot(self, other: Self) -> Self {
- Self(unsafe { _mm_andnot_si128(other.0, self.0) })
- }
-}
-
-impl Not for Block {
- type Output = Block;
- #[inline]
- fn not(self) -> Self::Output {
- unsafe { Self(_mm_xor_si128(self.0, Self::ALL.0)) }
- }
-}
-
-impl BitAnd for Block {
- type Output = Block;
- #[inline]
- fn bitand(self, other: Self) -> Self::Output {
- unsafe { Self(_mm_and_si128(self.0, other.0)) }
- }
-}
-
-impl BitAndAssign for Block {
- #[inline]
- fn bitand_assign(&mut self, other: Self) {
- unsafe {
- self.0 = _mm_and_si128(self.0, other.0);
- }
- }
-}
-
-impl BitOr for Block {
- type Output = Block;
- #[inline]
- fn bitor(self, other: Self) -> Self::Output {
- unsafe { Self(_mm_or_si128(self.0, other.0)) }
- }
-}
-
-impl BitOrAssign for Block {
- #[inline]
- fn bitor_assign(&mut self, other: Self) {
- unsafe {
- self.0 = _mm_or_si128(self.0, other.0);
- }
- }
-}
-
-impl BitXor for Block {
- type Output = Block;
- #[inline]
- fn bitxor(self, other: Self) -> Self::Output {
- unsafe { Self(_mm_xor_si128(self.0, other.0)) }
- }
-}
-
-impl BitXorAssign for Block {
- #[inline]
- fn bitxor_assign(&mut self, other: Self) {
- unsafe { self.0 = _mm_xor_si128(self.0, other.0) }
- }
-}
-
-impl PartialEq for Block {
- #[inline]
- fn eq(&self, other: &Self) -> bool {
- unsafe {
- #[cfg(not(target_feature = "sse4.1"))]
- {
- _mm_movemask_epi8(_mm_cmpeq_epi8(self.0, other.0)) == 0xffff
- }
- #[cfg(target_feature = "sse4.1")]
- {
- let neq = _mm_xor_si128(self.0, other.0);
- _mm_test_all_zeros(neq, neq) == 1
- }
- }
- }
-}
diff --git a/vendor/fixedbitset/src/block/wasm.rs b/vendor/fixedbitset/src/block/wasm.rs
deleted file mode 100644
index f823d86a..00000000
--- a/vendor/fixedbitset/src/block/wasm.rs
+++ /dev/null
@@ -1,80 +0,0 @@
-use core::{
- arch::wasm32::*,
- ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Not},
-};
-
-#[derive(Copy, Clone, Debug)]
-#[repr(transparent)]
-pub struct Block(pub(super) v128);
-
-impl Block {
- #[inline]
- pub fn is_empty(self) -> bool {
- !v128_any_true(self.0)
- }
-
- #[inline]
- pub fn andnot(self, other: Self) -> Self {
- Self(v128_andnot(self.0, other.0))
- }
-}
-
-impl Not for Block {
- type Output = Block;
- #[inline]
- fn not(self) -> Self::Output {
- Self(v128_xor(self.0, Self::ALL.0))
- }
-}
-
-impl BitAnd for Block {
- type Output = Block;
- #[inline]
- fn bitand(self, other: Self) -> Self::Output {
- Self(v128_and(self.0, other.0))
- }
-}
-
-impl BitAndAssign for Block {
- #[inline]
- fn bitand_assign(&mut self, other: Self) {
- self.0 = v128_and(self.0, other.0);
- }
-}
-
-impl BitOr for Block {
- type Output = Block;
- #[inline]
- fn bitor(self, other: Self) -> Self::Output {
- Self(v128_or(self.0, other.0))
- }
-}
-
-impl BitOrAssign for Block {
- #[inline]
- fn bitor_assign(&mut self, other: Self) {
- self.0 = v128_or(self.0, other.0);
- }
-}
-
-impl BitXor for Block {
- type Output = Block;
- #[inline]
- fn bitxor(self, other: Self) -> Self::Output {
- Self(v128_xor(self.0, other.0))
- }
-}
-
-impl BitXorAssign for Block {
- #[inline]
- fn bitxor_assign(&mut self, other: Self) {
- self.0 = v128_xor(self.0, other.0)
- }
-}
-
-impl PartialEq for Block {
- #[inline]
- fn eq(&self, other: &Self) -> bool {
- !v128_any_true(v128_xor(self.0, other.0))
- }
-}
diff --git a/vendor/fixedbitset/src/lib.rs b/vendor/fixedbitset/src/lib.rs
deleted file mode 100644
index f9d12f41..00000000
--- a/vendor/fixedbitset/src/lib.rs
+++ /dev/null
@@ -1,1711 +0,0 @@
-//! `FixedBitSet` is a simple fixed size set of bits.
-//!
-//! ### Crate features
-//!
-//! - `std` (default feature)
-//! Disabling this feature disables using std and instead uses crate alloc.
-//!
-//! ### SIMD Acceleration
-//! `fixedbitset` is written with SIMD in mind. The backing store and set operations will use aligned SIMD data types and instructions when compiling
-//! for compatible target platforms. The use of SIMD generally enables better performance in many set and batch operations (i.e. intersection/union/inserting a range).
-//!
-//! When SIMD is not available on the target, the crate will gracefully fallback to a default implementation. It is intended to add support for other SIMD architectures
-//! once they appear in stable Rust.
-//!
-//! Currently only SSE2/AVX/AVX2 on x86/x86_64 and wasm32 SIMD are supported as this is what stable Rust supports.
-#![no_std]
-#![deny(clippy::undocumented_unsafe_blocks)]
-
-extern crate alloc;
-use alloc::{vec, vec::Vec};
-
-mod block;
-mod range;
-
-#[cfg(feature = "serde")]
-extern crate serde;
-#[cfg(feature = "serde")]
-mod serde_impl;
-
-use core::fmt::Write;
-use core::fmt::{Binary, Display, Error, Formatter};
-
-use core::cmp::Ordering;
-use core::hash::Hash;
-use core::iter::{Chain, FusedIterator};
-use core::mem::ManuallyDrop;
-use core::mem::MaybeUninit;
-use core::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Index};
-use core::ptr::NonNull;
-pub use range::IndexRange;
-
-pub(crate) const BITS: usize = core::mem::size_of::<Block>() * 8;
-#[cfg(feature = "serde")]
-pub(crate) const BYTES: usize = core::mem::size_of::<Block>();
-
-use block::Block as SimdBlock;
-pub type Block = usize;
-
-#[inline]
-fn div_rem(x: usize, denominator: usize) -> (usize, usize) {
- (x / denominator, x % denominator)
-}
-
-fn vec_into_parts<T>(vec: Vec<T>) -> (NonNull<T>, usize, usize) {
- let mut vec = ManuallyDrop::new(vec);
- (
- // SAFETY: A Vec's internal pointer is always non-null.
- unsafe { NonNull::new_unchecked(vec.as_mut_ptr()) },
- vec.capacity(),
- vec.len(),
- )
-}
-
-/// `FixedBitSet` is a simple fixed size set of bits that each can
-/// be enabled (1 / **true**) or disabled (0 / **false**).
-///
-/// The bit set has a fixed capacity in terms of enabling bits (and the
-/// capacity can grow using the `grow` method).
-///
-/// Derived traits depend on both the zeros and ones, so [0,1] is not equal to
-/// [0,1,0].
-#[derive(Debug, Eq)]
-pub struct FixedBitSet {
- pub(crate) data: NonNull<MaybeUninit<SimdBlock>>,
- capacity: usize,
- /// length in bits
- pub(crate) length: usize,
-}
-
-// SAFETY: FixedBitset contains no thread-local state and can be safely sent between threads
-unsafe impl Send for FixedBitSet {}
-// SAFETY: FixedBitset does not provide simultaneous unsynchronized mutable access to the
-// underlying buffer.
-unsafe impl Sync for FixedBitSet {}
-
-impl FixedBitSet {
- /// Create a new empty **FixedBitSet**.
- pub const fn new() -> Self {
- FixedBitSet {
- data: NonNull::dangling(),
- capacity: 0,
- length: 0,
- }
- }
-
- /// Create a new **FixedBitSet** with a specific number of bits,
- /// all initially clear.
- pub fn with_capacity(bits: usize) -> Self {
- let (mut blocks, rem) = div_rem(bits, SimdBlock::BITS);
- blocks += (rem > 0) as usize;
- Self::from_blocks_and_len(vec![SimdBlock::NONE; blocks], bits)
- }
-
- #[inline]
- fn from_blocks_and_len(data: Vec<SimdBlock>, length: usize) -> Self {
- let (data, capacity, _) = vec_into_parts(data);
- FixedBitSet {
- data: data.cast(),
- capacity,
- length,
- }
- }
-
- /// Create a new **FixedBitSet** with a specific number of bits,
- /// initialized from provided blocks.
- ///
- /// If the blocks are not the exact size needed for the capacity
- /// they will be padded with zeros (if shorter) or truncated to
- /// the capacity (if longer).
- ///
- /// For example:
- /// ```
- /// let data = vec![4];
- /// let bs = fixedbitset::FixedBitSet::with_capacity_and_blocks(4, data);
- /// assert_eq!(format!("{:b}", bs), "0010");
- /// ```
- pub fn with_capacity_and_blocks<I: IntoIterator<Item = Block>>(bits: usize, blocks: I) -> Self {
- let mut bitset = Self::with_capacity(bits);
- for (subblock, value) in bitset.as_mut_slice().iter_mut().zip(blocks.into_iter()) {
- *subblock = value;
- }
- bitset
- }
-
- /// Grow capacity to **bits**, all new bits initialized to zero
- #[inline]
- pub fn grow(&mut self, bits: usize) {
- #[cold]
- #[track_caller]
- #[inline(never)]
- fn do_grow(slf: &mut FixedBitSet, bits: usize) {
- // SAFETY: The provided fill is initialized to NONE.
- unsafe { slf.grow_inner(bits, MaybeUninit::new(SimdBlock::NONE)) };
- }
-
- if bits > self.length {
- do_grow(self, bits);
- }
- }
-
- /// # Safety
- /// If `fill` is uninitialized, the memory must not be accessed and must be immediately
- /// written over
- #[inline(always)]
- unsafe fn grow_inner(&mut self, bits: usize, fill: MaybeUninit<SimdBlock>) {
- // SAFETY: The data pointer and capacity were created from a Vec initially. The block
- // len is identical to that of the original.
- let mut data = unsafe {
- Vec::from_raw_parts(self.data.as_ptr(), self.simd_block_len(), self.capacity)
- };
- let (mut blocks, rem) = div_rem(bits, SimdBlock::BITS);
- blocks += (rem > 0) as usize;
- data.resize(blocks, fill);
- let (data, capacity, _) = vec_into_parts(data);
- self.data = data;
- self.capacity = capacity;
- self.length = bits;
- }
-
- #[inline]
- unsafe fn get_unchecked(&self, subblock: usize) -> &Block {
- &*self.data.as_ptr().cast::<Block>().add(subblock)
- }
-
- #[inline]
- unsafe fn get_unchecked_mut(&mut self, subblock: usize) -> &mut Block {
- &mut *self.data.as_ptr().cast::<Block>().add(subblock)
- }
-
- #[inline]
- fn usize_len(&self) -> usize {
- let (mut blocks, rem) = div_rem(self.length, BITS);
- blocks += (rem > 0) as usize;
- blocks
- }
-
- #[inline]
- fn simd_block_len(&self) -> usize {
- let (mut blocks, rem) = div_rem(self.length, SimdBlock::BITS);
- blocks += (rem > 0) as usize;
- blocks
- }
-
- #[inline]
- fn batch_count_ones(blocks: impl IntoIterator<Item = Block>) -> usize {
- blocks.into_iter().map(|x| x.count_ones() as usize).sum()
- }
-
- #[inline]
- fn as_simd_slice(&self) -> &[SimdBlock] {
- // SAFETY: The slice constructed is within bounds of the underlying allocation. This function
- // is called with a read-only borrow so no other write can happen as long as the returned borrow lives.
- unsafe { core::slice::from_raw_parts(self.data.as_ptr().cast(), self.simd_block_len()) }
- }
-
- #[inline]
- fn as_mut_simd_slice(&mut self) -> &mut [SimdBlock] {
- // SAFETY: The slice constructed is within bounds of the underlying allocation. This function
- // is called with a mutable borrow so no other read or write can happen as long as the returned borrow lives.
- unsafe { core::slice::from_raw_parts_mut(self.data.as_ptr().cast(), self.simd_block_len()) }
- }
-
- #[inline]
- fn as_simd_slice_uninit(&self) -> &[MaybeUninit<SimdBlock>] {
- // SAFETY: The slice constructed is within bounds of the underlying allocation. This function
- // is called with a read-only borrow so no other write can happen as long as the returned borrow lives.
- unsafe { core::slice::from_raw_parts(self.data.as_ptr(), self.simd_block_len()) }
- }
-
- #[inline]
- fn as_mut_simd_slice_uninit(&mut self) -> &mut [MaybeUninit<SimdBlock>] {
- // SAFETY: The slice constructed is within bounds of the underlying allocation. This function
- // is called with a mutable borrow so no other read or write can happen as long as the returned borrow lives.
- unsafe { core::slice::from_raw_parts_mut(self.data.as_ptr(), self.simd_block_len()) }
- }
-
- /// Grows the internal size of the bitset before inserting a bit
- ///
- /// Unlike `insert`, this cannot panic, but may allocate if the bit is outside of the existing buffer's range.
- ///
- /// This is faster than calling `grow` then `insert` in succession.
- #[inline]
- pub fn grow_and_insert(&mut self, bits: usize) {
- self.grow(bits + 1);
-
- let (blocks, rem) = div_rem(bits, BITS);
- // SAFETY: The above grow ensures that the block is inside the Vec's allocation.
- unsafe {
- *self.get_unchecked_mut(blocks) |= 1 << rem;
- }
- }
-
- /// The length of the [`FixedBitSet`] in bits.
- ///
- /// Note: `len` includes both set and unset bits.
- /// ```
- /// # use fixedbitset::FixedBitSet;
- /// let bitset = FixedBitSet::with_capacity(10);
- /// // there are 0 set bits, but 10 unset bits
- /// assert_eq!(bitset.len(), 10);
- /// ```
- /// `len` does not return the count of set bits. For that, use
- /// [`bitset.count_ones(..)`](FixedBitSet::count_ones) instead.
- #[inline]
- pub fn len(&self) -> usize {
- self.length
- }
-
- /// `true` if the [`FixedBitSet`] is empty.
- ///
- /// Note that an "empty" `FixedBitSet` is a `FixedBitSet` with
- /// no bits (meaning: it's length is zero). If you want to check
- /// if all bits are unset, use [`FixedBitSet::is_clear`].
- ///
- /// ```
- /// # use fixedbitset::FixedBitSet;
- /// let bitset = FixedBitSet::with_capacity(10);
- /// assert!(!bitset.is_empty());
- ///
- /// let bitset = FixedBitSet::with_capacity(0);
- /// assert!(bitset.is_empty());
- /// ```
- #[inline]
- pub fn is_empty(&self) -> bool {
- self.len() == 0
- }
-
- /// `true` if all bits in the [`FixedBitSet`] are unset.
- ///
- /// As opposed to [`FixedBitSet::is_empty`], which is `true` only for
- /// sets without any bits, set or unset.
- ///
- /// ```
- /// # use fixedbitset::FixedBitSet;
- /// let mut bitset = FixedBitSet::with_capacity(10);
- /// assert!(bitset.is_clear());
- ///
- /// bitset.insert(2);
- /// assert!(!bitset.is_clear());
- /// ```
- ///
- /// This is equivalent to [`bitset.count_ones(..) == 0`](FixedBitSet::count_ones).
- #[inline]
- pub fn is_clear(&self) -> bool {
- self.as_simd_slice().iter().all(|block| block.is_empty())
- }
-
- /// Finds the lowest set bit in the bitset.
- ///
- /// Returns `None` if there aren't any set bits.
- ///
- /// ```
- /// # use fixedbitset::FixedBitSet;
- /// let mut bitset = FixedBitSet::with_capacity(10);
- /// assert_eq!(bitset.minimum(), None);
- ///
- /// bitset.insert(2);
- /// assert_eq!(bitset.minimum(), Some(2));
- /// bitset.insert(8);
- /// assert_eq!(bitset.minimum(), Some(2));
- /// ```
- #[inline]
- pub fn minimum(&self) -> Option<usize> {
- let (block_idx, block) = self
- .as_simd_slice()
- .iter()
- .enumerate()
- .find(|&(_, block)| !block.is_empty())?;
- let mut inner = 0;
- let mut trailing = 0;
- for subblock in block.into_usize_array() {
- if subblock != 0 {
- trailing = subblock.trailing_zeros() as usize;
- break;
- } else {
- inner += BITS;
- }
- }
- Some(block_idx * SimdBlock::BITS + inner + trailing)
- }
-
- /// Finds the highest set bit in the bitset.
- ///
- /// Returns `None` if there aren't any set bits.
- ///
- /// ```
- /// # use fixedbitset::FixedBitSet;
- /// let mut bitset = FixedBitSet::with_capacity(10);
- /// assert_eq!(bitset.maximum(), None);
- ///
- /// bitset.insert(8);
- /// assert_eq!(bitset.maximum(), Some(8));
- /// bitset.insert(2);
- /// assert_eq!(bitset.maximum(), Some(8));
- /// ```
- #[inline]
- pub fn maximum(&self) -> Option<usize> {
- let (block_idx, block) = self
- .as_simd_slice()
- .iter()
- .rev()
- .enumerate()
- .find(|&(_, block)| !block.is_empty())?;
- let mut inner = 0;
- let mut leading = 0;
- for subblock in block.into_usize_array().iter().rev() {
- if *subblock != 0 {
- leading = subblock.leading_zeros() as usize;
- break;
- } else {
- inner += BITS;
- }
- }
- let max = self.simd_block_len() * SimdBlock::BITS;
- Some(max - block_idx * SimdBlock::BITS - inner - leading - 1)
- }
-
- /// `true` if all bits in the [`FixedBitSet`] are set.
- ///
- /// ```
- /// # use fixedbitset::FixedBitSet;
- /// let mut bitset = FixedBitSet::with_capacity(10);
- /// assert!(!bitset.is_full());
- ///
- /// bitset.insert_range(..);
- /// assert!(bitset.is_full());
- /// ```
- ///
- /// This is equivalent to [`bitset.count_ones(..) == bitset.len()`](FixedBitSet::count_ones).
- #[inline]
- pub fn is_full(&self) -> bool {
- self.contains_all_in_range(..)
- }
-
- /// Return **true** if the bit is enabled in the **FixedBitSet**,
- /// **false** otherwise.
- ///
- /// Note: bits outside the capacity are always disabled.
- ///
- /// Note: Also available with index syntax: `bitset[bit]`.
- #[inline]
- pub fn contains(&self, bit: usize) -> bool {
- (bit < self.length)
- // SAFETY: The above check ensures that the block and bit are within bounds.
- .then(|| unsafe { self.contains_unchecked(bit) })
- .unwrap_or(false)
- }
-
- /// Return **true** if the bit is enabled in the **FixedBitSet**,
- /// **false** otherwise.
- ///
- /// Note: unlike `contains`, calling this with an invalid `bit`
- /// is undefined behavior.
- ///
- /// # Safety
- /// `bit` must be less than `self.len()`
- #[inline]
- pub unsafe fn contains_unchecked(&self, bit: usize) -> bool {
- let (block, i) = div_rem(bit, BITS);
- (self.get_unchecked(block) & (1 << i)) != 0
- }
-
- /// Clear all bits.
- #[inline]
- pub fn clear(&mut self) {
- for elt in self.as_mut_simd_slice().iter_mut() {
- *elt = SimdBlock::NONE
- }
- }
-
- /// Enable `bit`.
- ///
- /// **Panics** if **bit** is out of bounds.
- #[inline]
- pub fn insert(&mut self, bit: usize) {
- assert!(
- bit < self.length,
- "insert at index {} exceeds fixedbitset size {}",
- bit,
- self.length
- );
- // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
- unsafe {
- self.insert_unchecked(bit);
- }
- }
-
- /// Enable `bit` without any length checks.
- ///
- /// # Safety
- /// `bit` must be less than `self.len()`
- #[inline]
- pub unsafe fn insert_unchecked(&mut self, bit: usize) {
- let (block, i) = div_rem(bit, BITS);
- // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
- unsafe {
- *self.get_unchecked_mut(block) |= 1 << i;
- }
- }
-
- /// Disable `bit`.
- ///
- /// **Panics** if **bit** is out of bounds.
- #[inline]
- pub fn remove(&mut self, bit: usize) {
- assert!(
- bit < self.length,
- "remove at index {} exceeds fixedbitset size {}",
- bit,
- self.length
- );
- // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
- unsafe {
- self.remove_unchecked(bit);
- }
- }
-
- /// Disable `bit` without any bounds checking.
- ///
- /// # Safety
- /// `bit` must be less than `self.len()`
- #[inline]
- pub unsafe fn remove_unchecked(&mut self, bit: usize) {
- let (block, i) = div_rem(bit, BITS);
- // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
- unsafe {
- *self.get_unchecked_mut(block) &= !(1 << i);
- }
- }
-
- /// Enable `bit`, and return its previous value.
- ///
- /// **Panics** if **bit** is out of bounds.
- #[inline]
- pub fn put(&mut self, bit: usize) -> bool {
- assert!(
- bit < self.length,
- "put at index {} exceeds fixedbitset size {}",
- bit,
- self.length
- );
- // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
- unsafe { self.put_unchecked(bit) }
- }
-
- /// Enable `bit`, and return its previous value without doing any bounds checking.
- ///
- /// # Safety
- /// `bit` must be less than `self.len()`
- #[inline]
- pub unsafe fn put_unchecked(&mut self, bit: usize) -> bool {
- let (block, i) = div_rem(bit, BITS);
- // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
- unsafe {
- let word = self.get_unchecked_mut(block);
- let prev = *word & (1 << i) != 0;
- *word |= 1 << i;
- prev
- }
- }
-
- /// Toggle `bit` (inverting its state).
- ///
- /// ***Panics*** if **bit** is out of bounds
- #[inline]
- pub fn toggle(&mut self, bit: usize) {
- assert!(
- bit < self.length,
- "toggle at index {} exceeds fixedbitset size {}",
- bit,
- self.length
- );
- // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
- unsafe {
- self.toggle_unchecked(bit);
- }
- }
-
- /// Toggle `bit` (inverting its state) without any bounds checking.
- ///
- /// # Safety
- /// `bit` must be less than `self.len()`
- #[inline]
- pub unsafe fn toggle_unchecked(&mut self, bit: usize) {
- let (block, i) = div_rem(bit, BITS);
- // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
- unsafe {
- *self.get_unchecked_mut(block) ^= 1 << i;
- }
- }
-
- /// Sets a bit to the provided `enabled` value.
- ///
- /// **Panics** if **bit** is out of bounds.
- #[inline]
- pub fn set(&mut self, bit: usize, enabled: bool) {
- assert!(
- bit < self.length,
- "set at index {} exceeds fixedbitset size {}",
- bit,
- self.length
- );
- // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
- unsafe {
- self.set_unchecked(bit, enabled);
- }
- }
-
- /// Sets a bit to the provided `enabled` value without doing any bounds checking.
- ///
- /// # Safety
- /// `bit` must be less than `self.len()`
- #[inline]
- pub unsafe fn set_unchecked(&mut self, bit: usize, enabled: bool) {
- let (block, i) = div_rem(bit, BITS);
- // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
- let elt = unsafe { self.get_unchecked_mut(block) };
- if enabled {
- *elt |= 1 << i;
- } else {
- *elt &= !(1 << i);
- }
- }
-
- /// Copies boolean value from specified bit to the specified bit.
- ///
- /// If `from` is out-of-bounds, `to` will be unset.
- ///
- /// **Panics** if **to** is out of bounds.
- #[inline]
- pub fn copy_bit(&mut self, from: usize, to: usize) {
- assert!(
- to < self.length,
- "copy to index {} exceeds fixedbitset size {}",
- to,
- self.length
- );
- let enabled = self.contains(from);
- // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
- unsafe { self.set_unchecked(to, enabled) };
- }
-
- /// Copies boolean value from specified bit to the specified bit.
- ///
- /// Note: unlike `copy_bit`, calling this with an invalid `from`
- /// is undefined behavior.
- ///
- /// # Safety
- /// `to` must both be less than `self.len()`
- #[inline]
- pub unsafe fn copy_bit_unchecked(&mut self, from: usize, to: usize) {
- // SAFETY: Caller must ensure that `from` is within bounds.
- let enabled = self.contains_unchecked(from);
- // SAFETY: Caller must ensure that `to` is within bounds.
- self.set_unchecked(to, enabled);
- }
-
- /// Count the number of set bits in the given bit range.
- ///
- /// This function is potentially much faster than using `ones(other).count()`.
- /// Use `..` to count the whole content of the bitset.
- ///
- /// **Panics** if the range extends past the end of the bitset.
- #[inline]
- pub fn count_ones<T: IndexRange>(&self, range: T) -> usize {
- Self::batch_count_ones(Masks::new(range, self.length).map(|(block, mask)| {
- // SAFETY: Masks cannot return a block index that is out of range.
- unsafe { *self.get_unchecked(block) & mask }
- }))
- }
-
- /// Count the number of unset bits in the given bit range.
- ///
- /// This function is potentially much faster than using `zeroes(other).count()`.
- /// Use `..` to count the whole content of the bitset.
- ///
- /// **Panics** if the range extends past the end of the bitset.
- #[inline]
- pub fn count_zeroes<T: IndexRange>(&self, range: T) -> usize {
- Self::batch_count_ones(Masks::new(range, self.length).map(|(block, mask)| {
- // SAFETY: Masks cannot return a block index that is out of range.
- unsafe { !*self.get_unchecked(block) & mask }
- }))
- }
-
- /// Sets every bit in the given range to the given state (`enabled`)
- ///
- /// Use `..` to set the whole bitset.
- ///
- /// **Panics** if the range extends past the end of the bitset.
- #[inline]
- pub fn set_range<T: IndexRange>(&mut self, range: T, enabled: bool) {
- if enabled {
- self.insert_range(range);
- } else {
- self.remove_range(range);
- }
- }
-
- /// Enables every bit in the given range.
- ///
- /// Use `..` to make the whole bitset ones.
- ///
- /// **Panics** if the range extends past the end of the bitset.
- #[inline]
- pub fn insert_range<T: IndexRange>(&mut self, range: T) {
- for (block, mask) in Masks::new(range, self.length) {
- // SAFETY: Masks cannot return a block index that is out of range.
- let block = unsafe { self.get_unchecked_mut(block) };
- *block |= mask;
- }
- }
-
- /// Disables every bit in the given range.
- ///
- /// Use `..` to make the whole bitset ones.
- ///
- /// **Panics** if the range extends past the end of the bitset.
- #[inline]
- pub fn remove_range<T: IndexRange>(&mut self, range: T) {
- for (block, mask) in Masks::new(range, self.length) {
- // SAFETY: Masks cannot return a block index that is out of range.
- let block = unsafe { self.get_unchecked_mut(block) };
- *block &= !mask;
- }
- }
-
- /// Toggles (inverts) every bit in the given range.
- ///
- /// Use `..` to toggle the whole bitset.
- ///
- /// **Panics** if the range extends past the end of the bitset.
- #[inline]
- pub fn toggle_range<T: IndexRange>(&mut self, range: T) {
- for (block, mask) in Masks::new(range, self.length) {
- // SAFETY: Masks cannot return a block index that is out of range.
- let block = unsafe { self.get_unchecked_mut(block) };
- *block ^= mask;
- }
- }
-
- /// Checks if the bitset contains every bit in the given range.
- ///
- /// **Panics** if the range extends past the end of the bitset.
- #[inline]
- pub fn contains_all_in_range<T: IndexRange>(&self, range: T) -> bool {
- for (block, mask) in Masks::new(range, self.length) {
- // SAFETY: Masks cannot return a block index that is out of range.
- let block = unsafe { self.get_unchecked(block) };
- if block & mask != mask {
- return false;
- }
- }
- true
- }
-
- /// Checks if the bitset contains at least one set bit in the given range.
- ///
- /// **Panics** if the range extends past the end of the bitset.
- #[inline]
- pub fn contains_any_in_range<T: IndexRange>(&self, range: T) -> bool {
- for (block, mask) in Masks::new(range, self.length) {
- // SAFETY: Masks cannot return a block index that is out of range.
- let block = unsafe { self.get_unchecked(block) };
- if block & mask != 0 {
- return true;
- }
- }
- false
- }
-
- /// View the bitset as a slice of `Block` blocks
- #[inline]
- pub fn as_slice(&self) -> &[Block] {
- // SAFETY: The bits from both usize and Block are required to be reinterprettable, and
- // neither have any padding or alignment issues. The slice constructed is within bounds
- // of the underlying allocation. This function is called with a read-only borrow so
- // no other write can happen as long as the returned borrow lives.
- unsafe {
- let ptr = self.data.as_ptr().cast::<Block>();
- core::slice::from_raw_parts(ptr, self.usize_len())
- }
- }
-
- /// View the bitset as a mutable slice of `Block` blocks. Writing past the bitlength in the last
- /// will cause `contains` to return potentially incorrect results for bits past the bitlength.
- #[inline]
- pub fn as_mut_slice(&mut self) -> &mut [Block] {
- // SAFETY: The bits from both usize and Block are required to be reinterprettable, and
- // neither have any padding or alignment issues. The slice constructed is within bounds
- // of the underlying allocation. This function is called with a mutable borrow so
- // no other read or write can happen as long as the returned borrow lives.
- unsafe {
- let ptr = self.data.as_ptr().cast::<Block>();
- core::slice::from_raw_parts_mut(ptr, self.usize_len())
- }
- }
-
- /// Iterates over all enabled bits.
- ///
- /// Iterator element is the index of the `1` bit, type `usize`.
- #[inline]
- pub fn ones(&self) -> Ones {
- match self.as_slice().split_first() {
- Some((&first_block, rem)) => {
- let (&last_block, rem) = rem.split_last().unwrap_or((&0, rem));
- Ones {
- bitset_front: first_block,
- bitset_back: last_block,
- block_idx_front: 0,
- block_idx_back: (1 + rem.len()) * BITS,
- remaining_blocks: rem.iter(),
- }
- }
- None => Ones {
- bitset_front: 0,
- bitset_back: 0,
- block_idx_front: 0,
- block_idx_back: 0,
- remaining_blocks: [].iter(),
- },
- }
- }
-
- /// Iterates over all enabled bits.
- ///
- /// Iterator element is the index of the `1` bit, type `usize`.
- /// Unlike `ones`, this function consumes the `FixedBitset`.
- pub fn into_ones(self) -> IntoOnes {
- let ptr = self.data.as_ptr().cast();
- let len = self.simd_block_len() * SimdBlock::USIZE_COUNT;
- // SAFETY:
- // - ptr comes from self.data, so it is valid;
- // - self.data is valid for self.data.len() SimdBlocks,
- // which is exactly self.data.len() * SimdBlock::USIZE_COUNT usizes;
- // - we will keep this slice around only as long as self.data is,
- // so it won't become dangling.
- let slice = unsafe { core::slice::from_raw_parts(ptr, len) };
- // SAFETY: The data pointer and capacity were created from a Vec initially. The block
- // len is identical to that of the original.
- let data: Vec<SimdBlock> = unsafe {
- Vec::from_raw_parts(
- self.data.as_ptr().cast(),
- self.simd_block_len(),
- self.capacity,
- )
- };
- let mut iter = slice.iter().copied();
-
- core::mem::forget(self);
-
- IntoOnes {
- bitset_front: iter.next().unwrap_or(0),
- bitset_back: iter.next_back().unwrap_or(0),
- block_idx_front: 0,
- block_idx_back: len.saturating_sub(1) * BITS,
- remaining_blocks: iter,
- _buf: data,
- }
- }
-
- /// Iterates over all disabled bits.
- ///
- /// Iterator element is the index of the `0` bit, type `usize`.
- #[inline]
- pub fn zeroes(&self) -> Zeroes {
- match self.as_slice().split_first() {
- Some((&block, rem)) => Zeroes {
- bitset: !block,
- block_idx: 0,
- len: self.len(),
- remaining_blocks: rem.iter(),
- },
- None => Zeroes {
- bitset: !0,
- block_idx: 0,
- len: self.len(),
- remaining_blocks: [].iter(),
- },
- }
- }
-
- /// Returns a lazy iterator over the intersection of two `FixedBitSet`s
- pub fn intersection<'a>(&'a self, other: &'a FixedBitSet) -> Intersection<'a> {
- Intersection {
- iter: self.ones(),
- other,
- }
- }
-
- /// Returns a lazy iterator over the union of two `FixedBitSet`s.
- pub fn union<'a>(&'a self, other: &'a FixedBitSet) -> Union<'a> {
- Union {
- iter: self.ones().chain(other.difference(self)),
- }
- }
-
- /// Returns a lazy iterator over the difference of two `FixedBitSet`s. The difference of `a`
- /// and `b` is the elements of `a` which are not in `b`.
- pub fn difference<'a>(&'a self, other: &'a FixedBitSet) -> Difference<'a> {
- Difference {
- iter: self.ones(),
- other,
- }
- }
-
- /// Returns a lazy iterator over the symmetric difference of two `FixedBitSet`s.
- /// The symmetric difference of `a` and `b` is the elements of one, but not both, sets.
- pub fn symmetric_difference<'a>(&'a self, other: &'a FixedBitSet) -> SymmetricDifference<'a> {
- SymmetricDifference {
- iter: self.difference(other).chain(other.difference(self)),
- }
- }
-
- /// In-place union of two `FixedBitSet`s.
- ///
- /// On calling this method, `self`'s capacity may be increased to match `other`'s.
- pub fn union_with(&mut self, other: &FixedBitSet) {
- if other.len() >= self.len() {
- self.grow(other.len());
- }
- self.as_mut_simd_slice()
- .iter_mut()
- .zip(other.as_simd_slice().iter())
- .for_each(|(x, y)| *x |= *y);
- }
-
- /// In-place intersection of two `FixedBitSet`s.
- ///
- /// On calling this method, `self`'s capacity will remain the same as before.
- pub fn intersect_with(&mut self, other: &FixedBitSet) {
- let me = self.as_mut_simd_slice();
- let other = other.as_simd_slice();
- me.iter_mut().zip(other.iter()).for_each(|(x, y)| {
- *x &= *y;
- });
- let mn = core::cmp::min(me.len(), other.len());
- for wd in &mut me[mn..] {
- *wd = SimdBlock::NONE;
- }
- }
-
- /// In-place difference of two `FixedBitSet`s.
- ///
- /// On calling this method, `self`'s capacity will remain the same as before.
- pub fn difference_with(&mut self, other: &FixedBitSet) {
- self.as_mut_simd_slice()
- .iter_mut()
- .zip(other.as_simd_slice().iter())
- .for_each(|(x, y)| {
- *x &= !*y;
- });
-
- // There's no need to grow self or do any other adjustments.
- //
- // * If self is longer than other, the bits at the end of self won't be affected since other
- // has them implicitly set to 0.
- // * If other is longer than self, the bits at the end of other are irrelevant since self
- // has them set to 0 anyway.
- }
-
- /// In-place symmetric difference of two `FixedBitSet`s.
- ///
- /// On calling this method, `self`'s capacity may be increased to match `other`'s.
- pub fn symmetric_difference_with(&mut self, other: &FixedBitSet) {
- if other.len() >= self.len() {
- self.grow(other.len());
- }
- self.as_mut_simd_slice()
- .iter_mut()
- .zip(other.as_simd_slice().iter())
- .for_each(|(x, y)| {
- *x ^= *y;
- });
- }
-
- /// Computes how many bits would be set in the union between two bitsets.
- ///
- /// This is potentially much faster than using `union(other).count()`. Unlike
- /// other methods like using [`union_with`] followed by [`count_ones`], this
- /// does not mutate in place or require separate allocations.
- #[inline]
- pub fn union_count(&self, other: &FixedBitSet) -> usize {
- let me = self.as_slice();
- let other = other.as_slice();
- let count = Self::batch_count_ones(me.iter().zip(other.iter()).map(|(x, y)| (*x | *y)));
- match other.len().cmp(&me.len()) {
- Ordering::Greater => count + Self::batch_count_ones(other[me.len()..].iter().copied()),
- Ordering::Less => count + Self::batch_count_ones(me[other.len()..].iter().copied()),
- Ordering::Equal => count,
- }
- }
-
- /// Computes how many bits would be set in the intersection between two bitsets.
- ///
- /// This is potentially much faster than using `intersection(other).count()`. Unlike
- /// other methods like using [`intersect_with`] followed by [`count_ones`], this
- /// does not mutate in place or require separate allocations.
- #[inline]
- pub fn intersection_count(&self, other: &FixedBitSet) -> usize {
- Self::batch_count_ones(
- self.as_slice()
- .iter()
- .zip(other.as_slice())
- .map(|(x, y)| (*x & *y)),
- )
- }
-
- /// Computes how many bits would be set in the difference between two bitsets.
- ///
- /// This is potentially much faster than using `difference(other).count()`. Unlike
- /// other methods like using [`difference_with`] followed by [`count_ones`], this
- /// does not mutate in place or require separate allocations.
- #[inline]
- pub fn difference_count(&self, other: &FixedBitSet) -> usize {
- Self::batch_count_ones(
- self.as_slice()
- .iter()
- .zip(other.as_slice().iter())
- .map(|(x, y)| (*x & !*y)),
- )
- }
-
- /// Computes how many bits would be set in the symmetric difference between two bitsets.
- ///
- /// This is potentially much faster than using `symmetric_difference(other).count()`. Unlike
- /// other methods like using [`symmetric_difference_with`] followed by [`count_ones`], this
- /// does not mutate in place or require separate allocations.
- #[inline]
- pub fn symmetric_difference_count(&self, other: &FixedBitSet) -> usize {
- let me = self.as_slice();
- let other = other.as_slice();
- let count = Self::batch_count_ones(me.iter().zip(other.iter()).map(|(x, y)| (*x ^ *y)));
- match other.len().cmp(&me.len()) {
- Ordering::Greater => count + Self::batch_count_ones(other[me.len()..].iter().copied()),
- Ordering::Less => count + Self::batch_count_ones(me[other.len()..].iter().copied()),
- Ordering::Equal => count,
- }
- }
-
- /// Returns `true` if `self` has no elements in common with `other`. This
- /// is equivalent to checking for an empty intersection.
- pub fn is_disjoint(&self, other: &FixedBitSet) -> bool {
- self.as_simd_slice()
- .iter()
- .zip(other.as_simd_slice())
- .all(|(x, y)| (*x & *y).is_empty())
- }
-
- /// Returns `true` if the set is a subset of another, i.e. `other` contains
- /// at least all the values in `self`.
- pub fn is_subset(&self, other: &FixedBitSet) -> bool {
- let me = self.as_simd_slice();
- let other = other.as_simd_slice();
- me.iter()
- .zip(other.iter())
- .all(|(x, y)| x.andnot(*y).is_empty())
- && me.iter().skip(other.len()).all(|x| x.is_empty())
- }
-
- /// Returns `true` if the set is a superset of another, i.e. `self` contains
- /// at least all the values in `other`.
- pub fn is_superset(&self, other: &FixedBitSet) -> bool {
- other.is_subset(self)
- }
-}
-
-impl Hash for FixedBitSet {
- fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
- self.length.hash(state);
- self.as_simd_slice().hash(state);
- }
-}
-
-impl PartialEq for FixedBitSet {
- fn eq(&self, other: &Self) -> bool {
- self.length == other.length && self.as_simd_slice().eq(other.as_simd_slice())
- }
-}
-
-impl PartialOrd for FixedBitSet {
- fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
- Some(self.cmp(other))
- }
-}
-
-impl Ord for FixedBitSet {
- fn cmp(&self, other: &Self) -> Ordering {
- self.length
- .cmp(&other.length)
- .then_with(|| self.as_simd_slice().cmp(other.as_simd_slice()))
- }
-}
-
-impl Default for FixedBitSet {
- fn default() -> Self {
- Self::new()
- }
-}
-
-impl Drop for FixedBitSet {
- fn drop(&mut self) {
- // SAFETY: The data pointer and capacity were created from a Vec initially. The block
- // len is identical to that of the original.
- drop(unsafe {
- Vec::from_raw_parts(self.data.as_ptr(), self.simd_block_len(), self.capacity)
- });
- }
-}
-
-impl Binary for FixedBitSet {
- fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
- if f.alternate() {
- f.write_str("0b")?;
- }
-
- for i in 0..self.length {
- if self[i] {
- f.write_char('1')?;
- } else {
- f.write_char('0')?;
- }
- }
-
- Ok(())
- }
-}
-
-impl Display for FixedBitSet {
- fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
- Binary::fmt(&self, f)
- }
-}
-
-/// An iterator producing elements in the difference of two sets.
-///
-/// This struct is created by the [`FixedBitSet::difference`] method.
-pub struct Difference<'a> {
- iter: Ones<'a>,
- other: &'a FixedBitSet,
-}
-
-impl<'a> Iterator for Difference<'a> {
- type Item = usize;
-
- #[inline]
- fn next(&mut self) -> Option<Self::Item> {
- self.iter.by_ref().find(|&nxt| !self.other.contains(nxt))
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.iter.size_hint()
- }
-}
-
-impl<'a> DoubleEndedIterator for Difference<'a> {
- fn next_back(&mut self) -> Option<Self::Item> {
- self.iter
- .by_ref()
- .rev()
- .find(|&nxt| !self.other.contains(nxt))
- }
-}
-
-// Difference will continue to return None once it first returns None.
-impl<'a> FusedIterator for Difference<'a> {}
-
-/// An iterator producing elements in the symmetric difference of two sets.
-///
-/// This struct is created by the [`FixedBitSet::symmetric_difference`] method.
-pub struct SymmetricDifference<'a> {
- iter: Chain<Difference<'a>, Difference<'a>>,
-}
-
-impl<'a> Iterator for SymmetricDifference<'a> {
- type Item = usize;
-
- #[inline]
- fn next(&mut self) -> Option<Self::Item> {
- self.iter.next()
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.iter.size_hint()
- }
-}
-
-impl<'a> DoubleEndedIterator for SymmetricDifference<'a> {
- fn next_back(&mut self) -> Option<Self::Item> {
- self.iter.next_back()
- }
-}
-
-// SymmetricDifference will continue to return None once it first returns None.
-impl<'a> FusedIterator for SymmetricDifference<'a> {}
-
-/// An iterator producing elements in the intersection of two sets.
-///
-/// This struct is created by the [`FixedBitSet::intersection`] method.
-pub struct Intersection<'a> {
- iter: Ones<'a>,
- other: &'a FixedBitSet,
-}
-
-impl<'a> Iterator for Intersection<'a> {
- type Item = usize; // the bit position of the '1'
-
- #[inline]
- fn next(&mut self) -> Option<Self::Item> {
- self.iter.by_ref().find(|&nxt| self.other.contains(nxt))
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.iter.size_hint()
- }
-}
-
-impl<'a> DoubleEndedIterator for Intersection<'a> {
- fn next_back(&mut self) -> Option<Self::Item> {
- self.iter
- .by_ref()
- .rev()
- .find(|&nxt| self.other.contains(nxt))
- }
-}
-
-// Intersection will continue to return None once it first returns None.
-impl<'a> FusedIterator for Intersection<'a> {}
-
-/// An iterator producing elements in the union of two sets.
-///
-/// This struct is created by the [`FixedBitSet::union`] method.
-pub struct Union<'a> {
- iter: Chain<Ones<'a>, Difference<'a>>,
-}
-
-impl<'a> Iterator for Union<'a> {
- type Item = usize;
-
- #[inline]
- fn next(&mut self) -> Option<Self::Item> {
- self.iter.next()
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.iter.size_hint()
- }
-}
-
-impl<'a> DoubleEndedIterator for Union<'a> {
- fn next_back(&mut self) -> Option<Self::Item> {
- self.iter.next_back()
- }
-}
-
-// Union will continue to return None once it first returns None.
-impl<'a> FusedIterator for Union<'a> {}
-
-struct Masks {
- first_block: usize,
- first_mask: usize,
- last_block: usize,
- last_mask: usize,
-}
-
-impl Masks {
- #[inline]
- fn new<T: IndexRange>(range: T, length: usize) -> Masks {
- let start = range.start().unwrap_or(0);
- let end = range.end().unwrap_or(length);
- assert!(
- start <= end && end <= length,
- "invalid range {}..{} for a fixedbitset of size {}",
- start,
- end,
- length
- );
-
- let (first_block, first_rem) = div_rem(start, BITS);
- let (last_block, last_rem) = div_rem(end, BITS);
-
- Masks {
- first_block,
- first_mask: usize::MAX << first_rem,
- last_block,
- last_mask: (usize::MAX >> 1) >> (BITS - last_rem - 1),
- // this is equivalent to `MAX >> (BITS - x)` with correct semantics when x == 0.
- }
- }
-}
-
-impl Iterator for Masks {
- type Item = (usize, usize);
-
- #[inline]
- fn next(&mut self) -> Option<Self::Item> {
- match self.first_block.cmp(&self.last_block) {
- Ordering::Less => {
- let res = (self.first_block, self.first_mask);
- self.first_block += 1;
- self.first_mask = !0;
- Some(res)
- }
- Ordering::Equal => {
- let mask = self.first_mask & self.last_mask;
- let res = if mask == 0 {
- None
- } else {
- Some((self.first_block, mask))
- };
- self.first_block += 1;
- res
- }
- Ordering::Greater => None,
- }
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- (self.first_block..=self.last_block).size_hint()
- }
-}
-
-// Masks will continue to return None once it first returns None.
-impl FusedIterator for Masks {}
-
-// Masks's size_hint implementation is exact. It never returns an
-// unbounded value and always returns an exact number of values.
-impl ExactSizeIterator for Masks {}
-
-/// An iterator producing the indices of the set bit in a set.
-///
-/// This struct is created by the [`FixedBitSet::ones`] method.
-pub struct Ones<'a> {
- bitset_front: usize,
- bitset_back: usize,
- block_idx_front: usize,
- block_idx_back: usize,
- remaining_blocks: core::slice::Iter<'a, usize>,
-}
-
-impl<'a> Ones<'a> {
- #[inline]
- pub fn last_positive_bit_and_unset(n: &mut usize) -> usize {
- // Find the last set bit using x & -x
- let last_bit = *n & n.wrapping_neg();
-
- // Find the position of the last set bit
- let position = last_bit.trailing_zeros();
-
- // Unset the last set bit
- *n &= *n - 1;
-
- position as usize
- }
-
- #[inline]
- fn first_positive_bit_and_unset(n: &mut usize) -> usize {
- /* Identify the first non zero bit */
- let bit_idx = n.leading_zeros();
-
- /* set that bit to zero */
- let mask = !((1_usize) << (BITS as u32 - bit_idx - 1));
- n.bitand_assign(mask);
-
- bit_idx as usize
- }
-}
-
-impl<'a> DoubleEndedIterator for Ones<'a> {
- fn next_back(&mut self) -> Option<Self::Item> {
- while self.bitset_back == 0 {
- match self.remaining_blocks.next_back() {
- None => {
- if self.bitset_front != 0 {
- self.bitset_back = 0;
- self.block_idx_back = self.block_idx_front;
- return Some(
- self.block_idx_front + BITS
- - Self::first_positive_bit_and_unset(&mut self.bitset_front)
- - 1,
- );
- } else {
- return None;
- }
- }
- Some(next_block) => {
- self.bitset_back = *next_block;
- self.block_idx_back -= BITS;
- }
- };
- }
-
- Some(
- self.block_idx_back - Self::first_positive_bit_and_unset(&mut self.bitset_back) + BITS
- - 1,
- )
- }
-}
-
-impl<'a> Iterator for Ones<'a> {
- type Item = usize; // the bit position of the '1'
-
- #[inline]
- fn next(&mut self) -> Option<Self::Item> {
- while self.bitset_front == 0 {
- match self.remaining_blocks.next() {
- Some(next_block) => {
- self.bitset_front = *next_block;
- self.block_idx_front += BITS;
- }
- None => {
- if self.bitset_back != 0 {
- // not needed for iteration, but for size_hint
- self.block_idx_front = self.block_idx_back;
- self.bitset_front = 0;
-
- return Some(
- self.block_idx_back
- + Self::last_positive_bit_and_unset(&mut self.bitset_back),
- );
- } else {
- return None;
- }
- }
- };
- }
-
- Some(self.block_idx_front + Self::last_positive_bit_and_unset(&mut self.bitset_front))
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- (
- 0,
- (Some(self.block_idx_back - self.block_idx_front + 2 * BITS)),
- )
- }
-}
-
-// Ones will continue to return None once it first returns None.
-impl<'a> FusedIterator for Ones<'a> {}
-
-/// An iterator producing the indices of the set bit in a set.
-///
-/// This struct is created by the [`FixedBitSet::ones`] method.
-pub struct Zeroes<'a> {
- bitset: usize,
- block_idx: usize,
- len: usize,
- remaining_blocks: core::slice::Iter<'a, usize>,
-}
-
-impl<'a> Iterator for Zeroes<'a> {
- type Item = usize; // the bit position of the '1'
-
- #[inline]
- fn next(&mut self) -> Option<Self::Item> {
- while self.bitset == 0 {
- self.bitset = !*self.remaining_blocks.next()?;
- self.block_idx += BITS;
- }
- let t = self.bitset & (0_usize).wrapping_sub(self.bitset);
- let r = self.bitset.trailing_zeros() as usize;
- self.bitset ^= t;
- let bit = self.block_idx + r;
- // The remaining zeroes beyond the length of the bitset must be excluded.
- if bit < self.len {
- Some(bit)
- } else {
- None
- }
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- (0, Some(self.len))
- }
-}
-
-// Zeroes will stop returning Some when exhausted.
-impl<'a> FusedIterator for Zeroes<'a> {}
-
-impl Clone for FixedBitSet {
- #[inline]
- fn clone(&self) -> Self {
- Self::from_blocks_and_len(Vec::from(self.as_simd_slice()), self.length)
- }
-
- #[inline]
- fn clone_from(&mut self, source: &Self) {
- if self.length < source.length {
- // SAFETY: `fill` is uninitialized, but is immediately initialized from `source`.
- unsafe { self.grow_inner(source.length, MaybeUninit::uninit()) };
- }
- let me = self.as_mut_simd_slice_uninit();
- let them = source.as_simd_slice_uninit();
- match me.len().cmp(&them.len()) {
- Ordering::Greater => {
- let (head, tail) = me.split_at_mut(them.len());
- head.copy_from_slice(them);
- tail.fill(MaybeUninit::new(SimdBlock::NONE));
- }
- Ordering::Equal => me.copy_from_slice(them),
- // The grow_inner above ensures that self is at least as large as source.
- // so this branch is unreachable.
- Ordering::Less => {}
- }
- self.length = source.length;
- }
-}
-
-/// Return **true** if the bit is enabled in the bitset,
-/// or **false** otherwise.
-///
-/// Note: bits outside the capacity are always disabled, and thus
-/// indexing a FixedBitSet will not panic.
-impl Index<usize> for FixedBitSet {
- type Output = bool;
-
- #[inline]
- fn index(&self, bit: usize) -> &bool {
- if self.contains(bit) {
- &true
- } else {
- &false
- }
- }
-}
-
-/// Sets the bit at index **i** to **true** for each item **i** in the input **src**.
-impl Extend<usize> for FixedBitSet {
- fn extend<I: IntoIterator<Item = usize>>(&mut self, src: I) {
- let iter = src.into_iter();
- for i in iter {
- if i >= self.len() {
- self.grow(i + 1);
- }
- self.put(i);
- }
- }
-}
-
-/// Return a FixedBitSet containing bits set to **true** for every bit index in
-/// the iterator, other bits are set to **false**.
-impl FromIterator<usize> for FixedBitSet {
- fn from_iter<I: IntoIterator<Item = usize>>(src: I) -> Self {
- let mut fbs = FixedBitSet::with_capacity(0);
- fbs.extend(src);
- fbs
- }
-}
-
-pub struct IntoOnes {
- bitset_front: Block,
- bitset_back: Block,
- block_idx_front: usize,
- block_idx_back: usize,
- remaining_blocks: core::iter::Copied<core::slice::Iter<'static, usize>>,
- // Keep buf along so that `remaining_blocks` remains valid.
- _buf: Vec<SimdBlock>,
-}
-
-impl IntoOnes {
- #[inline]
- pub fn last_positive_bit_and_unset(n: &mut Block) -> usize {
- // Find the last set bit using x & -x
- let last_bit = *n & n.wrapping_neg();
-
- // Find the position of the last set bit
- let position = last_bit.trailing_zeros();
-
- // Unset the last set bit
- *n &= *n - 1;
-
- position as usize
- }
-
- #[inline]
- fn first_positive_bit_and_unset(n: &mut Block) -> usize {
- /* Identify the first non zero bit */
- let bit_idx = n.leading_zeros();
-
- /* set that bit to zero */
- let mask = !((1_usize) << (BITS as u32 - bit_idx - 1));
- n.bitand_assign(mask);
-
- bit_idx as usize
- }
-}
-
-impl DoubleEndedIterator for IntoOnes {
- fn next_back(&mut self) -> Option<Self::Item> {
- while self.bitset_back == 0 {
- match self.remaining_blocks.next_back() {
- None => {
- if self.bitset_front != 0 {
- self.bitset_back = 0;
- self.block_idx_back = self.block_idx_front;
- return Some(
- self.block_idx_front + BITS
- - Self::first_positive_bit_and_unset(&mut self.bitset_front)
- - 1,
- );
- } else {
- return None;
- }
- }
- Some(next_block) => {
- self.bitset_back = next_block;
- self.block_idx_back -= BITS;
- }
- };
- }
-
- Some(
- self.block_idx_back - Self::first_positive_bit_and_unset(&mut self.bitset_back) + BITS
- - 1,
- )
- }
-}
-
-impl Iterator for IntoOnes {
- type Item = usize; // the bit position of the '1'
-
- #[inline]
- fn next(&mut self) -> Option<Self::Item> {
- while self.bitset_front == 0 {
- match self.remaining_blocks.next() {
- Some(next_block) => {
- self.bitset_front = next_block;
- self.block_idx_front += BITS;
- }
- None => {
- if self.bitset_back != 0 {
- // not needed for iteration, but for size_hint
- self.block_idx_front = self.block_idx_back;
- self.bitset_front = 0;
-
- return Some(
- self.block_idx_back
- + Self::last_positive_bit_and_unset(&mut self.bitset_back),
- );
- } else {
- return None;
- }
- }
- };
- }
-
- Some(self.block_idx_front + Self::last_positive_bit_and_unset(&mut self.bitset_front))
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- (
- 0,
- (Some(self.block_idx_back - self.block_idx_front + 2 * BITS)),
- )
- }
-}
-
-// Ones will continue to return None once it first returns None.
-impl FusedIterator for IntoOnes {}
-
-impl<'a> BitAnd for &'a FixedBitSet {
- type Output = FixedBitSet;
- fn bitand(self, other: &FixedBitSet) -> FixedBitSet {
- let (short, long) = {
- if self.len() <= other.len() {
- (self.as_simd_slice(), other.as_simd_slice())
- } else {
- (other.as_simd_slice(), self.as_simd_slice())
- }
- };
- let mut data = Vec::from(short);
- for (data, block) in data.iter_mut().zip(long.iter()) {
- *data &= *block;
- }
- let len = core::cmp::min(self.len(), other.len());
- FixedBitSet::from_blocks_and_len(data, len)
- }
-}
-
-impl BitAndAssign for FixedBitSet {
- fn bitand_assign(&mut self, other: Self) {
- self.intersect_with(&other);
- }
-}
-
-impl BitAndAssign<&Self> for FixedBitSet {
- fn bitand_assign(&mut self, other: &Self) {
- self.intersect_with(other);
- }
-}
-
-impl<'a> BitOr for &'a FixedBitSet {
- type Output = FixedBitSet;
- fn bitor(self, other: &FixedBitSet) -> FixedBitSet {
- let (short, long) = {
- if self.len() <= other.len() {
- (self.as_simd_slice(), other.as_simd_slice())
- } else {
- (other.as_simd_slice(), self.as_simd_slice())
- }
- };
- let mut data = Vec::from(long);
- for (data, block) in data.iter_mut().zip(short.iter()) {
- *data |= *block;
- }
- let len = core::cmp::max(self.len(), other.len());
- FixedBitSet::from_blocks_and_len(data, len)
- }
-}
-
-impl BitOrAssign for FixedBitSet {
- fn bitor_assign(&mut self, other: Self) {
- self.union_with(&other);
- }
-}
-
-impl BitOrAssign<&Self> for FixedBitSet {
- fn bitor_assign(&mut self, other: &Self) {
- self.union_with(other);
- }
-}
-
-impl<'a> BitXor for &'a FixedBitSet {
- type Output = FixedBitSet;
- fn bitxor(self, other: &FixedBitSet) -> FixedBitSet {
- let (short, long) = {
- if self.len() <= other.len() {
- (self.as_simd_slice(), other.as_simd_slice())
- } else {
- (other.as_simd_slice(), self.as_simd_slice())
- }
- };
- let mut data = Vec::from(long);
- for (data, block) in data.iter_mut().zip(short.iter()) {
- *data ^= *block;
- }
- let len = core::cmp::max(self.len(), other.len());
- FixedBitSet::from_blocks_and_len(data, len)
- }
-}
-
-impl BitXorAssign for FixedBitSet {
- fn bitxor_assign(&mut self, other: Self) {
- self.symmetric_difference_with(&other);
- }
-}
-
-impl BitXorAssign<&Self> for FixedBitSet {
- fn bitxor_assign(&mut self, other: &Self) {
- self.symmetric_difference_with(other);
- }
-}
diff --git a/vendor/fixedbitset/src/range.rs b/vendor/fixedbitset/src/range.rs
deleted file mode 100644
index 9b385c42..00000000
--- a/vendor/fixedbitset/src/range.rs
+++ /dev/null
@@ -1,45 +0,0 @@
-use core::ops::{Range, RangeFrom, RangeFull, RangeTo};
-
-// Taken from https://github.com/bluss/odds/blob/master/src/range.rs.
-
-/// **IndexRange** is implemented by Rust's built-in range types, produced
-/// by range syntax like `..`, `a..`, `..b` or `c..d`.
-pub trait IndexRange<T = usize> {
- #[inline]
- /// Start index (inclusive)
- fn start(&self) -> Option<T> {
- None
- }
- #[inline]
- /// End index (exclusive)
- fn end(&self) -> Option<T> {
- None
- }
-}
-
-impl<T> IndexRange<T> for RangeFull {}
-
-impl<T: Copy> IndexRange<T> for RangeFrom<T> {
- #[inline]
- fn start(&self) -> Option<T> {
- Some(self.start)
- }
-}
-
-impl<T: Copy> IndexRange<T> for RangeTo<T> {
- #[inline]
- fn end(&self) -> Option<T> {
- Some(self.end)
- }
-}
-
-impl<T: Copy> IndexRange<T> for Range<T> {
- #[inline]
- fn start(&self) -> Option<T> {
- Some(self.start)
- }
- #[inline]
- fn end(&self) -> Option<T> {
- Some(self.end)
- }
-}
diff --git a/vendor/fixedbitset/src/serde_impl.rs b/vendor/fixedbitset/src/serde_impl.rs
deleted file mode 100644
index 98231599..00000000
--- a/vendor/fixedbitset/src/serde_impl.rs
+++ /dev/null
@@ -1,150 +0,0 @@
-#[cfg(not(feature = "std"))]
-use core as std;
-
-use crate::{Block, FixedBitSet, BYTES};
-use alloc::vec::Vec;
-use core::{convert::TryFrom, fmt};
-use serde::de::{self, Deserialize, Deserializer, MapAccess, SeqAccess, Visitor};
-use serde::ser::{Serialize, SerializeStruct, Serializer};
-
-struct BitSetByteSerializer<'a>(&'a FixedBitSet);
-
-impl Serialize for FixedBitSet {
- fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
- where
- S: Serializer,
- {
- let mut struct_serializer = serializer.serialize_struct("FixedBitset", 2)?;
- struct_serializer.serialize_field("length", &(self.length as u64))?;
- struct_serializer.serialize_field("data", &BitSetByteSerializer(self))?;
- struct_serializer.end()
- }
-}
-
-impl<'a> Serialize for BitSetByteSerializer<'a> {
- fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
- where
- S: Serializer,
- {
- let len = self.0.as_slice().len() * BYTES;
- // PERF: Figure out a way to do this without allocating.
- let mut temp = Vec::with_capacity(len);
- for block in self.0.as_slice() {
- temp.extend(&block.to_le_bytes());
- }
- serializer.serialize_bytes(&temp)
- }
-}
-
-impl<'de> Deserialize<'de> for FixedBitSet {
- fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
- where
- D: Deserializer<'de>,
- {
- enum Field {
- Length,
- Data,
- }
-
- fn bytes_to_data(length: usize, input: &[u8]) -> Vec<Block> {
- let block_len = length / BYTES + 1;
- let mut data = Vec::with_capacity(block_len);
- for chunk in input.chunks(BYTES) {
- match <&[u8; BYTES]>::try_from(chunk) {
- Ok(bytes) => data.push(usize::from_le_bytes(*bytes)),
- Err(_) => {
- let mut bytes = [0u8; BYTES];
- bytes[0..BYTES].copy_from_slice(chunk);
- data.push(usize::from_le_bytes(bytes));
- }
- }
- }
- data
- }
-
- impl<'de> Deserialize<'de> for Field {
- fn deserialize<D>(deserializer: D) -> Result<Field, D::Error>
- where
- D: Deserializer<'de>,
- {
- struct FieldVisitor;
-
- impl<'de> Visitor<'de> for FieldVisitor {
- type Value = Field;
-
- fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
- formatter.write_str("`length` or `data`")
- }
-
- fn visit_str<E>(self, value: &str) -> Result<Field, E>
- where
- E: de::Error,
- {
- match value {
- "length" => Ok(Field::Length),
- "data" => Ok(Field::Data),
- _ => Err(de::Error::unknown_field(value, FIELDS)),
- }
- }
- }
-
- deserializer.deserialize_identifier(FieldVisitor)
- }
- }
-
- struct FixedBitSetVisitor;
-
- impl<'de> Visitor<'de> for FixedBitSetVisitor {
- type Value = FixedBitSet;
-
- fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
- formatter.write_str("struct Duration")
- }
-
- fn visit_seq<V>(self, mut seq: V) -> Result<FixedBitSet, V::Error>
- where
- V: SeqAccess<'de>,
- {
- let length = seq
- .next_element()?
- .ok_or_else(|| de::Error::invalid_length(0, &self))?;
- let data: &[u8] = seq
- .next_element()?
- .ok_or_else(|| de::Error::invalid_length(1, &self))?;
- let data = bytes_to_data(length, data);
- Ok(FixedBitSet::with_capacity_and_blocks(length, data))
- }
-
- fn visit_map<V>(self, mut map: V) -> Result<FixedBitSet, V::Error>
- where
- V: MapAccess<'de>,
- {
- let mut length = None;
- let mut temp: Option<&[u8]> = None;
- while let Some(key) = map.next_key()? {
- match key {
- Field::Length => {
- if length.is_some() {
- return Err(de::Error::duplicate_field("length"));
- }
- length = Some(map.next_value()?);
- }
- Field::Data => {
- if temp.is_some() {
- return Err(de::Error::duplicate_field("data"));
- }
- temp = Some(map.next_value()?);
- }
- }
- }
- let length = length.ok_or_else(|| de::Error::missing_field("length"))?;
- let data = temp.ok_or_else(|| de::Error::missing_field("data"))?;
- let data = bytes_to_data(length, data);
- Ok(FixedBitSet::with_capacity_and_blocks(length, data))
- }
- }
-
- const FIELDS: &'static [&'static str] = &["length", "data"];
- deserializer.deserialize_struct("Duration", FIELDS, FixedBitSetVisitor)
- }
-}
diff --git a/vendor/fixedbitset/tests/tests.rs b/vendor/fixedbitset/tests/tests.rs
deleted file mode 100644
index fcc334df..00000000
--- a/vendor/fixedbitset/tests/tests.rs
+++ /dev/null
@@ -1,1313 +0,0 @@
-use fixedbitset::*;
-
-#[cfg(target_family = "wasm")]
-use wasm_bindgen_test::*;
-#[cfg(target_family = "wasm")]
-wasm_bindgen_test::wasm_bindgen_test_configure!(run_in_browser);
-
-extern crate alloc;
-
-const BITS: usize = core::mem::size_of::<Block>() * 8;
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn it_works() {
- const N: usize = 50;
- let mut fb = FixedBitSet::with_capacity(N);
-
- for i in 0..(N + 10) {
- assert_eq!(fb.contains(i), false);
- }
-
- fb.insert(10);
- fb.set(11, false);
- fb.set(12, false);
- fb.set(12, true);
- fb.set(N - 1, true);
-
- assert!(fb.contains(10));
- assert!(!fb.contains(11));
- assert!(fb.contains(12));
- assert!(fb.contains(N - 1));
- for i in 0..N {
- let contain = i == 10 || i == 12 || i == N - 1;
- assert_eq!(contain, fb[i]);
- }
-
- fb.clear();
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn with_blocks() {
- let fb = FixedBitSet::with_capacity_and_blocks(50, vec![8, 0]);
- assert!(fb.contains(3));
-
- let ones: Vec<_> = fb.ones().collect();
- assert_eq!(ones.len(), 1);
-
- let ones: Vec<_> = fb.ones().rev().collect();
- assert_eq!(ones.len(), 1);
-
- let ones: Vec<_> = fb.ones().rev().alternate().collect();
- assert_eq!(ones.len(), 1);
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn with_blocks_too_small() {
- let mut fb = FixedBitSet::with_capacity_and_blocks(500, vec![8, 0]);
- fb.insert(400);
- assert!(fb.contains(400));
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn with_blocks_too_big() {
- let fb = FixedBitSet::with_capacity_and_blocks(1, vec![8]);
-
- // since capacity is 1, 3 shouldn't be set here
- assert!(!fb.contains(3));
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn with_blocks_too_big_range_check() {
- let fb = FixedBitSet::with_capacity_and_blocks(1, vec![0xff]);
-
- // since capacity is 1, only 0 should be set
- assert!(fb.contains(0));
- for i in 1..0xff {
- assert!(!fb.contains(i));
- }
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn grow() {
- let mut fb = FixedBitSet::with_capacity(48);
- for i in 0..fb.len() {
- fb.set(i, true);
- }
-
- let old_len = fb.len();
- fb.grow(72);
- for j in 0..fb.len() {
- assert_eq!(fb.contains(j), j < old_len);
- }
- fb.set(64, true);
- assert!(fb.contains(64));
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn grow_and_insert() {
- let mut fb = FixedBitSet::default();
- for i in 0..100 {
- if i % 3 == 0 {
- fb.grow_and_insert(i);
- }
- }
-
- assert_eq!(fb.count_ones(..), 34);
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn test_toggle() {
- let mut fb = FixedBitSet::with_capacity(16);
- fb.toggle(1);
- fb.put(2);
- fb.toggle(2);
- fb.put(3);
- assert!(fb.contains(1));
- assert!(!fb.contains(2));
- assert!(fb.contains(3));
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn copy_bit() {
- let mut fb = FixedBitSet::with_capacity(48);
- for i in 0..fb.len() {
- fb.set(i, true);
- }
- fb.set(42, false);
- fb.copy_bit(42, 2);
- assert!(!fb.contains(42));
- assert!(!fb.contains(2));
- assert!(fb.contains(1));
- fb.copy_bit(1, 42);
- assert!(fb.contains(42));
- fb.copy_bit(1024, 42);
- assert!(!fb[42]);
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn count_ones() {
- let mut fb = FixedBitSet::with_capacity(100);
- fb.set(11, true);
- fb.set(12, true);
- fb.set(7, true);
- fb.set(35, true);
- fb.set(40, true);
- fb.set(77, true);
- fb.set(95, true);
- fb.set(50, true);
- fb.set(99, true);
- assert_eq!(fb.count_ones(..7), 0);
- assert_eq!(fb.count_ones(..8), 1);
- assert_eq!(fb.count_ones(..11), 1);
- assert_eq!(fb.count_ones(..12), 2);
- assert_eq!(fb.count_ones(..13), 3);
- assert_eq!(fb.count_ones(..35), 3);
- assert_eq!(fb.count_ones(..36), 4);
- assert_eq!(fb.count_ones(..40), 4);
- assert_eq!(fb.count_ones(..41), 5);
- assert_eq!(fb.count_ones(50..), 4);
- assert_eq!(fb.count_ones(70..95), 1);
- assert_eq!(fb.count_ones(70..96), 2);
- assert_eq!(fb.count_ones(70..99), 2);
- assert_eq!(fb.count_ones(..), 9);
- assert_eq!(fb.count_ones(0..100), 9);
- assert_eq!(fb.count_ones(0..0), 0);
- assert_eq!(fb.count_ones(100..100), 0);
- assert_eq!(fb.count_ones(7..), 9);
- assert_eq!(fb.count_ones(8..), 8);
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn count_zeroes() {
- let mut fb = FixedBitSet::with_capacity(100);
- fb.set(11, true);
- fb.set(12, true);
- fb.set(7, true);
- fb.set(35, true);
- fb.set(40, true);
- fb.set(77, true);
- fb.set(95, true);
- fb.set(50, true);
- fb.set(99, true);
- assert_eq!(fb.count_zeroes(..7), 7);
- assert_eq!(fb.count_zeroes(..8), 7);
- assert_eq!(fb.count_zeroes(..11), 10);
- assert_eq!(fb.count_zeroes(..12), 10);
- assert_eq!(fb.count_zeroes(..13), 10);
- assert_eq!(fb.count_zeroes(..35), 32);
- assert_eq!(fb.count_zeroes(..36), 32);
- assert_eq!(fb.count_zeroes(..40), 36);
- assert_eq!(fb.count_zeroes(..41), 36);
- assert_eq!(fb.count_zeroes(50..), 46);
- assert_eq!(fb.count_zeroes(70..95), 24);
- assert_eq!(fb.count_zeroes(70..96), 24);
- assert_eq!(fb.count_zeroes(70..99), 27);
- assert_eq!(fb.count_zeroes(..), 91);
- assert_eq!(fb.count_zeroes(0..100), 91);
- assert_eq!(fb.count_zeroes(0..0), 0);
- assert_eq!(fb.count_zeroes(100..100), 0);
- assert_eq!(fb.count_zeroes(7..), 84);
- assert_eq!(fb.count_zeroes(8..), 84);
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn minimum() {
- let mut fb = FixedBitSet::with_capacity(100);
- assert_eq!(fb.minimum(), None);
- fb.set(95, true);
- assert_eq!(fb.minimum(), Some(95));
- fb.set(77, true);
- assert_eq!(fb.minimum(), Some(77));
- fb.set(12, true);
- assert_eq!(fb.minimum(), Some(12));
- fb.set(40, true);
- assert_eq!(fb.minimum(), Some(12));
- fb.set(35, true);
- assert_eq!(fb.minimum(), Some(12));
- fb.set(11, true);
- assert_eq!(fb.minimum(), Some(11));
- fb.set(7, true);
- assert_eq!(fb.minimum(), Some(7));
- fb.set(50, true);
- assert_eq!(fb.minimum(), Some(7));
- fb.set(99, true);
- assert_eq!(fb.minimum(), Some(7));
- fb.clear();
- assert_eq!(fb.minimum(), None);
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn maximum() {
- let mut fb = FixedBitSet::with_capacity(100);
- assert_eq!(fb.maximum(), None);
- fb.set(11, true);
- assert_eq!(fb.maximum(), Some(11));
- fb.set(12, true);
- assert_eq!(fb.maximum(), Some(12));
- fb.set(7, true);
- assert_eq!(fb.maximum(), Some(12));
- fb.set(40, true);
- assert_eq!(fb.maximum(), Some(40));
- fb.set(35, true);
- assert_eq!(fb.maximum(), Some(40));
- fb.set(95, true);
- assert_eq!(fb.maximum(), Some(95));
- fb.set(50, true);
- assert_eq!(fb.maximum(), Some(95));
- fb.set(77, true);
- assert_eq!(fb.maximum(), Some(95));
- fb.set(99, true);
- assert_eq!(fb.maximum(), Some(99));
- fb.clear();
- assert_eq!(fb.maximum(), None);
-}
-
-/* Helper for testing double ended iterator */
-#[cfg(test)]
-struct Alternating<I> {
- iter: I,
- front: bool,
-}
-
-#[cfg(test)]
-impl<I: Iterator + DoubleEndedIterator> Iterator for Alternating<I> {
- type Item = I::Item;
-
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.iter.size_hint()
- }
- fn next(&mut self) -> Option<Self::Item> {
- if self.front {
- self.front = false;
- self.iter.next()
- } else {
- self.front = true;
- self.iter.next_back()
- }
- }
-}
-#[cfg(test)]
-trait AlternatingExt: Iterator + DoubleEndedIterator + Sized {
- fn alternate(self) -> Alternating<Self> {
- Alternating {
- iter: self,
- front: true,
- }
- }
-}
-
-#[cfg(test)]
-impl<I: Iterator + DoubleEndedIterator> AlternatingExt for I {}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn ones() {
- let mut fb = FixedBitSet::with_capacity(100);
- fb.set(11, true);
- fb.set(12, true);
- fb.set(7, true);
- fb.set(35, true);
- fb.set(40, true);
- fb.set(77, true);
- fb.set(95, true);
- fb.set(50, true);
- fb.set(99, true);
-
- let ones: Vec<_> = fb.ones().collect();
- let ones_rev: Vec<_> = fb.ones().rev().collect();
- let ones_alternating: Vec<_> = fb.ones().alternate().collect();
-
- let mut known_result = vec![7, 11, 12, 35, 40, 50, 77, 95, 99];
-
- assert_eq!(known_result, ones);
- known_result.reverse();
- assert_eq!(known_result, ones_rev);
- let known_result: Vec<_> = known_result.into_iter().rev().alternate().collect();
- assert_eq!(known_result, ones_alternating);
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn into_ones() {
- fn create() -> FixedBitSet {
- let mut fb = FixedBitSet::with_capacity(100);
- fb.set(11, true);
- fb.set(12, true);
- fb.set(7, true);
- fb.set(35, true);
- fb.set(40, true);
- fb.set(77, true);
- fb.set(95, true);
- fb.set(50, true);
- fb.set(99, true);
- fb
- }
-
- let ones: Vec<_> = create().into_ones().collect();
- let ones_rev: Vec<_> = create().into_ones().rev().collect();
- let ones_alternating: Vec<_> = create().into_ones().alternate().collect();
-
- let mut known_result = vec![7, 11, 12, 35, 40, 50, 77, 95, 99];
-
- assert_eq!(known_result, ones);
- known_result.reverse();
- assert_eq!(known_result, ones_rev);
- let known_result: Vec<_> = known_result.into_iter().rev().alternate().collect();
- assert_eq!(known_result, ones_alternating);
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn size_hint() {
- let iters = if cfg!(miri) { 250 } else { 1000 };
- for s in 0..iters {
- let mut bitset = FixedBitSet::with_capacity(s);
- bitset.insert_range(..);
- let mut t = s;
- let mut iter = bitset.ones().rev();
- loop {
- match iter.next() {
- None => break,
- Some(_) => {
- t -= 1;
- assert!(iter.size_hint().1.unwrap() >= t);
- // factor two, because we have first block and last block
- assert!(iter.size_hint().1.unwrap() <= t + 2 * BITS);
- }
- }
- }
- assert_eq!(t, 0);
- }
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn size_hint_alternate() {
- let iters = if cfg!(miri) { 250 } else { 1000 };
- for s in 0..iters {
- let mut bitset = FixedBitSet::with_capacity(s);
- bitset.insert_range(..);
- let mut t = s;
- extern crate std;
- let mut iter = bitset.ones().alternate();
- loop {
- match iter.next() {
- None => break,
- Some(_) => {
- t -= 1;
- assert!(iter.size_hint().1.unwrap() >= t);
- assert!(iter.size_hint().1.unwrap() <= t + 3 * BITS);
- }
- }
- }
- assert_eq!(t, 0);
- }
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn iter_ones_range() {
- fn test_range(from: usize, to: usize, capa: usize) {
- assert!(to <= capa);
- let mut fb = FixedBitSet::with_capacity(capa);
- for i in from..to {
- fb.insert(i);
- }
- let ones: Vec<_> = fb.ones().collect();
- let expected: Vec<_> = (from..to).collect();
- let ones_rev: Vec<_> = fb.ones().rev().collect();
- let expected_rev: Vec<_> = (from..to).rev().collect();
- let ones_rev_alt: Vec<_> = fb.ones().rev().alternate().collect();
- let expected_rev_alt: Vec<_> = (from..to).rev().alternate().collect();
- assert_eq!(expected, ones);
- assert_eq!(expected_rev, ones_rev);
- assert_eq!(expected_rev_alt, ones_rev_alt);
- }
-
- for i in 0..100 {
- test_range(i, 100, 100);
- test_range(0, i, 100);
- }
-}
-
-#[should_panic]
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn count_ones_oob() {
- let fb = FixedBitSet::with_capacity(100);
- fb.count_ones(90..101);
-}
-
-#[should_panic]
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn count_ones_negative_range() {
- let fb = FixedBitSet::with_capacity(100);
- fb.count_ones(90..80);
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn count_ones_panic() {
- let iters = if cfg!(miri) { 48 } else { 128 };
- for i in 1..iters {
- let fb = FixedBitSet::with_capacity(i);
- for j in 0..fb.len() + 1 {
- for k in j..fb.len() + 1 {
- assert_eq!(fb.count_ones(j..k), 0);
- }
- }
- }
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn default() {
- let fb = FixedBitSet::default();
- assert_eq!(fb.len(), 0);
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn insert_range() {
- let mut fb = FixedBitSet::with_capacity(97);
- fb.insert_range(..3);
- fb.insert_range(9..32);
- fb.insert_range(37..81);
- fb.insert_range(90..);
- for i in 0..97 {
- assert_eq!(
- fb.contains(i),
- i < 3 || 9 <= i && i < 32 || 37 <= i && i < 81 || 90 <= i
- );
- }
- assert!(!fb.contains(97));
- assert!(!fb.contains(127));
- assert!(!fb.contains(128));
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn contains_all_in_range() {
- let mut fb = FixedBitSet::with_capacity(48);
- fb.insert_range(..);
-
- fb.remove_range(..32);
- fb.remove_range(37..);
-
- assert!(fb.contains_all_in_range(32..37));
- assert!(fb.contains_all_in_range(32..35));
- assert!(!fb.contains_all_in_range(32..));
- assert!(!fb.contains_all_in_range(..37));
- assert!(!fb.contains_all_in_range(..));
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn contains_any_in_range() {
- let mut fb = FixedBitSet::with_capacity(48);
- fb.insert_range(..);
-
- fb.remove_range(..32);
- fb.remove_range(37..);
-
- assert!(!fb.contains_any_in_range(..32));
- assert!(fb.contains_any_in_range(32..37));
- assert!(fb.contains_any_in_range(32..35));
- assert!(fb.contains_any_in_range(32..));
- assert!(fb.contains_any_in_range(..37));
- assert!(!fb.contains_any_in_range(37..));
- assert!(fb.contains_any_in_range(..));
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn remove_range() {
- let mut fb = FixedBitSet::with_capacity(48);
- fb.insert_range(..);
-
- fb.remove_range(..32);
- fb.remove_range(37..);
-
- for i in 0..48 {
- assert_eq!(fb.contains(i), 32 <= i && i < 37);
- }
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn set_range() {
- let mut fb = FixedBitSet::with_capacity(48);
- fb.insert_range(..);
-
- fb.set_range(..32, false);
- fb.set_range(37.., false);
- fb.set_range(5..9, true);
- fb.set_range(40..40, true);
-
- for i in 0..48 {
- assert_eq!(fb.contains(i), 5 <= i && i < 9 || 32 <= i && i < 37);
- }
- assert!(!fb.contains(48));
- assert!(!fb.contains(64));
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn toggle_range() {
- let mut fb = FixedBitSet::with_capacity(40);
- fb.insert_range(..10);
- fb.insert_range(34..38);
-
- fb.toggle_range(5..12);
- fb.toggle_range(30..);
-
- for i in 0..40 {
- assert_eq!(
- fb.contains(i),
- i < 5 || 10 <= i && i < 12 || 30 <= i && i < 34 || 38 <= i
- );
- }
- assert!(!fb.contains(40));
- assert!(!fb.contains(64));
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn bitand_equal_lengths() {
- let len = 109;
- let a_end = 59;
- let b_start = 23;
- let mut a = FixedBitSet::with_capacity(len);
- let mut b = FixedBitSet::with_capacity(len);
- a.set_range(..a_end, true);
- b.set_range(b_start.., true);
- let ab = &a & &b;
- for i in 0..b_start {
- assert!(!ab.contains(i));
- }
- for i in b_start..a_end {
- assert!(ab.contains(i));
- }
- for i in a_end..len {
- assert!(!ab.contains(i));
- }
- assert_eq!(a.len(), ab.len());
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn bitand_first_smaller() {
- let a_len = 113;
- let b_len = 137;
- let len = core::cmp::min(a_len, b_len);
- let a_end = 97;
- let b_start = 89;
- let mut a = FixedBitSet::with_capacity(a_len);
- let mut b = FixedBitSet::with_capacity(b_len);
- a.set_range(..a_end, true);
- b.set_range(b_start.., true);
- let ab = &a & &b;
- for i in 0..b_start {
- assert!(!ab.contains(i));
- }
- for i in b_start..a_end {
- assert!(ab.contains(i));
- }
- for i in a_end..len {
- assert!(!ab.contains(i));
- }
- assert_eq!(a.len(), ab.len());
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn bitand_first_larger() {
- let a_len = 173;
- let b_len = 137;
- let len = core::cmp::min(a_len, b_len);
- let a_end = 107;
- let b_start = 43;
- let mut a = FixedBitSet::with_capacity(a_len);
- let mut b = FixedBitSet::with_capacity(b_len);
- a.set_range(..a_end, true);
- b.set_range(b_start.., true);
- let ab = &a & &b;
- for i in 0..b_start {
- assert!(!ab.contains(i));
- }
- for i in b_start..a_end {
- assert!(ab.contains(i));
- }
- for i in a_end..len {
- assert!(!ab.contains(i));
- }
- assert_eq!(b.len(), ab.len());
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn intersection() {
- let len = 109;
- let a_end = 59;
- let b_start = 23;
- let mut a = FixedBitSet::with_capacity(len);
- let mut b = FixedBitSet::with_capacity(len);
- a.set_range(..a_end, true);
- b.set_range(b_start.., true);
- let count = a.intersection_count(&b);
- let iterator_count = a.intersection(&b).count();
- let mut ab = a.intersection(&b).collect::<FixedBitSet>();
-
- for i in 0..b_start {
- assert!(!ab.contains(i));
- }
- for i in b_start..a_end {
- assert!(ab.contains(i));
- }
- for i in a_end..len {
- assert!(!ab.contains(i));
- }
-
- a.intersect_with(&b);
- // intersection + collect produces the same results but with a shorter length.
- ab.grow(a.len());
- assert_eq!(
- ab, a,
- "intersection and intersect_with produce the same results"
- );
- assert_eq!(
- ab.count_ones(..),
- count,
- "intersection and intersection_count produce the same results"
- );
- assert_eq!(
- count, iterator_count,
- "intersection and intersection_count produce the same results"
- );
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn union() {
- let a_len = 173;
- let b_len = 137;
- let a_start = 139;
- let b_end = 107;
- let mut a = FixedBitSet::with_capacity(a_len);
- let mut b = FixedBitSet::with_capacity(b_len);
- a.set_range(a_start.., true);
- b.set_range(..b_end, true);
- let count = a.union_count(&b);
- let iterator_count = a.union(&b).count();
- let ab = a.union(&b).collect::<FixedBitSet>();
- for i in a_start..a_len {
- assert!(ab.contains(i));
- }
- for i in 0..b_end {
- assert!(ab.contains(i));
- }
- for i in b_end..a_start {
- assert!(!ab.contains(i));
- }
-
- a.union_with(&b);
- assert_eq!(ab, a, "union and union_with produce the same results");
- assert_eq!(
- count,
- ab.count_ones(..),
- "union and union_count produce the same results"
- );
- assert_eq!(
- count, iterator_count,
- "union and union_count produce the same results"
- );
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn difference() {
- let a_len = 83;
- let b_len = 151;
- let a_start = 0;
- let a_end = 79;
- let b_start = 53;
- let mut a = FixedBitSet::with_capacity(a_len);
- let mut b = FixedBitSet::with_capacity(b_len);
- a.set_range(a_start..a_end, true);
- b.set_range(b_start..b_len, true);
- let count = a.difference_count(&b);
- let iterator_count = a.difference(&b).count();
- let mut a_diff_b = a.difference(&b).collect::<FixedBitSet>();
- for i in a_start..b_start {
- assert!(a_diff_b.contains(i));
- }
- for i in b_start..b_len {
- assert!(!a_diff_b.contains(i));
- }
-
- a.difference_with(&b);
- // difference + collect produces the same results but with a shorter length.
- a_diff_b.grow(a.len());
- assert_eq!(
- a_diff_b, a,
- "difference and difference_with produce the same results"
- );
- assert_eq!(
- a_diff_b.count_ones(..),
- count,
- "difference and difference_count produce the same results"
- );
- assert_eq!(
- count, iterator_count,
- "intersection and intersection_count produce the same results"
- );
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn symmetric_difference() {
- let a_len = 83;
- let b_len = 151;
- let a_start = 47;
- let a_end = 79;
- let b_start = 53;
- let mut a = FixedBitSet::with_capacity(a_len);
- let mut b = FixedBitSet::with_capacity(b_len);
- a.set_range(a_start..a_end, true);
- b.set_range(b_start..b_len, true);
- let count = a.symmetric_difference_count(&b);
- let iterator_count = a.symmetric_difference(&b).count();
- let a_sym_diff_b = a.symmetric_difference(&b).collect::<FixedBitSet>();
- for i in 0..a_start {
- assert!(!a_sym_diff_b.contains(i));
- }
- for i in a_start..b_start {
- assert!(a_sym_diff_b.contains(i));
- }
- for i in b_start..a_end {
- assert!(!a_sym_diff_b.contains(i));
- }
- for i in a_end..b_len {
- assert!(a_sym_diff_b.contains(i));
- }
-
- a.symmetric_difference_with(&b);
- assert_eq!(
- a_sym_diff_b, a,
- "symmetric_difference and _with produce the same results"
- );
- assert_eq!(
- a_sym_diff_b.count_ones(..),
- count,
- "symmetric_difference and _count produce the same results"
- );
- assert_eq!(
- count, iterator_count,
- "symmetric_difference and _count produce the same results"
- );
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn bitor_equal_lengths() {
- let len = 109;
- let a_start = 17;
- let a_end = 23;
- let b_start = 19;
- let b_end = 59;
- let mut a = FixedBitSet::with_capacity(len);
- let mut b = FixedBitSet::with_capacity(len);
- a.set_range(a_start..a_end, true);
- b.set_range(b_start..b_end, true);
- let ab = &a | &b;
- for i in 0..a_start {
- assert!(!ab.contains(i));
- }
- for i in a_start..b_end {
- assert!(ab.contains(i));
- }
- for i in b_end..len {
- assert!(!ab.contains(i));
- }
- assert_eq!(ab.len(), len);
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn bitor_first_smaller() {
- let a_len = 113;
- let b_len = 137;
- let a_end = 89;
- let b_start = 97;
- let mut a = FixedBitSet::with_capacity(a_len);
- let mut b = FixedBitSet::with_capacity(b_len);
- a.set_range(..a_end, true);
- b.set_range(b_start.., true);
- let ab = &a | &b;
- for i in 0..a_end {
- assert!(ab.contains(i));
- }
- for i in a_end..b_start {
- assert!(!ab.contains(i));
- }
- for i in b_start..b_len {
- assert!(ab.contains(i));
- }
- assert_eq!(b_len, ab.len());
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn bitor_first_larger() {
- let a_len = 173;
- let b_len = 137;
- let a_start = 139;
- let b_end = 107;
- let mut a = FixedBitSet::with_capacity(a_len);
- let mut b = FixedBitSet::with_capacity(b_len);
- a.set_range(a_start.., true);
- b.set_range(..b_end, true);
- let ab = &a | &b;
- for i in a_start..a_len {
- assert!(ab.contains(i));
- }
- for i in 0..b_end {
- assert!(ab.contains(i));
- }
- for i in b_end..a_start {
- assert!(!ab.contains(i));
- }
- assert_eq!(a_len, ab.len());
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn bitxor_equal_lengths() {
- let len = 109;
- let a_end = 59;
- let b_start = 23;
- let mut a = FixedBitSet::with_capacity(len);
- let mut b = FixedBitSet::with_capacity(len);
- a.set_range(..a_end, true);
- b.set_range(b_start.., true);
- let ab = &a ^ &b;
- for i in 0..b_start {
- assert!(ab.contains(i));
- }
- for i in b_start..a_end {
- assert!(!ab.contains(i));
- }
- for i in a_end..len {
- assert!(ab.contains(i));
- }
- assert_eq!(a.len(), ab.len());
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn bitxor_first_smaller() {
- let a_len = 113;
- let b_len = 137;
- let len = core::cmp::max(a_len, b_len);
- let a_end = 97;
- let b_start = 89;
- let mut a = FixedBitSet::with_capacity(a_len);
- let mut b = FixedBitSet::with_capacity(b_len);
- a.set_range(..a_end, true);
- b.set_range(b_start.., true);
- let ab = &a ^ &b;
- for i in 0..b_start {
- assert!(ab.contains(i));
- }
- for i in b_start..a_end {
- assert!(!ab.contains(i));
- }
- for i in a_end..len {
- assert!(ab.contains(i));
- }
- assert_eq!(b.len(), ab.len());
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn bitxor_first_larger() {
- let a_len = 173;
- let b_len = 137;
- let len = core::cmp::max(a_len, b_len);
- let a_end = 107;
- let b_start = 43;
- let mut a = FixedBitSet::with_capacity(a_len);
- let mut b = FixedBitSet::with_capacity(b_len);
- a.set_range(..a_end, true);
- b.set_range(b_start.., true);
- let ab = &a ^ &b;
- for i in 0..b_start {
- assert!(ab.contains(i));
- }
- for i in b_start..a_end {
- assert!(!ab.contains(i));
- }
- for i in a_end..b_len {
- assert!(ab.contains(i));
- }
- for i in b_len..len {
- assert!(!ab.contains(i));
- }
- assert_eq!(a.len(), ab.len());
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn bitand_assign_shorter() {
- let a_ones: Vec<usize> = vec![2, 3, 7, 19, 31, 32, 37, 41, 43, 47, 71, 73, 101];
- let b_ones: Vec<usize> = vec![2, 7, 8, 11, 23, 31, 32];
- let a_and_b: Vec<usize> = vec![2, 7, 31, 32];
- let mut a = a_ones.iter().cloned().collect::<FixedBitSet>();
- let b = b_ones.iter().cloned().collect::<FixedBitSet>();
- a &= b;
- let res = a.ones().collect::<Vec<usize>>();
-
- assert!(res == a_and_b);
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn bitand_assign_longer() {
- let a_ones: Vec<usize> = vec![2, 7, 8, 11, 23, 31, 32];
- let b_ones: Vec<usize> = vec![2, 3, 7, 19, 31, 32, 37, 41, 43, 47, 71, 73, 101];
- let a_and_b: Vec<usize> = vec![2, 7, 31, 32];
- let mut a = a_ones.iter().cloned().collect::<FixedBitSet>();
- let b = b_ones.iter().cloned().collect::<FixedBitSet>();
- a &= b;
- let res = a.ones().collect::<Vec<usize>>();
- assert!(res == a_and_b);
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn bitor_assign_shorter() {
- let a_ones: Vec<usize> = vec![2, 3, 7, 19, 31, 32, 37, 41, 43, 47, 71, 73, 101];
- let b_ones: Vec<usize> = vec![2, 7, 8, 11, 23, 31, 32];
- let a_or_b: Vec<usize> = vec![2, 3, 7, 8, 11, 19, 23, 31, 32, 37, 41, 43, 47, 71, 73, 101];
- let mut a = a_ones.iter().cloned().collect::<FixedBitSet>();
- let b = b_ones.iter().cloned().collect::<FixedBitSet>();
- a |= b;
- let res = a.ones().collect::<Vec<usize>>();
- assert!(res == a_or_b);
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn bitor_assign_longer() {
- let a_ones: Vec<usize> = vec![2, 7, 8, 11, 23, 31, 32];
- let b_ones: Vec<usize> = vec![2, 3, 7, 19, 31, 32, 37, 41, 43, 47, 71, 73, 101];
- let a_or_b: Vec<usize> = vec![2, 3, 7, 8, 11, 19, 23, 31, 32, 37, 41, 43, 47, 71, 73, 101];
- let mut a = a_ones.iter().cloned().collect::<FixedBitSet>();
- let b = b_ones.iter().cloned().collect::<FixedBitSet>();
- a |= b;
- let res = a.ones().collect::<Vec<usize>>();
- assert_eq!(res, a_or_b);
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn bitxor_assign_shorter() {
- let a_ones: Vec<usize> = vec![2, 3, 7, 19, 31, 32, 37, 41, 43, 47, 71, 73, 101];
- let b_ones: Vec<usize> = vec![2, 7, 8, 11, 23, 31, 32];
- let a_xor_b: Vec<usize> = vec![3, 8, 11, 19, 23, 37, 41, 43, 47, 71, 73, 101];
- let mut a = a_ones.iter().cloned().collect::<FixedBitSet>();
- let b = b_ones.iter().cloned().collect::<FixedBitSet>();
- a ^= b;
- let res = a.ones().collect::<Vec<usize>>();
- assert!(res == a_xor_b);
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn bitxor_assign_longer() {
- let a_ones: Vec<usize> = vec![2, 7, 8, 11, 23, 31, 32];
- let b_ones: Vec<usize> = vec![2, 3, 7, 19, 31, 32, 37, 41, 43, 47, 71, 73, 101];
- let a_xor_b: Vec<usize> = vec![3, 8, 11, 19, 23, 37, 41, 43, 47, 71, 73, 101];
- let mut a = a_ones.iter().cloned().collect::<FixedBitSet>();
- let b = b_ones.iter().cloned().collect::<FixedBitSet>();
- a ^= b;
- let res = a.ones().collect::<Vec<usize>>();
- assert!(res == a_xor_b);
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn op_assign_ref() {
- let mut a = FixedBitSet::with_capacity(8);
- let b = FixedBitSet::with_capacity(8);
-
- //check that all assign type operators work on references
- a &= &b;
- a |= &b;
- a ^= &b;
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn subset_superset_shorter() {
- let a_ones: Vec<usize> = vec![7, 31, 32, 63];
- let b_ones: Vec<usize> = vec![2, 7, 19, 31, 32, 37, 41, 43, 47, 63, 73, 101];
- let mut a = a_ones.iter().cloned().collect::<FixedBitSet>();
- let b = b_ones.iter().cloned().collect::<FixedBitSet>();
- assert!(a.is_subset(&b) && b.is_superset(&a));
- a.insert(14);
- assert!(!a.is_subset(&b) && !b.is_superset(&a));
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn subset_superset_longer() {
- let a_len = 153;
- let b_len = 75;
- let a_ones: Vec<usize> = vec![7, 31, 32, 63];
- let b_ones: Vec<usize> = vec![2, 7, 19, 31, 32, 37, 41, 43, 47, 63, 73];
- let mut a = FixedBitSet::with_capacity(a_len);
- let mut b = FixedBitSet::with_capacity(b_len);
- a.extend(a_ones.iter().cloned());
- b.extend(b_ones.iter().cloned());
- assert!(a.is_subset(&b) && b.is_superset(&a));
- a.insert(100);
- assert!(!a.is_subset(&b) && !b.is_superset(&a));
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn is_disjoint_first_shorter() {
- let a_len = 75;
- let b_len = 153;
- let a_ones: Vec<usize> = vec![2, 19, 32, 37, 41, 43, 47, 73];
- let b_ones: Vec<usize> = vec![7, 23, 31, 63, 124];
- let mut a = FixedBitSet::with_capacity(a_len);
- let mut b = FixedBitSet::with_capacity(b_len);
- a.extend(a_ones.iter().cloned());
- b.extend(b_ones.iter().cloned());
- assert!(a.is_disjoint(&b));
- a.insert(63);
- assert!(!a.is_disjoint(&b));
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn is_disjoint_first_longer() {
- let a_ones: Vec<usize> = vec![2, 19, 32, 37, 41, 43, 47, 73, 101];
- let b_ones: Vec<usize> = vec![7, 23, 31, 63];
- let a = a_ones.iter().cloned().collect::<FixedBitSet>();
- let mut b = b_ones.iter().cloned().collect::<FixedBitSet>();
- assert!(a.is_disjoint(&b));
- b.insert(2);
- assert!(!a.is_disjoint(&b));
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn extend_on_empty() {
- let items: Vec<usize> = vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31, 37, 167];
- let mut fbs = FixedBitSet::with_capacity(0);
- fbs.extend(items.iter().cloned());
- let ones = fbs.ones().collect::<Vec<usize>>();
- assert!(ones == items);
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn extend() {
- let items: Vec<usize> = vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31, 37, 167];
- let mut fbs = FixedBitSet::with_capacity(168);
- let new: Vec<usize> = vec![7, 37, 67, 137];
- for i in &new {
- fbs.put(*i);
- }
-
- fbs.extend(items.iter().cloned());
-
- let ones = fbs.ones().collect::<Vec<usize>>();
- let expected = {
- let mut tmp = items.clone();
- tmp.extend(new);
- tmp.sort();
- tmp.dedup();
- tmp
- };
-
- assert_eq!(ones, expected);
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn from_iterator() {
- let items: Vec<usize> = vec![0, 2, 4, 6, 8];
- let fb = items.iter().cloned().collect::<FixedBitSet>();
- for i in items {
- assert!(fb.contains(i));
- }
- for i in vec![1, 3, 5, 7] {
- assert!(!fb.contains(i));
- }
- assert_eq!(fb.len(), 9);
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn from_iterator_ones() {
- let len = 257;
- let mut fb = FixedBitSet::with_capacity(len);
- for i in (0..len).filter(|i| i % 7 == 0) {
- fb.put(i);
- }
- fb.put(len - 1);
- let dup = fb.ones().collect::<FixedBitSet>();
-
- assert_eq!(fb.len(), dup.len());
- assert_eq!(
- fb.ones().collect::<Vec<usize>>(),
- dup.ones().collect::<Vec<usize>>()
- );
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn zeroes() {
- let len = 232;
- let mut fb = FixedBitSet::with_capacity(len);
- for i in (0..len).filter(|i| i % 7 == 0) {
- fb.insert(i);
- }
- let zeroes = fb.zeroes().collect::<Vec<usize>>();
-
- assert_eq!(
- zeroes,
- vec![
- 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27,
- 29, 30, 31, 32, 33, 34, 36, 37, 38, 39, 40, 41, 43, 44, 45, 46, 47, 48, 50, 51, 52, 53,
- 54, 55, 57, 58, 59, 60, 61, 62, 64, 65, 66, 67, 68, 69, 71, 72, 73, 74, 75, 76, 78, 79,
- 80, 81, 82, 83, 85, 86, 87, 88, 89, 90, 92, 93, 94, 95, 96, 97, 99, 100, 101, 102, 103,
- 104, 106, 107, 108, 109, 110, 111, 113, 114, 115, 116, 117, 118, 120, 121, 122, 123,
- 124, 125, 127, 128, 129, 130, 131, 132, 134, 135, 136, 137, 138, 139, 141, 142, 143,
- 144, 145, 146, 148, 149, 150, 151, 152, 153, 155, 156, 157, 158, 159, 160, 162, 163,
- 164, 165, 166, 167, 169, 170, 171, 172, 173, 174, 176, 177, 178, 179, 180, 181, 183,
- 184, 185, 186, 187, 188, 190, 191, 192, 193, 194, 195, 197, 198, 199, 200, 201, 202,
- 204, 205, 206, 207, 208, 209, 211, 212, 213, 214, 215, 216, 218, 219, 220, 221, 222,
- 223, 225, 226, 227, 228, 229, 230
- ]
- );
-}
-
-#[cfg(feature = "std")]
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn binary_trait() {
- let items: Vec<usize> = vec![1, 5, 7, 10, 14, 15];
- let fb = items.iter().cloned().collect::<FixedBitSet>();
-
- assert_eq!(alloc::format!("{:b}", fb), "0100010100100011");
- assert_eq!(alloc::format!("{:#b}", fb), "0b0100010100100011");
-}
-
-#[cfg(feature = "std")]
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn display_trait() {
- let len = 8;
- let mut fb = FixedBitSet::with_capacity(len);
-
- fb.put(4);
- fb.put(2);
-
- assert_eq!(alloc::format!("{}", fb), "00101000");
- assert_eq!(alloc::format!("{:#}", fb), "0b00101000");
-}
-
-// TODO: Rewite this test to be platform agnostic.
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-#[cfg(all(feature = "serde", target_pointer_width = "64"))]
-fn test_serialize() {
- let mut fb = FixedBitSet::with_capacity(10);
- fb.put(2);
- fb.put(3);
- fb.put(6);
- fb.put(8);
- let serialized = serde_json::to_string(&fb).unwrap();
- assert_eq!(r#"{"length":10,"data":[76,1,0,0,0,0,0,0]}"#, serialized);
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn test_is_clear() {
- let mut fb = FixedBitSet::with_capacity(0);
- assert!(fb.is_clear());
-
- fb.grow(1);
- assert!(fb.is_clear());
-
- fb.put(0);
- assert!(!fb.is_clear());
-
- fb.grow(42);
- fb.clear();
- assert!(fb.is_clear());
-
- fb.put(17);
- fb.put(19);
- assert!(!fb.is_clear());
-}
-
-#[test]
-#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
-fn test_is_full() {
- let mut fb = FixedBitSet::with_capacity(0);
- assert!(fb.is_full());
-
- fb.grow(1);
- assert!(!fb.is_full());
-
- fb.put(0);
- assert!(fb.is_full());
-
- fb.grow(42);
- fb.clear();
- assert!(!fb.is_full());
-
- fb.put(17);
- fb.put(19);
- assert!(!fb.is_full());
-
- fb.insert_range(..);
- assert!(fb.is_full());
-}
-
-#[test]
-fn clone() {
- let mut fb = FixedBitSet::with_capacity(10000);
- fb.set(11, true);
- fb.set(12, true);
- fb.set(7, true);
- fb.set(35, true);
- fb.set(40, true);
- fb.set(77, true);
- fb.set(95, true);
- fb.set(50, true);
- fb.set(99, true);
-
- let fb_clone = fb.clone();
- let mut fb_clone_from_smaller = FixedBitSet::with_capacity(1000000);
- let mut fb_clone_from_same = FixedBitSet::with_capacity(10000);
- let mut fb_clone_from_bigger = FixedBitSet::with_capacity(100);
- fb_clone_from_smaller.clone_from(&fb);
- fb_clone_from_same.clone_from(&fb);
- fb_clone_from_bigger.clone_from(&fb);
-
- assert_eq!(&fb, &fb_clone);
- assert_eq!(&fb, &fb_clone_from_smaller);
- assert_eq!(&fb, &fb_clone_from_same);
- assert_eq!(&fb, &fb_clone_from_bigger);
-}
generated by cgit v1.2.3 (git 2.39.1) at 2026-02-02 20:40:18 +0000