An Id Manager

The first piece of code that I’m going to play with in Rust is a “reusable id manager”. This is a collection of numerical ids which can be allocated, used and then released back to a pool for later reuse. I tend to use this kind of code for network protocols where something like a peer-id is required; these ids can be within a given range (usually limited by the data type that represents them), and are “in use” for a period of time and then return to the collection. This allows us to have, say, an id for a connection that is represented by a BYTE where we may have up to 255 active connections, each with a unique id, at one time. Once a connection closes it releases the id and then the id can be used again for another connection.

To store this pool of available ids efficiently I use a series of intervals that represent the available ids. So, when the id manager is first created there may be a single interval of [0,255]. As ids are allocated this is adjusted, so that after several allocations it may be [10,255]. As ids are released back to the manager, in any order, additional intervals may be created, so we may end up with [0], [10,255] and then [0], [5], [10,255], [0,1], [5], [10,255], etc. The intervals are stored in a set, in order.

To prevent leaking ids it is useful to have a “smart id” that uses the RAII1 pattern to allocate an id when the “smart id” is created and then release it back to the collection when the “smart id” is destroyed.

It may be useful for the id manager to use the whole range of ids before it starts to reuse previously released ids, so we always allocate 0-255 in sequence before reusing. Alternatively it may be required that we always allocate the lowest available id first, so if we have allocated 10 ids and then release the first one, 0, the next one allocated will be 0 and not 11…

To allow for different id ranges the id manager should be generic, based on the type of the id it produces. To allow for some ids being ‘reserved’ we should be able to remove them from the pool of available ids when we create the manager.