[Rust] BinaryTreeMaps in flatbuffers

[aksatish19]

The language in question is Rust and I'm new to rust and FlatBuffers. Is there a way to represent a HashMap<uint64, Vec>? I can do this by using a vector tables where each table contains a uint64 and a Vec. If there is way to use dictionary, can you please provide an example. Any help would be appreciated.

[aardappel]

Generally FlatBuffers can represent dictionaries as vectors with binary search:

table KeyValue { k:ulong (key); v:[..]; }
// somewhere else:
dict:[KeyValue];   // these would be stored sorted according to k.

This appears supported in Rust (from the generated key_compare_less_than functions), but haven't tried it.. @rw will know more.

[rw]

key_compare_less_than is a building block, but we don't support binary search yet. A PR would be welcome!

[aksatish19]

Thanks for the clarification guys.

[aardappel]

https://stackoverflow.com/questions/66655825/how-to-use-flatbuffers-key-attribute-to-simulate-hashmap-with-flatbuffers-in-r @CasperN

[4ntoine]

Any chance to have it implemented?

[CasperN]

I don't have time to do it myself but I'll happily review PRs if anyone is willing to contribute. The following is the rough design / needed code-changes I have off the top of my head.

Reader changes

trait TableWithKey {
  type Key: Ord;
  fn key(&) -> Key;
}
impl TableWithKey for Foo { ... }

impl <'a, T: Follow<'a> + TableWithKey> Vector<'a, T> {
  fn is_sorted(&self) -> bool;
  // bikeshedding names: get_by_key, lookup, etc. (lookup_by_key is what C++ uses)
  fn lookup_by_key(&self, key: <T as TableWithKey>::Key) -> T::Inner;
}

Adding a trait-conditional methods on Vector instead of making a new Map type makes keeps old code forwards-compatible. Also, I think flatbuffers maps aren't necessarily sorted -- noting the C++ API has separate CreateVector and CreateVectorOfSortedTables

Builder changes

fn sort_tables<T: TableWithKey>(&mut self, tables: &mut [WipOffset<T>]) {
  todo!()  // I think we panic on duplicated keys?
}
fn sort_and_create_vector<T: TableWithKey>(&mut self, tables: &mut [WipOffset<T>]) -> WIPOffset<Vector<T>> {
  self.sort_tables(tables);
  self.create_vector(tables)
}

Of course, code-gen changes need to happen too

• TableWithKey needs to be implemented for tables with keys.
• the create method perhaps should create sorted vectors? do whatever C++ does

[github-actions[bot]]

This issue is stale because it has been open 6 months with no activity. Please comment or this will be closed in 14 days.

[ChristopherRabotin]

@CasperN Sorry to bother, but I was wondering whether you'd have more time now to implement this? I'm new to flatbuffers (but not to Rust), so I'm not sure I can be of much help. However, it seems like you've had an idea of a design in mind for some time now.

I can confirm that running flatc version 2.0.0, the generated KeyValue does not support in-place binary search.

Below is an example of a Flatbuffers schema and its generated (and formatted) Rust file.

demo.fbs

namespace KVDemo;

struct Quaternion {
    x: float;
    y: float;
    z: float;
    w: double;
}

table KeyValue { k:ulong (key); v:[Quaternion]; }

root_type KeyValue;

demo_generated.rs

// automatically generated by the FlatBuffers compiler, do not modify

use std::cmp::Ordering;
use std::mem;

extern crate flatbuffers;
use self::flatbuffers::{EndianScalar, Follow};

#[allow(unused_imports, dead_code)]
pub mod kvdemo {

    use std::cmp::Ordering;
    use std::mem;

    extern crate flatbuffers;
    use self::flatbuffers::{EndianScalar, Follow};

    // struct Quaternion, aligned to 8
    #[repr(transparent)]
    #[derive(Clone, Copy, PartialEq)]
    pub struct Quaternion(pub [u8; 24]);
    impl Default for Quaternion {
        fn default() -> Self {
            Self([0; 24])
        }
    }
    impl std::fmt::Debug for Quaternion {
        fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
            f.debug_struct("Quaternion")
                .field("x", &self.x())
                .field("y", &self.y())
                .field("z", &self.z())
                .field("w", &self.w())
                .finish()
        }
    }

    impl flatbuffers::SimpleToVerifyInSlice for Quaternion {}
    impl flatbuffers::SafeSliceAccess for Quaternion {}
    impl<'a> flatbuffers::Follow<'a> for Quaternion {
        type Inner = &'a Quaternion;
        #[inline]
        fn follow(buf: &'a [u8], loc: usize) -> Self::Inner {
            <&'a Quaternion>::follow(buf, loc)
        }
    }
    impl<'a> flatbuffers::Follow<'a> for &'a Quaternion {
        type Inner = &'a Quaternion;
        #[inline]
        fn follow(buf: &'a [u8], loc: usize) -> Self::Inner {
            flatbuffers::follow_cast_ref::<Quaternion>(buf, loc)
        }
    }
    impl<'b> flatbuffers::Push for Quaternion {
        type Output = Quaternion;
        #[inline]
        fn push(&self, dst: &mut [u8], _rest: &[u8]) {
            let src = unsafe {
                ::std::slice::from_raw_parts(self as *const Quaternion as *const u8, Self::size())
            };
            dst.copy_from_slice(src);
        }
    }
    impl<'b> flatbuffers::Push for &'b Quaternion {
        type Output = Quaternion;

        #[inline]
        fn push(&self, dst: &mut [u8], _rest: &[u8]) {
            let src = unsafe {
                ::std::slice::from_raw_parts(*self as *const Quaternion as *const u8, Self::size())
            };
            dst.copy_from_slice(src);
        }
    }

    impl<'a> flatbuffers::Verifiable for Quaternion {
        #[inline]
        fn run_verifier(
            v: &mut flatbuffers::Verifier,
            pos: usize,
        ) -> Result<(), flatbuffers::InvalidFlatbuffer> {
            use self::flatbuffers::Verifiable;
            v.in_buffer::<Self>(pos)
        }
    }
    impl<'a> Quaternion {
        #[allow(clippy::too_many_arguments)]
        pub fn new(x: f32, y: f32, z: f32, w: f64) -> Self {
            let mut s = Self([0; 24]);
            s.set_x(x);
            s.set_y(y);
            s.set_z(z);
            s.set_w(w);
            s
        }

        pub fn x(&self) -> f32 {
            let mut mem = core::mem::MaybeUninit::<f32>::uninit();
            unsafe {
                core::ptr::copy_nonoverlapping(
                    self.0[0..].as_ptr(),
                    mem.as_mut_ptr() as *mut u8,
                    core::mem::size_of::<f32>(),
                );
                mem.assume_init()
            }
            .from_little_endian()
        }

        pub fn set_x(&mut self, x: f32) {
            let x_le = x.to_little_endian();
            unsafe {
                core::ptr::copy_nonoverlapping(
                    &x_le as *const f32 as *const u8,
                    self.0[0..].as_mut_ptr(),
                    core::mem::size_of::<f32>(),
                );
            }
        }

        pub fn y(&self) -> f32 {
            let mut mem = core::mem::MaybeUninit::<f32>::uninit();
            unsafe {
                core::ptr::copy_nonoverlapping(
                    self.0[4..].as_ptr(),
                    mem.as_mut_ptr() as *mut u8,
                    core::mem::size_of::<f32>(),
                );
                mem.assume_init()
            }
            .from_little_endian()
        }

        pub fn set_y(&mut self, x: f32) {
            let x_le = x.to_little_endian();
            unsafe {
                core::ptr::copy_nonoverlapping(
                    &x_le as *const f32 as *const u8,
                    self.0[4..].as_mut_ptr(),
                    core::mem::size_of::<f32>(),
                );
            }
        }

        pub fn z(&self) -> f32 {
            let mut mem = core::mem::MaybeUninit::<f32>::uninit();
            unsafe {
                core::ptr::copy_nonoverlapping(
                    self.0[8..].as_ptr(),
                    mem.as_mut_ptr() as *mut u8,
                    core::mem::size_of::<f32>(),
                );
                mem.assume_init()
            }
            .from_little_endian()
        }

        pub fn set_z(&mut self, x: f32) {
            let x_le = x.to_little_endian();
            unsafe {
                core::ptr::copy_nonoverlapping(
                    &x_le as *const f32 as *const u8,
                    self.0[8..].as_mut_ptr(),
                    core::mem::size_of::<f32>(),
                );
            }
        }

        pub fn w(&self) -> f64 {
            let mut mem = core::mem::MaybeUninit::<f64>::uninit();
            unsafe {
                core::ptr::copy_nonoverlapping(
                    self.0[16..].as_ptr(),
                    mem.as_mut_ptr() as *mut u8,
                    core::mem::size_of::<f64>(),
                );
                mem.assume_init()
            }
            .from_little_endian()
        }

        pub fn set_w(&mut self, x: f64) {
            let x_le = x.to_little_endian();
            unsafe {
                core::ptr::copy_nonoverlapping(
                    &x_le as *const f64 as *const u8,
                    self.0[16..].as_mut_ptr(),
                    core::mem::size_of::<f64>(),
                );
            }
        }
    }

    pub enum KeyValueOffset {}
    #[derive(Copy, Clone, PartialEq)]

    pub struct KeyValue<'a> {
        pub _tab: flatbuffers::Table<'a>,
    }

    impl<'a> flatbuffers::Follow<'a> for KeyValue<'a> {
        type Inner = KeyValue<'a>;
        #[inline]
        fn follow(buf: &'a [u8], loc: usize) -> Self::Inner {
            Self {
                _tab: flatbuffers::Table { buf, loc },
            }
        }
    }

    impl<'a> KeyValue<'a> {
        #[inline]
        pub fn init_from_table(table: flatbuffers::Table<'a>) -> Self {
            KeyValue { _tab: table }
        }
        #[allow(unused_mut)]
        pub fn create<'bldr: 'args, 'args: 'mut_bldr, 'mut_bldr>(
            _fbb: &'mut_bldr mut flatbuffers::FlatBufferBuilder<'bldr>,
            args: &'args KeyValueArgs<'args>,
        ) -> flatbuffers::WIPOffset<KeyValue<'bldr>> {
            let mut builder = KeyValueBuilder::new(_fbb);
            builder.add_k(args.k);
            if let Some(x) = args.v {
                builder.add_v(x);
            }
            builder.finish()
        }

        pub const VT_K: flatbuffers::VOffsetT = 4;
        pub const VT_V: flatbuffers::VOffsetT = 6;

        #[inline]
        pub fn k(&self) -> u64 {
            self._tab.get::<u64>(KeyValue::VT_K, Some(0)).unwrap()
        }
        #[inline]
        pub fn key_compare_less_than(&self, o: &KeyValue) -> bool {
            self.k() < o.k()
        }

        #[inline]
        pub fn key_compare_with_value(&self, val: u64) -> ::std::cmp::Ordering {
            let key = self.k();
            key.cmp(&val)
        }
        #[inline]
        pub fn v(&self) -> Option<&'a [Quaternion]> {
            self._tab
                .get::<flatbuffers::ForwardsUOffset<flatbuffers::Vector<'a, Quaternion>>>(
                    KeyValue::VT_V,
                    None,
                )
                .map(|v| v.safe_slice())
        }
    }

    impl flatbuffers::Verifiable for KeyValue<'_> {
        #[inline]
        fn run_verifier(
            v: &mut flatbuffers::Verifier,
            pos: usize,
        ) -> Result<(), flatbuffers::InvalidFlatbuffer> {
            use self::flatbuffers::Verifiable;
            v.visit_table(pos)?
                .visit_field::<u64>(&"k", Self::VT_K, false)?
                .visit_field::<flatbuffers::ForwardsUOffset<flatbuffers::Vector<'_, Quaternion>>>(
                    &"v",
                    Self::VT_V,
                    false,
                )?
                .finish();
            Ok(())
        }
    }
    pub struct KeyValueArgs<'a> {
        pub k: u64,
        pub v: Option<flatbuffers::WIPOffset<flatbuffers::Vector<'a, Quaternion>>>,
    }
    impl<'a> Default for KeyValueArgs<'a> {
        #[inline]
        fn default() -> Self {
            KeyValueArgs { k: 0, v: None }
        }
    }
    pub struct KeyValueBuilder<'a: 'b, 'b> {
        fbb_: &'b mut flatbuffers::FlatBufferBuilder<'a>,
        start_: flatbuffers::WIPOffset<flatbuffers::TableUnfinishedWIPOffset>,
    }
    impl<'a: 'b, 'b> KeyValueBuilder<'a, 'b> {
        #[inline]
        pub fn add_k(&mut self, k: u64) {
            self.fbb_.push_slot::<u64>(KeyValue::VT_K, k, 0);
        }
        #[inline]
        pub fn add_v(&mut self, v: flatbuffers::WIPOffset<flatbuffers::Vector<'b, Quaternion>>) {
            self.fbb_
                .push_slot_always::<flatbuffers::WIPOffset<_>>(KeyValue::VT_V, v);
        }
        #[inline]
        pub fn new(_fbb: &'b mut flatbuffers::FlatBufferBuilder<'a>) -> KeyValueBuilder<'a, 'b> {
            let start = _fbb.start_table();
            KeyValueBuilder {
                fbb_: _fbb,
                start_: start,
            }
        }
        #[inline]
        pub fn finish(self) -> flatbuffers::WIPOffset<KeyValue<'a>> {
            let o = self.fbb_.end_table(self.start_);
            flatbuffers::WIPOffset::new(o.value())
        }
    }

    impl std::fmt::Debug for KeyValue<'_> {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            let mut ds = f.debug_struct("KeyValue");
            ds.field("k", &self.k());
            ds.field("v", &self.v());
            ds.finish()
        }
    }
    #[inline]
    #[deprecated(since = "2.0.0", note = "Deprecated in favor of `root_as...` methods.")]
    pub fn get_root_as_key_value<'a>(buf: &'a [u8]) -> KeyValue<'a> {
        unsafe { flatbuffers::root_unchecked::<KeyValue<'a>>(buf) }
    }

    #[inline]
    #[deprecated(since = "2.0.0", note = "Deprecated in favor of `root_as...` methods.")]
    pub fn get_size_prefixed_root_as_key_value<'a>(buf: &'a [u8]) -> KeyValue<'a> {
        unsafe { flatbuffers::size_prefixed_root_unchecked::<KeyValue<'a>>(buf) }
    }

    #[inline]
    /// Verifies that a buffer of bytes contains a `KeyValue`
    /// and returns it.
    /// Note that verification is still experimental and may not
    /// catch every error, or be maximally performant. For the
    /// previous, unchecked, behavior use
    /// `root_as_key_value_unchecked`.
    pub fn root_as_key_value(buf: &[u8]) -> Result<KeyValue, flatbuffers::InvalidFlatbuffer> {
        flatbuffers::root::<KeyValue>(buf)
    }
    #[inline]
    /// Verifies that a buffer of bytes contains a size prefixed
    /// `KeyValue` and returns it.
    /// Note that verification is still experimental and may not
    /// catch every error, or be maximally performant. For the
    /// previous, unchecked, behavior use
    /// `size_prefixed_root_as_key_value_unchecked`.
    pub fn size_prefixed_root_as_key_value(
        buf: &[u8],
    ) -> Result<KeyValue, flatbuffers::InvalidFlatbuffer> {
        flatbuffers::size_prefixed_root::<KeyValue>(buf)
    }
    #[inline]
    /// Verifies, with the given options, that a buffer of bytes
    /// contains a `KeyValue` and returns it.
    /// Note that verification is still experimental and may not
    /// catch every error, or be maximally performant. For the
    /// previous, unchecked, behavior use
    /// `root_as_key_value_unchecked`.
    pub fn root_as_key_value_with_opts<'b, 'o>(
        opts: &'o flatbuffers::VerifierOptions,
        buf: &'b [u8],
    ) -> Result<KeyValue<'b>, flatbuffers::InvalidFlatbuffer> {
        flatbuffers::root_with_opts::<KeyValue<'b>>(opts, buf)
    }
    #[inline]
    /// Verifies, with the given verifier options, that a buffer of
    /// bytes contains a size prefixed `KeyValue` and returns
    /// it. Note that verification is still experimental and may not
    /// catch every error, or be maximally performant. For the
    /// previous, unchecked, behavior use
    /// `root_as_key_value_unchecked`.
    pub fn size_prefixed_root_as_key_value_with_opts<'b, 'o>(
        opts: &'o flatbuffers::VerifierOptions,
        buf: &'b [u8],
    ) -> Result<KeyValue<'b>, flatbuffers::InvalidFlatbuffer> {
        flatbuffers::size_prefixed_root_with_opts::<KeyValue<'b>>(opts, buf)
    }
    #[inline]
    /// Assumes, without verification, that a buffer of bytes contains a KeyValue and returns it.
    /// # Safety
    /// Callers must trust the given bytes do indeed contain a valid `KeyValue`.
    pub unsafe fn root_as_key_value_unchecked(buf: &[u8]) -> KeyValue {
        flatbuffers::root_unchecked::<KeyValue>(buf)
    }
    #[inline]
    /// Assumes, without verification, that a buffer of bytes contains a size prefixed KeyValue and returns it.
    /// # Safety
    /// Callers must trust the given bytes do indeed contain a valid size prefixed `KeyValue`.
    pub unsafe fn size_prefixed_root_as_key_value_unchecked(buf: &[u8]) -> KeyValue {
        flatbuffers::size_prefixed_root_unchecked::<KeyValue>(buf)
    }
    #[inline]
    pub fn finish_key_value_buffer<'a, 'b>(
        fbb: &'b mut flatbuffers::FlatBufferBuilder<'a>,
        root: flatbuffers::WIPOffset<KeyValue<'a>>,
    ) {
        fbb.finish(root, None);
    }

    #[inline]
    pub fn finish_size_prefixed_key_value_buffer<'a, 'b>(
        fbb: &'b mut flatbuffers::FlatBufferBuilder<'a>,
        root: flatbuffers::WIPOffset<KeyValue<'a>>,
    ) {
        fbb.finish_size_prefixed(root, None);
    }
} // pub mod KVDemo

[CasperN]

@ChristopherRabotin Nope, I still don't have time.

I am curious though about your intended use case and what you'd like the code to look like.

[ChristopherRabotin]

My use case is that I store a series of quaternion starting from a given datetime and the key is the time offset from the absolute datetime stored above the demo I provided. Then, I want to arbitrarily query that quaternion. With an ordered index, I could use a binary search for the offset. Without that, I would probably need to rely on a copy of the index that is ordered, and binary search that index.

I imagine that, in the best of worlds, I'd like to call binary_search(&x) directly, like I would on a Vec.

[github-actions[bot]]

This issue is stale because it has been open 6 months with no activity. Please comment or this will be closed in 14 days.

[mpawlowski-eyeo]

I would also like to see support for a binary search via the key_compare_less_than building block. I need it for my project.

I tried the solution from https://github.com/google/flatbuffers/issues/5780 and, as long as I make sure to sort the items by key before building the vector, it seems to work.

I'm not happy about needing to extend the Vector implementation in my code tho. Would it be acceptable to just merge the solution @fabianmurariu suggested? It is incomplete in that there's no facility for automatically sorting the table, a user could end up performing a binary search on unsorted data if they're not careful.

I'm still learning Rust, I don't feel confident enough to drive a MR for this yet, or to propose a great solution.

[CasperN]

I no longer have the time to be an active maintainer anymore, sadly, but I agree its better to get some support rather than no support

[github-actions[bot]]

This issue is stale because it has been open 6 months with no activity. Please comment or label not-stale, or this will be closed in 14 days.

[github-actions[bot]]

This issue was automatically closed due to no activity for 6 months plus the 14 day notice period.