#[cfg(test)]
use std::collections::HashMap;
use std::hash::{BuildHasher, Hash, Hasher};
use crate::hashutil::{StableBuildHasher, TableBuildHasher, string_hash};
use crate::id::{LuaFault, ObjectId};
use crate::value::{LightDomain, Value};
pub(crate) const SORTED_KEY_ERROR: &str =
"sorted iteration profile does not support identity-bearing keys";
#[derive(Clone, Copy, Debug)]
pub(crate) enum SortedNextError {
InvalidKey,
UnsupportedKey,
}
pub(crate) type SortedNext = Result<Option<(Value, Value)>, SortedNextError>;
fn sorted_key_cmp(a: KeyView<'_>, b: KeyView<'_>) -> Option<std::cmp::Ordering> {
use KeyView::*;
use std::cmp::Ordering;
let rank = |key| match key {
Bool(_) => Some(0),
Integer(_) | Float(_) => Some(1),
String(_, _) => Some(2),
_ => None,
};
let ranks = rank(a)?.cmp(&rank(b)?);
if ranks != Ordering::Equal {
return Some(ranks);
}
Some(match (a, b) {
(Bool(a), Bool(b)) => a.cmp(&b),
(String(a, _), String(b, _)) => a.cmp(b),
_ => {
let number = |key| match key {
Integer(i) => crate::value::Value::Integer(i),
Float(f) => crate::value::Value::Float(f64::from_bits(f)),
_ => crate::value::Value::Nil,
};
let a = number(a);
let b = number(b);
if crate::compare::numbers_only(crate::opcode::CmpKind::Lt, a, b)? {
Ordering::Less
} else if crate::compare::numbers_only(crate::opcode::CmpKind::Lt, b, a)? {
Ordering::Greater
} else {
Ordering::Equal
}
}
})
}
#[derive(Clone, Debug)]
pub(crate) struct KeyString(std::rc::Rc<KeyBytes>);
#[derive(Debug)]
struct KeyBytes {
bytes: Vec<u8>,
hash: u64,
}
impl KeyString {
pub(crate) fn new(bytes: Vec<u8>) -> Self {
let hash = string_hash(&bytes);
Self(std::rc::Rc::new(KeyBytes { bytes, hash }))
}
fn copied(bytes: &[u8], hash: u64) -> Self {
Self(std::rc::Rc::new(KeyBytes {
bytes: bytes.to_vec(),
hash,
}))
}
pub(crate) fn hash(&self) -> u64 {
self.0.hash
}
#[inline(always)]
fn parts(&self) -> (&[u8], u64) {
(self.bytes(), self.hash())
}
#[inline]
pub(crate) fn bytes(&self) -> &[u8] {
&self.0.bytes
}
pub(crate) fn as_slice(&self) -> &[u8] {
self.bytes()
}
#[inline(always)]
fn matches_name(&self, name: &[u8], hash: u64) -> bool {
self.hash() == hash && name_bytes_eq(self.bytes(), name)
}
}
impl std::ops::Deref for KeyString {
type Target = [u8];
fn deref(&self) -> &[u8] {
self.bytes()
}
}
#[inline(always)]
fn name_bytes_eq(a: &[u8], b: &[u8]) -> bool {
let len = a.len();
if len != b.len() {
return false;
}
match len {
0 => true,
1 => a[0] == b[0],
2..=3 => {
u16::from_ne_bytes(a[..2].try_into().unwrap())
== u16::from_ne_bytes(b[..2].try_into().unwrap())
&& a[len - 1] == b[len - 1]
}
4..=7 => {
u32::from_ne_bytes(a[..4].try_into().unwrap())
== u32::from_ne_bytes(b[..4].try_into().unwrap())
&& u32::from_ne_bytes(a[len - 4..].try_into().unwrap())
== u32::from_ne_bytes(b[len - 4..].try_into().unwrap())
}
8..=16 => {
u64::from_ne_bytes(a[..8].try_into().unwrap())
== u64::from_ne_bytes(b[..8].try_into().unwrap())
&& u64::from_ne_bytes(a[len - 8..].try_into().unwrap())
== u64::from_ne_bytes(b[len - 8..].try_into().unwrap())
}
_ => a == b,
}
}
#[derive(Clone, Debug)]
pub(crate) enum TableKey {
Bool(bool),
Integer(i64),
Float(u64),
String(KeyString),
Object(ObjectId),
Native(u32),
Light(LightDomain, u64),
}
#[derive(Clone, Copy, Eq, Debug)]
pub(crate) enum KeyView<'a> {
Bool(bool),
Integer(i64),
Float(u64),
String(&'a [u8], u64),
Object(ObjectId),
Native(u32),
Light(LightDomain, u64),
}
impl PartialEq for KeyView<'_> {
#[inline]
fn eq(&self, other: &Self) -> bool {
match (self, other) {
(KeyView::String(a, _), KeyView::String(b, _)) => a == b,
(KeyView::Integer(a), KeyView::Integer(b)) => a == b,
_ => self.other_eq(other),
}
}
}
impl<'a> KeyView<'a> {
pub(crate) fn string(bytes: &'a [u8]) -> Self {
Self::String(bytes, string_hash(bytes))
}
#[inline]
pub(crate) fn cached_string(bytes: &'a [u8], hash: u64) -> Self {
debug_assert_eq!(hash, string_hash(bytes));
Self::String(bytes, hash)
}
#[inline(never)]
fn other_eq(&self, other: &Self) -> bool {
match (self, other) {
(KeyView::Bool(a), KeyView::Bool(b)) => a == b,
(KeyView::Float(a), KeyView::Float(b)) => a == b,
(KeyView::Object(a), KeyView::Object(b)) => a == b,
(KeyView::Native(a), KeyView::Native(b)) => a == b,
(KeyView::Light(d, a), KeyView::Light(e, b)) => d == e && a == b,
_ => false,
}
}
}
impl Hash for KeyView<'_> {
#[inline]
fn hash<H: Hasher>(&self, output: &mut H) {
if let Self::String(bytes, hash) = self {
debug_assert_eq!(*hash, string_hash(bytes));
output.write_u64(*hash);
return;
}
let mut hash = StableBuildHasher.build_hasher();
let state = &mut hash;
std::mem::discriminant(self).hash(state);
match self {
Self::Bool(v) => v.hash(state),
Self::Integer(v) => v.hash(state),
Self::Float(v) => v.hash(state),
Self::Object(v) => v.hash(state),
Self::Native(v) => v.hash(state),
Self::Light(d, v) => {
d.hash(state);
v.hash(state);
}
Self::String(..) => unreachable!(),
}
let hash = hash.finish();
output.write_u64(hash);
}
}
impl TableKey {
pub(crate) fn string(bytes: Vec<u8>) -> Self {
let hash = string_hash(&bytes);
Self::String(KeyString::copied(&bytes, hash))
}
pub(crate) fn view(&self) -> KeyView<'_> {
match self {
Self::Bool(bit) => KeyView::Bool(*bit),
Self::Integer(integer) => KeyView::Integer(*integer),
Self::Float(bits) => KeyView::Float(*bits),
Self::String(key) => {
let (bytes, hash) = key.parts();
KeyView::cached_string(bytes, hash)
}
Self::Object(id) => KeyView::Object(*id),
Self::Native(index) => KeyView::Native(*index),
Self::Light(domain, bits) => KeyView::Light(*domain, *bits),
}
}
fn canonical_value(&self, key_value: Value) -> Value {
match self {
Self::Bool(bit) => Value::Bool(*bit),
Self::Integer(integer) => Value::Integer(*integer),
Self::Float(bits) => Value::Float(f64::from_bits(*bits)),
Self::Native(index) => Value::Native(*index),
Self::Light(domain, bits) => Value::LightUserdata(*domain, *bits),
Self::String(..) | Self::Object(_) => key_value,
}
}
}
impl PartialEq for TableKey {
fn eq(&self, other: &Self) -> bool {
self.view() == other.view()
}
}
impl Eq for TableKey {}
impl Hash for TableKey {
fn hash<H: Hasher>(&self, state: &mut H) {
self.view().hash(state);
}
}
#[derive(Clone, Debug)]
pub(crate) struct Slot {
pub(crate) key: TableKey,
key_value: Value,
value: Value,
next_live: u32,
prev_live: u32,
}
impl Slot {
pub(crate) fn live(key: TableKey, key_value: Value, value: Value) -> Self {
Self {
key,
key_value,
value,
next_live: 0,
prev_live: 0,
}
}
pub(crate) fn dead(key: TableKey) -> Self {
Self::live(key, Value::Nil, Value::Nil)
}
pub(crate) fn pair(&self) -> Option<(Value, Value)> {
self.is_live().then_some((self.key_value, self.value))
}
pub(crate) fn pair_refs(&self) -> Option<(&Value, &Value)> {
self.is_live().then_some((&self.key_value, &self.value))
}
fn is_live(&self) -> bool {
!matches!(self.value, Value::Nil)
}
}
#[derive(Clone, Debug)]
pub(crate) struct Table {
slots: Vec<Slot>,
index: Vec<u32>,
indexed_keys: usize,
array: Vec<u32>,
first_live: Option<u32>,
last_live: Option<u32>,
live_count: u32,
dead_count: u32,
live_key_bytes: u64,
dead_key_bytes: u64,
positive_count: u32,
prefix: std::cell::Cell<u32>,
}
const ANCHOR_BYTES: u64 = 4096;
const SMALL_TABLE_SLOTS: usize = 5;
fn key_bytes(key: &TableKey) -> u64 {
match key {
TableKey::String(key) => key.bytes().len() as u64,
_ => 0,
}
}
fn is_positive(key: &TableKey) -> bool {
matches!(key, TableKey::Integer(key) if *key > 0)
}
impl Table {
pub(crate) fn reserve_hash(&mut self, entries: usize) {
self.index.reserve(entries.saturating_mul(2));
}
pub(crate) fn new() -> Self {
Self {
slots: Vec::new(),
index: Vec::new(),
indexed_keys: 0,
array: Vec::new(),
first_live: None,
last_live: None,
live_count: 0,
dead_count: 0,
live_key_bytes: 0,
dead_key_bytes: 0,
positive_count: 0,
prefix: std::cell::Cell::new(0),
}
}
#[cfg(any(test, feature = "__measure"))]
pub(crate) fn live_len(&self) -> usize {
self.live_count as usize
}
#[cfg(any(test, feature = "__measure"))]
pub(crate) fn dead_len(&self) -> usize {
self.dead_count as usize
}
pub(crate) fn slot_len(&self) -> usize {
self.slots.len()
}
pub(crate) fn slots(&self) -> &[Slot] {
&self.slots
}
#[inline]
fn bucket(&self, key: KeyView<'_>) -> usize {
TableBuildHasher.hash_one(key) as usize & (self.index.len() - 1)
}
fn lookup_index(&self, key: KeyView<'_>) -> Option<u32> {
if self.index.is_empty() {
return None;
}
let mut bucket = self.bucket(key);
loop {
let at = self.index[bucket].checked_sub(1)?;
if self.slots[at as usize].key.view() == key {
return Some(at);
}
bucket = (bucket + 1) & (self.index.len() - 1);
}
}
fn index_slot(&mut self, at: u32) {
let key = self.slots[at as usize].key.view();
let mut bucket = self.bucket(key);
loop {
let entry = self.index[bucket];
if entry == 0 {
self.index[bucket] = at + 1;
self.indexed_keys += 1;
return;
}
if self.slots[(entry - 1) as usize].key.view() == key {
self.index[bucket] = at + 1;
return;
}
bucket = (bucket + 1) & (self.index.len() - 1);
}
}
fn rebuild_index(&mut self, len: usize) {
self.index.clear();
self.index.resize(len, 0);
self.indexed_keys = 0;
for at in 0..self.slots.len() {
self.index_slot(at as u32);
}
}
#[inline(always)]
fn lookup(&self, key: KeyView<'_>) -> Option<u32> {
if let KeyView::Integer(integer) = key
&& integer > 0
&& let Ok(offset) = usize::try_from(integer - 1)
&& let Some(&entry) = self.array.get(offset)
{
let found = entry.checked_sub(1);
debug_assert_eq!(found, self.lookup_index(key));
return found;
}
if self.index.is_empty() {
return self.lookup_small(key).checked_sub(1);
}
self.lookup_index(key)
}
#[inline(never)]
fn lookup_small(&self, key: KeyView<'_>) -> u32 {
self.slots
.iter()
.rposition(|slot| slot.key.view() == key)
.map_or(0, |at| at as u32 + 1)
}
pub(crate) fn get(&self, key: &TableKey) -> Value {
self.get_view(key.view()).unwrap_or(Value::Nil)
}
pub(crate) fn get_view(&self, key: KeyView<'_>) -> Option<Value> {
let value = self.lookup_live(key).map(|(_, value)| value);
#[cfg(feature = "counters")]
crate::counters::table_probe(value.is_some(), matches!(key, KeyView::String(..)));
value
}
#[inline]
fn lookup_live(&self, key: KeyView<'_>) -> Option<(u32, Value)> {
let at = self.lookup(key)?;
let slot = &self.slots[at as usize];
slot.is_live().then_some((at, slot.value))
}
#[inline(always)]
pub(crate) fn get_name_hint(
&self,
name: &[u8],
hash: u64,
hint: &std::cell::Cell<u32>,
) -> Option<Value> {
let at = hint.get();
if let Some(slot) = self.slots.get(at as usize)
&& slot.is_live()
&& let TableKey::String(key) = &slot.key
&& key.matches_name(name, hash)
{
debug_assert_eq!(Some(at), self.lookup(KeyView::cached_string(name, hash)));
#[cfg(feature = "counters")]
crate::counters::table_probe(true, true);
return Some(slot.value);
}
let entry = self.lookup_live(KeyView::cached_string(name, hash));
#[cfg(feature = "counters")]
crate::counters::table_probe(entry.is_some(), true);
if let Some((at, _)) = entry {
hint.set(at);
}
entry.map(|(_, value)| value)
}
#[inline]
pub(crate) fn get_event_hint(
&self,
event: &[u8],
hint: &std::cell::Cell<u32>,
) -> Option<Value> {
let at = hint.get();
if let Some(slot) = self.slots.get(at as usize)
&& slot.is_live()
&& let TableKey::String(key) = &slot.key
&& key.bytes() == event
{
#[cfg(feature = "counters")]
crate::counters::table_probe(true, true);
return Some(slot.value);
}
let entry = self.lookup_live(KeyView::string(event));
#[cfg(feature = "counters")]
crate::counters::table_probe(entry.is_some(), true);
if let Some((at, _)) = entry {
hint.set(at);
}
entry.map(|(_, value)| value)
}
#[inline]
pub(crate) fn update_name_hint(
&mut self,
name: &[u8],
hash: u64,
hint: &std::cell::Cell<u32>,
value: Value,
) -> bool {
if matches!(value, Value::Nil) {
return false;
}
#[cfg(debug_assertions)]
let expected = self.lookup(KeyView::cached_string(name, hash));
let at = hint.get();
if let Some(slot) = self.slots.get_mut(at as usize)
&& slot.is_live()
&& let TableKey::String(key) = &slot.key
&& key.matches_name(name, hash)
{
#[cfg(debug_assertions)]
debug_assert_eq!(expected, Some(at));
#[cfg(feature = "counters")]
crate::counters::table_probe(true, true);
slot.value = value;
return true;
}
let at = self.update_view_slot(KeyView::cached_string(name, hash), value);
hint.set(at.unwrap_or(u32::MAX));
at.is_some()
}
pub(crate) fn update_view(&mut self, key: KeyView<'_>, value: Value) -> bool {
self.update_view_slot(key, value).is_some()
}
#[inline]
fn update_view_slot(&mut self, key: KeyView<'_>, value: Value) -> Option<u32> {
if matches!(value, Value::Nil) {
return None;
}
let found = self.lookup_live(key);
#[cfg(feature = "counters")]
crate::counters::table_probe(found.is_some(), matches!(key, KeyView::String(..)));
let (at, _) = found?;
self.slots[at as usize].value = value;
Some(at)
}
pub(crate) fn insert(&mut self, key: TableKey, key_value: Value, value: Value) {
if matches!(value, Value::Nil) {
self.delete_view(key.view());
return;
}
if let Some((at, _)) = self.lookup_live(key.view()) {
self.slots[at as usize].value = value;
return;
}
if u64::from(self.dead_count) * 2 > u64::from(self.live_count)
|| self.dead_key_bytes > self.live_key_bytes.saturating_add(ANCHOR_BYTES)
{
self.compact();
}
let key_value = key.canonical_value(key_value);
self.append_live(key, key_value, value);
}
pub(crate) fn restore(&mut self, slots: Vec<Slot>) {
self.slots = slots;
self.reindex_and_relink();
}
#[cfg(any(test, feature = "__measure"))]
pub(crate) fn next(&self, key: Option<&TableKey>) -> Result<Option<(Value, Value)>, ()> {
self.next_view(key.map(TableKey::view))
}
pub(crate) fn next_view(&self, key: Option<KeyView<'_>>) -> Result<Option<(Value, Value)>, ()> {
let cursor = match key {
None => self.first_live,
Some(key) => self.slots[self.lookup(key).ok_or(())? as usize]
.next_live
.checked_sub(1),
};
Ok(self.resolve(cursor).and_then(|at| self.pair_at(at)))
}
pub(crate) fn sorted_string_fuel(&self) -> u64 {
self.slots.iter().fold(0u64, |fuel, slot| {
let key = &slot.key;
let extra = match key {
TableKey::String(bytes) => bytes.bytes().len().saturating_sub(16).div_ceil(16),
_ => 0,
};
fuel.saturating_add((extra as u64).saturating_mul(4))
})
}
pub(crate) fn sorted_next_view(&self, key: Option<KeyView<'_>>) -> SortedNext {
if let Some(key) = key {
if !matches!(
key,
KeyView::Bool(_) | KeyView::Integer(_) | KeyView::Float(_) | KeyView::String(..)
) {
return Err(SortedNextError::UnsupportedKey);
}
if self.lookup(key).is_none() {
return Err(SortedNextError::InvalidKey);
}
}
let mut best: Option<(KeyView<'_>, Value, Value)> = None;
for slot in &self.slots {
if !slot.is_live() {
continue;
}
let candidate = slot.key.view();
if !matches!(
candidate,
KeyView::Bool(_) | KeyView::Integer(_) | KeyView::Float(_) | KeyView::String(..)
) {
return Err(SortedNextError::UnsupportedKey);
}
if key.is_some_and(|key| {
sorted_key_cmp(candidate, key) != Some(std::cmp::Ordering::Greater)
}) {
continue;
}
if best.is_none_or(|(key, _, _)| {
sorted_key_cmp(candidate, key) == Some(std::cmp::Ordering::Less)
}) {
best = Some((candidate, slot.key_value, slot.value));
}
}
Ok(best.map(|(_, key, value)| (key, value)))
}
pub(crate) fn raw_border(&self) -> i64 {
let border = smallest_border_from(
i64::from(self.prefix.get()),
i64::from(self.positive_count),
|key| self.get(&TableKey::Integer(key)) != Value::Nil,
);
self.prefix.set(u32::try_from(border).unwrap_or(0));
border
}
#[cfg(test)]
pub(crate) fn live_keys(&self) -> Vec<TableKey> {
self.slots
.iter()
.filter(|slot| slot.is_live())
.map(|slot| slot.key.clone())
.collect()
}
fn pair_at(&self, at: u32) -> Option<(Value, Value)> {
self.slots[at as usize].pair()
}
fn resolve(&self, mut cursor: Option<u32>) -> Option<u32> {
let mut steps = 0;
while let Some(at) = cursor {
if steps > self.slots.len() {
return None;
}
steps += 1;
let slot = &self.slots[at as usize];
if slot.is_live() {
return Some(at);
}
cursor = slot.next_live.checked_sub(1);
}
None
}
pub(crate) fn delete_slot(&mut self, at: usize) {
if !self.slots.get(at).is_some_and(Slot::is_live) {
return;
}
let next = self.slots[at].next_live;
let prev = self.slots[at].prev_live;
if let Some(prev) = prev.checked_sub(1) {
self.slots[prev as usize].next_live = next;
} else {
self.first_live = next.checked_sub(1);
}
if let Some(next) = next.checked_sub(1) {
self.slots[next as usize].prev_live = prev;
} else {
self.last_live = prev.checked_sub(1);
}
let slot = &mut self.slots[at];
let bytes = key_bytes(&slot.key);
slot.key_value = Value::Nil;
slot.value = Value::Nil;
slot.prev_live = 0;
self.live_count -= 1;
self.dead_count += 1;
self.live_key_bytes -= bytes;
self.dead_key_bytes += bytes;
if is_positive(&slot.key) {
self.positive_count -= 1;
if let TableKey::Integer(key) = slot.key
&& key <= i64::from(self.prefix.get())
{
self.prefix.set((key - 1) as u32);
}
}
}
pub(crate) fn delete_view(&mut self, key: KeyView<'_>) {
if let Some(at) = self.lookup(key) {
self.delete_slot(at as usize);
}
}
fn compact(&mut self) {
self.slots.retain(Slot::is_live);
if self.slots.capacity() > self.slots.len().saturating_mul(4) {
self.slots.shrink_to_fit();
}
self.reindex_and_relink();
}
fn append_live(&mut self, key: TableKey, key_value: Value, value: Value) {
count!("table_inserts");
let at = self.slots.len() as u32;
let prev = self.last_live.map_or(0, |at| at + 1);
for slot in self.slots.iter_mut().rev() {
slot.next_live = at + 1;
if slot.is_live() {
break;
}
}
if prev == 0 {
self.first_live = Some(at);
}
if is_positive(&key) {
self.positive_count += 1;
}
self.live_key_bytes += key_bytes(&key);
self.slots.push(Slot {
key,
key_value,
value,
next_live: 0,
prev_live: prev,
});
self.last_live = Some(at);
self.live_count += 1;
if self.slots.len() == SMALL_TABLE_SLOTS + 1 {
self.rebuild_index(16);
self.rebuild_array();
} else if self.slots.len() > SMALL_TABLE_SLOTS + 1 {
if (self.indexed_keys + 1) * 4 > self.index.len() * 3 {
self.rebuild_index(self.index.len() * 2);
count!("table_resizes");
} else {
self.index_slot(at);
}
self.index_array(at);
}
}
fn index_array(&mut self, at: u32) {
let TableKey::Integer(integer) = self.slots[at as usize].key else {
return;
};
let Ok(key) = usize::try_from(integer) else {
return;
};
if key == 0 {
return;
}
if key > self.array.len() {
if key > self.slots.len().saturating_mul(2) {
return;
}
let Some(len) = key.checked_next_power_of_two() else {
return;
};
let old = self.array.len();
self.array.resize(len, 0);
if (len - old).saturating_mul(16) < self.slots.len() {
for covered in old + 1..=len {
if let Some(at) = self.lookup_index(KeyView::Integer(covered as i64)) {
self.array[covered - 1] = at + 1;
}
}
} else {
for (i, entry) in self.slots.iter().enumerate() {
if let TableKey::Integer(integer) = entry.key
&& integer > old as i64
&& integer <= len as i64
{
self.array[integer as usize - 1] = i as u32 + 1;
}
}
}
}
self.array[key - 1] = at + 1;
}
fn reindex_and_relink(&mut self) {
count!("table_rehashes");
self.live_count = 0;
self.dead_count = 0;
self.live_key_bytes = 0;
self.dead_key_bytes = 0;
self.positive_count = 0;
self.prefix.set(0);
self.first_live = None;
self.last_live = None;
let mut next = 0;
for (at, slot) in self.slots.iter_mut().enumerate().rev() {
slot.next_live = next;
if slot.is_live() {
next = at as u32 + 1;
}
}
let mut prev = 0;
for (at, slot) in self.slots.iter_mut().enumerate() {
let bytes = key_bytes(&slot.key);
slot.prev_live = 0;
if slot.is_live() {
slot.prev_live = prev;
if prev == 0 {
self.first_live = Some(at as u32);
}
prev = at as u32 + 1;
self.last_live = Some(at as u32);
self.live_count += 1;
self.live_key_bytes += bytes;
if is_positive(&slot.key) {
self.positive_count += 1;
}
} else {
self.dead_count += 1;
self.dead_key_bytes += bytes;
}
}
if self.slots.len() > SMALL_TABLE_SLOTS {
let len = (self.slots.len() * 2).next_power_of_two();
self.rebuild_index(len);
self.rebuild_array();
} else {
self.index = Vec::new();
self.indexed_keys = 0;
self.array = Vec::new();
}
}
fn rebuild_array(&mut self) {
self.array = Vec::new();
let limit = self.slots.len().saturating_mul(2);
let max = self
.slots
.iter()
.filter_map(|slot| match slot.key {
TableKey::Integer(key) if key > 0 => {
usize::try_from(key).ok().filter(|key| *key <= limit)
}
_ => None,
})
.max()
.unwrap_or(0);
if let Some(len) = max.checked_next_power_of_two().filter(|_| max > 0) {
self.array.resize(len, 0);
for (at, slot) in self.slots.iter().enumerate() {
if let TableKey::Integer(key) = slot.key
&& key > 0
&& key <= len as i64
{
self.array[key as usize - 1] = at as u32 + 1;
}
}
}
}
}
#[cfg(test)]
pub(crate) fn smallest_border(limit: i64, present: impl Fn(i64) -> bool) -> i64 {
smallest_border_from(0, limit, present)
}
pub(crate) fn smallest_border_from(known: i64, limit: i64, present: impl Fn(i64) -> bool) -> i64 {
if known > 0 && known <= limit {
return extend_border(known, limit, present);
}
if limit <= 0 || !present(1) {
return 0;
}
extend_border(1, limit, present)
}
fn extend_border(mut border: i64, limit: i64, present: impl Fn(i64) -> bool) -> i64 {
loop {
if border == limit || border == i64::MAX {
return border;
}
let next = border.checked_add(1).expect("border is below i64::MAX");
if !present(next) {
return border;
}
border = next;
}
}
pub(crate) fn normalize_key(
value: Value,
string_bytes: Option<(&[u8], u64)>,
object_id: Option<ObjectId>,
) -> Result<TableKey, LuaFault> {
match value {
Value::Nil => Err(LuaFault::NilKey),
Value::Bool(bit) => Ok(TableKey::Bool(bit)),
Value::Integer(integer) => Ok(TableKey::Integer(integer)),
Value::Float(number) => normalize_float(number),
Value::String(_) => {
let (bytes, hash) = string_bytes.ok_or(LuaFault::Type)?;
Ok(TableKey::String(KeyString::copied(bytes, hash)))
}
Value::Table(_)
| Value::Closure(_)
| Value::Thread(_)
| Value::NativeClosure(_)
| Value::Userdata(_) => Ok(TableKey::Object(object_id.ok_or(LuaFault::Type)?)),
Value::Native(index) => Ok(TableKey::Native(index)),
Value::LightUserdata(domain, bits) => Ok(TableKey::Light(domain, bits)),
}
}
const TWO_POW_63: f64 = 9_223_372_036_854_775_808.0;
pub(crate) fn value_view(value: Value, string_bytes: Option<(&[u8], u64)>) -> Option<KeyView<'_>> {
Some(match value {
Value::Bool(bit) => KeyView::Bool(bit),
Value::Integer(integer) => KeyView::Integer(integer),
Value::Float(number) => match normalize_float(number).ok()? {
TableKey::Integer(integer) => KeyView::Integer(integer),
TableKey::Float(bits) => KeyView::Float(bits),
_ => return None,
},
Value::String(_) => {
let (bytes, hash) = string_bytes?;
KeyView::cached_string(bytes, hash)
}
Value::Native(index) => KeyView::Native(index),
Value::LightUserdata(domain, bits) => KeyView::Light(domain, bits),
Value::Nil
| Value::Table(_)
| Value::Closure(_)
| Value::Thread(_)
| Value::NativeClosure(_)
| Value::Userdata(_) => return None,
})
}
fn normalize_float(number: f64) -> Result<TableKey, LuaFault> {
if number.is_nan() {
return Err(LuaFault::NanKey);
}
if number == 0.0 {
return Ok(TableKey::Integer(0));
}
if number.fract() == 0.0 && (-TWO_POW_63..TWO_POW_63).contains(&number) {
return Ok(TableKey::Integer(number as i64));
}
Ok(TableKey::Float(number.to_bits()))
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn string_object_anchor_shares_bytes_without_retaining_the_object() {
let mut heap = crate::heap::Heap::new();
let handle = heap.alloc_string(b"anchor\0key".to_vec()).unwrap();
let value = Value::String(handle);
let key = heap.normalize_value(value).unwrap();
let TableKey::String(bytes) = &key else {
panic!("string key")
};
assert!(std::rc::Rc::ptr_eq(
&bytes.0,
&heap.strings.get(handle).unwrap().bytes.0
));
let mut table = Table::new();
table.insert(key, value, Value::Integer(7));
put(&mut table, 1, 9);
table.delete_view(KeyView::string(b"anchor\0key"));
assert_eq!(table.slots[0].key_value, Value::Nil);
heap.strings.free(handle.index);
assert!(heap.strings.get(handle).is_none());
let replacement = heap.alloc_string(b"anchor\0key".to_vec()).unwrap();
let key = heap.normalize_value(Value::String(replacement)).unwrap();
assert_eq!(table.get(&key), Value::Nil);
assert_eq!(
table.next(Some(&key)).unwrap(),
Some((Value::Integer(1), Value::Integer(9)))
);
table.restore(table.slots.clone());
assert_eq!(
table.next(Some(&key)).unwrap(),
Some((Value::Integer(1), Value::Integer(9)))
);
}
#[test]
fn probe_wrap_resize_and_latest_anchor() {
assert_eq!(std::mem::size_of::<TableKey>(), 16);
assert_eq!(std::mem::size_of::<Slot>(), 56);
let mut table = Table::new();
table.index.resize(16, 0);
let keys: Vec<_> = (1..10_000)
.filter(|&key| table.bucket(KeyView::Integer(key)) == 15)
.take(40)
.collect();
table.index.clear();
for (i, &key) in keys.iter().enumerate() {
put(&mut table, key, i as i64 + 1);
}
assert!(table.index.len() > 16);
for (i, &key) in keys.iter().enumerate() {
assert_eq!(
table.get(&TableKey::Integer(key)),
Value::Integer(i as i64 + 1)
);
}
table.delete_view(KeyView::Integer(keys[0]));
put(&mut table, keys[0], 99);
assert_eq!(table.lookup_index(KeyView::Integer(keys[0])), Some(40));
table.restore(table.slots.clone());
assert_eq!(table.get(&TableKey::Integer(keys[0])), Value::Integer(99));
assert_eq!(table.get(&TableKey::Integer(-1)), Value::Nil);
}
#[test]
fn small_tables_match_slot_index_through_mutation_and_restore() {
assert!(std::mem::size_of::<TableKey>() <= 24);
let keys = [
TableKey::Integer(1),
TableKey::Integer(2),
TableKey::Integer(i64::MAX),
TableKey::string(b"x".to_vec()),
TableKey::string(b"x\0y".to_vec()),
TableKey::string(vec![7; 128]),
TableKey::Bool(true),
TableKey::Float(1.5f64.to_bits()),
TableKey::Object(ObjectId(9)),
TableKey::Native(4),
];
let mut table = Table::new();
let mut seed = 0x2e14_497c_83b9_d061u64;
let mut small = 0;
let mut large = 0;
let mut promoted = 0;
let mut shrunk = 0;
for round in 0..4000 {
seed = seed.wrapping_mul(6364136223846793005).wrapping_add(1);
let was_small = table.slots.len() <= SMALL_TABLE_SLOTS;
let key = &keys[(seed >> 32) as usize % keys.len()];
match seed % 9 {
0..=3 => table.insert(key.clone(), Value::Nil, Value::Integer(round)),
4 => table.delete_view(key.view()),
5 => {
table.update_view(key.view(), Value::Integer(round));
}
6 => {
if !table.slots.is_empty() {
table.delete_slot(seed as usize % table.slots.len());
}
}
7 => table.restore(table.slots.clone()),
_ => table.compact(),
}
if round % 97 == 96 {
for slot in 0..table.slots.len() {
table.delete_slot(slot);
}
table.compact();
}
let is_small = table.slots.len() <= SMALL_TABLE_SLOTS;
promoted += usize::from(was_small && !is_small);
shrunk += usize::from(!was_small && is_small);
if is_small {
small += 1;
assert_eq!(table.index.capacity(), 0);
assert_eq!(table.array.capacity(), 0);
} else {
large += 1;
}
let mut reference = HashMap::with_hasher(TableBuildHasher);
for (index, slot) in table.slots.iter().enumerate() {
let key = &slot.key;
reference.insert(key.clone(), index as u32);
}
for key in &keys {
let expected = reference.get(key).copied();
assert_eq!(table.lookup(key.view()), expected);
let value = expected
.and_then(|index| table.slots[index as usize].pair().map(|(_, value)| value));
assert_eq!(table.get_view(key.view()), value);
let next = expected
.map(|index| {
table.slots[index as usize + 1..]
.iter()
.find_map(Slot::pair)
})
.ok_or(());
assert_eq!(table.next(Some(key)), next);
}
let border = smallest_border(i64::from(table.positive_count), |integer| {
reference
.get(&TableKey::Integer(integer))
.is_some_and(|&index| table.slots[index as usize].is_live())
});
assert_eq!(table.raw_border(), border);
}
assert!(small > 0 && large > 0 && promoted > 0 && shrunk > 0);
}
#[test]
fn dense_index_matches_hash_through_mutation_and_restore() {
let mut fast = Table::new();
let mut hash = Table::new();
let mut state = 0x67e2_19b5_08ac_d431u64;
let keys: Vec<_> = (1..=96)
.map(TableKey::Integer)
.chain([
TableKey::Integer(0),
TableKey::Integer(-1),
TableKey::Integer(i64::MAX),
TableKey::Integer(1 << 32),
TableKey::Bool(true),
TableKey::string(b"field".to_vec()),
TableKey::Object(ObjectId(9)),
normalize_float(1.5).unwrap(),
normalize_float(1.0).unwrap(),
])
.collect();
for k in (1..=96).rev() {
put(&mut fast, k, k);
put(&mut hash, k, k);
}
for step in 0..4_000 {
state ^= state << 13;
state ^= state >> 7;
state ^= state << 17;
let key = &keys[state as usize % keys.len()];
let value = Value::Integer(step);
hash.array.clear(); match (state >> 32) % 8 {
0..=2 => {
fast.insert(key.clone(), value, value);
hash.insert(key.clone(), value, value);
}
3 => {
fast.delete_view(key.view());
hash.delete_view(key.view());
}
4 => assert_eq!(
fast.update_view(key.view(), value),
hash.update_view(key.view(), value)
),
5 => {
if !fast.slots.is_empty() {
let slot = state as usize % fast.slots.len();
fast.delete_slot(slot);
hash.delete_slot(slot);
}
}
6 => {
fast.restore(fast.slots.clone());
hash.restore(hash.slots.clone());
}
_ => {
fast.compact();
hash.compact();
}
}
hash.array.clear();
assert_eq!(fast.live_keys(), hash.live_keys());
assert_eq!(fast.dead_len(), hash.dead_len());
assert_eq!(fast.raw_border(), hash.raw_border());
assert_eq!(fast.next(None), hash.next(None));
for key in &keys {
assert_eq!(fast.get(key), hash.get(key));
assert_eq!(fast.get_view(key.view()), hash.get_view(key.view()));
assert_eq!(fast.next(Some(key)), hash.next(Some(key)));
}
for (offset, &slot) in fast.array.iter().enumerate() {
assert_eq!(
slot.checked_sub(1),
fast.lookup_index(KeyView::Integer(offset as i64 + 1))
);
}
assert!(fast.array.len() <= fast.slots.len().saturating_mul(4));
}
}
#[test]
fn dense_growth_refill_matches_hash_in_string_heavy_tables() {
let mut table = Table::new();
for key in [9_000, 9_001, 9_500] {
put(&mut table, key, key);
}
table.delete_view(TableKey::Integer(9_001).view());
for i in 0..8_192 {
let key = TableKey::string(format!("k{i}").into_bytes());
table.insert(key, Value::Integer(i), Value::Integer(i));
}
let mut key = 1;
while key <= 16_383 {
put(&mut table, key, key);
for (offset, &slot) in table.array.iter().enumerate() {
assert_eq!(
slot.checked_sub(1),
table.lookup_index(KeyView::Integer(offset as i64 + 1))
);
}
key = key * 2 + 1;
}
assert!(table.array.len() >= 9_501);
}
#[test]
fn cached_string_lookup_matches_uncached_random_tables() {
let mut seed = 0xa593_261f_7810_4d27u64;
let mut random = || {
seed = seed.wrapping_mul(6364136223846793005).wrapping_add(1);
seed
};
let keys: Vec<Vec<u8>> = (0..128)
.map(|i| (0..i * 3).map(|_| (random() >> 32) as u8).collect())
.collect();
let hashes: Vec<u64> = keys.iter().map(|key| string_hash(key)).collect();
let mut table = Table::new();
let mut oracle = std::collections::BTreeMap::new();
for round in 0..4000 {
let index = (random() >> 32) as usize % keys.len();
let key = &keys[index];
let value = if random() & 3 == 0 {
Value::Nil
} else {
Value::Integer(round)
};
table.insert(
TableKey::String(KeyString::copied(key, hashes[index])),
Value::Nil,
value,
);
if value == Value::Nil {
oracle.remove(key);
} else {
oracle.insert(key.clone(), value);
}
if round % 31 == 0 {
table.restore(table.slots.clone());
}
for (key, &hash) in keys.iter().zip(&hashes) {
let expected = oracle.get(key).copied();
assert_eq!(table.get_view(KeyView::cached_string(key, hash)), expected);
assert_eq!(table.get_view(KeyView::string(key)), expected);
}
}
}
#[test]
fn slot_hints_match_uncached_random_tables() {
let mut seed = 0x459d_18ae_7493_b261u64;
let mut random = || {
seed = seed.wrapping_mul(6364136223846793005).wrapping_add(1);
seed
};
let keys: Vec<Vec<u8>> = (0..32)
.map(|i| {
let len = if i <= 17 { i } else { i * 7 };
(0..len).map(|_| (random() >> 32) as u8).collect()
})
.collect();
let hashes: Vec<_> = keys.iter().map(|key| string_hash(key)).collect();
let mut cached = std::array::from_fn::<_, 3, _>(|_| Table::new());
let mut plain = cached.clone();
let hints = std::array::from_fn::<_, 8, _>(|_| std::cell::Cell::new(u32::MAX));
for round in 0..4000 {
let bits = random();
let table_index = (bits >> 32) as usize % cached.len();
let key_index = (bits >> 16) as usize % keys.len();
let name = &keys[key_index];
let hash = hashes[key_index];
let hint = &hints[bits as usize % hints.len()];
let table = &mut cached[table_index];
let oracle = &mut plain[table_index];
let value = if bits & 7 == 0 {
Value::Nil
} else {
Value::Integer(round)
};
if round % 17 == 0 {
hint.set((bits >> 32) as u32);
}
match (bits >> 8) % 7 {
0..=1 => {
let key = TableKey::string(name.clone());
table.insert(key.clone(), Value::Nil, value);
oracle.insert(key, Value::Nil, value);
}
2 => assert_eq!(
table.update_name_hint(name, hash, hint, value),
oracle.update_view(KeyView::cached_string(name, hash), value)
),
3 => {
table.delete_view(KeyView::cached_string(name, hash));
oracle.delete_view(KeyView::cached_string(name, hash));
}
4 => {
if !table.slots.is_empty() {
let slot = bits as usize % table.slots.len();
table.delete_slot(slot); oracle.delete_slot(slot);
}
}
5 => {
table.compact();
oracle.compact();
}
_ => {
table.restore(table.slots.clone());
oracle.restore(oracle.slots.clone());
}
}
for (name, &hash) in keys.iter().zip(&hashes) {
assert_eq!(
table.get_name_hint(name, hash, hint),
oracle.get_view(KeyView::cached_string(name, hash))
);
}
table.get_name_hint(name, hash, hint);
assert_eq!(table.live_keys(), oracle.live_keys());
assert_eq!(table.dead_len(), oracle.dead_len());
let ordered = |table: &Table| {
table
.slots
.iter()
.filter_map(|slot| slot.pair().map(|(_, value)| (slot.key.clone(), value)))
.collect::<Vec<_>>()
};
assert_eq!(ordered(table), ordered(oracle));
}
}
fn put(table: &mut Table, key: i64, value: i64) {
table.insert(
TableKey::Integer(key),
Value::Integer(key),
Value::Integer(value),
);
}
#[test]
fn float_keys_normalize_like_lua() {
assert_eq!(
normalize_key(Value::Float(9_223_372_036_854_775_808.0), None, None),
Ok(TableKey::Float(9_223_372_036_854_775_808.0f64.to_bits()))
);
assert_eq!(
normalize_key(Value::Float(-9_223_372_036_854_775_808.0), None, None),
Ok(TableKey::Integer(i64::MIN))
);
let mut table = Table::new();
table.insert(TableKey::Integer(2), Value::Float(2.0), Value::Integer(1));
let (key, _) = table.next(None).unwrap().unwrap();
assert_eq!(key, Value::Integer(2), "next returns the integer key");
table.insert(TableKey::Integer(2), Value::Integer(2), Value::Integer(9));
assert_eq!(table.get_view(KeyView::Integer(2)), Some(Value::Integer(9)));
assert!(!table.update_view(KeyView::Integer(3), Value::Integer(1)));
assert!(!table.update_view(KeyView::Integer(2), Value::Nil));
assert_eq!(value_view(Value::Float(f64::NAN), None), None);
assert_eq!(
value_view(Value::Float(3.0), None),
Some(KeyView::Integer(3))
);
}
#[test]
fn the_border_cache_follows_inserts_deletes_and_compaction() {
let mut table = Table::new();
let recount = |table: &Table| {
table
.slots
.iter()
.filter(|slot| slot.is_live() && is_positive(&slot.key))
.count() as u32
};
let mut state = 7u64;
for _ in 0..4000 {
state = state
.wrapping_mul(6364136223846793005)
.wrapping_add(1442695040888963407);
let key = (state >> 40) as i64 % 64 - 8;
let value = if state & 3 == 0 {
Value::Nil
} else {
Value::Integer(1)
};
table.insert(TableKey::Integer(key), Value::Integer(key), value);
assert_eq!(table.positive_count, recount(&table));
let scanned = smallest_border(i64::from(recount(&table)), |key| {
table.get(&TableKey::Integer(key)) != Value::Nil
});
assert_eq!(table.raw_border(), scanned);
}
let slots = table.slots.clone();
table.restore(slots);
assert_eq!(table.positive_count, recount(&table));
}
#[test]
fn insertion_order_survives_update_and_delete() {
let mut table = Table::new();
put(&mut table, 1, 10);
put(&mut table, 2, 20);
put(&mut table, 1, 11);
table.insert(TableKey::Integer(1), Value::Integer(1), Value::Nil);
put(&mut table, 3, 30);
assert_eq!(
table.live_keys(),
vec![TableKey::Integer(2), TableKey::Integer(3)]
);
assert!(matches!(
table.get(&TableKey::Integer(2)),
Value::Integer(20)
));
assert_eq!(table.dead_len(), 0);
}
#[test]
fn nil_assignment_leaves_a_dead_anchor_until_the_next_insert() {
let mut table = Table::new();
table.insert(TableKey::Bool(true), Value::Bool(true), Value::Integer(1));
table.insert(TableKey::Bool(true), Value::Bool(true), Value::Nil);
assert_eq!(table.live_len(), 0);
assert_eq!(table.dead_len(), 1);
assert!(matches!(table.get(&TableKey::Bool(true)), Value::Nil));
put(&mut table, 1, 1);
assert_eq!(table.dead_len(), 0);
assert_eq!(table.live_len(), 1);
}
#[test]
fn float_keys_collapse_onto_integers() {
assert_eq!(normalize_float(1.0).unwrap(), TableKey::Integer(1));
assert_eq!(normalize_float(-0.0).unwrap(), TableKey::Integer(0));
assert_eq!(normalize_float(0.0).unwrap(), TableKey::Integer(0));
assert!(matches!(normalize_float(f64::NAN), Err(LuaFault::NanKey)));
assert_eq!(
normalize_float(1.5).unwrap(),
TableKey::Float(1.5f64.to_bits())
);
}
#[test]
fn next_walks_live_entries_and_survives_deleting_the_current_key() {
let mut table = Table::new();
put(&mut table, 1, 10);
put(&mut table, 2, 20);
put(&mut table, 3, 30);
let (key, value) = table.next(None).unwrap().unwrap();
assert_eq!((key, value), (Value::Integer(1), Value::Integer(10)));
table.insert(TableKey::Integer(1), Value::Integer(1), Value::Nil);
let (key, value) = table.next(Some(&TableKey::Integer(1))).unwrap().unwrap();
assert_eq!((key, value), (Value::Integer(2), Value::Integer(20)));
table.insert(TableKey::Integer(2), Value::Integer(2), Value::Integer(99));
let (key, _) = table.next(Some(&TableKey::Integer(2))).unwrap().unwrap();
assert_eq!(key, Value::Integer(3));
assert!(table.next(Some(&TableKey::Integer(3))).unwrap().is_none());
assert!(table.next(Some(&TableKey::Integer(9))).is_err());
assert!(matches!(
table.get(&TableKey::Integer(2)),
Value::Integer(99)
));
assert_eq!(table.dead_len(), 1);
}
#[test]
fn deleting_another_existing_key_is_skipped() {
let mut table = Table::new();
put(&mut table, 1, 10);
put(&mut table, 2, 20);
put(&mut table, 3, 30);
table.insert(TableKey::Integer(2), Value::Integer(2), Value::Nil);
let (key, _) = table.next(Some(&TableKey::Integer(1))).unwrap().unwrap();
assert_eq!(key, Value::Integer(3));
assert!(table.next(Some(&TableKey::Integer(2))).unwrap().unwrap().0 == Value::Integer(3));
}
#[test]
fn reinsertion_appends_and_drops_dead_anchors() {
let mut table = Table::new();
put(&mut table, 1, 10);
put(&mut table, 2, 20);
table.insert(TableKey::Integer(1), Value::Integer(1), Value::Nil);
put(&mut table, 1, 11);
assert_eq!(
table.live_keys(),
vec![TableKey::Integer(2), TableKey::Integer(1)]
);
assert_eq!(table.dead_len(), 0);
assert!(matches!(
table.get(&TableKey::Integer(1)),
Value::Integer(11)
));
let (key, _) = table.next(None).unwrap().unwrap();
assert_eq!(key, Value::Integer(2));
}
#[test]
fn compaction_releases_uncharged_slot_capacity() {
let mut table = Table::new();
for key in 1..=10_000 {
put(&mut table, key, key);
}
for key in 1..=10_000 {
table.delete_view(KeyView::Integer(key));
}
assert_eq!(table.slot_len(), 10_000);
assert_eq!(table.dead_len(), 10_000);
put(&mut table, 1, 1);
assert_eq!(table.slot_len(), 1);
assert_eq!(table.dead_len(), 0);
assert!(table.slots.capacity() <= 4 * table.slot_len());
}
#[test]
fn next_from_tail_anchors_is_checkpoint_transparent() {
use crate::{Host, HostRegistry, Journal, Runtime, StepOutcome, compile};
let cases = [
("t={1,2,3}; t[3]=nil; t[4]=4", 4, 1),
("t={1,2,3,4,5,6}; t[6]=nil; t[5]=nil; t[7]=7", 7, 2),
("t={1,2,3,4,5}; t[5]=nil; t[6]=6; t[6]=nil; t[7]=7", 7, 2),
];
let read_next = |runtime: &Runtime, last, dead| {
let heap = runtime.heap();
let globals = heap.globals.unwrap();
let Value::Table(handle) = heap
.table_get(globals, &TableKey::string(b"t".to_vec()))
.unwrap()
else {
panic!("expected table")
};
let table = &heap.tables.get(handle).unwrap().table;
assert_eq!(table.dead_len(), dead);
let mut results = vec![table.next(None)];
for key in 1..=last {
let at = table.lookup(KeyView::Integer(key)).unwrap() as usize;
let expected = table.slots[at + 1..].iter().find_map(Slot::pair);
let actual = table.next(Some(&TableKey::Integer(key)));
assert_eq!(actual, Ok(expected), "next from {key}");
results.push(actual);
}
results
};
for (source, last, dead) in cases {
let mut runtime = Runtime::builder().build().unwrap();
runtime
.load_main(&compile(source.as_bytes()).unwrap())
.unwrap();
assert_eq!(
runtime.run(10_000, &mut Journal::new()).unwrap(),
StepOutcome::Completed
);
let before = read_next(&runtime, last, dead);
let bytes = runtime.snapshot().unwrap();
let restored = Runtime::restore(&bytes, &Host::new(HostRegistry::new())).unwrap();
assert_eq!(before, read_next(&restored, last, dead));
assert_eq!(bytes, restored.snapshot().unwrap());
}
}
#[test]
fn repeated_insert_delete_does_not_accumulate_anchors() {
let mut table = Table::new();
for key in 0..1_000 {
put(&mut table, key, 1);
table.insert(TableKey::Integer(key), Value::Integer(key), Value::Nil);
assert!(table.dead_len() <= 1, "dead {}", table.dead_len());
assert_eq!(table.live_len(), 0);
}
for key in 0..1_000 {
put(&mut table, key, 1);
}
assert_eq!(table.dead_len(), 0);
assert_eq!(table.live_len(), 1_000);
for key in 0..1_000 {
table.insert(TableKey::Integer(key), Value::Integer(key), Value::Nil);
}
assert_eq!(table.dead_len(), 1_000);
assert_eq!(table.slot_len(), 1_000);
put(&mut table, 5, 1);
assert_eq!(table.dead_len(), 0);
assert_eq!(table.live_len(), 1);
}
#[test]
fn growing_the_index_does_not_change_live_order() {
let mut table = Table::new();
for key in 0..64 {
put(&mut table, key, key);
}
assert_eq!(
table.live_keys(),
(0..64).map(TableKey::Integer).collect::<Vec<_>>()
);
}
#[test]
fn borders_follow_the_smallest_legal_border() {
let empty = Table::new();
assert_eq!(empty.raw_border(), 0);
let mut sequence = Table::new();
put(&mut sequence, 1, 10);
put(&mut sequence, 2, 20);
put(&mut sequence, 3, 30);
assert_eq!(sequence.raw_border(), 3);
let mut hole = Table::new();
put(&mut hole, 1, 10);
put(&mut hole, 3, 30);
assert_eq!(hole.raw_border(), 1);
let mut missing = Table::new();
put(&mut missing, 2, 20);
put(&mut missing, 3, 30);
assert_eq!(missing.raw_border(), 0);
let mut irrelevant = Table::new();
put(&mut irrelevant, 0, 1);
put(&mut irrelevant, -5, 1);
irrelevant.insert(
TableKey::string(b"x".to_vec()),
Value::Nil,
Value::Integer(1),
);
irrelevant.insert(TableKey::Object(ObjectId(9)), Value::Nil, Value::Integer(1));
irrelevant.insert(
TableKey::Float(1.5f64.to_bits()),
Value::Nil,
Value::Integer(1),
);
put(&mut irrelevant, 1, 7);
put(&mut irrelevant, 2, 8);
assert_eq!(irrelevant.raw_border(), 2);
let mut sparse = Table::new();
put(&mut sparse, 1_000_000_000_000, 1);
assert_eq!(sparse.slot_len(), 1);
assert_eq!(sparse.raw_border(), 0);
let mut high = Table::new();
put(&mut high, 1, 1);
put(&mut high, 2, 1);
put(&mut high, i64::MAX, 1);
assert_eq!(high.slot_len(), 3);
assert_eq!(high.raw_border(), 2);
}
#[test]
fn float_one_counts_as_the_integer_border_key() {
let mut table = Table::new();
let key = normalize_float(1.0).unwrap();
table.insert(key, Value::Integer(1), Value::Integer(10));
put(&mut table, 2, 20);
assert_eq!(table.raw_border(), 2);
}
#[test]
fn border_search_does_not_wrap_maxinteger() {
assert_eq!(smallest_border(0, |_| true), 0);
assert_eq!(smallest_border(i64::MAX, |_| false), 0);
assert_eq!(smallest_border(4, |key| (1..=4).contains(&key)), 4);
assert_eq!(smallest_border(5, |key| key != 3), 2);
assert_eq!(
smallest_border(i64::MAX, |key| key == 1 || key == i64::MAX),
1
);
assert_eq!(smallest_border(i64::MAX, |key| key == 1), 1);
}
#[test]
fn restore_keeps_a_dead_anchor_between_live_keys() {
let mut table = Table::new();
put(&mut table, 1, 10);
put(&mut table, 2, 20);
table.insert(TableKey::Integer(1), Value::Integer(1), Value::Nil);
let slots = table.slots().to_vec();
let mut restored = Table::new();
restored.restore(slots);
let (key, _) = restored.next(Some(&TableKey::Integer(1))).unwrap().unwrap();
assert_eq!(key, Value::Integer(2));
assert_eq!(restored.dead_len(), 1);
assert_eq!(restored.raw_border(), 0);
}
#[test]
fn anchors_of_long_string_keys_go_before_their_bytes_pass_the_live_keys() {
let mut table = Table::new();
for key in 0..100 {
put(&mut table, key, key);
}
for round in 0..50u8 {
let key = TableKey::string(vec![round; 1 << 20]);
table.insert(key.clone(), Value::Integer(1), Value::Integer(1));
table.insert(key, Value::Integer(1), Value::Nil);
assert!(table.dead_key_bytes <= table.live_key_bytes + ANCHOR_BYTES + (1 << 20));
}
assert!(table.dead_len() <= 1);
}
}