Skip to main content

imhm/
lib.rs

1//! Persistent hash maps and sets: hash tries whose nodes are shared
2//! between versions. A clone is O(1); an update copies the path from
3//! the root to the key and shares everything else, and a map no other
4//! version shares is updated in place.
5//!
6//! Inner nodes branch on 5 hash bits per level, high bits first; a
7//! subtree of at most [`LEAF`] pairs is a flat leaf sorted by hash. A
8//! key set has one tree shape for a given hasher, and iteration follows
9//! it, in hash order, so with a deterministic hasher (the default) the
10//! order is the same in every process. [`Map::root`] and
11//! [`NodeHandle`] expose the tree to a codec that must reproduce its
12//! sharing.
13
14use anyhow::{Result, ensure};
15use node::Raw;
16pub use rustc_hash::FxBuildHasher;
17use std::{
18    array,
19    borrow::Borrow,
20    fmt,
21    hash::{BuildHasher, Hash},
22    iter::FusedIterator,
23    mem, slice, vec,
24};
25
26mod lanes;
27mod node;
28#[cfg(test)]
29mod test;
30
31const BITS: u32 = 5;
32/// The deepest inner node. Its fragment is the hash's last 4 bits, so
33/// two distinct hashes part at or above it, and below it are only
34/// leaves of one hash.
35const MAX_DEPTH: u8 = 12;
36/// The most pairs a leaf holds, unless all of them share one hash.
37pub const LEAF: usize = 32;
38/// The room a new leaf of two has.
39const PAIR_CAP: usize = 8;
40const MUL: u64 = 0x9e37_79b9_7f4a_7c15;
41
42/// Spreads the hasher's entropy over every bit the trie reads. A
43/// bijection, so distinct hashes stay distinct.
44#[inline]
45fn mix(h: u64) -> u64 {
46    let h = h.wrapping_mul(MUL);
47    h ^ (h >> 32)
48}
49
50fn hash_of<Q: Hash + ?Sized>(s: &impl BuildHasher, q: &Q) -> u64 {
51    mix(s.hash_one(q))
52}
53
54/// `hash`'s fragment at `depth`, high bits first, so a trie's order is
55/// its hashes' order.
56#[inline]
57fn frag(hash: u64, depth: u8) -> usize {
58    ((hash << (BITS * depth as u32)) >> 59) as usize
59}
60
61/// The fragments above `depth`, which every hash under a node there
62/// shares.
63#[inline]
64fn prefix(hash: u64, depth: u8) -> u64 {
65    match BITS * depth as u32 {
66        0 => 0,
67        n @ 1..64 => hash & !(u64::MAX >> n),
68        _ => hash,
69    }
70}
71
72#[derive(Clone)]
73struct Entry<K, V> {
74    hash: u64,
75    key: K,
76    val: V,
77}
78
79/// `bitmap` has the bits of the fragments whose slots are not empty.
80#[derive(Clone, Copy)]
81struct InnerHead {
82    len: usize,
83    bitmap: u32,
84    depth: u8,
85}
86
87/// For the first [`LEAF`] entries: `tags[i]` is the [`tag`] of entry
88/// `i`'s hash, and `order` lists their indices in hash order. Past the
89/// entries, the tags are 0 and the order [`lanes::GONE`].
90#[derive(Clone, Copy)]
91struct LeafHead {
92    depth: u8,
93    tags: [u8; LEAF],
94    order: [u8; LEAF],
95}
96
97/// A slot per fragment, holding more than [`LEAF`] pairs of at least two
98/// hashes.
99type Inner<K, V> = Raw<InnerHead, Slot<K, V>>;
100
101fn slots<K, V>(n: &Inner<K, V>) -> &[Slot<K, V>; 32] {
102    n.items().try_into().expect("a slot per fragment")
103}
104
105/// At least two entries below the root, and at most [`LEAF`] unless all
106/// share one hash.
107type Leaf<K, V> = Raw<LeafHead, Entry<K, V>>;
108
109enum Node<K, V> {
110    Inner(Inner<K, V>),
111    Leaf(Leaf<K, V>),
112}
113
114impl<K, V> Clone for Node<K, V> {
115    fn clone(&self) -> Self {
116        match self {
117            Node::Inner(n) => Node::Inner(n.clone()),
118            Node::Leaf(n) => Node::Leaf(n.clone()),
119        }
120    }
121}
122
123/// A subtree of one pair is an entry in its parent's slot.
124#[derive(Clone)]
125enum Slot<K, V> {
126    Empty,
127    Entry(Entry<K, V>),
128    Node(Node<K, V>),
129}
130
131fn empty_slots<K, V>() -> [Slot<K, V>; 32] {
132    array::from_fn(|_| Slot::Empty)
133}
134
135impl<K, V> Node<K, V> {
136    fn len(&self) -> usize {
137        match self {
138            Node::Inner(n) => n.header().len,
139            Node::Leaf(n) => n.items().len(),
140        }
141    }
142
143    fn depth(&self) -> u8 {
144        match self {
145            Node::Inner(n) => n.header().depth,
146            Node::Leaf(n) => n.header().depth,
147        }
148    }
149
150    /// A hash from the subtree. Every hash in it shares the fragments
151    /// above its depth, so any one places it.
152    fn hash(&self) -> u64 {
153        match self {
154            Node::Inner(n) => {
155                slots(n)[n.header().bitmap.trailing_zeros() as usize].hash()
156            }
157            Node::Leaf(n) => n.items()[0].hash,
158        }
159    }
160
161    fn addr(&self) -> usize {
162        match self {
163            Node::Inner(n) => n.addr(),
164            Node::Leaf(n) => n.addr(),
165        }
166    }
167
168    fn ptr_eq(&self, other: &Self) -> bool {
169        match (self, other) {
170            (Node::Inner(a), Node::Inner(b)) => a.ptr_eq(b),
171            (Node::Leaf(a), Node::Leaf(b)) => a.ptr_eq(b),
172            _ => false,
173        }
174    }
175}
176
177impl<K, V> Slot<K, V> {
178    /// A hash from a slot not empty.
179    fn hash(&self) -> u64 {
180        match self {
181            Slot::Empty => unreachable!("an empty slot has no hash"),
182            Slot::Entry(e) => e.hash,
183            Slot::Node(n) => n.hash(),
184        }
185    }
186
187    fn len(&self) -> usize {
188        match self {
189            Slot::Empty => 0,
190            Slot::Entry(_) => 1,
191            Slot::Node(n) => n.len(),
192        }
193    }
194}
195
196/// The byte of `hash` just below the fragments above `depth`, or 1 for
197/// 0, so a leaf's tags are in the order of its hashes and none is 0.
198#[inline]
199fn tag(hash: u64, depth: u8) -> u8 {
200    top_tag(hash.checked_shl(BITS * depth as u32).unwrap_or(0))
201}
202
203/// The tag of a hash whose fragments above the leaf are shifted out.
204#[inline]
205fn top_tag(rest: u64) -> u8 {
206    ((rest >> 56) as u8).max(1)
207}
208
209/// The header of a leaf at `depth` of `entries`, in hash order.
210fn leaf_head<'a, K: 'a, V: 'a>(
211    depth: u8,
212    entries: impl IntoIterator<Item = &'a Entry<K, V>>,
213) -> LeafHead {
214    let (mut tags, mut order) = ([0; LEAF], [lanes::GONE; LEAF]);
215    for (i, e) in entries.into_iter().take(LEAF).enumerate() {
216        tags[i] = tag(e.hash, depth);
217        order[i] = i as u8;
218    }
219    LeafHead { depth, tags, order }
220}
221
222/// The leaf at `depth` of `entries`, in hash order.
223fn leaf<K, V>(depth: u8, entries: Vec<Entry<K, V>>) -> Leaf<K, V> {
224    let cap = entries.len();
225    Raw::new(leaf_head(depth, &entries), cap, entries)
226}
227
228/// The leaf at `depth` of `a` and `b`.
229fn pair<K, V>(depth: u8, a: Entry<K, V>, b: Entry<K, V>) -> Leaf<K, V> {
230    let (a, b) = if b.hash < a.hash { (b, a) } else { (a, b) };
231    Raw::new(leaf_head(depth, [&a, &b]), PAIR_CAP, [a, b])
232}
233
234/// A leaf's entries in hash order, moved out if no other version holds
235/// it, which is left empty.
236fn sorted_items<K: Clone, V: Clone>(l: &mut Leaf<K, V>) -> Vec<Entry<K, V>> {
237    let order = l.header().order;
238    let mut v = l.take_items();
239    let mut placed = 0u64;
240    for k in 0..v.len().min(LEAF) {
241        let mut j = k;
242        while placed & 1 << j == 0 {
243            placed |= 1 << j;
244            let from = order[j] as usize;
245            if from == k {
246                break;
247            }
248            v.swap(j, from);
249            j = from;
250        }
251    }
252    v
253}
254
255/// The subtree at `depth` of the next `n` of `entries`, at least two,
256/// in hash order.
257fn build<K, V>(
258    depth: u8,
259    entries: &mut vec::Drain<'_, Entry<K, V>>,
260    n: usize,
261) -> Node<K, V> {
262    let s = &entries.as_slice()[..n];
263    if n <= LEAF || s[0].hash == s[n - 1].hash {
264        let h = leaf_head(depth, s);
265        return Node::Leaf(Raw::new(h, n, entries.by_ref().take(n)));
266    }
267    let mut slots = empty_slots();
268    let mut bitmap = 0;
269    let mut left = n;
270    while left > 0 {
271        let s = &entries.as_slice()[..left];
272        let f = frag(s[0].hash, depth);
273        let k = s.iter().take_while(|e| frag(e.hash, depth) == f).count();
274        slots[f] = match k {
275            1 => Slot::Entry(entries.next().expect("a group's entry")),
276            k => Slot::Node(build(depth + 1, entries, k)),
277        };
278        bitmap |= 1 << f;
279        left -= k;
280    }
281    Node::Inner(Raw::new(InnerHead { len: n, bitmap, depth }, 32, slots))
282}
283
284/// Every entry under `node`, in hash order, moved out of the nodes no
285/// other version holds, which are left empty.
286fn drain_into<K: Clone, V: Clone>(
287    node: &mut Node<K, V>,
288    out: &mut Vec<Entry<K, V>>,
289    g: &mut Grave<K, V>,
290) {
291    match node {
292        Node::Leaf(l) => out.extend(sorted_items(l)),
293        Node::Inner(n) => {
294            for slot in n.take_items() {
295                match slot {
296                    Slot::Empty => (),
297                    Slot::Entry(e) => out.push(e),
298                    Slot::Node(mut c) => {
299                        drain_into(&mut c, out, g);
300                        g.bury(c)
301                    }
302                }
303            }
304        }
305    }
306}
307
308/// Nodes a change replaced whose last handle it held. Dropping one drops
309/// its entries, running user code that may panic, so a change finishes
310/// its grave only once the tree is whole again.
311struct Grave<K, V> {
312    leaves: Vec<Leaf<K, V>>,
313    inners: Vec<Inner<K, V>>,
314}
315
316impl<K, V> Grave<K, V> {
317    fn new() -> Self {
318        Self { leaves: Vec::new(), inners: Vec::new() }
319    }
320
321    fn bury(&mut self, n: Node<K, V>) {
322        match n {
323            Node::Leaf(l) => l.release(&mut self.leaves),
324            Node::Inner(n) => n.release(&mut self.inners),
325        }
326    }
327
328    /// Drops what was buried; the tree must be whole again.
329    #[inline]
330    fn finish(self) {
331        if self.leaves.capacity() == 0 && self.inners.capacity() == 0 {
332            mem::forget(self)
333        } else {
334            drop(self)
335        }
336    }
337}
338
339/// Makes an inner node that now holds at most [`LEAF`] pairs, or only
340/// one leaf, a leaf.
341fn settle<K: Clone, V: Clone>(node: &mut Node<K, V>, g: &mut Grave<K, V>) {
342    let Node::Inner(n) = node else { return };
343    let h = *n.header();
344    if h.len > LEAF && !lone_leaf(n) {
345        return;
346    }
347    let (depth, len) = (h.depth, h.len);
348    let mut entries = Vec::with_capacity(len);
349    drain_into(node, &mut entries, g);
350    g.bury(mem::replace(node, build(depth, &mut entries.drain(..), len)));
351}
352
353/// Whether the node's only slot is a leaf, whose entries share one hash.
354fn lone_leaf<K, V>(n: &Inner<K, V>) -> bool {
355    let bitmap = n.header().bitmap;
356    bitmap.count_ones() == 1
357        && matches!(slots(n)[bitmap.trailing_zeros() as usize], Slot::Node(Node::Leaf(_)))
358}
359
360/// Whether comparing keys costs about as much as comparing hashes, so a
361/// tag match goes straight to the key.
362#[inline]
363const fn cheap_eq<K>() -> bool {
364    !mem::needs_drop::<K>() && mem::size_of::<K>() <= 16
365}
366
367/// The index of `q`, whose hash is `hash` with tag `t` here.
368#[inline]
369fn leaf_index<K, V, Q>(l: &Leaf<K, V>, t: u8, hash: u64, q: &Q) -> Option<usize>
370where
371    K: Borrow<Q>,
372    Q: Eq + ?Sized,
373{
374    let entries = l.items();
375    leaf_match(entries, same_tag(l, t), hash, q)
376}
377
378/// The entries tagged `t`, which is not 0.
379#[inline]
380fn same_tag<K, V>(l: &Leaf<K, V>, t: u8) -> lanes::Mask {
381    lanes::eq(&l.header().tags, t)
382}
383
384/// The index of `q` among `entries`, `same` holding those tagged like
385/// it.
386#[inline]
387fn leaf_match<K, V, Q>(
388    entries: &[Entry<K, V>],
389    same: lanes::Mask,
390    hash: u64,
391    q: &Q,
392) -> Option<usize>
393where
394    K: Borrow<Q>,
395    Q: Eq + ?Sized,
396{
397    for i in same {
398        let e = &entries[i];
399        if (cheap_eq::<K>() || e.hash == hash) && e.key.borrow() == q {
400            return Some(i);
401        }
402    }
403    if entries.len() > LEAF {
404        return untagged_index(entries, hash, q);
405    }
406    None
407}
408
409/// The index of `q` among the entries past the first [`LEAF`] of a leaf
410/// whose entries all share one hash.
411#[cold]
412fn untagged_index<K, V, Q>(entries: &[Entry<K, V>], hash: u64, q: &Q) -> Option<usize>
413where
414    K: Borrow<Q>,
415    Q: Eq + ?Sized,
416{
417    (entries[0].hash == hash)
418        .then(|| entries[LEAF..].iter().position(|e| e.key.borrow() == q))
419        .flatten()
420        .map(|i| i + LEAF)
421}
422
423/// `n` is a root: children are one level below their parent, so the
424/// fragment at each level is the next 5 bits of `hash`.
425#[inline]
426fn find<'a, K, V, Q>(mut n: &'a Node<K, V>, hash: u64, q: &Q) -> Option<(&'a K, &'a V)>
427where
428    K: Borrow<Q>,
429    Q: Eq + ?Sized,
430{
431    let mut rest = hash;
432    loop {
433        match n {
434            Node::Leaf(l) => {
435                let i = leaf_index(l, top_tag(rest), hash, q)?;
436                // SAFETY: `leaf_index` returns an index of an entry.
437                let e = unsafe { l.items().get_unchecked(i) };
438                return Some((&e.key, &e.val));
439            }
440            Node::Inner(inner) => {
441                let f = (rest >> 59) as usize;
442                rest <<= BITS;
443                match &slots(inner)[f] {
444                    Slot::Empty => return None,
445                    Slot::Entry(e) => {
446                        return (e.hash == hash && e.key.borrow() == q)
447                            .then_some((&e.key, &e.val));
448                    }
449                    Slot::Node(child) => n = child,
450                }
451            }
452        }
453    }
454}
455
456fn insert<K: Eq + Clone, V: Clone>(
457    node: &mut Node<K, V>,
458    hash: u64,
459    key: K,
460    val: V,
461    g: &mut Grave<K, V>,
462) -> Option<V> {
463    match node {
464        Node::Inner(inner) => {
465            let mut m = inner.make_mut(&mut g.inners);
466            let (h, slots) = m.parts();
467            let f = frag(hash, h.depth);
468            let slot = &mut slots[f];
469            let prev = match slot {
470                Slot::Empty => {
471                    *slot = Slot::Entry(Entry { hash, key, val });
472                    h.bitmap |= 1 << f;
473                    None
474                }
475                Slot::Entry(e) if e.hash == hash && e.key == key => {
476                    return without(key, mem::replace(&mut e.val, val));
477                }
478                Slot::Entry(_) => {
479                    let Slot::Entry(old) = mem::replace(slot, Slot::Empty) else {
480                        unreachable!("an entry, matched above")
481                    };
482                    let new = Entry { hash, key, val };
483                    *slot = Slot::Node(Node::Leaf(pair(h.depth + 1, old, new)));
484                    None
485                }
486                Slot::Node(child) => insert(child, hash, key, val, g),
487            };
488            if prev.is_none() {
489                h.len += 1
490            }
491            prev
492        }
493        Node::Leaf(l) => {
494            let t = tag(hash, l.header().depth);
495            let same = same_tag(l, t);
496            if let Some(i) = leaf_match(l.items(), same, hash, &key) {
497                let slot = &mut l.make_mut(&mut g.leaves).into_items()[i].val;
498                return without(key, mem::replace(slot, val));
499            }
500            let (entries, h) = (l.items(), l.header());
501            let n = entries.len();
502            let new = Entry { hash, key, val };
503            if n < LEAF {
504                let unused = LEAF - n;
505                let mut rank = lanes::below(&h.tags, t).count() - unused;
506                for i in same {
507                    rank += (entries[i].hash <= hash) as usize;
508                }
509                l.push(new, &mut g.leaves);
510                let mut m = l.make_mut(&mut g.leaves);
511                let h = m.header();
512                h.tags[n] = t;
513                lanes::insert(&mut h.order, rank, n as u8);
514            } else if [0, LEAF - 1].map(|k| entries[h.order[k] as usize].hash)
515                == [hash; 2]
516            {
517                l.push(new, &mut g.leaves);
518            } else {
519                let depth = h.depth;
520                let mut entries = sorted_items(l);
521                let at = entries.partition_point(|e| e.hash <= hash);
522                entries.insert(at, new);
523                g.bury(mem::replace(node, build(depth, &mut entries.drain(..), n + 1)));
524            }
525            None
526        }
527    }
528}
529
530/// `val`, once `key` is dropped: a destructor that panics while a
531/// function returns leaks the return value (rust-lang/rust#47949).
532fn without<K, V>(key: K, val: V) -> Option<V> {
533    drop(key);
534    Some(val)
535}
536
537/// Makes every node under `node` one no other version holds, copying
538/// those shared, so taking the subtree apart runs no user code.
539fn unshare<K: Clone, V: Clone>(node: &mut Node<K, V>, g: &mut Grave<K, V>) {
540    match node {
541        Node::Leaf(l) => drop(l.make_mut(&mut g.leaves)),
542        Node::Inner(n) => {
543            for slot in n.make_mut(&mut g.inners).into_items() {
544                if let Slot::Node(c) = slot {
545                    unshare(c, g)
546                }
547            }
548        }
549    }
550}
551
552/// Whether removing the key in slot `f` collapses `n` into a leaf.
553fn collapses<K, V>(n: &Inner<K, V>, f: usize) -> bool {
554    let (h, s) = (n.header(), slots(n));
555    let other = (h.bitmap & !(1 << f)).trailing_zeros() as usize;
556    h.len - 1 <= LEAF
557        || (h.bitmap.count_ones() == 2
558            && matches!(s[f], Slot::Entry(_))
559            && matches!(s.get(other), Some(Slot::Node(Node::Leaf(_)))))
560}
561
562/// Remove `q`, which must be present: a miss would copy the path for
563/// nothing. The entry is returned whole, so its key is dropped only once
564/// the tree is whole again. Every copy is made before anything moves,
565/// so a panicking clone leaves the map as it was.
566fn remove<K, V, Q>(
567    node: &mut Node<K, V>,
568    hash: u64,
569    q: &Q,
570    g: &mut Grave<K, V>,
571) -> Option<Entry<K, V>>
572where
573    K: Borrow<Q> + Clone,
574    V: Clone,
575    Q: Eq + ?Sized,
576{
577    match node {
578        Node::Leaf(l) => {
579            let i = leaf_index(l, tag(hash, l.header().depth), hash, q)?;
580            let n = l.items().len();
581            let e = l.swap_remove(i, &mut g.leaves);
582            if n <= LEAF {
583                let mut m = l.make_mut(&mut g.leaves);
584                let h = m.header();
585                let rank = lanes::eq(&h.order, i as u8).first();
586                lanes::remove(&mut h.order, rank.expect("each entry has a rank"));
587                h.tags[i] = h.tags[n - 1];
588                h.tags[n - 1] = 0;
589                if i != n - 1 {
590                    let moved = lanes::eq(&h.order, (n - 1) as u8).first();
591                    h.order[moved.expect("each entry has a rank")] = i as u8;
592                }
593            }
594            Some(e)
595        }
596        Node::Inner(inner) => {
597            let f = frag(hash, inner.header().depth);
598            if matches!(slots(inner)[f], Slot::Empty) {
599                return None;
600            }
601            if collapses(inner, f) {
602                unshare(node, g);
603            }
604            let Node::Inner(inner) = node else { unreachable!("still inner") };
605            let mut m = inner.make_mut(&mut g.inners);
606            let (h, slots) = m.parts();
607            let slot = &mut slots[f];
608            let v = match slot {
609                Slot::Entry(e) if e.hash == hash && e.key.borrow() == q => {
610                    let Slot::Entry(e) = mem::replace(slot, Slot::Empty) else {
611                        unreachable!("an entry, matched above")
612                    };
613                    h.bitmap &= !(1 << f);
614                    e
615                }
616                Slot::Empty | Slot::Entry(_) => return None,
617                Slot::Node(child) => {
618                    let e = remove(child, hash, q, g)?;
619                    match child {
620                        Node::Leaf(l) if l.items().len() == 1 => {
621                            let last = Slot::Entry(l.swap_remove(0, &mut g.leaves));
622                            if let Slot::Node(old) = mem::replace(slot, last) {
623                                g.bury(old)
624                            }
625                        }
626                        _ => settle(child, g),
627                    }
628                    e
629                }
630            };
631            h.len -= 1;
632            Some(v)
633        }
634    }
635}
636
637/// The value of `q`, which must be present: a miss would copy the path
638/// for nothing.
639fn get_mut<'a, K, V, Q>(
640    node: &'a mut Node<K, V>,
641    hash: u64,
642    q: &Q,
643    g: &mut Grave<K, V>,
644) -> Option<&'a mut V>
645where
646    K: Borrow<Q> + Clone,
647    V: Clone,
648    Q: Eq + ?Sized,
649{
650    match node {
651        Node::Leaf(l) => {
652            let i = leaf_index(l, tag(hash, l.header().depth), hash, q)?;
653            Some(&mut l.make_mut(&mut g.leaves).into_items()[i].val)
654        }
655        Node::Inner(inner) => {
656            let f = frag(hash, inner.header().depth);
657            match &mut inner.make_mut(&mut g.inners).into_items()[f] {
658                Slot::Empty => None,
659                Slot::Entry(e) => {
660                    (e.hash == hash && e.key.borrow() == q).then_some(&mut e.val)
661                }
662                Slot::Node(child) => get_mut(child, hash, q, g),
663            }
664        }
665    }
666}
667
668/// A persistent hash map.
669pub struct Map<K, V, S = FxBuildHasher> {
670    root: Option<Node<K, V>>,
671    hasher: S,
672}
673
674impl<K, V, S: Clone> Clone for Map<K, V, S> {
675    fn clone(&self) -> Self {
676        Self { root: self.root.clone(), hasher: self.hasher.clone() }
677    }
678}
679
680impl<K, V, S: Default> Default for Map<K, V, S> {
681    fn default() -> Self {
682        Self { root: None, hasher: S::default() }
683    }
684}
685
686impl<K, V> Map<K, V> {
687    pub fn new() -> Self {
688        Self::default()
689    }
690}
691
692impl<K, V, S> Map<K, V, S> {
693    pub fn with_hasher(hasher: S) -> Self {
694        Self { root: None, hasher }
695    }
696
697    pub fn hasher(&self) -> &S {
698        &self.hasher
699    }
700
701    pub fn len(&self) -> usize {
702        self.root.as_ref().map_or(0, Node::len)
703    }
704
705    pub fn is_empty(&self) -> bool {
706        self.root.is_none()
707    }
708
709    /// Whether the two share their whole tree, so they hold the same
710    /// pairs without comparing any; false says nothing.
711    pub fn ptr_eq(&self, other: &Self) -> bool {
712        match (&self.root, &other.root) {
713            (Some(a), Some(b)) => a.ptr_eq(b),
714            (a, b) => a.is_none() && b.is_none(),
715        }
716    }
717
718    /// The pairs in hash order.
719    pub fn iter(&self) -> Iter<'_, K, V> {
720        Iter::new(self.root.as_ref())
721    }
722
723    /// The root of the map's tree, `None` when empty.
724    pub fn root(&self) -> Option<NodeRef<'_, K, V>> {
725        self.root.as_ref().map(NodeRef)
726    }
727
728    /// The map over the tree rooted at `root`, a depth 0 node built
729    /// with a hasher that hashes like `hasher`.
730    pub fn from_root(root: Option<NodeHandle<K, V>>, hasher: S) -> Result<Self> {
731        if let Some(r) = &root {
732            ensure!(r.0.depth() == 0, "a root is at depth 0, not {}", r.0.depth());
733        }
734        Ok(Self { root: root.map(|r| r.0), hasher })
735    }
736}
737
738impl<K, V, S> Map<K, V, S>
739where
740    K: Hash + Eq,
741    S: BuildHasher,
742{
743    pub fn get_full<Q>(&self, q: &Q) -> Option<(&K, &V)>
744    where
745        K: Borrow<Q>,
746        Q: Hash + Eq + ?Sized,
747    {
748        find(self.root.as_ref()?, hash_of(&self.hasher, q), q)
749    }
750
751    pub fn get<Q>(&self, q: &Q) -> Option<&V>
752    where
753        K: Borrow<Q>,
754        Q: Hash + Eq + ?Sized,
755    {
756        self.get_full(q).map(|(_, v)| v)
757    }
758
759    pub fn get_key<Q>(&self, q: &Q) -> Option<&K>
760    where
761        K: Borrow<Q>,
762        Q: Hash + Eq + ?Sized,
763    {
764        self.get_full(q).map(|(k, _)| k)
765    }
766
767    pub fn contains_key<Q>(&self, q: &Q) -> bool
768    where
769        K: Borrow<Q>,
770        Q: Hash + Eq + ?Sized,
771    {
772        self.get_full(q).is_some()
773    }
774}
775
776impl<K, V, S> Map<K, V, S>
777where
778    K: Hash + Eq + Clone,
779    V: Clone,
780    S: BuildHasher,
781{
782    /// Insert in place, copying only the parts of the tree shared with
783    /// another version. Returns the previous value; the previous key
784    /// stays.
785    pub fn insert_cow(&mut self, key: K, val: V) -> Option<V> {
786        let hash = hash_of(&self.hasher, &key);
787        match &mut self.root {
788            Some(root) => {
789                let mut g = Grave::new();
790                let prev = insert(root, hash, key, val, &mut g);
791                g.finish();
792                prev
793            }
794            None => {
795                self.root = Some(Node::Leaf(leaf(0, vec![Entry { hash, key, val }])));
796                None
797            }
798        }
799    }
800
801    /// Remove in place, copying only the parts of the tree shared with
802    /// another version.
803    pub fn remove_cow<Q>(&mut self, q: &Q) -> Option<V>
804    where
805        K: Borrow<Q>,
806        Q: Hash + Eq + ?Sized,
807    {
808        let hash = hash_of(&self.hasher, q);
809        let root = self.root.as_mut()?;
810        find(root, hash, q)?;
811        let mut g = Grave::new();
812        let e = remove(root, hash, q, &mut g)?;
813        match root.len() {
814            0 => g.bury(self.root.take().expect("a root")),
815            _ => settle(root, &mut g),
816        }
817        g.finish();
818        without(e.key, e.val)
819    }
820
821    /// The value of `q` to change in place, copying only the parts of
822    /// the tree shared with another version.
823    pub fn get_mut_cow<Q>(&mut self, q: &Q) -> Option<&mut V>
824    where
825        K: Borrow<Q>,
826        Q: Hash + Eq + ?Sized,
827    {
828        let hash = hash_of(&self.hasher, q);
829        let root = self.root.as_mut()?;
830        find(root, hash, q)?;
831        let mut g = Grave::new();
832        let v = get_mut(root, hash, q, &mut g);
833        g.finish();
834        v
835    }
836
837    /// The value of `key`, first inserting `f()` if it is absent.
838    pub fn get_or_insert_cow(&mut self, key: K, f: impl FnOnce() -> V) -> &mut V {
839        if !self.contains_key(&key) {
840            self.insert_cow(key.clone(), f());
841        }
842        self.get_mut_cow(&key).expect("present after insert")
843    }
844
845    pub fn get_or_default_cow(&mut self, key: K) -> &mut V
846    where
847        V: Default,
848    {
849        self.get_or_insert_cow(key, V::default)
850    }
851}
852
853impl<K, V, S> Map<K, V, S>
854where
855    K: Hash + Eq + Clone,
856    V: Clone,
857    S: BuildHasher + Clone,
858{
859    /// A new map with `key` bound to `val`, and the previous value.
860    pub fn insert(&self, key: K, val: V) -> (Self, Option<V>) {
861        let mut m = self.clone();
862        let prev = m.insert_cow(key, val);
863        (m, prev)
864    }
865
866    /// A new map without `q`, and its value.
867    pub fn remove<Q>(&self, q: &Q) -> (Self, Option<V>)
868    where
869        K: Borrow<Q>,
870        Q: Hash + Eq + ?Sized,
871    {
872        let mut m = self.clone();
873        let prev = m.remove_cow(q);
874        (m, prev)
875    }
876
877    pub fn insert_many(&self, kvs: impl IntoIterator<Item = (K, V)>) -> Self {
878        let mut m = self.clone();
879        m.extend(kvs);
880        m
881    }
882
883    pub fn remove_many<Q>(&self, qs: impl IntoIterator<Item = Q>) -> Self
884    where
885        K: Borrow<Q>,
886        Q: Hash + Eq,
887    {
888        let mut m = self.clone();
889        for q in qs {
890            m.remove_cow(&q);
891        }
892        m
893    }
894}
895
896impl<K, V, S> Extend<(K, V)> for Map<K, V, S>
897where
898    K: Hash + Eq + Clone,
899    V: Clone,
900    S: BuildHasher,
901{
902    fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, kvs: I) {
903        for (k, v) in kvs {
904            self.insert_cow(k, v);
905        }
906    }
907}
908
909impl<K, V, S> FromIterator<(K, V)> for Map<K, V, S>
910where
911    K: Hash + Eq + Clone,
912    V: Clone,
913    S: BuildHasher + Default,
914{
915    fn from_iter<I: IntoIterator<Item = (K, V)>>(kvs: I) -> Self {
916        let mut m = Self::default();
917        m.extend(kvs);
918        m
919    }
920}
921
922impl<K, V, S> PartialEq for Map<K, V, S>
923where
924    K: Hash + Eq,
925    V: PartialEq,
926    S: BuildHasher,
927{
928    fn eq(&self, other: &Self) -> bool {
929        self.len() == other.len() && self.iter().all(|(k, v)| other.get(k) == Some(v))
930    }
931}
932
933impl<K: Hash + Eq, V: Eq, S: BuildHasher> Eq for Map<K, V, S> {}
934
935impl<K: fmt::Debug, V: fmt::Debug, S> fmt::Debug for Map<K, V, S> {
936    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
937        f.debug_map().entries(self.iter()).finish()
938    }
939}
940
941impl<'a, K, V, S> IntoIterator for &'a Map<K, V, S> {
942    type Item = (&'a K, &'a V);
943    type IntoIter = Iter<'a, K, V>;
944
945    fn into_iter(self) -> Iter<'a, K, V> {
946        self.iter()
947    }
948}
949
950/// A leaf's entries in hash order.
951struct Ordered<'a, K, V> {
952    entries: &'a [Entry<K, V>],
953    order: slice::Iter<'a, u8>,
954    rest: slice::Iter<'a, Entry<K, V>>,
955}
956
957impl<'a, K, V> Ordered<'a, K, V> {
958    fn new(l: &'a Leaf<K, V>) -> Self {
959        let entries = l.items();
960        let tagged = entries.len().min(LEAF);
961        let order = l.header().order[..tagged].iter();
962        Self { entries, order, rest: entries[tagged..].iter() }
963    }
964
965    fn empty() -> Self {
966        Self { entries: &[], order: [].iter(), rest: [].iter() }
967    }
968}
969
970impl<'a, K, V> Iterator for Ordered<'a, K, V> {
971    type Item = &'a Entry<K, V>;
972
973    #[inline]
974    fn next(&mut self) -> Option<&'a Entry<K, V>> {
975        match self.order.next() {
976            Some(&i) => Some(&self.entries[i as usize]),
977            None => self.rest.next(),
978        }
979    }
980
981    fn size_hint(&self) -> (usize, Option<usize>) {
982        let n = self.order.len() + self.rest.len();
983        (n, Some(n))
984    }
985}
986
987/// An inner node's slots that are not empty, in fragment order.
988struct Occupied<'a, K, V> {
989    slots: &'a [Slot<K, V>],
990    bits: u32,
991}
992
993impl<'a, K, V> Occupied<'a, K, V> {
994    fn new(n: &'a Inner<K, V>) -> Self {
995        Self { slots: n.items(), bits: n.header().bitmap }
996    }
997}
998
999impl<K, V> Clone for Occupied<'_, K, V> {
1000    fn clone(&self) -> Self {
1001        Self { slots: self.slots, bits: self.bits }
1002    }
1003}
1004
1005impl<'a, K, V> Iterator for Occupied<'a, K, V> {
1006    type Item = &'a Slot<K, V>;
1007
1008    #[inline]
1009    fn next(&mut self) -> Option<&'a Slot<K, V>> {
1010        let f = self.bits.trailing_zeros() as usize;
1011        self.bits &= self.bits.wrapping_sub(1);
1012        self.slots.get(f)
1013    }
1014
1015    fn size_hint(&self) -> (usize, Option<usize>) {
1016        let n = self.bits.count_ones() as usize;
1017        (n, Some(n))
1018    }
1019}
1020
1021/// A walk of a tree in hash order, with a frame per inner level.
1022pub struct Iter<'a, K, V> {
1023    stack: [Occupied<'a, K, V>; MAX_DEPTH as usize + 1],
1024    top: usize,
1025    leaf: Ordered<'a, K, V>,
1026    remaining: usize,
1027}
1028
1029impl<'a, K, V> Iter<'a, K, V> {
1030    fn new(root: Option<&'a Node<K, V>>) -> Self {
1031        let mut stack = array::from_fn(|_| Occupied { slots: &[], bits: 0 });
1032        let mut leaf = Ordered::empty();
1033        let mut top = 0;
1034        match root {
1035            None => (),
1036            Some(Node::Leaf(l)) => leaf = Ordered::new(l),
1037            Some(Node::Inner(n)) => {
1038                stack[0] = Occupied::new(n);
1039                top = 1;
1040            }
1041        }
1042        let remaining = root.map_or(0, Node::len);
1043        Self { stack, top, leaf, remaining }
1044    }
1045}
1046
1047impl<'a, K, V> Iterator for Iter<'a, K, V> {
1048    type Item = (&'a K, &'a V);
1049
1050    fn next(&mut self) -> Option<(&'a K, &'a V)> {
1051        loop {
1052            if let Some(e) = self.leaf.next() {
1053                self.remaining -= 1;
1054                return Some((&e.key, &e.val));
1055            }
1056            match self.stack[..self.top].last_mut()?.next() {
1057                None => self.top -= 1,
1058                Some(Slot::Empty) => unreachable!("occupied slots are not empty"),
1059                Some(Slot::Entry(e)) => {
1060                    self.remaining -= 1;
1061                    return Some((&e.key, &e.val));
1062                }
1063                Some(Slot::Node(Node::Leaf(l))) => self.leaf = Ordered::new(l),
1064                Some(Slot::Node(Node::Inner(n))) => {
1065                    self.stack[self.top] = Occupied::new(n);
1066                    self.top += 1;
1067                }
1068            }
1069        }
1070    }
1071
1072    fn size_hint(&self) -> (usize, Option<usize>) {
1073        (self.remaining, Some(self.remaining))
1074    }
1075}
1076
1077impl<K, V> ExactSizeIterator for Iter<'_, K, V> {}
1078impl<K, V> FusedIterator for Iter<'_, K, V> {}
1079
1080/// A borrowed node of a map's tree, for a codec that must reproduce
1081/// the tree's sharing. Two views with the same [`identity`] are the
1082/// same node; a [`NodeHandle`] from [`keep`] pins that identity for as
1083/// long as it is held.
1084///
1085/// [`identity`]: NodeRef::identity
1086/// [`keep`]: NodeRef::keep
1087pub struct NodeRef<'a, K, V>(&'a Node<K, V>);
1088
1089impl<K, V> Clone for NodeRef<'_, K, V> {
1090    fn clone(&self) -> Self {
1091        *self
1092    }
1093}
1094
1095impl<K, V> Copy for NodeRef<'_, K, V> {}
1096
1097/// What a node holds.
1098pub enum Contents<'a, K, V> {
1099    /// Slots in fragment order.
1100    Inner(Slots<'a, K, V>),
1101    /// Pairs in hash order.
1102    Leaf(Pairs<'a, K, V>),
1103}
1104
1105/// A slot of an inner node: a lone pair, or a subtree.
1106pub enum SlotRef<'a, K, V> {
1107    Entry(&'a K, &'a V),
1108    Node(NodeRef<'a, K, V>),
1109}
1110
1111pub struct Slots<'a, K, V>(Occupied<'a, K, V>);
1112
1113impl<'a, K, V> Iterator for Slots<'a, K, V> {
1114    type Item = SlotRef<'a, K, V>;
1115
1116    fn next(&mut self) -> Option<SlotRef<'a, K, V>> {
1117        Some(match self.0.next()? {
1118            Slot::Empty => unreachable!("occupied slots are not empty"),
1119            Slot::Entry(e) => SlotRef::Entry(&e.key, &e.val),
1120            Slot::Node(n) => SlotRef::Node(NodeRef(n)),
1121        })
1122    }
1123
1124    fn size_hint(&self) -> (usize, Option<usize>) {
1125        self.0.size_hint()
1126    }
1127}
1128
1129impl<K, V> ExactSizeIterator for Slots<'_, K, V> {}
1130
1131pub struct Pairs<'a, K, V>(Ordered<'a, K, V>);
1132
1133impl<'a, K, V> Iterator for Pairs<'a, K, V> {
1134    type Item = (&'a K, &'a V);
1135
1136    fn next(&mut self) -> Option<(&'a K, &'a V)> {
1137        self.0.next().map(|e| (&e.key, &e.val))
1138    }
1139
1140    fn size_hint(&self) -> (usize, Option<usize>) {
1141        self.0.size_hint()
1142    }
1143}
1144
1145impl<K, V> ExactSizeIterator for Pairs<'_, K, V> {}
1146
1147impl<'a, K, V> NodeRef<'a, K, V> {
1148    /// The node's allocation address: equal for two views of one node,
1149    /// distinct for two nodes that are both alive.
1150    pub fn identity(&self) -> usize {
1151        self.0.addr()
1152    }
1153
1154    pub fn keep(&self) -> NodeHandle<K, V> {
1155        NodeHandle(self.0.clone())
1156    }
1157
1158    /// The node's level; the root is at 0.
1159    pub fn depth(&self) -> u8 {
1160        self.0.depth()
1161    }
1162
1163    /// The pairs in the node's subtree.
1164    pub fn subtree_len(&self) -> usize {
1165        self.0.len()
1166    }
1167
1168    pub fn contents(&self) -> Contents<'a, K, V> {
1169        let node: &'a Node<K, V> = self.0;
1170        match node {
1171            Node::Inner(n) => Contents::Inner(Slots(Occupied::new(n))),
1172            Node::Leaf(n) => Contents::Leaf(Pairs(Ordered::new(n))),
1173        }
1174    }
1175}
1176
1177/// An owned node, built by [`inner`](NodeHandle::inner) or
1178/// [`leaf`](NodeHandle::leaf), or kept from a [`NodeRef`]. A map is
1179/// assembled from handles with [`Map::from_root`].
1180pub struct NodeHandle<K, V>(Node<K, V>);
1181
1182impl<K, V> Clone for NodeHandle<K, V> {
1183    fn clone(&self) -> Self {
1184        Self(self.0.clone())
1185    }
1186}
1187
1188impl<K, V> fmt::Debug for NodeHandle<K, V> {
1189    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1190        let v = self.view();
1191        write!(
1192            f,
1193            "NodeHandle({:#x}, depth {}, {} pairs)",
1194            v.identity(),
1195            v.depth(),
1196            v.subtree_len()
1197        )
1198    }
1199}
1200
1201/// A slot of an inner node to [create](NodeHandle::inner).
1202pub enum NewSlot<K, V> {
1203    Entry(K, V),
1204    Node(NodeHandle<K, V>),
1205}
1206
1207impl<K, V> NodeHandle<K, V> {
1208    pub fn view(&self) -> NodeRef<'_, K, V> {
1209        NodeRef(&self.0)
1210    }
1211
1212    /// The inner node at `depth` holding `slots`, exactly as a
1213    /// [`NodeRef`] reported them from a map using a hasher that hashes
1214    /// like `hasher`. Fails on any node that map could not have built.
1215    pub fn inner<S: BuildHasher>(
1216        hasher: &S,
1217        depth: u8,
1218        slots: impl IntoIterator<Item = NewSlot<K, V>>,
1219    ) -> Result<Self>
1220    where
1221        K: Hash + Eq,
1222    {
1223        ensure!(depth <= MAX_DEPTH, "depth {depth} is below the deepest inner level");
1224        let mut out = empty_slots();
1225        let mut bitmap = 0u32;
1226        let mut len = 0;
1227        let mut first_prefix = None;
1228        for s in slots {
1229            let slot = match s {
1230                NewSlot::Entry(key, val) => {
1231                    Slot::Entry(Entry { hash: hash_of(hasher, &key), key, val })
1232                }
1233                NewSlot::Node(child) => {
1234                    ensure!(child.0.depth() == depth + 1, "a child is one level down");
1235                    Slot::Node(child.0)
1236                }
1237            };
1238            let (hash, f) = (slot.hash(), frag(slot.hash(), depth));
1239            let p = prefix(hash, depth);
1240            ensure!(*first_prefix.get_or_insert(p) == p, "a node's slots share a prefix");
1241            ensure!(bitmap < 1 << f, "slots are in fragment order, one per fragment");
1242            bitmap |= 1 << f;
1243            len += slot.len();
1244            out[f] = slot;
1245        }
1246        let n = Raw::new(InnerHead { len, bitmap, depth }, 32, out);
1247        ensure!(len > LEAF, "an inner node holds more than {LEAF} pairs");
1248        ensure!(!lone_leaf(&n), "a lone leaf of one hash is the node itself");
1249        Ok(Self(Node::Inner(n)))
1250    }
1251
1252    /// The leaf at `depth` holding `pairs`, as [`inner`](Self::inner)
1253    /// does for an inner node.
1254    pub fn leaf<S: BuildHasher>(
1255        hasher: &S,
1256        depth: u8,
1257        pairs: impl IntoIterator<Item = (K, V)>,
1258    ) -> Result<Self>
1259    where
1260        K: Hash + Eq,
1261    {
1262        ensure!(depth <= MAX_DEPTH + 1, "depth {depth} is below the deepest level");
1263        let entries: Vec<Entry<K, V>> = pairs
1264            .into_iter()
1265            .map(|(key, val)| Entry { hash: hash_of(hasher, &key), key, val })
1266            .collect();
1267        let n = entries.len();
1268        let least = if depth > 0 { 2 } else { 1 };
1269        ensure!(n >= least, "a leaf below the root holds two pairs");
1270        let (first, last) = (entries[0].hash, entries[n - 1].hash);
1271        ensure!(n <= LEAF || first == last, "a leaf of many hashes holds at most {LEAF}");
1272        for (i, e) in entries.iter().enumerate() {
1273            ensure!(
1274                prefix(e.hash, depth) == prefix(first, depth),
1275                "a leaf shares a prefix"
1276            );
1277            ensure!(i == 0 || entries[i - 1].hash <= e.hash, "a leaf is in hash order");
1278            let mut same = entries[..i].iter().rev().take_while(|p| p.hash == e.hash);
1279            ensure!(same.all(|p| p.key != e.key), "a leaf's keys are distinct");
1280        }
1281        Ok(Self(Node::Leaf(leaf(depth, entries))))
1282    }
1283}
1284
1285/// A persistent hash set.
1286pub struct Set<K, S = FxBuildHasher>(Map<K, (), S>);
1287
1288impl<K, S: Clone> Clone for Set<K, S> {
1289    fn clone(&self) -> Self {
1290        Self(self.0.clone())
1291    }
1292}
1293
1294impl<K, S: Default> Default for Set<K, S> {
1295    fn default() -> Self {
1296        Self(Map::default())
1297    }
1298}
1299
1300impl<K> Set<K> {
1301    pub fn new() -> Self {
1302        Self::default()
1303    }
1304}
1305
1306impl<K, S> Set<K, S> {
1307    pub fn with_hasher(hasher: S) -> Self {
1308        Self(Map::with_hasher(hasher))
1309    }
1310
1311    pub fn hasher(&self) -> &S {
1312        self.0.hasher()
1313    }
1314
1315    pub fn len(&self) -> usize {
1316        self.0.len()
1317    }
1318
1319    pub fn is_empty(&self) -> bool {
1320        self.0.is_empty()
1321    }
1322
1323    /// Whether the two share their whole tree, as [`Map::ptr_eq`].
1324    pub fn ptr_eq(&self, other: &Self) -> bool {
1325        self.0.ptr_eq(&other.0)
1326    }
1327
1328    /// The members in hash order.
1329    pub fn iter(&self) -> SetIter<'_, K> {
1330        SetIter(self.0.iter())
1331    }
1332
1333    /// See [`Map::root`].
1334    pub fn root(&self) -> Option<NodeRef<'_, K, ()>> {
1335        self.0.root()
1336    }
1337
1338    /// See [`Map::from_root`].
1339    pub fn from_root(root: Option<NodeHandle<K, ()>>, hasher: S) -> Result<Self> {
1340        Ok(Self(Map::from_root(root, hasher)?))
1341    }
1342}
1343
1344impl<K: Hash + Eq, S: BuildHasher> Set<K, S> {
1345    pub fn get<Q>(&self, q: &Q) -> Option<&K>
1346    where
1347        K: Borrow<Q>,
1348        Q: Hash + Eq + ?Sized,
1349    {
1350        self.0.get_key(q)
1351    }
1352
1353    pub fn contains<Q>(&self, q: &Q) -> bool
1354    where
1355        K: Borrow<Q>,
1356        Q: Hash + Eq + ?Sized,
1357    {
1358        self.0.contains_key(q)
1359    }
1360}
1361
1362impl<K: Hash + Eq + Clone, S: BuildHasher> Set<K, S> {
1363    /// Insert in place, copying only the parts of the tree shared with
1364    /// another version. True if `key` was already a member, in which
1365    /// case nothing is copied.
1366    pub fn insert_cow(&mut self, key: K) -> bool {
1367        self.contains(&key) || self.0.insert_cow(key, ()).is_some()
1368    }
1369
1370    /// Remove in place, copying only the parts of the tree shared with
1371    /// another version. True if `q` was a member.
1372    pub fn remove_cow<Q>(&mut self, q: &Q) -> bool
1373    where
1374        K: Borrow<Q>,
1375        Q: Hash + Eq + ?Sized,
1376    {
1377        self.0.remove_cow(q).is_some()
1378    }
1379}
1380
1381impl<K: Hash + Eq + Clone, S: BuildHasher + Clone> Set<K, S> {
1382    /// A new set with `key`, and whether it was already a member.
1383    pub fn insert(&self, key: K) -> (Self, bool) {
1384        let mut s = self.clone();
1385        let present = s.insert_cow(key);
1386        (s, present)
1387    }
1388
1389    /// A new set without `q`, and whether it was a member.
1390    pub fn remove<Q>(&self, q: &Q) -> (Self, bool)
1391    where
1392        K: Borrow<Q>,
1393        Q: Hash + Eq + ?Sized,
1394    {
1395        let mut s = self.clone();
1396        let present = s.remove_cow(q);
1397        (s, present)
1398    }
1399
1400    pub fn insert_many(&self, ks: impl IntoIterator<Item = K>) -> Self {
1401        let mut s = self.clone();
1402        s.extend(ks);
1403        s
1404    }
1405
1406    pub fn remove_many<Q>(&self, qs: impl IntoIterator<Item = Q>) -> Self
1407    where
1408        K: Borrow<Q>,
1409        Q: Hash + Eq,
1410    {
1411        Self(self.0.remove_many(qs))
1412    }
1413}
1414
1415impl<K: Hash + Eq + Clone, S: BuildHasher> Extend<K> for Set<K, S> {
1416    fn extend<I: IntoIterator<Item = K>>(&mut self, ks: I) {
1417        for k in ks {
1418            self.insert_cow(k);
1419        }
1420    }
1421}
1422
1423impl<K: Hash + Eq + Clone, S: BuildHasher + Default> FromIterator<K> for Set<K, S> {
1424    fn from_iter<I: IntoIterator<Item = K>>(ks: I) -> Self {
1425        let mut s = Self::default();
1426        s.extend(ks);
1427        s
1428    }
1429}
1430
1431impl<K: Hash + Eq, S: BuildHasher> PartialEq for Set<K, S> {
1432    fn eq(&self, other: &Self) -> bool {
1433        self.0 == other.0
1434    }
1435}
1436
1437impl<K: Hash + Eq, S: BuildHasher> Eq for Set<K, S> {}
1438
1439impl<K: fmt::Debug, S> fmt::Debug for Set<K, S> {
1440    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1441        f.debug_set().entries(self.iter()).finish()
1442    }
1443}
1444
1445impl<'a, K, S> IntoIterator for &'a Set<K, S> {
1446    type Item = &'a K;
1447    type IntoIter = SetIter<'a, K>;
1448
1449    fn into_iter(self) -> SetIter<'a, K> {
1450        self.iter()
1451    }
1452}
1453
1454pub struct SetIter<'a, K>(Iter<'a, K, ()>);
1455
1456impl<'a, K> Iterator for SetIter<'a, K> {
1457    type Item = &'a K;
1458
1459    fn next(&mut self) -> Option<&'a K> {
1460        self.0.next().map(|(k, _)| k)
1461    }
1462
1463    fn size_hint(&self) -> (usize, Option<usize>) {
1464        self.0.size_hint()
1465    }
1466}
1467
1468impl<K> ExactSizeIterator for SetIter<'_, K> {}
1469impl<K> FusedIterator for SetIter<'_, K> {}