GNOME Bugzilla – Bug 585449
[libgee] Singly linked list implementation
Last modified: 2011-12-19 10:26:10 UTC
libgee should have a singly linked list implementation similar to SList in GLib.
Created attachment 136341 [details] Gee.SList, a singly linked list implementation for libgee
Created attachment 136604 [details] New version of Gee.SList Code cleanup.
Created attachment 136738 [details] [review] The same code (with a little bug fix) + test file as a patch. This patch depends on this one Attachment #136640 [details].
Created attachment 137032 [details] [review] Minor fixes My own libgee repository is visible here: http://git.isonoe.net/libgee/
OK. So we will call this implementation SinglyLinkedList. (Rational is doubly version is used most of the time, so the doubly implementation is simply named LinkedList) Also as discussed on IRC, a _tail private member has to be added, and the add() method made to append at the end of the list and not insert at the begining.
Created attachment 139066 [details] [review] New patch rebased against git master
Created attachment 139067 [details] [review] add now appends instead of prepends. The _tail field will also be useful for the Queue interface.
Created attachment 139075 [details] [review] New method: prepend + various cleanups
Created attachment 139093 [details] [review] Little optimization in SinglyLinkedList.slice.
Created attachment 139094 [details] [review] Various improvements in SinglyLinkedList. - Doc for non inherited methods. - Code optimization in SinglyLinkedList.Iterator.next. - Various cleanups.
Created attachment 139096 [details] [review] Various improvements in SinglyLinkedList. - Doc for non inherited methods. - Code optimization in SinglyLinkedList.Iterator.next. - Various cleanups.
Well, instead of sending endlessly patches, I am giving you the URL of my own branch of libgee which is based on the last git master: http://git.isonoe.net/gnome/libgee/?h=julien
Could we reuse that code to implement a unbounded lock-free queue ? (using AtomicPointer)
The code is no longer accessable however I've done some work on lock-free lists. I hope other lock-free structures will follow.
Created attachment 185308 [details] Original version of my singly linked implementation. I found my old implementation of SinglyLinkedList, it is unlikely that it will compiles against recent version of Vala/libGee. I don't suppose anyone will be interrested in it but we never know :)
This problem has been fixed in the development version. The fix will be available in the next major software release. Thank you for your bug report.