1use std::cmp::Ordering;
4use std::future::Future;
5use std::pin::Pin;
6use std::sync::Arc;
7
8use hashtree_core::{
9 Cid, DirEntry, HashTree, HashTreeConfig, HashTreeError, LinkType, Store, TreeEntry,
10};
11
12const DEFAULT_ORDER: usize = 32;
13
14#[derive(Debug, Clone, Default)]
15pub struct BTreeOptions {
16 pub order: Option<usize>,
17}
18
19#[derive(Debug, thiserror::Error)]
20pub enum BTreeError {
21 #[error("hash tree error: {0}")]
22 HashTree(#[from] HashTreeError),
23 #[error("value was not valid utf-8: {0}")]
24 Utf8(#[from] std::string::FromUtf8Error),
25}
26
27#[derive(Debug, Clone)]
28struct SplitResult {
29 left: Cid,
30 right: Cid,
31 left_first_key: String,
32 right_first_key: String,
33}
34
35#[derive(Debug, Clone)]
36enum InsertValue {
37 String(String),
38 Link(Cid),
39}
40
41type BTreeFuture<'a, T> = Pin<Box<dyn Future<Output = Result<T, BTreeError>> + 'a>>;
42
43pub struct BTree<S: Store> {
44 tree: HashTree<S>,
45 max_keys: usize,
46}
47
48#[derive(Debug, Clone)]
49struct BuiltNode {
50 first_key: String,
51 cid: Cid,
52}
53
54impl<S: Store> BTree<S> {
55 pub fn new(store: Arc<S>, options: BTreeOptions) -> Self {
56 let order = options.order.unwrap_or(DEFAULT_ORDER).max(2);
57 Self {
58 tree: HashTree::new(HashTreeConfig::new(store)),
59 max_keys: order - 1,
60 }
61 }
62
63 pub async fn insert(
64 &self,
65 root: Option<&Cid>,
66 key: &str,
67 value: &str,
68 ) -> Result<Cid, BTreeError> {
69 if let Some(root) = root {
70 if self.get(Some(root), key).await?.as_deref() == Some(value) {
71 return Ok(root.clone());
72 }
73
74 let result = self
75 .insert_recursive(
76 root.clone(),
77 key.to_string(),
78 InsertValue::String(value.to_string()),
79 )
80 .await?;
81 return self.finish_insert(result).await;
82 }
83
84 self.create_leaf(&[(key.to_string(), value.to_string())])
85 .await
86 }
87
88 pub async fn get(&self, root: Option<&Cid>, key: &str) -> Result<Option<String>, BTreeError> {
89 let Some(root) = root else {
90 return Ok(None);
91 };
92 self.get_recursive(root.clone(), key.to_string()).await
93 }
94
95 pub async fn insert_link(
96 &self,
97 root: Option<&Cid>,
98 key: &str,
99 target_cid: &Cid,
100 ) -> Result<Cid, BTreeError> {
101 if let Some(root) = root {
102 if self
103 .get_link(Some(root), key)
104 .await?
105 .is_some_and(|existing| cid_equals(&existing, target_cid))
106 {
107 return Ok(root.clone());
108 }
109
110 let result = self
111 .insert_recursive(
112 root.clone(),
113 key.to_string(),
114 InsertValue::Link(target_cid.clone()),
115 )
116 .await?;
117 return self.finish_insert(result).await;
118 }
119
120 self.create_leaf_with_links(&[(key.to_string(), target_cid.clone())])
121 .await
122 }
123
124 pub async fn insert_link_unchecked(
125 &self,
126 root: Option<&Cid>,
127 key: &str,
128 target_cid: &Cid,
129 ) -> Result<Cid, BTreeError> {
130 if let Some(root) = root {
131 let result = self
132 .insert_recursive(
133 root.clone(),
134 key.to_string(),
135 InsertValue::Link(target_cid.clone()),
136 )
137 .await?;
138 return self.finish_insert(result).await;
139 }
140
141 self.create_leaf_with_links(&[(key.to_string(), target_cid.clone())])
142 .await
143 }
144
145 pub async fn get_link(&self, root: Option<&Cid>, key: &str) -> Result<Option<Cid>, BTreeError> {
146 let Some(root) = root else {
147 return Ok(None);
148 };
149 self.get_link_recursive(root.clone(), key.to_string()).await
150 }
151
152 pub async fn entries(&self, root: Option<&Cid>) -> Result<Vec<(String, String)>, BTreeError> {
153 let Some(root) = root else {
154 return Ok(Vec::new());
155 };
156 self.traverse_in_order(root.clone()).await
157 }
158
159 pub async fn links_entries(
160 &self,
161 root: Option<&Cid>,
162 ) -> Result<Vec<(String, Cid)>, BTreeError> {
163 let Some(root) = root else {
164 return Ok(Vec::new());
165 };
166 self.traverse_links_in_order(root.clone()).await
167 }
168
169 pub async fn range(
170 &self,
171 root: &Cid,
172 start: Option<&str>,
173 end: Option<&str>,
174 ) -> Result<Vec<(String, String)>, BTreeError> {
175 self.range_traverse(
176 root.clone(),
177 start.map(ToOwned::to_owned),
178 end.map(ToOwned::to_owned),
179 )
180 .await
181 }
182
183 pub async fn prefix(
184 &self,
185 root: &Cid,
186 prefix: &str,
187 ) -> Result<Vec<(String, String)>, BTreeError> {
188 let end = increment_prefix(prefix);
189 self.range(root, Some(prefix), end.as_deref()).await
190 }
191
192 pub async fn prefix_links(
193 &self,
194 root: &Cid,
195 prefix: &str,
196 ) -> Result<Vec<(String, Cid)>, BTreeError> {
197 let end = increment_prefix(prefix);
198 self.range_link_traverse(root.clone(), Some(prefix.to_string()), end)
199 .await
200 }
201
202 pub async fn delete(&self, root: &Cid, key: &str) -> Result<Option<Cid>, BTreeError> {
203 self.delete_recursive(root.clone(), key.to_string()).await
204 }
205
206 pub async fn merge(
207 &self,
208 base: Option<&Cid>,
209 other: Option<&Cid>,
210 prefer_other: bool,
211 ) -> Result<Option<Cid>, BTreeError> {
212 let Some(other) = other else {
213 return Ok(base.cloned());
214 };
215 let Some(mut result) = base.cloned().or_else(|| Some(other.clone())) else {
216 return Ok(None);
217 };
218 if base.is_none() {
219 return Ok(Some(result));
220 }
221
222 for (key, value) in self.entries(Some(other)).await? {
223 let existing = self.get(Some(&result), &key).await?;
224 if existing.is_none() || prefer_other {
225 result = self.insert(Some(&result), &key, &value).await?;
226 }
227 }
228
229 Ok(Some(result))
230 }
231
232 pub async fn merge_links(
233 &self,
234 base: Option<&Cid>,
235 other: Option<&Cid>,
236 prefer_other: bool,
237 ) -> Result<Option<Cid>, BTreeError> {
238 let Some(other) = other else {
239 return Ok(base.cloned());
240 };
241 let Some(mut result) = base.cloned().or_else(|| Some(other.clone())) else {
242 return Ok(None);
243 };
244 if base.is_none() {
245 return Ok(Some(result));
246 }
247
248 for (key, value) in self.links_entries(Some(other)).await? {
249 let existing = self.get_link(Some(&result), &key).await?;
250 if existing.is_none() || prefer_other {
251 result = self.insert_link(Some(&result), &key, &value).await?;
252 }
253 }
254
255 Ok(Some(result))
256 }
257
258 pub async fn build<I>(&self, items: I) -> Result<Option<Cid>, BTreeError>
259 where
260 I: IntoIterator<Item = (String, String)>,
261 {
262 let mut sorted: Vec<(String, String)> = items.into_iter().collect();
263 if sorted.is_empty() {
264 return Ok(None);
265 }
266
267 sorted.sort_by(|left, right| left.0.cmp(&right.0));
268
269 let mut deduped = Vec::with_capacity(sorted.len());
270 for (key, value) in sorted {
271 if let Some((last_key, last_value)) = deduped.last_mut() {
272 if *last_key == key {
273 *last_value = value;
274 continue;
275 }
276 }
277 deduped.push((key, value));
278 }
279
280 let mut level = Vec::with_capacity(deduped.len().div_ceil(self.max_keys));
281 for chunk in deduped.chunks(self.max_keys) {
282 let cid = self.create_leaf(chunk).await?;
283 level.push(BuiltNode {
284 first_key: chunk[0].0.clone(),
285 cid,
286 });
287 }
288
289 while level.len() > 1 {
290 let mut next_level = Vec::with_capacity(level.len().div_ceil(self.max_keys));
291 for chunk in level.chunks(self.max_keys) {
292 let cid = self.create_internal_node(chunk).await?;
293 next_level.push(BuiltNode {
294 first_key: chunk[0].first_key.clone(),
295 cid,
296 });
297 }
298 level = next_level;
299 }
300
301 Ok(level.pop().map(|node| node.cid))
302 }
303
304 pub async fn build_links<I>(&self, items: I) -> Result<Option<Cid>, BTreeError>
305 where
306 I: IntoIterator<Item = (String, Cid)>,
307 {
308 let mut sorted: Vec<(String, Cid)> = items.into_iter().collect();
309 if sorted.is_empty() {
310 return Ok(None);
311 }
312
313 sorted.sort_by(|left, right| left.0.cmp(&right.0));
314
315 let mut deduped = Vec::with_capacity(sorted.len());
316 for (key, cid) in sorted {
317 if let Some((last_key, last_cid)) = deduped.last_mut() {
318 if *last_key == key {
319 *last_cid = cid;
320 continue;
321 }
322 }
323 deduped.push((key, cid));
324 }
325
326 let mut level = Vec::with_capacity(deduped.len().div_ceil(self.max_keys));
327 for chunk in deduped.chunks(self.max_keys) {
328 let cid = self.create_leaf_with_links(chunk).await?;
329 level.push(BuiltNode {
330 first_key: chunk[0].0.clone(),
331 cid,
332 });
333 }
334
335 while level.len() > 1 {
336 let mut next_level = Vec::with_capacity(level.len().div_ceil(self.max_keys));
337 for chunk in level.chunks(self.max_keys) {
338 let cid = self.create_internal_node(chunk).await?;
339 next_level.push(BuiltNode {
340 first_key: chunk[0].first_key.clone(),
341 cid,
342 });
343 }
344 level = next_level;
345 }
346
347 Ok(level.pop().map(|node| node.cid))
348 }
349
350 async fn finish_insert(&self, result: InsertResult) -> Result<Cid, BTreeError> {
351 if let Some(split) = result.split {
352 return self
353 .create_internal_root(
354 &split.left_first_key,
355 &split.left,
356 &split.right_first_key,
357 &split.right,
358 )
359 .await;
360 }
361 Ok(result.cid)
362 }
363
364 fn get_recursive<'a>(&'a self, root: Cid, key: String) -> BTreeFuture<'a, Option<String>> {
365 Box::pin(async move {
366 let entries = self.tree.list_directory(&root).await?;
367 if is_leaf_node(&entries) {
368 let escaped = escape_key(&key);
369 let Some(entry) = entries.iter().find(|entry| entry.name == escaped) else {
370 return Ok(None);
371 };
372 if entry.link_type != LinkType::Blob {
373 return Ok(None);
374 }
375
376 let cid = entry_cid(entry);
377 let Some(data) = self.tree.get(&cid, None).await? else {
378 return Ok(None);
379 };
380 return Ok(Some(String::from_utf8(data)?));
381 }
382
383 let child = find_child(&entries, &key);
384 self.get_recursive(entry_cid(&child), key).await
385 })
386 }
387
388 fn get_link_recursive<'a>(&'a self, root: Cid, key: String) -> BTreeFuture<'a, Option<Cid>> {
389 Box::pin(async move {
390 let entries = self.tree.list_directory(&root).await?;
391 if is_leaf_node(&entries) {
392 let escaped = escape_key(&key);
393 let Some(entry) = entries.iter().find(|entry| entry.name == escaped) else {
394 return Ok(None);
395 };
396 if entry.link_type != LinkType::File {
397 return Ok(None);
398 }
399 return Ok(Some(entry_cid(entry)));
400 }
401
402 let child = find_child(&entries, &key);
403 self.get_link_recursive(entry_cid(&child), key).await
404 })
405 }
406
407 fn insert_recursive<'a>(
408 &'a self,
409 node: Cid,
410 key: String,
411 value: InsertValue,
412 ) -> BTreeFuture<'a, InsertResult> {
413 Box::pin(async move {
414 let entries = self.tree.list_directory(&node).await?;
415 if is_leaf_node(&entries) {
416 return self.insert_into_leaf(node, entries, key, value).await;
417 }
418 self.insert_into_internal(node, entries, key, value).await
419 })
420 }
421
422 fn insert_into_leaf<'a>(
423 &'a self,
424 node: Cid,
425 _entries: Vec<TreeEntry>,
426 key: String,
427 value: InsertValue,
428 ) -> BTreeFuture<'a, InsertResult> {
429 Box::pin(async move {
430 let escaped_key = escape_key(&key);
431 let (entry_cid, size, link_type) = match value {
432 InsertValue::String(value) => {
433 let (cid, size) = self.tree.put_file(value.as_bytes()).await?;
434 (cid, size, LinkType::Blob)
435 }
436 InsertValue::Link(cid) => (cid, 0, LinkType::File),
437 };
438
439 let new_node = self
440 .tree
441 .set_entry(&node, &[], &escaped_key, &entry_cid, size, link_type)
442 .await?;
443
444 let new_entries = self.tree.list_directory(&new_node).await?;
445 if new_entries.len() > self.max_keys {
446 return Ok(InsertResult {
447 cid: new_node,
448 split: Some(self.split_leaf(new_entries).await?),
449 });
450 }
451
452 Ok(InsertResult {
453 cid: new_node,
454 split: None,
455 })
456 })
457 }
458
459 fn insert_into_internal<'a>(
460 &'a self,
461 node: Cid,
462 entries: Vec<TreeEntry>,
463 key: String,
464 value: InsertValue,
465 ) -> BTreeFuture<'a, InsertResult> {
466 Box::pin(async move {
467 let child = find_child(&entries, &key);
468 let child_name = child.name.clone();
469 let child_cid = entry_cid(&child);
470 let result = self.insert_recursive(child_cid, key, value).await?;
471
472 let mut new_node = self
473 .tree
474 .set_entry(&node, &[], &child_name, &result.cid, 0, LinkType::Dir)
475 .await?;
476
477 if let Some(split) = result.split {
478 new_node = self.tree.remove_entry(&new_node, &[], &child_name).await?;
479 new_node = self
480 .tree
481 .set_entry(
482 &new_node,
483 &[],
484 &escape_key(&split.left_first_key),
485 &split.left,
486 0,
487 LinkType::Dir,
488 )
489 .await?;
490 new_node = self
491 .tree
492 .set_entry(
493 &new_node,
494 &[],
495 &escape_key(&split.right_first_key),
496 &split.right,
497 0,
498 LinkType::Dir,
499 )
500 .await?;
501 }
502
503 let new_entries = self.tree.list_directory(&new_node).await?;
504 if new_entries.len() > self.max_keys {
505 return Ok(InsertResult {
506 cid: new_node,
507 split: Some(self.split_internal(new_entries).await?),
508 });
509 }
510
511 Ok(InsertResult {
512 cid: new_node,
513 split: None,
514 })
515 })
516 }
517
518 async fn split_leaf(&self, entries: Vec<TreeEntry>) -> Result<SplitResult, BTreeError> {
519 let sorted = sort_entries(entries);
520 let mid = sorted.len() / 2;
521 let left_entries = &sorted[..mid];
522 let right_entries = &sorted[mid..];
523
524 let left = self.create_node_from_entries(left_entries).await?;
525 let right = self.create_node_from_entries(right_entries).await?;
526
527 Ok(SplitResult {
528 left,
529 right,
530 left_first_key: unescape_key(&left_entries[0].name),
531 right_first_key: unescape_key(&right_entries[0].name),
532 })
533 }
534
535 async fn split_internal(&self, entries: Vec<TreeEntry>) -> Result<SplitResult, BTreeError> {
536 let sorted = sort_entries(entries);
537 let mid = sorted.len() / 2;
538 let left_entries = &sorted[..mid];
539 let right_entries = &sorted[mid..];
540
541 let left = self.create_node_from_entries(left_entries).await?;
542 let right = self.create_node_from_entries(right_entries).await?;
543
544 Ok(SplitResult {
545 left,
546 right,
547 left_first_key: unescape_key(&left_entries[0].name),
548 right_first_key: unescape_key(&right_entries[0].name),
549 })
550 }
551
552 async fn create_leaf(&self, items: &[(String, String)]) -> Result<Cid, BTreeError> {
553 let mut entries = Vec::with_capacity(items.len());
554 for (key, value) in items {
555 let (cid, size) = self.tree.put_file(value.as_bytes()).await?;
556 entries.push(
557 DirEntry::from_cid(escape_key(key), &cid)
558 .with_size(size)
559 .with_link_type(LinkType::Blob),
560 );
561 }
562 Ok(self.tree.put_directory(entries).await?)
563 }
564
565 async fn create_leaf_with_links(&self, items: &[(String, Cid)]) -> Result<Cid, BTreeError> {
566 let entries: Vec<DirEntry> = items
567 .iter()
568 .map(|(key, cid)| {
569 DirEntry::from_cid(escape_key(key), cid).with_link_type(LinkType::File)
570 })
571 .collect();
572 Ok(self.tree.put_directory(entries).await?)
573 }
574
575 async fn create_internal_node(&self, children: &[BuiltNode]) -> Result<Cid, BTreeError> {
576 let entries: Vec<DirEntry> = children
577 .iter()
578 .map(|child| {
579 DirEntry::from_cid(escape_key(&child.first_key), &child.cid)
580 .with_link_type(LinkType::Dir)
581 })
582 .collect();
583 Ok(self.tree.put_directory(entries).await?)
584 }
585
586 async fn create_internal_root(
587 &self,
588 left_key: &str,
589 left: &Cid,
590 right_key: &str,
591 right: &Cid,
592 ) -> Result<Cid, BTreeError> {
593 let entries = vec![
594 DirEntry::from_cid(escape_key(left_key), left).with_link_type(LinkType::Dir),
595 DirEntry::from_cid(escape_key(right_key), right).with_link_type(LinkType::Dir),
596 ];
597 Ok(self.tree.put_directory(entries).await?)
598 }
599
600 async fn create_node_from_entries(&self, entries: &[TreeEntry]) -> Result<Cid, BTreeError> {
601 let dir_entries = entries
602 .iter()
603 .cloned()
604 .map(tree_entry_to_dir_entry)
605 .collect::<Vec<_>>();
606 Ok(self.tree.put_directory(dir_entries).await?)
607 }
608
609 fn delete_recursive<'a>(&'a self, root: Cid, key: String) -> BTreeFuture<'a, Option<Cid>> {
610 Box::pin(async move {
611 let entries = self.tree.list_directory(&root).await?;
612 if is_leaf_node(&entries) {
613 let escaped = escape_key(&key);
614 if !entries.iter().any(|entry| entry.name == escaped) {
615 return Ok(Some(root));
616 }
617
618 let new_root = self.tree.remove_entry(&root, &[], &escaped).await?;
619 let new_entries = self.tree.list_directory(&new_root).await?;
620 if new_entries.is_empty() {
621 return Ok(None);
622 }
623 return Ok(Some(new_root));
624 }
625
626 let child = find_child(&entries, &key);
627 let child_name = child.name.clone();
628 let new_child = self.delete_recursive(entry_cid(&child), key).await?;
629
630 let Some(new_child) = new_child else {
631 let new_root = self.tree.remove_entry(&root, &[], &child_name).await?;
632 let new_entries = self.tree.list_directory(&new_root).await?;
633 if new_entries.is_empty() {
634 return Ok(None);
635 }
636 if new_entries.len() == 1 && new_entries[0].link_type == LinkType::Dir {
637 return Ok(Some(entry_cid(&new_entries[0])));
638 }
639 return Ok(Some(new_root));
640 };
641
642 if cid_equals(&new_child, &entry_cid(&child)) {
643 return Ok(Some(root));
644 }
645
646 let updated = self
647 .tree
648 .set_entry(&root, &[], &child_name, &new_child, 0, LinkType::Dir)
649 .await?;
650 Ok(Some(updated))
651 })
652 }
653
654 fn traverse_in_order<'a>(&'a self, node: Cid) -> BTreeFuture<'a, Vec<(String, String)>> {
655 Box::pin(async move {
656 let entries = self.tree.list_directory(&node).await?;
657 let sorted = sort_entries(entries);
658 let mut out = Vec::new();
659
660 if is_leaf_node(&sorted) {
661 for entry in sorted {
662 if entry.link_type != LinkType::Blob {
663 continue;
664 }
665 let cid = entry_cid(&entry);
666 if let Some(data) = self.tree.get(&cid, None).await? {
667 out.push((unescape_key(&entry.name), String::from_utf8(data)?));
668 }
669 }
670 return Ok(out);
671 }
672
673 for child in sorted {
674 out.extend(self.traverse_in_order(entry_cid(&child)).await?);
675 }
676 Ok(out)
677 })
678 }
679
680 fn traverse_links_in_order<'a>(&'a self, node: Cid) -> BTreeFuture<'a, Vec<(String, Cid)>> {
681 Box::pin(async move {
682 let entries = self.tree.list_directory(&node).await?;
683 let sorted = sort_entries(entries);
684 let mut out = Vec::new();
685
686 if is_leaf_node(&sorted) {
687 for entry in sorted {
688 if entry.link_type == LinkType::File {
689 out.push((unescape_key(&entry.name), entry_cid(&entry)));
690 }
691 }
692 return Ok(out);
693 }
694
695 for child in sorted {
696 out.extend(self.traverse_links_in_order(entry_cid(&child)).await?);
697 }
698 Ok(out)
699 })
700 }
701
702 fn range_traverse<'a>(
703 &'a self,
704 node: Cid,
705 start: Option<String>,
706 end: Option<String>,
707 ) -> BTreeFuture<'a, Vec<(String, String)>> {
708 Box::pin(async move {
709 let entries = self.tree.list_directory(&node).await?;
710 let sorted = sort_entries(entries);
711 let mut out = Vec::new();
712
713 if is_leaf_node(&sorted) {
714 for entry in sorted {
715 if entry.link_type != LinkType::Blob {
716 continue;
717 }
718 let key = unescape_key(&entry.name);
719 if start.as_ref().is_some_and(|start| key < *start) {
720 continue;
721 }
722 if end.as_ref().is_some_and(|end| key >= *end) {
723 return Ok(out);
724 }
725
726 let cid = entry_cid(&entry);
727 if let Some(data) = self.tree.get(&cid, None).await? {
728 out.push((key, String::from_utf8(data)?));
729 }
730 }
731 return Ok(out);
732 }
733
734 for (index, child) in sorted.iter().enumerate() {
735 let child_min = unescape_key(&child.name);
736 let child_max = sorted.get(index + 1).map(|entry| unescape_key(&entry.name));
737
738 if start.as_ref().is_some_and(|start| {
739 child_max
740 .as_ref()
741 .is_some_and(|child_max| child_max <= start)
742 }) {
743 continue;
744 }
745 if end.as_ref().is_some_and(|end| child_min >= *end) {
746 return Ok(out);
747 }
748
749 out.extend(
750 self.range_traverse(entry_cid(child), start.clone(), end.clone())
751 .await?,
752 );
753 }
754
755 Ok(out)
756 })
757 }
758
759 fn range_link_traverse<'a>(
760 &'a self,
761 node: Cid,
762 start: Option<String>,
763 end: Option<String>,
764 ) -> BTreeFuture<'a, Vec<(String, Cid)>> {
765 Box::pin(async move {
766 let entries = self.tree.list_directory(&node).await?;
767 let sorted = sort_entries(entries);
768 let mut out = Vec::new();
769
770 if is_leaf_node(&sorted) {
771 for entry in sorted {
772 if entry.link_type != LinkType::File {
773 continue;
774 }
775 let key = unescape_key(&entry.name);
776 if start.as_ref().is_some_and(|start| key < *start) {
777 continue;
778 }
779 if end.as_ref().is_some_and(|end| key >= *end) {
780 return Ok(out);
781 }
782 out.push((key, entry_cid(&entry)));
783 }
784 return Ok(out);
785 }
786
787 for (index, child) in sorted.iter().enumerate() {
788 let child_min = unescape_key(&child.name);
789 let child_max = sorted.get(index + 1).map(|entry| unescape_key(&entry.name));
790
791 if start.as_ref().is_some_and(|start| {
792 child_max
793 .as_ref()
794 .is_some_and(|child_max| child_max <= start)
795 }) {
796 continue;
797 }
798 if end.as_ref().is_some_and(|end| child_min >= *end) {
799 return Ok(out);
800 }
801
802 out.extend(
803 self.range_link_traverse(entry_cid(child), start.clone(), end.clone())
804 .await?,
805 );
806 }
807
808 Ok(out)
809 })
810 }
811}
812
813#[derive(Debug, Clone)]
814struct InsertResult {
815 cid: Cid,
816 split: Option<SplitResult>,
817}
818
819pub fn escape_key(key: &str) -> String {
820 key.replace('%', "%25")
821 .replace('/', "%2F")
822 .replace('\0', "%00")
823}
824
825pub fn unescape_key(name: &str) -> String {
826 name.replace("%2F", "/")
827 .replace("%2f", "/")
828 .replace("%00", "\0")
829 .replace("%25", "%")
830}
831
832fn increment_prefix(value: &str) -> Option<String> {
833 if value.is_empty() {
834 return Some(String::new());
835 }
836
837 let mut chars: Vec<char> = value.chars().collect();
838 let last = chars.pop()?;
839 let next = char::from_u32(last as u32 + 1)?;
840 chars.push(next);
841 Some(chars.into_iter().collect())
842}
843
844fn cid_equals(left: &Cid, right: &Cid) -> bool {
845 left.hash == right.hash && left.key == right.key
846}
847
848fn is_leaf_node(entries: &[TreeEntry]) -> bool {
849 entries.is_empty() || entries.iter().any(|entry| entry.link_type != LinkType::Dir)
850}
851
852fn sort_entries(mut entries: Vec<TreeEntry>) -> Vec<TreeEntry> {
853 entries.sort_by(|left, right| compare_unescaped_names(&left.name, &right.name));
854 entries
855}
856
857fn compare_unescaped_names(left: &str, right: &str) -> Ordering {
858 unescape_key(left).cmp(&unescape_key(right))
859}
860
861fn find_child(entries: &[TreeEntry], key: &str) -> TreeEntry {
862 let sorted = sort_entries(entries.to_vec());
863 for window in sorted.windows(2) {
864 let next_name = unescape_key(&window[1].name);
865 if key < next_name.as_str() {
866 return window[0].clone();
867 }
868 }
869 sorted
870 .last()
871 .cloned()
872 .expect("internal nodes must have children")
873}
874
875fn entry_cid(entry: &TreeEntry) -> Cid {
876 Cid {
877 hash: entry.hash,
878 key: entry.key,
879 }
880}
881
882fn tree_entry_to_dir_entry(entry: TreeEntry) -> DirEntry {
883 let mut out = DirEntry::from_cid(&entry.name, &entry_cid(&entry))
884 .with_size(entry.size)
885 .with_link_type(entry.link_type);
886 if let Some(meta) = entry.meta {
887 out = out.with_meta(meta);
888 }
889 out
890}