Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.std.c > #1391 > unrolled thread

The C Containers Library

Back to article view | Back to comp.std.c

Contents

  The C Containers Library jacob navia <jacob@spamsink.net> - 2012-07-08 21:53 +0200
    Re: The C Containers Library agottem@gmail.com - 2012-07-15 13:13 -0700
      Re: The C Containers Library jacob navia <jacob@spamsink.net> - 2012-07-15 23:10 +0200
        Re: The C Containers Library jacob navia <jacob@spamsink.net> - 2012-07-15 23:12 +0200
        Re: The C Containers Library agottem@gmail.com - 2012-07-15 16:15 -0700
          Re: The C Containers Library jacob navia <jacob@spamsink.net> - 2012-07-16 10:22 +0200

#1391 — The C Containers Library

To:
John Benito
Convener
	  ISO/IEC JTC1/SC22/WG14
           110 Shady Brook Court
           Santa Cruz, CA 95065-9728
           USA

From:

Jacob Navia
41 rue Maurice Ravel
93430 Villetaneuse
France

                                Villetaneuse, July 8th 2012

Dear Sir,

I would like to present the document:

"The C Containers Library"

to the committee for consideration for standardization.

This document has been discussed in the French C++ standardization
group of the AFNOR since there isn't a group for the C language
exclusively any more. C and C++ share the same group.

This document is available at the following address:

http://ccl.googlecode.com/files/ccl.pdf

I have setup a google project with the source code of the sample
implementation as described in the above document. Its address is:

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

I have been working in this project approximately for three years and
the document is still far from perfect, but I consider that it now
gives a clear idea of the scope of this undertaking and about how can
it be implemented.

I presented the very first release of this project on June 24th 2010
to the comp.std.c and comp.lang.c discussions groups. I had started to
design and implement the library approximately a year before.

In the document you will find:

o An introduction that describes the layout, the motivations, and an
   overview of what parts of the document are to be considered normative
   specifications.
o Two introductory chapters explaining things informally.
o Two normative chapters (Auxiliary interfaces and the Containers)
o A description of the sample implementation with some commented code
   excerpts.
o Applications and examples
o The "templated" form of the containers explained.

I have tried to keep the language of the specifications clear and
concise, but I have avoided trying to mimic "standardese" since I
believe that the explanations should be understood by all programmers
using the library without any artificial restrictions. As a model, I
used the language used in the "RFC"s of the interenet, specifications
that proved quite useful but are in plain language, understood by
everyone.

My goal in this first approach is to start a technical report (TR) that
could be further discussed within the community.

I thank you in advance for your attention. I remain available at any
time for any question you may have concerning this project.

Yours sincerely

Jacob Navia
Programmer

[toc] | [next] | [standalone]

#1395

On Sunday, July 8, 2012 2:53:07 PM UTC-5, jacob navia wrote:
> To:
> John Benito
> Convener
> 	  ISO/IEC JTC1/SC22/WG14
>            110 Shady Brook Court
>            Santa Cruz, CA 95065-9728
>            USA
> 
> From:
> 
> Jacob Navia
> 41 rue Maurice Ravel
> 93430 Villetaneuse
> France
> 
>                                 Villetaneuse, July 8th 2012
> 
> Dear Sir,
> 
> I would like to present the document:
> 
> "The C Containers Library"
> 
> to the committee for consideration for standardization.
> 
> This document has been discussed in the French C++ standardization
> group of the AFNOR since there isn't a group for the C language
> exclusively any more. C and C++ share the same group.
> 
> This document is available at the following address:
> 
> http://ccl.googlecode.com/files/ccl.pdf
> 
> I have setup a google project with the source code of the sample
> implementation as described in the above document. Its address is:
> 
> http://code.google.com/p/ccl/
> 
> I have been working in this project approximately for three years and
> the document is still far from perfect, but I consider that it now
> gives a clear idea of the scope of this undertaking and about how can
> it be implemented.
> 
> I presented the very first release of this project on June 24th 2010
> to the comp.std.c and comp.lang.c discussions groups. I had started to
> design and implement the library approximately a year before.
> 
> In the document you will find:
> 
> o An introduction that describes the layout, the motivations, and an
>    overview of what parts of the document are to be considered normative
>    specifications.
> o Two introductory chapters explaining things informally.
> o Two normative chapters (Auxiliary interfaces and the Containers)
> o A description of the sample implementation with some commented code
>    excerpts.
> o Applications and examples
> o The "templated" form of the containers explained.
> 
> I have tried to keep the language of the specifications clear and
> concise, but I have avoided trying to mimic "standardese" since I
> believe that the explanations should be understood by all programmers
> using the library without any artificial restrictions. As a model, I
> used the language used in the "RFC"s of the interenet, specifications
> that proved quite useful but are in plain language, understood by
> everyone.
> 
> My goal in this first approach is to start a technical report (TR) that
> could be further discussed within the community.
> 
> I thank you in advance for your attention. I remain available at any
> time for any question you may have concerning this project.
> 
> Yours sincerely
> 
> Jacob Navia
> Programmer

Looking at your deque.c implementation, I'm wondering why you decided to depend on 'Allocators' for your containers.  For example, why is the deque Add function invoking malloc at all?

Why not make use of the "container_of()" concept, and define the Add function as:

Add (struct deque* container, struct deque_node* node_to_add);


Someone needing a deque could then make use of the API via:

struct my_type
{
    int my_data;

    struct deque_node my_node;
};

struct deque container;

...

Add(&container, &my_type.my_node);


This would eliminate the need for STL-ish "allocators", would eliminate pointer chasing in the added elements, and would enable each element to be contained in multiple containers.  Furthermore, this style would be much closer to C philosophy.

[toc] | [prev] | [next] | [standalone]

#1396

Le 15/07/12 22:13, agottem@gmail.com a écrit :
>
> Looking at your deque.c implementation, I'm wondering why you decided to depend on 'Allocators' for your containers.

   For example, why is the deque Add function invoking malloc at all?
>
> Why not make use of the "container_of()" concept, and define the Add function as:
>
> Add (struct deque* container, struct deque_node* node_to_add);
>
>
> Someone needing a deque could then make use of the API via:
>
> struct my_type
> {
>      int my_data;
>
>      struct deque_node my_node;
> };
>
> struct deque container;
>
> ...
>
> Add(&container, &my_type.my_node);
>
>
> This would eliminate the need for STL-ish "allocators", would eliminate pointer

chasing in the added elements, and would enable each element to be 
contained in

multiple containers.  Furthermore, this style would be much closer to C 
philosophy.
>


Because I decided that I would follow the same way as the C++ STL does:

The container owns the memory of the stored objects.

This explains why allocators are needed.

Now, it is possible for the list and dlist containers to work with the
list elements themselves (your "nodes") for a limited number of
operations.

That is not the case for deque. Why?

Because deque has a limited API compared to lists or vectors since what
you are interested in, when using a deque, is the way you store and
retrieve the data.


What is the problem of storing an element in multiple containers that is
feasible without problems in the proposed library: you store just a
pointer to the objectinstead of the object itself. The  you can
store the object in as many containers as you wish.


jacob

[toc] | [prev] | [next] | [standalone]

#1398

Le 15/07/12 23:10, jacob navia a écrit :
> What is the problem of storing an element in multiple containers that is
> feasible without problems in the proposed library: you store just a
> pointer to the objectinstead of the object itself. The  you can
> store the object in as many containers as you wish.

That sentence makes no sense sorry. It should be:

For storing an object in multiple containers you store a pointer
to the object instead of the whole object. That way, it is YOU that owns
the memory and the library allocates just the space needed to
allocate a pointer.

[toc] | [prev] | [next] | [standalone]

#1399

On Sunday, July 15, 2012 4:10:09 PM UTC-5, jacob navia wrote:
> Because I decided that I would follow the same way as the C++ STL does:

I think it's a mistake to try and take the STL way of doing things and shoehorn it into C.  I suspect the value of having a container manage element memory is outweighed by the flexibility and stability of the "container_of" approach.

The container_of approach provides the following significant benefits:

1.  Functions like DequeAdd() can be error-free, avoiding needless error checking by the caller.

2.  I can lock a mutex around DequeAdd() knowing it'll do the minimum necessary to insert my element into the container.

3.  Elements can be trivially pre-allocated and added to the container without needing to bother with the complexity of an 'allocator'

4.  In the case of pre-allocated elements, containers can be trivially destroyed without needing to invoke a linear walk of the elements to free them.

5.  Adding an element to N containers won't result in N different calls to an allocator and N extra pointers to my element's data.

6.  The container_of method enables me to place the actual deque node anywhere within my structure.  This may be important when it comes to optimizing the arrangement of structures.

Personally, if I wanted to use STL style APIs, I'd use C++.  I use C precisely because those APIs aren't, in my opinion, good.


--Andrew

[toc] | [prev] | [next] | [standalone]

#1400

Le 16/07/12 01:15, agottem@gmail.com a écrit :
> On Sunday, July 15, 2012 4:10:09 PM UTC-5, jacob navia wrote:
>> Because I decided that I would follow the same way as the C++ STL does:
>
> I think it's a mistake to try and take the STL way of doing things and shoehorn it into C.

Well, there are two possible ways of doing it:

1) The container manages the data storage
2) The user of the library manages it.

I have followed a way that allows both to be possible:

You pass the data to the container: the container manages the data 
storage requirements

You pass a pointer to the data: You manage the storage requirements. The
container just allocates space for a pointer.

Note that the second choice implies an allocator anyway since even if 
the storage requiremenets are minimal, they are still there.

Note that save/restore functions are only meaningful when the container
owns the data. When you store just a pointer to the data those
functions are useless.

I suspect the value of having a container manage element memory is 
outweighed by the flexibility and stability of the "container_of" approach.

No, as I outlined above you can pass a pointer to the data and store 
only the pointer!

>
> The container_of approach provides the following significant benefits:
>
> 1.  Functions like DequeAdd() can be error-free, avoiding needless error checking by the caller.

Mmmm, NULL pointer checks should be done anyway

>
> 2.  I can lock a mutex around DequeAdd() knowing it'll do the minimum necessary to insert my element into the container.

The library approach now is the same... You can add a mutex within the
Deque.Add function

>
> 3.  Elements can be trivially pre-allocated and added to the container without needing to bother with the complexity of an 'allocator'

Yes, but the application needs to follow all allocations now. The
complexity is not in the container but in each application.

And this is very important point. The design philosophy within the
library was to have as much complexity as possible taken AWAY from the
application into the container, assuming that debugging the container
once will be easier as debugging all those allocations and releases
done in thousands of applications.

>
> 4.  In the case of pre-allocated elements, containers can be trivially destroyed without needing to invoke a linear walk of the elements to free them.

That is why you can change the allocator to a pool allocator, that frees 
all memory at once.

>
> 5.  Adding an element to N containers won't result in N different calls to an allocator and N extra pointers to my element's data.

Yes, that is an advantage when you are inserting. But deleting becomes a 
mess!

If you want to delete an element, you have to delete it in all the
containers you have stored it in. This problem exists also when you
just store a pointer in the container.

Normally, an object is stored in a single container in most applications.

>
> 6.  The container_of method enables me to place the actual deque node anywhere within my structure.

This may be important when it comes to optimizing the arrangement of 
structures.

Storing a pointer gives you the same advantages (and incovenients).

Basically the problem with your approach is that the container's data 
structures MUST be disclosed to the user since the compiler must
know their size. Using your example:

struct my_type
{
     int my_data;
     struct deque_node my_node;
};

The structure "deque_node" must be known to be able to be inserted
into another one...

This precludes all information hiding and ties client code to the
precise structure of the container. Each new version of the container
needs a recompilation of all client code.

Using the approach of the proposed library there is NO need for 
recompilation if a new version of the library changes its internal
data structures.

jacob

[toc] | [prev] | [standalone]

Back to top | Article view | comp.std.c

csiph-web