A container library for the C language

[jacob navia]

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

 

[Dann Corbit]

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

Here is the output of compilation:

c:\tmp\container>cl -Dinline= -I . /W4 /Ox *.c
Microsoft (R) C/C++ Optimizing Compiler Version 15.00.30729.01 for x64
Copyright (C) Microsoft Corporation. All rights reserved.
arraylist.c
bitstrings.c
bitstrings.c(786) : warning C4100: 'Args' : unreferenced formal
parameter
bitstrings.c(791) : warning C4100: 'ExtraArgs' : unreferenced formal
parameter
bitstrings.c(969) : warning C4127: conditional expression is constant
bitstrings.c(1109) : warning C4100: 'arg' : unreferenced formal
parameter
bitstrings.c(1109) : warning C4100: 'saveFn' : unreferenced formal
parameter
bitstrings.c(1118) : warning C4100: 'arg' : unreferenced formal
parameter
bitstrings.c(1118) : warning C4100: 'readFn' : unreferenced formal
parameter
bloom.c
containererror.c
containererror.c(37) : warning C4100: 'errcode' : unreferenced formal
parameter
containererror.c(37) : warning C4100: 'fnname' : unreferenced formal
parameter
deque.c
dictionary.c
dictionary.c(128) : warning C4996: 'sprintf': This function or variable
may be unsafe. Consider using sprintf_s instead. To disable deprecation,
use _CRT_SECURE_NO_WARNINGS. See online help for details. c:\Program
Files (x86)\Microsoft Visual Studio 9.0\VC\INCLUDE\stdio.h(366) : see
declaration of 'sprintf'
dictionary.c(325) : warning C4996: 'strcpy': This function or variable
may be unsafe. Consider using strcpy_s instead. To disable deprecation,
use _CRT_SECURE_NO_WARNINGS. See online help for details.
dlist.c
fgetline.c
hashtable.c
hashtable.c(64) : warning C4996: 'sprintf': This function or variable
may be unsafe. Consider using sprintf_s instead. To disable deprecation,
use _CRT_SECURE_NO_WARNINGS. See online help for details. c:\Program
Files (x86)\Microsoft Visual Studio 9.0\VC\INCLUDE\stdio.h(366) : see
declaration of 'sprintf'
heap.c
list.c
malloc_debug.c
pool.c
pool.c(414) : warning C4127: conditional expression is constant
pool.c(427) : warning C4127: conditional expression is constant
pool.c(444) : warning C4127: conditional expression is constant
pool.c(445) : warning C4127: conditional expression is constant
pooldebug.c
pooldebug.c(325) : warning C4100: 'pool' : unreferenced formal parameter
pooldebug.c(334) : warning C4100: 'file_line' : unreferenced formal
parameter
pooldebug.c(400) : warning C4100: 'file_line' : unreferenced formal
parameter
qsort_r.c
qsort_r.c(40) : warning C4005: 'min' : macro redefinition c:\Program
Files (x86)\Microsoft Visual Studio 9.0\VC\INCLUDE\stdlib.h(850) : see
previous definition of 'min'
qsort_r.c(103) : warning C4267: 'function' : conversion from 'size_t' to
'int', possible loss of data
qsort_r.c(118) : warning C4267: 'function' : conversion from 'size_t' to
'int', possible loss of data
qsort_r.c(126) : warning C4267: 'function' : conversion from 'size_t' to
'int', possible loss of data
qsort_r.c(134) : warning C4267: 'function' : conversion from 'size_t' to
'int', possible loss of data
qsort_r.c(141) : warning C4267: 'function' : conversion from 'size_t' to
'int', possible loss of data
qsort_r.c(151) : warning C4267: 'function' : conversion from 'size_t' to
'int', possible loss of data
qsort_r.c(157) : warning C4267: 'function' : conversion from 'size_t' to
'int', possible loss of data
qsort_r.c(158) : warning C4018: '<' : signed/unsigned mismatch
qsort_r.c(159) : warning C4267: 'function' : conversion from 'size_t' to
'int', possible loss of data
qsortex.c
redblacktree.c
redblacktree.c(45) : warning C4100: 'KeySize' : unreferenced formal
parameter
redblacktree.c(663) : warning C4100: 'p' : unreferenced formal parameter
redblacktree.c(666) : warning C4100: 'it' : unreferenced formal
parameter
redblacktree.c(668) : warning C4100: 'arg' : unreferenced formal
parameter
redblacktree.c(668) : warning C4100: 'Applyfn' : unreferenced formal
parameter
redblacktree.c(668) : warning C4100: 'ST' : unreferenced formal
parameter
redblacktree.c(672) : warning C4100: 't' : unreferenced formal parameter
redblacktree.c(675) : warning C4100: 't' : unreferenced formal parameter
scapegoat.c
scapegoat.c(319) : warning C4267: 'function' : conversion from 'size_t'
to 'unsigned long', possible loss of data
scapegoat.c(323) : warning C4267: 'function' : conversion from 'size_t'
to 'unsigned long', possible loss of data
scapegoat.c(447) : warning C4267: 'function' : conversion from 'size_t'
to 'int', possible loss of data
scapegoat.c(501) : warning C4100: 'data' : unreferenced formal parameter
scapegoat.c(517) : warning C4100: 'element' : unreferenced formal
parameter
searchtree.c
searchtree.c(776) : warning C4100: 'tree' : unreferenced formal
parameter
searchtree.c(781) : warning C4100: 'tree' : unreferenced formal
parameter
smallpool.c
smallpool.c(387) : warning C4127: conditional expression is constant
smallpool.c(400) : warning C4127: conditional expression is constant
smallpool.c(417) : warning C4127: conditional expression is constant
smallpool.c(418) : warning C4127: conditional expression is constant
Generating Code...
c:\tmp\container\hashtable.c(474) : warning C4706: assignment within
conditional expression
c:\tmp\container\hashtable.c(498) : warning C4706: assignment within
conditional expression
c:\tmp\container\hashtable.c(580) : warning C4706: assignment within
conditional expression
Compiling...
strcollection.c
strcollection.c(41) : warning C4996: 'sprintf': This function or
variable may be unsafe. Consider using sprintf_s instead. To disable
deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
c:\Program Files (x86)\Microsoft Visual Studio 9.0\VC\INCLUDE\stdio.h
(366) : see declaration of 'sprintf'
strcollection.c(79) : warning C4996: 'strcpy': This function or variable
may be unsafe. Consider using strcpy_s instead. To disable deprecation,
use _CRT_SECURE_NO_WARNINGS. See online help for details.
strcollection.c(603) : warning C4100: 'arg' : unreferenced formal
parameter
strcollection.c(684) : warning C4996: 'fopen': This function or variable
may be unsafe. Consider using fopen_s instead. To disable deprecation,
use _CRT_SECURE_NO_WARNINGS. See online help for details. c:\Program
Files (x86)\Microsoft Visual Studio 9.0\VC\INCLUDE\stdio.h(237) : see
declaration of 'fopen'
strcollection.c(704) : warning C4996: 'fopen': This function or variable
may be unsafe. Consider using fopen_s instead. To disable deprecation,
use _CRT_SECURE_NO_WARNINGS. See online help for details. c:\Program
Files (x86)\Microsoft Visual Studio 9.0\VC\INCLUDE\stdio.h(237) : see
declaration of 'fopen'
test.c
test.c(17) : warning C4244: '=' : conversion from 'size_t' to 'double',
possible loss of data
test.c(78) : warning C4100: 'ExtraArgs' : unreferenced formal parameter
test.c(308) : warning C4100: 'arg' : unreferenced formal parameter
test.c(336) : warning C4244: '=' : conversion from 'size_t' to 'double',
possible loss of data
test.c(345) : warning C4244: '=' : conversion from 'size_t' to 'double',
possible loss of data
Generating Code...
Microsoft (R) Incremental Linker Version 9.00.30729.01
Copyright (C) Microsoft Corporation. All rights reserved.
/out:arraylist.exe
arraylist.obj
bitstrings.obj
bloom.obj
containererror.obj
deque.obj
dictionary.obj
dlist.obj
fgetline.obj
hashtable.obj
heap.obj
list.obj
malloc_debug.obj
pool.obj
pooldebug.obj
qsort_r.obj
qsortex.obj
redblacktree.obj
scapegoat.obj
searchtree.obj
smallpool.obj
strcollection.obj
test.obj

I suggest that the unused parameters and type conversions should get
examination. This is especially true in a case like size_t to int
truncation in qsort_r().

An int seems pretty large but I often deal with sets larger than 2
billion items (no, really) and so I would suggest that anything that
carries a dimension should be retained as a size_t throughout.

 

[Keith Thompson]

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

I eliminated some spurious warnings and error messages by modifying
the makefile, adding "-std=c99" to CFLAGS and "-lm" to the linking
command.

I still got two warnings that seem to be valid:

test.c: In function ‘testBinarySearchTree’:
test.c:342: warning: format ‘%lu’ expects type ‘long unsigned int’, but
argument 2 has type ‘size_t’

searchtree.c:601: warning: ‘hide’ defined but not used

(I'm guessing you didn't see the first warning because you compiled
on a system where size_t is unsigned long; on mine it's unsigned
int.)

 

[jacob navia]

Thanks for your input.

As you may know, Microsoft deprecated most of the C language.
You should
#define _CRT_SECURE_NO_WARNINGS
and most warnings will disppear.

The problem in qsort_r is solved, but apparently I posted a slightly
older version.

jacob

P.S. Please look at the specs too, they are actually the most important
part of this contribution.

 

[Dann Corbit]

Thanks for your input.

As you may know, Microsoft deprecated most of the C language.
You should
#define _CRT_SECURE_NO_WARNINGS
and most warnings will disppear.

The problem in qsort_r is solved, but apparently I posted a slightly
older version.

jacob

P.S. Please look at the specs too, they are actually the most important
part of this contribution.

I will do so. I do think that this is a very good idea.

 

[Ian Collins]

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!

The DOS line endings are a bit of a pain, but easily cleaned up.

The function declared as "int getline(char **,FILE *);" is missing.
There is an "int getline(char **LinePointer,int *n, FILE *stream)"

 

[Keith Thompson]

The DOS line endings are a bit of a pain, but easily cleaned up.

Note that some of the source files have DOS-style line endings and some
have Unix-style line endings. You probably want to be consistent.

If you use "unzip -a", it will automatically convert any text files to
native format, and it recognizes that stl-doc.odt and stl-doc.doc are
binary.

 

[jacob navia]

Keith Thompson a écrit :

Note that some of the source files have DOS-style line endings and some
have Unix-style line endings. You probably want to be consistent.

I have developed this on a Macintosh with OS X (main dvelopment) and
tested it under windows 7 with Visual Studio 10. Some files have
dos line endings, where I edited in the windows machine
and other are unix when I edited in the mac.

If you use "unzip -a", it will automatically convert any text files to
native format, and it recognizes that stl-doc.odt and stl-doc.doc are
binary.

I will add that to the download page.

 

[jacob navia]

Dann Corbit a écrit :

I will do so. I do think that this is a very good idea.

Have you seen how SMALL the executable is?

Visual studio 2010 arrives at making it around 60K... with full
optimizations enabled of course.

 

[Keith Thompson]

Keith Thompson a écrit :

I have developed this on a Macintosh with OS X (main dvelopment) and
tested it under windows 7 with Visual Studio 10. Some files have
dos line endings, where I edited in the windows machine
and other are unix when I edited in the mac.

Ok, I understand why the line endings are inconsistent.

I still suggest that it would be better to make them consistent,
one way or the other, in the next release. (See dos2unix and/or
unix2dos, aka fromdos and/or todos -- but beware that, unlike most
Unix utilities, they overwrite their input files by default.)

[...]

 

[Ian Collins]

Keith Thompson a écrit :

I have developed this on a Macintosh with OS X (main dvelopment) and
tested it under windows 7 with Visual Studio 10. Some files have
dos line endings, where I edited in the windows machine
and other are unix when I edited in the mac.

All the windows editors I've used have an option to save with Unix line
endings and windows compilers are happy with either.

I will add that to the download page.

What about the missing function?

 

[Ed]

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!

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.

 

[John Whorfin]

Phong Vo's CDT may be of interest...

http://www2.research.att.com/~gsf/download/ref/cdt/cdt.html

 

[jacob navia]

Ed a écrit :
Here we have the typical answer of a c++ zealot.

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!

They need no arguments of course. Just the assertions of "facts"
like "kludgy" or "brought down to C". It would be tempting to answer in
a like fashion but I will better refrain.

Containers,
iterators, algorithms, a template system: it's ALREADY DONE IN C++.

YES.

And in C#, in Java, and in many other languages. That's why it is a good
idea to do it 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.

I do not consider C as a legacy language where all development has
ceased. I have developed a compiler system for C, and I think that C is
a simple language that is smaller and easier to master than the bloated
counterpart.

Face it, it's not that "it can't be done", it's that it is not practical.

Who says so?

Think about it, eventually the intricacies of your proposed library and
the complex machinery will be more complex than the entire standard C!

The library code when you use all implemented containers fits in 64K.
I think the final version could take up to 128K.

C can have container libraries, but C++-like ones, I don't think so.

I agree. People that use the STL and C++ should go on using that.
People that use C can use the CCL (C Containers library).

Just my opinion, I'm not saying "stop that!".

Yes, This is exactly that: your opinion. You haven't advanced a single
arguùment to validate your opinion.

 

[jacob navia]

John Whorfin a écrit :

Phong Vo's CDT may be of interest...

http://www2.research.att.com/~gsf/download/ref/cdt/cdt.html

Thanks, that is very interesting

 

[tea leaf]

jacob navia:

I do not consider C as a legacy language where all development has
ceased. I have developed a compiler system for C, and I think that C is
a simple language that is smaller and easier to master than the bloated
counterpart.

More accurately, you have bought a compiler system that someone else
developed, made a few cosmetic changes, added a horrible GUI, and now you
constantly try to hawk the result in this newsgroup.

The library code when you use all implemented containers fits in 64K. I
think the final version could take up to 128K.

Your library is small because it doesn't do very much. Knocking up a
generic linked list and hashtable is hardly going to transform the world.
If you want high-powered libraries, use a modern object framework with C
bindings - GLib for example.

 

[jacob navia]

tea leaf a écrit :

jacob navia:

More accurately, you have bought a compiler system that someone else
developed, made a few cosmetic changes, added a horrible GUI, and now you
constantly try to hawk the result in this newsgroup.

I rewrote the front end, the back end completely, added an assembler, a
linker and a debugger.

My horrible GUI as you say has a front end for the debugger, a resource
editor, go to definition,
syntax checking etc.

Your library is small because it doesn't do very much. Knocking up a
generic linked list and hashtable is hardly going to transform the world.

The containers implemented so far in the sample implementation are:

* Lists (single and double linked)
* String collection
* Array list (flexible arrays)
* Dictionary (Hash table)
* Hash table (resizable, more sophisticated than dictionary)
* Bitstrings
* AVL-Tree
* Red/Black trees
* Scapegoat trees
* Queue
* Deque
* Bloom filter

The specifications are still incomplete for some containers like AVL
trees, Red-black trees and scapegoat trees.

Auxiliary interfaces are provided to:

* heaps
* memory pools
* debugging malloc
* error handling

All in 64K. But it is better to spread misinformation. You do not even
read the home page of that project but you know already that it doesn't
"do much".

If you want high-powered libraries, use a modern object framework with C
bindings - GLib for example.

Sure, and any time I allocate something my program will shutdown if
there is no memory. Great.

 

[Keith Thompson]

tea leaf a écrit :

I rewrote the front end, the back end completely, added an assembler, a
linker and a debugger.

[snip]

jacob, my advice is that you don't waste your time responding to
this "tea leaf" troll. It's obvious he has some personal vendetta
against you, and nobody takes him seriously. Of course you can
reply if you like, but I suggest that it's not necessary.

 

[Gene]

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

Thanks Jacob. This is very interesting and nicely done. I wonder if
you have done any benchmarking to see what the cost is of invoking all
the API entries using function pointers in the interface objects.

 

[Pierre Asselin]

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

I can't read the .doc or the .odt but I had a quick look at
containers.h . Suppose I need a simple linked list, nothing fancy.
If I use your library, I reference your "iList" extern variable
and the linker pulls in all the list methods in the vtable, even
though I only use a couple. I pay (in code size) for what I don't
use.

Maybe that's not a big cost, but your url says:
This page describes the work presented to the French C
standardization committee of the AFNOR to be included in
the next C standard.

If your interface becomes part of the standard library IMHO the
added cost is a problem. Maybe you can convince the committee that
the cost is acceptable in a hosted environment, but you will have
to argue the case. Or describe a low cost implementation, or modify
the interface.