redb/
types.rs

Help
1use std::cmp::Ordering;
2use std::convert::TryInto;
3use std::fmt::Debug;
4use std::mem::size_of;
5
6#[derive(Eq, PartialEq, Clone, Debug)]
7enum TypeClassification {
8    Internal,
9    UserDefined,
10}
11
12impl TypeClassification {
13    fn to_byte(&self) -> u8 {
14        match self {
15            TypeClassification::Internal => 1,
16            TypeClassification::UserDefined => 2,
17        }
18    }
19
20    fn from_byte(value: u8) -> Self {
21        match value {
22            1 => TypeClassification::Internal,
23            2 => TypeClassification::UserDefined,
24            _ => unreachable!(),
25        }
26    }
27}
28
29#[derive(Eq, PartialEq, Debug, Clone)]
30pub struct TypeName {
31    classification: TypeClassification,
32    name: String,
33}
34
35impl TypeName {
36    /// It is recommended that `name` be prefixed with the crate name to minimize the chance of
37    /// it coliding with another user defined type
38    pub fn new(name: &str) -> Self {
39        Self {
40            classification: TypeClassification::UserDefined,
41            name: name.to_string(),
42        }
43    }
44
45    pub(crate) fn internal(name: &str) -> Self {
46        Self {
47            classification: TypeClassification::Internal,
48            name: name.to_string(),
49        }
50    }
51
52    pub(crate) fn to_bytes(&self) -> Vec<u8> {
53        let mut result = Vec::with_capacity(self.name.len() + 1);
54        result.push(self.classification.to_byte());
55        result.extend_from_slice(self.name.as_bytes());
56        result
57    }
58
59    pub(crate) fn from_bytes(bytes: &[u8]) -> Self {
60        let classification = TypeClassification::from_byte(bytes[0]);
61        let name = std::str::from_utf8(&bytes[1..]).unwrap().to_string();
62
63        Self {
64            classification,
65            name,
66        }
67    }
68
69    pub(crate) fn name(&self) -> &str {
70        &self.name
71    }
72}
73
74pub trait Value: Debug {
75    /// `SelfType<'a>` must be the same type as Self with all lifetimes replaced with 'a
76    type SelfType<'a>: Debug + 'a
77    where
78        Self: 'a;
79
80    type AsBytes<'a>: AsRef<[u8]> + 'a
81    where
82        Self: 'a;
83
84    /// Width of a fixed type, or None for variable width
85    fn fixed_width() -> Option<usize>;
86
87    /// Deserializes data
88    /// Implementations may return a view over data, or an owned type
89    fn from_bytes<'a>(data: &'a [u8]) -> Self::SelfType<'a>
90    where
91        Self: 'a;
92
93    /// Serialize the value to a slice
94    fn as_bytes<'a, 'b: 'a>(value: &'a Self::SelfType<'b>) -> Self::AsBytes<'a>
95    where
96        Self: 'b;
97
98    /// Globally unique identifier for this type
99    fn type_name() -> TypeName;
100}
101
102/// Implementing this trait indicates that the type can be mutated in-place as a &mut [u8].
103/// This enables the `.insert_reserve()` method on Table
104pub trait MutInPlaceValue: Value {
105    /// The base type such that &mut [u8] can be safely transmuted to `&mut BaseRefType`
106    type BaseRefType: Debug + ?Sized;
107
108    // Initialize `data` to a valid value. This method will be called (at some point, not necessarily immediately)
109    // before from_bytes_mut() is called on a slice.
110    fn initialize(data: &mut [u8]);
111
112    fn from_bytes_mut(data: &mut [u8]) -> &mut Self::BaseRefType;
113}
114
115impl MutInPlaceValue for &[u8] {
116    type BaseRefType = [u8];
117
118    fn initialize(_data: &mut [u8]) {
119        // no-op. All values are valid.
120    }
121
122    fn from_bytes_mut(data: &mut [u8]) -> &mut Self::BaseRefType {
123        data
124    }
125}
126
127pub trait Key: Value {
128    /// Compare data1 with data2
129    fn compare(data1: &[u8], data2: &[u8]) -> Ordering;
130}
131
132impl Value for () {
133    type SelfType<'a>
134        = ()
135    where
136        Self: 'a;
137    type AsBytes<'a>
138        = &'a [u8]
139    where
140        Self: 'a;
141
142    fn fixed_width() -> Option<usize> {
143        Some(0)
144    }
145
146    #[allow(clippy::unused_unit, clippy::semicolon_if_nothing_returned)]
147    fn from_bytes<'a>(_data: &'a [u8]) -> ()
148    where
149        Self: 'a,
150    {
151        ()
152    }
153
154    #[allow(clippy::ignored_unit_patterns)]
155    fn as_bytes<'a, 'b: 'a>(_: &'a Self::SelfType<'b>) -> &'a [u8]
156    where
157        Self: 'b,
158    {
159        &[]
160    }
161
162    fn type_name() -> TypeName {
163        TypeName::internal("()")
164    }
165}
166
167impl Key for () {
168    fn compare(_data1: &[u8], _data2: &[u8]) -> Ordering {
169        Ordering::Equal
170    }
171}
172
173impl Value for bool {
174    type SelfType<'a>
175        = bool
176    where
177        Self: 'a;
178    type AsBytes<'a>
179        = &'a [u8]
180    where
181        Self: 'a;
182
183    fn fixed_width() -> Option<usize> {
184        Some(1)
185    }
186
187    fn from_bytes<'a>(data: &'a [u8]) -> bool
188    where
189        Self: 'a,
190    {
191        match data[0] {
192            0 => false,
193            1 => true,
194            _ => unreachable!(),
195        }
196    }
197
198    fn as_bytes<'a, 'b: 'a>(value: &'a Self::SelfType<'b>) -> &'a [u8]
199    where
200        Self: 'b,
201    {
202        match value {
203            true => &[1],
204            false => &[0],
205        }
206    }
207
208    fn type_name() -> TypeName {
209        TypeName::internal("bool")
210    }
211}
212
213impl Key for bool {
214    fn compare(data1: &[u8], data2: &[u8]) -> Ordering {
215        let value1 = Self::from_bytes(data1);
216        let value2 = Self::from_bytes(data2);
217        value1.cmp(&value2)
218    }
219}
220
221impl<T: Value> Value for Option<T> {
222    type SelfType<'a>
223        = Option<T::SelfType<'a>>
224    where
225        Self: 'a;
226    type AsBytes<'a>
227        = Vec<u8>
228    where
229        Self: 'a;
230
231    fn fixed_width() -> Option<usize> {
232        T::fixed_width().map(|x| x + 1)
233    }
234
235    fn from_bytes<'a>(data: &'a [u8]) -> Option<T::SelfType<'a>>
236    where
237        Self: 'a,
238    {
239        match data[0] {
240            0 => None,
241            1 => Some(T::from_bytes(&data[1..])),
242            _ => unreachable!(),
243        }
244    }
245
246    fn as_bytes<'a, 'b: 'a>(value: &'a Self::SelfType<'b>) -> Vec<u8>
247    where
248        Self: 'b,
249    {
250        let mut result = vec![0];
251        if let Some(x) = value {
252            result[0] = 1;
253            result.extend_from_slice(T::as_bytes(x).as_ref());
254        } else if let Some(fixed_width) = T::fixed_width() {
255            result.extend_from_slice(&vec![0; fixed_width]);
256        }
257        result
258    }
259
260    fn type_name() -> TypeName {
261        TypeName::internal(&format!("Option<{}>", T::type_name().name()))
262    }
263}
264
265impl<T: Key> Key for Option<T> {
266    #[allow(clippy::collapsible_else_if)]
267    fn compare(data1: &[u8], data2: &[u8]) -> Ordering {
268        if data1[0] == 0 {
269            if data2[0] == 0 {
270                Ordering::Equal
271            } else {
272                Ordering::Less
273            }
274        } else {
275            if data2[0] == 0 {
276                Ordering::Greater
277            } else {
278                T::compare(&data1[1..], &data2[1..])
279            }
280        }
281    }
282}
283
284impl Value for &[u8] {
285    type SelfType<'a>
286        = &'a [u8]
287    where
288        Self: 'a;
289    type AsBytes<'a>
290        = &'a [u8]
291    where
292        Self: 'a;
293
294    fn fixed_width() -> Option<usize> {
295        None
296    }
297
298    fn from_bytes<'a>(data: &'a [u8]) -> &'a [u8]
299    where
300        Self: 'a,
301    {
302        data
303    }
304
305    fn as_bytes<'a, 'b: 'a>(value: &'a Self::SelfType<'b>) -> &'a [u8]
306    where
307        Self: 'b,
308    {
309        value
310    }
311
312    fn type_name() -> TypeName {
313        TypeName::internal("&[u8]")
314    }
315}
316
317impl Key for &[u8] {
318    fn compare(data1: &[u8], data2: &[u8]) -> Ordering {
319        data1.cmp(data2)
320    }
321}
322
323impl<const N: usize> Value for &[u8; N] {
324    type SelfType<'a>
325        = &'a [u8; N]
326    where
327        Self: 'a;
328    type AsBytes<'a>
329        = &'a [u8; N]
330    where
331        Self: 'a;
332
333    fn fixed_width() -> Option<usize> {
334        Some(N)
335    }
336
337    fn from_bytes<'a>(data: &'a [u8]) -> &'a [u8; N]
338    where
339        Self: 'a,
340    {
341        data.try_into().unwrap()
342    }
343
344    fn as_bytes<'a, 'b: 'a>(value: &'a Self::SelfType<'b>) -> &'a [u8; N]
345    where
346        Self: 'b,
347    {
348        value
349    }
350
351    fn type_name() -> TypeName {
352        TypeName::internal(&format!("[u8;{N}]"))
353    }
354}
355
356impl<const N: usize> Key for &[u8; N] {
357    fn compare(data1: &[u8], data2: &[u8]) -> Ordering {
358        data1.cmp(data2)
359    }
360}
361
362impl<const N: usize, T: Value> Value for [T; N] {
363    type SelfType<'a>
364        = [T::SelfType<'a>; N]
365    where
366        Self: 'a;
367    type AsBytes<'a>
368        = Vec<u8>
369    where
370        Self: 'a;
371
372    fn fixed_width() -> Option<usize> {
373        T::fixed_width().map(|x| x * N)
374    }
375
376    fn from_bytes<'a>(data: &'a [u8]) -> [T::SelfType<'a>; N]
377    where
378        Self: 'a,
379    {
380        let mut result = Vec::with_capacity(N);
381        if let Some(fixed) = T::fixed_width() {
382            for i in 0..N {
383                result.push(T::from_bytes(&data[fixed * i..fixed * (i + 1)]));
384            }
385        } else {
386            // Set offset to the first data item
387            let mut start = size_of::<u32>() * N;
388            for i in 0..N {
389                let range = size_of::<u32>() * i..size_of::<u32>() * (i + 1);
390                let end = u32::from_le_bytes(data[range].try_into().unwrap()) as usize;
391                result.push(T::from_bytes(&data[start..end]));
392                start = end;
393            }
394        }
395        result.try_into().unwrap()
396    }
397
398    fn as_bytes<'a, 'b: 'a>(value: &'a Self::SelfType<'b>) -> Vec<u8>
399    where
400        Self: 'b,
401    {
402        if let Some(fixed) = T::fixed_width() {
403            let mut result = Vec::with_capacity(fixed * N);
404            for item in value {
405                result.extend_from_slice(T::as_bytes(item).as_ref());
406            }
407            result
408        } else {
409            // Reserve space for the end offsets
410            let mut result = vec![0u8; size_of::<u32>() * N];
411            for i in 0..N {
412                result.extend_from_slice(T::as_bytes(&value[i]).as_ref());
413                let end: u32 = result.len().try_into().unwrap();
414                result[size_of::<u32>() * i..size_of::<u32>() * (i + 1)]
415                    .copy_from_slice(&end.to_le_bytes());
416            }
417            result
418        }
419    }
420
421    fn type_name() -> TypeName {
422        // Uses the same type name as [T;N] so that tables are compatible with [u8;N] and &[u8;N] types
423        // This requires that the binary encoding be the same
424        TypeName::internal(&format!("[{};{N}]", T::type_name().name()))
425    }
426}
427
428impl<const N: usize, T: Key> Key for [T; N] {
429    fn compare(data1: &[u8], data2: &[u8]) -> Ordering {
430        if let Some(fixed) = T::fixed_width() {
431            for i in 0..N {
432                let range = fixed * i..fixed * (i + 1);
433                let comparison = T::compare(&data1[range.clone()], &data2[range]);
434                if !comparison.is_eq() {
435                    return comparison;
436                }
437            }
438        } else {
439            // Set offset to the first data item
440            let mut start1 = size_of::<u32>() * N;
441            let mut start2 = size_of::<u32>() * N;
442            for i in 0..N {
443                let range = size_of::<u32>() * i..size_of::<u32>() * (i + 1);
444                let end1 = u32::from_le_bytes(data1[range.clone()].try_into().unwrap()) as usize;
445                let end2 = u32::from_le_bytes(data2[range].try_into().unwrap()) as usize;
446                let comparison = T::compare(&data1[start1..end1], &data2[start2..end2]);
447                if !comparison.is_eq() {
448                    return comparison;
449                }
450                start1 = end1;
451                start2 = end2;
452            }
453        }
454        Ordering::Equal
455    }
456}
457
458impl Value for &str {
459    type SelfType<'a>
460        = &'a str
461    where
462        Self: 'a;
463    type AsBytes<'a>
464        = &'a str
465    where
466        Self: 'a;
467
468    fn fixed_width() -> Option<usize> {
469        None
470    }
471
472    fn from_bytes<'a>(data: &'a [u8]) -> &'a str
473    where
474        Self: 'a,
475    {
476        std::str::from_utf8(data).unwrap()
477    }
478
479    fn as_bytes<'a, 'b: 'a>(value: &'a Self::SelfType<'b>) -> &'a str
480    where
481        Self: 'b,
482    {
483        value
484    }
485
486    fn type_name() -> TypeName {
487        TypeName::internal("&str")
488    }
489}
490
491impl Key for &str {
492    fn compare(data1: &[u8], data2: &[u8]) -> Ordering {
493        let str1 = Self::from_bytes(data1);
494        let str2 = Self::from_bytes(data2);
495        str1.cmp(str2)
496    }
497}
498
499impl Value for String {
500    type SelfType<'a>
501        = String
502    where
503        Self: 'a;
504    type AsBytes<'a>
505        = &'a str
506    where
507        Self: 'a;
508
509    fn fixed_width() -> Option<usize> {
510        None
511    }
512
513    fn from_bytes<'a>(data: &'a [u8]) -> String
514    where
515        Self: 'a,
516    {
517        std::str::from_utf8(data).unwrap().to_string()
518    }
519
520    fn as_bytes<'a, 'b: 'a>(value: &'a Self::SelfType<'b>) -> &'a str
521    where
522        Self: 'b,
523    {
524        value.as_str()
525    }
526
527    fn type_name() -> TypeName {
528        TypeName::internal("String")
529    }
530}
531
532impl Key for String {
533    fn compare(data1: &[u8], data2: &[u8]) -> Ordering {
534        let str1 = std::str::from_utf8(data1).unwrap();
535        let str2 = std::str::from_utf8(data2).unwrap();
536        str1.cmp(str2)
537    }
538}
539
540impl Value for char {
541    type SelfType<'a> = char;
542    type AsBytes<'a>
543        = [u8; 3]
544    where
545        Self: 'a;
546
547    fn fixed_width() -> Option<usize> {
548        Some(3)
549    }
550
551    fn from_bytes<'a>(data: &'a [u8]) -> char
552    where
553        Self: 'a,
554    {
555        char::from_u32(u32::from_le_bytes([data[0], data[1], data[2], 0])).unwrap()
556    }
557
558    fn as_bytes<'a, 'b: 'a>(value: &'a Self::SelfType<'b>) -> [u8; 3]
559    where
560        Self: 'b,
561    {
562        let bytes = u32::from(*value).to_le_bytes();
563        [bytes[0], bytes[1], bytes[2]]
564    }
565
566    fn type_name() -> TypeName {
567        TypeName::internal(stringify!(char))
568    }
569}
570
571impl Key for char {
572    fn compare(data1: &[u8], data2: &[u8]) -> Ordering {
573        Self::from_bytes(data1).cmp(&Self::from_bytes(data2))
574    }
575}
576
577macro_rules! le_value {
578    ($t:ty) => {
579        impl Value for $t {
580            type SelfType<'a> = $t;
581            type AsBytes<'a>
582                = [u8; std::mem::size_of::<$t>()]
583            where
584                Self: 'a;
585
586            fn fixed_width() -> Option<usize> {
587                Some(std::mem::size_of::<$t>())
588            }
589
590            fn from_bytes<'a>(data: &'a [u8]) -> $t
591            where
592                Self: 'a,
593            {
594                <$t>::from_le_bytes(data.try_into().unwrap())
595            }
596
597            fn as_bytes<'a, 'b: 'a>(
598                value: &'a Self::SelfType<'b>,
599            ) -> [u8; std::mem::size_of::<$t>()]
600            where
601                Self: 'a,
602                Self: 'b,
603            {
604                value.to_le_bytes()
605            }
606
607            fn type_name() -> TypeName {
608                TypeName::internal(stringify!($t))
609            }
610        }
611    };
612}
613
614macro_rules! le_impl {
615    ($t:ty) => {
616        le_value!($t);
617
618        impl Key for $t {
619            fn compare(data1: &[u8], data2: &[u8]) -> Ordering {
620                Self::from_bytes(data1).cmp(&Self::from_bytes(data2))
621            }
622        }
623    };
624}
625
626le_impl!(u8);
627le_impl!(u16);
628le_impl!(u32);
629le_impl!(u64);
630le_impl!(u128);
631le_impl!(i8);
632le_impl!(i16);
633le_impl!(i32);
634le_impl!(i64);
635le_impl!(i128);
636le_value!(f32);
637le_value!(f64);
redb/types.rs

redb/
types.rs
