hashtree_index/
lib.rs

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

hashtree_index/
lib.rs
