Re: GLib source id wrap around

[Soeren Sandmann <sandmann daimi au dk>]

Owen Taylor <otaylor redhat com> writes:

> storing all used IDs in a sorted data structure is possible, but
> expensive.

I occured to me that this can be done using just two bits per stored
ID. The data structure is a binary tree storing all numbers in a range
[0, 2^k - 1], like this one for the range [0, 15]:

                       .
               .               .
           .       .       .       .
         .   .   .   .   .   .   .   .
        . . . . . . . . . . . . . . . .
        0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1
                            0 1 2 3 4 5


Each dot in the tree is a bit meaning

        TRUE, all leaves below me are used 
        FALSE, there is at least one unused leaf below me

This would allow you to find an available leaf in time O(log n). When
the range overflows, you build a new tree twice the size of the old
one. You can do that without additional cost, because at this point
because at that point you already spent at least time O(n).

Since the tree is always perfectly balanced it is possible to
represent it by an array. Just write out the tree layer by layer.
Then given the index of a bit in the array you can find the index of
its relatives by the formulas

        parent:         (index - index % 2 + 1) / 2
        left child:     index * 2 + 1
        right child:    index * 2 + 2

The size of the tree is twice the number of numbers stored in it,
ie. it uses two bits per stored id.


Søren