Struct fst::MapBuilder[][src]

pub struct MapBuilder<W>(_);

A builder for creating a map.

This is not your average everyday builder. It has two important qualities that make it a bit unique from what you might expect:

  1. All keys must be added in lexicographic order. Adding a key out of order will result in an error. Additionally, adding a duplicate key will also result in an error. That is, once a key is associated with a value, that association can never be modified or deleted.
  2. The representation of a map is streamed to any io::Write as it is built. For an in memory representation, this can be a Vec<u8>.

Point (2) is especially important because it means that a map can be constructed without storing the entire map in memory. Namely, since it works with any io::Write, it can be streamed directly to a file.

With that said, the builder does use memory, but memory usage is bounded to a constant size. The amount of memory used trades off with the compression ratio. Currently, the implementation hard codes this trade off which can result in about 5-20MB of heap usage during construction. (N.B. Guaranteeing a maximal compression ratio requires memory proportional to the size of the map, which defeats some of the benefit of streaming it to disk. In practice, a small bounded amount of memory achieves close-to-minimal compression ratios.)

The algorithmic complexity of map construction is O(n) where n is the number of elements added to the map.

Example: build in memory

This shows how to use the builder to construct a map in memory. Note that Map::from_iter provides a convenience function that achieves this same goal without needing to explicitly use MapBuilder.

use fst::{IntoStreamer, Streamer, Map, MapBuilder};

let mut build = MapBuilder::memory();
build.insert("bruce", 1).unwrap();
build.insert("clarence", 2).unwrap();
build.insert("stevie", 3).unwrap();

// You could also call `finish()` here, but since we're building the map in
// memory, there would be no way to get the `Vec<u8>` back.
let bytes = build.into_inner().unwrap();

// At this point, the map has been constructed, but here's how to read it.
let map = Map::new(bytes).unwrap();
let mut stream = map.into_stream();
let mut kvs = vec![];
while let Some((k, v)) = stream.next() {
    kvs.push((k.to_vec(), v));
}
assert_eq!(kvs, vec![
    (b"bruce".to_vec(), 1),
    (b"clarence".to_vec(), 2),
    (b"stevie".to_vec(), 3),
]);

Example: stream to file

This shows how to do stream construction of a map to a file.

use std::fs::File;
use std::io;

use fst::{IntoStreamer, Streamer, Map, MapBuilder};

let mut wtr = io::BufWriter::new(File::create("map.fst").unwrap());
let mut build = MapBuilder::new(wtr).unwrap();
build.insert("bruce", 1).unwrap();
build.insert("clarence", 2).unwrap();
build.insert("stevie", 3).unwrap();

// If you want the writer back, then call `into_inner`. Otherwise, this
// will finish construction and call `flush`.
build.finish().unwrap();

// At this point, the map has been constructed, but here's how to read it.
// NOTE: Normally, one would memory map a file instead of reading its
// entire contents on to the heap.
let map = Map::new(std::fs::read("map.fst").unwrap()).unwrap();
let mut stream = map.into_stream();
let mut kvs = vec![];
while let Some((k, v)) = stream.next() {
    kvs.push((k.to_vec(), v));
}
assert_eq!(kvs, vec![
    (b"bruce".to_vec(), 1),
    (b"clarence".to_vec(), 2),
    (b"stevie".to_vec(), 3),
]);

Implementations

impl MapBuilder<Vec<u8>>[src]

pub fn memory() -> MapBuilder<Vec<u8>>[src]

Create a builder that builds a map in memory.

pub fn into_map(self) -> Map<Vec<u8>>[src]

Finishes the construction of the map and returns it.

impl<W: Write> MapBuilder<W>[src]

pub fn new(wtr: W) -> Result<MapBuilder<W>>[src]

Create a builder that builds a map by writing it to wtr in a streaming fashion.

pub fn insert<K: AsRef<[u8]>>(&mut self, key: K, val: u64) -> Result<()>[src]

Insert a new key-value pair into the map.

Keys must be convertible to byte strings. Values must be a u64, which is a restriction of the current implementation of finite state transducers. (Values may one day be expanded to other types.)

If a key is inserted that is less than or equal to any previous key added, then an error is returned. Similarly, if there was a problem writing to the underlying writer, an error is returned.

pub fn extend_iter<K, I>(&mut self, iter: I) -> Result<()> where
    K: AsRef<[u8]>,
    I: IntoIterator<Item = (K, u64)>, 
[src]

Calls insert on each item in the iterator.

If an error occurred while adding an element, processing is stopped and the error is returned.

If a key is inserted that is less than or equal to any previous key added, then an error is returned. Similarly, if there was a problem writing to the underlying writer, an error is returned.

pub fn extend_stream<'f, I, S>(&mut self, stream: I) -> Result<()> where
    I: for<'a> IntoStreamer<'a, Into = S, Item = (&'a [u8], u64)>,
    S: 'f + for<'a> Streamer<'a, Item = (&'a [u8], u64)>, 
[src]

Calls insert on each item in the stream.

Note that unlike extend_iter, this is not generic on the items in the stream.

If a key is inserted that is less than or equal to any previous key added, then an error is returned. Similarly, if there was a problem writing to the underlying writer, an error is returned.

pub fn finish(self) -> Result<()>[src]

Finishes the construction of the map and flushes the underlying writer. After completion, the data written to W may be read using one of Map’s constructor methods.

pub fn into_inner(self) -> Result<W>[src]

Just like finish, except it returns the underlying writer after flushing it.

pub fn get_ref(&self) -> &W[src]

Gets a reference to the underlying writer.

pub fn bytes_written(&self) -> u64[src]

Returns the number of bytes written to the underlying writer

Auto Trait Implementations

impl<W> RefUnwindSafe for MapBuilder<W> where
    W: RefUnwindSafe

impl<W> Send for MapBuilder<W> where
    W: Send

impl<W> Sync for MapBuilder<W> where
    W: Sync

impl<W> Unpin for MapBuilder<W> where
    W: Unpin

impl<W> UnwindSafe for MapBuilder<W> where
    W: UnwindSafe

Blanket Implementations

impl<T> Any for T where
    T: 'static + ?Sized
[src]

pub fn type_id(&self) -> TypeId[src]

Gets the TypeId of self. Read more

impl<T> Borrow<T> for T where
    T: ?Sized
[src]

pub fn borrow(&self) -> &T[src]

Immutably borrows from an owned value. Read more

impl<T> BorrowMut<T> for T where
    T: ?Sized
[src]

pub fn borrow_mut(&mut self) -> &mut T[src]

Mutably borrows from an owned value. Read more

impl<T> From<T> for T[src]

pub fn from(t: T) -> T[src]

Performs the conversion.

impl<T, U> Into<U> for T where
    U: From<T>, 
[src]

pub fn into(self) -> U[src]

Performs the conversion.

impl<T, U> TryFrom<U> for T where
    U: Into<T>, 
[src]

type Error = Infallible

The type returned in the event of a conversion error.

pub fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>[src]

Performs the conversion.

impl<T, U> TryInto<U> for T where
    U: TryFrom<T>, 
[src]

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.

pub fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>[src]

Performs the conversion.