use std::collections::hash_map::Entry;
use std::collections::HashMap;
use std::mem::size_of;
use super::postings::{Position, PostingCursor, PostingList, TermStore};
use super::DocId;
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Posting {
pub doc: DocId,
pub positions: Vec<Position>,
}
#[derive(Debug, Default, Clone, PartialEq, Eq)]
pub struct MemPostingList {
postings: Vec<Posting>,
}
impl MemPostingList {
pub fn push(&mut self, doc: DocId, position: Position) {
match self.postings.last_mut() {
Some(last) if last.doc == doc => {
if last.positions.last() != Some(&position) {
debug_assert!(last.positions.last().is_none_or(|&p| p < position));
last.positions.push(position);
}
}
Some(last) => {
debug_assert!(last.doc < doc, "postings must be pushed in doc order");
self.postings.push(Posting { doc, positions: vec![position] });
}
None => self.postings.push(Posting { doc, positions: vec![position] }),
}
}
pub(crate) fn append(&mut self, other: MemPostingList) {
debug_assert!(
match (self.postings.last(), other.postings.first()) {
(Some(a), Some(b)) => a.doc < b.doc,
_ => true,
},
"appended list must start after this one ends"
);
self.postings.extend(other.postings);
}
pub fn as_slice(&self) -> &[Posting] {
&self.postings
}
pub fn heap_bytes(&self) -> usize {
self.postings.capacity() * size_of::<Posting>()
+ self.postings.iter().map(|p| p.positions.capacity() * size_of::<Position>()).sum::<usize>()
}
}
pub struct MemPostingCursor<'a> {
postings: &'a [Posting],
idx: usize,
}
impl PostingCursor for MemPostingCursor<'_> {
fn doc(&self) -> Option<DocId> {
self.postings.get(self.idx).map(|p| p.doc)
}
fn advance(&mut self) -> Option<DocId> {
if self.idx < self.postings.len() {
self.idx += 1;
}
self.doc()
}
fn seek(&mut self, target: DocId) -> Option<DocId> {
let len = self.postings.len();
if self.idx >= len {
return None;
}
if self.postings[self.idx].doc >= target {
return Some(self.postings[self.idx].doc);
}
let mut lo = self.idx;
let mut step = 1;
let mut hi = lo + step;
while hi < len && self.postings[hi].doc < target {
lo = hi;
step *= 2;
hi = lo + step;
}
let hi = hi.min(len);
let off = self.postings[lo + 1..hi].partition_point(|p| p.doc < target);
self.idx = lo + 1 + off;
self.doc()
}
fn positions(&mut self) -> &[Position] {
&self.postings[self.idx].positions
}
}
impl PostingList for MemPostingList {
type Cursor<'a> = MemPostingCursor<'a>;
fn doc_freq(&self) -> u32 {
self.postings.len() as u32
}
fn cursor(&self) -> MemPostingCursor<'_> {
MemPostingCursor { postings: &self.postings, idx: 0 }
}
}
#[derive(Debug, Default)]
pub struct MemTermStore {
terms: HashMap<String, MemPostingList>,
}
impl MemTermStore {
pub fn iter(&self) -> impl Iterator<Item = (&str, &MemPostingList)> {
self.terms.iter().map(|(t, p)| (t.as_str(), p))
}
pub fn total_postings(&self) -> u64 {
self.terms.values().map(|l| l.postings.len() as u64).sum()
}
pub(crate) fn merge_shard(&mut self, shard: HashMap<String, MemPostingList>) {
if self.terms.is_empty() {
self.terms = shard;
return;
}
for (term, list) in shard {
match self.terms.entry(term) {
Entry::Occupied(mut e) => e.get_mut().append(list),
Entry::Vacant(e) => {
e.insert(list);
}
}
}
}
}
impl TermStore for MemTermStore {
type List<'a> = &'a MemPostingList;
fn get(&self, term: &str) -> Option<&MemPostingList> {
self.terms.get(term)
}
fn term_count(&self) -> usize {
self.terms.len()
}
fn memory_bytes(&self) -> usize {
let cap = self.terms.capacity();
let buckets = if cap == 0 { 0 } else { (cap * 8 / 7).next_power_of_two() };
let table = buckets * (size_of::<String>() + size_of::<MemPostingList>() + 1);
let contents: usize = self.terms.iter().map(|(k, v)| k.capacity() + v.heap_bytes()).sum();
size_of::<Self>() + table + contents
}
}
#[cfg(test)]
mod tests {
use super::*;
fn list(docs: &[(DocId, &[Position])]) -> MemPostingList {
let mut l = MemPostingList::default();
for (d, ps) in docs {
for &p in *ps {
l.push(*d, p);
}
}
l
}
fn docs<C: PostingCursor>(mut c: C) -> Vec<DocId> {
let mut out = vec![];
while let Some(d) = c.doc() {
out.push(d);
c.advance();
}
out
}
#[test]
fn push_groups_positions_by_doc_and_dedups_repeats() {
let mut l = MemPostingList::default();
l.push(3, 0);
l.push(3, 0); l.push(3, 5);
l.push(7, 1);
assert_eq!(
l.as_slice(),
&[Posting { doc: 3, positions: vec![0, 5] }, Posting { doc: 7, positions: vec![1] }]
);
assert_eq!(l.doc_freq(), 2);
}
#[test]
fn cursor_walks_in_order_and_exhausts() {
let l = list(&[(1, &[0]), (4, &[2, 3]), (9, &[1])]);
assert_eq!(docs(l.cursor()), vec![1, 4, 9]);
let mut c = l.cursor();
c.advance();
assert_eq!(c.positions(), &[2, 3]);
assert_eq!(c.term_freq(), 2);
c.advance();
c.advance();
assert_eq!(c.doc(), None);
assert_eq!(c.advance(), None); }
#[test]
fn empty_list_cursor_is_exhausted() {
let l = MemPostingList::default();
let mut c = l.cursor();
assert_eq!(c.doc(), None);
assert_eq!(c.seek(0), None);
}
#[test]
fn seek_semantics() {
let ids: Vec<DocId> = (0..200).map(|i| i * 3).collect(); let l = list(&ids.iter().map(|&d| (d, &[0u32][..])).collect::<Vec<_>>());
let mut c = l.cursor();
assert_eq!(c.seek(0), Some(0)); assert_eq!(c.seek(4), Some(6)); assert_eq!(c.seek(6), Some(6)); assert_eq!(c.seek(2), Some(6)); assert_eq!(c.seek(300), Some(300)); assert_eq!(c.seek(596), Some(597)); assert_eq!(c.seek(598), None); assert_eq!(c.doc(), None);
}
#[test]
fn seek_every_target_matches_linear_scan() {
let ids: Vec<DocId> = [1u32, 2, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377].to_vec();
let l = list(&ids.iter().map(|&d| (d, &[0u32][..])).collect::<Vec<_>>());
for start in 0..ids.len() {
for target in 0..400u32 {
let mut c = l.cursor();
for _ in 0..start {
c.advance();
}
let expected = ids.iter().copied().find(|&d| d >= ids[start] && d >= target);
assert_eq!(c.seek(target), expected, "start={start} target={target}");
}
}
}
#[test]
fn append_concatenates() {
let mut a = list(&[(1, &[0]), (2, &[1])]);
let b = list(&[(5, &[0]), (8, &[1])]);
a.append(b);
assert_eq!(docs(a.cursor()), vec![1, 2, 5, 8]);
}
#[test]
fn merge_shard_appends_existing_terms_and_adds_new() {
let mut store = MemTermStore::default();
let mut s1 = HashMap::new();
s1.insert("foo".to_string(), list(&[(0, &[0]), (1, &[0])]));
s1.insert("bar".to_string(), list(&[(1, &[1])]));
let mut s2 = HashMap::new();
s2.insert("foo".to_string(), list(&[(2, &[0])]));
s2.insert("baz".to_string(), list(&[(3, &[0])]));
store.merge_shard(s1);
store.merge_shard(s2);
assert_eq!(store.term_count(), 3);
assert_eq!(docs(store.get("foo").unwrap().cursor()), vec![0, 1, 2]);
assert_eq!(docs(store.get("bar").unwrap().cursor()), vec![1]);
assert_eq!(docs(store.get("baz").unwrap().cursor()), vec![3]);
assert!(store.get("nope").is_none());
assert_eq!(store.total_postings(), 5);
}
#[test]
fn reference_is_a_posting_list() {
fn df<L: PostingList>(l: L) -> u32 {
l.doc_freq()
}
let l = list(&[(1, &[0])]);
assert_eq!(df(&l), 1);
assert_eq!(df(&l), 1);
}
#[test]
fn memory_accounting_is_positive_and_grows() {
let mut store = MemTermStore::default();
let base = store.memory_bytes();
let mut s = HashMap::new();
for i in 0..1000 {
s.insert(format!("term{i}"), list(&[(i, &[0, 1, 2])]));
}
store.merge_shard(s);
assert!(store.memory_bytes() > base + 1000 * 3 * size_of::<Position>());
}
}