ostd/util/
id_set.rs

1// SPDX-License-Identifier: MPL-2.0
2
3//! A fixed-size set of unique IDs.
4//!
5//! This module introduces two abstract data collection types.
6//! The first one is [`IdSet<I>`],
7//! a set that contains at most `I::cardinality()` items,
8//! each of which represents a unique ID of type `I`.
9//! The second one is [`AtomicIdSet<I>`],
10//! the atomic version of `IdSet<I>`.
11//!
12//! The type parameter `I` implements the [`Id`] trait,
13//! which abstracts any ID type whose instances
14//! can be 1:1 mapped to the integers from 0 to `Id::cardinality()` (exclusive).
15//! The ID type is required to implement `Into<u32>` and `TryFrom<u32>`.
16//!
17//! One use case of `IdSet<I>` inside OSTD is
18//! to implement a set of CPU IDs.
19//! [`crate::cpu::CpuSet`] has been simply defined
20//! as a typa alias for `IdSet<CpuId>`.
21
22use core::{
23    fmt::Debug,
24    marker::PhantomData,
25    mem::size_of,
26    ops::{Bound, Range, RangeFrom, RangeFull, RangeTo, RangeToInclusive},
27    sync::atomic::{AtomicU64, Ordering},
28};
29
30use bitvec::{order::Lsb0, view::BitView};
31use smallvec::SmallVec;
32
33use crate::const_assert;
34
35/// A trait to abstract an ID type.
36///
37/// # Safety
38///
39/// There must be a 1:1 mapping between this ID type and
40/// the integers from 0 to `Self::cardinality()` (exclusive).
41/// This implies that the implementation must ensure that
42/// if one invokes `Into::<u32>::into()` for an `Id` value,
43/// then the returned integer always falls within `0..Id::cardinality()`.
44/// Furthermore, the implementation must ensure that
45/// for any `id_value` of type `MyId: Id`,
46/// the following assertion always succeed
47///
48/// ```rust
49/// assert!(id_value == MyId::new(id_value.into()));
50/// ```
51///
52/// There are also constraints on the implementation of `self::cardinality`.
53/// For one thing, the cardinality of the ID type must not change, i.e.,
54/// different calls to `self::cardinality` return the same value.
55/// In addition, the value of a cardinality must be greater than zero.
56pub unsafe trait Id: Copy + Clone + Debug + Eq + Into<u32> + PartialEq {
57    /// Creates an ID instance given a raw ID number.
58    ///
59    /// # Panics
60    ///
61    /// The given number must be less than `Self::cardinality()`.
62    /// Otherwise, this method would panic.
63    fn new(raw_id: u32) -> Self {
64        assert!(raw_id < Self::cardinality());
65        // SAFETY: The raw ID is a valid one.
66        unsafe { Self::new_unchecked(raw_id) }
67    }
68
69    /// Creates an ID instance given a raw ID number.
70    ///
71    /// # Safety
72    ///
73    /// The given number must be less than `Self::cardinality()`.
74    unsafe fn new_unchecked(raw_id: u32) -> Self;
75
76    /// The number of unique IDs representable by this type.
77    fn cardinality() -> u32;
78
79    /// Returns an [`usize`] from the [`Id`]'s corresponding [`u32`].
80    fn as_usize(self) -> usize {
81        Into::<u32>::into(self) as usize
82    }
83}
84
85/// A set of IDs.
86///
87/// # Examples
88///
89/// Assume that you have a type named `MyId`,
90/// which represents a set of IDs from 0 to 10 (exclusive).
91///
92/// ```
93/// #[derive(Copy, Clone, Debug, Eq, PartialEq)]
94/// pub struct MyId(u32);
95///
96/// // SAFETY: `MyId` maintains the 1:1 mapping invariant for 0..10.
97/// unsafe impl Id for MyId {
98///     fn new_unchecked(raw_id: u32) -> Self { Self(raw_id) }
99///     fn cardinality() -> u32 { 10 } // Fixed cardinality for this example
100/// }
101/// impl From<MyId> for u32 { fn from(id: MyId) -> u32 { id.0 } }
102/// ```
103///
104/// Now you can use `IdSet<MyId>` as a container for `MyID`s.
105///
106/// ```
107/// let mut my_id_set: IdSet<MyId> = IdSet::new_empty();
108///
109/// let id0 = MyId::new(0);
110/// my_id_set.add(id0);
111/// assert!(my_id_set.contains(id0));
112/// assert_eq!(my_id_set.count(), 1);
113///
114/// let id5 = MyId::new(5);
115/// my_id_set.add(id5);
116/// assert!(my_id_set.contains(id5));
117/// assert_eq!(my_id_set.count(), 2);
118///
119/// my_id_set.remove(id0);
120/// assert!(!my_id_set.contains(id0));
121/// assert_eq!(my_id_set.count(), 1);
122///
123/// let full_set = IdSet::<MyId>::new_full();
124/// assert_eq!(full_set.count(), 10);
125/// assert!(full_set.contains(MyId::new(9)));
126/// ```
127#[derive(Clone, Debug, Eq, PartialEq)]
128pub struct IdSet<I> {
129    bits: SmallVec<[InnerPart; NR_PARTS_NO_ALLOC]>,
130    phantom: PhantomData<I>,
131}
132
133type InnerPart = u64;
134
135const BITS_PER_PART: usize = InnerPart::BITS as usize;
136const NR_PARTS_NO_ALLOC: usize = 2;
137
138fn part_idx<I: Id>(id: I) -> usize {
139    (id.into() as usize) / BITS_PER_PART
140}
141
142fn bit_idx<I: Id>(id: I) -> usize {
143    (id.into() as usize) % BITS_PER_PART
144}
145
146fn parts_for_ids<I: Id>() -> usize {
147    (I::cardinality() as usize).div_ceil(BITS_PER_PART)
148}
149
150impl<I: Id> IdSet<I> {
151    /// Creates a new `IdSet` with all IDs in the system.
152    pub fn new_full() -> Self {
153        let mut bits = Self::with_bit_pattern(!0);
154        Self::clear_invalid_id_bits(&mut bits);
155        Self {
156            bits,
157            phantom: PhantomData,
158        }
159    }
160
161    /// Creates a new `IdSet` with no IDs in the system.
162    pub fn new_empty() -> Self {
163        let bits = Self::with_bit_pattern(0);
164        Self {
165            bits,
166            phantom: PhantomData,
167        }
168    }
169
170    /// Creates a new bitmap with each of its parts filled with the given bits.
171    ///
172    /// Depending on the bit pattern and the number of IDs,
173    /// the resulting bitmap may end with some invalid bits.
174    fn with_bit_pattern(part_bits: InnerPart) -> SmallVec<[InnerPart; NR_PARTS_NO_ALLOC]> {
175        let num_parts = parts_for_ids::<I>();
176        let mut bits = SmallVec::with_capacity(num_parts);
177        bits.resize(num_parts, part_bits);
178        bits
179    }
180
181    fn clear_invalid_id_bits(bits: &mut SmallVec<[InnerPart; NR_PARTS_NO_ALLOC]>) {
182        let num_ids = I::cardinality() as usize;
183        if !num_ids.is_multiple_of(BITS_PER_PART) {
184            let num_parts = parts_for_ids::<I>();
185            bits[num_parts - 1] &= (1 << (num_ids % BITS_PER_PART)) - 1;
186        }
187    }
188
189    /// Adds an ID to the set.
190    pub fn add(&mut self, id: I) {
191        let part_idx = part_idx(id);
192        let bit_idx = bit_idx(id);
193        if part_idx >= self.bits.len() {
194            self.bits.resize(part_idx + 1, 0);
195        }
196        self.bits[part_idx] |= 1 << bit_idx;
197    }
198
199    /// Removes an ID from the set.
200    pub fn remove(&mut self, id: I) {
201        let part_idx = part_idx(id);
202        let bit_idx = bit_idx(id);
203        if part_idx < self.bits.len() {
204            self.bits[part_idx] &= !(1 << bit_idx);
205        }
206    }
207
208    /// Returns true if the set contains the specified ID.
209    pub fn contains(&self, id: I) -> bool {
210        let part_idx = part_idx(id);
211        let bit_idx = bit_idx(id);
212        part_idx < self.bits.len() && (self.bits[part_idx] & (1 << bit_idx)) != 0
213    }
214
215    /// Returns the number of IDs in the set.
216    pub fn count(&self) -> usize {
217        self.bits
218            .iter()
219            .map(|part| part.count_ones() as usize)
220            .sum()
221    }
222
223    /// Returns true if the set is empty.
224    pub fn is_empty(&self) -> bool {
225        self.bits.iter().all(|part| *part == 0)
226    }
227
228    /// Returns true if the set is full.
229    pub fn is_full(&self) -> bool {
230        let num_ids = I::cardinality() as usize;
231        self.bits.iter().enumerate().all(|(idx, part)| {
232            if idx == self.bits.len() - 1 && !num_ids.is_multiple_of(BITS_PER_PART) {
233                *part == (1 << (num_ids % BITS_PER_PART)) - 1
234            } else {
235                *part == !0
236            }
237        })
238    }
239
240    /// Adds all IDs to the set.
241    pub fn add_all(&mut self) {
242        self.bits.fill(!0);
243        Self::clear_invalid_id_bits(&mut self.bits);
244    }
245
246    /// Removes all IDs from the set.
247    pub fn clear(&mut self) {
248        self.bits.fill(0);
249    }
250
251    /// Iterates over all IDs in the set.
252    ///
253    /// The iteration is guaranteed to be in ascending order.
254    #[inline]
255    pub fn iter(&self) -> impl Iterator<Item = I> + '_ {
256        self.iter_in(..)
257    }
258
259    /// Iterates over the IDs in the set within the specified range.
260    ///
261    /// The iteration is guaranteed to be in ascending order.
262    /// Only IDs that are both in the set and within the specified range will be returned.
263    pub fn iter_in<S: IdSetSlicer<I>>(&self, slicer: S) -> impl Iterator<Item = I> + '_ {
264        let (start, end) = slicer.to_range_bounds();
265
266        self.bits.view_bits::<Lsb0>()[start..end]
267            .iter_ones()
268            .map(move |offset| {
269                // SAFETY: `offset` is relative to the slice `[start..end]`,
270                // therefore `start + offset` is the absolute index of the bit.
271                // Since `offset` only iterates over relative positions of bit 1s, the
272                // resulting absolute index must refer to an active bit in `self.bits`.
273                unsafe { I::new_unchecked((start + offset) as u32) }
274            })
275    }
276}
277
278/// A trait that unifies all types that slice a portion of [`IdSet`].
279pub trait IdSetSlicer<I: Id> {
280    /// Converts the index type to inclusive start and exclusive end bounds.
281    ///
282    /// Returns `(start, end)` where:
283    /// - `start`: inclusive lower bound
284    /// - `end`: exclusive upper bound
285    fn to_range_bounds(self) -> (usize, usize);
286}
287
288// In the following implementations of `IdSetSlicer`, the `Id` values are upcast
289// from `u32` to `usize`. So adding one is guaranteed to *not* overflow.
290impl<I: Id> IdSetSlicer<I> for RangeTo<I> {
291    fn to_range_bounds(self) -> (usize, usize) {
292        (0, self.end.as_usize())
293    }
294}
295impl<I: Id> IdSetSlicer<I> for RangeFrom<I> {
296    fn to_range_bounds(self) -> (usize, usize) {
297        (self.start.as_usize(), I::cardinality() as usize)
298    }
299}
300impl<I: Id> IdSetSlicer<I> for Range<I> {
301    fn to_range_bounds(self) -> (usize, usize) {
302        (self.start.as_usize(), self.end.as_usize())
303    }
304}
305impl<I: Id> IdSetSlicer<I> for RangeFull {
306    fn to_range_bounds(self) -> (usize, usize) {
307        (0, I::cardinality() as usize)
308    }
309}
310impl<I: Id> IdSetSlicer<I> for RangeToInclusive<I> {
311    fn to_range_bounds(self) -> (usize, usize) {
312        (0, self.end.as_usize() + 1)
313    }
314}
315impl<I: Id> IdSetSlicer<I> for (Bound<I>, Bound<I>) {
316    fn to_range_bounds(self) -> (usize, usize) {
317        let (start_bound, end_bound) = self;
318        let start = match start_bound {
319            Bound::Included(id) => id.as_usize(),
320            Bound::Excluded(id) => id.as_usize() + 1,
321            Bound::Unbounded => 0,
322        };
323        let end = match end_bound {
324            Bound::Included(id) => id.as_usize() + 1,
325            Bound::Excluded(id) => id.as_usize(),
326            Bound::Unbounded => I::cardinality() as usize,
327        };
328        (start, end)
329    }
330}
331
332impl<I: Id> From<I> for IdSet<I> {
333    fn from(id: I) -> Self {
334        let mut set = Self::new_empty();
335        set.add(id);
336        set
337    }
338}
339
340impl<I: Id> Default for IdSet<I> {
341    fn default() -> Self {
342        Self::new_empty()
343    }
344}
345
346/// A set of IDs that may be accessed concurrently.
347///
348/// `AtomicIdSet` is backed by an array of `AtomicU64`.
349/// This allows individual ID bits to be added, removed, or tested atomically.
350/// But operations that span multiple `AtomicU64` values are non-atomic.
351#[derive(Debug)]
352pub struct AtomicIdSet<I> {
353    bits: SmallVec<[AtomicInnerPart; NR_PARTS_NO_ALLOC]>,
354    phantom: PhantomData<I>,
355}
356
357type AtomicInnerPart = AtomicU64;
358const_assert!(size_of::<AtomicInnerPart>() == size_of::<InnerPart>());
359
360impl<I: Id> AtomicIdSet<I> {
361    /// Creates a new `AtomicIdSet` from an `IdSet`.
362    pub fn new(value: IdSet<I>) -> Self {
363        let bits = value.bits.into_iter().map(AtomicU64::new).collect();
364        Self {
365            bits,
366            phantom: PhantomData,
367        }
368    }
369
370    /// Loads the value of the set with the given ordering.
371    ///
372    /// This operation is not atomic. When racing with a [`Self::store`]
373    /// operation, this load may return a set that contains a portion of the
374    /// new value and a portion of the old value. Load on each specific
375    /// word is atomic, and follows the specified ordering.
376    ///
377    /// Note that load with [`Ordering::Release`] is a valid operation, which
378    /// is different from the normal atomic operations. When coupled with
379    /// [`Ordering::Release`], it actually performs `fetch_or(0, Release)`.
380    pub fn load(&self, ordering: Ordering) -> IdSet<I> {
381        let bits = self
382            .bits
383            .iter()
384            .map(|part| match ordering {
385                Ordering::Release => part.fetch_or(0, ordering),
386                _ => part.load(ordering),
387            })
388            .collect();
389        IdSet {
390            bits,
391            phantom: PhantomData,
392        }
393    }
394
395    /// Stores a new value to the set with the given ordering.
396    ///
397    /// This operation is not atomic. When racing with a [`Self::load`]
398    /// operation, that load may return a set that contains a portion of the
399    /// new value and a portion of the old value. Load on each specific
400    /// word is atomic, and follows the specified ordering.
401    pub fn store(&self, value: &IdSet<I>, ordering: Ordering) {
402        for (part, new_part) in self.bits.iter().zip(value.bits.iter()) {
403            part.store(*new_part, ordering);
404        }
405    }
406
407    /// Atomically adds an ID with the given ordering.
408    pub fn add(&self, id: I, ordering: Ordering) {
409        let part_idx = part_idx(id);
410        let bit_idx = bit_idx(id);
411        if part_idx < self.bits.len() {
412            self.bits[part_idx].fetch_or(1 << bit_idx, ordering);
413        }
414    }
415
416    /// Atomically removes an ID with the given ordering.
417    pub fn remove(&self, id: I, ordering: Ordering) {
418        let part_idx = part_idx(id);
419        let bit_idx = bit_idx(id);
420        if part_idx < self.bits.len() {
421            self.bits[part_idx].fetch_and(!(1 << bit_idx), ordering);
422        }
423    }
424
425    /// Atomically checks if the set contains the specified ID.
426    pub fn contains(&self, id: I, ordering: Ordering) -> bool {
427        let part_idx = part_idx(id);
428        let bit_idx = bit_idx(id);
429        part_idx < self.bits.len() && (self.bits[part_idx].load(ordering) & (1 << bit_idx)) != 0
430    }
431}
432
433#[cfg(ktest)]
434mod id_set_tests {
435    use alloc::vec;
436
437    use super::*;
438    use crate::prelude::*;
439
440    /// A mock ID type for testing `IdSet`.
441    /// `C` is the cardinality of this ID type.
442    #[derive(Copy, Clone, Debug, Eq, PartialEq)]
443    struct MockId<const C: u32>(u32);
444
445    unsafe impl<const C: u32> Id for MockId<C> {
446        unsafe fn new_unchecked(raw_id: u32) -> Self {
447            MockId(raw_id)
448        }
449
450        fn cardinality() -> u32 {
451            C
452        }
453    }
454
455    impl<const C: u32> From<MockId<C>> for u32 {
456        fn from(id: MockId<C>) -> u32 {
457            id.0
458        }
459    }
460
461    // Test cases for `IdSet` with various cardinalities
462
463    #[ktest]
464    fn id_set_empty() {
465        type TestId = MockId<10>; // Cardinality 10
466        let set: IdSet<TestId> = IdSet::new_empty();
467        assert!(set.is_empty());
468        assert_eq!(set.count(), 0);
469        for i in 0..10 {
470            assert!(!set.contains(TestId::new(i)));
471        }
472    }
473
474    #[ktest]
475    fn id_set_full() {
476        type TestId = MockId<10>; // Cardinality 10
477        let set: IdSet<TestId> = IdSet::new_full();
478        assert!(!set.is_empty());
479        assert_eq!(set.count(), 10);
480        for i in 0..10 {
481            assert!(set.contains(TestId::new(i)));
482        }
483    }
484
485    #[ktest]
486    fn id_set_add_remove() {
487        type TestId = MockId<64>; // Cardinality 64 (one InnerPart)
488        let mut set: IdSet<TestId> = IdSet::new_empty();
489
490        assert!(set.is_empty());
491
492        set.add(TestId::new(0));
493        assert!(set.contains(TestId::new(0)));
494        assert_eq!(set.count(), 1);
495        assert!(!set.is_empty());
496
497        set.add(TestId::new(63));
498        assert!(set.contains(TestId::new(63)));
499        assert_eq!(set.count(), 2);
500
501        set.add(TestId::new(32));
502        assert!(set.contains(TestId::new(32)));
503        assert_eq!(set.count(), 3);
504
505        set.remove(TestId::new(0));
506        assert!(!set.contains(TestId::new(0)));
507        assert_eq!(set.count(), 2);
508
509        set.remove(TestId::new(63));
510        assert!(!set.contains(TestId::new(63)));
511        assert_eq!(set.count(), 1);
512
513        set.remove(TestId::new(32));
514        assert!(!set.contains(TestId::new(32)));
515        assert_eq!(set.count(), 0);
516        assert!(set.is_empty());
517
518        // Removing a non-existent ID should not panic or change the set
519        set.remove(TestId::new(1));
520        assert!(set.is_empty());
521    }
522
523    #[ktest]
524    fn id_set_add_remove_multi_part() {
525        type TestId = MockId<128>; // Cardinality 128 (two InnerParts)
526        let mut set: IdSet<TestId> = IdSet::new_empty();
527
528        set.add(TestId::new(0));
529        set.add(TestId::new(63)); // Last bit of first part
530        set.add(TestId::new(64)); // First bit of second part
531        set.add(TestId::new(127)); // Last bit of second part
532
533        assert_eq!(set.count(), 4);
534        assert!(set.contains(TestId::new(0)));
535        assert!(set.contains(TestId::new(63)));
536        assert!(set.contains(TestId::new(64)));
537        assert!(set.contains(TestId::new(127)));
538
539        set.remove(TestId::new(63));
540        assert!(!set.contains(TestId::new(63)));
541        assert_eq!(set.count(), 3);
542
543        set.remove(TestId::new(64));
544        assert!(!set.contains(TestId::new(64)));
545        assert_eq!(set.count(), 2);
546    }
547
548    #[ktest]
549    fn id_set_add_all_clear() {
550        type TestId = MockId<70>; // Cardinality 70 (spans two parts, second part not full)
551        let mut set: IdSet<TestId> = IdSet::new_empty();
552
553        set.add_all();
554        assert_eq!(set.count(), 70);
555        assert!(set.is_full());
556        for i in 0..70 {
557            assert!(set.contains(TestId::new(i)));
558        }
559
560        set.clear();
561        assert!(set.is_empty());
562        assert_eq!(set.count(), 0);
563        for i in 0..70 {
564            assert!(!set.contains(TestId::new(i)));
565        }
566    }
567
568    #[ktest]
569    fn id_set_iter() {
570        type TestId = MockId<5>; // Cardinality 5
571        let mut set: IdSet<TestId> = IdSet::new_empty();
572
573        set.add(TestId::new(2));
574        set.add(TestId::new(0));
575        set.add(TestId::new(4));
576
577        let collected_ids: Vec<TestId> = set.iter().collect();
578        assert_eq!(
579            collected_ids,
580            vec![TestId::new(0), TestId::new(2), TestId::new(4)]
581        );
582
583        set.clear();
584        let collected_ids: Vec<TestId> = set.iter().collect();
585        assert!(collected_ids.is_empty());
586    }
587
588    #[ktest]
589    fn id_set_iter_full() {
590        type TestId = MockId<3>; // Cardinality 3
591        let set: IdSet<TestId> = IdSet::new_full();
592        let collected_ids: Vec<TestId> = set.iter().collect();
593        assert_eq!(
594            collected_ids,
595            vec![TestId::new(0), TestId::new(1), TestId::new(2)]
596        );
597    }
598
599    #[ktest]
600    fn id_set_iter_multi_part() {
601        type TestId = MockId<100>; // Cardinality 100
602        let mut set: IdSet<TestId> = IdSet::new_empty();
603        set.add(TestId::new(1));
604        set.add(TestId::new(65));
605        set.add(TestId::new(99));
606        set.add(TestId::new(0));
607        set.add(TestId::new(63));
608
609        let collected_ids: Vec<TestId> = set.iter().collect();
610        assert_eq!(
611            collected_ids,
612            vec![
613                TestId::new(0),
614                TestId::new(1),
615                TestId::new(63),
616                TestId::new(65),
617                TestId::new(99)
618            ]
619        );
620    }
621
622    #[ktest]
623    fn id_set_from_id() {
624        type TestId = MockId<10>;
625        let id = TestId::new(5);
626        let set: IdSet<TestId> = id.into();
627        assert_eq!(set.count(), 1);
628        assert!(set.contains(id));
629        assert!(!set.contains(TestId::new(0)));
630    }
631
632    #[ktest]
633    fn id_set_cardinality_one() {
634        type TestId = MockId<1>; // Cardinality 1
635        let mut set: IdSet<TestId> = IdSet::new_empty();
636        assert!(set.is_empty());
637        assert_eq!(set.count(), 0);
638
639        set.add(TestId::new(0));
640        assert!(set.contains(TestId::new(0)));
641        assert_eq!(set.count(), 1);
642        assert!(set.is_full());
643
644        set.remove(TestId::new(0));
645        assert!(!set.contains(TestId::new(0)));
646        assert_eq!(set.count(), 0);
647        assert!(set.is_empty());
648
649        let full_set = IdSet::<TestId>::new_full();
650        assert!(full_set.contains(TestId::new(0)));
651        assert_eq!(full_set.count(), 1);
652    }
653
654    #[ktest]
655    fn id_set_exact_part_boundary() {
656        type TestId = MockId<64>; // Cardinality exactly one full part
657        let mut set: IdSet<TestId> = IdSet::new_empty();
658
659        set.add(TestId::new(0));
660        set.add(TestId::new(63));
661        assert_eq!(set.count(), 2);
662
663        let full_set = IdSet::<TestId>::new_full();
664        assert!(full_set.is_full());
665        assert_eq!(full_set.count(), 64);
666        for i in 0..64 {
667            assert!(full_set.contains(TestId::new(i)));
668        }
669    }
670
671    #[ktest]
672    fn id_set_just_over_part_boundary() {
673        type TestId = MockId<65>; // Cardinality just over one part
674        let mut set: IdSet<TestId> = IdSet::new_empty();
675
676        set.add(TestId::new(0));
677        set.add(TestId::new(63)); // End of first part
678        set.add(TestId::new(64)); // Start of second part
679        assert_eq!(set.count(), 3);
680
681        let full_set = IdSet::<TestId>::new_full();
682        assert!(full_set.is_full());
683        assert_eq!(full_set.count(), 65);
684        for i in 0..65 {
685            assert!(full_set.contains(TestId::new(i)));
686        }
687    }
688
689    #[ktest]
690    fn id_set_is_full_with_less_than_full_last_part() {
691        type TestId = MockId<70>; // Cardinality 70 (64 in first part, 6 in second)
692        let mut set: IdSet<TestId> = IdSet::new_full();
693
694        assert!(set.is_full());
695        assert_eq!(set.count(), 70);
696
697        // Remove one ID from the last part
698        set.remove(TestId::new(69));
699        assert!(!set.is_full());
700        assert_eq!(set.count(), 69);
701
702        // Add it back
703        set.add(TestId::new(69));
704        assert!(set.is_full());
705        assert_eq!(set.count(), 70);
706    }
707
708    #[ktest]
709    fn id_set_default() {
710        type TestId = MockId<10>;
711        let set: IdSet<TestId> = Default::default();
712        assert!(set.is_empty());
713        assert_eq!(set.count(), 0);
714    }
715
716    #[ktest]
717    fn iter_in_range() {
718        type TestId = MockId<7>;
719        let mut set: IdSet<TestId> = IdSet::new_empty();
720        set.add(TestId::new(0));
721        set.add(TestId::new(1));
722        set.add(TestId::new(2));
723        set.add(TestId::new(5));
724        set.add(TestId::new(6));
725
726        let collected_ids: Vec<TestId> = set.iter_in(TestId::new(1)..TestId::new(5)).collect();
727        assert_eq!(collected_ids, vec![TestId::new(1), TestId::new(2)],);
728    }
729
730    #[ktest]
731    fn iter_in_range_to() {
732        type TestId = MockId<7>;
733        let mut set: IdSet<TestId> = IdSet::new_empty();
734        set.add(TestId::new(0));
735        set.add(TestId::new(1));
736        set.add(TestId::new(2));
737        set.add(TestId::new(5));
738        set.add(TestId::new(6));
739
740        let collected_ids: Vec<TestId> = set.iter_in(..TestId::new(5)).collect();
741        assert_eq!(
742            collected_ids,
743            vec![TestId::new(0), TestId::new(1), TestId::new(2)],
744        );
745    }
746
747    #[ktest]
748    fn iter_in_range_to_inclusive() {
749        type TestId = MockId<7>;
750        let mut set: IdSet<TestId> = IdSet::new_empty();
751        set.add(TestId::new(0));
752        set.add(TestId::new(1));
753        set.add(TestId::new(2));
754        set.add(TestId::new(5));
755        set.add(TestId::new(6));
756
757        let collected_ids: Vec<TestId> = set.iter_in(..=TestId::new(5)).collect();
758        assert_eq!(
759            collected_ids,
760            vec![
761                TestId::new(0),
762                TestId::new(1),
763                TestId::new(2),
764                TestId::new(5)
765            ],
766        );
767    }
768
769    #[ktest]
770    fn iter_in_range_from() {
771        type TestId = MockId<7>;
772        let mut set: IdSet<TestId> = IdSet::new_empty();
773        set.add(TestId::new(0));
774        set.add(TestId::new(1));
775        set.add(TestId::new(2));
776        set.add(TestId::new(5));
777        set.add(TestId::new(6));
778
779        let collected_ids: Vec<TestId> = set.iter_in(TestId::new(2)..).collect();
780        assert_eq!(
781            collected_ids,
782            vec![TestId::new(2), TestId::new(5), TestId::new(6)],
783        );
784    }
785
786    #[ktest]
787    fn iter_in_range_full() {
788        type TestId = MockId<7>;
789        let mut set: IdSet<TestId> = IdSet::new_empty();
790        set.add(TestId::new(0));
791        set.add(TestId::new(1));
792        set.add(TestId::new(2));
793        set.add(TestId::new(5));
794        set.add(TestId::new(6));
795
796        let collected_ids: Vec<TestId> = set.iter_in(..).collect();
797        assert_eq!(
798            collected_ids,
799            vec![
800                TestId::new(0),
801                TestId::new(1),
802                TestId::new(2),
803                TestId::new(5),
804                TestId::new(6)
805            ],
806        );
807    }
808
809    #[ktest]
810    fn iter_in_bound_tuple_inclusive_exclusive() {
811        type TestId = MockId<7>;
812        let mut set: IdSet<TestId> = IdSet::new_empty();
813        set.add(TestId::new(0));
814        set.add(TestId::new(1));
815        set.add(TestId::new(2));
816        set.add(TestId::new(5));
817        set.add(TestId::new(6));
818
819        let collected_ids: Vec<TestId> = set
820            .iter_in((
821                Bound::Included(TestId::new(1)),
822                Bound::Excluded(TestId::new(5)),
823            ))
824            .collect();
825        assert_eq!(collected_ids, vec![TestId::new(1), TestId::new(2)],);
826    }
827
828    #[ktest]
829    fn iter_in_bound_tuple_exclusive_inclusive() {
830        type TestId = MockId<7>;
831        let mut set: IdSet<TestId> = IdSet::new_empty();
832        set.add(TestId::new(0));
833        set.add(TestId::new(1));
834        set.add(TestId::new(2));
835        set.add(TestId::new(5));
836        set.add(TestId::new(6));
837
838        let collected_ids: Vec<TestId> = set
839            .iter_in((
840                Bound::Excluded(TestId::new(1)),
841                Bound::Included(TestId::new(5)),
842            ))
843            .collect();
844        assert_eq!(collected_ids, vec![TestId::new(2), TestId::new(5)],);
845    }
846
847    #[ktest]
848    fn iter_in_unbounded_bounds() {
849        type TestId = MockId<7>;
850        let mut set: IdSet<TestId> = IdSet::new_empty();
851        set.add(TestId::new(0));
852        set.add(TestId::new(1));
853        set.add(TestId::new(2));
854        set.add(TestId::new(5));
855        set.add(TestId::new(6));
856
857        let collected_ids: Vec<TestId> = set
858            .iter_in((Bound::Unbounded::<TestId>, Bound::Unbounded::<TestId>))
859            .collect();
860        assert_eq!(
861            collected_ids,
862            vec![
863                TestId::new(0),
864                TestId::new(1),
865                TestId::new(2),
866                TestId::new(5),
867                TestId::new(6)
868            ],
869        );
870    }
871
872    #[ktest]
873    fn iter_in_half_unbounded() {
874        type TestId = MockId<7>;
875        let mut set: IdSet<TestId> = IdSet::new_empty();
876        set.add(TestId::new(0));
877        set.add(TestId::new(1));
878        set.add(TestId::new(2));
879        set.add(TestId::new(5));
880        set.add(TestId::new(6));
881
882        let collected_ids: Vec<TestId> = set
883            .iter_in((Bound::Included(TestId::new(2)), Bound::Unbounded::<TestId>))
884            .collect();
885        assert_eq!(
886            collected_ids,
887            vec![TestId::new(2), TestId::new(5), TestId::new(6)],
888        );
889
890        let collected_ids: Vec<TestId> = set
891            .iter_in((Bound::Unbounded::<TestId>, Bound::Included(TestId::new(2))))
892            .collect();
893        assert_eq!(
894            collected_ids,
895            vec![TestId::new(0), TestId::new(1), TestId::new(2)],
896        );
897    }
898
899    #[ktest]
900    fn iter_in_range_starts_after_last() {
901        type TestId = MockId<7>;
902        let mut set: IdSet<TestId> = IdSet::new_empty();
903        set.add(TestId::new(0));
904        set.add(TestId::new(1));
905        set.add(TestId::new(2));
906
907        let collected_ids: Vec<TestId> = set.iter_in(TestId::new(3)..).collect();
908        assert_eq!(collected_ids, vec![],);
909    }
910
911    #[ktest]
912    fn iter_in_range_ends_after_last() {
913        type TestId = MockId<7>;
914        let mut set: IdSet<TestId> = IdSet::new_empty();
915        set.add(TestId::new(0));
916        set.add(TestId::new(1));
917        set.add(TestId::new(2));
918
919        let collected_ids: Vec<TestId> = set.iter_in(..TestId::new(3)).collect();
920        assert_eq!(
921            collected_ids,
922            vec![TestId::new(0), TestId::new(1), TestId::new(2)],
923        );
924    }
925
926    #[ktest]
927    fn iter_in_range_next_part() {
928        type TestId = MockId<{ InnerPart::BITS }>;
929        let last_id = TestId::new(InnerPart::BITS - 1);
930
931        let mut set: IdSet<TestId> = IdSet::new_empty();
932        set.add(last_id);
933
934        let collected_ids: Vec<TestId> = set
935            .iter_in((Bound::Excluded(last_id), Bound::Included(last_id)))
936            .collect();
937        assert_eq!(collected_ids, vec![],);
938    }
939}
ostd/util/id_set.rs

ostd/util/
id_set.rs
