A container library for the C language

[Ben Bacarisse]

Ian Collins a écrit :

That function is defined in fgetline.c line 73.

Some people using your makefile will think that it is missing because
you don't link fgetline.o with the test program (and in that sense it is
missing). For others, the gcc options used in the makefile will simply
stop the compilation when your getline prototype conflicts with the GNU
one. You'll get more people trying your code out if the makefile just
worked.

<snip>

 

[jacob navia]

Ben Bacarisse a écrit :

Some people using your makefile will think that it is missing because
you don't link fgetline.o with the test program (and in that sense it is
missing). For others, the gcc options used in the makefile will simply
stop the compilation when your getline prototype conflicts with the GNU
one. You'll get more people trying your code out if the makefile just
worked.

<snip>

OK, fixed that: changed getline to GetLine, and added fgetline.o to the
objects.

 

[jacob navia]

Sebastian a écrit :

There are header-only libraries containing templates and inline
functions only. So, for example, if you have a header like
linkedlist.hpp and never use the class template's member function
mergesort(), the code just won't be generated. In terms of header
dependencies/compilation templates are kind of a horror but they also
have their advantages. The compiler only translating the functions
that are actually used is one of these advantages.

I *could* have done a similar thing with macros, but it would
have been very cumbersome and would clutter the interface.

I repeat. The whole list module (single linked) is about 4900 bytes.
Since you have the source you can trim down the functions you do not use,
but I think an overhead of 5K is not that significant.

Yes, C++ *can* be efficient but in practice I wouild be surprised
if a program using the STL would be as efficient (space-wise) as C.

Just to give you an example. This program:
// Standard Template Library example

#include <iostream>
#include <list>
using namespace std;

// Simple example uses type int

int main(void)
{
list<int> L;
L.push_back(0); // Insert a new element at the end
L.push_front(0); // Insert a new element at the beginning
L.insert(++L.begin(),2); // Insert "2" before position of first argument
// (Place before second argument)
L.push_back(5);
L.push_back(6);

list<int>::iterator i;

for(i=L.begin(); i != L.end(); ++i) cout << *i << " ";
cout << endl;
return 0;
}

Executable size: 153 008 bytes (windows vista, MSVC 2008 -Ox)

A similar program using the container library takes 37 920 bytes

BTW: Have you heard about the abstraction penalty tests? The idea of
these tests is to check the quality of a C++ compiler / standard
library combination in terms of performance (speed, memory overhead,
etc). One typically expects a quality implementation of a "generic
container" to be about as efficient as its "handrolled" counterpart.
Resolving things at compile-time obviously helps here due to inlining
possibilities.

Inlining helps to make code slower in many cases due to code bloat.
We have this problem at work with a huge C++ monster 25MB code size
(with full optimizations). Inline is horrible since the code is so bloated
that the code cache simply doesn't work.


Using function pointers may hurt performance.

I do not think that the difference is measurable in modern
machines.

From what
I can tell, C++ combined with a quality implementation manages to get
both: low abstraction penalties and nice encapsulation. Do you expect
to be able to compete with this?

Look. I am not a language zealot. I think that people that like C++ should
go on using that. I expect (and have measured) very similar performance
for my library and for C++ STL. I expect that optimized versions will
appear and then the performance will go even higher.

My principal aim however is NOT to "replace the STL" but to provide a container
library for C programmers.

Thanks for your contribution.

 

[Uno]

I have been talking about this since quite a long time. It is (maybe)
time to offer the first release.

The URL is:
http://www.cs.virginia.edu/~lcc-win32/container.html

There you can download a zip file containing
(1) The specifications of the library
(2) The source code of the sample implementation
(3) a makefile for Unix systems

Enjoy!

Jacob,

What do you mean by "container library." (I'm trying to implement
libraries just to get the hang of it.)

Is what you have at that link only gonna work on lcc, or can I do it
with gcc as well?

 

[Ben Bacarisse]

OK, fixed that: changed getline to GetLine, and added fgetline.o to the
objects.

.... now getdelim conflicts when compiling fgetline.c. Applying the same
fix (capitalising the name) and adding -lm to command line does then
allow the compile to complete (with warnings about C99 usages).

Execution gives a segmentation fault due, I suspect, to not testing an
error return in the test program (there is no file called ../../test.c
on my system). Fixing that makes the test program abort:

*****

ABORT
File test.c Line 287
**********

This looks to be a more serious bug but I have not investigated any
further. You may want to team up with a Unix/Linux person to shake down
this version rather than trying to fix it here issue by issue.
Presumably your test program shows no problems on a Windows machine so
the bug may be due to something Unix/Linux specific.

 

[jacob navia]

Uno a écrit :

Jacob,

What do you mean by "container library." (I'm trying to implement
libraries just to get the hang of it.)

Is what you have at that link only gonna work on lcc, or can I do it
with gcc as well?

I have compiled it with gcc and lcc under windows and Mac OS X.
I have done several compilations under linux too.

I mean with "container library" a library that allows you to use
hash tables, linked lists, resizable arrays, and other data structures
that are used to store data.

jacob

 

[Keith Thompson]

I have compiled it with gcc and lcc under windows and Mac OS X.
I have done several compilations under linux too.

[...]

By "lcc" do you mean lcc-win, or the original lcc? Just curious.

 

[Ed]

everyone?

Nice try, but no, not hardly.

with whats?

Programming Languages as an end instead of a means.

std::vector and std::string seem eminantly usable even in small
programs.

It's probably the worst offender in the package. It is THE main "lock my
code into C++" element of C++ or pretty darn close.

What's wrong with the STL? I always thought it was one of C+
+s selling points!

It can be, but not hardly for everyone nor all the time. Much of C++
focuses on large-scale development and you don't get in one area without
sacrificing in another (you can build an engine for low RPM torque or
high RPM horsepower, but it's a tradeoff). Parameterization is not a
panacea.

not conforming to the initiator's expectations. To be widely adopted
and maybe even standardised.

Maybe meaning well, but not being up to the task. Wishfull thinking.
Building the wrong thing. The aforementioned are all (but not the only)
precursors to failed projects and they can be recognized but not by the
uninitiated.

[...] The best that I think any aspiring C container library would
be is some kind of Boost like use. At the moment, I feel that
someone trying to get a C container library standardized borders on
delusions of grandeur. 30+ years of C and people much smarter than
me and still no standard C container library leaves me with no
confidence that it can be done.

I agree. But I think the problems are historical and political rather
than technical.

I think, FWIW, that the introduction of C++ effectively curbed any
further evolution of C in the directions that C++ went. Surely many
simply moved to C++ and left mostly the "die-hard" C people in C land and
those with very niche requirements like embedded where C++ were decidely
inappropriate (that last part probably isn't true anymore since people
know how to avoid non-deterministic features etc).

I can well imagine C++ going a different route from
the STL and ending up up with a balkanised library.

Templates are good, but they're not the only way of doing generics nor
are generics all that one needs or wants. You don't always need a Swiss
Army knife (bad analogy probably).

 

[Ed]

The part of the C++ standard library formally known as the STL is
sufficiently general to appeal to most C++ programmers and projects.

It is the "epitome of generality" and that is not always required. Maybe
not even usually required. You have to admit that people gravitate toward
institutionalized stuff and that makes it hard to introduce anything new
because of the large and powerful incumbant.

That was the key to its inclusion in the standard library and its
enduring success.

It's not a panacea nor are templates.

The battle anyone faces when proposing library additions is
demonstrating not only the utility of their proposed solution, but its
acceptance in general use.

I would not say "in general use" but rather "appropriateness for
large-scale development". As "general" necessarily includes large-scale
projects, that disproportionally constrains the possibilities.

The STL had been in use for many years
before it was incorporated in the C++ standard and the library
extensions in the next C++ standard have also been available and well
used for many years.

I understand one of the guidelines of the C committee is to
standardise existing practice (which I guess could be interpreted as
"maintenance mode"), so any new library extensions will probably have
to wait for C next +1, assuming they last that long in the wild.

A point I tried to make in another post.

 

[jacob navia]

Ben Bacarisse a écrit :

... now getdelim conflicts when compiling fgetline.c. Applying the same
fix (capitalising the name) and adding -lm to command line does then
allow the compile to complete (with warnings about C99 usages).

Execution gives a segmentation fault due, I suspect, to not testing an
error return in the test program (there is no file called ../../test.c
on my system). Fixing that makes the test program abort:

*****

ABORT
File test.c Line 287
**********

This looks to be a more serious bug but I have not investigated any
further. You may want to team up with a Unix/Linux person to shake down
this version rather than trying to fix it here issue by issue.
Presumably your test program shows no problems on a Windows machine so
the bug may be due to something Unix/Linux specific.

It wasn't Unix specific, it was just a bug.

Thanks for your help Ben.

jacob

 

[Ed]

On 27 June, 09:46, Francis Glassborow
Ed wrote:
jacob navia wrote:

I have been talking about this [a container library for C]
since quite a long time.

A STL for C? Anyone going that far will undoubtedly choose C++,
and not some kludgy thing patterned after STL/C++brought down to
C! Containers, iterators, algorithms, a template system: it's
ALREADY DONE IN C++. No manpower required to reimplement that in
a legacy language that does not have the mechanisms that allow
elegant implementation of such stuff. Face it, it's not that "it
can't be done", it's that it is not practical. Think about it,
eventually the intricacies of your proposed library and the
complex machinery will be more complex than the entire standard
C! C can have container libraries, but C++-like ones, I don't
think so. Just my opinion, I'm not saying "stop that!". It is
hard seeing you wasting your time though. It's not a waste if you
are having fun, and you're obviously learning things, so in that
respect, go for it, but do be aware of the landscape. Please say
you know C++ and have programmed in it, especially the
containers/iterators/algorithms.

OK, I get it. You hate the idea. Many things have already been done
in C++. OTOH there are many places where C++ cannot be used for a
variety of reasons. Some of these places have uses for containers
and writing a container from scratch is a non-trivial task.

By all means critique someone's code but the above is not that, it
is just a very negative criticism. If 'it has been done before
elswhere' were a reason for not doing something there is not much
that most people could do.

I'm not sure I agree his criticism is entirely negative.

It wasn't AT ALL NEGATIVE.

?

It wasn't. If I'm "so honest it hurts" (blunt), so be it.

ITYM "misinformed", he'll *become* disillusioned if the project goes
as you predict.

To me he seems to be "wishfully thinging" and conveniently ignoring
anything that "bursts his bubble". He appears be trying to suck people
into "getting onboard" without anything but a cry, "all aboard!". He
wants me to look at his code in detail when I can see from a mile away
that I don't need to examine it any further as my assessment of it as it
is today is complete for my purposes. Next assessment in 3 to 5 years.
YMMV.

he's implemented a C compiler and a suite of libraries to go with it

I don't like his libraries either. I find them neither adequate nor
fundamentally correct. (Not a negative, just the truth). Assessment
completed a few years ago. YMMV.

that there were existing container libraries out there, that something
with ->VTable in it would be a hard sell and that Jacob was going to
do it anyway

It's a good learning experience. If nothing else, it helps to establish
what one really wants from a library. Sounds like a personal growth
project. Of course, submission to ISO should come after years beyond that
when something is evolved, proven and established.

C++? I'm guessing he's had some experience of it. It's a big bugger.

He seems to resent it and any mention of it. Mention C++ and you're
likely to be called a "zealot".

his compiler supports operator over loading...

HIS compiler can do whatever it wants. HE presents his material as
direction for THE C Standard, which is rather bizarre given the
immaturity of his "proposals", don't you think? I would "give him more
slack" if he showed objectivity and capability, but I see neither. Not to
be discouraging about personal projects though, it's all good. Trying to
starting a "rah rah!" with blindsiders on is not though. Study the
"problem" well, decide if there really is a problem, document well the
current landscape and the history, clearly document the goals and
potentials and risks, ... Note that at every stage there is a decision
diamond that may lead to the "stop" oval. All of those diamonds need to
be thoroughly and objectively addressed and documented, and it is able to
be analyzed that way BEFORE setting out to rough seas in a rowboat.

this irritates Jacob, he doesn't believe C has to be frozen like this

I get that impression also. I don't understand how that can be so. Must
be romantic about it or something similar. It may be selfish too: how
many C users don't want ANY more changes and where are the numbers? There
is so much more work to do with something like this just because it is C,
that most all would realize and say: "It's just not worth it" (I am
saying that too, but I say it about C++, let alone C!) and what you gain
for one segment of the group, you lose in another or lose the other
completely maybe. After all this, I think that C is not in "maintenance"
mode, but rather PRESERVATION mode, a Smithsonian exhibit, and
appropriately.

 

[Ian Collins]

It is the "epitome of generality" and that is not always required. Maybe
not even usually required. You have to admit that people gravitate toward
institutionalized stuff and that makes it hard to introduce anything new
because of the large and powerful incumbant.

Ah but it hasn't. Having a standard container library has acted as a
catalyst for new development, not a hindrance. This is clear when one
compares the developments (or lack of) in the C and C++ standard libraries.

It's not a panacea nor are templates.

You are missing (or avoiding?) the point. In the context of this
thread, the STL was a container and algorithm library that was in
widespread used when C++ was standardised. Unfortunately C has never
had this.

I would not say "in general use" but rather "appropriateness for
large-scale development". As "general" necessarily includes large-scale
projects, that disproportionally constrains the possibilities.

Any language standard library has to be appropriate for large scale
development.

 

[Ian Collins]

A "list" is an ordered series of data items.

No in C++ terms, list is unordered.

The generic STL way of taking a list to to take an iterator to the
start and end of the controlled sequence. The problem is that this
mechanism is too difficult, counter-intuitive, or whatever for
everyone to use consistently.

Everyone maybe, but not programmers.

TRy declaring some simple data structures with the STL, in a real but
simple program. Then write the same program in C. You'll soon see the
problem with the STL syntax.

The benefits of a standard library more than outweigh any unpleasant
declaration syntax. Just like with messy C declarations, typedef is
your friend.

 

[jacob navia]

Ed a écrit :

To me he seems to be "wishfully thinging" and conveniently ignoring
anything that "bursts his bubble".

Strange. *I* answer your messages but *you* never answer the arguments
I advance:

(1) Read the specifications that I propose
(2) Then argue against them

To me you seem to be "wishfully thinging" and conveniently ignoring
anything that "bursts your bubble".

Proof: You never answer anything I tell you, you do not read the
proposal, and in general you avoid any substantive discussion.

He appears be trying to suck people
into "getting onboard" without anything but a cry, "all aboard!". He
wants me to look at his code in detail when I can see from a mile away
that I don't need to examine it any further as my assessment of it as it
is today is complete for my purposes. Next assessment in 3 to 5 years.
YMMV.

Essentially you say that your prejudices against something you
haven't even read tell you that I am wrong.

Fine. Then why keep this discussion?

Just go away.

I don't like his libraries either. I find them neither adequate nor
fundamentally correct. (Not a negative, just the truth). Assessment
completed a few years ago. YMMV.

Well, I don't like you too... Sniff Sniff

We are getting DIVORCED pal!

He seems to resent it and any mention of it. Mention C++ and you're
likely to be called a "zealot".

Obviously not. When you say that C is a legacy language already dead,
THEN I call you a zealot...

I have nothing against people using C++. I am writing A C library for
C programmers!

And that is what bothers you apparently. That I address C programmers
and try to develop in C.

I get that impression also. I don't understand how that can be so. Must
be romantic about it or something similar. It may be selfish too: how
many C users don't want ANY more changes and where are the numbers? There
is so much more work to do with something like this just because it is C,
that most all would realize and say: "It's just not worth it" (I am
saying that too, but I say it about C++, let alone C!) and what you gain
for one segment of the group, you lose in another or lose the other
completely maybe. After all this, I think that C is not in "maintenance"
mode, but rather PRESERVATION mode, a Smithsonian exhibit, and
appropriately.

Yes Sir!

C is dead, and nobody should develop in C. Mr "Ed" said so,
and we are going to follow our great commander!

 

[Ed]

Ed a écrit :

Who wants to duplicate that journey?

You apparently. If C++ is "bad" when it has the underpinnings to do
"containers", why is something without those going to be better?
(Rhetorical, don't answer me, put it in a comprehensive document after
much research, study and analysis).

C++ got completely lost in unmastered complexity traps. The complexity
has grown to such proportions that the creator of the language is
unable to add an apparently simple feature after YEARS of efforts.

"Concepts" anyone?

Concepts were an attempt to fill a design gap in the language. You want
to do templates with the same gap. See, you could have made something
better, but you're doing the exact same thing the exact same wrong way.
You are on the path that C++ was on.

I do not propose any language changes with this library because
PRECISELY what I want is to prove that much of the complexity
is unnecessary in software development.

That can't be proven, because there is nothing to prove. It is obvious
that one can work with as minimal a set of constructs as one wishes. The
question is who wants to. It's personal or team choice. Again, there is
nothing to prove and stating like there is something to prove sounds like
something a snake oil salesman would say.

The syntax is simple, the speed is roughly the same as the STL,
the size is approximately 1/10th or 1/50th of the STL implementations.

STL is rather complete and evolved while you are just starting out
considering the possibilities. There are many, many considerations, not
the least of which is "one size fits all" (IMO, one failing of STL) and
you are doing the same thing: proposing a "one size fits all" library
(for a language in preservation mode!).

True, there are no templates but a simple program is provided that
replaces templates with no effort.

Templates as glorified macros (or an ancillary program to generate from
them) are still basically the same thing.

"half way?" What is "half way?".

No way. I stayed within standard C.

Kludgy then.

GREAT!

Then step aside, do not embark, and keep your prejudices out of this
discussion. You offer no arguments anyway, so you are just
contributing noise.

Stop posting to me and put me on ignore then. I'll check back in with ya
in 5-10 years.

???

What did I bypass?

It is not evident that the thousands of list libraries, hash table
libraries written in C could benefit by having a standrad way of
making them inter-operable so that you can replace libraries without
pain?

Just because you say THAT is the landscape does not make it so. Take a
break from playing with source code and do the up front work that is
required trying to be thorough and diligent in your research and
objective in your conclusions. 3rd party examination will be required.

It may even be dishonest.

What is dishonest is to criticize a proposal without reading
what it proposes.

[snip crap]

A detailed read was not worth my time. I was able to assess it with at
"once over look". Your approach is defficient IMO.

 

[jacob navia]

Ed a écrit :

Concepts were an attempt to fill a design gap in the language.

Yes. They should have allowed to put characteristics onto
types and define classes of types
(comparable, serializable, etc). That way a template would
have been able to restrain its arguments to classes of types.

You want
to do templates with the same gap.

Excuse me but that doesn't compute...

What does it mean that I want to do templates?
With my tiny container lib proposal?

See, you could have made something
better, but you're doing the exact same thing the exact same wrong way.
You are on the path that C++ was on.

Maybe, I have nothing against C++ actually. It is a big language
that has some good ideas. It went too far away into the
complexity trip and crashed, but that doesn't mean that there aren't
good ideas in that language or that the many fellow programmers that
use it (including myself at work) are stupids.

That can't be proven, because there is nothing to prove. It is obvious
that one can work with as minimal a set of constructs as one wishes.

OK we agree then.

The

question is who wants to.

All people that think less complexity is more manageable than
more complexity. Engineering is a trade off between contradicting
requirements, and in many situations of software engineering
less complexity is better and gives you more power.

I still program in ASSEMBLER (maybe because I generate it in the
compiler system) but also because I like the incredible power
it gives you.

But not everyone likes assembly... and I use other tools and languages.

It's personal or team choice.

Exactly. My proposal adds to those choices, allowing people to program
in C without having to reinvent a list at each application.


[snip]

STL is rather complete and evolved while you are just starting out
considering the possibilities. There are many, many considerations, not
the least of which is "one size fits all" (IMO, one failing of STL) and
you are doing the same thing: proposing a "one size fits all" library
(for a language in preservation mode!).

Since you haven't read the proposal you are telling nonsense.

I propose a standard INTERFACE, not code. There will be MANY implementations
of the same interface adapted for DIFFERENT requirements. What is nice in this,
is that USER code doesn't need to be changed when you pass from a list designed
for 100 items to another that is designed for 1000000.

Templates as glorified macros (or an ancillary program to generate from
them) are still basically the same thing.

Yes, that is why the small program is useful.

Kludgy then.

Yes, C is kludgy, like assembler and other low level stuff.
But machines are kludgy and do not understand ANYTHING ELSE
but assembler.

Software is the art of illusion. You "double click" in an icon and
you set things in movement, "windows" open, etc.

Computer "languages" give you the illusion that the machinbe understands
english. FORTRAN was a formula translator. When in fact...

it wasn't a translator since it didn't understand anything of what was going on.

A compiler is a mechanical process, and the C++ compiler can give you
MORE illusions about what the machine is doing than a simpler and
kludgier C compiler. Not to speak about the assembler

Illusions are practical, as abstractions are. But some pople LIKE
tearing those illusions AWAY and programming the way the machines
ARE, the bare bones circuit.

But this is a matter of taste, of elegance, to use a term you
have often misused...

Stop posting to me and put me on ignore then. I'll check back in with ya
in 5-10 years.

Why should I do that?

So that you can go on trying to destroy my work?

No way man.

A detailed read was not worth my time.

Sure, how an important guy you are. Your time is SO VALUABLE.

I was able to assess it with at
"once over look". Your approach is defficient IMO.

If you would even had that "once over look" you would
put here an argument, a concrete example, something.

You just state over and over again your opinion:

"defficient approach"

Just that suffices, you think.

Well your approach is defficient IMO.

jacob

 

[Ed]

Ah but it hasn't.

It has. That building more upon the template system has happened doesn't
mean that alternatives have not been suppressed.

Having a standard container library has acted as a
catalyst for new development, not a hindrance. This is clear when one
compares the developments (or lack of) in the C and C++ standard
libraries.

You are missing (or avoiding?) the point. In the context of this
thread, the STL was a container and algorithm library that was in
widespread used when C++ was standardised. Unfortunately C has never
had this.

And just surely partly and maybe completely BECAUSE of C++. It took the
wind out of C's sails and C programmers jumped ship. Putting a "new and
improved!" sticker (aka, "Standard") does not automagically make it good
nor appealing (perhaps to sheeple/follower types). Revisiting this and
conjecturing or even playing with code may be fun, but presenting it with
no more justification that "I think this should be done" or "just because
it will work" or <other lame justification> is irresponsible at best. At
this stage of C's lifetime (hehe, on life support! Pull the plug, let it
stay in a coma or make the brain dead thing move by installing robotics
in it... which is most appropriate... decisions, decisions.) it should be
easy to poll every single user of C that is left, so it's not necessarily
a huge amount of work to go about it in an organized and well-thought out
manner.

Any language standard library has to be appropriate for large scale
development.

It does not. But let's say you are corect: then it necessarily constrains
the solution space for that which is not large-scale development.

 

[Ian Collins]

On 07/ 1/10 05:36 AM, jacob navia wrote:s C.

Just to give you an example. This program:
// Standard Template Library example

#include <iostream>
#include <list>
using namespace std;

// Simple example uses type int

int main(void)
{
list<int> L;
L.push_back(0); // Insert a new element at the end
L.push_front(0); // Insert a new element at the beginning
L.insert(++L.begin(),2); // Insert "2" before position of first argument
// (Place before second argument)
L.push_back(5);
L.push_back(6);

list<int>::iterator i;

for(i=L.begin(); i != L.end(); ++i) cout << *i << " ";
cout << endl;
return 0;
}

Executable size: 153 008 bytes (windows vista, MSVC 2008 -Ox)

A similar program using the container library takes 37 920 bytes

As an illustrative example, what is the program using your the container
library?

 

[Richard Kettlewell]

Yes, C++ *can* be efficient but in practice I wouild be surprised
if a program using the STL would be as efficient (space-wise) as C.

Just to give you an example. This program:
// Standard Template Library example

#include <iostream>
#include <list>
using namespace std;

// Simple example uses type int

int main(void)
{
list<int> L;
L.push_back(0); // Insert a new element at the end
L.push_front(0); // Insert a new element at the beginning
L.insert(++L.begin(),2); // Insert "2" before position of first argument
// (Place before second argument)
L.push_back(5);
L.push_back(6);

list<int>::iterator i;

for(i=L.begin(); i != L.end(); ++i) cout << *i << " ";
cout << endl;
return 0;
}

Executable size: 153 008 bytes (windows vista, MSVC 2008 -Ox)

10-12k on a couple of Unix platforms I tried.

 

[jacob navia]

As an illustrative example, what is the program using your the container
library?

#include "containers.h"
int main(void)
{
List *l = iList.Create(sizeof(int));
int i=5;
iList.Add(l,&i);
}

Note that ALL list functions are included if you just use one of them, so
if I add a loop or Insert, whatever, the result will change by a few bytes
only.