[Xcb] magical callback funness

[Jamey Sharp]

On Fri, Mar 25, 2005 at 01:26:16AM -0800, Barton C Massey wrote:
> In message <20050325091606.GI1769 at minilop.net> you wrote:
> > I'm more concerned about whether it will make XCB harder to use. I like
> > the fact that the current implementation has the ability to detect
> > errors at run-time both for unexpected replies and for expected replies
> > that never come. This change will make those run-time checks harder.
> 
> You and me both.  I think the magic bit isn't that hard to
> add, and only requests that can generate multiple replies
> should accept them---I could be talked out of this view,
> though.

Call me a waffler if you like, but that's a view that is hard to argue
with. Still, I think I'll implement without the magic bit, and add it
later as a simple error-check.

> > Yeah, it could do that, but that involves a linear-time walk through the
> > queue: not so good, but the best I'd come up with so far. (Also I built
> > an abstraction layer around the linked lists in XCB a long time ago, and
> > that layer makes this particular walk a little awkward. It's also become
> > a performance limit. It'll go away eventually.) I think a better data
> > structure will be necessary, but we'll have to see how the initial
> > implementation falls out to figure out how it should work.
> 
> So I'm quite confused by the XCB data structures at this
> point.  Is there some reason that you don't have an
> array-based queue that's binary searchable or direct-indexed
> by sequence number?

There are two reasons: first, I haven't implemented one for XCB yet.
Second, I haven't finished studying XCB's access patterns (and my
friendly local algorithms textbook) to decide which data structure is
most appropriate. So it's stayed a linked list, so far. :-)
(*Everything* in XCB is a linked list. I had this handy abstraction
layer, so I, er, used it. Map? Queue? LRU cache? What's the difference?)

Until this week, I think it was very unusual for more than two or three
entries to be in the queue at once, so the issue never came up. My
window manager was the only app I can think of that might have exceeded
that, and then only in proportion to the number of windows it had to get
geometry for at startup.

I note the array direct-indexed by sequence number, which is an
attractive option, makes the linear search problem worse: it should turn
out to be a sparse array. I hadn't considered binary-searching a
circular array, which is an interesting option, but the application can
cause entries to be removed from the queue in any order, so I'm not sure
it'll work out.

> If anybody's taking anybody seriously around here, I'm sure
> we're all in big trouble.

Most of all if they're listening to *me*... :-)

> Go to bed; it's late :-).

"Hey kettle? The pot called again..." ;-)

--Jamey