disklru 0.3.3

// Copyright (C) 2024 Christian Mauduit <ufoot@ufoot.org>

use crate::error::*;
use crate::serial::*;
use serde::de::DeserializeOwned;
use serde::Serialize;
use sled::transaction::{ConflictableTransactionError, TransactionalTree};

pub(crate) fn audit<K, V>(
    db: &TransactionalTree,
) -> std::result::Result<usize, ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned + Eq + Clone + std::fmt::Debug,
    V: Serialize + DeserializeOwned,
{
    let len_struct = audit_general_structure::<K, V>(db)?;
    let len_meta = audit_sizes(db)?;

    if len_struct != len_meta {
        return Err(Error::invalid_data(&format!(
            "metadata len {} does not match links len {}",
            len_meta, len_struct
        ))
        .abort());
    }

    Ok(len_struct)
}

fn audit_sizes(
    db: &TransactionalTree,
) -> std::result::Result<usize, ConflictableTransactionError<Error>> {
    let db_len = get_len(db)?;
    if db_len.is_none() {
        return Err(Error::invalid_data("no len in db").abort());
    }
    let db_capacity = get_capacity(db)?;
    if db_capacity.is_none() {
        return Err(Error::invalid_data("no capacity in db").abort());
    };

    Ok(db_len.unwrap())
}

fn audit_general_structure<K, V>(
    db: &TransactionalTree,
) -> std::result::Result<usize, ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned + Eq + Clone + std::fmt::Debug,
    V: Serialize + DeserializeOwned,
{
    let head = find_head::<K>(db)?;
    match head {
        Some(head) => {
            let mut len = 0;
            let mut pos = head.clone();
            loop {
                let data: Data<K, V> = peek_data_must_exist(db, &pos)?;
                if data.key != pos {
                    return Err(Error::invalid_data(&format!(
                        "data key mismatch, expected \"{:?}\" got
\"{:?}\"",
                        pos, data.key
                    ))
                    .abort());
                };

                let link: Link<K> = peek_link_must_exist(db, &pos)?;
                let prev_link: Link<K> = peek_link_must_exist(db, &link.prev)?;
                if prev_link.next != pos {
                    return Err(Error::invalid_data(&format!(
                        "inconsistent links: {:?}->prev={:?} but {:?}->next={:?}",
                        pos, link.prev, link.prev, prev_link.next,
                    ))
                    .abort());
                }
                let next_link: Link<K> = peek_link_must_exist(db, &link.next)?;
                if next_link.prev != pos {
                    return Err(Error::invalid_data(&format!(
                        "inconsistent links: {:?}->next={:?} but {:?}->prev={:?}",
                        pos, link.next, link.next, next_link.prev,
                    ))
                    .abort());
                }

                len += 1;
                pos = link.next;
                if pos == head {
                    break;
                }
            }
            Ok(len)
        }
        None => Ok(0),
    }
}

pub(crate) fn get_capacity(
    db: &TransactionalTree,
) -> std::result::Result<Option<usize>, ConflictableTransactionError<Error>> {
    let capacity_k = serialize_key_capacity()?;
    let capacity = db.get(capacity_k)?;
    match capacity {
        Some(capacity) => {
            let ret = deserialize_size(capacity)?;
            Ok(Some(ret))
        }
        None => Ok(None),
    }
}

pub(crate) fn set_capacity(
    db: &TransactionalTree,
    capacity: usize,
) -> std::result::Result<(), ConflictableTransactionError<Error>> {
    let capacity_kv = serialize_kv_capacity(capacity)?;
    db.insert(capacity_kv.0, capacity_kv.1)?;
    Ok(())
}

pub(crate) fn get_len(
    db: &TransactionalTree,
) -> std::result::Result<Option<usize>, ConflictableTransactionError<Error>> {
    let len_k = serialize_key_len()?;
    let len = db.get(len_k)?;
    match len {
        Some(len) => {
            let ret = deserialize_size(len)?;
            Ok(Some(ret))
        }
        None => Ok(None),
    }
}

pub(crate) fn set_len(
    db: &TransactionalTree,
    len: usize,
) -> std::result::Result<(), ConflictableTransactionError<Error>> {
    let len_kv = serialize_kv_len(len)?;
    db.insert(len_kv.0, len_kv.1)?;
    Ok(())
}

pub(crate) fn peek_link<K>(
    db: &TransactionalTree,
    k: &K,
) -> std::result::Result<Option<Link<K>>, ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned,
{
    let link_k = serialize_key_link(k)?;
    let link_raw = db.get(link_k)?;
    let ret = match link_raw {
        Some(link_raw) => {
            let link = deserialize_link(link_raw)?;
            Some(link)
        }
        None => None,
    };
    Ok(ret)
}

pub(crate) fn peek_link_must_exist<K>(
    db: &TransactionalTree,
    k: &K,
) -> std::result::Result<Link<K>, ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned,
{
    let link = peek_link(db, k)?;
    match link {
        Some(link) => Ok(link),
        None => Err(Error::report_bug("link not found").abort()),
    }
}

pub(crate) fn create_link<K>(
    db: &TransactionalTree,
    key: &K,
    prev: &K,
    next: &K,
) -> std::result::Result<(), ConflictableTransactionError<Error>>
where
    K: Serialize,
{
    let link_kv = serialize_kv_link(key, prev, next)?;
    let old = db.insert(link_kv.0, link_kv.1)?;
    match old {
        Some(_) => {
            Err(Error::report_bug("can not create link, would overwrite existing version").abort())
        }
        None => Ok(()),
    }
}

pub(crate) fn replace_link<K>(
    db: &TransactionalTree,
    key: &K,
    prev: &K,
    next: &K,
) -> std::result::Result<(), ConflictableTransactionError<Error>>
where
    K: Serialize,
{
    let link_kv = serialize_kv_link(key, prev, next)?;
    let old = db.insert(link_kv.0, link_kv.1)?;
    match old {
        Some(_) => Ok(()),
        None => {
            Err(Error::report_bug("can not replace link, there is no existing version").abort())
        }
    }
}

pub(crate) fn peek_data<K, V>(
    db: &TransactionalTree,
    k: &K,
) -> std::result::Result<Option<Data<K, V>>, ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned,
    V: DeserializeOwned,
{
    let data_k = serialize_key_data(k)?;
    let data_raw = db.get(data_k)?;
    let ret = match data_raw {
        Some(data_raw) => {
            let data: Data<K, V> = deserialize_data(data_raw)?;
            Some(data)
        }
        None => None,
    };
    Ok(ret)
}

pub(crate) fn peek_data_must_exist<K, V>(
    db: &TransactionalTree,
    k: &K,
) -> std::result::Result<Data<K, V>, ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned,
    V: DeserializeOwned,
{
    let data = peek_data(db, k)?;
    match data {
        Some(data) => Ok(data),
        None => Err(Error::report_bug("data not found").abort()),
    }
}

pub(crate) fn create_data<K, V>(
    db: &TransactionalTree,
    key: &K,
    value: &V,
) -> std::result::Result<(), ConflictableTransactionError<Error>>
where
    K: Serialize,
    V: Serialize,
{
    let data_kv = serialize_kv_data(key, value)?;
    let old = db.insert(data_kv.0, data_kv.1)?;
    match old {
        Some(_) => {
            Err(Error::report_bug("can not create data, would overwrite existing version").abort())
        }
        None => Ok(()),
    }
}

pub(crate) fn update_data<K, V>(
    db: &TransactionalTree,
    key: &K,
    value: &V,
) -> std::result::Result<Option<Data<K, V>>, ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned,
    V: Serialize + DeserializeOwned,
{
    let data_kv = serialize_kv_data(key, value)?;
    let old = db.insert(data_kv.0, data_kv.1)?;
    match old {
        Some(old) => {
            let old = deserialize_data(old)?;
            Ok(Some(old))
        }
        None => Ok(None),
    }
}

pub(crate) fn peek_node<K, V>(
    db: &TransactionalTree,
    k: &K,
) -> std::result::Result<Option<Node<K, V>>, ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned,
    V: DeserializeOwned,
{
    let link = peek_link(db, k)?;
    match link {
        Some(link) => {
            let data = peek_data(db, k)?;
            match data {
                Some(data) => Ok(Some(Node { link, data })),
                None => Err(Error::report_bug("link exists, but there is no data").abort()),
            }
        }
        None => Ok(None),
    }
}

pub(crate) fn set_head<K>(
    db: &TransactionalTree,
    k: Option<&K>,
) -> std::result::Result<(), ConflictableTransactionError<Error>>
where
    K: Serialize,
{
    let head_kv = serialize_kv_head(k)?;
    db.insert(head_kv.0, head_kv.1)?;
    Ok(())
}

pub(crate) fn init_head_if_not_exists<K>(
    db: &TransactionalTree,
) -> std::result::Result<(), ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned,
{
    let current_head: Option<K> = find_head(db)?;
    match current_head {
        Some(_) => (),
        None => {
            let head_kv = serialize_kv_head::<K>(None)?;
            db.insert(head_kv.0, head_kv.1)?;
        }
    };
    Ok(())
}

pub(crate) fn find_head<K>(
    db: &TransactionalTree,
) -> std::result::Result<Option<K>, ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned,
{
    let head_k = serialize_key_head()?;
    let head_buf = db.get(head_k)?;
    let ret = match head_buf {
        Some(head_buf) => {
            let ptr: Ptr<K> = deserialize_ptr(head_buf)?;
            ptr.key
        }
        None => None,
    };
    Ok(ret)
}

pub(crate) fn find_head_must_exist<K>(
    db: &TransactionalTree,
) -> std::result::Result<K, ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned,
{
    let head = find_head(db)?;

    match head {
        Some(head) => Ok(head),
        None => Err(Error::report_bug("head not found").abort()),
    }
}

pub(crate) fn find_tail<K>(
    db: &TransactionalTree,
) -> std::result::Result<Option<K>, ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned,
{
    let head: Option<K> = find_head_must_exist(db)?;
    let ret = match head {
        Some(head) => {
            let head_link = peek_link_must_exist(db, &head)?;
            Some(head_link.prev)
        }
        None => None,
    };
    Ok(ret)
}

pub(crate) fn find_tail_must_exist<K>(
    db: &TransactionalTree,
) -> std::result::Result<K, ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned,
{
    let tail: Option<K> = find_tail(db)?;

    match tail {
        Some(tail) => Ok(tail),
        None => Err(Error::report_bug("tail not found").abort()),
    }
}

pub(crate) fn relink_before_insert_or_push<K>(
    db: &TransactionalTree,
    k: &K,
) -> std::result::Result<(), ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned,
{
    let old_head_key = find_head_must_exist::<K>(db)?;
    let old_head_link = peek_link_must_exist(db, &old_head_key)?;
    let old_tail_key = &old_head_link.prev;
    replace_link(db, &old_head_key, k, &old_head_link.next)?;
    let old_tail_link = peek_link_must_exist(db, old_tail_key)?;
    replace_link(db, old_tail_key, &old_tail_link.prev, k)?;
    create_link(db, k, old_tail_key, &old_head_key)?;
    set_head(db, Some(k))?;
    Ok(())
}

fn insert_when_len_is_0<K, V>(
    db: &TransactionalTree,
    k: &K,
    v: &V,
) -> std::result::Result<(), ConflictableTransactionError<Error>>
where
    K: Serialize,
    V: Serialize,
{
    set_head(db, Some(k))?;

    create_data(db, k, v)?;
    create_link(db, k, k, k)?;

    Ok(())
}

fn insert_when_len_is_not_0<K, V>(
    db: &TransactionalTree,
    k: &K,
    v: &V,
    len: usize,
) -> std::result::Result<(Option<V>, usize), ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned + Eq,
    V: Serialize + DeserializeOwned,
{
    let len_after_unlink = unlink::<K>(db, k, len)?;
    if len_after_unlink == 0 {
        insert_when_len_is_0(db, k, v)?;
        return Ok((None, 1));
    };

    relink_before_insert_or_push(db, k)?;

    let old = update_data(db, k, v)?;
    match old {
        Some(old) => {
            if len_after_unlink < len {
                Ok((Some(old.value), len))
            } else {
                Err(Error::report_bug("unlink but there was no data").abort())
            }
        }
        None => {
            if len_after_unlink == len {
                Ok((None, len + 1))
            } else {
                Err(Error::report_bug("no unlink, but there was data").abort())
            }
        }
    }
}

fn insert_when_head_is_same<K, V>(
    db: &TransactionalTree,
    k: &K,
    v: &V,
) -> std::result::Result<V, ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned,
    V: Serialize + DeserializeOwned,
{
    let old = update_data(db, k, v)?;
    match old {
        Some(old) => Ok(old.value),
        None => Err(Error::report_bug("inserting on head, but there is no data").abort()),
    }
}

pub(crate) fn insert<K, V>(
    db: &TransactionalTree,
    k: &K,
    v: &V,
    len: usize,
) -> std::result::Result<(Option<V>, usize), ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned + Eq,
    V: Serialize + DeserializeOwned,
{
    let (ret_v, ret_l) = match len {
        0 => {
            insert_when_len_is_0(db, k, v)?;
            (None, 1)
        }
        l => {
            let head: K = find_head_must_exist(db)?;
            if k == &head {
                let old = insert_when_head_is_same(db, k, v)?;
                (Some(old), len)
            } else {
                let ret = insert_when_len_is_not_0(db, k, v, l)?;
                ret
            }
        }
    };

    if ret_l != len {
        set_len(db, ret_l)?;
    }

    Ok((ret_v, ret_l))
}

fn push_relink_when_len_is_0<K>(
    db: &TransactionalTree,
    k: &K,
) -> std::result::Result<(), ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned,
{
    set_head(db, Some(k))?;
    create_link(db, k, k, k)?;
    Ok(())
}

fn push_relink_when_len_is_not_0<K>(
    db: &TransactionalTree,
    k: &K,
    len: usize,
) -> std::result::Result<usize, ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned + Eq,
{
    let len_after_unlink = unlink::<K>(db, k, len)?;
    if len_after_unlink == 0 {
        push_relink_when_len_is_0(db, k)?;
        return Ok(1);
    };

    relink_before_insert_or_push(db, k)?;
    Ok(len_after_unlink + 1)
}

pub(crate) fn push<K, V>(
    db: &TransactionalTree,
    k: &K,
    v: &V,
    len: usize,
    capacity: usize,
) -> std::result::Result<(Option<(K, V)>, usize), ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned + Eq,
    V: Serialize + DeserializeOwned,
{
    let key_link = peek_link(db, k)?;
    let (ret_kv, new_len) = if len >= capacity && key_link.is_none() {
        let (ret_kv, new_len) = pop_tail_must_exist_no_len_update(db, len)?;
        (Some(ret_kv), new_len)
    } else {
        (None, len)
    };

    let data_kv = serialize_kv_data(k, v)?;
    db.insert(data_kv.0, data_kv.1)?;

    let ret_len = match new_len {
        0 => {
            push_relink_when_len_is_0(db, k)?;
            1
        }
        l => {
            let head: K = find_head_must_exist(db)?;
            if k == &head {
                l
            } else {
                let ret = push_relink_when_len_is_not_0(db, k, l)?;
                ret
            }
        }
    };

    if ret_len != len {
        set_len(db, ret_len)?;
    }

    Ok((ret_kv, ret_len))
}

fn unlink_when_len_is_1<K>(
    db: &TransactionalTree,
    k: &K,
) -> std::result::Result<usize, ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned,
{
    let link_k = serialize_key_link(k)?;
    let old_link = db.remove(link_k)?;
    match old_link {
        Some(_) => {
            set_head::<K>(db, None)?;
            Ok(0)
        }
        None => Ok(1),
    }
}

fn unlink_when_len_is_ge_2<K>(
    db: &TransactionalTree,
    k: &K,
    len: usize,
) -> std::result::Result<usize, ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned + Eq,
{
    let link_k = serialize_key_link(k)?;
    let old_link = db.remove(link_k)?;
    match old_link {
        Some(old_link) => {
            let old_link: Link<K> = deserialize_link(old_link)?;
            let old_prev = peek_link_must_exist(db, &old_link.prev)?;
            replace_link(db, &old_link.prev, &old_prev.prev, &old_link.next)?;
            let old_next = peek_link_must_exist(db, &old_link.next)?;
            replace_link(db, &old_link.next, &old_link.prev, &old_next.next)?;
            let old_head = find_head_must_exist::<K>(db)?;
            if &old_head == k {
                set_head(db, Some(&old_link.next))?;
            }
            Ok(len - 1)
        }
        None => Ok(len),
    }
}

fn unlink<K>(
    db: &TransactionalTree,
    k: &K,
    len: usize,
) -> std::result::Result<usize, ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned + Eq,
{
    match len {
        0 => return Ok(0),
        1 => {
            let l = unlink_when_len_is_1(db, k)?;
            Ok(l)
        }
        l => {
            let l = unlink_when_len_is_ge_2(db, k, l)?;
            Ok(l)
        }
    }
}

pub(crate) fn remove<K, V>(
    db: &TransactionalTree,
    k: &K,
    len: usize,
) -> std::result::Result<(Option<V>, usize), ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned + Eq,
    V: DeserializeOwned,
{
    let popped = pop(db, k, len)?;

    match popped.0 {
        Some(p) => Ok((Some(p.1), popped.1)),
        None => Ok((None, popped.1)),
    }
}

pub(crate) fn forget<K>(
    db: &TransactionalTree,
    k: &K,
    len: usize,
) -> std::result::Result<usize, ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned + Eq,
{
    let new_len = unlink(db, k, len)?;

    if new_len < len {
        let data_k = serialize_key_data(k)?;
        let old_data = db.remove(data_k)?;
        if old_data.is_none() {
            return Err(Error::report_bug("link removed (forget), but there was no data").abort());
        }
    }

    if new_len != len {
        set_len(db, new_len)?;
    }

    Ok(new_len)
}

pub(crate) fn forget_tail_must_exist<K>(
    db: &TransactionalTree,
    len: usize,
) -> std::result::Result<usize, ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned + Eq,
{
    let tail: K = find_tail_must_exist(db)?;
    let new_len = forget(db, &tail, len)?;

    if new_len != len {
        set_len(db, new_len)?;
    }

    Ok(new_len)
}

fn pop_tail_must_exist_no_len_update<K, V>(
    db: &TransactionalTree,
    len: usize,
) -> std::result::Result<((K, V), usize), ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned + Eq,
    V: DeserializeOwned,
{
    let k: K = find_tail_must_exist(db)?;
    unlink(db, &k, len)?;
    let data_k = serialize_key_data(&k)?;
    let old_data = db.remove(data_k)?;
    let (ret_kv, ret_len) = match old_data {
        Some(old_data) => {
            let data: Data<K, V> = deserialize_data(old_data)?;
            ((data.key, data.value), len - 1)
        }
        None => {
            return Err(Error::report_bug("can not pop tail, no data").abort());
        }
    };

    Ok((ret_kv, ret_len))
}

pub(crate) fn pop_tail_must_exist<K, V>(
    db: &TransactionalTree,
    len: usize,
) -> std::result::Result<((K, V), usize), ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned + Eq,
    V: DeserializeOwned,
{
    let (ret_kv, ret_len) = pop_tail_must_exist_no_len_update(db, len)?;

    if ret_len != len {
        set_len(db, ret_len)?;
    }

    Ok((ret_kv, ret_len))
}

pub(crate) fn pop<K, V>(
    db: &TransactionalTree,
    k: &K,
    len: usize,
) -> std::result::Result<(Option<(K, V)>, usize), ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned + Eq,
    V: DeserializeOwned,
{
    let new_len = unlink(db, k, len)?;

    let kv = if new_len < len {
        let data_k = serialize_key_data(k)?;
        let old_data = db.remove(data_k)?;
        match old_data {
            Some(old_data) => {
                let old_data: Data<K, V> = deserialize_data(old_data)?;
                Some((old_data.key, old_data.value))
            }
            None => {
                return Err(Error::report_bug("link removed, but there was no data").abort());
            }
        }
    } else {
        None
    };

    if new_len != len {
        set_len(db, new_len)?;
    }

    Ok((kv, new_len))
}

fn relink_after_get<K>(
    db: &TransactionalTree,
    k: &K,
) -> std::result::Result<(), ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned + Eq,
{
    let old_head_key = find_head_must_exist(db)?;

    if k == &old_head_key {
        return Ok(());
    }

    set_head(db, Some(k))?;

    let old_head = peek_link_must_exist(db, &old_head_key)?;
    let old_tail_key = &old_head.prev;
    if k == old_tail_key {
        // Small optimisation, we're getting the LRU, so the
        // order does not really change, just move the head pointer.
        return Ok(());
    }

    replace_link(db, &old_head_key, k, &old_head.next)?;
    let old_tail = peek_link_must_exist(db, old_tail_key)?;
    replace_link(db, old_tail_key, &old_tail.prev, k)?;

    let new_head = peek_link_must_exist(db, k)?;
    let old_new_head_next_key = &new_head.next;
    let old_new_head_prev_key = &new_head.prev;
    let old_new_head_next = peek_link_must_exist(db, old_new_head_next_key)?;
    let old_new_head_prev = peek_link_must_exist(db, old_new_head_prev_key)?;

    replace_link(
        db,
        old_new_head_next_key,
        old_new_head_prev_key,
        &old_new_head_next.next,
    )?;

    replace_link(
        db,
        old_new_head_prev_key,
        &old_new_head_prev.prev,
        old_new_head_next_key,
    )?;

    replace_link(db, k, old_tail_key, &old_head_key)?;

    Ok(())
}

pub(crate) fn get_data<K, V>(
    db: &TransactionalTree,
    k: &K,
) -> std::result::Result<Option<Data<K, V>>, ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned + Eq,
    V: DeserializeOwned,
{
    let data = peek_data(db, k)?;
    match data {
        Some(data) => {
            relink_after_get(db, k)?;
            Ok(Some(data))
        }
        None => Ok(None),
    }
}

pub(crate) fn bump<K>(
    db: &TransactionalTree,
    k: &K,
) -> std::result::Result<(), ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned + Eq,
{
    let contains_key = contains_key(db, k)?;
    if contains_key {
        relink_after_get(db, k)?;
    }
    Ok(())
}

pub(crate) fn contains_key<K>(
    db: &TransactionalTree,
    k: &K,
) -> std::result::Result<bool, ConflictableTransactionError<Error>>
where
    K: Serialize + DeserializeOwned + Eq,
{
    let link_k = serialize_key_link(k)?;
    let link = db.get(link_k)?;
    Ok(!link.is_none())
}