NEW BOT Телеграм, страница

Запишем сначала определение интернированной строки:

#[derive(Clone, Copy, PartialEq, Eq)]
pub struct InternedStr<'a> {
    ptr: NonNull<u8>,
    _lt: PhantomData<&'a ()>,
}

impl<'a> InternedStr<'a> {
    // Конструктор unsafe, потому что корректность
    // времён жизни нужно обеспечивать пользователю
    unsafe fn from_ptr(ptr: NonNull<u8>) -> Self {
        Self {
            ptr,
            _lt: PhantomData,
        }
    }
}

Самая полезная операция для это строки — перевод в &str. Для этого нам нужно считать размер строки из начала аллокации, сдвинуть указатель на размер usize и сделать толстый указатель из полученного тонкого и длины:

const USIZE_SIZE: usize = std::mem::size_of::<usize>();

impl<'a> InternedStr<'a> {
    pub fn as_str(self) -> &'a str {
        let len = unsafe { self.ptr.cast::<usize>().read() };
        let ptr = unsafe { self.ptr.add(USIZE_SIZE) };
        unsafe {
            str::from_utf8_unchecked(
                std::slice::from_raw_parts(
                    ptr.as_ptr(),
                    len
                )
            )
        }
    }
}

Теперь немного подумаем о том, как будет выглядеть пул строк. Очевидно, нам нужен Bump для выделения памяти. Также нам всё ещё нужно иметь возможность быстро определять, записали мы строку или нет, поэтому в пул нужно включить HashSet<InternedStr<'_>>.

Со вторым полем есть пара вопросов.

Во-первых, какое именно время жизни нужно вписать для хранимых InternedStr? Технически мы заимствуем память из соседнего поля типа Bump, то есть определение является самоссылающимся типом. Воспользуемся типичным для такой ситуации подходом: будем хранить в множестве InternedStr<'static>, а безопасность это, вообще говоря, некорректного времени жизни будем обеспечивать API, который будет выдавать строки со временем жизни, привязанным к пулу строк.

Во-вторых, что делать с мутабельностью? Выделение новых строк в памяти, очевидно, требует модификации множества, но если мы запишем метод вида

fn alloc(&mut self, s: &str) -> InternedStr<'_> { ... }

, то из-за исключительного заимствования пулом будет невозможно пользоваться, пока возвращённая строка не будет дропнута. Очевидно, здесь требуется внутренняя изменяемость, и так как Bump и так !Sync, достаточно немногопоточного RefCell.

Итого определение выглядит так:

const USIZE_ALIGN: usize = std::mem::align_of::<usize>();

#[derive(Default)]
pub struct Interner<S = std::collections::hash_map::RandomState> {
    strs: RefCell<HashSet<InternedStr<'static>, S>>,
    mem: Bump<{ USIZE_ALIGN }>,
}

Bump параметризован минимальным выравниванием для аллокаций. Выравнивание для usize позволяет нам использовать выровненный доступ к длине в InternedStr::as_str, то есть read вместо read_unaligned.

Запишем реализацию метода для выделения строки:

    pub fn alloc(&self, s: &str) -> InternedStr<'_> {
        ...

Для начала нужно проверить, записана ли вообще уже строка. Если да, то сразу возвращаем её — в этом и состоит смысл интернирования:

        ...
        let mut strs = self.strs.borrow_mut();
        if let Some(&interned) = strs.get(s) {
            return interned;
        }
        ...

Теперь нужно выделить память под строку и под длину строки. У Bump есть много методов выделения памяти, но почти все из них подразумевают, что значение для аллокации уже есть в наличии. В нашем случае это не так, поэтому мы воспользуемся методом, который возвращает неинициализированную память: Bump::alloc_layout.

(тут на самом деле можно попенять авторов, потому что этот метод почему-то возвращает NonNull<u8> вместо гораздо более эргономичного &mut [MaybeUninit<u8>])

❤1👍1

719 views18:22