1use 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;
32const MAX_DEPTH: u8 = 12;
36pub const LEAF: usize = 32;
38const PAIR_CAP: usize = 8;
40const MUL: u64 = 0x9e37_79b9_7f4a_7c15;
41
42#[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#[inline]
57fn frag(hash: u64, depth: u8) -> usize {
58 ((hash << (BITS * depth as u32)) >> 59) as usize
59}
60
61#[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#[derive(Clone, Copy)]
81struct InnerHead {
82 len: usize,
83 bitmap: u32,
84 depth: u8,
85}
86
87#[derive(Clone, Copy)]
91struct LeafHead {
92 depth: u8,
93 tags: [u8; LEAF],
94 order: [u8; LEAF],
95}
96
97type 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
105type 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#[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 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 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#[inline]
199fn tag(hash: u64, depth: u8) -> u8 {
200 top_tag(hash.checked_shl(BITS * depth as u32).unwrap_or(0))
201}
202
203#[inline]
205fn top_tag(rest: u64) -> u8 {
206 ((rest >> 56) as u8).max(1)
207}
208
209fn 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
222fn 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
228fn 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
234fn 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
255fn 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
284fn 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
308struct 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 #[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
339fn 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
353fn 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#[inline]
363const fn cheap_eq<K>() -> bool {
364 !mem::needs_drop::<K>() && mem::size_of::<K>() <= 16
365}
366
367#[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#[inline]
380fn same_tag<K, V>(l: &Leaf<K, V>, t: u8) -> lanes::Mask {
381 lanes::eq(&l.header().tags, t)
382}
383
384#[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#[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#[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 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
530fn without<K, V>(key: K, val: V) -> Option<V> {
533 drop(key);
534 Some(val)
535}
536
537fn 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
552fn 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
562fn 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
637fn 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
668pub 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 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 pub fn iter(&self) -> Iter<'_, K, V> {
720 Iter::new(self.root.as_ref())
721 }
722
723 pub fn root(&self) -> Option<NodeRef<'_, K, V>> {
725 self.root.as_ref().map(NodeRef)
726 }
727
728 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 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 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 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 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 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 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
950struct 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
987struct 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
1021pub 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
1080pub 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
1097pub enum Contents<'a, K, V> {
1099 Inner(Slots<'a, K, V>),
1101 Leaf(Pairs<'a, K, V>),
1103}
1104
1105pub 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 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 pub fn depth(&self) -> u8 {
1160 self.0.depth()
1161 }
1162
1163 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
1177pub 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
1201pub 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 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 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
1285pub 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 pub fn ptr_eq(&self, other: &Self) -> bool {
1325 self.0.ptr_eq(&other.0)
1326 }
1327
1328 pub fn iter(&self) -> SetIter<'_, K> {
1330 SetIter(self.0.iter())
1331 }
1332
1333 pub fn root(&self) -> Option<NodeRef<'_, K, ()>> {
1335 self.0.root()
1336 }
1337
1338 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 pub fn insert_cow(&mut self, key: K) -> bool {
1367 self.contains(&key) || self.0.insert_cow(key, ()).is_some()
1368 }
1369
1370 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 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 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> {}