sfkv/src/lib.rs

#![no_std]

use core::str;
use byteorder::{ByteOrder, BigEndian};
#[cfg(feature = "postcard-values")]
use serde::{Deserialize, Serialize};

mod error;
pub use error::{Error, ReadError, WriteError};
mod iter;
use iter::Iter;
pub mod no_flash;
mod test;

/// Backend interface for `Store`
pub trait StoreBackend {
    /// type returned by `data()` for reading the flash
    type Data: ?Sized + AsRef<[u8]>;

    /// memory-mapped
    fn data(&self) -> &Self::Data;
    /// size of flash page
    fn len(&self) -> usize {
        self.data().as_ref().len()
    }

    /// error type returned by `erase()`/`flash()` operations
    type Error;
    /// erase flash page
    fn erase(&mut self) -> Result<(), Self::Error>;
    /// program flash with offset into flash page
    fn program(&mut self, offset: usize, payload: &[u8]) -> Result<(), Self::Error>;
    /// called after repeated `program()` invocations to allow for eg. cache flushing
    fn program_done(&mut self) {}

    /// need for automatic compaction
    ///
    /// leaves memory management to the implementer
    fn backup_space(&self) -> &'static mut [u8];
}

/// Simple Flash Key Value Store
pub struct Store<B: StoreBackend> {
    backend: B,
}

impl<B: StoreBackend> Store<B> {
    /// wrap a `StoreBackend` into a store
    pub fn new(backend: B) -> Self {
        Store { backend }
    }

    /// read from `key`
    pub fn read(&self, key: &str) -> Result<Option<&[u8]>, ReadError> {
        let mut iter = Iter::new(self.backend.data().as_ref());
        let mut value = None;
        while let Some(result) = iter.next() {
            let (record_key, record_value) = result?;
            if key.as_bytes() == record_key {
                // last write wins
                value = Some(record_value)
            }
        }
        Ok(value)
    }

    /// read from `key`, decode UTF-8
    pub fn read_str(&self, key: &str) -> Result<Option<&str>, ReadError> {
        self.read(key)
            .and_then(|value| value
                      .map(|value| str::from_utf8(value)
                           .map_err(ReadError::Utf8Error)
                      )
                      .transpose()
            )
    }

    /// read from `key`, decode with `postcard`
    #[cfg(feature = "postcard-values")]
    pub fn read_value<'a, T: Deserialize<'a>>(&'a self, key: &str) -> Result<Option<T>, Error<B::Error>> {
        self.read(key)?
            .map(
                |data| postcard::from_bytes(data)
                    .map_err(Error::Decode)
            ).transpose()
    }

    /// how many bytes are currently used
    ///
    /// equally, offset of free space
    pub fn get_bytes_used(&self) -> Result<usize, ReadError> {
        let mut iter = Iter::new(self.backend.data().as_ref());
        while let Some(result) = iter.next() {
            let _ = result?;
        }
        Ok(iter.offset)
    }

    unsafe fn append_at(&mut self, mut offset: usize,
                        key: &[u8], value: &[u8]) -> Result<usize, WriteError<B::Error>> {
        let record_size = 4 + key.len() + 1 + value.len();
        if offset + record_size > self.backend.len() {
            return Err(WriteError::SpaceExhausted)
        }

        let mut record_size_bytes = [0u8; 4];
        BigEndian::write_u32(&mut record_size_bytes[..], record_size as u32);

        {
            let mut write = |payload| -> Result<(), WriteError<B::Error>> {
                self.backend.program(offset, payload)
                    .map_err(WriteError::Backend)?;
                offset += payload.len();
                Ok(())
            };

            write(&record_size_bytes[..])?;
            write(key)?;
            write(&[0])?;
            write(value)?;
        }
        self.backend.program_done();

        Ok(offset)
    }

    fn compact(&mut self) -> Result<(), Error<B::Error>> {
        let old_data = self.backend.backup_space();
        old_data.copy_from_slice(self.backend.data().as_ref());

        self.erase()?;

        // This is worst-case quadratic, but we're limited by a small SPI flash sector size,
        // so it does not really matter.
        let mut offset = 0;
        let mut iter = Iter::new(old_data.as_ref());
        'iter: while let Some(result) = iter.next() {
            let (key, value) = result?;
            if value.is_empty() {
                // This is a removed entry, ignore it.
                continue
            }

            let mut next_iter = iter.clone();
            while let Some(next_result) = next_iter.next() {
                let (next_key, _) = next_result?;
                if key == next_key {
                    // There's another entry that overwrites this one, ignore this one.
                    continue 'iter
                }
            }
            offset = unsafe { self.append_at(offset, key, value)? };
        }

        Ok(())
    }

    fn append(&mut self, key: &str, value: &[u8]) -> Result<(), Error<B::Error>> {
        let free_offset = {
            let mut iter = Iter::new(self.backend.data().as_ref());
            let mut not_modified = false;
            while let Some(result) = iter.next() {
                let (record_key, record_value) = result?;
                if key.as_bytes() == record_key {
                    not_modified = value == record_value;
                }
            }
            if not_modified {
                return Ok(())
            }
            iter.offset
        };

        unsafe { self.append_at(free_offset, key.as_bytes(), value)? };
        Ok(())
    }

    /// store a buffer `value` at `key`
    pub fn write<V: AsRef<[u8]>>(&mut self, key: &str, value: V) -> Result<(), Error<B::Error>> {
        let value = value.as_ref();
        match self.append(key, value) {
            Err(Error::Write(WriteError::SpaceExhausted)) => {
                self.compact()?;
                self.append(key, value)
            }
            res => res
        }
    }

    /// encode with `postcard`, write at `key`
    #[cfg(feature = "postcard-values")]
    pub fn write_value<T, V>(&mut self, key: &str, value: &T, mut value_buf: V) -> Result<(), Error<B::Error>>
    where
        T: Serialize,
        V: AsMut<[u8]>,
    {
        let data = postcard::to_slice(value, value_buf.as_mut())
            .map_err(Error::Encode)?;
        self.write(key, data)
    }

    /// store a 0-byte tombstone value at `key`
    pub fn remove(&mut self, key: &str) -> Result<(), Error<B::Error>> {
        self.write(key, &[])
    }

    /// invokes erase on the backend (this is no compaction!)
    pub fn erase(&mut self) -> Result<(), WriteError<B::Error>> {
        self.backend.erase()
            .map_err(WriteError::Backend)?;

        Ok(())
    }
}