Lib.rs

API Documentation

A timer system that uses a binary heap to order timers by expiration time.

lib.rs:

A binary heap based timer system with fast deletes.

Timers are maintained in a binary heap ordered by expiration time. In order to prevent O(n) deletes, keys are also stored in an active map. A timer is only active when when it exists in the active map. When a timer is deleted, it is only removed from the active map . When expire is called the key for a timer is only returned if it exists in the active map.

In order to differentiate multiple adds of the same key, so that when a key is deleted and re-added all previously non-expired keys don't become active (since they remain in the heap), each heap entry and active entry is attached to a montonically increasing counter. This ensures only truly active versions of the same key can be expired.

In order to provide this fast delete functionality, there is extra cpu overhead from hashmap lookups during expiry and time_remaining functionality. There is also extra memory usage for the duplicate keys and monotonic counters maintained in each heap entry and active map value. Note that when a lot of keys are added and deleted, expiry can become long if those keys are in the front of the heap and also expired, as they need to be scanned over to get to a valid expired value. However, this may be fine depending upon use case, as it's possible the keys cancelled will be evenly distriuted throughout the heap, and we only scan through expiry until we reach a non-expired time, whether the key is active or not. The tradeoff made for the user is whether they want to do any scans during deletes in order to save memory and cpu during expiry and time_remaining functionality.