We interrupt this programme

As I said when I started this site, part of the reason for this was to learn enough Hugo to be able to rework my older websites and move them away from Movable Type. This work is now under way and it means that I’ll be blogging less here for a while. I have several sites to update: https://lhexapod.com - my old adventures in robotics site https://lockexplorer.com - a site that needs to be shut down as the tools I used to sell have been discontinued.


Now that I have my generic IdManager I’d like to use it from multiple threads. As I said, this code would normally be used for things like connection ids for network protocols and I’ve spent the past 20 years or so writing servers that use small numbers of threads to handle many thousands of connections with work for each connection being given to a thread from a thread pool to perform.

The journey so far

I’ve now built a generic IdManager which does everything I want it to do, for now. I’ve bumbled along in a very non-scientific manner, mostly using the compiler errors to guide me towards things I’ve then looked up on the web. The code works and is tested, but it’s now time to go back to the books with a series of questions that this journey has got me thinking about:

Clean up and additional functionality

We now have a generic IdManager so now we just need to finish off the required functionality. The missing pieces are: a “reuse policy”, so we can dictate how new ids are allocated the ability to restrict the range of ids used. the ability to mark some ids as used The first of these is to allow us to use the id range “in order” before we start using ids that have been returned to us.

Generic code in Rust

Now that we have an IdManager that works reasonably well and does much of what we require of it we can look at how to make it a bit more flexible. At present the IdManager can only provide Ids that are BYTE sized. I’d like to make it a generic type so that we can specify the data type to used for the Id that is provided. Generic code in Rust can look a little similar to generic code in C++, they both make extensive use of angle brackets, however Rust generics are much more precise; though C++20 has constraints and concepts which do a similar thing to Rust Trait Bounds, but more on Traits later… Our first attempt at generic code in Rust might look something like this, if we start with making just the Interval generic:

Renaming without restructuring

We now have a ThreadSafeIdManager that can provide SmartId’s. It would probably be better to simply have an IdManager that provides Id’s, especially since, in Rust, we can’t even reliably use the original IdManager implementation. I’m adverse to renaming the code at this point as that breaks the ease of comparison with earlier versions. I could, of course, shuffle all the code around, rename files and change modules but, to be honest, the whole module structure is also a bit unwieldy at present.

Smart Ids; object lifetime and mutability

The simple id manager that I built last time is just that, simple. However, it’s enough to start exploring some more complex ideas in Rust. With the current interface you can allocate an id from the id manager and never give it back. In fact, it’s easier to do that than it is to use it properly and always give the id back when you’re done with it. The usual way of addressing this issue in C++ is by using the RAII1 pattern whereby a separate object becomes responsible for the lifetime of the resource.

Building an id manager from a collection of intervals

Now that we have a collection of intervals we can begin to build our id manager. The id manager turns the collection of intervals on its head a bit in that the intervals represent the available ids, so the manager allocates an id by removing it from the collection. The simplest id manager looks a bit like this: pub struct IdManager { free_ids: Intervals, } impl IdManager { pub fn new() -> Self { let mut manager = IdManager { free_ids: Intervals::new() }; manager.

Removing values

Now that we can insert intervals into our collection we need to be able to remove them. There are three ways to remove values from our collection: remove the first interval in the collection remove the first value in the collection remove an arbitrary value from the collection The first is the easiest and the following tests show how it should work: #[test] #[should_panic(expected = "Empty!")] fn test_remove_first_interval_when_empty() { let mut intervals = Intervals::new(); assert_eq!

Adding intervals correctly

Our simple collection of intervals has a major failing, it doesn’t merge intervals and so we end up with as many intervals as we perform insert operations. For example, if we start with an empty collection and add [4] and then [6] we should have [4], [6], which we currently do. However, if we then add [5] we should end up with a single interval, [4,6] rather three separate intervals, [4], [5], [6].