1use std::pin::Pin;
2
3use futures_util::TryStreamExt;
4use object_rainbow::{
5 Enum, Fetch, Hash, Inline, InlineOutput, ListHashes, MaybeHasNiche, Output, Parse, ParseInline,
6 PointInput, PointVisitor, Singular, Size, SizeExt, Tagged, Tags, ToOutput, Topological,
7 Traversible, assert_impl,
8};
9use object_rainbow_array_map::ArrayMap;
10use object_rainbow_point::{IntoPoint, Point};
11
12type ActionFuture<'a, T = ()> =
13 Pin<Box<dyn 'a + Send + Future<Output = object_rainbow::Result<T>>>>;
14type OptionFuture<'a, T> = ActionFuture<'a, Option<T>>;
15
16trait Amt<K>: Sized {
17 type V: Send + Sync;
18 fn is_empty(&self) -> bool;
19 fn insert(&mut self, key: K, value: Self::V) -> OptionFuture<'_, Self::V>;
20 fn remove(&mut self, key: K) -> OptionFuture<'_, Self::V>;
21 fn extract_only(&mut self) -> OptionFuture<'_, (K, Self::V)>;
22 fn from_pair(a: (K, Self::V), b: (K, Self::V)) -> Self;
23 fn get<'a, O: Send>(
24 &'a self,
25 key: K,
26 f: impl 'a + Send + FnOnce(&Self::V) -> O,
27 ) -> OptionFuture<'a, O>;
28 fn append<'a>(&'a mut self, other: &'a mut Self) -> ActionFuture<'a>;
29 fn intersect<'a>(&'a mut self, other: &'a Self) -> ActionFuture<'a>
30 where
31 Self::V: PartialEq;
32 fn subtract<'a>(&'a mut self, other: &'a Self) -> ActionFuture<'a>
33 where
34 Self::V: PartialEq;
35}
36
37#[derive(ToOutput, Tagged, ListHashes, Topological, Parse, Clone)]
38struct DeepestLeaf<V = ()>(ArrayMap<V>);
40
41impl<V: Send + Sync + Clone> Amt<u8> for DeepestLeaf<V> {
42 type V = V;
43
44 fn is_empty(&self) -> bool {
45 self.0.is_empty()
46 }
47
48 fn insert(&mut self, key: u8, value: Self::V) -> OptionFuture<'_, Self::V> {
49 Box::pin(async move { Ok(self.0.insert(key, value)) })
50 }
51
52 fn remove(&mut self, key: u8) -> OptionFuture<'_, Self::V> {
53 Box::pin(async move { Ok(self.0.remove(key)) })
54 }
55
56 fn extract_only(&mut self) -> OptionFuture<'_, (u8, Self::V)> {
57 Box::pin(async move {
58 Ok(if self.0.len() == 1 {
59 self.0.pop_first()
60 } else {
61 None
62 })
63 })
64 }
65
66 fn from_pair(a: (u8, Self::V), b: (u8, Self::V)) -> Self {
67 Self([a, b].into())
68 }
69
70 fn get<'a, O: Send>(
71 &'a self,
72 key: u8,
73 f: impl 'a + Send + FnOnce(&Self::V) -> O,
74 ) -> OptionFuture<'a, O> {
75 Box::pin(async move { Ok(self.0.get(key).map(f)) })
76 }
77
78 fn append<'a>(&'a mut self, other: &'a mut Self) -> ActionFuture<'a> {
79 Box::pin(async move {
80 self.0.append(&mut other.0);
81 Ok(())
82 })
83 }
84
85 fn intersect<'a>(&'a mut self, other: &'a Self) -> ActionFuture<'a>
86 where
87 Self::V: PartialEq,
88 {
89 Box::pin(async move {
90 self.0
91 .retain(|key, value| other.0.get(key).is_some_and(|other| other == value));
92 Ok(())
93 })
94 }
95
96 fn subtract<'a>(&'a mut self, other: &'a Self) -> ActionFuture<'a>
97 where
98 Self::V: PartialEq,
99 {
100 Box::pin(async move {
101 self.0
102 .retain(|key, value| other.0.get(key).is_none_or(|other| other != value));
103 Ok(())
104 })
105 }
106}
107
108#[derive(
109 Enum, ToOutput, InlineOutput, Tagged, ListHashes, Topological, Parse, ParseInline, Default,
110)]
111enum SubTree<T, K, V = <T as Amt<K>>::V> {
112 Leaf(K, V),
113 Sub(Point<T>),
114 #[default]
115 Empty,
116}
117
118impl<T, K: Clone, V: Clone> Clone for SubTree<T, K, V> {
119 fn clone(&self) -> Self {
120 match self {
121 Self::Leaf(key, value) => Self::Leaf(key.clone(), value.clone()),
122 Self::Sub(point) => Self::Sub(point.clone()),
123 Self::Empty => Self::Empty,
124 }
125 }
126}
127
128impl<T: Amt<K, V: Clone> + Clone + Traversible, K: Send + Sync + PartialEq + Clone> Amt<K>
129 for SubTree<T, K>
130{
131 type V = T::V;
132
133 fn is_empty(&self) -> bool {
134 matches!(self, Self::Empty)
135 }
136
137 fn insert(&mut self, key: K, value: Self::V) -> OptionFuture<'_, Self::V> {
138 Box::pin(async move {
139 match self {
140 Self::Leaf(xkey, xvalue) => Ok(if *xkey != key {
141 *self = Self::from_pair((xkey.clone(), xvalue.clone()), (key, value));
142 None
143 } else {
144 Some(std::mem::replace(xvalue, value))
145 }),
146 Self::Sub(sub) => sub.fetch_mut().await?.insert(key, value).await,
147 Self::Empty => Err(object_rainbow::error_consistency!(
148 "empty subtree? (invalid state)",
149 )),
150 }
151 })
152 }
153
154 fn remove(&mut self, key: K) -> OptionFuture<'_, Self::V> {
155 Box::pin(async move {
156 match self {
157 Self::Leaf(xkey, _) => Ok(if *xkey != key {
158 None
159 } else {
160 match std::mem::take(self) {
161 Self::Leaf(_, v) => Some(v),
162 _ => unreachable!(),
163 }
164 }),
165 Self::Sub(point) => {
166 let (value, extracted) = {
167 let sub = &mut *point.fetch_mut().await?;
168 let value = sub.remove(key).await?;
169 (value, sub.extract_only().await?)
170 };
171 if let Some((k, v)) = extracted {
172 *self = Self::Leaf(k, v);
173 }
174 Ok(value)
175 }
176 Self::Empty => Err(object_rainbow::error_consistency!(
177 "empty subtree? (invalid state)",
178 )),
179 }
180 })
181 }
182
183 fn extract_only(&mut self) -> OptionFuture<'_, (K, Self::V)> {
184 Box::pin(async move {
185 match self {
186 Self::Leaf(_, _) => match std::mem::take(self) {
187 Self::Leaf(k, v) => Ok(Some((k, v))),
188 _ => unreachable!(),
189 },
190 Self::Sub(point) => {
191 let extracted = point.fetch_mut().await?.extract_only().await?;
192 if let Some((k, v)) = extracted {
193 *self = Self::Empty;
194 Ok(Some((k, v)))
195 } else {
196 Ok(None)
197 }
198 }
199 Self::Empty => Err(object_rainbow::error_consistency!(
200 "empty subtree? (invalid state)",
201 )),
202 }
203 })
204 }
205
206 fn from_pair(a: (K, Self::V), b: (K, Self::V)) -> Self {
207 Self::Sub(T::from_pair(a, b).point())
208 }
209
210 fn get<'a, O: Send>(
211 &'a self,
212 key: K,
213 f: impl 'a + Send + FnOnce(&Self::V) -> O,
214 ) -> OptionFuture<'a, O> {
215 Box::pin(async move {
216 match self {
217 Self::Leaf(existing, value) => Ok((*existing == key).then(|| f(value))),
218 Self::Sub(sub) => sub.fetch().await?.get(key, f).await,
219 Self::Empty => Err(object_rainbow::error_consistency!(
220 "empty subtree? (invalid state)",
221 )),
222 }
223 })
224 }
225
226 fn append<'a>(&'a mut self, other: &'a mut Self) -> ActionFuture<'a> {
227 Box::pin(async move {
228 if matches!((&*self, &*other), (Self::Leaf(_, _), Self::Sub(_))) {
229 std::mem::swap(self, other);
230 }
231 match (&mut *self, &mut *other) {
232 (_, Self::Empty) => {}
233 (Self::Empty, _) => std::mem::swap(self, other),
234 (Self::Leaf(kl, vl), Self::Leaf(kr, vr)) if kl == kr => {
235 std::mem::swap(vl, vr);
236 *other = Self::Empty;
237 }
238 (Self::Leaf(_, _), Self::Leaf(_, _)) => {
239 match (std::mem::take(self), std::mem::take(other)) {
240 (Self::Leaf(kl, vl), Self::Leaf(kr, vr)) => {
241 *self = Self::Sub(T::from_pair((kl, vl), (kr, vr)).point());
242 }
243 _ => unreachable!(),
244 }
245 }
246 (Self::Leaf(_, _), Self::Sub(_)) => unreachable!(),
247 (Self::Sub(point), Self::Leaf(_, _)) => match std::mem::take(other) {
248 Self::Leaf(key, value) => {
249 point.fetch_mut().await?.insert(key, value).await?;
250 }
251 _ => unreachable!(),
252 },
253 (Self::Sub(l), Self::Sub(r)) => {
254 if l.hash() != r.hash() {
255 l.fetch_mut()
256 .await?
257 .append(&mut *r.fetch_mut().await?)
258 .await?;
259 }
260 *other = Self::Empty;
261 }
262 }
263 Ok(())
264 })
265 }
266
267 fn intersect<'a>(&'a mut self, other: &'a Self) -> ActionFuture<'a>
268 where
269 Self::V: PartialEq,
270 {
271 Box::pin(async move {
272 match (&mut *self, other) {
273 (Self::Empty, _) => {}
274 (_, Self::Empty) => *self = Self::Empty,
275 (Self::Leaf(kl, vl), Self::Leaf(kr, vr)) if kl == kr && vl == vr => {}
276 (Self::Leaf(_, _), Self::Leaf(_, _)) => *self = Self::Empty,
277 (Self::Leaf(key, value), Self::Sub(sub))
278 if sub
279 .fetch()
280 .await?
281 .get(key.clone(), |existing| value == existing)
282 .await?
283 .unwrap_or_default() => {}
284 (Self::Leaf(_, _), Self::Sub(_)) => *self = Self::Empty,
285 (Self::Sub(sub), Self::Leaf(key, value))
286 if sub
287 .fetch()
288 .await?
289 .get(key.clone(), |existing| value == existing)
290 .await?
291 .unwrap_or_default() =>
292 {
293 *self = other.clone()
294 }
295 (Self::Sub(_), Self::Leaf(_, _)) => *self = Self::Empty,
296 (Self::Sub(sub), Self::Sub(other)) => {
297 if sub.hash() == other.hash() {
298 return Ok(());
299 }
300 let (is_empty, extracted) = {
301 let sub = &mut *sub.fetch_mut().await?;
302 let other = &other.fetch().await?;
303 sub.intersect(other).await?;
304 (sub.is_empty(), sub.extract_only().await?)
305 };
306 if is_empty {
307 assert!(extracted.is_none());
308 *self = Self::Empty;
309 }
310 if let Some((k, v)) = extracted {
311 assert!(!is_empty);
312 *self = Self::Leaf(k, v);
313 }
314 }
315 }
316 Ok(())
317 })
318 }
319
320 fn subtract<'a>(&'a mut self, other: &'a Self) -> ActionFuture<'a>
321 where
322 Self::V: PartialEq,
323 {
324 Box::pin(async move {
325 match (&mut *self, other) {
326 (Self::Empty, _) => {}
327 (_, Self::Empty) => {}
328 (Self::Leaf(kl, vl), Self::Leaf(kr, vr)) if kl == kr && vl == vr => {
329 *self = Self::Empty;
330 }
331 (Self::Leaf(_, _), Self::Leaf(_, _)) => {}
332 (Self::Leaf(key, value), Self::Sub(sub))
333 if sub
334 .fetch()
335 .await?
336 .get(key.clone(), |existing| value == existing)
337 .await?
338 .unwrap_or_default() =>
339 {
340 *self = Self::Empty;
341 }
342 (Self::Leaf(_, _), Self::Sub(_)) => {}
343 (Self::Sub(sub), Self::Leaf(key, value))
344 if sub
345 .fetch()
346 .await?
347 .get(key.clone(), |existing| value == existing)
348 .await?
349 .unwrap_or_default() =>
350 {
351 let extracted = {
352 let sub = &mut *sub.fetch_mut().await?;
353 sub.remove(key.clone()).await?;
354 assert!(!sub.is_empty());
355 sub.extract_only().await?
356 };
357 if let Some((k, v)) = extracted {
358 *self = Self::Leaf(k, v);
359 }
360 }
361 (Self::Sub(_), Self::Leaf(_, _)) => {}
362 (Self::Sub(sub), Self::Sub(other)) => {
363 if sub.hash() == other.hash() {
364 *self = Self::Empty;
365 return Ok(());
366 }
367 let (is_empty, extracted) = {
368 let sub = &mut *sub.fetch_mut().await?;
369 let other = &other.fetch().await?;
370 sub.subtract(other).await?;
371 (sub.is_empty(), sub.extract_only().await?)
372 };
373 if is_empty {
374 assert!(extracted.is_none());
375 *self = Self::Empty;
376 }
377 if let Some((k, v)) = extracted {
378 assert!(!is_empty);
379 *self = Self::Leaf(k, v);
380 }
381 }
382 }
383 Ok(())
384 })
385 }
386}
387
388#[derive(ToOutput, Tagged, ListHashes, Topological, Parse)]
389struct SetNode<T, K, V = <T as Amt<K>>::V>(ArrayMap<SubTree<T, K, V>>);
390
391impl<T, K: Clone, V: Clone> Clone for SetNode<T, K, V> {
392 fn clone(&self) -> Self {
393 Self(self.0.clone())
394 }
395}
396
397impl<T, K, V> Default for SetNode<T, K, V> {
398 fn default() -> Self {
399 Self(Default::default())
400 }
401}
402
403impl<T: Amt<K, V: Clone> + Clone + Traversible, K: Send + Sync + PartialEq + Clone> Amt<(u8, K)>
404 for SetNode<T, K>
405{
406 type V = T::V;
407
408 fn is_empty(&self) -> bool {
409 self.0.is_empty()
410 }
411
412 fn insert(&mut self, (key, rest): (u8, K), value: Self::V) -> OptionFuture<'_, Self::V> {
413 Box::pin(async move {
414 if let Some(sub) = self.0.get_mut(key) {
415 sub.insert(rest, value).await
416 } else {
417 assert!(self.0.insert(key, SubTree::Leaf(rest, value)).is_none());
418 Ok(None)
419 }
420 })
421 }
422
423 fn remove(&mut self, (key, rest): (u8, K)) -> OptionFuture<'_, Self::V> {
424 Box::pin(async move {
425 if let Some(sub) = self.0.get_mut(key) {
426 let value = sub.remove(rest).await?;
427 if sub.is_empty() {
428 self.0.remove(key);
429 }
430 Ok(value)
431 } else {
432 Ok(None)
433 }
434 })
435 }
436
437 fn extract_only(&mut self) -> OptionFuture<'_, ((u8, K), Self::V)> {
438 Box::pin(async move {
439 Ok(if self.0.len() == 1 {
440 let (key, sub) = self.0.iter_mut().next().expect("must be len 1");
441 if let Some((rest, v)) = sub.extract_only().await? {
442 self.0.remove(key);
443 Some(((key, rest), v))
444 } else {
445 None
446 }
447 } else {
448 None
449 })
450 })
451 }
452
453 fn from_pair(
454 ((a, rest_a), value_a): ((u8, K), Self::V),
455 ((b, rest_b), value_b): ((u8, K), Self::V),
456 ) -> Self {
457 if a == b {
458 Self([(a, SubTree::from_pair((rest_a, value_a), (rest_b, value_b)))].into())
459 } else {
460 Self(
461 [
462 (a, SubTree::Leaf(rest_a, value_a)),
463 (b, SubTree::Leaf(rest_b, value_b)),
464 ]
465 .into(),
466 )
467 }
468 }
469
470 fn get<'a, O: Send>(
471 &'a self,
472 (key, rest): (u8, K),
473 f: impl 'a + Send + FnOnce(&Self::V) -> O,
474 ) -> OptionFuture<'a, O> {
475 Box::pin(async move {
476 if let Some(sub) = self.0.get(key) {
477 sub.get(rest, f).await
478 } else {
479 Ok(None)
480 }
481 })
482 }
483
484 fn append<'a>(&'a mut self, other: &'a mut Self) -> ActionFuture<'a> {
485 Box::pin(async move {
486 {
487 let mut futures = futures_util::stream::FuturesUnordered::new();
488 for (key, sub) in self.0.iter_mut() {
489 if let Some(mut other) = other.0.remove(key) {
490 futures.push(async move {
491 sub.append(&mut other)
492 .await
493 .map(|_| assert!(other.is_empty()))
494 });
495 }
496 }
497 while futures.try_next().await?.is_some() {}
498 }
499 while let Some((key, sub)) = other.0.pop_first() {
500 assert!(!self.0.contains(key));
501 self.0.insert(key, sub);
502 }
503 assert!(other.0.is_empty());
504 Ok(())
505 })
506 }
507
508 fn intersect<'a>(&'a mut self, other: &'a Self) -> ActionFuture<'a>
509 where
510 Self::V: PartialEq,
511 {
512 Box::pin(async move {
513 {
514 let mut futures = futures_util::stream::FuturesUnordered::new();
515 for (key, sub) in self.0.iter_mut() {
516 if let Some(other) = other.0.get(key) {
517 futures.push(sub.intersect(other));
518 } else {
519 *sub = SubTree::Empty;
520 }
521 }
522 while futures.try_next().await?.is_some() {}
523 }
524 self.0.retain(|_, sub| !sub.is_empty());
525 Ok(())
526 })
527 }
528
529 fn subtract<'a>(&'a mut self, other: &'a Self) -> ActionFuture<'a>
530 where
531 Self::V: PartialEq,
532 {
533 Box::pin(async move {
534 {
535 let mut futures = futures_util::stream::FuturesUnordered::new();
536 for (key, sub) in self.0.iter_mut() {
537 if let Some(other) = other.0.get(key) {
538 futures.push(sub.subtract(other));
539 }
540 }
541 while futures.try_next().await?.is_some() {}
542 }
543 self.0.retain(|_, sub| !sub.is_empty());
544 Ok(())
545 })
546 }
547}
548
549type K1 = u8;
550type K2 = (u8, K1);
551type K3 = (u8, K2);
552type K4 = (u8, K3);
553type K5 = (u8, K4);
554type K6 = (u8, K5);
555type K7 = (u8, K6);
556type K8 = (u8, K7);
557type K9 = (u8, K8);
558type K10 = (u8, K9);
559type K11 = (u8, K10);
560type K12 = (u8, K11);
561type K13 = (u8, K12);
562type K14 = (u8, K13);
563type K15 = (u8, K14);
564type K16 = (u8, K15);
565type K17 = (u8, K16);
566type K18 = (u8, K17);
567type K19 = (u8, K18);
568type K20 = (u8, K19);
569type K21 = (u8, K20);
570type K22 = (u8, K21);
571type K23 = (u8, K22);
572type K24 = (u8, K23);
573type K25 = (u8, K24);
574type K26 = (u8, K25);
575type K27 = (u8, K26);
576type K28 = (u8, K27);
577type K29 = (u8, K28);
578type K30 = (u8, K29);
579type K31 = (u8, K30);
580type K32 = (u8, K31);
581
582mod private {
583 use super::*;
584 type N1<V = ()> = DeepestLeaf<V>;
585
586 macro_rules! next_node {
587 ($prev:ident, $next:ident, $pk:ident, $k:ident) => {
588 #[derive(Clone)]
589 pub struct $next<V = ()>(SetNode<$prev<V>, $pk, V>);
590
591 impl<V> Default for $next<V> {
592 fn default() -> Self {
593 Self(Default::default())
594 }
595 }
596
597 impl<V: ParseInline<I> + Inline<I::Extra>, I: PointInput<Extra: Send + Sync>> Parse<I>
598 for $next<V>
599 {
600 fn parse(input: I) -> object_rainbow::Result<Self> {
601 Ok(Self(input.parse()?))
602 }
603 }
604
605 impl<V: Tagged> Tagged for $next<V> {
606 const TAGS: Tags = V::TAGS;
607 }
608
609 impl<V: InlineOutput> ToOutput for $next<V> {
610 fn to_output(&self, output: &mut impl Output) {
611 self.0.to_output(output);
612 }
613 }
614
615 impl<V: ListHashes> ListHashes for $next<V> {
616 fn list_hashes(&self, f: &mut impl FnMut(Hash)) {
617 self.0.list_hashes(f)
618 }
619 }
620
621 impl<V: Traversible + InlineOutput> Topological for $next<V> {
622 fn traverse(&self, visitor: &mut impl PointVisitor) {
623 self.0.traverse(visitor)
624 }
625 }
626
627 impl<V: Traversible + InlineOutput + Clone> Amt<$k> for $next<V> {
628 type V = V;
629
630 fn is_empty(&self) -> bool {
631 self.0.is_empty()
632 }
633
634 fn insert(&mut self, key: $k, value: Self::V) -> OptionFuture<'_, Self::V> {
635 self.0.insert(key, value)
636 }
637
638 fn remove(&mut self, key: $k) -> OptionFuture<'_, Self::V> {
639 self.0.remove(key)
640 }
641
642 fn extract_only(&mut self) -> OptionFuture<'_, ($k, Self::V)> {
643 self.0.extract_only()
644 }
645
646 fn from_pair(a: ($k, Self::V), b: ($k, Self::V)) -> Self {
647 Self(Amt::from_pair(a, b))
648 }
649
650 fn get<'a, O: Send>(
651 &'a self,
652 key: $k,
653 f: impl 'a + Send + FnOnce(&Self::V) -> O,
654 ) -> OptionFuture<'a, O> {
655 self.0.get(key, f)
656 }
657
658 fn append<'a>(&'a mut self, other: &'a mut Self) -> ActionFuture<'a> {
659 self.0.append(&mut other.0)
660 }
661
662 fn intersect<'a>(&'a mut self, other: &'a Self) -> ActionFuture<'a>
663 where
664 Self::V: PartialEq,
665 {
666 self.0.intersect(&other.0)
667 }
668
669 fn subtract<'a>(&'a mut self, other: &'a Self) -> ActionFuture<'a>
670 where
671 Self::V: PartialEq,
672 {
673 self.0.subtract(&other.0)
674 }
675 }
676 };
677 }
678
679 next_node!(N1, N2, K1, K2);
680 next_node!(N2, N3, K2, K3);
681 next_node!(N3, N4, K3, K4);
682 next_node!(N4, N5, K4, K5);
683 next_node!(N5, N6, K5, K6);
684 next_node!(N6, N7, K6, K7);
685 next_node!(N7, N8, K7, K8);
686 next_node!(N8, N9, K8, K9);
687 next_node!(N9, N10, K9, K10);
688 next_node!(N10, N11, K10, K11);
689 next_node!(N11, N12, K11, K12);
690 next_node!(N12, N13, K12, K13);
691 next_node!(N13, N14, K13, K14);
692 next_node!(N14, N15, K14, K15);
693 next_node!(N15, N16, K15, K16);
694 next_node!(N16, N17, K16, K17);
695 next_node!(N17, N18, K17, K18);
696 next_node!(N18, N19, K18, K19);
697 next_node!(N19, N20, K19, K20);
698 next_node!(N20, N21, K20, K21);
699 next_node!(N21, N22, K21, K22);
700 next_node!(N22, N23, K22, K23);
701 next_node!(N23, N24, K23, K24);
702 next_node!(N24, N25, K24, K25);
703 next_node!(N25, N26, K25, K26);
704 next_node!(N26, N27, K26, K27);
705 next_node!(N27, N28, K27, K28);
706 next_node!(N28, N29, K28, K29);
707 next_node!(N29, N30, K29, K30);
708 next_node!(N30, N31, K30, K31);
709 next_node!(N31, N32, K31, K32);
710}
711
712#[derive(
713 ToOutput, InlineOutput, Tagged, ListHashes, Topological, Parse, ParseInline, Size, MaybeHasNiche,
714)]
715pub struct HamtMap<V>(Point<private::N32<V>>);
716
717assert_impl!(
718 impl<V, E> Inline<E> for HamtMap<V>
719 where
720 E: 'static + Send + Sync + Clone,
721 V: Inline<E>,
722 {
723 }
724);
725
726impl<V> Clone for HamtMap<V> {
727 fn clone(&self) -> Self {
728 Self(self.0.clone())
729 }
730}
731
732impl<V> PartialEq for HamtMap<V> {
733 fn eq(&self, other: &Self) -> bool {
734 self.0 == other.0
735 }
736}
737
738impl<V> Eq for HamtMap<V> {}
739
740impl<V: Traversible + InlineOutput + Clone> Default for HamtMap<V> {
741 fn default() -> Self {
742 Self(Default::default())
743 }
744}
745
746impl<V: Traversible + InlineOutput + Clone> HamtMap<V> {
747 pub fn new() -> Self {
748 Self::default()
749 }
750
751 pub async fn insert(&mut self, hash: Hash, value: V) -> object_rainbow::Result<Option<V>> {
752 self.0
753 .fetch_mut()
754 .await?
755 .insert(hash.reinterpret(), value)
756 .await
757 }
758
759 pub async fn remove(&mut self, hash: Hash) -> object_rainbow::Result<Option<V>> {
760 self.0.fetch_mut().await?.remove(hash.reinterpret()).await
761 }
762
763 pub async fn get(&self, hash: Hash) -> object_rainbow::Result<Option<V>> {
764 self.0
765 .fetch()
766 .await?
767 .get(hash.reinterpret(), |value| value.clone())
768 .await
769 }
770
771 pub async fn contains(&self, hash: Hash) -> object_rainbow::Result<bool> {
772 self.0
773 .fetch()
774 .await?
775 .get(hash.reinterpret(), |_| {})
776 .await
777 .map(|o| o.is_some())
778 }
779
780 pub async fn append(&mut self, other: &mut Self) -> object_rainbow::Result<()> {
781 if self.0.hash() == other.0.hash() {
782 other.clear();
783 Ok(())
784 } else {
785 self.0
786 .fetch_mut()
787 .await?
788 .append(&mut *other.0.fetch_mut().await?)
789 .await
790 }
791 }
792
793 pub fn is_empty(&self) -> bool {
794 self.0.is_default()
795 }
796
797 pub fn clear(&mut self) {
798 std::mem::take(self);
799 }
800}
801
802#[derive(
803 ToOutput,
804 InlineOutput,
805 Tagged,
806 ListHashes,
807 Topological,
808 Parse,
809 ParseInline,
810 Size,
811 MaybeHasNiche,
812 Clone,
813 Default,
814 PartialEq,
815 Eq,
816)]
817pub struct HamtSet(HamtMap<()>);
818
819assert_impl!(
820 impl<E> Inline<E> for HamtSet where E: 'static + Send + Sync + Clone {}
821);
822
823impl HamtSet {
824 pub fn new() -> Self {
825 Self::default()
826 }
827
828 pub async fn insert(&mut self, hash: Hash) -> object_rainbow::Result<bool> {
829 Ok(self.0.insert(hash, ()).await?.is_none())
830 }
831
832 pub async fn remove(&mut self, hash: Hash) -> object_rainbow::Result<bool> {
833 Ok(self.0.remove(hash).await?.is_some())
834 }
835
836 pub async fn contains(&self, hash: Hash) -> object_rainbow::Result<bool> {
837 self.0.contains(hash).await
838 }
839
840 pub async fn append(&mut self, other: &mut Self) -> object_rainbow::Result<()> {
841 self.0.append(&mut other.0).await
842 }
843
844 pub async fn intersect(&mut self, other: &Self) -> object_rainbow::Result<()> {
845 if self.0.0.hash() == other.0.0.hash() {
846 Ok(())
847 } else {
848 self.0
849 .0
850 .fetch_mut()
851 .await?
852 .intersect(&other.0.0.fetch().await?)
853 .await
854 }
855 }
856
857 pub async fn subtract(&mut self, other: &Self) -> object_rainbow::Result<()> {
858 if self.0.0.hash() == other.0.0.hash() {
859 self.clear();
860 Ok(())
861 } else {
862 self.0
863 .0
864 .fetch_mut()
865 .await?
866 .subtract(&other.0.0.fetch().await?)
867 .await
868 }
869 }
870
871 pub fn is_empty(&self) -> bool {
872 self.0.is_empty()
873 }
874
875 pub fn clear(&mut self) {
876 std::mem::take(self);
877 }
878}
879
880#[cfg(test)]
881mod test {
882 use macro_rules_attribute::apply;
883 use object_rainbow::{FullHash, numeric::Le};
884 use smol_macros::test;
885
886 use crate::{HamtMap, HamtSet};
887
888 #[apply(test!)]
889 async fn test() -> object_rainbow::Result<()> {
890 let mut map = HamtMap::<Le<u16>>::new();
891 let empty_hash = map.full_hash();
892 for i in (0u16..=10_000).map(Le) {
893 map.insert(i.full_hash(), i).await?;
894 }
895 for i in (0u16..=10_000).map(Le) {
896 assert_eq!(map.get(i.full_hash()).await?, Some(i));
897 }
898 for i in (0u16..=10_000).map(Le) {
899 map.remove(i.full_hash()).await?;
900 }
901 assert_eq!(map.full_hash(), empty_hash);
902 Ok(())
903 }
904
905 #[apply(test!)]
906 async fn intersect() -> object_rainbow::Result<()> {
907 let mut l = HamtSet::new();
908 for i in 0u8..=254 {
909 l.insert((i, 1u8).full_hash()).await?;
910 l.insert((i, 3u8).full_hash()).await?;
911 }
912 let mut r = HamtSet::new();
913 for i in 0u8..=254 {
914 r.insert((i, 2u8).full_hash()).await?;
915 r.insert((i, 3u8).full_hash()).await?;
916 }
917 l.intersect(&r).await?;
918 for i in 0u8..=254 {
919 assert!(!l.contains((i, 1u8).full_hash()).await?);
920 assert!(!l.contains((i, 2u8).full_hash()).await?);
921 assert!(l.contains((i, 3u8).full_hash()).await?);
922 }
923 let mut r = HamtSet::new();
924 for i in 0u8..=254 {
925 r.insert((i, 1u8).full_hash()).await?;
926 r.insert((i, 2u8).full_hash()).await?;
927 }
928 l.intersect(&r).await?;
929 assert!(l.is_empty());
930 Ok(())
931 }
932
933 #[apply(test!)]
934 async fn subtract() -> object_rainbow::Result<()> {
935 let mut l = HamtSet::new();
936 for i in 0u8..=254 {
937 l.insert((i, 1u8).full_hash()).await?;
938 l.insert((i, 3u8).full_hash()).await?;
939 }
940 let mut r = HamtSet::new();
941 for i in 0u8..=254 {
942 r.insert((i, 2u8).full_hash()).await?;
943 r.insert((i, 3u8).full_hash()).await?;
944 }
945 l.subtract(&r).await?;
946 for i in 0u8..=254 {
947 assert!(l.contains((i, 1u8).full_hash()).await?);
948 assert!(!l.contains((i, 2u8).full_hash()).await?);
949 assert!(!l.contains((i, 3u8).full_hash()).await?);
950 }
951 let mut r = HamtSet::new();
952 for i in 0u8..=254 {
953 r.insert((i, 1u8).full_hash()).await?;
954 r.insert((i, 2u8).full_hash()).await?;
955 }
956 l.subtract(&r).await?;
957 assert!(l.is_empty());
958 Ok(())
959 }
960}