[RFC][PATCH] Make GetXIDRange O(1) instead of O(N^2)

[Peter Harris]

On 2013-05-28 03:15, Roberto Ragusa wrote:
> I hope someone can explain the ID reuse stuff. I'm not able to say
> what applications rely on this, but I can say that in my first
> implementation I assumed one add and one free for each ID and the
> KDE desktop was not able to start (and fluxbox too, IIRC).

Clients can reuse IDs, as long as the lifespans are disjoint (otherwise
GetXIDRange would be much less useful). A client cannot reuse an active
ID (see LEGAL_NEW_RESOURCE).

The server can reuse IDs internally in order to create related objects
of a constrained lifetime. For example, A GLX window has a
__glXDrawableRes resource which uses the same ID as the RT_WINDOW it is
based on, so when the client frees the RT_WINDOW the __glXDrawableRes is
also freed automatically.

(Why didn't SGI just use AllocateWindowPrivate? The shared resource ID
mechanism predates the shared devPrivates mechanism. Possibly by enough
that shared devPrivates didn't exist when GLX was being written).

The whole point of GetXIDRange was to avoid the need to track free
resource IDs on the client side. Since computers have a few orders of
magnitude more storage now than they did in 1987, maybe it makes sense
to add (optional?) resource ID tracking to Xlib instead of the server?
In the typical case, Xlib could be re-using IDs before generating new
ones, so the rbtree (or even a simple stack of reusable IDs) shouldn't
grow as large as it would in the server.

(In xcb, resource IDs are explicit. An xcb application that would
benefit from reusing free IDs can already do so.)

Peter Harris
-- 
               Open Text Connectivity Solutions Group
Peter Harris                    http://connectivity.opentext.com/
Research and Development        Phone: +1 905 762 6001
pharris at opentext.com            Toll Free: 1 877 359 4866