use std::collections::BTreeMap;
use std::ops::RangeBounds;
use crate::core::errors::{PvError, Result};
use crate::core::types::RecordAddr;
use crate::core::value::Value;
const IV_NULL: u8 = 0x00;
const IV_INT: u8 = 0x01;
const IV_TEXT: u8 = 0x02;
const IV_BLOB: u8 = 0x03;
const IV_DECIMAL: u8 = 0x06;
#[derive(Default)]
pub struct SecondaryIndex {
map: BTreeMap<Value, Vec<RecordAddr>>,
entries: usize,
}
impl SecondaryIndex {
pub fn new() -> Self {
Self::default()
}
pub fn insert(&mut self, value: &Value, addr: RecordAddr) {
self.map.entry(value.clone()).or_default().push(addr);
self.entries += 1;
}
pub fn lookup(&self, value: &Value) -> &[RecordAddr] {
self.map.get(value).map(Vec::as_slice).unwrap_or(&[])
}
pub fn range<R: RangeBounds<Value>>(&self, range: R) -> Vec<RecordAddr> {
self.map
.range(range)
.flat_map(|(_, addrs)| addrs.iter().copied())
.collect()
}
pub fn range_len<R: RangeBounds<Value>>(&self, range: R) -> usize {
self.map
.range(range)
.map(|(_, addresses)| addresses.len())
.sum()
}
pub(crate) fn append_range<R: RangeBounds<Value>>(&self, range: R, out: &mut Vec<RecordAddr>) {
out.extend(
self.map
.range(range)
.flat_map(|(_, addresses)| addresses.iter().copied()),
);
}
pub fn ordered_addrs(&self, descending: bool) -> Vec<RecordAddr> {
if descending {
self.map.values().rev().flatten().copied().collect()
} else {
self.map.values().flatten().copied().collect()
}
}
pub fn len(&self) -> usize {
self.entries
}
pub fn is_empty(&self) -> bool {
self.entries == 0
}
pub fn distinct_keys(&self) -> usize {
self.map.len()
}
pub fn to_pairs(&self) -> Vec<(Value, Vec<RecordAddr>)> {
self.map
.iter()
.map(|(k, v)| (k.clone(), v.clone()))
.collect()
}
pub fn from_pairs(pairs: Vec<(Value, Vec<RecordAddr>)>) -> Self {
let mut map: BTreeMap<Value, Vec<RecordAddr>> = BTreeMap::new();
let mut entries = 0;
for (k, addrs) in pairs {
entries += addrs.len();
map.entry(k).or_default().extend(addrs);
}
Self { map, entries }
}
pub fn encode_binary(&self) -> Vec<u8> {
let mut out = Vec::new();
out.extend_from_slice(&(self.map.len() as u32).to_le_bytes());
for (key, addrs) in &self.map {
encode_index_value(&mut out, key);
out.extend_from_slice(&(addrs.len() as u32).to_le_bytes());
for &addr in addrs {
out.extend_from_slice(&addr.to_le_bytes());
}
}
out
}
pub fn decode_binary(bytes: &[u8]) -> Result<Self> {
let mut pos = 0usize;
let key_count = rd_u32(bytes, &mut pos)? as usize;
let mut map: BTreeMap<Value, Vec<RecordAddr>> = BTreeMap::new();
let mut entries = 0usize;
for _ in 0..key_count {
let key = decode_index_value(bytes, &mut pos)?;
if map.contains_key(&key) {
return Err(PvError::Corruption(
"index: duplicate key entry in binary encoding".into(),
));
}
let addr_count = rd_u32(bytes, &mut pos)? as usize;
let mut addrs = Vec::with_capacity(addr_count.min(1024));
for _ in 0..addr_count {
addrs.push(rd_u64(bytes, &mut pos)?);
}
entries += addrs.len();
map.insert(key, addrs);
}
if pos != bytes.len() {
return Err(PvError::Corruption(
"index: trailing bytes after declared keys".into(),
));
}
Ok(Self { map, entries })
}
}
fn encode_index_value(out: &mut Vec<u8>, value: &Value) {
match value {
Value::Null => out.push(IV_NULL),
Value::Int(i) => {
out.push(IV_INT);
out.extend_from_slice(&i.to_le_bytes());
}
Value::Decimal(m) => {
out.push(IV_DECIMAL);
out.extend_from_slice(&m.to_le_bytes());
}
Value::Text(s) => {
out.push(IV_TEXT);
let b = s.as_bytes();
out.extend_from_slice(&(b.len() as u32).to_le_bytes());
out.extend_from_slice(b);
}
Value::Blob(b) => {
out.push(IV_BLOB);
out.extend_from_slice(&(b.len() as u32).to_le_bytes());
out.extend_from_slice(b);
}
}
}
fn decode_index_value(buf: &[u8], pos: &mut usize) -> Result<Value> {
let tag = *buf
.get(*pos)
.ok_or_else(|| PvError::Corruption("index: truncated at value tag".into()))?;
*pos += 1;
Ok(match tag {
IV_NULL => Value::Null,
IV_INT => Value::Int(rd_u64(buf, pos)? as i64),
IV_DECIMAL => Value::Decimal(rd_i128(buf, pos)?),
IV_TEXT => {
let bytes = rd_bytes(buf, pos)?;
Value::Text(
String::from_utf8(bytes.to_vec())
.map_err(|_| PvError::Corruption("index: invalid utf-8 key".into()))?,
)
}
IV_BLOB => Value::Blob(rd_bytes(buf, pos)?.to_vec()),
other => {
return Err(PvError::Corruption(format!(
"index: bad value tag 0x{other:02X}"
)))
}
})
}
fn rd_bytes<'a>(buf: &'a [u8], pos: &mut usize) -> Result<&'a [u8]> {
let len = rd_u32(buf, pos)? as usize;
let end = pos
.checked_add(len)
.filter(|&e| e <= buf.len())
.ok_or_else(|| PvError::Corruption("index: truncated payload".into()))?;
let slice = &buf[*pos..end];
*pos = end;
Ok(slice)
}
fn rd_u32(buf: &[u8], pos: &mut usize) -> Result<u32> {
let slice = buf
.get(*pos..*pos + 4)
.ok_or_else(|| PvError::Corruption("index: truncated u32".into()))?;
*pos += 4;
Ok(u32::from_le_bytes(slice.try_into().unwrap()))
}
fn rd_u64(buf: &[u8], pos: &mut usize) -> Result<u64> {
let slice = buf
.get(*pos..*pos + 8)
.ok_or_else(|| PvError::Corruption("index: truncated u64".into()))?;
*pos += 8;
Ok(u64::from_le_bytes(slice.try_into().unwrap()))
}
fn rd_i128(buf: &[u8], pos: &mut usize) -> Result<i128> {
let slice = buf
.get(*pos..*pos + 16)
.ok_or_else(|| PvError::Corruption("index: truncated i128".into()))?;
*pos += 16;
Ok(i128::from_le_bytes(slice.try_into().unwrap()))
}
#[cfg(test)]
mod tests {
use super::*;
use std::ops::Bound;
#[test]
fn groups_addresses_by_value() {
let mut idx = SecondaryIndex::new();
idx.insert(&Value::Int(1), 10);
idx.insert(&Value::Int(1), 11);
idx.insert(&Value::Int(2), 20);
idx.insert(&Value::from("x"), 30);
assert_eq!(idx.lookup(&Value::Int(1)), &[10, 11]);
assert_eq!(idx.lookup(&Value::Int(2)), &[20]);
assert_eq!(idx.lookup(&Value::from("x")), &[30]);
assert_eq!(idx.lookup(&Value::Int(99)), &[] as &[RecordAddr]);
assert_eq!(idx.len(), 4);
assert_eq!(idx.distinct_keys(), 3);
}
#[test]
fn distinguishes_types_with_same_bytes() {
let mut idx = SecondaryIndex::new();
idx.insert(&Value::Int(0), 1);
idx.insert(&Value::Null, 2);
assert_eq!(idx.lookup(&Value::Int(0)), &[1]);
assert_eq!(idx.lookup(&Value::Null), &[2]);
}
#[test]
fn range_scan_returns_keys_in_order() {
let mut idx = SecondaryIndex::new();
for (v, a) in [(10, 1), (30, 2), (20, 3), (30, 4), (40, 5)] {
idx.insert(&Value::Int(v), a);
}
assert_eq!(
idx.range((Bound::Excluded(Value::Int(20)), Bound::Unbounded)),
vec![2, 4, 5]
);
assert_eq!(
idx.range((Bound::Unbounded, Bound::Included(Value::Int(20)))),
vec![1, 3]
);
assert_eq!(
idx.range((
Bound::Included(Value::Int(20)),
Bound::Excluded(Value::Int(40))
)),
vec![3, 2, 4]
);
}
#[test]
fn ordered_addrs_walks_keys_in_order() {
let mut idx = SecondaryIndex::new();
for (v, a) in [(30, 1), (10, 2), (20, 3), (10, 4)] {
idx.insert(&Value::Int(v), a);
}
assert_eq!(idx.ordered_addrs(false), vec![2, 4, 3, 1]);
assert_eq!(idx.ordered_addrs(true), vec![1, 3, 2, 4]);
}
#[test]
fn binary_round_trips_every_value_kind() {
let mut idx = SecondaryIndex::new();
idx.insert(&Value::Null, 1);
idx.insert(&Value::Int(-42), 2);
idx.insert(&Value::Int(-42), 3); idx.insert(&Value::Decimal(1_500_000), 4);
idx.insert(&Value::from("crate"), 5);
idx.insert(&Value::Blob(vec![0xDE, 0xAD, 0xBE, 0xEF]), 6);
let blob = idx.encode_binary();
let back = SecondaryIndex::decode_binary(&blob).unwrap();
assert_eq!(back.len(), idx.len());
assert_eq!(back.distinct_keys(), idx.distinct_keys());
assert_eq!(back.lookup(&Value::Int(-42)), &[2, 3]);
assert_eq!(back.lookup(&Value::Null), &[1]);
assert_eq!(back.lookup(&Value::Decimal(1_500_000)), &[4]);
assert_eq!(back.lookup(&Value::from("crate")), &[5]);
assert_eq!(
back.lookup(&Value::Blob(vec![0xDE, 0xAD, 0xBE, 0xEF])),
&[6]
);
assert_eq!(back.ordered_addrs(false), idx.ordered_addrs(false));
}
#[test]
fn binary_decode_rejects_truncation() {
let mut idx = SecondaryIndex::new();
idx.insert(&Value::Int(7), 100);
idx.insert(&Value::from("hello"), 200);
let blob = idx.encode_binary();
for cut in 0..blob.len() {
assert!(SecondaryIndex::decode_binary(&blob[..cut]).is_err());
}
assert!(SecondaryIndex::decode_binary(&blob).is_ok());
let mut trailing = blob;
trailing.push(0);
assert!(SecondaryIndex::decode_binary(&trailing).is_err());
}
#[test]
fn binary_decode_rejects_duplicate_key_blocks() {
let mut idx = SecondaryIndex::new();
idx.insert(&Value::Int(7), 100);
let mut blob = idx.encode_binary();
let duplicate = blob[4..].to_vec();
blob[..4].copy_from_slice(&2u32.to_le_bytes());
blob.extend_from_slice(&duplicate);
assert!(SecondaryIndex::decode_binary(&blob).is_err());
}
}