[interfacekit] Re: BHandler::fToken

The issue isn't how hard it is to find a known token value; the issue is 
the speed with which we can find the first available *unused* token 
value.  As BHandler-derived instances are destroyed, they return their 
token to BTokenSpace; that token can now be reused.  BTokenSpace keeps 
an internal counter which simultaneously tracks how many tokens have 
been handed out in the life of the app *and* provides the token values 
themselves.

In the *extremely* unlikely event that an application actually manages 
to request 32 bits worth of tokens in a given execution, the counter 
will max out and BTokenSpace will have to start using returned tokens. 
The obvious solution is to walk the token-to-handler map beginning with 
0 until you reach a value which is not contained in the map -- that 
token is not being used currently.  In order to save the overhead of 
walking the map, BTokenSpace has a queue (actually a stack currently) in 
which returned tokens are placed so that once the internal counter is 
maxed out, you don't have to walk the map to try and find a token that 
isn't being used.

This discussion is almost entirely separate from the server token 
discussion, aside from the fact that one of the proposals was that the 
handler token be used as the server token for BViews.

Hope that clears the air a bit. ;)

e

John Hedditch wrote:
> <lurk mode off>
> 
> I think I must be missing something. I don't see why you need a token
> queue at all.
> 
>>From what I can recall from old CS lectures, the hash table is just a way of 
> providing a way of sorting unpredictable
> input data into relatively even piles. If we have as many, or more, buckets
> than inputs, then generally we get no collision, (providing we have a good
> hash function), and we have either one or zero entities per bucket. 
> 
> If we have a 32 bit id as the hash key, and we insert more than 4 billion
> entries, we will get collision, but so what. In the case of 40 billion
> entries it takes 10 lookups to find an entity. That sounds pretty good to
> me.
> 
> Cheers,
> John
> 
> On Tue, Mar 11, 2003 at 04:15:52PM -0800, Erik Jaesler wrote:
> 
>>Axel Dörfler wrote:
>>
>>>Erik Jaesler <erik@xxxxxxxxxxxxxx> wrote:
>>>OTOH looking up a token should be very fast, since we have to do that 
>>>all the time, even more often than creating/deleting them.
>>
>>It's not looking up *one* token that concerns me; even with just a 
>>regular map that's plenty fast.  The case that the token queue is 
>>supposed to deal with is when you've maxed out the token counter.  Once 
>>that's happened, without the queue, you have to start at zero and check, 
>>iteratively, whether a given token is currently being used.  With the 
>>token queue, we have a cache of tokens we *know* aren't being used, so 
>>we don't have to hunt through the token space trying to find a free one. 
>>  With the queue, the only time that would happen is when an app has 
>>maxed the token counter *and* used up everything in the queue.  Maybe 
>>this is an unnecessary concern; perhaps walking the map looking for a 
>>free token will be fast enough even under the worst case.
>>
>>e
>>
>>
> 
>

Other related posts: