aboutsummaryrefslogtreecommitdiff
path: root/database/src/kv
diff options
context:
space:
mode:
Diffstat (limited to 'database/src/kv')
-rw-r--r--database/src/kv/binning.rs148
-rw-r--r--database/src/kv/counters.rs59
-rw-r--r--database/src/kv/mod.rs217
-rw-r--r--database/src/kv/prefix_iterator.rs22
-rw-r--r--database/src/kv/sort/mod.rs29
-rw-r--r--database/src/kv/sort/none.rs50
-rw-r--r--database/src/kv/sort/value.rs86
7 files changed, 611 insertions, 0 deletions
diff --git a/database/src/kv/binning.rs b/database/src/kv/binning.rs
new file mode 100644
index 0000000..7bec294
--- /dev/null
+++ b/database/src/kv/binning.rs
@@ -0,0 +1,148 @@
+/*
+ This file is part of jellything (https://codeberg.org/metamuffin/jellything)
+ which is licensed under the GNU Affero General Public License (version 3); see /COPYING.
+ Copyright (C) 2026 metamuffin <metamuffin.org>
+*/
+
+use jellyobject::{Object, Path};
+
+use crate::Filter;
+
+/// Sorted list of components to bin objects by filterable values.
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+pub struct Binning(Vec<BinningComponent>);
+
+#[derive(Debug, Clone, PartialEq, PartialOrd, Eq, Ord, Hash)]
+pub enum BinningComponent {
+ Has(Path),
+ Match(Path),
+}
+
+impl Binning {
+ pub fn new(mut comps: Vec<BinningComponent>) -> Self {
+ comps.sort();
+ Self(comps)
+ }
+ pub fn apply(&self, ob: Object<'_>, keys: &mut Vec<Vec<u8>>) {
+ for f in &self.0 {
+ f.apply(ob, keys);
+ }
+ }
+}
+impl BinningComponent {
+ pub fn apply(&self, ob: Object<'_>, keys: &mut Vec<Vec<u8>>) {
+ match self {
+ BinningComponent::Has(path) => {
+ let has = path.get_matching_value(ob).is_some();
+ for co in keys {
+ co.push(has as u8)
+ }
+ }
+ BinningComponent::Match(path) => {
+ let mut new_out = Vec::new();
+ for value in path.get_matching_values(ob) {
+ for mut co in keys.clone() {
+ co.extend((co.len() as u32).to_be_bytes());
+ co.extend(value);
+ new_out.push(co);
+ }
+ }
+ *keys = new_out;
+ }
+ }
+ }
+}
+
+impl Filter {
+ pub fn get_bins(&self) -> Vec<Binning> {
+ fn recurse(f: &Filter) -> Vec<Vec<BinningComponent>> {
+ match f {
+ Filter::True => vec![vec![]],
+ Filter::All(filters) => {
+ let mut o = vec![vec![]];
+ for filter in filters {
+ let mut new_o = Vec::new();
+ for par in recurse(filter) {
+ for mut prev in o.clone() {
+ prev.extend(par.clone());
+ new_o.push(prev);
+ }
+ }
+ o = new_o;
+ }
+ o
+ }
+ Filter::Any(filters) => filters.iter().flat_map(|f| recurse(f)).collect(),
+ Filter::Match(path, _) => vec![vec![BinningComponent::Match(path.to_owned())]],
+ Filter::Has(path) => vec![vec![BinningComponent::Has(path.to_owned())]],
+ }
+ }
+ recurse(self).into_iter().map(Binning::new).collect()
+ }
+}
+
+#[cfg(test)]
+mod test {
+ use jellyobject::{Path, Tag};
+
+ use crate::{Filter, kv::binning::{Binning, BinningComponent}};
+
+ #[test]
+ fn all() {
+ let f = Filter::All(vec![
+ Filter::Has(Path(vec![Tag(0)])),
+ Filter::Has(Path(vec![Tag(1)])),
+ ]);
+ let bins = vec![Binning::new(vec![
+ BinningComponent::Has(Path(vec![Tag(0)])),
+ BinningComponent::Has(Path(vec![Tag(1)])),
+ ])];
+ assert_eq!(f.get_bins(), bins)
+ }
+
+ #[test]
+ fn any() {
+ let f = Filter::Any(vec![
+ Filter::Has(Path(vec![Tag(0)])),
+ Filter::Has(Path(vec![Tag(1)])),
+ ]);
+ let bins = vec![
+ Binning::new(vec![BinningComponent::Has(Path(vec![Tag(0)]))]),
+ Binning::new(vec![BinningComponent::Has(Path(vec![Tag(1)]))]),
+ ];
+ assert_eq!(f.get_bins(), bins)
+ }
+
+ #[test]
+ fn nested() {
+ let f = Filter::All(vec![
+ Filter::Any(vec![
+ Filter::Has(Path(vec![Tag(0)])),
+ Filter::Has(Path(vec![Tag(1)])),
+ ]),
+ Filter::Any(vec![
+ Filter::Has(Path(vec![Tag(2)])),
+ Filter::Has(Path(vec![Tag(3)])),
+ ]),
+ ]);
+ let bins = vec![
+ Binning::new(vec![
+ BinningComponent::Has(Path(vec![Tag(0)])),
+ BinningComponent::Has(Path(vec![Tag(2)])),
+ ]),
+ Binning::new(vec![
+ BinningComponent::Has(Path(vec![Tag(1)])),
+ BinningComponent::Has(Path(vec![Tag(2)])),
+ ]),
+ Binning::new(vec![
+ BinningComponent::Has(Path(vec![Tag(0)])),
+ BinningComponent::Has(Path(vec![Tag(3)])),
+ ]),
+ Binning::new(vec![
+ BinningComponent::Has(Path(vec![Tag(1)])),
+ BinningComponent::Has(Path(vec![Tag(3)])),
+ ]),
+ ];
+ assert_eq!(f.get_bins(), bins)
+ }
+}
diff --git a/database/src/kv/counters.rs b/database/src/kv/counters.rs
new file mode 100644
index 0000000..fae7b42
--- /dev/null
+++ b/database/src/kv/counters.rs
@@ -0,0 +1,59 @@
+/*
+ This file is part of jellything (https://codeberg.org/metamuffin/jellything)
+ which is licensed under the GNU Affero General Public License (version 3); see /COPYING.
+ Copyright (C) 2026 metamuffin <metamuffin.org>
+*/
+use crate::{
+ Query, RowNum,
+ kv::{self, TableNum, binning::Binning},
+};
+use anyhow::Result;
+use jellyobject::Object;
+use std::collections::HashMap;
+
+pub(crate) struct Counters(pub HashMap<Binning, TableNum>);
+impl Counters {
+ pub fn update(
+ &self,
+ txn: &mut dyn jellykv::Transaction,
+ ob: Object<'_>,
+ remove: bool,
+ ) -> Result<()> {
+ for (b, &table) in &self.0 {
+ let mut k = vec![vec![]];
+ b.apply(ob, &mut k);
+ if k.is_empty() {
+ continue;
+ }
+ let mut counter = read_counter(txn, table)?;
+ if remove {
+ counter += k.len() as u64;
+ } else {
+ counter -= k.len() as u64;
+ }
+ write_counter(txn, table, counter)?;
+ }
+ Ok(())
+ }
+ pub fn count(&self, txn: &dyn jellykv::Transaction, query: &Query) -> Result<Option<u64>> {
+ let mut total = 0;
+ for binning in query.filter.get_bins() {
+ let Some(b) = self.0.get(&binning) else {
+ return Ok(None);
+ };
+ total += read_counter(txn, *b)?;
+ }
+ Ok(Some(total))
+ }
+}
+
+pub fn write_counter(txn: &mut dyn jellykv::Transaction, t: TableNum, value: u64) -> Result<()> {
+ txn.set(&t.to_be_bytes(), &value.to_be_bytes())
+}
+pub fn read_counter(txn: &dyn jellykv::Transaction, t: TableNum) -> Result<u64> {
+ Ok(txn
+ .get(&t.to_be_bytes())?
+ .map(|k| k.as_slice().try_into().map(RowNum::from_be_bytes).ok())
+ .flatten()
+ .unwrap_or(0))
+}
diff --git a/database/src/kv/mod.rs b/database/src/kv/mod.rs
new file mode 100644
index 0000000..b4bd000
--- /dev/null
+++ b/database/src/kv/mod.rs
@@ -0,0 +1,217 @@
+/*
+ This file is part of jellything (https://codeberg.org/metamuffin/jellything)
+ which is licensed under the GNU Affero General Public License (version 3); see /COPYING.
+ Copyright (C) 2026 metamuffin <metamuffin.org>
+*/
+
+pub mod binning;
+pub mod counters;
+pub mod prefix_iterator;
+pub mod sort;
+
+use crate::{
+ Database, Query, RowIter, RowNum, Transaction,
+ kv::{binning::Binning, sort::SortKey},
+};
+use anyhow::Result;
+use jellyobject::ObjectBuffer;
+
+pub type IndexKey = (Binning, SortKey);
+pub type TableNum = u32;
+
+impl<T: jellykv::Store> Database for T {
+ fn transaction(&self, f: &mut dyn FnMut(&mut dyn Transaction) -> Result<()>) -> Result<()> {
+ todo!()
+ }
+}
+
+impl<T: jellykv::Transaction> Transaction for T {
+ fn insert(&self, entry: ObjectBuffer) -> Result<RowNum> {
+ todo!()
+ }
+
+ fn get(&self, row: RowNum) -> Result<Option<ObjectBuffer>> {
+ todo!()
+ }
+
+ fn remove(&self, row: RowNum) -> Result<()> {
+ todo!()
+ }
+
+ fn update(&self, row: RowNum, entry: ObjectBuffer) -> Result<()> {
+ todo!()
+ }
+
+ fn query(&self, query: Query) -> Result<RowIter> {
+ todo!()
+ }
+
+ fn query_single(&self, query: Query) -> Result<Option<RowNum>> {
+ todo!()
+ }
+
+ fn count(&self, query: Query) -> Result<u64> {
+ todo!()
+ }
+}
+
+// pub struct Table {
+// id: TableNum,
+// pub(crate) counters: HashMap<Binning, TableNum>,
+// pub(crate) indices: HashMap<IndexKey, TableNum>,
+// }
+// impl Table {
+// pub fn new(id: u32) -> Self {
+// Self {
+// id,
+// counters: HashMap::new(),
+// indices: HashMap::new(),
+// }
+// }
+// fn key(&self, row: RowNum) -> Vec<u8> {
+// let mut key = Vec::new();
+// key.extend(self.id.to_be_bytes());
+// key.extend(row.to_be_bytes());
+// key
+// }
+// pub fn iter(&self, txn: &dyn ReadTransaction) -> Result<impl Iterator<Item = Result<RowNum>>> {
+// Ok(PrefixIterator {
+// inner: txn.iter(&self.id.to_be_bytes(), false)?,
+// prefix: self.id.to_be_bytes().to_vec().into(),
+// }
+// .map(|r| r.map(|r| RowNum::from_be_bytes(r.try_into().unwrap()))))
+// }
+// pub fn insert(&self, txn: &mut dyn WriteTransaction, entry: ObjectBuffer) -> Result<RowNum> {
+// let mut id_counter = read_counter(txn, self.id)?;
+// let row = id_counter;
+// id_counter += 1;
+// write_counter(txn, self.id, id_counter)?;
+
+// txn.set(&self.key(row), bytemuck::cast_slice(entry.0.as_slice()))?;
+
+// let ob = entry.as_object();
+// // for idx in self.indices.values() {
+// // idx.add(txn, row, ob)?;
+// // }
+
+// Ok(row)
+// }
+// pub fn get(&self, txn: &dyn ReadTransaction, row: RowNum) -> Result<Option<ObjectBuffer>> {
+// Ok(txn.get(&self.key(row))?.map(ObjectBuffer::from))
+// }
+// pub fn remove(&self, db: &mut dyn WriteTransaction, row: RowNum) -> Result<bool> {
+// let Some(entry) = self.get(db, row)? else {
+// return Ok(false);
+// };
+// let ob = entry.as_object();
+// // for index in self.indices.values() {
+// // index.remove(db, row, ob)?;
+// // }
+// db.del(&self.key(row))?;
+// Ok(true)
+// }
+// pub fn update(
+// &self,
+// txn: &mut dyn WriteTransaction,
+// row: RowNum,
+// entry: ObjectBuffer,
+// ) -> Result<()> {
+// let before = self
+// .get(txn, row)?
+// .ok_or(anyhow!("row to update missing"))?;
+// let before = before.as_object();
+// let after = entry.as_object();
+
+// txn.set(&self.key(row), bytemuck::cast_slice(entry.0.as_slice()))?;
+
+// // for index in self.indices.values() {
+// // if !index.compare(before, after) {
+// // index.remove(txn, row, before)?;
+// // index.add(txn, row, after)?;
+// // }
+// // }
+
+// Ok(())
+// }
+// pub fn query(&self, txn: &dyn ReadTransaction, query: Query) -> Result<RowIter> {
+// // query
+// // .filter
+// // .get_bins()
+// // .into_iter()
+// // .flat_map(|b| {
+// // let ikey = (b, query.sort.key());
+// // self.indices.get(&ikey)
+// // })
+// // .map(|i| i.query(txn, &query.sort))
+// todo!()
+// }
+// pub fn query_single(&self, txn: &dyn ReadTransaction, query: Query) -> Result<Option<RowNum>> {
+// self.query(txn, query)?.next().transpose()
+// }
+// pub fn count(&self, txn: &dyn ReadTransaction, query: Query) -> Result<u64> {
+// let mut total = 0;
+// for b in query.filter.get_bins() {
+// if let Some(&c) = self.counters.get(&b) {
+// total += read_counter(txn, c)?;
+// }
+// }
+// Ok(total)
+// }
+// }
+
+// #[cfg(test)]
+// mod test {
+// use {
+// table::Table,
+// test_shared::{NAME, new_bob},
+// };
+// use anyhow::Result;
+// use jellykv::Database;
+
+// #[test]
+// pub fn insert_get() -> Result<()> {
+// let db = jellykv::memory::new();
+// let table = Table::new(5);
+
+// let mut bob_row = 0;
+// db.write_transaction(&mut |txn| {
+// bob_row = table.insert(txn, new_bob())?;
+// Ok(())
+// })?;
+
+// let mut bob = None;
+// db.read_transaction(&mut |txn| {
+// bob = table.get(txn, bob_row)?;
+// Ok(())
+// })?;
+
+// assert_eq!(bob.unwrap().as_object().get(NAME).unwrap(), "Bob");
+// Ok(())
+// }
+
+// #[test]
+// pub fn update() -> Result<()> {
+// let db = jellykv::memory::new();
+// let table = Table::new(5);
+
+// let mut bob_row = 0;
+// let mut bob = None;
+
+// db.write_transaction(&mut |txn| {
+// bob_row = table.insert(txn, new_bob())?;
+// Ok(())
+// })?;
+// db.write_transaction(&mut |txn| {
+// let better_bob = new_bob().as_object().insert(NAME, "Better Bob");
+// table.update(txn, bob_row, better_bob)?;
+// Ok(())
+// })?;
+// db.read_transaction(&mut |txn| {
+// bob = table.get(txn, bob_row)?;
+// Ok(())
+// })?;
+
+// assert_eq!(bob.unwrap().as_object().get(NAME).unwrap(), "Better Bob");
+// Ok(())
+// }
+// }
diff --git a/database/src/kv/prefix_iterator.rs b/database/src/kv/prefix_iterator.rs
new file mode 100644
index 0000000..9a73558
--- /dev/null
+++ b/database/src/kv/prefix_iterator.rs
@@ -0,0 +1,22 @@
+/*
+ This file is part of jellything (https://codeberg.org/metamuffin/jellything)
+ which is licensed under the GNU Affero General Public License (version 3); see /COPYING.
+ Copyright (C) 2026 metamuffin <metamuffin.org>
+*/
+
+use anyhow::Result;
+use std::borrow::Cow;
+
+pub struct PrefixIterator<'a> {
+ pub inner: Box<dyn Iterator<Item = Result<Vec<u8>>> + 'a>,
+ pub prefix: Cow<'a, [u8]>,
+}
+impl Iterator for PrefixIterator<'_> {
+ type Item = Result<Vec<u8>>;
+ fn next(&mut self) -> Option<Self::Item> {
+ self.inner.next().filter(|k| match k {
+ Ok(v) => v.starts_with(&self.prefix),
+ Err(_) => true,
+ })
+ }
+}
diff --git a/database/src/kv/sort/mod.rs b/database/src/kv/sort/mod.rs
new file mode 100644
index 0000000..403ba73
--- /dev/null
+++ b/database/src/kv/sort/mod.rs
@@ -0,0 +1,29 @@
+/*
+ This file is part of jellything (https://codeberg.org/metamuffin/jellything)
+ which is licensed under the GNU Affero General Public License (version 3); see /COPYING.
+ Copyright (C) 2026 metamuffin <metamuffin.org>
+*/
+
+use jellyobject::Path;
+
+use crate::{MultiBehaviour, Sort};
+
+pub mod none;
+pub mod value;
+
+#[derive(Hash, PartialEq, Eq)]
+pub enum SortKey {
+ None,
+ Value(Path, MultiBehaviour),
+ Text(Path),
+}
+
+impl Sort {
+ pub fn key(&self) -> SortKey {
+ match self {
+ Sort::None => SortKey::None,
+ Sort::Value(vs) => SortKey::Value(vs.path.clone(), vs.multi),
+ Sort::TextSearch(p, _) => SortKey::Text(p.to_owned()),
+ }
+ }
+}
diff --git a/database/src/kv/sort/none.rs b/database/src/kv/sort/none.rs
new file mode 100644
index 0000000..b4d5db2
--- /dev/null
+++ b/database/src/kv/sort/none.rs
@@ -0,0 +1,50 @@
+/*
+ This file is part of jellything (https://codeberg.org/metamuffin/jellything)
+ which is licensed under the GNU Affero General Public License (version 3); see /COPYING.
+ Copyright (C) 2026 metamuffin <metamuffin.org>
+*/
+
+use crate::{
+ RowNum,
+ kv::{TableNum, binning::Binning},
+};
+use jellyobject::Object;
+
+pub struct UnsortedIndex {
+ id: TableNum,
+ binning: Binning,
+}
+
+impl UnsortedIndex {
+ pub fn new(id: TableNum, binning: Binning) -> Self {
+ Self { id, binning }
+ }
+ fn keys(&self, id: RowNum, ob: Object) -> Vec<Vec<u8>> {
+ let mut keys = vec![self.id.to_be_bytes().to_vec()];
+ self.binning.apply(ob, &mut keys);
+ for k in &mut keys {
+ k.extend(id.to_ne_bytes());
+ }
+ keys
+ }
+}
+// impl Index for UnsortedIndex {
+// fn add(&self, db: &mut dyn WriteTransaction, id: RowNum, ob: Object) -> Result<()> {
+// for key in self.keys(id, ob) {
+// db.set(&key, &[])?;
+// }
+// Ok(())
+// }
+// fn remove(&self, db: &mut dyn WriteTransaction, id: RowNum, ob: Object) -> Result<()> {
+// for key in self.keys(id, ob) {
+// db.del(&key)?;
+// }
+// Ok(())
+// }
+// fn compare(&self, before: Object, after: Object) -> bool {
+// self.keys(0, before) == self.keys(0, after)
+// }
+// fn query(&self, txn: &mut dyn ReadTransaction, _sort: &Sort) -> Result<RowIter> {
+// todo!()
+// }
+// }
diff --git a/database/src/kv/sort/value.rs b/database/src/kv/sort/value.rs
new file mode 100644
index 0000000..0d4ceb7
--- /dev/null
+++ b/database/src/kv/sort/value.rs
@@ -0,0 +1,86 @@
+/*
+ This file is part of jellything (https://codeberg.org/metamuffin/jellything)
+ which is licensed under the GNU Affero General Public License (version 3); see /COPYING.
+ Copyright (C) 2026 metamuffin <metamuffin.org>
+*/
+
+use jellyobject::Object;
+
+use crate::{
+ MultiBehaviour, RowNum, ValueSort,
+ kv::{TableNum, binning::Binning},
+};
+
+pub struct ValueIndex {
+ id: TableNum,
+ binning: Binning,
+ sort: ValueSort,
+}
+
+impl ValueIndex {
+ pub fn new(id: TableNum, binning: Binning, sort: ValueSort) -> Self {
+ Self { id, binning, sort }
+ }
+ fn keys(&self, id: RowNum, ob: Object) -> Vec<Vec<u8>> {
+ let mut keys = vec![self.id.to_be_bytes().to_vec()];
+ self.binning.apply(ob, &mut keys);
+ self.sort.apply(ob, &mut keys);
+ for k in &mut keys {
+ k.extend(id.to_ne_bytes());
+ }
+ keys
+ }
+}
+// impl Index for ValueIndex {
+// fn add(&self, db: &mut dyn WriteTransaction, id: RowNum, ob: Object) -> Result<()> {
+// for key in self.keys(id, ob) {
+// db.set(&key, &[])?;
+// }
+// Ok(())
+// }
+// fn remove(&self, db: &mut dyn WriteTransaction, id: RowNum, ob: Object) -> Result<()> {
+// for key in self.keys(id, ob) {
+// db.del(&key)?;
+// }
+// Ok(())
+// }
+// fn compare(&self, before: Object, after: Object) -> bool {
+// self.keys(0, before) == self.keys(0, after)
+// }
+// fn query(&self, txn: &mut dyn ReadTransaction, sort: &Sort) -> Result<RowIter> {
+// todo!()
+// }
+// }
+impl ValueSort {
+ fn apply(&self, ob: Object, keys: &mut Vec<Vec<u8>>) {
+ match self.multi {
+ MultiBehaviour::First => {
+ if let Some(val) = self.path.get_matching_value(ob) {
+ for k in keys.iter_mut() {
+ k.extend(val);
+ }
+ } else {
+ keys.clear();
+ }
+ }
+ MultiBehaviour::ForEach => {
+ let mut keys_out = Vec::new();
+ for val in self.path.get_matching_values(ob) {
+ for mut k in keys.clone() {
+ k.extend(val);
+ keys_out.push(k);
+ }
+ }
+ *keys = keys_out
+ }
+ MultiBehaviour::Max => todo!(),
+ MultiBehaviour::Min => todo!(),
+ MultiBehaviour::Count => {
+ let count = self.path.get_matching_values(ob).len() as u32;
+ for k in keys.iter_mut() {
+ k.extend(count.to_be_bytes());
+ }
+ }
+ }
+ }
+}
generated by cgit v1.3 (git 2.53.0) at 2026-03-20 03:03:04 +0000