Main Page | Report Page

 

  Computers Forum Index » Computer Languages (C) » New release of the C Containers Library (CCL)...

Author Message
jacob navia...
Posted: Sat Oct 30, 2010 3:40 am
 
Hi

The new release contains a significant innovation: generic containers.

Generic containers are like virtual classes in the sense that you have
no creation function, i.e. you can never create a generic container,
only a specific kind of container (list, array, hash table, etc)

The iGenericContainer interface allows to treat all containers for
specific general functions the same. For instance

iGenericContainer.GetSize(someContainer);

will always return a size_t with the number of elements in the
container, no matter which container it is that is passed as argument.

The general container interface has no functions to add an element
however, since the syntax for sequential or associative elements
differ.

A further classification then, allows for those 2 branches:

Sequential containers (lists, arrays, string-arrays, bitststrings, etc)
and associative containers (hash-tables, trees) share with the generic
containers all the generic interface, adding some functions of their own.

This allows for writing of powerful completely general functions like
this "append" function (that is part of the generic sequential
containers interface):

static int Append(SequentialContainer *g1,SequentialContainer *g2)
{
int r;
void *element;
Iterator *it1 = newIterator((GenericContainer *)g2);
for (element = it1->GetFirst(it1);
element != NULL;
element = it1->GetNext(it1)) {
r = iGenericContainer.Add(g1,element);
if (r <=0) {
return r;
}

}
return 1;
}

This function will append to the first container the second one, no
matter what the exact types of g1 or g2 are.

Note that the iterators are part of the generic interface, not the
sequential one.

All of this is completely extensible and will work with ANY future
container that agrees to respect the defined protocol.

jacob
 
Jon...
Posted: Sat Nov 06, 2010 8:17 am
 
jacob navia wrote:

Quote:
For instance to call the generic function "newIterator":

Iterator *newIterator(GenericContainer *gen)
{
return gen->VTable->newIterator(gen);
}

You see?

If you write
Iterator *n = iList.newIterator(container);

You call directly the right function, but then you have to know
that your container is a list.

It costs a function call + indirection + indirect function call.

It costs, apparently: a function call + indirection + indirection +
function call.

Your "notation" makes it seem like it is twice removed whereas it
actually is thrice so.

Quote:
I haven't found any way to avoid that extra call.

#define newIterator(generic_cont)
generic_cont->VTable->newIterator(generic_cont)

Macros: the "poor man's" inline function.
 
Jon...
Posted: Sat Nov 06, 2010 8:21 am
 
Ben Bacarisse wrote:
Quote:
jacob navia <jacob at (no spam) spamsink.net> writes:

Le 01/11/10 11:49, Malcolm McLean a écrit :
On Nov 1, 12:41 pm, jacob navia<ja... at (no spam) spamsink.net> wrote:

I do not know if you can do this in C++. In Objective C you can.

In C++ you make "Container" a virtual base class, that is to say,
you give it pure virtual functions set to " = 0 ". The functions
must be overridden in derived classes that are instantiated.

Interesting...

In my implementation, the generic functions aren't virtual really
since they call the container specific function. This costs an
indirection and an indirect function call in C.

I would be interested to know what the cost of virtual base classes
is in C++ (if any)

I think you're going to be end up with the wrong view of C++ if you
take your information from this group.

I am not a C++ expert, but I believe Malcolm is wrong about how "you
make" containers in C++. Using inheritance and virtual base classes
is, I think, regarded as how *not* to do it. The STL uses template
classes and though inheritance is used (particularly for types with a
lot of shared behaviour like iterators) there is no ultimate
container virtual base class.

Maybe the C++ people rejected the design Jacob is proposing for a good
reason ya think? It's not good enough for C++ but good enough for "second
class" C?
 
Jon...
Posted: Sat Nov 06, 2010 8:36 am
 
Ian Collins wrote:
Quote:
On 11/ 2/10 01:46 AM, Ben Bacarisse wrote:
jacob navia<jacob at (no spam) spamsink.net> writes:

Le 01/11/10 11:49, Malcolm McLean a écrit :
On Nov 1, 12:41 pm, jacob navia<ja... at (no spam) spamsink.net> wrote:

I do not know if you can do this in C++. In Objective C you can.

In C++ you make "Container" a virtual base class, that is to say,
you give it pure virtual functions set to " = 0 ". The functions
must be overridden in derived classes that are instantiated.

Interesting...

In my implementation, the generic functions aren't virtual really
since they call the container specific function. This costs an
indirection and an indirect function call in C.

I would be interested to know what the cost of virtual base classes
is in C++ (if any)

I think you're going to be end up with the wrong view of C++ if you
take your information from this group.

I am not a C++ expert, but I believe Malcolm is wrong about how "you
make" containers in C++. Using inheritance and virtual base classes
is, I think, regarded as how *not* to do it. The STL uses template
classes and though inheritance is used (particularly for types with
a lot of shared behaviour like iterators) there is no ultimate
container virtual base class.

That's a fair summary.

The cost of the C++ approach

C++ is much much broader in scope than a single library (STL) or the C++
standard. There's that "little" think called *programming* that seems to
escape "language lawyers" quite regularly. You should have said "STL
approach" instead of "C++ approach".

Quote:
is it requires some form of generics
(templates) and the benefit is performance. While removing indirect
function calls only contributes a small performance gain, the ability
to optimise away those calls can make significant performance gains.

And, "of course", since Lamborghini's are available, SUVs are irrelevant.

http://www.lamborghinihouston.com/
http://automobiles.honda.com/cr-v/price.aspx
 
Jon...
Posted: Sat Nov 06, 2010 8:46 am
 
MartinBroadhurst wrote:
Quote:
On 1 Nov, 10:49, Malcolm McLean <malcolm.mcle... at (no spam) btinternet.com
wrote:
On Nov 1, 12:41 pm, jacob navia <ja... at (no spam) spamsink.net> wrote:

I do not know if you can do this in C++. In Objective C you can.

In C++ you make "Container" a virtual base class, that is to say, you
give it pure virtual functions set to " = 0 ".

No, a virtual base class is one that can be inherited more than once
without duplication of members.
You are talking about an abstract base class.

What C++ forgot and Java remembered was the "interface". You can
achieve nearly the same thing with multiple inheritance, but that
leads into all sorts of difficulties.

At 2 levels: The language implementation level (very hard/complex) and
the language usage level (inelegant/kludgy).

Quote:

No it doesn't because you are inheriting from abstract base classes.
The problems with multiple inheritance manifest themselves when you
inherit from multiple concrete classes - hence the need for virtual
base classes.


Virtual derivation from C++ ABCs is still required when faced with "the
diamond of death" (at least with VC++ I know that it does).
 
Jon...
Posted: Sat Nov 06, 2010 8:50 am
 
MartinBroadhurst wrote:
Quote:
On 1 Nov, 11:22, jacob navia <ja... at (no spam) spamsink.net> wrote:

But in C++ you cannot use an abstract class as a parameter type, a
function return type, or the type of an explicit conversion


You would use a *pointer* to an abstract base class, just as we're
using pointers here in C.


Yes, the polymorphic behavior (passing a derived class to something
specifying a base class) in C++ is via pointers and references.
 
Jon...
Posted: Sat Nov 06, 2010 8:56 am
 
MartinBroadhurst wrote:
Quote:
On 1 Nov, 11:40, jacob navia <ja... at (no spam) spamsink.net> wrote:

Well, then it corresponds exactly to an abstract structure in C.
(struct foo;)

Do an abstract class force a performance penalty in C++?


Yes, because there is an extra level of indirection. When a method is
called on a pointer to an abstract base class, the vtable is retrieved
from the address point of the object, and then the derived class
method pointer is retrieved from the vtable.

When I call an abstract class, does the generated code have more to
do?


Yes, for the same reason. In addition, there is some overhead in
constructing objects with virtual functions because the vtable needs
to be set up.


You are assuming the obvious simplistic implementation (like the one
presented in "The C++ Object Model"). I wouldn't be surprised to find
"zero overhead" implementation in certain scenarios. Anyway, my point is
that there are a number of ways to implement OO and C++ does not specify
*how* to do it, only that the resultant behavior be as specified.
 
Jon...
Posted: Sat Nov 06, 2010 9:11 am
 
jacob navia wrote:
Quote:
Le 01/11/10 12:46, MartinBroadhurst a crit :
On 1 Nov, 11:40, jacob navia<ja... at (no spam) spamsink.net> wrote:

Well, then it corresponds exactly to an abstract structure in C.
(struct foo;)

Do an abstract class force a performance penalty in C++?


Yes, because there is an extra level of indirection. When a method is
called on a pointer to an abstract base class, the vtable is
retrieved from the address point of the object, and then the derived
class method pointer is retrieved from the vtable.

That is exactly what I do:

For instance to call the generic function "newIterator":

Iterator *newIterator(GenericContainer *gen)
{
return gen->VTable->newIterator(gen);
}

I call the vtable of the object. Since the vtables of all
containers contain the function "newIterator" at the same position,
this works.

I do it with ONE indirection, and not two, as you can see.

OK, then if I am at the same level of C++ it is OK.

Don't kid yourself. I don't think you'd be likely to find any commercial
compiler that implements C++ OO characteristics like a college student in
course called OO 101 would implement it. Basically though, if you are
working at the language level (rather than the implementation level) in
C, the *best* you can achieve is to *approach* that OO 101 thing. What
your comparison should be against is "zero overhead" and not some toy
implementation of OO, because I think that *is* achieved in some
instances in commercial C++ compilers (not always, but for certain
constructs in certain cases).

Quote:
What is relly nice when working in C is the absolute freedom to do as
you want. In this case, not having ANY object oriented framework is a
bonus in some ways since you can lay out your object as you want.

Of course though, what you end up with, no matter how clever your C
language-level OO implementation, is still just a hack.
 
Jon...
Posted: Sat Nov 06, 2010 9:22 am
 
MartinBroadhurst wrote:
Quote:
On 1 Nov, 12:28, jacob navia <ja... at (no spam) spamsink.net> wrote:

That is exactly what I do:

For instance to call the generic function "newIterator":

Iterator *newIterator(GenericContainer *gen)
{
return gen->VTable->newIterator(gen);

}

I call the vtable of the object. Since the vtables of all
containers contain the function "newIterator" at the same position,
this works.


If you want to know how C++ abstract base classes are actually laid
out in memory, get hold of the Windows SDK and look in the Include
directory for a header file that has a corresponding .idl file with
the same name, say oledb.h. Search the file for the string "C style
interface". What you will see is a vtable, and a C struct containing
it, that have been laid out to be identical to a C++ abstract base
class. This is provided so that C programmers can write COM
components.

There is also an article about COM programming in C on MSDN that I
found quite informative here:

http://msdn.microsoft.com/en-us/library/ms809982.aspx


MS COM objects != C++ objects! MS had to invent COM because it was
concerned with cross-language OO. COM is at a much higher level than
language implementation. Apples and oranges.
 
jacob navia...
Posted: Sat Nov 06, 2010 11:53 am
 
Le 06/11/10 05:56, Jon a crit :

Quote:
You are assuming the obvious simplistic implementation (like the one
presented in "The C++ Object Model"). I wouldn't be surprised to find
"zero overhead" implementation in certain scenarios. Anyway, my point is
that there are a number of ways to implement OO and C++ does not specify
*how* to do it, only that the resultant behavior be as specified.



C compilers can optimize this constructs too, and end up with a zero
overhead implementation. That is why is important that it be standardized.
 
jacob navia...
Posted: Sat Nov 06, 2010 11:53 am
 
Le 06/11/10 06:11, Jon a crit :
Quote:
jacob navia wrote:
Le 01/11/10 12:46, MartinBroadhurst a crit :
On 1 Nov, 11:40, jacob navia<ja... at (no spam) spamsink.net> wrote:

Well, then it corresponds exactly to an abstract structure in C.
(struct foo;)

Do an abstract class force a performance penalty in C++?


Yes, because there is an extra level of indirection. When a method is
called on a pointer to an abstract base class, the vtable is
retrieved from the address point of the object, and then the derived
class method pointer is retrieved from the vtable.

That is exactly what I do:

For instance to call the generic function "newIterator":

Iterator *newIterator(GenericContainer *gen)
{
return gen->VTable->newIterator(gen);
}

I call the vtable of the object. Since the vtables of all
containers contain the function "newIterator" at the same position,
this works.

I do it with ONE indirection, and not two, as you can see.

OK, then if I am at the same level of C++ it is OK.

Don't kid yourself. I don't think you'd be likely to find any commercial
compiler that implements C++ OO characteristics like a college student in
course called OO 101 would implement it. Basically though, if you are
working at the language level (rather than the implementation level) in
C, the *best* you can achieve is to *approach* that OO 101 thing. What
your comparison should be against is "zero overhead" and not some toy
implementation of OO, because I think that *is* achieved in some
instances in commercial C++ compilers (not always, but for certain
constructs in certain cases).


That will be the case for C compilers too if these propositions are
standardized. They can also optimize away the indirections since all
those procedures are open for a given implementation.

When writing the sample implementation hoewever, that should compile in
ALL compilers (include C90 onees) without ANY implementation hack, it is
impossible to use inline or macros, as you propose elsewhere.

Quote:
What is relly nice when working in C is the absolute freedom to do as
you want. In this case, not having ANY object oriented framework is a
bonus in some ways since you can lay out your object as you want.

Of course though, what you end up with, no matter how clever your C
language-level OO implementation, is still just a hack.

I am not implementing any OO language. It is an OO based design, but it
requires no language changes whatsoever.

The interfaces that I propose are very similar to the "protocols" of
objective C.
 
Jon...
Posted: Tue Nov 09, 2010 2:31 am
 
MartinBroadhurst wrote:
Quote:
On Nov 8, 7:43 pm, "Jon" <jo... at (no spam) spblocker.net> wrote:

Just because you found other incorrect usages of the term
doesn't make it correct. A "concrete" class in C++ is one who's
object instances behave like built-in types. Such a class must
include the following special member functions: a default
constructor, a copy constructor, a copy-assignment operator, a
destructor.


Which built-in types? Integers?

class C
{
/* No need to define a default constructor; one is implicitly
defined */
/* No need to define a copy constructor; one is implicitly defined
*/
/* No need to define a copy-assignment operator; one is implicitly
defined */
/* No need to define a destructor; one is implicitly defined */
};

C c1;
C c2;
c1 += c2; /* Damn! */


I've said all that needs to be said with "my" "definition" above. Use it
or don't. "No skin off of my nose". *I* didn't make the definition, the
language creators did. Take it up with them.
 
Jon...
Posted: Tue Nov 09, 2010 2:31 am
 
MartinBroadhurst wrote:
Quote:
On Nov 8, 7:43 pm, "Jon" <jo... at (no spam) spblocker.net> wrote:

Just because you found other incorrect usages of the term
doesn't make it correct. A "concrete" class in C++ is one who's
object instances behave like built-in types. Such a class must
include the following special member functions: a default
constructor, a copy constructor, a copy-assignment operator, a
destructor.


Which built-in types? Integers?

class C
{
/* No need to define a default constructor; one is implicitly
defined */
/* No need to define a copy constructor; one is implicitly defined
*/
/* No need to define a copy-assignment operator; one is implicitly
defined */
/* No need to define a destructor; one is implicitly defined */
};

C c1;
C c2;
c1 += c2; /* Damn! */


I've said all that needs to be said with "my" "definition" above. Use it
or don't. "No skin off of my nose". *I* didn't make the definition, the
language creators did. Take it up with them.
 
Jon...
Posted: Tue Nov 09, 2010 2:31 am
 
MartinBroadhurst wrote:
Quote:
On Nov 8, 7:43 pm, "Jon" <jo... at (no spam) spblocker.net> wrote:

Just because you found other incorrect usages of the term
doesn't make it correct. A "concrete" class in C++ is one who's
object instances behave like built-in types. Such a class must
include the following special member functions: a default
constructor, a copy constructor, a copy-assignment operator, a
destructor.


Jon, you're so wrong that people who are merely massively in error
look to you for consolation.
You're so wrong that the people of the planet Wrong have rung to say
that they don't know you.
You're so wrong that somewhere in Paris, there is an aluminium
simulacrum of you; it is the SI unit of being wrong.


Okie dokie.
 
Seebs...
Posted: Tue Nov 09, 2010 2:35 am
 
On 2010-11-08, MartinBroadhurst <martin.broadhurst at (no spam) gmail.com> wrote:
Quote:
Jon, you're so wrong that people who are merely massively in error
look to you for consolation.
You're so wrong that the people of the planet Wrong have rung to say
that they don't know you.
You're so wrong that somewhere in Paris, there is an aluminium
simulacrum of you; it is the SI unit of being wrong.

The term is "fractally wrong":

http://www.alphadictionary.com/blog/?p=200

"The state of being wrong at every conceivable scale of
resolution. That is, from a distance, a fractally wrong
person's worldview is incorrect; and furthermore, if you
zoom in on any small part of that person's worldview, that
part is just as wrong as the whole worldview."

We get a fair number of examples of them around here.

-s
--
Copyright 2010, all wrongs reversed. Peter Seebach / usenet-nospam at (no spam) seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
I am not speaking for my employer, although they do rent some of my opinions.
 
 
Page 1 of 2    Goto page 1, 2  Next
All times are GMT
The time now is Fri Apr 18, 2014 6:20 am