libclc-developers

[Libclc-developers] An alternative clc_list approach + an iterator.

[<bo...@me...>]

Attached is a file containing a list adt as well as an iterator adt. It 
even contains a readme, a test program and a Makefile.

The list adt, clc_list, is a traditional list. The interface it 
currently not complete as this version is just a proof of concept.

The iterator is capable of iterating on any data structure, provided 
that it is initialized properly. It should therefore be possible to use 
it for many different things in libclc, including maps, sets and hashes.

Please review and comment. I think that most errors, conceptual and 
others, must be removed before the concept is presented to c.l.c, so 
this review may turn out to be very important.

Thanks in advance.
Bjørn

Re: [Libclc-developers] An alternative clc_list approach + an iterator.

[Hallvard B F. <h.b...@us...>]

Iterator:

clc_begin() and clc_end() looks like functions that begin and end
something.  Call them clc_atstart() and clc_atend().

Except, we may want more firsts and nexts and whatever, so maybe the
iterator functions should start with clc_iter_, not just clc_.

List:

I still think the names should either be _new and _delete like in C++
or _alloc and _free like in C.  Not the mix _new and _free.
Or neither: _make and _destroy, or something.

-- 
Hallvard

Re: [Libclc-developers] An alternative clc_list approach + an iterator.

[<bo...@me...>]

Hallvard B Furuseth wrote:
> Iterator:
> 
> clc_begin() and clc_end() looks like functions that begin and end
> something.  Call them clc_atstart() and clc_atend().
> 
> Except, we may want more firsts and nexts and whatever, so maybe the
> iterator functions should start with clc_iter_, not just clc_.
> 
> List:
> 
> I still think the names should either be _new and _delete like in C++
> or _alloc and _free like in C.  Not the mix _new and _free.
> Or neither: _make and _destroy, or something.
> 

I see your point and have seen it all along. It's just that I have one 
more adt up my sleeve which I haven't mentioned at all. This may be the 
time?

The adt is a a general purpose pool. It can be used as e.g. a resource 
pool, where the "resource" is an adt. The pool e.g. can be a pool of 
preallocated clc_list objects. This concept is IMO a very good idea in 
some applications, e.g. high performance multithreaded servers where you 
want to avoid malloc()/free() bottlenecks or if you want to utilize 
available memory better by allocating larger chucks of memory and then 
subdivide it into fixed sizes.

The naming problem arises *if* we allow for custom allocators in 
conjunction with our adt's. Straight malloc/free creation can be named 
alloc/free, using a pool better names could be get/release. I currently 
have no good solution, and that's why I've dodged the issue.

Now you all know my dark secret :-)
-- 
boa

Re: [Libclc-developers] An alternative clc_list approach + an iterator.

[<bo...@me...>]

Hallvard B Furuseth wrote:
> Iterator:
> 
> clc_begin() and clc_end() looks like functions that begin and end
> something.  Call them clc_atstart() and clc_atend().

Not a bad idea. ;-)

> 
> Except, we may want more firsts and nexts and whatever, so maybe the
> iterator functions should start with clc_iter_, not just clc_.


clc_first(), clc_last() and friends solves a major issue I've had with 
the whole clc_ prefix requirement, it makes the code *look ugly*. 
Consider looping over a list:
    for(s = clc_iter_first(i); !clc_iter_atend(i); s = clc_iter_next(i))
       ;

It's way too verbose and people will go blind trying to find out what 
the line does. Even with the shortest possible variable names (s&i) and 
a single indentation level of 4 spaces, a line will be 72 characters 
wide!  Now use 8 chars for indentation and add an indentation level or 
two. :-(

I will have a very hard time living with code like that. This is much 
more acceptable:
    for(s = clc_first(i); !clc_atend(i); s = clc_next(i))
       ;

Remember that clc_* is *our* global name space and that we are allowed 
to place functions there. We just have to be careful when choosing which 
ones. If the iterator concept is accepted it will be used for most 
container adt's and hence be widely used. Widely used stuff should be in 
our global namespace, IMO.

(BTW, I would not have named clc_first()/clc_last() just first()/last() 
if there wasn't a prefix requirement.)

Other opinions?


-- 
boa

Re: [Libclc-developers] An alternative clc_list approach + an iterator.

[Hallvard B F. <h.b...@us...>]

Bj=F8rn Augestad writes:
>Hallvard B Furuseth wrote:
>> Iterator: (...)
>>=20
>> Except, we may want more firsts and nexts and whatever, so maybe the
>> iterator functions should start with clc_iter_, not just clc_.
>=20
> clc_first(), clc_last() and friends solves a major issue I've had with=20
> the whole clc_ prefix requirement, it makes the code *look ugly*.=20
> Consider looping over a list:
>     for(s =3D clc_iter_first(i); !clc_iter_atend(i); s =3D clc_iter_next(=
i))
>        ;

      for (s =3D clc_iter_first(i); s; s =3D clc_iter_next(i))
         ;

> Remember that clc_* is *our* global name space and that we are allowed=20
> to place functions there. We just have to be careful when choosing which=
=20
> ones. If the iterator concept is accepted it will be used for most=20
> container adt's and hence be widely used. Widely used stuff should be in
> our global namespace, IMO.

Looks like you are more optimistic for how much iterators will be used
than I am, but I guess it makes sense if you are right.
Maybe I'll re-raise the issue later if the clc_* "global" namespace
gets too full of similar general functions, or if iterators are less
of a success than you hope.

--=20
Hallvard

Re: [Libclc-developers] An alternative clc_list approach + an iterator.

[Hallvard B F. <h.b...@us...>]

Bj=F8rn Augestad writes:
> Attached is a file containing a list adt as well as an iterator adt.

clc_stl.h says:

  typedef struct clc_list_tag* clc_list;
  typedef struct clc_iterator_tag* clc_iterator;

I think typedefs to pointers like this is a bad idea.  It makes
calls to functions like these:

  int clc_list_push_back(clc_list lst, void* data);

look like they are sending a list argument which is only read by the
function, while the function is actually updating through the 'hidden'
pointer.

I'd rather see

  typedef struct clc_list_tag     clc_list;
  typedef struct clc_iterator_tag clc_iterator;

and

  int clc_list_push_back(clc_list *lst, void* data);

--=20
Hallvard

Re: [Libclc-developers] An alternative clc_list approach + an iterator.

[<bo...@me...>]

Hallvard B Furuseth wrote:
> Bjørn Augestad writes:
> 
>>Attached is a file containing a list adt as well as an iterator adt.
> 
> 
> clc_stl.h says:
> 
>   typedef struct clc_list_tag* clc_list;
>   typedef struct clc_iterator_tag* clc_iterator;
> 
> I think typedefs to pointers like this is a bad idea.  It makes
> calls to functions like these:
> 
>   int clc_list_push_back(clc_list lst, void* data);
> 
> look like they are sending a list argument which is only read by the
> function, while the function is actually updating through the 'hidden'
> pointer.
> 
> I'd rather see
> 
>   typedef struct clc_list_tag     clc_list;
>   typedef struct clc_iterator_tag clc_iterator;
> 
> and
> 
>   int clc_list_push_back(clc_list *lst, void* data);

Thanks for the feedback. The general concensus on c.l.c seems to be that 
it's OK to typedef the pointer if no struct members are available 
outside the implementation. That's my opinion as well.

We can compromise by dropping the _tag suffix,
	typedef struct foo* foo;
but then C++ gets *really* confused. ;-)

How about the iterator concept? Do you think it can be applied to all 
the containers we want to add? Performance issues? Will it be too 
complex to use for beginners? Does the design easily create mem leaks?


-- 
boa

libclc home: http://libclc.sourceforge.net

Re: [Libclc-developers] An alternative clc_list approach + an iterator.

[Hallvard B F. <h.b...@us...>]

Bj=F8rn Augestad writes:
>Hallvard B Furuseth wrote:
>>=20
>> clc_stl.h says:
>>=20
>>   typedef struct clc_list_tag* clc_list;
>>   typedef struct clc_iterator_tag* clc_iterator;
>>=20
>> I think typedefs to pointers like this is a bad idea.
>> (...) I'd rather see
>>=20
>>   typedef struct clc_list_tag     clc_list;
>>   typedef struct clc_iterator_tag clc_iterator;
>>=20
>> (...)
>=20
> Thanks for the feedback. The general concensus on c.l.c seems to be that=
=20
> it's OK to typedef the pointer if no struct members are available=20
> outside the implementation.

That's not what c.l.c said last time.  They said one should normally not
typedef a struct at all, but it's OK if no struct members are available
outside the implementation.  While typedefs to pointers are evil.  See:

http://groups.google.com/groups?selm=3Dnewscache%2405mrbh%24jt1%241%40tomat=
o.pcug.org.au
http://groups.google.com/groups?selm=3Db553pt%245f8%241%40sunnews.cern.ch

> That's my opinion as well.
>=20
> We can compromise by dropping the _tag suffix,
> 	typedef struct foo* foo;

Absolutely not!  If we have a struct tag and a typedef with the same
name, they should be the same type.

> How about the iterator concept? Do you think it can be applied to all
> the containers we want to add?

Personally I expect I'll think it's overkill, but let me look at the
actual containers and their built-in ways to iterate first...

> Performance issues?

That's another thing, yes.  A built-in list walker need only take the
previous object as an argument and return the next, or vice versa.

> Will it be too complex to use for beginners?

Don't think so.

> Does the design easily create mem leaks?

Maybe.  It would be safer with
  struct clc_iterator iter;
  clc_iterator_init(&iter, ...);
because then many iterators would not need to be freed at all.

--=20
Hallvard

Re: [Libclc-developers] An alternative clc_list approach + an iterator.

[<bo...@me...>]

Hallvard B Furuseth wrote:
> Bjørn Augestad writes:
> 
>>Hallvard B Furuseth wrote:
>>
>>>clc_stl.h says:
>>>
>>>  typedef struct clc_list_tag* clc_list;
>>>  typedef struct clc_iterator_tag* clc_iterator;
>>>
>>>I think typedefs to pointers like this is a bad idea.
>>>(...) I'd rather see
>>>
>>>  typedef struct clc_list_tag     clc_list;
>>>  typedef struct clc_iterator_tag clc_iterator;
>>>
>>>(...)
>>
>>Thanks for the feedback. The general concensus on c.l.c seems to be that 
>>it's OK to typedef the pointer if no struct members are available 
>>outside the implementation.
> 
> 
> That's not what c.l.c said last time.  They said one should normally not
> typedef a struct at all, but it's OK if no struct members are available
> outside the implementation.  While typedefs to pointers are evil.  See:
> 
> http://groups.google.com/groups?selm=newscache%2405mrbh%24jt1%241%40tomato.pcug.org.au
> http://groups.google.com/groups?selm=b553pt%245f8%241%40sunnews.cern.ch

I must have misread those the last time, possibly mixing in memories 
from the clc_bitset discussion where this issue was discussed as well. 
Memory can be quite selective...

Let's continue to disagree for a while, shall we? ;-)


>>We can compromise by dropping the _tag suffix,
>>	typedef struct foo* foo;
> 
> 
> Absolutely not!  If we have a struct tag and a typedef with the same
> name, they should be the same type.

That was a joke. :-)


>>Does the design easily create mem leaks?
> 
> 
> Maybe.  It would be safer with
>   struct clc_iterator iter;
>   clc_iterator_init(&iter, ...);
> because then many iterators would not need to be freed at all.

Can't do that with an ADT. It has to be allocated since it is an 
incomplete type.


-- 
boa

libclc home: http://libclc.sourceforge.net

Re: [Libclc-developers] An alternative clc_list approach + an iterator.

[Hallvard B F. <h.b...@us...>]

Bj=F8rn Augestad writes:
> [typedefs to pointers]
> Let's continue to disagree for a while, shall we? ;-)

OK.  Until the news discussion...

>>> Does the design [of iterators] easily create mem leaks?
>>=20
>>=20
>> Maybe.  It would be safer with
>>   struct clc_iterator iter;
>>   clc_iterator_init(&iter, ...);
>> because then many iterators would not need to be freed at all.
>=20
> Can't do that with an ADT. It has to be allocated since it is an=20
> incomplete type.

It doesn't have to be an incomplete type just because users shouldn't
access it.  Look at various FILE implementations, for example.  We could
just document that the struct implementation is subject to change and
should not be accessed directly.

--=20
Hallvard