use crate::core::index::knn_vector_values::{DenseDocIndexIterator, DocIndexIterator};
use crate::core::search::doc_id_set_iterator::DocIdSetIterator;
use crate::core::store::data_input_ext::DataInputExt;
use crate::core::store::dummy::dummy_random_access_input::DummyRandomAccessInput;
use crate::core::store::random_access_input::RandomAccessInput;
use crate::core::store::{DataInput, IndexInput, IndexOutput};
use crate::core::util::bit_util::BitUtil;
use crate::core::util::error::lucene_error::{LuceneError, Result};
use parking_lot::Mutex;
use std::sync::Arc;
pub struct IndexedDISIImpl<I, R>
where
I: IndexInput,
R: RandomAccessInput,
{
slice: I,
jump_table: Option<R>,
jump_table_entry_count: i32,
dense_rank_power: i8,
dense_rank_words: i32,
dense_rank_table: Option<Box<[u8]>>,
cost: i64,
block: i32,
block_end: usize,
dense_bitmap_offset: Option<usize>,
next_block_index: i32,
pub(crate) method: Method,
doc: i32,
index: i32,
exists: bool,
next_exist_doc_in_block: i32,
word: i64,
word_index: i32,
number_of_ones: i32,
dense_origo_index: i32,
gap: i32,
}
pub type IndexedDISI<I, P> =
IndexedDISIImpl<<P as IndexedDISIPolicy<I>>::Slice, <P as IndexedDISIPolicy<I>>::JumpTable>;
impl<I, R> IndexedDISIImpl<I, R>
where
I: IndexInput,
R: RandomAccessInput,
{
pub fn new<D>(
index_input: &D,
offset: usize,
length: usize,
jump_table_entry_count: i32,
dense_rank_power: i8,
cost: i64,
) -> Result<Self>
where
D: IndexInput<IndexInput = I, RandomAccessSlice = R>,
{
let block_slice =
create_block_slice(index_input, "docs", offset, length, jump_table_entry_count)?;
let jump_table = create_jump_table(index_input, offset, length, jump_table_entry_count)?;
Self::from_components(
block_slice,
jump_table,
jump_table_entry_count,
dense_rank_power,
cost,
)
}
}
impl<I, R> IndexedDISIImpl<I, R>
where
I: IndexInput,
R: RandomAccessInput,
{
pub fn from_components(
block_slice: I,
jump_table: Option<R>,
jump_table_entry_count: i32,
dense_rank_power: i8,
cost: i64,
) -> Result<Self> {
if !(7..=15).contains(&dense_rank_power) && dense_rank_power != -1 {
return Err(LuceneError::illegal_argument(format!(
"Acceptable values for denseRankPower are 7-15 (every 128-32768 docIDs). \
The provided power was {} (every {} docIDs).",
dense_rank_power,
2_f64.powi(dense_rank_power as i32) as i32
)));
}
if block_slice.length()? > 0 {
block_slice.prefetch(0, 1)?;
}
if let Some(jump_table) = &jump_table
&& jump_table.length()? > 0
{
jump_table.prefetch(0, 1)?;
}
let dense_rank_table = if dense_rank_power == -1 {
None
} else {
let rank_index_shift = dense_rank_power - 7;
Some(vec![0u8; DENSE_BLOCK_LONGS >> rank_index_shift].into_boxed_slice())
};
Ok(Self {
slice: block_slice,
jump_table,
jump_table_entry_count,
dense_rank_power,
dense_rank_words: if dense_rank_power == -1 {
0
} else {
1 << (dense_rank_power - 6)
},
dense_rank_table,
cost,
block: -1,
block_end: 0,
dense_bitmap_offset: None,
next_block_index: -1,
method: Method::Sparse,
doc: -1,
index: -1,
exists: false,
next_exist_doc_in_block: 0,
word: 0,
word_index: -1,
number_of_ones: 0,
dense_origo_index: 0,
gap: 0,
})
}
fn advance_block(&mut self, target_block: i32) -> Result<()> {
let block_index = target_block >> 16;
if let Some(jump_table) = &self.jump_table
&& block_index >= (self.block >> 16) + 2
{
let in_range_block_index = if block_index < self.jump_table_entry_count {
block_index
} else {
self.jump_table_entry_count - 1
};
let jump_pos = in_range_block_index.try_convert()? * BitUtil::LONG_BYTES;
let entry = jump_table.read_long(jump_pos)?;
let index = entry as i32;
let offset = (entry >> 32) as i32;
self.next_block_index = index - 1;
self.slice.seek(offset as usize)?;
self.read_block_header()?;
return Ok(());
}
loop {
self.slice.seek(self.block_end)?;
self.read_block_header()?;
if self.block < target_block {
continue;
}
break;
}
Ok(())
}
fn read_block_header(&mut self) -> Result<()> {
{
let slice = &mut self.slice;
self.block = (slice.read_short()? as u16 as i32) << 16;
debug_assert!(self.block >= 0);
let num_values = 1 + slice.read_short()? as u16 as i32;
self.index = self.next_block_index;
self.next_block_index = self.index + num_values;
if num_values <= MAX_ARRAY_LENGTH {
self.method = Method::Sparse;
self.block_end = slice.get_file_pointer()? + (num_values << 1) as usize;
self.next_exist_doc_in_block = -1;
} else if num_values == BLOCK_SIZE {
self.method = Method::ALL;
self.block_end = slice.get_file_pointer()?;
self.gap = self.block - self.index - 1;
} else {
self.method = Method::Dense;
let dense_bitmap_offset =
slice.get_file_pointer()? + self.dense_rank_table.as_ref().map(|v| v.len()).unwrap_or(0);
self.dense_bitmap_offset = Some(dense_bitmap_offset);
self.block_end = dense_bitmap_offset + (1 << 13);
if self.dense_rank_power != -1 {
let rank_table = self
.dense_rank_table
.as_mut()
.ok_or_else(|| LuceneError::illegal_state("dense rank table is not initialized"))?;
let rank_table_len = rank_table.len();
debug_assert!(rank_table_len <= i32::MAX as usize);
slice.read_bytes(rank_table, 0, rank_table_len)?;
}
self.word_index = -1;
self.number_of_ones = self.index + 1;
self.dense_origo_index = self.number_of_ones;
}
}
Ok(())
}
pub fn advance_exact(&mut self, target: i32) -> Result<bool> {
let target_block = ((target as u32) & 0xFFFF_0000) as i32;
if self.block < target_block {
self.advance_block(target_block)?;
}
let found = self.block == target_block && {
match self.method {
Method::Sparse => SparseMethod.advance_exact_within_block(self, target)?,
Method::Dense => DenseMethod.advance_exact_within_block(self, target)?,
Method::ALL => All.advance_exact_within_block(self, target)?,
}
};
self.doc = target;
Ok(found)
}
pub fn index(&self) -> i32 {
self.index
}
pub(crate) fn index_u(&self) -> usize {
debug_assert!(self.index >= 0);
self.index as usize
}
}
impl<I, R> crate::core::search::doc_id_set_iterator::DocIdSetIteratorExtensions
for IndexedDISIImpl<I, R>
where
I: IndexInput,
R: RandomAccessInput,
{
}
impl<I, R> crate::core::search::doc_id_set_iterator::BitSetIteratorAccess for IndexedDISIImpl<I, R>
where
I: IndexInput,
R: RandomAccessInput,
{
}
impl<I, R> DocIdSetIterator for IndexedDISIImpl<I, R>
where
I: IndexInput,
R: RandomAccessInput,
{
fn doc_id(&self) -> i32 {
self.doc
}
fn next_doc(&mut self) -> Result<i32> {
self.advance(self.doc + 1)
}
fn advance(&mut self, target: i32) -> Result<i32> {
let target_block = ((target as u32) & 0xFFFF_0000) as i32;
if self.block < target_block {
self.advance_block(target_block)?;
}
if self.block == target_block {
let advanced = match self.method {
Method::Sparse => SparseMethod.advance_within_block(self, target)?,
Method::Dense => DenseMethod.advance_within_block(self, target)?,
Method::ALL => All.advance_within_block(self, target)?,
};
if advanced {
return Ok(self.doc);
}
self.read_block_header()?;
}
let found = match self.method {
Method::Sparse => SparseMethod.advance_within_block(self, self.block)?,
Method::Dense => DenseMethod.advance_within_block(self, self.block)?,
Method::ALL => All.advance_within_block(self, self.block)?,
};
debug_assert!(found);
Ok(self.doc)
}
fn cost(&self) -> Result<i64> {
Ok(self.cost)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Method {
Sparse,
Dense,
ALL,
}
impl MethodBehavior for Method {
fn advance_within_block<I, R>(
&self,
disi: &mut IndexedDISIImpl<I, R>,
target: i32,
) -> Result<bool>
where
I: IndexInput,
R: RandomAccessInput,
{
match self {
Method::Sparse => SparseMethod.advance_within_block(disi, target),
Method::Dense => DenseMethod.advance_within_block(disi, target),
Method::ALL => All.advance_within_block(disi, target),
}
}
fn advance_exact_within_block<I, R>(
&self,
disi: &mut IndexedDISIImpl<I, R>,
target: i32,
) -> Result<bool>
where
I: IndexInput,
R: RandomAccessInput,
{
match self {
Method::Sparse => SparseMethod.advance_exact_within_block(disi, target),
Method::Dense => DenseMethod.advance_exact_within_block(disi, target),
Method::ALL => All.advance_exact_within_block(disi, target),
}
}
}
trait MethodBehavior {
fn advance_within_block<I, R>(
&self,
disi: &mut IndexedDISIImpl<I, R>,
target: i32,
) -> Result<bool>
where
I: IndexInput,
R: RandomAccessInput;
fn advance_exact_within_block<I, R>(
&self,
disi: &mut IndexedDISIImpl<I, R>,
target: i32,
) -> Result<bool>
where
I: IndexInput,
R: RandomAccessInput;
}
struct SparseMethod;
impl MethodBehavior for SparseMethod {
fn advance_within_block<I, R>(
&self,
disi: &mut IndexedDISIImpl<I, R>,
target: i32,
) -> Result<bool>
where
I: IndexInput,
R: RandomAccessInput,
{
let target_in_block = target & 0xFFFF;
let next_block_index = disi.next_block_index;
while disi.index < next_block_index {
let doc = disi.slice.read_short()? as u16 as i32;
disi.index += 1;
if doc >= target_in_block {
disi.doc = disi.block | doc;
disi.exists = true;
disi.next_exist_doc_in_block = doc;
return Ok(true);
}
}
Ok(false)
}
fn advance_exact_within_block<I, R>(
&self,
disi: &mut IndexedDISIImpl<I, R>,
target: i32,
) -> Result<bool>
where
I: IndexInput,
R: RandomAccessInput,
{
let target_in_block = target & 0xFFFF;
if disi.next_exist_doc_in_block > target_in_block {
debug_assert!(!disi.exists);
return Ok(false);
}
if disi.doc == target {
return Ok(disi.exists);
}
let next_block_index = disi.next_block_index;
while disi.index < next_block_index {
let doc = disi.slice.read_short()? as u16 as i32;
disi.index += 1;
if doc >= target_in_block {
disi.next_exist_doc_in_block = doc;
if doc != target_in_block {
disi.index -= 1;
let fp = disi.slice.get_file_pointer()?;
disi.slice.seek(fp - BitUtil::SHORT_BYTES)?;
break;
}
disi.exists = true;
return Ok(true);
}
}
disi.exists = false;
Ok(false)
}
}
struct DenseMethod;
impl MethodBehavior for DenseMethod {
fn advance_within_block<I, R>(
&self,
disi: &mut IndexedDISIImpl<I, R>,
target: i32,
) -> Result<bool>
where
I: IndexInput,
R: RandomAccessInput,
{
let target_in_block = target & 0xFFFF;
let target_word_index = (target_in_block as u32 >> 6) as i32;
if disi.dense_rank_power != -1 && target_word_index - disi.word_index >= disi.dense_rank_words {
rank_skip(disi, target_in_block)?;
}
for _ in disi.word_index + 1..=target_word_index {
disi.word = disi.slice.read_long()?;
disi.number_of_ones += disi.word.count_ones() as i32;
}
disi.word_index = target_word_index;
let left_bits = (disi.word as u64) >> (target_in_block & 63);
if left_bits != 0 {
disi.doc = target + left_bits.trailing_zeros() as i32;
disi.index = disi.number_of_ones - left_bits.count_ones() as i32;
return Ok(true);
}
while {
disi.word_index += 1;
disi.word_index < 1024
} {
disi.word = disi.slice.read_long()?;
if disi.word != 0 {
disi.index = disi.number_of_ones;
disi.number_of_ones += disi.word.count_ones() as i32;
disi.doc = disi.block | ((disi.word_index << 6) | disi.word.trailing_zeros() as i32);
return Ok(true);
}
}
Ok(false)
}
fn advance_exact_within_block<I, R>(
&self,
disi: &mut IndexedDISIImpl<I, R>,
target: i32,
) -> Result<bool>
where
I: IndexInput,
R: RandomAccessInput,
{
let target_in_block = target & 0xFFFF;
let target_word_index = ((target_in_block as u32) >> 6) as i32;
if disi.dense_rank_power != -1 && target_word_index - disi.word_index >= disi.dense_rank_words {
rank_skip(disi, target_in_block)?;
}
for _ in (disi.word_index + 1)..=target_word_index {
disi.word = disi.slice.read_long()?;
disi.number_of_ones += disi.word.count_ones() as i32;
}
disi.word_index = target_word_index;
let left_bits = (disi.word as u64 >> (target_in_block & 63)) as i64;
disi.index = disi.number_of_ones - left_bits.count_ones() as i32;
Ok((left_bits & 1) != 0)
}
}
struct All;
impl MethodBehavior for All {
fn advance_within_block<I, R>(
&self,
disi: &mut IndexedDISIImpl<I, R>,
target: i32,
) -> Result<bool>
where
I: IndexInput,
R: RandomAccessInput,
{
disi.doc = target;
disi.index = target - disi.gap;
Ok(true)
}
fn advance_exact_within_block<I, R>(
&self,
disi: &mut IndexedDISIImpl<I, R>,
target: i32,
) -> Result<bool>
where
I: IndexInput,
R: RandomAccessInput,
{
disi.index = target - disi.gap;
Ok(true)
}
}
pub struct DocIndexIteratorImpl<I>
where
I: IndexInput,
{
pub(crate) disi: IndexedDISIImpl<I::IndexInput, I::RandomAccessSlice>,
}
impl<I> DocIndexIteratorImpl<I>
where
I: IndexInput,
{
pub fn new(disi: IndexedDISIImpl<I::IndexInput, I::RandomAccessSlice>) -> Self {
Self { disi }
}
}
impl<I> crate::core::search::doc_id_set_iterator::DocIdSetIteratorExtensions
for DocIndexIteratorImpl<I>
where
I: IndexInput,
{
}
impl<I> crate::core::search::doc_id_set_iterator::BitSetIteratorAccess for DocIndexIteratorImpl<I> where
I: IndexInput
{
}
impl<I> DocIdSetIterator for DocIndexIteratorImpl<I>
where
I: IndexInput,
{
fn doc_id(&self) -> i32 {
self.disi.doc_id()
}
fn next_doc(&mut self) -> Result<i32> {
self.disi.next_doc()
}
fn advance(&mut self, target: i32) -> Result<i32> {
self.disi.advance(target)
}
fn cost(&self) -> Result<i64> {
self.disi.cost()
}
}
impl<I> DocIndexIterator for DocIndexIteratorImpl<I>
where
I: IndexInput,
{
fn index(&self) -> Result<i32> {
Ok(self.disi.index())
}
}
pub enum IndexedDISIDocIndexIterator<I>
where
I: IndexInput,
{
Dense(DenseDocIndexIterator),
Sparse(DocIndexIteratorImpl<I>),
}
impl<I> crate::core::search::doc_id_set_iterator::DocIdSetIteratorExtensions
for IndexedDISIDocIndexIterator<I>
where
I: IndexInput,
{
}
impl<I> crate::core::search::doc_id_set_iterator::BitSetIteratorAccess
for IndexedDISIDocIndexIterator<I>
where
I: IndexInput,
{
}
impl<I> DocIdSetIterator for IndexedDISIDocIndexIterator<I>
where
I: IndexInput,
{
fn doc_id(&self) -> i32 {
match self {
Self::Dense(iterator) => iterator.doc_id(),
Self::Sparse(iterator) => iterator.doc_id(),
}
}
fn next_doc(&mut self) -> Result<i32> {
match self {
Self::Dense(iterator) => iterator.next_doc(),
Self::Sparse(iterator) => iterator.next_doc(),
}
}
fn advance(&mut self, target: i32) -> Result<i32> {
match self {
Self::Dense(iterator) => iterator.advance(target),
Self::Sparse(iterator) => iterator.advance(target),
}
}
fn slow_advance(&mut self, target: i32) -> Result<i32> {
match self {
Self::Dense(iterator) => iterator.slow_advance(target),
Self::Sparse(iterator) => iterator.slow_advance(target),
}
}
fn cost(&self) -> Result<i64> {
match self {
Self::Dense(iterator) => iterator.cost(),
Self::Sparse(iterator) => iterator.cost(),
}
}
}
impl<I> DocIndexIterator for IndexedDISIDocIndexIterator<I>
where
I: IndexInput,
{
fn index(&self) -> Result<i32> {
match self {
Self::Dense(iterator) => iterator.index(),
Self::Sparse(iterator) => iterator.index(),
}
}
}
pub trait IndexedDISIPolicy<I>
where
I: IndexInput,
{
type Slice: IndexInput;
type JumpTable: RandomAccessInput;
}
pub struct Owned;
pub struct Shared;
pub struct IndexInputImpl<I> {
input: Arc<Mutex<I>>,
offset: usize,
}
impl<I> IndexInputImpl<I> {
pub fn new(input: Arc<Mutex<I>>) -> Self {
Self { input, offset: 0 }
}
}
impl<I> crate::core::util::close::CloseableRef for IndexInputImpl<I> {}
impl<I> DataInput for IndexInputImpl<I>
where
I: IndexInput,
{
fn read_byte(&mut self) -> Result<u8> {
Err(LuceneError::unsupported_operation("Unused by IndexedDISI"))
}
fn get_bytes(&mut self, len: usize) -> Result<std::borrow::Cow<'_, [u8]>> {
let mut bytes = vec![0; len];
self.read_bytes(&mut bytes, 0, len)?;
Ok(std::borrow::Cow::Owned(bytes))
}
fn read_bytes(&mut self, b: &mut [u8], offset: usize, len: usize) -> Result<()> {
let mut input = self.input.lock();
input.seek(self.offset)?;
self.offset += len;
input.read_bytes(b, offset, len)
}
fn read_short(&mut self) -> Result<i16> {
let mut input = self.input.lock();
input.seek(self.offset)?;
self.offset += BitUtil::SHORT_BYTES;
input.read_short()
}
fn read_long(&mut self) -> Result<i64> {
let mut input = self.input.lock();
input.seek(self.offset)?;
self.offset += BitUtil::LONG_BYTES;
input.read_long()
}
fn read_group_vint(&mut self, dst: &mut [i32], offset: usize) -> Result<()> {
crate::core::util::group_vint_util::GroupVIntUtil::read_group_vint_i32(self, dst, offset)
}
fn skip_bytes(&mut self, num_bytes: i64) -> Result<()> {
IndexInput::skip_bytes(self, num_bytes)
}
}
impl<I> DataInputExt for IndexInputImpl<I>
where
I: IndexInput,
{
crate::core::store::data_input_ext::impl_index_input_ext!();
}
impl<I> std::fmt::Display for IndexInputImpl<I> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "docs")
}
}
impl<I> crate::core::util::clone::TryClone for IndexInputImpl<I> {
fn try_clone(&self) -> Result<Self> {
Ok(Self {
input: Arc::clone(&self.input),
offset: self.offset,
})
}
}
impl<I> IndexInput for IndexInputImpl<I>
where
I: IndexInput,
{
type IndexInput = Self;
fn get_file_pointer(&self) -> Result<usize> {
Ok(self.offset)
}
fn seek(&mut self, pos: usize) -> Result<()> {
self.offset = pos;
Ok(())
}
fn length(&self) -> Result<usize> {
self.input.lock().length()
}
type RandomAccessSlice = DummyRandomAccessInput;
fn random_access_slice(&self, _offset: usize, _length: usize) -> Result<Self::RandomAccessSlice> {
Err(LuceneError::unsupported_operation("Unused by IndexedDISI"))
}
fn prefetch(&self, _pos: usize, _len: usize) -> Result<()> {
Ok(())
}
}
impl<R> RandomAccessInput for Arc<R>
where
R: RandomAccessInput,
{
fn length(&self) -> Result<usize> {
self.as_ref().length()
}
#[inline]
fn read_byte(&self, pos: usize) -> Result<u8> {
self.as_ref().read_byte(pos)
}
fn read_bytes(&self, pos: usize, len: usize) -> Result<std::borrow::Cow<'_, [u8]>> {
self.as_ref().read_bytes(pos, len)
}
fn read_short(&self, pos: usize) -> Result<i16> {
self.as_ref().read_short(pos)
}
fn read_int(&self, pos: usize) -> Result<i32> {
self.as_ref().read_int(pos)
}
fn read_long(&self, pos: usize) -> Result<i64> {
self.as_ref().read_long(pos)
}
fn prefetch(&self, pos: usize, len: usize) -> Result<()> {
self.as_ref().prefetch(pos, len)
}
}
impl<I> IndexedDISIPolicy<I> for Owned
where
I: IndexInput,
{
type Slice = I::IndexInput;
type JumpTable = I::RandomAccessSlice;
}
impl<I> IndexedDISIPolicy<I> for Shared
where
I: IndexInput,
{
type Slice = IndexInputImpl<I::IndexInput>;
type JumpTable = Arc<I::RandomAccessSlice>;
}
use crate::core::search::doc_id_set_iterator::NO_MORE_DOCS;
use crate::core::util::TryIntoInt;
use crate::core::util::array_util::ArrayUtil;
use crate::core::util::bit_set::BitSet;
use crate::core::util::bit_set_iterator::BitSetIterator;
use crate::core::util::fixed_bit_set::FixedBitSet;
const BLOCK_SIZE: i32 = 65536;
const DENSE_BLOCK_LONGS: usize = BLOCK_SIZE as usize / i64::BITS as usize;
pub const DEFAULT_DENSE_RANK_POWER: i8 = 9;
pub(crate) const MAX_ARRAY_LENGTH: i32 = (1 << 12) - 1;
#[allow(dead_code)]
pub(crate) fn write_bitset<O, I>(it: &mut I, out: &mut O) -> Result<i16>
where
O: IndexOutput,
I: DocIdSetIterator,
{
write_bitset_with_dense_rank_power(it, out, DEFAULT_DENSE_RANK_POWER)
}
pub fn write_bitset_with_dense_rank_power<O, I>(
it: &mut I,
out: &mut O,
dense_rank_power: i8,
) -> Result<i16>
where
O: IndexOutput,
I: DocIdSetIterator,
{
let origo = out.get_file_pointer()?;
if !(7..=15).contains(&dense_rank_power) && dense_rank_power != -1 {
return Err(LuceneError::illegal_argument(format!(
"Acceptable values for denseRankPower are 7-15 (every 128-32768 docIDs). \
The provided power was {} (every {} docIDs)",
dense_rank_power,
2_f64.powi(dense_rank_power as i32) as i32
)));
}
let mut total_cardinality = 0;
let mut block_cardinality = 0;
let jumps_len = ArrayUtil::oversize(1, BitUtil::INT_BYTES * 2)?;
let mut jumps: smallvec::SmallVec<[i32; 4]> = smallvec::smallvec![0; jumps_len];
let mut prev_doc = -1;
let mut jump_block_index = 0;
let mut doc = it.next_doc()?;
let mut buffer = FixedBitSet::new(if doc == NO_MORE_DOCS {
0
} else {
BLOCK_SIZE as usize
});
let mut first_in_block = (doc & 0xFFFF) as usize;
while doc != NO_MORE_DOCS {
let prev_block = prev_doc >> 16;
if prev_block != -1 && doc >> 16 != prev_block {
add_jumps(
&mut jumps,
out.get_file_pointer()? - origo,
total_cardinality,
jump_block_index,
(prev_block + 1) as usize,
)?;
jump_block_index = (prev_block + 1) as usize;
buffer = flush(prev_block, buffer, block_cardinality, dense_rank_power, out)?;
let start = first_in_block & !63;
let end = ((prev_doc & 0xFFFF) as usize | 63) + 1;
if start == 0 && end == BLOCK_SIZE as usize {
buffer.clear()?;
} else {
buffer.clear_range(start, end)?;
}
first_in_block = (doc & 0xFFFF) as usize;
total_cardinality += block_cardinality;
block_cardinality = 0;
}
buffer.set((doc & 0xFFFF).try_convert()?)?;
block_cardinality += 1;
prev_doc = doc;
doc = it.next_doc()?;
}
let mut prev_block = prev_doc >> 16;
if block_cardinality > 0 {
add_jumps(
&mut jumps,
out.get_file_pointer()? - origo,
total_cardinality,
jump_block_index,
(prev_block + 1) as usize,
)?;
total_cardinality += block_cardinality;
let _ = flush(prev_block, buffer, block_cardinality, dense_rank_power, out)?;
prev_block += 1;
}
let last_block: usize = if prev_block == -1 {
0
} else {
prev_block as usize
};
add_jumps(
&mut jumps,
out.get_file_pointer()? - origo,
total_cardinality,
last_block,
last_block + 1,
)?;
out.write_short((NO_MORE_DOCS >> 16) as i16)?;
out.write_short(0)?; out.write_short((NO_MORE_DOCS & 0xFFFF) as i16)?;
flush_block_jumps(&jumps, last_block + 1, out)
}
pub fn create_block_slice<I>(
slice: &I,
slice_description: &str,
offset: usize,
length: usize,
jump_table_entry_count: i32,
) -> Result<I::IndexInput>
where
I: IndexInput,
{
let jump_table_bytes = if jump_table_entry_count < 0 {
0
} else {
jump_table_entry_count as usize * BitUtil::INT_BYTES * 2
};
slice.slice(slice_description, offset, length - jump_table_bytes)
}
pub fn create_jump_table<I>(
slice: &I,
offset: usize,
length: usize,
jump_table_entry_count: i32,
) -> Result<Option<I::RandomAccessSlice>>
where
I: IndexInput,
{
if jump_table_entry_count <= 0 {
Ok(None)
} else {
let jump_table_bytes = jump_table_entry_count as usize * BitUtil::INT_BYTES * 2;
slice
.random_access_slice(offset + length - jump_table_bytes, jump_table_bytes)
.map(Some)
}
}
fn flush<O>(
block: i32,
mut buffer: FixedBitSet,
cardinality: i32,
dense_rank_power: i8,
out: &mut O,
) -> Result<FixedBitSet>
where
O: IndexOutput,
{
debug_assert!((0..BLOCK_SIZE).contains(&block));
out.write_short(block as i16)?;
debug_assert!(cardinality > 0 && cardinality <= BLOCK_SIZE);
out.write_short((cardinality - 1) as i16)?;
if cardinality > MAX_ARRAY_LENGTH {
if cardinality != BLOCK_SIZE {
if dense_rank_power != -1 {
let (rank, rank_len) = create_rank(&buffer, dense_rank_power as u8);
debug_assert!(rank_len <= i32::MAX as usize);
out.write_bytes_with_len(&rank[..rank_len], rank_len)?;
}
for word in buffer.get_bits() {
out.write_long(*word)?;
}
}
} else if cardinality > DENSE_BLOCK_LONGS as i32 && cardinality <= 2 * DENSE_BLOCK_LONGS as i32 {
write_sparse_simd(buffer.get_bits(), out)?;
} else {
let mut iter = BitSetIterator::new(buffer, cardinality as i64)?;
let mut doc = iter.next_doc()?;
if cardinality <= 3 * DENSE_BLOCK_LONGS as i32 / 4 {
while doc != NO_MORE_DOCS {
out.write_short(doc as i16)?;
doc = iter.next_doc()?;
}
} else {
while doc != NO_MORE_DOCS {
let word_index = (doc as usize) >> 6;
let mut word = iter.bits.get_bits()[word_index] as u64;
loop {
out.write_short(doc as i16)?;
word &= word - 1;
if word == 0 {
break;
}
doc = ((word_index << 6) + word.trailing_zeros() as usize) as i32;
}
iter.set_doc_id(doc | 63);
doc = iter.next_doc()?;
}
}
buffer = iter.bits
}
Ok(buffer)
}
#[inline]
fn write_sparse_simd<O>(bits: &[i64], out: &mut O) -> Result<()>
where
O: IndexOutput,
{
for (group, &words) in bits.as_chunks::<4>().0.iter().enumerate() {
let mut nonempty = wide::i64x4::new(words)
.simd_ne(wide::i64x4::ZERO)
.to_bitmask();
if nonempty == 0b1111 {
for (lane, &word) in words.iter().enumerate() {
let doc_base = (group * 4 + lane) * 64;
let mut word = word as u64;
loop {
let doc = doc_base + word.trailing_zeros() as usize;
out.write_short(doc as i16)?;
word &= word - 1;
if word == 0 {
break;
}
}
}
continue;
}
while nonempty != 0 {
let lane = nonempty.trailing_zeros() as usize;
nonempty &= nonempty - 1;
let doc_base = (group * 4 + lane) * 64;
let mut word = words[lane] as u64;
while word != 0 {
let doc = doc_base + word.trailing_zeros() as usize;
out.write_short(doc as i16)?;
word &= word - 1;
}
}
}
Ok(())
}
fn create_rank(buffer: &FixedBitSet, dense_rank_power: u8) -> ([u8; DENSE_BLOCK_LONGS], usize) {
let longs_per_rank = 1 << (dense_rank_power - 6);
let rank_mark = longs_per_rank - 1;
let rank_index_shift = dense_rank_power - 7;
let rank_len = DENSE_BLOCK_LONGS >> rank_index_shift;
let mut rank = [0u8; DENSE_BLOCK_LONGS];
let bits = buffer.get_bits();
let mut bit_count = 0;
if dense_rank_power == 9 && bits.len() >= DENSE_BLOCK_LONGS {
for (entry, words) in rank[..rank_len]
.as_chunks_mut::<2>()
.0
.iter_mut()
.zip(bits[..DENSE_BLOCK_LONGS].as_chunks::<8>().0)
{
entry[0] = (bit_count >> 8) as u8;
entry[1] = (bit_count & 0xFF) as u8;
let [a, b, c, d]: [[u8; 16]; 4] = wide::bytemuck::cast(*words);
let popcounts = |bytes: [u8; 16]| wide::u8x16::new(bytes.map(|byte| byte.count_ones() as u8));
let counts = popcounts(a) + popcounts(b) + popcounts(c) + popcounts(d);
let totals = wide::u16x8::from_u8x16_low(counts) + wide::u16x8::from_u8x16_high(counts);
bit_count += i32::from(totals.reduce_add());
}
} else if bits.len() >= DENSE_BLOCK_LONGS {
let entries = rank[..rank_len].as_chunks_mut::<2>().0;
for (entry, words) in entries
.iter_mut()
.zip(bits[..DENSE_BLOCK_LONGS].chunks_exact(longs_per_rank))
{
*entry = (bit_count as u16).to_be_bytes();
for group in words.as_chunks::<2>().0.chunks(16) {
let mut counts = wide::u8x16::ZERO;
for &pair in group {
let bytes: [u8; 16] = wide::bytemuck::cast(pair);
counts += wide::u8x16::new(bytes.map(|byte| byte.count_ones() as u8));
}
let totals = wide::u16x8::from_u8x16_low(counts) + wide::u16x8::from_u8x16_high(counts);
bit_count += i32::from(totals.reduce_add());
}
}
} else {
for (word, b) in bits.iter().take(DENSE_BLOCK_LONGS).enumerate() {
if (word & rank_mark) == 0 {
let rank_index = word >> rank_index_shift;
rank[rank_index] = (bit_count >> 8) as u8;
rank[rank_index + 1] = (bit_count & 0xFF) as u8;
}
bit_count += b.count_ones() as i32;
}
}
(rank, rank_len)
}
fn add_jumps(
jumps: &mut smallvec::SmallVec<[i32; 4]>,
offset: usize,
index: i32,
start_block: usize,
end_block: usize,
) -> Result<()> {
debug_assert!(
offset < i32::MAX as usize,
"Logically the offset should not exceed 2^30 but was >= i32::MAX"
);
let required = end_block * 2;
if jumps.len() < required {
ArrayUtil::oversize(required, std::mem::size_of::<i32>())?;
if jumps.capacity() < required {
let capacity = required.max(jumps.capacity() * 2);
jumps.reserve_exact(capacity - jumps.len());
}
jumps.resize(required, 0);
}
if start_block < end_block {
let entries = &mut jumps[start_block * 2..end_block * 2];
if entries.len() == 2 {
entries[0] = index;
entries[1] = offset as i32;
} else {
entries.as_chunks_mut::<2>().0.fill([index, offset as i32]);
}
}
Ok(())
}
fn flush_block_jumps<O>(jumps: &[i32], mut block_count: usize, out: &mut O) -> Result<i16>
where
O: IndexOutput,
{
if block_count == 2 {
block_count = 0;
}
for entries in jumps[..block_count * 2].chunks(32) {
out.write_ints(entries)?;
}
Ok(block_count as i16)
}
fn rank_skip<I, R>(disi: &mut IndexedDISIImpl<I, R>, target_in_block: i32) -> Result<()>
where
I: IndexInput,
R: RandomAccessInput,
{
debug_assert!(
disi.dense_rank_power >= 0,
"dense_rank_power = {}",
disi.dense_rank_power
);
let rank_index = target_in_block >> disi.dense_rank_power; let byte_index = (rank_index << 1) as usize;
let mut rank = 0;
match &disi.dense_rank_table {
None => {
Err::<(), LuceneError>(LuceneError::unreachable(""))?;
},
Some(rank_table) => {
let rank_table: &[u8] = rank_table;
let high = rank_table[byte_index] as u16;
let low = rank_table[byte_index + 1] as u16;
rank = ((high << 8) | low) as i32;
},
}
let rank_aligned_word_index = (rank_index << disi.dense_rank_power) >> 6;
let offset = disi
.dense_bitmap_offset
.ok_or_else(|| LuceneError::illegal_state("dense bitmap offset is not initialized"))?
+ rank_aligned_word_index as usize * BitUtil::LONG_BYTES;
disi.slice.seek(offset)?;
let rank_word = disi.slice.read_long()?;
let dense_noo = rank + rank_word.count_ones() as i32;
disi.word_index = rank_aligned_word_index;
disi.word = rank_word;
disi.number_of_ones = disi.dense_origo_index + dense_noo;
Ok(())
}
pub fn get_doc_index_iterator<I>(
disi: IndexedDISIImpl<I::IndexInput, I::RandomAccessSlice>,
) -> DocIndexIteratorImpl<I>
where
I: IndexInput,
{
DocIndexIteratorImpl::new(disi)
}