GBSearchArray

[Owen Taylor <otaylor redhat com>]

OK, I spent some time looking at the GBSearchArray. The first thing
I'd say is, if it is public API, then we need docs for it. I had to
spend some time reading through the implementation to figure out 
how it works.

But that being said, I don't think it belongs in GLib. It's not really
a container like GHash/GTree/GList/GSList/GQueue, since our generic
containers are by-reference, not by value. What it is, is a rewrite of
GArray, with slightly different tradeoffs for memory and speed, and
the addition of sorted searching.

I understand that for applications like object data, these may be be
important differences, and its fine to have this as an internal
implementation detail of GObject, but IMO adding this to the public
GLib API is not the right way to keep the public API of GLib simple
and understandable.

To provide the same basic performance guarantees, it would be better
to simply add something along the lines:

GArray* g_array_insert_sorted (GArray           *array,
			       gconstpointer     data,
                               GCompareDataFunc  compare_func,
                               gpointer          user_data); 
gint g_array_bsearch (GArray           *array,
	              gconstpointer     key,
                      GCompareDataFunc  compare_func,
                      gpointer          user_data); 

(-1 to indicate not found; or maybe, use GCompareFunc, and add _with_data
variants - this would be more consistent with current API's, if a little
more long winded when user data is needed.)

I don't like the idea of having multiple, somewhat similar API's 
(compare g_array_free/g_bsearch_array_destroy, g_bsearch_array_get_nth,
g_array_index, etc). The more we can keep things simple and consistent,
the happier our users will be.

Regards,
                                        Owen