Re: about DoublyLinkedList

I'm CCing this to the kernel list, which is the best place to discuss it. 
Although I have written several of the kernel utils classes, I'm certain 
others have an opinion about them, too.

On 2007-04-01 at 22:21:38 [+0200], Hugo Santos <[email protected]> wrote:
> 
>   I want to use DoublyLinkedList but i have a small issue with its
> iterators. They were designed to be used with while() constructs while
> i prefer for() constructs to iterate through data structures, i think
> it's easier to read. So the particular issue is that the iterator
> starts in an invalid state (i.e. fCurrent = NULL) and is only updated
> after the first Next() call. I would prefer something that could be
> used like this:
> 
>   for (Iterator i = list.First(); i.IsValid(); i.Next()) { ...

You can already use:

	for (Iterator i = list.GetIterator(); i.Next();) {
	}

>   I don't like "IsValid()" much but i think it's better than
> "HasNext()".

In fact the iterator interface for DoublyLinkedList is pretty close to 
Java's iterators and I prefer it a lot over STL style iterators. We 
(basically Tyler and me) designed Vector, VectorSet, VectorMap STL style, 
but I realized quite some time ago, that the Java style feels way closer to 
Be's APIs. And I believe I'll convert the (very rarely used) Vector* 
classes one day.

> Also, i think the operators -> and * are useful so we
> don't have to keep around pointers to the data (and from a C++ POV
> make sense: accessing the iterator and dereferencing it).

Also STL like, though I wouldn't object, if those were added.

> Having
> First() return an Iterator is also better than returning a pointer
> directly as it allows for stuff like:
> 
>   RemoveObject(list.First().Remove());
> 
>   This allows "RemoveHead" to be removed as First().Remove() gets
> inlined into the same code.

The main reason for RemoveHead()'s existence is not code size or 
efficiency, but simplicity. Functionality like this is needed often enough, 
particularly when emptying lists or implementing queue-like behavior, so it 
has got a shorthand.

> Head() could still return a pointer since
> "Head" reflects better the underlying data structure while "First"
> makes more sense from a sequence perspective, and thus the Iterator.
> Also since we are asking for First() instead of GetIterator() it makes
> sense to return a valid iterator (if the list has items of course)
> instead of an "invalid" one as is currently the case.

I think First() and Last() exist mainly because we created a quite a bit of 
confusion by having container classes with different interface. At least 
IMHO GetInterator()/GetReverseIterator() do the job well enough.

>   As the amount of code that uses DoublyLinkedList is still small it
> would be easy to convert all of it to the new interface (if you agree
> of course).

Please don't. :-)

> I would personally convert some of the net stack code to
> use this interface instead of the C list API as a type-safe approach
> is much better.

Definitely. If it was up to me, I would root out the evil pure C code and C 
interfaces in the kernel completely. :-P

CU, Ingo

-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys-and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV