outlook_pst/ndb/
block.rs

1//! [Blocks](https://learn.microsoft.com/en-us/openspecs/office_file_formats/ms-pst/a9c1981d-d1ea-457c-b39e-dc7fb0eb95d4)
2
3use byteorder::{LittleEndian, ReadBytesExt, WriteBytesExt};
4use std::{
5    collections::{btree_map, BTreeMap, VecDeque},
6    io::{self, Cursor, Read, Seek, SeekFrom, Write},
7    iter,
8};
9use tracing::error;
10
11use super::{block_id::*, block_ref::*, byte_index::*, node_id::*, page::*, read_write::*, *};
12use crate::{AnsiPstFile, PstFile, PstFileReadWriteBlockBTree, PstReader, UnicodePstFile};
13
14pub const MAX_BLOCK_SIZE: u16 = 8192;
15
16pub const fn block_size(size: u16) -> u16 {
17    assert!(size > 0);
18    assert!(size <= MAX_BLOCK_SIZE);
19    size.div_ceil(64) * 64
20}
21
22/// [BLOCKTRAILER](https://learn.microsoft.com/en-us/openspecs/office_file_formats/ms-pst/a14943ef-70c2-403f-898c-5bc3747117e1)
23pub trait BlockTrailer {
24    type BlockId: BlockId;
25
26    fn size(&self) -> u16;
27    fn signature(&self) -> u16;
28    fn crc(&self) -> u32;
29    fn block_id(&self) -> Self::BlockId;
30    fn cyclic_key(&self) -> u32;
31    fn verify_block_id(&self, is_internal: bool) -> NdbResult<()>;
32}
33
34#[derive(Clone, Copy, Default)]
35pub struct UnicodeBlockTrailer {
36    size: u16,
37    signature: u16,
38    crc: u32,
39    block_id: UnicodeBlockId,
40}
41
42impl UnicodeBlockTrailer {
43    pub fn new(size: u16, signature: u16, crc: u32, block_id: UnicodeBlockId) -> NdbResult<Self> {
44        if !(1..=(MAX_BLOCK_SIZE - Self::SIZE)).contains(&size) {
45            return Err(NdbError::InvalidBlockSize(size));
46        }
47
48        Ok(Self {
49            size,
50            block_id,
51            signature,
52            crc,
53        })
54    }
55}
56
57impl BlockTrailer for UnicodeBlockTrailer {
58    type BlockId = UnicodeBlockId;
59
60    fn size(&self) -> u16 {
61        self.size
62    }
63
64    fn signature(&self) -> u16 {
65        self.signature
66    }
67
68    fn crc(&self) -> u32 {
69        self.crc
70    }
71
72    fn block_id(&self) -> UnicodeBlockId {
73        self.block_id
74    }
75
76    fn cyclic_key(&self) -> u32 {
77        self.block_id.search_key() as u32
78    }
79
80    fn verify_block_id(&self, is_internal: bool) -> NdbResult<()> {
81        if self.block_id.is_internal() != is_internal {
82            return Err(NdbError::InvalidUnicodeBlockTrailerId(u64::from(
83                self.block_id,
84            )));
85        }
86        Ok(())
87    }
88}
89
90impl BlockTrailerReadWrite for UnicodeBlockTrailer {
91    const SIZE: u16 = 16;
92
93    fn new(size: u16, signature: u16, crc: u32, block_id: UnicodeBlockId) -> NdbResult<Self> {
94        Self::new(size, signature, crc, block_id)
95    }
96
97    fn read(f: &mut dyn Read) -> io::Result<Self> {
98        let size = f.read_u16::<LittleEndian>()?;
99        if !(1..=(MAX_BLOCK_SIZE - Self::SIZE)).contains(&size) {
100            return Err(NdbError::InvalidBlockSize(size).into());
101        }
102
103        let signature = f.read_u16::<LittleEndian>()?;
104        let crc = f.read_u32::<LittleEndian>()?;
105        let block_id = UnicodeBlockId::read(f)?;
106
107        Ok(Self {
108            size,
109            signature,
110            crc,
111            block_id,
112        })
113    }
114
115    fn write(&self, f: &mut dyn Write) -> io::Result<()> {
116        f.write_u16::<LittleEndian>(self.size)?;
117        f.write_u16::<LittleEndian>(self.signature)?;
118        f.write_u32::<LittleEndian>(self.crc)?;
119        self.block_id.write(f)
120    }
121}
122
123#[derive(Clone, Copy, Default)]
124pub struct AnsiBlockTrailer {
125    size: u16,
126    signature: u16,
127    block_id: AnsiBlockId,
128    crc: u32,
129}
130
131impl AnsiBlockTrailer {
132    pub fn new(size: u16, signature: u16, crc: u32, block_id: AnsiBlockId) -> NdbResult<Self> {
133        if !(1..=(MAX_BLOCK_SIZE - Self::SIZE)).contains(&size) {
134            return Err(NdbError::InvalidBlockSize(size));
135        }
136
137        Ok(Self {
138            size,
139            signature,
140            block_id,
141            crc,
142        })
143    }
144}
145
146impl BlockTrailer for AnsiBlockTrailer {
147    type BlockId = AnsiBlockId;
148
149    fn size(&self) -> u16 {
150        self.size
151    }
152
153    fn signature(&self) -> u16 {
154        self.signature
155    }
156
157    fn crc(&self) -> u32 {
158        self.crc
159    }
160
161    fn block_id(&self) -> AnsiBlockId {
162        self.block_id
163    }
164
165    fn cyclic_key(&self) -> u32 {
166        self.block_id.search_key()
167    }
168
169    fn verify_block_id(&self, is_internal: bool) -> NdbResult<()> {
170        if self.block_id.is_internal() != is_internal {
171            return Err(NdbError::InvalidAnsiBlockTrailerId(u32::from(
172                self.block_id,
173            )));
174        }
175        Ok(())
176    }
177}
178
179impl BlockTrailerReadWrite for AnsiBlockTrailer {
180    const SIZE: u16 = 12;
181
182    fn new(size: u16, signature: u16, crc: u32, block_id: AnsiBlockId) -> NdbResult<Self> {
183        Self::new(size, signature, crc, block_id)
184    }
185
186    fn read(f: &mut dyn Read) -> io::Result<Self> {
187        let size = f.read_u16::<LittleEndian>()?;
188        if !(1..=(MAX_BLOCK_SIZE - Self::SIZE)).contains(&size) {
189            return Err(NdbError::InvalidBlockSize(size).into());
190        }
191
192        let signature = f.read_u16::<LittleEndian>()?;
193        let block_id = AnsiBlockId::read(f)?;
194        let crc = f.read_u32::<LittleEndian>()?;
195
196        Ok(Self {
197            size,
198            signature,
199            block_id,
200            crc,
201        })
202    }
203
204    fn write(&self, f: &mut dyn Write) -> io::Result<()> {
205        f.write_u16::<LittleEndian>(self.size)?;
206        f.write_u16::<LittleEndian>(self.signature)?;
207        self.block_id.write(f)?;
208        f.write_u32::<LittleEndian>(self.crc)
209    }
210}
211
212/// [Data Blocks](https://learn.microsoft.com/en-us/openspecs/office_file_formats/ms-pst/d0e6fbaf-00e3-4d4d-bea8-8ab3cdb4fde6)
213pub trait Block {
214    type Trailer: BlockTrailer;
215
216    fn encoding(&self) -> NdbCryptMethod;
217    fn data(&self) -> &[u8];
218    fn trailer(&self) -> &Self::Trailer;
219}
220
221#[derive(Clone, Default)]
222pub struct UnicodeDataBlock {
223    encoding: NdbCryptMethod,
224    data: Vec<u8>,
225    trailer: UnicodeBlockTrailer,
226}
227
228impl UnicodeDataBlock {
229    pub fn new(
230        encoding: NdbCryptMethod,
231        data: Vec<u8>,
232        trailer: UnicodeBlockTrailer,
233    ) -> NdbResult<Self> {
234        Ok(Self {
235            data,
236            encoding,
237            trailer,
238        })
239    }
240}
241
242impl Block for UnicodeDataBlock {
243    type Trailer = UnicodeBlockTrailer;
244
245    fn encoding(&self) -> NdbCryptMethod {
246        self.encoding
247    }
248
249    fn data(&self) -> &[u8] {
250        &self.data
251    }
252
253    fn trailer(&self) -> &UnicodeBlockTrailer {
254        &self.trailer
255    }
256}
257
258impl BlockReadWrite for UnicodeDataBlock {
259    fn new(
260        encoding: NdbCryptMethod,
261        data: Vec<u8>,
262        trailer: UnicodeBlockTrailer,
263    ) -> NdbResult<Self> {
264        Self::new(encoding, data, trailer)
265    }
266}
267
268impl From<UnicodeDataBlock> for Vec<u8> {
269    fn from(value: UnicodeDataBlock) -> Self {
270        value.data
271    }
272}
273
274#[derive(Clone, Default)]
275pub struct AnsiDataBlock {
276    encoding: NdbCryptMethod,
277    data: Vec<u8>,
278    trailer: AnsiBlockTrailer,
279}
280
281impl AnsiDataBlock {
282    pub fn new(
283        encoding: NdbCryptMethod,
284        data: Vec<u8>,
285        trailer: AnsiBlockTrailer,
286    ) -> NdbResult<Self> {
287        Ok(Self {
288            data,
289            encoding,
290            trailer,
291        })
292    }
293}
294
295impl Block for AnsiDataBlock {
296    type Trailer = AnsiBlockTrailer;
297
298    fn encoding(&self) -> NdbCryptMethod {
299        self.encoding
300    }
301
302    fn data(&self) -> &[u8] {
303        &self.data
304    }
305
306    fn trailer(&self) -> &AnsiBlockTrailer {
307        &self.trailer
308    }
309}
310
311impl BlockReadWrite for AnsiDataBlock {
312    fn new(encoding: NdbCryptMethod, data: Vec<u8>, trailer: AnsiBlockTrailer) -> NdbResult<Self> {
313        Self::new(encoding, data, trailer)
314    }
315}
316
317impl From<AnsiDataBlock> for Vec<u8> {
318    fn from(value: AnsiDataBlock) -> Self {
319        value.data
320    }
321}
322
323pub trait IntermediateTreeHeader {
324    fn level(&self) -> u8;
325    fn entry_count(&self) -> u16;
326}
327
328pub trait IntermediateTreeEntry {}
329
330pub trait IntermediateTreeBlock {
331    type Header: IntermediateTreeHeader;
332    type Entry: IntermediateTreeEntry;
333    type Trailer: BlockTrailer;
334
335    fn header(&self) -> &Self::Header;
336    fn entries(&self) -> &[Self::Entry];
337    fn trailer(&self) -> &Self::Trailer;
338}
339
340#[derive(Clone, Copy, Default)]
341pub struct DataTreeBlockHeader {
342    level: u8,
343    entry_count: u16,
344    total_size: u32,
345}
346
347impl DataTreeBlockHeader {
348    pub fn new(level: u8, entry_count: u16, total_size: u32) -> Self {
349        Self {
350            level,
351            entry_count,
352            total_size,
353        }
354    }
355
356    pub fn total_size(&self) -> u32 {
357        self.total_size
358    }
359}
360
361impl IntermediateTreeHeader for DataTreeBlockHeader {
362    fn level(&self) -> u8 {
363        self.level
364    }
365
366    fn entry_count(&self) -> u16 {
367        self.entry_count
368    }
369}
370
371impl IntermediateTreeHeaderReadWrite for DataTreeBlockHeader {
372    const HEADER_SIZE: u16 = 8;
373
374    fn read(f: &mut dyn Read) -> io::Result<Self> {
375        let block_type = f.read_u8()?;
376        if block_type != 0x01 {
377            return Err(NdbError::InvalidInternalBlockType(block_type).into());
378        }
379
380        let level = f.read_u8()?;
381        let entry_count = f.read_u16::<LittleEndian>()?;
382        let total_size = f.read_u32::<LittleEndian>()?;
383
384        Ok(Self {
385            level,
386            entry_count,
387            total_size,
388        })
389    }
390
391    fn write(&self, f: &mut dyn Write) -> io::Result<()> {
392        f.write_u8(0x01)?;
393        f.write_u8(self.level)?;
394        f.write_u16::<LittleEndian>(self.entry_count)?;
395        f.write_u32::<LittleEndian>(self.total_size)
396    }
397}
398
399pub trait IntermediateDataTreeEntry<Pst>: IntermediateTreeEntry
400where
401    Pst: PstFile,
402{
403    fn new(block: <Pst as PstFile>::BlockId) -> Self;
404    fn block(&self) -> <Pst as PstFile>::BlockId;
405}
406
407#[derive(Clone, Copy, Default)]
408pub struct UnicodeDataTreeEntry(UnicodeBlockId);
409
410impl IntermediateTreeEntry for UnicodeDataTreeEntry {}
411
412impl IntermediateDataTreeEntry<UnicodePstFile> for UnicodeDataTreeEntry {
413    fn new(block: UnicodeBlockId) -> Self {
414        Self(block)
415    }
416
417    fn block(&self) -> UnicodeBlockId {
418        self.0
419    }
420}
421
422impl IntermediateTreeEntryReadWrite for UnicodeDataTreeEntry {
423    const ENTRY_SIZE: u16 = 8;
424
425    fn read(f: &mut dyn Read) -> io::Result<Self> {
426        Ok(Self(UnicodeBlockId::read(f)?))
427    }
428
429    fn write(&self, f: &mut dyn Write) -> io::Result<()> {
430        self.0.write(f)
431    }
432}
433
434impl From<UnicodeBlockId> for UnicodeDataTreeEntry {
435    fn from(value: UnicodeBlockId) -> Self {
436        Self::new(value)
437    }
438}
439
440impl From<UnicodeDataTreeEntry> for UnicodeBlockId {
441    fn from(value: UnicodeDataTreeEntry) -> Self {
442        value.block()
443    }
444}
445
446#[derive(Clone, Copy, Default)]
447pub struct AnsiDataTreeEntry(AnsiBlockId);
448
449impl IntermediateTreeEntry for AnsiDataTreeEntry {}
450
451impl IntermediateDataTreeEntry<AnsiPstFile> for AnsiDataTreeEntry {
452    fn new(block: AnsiBlockId) -> Self {
453        Self(block)
454    }
455
456    fn block(&self) -> AnsiBlockId {
457        self.0
458    }
459}
460
461impl IntermediateTreeEntryReadWrite for AnsiDataTreeEntry {
462    const ENTRY_SIZE: u16 = 4;
463
464    fn read(f: &mut dyn Read) -> io::Result<Self> {
465        Ok(Self(AnsiBlockId::read(f)?))
466    }
467
468    fn write(&self, f: &mut dyn Write) -> io::Result<()> {
469        self.0.write(f)
470    }
471}
472
473impl From<AnsiBlockId> for AnsiDataTreeEntry {
474    fn from(value: AnsiBlockId) -> Self {
475        Self::new(value)
476    }
477}
478
479impl From<AnsiDataTreeEntry> for AnsiBlockId {
480    fn from(value: AnsiDataTreeEntry) -> Self {
481        value.block()
482    }
483}
484
485/// [XBLOCK](https://learn.microsoft.com/en-us/openspecs/office_file_formats/ms-pst/5b7a6935-e83d-4917-9f62-6ce3707f09e0)
486/// / [XXBLOCK](https://learn.microsoft.com/en-us/openspecs/office_file_formats/ms-pst/061b6ac4-d1da-468c-b75d-0303a0a8f468)
487struct DataTreeBlockInner<Entry, Trailer>
488where
489    Entry: IntermediateTreeEntry,
490    Trailer: BlockTrailer,
491{
492    header: DataTreeBlockHeader,
493    entries: Vec<Entry>,
494    trailer: Trailer,
495}
496
497impl<Entry, Trailer> DataTreeBlockInner<Entry, Trailer>
498where
499    Entry: IntermediateTreeEntry,
500    Trailer: BlockTrailer,
501{
502    pub fn new(
503        header: DataTreeBlockHeader,
504        entries: Vec<Entry>,
505        trailer: Trailer,
506    ) -> NdbResult<Self> {
507        trailer.verify_block_id(true)?;
508
509        Ok(Self {
510            header,
511            entries,
512            trailer,
513        })
514    }
515}
516
517pub struct UnicodeDataTreeBlock {
518    inner: DataTreeBlockInner<UnicodeDataTreeEntry, UnicodeBlockTrailer>,
519}
520
521impl IntermediateTreeBlock for UnicodeDataTreeBlock {
522    type Header = DataTreeBlockHeader;
523    type Entry = UnicodeDataTreeEntry;
524    type Trailer = UnicodeBlockTrailer;
525
526    fn header(&self) -> &Self::Header {
527        &self.inner.header
528    }
529
530    fn entries(&self) -> &[Self::Entry] {
531        &self.inner.entries
532    }
533
534    fn trailer(&self) -> &Self::Trailer {
535        &self.inner.trailer
536    }
537}
538
539impl IntermediateTreeBlockReadWrite for UnicodeDataTreeBlock {
540    fn new(
541        header: DataTreeBlockHeader,
542        entries: Vec<UnicodeDataTreeEntry>,
543        trailer: UnicodeBlockTrailer,
544    ) -> NdbResult<Self> {
545        Ok(Self {
546            inner: DataTreeBlockInner::new(header, entries, trailer)?,
547        })
548    }
549}
550
551pub struct AnsiDataTreeBlock {
552    inner: DataTreeBlockInner<AnsiDataTreeEntry, AnsiBlockTrailer>,
553}
554
555impl IntermediateTreeBlock for AnsiDataTreeBlock {
556    type Header = DataTreeBlockHeader;
557    type Entry = AnsiDataTreeEntry;
558    type Trailer = AnsiBlockTrailer;
559
560    fn header(&self) -> &Self::Header {
561        &self.inner.header
562    }
563
564    fn entries(&self) -> &[Self::Entry] {
565        &self.inner.entries
566    }
567
568    fn trailer(&self) -> &Self::Trailer {
569        &self.inner.trailer
570    }
571}
572
573impl IntermediateTreeBlockReadWrite for AnsiDataTreeBlock {
574    fn new(
575        header: DataTreeBlockHeader,
576        entries: Vec<AnsiDataTreeEntry>,
577        trailer: AnsiBlockTrailer,
578    ) -> NdbResult<Self> {
579        Ok(Self {
580            inner: DataTreeBlockInner::new(header, entries, trailer)?,
581        })
582    }
583}
584
585pub type DataBlockCache<Pst> = BTreeMap<<Pst as PstFile>::BlockId, DataTree<Pst>>;
586
587pub enum DataTree<Pst>
588where
589    Pst: PstFile,
590{
591    Intermediate(Box<<Pst as PstFile>::DataTreeBlock>),
592    Leaf(Box<<Pst as PstFile>::DataBlock>),
593}
594
595impl<Pst> DataTree<Pst>
596where
597    Pst: PstFile,
598    <Pst as PstFile>::BlockTrailer: BlockTrailerReadWrite,
599    <Pst as PstFile>::DataTreeBlock: IntermediateTreeBlockReadWrite,
600    <<Pst as PstFile>::DataTreeBlock as IntermediateTreeBlock>::Entry:
601        IntermediateTreeEntryReadWrite,
602    <Pst as PstFile>::DataBlock: BlockReadWrite,
603{
604    pub fn read<R>(
605        f: &mut R,
606        encoding: NdbCryptMethod,
607        block: &<Pst as PstFile>::BlockBTreeEntry,
608    ) -> io::Result<Self>
609    where
610        R: PstReader,
611    {
612        f.seek(SeekFrom::Start(block.block().index().index().into()))?;
613
614        let block_size = block_size(
615            block.size() + <<Pst as PstFile>::BlockTrailer as BlockTrailerReadWrite>::SIZE,
616        );
617        let mut data = vec![0; block_size as usize];
618        f.read_exact(&mut data)?;
619        let mut cursor = Cursor::new(data);
620
621        let block = if block.block().block().is_internal() {
622            let header = DataTreeBlockHeader::read(&mut cursor)?;
623            cursor.seek(SeekFrom::Start(0))?;
624            let block = <<Pst as PstFile>::DataTreeBlock as IntermediateTreeBlockReadWrite>::read(
625                &mut cursor,
626                header,
627                block.size(),
628            )?;
629            Self::Intermediate(Box::new(block))
630        } else {
631            let block = <<Pst as PstFile>::DataBlock as BlockReadWrite>::read(
632                &mut cursor,
633                block.size(),
634                encoding,
635            )?;
636            Self::Leaf(Box::new(block))
637        };
638
639        Ok(block)
640    }
641
642    pub fn write<W: Write + Seek>(
643        &self,
644        f: &mut W,
645        block: &<Pst as PstFile>::BlockBTreeEntry,
646    ) -> io::Result<()> {
647        f.seek(SeekFrom::Start(block.block().index().index().into()))?;
648
649        match self {
650            Self::Intermediate(block, ..) => block.write(f),
651            Self::Leaf(block) => block.write(f),
652        }
653    }
654
655    pub fn blocks<'a, R>(
656        &'a self,
657        f: &mut R,
658        encoding: NdbCryptMethod,
659        block_btree: &PstFileReadWriteBlockBTree<Pst>,
660        page_cache: &mut RootBTreePageCache<<Pst as PstFile>::BlockBTree>,
661        block_cache: &'a mut DataBlockCache<Pst>,
662    ) -> io::Result<Box<dyn 'a + Iterator<Item = <Pst as PstFile>::DataBlock>>>
663    where
664        R: PstReader,
665        <Pst as PstFile>::DataBlock: 'a + Clone,
666        <Pst as PstFile>::BlockId: BlockId<Index = <Pst as PstFile>::BTreeKey> + BlockIdReadWrite,
667        <Pst as PstFile>::ByteIndex: ByteIndexReadWrite,
668        <Pst as PstFile>::BlockRef: BlockRefReadWrite,
669        <Pst as PstFile>::PageTrailer: PageTrailerReadWrite,
670        <Pst as PstFile>::BTreeKey: BTreePageKeyReadWrite,
671        <Pst as PstFile>::BlockBTree: RootBTreeReadWrite,
672        <<Pst as PstFile>::BlockBTree as RootBTree>::Entry: BTreeEntryReadWrite,
673        <<Pst as PstFile>::BlockBTree as RootBTree>::IntermediatePage:
674            RootBTreeIntermediatePageReadWrite<
675                Pst,
676                <<Pst as PstFile>::BlockBTree as RootBTree>::Entry,
677                <<Pst as PstFile>::BlockBTree as RootBTree>::LeafPage,
678            >,
679        <<Pst as PstFile>::BlockBTree as RootBTree>::LeafPage:
680            RootBTreeLeafPageReadWrite<Pst> + BTreePageReadWrite,
681    {
682        match self {
683            Self::Intermediate(block, ..) => {
684                let mut blocks = Vec::with_capacity(block.entries().len());
685                for entry in block.entries() {
686                    let data_tree = match block_cache.remove(&entry.block()) {
687                        Some(entry) => entry,
688                        None => {
689                            let data_block = block_btree.find_entry(
690                                f,
691                                entry.block().search_key(),
692                                page_cache,
693                            )?;
694                            Self::read(&mut *f, encoding, &data_block)?
695                        }
696                    };
697                    let entries = data_tree
698                        .blocks(f, encoding, block_btree, page_cache, block_cache)
699                        .map(|blocks| blocks.collect::<Vec<_>>());
700                    block_cache.insert(entry.block(), data_tree);
701                    blocks.push(entries?);
702                }
703                Ok(Box::new(blocks.into_iter().flatten()))
704            }
705            Self::Leaf(block) => Ok(Box::new(Some(block.as_ref()).cloned().into_iter())),
706        }
707    }
708
709    pub fn nth<R>(
710        &self,
711        n: usize,
712        f: &mut R,
713        encoding: NdbCryptMethod,
714        block_btree: &PstFileReadWriteBlockBTree<Pst>,
715        page_cache: &mut RootBTreePageCache<<Pst as PstFile>::BlockBTree>,
716        block_cache: &mut DataBlockCache<Pst>,
717    ) -> io::Result<Option<Vec<u8>>>
718    where
719        R: PstReader,
720        <Pst as PstFile>::BlockId: BlockId<Index = <Pst as PstFile>::BTreeKey> + BlockIdReadWrite,
721        <Pst as PstFile>::ByteIndex: ByteIndexReadWrite,
722        <Pst as PstFile>::BlockRef: BlockRefReadWrite,
723        <Pst as PstFile>::PageTrailer: PageTrailerReadWrite,
724        <Pst as PstFile>::BTreeKey: BTreePageKeyReadWrite,
725        <Pst as PstFile>::BlockBTree: RootBTreeReadWrite,
726        <<Pst as PstFile>::BlockBTree as RootBTree>::Entry: BTreeEntryReadWrite,
727        <<Pst as PstFile>::BlockBTree as RootBTree>::IntermediatePage:
728            RootBTreeIntermediatePageReadWrite<
729                Pst,
730                <<Pst as PstFile>::BlockBTree as RootBTree>::Entry,
731                <<Pst as PstFile>::BlockBTree as RootBTree>::LeafPage,
732            >,
733        <<Pst as PstFile>::BlockBTree as RootBTree>::LeafPage:
734            RootBTreeLeafPageReadWrite<Pst> + BTreePageReadWrite,
735    {
736        Ok(Some(match self {
737            Self::Intermediate(_) => {
738                let Some(data_block) = self
739                    .sub_entries(f, encoding, block_btree, page_cache, block_cache)?
740                    .nth(n)
741                else {
742                    return Ok(None);
743                };
744
745                let data_tree = match block_cache.entry(data_block.block().block()) {
746                    btree_map::Entry::Vacant(entry) => {
747                        entry.insert(Self::read(&mut *f, encoding, &data_block)?)
748                    }
749                    btree_map::Entry::Occupied(entry) => entry.into_mut(),
750                };
751
752                let Self::Leaf(block) = data_tree else {
753                    error!(
754                        name: "PstInvalidDataTreeIntermediateBlock",
755                        "Data tree intermediate block has non-leaf sub-entry"
756                    );
757
758                    return Err(NdbError::InvalidInternalBlockLevel(0).into());
759                };
760
761                block.data().to_vec()
762            }
763            Self::Leaf(block) => {
764                if n != 0 {
765                    return Ok(None);
766                }
767
768                block.data().to_vec()
769            }
770        }))
771    }
772
773    pub fn reader<'a, R>(
774        &self,
775        f: &'a mut R,
776        encoding: NdbCryptMethod,
777        block_btree: &'a PstFileReadWriteBlockBTree<Pst>,
778        page_cache: &mut RootBTreePageCache<<Pst as PstFile>::BlockBTree>,
779        block_cache: &'a mut DataBlockCache<Pst>,
780    ) -> io::Result<Box<dyn 'a + Read>>
781    where
782        Pst: 'a,
783        R: PstReader,
784        <Pst as PstFile>::DataBlock: 'a + Clone,
785        <Pst as PstFile>::BTreeKey: BTreePageKeyReadWrite,
786        <Pst as PstFile>::BlockBTree: RootBTreeReadWrite,
787        <<Pst as PstFile>::BlockBTree as RootBTree>::Entry: BTreeEntryReadWrite,
788        <<Pst as PstFile>::BlockBTree as RootBTree>::IntermediatePage:
789            RootBTreeIntermediatePageReadWrite<
790                Pst,
791                <<Pst as PstFile>::BlockBTree as RootBTree>::Entry,
792                <<Pst as PstFile>::BlockBTree as RootBTree>::LeafPage,
793            >,
794        <<Pst as PstFile>::BlockBTree as RootBTree>::LeafPage:
795            RootBTreeLeafPageReadWrite<Pst> + BTreePageReadWrite,
796    {
797        let reader: DataTreeReader<'a, Pst, R> =
798            DataTreeReader::new(self, f, encoding, block_btree, page_cache, block_cache)?;
799        let reader: Box<dyn 'a + Read> = Box::new(reader);
800        Ok(reader)
801    }
802
803    fn sub_entries<'a, R>(
804        &self,
805        f: &mut R,
806        encoding: NdbCryptMethod,
807        block_btree: &PstFileReadWriteBlockBTree<Pst>,
808        page_cache: &mut RootBTreePageCache<<Pst as PstFile>::BlockBTree>,
809        block_cache: &'a mut DataBlockCache<Pst>,
810    ) -> io::Result<Box<dyn 'a + Iterator<Item = <Pst as PstFile>::BlockBTreeEntry>>>
811    where
812        R: PstReader,
813        <Pst as PstFile>::BlockBTreeEntry: 'a,
814        <Pst as PstFile>::BlockId: BlockId<Index = <Pst as PstFile>::BTreeKey> + BlockIdReadWrite,
815        <Pst as PstFile>::ByteIndex: ByteIndexReadWrite,
816        <Pst as PstFile>::BlockRef: BlockRefReadWrite,
817        <Pst as PstFile>::PageTrailer: PageTrailerReadWrite,
818        <Pst as PstFile>::BTreeKey: BTreePageKeyReadWrite,
819        <Pst as PstFile>::BlockBTree: RootBTreeReadWrite,
820        <<Pst as PstFile>::BlockBTree as RootBTree>::Entry: BTreeEntryReadWrite,
821        <<Pst as PstFile>::BlockBTree as RootBTree>::IntermediatePage:
822            RootBTreeIntermediatePageReadWrite<
823                Pst,
824                <<Pst as PstFile>::BlockBTree as RootBTree>::Entry,
825                <<Pst as PstFile>::BlockBTree as RootBTree>::LeafPage,
826            >,
827        <<Pst as PstFile>::BlockBTree as RootBTree>::LeafPage:
828            RootBTreeLeafPageReadWrite<Pst> + BTreePageReadWrite,
829    {
830        match self {
831            Self::Intermediate(block, ..) => {
832                let mut blocks = Vec::with_capacity(block.entries().len());
833                for entry in block.entries() {
834                    if entry.block().is_internal() {
835                        let data_tree = match block_cache.remove(&entry.block()) {
836                            Some(entry) => entry,
837                            None => {
838                                let data_block = block_btree.find_entry(
839                                    f,
840                                    entry.block().search_key(),
841                                    page_cache,
842                                )?;
843                                Self::read(&mut *f, encoding, &data_block)?
844                            }
845                        };
846                        let entries = data_tree
847                            .sub_entries(f, encoding, block_btree, page_cache, block_cache)
848                            .map(|entries| entries.collect::<Vec<_>>());
849                        block_cache.insert(entry.block(), data_tree);
850                        blocks.push(entries?);
851                    } else {
852                        let data_block =
853                            block_btree.find_entry(f, entry.block().search_key(), page_cache)?;
854                        blocks.push(vec![data_block]);
855                    }
856                }
857                Ok(Box::new(blocks.into_iter().flatten()))
858            }
859            Self::Leaf(_) => Ok(Box::new(iter::empty())),
860        }
861    }
862}
863
864struct DataTreeCursor<Pst>
865where
866    Pst: PstFile,
867{
868    current: Cursor<Vec<u8>>,
869    next: VecDeque<<Pst as PstFile>::BlockBTreeEntry>,
870}
871
872struct DataTreeReader<'a, Pst, R>
873where
874    Pst: PstFile,
875    R: PstReader,
876{
877    file: &'a mut R,
878    encoding: NdbCryptMethod,
879    cursor: DataTreeCursor<Pst>,
880}
881
882impl<'a, Pst, R> DataTreeReader<'a, Pst, R>
883where
884    Pst: PstFile,
885    R: PstReader,
886{
887    fn new(
888        data_tree: &DataTree<Pst>,
889        file: &'a mut R,
890        encoding: NdbCryptMethod,
891        block_btree: &'a PstFileReadWriteBlockBTree<Pst>,
892        page_cache: &mut RootBTreePageCache<<Pst as PstFile>::BlockBTree>,
893        block_cache: &'a mut DataBlockCache<Pst>,
894    ) -> io::Result<Self>
895    where
896        <Pst as PstFile>::BlockId: BlockId<Index = <Pst as PstFile>::BTreeKey> + BlockIdReadWrite,
897        <Pst as PstFile>::ByteIndex: ByteIndexReadWrite,
898        <Pst as PstFile>::BlockRef: BlockRefReadWrite,
899        <Pst as PstFile>::PageTrailer: PageTrailerReadWrite,
900        <Pst as PstFile>::BTreeKey: BTreePageKeyReadWrite,
901        <Pst as PstFile>::BlockBTree: RootBTreeReadWrite,
902        <<Pst as PstFile>::BlockBTree as RootBTree>::Entry: BTreeEntryReadWrite,
903        <<Pst as PstFile>::BlockBTree as RootBTree>::IntermediatePage:
904            RootBTreeIntermediatePageReadWrite<
905                Pst,
906                <<Pst as PstFile>::BlockBTree as RootBTree>::Entry,
907                <<Pst as PstFile>::BlockBTree as RootBTree>::LeafPage,
908            >,
909        <<Pst as PstFile>::BlockBTree as RootBTree>::LeafPage:
910            RootBTreeLeafPageReadWrite<Pst> + BTreePageReadWrite,
911        <Pst as PstFile>::BlockTrailer: BlockTrailerReadWrite,
912        <Pst as PstFile>::DataTreeBlock: IntermediateTreeBlockReadWrite,
913        <<Pst as PstFile>::DataTreeBlock as IntermediateTreeBlock>::Entry:
914            IntermediateTreeEntryReadWrite,
915        <Pst as PstFile>::DataBlock: BlockReadWrite,
916    {
917        let cursor = match data_tree {
918            DataTree::Intermediate(_) => {
919                let next = data_tree
920                    .sub_entries(file, encoding, block_btree, page_cache, block_cache)?
921                    .collect();
922
923                DataTreeCursor {
924                    current: Default::default(),
925                    next,
926                }
927            }
928            DataTree::Leaf(block) => DataTreeCursor {
929                current: Cursor::new(block.data().to_vec()),
930                next: Default::default(),
931            },
932        };
933
934        Ok(Self {
935            cursor,
936            file,
937            encoding,
938        })
939    }
940}
941
942impl<Pst, R> Read for DataTreeReader<'_, Pst, R>
943where
944    Pst: PstFile,
945    R: PstReader,
946    <Pst as PstFile>::BlockId: BlockId<Index = <Pst as PstFile>::BTreeKey> + BlockIdReadWrite,
947    <Pst as PstFile>::ByteIndex: ByteIndexReadWrite,
948    <Pst as PstFile>::BlockRef: BlockRefReadWrite,
949    <Pst as PstFile>::PageTrailer: PageTrailerReadWrite,
950    <Pst as PstFile>::BTreeKey: BTreePageKeyReadWrite,
951    <Pst as PstFile>::BlockBTree: RootBTreeReadWrite,
952    <<Pst as PstFile>::BlockBTree as RootBTree>::Entry: BTreeEntryReadWrite,
953    <<Pst as PstFile>::BlockBTree as RootBTree>::IntermediatePage:
954        RootBTreeIntermediatePageReadWrite<
955            Pst,
956            <<Pst as PstFile>::BlockBTree as RootBTree>::Entry,
957            <<Pst as PstFile>::BlockBTree as RootBTree>::LeafPage,
958        >,
959    <<Pst as PstFile>::BlockBTree as RootBTree>::LeafPage:
960        RootBTreeLeafPageReadWrite<Pst> + BTreePageReadWrite,
961    <Pst as PstFile>::BlockTrailer: BlockTrailerReadWrite,
962    <Pst as PstFile>::DataTreeBlock: IntermediateTreeBlockReadWrite,
963    <<Pst as PstFile>::DataTreeBlock as IntermediateTreeBlock>::Entry:
964        IntermediateTreeEntryReadWrite,
965    <Pst as PstFile>::DataBlock: BlockReadWrite,
966{
967    fn read(&mut self, buf: &mut [u8]) -> io::Result<usize> {
968        let mut total_read = self.cursor.current.read(buf)?;
969
970        while total_read < buf.len() {
971            let Some(next) = self.cursor.next.pop_front() else {
972                break;
973            };
974
975            let next: DataTree<Pst> = DataTree::read(self.file, self.encoding, &next)?;
976            let DataTree::Leaf(next) = next else {
977                error!(
978                    name: "PstInvalidDataTreeIntermediateBlock",
979                    "Data tree intermediate block has non-leaf sub-entry"
980                );
981
982                return Err(NdbError::InvalidInternalBlockLevel(0).into());
983            };
984            self.cursor.current = Cursor::new(next.data().to_vec());
985
986            let buf = &mut buf[total_read..];
987            total_read += self.cursor.current.read(buf)?;
988        }
989
990        Ok(total_read)
991    }
992}
993
994pub type UnicodeDataTree = DataTree<UnicodePstFile>;
995pub type AnsiDataTree = DataTree<AnsiPstFile>;
996
997#[derive(Clone, Copy, Default)]
998struct SubNodeTreeBlockHeader {
999    level: u8,
1000    entry_count: u16,
1001}
1002
1003#[derive(Clone, Copy, Default)]
1004pub struct UnicodeSubNodeTreeBlockHeader(SubNodeTreeBlockHeader);
1005
1006impl UnicodeSubNodeTreeBlockHeader {
1007    pub fn new(level: u8, entry_count: u16) -> Self {
1008        Self(SubNodeTreeBlockHeader { level, entry_count })
1009    }
1010}
1011
1012impl IntermediateTreeHeader for UnicodeSubNodeTreeBlockHeader {
1013    fn level(&self) -> u8 {
1014        self.0.level
1015    }
1016
1017    fn entry_count(&self) -> u16 {
1018        self.0.entry_count
1019    }
1020}
1021
1022impl IntermediateTreeHeaderReadWrite for UnicodeSubNodeTreeBlockHeader {
1023    const HEADER_SIZE: u16 = 8;
1024
1025    fn read(f: &mut dyn Read) -> io::Result<Self> {
1026        let block_type = f.read_u8()?;
1027        if block_type != 0x02 {
1028            return Err(NdbError::InvalidInternalBlockType(block_type).into());
1029        }
1030
1031        let level = f.read_u8()?;
1032        let entry_count = f.read_u16::<LittleEndian>()?;
1033
1034        let padding = f.read_u32::<LittleEndian>()?;
1035        if padding != 0 {
1036            return Err(NdbError::InvalidSubNodeBlockPadding(padding).into());
1037        }
1038
1039        Ok(Self::new(level, entry_count))
1040    }
1041
1042    fn write(&self, f: &mut dyn Write) -> io::Result<()> {
1043        f.write_u8(0x02)?;
1044        f.write_u8(self.level())?;
1045        f.write_u16::<LittleEndian>(self.entry_count())?;
1046        f.write_u32::<LittleEndian>(0)
1047    }
1048}
1049
1050impl SubNodeTreeBlockHeaderReadWrite for UnicodeSubNodeTreeBlockHeader {
1051    fn new(level: u8, entry_count: u16) -> Self {
1052        Self::new(level, entry_count)
1053    }
1054}
1055
1056#[derive(Clone, Copy, Default)]
1057pub struct AnsiSubNodeTreeBlockHeader(SubNodeTreeBlockHeader);
1058
1059impl AnsiSubNodeTreeBlockHeader {
1060    pub fn new(level: u8, entry_count: u16) -> Self {
1061        Self(SubNodeTreeBlockHeader { level, entry_count })
1062    }
1063}
1064
1065impl IntermediateTreeHeader for AnsiSubNodeTreeBlockHeader {
1066    fn level(&self) -> u8 {
1067        self.0.level
1068    }
1069
1070    fn entry_count(&self) -> u16 {
1071        self.0.entry_count
1072    }
1073}
1074
1075impl IntermediateTreeHeaderReadWrite for AnsiSubNodeTreeBlockHeader {
1076    const HEADER_SIZE: u16 = 4;
1077
1078    fn read(f: &mut dyn Read) -> io::Result<Self> {
1079        let block_type = f.read_u8()?;
1080        if block_type != 0x02 {
1081            return Err(NdbError::InvalidInternalBlockType(block_type).into());
1082        }
1083
1084        let level = f.read_u8()?;
1085        let entry_count = f.read_u16::<LittleEndian>()?;
1086
1087        Ok(Self::new(level, entry_count))
1088    }
1089
1090    fn write(&self, f: &mut dyn Write) -> io::Result<()> {
1091        f.write_u8(0x02)?;
1092        f.write_u8(self.level())?;
1093        f.write_u16::<LittleEndian>(self.entry_count())
1094    }
1095}
1096
1097impl SubNodeTreeBlockHeaderReadWrite for AnsiSubNodeTreeBlockHeader {
1098    fn new(level: u8, entry_count: u16) -> Self {
1099        Self::new(level, entry_count)
1100    }
1101}
1102
1103/// [SLENTRY (Leaf Block Entry)](https://learn.microsoft.com/en-us/openspecs/office_file_formats/ms-pst/85c4d943-0779-43c5-bd98-61dc9bb5dfd6)
1104#[derive(Clone, Copy, Default)]
1105pub struct LeafSubNodeTreeEntry<Block>
1106where
1107    Block: BlockId,
1108{
1109    inner: IntermediateSubNodeTreeEntry<Block>,
1110    sub_node: Option<Block>,
1111}
1112
1113impl<Block> LeafSubNodeTreeEntry<Block>
1114where
1115    Block: BlockId,
1116{
1117    pub fn new(node: NodeId, block: Block, sub_node: Option<Block>) -> Self {
1118        Self {
1119            inner: IntermediateSubNodeTreeEntry::new(node, block),
1120            sub_node,
1121        }
1122    }
1123
1124    pub fn node(&self) -> NodeId {
1125        self.inner.node()
1126    }
1127
1128    pub fn block(&self) -> Block {
1129        self.inner.block()
1130    }
1131
1132    pub fn sub_node(&self) -> Option<Block> {
1133        self.sub_node
1134    }
1135}
1136
1137pub type UnicodeLeafSubNodeTreeEntry = LeafSubNodeTreeEntry<UnicodeBlockId>;
1138pub type AnsiLeafSubNodeTreeEntry = LeafSubNodeTreeEntry<AnsiBlockId>;
1139
1140impl IntermediateTreeEntry for UnicodeLeafSubNodeTreeEntry {}
1141
1142impl IntermediateTreeEntryReadWrite for UnicodeLeafSubNodeTreeEntry {
1143    const ENTRY_SIZE: u16 = 24;
1144
1145    fn read(f: &mut dyn Read) -> io::Result<Self> {
1146        let inner = UnicodeIntermediateSubNodeTreeEntry::read(f)?;
1147        let sub_node = UnicodeBlockId::read(f)?;
1148        let sub_node = if sub_node.search_key() != 0 {
1149            Some(sub_node)
1150        } else {
1151            None
1152        };
1153
1154        Ok(Self::new(inner.node(), inner.block(), sub_node))
1155    }
1156
1157    fn write(&self, f: &mut dyn Write) -> io::Result<()> {
1158        self.inner.write(f)?;
1159        self.sub_node.unwrap_or_default().write(f)
1160    }
1161}
1162
1163impl IntermediateTreeEntry for AnsiLeafSubNodeTreeEntry {}
1164
1165impl IntermediateTreeEntryReadWrite for AnsiLeafSubNodeTreeEntry {
1166    const ENTRY_SIZE: u16 = 12;
1167
1168    fn read(f: &mut dyn Read) -> io::Result<Self> {
1169        let inner = AnsiIntermediateSubNodeTreeEntry::read(f)?;
1170        let sub_node = AnsiBlockId::read(f)?;
1171        let sub_node = if sub_node.search_key() != 0 {
1172            Some(sub_node)
1173        } else {
1174            None
1175        };
1176
1177        Ok(Self::new(inner.node(), inner.block(), sub_node))
1178    }
1179
1180    fn write(&self, f: &mut dyn Write) -> io::Result<()> {
1181        self.inner.write(f)?;
1182        self.sub_node.unwrap_or_default().write(f)
1183    }
1184}
1185
1186/// [SIENTRY (Intermediate Block Entry)](https://learn.microsoft.com/en-us/openspecs/office_file_formats/ms-pst/9e79c673-d2f4-49fb-a00b-51b08fd2d1e4)
1187#[derive(Clone, Copy, Default)]
1188pub struct IntermediateSubNodeTreeEntry<Block>
1189where
1190    Block: BlockId,
1191{
1192    node: NodeId,
1193    block: Block,
1194}
1195
1196impl<Block> IntermediateSubNodeTreeEntry<Block>
1197where
1198    Block: BlockId,
1199{
1200    pub fn new(node: NodeId, block: Block) -> Self {
1201        Self { node, block }
1202    }
1203
1204    pub fn node(&self) -> NodeId {
1205        self.node
1206    }
1207
1208    pub fn block(&self) -> Block {
1209        self.block
1210    }
1211}
1212
1213pub type UnicodeIntermediateSubNodeTreeEntry = IntermediateSubNodeTreeEntry<UnicodeBlockId>;
1214pub type AnsiIntermediateSubNodeTreeEntry = IntermediateSubNodeTreeEntry<AnsiBlockId>;
1215
1216impl IntermediateTreeEntry for UnicodeIntermediateSubNodeTreeEntry {}
1217
1218impl IntermediateTreeEntryReadWrite for UnicodeIntermediateSubNodeTreeEntry {
1219    const ENTRY_SIZE: u16 = 16;
1220
1221    fn read(f: &mut dyn Read) -> io::Result<Self> {
1222        let node = NodeId::from(f.read_u64::<LittleEndian>()? as u32);
1223        let block = UnicodeBlockId::read(f)?;
1224        Ok(Self::new(node, block))
1225    }
1226
1227    fn write(&self, f: &mut dyn Write) -> io::Result<()> {
1228        f.write_u64::<LittleEndian>(u64::from(u32::from(self.node)))?;
1229        self.block.write(f)
1230    }
1231}
1232
1233impl IntermediateTreeEntry for AnsiIntermediateSubNodeTreeEntry {}
1234
1235impl IntermediateTreeEntryReadWrite for AnsiIntermediateSubNodeTreeEntry {
1236    const ENTRY_SIZE: u16 = 8;
1237
1238    fn read(f: &mut dyn Read) -> io::Result<Self> {
1239        let node = NodeId::read(f)?;
1240        let block = AnsiBlockId::read(f)?;
1241        Ok(Self::new(node, block))
1242    }
1243
1244    fn write(&self, f: &mut dyn Write) -> io::Result<()> {
1245        self.node.write(f)?;
1246        self.block.write(f)
1247    }
1248}
1249
1250/// [SLBLOCK](https://learn.microsoft.com/en-us/openspecs/office_file_formats/ms-pst/5182eb24-4b0b-4816-aa3f-719cc6e6b018)
1251/// / [SIBLOCK](https://learn.microsoft.com/en-us/openspecs/office_file_formats/ms-pst/729fb9bd-060a-4bbc-9b3b-8f014b487dad)
1252pub struct SubNodeTreeBlock<Header, Entry, Trailer>
1253where
1254    Header: IntermediateTreeHeader,
1255    Entry: IntermediateTreeEntry,
1256    Trailer: BlockTrailer,
1257{
1258    header: Header,
1259    entries: Vec<Entry>,
1260    trailer: Trailer,
1261}
1262
1263impl<Header, Entry, Trailer> SubNodeTreeBlock<Header, Entry, Trailer>
1264where
1265    Header: IntermediateTreeHeader,
1266    Entry: IntermediateTreeEntry,
1267    Trailer: BlockTrailer,
1268{
1269    pub fn new(header: Header, entries: Vec<Entry>, trailer: Trailer) -> NdbResult<Self> {
1270        trailer.verify_block_id(true)?;
1271
1272        Ok(Self {
1273            header,
1274            entries,
1275            trailer,
1276        })
1277    }
1278}
1279
1280impl<Header, Entry, Trailer> IntermediateTreeBlock for SubNodeTreeBlock<Header, Entry, Trailer>
1281where
1282    Header: IntermediateTreeHeader,
1283    Entry: IntermediateTreeEntry,
1284    Trailer: BlockTrailer,
1285{
1286    type Header = Header;
1287    type Entry = Entry;
1288    type Trailer = Trailer;
1289
1290    fn header(&self) -> &Self::Header {
1291        &self.header
1292    }
1293
1294    fn entries(&self) -> &[Self::Entry] {
1295        &self.entries
1296    }
1297
1298    fn trailer(&self) -> &Trailer {
1299        &self.trailer
1300    }
1301}
1302
1303impl<Header, Entry, Trailer> IntermediateTreeBlockReadWrite
1304    for SubNodeTreeBlock<Header, Entry, Trailer>
1305where
1306    Header: IntermediateTreeHeaderReadWrite,
1307    Entry: IntermediateTreeEntryReadWrite,
1308    Trailer: BlockTrailerReadWrite,
1309{
1310    fn new(header: Header, entries: Vec<Entry>, trailer: Trailer) -> NdbResult<Self> {
1311        Self::new(header, entries, trailer)
1312    }
1313}
1314
1315pub type UnicodeIntermediateSubNodeTreeBlock = SubNodeTreeBlock<
1316    UnicodeSubNodeTreeBlockHeader,
1317    UnicodeIntermediateSubNodeTreeEntry,
1318    UnicodeBlockTrailer,
1319>;
1320pub type AnsiIntermediateSubNodeTreeBlock = SubNodeTreeBlock<
1321    AnsiSubNodeTreeBlockHeader,
1322    AnsiIntermediateSubNodeTreeEntry,
1323    AnsiBlockTrailer,
1324>;
1325
1326pub type UnicodeLeafSubNodeTreeBlock = SubNodeTreeBlock<
1327    UnicodeSubNodeTreeBlockHeader,
1328    UnicodeLeafSubNodeTreeEntry,
1329    UnicodeBlockTrailer,
1330>;
1331pub type AnsiLeafSubNodeTreeBlock =
1332    SubNodeTreeBlock<AnsiSubNodeTreeBlockHeader, AnsiLeafSubNodeTreeEntry, AnsiBlockTrailer>;
1333
1334pub enum SubNodeTree<Pst>
1335where
1336    Pst: PstFile,
1337{
1338    Intermediate(Box<<Pst as PstFile>::SubNodeTreeBlock>),
1339    Leaf(Box<<Pst as PstFile>::SubNodeBlock>),
1340}
1341
1342impl<Pst> SubNodeTree<Pst>
1343where
1344    Pst: PstFile,
1345    <Pst as PstFile>::BlockTrailer: BlockTrailerReadWrite,
1346    <Pst as PstFile>::SubNodeTreeBlockHeader: IntermediateTreeHeaderReadWrite,
1347    <Pst as PstFile>::SubNodeTreeBlock: IntermediateTreeBlockReadWrite,
1348    <<Pst as PstFile>::SubNodeTreeBlock as IntermediateTreeBlock>::Entry:
1349        IntermediateTreeEntryReadWrite,
1350    <Pst as PstFile>::SubNodeBlock: IntermediateTreeBlockReadWrite,
1351    <<Pst as PstFile>::SubNodeBlock as IntermediateTreeBlock>::Entry:
1352        IntermediateTreeEntryReadWrite,
1353{
1354    pub fn read<R: PstReader>(
1355        f: &mut R,
1356        block: &<Pst as PstFile>::BlockBTreeEntry,
1357    ) -> io::Result<Self> {
1358        f.seek(SeekFrom::Start(block.block().index().index().into()))?;
1359
1360        let block_size = block_size(
1361            block.size() + <<Pst as PstFile>::BlockTrailer as BlockTrailerReadWrite>::SIZE,
1362        );
1363        let mut data = vec![0; block_size as usize];
1364        f.read_exact(&mut data)?;
1365        let mut cursor = Cursor::new(data);
1366        let header =
1367            <<Pst as PstFile>::SubNodeTreeBlockHeader as IntermediateTreeHeaderReadWrite>::read(
1368                &mut cursor,
1369            )?;
1370        cursor.seek(SeekFrom::Start(0))?;
1371
1372        if header.level() > 0 {
1373            let block =
1374                <<Pst as PstFile>::SubNodeTreeBlock as IntermediateTreeBlockReadWrite>::read(
1375                    &mut cursor,
1376                    header,
1377                    block.size(),
1378                )?;
1379            Ok(Self::Intermediate(Box::new(block)))
1380        } else {
1381            let block = <<Pst as PstFile>::SubNodeBlock as IntermediateTreeBlockReadWrite>::read(
1382                &mut cursor,
1383                header,
1384                block.size(),
1385            )?;
1386            Ok(Self::Leaf(Box::new(block)))
1387        }
1388    }
1389
1390    pub fn write<W: Write + Seek>(
1391        &self,
1392        f: &mut W,
1393        block: &<Pst as PstFile>::BlockBTreeEntry,
1394    ) -> io::Result<()> {
1395        f.seek(SeekFrom::Start(block.block().index().index().into()))?;
1396
1397        match self {
1398            Self::Intermediate(block) => block.write(f),
1399            Self::Leaf(block) => block.write(f),
1400        }
1401    }
1402
1403    pub fn find_entry<R>(
1404        &self,
1405        f: &mut R,
1406        block_btree: &PstFileReadWriteBlockBTree<Pst>,
1407        node: NodeId,
1408        page_cache: &mut RootBTreePageCache<<Pst as PstFile>::BlockBTree>,
1409    ) -> io::Result<<Pst as PstFile>::BlockId>
1410    where
1411        R: PstReader,
1412        <Pst as PstFile>::BlockId: BlockId<Index = <Pst as PstFile>::BTreeKey> + BlockIdReadWrite,
1413        <Pst as PstFile>::ByteIndex: ByteIndexReadWrite,
1414        <Pst as PstFile>::BlockRef: BlockRefReadWrite,
1415        <Pst as PstFile>::PageTrailer: PageTrailerReadWrite,
1416        <Pst as PstFile>::BTreeKey: BTreePageKeyReadWrite,
1417        <Pst as PstFile>::BlockBTree: RootBTreeReadWrite,
1418        <<Pst as PstFile>::BlockBTree as RootBTree>::Entry: BTreeEntryReadWrite,
1419        <<Pst as PstFile>::BlockBTree as RootBTree>::IntermediatePage:
1420            RootBTreeIntermediatePageReadWrite<
1421                Pst,
1422                <<Pst as PstFile>::BlockBTree as RootBTree>::Entry,
1423                <<Pst as PstFile>::BlockBTree as RootBTree>::LeafPage,
1424            >,
1425        <<Pst as PstFile>::BlockBTree as RootBTree>::LeafPage:
1426            RootBTreeLeafPageReadWrite<Pst> + BTreePageReadWrite,
1427    {
1428        match self {
1429            Self::Intermediate(block) => {
1430                let entries = block.entries();
1431                let index =
1432                    entries.partition_point(|entry| u32::from(entry.node()) <= u32::from(node));
1433                let entry = index
1434                    .checked_sub(1)
1435                    .and_then(|index| entries.get(index))
1436                    .ok_or(NdbError::SubNodeNotFound(node))?;
1437                let block = block_btree.find_entry(f, entry.block().search_key(), page_cache)?;
1438                let page = Self::read(f, &block)?;
1439                page.find_entry(f, block_btree, node, page_cache)
1440            }
1441            Self::Leaf(block) => {
1442                let entry = block
1443                    .entries()
1444                    .iter()
1445                    .find(|entry| u32::from(entry.node()) == u32::from(node))
1446                    .map(|entry| entry.block())
1447                    .ok_or(NdbError::SubNodeNotFound(node))?;
1448                Ok(entry)
1449            }
1450        }
1451    }
1452
1453    pub fn entries<'a, R>(
1454        &self,
1455        f: &mut R,
1456        block_btree: &PstFileReadWriteBlockBTree<Pst>,
1457        page_cache: &mut RootBTreePageCache<<Pst as PstFile>::BlockBTree>,
1458    ) -> io::Result<Box<dyn 'a + Iterator<Item = LeafSubNodeTreeEntry<<Pst as PstFile>::BlockId>>>>
1459    where
1460        R: PstReader,
1461        <Pst as PstFile>::BlockId:
1462            'a + BlockId<Index = <Pst as PstFile>::BTreeKey> + BlockIdReadWrite,
1463        <Pst as PstFile>::ByteIndex: ByteIndexReadWrite,
1464        <Pst as PstFile>::BlockRef: BlockRefReadWrite,
1465        <Pst as PstFile>::PageTrailer: PageTrailerReadWrite,
1466        <Pst as PstFile>::BTreeKey: BTreePageKeyReadWrite,
1467        <Pst as PstFile>::BlockBTree: RootBTreeReadWrite,
1468        <<Pst as PstFile>::BlockBTree as RootBTree>::Entry: BTreeEntryReadWrite,
1469        <<Pst as PstFile>::BlockBTree as RootBTree>::IntermediatePage:
1470            RootBTreeIntermediatePageReadWrite<
1471                Pst,
1472                <<Pst as PstFile>::BlockBTree as RootBTree>::Entry,
1473                <<Pst as PstFile>::BlockBTree as RootBTree>::LeafPage,
1474            >,
1475        <<Pst as PstFile>::BlockBTree as RootBTree>::LeafPage:
1476            RootBTreeLeafPageReadWrite<Pst> + BTreePageReadWrite,
1477    {
1478        match self {
1479            Self::Intermediate(block) => {
1480                let entries = block
1481                    .entries()
1482                    .iter()
1483                    .map(|entry| {
1484                        let block =
1485                            block_btree.find_entry(f, entry.block().search_key(), page_cache)?;
1486                        let sub_nodes = Self::read(f, &block)?;
1487                        sub_nodes.entries(f, block_btree, page_cache)
1488                    })
1489                    .collect::<io::Result<Vec<_>>>()?;
1490                Ok(Box::new(entries.into_iter().flatten()))
1491            }
1492            Self::Leaf(block) => {
1493                let entries = block.entries().to_vec();
1494                Ok(Box::new(entries.into_iter()))
1495            }
1496        }
1497    }
1498}
1499
1500pub type UnicodeSubNodeTree = SubNodeTree<UnicodePstFile>;
1501pub type AnsiSubNodeTree = SubNodeTree<AnsiPstFile>;
outlook_pst/ndb/block.rs

outlook_pst/ndb/
block.rs
