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

hashtree_index/
lib.rs
