Re: GLib source id wrap around

[Max Krasnyansky <maxk qualcomm com>]

At 09:53 AM 10/13/2003, Owen Taylor wrote:
>On Thu, 2003-10-09 at 20:51, Max Krasnyansky wrote:
>> I'd say we need to add something like following to that function.
>>         /* Handle wrap around. id 0 is invalid */
>>         if (!context->next_id)
>>                 context->next_id = 1;
>
>That won't work, since it doesn't guarantee uniqueness. 
Good point.

>Getting around that without introducing significant overhead isn't obvious to me..
>storing all used IDs in a sorted data structure is possible, but
>expensive.
>
>Another possibility is to keep track of the next range of unused
>IDs ... it gives you excellent performance until you wrap around
>the first time, and after that, still should perform pretty
>well on average as long as the total ID space is sparsely 
>occupied.
>
> if (context->next_id == context->next_used_id)
>   {
>     /* Recalculate context->next_id and next_used_id;
>      * a bit expensive, but can be done O(n_sources)
>      */
>   } 
> else
>   {
>     source_id = context->next_id++;
>   }
May be we could do some hashing of the Source * address or something. Actually
on 32bit platforms we could just use address as an id.

Max