== Concept
For background information of what a token bucket is please consult the internet or books on packet scheduling and traffic shaping.
== Constructing a bucket
The constructor is:
TokenBucket(tokencount_t rate, timeunit_t time_unit, tokencount_t limit)
The rate is the number of tokens added to the bucket every time unit.
The time unit is what is convenient for you to use a clock.
The limit is the maximum number of tokens the bucket can hold.
For instance, if you want 10000 tokens every second with a burst limit of 20000 then do:
TokenBucket(10000,1,20000)
If the clock granularity you want to use is nanoseconds then:
TokenBucket(10000,1000000000,20000)
If the clock tick is aligned with a system clock of 1024Hz then:
TokenBucket(10000,1024,20000)
Zero-rate buckets are possible:
TokenBucket(0,1,20000)
And so is zero-capacity buckets:
TokenBucket(10000,1,0)
(which essentially is zero-rate too because the bucket cannot hold any tokens to take)
The implementation does not like it if the clock moves backward so you should use a realtime clock and not a "wall" clock.
== Using a bucket
The bucket must be updated with the current time so it can calculate how may tokens to add. You can do this with the update() method, or with the canGet/getTokens/whenAvail methods that take the current time as a parameter.
When you have something to send/process that requires tokens you can call canGet() to check if it is possible to take some tokens.
After that you call getTokens() specifying how many tokens you would like to take. This can be more than the previously probed with canGet(). getTokens() will return at least as many tokens was guaranteed by canGet() and possibly more (but no more than requested).
After doing the work represented by the tokens you put back any unused tokens with putTokens().
If there is more work to be done you can call whenAvail() to determine when sufficient tokens will have been added to the bucket. (whenAvail() returns 'never' if that will never happen due to too low capacity or zero rate).
In general the usage pattern will be:
<>
update(current_clock)
if(canGet(minimum_meaningful_work_size)) {
tokens = getTokens(work_size)
<>
putTokens(unused_tokens)
}
if(still work to be done)
wakeup_time = whenAvail(minimum_meaningful_work_size);
If the minimum meaningful amount of work to be done is 1 and your algorithm can handle 0 tokens and there is never unused tokens then it can be simplified to:
<>
tokens = getTokens(current_clock,work_size)
<>
if(still work to be done)
wakeup_time = whenAvail(minimum_meaningful_work_size);
== Reconfiguring a bucket
Basically you can't. But you can replace it.
TokenBucket bucket_a(1,2,3);
...
TokenBucket new_bucket(4,5,6);
bucket_a = new_bucket;
If you want to carry over the current tokens (they are lost by the method above) then you have to do a bit more work:
TokenBucket bucket_a(1,2,3);
...
TokenBucket new_bucket(4,5,6);
bucket_a.swap(new_bucket);
bucket_a.setTokens(new_bucket.tokensLeft());
bucket_a.update(new_bucket.lastUpdate());
== Using other types for the token count and time units
I chose uint64_t because:
1: It has sufficient precision to even specify bits per century.
2: Most 64-bit CPUs has short-circuit calculations of small values in 64-bit registers, so the only cost is memory.
You can change the type of the two typedefs tokencount_t and timeunit_t.
If you change the types to something smaller then you should downscale rate and timeunits, and ensure frequent calls to update() to avoid overflows in the calculations.
The easiest way to downscale them is do divide rate and timeunit by their GCD. Eg rate 15000000 and timeunit 1000000 can be scaled down by factor 64 without loss of precision.