Index: Cargo.toml ================================================================== --- Cargo.toml +++ Cargo.toml @@ -1,25 +1,38 @@ [package] name = "idbag" -version = "0.1.2" +version = "0.2.0" edition = "2021" license = "0BSD" +# https://crates.io/category_slugs categories = [ "data-structures" ] keywords = [ "bag", "identifier" ] repository = "https://repos.qrnch.tech/pub/idbag" -description = "A bag of u32 identifiers." -rust-version = "1.56" +description = "A bag of integers." +rust-version = "1.70" exclude = [ ".fossil-settings", ".efiles", ".fslckout", "www", + "bacon.toml", "rustfmt.toml" ] +# https://doc.rust-lang.org/cargo/reference/manifest.html#the-badges-section +[badges] +maintenance = { status = "passively-maintained" } + [dependencies] -hashbrown = { version = "0.14.3" } -parking_lot = { version = "0.12.1" } +hashbrown = { version = "0.14.5" } +parking_lot = { version = "0.12.3" } +paste = { version = "1.0.15" } [package.metadata.docs.rs] rustdoc-args = ["--generate-link-to-definition"] +[lints.clippy] +all = { level = "deny", priority = -1 } +pedantic = { level = "warn", priority = -1 } +nursery = { level = "warn", priority = -1 } +cargo = { level = "warn", priority = -1 } + Index: README.md ================================================================== --- README.md +++ README.md @@ -1,5 +1,4 @@ # idbag -A bag that initially contains (all) `u32` values that can be allocated and -returned to the bag. +A bag of integers that can be allocated and then returned to the bag. ADDED bacon.toml Index: bacon.toml ================================================================== --- /dev/null +++ bacon.toml @@ -0,0 +1,105 @@ +# This is a configuration file for the bacon tool +# +# Bacon repository: https://github.com/Canop/bacon +# Complete help on configuration: https://dystroy.org/bacon/config/ +# You can also check bacon's own bacon.toml file +# as an example: https://github.com/Canop/bacon/blob/main/bacon.toml + +# For information about clippy lints, see: +# https://github.com/rust-lang/rust-clippy/blob/master/README.md + +#default_job = "check" +default_job = "clippy-all" + +[jobs.check] +command = ["cargo", "check", "--color", "always"] +need_stdout = false + +[jobs.check-all] +command = ["cargo", "check", "--all-targets", "--color", "always"] +need_stdout = false + +# Run clippy on the default target +[jobs.clippy] +command = [ + "cargo", "clippy", + "--color", "always", +] +need_stdout = false + +# Run clippy on all targets +# To disable some lints, you may change the job this way: +# [jobs.clippy-all] +# command = [ +# "cargo", "clippy", +# "--all-targets", +# "--color", "always", +# "--", +# "-A", "clippy::bool_to_int_with_if", +# "-A", "clippy::collapsible_if", +# "-A", "clippy::derive_partial_eq_without_eq", +# ] +# need_stdout = false +[jobs.clippy-all] +command = [ + "cargo", "clippy", + "--all-targets", + "--color", "always", +] +need_stdout = false + +# This job lets you run +# - all tests: bacon test +# - a specific test: bacon test -- config::test_default_files +# - the tests of a package: bacon test -- -- -p config +[jobs.test] +command = [ + "cargo", "test", "--color", "always", + "--", "--color", "always", # see https://github.com/Canop/bacon/issues/124 +] +need_stdout = true + +[jobs.doc] +command = ["cargo", "doc", "--color", "always", "--no-deps"] +need_stdout = false + +# If the doc compiles, then it opens in your browser and bacon switches +# to the previous job +[jobs.doc-open] +command = ["cargo", "doc", "--color", "always", "--no-deps", "--open"] +need_stdout = false +on_success = "back" # so that we don't open the browser at each change + +# You can run your application and have the result displayed in bacon, +# *if* it makes sense for this crate. +# Don't forget the `--color always` part or the errors won't be +# properly parsed. +# If your program never stops (eg a server), you may set `background` +# to false to have the cargo run output immediately displayed instead +# of waiting for program's end. +[jobs.run] +command = [ + "cargo", "run", + "--color", "always", + # put launch parameters for your program behind a `--` separator +] +need_stdout = true +allow_warnings = true +background = true + +# This parameterized job runs the example of your choice, as soon +# as the code compiles. +# Call it as +# bacon ex -- my-example +[jobs.ex] +command = ["cargo", "run", "--color", "always", "--example"] +need_stdout = true +allow_warnings = true + +# You may define here keybindings that would be specific to +# a project, for example a shortcut to launch a specific job. +# Shortcuts to internal functions (scrolling, toggling, etc.) +# should go in your personal global prefs.toml file instead. +[keybindings] +# alt-m = "job:my-job" +c = "job:clippy-all" # comment this to have 'c' run clippy on only the default target Index: src/lib.rs ================================================================== --- src/lib.rs +++ src/lib.rs @@ -1,19 +1,20 @@ -//! The [`IdBag`] is conceptually a bag that initially contains (all) `u32` -//! values. An application can request to allocate an [`Id`] that will contain -//! a `u32` value taken from the bag. Once the Id is dropped its `u32` will -//! automatically be returned to the bag and be available for allocation again. +//! An id bag is conceptually a bag that initially contains (all) intger +//! values of the type of the bag. An application can request to allocate an +//! id from the bag, which behaves like the identifier has been taken out of +//! the bag. Once the id is dropped its integer will automatically be +//! returned to the bag and be available for allocation again. //! -//! `Id` objects are hashable and transparently maps to its internal `u32`. -//! They can also be +//! Allocated identifier objects are hashable and derefernces to its internal +//! integer value. //! //! # Introductionary example //! ``` -//! use idbag::IdBag; +//! use idbag::IdBagU32; //! -//! // Create a new id heap. -//! let idbag = IdBag::new(); +//! // Create a new id bag. +//! let idbag = IdBagU32::new(); //! //! // Allocate an id; first id will have a value of 1. //! let id = idbag.alloc(); //! assert_eq!(id.val(), 1); //! @@ -25,10 +26,17 @@ //! assert_eq!(id.val(), 2); //! //! // The id's drop handler returns 2 to the idbag //! drop(id); //! ``` +//! +//! # Assigned integer semantics +//! The assigned integer increases by one each time a new id has been allocated +//! and wraps around at its maximum value. + +#![forbid(missing_docs)] +#![forbid(clippy::missing_docs_in_private_items)] use std::{ borrow::Borrow, fmt, hash::{Hash, Hasher}, @@ -37,212 +45,295 @@ use parking_lot::Mutex; use hashbrown::HashSet; -/// Internal representation of the IdBag. -#[derive(Default)] -pub struct InnerBag { - set: HashSet, - idgen: u32 -} - -/// A collection of all `u32` integers that can be allocated. -#[derive(Default)] -#[repr(transparent)] -pub struct IdBag(Arc>); - -impl IdBag { - /// Create a new id bag. - pub fn new() -> Self { - Self::default() - } - - /// Create a new id generator using a pre-existing set. - /// - /// This is useful when multiple `IdBag` instances should share the - /// same inner context. The practical implication of this is that the - /// `IdBag`'s that share the same inner context will not yield overlapping - /// identifier values. - /// - /// ``` - /// use idbag::IdBag; - /// - /// let idheap1 = IdBag::new(); - /// let idheap2 = IdBag::with_inner(idheap1.clone_inner()); - /// - /// let id1 = idheap1.alloc(); - /// assert_eq!(id1.val(), 1); - /// - /// let id2 = idheap2.alloc(); - /// assert_eq!(id2.val(), 2); - /// ``` - pub fn with_inner(inner: Arc>) -> Self { - Self(inner) - } - - /// Return a clone of the internal id collection. - pub fn clone_inner(&self) -> Arc> { - Arc::clone(&self.0) - } - - /// Allocate a new identifier. - /// - /// ``` - /// use idbag::IdBag; - /// - /// let idheap = IdBag::new(); - /// - /// let id = idheap.alloc(); - /// assert_eq!(id.val(), 1); - /// - /// let id = idheap.alloc(); - /// assert_eq!(id.val(), 2); - /// ``` - /// - /// # Desgin flaws - /// This function will hang if all the id's have been exhausted. - pub fn alloc(&self) -> Id { - let mut g = self.0.lock(); - let id = loop { - g.idgen = g.idgen.wrapping_add(1); - if !g.set.contains(&g.idgen) { - break g.idgen; - } - }; - g.set.insert(id); - Id { - id, - idbag: Arc::downgrade(&self.0) - } - } - - /// Allocate a specific id, if available. - /// - /// ``` - /// use idbag::IdBag; - /// - /// let idheap = IdBag::new(); - /// - /// let Some(id) = idheap.alloc_id(42) else { - /// panic!("Unexpectedly unable to allocate id 42"); - /// }; - /// assert_eq!(id.val(), 42); - /// - /// let id = idheap.alloc_id(42); - /// assert_eq!(id, None); - /// ``` - pub fn alloc_id(&self, id: u32) -> Option { - let mut g = self.0.lock(); - if g.set.contains(&id) { - None - } else { - g.set.insert(id); - Some(Id { - id, - idbag: Arc::downgrade(&self.0) - }) - } - } -} - -/// Representation of an allocated identifier. -pub struct Id { - id: u32, - idbag: Weak> -} - -impl fmt::Debug for Id { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - write!(f, "Id:{}", self.id) - } -} - -impl Hash for Id { - fn hash(&self, state: &mut H) - where - H: Hasher - { - self.id.hash(state); - } -} - -impl PartialEq for Id { - fn eq(&self, other: &Self) -> bool { - self.id == other.id - } -} - -impl Eq for Id {} - -impl Borrow for Id { - /// Allow Id to be borrowed as a `&u32`. - /// - /// This allows a `HashMap` to look up entries using a `&u32`. - fn borrow(&self) -> &u32 { - &self.id - } -} - -impl Id { - /// Return the internal identifier `u32` value. - pub fn val(&self) -> u32 { - self.id - } - - /// Turn object into an [`ArcId`]. - pub fn into_arcid(self) -> ArcId { - ArcId(Arc::new(self)) - } -} - -impl Drop for Id { - /// When an [`Id`] is dropped, return the internal integer to the collection. - fn drop(&mut self) { - if let Some(idbag) = self.idbag.upgrade() { - let mut g = idbag.lock(); - g.set.remove(&self.id); - } - } -} - -/// An atomically referenced counted version of [`Id`]. -/// -/// This exists primarily because we want to be able to look up `Arc`'s by -/// `u32`'s in `HashMap`'s. While it is possible to look up `Id`'s in -/// `HashMap`'s using `&u32`'s, it doesn't work for `Arc`'s. To workaround -/// we create an `ArcId` newtype that implements `Borrow`, which passes it -/// through the `Arc` to it's inner `Id`. -#[derive(Clone, Hash, PartialEq, Eq)] -#[repr(transparent)] -pub struct ArcId(Arc); - -impl fmt::Debug for ArcId { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - write!(f, "Id:{}", self.0.id) - } -} - -impl ArcId { - /// Return the internal identifier `u32` value. - pub fn val(&self) -> u32 { - self.0.val() - } - - /// Returns the inner value, if the `ArcId` has exactly one strong reference. - pub fn try_unwrap(this: ArcId) -> Result { - Arc::::try_unwrap(this.0).map_err(ArcId) - } - - /// Returns the inner value, if the `ArcId` has exactly one strong reference. - pub fn into_inner(this: ArcId) -> Option { - Arc::::into_inner(this.0) - } -} - -impl Borrow for ArcId { - fn borrow(&self) -> &u32 { - (*self.0).borrow() - } -} +use paste::paste; + +/// Implement an id bag for an integer type. +macro_rules! impl_Bag { + ($int_type:ident $int_name:ident) => { + paste! { + #[doc = "Internal representation of the [`IdBag" $int_name "`]."] + #[derive(Default)] + pub struct [] { + set: HashSet<$int_type>, + idgen: $int_type + } + } + + paste! { + #[doc = "A collection of allocatable `" $int_type "` integers."] + #[derive(Default)] + #[repr(transparent)] + pub struct [](Arc]>>); + } + + paste! { + impl [] { + #[doc = "Create a new id bag containing `" $int_type "` integers."] + #[must_use] + pub fn new() -> Self { + Self::default() + } + + #[doc = r#" + Create a new id generator using a pre-existing set. + + This is useful when multiple `IdBag` instances should share the + same inner context. The practical implication of this is that the + `IdBag`'s that share the same inner context will not yield overlapping + identifier values. + + ``` + use idbag::IdBag"# $int_name r#"; + + let idbag1 = IdBag"# $int_name r#"::new(); + let idbag2 = IdBag"# $int_name r#"::with_inner(idbag1.clone_inner()); + + let id1 = idbag1.alloc(); + assert_eq!(id1.val(), 1); + + let id2 = idbag2.alloc(); + assert_eq!(id2.val(), 2); + ``` + "#] + pub const fn with_inner( + inner: Arc]>> + ) -> Self { + Self(inner) + } + + /// Return a clone of the internal id collection. + #[must_use] + pub fn clone_inner(&self) -> Arc]>> { + Arc::clone(&self.0) + } + + + #[doc = r#" + Allocate a new identifier. + + ``` + use idbag::IdBag"# $int_name r#"; + + let idbag = IdBag"# $int_name r#"::new(); + + let id = idbag.alloc(); + assert_eq!(id.val(), 1); + + let id = idbag.alloc(); + assert_eq!(id.val(), 2); + ``` + # Desgin flaws + This function will hang if all the id's have been exhausted. + "#] + #[must_use] + pub fn alloc(&self) -> [] { + let mut g = self.0.lock(); + // ToDo: exhaust-deadlock + let id = loop { + g.idgen = g.idgen.wrapping_add(1); + if !g.set.contains(&g.idgen) { + break g.idgen; + } + }; + g.set.insert(id); + drop(g); + [] { + id, + idbag: Arc::downgrade(&self.0) + } + } + + + #[doc = r#" + Allocate a specific id, if available. + + ``` + use idbag::IdBag"# $int_name r#"; + + let idbag = IdBag"# $int_name r#"::new(); + + let Some(id) = idbag.alloc_id(42) else { + panic!("Unexpectedly unable to allocate id 42"); + }; + assert_eq!(id.val(), 42); + + let id = idbag.alloc_id(42); + assert_eq!(id, None); + ``` + "#] + #[must_use] + pub fn alloc_id(&self, id: $int_type) -> Option<[]> { + let mut g = self.0.lock(); + if g.set.contains(&id) { + None + } else { + g.set.insert(id); + drop(g); + Some([] { + id, + idbag: Arc::downgrade(&self.0) + }) + } + } + } + } + + paste! { + #[doc = r#" + An allocated `"# $int_type r#"` identifier. + "#] + pub struct [] { + id: $int_type, + idbag: Weak]>> + } + + impl fmt::Debug for [] { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + write!(f, "Id:{}", self.id) + } + } + + impl Hash for [] { + fn hash(&self, state: &mut H) + where + H: Hasher + { + self.id.hash(state); + } + } + + impl PartialEq for [] { + fn eq(&self, other: &Self) -> bool { + self.id == other.id + } + } + + impl Eq for [] {} + + impl Borrow<$int_type> for [] { + #[doc = r#" + Allow `Id"# $int_name r#"` to be borrowed as a `&"# $int_type r#"`. + + This allows a `HashMap` to look up entries + using a `&"# $int_type r#"`. + "#] + fn borrow(&self) -> &$int_type { + &self.id + } + } + + impl [] { + #[doc = r#"Return the internal `"# $int_type r#"` value."#] + #[must_use] + #[deprecated(since = "0.2.0", note = "Use `get()` method instead.")] + pub const fn val(&self) -> $int_type { + self.id + } + + #[doc = r#"Return the internal `"# $int_type r#"` value."#] + #[must_use] + pub const fn get(&self) -> $int_type { + self.id + } + + #[doc = r#" + Turn object into an [`ArcId"# $int_name r#"`]. + ``` + let idbag = idbag::IdBag"# $int_name r#"::new(); + + let aid = idbag.alloc().into_arcid(); + ``` + "#] + #[must_use] + pub fn into_arcid(self) -> [] { + [](Arc::new(self)) + } + } + + impl Drop for [] { + #[doc = r#" + When an [`Id"# $int_name r#"`] is dropped, return the internal integer + to the collection. + "#] + fn drop(&mut self) { + if let Some(idbag) = self.idbag.upgrade() { + let mut g = idbag.lock(); + g.set.remove(&self.id); + } + } + } + } + + + paste! { + #[doc = r#" + An atomically referenced counted version of [`Id"# $int_name r#"`]. + + This exists primarily because it should be possible to look up + `Arc`'s by `"# $int_type r#"`'s in `HashMap`'s. + While it is possible to look up `Id`'s in `HashMap`'s using + `&"# $int_type r#"`'s, it doesn't work for `Arc`'s. + To workaround this limitation this `ArcId"# $int_name r#"` newtype + implements `Borrow<"# $int_type r#">`, which passes it through the + `Arc` to it's inner `Id"# $int_name r#"`. + "#] + #[derive(Clone, Hash, PartialEq, Eq)] + #[repr(transparent)] + pub struct [](Arc<[]>); + + impl fmt::Debug for [] { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + write!(f, "Id:{}", self.0.id) + } + } + + impl [] { + #[doc = r#" + Return the internal identifier `"# $int_type r#"` value. + "#] + #[must_use] + pub fn val(&self) -> $int_type { + self.0.get() + } + + #[doc = r#" + Returns the inner value, if the `ArcId` has exactly one strong + reference. + + # Errors + If there's more than one strong reference to the + `ArcId"# $int_name r#"`, the `ArcId"# $int_name r#"` will be returned. + "#] + pub fn try_unwrap(this: Self) -> Result<[], Self> { + Arc::<[]>::try_unwrap(this.0) + .map_err([]) + } + + #[doc = r#" + Returns the inner value, if the `ArcId"# $int_name r#"` has exactly + one strong reference. + "#] + #[must_use] + pub fn into_inner(this: Self) -> Option<[]> { + Arc::<[]>::into_inner(this.0) + } + } + + impl Borrow<$int_type> for [] { + fn borrow(&self) -> &$int_type { + (*self.0).borrow() + } + } + } + }; +} + +impl_Bag! { u8 U8 } +impl_Bag! { u16 U16 } +impl_Bag! { u32 U32 } +impl_Bag! { u64 U64 } +impl_Bag! { usize Usize } // vim: set ft=rust et sw=2 ts=2 sts=2 cinoptions=2 tw=79 : Index: tests/arc.rs ================================================================== --- tests/arc.rs +++ tests/arc.rs @@ -1,16 +1,16 @@ -use idbag::{ArcId, IdBag}; +use idbag::{ArcIdU32, IdBagU32}; #[test] fn arc() { - let idbag = IdBag::new(); + let idbag = IdBagU32::new(); let id = idbag.alloc().into_arcid(); let id2 = id.clone(); - assert_eq!(ArcId::into_inner(id2), None); - let Some(id) = ArcId::into_inner(id) else { + assert_eq!(ArcIdU32::into_inner(id2), None); + let Some(id) = ArcIdU32::into_inner(id) else { panic!("Unable to into_inner()"); }; - assert_eq!(id.val(), 1); + assert_eq!(id.get(), 1); } // vim: set ft=rust et sw=2 ts=2 sts=2 cinoptions=2 tw=79 : Index: tests/map_access.rs ================================================================== --- tests/map_access.rs +++ tests/map_access.rs @@ -1,15 +1,15 @@ use hashbrown::HashMap; -use idbag::{ArcId, Id, IdBag}; +use idbag::{ArcIdU32, IdBagU32, IdU32}; #[test] fn access() { - let mut m: HashMap = HashMap::new(); - let idbag = IdBag::new(); + let mut m: HashMap = HashMap::new(); + let idbag = IdBagU32::new(); let id = idbag.alloc(); - let idval = id.val(); + let idval = id.get(); m.insert(id, String::from("hello")); // Look up using &u32 if let Some(v) = m.get(&idval) { @@ -19,15 +19,17 @@ } } #[test] fn arced() { - let mut m: HashMap = HashMap::new(); - let idbag = IdBag::new(); + let mut m: HashMap = HashMap::new(); + let idbag = IdBagU32::new(); let id = idbag.alloc().into_arcid(); let idval = id.val(); + // Actually testing the clone here, so don't warn about it + #[allow(clippy::redundant_clone)] m.insert(id.clone(), String::from("hello")); // Look up using &u32 if let Some(v) = m.get(&idval) { assert_eq!(v, &String::from("hello")); Index: www/changelog.md ================================================================== --- www/changelog.md +++ www/changelog.md @@ -1,14 +1,19 @@ # Change Log +⚠️ indicates a breaking change. + ## [Unreleased] [Details](/vdiff?from=idbag-0.1.2&to=trunk) ### Added ### Changed + +- ⚠️ Implement for explicit integer types. Instead of `IdBag`, `Id`, etc, now + uses `IdBag{U8,U16,U32,U64,Usize}`, `Id{U8,U16,..}`, etc. ### Removed --- Index: www/index.md ================================================================== --- www/index.md +++ www/index.md @@ -1,9 +1,8 @@ # idbag -A bag that initially contains (all) `u32` values that can be allocated and -returned to the bag. +A bag of integers that can be allocated and then returned to the bag. ## Change log The details of changes can always be found in the timeline, but for a