Add an embedded list implementation
Submitted by Neil Roberts
Link to original bug (#652587)
Description
I think it would be a really useful feature if GLib provided an embedded linked-list implementation in the style popularized by the Linux kernel.
For some applications dealing with large lists GList isn't ideal because it requires a separate slice allocation for the list node. The Linux list implementation uses macros to store the list node directly in the struct being listed. This also has the major advantage that removing from a doubly-linked list is O(1) because it can directly get a pointer to the list node given a pointer to the node data. g_list_remove is O(n) because it has to walk the entire list to find the right node.
There was some discussion about this in 2007 here:
http://mail.gnome.org/archives/gtk-devel-list/2007-November/msg00218.html
I guess it's not possible to take the Linux kernel implementation directly because that is licensed under GPL. However I think it should be possible to take the FreeBSD implementation instead which is largely equivalent except it also provides singly-linked lists whereas the Linux version only implements doubly-linked lists. It also doesn't appear to use any GCC-isms or C99-isms.
The new list implementation wouldn't be a replacement for the existing lists in GLib because both are useful in different circumstances.
The discussion around adding this to glib arose from Cogl bug 652514.