use std::borrow::{Borrow, Cow};
use crate::core::index::{BytesRef, BytesRefBuilder, BytesRefValueEnum};
use crate::core::util::access::ByteSource;
use crate::core::util::accountable::Accountable;
use crate::core::util::allocator_byte::DirectTrackingAllocatorByte;
use crate::core::util::array_util::ArrayUtil;
use crate::core::util::byte_block_pool::{BYTE_BLOCK_MASK, BYTE_BLOCK_SHIFT, BYTE_BLOCK_SIZE};
use crate::core::util::error::lucene_error::{LuceneError, Result};
use crate::core::util::ram_usage_estimator::size_of_array_capacity;
use crate::core::util::sortable_bytes_ref_array::SortableBytesRefArray;
use crate::core::util::{
ByteBlockPool, BytesRefComparator, Counter, MSBRadixSorterBase, SharedCounter, SliceCopyOps,
Sorter, StableStringSorter, StableStringSorterBase, StringSorter, StringSorterBase, TryIntoInt,
};
#[derive(Debug)]
pub struct BytesRefArray {
storage: ByteStorage,
offsets: smallvec::SmallVec<[usize; 1]>,
last_element: usize,
current_offset: usize,
byte_used: SharedCounter,
}
#[derive(Debug)]
enum ByteStorage {
Blocks(Box<ByteBlockPool>),
Compact(Vec<u8>),
}
impl BytesRefArray {
pub fn new(byte_used: SharedCounter) -> Result<BytesRefArray> {
let allocator = DirectTrackingAllocatorByte::new(byte_used.clone());
byte_used.add_and_get(size_of::<ByteBlockPool>() as i64);
let storage = ByteStorage::Blocks(Box::new(ByteBlockPool::new(allocator)));
Ok(Self::with_storage(byte_used, storage))
}
pub(crate) fn new_compact(byte_used: SharedCounter) -> Self {
Self::with_storage(byte_used, ByteStorage::Compact(Vec::new()))
}
fn with_storage(byte_used: SharedCounter, storage: ByteStorage) -> Self {
let offsets = smallvec::SmallVec::with_capacity(1);
byte_used.add_and_get(size_of_array_capacity::<usize>(offsets.capacity()));
Self {
storage,
offsets,
last_element: 0,
current_offset: 0,
byte_used,
}
}
pub fn get(&self, index: usize) -> Result<BytesRefValueEnum<'_>> {
if index >= self.last_element {
return Err(LuceneError::array_index_out_of_bounds(format!(
"index: {}, last_element: {}",
index, self.last_element
)));
}
let offset = self.offsets[index];
let length = if index == self.last_element - 1 {
self.current_offset - offset
} else {
self.offsets[index + 1] - offset
};
if length == 0 {
return Ok(BytesRefValueEnum::Slice(BytesRef {
bytes: &[],
offset: 0,
length: 0,
}));
}
let pool = match &self.storage {
ByteStorage::Compact(bytes) => {
return Ok(BytesRefValueEnum::Slice(BytesRef {
bytes: &bytes[offset..offset + length],
offset: 0,
length,
}));
},
ByteStorage::Blocks(pool) => pool,
};
let block_index = offset >> BYTE_BLOCK_SHIFT;
let block_offset = offset & BYTE_BLOCK_MASK as usize;
if length <= BYTE_BLOCK_SIZE as usize - block_offset {
return Ok(BytesRefValueEnum::Slice(BytesRef {
bytes: &pool.get_buffer(block_index)[block_offset..block_offset + length],
offset: 0,
length,
}));
}
ArrayUtil::oversize(length, size_of::<u8>())?;
let mut bytes = Vec::with_capacity(length);
let buffer_index: i32 = ((offset as i64) >> BYTE_BLOCK_SHIFT).try_convert()?;
let mut buffer_index = buffer_index as usize;
let mut pos = (offset as i64 & BYTE_BLOCK_MASK as i64) as usize;
let mut remaining = length;
while remaining > 0 {
let chunk = std::cmp::min(BYTE_BLOCK_SIZE as usize - pos, remaining);
bytes.extend_from_slice(&pool.get_buffer(buffer_index)[pos..pos + chunk]);
remaining -= chunk;
buffer_index += 1;
pos = 0;
}
Ok(BytesRefValueEnum::Buffer(Cow::Owned(BytesRef {
bytes,
offset: 0,
length,
})))
}
#[allow(
clippy::owned_cow,
reason = "Matches ByteBlockPool's Vec carrier, which preserves reusable cross-block capacity"
)]
fn set_bytes_ref<'a>(
&'a self,
spare: &mut BytesRefBuilder<Vec<u8>>,
result: &mut BytesRef<Cow<'a, Vec<u8>>>,
index: usize,
) -> Result<()> {
if index >= self.last_element {
return Err(LuceneError::array_index_out_of_bounds(format!(
"index: {}, last_element: {}",
index, self.last_element
)));
}
let offset = self.offsets[index];
let length = if index == self.last_element - 1 {
self.current_offset - offset
} else {
self.offsets[index + 1] - offset
};
match &self.storage {
ByteStorage::Compact(bytes) => {
result.bytes = Cow::Borrowed(bytes);
result.offset = offset;
result.length = length;
},
ByteStorage::Blocks(pool) => pool.set_bytes_ref(spare, result, offset as i64, length)?,
}
Ok(())
}
pub fn sort<'a, C>(&'a self, comp: C, stable: bool) -> Result<SortState>
where
C: BytesRefComparator<Cow<'a, Vec<u8>>>,
{
let size = self.size();
let mut indices = (size > 1).then(|| (0..size).collect::<smallvec::SmallVec<_>>());
let mut identity = [0];
let ordered_entries = indices
.as_deref_mut()
.unwrap_or(&mut identity[..size.min(1)]);
if stable {
let delegate = StableStringSorterImpl {
tmp: Vec::new(),
ordered_entries,
bytes_ref_array: self,
};
let stable_string_sorter = StableStringSorter::new(delegate);
let mut string_sorter = StringSorter::new(stable_string_sorter, comp);
string_sorter.sort(0, size)?;
} else {
let delegate = StringSorterImpl {
ordered_entries,
bytes_ref_array: self,
};
let mut string_sorter = StringSorter::new(delegate, comp);
string_sorter.sort(0, size)?;
}
Ok(SortState::new(indices))
}
pub fn iterator(&'_ self) -> IndexedBytesRefIteratorImpl<'_> {
IndexedBytesRefIteratorImpl::new(None, self)
}
pub fn iterator_with_state<S: Borrow<SortState>>(
&self,
sort_state: S,
) -> IndexedBytesRefIteratorImpl<'_, S> {
IndexedBytesRefIteratorImpl::new(Some(sort_state), self)
}
}
impl<'a> SortableBytesRefArray<'a> for BytesRefArray {
fn append<AV: ByteSource>(&mut self, bytes: &BytesRef<AV>) -> Result<usize> {
let view = bytes.as_byte_slice();
if self.offsets.len() == self.offsets.capacity() {
let old_size = size_of_array_capacity::<usize>(self.offsets.capacity());
let min_size = self.offsets.len() + 1;
ArrayUtil::oversize(min_size, size_of::<usize>())?;
let capacity = min_size.max(self.offsets.capacity() * 2).max(4);
self.offsets.reserve_exact(capacity - self.offsets.len());
self
.byte_used
.add_and_get(size_of_array_capacity::<usize>(self.offsets.capacity()) - old_size);
}
match &mut self.storage {
ByteStorage::Compact(bytes) => {
let end = bytes
.len()
.checked_add(view.len())
.filter(|&end| i32::try_from(end).is_ok());
if end.is_none() {
return Err(LuceneError::number_overflow(
"Overflow when calculating byte offset.",
));
}
let old_capacity = bytes.capacity();
bytes.extend_from_slice(view);
if bytes.capacity() != old_capacity {
self.byte_used.add_and_get(
size_of_array_capacity::<u8>(bytes.capacity())
- if old_capacity == 0 {
0
} else {
size_of_array_capacity::<u8>(old_capacity)
},
);
}
},
ByteStorage::Blocks(pool) => {
if pool.buffer_upto.is_none() {
pool.next_buffer()?;
}
pool.append(view)?;
},
}
self.offsets.push(self.current_offset);
self.last_element += 1;
self.current_offset += view.len();
Ok(self.last_element - 1)
}
fn clear(&mut self) {
self.last_element = 0;
self.current_offset = 0;
self.offsets.clear();
match &mut self.storage {
ByteStorage::Compact(bytes) => bytes.clear(),
ByteStorage::Blocks(pool) => pool.reset(false, true),
}
}
fn size(&self) -> usize {
self.last_element
}
type Iter = IndexedBytesRefIteratorImpl<'a>;
fn iterator<C>(&'a self, comp: C) -> Result<Self::Iter>
where
C: BytesRefComparator<Cow<'a, Vec<u8>>>,
{
let ords = self.sort(comp, false)?;
Ok(self.iterator_with_state(ords))
}
}
#[derive(Clone, Debug)]
pub struct SortState {
pub(crate) indices: Option<smallvec::SmallVec<[usize; 4]>>,
}
impl SortState {
fn new(indices: Option<smallvec::SmallVec<[usize; 4]>>) -> SortState {
SortState { indices }
}
}
impl Accountable for SortState {
fn ram_bytes_used(&self) -> Result<i64> {
Ok(
self
.indices
.as_ref()
.filter(|indices| indices.spilled())
.map_or(0, |indices| {
size_of_array_capacity::<usize>(indices.capacity())
}),
)
}
}
pub struct IndexedBytesRefIteratorImpl<'a, S = SortState> {
pos: usize,
pub(crate) ord: usize,
sort_state: Option<S>,
size: usize,
bytes_ref_array: &'a BytesRefArray,
result: BytesRef<Vec<u8>>,
}
impl<'a, S: Borrow<SortState>> IndexedBytesRefIteratorImpl<'a, S> {
pub(crate) fn new(
sort_state: Option<S>,
bytes_ref_array: &'a BytesRefArray,
) -> IndexedBytesRefIteratorImpl<'a, S> {
if let Some(indices) = sort_state
.as_ref()
.and_then(|state| state.borrow().indices.as_ref())
{
debug_assert_eq!(indices.len(), bytes_ref_array.size());
}
Self {
pos: 0,
ord: 0,
sort_state,
size: bytes_ref_array.size(),
bytes_ref_array,
result: BytesRef::new(),
}
}
}
impl<S: Borrow<SortState>> IndexedBytesRefIterator for IndexedBytesRefIteratorImpl<'_, S> {
fn next(&mut self) -> Result<Option<(usize, BytesRefValueEnum<'_>)>> {
if self.pos < self.size {
self.ord = match self
.sort_state
.as_ref()
.and_then(|state| state.borrow().indices.as_ref())
{
None => self.pos,
Some(indices) => indices[self.pos],
};
let array = self.bytes_ref_array;
if self.ord >= array.last_element {
return Err(LuceneError::array_index_out_of_bounds(format!(
"index: {}, last_element: {}",
self.ord, array.last_element
)));
}
let offset = array.offsets[self.ord];
let length = if self.ord == array.last_element - 1 {
array.current_offset - offset
} else {
array.offsets[self.ord + 1] - offset
};
if self.result.bytes.len() < length {
ArrayUtil::oversize(length, size_of::<u8>())?;
}
let pool = match &array.storage {
ByteStorage::Compact(bytes) => {
self.pos += 1;
let value = BytesRef {
bytes: &bytes[offset..offset + length],
offset: 0,
length,
};
return Ok(Some((self.ord, BytesRefValueEnum::Slice(value))));
},
ByteStorage::Blocks(pool) => pool,
};
let offset = offset as i64;
let pos = (offset & BYTE_BLOCK_MASK as i64) as usize;
if pos + length > BYTE_BLOCK_SIZE as usize {
ArrayUtil::grow_no_copy(&mut self.result.bytes, length, || 0)?;
}
self.result.length = length;
let buffer_index: i32 = (offset >> BYTE_BLOCK_SHIFT).try_convert()?;
let value = if pos + length <= BYTE_BLOCK_SIZE as usize {
let bytes = &pool.get_buffer(buffer_index as usize)[pos..pos + length];
self.result.offset = 0;
BytesRefValueEnum::Slice(BytesRef {
bytes,
offset: 0,
length,
})
} else {
self.result.offset = 0;
pool.read_bytes(offset, &mut self.result.bytes, 0, length)?;
BytesRefValueEnum::Buffer(Cow::Borrowed(&self.result))
};
self.pos += 1;
Ok(Some((self.ord, value)))
} else {
Ok(None)
}
}
fn ord(&self) -> usize {
self.ord
}
}
pub trait IndexedBytesRefIterator {
fn next(&mut self) -> Result<Option<(usize, BytesRefValueEnum<'_>)>>;
fn ord(&self) -> usize;
}
struct StableStringSorterImpl<'a, 'o> {
tmp: Vec<usize>,
ordered_entries: &'o mut [usize],
bytes_ref_array: &'a BytesRefArray,
}
impl Sorter for StableStringSorterImpl<'_, '_> {
fn swap(&mut self, i: usize, j: usize) -> Result<()> {
self.ordered_entries.swap(i, j);
Ok(())
}
}
impl<'a> StringSorterBase for StableStringSorterImpl<'a, '_> {
type Bytes = Cow<'a, Vec<u8>>;
fn get(
&mut self,
builder: &mut BytesRefBuilder<Vec<u8>>,
result: &mut BytesRef<Cow<'a, Vec<u8>>>,
i: usize,
) -> Result<()> {
self
.bytes_ref_array
.set_bytes_ref(builder, result, self.ordered_entries[i])
}
}
impl StableStringSorterBase for StableStringSorterImpl<'_, '_> {
fn save(&mut self, i: usize, j: usize) {
let value = self.ordered_entries[i];
if self.tmp.is_empty() {
self.tmp = vec![0; self.ordered_entries.len()];
}
self.tmp[j] = value;
}
fn restore(&mut self, i: usize, j: usize) {
self.ordered_entries.copy_from(&self.tmp[i..j], i);
}
}
impl MSBRadixSorterBase for StableStringSorterImpl<'_, '_> {}
struct StringSorterImpl<'a, 'o> {
ordered_entries: &'o mut [usize],
bytes_ref_array: &'a BytesRefArray,
}
impl Sorter for StringSorterImpl<'_, '_> {
fn swap(&mut self, i: usize, j: usize) -> Result<()> {
self.ordered_entries.swap(i, j);
Ok(())
}
}
impl<'a> StringSorterBase for StringSorterImpl<'a, '_> {
type Bytes = Cow<'a, Vec<u8>>;
fn get(
&mut self,
builder: &mut BytesRefBuilder<Vec<u8>>,
result: &mut BytesRef<Cow<'a, Vec<u8>>>,
i: usize,
) -> Result<()> {
self
.bytes_ref_array
.set_bytes_ref(builder, result, self.ordered_entries[i])
}
}