outlook_pst/ndb/
page.rs

1//! [Pages](https://learn.microsoft.com/en-us/openspecs/office_file_formats/ms-pst/5774b4f2-cdc4-453e-996a-8c8230116930)
2
3use byteorder::{LittleEndian, ReadBytesExt, WriteBytesExt};
4use core::mem;
5use std::{
6    fmt::Debug,
7    io::{self, Cursor, Read, Seek, SeekFrom, Write},
8    marker::PhantomData,
9    ops::Range,
10};
11
12use super::{block_id::*, block_ref::*, byte_index::*, node_id::*, read_write::*, *};
13use crate::{
14    block_sig::compute_sig, crc::compute_crc, AnsiPstFile, PstFile, PstReader, UnicodePstFile,
15};
16
17/// `ptype`
18///
19/// ### See also
20/// [PageTrailer]
21#[repr(u8)]
22#[derive(Copy, Clone, PartialEq, Eq, Default, Debug)]
23pub enum PageType {
24    #[default]
25    None = 0x00,
26    /// `ptypeBBT`: Block BTree page
27    BlockBTree = 0x80,
28    /// `ptypeNBT`: Node BTree page
29    NodeBTree = 0x81,
30    /// `ptypeFMap`: Free Map page
31    FreeMap = 0x82,
32    /// `ptypePMap`: Allocation Page Map page
33    AllocationPageMap = 0x83,
34    /// `ptypeAMap`: Allocation Map page
35    AllocationMap = 0x84,
36    /// `ptypeFPMap`: Free Page Map page
37    FreePageMap = 0x85,
38    /// `ptypeDL`: Density List page
39    DensityList = 0x86,
40}
41
42impl TryFrom<u8> for PageType {
43    type Error = NdbError;
44
45    fn try_from(value: u8) -> Result<Self, Self::Error> {
46        match value {
47            0x80 => Ok(PageType::BlockBTree),
48            0x81 => Ok(PageType::NodeBTree),
49            0x82 => Ok(PageType::FreeMap),
50            0x83 => Ok(PageType::AllocationPageMap),
51            0x84 => Ok(PageType::AllocationMap),
52            0x85 => Ok(PageType::FreePageMap),
53            0x86 => Ok(PageType::DensityList),
54            _ => Err(NdbError::InvalidPageType(value)),
55        }
56    }
57}
58
59impl PageType {
60    pub fn signature(&self, index: u64, block_id: u64) -> u16 {
61        match self {
62            PageType::BlockBTree | PageType::NodeBTree | PageType::DensityList => compute_sig(
63                (index & u64::from(u32::MAX)) as u32,
64                (block_id & u64::from(u32::MAX)) as u32,
65            ),
66            _ => 0,
67        }
68    }
69}
70
71pub const PAGE_SIZE: usize = 512;
72
73/// [PAGETRAILER](https://learn.microsoft.com/en-us/openspecs/office_file_formats/ms-pst/f4ccb38a-930a-4db4-98df-a69c195926ba)
74pub trait PageTrailer {
75    type BlockId: BlockId + Debug;
76
77    fn page_type(&self) -> PageType;
78    fn signature(&self) -> u16;
79    fn crc(&self) -> u32;
80    fn block_id(&self) -> Self::BlockId;
81}
82
83#[derive(Copy, Clone, Default)]
84pub struct UnicodePageTrailer {
85    page_type: PageType,
86    signature: u16,
87    crc: u32,
88    block_id: UnicodePageId,
89}
90
91impl PageTrailer for UnicodePageTrailer {
92    type BlockId = UnicodePageId;
93
94    fn page_type(&self) -> PageType {
95        self.page_type
96    }
97
98    fn signature(&self) -> u16 {
99        self.signature
100    }
101
102    fn crc(&self) -> u32 {
103        self.crc
104    }
105
106    fn block_id(&self) -> UnicodePageId {
107        self.block_id
108    }
109}
110
111impl PageTrailerReadWrite for UnicodePageTrailer {
112    fn new(page_type: PageType, signature: u16, block_id: UnicodePageId, crc: u32) -> Self {
113        Self {
114            page_type,
115            block_id,
116            signature,
117            crc,
118        }
119    }
120
121    fn read(f: &mut dyn Read) -> io::Result<Self> {
122        let mut page_type = [0_u8; 2];
123        f.read_exact(&mut page_type)?;
124        if page_type[0] != page_type[1] {
125            return Err(NdbError::MismatchPageTypeRepeat(page_type[0], page_type[1]).into());
126        }
127        let page_type = PageType::try_from(page_type[0])?;
128        let signature = f.read_u16::<LittleEndian>()?;
129        let crc = f.read_u32::<LittleEndian>()?;
130        let block_id = UnicodePageId::read(f)?;
131
132        Ok(Self {
133            page_type,
134            signature,
135            crc,
136            block_id,
137        })
138    }
139
140    fn write(&self, f: &mut dyn Write) -> io::Result<()> {
141        f.write_all(&[self.page_type as u8; 2])?;
142        f.write_u16::<LittleEndian>(self.signature)?;
143        f.write_u32::<LittleEndian>(self.crc)?;
144        self.block_id.write(f)
145    }
146}
147
148#[derive(Copy, Clone, Default)]
149pub struct AnsiPageTrailer {
150    page_type: PageType,
151    signature: u16,
152    block_id: AnsiPageId,
153    crc: u32,
154}
155
156impl PageTrailer for AnsiPageTrailer {
157    type BlockId = AnsiPageId;
158
159    fn page_type(&self) -> PageType {
160        self.page_type
161    }
162
163    fn signature(&self) -> u16 {
164        self.signature
165    }
166
167    fn crc(&self) -> u32 {
168        self.crc
169    }
170
171    fn block_id(&self) -> AnsiPageId {
172        self.block_id
173    }
174}
175
176impl PageTrailerReadWrite for AnsiPageTrailer {
177    fn new(page_type: PageType, signature: u16, block_id: AnsiPageId, crc: u32) -> Self {
178        Self {
179            page_type,
180            crc,
181            block_id,
182            signature,
183        }
184    }
185
186    fn read(f: &mut dyn Read) -> io::Result<Self> {
187        let mut page_type = [0_u8; 2];
188        f.read_exact(&mut page_type)?;
189        if page_type[0] != page_type[1] {
190            return Err(NdbError::MismatchPageTypeRepeat(page_type[0], page_type[1]).into());
191        }
192        let page_type = PageType::try_from(page_type[0])?;
193        let signature = f.read_u16::<LittleEndian>()?;
194        let block_id = AnsiPageId::read(f)?;
195        let crc = f.read_u32::<LittleEndian>()?;
196
197        Ok(Self {
198            page_type,
199            signature,
200            block_id,
201            crc,
202        })
203    }
204
205    fn write(&self, f: &mut dyn Write) -> io::Result<()> {
206        f.write_all(&[self.page_type as u8; 2])?;
207        f.write_u16::<LittleEndian>(self.signature)?;
208        self.block_id.write(f)?;
209        f.write_u32::<LittleEndian>(self.crc)
210    }
211}
212
213pub type MapBits = [u8; 496];
214
215pub trait MapPage<Pst, const PAGE_TYPE: u8>
216where
217    Pst: PstFile,
218{
219    fn map_bits(&self) -> &MapBits;
220    fn map_bits_mut(&mut self) -> &mut MapBits;
221    fn trailer(&self) -> &Pst::PageTrailer;
222}
223
224const fn leading_zero_count(b: u8) -> u8 {
225    match b {
226        0x00 => 8,
227        b if b < 0x02 => 7,
228        b if b < 0x04 => 6,
229        b if b < 0x08 => 5,
230        b if b < 0x10 => 4,
231        b if b < 0x20 => 3,
232        b if b < 0x40 => 2,
233        b if b < 0x80 => 1,
234        _ => 0,
235    }
236}
237
238const fn trailing_zero_count(b: u8) -> u8 {
239    match b {
240        0x00 => 8,
241        b if b & 0x7F == 0 => 7,
242        b if b & 0x3F == 0 => 6,
243        b if b & 0x1F == 0 => 5,
244        b if b & 0x0F == 0 => 4,
245        b if b & 0x07 == 0 => 3,
246        b if b & 0x03 == 0 => 2,
247        b if b & 0x01 == 0 => 1,
248        _ => 0,
249    }
250}
251
252/// [AMAPPAGE](https://learn.microsoft.com/en-us/openspecs/office_file_formats/ms-pst/43d8f556-2c0e-4976-8ec7-84e57f8b1234)
253pub trait AllocationMapPage<Pst>: MapPage<Pst, { PageType::AllocationMap as u8 }>
254where
255    Pst: PstFile,
256{
257    /// Scan the allocation map for contiguous free bits up to the specified max size.
258    fn find_free_bits(&self, max_size: u16) -> Range<u16> {
259        let mut max_free_slots = 0..0;
260        let mut current = 0..0;
261
262        for &page in self.map_bits() {
263            if page == 0 {
264                current.end += 8;
265                if current.end - current.start > max_free_slots.end - max_free_slots.start {
266                    max_free_slots = current.clone();
267                }
268            } else {
269                let leading_zero = u16::from(leading_zero_count(page));
270                let trailing_zero = u16::from(trailing_zero_count(page));
271                assert!(leading_zero + trailing_zero < 8, "leading_zero: {leading_zero}, trailing_zero: {trailing_zero} for page: 0x{page:02X}");
272
273                let page_offset = current.end + 8;
274                current.end += leading_zero;
275
276                if current.end - current.start > max_free_slots.end - max_free_slots.start {
277                    max_free_slots = current.clone();
278                }
279
280                if page != 0xFF
281                    && (max_free_slots.end - max_free_slots.start + 2)
282                        < (8 - trailing_zero - leading_zero)
283                {
284                    let mut current = (current.end + 1)..(current.end + 1);
285
286                    for i in (leading_zero + 1)..(7 - trailing_zero) {
287                        if page & (0x80 >> i) == 0 {
288                            current.end += 1;
289                        } else {
290                            if current.end - current.start
291                                > max_free_slots.end - max_free_slots.start
292                            {
293                                max_free_slots = current.clone();
294                            }
295                            current = (current.end + 1)..(current.end + 1);
296                        }
297                    }
298
299                    if current.end - current.start > max_free_slots.end - max_free_slots.start {
300                        max_free_slots = current;
301                    }
302                }
303
304                current = (page_offset - trailing_zero)..page_offset;
305            }
306
307            if max_free_slots.end - max_free_slots.start >= max_size {
308                break;
309            }
310        }
311
312        if current.end - current.start > max_free_slots.end - max_free_slots.start {
313            max_free_slots = current;
314        }
315
316        (max_free_slots.start)..(max_free_slots.end.min(max_free_slots.start + max_size))
317    }
318}
319
320impl<Pst, Page> AllocationMapPage<Pst> for Page
321where
322    Pst: PstFile,
323    Page: MapPage<Pst, { PageType::AllocationMap as u8 }>,
324{
325}
326
327/// [PMAPPAGE](https://learn.microsoft.com/en-us/openspecs/office_file_formats/ms-pst/7e64a91f-cbd1-4a11-90c9-df5789e7d9a1)
328pub trait AllocationPageMapPage<Pst>: MapPage<Pst, { PageType::AllocationPageMap as u8 }>
329where
330    Pst: PstFile,
331{
332}
333
334impl<Pst, Page> AllocationPageMapPage<Pst> for Page
335where
336    Pst: PstFile,
337    Page: MapPage<Pst, { PageType::AllocationPageMap as u8 }>,
338{
339}
340
341/// [FMAPPAGE](https://learn.microsoft.com/en-us/openspecs/office_file_formats/ms-pst/26273ead-797e-4ea6-9b3c-9b9a5c581115)
342pub trait FreeMapPage<Pst>: MapPage<Pst, { PageType::FreeMap as u8 }>
343where
344    Pst: PstFile,
345{
346}
347
348impl<Pst, Page> FreeMapPage<Pst> for Page
349where
350    Pst: PstFile,
351    Page: MapPage<Pst, { PageType::FreeMap as u8 }>,
352{
353}
354
355/// [FPMAPPAGE](https://learn.microsoft.com/en-us/openspecs/office_file_formats/ms-pst/913a72b0-83f6-4c29-8b0b-40967579a534)
356pub trait FreePageMapPage<Pst>: MapPage<Pst, { PageType::FreePageMap as u8 }>
357where
358    Pst: PstFile,
359{
360}
361
362impl<Pst, Page> FreePageMapPage<Pst> for Page
363where
364    Pst: PstFile,
365    Page: MapPage<Pst, { PageType::FreePageMap as u8 }>,
366{
367}
368
369pub struct UnicodeMapPage<const P: u8> {
370    map_bits: MapBits,
371    trailer: UnicodePageTrailer,
372}
373
374impl<const PAGE_TYPE: u8> MapPage<UnicodePstFile, PAGE_TYPE> for UnicodeMapPage<PAGE_TYPE> {
375    fn map_bits(&self) -> &MapBits {
376        &self.map_bits
377    }
378
379    fn map_bits_mut(&mut self) -> &mut MapBits {
380        &mut self.map_bits
381    }
382
383    fn trailer(&self) -> &UnicodePageTrailer {
384        &self.trailer
385    }
386}
387
388impl<const PAGE_TYPE: u8> MapPageReadWrite<UnicodePstFile, PAGE_TYPE>
389    for UnicodeMapPage<PAGE_TYPE>
390{
391    fn new(map_bits: MapBits, trailer: UnicodePageTrailer) -> NdbResult<Self> {
392        if trailer.page_type() as u8 != PAGE_TYPE {
393            return Err(NdbError::UnexpectedPageType(trailer.page_type()));
394        }
395        Ok(Self { map_bits, trailer })
396    }
397
398    fn read(f: &mut dyn Read) -> io::Result<Self> {
399        let mut map_bits = [0_u8; mem::size_of::<MapBits>()];
400        f.read_exact(&mut map_bits)?;
401
402        let trailer = UnicodePageTrailer::read(f)?;
403        if trailer.page_type() as u8 != PAGE_TYPE {
404            return Err(NdbError::UnexpectedPageType(trailer.page_type()).into());
405        }
406
407        let crc = compute_crc(0, &map_bits);
408        if crc != trailer.crc() {
409            return Err(NdbError::InvalidPageCrc(crc).into());
410        }
411
412        Ok(Self { map_bits, trailer })
413    }
414
415    fn write(&self, f: &mut dyn Write) -> io::Result<()> {
416        f.write_all(&self.map_bits)?;
417
418        let crc = compute_crc(0, &self.map_bits);
419        let trailer = UnicodePageTrailer {
420            crc,
421            ..self.trailer
422        };
423        trailer.write(f)
424    }
425}
426
427pub struct AnsiMapPage<const P: u8> {
428    map_bits: MapBits,
429    trailer: AnsiPageTrailer,
430    padding: u32,
431}
432
433impl<const PAGE_TYPE: u8> MapPage<AnsiPstFile, PAGE_TYPE> for AnsiMapPage<PAGE_TYPE> {
434    fn map_bits(&self) -> &MapBits {
435        &self.map_bits
436    }
437
438    fn map_bits_mut(&mut self) -> &mut MapBits {
439        &mut self.map_bits
440    }
441
442    fn trailer(&self) -> &AnsiPageTrailer {
443        &self.trailer
444    }
445}
446
447impl MapPageReadWrite<AnsiPstFile, { PageType::AllocationMap as u8 }>
448    for AnsiMapPage<{ PageType::AllocationMap as u8 }>
449{
450    fn new(amap_bits: MapBits, trailer: AnsiPageTrailer) -> NdbResult<Self> {
451        if trailer.page_type() != PageType::AllocationMap {
452            return Err(NdbError::UnexpectedPageType(trailer.page_type()));
453        }
454        Ok(Self {
455            map_bits: amap_bits,
456            trailer,
457            padding: 0,
458        })
459    }
460
461    fn read(f: &mut dyn Read) -> io::Result<Self> {
462        let mut buffer = [0_u8; 500];
463        f.read_exact(&mut buffer)?;
464        let mut cursor = Cursor::new(buffer);
465
466        let padding = cursor.read_u32::<LittleEndian>()?;
467
468        let mut map_bits = [0_u8; mem::size_of::<MapBits>()];
469        cursor.read_exact(&mut map_bits)?;
470
471        let buffer = cursor.into_inner();
472
473        let trailer = AnsiPageTrailer::read(f)?;
474        if trailer.page_type() != PageType::AllocationMap {
475            return Err(NdbError::UnexpectedPageType(trailer.page_type()).into());
476        }
477
478        let crc = compute_crc(0, &buffer);
479        if crc != trailer.crc() {
480            return Err(NdbError::InvalidPageCrc(crc).into());
481        }
482
483        Ok(Self {
484            map_bits,
485            trailer,
486            padding,
487        })
488    }
489
490    fn write(&self, f: &mut dyn Write) -> io::Result<()> {
491        let mut cursor = Cursor::new([0_u8; 500]);
492
493        cursor.write_u32::<LittleEndian>(self.padding)?;
494        cursor.write_all(&self.map_bits)?;
495
496        let buffer = cursor.into_inner();
497        let crc = compute_crc(0, &buffer);
498
499        f.write_all(&buffer)?;
500
501        let trailer = AnsiPageTrailer {
502            crc,
503            ..self.trailer
504        };
505        trailer.write(f)
506    }
507}
508
509impl MapPageReadWrite<AnsiPstFile, { PageType::AllocationPageMap as u8 }>
510    for AnsiMapPage<{ PageType::AllocationPageMap as u8 }>
511{
512    fn new(amap_bits: MapBits, trailer: AnsiPageTrailer) -> NdbResult<Self> {
513        if trailer.page_type() != PageType::AllocationPageMap {
514            return Err(NdbError::UnexpectedPageType(trailer.page_type()));
515        }
516        Ok(Self {
517            map_bits: amap_bits,
518            trailer,
519            padding: 0,
520        })
521    }
522
523    fn read(f: &mut dyn Read) -> io::Result<Self> {
524        let mut buffer = [0_u8; 500];
525        f.read_exact(&mut buffer)?;
526        let mut cursor = Cursor::new(buffer);
527
528        let padding = cursor.read_u32::<LittleEndian>()?;
529
530        let mut map_bits = [0_u8; mem::size_of::<MapBits>()];
531        cursor.read_exact(&mut map_bits)?;
532
533        let buffer = cursor.into_inner();
534
535        let trailer = AnsiPageTrailer::read(f)?;
536        if trailer.page_type() != PageType::AllocationPageMap {
537            return Err(NdbError::UnexpectedPageType(trailer.page_type()).into());
538        }
539
540        let crc = compute_crc(0, &buffer);
541        if crc != trailer.crc() {
542            return Err(NdbError::InvalidPageCrc(crc).into());
543        }
544
545        Ok(Self {
546            map_bits,
547            trailer,
548            padding,
549        })
550    }
551
552    fn write(&self, f: &mut dyn Write) -> io::Result<()> {
553        let mut cursor = Cursor::new([0_u8; 500]);
554
555        cursor.write_u32::<LittleEndian>(self.padding)?;
556        cursor.write_all(&self.map_bits)?;
557
558        let buffer = cursor.into_inner();
559        let crc = compute_crc(0, &buffer);
560
561        f.write_all(&buffer)?;
562
563        let trailer = AnsiPageTrailer {
564            crc,
565            ..self.trailer
566        };
567        trailer.write(f)
568    }
569}
570
571impl MapPageReadWrite<AnsiPstFile, { PageType::FreeMap as u8 }>
572    for AnsiMapPage<{ PageType::FreeMap as u8 }>
573{
574    fn new(amap_bits: MapBits, trailer: AnsiPageTrailer) -> NdbResult<Self> {
575        if trailer.page_type() != PageType::FreeMap {
576            return Err(NdbError::UnexpectedPageType(trailer.page_type()));
577        }
578        Ok(Self {
579            map_bits: amap_bits,
580            trailer,
581            padding: 0,
582        })
583    }
584
585    fn read(f: &mut dyn Read) -> io::Result<Self> {
586        let mut buffer = [0_u8; 500];
587        f.read_exact(&mut buffer)?;
588        let mut cursor = Cursor::new(buffer);
589
590        let mut map_bits = [0_u8; mem::size_of::<MapBits>()];
591        cursor.read_exact(&mut map_bits)?;
592
593        let padding = cursor.read_u32::<LittleEndian>()?;
594
595        let buffer = cursor.into_inner();
596
597        let trailer = AnsiPageTrailer::read(f)?;
598        if trailer.page_type() != PageType::FreeMap {
599            return Err(NdbError::UnexpectedPageType(trailer.page_type()).into());
600        }
601
602        let crc = compute_crc(0, &buffer);
603        if crc != trailer.crc() {
604            return Err(NdbError::InvalidPageCrc(crc).into());
605        }
606
607        Ok(Self {
608            map_bits,
609            trailer,
610            padding,
611        })
612    }
613
614    fn write(&self, f: &mut dyn Write) -> io::Result<()> {
615        let mut cursor = Cursor::new([0_u8; 500]);
616
617        cursor.write_all(&self.map_bits)?;
618        cursor.write_u32::<LittleEndian>(self.padding)?;
619
620        let buffer = cursor.into_inner();
621        let crc = compute_crc(0, &buffer);
622
623        f.write_all(&buffer)?;
624
625        let trailer = AnsiPageTrailer {
626            crc,
627            ..self.trailer
628        };
629        trailer.write(f)
630    }
631}
632
633impl MapPageReadWrite<AnsiPstFile, { PageType::FreePageMap as u8 }>
634    for AnsiMapPage<{ PageType::FreePageMap as u8 }>
635{
636    fn new(amap_bits: MapBits, trailer: AnsiPageTrailer) -> NdbResult<Self> {
637        if trailer.page_type() != PageType::FreePageMap {
638            return Err(NdbError::UnexpectedPageType(trailer.page_type()));
639        }
640        Ok(Self {
641            map_bits: amap_bits,
642            trailer,
643            padding: 0,
644        })
645    }
646
647    fn read(f: &mut dyn Read) -> io::Result<Self> {
648        let mut buffer = [0_u8; 500];
649        f.read_exact(&mut buffer)?;
650        let mut cursor = Cursor::new(buffer);
651
652        let mut map_bits = [0_u8; mem::size_of::<MapBits>()];
653        cursor.read_exact(&mut map_bits)?;
654
655        let padding = cursor.read_u32::<LittleEndian>()?;
656
657        let buffer = cursor.into_inner();
658
659        let trailer = AnsiPageTrailer::read(f)?;
660        if trailer.page_type() != PageType::FreePageMap {
661            return Err(NdbError::UnexpectedPageType(trailer.page_type()).into());
662        }
663
664        let crc = compute_crc(0, &buffer);
665        if crc != trailer.crc() {
666            return Err(NdbError::InvalidPageCrc(crc).into());
667        }
668
669        Ok(Self {
670            map_bits,
671            trailer,
672            padding,
673        })
674    }
675
676    fn write(&self, f: &mut dyn Write) -> io::Result<()> {
677        let mut cursor = Cursor::new([0_u8; 500]);
678
679        cursor.write_all(&self.map_bits)?;
680        cursor.write_u32::<LittleEndian>(self.padding)?;
681
682        let buffer = cursor.into_inner();
683        let crc = compute_crc(0, &buffer);
684
685        f.write_all(&buffer)?;
686
687        let trailer = AnsiPageTrailer {
688            crc,
689            ..self.trailer
690        };
691        trailer.write(f)
692    }
693}
694
695const DENSITY_LIST_ENTRY_PAGE_NUMBER_MASK: u32 = 0x000F_FFFF;
696
697/// [DLISTPAGEENT](https://learn.microsoft.com/en-us/openspecs/office_file_formats/ms-pst/9d3c45b9-a415-446c-954f-b1b473dbb415)
698#[derive(Copy, Clone, Debug)]
699pub struct DensityListPageEntry(u32);
700
701impl DensityListPageEntry {
702    pub fn new(page: u32, free_slots: u16) -> NdbResult<Self> {
703        if page & !0x000F_FFFF != 0 {
704            return Err(NdbError::InvalidDensityListEntryPageNumber(page));
705        };
706        if free_slots & !0x0FFF != 0 {
707            return Err(NdbError::InvalidDensityListEntryFreeSlots(free_slots));
708        };
709
710        Ok(Self(page | ((free_slots as u32) << 20)))
711    }
712
713    pub fn read(f: &mut dyn Read) -> io::Result<Self> {
714        Ok(Self(f.read_u32::<LittleEndian>()?))
715    }
716
717    pub fn write(&self, f: &mut dyn Write) -> io::Result<()> {
718        f.write_u32::<LittleEndian>(self.0)
719    }
720
721    pub fn page(&self) -> u32 {
722        self.0 & DENSITY_LIST_ENTRY_PAGE_NUMBER_MASK
723    }
724
725    pub fn free_slots(&self) -> u16 {
726        (self.0 >> 20) as u16
727    }
728}
729
730pub const DENSITY_LIST_FILE_OFFSET: u64 = 0x4200;
731
732/// [DLISTPAGE](https://learn.microsoft.com/en-us/openspecs/office_file_formats/ms-pst/5d426b2d-ec10-4614-b768-46813652d5e3)
733pub trait DensityListPage<Pst>
734where
735    Pst: PstFile,
736{
737    fn backfill_complete(&self) -> bool;
738    fn current_page(&self) -> u32;
739    fn entries(&self) -> &[DensityListPageEntry];
740    fn trailer(&self) -> &<Pst as PstFile>::PageTrailer;
741}
742
743pub struct UnicodeDensityListPage {
744    backfill_complete: bool,
745    current_page: u32,
746    entry_count: u8,
747    entries:
748        [DensityListPageEntry; <Self as DensityListPageReadWrite<UnicodePstFile>>::MAX_ENTRIES],
749    trailer: UnicodePageTrailer,
750}
751
752impl DensityListPage<UnicodePstFile> for UnicodeDensityListPage {
753    fn backfill_complete(&self) -> bool {
754        self.backfill_complete
755    }
756
757    fn current_page(&self) -> u32 {
758        self.current_page
759    }
760
761    fn entries(&self) -> &[DensityListPageEntry] {
762        &self.entries[..self.entry_count as usize]
763    }
764
765    fn trailer(&self) -> &UnicodePageTrailer {
766        &self.trailer
767    }
768}
769
770impl DensityListPageReadWrite<UnicodePstFile> for UnicodeDensityListPage {
771    const MAX_ENTRIES: usize = 476 / mem::size_of::<DensityListPageEntry>();
772
773    fn new(
774        backfill_complete: bool,
775        current_page: u32,
776        entries: &[DensityListPageEntry],
777        trailer: UnicodePageTrailer,
778    ) -> NdbResult<Self> {
779        if entries.len() > Self::MAX_ENTRIES {
780            return Err(NdbError::InvalidDensityListEntryCount(entries.len()));
781        }
782
783        if trailer.page_type() != PageType::DensityList {
784            return Err(NdbError::UnexpectedPageType(trailer.page_type()));
785        }
786
787        let entry_count = entries.len() as u8;
788
789        let mut buffer = [DensityListPageEntry(0); Self::MAX_ENTRIES];
790        buffer[..entries.len()].copy_from_slice(entries);
791        let entries = buffer;
792
793        Ok(Self {
794            backfill_complete,
795            current_page,
796            entry_count,
797            entries,
798            trailer,
799        })
800    }
801
802    fn read<R: PstReader>(f: &mut R) -> io::Result<Self> {
803        f.seek(SeekFrom::Start(DENSITY_LIST_FILE_OFFSET))?;
804
805        let mut buffer = [0_u8; 496];
806        f.read_exact(&mut buffer)?;
807        let mut cursor = Cursor::new(buffer);
808
809        // bFlags
810        let backfill_complete = cursor.read_u8()? & 0x01 != 0;
811
812        // cEntDList
813        let entry_count = cursor.read_u8()?;
814        if entry_count > Self::MAX_ENTRIES as u8 {
815            return Err(NdbError::InvalidDensityListEntryCount(entry_count as usize).into());
816        }
817
818        // wPadding
819        if cursor.read_u16::<LittleEndian>()? != 0 {
820            return Err(NdbError::InvalidDensityListPadding.into());
821        }
822
823        // ulCurrentPage
824        let current_page = cursor.read_u32::<LittleEndian>()?;
825
826        // rgDListPageEnt
827        let mut entries = [DensityListPageEntry(0); Self::MAX_ENTRIES];
828        for entry in entries.iter_mut().take(entry_count as usize) {
829            *entry = DensityListPageEntry::read(&mut cursor)?;
830        }
831        cursor.seek(SeekFrom::Current(
832            ((Self::MAX_ENTRIES - entry_count as usize) * mem::size_of::<DensityListPageEntry>())
833                as i64,
834        ))?;
835
836        // rgPadding
837        let mut padding = [0_u8; 12];
838        cursor.read_exact(&mut padding)?;
839        if padding != [0; 12] {
840            return Err(NdbError::InvalidDensityListPadding.into());
841        }
842
843        let buffer = cursor.into_inner();
844
845        // pageTrailer
846        let trailer = UnicodePageTrailer::read(f)?;
847        if trailer.page_type() != PageType::DensityList {
848            return Err(NdbError::UnexpectedPageType(trailer.page_type()).into());
849        }
850
851        let crc = compute_crc(0, &buffer);
852        if crc != trailer.crc() {
853            return Err(NdbError::InvalidPageCrc(crc).into());
854        }
855
856        Ok(Self {
857            backfill_complete,
858            current_page,
859            entry_count,
860            entries,
861            trailer,
862        })
863    }
864
865    fn write<W: Write + Seek>(&self, f: &mut W) -> io::Result<()> {
866        let mut cursor = Cursor::new([0_u8; 496]);
867
868        // bFlags
869        cursor.write_u8(if self.backfill_complete { 0x01 } else { 0 })?;
870
871        // cEntDList
872        cursor.write_u8(self.entry_count)?;
873
874        // wPadding
875        cursor.write_u16::<LittleEndian>(0)?;
876
877        // ulCurrentPage
878        cursor.write_u32::<LittleEndian>(self.current_page)?;
879
880        // rgDListPageEnt
881        for entry in self.entries.iter() {
882            entry.write(&mut cursor)?;
883        }
884
885        // rgPadding
886        cursor.write_all(&[0; 12])?;
887
888        let buffer = cursor.into_inner();
889        let crc = compute_crc(0, &buffer);
890
891        f.seek(SeekFrom::Start(DENSITY_LIST_FILE_OFFSET))?;
892        f.write_all(&buffer)?;
893
894        // pageTrailer
895        let trailer = UnicodePageTrailer {
896            crc,
897            ..self.trailer
898        };
899        trailer.write(f)
900    }
901}
902
903pub struct AnsiDensityListPage {
904    backfill_complete: bool,
905    current_page: u32,
906    entry_count: u8,
907    entries: [DensityListPageEntry; <Self as DensityListPageReadWrite<AnsiPstFile>>::MAX_ENTRIES],
908    trailer: AnsiPageTrailer,
909}
910
911impl DensityListPage<AnsiPstFile> for AnsiDensityListPage {
912    fn backfill_complete(&self) -> bool {
913        self.backfill_complete
914    }
915
916    fn current_page(&self) -> u32 {
917        self.current_page
918    }
919
920    fn entries(&self) -> &[DensityListPageEntry] {
921        &self.entries[..self.entry_count as usize]
922    }
923
924    fn trailer(&self) -> &AnsiPageTrailer {
925        &self.trailer
926    }
927}
928
929impl DensityListPageReadWrite<AnsiPstFile> for AnsiDensityListPage {
930    const MAX_ENTRIES: usize = 480 / mem::size_of::<DensityListPageEntry>();
931
932    fn new(
933        backfill_complete: bool,
934        current_page: u32,
935        entries: &[DensityListPageEntry],
936        trailer: AnsiPageTrailer,
937    ) -> NdbResult<Self> {
938        if entries.len() > Self::MAX_ENTRIES {
939            return Err(NdbError::InvalidDensityListEntryCount(entries.len()));
940        }
941
942        if trailer.page_type() != PageType::DensityList {
943            return Err(NdbError::UnexpectedPageType(trailer.page_type()));
944        }
945
946        let entry_count = entries.len() as u8;
947
948        let mut buffer = [DensityListPageEntry(0); Self::MAX_ENTRIES];
949        buffer[..entries.len()].copy_from_slice(entries);
950        let entries = buffer;
951
952        Ok(Self {
953            backfill_complete,
954            current_page,
955            entry_count,
956            entries,
957            trailer,
958        })
959    }
960
961    fn read<R: PstReader>(f: &mut R) -> io::Result<Self> {
962        f.seek(SeekFrom::Start(DENSITY_LIST_FILE_OFFSET))?;
963
964        let mut buffer = [0_u8; 500];
965        f.read_exact(&mut buffer)?;
966        let mut cursor = Cursor::new(buffer);
967
968        // bFlags
969        let backfill_complete = cursor.read_u8()? & 0x01 != 0;
970
971        // cEntDList
972        let entry_count = cursor.read_u8()?;
973        if entry_count > Self::MAX_ENTRIES as u8 {
974            return Err(NdbError::InvalidDensityListEntryCount(entry_count as usize).into());
975        }
976
977        // wPadding
978        if cursor.read_u16::<LittleEndian>()? != 0 {
979            return Err(NdbError::InvalidDensityListPadding.into());
980        }
981
982        // ulCurrentPage
983        let current_page = cursor.read_u32::<LittleEndian>()?;
984
985        // rgDListPageEnt
986        let mut entries = [DensityListPageEntry(0); Self::MAX_ENTRIES];
987        for entry in entries.iter_mut().take(entry_count as usize) {
988            *entry = DensityListPageEntry::read(&mut cursor)?;
989        }
990        cursor.seek(SeekFrom::Current(
991            ((Self::MAX_ENTRIES - entry_count as usize) * mem::size_of::<DensityListPageEntry>())
992                as i64,
993        ))?;
994
995        // rgPadding
996        let mut padding = [0_u8; 12];
997        cursor.read_exact(&mut padding)?;
998        if padding != [0; 12] {
999            return Err(NdbError::InvalidDensityListPadding.into());
1000        }
1001
1002        let buffer = cursor.into_inner();
1003
1004        // pageTrailer
1005        let trailer = AnsiPageTrailer::read(f)?;
1006        if trailer.page_type() != PageType::DensityList {
1007            return Err(NdbError::UnexpectedPageType(trailer.page_type()).into());
1008        }
1009
1010        let crc = compute_crc(0, &buffer);
1011        if crc != trailer.crc() {
1012            return Err(NdbError::InvalidPageCrc(crc).into());
1013        }
1014
1015        Ok(Self {
1016            backfill_complete,
1017            current_page,
1018            entry_count,
1019            entries,
1020            trailer,
1021        })
1022    }
1023
1024    fn write<W: Write + Seek>(&self, f: &mut W) -> io::Result<()> {
1025        let mut cursor = Cursor::new([0_u8; 500]);
1026
1027        // bFlags
1028        cursor.write_u8(if self.backfill_complete { 0x01 } else { 0 })?;
1029
1030        // cEntDList
1031        cursor.write_u8(self.entry_count)?;
1032
1033        // wPadding
1034        cursor.write_u16::<LittleEndian>(0)?;
1035
1036        // ulCurrentPage
1037        cursor.write_u32::<LittleEndian>(self.current_page)?;
1038
1039        // rgDListPageEnt
1040        for entry in self.entries.iter() {
1041            entry.write(&mut cursor)?;
1042        }
1043
1044        // rgPadding
1045        cursor.write_all(&[0; 12])?;
1046
1047        let buffer = cursor.into_inner();
1048        let crc = compute_crc(0, &buffer);
1049
1050        f.seek(SeekFrom::Start(DENSITY_LIST_FILE_OFFSET))?;
1051        f.write_all(&buffer)?;
1052
1053        // pageTrailer
1054        let trailer = AnsiPageTrailer {
1055            crc,
1056            ..self.trailer
1057        };
1058        trailer.write(f)
1059    }
1060}
1061
1062pub trait BTreeEntryKey: Copy + Sized + Into<u64> + From<u32> {}
1063
1064impl BTreeEntryKey for u32 {}
1065impl BTreeEntryKey for u64 {}
1066
1067pub trait BTreeEntry: Copy + Sized {
1068    type Key: BTreeEntryKey;
1069
1070    fn key(&self) -> Self::Key;
1071}
1072
1073/// [BTPAGE](https://learn.microsoft.com/en-us/openspecs/office_file_formats/ms-pst/4f0cd8e7-c2d0-4975-90a4-d417cfca77f8)
1074pub trait BTreePage {
1075    type Entry: BTreeEntry;
1076    type Trailer: PageTrailer;
1077
1078    fn level(&self) -> u8;
1079    fn entries(&self) -> &[Self::Entry];
1080    fn trailer(&self) -> &Self::Trailer;
1081}
1082
1083pub struct UnicodeBTreeEntryPage {
1084    level: u8,
1085    max_entries: u8,
1086    entry_size: u8,
1087    entries: Vec<UnicodeBTreePageEntry>,
1088    trailer: UnicodePageTrailer,
1089}
1090
1091impl UnicodeBTreeEntryPage {
1092    pub fn new(
1093        level: u8,
1094        max_entries: u8,
1095        entry_size: u8,
1096        entries: &[UnicodeBTreePageEntry],
1097        trailer: UnicodePageTrailer,
1098    ) -> NdbResult<Self> {
1099        if !(1..=8).contains(&level) {
1100            return Err(NdbError::InvalidBTreePageLevel(level));
1101        }
1102
1103        if entries.len() > usize::from(max_entries) {
1104            return Err(NdbError::InvalidBTreeEntryCount(entries.len()));
1105        }
1106
1107        if trailer.page_type() != PageType::BlockBTree && trailer.page_type() != PageType::NodeBTree
1108        {
1109            return Err(NdbError::UnexpectedPageType(trailer.page_type()));
1110        }
1111
1112        let entries = entries.to_vec();
1113
1114        Ok(Self {
1115            level,
1116            max_entries,
1117            entry_size,
1118            entries,
1119            trailer,
1120        })
1121    }
1122}
1123
1124impl BTreePage for UnicodeBTreeEntryPage {
1125    type Entry = UnicodeBTreePageEntry;
1126    type Trailer = UnicodePageTrailer;
1127
1128    fn level(&self) -> u8 {
1129        self.level
1130    }
1131
1132    fn entries(&self) -> &[UnicodeBTreePageEntry] {
1133        &self.entries
1134    }
1135
1136    fn trailer(&self) -> &UnicodePageTrailer {
1137        &self.trailer
1138    }
1139}
1140
1141impl BTreePageReadWrite for UnicodeBTreeEntryPage {
1142    fn new(
1143        level: u8,
1144        max_entries: u8,
1145        entry_size: u8,
1146        entries: &[UnicodeBTreePageEntry],
1147        trailer: UnicodePageTrailer,
1148    ) -> NdbResult<Self> {
1149        Self::new(level, max_entries, entry_size, entries, trailer)
1150    }
1151
1152    fn max_entries(&self) -> u8 {
1153        self.max_entries
1154    }
1155
1156    fn entry_size(&self) -> u8 {
1157        self.entry_size
1158    }
1159}
1160
1161impl UnicodeBTreePageReadWrite<UnicodeBTreePageEntry> for UnicodeBTreeEntryPage {}
1162
1163pub struct AnsiBTreeEntryPage {
1164    level: u8,
1165    max_entries: u8,
1166    entry_size: u8,
1167    entries: Vec<AnsiBTreePageEntry>,
1168    trailer: AnsiPageTrailer,
1169}
1170
1171impl BTreePage for AnsiBTreeEntryPage {
1172    type Entry = AnsiBTreePageEntry;
1173    type Trailer = AnsiPageTrailer;
1174
1175    fn level(&self) -> u8 {
1176        self.level
1177    }
1178
1179    fn entries(&self) -> &[AnsiBTreePageEntry] {
1180        &self.entries
1181    }
1182
1183    fn trailer(&self) -> &AnsiPageTrailer {
1184        &self.trailer
1185    }
1186}
1187
1188impl BTreePageReadWrite for AnsiBTreeEntryPage {
1189    fn new(
1190        level: u8,
1191        max_entries: u8,
1192        entry_size: u8,
1193        entries: &[AnsiBTreePageEntry],
1194        trailer: AnsiPageTrailer,
1195    ) -> NdbResult<Self> {
1196        if !(1..=8).contains(&level) {
1197            return Err(NdbError::InvalidBTreePageLevel(level));
1198        }
1199
1200        if entries.len() > usize::from(max_entries) {
1201            return Err(NdbError::InvalidBTreeEntryCount(entries.len()));
1202        }
1203
1204        if trailer.page_type() != PageType::BlockBTree && trailer.page_type() != PageType::NodeBTree
1205        {
1206            return Err(NdbError::UnexpectedPageType(trailer.page_type()));
1207        }
1208
1209        let entries = entries.to_vec();
1210
1211        Ok(Self {
1212            level,
1213            max_entries,
1214            entry_size,
1215            entries,
1216            trailer,
1217        })
1218    }
1219
1220    fn max_entries(&self) -> u8 {
1221        self.max_entries
1222    }
1223
1224    fn entry_size(&self) -> u8 {
1225        self.entry_size
1226    }
1227}
1228
1229impl AnsiBTreePageReadWrite<AnsiBTreePageEntry> for AnsiBTreeEntryPage {}
1230
1231/// [BTENTRY](https://learn.microsoft.com/en-us/openspecs/office_file_formats/ms-pst/bc8052a3-f300-4022-be31-f0f408fffca0)
1232pub trait BTreePageEntry: BTreeEntry {
1233    type Block: BlockRef;
1234
1235    fn block(&self) -> Self::Block;
1236}
1237
1238impl<Entry> BTreeEntryReadWrite for Entry
1239where
1240    Entry: BTreeEntry<Key: BTreePageKeyReadWrite>
1241        + BTreePageEntry<Block: BlockRefReadWrite<Block: BlockIdReadWrite, Index: ByteIndexReadWrite>>
1242        + BTreePageEntryReadWrite,
1243{
1244    const ENTRY_SIZE: usize = <Entry as BTreePageEntryReadWrite>::ENTRY_SIZE;
1245
1246    fn read(f: &mut dyn Read) -> io::Result<Self> {
1247        Ok(Self::new(
1248            <Self as BTreeEntry>::Key::read(f)?,
1249            <Self as BTreePageEntry>::Block::read(f)?,
1250        ))
1251    }
1252
1253    fn write(&self, f: &mut dyn Write) -> io::Result<()> {
1254        self.key().write(f)?;
1255        self.block().write(f)
1256    }
1257}
1258
1259impl BTreePageKeyReadWrite for u64 {
1260    fn read(f: &mut dyn Read) -> io::Result<Self> {
1261        f.read_u64::<LittleEndian>()
1262    }
1263
1264    fn write(self, f: &mut dyn Write) -> io::Result<()> {
1265        f.write_u64::<LittleEndian>(self)
1266    }
1267}
1268
1269#[derive(Copy, Clone, Default, Debug)]
1270pub struct UnicodeBTreePageEntry {
1271    key: u64,
1272    block: UnicodePageRef,
1273}
1274
1275impl BTreeEntry for UnicodeBTreePageEntry {
1276    type Key = u64;
1277
1278    fn key(&self) -> u64 {
1279        self.key
1280    }
1281}
1282
1283impl BTreePageEntry for UnicodeBTreePageEntry {
1284    type Block = UnicodePageRef;
1285
1286    fn block(&self) -> UnicodePageRef {
1287        self.block
1288    }
1289}
1290
1291impl BTreePageEntryReadWrite for UnicodeBTreePageEntry {
1292    const ENTRY_SIZE: usize = 24;
1293
1294    fn new(key: u64, block: UnicodePageRef) -> Self {
1295        Self { key, block }
1296    }
1297}
1298
1299impl BTreePageKeyReadWrite for u32 {
1300    fn read(f: &mut dyn Read) -> io::Result<Self> {
1301        f.read_u32::<LittleEndian>()
1302    }
1303
1304    fn write(self, f: &mut dyn Write) -> io::Result<()> {
1305        f.write_u32::<LittleEndian>(self)
1306    }
1307}
1308
1309#[derive(Copy, Clone, Default, Debug)]
1310pub struct AnsiBTreePageEntry {
1311    key: u32,
1312    block: AnsiPageRef,
1313}
1314
1315impl BTreeEntry for AnsiBTreePageEntry {
1316    type Key = u32;
1317
1318    fn key(&self) -> u32 {
1319        self.key
1320    }
1321}
1322
1323impl BTreePageEntry for AnsiBTreePageEntry {
1324    type Block = AnsiPageRef;
1325
1326    fn block(&self) -> AnsiPageRef {
1327        self.block
1328    }
1329}
1330
1331impl BTreePageEntryReadWrite for AnsiBTreePageEntry {
1332    const ENTRY_SIZE: usize = 12;
1333
1334    fn new(key: u32, block: AnsiPageRef) -> Self {
1335        Self { key, block }
1336    }
1337}
1338
1339/// [BBTENTRY](https://learn.microsoft.com/en-us/openspecs/office_file_formats/ms-pst/53a4b926-8ac4-45c9-9c6d-8358d951dbcd)
1340pub trait BlockBTreeEntry: BTreeEntry {
1341    type Block: BlockRef;
1342
1343    fn block(&self) -> Self::Block;
1344    fn size(&self) -> u16;
1345    fn ref_count(&self) -> u16;
1346}
1347
1348#[derive(Copy, Clone, Default, Debug)]
1349pub struct UnicodeBlockBTreeEntry {
1350    block: UnicodeBlockRef,
1351    size: u16,
1352    ref_count: u16,
1353    padding: u32,
1354}
1355
1356impl UnicodeBlockBTreeEntry {
1357    pub fn new(block: UnicodeBlockRef, size: u16) -> Self {
1358        Self {
1359            block,
1360            size,
1361            ref_count: 1,
1362            ..Default::default()
1363        }
1364    }
1365}
1366
1367impl BTreeEntry for UnicodeBlockBTreeEntry {
1368    type Key = u64;
1369
1370    fn key(&self) -> u64 {
1371        self.block.block().search_key()
1372    }
1373}
1374
1375impl BTreeEntryReadWrite for UnicodeBlockBTreeEntry {
1376    const ENTRY_SIZE: usize = 24;
1377
1378    fn read(f: &mut dyn Read) -> io::Result<Self> {
1379        let block = UnicodeBlockRef::read(f)?;
1380        let size = f.read_u16::<LittleEndian>()?;
1381        let ref_count = f.read_u16::<LittleEndian>()?;
1382        let padding = f.read_u32::<LittleEndian>()?;
1383
1384        Ok(Self {
1385            block,
1386            size,
1387            ref_count,
1388            padding,
1389        })
1390    }
1391
1392    fn write(&self, f: &mut dyn Write) -> io::Result<()> {
1393        self.block.write(f)?;
1394        f.write_u16::<LittleEndian>(self.size)?;
1395        f.write_u16::<LittleEndian>(self.ref_count)?;
1396        f.write_u32::<LittleEndian>(self.padding)
1397    }
1398}
1399
1400impl BlockBTreeEntry for UnicodeBlockBTreeEntry {
1401    type Block = UnicodeBlockRef;
1402
1403    fn block(&self) -> UnicodeBlockRef {
1404        self.block
1405    }
1406
1407    fn size(&self) -> u16 {
1408        self.size
1409    }
1410
1411    fn ref_count(&self) -> u16 {
1412        self.ref_count
1413    }
1414}
1415
1416impl BlockBTreeEntryReadWrite for UnicodeBlockBTreeEntry {
1417    fn new(block: UnicodeBlockRef, size: u16) -> Self {
1418        Self::new(block, size)
1419    }
1420}
1421
1422pub struct UnicodeBlockBTreePage {
1423    max_entries: u8,
1424    entry_size: u8,
1425    entries: Vec<UnicodeBlockBTreeEntry>,
1426    trailer: UnicodePageTrailer,
1427}
1428
1429impl UnicodeBlockBTreePage {
1430    pub fn new(
1431        level: u8,
1432        max_entries: u8,
1433        entry_size: u8,
1434        entries: &[UnicodeBlockBTreeEntry],
1435        trailer: UnicodePageTrailer,
1436    ) -> NdbResult<Self> {
1437        if level != 0 {
1438            return Err(NdbError::InvalidBTreePageLevel(level));
1439        }
1440
1441        if entries.len() > usize::from(max_entries) {
1442            return Err(NdbError::InvalidBTreeEntryCount(entries.len()));
1443        }
1444
1445        if trailer.page_type() != PageType::BlockBTree {
1446            return Err(NdbError::UnexpectedPageType(trailer.page_type()));
1447        }
1448
1449        let entries = entries.to_vec();
1450
1451        Ok(Self {
1452            max_entries,
1453            entry_size,
1454            entries,
1455            trailer,
1456        })
1457    }
1458}
1459
1460impl BTreePage for UnicodeBlockBTreePage {
1461    type Entry = UnicodeBlockBTreeEntry;
1462    type Trailer = UnicodePageTrailer;
1463
1464    fn level(&self) -> u8 {
1465        0
1466    }
1467
1468    fn entries(&self) -> &[UnicodeBlockBTreeEntry] {
1469        &self.entries
1470    }
1471
1472    fn trailer(&self) -> &UnicodePageTrailer {
1473        &self.trailer
1474    }
1475}
1476
1477impl BTreePageReadWrite for UnicodeBlockBTreePage {
1478    fn new(
1479        level: u8,
1480        max_entries: u8,
1481        entry_size: u8,
1482        entries: &[UnicodeBlockBTreeEntry],
1483        trailer: UnicodePageTrailer,
1484    ) -> NdbResult<Self> {
1485        Self::new(level, max_entries, entry_size, entries, trailer)
1486    }
1487
1488    fn max_entries(&self) -> u8 {
1489        self.max_entries
1490    }
1491
1492    fn entry_size(&self) -> u8 {
1493        self.entry_size
1494    }
1495}
1496
1497impl UnicodeBTreePageReadWrite<UnicodeBlockBTreeEntry> for UnicodeBlockBTreePage {}
1498
1499#[derive(Copy, Clone, Default, Debug)]
1500pub struct AnsiBlockBTreeEntry {
1501    block: AnsiBlockRef,
1502    size: u16,
1503    ref_count: u16,
1504}
1505
1506impl AnsiBlockBTreeEntry {
1507    pub fn new(block: AnsiBlockRef, size: u16) -> Self {
1508        Self {
1509            block,
1510            size,
1511            ref_count: 1,
1512        }
1513    }
1514}
1515
1516impl BTreeEntry for AnsiBlockBTreeEntry {
1517    type Key = u32;
1518
1519    fn key(&self) -> u32 {
1520        self.block.block().search_key()
1521    }
1522}
1523
1524impl BTreeEntryReadWrite for AnsiBlockBTreeEntry {
1525    const ENTRY_SIZE: usize = 12;
1526
1527    fn read(f: &mut dyn Read) -> io::Result<Self> {
1528        Ok(Self {
1529            block: AnsiBlockRef::read(f)?,
1530            size: f.read_u16::<LittleEndian>()?,
1531            ref_count: f.read_u16::<LittleEndian>()?,
1532        })
1533    }
1534
1535    fn write(&self, f: &mut dyn Write) -> io::Result<()> {
1536        self.block.write(f)?;
1537        f.write_u16::<LittleEndian>(self.size)?;
1538        f.write_u16::<LittleEndian>(self.ref_count)
1539    }
1540}
1541
1542impl BlockBTreeEntry for AnsiBlockBTreeEntry {
1543    type Block = AnsiBlockRef;
1544
1545    fn block(&self) -> AnsiBlockRef {
1546        self.block
1547    }
1548
1549    fn size(&self) -> u16 {
1550        self.size
1551    }
1552
1553    fn ref_count(&self) -> u16 {
1554        self.ref_count
1555    }
1556}
1557
1558impl BlockBTreeEntryReadWrite for AnsiBlockBTreeEntry {
1559    fn new(block: AnsiBlockRef, size: u16) -> Self {
1560        Self::new(block, size)
1561    }
1562}
1563
1564pub struct AnsiBlockBTreePage {
1565    max_entries: u8,
1566    entry_size: u8,
1567    entries: Vec<AnsiBlockBTreeEntry>,
1568    trailer: AnsiPageTrailer,
1569}
1570
1571impl AnsiBlockBTreePage {
1572    pub fn new(
1573        level: u8,
1574        max_entries: u8,
1575        entry_size: u8,
1576        entries: &[AnsiBlockBTreeEntry],
1577        trailer: AnsiPageTrailer,
1578    ) -> NdbResult<Self> {
1579        if level != 0 {
1580            return Err(NdbError::InvalidBTreePageLevel(level));
1581        }
1582
1583        if entries.len() > usize::from(max_entries) {
1584            return Err(NdbError::InvalidBTreeEntryCount(entries.len()));
1585        }
1586
1587        if trailer.page_type() != PageType::BlockBTree {
1588            return Err(NdbError::UnexpectedPageType(trailer.page_type()));
1589        }
1590
1591        let entries = entries.to_vec();
1592
1593        Ok(Self {
1594            max_entries,
1595            entry_size,
1596            entries,
1597            trailer,
1598        })
1599    }
1600}
1601
1602impl BTreePage for AnsiBlockBTreePage {
1603    type Entry = AnsiBlockBTreeEntry;
1604    type Trailer = AnsiPageTrailer;
1605
1606    fn level(&self) -> u8 {
1607        0
1608    }
1609
1610    fn entries(&self) -> &[AnsiBlockBTreeEntry] {
1611        &self.entries
1612    }
1613
1614    fn trailer(&self) -> &AnsiPageTrailer {
1615        &self.trailer
1616    }
1617}
1618
1619impl BTreePageReadWrite for AnsiBlockBTreePage {
1620    fn new(
1621        level: u8,
1622        max_entries: u8,
1623        entry_size: u8,
1624        entries: &[AnsiBlockBTreeEntry],
1625        trailer: AnsiPageTrailer,
1626    ) -> NdbResult<Self> {
1627        Self::new(level, max_entries, entry_size, entries, trailer)
1628    }
1629
1630    fn max_entries(&self) -> u8 {
1631        self.max_entries
1632    }
1633
1634    fn entry_size(&self) -> u8 {
1635        self.entry_size
1636    }
1637}
1638
1639impl AnsiBTreePageReadWrite<AnsiBlockBTreeEntry> for AnsiBlockBTreePage {}
1640
1641/// [NBTENTRY](https://learn.microsoft.com/en-us/openspecs/office_file_formats/ms-pst/53a4b926-8ac4-45c9-9c6d-8358d951dbcd)
1642pub trait NodeBTreeEntry: BTreeEntry {
1643    type Block: BlockId;
1644
1645    fn node(&self) -> NodeId;
1646    fn data(&self) -> Self::Block;
1647    fn sub_node(&self) -> Option<Self::Block>;
1648    fn parent(&self) -> Option<NodeId>;
1649}
1650
1651#[derive(Copy, Clone, Default, Debug)]
1652pub struct UnicodeNodeBTreeEntry {
1653    node: NodeId,
1654    data: UnicodeBlockId,
1655    sub_node: Option<UnicodeBlockId>,
1656    parent: Option<NodeId>,
1657    padding: u32,
1658}
1659
1660impl UnicodeNodeBTreeEntry {
1661    pub fn new(
1662        node: NodeId,
1663        data: UnicodeBlockId,
1664        sub_node: Option<UnicodeBlockId>,
1665        parent: Option<NodeId>,
1666    ) -> Self {
1667        Self {
1668            node,
1669            data,
1670            sub_node,
1671            parent,
1672            ..Default::default()
1673        }
1674    }
1675}
1676
1677impl BTreeEntry for UnicodeNodeBTreeEntry {
1678    type Key = u64;
1679
1680    fn key(&self) -> u64 {
1681        u64::from(u32::from(self.node))
1682    }
1683}
1684
1685impl BTreeEntryReadWrite for UnicodeNodeBTreeEntry {
1686    const ENTRY_SIZE: usize = 32;
1687
1688    fn read(f: &mut dyn Read) -> io::Result<Self> {
1689        // nid
1690        let node = f.read_u64::<LittleEndian>()?;
1691        let Ok(node) = u32::try_from(node) else {
1692            return Err(NdbError::InvalidNodeBTreeEntryNodeId(node).into());
1693        };
1694        let node = NodeId::from(node);
1695
1696        // bidData
1697        let data = UnicodeBlockId::read(f)?;
1698
1699        // bidSub
1700        let sub_node = UnicodeBlockId::read(f)?;
1701        let sub_node = if sub_node.search_key() == 0 {
1702            None
1703        } else {
1704            Some(sub_node)
1705        };
1706
1707        // nidParent
1708        let parent = NodeId::read(f)?;
1709        let parent = if u32::from(parent) == 0 {
1710            None
1711        } else {
1712            Some(parent)
1713        };
1714
1715        // dwPadding
1716        let padding = f.read_u32::<LittleEndian>()?;
1717
1718        Ok(Self {
1719            node,
1720            data,
1721            sub_node,
1722            parent,
1723            padding,
1724        })
1725    }
1726
1727    fn write(&self, f: &mut dyn Write) -> io::Result<()> {
1728        // nid
1729        f.write_u64::<LittleEndian>(u64::from(u32::from(self.node)))?;
1730
1731        // bidData
1732        self.data.write(f)?;
1733
1734        // bidSub
1735        self.sub_node.unwrap_or_default().write(f)?;
1736
1737        // nidParent
1738        self.parent.unwrap_or_default().write(f)?;
1739
1740        // dwPadding
1741        f.write_u32::<LittleEndian>(self.padding)
1742    }
1743}
1744
1745impl NodeBTreeEntry for UnicodeNodeBTreeEntry {
1746    type Block = UnicodeBlockId;
1747
1748    fn node(&self) -> NodeId {
1749        self.node
1750    }
1751
1752    fn data(&self) -> UnicodeBlockId {
1753        self.data
1754    }
1755
1756    fn sub_node(&self) -> Option<UnicodeBlockId> {
1757        self.sub_node
1758    }
1759
1760    fn parent(&self) -> Option<NodeId> {
1761        self.parent
1762    }
1763}
1764
1765impl NodeBTreeEntryReadWrite for UnicodeNodeBTreeEntry {
1766    fn new(
1767        node: NodeId,
1768        data: UnicodeBlockId,
1769        sub_node: Option<UnicodeBlockId>,
1770        parent: Option<NodeId>,
1771    ) -> Self {
1772        Self::new(node, data, sub_node, parent)
1773    }
1774}
1775
1776pub struct UnicodeNodeBTreePage {
1777    max_entries: u8,
1778    entry_size: u8,
1779    entries: Vec<UnicodeNodeBTreeEntry>,
1780    trailer: UnicodePageTrailer,
1781}
1782
1783impl UnicodeNodeBTreePage {
1784    pub fn new(
1785        level: u8,
1786        max_entries: u8,
1787        entry_size: u8,
1788        entries: &[UnicodeNodeBTreeEntry],
1789        trailer: UnicodePageTrailer,
1790    ) -> NdbResult<Self> {
1791        if level != 0 {
1792            return Err(NdbError::InvalidBTreePageLevel(level));
1793        }
1794
1795        if entries.len() > usize::from(max_entries) {
1796            return Err(NdbError::InvalidBTreeEntryCount(entries.len()));
1797        }
1798
1799        if trailer.page_type() != PageType::NodeBTree {
1800            return Err(NdbError::UnexpectedPageType(trailer.page_type()));
1801        }
1802
1803        let entries = entries.to_vec();
1804
1805        Ok(Self {
1806            max_entries,
1807            entry_size,
1808            entries,
1809            trailer,
1810        })
1811    }
1812}
1813
1814impl BTreePage for UnicodeNodeBTreePage {
1815    type Entry = UnicodeNodeBTreeEntry;
1816    type Trailer = UnicodePageTrailer;
1817
1818    fn level(&self) -> u8 {
1819        0
1820    }
1821
1822    fn entries(&self) -> &[UnicodeNodeBTreeEntry] {
1823        &self.entries
1824    }
1825
1826    fn trailer(&self) -> &UnicodePageTrailer {
1827        &self.trailer
1828    }
1829}
1830
1831impl BTreePageReadWrite for UnicodeNodeBTreePage {
1832    fn new(
1833        level: u8,
1834        max_entries: u8,
1835        entry_size: u8,
1836        entries: &[UnicodeNodeBTreeEntry],
1837        trailer: UnicodePageTrailer,
1838    ) -> NdbResult<Self> {
1839        Self::new(level, max_entries, entry_size, entries, trailer)
1840    }
1841
1842    fn max_entries(&self) -> u8 {
1843        self.max_entries
1844    }
1845
1846    fn entry_size(&self) -> u8 {
1847        self.entry_size
1848    }
1849}
1850
1851impl UnicodeBTreePageReadWrite<UnicodeNodeBTreeEntry> for UnicodeNodeBTreePage {}
1852
1853#[derive(Copy, Clone, Default, Debug)]
1854pub struct AnsiNodeBTreeEntry {
1855    node: NodeId,
1856    data: AnsiBlockId,
1857    sub_node: Option<AnsiBlockId>,
1858    parent: Option<NodeId>,
1859}
1860
1861impl AnsiNodeBTreeEntry {
1862    pub fn new(
1863        node: NodeId,
1864        data: AnsiBlockId,
1865        sub_node: Option<AnsiBlockId>,
1866        parent: Option<NodeId>,
1867    ) -> Self {
1868        Self {
1869            node,
1870            data,
1871            sub_node,
1872            parent,
1873        }
1874    }
1875}
1876
1877impl BTreeEntry for AnsiNodeBTreeEntry {
1878    type Key = u32;
1879
1880    fn key(&self) -> u32 {
1881        u32::from(self.node)
1882    }
1883}
1884
1885impl BTreeEntryReadWrite for AnsiNodeBTreeEntry {
1886    const ENTRY_SIZE: usize = 16;
1887
1888    fn read(f: &mut dyn Read) -> io::Result<Self> {
1889        // nid
1890        let node = NodeId::read(f)?;
1891
1892        // bidData
1893        let data = AnsiBlockId::read(f)?;
1894
1895        // bidSub
1896        let sub_node = AnsiBlockId::read(f)?;
1897        let sub_node = if sub_node.search_key() == 0 {
1898            None
1899        } else {
1900            Some(sub_node)
1901        };
1902
1903        // nidParent
1904        let parent = NodeId::read(f)?;
1905        let parent = if u32::from(parent) == 0 {
1906            None
1907        } else {
1908            Some(parent)
1909        };
1910
1911        Ok(Self {
1912            node,
1913            data,
1914            sub_node,
1915            parent,
1916        })
1917    }
1918
1919    fn write(&self, f: &mut dyn Write) -> io::Result<()> {
1920        // nid
1921        self.node.write(f)?;
1922
1923        // bidData
1924        self.data.write(f)?;
1925
1926        // bidSub
1927        self.sub_node.unwrap_or_default().write(f)?;
1928
1929        // nidParent
1930        self.parent.unwrap_or_default().write(f)
1931    }
1932}
1933
1934impl NodeBTreeEntry for AnsiNodeBTreeEntry {
1935    type Block = AnsiBlockId;
1936
1937    fn node(&self) -> NodeId {
1938        self.node
1939    }
1940
1941    fn data(&self) -> AnsiBlockId {
1942        self.data
1943    }
1944
1945    fn sub_node(&self) -> Option<AnsiBlockId> {
1946        self.sub_node
1947    }
1948
1949    fn parent(&self) -> Option<NodeId> {
1950        self.parent
1951    }
1952}
1953
1954impl NodeBTreeEntryReadWrite for AnsiNodeBTreeEntry {
1955    fn new(
1956        node: NodeId,
1957        data: AnsiBlockId,
1958        sub_node: Option<AnsiBlockId>,
1959        parent: Option<NodeId>,
1960    ) -> Self {
1961        Self::new(node, data, sub_node, parent)
1962    }
1963}
1964
1965pub struct AnsiNodeBTreePage {
1966    max_entries: u8,
1967    entry_size: u8,
1968    entries: Vec<AnsiNodeBTreeEntry>,
1969    trailer: AnsiPageTrailer,
1970}
1971
1972impl AnsiNodeBTreePage {
1973    pub fn new(
1974        level: u8,
1975        max_entries: u8,
1976        entry_size: u8,
1977        entries: &[AnsiNodeBTreeEntry],
1978        trailer: AnsiPageTrailer,
1979    ) -> NdbResult<Self> {
1980        if level != 0 {
1981            return Err(NdbError::InvalidBTreePageLevel(level));
1982        }
1983
1984        if entries.len() > usize::from(max_entries) {
1985            return Err(NdbError::InvalidBTreeEntryCount(entries.len()));
1986        }
1987
1988        if trailer.page_type() != PageType::NodeBTree {
1989            return Err(NdbError::UnexpectedPageType(trailer.page_type()));
1990        }
1991
1992        let entries = entries.to_vec();
1993
1994        Ok(Self {
1995            max_entries,
1996            entry_size,
1997            entries,
1998            trailer,
1999        })
2000    }
2001}
2002
2003impl BTreePage for AnsiNodeBTreePage {
2004    type Entry = AnsiNodeBTreeEntry;
2005    type Trailer = AnsiPageTrailer;
2006
2007    fn level(&self) -> u8 {
2008        0
2009    }
2010
2011    fn entries(&self) -> &[AnsiNodeBTreeEntry] {
2012        &self.entries
2013    }
2014
2015    fn trailer(&self) -> &AnsiPageTrailer {
2016        &self.trailer
2017    }
2018}
2019
2020impl BTreePageReadWrite for AnsiNodeBTreePage {
2021    fn new(
2022        level: u8,
2023        max_entries: u8,
2024        entry_size: u8,
2025        entries: &[AnsiNodeBTreeEntry],
2026        trailer: AnsiPageTrailer,
2027    ) -> NdbResult<Self> {
2028        Self::new(level, max_entries, entry_size, entries, trailer)
2029    }
2030
2031    fn max_entries(&self) -> u8 {
2032        self.max_entries
2033    }
2034
2035    fn entry_size(&self) -> u8 {
2036        self.entry_size
2037    }
2038}
2039
2040impl AnsiBTreePageReadWrite<AnsiNodeBTreeEntry> for AnsiNodeBTreePage {}
2041
2042pub trait RootBTreeIntermediatePage<Pst, Entry, LeafPage>
2043where
2044    Pst: PstFile,
2045    Entry: BTreeEntry<Key = <Pst as PstFile>::BTreeKey>,
2046    LeafPage: RootBTreeLeafPage<Pst, Entry = Entry>,
2047    Self: BTreePage<
2048        Entry = <Self as RootBTreeIntermediatePage<Pst, Entry, LeafPage>>::Entry,
2049        Trailer = <Pst as PstFile>::PageTrailer,
2050    >,
2051{
2052    type Entry: BTreeEntry<Key = <Pst as PstFile>::BTreeKey>
2053        + BTreePageEntry<Block = <Pst as PstFile>::PageRef>;
2054    type Page: BTreePageReadWrite<
2055        Entry = <Self as RootBTreeIntermediatePage<Pst, Entry, LeafPage>>::Entry,
2056        Trailer = <Pst as PstFile>::PageTrailer,
2057    >;
2058}
2059
2060impl<Entry, LeafPage> RootBTreeIntermediatePage<UnicodePstFile, Entry, LeafPage>
2061    for UnicodeBTreeEntryPage
2062where
2063    Entry: BTreeEntry<Key = u64> + BTreeEntryReadWrite,
2064    LeafPage: RootBTreeLeafPage<UnicodePstFile, Entry = Entry>,
2065{
2066    type Entry = UnicodeBTreePageEntry;
2067    type Page = UnicodeBTreeEntryPage;
2068}
2069
2070impl<Entry, LeafPage> RootBTreeIntermediatePageReadWrite<UnicodePstFile, Entry, LeafPage>
2071    for UnicodeBTreeEntryPage
2072where
2073    Entry: BTreeEntry<Key = u64> + BTreeEntryReadWrite,
2074    LeafPage: RootBTreeLeafPage<UnicodePstFile, Entry = Entry>
2075        + RootBTreeLeafPageReadWrite<UnicodePstFile>,
2076{
2077    fn read<R: PstReader>(f: &mut R) -> io::Result<Self> {
2078        <Self as UnicodeBTreePageReadWrite<UnicodeBTreePageEntry>>::read(f)
2079    }
2080
2081    fn write<W: Write + Seek>(&self, f: &mut W) -> io::Result<()> {
2082        <Self as UnicodeBTreePageReadWrite<UnicodeBTreePageEntry>>::write(self, f)
2083    }
2084}
2085
2086impl<Entry, LeafPage> RootBTreeIntermediatePage<AnsiPstFile, Entry, LeafPage> for AnsiBTreeEntryPage
2087where
2088    Entry: BTreeEntry<Key = u32> + BTreeEntryReadWrite,
2089    LeafPage: RootBTreeLeafPage<AnsiPstFile, Entry = Entry>,
2090{
2091    type Entry = AnsiBTreePageEntry;
2092    type Page = AnsiBTreeEntryPage;
2093}
2094
2095impl<Entry, LeafPage> RootBTreeIntermediatePageReadWrite<AnsiPstFile, Entry, LeafPage>
2096    for AnsiBTreeEntryPage
2097where
2098    Entry: BTreeEntry<Key = u32> + BTreeEntryReadWrite,
2099    LeafPage:
2100        RootBTreeLeafPage<AnsiPstFile, Entry = Entry> + RootBTreeLeafPageReadWrite<AnsiPstFile>,
2101{
2102    fn read<R: PstReader>(f: &mut R) -> io::Result<Self> {
2103        <Self as AnsiBTreePageReadWrite<AnsiBTreePageEntry>>::read(f)
2104    }
2105
2106    fn write<W: Write + Seek>(&self, f: &mut W) -> io::Result<()> {
2107        <Self as AnsiBTreePageReadWrite<AnsiBTreePageEntry>>::write(self, f)
2108    }
2109}
2110
2111pub trait RootBTreeLeafPage<Pst>
2112where
2113    Pst: PstFile,
2114    Self: BTreePage<
2115        Entry = <Self as RootBTreeLeafPage<Pst>>::Entry,
2116        Trailer = <Pst as PstFile>::PageTrailer,
2117    >,
2118{
2119    type Entry: BTreeEntry<Key = <Pst as PstFile>::BTreeKey>;
2120}
2121
2122impl RootBTreeLeafPage<UnicodePstFile> for UnicodeBlockBTreePage {
2123    type Entry = UnicodeBlockBTreeEntry;
2124}
2125
2126impl RootBTreeLeafPageReadWrite<UnicodePstFile> for UnicodeBlockBTreePage {
2127    const BTREE_ENTRIES_SIZE: usize = UNICODE_BTREE_ENTRIES_SIZE;
2128
2129    fn read<R: PstReader>(f: &mut R) -> io::Result<Self> {
2130        <Self as UnicodeBTreePageReadWrite<UnicodeBlockBTreeEntry>>::read(f)
2131    }
2132
2133    fn write<W: Write + Seek>(&self, f: &mut W) -> io::Result<()> {
2134        <Self as UnicodeBTreePageReadWrite<UnicodeBlockBTreeEntry>>::write(self, f)
2135    }
2136}
2137
2138impl RootBTreeLeafPage<AnsiPstFile> for AnsiBlockBTreePage {
2139    type Entry = AnsiBlockBTreeEntry;
2140}
2141
2142impl RootBTreeLeafPageReadWrite<AnsiPstFile> for AnsiBlockBTreePage {
2143    const BTREE_ENTRIES_SIZE: usize = ANSI_BTREE_ENTRIES_SIZE;
2144
2145    fn read<R: PstReader>(f: &mut R) -> io::Result<Self> {
2146        <Self as AnsiBTreePageReadWrite<AnsiBlockBTreeEntry>>::read(f)
2147    }
2148
2149    fn write<W: Write + Seek>(&self, f: &mut W) -> io::Result<()> {
2150        <Self as AnsiBTreePageReadWrite<AnsiBlockBTreeEntry>>::write(self, f)
2151    }
2152}
2153
2154impl RootBTreeLeafPage<UnicodePstFile> for UnicodeNodeBTreePage {
2155    type Entry = UnicodeNodeBTreeEntry;
2156}
2157
2158impl RootBTreeLeafPageReadWrite<UnicodePstFile> for UnicodeNodeBTreePage {
2159    const BTREE_ENTRIES_SIZE: usize = UNICODE_BTREE_ENTRIES_SIZE;
2160
2161    fn read<R: PstReader>(f: &mut R) -> io::Result<Self> {
2162        <Self as UnicodeBTreePageReadWrite<UnicodeNodeBTreeEntry>>::read(f)
2163    }
2164
2165    fn write<W: Write + Seek>(&self, f: &mut W) -> io::Result<()> {
2166        <Self as UnicodeBTreePageReadWrite<UnicodeNodeBTreeEntry>>::write(self, f)
2167    }
2168}
2169
2170impl RootBTreeLeafPage<AnsiPstFile> for AnsiNodeBTreePage {
2171    type Entry = AnsiNodeBTreeEntry;
2172}
2173
2174impl RootBTreeLeafPageReadWrite<AnsiPstFile> for AnsiNodeBTreePage {
2175    const BTREE_ENTRIES_SIZE: usize = ANSI_BTREE_ENTRIES_SIZE;
2176
2177    fn read<R: PstReader>(f: &mut R) -> io::Result<Self> {
2178        <Self as AnsiBTreePageReadWrite<AnsiNodeBTreeEntry>>::read(f)
2179    }
2180
2181    fn write<W: Write + Seek>(&self, f: &mut W) -> io::Result<()> {
2182        <Self as AnsiBTreePageReadWrite<AnsiNodeBTreeEntry>>::write(self, f)
2183    }
2184}
2185
2186pub trait RootBTree {
2187    type Pst: PstFile<BTreeKey: BTreeEntryKey>;
2188    type Entry: BTreeEntry<Key = <Self::Pst as PstFile>::BTreeKey> + Sized;
2189    type IntermediatePage: RootBTreeIntermediatePage<Self::Pst, Self::Entry, Self::LeafPage>;
2190    type LeafPage: RootBTreeLeafPage<Self::Pst, Entry = Self::Entry>;
2191}
2192
2193pub enum RootBTreePage<Pst, Entry, IntermediatePage, LeafPage>
2194where
2195    Pst: PstFile,
2196    Entry: BTreeEntry<Key = <Pst as PstFile>::BTreeKey>,
2197    IntermediatePage: RootBTreeIntermediatePage<Pst, Entry, LeafPage>,
2198    LeafPage: RootBTreeLeafPage<Pst, Entry = Entry>,
2199{
2200    Intermediate(Box<IntermediatePage>, PhantomData<(Pst, Entry)>),
2201    Leaf(Box<LeafPage>),
2202}
2203
2204impl<Pst, Entry, IntermediatePage, LeafPage> RootBTree
2205    for RootBTreePage<Pst, Entry, IntermediatePage, LeafPage>
2206where
2207    Pst: PstFile,
2208    Entry: BTreeEntry<Key = <Pst as PstFile>::BTreeKey>,
2209    IntermediatePage: RootBTreeIntermediatePage<Pst, Entry, LeafPage>,
2210    LeafPage: RootBTreeLeafPage<Pst, Entry = Entry>,
2211{
2212    type Pst = Pst;
2213    type Entry = Entry;
2214    type IntermediatePage = IntermediatePage;
2215    type LeafPage = LeafPage;
2216}
2217
2218impl<Pst, Entry, IntermediatePage, LeafPage> RootBTreeReadWrite
2219    for RootBTreePage<Pst, Entry, IntermediatePage, LeafPage>
2220where
2221    Pst: PstFile,
2222    <Pst as PstFile>::BlockId: BlockIdReadWrite,
2223    <Pst as PstFile>::ByteIndex: ByteIndexReadWrite,
2224    <Pst as PstFile>::BlockRef: BlockRefReadWrite,
2225    <Pst as PstFile>::PageRef: BlockRefReadWrite,
2226    <Pst as PstFile>::PageTrailer: PageTrailerReadWrite,
2227    <Pst as PstFile>::BTreeKey: BTreePageKeyReadWrite + Into<u64>,
2228    Entry: BTreeEntry<Key = <Pst as PstFile>::BTreeKey> + BTreeEntryReadWrite,
2229    IntermediatePage: RootBTreeIntermediatePage<Pst, Entry, LeafPage>,
2230    LeafPage: RootBTreeLeafPage<Pst, Entry = Entry>,
2231    <Self as RootBTree>::Entry: BTreeEntry<Key = <Pst as PstFile>::BTreeKey> + BTreeEntryReadWrite,
2232    <Self as RootBTree>::IntermediatePage: RootBTreeIntermediatePageReadWrite<Pst, Entry, LeafPage>,
2233    <Self as RootBTree>::LeafPage: RootBTreeLeafPageReadWrite<Pst>,
2234{
2235    fn read<R: PstReader>(f: &mut R, block: <Pst as PstFile>::PageRef) -> io::Result<Self> {
2236        f.seek(SeekFrom::Start(block.index().index().into()))?;
2237
2238        let mut buffer = [0_u8; PAGE_SIZE];
2239        f.read_exact(&mut buffer)?;
2240        let mut cursor = Cursor::new(buffer);
2241
2242        cursor.seek(SeekFrom::Start(LeafPage::BTREE_ENTRIES_SIZE as u64 + 3))?;
2243        let level = cursor.read_u8()?;
2244
2245        cursor.seek(SeekFrom::Start(0))?;
2246        Ok(if level == 0 {
2247            Self::Leaf(Box::new(LeafPage::read(&mut cursor)?))
2248        } else {
2249            Self::Intermediate(Box::new(IntermediatePage::read(&mut cursor)?), PhantomData)
2250        })
2251    }
2252
2253    fn write<W: Write + Seek>(
2254        &self,
2255        f: &mut W,
2256        block: <Pst as PstFile>::PageRef,
2257    ) -> io::Result<()> {
2258        f.seek(SeekFrom::Start(block.index().index().into()))?;
2259
2260        match self {
2261            Self::Intermediate(page, ..) => page.write(f),
2262            Self::Leaf(page) => page.write(f),
2263        }
2264    }
2265
2266    fn find_entry<R: PstReader>(
2267        &self,
2268        f: &mut R,
2269        key: <Pst as PstFile>::BTreeKey,
2270        page_cache: &mut RootBTreePageCache<Self>,
2271    ) -> io::Result<Entry> {
2272        let search_key: u64 = key.into();
2273        match self {
2274            Self::Intermediate(page, ..) => {
2275                let entries = <Self::IntermediatePage as BTreePage>::entries(page);
2276                let index = entries.partition_point(|entry| entry.key().into() <= search_key);
2277                let entry = index
2278                    .checked_sub(1)
2279                    .and_then(|index| entries.get(index))
2280                    .ok_or(NdbError::BTreePageNotFound(search_key))?;
2281                let block = entry.block();
2282                let page = match page_cache.remove(&block.block()) {
2283                    Some(page) => page,
2284                    None => <Self as RootBTreeReadWrite>::read(f, block)?,
2285                };
2286                let entry = page.find_entry(f, key, page_cache);
2287                page_cache.insert(block.block(), page);
2288                entry
2289            }
2290            Self::Leaf(page) => {
2291                let entry = <Self::LeafPage as BTreePage>::entries(page)
2292                    .iter()
2293                    .find(|entry| entry.key().into() == search_key)
2294                    .ok_or(NdbError::BTreePageNotFound(search_key))?;
2295                Ok(*entry)
2296            }
2297        }
2298    }
2299}
2300
2301impl<Pst, Entry, IntermediatePage, LeafPage> RootBTreePage<Pst, Entry, IntermediatePage, LeafPage>
2302where
2303    Pst: PstFile,
2304    <Pst as PstFile>::BlockId: BlockIdReadWrite,
2305    <Pst as PstFile>::ByteIndex: ByteIndexReadWrite,
2306    <Pst as PstFile>::BlockRef: BlockRefReadWrite,
2307    <Pst as PstFile>::PageRef: BlockRefReadWrite,
2308    <Pst as PstFile>::PageTrailer: PageTrailerReadWrite,
2309    <Pst as PstFile>::BTreeKey: BTreePageKeyReadWrite + Into<u64>,
2310    Entry: BTreeEntry<Key = <Pst as PstFile>::BTreeKey> + BTreeEntryReadWrite,
2311    IntermediatePage: RootBTreeIntermediatePage<Pst, Entry, LeafPage>,
2312    LeafPage: RootBTreeLeafPage<Pst, Entry = Entry>,
2313    <Self as RootBTree>::Entry: BTreeEntry<Key = <Pst as PstFile>::BTreeKey> + BTreeEntryReadWrite,
2314    <Self as RootBTree>::IntermediatePage: RootBTreeIntermediatePageReadWrite<Pst, Entry, LeafPage>,
2315    <Self as RootBTree>::LeafPage: RootBTreeLeafPageReadWrite<Pst>,
2316{
2317    pub fn read<R: PstReader>(f: &mut R, block: <Pst as PstFile>::PageRef) -> io::Result<Self> {
2318        <Self as RootBTreeReadWrite>::read(f, block)
2319    }
2320
2321    pub fn write<W: Write + Seek>(
2322        &self,
2323        f: &mut W,
2324        block: <Pst as PstFile>::PageRef,
2325    ) -> io::Result<()> {
2326        <Self as RootBTreeReadWrite>::write(self, f, block)
2327    }
2328
2329    pub fn find_entry<R: PstReader>(
2330        &self,
2331        f: &mut R,
2332        key: <Pst as PstFile>::BTreeKey,
2333        page_cache: &mut RootBTreePageCache<Self>,
2334    ) -> io::Result<Entry> {
2335        <Self as RootBTreeReadWrite>::find_entry(self, f, key, page_cache)
2336    }
2337}
2338
2339pub type UnicodeBTree<Entry, LeafPage> =
2340    RootBTreePage<UnicodePstFile, Entry, UnicodeBTreeEntryPage, LeafPage>;
2341
2342pub type AnsiBTree<Entry, LeafPage> =
2343    RootBTreePage<AnsiPstFile, Entry, AnsiBTreeEntryPage, LeafPage>;
2344
2345pub trait BlockBTree<Pst, Entry>: RootBTree<Pst = Pst, Entry = Entry>
2346where
2347    Pst: PstFile,
2348    Entry: BTreeEntry<Key = <Pst as PstFile>::BTreeKey>
2349        + BlockBTreeEntry<Block = <Pst as PstFile>::BlockRef>,
2350    <Self as RootBTree>::IntermediatePage:
2351        RootBTreeIntermediatePage<Pst, Entry, <Self as RootBTree>::LeafPage>,
2352    <Self as RootBTree>::LeafPage: RootBTreeLeafPage<Pst, Entry = <Self as RootBTree>::Entry>,
2353{
2354}
2355
2356pub type UnicodeBlockBTree = UnicodeBTree<UnicodeBlockBTreeEntry, UnicodeBlockBTreePage>;
2357impl BlockBTree<UnicodePstFile, UnicodeBlockBTreeEntry> for UnicodeBlockBTree {}
2358impl BlockBTreeReadWrite<UnicodePstFile, UnicodeBlockBTreeEntry> for UnicodeBlockBTree {}
2359
2360pub type AnsiBlockBTree = AnsiBTree<AnsiBlockBTreeEntry, AnsiBlockBTreePage>;
2361impl BlockBTree<AnsiPstFile, AnsiBlockBTreeEntry> for AnsiBlockBTree {}
2362impl BlockBTreeReadWrite<AnsiPstFile, AnsiBlockBTreeEntry> for AnsiBlockBTree {}
2363
2364pub trait NodeBTree<Pst, Entry>: RootBTree<Pst = Pst, Entry = Entry>
2365where
2366    Pst: PstFile,
2367    Entry: BTreeEntry<Key = <Pst as PstFile>::BTreeKey>
2368        + NodeBTreeEntry<Block = <Pst as PstFile>::BlockId>,
2369    <Self as RootBTree>::IntermediatePage:
2370        RootBTreeIntermediatePage<Pst, Entry, <Self as RootBTree>::LeafPage>,
2371    <Self as RootBTree>::LeafPage: RootBTreeLeafPage<Pst, Entry = <Self as RootBTree>::Entry>,
2372{
2373}
2374
2375pub type UnicodeNodeBTree = UnicodeBTree<UnicodeNodeBTreeEntry, UnicodeNodeBTreePage>;
2376impl NodeBTree<UnicodePstFile, UnicodeNodeBTreeEntry> for UnicodeNodeBTree {}
2377impl NodeBTreeReadWrite<UnicodePstFile, UnicodeNodeBTreeEntry> for UnicodeNodeBTree {}
2378
2379pub type AnsiNodeBTree = AnsiBTree<AnsiNodeBTreeEntry, AnsiNodeBTreePage>;
2380impl NodeBTree<AnsiPstFile, AnsiNodeBTreeEntry> for AnsiNodeBTree {}
2381impl NodeBTreeReadWrite<AnsiPstFile, AnsiNodeBTreeEntry> for AnsiNodeBTree {}
outlook_pst/ndb/page.rs

outlook_pst/ndb/
page.rs
