concept_store/
keys.rs

1// SPDX-FileCopyrightText: Cadasto B.V.
2// SPDX-License-Identifier: BUSL-1.1
3
4//! A sorted `u64` key to `u32` ordinal table beside an artifact.
5//!
6//! A code system whose concepts have identifiers beyond their codes (the atom
7//! identifiers of `RxNorm`, the entity identifiers of ICD-11) keeps them here,
8//! each next to its concept ordinal. No spec governs the layout: our own
9//! design, little-endian, a magic and version, a count, then sorted
10//! `(key, ordinal)` pairs.
11
12use std::io::{self, Read, Write};
13
14const MAGIC: &[u8; 8] = b"FTKEYS\0\0";
15const VERSION: u32 = 1;
16
17/// A count past the integer the key table layout stores.
18#[derive(Debug, thiserror::Error)]
19#[error("{what} exceeds the integer the key table layout stores")]
20struct Overflow {
21    what: &'static str,
22    #[source]
23    source: std::num::TryFromIntError,
24}
25
26/// A failure while reading or writing the table.
27#[derive(Debug, thiserror::Error)]
28pub enum KeyTableError {
29    /// An I/O failure.
30    #[error("key table I/O failed")]
31    Io(#[from] io::Error),
32    /// The bytes do not start with the table magic.
33    #[error("not a key table")]
34    Magic,
35    /// The layout version is not the one this build reads.
36    #[error("key table version {found}, expected {expected}")]
37    Version {
38        /// The version found.
39        found: u32,
40        /// The version this build reads.
41        expected: u32,
42    },
43}
44
45/// The sorted table.
46#[derive(Debug, Clone, PartialEq, Eq, Default)]
47pub struct KeyTable {
48    pairs: Vec<(u64, u32)>,
49}
50
51impl KeyTable {
52    /// Builds the table from `(key, ordinal)` pairs, in any order.
53    #[must_use]
54    pub fn new(mut pairs: Vec<(u64, u32)>) -> Self {
55        pairs.sort_unstable();
56        pairs.dedup();
57        Self { pairs }
58    }
59
60    /// The ordinal stored under `key`.
61    #[must_use]
62    pub fn get(&self, key: u64) -> Option<u32> {
63        self.pairs
64            .binary_search_by_key(&key, |(k, _)| *k)
65            .ok()
66            .and_then(|i| self.pairs.get(i))
67            .map(|(_, o)| *o)
68    }
69
70    /// The entry count.
71    #[must_use]
72    pub fn len(&self) -> usize {
73        self.pairs.len()
74    }
75
76    /// Whether the table is empty.
77    #[must_use]
78    pub fn is_empty(&self) -> bool {
79        self.pairs.is_empty()
80    }
81
82    /// Writes the layout.
83    ///
84    /// # Errors
85    ///
86    /// Returns [`KeyTableError::Io`] when writing fails.
87    pub fn write_to(&self, out: &mut impl Write) -> Result<(), KeyTableError> {
88        out.write_all(MAGIC)?;
89        out.write_all(&VERSION.to_le_bytes())?;
90        let len = u64::try_from(self.pairs.len()).map_err(|source| {
91            io::Error::other(Overflow {
92                what: "the key count",
93                source,
94            })
95        })?;
96        out.write_all(&len.to_le_bytes())?;
97        for (key, ordinal) in &self.pairs {
98            out.write_all(&key.to_le_bytes())?;
99            out.write_all(&ordinal.to_le_bytes())?;
100        }
101        Ok(())
102    }
103
104    /// Reads the layout.
105    ///
106    /// # Errors
107    ///
108    /// Returns [`KeyTableError`] for a truncated or foreign table.
109    pub fn read_from(input: &mut impl Read) -> Result<Self, KeyTableError> {
110        let mut magic = [0_u8; 8];
111        input.read_exact(&mut magic)?;
112        if &magic != MAGIC {
113            return Err(KeyTableError::Magic);
114        }
115        let mut word = [0_u8; 4];
116        input.read_exact(&mut word)?;
117        let version = u32::from_le_bytes(word);
118        if version != VERSION {
119            return Err(KeyTableError::Version {
120                found: version,
121                expected: VERSION,
122            });
123        }
124        let mut long = [0_u8; 8];
125        input.read_exact(&mut long)?;
126        let len = usize::try_from(u64::from_le_bytes(long)).map_err(|source| {
127            io::Error::other(Overflow {
128                what: "the key count",
129                source,
130            })
131        })?;
132        let mut pairs = Vec::with_capacity(len);
133        for _ in 0..len {
134            input.read_exact(&mut long)?;
135            input.read_exact(&mut word)?;
136            pairs.push((u64::from_le_bytes(long), u32::from_le_bytes(word)));
137        }
138        Ok(Self { pairs })
139    }
140}
141
142#[cfg(test)]
143mod tests {
144    use super::{KeyTable, KeyTableError};
145
146    #[test]
147    fn the_table_answers_by_key_and_round_trips() {
148        let keys = KeyTable::new(vec![(829, 0), (12_251_526, 1), (2_798_745, 1), (829, 0)]);
149        assert_eq!(keys.len(), 3);
150        assert_eq!(keys.get(2_798_745), Some(1));
151        assert_eq!(keys.get(1), None);
152        let mut bytes = Vec::new();
153        keys.write_to(&mut bytes).expect("writes");
154        assert_eq!(
155            KeyTable::read_from(&mut bytes.as_slice()).expect("reads"),
156            keys
157        );
158        assert!(matches!(
159            KeyTable::read_from(&mut b"XXXXXXXX\0\0\0\0".as_slice()),
160            Err(KeyTableError::Magic)
161        ));
162    }
163}
concept_store/keys.rs

concept_store/
keys.rs
