use crate::ordered::OrderedMap;
use std::cmp::Ordering;
pub const MIN_BLOCK_HANDLE_LENGTH: usize = 4;
const ALPHABET: &[u8; 64] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_";
pub(crate) const HANDLE_KEY_LENGTH: usize = 11;
pub(crate) fn handle_key(id: &str) -> String {
let mut h1: u32 = 0xdeadbeef;
let mut h2: u32 = 0x41c6ce57;
for c in id.encode_utf16() {
h1 = (h1 ^ u32::from(c)).wrapping_mul(2654435761);
h2 = (h2 ^ u32::from(c)).wrapping_mul(1597334677);
}
h1 = (h1 ^ (h1 >> 16)).wrapping_mul(2246822507);
h1 ^= (h2 ^ (h2 >> 13)).wrapping_mul(3266489909);
h2 = (h2 ^ (h2 >> 16)).wrapping_mul(2246822507);
h2 ^= (h1 ^ (h1 >> 13)).wrapping_mul(3266489909);
let mut key = String::with_capacity(HANDLE_KEY_LENGTH);
let mut bit: i32 = 0;
while bit < 64 {
let value = if bit + 6 <= 32 {
h2 >> (26 - bit)
} else if bit >= 32 {
let shift = 26 - (bit - 32);
if shift >= 0 {
h1 >> shift
} else {
h1 << -shift
}
} else {
let low = bit + 6 - 32;
(h2 << low) | (h1 >> (32 - low))
};
key.push(ALPHABET[(value & 63) as usize] as char);
bit += 6;
}
key
}
pub(crate) struct HandleTable {
pub(crate) sorted: Vec<String>,
pub(crate) ids_of_key: OrderedMap<Vec<String>>,
pub(crate) handles: OrderedMap<String>,
}
fn common_prefix_length(a: &str, b: &str) -> usize {
a.bytes().zip(b.bytes()).take_while(|(x, y)| x == y).count()
}
fn handle_between(key: &str, prev: Option<&str>, next: Option<&str>) -> String {
let mut length = MIN_BLOCK_HANDLE_LENGTH;
if let Some(prev) = prev {
length = length.max(common_prefix_length(key, prev) + 1);
}
if let Some(next) = next {
length = length.max(common_prefix_length(key, next) + 1);
}
key[..length.min(key.len())].to_owned()
}
fn lower_bound(sorted: &[String], value: &str) -> usize {
sorted.partition_point(|key| crate::utf16::cmp(key, value) == Ordering::Less)
}
#[cfg(test)]
thread_local! {
pub(crate) static BUILD_HANDLE_TABLE_CALLS: std::cell::Cell<usize> =
const { std::cell::Cell::new(0) };
}
pub(crate) fn build_handle_table<'a>(ids: impl IntoIterator<Item = &'a str>) -> HandleTable {
#[cfg(test)]
BUILD_HANDLE_TABLE_CALLS.with(|calls| calls.set(calls.get() + 1));
let mut ids_of_key: OrderedMap<Vec<String>> = OrderedMap::new();
let mut seen = crate::ordered::OrderedSet::new();
for id in ids {
if seen.contains(id) {
continue;
}
seen.add(id);
let key = handle_key(id);
match ids_of_key.get_mut(&key) {
Some(list) => list.push(id.to_owned()),
None => ids_of_key.set(&key, vec![id.to_owned()]),
}
}
let mut sorted: Vec<String> = ids_of_key.keys().map(str::to_owned).collect();
sorted.sort_by(|a, b| crate::utf16::cmp(a, b));
let mut handles = OrderedMap::new();
for (i, key) in sorted.iter().enumerate() {
let prev = i.checked_sub(1).map(|j| sorted[j].as_str());
let next = sorted.get(i + 1).map(String::as_str);
let handle = handle_between(key, prev, next);
for id in ids_of_key.get(key).expect("a key of the table") {
handles.set(id, handle.clone());
}
}
HandleTable {
sorted,
ids_of_key,
handles,
}
}
pub(crate) fn handle_in_table(table: &HandleTable, id: &str) -> String {
if let Some(known) = table.handles.get(id) {
return known.clone();
}
let key = handle_key(id);
let sorted = &table.sorted;
let i = lower_bound(sorted, &key);
let at = sorted.get(i).map(String::as_str);
let next = if at == Some(key.as_str()) {
sorted.get(i + 1).map(String::as_str)
} else {
at
};
let prev = i.checked_sub(1).map(|j| sorted[j].as_str());
handle_between(&key, prev, next)
}
pub(crate) fn ids_with_prefix(table: &HandleTable, prefix: &str) -> Vec<String> {
let mut result = Vec::new();
let mut i = lower_bound(&table.sorted, prefix);
while i < table.sorted.len() && table.sorted[i].starts_with(prefix) {
result.extend(
table
.ids_of_key
.get(&table.sorted[i])
.expect("a key of the table")
.iter()
.cloned(),
);
i += 1;
}
result
}