Use smarter data structures for keeping track of circuit IDs per channel
In 0.2.4 and 0.2.5, we use a hash table mapping (channel_t *, circid_t) pairs to circuit_t * to look up circuits; see circuit_get_by_circid_channel_impl() in circuitlist.c. Prior to 0.2.4, we did something similar but with orconns rather than channels. In legacy/trac#11553 (moved), we introduced a random circuit ID selection which can fail if the space of circuit IDs is nearly full; this is preferable to the old linear-time search, but still not as good as a deterministic solution without false positive exhaustion detection would be.
If we used a balanced tree (AVL tree, red/black tree, anything along those lines) augmented at each node with a count of the total nodes in the subtree rooted at that node, we could still do all the operations we currently use the hash table for in deterministic log time, but we could also easily pick a uniformly distributed random unused circuit id in deterministic log time by picking a random integer x in the range [0, max_circ_id - n_circ_ids_used), and then walk down the tree to where the node for that newly allocated circuit id should be, using the node counts to add the number of used circuit ids less than x at each step.