[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 }

# 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.

# 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

//! 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);
//!
//! // The id's drop handler returns 1 to the idbag
//! drop(id);
//!
//! // Allocate another id; next id will have a value of 2.
//! let id = idbag.alloc();
//! 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},
  sync::{Arc, Weak}
};

use parking_lot::Mutex;

use hashbrown::HashSet;

use paste::paste;

/// Implement an id bag for an integer type.
macro_rules! impl_Bag {
  ($int_type:ident $int_name:ident) => {
    paste! {
/// Internal representation of the IdBag.
#[derive(Default)]
pub struct InnerBag {
  set: HashSet<u32>,
  idgen: u32
}

/// A collection of all `u32` integers that can be allocated.
#[derive(Default)]
#[repr(transparent)]
pub struct IdBag(Arc<Mutex<InnerBag>>);

      #[doc = "Internal representation of the  [`IdBag" $int_name "`]."]
      #[derive(Default)]
      pub struct [<InnerBag $int_name>] {
        set: HashSet<$int_type>,
        idgen: $int_type
      }
    }

    paste! {
      #[doc = "A collection of allocatable `" $int_type "` integers."]
      #[derive(Default)]
      #[repr(transparent)]
      pub struct [<IdBag $int_name>](Arc<Mutex<[<InnerBag $int_name>]>>);
    }
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());

    paste! {
      impl [<IdBag $int_name>] {
        #[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 = idheap1.alloc();
  /// assert_eq!(id1.val(), 1);
  ///
  /// let id2 = idheap2.alloc();
  /// assert_eq!(id2.val(), 2);
  /// ```
  pub fn with_inner(inner: Arc<Mutex<InnerBag>>) -> Self {
    Self(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<Mutex<[<InnerBag $int_name>]>>
        ) -> Self {
          Self(inner)
        }

  /// Return a clone of the internal id collection.
  pub fn clone_inner(&self) -> Arc<Mutex<InnerBag>> {
    Arc::clone(&self.0)
  }
        /// Return a clone of the internal id collection.
        #[must_use]
        pub fn clone_inner(&self) -> Arc<Mutex<[<InnerBag $int_name>]>> {
          Arc::clone(&self.0)
        }


        #[doc = r#"
  /// 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);
  /// ```
        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.
  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)
    }
  }
        # Desgin flaws
        This function will hang if all the id's have been exhausted.
        "#]
        #[must_use]
        pub fn alloc(&self) -> [<Id $int_name>] {
          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 $int_name>] {
            id,
            idbag: Arc::downgrade(&self.0)
          }
        }


        #[doc = r#"
  /// 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<Id> {
    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<Mutex<InnerBag>>
}
        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<[<Id $int_name>]> {
          let mut g = self.0.lock();
          if g.set.contains(&id) {
            None
          } else {
            g.set.insert(id);
            drop(g);
            Some([<Id $int_name>] {
              id,
              idbag: Arc::downgrade(&self.0)
            })
          }
        }
      }
    }

    paste! {
      #[doc = r#"
      An allocated `"# $int_type r#"` identifier.
      "#]
      pub struct [<Id $int_name>] {
        id: $int_type,
        idbag: Weak<Mutex<[<InnerBag $int_name>]>>
      }

impl fmt::Debug for Id {
  fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
    write!(f, "Id:{}", self.id)
  }
}
      impl fmt::Debug for [<Id $int_name>] {
        fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
          write!(f, "Id:{}", self.id)
        }
      }

impl Hash for Id {
  fn hash<H>(&self, state: &mut H)
  where
    H: Hasher
  {
    self.id.hash(state);
  }
}
      impl Hash for [<Id $int_name>] {
        fn hash<H>(&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 PartialEq for [<Id $int_name>] {
        fn eq(&self, other: &Self) -> bool {
          self.id == other.id
        }
      }

impl Eq for Id {}
      impl Eq for [<Id $int_name>] {}

impl Borrow<u32> for Id {
  /// Allow Id to be borrowed as a `&u32`.
  ///
  /// This allows a `HashMap<Id, T>` to look up entries using a `&u32`.
  fn borrow(&self) -> &u32 {
    &self.id
  }
}
      impl Borrow<$int_type> for [<Id $int_name>] {
        #[doc = r#"
        Allow `Id"# $int_name r#"` to be borrowed as a `&"# $int_type r#"`.

        This allows a `HashMap<Id"# $int_name r#", T>` to look up entries
        using a `&"# $int_type r#"`.
        "#]
        fn borrow(&self) -> &$int_type {
          &self.id
        }
      }

impl Id {
  /// Return the internal identifier `u32` value.
  pub fn val(&self) -> u32 {
    self.id
  }
      impl [<Id $int_name>] {
        #[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`].
  pub fn into_arcid(self) -> ArcId {
    ArcId(Arc::new(self))
  }
}
        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) -> [<ArcId $int_name>] {
          [<ArcId $int_name>](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<Id>`'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<Id>`'s.  To workaround
/// we create an `ArcId` newtype that implements `Borrow<u32>`, which passes it
/// through the `Arc` to it's inner `Id`.
#[derive(Clone, Hash, PartialEq, Eq)]
#[repr(transparent)]
pub struct ArcId(Arc<Id>);
      impl Drop for [<Id $int_name>] {
        #[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<Id"# $int_name r#">`'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<Id"# $int_name r#">`'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 [<ArcId $int_name>](Arc<[<Id $int_name>]>);

impl fmt::Debug for ArcId {
  fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
    write!(f, "Id:{}", self.0.id)
  }
}
      impl fmt::Debug for [<ArcId $int_name>] {
        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()
  }
      impl [<ArcId $int_name>] {
        #[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.
  pub fn try_unwrap(this: ArcId) -> Result<Id, ArcId> {
    Arc::<Id>::try_unwrap(this.0).map_err(ArcId)
  }
        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<[<Id $int_name>], Self> {
          Arc::<[<Id $int_name>]>::try_unwrap(this.0)
            .map_err([<ArcId $int_name>])
        }

        #[doc = r#"
  /// Returns the inner value, if the `ArcId` has exactly one strong reference.
  pub fn into_inner(this: ArcId) -> Option<Id> {
    Arc::<Id>::into_inner(this.0)
  }
}
        Returns the inner value, if the `ArcId"# $int_name r#"` has exactly
        one strong reference.
        "#]
        #[must_use]
        pub fn into_inner(this: Self) -> Option<[<Id $int_name>]> {
          Arc::<[<Id $int_name>]>::into_inner(this.0)
        }
      }

impl Borrow<u32> for ArcId {
  fn borrow(&self) -> &u32 {
    (*self.0).borrow()
  }
}
      impl Borrow<$int_type> for [<ArcId $int_name>] {
        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 :

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 :

use hashbrown::HashMap;

use idbag::{ArcId, Id, IdBag};
use idbag::{ArcIdU32, IdBagU32, IdU32};

#[test]
fn access() {
  let mut m: HashMap<Id, String> = HashMap::new();
  let idbag = IdBag::new();
  let mut m: HashMap<IdU32, String> = 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) {
    assert_eq!(v, &String::from("hello"));
  } else {
    panic!("Unable to find entry");
  }
}

#[test]
fn arced() {
  let mut m: HashMap<ArcId, String> = HashMap::new();
  let idbag = IdBag::new();
  let mut m: HashMap<ArcIdU32, String> = 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"));
  } else {
    panic!("Unable to find entry");

# 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

---

## [0.1.2] - 2024-01-23

# 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
high-level view of changes between released versions there's a manually
maintained [Change Log](./changelog.md).