Re: [Evolution-hackers] [maybe OT?] Code excerpts from Evolution

[Not Zed <notzed ximian com>]

Hi Tom,

"evolution-2.0.2/e-util/e-memory.c uses a GTree to track memory "chunks" that can be freed. It uses a custom GCompareFunc, tree_compare, to order the _cleaninfo structures which point to freeable chunks."

This isn't quite right.  It doesn't use a gtree to track the chunks, it uses it to calculate the unused chunks.  Subtle difference - in that the tree is used as a one-off structure during the clean process, not as long-term tracking structure.

We probably have more interesting collection usage throughout the code, although some of the more interesting ones don't use glib.

We actually don't use g* collections for many things we might, because of efficiency & preference issues.  Evolution also has many of its own data structures, because the glib ones aren't flexible enough or suitable.  e.g. its own m-tree structures in several places, its own single and double-linked list implementations, etc.

e.g. edlist is a double-linked list implementation which has O(1) append and prepend, and O(1) removal of head and tail nodes.  GList has O(N) append and O(N) removal of the tail node.  This often leads to unecessary and inefficient code such as g_list_reverse, or having to manually track the tail node which is prone to coding mistakes.  It also means you can't re-use the same simple code as a stack, a queue, or an ordered list without a performance penalty in some of the cases - there are even more special api's for each case.

In general, the glib collections:

• have inconsistent interfaces, e.g. g_ptr_array_add vs g_*array*append, g_list_free vs g_hash_table_destroy, g_list_nth vs g_array_index, g_list_length vs g_hash_table_size, etc.
• most of the interfaces are over-designed - glist has 30 functions and 2 macros.
• are not very well implemented, generally each is implemented separately with no overlap (glist vs gslist, g*array vs gstring), or the overlap and 'subclassing' is funny (e.g. g*array).
• cannot be subclassed or extended in any way.  not even internally!  e.g. GQueue vs GList.
• often can only be iterated using callbacks, without iterators, making some code much more complex and less efficient than needed (e.g. requiring one-off callback data structures to be written).  A particularly bad case is GHashTable.
• provide zero type safety.  At least if the base structures could be extended they could provide some type safety.  e.g. edlist provides data node type safety at least by having each usage 'subclass' the next/prev node pointers structure.
• aren't as flexible and efficient as they might be.  e.g. you often store a hashtable key+data pair where the data contains the key, or it can be calculated from the data.  So you end up wasting a pointer storing a duplicate of the key pointer.  Or worse, where you store an integer as the data pointer which has portability as well as type issues.
• I could probably go on ...

To put it bluntly, glib's data structures 'mostly suck', but they're there, and usually simple to use, so we use them sometimes.

Cheers,
 Michael

On Mon, 2005-05-02 at 16:58 -0400, Tom Copeland wrote:
> Howdy -
>
> Here's a bit of Evolution "code publicity" I thought folks might be
> interested in.  I'm working on a tutorial for IBM's developerWorks site
> on the GLib collections - GSList, GHashTable, GTree, and all that.  As
> part of the tutorial, I'm picking out excerpts of various collection
> types from a couple of nice open source apps: Gaim, the GIMP, and,
> naturally, Evolution.  
>
> Here's a list of the references to Evolution that I've currently got in
> the article:
>
> http://infoether.com/~tom/evolution_snippets.html
>
> If anyone has any suggestions/corrections to the descriptions of these
> usages, please email me at tom infoether com (or here if you think it's
> on-topic enough).  
>
> Many thanks,
>
> Tom Copeland
> tom infoether com
>
> _______________________________________________
> evolution-hackers maillist  -  evolution-hackers lists ximian com
> http://lists.ximian.com/mailman/listinfo/evolution-hackers