Struct tantivy_stacker::ExpUnrolledLinkedList

pub struct ExpUnrolledLinkedList { /* private fields */ }

An exponential unrolled link.

The use case is as follows. Tantivy’s indexer conceptually acts like a HashMap<Term, Vec<u32>>. As we come across a given term in document D, we lookup the term in the map and append the document id to its vector.

The vector is then only read when it is serialized.

The ExpUnrolledLinkedList offers a more efficient solution to this problem.

It combines the idea of the unrolled linked list and tries to address the problem of selecting an adequate block size using a strategy similar to that of the Vec amortized resize strategy.

Data is stored in a linked list of blocks. The first block has a size of 8 and each block has a length of twice that of the previous block up to MAX_BLOCK_LEN = 1<<15.

This strategy is a good trade off to handle numerous very rare terms and avoid wasting half of the memory for very frequent terms.

Implementations

impl ExpUnrolledLinkedList

pub fn increment_num_blocks(&mut self)

pub fn writer<'a>( &'a mut self, arena: &'a mut MemoryArena ) -> ExpUnrolledLinkedListWriter<'a>

pub fn read_to_end(&self, arena: &MemoryArena, output: &mut Vec<u8>)

Trait Implementations

impl Clone for ExpUnrolledLinkedList

fn clone(&self) -> ExpUnrolledLinkedList

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for ExpUnrolledLinkedList

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for ExpUnrolledLinkedList

fn default() -> Self

Returns the “default value” for a type.

impl Copy for ExpUnrolledLinkedList