[Gambas-user] [Gambas-devel] gb.adt component

[Tobias Boege]

Oops, the CC: to gambas-user got lost.

---

On Sun, 19 Aug 2012, Beno??t Minisini wrote:
> Hi Tobi,
> 
> If Deque, Stack... classes can be useful, I'm not sure about your List 
> and ListRoot classes.
> 
> I think you tried to mimic in Gambas the way linked list are implemented 
> in C: consequently, the Gambas interface is over-complicated.
> 

Could be. I strived after the least possible constraints on how to use
the List class. ListRoot is just there to automate cleanup. It may got
complicated at the surface...

> First, you must know that linked list are far less useful nowadays. As 
> they trash the CPU cache, using an array is way faster, the speed gain 
> usually compensating the need for reallocation. Bet let's ignore that point.
> 

This information is absolutely new to me - but makes sense!

> I think a List class should have the following interface:
> - Create a new List. (_new)
> - Put one Variant at the beginning. (Add / Append)
> - Put one Variant at the end. (Prepend)
> - Enumerate the contents. (_next)
> - Have an internal cursor, on which we could do a MoveNext() and 
> MovePrevious(). (MoveNext, MovePrevious, MoveFirst, MoveLast).
> - Have a current item, and be allow to retrieve it. (Current)
> - A Count property. (Count)
> - An array method to retrieve the i-th element (slowly of course). 
> (_get), and eventually to modify it (_put)
> - Take the current element from the list (i.e. removing it from the list 
> and returning it). (Take)
> - Find a value inside the list. (Find or FindFirst, maybe FindLast too)
> - Find a value from the current one, forward or backward. (FindNext, 
> FindPrevious).

So we would rather see the 'List' class as a full list and not, as I did, a
single list node at a time. This will certainly ease handling - at the cost
of some power. But hey: Gambas is not C.
Would be good to hear from other Gambas programmers what they would expect a
linked list implementation to look like.

> 
> Internally, the List can be managed with a double-linked list of nodes, 
> each node having a GB_VARIANT_VALUE inside.
> 
> But, for performance reasons, it can later be implemented as a 
> double-linked list of arrays of Variant. Faster, but harder to implement.
> 

This sounds cool! Never heard of such a hybrid approach...

> As for "embedding" the list inside an object, i.e. doing what we usually 
> do in C, I think I understood what you want to do, but I don't think it 
> is really useful in Gambas.
> 

This embedding was the whole OO idea behind the thing. Sure, this would be
useless if we see a List as a whole and not let the programmer touch 'list
nodes'.

The above proposition for List methods and stuff really looks Gambas-like
and so does the idea to not have 'list node' classes but I would probably
miss some of the flexibility then.

Again, others' opinions would be interesting but essentially I am not averse
to this interface...

> The only advantage I see is being able to find the next (or previous) 
> object of the list as soon as you have a reference on the object. Which 
> is not possible with the previous List class.
> 

All operations on the list are valid from every node in the list. If you
embed a list node into a class you have all opportunities to operate on the
full list as long as you have a random object linked to this list flying
around in your current scope.
It could be considered bad style but I can imagine cases for this feature
being really handy. These can also be worked around, sure.

> To do that, maybe I would create another class (something like 
> 'StaticList'). But anyway it will not be easy to have a practical interface!
> 

I don't get the context. 'StaticList' for embedded nodes?

Then we have the mentality of acting on individual nodes again, instead of
the list as a whole - we can cancel that 'Current' property from above and
the like. It would be pretty much like the current implementation, I think.
Except that having two different list classes could help unscramble source
code.
If it is o.k. to have two distinct list classes - always assuming I got your
statements right -, both could be tuned to their special usage. This way it
_may_ be possible to reduce code size and complexity.

> As for having a list interface in the interpreter API: why not. But it 
> would be done if this is really useful, as implementation of linked list 
> is done in a few lines of codes, and usually need to be adapted for 
> performance reasons. Anyway see '/trunk/main/share/gb_list.h'
> and '/trunk/main/share/gb_list_temp.h', which is my own implementation 
> of embedded linked lists in C.
> 

Yes, I mentioned that I saw these files and they are really damn cunning
from a performance point of view - I think so, never tested - similar to
what the Linux kernel does with its container_of() macro if I got it right.
Albeit you need to pass additional parameters to each invocation of the
functions to compute the location of the list structure.

Too, IMHO, it is not a really clean and comfortable design - but no
objection since it may be more efficient than the cleaner data-pointer way.
BTW, do you arrange in LIST_for_each() that only structures with a
statically allocated field "LIST list" can be enumerated?
My point here is that gb_list_temp.h is not universal.

You mean that the implementation that could go into the API must be
optimised for performance; we need not just take the C backend of the Gambas
List class but have an optimised version...?
If we go the way without a data pointer in the list struct - as it seems -,
the container_of() approach will be considerably faster though internally
different because LIST will link to another LIST, not to another container
struct... Feasible if need be.

But, these are all wasted considerations, as you said, if there is just no
need to include a List API at the moment. I most probably won't need any
for gb.ncurses and the last I want is to bloat the interpreter. The above
paragraphs do not count either if there is no point in improving the current
gb_list_temp.h to be more universal.

Regards,
Tobi