rust-puzzles/hostnames_allocator

Task

(Task description is vaguely reproduced from memory.)

Implement a hostname allocator supporting two commands, A hosttype and D hostname, such that:

• A hosttype allocates and returns unique hostname of the form hosttype123 with the smallest possible integer number (starting with 1) currently free for this host type;
• D hostname (where hostname is always of the form hosttype123) frees this hostname (or does nothing if it wasn't allocated before), allowing to reuse it later.

For example:

A gateway
A gateway
A gateway
A proxy
A proxy
D gateway2
D gateway5
A proxy
A gateway
A gateway
A gateway

should result in the following allocations made

gateway1
gateway2
gateway3
proxy1
proxy2
proxy3
gateway2
gateway4
gateway5

No error handling is necessary; panicking if any of the input values is not in the expected format is acceptable.

Goals

The solution should be reasonably fast for both types of commands; it should be implemented within 1-2 hours; readability and maintainability can suffer.

Algorithm

Store hashmap of allocators by host types.

For every host type, store a self-balancing tree (with access and modify operations taking O(tree depth) = O(log(tree length))) with non-adjacent ranges of reserved numbers; "non-adjacent" as in at least one unallocated number should separate any two ranges. This way, for every "free" operation, finding a matching range (if any) and updating the tree should take O(log(number of ranges for host type)); and for every "allocate" operation, only the first or the first two ranges need to be checked and updated, which might mean constant time in best case (depending on the tree implementation) and O(log(number of ranges for host type)) in worst case (plus O(log(number of host types))).

See src/ranged_number_allocator.rs for more details.

The asymptotic complexity above is theoretical; in practice, ideal trees don't actually work like that. In this implementation, Rust's BTreeMap is used which is supposed to provide the same logarithmic asymptotic complexity in practice. Range starts are used as keys and range ends as values.

Memory requirements are O(number of ranges) plus combined length of all host types.

Constant factors were not considered in this implementation.

Compiled binary size on x86_64-unknown-linux-musl target, in release mode, is 506KB.

Usage

Nightly Rust is needed (because btree_cursors unstable feature is used). This implementation can probably be rewritten from btree_cursors feature to range_mut method, but then it will be even more complex and even more difficult to reason about.

Tests are in tests/ and can be run with:

cargo test

Sample input commands are in sample.in and can be run with:

cargo run < sample.in