Re: get_child() APIs

[Emmanuele Bassi <ebassi gmail com>]

hi Benjamin;

On 9 December 2011 00:38, Benjamin Otte <otte gnome org> wrote:
> Hey Emmanuele,

first of all, thanks a lot for looking into this.

by the by, the first apocalypse is already implemented in Git here:

  http://git.gnome.org/browse/clutter/log/?h=wip/apocalypses/apocalypse-1

though still a work-in-progress.

> And a node basically has these fields:
> class Node {
>  Node parent;
>  Node previous_sibling;
>  Node next_sibling;
>  Node first_child;
>  Node last_child;
> };

> If you were to use this for ClutterActor or GtkContainer, you'd have
> to maintain the list yourself and can't use GList, GSequence or
> GArray.

yes, I thought about using a GQueue-like structure to get at least
first/last child, as well as an inline list. the current
implementation is mostly there because we went for the simple case,
and at the end of the day, we still have public API that expects
lists.

> However, there is also a pretty complicated machinery for accessing
> nodes as an array (using caches and whatnot) to support HTMLs
> childNodes array performantly:
>  http://trac.webkit.org/browser/trunk/Source/WebCore/dom/DynamicNodeList.h
>  http://trac.webkit.org/browser/trunk/Source/WebCore/dom/DynamicNodeList.cpp
> That class basically just caches the count of children and the last
> item and its index (and invalidates both when the list of children
> changes). Note that this is just the base implementation and it can be
> overridden by subclasses. I have not yet investigated how many
> subclasses actually do that.

I think this is mostly an edge case for the Clutter scope, but it
would be interesting to keep it in mind.

> So I am not sure what is the best approach for coming up with a good
> API for working with child actors/widgets. I think this API is good
> enough for what you want to do usually, but if you were to decide to
> use it, you should probably not support a native get_child_at() API
> because then people will write:
> for (i = 0;
>    i < node.count_children();
>    i++)
>  {
>    child = node.get_child_at (i);
>    /* do stuff */
>  }
> which is O(2 * N^2)

yes, but this would be clearly stupid, and it should be documented as
such. computational complexity should be part of the API
documentation.

> If you want to support a get_child_at() API, you need to at least
> support what DynamicNodeList does, which will restore the O(N)
> behavior for the for loop above.

only if we wanted to prevent people from ever doing anything wrong
without ever looking at the documentation; but it's a fair point, and
one to keep in mind.

by the way, there are other apocalypses on the wiki; the other ones
are still in the design phase, and I've yet to write proper exegeses
and synopses, but I'd be interested in thoughts from gtk developers as
well.

ciao,
 Emmanuele.

-- 
W: http://www.emmanuelebassi.name
B: http://blogs.gnome.org/ebassi/