I comitted a small optimization for SPReprs tonight; essentially sp_repr_position() and sp_repr_n_children() are now cached in SPReprs.

The way it's actually accomplished is with SPRepr::_n_siblings, which is the number of siblings counting from that particular repr (inclusive) to the end of the sibling list.

Looking at it from the parent's perspective, SPRepr::_n_siblings of a its first child will == sp_repr_n_children(), and the sp_repr_position() of a specific child will be:

( sp_repr_n_children(parent) - child->_n_siblings )

Normally, only the first child's SPRepr::_n_siblings will be kept up-to-date; there is a boolean flag (SPRepr::_child_counts_complete) in the parent indicating whether the remainder of its children also have up-to-date _n_siblings members.

That flag is checked when sp_repr_position() is called, and the children scanned and updated "lazily" at that time if necessary. This permits node addition and removal to remain constant-time activities.

The beneficial effect is that sp_repr_n_children() is always constant-time, and all calls but the first to sp_repr_position() are also constant-time.

This will be important later for things like the "sort by overall z-order" facility that bulia asked for (we may need it for some finer points of the 0.40 release), as well as Gtk treeview models (which would necessarily heavily query sp_repr_position() to build GtkTreePaths) later.

-mental

p.s. Note that sp_repr_nth_child() isn't any faster, but I don't think it's necessary to further optimize at this time.

p.p.s. _child_counts_complete sucks as a name. any better ideas?