Rust - Clean up and additional functionality
This article was previously published on len-learns-rust.com. A full index of these articles can be found here.
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. This often makes it easier to debug connections as the ids don’t get reused quickly and so log lines for ‘id 1’ are all for the same connection rather than for multiple connections as ‘1’ is used, release, reused, etc.
The first thing we need to do is add a ReusePolicy enum to give us the ability to ask
for an IdManager with a policy of either ReuseSlow or ReuseFast.
We then adjust allocate() so that know the last Id that we allocated and increment it
and try and allocate the next id if it’s available (it might not be if we’ve already been
through the collection once and are now working on a disparate set of available id intervals.
pub fn allocate(&mut self) -> T {
if self.free_ids.is_empty()
{
panic!("No Ids available")
}
if self.reuse_policy == ReusePolicy::ReuseFast
{
return self.free_ids.remove_first_value();
}
let id: T;
loop {
if self.free_ids.remove_value(self.next_to_allocate)
{
id = self.next_to_allocate;
self.next_to_allocate = self.increment_id(self.next_to_allocate);
break;
}
self.next_to_allocate = self.increment_id(self.next_to_allocate);
}
id
}
fn increment_id(&self, mut id: T) -> T {
if id == T::MAX
{
id = T::MIN;
} else {
id = id + T::one();
//id += T::one(); // needs additional bounds
}
id
}
We could use id += T::one(); rather than id = id + T::one(); but that means
that we need to adjust our IdType trait to include an additional trait std::ops::AddAssign
and there’s no real need for that right now…
Of course we need some tests for this change and the addition of the ReusePolicy to
the creation of the object means that the change is quite sweeping.
The code for the reuse policy change can be found here.
The next requirement is to be able to restrict the range of Ids provided to
less than the full range that the datatype chosen allows. For example, valid
Ids may be between [10,200] and we’re using a u8. This change is simply
another code change that uses no new Rust constructs, so I’ll just let the code
speak for itself.
The code for the restricted range change can be found here.
The final piece of functionality is the ability to clearly state that some
Ids aren’t available. Once again, we may have our range of valid Ids represented
as a u8 but it may be that 0xFA through 0xFF and 0xAA are all ‘reserved’
values that shouldn’t be allocated for this particular use case. We need
a way to easily remove these from consideration.
This requires that we add functionality to the collection of intervals so that we can remove an interval. This is reasonably easy if we restrict its use to a new collection, containing a single interval of available Ids but becomes more complex if we allow it at any time where the interval that we wish to remove may span multiple intervals in the collection. We’ll go with the complex version as it’s not that much more complex and it requires less documentation and will cause fewer surprises…
We need to add this:
pub fn remove_interval(&mut self, lower: T, upper: T) {
let mut remove_these: BTreeSet<Interval<T>> = BTreeSet::new();
let mut add_these: BTreeSet<Interval<T>> = BTreeSet::new();
{
let interval_to_remove = Interval::new(lower, upper);
let intervals = self.intervals.range((Included(Interval::new(T::MIN, lower)), Unbounded));
for interval in intervals {
if interval_to_remove.overlaps(interval) {
remove_these.insert(interval.clone());
}
else if interval.contains_value(lower) || interval.contains_value(upper) {
remove_these.insert(interval.clone());
}
if interval.lower() < lower && interval.upper() >= lower {
add_these.insert(Interval::<T>::new(interval.lower(), lower - T::one()));
}
if interval.upper() > upper && interval.lower() <= upper {
add_these.insert(Interval::<T>::new(upper + T::one(), interval.upper()));
}
}
}
for interval in remove_these {
self.intervals.remove(&interval);
}
for interval in add_these {
self.intervals.insert(interval);
}
}
The main complexity here is that we can’t simply iterate the collection and remove or adjust as we go, so we need to keep track of the intervals that we need to remove and the new intervals that we need to add.
This test covers the new code:
#[test]
fn test_remove_interval()
{
let mut intervals = Intervals::new();
assert_eq!(intervals.insert_interval(u8::MIN, u8::MAX), true);
assert_eq!(intervals.dump(), "[0,255]");
intervals.remove_interval(10,30); // middle
assert_eq!(intervals.dump(), "[0,9], [31,255]");
intervals.remove_interval(10,30); // duplicate
assert_eq!(intervals.dump(), "[0,9], [31,255]");
intervals.remove_interval(50,60);
assert_eq!(intervals.dump(), "[0,9], [31,49], [61,255]");
intervals.remove_interval(70,90);
assert_eq!(intervals.dump(), "[0,9], [31,49], [61,69], [91,255]");
intervals.remove_interval(68,91); // first/last
assert_eq!(intervals.dump(), "[0,9], [31,49], [61,67], [92,255]");
intervals.remove_interval(65,93);
assert_eq!(intervals.dump(), "[0,9], [31,49], [61,64], [94,255]");
intervals.remove_interval(50,93); // spans
assert_eq!(intervals.dump(), "[0,9], [31,49], [94,255]");
intervals.remove_interval(50,93);
assert_eq!(intervals.dump(), "[0,9], [31,49], [94,255]");
intervals.remove_interval(200,255); // end
assert_eq!(intervals.dump(), "[0,9], [31,49], [94,199]");
intervals.remove_interval(0,5); // start
assert_eq!(intervals.dump(), "[6,9], [31,49], [94,199]");
intervals.remove_interval(7,198); // most
assert_eq!(intervals.dump(), "[6], [199]");
intervals.remove_interval(0,255); // all
assert_eq!(intervals.dump(), "");
}
We are now able to add mark_value_as_used() and mark_interval_as_used() in
the IdManager code that uses the collection. Add some tests there, and we’re done.
Due two-part design of the IdManager and the locking we end up with two sets of
almost identical tests. For now I can live with it, but ideally we either need to
refactor the IdManager into a single object, accept that the ‘outer’ object’s
tests cover the ‘inner’ object or somehow macro generate the tests…
The code can be found here on GitHub each step on the journey will have one or more separate directories of code, so this article’s code is here, here and here this allows for easy comparison of changes at each stage.
Of course, there may be a better way; leave comments if you’d like to help me learn.
