1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191
//! Package implement Persistent Ordered Map.
//!
//! Quoting from [Wikipedia][pds]:
//!
//! > A data structure is *partially persistent* if all versions can be
//! > accessed but only the newest version can be modified. The data
//! > structure is *fully persistent* if every version can be both accessed
//! > and modified. If there is also a meld or merge operation that can
//! > create a new version from two previous versions, the data structure is
//! > called *confluently persistent*. Structures that are not persistent are
//! > called *ephemeral* data structures.
//!
//! Following types implement an ordered-map for specific use cases:
//!
//! * [OMap] implement *ephemeral* ordered-map, that is meant for best case
//! single-threaded performance.
//! * [rc::OMap] implement *fully persistent* ordered-map that allows
//! shared-ownership, but not thread-safe.
//! * [arc::OMap] implement *fully persistent* ordered-map that allows
//! shared-ownership and thread-safe.
//! * [mdb::OMap] implements *partially persistent* ordered-map most useful for
//! database applications.
//!
//! All the above types use [Left-Leaning-Red-Black][wiki-llrb] tree underneath.
//!
//! Ephemeral ordered-map
//! ---------------------
//!
//! - Each entry in OMap instance correspond to a {Key, Value} pair.
//! - Parametrised over `key-type` and `value-type`.
//! - CRUD operations, via set(), get(), remove() api.
//! - Full table scan, to iterate over all entries.
//! - Range scan, to iterate between a ``low`` and ``high``.
//! - Reverse iteration.
//! - Uses ownership model and borrow semantics to ensure safety.
//! - No Durability guarantee.
//! - Not thread safe.
//!
//! Ownership and Cloning
//! ---------------------
//!
//! Cloning `arc::OMap` and `rc::OMap` is cheap, it creates a shared ownership
//! of the underlying tree. This is great for applications requiring
//! shared-ownership, but at the cost of copy-on-write for every mutation, like
//! set and remove operations.
//!
//! Thread Safety
//! -------------
//!
//! `arc::OMap` is thread safe through `Arc`. To trade-off thread-safety for
//! performance use `rc::OMap` type, which is same as `arc::OMap` type except
//! for using `std::rc::Rc` instead of `std::sync::Arc` for shared ownership.
//! That is, `Send` and `Sync` traits are not available for `rc::OMap` type
//! while it is available for `arc::OMap` type.
//!
//! Constructing a new [OMap] instance and CRUD operations:
//!
//! ```
//! use ppom::OMap;
//!
//! let mut index: OMap<String,String> = OMap::new();
//! assert_eq!(index.len(), 0);
//! assert_eq!(index.is_empty(), true);
//!
//! index.set("key1".to_string(), "value1".to_string());
//! index.set("key2".to_string(), "value2".to_string());
//!
//! assert_eq!(index.len(), 2);
//! assert_eq!(index.get("key1").unwrap(), "value1".to_string());
//! assert_eq!(index.remove("key1").unwrap(), "value1".to_string());
//! ```
//!
//! Fully persistent ordered-map
//! ----------------------------
//!
//! Supports all the features as that of ephemeral OMap, with slight difference
//! in call pattern:
//!
//! ```
//! use ppom::rc::OMap;
//!
//! let mut index: OMap<String,String> = OMap::new();
//! assert_eq!(index.len(), 0);
//! assert_eq!(index.is_empty(), true);
//!
//! index = index.set("key1".to_string(), "value1".to_string());
//! index = index.set("key2".to_string(), "value2".to_string());
//!
//! assert_eq!(index.len(), 2);
//! assert_eq!(index.get("key1").unwrap(), "value1".to_string());
//! let new_index = index.remove("key1");
//! assert_eq!(index.get("key1").unwrap(), "value1".to_string());
//! assert_eq!(new_index.get("key1").is_none(), true);
//! ```
//!
//! [wiki-llrb]: https://en.wikipedia.org/wiki/Left-leaning_red-black_tree
//! [pds]: https://en.wikipedia.org/wiki/Persistent_data_structure
//! [im]: https://github.com/bodil/im-rs
use std::{error, fmt, result};
// Short form to compose Error values.
//
// Here are few possible ways:
//
// ```ignore
// use crate::Error;
// err_at!(ParseError, msg: format!("bad argument"));
// ```
//
// ```ignore
// use crate::Error;
// err_at!(ParseError, std::io::read(buf));
// ```
//
// ```ignore
// use crate::Error;
// err_at!(ParseError, std::fs::read(file_path), format!("read failed"));
// ```
//
macro_rules! err_at {
($v:ident, msg: $($arg:expr),+) => {{
let prefix = format!("{}:{}", file!(), line!());
Err(Error::$v(prefix, format!($($arg),+)))
}};
($v:ident, $e:expr) => {{
match $e {
Ok(val) => Ok(val),
Err(err) => {
let prefix = format!("{}:{}", file!(), line!());
Err(Error::$v(prefix, format!("{}", err)))
}
}
}};
($v:ident, $e:expr, $($arg:expr),+) => {{
match $e {
Ok(val) => Ok(val),
Err(err) => {
let prefix = format!("{}:{}", file!(), line!());
let msg = format!($($arg),+);
Err(Error::$v(prefix, format!("{} {}", err, msg)))
}
}
}};
}
/// Error variants that are returned by this package's API.
///
/// Each variant carries a prefix, typically identifying the
/// error location.
pub enum Error {
Fatal(String, String),
KeyNotFound(String, String),
InvalidCAS(String, String),
Invalid(String, String),
FailConvert(String, String),
}
impl fmt::Display for Error {
fn fmt(&self, f: &mut fmt::Formatter) -> result::Result<(), fmt::Error> {
use Error::*;
match self {
Fatal(p, msg) => write!(f, "{} Fatal: {}", p, msg),
KeyNotFound(p, msg) => write!(f, "{} KeyNotFound: {}", p, msg),
InvalidCAS(p, msg) => write!(f, "{} InvalidCAS: {}", p, msg),
Invalid(p, msg) => write!(f, "{} Invalid: {}", p, msg),
FailConvert(p, msg) => write!(f, "{} FailConvert: {}", p, msg),
}
}
}
impl fmt::Debug for Error {
fn fmt(&self, f: &mut fmt::Formatter) -> result::Result<(), fmt::Error> {
write!(f, "{}", self)
}
}
impl error::Error for Error {}
/// Type alias for Result return type, used by this package.
pub type Result<T> = result::Result<T, Error>;
pub mod arc;
pub mod mdb;
mod mdb_node;
mod omap;
pub mod rc;
mod spinlock;
pub use omap::OMap;