Web site for the containers library

[jacob navia]

I have set up a google project for the containers library.

http://code.google.com/p/ccl/

This project tries to address the problem of the lack of an easy to use
library that would complement the standard library so that not every
c programmer has to reinvent hash tables, flexible arrays, red-black
trees, and similar data structures.

I will present this project to the french standardization group as
soon as it is possible.

Please read the documentation in downloads/ccl.pdf

The source can be browsed in source/svn/trunk

jacob

 

[jacob navia]

Le 10/01/11 00:39, Richard a écrit :

Whats wrong with the oodles of OSS solutions out there?

(1) This library introduces the concept of an interface, i.e. a table
of functions in a single object that opens a new name space to avoid
as much as possible name pollution.

The syntax looks like:

HashTable *ht = iHashTable.Create(512); // Creation

iHashTable.Add(ht,"A key", &data); //add an element

d = iHashTable.GetElement(ht, "A key"); // Retrieve data

iHashTable.Finalize(ht); // Destroy the table

The only name used here is "iHashTable". The interface is the
table of functions of the HashTable container.

(2) This library introduces the concept of a general container,
and a subclassing of it: sequential and associative containers.
All containers share the same vocabulary. It is easy then,
to change the data representation without doing enormous
changes to the code.

(3) It introduces the concept of general iterators that allow you to
use the same vocabulary for iterating through a container, be it
a list or a hash table.

But the main point is that it proposes a standard way of handling this
data structures. My goal is to achieve an extension of the standard
library so that software written in C can interoperate. The problem
with the absence of a standard way of doing a list or a hash table
is that
(1) Each developer has to develop again and again the same software
(2) The resulting mess of slightly different implementations forces
the developer to develop "adapters" that convert lists in XYZ format
to lists in ZYX format...

Note that the aim is here not to provide a library (even if a sample
implementation is provided) but a *standard* vocabulary.

For instance, using the same vocabulary an implementation can develop
a small bare bones version for small machines, and a full fledged
version for bigger machines.

Please take a look to the documentation (pdf) to see more in detail what
is this proposal about.

 

[Ben Pfaff]

All containers share the same vocabulary. It is easy then,
to change the data representation without doing enormous
changes to the code.

Developers promoting container libraries often mention this as a
feature. But why is it such a great feature? Who wants to
change data representations often?

 

[Ian Collins]

Developers promoting container libraries often mention this as a
feature. But why is it such a great feature? Who wants to
change data representations often?

It's not that uncommon when you can!

In C++ sometimes find I want a sorted container when I initially did not.

Then there's generic algorithms..

 

[jacob navia]

Le 10/01/11 01:05, Ben Pfaff a écrit :

Developers promoting container libraries often mention this as a
feature. But why is it such a great feature? Who wants to
change data representations often?

It is possible to change from a single linked list
to a double linked, for instance, if you see that you are
inserting very often items at the middle of a list.

Or to drop lists altogether and use an array if you see that you are
not inserting so much and a flexible array would be much faster.

Or you decide that the bottleneck of searching through the whole array
is too much and you need a hash table.

Applications discover that some of the assumptions done at
design time are no longer valid. Hence it is important
to be able to change that.

jacob

 

[Tim Harig]

["Followup-To:" header set to comp.lang.c.]

Whats wrong with the oodles of OSS solutions out there?

Using OSS libraries has worked well; but, because there are so many
available with different interfaces, it also causes some common problems:

1. It create yet another dependency that people using your software have to
contend with and bloat because it means having to have several
different redundant libraries installed to meet the needs of
different pieces of software with each using their own preferred
library.

2. It creates a complexity issue for developers who may have to learn
several different redundant interfaces to work with different
projects to which they might contribute.

 

[Charles]

Developers promoting container libraries often mention this as a
feature.

It's a stepping stone. It's where all container library developers start
out. As experience increases with that design, its limitations and
"incorrectness" become clear.

But why is it such a great feature?

It's not.

Who wants to
change data representations often?

Inexperienced and/or unknowledgeable developers or those who won't or
can't analyze and design before jumping in and coding. I see no reason to
build a library in a fashion to support that. Indeed, it is GOOD for
someone to have more tedium when a design change is necessary because of
inadequate capability or preparation, for learning by making mistakes is
a powerful teaching process.

 

[Charles]

Le 10/01/11 01:05, Ben Pfaff a écrit :

It is possible to change from a single linked list
to a double linked, for instance, if you see that you are
inserting very often items at the middle of a list.

Or to drop lists altogether and use an array if you see that you are
not inserting so much and a flexible array would be much faster.

Or you decide that the bottleneck of searching through the whole array
is too much and you need a hash table.

Those scenarios are all from lack of understanding of the requirements
(or lack of understanding of containers/algos and how/when to use them)
or lack of skills beyond coding (analysis and design).

Applications discover

How many applications have you seen discover anything? Do you work in the
AI field?

that some of the assumptions done at
design time are no longer valid. Hence it is important
to be able to change that.

That's some "hearty" reasoning! Are you high? ;-)

 

[Tim Harig]

Inexperienced and/or unknowledgeable developers or those who won't or
can't analyze and design before jumping in and coding. I see no reason to
build a library in a fashion to support that. Indeed, it is GOOD for
someone to have more tedium when a design change is necessary because of
inadequate capability or preparation, for learning by making mistakes is
a powerful teaching process.

Fred Brookes told us to plan to throw away because you will anyway.
Perhaps you don't think he was intelligent enough to plan ahead?
Pitfalls of preoptimization are well known and the simple fact is that
requirements have a tendency to change. All the planning in the world
will not help you when somebody decides to use a display engine you
decided that you designed as a web browser as the basis for an IDE and
development platform. That your code was flexible enough to hit the
ground running when requirement changes take place or when being used
for things you never originally intended *is* a good measure of how well
you planned your project.

 

[Ian Collins]

Those scenarios are all from lack of understanding of the requirements
(or lack of understanding of containers/algos and how/when to use them)
or lack of skills beyond coding (analysis and design).

Nonsense.

How many clients do you have who know exactly what they want at the
start of a project and never change the project scope?

 

[copx]

"jacob navia" wrote in message news:[email protected]...

I have set up a google project for the containers library.

http://code.google.com/p/ccl/

Looks nice, thank you for distributing this for free (BSD-license).
I will try it when the opportunity arises.

Will you include more container ADTs in future or is this the
final set? Given that you say that one of the features of your library
is that it's relatively easy to switch from one ADT to another (good idea
BTW!) it would be interesting to compare the performance of the various
ADTs in practical situations. Right now your library only includes to most
common and basic ADTs. I always wanted to try Judy arrays for example:
http://en.wikipedia.org/wiki/Judy_array

 

[jacob navia]

Le 10/01/11 09:51, copx a écrit :

in message news:[email protected]...

Looks nice, thank you for distributing this for free (BSD-license).
I will try it when the opportunity arises.

Will you include more container ADTs in future or is this the
final set? Given that you say that one of the features of your library
is that it's relatively easy to switch from one ADT to another (good idea
BTW!) it would be interesting to compare the performance of the various
ADTs in practical situations. Right now your library only includes to
most common and basic ADTs. I always wanted to try Judy arrays for example:
http://en.wikipedia.org/wiki/Judy_array

Well, the problem is:

<quote>
Judy was invented at HP's UNIX Software Enablement Laboratory at Fort
Collins Colorado. Hewlett-Packard has patents pending on the Judy
Technology.
<end quote>

I do not want to have HP's lawyers knocking at my door.

Besides that, it is really a good technology.

 

[jacob navia]

Le 10/01/11 07:17, Charles a écrit :

Those scenarios are all from lack of understanding of the requirements
(or lack of understanding of containers/algos and how/when to use them)
or lack of skills beyond coding (analysis and design).

Sure. In your world requirements never change, designers know in
advance all that is to know, and once the application is running
it will be used exactly as the designer thought. Forever.


Sorry, but I live in another world as your ideal one. In mine,
at design time requirements are very vague, and then when the
application is running, it will be used in very different
ways as you were told. Minor features become major ones,
and what you thought were important features become
unimportant.

How many applications have you seen discover anything? Do you work in the
AI field?

clever, clever. I missed "programmer", it should have been
"applications programmer".

Now, that type onvalidate everything else of course.

 

[jacob navia]

Le 10/01/11 07:52, Tim Harig a écrit :

Fred Brookes told us to plan to throw away because you will anyway.
Perhaps you don't think he was intelligent enough to plan ahead?
Pitfalls of preoptimization are well known and the simple fact is that
requirements have a tendency to change. All the planning in the world
will not help you when somebody decides to use a display engine you
decided that you designed as a web browser as the basis for an IDE and
development platform. That your code was flexible enough to hit the
ground running when requirement changes take place or when being used
for things you never originally intended *is* a good measure of how well
you planned your project.

In Charles' world, requirements never change, everything is known
on advance, etc.

This is the type of person pontificating (it is very cheap) without
any REAL world experience.

 

[copx]

"jacob navia" wrote in message news:[email protected]...

Well, the problem is:

<quote>
Judy was invented at HP's UNIX Software Enablement Laboratory at Fort
Collins Colorado. Hewlett-Packard has patents pending on the Judy
Technology.
<end quote>

Oh.. I wasn't aware of that issue.

I do not want to have HP's lawyers knocking at my door.

Understandable.

 

[Charles]

Le 10/01/11 07:17, Charles a écrit :

Sure. In your world requirements never change, designers know in
advance all that is to know, and once the application is running
it will be used exactly as the designer thought. Forever.


Sorry, but I live in another world as your ideal one. In mine,
at design time requirements are very vague, and then when the
application is running, it will be used in very different
ways as you were told. Minor features become major ones,
and what you thought were important features become
unimportant.

No, you see, just because you and Ian don't know how to run projects,
manage clients, extract and analyze requirements and design software does
not mean that other people don't know how to. And no need to pretend that
you two do, for both of your responses show lack of any such
understanding or capability. It's OK not to know and to be "just" a
programmer, but stop pretending about the other things, because you are
not fooling anyone. Stop fooling yourselves. And if you are just throwing
a tantrum because you WISH things were as you describe, well that's worse
than actually not knowing: won't YOU be surprised when you figure out
that people aren't stupid.

 

[jacob navia]

Le 10/01/11 15:22, Charles a écrit :

No, you see, just because you and Ian don't know how to run projects,
manage clients, extract and analyze requirements and design software does
not mean that other people don't know how to.

Ahhhh OK.

You are the best manager in the whole world, oh pardon, of the whole
Universe.

And no need to pretend that
you two do, for both of your responses show lack of any such
understanding or capability.

Of course. We are nothing compared to your Honor. NOTHING,
not even a worm compared to an eagle.

It's OK not to know and to be "just" a
programmer,

Ohhh thank you Sir, how much consideration for our humble souls...

but stop pretending about the other things, because you are
not fooling anyone. Stop fooling yourselves.

YES your Honor. We are nothing, nothing at all.

And if you are just throwing
a tantrum because you WISH things were as you describe, well that's worse
than actually not knowing: won't YOU be surprised when you figure out
that people aren't stupid.

OF COURSE SIR!

YOU are NOT stupid.

NO.

How could we just DARE to think something
like that?

 

[Malcolm McLean]

No, you see, just because you and Ian don't know how to run projects,
manage clients, extract and analyze requirements and design software does
not mean that other people don't know how to. And no need to pretend that
you two do, for both of your responses show lack of any such
understanding or capability. It's OK not to know and to be "just" a
programmer, but stop pretending about the other things, because you are
not fooling anyone. Stop fooling yourselves. And if you are just throwing
a tantrum because you WISH things were as you describe, well that's worse
than actually not knowing: won't YOU be surprised when you figure out
that people aren't stupid.

You're talking about one type of software, probably bespoke business
systems.

Games programming doesn't work like that, nor does scientific
programming. My current programming is highly exploratory, for
instance. I have datasets and I run scripts over them to see if
there's anything interesting that other people have missed. If there
is, I download more data and slightly modify the scripts, the results
suggesting new analyses. Of course I've also got to keep up with the
experimental side of things as well. Flexibility to write programs
quickly and easily, modifying the code and data in unforeseen ways, is
very valuable to me.

A huge fuss was made about formal methods, and object orientation,
held to the be solution to a huge number of programming woes. Some
people are still making the same mistakes. Meanwhile they write their
methods on word processors and operating systems not designed
according to the methodology they are advocating.

I'm saying your experience is irrelevant, but it's limited to one or
two modes of working.

 

[Frederik Van Bogaert]

I have set up a google project for the containers library.

http://code.google.com/p/ccl/

This project tries to address the problem of the lack of an easy to use
library that would complement the standard library so that not every
c programmer has to reinvent hash tables, flexible arrays, red-black
trees, and similar data structures.

I will present this project to the french standardization group as
soon as it is possible.

Please read the documentation in downloads/ccl.pdf

The source can be browsed in source/svn/trunk

jacob

It looks nice, but I do have a few comments ...

Firstly, any document that aims to set a standard should be impartial.
Rants against, say, a certain Microsoft representative who allegedly
sabotaged the C99 standardisation process do not belong there. It just
doesn't look professional.

Secondly, is there any method for serialisation in your library? I
certainly could have used one in the past
The documentation mentions Save and Load operations can be performed on
containers, but these take a FILE* as argument and so are useless if you
want to send data over the network[1], for instance, unless your OS
happens to have methods to address a block of memory through a FILE*.
It would be nice if serialisation just wrote to memory, and you
implemented Save/Load based on those serialisation/de-serialisation methods.

Thirdly, what advantage does this project have to just using C++? Do you
really think eventually systems will exist where your library is
present, but a C++ compiler isn't? Yes, I don't like the STL either, but
it does the job and, anyway, there are alternatives[2].

Frederik

[1] Well, you could always save to a file and then read it back in, but
I don't think most people will think of that as a satisfactory solution

[2] I particularly like the containers of the Qt library

 

[Ben Pfaff]

Le 10/01/11 01:05, Ben Pfaff a écrit :

It is possible to change from a single linked list
to a double linked, for instance, if you see that you are
inserting very often items at the middle of a list.

Or to drop lists altogether and use an array if you see that you are
not inserting so much and a flexible array would be much faster.

Or you decide that the bottleneck of searching through the whole array
is too much and you need a hash table.

Applications discover that some of the assumptions done at
design time are no longer valid. Hence it is important
to be able to change that.

But in many cases the change of container demands other changes
anyhow. For example, you mention switching from an array to a
hash table. An array doesn't call for a hash function or
(usually--I haven't looked at your container library) a
comparison function, but a hash table needs both. So there is
limited value in making it simple to change the container.