Expand description
§index-set
bitset implementation with support for atomic operations
§Why use index-set
?
In our use case, We needed to track the online/offline status of millions of users with minimal memory usage and lightning-fast lookup performance. Our ideal solution required the following:
-
Reuses identifiers when they are removed from the set. When an identifier is removed, it is recycled for future use.
-
Atomic and thread-safe operations.
-
Constant-time performance: Insertion, removal, and lookup operations must all be
O(1)
. -
Compact memory usage, Each identifier is represented by a bit in the memory. For example,
1
megabyte of memory can store8
millions (8,388,608
) unique identifiers. -
Identifiers are unique and as small as possible.
§Example
Add this to your Cargo.toml
file:
[dependencies]
index-set = "0.2"
Here is a simple example of how to use AtomicBitSet
:
use index_set::{AtomicBitSet, slot_count, BitSet, SharedBitSet};
// Create `AtomicBitSet` with memory size of 1 kilobyte
static BIT_SET: AtomicBitSet<{ slot_count::from_kilobytes(1) }> = AtomicBitSet::new();
fn main() {
assert_eq!(BIT_SET.set_next_free_bit(), Some(0));
BIT_SET.insert(2);
assert_eq!(BIT_SET.set_next_free_bit(), Some(1));
BIT_SET.remove(1);
assert_eq!(BIT_SET.set_next_free_bit(), Some(1));
assert_eq!(BIT_SET.size(), 3);
assert_eq!(BIT_SET.capacity(), 8192);
}
Here is basic usage of BitSet
and BitSetMut
traits.
use index_set::{BitSet, BitSetMut};
let mut bitset = [0_u32; 2];
bitset.insert(42);
assert_eq!(bitset.has(42), true);
assert_eq!(bitset.remove(42), Some(true));
assert_eq!(bitset.size(), 0);
assert_eq!(bitset.capacity(), 64);
Here is an example of bitvec, which is Vec<T>
that implements BitSetMut
traits.
use index_set::{BitSet, BitSetMut};
let mut bitvec: Vec<u32> = Vec::new();
BitSetMut::insert(&mut bitvec, 42);
assert_eq!(bitvec.has(42), true);
assert_eq!(BitSetMut::remove(&mut bitvec, 42), Some(true));
assert_eq!(bitvec.size(), 0);
Modules§
- slot_
count - A module that provides functions to calculate the number of slots.
Structs§
- Atomic
BitSet - Same as
[AtomicUsize; N]
, but with an additional functionality.
Traits§
- BitSet
- A trait for reading values from a bit set.
- BitSet
Mut - A trait for a mutate values in a bit set.
- Shared
BitSet - A trait for updating values in a shared bit-set.