indexset/concurrent/
multimap.rs

1use ::core::borrow::Borrow;
2use ::core::fmt::Debug;
3use ::core::iter::FusedIterator;
4use ::core::marker::PhantomData;
5use ::core::ops::{Bound, RangeBounds};
6use alloc::vec::Vec;
7
8use crate::core::node::NodeLike;
9use crate::{
10    cdc::change::ChangeEvent,
11    core::multipair::{MultiPair, MultiPairInsertHelper, MultiPairLike, MultiPairRemoveHelper, OrdMultiPair},
12};
13
14use super::set::BTreeSet;
15
16#[derive(Debug)]
17pub struct BTreeMultiMap<K, V, Node = Vec<MultiPair<K, V>>, M = MultiPair<K, V>>
18where
19    K: Debug + Send + Ord + Clone + 'static,
20    V: Debug + Send + Clone + 'static,
21    M: MultiPairLike<K, V> + Debug + Clone + Send + 'static,
22    Node: NodeLike<M> + Send + 'static,
23{
24    pub(crate) set: BTreeSet<M, Node>,
25    marker: PhantomData<(K, V)>,
26}
27
28/// A multimap whose entries are ordered by key and then value.
29///
30/// This representation requires `V: Ord`, and lets exact pair removal locate
31/// the value directly instead of scanning entries that share the same key.
32/// Removal remains `O(log n)`; the ordered representation avoids a linear scan
33/// over values that share a key, rather than making removal `O(1)`.
34///
35/// ```
36/// use indexset::concurrent::multimap::OrderedBTreeMultiMap;
37///
38/// let map = OrderedBTreeMultiMap::<usize, &str>::new();
39/// map.insert(1, "b");
40/// map.insert(1, "a");
41///
42/// assert_eq!(map.remove(&1, &"b"), Some((1, "b")));
43/// ```
44pub type OrderedBTreeMultiMap<K, V> = BTreeMultiMap<K, V, Vec<OrdMultiPair<K, V>>, OrdMultiPair<K, V>>;
45
46impl<K, V, Node, M> Default for BTreeMultiMap<K, V, Node, M>
47where
48    K: Debug + Send + Ord + Clone + 'static,
49    V: Debug + Send + Clone + 'static,
50    M: MultiPairLike<K, V> + Debug + Clone + Send + 'static,
51    Node: NodeLike<M> + Send + 'static,
52{
53    fn default() -> Self {
54        Self {
55            set: BTreeSet::default().with_grouped_borrow_routing(),
56            marker: PhantomData,
57        }
58    }
59}
60
61pub struct Iter<'a, K, V, Node, M>
62where
63    K: Debug + Send + Ord + Clone + 'static,
64    V: Debug + Send + Clone + 'static,
65    M: MultiPairLike<K, V> + Debug + Clone + Send + 'static,
66    Node: NodeLike<M> + Send + 'static,
67{
68    inner: super::set::Iter<'a, M, Node>,
69    marker: PhantomData<(K, V)>,
70}
71
72impl<'a, K, V, Node, M> Iterator for Iter<'a, K, V, Node, M>
73where
74    K: Debug + Send + Ord + Clone + 'static,
75    V: Debug + Send + Clone + 'static,
76    M: MultiPairLike<K, V> + Debug + Clone + Send + 'static,
77    Node: NodeLike<M> + Send + 'static,
78{
79    type Item = (K, V);
80
81    fn next(&mut self) -> Option<Self::Item> {
82        if let Some(entry) = self.inner.next() {
83            return Some(entry.into());
84        }
85
86        None
87    }
88}
89
90impl<'a, K, V, Node, M> DoubleEndedIterator for Iter<'a, K, V, Node, M>
91where
92    K: Debug + Send + Ord + Clone + 'static,
93    V: Debug + Send + Clone + 'static,
94    M: MultiPairLike<K, V> + Debug + Clone + Send + 'static,
95    Node: NodeLike<M> + Send + 'static,
96{
97    fn next_back(&mut self) -> Option<Self::Item> {
98        if let Some(entry) = self.inner.next_back() {
99            return Some(entry.into());
100        }
101
102        None
103    }
104}
105
106impl<'a, K, V, Node, M> FusedIterator for Iter<'a, K, V, Node, M>
107where
108    K: Debug + Send + Ord + Clone + 'static,
109    V: Debug + Send + Clone + 'static,
110    M: MultiPairLike<K, V> + Debug + Clone + Send + 'static,
111    Node: NodeLike<M> + Send + 'static,
112{
113}
114
115pub struct Range<'a, K, V, Node, M>
116where
117    K: Debug + Send + Ord + Clone + 'static,
118    V: Debug + Send + Clone + 'static,
119    M: MultiPairLike<K, V> + Debug + Clone + Send + 'static,
120    Node: NodeLike<M> + Send + 'static,
121{
122    inner: super::set::Range<'a, M, Node>,
123    marker: PhantomData<(K, V)>,
124}
125
126impl<'a, K, V, Node, M> Iterator for Range<'a, K, V, Node, M>
127where
128    K: Debug + Send + Ord + Clone + 'static,
129    V: Debug + Send + Clone + 'static,
130    M: MultiPairLike<K, V> + Debug + Clone + Send + 'static,
131    Node: NodeLike<M> + Send + 'static,
132{
133    type Item = (K, V);
134
135    fn next(&mut self) -> Option<Self::Item> {
136        self.inner.next().map(Into::into)
137    }
138}
139
140impl<'a, K, V, Node, M> DoubleEndedIterator for Range<'a, K, V, Node, M>
141where
142    K: Debug + Send + Ord + Clone + 'static,
143    V: Debug + Send + Clone + 'static,
144    M: MultiPairLike<K, V> + Debug + Clone + Send + 'static,
145    Node: NodeLike<M> + Send + 'static,
146{
147    fn next_back(&mut self) -> Option<Self::Item> {
148        self.inner.next_back().map(Into::into)
149    }
150}
151
152impl<'a, K, V, Node, M> FusedIterator for Range<'a, K, V, Node, M>
153where
154    K: Debug + Send + Ord + Clone + 'static,
155    V: Debug + Send + Clone + 'static,
156    M: MultiPairLike<K, V> + Debug + Clone + Send + 'static,
157    Node: NodeLike<M> + Send + 'static,
158{
159}
160
161impl<K, V, Node, M> BTreeMultiMap<K, V, Node, M>
162where
163    K: Debug + Send + Ord + Clone + 'static,
164    V: Debug + Send + Clone + 'static,
165    M: MultiPairLike<K, V> + Debug + Clone + Send + 'static,
166    Node: NodeLike<M> + Send + 'static,
167{
168    /// Makes a new, empty, persistent `BTreeMultiMap`.
169    ///
170    /// # Examples
171    ///
172    /// Basic usage:
173    ///
174    /// ```
175    /// use indexset::concurrent::multimap::BTreeMultiMap;
176    ///
177    /// let mut map = BTreeMultiMap::<usize, &str>::new();
178    ///
179    /// // entries can now be inserted into the empty map
180    /// map.insert(1, "a");
181    /// ```
182    pub fn new() -> Self {
183        Self {
184            set: BTreeSet::default().with_grouped_borrow_routing(),
185            marker: PhantomData,
186        }
187    }
188    /// Makes a new, empty `BTreeMultiMap` with the given maximum node size. Allocates one vec with
189    /// the capacity set to be the specified node size.
190    ///
191    /// # Examples
192    ///
193    /// ```
194    /// use indexset::concurrent::multimap::BTreeMultiMap;
195    ///
196    /// let map = BTreeMultiMap::<i32, i32>::with_maximum_node_size(128);
197    pub fn with_maximum_node_size(node_capacity: usize) -> Self {
198        Self {
199            set: BTreeSet::with_maximum_node_size(node_capacity).with_grouped_borrow_routing(),
200            marker: PhantomData,
201        }
202    }
203    /// Adds full [`Node`] to this multiset. [`Node`] should be correct node with
204    /// values sorted.
205    #[cfg(feature = "cdc")]
206    pub fn attach_multi_node(&self, node: Node) {
207        self.set.attach_node(node)
208    }
209    /// Attaches persisted [`Node`]s with one topology publication.
210    #[cfg(feature = "cdc")]
211    pub fn attach_multi_nodes(&self, nodes: impl IntoIterator<Item = Node>) {
212        self.set.attach_nodes(nodes)
213    }
214
215    /// Returns detached, read-only snapshots of this multimap's [`Node`]s.
216    ///
217    /// Callers requiring one coherent logical generation must prevent
218    /// concurrent mutation while collecting.
219    #[cfg(feature = "cdc")]
220    pub fn snapshot_nodes(&self) -> Vec<Node>
221    where
222        Node: Clone,
223    {
224        self.set
225            .index
226            .read()
227            .values()
228            .map(|node| (*node.read()).clone())
229            .collect()
230    }
231    /// Returns `true` if the map contains at least one occurance of the specified key.
232    ///
233    /// The key may be any borrowed form of the map's key type, but the ordering
234    /// on the borrowed form *must* match the ordering on the key type.
235    ///
236    /// # Examples
237    ///
238    /// Basic usage:
239    ///
240    /// ```
241    /// use indexset::concurrent::multimap::BTreeMultiMap;
242    ///
243    /// let mut map = BTreeMultiMap::<usize, &str>::new();
244    /// map.insert(1, "a");
245    /// map.insert(1, "b");
246    /// assert_eq!(map.contains_key(&1), true);
247    /// assert_eq!(map.contains_key(&2), false);
248    /// ```
249    pub fn contains_key<Q>(&self, key: &Q) -> bool
250    where
251        M: Borrow<Q>,
252        Q: Ord + ?Sized,
253    {
254        self.set.contains(key)
255    }
256    fn _range<Q, R>(&self, range: R) -> Range<'_, K, V, Node, M>
257    where
258        M: Borrow<Q>,
259        Q: Ord + ?Sized,
260        R: RangeBounds<Q>,
261    {
262        Range {
263            inner: super::set::BTreeSet::range(&self.set, range),
264            marker: PhantomData,
265        }
266    }
267    /// Constructs a double-ended iterator over all key value pairs with the given key in the map.
268    ///
269    /// ```
270    /// use indexset::concurrent::multimap::BTreeMultiMap;
271    /// use indexset::BTreeSet;
272    ///
273    /// let mut map = BTreeMultiMap::<usize, &str>::new();
274    ///
275    /// map.insert(1, "b");
276    /// map.insert(1, "a");
277    /// map.insert(2, "c");
278    ///
279    /// let all_with_key = map.get(&1).collect::<BTreeSet<_>>();
280    /// assert_eq!(all_with_key.len(), 2);
281    /// assert_eq!(all_with_key, vec![(1, "a"), (1, "b")].into_iter().collect::<BTreeSet<_>>());
282    /// ```
283    pub fn get(&self, key: &K) -> Range<'_, K, V, Node, M>
284    where
285        M: Borrow<K>,
286    {
287        self._range((Bound::Included(key), Bound::Included(key)))
288    }
289    /// Removes some key from the map that matches the given key, returning the
290    /// key and the value if the key was previously in the map.
291    ///
292    /// The key may be any borrowed form of the map's key type, but the ordering
293    /// on the borrowed form *must* match the ordering on the key type.
294    ///
295    /// # Examples
296    ///
297    /// Basic usage:
298    ///
299    /// ```
300    /// use indexset::concurrent::multimap::BTreeMultiMap;
301    ///
302    /// let map = BTreeMultiMap::<usize, &str>::new();
303    /// map.insert(1, "b");
304    /// map.insert(1, "a");
305    ///
306    /// let first_removed = map.remove_some(&1).unwrap();
307    /// let second_removed = map.remove_some(&1).unwrap();
308    /// let removals = vec![first_removed, second_removed];
309    ///
310    /// assert!(removals.contains(&(1, "a")));
311    /// assert!(removals.contains(&(1, "b")));
312    /// ```
313    pub fn remove_some<Q>(&self, key: &Q) -> Option<(K, V)>
314    where
315        M: Borrow<Q>,
316        Q: Ord + ?Sized,
317    {
318        self.set.remove(key).map(Into::into)
319    }
320    /// Removes some key from the map that matches the given key, returning the
321    /// key and the value if the key was previously in the map with
322    /// [`ChangeEvent`]'s describing this `remove_some` action.
323    #[cfg(feature = "cdc")]
324    pub fn remove_some_cdc<Q>(&self, key: &Q) -> (Option<(K, V)>, Vec<ChangeEvent<M>>)
325    where
326        M: Borrow<Q>,
327        Q: Ord + ?Sized,
328    {
329        let (old_value, cdc) = self.set.remove_cdc(key);
330
331        (old_value.map(Into::into), cdc)
332    }
333    /// Returns the number of elements in the map.
334    ///
335    /// # Examples
336    ///
337    /// Basic usage:
338    ///
339    /// ```
340    /// use indexset::concurrent::multimap::BTreeMultiMap;
341    ///
342    /// let mut a = BTreeMultiMap::<usize, &str>::new();
343    /// assert_eq!(a.len(), 0);
344    /// a.insert(1, "a");
345    /// assert_eq!(a.len(), 1);
346    /// ```
347    pub fn len(&self) -> usize {
348        self.set.len()
349    }
350    /// Returns `true` if the multimap contains no elements.
351    ///
352    /// # Examples
353    ///
354    /// Basic usage:
355    ///
356    /// ```
357    /// use indexset::concurrent::multimap::BTreeMultiMap;
358    ///
359    /// let mut a = BTreeMultiMap::<usize, &str>::new();
360    /// assert!(a.is_empty());
361    /// a.insert(1, "a");
362    /// assert!(!a.is_empty());
363    /// ```
364    pub fn is_empty(&self) -> bool {
365        self.set.is_empty()
366    }
367    /// Returns the total number of allocated slots across all internal nodes.
368    ///
369    /// This represents the number of key-value pairs the multimap can hold
370    /// without reallocating memory in its internal vectors.
371    ///
372    /// # Examples
373    ///
374    /// Basic usage:
375    ///
376    /// ```
377    /// use indexset::concurrent::multimap::BTreeMultiMap;
378    ///
379    /// let mut a = BTreeMultiMap::<usize, &str>::with_maximum_node_size(8);
380    ///
381    /// a.insert(1, "a");
382    /// a.insert(1, "b");
383    ///
384    /// // Capacity remains unchanged until reallocation occurs
385    /// assert_eq!(a.capacity(), 8);
386    /// ```
387    pub fn capacity(&self) -> usize {
388        self.set.capacity()
389    }
390    /// Returns the total number of nodes.
391    ///
392    ///
393    /// # Examples
394    ///
395    /// Basic usage:
396    ///
397    /// ```
398    /// use indexset::concurrent::map::BTreeMap;
399    ///
400    /// let mut a = BTreeMap::<usize, &str>::with_maximum_node_size(16);
401    ///
402    /// a.insert(1, "a");
403    /// a.insert(2, "b");
404    ///
405    /// assert_eq!(a.node_count(), 1);
406    /// ```
407    pub fn node_count(&self) -> usize {
408        self.set.node_count()
409    }
410    /// Gets an iterator over the entries of the map, sorted by key.
411    ///
412    /// # Examples
413    ///
414    /// Basic usage:
415    ///
416    /// ```
417    /// use indexset::concurrent::multimap::BTreeMultiMap;
418    ///
419    /// let mut map = BTreeMultiMap::<usize, &str>::new();
420    /// map.insert(3, "c");
421    /// map.insert(2, "b");
422    /// map.insert(1, "a");
423    ///
424    /// for (key, value) in map.iter() {
425    ///     println!("{key}: {value}");
426    /// }
427    ///
428    /// let (first_key, first_value) = map.iter().next().unwrap();
429    /// assert_eq!((first_key, first_value), (1, "a"));
430    /// ```
431    pub fn iter(&self) -> Iter<'_, K, V, Node, M> {
432        Iter {
433            inner: self.set.iter(),
434            marker: PhantomData,
435        }
436    }
437    /// Constructs a double-ended iterator over a sub-range of elements in the map.
438    /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
439    /// yield elements from min (inclusive) to max (exclusive).
440    /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
441    /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
442    /// range from 4 to 10.
443    ///
444    /// # Panics
445    ///
446    /// Panics if range `start > end`.
447    /// Panics if range `start == end` and both bounds are `Excluded`.
448    ///
449    /// # Examples
450    ///
451    /// Basic usage:
452    ///
453    /// ```
454    /// use indexset::concurrent::multimap::BTreeMultiMap;
455    /// use std::ops::Bound::Included;
456    ///
457    /// let mut map = BTreeMultiMap::<usize, &str>::new();
458    /// map.insert(3, "a");
459    /// map.insert(5, "b");
460    /// map.insert(8, "c");
461    /// for (key, value) in map.range((Included(&4), Included(&8))) {
462    ///     println!("{key}: {value}");
463    /// }
464    /// assert_eq!(Some((5, "b")), map.range(4..).next());
465    /// ```
466    pub fn range<R>(&self, range: R) -> Range<'_, K, V, Node, M>
467    where
468        M: Borrow<K>,
469        R: RangeBounds<K>,
470    {
471        self._range(range)
472    }
473}
474
475impl<K, V, Node, M> BTreeMultiMap<K, V, Node, M>
476where
477    K: Debug + Send + Ord + Clone + 'static,
478    V: Debug + Send + Clone + 'static,
479    M: MultiPairLike<K, V> + MultiPairInsertHelper<K, V> + Debug + Clone + Send + 'static,
480    Node: NodeLike<M> + Send + 'static,
481{
482    /// Inserts a key-value pair into the multi map.
483    ///
484    /// The logical identity of an entry is the `(key, value)` pair: inserting
485    /// a pair that is already present (by the representation's value
486    /// equality) replaces it in place and returns the old value, while a new
487    /// pair is added alongside the key's other values.
488    ///
489    /// # Examples
490    ///
491    /// Basic usage:
492    ///
493    /// ```
494    /// use indexset::concurrent::multimap::BTreeMultiMap;
495    ///
496    /// let mut map = BTreeMultiMap::<usize, &str>::new();
497    /// assert_eq!(map.insert(37, "a"), None);
498    /// assert_eq!(map.len() == 0, false);
499    ///
500    /// map.insert(37, "b");
501    /// assert_eq!(map.insert(37, "c"), None);
502    /// assert_eq!(map.insert(37, "a"), Some("a"));
503    /// assert_eq!(map.len(), 3);
504    /// ```
505    pub fn insert(&self, key: K, value: V) -> Option<V> {
506        M::insert_into(&self.set, key, value).map(|(_, value)| value)
507    }
508
509    /// Inserts a key-value pair into the map and returns old value (if it was
510    /// already in set) with [`ChangeEvent`]'s that describes this insert
511    /// action. See [`BTreeMultiMap::insert`] for the replace semantics.
512    #[cfg(feature = "cdc")]
513    pub fn insert_cdc(&self, key: K, value: V) -> (Option<V>, Vec<ChangeEvent<M>>) {
514        let (old_value, cdc) = M::insert_cdc_into(&self.set, key, value);
515
516        (old_value.map(|(_, value)| value), cdc)
517    }
518}
519
520impl<K, V, Node, M> BTreeMultiMap<K, V, Node, M>
521where
522    K: Debug + Send + Ord + Clone + 'static,
523    V: Debug + Send + Clone + 'static,
524    M: MultiPairLike<K, V> + MultiPairRemoveHelper<K, V> + Debug + Clone + Send + 'static,
525    Node: NodeLike<M> + Send + 'static,
526{
527    /// Removes a specific key-value pair from the map returning the key and the value if the key
528    /// was previously in the map.
529    ///
530    /// # Examples
531    ///
532    /// Basic usage:
533    ///
534    /// ```
535    /// use indexset::concurrent::multimap::BTreeMultiMap;
536    ///
537    /// let map = BTreeMultiMap::<usize, &str>::new();
538    /// map.insert(1, "b");
539    /// map.insert(1, "a");
540    ///
541    /// assert_eq!(map.remove(&1, &"a"), Some((1, "a")));
542    /// assert_eq!(map.remove(&1, &"b"), Some((1, "b")));
543    /// ```
544    pub fn remove(&self, key: &K, value: &V) -> Option<(K, V)> {
545        M::remove_from(&self.set, key, value)
546    }
547
548    /// Removes a specific key-value pair from the map returning the key and the
549    /// value if the key was previously in the map with [`ChangeEvent`]'s
550    /// describing this `remove_some` action.
551    #[cfg(feature = "cdc")]
552    pub fn remove_cdc(&self, key: &K, value: &V) -> (Option<(K, V)>, Vec<ChangeEvent<M>>) {
553        M::remove_cdc_from(&self.set, key, value)
554    }
555}
556
557#[cfg(test)]
558mod tests {
559    use super::BTreeMultiMap;
560    use crate::core::multipair::{MultiPairLike, OrdMultiPair};
561    use crate::BTreeSet;
562    use std::borrow::Borrow;
563    use std::fmt::Debug;
564    use std::ops::Bound::{Excluded, Unbounded};
565    use std::sync::atomic::{AtomicUsize, Ordering};
566    use std::sync::{Arc, Barrier};
567    use std::thread;
568
569    #[test]
570    fn test_insert_works_as_expected() {
571        let maximum_node_size = 3;
572        let multi_map = BTreeMultiMap::<usize, &str>::with_maximum_node_size(maximum_node_size);
573
574        multi_map.insert(1usize, "a");
575        multi_map.insert(1usize, "b");
576        multi_map.insert(2usize, "c");
577        multi_map.insert(2usize, "d");
578        multi_map.insert(3usize, "e");
579        multi_map.insert(4usize, "f");
580        multi_map.insert(4usize, "g");
581
582        let expected_pairs = vec![(1, "b"), (1, "a"), (2, "d"), (2, "c"), (3, "e"), (4, "f"), (4, "g")]
583            .into_iter()
584            .collect::<BTreeSet<_>>();
585
586        let all_pairs = multi_map.iter().collect::<BTreeSet<_>>();
587        assert_eq!(all_pairs, expected_pairs);
588    }
589
590    #[test]
591    fn test_insert_all_same_key_works_as_expected() {
592        let maximum_node_size = 3;
593        let map = BTreeMultiMap::<usize, &str>::with_maximum_node_size(maximum_node_size);
594
595        map.insert(1usize, "a");
596        map.insert(1usize, "b");
597        map.insert(1usize, "c");
598        map.insert(1usize, "d");
599        map.insert(1usize, "e");
600        map.insert(1usize, "f");
601
602        let all_actual_pairs = map.iter().collect::<BTreeSet<_>>();
603        let all_expected_pairs = vec![(1, "f"), (1, "e"), (1, "d"), (1, "c"), (1, "b"), (1, "a")]
604            .into_iter()
605            .collect::<BTreeSet<_>>();
606        assert_eq!(all_actual_pairs, all_expected_pairs);
607
608        let all_ranged_pairs = map.range(1..2).collect::<BTreeSet<_>>();
609        assert_eq!(all_ranged_pairs, all_expected_pairs);
610        assert!(map.range(1..1).next().is_none());
611    }
612
613    fn assert_concurrent_remove_reinsert_preserves_exact_pairs(
614        records: usize,
615        buckets: usize,
616        threads: usize,
617        operations: usize,
618    ) {
619        let map = Arc::new(BTreeMultiMap::<usize, usize>::new());
620        let expected = Arc::new(
621            (0..records)
622                .map(|id| AtomicUsize::new(id % buckets))
623                .collect::<Vec<_>>(),
624        );
625        let start = Arc::new(Barrier::new(threads));
626        let mut handles = Vec::with_capacity(threads);
627
628        for id in 0..records {
629            map.insert(id % buckets, id);
630        }
631
632        for worker in 0..threads {
633            let map = Arc::clone(&map);
634            let expected = Arc::clone(&expected);
635            let start = Arc::clone(&start);
636            handles.push(thread::spawn(move || {
637                let owned = (worker..records).step_by(threads).collect::<Vec<_>>();
638                let worker_operations = operations / threads + usize::from(worker < operations % threads);
639                start.wait();
640
641                for sequence in 0..worker_operations {
642                    let id = owned[sequence % owned.len()];
643                    let old_bucket = expected[id].load(Ordering::Relaxed);
644                    let new_bucket = (old_bucket + 1) % buckets;
645
646                    assert_eq!(map.remove(&old_bucket, &id), Some((old_bucket, id)));
647                    assert_eq!(map.insert(new_bucket, id), None);
648                    expected[id].store(new_bucket, Ordering::Relaxed);
649                }
650            }));
651        }
652
653        for handle in handles {
654            handle.join().unwrap();
655        }
656
657        let mut occurrences = vec![0usize; records];
658        for (bucket, id) in map.iter() {
659            assert_eq!(bucket, expected[id].load(Ordering::Relaxed));
660            occurrences[id] += 1;
661        }
662
663        assert_eq!(map.len(), records);
664        assert!(occurrences.into_iter().all(|count| count == 1));
665    }
666
667    #[test]
668    fn test_concurrent_remove_reinsert_preserves_exact_pairs() {
669        assert_concurrent_remove_reinsert_preserves_exact_pairs(1_000, 16, 16, 10_000);
670    }
671
672    #[test]
673    fn test_concurrent_multimap_remove_reinsert_stress() {
674        assert_concurrent_remove_reinsert_preserves_exact_pairs(1_000, 16, 32, 100_000);
675    }
676
677    // The 250-insert churn that measured 55 live pairs under the old
678    // value-consulting Ord: cycling 5 logical pairs through insert must keep
679    // the logical pair count exact, with every repeat reported as a replace.
680    #[test]
681    fn same_key_churn_keeps_logical_pair_count_exact() {
682        let map = BTreeMultiMap::<usize, usize>::with_maximum_node_size(4);
683
684        for i in 0..250 {
685            let replaced = map.insert(1, i % 5);
686            if i < 5 {
687                assert_eq!(replaced, None, "first insert of value {} must be fresh", i % 5);
688            } else {
689                assert_eq!(replaced, Some(i % 5), "repeat insert of value {} must replace", i % 5);
690            }
691        }
692
693        assert_eq!(map.len(), 5, "same-key churn must not accumulate duplicates");
694        let mut values = map.get(&1).map(|(_, value)| value).collect::<Vec<_>>();
695        values.sort();
696        assert_eq!(values, vec![0, 1, 2, 3, 4]);
697
698        for value in 0..5 {
699            assert_eq!(map.remove(&1, &value), Some((1, value)));
700        }
701        assert!(map.is_empty());
702    }
703
704    // Split-livelock regression: many values under one key force nodes whose
705    // maxima share the key to split. Under the old Ord the split maxima
706    // compared Equal as skip-map entry keys, corrupting routing and
707    // livelocking the split retry loop (reproduced on master). With
708    // (key, discriminator) identity every entry key is unique, so this must
709    // terminate with every pair reachable and removable.
710    #[test]
711    fn same_key_node_splits_keep_routing_lawful() {
712        let map = BTreeMultiMap::<usize, usize>::with_maximum_node_size(4);
713
714        for value in 0..200 {
715            assert_eq!(map.insert(7, value), None);
716        }
717
718        assert_eq!(map.len(), 200);
719        assert!(map.node_count() > 1, "fixture must actually split");
720
721        let mut values = map.get(&7).map(|(_, value)| value).collect::<Vec<_>>();
722        values.sort();
723        assert_eq!(values, (0..200).collect::<Vec<_>>());
724
725        for value in 0..200 {
726            assert_eq!(map.remove(&7, &value), Some((7, value)));
727        }
728        assert!(map.is_empty());
729    }
730
731    #[test]
732    fn test_range_edge_cast() {
733        let maximum_node_size = 3;
734        let map = BTreeMultiMap::<usize, &str>::with_maximum_node_size(maximum_node_size);
735
736        map.insert(1usize, "a");
737        map.insert(1usize, "b");
738        map.insert(2usize, "c");
739        map.insert(2usize, "d");
740        map.insert(3usize, "e");
741        map.insert(4usize, "f");
742        map.insert(4usize, "g");
743
744        let mid_range = map.range(2..3).collect::<BTreeSet<_>>();
745        assert_eq!(
746            mid_range,
747            vec![(2, "c"), (2, "d"),].into_iter().collect::<BTreeSet<_>>()
748        );
749    }
750
751    fn assert_range_works_as_expected<M>()
752    where
753        M: MultiPairLike<usize, &'static str>
754            + crate::core::multipair::MultiPairInsertHelper<usize, &'static str>
755            + Borrow<usize>
756            + Debug
757            + Clone
758            + Send
759            + 'static,
760    {
761        let maximum_node_size = 3;
762        let map = BTreeMultiMap::<usize, &'static str, Vec<M>, M>::with_maximum_node_size(maximum_node_size);
763
764        map.insert(1usize, "a");
765        map.insert(1usize, "b");
766        map.insert(2usize, "c");
767        map.insert(2usize, "d");
768        map.insert(3usize, "e");
769        map.insert(4usize, "f");
770        map.insert(4usize, "g");
771
772        let truly_all_pairs = map.iter().collect::<BTreeSet<_>>();
773        let all_pairs = map.range(..).collect::<BTreeSet<_>>();
774        assert_eq!(all_pairs, truly_all_pairs);
775
776        let mid_range = map.range(2..3).collect::<BTreeSet<_>>();
777        assert_eq!(
778            mid_range,
779            vec![(2, "c"), (2, "d"),].into_iter().collect::<BTreeSet<_>>()
780        );
781
782        let reverse_range = map.range(1..4).rev().collect::<BTreeSet<_>>();
783        assert_eq!(
784            reverse_range,
785            vec![(3, "e"), (2, "d"), (2, "c"), (1, "b"), (1, "a"),]
786                .into_iter()
787                .collect::<BTreeSet<_>>()
788        );
789
790        let empty_range = map.range(5..).collect::<BTreeSet<_>>();
791        assert_eq!(empty_range, vec![].into_iter().collect::<BTreeSet<_>>());
792    }
793
794    #[test]
795    fn test_range_works_as_expected() {
796        assert_range_works_as_expected::<OrdMultiPair<usize, &'static str>>();
797    }
798
799    fn assert_range_excludes_values_at_bounds<M>()
800    where
801        M: MultiPairLike<usize, &'static str>
802            + crate::core::multipair::MultiPairInsertHelper<usize, &'static str>
803            + Borrow<usize>
804            + Debug
805            + Clone
806            + Send
807            + 'static,
808    {
809        let map = BTreeMultiMap::<usize, &'static str, Vec<M>, M>::with_maximum_node_size(10);
810
811        map.insert(1usize, "a");
812        map.insert(1usize, "b");
813        map.insert(2usize, "c");
814        map.insert(2usize, "d");
815        map.insert(3usize, "e");
816        map.insert(3usize, "f");
817
818        assert_eq!(
819            map.range((Excluded(&1), Unbounded)).collect::<BTreeSet<_>>(),
820            vec![(2, "c"), (2, "d"), (3, "e"), (3, "f")]
821                .into_iter()
822                .collect::<BTreeSet<_>>(),
823        );
824        assert_eq!(
825            map.range((Unbounded, Excluded(&3))).collect::<BTreeSet<_>>(),
826            vec![(1, "a"), (1, "b"), (2, "c"), (2, "d")]
827                .into_iter()
828                .collect::<BTreeSet<_>>(),
829        );
830    }
831
832    #[test]
833    fn test_range_excludes_all_values_at_bounds() {
834        assert_range_excludes_values_at_bounds::<OrdMultiPair<usize, &'static str>>();
835    }
836
837    fn assert_get_works_as_expected<M>()
838    where
839        M: MultiPairLike<usize, &'static str>
840            + crate::core::multipair::MultiPairInsertHelper<usize, &'static str>
841            + Borrow<usize>
842            + Debug
843            + Clone
844            + Send
845            + 'static,
846    {
847        let maximum_node_size = 10;
848        let map = BTreeMultiMap::<usize, &'static str, Vec<M>, M>::with_maximum_node_size(maximum_node_size);
849
850        map.insert(1usize, "a");
851        map.insert(1usize, "b");
852        map.insert(2usize, "c");
853        map.insert(2usize, "d");
854        map.insert(3usize, "e");
855        map.insert(4usize, "f");
856        map.insert(4usize, "g");
857
858        let range = map.get(&1).collect::<BTreeSet<_>>();
859
860        assert_eq!(range, vec![(1, "b"), (1, "a"),].into_iter().collect::<BTreeSet<_>>());
861
862        let range = map.get(&2).collect::<BTreeSet<_>>();
863        assert_eq!(range, vec![(2, "d"), (2, "c"),].into_iter().collect::<BTreeSet<_>>());
864
865        let range = map.get(&3).collect::<BTreeSet<_>>();
866        assert_eq!(range, vec![(3, "e"),].into_iter().collect::<BTreeSet<_>>());
867
868        let range = map.get(&4).collect::<BTreeSet<_>>();
869        assert_eq!(range, vec![(4, "g"), (4, "f"),].into_iter().collect::<BTreeSet<_>>());
870    }
871
872    #[test]
873    fn test_get_works_as_expected() {
874        assert_get_works_as_expected::<OrdMultiPair<usize, &'static str>>();
875    }
876
877    #[test]
878    fn test_get_works_as_expected_at_big_amounts() {
879        let maximum_node_size = 100;
880        let map = BTreeMultiMap::<String, usize>::with_maximum_node_size(maximum_node_size);
881
882        for i in 1..2000 {
883            map.insert(format!("ValueNum{}", i), i);
884        }
885
886        for i in 1..2000 {
887            let range = map.get(&format!("ValueNum{}", i)).collect::<BTreeSet<_>>();
888            assert_eq!(
889                range,
890                vec![(format!("ValueNum{}", i), i),]
891                    .into_iter()
892                    .collect::<BTreeSet<_>>()
893            );
894        }
895    }
896}
indexset/concurrent/multimap.rs

indexset/concurrent/
multimap.rs
