kvstructs/
lib.rs

1//! General basic key-value structs for Key-Value based storages.
2//!
3#![cfg_attr(not(feature = "std"), no_std)]
4#![cfg_attr(docsrs, feature(doc_cfg))]
5#![cfg_attr(docsrs, allow(unused_attributes))]
6#![deny(missing_docs)]
7
8macro_rules! has_prefix {
9    ($trait:tt::$fn:tt) => {
10        /// Returns whether the slice self begins with prefix.
11        #[inline]
12        fn has_prefix(&self, prefix: impl $trait) -> bool {
13            let src = $trait::$fn(self);
14            let prefix = $trait::$fn(&prefix);
15            let pl = prefix.len();
16            if src.len() < pl {
17                return false;
18            }
19
20            src[0..pl].eq(prefix)
21        }
22    };
23}
24
25macro_rules! has_suffix {
26    ($trait:tt::$fn:tt) => {
27        /// Returns whether the slice self ends with suffix.
28        #[inline]
29        fn has_suffix(&self, suffix: impl $trait) -> bool {
30            let src = $trait::$fn(self);
31            let suffix = $trait::$fn(&suffix);
32            let pl = suffix.len() - 1;
33            if src.len() <= pl {
34                return false;
35            }
36
37            src[pl..].eq(suffix)
38        }
39    };
40}
41
42macro_rules! longest_prefix {
43    ($trait:tt::$fn:tt, $ty: ty) => {
44        /// Finds the longest shared prefix
45        #[inline]
46        fn longest_prefix(&self, other: impl $trait) -> &[$ty] {
47            let k1 = $trait::$fn(self);
48            let k2 = $trait::$fn(&other);
49            let max = k1.len().min(k2.len());
50
51            let mut n = max - 1;
52            for i in 0..max {
53                if k1[i].ne(&k2[i]) {
54                    n = i;
55                    break;
56                }
57            }
58            &k1[..n]
59        }
60    };
61}
62
63macro_rules! longest_suffix {
64    ($trait:tt::$fn:tt, $ty: ty) => {
65        /// Finds the longest shared suffix
66        #[inline]
67        fn longest_suffix(&self, other: impl $trait) -> &[$ty] {
68            let k1 = $trait::$fn(self);
69            let k1_len = k1.len();
70            let k2 = $trait::$fn(&other);
71            let k2_len = k2.len();
72            return if k1_len < k2_len {
73                let max = k1_len;
74                let mut n = max;
75                for i in 0..max {
76                    if k1[k1_len - i - 1].ne(&k2[k2_len - i - 1]) {
77                        n = i;
78                        break;
79                    }
80                }
81                &k1[max - n..]
82            } else {
83                let max = k2_len;
84                let mut n = max;
85                for i in 0..max {
86                    if k1[k1_len - i - 1].ne(&k2[k2_len - i - 1]) {
87                        n = i;
88                        break;
89                    }
90                }
91                &k1[k1_len - k2_len + max - n..]
92            };
93        }
94    };
95}
96
97macro_rules! longest_prefix_lossy {
98    ($trait:tt::$fn:tt, $ty: ty, $ty_literal: literal) => {
99        #[doc = concat!("Finds the longest shared prefix, return a Cow<'_, [", $ty_literal, "]>.")]
100        #[inline]
101        fn longest_prefix_lossy(&self, other: impl $trait) -> Cow<'_, [$ty]> {
102            Cow::Borrowed(self.longest_prefix(other))
103        }
104    };
105}
106
107macro_rules! longest_suffix_lossy {
108    ($trait:tt::$fn:tt, $ty: ty, $ty_literal: literal) => {
109        #[doc = concat!("Finds the longest shared suffix, return a Cow<'_, [", $ty_literal, "]>.")]
110        #[inline]
111        fn longest_suffix_lossy(&self, other: impl $trait) -> Cow<'_, [$ty]> {
112            Cow::Borrowed(self.longest_suffix(other))
113        }
114    };
115}
116
117macro_rules! impl_psfix_suites {
118    ($trait:tt::$fn:tt, $ty: ty, $ty_literal: literal) => {
119        has_prefix!($trait::$fn);
120
121        has_suffix!($trait::$fn);
122
123        longest_prefix!($trait::$fn, $ty);
124
125        longest_suffix!($trait::$fn, $ty);
126
127        longest_prefix_lossy!($trait::$fn, $ty, $ty_literal);
128
129        longest_suffix_lossy!($trait::$fn, $ty, $ty_literal);
130    };
131}
132
133macro_rules! cfg_std {
134    ($($item: item)*) => {
135        $(
136        #[cfg(feature = "std")]
137        $item
138        )*
139    };
140}
141
142extern crate alloc;
143
144mod entry;
145mod header;
146/// Iterator trait
147pub mod iterator;
148mod key;
149mod key_mut;
150mod raw_entry_pointer;
151mod raw_key_pointer;
152mod raw_value_pointer;
153mod value;
154mod value_enc;
155mod value_mut;
156
157/// Unsafe raw pointer for [`Key`], [`Value`], [`Entry`]
158///
159/// [`Key`]: struct.Key.html
160/// [`Value`]: struct.Value.html
161/// [`Entry`]: struct.Entry.html
162pub mod raw_pointer {
163    pub use crate::raw_entry_pointer::*;
164    pub use crate::raw_key_pointer::*;
165    pub use crate::raw_value_pointer::*;
166}
167/// re-export [`bytes`] crate.
168///
169/// [`bytes`]: https://docs.rs/bytes/
170pub mod bytes {
171    pub use bytes::*;
172}
173pub use entry::*;
174pub use header::*;
175pub use key::*;
176pub use key_mut::*;
177pub use value::*;
178pub use value_enc::*;
179pub use value_mut::*;
180
181use crate::bytes::{BufMut, BytesMut};
182use alloc::vec::Vec;
183use bitflags::bitflags;
184#[cfg(feature = "std")]
185use header::ByteReader;
186
187const TIMESTAMP_SIZE: usize = core::mem::size_of::<u64>();
188
189bitflags! {
190    /// Values have their first byte being byteData or byteDelete. This helps us distinguish between
191    /// a key that has never been seen and a key that has been explicitly deleted.
192    pub struct OP: u8 {
193        #[doc = "Set if the key has been deleted."]
194        const BIT_DELETE = 1 << 0;
195        #[doc = "Set if the value is NOT stored directly next to key."]
196        const BIT_VALUE_POINTER = 1 << 1;
197        #[doc = "Set if earlier versions can be discarded."]
198        const BIT_DISCARD_EARLIER_VERSIONS = 1 << 2;
199        #[doc = "Set if item shouldn't be discarded via compactions (used by merge operator)"]
200        const BIT_MERGE_ENTRY = 1 << 3;
201        #[doc = "Set if the entry is part of a txn."]
202        const BIT_TXN = 1 << 6;
203        #[doc = "Set if the entry is to indicate end of txn in value log."]
204        const BIT_FIN_TXN = 1 << 7;
205    }
206}
207
208#[inline]
209fn u64_big_endian(b: &[u8]) -> u64 {
210    (b[7] as u64)
211        | ((b[6] as u64) << 8)
212        | (b[5] as u64) << 16
213        | (b[4] as u64) << 24
214        | (b[3] as u64) << 32
215        | (b[2] as u64) << 40
216        | (b[1] as u64) << 48
217        | (b[0] as u64) << 56
218}
219
220const MAX_VARINT_LEN64: usize = 10;
221
222/// binary_uvarint decodes a uint64 from buf and returns that value and the
223/// number of bytes read (> 0). If an error occurred, the value is 0
224/// and the number of bytes n is <= 0 meaning:
225///
226/// n == 0: buf too small
227///
228/// n  < 0: value larger than 64 bits (overflow)
229/// and !n is the number of bytes read
230///
231#[inline]
232fn binary_uvarint(buf: &[u8]) -> (u64, usize) {
233    let mut x = 0;
234    let mut s = 0usize;
235    for (idx, b) in buf.iter().enumerate() {
236        let b = *b;
237        if b < 0x80 {
238            if idx >= MAX_VARINT_LEN64 || idx == MAX_VARINT_LEN64 - 1 && b > 1 {
239                return (0, !(idx + 1)); //overflow
240            }
241            return (x | (b as u64) << s, idx + 1);
242        }
243        x |= ((b & 0x7f) as u64) << s;
244        s += 7;
245    }
246    (0, 0)
247}
248
249#[inline]
250fn put_binary_uvariant_to_vec(vec: &mut Vec<u8>, mut x: u64) {
251    while x >= 0x80 {
252        vec.push((x as u8) | 0x80);
253        x >>= 7;
254    }
255    vec.push(x as u8)
256}
257
258#[inline]
259fn binary_put_uvariant_to_bufmut(buf: &mut BytesMut, mut x: u64) -> usize {
260    let mut i = 0;
261    while x >= 0x80 {
262        buf.put_u8((x as u8) | 0x80);
263        x >>= 7;
264        i += 1;
265    }
266    buf.put_u8(x as u8);
267    i + 1
268}
269
270cfg_std! {
271    /// Uvariant overflows a 64-bit integer
272    #[derive(Copy, Clone, Debug)]
273    pub struct Overflow;
274
275    impl std::fmt::Display for Overflow {
276        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
277            write!(f, "binary: variant overflows a 64-bit integer")
278        }
279    }
280
281    impl std::error::Error for Overflow {}
282
283    impl From<Overflow> for std::io::Error {
284        fn from(of: Overflow) -> Self {
285            std::io::Error::new(std::io::ErrorKind::Other, of)
286        }
287    }
288
289    /// read_uvarint reads an encoded unsigned integer from r and returns it as a u64.
290    fn binary_read_and_put_uvarint(r: &mut impl ByteReader, dst: &mut BytesMut) -> std::io::Result<u64> {
291        let mut x = 0u64;
292        let mut s = 0usize;
293        for idx in 0..MAX_VARINT_LEN64 {
294            let b = r.read_byte()?;
295            dst.put_u8(b);
296            if b < 0x80 {
297                if idx == MAX_VARINT_LEN64 - 1 && b > 1 {
298                    return Err(Overflow.into());
299                }
300                return Ok(x | (b as u64) << s);
301            }
302            x |= ((b & 0x7f) as u64) << s;
303            s += 7;
304        }
305        Ok(x)
306    }
307}
308
309#[inline]
310fn binary_put_uvariant_to_vec(buf: &mut Vec<u8>, mut x: u64) -> usize {
311    let mut i = 0;
312    while x >= 0x80 {
313        buf.push((x as u8) | 0x80);
314        x >>= 7;
315        i += 1;
316    }
317    buf.push(x as u8);
318    i + 1
319}
320
321#[inline]
322fn binary_uvarint_allocate(mut x: u64) -> Vec<u8> {
323    let mut vec = Vec::with_capacity(MAX_VARINT_LEN64);
324    while x >= 0x80 {
325        vec.push((x as u8) | 0x80);
326        x >>= 7;
327    }
328    vec.push(x as u8);
329    vec
330}
kvstructs/lib.rs

kvstructs/
lib.rs
